What is approximate nearest neighbor (ANN) search?
Also called ANN search, ANN, vector similarity search
Definition
Approximate nearest neighbor (ANN) search is a family of indexing methods that find vectors close to a query vector without comparing it to every stored vector, accepting that some true nearest neighbors are missed.
Approximate nearest neighbor (ANN) search finds the stored vectors closest to a query vector by searching an index instead of comparing the query with every vector. Exact search, often called brute force or flat search, computes the distance to all N vectors, so its cost grows linearly with the corpus. An ANN index visits only a small fraction of the vectors and may miss a few of the true nearest neighbors. A vector database builds ANN indexes so that similarity queries stay fast as a corpus grows into millions of vectors.
How HNSW and IVF work#
HNSW and IVF are the two main families of ANN indexes. HNSW navigates a layered graph that links each vector to its near neighbors. IVF clusters the vectors and scans only the clusters nearest the query. Both are often combined with compression such as product quantization to cut memory use.
HNSW (hierarchical navigable small world). Malkov and Yashunin build a stack of proximity graphs over nested subsets of the data. Each vector's top layer is chosen at random with an exponentially decaying probability, so upper layers are sparse and hold long-range links. A search enters at the top, moves greedily toward the query, and drops down a layer at a time until it reaches the dense bottom graph; the authors describe logarithmic complexity scaling. The main parameters are M, the number of links per vector (more accurate, more memory), and ef_search, the size of the candidate list kept during a query.
IVF (inverted file index). A k-means step partitions the vectors into nlist clusters, and each vector is stored in the list of its nearest centroid. At query time the index compares the query with the centroids and scans only the nprobe closest lists. The search fails to find a neighbor when that neighbor sits in a cluster that was not probed.
The Faiss library paper (Douze et al., 2024) picks an index by speed, memory, and accuracy. It recommends graph indexes when memory is not constrained, typically below about 1 million vectors, and calls IVF the only option for the largest compressed indexes.
| HNSW | IVF | |
|---|---|---|
| Structure | Layered neighbor graph | Clusters with inverted lists |
| Query-time knob | ef_search | nprobe |
| Build | Slower, no training step | Faster, needs k-means training |
| Memory | Higher, stores graph edges | Lower, especially with compression |
Recall vs latency in ANN search#
Every ANN index trades recall for latency through its query-time parameters. Recall here means the fraction of the true nearest neighbors, as found by exact search, that the index returns. Raising ef_search or nprobe examines more candidates, so recall goes up and queries slow down. The useful settings are the fastest ones that meet a recall target.
The pgvector documentation states the trade-off for both families: HNSW has a better speed-recall trade-off than IVFFlat but slower builds and more memory, and raising hnsw.ef_search (default 40) or ivfflat.probes (default 1) improves recall at the cost of speed. Faiss calls the settings that are fastest for a given accuracy Pareto-optimal.
ANN recall is not the same as recall@k in RAG evaluation. ANN recall compares the index with exact search over the same embeddings; retrieval recall@k compares results with human relevance labels. An index can match exact search almost perfectly and still return irrelevant chunks if the embedding model ranks them highest, so measure both.
The vector databases directory compares engines that build these indexes, and What is RAG shows where the index sits in the pipeline.
Related terms
Guides that cover approximate nearest neighbor search
Cite this definition
The AI Engineering Editors. "What is approximate nearest neighbor (ANN) search?" The AI Engineering, updated Nov 06, 2026. https://theaiengineering.com/glossary/approximate-nearest-neighbor
- Title
- What is approximate nearest neighbor (ANN) search?
- Author
- The AI Engineering Editors
- Publisher
- The AI Engineering
- Updated