Beam Search

A heuristic search algorithm that explores a graph by expanding the most promising nodes in a limited set (the 'beam'), often used to find the most likely sentence translation or output sequence.

How it works

Beam search maintains a set of B candidate sequences (the beam) at each generation step. For each candidate, it expands all possible next tokens and scores the resulting B × |V| sequences by their cumulative log-probability. It then keeps only the top-B sequences as the new beam. This is repeated until all beams reach an EOS token. The final output is the complete sequence with the highest total log-probability. Beam width B controls the compute-quality trade-off: larger beams explore more possibilities but are slower.

Why it matters

Beam search was the standard decoding method for neural machine translation and early seq2seq models, producing more grammatical and fluent outputs than greedy decoding. For LLMs, it has been largely replaced by sampling-based methods (temperature, top-p, top-k) because beam search tends to produce generic, repetitive outputs and doesn't benefit as much from the fluency already baked into large language models. Understanding beam search remains important for structured output tasks and translation systems.