Approximate Nearest Neighbor
ANN indexes return almost the exact nearest neighbours much faster by pruning the search space for a controlled, measurable recall loss.
Definition
Approximate nearest neighbour (ANN) search replaces the exhaustive scan of exact k-nearest-neighbour with a data structure that visits only a promising subset of candidates. Graph indexes such as HNSW, partition schemes such as IVF, and hashing methods such as LSH each trade memory, build time, and recall differently. The result is a tunable curve: more effort yields higher recall, and any operating point is only as good as its measured recall on real queries.
Context and scope
Required when embeddings must be searched at millions-of-vectors scale under strict latency budgets, where exact search cannot meet the time or memory cost.
Common misconceptions
- ANN always returns the true nearest neighbour — approximation means some true neighbours are missed by design; recall must be measured, not assumed
- There is a single best index — HNSW, IVF, and hashing win under different memory, freshness, and latency constraints
- Build parameters can be set once and ignored — recall drifts as the corpus, query mix, and filters change
Anti-patterns
- Deploying an approximate index without a labelled recall benchmark
- Tuning only for top-1 accuracy while the product depends on top-k recall
- Using heavy metadata filters that gut the graph connectivity and silently collapse recall
Related concepts
Authoritative source
What it is
Exact nearest-neighbour search compares the query against every stored vector, which is O(n) per query. ANNs cut that cost by assuming close vectors are reachable through shortcuts. HNSW builds a layered navigable graph and greedily descends it; IVF clusters vectors and scans only nearby cells; LSH hashes similar vectors to the same buckets. Each method exposes knobs that move the recall-versus-speed tradeoff.
Why it matters
At millions of vectors, exact search cannot satisfy interactive latency, and memory for full scans is prohibitive. ANNs make semantic retrieval affordable. The price is that the top result is no longer guaranteed: on a given query the true nearest neighbour may be pruned away. That single property governs how the rest of the system must be designed.
How to use it well
Choose the index for the constraints — graph indexes for high recall, partitions for cheaper memory, hashing for fast updates — then benchmark recall@k on a labelled query set, not on intuition. Increase search effort until recall meets the product bar, re-measure after corpus or filter changes, and keep an exact fallback for the small queries where correctness outweighs speed.