Retrieval Engineering
kNN & approximate nearest neighbors
Lesson 3 of 5
What you'll learn
- Implement exact top-k nearest-neighbor search
- Understand why brute force doesn't scale
- Grasp the recall/speed trade-off behind ANN and HNSW
Once everything is a vector, retrieval is nearest-neighbor search: given a query vector, find the k closest corpus vectors. The exact answer is brute-force kNN — score the query against every vector and take the top k. It's correct by construction and trivial to implement.
// brute force: O(N * d) work per query — fine for thousands, painful for millions
The problem is the N. At ten million vectors, scoring all of them per query is too slow and too expensive for interactive use. You need to avoid looking at most of the corpus.
Approximate nearest neighbors
ANN indexes give up the guarantee of finding the exact top k in exchange for visiting only a tiny fraction of the vectors. The dominant approach is HNSW (Hierarchical Navigable Small World): a layered graph where each vector links to its neighbors. Search starts at a sparse top layer, greedily hops toward the query, then descends into denser layers to refine. You touch a few hundred nodes instead of millions.
The dial you're turning
ANN exposes a recall vs. speed knob (in HNSW, parameters like efSearch). Higher efSearch explores more of the graph: higher recall, slower queries. Lower means faster but more likely to miss a true neighbor. Production tuning is picking the cheapest setting that still hits your recall target — measured, not guessed.
Approximate means approximate
ANN can silently drop a relevant chunk that exact search would have found. Always measure recall against a brute-force baseline on a sample before trusting an index in production. A fast retriever that misses the right document is worse than a slow one that doesn't.
Run it. It does an exact brute-force top-k search over a small set of vectors using cosine similarity, exactly as an ANN index approximates.
What does an ANN index like HNSW trade away to gain its speed over brute-force kNN?
Saved on this device. Sign in to sync your progress everywhere.