Abstract
Approximate Nearest-Neighbor Search (ANNS) efficiently finds data items whose embeddings are close to that of a given query in a high-dimensional space, aiming to balance accuracy with speed. Used in recommendation systems, image and video retrieval, natural language processing, and retrieval-augmented generation (RAG), ANNS algorithms such as IVFPQ, HNSW graphs, Annoy, and MRPT utilize graph, tree, clustering, and quantization techniques to navigate large vector spaces. Despite this progress, ANNS systems spend up to 99\% of query time to compute distances in their final refinement phase. In this paper, we present PANORAMA, a machine learning-driven approach that tackles the ANNS verification bottleneck through data-adaptive learned orthogonal transforms that facilitate the accretive refinement of distance bounds. Such transforms compact over 90\% of signal energy into the first half of dimensions, enabling early candidate pruning with partial distance computations. We integrate PANORAMA into state-of-the-art ANNS methods, namely IVFPQ/Flat, HNSW, MRPT, and Annoy, without index modification, using level-major memory layouts, SIMD-vectorized partial distance computations, and cache-aware access patterns. Experiments across diverse datasets -- from image-based CIFAR-10 and GIST to modern embedding spaces including OpenAI's Ada 2 and Large 3 -- demonstrate that PANORAMA affords a 2--30$\times$ end-to-end speedup with no recall loss.
Abstract (translated)
近似最近邻搜索（ANNS）能够在高维空间中高效地找到与给定查询嵌入接近的数据项，旨在平衡准确性和速度。该技术广泛应用于推荐系统、图像和视频检索、自然语言处理以及增强检索的生成模型（RAG）。ANNS算法如IVFPQ、HNSW图、Annoy和MRPT利用图、树、聚类及量化等方法在庞大的向量空间中导航。尽管取得了这些进展，ANNS系统仍需花费高达99%的查询时间来计算最终细化阶段的距离。 本文介绍了PANORAMA，这是一种基于机器学习的方法，通过数据自适应地学习正交变换来解决ANNS验证瓶颈问题，这种方法能够逐步精确距离界限。这些变换将超过90%的能量集中于前半部分维度，使得可以在进行部分距离计算时提前剔除候选对象。 我们将PANORAMA无缝集成到最先进的ANNS方法（包括IVFPQ/Flat、HNSW、MRPT和Annoy）中，无需修改索引，同时利用层级优先内存布局、SIMD向量化部分距离计算以及缓存感知访问模式。跨多种数据集的实验——从基于图像的CIFAR-10和GIST到包括OpenAI的Ada 2和Large 3在内的现代嵌入空间——表明PANORAMA能够在不损失召回率的情况下提供高达2至30倍的整体加速效果。
URL
https://arxiv.org/abs/2510.00566
