LLM & VLM courseBlog
79Track 5: LLM inference and serving · session 2 of 65

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.

Time: 2.5 to 3 hours (reading 2 hours, exercises 45 minutes)Level: BeginnerBefore this: Sessions 3, 6 and 78

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:

  1. 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.
  2. Sampling with controls: temperature, top-k, top-p (nucleus) and min-p. The default for chat and creative text.
  3. Fixing the scores before choosing: repetition penalties, and contrastive decoding with a second, smaller model.
  4. 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:

\[ p(x_t = i \mid x_{\lt t}) = \softmax(\mathbf{z})_i = \frac{e^{z_i}}{\sum_{j=1}^{V} e^{z_j}} \tag{79.1} \]

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.

\[ x_t = \argmax_{i} \; p(x_t = i \mid x_{\lt t}) = \argmax_i \; z_i \tag{79.2} \]

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:

\[ \operatorname{score}(y_{1:t}) = \log P(y_{1:t} \mid x) = \sum_{s=1}^{t} \log p(y_s \mid y_{\lt s}, x) \tag{79.3} \]
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.

Algorithm 1: beam search with width \(B\)
  1. input: prompt \(x\), model \(p\), beam width \(B\), maximum length \(T\)
  2. beams \(\leftarrow \{(\text{score} = 0,\ y = [\,])\}\); finished \(\leftarrow \{\}\)
  3. for \(t = 1\) to \(T\):
  4.   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
  5.   beams \(\leftarrow\) the \(B\) candidates with the highest score // formula (79.3)
  6.   move beams that end with EOS into finished
  7.   if no beams are left: break
  8. return the finished (or remaining) sequence with the best length-normalized score // formula (79.4)
new candidatekept beamprunedfinished (ended with ⟨eos⟩)returned answer
  1. Algorithm 1, live
  2. \(\text{beams} \leftarrow \{(0, [\text{The}])\}\); \(\text{finished} \leftarrow \{\,\}\)
  3. for \(t = 1, \dots, T\): for each beam \((s, y)\):
  4. for each token \(i\): \(\text{cand} \mathrel{+}= (s + \ln p(i \mid y),\ y + [i])\)
  5. \(\text{beams} \leftarrow\) the \(B\) candidates with the highest score
  6. move beams that end with EOS to finished
  7. if no beams are left: break
  8. return \(\argmax_{Y \in \text{finished}} \log P(Y) / \operatorname{lp}(|Y|)\)
Formula with the live numbers
Figure 1. Beam search as a growing tree on a toy model after the prompt “The”, with at most 4 new tokens. Each column is one step. A node shows the token and the total log-probability of the path to it, formula (79.3); after ranking, the small #k is its rank among the candidates of that step. The pseudo-code line that is running is highlighted, and the box next to it shows the formula with the real numbers of this frame. The table lists the finished hypotheses and their length-normalized scores, formula (79.4).
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.

Worked example: the numbers in Figure 1

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:

\[ s(Y) = \frac{\log P(Y \mid X)}{\operatorname{lp}(Y)}, \qquad \operatorname{lp}(Y) = \frac{(5 + |Y|)^{\alpha}}{(5 + 1)^{\alpha}} \tag{79.4} \]

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]

Worked example: a short and a long translation

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:

\[ p_i(T) = \frac{e^{z_i / T}}{\sum_{j} e^{z_j / T}} \tag{79.5} \]

\(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.

Worked example: three logits

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:

\[ p'_i = \begin{cases} \dfrac{p_i}{\sum_{j \in V_k} p_j} & i \in V_k \\[4pt] 0 & \text{otherwise} \end{cases} \tag{79.6} \]

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:

\[ V^{(p)} = \text{the smallest set } S \text{ of top tokens with } \sum_{i \in S} p_i \ \ge\ p \tag{79.7} \]

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}\):

\[ V_{\min} = \{\, i \;:\; p_i \ \ge\ p_{\text{base}} \cdot p_{\max} \,\} \tag{79.8} \]
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:

\[ i \in V_{\min} \iff \frac{z_{\max} - z_i}{T} \ \le\ \ln \frac{1}{p_{\text{base}}} \tag{79.9} \]

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.

I just ate an apple. My favorite fruit is
model at \(T = 1\) (reference)current valuechanged by the penalty / drawn tokentop-p running sumremoved
  1. Algorithm 2, live
  2. \(z \leftarrow \text{model}(x)\)
  3. \(z_i \leftarrow z_i / \theta\) (\(z_i \cdot \theta\) if \(z_i \le 0\)) for seen \(i\)
  4. \(z \leftarrow z / T\)
  5. \(p \leftarrow \softmax(z)\)
  6. keep the \(k\) largest \(p_i\)
  7. keep the smallest top set with \(\sum p \ge p_{\text{top}}\)
  8. keep \(p_i \ge p_{\text{base}} \cdot p_{\max}\)
  9. \(q \leftarrow p / \sum_{\text{kept}} p\)
  10. \(u \sim U(0,1)\); return first \(i\) with \(\sum_{j \le i} q_j \gt u\)
Formula with the live numbers
Figure 2. One sampling step, stage by stage, after “I just ate an apple. My favorite fruit is” with 12 candidate tokens. The order is the one used by Hugging Face and the min-p paper: penalties, temperature, top-k, top-p, min-p, renormalize, draw. Stages 1 to 3 show logits; from stage 4 on the bars are probabilities. Every number is computed in your browser from the settings above.
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.

Worked example: the fruit distribution at \(T = 1\), no penalty (\(\theta = 1\))

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.

Figure 3. One filter setting on two contexts. Top: “The capital of France is” (peaked). Bottom: “My favorite color is” (flat). Blue tokens are kept, grey ones are removed. Bar heights are scaled to the top token of each context; the numbers are the real probabilities.
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.

Algorithm 2: one sampling step (the logit-processor chain)
  1. 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
  2. \(\mathbf{z} \leftarrow\) repetition penalties using the counts of tokens in \(y\) // formulas (79.10), (79.11)
  3. if a constraint is active: \(z_i \leftarrow -\infty\) for every \(i \notin A\) // formula (79.13)
  4. \(\mathbf{z} \leftarrow \mathbf{z} / T\) // (79.5); if \(T = 0\), return \(\argmax \mathbf{z}\)
  5. keep top-\(k\); then the nucleus \(V^{(p)}\); then \(V_{\min}\); set the rest to \(-\infty\) // (79.6) to (79.8)
  6. \(\mathbf{q} \leftarrow \softmax(\mathbf{z})\) // renormalizes over the survivors
  7. 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]

\[ z'_i = \begin{cases} z_i / \theta & \text{if } i \text{ appeared and } z_i \gt 0 \\ z_i \cdot \theta & \text{if } i \text{ appeared and } z_i \le 0 \\ z_i & \text{otherwise} \end{cases} \tag{79.10} \]

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\):

\[ z'_i = z_i - \alpha_{\text{freq}} \cdot c_i - \alpha_{\text{pres}} \cdot \mathbb{1}[c_i \gt 0] \tag{79.11} \]
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.

I like cats. I like cats. I like
original logitlogit after penaltiestoken already seen (count shown)
Figure 4. Repetition penalties on the next token after a looping text. “cats”, “I”, “like” and “.” have each appeared twice. The readout gives the softmax probability of the top token.
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:

\[ \begin{gathered} \operatorname{CD}(i) = \begin{cases} \log p_{\text{EXP}}(i \mid x_{\lt t}) - \log p_{\text{AMA}}(i \mid x_{\lt t}) & i \in V_{\text{head}} \\ -\infty & \text{otherwise} \end{cases} \\[4pt] V_{\text{head}} = \{\, i : p_{\text{EXP}}(i \mid x_{\lt t}) \ge \alpha \max_w p_{\text{EXP}}(w \mid x_{\lt t}) \,\} \end{gathered} \tag{79.12} \]
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.

Barack Obama was born in Honolulu, Hawaii. He was born in
expert probabilityamateur probabilityCD score (log ratio)
Figure 5. Contrastive decoding on one step (toy numbers). The expert alone would copy “Honolulu” from the prompt. The amateur likes copying even more, so the contrast moves the choice to the new fact “1961”.
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.

\[ p'(i \mid x_{\lt t}) = \frac{p(i \mid x_{\lt t}) \cdot \mathbb{1}[\, i \in A(s_t) \,]}{\sum_{j \in A(s_t)} p(j \mid x_{\lt t})}, \qquad s_{t+1} = \delta(s_t, x_t) \tag{79.13} \]
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]

Algorithm 3: constrained decoding with a grammar
  1. input: grammar \(G\) (regex, JSON schema or CFG), tokenizer, model
  2. 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
  3. \(s \leftarrow\) start state
  4. repeat:
  5.   \(\mathbf{z} \leftarrow\) model logits (GPU) // at the same time, on the CPU:
  6.   \(A \leftarrow\) cached mask for \(s\), plus run-time checks for stack-dependent tokens
  7.   \(z_i \leftarrow -\infty\) for \(i \notin A\); EOS is allowed only if \(s\) is an accepting state // formula (79.13)
  8.   \(x \leftarrow\) greedy or sampled token from the masked logits (Algorithm 2)
  9.   \(s \leftarrow \delta(s, x)\)
  10. until \(x\) = EOS
Schema: {"label": "cat" | "dog" | "bird", "conf": 0.D}, where D is one of 1, 5, 7, 9
model’s own top choiceallowed by the grammarchosen (highest p′ among allowed)masked (probability set to 0)
  1. Algorithm 3, live (greedy)
  2. \(z \leftarrow \text{model}(x_{\lt t})\); \(p \leftarrow \softmax(z)\)
  3. \(A \leftarrow\) tokens that keep the text a valid prefix in state \(s\)
  4. \(z_i \leftarrow -\infty\) for \(i \notin A\); \(p' = p / \sum_{j \in A} p_j\)
  5. \(x \leftarrow \argmax p'\)
  6. \(s \leftarrow \delta(s, x)\); append \(x\)
  7. until \(x = \text{EOS}\) (allowed only in the accepting state)
Formula with the live numbers
Figure 6. Greedy constrained decoding with a 27-token toy vocabulary, three frames per token: the model scores every token, the grammar masks the tokens that would break the schema, and the best allowed token is appended. The top diagram is the schema as a chain of grammar states: green characters are already written, the triangle marks the next character, and the dashed boxes are choice points. Each chip shows its probability (after masking: the renormalized p′). Tokens that contain a space are shown in quotes; the space inside the quotes, as in “ Here”, is part of the token.
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 }.

Worked example: how much the mask changes the distribution

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

TaskTypical decodingWhy
Machine translation, speech recognitionBeam search, \(B\) around 4 to 5, with length normalizationOne correct output; the most likely output is usually right
Image and video captioningBeam search in classic captioning models; greedy or low temperature in VLMs [Likely]Short, factual outputs that should match the content
Chat assistantsSampling, \(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, brainstormingHigher \(T\) with min-p 0.05 to 0.1Min-p keeps text coherent even when the temperature is high
Code, math, extractionGreedy or low \(T\); no repetition penaltyExact 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 agentsJSON-schema constrained decoding (Outlines, XGrammar)A parser must read the call; one bad bracket breaks the agent (session 154)
Video key-moment detection, Video-RAGGrammar-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 VLMConstrain the answer to the label set or the letters A to D, then read the probabilitiesGives 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
In translation the output is almost determined by the input, so the most likely output is usually a good one, and beam search finds more likely outputs than greedy. In open-ended text many continuations are good, and the most likely one is bland. Models also become more confident each time they repeat a phrase, so probability-maximizing search falls into loops. Holtzman et al. showed that human text has much lower per-token probability than beam-search text. So for open text we sample instead, with truncation (top-p, min-p).
What is temperature, and what happens at \(T \to 0\) and \(T \to \infty\)?basic
Temperature divides the logits before the softmax: \(p_i \propto e^{z_i/T}\). It keeps the token order but changes how peaked the distribution is. As \(T \to 0\), all mass goes to the argmax and sampling becomes greedy decoding. As \(T \to \infty\), the distribution becomes uniform over the vocabulary. Example: logits \((2, 1, 0)\) give \((0.665, 0.245, 0.090)\) at \(T = 1\) and \((0.867, 0.117, 0.016)\) at \(T = 0.5\).
Compare top-k, top-p and min-p. When does each fail?core
Top-k keeps a fixed number of tokens. It fails because the right number changes with context: a peaked distribution needs 1 to 2 tokens, a flat one needs dozens. Top-p keeps the smallest set with total mass at least \(p\), so it adapts: one token when the model is sure, many when it is not. It can still let in a long tail when the distribution is very flat, for example at high temperature. Min-p keeps tokens with \(p_i \ge p_{\text{base}} p_{\max}\), a threshold relative to the top token, which equals a fixed logit window \(T\ln(1/p_{\text{base}})\). It stays coherent at high temperature. All three remove the junk tail; they differ in how they decide where the tail starts.
Does the order of temperature and top-p matter?core
Yes. Top-k does not depend on temperature, because temperature keeps the order. Top-p and min-p do: lower temperature sharpens the distribution, so the nucleus for \(p = 0.9\) contains fewer tokens. In the fruit example, top-p 0.9 keeps 5 tokens at \(T = 0.7\), 7 at \(T = 1\) and 8 at \(T = 1.5\). Hugging Face and the min-p paper apply temperature first, then truncate. If an engine truncates first and then applies temperature, the same settings give a different distribution. Check your engine.
Why do repetition penalties divide positive logits but multiply negative ones?core
The goal is to lower the score of seen tokens. Dividing a positive logit by \(\theta \gt 1\) lowers it, but dividing a negative logit would raise it toward 0, which would make a seen token more likely. So the implementation multiplies negative logits by \(\theta\). A side effect: the effect depends on the logit's size and on the arbitrary zero point of the logits, unlike the additive presence and frequency penalties, which subtract a fixed amount per occurrence.
Explain contrastive decoding. Why is the plausibility constraint needed?advanced
Contrastive decoding scores each token by \(\log p_{\text{EXP}} - \log p_{\text{AMA}}\): how much more a large expert model likes it than a small amateur. Failures like repetition and generic words are shared (and stronger) in the amateur, so they cancel. But the ratio is also huge for junk tokens where both models are near zero (\(0.002 / 0.00001 = 200\)). The constraint \(V_{\text{head}} = \{i : p_{\text{EXP}}(i) \ge \alpha \max p_{\text{EXP}}\}\) with \(\alpha = 0.1\) allows only tokens the expert finds plausible. The cost is running a second model.
How does a JSON mode guarantee valid JSON?core
The schema or grammar is compiled into an automaton (an FSM for regular formats, a pushdown automaton for nested JSON). At each step the engine computes the set of tokens that keep the output a valid prefix, sets all other logits to \(-\infty\), and only allows EOS in accepting states. Then any decoding rule (greedy or sampling) can only produce valid text. To make it fast, masks are precomputed per state (Outlines) or for the context-independent tokens (XGrammar), and the mask is computed on the CPU while the GPU runs the model.
Why is the token vocabulary the hard part of constrained decoding?advanced
The grammar is defined over characters, but tokens are multi-character pieces that can cross grammar boundaries (a token like ", 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
Yes. The mask renormalizes over the allowed tokens. If the model put most mass elsewhere (for example on a label not in the enum, or on “I am not sure”), the output is valid but forced, and may be wrong. Mitigations: let the model reason in free text first and constrain only the final answer; put the allowed values in the prompt; include escape values like null or "unknown"; keep a natural key order; and measure task accuracy, not only the parse rate.
What is the cost of beam search in an LLM server, and why is it rarely used for chat?advanced
Each beam is a separate sequence, so \(B\) beams need about \(B\) times the decode compute and \(B\) KV caches (the prompt’s cache can be shared, and paged-attention engines share blocks copy-on-write). The candidate selection needs the top \(B\) tokens of each beam each step. It also complicates streaming, because the best beam can change, so tokens cannot be shown until beams agree. Since sampling gives better open-ended text anyway, chat servers almost always sample.
Why does length normalization matter for beam search?basic
Each token adds a negative log-probability, so the raw score always prefers shorter outputs and beam search tends to stop early. Dividing by a length penalty such as \(((5+|Y|)/6)^{\alpha}\) removes some of this bias. Example: 3 tokens at \(-2.4\) vs 8 tokens at \(-3.6\). Raw, the short one wins; with \(\alpha = 1\), the long one wins (\(-1.66\) vs \(-1.80\)).
Which decoding settings would you use for RL rollouts, and why not top-p 0.5?advanced
RL methods like PPO and GRPO assume the samples come from the policy whose log-probabilities are used in the loss. Strong truncation or low temperature changes the sampling distribution, so the stored log-probs no longer match, and diversity (needed to see different rewards within a group) drops. So rollouts usually use temperature near 1 with little or no truncation, and if a filter is used, the log-probs should be computed consistently with it. [Likely]

Exercises

  1. Compute the softmax of logits \((2, 1, 0)\) at \(T = 0.5\).
  2. 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?
  3. 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\)?
  4. 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?
  5. 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?
  6. 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
1. Logits become \((4, 2, 0)\); probabilities \((0.867, 0.117, 0.016)\). 2. 7 tokens with total mass 0.931 (after 6 tokens the sum is only 0.893). 3. \(\ln 20 = 3.00\) nats at \(T = 1\); \(2 \ln 20 = 5.99\) nats at \(T = 2\). 4. \(-0.8 \times 1.3 = -1.04\); with the additive penalties, \(-0.8 - 0.5 \times 2 - 0.5 = -2.3\). 5. \(4 \times 128{,}256 = 513{,}024\) candidates, but only the top 4 of each beam can be among the best 4 overall, so you need to sort only \(4 \times 4 = 16\). 6. At step 2 the candidates are cat sat \(-1.022\), dog barked \(-1.609\), dog ran \(-1.743\), …; \(B = 2\) keeps only the first two, so “dog ran” is pruned, although “dog ran away ⟨eos⟩” would end at \(-1.763\) (its next tokens have probability 0.99 each). With \(\alpha = 0\) this does not change the answer, because \(-1.715\) is still higher; with \(\alpha = 1\) it does: \(-1.763/1.5 = -1.175\) beats \(-1.248\).

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

\[ p_i(T) = \frac{e^{z_i/T}}{\sum_j e^{z_j/T}}, \qquad V^{(p)}: \sum_{i \in V^{(p)}} p_i \ge p, \qquad V_{\min}: p_i \ge p_{\text{base}}\, p_{\max} \]
\[ \operatorname{score}(y) = \sum_s \log p(y_s \mid y_{\lt s}, x), \qquad \operatorname{CD}(i) = \log \frac{p_{\text{EXP}}(i)}{p_{\text{AMA}}(i)}, \qquad p'_i \propto p_i \, \mathbb{1}[i \in A(s)] \]

References for this session

  1. Holtzman et al. (2019). The Curious Case of Neural Text Degeneration
  2. Nguyen et al. (2024). Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs
  3. Li et al. (2022). Contrastive Decoding: Open-ended Text Generation as Optimization
  4. Willard & Louf (2023). Efficient Guided Generation for Large Language Models
  5. Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
  6. Holtzman et al. (2019). The Curious Case of Neural Text Degeneration
  7. Nguyen et al. (2024). Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs
  8. Li et al. (2022). Contrastive Decoding: Open-ended Text Generation as Optimization
  9. Willard & Louf (2023). Efficient Guided Generation for Large Language Models
  10. Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
  11. Keskar et al. (2019). CTRL: A Conditional Transformer Language Model for Controllable Generation
  12. Wu et al. (2016). Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
  13. Fan, Lewis & Dauphin (2018). Hierarchical Neural Story Generation
  14. Su et al. (2022). A Contrastive Framework for Neural Text Generation
  15. Meister et al. (2022). Locally Typical Sampling
  16. Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs