Approximate nearest neighbour (ANN)
Approximate nearest neighbour search: find vectors close to a query without comparing against all of them, trading a little recall for 100–1000× speed.
Exact nearest-neighbour search compares your query vector with every stored vector, which is too slow at millions of items. ANN algorithms build an index — a graph (HNSW), clusters (IVF (inverted file index)) or compressed codes (Product quantization (PQ)) — that lets the search visit only a small part of the data. The answer is approximate: it usually finds 95–99% of the true nearest neighbours, measured as ANN recall (efSearch, nprobe).
Finding the nearest café by walking toward the busy part of town and checking the streets there, instead of visiting every café in the city.
Blaming the embedding model for misses the ANN index caused. Always compute exact-search recall on a sample: if exact top-10 contains the answer but ANN top-10 doesn't, the fix is ef_search/nprobe, not a new model.
Three families dominate. Graph (HNSW, DiskANN/Vamana): greedy walk on a proximity graph; best recall–latency trade-off in RAM; memory ≈ vectors + ~2·M·4 bytes of links per vector. Inverted file (IVF): k-means into nlist cells, probe nprobe of them; cheaper to build, easy to shard, recall depends on nprobe/nlist. Quantization (PQ, SQ8, binary): compress vectors so more fit in RAM/cache, then rescore top candidates with full precision. Real systems combine them: FAISS IVF65536,PQ64 for 1B vectors, HNSW32 for 10M, Qdrant HNSW + int8 scalar quantization with rescoring. Brute force on a GPU (FAISS Flat) is exact and competitive up to ~1–5M vectors; below ~100k vectors, skip the index entirely.
≤ 100k vectors: exact search. 100k–20M: HNSW (pgvector m=16/ef_construction=64, Qdrant m=16/ef_construct=100, FAISS HNSW32) with ef_search 64–128. > 50M or RAM-bound: FAISS OPQ64,IVF65536,PQ64 or DiskANN-style on-SSD graphs with full-precision rescoring of the top 100–200.
Code search embeddings, 10M × 768-d. Exact search: 10M dot products × 768 = 7.7 GFLOP per query → ~150 ms on 16 CPU cores. HNSW (m=16, ef_search=100): ~1,500 distance computations, ~1.5 ms, recall@10 ≈ 0.97. The 3% miss rate means 1 in ~33 relevant chunks is never seen — acceptable when a reranker and fusion follow, not acceptable for de-duplication.
Show you can pick by constraint: "Under 10M vectors in RAM I default to HNSW; over 100M or RAM-bound I use IVF-PQ with full-precision rescoring; under 100k I don't index at all." Expect: how do you measure the 'approximate' part? Compute exact top-k on 1,000 sampled queries offline and report recall@k at your chosen ef/nprobe.
Numbers worth knowing
- HNSW query latency
- 1–3 ms10M × 768-d in RAM, ef_search 100, recall@10 ≈ 0.95–0.98
- Exact CPU scan
- ~150 ms10M × 768-d, 16 cores, float32
- IVF-PQ memory
- ~70–100 B/vectorPQ64 codes + 8-B ids, vs 3,072 B raw at 768-d float32
How to decide
| When | Do this |
|---|---|
| < 100k vectors | Brute force; an index adds build cost and recall loss for no gain. |
| Fits in RAM, latency-critical, frequent upserts | HNSW. |
| 100M+ vectors or RAM costs dominate | IVF (inverted file index) + Product quantization (PQ) with rescoring, or an on-disk graph. |
Cost maths
RAM is the bill. 10M × 768-d: HNSW float32 ≈ 33 GB → a 64 GB node (assume ~$0.43/hr ≈ $310/month per replica, illustrative Oct 2026). With int8 SQ ≈ 10 GB → a 16 GB node (~$80/month). At 1B vectors, HNSW float32 ≈ 3.3 TB of RAM (~50 such nodes, ~$15k/month per replica) vs IVF-PQ64 ≈ 90 GB (2 nodes) — the reason billion-scale systems quantize.
Operating it
- Index RAM > 70% of node memory — quantize or shard
- Recall@10 at your latency SLO < 0.9 on the exact-search sample — raise ef/nprobe or change index type
- Index build time > maintenance window — move to IVF or segment-based incremental builds
- ANN recall@k vs exact on a daily 1,000-query sample — alert below 0.93
- Search p99 latency — alert above 20 ms for the vector stage
- Index memory / node RAM — alert above 75%
When it goes wrong
A legal-research RAG system answered 'no precedent found' for queries a paralegal could find by browsing.
Weekly job comparing exact vs ANN top-20 on 1,000 sampled queries showed recall@20 of 0.71.
An IVF index was built with nlist=16384 on a 5M-vector sample but served 40M vectors after growth; nprobe stayed at 8 (0.05% of cells).
Rebuilt with nlist=65536, raised nprobe to 64 and added a recall gate to the index-build pipeline (fail the deploy below 0.95 recall@20).
Related terms
Where it shows up
Sources
- ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms — Aumüller, Bernhardsson & Faithfull, 2018paper
- The Faiss library — Douze et al., 2024paper
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — Malkov & Yashunin, 2016paper
Check yourself
Three questions. Every option is explained once you answer.