Variants of Beam Search for DiskANN

Viraj Agrawal, Kirankumar ShiragurarXiv 2026 · arXiv

Graph-based indices like DiskANN and HNSW have become the backbone of modern vector databases, powering everything from web search to Retrieval-Augmented Generation (RAG). At their heart, these systems rely on Beam Search to navigate high-dimensional space. However, most implementations treat every query the same, assigning a fixed "budget" regardless of whether a query is easy or hard.

In their recent paper, researchers from Microsoft Research India provide both a theoretical unification of beam search variants and a practical, learned "Beam Predictor" that significantly boosts search efficiency by adapting to query difficulty on the fly.

TL;DR

This paper unifies the theoretical guarantees for Adaptive Beam Search (ABS) on structured graphs and introduces Beam Predictor, a learned model that tailors search effort to individual queries. By running a short "pilot search" to estimate query difficulty, Beam Predictor reduces SSD query latency by up to 29.6% compared to classical methods while maintaining high recall.

What Problem Does This Paper Address?

Approximate Nearest Neighbor (ANN) search is a balancing act between recall (accuracy) and latency (speed). Graph-based methods navigate a dataset by jumping between neighboring points, getting closer to the query with each step.

There are two main ways to do this:

  1. Classical Beam Search (CBS): Uses a fixed "list size" ($L$). It keeps track of the $L$ best candidates found so far. Larger $L$ means better accuracy but more computation.
  2. Adaptive Beam Search (ABS): Uses a relaxation parameter to decide when to stop based on how much the results are still improving.

The Gap: Theoretically, we had guarantees for greedy search on specific graph types ($\alpha$-reachable graphs) and for ABS on "navigable" graphs, but no unified theory. Practically, CBS is inefficient because it spends the same amount of effort on an "easy" query (where the neighbor is obvious) as it does on a "hard" query (located in a crowded or complex region of the graph).

Methods

1. Theoretical Unification

The authors prove new approximation bounds for ABS on $\alpha$-reachable graphs (graphs where you can always find a neighbor that is closer to your target by a factor of $\alpha$). They show that ABS achieves a specific approximation factor for any metric and provide even tighter bounds for the standard Euclidean ($\ell_2$) metric on "sorted" graphs.

2. The Beam Predictor

The star of the practical side is the Beam Predictor. Instead of a fixed $L$ or a simple stopping rule, it uses a three-phase approach:

  • The Pilot: It starts a standard beam search with a small list size ($L=K$).
  • The Prediction: Once the pilot converges, the algorithm extracts features—like the distances of the top results and how quickly those distances dropped during the pilot (the "trajectory"). A linear regression model then predicts the optimal total list size ($\hat{L}$) needed to hit a target recall.
  • The Extension: The search doesn't restart; it simply resumes from where the pilot left off, but now with the expanded budget $\hat{L}$.

The model is trained offline by solving a "multiple-choice knapsack problem" using Lagrangian relaxation to find the most cost-effective distribution of search budgets across a training set.

Datasets

The authors evaluated their work on three massive 100-million-point benchmarks from the NeurIPS’21 Billion-Scale ANN Challenge:

  • SIFT100M: 128-dimensional vectors (image descriptors).
  • DEEP100M: 96-dimensional vectors (deep learning embeddings).
  • MSSpaceV100M: 100-dimensional vectors (search engine data).

Key Insights and Ideas

  • Query "DNA" in the Pilot: The most striking insight is that a very short pilot search contains enough information about the local graph topology to accurately predict how much more work is needed.
  • Trajectory Matters: It’s not just about how close you are to the query, but how fast you got there. If the distance sum of your top candidates drops off a cliff during the pilot, the query is likely "easy."
  • Global Optimization for Local Decisions: By training the predictor to minimize mean distance computations across a batch, the system learns to "steal" budget from easy queries to pay for the extra work required by hard ones.

Key Results

  • SSD Latency: On SSD-resident indices (where I/O is the bottleneck), Beam Predictor lowered mean query latency by up to 29.6% relative to CBS at the same recall level.
  • Computational Efficiency: In-memory, it required 1.3% to 23.7% fewer distance computations than CBS.
  • Scaling with K: As the number of requested neighbors ($K$) increases (e.g., from 100 to 500), the advantage of Beam Predictor over ABS actually grows, making it more robust for large-scale retrieval tasks.
  • Theoretical Tightness: The authors didn't just provide bounds; they provided specific examples showing their theoretical bounds are "tight" (the worst-case scenario actually happens).

Limitations and Future Work

  • Graph Assumptions: The theoretical guarantees rely on $\alpha$-reachability. While DiskANN's construction is inspired by this, practical, fast-built graphs aren't strictly proven to meet these criteria.
  • Tail Latency: Because the predictor gives "hard" queries a much larger budget, the 99.9th percentile latency can be higher than CBS. This might be a dealbreaker for systems with strict hard-latency SLAs.
  • Offline Overhead: The system requires an offline "sweep" of training queries to calibrate the model.
  • Future Directions: The authors suggest exploring how this predictor handles "out-of-distribution" queries (queries very different from the training set) and applying similar logic to other graph types like HNSW.

For more details, you can find the full paper titled "Variants of Beam Search for DiskANN" on arXiv (2611.26609v1).

Summary updated

Abstract

Graph-based data structures such as DiskANN, HNSW, and NSG constitute the state of the art for large-scale approximate nearest-neighbor (ANN) search. Indyk and Xu introduced the notion of $α$-reachable graphs, which include graphs built by DiskANN's slow-preprocessing construction, and proved that greedy search achieves an approximation factor of $\tfrac{α+1}{α-1}$. Independently, Al-Jazzazi et al. proposed adaptive beam search (ABS) with a relaxation parameter $γ> 0$, showing a $\tfrac{2}γ$ approximation on navigable graphs ($α\approx 1$), where greedy search admits no guarantees. In this work, we unify and generalize these results by proving that ABS with parameter $γ$ on $α$-reachable graphs achieves an approximation of $\tfrac{α+1}{α(γ+1)-1}$ for any metric. Moreover, on sorted $α$-reachable graphs (introduced by Gollapudi et al.) under the $\ell_2$ metric, we obtain the tighter bound $\max\bigl(\tfracα{α(γ+1)-1}, \tfrac{α^{2}+1}{α^{2}(γ+1)-1}\bigr)$. Beyond these theoretical results, we design a beam predictor using features inspired by fine-grained analysis of ABS, trained via a constrained objective that minimizes mean distance computations subject to a target recall. On three 100-million-point benchmarks, using graphs built by DiskANN's practical construction, beam predictor lowers mean query latency on SSD-resident indices at matched recall by up to $29.6\%$ relative to classical beam search (CBS). Relative to ABS, it is faster in $11$ of $15$ settings, by up to $6.5\%$, and at most $1.4\%$ slower in the other $4$; at $95\%$ recall, its advantage over ABS grows from $0.8$--$4.2\%$ for $100$ neighbors to $4.6$--$5.6\%$ for $500$ neighbors. In memory, it needs $1.3$--$23.7\%$ fewer distance computations than CBS and $0.0$--$3.9\%$ fewer than ABS.
BibTeX
@misc{agrawal2026variants,
  author = {Viraj Agrawal and Kirankumar Shiragur},
  title = {{Variants of Beam Search for DiskANN}},
  year = {2026},
  eprint = {2611.26609},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.26609},
}
Figure