When you store dense embeddings in a database, the basic question is: given a query vector, find the K most similar stored vectors.
The simplest method is **exact nearest-neighbor search**: loop over every stored vector, compute the distance to the query, sort, return the top K. This is correct but its cost is linear in the corpus size N. For ten thousand vectors that is fast. For ten million it is slow. For a billion it is impossible inside a user facing latency budget.
Approximate nearest-neighbor search (ANN) builds a clever index ahead of time, a graph in HNSW or a partition map in IVF, that lets each query touch only a small subset of vectors. You accept that occasionally the algorithm misses a true neighbor and substitutes a slightly worse one. In practice that recall hit is 1 to 5 percent.
The payoff is enormous. Queries that took 500ms exhaustively now finish in under 1ms. That is why every managed vector DB (Pinecone, Weaviate, Qdrant, Milvus) defaults to an ANN index.
**Exact nearest-neighbor search is O(N) per query.** For ten thousand vectors that is fine; for ten million it pushes past interactive latency budgets; for a billion it is infeasible at any reasonable cost.
ANN indexes (HNSW, IVF, IVF-PQ, DiskANN) trade a small recall hit, typically 1 to 5 percent, for two to three orders of magnitude in latency. The mechanism varies by family: HNSW navigates a proximity graph, IVF probes a few k-means partitions, PQ shrinks each vector to a few bytes for cheap distance arithmetic. All of them touch a small constant ish number of candidates per query rather than every vector in the corpus.
The other three options in the question are distractors that show up in 2026 interviews and are wrong:
- The curse of dimensionality is real (distances concentrate at high d), but it does not forbid exact search; exact search remains mathematically well defined.
- L2 normalization changes which metric you use but not whether brute force is feasible.
- Faiss is BSD-licensed and used widely; the licensing claim is fiction.
The right answer is the boring one: production systems run ANN because exact search does not survive contact with a million row corpus and a 50ms latency SLO.
Quick reference
TL;DR
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.
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.
Corpus under 10k vectors with no latency pressure Brute force is exact, has zero build time, and finishes in microseconds; an ANN index adds engineering complexity without measurable benefit.
Strict legal or compliance recall above 0.999 with no tolerance for misses ANN sacrifices a small fraction of recall by design; if every miss is a regulated event, exact search or hybrid sparse+dense is the safer choice.
Vectors regenerated end to end every few seconds ANN index builds (especially HNSW) are expensive and assume relatively stable corpora; very volatile data fits brute force or batch reindex patterns better.
Quick scan · 2–4 min
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-world examples
Real products, models, and research that use this idea.
1Pinecone serverless uses HNSW for indexes under 50M vectors and shifts to compressed variants above that, never exact search.
2Weaviate exposes HNSW as the default index with optional Product Quantization for cost sensitive deployments.
3Qdrant Cloud ships HNSW with binary and scalar quantization options, used by cost sensitive RAG teams.
4Milvus and Zilliz Cloud implement IVF-PQ and HNSW; LinkedIn and Salesforce run billion vector workloads on it.
5Meta's Faiss library is the BSD-licensed reference for IVF-PQ at billion scale and powers many in house search systems.
Interviewer follow-ups
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?
Sign in or go Pro to see the approach for this follow-up.
QAt what corpus size does brute force exact search stop being viable for sub-50ms latency?
Sign in or go Pro to see the approach for this follow-up.
QWhy does HNSW achieve much higher recall than IVF at the same latency budget?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
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.