Skip to content
AI Engineer Guide.

concept · concepts · intermediate · concept 15 of 28

Greedy/beam

0 of 28 complete

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

Mechanism, step by stepInteractive
  1. 1Run the forward pass and take the argmax over the vocabulary for greedy decoding, append the token and repeat.
  2. 2For beam search, keep a fixed number of partial sequences and expand each one by its top candidates at every step.
  3. 3Score beams by summed log-probability, optionally normalised by length to avoid favouring short sequences.
  4. 4Prune back to the beam width, deduplicate equivalent prefixes, and continue until every beam hits a stop condition.
  5. 5Choose the final sequence by score, or re-rank the finished beams with a separate model when quality matters.
  6. 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.

Step 1/6 · step 1

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…

  1. Run the forward pass and take the argmax over the vocabulary for greedy decoding, append the token and repeat.
  2. For beam search, keep a fixed number of partial sequences and expand each one by its top candidates at every step.
  3. Score beams by summed log-probability, optionally normalised by length to avoid favouring short sequences.
  4. Prune back to the beam width, deduplicate equivalent prefixes, and continue until every beam hits a stop condition.
  5. Choose the final sequence by score, or re-rank the finished beams with a separate model when quality matters.
  6. Use greedy for extraction and classification, beam search for constrained generation, sampling for open-ended text.

Trade-offs

ChoiceGood forCostFails when
GreedyDeterministic, cheapest per tokenLocally optimal, can loop or repeatThe task needs a globally coherent sequence
Beam searchHigher sequence likelihood, stable outputMultiple forward passes per stepThe output should be creative or varied
Length-normalised beamFair comparison across lengthsFavours longer, sometimes padded answersBrevity is part of quality
Beam plus rerankerBetter final selectionExtra model and latencyThe reranker is not trained on your task
Trade-off mapInteractive

Good for

Deterministic, cheapest per token

Cost

Locally optimal, can loop or repeat

Fails when

The task needs a globally coherent sequence

  1. The task needs a globally coherent sequence
  2. The output should be creative or varied
  3. Brevity is part of quality
  4. 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