LLM Sampling — Greedy, Beam, Top-k, Top-p, Temperature

Why this session exists

A language model supplies logits; decoding chooses an output sequence. Changing temperature, support truncation, penalties or search changes that policy without changing the model weights. It can affect repetition, diversity, accuracy and latency, but there is no evidence that a particular slider causes half of all RAG hallucinations.

We will derive the transformations, work through a distribution, implement exact edge-case behavior and compare greedy with beam search on a finite tree. The examples are CPU probability fixtures, not GPT-2 generation or vendor-service benchmarks.

Outcomes: explain temperature/top-k/top-p/beam width; implement and test them; distinguish format constraints from factuality; diagnose repetition and nondeterminism; and translate a tested policy into a model-specific API configuration rather than memorizing supposed industry defaults.

Prerequisites

Session 112's causal factorization also applies to an encoder-decoder's target generation. Decoder-only models are not the only models that sample. Know logits, softmax and conditional probabilities.

(a) Intuition · 5 min

A forecaster supplies a distribution and a decision-maker chooses how to use it. Always choosing the most likely weather is different from sampling weather in proportion to probability. Neither policy makes an incorrect forecast true. Similarly, a valid token under a model is not necessarily a correct fact, safe tool call or authorized SQL query.

The core distinction — deterministic vs stochastic

Greedy and conventional beam search are deterministic given identical logits, score definitions and tie-breaking. Sampling uses a pseudorandom draw. A fixed seed helps reproduce a fixed software/hardware execution, but batching, floating-point reductions, model revisions and kernels may change logits or random-number consumption. Cache keys should identify the complete request/model/policy rather than assume temperature zero fixes every dependency.

Beam sampling and other hybrids exist. Deterministic versus stochastic is a useful first distinction, not a prohibition against combining methods. Code synthesis can benefit from sampling several candidates and running tests; a single correct-answer task does not imply greedy always has the highest success rate.

Short history of decoding

Beam search predates neural language models and has long been used in speech/translation. Top-k was used for neural story generation before nucleus sampling's 2019 preprint. Holtzman et al. study degeneration under likelihood-oriented decoding and introduce adaptive nucleus truncation [1]. Structured decoding did not first appear in 2024; recent APIs made selected constrained-output modes easier to use. Historical scope matters more than an invented chronology of universal defaults.

The pipeline from logits to token

The ordering is part of the contract. Temperature before top-p changes nucleus membership; top-k before top-p means the latter is measured on the renormalized top-k support. Do not describe a different ordering than the code executes. Constraints may remove the unconstrained argmax; if every token is illegal, the controller must fail or recover explicitly, not call softmax on an all-negative-infinity row. The diagram includes that production constraint stage; the finite-vector CPU sampler below does not implement grammar masks and rejects infinite logits.

What each knob actually does

For finite logits z and positive T,

Log odds scale as $(z_i-z_j)/T$. Positive temperature preserves ranking, sharpens for T below one and flattens for T above one. At T=0 the formula is undefined: this lesson implements a separate argmax branch. As T tends to zero with tied maxima, softmax approaches a uniform distribution over those ties; that is not the same as a deterministic tie-breaking argmax. Dividing by a tiny epsilon and sampling is therefore not exact greedy.

Top-k keeps k ranked IDs. Thresholding at the kth logit may keep more than k when there are ties; our stable sort keeps exactly k. Top-p keeps the smallest sorted prefix whose mass is at least p, then renormalizes. Keep the crossing token, and stop at an exact equality. At p=1, explicitly disable nucleus filtering: a floating-point cumulative sum can round to one before reaching small but representable tail probabilities. The program rejects k outside 1..V and p outside (0,1]. Libraries can choose different boundary/min-token conventions; Transformers 4.57.1 provides its own documented processors [2].

Repetition penalty is not simply dividing every seen logit. For factor r>1, positive seen logits are divided by r and negative ones multiplied by r; otherwise a negative logit would increase and encourage repetition. Apply once per unique seen token for this multiplicative policy. Frequency and presence penalties are different additive policies. Penalizing every repeated token can damage legitimate repetitions in names, code and quotes.

Same prompt, four decoding strategies

Suppose the next-token probabilities are Python .72, R .10, Julia .06, Rust .04, JavaScript .03 and 50,000 tail tokens with total mass .05. At T=1, p=.9, cumulative head masses are .72,.82,.88,.92, so the nucleus is the first four. Conditional probabilities within it are those four probabilities divided by .92.

At T=.7 the probabilities must be transformed before selecting the nucleus. The original page incorrectly reused the T=1 membership. Also, knowing only total tail mass is insufficient for computing its transformed mass: $(a+b)^{1/T}$ is generally not $a^{1/T}+b^{1/T}$. The executable example explicitly assumes a uniform tail and reports the resulting nucleus; no hidden vendor vocabulary is inferred.

At T=1.5 the tail's many small terms can collectively matter more. Greedy still selects Python, but a wider beam might prefer a sequence beginning with R if its later conditional probabilities are better. A high-probability token is not a guarantee of a high-probability full sequence.

Beam search, length bias and a worked counterexample

Let the first step give A=.6 and B=.4. After A, EOS=.4 and an alternative=.6; after B, EOS=.9 and an alternative=.1. For two-step completed paths, A→alternative has probability .36 and B→EOS also .36; tweak A's continuation to EOS=.55/alternative=.45 and greedy A→EOS=.33 loses to B→EOS=.36. Width-two search keeps B long enough to discover the latter. The fixture uses that unambiguous .33 versus .36 example and checks against exhaustive enumeration.

Beam search retains B partial hypotheses by cumulative log probability and moves EOS-completed hypotheses into a completed set. Pruning makes it approximate: a pruned prefix can later have the best completion. Multiplying probabilities ≤1 naturally favors short completions in some tasks; length normalization changes the objective and requires a specified exponent/denominator. Minimum Bayes risk instead selects a candidate minimizing expected task loss under a candidate distribution. More search under the wrong model/objective need not improve translation or chat quality.

Presets you should test, not memorize

• Extraction/JSON/SQL: compare greedy with a supported constrained-output mode. Validate schema and semantics; SQL additionally needs authorization and an execution policy. Low T cannot supply those.
• Chat: start from the checkpoint's documented recommendation, then assess quality and variation on realistic dialogue. The page does not know Claude or ChatGPT's private defaults.
• Code: evaluate greedy and several sampled candidates with exact tests. Record cost per accepted solution, not only pass rate per sample.
• Creative writing: sweep temperature and support, judge diversity/coherence and deduplicate outputs. Per-sequence repetition penalties do not automatically diversify ten independent completions against one another.
• RAG: measure evidence support, abstention and answer accuracy separately from style. Low temperature may reduce variation but confidently preserve an unsupported fact.
• Tool selection/judging: require validated structured proposals and stable evaluation configurations. Repeated trials may be useful to estimate judge variance; temperature zero is not an authenticity or permission check.

Tune one control at a time initially to identify its effect. Combining T and top-p is mathematically valid and supported by some APIs; it is not forbidden. OpenAI, Anthropic and vLLM expose different options and model-specific restrictions. Before applying a preset, check the exact endpoint/model, whether temperature/top-p are supported, defaults, accepted ranges, stop/max-output semantics, seed behavior and structured-output limitations. Omit unsupported controls rather than assuming all providers mirror one API. No paid API call is made here.

Translating the policy to versioned APIs

These source-checked interfaces are pinned examples, not a claim that every current model accepts every field:

Current API check (2026-10-09): Anthropic's Messages parameter documentation now marks these sampling controls deprecated for models released after Claude Opus 4.6: temperature accepts only 1.0 for backward compatibility, any top_k is rejected, and top_p accepts only values at least 0.99 [5]. Omit these controls for that model group instead of copying temperature=0 from the historical SDK row. This is a documentation check, not a live request test.

Before sending any request, check the selected model's restrictions, especially reasoning/thinking modes, and its output-budget field. The versioned SDK schema documents the general interface, not server acceptance for every model. The local sampler intentionally rejects top_k=0 while vLLM uses it as a disable sentinel: translate semantics, do not blindly copy arguments. None of these source checks is an API execution or a guarantee of factual output.

Two dials: candidates and sharpness

A finite-logit softmax has positive probability everywhere in real arithmetic; machine underflow or explicit masks can yield zeros. If a bad-tail event has conditional probability ε at every step along surviving histories, survival over n steps is $(1-\epsilon)^n$. Independence of generated tokens is not required for that conditional product, and actual probabilities vary with history. Truncation changes support, temperature changes relative weights and penalties depend on history. None identifies truth by itself.

For machine-consumed output, a correct grammar-aware decoder can restrict tokens to legal continuations, but supported schema subsets, refusal paths, truncation and incomplete outputs must be handled. A well-formed JSON object can still contain wrong or unauthorized values. Validate both layers.

(c) Hands-on · 25 min

The full program below executes the policy on fixed logits, generates from a local transition table, compares a beam frontier with exhaustive search and tests negative controls. It replaces the old automatic GPT-2 download with a testable probability experiment. For a later locally supplied causal checkpoint, pass its final-position logits into sample_next, append the returned ID, stop on EOS/budget and enforce its position limit. That adapter changes the source of logits, not the sampler's contract.

import math,itertools
import torch
torch.set_num_threads(1);torch.manual_seed(113)
 
def penalize(logits,already=(),factor=1.0):
    if logits.ndim!=1 or not len(logits) or not logits.is_floating_point() or not torch.isfinite(logits).all():
        raise ValueError('finite floating-point vector required')
    if not math.isfinite(factor) or factor<=0:raise ValueError('invalid penalty')
    z=logits.to(torch.float64).clone()  # CPU teaching policy, not a fast device kernel.
    for i in set(already):
        if type(i) is not int or not 0<=i<len(z):raise ValueError('invalid history ID')
        z[i]=z[i]/factor if z[i]>0 else z[i]*factor
    if not torch.isfinite(z).all():raise ValueError('penalized logits overflowed')
    return z
 
def distribution(logits,temperature=1.0,top_k=None,top_p=1.0,already=(),penalty=1.0):
    if logits.ndim!=1 or not len(logits) or not torch.isfinite(logits).all():raise ValueError('finite vector required')
    if not math.isfinite(temperature) or temperature<=0:raise ValueError('positive temperature required')
    if not math.isfinite(top_p) or not 0<top_p<=1:raise ValueError('invalid p')
    if top_k is not None and (type(top_k) is not int or not 1<=top_k<=len(logits)):raise ValueError('invalid k')
    z=penalize(logits,already,penalty)
    order=torch.argsort(z,descending=True,stable=True)
    if top_k is not None:order=order[:top_k]
    # Center before dividing: tiny positive T must not turn tied maxima into +inf.
    scaled=(z[order]-z[order[0]])/temperature
    weights=scaled.softmax(0)
    # At p=1 keep all ranks, even if cumulative mass rounds to one early.
    prior=torch.cat((weights.new_zeros(1),weights.cumsum(0)[:-1]))
    keep=torch.ones_like(weights,dtype=torch.bool) if top_p==1 else prior<top_p
    keep[0]=True
    out=torch.zeros_like(z);out[order[keep]]=weights[keep];return out/out.sum()
 
def sample_next(logits,temperature=1.0,**kwargs):
    if not math.isfinite(temperature) or temperature<0:raise ValueError('invalid temperature')
    if temperature==0:
        # Validate optional controls too; greedy ignores support filters retaining argmax.
        distribution(logits,1.0,**kwargs)
        return int(penalize(logits,kwargs.get('already',()),kwargs.get('penalty',1.0)).argmax())
    return int(torch.multinomial(distribution(logits,temperature,**kwargs),1))
 
p=torch.tensor([.5,.25,.125,.125],dtype=torch.float64);z=p.log()
assert torch.equal(distribution(z,top_p=.75)>0,torch.tensor([True,True,False,False]))
assert torch.equal(distribution(torch.zeros(4,dtype=torch.float64),top_k=2)>0,torch.tensor([True,True,False,False]))
assert sample_next(torch.zeros(4),temperature=0)==0
assert torch.allclose(distribution(z,temperature=.5),p.square()/p.square().sum())
# Tiny representable tails survive p=1; tiny T preserves uniform tied maxima.
tail=torch.tensor([0.,-40.],dtype=torch.float64)
assert distribution(tail,top_p=1)[1]>0
assert torch.equal(distribution(torch.ones(2,dtype=torch.float64),temperature=1e-320),torch.tensor([.5,.5],dtype=torch.float64))
assert torch.equal(distribution(torch.tensor([1.,0.]),temperature=1e-320),torch.tensor([1.,0.],dtype=torch.float64))
# Signed division must not silently truncate an integer input.
try:penalize(torch.tensor([2,1]),[0],1.2)
except ValueError:pass
else:raise AssertionError('integer logits accepted')
# Independent scalar inverse-CDF support/mass oracle.
expected=[.5/.75,.25/.75,0,0]
assert all(abs(float(a)-b)<1e-14 for a,b in zip(distribution(z,top_p=.75),expected))
q=penalize(torch.tensor([2.,-1.]),[1],1.2);assert abs(float(q[1])+1.2)<1e-6
assert float(q[1]) < -1 and -1/1.2 > -1
assert sample_next(torch.tensor([100.,1.]),0,already=[0],penalty=1.2)==0
assert sample_next(torch.tensor([2.,1.9]),0,already=[0],penalty=1.2)==1
for call in [lambda:distribution(z,top_k=5),lambda:distribution(z,top_p=0),
             lambda:distribution(z,temperature=-1),lambda:distribution(torch.tensor([float('nan')]))]:
    try:call()
    except ValueError:pass
    else:raise AssertionError('invalid input accepted')
full=torch.tensor([.72,.10,.06,.04,.03]+[.05/50000]*50000,dtype=torch.float64)
for t in (1.,.7,1.5):
    probs=distribution(full.log(),temperature=t,top_p=.9)
    print('uniform-tail illustration',t,'nucleus size',int((probs>0).sum()),'head',probs[:5].tolist())
assert (distribution(full.log(),top_p=.9)>0).sum()==4
# A tiny transition model with an explicit EOS and hard output budget.
trans=torch.tensor([[.6,.3,.1],[.2,.5,.3],[.1,.1,.8]],dtype=torch.float64)
def generate(start,max_new,**policy):
    ids=[start]
    for _ in range(max_new):
        nxt=sample_next(trans[ids[-1]].log(),already=ids,**policy);ids.append(nxt)
        if nxt==2:break
    return ids
for policy in [dict(temperature=0),dict(temperature=.7,top_k=2),dict(temperature=1.,top_p=.9)]:
    print('transition sample',policy,generate(0,8,**policy))
# Beam search for two-step completed candidates; exhaustive oracle is independent.
first={'A':.6,'B':.4};second={'A':{'EOS':.55,'X':.45},'B':{'EOS':.9,'X':.1}}
def beam(width):
    frontier=[((),0.)]
    for depth in range(2):
        candidates=[]
        for seq,score in frontier:
            dist=first if not seq else second[seq[-1]]
            candidates.extend((seq+(token,),score+math.log(prob)) for token,prob in dist.items())
        frontier=sorted(candidates,key=lambda v:(-v[1],v[0]))[:width]
    return frontier[0]
assert beam(1)[0]==('A','EOS') and beam(2)[0]==('B','EOS')
all_paths=[((a,b),first[a]*second[a][b]) for a in first for b in second[a]]
assert max(all_paths,key=lambda x:x[1])[0]==beam(2)[0]
# Explicit nonassociativity, not a probabilistic random reduction test.
a,b,c=[torch.tensor(v,dtype=torch.float32) for v in (1e20,-1e20,3.14)]
assert float((a+b)+c)!=float(a+(b+c))
print('sampling support, penalties, beam oracle and negative controls passed')

Line-by-line

Convert floating-point logits to a cloned float64 working vector before applying a penalty so the caller's tensor is not mutated and integer assignment cannot truncate a penalty. Reject nonfinite inputs or overflowing penalty results; T=0 uses argmax directly. Stable sorting defines tie order. Subtract the largest penalized logit before dividing by positive T; this prevents positive overflow at tied maxima for tiny T. Very negative scaled differences can still underflow to zero probability. Nucleus inclusion compares the cumulative mass before each token with p, preserving the first crossing and handling equality; p=1 bypasses this comparison so a rounded cumulative sum cannot spuriously discard the tail. torch.multinomial supplies categorical draws; its internal algorithm is not promised to be inverse-CDF across every backend.

The local generation fixture returns IDs under several policies, not stories whose fluency can be evaluated. A seed controls those fixture draws only. The original “greedy T=.01” was stochastic; the explicit zero branch fixes that. The repetition experiment checks both a case that changes the winning token and a case where a penalty leaves the winner unchanged. A universal loop-fixing promise would fail the second case.

Practice: repetition and numeric reproducibility

Take logits [2,-1] with the second ID already seen. Dividing −1 by 1.2 gives −.8333, making it more likely; multiplying gives −1.2, correctly reducing it. Then use logits [100,1] with the first seen: a penalty of 1.2 still leaves it on top. Sampling is also capable of repeating a token.

For deterministic floating-point non-associativity use (1e20 + -1e20) + 3.14 versus 1e20 + (-1e20 + 3.14) in float32. A small random reduction-order difference is not guaranteed on every run. This counterexample establishes the numerical mechanism, not a measured frequency of commercial serving drift.

(d) Production reality · 15 min

Diagnose a RAG error by checking retrieved evidence/version, prompt, output and effective decoding configuration together. Do not replace this trace with an unsupported Notion/Zapier temperature anecdote. Similarly, random sampling is not copyright insurance and does not eliminate memorization; a public-code matching control is a separate mechanism, not evidence for a private Copilot decoding preset.

KV caching stores past keys/values. With a fixed-width dense model and output length T, recomputing every entire prefix incurs a sum of quadratic attention work, O(T³); incremental cached decoding has O(T) attention per new token and O(T²) total after prefill. Projection/FFN work also changes and prompt length affects constants. These asymptotic statements are not a promised 10–100× latency gain.

Speculative decoding can preserve a target sampling distribution with an acceptance/rejection correction, not merely by accepting any draft whose token “looks right.” For a draft proposal q and target p, accept a proposed token with probability min(1,p/q); on rejection sample from the normalized positive residual max(p−q,0), under the algorithm's assumptions [3]. Verification can process proposed positions together. Acceptance rate, draft cost and hardware determine whether this helps; this lesson does not claim a vendor implements any particular variant.

Where this shows up next

Prompting and sampling interact but need separate ablations. Candidate reranking and self-consistency add another selection layer. Serving includes batching, caching and kernels; evaluation must retain the entire policy and stopping criteria. Structured tool calls remain proposals to validate, regardless of deterministic decoding.

(e) Recall + stretch · 10 min

1. T=0? A separate deterministic argmax branch with specified tie-breaking; tiny-temperature multinomial is not equivalent on ties.
2. Top-k/top-p? Fixed rank count versus smallest cumulative-mass prefix. Define ties, equality and ordering with temperature; explicitly bypass nucleus filtering at p=1 rather than trusting rounded cumulative sums.
3. Repetition? Feedback between context and the model's next-token distribution can form loops. Penalties or sampling may help, but neither guarantees escape.
4. SQL generator? Test a low-variation policy plus grammar/schema constraints; validate identifiers, intent, authorization and read/write limits before execution.
5. Beam for chat? It optimizes its sequence score, which may poorly align with useful/diverse conversation. It is approximate and requires EOS/length handling.
6. RAG hallucination? Inspect evidence, version, prompt and effective decoding settings; do not assume a default temperature explains most failures.
7. T or top-p? Change one at a time for interpretable tuning; combining them is valid but changes support and sharpness together.
8. KV cache? Reuse past K/V to avoid full-prefix recomputation; attention over past keys still grows with prefix length.
9. Ten names? Sample candidates under a validated policy, deduplicate across completions and assess coherence. Presence/frequency penalties within one output do not enforce cross-output diversity.
10. Speculation? A draft proposes, target verifies and acceptance/residual sampling corrects the distribution. It is not greedy matching or an unconditional speedup.

Explain-out-loud test

Derive the power transform, show the .33 versus .36 greedy counterexample, compute a nucleus at T=1 and after a temperature change, and explain why there is no one-slider fix for half of RAG errors.

What comes next

Scaling laws concerns training allocation, not decoding quality. Learning-plan hub.

Primary references

1. Holtzman et al., The Curious Case of Neural Text Degeneration, 2019 preprint/ICLR 2020.
2. Transformers v4.57.1 logit processors.
3. Leviathan et al., Fast Inference from Transformers via Speculative Decoding, ICML 2023.
4. OpenAI Python 1.109.1 request schema, Anthropic Python 0.69.0 Messages schema, and vLLM 0.11.0 SamplingParams.
5. Anthropic Messages API parameter restrictions, checked 2026-10-09.