Approximate nearest neighbor search
Approximate nearest neighbor (ANN) search finds vectors close to a query without checking every stored vector. It gives up a guarantee of the exact best match in exchange for much faster search on large collections.
Also called: ANN, ANN search, approximate k-nearest neighbor
By Divya Sharma · Checked Nov 15, 2026 · How we review
Finding the exact nearest neighbors means comparing the query with every vector you have. That is fine for a small collection and too slow for a very large one. ANN algorithms build an index ahead of time so a search only touches a small part of the data.
Main families
Graph-based indexes such as HNSW link each vector to nearby vectors and walk the graph toward the query. Clustering indexes such as IVF group vectors into buckets and only search the buckets nearest the query. Quantization methods compress vectors so more fit in memory and distance checks are cheaper. Libraries like Faiss combine these.
The trade-off
ANN quality is measured as recall: the share of true nearest neighbors the index actually returns. Settings such as how many graph neighbors to explore or how many clusters to probe trade recall against speed and memory. For most search and retrieval-augmented generation uses, a near neighbor is about as useful as the exact one, so the loss is small.
Where you meet it
You rarely implement ANN yourself. A vector database picks and tunes an index for you, though most expose parameters. If results seem to miss obvious matches, check the index settings before blaming the embedding model. Measure with retrieval metrics on a labelled set.
Related terms
- HNSW
- HNSW (hierarchical navigable small world) is a graph-based index for approximate nearest neighbor search. It links vectors to their neighbors across several layers, so a search can hop quickly toward the closest matches.
- Vector database
- A vector database stores embeddings alongside their source records and finds the stored vectors closest to a query vector, usually with an approximate index so search stays fast across millions of items.
- Vector search
- Vector search finds items by comparing their embeddings to the embedding of a query and returning the closest ones, so results match on meaning rather than on shared keywords.
- Retrieval metrics (recall@k, nDCG, MRR)
- Retrieval metrics score how well a search system returns relevant documents. Recall@k checks how many relevant items appear in the top k, nDCG rewards ranking them high, and MRR measures how early the first correct one appears.
- Embedding dimension
- Embedding dimension is the number of values in each vector an embedding model outputs. More dimensions can hold more detail, but every extra value adds storage, memory and search cost per item.