Approximate Nearest Neighbor (ANN) Search and HNSW Intuition
~14 min read
Checking every stored vector against a query doesn't scale past a few hundred thousand documents. ANN algorithms like HNSW trade a tiny bit of accuracy for massive speed by building a searchable shortcut structure instead.
Approximate Nearest Neighbor (ANN) Search and HNSW Intuition is a Pro topic
Sign in, then upgrade to Pro or Power to unlock this topic and the full AI Engineering curriculum.
Key points
- •Brute-force (exact) search checks every stored vector against the query — correct, but its cost grows linearly with collection size, unworkable at millions of vectors
- •ANN search trades a small, usually negligible accuracy loss for a massive speedup — finding a near-optimal match almost every time instead of the guaranteed-best one
- •HNSW builds multiple graph layers: a sparse top layer with long-range connections (like highways) narrows the search fast, then lower layers refine locally (like city streets)
- •The book's RAG workflow confirms this is standard practice: vector databases explicitly retrieve 'approximate nearest neighbors,' not exact ones
- •You rarely implement ANN yourself — vector databases expose it as simple add/search calls, with tunable knobs (like HNSW's ef_search) trading speed against accuracy