Greedy, beam search, and why chat models refuse both

The obvious strategy, and what it does

You have a distribution over 128,256 tokens. The obvious move is to take the most likely one, append it, and repeat. That is greedy decoding, and it is two lines:

for _ in range(max_tokens):
    logits = model(ids)[-1]
    ids.append(int(logits.argmax()))

Try it on an open model with an open-ended prompt. Within fifty tokens you will usually see something like this:

The best way to learn a language is to practise every day. The best way to
learn a language is to practise every day. The best way to learn a language...

It locks into a loop. This is not a bug in any particular model; it is a documented and general property, described carefully in work on neural text degeneration in 2019, and it happens across model families and sizes.

Why maximising probability produces bad text

The finding that made this click is counter-intuitive. Human-written text does not consist of high-probability tokens. Measure the per-token probability of real writing under a language model and you see constant variation: probable words, then a surprising one, then probable again. Greedy decoding produces a flat, uniformly high-probability sequence, which is a shape that human text never has.

There is a second, self-reinforcing effect. Once “The best way to learn a language is to practise every day.” appears in the context, the induction mechanism from module two makes repeating it the single most likely continuation. Each repetition raises the probability of the next. Greedy decoding walks straight into that trap and cannot get out, because it has no mechanism for taking a less likely path.

Beam search: better maximising, same problem

Beam search keeps the k best partial sequences at each step rather than one, scoring whole sequences instead of single tokens. It is better at finding a high-probability sequence, and it is the right tool for translation and speech recognition, where there is a single correct output and the model’s probability is a good proxy for correctness.

For open-ended generation it makes things worse in a specific way: it finds even more probable text, and more probable means blander and more repetitive. It also costs k times the compute, and it interacts badly with the key-value cache, since each beam needs its own. This is why beam search, once standard in machine translation, is essentially absent from chat model serving.

Penalties, and their side effects

The blunt instruments for repetition:

• Repetition penalty divides the logit of any token already present, discouraging reuse regardless of how far back it appeared.
• Frequency penalty subtracts an amount proportional to how many times a token has occurred.
• Presence penalty subtracts a fixed amount if a token has occurred at all.
• No-repeat n-gram blocking forbids any n-gram from appearing twice: effective and dangerous.

Every one of these is content-blind, and that is the honest caveat. A penalty that stops “the best way” repeating also penalises the second occurrence of a variable name in code, the recurring subject of a paragraph, and the word “patient” in a medical summary. Blocking repeated 4-grams will break a citation format. The usual practical advice is to keep these low, 1.0 to 1.15 for repetition penalty, and prefer better sampling to heavy penalties.

What is actually used

Chat models sample: draw from the distribution rather than maximising it, then restrict the pool with top-k, top-p or min-p, which the next lesson covers in detail. Sampling reintroduces the variation that real text has, and it escapes loops because a lower-probability token can win occasionally.

The trade-off is stated plainly and it never goes away. Sampling makes output more human and less predictable. Maximising makes it more predictable and less human. There is no setting that gives you both, and any advice that promises one is describing a preference rather than a mechanism.

Choosing, by task

• Extraction, classification, code that must compile, any task with one right answer: greedy or near-greedy. Low temperature, small pool. The failure mode of blandness does not apply when there is nothing to be creative about.
• Translation and transcription: beam search remains reasonable, and the tooling for it exists.
• Anything open-ended: sample. Accept the variation, and if you need consistency, get it from evaluation over many runs rather than from a decoding setting.

The test worth running

Take one prompt. Generate ten completions greedily and ten with sampling at temperature 0.8. Read all twenty. The greedy ten will be near-identical to each other and duller than you expected; the sampled ten will vary in quality in both directions. That five-minute exercise settles the question better than any argument about settings.