Approximate nearest neighbor search
Approximate nearest neighbor search finds stored vectors that are very close to a query quickly, by checking only a promising part of the collection and accepting a few misses.
Nearest neighbor search finds the stored items that are closest to a query. Vector search is a core job of vector databases.
The approximate version gives up perfect accuracy. It accepts a few mistakes, and in return it runs faster.
Exact search is the starting point. It checks every stored vector. Faiss, a search library, offers an index for it. pgvector, a vector add-on for the Postgres database, does exact search by default. Exact search gives perfect recall. Recall means the share of the true nearest vectors that a search actually returns. So the approximate version trades a little recall for speed.
Here are two kinds of approximate index. An IVFFlat index sorts vectors into groups, then checks only the groups nearest the query. HNSW is a different kind, called a graph index. For the same recall, HNSW is faster than IVFFlat. But it takes longer to build and uses more memory.
Think of a music app that finds songs like one you already love. It does not need the perfect top ten. Ten very close songs, shown instantly, are good enough.
You can always turn the dial back. In pgvector, if you set probes (how many groups to check) to the number of lists (groups), the search becomes exact again.
ANN-Benchmarks is a project with tools to benchmark many approximate nearest neighbor libraries. Its maintainers say the project is no longer being actively updated.
Checking every stored vector gets too slow as a collection grows.
Follow one query through a cluster index.
- 1 · partitionBefore searching, the index splits the stored vectors into cells, for example with k-means clustering.
- 2 · assignEach stored vector is filed in the list of the cell whose centre is closest to it.
- 3 · probeAt query time the index picks only the few cells nearest the query, a number called nprobe.
- 4 · compareThe query is compared with every vector in those cells, and the closest ones are returned.
Opening more cells finds more true neighbours but takes longer.
| Who | What they ask | What it works with |
|---|---|---|
| App developer on Postgres | “Can my similarity query stop scanning the whole embeddings table?” | An ivfflat or hnsw index in pgvector |
| Search engineer | “How close are my approximate results to an exact search?” | Results compared against an exact search |
| Library evaluator | “Which ANN library gives the best speed for the recall I need?” | Shared benchmark datasets |
- Only a fraction of the collection is compared with each query, so searches get much faster.
- One setting at query time, such as nprobe or ef_search, trades accuracy against speed.
- In HNSW, search work grows only logarithmically with the collection size, so doubling the data adds little work.
- Ready-made tools such as Faiss, ScaNN and pgvector offer vector similarity search.
- Answers can differ from an exact search, because some true neighbours are missed.
- Cluster indexes such as IVFFlat need a training step on existing data before use.
- Filters are applied after the index scan in pgvector, so a filtered query can return fewer results.
- It does not make embeddings better. It only finds vectors close to the query faster.
Sources used
This explainer is written in original language. The links below support its factual claims.
- paperEfficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, Malkov and Yashunin, arXiv · read 28 Sept 2026
- docsFaiss indexes, Meta AI Research (Faiss wiki) · read 28 Sept 2026
- paperThe Faiss library, Douze et al., arXiv · read 28 Sept 2026
- repopgvector: open-source vector similarity search for Postgres, pgvector · read 28 Sept 2026
- repoScaNN, Google Research · read 28 Sept 2026
- repoANN-Benchmarks: benchmarking nearest neighbors, ANN-Benchmarks project · read 28 Sept 2026