Why it matters
Decoding has to choose one path through an exponentially large space of sequences. Greedy takes the cheapest approximation and beam search spends more compute to keep alternatives alive. The engineering problem is that the objective, sequence probability, is only a proxy for usefulness: it rewards safe, repetitive continuations, so a decoder that optimises it harder can produce worse text. Choosing a decoder is choosing which failure you prefer.
Mental model
Greedy is walking downhill one step at a time; beam search keeps a few trails open in case the first dead-ends. The image breaks because the hill is not the goal: a higher-probability path can lead to a bland or repetitive answer, so the best-scoring trail is not necessarily the best answer.
How it works
- 1Run the forward pass and take the argmax over the vocabulary for greedy decoding, append the token and repeat.
- 2For beam search, keep a fixed number of partial sequences and expand each one by its top candidates at every step.
- 3Score beams by summed log-probability, optionally normalised by length to avoid favouring short sequences.
- 4Prune back to the beam width, deduplicate equivalent prefixes, and continue until every beam hits a stop condition.
- 5Choose the final sequence by score, or re-rank the finished beams with a separate model when quality matters.
- 6Use greedy for extraction and classification, beam search for constrained generation, sampling for open-ended text.
Step 1 of 6
Run the forward pass and take the argmax over the vocabulary for greedy decoding, append the token and repeat.
Figure. The mechanism in this page's own steps. The figure adds sequence, not new claims.
What to notice. A step can be read alone, but the order is the mechanism. The control lets you stop on any one.
Text version
The page's steps: 1. Run the forward pass and take the argmax over the vocabulary for greedy decoding, append … 2. For beam search, keep a fixed number of partial sequences and expand each one by its top … 3. Score beams by summed log-probability, optionally normalised by length to avoid favouring… 4. Prune back to the beam width, deduplicate equivalent prefixes, and continue until every b… 5. Choose the final sequence by score, or re-rank the finished beams with a separate model w… 6. Use greedy for extraction and classification, beam search for constrained generation, sam…
- Run the forward pass and take the argmax over the vocabulary for greedy decoding, append the token and repeat.
- For beam search, keep a fixed number of partial sequences and expand each one by its top candidates at every step.
- Score beams by summed log-probability, optionally normalised by length to avoid favouring short sequences.
- Prune back to the beam width, deduplicate equivalent prefixes, and continue until every beam hits a stop condition.
- Choose the final sequence by score, or re-rank the finished beams with a separate model when quality matters.
- Use greedy for extraction and classification, beam search for constrained generation, sampling for open-ended text.
Trade-offs
| Choice | Good for | Cost | Fails when |
|---|---|---|---|
| Greedy | Deterministic, cheapest per token | Locally optimal, can loop or repeat | The task needs a globally coherent sequence |
| Beam search | Higher sequence likelihood, stable output | Multiple forward passes per step | The output should be creative or varied |
| Length-normalised beam | Fair comparison across lengths | Favours longer, sometimes padded answers | Brevity is part of quality |
| Beam plus reranker | Better final selection | Extra model and latency | The reranker is not trained on your task |
Good for
Deterministic, cheapest per token
Cost
Locally optimal, can loop or repeat
Fails when
The task needs a globally coherent sequence
- The task needs a globally coherent sequence
- The output should be creative or varied
- Brevity is part of quality
- The reranker is not trained on your task
Figure. Each choice with what it buys, what it costs, and the case where it loses.
What to notice. The fourth column is the decision: if the losing case describes your situation, the choice is wrong.
Text version
Four trade-offs: Greedy is good for Deterministic, cheapest per token, costs Locally optimal, can loop or repeat, and fails when The task needs a globally coherent sequence. Beam search is good for Higher sequence likelihood, stable output, costs Multiple forward passes per step, and fails when The output should be creative or varied. Length-normalised beam is good for Fair comparison across lengths, costs Favours longer, sometimes padded answers, and fails when Brevity is part of quality. Beam plus reranker is good for Better final selection, costs Extra model and latency, and fails when The reranker is not trained on your task
Failure modes
- Repetition loop. Greedy decoding settles into a cycle of the same phrase. Debug: inspect per-step probabilities around the loop and check for a repeated n-gram in the output.
- Beam collapse. All beams converge to the same prefix and the search adds cost without diversity. Debug: log distinct beam prefixes per step.
- Length bias. Unnormalised scores favour short outputs that stop early. Debug: compare scores before and after length normalisation on the same prompt.
In production
Track output length and repetition rate per route, since both are early signs that a deterministic decoder is stuck. Cap beam width, because cost scales linearly with it.
Common misconceptions
People think: Beam search always produces better text than greedy.
Actually: It optimises sequence probability, which often means blander text; for open-ended generation sampling usually reads better.
People think: Greedy decoding is reproducible across providers.
Actually: Floating-point kernels, batching and model version can all change the argmax, so identical output is not guaranteed.
Interview angle
Compare the search space each method explores and the objective they optimise, then name the task types where that objective misleads. Mention cost per step and the role of length normalisation. A weak answer claims beam search is simply higher quality and cannot explain why it produces repetitive text.
Sources
- Vijayakumar et al., Diverse Beam Search — why plain beam search returns near-duplicate candidates.
- Holtzman et al., The Curious Case of Neural Text Degeneration — the failure modes of likelihood-maximising decoding.
- Sutskever et al., Sequence to Sequence Learning with Neural Networks — beam search as a sequence decoding procedure.