---
title: "What is approximate nearest neighbor (ANN) search?"
description: "Approximate nearest neighbor (ANN) search finds the vectors closest to a query without scanning them all. How HNSW and IVF work and the recall-speed trade-off."
type: "glossary-term"
canonical_url: "https://theaiengineering.com/glossary/approximate-nearest-neighbor"
markdown_url: "https://theaiengineering.com/glossary/approximate-nearest-neighbor.md"
topic: "RAG and vector search"
author: "The AI Engineering Editors"
publisher: "The AI Engineering"
updated: "2026-11-06"
keywords: ["Approximate nearest neighbor search","ANN search","ANN","vector similarity search"]
citation: "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"
---

# What is approximate nearest neighbor (ANN) search?

Also called ANN search, ANN, vector similarity search.

> **Definition of Approximate nearest neighbor search:** 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](https://theaiengineering.com/glossary/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](https://theaiengineering.com/glossary/quantization) to cut memory use.

**HNSW (hierarchical navigable small world).** [Malkov and Yashunin](https://arxiv.org/abs/1603.09320) 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](https://arxiv.org/abs/2401.08281) (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](https://github.com/pgvector/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](https://theaiengineering.com/glossary/recall-at-k) in RAG evaluation. ANN recall compares the index with exact search over the same [embeddings](https://theaiengineering.com/glossary/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](https://theaiengineering.com/platforms/vector-databases) compares engines that build these indexes, and [What is RAG](https://theaiengineering.com/articles/what-is-rag) shows where the index sits in the pipeline.

## Related terms

- [Vector database](https://theaiengineering.com/glossary/vector-database): A vector database is a database built to store embedding vectors and quickly return the vectors most similar to a query vector, usually with approximate nearest neighbor indexes such as HNSW.
- [Embeddings](https://theaiengineering.com/glossary/embeddings): Embeddings are fixed-length vectors of numbers that represent data such as text or images so that items with similar meaning sit close together, which lets software compare meaning with arithmetic.
- [Cosine similarity](https://theaiengineering.com/glossary/cosine-similarity): Cosine similarity is a measure of how closely two vectors point in the same direction, computed as their dot product divided by the product of their lengths, with values from -1 to 1.
- [Recall@k](https://theaiengineering.com/glossary/recall-at-k): Recall@k is a retrieval metric that measures the fraction of a query's relevant documents that appear in the top k results, averaged over a set of test queries.
- [Hybrid search](https://theaiengineering.com/glossary/hybrid-search): Hybrid search is a retrieval method that runs keyword search, typically BM25, and vector similarity search on the same query and merges the two ranked lists into one result set.
- [Quantization](https://theaiengineering.com/glossary/quantization): Quantization is a model compression technique that represents a neural network's weights, and sometimes its activations or KV cache, with fewer bits, such as 8-bit or 4-bit integers instead of 16-bit floats.

## Guides that cover approximate nearest neighbor search

- [What is retrieval-augmented generation (RAG)? How RAG works](https://theaiengineering.com/articles/what-is-rag): Retrieval-augmented generation (RAG) grounds LLM answers in your documents. Learn the RAG pipeline, hybrid search, agentic RAG, evaluation, and failure modes.
- [AI engineer roadmap: skills, projects, and resources by stage](https://theaiengineering.com/articles/ai-engineer-roadmap): A practical AI engineer roadmap in seven stages, each with the skills to learn, a project to ship, and resources worth the time, from Python to production.
- [Semantic caching for LLMs: how it works and when it pays off](https://theaiengineering.com/articles/semantic-caching): Semantic caching returns a stored LLM response for prompts with similar meaning. Learn how a semantic cache works, how to tune it, and what never to cache.

Part of the [RAG and vector search](https://theaiengineering.com/topics/rag) topic hub.

## 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: 2026-11-06
- URL: https://theaiengineering.com/glossary/approximate-nearest-neighbor
- Markdown: https://theaiengineering.com/glossary/approximate-nearest-neighbor.md
