Measuring ANN Recall Honestly

The NeurIPS'21 billion-scale ANN challenge inverted the usual benchmark. Rather than letting entrants choose an operating point, the organisers fixed throughput at 10,000 queries per second on a 32-vCPU VM and ranked submissions purely on the recall they could hold there. Tuned entries from specialist teams came in around 0.71 to 0.79 recall@10 on the billion-point BIGANN, DEEP and MS Turing sets (Simhadri et al., 2022, PMLR 176). Any vendor chart that shows throughput without a recall axis is hiding this number, and the number is usually not 0.99.

Which recall

Two definitions circulate and they are not interchangeable.

recall@k is the fraction of the true \(k\) nearest neighbours that appear in the \(k\) returned. ScaNN's documentation states it this way, as the proportion of the true nearest \(k\) present in the returned \(k\). It is the right metric when a downstream consumer, a reranker or an LLM context window, will see all \(k\) results and can tolerate reordering.

1-recall@1, used throughout the DiskANN results, asks only whether the single true nearest neighbour is returned first. It is strictly harder for the same system and is the right metric for deduplication, entity resolution and anything that acts on the top hit alone.

A system quoting 0.95 on one of these can sit well below that on the other, so the metric belongs in every reported figure. For retrieval feeding a reranker, also measure recall at shortlist depth \(k \times \text{k\_factor}\) rather than at \(k\): that is the quantity the first stage is actually responsible for, and it is considerably more forgiving.

The ground-truth problem

Recall needs exact nearest neighbours, and exact search is the thing the index exists to avoid. That circularity is why most teams measure once, during the launch project, on a sampled query set against a frozen snapshot, and then never again.

The practical escape is sampling on both axes. A few hundred queries exact-searched against the current corpus gives a usable estimate; the cost is one brute-force pass over the corpus per batch, which is a nightly job, not a service. Keeping the query sample drawn from live traffic matters more than its size, because synthetic or historical queries miss exactly the shifts that cause recall to decay: new content, new phrasing, new language mix.

Two decay mechanisms show the same symptom and need different fixes. Tombstone accumulation in a graph index causes slow monotonic decline, fixed by a rebuild. Codebook or centroid staleness after a distribution shift causes a step change confined to a subset of queries, fixed by retraining. A single averaged recall number distinguishes neither, which is an argument for slicing the measurement by content age or tenant.

Reading other people's numbers

Standardised harnesses help. ANN-Benchmarks established the recall-versus-QPS curve as the standard figure and provides one interface across many libraries (Aumüller, Bernhardsson & Faithfull, Information Systems). Even so, three caveats survive.

Dataset dependence is severe: a configuration tuned on one embedding distribution transfers poorly to another, and published curves are drawn on SIFT, GloVe, DEEP and similar sets rather than on your corpus. Vendor ratios are claims, not measurements: ScaNN's roughly 2x QPS at matched accuracy on glove-100-angular is the authors' own figure against the libraries they tuned (Guo et al., ICML 2020). And published numbers are almost always unfiltered, while real queries carry predicates; for filtered search, independent reruns of Filtered-DiskANN on other datasets report considerably more modest throughput gains than the original paper's headline, so filtered recall has to be measured on your own filter distribution.

When it breaks

The failure is not a wrong number, it is an absent one. An index quietly running at 0.80 recall@10 loses one relevant document in five before any downstream component sees the candidates, and nothing recovers it later. Latency SLOs are standard and recall SLOs are not, largely because verification costs an exact search, which makes the nightly sampled job the cheapest observability a vector search system can buy.