🤖 AI

ANN Search: Recall What Matters

This paper argues that the standard Recall@k metric for Approximate Nearest Neighbor (ANN) search is a flawed proxy for actual utility because it prioritizes set overlap over result quality, proposing the inverse approximation ratio (1/Ratio@k) instead as a more accurate, efficient, and deployable metric that better correlates with downstream task performance while reducing unnecessary computational overhead.

Original authors: Dimitris Dimitropoulos, Nikos Mamoulis

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dimitris Dimitropoulos, Nikos Mamoulis

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

Imagine you are looking for the three best apples in a massive orchard to make a pie. You have a super-fast robot helper (the ANN algorithm) that can scan the orchard in a split second.

For years, the community has judged this robot based on one strict rule: Did it pick the exact same three apples that a human expert would have picked? This rule is called Recall. If the human picked apples A, B, and C, and the robot picked A, B, and D, the robot gets a bad score, even if apple D is just as sweet and perfect for the pie as apple C.

The authors of this paper argue that this rule is broken. They say: "Stop obsessing over the exact ID of the apple; just taste the apple."

Here is the breakdown of their argument using simple analogies:

1. The Problem: The "Name-Tag" Obsession

In the world of AI, data is often represented as points in a multi-dimensional space (like a giant, invisible cloud of dots). When you ask the AI for the "nearest" neighbors (the best apples), it returns a list.

The Old Way (Recall): The system checks if the robot returned the exact same IDs as the perfect list.
The Reality: In high-dimensional spaces (like complex AI models), there are often thousands of apples that are almost identical in taste and distance. The robot might pick apple D instead of apple C. They are practically twins. But because the ID is different, the "Recall" score crashes, making the robot look terrible.

The authors say this is like a teacher failing a student who wrote the correct answer "4" because the teacher's answer key said "4.00001." The student is right, but the grading system is too rigid.

2. The New Solution: The "Taste Test" (1/Ratio)

The authors propose a new metric called 1/Ratio. Instead of checking if the robot picked the exact same apples, it measures how close the apples are to the perfect ones.

The Analogy: Imagine the perfect apples are sitting on a table.
- Recall asks: "Did you pick the exact apples on the table?"
- 1/Ratio asks: "How far away from the table did you have to walk to find your apples?"

If the robot picks an apple that is 1 millimeter away from the perfect spot, 1/Ratio gives it a near-perfect score. If it picks an apple 10 miles away, the score drops. This metric ignores the "name tag" and focuses on the actual quality (distance).

3. The Big Discovery: You Can Go Much Faster

The paper ran tests on five different types of robot helpers (algorithms) across six different types of orchards (datasets). They found a massive surprise:

The Cost of Perfection: To get a high Recall score (picking the exact same IDs), the robots had to work incredibly hard, checking millions of extra apples. This slowed them down significantly.
The Efficiency of "Good Enough": When the robots were allowed to optimize for 1/Ratio (picking apples that are very close to the perfect ones, even if the ID is different), they could work 3 to 10 times faster.

The Metaphor: It's like trying to find a specific person in a crowd.

Recall demands you find the exact person wearing the specific hat you described. You have to stop and check every single face.
1/Ratio allows you to grab the person standing right next to them who looks 99.9% identical. You grab them instantly. The result is the same for your purpose, but you saved hours of time.

4. Does "Good Enough" Actually Work?

The skeptics might ask: "If we stop picking the exact apples, will our pie taste bad?"

The authors tested this in two real-world scenarios:

Image Classification (Sorting Photos): They tried to sort photos of cats and dogs. Even when the robot's "Recall" was low (it missed the exact "best" photos), the final result of sorting the photos remained almost perfectly accurate. The "mistakes" didn't matter.
RAG (Chatbots using search): They tested a chatbot that answers questions by searching a database. Even when the search engine missed the "exact" perfect documents (low Recall), the chatbot still gave excellent answers. The quality of the answer didn't drop.

The Conclusion: The "bad" scores from the old metric were a lie. The robots were actually doing a great job; they just weren't picking the exact same IDs.

5. Why This Matters

The paper concludes that the AI community has been wasting massive amounts of computing power trying to achieve a "perfect" score (Recall) that doesn't actually make the final result any better.

Old Way: "We need 100% Recall!" -> Result: Slow, expensive, and over-engineered.
New Way: "We need high 1/Ratio!" -> Result: Much faster, cheaper, and the final result (the pie, the photo sort, the chatbot answer) is just as good.

In short: Stop worrying about the exact name of the neighbor you found. If they live right next door to the perfect neighbor, they are good enough. And by accepting that, we can make AI systems run much faster and cheaper.

Technical Summary: ANN Search: Recall What Matters

Problem Statement

Approximate Nearest Neighbor (ANN) search is a foundational primitive in modern information retrieval and machine learning, particularly for tasks like classification and Retrieval-Augmented Generation (RAG). The community has standardized on Recall@k (the fraction of true exact $k$ -nearest neighbors retrieved) as the primary metric for evaluating and tuning ANN algorithms. Researchers optimize for throughput (Queries-Per-Second, QPS) at fixed Recall thresholds.

The authors argue that this convention is misaligned with the actual utility of ANN systems. In high-dimensional spaces (common in modern embeddings), distances to successive neighbors concentrate, leading to many "near-equidistant" candidates. An ANN algorithm may retrieve points that are geometrically as close to the query as the true neighbors but carry different identifiers. Under Recall@k, these geometrically accurate results are penalized as misses, forcing systems to incur unnecessary computational overhead to achieve high identifier overlap. The paper posits that Recall@k overstates the difficulty of the task and the cost of approximation, potentially leading to suboptimal system configurations.

Methodology

The paper proposes replacing Recall@k with 1/Ratio@k, the inverse of the approximation ratio. Unlike Recall, which counts identifier matches, 1/Ratio@k measures the quality of retrieved results based on the distances of the returned neighbors relative to the true $k$ -nearest neighbors.

Key Definitions:

Recall@k: $\frac{| \tilde{N}_k(q) \cap N_k(q) |}{k}$ , where $\tilde{N}_k$ is the retrieved set and $N_k$ is the true set.
Ratio@k: The mean of per-position distance ratios: $\frac{1}{k} \sum_{i=1}^k \frac{\tilde{d}_i(q)}{d_i(q)}$ , where $\tilde{d}_i$ and $d_i$ are the distances to the $i$ -th returned and true neighbors, respectively.
1/Ratio@k: The inverse of the above ratio, ranging from 0 to 1 (1 indicating perfect retrieval).

Experimental Setup:
The authors benchmarked five state-of-the-art ANN algorithms across diverse datasets with varying intrinsic dimensionalities (LID):

Annoy (Tree-based)
SuCo (Collision-based)
HNSW (Graph-based, industry standard)
RaBitQ (Quantization-based)
SymphonyQG (Hybrid Graph-Quantization)

The evaluation covered six datasets (Gist, SimpleWiki, ImageNet, AGNews, MNIST, Fashion-MNIST) and extended to downstream tasks including image classification (MNIST, Fashion-MNIST, CIFAR-10, SVHN) and RAG (SciFact, NFCorpus, HotpotQA, MS-MARCO, PubMedQA).

Evaluation Strategy:

Efficiency Analysis: Measured the computational cost (QPS, distance computations, build time, memory) required to reach specific quality thresholds ( $T \in \{0.90, 0.95, 0.99\}$ ) under both metrics.
Downstream Validation: Used synthetic recall control to artificially degrade recall levels ( $r \in [0.4, 1.0]$ ) while maintaining geometric quality. They measured downstream performance (Label Precision for classification; BERTScore, Semantic Similarity, and LLM-graded scores for RAG) to determine if low Recall actually degrades utility.
Metric Comparison: Calculated the Mean Absolute Deviation (MAD) between the metrics (Recall vs. 1/Ratio) and the true downstream quality to assess which metric is a better proxy.

Key Contributions

Proposal of 1/Ratio@k: Introduced a quality metric that is judge-free, hyperparameter-free, and computable solely from standard ANN benchmark inputs (embeddings and ground-truth identifiers). Unlike alternatives like Semantic Recall or Tolerant Recall, it requires no external LLM judges or tunable tolerance parameters.
Demonstration of Computational Overhead: Showed that optimizing for Recall@k imposes a substantial computational penalty compared to optimizing for 1/Ratio@k.
Downstream Stability Evidence: Provided empirical evidence that downstream task performance (classification accuracy and RAG answer quality) remains stable even when Recall drops significantly (e.g., to 0.4), provided the geometric distance quality (1/Ratio) remains high.
Geometric Explanation: Linked the divergence between Recall and 1/Ratio to Local Intrinsic Dimensionality (LID) and the neighborhood size $k$ . As LID and $k$ increase, the probability of retrieving geometrically close but identifier-mismatched neighbors increases, causing Recall to degrade while 1/Ratio remains high.

Experimental Results

1. Efficiency and Cost (RQ1 & RQ2)

Throughput (QPS): Optimizing for 1/Ratio@k yields significantly higher throughput than optimizing for Recall@k. At a quality threshold of $T=0.95$ $T = 0.95$ and $k=100$ $k = 100$ , the speedup ranges from 1.86× to 9.36× in distance computations and 2× to 10× in QPS depending on the algorithm and dataset.
- Example: On the ImageNet dataset with HNSW, achieving 1/Ratio@100 $\ge$ 0.95 is 9.98× faster than achieving Recall@100 $\ge$ 0.95.
Build Time: The cost to build indices for high Recall is often higher. For HNSW on Gist, achieving Recall $\ge$ 0.90 required 18.39× more build time than achieving 1/Ratio $\ge$ 0.90.
Memory: Memory footprint differences are minimal. The gap is usually near 1.0×, as memory is dominated by vector storage rather than the parameters used to tune for high Recall.
Algorithm Rankings: The relative ranking of algorithms (which is fastest/cheapest) remains largely stable between the two metrics. The metric change affects the absolute cost to reach a threshold, not the relative performance of the algorithms.

2. Geometric Divergence (RQ3)

The gap between Recall and 1/Ratio widens as $k$ increases and as LID increases.
In high-LID spaces, neighbors are nearly equidistant. An ANN algorithm returning a vector with a different ID but nearly identical distance is penalized heavily by Recall but receives a high score from 1/Ratio.
Recall degrades substantially as $k$ grows (e.g., dropping significantly from $k=1$ to $k=100$ ), whereas 1/Ratio remains relatively flat.

3. Downstream Task Quality (RQ4)

Image Classification: As Recall dropped from 1.0 to 0.4, Label Precision (LP@100) remained remarkably stable (e.g., dropping only from 1.0 to ~0.94 on SVHN).
- MAD Analysis: Recall had a Mean Absolute Deviation (prediction error) of ~26% from true quality. In contrast, 1/Ratio had an error of < 3% (often < 1%).
RAG Tasks: Answer quality (measured by BERTScore, Semantic Similarity, and LLM grades) showed negligible degradation as Recall dropped to 0.4.
- On human-annotated benchmarks, text quality metrics varied by less than 1.2% despite a 60% drop in Recall.
- 1/Ratio tracked this stability closely, while Recall falsely signaled a massive quality drop.
- MAD Analysis: For RAG, Recall's prediction error was ~30%, while 1/Ratio's error was < 3% (often < 1%).

Significance and Claims

The paper claims that the community's reliance on Recall@k has led to an unnecessary over-engineering of ANN systems. By tuning for high Recall, practitioners incur substantial computational costs (time, energy, latency) to retrieve results that are geometrically indistinguishable from the ground truth but fail an identifier-matching test.

The authors conclude that:

1/Ratio@k is a superior proxy for actual downstream utility, accurately reflecting the stability of retrieval quality even when Recall is low.
Adopting 1/Ratio@k allows for faster, cheaper, and more efficient ANN deployments without sacrificing the quality of the final application (classification or generation).
Configurations currently dismissed as "inadequate" due to low Recall are often operationally sufficient and can be deployed to achieve significant efficiency gains.

The study advocates for a shift in the ANN research community's evaluation paradigm: moving away from optimizing for identifier overlap (Recall) toward optimizing for geometric proximity (1/Ratio), thereby aligning system tuning with the true requirements of downstream machine learning tasks.