Beam Search

The algorithm maintains exactly k candidate sequences at each decoding step, where k is the beam width. After expanding all possible next tokens for each candidate, the top-k highest-scoring sequences are retained and the rest are pruned. This parameter directly controls the trade-off between accuracy and computational cost:

• k=1: Equivalent to greedy search—fast but prone to error propagation
• k=5-10: Standard for neural machine translation, balancing quality and speed
• k=50+: Used in dependency parsing to avoid losing correct but initially low-probability arcs

The fixed budget ensures linear time complexity O(k × n × |V|) where n is sequence length and |V| is vocabulary size, making it tractable for real-time applications.

Beam search ranks partial hypotheses using cumulative log-probability scores rather than raw probabilities. This prevents numerical underflow when multiplying many small probability values together. The score for a partial sequence y₁...yₜ is:

codeCopy
score(y₁...yₜ) = Σᵢ₌₁ᵗ log P(yᵢ | y₁...yᵢ₋₁, x)

A critical implementation detail is length normalization, which divides the cumulative score by a length penalty factor to prevent the algorithm from favoring shorter sequences. Without normalization, beam search exhibits a well-known length bias—preferring shorter hypotheses because each additional token reduces the cumulative probability.

Standard beam search suffers from hypothesis convergence, where the top-k candidates become near-identical after a few decoding steps, differing only in the final few tokens. This reduces the effective search diversity and can cause the algorithm to miss globally optimal solutions.

Mitigation strategies include:

• Diverse beam search: Adds a dissimilarity penalty between sibling hypotheses to encourage exploration of distinct syntactic structures
• Stochastic beam search: Samples candidates from the top-k distribution rather than deterministically selecting the highest-scoring ones
• Coverage mechanisms: Penalize tokens that have received attention in previous steps to reduce repetition

In dependency parsing, this diversity is critical for maintaining alternative attachment decisions for prepositional phrases and relative clauses.

In transition-based dependency parsing, beam search mitigates the error propagation inherent in greedy shift-reduce decisions. At each parser state, instead of committing to a single action (SHIFT, LEFT-ARC, RIGHT-ARC), the algorithm maintains k parallel parser states with their respective stacks and buffers.

Key implementation details:

• State representation: Each beam element tracks its own stack, buffer, and partial dependency arcs
• Action expansion: All valid transitions are applied to each state, generating k × |actions| candidates
• State merging: Identical parser states from different histories are merged to avoid redundant computation
• Dynamic oracle training: Enables exploration of non-gold states during learning, teaching the parser to recover from suboptimal beam positions

This approach allows the parser to delay attachment decisions until disambiguating context is observed, significantly improving Labeled Attachment Score (LAS).

Beam search efficiency can be improved through aggressive pruning heuristics that eliminate candidates unlikely to recover:

• Relative threshold pruning: Discard any hypothesis whose score falls below the current best score minus a threshold δ
• Top-k within threshold: Keep only the top-k candidates that are within the relative threshold
• Histogram pruning: Group candidates by score buckets and keep only the top candidates per bucket

For sequence generation tasks, early stopping occurs when a complete hypothesis (ending with an end-of-sequence token) achieves a score that no incomplete hypothesis can surpass, even with maximally optimistic future scores. This guarantees optimality without exploring the full search space.

Beam search occupies a middle ground in the search strategy spectrum:

• Greedy search: Selects only the single best action at each step. Fastest (O(n)) but cannot recover from early mistakes. Used when latency is critical.
• Beam search: Maintains k hypotheses. Balances speed and accuracy. The de facto standard for neural sequence generation.
• Viterbi decoding: Finds the exact maximum-probability sequence via dynamic programming. Optimal but only tractable for models with Markov assumptions and small state spaces.
• A search*: Uses an admissible heuristic to guide exploration toward the goal. Can be optimal if the heuristic is admissible, but requires a well-defined goal state and heuristic function.

For neural models without Markov structure, beam search provides the best practical trade-off between optimality guarantees and computational feasibility.

Beam search is the standard decoding strategy for sequence-to-sequence models. Instead of selecting the single most probable token at each time step, the decoder maintains k candidate translations. At each step, the model expands all k hypotheses by the top k tokens, scores the resulting k² sequences, and prunes back to the top k to prevent exponential explosion.

• Typical beam width: 4 to 8 for translation
• Mitigates the exposure bias of greedy decoding
• Often combined with length normalization to avoid favoring short sequences

Modern end-to-end ASR systems use beam search to decode acoustic model outputs into text. The algorithm integrates the acoustic model, pronunciation lexicon, and language model into a unified search graph. The beam prunes unlikely phoneme sequences early, keeping computation tractable.

• Weighted Finite State Transducers compose the search space
• External language models are integrated via shallow fusion
• Beam width is dynamically adjusted based on pruning thresholds

In transition-based dependency parsing, beam search mitigates the error propagation inherent in greedy shift-reduce algorithms. At each parser state, the model scores all valid actions and retains the top k partial parse trees. This allows the parser to explore alternative attachment decisions before committing.

• Enables recovery from garden-path sentences
• Used with dynamic oracles to explore non-gold states
• Balances linear time complexity with improved accuracy

Visual captioning models use beam search to generate fluent, contextually relevant descriptions. The algorithm explores multiple narrative paths simultaneously, preventing the model from committing to a generic opening phrase that leads to a suboptimal caption.

• Beam width of 3 to 5 is common
• Combined with CIDEr optimization for task-specific scoring
• Prevents premature commitment to high-frequency phrases

Beam search can enforce lexical constraints by filtering the candidate set at each step. This is critical for lexically constrained decoding where specific terms must appear in the output. The algorithm prunes any hypothesis that cannot satisfy the constraints within the remaining length budget.

• Used for controlled summarization with mandatory keywords
• Enables grid beam search for multiple simultaneous constraints
• Maintains fluency while guaranteeing term coverage

In computational biology, beam search explores the combinatorial space of amino acid residue conformations. The algorithm builds protein backbone structures incrementally, maintaining a diverse set of low-energy candidates. This prevents premature convergence to local energy minima.

• Used in fragment assembly methods like Rosetta
• Beam tracks torsion angle combinations
• Balances energy minimization with structural diversity