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:
- 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.
- 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