recallA retrieval
field guide

Exact vs Approximate Nearest Neighbour Search

Build this skill

Compare exact and approximate nearest-neighbour search and measure the recall–speed trade-off.

Finding the nearest neighbours

Every vector search asks the same question: given a query vector, which stored vectors are closest to it? Those closest vectors are called the query's nearest neighbours. Finding the K closest (say, the top 5) is called K-nearest-neighbour search, or KNN.

There are two ways to do it. Exact search compares the query with every stored vector and returns the true top K, guaranteed. Approximate nearest neighbour search, or ANN, skips most of the comparisons and returns a top K that is almost always the true one, in a fraction of the time.

Suppose you want to find the five students on campus whose interests are most like yours. The exact method is to interview all 8,000 students. The approximate method is to visit the two or three clubs that match your interests and ask only there. You will meet most of your five in a hundredth of the time, and you might miss one who never joined a club.

Why exact search does not scale

Exact search does one comparison per stored vector, and each comparison multiplies and adds every number in the vector. For a million passages with 1,024 numbers each, one question needs about a billion multiplications. A modern CPU manages that in a fraction of a second. The trouble starts when a thousand students ask questions at the same moment, or the collection grows to 100 million passages.

Simple shortcuts also fail. On a 2-D map you could lay a grid over the points and look only in the squares around the query. Embeddings have hundreds of dimensions, and a grid that cuts each of 1,024 dimensions into just two halves has more cells than there are atoms in the universe. Almost every cell is empty, so "the neighbouring cells" tells you nothing. This is the curse of dimensionality, and ANN methods were designed to work in spite of it.

The approximate idea: search where the answer probably is

ANN methods do some work ahead of time so that each search has less to do. One simple approach groups the vectors into buckets of similar vectors, each with a centre point. At query time, the query is compared with the bucket centres first, and then only the vectors inside the closest few buckets are checked. These are the "clubs" from the example above.

The catch is that a true nearest neighbour may sit just inside a bucket that was not searched, and then it is missed. Searching more buckets lowers that risk and costs more time. Every ANN method has this dial, with recall at one end and speed at the other.

Recall@K puts a number on what was lost: of the true K nearest neighbours (found by exact search), what share did the approximate search return?

Worked example: recall@5 for one query

Exact search says the true top 5 passages are numbers 12, 40, 7, 93 and 61.

The approximate search returns 12, 40, 93, 18 and 61.

Four of the true five (12, 40, 93, 61) were found. Passage 7 was missed, and passage 18 took its place.

Recall@5 = 4 ÷ 5 = 0.8.

Try it below. The plot shows 240 points split into 16 buckets. Search more or fewer buckets and watch both the work done and the recall change.

Exact (all buckets)100% of the work · recall 1.00Search 4 of 16≈ 25% of the work · recall often ≈ 0.9Search 1 of 16≈ 6% of the work · recall can drop a lotShare of comparisons compared with exact search (illustrative)

Approximate search trades a small amount of recall for a large saving in work.

Measuring recall yourself

The program below builds the bucket idea with NumPy. It makes 10,000 fake embeddings, sorts them into 64 buckets, and then compares exact search with a search over 1, 4 and 16 buckets.

python · runs in your browser

Expected output:

text
buckets searched  1: recall@10 = 0.60, work = 3% of exact
buckets searched  4: recall@10 = 0.84, work = 10% of exact
buckets searched 16: recall@10 = 0.99, work = 38% of exact
Part of the code What it does
bucket_of = ... The work done ahead of time: each vector's nearest centre is found and recorded.
exact(q) Measures the distance to all 10,000 vectors and keeps the 10 closest. This is the true answer.
nearest_buckets, ids Compares the query with the 64 centres, keeps the closest probes buckets, and collects the vectors inside them.
len(found & exact(q)) / 10 How many of the true 10 the approximate search also found: recall@10.

Searching more buckets raises recall and costs more work. Real ANN indexes are much smarter than this version, but they make the same trade, controlled by a setting you can tune.

Is "approximate" good enough?

For retrieval-augmented generation, usually yes. Embeddings are themselves an approximation of meaning, so the difference between the true 4th-nearest passage and one that is almost as close is rarely what decides whether an answer is right. Chunking, the embedding model and reranking make far bigger differences. A typical target is a recall@10 of 0.95 or more against exact search, at a speed that keeps every query well under 100 milliseconds.

Exact search is still the better choice for small collections (under roughly 50,000 vectors brute force is fast enough), for searches where a filter leaves only a few thousand candidates, and for evaluation, where you need the true answer to measure an index against.

Follow your curiosity.

↑ ↓ to explore · Enter to open · Escape to close