TL;DR
Graph-based approximate nearest neighbor (ANN) search algorithms like HNSW and DiskANN are highly popular but rely on a fixed "beam width" stopping criterion that lacks theoretical guarantees and fails to adapt to query difficulty. This paper introduces Adaptive Beam Search, which replaces fixed widths with a distance-based termination condition. This simple change provides the first provable approximation guarantees on navigable graphs while reducing distance computations by 10% to 50% in practical applications.
What Problem Does This Paper Address?
Searching for the nearest neighbors of a query point in high-dimensional space is a foundational task for vector databases, retrieval-augmented generation (RAG) for LLMs, and recommendation systems. Modern state-of-the-art methods build a directed graph over the dataset and traverse it using beam search—maintaining a set of $b$ closest candidates and exploring their neighbors greedily.
However, standard beam search suffers from a significant theory-practice gap:
- Lack of Theoretical Guarantees: Even if a graph is perfectly "navigable" (meaning a path always exists where distance to any target strictly decreases), standard beam search with a fixed beam width can get stuck and completely fail to find the true nearest neighbors.
- Rigid Stopping Criteria: Using a fixed beam width ($b$) means the algorithm spends the same structural budget on "easy" queries as it does on "hard" queries, leading to computational inefficiency.
The authors set out to design a principled stopping rule that connects graph navigability to search accuracy while improving real-world search efficiency.
Methods
The authors propose a decoupled view of beam search, separating the search order (how the graph is traversed) from the termination condition (when to stop).
Instead of stopping when a fixed number of candidates $b$ have been evaluated, Adaptive Beam Search introduces a distance-based slack parameter $\gamma \ge 0$. The search terminates only when the next closest node $x$ lined up for expansion is significantly further away from the query $q$ than the $k$-th best candidate discovered so far. Specifically, it stops if:
$$d(q, x) \ge (1 + \gamma) \cdot d(q, j_k)$$
Where $j_k$ is the $k$-th closest point found so far.
Theoretical Guarantee
The core mathematical contribution (Theorem 1) proves that if the underlying graph is navigable, Adaptive Beam Search is guaranteed to return a set of points where no missed point is closer to the query than the returned points by more than a factor of $2/\gamma$. When $\gamma = 2$, it is guaranteed to solve the exact $k$-nearest neighbor problem perfectly. Conversely, they prove that standard beam search can fail entirely under the same conditions.
Datasets
The method was evaluated using six standard high-dimensional vector search benchmarks:
- MNIST: 60k handwritten digit images (784 dimensions)
- SIFT1M: 1M image descriptor vectors (128 dimensions)
- DEEP96 / DEEP256: 1M deep learning embedding vectors (96 and 256 dimensions)
- GloVe: 1M text word embeddings (200 dimensions)
- GIST: 1M image feature vectors (960 dimensions)
Experiments were conducted on both truly navigable graphs (constructed using randomized methods and pruned via a custom algorithm) and popular heuristic graphs used in production (HNSW, Vamana/DiskANN, NSG, and EFANNA).
Key Insights and Ideas
- Navigability $\neq$ Beam Search Success: A graph being navigable ensures that greedy routing ($b=1$) works if the target is at distance 0, but standard beam search ($b > 1$) can easily bypass the true nearest neighbor if it gets distracted by a cluster of "false friends" that look closer early on.
- Dynamic Query Adaptivity: By tying termination to distance rather than a count element, the algorithm naturally adapts to query difficulty. For an "easy" query with isolated, highly distinct neighbors, it stops almost immediately. For a "hard" query surrounded by ambiguous points, it automatically expands its search radius.
Key Results
- 10% to 50% Computation Reduction: Across various recall targets, datasets, and graph types, Adaptive Beam Search consistently outperformed standard beam search, requiring significantly fewer distance computations to achieve the same accuracy.
- Robustness Across Graph Types: The performance gains were not limited to theoretical navigable graphs; they translated directly to heuristic production graphs like HNSW and Vamana.
- Drop-in Feasibility: Because the method only alters the
ifstatement determining when the search loop breaks, it can be integrated into existing vector search libraries with minimal code modifications.
Limitations and Future Work
- High Pruning Complexity: To test truly navigable graphs at practical sparsity levels, the authors designed a custom pruning algorithm. However, its runtime scales quadratically ($O(n^2)$) with the dataset size, meaning they could only construct truly navigable graphs for subsamples of up to 100,000 points.
- Priority Queue Overhead: While distance computations dominate search time in high dimensions, highly aggressive adaptive rules can sometimes add minor bookkeeping overhead to candidate queues, which warrants further engineering optimization.
- Hybrid Rules: Initial explorations into combining both fixed-width and distance-based constraints (hybrid rules) performed similarly to Adaptive Beam Search, but the authors note that more optimal combinations may exist.
Summary updated