Learn · Intermediate

Approximate nearest neighbor search: how a vector database finds a needle in a billion haystacks

Approximate nearest neighbor search - ANN - is the family of algorithms that finds the vectors closest to a query vector without comparing it against every vector you have stored. It is the load-bearing component of every vector database and every retrieval-augmented generation system, and it earns its place by being roughly a hundred times faster than the exhaustive alternative while giving up a small, deliberately tunable amount of accuracy. That trade is not a flaw. It is the entire product, and understanding which dial you are turning explains a surprising share of retrieval bugs.

The problem: exact search does not scale

An embedding model turns each document into a list of numbers - a point in a space of maybe 768 or 1,536 dimensions - positioned so that similar meanings land near each other. Retrieval then means: given the query's point, find the nearest stored points.

Done exactly, this is a brute-force scan. Ten million documents at 768 dimensions is about eight billion multiply-adds per query. That is fine as a batch job and hopeless as a search box someone is waiting on, and it gets linearly worse with every document you add.

So the exact answer is abandoned on purpose. If the true best match ranks second, or is occasionally missed entirely, a downstream language model reading the top ten results almost never notices. Recall becomes a dial you set rather than a guarantee you hold.

Two families that do the work

Inverted file index (IVF) is the intuitive one. Run k-means over your vectors to carve the space into, say, 4,096 clusters, each with a centroid. To search, compare the query against the 4,096 centroids - cheap - then exhaustively scan only the few closest clusters. If you scan 16 of 4,096, you have touched under half a percent of the data.

The analogy is a library organised by subject. You do not read every book; you walk to the shelf your topic lives on. And you inherit that system's failure mode: a book that straddles two subjects sits on one shelf, so a query that lands just on the wrong side of a cluster boundary misses it. Probing more clusters buys that back, at proportional cost. This is the nprobe parameter, and it is the most common thing tuned wrong in production.

HNSW - Hierarchical Navigable Small World, from Yury Malkov and Dmitry Yashunin's 2016 paper - is the one most defaults use today. It builds a graph where each vector links to a few dozen near neighbors, stacked in layers: a sparse top layer with long-range links, denser layers below. A search enters at the top, greedily walks toward the query, drops a layer, and repeats.

Think of finding an address by first taking the interstate to the right city, then arterial roads to the right district, then local streets to the door. The long links at the top cover distance fast; the dense links at the bottom get precision. HNSW generally posts the best speed-versus-recall curve on the public ANN-Benchmarks suite, which is why it is the default in most vector databases. Its costs are real, though: the graph itself can consume more memory than the vectors, and deletions are awkward because removing a node can strand parts of the graph, so most implementations tombstone deleted entries and periodically rebuild.

Compression, and the second trade

At a billion vectors, storing raw floats stops being affordable. Product quantization splits each vector into chunks, replaces each chunk with the nearest entry from a small learned codebook, and stores only the codebook indices - the same discrete-code idea that shows up throughout modern ML, and a close cousin of model quantization. Compression of 16 to 32 times is routine, which is what lets a billion vectors sit in RAM.

The catch is that distances are now computed between approximations, so ranking gets noisier. Systems handle this with a two-stage pattern: retrieve a few hundred candidates using the compressed codes, then re-score just those against the full-precision vectors. Google's ScaNN paper by Ruiqi Guo and colleagues sharpened this by observing that quantization error matters far more for vectors that might actually rank near the top, and weighting the codebook training accordingly - an idea they summarised as an "anisotropic" loss, because error along the query direction is not equivalent to error across it. Meta's FAISS, described in Johnson, Douze and Jegou's 2017 paper, is the library most of this ecosystem is still built on.

What this means when your retrieval misses

When a RAG system fails to surface a document you know is in the index, there are now three distinct suspects, and they need different fixes. The embedding model may not place the query near the document - a modelling problem. The index may be dropping it - a recall problem, fixed by raising nprobe or efSearch and paying latency. Or the query may be genuinely lexical, a product code or a rare name, where BM25 keyword search beats vectors outright, which is why serious systems run both and fuse the results.

The practical discipline is simple and widely skipped: build a small ground-truth set, compute exact nearest neighbors for it once with a brute-force scan, and measure your index against that. Without it, you cannot tell a 70-percent-recall index from a 99-percent one - both return ten plausible-looking results, and only one of them is quietly losing answers.

Ground Truth. (2026, August 5). Approximate nearest neighbor search: how a vector database finds a needle in a billion haystacks. Ground Truth. https://groundtruth.day/learn/approximate-nearest-neighbor-search.html

@misc{groundtruth:approximate-nearest-neighbor-search,
  title  = {Approximate nearest neighbor search: how a vector database finds a needle in a billion haystacks},
  author = {{Ground Truth}},
  year   = {2026},
  month  = {aug},
  url    = {https://groundtruth.day/learn/approximate-nearest-neighbor-search.html}
}

Topics: retrieval · embeddings · vector-database · hnsw · rag · search · infrastructure