Beam Search.

Beam search is a heuristic search algorithm used in sequence generation tasks like machine translation, text summarization, and language modeling to find outputs with higher overall probability than greedy decoding. Instead of selecting only the single most probable token at each step (greedy search), beam search maintains multiple candidate sequences simultaneously, keeping track of the k most promising partial sequences based on their cumulative probability scores. This approach helps avoid the local optima problem where an early suboptimal choice leads to poor overall results.

The algorithm works by expanding each of the k current candidates with all possible next tokens, scoring the resulting sequences, and then pruning back to the top k candidates for the next iteration. The beam width k represents a trade-off between computational cost and search quality—larger beams explore more possibilities but require more computation. At each step, sequences are typically scored using log probabilities to avoid numerical underflow, and various normalization techniques like length penalties are often applied to prevent bias toward shorter sequences.

Beam search significantly improves output quality compared to greedy decoding in many applications, particularly in machine translation where it has been a standard technique for decades. However, it comes with increased computational overhead that scales linearly with beam width, and it can still miss the globally optimal solution since it's a heuristic approximation. Modern neural text generation often combines beam search with other techniques like nucleus sampling or uses it selectively for tasks where deterministic, high-quality outputs are more important than diversity or speed.