The recall-latency curve — Nearest Neighbour

Every technique on this site — search breadth, connectivity, nprobe, quantization, oversampling — is a way of moving along the same curve. Recall on one axis, latency on the other, memory as a third dimension you’re also paying in.

Seeing the curve makes the parameters stop feeling arbitrary. It also tells you when to stop tuning.

What recall means here

Recall@k is the fraction of the true nearest neighbours that appear in your returned top-k.

recall@k = |returned_top_k ∩ true_top_k| / k

If the true 10 nearest neighbours are some set of documents and your index returns 8 of them in its top 10, recall@10 is 0.8.

Two things about this definition matter and both get missed.

“True” means brute force. To compute recall you need ground truth, which means running an exact flat search over the whole collection for each query in your test set. That’s expensive, which is why you do it once over a few hundred queries and save the results, rather than continuously.

Recall is not answer quality. Recall measures agreement with exact vector search. It says nothing about whether exact vector search would have been useful. An index at recall 1.0 over embeddings that don’t capture what your users mean is a perfectly faithful reproduction of a bad ranking. Recall is a measure of index fidelity, and it’s the right measure for tuning an index — just don’t mistake it for a measure of whether the system works.

Building an honest test set

The instrument determines the answer, so this is worth doing carefully.

Sample queries from your real distribution. Not hand-written examples. Real queries, including the short and strange ones. A few hundred is enough.
Compute exact ground truth with a flat search over the full collection. Slow, done once.
Store it — query, and the true top-k IDs with their distances.
Measure recall at your actual k. Recall@10 and recall@100 behave differently; tuning against the wrong one is a common error.
Regenerate whenever the corpus or the embedding model changes. Ground truth is relative to a specific collection state. Stale ground truth manufactures false alarms.

Two traps worth naming. Tuning on the same queries you evaluate on overfits the parameters to those queries — keep a held-out set. And averaging recall hides the tail: mean recall of 0.95 is consistent with most queries at 1.0 and a handful at 0.3. Look at the distribution, and look at the worst queries by hand. They’re usually a recognisable category — very short queries, or ones landing in a sparse region.

The shape of the curve

Plot recall against latency while sweeping one parameter — search breadth is the usual choice — and you get the same shape every time:

recall
  1.0 |                    ..............
      |              ......
      |         .....
      |      ...
      |    ..
      |  ..
  0.5 | .
      |.
      +------------------------------------ latency

Steep at first, then flattening hard. Three regions:

The steep region. Small increases in work buy large gains in recall. If you’re here, you’re under-provisioned and tuning up is close to free. Most default configurations sit here or just past it.

The knee. Where the slope drops sharply. Typically the best operating point — you have most of the recall available and haven’t started paying badly for it.

The flat region. Doubling the work buys a percent or two. Getting from 0.98 to 0.99 can cost as much as getting from 0.5 to 0.95 did. Almost nobody needs to be here.

The practical procedure: sweep the parameter, plot it, find the knee, sit slightly past it. This takes an afternoon and replaces months of guessing. Do it against your own data — the position of the knee is a property of your collection, not of the algorithm.

Which parameter to move

Several knobs move you along the curve, and they aren’t interchangeable.

Knob	Buys	Costs	Rebuild?
Search breadth (`efSearch`)	Recall	Latency	No
`nprobe`	Recall	Latency	No
Rerank oversampling	Recall	Latency	No
Connectivity (`M`)	Recall, better curve overall	Memory, per-hop cost	Yes
Build breadth (`efConstruction`)	Better curve overall	Build time only	Yes
Quantization level	Memory	Recall	Yes

The distinction that matters most: runtime parameters move you along the curve; build parameters move the curve itself.

Raising search breadth trades latency for recall on the curve you have. Raising connectivity or build breadth produces a better curve — more recall available at every latency. Build breadth is the standout, because it costs only build time and nothing at query time. If you’re tuning and haven’t raised it, raise it before anything else; you pay once.

Quantization moves you in the memory dimension, usually at some recall cost, and often lets you afford a better index — which can put you on a better curve overall despite the compression. This is why IVF-PQ at large scale can beat an uncompressed index that doesn’t fit in memory. The compressed one is worse per-vector and vastly better in aggregate, because the alternative was disk.

The ceiling: distance concentration

Sometimes the curve flattens below where you want it, and no parameter fixes that. Usually the cause is a property of the data rather than the index.

In high-dimensional spaces, under many distributions, distances concentrate: the distance from a query to its nearest point and to a far-away point become closer together as dimensionality rises. The ratio between them approaches 1. When that happens, “nearest” is a distinction with very little margin, and any approximate method — which works by pruning based on distance — has almost nothing to prune on.

It’s worth being precise, because this idea gets overstated. This is not the claim that high-dimensional search doesn’t work. Plenty of 768- and 1536-dimensional search works well. The phenomenon depends on the distribution, not just the dimension count. Real embeddings are not uniformly distributed in their nominal space — they lie on a much lower-dimensional structure within it. The quantity that governs difficulty is that intrinsic dimensionality, not the number of components.

Practical signs you’re near the data’s ceiling:

Recall flattens well below 0.9 no matter how much breadth you spend.
The gap between the 1st and 100th nearest distances is small.
Exact search’s own results don’t look meaningfully better than approximate ones.

That last one is the diagnostic. If exact search returns results your users find no better, the index was never the problem — the embeddings are. No amount of tuning fixes a representation that doesn’t separate your data, and the fix is a different embedding model, better preprocessing, or a hybrid approach that brings in a non-vector signal.

What recall target to aim for

Depends on what sits downstream, and the honest answer is often lower than instinct suggests.

Feeding a reranker. Recall@100 into a cross-encoder that reorders them — a moderate first-stage recall is fine. The reranker fixes ordering; you only need the right documents present. Spending latency on first-stage precision here is close to waste.

Feeding an LLM with top-5. Now recall@5 matters directly. Miss the right document and no downstream stage recovers it.

Deduplication or matching. Often needs very high recall, and is sometimes the case where exact search is the correct answer. If the collection is small enough for a flat index, use one — perfect recall, no tuning, no drift.

Recommendations and discovery. Frequently the most forgiving. If a user is browsing similar items, returning the 2nd through 11th nearest instead of the 1st through 10th is unnoticeable.

The mistake worth avoiding is tuning to 0.99 because it sounds responsible, and paying several times the latency for a difference no downstream consumer can detect.

The procedure

Build a query set of a few hundred real queries with exact ground truth. Hold some out.
Decide what recall your downstream stage actually needs.
Raise build breadth — it’s free at query time.
Sweep the runtime knob, plot recall against latency, find the knee.
Sit slightly past the knee, at or above your target.
Look at the worst-recall queries by hand. They’ll tell you something the average won’t.
Re-measure after any corpus, model, or version change. All three move the curve.

Everything else on this site — metrics, graph indexes, cluster indexes, quantization — is a different way of choosing where on this curve you sit, and how good a curve you get to choose from.