Faiss

Part I: The mental model

index.search(xq, k)                       Python (numpy)     faiss/python/class_wrappers.py
        |
SWIG binding into C++                     one .so per CPU    faiss/python/loader.py picks AVX2/AVX512
        |
IndexIVF::search                          orchestration      faiss/IndexIVF.cpp
        |
quantizer->search(xq, nprobe)             coarse quantizer   an IndexFlat (or HNSW) over nlist centroids
        |
search_preassigned                        per-probe loop     faiss/IndexIVF.cpp
        |
scanner: build ADC table for this list    M*ksub lookups     faiss/impl/ProductQuantizer.cpp
scan_codes over the inverted list         table sums         faiss/invlists/InvertedLists.h
        |
max-heap of current top-k                 replace-top        faiss/utils/Heap.h
        |
heap_reorder -> sorted (D, I) back to numpy

The one-sentence identity: Faiss is a menu of data structures that all implement one tiny contract, train, add, search, over dense float vectors, where each structure is a different named point in the triangle of recall, speed, and memory. The library's genius is not any single algorithm but the composition: a pruning structure (inverted lists, a graph) decides which vectors to look at, an encoding (raw floats, quantized codes) decides what looking at one costs, and the two choices are independent.

The canonical composed index, and this chapter's specimen, is IndexIVFPQ: k-means partitions the vector space into nlist cells, every database vector is stored in the inverted list of its nearest centroid as a product-quantized code of a few bytes, and a query visits only the nprobe most promising cells, computing approximate distances straight from the codes without ever decompressing them. That one design is why a billion vectors fit in RAM on one machine and why a query over them costs milliseconds.

Everything else in the repository hangs off this skeleton: the flat indexes are the contract with no pruning and no compression, HNSW swaps the pruning strategy for a navigable graph, OPQ and scalar quantizers swap the encoding, the factory string is a grammar for naming compositions, and the GPU tree reimplements the hot compositions for CUDA. If you understand one IVFPQ query end to end, you can place every file in the repository.

Part II: Using it

Installing

The official binaries ship through conda, on Linux and macOS alike (the pip packages of the same names are community builds):

# Linux or macOS, CPU
conda install -c pytorch -c conda-forge faiss-cpu=1.14.3

# Linux with NVIDIA GPUs
conda install -c pytorch -c nvidia -c conda-forge faiss-gpu=1.14.3

There is no GPU build for macOS; the CPU package covers Apple Silicon. A quick smoke test:

python -c "import faiss; print(faiss.__version__)"   # 1.14.3

First session: exact search in four lines

import numpy as np
import faiss

d = 128
rng = np.random.default_rng(0)
xb = rng.random((100_000, d), dtype="float32")
xq = rng.random((5, d), dtype="float32")

index = faiss.IndexFlatL2(d)
index.add(xb)
D, I = index.search(xq, 5)
print(I[0])   # e.g. [90923 51641 67989 27636 88863], ids of the 5 nearest
print(D[0])   # squared L2 distances, ascending, e.g. [13.19 13.32 13.51 ...]

Exact ids and distances vary with the random data; the shape contract does not: D and I are (nq, k), distances ascending for L2. Two conventions to absorb immediately: Faiss returns squared L2 distances (no square root is taken, since it does not change the ranking), and ids are sequential integers assigned in add order unless you arrange otherwise.

The first approximate index, and the first mistake

Approximate indexes have internal structure that must be learned from data before anything can be added. Forgetting that is the canonical first error:

# WRONG: add before train
index = faiss.index_factory(d, "IVF1024,Flat")
index.add(xb)          # RuntimeError: ... is_trained ...

# RIGHT: train, then add, then search
index = faiss.index_factory(d, "IVF1024,Flat")
index.train(xb)        # runs k-means for the 1024 centroids
index.add(xb)
index.nprobe = 16      # search-time knob; the default is 1
D, I = index.search(xq, 5)

The second line of that fix matters as much as the first: the default nprobe is 1, which visits one cell in a thousand and produces recall bad enough to make IVF look broken. A large fraction of "Faiss gives wrong results" reports are this default. Sweep nprobe and measure recall before concluding anything.

Cosine similarity is a preprocessing step

Faiss has L2 and inner-product metrics (plus a few exotic ones). Cosine similarity is not a separate metric; it is inner product over normalized vectors, and forgetting to normalize the queries too is the classic half-bug:

# WRONG: inner product over unnormalized embeddings, "cosine" in name only
index = faiss.IndexFlatIP(d)
index.add(xb)

# RIGHT: normalize both sides, then inner product == cosine
xb_n = xb.copy(); faiss.normalize_L2(xb_n)
xq_n = xq.copy(); faiss.normalize_L2(xq_n)
index = faiss.IndexFlatIP(d)
index.add(xb_n)
D, I = index.search(xq_n, 5)   # D is cosine similarity, descending

Dtypes, ids, and persistence

The API is float32; passing float64 does not error, because the Python wrappers call np.ascontiguousarray(x, dtype="float32"), which means every call silently copies and converts your array. Cast once at the boundary. Custom ids need either an index that supports add_with_ids natively (the IVF family does) or an IndexIDMap wrapper around one that does not (flat indexes). Persistence is two functions, and the file is a faithful snapshot of the whole object graph:

faiss.write_index(index, "vectors.faiss")
index2 = faiss.read_index("vectors.faiss")   # trained, populated, ready

Scaling the same four lines

The endgame of the tutorial is realizing that everything above survives at scale with only the factory string changing: "Flat" for exactness, "HNSW32" when memory is cheap and latency matters, "IVF65536,PQ32" when a hundred million vectors must fit in a modest box, with index.nprobe or efSearch as the live recall dial. Moving any CPU index to a GPU is a wrapper, faiss.index_cpu_to_gpu(faiss.StandardGpuResources(), 0, index), covered at concept level in Part VIII.

Part III: When it is the right tool

Faiss is the right tool when the problem is the search itself: offline batch retrieval over embeddings, the retrieval core inside a service you are building (the position it occupies in my RAG design and visual search design write-ups), deduplication and clustering at scale (its k-means is among the fastest available), research on ANN structures, and any setting where you want in-process search with no network hop and total control of the memory layout.

The alternatives divide by what they add or remove. hnswlib is a leaner choice when the answer is exactly "one HNSW graph in RAM" and nothing else. ScaNN ships Google's anisotropic quantization with excellent recall-per-cycle on CPU. And the managed vector databases, Milvus, Qdrant, Weaviate, pgvector inside Postgres, exist because Faiss is deliberately not a database: it has no durability story, no replication, no metadata filtering beyond ID selectors, no live CRUD semantics under concurrent writers, and no server. Several of them embed or reimplement Faiss structures; what you are buying is the operational shell around the index, and when you need that shell, buy it rather than build it.

That is also the architecture-shaped warning. The tempting design is one long-lived index object inside a service, mutated in place by writers while readers search it. Faiss's actual contract is that concurrent searches are safe but any mutation concurrent with anything is yours to synchronize, and index quality decays as the data distribution drifts from what train saw. The safe architecture treats indexes as immutable, versioned artifacts: build offline, ship a file, swap a pointer, keep a small sidecar (flat or HNSW) for fresh vectors, and retrain on a schedule.

SAFE                                      DANGEROUS
builder job -> index.v42 file             one shared IndexIVFPQ object
   -> replicas read_index(v42)            writers: add()/remove_ids() live
   -> atomic swap, delete v41             readers: search() concurrently
fresh writes -> small sidecar index       -> races, stale centroids,
searched alongside, merged at rebuild        unbounded quality drift

Part IV: The full life of one query

The canonical operation: one query vector through index = faiss.index_factory(128, "IVF4096,PQ8"), trained and filled with 10 million vectors, index.nprobe = 16, index.search(xq, 10). Every stage names the file that owns it.

Stage 1: the Python surface

import faiss runs faiss/python/loader.py, which inspects the CPU and loads the most capable compiled variant of the SWIG-generated module (AVX512, AVX2, or scalar; SVE on ARM). The class you hold is a SWIG proxy for the C++ IndexIVFPQ, but the method you call is not raw SWIG: faiss/python/class_wrappers.py replaces search with replacement_search, which validates the (n, d) shape, makes the array contiguous float32, allocates the (n, k) result matrices, and passes raw pointers across the boundary. The binding layer is deliberately dumb; no search logic lives in Python.

Stage 2: orchestration in IndexIVF::search

faiss/IndexIVF.cpp owns the top of the C++ call. It resolves the effective nprobe (clamped to nlist, overridable per call via SearchParameters), then splits large query batches into slices parallelized with OpenMP. For each slice it runs a two-phase plan: coarse quantization, then preassigned search. The same file maintains indexIVF_stats, global counters of lists visited, codes scanned, and heap updates, which Part X uses as a measurement tool.

Stage 3: coarse quantization

The "which cells" question is itself a nearest-neighbor search: quantizer->search(n, x, nprobe, coarse_dis, idx), where the quantizer is a plain IndexFlat over the 4096 centroids that train learned (large nlist deployments use an HNSW quantizer here, which is what the factory spelling IVF65536_HNSW32 means). The result is 16 cell ids with their distances. The recursion is worth savoring: Faiss prunes a big search using a small exact search over the summary it built of the data.

Stage 4: setup for the scan

search_preassigned (same file) initializes the result heap for each query, k slots managed by the heap primitives in faiss/utils/Heap.h (a max-heap for L2, so the worst current candidate sits at the top for cheap replacement), chooses a parallelization mode (parallel_mode: over queries by default, over probes for low-query-count workloads), and asks the index for a get_InvertedListScanner(), the strategy object that knows how to score this index's codes. Inverted lists themselves live behind the InvertedLists abstraction in faiss/invlists/, in-RAM arrays by default, memory mapped on-disk variants (OnDiskInvertedLists.h) when data exceeds RAM.

Stage 5: the ADC distance table

For each probed cell, the scanner (built in faiss/IndexIVFPQ.cpp) prepares asymmetric distance computation. The query is not quantized; instead, for this cell, compute the residual r = x minus centroid (IVFPQ encodes residuals by default, by_residual = true), then build a table of distances from r's subvectors to every codebook centroid: for M = 8 subquantizers with ksub = 256 centroids each, a table of 8 x 256 = 2048 floats (ProductQuantizer::compute_distance_table in faiss/impl/ProductQuantizer.cpp). All the geometry of a 128-dimensional distance is now precomputed; scoring a code will be table lookups. (An optional use_precomputed_table mode moves part of this work to build time at a memory cost; the long comment above initialize_IVFPQ_precomputed_table in IndexIVFPQ.cpp is the best writeup of the trick.)

Stage 6: scanning codes

scanner->scan_codes(list_size, codes, ids, ...) is the hot loop of the entire library: for each 8-byte code in the inverted list, the approximate distance is the sum of 8 table entries, table[0][code[0]] + table[1][code[1]] + ..., about 390 thousand codes for our 16 probes over 10 million balanced vectors, and each candidate that beats the heap's worst entry replaces it via maxheap_replace_top. The SIMD-blocked FastScan variants (IndexIVFPQFastScan, 4-bit codes scored with register-resident lookup tables) exist because even this loop has a faster shape when codes shrink to fit SIMD registers.

Stage 7: return

After the last probe, heap_reorder sorts each heap into ascending distance order, stats are accumulated, and the preallocated numpy arrays from Stage 1 are already full: the (5, 10) D and I the caller receives were written in place by C++. Total work per query: 4096 exact 128-dim distances, 16 tables of 2048 entries, ~390k sums of 8 bytes' worth of lookups, ~10 heap replacements that survive. Compare the flat baseline: 10 million exact 128-dim distances.

Part V: Deep dive: the families, and PQ by the numbers

Every index is a point in the recall/speed/memory triangle, and the families are named strategies for trading among the corners:

Product quantization deserves the numbers, because the numbers are the idea. Take d = 128, M = 8 subvectors of dsub = 16 dimensions, nbits = 8 so ksub = 256 centroids per subquantizer. Training runs k-means 8 times, once per 16-dimensional slice of the data, producing codebooks of 8 x 256 x 16 = 32,768 floats, 131 KB total. Encoding a vector snaps each slice to its nearest centroid and records the 8 one-byte centroid ids:

vector (512 bytes)   [ x0..x15 | x16..x31 | ... | x112..x127 ]
                          |          |                |
nearest centroid id      142         7               209
code (8 bytes)       [142, 7, ..., 209]        64x compression

effective codebook: 256^8 = 1.8e19 virtual centroids
from only 8*256 = 2048 stored ones: the product in "product quantization"

The compounding matters at fleet scale: 100 million vectors at d = 128 are 51.2 GB raw, 0.8 GB as PQ8 codes (plus ids and centroids). And the codes are not just storage, they are a compute format: with the query's 2048-entry table from Part IV, a distance costs 8 loads and 7 adds instead of 128 multiplies and adds, which is where the speed of the scan comes from. The approximation error is the sum of each subquantizer's quantization error; OPQ (OPQ16_64 in factory spelling) learns a rotation first so variance spreads evenly across subvectors and dimensions within them, cheap insurance that usually buys several recall points.

The famous trap in this family: PQ distances are estimates, so the top-k by code distance is not the true top-k, and the fix is to re-rank: retrieve a few times k candidates by code, then rescore just those with exact vectors, which is the IndexRefine wrapper (,RFlat as a factory suffix) or, in RAG-style systems, the re-ranking stage downstream. A second correction worth stating: IVF's recall failures are not random noise; they happen when the true neighbor sits in a cell you did not probe, which is systematically more likely for queries near cell boundaries. Raising nprobe is the cure, and recall versus nprobe is the first curve to plot for any deployment.

Part VI: Deep dive: the index_factory grammar

With families that compose, constructing indexes by hand gets verbose, so Faiss exposes a small language. faiss.index_factory(d, spec) parses a comma-separated spec of up to three parts, an optional preprocessing transform, the coarse structure, and the encoding, plus an optional refinement suffix, and builds the object graph. The parser is faiss/index_factory.cpp, and it is literally a pile of regular expressions (match("PCA(W?)(R?)([0-9]+)") and friends), which makes it a readable, exhaustive catalog of what exists:

"Flat"                    IndexFlatL2
"HNSW32"                  IndexHNSWFlat, 32 links per node
"IVF4096,Flat"            IndexIVFFlat: prune, store raw
"IVF4096,PQ8"             IndexIVFPQ: prune, store 8-byte codes
"PCA64,IVF4096,PQ8"       IndexPreTransform -> PCA to 64 dims -> IVFPQ
"OPQ16_64,IVF4096,PQ16"   learned rotation -> prune -> 16-byte codes
"IVF65536_HNSW32,PQ16"    HNSW as the coarse quantizer over 65536 centroids
"IVF4096,PQ8,RFlat"       + exact re-ranking over the raw vectors
"IVF1024,SQ8"             scalar quantizer: 1 byte per dimension

Learning to read factory strings is learning Faiss: every deployed index is one of these one-liners, every benchmark in the ANN literature can be named in the grammar, and the string is the natural unit of configuration to A/B test. What the string does not fix are the search-time knobs, nprobe for IVF, efSearch for HNSW (default 16, in faiss/impl/HNSW.h), k_factor for refinement, and those are exactly the parameters that trade latency for recall on a live system. The ParameterSpace machinery in faiss/AutoTune.h can sweep them against a ground truth to map the frontier; tutorial/python/ and demos/demo_auto_tune.py show it working.

A useful habit: after building from a string, walk the object graph to confirm what you got, since composition means your "index" may be a transform wrapping an IVF wrapping a quantizer:

index = faiss.index_factory(128, "OPQ16_64,IVF4096,PQ16")
print(type(index))                        # IndexPreTransform
inner = faiss.downcast_index(index.index) # the IVFPQ inside
print(inner.nlist, inner.pq.M)            # 4096 16
quant = faiss.downcast_index(inner.quantizer)
print(type(quant))                        # IndexFlat(L2) over centroids

Part VII: Deep dive: the three lifecycles

Faiss separates what most databases fuse: train learns structure from a sample, add populates, search queries, and the separation is load-bearing. Training an IVF4096,PQ8 index runs k-means for 4096 coarse centroids and 8 more k-means runs for the PQ codebooks. It does not need all your data: the clustering code (faiss/Clustering.h) subsamples to at most max_points_per_centroid = 256 points per centroid and warns below min_points_per_centroid = 39, so for nlist = 4096 something like one to two million representative vectors is a sensible training set, and training on a small uniform sample of the corpus is standard practice.

Three consequences follow. First, is_trained is a real state, and adding before training throws. Second, the centroids freeze at train time: you can keep adding vectors forever, but if the distribution drifts, vectors land in increasingly wrong cells and recall decays silently, which is why the safe architecture in Part III retrains on a schedule. Third, training is the expensive, offline step and search-time knobs are cheap, so the tuning loop is: fix a factory string, train once, then sweep nprobe-class knobs against a ground truth built with a flat index (the contrib/evaluation.py helpers exist for exactly this).

The add and persistence lifecycles have their own file-level homes worth knowing: add_with_ids and deletion by IDSelector live in the IVF family with a DirectMap (in faiss/invlists/) when you need id-to-location lookup; serialization is faiss/impl/index_write.cpp and index_read.cpp, a tagged binary format that round trips the entire object graph, which is what makes the build-offline-ship-file architecture trivial; and beyond-RAM deployments swap the in-memory inverted lists for OnDiskInvertedLists without changing the index logic above them.

Concurrency, stated precisely because it is the trap: search is const and thread-safe from many threads against a quiescent index and is itself internally parallelized with OpenMP; add, train, and remove_ids are not safe against anything concurrent. "Faiss is thread-safe" and "Faiss is not thread-safe" are both wrong sentences; the correct one is "reads share, writes exclude, and you hold the lock."

Part VIII: Deep dive: the GPU tree, at concept level

faiss/gpu/ mirrors the hot CPU indexes as CUDA implementations: GpuIndexFlat, GpuIndexIVFFlat, GpuIndexIVFPQ, plus GpuIndexCagra binding the cuVS CAGRA graph index from NVIDIA's RAPIDS work. The same Index contract holds, so faiss.index_cpu_to_gpu (the cloner in faiss/gpu/GpuCloner.cpp) converts an existing CPU index, and StandardGpuResources owns the memory pools and streams that make repeated searches allocation-free.

Concept level is the right level here because the GPU tree's design point differs: it wants big query batches to amortize kernel launches and PCIe transfers, it keeps k-selection on the GPU with specialized heap kernels rather than round-tripping candidates, and it historically imposed stricter parameter limits than CPU (notably k and nprobe caps at 2048). A single query at a time on a GPU index can easily lose to AVX512 CPU code; a hundred thousand queries in one call is where the GPU version wins by an order of magnitude. If your workload is offline embedding joins or index construction (GPU k-means for training, then move to CPU for serving), the GPU tree is the right tool; latency-critical single-query serving usually is not, and the CPU FastScan indexes are the competitor to beat.

Part IX: Reading the repository

Faiss is a C++ library first, with the Python API generated from it, so read C++ headers even if you only ever call Python; names map one to one. Every path below exists at release 1.14.3.

Stage 0: the contract

Read faiss/Index.h completely: the abstract base class, maybe two hundred meaningful lines, defining train, add, search, range_search, reconstruct, and the codec interface (sa_encode/sa_decode). Then faiss/MetricType.h. Questions you should be able to answer: why do all results come back as (distances, labels) matrices; what does is_trained gate; what id conventions does add promise?

Stage 1: the smallest real index, and the tutorial

Read faiss/IndexFlat.h/.cpp, which is the contract with no ideas in it, then run the numbered scripts in tutorial/python/ (1-Flat.py, 2-IVFFlat.py, 3-IVFPQ.py, 6-HNSW.py, 7-PQFastScan.py). Questions: where does brute-force distance computation actually happen (follow it into faiss/utils/distances.h); what changes between the three tutorial index types in code written against them?

Stage 2: the heart

Read faiss/IndexIVF.h and then IndexIVF::search and search_preassigned in faiss/IndexIVF.cpp with Part IV of this chapter beside you, plus faiss/invlists/InvertedLists.h. Questions: where exactly does coarse quantization happen; what does an InvertedListScanner abstract over; what do the parallel_mode values parallelize?

Stage 3: the encodings

Read faiss/impl/ProductQuantizer.h/.cpp against the 2011 Jégou et al. paper, then faiss/IndexIVFPQ.cpp (especially the precomputed-tables comment block), then faiss/impl/HNSW.h/.cpp against the Malkov and Yashunin paper. Questions: what is asymmetric about ADC; why encode residuals inside IVF; what do efSearch and efConstruction each control?

Stage 4: the grammar and the edges

Read faiss/index_factory.cpp top to bottom as a catalog, skim faiss/impl/index_write.cpp to see the serialization format, then sample the outer rings as interest dictates: faiss/gpu/, contrib/ (datasets.py, evaluation.py, ivf_tools.py), benchs/ for reproduced paper results, c_api/ for the C shell other languages bind.

Where not to start

Do not start in faiss/utils/ (SIMD distance kernels, meaningful only once you know who calls them), in faiss/impl/'s FastScan and additive-quantizer corners (research-frontier code with the highest churn), or in the SWIG layer (faiss/python/swigfaiss.swig is plumbing). And do not read any of it before running the tutorial scripts; this library rewards touching first.

Part X: Hands-on labs

All labs run on CPU. Timings vary with hardware; trends and shapes should reproduce. Setup shared by labs 1 to 4:

import numpy as np, faiss, time
d, nb, nq = 64, 200_000, 500
rng = np.random.default_rng(0)
xb = rng.standard_normal((nb, d), dtype="float32")
xq = rng.standard_normal((nq, d), dtype="float32")
gt = faiss.IndexFlatL2(d); gt.add(xb)
_, I_true = gt.search(xq, 10)                  # ground truth top-10

Lab 1: recall is a dial (concept: Parts V, VII)

index = faiss.index_factory(d, "IVF1024,Flat")
index.train(xb); index.add(xb)
for nprobe in [1, 2, 4, 8, 16, 32, 64]:
    index.nprobe = nprobe
    t0 = time.perf_counter(); _, I = index.search(xq, 10)
    dt = time.perf_counter() - t0
    recall = (I == I_true).sum() / I_true.size
    print(f"nprobe={nprobe:3d} recall@10={recall:.3f} qps={nq/dt:,.0f}")

Observe: recall climbing from roughly 0.2-0.4 at nprobe=1 toward 0.95+ at 64 while QPS falls a few fold. This one curve is the IVF trade in its entirety, and the nprobe=1 row is why the default burns beginners.

Lab 2: PQ, felt numerically (concept: Part V)

pq = faiss.ProductQuantizer(d, 8, 8)     # M=8 subvectors, 8 bits each
pq.train(xb)
codes = pq.compute_codes(xb[:5])
print(codes.shape, codes.dtype)          # (5, 8) uint8: 8 bytes per vector
recon = pq.decode(codes)
err = np.linalg.norm(xb[:5] - recon, axis=1) / np.linalg.norm(xb[:5], axis=1)
print(err)                               # relative error, commonly ~0.5-0.9
                                         # for random Gaussian data

Observe: 64 to 1 compression and a large per-vector reconstruction error, yet Lab 1's machinery still ranks neighbors usefully, because ranking tolerates far more distance error than reconstruction does. Note random Gaussian data is PQ's worst case; real embeddings, which concentrate on lower-dimensional structure, quantize much better.

Lab 3: read the object graph (concept: Part VI)

index = faiss.index_factory(d, "OPQ8_32,IVF256,PQ8")
index.train(xb); index.add(xb)
print(type(index).__name__)                        # IndexPreTransform
vt = faiss.downcast_VectorTransform(index.chain.at(0))
print(type(vt).__name__, vt.d_in, vt.d_out)        # OPQMatrix 64 32
ivf = faiss.downcast_index(index.index)
print(type(ivf).__name__, ivf.nlist, ivf.pq.M)     # IndexIVFPQ 256 8

Observe: the factory string reads left to right as the object graph reads outside in. Change the string, re-inspect, and the grammar of Part VI becomes muscle memory.

Lab 4: count the work, don't guess it (concept: Part IV)

index = faiss.index_factory(d, "IVF1024,PQ8")
index.train(xb); index.add(xb)
for nprobe in [1, 8, 64]:
    index.nprobe = nprobe
    stats = faiss.cvar.indexIVF_stats; stats.reset()
    index.search(xq, 10)
    print(f"nprobe={nprobe:3d} lists={stats.nlist/nq:7.1f} "
          f"codes={stats.ndis/nq:9.0f} heap_updates={stats.nheap_updates/nq:6.0f}")

Observe: codes scanned per query scales linearly with nprobe (about nprobe/1024 of the 200k database), while heap updates stay tiny. The cost model from Part IV, stage 7, printed by the library itself.

Lab 5: files as the deployment unit (concept: Parts III, VII)

flat = faiss.IndexFlatL2(d); flat.add(xb)
faiss.write_index(flat, "flat.faiss")
ivfpq = faiss.index_factory(d, "IVF1024,PQ8")
ivfpq.train(xb); ivfpq.add(xb)
faiss.write_index(ivfpq, "ivfpq.faiss")
# ls -l: flat.faiss ~51 MB (200k * 64 * 4 bytes), ivfpq.faiss ~3.5 MB
back = faiss.read_index("ivfpq.faiss")
print(back.ntotal, faiss.downcast_index(back.quantizer).ntotal)  # 200000 1024

Observe: the serialized file carries the trained centroids, the codebooks, the codes, and the ids, so a reader process needs zero retraining, which is what makes the build-then-swap architecture from Part III a rename plus a read_index.

Lab 6: the refine escape hatch (concept: Part V)

for spec in ["IVF1024,PQ8", "IVF1024,PQ8,RFlat"]:
    index = faiss.index_factory(d, spec)
    index.train(xb); index.add(xb)
    ps = faiss.ParameterSpace()
    ps.set_index_parameter(index, "nprobe", 32)
    _, I = index.search(xq, 10)
    print(spec, "recall@10 =", (I == I_true).sum() / I_true.size)

Observe: re-ranking PQ candidates against exact vectors recovers several recall points for the price of storing the raw vectors again, a pure memory-for-recall trade, and note ParameterSpace setting nprobe through the wrapper, which is the idiom for knobs on composed indexes.

Part XI: Questions and model answers

Q1. What is Faiss, in one sentence that distinguishes it from a vector database?

Faiss is an in-process C++/Python library of vector index data structures behind a train/add/search contract; it deliberately provides no server, durability, replication, or metadata filtering, which is exactly the layer vector databases add, often on top of Faiss's own structures.

Q2. Walk through one IVFPQ query at a high level.

The query is compared exactly against the nlist coarse centroids to pick the nprobe nearest cells; for each cell, the query's residual builds an M by ksub table of subvector-to-centroid distances; each stored code in the cell is scored as M table lookups summed; candidates that beat the current worst enter a k-slot max-heap; heaps are sorted and returned as (D, I).

Q3. Why does IVFPQ encode residuals rather than raw vectors?

Within a cell, vectors share their centroid's location, so the residual distribution is centered and much lower variance than the raw data, and the same code budget quantizes it more accurately. The cost is that distance tables become cell-dependent, which is why they are built per probe, and why the precomputed-tables optimization exists.

Q4. What exactly does train do, and what happens if you skip or reuse it badly?

Train runs k-means for the coarse centroids and per-subvector codebooks (on a subsample, at most 256 points per centroid). Skipping it throws at add time via is_trained. Reusing a training done on last year's distribution silently degrades recall as vectors land in poorly fitting cells, which is an argument for scheduled rebuilds, not a code fix.

Q5. How do you get cosine similarity?

Normalize database and query vectors to unit length with faiss.normalize_L2 and use an inner-product index (IndexFlatIP or metric argument); cosine is then identical to inner product. Normalizing only one side is the classic half-bug.

Q6. Why 8 bytes can beat 512: what makes PQ distances fast, not just small?

ADC precomputes, per query, the distance from each query subvector to all 256 centroids of each subquantizer; a code's distance is then M table lookups and adds instead of a d-dimensional arithmetic pass. Compression pays once in memory and again in compute format.

Q7. When would you pick HNSW over IVF, and what does it cost?

HNSW needs no training, handles incremental adds gracefully, and reaches high recall at low latency for datasets that fit in RAM with room to spare; it pays in memory for links (dozens of extra bytes per vector at HNSW32), slower construction, and no compression story of its own, which is why beyond tens of millions of vectors IVF+PQ variants usually take over.

Q8. Read this string: "OPQ16_64,IVF4096_HNSW32,PQ16,RFlat".

Learn a rotation and project to 64 dimensions (OPQ with 16 blocks); partition into 4096 cells whose coarse quantizer is itself an HNSW graph (for fast centroid lookup at large nlist); store 16-byte PQ codes in the lists; after the code scan, re-rank the shortlist against stored raw vectors.

Q9. What are the search-time knobs, and why do they matter operationally?

nprobe (IVF), efSearch (HNSW), and k_factor (refinement) trade latency for recall without touching the built index, so a live service can move along the frontier per request class; everything baked into the factory string requires a rebuild to change.

Q10. Your recall is fine on a benchmark but poor in production. Name three suspects.

Default nprobe=1 left in place; distribution drift between the training sample and production vectors (or training on synthetic/random data); and a metric mismatch, such as embeddings trained for cosine being searched with unnormalized L2 or inner product. A fourth classic: measuring recall against no ground truth at all, rather than a flat index over the same data.

Q11. What is thread-safe in Faiss?

Concurrent search calls against an index nobody is mutating are safe, and single searches are internally OpenMP-parallel. Any concurrent add, train, or remove_ids requires external exclusion. The robust production pattern sidesteps the question: immutable index snapshots swapped atomically.

Q12. How does Faiss handle ids, and where do people trip?

Plain indexes assign sequential ids in add order; IVF indexes support add_with_ids natively; flat indexes need an IndexIDMap wrapper for custom ids. The trip is deleting or re-adding while assuming ids are stable handles into external metadata; treat the mapping as your application's responsibility, with -1 reserved for "no result."

Q13. Compare Faiss and hnswlib for a 5-million-vector, RAM-resident, low-latency service.

Both would serve HNSW; hnswlib is smaller, header-only, and has fewer moving parts, a fine choice if HNSW is the final answer. Faiss buys option value: the same code path can move to IVF+PQ when the corpus grows tenfold, add refinement, use GPU for builds, and serialize uniformly, so the choice is really "is this system's index strategy settled forever?"

Q14. When are GPU indexes the right call?

Batch-heavy work: offline joins of millions of queries, index construction and k-means training, and research sweeps. The GPU tree wants big batches to amortize transfers and keeps k-selection on-device; single-query latency serving on a modern AVX-512 CPU with FastScan indexes is often faster and always cheaper, so serve on CPU unless the query volume is itself batch-shaped.

Q15. What would you measure first when a query is slow?

The work counters: reset faiss.cvar.indexIVF_stats, run the query, and read lists visited, codes scanned, and heap updates. That immediately separates "scanning too much" (nprobe or unbalanced lists, fix with tuning or better training) from "scanning is slow" (dtype conversion copies, non-contiguous arrays, missing SIMD build, thread contention), which have entirely different fixes.

Part XII: Design lessons

A tiny uniform contract makes a zoo composable. Everything is train/add/search over (n, d) float32, so indexes nest inside indexes: the coarse quantizer of an IVF is itself an Index, refinement wraps an Index around an Index, and the GPU tree substitutes freely. This is the same move as Unix file descriptors and PyTorch's Module: make the interface small enough that composition is the default, and the library's power becomes combinatorial.

Separate the pruning decision from the encoding decision. "Which candidates do I look at" and "what does looking at one cost" are orthogonal axes, and Faiss's families are their cross product. The same factoring appears in databases as index selection versus page format, and in search engines as candidate generation versus scoring; recognizing two fused concerns and splitting them is the recurring senior move.

Turn configuration into a language when the space is combinatorial. The factory string is a domain-specific grammar over the composition space, cheap to log, diff, and A/B test, with a regex parser anyone can read. Connection strings, ffmpeg filter graphs, and scikit-learn pipelines are the same pattern: when valid configurations form an algebra, name the algebra.

Precompute per-query, not per-candidate. The ADC table moves all d-dimensional geometry into one per-list setup step so the per-candidate cost collapses to lookups. The general form, hoist invariant work to the outermost loop that can hold it, is the essence of query compilation in databases and of shader specialization in graphics, and PQ is its cleanest small example.

Make cost observable, not inferable. indexIVF_stats ships in the library: lists visited, codes scanned, heap updates, per phase timings. Systems that expose their own work counters get debugged by their users; systems that do not get blamed. The EXPLAIN of a database and the stats blocks of Faiss are the same design conviction.

Part XIII: Memorization framework

One sentence: Faiss is train/add/search over composable index structures, where a coarse structure prunes the candidate set, an encoding sets the cost of scoring each candidate, and a heap keeps the top-k, with recall traded against speed and memory by named knobs.

query -> binding -> coarse quantize -> probe lists -> ADC table -> scan codes -> heap -> (D, I)

binding    faiss/python/class_wrappers.py    replacement_search: float32, shapes, pointers
orchestr.  faiss/IndexIVF.cpp                IndexIVF::search, nprobe, OpenMP slicing
coarse     (quantizer) faiss/IndexFlat.cpp   nprobe nearest of nlist centroids
setup      faiss/IndexIVF.cpp                search_preassigned, heap init, scanner
table      faiss/impl/ProductQuantizer.cpp   compute_distance_table, M x ksub floats
scan       faiss/IndexIVFPQ.cpp + invlists/  scan_codes: M lookups per code
heap       faiss/utils/Heap.h                maxheap_replace_top, heap_reorder

Memorize these blocks:

CONTRACT: train (learn structure, subsampled ~<=256 pts/centroid) -> add -> search.
float32 in, (nq, k) distances + int64 ids out; L2 distances are SQUARED; -1 = no result.

PQ NUMBERS: d=128, M=8, nbits=8 => dsub=16, ksub=256, code = 8 bytes (64x),
codebooks 8*256*16 floats, ADC table per query 8*256 = 2048 floats,
distance = 8 lookups + 7 adds. Virtual centroids: 256^8.

FACTORY GRAMMAR: [transform,] coarse, encoding [,refine]
OPQ16_64 , IVF4096(_HNSW32) , PQ16 , RFlat.  Search knobs stay live:
nprobe (IVF, default 1!), efSearch (HNSW, default 16), k_factor (refine).

TRIANGLE: Flat = exact corner; IVF = tunable pruning; HNSW = memory-for-latency graph;
PQ/OPQ = memory-for-accuracy encoding; compose IVF+PQ+refine for billion scale.

OPERATIONS: library not database; searches share, mutations exclude;
ship immutable index files (write_index/read_index) and swap; retrain on drift.

Final takeaway