Retrieval & Context

Approximate Nearest Neighbor (ANN)

By Aditya Kumar Jha, Engineer

Approximate nearest neighbor (ANN) search finds vectors close to a query vector quickly by trading a small amount of accuracy for large speed gains, instead of scanning every vector exactly. It is the indexing layer that makes vector search at scale practical.

What approximate nearest neighbor search is

Nearest neighbor search answers a simple question: given a query vector, which stored vectors are closest to it under a chosen distance, such as Euclidean (L2) distance or cosine similarity? Exact k-nearest-neighbor (kNN) search guarantees the true closest k results, but the only way to be certain is to compare the query against every stored vector. That brute-force scan costs O(N) distance computations per query for N vectors, and each computation is itself O(d) for d-dimensional vectors. At a few thousand vectors this is fine; at tens of millions it becomes the dominant cost in a retrieval system.

Approximate nearest neighbor (ANN) search relaxes the exactness guarantee. Instead of promising the true top k, an ANN index returns results that are correct most of the time, and it does so by examining only a small fraction of the dataset. The accuracy it gives up is measured as recall, and the speed it gains is measured as throughput or latency. Because the loss in accuracy is usually small and tunable, ANN is the default mechanism behind production vector search, semantic search, and retrieval-augmented generation.

An ANN index is a precomputed data structure built over the vectors. Building it costs time and memory up front, after which each query traverses only part of the structure. The central design question for every ANN method is the same: how to organize vectors so that a short, guided walk reaches the true neighbors with high probability, rather than a full linear scan.

  • Exact kNN guarantees correctness but costs O(N) distance computations per query, which does not scale to large corpora.
  • ANN trades a small, controllable accuracy loss for order-of-magnitude faster queries.
  • The accuracy of an ANN method is reported as recall against the exact result set.
  • Every ANN index is built once and then reused across many queries.

Why exact kNN does not scale

The difficulty is not only the linear N term; it is the combination of large N, high dimension d, and the geometry of high-dimensional space. In high dimensions, distances between points concentrate: the gap between the nearest and the farthest point shrinks in relative terms, which weakens the partitioning tricks (such as KD-trees) that work well in two or three dimensions. This effect, often called the curse of dimensionality, is why classical exact spatial indexes degrade toward brute force as dimension grows into the hundreds typical of modern embeddings.

A single brute-force query over N vectors of dimension d costs on the order of N times d floating-point operations. For one million 768-dimensional embeddings that is roughly 768 million multiply-add operations per query, repeated for every incoming request. Memory bandwidth, not just compute, becomes the bottleneck because the full vector set must be streamed from memory for each query. Caching and SIMD help, but they do not change the linear growth.

ANN methods sidestep the linear scan by restricting comparisons to a candidate set that is far smaller than N. Graph-based methods walk a navigable graph toward the query. Partition-based methods (inverted files) probe only a few clusters. Hashing methods bucket similar vectors together. Each approach narrows the search space before any exact distances are computed, which is where the speedup comes from.

  • High-dimensional geometry makes distances concentrate, eroding classical tree-based partitioning.
  • Brute-force search is bound by memory bandwidth as much as by raw arithmetic.
  • ANN reduces work by building a candidate set much smaller than the full corpus.
  • The three dominant strategies are graph traversal, cluster (inverted-file) probing, and hashing.

The recall-versus-latency tradeoff

Recall@k is the standard accuracy metric for ANN. It measures, for a given query, the fraction of the true k nearest neighbors that the approximate search actually returned. A recall@10 of 0.95 means that on average the index recovers 9.5 of the 10 true neighbors. Recall is computed against an exact ground truth, so it directly quantifies how much accuracy the approximation costs.

Every ANN index exposes parameters that move along a curve trading recall against speed. Spending more effort per query, for example exploring a larger candidate list in a graph or probing more clusters in an inverted file, raises recall but lowers throughput. The honest way to compare two methods is therefore not a single number but the whole recall-versus-throughput curve. The ANN-Benchmarks project standardizes exactly this comparison, plotting recall against queries per second (QPS) across many algorithms and datasets so that methods are judged at matched accuracy rather than at cherry-picked operating points.

Because the tradeoff is tunable at query time in most index families, a deployment can dial recall up for high-stakes retrieval or dial it down for latency-sensitive paths, without rebuilding the index. The right operating point depends on how the downstream system tolerates a missing neighbor, which for retrieval-augmented generation often depends on whether a reranking stage can recover from imperfect candidate sets.

recall@k = |A ∩ G| / k
Recall@k for one query: A is the set of k results the ANN index returns, G is the set of true k nearest neighbors, and |A ∩ G| counts how many of the true neighbors were recovered. Averaging over a query set gives the reported recall.
  • Recall@k is the fraction of the true top-k neighbors that the approximate search returns.
  • Recall is measured against an exact ground-truth result set.
  • Methods should be compared on the full recall-versus-QPS curve, not a single point.
  • ANN-Benchmarks is the standard open framework for plotting recall against queries per second.

The main index families: HNSW, IVF, IVF-PQ, LSH

HNSW (Hierarchical Navigable Small World) is a graph-based index introduced by Yu. A. Malkov and D. A. Yashunin. It links each vector to a set of near neighbors and stacks these proximity graphs in layers, with sparse long-range links in upper layers and dense local links at the bottom. A search starts at the top layer, greedily hops toward the query, and descends layer by layer, which the authors show yields logarithmic-scale search complexity. HNSW typically reaches very high recall at low latency and is the default index in many vector databases, at the cost of higher memory use and slower builds.

IVF (inverted file) is a partition-based index. A clustering step (usually k-means) splits the space into cells, each with a centroid. At query time the index finds the few centroids nearest the query and searches only the vectors assigned to those cells. The nprobe parameter, the number of cells probed, directly controls the recall-versus-speed tradeoff: probing one cell is fast but may miss neighbors near a boundary, while probing many cells approaches exact search. IVF builds faster and uses less memory than HNSW but generally needs more probing to match its recall.

IVF-PQ combines the inverted file with product quantization to compress the vectors themselves, which is what enables billion-scale search in bounded memory. Locality-sensitive hashing (LSH) takes a different route: it uses hash functions designed so that nearby vectors collide in the same bucket with high probability, turning search into a lookup over a few buckets. LSH gives formal probabilistic guarantees but in practice is often outperformed on the recall-versus-QPS curve by graph and IVF methods on dense embeddings, as the ANN-Benchmarks comparisons show.

  • HNSW is a layered proximity graph with logarithmic-scale search; high recall and low latency, higher memory.
  • IVF partitions the space into cells and probes only the nearest few, tuned by the nprobe parameter.
  • IVF-PQ adds product quantization on top of IVF to compress vectors for billion-scale, memory-bounded search.
  • LSH buckets similar vectors via locality-sensitive hash functions, with formal collision-probability guarantees.

Product quantization (PQ) is a lossy compression scheme that makes ANN viable when the raw vectors will not fit in memory. A d-dimensional vector is split into m contiguous subvectors, and each subvector is quantized independently to the nearest entry in a small learned codebook (typically 256 centroids, so each code is one byte). A 128-dimensional float32 vector that occupied 512 bytes can be stored as an m-byte PQ code, often 8 to 16 bytes, a compression of one to two orders of magnitude. That compression is why a billion vectors that would never fit in memory raw can fit once quantized, and exact search over them stops being a memory problem.

The decisive property is that approximate distances can be computed directly in the compressed domain. Using asymmetric distance computation, the query stays uncompressed while the database vectors stay as PQ codes, and the distance from the query to each subvector codebook is precomputed into small lookup tables. Estimating the distance to a stored vector then reduces to m table lookups and additions, which is fast and cache-friendly. This is the mechanism behind FAISS, the open-source similarity-search library from FAIR (now part of Meta), whose IVF-PQ indexes combine cell pruning with PQ-compressed scoring.

Compression trades memory and speed against precision: more subquantizers and larger codebooks raise accuracy but increase code size and lookup cost. In practice PQ is paired with an inverted file (IVF-PQ) so that quantization handles memory while the inverted file handles pruning, and an optional exact re-scoring pass over the top candidates recovers recall lost to quantization. Quantization for ANN is the same underlying idea as model quantization: represent values with fewer bits while preserving the distances or outputs that matter.

python
import numpy as np
import faiss

d = 128                      # vector dimension
nb = 100_000                 # database size
rng = np.random.default_rng(0)
xb = rng.random((nb, d), dtype="float32")
xq = rng.random((5, d), dtype="float32")

# IVF-PQ index: 1024 cells, PQ with 16 subquantizers, 8 bits each
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ(quantizer, d, 1024, 16, 8)

index.train(xb)             # learn cell centroids and PQ codebooks
index.add(xb)               # add compressed vectors
index.nprobe = 16           # cells probed per query (recall vs speed)

distances, ids = index.search(xq, k=10)   # 10 approximate neighbors per query
print(ids.shape, distances.shape)         # (5, 10) (5, 10)
Building and querying a FAISS IVF-PQ index. The index must be trained before adding vectors; nprobe tunes the recall-versus-speed tradeoff at query time. Verified against the FAISS Python API.
  • PQ splits each vector into subvectors and replaces each with a one-byte codebook index, cutting storage by one to two orders of magnitude.
  • Asymmetric distance computation scores compressed vectors using small precomputed lookup tables.
  • FAISS implements IVF-PQ, pairing cell pruning with compressed-domain scoring for billion-scale search.
  • A final exact re-scoring of top candidates recovers recall lost to quantization.

Where ANN fits in retrieval systems

ANN is the engine inside a vector database. The database adds storage, filtering by metadata, updates and deletes, persistence, and horizontal scaling on top of an ANN index, but the core retrieval step that finds candidate vectors is an ANN query. Choosing an index family and its parameters is therefore one of the main levers a vector database exposes, whether directly or behind defaults.

In a typical semantic search or retrieval-augmented generation pipeline, ANN runs as the first-stage retriever. It produces a candidate set of perhaps the top 50 to 200 neighbors quickly, and a slower, more accurate reranking model then reorders a short list of those candidates. Because reranking only sees what the first stage retrieved, first-stage recall sets a ceiling on end-to-end quality: a relevant document that ANN never surfaces cannot be recovered later. This is why recall at the retrieval stage is tuned deliberately rather than minimized for speed alone.

The operating point also interacts with embedding quality. Better embeddings place true neighbors closer together, which lets an ANN index hit a target recall while doing less work. Conversely, no index can recover a neighbor the embedding space placed far from the query. ANN, embeddings, and reranking are thus tuned together rather than in isolation.

  • A vector database wraps an ANN index with metadata filtering, updates, persistence, and scaling.
  • ANN usually serves as the first-stage retriever, feeding a candidate set to a reranker.
  • First-stage recall caps end-to-end retrieval quality, since reranking cannot recover unretrieved items.
  • Embedding quality and ANN parameters are tuned jointly, because both shape achievable recall.

Key takeaways

  • Approximate nearest neighbor (ANN) search trades a small, tunable accuracy loss for order-of-magnitude faster vector queries than exact kNN.
  • Exact kNN costs O(N) distance computations per query and degrades in high dimensions, which is why large-scale vector search relies on ANN.
  • Quality is measured as recall@k against an exact ground truth, and methods are compared on the full recall-versus-queries-per-second curve.
  • HNSW is a layered proximity graph with logarithmic-scale search; IVF partitions the space into cells and probes the nearest few via nprobe.
  • Product quantization compresses vectors into compact codes and scores them in the compressed domain, enabling billion-scale search in bounded memory, as in FAISS IVF-PQ.
  • ANN is the first-stage retriever in vector databases and RAG pipelines, so its recall sets the ceiling on what reranking can later recover.

Frequently asked questions

FAISS uses -1 as a sentinel in the returned ids array, meaning no neighbor was found for that result slot, and sets the matching distance to a large value. It shows up in three cases: the index is empty (ntotal is 0); the index holds fewer than k vectors, so the trailing slots of the k-wide result are padded with -1; or, for an IVF index, nprobe is too small and the probed cells held fewer than k candidates. Filter these out before using the results, for example ids = [i for i in I[0] if i != -1], and raise nprobe if an IVF index returns too few hits.
Exact nearest neighbor search guarantees the true closest vectors by comparing the query against every stored vector, which costs O(N) per query. Approximate (ANN) search examines only a small candidate set, returning results that are correct most of the time. The accuracy given up is measured as recall, and in exchange ANN is often orders of magnitude faster on large datasets.
The standard metric is recall@k: the fraction of a query's true k nearest neighbors that the approximate search actually returns, averaged over a query set. It is computed against an exact ground truth. A recall@10 of 0.95 means the index recovers, on average, 9.5 of the true 10 neighbors.
HNSW (a layered proximity graph) generally gives the highest recall at the lowest latency and is a strong default, but it builds more slowly and uses more memory. IVF (an inverted file that probes a few clusters) builds faster and uses less memory, and pairs with product quantization as IVF-PQ when vectors must be compressed for very large corpora. The right choice depends on corpus size, memory budget, and latency targets.
Product quantization (PQ) compresses each vector by splitting it into subvectors and replacing each with a one-byte index into a small learned codebook, cutting storage by one to two orders of magnitude. Crucially, distances can be estimated directly on the compressed codes using precomputed lookup tables. This is what lets indexes like FAISS IVF-PQ search billions of vectors within a bounded memory budget.
Exact kNN must compute the distance from the query to every stored vector, so cost grows linearly with the number of vectors and is bound by memory bandwidth as well as compute. High-dimensional embeddings also defeat classical tree-based spatial indexes because distances concentrate, an effect known as the curse of dimensionality. ANN methods avoid the full scan by restricting comparisons to a much smaller candidate set.
ANN-Benchmarks is an open-source framework by Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull for evaluating in-memory approximate nearest neighbor algorithms on standard datasets. It plots recall against queries per second so that algorithms are compared at matched accuracy rather than at single cherry-picked operating points. It is the common reference for judging ANN methods.

Put the idea into practice

MemX is an AI memory agent built on these ideas: store anything, skip the folders, and find it again by asking in plain English.

Try MemX Free