Finding the closest vector among ten million: the arithmetic of approximate search

The honest version: compare with everything

Given a query embedding and a store of n embeddings of dimension d, the exact way to find the nearest is to compute all n similarities. That is n × d multiply-adds per query, and the store occupies n × d × 4 bytes in float32.

n = 100,000, d = 768:   1.5 × 10^8 FLOPs per query, 300 MB
n = 10,000,000:         1.5 × 10^10 FLOPs per query, 30 GB

At a hundred thousand, one query is about a millisecond on a laptop and the store fits in RAM. Brute force is the right answer, and building an index for it is wasted effort that also costs recall. The course machine-learning-foundations builds a working search at this scale with NumPy; nothing more is needed until the numbers change.

At ten million, one query is around 150 milliseconds on a CPU, tolerable for one user and hopeless for a thousand, and the store is 30 GB, which is beyond a laptop and beyond most graphics cards. Something has to give, and there are exactly four things that can.

Shrink the vectors

Drop dimensions. Module 2's singular values, or a model trained to put its important dimensions first, let you keep 256 of 768 with a modest loss in ranking quality: threefold less memory and compute. Then shrink each number. Float32 to int8 is fourfold at almost no loss. Product quantisation goes further: split the vector into sub-vectors, replace each with the index of its nearest entry in a small learned codebook, and store perhaps 64 bytes per vector instead of 3,072:

10^7 vectors × 64 bytes = 640 MB

The 30 GB store now fits in a phone. The similarity computed from codes is approximate, which is the first place recall is spent.

Search fewer of them

Partition the store into clusters, module 4's k-means will do, with about √n centres: 3,000 or so for ten million. A query is compared first with the 3,000 centres, then only with the vectors in the nearest few clusters. Probe 32 clusters and you examine about one per cent of the store:

3,000 centre comparisons + 1% of 10^7 = about 130,000 comparisons, against 10,000,000

Roughly a hundredfold faster. The cost is that the true nearest neighbour sometimes sits in a cluster you did not probe; at one per cent probed, expect to miss it a few times in a hundred, and to find it nineteen times in twenty. Probing more clusters buys recall with time, and the curve between them is the thing you tune.

Walk a graph instead

Build a graph in which each vector links to a few dozen near neighbours, with sparser long-range links layered on top. A query starts at an entry point and greedily hops to whichever neighbour is closest to it, descending the layers, until no neighbour is closer. This is HNSW, and a query typically touches a few hundred to a thousand vectors:

~1,000 comparisons per query, against 10,000,000: ten-thousandfold

The price is memory for the links, around 100 to 300 bytes per vector on top of the vector itself, and a build time that is itself a nearest-neighbour problem, hours for ten million on a laptop. Recall is typically above 95 per cent and adjustable with a search-width parameter. Most hosted vector databases run this.

What recall costs you

Every approximate method returns the true nearest neighbour some fraction of the time, and the fraction is measured, not guaranteed. A retrieval system at 95 per cent recall silently gives the wrong first passage to one query in twenty. Whether that matters depends on what sits downstream: a recommender barely notices; a system answering questions from a single retrieved document notices every time. Measure recall on your own queries against brute force on a sample, because the number in the library's documentation was measured on a different dataset.

The rule of thumb

under 10^5 vectors:   brute force, NumPy, no index
10^5 to 10^6:         brute force on a GPU or with int8; index only if latency demands
above 10^6:           IVF or HNSW, with quantisation once memory bites
above 10^8:           quantise first, then partition, and expect to tune for weeks

Every one of those lines is a consequence of n × d and n × d × 4. Do the two multiplications for your own n before choosing a tool.

Free tools, and one more number

faiss on a CPU implements everything above and is free; hnswlib is a small, fast HNSW; NumPy is brute force. All run on a laptop. The one further number to know is that the query embedding must be produced by the same model, with the same normalisation, as the stored ones; module 1's cosine lesson explained why, and a store of unit vectors searched with an un-normalised query returns confidently wrong answers at any scale, with a perfect index.