Decoding Strategies: Greedy Search and Beam Search

Once a model produces a probability distribution, something has to turn it into a sequence. The deterministic strategies — greedy and beam search — and why the locally best token is not the globally best sentence.

At every step, a language model hands you a probability distribution over the next token. It does not hand you a sentence. The rule that turns a sequence of distributions into an actual output is the decoding strategy, and the choice is not a detail — the same model produces markedly different text depending on it. This tutorial covers the deterministic strategies, greedy and beam search, which try to find the highest-probability sequence. The randomized alternatives — temperature, top-p, top-k — are covered separately in Temperature and Top-p.

The problem decoding solves

Recall the generation loop: predict a distribution, pick a token, append, repeat. The “pick a token” step is where decoding lives. It sounds trivial — take the most likely one? — but there is a real problem hiding in it.

What you usually want is the most probable sequence, not a chain of individually most-probable tokens. Those are not the same thing. A token that looks best right now can lead into a region where every continuation is poor, while a slightly worse token now might open onto a much better sentence. Decoding strategies differ in how hard they work to avoid that trap.

Greedy search

The simplest strategy: at each step, take the single highest-probability token. No looking ahead, no alternatives kept. This is what temperature approaching zero collapses to.

Greedy decoding is fast and deterministic — same input, same output every time — and for short, factual completions it is often exactly right. Asked for the capital of France, you want the top token and nothing fancier.

Its weakness is structural: it is locally optimal, globally blind. Consider the model wanting to produce “New York.” Suppose after some prefix the single most likely next token is “New,” but the model actually assigns even higher combined probability to a phrasing that starts with a slightly less likely token. Greedy commits to “New” and can never recover, because it never reconsiders. Each choice is final, and one greedy step can steer the whole sequence into a lower-probability path than a little foresight would have found. On longer generations this shows up as text that is fluent locally but sometimes takes an awkward turn it cannot back out of.

Beam search

Beam search is the direct answer to greedy’s blindness: instead of keeping one candidate sequence, keep the k best. That k is the beam width.

At each step, every one of the k surviving sequences is extended by every possible next token, all the resulting longer sequences are scored by their total probability, and only the top k are kept. The rest are discarded. When generation ends, the highest-scoring sequence in the beam is returned.

The intuition: greedy commits to one path immediately; beam search hedges across several promising paths and lets them compete over multiple steps. A token that looked mediocre at step 3 can win if the sequences built on it turn out strongest by step 8. With a beam of 5, the model explores five parallel hypotheses and picks the best complete one — often recovering the higher-probability sequence that greedy walked straight past.

One necessary detail: length normalization. Because each token’s probability is below 1, longer sequences accumulate lower total probability just by being longer. Without correcting for this, beam search is biased toward short outputs. Scores are normalized by length so that longer, genuinely-better sequences are not unfairly penalized.

Why beam search is not the default for chat

If beam search finds higher-probability sequences, why do open-ended assistants rarely use it? Because for open-ended generation, “highest probability” is the wrong target.

The most probable sequence is often bland, generic, and repetitive — the safest, most predictable continuation, which reads as flat and can get stuck in loops. Beam search actively optimizes toward that blandness, and often produces text that repeats itself. For open-ended writing and conversation, the deliberate randomness of sampling yields output that is more varied, natural, and human. So the field split by task.

Beam search remains the right tool where there genuinely is a single best answer and faithfulness matters more than variety: machine translation, speech transcription, and other sequence-to-sequence transformations. There, finding the highest-probability output is exactly the goal, and beam search’s search effort pays off. For chat and creative generation, sampling wins.

Matching strategy to task

• Greedy: fast, deterministic, good for short factual answers; risks awkward locally-optimal paths on longer output.
• Beam search: explores multiple hypotheses to find a high-probability sequence; best for translation and transcription, where one right answer exists.
• Sampling (see Temperature and Top-p): deliberate randomness for varied, natural open-ended text; the default for chat and creative work.

The deep point is that decoding is a genuine choice with no universal winner. “Best next token” and “best sequence” and “most useful output” are three different targets, and the strategy you pick decides which one you optimize.

What to remember

• Decoding turns a sequence of probability distributions into an actual output; the choice materially changes what a model produces.
• Greedy takes the top token each step — fast and deterministic, but locally optimal and unable to recover from a bad turn.
• Beam search keeps the k best sequences and lets them compete, finding higher-probability sequences greedy would miss; it needs length normalization to avoid favoring short outputs.
• Beam search is not used for chat because the most-probable sequence is often bland and repetitive; it shines in translation and transcription.
• “Best token,” “best sequence,” and “most useful text” are different targets — decoding is the choice of which one you pursue.

Next: Temperature and Top-p — the randomized decoding strategies for open-ended generation.