Decoding and sampling

Logits → probabilities → one token

At each step the model produces logits $\mathbf{z}\in\mathbb{R}^{V}$ over the vocabulary. Softmax turns them into probabilities, we pick a token, append it, and run the next forward pass (cheaply, thanks to the KV cache — 7.10 Efficient inference: KV cache, GQA, FlashAttention, speculative decoding, quantization) until an end-of-sequence token or a length limit. Decoding strategies differ only in how we pick.

Greedy and beam search

Greedy decoding takes $\arg\max_i p_i$ every step. It is fast and fine for short, factual outputs and classification, but for open-ended text it produces loops ("I think that I think that…") and bland phrasing — the most probable next token repeatedly is not the most probable sequence, and not what humans write. Beam search keeps the $B$ best partial sequences by cumulative log-probability (with length normalization so short outputs are not favored). It shines in encoder–decoder tasks with a narrow correct answer — translation, speech recognition (7.7 Encoder–decoder: T5, BART and choosing an architecture) — and is rarely used for chat, where it amplifies repetition and genericness.

Temperature

Divide the logits by a temperature $T>0$ before the softmax:

$T\to0$ recovers greedy decoding; $T=1$ samples from the model's own distribution; $T>1$ flattens it, raising the entropy (1.9 Information theory: entropy, cross-entropy and KL divergence) and the chance of unlikely tokens. Temperature never reorders tokens — it only changes how peaked the distribution is.

Math check. Three logits $\mathbf{z}=(2,1,0)$. At $T=1$: $e^{2}=7.389, e^{1}=2.718, e^{0}=1$, sum $11.107$, so $p=(0.665, 0.245, 0.090)$. At $T=0.5$ the logits become $(4,2,0)$: $p=(0.867, 0.117, 0.016)$. At $T=2$ they become $(1, 0.5, 0)$: $p=(0.506, 0.307, 0.186)$. Same ranking, very different sharpness.

Truncation: top-k, top-p, min-p

Sampling from the full distribution occasionally picks a token from the long, low-probability tail — the source of many nonsense outputs. Truncation methods cut the tail, then renormalize:

• Top-k keeps the $k$ most probable tokens. Simple, but a fixed $k$ is too many when the model is confident and too few when it is not.
• Top-p (nucleus) keeps the smallest set of tokens whose cumulative probability reaches $p$ (e.g. 0.9). The set adapts: one token when the model is sure, dozens when it is uncertain.
• Min-p keeps tokens with $p_i \ge p_{\min}\cdot \max_j p_j$, scaling the cutoff with the model's confidence; it behaves well at high temperatures.

Implementations usually apply temperature first, then top-k, then top-p. Typical chat settings are $T\in[0.7,1.0]$ with top-p $0.9$–$0.95$; for extraction or code, $T\in[0,0.3]$.

Penalties, stops and biases

• Repetition penalty: divide the logits of already-generated tokens by $\theta>1$ (or subtract a constant); frequency/presence penalties subtract $\alpha\cdot\text{count}_i$ and $\beta\cdot\mathbb{1}[\text{count}_i>0]$. Mild values reduce loops; strong values forbid legitimate repeats (code!).
• No-repeat n-gram blocking: ban any $n$-gram that already occurred.
• Stop sequences end generation when a string appears (e.g. a closing tag); max tokens caps length.
• Logit bias: add a constant to chosen tokens' logits to encourage or forbid them (e.g. force a yes/no answer).

Constrained (grammar-guided) decoding

To guarantee valid JSON matching a schema, compute at each step the set of tokens that keep the output consistent with a grammar or finite-state machine compiled from the schema, and mask everything else (set their logits to $-\infty$) before sampling. Libraries such as Outlines, llguidance and the guided-decoding modes of vLLM implement this; provider APIs expose it as structured outputs. The model still chooses content; the grammar guarantees form. This is the backbone of reliable tool calling (10.2 Tool use and function calling) and structured extraction (9.6 Generation side: context assembly, citations, structured outputs and tool calling).

Determinism, seeds and reasoning models

Sampling with a fixed seed is reproducible in principle, but batched GPU kernels are not bit-exact across batch compositions and hardware, so even $T=0$ can produce different outputs across calls — "temperature 0" means mostly deterministic. Providers of reasoning models (8.6 Reasoning models and test-time compute) generally recommend leaving sampling at defaults ($T=1$, no top-p tweaks): the reasoning trace needs diversity, and the final answer is already filtered by the model's own verification.

Choosing settings

Speed tricks such as speculative decoding (7.10 Efficient inference: KV cache, GQA, FlashAttention, speculative decoding, quantization) draft tokens with a small model and verify them with the large one without changing the sampling distribution — decoding settings and inference optimization are separate concerns.

import torch

def sample_next(logits, temperature=1.0, top_k=0, top_p=1.0):
    if temperature <= 0:
        return int(torch.argmax(logits))
    logits = logits / temperature
    if top_k > 0:
        kth = torch.topk(logits, top_k).values[-1]
        logits = torch.where(logits < kth, torch.full_like(logits, -float("inf")), logits)
    probs = torch.softmax(logits, dim=-1)
    if top_p < 1.0:
        sorted_p, idx = torch.sort(probs, descending=True)
        cum = torch.cumsum(sorted_p, dim=-1)
        cut = cum - sorted_p > top_p          # tokens after the nucleus
        sorted_p[cut] = 0.0
        probs = torch.zeros_like(probs).scatter(0, idx, sorted_p)
        probs = probs / probs.sum()
    return int(torch.multinomial(probs, 1))

Where this shows up later

• Constrained decoding underlies structured outputs and tool calls — 9.6 Generation side: context assembly, citations, structured outputs and tool calling, 10.2 Tool use and function calling.
• Reasoning models shift control from sampling knobs to thinking budgets — 8.6 Reasoning models and test-time compute.
• Decoding is where inference cost is paid token by token — 7.10 Efficient inference: KV cache, GQA, FlashAttention, speculative decoding, quantization; evaluation must fix decoding settings to be reproducible — 8.7 Evaluating LLMs.