Decoding: From a Distribution to Text

A language model doesn’t produce text. At each step it produces a distribution: one probability for every token in its vocabulary, given everything so far (What “Generative” Means). Something has to turn that into a choice, then feed the choice back and ask again. That something is decoding, and it’s a separate decision from the model: the same weights write repetitive nonsense or fluent prose depending on it.

This post works through the decoding policies in use, each one as code that edits the model’s scores before a token is chosen, and measures them. The model is Qwen2.5-1.5B-Instruct (Qwen team, 2024), run as a plain next-token predictor on a laptop GPU. Build a Tiny GPT, End to End, and Train It on This Blog’s tiny GPT would show the same mechanics, but its outputs are too weak to show their consequences.

Table of contents

The policies, as code

The model’s output for the next token is a vector of logits $z$, one per token, about 152,000 here; softmax turns them into probabilities (The Residual Stream). Every policy below is an edit to those logits, setting a token’s logit to $-\infty$ to rule it out, followed by one draw:

import torch

# Decoding policies, each a function from the model's logits for the next
# token to a choice. They're written as edits to the logits (masking a token
# means setting its logit to -inf), applied in a fixed order, then one draw.

def repetition_penalty(logits, history, theta):
    """Repetition penalty (Keskar et al., 2019): every token already generated
    becomes less likely. CTRL divides its logit by theta; dividing a negative
    logit would raise it, so (as in Hugging Face) negative ones are multiplied."""
    if theta == 1.0 or not history:
        return logits
    seen = torch.tensor(sorted(set(history)), device=logits.device)
    l = logits[seen]
    logits[seen] = torch.where(l > 0, l / theta, l * theta)
    return logits

def frequency_presence(logits, history, frequency, presence):
    """The OpenAI-style penalties: subtract frequency * (times the token has
    appeared) and presence * (1 if it has appeared at all)."""
    if not history or (frequency == 0 and presence == 0):
        return logits
    counts = torch.bincount(torch.tensor(history, device=logits.device), minlength=logits.numel()).float()
    return logits - frequency * counts - presence * (counts > 0).float()

def top_k(logits, k):
    """Keep the k most likely tokens."""
    if k is None:
        return logits
    kth = logits.topk(k).values[-1]
    return logits.masked_fill(logits < kth, float("-inf"))

def top_p(logits, p):
    """Nucleus sampling (Holtzman et al., 2020): keep the smallest set of the
    most likely tokens whose probabilities add up to at least p."""
    if p is None:
        return logits
    sorted_logits, order = logits.sort(descending=True)
    cumulative = sorted_logits.softmax(-1).cumsum(-1)
    drop = cumulative - sorted_logits.softmax(-1) >= p           # the mass *before* this token already reached p
    return logits.masked_fill(drop.scatter(0, order, drop), float("-inf"))

def min_p(logits, p_base):
    """Min-p (Nguyen et al., 2025): keep tokens with probability at least
    p_base times the top token's probability."""
    if p_base is None:
        return logits
    probs = logits.softmax(-1)
    return logits.masked_fill(probs < p_base * probs.max(), float("-inf"))

def choose(logits, history, generator, temperature=1.0, k=None, p=None, mp=None,
           rep=1.0, freq=0.0, pres=0.0):
    """One decoding step: penalties, then temperature, then the filters, then
    a draw. Temperature 0 means greedy: always the most likely token."""
    logits = logits.float().clone()
    logits = repetition_penalty(logits, history, rep)
    logits = frequency_presence(logits, history, freq, pres)
    if temperature == 0:
        return logits.argmax().item()
    logits = logits / temperature
    logits = min_p(top_p(top_k(logits, k), p), mp)
    return torch.multinomial(logits.softmax(-1), 1, generator=generator).item()

@torch.no_grad()
def generate(model, prompt_ids, n, seed=0, stop=(), **policy):
    """Generate up to n tokens with a KV cache: the prompt once, then one
    token per step ("What Generative Means" and "The KV Cache"). Stops early at any token in `stop`."""
    g = torch.Generator(device=prompt_ids.device).manual_seed(seed)
    out = model(prompt_ids[None], use_cache=True)
    history = []
    for _ in range(n):
        token = choose(out.logits[0, -1], history, g, **policy)
        history.append(token)
        if token in stop:
            break
        out = model(torch.tensor([[token]], device=prompt_ids.device),
                    past_key_values=out.past_key_values, use_cache=True)
    return history

Full script: sampling.py

The other scripts load the model through lm.py, which downloads Qwen2.5-1.5B-Instruct at a pinned revision and runs it in 16-bit floats.

Two real distributions, to see what the policies act on. One prompt where the next token is nearly certain, one where many continuations are reasonable:

def entropy_nats(logits):
    p = logits.softmax(-1)
    return -(p * p.clamp_min(1e-30).log()).sum().item()

kept = lambda l: int((l > float("-inf")).sum())
for prompt in ("The KV cache stores the keys and", "My favorite thing about this blog is"):
    with torch.no_grad():
        logits = model(encode(prompt)[None]).logits[0, -1].float()
    p = logits.softmax(-1)
    top = p.topk(6)
    print(f"{prompt!r} ->")
    print("   " + ", ".join(f"{tok.decode(int(i))!r} {v:.3f}" for v, i in zip(top.values, top.indices)))
    print("   entropy at T = 0.5 / 1 / 1.5: " + " / ".join(f"{entropy_nats(logits / t):.2f}" for t in (0.5, 1, 1.5))
          + f" nats;  top token's probability at T = 0.1: {(logits / 0.1).softmax(-1).max():.4f}")
    print(f"   tokens kept at T = 1: top-k 40 keeps {kept(top_k(logits.clone(), 40))}, "
          f"top-p 0.9 keeps {kept(top_p(logits.clone(), 0.9))}, min-p 0.1 keeps {kept(min_p(logits.clone(), 0.1))}")
    for t in (1.5, 2.0):
        print(f"   at T = {t} (temperature applied first): top-p 0.9 keeps {kept(top_p(logits / t, 0.9))}, "
              f"min-p 0.1 keeps {kept(min_p(logits / t, 0.1))}; with the filters first, top-p's set stays "
              f"{kept(top_p(logits.clone(), 0.9))} and min-p's {kept(min_p(logits.clone(), 0.1))}")

Full script: distributions.py

The rest of the script saves the open prompt’s distribution for the widget further down: the 200 most likely tokens one by one, and the other tokens as a histogram of logits in bins 0.25 wide, so the widget can still apply temperature and filters to the tail. It prints the last line of the output.

'The KV cache stores the keys and' ->
   ' values' 0.758, ' their' 0.084, ' corresponding' 0.043, ' the' 0.015, ' associated' 0.008, ' data' 0.008
   entropy at T = 0.5 / 1 / 1.5: 0.09 / 1.40 / 6.11 nats;  top token's probability at T = 0.1: 1.0000
   tokens kept at T = 1: top-k 40 keeps 40, top-p 0.9 keeps 5, min-p 0.1 keeps 2
   at T = 1.5 (temperature applied first): top-p 0.9 keeps 3655, min-p 0.1 keeps 3; with the filters first, top-p's set stays 5 and min-p's 2
   at T = 2.0 (temperature applied first): top-p 0.9 keeps 26113, min-p 0.1 keeps 6; with the filters first, top-p's set stays 5 and min-p's 2
'My favorite thing about this blog is' ->
   ' that' 0.461, ' the' 0.211, ' how' 0.039, ' when' 0.036, ' its' 0.014, ' seeing' 0.012
   entropy at T = 0.5 / 1 / 1.5: 0.57 / 2.53 / 6.92 nats;  top token's probability at T = 0.1: 0.9996
   tokens kept at T = 1: top-k 40 keeps 40, top-p 0.9 keeps 26, min-p 0.1 keeps 2
   at T = 1.5 (temperature applied first): top-p 0.9 keeps 9542, min-p 0.1 keeps 4; with the filters first, top-p's set stays 26 and min-p's 2
   at T = 2.0 (temperature applied first): top-p 0.9 keeps 45600, min-p 0.1 keeps 20; with the filters first, top-p's set stays 26 and min-p's 2
the widget's 200 tokens cover 97.1% of the probability at T = 1; the other 151,736 tokens go in 87 bins

The two prompts behave very differently. After “the keys and”, three quarters of the probability is on ” values”, and the entropy, the average surprise (Cross-Entropy and the Softmax Gradient), is 1.4 nats at temperature 1. After “My favorite thing about this blog is”, the top token has under half, the rest is spread thinly over many tokens, and the entropy is 2.5 nats. A good policy has to handle both: commit when the model is sure, keep options open when it isn’t. The rest of the output is about how each policy responds to that difference.

Greedy decoding, and its loops

The simplest policy takes the most likely token every time: greedy decoding, temperature=0 in choose. It’s deterministic, and it looks like the right answer: if the model is good, its top choice should be good.

It isn’t. Greedy text gets stuck. The model gives high probability to continuing a pattern that’s already in its context, so once a phrase repeats, the repeat makes the next repeat more likely, and greedy, which never takes a less likely token, can’t break out. In the measurements below, 25% of the 4-token sequences in greedy’s first 64 tokens are repeats of earlier ones, and 13 of the 20 continuations are more than 30% repeats by 128 tokens. The posts’ real continuations have 0.3%.

The deeper reason is in the log-probabilities. Greedy text scores $-0.85$ nats per token under the model: far more likely, to the model, than the real continuation, which scores $-3.53$. Part of that gap is the model’s own error, a 1.5-billion-parameter model on technical prose it has never seen: per paragraph the real text scores anywhere from $-4.5$ to $-2.5$, and it isn’t the paragraphs full of numbers that are hardest. But not all of it. Even a perfect model would score real text below its own greedy output, because real text isn’t the most likely text: it’s written to say something, and saying something means being somewhat surprising (Holtzman et al., 2020). A policy that always picks the most likely token produces text unlike what anyone writes.

import json
import torch
from lm import model, tok, encode

# The real continuations' log-probability, prompt by prompt: how much it
# varies, and whether the paragraphs full of numbers are the hard ones.
prompts = json.load(open("prompts.json"))
rows = []
with torch.no_grad():
    for i, item in enumerate(prompts):
        prompt, ids = encode(item["prompt"]), tok(item["human"]).input_ids[:64]
        x = torch.cat([prompt, torch.tensor(ids, device=prompt.device)])
        lp = model(x[None]).logits[0, len(prompt) - 1:-1].float().log_softmax(-1)
        score = lp.gather(1, x[len(prompt):, None]).mean().item()
        numeric = sum(any(c.isdigit() for c in tok.decode([t])) for t in ids) / len(ids)
        rows.append((score, numeric, i))
rows.sort()
print("per-prompt log-prob of the real continuation: " + ", ".join(f"{s:.2f}" for s, _, _ in rows))
print(f"lowest {rows[0][0]:.2f} (prompt {rows[0][2]}, {rows[0][1]:.0%} of tokens with digits); highest {rows[-1][0]:.2f} "
      f"(prompt {rows[-1][2]}, {rows[-1][1]:.0%} with digits); mean {sum(r[0] for r in rows) / 20:.2f}")

Full script: human_logprob.py

per-prompt log-prob of the real continuation: -4.46, -4.36, -4.24, -4.18, -4.05, -4.03, -3.91, -3.87, -3.75, -3.56, -3.43, -3.35, -3.29, -3.05, -2.99, -2.96, -2.91, -2.90, -2.74, -2.49
lowest -4.46 (prompt 10, 0% of tokens with digits); highest -2.49 (prompt 17, 39% with digits); mean -3.53

Temperature

The alternative is to sample: draw the next token at random from the distribution. Temperature $T$ controls how sharp that distribution is, by dividing the logits before the softmax:

Two limits show what it does. The ratio of any token’s probability to the top token’s is $p_i / p_{\max} = e^{(z_i - z_{\max}) / T}$. As $T \to 0$ every ratio goes to 0 (for every token below the top; tied tokens stay tied), since $z_i - z_{\max} < 0$ is divided by a smaller and smaller number: all the probability goes to the top token, and sampling becomes greedy. That’s why temperature=0 means greedy. As $T \to \infty$ every ratio goes to 1: the distribution becomes uniform over the whole vocabulary. Worked, on two logits $(2, 1)$:

• at $T = 1$: $e^2 / (e^2 + e^1) = 0.731$ and $0.269$;
• at $T = 0.5$, logits $(4, 2)$: $0.881$ and $0.119$, sharper;
• at $T = 2$, logits $(1, 0.5)$: $0.622$ and $0.378$, flatter.

The entropy rises with $T$ throughout. On the real distributions above it goes from 0.09 nats at $T = 0.5$ to 1.4 at 1 and 6.1 at 1.5 for the sure prompt. The jump at 1.5 is the tail: about 152,000 tokens, each with a tiny probability, and at a high temperature their combined share becomes large. At $T = 0.1$ the top token has more than 99.9%.

Temperature is a single knob for one trade-off. Low, and the text is safe and repetitive; high, and it’s varied and, eventually, nonsense. In the measurements, pure sampling at $T = 1$ scores $-3.0$ nats per token, close to the real text’s $-3.5$, and repeats almost nothing. Those two numbers are related. Sampling at $T = 1$ draws each token from the model’s own distribution, so its average log-probability is minus the model’s entropy along the way: $-3.0$ says the model is, on average, about as uncertain as a choice among $e^3 \approx 20$ equally likely tokens at each step. (Real text scores lower here. That is a measurement, not a rule: its score is minus the cross-entropy between the text’s source and the model, which can be above or below the model’s own entropy.) At $T = 1.5$ it scores $-10$: the text is made of tokens the model itself considers absurd, and reads like it. The problem with sampling at $T = 1$ is the same tail: each step there’s a real chance of drawing one of the many unlikely tokens, and over a hundred steps that chance becomes a near certainty. One bad token can derail everything after it.

Truncation: top-k, top-p and min-p

So the other family of policies truncates: it removes the unlikely tail before sampling, and renormalizes over what’s left.

• Top-k (Fan et al., 2018) keeps the $k$ most likely tokens. Simple, but blind to the shape of the distribution: $k = 40$ keeps 40 tokens after “the keys and”, where two are reasonable, and the same 40 after “my favorite thing”, where there are many more.
• Top-p, or nucleus sampling (Holtzman et al., 2020), keeps the smallest set of most likely tokens whose probabilities add up to at least $p$ (the token that crosses $p$ is kept). It adapts: $p = 0.9$ keeps 5 tokens for the sure prompt and 26 for the open one.
• Min-p (Nguyen et al., 2025) keeps every token with at least a fraction $p_{\text{base}}$ of the top token’s probability. With $0.1$ it keeps the 2 tokens within a factor of ten of the top one, on both prompts here. Its threshold scales with the model’s confidence: a sure model has a high top probability and so a high bar. (Its benefits are disputed: a reanalysis, Schaeffer et al., 2025, finds that min-p’s quality advantage disappears once the other methods are tuned as carefully.)

Try them on the open prompt’s real distribution, over the whole vocabulary. The faint bars are the model’s probabilities at $T = 1$, the solid bars what the policy samples from; the last bar is every token but the top 20. Raise the temperature with no filter, and watch that bar swallow the distribution; then add top-p or min-p:

Measured on twenty paragraphs

To compare the policies on real text, take 20 paragraphs of this blog’s own prose, spread evenly over the eligible paragraphs (code, math and lists excluded), from 14 posts, and give each policy the first 200 characters of each. The model has never seen these posts, which postdate it, and the rest of each paragraph is the post’s real continuation. Two measures, each with a known failure:

• Repetition: the share of 4-token sequences that already occurred earlier in the same continuation. A loop scores high.
• Log-probability per token under the model’s plain distribution: how likely the model finds the text. Nonsense scores very low; but so does real writing, a little, as the real continuations show.

Sampling policies run with two seeds. Each policy and seed takes about two minutes (the times in the output); on an Apple M4 laptop, all of this post’s code takes about 40 minutes.

POLICIES = {
    "greedy":                 dict(temperature=0),
    "beam search, 4 beams":   "beam",
    "greedy + repetition 1.2": dict(temperature=0, rep=1.2),
    "pure sampling, T=1":     dict(temperature=1.0),
    "T=0.7":                  dict(temperature=0.7),
    "top-k 40":               dict(k=40),
    "top-p 0.9":              dict(p=0.9),
    "min-p 0.1":              dict(mp=0.1),
    "T=1.5 alone":            dict(temperature=1.5),
    "T=1.5 + min-p 0.1":      dict(temperature=1.5, mp=0.1),
}

def repeats(ids, n=4):
    grams = [tuple(ids[i:i + n]) for i in range(len(ids) - n + 1)]
    return sum(g in set(grams[:i]) for i, g in enumerate(grams)) / max(1, len(grams))

@torch.no_grad()
def logprob(prompt, ids):
    x = torch.cat([prompt, torch.tensor(ids, device=prompt.device)])
    lp = model(x[None]).logits[0, len(prompt) - 1:-1].float().log_softmax(-1)
    return lp.gather(1, x[len(prompt):, None]).mean().item()

Full script: compare.py

The rest of compare.py runs every policy on the 20 prompts, 128 new tokens each, with beam search through Hugging Face’s generate. It prints one line per policy and seed, scores the real continuations the same way, and saves every text to compare_texts.json. The real continuations are scored on their first 64 tokens, because the shortest has 67, and each policy’s text is scored on its first 64 too, so the two compare like for like; the repetition rate over all 128 tokens is reported for the policies alone.

greedy                   seed 0: first 64 tokens: repeated 4-grams 25.0%, log-prob -0.85; all 128: repeated 48.6%, 13/20 over 30%  (124 s)
beam search, 4 beams     seed 0: first 64 tokens: repeated 4-grams 16.8%, log-prob -0.62; all 128: repeated 41.4%, 14/20 over 30%  (131 s)
greedy + repetition 1.2  seed 0: first 64 tokens: repeated 4-grams  1.0%, log-prob -1.43; all 128: repeated  2.6%,  0/20 over 30%  (107 s)
pure sampling, T=1       seed 0: first 64 tokens: repeated 4-grams  0.5%, log-prob -3.15; all 128: repeated  1.8%,  0/20 over 30%  (105 s)
pure sampling, T=1       seed 1: first 64 tokens: repeated 4-grams  1.3%, log-prob -2.86; all 128: repeated  3.5%,  1/20 over 30%  (101 s)
T=0.7                    seed 0: first 64 tokens: repeated 4-grams  3.4%, log-prob -1.46; all 128: repeated  5.8%,  1/20 over 30%  (109 s)
T=0.7                    seed 1: first 64 tokens: repeated 4-grams  3.8%, log-prob -1.66; all 128: repeated  8.1%,  2/20 over 30%  (112 s)
top-k 40                 seed 0: first 64 tokens: repeated 4-grams  1.2%, log-prob -2.10; all 128: repeated  2.0%,  0/20 over 30%  (113 s)
top-k 40                 seed 1: first 64 tokens: repeated 4-grams  3.4%, log-prob -1.93; all 128: repeated  5.0%,  0/20 over 30%  (107 s)
top-p 0.9                seed 0: first 64 tokens: repeated 4-grams  0.3%, log-prob -2.30; all 128: repeated  2.4%,  0/20 over 30%  (119 s)
top-p 0.9                seed 1: first 64 tokens: repeated 4-grams  3.9%, log-prob -2.11; all 128: repeated  7.0%,  1/20 over 30%  (112 s)
min-p 0.1                seed 0: first 64 tokens: repeated 4-grams  3.3%, log-prob -1.49; all 128: repeated  9.2%,  2/20 over 30%  (106 s)
min-p 0.1                seed 1: first 64 tokens: repeated 4-grams  2.9%, log-prob -1.34; all 128: repeated  8.4%,  1/20 over 30%  (113 s)
T=1.5 alone              seed 0: first 64 tokens: repeated 4-grams  0.0%, log-prob -10.13; all 128: repeated  0.0%,  0/20 over 30%  (111 s)
T=1.5 alone              seed 1: first 64 tokens: repeated 4-grams  0.0%, log-prob -10.24; all 128: repeated  0.0%,  0/20 over 30%  (111 s)
T=1.5 + min-p 0.1        seed 0: first 64 tokens: repeated 4-grams  2.4%, log-prob -2.18; all 128: repeated  4.2%,  1/20 over 30%  (125 s)
T=1.5 + min-p 0.1        seed 1: first 64 tokens: repeated 4-grams  1.3%, log-prob -2.06; all 128: repeated  3.7%,  0/20 over 30%  (120 s)
human continuation             : first 64 tokens: repeated 4-grams  0.3%, log-prob -3.53

And one prompt’s continuations, to see what the numbers mean:

import json

# One prompt's continuations from compare.py, under each policy (seed 0),
# first 260 characters, with the paragraph's real continuation last.
texts, prompts = json.load(open("compare_texts.json")), json.load(open("prompts.json"))
i = 7
print(f"PROMPT: {prompts[i]['prompt']}\n")
for name in ("greedy", "beam search, 4 beams", "greedy + repetition 1.2", "pure sampling, T=1", "top-p 0.9",
             "min-p 0.1", "T=1.5 alone", "T=1.5 + min-p 0.1"):
    print(f"[{name}]{texts[name + '|0'][i][:260]!r}\n")
print(f"[what the post says]{prompts[i]['human'][:260]!r}")

Full script: one_prompt.py

PROMPT: All three need about the same number of updates to get close, around 50. But an update on one question costs a 24th of a full-batch update. So SGD gets there after seeing the data about twice, where

[greedy]" as the other two need to see the data about 10 times. \n\nSo, the question is, why does SGD need to see the data about 10 times, while the other two need to see the data about 50 times? \n\nI understand that SGD is a stochastic algorithm, but I don't understand w"

[beam search, 4 beams]' mini-batch gets there after seeing the data about 1.5 times. This is because mini-batch has to see the data 1.5 times to get the same number of updates as SGD, and SGD has to see the data 2 times to get the same number of updates as mini-batch. So mini-batch '

[greedy + repetition 1.2]" as the other two need to see it 3 times. I'm not sure if this is a good thing or bad, but my intuition says that SGD should be faster than both of them.\n\nI've been trying to understand why and how these things work in practice (and what they mean), so any hel"

[pure sampling, T=1]' agrad and rose have each seen almost the entire batch of updates. Worst case, I suppose. So far, by updating the golden set, I have trouble seeing a good upper bound on the number of updates it takes. Can anyone help with referencing the complexities to get t'

[top-p 0.9]' as Batch would take 15 minutes for a full-batch. \\n\\nA Batch update with a full-batch would result in a new estimate for the error after every update. If, instead, the batch update with a partial batch is used, then the error can only be updated after every $'

[min-p 0.1]' as Adam and RMSProp each take about the same amount of updates. \\n\\n'

[T=1.5 alone]' agodly rose closes in without using the heavy Smith Archive warmup quadrant.\\nTS_USD_OPEN安い decimal by:", finelist الأمم synchronization method with trouble�iers SMART công&PubOrganwoo-oriented cetверParser).\\-output[i referencing執INCLUDINGCKكف纂-language sub_'

[T=1.5 + min-p 0.1]' SGA would have seen it almost four times over.\\nI can tell you the size of my learning batches and the total number of updates needed, so you could simulate your own. Would the algorithm speed up more quickly than it would if the batch size and total updates '

[what the post says]" full-batch descent needs 52 passes. The price is noise, and it shows in the last two columns. With a constant learning rate, SGD never settles. After 5,000 updates its median loss is 0.4949 against the optimum's 0.4837, and its worst run is at 0.7688, knocked"

Read together:

• Greedy is fluent for a few lines and then repeats itself, as above.
• Pure sampling at $T = 1$ has nearly the real text’s likelihood and almost no repetition, and it wanders off topic, one unlucky token at a time.
• Truncated sampling, top-k, top-p and min-p, sits between: a little repetition, likelihood between greedy’s and the real text’s, and readable text. Over the first 64 tokens the three can’t be ranked on repetition: the gaps between them are as large as the gaps between two seeds of the same policy. Min-p 0.1 stands apart in two ways, both because at this setting it keeps the fewest tokens: its likelihood, $-1.3$ to $-1.5$ against $-1.9$ to $-2.3$, is about where $T = 0.7$‘s is, and over 128 tokens it’s the most repetitive of the three on both seeds (8–9%). It sits closer to greedy: safer and more repetitive, not better.
• $T = 1.5$ alone is noise; with min-p it’s text again.

None of these measures says whether the text is good, whether it’s true or on topic. Every generated continuation above invents facts about SGD that the post doesn’t contain. A decoding policy chooses among the model’s options; it can’t add knowledge the model lacks. And the model here is instruction-tuned, which shows: several continuations turn into a question-and-answer exchange, the format it was tuned on. Tuning also typically sharpens a model’s distributions, so the likelihood gaps here are probably wider than a base model’s would be. (Some of the samples contain a literal backslash and “n”: the model wrote those characters, not newlines.)

Beam search, and why chat models don’t use it

Greedy picks the best next token; the best whole sequence may start with a token that isn’t the best next one. Beam search looks further. It keeps the $B$ most likely partial sequences, the beams, scored by their summed log-probability. At each step it extends every beam by every possible token, and keeps the $B$ best of the results. With $B = 1$ it’s greedy; as $B$ grows it gets closer to the single most likely sequence, though it’s only guaranteed to find it when the beams cover every candidate. (Hugging Face picks the final beam by summed log-probability divided by length, so long answers aren’t penalized for having more terms.)

In the comparison, with 4 beams, it does find more likely text: $-0.62$ nats per token, the highest of any policy. And it’s barely better at loops: 17% repeats in the first 64 tokens and 41% over 128, against greedy’s 25% and 49%, with 14 of 20 continuations looping against greedy’s 13. That’s the result to expect once the likelihood numbers are clear. Beam search is a better optimizer of the model’s probability, and for open-ended text, the most probable sequence is not what anyone wants: it’s repetitive and bland. The extreme case is known from translation: searching exactly for the most likely output, the model’s favorite translation of more than half of the sentences was the empty one (Stahlberg and Byrne, 2019).

Beam search does well where there’s essentially one right output and it’s short: translation, speech recognition, structured outputs. There, beam search’s own imperfection may be part of why it works (Meister et al., 2020, argue it favors text with evenly spread surprise, as people produce). For chat it costs $B$ times the compute and memory, $B$ KV caches, can’t stream a token until the beams agree, and optimizes the wrong thing. Chat systems sample.

(A first run of this beam search silently used the hidden repetition penalty of 1.1 from Qwen’s defaults, see below, and repeated fewer of its 4-grams and looped on fewer prompts: a setting nobody chose had changed the result.)

Penalties for repeating

Truncation fixes the tail; it does nothing about loops, which come from the top of the distribution. Penalties attack loops directly, by lowering the logits of tokens that have already appeared.

• The repetition penalty (Keskar et al., 2019). CTRL divides each seen token’s logit by $\theta > 1$; since dividing a negative logit would raise it, implementations such as Hugging Face’s multiply negative logits instead, so a seen token always loses: $z_i \mapsto z_i / \theta$ if $z_i > 0$, else $z_i\,\theta$. CTRL suggests $\theta \approx 1.2$ with greedy decoding; shipped defaults are milder (Qwen’s is 1.1).
• Frequency and presence penalties, as in OpenAI’s API, subtract from each seen token’s logit an amount per occurrence and an amount for having occurred at all: $z_i \mapsto z_i - \alpha_f c_i - \alpha_p\, \mathbb{1}[c_i > 0]$, with $c_i$ the number of times token $i$ has been generated so far.

Applied to greedy decoding, $\theta = 1.2$ takes the repeats from 25% to 1%, and 0 of the 20 continuations loop. But the penalty is blunt. It can’t tell a loop from words that should recur: “the”, a variable name, the subject of the paragraph. Its log-probability, $-1.43$, shows it now avoids likely tokens just because they appeared, and its text, above, wanders. Implementations also differ in what counts as “seen”: the code here penalizes only generated tokens, while Hugging Face’s applies the penalty to the prompt’s tokens too.

The order of operations

Policies are usually combined, temperature with top-p, say, and then the order matters. choose above applies penalties, then temperature, then top-k, top-p and min-p, and draws: Hugging Face’s generate uses the same order. The first output above shows why it matters. At $T = 1.5$, applying the temperature first flattens the distribution before top-p measures it, and top-p 0.9 then keeps 3,655 tokens for the sure prompt and 9,542 for the open one: the nucleus fills with tail. Measured on the distribution at $T = 1$, the same top-p keeps 5 and 26. At $T = 2$ it’s 26,113 and 45,600. Min-p is much less sensitive to the order. It compares each token with the top one, so with temperature first its cut-off in logits, $z_{\max} + T \ln p_{\text{base}}$, widens only in proportion to $T$: it keeps 3 and 4 tokens at $T = 1.5$, and 6 and 20 at $T = 2$, against top-p’s tens of thousands. With min-p first it keeps the same 2 at any temperature. In the comparison, $T = 1.5$ with min-p 0.1 reads like normal text ($-2.1$ nats per token), where $T = 1.5$ alone is noise ($-10$). That behavior at high temperatures is the case the min-p paper makes.

Engines disagree on the order. llama.cpp’s default chain applies the penalties and the filters first and temperature last, so the same settings in llama.cpp and in Hugging Face give different distributions. When a sampling setting “behaves differently” after moving engines, this is the first thing to check.

Same prompt, same seed, different text

Sampling is random, but it’s pseudo-random: a seeded generator gives the same draws every time. So “temperature 0” or “seed 42” should make output reproducible. Two checks, on the same machine:

import json
import torch
from lm import model, tok, encode, DEVICE
from sampling import generate

# Is decoding reproducible? (1) The same seed twice. (2) The same prompt
# decoded greedily on its own, and inside a batch of four prompts padded to
# the same length: mathematically the same computation for this prompt.
prompts = [p["prompt"] for p in json.load(open("prompts.json"))]

same = sum(generate(model, encode(p), 64, seed=7, p=0.9) == generate(model, encode(p), 64, seed=7, p=0.9)
           for p in prompts[:5])
print(f"top-p 0.9, the same seed twice: identical text for {same} of 5 prompts")

@torch.no_grad()
def greedy(batch):
    tok.padding_side = "left"
    enc = tok(batch, return_tensors="pt", padding=True).to(DEVICE)
    out = model.generate(**enc, max_new_tokens=64, do_sample=False, pad_token_id=tok.eos_token_id,
                         repetition_penalty=1.0,     # the model's generation_config.json sets 1.1
                         output_scores=True, return_dict_in_generate=True)
    return out.sequences[:, enc.input_ids.shape[1]:].tolist(), out.scores[0].float()

diverged, first, gaps = 0, [], []
for i in range(0, 20, 4):
    batch = prompts[i:i + 4]
    together, scores_b = greedy(batch)
    for j, p in enumerate(batch):
        alone, scores_a = greedy([p])
        gaps.append((scores_a[0] - scores_b[j]).abs().max().item())
        a, b = alone[0], together[j]
        if a != b:
            diverged += 1
            first.append(next(k for k in range(min(len(a), len(b))) if a[k] != b[k]))
print(f"greedy, alone vs in a padded batch of 4: largest first-step logit difference "
      f"{max(gaps):.3f} (median {sorted(gaps)[10]:.3f}); the 64-token outputs differ for {diverged} of 20 "
      f"prompts, first at token {sorted(first) if first else '-'}")

Full script: reproducible.py

top-p 0.9, the same seed twice: identical text for 5 of 5 prompts
greedy, alone vs in a padded batch of 4: largest first-step logit difference 0.039 (median 0.027); the 64-token outputs differ for 3 of 20 prompts, first at token [22, 37, 52]

The same seed gives the same text, every time. But greedy decoding, which involves no randomness at all, gives different text for 3 of 20 prompts depending on whether the prompt runs alone or in a batch of four, where the shorter prompts are padded on the left to the longest one’s length and the padding is masked out. Mathematically the computation for each prompt is the same. Numerically it isn’t: a batch of a different shape can run through different kernels or tilings, which add the same numbers in a different order, and floating-point addition isn’t associative (PyTorch from the Inside). In 16-bit floats the first step’s logits differ by up to 0.04. That’s nothing until two tokens are nearly tied; then the argmax flips, and every later token follows a different history, here first at tokens 22, 37 and 52. The same first-step comparison, directly, in 16-bit and in 32-bit floats:

# The first step's logits for four prompts, alone and in a padded batch,
# in 16-bit and in 32-bit floats (run once with each: python det_check.py 16 / 32).
import json, sys, torch
from transformers import AutoModelForCausalLM, AutoTokenizer
from lm import PATH
DEVICE = "cuda" if torch.cuda.is_available() else "mps" if torch.backends.mps.is_available() else "cpu"
dtype = {"16": torch.float16, "32": torch.float32}[sys.argv[1]]
tok = AutoTokenizer.from_pretrained(PATH); tok.padding_side = "left"
model = AutoModelForCausalLM.from_pretrained(PATH, dtype=dtype).to(DEVICE).eval()
prompts = [p["prompt"] for p in json.load(open("prompts.json"))][:4]
with torch.no_grad():
    enc = tok(prompts, return_tensors="pt", padding=True).to(DEVICE)
    pos = (enc.attention_mask.cumsum(-1) - 1).clamp(min=0)
    b = model(**enc).logits[:, -1].float()
    b2 = model(**enc, position_ids=pos).logits[:, -1].float()
    for j, p in enumerate(prompts):
        a = model(**tok([p], return_tensors="pt").to(DEVICE)).logits[0, -1].float()
        print(sys.argv[1], j, "pad tokens", int((enc.attention_mask[j] == 0).sum()), "diff", round((a - b[j]).abs().max().item(), 4), "with position_ids", round((a - b2[j]).abs().max().item(), 4))

Full script: det_check.py

det_check_both.py runs it once in 16-bit and once in 32-bit floats.

16 0 pad tokens 17 diff 0.0195 with position_ids 0.0312
16 1 pad tokens 7 diff 0.0234 with position_ids 0.0234
16 2 pad tokens 0 diff 0.0273 with position_ids 0.0273
16 3 pad tokens 16 diff 0.0293 with position_ids 0.0352
32 0 pad tokens 17 diff 0.0 with position_ids 0.0
32 1 pad tokens 7 diff 0.0 with position_ids 0.0
32 2 pad tokens 0 diff 0.0 with position_ids 0.0
32 3 pad tokens 16 diff 0.0001 with position_ids 0.0001

In 16 bits the logits differ by 0.02–0.03, a few units in the last place of a 16-bit float at these magnitudes, and that includes the prompt that needed no padding at all: it’s the batch’s shape, not the padding. In 32 bits, on this backend, three of the four agree to the four decimals printed, and the fourth differs by 0.0001. Passing explicit position numbers for the padded rows changes little, as it should: RoPE depends only on relative position (Where Am I? Position in Attention, from Sinusoids to RoPE), so shifting every position by the same amount leaves attention unchanged. That’s this laptop; serving GPUs run 16-bit arithmetic with constantly changing batch shapes, which is the case Thinking Machines studied.

This is why an API called twice with temperature 0 can return different text. A server batches whatever requests arrive together, so the batch, and with it the arithmetic, changes from call to call. Horace He and Thinking Machines (2025) traced this to kernels that aren’t batch-invariant, and showed that it’s fixable, at some cost in speed, with kernels whose results don’t depend on the batch.

One more trap, found while writing this post. Hugging Face’s generate reads defaults from the model’s generation_config.json, and Qwen2.5’s sets a repetition penalty of 1.1, along with temperature 0.7, top-p 0.8 and top-k 20 for sampling. The first run of the beam search and batch experiments silently used that penalty. It also skewed the batch comparison, since the penalty applies to every token of the input, padding included, and gave logit differences far larger than 0.04. The code above passes repetition_penalty=1.0 explicitly. Check what defaults a model ships with before measuring anything about decoding.

Other knobs

A few more settings that appear in every API and engine, each another edit to the logits or the loop:

• Stop sequences and a token limit end generation: the stop set in generate above, or strings an API watches for.
• Logit bias adds a fixed amount to chosen tokens’ logits; $-\infty$ bans a token.
• Constrained decoding masks, at every step, every token that would break a grammar or a JSON schema: the same “set the logit to $-\infty$” mechanism, driven by a parser (Willard and Louf, 2023). Serving engines can use it to guarantee well-formed tool calls, as From Function Calling to the Agent Loop describes.
• Targeted repetition controls: no_repeat_ngram_size bans exact repeats of an $n$-gram; llama.cpp’s DRY penalizes extending a sequence that already occurred. Both aim at loops without taxing every repeated word.
• Other truncation rules: typical sampling, $\epsilon$- and $\eta$-sampling, top-$n\sigma$, all variations on “drop the unlikely tail”, with different definitions of unlikely. Contrastive search (Su et al., 2022) instead trades likelihood against similarity to the text so far.
• Ranges and defaults differ. OpenAI’s API takes temperature from 0 to 2 (default 1), Anthropic’s from 0 to 1; some reasoning models fix the temperature or ignore it, and a seed parameter is “best effort”. llama.cpp’s defaults are $T = 0.8$, top-k 40, top-p 0.95 and min-p 0.05; Qwen2.5 ships $T = 0.7$, top-k 20, top-p 0.8 and a repetition penalty of 1.1.

Speculative decoding (Speculative Decoding, Derived) makes generation faster without changing any of this: it reproduces the sampling distribution exactly, so the policies above still apply.

What decoding costs

cost.py times one forward pass against the policy that picks the token. Its sync waits for the GPU to finish before the clock is read: torch.mps.synchronize on the Apple GPU the post ran on, torch.cuda.synchronize on an NVIDIA one:

prompt = encode("The KV cache stores the keys and values of every earlier token, so")
g = torch.Generator(device=prompt.device).manual_seed(0)
with torch.no_grad():
    out = model(prompt[None], use_cache=True)
    logits, cache = out.logits[0, -1], out.past_key_values
    def step():
        model(torch.tensor([[11]], device=prompt.device), past_key_values=cache, use_cache=True)
    def timed(fn, n=30):
        for _ in range(3):
            fn()
        sync(); t0 = time.perf_counter()
        for _ in range(n):
            fn()
        sync()
        return (time.perf_counter() - t0) / n * 1e3
    print(f"forward pass for one token: {timed(step):.1f} ms")
    for name, policy in (("greedy", dict(temperature=0)), ("top-p 0.9", dict(p=0.9)),
                         ("T 0.7 + top-k 40 + top-p 0.9 + min-p 0.05 + repetition 1.1",
                          dict(temperature=0.7, k=40, p=0.9, mp=0.05, rep=1.1))):
        print(f"choosing the token, {name}: {timed(lambda: choose(logits, list(range(50)), g, **policy)):.2f} ms")

Full script: cost.py

forward pass for one token: 41.0 ms
choosing the token, greedy: 0.24 ms
choosing the token, top-p 0.9: 0.91 ms
choosing the token, T 0.7 + top-k 40 + top-p 0.9 + min-p 0.05 + repetition 1.1: 1.61 ms

Choosing the token is cheap, on one sequence on a laptop: well under 2 ms with every policy combined, against 41 ms for the model’s forward pass, so under 4% of a step. (At serving batch sizes the per-row sort for top-p starts to show, which is why serving engines ship sampling kernels that avoid sorting.) Even top-p’s sort over 152,000 logits costs under a millisecond. What decoding costs is not the policy but the loop around it: each token needs its own forward pass, which needs the token before it. Generation is sequential, one model call per token, and that cost is what The KV Cache, FlashAttention and serving engines such as the one in vLLM Architecture are built to reduce.

Where this leads

• Streaming Tokens to the User sends these tokens to a user as they’re generated, and measures what the reader actually waits for.
• The KV Cache is what makes the one-token-at-a-time loop in generate affordable, and vLLM Architecture shows a serving engine running it for many users at once, which is where the batch effects above come from.
• Temperature comes back in distillation (Knowledge Distillation), where soft probabilities carry what the model knows, and in evaluation, where a single sample isn’t a measurement.

Takeaways

• A model outputs a distribution over its vocabulary; decoding is a separate policy that turns it into text, and it changes the text as much as the weights do.
• Greedy and beam search maximize likelihood, and the most likely text is repetitive: greedy repeated 25% of its 4-grams, beam search 17%, the posts’ real text 0.3%. Real text scores far lower under the model ($-3.5$ nats per token) than greedy text ($-0.85$), partly from the model’s error and partly because real text isn’t the most likely text.
• Temperature $T$ divides the logits: $T \to 0$ is greedy, $T \to \infty$ is uniform. Sampling at $T = 1$ comes close to human likelihood but drifts, because of the long tail of unlikely tokens.
• Truncation removes the tail: top-k keeps a fixed count, top-p a fixed mass, min-p everything within a fraction of the top token. Top-p and min-p adapt to how sure the model is; min-p also degrades far more gracefully at high temperatures, though its advantage over well-tuned top-p is disputed.
• Order matters: temperature before top-p can flood the nucleus with thousands of tokens, and engines differ (Hugging Face applies temperature first, llama.cpp last).
• Repetition penalties stop loops bluntly, by also penalizing words that should recur.
• The same seed reproduces sampling, but batching changes floating-point arithmetic, so even greedy output can change with the batch. Check the defaults a model ships with, too: Qwen2.5’s add a repetition penalty silently.
• Choosing a token costs about a millisecond; the forward pass costs 40. Decoding is cheap but sequential.

References

Start with Holtzman et al., the paper that explained why the most likely text is the wrong target and introduced top-p. Then read the Thinking Machines post on nondeterminism, and the min-p paper together with its reanalysis.

• Holtzman, Buys, Du, Forbes and Choi, The Curious Case of Neural Text Degeneration (ICLR, 2020): nucleus (top-p) sampling, and human text vs the most likely text.
• Fan, Lewis and Dauphin, Hierarchical Neural Story Generation (ACL, 2018): top-k sampling.
• Nguyen, Baker, Neo, Roush, Kirsch and Shwartz-Ziv, Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs (ICLR, 2025): min-p.
• Keskar, McCann, Varshney, Xiong and Socher, CTRL: A Conditional Transformer Language Model for Controllable Generation (2019): the repetition penalty.
• Schaeffer, Kazdan and Denisov-Blanch, Min-p, Max Exaggeration: A Critical Analysis of Min-p Sampling in Language Models (2025): a reanalysis of min-p’s evidence.
• Willard and Louf, Efficient Guided Generation for Large Language Models (2023): constrained decoding with grammars and regular expressions (Outlines).
• Su, Lan, Wang, Yogatama, Kong and Collier, A Contrastive Framework for Neural Text Generation (NeurIPS, 2022): contrastive search.
• Stahlberg and Byrne, On NMT Search Errors and Model Errors: Cat Got Your Tongue? (EMNLP, 2019): exact search finds the empty translation most likely.
• Meister, Vieira and Cotterell, If Beam Search is the Answer, What was the Question? (EMNLP, 2020): beam search as a bias toward evenly spread surprise.
• He and Thinking Machines Lab, Defeating Nondeterminism in LLM Inference (2025): batch size, not concurrency, as the source of nondeterminism.
• Qwen Team, Qwen2.5 Technical Report (2024): the model used here.