Exact vs Approximate Nearest Neighbor
Exact search compares your query with every stored vector (always correct, but slow); approximate search checks only a clever subset — far faster, and almost always just as good.
Explain like I'm new to AI
To find the nearest vectors, the simplest method is brute force: compare the query with every single stored vector. That's exact — guaranteed correct — but with millions of vectors it's far too slow.
Approximate nearest neighbor (ANN) search is the trick that makes vector databases fast: instead of checking everything, it checks a smart subset likely to contain the best matches. Toggle between the two and watch the difference:
Exact checks every point and is always right but slow. ANN checks a smart subset — far faster, and usually finds the same answer. The small chance of missing is called a recall trade-off.
Mental model
Finding a friend in a stadium:
- Exact = check every seat, row by row. You'll definitely find them — eventually.
- Approximate = go to their usual section and look nearby. Almost always works, in a fraction of the time.
How it works
- Exact (brute force): compute similarity to all N vectors, sort, return top-k. Cost grows linearly with N.
- Approximate (ANN): a pre-built index (like HNSW or IVF) guides the search to promising regions, comparing far fewer vectors — often logarithmic-ish in practice.
- The price is recall: the fraction of true nearest neighbors the approximate search actually finds. Good indexes hit 95–99%+ recall while being orders of magnitude faster.
Real-world example
Searching 100 million product embeddings, exact search might compare all 100M per query — impossibly slow for a live app. An ANN index compares maybe a few thousand, returns in milliseconds, and still finds the true best match nearly every time. That trade is almost always worth it.
Technical explanation
The core tension is recall vs. latency vs. memory, tunable per index:
- Raise ANN "effort" parameters (e.g. how many candidates to explore) → higher recall, higher latency.
- Lower them → faster, but more misses.
Measure recall by comparing ANN results against a brute-force ground truth on a sample. Exact search still makes sense for small collections or when 100% correctness is mandatory. Many systems even do exact re-ranking of an ANN shortlist to combine speed and precision.
Common mistakes
Assuming "approximate" means "unreliable." Well-tuned ANN routinely achieves 95–99%+ recall — the occasional miss is a deliberate, measurable trade for enormous speed gains.
- Shipping an ANN index without ever measuring recall on your data.
- Using brute force at scale and blaming the database for slow queries.
When to use it
- Exact: small datasets, or when perfect recall is non-negotiable.
- Approximate: anything at scale needing low latency — the default for production vector search.
When NOT to use it
- Don't use exact search over millions of vectors in a latency-sensitive path.
Alternatives
- Hybrid approach: ANN shortlist + exact re-rank to get both speed and top-end precision.
Quick quiz
Related concepts
- What is Vector Search? — Vector search finds the stored items whose embeddings are closest to a query embedding — the nearest-neighbor operation behind semantic search.
- What is HNSW? — HNSW is a graph-based ANN index that searches from sparse top layers down to dense bottom layers, giving fast, high-recall nearest-neighbor search.
Last reviewed: 2026-09-01 · Written by ByHeart AI · Reviewed by ByHeart AI