Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search

Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, Torsten Suel

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:

  1. 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.
  2. 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.

Counterexample showing standard beam search failure

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.
Query difficulty adaptivity shown via flatter histograms

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 if statement 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

Abstract

Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have become popular thanks to their empirical accuracy and efficiency. These methods construct a directed graph over the dataset and perform beam search on the graph to find nodes close to a given query. While significant work has focused on practical refinements and theoretical understanding of graph-based methods, many questions remain. We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width. We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem, establishing a connection between navigability and the performance of graph-based search. We also provide extensive experiments on our new termination condition for both navigable graphs and approximately navigable graphs used in practice, such as HNSW and Vamana graphs. We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors. It thus provides a simple and practical way to improve the performance of popular methods.
BibTeX
@inproceedings{aljazzazi2025distance,
  author = {Yousef Al-Jazzazi and Haya Diwan and Jinrui Gou and Cameron Musco and Christopher Musco and Torsten Suel},
  title = {{Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=wORrUUmffG},
}
Figure