Definition
Approximate nearest neighbor (ANN) search returns vectors that are probably among the closest to a query, without comparing the query to every stored vector. Three ideas dominate practice: graph search with HNSW (Malkov and Yashunin, arXiv 2016, IEEE TPAMI 2020), the inverted file (IVF) of k-means lists, and product quantization (PQ) (Jégou, Douze and Schmid, "Product quantization for nearest neighbor search", IEEE TPAMI 2011), which also introduced IVF+PQ (IVFADC).
Exact -NN costs distance computations of dimensions per query. For 10M vectors of 768 floats that is 7.7 billion multiply-adds per query, and 30.7 GB of float32 to read. A RAG retriever or recommender needs answers in milliseconds at hundreds of queries per second, so exact scans stop scaling somewhere around a few million vectors per machine. ANN indexes are the engine inside every Vector databases product and every library such as FAISS (Johnson, Douze and Jégou, "Billion-scale similarity search with GPUs", 2017).
Quality is measured against brute force on the same data. The standard metric is recall@; cost is distance computations, latency or queries per second (QPS) at a target recall:
- the ids the index returns for query
- the true nearest ids, from a brute-force scan
HNSW: a navigable graph
HNSW builds a proximity graph incrementally. Each new point draws a level with and , so about a fraction of nodes reaches each next layer. The point is inserted by searching for its neighbours with a beam of efConstruction and linking it to at most of them per layer ( on layer 0). A heuristic keeps a candidate only if it is closer to the new point than to any neighbour already kept, so links spread in different directions and bridge clusters.
A query starts at the single top-layer entry point, moves greedily to the closest neighbour until no neighbour is closer, drops a layer, and repeats. On layer 0 it keeps a candidate list of size efSearch (at least ) and stops when the closest unexpanded candidate is farther than the worst of the list. The upper layers act like a skip list, giving roughly logarithmic scaling in . efSearch is the query-time knob: larger means more distance computations and higher recall. The paper suggests between 5 and 48: higher for high-dimensional data and high recall, at the price of memory.
IVF: scan only the closest lists
IVF trains = nlist k-means centroids on a sample, assigns every vector to its closest centroid, and stores one list per centroid. A query computes centroid distances, then scans the nprobe closest lists exhaustively. Neighbours that fall just across a boundary are missed unless more lists are probed. With balanced lists the cost per query is:
nlist, the number of k-means cells- average list length; real lists are uneven, so the scan is longer when the query falls in a dense region
The FAISS guidelines put nlist between and . IVF adds vectors cheaply (one centroid lookup each) and works well on GPUs, but the centroids are frozen at training time. If the data distribution drifts, the lists become unbalanced and recall at a fixed nprobe falls until you retrain.
PQ: compress the vectors themselves
PQ splits a -dimensional vector into sub-vectors of dimensions and runs k-means separately in each subspace, usually with centroids. A vector is then stored as one-byte centroid indices. For the query, PQ builds a lookup table of sub-distances once. Every stored code is then scored with table lookups and adds, which is asymmetric distance computation (ADC):
- the -th sub-vector of the query and of the stored vector
- the -th codebook; is the index of the centroid closest to
- the query's distances to codebook , computed once per query
"Asymmetric" means the query stays exact and only the database side is quantized, which is more accurate than quantizing both. IVFADC quantizes the residual inside each IVF list rather than itself. The residuals are smaller, so the same code size loses less. Because is biased and noisy, production systems usually re-rank the top few hundred PQ candidates with the full-precision vectors.
Reference points
- PQ paper
- Jégou et al. (2011) used (8-bit) sub-quantizers; 64-bit codes () on SIFT descriptors were a standard setting.
- HNSW defaults
- , ; memory for the links is about bytes per vector on layer 0 (128 B at ), on top of the vectors.
- FAISS index strings
"HNSW32"(HNSW, , full vectors),"IVF4096,Flat"(IVF, uncompressed lists),"IVF4096,PQ64"(IVF with 64-byte PQ codes).nprobedefaults to 1.- Benchmarks
- ann-benchmarks (Aumüller, Bernhardsson and Faithfull) plots recall against QPS for many libraries on fixed datasets (SIFT, GloVe, Fashion-MNIST, …). Compare indexes at the same recall, never at default settings.
- Other families
- ScaNN (Guo et al., ICML 2020) uses anisotropic quantization tuned for inner product; DiskANN (Subramanya et al., NeurIPS 2019) keeps a graph on SSD with compressed vectors in RAM for billion-scale indexes on one machine.
Both indexes trace the same shape: recall climbs steeply and then saturates, and the last percent costs as much as the first eighty. The graph index needs about half the distance computations of IVF for 99% recall here. That gap is typical of in-memory benchmarks, and it is why HNSW is the common default. IVF and PQ win where memory or GPU batch throughput matter more.
Worked example
| j | x_j | Nearest centroid (code) | LUT_j for q (4 entries) | LUT_j[code] |
|---|---|---|---|---|
| 1 | (0.9, 0.1) | (1, 0) → 2 | 0.98, 2.98, 0.18, 0.08 | 0.18 |
| 2 | (0.4, 0.8) | (0.5, 1) → 3 | 0.50, 0.25, 1.00, 0.25 | 0.25 |
| 3 | (−0.3, 0.2) | (−0.5, 0) → 1 | 0.26, 0.16, 0.61, 1.01 | 0.16 |
| 4 | (0.6, −0.5) | (0.5, −0.5) → 0 | 0.02, 0.72, 1.37, 0.82 | 0.02 |
The code is : 8 bits in place of 32 bytes. ADC gives , while the exact , because each sub-vector sits up to 0.08 (squared distance) from its centroid, for a total reconstruction error of 0.16. Four centroids per subspace is a toy; with 256 the error is far smaller, but ranking errors remain, hence re-ranking.
Sizing IVF-PQ for 1M vectors of 768 dims
- 1Raw float32: B GB.
- 2
nlist: , so take 4096. Withnprobe= 16, is also the cost-optimal . - 3Scan per query: codes plus 4096 centroids, about 8002 distance evaluations, or 0.80% of brute force.
- 4PQ with , 8 bits: 96 B per vector, 96 MB of codes (32× smaller). The per-query LUT has entries.
- 5Re-rank the top 200 ADC candidates with exact distances; this needs the raw vectors on disk or in RAM.
1import numpy as np, faiss23d, k = 768, 104xb = np.random.rand(200_000, d).astype("float32") # stand-in for your embeddings5xq = np.random.rand(1_000, d).astype("float32")67flat = faiss.IndexFlatL2(d); flat.add(xb)8_, gt = flat.search(xq, k) # exact top-10910hnsw = faiss.IndexHNSWFlat(d, 32) # M = 3211hnsw.hnsw.efConstruction = 20012hnsw.add(xb)1314quant = faiss.IndexFlatL2(d)15ivfpq = faiss.IndexIVFPQ(quant, d, 2048, 96, 8) # nlist, m, bits per code16ivfpq.train(xb[:100_000]); ivfpq.add(xb)1718def recall(I):19 return np.mean([len(set(a) & set(b)) / k for a, b in zip(I, gt)])2021for ef in (16, 64, 256):22 hnsw.hnsw.efSearch = ef23 print("HNSW ef", ef, recall(hnsw.search(xq, k)[1]))24for nprobe in (1, 8, 32):25 ivfpq.nprobe = nprobe26 print("IVF-PQ nprobe", nprobe, recall(ivfpq.search(xq, k)[1]))Use when
- +HNSW: highest recall per distance computation in memory; incremental inserts with no training step.
- +IVF: cheap inserts, simple sharding by list, very fast on GPUs in large batches.
- +PQ: 16–64× less memory; billions of vectors fit in RAM on one machine.
Avoid when
- −HNSW: vectors plus links must sit in RAM; deletes leave tombstones; builds are slow at high efConstruction.
- −IVF: needs a training sample; recall degrades if the data drifts away from the centroids.
- −PQ: distances are approximate and biased; needs re-ranking with full vectors for high recall.
Check yourself
An IVF index with nlist = 4096 and nprobe = 1 returns recall@10 = 0.62. What is the cheapest first fix?
Check yourself
1024-d float32 vectors are compressed with PQ, m = 64 sub-vectors and 8-bit codes. How many bytes does each code take, and what is the compression ratio?
Remember
- ✓Measure recall@ against brute force on your own queries; compare indexes at equal recall, by QPS or distance computations.
- ✓HNSW: layered graph, , greedy descent then a beam of
efSearchon layer 0; sets memory,efSearchsets recall. - ✓IVF: k-means lists, scan the
nprobeclosest; cost , minimised at . - ✓PQ (Jégou et al. 2011): sub-vectors × 8-bit codes; ADC scores a code with table lookups; re-rank with full vectors.
- ✓In the figure, 99% recall@10 costs 115 distances with HNSW, 225 with IVF and 800 with brute force.