Decoding strategies
A language model only gives a probability for every next token; the decoding strategy decides which token is written. This session builds the main strategies step by step: greedy and beam search, sampling with temperature, top-k, top-p and min-p, repetition penalties, contrastive decoding, and constrained decoding that forces valid JSON with grammars.
What you will learn
- Greedy decoding and beam search, why beam search can miss the best sequence, and length normalization
- Why maximizing probability works for translation and captioning but makes open-ended text bland and repetitive
- Temperature, top-k, top-p (nucleus) and min-p: what each keeps, how they depend on temperature, and in which order engines apply them
- Repetition penalties (multiplicative, presence and frequency) and when they break code and JSON
- Contrastive decoding with an expert and an amateur model, and why it needs a plausibility constraint
- Constrained decoding: token masks from finite-state machines (Outlines) and pushdown automata (XGrammar), and what forcing a format does to quality
Why this matters
A language model does not write text. It gives a probability for every possible next token, and then something else picks one. That something is the decoding strategy. With the same weights, one strategy gives a dull loop, another gives good prose, and a third gives valid JSON every time.
In session 78 we saw the loop itself: prefill the prompt, then decode one token per step. This session is about the one line inside that loop that we skipped: “choose the next token from the logits”. It is cheap in compute, but it decides a lot of the quality you see. Every API exposes it (temperature, top_p, top_k, min_p, presence_penalty, response_format), and every serving engine (vLLM, SGLang, TensorRT-LLM, llama.cpp) implements it as a chain of small “logit processors”.
The ideas fall into four groups, and we take them in order:
- Search for the most likely text: greedy decoding and beam search. Good when there is one right answer (translation, speech recognition), bad for open text.
- Sampling with controls: temperature, top-k, top-p (nucleus) and min-p. The default for chat and creative text.
- Fixing the scores before choosing: repetition penalties, and contrastive decoding with a second, smaller model.
- Constraining the output to a language: regular expressions, grammars and JSON schemas, enforced by masking tokens.
One decoding step: from logits to a token
At step \(t\) the model reads the tokens so far, \(x_{\lt t}\), and outputs one score per vocabulary entry: the logits \(\mathbf{z} \in \R^{V}\). For Llama 3, \(V = 128{,}256\). The softmax turns them into a probability distribution:
A decoding strategy is a rule that maps this distribution (and maybe the history) to one token. In real engines it is a pipeline: first change the logits (penalties, masks), then reshape them (temperature), then cut the tail (top-k, top-p, min-p), then choose (argmax or a random draw). We will build each stage.
Greedy decoding and beam search
Greedy
The simplest rule: always take the token with the highest probability.
Greedy is deterministic, fast and has no settings. It is what “temperature 0” means in most APIs. Its problem: the best first token does not always start the best sentence. A token with a slightly lower probability can lead to a continuation that is much more likely in total.
Beam search
Beam search keeps the \(B\) best partial sequences (the beams), not only one. The score of a sequence is its total log-probability:
- Read the symbols
- \(x\)
- the prompt (or the source sentence in translation)
- \(y_{1:t}\)
- the output tokens so far, \(y_1\) to \(y_t\)
- \(B\)
- the beam width: how many partial sequences we keep (typical values 4 to 5 in translation)
- \(\log P\)
- we add log-probabilities instead of multiplying probabilities, which avoids numbers too small for floating point
At each step, every beam is extended by every token, giving \(B \times V\) candidates. We keep the \(B\) with the highest score and drop the rest. A beam that produces the end-of-sequence token is set aside as finished. With \(B = 1\), beam search is greedy decoding. Beam search is still a heuristic: the exact best sequence needs a search over \(V^{T}\) sequences, which is impossible, and beam search can miss it. Figure 1 shows both effects on a tiny example.
- input: prompt \(x\), model \(p\), beam width \(B\), maximum length \(T\)
- beams \(\leftarrow \{(\text{score} = 0,\ y = [\,])\}\); finished \(\leftarrow \{\}\)
- for \(t = 1\) to \(T\):
- candidates \(\leftarrow\) for each beam \((s, y)\) and each of its top-\(B\) tokens \(i\): \((s + \log p(i \mid y, x),\ y + [i])\) // only \(B\) per beam can survive
- beams \(\leftarrow\) the \(B\) candidates with the highest score // formula (79.3)
- move beams that end with EOS into finished
- if no beams are left: break
- return the finished (or remaining) sequence with the best length-normalized score // formula (79.4)
- Algorithm 1, live
- \(\text{beams} \leftarrow \{(0, [\text{The}])\}\); \(\text{finished} \leftarrow \{\,\}\)
- for \(t = 1, \dots, T\): for each beam \((s, y)\):
- for each token \(i\): \(\text{cand} \mathrel{+}= (s + \ln p(i \mid y),\ y + [i])\)
- \(\text{beams} \leftarrow\) the \(B\) candidates with the highest score
- move beams that end with EOS to finished
- if no beams are left: break
- return \(\argmax_{Y \in \text{finished}} \log P(Y) / \operatorname{lp}(|Y|)\)
How to read Figure 1
Press Play (or Step). Purple nodes are new candidates, blue nodes are the beams kept for the next step, faded nodes are pruned, and green nodes ended with ⟨eos⟩ and wait in the finished list. Greedy (\(B = 1\)) takes “dog” (0.5), then “barked” (0.4), then ⟨eos⟩ (0.55): log P \(= -2.207\), probability 0.110. With \(B = 2\), “cat” survives step 1, “cat sat” (0.36) is the best prefix at step 2, and “The cat sat ⟨eos⟩” finishes at step 3 with log P \(= -1.715\) (probability 0.180): a better sentence that greedy never sees. Now move \(\alpha\). With \(B = 2\), the longer “The cat sat down ⟨eos⟩” (\(-1.871\)) wins once \(\alpha\) passes about 0.74. With \(B = 3\), the beam also keeps “dog ran” at step 2, and “The dog ran away ⟨eos⟩” (\(-1.763\)) wins for \(\alpha\) above about 0.24. So the beam width and the length penalty both change the answer.
Greedy: \(\ln 0.5 + \ln 0.4 + \ln 0.55 = -0.693 - 0.916 - 0.598 = -2.207\), so \(P = 0.110\). Beam \(B = 2\): after step 1 the beams are “dog” \((-0.693)\) and “cat” \((-0.916)\). Step 2 has 6 candidates; the best two are “cat sat” \(-0.916 + \ln 0.9 = -1.022\) and “dog barked” \(-1.609\); “dog ran” \((-1.743)\) is pruned. At step 3, “cat sat ⟨eos⟩” \(= -1.022 + \ln 0.5 = -1.715\) is first and is finished; “cat sat down” \((-1.820)\) is kept, and ends at step 4 with \(-1.871\). With \(\alpha = 0\) the answer is “The cat sat”, \(P = e^{-1.715} = 0.180\), clearly better than greedy’s 0.110. With \(\alpha = 1\): \(-1.715 / (8/6) = -1.286\) against \(-1.871 / (9/6) = -1.248\), so the longer sentence wins.
Length normalization
Every extra token multiplies the probability by a number below 1, so the log-probability (79.3) always goes down as a sequence gets longer. Pure beam search therefore prefers short outputs and tends to stop early. Translation systems divide the score by a length penalty. The one from Google’s neural machine translation system (GNMT) is:
Here \(|Y|\) is the output length (in Figure 1 we count the ⟨eos⟩ token too) and \(\alpha\) sets the strength: \(\alpha = 0\) is no normalization, \(\alpha = 1\) is close to dividing by the length. GNMT tuned \(\alpha\) on a development set; it used \(\alpha = 0.2\) in most experiments, with a beam of 3 finished hypotheses. [Certain] Hugging Face’s length_penalty is a simpler version: it divides by \(|Y|^{\alpha}\). [Likely]
Hypothesis A has 3 tokens and \(\log P = -2.4\). Hypothesis B has 8 tokens and \(\log P = -3.6\). Raw scores: A wins (\(-2.4 \gt -3.6\)). With \(\alpha = 0.6\): \(\operatorname{lp}(3) = (8/6)^{0.6} = 1.188\) and \(\operatorname{lp}(8) = (13/6)^{0.6} = 1.590\), so A scores \(-2.020\) and B scores \(-2.264\): A still wins. With \(\alpha = 1\): A scores \(-2.4/1.333 = -1.800\) and B scores \(-3.6/2.167 = -1.662\): now B wins. Per token, B is clearly more likely (\(-0.45\) vs \(-0.80\)).
Where beam search works, and where it fails
Beam search works when the output is almost fixed by the input: translation, speech recognition, image or video captioning, summarization with short outputs. There the most likely output is usually a good output, and beam search finds better ones than greedy.
It fails for open-ended text (stories, chat, long answers). Holtzman et al. showed that text found by beam search (and greedy) is bland and often falls into repetition loops, and that the per-token probability of human text is, on average, much lower than that of beam-search text. [Certain] People do not choose the most likely next word; they say something informative. A model that is a little more confident each time it repeats a phrase will be pulled into a loop by any strategy that maximizes probability. This is sometimes called degeneration.
Sampling: temperature, top-k, top-p, min-p
The alternative to searching is sampling: draw the next token at random from the distribution (79.1). Pure sampling has the opposite problem. The vocabulary has over 100,000 tokens, and most of them are nonsense in any given place. Each one has a tiny probability, but together the tail can hold a few percent of the mass. Over hundreds of steps, a few nonsense tokens are almost certain to be drawn, and one bad token can derail everything after it. So we reshape the distribution before drawing.
Temperature
Divide the logits by a temperature \(T \gt 0\) before the softmax:
\(T = 1\) is the model’s own distribution. \(T \lt 1\) makes it sharper: big logits win even more. As \(T \to 0\), all mass goes to the top token and sampling becomes greedy. \(T \gt 1\) makes it flatter, giving more weight to the tail. Temperature never changes the order of the tokens, only how far apart their probabilities are.
Take \(\mathbf{z} = (2, 1, 0)\). At \(T = 1\): \((0.665, 0.245, 0.090)\). At \(T = 0.5\) (the logits become \((4, 2, 0)\)): \((0.867, 0.117, 0.016)\). At \(T = 2\): \((0.506, 0.307, 0.186)\). Lower temperature takes mass from the tail and gives it to the top.
Top-k
Keep only the \(k\) tokens with the highest probability, set the others to zero, and renormalize. Top-k sampling was popularized by story generation (Fan et al., 2018) and GPT-2 (with \(k = 40\) a common choice). [Likely] Let \(V_k\) be the set of the top \(k\) tokens:
The weakness of top-k is that \(k\) is fixed, but the shape of the distribution is not. After “The capital of France is”, almost all mass is on one token, and \(k = 40\) lets 39 bad tokens in. After “My favorite color is”, dozens of tokens are fine, and a small \(k\) cuts good ones. Figure 3 shows this.
Top-p (nucleus sampling)
Holtzman et al. proposed to fix the mass instead of the count. Sort tokens by probability and keep the smallest set whose total probability reaches \(p\). This set is the nucleus:
Then renormalize over \(V^{(p)}\) as in (79.6). When the model is sure, the nucleus is one or two tokens; when it is unsure, it is large. Typical values are \(p = 0.9\) to \(0.95\); the paper’s main setting was \(p = 0.95\). [Certain]
Min-p
Top-p still has a problem at high temperature. When the distribution is flat, reaching 90% of the mass may need hundreds of tail tokens. Min-p (Nguyen et al., ICLR 2025) uses a threshold that scales with the top probability \(p_{\max}\):
- Read the symbols
- \(p_{\max}\)
- the probability of the most likely token at this step
- \(p_{\text{base}}\)
- the min-p setting; the paper recommends 0.05 to 0.1
- \(V_{\min}\)
- the tokens that survive; then renormalize and sample as before
If the model is confident (\(p_{\max} = 0.9\)), with \(p_{\text{base}} = 0.1\) a token needs 0.09 to survive. If it is unsure (\(p_{\max} = 0.15\)), 0.015 is enough. In the paper, temperature is applied first and the threshold is computed on the result. [Certain] Taking logs of (79.8) gives a simple view in logit space:
So min-p keeps every token whose logit is within \(T \ln(1/p_{\text{base}})\) of the best one. With \(p_{\text{base}} = 0.1\) and \(T = 1\) the window is \(\ln 10 = 2.30\) nats. Doubling the temperature doubles the window. Other adaptive rules exist, such as locally typical sampling (Meister et al., 2022), which keeps tokens whose surprise is close to the average surprise; top-p and min-p are the ones most engines expose. Note: top-k does not depend on \(T\) at all (the order does not change), but top-p and min-p do.
- Algorithm 2, live
- \(z \leftarrow \text{model}(x)\)
- \(z_i \leftarrow z_i / \theta\) (\(z_i \cdot \theta\) if \(z_i \le 0\)) for seen \(i\)
- \(z \leftarrow z / T\)
- \(p \leftarrow \softmax(z)\)
- keep the \(k\) largest \(p_i\)
- keep the smallest top set with \(\sum p \ge p_{\text{top}}\)
- keep \(p_i \ge p_{\text{base}} \cdot p_{\max}\)
- \(q \leftarrow p / \sum_{\text{kept}} p\)
- \(u \sim U(0,1)\); return first \(i\) with \(\sum_{j \le i} q_j \gt u\)
How to read Figure 2
Press Play to run the nine stages; change any slider at any time and the current stage is recomputed. With the default settings (\(T = 0.8\), \(\theta = 1.3\), top-p 0.9): the penalty lowers “apple” from 3.00 to \(3.00/1.3 = 2.308\), below “banana” (2.40), so banana becomes the top token (0.258 after temperature). Top-p walks banana 0.258, apple 0.487, mango 0.644, orange 0.782, strawberry 0.865, “the” 0.910 and stops: 6 tokens holding 0.910 of the mass. After renormalizing, banana has \(0.258/0.910 = 0.283\), and seeded draw #1 (\(u = 0.032\)) picks “banana”. Set \(\theta = 1\) to remove the penalty, then compare temperatures: top-p 0.9 keeps 5 tokens at \(T = 0.7\), 7 at \(T = 1\) and 8 at \(T = 1.5\); min-p 0.1 (with top-p off) keeps 5, 7 and 9. “New draw” takes the next seed, so the same settings always give the same draws.
The top probabilities are apple 0.342, banana 0.188, mango 0.126, orange 0.114, strawberry 0.076, and the remaining seven tokens hold the rest. The entropy is 1.92 nats.
Top-k = 5 keeps 0.847 of the mass; after renormalizing, apple is \(0.342/0.847 = 0.404\). Top-p = 0.9: the running sum passes 0.9 at the 7th token (0.931), so 7 tokens survive. Min-p = 0.1: the threshold is \(0.1 \times 0.342 = 0.0342\), and 7 tokens are above it. “cheese” (0.004) and “zebra” (0.001) are removed by every filter.
How to read Figure 3
With top-k = 5, the peaked context keeps four bad tokens (“the”, “a”, “located”, “Lyon”) and the flat context drops five good colors that hold 38% of the mass. Switch to top-p = 0.9: the peaked context keeps only “Paris” (0.928) and the flat context keeps 9 colors. Min-p = 0.1 behaves the same way. The adaptive filters follow the model’s confidence; a fixed \(k\) cannot.
- input: logits \(\mathbf{z}\), history \(y\), settings \(\theta, \alpha_{\text{pres}}, \alpha_{\text{freq}}, T, k, p, p_{\text{base}}\), optional mask \(A\), random generator
- \(\mathbf{z} \leftarrow\) repetition penalties using the counts of tokens in \(y\) // formulas (79.10), (79.11)
- if a constraint is active: \(z_i \leftarrow -\infty\) for every \(i \notin A\) // formula (79.13)
- \(\mathbf{z} \leftarrow \mathbf{z} / T\) // (79.5); if \(T = 0\), return \(\argmax \mathbf{z}\)
- keep top-\(k\); then the nucleus \(V^{(p)}\); then \(V_{\min}\); set the rest to \(-\infty\) // (79.6) to (79.8)
- \(\mathbf{q} \leftarrow \softmax(\mathbf{z})\) // renormalizes over the survivors
- return a token drawn from \(\mathbf{q}\)
Repetition penalties
Sampling reduces loops, but models still repeat words, phrases and whole lines, especially small models and long outputs. A repetition penalty lowers the logits of tokens that already appeared. There are two common forms.
The multiplicative penalty (from the CTRL paper, Keskar et al., 2019) divides the logit of every token that appeared before by \(\theta \gt 1\). Hugging Face and vLLM implement it so that it always lowers the probability: positive logits are divided, negative ones are multiplied. [Likely]
CTRL reported that greedy decoding with \(\theta \approx 1.2\) gave a good balance between truthful text and little repetition. [Certain]
The additive penalties (the OpenAI style presence_penalty and frequency_penalty) subtract from the logit, based on how often token \(i\) appeared so far, \(c_i\):
- Read the symbols
- \(c_i\)
- how many times token \(i\) is already in the output (some engines also count the prompt)
- \(\alpha_{\text{freq}}\)
- frequency penalty: grows with every repeat, so it stops long loops
- \(\alpha_{\text{pres}}\)
- presence penalty: a fixed cost for any token seen at least once, which pushes toward new topics
- \(\mathbb{1}[\cdot]\)
- 1 if the condition is true, else 0
A third, blunt tool is no_repeat_ngram_size: forbid any \(n\)-gram that already appeared. It kills loops but also blocks needed repeats, such as a name used twice.
How to read Figure 4
With no penalty, “cats” has probability 0.601 and the loop continues. \(\theta = 1.3\) lowers “cats” from logit 4.0 to 3.08 (probability 0.381), but it is still first. Above \(\theta = 4.0/2.6 = 1.54\), “dogs” wins. Note the negative logits: “like” goes from −0.8 to −1.04 at \(\theta = 1.3\), lower, not higher, because negative logits are multiplied. Try presence 0.5 with frequency 0.5: “cats” drops by \(0.5 + 2 \times 0.5 = 1.5\) to 2.5, and “dogs” (0.302) wins.
Contrastive decoding
Many failures of a large model (repetition, generic phrases, copying the prompt) are shared with a small model of the same family, and are even stronger in the small one. Contrastive decoding (Li et al., 2022) uses this. It runs a large expert model and a small amateur model on the same text, and prefers tokens the expert likes much more than the amateur does:
- Read the symbols
- \(p_{\text{EXP}}, p_{\text{AMA}}\)
- the expert (for example OPT-13B) and the amateur (for example OPT-125M) distributions
- \(V_{\text{head}}\)
- the plausibility constraint: only tokens the expert itself finds reasonable can be chosen
- \(\alpha\)
- how strict the constraint is; the paper uses \(\alpha = 0.1\) everywhere
Why the constraint? A junk token with \(p_{\text{EXP}} = 0.002\) and \(p_{\text{AMA}} = 0.00001\) has a huge ratio (200). Without \(V_{\text{head}}\), it would win. Note that \(V_{\text{head}}\) has the same form as min-p (79.8). The paper searches for the CD score with beam search (beam 5) and reports better open-ended text than nucleus and top-k sampling, in both automatic and human evaluation. [Certain] The cost is a second model running in parallel. Do not confuse it with contrastive search (Su et al., 2022), a different method that penalizes tokens whose hidden state is too similar to earlier ones.
How to read Figure 5
At \(\alpha = 0.1\) the threshold is \(0.1 \times 0.32 = 0.032\): “Kenya” (0.03) and the junk sub-word “Hono” (0.002) are excluded. Among the rest, “1961” has the largest log ratio, \(\ln(0.26/0.03) = 2.16\). Move \(\alpha\) to 0: the constraint is gone, and “Hono” wins with \(\ln(0.002/0.00001) = 5.30\). That is exactly the failure the constraint prevents.
Constrained decoding: grammars and JSON schemas
Programs that read model output need it in an exact format: valid JSON for a tool call, one of four letters for a multiple-choice question, a timestamp like 00:01:23. Asking nicely in the prompt works most of the time. Constrained decoding makes it work every time: at each step, the tokens that would break the format get logit \(-\infty\), so their probability is exactly zero.
- Read the symbols
- \(s_t\)
- the state of a parser that has read the output so far
- \(A(s_t)\)
- the allowed tokens: those that keep the text a valid prefix of some string in the target language
- \(\delta\)
- the transition function: the new parser state after reading token \(x_t\)
Regular expressions and finite-state machines
A regular expression (and a JSON schema with no unbounded nesting can be turned into one) is equivalent to a finite-state machine (FSM) over characters. The hard part is that the model emits tokens, not characters, and one token can cover several characters, even across parts of the format (for example the token ", closes a string and adds a comma). Checking all 128,256 tokens against the machine at every step would be slow.
Outlines (Willard and Louf, 2023) solves this with an index. Before generation, for every FSM state, it walks every vocabulary token through the machine and stores which tokens are allowed and where they lead. During generation, getting the mask is a lookup. [Certain] The index is built once per (format, tokenizer) pair.
Context-free grammars and pushdown automata
Real JSON has nesting (objects inside lists inside objects) of any depth. That needs a context-free grammar (CFG), and the parser needs a stack: a pushdown automaton (PDA). Now the allowed tokens depend on the stack contents, and a full precomputed index is no longer possible. XGrammar (Dong et al., 2024) splits the vocabulary in two:
- Context-independent tokens: their validity depends only on the current grammar position, not on the rest of the stack. These are precomputed in an “adaptive token mask cache”.
- Context-dependent tokens: they must be checked at run time against the stack. XGrammar uses a persistent stack to make this fast.
For Llama 3.1 with a JSON grammar, the paper reports that context-dependent tokens are less than 1% of the vocabulary (1,134 of 128k). Mask generation takes under 40 µs per token for JSON schemas, and the grammar work runs on the CPU while the GPU computes the next logits, so the overhead in end-to-end serving is near zero. The paper reports up to 100× speedup over earlier solutions. [Certain] XGrammar is used as a structured-output backend in engines such as vLLM, SGLang and TensorRT-LLM. [Likely]
- input: grammar \(G\) (regex, JSON schema or CFG), tokenizer, model
- offline: compile \(G\) to an FSM or PDA; for each state, precompute the mask of tokens whose validity does not depend on the stack // Outlines index / XGrammar cache
- \(s \leftarrow\) start state
- repeat:
- \(\mathbf{z} \leftarrow\) model logits (GPU) // at the same time, on the CPU:
- \(A \leftarrow\) cached mask for \(s\), plus run-time checks for stack-dependent tokens
- \(z_i \leftarrow -\infty\) for \(i \notin A\); EOS is allowed only if \(s\) is an accepting state // formula (79.13)
- \(x \leftarrow\) greedy or sampled token from the masked logits (Algorithm 2)
- \(s \leftarrow \delta(s, x)\)
- until \(x\) = EOS
{"label": "cat" | "dog" | "bird", "conf": 0.D}, where D is one of 1, 5, 7, 9- Algorithm 3, live (greedy)
- \(z \leftarrow \text{model}(x_{\lt t})\); \(p \leftarrow \softmax(z)\)
- \(A \leftarrow\) tokens that keep the text a valid prefix in state \(s\)
- \(z_i \leftarrow -\infty\) for \(i \notin A\); \(p' = p / \sum_{j \in A} p_j\)
- \(x \leftarrow \argmax p'\)
- \(s \leftarrow \delta(s, x)\); append \(x\)
- until \(x = \text{EOS}\) (allowed only in the accepting state)
How to read Figure 6
At step 1 the model wants to say “Sure” (probability 0.626), as chat models often do; the grammar allows only {" and {, which together hold 0.234 of the mass, and {" gets \(p' = 0.230/0.234 = 0.982\). At step 5 the model wants “fish”, which is not in the enum (shown in red under the choice box); the allowed labels hold only 0.070 of the mass, and “dog” wins among them with \(p' = 0.432\). The output is always valid, but at such steps the constraint is overriding the model, not following it. Note also token boundaries: ", closes the string and adds the comma in one token, so the state jumps two characters. ⟨eos⟩ is allowed only at step 13, after }.
At step 5 of Figure 6, “fish” has 0.608 of the probability and the three allowed labels have 0.070 together. Renormalizing (79.13) multiplies their probabilities by \(1/0.070 \approx 14\). When the allowed mass is that small, the result is valid but may be wrong: the model was “thinking” of another answer. A good design lets the model reason in free text first and applies the format only to the final answer, or adds the needed options to the prompt.
Putting it together in PyTorch
The code below implements every strategy of this session on a toy “language model”: a fixed random table where the next-token logits depend only on the last token. It is deterministic (seeded), runs on a CPU in under a second, and its output is shown below it.
import torch torch.manual_seed(0) V = 50 # a toy vocabulary of 50 tokens TABLE = torch.randn(V, V) * 2.0 # toy "LM": next-token logits depend on the last token only def next_logits(seq): # seq: list of token ids -> logits of shape (V,) return TABLE[seq[-1]].clone() def apply_penalties(z, seq, rep=1.0, presence=0.0, frequency=0.0): counts = torch.bincount(torch.tensor(seq), minlength=V).float() seen = counts > 0 z = torch.where(seen & (z > 0), z / rep, torch.where(seen, z * rep, z)) # CTRL / HF style, formula (79.10) return z - frequency * counts - presence * seen.float() # OpenAI style, formula (79.11) def warp(z, temperature=1.0, top_k=0, top_p=1.0, min_p=0.0): z = z / temperature # formula (79.5) if top_k > 0: # formula (79.6) kth = torch.topk(z, top_k).values[-1] z = z.masked_fill(z < kth, float("-inf")) if top_p < 1.0: # formula (79.7) p, idx = torch.softmax(z, -1).sort(descending=True) drop = p.cumsum(-1) - p >= top_p # mass BEFORE this token already reached top_p z[idx[drop]] = float("-inf") if min_p > 0.0: # formula (79.8) p = torch.softmax(z, -1) z = z.masked_fill(p < min_p * p.max(), float("-inf")) return z def sample(prompt, n, gen, rep=1.0, presence=0.0, frequency=0.0, **kw): seq = list(prompt) for _ in range(n): z = apply_penalties(next_logits(seq), seq, rep, presence, frequency) z = warp(z, **kw) seq.append(torch.multinomial(torch.softmax(z, -1), 1, generator=gen).item()) return seq def greedy(prompt, n): seq = list(prompt) for _ in range(n): seq.append(next_logits(seq).argmax().item()) return seq def beam_search(prompt, n, k): beams = [(0.0, list(prompt))] # (sum of log-probs, tokens) for _ in range(n): cand = [] for score, seq in beams: logp = torch.log_softmax(next_logits(seq), -1) top = torch.topk(logp, k) # only k per beam can survive cand += [(score + v.item(), seq + [i.item()]) for v, i in zip(top.values, top.indices)] beams = sorted(cand, key=lambda c: -c[0])[:k] # formula (79.3) return beams[0] def seq_logprob(seq, start): return sum(torch.log_softmax(next_logits(seq[:t]), -1)[seq[t]].item() for t in range(start, len(seq))) g = greedy([0], 6); print("greedy ", g, round(seq_logprob(g, 1), 3)) s, b = beam_search([0], 6, 4); print("beam k=4", b, round(s, 3)) gen = torch.Generator().manual_seed(1) print("sampled", sample([0], 6, gen, rep=1.2, temperature=0.8, top_p=0.9)) # the filters on one distribution: how many tokens survive? z = next_logits([0]) for kw in [dict(), dict(top_k=5), dict(top_p=0.9), dict(min_p=0.1), dict(temperature=0.5, min_p=0.1)]: print(kw, "keeps", int(torch.isfinite(warp(z.clone(), **kw)).sum())) # repetition penalty pushes down seen tokens seq = [0, 7, 7, 7] z = next_logits(seq) zp = apply_penalties(z, seq, rep=1.3, presence=0.5, frequency=0.5) print("logit of token 7:", round(z[7].item(), 3), "->", round(zp[7].item(), 3)) # constrained decoding: mask everything outside an allowed set, then pick allowed = torch.zeros(V, dtype=torch.bool); allowed[[3, 11, 42]] = True zc = next_logits([0]).masked_fill(~allowed, float("-inf")) print("constrained pick:", zc.argmax().item(), "allowed mass:", round(torch.softmax(next_logits([0]), -1)[allowed].sum().item(), 3))
Output (PyTorch 2.8, CPU):
greedy [0, 45, 12, 5, 21, 14, 34] -7.429
beam k=4 [0, 45, 12, 1, 9, 2, 34] -6.078
sampled [0, 45, 12, 15, 39, 2, 47]
{} keeps 50
{'top_k': 5} keeps 5
{'top_p': 0.9} keeps 17
{'min_p': 0.1} keeps 5
{'temperature': 0.5, 'min_p': 0.1} keeps 2
logit of token 7: 3.239 -> 0.491
constrained pick: 11 allowed mass: 0.01
Three things to notice. Beam search found a sequence with log-probability \(-6.078\), much higher than greedy’s \(-7.429\), even though both start with the same two tokens. Min-p with \(T = 0.5\) keeps fewer tokens than with \(T = 1\) (2 vs 5), as (79.9) predicts. And the repetition penalty on token 7 (seen 3 times) gives \(3.239/1.3 - 0.5 \times 3 - 0.5 = 0.491\). In real engines the same chain runs on the GPU for the whole batch at once, with a different setting for each request.
Where this is used
| Task | Typical decoding | Why |
|---|---|---|
| Machine translation, speech recognition | Beam search, \(B\) around 4 to 5, with length normalization | One correct output; the most likely output is usually right |
| Image and video captioning | Beam search in classic captioning models; greedy or low temperature in VLMs [Likely] | Short, factual outputs that should match the content |
| Chat assistants | Sampling, \(T\) around 0.6 to 1.0 with top-p 0.9 to 0.95; model cards often give recommended values [Likely] | Natural, varied text without tail tokens |
| Creative writing, brainstorming | Higher \(T\) with min-p 0.05 to 0.1 | Min-p keeps text coherent even when the temperature is high |
| Code, math, extraction | Greedy or low \(T\); no repetition penalty | Exact tokens matter, and repeats are needed |
| Best-of-n, pass@k, RL rollouts (GRPO) | \(T\) around 0.6 to 1.0, many samples per prompt [Likely] | Diversity is the point; RL needs samples from the true policy (session 70) |
| Tool calls and agents | JSON-schema constrained decoding (Outlines, XGrammar) | A parser must read the call; one bad bracket breaks the agent (session 154) |
| Video key-moment detection, Video-RAG | Grammar-constrained JSON with timestamp fields, for example {"start": "00:01:23", "end": ...} | Downstream code cuts the clip or queries the index; timestamps must parse (session 210) |
| Video classification and multiple-choice video QA with a VLM | Constrain the answer to the label set or the letters A to D, then read the probabilities | Gives a valid label and a score usable for ranking or calibration |
Common mistakes
- Using beam search for chat or stories. It maximizes probability, which gives bland, repetitive text. Use sampling with top-p or min-p.
- Setting top-k and top-p and thinking they are independent. They run in sequence; the stricter one decides. Know your engine’s order (temperature before or after truncation changes the result for top-p and min-p).
- Expecting temperature 0 to be perfectly deterministic in production. Batching changes the order of floating-point sums, so two equal logits can swap. [Likely] For exact reproducibility, fix the batch, the kernels and the seed.
- Very high temperature without a filter. At \(T = 1.5\) the tail grows fast; one nonsense token can derail the rest. Pair high temperature with min-p.
- Repetition penalties on code or JSON. They punish the brackets and names that must repeat. Turn them off for structured output.
- Forgetting EOS in the constraint. If the grammar does not allow EOS in its accepting states, the model keeps generating; if it allows EOS too early, output is cut.
- Forcing a format that leaves the model no way out. A schema with no “unknown” option forces a guess. Add an escape value, and let the model reason before the constrained part.
- Comparing models with different decoding settings. Benchmark numbers change with temperature and sampling; report them (session 40).
Interview questions
Why does beam search work well for translation but badly for open-ended generation?core
What is temperature, and what happens at \(T \to 0\) and \(T \to \infty\)?basic
Compare top-k, top-p and min-p. When does each fail?core
Does the order of temperature and top-p matter?core
Why do repetition penalties divide positive logits but multiply negative ones?core
Explain contrastive decoding. Why is the plausibility constraint needed?advanced
How does a JSON mode guarantee valid JSON?core
Why is the token vocabulary the hard part of constrained decoding?advanced
", ends a string and adds a separator), and the vocabulary has over 100,000 entries. Naively, every step requires walking every token through the automaton. The solutions precompute token-to-state transitions per automaton state. With a CFG, validity can depend on the stack, so only part of the work can be cached; XGrammar reports that less than 1% of Llama 3.1 tokens are stack-dependent for JSON. Also, forcing a token sequence the model would not produce (unusual tokenization) can lower quality.Can constrained decoding make answers worse? How do you mitigate it?advanced
What is the cost of beam search in an LLM server, and why is it rarely used for chat?advanced
Why does length normalization matter for beam search?basic
Which decoding settings would you use for RL rollouts, and why not top-p 0.5?advanced
Exercises
- Compute the softmax of logits \((2, 1, 0)\) at \(T = 0.5\).
- In Figure 2 at \(T = 1\) with no repetition penalty (\(\theta = 1\)), how many tokens does top-p = 0.9 keep, and what is their total mass?
- With min-p \(p_{\text{base}} = 0.05\) and \(T = 1\), how far below the top logit can a token be and still survive? With \(T = 2\)?
- A token appeared twice and has logit \(-0.8\). What is its new logit with \(\theta = 1.3\)? With \(\alpha_{\text{freq}} = 0.5\) and \(\alpha_{\text{pres}} = 0.5\) instead?
- Beam search with \(B = 4\) over a vocabulary of 128,256 tokens. How many candidate scores exist per step, and how many do you really need to sort?
- In Figure 1 with \(\alpha = 1\), \(B = 2\) and \(B = 3\) return different sentences. Which candidate does \(B = 2\) prune, at which step, and why does that matter only when \(\alpha\) is large?
Answerscheck
Key takeaways
- Decoding turns the distribution (79.1) into tokens. Greedy (79.2) and beam search (79.3) maximize probability; they suit translation and captioning and need length normalization (79.4), but they make open text bland and repetitive.
- Sampling with temperature (79.5) plus truncation is the default for open text. Top-k (79.6) uses a fixed count; top-p (79.7) a fixed mass; min-p (79.8) a threshold relative to the top token, equal to a logit window \(T\ln(1/p_{\text{base}})\) (79.9).
- Repetition penalties (79.10, 79.11) lower the logits of seen tokens; use them gently, and not for code or JSON.
- Contrastive decoding (79.12) prefers what a large model knows and a small one does not, inside a plausibility set like min-p.
- Constrained decoding (79.13) masks tokens that break a grammar, using precomputed FSM indexes (Outlines) or PDA caches (XGrammar) with near-zero overhead. It guarantees format, not correctness.
Key formulas
References for this session
- Holtzman et al. (2019). The Curious Case of Neural Text Degeneration
- Nguyen et al. (2024). Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs
- Li et al. (2022). Contrastive Decoding: Open-ended Text Generation as Optimization
- Willard & Louf (2023). Efficient Guided Generation for Large Language Models
- Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
- Holtzman et al. (2019). The Curious Case of Neural Text Degeneration
- Nguyen et al. (2024). Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs
- Li et al. (2022). Contrastive Decoding: Open-ended Text Generation as Optimization
- Willard & Louf (2023). Efficient Guided Generation for Large Language Models
- Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
- Keskar et al. (2019). CTRL: A Conditional Transformer Language Model for Controllable Generation
- Wu et al. (2016). Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
- Fan, Lewis & Dauphin (2018). Hierarchical Neural Story Generation
- Su et al. (2022). A Contrastive Framework for Neural Text Generation
- Meister et al. (2022). Locally Typical Sampling
- Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs