14Decoding and Sampling

The model does not emit text. At every step it emits a distribution — a probability for every token in the vocabulary, the softmax output from Chapter 4 — and something else has to turn that distribution into an actual next token. That something is the decoder, and it is a separate choice from the weights: it costs no training, changes no parameter, and yet swings the output from crisp to rambling to broken. The same model, decoded two ways, is effectively two products. This chapter is about the knobs on that dial and what they actually do to the distribution.

14.1Greedy, beam, and why sampling won

The first instinct is to be greedy: at each step take the single most probable token, append it, repeat. A less myopic version is beam search, which keeps the \(B\) highest-probability partial sequences alive at once and expands them in parallel, so a locally poor token can survive if it leads somewhere globally likely. Both are search: they try to find the sequence the model scores highest.

For closed-ended tasks that has a right answer to aim at, search is exactly right — machine translation and speech recognition leaned on beam search for years, because there the highest-probability output is usually the correct one. Open-ended generation breaks that assumption. Maximizing sequence probability produces text that is bland, generic, and pathologically repetitive: it falls into loops, restating the same clause until you cut it off. This is neural text degeneration, and its diagnosis is that natural human language is simply not the maximum-probability string — people constantly choose locally surprising words, and a decoder that refuses to do so drifts into a rut the model itself would never have written (Holtzman et al., 2020).

The fix is to stop searching and start sampling: draw the next token from the distribution rather than maximizing over it. Pure sampling restores the human-like variance, but it overshoots — the distribution's long tail holds thousands of low-probability tokens whose combined mass is large, and sampling one occasionally derails a sentence into nonsense. So the practical decoders are all sampling with the unreliable tail cut away, which is the next section.

14.2Temperature, top-k, and top-p

Every knob reshapes the same distribution before you draw from it. Temperature \(T\) divides the logits before the softmax: \(T < 1\) sharpens the distribution toward its peak (more conservative), \(T > 1\) flattens it toward uniform (more random), and \(T \to 0\) recovers greedy decoding. Note what temperature does not do — it never reorders the tokens, so it cannot make an unlikely token beat a likely one; it only changes how often the also-rans get picked.

Temperature alone still leaves the whole tail in play, so two truncation knobs cut it off before sampling. Top-k keeps the \(k\) highest-probability tokens, zeros the rest, and renormalizes (Fan et al., 2018). It is simple but rigid: \(k\) is fixed whether the model is certain (where even \(k=5\) admits junk) or torn (where \(k=5\) throws away good options). Top-p, or nucleus sampling, fixes that by cutting on mass instead of count — keep the smallest set of tokens whose cumulative probability reaches \(p\) (say \(0.9\)), then renormalize (Holtzman et al., 2020). When the model is confident the nucleus is one or two tokens; when it is unsure the nucleus widens to admit many. Top-p adapts its own cutoff to the shape of the distribution, which is why it became the default.

14.3Newer samplers and the penalties

Nucleus sampling is not the last word. Min-p sets its threshold relative to the top token: keep every token whose probability is at least \(p_{\min}\) times the maximum, so a peaked distribution admits a handful and a flat one admits many (Nguyen et al., 2024). That makes it robust at high temperature — where top-p can let a flattened tail leak in, min-p's floor scales down with the peak and holds the line. Locally typical sampling takes a different cut entirely: instead of keeping the most probable tokens it keeps the typical ones, those whose surprisal sits close to the distribution's entropy, on the information-theoretic argument that fluent human text hugs its expected information content rather than maximizing probability (Meister et al., 2023).

A separate family fights repetition directly by editing logits from the history. The repetition penalty divides the logit of any token already generated, discouraging reuse (Keskar et al., 2019); OpenAI-style presence and frequency penalties subtract a flat amount for having appeared at all, or an amount scaled by how often. These break loops, but they are blunt: a strong penalty punishes the legitimate repetition that code, names, and structured text depend on.

The defaults also assume open-ended prose, and that assumption is often wrong. Factual answers, extraction, and code want a low temperature — you are not after diversity, you are after the one right continuation. Reasoning models (Chapter 25) push this furthest: they typically want near-greedy decoding, because the goal is the single most-likely chain of thought, and sampling temperature there mostly adds a chance to wander off a correct derivation.

14.4Structured and constrained decoding: a preview

Sometimes "usually valid" is not good enough — a downstream parser needs the output to be a JSON object, or match a regex, or follow a grammar, every time. Constrained decoding guarantees this by masking: at each step it sets the logits of every token the format forbids to \(-\infty\) before sampling, so only legal continuations can be drawn. The samplers from this chapter still run, but on the survivors — mask first, then apply temperature and top-p to whatever remains legal.

The catch is that a hard mask can distort the model's intent — if the format forbids the token the model actually wanted, you get a valid output the model would rate poorly — and building the mask correctly against the tokenizer is fiddly. This is a harness concern, so the full treatment of JSON mode, regex, and context-free grammars lives in Chapter 20; here it is enough to see that decoding and format constraints compose. The other axis this chapter set aside is cost: every sampled token requires a full forward pass, and making that pass cheap — the KV cache, speculative decoding — is the subject of Chapter 15.