8.7  Decoding and Generation

The language model of Section 8.5 ended with a cliffhanger. We trained a network that assigns a probability to every possible next token, and the moment we asked it to write, two crude recipes presented themselves: always take the most probable token, or draw one at random from the model’s distribution. Both produced text, and both produced problems, from continuations that circle through the same phrase to continuations that wander into gibberish. This section treats the step we improvised there as a subject of its own. Decoding, turning a model over next tokens into actual sequences, is a design space with its own algorithms, failure modes, and a modern toolkit (Graves 2013; Holtzman et al. 2020), and it is largely independent of the network that feeds it: everything we build here applies unchanged to the gated architectures of the next chapter and to the largest of large language models.

%matplotlib inline
from d2l import torch as d2l
import math
import numpy as np
import random
import torch
%matplotlib inline
from d2l import tensorflow as d2l
import math
import numpy as np
import random
%matplotlib inline
from d2l import jax as d2l
import math
import numpy as np
import random
%matplotlib inline
from d2l import mxnet as d2l
import math
import numpy as np
import random
from mxnet import npx
npx.set_np()

8.7.1 The Decoding Problem

A trained language model supplies conditionals: writing \(x_{<t}\) for the prefix \(x_1, \ldots, x_{t-1}\), it turns any prefix into a distribution \(P(x_t \mid x_{<t})\) over the next token. The chain rule of probability assembles these local judgments into the probability of an entire sequence,

\[P(x_1, \ldots, x_T) = \prod_{t=1}^{T} P(x_t \mid x_{<t}). \tag{8.7.1}\]

Decoding asks the inverse question: given the conditionals, which sequence should we output? One natural answer is the most probable sequence, the argmax of Equation 8.7.1 over all candidates. But the number of candidates is staggering. With vocabulary \(\mathcal{V}\) and \(T\) tokens to generate there are \(|\mathcal{V}|^T\) sequences to compare; for our modest 1,024-token vocabulary and a 50-token continuation that is \(1024^{50} = 2^{500} \approx 10^{150}\) sequences, vastly more than there are atoms in the observable universe. Evaluating them all, exhaustive search, costs \(\mathcal{O}(|\mathcal{V}|^T)\) model evaluations and is out of the question; every practical decoder explores a vanishing fraction of this space and must decide, step by step, which fraction.

Intractability is only half of the problem, though. The other half is that for many uses the most probable sequence is not even what we want. When a task has essentially one right answer conditioned on the input, a French sentence to translate, an utterance to transcribe, a function signature to complete, probability mass concentrates on that answer and hunting for the argmax is exactly right. But when we ask a model to write, there are astronomically many acceptable continuations, each individually improbable. A model that has learned this diversity spreads its mass accordingly, and insisting on the single most probable output discards the diversity we asked for; we will see shortly that it collapses into dull repetition. Matching the output’s diversity to the model’s is what sampling does.

These two regimes organize the whole section (Figure 8.7.1). Maximization methods, greedy decoding and beam search, chase the most probable output and rule tasks with a right answer, such as machine translation and speech recognition. Sampling methods draw from the model’s distribution, reshaped by a small set of dials named temperature, top-\(k\), top-\(p\), and min-\(p\), and rule open-ended generation: chat, stories, and everything one now associates with a large language model.

Figure 8.7.1: One trained language model, two families of decoding strategies: maximization for tasks with one right answer, sampling for tasks with many.

8.7.1.1 A Model to Decode From

We need a trained model to experiment on, and the concise RNN language model of Section 8.5 is ideal: small enough to train here in about a minute, good enough (recall, about 2.4 bits per byte) that its continuations respond visibly to decoding choices. We retrain it with exactly the recipe used there.

data = d2l.TimeMachine(batch_size=1024, num_steps=32,
                       num_train=50000, num_val=5000)
rnn = d2l.RNN(num_inputs=64, num_hiddens=128)
model = d2l.RNNLM(rnn, vocab_size=len(data.vocab), lr=4)
with d2l.try_gpu():
    rnn = d2l.RNN(num_inputs=64, num_hiddens=128)
    model = d2l.RNNLM(rnn, vocab_size=len(data.vocab), lr=4)
rnn = d2l.RNN(num_inputs=64, num_hiddens=128)
model = d2l.RNNLM(rnn, vocab_size=len(data.vocab), lr=4)
rnn = d2l.RNN(num_inputs=64, num_hiddens=128)
model = d2l.RNNLM(rnn, vocab_size=len(data.vocab), lr=4)
trainer = d2l.Trainer(max_epochs=10, gradient_clip_val=1, num_gpus=1)
model.board.yscale = 'log'
trainer.fit(model, data)

Every decoding strategy in this section interacts with the model through one narrow interface: hand me the token ids so far, and I will hand you the logits for the next token. We wrap the trained network in a step_fn implementing that interface, converting the result to a plain NumPy vector so that the strategies themselves can be written once, in ordinary Python, with no framework in sight. Any model that can fill this interface, today’s RNN, next chapter’s LSTM, a transformer, can be decoded by every algorithm below.

def step_fn(ids):  # Token ids in, numpy logits for the next token out
    with torch.no_grad():
        logits = model(d2l.tensor([ids], device=d2l.try_gpu()))
    return d2l.numpy(logits)[0, -1]
def step_fn(ids):  # Token ids in, numpy logits for the next token out
    logits = model(d2l.tensor([ids]))
    return d2l.numpy(logits)[0, -1]
def step_fn(ids):  # Token ids in, numpy logits for the next token out
    logits = model(d2l.tensor([ids]))
    return d2l.numpy(logits)[0, -1]
def step_fn(ids):  # Token ids in, numpy logits for the next token out
    logits = model(d2l.tensor([ids], ctx=d2l.try_gpu()))
    return d2l.numpy(logits)[0, -1]

Note the deliberate extravagance: each call re-runs the network over the entire prefix just to produce one vector of logits. We will tally the cost of this convenience at the end of the section.

8.7.2 Greedy Decoding

The simplest decoder commits, at every step, to the single most likely token:

\[x_t = \operatorname*{argmax}_{x \in \mathcal{V}} P(x \mid x_{<t}).\]

The algorithm is a one-line loop: score, take the argmax, append, repeat. It costs one model evaluation per token, \(\mathcal{O}(|\mathcal{V}| T)\) work in total, and it is deterministic: the same prefix always yields the same continuation.

def decode_greedy(text, num_tokens=50):
    ids = data.tokenizer.encode(text)
    for _ in range(num_tokens):
        ids.append(int(step_fn(ids).argmax()))
    return data.tokenizer.decode(ids)

for text in ('the time traveller', 'it seemed to me that'):
    print(repr(decode_greedy(text)))
'the time traveller\nand startment of the\nsle of the\nside of the\nbut of the\nbut of the\nbut of the\nbut of the\nbut of the\nbut of the\nbut'
"it seemed to me that the\nsidea.\n\n'In a\nmath.\n\n'In a\nbut I was a\nsloring of the\nbut of the\nbut of the\nbut of"
'the time traveller the\nside, I saw\nlittleess of the\nfour of the floor of the\nsunned and\npresented\ntheseength, the\nfour of the faint of'
'it seemed to me that the\nhim, and that the\nfour of the floor of the\nsunned and\npresented\ntheseength, the\nfour of the faint of\nthese, I'
"the time travellerfer. I had a vast\n'I think that the\nshass.\n\n'I cannot tired, I saw a\nmane, and\nthere I was in\nthese, and"
"it seemed to me that I\nwas fanced the\nlittle lawn. I\ncame a\nhandly in the Time Traveller.\n\n'I cannot travel-matches. I thought of a\ndisapped"
'the time traveller I had come into the future. I was a vast array of a vast array of a vast array of a vast array of a vast array of a vast arr'
'it seemed to me that the sun willutes of a tramblance of the Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller.'

The output is locally plausible Wells, but it drifts toward the generic, and it drifts predictably: the two different prefixes soon funnel into the same stock phrases, and, depending on the training run, the continuation may lock into a verbatim repeating cycle outright. Two distinct flaws are on display. The first is myopia: a sequence of locally best tokens need not be the best sequence. Suppose the vocabulary holds four tokens \(A\), \(B\), \(C\), and \(D\), and at the first step the model assigns them probabilities 0.5, 0.2, 0.2, and 0.1. Greedy picks \(A\). Conditioned on \(A\), suppose the best continuation runs through \(B\) with probability 0.4, then 0.4, then 0.6: the greedy sequence has probability \(0.5 \times 0.4 \times 0.4 \times 0.6 = 0.048\). Had we accepted the second-best token \(C\) (probability 0.3) at the second step, the changed conditioning might offer 0.6 and 0.6 next, for a total of \(0.5 \times 0.3 \times 0.6 \times 0.6 = 0.054\). Taking one locally suboptimal step bought a globally better sequence; greedy can never make that trade.

The second flaw runs deeper than myopia. Greedy decoding feeds its own argmax back in as context, and repetition is self-reinforcing: once a phrase has appeared twice, its third occurrence is more probable still, since the model has learned that text which repeats tends to keep repeating. The argmax feedback loop rides this gradient toward repetition and, given enough maximization pressure, into a literal fixed cycle. Holtzman et al. (2020) documented the phenomenon, aptly named neural text degeneration, in models a thousand times larger than ours: maximization-based decoding of open-ended text produces output that is repetitive, low-diversity, and measurably unlike human text, no matter how good the underlying model is. Keep that in mind as we now fix the first flaw, myopia, and watch the second one get worse.

8.7.4 Sampling and Its Dials

If the model’s distribution is worth trusting, the principled way to generate is to sample from it: draw \(x_t \sim P(x_t \mid x_{<t})\), append, repeat. Text produced this way is distributed exactly as the model believes text should be, with all the diversity that maximization threw away and none of its repetition traps. The catch appears in the tail. Our model spreads small probability over a thousand tokens, a large one over hundreds of thousands, and although each unlikely token is individually negligible, their combined mass at every step is not. Sampling therefore regularly hits tokens the model itself considers near-nonsense, and one absurd token, fed back as context, can derail everything after it. Holtzman et al. (2020) call this the unreliable tail: the model’s estimates are relatively trustworthy at the head of the distribution and mostly noise far down the ranking, so the fix is to sample from a reshaped, truncated distribution. Each of the dials below is one way of doing that.

Temperature rescales before sampling. Dividing every logit \(o_x\) by a temperature \(T > 0\) gives

\[P_T(x \mid x_{<t}) = \frac{\exp(o_x / T)}{\sum_{x' \in \mathcal{V}} \exp(o_{x'} / T)} \propto P(x \mid x_{<t})^{1/T}. \tag{8.7.4}\]

At \(T = 1\) we sample the model as-is; as \(T \to 0\) the distribution sharpens toward its mode and sampling becomes greedy decoding; as \(T\) grows it flattens toward uniform. Temperature trades diversity against safety smoothly, but it reshapes head and tail together: cooling the distribution enough to suppress the tail also crushes legitimate variety at the head.

Top-\(k\) truncates by count: keep the \(k\) most probable tokens, renormalize, and sample (Radford et al. 2019). Top-\(p\) (or nucleus) sampling truncates by mass: keep the smallest set of most-probable tokens whose cumulative probability reaches \(p\), for example \(p = 0.9\) (Holtzman et al. 2020). The difference matters because the model’s confidence varies wildly from step to step. Where our model is nearly certain of the next token, a fixed \(k = 20\) needlessly admits nineteen bad options; mid-sentence, where dozens of words are genuinely plausible, the same \(k\) may cut off real diversity. Top-\(p\) adapts better, keeping few tokens when the head is heavy and many when it is flat, but it too misbehaves on peaked distributions: if the top token already holds 0.95 of the mass, top-\(p\) with \(p = 0.9\) keeps exactly one token and acts greedily even where the runner-up was perfectly acceptable.

Min-\(p\) scales the cutoff by the model’s own confidence (Nguyen et al. 2025): keep every token whose probability is at least \(p_{\min}\) times that of the most probable token, e.g. \(p_{\min} = 0.05\). When the model is sure, the bar is high and few tokens pass; when the model is uncertain, the bar drops and the genuine variety survives. This relative rule holds up notably better at high temperatures, where creative sampling wants to operate and where absolute-threshold rules admit the noise floor wholesale.

8.7.4.1 A Unified Sampler

All four dials act on the same object, the next-token distribution, so a single function can host them. sample_next turns one vector of logits into one token id: greedy if asked, otherwise temperature-scaled sampling after optional top-\(k\), top-\(p\), and min-\(p\) truncation. Note how each truncation rule is just a different cut of the same sorted-by-probability order, a pure function of the distribution; we exploit that shortly to visualize all three at once. Like beam_search it is written in plain Python, and it draws through an explicit rng (anything with a random() method, such as numpy.random.default_rng(seed)) so that generation is reproducible.

def sample_next(logits, strategy='greedy', temperature=1.0,
                k=None, p=None, min_p=None, rng=None):
    """Choose the next token id from a 1-D numpy logits array.
    strategy: 'greedy' | 'sample' (with optional top-k / top-p / min-p
    truncation applied to the temperature-scaled distribution)."""
    logits = [float(l) for l in logits]
    if strategy == 'greedy' or temperature == 0:
        return max(range(len(logits)), key=lambda i: logits[i])
    m = max(logits)
    probs = [math.exp((l - m) / temperature) for l in logits]
    total = sum(probs)
    probs = [q / total for q in probs]
    order = sorted(range(len(probs)), key=lambda i: -probs[i])
    keep = len(order)
    if k is not None:  # Top-k: the k most probable tokens
        keep = min(keep, k)
    if p is not None:  # Top-p: smallest head with cumulative mass >= p
        mass, n = 0.0, 0
        while mass < p and n < len(order):
            mass, n = mass + probs[order[n]], n + 1
        keep = min(keep, n)
    if min_p is not None:  # Min-p: within a factor of the top token
        bar = min_p * probs[order[0]]
        keep = min(keep, sum(q >= bar for q in probs))
    kept = order[:keep]
    rng = random if rng is None else rng
    r = rng.random() * sum(probs[i] for i in kept)
    for i in kept:
        r -= probs[i]
        if r <= 0:
            return i
    return kept[-1]

generate is the loop we have been writing by hand all along: query step_fn, choose via sample_next (extra keyword arguments pass straight through to it), append, and stop early if an end-of-sequence token appears. Open-ended generation has no such token, so our demonstrations simply run for a fixed length; the translation models of the next chapter set eos_id and let the model decide when it is done.

def generate(step_fn, prefix, num_tokens, eos_id=None, **strategy):
    """Autoregressive generation. step_fn(ids: list[int]) -> numpy logits
    for the next token. Returns prefix + continuation (stops on eos_id)."""
    ids = list(prefix)
    for _ in range(num_tokens):
        ids.append(sample_next(step_fn(ids), **strategy))
        if eos_id is not None and ids[-1] == eos_id:
            break
    return ids

A toy distribution makes the truncation rules concrete. Five tokens carry probabilities 0.45, 0.25, 0.15, 0.10, and 0.05. Top-\(k\) with \(k = 2\) may only ever emit tokens 0 and 1; top-\(p\) with \(p = 0.85\) keeps three tokens, since the cumulative mass first reaches 0.85 at the third; min-\(p\) with \(p_{\min} = 0.5\) keeps the tokens with probability at least \(0.5 \times 0.45 = 0.225\), which is again tokens 0 and 1.

logits, rng = np.log([0.45, 0.25, 0.15, 0.1, 0.05]), np.random.default_rng(0)
print('greedy:', sample_next(logits))
for dial in (dict(k=2), dict(p=0.85), dict(min_p=0.5)):
    draws = [sample_next(logits, strategy='sample', rng=rng, **dial)
             for _ in range(15)]
    print(dial, draws)
greedy: 0
{'k': 2} [0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1]
{'p': 0.85} [0, 2, 1, 0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 1, 1]
{'min_p': 0.5} [1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]

8.7.4.2 One Distribution, Three Cutoffs

Toy numbers are one thing; here is the real object every dial acts on. We query the trained model once and plot its entire next-token distribution, sorted by decreasing probability, on logarithmic axes (the shape is Zipf-like, as Section 8.3 would lead us to expect). On this plot each truncation rule is a single line. Top-\(k\) is a vertical cut at rank \(k\), wherever the probabilities happen to lie. Top-\(p\) is a vertical cut at the rank where the cumulative mass reaches \(p\), so its position slides with the shape of the head. Min-\(p\) is a horizontal cut at \(p_{\min}\) times the top probability: every token above the line survives, and the line itself rides up and down with the model’s confidence. Everything below and to the right of the cuts is the unreliable tail that truncation exists to remove.

def next_probs(text):  # Sorted next-token distribution after a prefix
    logits = step_fn(data.tokenizer.encode(text))
    probs = np.exp(logits - logits.max())
    return np.sort(probs / probs.sum())[::-1]

probs = next_probs('the time traveller')
n_p = int((np.cumsum(probs) < 0.9).sum()) + 1
n_m = int((probs >= 0.05 * probs[0]).sum())
d2l.set_figsize((5.5, 3))
d2l.plt.loglog(np.arange(1, len(probs) + 1), probs, color='C0')
d2l.plt.axvline(20, color='C1', ls='--', label='top-k, k=20')
d2l.plt.axvline(n_p, color='C2', ls='-.', label=f'top-p=0.9: keep {n_p}')
d2l.plt.axhline(0.05 * probs[0], color='C3', ls=':',
                label=f'min-p=0.05: keep {n_m}')
d2l.plt.xlabel('token rank')
d2l.plt.ylabel('probability')
d2l.plt.legend()
<matplotlib.legend.Legend at 0x7b94dd3b32c0>

<matplotlib.legend.Legend at 0x73b5d87d9880>

<matplotlib.legend.Legend at 0x7796b43d4cb0>

<matplotlib.legend.Legend at 0x76b93a316000>

The adaptivity argument is now checkable: apply the same dials after two different prefixes and compare the kept sets. Top-\(k\) keeps twenty tokens regardless. The other two rules track the model’s confidence (how confident it is after a given prefix varies from training run to training run; the printed top probability tells you what this one thinks): the more certain the model, the smaller the top-\(p\) and min-\(p\) sets tend to be. That is the behavior we wanted: strict where the model is sure, permissive where it is genuinely uncertain.

for text in ('the time traveller', 'it seemed to me that'):
    probs = next_probs(text)
    n_p = int((np.cumsum(probs) < 0.9).sum()) + 1
    n_m = int((probs >= 0.05 * probs[0]).sum())
    print(f'{text!r}: top prob {probs[0]:.2f}, top-k keeps 20, '
          f'top-p keeps {n_p}, min-p keeps {n_m}')
'the time traveller': top prob 0.11, top-k keeps 20, top-p keeps 179, min-p keeps 26
'it seemed to me that': top prob 0.31, top-k keeps 20, top-p keeps 76, min-p keeps 6
'the time traveller': top prob 0.07, top-k keeps 20, top-p keeps 149, min-p keeps 42
'it seemed to me that': top prob 0.20, top-k keeps 20, top-p keeps 53, min-p keeps 11
'the time traveller': top prob 0.12, top-k keeps 20, top-p keeps 122, min-p keeps 27
'it seemed to me that': top prob 0.11, top-k keeps 20, top-p keeps 120, min-p keeps 37
'the time traveller': top prob 0.28, top-k keeps 20, top-p keeps 40, min-p keeps 12
'it seemed to me that': top prob 0.14, top-k keeps 20, top-p keeps 56, min-p keeps 20

8.7.4.3 The Same Prefix Under Every Strategy

Time to hear the dials rather than plot them. First, temperature alone: at \(T = 0.5\) the text hugs the model’s mode and inherits some of greedy’s repetitiveness, at \(T = 1\) it is diverse but occasionally derails into tail nonsense, already reaching for tokens whose bytes no longer decode to valid text (the replacement characters below), and at \(T = 2\) the flattened distribution produces gibberish outright.

prefix = data.tokenizer.encode('the time traveller')
for T in (0.5, 1.0, 2.0):
    out = generate(step_fn, prefix, 50, strategy='sample', temperature=T,
                   rng=np.random.default_rng(0))
    print(f'T={T}: {data.tokenizer.decode(out)!r}')
T=0.5: "the time travellerley of the future. The Medical Man.\n\n'There was the\ntime.\n\n'I so up the\nconditions of the\nhaster, the\nfeight and the\nha"
T=1.0: 'the time traveller of the\nsal car new and tchle of nected\npe-worldcle to tendill-�by, but even a\nreyer was only necay upon mystand cl\nexpl t'
T=2.0: 'the time traveller fo could\nfU inch could co�ps eyes. alverty bageibly the slowofust follow Medicalought ey off satig bet they into its�very time she tcl Time under\x07 an black spolog'
T=0.5: "the time travellerce a\nbut in.\n\n'That's guessy, I saw\nstrdle. L\n\n\nmake, and I\npresently read\nscessively\nfour;"
T=1.0: 'the time travellers and.\nI either him to and approumpessity upon me. It was\nbeto either� lever of proenox orually the twoworic, and gallery were very siln'
T=2.0: 'the time traveller hech.\near�ich part seemed� along the they wereullh�ffently once;off perhaps onlyndwas above under such betbleag arearereive\x06istme aser j onether; round witheen'
T=0.5: "the time traveller.\n\n'And all the Time Machine was aw, a loolishs of\nailing to crevised\nthe bushes,\ninto the\ntime is jumping."
T=1.0: 'the time travellerways, and tritues meward is\nown the Dim come--tate, be, or as itAciort;ite was a walkedantedderable direction with his teron'
T=2.0: 'the time travellerhe. I\nkeven an was which�ect\n wor a at his alersing last a sebe intuspedlfone tooings triedery youing sleto doworldilwas Y we pazeared s clamach'
T=0.5: 'the time traveller I had come into my hand. I thought, for a small shadows. I was a vast array I that my tanger. I felt a valthyoins. Indeed, and sat'
T=1.0: 'the time travelleriveley. (ason b another queuge and ta-haoces I scattered� lirial swific earlyt. Oittly comfort. I should a shome'
T=2.0: "the time traveller from lesseres� pl her long At perhaps a ruin necileking my to myself, incenseace from<pad>\x14ren neous,'edolog surtingideitt incingsence had part lastplacx toac"

Finally, the whole menu on one prefix, with the distinct-3 diversity score alongside. Greedy is deterministic and generic, when not stuck in a loop outright; pure sampling is diverse but erratic; the truncated samplers occupy the useful middle, keeping the diversity that maximization destroyed (their distinct-3 stays near 1) while cutting the tail that pure sampling trips over. This is why some combination of temperature with top-\(p\) or min-\(p\) is the default in essentially every deployed text generator today.

strategies = {'greedy': dict(strategy='greedy'),
              'T=1.0': dict(strategy='sample'),
              'top-k': dict(strategy='sample', k=20),
              'top-p': dict(strategy='sample', p=0.9),
              'min-p': dict(strategy='sample', min_p=0.05)}
for name, s in strategies.items():
    out = generate(step_fn, prefix, 50, rng=np.random.default_rng(0), **s)
    print(f'{name:>7} (distinct-3 {distinct(out[len(prefix):]):.2f}): '
          f'{data.tokenizer.decode(out)!r}')
 greedy (distinct-3 0.35): 'the time traveller\nand startment of the\nsle of the\nside of the\nbut of the\nbut of the\nbut of the\nbut of the\nbut of the\nbut of the\nbut'
  T=1.0 (distinct-3 1.00): 'the time traveller of the\nsal car new and tchle of nected\npe-worldcle to tendill-�by, but even a\nreyer was only necay upon mystand cl\nexpl t'
  top-k (distinct-3 1.00): 'the time travellerster.\nI cannot have\ncovering with the mor and sension of the panishing into masch and in the sch. The Psychologist trilph over. But there was\nfast'
  top-p (distinct-3 1.00): 'the time travellersuching\nconasp the last things, and Weena\nexpllance and the\nfelt the face of anyearartzen that the turnentif\nhad. You was unless palred\non'
  min-p (distinct-3 0.98): 'the time travellerally\ncame in my own me. (asching.\nThey were\ndown into a little c beonve I had the Time Machine, and the machine there of the\nnold\ndown-wor'
 greedy (distinct-3 0.85): 'the time traveller the\nside, I saw\nlittleess of the\nfour of the floor of the\nsunned and\npresented\ntheseength, the\nfour of the faint of'
  T=1.0 (distinct-3 1.00): 'the time travellers and.\nI either him to and approumpessity upon me. It was\nbeto either� lever of proenox orually the twoworic, and gallery were very siln'
  top-k (distinct-3 1.00): "the time travellerces, and I went downsetulate\nMy and\ns the breathing of detewomion, it's have been during. Soets and spiming. For\nmyself he"
  top-p (distinct-3 1.00): "the time travellercondon of white had come me thinks upon\nthated; and eitherance of\nbacstand. So who Man oner, and disappceptuooing.\n\n'Aman, and you"
  min-p (distinct-3 1.00): "the time traveller\nthereenumy of a marms of us. 'I bewered.\n\n'Tondeedorce the\nwellorner, the night, and that was the starteroots!"
 greedy (distinct-3 0.98): "the time travellerfer. I had a vast\n'I think that the\nshass.\n\n'I cannot tired, I saw a\nmane, and\nthere I was in\nthese, and"
  T=1.0 (distinct-3 1.00): 'the time travellerways, and tritues meward is\nown the Dim come--tate, be, or as itAciort;ite was a walkedantedderable direction with his teron'
  top-k (distinct-3 1.00): 'the time travelleres the little people and so I could, this is a a garden Pget. I\nI think I\nshumpes\nthe keening. But a civils. Ifing a\nco'
  top-p (distinct-3 1.00): 'the time travellergan, and disanee, stuming his\nthe lootter to finnered\nt herens a the\ndurriedin, trimension in fact isD I not\nsa'
  min-p (distinct-3 0.98): "the time traveller, and I was neveress, and I learn,\nunooked\ntrecial. Sbab me and cral, I thought.\n\n'One mightre my balss, in\nit"
 greedy (distinct-3 0.35): 'the time traveller I had come into the future. I was a vast array of a vast array of a vast array of a vast array of a vast array of a vast arr'
  T=1.0 (distinct-3 1.00): 'the time travelleriveley. (ason b another queuge and ta-haoces I scattered� lirial swific earlyt. Oittly comfort. I should a shome'
  top-k (distinct-3 1.00): "the time traveller by moderonke at it for any more. 'I supposit and course. It is this lit a civiliz. I felt asked in avolution. Instance of n"
  top-p (distinct-3 1.00): "the time traveller of a cigarened intoansites on ekingic were direain of the Time Traveller, however, catodous feet. 'Halloations togethering at elects of any kind r"
  min-p (distinct-3 1.00): 'the time traveller-sidered that, was the chinased me. And there are of our own time. What it was this yet railway to the shaday very. One nothing had flowers. I do'

Our small model cannot make any of these continuations good; what it makes visible is that they are different, in exactly the directions the theory predicts, and the differences only grow with model quality. The same dials, at the same typical settings, ship in every large language model API you will ever call.

8.7.5 Evaluation and Efficiency

8.7.5.1 Evaluating Generated Text

How would we decide, beyond eyeballing, which strategy wrote better text? Perplexity, our faithful metric so far, is of surprisingly little help. It evaluates the model: how well the predicted conditionals compress text that humans actually wrote. It says nothing about any particular sample, and scoring a sample by its own model probability would just reinvent maximization, crowning the repetitive beam-search output we have already rejected. A generation strategy is not better because its output is more probable; the whole point of the sampling family is to deviate from the mode on purpose.

The honest target is human judgment: can readers distinguish the model’s text from text people wrote, and which do they prefer? Alongside such judgments, automated proxies catch specific failure modes: diversity statistics such as our distinct-3 flag degeneration, and repetition and length statistics serve as cheap regression tests for a decoding stack. Tasks with a reference answer are easier to score; the next chapter evaluates translations by their overlap with reference translations, the setting where maximization and automatic metrics agree best.

At the frontier, evaluation has become a discipline of its own. Modern practice ranks systems by collecting human preferences between paired responses, and increasingly by asking a strong language model to play the judge, with well-documented blind spots of its own. We return to generation-quality evaluation in the context of large language models later in the book; for now, the operational summary is that perplexity selects the model, while humans, or proxies for them, select the decoding strategy.

8.7.5.2 The Cost of Generation

One last practical concern, and a preview. Our step_fn re-runs the network over the whole prefix for every token generated, so a \(T\)-token continuation costs \(\mathcal{O}(T^2)\) cell updates, and generation is inherently sequential: unlike training, where all time steps of a known sequence are processed together, token \(t + 1\) cannot be scored before token \(t\) exists. For a recurrent network the quadratic part is pure waste: the hidden state already summarizes the prefix, so carrying it forward (as predict in Section 8.5 did) makes each new token cost \(\mathcal{O}(1)\), independent of everything that came before. That constant-memory, constant-time-per-token property is a defining virtue of recurrence, and Chapter 12 builds architectures that keep it at much higher quality. The sequential bottleneck, meanwhile, has spawned a toolbox of its own, most prominently speculative decoding, where a small draft model proposes several tokens and the large model verifies them in one parallel pass; we return to serving-time efficiency when we meet large language models.

8.7.6 Summary

Decoding turns a language model’s conditionals into sequences, and the choice of strategy is a modeling decision in its own right. Maximization targets the most probable output: greedy decoding takes the local argmax and is myopic; beam search keeps the \(k\) best prefixes under the length-normalized score Equation 8.7.3 and fixes myopia at \(k\) times the cost. Maximization suits tasks with an essentially unique answer, but for open-ended text its target is wrong: the argmax of a good model is repetitive and dull, and a stronger search only finds it faster. Sampling draws from the model’s distribution, reshaped by temperature Equation 8.7.4 and truncated by top-\(k\) (fixed count), top-\(p\) (fixed mass), or min-\(p\) (fixed fraction of the top probability, hence adaptive to the model’s confidence). Perplexity evaluates the model rather than its samples; judging generated text requires humans or proxies for them. Finally, generating naively re-runs the model over a growing prefix for every new token; a recurrent state cuts this to constant work per token, a property the next chapter’s architectures inherit.

8.7.7 Exercises

  1. Implement a repetition penalty: in sample_next, divide the probability of every token already present in the generated sequence by a constant \(\theta > 1\) before truncation (you will need to thread the generated ids through). Decode greedily with \(\theta = 1.2\). Does it cure the loops? What legitimate text does it punish?
  2. In Figure 8.7.2, could the best candidate after three steps (by cumulative probability) fail to contain the best candidate after two steps as its prefix? Construct explicit probabilities or prove it impossible. What does your answer imply about how beam search can miss the true argmax sequence?
  3. Can exhaustive search be seen as a special case of beam search? For which beam size do the two coincide?
  4. Add an eos_id to the beam-search demonstration (for instance the token id of a newline) and vary \(\alpha \in \{0, 0.75, 1.5\}\) at \(k = 4\). Compare the lengths and scores of the winning candidates and explain the trend using Equation 8.7.3.
  5. At temperature \(T = 1.5\), tune \(p\) for top-\(p\) and \(p_{\min}\) for min-\(p\) until each just keeps continuations coherent. Which setting preserves more diversity (distinct-3) at matched coherence? Compare your finding with those of Nguyen et al. (2025) .
  6. Once you have trained the sequence-to-sequence translation model of the next chapter, decode it with beam_search for \(k \in \{1, 2, 4, 8, 16\}\). Measure translation quality and decoding time as functions of \(k\). Where does quality peak, and why does it not keep improving?
  7. Constrained sampling: ban a set of tokens (say, every token whose text contains the letter “e”) by masking their logits to \(-\infty\) before calling sample_next. Why is banning a word harder than banning a token under a subword tokenizer? What can go wrong at the boundary between two tokens?

Discussions