Approximate vs Exact Nearest Neighbour Search: The Core Trade-Off
Why exact nearest neighbour search does not scale, how approximate search trades a little recall for massive speed, and how to choose.
Published on • November 22, 2026
AI Assistant

Introduction
The honest definition of nearest neighbour search is simple: find the k closest points to a query. Exact search guarantees the true top-k. Approximate search usually returns them, much faster, by giving up a little accuracy. That trade-off is the central decision in every vector database.
Why Exact Search Does Not Scale
The naive exact method is a linear scan: compute the distance from the query to every vector, keep the best k.
- 1 million × 768-dim vectors ≈ 768 million multiply-adds per query
- 1 billion vectors ≈ a minute of pure arithmetic per query, before any I/O
Exact algorithms exist that beat brute force at low dimensions (k-d trees, ball trees), but they degrade badly as dimensionality rises — the curse of dimensionality: distances concentrate, and tree partitions stop pruning effectively. Embeddings live in 128–1536 dimensions, exactly where these structures lose their edge.
So at embedding scale, “exact” effectively means “brute force,” and brute force costs latency and compute that grow linearly with corpus size.
What Approximate Search Does
ANN algorithms — HNSW graphs, IVF partitions, LSH, product-quantised codes — build an index offline so queries only examine a small fraction of the data:
- Graph methods (HNSW): greedily walk a navigable graph toward the query region.
- Partitioning methods (IVF): probe only the nearest cluster centroids.
- Hashing (LSH): only compare items landing in the same bucket.
- Compression (PQ): compare cheap codes instead of full vectors.
The result: query cost grows roughly with log n or a constant probe count instead of n.
The Trade-Off: Recall@k
ANN quality is measured by recall@k — the fraction of the true top-k that the approximate search returned.
| Recall | What it means |
|---|---|
| 1.00 | Exact-equivalent results |
| 0.95–0.99 | Typical production target; usually indistinguishable to users |
| 0.80–0.90 | Faster, but users notice missing items |
| < 0.80 | Risky for RAG — critical context may be dropped |
Almost every ANN index exposes “knobs” (efSearch in HNSW, nprobe in IVF) that slide along the speed–recall curve. Higher recall costs more latency; lower latency costs more misses.
When Exact Still Wins
- Small corpora (< ~100k vectors): a brute-force scan in memory is milliseconds and has zero index-maintenance overhead.
- Ground truth generation: you need exact results to measure ANN recall.
- Low-latency caches: precomputed exact results for hot queries.
- Simplicity: no index build, no tuning, no drift.
How to Choose
- Start with exact/brute force if the corpus fits your latency budget — it is the honest baseline.
- Move to ANN when p95 latency or cost breaks the budget.
- Tune ANN knobs against an exact ground truth until recall@k meets your target (≥0.95 is a common bar).
- Re-benchmark after any data growth or model change.
Conclusion
Exact search gives perfect answers at linear cost; approximate search gives near-perfect answers at sub-linear cost. Neither is universally right — the skill is measuring recall honestly and picking the point on the curve your application actually needs.