Decoding Strategies: Greedy to Nucleus

A status assistant has one small-looking decision: finish The canary status is without turning a plausible token into a misleading incident update. A transformer gives its decoder a score for every next token, not a sentence.

Once those scores exist, decoding decides what reaches the user, one token at a time. That decision trades reproducibility, variety, and serving cost.

Keep this running example in view. Treat each word below as a single token. One model step might look like this:

Greedy decoding writes degraded because it wins this step. A sampling policy might write in and continue into in recovery; on could lead to on track.

Same model, same prompt, different policy, different sentence. The decoder is choosing how much uncertainty to let through.

For top-p sampling at p = 0.90, the first three tokens reach exactly 0.45 + 0.30 + 0.15 = 0.90. Sampling then renormalizes that retained mass, so degraded, in, and on have probabilities 0.50, 0.333..., and 0.166....

The boundary matters: a cutoff that drops the token that reaches the threshold changes both candidate set and draw probabilities.

The earlier decoding algorithms lesson built stable softmax from raw next-token scores (logits). Here, predict which paths survive, compute their scores, and test what changes when several controls interact. All probabilities below are authored fixtures, not measurements from a deployed model. A higher sequence probability doesn't tell us the canary's actual status.

Speculative decoding is a serving technique that drafts tokens for target-model verification. An exact acceptance/correction algorithm preserves the target sampling distribution, including its chosen processors; it needn't reproduce the same seeded token trace as ordinary decoding. Approximate verification can change that distribution.^{[1]Reference 1Fast Inference from Transformers via Speculative Decoding.https://arxiv.org/abs/2211.17192}

Greedy decoding

Greedy's weakness appears when a first-step winner leads to a weak continuation. Compare two paths of exactly two tokens. After degraded, the next-token probabilities are . 0.40, again 0.35, and today 0.25. After in, they are recovery 0.90 and maintenance 0.10. Each conditional distribution sums to one:

Argmax at step one writes degraded and never looks at the other prefix. Multiply each pair to inspect what that commitment hides: in recovery is the better two-token sequence.

first_step = {"degraded": 0.45, "in": 0.30, "on": 0.15, "broken": 0.02,
              **{f"tail{i}": 0.01 for i in range(8)}}
continuations = {
    "degraded": {".": 0.40, "again": 0.35, "today": 0.25},
    "in": {"recovery": 0.90, "maintenance": 0.10},
    "on": {"track": 0.70, "hold": 0.30},
    **{token: {".": 1.0} for token in first_step if token not in {"degraded", "in", "on"}},
}

greedy_first = max(first_step, key=first_step.get)
path_probabilities = {f"{prefix} {token}": probability * conditional
                      for prefix, probability in first_step.items()
                      for token, conditional in continuations[prefix].items()}
highest_sequence = max(path_probabilities, key=path_probabilities.get)

print(f"greedy first token: {greedy_first}")
print("two selected paths:", {key: round(path_probabilities[key], 3)
                              for key in ["degraded .", "in recovery"]})
print(f"higher-probability sequence: {highest_sequence}")

assert greedy_first == "degraded"
assert highest_sequence == "in recovery"
assert path_probabilities["in recovery"] > path_probabilities["degraded ."]

greedy first token: degraded
two selected paths: {'degraded .': 0.18, 'in recovery': 0.27}
higher-probability sequence: in recovery

The myopic trap and likelihood collapse

At each autoregressive step, greedy decoding selects the token with the highest immediate probability:

$w_t = \arg\max_{w \in V} P(w \mid w_{<t})$

Greedy has zero lookahead. It matches width-one beam search under ordinary prefix ranking without separate finished-hypothesis handling. The decoder scans vocabulary $V$, picks the local argmax, and discards the other $|V|-1$ branches. Selection costs $O(|V|)$ per step, excluding the transformer forward pass. There's no random draw or backtracking. Identical logits and deterministic tie-breaking give repeatable choices; a serving system must also reproduce those logits.

Why is this greedy commitment risky? Autoregressive sequence probability factorizes through the chain rule:

$P(w_1, w_2, \ldots, w_T) = \prod_{t=1}^T P(w_t \mid w_{<t})$

Maximizing each individual conditional factor $P(w_t \mid w_{<t})$ doesn't maximize the joint product. In our fixture, a 0.30 first token followed by a 0.90 continuation beats a 0.45 first token followed by 0.40. Greedy never compares those paths.

Evaluate greedy when output variance is costly, such as classification or entity extraction. Argmax alone doesn't enforce a schema or make a status true. Use explicit output constraints and evidence when the contract requires them.

For open-ended generation, Holtzman et al.'s GPT-2 experiments found repetitive or generic text under likelihood-maximizing decoding.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751} A repeated phrase can remain the next-step mode, so argmax may keep selecting it. That observation doesn't establish one universal attention/KV-cache mechanism or imply that every current model loops under greedy decoding. Sampling can loop too, especially when aggressive truncation leaves little choice.

DeepSeek-R1's evaluation report found higher repetition and checkpoint-to-checkpoint variability with greedy decoding of long reasoning outputs. It estimated pass@1 from repeated correctness samples at $T=0.6, p=0.95$.^{[3]Reference 3DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.https://arxiv.org/abs/2501.12948} This is evidence about that evaluation, not a rule that stochastic decoding always improves reasoning accuracy.

Beam search

Greedy keeps one prefix. Beam search keeps B scored prefixes and expands each of them. That extra memory is useful when a slightly weaker first token may unlock a stronger continuation.

Beam search is approximate because a discarded prefix can never return, even if its later continuation would win. Exhaustive search keeps every prefix, growing exponentially with sequence length.

For ordinary same-length cumulative-log-probability ranking, proposing only each parent's top-$B$ children is sufficient to recover the global top $B$: a lower-ranked child already has $B$ siblings scoring at least as high. Use consistent tie-breaking. This shortcut isn't the source of beam search's approximation. Finished-hypothesis quotas or diversity bonuses can change that argument.

Run width 2 on the same two-step status reply. Predict first: which prefix survives step one, and which full sequence should win after step two?

def keep_top(candidates, width):
    return sorted(candidates, key=lambda item: item[1], reverse=True)[:width]

step_one = keep_top(list(first_step.items()), width=2)
step_two = []
for prefix, prefix_prob in step_one:
    for token, token_prob in continuations[prefix].items():
        step_two.append((f"{prefix} {token}", prefix_prob * token_prob))

winner = keep_top(step_two, width=2)[0]
greedy = f"{greedy_first} {max(continuations[greedy_first], key=continuations[greedy_first].get)}"

print(f"beam after step 1: {step_one}")
print(f"beam after step 2: {[(text, round(prob, 3)) for text, prob in keep_top(step_two, width=2)]}")
print(f"greedy path: {greedy}")
print(f"beam winner: {winner[0]}")

assert [token for token, _ in step_one] == ["degraded", "in"]
assert greedy == "degraded ."
assert winner[0] == "in recovery"

beam after step 1: [('degraded', 0.45), ('in', 0.3)]
beam after step 2: [('in recovery', 0.27), ('degraded .', 0.18)]
greedy path: degraded .
beam winner: in recovery

The result keeps degraded (0.45) and in (0.30) after step one, drops on (0.15), and returns in recovery at 0.27 after step two. Beam search recovered the path greedy discarded because it kept that second prefix alive.

Width 2 isn't a guarantee. If degraded and in each spread their continuation mass uniformly across ten tokens, their best two-token scores would be 0.045 and 0.030. A discarded on prefix followed by a certain track would score 0.15 and beat both. More accurate search still only optimizes the specified model score.

This example scores two-token prefixes, not complete sentences: it doesn't model an end-of-sequence (EOS) token. For complete-sequence likelihood, score EOS too. A length cutoff leaves a truncated prefix, not an EOS-completed answer.

A decoder must specify whether truncated candidates are eligible for return, how finished hypotheses are stored, and when search stops. A complete-only contract may reject every truncated candidate; a prefix-allowed contract may compare both groups under its chosen score while retaining the stop reason. Never append an unscored EOS and call the result a completed sequence probability.

Length penalty

Every extension multiplies a prefix probability by a value at most 1, so its log-probability can't increase. This can favor early EOS. It doesn't mean every short sequence beats every longer one: different prefixes start with different scores.

Google's Neural Machine Translation system divides sequence log-probability by a length term:

$\text{score}(Y) = \frac{\log P(Y)}{(5 + |Y|)^\alpha / 6^\alpha}$

When $\alpha = 0$, denominator is 1 and you are back to raw log-probability. Larger $\alpha$ reduces short-sequence bias.

Wu et al. first tried dividing by $\text{length}^\alpha$ and often landed near $0.6$ to $0.7$ on development data. The formula above is the later GNMT term.

In reported experiments they used $\alpha = 0.2$ with a separate coverage penalty $\beta = 0.2$ unless noted otherwise. Neither number is a universal default. Tune $\alpha$ on validation data for your model, stopping rule, and metric.^{[4]Reference 4Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.https://arxiv.org/abs/1609.08144}

The independent fixture below uses $\alpha = 0.6$ to show a ranking flip, not as a recommended setting. Treat both hypotheses as EOS-completed and their invented log-probabilities as including EOS. Here $|Y|$ counts displayed words and punctuation, excluding EOS; check your runtime's counting convention. These scores are unrelated to the two-step table above.

def gnmt_score(log_probability, length, alpha=0.6):
    penalty = ((5 + length) / 6) ** alpha
    return log_probability / penalty

short = {"text": "degraded.", "log_probability": -1.00, "length": 2}
complete = {"text": "in recovery mode now .", "log_probability": -1.08, "length": 5}

raw_choice = max([short, complete], key=lambda item: item["log_probability"])["text"]
normalized_choice = max(
    [short, complete],
    key=lambda item: gnmt_score(item["log_probability"], item["length"]),
)["text"]
print(f"raw sequence score chooses: {raw_choice}")
print(f"length-normalized score chooses: {normalized_choice}")
print("normalized scores:", [round(gnmt_score(x["log_probability"], x["length"]), 4)
                              for x in [short, complete]])

assert raw_choice == "degraded."
assert normalized_choice == "in recovery mode now ."

raw sequence score chooses: degraded.
length-normalized score chooses: in recovery mode now .
normalized scores: [-0.9117, -0.7949]

Better model score, worse answer

Machine translation has a specified source meaning, making sequence search a useful candidate to evaluate. Code generation and extraction still require tests or task-specific checks: a narrow output contract doesn't guarantee that valid answers occupy the model's highest-probability mode.

For open-ended generation, Holtzman's GPT-2 study found that high-likelihood outputs could be generic or repetitive, and very wide beams could prefer immediate termination.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751} More accurate optimization of the wrong objective can make an answer worse.

Meister et al. interpret beam search through a different, regularized decoding objective. Their limiting construction recovers greedy/beam decisions by enforcing locally favorable choices; their translation experiments connect more uniform token surprisal with BLEU.^{[5]Reference 5If Beam Search is the Answer, What was the Question?.https://arxiv.org/abs/2010.02650} They don't prove that beams of 3–6 are universally optimal, or that quality always falls above width 10.

Beam width limits the number of retained prefixes, not search depth. Larger beams needn't produce monotonically better task results, or even a monotonically better final model score under every pruning/stopping rule. Compare actual completed outputs, EOS behavior, and the chosen task metric.

Width-$B$ search can evaluate up to $B$ active prefixes at a step. Batching and shared-prefix KV-cache pages can reduce overhead, while divergent suffixes add state and work. This isn't necessarily $B$ serial forward calls or exactly $B$ times the latency or memory. Measure the engine, task, and output lengths you serve.

Length normalization affects stopping too: a normalized prefix score can improve on extension even while raw log-probability decreases. With $\alpha=0.6$, a length-one prefix at log-probability $-1$ scores $-1$; extending it with conditional probability 0.99 gives a length-two score about $-0.921$. Early-stop bounds must match the normalized objective, not assume every prefix score can only fall.

Temperature scaling

Beam search asks which sequence scores highest. Sampling asks a different question: how much uncertainty should survive at each autoregressive step?

The Boltzmann distribution motivates the term temperature: probabilities scale as $\exp(-E_i/(k_BT))$. In a language-model sampler, logits play the role of negative energy and $T>0$ controls distribution sharpness. Scaling doesn't itself add noise to logits; the categorical draw supplies randomness:

$P(w_i) = \frac{\exp(z_i / T)}{\sum_{j=1}^{|V|} \exp(z_j / T)}$

Dividing logits by $T$ reshapes probability by directly controlling the log-odds ratio between competing tokens. For any two vocabulary tokens $A$ and $B$, their relative probability ratio depends exponentially on their scaled logit gap:

$\frac{P(w_A)}{P(w_B)} = \frac{\exp(z_A / T)}{\exp(z_B / T)} = \exp\left(\frac{z_A - z_B}{T}\right)$

When $z_A - z_B = 2.0$:

• At $T = 1.0$: the odds ratio is $\exp(2.0) \approx 7.39$. Token $A$ is $7.4\times$ more likely than $B$.
• At $T = 0.5$: the odds ratio jumps to $\exp(2.0 / 0.5) = \exp(4.0) \approx 54.60$. The gap widens more than sevenfold.
• At $T = 1.5$: the odds ratio compresses to $\exp(2.0 / 1.5) = \exp(1.33) \approx 3.79$. Token $B$ becomes a viable competitor.

This scaling directly modifies the Shannon entropy $H(P) = -\sum_{i=1}^{|V|} P(w_i) \log_2 P(w_i)$ of the next-token distribution:

• As $T\to0^+$: Mass becomes uniform over the $r$ exactly tied maximum logits: $\lim P(w_i)=\mathbf{1}[z_i=z_{\max}]/r$. Entropy tends to $\log_2 r$. With a unique maximum, this gives the same choice as greedy; with ties, a random draw differs from deterministic tie-breaking.
• As $T\to\infty$: With a fixed set of $N$ finite, eligible logits, probabilities approach $1/N$ and entropy approaches $\log_2 N$. Hard-masked tokens remain excluded. Higher temperature doesn't undo a grammar mask.

For fixed finite logits and masks, entropy is nondecreasing in $T$: in nats, $dH/dT=\operatorname{Var}_{P_T}(z)/T^3\ge0$. This concerns one next-token distribution, not guaranteed diversity or correctness of complete answers. $T=1$ preserves the supplied scale; it doesn't establish statistical calibration.

Return to The canary status is. The original probabilities are 0.45, 0.30, 0.15, 0.02, and eight tail tokens of 0.01 each.

If you already have probabilities, renormalizing each individual $P_i^{1/T}$ is equivalent. It's not equivalent if you first glue the tail into one bucket and then raise that bucket to $1/T$.

Scale all twelve tokens first, then add the eight tail probabilities for display. Entropy is also computed over all twelve tokens, not the five displayed bars. This distinction matters: at $T=1.5$, eight 1% tokens collectively grow to about 21.1%, not the 11.8% obtained by incorrectly treating their 8% total as one token.

Read the columns as a prediction about variance. At $T = 0.3$, sampling usually still writes degraded; at $T = 1.5$, on and even broken are in play.

Subtract the largest eligible logit before exponentiation: $(z_i-z_{\max})/T$. A stable implementation avoids exponential overflow; low precision can still underflow tiny probabilities or change near ties. Reject an empty/all-masked set. Zero isn't a valid divisor: our sampler treats it as an explicit argmax branch. Transformers selects ordinary greedy decoding with do_sample=False and num_beams=1, provided another search mode isn't enabled; its sampling-temperature processor requires a positive value. Setting do_sample=False alone can still select beam search. Inspect the installed interface and generation configuration.

from math import exp, fsum, isclose, isfinite, log, log2

probs = [0.45, 0.30, 0.15, 0.02] + [0.01] * 8

def temperature_from_probs(values, temperature):
    if not isfinite(temperature) or temperature <= 0:
        raise ValueError("temperature must be finite and > 0")
    if (not values or any(not isfinite(x) or x < 0 for x in values)
            or not isclose(fsum(values), 1.0, rel_tol=1e-12, abs_tol=1e-12)):
        raise ValueError("expected a finite, nonnegative probability distribution")
    peak = log(max(values))
    weights = [exp((log(x) - peak) / temperature) if x else 0.0 for x in values]
    total = fsum(weights)
    return [weight / total for weight in weights]

def entropy_bits(values):
    return -sum(value * log2(value) for value in values if value > 0)

low_t = temperature_from_probs(probs, 0.3)
high_t = temperature_from_probs(probs, 1.5)
for temperature, values in [(0.3, low_t), (1.5, high_t)]:
    print(f"T={temperature}:", [round(x, 6) for x in values[:4] + [fsum(values[4:])]])
print("entropy bits:", round(entropy_bits(low_t), 3), round(entropy_bits(probs), 3), round(entropy_bits(high_t), 3))

assert round(low_t[0], 4) == 0.7785
assert round(high_t[0], 4) == 0.3331
assert temperature_from_probs([0.5, 0.5, 0.0], 0.0001) == [0.5, 0.5, 0.0]
assert entropy_bits(low_t) < entropy_bits(probs) < entropy_bits(high_t)

try:
    temperature_from_probs(probs, 0.0)
except ValueError as error:
    print("zero temperature:", error)

T=0.3: [0.778468, 0.201498, 0.019991, 2.4e-05, 1.9e-05]
T=1.5: [0.333144, 0.254237, 0.160159, 0.0418, 0.210659]
entropy bits: 0.861 2.094 2.751
zero temperature: temperature must be finite and > 0

Dividing logits by $T < 1$ stretches differences, so the top token takes more mass. Dividing by $T > 1$ compresses those differences. Temperature is a global sharpness knob.

Temperature sees neither retrieved evidence nor factual support, and it leaves the tail in play. Put a temperature sweep beside task metrics, not in their place:

Top-k sampling

Temperature still leaves the whole vocabulary in play. Top-k sampling, popularized for neural story generation, keeps only the $k$ most probable tokens, then renormalizes and samples.^{[6]Reference 6Hierarchical Neural Story Generation.https://arxiv.org/abs/1805.04833}

On the canary-status step, $k = 2$ keeps degraded and in, then drops on, broken, and the tail. Their 0.45 and 0.30 weights become 0.60 and 0.40 after renormalization.

Our examples retain exactly $k$ eligible tokens, breaking ties by their existing order. Implementations can instead retain every token tied at the kth score. Transformers' current top-k processor uses that threshold rule: scores [2, 2, 2, 0] with k=1 retain three tokens. Read “fixed count” below under the examples' exact-k convention.

The fixed count is both top-k's appeal and its weakness. Ask how peaked each context is before choosing $k$:

When the distribution is peaked, $k = 50$ can admit dozens of weak candidates. They remain unlikely unless transforms such as high temperature give them appreciable mass. Low probability alone doesn't prove a token irrelevant.

When distribution is flat, $k = 10$ can cut off valid continuations. The count ignores confidence, which is why later methods moved to a dynamic cutoff.

def top_k_tokens(tokens_and_probs, k):
    ranked = sorted(tokens_and_probs, key=lambda item: item[1], reverse=True)
    return [token for token, _ in ranked[:k]]

def top_p_tokens(tokens_and_probs, p):
    kept = []
    cumulative = 0.0
    for token, probability in sorted(tokens_and_probs, key=lambda item: item[1], reverse=True):
        kept.append(token)
        cumulative += probability
        if cumulative >= p:
            break
    return kept

distribution = [
    ("degraded", 0.45),
    ("in", 0.30),
    ("on", 0.15),
    ("paused", 0.04),
    ("held", 0.03),
    ("broken", 0.02),
    ("rollback", 0.01),
]

assert top_k_tokens(distribution, 2) == ["degraded", "in"]
assert top_p_tokens(distribution, 0.8) == ["degraded", "in", "on"]

Nucleus (top-p) sampling

Top-k with $k = 50$ keeps fifty tokens even when two are plausible or when hundreds deserve a look. Nucleus sampling, also called top-p, changes the question from “how many?” to “how much mass?”

It keeps adding highest-probability tokens until cumulative mass reaches threshold $p$.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

Using the same canary-status table, $p = 0.80$ includes degraded, in, and on (cumulative 0.90) and excludes broken plus the tail. If degraded had 0.85, nucleus would be one token.

Here $w_{(i)}$ are sorted by decreasing probability. After truncation, divide each kept probability by kept mass so nucleus sums to 1.

def nucleus_distribution(tokens_and_probs, threshold):
    from math import fsum, isclose, isfinite
    if not isfinite(threshold) or not 0 < threshold <= 1:
        raise ValueError("threshold must be in (0, 1]")
    if (not tokens_and_probs or any(not isfinite(p) or p < 0 for _, p in tokens_and_probs)
            or not isclose(fsum(p for _, p in tokens_and_probs), 1.0, abs_tol=1e-12)):
        raise ValueError("expected a probability distribution")
    kept = []
    mass = 0.0
    for token, probability in sorted(tokens_and_probs, key=lambda item: item[1], reverse=True):
        if probability == 0:
            continue
        kept.append((token, probability))
        mass += probability
        if mass >= threshold and threshold < 1:
            break
    return [(token, probability / mass) for token, probability in kept]

tokens = [("degraded", 0.45), ("in", 0.30), ("on", 0.15), ("broken", 0.02)] + [
    (f"tail{i}", 0.01) for i in range(8)]
nucleus = nucleus_distribution(tokens, threshold=0.8)
rounded = [(token, round(p, 3)) for token, p in nucleus]
print("renormalized nucleus:", rounded)

assert rounded == [("degraded", 0.5), ("in", 0.333), ("on", 0.167)]
assert round(sum(probability for _, probability in nucleus), 3) == 1.0

renormalized nucleus: [('degraded', 0.5), ('in', 0.333), ('on', 0.167)]

At fixed $p = 0.90$, survivor count is a function of distribution shape, not a hidden constant:

Real nucleus size also depends on model, tokenizer, prompt, and temperature. The threshold stays fixed; candidate count moves with confidence.

The long-tail failure at high $T$

Top-p has a failure mode to measure at high temperatures ($T > 1$). Flattening gives many weak tokens enough combined mass to enter the cumulative set.

A $p = 0.9$ nucleus can therefore get large even when no individual tail token is a good next word. That is one motivation for confidence-scaled cutoffs such as min-p.

from math import exp

def probabilities(logits, temperature):
    from math import isfinite
    if not isfinite(temperature) or temperature <= 0:
        raise ValueError("temperature must be finite and positive")
    if not logits or not all(isfinite(logit) for logit in logits):
        raise ValueError("this fixture expects finite, unmasked logits")
    peak = max(logits)
    weights = [exp((logit - peak) / temperature) for logit in logits]
    total = sum(weights)
    return [weight / total for weight in weights]

def nucleus_size(probs, threshold):
    mass = 0.0
    for index, probability in enumerate(sorted(probs, reverse=True), start=1):
        mass += probability
        if mass >= threshold:
            return index

logits = [4.0, 2.0, 1.0, 0.0, -0.5, -1.0]
focused = nucleus_size(probabilities(logits, 0.7), threshold=0.9)
flattened = nucleus_size(probabilities(logits, 1.5), threshold=0.9)
print(f"nucleus size at T=0.7: {focused}")
print(f"nucleus size at T=1.5: {flattened}")

assert focused == 1
assert flattened == 3
assert flattened > focused

nucleus size at T=0.7: 1
nucleus size at T=1.5: 3

Beyond nucleus: min-p

Top-p asks how many ranked tokens are needed to cover a chosen mass. Min-p asks a different question: is each token strong enough relative to the best token? Keep tokens whose probability is at least a fraction $\rho$ of that peak.

A dominant top token sets a high bar; a weak top token lowers it. The cutoff follows relative confidence, not a fixed cumulative sum. Nguyen et al. (ICLR 2025 oral) define the kept set as:^{[7]Reference 7Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs.https://arxiv.org/abs/2407.01082}

$V_{\min\text{-}p} = \{w : P(w) \geq \rho \cdot \max_v P(v)\}$

If the top token has probability 0.80 and $\rho = 0.1$, anything below 0.08 is dropped. If the top token has only 0.05, the bar falls to 0.005, so more alternatives survive.

Use the figure as a prediction test. On a peaked split, which rule should keep the fewest candidates? On a flatter split, which rule should expand its set? In the flatter fixture, the 10% tail is ten separate 1% tokens. None outranks paused at 3.5%; the tail must not be sorted as one token.

Run the small implementation after making that prediction. It returns survivors before any renormalization, so the threshold is visible in isolation.

def min_p_tokens(tokens_and_probs, rho):
    from math import fsum, isclose, isfinite
    if not isfinite(rho) or not 0 <= rho <= 1:
        raise ValueError("rho must be in [0, 1]")
    if (not tokens_and_probs or any(not isfinite(p) or p < 0 for _, p in tokens_and_probs)
            or not isclose(fsum(p for _, p in tokens_and_probs), 1.0, abs_tol=1e-12)):
        raise ValueError("expected a probability distribution")
    max_probability = max(probability for _, probability in tokens_and_probs)
    threshold = rho * max_probability
    return [token for token, probability in tokens_and_probs if probability > 0 and probability >= threshold]

confident = [("degraded", 0.80), ("in", 0.09), ("broken", 0.01)] + [
    (f"tail{i}", 0.01) for i in range(10)]
uncertain = [("degraded", 0.05), ("in", 0.04), ("on", 0.03)] + [
    (f"tail{i}", 0.004) for i in range(220)]

assert min_p_tokens(confident, rho=0.1) == ["degraded", "in"]
assert min_p_tokens(uncertain, rho=0.1) == ["degraded", "in", "on"]

Min-p is a newer truncation heuristic to evaluate, not a settled replacement for nucleus sampling. Nguyen et al. propose it for the high-temperature tail that top-p can admit.^{[7]Reference 7Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs.https://arxiv.org/abs/2407.01082}

A later critical reanalysis reports that min-p didn't reliably improve quality-diversity tradeoffs against commonly used samplers in its experiments, and disputes broad adoption claims.^{[8]Reference 8Min-p, Max Exaggeration: A Critical Analysis of Min-p Sampling in Language Modelshttps://arxiv.org/abs/2506.13681}

That reanalysis concerns the original evidence and additional experiments with its code; it doesn't rule out benefits on every model or task. Compare tuning budgets, prompts, judges, and uncertainty, rather than treating either paper's conclusion as a universal ranking.

Treat any published setting, including DeepSeek-R1's temperature 0.6 with top-p 0.95 pass@1 configuration, as an experiment input for that model, not a preset for yours.^{[3]Reference 3DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.https://arxiv.org/abs/2501.12948}

Min-p still depends on temperature and order

If min-p reads temperature-scaled probabilities and $\rho>0$, its rule is equivalent to

$z_i\ge z_{\max}+T\log\rho.$

As $T$ rises, this logit cutoff becomes more permissive. Applying the same min-p rule before temperature uses the original scale and retains a different set. Neither ordering guarantees a smaller pool than top-p. On a uniform distribution, min-p with $\rho\le1$ keeps every eligible token.

from math import log

def minp_ids(logits, rho, temperature):
    # This fixture uses finite logits, 0 < rho <= 1, and positive T.
    cutoff = max(logits) + temperature * log(rho)
    return [index for index, score in enumerate(logits) if score >= cutoff]

logits = [0.0, -2.0, -4.0]
print("min-p before T=2:", minp_ids(logits, 0.1, 1.0))
print("min-p after T=2:", minp_ids(logits, 0.1, 2.0))
uniform_minp = minp_ids([0.0] * 8, 0.1, 2.0)
uniform_top_p_count = 6  # Six probabilities of 1/8 reach p=0.75 exactly.
print(f"uniform pool: min-p={len(uniform_minp)}, top-p={uniform_top_p_count}")
assert minp_ids(logits, 0.1, 1.0) == [0, 1]
assert minp_ids(logits, 0.1, 2.0) == [0, 1, 2]
assert len(uniform_minp) == 8

min-p before T=2: [0, 1]
min-p after T=2: [0, 1, 2]
uniform pool: min-p=8, top-p=6

Repetition penalty

When a generated answer loops, the sampler is reusing tokens that remain too attractive:

"The deploy rolled back. The deploy rolled back. The deploy rolled..."

CTRL introduced penalized sampling: discount logits of tokens already in the generated list. Keskar et al. reported that near-greedy sampling with $\theta \approx 1.2$ balanced truthful generation against repetition in their experiments.^{[9]Reference 9CTRL: A Conditional Transformer Language Model for Controllable Generation.https://arxiv.org/abs/1909.05858}

Their original rule scales the logit of a seen token through a temperature multiplier $\theta$. Modern runtimes expose related variants; inspect the transform instead of inferring it from the name.

Common runtimes such as Hugging Face Transformers expose a related sign-aware processor.

For a repeated token, divide a positive logit by the penalty and multiply a negative logit by it. Both move down in preference rather than toward zero. See RepetitionPenaltyLogitsProcessor.

The first function isolates that sign rule for valid token IDs and finite logits. The combined sampler later adds input and mask validation:

def apply_repetition_penalty(logits, generated_ids, penalty=1.2):
    if penalty <= 0:
        raise ValueError("penalty must be positive")
    adjusted = list(logits)
    for token_id in set(generated_ids):
        if adjusted[token_id] > 0:
            adjusted[token_id] /= penalty
        else:
            adjusted[token_id] *= penalty
    return adjusted

logits = [2.4, -0.5, 0.7]
penalized = apply_repetition_penalty(logits, generated_ids=[0, 1], penalty=1.2)
print("original logits:", logits)
print("penalized logits:", [round(value, 3) for value in penalized])

assert penalized[0] < logits[0]
assert penalized[1] < logits[1]
assert penalized[2] == logits[2]

original logits: [2.4, -0.5, 0.7]
penalized logits: [2.0, -0.6, 0.7]

Token 0 was positive, so the penalty divides it (2.4 / 1.2 = 2.0). Token 1 was negative, so the penalty multiplies it (-0.5 × 1.2 = -0.6). Token 2 never appeared, so its logit stays unchanged.

A naive “divide every seen logit” rule would move -0.5 toward zero and make that token more likely. The sign branch is the important detail.

Apply this transform once per distinct token, not once per occurrence. Values between 0 and 1 reward repetition; 1 leaves logits unchanged. The chosen history can include the prompt, as Transformers does by default for decoder-only models. A repeated service name or code identifier may be necessary, so measure damage as well as loop reduction. Unlike softmax, this sign-aware transform isn't invariant to adding a constant to every raw logit.

Subtracting the maximum before that penalty isn't an innocent numerical trick. It changes the sign branch and how far scores move. Predict the winner for each order:

from math import exp

def penalize(scores, history, factor):
    return [(score / factor if score > 0 else score * factor)
            if index in history else score
            for index, score in enumerate(scores)]

def probabilities(scores):
    weights = [exp(score - max(scores)) for score in scores]
    return [weight / sum(weights) for weight in weights]

scores = [2.4, 2.1, 1.2, 0.3]
names = ["degraded", "in", "on", "broken"]
proper = penalize(scores, {0}, 1.2)
centered_first = penalize([score - max(scores) for score in scores], {0}, 1.2)
print("penalty then argmax:", names[max(range(4), key=proper.__getitem__)])
print("center first then penalty:", names[max(range(4), key=centered_first.__getitem__)])

# Penalized A can gain probability if competitor B is reduced much more.
before = probabilities([2.0, 10.0, 0.0])[0]
after = probabilities(penalize([2.0, 10.0, 0.0], {0, 1}, 2.0))[0]
print(f"seen A probability: {before:.4f} -> {after:.4f}")
assert proper.index(max(proper)) == 1
assert centered_first.index(max(centered_first)) == 0
assert after > before

penalty then argmax: in
center first then penalty: degraded
seen A probability: 0.0003 -> 0.0179

Frequency and presence penalties

A different pair of additive controls changes how often a token has appeared in the current generation:

$\text{logit}_{\text{adjusted}} = \text{logit} - \alpha \cdot \text{count}(\text{token}) - \beta \cdot \mathbb{1}[\text{count}(\text{token}) > 0]$

For positive coefficients, the frequency penalty $\alpha$ scales linearly with every single reuse: five copies of a token cost $5\alpha$. The presence penalty $\beta$ is a flat, one-time penalty triggered as soon as the token appears once.

Both act on token IDs, not semantic concepts. Large penalties can discourage necessary service names, code identifiers, or grammatical tokens. There is no universal harmful threshold such as $\alpha>0.5$: the effect depends on counts, logit gaps, tokenizer, and processor order. Specify whether the history includes the prompt; runtimes can use different histories for different penalties. Negative coefficients reward reuse.

Positive penalties discourage already-seen tokens. They don't supply missing evidence or repair a hallucination, and they don't guarantee that every seen token's normalized probability decreases when several logits change together.

Combining strategies in production

In production inference runtimes like vLLM, SGLang, and TensorRT-LLM, next-token selection isn't a single formula. It's an ordered pipeline of logit processors, constraint masks, temperature scaling, adaptive truncation, and termination checks.

Here is one illustrative pipeline. It isn't a universal runtime order. The local fixture later implements the repetition, temperature, top-p, and token-choice stages:

1. Biases and constraints: Add specified logit biases and mask forbidden tokens to $-\infty$. A grammar can restrict syntactically legal next tokens; valid JSON alone doesn't establish truthful fields. If no token remains eligible, return a constraint error rather than choosing a forbidden token.
2. History Penalties: Apply repetition penalty (sign-aware scaling) followed by additive frequency and presence penalties based on generated token IDs.
3. Greedy branch: In this fixture, exact $T=0$ selects argmax after processors. Runtimes may use different flags or small-temperature thresholds. Sorting and categorical sampling are unnecessary here, but validation and constraints still apply.
4. Stochastic Sampling Branch ($T > 0$):
   • Scale logits by temperature: $\tilde{z}_i = (z_i - z_{\max}) / T$.
   • (Optional) Top-k filter: retain only the top $k$ logits, masking the rest to $-\infty$.
   • Softmax: compute normalized probabilities over surviving logits.
   • Top-p (nucleus) and/or Min-p filter: dynamically truncate the tail based on cumulative mass or relative ratio to $P_{\max}$.
   • Renormalize: divide surviving probabilities by remaining mass so the categorical pool sums to 1.0.
   • Sample: draw from the retained weights using a PRNG, with seed handling defined by the runtime.
5. Termination: Check EOS IDs, output limits, and configured stop strings. A stop string may span tokens or end inside a token. Implementations differ: Transformers' StopStringCriteria precomputes token overlaps and matches with tensor operations rather than requiring a rolling decoded buffer. Record whether stop text is returned and how streaming buffers withhold incomplete matches. See the official criteria documentation.

Checked October 10, 2026: Transformers' current generation source adds sampling temperature before top-k, top-p, and min-p, when those controls are enabled. Other processors, custom code, and defaults can change the full stack. Don't copy an unversioned claim that Transformers always truncates before temperature.

Algorithmic compatibility doesn't guarantee engine support. On the same check date, vLLM's sampling-parameter validation rejects min-p and logit bias with speculative decoding. An exact speculative algorithm can preserve a processed target distribution, but your deployed engine must implement that combination.

Moving temperature across top-p changes which tokens survive, even though positive temperature scaling preserves token rank. By contrast, an exact-k filter with fixed tie-breaking retains the same top-k IDs either way. If top-k and top-p are combined, specify whether top-p's cumulative probabilities are renormalized after top-k. Always check the documentation and source of the inference engine you deploy.

Two order changes, two different mechanisms. Temperature changes cumulative mass while preserving rank. Top-k removes mass, so a later top-p processor reads a new normalized distribution:

from math import fsum

def normalize(values):
    mass = fsum(values)
    return [value / mass for value in values]

def top_p_ids(values, threshold):
    ranked = sorted(range(len(values)), key=values.__getitem__, reverse=True)
    kept = []
    for index in ranked:
        kept.append(index)
        if fsum(values[i] for i in kept) >= threshold:
            break
    return kept

base = [0.45, 0.30, 0.15, 0.02] + [0.01] * 8
hot = normalize([probability ** (1 / 1.5) for probability in base])
print("top-p 0.90 before/after T=1.5:",
      len(top_p_ids(base, 0.90)), len(top_p_ids(hot, 0.90)))

four_tokens = [0.45, 0.30, 0.15, 0.10]
after_top_k = normalize(four_tokens[:3] + [0.0])
k_then_p = top_p_ids(after_top_k, 0.8)
p_then_k = top_p_ids(four_tokens, 0.8)[:3]
print("top-k 3 then top-p 0.8:", k_then_p)
print("top-p 0.8 then top-k 3:", p_then_k)
assert len(top_p_ids(base, 0.90)) == 3
assert len(top_p_ids(hot, 0.90)) == 9
assert k_then_p == [0, 1] and p_then_k == [0, 1, 2]

top-p 0.90 before/after T=1.5: 3 9
top-k 3 then top-p 0.8: [0, 1]
top-p 0.8 then top-k 3: [0, 1, 2]

Reproducibility is a property of the serving stack

Greedy removes the categorical draw; a seed controls specified PRNG states. Neither alone guarantees identical logits or answers across serving configurations. Distinguish repeatable token choices, identical returned text, and bitwise-identical intermediate tensors.

Different reduction groupings, kernel choices, precision, or batch shapes can introduce rounding differences that flip near-tied logits. This doesn't mean every CUDA reduction randomly changes order. MoE routing and distributed operations add implementation-specific concerns; atomic assignment isn't a universal explanation.

Checked October 10, 2026: vLLM's reproducibility guide documents deterministic scheduling for offline inference or batch invariance; online serving uses batch invariance. Its beta batch-invariance mode uses VLLM_BATCH_INVARIANT=1, with documented hardware/model support and possible performance cost. Guarantees are scoped to the same hardware and vLLM version. Dedicated single-request serving is neither universally necessary nor sufficient.

Record checkpoint, tokenizer/template, runtime version, dtype, hardware, processors, stopping policy, and seeds. Test repeat requests alone and under concurrent load. A divergence identifies a reproducibility problem; it doesn't establish which numerical mechanism caused it.

Use the next figure as a dry run with a separate four-token logit fixture. degraded is in the supplied history, so a 1.2 penalty drops it from 2.4 to 2.0, below in at 2.1. Greedy now emits in.

After softmax, the penalized logits are approximately in 0.404, degraded 0.365, on 0.164, and broken 0.067. A $p = 0.90$ nucleus keeps the first three (cumulative 0.933) and drops broken.

The illustrated sample is on, inside the nucleus but not the mode. That's the point of a sampling path: its draw need not be argmax.

Runnable code uses that same conceptual order: penalty, then a greedy branch at temperature 0, otherwise temperature plus nucleus sampling.

random.Random(0) reproduces this local Python fixture. It doesn't guarantee identical outputs across engines, numerical kernels, batching, or tokenizer versions. The fixture rejects an all-masked vocabulary instead of silently choosing a forbidden token.

import math
import random

def apply_repetition_penalty(logits, generated_ids, penalty=1.2):
    if not math.isfinite(penalty) or penalty <= 0:
        raise ValueError("penalty must be finite and positive")
    adjusted = list(logits)
    for token_id in set(generated_ids):
        if type(token_id) is not int or not 0 <= token_id < len(adjusted):
            raise ValueError("history contains an invalid token ID")
        if adjusted[token_id] > 0:
            adjusted[token_id] /= penalty
        else:
            adjusted[token_id] *= penalty
    return adjusted

def softmax(logits):
    if (not logits or any(math.isnan(x) or x == math.inf for x in logits)
            or max(logits) == -math.inf):
        raise ValueError("need at least one finite unmasked logit")
    peak = max(logits)
    weights = [math.exp(logit - peak) for logit in logits]
    total = sum(weights)
    return [weight / total for weight in weights]

def nucleus_sample(logits, threshold, rng):
    if not math.isfinite(threshold) or not 0 < threshold <= 1:
        raise ValueError("top_p must be in (0, 1]")
    probs = softmax(logits)
    ranked = sorted(enumerate(probs), key=lambda item: item[1], reverse=True)
    kept = []
    mass = 0.0
    for index, probability in ranked:
        if probability == 0:
            continue
        kept.append((index, probability))
        mass += probability
        if threshold < 1 and mass >= threshold:
            break
    tokens, weights = zip(*kept)
    return rng.choices(tokens, weights=weights, k=1)[0]

def sample_next_token(logits, generated_ids, temperature, top_p, rng):
    if not math.isfinite(temperature) or temperature < 0:
        raise ValueError("temperature must be finite and nonnegative")
    if not math.isfinite(top_p) or not 0 < top_p <= 1:
        raise ValueError("top_p must be in (0, 1]")
    logits = apply_repetition_penalty(logits, generated_ids, penalty=1.2)
    softmax(logits)  # Validate masks even on the greedy branch.
    if temperature == 0:
        return max(range(len(logits)), key=lambda index: logits[index])
    peak = max(logits)
    scaled = [(logit - peak) / temperature for logit in logits]
    return nucleus_sample(scaled, threshold=top_p, rng=rng)

logits = [2.4, 2.1, 1.2, 0.3]
generated_ids = [0]
rng = random.Random(0)

greedy_id = sample_next_token(logits, generated_ids, temperature=0, top_p=0.9, rng=rng)
sampled_id = sample_next_token(logits, generated_ids, temperature=1.0, top_p=0.9, rng=rng)
names = ["degraded", "in", "on", "broken"]
print(f"greedy token: {names[greedy_id]}")
print(f"sampled token: {names[sampled_id]}")

assert greedy_id == 1
assert names[greedy_id] == "in"
assert sampled_id == 2
assert names[sampled_id] == "on"
assert sample_next_token([-math.inf, 1.0], [], 0, 1, rng) == 1
assert sample_next_token([1000.0, 999.0], [], 0.0001, 1, rng) == 0

greedy token: in
sampled token: on

With seed 0, the sampled path lands on on, matching the figure. Nucleus sampling can redraw the mode or another kept token.

on is one legal draw from this nucleus, not a second deterministic answer.

An empty pool can also come from incompatible processor order, even when the grammar allows a token. Suppose three tokens have probabilities [0.6, 0.3, 0.1], and the grammar permits only token 2. Top-p 0.8 applied first discards token 2. Masking afterward leaves nothing. Applying the grammar first gives token 2 probability 1, so the same top-p threshold retains it. Transformers' built-in prefix constraint runs before its sampling warpers in the checked source; custom stacks need their own check.

scores = [math.log(probability) for probability in [0.6, 0.3, 0.1]]
allowed = {2}
grammar_first = [score if index in allowed else -math.inf
                 for index, score in enumerate(scores)]
chosen = sample_next_token(grammar_first, [], 1.0, 0.8, random.Random(0))
print("grammar first selects:", chosen)
assert chosen == 2

ranked = sorted(enumerate(softmax(scores)), key=lambda item: item[1], reverse=True)
retained, mass = set(), 0.0
for index, probability in ranked:
    retained.add(index)
    mass += probability
    if mass >= 0.8:
        break
cutoff_first = [score if index in retained & allowed else -math.inf
                for index, score in enumerate(scores)]
assert retained == {0, 1}

for label, masked in [("cutoff before grammar", cutoff_first),
                       ("grammar allows nothing", [-math.inf] * 3)]:
    for temperature in [0.0, 1.0]:
        try:
            sample_next_token(masked, [], temperature, 0.8, random.Random(0))
        except ValueError as error:
            print(f"{label}, T={temperature}: {error}")
        else:
            raise AssertionError("an empty eligible pool must not emit a token")

grammar first selects: 2
cutoff before grammar, T=0.0: need at least one finite unmasked logit
cutoff before grammar, T=1.0: need at least one finite unmasked logit
grammar allows nothing, T=0.0: need at least one finite unmasked logit
grammar allows nothing, T=1.0: need at least one finite unmasked logit

Both failures produce the same error here, but their causes differ. For the first, recompute truncation over grammar-eligible logits under the chosen policy. For the second, inspect the constraint and tokenization. Removing the hard mask to avoid the error would violate the output contract.

Evaluation configurations

The first four rows are authored candidate sweeps, not recommended defaults. Compare them on held-out prompts with a stated tuning budget. DeepSeek's pass@1 was an average of sampled correctness outcomes, not the best response chosen from many draws. When comparing pass@k, voting, or reranking, include their extra samples and execution/verification cost.^{[3]Reference 3DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.https://arxiv.org/abs/2501.12948}

Choosing a policy by task

Choose a policy from the output contract, not from a favorite knob. First decide how much output variance the endpoint can tolerate and which failures cost most. Then compare candidates on task metrics, repetition, format validity, and latency.

Every strategy depends on the context through the logits. What differs is how its candidate count adapts. Sampling can also become deterministic when only one positive-probability token survives. Temperature and repetition penalty modify scores before selection; evaluate the stack together.

Decoding trade-offs and audit criteria

Use these pass bars as predictions you can defend from examples, not as settings to memorize.

Common failures and fixes

Beam search made chat sound robotic

Answers became generic and more repetitive after you increased beam width. Inspect the objective first: beam search is pushing toward a most likely overall continuation, which can be generic in open-ended dialogue.

Compare beam search with sampling on held-out prompts. Keep the task, model, stopping rules, and output budget fixed so the comparison measures the decoding change, not several changes at once.

Temperature tweak didn't fix hallucinations

You lowered temperature, but the model still states wrong facts confidently. Temperature changes distribution sharpness, not factual grounding. If the model lacks evidence, a wrong continuation can still be high probability.

Keep decoding conservative for factual tasks, but fix retrieval, prompt grounding, or output constraints. Temperature isn't a truth knob.

High temperature plus top-p pulled in nonsense tail tokens

Creative mode started producing weird fragments or off-topic words. Higher temperature flattened the distribution, so top-p admitted a long tail of individually weak candidates.

Lower temperature, tighten top-p, or test min-p. Min-p makes the cutoff track strength of the best token instead of only cumulative mass.

Fixed top-k clipped valid options

Outputs stayed narrow on creative prompts and erratic on factual prompts with the same k. Top-k uses the same cutoff in every shape: too small in flat contexts and too large in peaked ones.

Treat top-k as a simple baseline. Compare top-p or min-p when candidate-set size should react to model confidence.

Same knobs changed behavior after a runtime swap

Another engine gives different outputs even with matching documented settings. Sampler order, defaults, or special cases such as temperature=0 can differ across implementations.

Inspect the actual sampler path and log intermediate logits if needed. Validate representative prompts before blaming model weights.

temperature=0 was sent through the sampling math directly

The runtime crashes, returns NaNs, or behaves inconsistently when someone sets temperature to zero. The implementation divided logits by zero instead of treating temperature=0 as a greedy special case.

If your interface accepts zero as greedy, branch explicitly before division. If it uses a separate greedy flag, configure that flag and reject invalid sampling temperatures. Either contract needs at least one eligible token.

Truncated probabilities no longer sum to one

Logged or returned survivor probabilities sum to less than one after truncation. Tail probabilities were set to zero, but downstream code still expects a normalized distribution. Some sampling APIs accept unnormalized nonnegative weights; metrics and probability contracts expect normalized probabilities.

Mask logits with negative infinity and run softmax again, or divide surviving probabilities by remaining mass before returning them.

Practice drill

First, modify the executable fixtures without calling a model:

1. Verify every conditional distribution sums to one. Replace the continuations with the width-2 counterexample above and compare exhaustive search with beam search.
2. At top-p 0.90, compare nucleus sizes before and after temperature 1.5 using the twelve-token distribution. Expect 3 versus 9 retained tokens under the inclusive boundary rule.
3. Reverse temperature and nucleus truncation. Explain why the token ranks stay the same but the retained set can change.
4. Pass all-negative-infinity logits to both sampler branches. Both must fail, not return a token.

These tests establish mechanisms, not output quality. For a model-backed extension:

Create one decoding audit table for three production routes: a factual status answer, a creative incident narrative, and code completion. Each route has a different cost for variance, so run its experiment separately instead of letting one global preset decide.

1. Pick baseline settings for temperature, top-p or top-k, repetition penalty, and stop conditions.
2. Write two failure examples per route: one too deterministic, one too random or unsupported.
3. Compare outputs under at least three setting changes, then mark accuracy, diversity, latency, and parseability.
4. Choose one launch setting per route and write the rollback trigger that would force you to change it.

Finish by recording an evaluation-backed decoding policy for each task, model, and tokenizer. The record should explain which failure the setting is meant to prevent and which measurement would make you revisit it.