Greedy Decoding vs Beam Search vs Sampling

The interesting split is not between algorithms. It is between two incompatible goals: produce the most probable sequence, or produce a typical one. Once you know which you want, the algorithm follows — and for open-ended text the most probable sequence is not what you want.

Two objectives, not three algorithms

At each step the model gives a distribution over the next token. A decoding strategy is a policy for turning a sequence of those distributions into one output sequence, and the policies divide by what they are trying to achieve.

• Maximisation — find the sequence with the highest joint probability. Greedy and beam search are two approximations to this, since exact search over all sequences is intractable.
• Sampling — draw from the distribution the model actually produced, possibly after reshaping it with temperature and truncation.

These are not two settings of one dial. They answer different questions, and the reason the field moved to sampling for open-ended generation is that the maximisation objective turned out to be the wrong objective, not that it was solved badly.

Greedy

Take the highest-probability token at every step. This is beam search with a beam width of one, and it is what T = 0 gives you in an API.

Its weakness is structural: a locally best token can lead into a region where every continuation is poor, and greedy has no way to reconsider. It committed at step 3 and discovers the problem at step 40. Its strength is the mirror image of that: one forward pass per token, no extra memory, and near-reproducible output, which is why it is the right default for extraction, classification and anything you plan to diff between runs.

Beam search and the maximisation trap

Beam search keeps the b best partial sequences at every step instead of one, extends each, and re-ranks by cumulative log-probability. It costs roughly b times the compute and finds higher-probability sequences than greedy. Two details bite immediately: log-probabilities are negative, so longer sequences score worse and a length normalisation term is mandatory; and the beams tend to be minor variations of one another, so the diversity you might have hoped for is not there.

The deeper problem is that higher probability is not better text. Two findings from the literature make this concrete. Koehn and Knowles (2017) documented that in neural machine translation, quality degrades beyond a modest beam width — searching harder finds worse translations, which is only possible if the model’s probability is not aligned with quality. Holtzman et al. (2020), in “The Curious Case of Neural Text Degeneration”, showed the same effect for open-ended generation: maximisation-based decoding produces bland, repetitive text, and their explanation is that human text is not the maximum-probability continuation. Real writing keeps taking mildly surprising turns; a maximiser never does, and a model that has been pushed into a repetitive loop finds that the loop is the highest-probability continuation available.

That is the mechanism behind repetition loops: once “A B A B” is in the context, “A” genuinely is the most likely next token, and any strategy whose objective is maximisation will take it every time.

Beam search remains right where the objective genuinely is maximisation: a short output, a single correct answer, a strong alignment between model probability and correctness. Machine translation and speech recognition are the classic cases, which is also why they are the classic encoder-decoder domains. Most hosted chat APIs do not expose it at all, which settles the question for most readers before they get to weigh it.

Sampling

Draw from the distribution instead of maximising it. Pure sampling from the raw distribution is too permissive — the tail of a 32000-token vocabulary contains a lot of nonsense with small but non-zero probability, and over hundreds of steps something from it will be drawn. Truncation methods exist to cut that tail without flattening the head, which is what nucleus sampling was introduced to do.

Two further members worth naming because they are available in open runtimes and often better than their defaults suggest. Locally typical sampling (Meister et al., 2022) keeps tokens whose information content is close to the distribution’s entropy, on the theory that human text is typical rather than maximal. Contrastive search (Su et al., 2022) penalises candidates that are too similar to what has already been generated, attacking repetition directly rather than probabilistically.

One thing that is not a decoding strategy, despite the name sounding like one: speculative decoding is an execution optimisation that provably preserves the output distribution. It changes how fast tokens arrive, not which ones.

Two parameters belong to the decode policy even though they are not usually discussed as part of it. max_tokens is a hard stop applied by the runtime, and a response cut by it is not a response the model finished — the difference shows up in the finish reason and is worth branching on, because a truncated JSON object and a complete one fail very differently. Stop sequences work the same way: they terminate the loop when a string appears, so a stop sequence that can occur inside a legitimate answer will silently truncate it.

Choosing, by task

The honest caveat: this table is a starting point, and the only way to settle it for your task is to run both and look. The harness in the sampling-parameters guide sweeps settings on your own prompt and reports how much the output varies; point it at a task where you can score correctness and you have the comparison this page deliberately does not fabricate.