Greedy Decoding and the Beam That Faded

Lesson 1 of 4 in Decoding and Sampling.

Every Decode step ends the same way: the forward pass produces Logits — one score per entry in the Vocabulary — and Softmax turns them into a probability distribution over every possible next Token. The model’s job stops there. Something still has to pick one token from that distribution, and that something is the decoding strategy. It runs on the serving side, costs almost nothing per step, and shapes the output as much as anything inside the model.

The simplest strategy is greedy decoding: take the argmax — the single highest-probability token — every step, always. It is deterministic given identical logits, needs no tuning, and is exactly right when there is one correct continuation. But greedy is myopic. It optimizes each step in isolation, and the best sequence is not always built from the best next token: a slightly less likely word now can open onto a far more likely continuation later. Greedy also feeds its own failure mode — once it drifts into a repetitive phrase, repetition tends to raise the probability of more repetition, and the output can lock into a loop.

Beam search is the classic fix for the myopia. Instead of one running hypothesis, keep the k most probable partial sequences (the “beam”), extend each of them every step, and keep the best k of the results. It searches for a whole sequence with high joint probability rather than a chain of locally best picks.

Greedy takes one path; beam width 2 keeps the runner-up alive (toy probabilities)

  1. Context: “The food was …”

    All probabilities in this tree are invented for teaching — an illustrative two-step lookahead.

  2. “good” — p 0.45

    The single most probable next token. Greedy commits to it and never looks back.

  3. “surprisingly” — p 0.35

    Only the runner-up this step — but beam search (width 2) keeps it alive as a second hypothesis.

  4. “.” — joint p 0.14

    0.45 × 0.30. The greedy path’s best continuation is weak: “good” led somewhere ordinary.

  5. “good” — joint p 0.28

    0.35 × 0.80. The runner-up first word opened onto a much stronger continuation.

  6. Greedy output: “good.”

    Locally optimal at every step, yet the lower-probability sequence overall.

  7. Beam output: “surprisingly good”

    Beam search surfaces the higher joint-probability sequence greedy could never reach.

Beam search ruled the previous era of text generation — machine translation and speech recognition lived on it. So why do LLM APIs barely offer it? Because open-ended generation broke it. Holtzman et al. (2020) showed that maximization-based decoding — beam search included — produces text that is measurably unlike human text: it is too predictable, and it degenerates into bland, repetitive loops. Human writing constantly uses tokens the model considers merely plausible rather than maximal; a decoder that always chases the probability peak writes prose no human would. The paper’s memorable evidence: beam-searched continuations sit at consistently high per-token probability while human continuations fluctuate — and the beam text repeats itself into the ground.

Where does beam survive? In the niches shaped like its old home: short, constrained outputs with a notion of a correct answer — translation-style tasks, transcription, some structured rewriting — settings where joint probability genuinely tracks quality and degeneration has no room to develop. Even there it is a judgment call, not a default; most production LLM serving today exposes greedy and sampling, and leaves beam off the menu.

Why chasing the probability peak writes inhuman text

Two mechanisms interlock. First, the objective is wrong for the task. Beam search approximately maximizes the joint probability of the whole sequence — the product of per-step probabilities. But Next-token prediction training makes the model a distribution estimator, not an oracle whose top pick is “the right answer”. In open-ended text, the true distribution over good continuations is wide and flat; picking its mode over and over samples a statistically freakish object — a sequence more probable than almost anything a human would produce. Holtzman et al. (2020) framed this directly: high-quality human text does not maximize probability, so a decoder that does is optimizing the wrong thing.

Second, repetition is self-reinforcing. Once a phrase appears twice, the model — which has seen plenty of legitimately repetitive text — raises the probability of a third occurrence, which raises it again. Maximization-based decoding has no escape hatch: the loop is the probability peak, so greedy and beam fall in and stay. Sampling escapes almost for free, because any nonzero-probability alternative can be drawn. That asymmetry, more than anything, is why the knobs in the next lesson became the default interface of every LLM API.

Interactive checkpoint quiz (2 questions) — open this page in a browser to take it.