FAISS is a toolkit, not an algorithm
The first mental shift is to stop asking ‘how does FAISS search?’ and start asking ‘which index did I build?’ FAISS (Facebook AI Similarity Search) is a collection of index classes that all implement the same tiny interface — train, add, search — but differ enormously in how they store vectors and find neighbors. Some are exact, most approximate; some keep every float, most compress; some scan a shortlist, some walk a graph.
Because the interface is uniform, you can swap IndexFlatL2 for IndexIVFPQ without touching your query code — only the construction line changes. So the ‘math’ of FAISS is less a single formula than a small set of composable ideas — partitioning, quantization, graph traversal — and the arithmetic of how each moves recall, latency, and bytes.
IndexFlat: the exact baseline you measure against
The simplest index is IndexFlatL2 (or IndexFlatIP for inner product): store every vector verbatim and, at query time, compute the distance to all of them, then keep the top k. For N vectors of dimension d, one query costs O(N · d) multiply-adds and the index costs 4 · N · d bytes in fp32. Nothing is approximated, so recall is exactly 1.0 by definition.
That is precisely why Flat matters even when it is too slow to ship: it is the ground truth. You measure every approximate index’s recall against Flat’s answers — recall@k is the fraction of the true k neighbors also returned. And Flat is the right choice outright when N is small (up to roughly a hundred thousand to a million vectors): a brute-force scan is trivially parallel and cache-friendly, often faster than a fancy index’s overhead at that scale. Approximate only when the linear scan stops fitting your budget.
The three knobs: recall, speed, memory
Every FAISS design decision is a point in a triangle whose corners are recall, speed, and memory. You do not get to maximize all three; you buy one with another. Approximation buys speed by not looking at every vector — it examines a shortlist and accepts a small chance of a miss. Compression buys memory by storing each vector in a few bytes instead of 4d — and pays in recall, since a compressed vector’s distances are slightly wrong.
Two families of technique map onto two of the corners. Partitioning (IVF) and graphs (HNSW) attack speed: they cut how many vectors you compare against. Quantization (PQ, SQ, and friends) attacks memory: it shrinks each stored vector. The knobs you tune afterwards — nprobe, efSearch, the PQ code length — slide you along the recall axis at a fixed structural choice. This turns index selection into a budgeting exercise: fix the two corners your deployment constrains, and recall is what you tune as high as it will go.
IVF: coarse quantization and the nprobe dial
IndexIVFFlat — inverted file — is the workhorse for speed. Training runs k-means over a sample to find nlist centroids; each owns a cell (a Voronoi region) and its own posting list, and every database vector is stored in its nearest centroid’s list. This assignment is the coarse quantizer: it maps a vector to one of nlist cells.
At query time you do not scan all N vectors. You find the nprobe centroids nearest the query, then scan only those cells — roughly nprobe / nlist of the database. With nlist = 4096 and nprobe = 16 you touch about 0.4% of vectors, a ~256× speedup over Flat. The risk: a true neighbor can sit just across a boundary in an unprobed cell, so recall drops. nprobe trades it back — probe 1 cell for maximum speed, probe 64 to approach exhaustive recall. A common start is nlist ≈ sqrt(N), then sweep nprobe on a validation set until recall clears target.
PQ and IVFPQ: compressing the vectors themselves
IVF cuts how many vectors you compare; it does nothing for the 4d bytes each costs. At a billion vectors that memory is the wall. Product Quantization (PQ) is the answer: split each vector into m sub-vectors and encode each as the nearest of 256 learned centroids — one byte apiece. A vector becomes just m bytes. PQ64 stores a 768-dim vector in 64 bytes instead of 3072, a 48× shrink, and distances come from small precomputed lookup tables rather than full arithmetic. (The codebook and asymmetric-distance mechanics live in the sibling product-quantization and OPQ articles — here PQ is just the memory knob.)
IndexIVFPQ combines both: IVF partitions for speed, PQ compresses for memory. It is the default choice for large, memory-constrained corpora — the shortlist and the tiny footprint. The cost is compounded approximation: you may probe the wrong cell and your distances are lossy, so recall needs watching. A cheap fix is re-ranking — retrieve a larger candidate set with the compressed index, then re-score those few with exact distances.
The pattern underneath: coarse quantizer plus residual
IVFPQ hides an elegant trick worth naming, because it recurs throughout FAISS. Once IVF assigns a vector to a centroid, that centroid is already a coarse approximation. So FAISS PQ-encodes not the raw vector but the residual — the vector minus its centroid, r = x − c. Residuals are smaller and more concentrated, so the same PQ bytes capture them more accurately, and the vector is reconstructed as centroid + decode(PQ code): a coarse part plus a fine correction.
This coarse-quantizer + residual-encoding pattern is the load-bearing idea behind FAISS’s billion-scale indexes. It is why the coarse quantizer is a pluggable object — you can even use an HNSW graph as the coarse quantizer to find the right cells faster when nlist is huge. Multi-level variants push the recursion further: quantize coarsely, then keep quantizing the leftover error. Recognizing it makes the exotic composite indexes read as variations on one theme rather than a bag of unrelated tricks.
HNSW: the graph option for speed without partitions
The other route to a small shortlist is a navigable graph. IndexHNSWFlat builds a hierarchical proximity graph — each vector a node linked to its near neighbors, with sparse long-range links in upper layers — and a query greedily walks toward the target, examining only a path’s worth of vectors. It typically delivers the best recall-vs-speed curve of any FAISS index and needs no training, which makes it attractive for mid-scale, latency-critical, in-memory search.
The catch is memory: HNSW keeps the full vectors and the graph edges, so it is the memory-hungriest option — often 1.5–2× the raw vectors. Its search knob is efSearch (how wide to keep the candidate frontier), the direct analogue of nprobe: raise it for recall, lower it for speed. The graph and its construction math are covered in the sibling HNSW article; for index selection the one-liner is HNSW when you have the RAM and want the best latency at fixed recall; IVF when you cannot afford the memory or must scale past RAM.