Web-scale search systems learn an encoder to embed a given query which is
then hooked into an approximate nearest neighbor search (ANNS) pipeline to
retrieve similar data points. To accurately capture tail queries and data
points, learned representations typically are rigid, high-dimensional vectors
that are generally used as-is in the entire ANNS pipeline and can lead to
computationally expensive retrieval. In this paper, we argue that instead of
rigid representations, different stages of ANNS can leverage adaptive
representations of varying capacities to achieve significantly better
accuracy-compute trade-offs, i.e., stages of ANNS that can get away with more
approximate computation should use a lower-capacity representation of the same
data point. To this end, we introduce AdANNS, a novel ANNS design framework
that explicitly leverages the flexibility of Matryoshka Representations. We
demonstrate state-of-the-art accuracy-compute trade-offs using novel
AdANNS-based key ANNS building blocks like search data structures (AdANNS-IVF)
and quantization (AdANNS-OPQ). For example on ImageNet retrieval, AdANNS-IVF is
up to 1.5% more accurate than the rigid representations-based IVF at the same
compute budget; and matches accuracy while being up to 90x faster in wall-clock
time. For Natural Questions, 32-byte AdANNS-OPQ matches the accuracy of the
64-byte OPQ baseline constructed using rigid representations -- same accuracy
at half the cost! We further show that the gains from AdANNS translate to
modern-day composite ANNS indices that combine search structures and
quantization. Finally, we demonstrate that AdANNS can enable inference-time
adaptivity for compute-aware search on ANNS indices built non-adaptively on
matryoshka representations. Code is open-sourced at
this https URL

本文介绍了一种基于 Matryoshka Representations 的 ANNS 设计框架 - AdANNS，通过使用不同容量的自适应表示来实现更好的准确性和计算效率平衡，例如在图像检索上，AdANNS-IVF 与在相同计算预算下基于刚性表示的 IVF 相比可提高 1.5% 的准确性，并且在时钟时间上快 90 倍；在自然问题上，32 字节的 AdANNS-OPQ 与使用刚性表示的 64 字节 OPQ 相比具有相同的准确性，成本减少了一半。