Source-linked AI summary
Semantic Recall for Vector Search
Leonardo Kuffo, Ioanna Tsakalidou, Roberta De Viti, Albert Angel, Jiří Iša, Rastislav Lenhardt
TL;DR
Traditional recall can penalize approximate search for missing mathematically close but semantically irrelevant neighbors. The paper proposes semantic recall and tolerant recall, and reports that these measures better reflect retrieval quality and support improved cost-quality tradeoffs. Its tuning results include reduced search cost while preserving the targeted metric.
Problem
Traditional recall can misrepresent semantic retrieval quality because it penalizes missing mathematically close neighbors even when they are irrelevant.
Source: §1 · p. 1Method
Results
Across embedding models, ANNS algorithms, and data scales, the metrics provide more faithful evaluation; tuning for semantic recall reduced cost by 14% while preserving semantic recall.
Source: §4.3 · p. 4, §7 · p. 5Takeaways & Limitations
Semantic recall distinguishes losses affecting relevant results from reshuffling irrelevant ones, supporting more meaningful cost-quality tradeoffs in algorithm design and tuning.
Source: §6 · p. 5Semantic recall requires access to raw objects for judging, and domain-specific datasets may still require human validation of LLM judgments.
Source: §6 · p. 5
Abstract
from arXiv · showhide
We introduce Semantic Recall, a novel metric to assess the quality of approximate nearest neighbor search algorithms by considering only semantically relevant objects that are theoretically retrievable via exact nearest neighbor search. Unlike traditional recall, semantic recall does not penalize algorithms for failing to retrieve objects that are semantically irrelevant to the query, even if those objects are among their nearest neighbors. We demonstrate that semantic recall is particularly useful for assessing retrieval quality on queries that have few relevant results among their nearest neighbors-a scenario we uncover to be common within embedding datasets. Additionally, we introduce Tolerant Recall, a proxy metric that approximates semantic recall when semantically relevant objects cannot be identified. We empirically show that our metrics are more effective indicators of retrieval quality, and that optimizing search algorithms for these metrics can lead to improved cost-quality tradeoffs.
1 Introduction
Approximate nearest-neighbor search speeds up vector retrieval, but traditional recall can misrepresent semantic quality by penalizing missed mathematically close yet irrelevant results. The paper introduces semantic recall and tolerant recall to evaluate retrieval more meaningfully.
1 Introduction
- Traditional recall penalizes missed exact neighbors even when they are semantically irrelevant, so low recall can misstate approximate search quality.This issue is especially prevalent for queries with few relevant results among their nearest neighbors.Source: §1 · p. 1
- Curated ground truth can label relevant objects that exact search misses because the embedding model placed them too far away, potentially penalizing ANNS algorithms for model limitations.The paper notes that ANNS cannot retrieve semantically better neighbors than exact search identifies.Source: §1 · p. 2
- Semantic recall counts semantically relevant ground-truth neighbors that are theoretically retrievable via exact nearest-neighbor search.The figure highlights these eligible results in green.Source: Figure 1 · p. 1, §1 · p. 2
- The paper introduces tolerant recall as a proxy for semantic recall, allowing a true nearest neighbor to be replaced by a retrieved result with a sufficiently close score.Its contributions also include evaluating the metrics and tuning ANNS search algorithms with them.Source: §1 · p. 2
2 Semantic Recall
Semantic recall evaluates whether approximate search retrieves semantically relevant objects among exact-search neighbors, rather than rewarding mathematical proximity alone. The paper identifies those semantic neighbors by judging a reduced set of exact-search results.
2 Semantic Recall
- Semantic recall is the fraction of retrieved ANNS results that belong to the semantically relevant subset of a query’s top-k exact-search neighbors.Semantic neighbors are identified by an external judge; a high score indicates retrieval of semantically meaningful objects.Source: §2 · p. 2
- Semantic recall avoids penalizing missed irrelevant neighbors and needs no threshold hyperparameter, unlike metrics such as recall@k-ε, robustness@k-γ, and RDE.It also focuses on relevant objects present in exact-search ground truth, avoiding penalties for relevant objects the embedding model failed to place there.Source: §2 · p. 2
2.1 Finding Semantic Neighbors
- To find semantic neighbors, the method runs exact nearest-neighbor search, then judges each top-k result as relevant or irrelevant.Human judges or LLMs can perform the classification, which evaluates a reduced subset rather than millions of query-object pairs.Source: §2.1 · p. 2
3 Tolerant Recall
Tolerant recall scores approximate search by allowing retrieved objects to replace ground-truth neighbors when their scores are sufficiently close. The metric is intended for settings where semantic neighbors cannot be identified and is described as useful for dynamic datasets.
3 Tolerant Recall
- Tolerant recall allows retrieved results to replace ground-truth neighbors when their scores fall within a specified tolerance.For inner-product similarity, the tolerance is a percentage threshold; the metric counts the largest set of unique matches or qualifying replacements.Source: §3 · p. 2
- When semantic neighbors are unavailable, score-based replacements provide an approximation of semantic recall and can be used in existing ANNS pipelines.The paper also describes tolerant recall as more robust for monitoring frequently updated datasets when ground truth is not updated with each database change.Source: §3 · pp. 2–3
- Tolerant recall can register losing one of a query’s few high-scoring semantic results, unlike recall@k-ε, which may still count a result within its threshold of the kth ground-truth neighbor as correct.The metric is also described as robust to small ranking perturbations, including those introduced by quantization.Source: §3 · pp. 2–3
4 Evaluation
The evaluation examines semantic-neighbor distributions and compares recall metrics on MSMARCO, including their use as tuning objectives. Semantic and tolerant recall better reflect retrieval of relevant results in low-semantic-neighbor queries, and tuning for them can reduce search cost.
4 Evaluation
- The MSMARCO evaluation used 8.83M documents embedded as 3072-dimensional vectors, 250 questions, top-100 brute-force neighbors, and Gemini 2.5 relevance judgments.The evaluation used normalized embeddings and inner-product similarity.Source: §4 · p. 3
4.1 Analysis of Semantic Neighbors
- 40% of queries had 0–15 semantic neighbors, while another cluster neared 90–100; semantic neighbors showed larger score gaps, especially for queries with fewer than 20.Non-semantic neighbors had consistently small score deltas, making their ranking more sensitive to fluctuations and traditional-recall penalties.Source: §4.1 · p. 3
4.1.1 Cross validation.
- Independent judges agreed on 91.1% of sampled relevance labels (Cohen’s κ=0.82), while Gemini labeled disputed cases relevant more often than Claude.Agreement was 89.5% for relevant labels and 93.3% for not-relevant labels; only two queries fell below 70% agreement.Source: §4.1.1 · p. 3
4.2 Traditional, Semantic, and Tolerant Recall
- For queries with few semantic neighbors, semantic recall is 0.903 versus traditional recall 0.762; tolerant recall closely approximates semantic recall, while small 8-bit score errors can reorder irrelevant neighbors.The comparison also reports top-20 traditional and semantic recall of 0.869 and 0.901, respectively.Source: §4.2 · pp. 3–4, Table 3 · p. 3, Figure 3 · p. 4
4.2.1 Comparison to R-Precision.
- R-precision can penalize relevant documents outside the top-R ground-truth ranking even when exact search would not return them there; semantic recall allows relevant results anywhere in top-k.For queries with fewer than 20 semantic neighbors, ground-truth rank and semantic relevance were negatively correlated (rank-biserial correlation −0.72), but not perfectly aligned.Source: §4.2.1 · p. 4
4.3 Tuning for Semantic Recall
- At 95% tolerant versus traditional recall, cost falls ~25% on BigANN, ~5% on GloVe, and ~35% on MSMARCO; matching 98.93% semantic recall cuts cost 14%.At 98.69% tolerant recall, tuning for tolerant recall also achieves the same metric at 5% lower cost than the traditional-recall-tuned configuration.Source: §4.3 · p. 4, Figure 5 · p. 4
5 Generalizability
A Thai-language MIRACL evaluation tests whether the recall metrics generalize beyond MSMARCO. The paper also proposes a score-difference proxy for choosing tolerant-recall thresholds when semantic labels are unavailable.
5 Generalizability
- 60% of MIRACL queries had at most four semantic neighbors, and, as on MSMARCO, low-neighbor queries showed low traditional recall while semantic recall confirmed relevant retrieval.Tolerant recall provided a middle-ground approximation without requiring semantic judgments; semantic neighbors also had larger score deltas than non-semantic neighbors.Source: §5 · pp. 4–5, Figure 6 · p. 5
- On 542,166 Thai-language MIRACL documents and 100 questions, average traditional, semantic, and tolerant recall were 0.75, 0.85, and 0.83, respectively.The evaluation used top-20 brute-force neighbors, Gemini 2.5 judgments, and a FAISS IVF index with a 2% tolerance threshold.Source: §5 · pp. 4–5, Figure 7 · p. 5
5.1 Choosing a tolerance threshold
- The proposed threshold proxy uses the relative score difference between the 2^3k-th and kth neighbors, normalized by the maximum ground-truth score and averaged across queries.The proxy closely matched semantic recall on both datasets; estimating thresholds per query is noted as a possible improvement, and score-compression error offers a conservative lower bound.Source: §5.1 · p. 5
6 Discussion
Semantic recall distinguishes losses in relevant results from reshuffling irrelevant neighbors, supporting cost–quality tradeoffs and suggesting that low traditional recall can reflect queries with few or no relevant neighbors. The discussion also notes practical limits of semantic recall and reports that tolerant recall tracks it across thresholds.
6 Discussion
- Semantic recall distinguishes performance losses affecting relevant results from those reshuffling irrelevant ones, supporting more meaningful cost–quality tradeoffs.The authors hypothesize that queries with few or no relevant neighbors contribute to long-tailed traditional-recall distributions.Source: §6 · p. 5
- Across thresholds, the tolerant-recall proxy closely follows semantic recall.Figure 8 shows the effect of different thresholds on tolerant recall.Source: Figure 8 · p. 5
- Traditional-recall tuning can incur extra retrieval effort to recover near-equidistant irrelevant neighbors, effectively optimizing for mathematical exactness at unnecessary cost.The discussion characterizes these neighbors as “noise.”Source: §6 · p. 5
- Semantic recall requires raw objects for judging, and domain-specific datasets may require human validation of LLM judgments.The paper also notes binary judgments, unavoidable judgment errors, possible judge–system correlations, and that semantic recall is undefined when no relevant results exist.Source: §6 · p. 5
7 Conclusions
The paper concludes that semantic and tolerant recall better capture retrieval quality in semantic search than traditional recall, supporting more meaningful cost–quality tradeoffs. It reports validation across embedding models, ANNS algorithms, and data scales, and proposes further evaluation and early-termination work.
7 Conclusions
- Semantic and tolerant recall better capture retrieval quality by avoiding penalties for missing near-equidistant but semantically irrelevant results.The paper reports validation across embedding models, ANNS algorithms, and data scales.Source: §7 · p. 5
- These metrics support more meaningful cost–quality tradeoffs for algorithm design and tuning.The authors hope the IR and Vector Search communities will evaluate relevant answers rather than mathematically closest noise.Source: §7 · p. 5
- Future work proposed includes incorporating the metrics into early-termination mechanisms and comparing them across ANNS algorithms such as HNSW.The paper also provides a code notebook to reproduce its experiments.Source: §7 · p. 5