ModelRefs / Approximate Nearest Neighbor (ANN) — AI Glossary
Approximate Nearest Neighbor (ANN) — AI Glossary
An algorithm finding the approximate k closest vectors to a query in high-dimensional space, trading exactness for speed.
Overview
Exact nearest-neighbor search is O(n) in dataset size. ANN algorithms (HNSW, IVF, ScaNN, FAISS) pre-build index structures enabling sub-linear search: HNSW achieves 1–5 ms at 99%+ recall on 100M vectors. Used in every production vector database. Trade-off: index build time, memory overhead, and recall vs. latency.
Reference details
| Topic | rag |
|---|---|
| Also known as | approximate nearest neighbor, vector search |
| Last reviewed | 2026-06-24 |
Related terms
Example: Why the index exists
Exact search compares the query against every stored vector. Over 1,000,000 embeddings of 1,536 dimensions that is 1,000,000 × 1,536 ≈ 1.5 billion multiply-adds for a single query, and it grows linearly with the corpus. An HNSW index instead walks a navigable graph, touching a few thousand candidates — sub-linear in corpus size. You pay for it three times: index build time, extra memory for the graph, and recall below 100%. The vectors the search misses are invisible: nothing errors, the answer is simply built from a slightly worse neighbourhood.
Commonly confused with
In this glossary ANN means approximate nearest neighbour. The same three letters are also used for artificial neural network in older literature — if a paper says “ANN” next to “backpropagation”, it means the network, not the search. Within retrieval, ANN is also not a vector database: it is the index inside one.
When to use it
Reach for it when:
- Corpora large enough that exact-scan latency exceeds your budget — typically beyond a few hundred thousand vectors
- Recall can be measured and tuned against an exact baseline on a held-out query set
- Read-heavy workloads, where the index build amortises over many queries
Reach for something else when:
- Small corpora — exact search over a few thousand vectors is fast, simpler and perfectly recalled
- Correctness-critical lookups where a silently missed neighbour is unacceptable
- Write-heavy data with constant deletions, unless the index supports incremental updates well
Continue your research
Use these connected ModelRefs sections to compare alternatives, inspect implementation paths, and review the evidence and governance boundaries relevant to Approximate Nearest Neighbor (ANN) — AI Glossary.
Frequently asked questions
What is Approximate Nearest Neighbor (ANN)?
An algorithm finding the approximate k closest vectors to a query in high-dimensional space, trading exactness for speed.
Is Approximate Nearest Neighbor (ANN) the same as approximate nearest neighbor?
Yes — approximate nearest neighbor, vector search are common aliases for Approximate Nearest Neighbor (ANN).
What concepts are related to Approximate Nearest Neighbor (ANN)?
Closely related concepts include cosine similarity, ivf, faiss.