Beam Search › Greedy Decoding and Why It Fails

The most natural strategy is greedy decoding: at each step, pick the highest-probability token and move on.

At time step $t$, the decoder outputs a probability distribution over the vocabulary $V$. Greedy decoding selects:

$$\hat{y}_t = \arg\max_{w \in V} P(w \mid \hat{y}_1, \ldots, \hat{y}_{t-1}, \mathbf{c})$$

where:

• $\hat{y}_t$: the token selected at step $t$
• $w$: a candidate token from vocabulary $V$
• $P(w \mid \hat{y}_1, \ldots, \hat{y}_{t-1}, \mathbf{c})$: the model's probability for token $w$ given all previously generated tokens and the context vector $\mathbf{c}$

This is fast and simple. The problem is that it maximizes local probability at each step, but local optima do not stack into a global optimum.

Consider translating the German sentence "Ich habe gestern das Buch gelesen" (I read the book yesterday). Suppose at step 1, the model assigns probability 0.45 to "I" and probability 0.40 to "Yesterday". Greedy decoding commits to "I" immediately. But "Yesterday I read the book" and "I read the book yesterday" are both valid translations with similar quality. If choosing "Yesterday" at step 1 leads to a sequence where all subsequent tokens are extremely high probability, then the full "Yesterday I read the book" sequence might have higher joint probability than "I read the book yesterday". Greedy decoding, having committed to "I" on step 1, will never discover this.

The fundamental issue is that greedy decoding makes irrevocable decisions without considering the downstream consequences. A choice that looks locally optimal may close off globally better paths. The metaphor of hiking comes to mind: if you always walk in the direction that appears to go uphill right now, you will quickly reach a local peak, but you may have missed the real summit by choosing poorly at an early fork in the trail.

There is a deeper pathology here that connects to the exposure bias problem we discussed in the Teacher Forcing chapter. The model was trained on human-generated sequences, where high-probability next tokens also tend to lead to high-probability continuations. But once the model starts generating its own output, errors compound. A greedy choice at step 3 that was slightly suboptimal might, by step 7, have led the model into a distribution that looks very different from anything in training. The model then has no good options and starts producing incoherent text. Greedy decoding is the strategy most vulnerable to this failure mode.

During training, every prefix the model sees is drawn from the training data. The decoder never observes what happens when it makes a mistake because the teacher-forced input always provides the correct previous token. At test time, the model is operating from a distribution it was never explicitly trained to handle: sequences that contain its own errors. Greedy decoding amplifies this mismatch because each step further diverges the model's current state from anything it encountered during training. Beam search partially mitigates this by keeping several paths alive, which provides a form of error recovery: if one hypothesis drifts into a bad region, another hypothesis in the beam may still be in a high-quality region.

The alternative would be to consider all possible sequences. Given a vocabulary of size $|V|$ and a maximum output length of $T$, the total number of sequences is $|V|^T$. For typical NLP settings ($|V| = 30{,}000$, $T = 50$), this is $30{,}000^{50}$, which is completely intractable.

What we need is an algorithm that explores more than one path without requiring exponential computation. Beam search achieves this by committing to a controlled level of exploration, keeping the $k$ best hypotheses at each step and discarding the rest. It does not guarantee finding the globally optimal sequence, but in practice it finds sequences that are significantly better than greedy decoding at a fraction of the cost of exhaustive search.