Beam Search

The beam width (k) is the algorithm's primary hyperparameter, defining the number of most promising partial sequences (or nodes) retained at each step of the search. This creates a memory- and compute-efficient approximation of breadth-first search.

• k=1: Equivalent to a greedy search, following the single best option at each step.
• k=n (full breadth): Equivalent to exhaustive breadth-first search, exploring all possibilities but at high computational cost.
• Typical values: Range from 4 to 10 for tasks like machine translation or text summarization, providing a practical trade-off between quality and speed.

At each decoding step, Beam Search performs a pruning operation. It generates all possible next-step extensions for the k sequences in the current beam, scores them (e.g., using log probabilities), and then selects only the top-k highest-scoring sequences to form the new beam. All other candidates are permanently discarded.

This selective pruning is what differentiates it from best-first search algorithms that maintain a global priority queue, making Beam Search far more memory-efficient for long sequences common in natural language generation.

Beam Search offers a predictable computational profile, making it suitable for production systems.

• Time Complexity: Approximately O(k * V * T), where k is the beam width, V is the vocabulary size (for language models), and T is the target sequence length. This is a dramatic reduction from the exponential complexity of exploring all possible sequences.
• Space Complexity: O(k * T), as the algorithm must store the k candidate sequences, each of length up to T. This is its key advantage over breadth-first search, which has a space complexity that grows exponentially with depth.

Beam Search typically terminates when all k candidate sequences in the beam have reached an end-of-sequence token or when a predefined maximum length T is reached. The final output is selected from the completed sequences in the beam.

The standard selection criterion is the sequence with the highest cumulative score, often the sum of log probabilities. However, this can favor shorter sequences. Length normalization (dividing the score by sequence length) is a common technique to correct for this bias and is critical for comparing sequences of different lengths.

Beam Search occupies a strategic middle ground between other fundamental search strategies.

• vs. Greedy Decoding (k=1): Greedy search is faster but can commit to a suboptimal early token, leading to locally optimal but globally poor sequences (a greedy trap). Beam Search maintains multiple hypotheses, offering a chance to recover from early mistakes.
• vs. Breadth-First Search (BFS): BFS is guaranteed to find the optimal sequence but is computationally infeasible for large state spaces (like language model vocabularies). Beam Search provides a bounded approximation of BFS, trading optimality guarantees for tractability.

Beam Search is the de facto standard decoding algorithm for autoregressive sequence generation tasks where quality is prioritized over pure speed. Its core application is guiding large language models (LLMs) and sequence-to-sequence models.

Common Applications:

• Machine Translation (e.g., Google's Neural Machine Translation systems)
• Text Summarization
• Image Captioning
• Speech Recognition (decoding over phoneme or word sequences)
• Code Generation

It is less suitable for tasks requiring highly diverse outputs or creative exploration, where sampling-based methods (like top-k or nucleus sampling) are often preferred.

A search algorithm that expands the node deemed closest to the goal based solely on a heuristic function h(n). It prioritizes immediate promise without considering the path cost incurred to reach the node. This makes it fast but often suboptimal and prone to getting stuck, as it lacks the cumulative cost consideration of algorithms like A* or the breadth consideration of Beam Search.

• Core Mechanism: Always expands the node with the lowest heuristic value.
• Trade-off: Extreme speed for potential loss of optimality.
• Relation to Beam Search: Beam Search with a beam width of k=1 is equivalent to Greedy Best-First Search, as it only keeps the single most promising node at each depth level.

A graph traversal algorithm that explores all nodes at the present depth level before moving to the next level. It uses a queue to manage the frontier and guarantees finding the shortest path in an unweighted graph. Its primary limitation is memory consumption, as it stores all nodes at the current frontier, which grows exponentially with depth.

• Exhaustive Nature: Systematically explores all possibilities level by level.
• Memory Complexity: O(b^d), where b is branching factor, d is depth.
• Relation to Beam Search: Beam Search is a memory-constrained approximation of BFS. Instead of keeping all nodes at a level, it prunes all but the top-k (the beam width), trading completeness and optimality guarantees for tractability.

The hyperparameter k that defines the core constraint of the Beam Search algorithm. It is the maximum number of most promising nodes (the "beam") retained for expansion at each step or depth level of the search. This parameter directly controls the trade-off between search quality and computational cost.

• Small k (e.g., 1-10): Highly memory and compute efficient, but risks pruning the globally optimal path early ("search error").
• Large k: Approximates breadth-first search, improving solution quality at the cost of increased memory (O(k)) and time (O(k * b)).
• Tuning Context: In sequence generation (e.g., machine translation), typical values range from 4 to 10. In complex planning, it may be tuned based on available compute.

A general technique in search and optimization algorithms to eliminate branches or nodes from consideration that are deemed unlikely to be part of an optimal solution. This reduces the effective size of the search space, making exploration tractable.

• Beam Search Pruning: At each step, all generated successor nodes are scored (e.g., by a heuristic or model probability). Only the top-k are kept; the rest are permanently discarded.
• Contrast with Alpha-Beta Pruning: Used in game trees (Minimax), where branches are cut because they cannot affect the final decision, guaranteeing the same result as an exhaustive search.
• Key Insight: Beam Search uses aggressive, heuristic-based pruning that sacrifices guarantees for efficiency, unlike optimal pruning methods.

A dynamic programming algorithm for finding the most likely sequence of hidden states (the Viterbi path) in a Hidden Markov Model (HMM). It efficiently computes the optimal path through a trellis diagram by maintaining the maximum probability path to each state at each time step.

• Optimality Guarantee: Finds the single globally optimal sequence.
• Mechanism: Uses dynamic programming to avoid recomputation, storing backpointers.
• Relation to Beam Search: Beam Search is often viewed as an approximation of the Viterbi algorithm for models where the state space is too large (e.g., neural sequence models). Instead of keeping paths to all states, Beam Search keeps only the top-k paths, offering a tractable but potentially suboptimal alternative.

A variant of Beam Search where the k best states are selected from the entire set of successors generated by all current beam states, not just within independent depth levels. It operates more like a parallel, stochastic hill-climbing search.

• Mechanism: Generate successors from all k current states. From the combined pool, select the k best unique states as the next beam. Repeat.
• Contrast with Standard (Global) Beam Search: Standard Beam Search progresses depth-by-depth, akin to a level-synchronous search. Local Beam Search is asynchronous and can "jump" between branches more freely.
• Use Case: Often applied in optimization and constraint satisfaction problems where a strict sequence length isn't defined, unlike in sequence generation tasks.