Decoding Algorithms

The rotation guide won its place in the context prompt:

Create a replacement key, deploy it, then revoke the old key.

That passage supplies context for the answer. In Core Retrieval Algorithms, retrieval picked documentation for How do I rotate an API key? Generation scores the next token. To complete The first rotation step is, a model could score create, revoke, or quota. For this authored guide, create is the supported first word. This fixture demonstrates text generation with an authored guide. Provider-specific rotation procedures and outage experiments require their own evidence.

Decoding translates raw model scores into generated text. The same scores can still emit different text. Greedy selection, a random draw, and a beam of partial paths are different rules. None of them turns an unsupported hallucination into ground truth.

We'll use hand-chosen score vectors rather than downloading a checkpoint. Predict which tokens survive each policy, then run the calculation. These examples expose decoder mechanics. Their numbers aren't measurements of a trained model's factual accuracy.

The autoregressive search space: $|V|^T$ exponential token trees

An autoregressive model doesn't generate an entire sentence in one shot. It predicts text sequentially, token by token. Given an input prompt $x = (x_1, \dots, x_M)$, the model computes conditional probabilities over the vocabulary $V$ at each step $t$:

Working in log-probability space turns this product into a sum, avoiding the underflow of multiplying many small probabilities. Compute log-probabilities directly with a stable log-softmax when possible; taking a logarithm after a probability has rounded to zero cannot recover it.

One possible search objective is the most probable sequence under the model:

Here $\mathcal{Y}$ must specify eligible sequences: a fixed token horizon, or completed answers including the probability of an end-of-sequence token (EOS) and a maximum length. Model probability isn't a factuality or usefulness score.

For a hypothetical vocabulary of $|V| = 32{,}000$ and a fixed horizon $T = 100$, unconstrained enumeration considers:

These are length-100 paths, not a count of all intermediate tree nodes. EOS rules and constraints can reduce the eligible set. Vocabulary size is tokenizer-specific; 32,000 isn't a universal lower or upper bound.

Viterbi gains efficiency by merging histories that share a compact state with identical future transition probabilities. General transformer prefixes don't usually admit that small state space: retaining the entire prefix or KV cache as the state doesn't remove the explosion of distinct histories. Exhaustive search at this scale is impractical, though exact search on a small tree is possible.

Greedy and finite-width beam search approximate this sequence-maximization objective. Sampling has a different goal. Drawing each next token from the model's actual conditional distribution samples exactly from its joint distribution in ideal arithmetic, without finding its mode. Temperature, filters, constraints, and verifier selection define other output policies.

View larger

From raw logits to numerically stable probabilities

For clear arithmetic, treat each word below as a single token. Our prompt ends with:

Evidence: Create a replacement key, deploy it, then revoke the old key.
Answer: The first rotation step is

Here are invented next-token scores, called logits:

Logits aren't probabilities: they're real numbers that can be negative and don't sum to one. Softmax converts unbounded logits into a normalized probability distribution:

Subtracting the maximum logit $m$ doesn't alter the output probabilities. Because $\exp(z_i - m) = \exp(z_i) \cdot \exp(-m)$, the constant factor $\exp(-m)$ factors out of both numerator and denominator and cancels cleanly.

For finite logits, shifted exponents are at most zero, so their exponentials cannot overflow.^{[1]Reference 1Accurate Computation of the Log-Sum-Exp and Softmax Functionshttps://arxiv.org/abs/1909.03469} Unshifted exp(1000) exceeds even FP64's range: Python's math.exp raises an exception, while some array backends return infinity with a warning. Neither is a hardware crash.

import numpy as np

tokens = ["create", "revoke", "rename", "quota"]
logits = [3.0, 2.5, 1.0, -1.0]

def softmax(scores) -> np.ndarray:
    scores = np.asarray(scores, dtype=np.float64)
    if scores.ndim != 1 or scores.size == 0:
        raise ValueError("scores must be a nonempty vector")
    if np.isnan(scores).any() or np.isposinf(scores).any():
        raise ValueError("NaN and positive infinity are invalid logits")
    if not np.isfinite(scores).any():
        raise ValueError("all tokens are masked")
    # Negative infinity represents an intentional mask and gets zero weight.
    weights = np.exp(scores - scores.max())
    return weights / weights.sum()

probabilities = softmax(logits)
for token, score, probability in zip(tokens, logits, probabilities):
    print(f"{token:8} logit={score:>4.1f} probability={probability:.3f}")
print(f"sum={sum(probabilities):.3f}")

create   logit= 3.0 probability=0.568
revoke   logit= 2.5 probability=0.345
rename   logit= 1.0 probability=0.077
quota    logit=-1.0 probability=0.010
sum=1.000

create is the mode at 0.568. Unfiltered sampling chooses revoke at this one position with probability about 0.345. That isn't the probability of an incorrect complete answer, an executed action, or an outage. Subsequent text could even say revoke only after deploying the replacement. Grade complete responses separately.

Numerical stability under extreme ranges

The max shift isn't an optional speed trick. Directly calling exp(1000) overflows standard 64-bit floating-point math, even though the resulting probabilities are mathematically well behaved.

from math import exp

large_logits = [1000.0, 999.0, 998.0]

try:
    raw_weights = [exp(score) for score in large_logits]
    naive = [weight / sum(raw_weights) for weight in raw_weights]
    print("naive:", naive)
except OverflowError:
    print("naive softmax: overflow")

print("stable:", softmax(large_logits).round(3).tolist())
print("extreme gap:", softmax([0.0, -1000.0]).tolist())
try:
    softmax([-np.inf, -np.inf])
except ValueError as exc:
    print("rejected:", str(exc))

naive softmax: overflow
stable: [0.665, 0.245, 0.09]
extreme gap: [1.0, 0.0]
rejected: all tokens are masked

The max subtraction eliminates exponential overflow, but hardware floating-point numbers still have finite precision. An extreme negative gap like exp(-1000) safely underflows to 0.0.

When every token is masked to negative infinity, total probability mass collapses to zero: the decoder must handle that condition explicitly rather than dividing zero by zero.

Deterministic search: greedy myopic traps and beam exploration

After picking a token, the runtime appends it to the prefix and feeds the extended sequence back into the model to predict the subsequent position. Repeating that process builds the autoregressive loop.

In serving runtimes, a key-value (KV) cache retains previous attention keys and values so earlier positions aren't recalculated from scratch.^{[2]Reference 2Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} That architecture optimizes inference throughput, but it doesn't choose the token. Selecting tokens remains the responsibility of the decoding algorithm.

Greedy decoding picks the token with the highest logit at every step:

example_logits = [
    {"create": 3.0, "revoke": 2.5, "rename": 1.0, "quota": -1.0},
    {".": 4.0, "then": 1.5, "after": 0.5},
]

def greedy_token(scores: dict[str, float]) -> str:
    return max(scores, key=scores.get)

generated = []
for step, scores in enumerate(example_logits, start=1):
    chosen = greedy_token(scores)
    generated.append(chosen)
    print(f"step {step}: chose {chosen!r} from {len(scores)} candidates")

answer = "The first rotation step is " + " ".join(generated).replace(" .", ".")
print(answer)

step 1: chose 'create' from 4 candidates
step 2: chose '.' from 3 candidates
The first rotation step is create.

Greedy token selection is deterministic given identical logits and a fixed tie rule. It avoids keeping alternative prefixes, but still performs an argmax and needs stopping/length rules. The model runtime can introduce numerical differences even when sampling is disabled. Greedy is a useful baseline; code correctness and extraction accuracy need task evaluation.

Yet greedy decoding suffers from a fundamental search failure: the myopic trap. Because greedy search commits irreversibly to the immediate highest-scoring token at step $t$, it can miss globally higher-probability sequences that begin with a slightly lower-scoring first token.

Beam search tracks parallel hypotheses

Beam search mitigates greedy myopia by maintaining a set of $B$ active hypotheses, where $B$ is the beam width.

At each step, the algorithm:

1. Expands all $B$ currently retained partial sequences by considering all possible continuations in $V$.
2. Computes the cumulative log-probability for each candidate extension: $\sum_{\tau=1}^t \log P(y_\tau \mid x, y_{<\tau})$.
3. Prunes the pool back to the top $B$ highest-scoring paths.

Consider a separate hand-built, fixed-two-token tree with prefix You should. These probabilities aren't the earlier softmax vector. Greedy grabs create at step 1 because $0.40 \gt 0.35$. But look at step 2:

Greedy gets trapped with create . at joint probability $0.080$. A beam search with width $B = 2$ retains both create and first through step 1. At step 2, it evaluates the joint paths and discovers first create at $0.245$: more than triple the joint probability of the greedy choice.

View larger

from math import exp, isclose, log

first_step = {"create": 0.40, "first": 0.35, "revoke": 0.25}
second_step = {
    "create": {".": 0.20, "a": 0.19, "the": 0.18, "your": 0.17, "another": 0.14, "one": 0.12},
    "first": {"create": 0.70, "deploy": 0.20, "revoke": 0.10},
    "revoke": {".": 0.30, "the": 0.25, "your": 0.25, "it": 0.20},
}

def beam_search(distributions, width: int, steps: int):
    if type(width) is not int or width < 1:
        raise ValueError("beam width must be a positive integer")
    beam = [((), 0.0)]
    for _ in range(steps):
        candidates = []
        for prefix, score in beam:
            probs = distributions[prefix]
            assert isclose(sum(probs.values()), 1.0)
            assert all(0 <= p <= 1 for p in probs.values())
            for token, p in probs.items():
                if p > 0:
                    candidates.append((prefix + (token,), score + log(p)))
        beam = sorted(candidates, key=lambda row: row[1], reverse=True)[:width]
    return beam

tree = {(): first_step, **{(token,): probs for token, probs in second_step.items()}}
greedy_first = max(first_step, key=first_step.get)
greedy_second = max(second_step[greedy_first], key=second_step[greedy_first].get)
greedy_prob = first_step[greedy_first] * second_step[greedy_first][greedy_second]

winner, winner_log_p = beam_search(tree, width=2, steps=2)[0]
print("greedy:", f"{greedy_first} {greedy_second}", f"probability={greedy_prob:.3f}")
print("beam:  ", " ".join(winner), f"probability={exp(winner_log_p):.3f}")

greedy: create . probability=0.080
beam:   first create probability=0.245

Beam search remains an approximate heuristic. Once a prefix falls outside the top $B$ hypotheses at any step, the search discards it permanently. Even if that pruned prefix would have unlocked a continuation with probability $1.0$, beam search can never recover it.

counterexample = {
    (): {"A": 0.5, "B": 0.3, "C": 0.2},
    ("A",): {str(i): 0.1 for i in range(10)},
    ("B",): {str(i): 0.2 for i in range(5)},
    ("C",): {"win": 1.0},
}
for width in (2, 3):
    path, score = beam_search(counterexample, width, steps=2)[0]
    print(f"width={width}: {' '.join(path)} probability={exp(score):.3f}")

width=2: B 0 probability=0.060
width=3: C win probability=0.200

Width $B = 2$ prunes branch C at step 1 because $0.2 \lt 0.3$. It then settles for B 0 at joint probability 0.060. Expanding width to $B = 3$ preserves C, discovering the global optimum C win at joint probability 0.200.

A larger beam retains more prefixes at a given pruning step, but isn't a general monotonic guarantee of final quality or score across runs. A naive implementation duplicates per-prefix caches, approaching $B$ times that cache storage. Model weights remain shared, and serving engines can share common-prefix cache blocks, so total memory needn't grow by exactly $B$.^{[2]Reference 2Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Length normalization and repetition penalties

Raw likelihood search can prefer short completions and repetitive text. Neither behavior is inevitable, and changing the score changes the search objective.

Length normalization changes which completions win

Every generated token multiplies the joint probability by a conditional value $P(y_t \mid \dots) \le 1$. In log space, adding non-positive log-probabilities causes cumulative path scores to decay monotonically with sequence length:

This inequality compares a prefix with its own extension. It doesn't prove that every short completed answer outranks a longer answer on another branch. EOS has a conditional probability too. If EOS has probability 0.01 at the first position, while create has probability 0.99 followed by EOS with probability 0.90, the longer completion has probability 0.891 and wins.

Length normalization can counter an unwanted preference for brief answers, but there is no universally fair length score. One GNMT heuristic is:^{[3]Reference 3Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.https://arxiv.org/abs/1609.08144}

Tune $\alpha$ on development data; it isn't restricted to $[0.6,1.0]$. At $\alpha=0$, this is raw log-probability. At $\alpha=1$, GNMT divides by $(5+L)/6$, not by $L$. Hugging Face's documented beam length_penalty instead divides by $L^\alpha$.^{[4]Reference 4Text Generation.https://huggingface.co/docs/transformers/en/main_classes/text_generation} The next example uses that latter convention with $\alpha=1$; its candidate scores are authored.

candidates = [
    {"text": "create <EOS>", "log_probability": -1.0, "tokens": 2},
    {"text": "create deploy then revoke <EOS>", "log_probability": -1.6, "tokens": 5},
]

raw_winner = max(candidates, key=lambda row: row["log_probability"])
normalized_winner = max(candidates, key=lambda row: row["log_probability"] / row["tokens"])

print("raw winner:               ", raw_winner["text"])
print("length-normalized winner: ", normalized_winner["text"])
for row in candidates:
    average = row["log_probability"] / row["tokens"]
    print(f"{row['text']:31} raw={row['log_probability']:.3f} average={average:.3f}")

raw winner:                create <EOS>
length-normalized winner:  create deploy then revoke <EOS>
create <EOS>                    raw=-1.000 average=-0.500
create deploy then revoke <EOS> raw=-1.600 average=-0.320

The winner changes because -0.320 > -0.500. That arithmetic doesn't check whether either text is a complete or applicable procedure. With GNMT's formula at $\alpha=1$, the scores would be $-1/(7/6)\approx-0.857$ and $-1.6/(10/6)=-0.960$: the short candidate wins. A parameter named length_penalty doesn't identify its formula.

Repetition penalties discourage reused tokens

Holtzman et al. observed repetitive likelihood-maximizing continuations in their GPT-2 experiments.^{[5]Reference 5The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751} An example of the pattern is:

The incident team notified the manager and notified the manager and notified the manager...

A model can assign rising probability to a phrase as that phrase repeats in its context. Maximization can exploit this feedback. Self-attention doesn't mathematically require that behavior, and modern models and tasks can differ.

CTRL introduced penalized sampling.^{[6]Reference 6CTRL: A Conditional Transformer Language Model for Controllable Generation.https://arxiv.org/abs/1909.05858} The following sign-aware variant, used by Hugging Face, lowers the logits of tokens seen in the prefix when $\theta>1$:^{[7]Reference 7Transformers logits processors: repetition penalties and sampling boundarieshttps://github.com/huggingface/transformers/blob/main/src/transformers/generation/logits_process.py}

Positive logits decrease by division; negative logits decrease by multiplication. A zero logit stays zero. This reduces treated tokens' scores relative to untouched candidates, without banning them. After renormalization, an individual treated token's probability can still rise if other treated tokens were reduced more.

import math

def apply_repetition_penalty(
    logits: dict[str, float], sequence: list[str], theta: float = 1.2
) -> dict[str, float]:
    if not math.isfinite(theta) or theta < 1:
        raise ValueError("theta must be finite and at least one in this lab")
    penalized = dict(logits)
    for token in set(sequence):
        if token in penalized:
            score = penalized[token]
            penalized[token] = score / theta if score > 0 else score * theta
    return penalized

step_logits = {"create": 3.0, "deploy": 2.8, "revoke": 2.5}
print("unpenalized choice:", max(step_logits, key=step_logits.get))

# After 'create' was emitted at step 1, apply repetition penalty:
penalized = apply_repetition_penalty(step_logits, ["create"], theta=1.2)
print("penalized 'create' logit:", f"{penalized['create']:.2f}")
print("penalized choice:        ", max(penalized, key=penalized.get))

unpenalized choice: create
penalized 'create' logit: 2.50
penalized choice:         deploy

With $\theta=1.2$, create drops below deploy in this fixture. The penalty doesn't know that deploy is a required operation. It can also suppress necessary repetitions, such as a variable name in code. Tokenization matters, and so does whether the runtime includes prompt tokens in the penalty.^{[7]Reference 7Transformers logits processors: repetition penalties and sampling boundarieshttps://github.com/huggingface/transformers/blob/main/src/transformers/generation/logits_process.py}

Search still returns one high-scoring path. Sampling asks what happens if the next token is drawn from the scores instead of taken from the maximum.

Temperature reshapes entropy

Sampling draws a token rather than searching for a sequence maximum. Temperature $T>0$ scales logits before softmax:

• As $T \to 0$, mass concentrates on the maximum. With a unique finite maximum, this approaches greedy selection. With tied maxima, the limit is uniform over the ties, whereas greedy applies a tie rule.
• When $T = 1.0$, probabilities match the model's raw unscaled distribution.
• As $T \to \infty$, finite logits approach a uniform distribution over the unmasked candidates. Tokens masked to $-\infty$ stay excluded.

Shannon entropy is $H(p)=-\sum_i p_i\log p_i$, with $0\log0=0$. Natural logarithms give nats. For a fixed finite score vector and unchanged masks, entropy is non-decreasing with $T$. Higher entropy describes uncertainty in the next draw, not factual uncertainty or a full answer's quality.

tokens = ["create", "revoke", "rename", "quota"]
logits = [3.0, 2.5, 1.0, -1.0]

def entropy(probabilities) -> float:
    positive = np.asarray(probabilities)[np.asarray(probabilities) > 0]
    return float(-np.sum(positive * np.log(positive)))

for temperature in (0.5, 1.0, 2.0):
    probabilities = softmax([score / temperature for score in logits])
    table = dict(zip(tokens, probabilities))
    print(
        f"T={temperature:.1f}: create={table['create']:.3f} "
        f"quota={table['quota']:.3f} entropy={entropy(probabilities):.3f}"
    )

T=0.5: create=0.721 quota=0.000 entropy=0.647
T=1.0: create=0.568 quota=0.010 entropy=0.933
T=2.0: create=0.438 quota=0.059 entropy=1.190

At $T = 0.5$, entropy falls to $0.647$ nats and create claims $72.1\%$ of the probability mass. At $T = 2.0$, entropy rises to $1.190$ nats: the irrelevant tail token quota jumps from $1\%$ to nearly $6\%$.

Does near-zero temperature choose one winner when the largest scores tie? Try this before assuming it reproduces greedy:

scores = np.array([2.0, 2.0, 0.0, -np.inf])
for temperature in (0.01, 1_000_000.0):
    probabilities = softmax((scores - scores.max()) / temperature)
    assert probabilities[3] == 0
    print(f"T={temperature:g}: {probabilities.round(3).tolist()}")
print("greedy tie rule picks index:", int(np.argmax(scores)))

T=0.01: [0.5, 0.5, 0.0, 0.0]
T=1e+06: [0.333, 0.333, 0.333, 0.0]
greedy tie rule picks index: 0

The low-temperature sampler still has two choices; NumPy's argmax chooses the first tied index. The high-temperature limit has three choices, not four, because the mask remains in force.

For a fixed score vector, lowering temperature sharpens the distribution. In exact arithmetic with $T>0$, every unmasked finite-logit token still has positive probability. To request greedy generation, use the runtime's dedicated control: Hugging Face uses do_sample=False.^{[4]Reference 4Text Generation.https://huggingface.co/docs/transformers/en/main_classes/text_generation} Don't substitute $T=0$ into the softmax equation; an API's zero-temperature convention is a separate rule.

Seeding and production reproducibility

Sampling draws random tokens according to model probabilities. In local development, passing a fixed random seed allows repeatable draws from a static distribution:

from random import Random

tokens = ["create", "revoke", "rename", "quota"]
probabilities = [0.568, 0.345, 0.077, 0.010]

def draw_sequence(seed: int, length: int = 8) -> list[str]:
    rng = Random(seed)
    return rng.choices(tokens, weights=probabilities, k=length)

for seed in (7, 7, 21):
    print(f"seed={seed}: {' '.join(draw_sequence(seed))}")

seed=7: create create revoke create create create create create
seed=7: create create revoke create create create create create
seed=21: create revoke revoke create create revoke revoke create

The repeated seed reproduces this static distribution's draws with this Python implementation. A seed alone doesn't make arbitrary model inference deterministic.

Floating-point addition is non-associative. Different batching shapes, kernels, or accumulation precision can change logits; a near tie can then change even a greedy result.^{[8]Reference 8PyTorch numerical accuracy: reduction order and batched computationshttps://github.com/pytorch/pytorch/blob/main/docs/source/notes/numerical_accuracy.md} Parallel computation isn't inherently nondeterministic: deterministic kernels and a fixed environment can support repeatable inference. PyTorch documents additional randomness controls and limitations across releases, devices, and platforms.^{[9]Reference 9PyTorch reproducibility: random generators and deterministic algorithmshttps://github.com/pytorch/pytorch/blob/main/docs/source/notes/randomness.md}

Check the exact model's supported controls rather than copying a local sampler configuration into every API. Verified October 10, 2026: Claude Sonnet 5 returns HTTP 400 for non-default temperature, top_p, or top_k values; defaults and omission are accepted.^{[10]Reference 10What's new in Claude Sonnet 5https://platform.claude.com/docs/en/about-claude/models/whats-new-sonnet-5}

Record the exact model identifier, prompts, supported decoding settings, runtime details, and request/response identifiers. Record weight/tokenizer hashes when you control them. A hosted API may not expose hashes or guarantee replay.

Temperature still leaves every unmasked token eligible. Which of those tokens should a draw be allowed to land on?

Truncating the long tail: Top-k, Top-p, and Min-p

Holtzman et al. called low-probability candidates an unreliable tail in their open-ended generation experiments.^{[5]Reference 5The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751} A rare token can nevertheless be the right identifier, name, or fact. Filtering ranks probabilities, not truth.

In a constructed model where each of 500 positions has conditional tail-event probability $0.002$, including after every history with no previous tail event, the probability of at least one such event is:

Actual conditional probabilities change with the prefix. The calculation isn't an estimated hallucination rate. Truncation is one way to exclude low-ranked candidates; its effect on task quality needs evaluation.

Top-k truncation: fixed rank cutoff

Top-k sampling retains only the $k$ highest-probability tokens, setting the probability of all other tokens to zero and renormalizing the remaining mass:^{[11]Reference 11Hierarchical Neural Story Generation.https://arxiv.org/abs/1805.04833}

from math import isclose, isfinite

peaked = {"create": 0.568, "revoke": 0.345, "rename": 0.077, "quota": 0.010}

def ranked_distribution(probabilities: dict[str, float]) -> list[tuple[str, float]]:
    values = list(probabilities.values())
    if not values or any(not isfinite(p) or p < 0 for p in values):
        raise ValueError("probabilities must be finite and nonnegative")
    if not isclose(sum(values), 1.0, rel_tol=1e-12, abs_tol=1e-12):
        raise ValueError("probabilities must sum to one")
    return sorted(
        ((token, p) for token, p in probabilities.items() if p > 0),
        key=lambda row: row[1], reverse=True,
    )

def top_k(probabilities: dict[str, float], k: int) -> list[tuple[str, float]]:
    if type(k) is not int or k < 1:
        raise ValueError("k must be a positive integer")
    ranked = ranked_distribution(probabilities)[:k]
    retained_mass = sum(prob for _, prob in ranked)
    return [(token, prob / retained_mass) for token, prob in ranked]

for token, prob in top_k(peaked, k=2):
    print(f"{token:8} renormalized={prob:.3f}")

create   renormalized=0.622
revoke   renormalized=0.378

Top-k sampling has a major structural flaw: fixed cardinality.

If a single token holds 99% of the mass and at least 50 candidates have positive probability, $k=50$ retains 49 lower-ranked candidates too. They aren't necessarily garbage, and their combined original mass is at most 1%.

Conversely, when the distribution is flat because many synonyms are equally valid, $k = 50$ arbitrarily cuts off good candidates that happen to rank 51st.

Top-p (Nucleus) sampling: dynamic cumulative thresholding

Top-p sampling, or nucleus sampling, solves the fixed-cardinality problem by accumulating mass. It selects the smallest set of ranked tokens whose cumulative probability reaches a threshold $p \in (0, 1]$:^{[5]Reference 5The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

def nucleus(probabilities: dict[str, float], threshold: float) -> list[str]:
    if not isfinite(threshold) or not 0 < threshold <= 1:
        raise ValueError("top-p threshold must be in (0, 1]")
    ranked = ranked_distribution(probabilities)
    if threshold == 1:
        return [token for token, _ in ranked]
    kept = []
    cumulative = 0.0
    for token, prob in ranked:
        kept.append(token)
        cumulative += prob
        if cumulative >= threshold:
            break
    return kept

peaked = {"create": 0.568, "revoke": 0.345, "rename": 0.077, "quota": 0.010}
flat = {"create": 0.28, "revoke": 0.25, "rename": 0.24, "quota": 0.23}

print("peaked p=0.90:", nucleus(peaked, 0.90))
print("flat   p=0.90:", nucleus(flat, 0.90))

peaked p=0.90: ['create', 'revoke']
flat   p=0.90: ['create', 'revoke', 'rename', 'quota']

At $p=0.90$, Top-p keeps two tokens in the peaked fixture ($0.568+0.345=0.913\ge0.90$) and all four in the flat fixture. It adapts pool size to probability concentration, without checking whether that concentration is justified.

Min-p sampling: relative probability filtering

Higher temperatures can enlarge the nucleus needed to reach a fixed mass threshold. There is no universal failure boundary at $T=1.2$. The Min-p paper reports favorable comparisons in its tested models, tasks, and temperature settings; these aren't a guarantee of better text in every application.^{[12]Reference 12Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs.https://arxiv.org/abs/2407.01082}

Min-p sampling sets its truncation threshold relative to the top candidate's probability.^{[12]Reference 12Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs.https://arxiv.org/abs/2407.01082} Instead of fixing rank $k$ or cumulative mass $p$, it keeps only tokens whose probability is at least a fraction $p_{\text{base}}$ of the maximum token's probability:

def min_p(probabilities: dict[str, float], base_threshold: float) -> list[str]:
    if not isfinite(base_threshold) or not 0 <= base_threshold <= 1:
        raise ValueError("min-p threshold must be in [0, 1]")
    ranked = ranked_distribution(probabilities)
    max_p = ranked[0][1]
    cutoff = base_threshold * max_p
    return [token for token, p in ranked if p >= cutoff]

peaked = {"create": 0.568, "revoke": 0.345, "rename": 0.077, "quota": 0.010}
flat = {"create": 0.28, "revoke": 0.25, "rename": 0.24, "quota": 0.23}

print("peaked min-p=0.10:", min_p(peaked, 0.10))
print("flat   min-p=0.10:", min_p(flat, 0.10))

peaked min-p=0.10: ['create', 'revoke', 'rename']
flat   min-p=0.10: ['create', 'revoke', 'rename', 'quota']

Under the peaked distribution, the top token is create at 0.568. With $p_{\text{base}} = 0.10$, the absolute cutoff is $0.10 \times 0.568 = 0.0568$. rename ($0.077$) survives, but quota ($0.010$) is discarded.

Under the flat distribution, the top token is 0.28, establishing a cutoff of $0.028$. All four tokens easily clear that bar.

With $p_{\text{base}}=0.10$, a peak of 0.90 gives a cutoff of 0.090, and a peak of 0.10 gives 0.010. The cutoff depends on each distribution's top-token score; assess model certainty and exploration separately. As $T\to\infty$, any fixed $p_{\text{base}}<1$ eventually admits all finite-logit candidates, so Min-p doesn't prevent degeneration at arbitrarily high temperatures.

Hugging Face includes native support for min_p directly in GenerationConfig.^{[4]Reference 4Text Generation.https://huggingface.co/docs/transformers/en/main_classes/text_generation}

View larger

Boundary cases in filter implementations

Production filter implementations must handle boundary conditions predictably:

boundary = {"create": 0.5, "revoke": 0.25, "rename": 0.25, "quota": 0.0}
print("top-k k=2: ", [token for token, _ in top_k(boundary, 2)])
print("top-p p=.75:", nucleus(boundary, 0.75))
print("top-p p=1:  ", nucleus(boundary, 1.0))
print("min-p=.5:   ", min_p(boundary, 0.5))
print("min-p=1:    ", min_p({"create": 0.5, "revoke": 0.5}, 1.0))

for label, call in [
    ("k=0", lambda: top_k(boundary, 0)),
    ("p=0", lambda: nucleus(boundary, 0)),
    ("zero mass", lambda: min_p({"create": 0.0}, 0.1)),
]:
    try:
        call()
    except ValueError as exc:
        print(label, "REJECT", str(exc))

top-k k=2:  ['create', 'revoke']
top-p p=.75: ['create', 'revoke']
top-p p=1:   ['create', 'revoke', 'rename']
min-p=.5:    ['create', 'revoke', 'rename']
min-p=1:     ['create', 'revoke']
k=0 REJECT k must be a positive integer
p=0 REJECT top-p threshold must be in (0, 1]
zero mass REJECT probabilities must sum to one

This lab excludes zero-mass candidates, breaks rank ties by dictionary insertion order, and rejects $k=0$. Runtime conventions differ. Hugging Face's Top-k processor compares logits with the kth score, so ties at the boundary can retain more than $k$ tokens.^{[7]Reference 7Transformers logits processors: repetition penalties and sampling boundarieshttps://github.com/huggingface/transformers/blob/main/src/transformers/generation/logits_process.py} Its generate loop skips that processor when top_k=0.^{[13]Reference 13Transformers generation loop: sampling controls and processor orderhttps://github.com/huggingface/transformers/blob/main/src/transformers/generation/utils.py} Check the interface you're using.

The diagram describes our order: temperature first, then one filter, then renormalization and sampling. Other runtimes can order filters differently. Stacking filters is possible, but their interaction and order must be recorded and evaluated.

For a concrete ordering trap, use the same thresholds twice:

base = {"A": 0.60, "B": 0.25, "C": 0.15}
k_first = dict(top_k(base, 2))
p_after_k = nucleus(k_first, 0.70)

p_first = nucleus(base, 0.70)
mass = sum(base[token] for token in p_first)
p_distribution = {token: base[token] / mass for token in p_first}
k_after_p = [token for token, _ in top_k(p_distribution, 2)]
print("top-k then top-p:", p_after_k)
print("top-p then top-k:", k_after_p)

top-k then top-p: ['A']
top-p then top-k: ['A', 'B']

After Top-k removes C, A's renormalized mass is $0.60/0.85\approx0.706$, enough to reach 0.70 alone. On the original distribution, Top-p needs A and B. The methods select different sets because Top-k renormalizes after truncation.

View larger

Grammar-constrained decoding: syntax enforcement versus semantic truth

The rotation step may have to come out as JSON or as a SQL string. A grammar can reject a trailing comma or an unescaped quote. It doesn't check that the query would run on the real schema, or that the JSON names the step the guide supports.

Constrained decoding prevents syntax violations by applying a formal grammar (Context-Free Grammar, JSON Schema, or Regular Expression) directly to the decoding loop.^{[14]Reference 14Efficient Guided Generation for Large Language Models.https://arxiv.org/abs/2307.09702[15]Reference 15XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Modelshttps://arxiv.org/abs/2411.15100[16]Reference 16llama.cpp Grammars Documentationhttps://github.com/ggml-org/llama.cpp/blob/master/grammars/README.md}

Regular-language constraints can use a finite-state machine (FSM). Recursive grammars, such as arbitrary JSON nesting, generally require stack-based state, as in XGrammar's byte-level pushdown automaton.^{[15]Reference 15XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Modelshttps://arxiv.org/abs/2411.15100} At each step:

1. The matcher inspects its current state and identifies allowed continuations.
2. The engine checks each candidate token's full decoded character/byte sequence, which can cross several grammar boundaries.
3. Any token that would transition the output into an invalid state has its logit forced to $-\infty$ prior to softmax:

Masked tokens have zero weight. With a correct matcher, tokenizer integration, and permitted EOS only in an accepting state, this keeps generated prefixes compatible with the grammar. A length limit or interruption can still leave an incomplete JSON prefix. Unsupported schema features, grammar bugs, or an empty allowed set also need explicit handling.

logits = {"quota": 6.0, "revoke": 4.0, "create": 3.0, "rename": 2.0}
schema_values = {"create", "revoke", "rename"}
supported_by_guide = {"create"}

def constrained_greedy(scores: dict[str, float], allowed: set[str]) -> str:
    candidates = {token: score for token, score in scores.items() if token in allowed}
    if not candidates:
        raise ValueError("constraint removed every token")
    return max(candidates, key=candidates.get)

print("unconstrained:     ", max(logits, key=logits.get))
print("schema-only:       ", constrained_greedy(logits, schema_values))
print("evidence-supported:", constrained_greedy(logits, supported_by_guide))

unconstrained:      quota
schema-only:        revoke
evidence-supported: create

Notice the clear distinction between the second and third lines:

• Unconstrained decoding picks quota because it has the highest logit (6.0).
• Schema-constrained decoding masks quota, but picks revoke (4.0) because revoke is a valid enum field in the JSON Schema.
• Guide-derived allowlist picks create because we manually supplied supported_by_guide = {"create"}.

This illustrates the core boundary of constrained decoding: syntax enforcement is not semantic verification.^{[17]Reference 17Structured outputshttps://developers.openai.com/api/docs/guides/structured-outputs}

The example selects whole enum values as if each were one token; it isn't a JSON parser or a measured verifier. Real engines must handle multi-token strings.

Local masks define a different sampling policy

Grammar validity also differs from sampling the original model conditioned on a valid complete sequence. A local mask keeps any next token that can lead to a valid completion, then renormalizes at that position. It doesn't account for how much valid continuation probability lies beyond each surviving prefix.

Consider an authored two-token tree. The grammar accepts only A x and B y. Both first tokens are allowed, but the model gives their required second tokens very different probabilities:

first = {"A": 0.4, "B": 0.6}
second = {
    "A": {"x": 0.1, "invalid": 0.9},
    "B": {"y": 0.9, "invalid": 0.1},
}
valid = {"A": "x", "B": "y"}
valid_mass = {prefix: first[prefix] * second[prefix][token]
              for prefix, token in valid.items()}
total_valid = sum(valid_mass.values())

for prefix, token in valid.items():
    # The first mask allows both prefixes; the second forces its valid token.
    local_mask_probability = first[prefix] * 1.0
    conditioned_probability = valid_mass[prefix] / total_valid
    print(f"{prefix} {token}: local={local_mask_probability:.3f} "
          f"conditioned={conditioned_probability:.3f}")
assert abs(total_valid - 0.58) < 1e-12

A x: local=0.400 conditioned=0.069
B y: local=0.600 conditioned=0.931

Unmasked model probability is 0.4 × 0.1 = 0.04 for A x and 0.6 × 0.9 = 0.54 for B y. Conditioning on validity divides by their total 0.58, giving about 0.069 and 0.931. Local masking instead gives 0.400 and 0.600: each prefix's only valid second token becomes certain. Both policies produce valid strings, with different frequencies.

Exact conditioning would require valid future probability mass, which can be expensive to compute. Grammar-aligned decoding studies this distinction.^{[18]Reference 18Grammar-Aligned Decodinghttps://papers.neurips.cc/paper_files/paper/2024/file/2bdc2267c3d7d01523e2e17ac0a754f3-Paper-Conference.pdf} For this lesson's audits, record the actual mask-and-renormalize policy; don't infer a conditional sequence distribution from schema compliance alone.

Verified October 10, 2026: OpenAI Structured Outputs supports a documented JSON Schema subset. Handle refusals and incomplete responses separately before consuming a completed schema-conforming result.^{[17]Reference 17Structured outputshttps://developers.openai.com/api/docs/guides/structured-outputs} llama.cpp's converter also supports a subset and documents that unsupported features can be skipped.^{[16]Reference 16llama.cpp Grammars Documentationhttps://github.com/ggml-org/llama.cpp/blob/master/grammars/README.md} A grammar constrains what it represents; it doesn't validate arbitrary business rules or factual accuracy.

Test-time search and reasoning: verifiers and thought trees

Inference-time computation can generate, revise, or evaluate multiple candidates. In Snell et al.'s MATH experiments with PaLM 2 models, some prompt-dependent strategies beat a roughly 14× larger model in specified FLOPs-matched settings. Difficult questions and high inference workloads could favor pretraining instead.^{[19]Reference 19Scaling LLM Test-Time Compute Optimally Can Be More Effective Than Scaling Model Parameters.https://arxiv.org/abs/2408.03314} This isn't a universal 10× compute advantage or a claim that training becomes unnecessary.

Instead of searching blindly across raw token spaces, test-time search operates across complete trajectories or discrete reasoning steps.

Best-of-N selection with outcome evaluators

In Best-of-N, generate $N$ candidate answers, score each with an outcome evaluator, and select the best score. Independent draws from a fixed generator are one common design.^{[20]Reference 20Training Verifiers to Solve Math Word Problems (GSM8K).https://arxiv.org/abs/2110.14168} This rank-and-select procedure isn't the same as rejection sampling, which accepts samples using a specified acceptance rule.

An automated checker can replace a learned scorer when available. Passing a finite test suite verifies those cases, not every possible input. A formal proof checker verifies a proof relative to its formal statement and trusted assumptions.

Process Reward Models catch intermediate reasoning failures

Outcome supervision gives one label for a whole solution, often from its final answer. An ORM can still read the complete trajectory; it isn't required to ignore the reasoning. Inferring where an error occurred from a final label is a credit-assignment problem.^{[21]Reference 21Let's Verify Step by Step.https://arxiv.org/abs/2305.20050}

A correct final answer can conceal invalid steps. Conversely, a nearly correct derivation with a wrong final answer is correctly labeled wrong for a final-answer task, while that label says little about which steps were sound.

Process Reward Models (PRMs) score intermediate steps, usually using preceding context. A probability-style output can be written as:

The interval $[0,1]$ is one score convention for PRMs. Calibration needs separate evidence. Aggregating step scores by a minimum, product, or another rule is an additional design choice. The following invented scores demonstrate a minimum rule; benchmarking an ORM or PRM requires representative data and evaluation.

candidates = [
    {
        "id": "plan_A",
        "steps": ["Create replacement key", "Deploy key to cluster", "Revoke old key"],
        "prm_steps": [0.95, 0.92, 0.98],
        "orm_score": 0.96,
    },
    {
        "id": "plan_B",
        "steps": ["Revoke old key immediately", "Create replacement key", "Deploy key to cluster"],
        "prm_steps": [0.05, 0.90, 0.92],
        "orm_score": 0.72,
    },
]

def prm_min_score(traj: dict) -> float:
    return min(traj["prm_steps"])

orm_best = max(candidates, key=lambda t: t["orm_score"])
prm_best = max(candidates, key=prm_min_score)

print(f"ORM best: {orm_best['id']} (score={orm_best['orm_score']:.2f})")
print(f"PRM best: {prm_best['id']} (min_step={prm_min_score(prm_best):.2f})")
for t in candidates:
    print(f"{t['id']}: ORM={t['orm_score']:.2f} PRM_min={prm_min_score(t):.2f} first_step={t['steps'][0]!r}")

ORM best: plan_A (score=0.96)
PRM best: plan_A (min_step=0.92)
plan_A: ORM=0.96 PRM_min=0.92 first_step='Create replacement key'
plan_B: ORM=0.72 PRM_min=0.05 first_step='Revoke old key immediately'

Both rules select plan_A with the assigned numbers. The minimum rule exposes plan_B's low first-step score. No evaluator was run, and the code applies no rejection threshold. If a fallible PRM assigns the first step 0.99 instead, it won't catch that error. Assess evaluator reliability and final task outcomes as well as intermediate scores.

Tree of Thoughts and Monte Carlo Tree Search

Reasoning can also be organized as a tree of thoughts.^{[22]Reference 22Tree of Thoughts: Deliberate Problem Solving with Large Language Models.https://arxiv.org/abs/2305.10601} It is one explicit search design. Reasoning-model runtimes use varied methods.

Each node in the tree represents a partial reasoning state (a thought step or sub-goal). The search engine uses PRM step scores or heuristic value functions to:

• Expand: Propose $k$ candidate next reasoning thoughts.
• Evaluate: Use a learned scorer, a checker, or a prompted model heuristic.
• Prune or backtrack: Discard weak candidates under the chosen search rule. Any numeric threshold must be justified for that evaluator.

The original Tree of Thoughts paper explored BFS and DFS with model self-evaluation, leaving MCTS for future work.^{[22]Reference 22Tree of Thoughts: Deliberate Problem Solving with Large Language Models.https://arxiv.org/abs/2305.10601} MCTS-based methods such as RAP separately use selection, expansion, simulation, and reward back-propagation to allocate visits.^{[23]Reference 23Reasoning with Language Model is Planning with World Modelhttps://arxiv.org/abs/2305.14992} Neither requires that a PRM be the evaluator. Search can miss a solution or amplify a scorer's mistake; more computation doesn't guarantee truth.

Speculative decoding: lossless serving optimization

Exact speculative decoding aims to accelerate a specified target policy while preserving its output distribution in ideal arithmetic.^{[24]Reference 24Fast Inference from Transformers via Speculative Decoding.https://arxiv.org/abs/2211.17192} Equal distributions don't mean identical sampled text for the same seed, nor a bitwise guarantee across different kernels.

A standard autoregressive loop evaluates the target for each successive next-token choice, with the initial choice available from prefill. At low batch sizes, weight/cache reads can make decoding memory-bound; high batching and other workloads can have different bottlenecks.

Speculative decoding pairs the large target model $M_{\text{target}}$ with a small, lightweight draft model $M_{\text{draft}}$:

1. Draft phase: The small draft model autoregressively proposes a burst of $K$ candidate tokens quickly.
2. Verification phase: A batched target evaluation obtains distributions for the draft prefixes, including $p_{K+1}$ after all $K$ drafts. Causal attention lets it evaluate these known positions together.
3. Modified rejection sampling: For each draft token $i \in \{1, \dots, K\}$, if the target probability $p(x) \ge q(x)$ (where $q$ is the draft probability), the token is accepted. If $p(x) < q(x)$, the token is accepted with probability $p(x) / q(x)$.
4. Correction: At the first rejected position $j$, discard that token and its suffix. Draw a replacement from the normalized residual $\max(0,p_j(x)-q_j(x))$, using the already computed distributions.
5. All accepted: Append one additional token sampled from $p_{K+1}$. One iteration yields between 1 and $K+1$ tokens, subject to stopping rules.

Here $q$ must be the actual proposal distribution and $p$ the target policy after any intended temperature, filters, or masks. Acceptance alone isn't enough: the residual correction restores the target mass. A greedy target uses a matching deterministic verification rule.

Predict the replacement below: the draft overproduces create, so where must rejected probability mass go?

from math import isclose

target = {"create": 0.6, "revoke": 0.3, "rename": 0.1}
draft = {"create": 0.8, "revoke": 0.1, "rename": 0.1}
accepted_mass = {token: min(target[token], draft[token]) for token in target}
rejection_mass = 1 - sum(accepted_mass.values())
residual = {token: max(0.0, target[token] - draft[token]) for token in target}
residual_total = sum(residual.values())
assert isclose(residual_total, rejection_mass)

for token in target:
    correction = rejection_mass * residual[token] / residual_total
    output_mass = accepted_mass[token] + correction
    # Incorrect alternative: redraw from the unadjusted target on rejection.
    wrong_mass = accepted_mass[token] + rejection_mass * target[token]
    assert isclose(output_mass, target[token])
    print(
        f"{token:6} accepted={accepted_mass[token]:.2f} "
        f"corrected={output_mass:.2f} wrong_redraw={wrong_mass:.2f}"
    )
print(f"rejection mass={rejection_mass:.2f}")

create accepted=0.60 corrected=0.60 wrong_redraw=0.72
revoke accepted=0.10 corrected=0.30 wrong_redraw=0.16
rename accepted=0.10 corrected=0.10 wrong_redraw=0.12
rejection mass=0.20

All residual mass goes to revoke here. Redrawing from the unadjusted target would bias the result; matching the intended target distribution is unrelated to whether this guide supports the text. If $p=q$, rejection probability is zero and no residual draw is needed.

The original paper reported roughly 2×–3× acceleration for its T5-XXL/T5X setup. Draft cost, acceptance, verification kernels, batch size, and generation length affect the result; speculation can slow a workload down.^{[24]Reference 24Fast Inference from Transformers via Speculative Decoding.https://arxiv.org/abs/2211.17192} Measure latency and throughput against the same target policy before estimating speedup on another system.

Production generation audits and offline evaluation

Exact speculation is useful only when you know which target policy you preserved. If a release changes both the retrieved passages and the temperature, a worse rotation answer doesn't tell you which change did it.

A generation audit record must capture:

• Prompt hash, model identifier, and runtime build version.
• Retrieval evidence snapshot ID and document chunks.
• Decoding configuration: temperature, top-k, top-p, min-p, beam width, and length penalty.
• Repetition penalty $\theta$, filter/processor order, and grammar/schema version.
• Random seed and engine stop reason (e.g. stop_token, length_limit).
• Task-grading judgments and their source; keep learned scores distinct from ground truth.

Before blaming a user-facing answer, check the decoder on a fixed score vector. If that simulation already prefers the wrong word, the retrieval change is not the only suspect.

from math import exp
from random import Random

def distribution(temperature):
    if not isfinite(temperature) or temperature <= 0:
        raise ValueError("temperature must be finite and positive")
    scores = dict(create=3.0, revoke=2.5, rename=1.0, quota=-1.0)
    weights = {token: exp((z - max(scores.values())) / temperature) for token, z in scores.items()}
    total = sum(weights.values())
    return {token: weight / total for token, weight in weights.items()}

base = distribution(1.0)
kept = nucleus(base, 0.9)
retained_mass = sum(base[token] for token in kept)
policies = {
    "greedy":     {max(base, key=base.get): 1.0},
    "sample T=2": distribution(2.0),
    "top-p p=.9": {token: base[token] / retained_mass for token in kept},
}

for label, probabilities in policies.items():
    rng = Random(7)
    outputs = rng.choices(list(probabilities), weights=list(probabilities.values()), k=2000)
    observed = outputs.count("create") / len(outputs)
    print(f"{label:12} expected={probabilities.get('create', 0):.3f} observed={observed:.3f}")

greedy       expected=1.000 observed=1.000
sample T=2   expected=0.438 observed=0.457
top-p p=.9   expected=0.622 observed=0.621

These are 2,000 independent next-token draws from fixed distributions, not autoregressive answers. Greedy always picks create here. Top-p's observed create rate is 62.1%, near its expected 62.2%; the $T=2$ observation is 45.7%, versus an expectation of 43.8%. Finite-sample variation isn't a decoder defect.

If revoke had the highest score, greedy would emit that word. Emitting text isn't executing an action. Evaluate factual support, complete-answer correctness, schema completion, repetition, diversity when useful, and serving cost separately.

Turn one score vector into a next-token policy, and name which tokens a filter keeps. Hold that policy fixed when a later test changes only the retrieved evidence.

Try three changes before judging a policy:

1. Give revoke logit 4.0. Which policy still favors the guide's first word? Does lowering temperature help when the mode is wrong?
2. Set the nucleus threshold to 0.50, then 0.99. Using the unrounded probabilities from distribution(1.0), predict the retained sets: one candidate, then all four. The first three have mass about 0.9896, although their three-decimal display can sum to 0.990. Which values should a filter use? What support check does either threshold perform?
3. Keep the decoder fixed while changing retrieval. Grade complete answers against an explicit rubric, including missing information and appropriate abstention. Record stop reasons so truncated outputs don't silently count as complete.