Approximate nearest neighbor search (HNSW, IVF, PQ)

ANN indexes trade a little recall for orders-of-magnitude fewer distance computations: HNSW walks a layered graph, IVF scans the nprobe closest k-means lists, and PQ compresses vectors to m-byte codes scored by table lookups.

8 min read1012 wordsadvanced0 viewsupdated 2026-10-21

Definition

Approximate nearest neighbor (ANN) search returns kk vectors that are probably among the kk 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 kk-NN costs NN distance computations of dd 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@kk; cost is distance computations, latency or queries per second (QPS) at a target recall:

recall@k=∣ ANNk(q)∩Exactk(q) ∣k,averaged over a held-out query set\text{recall@}k=\frac{|\,\text{ANN}_k(q)\cap\text{Exact}_k(q)\,|}{k},\qquad\text{averaged over a held-out query set}
ANNk(q)\text{ANN}_k(q)
the kk ids the index returns for query qq
Exactk(q)\text{Exact}_k(q)
the true kk nearest ids, from a brute-force scan
HNSW: layered graphlayer 2layer 1layer 0entrygreedy (ef = 1) on upper layers,beam of efSearch on layer 0P(level ≥ l) = M^−lIVF: k-means inverted listsnlist 6, nprobe 2: scan 2 listsnprobe = 1 misses the true NN ●(it sits in the 2nd-closest cell)PQ: 8-d x → 4 codessub-vector → nearest centroid(0.9, 0.1)c₂ = (1, 0)(0.4, 0.8)c₃ = (0.5, 1)(−0.3, 0.2)c₁ = (−0.5, 0)(0.6, −0.5)c₀ = (0.5, −0.5)code [2,3,1,0]: 4 × 2 bitsADC: d̂ = Σⱼ LUTⱼ[codeⱼ]0.18+0.25+0.16+0.02 = 0.61exact ‖q − x‖² = 0.31LUTⱼ[c] = ‖qⱼ − cⱼ,c‖², builtonce per query: m × 2^b entriesbytes per 768-d vector (100M vectors: 307.2 GB as float32, 9.6 GB as PQ96)float32 vector3072 BPQ, m = 96 × 8 bits96 B (32× smaller)HNSW links, M = 16≈128 B on layer 0 (2M × 4 B ids)
fig.The three building blocks. HNSW: each node gets a random top level with P(level ≥ l) = M^−l; search descends greedily through the sparse upper layers, then runs a beam of width efSearch on layer 0. IVF: k-means splits the space into nlist cells; the query scans only the nprobe closest, and with nprobe = 1 it would miss a true neighbour just across a cell boundary. PQ: an 8-d vector becomes four 2-bit codes, and the query's distance is a sum of four table lookups (0.61, against an exact 0.31). Bottom: bytes per 768-d vector.

HNSW: a navigable graph

HNSW builds a proximity graph incrementally. Each new point draws a level l=⌊−ln⁡U⋅mL⌋l=\lfloor-\ln U\cdot m_L\rfloor with U∼Uniform(0,1)U\sim\text{Uniform}(0,1) and mL=1/ln⁡Mm_L=1/\ln M, so about a 1/M1/M 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 MM of them per layer (M0=2MM_0=2M 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 kk) 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 NN. efSearch is the query-time knob: larger means more distance computations and higher recall. The paper suggests MM 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 LL = nlist k-means centroids on a sample, assigns every vector to its closest centroid, and stores one list per centroid. A query computes LL 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:

cost(L)≈L+nprobe⋅NL,arg⁡min⁡Lcost=nprobe⋅N\text{cost}(L)\approx L+\text{nprobe}\cdot\frac{N}{L},\qquad \arg\min_L\text{cost}=\sqrt{\text{nprobe}\cdot N}
LL
nlist, the number of k-means cells
N/LN/L
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 4N4\sqrt N and 16N16\sqrt N. 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 dd-dimensional vector into mm sub-vectors of d/md/m dimensions and runs k-means separately in each subspace, usually with k∗=256k^*=256 centroids. A vector is then stored as mm one-byte centroid indices. For the query, PQ builds a lookup table of m×256m\times256 sub-distances once. Every stored code is then scored with mm table lookups and adds, which is asymmetric distance computation (ADC):

∥q−x∥2≈d^(q,x)=∑j=1m∥qj−cj(codej(x))∥2=∑j=1mLUTj[codej(x)]\|q-x\|^2\approx\hat d(q,x)=\sum_{j=1}^{m}\big\|q_j-c_j\big(\text{code}_j(x)\big)\big\|^2=\sum_{j=1}^{m}\text{LUT}_j[\text{code}_j(x)]
qj,  xjq_j,\;x_j
the jj-th sub-vector of the query and of the stored vector
cj(⋅)c_j(\cdot)
the jj-th codebook; codej(x)\text{code}_j(x) is the index of the centroid closest to xjx_j
LUTj\text{LUT}_j
the query's 2b2^b distances to codebook jj, 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 x−centroidx-\text{centroid} inside each IVF list rather than xx itself. The residuals are smaller, so the same code size loses less. Because d^\hat d 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 k∗=256k^*=256 (8-bit) sub-quantizers; 64-bit codes (m=8m=8) on SIFT descriptors were a standard setting.
HNSW defaults
M0=2MM_0=2M, mL=1/ln⁡Mm_L=1/\ln M; memory for the links is about M0×4M_0\times4 bytes per vector on layer 0 (128 B at M=16M=16), on top of the vectors.
FAISS index strings
"HNSW32" (HNSW, M=32M=32, full vectors), "IVF4096,Flat" (IVF, uncompressed lists), "IVF4096,PQ64" (IVF with 64-byte PQ codes). nprobe defaults 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.
IVF: 32 k-means lists, scan the nprobe = 2 closest · query 1/40, k = 10first 2 of 16 coordinates · ■ query · ● true top-10 found · ○ missed● points in the probed lists (+ = list centroid)mean recall@10 over 40 queries0.50.7510200400600800distance computations per querybrute forceHNSW (ef 10–160)IVF (nprobe 1–32)this queryrecall@10 5/10 · cost 61mean over 40 queriesrecall@10 80.25% · cost 98= 12.2% of the 800 brute-force distancescost = 32 centroids + points scanned
index
fig.A real IVF (32 k-means lists) and a real HNSW (M = 8, M₀ = 16, efConstruction = 40) over 800 clustered 16-d points, 40 queries, k = 10; cost counts every distance computed. Default IVF, nprobe = 2: mean recall@10 is 80.25% at 98 distances (12.2% of brute force); query 1 finds only 5/10. IVF reaches 99.00% at nprobe = 8 (225 distances) and costs 832 > 800 at nprobe = 32. HNSW gets 93.00% at efSearch = 10 (96 distances), 99.00% at 15 (115) and 100% from 30 (156). The HNSW levels hold 800, 108, 15 and 1 nodes.

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

jx_jNearest centroid (code)LUT_j for q (4 entries)LUT_j[code]
1(0.9, 0.1)(1, 0) → 20.98, 2.98, 0.18, 0.080.18
2(0.4, 0.8)(0.5, 1) → 30.50, 0.25, 1.00, 0.250.25
3(−0.3, 0.2)(−0.5, 0) → 10.26, 0.16, 0.61, 1.010.16
4(0.6, −0.5)(0.5, −0.5) → 00.02, 0.72, 1.37, 0.820.02
PQ with m = 4 sub-vectors of 2 dims and 4 centroids each (2-bit codes), q = (0.7, 0.3, 0.5, 0.5, −0.1, 0, 0.4, −0.6) (computed in numpy)

The code is [2,3,1,0][2,3,1,0]: 8 bits in place of 32 bytes. ADC gives d^=0.18+0.25+0.16+0.02=0.61\hat d=0.18+0.25+0.16+0.02=0.61, while the exact ∥q−x∥2=0.31\|q-x\|^2=0.31, 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

  1. 1Raw float32: 106×768×410^6\times768\times4 B =3.07=3.07 GB.
  2. 2nlist: 4N=40004\sqrt N=4000, so take 4096. With nprobe = 16, 16⋅106=4000\sqrt{16\cdot10^6}=4000 is also the cost-optimal LL.
  3. 3Scan per query: 16×106/4096≈390616\times10^6/4096\approx3906 codes plus 4096 centroids, about 8002 distance evaluations, or 0.80% of brute force.
  4. 4PQ with m=96m=96, 8 bits: 96 B per vector, 96 MB of codes (32× smaller). The per-query LUT has 96×256=24,57696\times256=24{,}576 entries.
  5. 5Re-rank the top 200 ADC candidates with exact distances; this needs the raw vectors on disk or in RAM.
python
1import numpy as np, faiss
2
3d, k = 768, 10
4xb = np.random.rand(200_000, d).astype("float32") # stand-in for your embeddings
5xq = np.random.rand(1_000, d).astype("float32")
6
7flat = faiss.IndexFlatL2(d); flat.add(xb)
8_, gt = flat.search(xq, k) # exact top-10
9
10hnsw = faiss.IndexHNSWFlat(d, 32) # M = 32
11hnsw.hnsw.efConstruction = 200
12hnsw.add(xb)
13
14quant = faiss.IndexFlatL2(d)
15ivfpq = faiss.IndexIVFPQ(quant, d, 2048, 96, 8) # nlist, m, bits per code
16ivfpq.train(xb[:100_000]); ivfpq.add(xb)
17
18def recall(I):
19 return np.mean([len(set(a) & set(b)) / k for a, b in zip(I, gt)])
20
21for ef in (16, 64, 256):
22 hnsw.hnsw.efSearch = ef
23 print("HNSW ef", ef, recall(hnsw.search(xq, k)[1]))
24for nprobe in (1, 8, 32):
25 ivfpq.nprobe = nprobe
26 print("IVF-PQ nprobe", nprobe, recall(ivfpq.search(xq, k)[1]))
Build HNSW and IVF-PQ indexes with FAISS and measure recall@10 against brute force (faiss-cpu API; not run here because faiss is not installed in this environment)

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@kk against brute force on your own queries; compare indexes at equal recall, by QPS or distance computations.
  • ✓HNSW: layered graph, P(level≥l)=M−lP(\text{level}\ge l)=M^{-l}, greedy descent then a beam of efSearch on layer 0; MM sets memory, efSearch sets recall.
  • ✓IVF: LL k-means lists, scan the nprobe closest; cost ≈L+nprobe⋅N/L\approx L+\text{nprobe}\cdot N/L, minimised at L=nprobe NL=\sqrt{\text{nprobe}\,N}.
  • ✓PQ (Jégou et al. 2011): mm sub-vectors × 8-bit codes; ADC scores a code with mm 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.
← back to Generative AI roadmap