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.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
The choice between exact and approximate nearest-neighbor search is not really a choice once the corpus passes a million vectors. Exact search has linear in N per query cost, and that cost crashes into the latency budget of any interactive product long before the corpus reaches what real workloads look like in 2026.
This question is a litmus test for whether a candidate understands the production cost model behind ANN, or treats it as a tutorial buzzword. A good answer names the cost of brute force, the recall sacrifice ANN trades for speed, and at least one ANN family that delivers the tradeoff in real systems.
Why exact search dies at a million vectors
Exact nearest-neighbor search computes the distance from the query to every stored vector. For N vectors in d dimensions, that is O(N * d) floating point operations per query.
Modern x86 cores with AVX-512 do roughly 10 GFLOPS of dot-product work per core. A 100M corpus at 1024 dimensions needs 100B distance ops per query, which is 10 seconds per query per core. Spread across 16 cores it is 600ms. That blows past any interactive SLA: RAG products typically demand p99 under 100ms end to end including the LLM call.
GPUs help, but only by a constant factor. The asymptotic problem is unchanged: brute force scales linearly with corpus size, and at a billion vectors no commodity hardware delivers interactive latency. The only escape is an index that touches a sub-linear number of candidates per query.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
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.
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?
Sample a small ground truth set, compute exact top-K offline, then measure overlap with the ANN top-K. Recall@K is the standard metric.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases 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.
60 second bullets to scan on the way to the call.
Cost of exact NN as a function of corpus size
Recall latency curve and how ANN tunes it
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.