FAISS is not one algorithm — it is a library of interchangeable index structures for approximate nearest-neighbor (ANN) search over dense vectors, plus the machinery to compose them. The hard part of using it is rarely the API; it is the choice. Behind a single index.search(x, k) call sits a decision about which of a dozen index types to build — exact or approximate, compressed or full-precision, flat or partitioned or graph-based — and every choice trades three quantities against each other: recall (do you find the true neighbors?), speed (queries per second), and memory (bytes per vector). This piece is a map of the index zoo: what each family does, the knobs that move the trade-off, the compositional pattern that ties them together, the index_factory shorthand, and a worked example of how the right answer changes as your dataset grows from thousands to billions of vectors.
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.
The index factory: naming a whole pipeline in one string
Rather than construct these objects by hand, FAISS lets you spell out a full pipeline as a string passed to faiss.index_factory(d, "...") — a comma-separated recipe read left to right: an optional preprocessing step, the coarse structure, then the encoding.
"Flat" exact brute force
"IVF4096,Flat" IVF, 4096 cells, full vectors in each cell
"IVF4096,PQ64" IVF + product quantization, 64-byte codes
"HNSW32" HNSW graph, 32 links per node
"OPQ64,IVF16384,PQ64" rotate (OPQ), then IVF, then PQ
"PCA128,Flat" reduce to 128 dims, then exact searchSo "IVF4096,PQ64" reads as: partition into 4096 IVF cells, store each vector as a 64-byte PQ code (of the residual, automatically). A leading OPQ64 or PCA128 is a transform applied first — OPQ rotates the space so PQ compresses with less error, PCA reduces dimensionality. The factory string is the single most useful thing to learn about FAISS: it turns index selection into one legible sentence, and it is the notation benchmarks and papers use.
A worked choice: pick the index by dataset size
The right index is mostly a function of N and your memory budget. Assume 768-dim fp32 vectors (3 KB each) and a recall@10 target near 0.95.
| Vectors N | Raw size | Sensible factory string | Why |
|---|---|---|---|
| < 100K | < 0.3 GB | Flat | Brute force is fast enough; recall = 1.0 |
| 100K – 1M | 0.3–3 GB | HNSW32 | Best latency at high recall; no training |
| 1M – 10M | 3–30 GB | IVF16384,Flat | Partition for speed; full vectors keep recall easy |
| 10M – 100M | 30–300 GB | OPQ64,IVF65536,PQ64 | Compress to ~64 B/vec to fit RAM; OPQ recovers recall |
| > 100M | > 0.3 TB | OPQ32,IVF262144,PQ32 | Aggressive compression, many cells; shard on GPUs |
The through-line: as N climbs you move rightward across the triangle. Small data buys exactness for free; mid-scale spends memory on a graph to keep latency down; large scale is forced to compress, trading recall for a footprint that still fits and leaning on OPQ and re-ranking to claw recall back. Benchmark from these starting points.
GPU support: the same indexes, an order of magnitude faster
FAISS ships GPU implementations of the most-used indexes — GpuIndexFlat, GpuIndexIVFFlat, GpuIndexIVFPQ — and moving is usually two lines: build on CPU, then index_cpu_to_gpu(res, 0, index). The API and index math are identical; only throughput changes, often by 5–20× for batched search because distance computation and the IVF scan map cleanly onto thousands of GPU threads.
The trade is different resources. GPU memory is smaller and pricier than host RAM, which pushes you toward the compressed PQ indexes precisely when the dataset is large enough to want a GPU — the two pressures agree. FAISS can shard one index across multiple GPUs for billion-scale corpora, and brute-force GpuIndexFlat is fast enough on a GPU to extend the ‘just use Flat’ regime to larger N. A few CPU-only types (notably HNSW) have no GPU equivalent: if you need GPU throughput at scale, IVFPQ is the natural family, not the graph.