Approximate nearest neighbor search (ANN search) is the family of algorithms that find the vectors most similar to a query vector in a large collection without comparing the query to every stored vector, accepting that a small share of the true nearest neighbors may be missed. In artificial intelligence retrieval systems, it is the engine behind semantic search, recommendation and retrieval-augmented generation, where millions or billions of embeddings must be searched in milliseconds.
The defining trade-off is recall versus latency and memory. Exact search is simple and always correct, but its cost grows linearly with the collection. Approximate methods build an index that narrows the search to promising regions, typically reaching recall of 90 to 99 percent at a fraction of the cost.
Why exact search does not scale
Exact nearest neighbor search compares the query with every vector in the collection, so its cost is proportional to the number of vectors multiplied by their dimension. With 100 million embeddings of 768 dimensions, a single query involves tens of billions of multiply-add operations, which is too slow for interactive use at high query volume.
Classic spatial indexes such as k-d trees do not solve the problem in high dimensions. Because of the curse of dimensionality, distances between random points become similar, tree pruning stops working, and such indexes degrade toward brute force. ANN methods instead exploit the fact that real embeddings lie on structured, clustered regions of the space.
Main index families
ANN indexes fall into four main families that differ in how they limit the candidates examined for each query. Graph-based indexes, especially HNSW, dominate in-memory search, while partition and compression methods are preferred when memory is the constraint.
| Index family | How it narrows the search | Strengths and weaknesses |
|---|---|---|
| Graph-based (HNSW) | Greedy walk over a proximity graph | High recall and speed, large memory use |
| Inverted file (IVF) | Searches only the nearest clusters | Fast build, recall depends on probes |
| Product quantization (PQ) | Compares compressed vector codes | Very small memory, lower precision |
| Locality-sensitive hashing | Hashes similar vectors to same buckets | Theoretical guarantees, often less efficient |
| Disk-based graph | Graph on SSD with compressed copy in memory | Billion scale on one machine, higher latency |
Families are often combined. A common configuration is IVF with product quantization, which clusters vectors and stores compressed residuals, followed by a re-scoring step that recomputes exact distances for the best few hundred candidates.
Parameters that control recall and speed
Every ANN index exposes build-time and query-time parameters that move it along the recall-latency curve. Build-time parameters decide index quality and memory; query-time parameters can be tuned per request without rebuilding the index.
| Parameter | Typical range | Effect of a higher value |
|---|---|---|
| HNSW M (links per node) | 8 to 64 | Better recall, more memory |
| HNSW efConstruction | 100 to 500 | Better graph, slower build |
| HNSW efSearch | Tens to several hundred | Higher recall, higher latency |
| IVF number of lists | About the square root of collection size | Finer clusters, more training |
| IVF nprobe | 1 to a few percent of lists | Higher recall, more distance computations |
| PQ code size | 8 to 64 bytes per vector | More precise distances, more memory |
Performance is measured as recall at k, the fraction of true top-k neighbors returned, against queries per second or tail latency at a fixed hardware budget. Results should be measured on the actual embedding distribution, since public benchmark rankings do not always transfer.
Distance metrics and filtering
ANN search depends on a distance or similarity metric that matches how the embeddings were trained. Text embedding models are usually used with cosine similarity or inner product; image and audio features may use Euclidean distance. Normalizing vectors to unit length makes cosine and inner product equivalent and lets a single index type serve both.
| Metric | Meaning | Typical use |
|---|---|---|
| Cosine similarity | Angle between vectors | Text and sentence embeddings |
| Inner product | Projection, sensitive to length | Recommendation scores |
| Euclidean distance | Straight-line distance | Image and sensor features |
Real applications rarely search the whole collection: they restrict results by tenant, date, language or access rights. Metadata filtering interacts badly with naive ANN, because a restrictive filter applied after the search may leave too few results. Systems therefore use filter-aware traversal, pre-filtered partitions, or exact search when the filtered subset is small.
Role in retrieval pipelines
In retrieval-augmented generation and semantic search, ANN search is the first-stage candidate generator. Documents are split by chunking, embedded, and indexed; at query time the query embedding retrieves the top 20 to 200 chunks, which are often merged with BM25 keyword results in hybrid search and reordered by a more precise reranking model.
- Missed neighbors are usually harmless when a reranker reorders a generous candidate set.
- Index drift occurs when many inserts and deletes accumulate; periodic rebuilding restores quality.
- Changing the embedding model requires re-embedding and re-indexing the whole collection.
- Memory planning must include graph links or codes, not only the raw vectors.
A frequent design error is to blame the vector index for poor answers that actually come from weak embeddings or poor chunking. Comparing ANN results with exact search on a sample quickly shows whether the index is the bottleneck.
Put simply
Picture a huge library where every book has a position on a map according to its meaning. Finding books similar to a question means finding the nearest points on that map. Checking every book would take far too long.
Approximate nearest neighbor search uses clever shortcuts, like signposts between neighborhoods, to jump close to the right area quickly. It may occasionally miss one good book. In exchange, it answers in a blink, even with billions of books.
In practice
A customer support platform stores about 40 million text chunks from manuals and past tickets, each embedded as a 1,024-dimensional vector. Exact search takes several seconds per query on its servers, which is too slow for a chat assistant.
The engineers build an HNSW index with M set to 32 and tune efSearch on a sample of real queries. At efSearch of 128, the index returns about 97 percent of the exact top-10 results with latency in the low milliseconds. A reranker then reorders the top 50 candidates. In side-by-side tests, answer quality is indistinguishable from exact search, while the system now handles hundreds of queries per second on the same hardware.