Greedy Decoding and Beam Search

A language model gives a probability distribution over the next token. Decoding is the procedure that turns those distributions into one output sequence. Greedy decoding and beam search are the two standard deterministic procedures: both try to find a high-probability sequence rather than sample a varied one.

The search problem

The model scores a whole sequence as a product of per-token conditionals, \(p(y\mid x)=\prod_t p(y_t\mid y_{<t},x)\). The best sequence under this score is the one with the largest product. With a vocabulary of size \(V\) and length \(n\), there are \(V^n\) candidates, so exhaustive search is infeasible for real models. Decoders therefore commit to tokens step by step.

Greedy decoding takes the single most probable token at each step and moves on. It costs one model call per generated token.

Beam search keeps the \(B\) best partial sequences (the beam) at each step. Each is extended by every possible next token, and the \(B\) best extensions by total log probability form the next beam. Greedy decoding is beam search with \(B=1\). Cost is about \(B\) times higher.

A traced example

Use a hypothetical two-step model: the first token is A with probability 0.6 or B with 0.4. After A, the next token is x, y, or z with probabilities 0.4, 0.3, 0.3. After B, it is x with 0.9, and y or z with 0.05 each.

• Greedy takes A (0.6), then x (0.4), producing Ax with probability 0.24.
• The best sequence is Bx, with 0.4 x 0.9 = 0.36.
• Beam search with \(B=2\) keeps both A and B after step one, scores all six extensions, and finds Bx at 0.36.

Greedy failed because the best first token was not on the best path: A has more mass at the first step but spreads its continuation, while B commits. Beam search is not guaranteed to succeed either. A prefix that falls out of the beam is gone for good, so if the best sequence begins with a first token ranked below \(B\), it is missed. Wider beams reduce this risk at higher cost.

Length bias

Every extra token multiplies the sequence probability by a number at most 1, so longer sequences tend to have lower total probability. Take two hypothetical complete outputs: a 2-token output with token probabilities 0.8 and 0.5 (product 0.40) and a 4-token output with probabilities 0.75 each (product 0.316). Raw probability prefers the short output. Per-token average log probability is -0.458 for the short one and -0.288 for the long one, so a length-normalized score prefers the long one. Beam implementations commonly normalize by length (Wu et al. use a length penalty in their translation system), and the choice of normalization changes which output wins, so it should be treated as a tunable setting.

Is the highest-probability sequence the best text?

For tasks with one right answer, such as extraction or classification, a mode-seeking decoder is natural. For open-ended generation, Holtzman et al. observe that likelihood-maximizing decoding yields bland, repetitive text, which is why sampling methods (see Top-k and Top-p Sampling) are used there. The model’s probability measures how likely a sequence is under the model’s training distribution, not how useful or true it is, and the most probable sequence can be a generic or degenerate one. Beam search in machine translation also helps up to moderate widths and then can degrade quality as it finds ever more probable but worse outputs, a pattern that has been studied under the name of the beam search curse.

Practical notes

• Greedy decoding is a deterministic function of the logits, but logits can differ slightly across hardware, batch composition, or floating-point order. When two tokens are nearly tied the argmax can flip, so exact repeatability is likely but not guaranteed.
• Temperature zero in an API usually means greedy decoding.
• Beam search needs the \(B\) beams in memory and generally is not what hosted chat APIs offer; sampling with truncation is the common alternative.

References

• Holtzman et al., The Curious Case of Neural Text Degeneration — https://arxiv.org/abs/1904.09751
• Wu et al., Google’s Neural Machine Translation System — https://arxiv.org/abs/1609.08144