Beam Search

Beam search is what you reach for when greedy-decoding's single-path myopia is unacceptable but exhaustively searching every possible sequence is intractable. The vocabulary is tens of thousands of tokens wide; even a modest output of 20 tokens has more possible sequences than atoms worth counting. Beam search compromises: instead of one candidate or all of them, it tracks a fixed number k of the most promising partial sequences at every step, called the beam width.

The algorithm

At each step, for every one of the k sequences currently on the beam, beam search considers extending it with every token in the vocabulary, scores each resulting sequence by cumulative log-probability, and keeps only the top k overall (not top k per beam, top k across all k * vocab_size candidates):

score(sequence) = sum_t  log p(x_t | x_1, ..., x_{t-1})

Summing log-probabilities rather than multiplying raw probabilities avoids numerical underflow over long sequences and turns the objective into something you can compare additively across candidates of different lengths (with a length penalty, discussed below, since summed log-probabilities are naturally biased toward shorter sequences). At k=1, beam search is exactly greedy decoding; larger k explores more of the tree at proportionally higher compute cost, since every beam requires its own forward pass through the model at each step.

Why length needs correcting for

Log-probabilities are negative and accumulate downward with every token (each token has probability less than one, so log p < 0). Left uncorrected, this means beam search's raw score systematically favours shorter sequences: a 5-token sequence has fewer negative terms summed in than a 20-token one, even if the 20-token sequence is a better, more fluent completion. The standard fix is a length penalty that divides the cumulative score by some function of the length, commonly length^alpha for alpha in roughly [0.6, 1.0], so that longer sequences are not unfairly punished for having more terms to sum:

normalised_score = score(sequence) / length(sequence)^alpha

Get this wrong and beam search either truncates outputs unnaturally early (no length penalty) or runs long and rambling (over-corrected penalty). Every production beam search implementation, and every seq2seq translation system, tunes this knob explicitly.

Where beam search wins

Machine translation is beam search's home turf, and for a structural reason: translation has something close to a single correct answer (or a small family of acceptable ones), and higher sequence probability genuinely correlates with translation quality. The same logic applies to summarisation and other tasks with a narrow, mostly-correct target. In these settings, exploring more of the search tree than greedy does reliably finds better sequences, and the extra compute is worth it.

Where beam search backfires

Open-ended generation is a different problem, and this is where beam search's core assumption, that higher sequence probability is better, breaks down. Maximising probability drives beam search toward exactly the same degenerate territory as greedy: bland, generic, repetitive continuations, because those are frequently the highest-probability continuations in a model trained on natural text. Holtzman et al., 2019 show this concretely: beam search text scores highly on likelihood but is measurably duller (lower lexical diversity, more repeated n-grams) than either human text or text produced by sampling-based decoders. This is the central argument for why chat, story generation, and brainstorming use sampling methods like temperature-sampling and nucleus-sampling-top-p instead of beam search, despite beam search doing a more thorough job of finding a high-probability sequence.

When it falls down

• Compute scales with beam width. A beam of width k costs roughly k times the forward-pass compute of greedy per step; wide beams are expensive, and the quality gains diminish quickly past small widths (often k=4 to k=10 in translation systems).
• High probability, low quality for open text. On open-ended generation it optimises exactly the wrong objective, sequence likelihood, and produces text that is fluent but generic; this is the primary reason it lost ground to sampling for chat and creative tasks.
• Beam search can still repeat. Wider beams reduce but do not eliminate repetition loops, since a repeated phrase can remain the jointly highest-scoring continuation across several beams at once; practical implementations often add an explicit no-repeat n-gram constraint on top (see repetition-penalty).
• The length penalty is a hack, not a principled fix. alpha is tuned empirically per task and dataset; there is no single correct value, and a penalty tuned for one domain can misbehave on another.

Further reading

• Holtzman et al., 2019, The Curious Case of Neural Text Degeneration, arXiv:1904.09751 - the empirical case that beam search's high-probability text is lower quality than sampled text on open-ended generation.
• Wu et al., 2016, Google's Neural Machine Translation System, arXiv:1609.08144 - production-scale beam search with the length-penalty formulation still used today.