Sampling & decoding

Chapter 17 made the forward pass faster. Chapter 18 made it smaller. This chapter is about what happens after the forward pass: how a vector of logits, one score per vocabulary token, becomes the next emitted text token. The choice matters enormously. Greedy decoding produces robotic, repetitive output. Pure random sampling produces incoherent nonsense. Carefully-designed strategies (temperature + nucleus + a mild repetition penalty) produce natural, varied, useful text. The algorithms are short; the impact is huge.

This chapter walks through the canon: greedy (argmax) as the baseline; temperature as the global softening knob; top-k as fixed-size truncation; top-p (nucleus) sampling (Holtzman 2019) as the modern adaptive default; repetition penalties for loop prevention; beam search for the few cases where it still wins; and constrained decoding for production agents that need structured output. By the end you should know which sampling configuration to reach for in chat, code, creative writing, reasoning, and structured-output use cases, and why the production defaults are what they are.

And then Part VI is complete. Three chapters covered the full inference-engineering arc: cache + batching + Flash Attention + speculative + paging (Ch 17); quantization + NF4 + GPTQ + AWQ (Ch 18); and sampling (this chapter). Combined, these are the difference between a $50$-token-per-second research curiosity and a $500$-to-$1{,}000$-token-per-second production service. Part VII picks up with capabilities, reasoning, tools, retrieval, multimodal, the chapters that turn deployable models into useful systems.

From logits to text

The three steps

Every decode step inside an LLM has the same three-step shape. Logits come out of the forward pass: a vector $z \in \mathbb{R}^V$ where $V$ is the vocabulary size, typically $50{,}000$ to $200{,}000$ entries. Softmax turns that into a probability distribution: $p_i = \exp(z_i) / \sum_j \exp(z_j)$, with the standard max-subtraction trick for numerical stability (see Chapter 4’s derivation of scaled dot-product attention, where the same trick stabilizes the attention softmax). Sampling is the algorithm that picks a single token index $i^*$ from the distribution, and that index is the next emitted token. The forward pass is the same regardless of strategy; the sampler is what changes, and that third step is what this chapter is about.

Why this is microseconds

The forward pass dominates time per decode step, hundreds of milliseconds at scale, or tens of milliseconds in a well-optimized serving stack (Ch 17 §2 walked through why decode is memory-bound). Sampling is microseconds. Even an elaborate strategy, top-p plus a repetition penalty plus a constrained-decoding mask, runs in well under a millisecond per token. The sampler is not where the engineering effort is hardest, and it is not where the time is. But the impact on output quality is enormous: an order-of-magnitude difference in usefulness between greedy and a well-tuned nucleus configuration. The leverage ratio is the highest in Part VI, a few lines of Python transform the model’s user-facing behavior.

Greedy and temperature

Greedy decoding

Greedy decoding is the simplest possible sampler: emit the token with the highest logit at each step. It is deterministic, reproducible, and the obvious thing to try first. It is also wrong for most LLM use cases, for three connected reasons. Greedy loops: once the most-likely token at position $t$ becomes the most-likely token at position $t+1$, the same word can repeat (“the cat sat on the the cat sat on the”) because there is no randomness to break out of the attractor. Greedy is brittle: a single early misstep, like picking a slightly wrong noun, locks the rest of the sequence into a chain of conditioned errors that compounds. Greedy is robotic: human text has variation; greedy text does not, and the absence of variation reads as machine-generated even when the content is correct.

There are still cases where greedy is the right call. Short factual extraction (“what is the capital of France”), a code-completion site where the next token is genuinely the only sensible one, and any setting where reproducibility matters more than quality (testing, regression checks). But for chat-grade generation across hundreds of tokens, greedy underperforms moderate stochastic sampling by a wide margin, even on tasks that nominally have a single correct answer.

Temperature scaling

Temperature is the simplest stochastic generalization of greedy. Divide every logit by a scalar $T > 0$ before the softmax:

When $T = 1$, this is the model’s natural distribution, the same probabilities you would get by softmaxing the raw logits. When $T < 1$, the distribution sharpens: ratios between probabilities widen, the top token’s mass grows, and as $T \to 0$ the sampler collapses to greedy. When $T > 1$, the distribution softens: ratios shrink, mass spreads out, and as $T \to \infty$ the sampler approaches uniform random.

Typical values are well-established in practice. $T = 0$ (or near-zero) for factual extraction, structured tasks, and “definite” code tokens. $T = 0.7$ to $1.0$ for chat and instruction following, the default range for almost every chat API. $T = 1.2$ to $1.5$ for brainstorming, story writing, and other settings where diversity matters more than reliability. Above $T = 1.5$ the distribution becomes too flat to produce coherent text; the model emits random-looking tokens from the long tail and the output degrades fast.

The connection back to Ch 16 is worth noticing. Temperature here is the same mathematical operation as in distillation: divide logits by $T$ before softmax. There, high temperature revealed the teacher’s dark knowledge by softening its peaked distribution so that the student could learn from the relative ordering of unlikely classes. Here, temperature adjusts the creativity dial. Same math, different purpose, and the reuse is genuine, not coincidental, because both settings care about the same thing (how peaked or flat the distribution is) for different reasons.

import numpy as np

def softmax(z):
    z = z - z.max()
    e = np.exp(z)
    return e / e.sum()

def greedy(logits):
    """Emit argmax."""
    return int(np.argmax(logits))

def temperature_sample(logits, T=1.0, rng=None):
    """Sample from softened distribution."""
    if rng is None:
        rng = np.random
    p = softmax(logits / T)
    return int(rng.choice(len(p), p=p))

# Synthetic logits with one clear winner + several runners-up
np.random.seed(0)
V = 100
logits = np.random.normal(0, 1, V)
logits[5]  = 4.0   # clear winner
logits[12] = 2.5   # runner-up
logits[42] = 2.0   # distant third

print(f"Logits peak at token 5 (4.0); runner-up at 12 (2.5)\n")
print(f"{'Method':<22} | 10 samples")
print("-" * 70)
rng = np.random.RandomState(42)
for name, fn in [
    ("Greedy (T=0)",      lambda: greedy(logits)),
    ("Temp = 0.5 (sharp)", lambda: temperature_sample(logits, T=0.5, rng=rng)),
    ("Temp = 1.0 (raw)",   lambda: temperature_sample(logits, T=1.0, rng=rng)),
    ("Temp = 2.0 (soft)",  lambda: temperature_sample(logits, T=2.0, rng=rng)),
]:
    samples = [fn() for _ in range(10)]
    print(f"{name:<22} | {samples}")

print("\nObservations:")
print("- Greedy: always token 5 (deterministic, but boring)")
print("- T = 0.5: mostly 5, occasional 12 (sharp, conservative)")
print("- T = 1.0: balanced, 5 dominant, 12 and 42 appear sometimes")
print("- T = 2.0: random tokens from all over (too noisy)")

Top-k sampling

The tail-noise problem

Even at $T = 1$, the tail of the distribution still contributes occasionally. A long-tail token with probability $10^{-6}$ will be sampled roughly once in a million decode steps, rare but not zero, and in a $2{,}000$-token generation across many parallel sessions the rare events add up. Most of those tail tokens are nonsensical given the context: they are the model’s residual uncertainty leaking through, and when they leak they break coherence. The phenomenon has a name: tail noise, and it is the central reason raw temperature sampling underperforms truncated sampling for long-form generation.

The fix is to throw away the tail before sampling. There are two ways to do this, pick a fixed number of tokens to keep (top-k, this section), or pick a fixed amount of probability mass to keep (top-p, next section). Top-k is the older idea, and the simpler one.

Fixed-size truncation

Top-k sampling (Fan et al., 2018) keeps the $k$ highest-probability tokens, renormalizes, and samples from the truncated distribution. Sort logits descending, keep the first $k$ indices, set the rest to $-\infty$ (or equivalently, mask them out), softmax over what remains, and sample. The typical values are $k = 50$ (the historical default), $k = 40$ (chat configurations), and $k = 20$ (focused outputs like code completion). The cost is negligible; the implementation is a few lines.

The structural limitation of top-k is that $k$ is fixed regardless of distribution shape, and distribution shape varies enormously across decode steps. After a punctuation token the next-token distribution is wildly uncertain, many words could plausibly start the next sentence. After “the cat sat on the” the distribution is highly peaked, “mat” or “floor” dominate, and the third-most-likely token is much less plausible than the second. A fixed $k = 50$ wastes resolution on the peaked case (only the top few tokens matter; the other $47$ are noise that the sampler should not be considering) and risks under-sampling on the flat case (genuine alternatives outside the top $50$ get excluded). The mismatch motivates top-p, which adapts to the shape automatically.

The interactive widget later in this chapter lets you dial $k$ directly, alongside top-p and temperature, and watch the kept-token set change in real time.

Implementing top-k

The implementation is a sort, a slice, and a renormalize:

import numpy as np

def softmax(z):
    z = z - z.max()
    e = np.exp(z)
    return e / e.sum()

def top_k_sample(logits, k=50, T=1.0, rng=None):
    """Top-k truncation + sampling."""
    if rng is None:
        rng = np.random
    z = logits / T
    k = min(k, len(z))
    top_k_idx = np.argsort(z)[::-1][:k]
    mask = np.full_like(z, -np.inf)
    mask[top_k_idx] = z[top_k_idx]
    p = softmax(mask)
    return int(rng.choice(len(p), p=p))

def mass_captured(logits, k):
    """Diagnostic: how much probability mass falls inside the top-k set."""
    probs = softmax(logits)
    return np.sort(probs)[::-1][:k].sum()

def make_distribution(shape, V=200):
    np.random.seed(0)
    z = np.random.normal(0, 1, V)
    if shape == 'peaked':
        z[0] += 6.0
    elif shape == 'bimodal':
        z[0] += 4.0
        z[1] += 3.5
    return z

print(f"{'Shape':<10} | {'mass, k=10':>10} | {'mass, k=50':>10} | {'mass, k=100':>11}")
print("-" * 48)
for shape in ['peaked', 'bimodal', 'flat']:
    z = make_distribution(shape)
    row = [mass_captured(z, k) for k in [10, 50, 100]]
    print(f"{shape:<10} | {row[0]:>10.3f} | {row[1]:>10.3f} | {row[2]:>11.3f}")

rng = np.random.RandomState(42)
z = make_distribution('flat')
samples = [top_k_sample(z, k=10, rng=rng) for _ in range(10)]
print(f"\nflat, k=10 samples: {samples}")

print("\nObservations:")
print("- Peaked: k=10 already captures 90% of the mass; k=50 or k=100 add almost nothing.")
print("- Flat: even k=100 (half the vocabulary) misses 15% of the real mass.")
print("- A fixed k cannot distinguish these cases; top-p (next section) adapts automatically.")

The mass table makes the structural limitation from the previous section concrete: on the peaked distribution, $k = 50$ and $k = 100$ buy almost nothing over $k = 10$, forty or ninety extra kept tokens for a rounding error’s worth of probability mass. On the flat distribution, even $k = 100$, half the vocabulary, still leaves $15\%$ of the real mass outside the kept set. Same $k$, opposite failure mode. Top-p fixes this by truncating on cumulative mass instead of rank.

Top-p (nucleus) sampling

The adaptive insight

Holtzman and collaborators in 2019 made the central observation that drives modern decoding: the right truncation set depends on the distribution’s peakedness, not on a fixed size. A peaked distribution puts almost all its mass on a handful of tokens, keep those few and you have captured nearly all the probability the model believes. A flat distribution spreads mass across many tokens, many of them are plausible, and aggressive truncation throws away legitimate options. A fixed $k$ cannot adapt to either case; an adaptive truncator can.

The adaptive criterion they proposed is cumulative probability mass. Sort the tokens by descending probability; walk down the sorted list summing as you go; stop at the smallest index where the cumulative sum reaches a target threshold $p$ (typically $0.95$). The retained set is the nucleus, the smallest set of tokens whose probability mass adds to at least $p$. Everything outside the nucleus is discarded; everything inside is renormalized and sampled.

The algorithm

The truncation criterion in compact form:

Mechanically: sort descending; cumulative-sum the sorted probabilities; binary-search for the first index where the cumsum crosses $p$ (or use np.searchsorted); keep that prefix of sorted indices; mask everything else to $-\infty$; softmax-and-sample over what remains. The whole thing is a half-dozen lines of numpy and runs in microseconds for any realistic $V$.

Why it’s the default

The behavior on the two distribution-shape extremes is what makes nucleus the default. At peaked distributions, the nucleus is small: if the top token already carries $0.9$ of the mass, the nucleus might be just one or two tokens, and the sampler effectively reduces to greedy on the cases where greedy is the right call. At flat distributions, the nucleus grows: needing $0.95$ of the mass from a roughly-uniform tail might require dozens of tokens, and the sampler keeps all of them so that the genuine alternatives stay in play. The truncation budget adjusts to what the model believes, which is exactly what a sampler should do.

Typical values are $p = 0.95$ (the modern chat default across most providers), $p = 0.9$ (the older default, slightly tighter), and $p = 0.8$ for more focused outputs. Nucleus sampling is the standard truncation method used by GPT, Claude, Llama, Gemini, and essentially every other production LLM API (the API-level default often leaves top-p at $1.0$, effectively off, until the caller sets it; see the recipes below). There is also a more recent variant, min-p (Nguyen et al., 2024), which keeps tokens with $p_i \geq p_{\min} \cdot \max_j p_j$, adapting to the peak rather than to cumulative mass. It is gaining traction but is not yet the default anywhere widely deployed; nucleus is still the standard.

import numpy as np

def softmax(z):
    z = z - z.max()
    e = np.exp(z)
    return e / e.sum()

def top_p_sample(logits, p=0.95, T=1.0, rng=None):
    """Top-p (nucleus) truncation + sampling."""
    if rng is None:
        rng = np.random
    z = logits / T
    probs = softmax(z)
    sorted_idx = np.argsort(probs)[::-1]
    sorted_probs = probs[sorted_idx]
    cumsum = np.cumsum(sorted_probs)
    nucleus_size = int(np.searchsorted(cumsum, p) + 1)
    nucleus_idx = sorted_idx[:nucleus_size]
    mask = np.full_like(z, -np.inf)
    mask[nucleus_idx] = z[nucleus_idx]
    p_final = softmax(mask)
    return int(rng.choice(len(p_final), p=p_final))

def nucleus_size(probs, p=0.95):
    """Return the size of the nucleus, for diagnostics."""
    sorted_probs = np.sort(probs)[::-1]
    cumsum = np.cumsum(sorted_probs)
    return int(np.searchsorted(cumsum, p) + 1)

def make_distribution(shape, V=50):
    np.random.seed(0)
    z = np.random.normal(0, 1, V)
    if shape == 'peaked':
        z[0] += 5.0
    elif shape == 'bimodal':
        z[0] += 3.0
        z[1] += 2.5
    return softmax(z)

print(f"{'Shape':<10} | {'p=0.5':>8} {'p=0.9':>8} {'p=0.95':>8}")
print("-" * 42)
for shape in ['peaked', 'bimodal', 'flat']:
    probs = make_distribution(shape)
    sizes = [nucleus_size(probs, p) for p in [0.5, 0.9, 0.95]]
    print(f"{shape:<10} | {sizes[0]:>8} {sizes[1]:>8} {sizes[2]:>8}")

print("\nObservations:")
print("- Peaked: nucleus is small (~1-3 tokens at p=0.95)")
print("- Bimodal: nucleus includes both peaks (~2-4 tokens)")
print("- Flat: nucleus is large (need many tokens to reach 95% mass)")
print("\nTop-p adapts where top-k cannot.")

Min-p: truncating relative to the peak

Nucleus truncates on cumulative mass; min-p truncates on mass relative to the top token. Keep every token whose probability is at least $p_{\min}$ times the top token’s probability, renormalize, sample:

The motivation (Nguyen et al., 2024) is that top-p’s threshold is oblivious to how peaked the distribution is: at a fixed $p = 0.95$, a distribution with one dominant token and a distribution with two nearly-tied dominant tokens can produce very different-feeling nucleuses relative to their own shape. Min-p ties the threshold directly to the top token’s confidence instead: when the model is very sure ($\max_j p_j$ is large), the bar for inclusion is high and few tokens survive; when the model is unsure ($\max_j p_j$ is small), the bar drops and more tokens survive, roughly proportional to how flat the whole distribution already is.

import numpy as np

def softmax(z):
    z = z - z.max()
    e = np.exp(z)
    return e / e.sum()

def min_p_sample(logits, p_min=0.1, T=1.0, rng=None):
    """Min-p truncation + sampling: keep tokens with p_i >= p_min * max_j p_j."""
    if rng is None:
        rng = np.random
    z = logits / T
    probs = softmax(z)
    threshold = p_min * probs.max()
    keep = probs >= threshold
    mask = np.where(keep, z, -np.inf)
    p_final = softmax(mask)
    return int(rng.choice(len(p_final), p=p_final)), int(keep.sum())

def make_distribution(shape, V=200):
    np.random.seed(0)
    z = np.random.normal(0, 1, V)
    if shape == 'peaked':
        z[0] += 6.0
    elif shape == 'bimodal':
        z[0] += 4.0
        z[1] += 3.5
    return z

print(f"{'Shape':<10} | {'kept, p_min=0.5':>15} | {'kept, p_min=0.1':>15} | {'kept, p_min=0.02':>16}")
print("-" * 66)
rng = np.random.RandomState(0)
for shape in ['peaked', 'bimodal', 'flat']:
    z = make_distribution(shape)
    counts = [min_p_sample(z, p_min=pm, rng=rng)[1] for pm in [0.5, 0.1, 0.02]]
    print(f"{shape:<10} | {counts[0]:>15} | {counts[1]:>15} | {counts[2]:>16}")

print("\nObservations:")
print("- Peaked: stays at 1 kept token even at a loose threshold (p_min=0.02);")
print("  nothing else comes within 2% of the top token's probability.")
print("- Flat: kept-set size explodes as p_min loosens (17 -> 98 -> 190 of 200);")
print("  when every token is nearly as likely as the max, min-p barely truncates.")

Typical values are $p_{\min} = 0.05$ to $0.1$; below that min-p barely truncates anything, above $0.2$ it starts behaving like a much stricter top-p. Min-p is cheaper than top-p (no sort or cumulative sum needed, just a max and a threshold comparison) and composes cleanly with temperature, since raising $T$ flattens the whole distribution including the max, which loosens the min-p bar automatically. It is gaining adoption in open-source serving stacks but has not displaced nucleus as the default anywhere widely deployed.

Cumulative mass (top-p) and peak-relative mass (min-p) are not the only adaptive criteria in the literature. Typical sampling (Meister et al., 2022, arxiv.org/abs/2202.00666) truncates on information content instead: it keeps tokens whose surprisal $-\log p_i$ is closest to the distribution’s entropy, on the reasoning that natural text tends to sit near the “typical” information rate at each step rather than at the extremes (neither the most predictable token nor the most surprising one). It never displaced nucleus sampling as a production default, but it is worth knowing as a third answer to “where do you cut the distribution”: by rank (top-k), by cumulative mass (top-p), by distance from the top (min-p), or by distance from typical information content (typical sampling).

Combining strategies

Order of operations

A production sampling step stacks several operations, and the order matters. The standard pipeline:

1. Compute logits $z$ from the forward pass.
2. Apply temperature: $z' = z / T$.
3. Apply nucleus (top-p) truncation: keep tokens with cumulative mass $\geq p$ after softmax of $z'$.
4. Apply repetition penalty (next section): downweight recently-seen tokens.
5. Softmax over the surviving tokens.
6. Sample.

Temperature comes first because it reshapes the distribution that subsequent truncation operates on, a temperature of $0.7$ produces a peakier distribution than $T = 1$, and the nucleus on that peaker distribution is naturally smaller. Truncation comes second because it bounds the candidate set, and applying a repetition penalty to a thousand-token full vocabulary is wasteful when only a few dozen will survive truncation anyway. Repetition penalty comes third because it operates on the surviving candidates, not on the full vocabulary. Softmax-and-sample comes last. Some implementations rearrange these, applying the repetition penalty to raw logits before temperature, for instance, and the differences are usually small, but the order above is the most common convention.

Production recipes

The recipes table is the most directly actionable artifact in the chapter. Copy these defaults into your own code as a starting point, then tune from there.

API defaults differ across providers. OpenAI: $T = 1.0$, top-p $= 1.0$ (effectively off), no top-k, no penalties, the user is expected to set them per-request. Anthropic Claude: $T = 1.0$ as the default, other parameters per-request. Llama (per Meta’s reference inference): $T = 0.6$, top-p $= 0.9$, slightly more conservative than the OpenAI defaults. Codex / Copilot for code completion: $T = 0.2$, top-p $= 0.95$, high confidence, low variance. Reasoning models: DeepSeek recommends $T = 0.6$, top-p $= 0.95$ for R1, balanced between exploration during chain-of-thought and convergence to the final answer. OpenAI’s o1-family models are the exception to the whole table: the API does not expose temperature, top-p, or penalty parameters at all, these are fixed internally, so there is no recipe to tune.

The practical guideline is short: start with chat defaults ($T = 0.7$, top-p $= 0.95$, mild repetition penalty); observe the output on your actual workload; adjust from there. The defaults are good enough for almost any use case; the cases where they need tuning are usually obvious from the failure mode (loops → bump repetition penalty; bland output → bump temperature; incoherence → drop temperature).

Repetition penalties

Three mechanisms

Even with stochastic sampling, models can fall into repetition loops, especially at low temperature, with peaked distributions, or when the prompt contains repeated phrases the model latches onto. Three mechanisms are standard for damping repetition before it spirals.

Frequency penalty (the OpenAI convention): reduce each token’s logit proportional to how many times it has appeared so far. $z'_i = z_i - \alpha \cdot \text{count}_i$. A token that has appeared three times has its logit reduced by $3\alpha$; the next occurrence by $4\alpha$. The penalty grows with use, which makes runaway repetition essentially impossible.

Presence penalty: reduce a token’s logit by a fixed amount if it has appeared at all, regardless of count. $z'_i = z_i - \alpha \cdot \mathbb{1}[\text{count}_i > 0]$. Cheaper and less aggressive, discourages reuse without escalating.

N-gram blocking: the strictest of the three. If generating token $t$ would produce an $n$-gram (typically $3$- or $4$-grams) that already appears in the output, set $p_t = 0$. Common in beam search; less common in standard sampling because stochastic sampling rarely needs the heaviest hammer.

Typical values: frequency penalty $\alpha = 0.0$ – $0.3$ (rarely above), presence penalty $\alpha = 0.0$ – $0.5$, n-gram blocking at $n = 3$ or $n = 4$.

When to use

Modern instruction-tuned models (post-SFT, post-RLHF) rarely need strong repetition penalties because the post-training process already discourages loops directly, RLHF reward models penalize repetitive outputs, and SFT data is curated for natural variation. A mild frequency penalty of $\alpha = 0.1$ is usually sufficient for chat. Higher values often hurt quality: at $\alpha > 0.5$, the model starts avoiding natural repetition (common words like “the” and “and” become artificially rare), and the output reads as stilted even when it is no longer looping.

The order of when to reach for repetition penalties: start at $\alpha = 0.0$ (off); if you observe loops on your workload, bump to $0.1$; if loops persist, bump to $0.3$; above that, you are probably better off changing the temperature or top-p than adding more penalty.

import numpy as np

def softmax(z):
    z = z - z.max()
    e = np.exp(z)
    return e / e.sum()

def apply_frequency_penalty(logits, token_counts, alpha=0.5):
    """Reduce logit by alpha * count."""
    return logits - alpha * token_counts

def apply_presence_penalty(logits, seen_tokens, alpha=0.5):
    """Reduce logit by alpha if token has appeared at all."""
    penalty = np.zeros_like(logits)
    for t in seen_tokens:
        penalty[t] = alpha
    return logits - penalty

# Demo: a decode step where token 5 has been emitted 3 times
np.random.seed(0)
V = 50
logits = np.random.normal(0, 1, V)
logits[5] = 5.0   # strong preference for token 5
token_counts = np.zeros(V)
token_counts[5] = 3
seen = {5}

p_orig = softmax(logits)[5]
p_freq = softmax(apply_frequency_penalty(logits, token_counts, 0.5))[5]
p_pres = softmax(apply_presence_penalty(logits, seen, 0.5))[5]

print(f"Original logit for token 5: {logits[5]:.2f}")
print(f"P(token 5):")
print(f"  Original:              {p_orig:.3f}")
print(f"  Freq penalty (α=0.5):  {p_freq:.3f}  (penalty grows with count)")
print(f"  Presence penalty:      {p_pres:.3f}  (fixed regardless of count)")
print(f"\nFor modern chat models, α = 0.1 is usually sufficient.")
print(f"α > 0.5 often degrades output by suppressing natural repetition.")

Beam search

The mechanics

Beam search is a search-based decoding strategy. Maintain $B$ partial sequences at each step, the “beam”. For each sequence in the beam, run a forward pass, take the top $k$ next-token extensions, and produce $B \times k$ candidates. Score each candidate by cumulative log-probability (sum of log-probs of the tokens chosen so far) and keep the top $B$ overall as the new beam. Repeat until every beam has emitted end-of-sequence or hit the max length, then return the highest-scoring complete sequence. The output is the highest-likelihood sequence the search found, not the highest-likelihood sequence overall (true ML decoding is intractable), but a reasonable approximation.

Beam width $B$ is the knob. $B = 1$ degenerates to greedy. $B = 4$ to $10$ is typical for translation. Larger $B$ explores more paths and finds higher-likelihood sequences but costs $B$ times more compute per step (and more memory for the KV cache, which now has to be replicated across beams).

Why it’s rare in LLM serving

Beam search dominated machine translation from $2014$ to $2020$ and is still the standard there. For modern LLM serving it is rarely used, for four overlapping reasons. Repetitive at high beam width: famously degenerate (Holtzman 2019, the same paper that gave us nucleus sampling, was largely motivated by this observation). The highest-likelihood sequence tends to be a low-entropy sequence, and low-entropy sequences love to repeat common phrases. Computational cost: $B$ times more forward passes per step, with the KV cache replicated across beams. For an LLM at decode-time bandwidth limits, this is a significant tax. Bland output: maximum-likelihood sequences are “safe”: no surprising choices, no rare-but-good vocabulary, no creative leaps. Often dull to read. Wrong objective for most LLM tasks: chat, story generation, brainstorming, and even most reasoning tasks all want diversity over max-likelihood. Translation wants max-likelihood because translation has a correct answer; chat does not.

The result is that most production LLM APIs do not expose beam search as a sampling option. It is available in transformers.generate() and other library defaults, but it is essentially never the path taken by an OpenAI, Anthropic, or Llama serving stack. Stochastic sampling with nucleus and modest temperature wins on almost every chat-style benchmark, costs less to run, and produces more pleasant output.

Contrastive search

A deterministic alternative to both

Beam search and greedy share a weakness: both pick tokens by likelihood alone, and likelihood-only decoding degenerates into repetition (that is the whole Holtzman finding that opened this chapter’s case for nucleus sampling). Stochastic sampling avoids degeneration by adding randomness. Contrastive search (Su et al., $2022$, arxiv.org/abs/2202.06417) takes a different route: stay deterministic, but change the scoring function so that repetition is penalized directly at the representation level, not fixed by injecting noise.

At each step, take the $k$ highest-probability candidate tokens under the model (a small top-k shortlist, not the full vocabulary). For each candidate $v$, run it through the model far enough to get its hidden-state representation $h_v$, and score it by a weighted combination of two terms: how much the model favors it, and how similar its representation is to everything already generated.

The first term, model confidence, is the same signal greedy decoding uses. The second term, the degeneration penalty, is the maximum cosine similarity between the candidate’s representation and every previous token’s representation, high when the candidate would repeat something the model already said in a similar way, low when it would say something new. $\alpha \in [0, 1]$ trades the two off; $\alpha = 0$ is plain greedy over the shortlist, and larger $\alpha$ pushes harder against repetition. Because the whole thing is a $\argmax$, decoding stays deterministic, reproducible, no random seed required, while still avoiding the degenerate loops that sink beam search and greedy.

Constrained decoding and modern recipes

Why constrained decoding matters

Production agents need structured outputs. JSON for tool calls. Regex matches for parseable fields. A grammar like “valid Python” or “valid SQL” for code-generation pipelines. The naive approach is to prompt the model to follow the format, parse the output, and retry on failure, brittle and slow. Retry rates of ten percent are common at first; latency spikes when the retry path fires; and the failure mode (malformed JSON in a tool call) breaks every downstream system that depends on the output. Constrained decoding is the alternative: guarantee that the output satisfies the structural constraint by enforcing it at the sampler.

The FSM masking technique

The technique generalizes nicely. Compile the structural constraint to a finite-state machine (or, more generally, a context-free grammar), for regex constraints this is the standard regex-to-DFA conversion that every textbook covers; for grammars it is parser-generator machinery (LR, GLR, Earley). The compiled FSM has a notion of “current state” and “valid next transitions”. At each decode step, look up which token IDs from the model’s vocabulary would correspond to a legal next transition from the current FSM state, and mask the logits of every other token to $-\infty$:

Apply the usual sampling pipeline, temperature, top-p, repetition penalty if you like, over the masked distribution. The infinities become zeros after softmax, so the sampler can only choose from the valid set. The model picks its most-likely valid token, the FSM advances, and the next step repeats. The output is guaranteed to satisfy the constraint, the model’s predictions stay coherent (because it is still choosing what it thinks is best, just restricted to valid options), and the latency overhead is small, an FSM lookup per step, with state cached across steps so the cost stays per-token rather than per-token-squared.

Production implementations vary by ecosystem. Outlines (Willard & Louf, 2023) compiles regex to FSMs; works with any Hugging Face model. OpenAI JSON mode (response_format = json_object) constrains output to valid JSON, but not to any particular schema, the model can emit any well-formed JSON it likes. OpenAI Structured Outputs (response_format = json_schema, strict: true) goes further: it compiles a caller-supplied JSON Schema into exactly the FSM-masking constraint this section describes, guaranteeing the output matches the schema, not just generic JSON. Anthropic structured outputs enforce tool schemas under the hood. Llama.cpp grammar mode accepts BNF grammars and applies them as masking constraints at every decode step. The mechanics are similar across all of them; the API surface differs.

Exercises

Four exercises that lock in the chapter’s machinery. Each is a self-contained problem with a starting template; hints are collapsed by default; try the problem first.

Exercise 1 (easy): Greedy and temperature

Implement greedy decoding and temperature-scaled sampling. Verify the qualitative behavior: greedy is deterministic; low temperature is conservative; high temperature is noisy.

def greedy(logits):
    return int(np.argmax(logits))

def temperature_sample(logits, T=1.0, rng=None):
    scaled = logits / T
    probs = softmax(scaled)
    return rng.choice(len(probs), p=probs)

Greedy: always 5
T = 0.3: samples = [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
T = 1.0: samples = [0, 44, 29, 5, 5, 5, 5, 6, 5, 5]
T = 2.0: samples = [24, 4, 7, 11, 16, 35, 5, 19, 24, 1]

Exercise 2 (medium): Top-p sampling

Implement top-p (nucleus) sampling. Verify the nucleus size adapts to distribution shape, small for peaked, large for flat.

def top_p_indices(probs, p=0.95):
    order = np.argsort(probs)[::-1]
    sorted_probs = probs[order]
    cumsum = np.cumsum(sorted_probs)
    k = np.searchsorted(cumsum, p) + 1
    k = min(k, len(probs))
    nucleus = order[:k]
    return nucleus, k

def top_p_sample(logits, p=0.95, T=1.0, rng=None):
    scaled = logits / T
    probs = softmax(scaled)
    nucleus, k = top_p_indices(probs, p)
    masked = np.full(len(logits), -np.inf)
    masked[nucleus] = scaled[nucleus]
    masked_probs = softmax(masked)
    return rng.choice(len(masked_probs), p=masked_probs)

peaked   | [1, 2, 9]
bimodal  | [1, 19, 28]
flat     | [8, 29, 36]

Exercise 3 (medium): Repetition penalty

Implement a frequency penalty: each token’s logit is reduced proportional to how many times it has appeared in the generation so far. Verify the effect on a token that has been repeated.

def apply_frequency_penalty(logits, token_counts, alpha=0.5):
    return logits - alpha * token_counts

def sample_with_penalty(logits, T=1.0, alpha=0.0, n=20, rng=None):
    if rng is None: rng = np.random
    V = len(logits)
    token_counts = np.zeros(V)
    samples = []
    for _ in range(n):
        adj_logits = apply_frequency_penalty(logits, token_counts, alpha) if alpha > 0 else logits
        probs = softmax(adj_logits / T)
        tok = rng.choice(V, p=probs)
        token_counts[tok] += 1
        samples.append(tok)
    return samples

Without penalty: [5, 28, 14, 5, 4, 4, 2, 24, 5, 12, 0, 29, 22, 5, 4, 4, 5, 5, 5, 5]
With penalty:    [5, 28, 16, 8, 3, 4, 0, 24, 9, 14, 0, 29, 22, 5, 4, 4, 5, 11, 6, 5]
Token 5 count: without penalty 8 / 20, with penalty 4 / 20

Exercise 4 (hard): FSM masking for constrained decoding

Implement constrained decoding via FSM masking for a tiny JSON-like grammar. At each step, mask out tokens that would violate the current FSM state.

def constrained_decode(logits_fn, state, rng=None):
    if rng is None: rng = np.random
    emitted = []

    while state != 'DONE':
        logits = logits_fn(state)
        valid = valid_tokens(state)
        masked = np.full(len(logits), -np.inf)
        masked[valid] = logits[valid]
        tok = int(np.argmax(masked))
        emitted.append(tok)
        state = TRANSITIONS[state][tok]

    return emitted, state

The inference-engineering arc, complete

Part VI wraps with this chapter. The trilogy: Ch 17 reduced wasted computation, KV cache, continuous batching, Flash Attention, speculative decoding, PagedAttention. Ch 18 reduced bits per parameter, INT8 with LLM.int8 outlier handling, INT4 with per-group scales, NF4 with double quantization, GPTQ and AWQ as the modern PTQ algorithms. Ch 19 governs the decision, how the decoder picks tokens given the logits the (cached, batched, quantized) forward pass produces. Combined, the three chapters are the difference between an order-of-magnitude operational cost on identical hardware: about $50$ tokens per second from naive inference, against $500$ to $1{,}000$ tokens per second aggregate from a production stack with everything in place.

Part VII opens next with capabilities. Where Part VI made the model deployable, Part VII makes it useful. Reasoning (Ch 20) covers chain-of-thought, test-time compute, deliberation, and modern reasoning models like o1 and R1 that scale capability through inference-time search rather than parameter count. Tools (Ch 21) covers how the model calls external APIs, where the constrained-decoding JSON-mode machinery from this chapter does its operationally critical work. Retrieval-augmented generation (Ch 22) covers RAG, pulling relevant context out of vector stores and feeding it back through a deployed model. Multimodal (Ch 23) covers vision and audio, how the same transformer backbone extends to non-text inputs. From here on, deployment is assumed and the focus shifts to building useful systems on top of deployed models.