Prune, Don’t Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search

Over the past decade, graph-based approximate nearest neighbor (ANN) algorithms, such as DiskANN (Jayaram Subramanya et al., 2019) and HNSW (Malkov & Yashunin, 2018), have demonstrated state-of-the-art empirical performance. Recent theoretical works (Indyk & Xu, 2023; Gollapudi et al., 2025) introduce the framework of $\alpha$-reachability to obtain worst-case performance guarantees for DiskANN; here, the reachability parameter $\alpha$ gives a trade-off between construction time, query time, and accuracy. In this work, we propose RP-TUNING, an efficient and simple post-hoc algorithm, based on DiskANN's pruning step, and show that (1) Theoretically, efficiently adjusting the reachability of an $\alpha$-reachable graph is possible via pruning: RP-TUNING preserves worst-case reachability guarantees in general metrics and improved guarantees in Euclidean metrics. (2) Empirically, RP-TUNING accelerates DiskANN tuning on four datasets by up to 73$\times$ with varied performance trade-offs compared to fully rebuilt graphs.