Beam Search

The beam width (B) is the algorithm's core hyperparameter, defining the size of the priority queue (the "beam"). It controls the fundamental trade-off between search quality and speed.

• A larger beam width explores more candidate nodes per step, increasing the probability of finding the true nearest neighbors (higher recall) but at a higher computational cost.
• A smaller beam width is more aggressive in pruning the search space, leading to faster queries but a higher risk of getting trapped in a local minimum of the graph, potentially missing better neighbors. In practice, beam width is tuned based on latency requirements and desired recall levels for the application.

At each step of the traversal, beam search maintains a min-heap or max-heap priority queue (depending on the distance metric) containing the B most promising nodes discovered so far.

• The queue is initialized with one or more entry points into the graph.
• For each node in the current beam, its neighbors are examined, and their distances to the query vector are computed.
• All candidate neighbors are pooled, and only the top-B closest nodes are retained to form the beam for the next iteration. This iterative refinement ensures the search progressively focuses on the region of the graph most likely to contain the nearest neighbors.

The search terminates when no new, closer nodes are found, indicating convergence. Common stopping criteria include:

• No improvement: The set of nodes in the beam remains unchanged between iterations.
• Maximum iterations: A predefined limit on the number of search steps to prevent excessive traversal, especially in large or dense graphs.
• Distance threshold: Stopping when the distance of the farthest node in the beam is below a certain threshold, indicating high confidence in the results. Upon termination, the nodes in the final beam are returned as the approximate nearest neighbors.

Beam search generalizes two simpler graph traversal strategies:

• Greedy Search (Beam Width = 1): At each step, only the single closest neighbor to the query is selected for expansion. This is highly efficient but highly prone to following a suboptimal path and missing the global nearest neighbors.
• Exhaustive Search (Beam Width = N): The beam encompasses the entire dataset, guaranteeing an exact result but requiring linear time complexity, defeating the purpose of ANN. Beam search operates in the middle ground, using a beam width 1 < B << N to mitigate the myopia of greedy search while maintaining sub-linear time complexity.

Beam search is the core traversal algorithm used in the Hierarchical Navigable Small World (HNSW) index, one of the most popular graph-based ANN methods.

• In HNSW, search begins at a high layer of the graph with long-range connections, using a small beam width for fast, coarse navigation.
• As the search descends to lower, denser layers, the beam width is often increased to refine the search in the localized neighborhood.
• This layered application of beam search is key to HNSW achieving its logarithmic time complexity for high-recall queries.

Implementing beam search involves balancing several performance dimensions:

• Recall vs. Latency: The primary trade-off governed by beam width. Higher recall requires a wider beam and more distance computations.
• Graph Quality Dependency: The effectiveness of beam search is heavily dependent on the underlying graph's construction. A well-built graph (e.g., with good small-world properties) allows a narrower beam to achieve high recall.
• Memory Overhead: Maintaining the beam and candidate lists requires O(B) memory per query, which is negligible compared to index size but must be considered for highly concurrent systems. Tuning involves benchmarking recall@K and query latency across a range of beam widths for a representative query set.

In Hierarchical Navigable Small World (HNSW) and other graph-based ANN indices, beam search is the core traversal algorithm. It explores the graph from entry points by:

• Maintaining a dynamic candidate list (the beam) of the most promising nodes to visit next, ranked by distance to the query.
• Iteratively expanding the beam's neighbors, pruning the list to a fixed width B (beam width).
• This balances exploration (visiting new regions) with efficiency, preventing the exponential growth of a naive breadth-first search while achieving high recall with sub-linear time complexity.

Beam search is a standard decoding algorithm for autoregressive models like Large Language Models (LLMs) when generating text, code, or other sequences.

• Instead of greedily choosing the single next most likely token, it keeps the top-B most probable partial sequences (hypotheses) at each step.
• It scores sequences using the log probability of the sequence given the model.
• This allows the model to recover from potential early errors made by a greedy approach, producing more fluent and higher-quality outputs, especially for tasks like machine translation, summarization, and code completion.

In Automatic Speech Recognition (ASR) systems, beam search decodes acoustic feature sequences into text.

• The search space is a weighted finite-state transducer (WFST) that combines an acoustic model, a pronunciation lexicon, and a language model.
• The beam prunes unlikely partial word hypotheses at each time step, managing the massive combinatorial space.
• This application is critical for real-time systems, where search latency and accuracy are paramount. Modern end-to-end models like RNN-T also rely on beam search for efficient decoding.

Historically foundational, beam search was the dominant decoding algorithm for statistical machine translation (SMT) and remains crucial for neural machine translation (NMT).

• It searches through possible translations by sequentially adding target language words.
• The beam maintains several partial translation hypotheses, scoring them with a combination of model probabilities (the translation model) and a language model for fluency.
• The algorithm must handle reordering between languages (a major search challenge) and often incorporates length normalization to avoid bias towards shorter outputs.

In robotics and game AI, beam search is applied to action planning and pathfinding in large state spaces.

• Each node represents a state (e.g., a robot's configuration, a game board), and edges represent possible actions.
• The beam width controls computational cost, allowing for real-time planning.
• It is particularly useful when a cost function or heuristic can guide the search, but the state space is too large for exhaustive methods like A*. This makes it applicable for non-player character (NPC) behavior and logistics optimization.

Beam search can solve combinatorial optimization problems like scheduling, routing, and certain types of protein folding.

• Solutions are constructed incrementally (e.g., assigning a time slot to a task, placing the next amino acid).
• A heuristic function evaluates partial solutions, and the beam retains the most promising ones.
• While not guaranteed to find the global optimum, it provides a high-quality approximate solution with predictable, controllable runtime, which is often necessary for NP-hard problems. It trades off against more exhaustive methods like branch and bound.

A graph-based index is a data structure for approximate nearest neighbor search where vectors are represented as nodes, and edges connect neighboring vectors. Search proceeds via greedy traversal from entry points.

• Core Mechanism: Algorithms like HNSW construct a graph where similar vectors are linked, enabling fast hop-by-hop navigation.
• Beam Search Role: Beam search is the primary traversal algorithm used on these graphs, maintaining a fixed-size priority queue (the beam) of candidate nodes to explore next.
• Trade-off: Balances exploration (visiting new candidates) with efficiency (limiting queue size) to achieve sub-linear search times.

Hierarchical Navigable Small World (HNSW) is a state-of-the-art graph-based ANN algorithm. It constructs a multi-layered graph where higher layers have long-range connections for fast navigation, and lower layers have dense connections for high accuracy.

• Beam Search Integration: The search process on an HNSW graph is a canonical application of beam search. At each layer, the algorithm uses a beam to select the most promising neighbors to explore further.
• Performance: Provides logarithmic time complexity for search, making it a preferred choice for high-recall, low-latency applications in vector databases like Weaviate and Qdrant.

The recall-precision trade-off in ANN search describes the inverse relationship between the completeness of results (recall) and system performance metrics like speed and resource usage.

• Beam Width Parameter: In beam search, the beam width (k) directly controls this trade-off. A larger beam explores more candidates per step, increasing recall but also search latency and compute cost.
• Engineering Decision: Tuning the beam width is a critical optimization for production systems. A common heuristic is to set it proportional to the logarithm of the graph size to balance effectiveness and efficiency.

Greedy search is a simplified graph traversal strategy where, at each step, the algorithm moves to the single neighbor that is closest to the query vector. It does not maintain a beam or explore multiple paths concurrently.

• Comparison to Beam Search: Beam search generalizes greedy search. Greedy search is equivalent to beam search with a beam width of 1.
• Limitation: Greedy search is highly susceptible to local minima. It can get trapped in a suboptimal region of the graph, leading to poor recall. Beam search mitigates this by keeping multiple candidates alive.

Sublinear time complexity describes an algorithm whose runtime grows slower than linearly with the size of the dataset (e.g., O(log N)). This is the fundamental goal of all ANN algorithms.

• Beam Search's Contribution: By restricting the search to a fixed number of paths (the beam width) and leveraging a well-constructed graph, beam search enables query times that are logarithmic in the number of vectors, not linear.
• Practical Impact: This is what allows billion-scale vector databases to return results in milliseconds, as the search explores only a tiny, guided fraction of the total dataset.

Best-First Search is a family of informed search algorithms that use a heuristic function to estimate the cost to the goal. A search* is a famous variant that combines the cost incurred so far with a heuristic estimate of the remaining cost.

• Conceptual Relationship: Beam search is a bounded, best-first search. It expands nodes based on a priority (distance to query) but is constrained by the beam width, not by an explicit heuristic goal cost.
• Key Difference: A* aims for an optimal path to a defined goal state. Beam search in ANN has no single "goal" but seeks to find the k closest vectors in an unbounded graph, making pure A* less applicable.