arXiv:2606.04522cs.IRcs.AI2026-06

用新指标替代召回率,更真实反映近似最近邻搜索的实用价值。

ANN Search: Recall What Matters

  • 提出1/Ratio@k指标,基于检索结果与真实邻居的距离差异评估质量。
  • 在相同效率下,1/Ratio@k达标时的计算成本远低于传统召回率标准。
  • 下游任务中,该指标更稳定地反映实际效果,适合工程部署参考。

近似最近邻(ANN)搜索已成为信息检索和现代机器学习任务的核心组件,涵盖分类到检索增强生成。当前社区主要通过特定召回率@k(Recall@k)下的吞吐量来评估和调优算法。本文认为,真正重要的是检索结果的质量,而非其与真实k近邻集合的重叠程度。我们发现,使用Recall@k评估会带来不必要的计算开销,并提出用1/Ratio@k(逆近似比)替代。该指标衡量检索结果与真实邻居间的距离差异,无需裁判、无超参数,仅需标准基准输入即可计算。我们在涵盖广泛内在维度的多种数据集上对主流ANN算法进行了全面评估,覆盖效率、下游分类及检索增强生成任务。在效率方面,优化1/Ratio@k可在显著更低的计算成本下达到运行质量阈值;在下游任务中,标签精确度、语义相似性、BERTScore及大模型评分等指标在Recall@k大幅下降时仍保持高度稳定,而1/Ratio@k则紧密跟踪这一稳定性,显著优于Recall@k。最终,尽管Recall@k高估了近似的真实成本,1/Ratio@k却提供了更准确、可部署的近似搜索质量代理指标。

原文摘要 · Abstract (English)

Approximate nearest neighbor (ANN) search has become a core primitive in information retrieval and modern machine learning tasks, from classification to retrieval-augmented generation. The community evaluates and tunes ANN algorithms primarily on their throughput at a given Recall@k, the fraction of true exact neighbors retrieved. We argue that what really matters in ANN search is the quality of the retrieved results and not their overlap with the true kNN set. We show that using Recall@k to assess retrieval quality forces unnecessary computational overhead and investigate replacing it by 1/Ratio@k, the inverse approximation ratio. 1/Ratio@k evaluates the differences between the distances of the retrieved and true neighbors. It is judge-free, hyperparameter-free, and computable from standard ANN benchmark inputs alone. We benchmark state-of-the-art ANN algorithms across diverse datasets spanning a wide range of intrinsic dimensionalities, evaluating the two metrics comprehensively across efficiency, downstream classification, and retrieval-augmented generation. On the efficiency axis, optimizing for 1/Ratio@k reaches operational quality thresholds at a substantially lower computational cost than Recall@k. In downstream tasks, performance indicators (label precision, semantic similarity, BERTScore, and LLM-graded quality) remain highly stable even when Recall@k drops significantly. The inverse approximation ratio, on the other hand, closely mirrors this stability, tracking true utility much better than Recall@k. Ultimately, while Recall@k overstates the true cost of approximation, 1/Ratio@k offers a more accurate, deployable proxy for actual ANN quality.

近似搜索评估指标性能优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。