Approximate Nearest Neighbor (ANN) — AI Glossary

Reference details

Related terms

• Cosine Similarity
• Inverted File Index (IVF)
• FAISS

How it works

1. A graph index connects each vector to a set of near neighbours and adds sparse long-range links in upper layers, so the structure has both local detail and coarse navigation.
2. Search enters at the top layer, moves greedily to whichever neighbour is closer to the query, descends when no neighbour improves, and repeats — so the number of vectors examined grows with the logarithm of the corpus rather than with the corpus.
3. An inverted-file index takes the other approach: cluster the vectors, keep the centroids, and at query time compare against centroids first and then search only the nearest few cells.
4. Both split their parameters into two groups, and the distinction decides how the index can be operated: neighbour count and construction effort are fixed when the index is built, while search breadth and cells probed are chosen per query.
5. That means recall can be traded against latency at request time without rebuilding, but the ceiling on achievable recall was set at build time and raising it means building again.
6. Recall is measured by running an exact scan over a held-out query set and comparing, which is the only way to know what the approximation costs — nothing in the search reports a miss, since a missed neighbour simply never appears.

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.

• Browse models
• Review providers
• Inspect benchmarks
• Explore workflows
• Learn AI concepts
• Read decision guides
• Review trust and methodology
• Start a decision path