7  Decoding strategies

Next-token probabilities need a selection rule and repeated feedback to produce a generated sequence with fixed parameters.

A next-token model assigns probabilities to possible continuations but leaves the output token undecided. Generation selects a token, appends it to the prefix, and calculates another distribution from the longer input. The parameters stay fixed while the selected text changes the input to the next model calculation.

Three numbered panels are arranged in one row. Panel 7.1 loops from a token prefix through a fixed model and a selection rule back to a longer prefix. Panel 7.2 compares the original token distribution with temperature, top-k, top-p, and a combined sampling policy. Panel 7.3 shows two rounds of beam expansion, cumulative log scores, completed sequences, and pruning.
Figure 7.1: Section 7.1 repeats next token selection with fixed model parameters to build a sequence. Section 7.2 changes candidate probabilities with temperature, top-k, or top-p, then samples a token. Section 7.3 expands several candidate sequences, adds their log scores, and keeps the strongest beams until they finish or reach a stopping limit.

7.1 Next-token selection and the generation loop

A classifier can return one category after a single calculation. Generating text with a language model repeats the model calculation and token selection until a stopping condition is met. Each decoder step calculates the next-token logits for the available prefix. Softmax, as defined in §6.2, converts those scores into a vocabulary distribution, with one probability per possible next token:

\[ P(\mathrm{next}=i\mid\mathrm{context})=\operatorname{softmax}(\mathrm{logits})_i \tag{7.1}\]

Here \(i\) identifies a candidate token. Selecting a different token changes the prefix and can change every probability in the following step.

Greedy decoding selects a token with the highest current probability:

\[ \mathrm{next}=\operatorname*{arg\,max}_{i}p_i \tag{7.2}\]

The probabilities are \(p_i\). If several candidates share the maximum, this example chooses the lowest token ID. With finite logits and exact arithmetic, taking their maximum gives the same choice as taking the softmax maximum. The decision rule is deterministic for fixed computed scores and a fixed tie rule.

Example: Selection, appending, and stopping

Use three possible next-token IDs: 0 for cat, 1 for sat, and 2 for EOS. The prompt is the. Treat the following distributions as supplied model outputs for this small inference trace.

  1. For prefix the, probabilities are \((0.6,0.3,0.1)\). Greedy selection chooses ID 0, whose probability is 0.6. Appending it gives the cat.
  2. The fixed model receives that longer prefix. Its new probabilities are \((0.1,0.2,0.7)\). It selects ID 2 and appends EOS, ending this generation.

No reference answer or loss is needed for either choice. EOS marks completion, while a separate maximum-new-token limit can stop a sequence that never selects EOS. The displayed text normally omits this control marker.

Conclusion: One distribution supplied one decision. A second model calculation was necessary because the prefix changed. Appending tokens changed the inference state without changing any parameter.

Greedy choice does not examine the continuations that would follow a rejected token. Sampling can explore different prefixes, and beam search can keep several candidates.

7.2 Temperature, candidate filtering, and sampling

Drawing directly from the model distribution can select a low-probability token. A decoding policy can change the probability gaps or restrict the available candidates before that draw. These choices can change repetition and diversity. They do not establish whether the generated text is factually correct.

Temperature is a positive divisor on logits before softmax:

\[ p_i^{(\tau)}=\frac{e^{z_i/\tau}}{\sum_j e^{z_j/\tau}} \tag{7.3}\]

Here \(z_i\) is the logit of token \(i\) and \(\tau>0\) is the temperature. At \(\tau=1\), the original distribution is recovered. A larger divisor reduces score gaps, while a smaller divisor increases them. As \(\tau\) approaches zero, mass concentrates on the largest logits. Setting \(\tau=0\) in this formula is undefined. With tied maxima, this limit alone does not choose one token.

Let \(V\) be the prediction vocabulary and \(|V|\) its size. For filtering, sort its token indices as \((i_1,\ldots,i_{|V|})\) by decreasing probability, using token ID to break ties. Top-k sampling retains exactly the first \(k\) indices, for \(1\le k\le |V|\):

\[ S_k=\{i_1,\ldots,i_k\},\quad p_{i_1}\ge p_{i_2}\ge\ldots\ge p_{i_{|V|}},\quad 1\le k\le |V| \tag{7.4}\]

Top-p sampling, also called nucleus sampling, retains the shortest sorted prefix whose probability mass reaches or exceeds a threshold \(0<p_{\mathrm{top}}\le1\):1

\[ S_{p_{\mathrm{top}}}=\{i_1,\ldots,i_m\},\quad m=\min\left\{r:\sum_{j=1}^{r}p_{i_j}\ge p_{\mathrm{top}}\right\},\quad 0<p_{\mathrm{top}}\le1 \tag{7.5}\]

The support of a sampling distribution consists of candidates with nonzero probability. It equals the retained set when every retained probability is positive. Top-k fixes the retained count. Top-p can retain many candidates for a flat distribution and few for a concentrated one.

For either retained set \(S\), renormalization gives \(q_i=p_i/\sum_{j\in S}p_j\) within \(S\), and zero outside it. One possible combined policy applies temperature, top-k, renormalization, top-p, then final renormalization before sampling. The operation order is part of the policy. The following comparisons instead apply each change separately to show its effect.

Example: How the selection policy changes a draw

Start with \(z=[2,1,0]\). At temperature 1, softmax gives approximately \([0.665,0.245,0.090]\). Greedy choice is ID 0.

For a temperature-only comparison, set \(\tau=2\). Applying the temperature rule above scales the scores to \([1,0.5,0]\) and gives approximately \([0.506,0.307,0.186]\). The displayed probabilities are rounded and need not sum to exactly one.

For a separate filtering comparison, use the original temperature-1 probabilities. Top-k with \(k=2\) retains IDs 0 and 1, whose mass is approximately \(0.665+0.245=0.910\). Renormalization gives \([0.731,0.269,0]\).

Dividing \([0,1)\) at probability 0.731 gives a sampling interval for each retained token. A supplied uniform draw of 0.8 belongs to the second interval and selects ID 1. Appending that ID changes the prefix for the next model calculation.

Top-p need not retain the same number of tokens as top-k. Two further distributions show how its retained count depends on concentration:

  • For \(p=(0.30,0.25,0.25,0.20)\), top-k with \(k=2\) retains IDs 0 and 1 under the token-ID tie rule. Their mass is 0.55, giving approximately \((0.545,0.455,0,0)\) after renormalization. Top-p at 0.8 needs the first three entries, whose mass reaches 0.8 exactly, giving \((0.375,0.3125,0.3125,0)\).
  • For \(p=(0.90,0.05,0.05)\), top-p at 0.8 retains only ID 0, with probability 1 after renormalization. Top-k with \(k=2\) retains IDs 0 and 1, giving approximately \((0.947,0.053,0)\).

Conclusion: Top-p retained three candidates for the flatter distribution and one for the concentrated distribution, while top-k retained two in both. Filtering still allowed the earlier draw to select ID 1 rather than the greedy maximum.

Context-to-token diagram with separate descriptions of greedy selection, temperature, top-k, and top-p.
Figure 7.2: One-token selection connects context IDs, logits, probabilities, and a selected output.

The runnable PyTorch example takes four logits, applies temperature 0.8, and retains two candidates. torch.topk selects their scores and indices. Negative infinity excludes the other scores when torch.softmax normalizes them, using §6.3’s finite-maximum condition. Here both retained scores are finite. torch.multinomial then draws one retained ID.

Code example: Temperature and top-k filtering for one next-token decision

import torch

logits = torch.tensor([2.0, 1.0, 0.5, -1.0])
temperature = 0.8
top_k = 2

scaled = logits / temperature
values, indices = torch.topk(scaled, top_k)
filtered = torch.full_like(scaled, float("-inf"))
filtered[indices] = values
probabilities = torch.softmax(filtered, dim=-1)

print(probabilities)
print(torch.multinomial(probabilities, num_samples=1))

The probability vector is approximately [0.7773, 0.2227, 0, 0], and the sampled ID is 0 or 1. This is one selection, not the append-and-repeat loop. Its four logits are distinct, so it does not test the token-ID tie rule defined above. A general implementation must apply that rule explicitly when scores tie. The snippet uses the current random generator state. Reproducing a draw requires its seed or state, library version, device, and execution settings.

The transformers library exposes these choices through GenerationConfig and a model’s generate method. The configuration also specifies generated-length limits and EOS handling.2

Sampling commits to its selected prefix. Keeping several possible prefixes requires comparing their accumulated sequence probabilities.

7.3 Beam expansion, scoring, and pruning

The token with the highest current probability may lead to a less probable continuation than a competing token. Beam search retains several partial sequences, expands each, and keeps the best-scoring candidates after each step. Its beam width sets the maximum number of candidates retained at each pruning step in the example below.3

The sequence score is the sum of conditional log probabilities along a candidate:

\[ \operatorname{score}(y_{1:t})=\sum_{i=1}^{t}\log P(y_i\mid y_{<i},x) \tag{7.6}\]

Here \(x\) is the prompt, \(y_{1:t}\) is the generated prefix, and \(y_{<i}\) contains its earlier generated tokens. The probability chain rule multiplies the conditional probabilities. Taking a logarithm turns that product into the sum above. Larger scores, including less negative scores, rank higher.

Example: Two expansion and pruning steps

Use beam width 2, no sampling, natural logarithms, and no length adjustment. Tokens are A, B, and EOS, in that ID order. Ties use that order. The chosen stopping rule ends after two generated tokens or earlier EOS. A completed candidate keeps its score and is not expanded again.

At the first step, the supplied probabilities are \((0.5,0.4,0.1)\). Their scores are \(\log0.5\approx-0.693\), \(\log0.4\approx-0.916\), and \(\log0.1\approx-2.303\). The beam retains A and B and discards EOS.

For the next step, the model gives probabilities \((0.4,0.1,0.5)\) after A and \((0.1,0.2,0.7)\) after B. Each row sums to one. Expanding both retained prefixes produces six candidates.

Table 7.1: Expanding two retained prefixes gives six candidates. The two highest sequence probabilities belong to completed sequences.
Candidate Conditional probability Sequence probability Log score After pruning
A A 0.4 0.20 −1.609 Discard
A B 0.1 0.05 −2.996 Discard
A EOS 0.5 0.25 −1.386 Keep completed
B A 0.1 0.04 −3.219 Discard
B B 0.2 0.08 −2.526 Discard
B EOS 0.7 0.28 −1.273 Keep completed

The two highest scores retain B EOS and A EOS. Both are completed, so the search stops and returns B EOS. Greedy selection would first choose A and then EOS, giving probability 0.25 rather than 0.28.

Conclusion: Expanding both prefixes recovered a better completed sequence than greedy choice in this example. The comparison covers only the candidates retained by this finite search.

Pruning can remove the eventual best completion. In a separate vocabulary, let ordinary tokens A, B, and C have first-step probabilities \((0.40,0.35,0.25)\), with zero probability for EOS. Keep the same two-token stopping limit. Width 2 discards C. If C next assigns probability 1 to EOS, its completion has probability 0.25. If each retained prefix’s best next token has probability 0.4, their best two-token products are only 0.16 and 0.14. The discarded completion would have beaten both.

Longer sequences add more nonpositive log terms. A length penalty adjusts sequence scores to change that length preference. Its formula, completion handling, and stopping rule are choices that must accompany a beam result. The deterministic trace above does not describe beam sampling or every library configuration.

Beam search spends more computation and stores more partial sequences to explore alternatives. A higher model score still does not establish that the output is useful or true. The policy checks in §7.2 isolate token selection. Reference answers and losses, developed in Chapter 8, instead measure the probability assigned to recorded answers during training or evaluation, whether or not decoding would select them.

Chapter checkpoint

With sorted probabilities \((0.30,0.25,0.25,0.20)\), how do the retained sets differ between top-k with \(k=2\) and top-p at 0.8? What must happen after sampling one token? Does beam width 2 guarantee the globally best sequence?

Answer: Top-k retains the first two candidates. Top-p retains the smallest prefix with cumulative mass of at least 0.8, which contains the first three candidates. Each retained set is renormalized before sampling. The selected ID is appended, then the model calculates a new distribution unless a stopping rule applies. Width 2 can discard a prefix that would later lead to a higher-scoring completed sequence, so it gives no global guarantee.


  1. Holtzman, A., Buys, J., Du, L., Forbes, M., & Choi, Y. (2020). The Curious Case of Neural Text Degeneration. International Conference on Learning Representations, §3.1. The paper defines nucleus sampling and renormalization. The numerical examples here are illustrative.↩︎

  2. Hugging Face. (n.d.). Generation. Transformers documentation. Retrieved September 24, 2026. The interface supports greedy selection, sampling, and beam variants. The one-token code above does not call a pretrained model.↩︎

  3. Jurafsky, D., & Martin, J. H. (2026). Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition with Language Models. Third edition draft, released August 19, 2026, §13.4. The tie, completion, and stopping rules here are declared example conventions.↩︎