不重建索引就能快速调整向量搜索参数，提升效率43倍。
Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search
- 基于剪枝机制动态调整搜索参数α，无需重新构建索引。
- 在四个公开数据集上实现最高43倍的调优加速，几乎无额外开销。
- 适用于大规模向量数据库，尤其适合需要频繁调参的场景。
向量相似性搜索是现代人工智能与机器学习应用中的核心操作。多数向量数据库采用基于图的近似最近邻（ANN）搜索算法，如DiskANN（Subramanya等，2019），其在实际性能上表现卓越。DiskANN的图结构由可达性参数α控制，该参数在构建时间、查询时间和准确性之间存在权衡。然而，自适应调节此权衡通常需要为不同α值重建索引，这在大规模场景下代价高昂。本文提出RP-Tuning，一种基于DiskANN剪枝步骤的高效事后调参方法，可在不重建完整索引的情况下调整α参数。在先前理论工作（Indyk和Xu，2023；Gollapudi等，2025）的α-可达性框架下，我们证明：通过RP-Tuning剪枝初始α-可达图，能在一般度量空间中保持最坏情况下的可达性保证，在欧氏空间中可获得更优保证。实验表明，RP-Tuning在四个公开数据集上使DiskANN的调优速度提升高达43倍，且开销可忽略不计。
原文摘要 · Abstract (English)
Vector similarity search is an essential primitive in modern AI and ML applications. Most vector databases adopt graph-based approximate nearest neighbor (ANN) search algorithms, such as DiskANN (Subramanya et al., 2019), which have demonstrated state-of-the-art empirical performance. DiskANN's graph construction is governed by a reachability parameter $α$, which gives a trade-off between construction time, query time, and accuracy. However, adaptively tuning this trade-off typically requires rebuilding the index for different $α$ values, which is prohibitive at scale. In this work, we propose RP-Tuning, an efficient post-hoc routine, based on DiskANN's pruning step, to adjust the $α$ parameter without reconstructing the full index. Within the $α$-reachability framework of prior theoretical works (Indyk and Xu, 2023; Gollapudi et al., 2025), we prove that pruning an initially $α$-reachable graph with RP-Tuning preserves worst-case reachability guarantees in general metrics and improved guarantees in Euclidean metrics. Empirically, we show that RP-Tuning accelerates DiskANN tuning on four public datasets by up to $43\times$ with negligible overhead.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。