Why vector search is approximate on purpose

Exact nearest-neighbor search exists, works, and is correct. At scale, the AI-era retrieval stack quietly walks away from it. The reason is more interesting than 'it's faster.'

The picture version

Six pictures for a reader who has never heard of a vector database. The prose below fills in the seams the pictures skip.

Why it exists

You’re building the thing everyone builds now: a search box over your company’s help center, five million chunks of documentation, where typing “how do I cancel my subscription” should surface the right article even though it never uses the word “cancel.” That’s the running example for the rest of this post. You reach for a vector database — Pinecone, Qdrant, Weaviate, pgvector, FAISS — and in the docs there’s a phrase that should make you stop and squint: approximate nearest neighbor. Approximate. The system whose entire job is “find me the most similar vector to this query” is openly telling you it might not return the actual most similar vector.

You probably read that as a compromise the vendor is apologizing for — “we’d give you the exact answer if only we could afford it.” It’s closer to the opposite. These systems do support exact search — it’s pgvector’s default when you build no index at all, and it’s FAISS’s IndexFlat, Qdrant’s exact mode, Weaviate’s flat index. They’re just not what most production deployments switch on once the corpus gets big. Approximate becomes the default, on purpose, and the reason isn’t only cost.

That should still feel strange. We don’t accept it from databases elsewhere. A SQL WHERE id = 42 that returned “probably row 42, but maybe row 39, sorry” would be a bug. Why is the AI-era retrieval stack happy to ship the equivalent?

There are two answers, and both are worth carrying around. The boring one is that exact NN search degrades sharply in high dimensions: the data structures that make exact search fast in low-dimensional space lose most of their pruning power, and you end up not far from a linear scan over the whole corpus. The interesting one is empirical: in the workloads where approximate nearest neighbour (ANN) indexes dominate, the embeddings themselves are noisy enough that the index’s near-misses are roughly the same size as the embedding model’s own ranking jitter. So an “exact” answer to a fuzzy question is no better than an approximate answer to it. That’s a regime claim, not a law — true for text/RAG, less true for tasks with cleaner signals — and it’s the one worth understanding.

Why it matters now

If you’re building anything on RAG or semantic search, ANN is the layer your latency, recall, and bill all sit on top of. Treating it as a black box leads to predictable disappointments:

• You won’t understand the dial. Every ANN index exposes a speed-vs-accuracy knob (HNSW’s efSearch, IVF’s nprobe, etc.). Without a model of why it’s approximate, you tune it by guessing.
• You’ll over-spec. Teams routinely demand “100% recall” from vector search and then pay a steep multiple in latency or hardware for an improvement the downstream LLM can’t even see.
• You’ll misdiagnose retrieval failures. When RAG returns a bad passage, the cause is usually the embedding being a bad fit for the query, or the chunking strategy — not the ANN index missing a true neighbor. Blaming the index is a common dead end.
• You’ll pick the wrong index for the wrong reason. HNSW vs. IVF vs. ScaNN vs. flat search isn’t a flavor war; each is a different point on a curve, and which point you want depends on data size, update frequency, and how much recall you actually need.

The mental model “vector DB = approximate on purpose, and that’s fine because embeddings are fuzzy” answers most of those.

The short answer

ANN = sub-linear-time index + accept a small recall loss + big speedup, justified because the embedding distance is itself fuzzy

Picture to keep: the index is a ruler marked in millimetres being used to measure something whose edges are blurred by a centimetre. Grinding finer marks into the ruler doesn’t tell you anything new about where the edge is.

Exact nearest-neighbor in high dimensions tends to collapse toward linear scan — the indexes that prune well in 2D or 3D lose most of their power. ANN indexes (graph-based like HNSW, partition-based like IVF, hash-based like LSH) skip most of the data using clever structure, at the cost of occasionally missing the true top-k. In text/RAG-style workloads the cost is usually acceptable because the embedding model’s own ranking is already noisy at the margins.

How it works

Start from the naive plan and let it break twice.

Naive attempt: for each query, compute the distance to all five million help-center chunks and keep the closest ten. This is correct by construction, and for a small corpus it’s the right answer — stop here.

1. Why it breaks: exact NN at scale gets ugly fast

There’s a classical result loosely called the curse of dimensionality. The compact statement: under many distributions, as dimensionality grows the distances between points concentrate, and partitioning structures that pruned aggressively in low dimensions lose most of their leverage. A k-d tree splits space at each node, but in high-dimensional spaces a query’s “nearby” region touches almost every branch, so the tree ends up walking most of the data anyway. Beyer et al. (1999), “When Is ‘Nearest Neighbor’ Meaningful?”, is the standard reference for the concentration effect itself, under stated conditions — the consequence for indexes is the usual practical reading of it, not something the paper proves outright. So the honest version is often approaches brute force, not always collapses to it.

That leaves you with mostly-honest options for big high-dimensional corpora:

• Linear scan with a fast inner-product kernel. Correct, embarrassingly parallel, and expensive: every query touches every vector. Possible on a big GPU for moderate corpora; quickly stops being the per-query cost target a search product wants once you scale out.
• Distributed linear scan. Same per-query cost, spread across machines. Buys throughput, not latency.

Neither comfortably hits the low-millisecond, large-corpus, single-node bar that production semantic search is usually held to. So the field went looking for something that isn’t exact — which sounds like a straightforward accuracy-for-speed trade, until you look at what “accuracy” means here.

2. The fix is cheaper than it looks: approximation is often effectively free in embedding space

This is the part that’s worth internalizing, with the caveat that it’s a regime claim, not a theorem. It’s true for the workloads that drove ANN to dominance (text-style RAG, semantic search over noisy human-written corpora). It’s less true for tasks with cleaner signals, which I’ll come back to.

An embedding model maps text (or images, or whatever) into a vector. The training objective shapes which directions are close, but it does not nail down a precise distance: two equally-good paraphrases of a sentence land in nearby-but-not-identical points, and the model’s “rank” of the top results for a query is genuinely noisy near the boundary. Re-train the model with a different seed, or even use a different pooling strategy, and the ordering of result #4 vs. result #7 will jiggle. Result #1 vs. result #500 won’t. In help-center terms: the model is confident that “Cancelling your plan” beats “Keyboard shortcuts” for your query, and genuinely unsure whether “Cancelling your plan” or “Managing your billing cycle” should be #1.

Now layer an ANN index on top. A well-tuned HNSW index typically returns the true top-k most of the time, and when it misses, it usually returns vectors that are almost as close as the true neighbor — its errors look like “swap result #5 with result #6,” not “completely miss the topic.” That error is roughly the same kind, and the same scale, as the embedding’s own ranking noise.

Stack them and you get the argument: in this regime, the ANN-vs-exact gap lives below the embedding-vs-truth gap. So spending compute to close the ANN gap doesn’t move end-to-end retrieval quality much. You’re sharpening a measurement whose underlying signal was already blurry.

This is why “high recall” benchmarks for ANN are easy to over-index on. The last few percentage points of recall often cost a sizable multiple in latency, and in an end-to-end RAG eval the difference is frequently inside the noise of the LLM’s own answer variability. (There is no canonical citation for this — it’s the folklore claim that “embedding error dominates ANN error” in noisy text workloads. The shape is well-supported by ANN benchmarks like ann-benchmarks.com, but how universally it holds across embedding models and corpora is a claim that varies by setup.)

How the indexes actually skip work

Three families dominate, and each cheats in a different direction. Keep the same query in mind — the vector for “how do I cancel my subscription” arriving at five million chunks:

• Graph-based (HNSW). Build a multi-layer graph where each vector links to a small number of others. To search, greedy-walk the graph toward the query, descending layers — your query lands somewhere generic, then walks “warmer” hop by hop until it’s among the billing articles. Skips work because most of the five million vectors are never visited at all. The dial: how many candidates to expand at each step (efSearch). Higher = closer to exact, slower.
• Partition-based (IVF). Cluster all vectors into, say, 4096 cells via k-means. At query time, find the cells closest to the query and search only those — you score the “billing and account” cells and never look at the ones full of API reference. Skips work by ignoring most cells. The dial: nprobe, how many cells to inspect. Higher = closer to exact, slower. Often combined with PQ (Jégou, Douze & Schmid, 2011) to also shrink memory.
• Hash-based (LSH). Pick hash functions where similar vectors collide more often than dissimilar ones. Look up the query’s bucket, score what’s there. The theoretical pitch is probabilistic guarantees on recall as a function of distance — clean math, and it was the dominant ANN family for years. On dense-vector benchmarks, HNSW and IVF-family methods now usually beat classic LSH on the recall/latency frontier (the ann-benchmarks curves are the easiest place to see this), but LSH still shows up where worst-case behaviour matters more than average-case throughput.

All three give you sub-linear query time and a knob that says “trade more compute for fewer mistakes.” The memory bill varies by family — graph indexes like HNSW typically end up larger than the raw vectors; IVF combined with PQ is often smaller, sometimes by an order of magnitude. (The FAISS index guide gives per-index bytes-per-vector numbers if you want to size this for your own corpus rather than trust the shape of the claim.)

Where the argument breaks down

The “approximation is free” story is contingent. A few honest exceptions:

• Small corpora. When the corpus is small enough, exact search is fast enough that you should just do it. pgvector with no index, FAISS IndexFlat, or even NumPy will give you exact answers quickly. ANN’s fixed costs (build time, memory, parameter tuning) aren’t worth it until the dataset earns them.
• Safety-critical lookups. If you’re using vector search for dedup, copyright matching, or anything where a missed true neighbor is a correctness bug rather than a quality wobble, exact search (or ANN as candidate generation followed by exact rerank) is the standard pattern.
• Tiny k and tight thresholds. If you only care whether the closest match is below distance t, and t is small, ANN’s near-miss errors can flip the answer. Exact rerank of the top candidates is the standard fix.
• The “approximation is free” claim is empirical. It depends on the embedding model’s noise floor being similar in magnitude to the ANN index’s miss rate. For embeddings trained on much cleaner signals (face recognition, fingerprint matching), the noise floor is much lower and ANN errors do show up in end-to-end quality. The text/RAG case is the friendly one.

You started with ANN = sub-linear index + accept a small recall loss. What did this post add? — + a noise floor you didn't put there, and it’s the half that changes what you should optimize. Vector databases are approximate not because the field gave up on correctness, but because correctness is being measured against a ranking that was already approximate before the index ever saw it. The index is rounded to the precision of the question it’s being asked.

Which answers the squint you started with: the docs aren’t apologizing. For your help-center search, “the exact 10th-nearest chunk” isn’t a fact the system is failing to deliver — it’s a number the embedding model was never confident about in the first place. In most text/RAG setups, what you should worry about first is whether the embeddings and the chunking are any good, because that’s the error term that usually dominates. Move to a domain with a cleaner signal and that ordering can flip.

Check yourself

Before you go — your RAG answers are bad, so you raise HNSW’s efSearch until measured recall@10 goes from 92% to 99.5%. Answer quality doesn’t budge. What does that tell you?

And a trade-off: same 5-million-chunk corpus, but now the job is detecting whether an uploaded document is a near-duplicate of one already in the system. Same vectors, same index. Does the “approximation is free” argument still hold?

Famous related terms

• HNSW — HNSW = multi-layer graph + greedy nearest-neighbor walk — a widely deployed graph-based ANN index. Common across pgvector, Qdrant, Weaviate, and FAISS.
• IVF — IVF = k-means clusters + search only the closest cells — the partition-based alternative; often paired with PQ for memory savings.
• PQ (Product Quantization) — PQ = chop vector into chunks + quantize each chunk — substantially shrinks memory at a small accuracy cost. Why FAISS can hold very large corpora in RAM.
• LSH — LSH = hash function where similar things collide — the original ANN family; clean probabilistic guarantees, less common in production for dense embeddings today.
• Recall@k — recall@k = average fraction of the true top-k neighbours the index actually returned — the metric ANN benchmarks live or die by, averaged over queries. The number you tune the speed-vs-accuracy dial against.
• Cosine similarity — cosine similarity = dot product / (‖a‖·‖b‖) — the metric most text-embedding ANN setups are configured to optimize; dot product and L2 also common.
• Embeddings — embedding = learned vector representation of a discrete thing — the vectors the index is full of, and the source of the noise that makes approximation acceptable in the regime where it does.
• RAG — RAG = retriever + generator + prompt assembly — the most common reason this whole stack exists.

Going deeper

• Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv 1603.09320) — the primary source, and the answer to “what is the index actually doing when it skips 99% of my corpus?” The algorithm is shorter than you’d expect.
• The FAISS wiki — the explainer to read when you need to decide which index to build, since it lays out the families and their memory/recall/build-time costs side by side.
• ann-benchmarks.com — the rabbit hole, for the reader who wants to see the trade-off rather than be told about it: the recall-vs-queries-per-second curves make the shape of “the last few points of recall are the expensive ones” immediately obvious.