💻 computer science

Semantic Recall for Vector Search

This paper introduces "Semantic Recall," a novel metric for evaluating approximate nearest neighbor search that focuses only on semantically relevant objects to avoid penalizing algorithms for missing irrelevant neighbors, alongside a proxy metric called "Tolerant Recall," demonstrating that optimizing for these measures yields better cost-quality tradeoffs than traditional recall.

Original authors: Leonardo Kuffo, Ioanna Tsakalidou, Roberta De Viti, Albert Angel, Jiří Iša, Rastislav Lenhardt

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Leonardo Kuffo, Ioanna Tsakalidou, Roberta De Viti, Albert Angel, Jiří Iša, Rastislav Lenhardt

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The "Perfect Match" Problem: Why Being Mathematically Close Isn't Always Being Relevant

Imagine you are a librarian in a massive, futuristic library where every book is represented by a single dot on a giant, invisible map. When you ask a question (like "How do I fix a leaky faucet?"), the library's robot doesn't read the books; it just looks for the dots that are physically closest to your question dot on the map.

This is how modern AI search works. It turns your words into numbers (vectors) and finds the "nearest neighbors." But here's the catch: Being close on the map doesn't always mean the book is actually helpful.

This paper introduces a new way to measure how good these search robots are, arguing that we've been grading them on the wrong test.

The Old Way: The "Strict Math Teacher"

Traditional Recall is like a strict math teacher who only cares about the ruler.

The Scenario: You ask, "How do I fix a faucet?"
The Reality: The robot finds 10 books.
- Book #1: "How to fix a faucet" (Perfect match).
- Book #2: "History of plumbing tools" (Okay, but not a fix).
- Book #3: "How to fix a bicycle" (Wrong topic, but the words "fix" and "tool" make it sit very close to your question on the map).
The Problem: Because Book #3 is mathematically closer to your question than Book #1, the "Strict Math Teacher" says, "You missed the true closest book! You failed!"

The paper argues this is unfair. The robot didn't fail; the map itself is slightly blurry. The AI model that created the map made a tiny mistake, placing "bicycle" too close to "faucet." Penalizing the robot for missing a mathematically close but useless book is like punishing a GPS for getting you to the wrong street because the map was drawn slightly wrong.

The New Way: "Semantic Recall" (The "Smart Librarian")

The authors propose Semantic Recall. This metric acts like a Smart Librarian who actually reads the books.

How it works: The Smart Librarian looks at the "True" list of the 10 closest books (the ground truth). Then, they ask: "Which of these are actually relevant to the question?"
- If "How to fix a bicycle" is on the list but isn't actually helpful, the Librarian says, "Ignore that one. It's just noise."
- The robot only gets penalized if it misses a book that is both close on the map AND actually helpful.
The Analogy: Imagine you are looking for a red apple in a basket.
- Old Metric: If there is a red marble right next to the apple, and you grab the apple but miss the marble, you get a bad grade.
- New Metric: The marble is irrelevant. If you grab the apple, you get an A+. We don't care about the marble.

The "Tolerant Recall" (The "Fuzzy Match")

Sometimes, we don't have a Smart Librarian to read the books (maybe we only have the numbers, not the text). In that case, the authors suggest Tolerant Recall.

The Analogy: Imagine you are looking for a specific shade of blue paint.
- Strict Math: You must find the exact paint chip. If you get a shade that is 0.01% different, you fail.
- Tolerant Recall: If the paint chip you found is so close in color that the human eye can't tell the difference, we count it as a win.
Why it helps: In search, tiny mathematical errors (like rounding numbers to save space) often shuffle the order of useless books. Tolerant Recall says, "If the scores are basically the same, it doesn't matter which useless book you picked. As long as the good books are there, you're doing fine."

Why Does This Matter? (The "Cost" of Being Perfect)

The paper shows that trying to be perfect at the "Strict Math" game is incredibly expensive and often useless.

The "Noise" Trap: To find that mathematically closest "bicycle" book (which is actually irrelevant), the computer has to dig deeper, check more shelves, and use more electricity.
The Result: By chasing "mathematical perfection," companies are spending a fortune to retrieve junk.
The Fix: By using Semantic or Tolerant Recall, developers can tune their systems to stop chasing the noise. They can save up to 35% of their computing costs while still giving users the right answers.

The Big Picture

The authors found that in many datasets, most questions only have a few truly relevant answers, surrounded by a sea of "mathematically close but useless" noise.

Old View: "The search engine is broken because it missed the 5th closest math neighbor."
New View: "The search engine is great because it found the 3 relevant answers, even if it missed the 4th closest math neighbor which was just a red herring."

In short: Stop grading the search engine on how well it follows a blurry map. Grade it on whether it actually brings you the right book. This new metric allows us to build faster, cheaper, and smarter search engines that focus on meaning rather than just math.

1. Problem Statement

The paper addresses a critical flaw in the evaluation of Approximate Nearest Neighbor Search (ANNS) algorithms used in modern semantic search systems.

The Limitation of Traditional Recall: Current industry standards rely on "Recall," which measures the proportion of retrieved items that appear in a "ground truth" list generated by an exact (brute-force) Nearest Neighbor Search (NNS).
The Core Issue: Exact NNS relies on mathematical proximity (e.g., Euclidean distance or inner product) within an embedding space. However, mathematical closeness does not always equate to semantic relevance.
- Embedding models often place semantically irrelevant items ("mathematical noise") very close to a query vector.
- Conversely, semantically relevant items might be slightly further away mathematically due to model limitations.
The Consequence: Traditional recall penalizes ANNS algorithms for failing to retrieve these mathematically close but semantically irrelevant items. This leads to misleading metrics where an algorithm is deemed "worse" for skipping noise, even if it successfully retrieved the semantically relevant items. This is particularly problematic for queries with few relevant results, a common scenario in embedding datasets.

2. Methodology

The authors propose two novel metrics to better align evaluation with the actual goal of semantic search: retrieving relevant information rather than mathematical neighbors.

A. Semantic Recall (srecall)

Definition: The fraction of semantically relevant neighbors retrieved by an ANNS algorithm, relative to the total number of semantically relevant neighbors found in the exact ground truth.
Formula: $srecall = \frac{|R \cap SN|}{|SN|}$ $sr ec a l l = \frac{∣ R \cap S N ∣}{∣ S N ∣}$
- $R$ : Set of retrieved neighbors.
- $SN$: Set of Semantic Neighbors (a subset of the ground truth identified as semantically relevant).
Identification of Semantic Neighbors: The authors employ a two-step process:
1. Compute the top- $k$ ground truth via exact NNS.
2. Use an external judge (Human or Large Language Model, specifically Gemini 2.5 in their experiments) to classify each ground truth item as "Relevant" or "Not Relevant" based on the query.
Key Advantage: It ignores "mathematical noise." If an ANNS algorithm skips an irrelevant neighbor that was mathematically closer than a relevant one, it is not penalized.

B. Tolerant Recall (trecall)

Motivation: Semantic Recall requires access to raw data and a judging process (LLM/Human), which is not always feasible (e.g., in dynamic datasets or when only embeddings are available).
Definition: A proxy metric that approximates Semantic Recall by allowing a retrieved result to replace a ground truth neighbor if their similarity scores are within a specific tolerance threshold ( $x\%$ ).
Mechanism: If a retrieved item $t_i$ has a score $score(t_i) \ge score(g_i) \cdot (1 - x\%)$ , where $g_i$ is a ground truth neighbor, it counts as a match.
Benefit: It is robust to small perturbations in the distance metric (e.g., caused by quantization) and does not require manual semantic labeling, making it suitable for production pipelines.

3. Key Contributions

Definition of Semantic Recall: A new metric that filters out mathematical noise, focusing strictly on the retrieval of semantically meaningful objects.
Methodology for Semantic Neighbor Identification: A scalable approach using LLMs to judge relevance on the top- $k$ ground truth results, which is significantly more efficient than curating full "gold standard" datasets.
Introduction of Tolerant Recall: A practical, hyperparameter-free (or easily tunable) proxy that tracks Semantic Recall closely without requiring semantic labels.
Empirical Validation: Comprehensive experiments on the MSMARCO (English) and MIRACL (Thai) datasets demonstrating that traditional recall is often misaligned with user satisfaction, especially for queries with few relevant results.
Optimization Insights: Evidence that tuning ANNS algorithms for Semantic/Tolerant Recall yields better cost-quality tradeoffs than tuning for traditional Recall.

4. Results

The authors evaluated their metrics using the MSMARCO corpus (8.83M documents) and MIRACL (Thai subset) with various ANNS configurations (e.g., ScANN, FAISS IVF).

Distribution of Relevant Results: Analysis revealed a bimodal distribution where many queries have very few (0–15) semantically relevant neighbors in the top-100 ground truth.
Metric Comparison:
- Traditional Recall: Significantly lower for queries with few semantic neighbors (avg. 0.762) because it penalizes the omission of irrelevant, mathematically close neighbors.
- Semantic Recall: Much higher (avg. 0.903 for the same group), reflecting that the relevant items were actually retrieved.
- Tolerant Recall: Closely tracks Semantic Recall (0.859 vs 0.903) with a 1% tolerance, validating its use as a proxy.
Impact of Quantization: Small errors introduced by 8-bit quantization reorder irrelevant neighbors, causing Traditional Recall to drop. Tolerant Recall and Semantic Recall remain stable as they ignore these irrelevant swaps.
Cost-Quality Tradeoff (Tuning):
- When tuning ScANN to target 98% Traditional Recall, the system incurs high computational costs to retrieve irrelevant neighbors.
- When tuning for 98% Tolerant Recall (which corresponds to ~98.9% Semantic Recall), the system achieves the same quality of relevant retrieval at 5% lower cost.
- Tuning for 95% Tolerant Recall instead of 95% Traditional Recall reduced costs by ~25% on BigANN, ~5% on GloVe, and ~35% on MSMARCO.

5. Significance and Conclusion

Paradigm Shift: The paper argues that the IR community should move away from optimizing for mathematical exactness (Traditional Recall) toward optimizing for semantic utility.
Efficiency Gains: By recognizing that "near-equidistant" irrelevant neighbors are noise, developers can relax search constraints, significantly reducing computational costs (bytes read, CPU cycles) without degrading the actual user experience.
Practical Applicability: The proposed metrics are applicable across different embedding models, ANNS algorithms (HNSW, ScANN, IVF), and data scales.
Future Work: The authors suggest integrating these metrics into early-termination mechanisms and comparing them across diverse ANNS architectures.

In summary, Semantic Recall and Tolerant Recall provide a more accurate, user-centric evaluation framework for vector search, enabling systems to be faster and cheaper while maintaining high relevance.