Research map / Learning theory and algorithms / Sample complexity
Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs
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.
Introduces sorted α-reachable graphs to tighten worst-case approximation guarantees for DiskANN on Euclidean metrics (α/(α−1)) and gives the first worst-case analysis of beam search for k>1 nearest neighbors, with experiments on sorted vs unsorted DiskANN.
Problem
Worst-case guarantees for graph-based approximate nearest-neighbor search are known only for DiskANN with greedy search (approximation (α+1)/(α−1) for any metric), and nothing is proven for beam search returning k>1 candidates.
Approach
Exploit the sorting step in DiskANN's pruning (closest remaining candidate chosen first) to define sorted α-reachability, which adds the constraint D(v,t) ≤ D(v,a); combined with Euclidean geometry (SDP duality) this improves the approximation to α/(α−1), and the analysis is extended to beam search.
Key results
- Sorted DiskANN approximation bound improves from (α+1)/(α−1) to α/(α−1) for Euclidean metrics (e.g., ratio 3 to 2 at α=2).
- Sorted index achieves 5%, 8%, and 7.5% higher QPS on SIFT1M (99% recall), OpenAI (90% recall), and SPACEV (95% recall).
- Sorted index uses 10% fewer distance comparisons on SIFT1M, 6% on OpenAI, and 18% on SPACEV; unsorted graphs have 6–25% higher average degree.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Sort candidate neighbors before pruning (ablation) | DiskANN · SIFT1M (at 99% recall) | QPS: 5% higher QPS | Helped |
| Sort candidate neighbors before pruning (ablation) | DiskANN · OpenAI (at 90% recall) | QPS: 8% higher QPS | Helped |
| Sort candidate neighbors before pruning (ablation) | DiskANN · SPACEV (at 95% recall) | QPS: 7.5% higher QPS | Helped |
| Sort candidate neighbors before pruning (ablation) | DiskANN · SIFT1M (at 99.9% recall) | average distance comparisons: 10% fewer comparisons | Helped |
| Sort candidate neighbors before pruning (ablation) | DiskANN · OpenAI (at 90% recall) | average distance comparisons: 6% fewer | Helped |
| Sort candidate neighbors before pruning (ablation) | DiskANN · SPACEV (at 95% recall) | average distance comparisons: 18% fewer | Helped |
| Sort candidate neighbors before pruning (ablation) | DiskANN · OpenAI | mean max approximation ratio: worse by 25% on OpenAI (at a 1.008 approx. ratio) | Hurt |
| Sort candidate neighbors before pruning (ablation) | DiskANN · SIFT1M | mean max approximation ratio: better by 9% on SIFT (at a 1.001 approx. ratio) | Helped |
| Sort candidate neighbors before pruning (ablation) | DiskANN · SPACEV | mean max approximation ratio: 17% on SPACEV (at a 1.020 approx. ratio) | Helped |
| Sort candidate neighbors before pruning (ablation) | DiskANN disk-based index · SPACEV | 100@100 recall: approximately a 0.5% improved recall | Helped |
Surprising findings
- Improving either the Euclidean metric assumption or the sorting alone does not improve the bound; only their combination does.
- On the mean max approximation ratio metric, the sorted index is worse on OpenAI (25% worse at 1.008 ratio), contrary to its advantage elsewhere.
Limitations
- Improved bounds are proven only for Euclidean ℓ2; general metrics retain the (α+1)/(α−1) bound.
- Empirical study compares only sorted vs unsorted fast-preprocessing DiskANN; the theory covers slow-preprocessing graphs.
- Some datasets (OpenAI approximation ratio, Wikipedia) show mixed or unexplained results that are left for future work.
Experimental setup
Datasets: SIFT1M OpenAI embeddings (Arxiv abstracts) Cohere Wikipedia embeddings Microsoft SPACEV
Benchmarks: SIFT1M OpenAI Wikipedia SPACEV
Metrics: Recall100@100 QPS average distance comparisons mean max approximation ratio disk IOs build time average degree
Baselines: unsorted DiskANN Indyk & Xu (2024) bound
Builds on: DiskANN alpha-reachable graphs (Indyk & Xu)
Closest papers by meaning
- Prune, Don’t Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search (NeurIPS 2026 · similarity 0.92)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.88)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.87)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.87)
- Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search (NeurIPS 2025 · similarity 0.86)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.