Research map / Graph learning / Graph algorithms and clustering

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

NeurIPS 2026 · Graph learning › Graph algorithms and clustering · approach: Graph comparison and random features

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes RP-Tuning, a post-hoc pruning of an alpha1-reachable DiskANN graph with RobustPrune at a smaller alpha2, giving worst-case reachability bounds in general and Euclidean metrics and up to 43x faster tuning than rebuilding on four BigANN datasets.

Problem

Tuning DiskANN's reachability parameter alpha requires rebuilding the index for each value, which is prohibitively expensive at scale; the worst-case guarantees of pruning an existing alpha-reachable graph are unknown.

Approach

Re-apply RobustPrune with a new smaller alpha to an existing alpha1-reachable graph (RP-Tuning), and derive tight worst-case reachability for unsorted and sorted neighbor pruning in general and Euclidean metrics, with sorted Euclidean giving the best bound via an SDP-based analysis.

Key results

• RP-Tuning tuning is up to 43x faster than rebuilding on GIST-1M (total across alpha=1.01,1.05,1.10), with 14x on SIFT1M and 13x on DEEP1M.
• Pruned indices from a base alpha=1.2 graph show superior recall-QPS trade-offs compared to rebuilt indices at the same alpha across all four datasets.
• Worst-case reachability after pruning is 1/(1/a1+1/a2) for sorted general metrics and a tighter Euclidean expression via SDP, e.g. about 1.226 vs 1.2 at a1=3, a2=2.

Surprising findings

• Pruned graphs can have vacuous worst-case reachability (below 1) in theory yet still outperform rebuilt indices empirically.
• Rebuilding with small alpha on SIFT1M yields indices where larger beam size reduces both QPS and recall.

Limitations

• Worst-case reachability after pruning can be below the target alpha2 and even below 1, so theory does not guarantee the empirical gains.
• Experiments use Vamana heuristics in Python with a fixed base alpha=1.2 and only Euclidean datasets.
• Hardware is a single cloud CPU instance; no GPU or distributed evaluation.

Experimental setup

Datasets: SIFT-1M GIST-1M Deep-1M MSSPACEV-1M

Benchmarks: SIFT-1M GIST-1M Deep-1M MSSPACEV-1M

Metrics: recall@100 QPS runtime speedup

Baselines: DiskANN rebuild at alpha=1.1, 1.05, 1.01

Builds on: DiskANN RobustPrune alpha-reachability framework

Closest papers by meaning

• Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.92)
• Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.86)
• Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search (ICML 2024 · similarity 0.85)
• CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.85)
• Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.85)
• Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.85)