Why does every production retrieval system use approximate nearest-neighbor search instead of exact search past a certain corpus size?
Exact NN search is O(N) per query and breaks interactive latency past ~1M vectors; ANN trades 1-5% recall for 100-1000x faster queries.
Imagine you have a phone book with a million names and you want to find people whose names sound most like 'Robert'. Reading every single entry to find the closest matches works for a tiny phone book, but with a million names it takes forever. A clever trick is to roughly group the phone book into sound alike bins ahead of time and only search a few promising bins per question. You might miss one or two genuine matches, but you get an answer in milliseconds instead of seconds. That tradeoff, accept a tiny quality loss for a huge speed gain, is exactly what every production search engine does once the data is too big to scan exhaustively.
Detailed answer & concept explanation~4 min readEverything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Everything important, quickly.
5 min: why exact NN is O(N), how ANN families touch a small subset, the recall latency curve, and the 2026 production vendor picture.
Real products, models, and research that use this idea.
- Pinecone serverless uses HNSW for indexes under 50M vectors and shifts to compressed variants above that, never exact search.
- Weaviate exposes HNSW as the default index with optional Product Quantization for cost sensitive deployments.
- Qdrant Cloud ships HNSW with binary and scalar quantization options, used by cost sensitive RAG teams.
- Milvus and Zilliz Cloud implement IVF-PQ and HNSW; LinkedIn and Salesforce run billion vector workloads on it.
- Meta's Faiss library is the BSD-licensed reference for IVF-PQ at billion scale and powers many in house search systems.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow would you measure the recall sacrifice an ANN index is making in production?
QAt what corpus size does brute force exact search stop being viable for sub-50ms latency?
Don't say thisRed flags and common mistakes that signal junior thinking. Click to expand.
Red flags and common mistakes that signal junior thinking. Click to expand.
Claiming ANN is required by the curse of dimensionality. Exact search is mathematically fine in any dimension; the problem is purely about wall clock latency.
The night-before-the-interview bullets. Scan these on the way to the call.
Primary sources. Skim if you want the original framing.
Same topic, related formats. Practice these next.