Approximate nearest neighbour search

Why does a search that deliberately settles for approximate answers beat one that checks every record?

You have fifty million passages, each stored as a vector of a thousand numbers, and a query vector. You want the ten closest. The exact method is embarrassingly simple: compute the distance to all fifty million and keep the best ten. It is correct by construction and needs no index.

And essentially nobody runs it in production. Instead they run algorithms that are permitted to miss — that will sometimes return the eleventh-closest passage and not the third, configured with a dial marked recall deliberately set below one.

That should feel odd. We are choosing to be wrong. So the question is what makes exactness the wrong thing to buy here, and why the obvious remedy — a proper index, the way a database has one — is not available.

Start with the cost of the exact scan. Fifty million vectors of a thousand dimensions is fifty billion multiply-adds per query, and about 200 gigabytes to read if the numbers are 32-bit floats. Modern hardware can do this — in a couple of seconds, using the whole machine, for one query. That is the shape of the problem: not impossible, just hopelessly far from the millisecond budget of an interactive system serving many queries at once.

Now the natural next move: build an index. In one dimension you sort and binary-search. In two or three, a k-d tree splits the plane recursively and you descend to the right region — this is what makes geographic search fast. So extend to a thousand dimensions and we are done.

Except we are not, and the reason is the most important idea here. As dimension rises, space behaves in ways our three-dimensional intuition actively misleads us about. Distances concentrate: the ratio between the farthest and nearest points in a random set drifts toward one, so "nearest" becomes a weak, poorly separated notion. And a partitioning tree fails structurally — with a thousand axes, a query's neighbourhood touches an enormous number of cells, so the search must examine most of the tree to be sure it has missed nothing. Above roughly ten dimensions, exact tree methods degrade to no better than scanning. This is the curse of dimensionality: not a gap in our cleverness, but a property of high-dimensional geometry.

So here is the trade that has to be faced. Exactness in high dimensions costs a full scan. There is no known structure that gives guaranteed nearest neighbours in high dimensions substantially faster than looking at everything.

Which invites the question that reframes the problem: how much is exactness worth? The vectors came from an embedding model that is itself an imperfect approximation of meaning, so the ranking they induce is already noisy — the true third-nearest passage is not reliably more useful than the true eleventh, and a reranker will re-sort the candidates anyway. We are being asked to pay a thousandfold in compute to be exactly right about an ordering that was approximate before the search began.

Put that way the answer is obvious, and the algorithms follow. The dominant one, HNSW, builds a navigable graph: every vector is a node linked to some of its near neighbours, arranged in layers where the top is sparse and long-range and each layer below is denser. A search enters at the top, greedily walks toward the query until it cannot improve, drops a layer, and repeats — a coarse-to-fine descent touching thousands of nodes instead of fifty million. The alternative family, inverted file indexes, clusters the vectors first and searches only the clusters nearest the query, usually with the vectors compressed by product quantisation so that far more fit in memory.

Both have the same dial. Search more of the graph, or more clusters, and recall rises and latency rises with it. You choose a point on that curve; typical production settings sit around 90 to 99 percent recall at the top ten, though the achievable figure depends heavily on the data.

Three refinements.

First, "approximate" names a bounded, measured shortfall. Recall at k is measured directly against a brute-force ground truth on a sample, and it is a tuning parameter you set rather than a mystery you accept. A system whose recall is unmeasured is not doing approximate search; it is guessing.

Second, the costs move around rather than vanishing. HNSW is fast to query and expensive in memory — the graph's links can rival the vectors in size — and awkward to update, since deletions typically mark nodes as removed rather than repairing the graph. Cluster-based indexes are cheaper in memory and easier to rebuild, but need their clustering trained on a sample and degrade if the data drifts away from it. Choosing between them is mostly a memory and update-rate decision, not an accuracy one.

Third, correct the framing that "approximate" is a compromise forced by weak hardware. In high dimensions no exact method beats scanning, so approximation is the only route to sublinear search anyone has found — and since the vectors encode meaning imprecisely to begin with, spending heavily on exactness buys precision the data cannot support.

• How product quantisation keeps a billion vectors in memory, and what it costs in recall.
• Why filtered vector search — neighbours subject to a metadata condition — is so much harder than it sounds.

Every term the collection defines is gathered in the glossary.