Vol. XXII · Decoding Plate 1 of 8greedy decoding, beam search, maximum likelihood, repetition, degeneration, searchAE

Greedy and Beam Search.

The most probable continuation is not the best one. It is usually the same phrase, again.

A language model gives a distribution over the next token; decoding chooses what to write. The simplest rule is greedy: always take the most probable token. Beam search keeps the w most probable partial continuations at each step, extends each by every token, and keeps the w best of those, so it can find continuations whose total probability is higher than greedy’s. For translation and speech recognition, where one correct output exists, beam search is standard.

For open-ended text it fails in a characteristic way. Holtzman and colleagues (2020) showed that human text is not the most probable text a model can produce — it is full of mildly surprising words — and that maximising probability leads to bland, repetitive output: once a phrase repeats, repeating it again becomes the most probable continuation. The course model micro (1.8 million parameters, four layers, trained on this course’s own plates in English and Chinese; plate I.9) runs in the page. The workshop decodes 30 tokens after a prompt with beams of width 1 (greedy) to 8.

Below: the continuation found at the chosen beam width; readouts give its log-probability per token and the share of its two-token sequences that are distinct.

What you will learn

Define greedy decoding and beam search.
Show beam search finding more probable text.
Show that high-probability text repeats.
Say where beam search is the right tool.

Workshop

micro, prompt “The attention”, 30 tokens. Beam width 1 is greedy. Log-probability per token: the continuation’s total log-probability under micro divided by its length. Distinct 2-grams: unique consecutive token pairs as a share of all pairs.

Probable is not good

Greedy decoding gives a continuation at −1.900 nats per token in which only 62% of two-token pairs are distinct: micro settles on a phrase and repeats it. Beam width 4 finds a continuation more probable by its own measure — −1.355 nats per token — and width 8 more probable still, −1.194; both still loop, on a different phrase. Search has done its job; the objective is the problem.

Human text sits far from the mode of a model’s distribution, so the decoding rules that write well for open-ended text — sampling with temperature and truncation, the next plates — deliberately do not seek the most probable output. Beam search remains right where the most probable output is the correct one: translation, transcription, constrained extraction, and in search over reasoning steps scored by a verifier, where probability is not the only criterion.

Repetition feeds itself: each repeat of a phrase raises the probability of repeating it again, because the model has learned that text which has repeated tends to keep repeating — an induction-head effect (plate XXVIII.4).

Terms

Greedy decoding: Choosing the most probable token at every step.
Beam search: Keeping the w most probable partial outputs at each step.
Degeneration: Bland, repetitive text produced by maximising probability.
Distinct n-grams: The share of n-token sequences that are unique: a measure of repetition.

Maximising probability finds bland, repetitive text; beam search finds it more efficiently than greedy, which is why open-ended generation samples instead.

Sources

Holtzman, Buys, Du, Forbes and Choi, “The Curious Case of Neural Text Degeneration”, ICLR 2020.
Graves, “Sequence Transduction with Recurrent Neural Networks”, 2012; Sutskever, Vinyals and Le, NeurIPS 2014 (beam search for sequence models).