What is the difference between precision and recall in ANN search?

Precision and recall in ANN search measure different questions, recall asking what fraction of correct answers were found and precision asking what fraction of returned answers are correct, though the two collapse into the same number for top-k search.
Created: Updated: 5 min read

Precision and recall in ANN search measure two different questions about a set of returned results — recall asks what fraction of the truly correct answers actually got found, while precision asks what fraction of the returned answers are actually correct. In the specific, common case of top-k nearest-neighbor search, where a fixed number of results are always requested, these two metrics turn out to collapse into the same number, which is exactly why this documentation, and most discussions of HNSW generally, focus almost exclusively on recall — but understanding why that collapse happens, and when it stops happening, clarifies a distinction that matters more in other search contexts.

Recall, in its general form across many kinds of search and classification problems, measures how much of everything relevant actually got captured — out of every genuinely correct answer that exists, what fraction did the system actually return. Precision measures the inverse concern — out of everything the system actually returned, what fraction was genuinely correct, rather than a mistaken or irrelevant inclusion. A system that returns a huge number of results, including every correct one but also a large number of incorrect ones, would have high recall but low precision, since it captured everything relevant but diluted that success with many wrong answers. A system that returns only a small number of very carefully chosen results, all of which are correct but which miss many other genuinely correct answers that exist, would have high precision but low recall.

In a top-k search, both the “correct” set — ground truth’s true k nearest neighbors — and the “returned” set — the approximate search’s own k results — are fixed at exactly the same size, k, by construction. Recall, as covered on the recall@k glossary page, is the number of correctly matched results divided by k, the size of the ground-truth set. Precision, applying the general definition above, would be the number of correctly matched results divided by k as well, but this time as the size of the returned set. Because both denominators are identical — both are exactly k, by the very nature of how a top-k query is structured — recall and precision produce the exact same numeric value for any top-k nearest-neighbor search, which is precisely why the two terms are used interchangeably in this specific context and why HNSW documentation generally settles on “recall” as the standard term rather than needing to track both separately.

This collapse specifically depends on the returned set and the ground-truth set being the same fixed size, which stops holding once a search’s result-set size isn’t rigidly tied to k in this way. Range search, covered on its own glossary page, is exactly this kind of case: a range query returns however many points happen to fall within the given distance threshold, which generally isn’t the same number as however many points ground truth’s exhaustive search would identify as genuinely within that threshold. In a range-search context, recall and precision genuinely diverge and need to be measured separately — recall asks what fraction of the true qualifying points the search actually found, while precision asks what fraction of the points the search actually returned were genuinely qualifying, and a search could score well on one of these measures while scoring poorly on the other, since the two denominators are no longer forced to be identical the way they are in fixed-k top-k search.

Why does this distinction matter for anyone reading benchmark results or evaluation methodology involving a mix of query types?

Recognizing this collapse-versus-divergence distinction prevents a specific, easy-to-make mistake: assuming a single “recall” number reported for a top-k benchmark automatically tells the whole story for a system that also, elsewhere, handles range queries or other non-fixed-size result patterns. A range-search-heavy application evaluating its own search quality needs to actually track precision and recall as genuinely separate figures, since a single collapsed number wouldn’t exist to report in the first place — the fixed-k coincidence that makes “recall” alone sufficient for standard nearest-neighbor search simply doesn’t apply once the result-set size itself becomes variable.

Having covered why precision and recall collapse into a single figure for standard top-k search but genuinely diverge for range search, the recall@k and range-search glossary pages are worth revisiting together with this fuller picture of exactly when each concept applies cleanly and when the two need to be tracked independently. From there, the naive-post-filtering and oversampling-in-filtered-search glossary pages, under filtered and hybrid search concepts, look at related evaluation nuances that arise once filtering gets layered on top of either query pattern.