Approximate Nearest Neighbor Search

ANN algorithms find vectors close to a query far faster than exhaustive comparison by accepting a small, tunable loss in recall.

Trading exactness for speed

Exact nearest-neighbor search must, in the worst case, examine every stored vector, giving a cost proportional to the number of vectors times their dimension. Approximate methods restructure the data so a query examines only a small, cleverly chosen subset. The result may miss a true neighbor occasionally, but with the right parameters it returns the correct top results the large majority of the time while running orders of magnitude faster.

Measuring quality: recall@k

ANN quality is measured by recall@k: of the k true nearest neighbors, what fraction did the approximate search return? A recall@10 of 0.98 means the index found, on average, 9.8 of the true top ten. Every ANN system exposes parameters that trade recall against latency, and the right operating point is chosen empirically against a labeled query set.

HNSW graphs

Hierarchical Navigable Small World indexes build a layered graph where each vector links to a few near neighbors. A search starts at an entry point in the top, sparse layer and greedily walks toward the query, descending layers as it homes in. The parameter that controls candidate breadth during search (often called efSearch) directly trades recall for latency; larger values explore more of the graph.

IVF and quantization

Inverted-file (IVF) indexes cluster vectors and record which cluster each belongs to. A query is compared only against vectors in the few clusters nearest its centroid. Product quantization compresses each vector into a compact code, so memory shrinks and distance computations become table lookups. IVF and PQ are frequently combined: coarse cluster pruning plus compressed residuals.

Choosing an index

A practical workflow keeps a small exact (flat) index as a correctness oracle: sample queries, run both, and measure recall of the approximate index against exact truth before trusting it in production. See vector databases and embedding storage.