Skip to content
ML to LLMs
Labs / LLM and RAG Lab

Approximate nearest neighbors

Partition vectors into clusters, probe a few, and trade recall against the number of distance computations.

Theory and worked examples: Vector search

Approximate nearest neighbors (IVF)

500 synthetic 2D vectors. Click or drag to move the query. IVF clusters them into cells and scans only the nprobe cells nearest the query.

IVF search02468100246810dimension 1dimension 2
querytrue top-k, foundtrue top-k, missed× centroids (bold = probed)

IVF compared the query with 16 centroids, then scanned 82 of 500 vectors in 2 cells: 98 distance computations instead of 500. It found 9 of the true 10 nearest neighbors (recall@10 = 0.90).

The 1 missed neighbor sits in a cell that was not probed, even though it is close to the query: queries near cell boundaries are where IVF loses recall. Raise nprobe to recover them at extra cost.