Research map / Graph learning / Graph algorithms and clustering
Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
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 Adaptive Beam Search, which replaces beam-width termination with a distance-based stopping rule, and proves it returns approximate k-NN on navigable graphs while reducing distance computations versus beam search on HNSW, Vamana, NSG, and EFANNA graphs.
Problem
Graph-based approximate nearest neighbor search typically uses beam search with a fixed beam width as its termination rule, which lacks theoretical guarantees and does not adapt to query difficulty.
Approach
Decouple beam search into a search order and a stopping criterion, and replace the fixed beam-width stopping rule with a distance-based rule: stop when k discovered points satisfy (1+gamma)·d(q,j) ≤ d(q,x) for the expanded candidate x. Proven to return approximate k-NN whenever the graph is navigable.
Key results
- Adaptive Beam Search matches or beats standard beam search across navigable and heuristic graphs, with up to 30-40% fewer distance computations at fixed recall on navigable graphs.
- On heuristic graphs, Adaptive Beam Search sometimes gives more than a 2x reduction in distance computations, e.g., on MNIST.
- Theorem: on navigable graphs with gamma<=2, the returned set satisfies d(q,v) >= (gamma/2) max d(q,j) for all v outside the set; gamma=2 gives exact k-NN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace fixed beam-width termination with distance-adaptive termination | Graph-based nearest-neighbor search · Navigable graphs (SIFT1M, DEEP96, MNIST) | distance computations at fixed recall | Helped |
| Replace fixed beam-width termination with distance-adaptive termination | Graph-based nearest-neighbor search · Heuristic graphs (NSG, Vamana, EFANNA, HNSW) | distance computations at fixed recall | Helped |
| Use distance-adaptive termination instead of classic beam search | HNSW search · GIST, k = 1 | distance computations at fixed recall | Hurt |
| Replace the threshold (1+γ)·d_k with the more aggressive threshold d_1 + γ·d_k (ablation) | Adaptive Beam Search · Navigable graphs | distance computations at fixed recall | Hurt |
| Combine beam width b with distance slack γ in the stopping rule (ablation) | Adaptive Beam Search · Three datasets (hybrid-rule experiments) | distance computations at fixed recall | No clear effect |
Surprising findings
- Adaptive Beam Search V2 (threshold d1 + gamma*dk) underperforms standard beam search despite a natural-looking variant.
- Standard beam search on navigable graphs can fail to approximate nearest neighbors for any finite factor unless beam width is near n.
Limitations
- Theory guarantees solution quality but not worst-case runtime.
- Navigable graph experiments limited to subsamples (100K points) due to expensive pruning, which scales at least quadratically with n.
- Adaptive Beam Search can underperform on GIST with k=1 on HNSW graphs.
Experimental setup
Datasets: MNIST SIFT1M DEEP96 DEEP256 GloVe GIST
Benchmarks: MNIST SIFT1M DEEP96 DEEP256 GloVe GIST
Metrics: recall distance computations per query
Baselines: standard beam search classic greedy search Adaptive Beam Search V2 HNSW Vamana NSG EFANNA
Builds on: HNSW Vamana NSG beam search Indyk and Xu shortcut reachability
Closest papers by meaning
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.88)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.88)
- Prune, Don’t Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search (NeurIPS 2026 · similarity 0.86)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.85)
- 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)
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.