# 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.

Source: https://www.mlfoundry.in/learn/approximate-nearest-neighbor-search  
Section: Generative AI › Retrieval-Augmented Generation (RAG)  
Level: advanced · 8 min read · updated 2026-10-21

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

$$
\text{recall@}k=\frac{|\,\text{ANN}_k(q)\cap\text{Exact}_k(q)\,|}{k},\qquad\text{averaged over a held-out query set}
$$

- $\text{ANN}_k(q)$: the $k$ ids the index returns for query $q$
- $\text{Exact}_k(q)$: the true $k$ nearest ids, from a brute-force scan

> Figure: 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=\lfloor-\ln U\cdot m_L\rfloor$ with $U\sim\text{Uniform}(0,1)$ and $m_L=1/\ln M$, so about a $1/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 $M$ of them per layer ($M_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 $k$) 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 $N$. `efSearch` is the query-time knob: larger means more distance computations and higher recall. The paper suggests $M$ 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 $L$ = `nlist` k-means centroids on a sample, assigns every vector to its closest centroid, and stores one list per centroid. A query computes $L$ 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:

$$
\text{cost}(L)\approx L+\text{nprobe}\cdot\frac{N}{L},\qquad \arg\min_L\text{cost}=\sqrt{\text{nprobe}\cdot N}
$$

- $L$: `nlist`, the number of k-means cells
- $N/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 $4\sqrt N$ and $16\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 $d$-dimensional vector into $m$ sub-vectors of $d/m$ dimensions and runs k-means separately in each subspace, usually with $k^*=256$ centroids. A vector is then stored as $m$ one-byte centroid indices. For the query, PQ builds a lookup table of $m\times256$ sub-distances once. Every stored code is then scored with $m$ table lookups and adds, which is asymmetric distance computation (ADC):

$$
\|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)]
$$

- $q_j,\;x_j$: the $j$-th sub-vector of the query and of the stored vector
- $c_j(\cdot)$: the $j$-th codebook; $\text{code}_j(x)$ is the index of the centroid closest to $x_j$
- $\text{LUT}_j$: the query's $2^b$ distances to codebook $j$, 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-\text{centroid}$ inside each IVF list rather than $x$ itself. The residuals are smaller, so the same code size loses less. Because $\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^*=256$ (8-bit) sub-quantizers; 64-bit codes ($m=8$) on SIFT descriptors were a standard setting.
- **HNSW defaults:** $M_0=2M$, $m_L=1/\ln M$; memory for the links is about $M_0\times4$ bytes per vector on layer 0 (128 B at $M=16$), on top of the vectors.
- **FAISS index strings:** `"HNSW32"` (HNSW, $M=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.

> Figure: 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

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)

| 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 $[2,3,1,0]$: 8 bits in place of 32 bytes. ADC gives $\hat d=0.18+0.25+0.16+0.02=0.61$, while the exact $\|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. Raw float32: $10^6\times768\times4$ B $=3.07$ GB.
2. `nlist`: $4\sqrt N=4000$, so take 4096. With `nprobe` = 16, $\sqrt{16\cdot10^6}=4000$ is also the cost-optimal $L$.
3. Scan per query: $16\times10^6/4096\approx3906$ codes plus 4096 centroids, about 8002 distance evaluations, or 0.80% of brute force.
4. PQ with $m=96$, 8 bits: 96 B per vector, 96 MB of codes (32× smaller). The per-query LUT has $96\times256=24{,}576$ entries.
5. Re-rank the top 200 ADC candidates with exact distances; this needs the raw vectors on disk or in RAM.

```python
import numpy as np, faiss

d, k = 768, 10
xb = np.random.rand(200_000, d).astype("float32")   # stand-in for your embeddings
xq = np.random.rand(1_000, d).astype("float32")

flat = faiss.IndexFlatL2(d); flat.add(xb)
_, gt = flat.search(xq, k)                            # exact top-10

hnsw = faiss.IndexHNSWFlat(d, 32)                     # M = 32
hnsw.hnsw.efConstruction = 200
hnsw.add(xb)

quant = faiss.IndexFlatL2(d)
ivfpq = faiss.IndexIVFPQ(quant, d, 2048, 96, 8)       # nlist, m, bits per code
ivfpq.train(xb[:100_000]); ivfpq.add(xb)

def recall(I):
    return np.mean([len(set(a) & set(b)) / k for a, b in zip(I, gt)])

for ef in (16, 64, 256):
    hnsw.hnsw.efSearch = ef
    print("HNSW ef", ef, recall(hnsw.search(xq, k)[1]))
for nprobe in (1, 8, 32):
    ivfpq.nprobe = nprobe
    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)

> **Recall on someone else's benchmark is not your recall:** Recall depends on the data's intrinsic dimension, the metric, $k$, and filters. A setting that gives 0.99 on SIFT can give 0.9 on your embeddings. Restrictive metadata filters can disconnect an HNSW graph (see **Vector databases**). Keep a few hundred real queries with brute-force ground truth and re-measure recall whenever you change the index, the embedding model or the data size.

> **Normalise once, then every metric is L2:** For unit vectors, $\|a-b\|^2=2-2\cos(a,b)$, so cosine, inner product and L2 give the same ranking. Normalising at ingest and at query time lets you use any index type. Without normalisation, maximum inner product search is a different problem; L2-based IVF and PQ then need care or a transformation.

**Strengths**

- 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.

**Limitations**

- 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.

**Question:** An IVF index with nlist = 4096 and nprobe = 1 returns recall@10 = 0.62. What is the cheapest first fix?

- A. Retrain with nlist = 65,536
- B. Raise nprobe (e.g. to 16) and re-measure
- C. Switch the metric from L2 to cosine
- D. Reduce k to 1

**Answer:** B. Raise nprobe (e.g. to 16) and re-measure — With nprobe = 1 every neighbour in an adjacent cell is lost. Probing more lists is a query-time change with a predictable cost of about nprobe × N / nlist extra codes. A larger nlist makes cells smaller and misses more at the same nprobe. Changing $k$ only hides the problem.

**Question:** 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?

- A. 64 B, 64×
- B. 128 B, 32×
- C. 512 B, 8×
- D. 8 B, 512×

**Answer:** A. 64 B, 64× — $m=64$ codes of 8 bits each is 64 bytes. The raw vector is $1024\times4=4096$ bytes, and $4096/64=64$.

**Key points**

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

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
