Sampling & decoding strategies

What it is (intuition first)

At every generation step a language model produces one thing: a probability distribution over its entire vocabulary. Decoding is the policy that turns that distribution into the one token you actually emit, repeated autoregressively until you stop. It is the layer that sits after the model and before the text — the model proposes, the decoding strategy disposes.

This is the orthogonal sibling of constrained decoding ([[constrained-decoding-structured-output]]). Constrained decoding decides which tokens are legal; sampling decides which legal token you pick. You can stack them — mask first, then sample from what survives.

The intuition that makes the whole field click: the model's probability distribution has a long, unreliable tail. The top few tokens are usually trustworthy; the thousands of low-probability tokens in the tail are mostly noise the model can't really distinguish. The two failure modes of decoding come from trusting that tail too much or too little:

• Trust it too little (always take the single most likely token, or search for the globally most-probable sequence) and you get degeneration — bland, repetitive, loopy text. Holtzman et al. (arXiv:1904.09751) showed that maximization-based decoding like beam search drives high-quality models into repetitive, unnatural loops, and that the model often assigns higher aggregate probability to repetitive text than humans ever would.
• Trust it too much (sample from the full distribution at high temperature) and you periodically draw a token from the garbage tail, derailing into incoherence.

Every practical strategy is therefore some form of truncation + randomness: cut the unreliable tail, then sample from what's left. The whole zoo of knobs (temperature, top_k, top_p, min_p) is just different ways of drawing that cut line.

Why it matters

• It is a free quality dial you control at inference time. No retraining, no new weights — changing temperature or swapping top-p for min-p changes the character of every output. For the same model, a good sampling config is the difference between "creative and coherent" and "either boring or unhinged."
• It is task-shaped, not model-shaped. Deterministic tasks (code, math, tool arguments, extraction) want near-greedy decoding so the answer is stable and the format holds. Open-ended tasks (brainstorming, fiction, persona) want a wider, warmer distribution. The same model needs opposite settings for these — which is why a single global default is always a compromise.
• It is where reproducibility quietly dies. Even at temperature=0 ("greedy"), production LLM endpoints are usually not bit-deterministic — and the reason is not the sampler but the serving stack (see §5). This breaks caching, evals, and RL training that assume the same input gives the same output.
• It interacts with everything downstream. Speculative decoding ([[speculative-decoding]]) must preserve the target sampler's distribution to be lossless; structured/tool outputs ([[tool-use-function-calling]]) usually want low temperature so the schema holds; an [[agentic-loops]] step that samples its tool args too hot will hand the executor malformed JSON.

How it works (real mechanics)

0. The softmax + temperature knob

The model outputs raw logits z; a softmax turns them into probabilities. Temperature T rescales the logits before softmax: softmax(z / T).

• T → 0: the distribution collapses onto the single highest logit → greedy (argmax). Deterministic in principle (caveats in §5).
• T = 1: the model's native distribution, untouched.
• T > 1: the distribution flattens — low-probability tokens get more mass → more diverse, more risk of incoherence.

Temperature alone is a poor safety mechanism, because raising it for creativity also fattens the unreliable tail. That is the entire motivation for truncation methods, which are usually applied together with temperature: truncate first to delete the tail, then let temperature add randomness over the survivors.

1. Greedy and beam search — the maximization family

Greedy takes argmax every step. Beam search keeps the k highest-aggregate- probability partial sequences and extends them, returning the most probable complete sequence. Both chase high total sequence probability — and that is exactly the trap Holtzman et al. identified: for open-ended generation, the most-probable sequence is often a degenerate repetitive loop, not good text. Maximization works well for closed-ended tasks where there genuinely is one right answer (translation, short factual answers, constrained extraction) and badly for open-ended ones.

2. Top-k and top-p (nucleus) — fixed vs. dynamic truncation

• Top-k keeps the k highest-probability tokens, zeroes the rest, renormalizes, samples. Simple, but k is a fixed count — wrong in both regimes: when the model is confident (one obvious next token) k=50 still admits 49 distractors; when it's genuinely uncertain (many plausible continuations) k=50 may chop valid options.
• Top-p / nucleus sampling (Holtzman et al., arXiv:1904.09751) fixes this by truncating on cumulative probability mass instead of count: sort tokens descending, keep the smallest set whose probabilities sum to ≥ p (e.g. 0.9), sample from that "nucleus." The nucleus is dynamic — small when the model is confident, large when it's uncertain — which is why it became the default open-ended sampler for years. Holtzman et al. argued nucleus sampling produces long-form text that is both higher quality and more diverse than beam search or pure sampling on their human and automatic evaluations.

3. Min-p — confidence-scaled truncation (and a live controversy)

Min-p sampling (Nguyen et al., Turning Up the Heat, arXiv:2407.01082, ICLR 2025 Oral) sets the cut relative to the top token's probability. The threshold is

threshold = p_base × p_max

where p_max is the highest token probability this step and p_base is the knob (e.g. 0.1). Keep every token with probability ≥ threshold, drop the rest. The effect:

• When the model is confident (p_max high, say 0.9 → threshold 0.09) the gate is strict, admitting only strong candidates.
• When the model is uncertain (p_max low, say 0.2 → threshold 0.02) the gate relaxes, admitting more options.

The paper's pitch is that this decouples truncation from temperature, so you can raise temperature for creativity without the tail leaking in — and reports improvements in quality and diversity on GPQA, GSM8K, and AlpacaEval Creative Writing across Mistral and Llama-3 families (1B–123B), with human preference for min-p at high temperature. Min-p has been adopted by Hugging Face Transformers, vLLM, and others.

⚠️ Contested. A 2025 critical re-analysis, Min-p, Max Exaggeration (arXiv:2506.13681), disputes these claims: it reports that the original human evaluations "contained omitted data, incorrect statistical testing, and inaccurate qualitative descriptions," that a controlled hyperparameter sweep does not show min-p beating baselines, and that some publicized adoption statistics were unsubstantiated and later removed by the original authors. The mechanism (confidence- scaled truncation) is sound and widely shipped; treat the superiority claims as open and contested, not settled, and tune on your own task rather than trusting the headline benchmark deltas.

4. Contrastive search — penalizing degeneration directly

Su et al. (A Contrastive Framework for Neural Text Generation, arXiv:2202.06417, NeurIPS 2022) attack repetition from a different angle. Rather than truncating the distribution, contrastive search picks the next token by balancing two terms: the model's confidence (probability) minus a degeneration penalty equal to the candidate's maximum representational similarity to tokens already generated. A token that the model likes but that looks too much like the recent context gets penalized, which directly discourages repetitive loops. Their paper pairs this with a contrastive training objective (SimCTG) that spreads token representations apart (reducing "anisotropy") so the similarity penalty is meaningful. Contrastive search is supported in Hugging Face generate. It is more expensive per step (it scores a candidate set against context) and its quality depends on a well-calibrated representation space.

5. The determinism problem — why temperature=0 still isn't reproducible

A near-universal surprise: set temperature=0, send the same prompt twice to a production endpoint, and you can get different outputs. The common folk explanation ("floating-point non-associativity / GPU race conditions") is, per Thinking Machines' Defeating Nondeterminism in LLM Inference (2025), the wrong root cause. Their finding: the real culprit is batch-size variance. Server load changes the batch your request lands in, and many kernels (matmul, RMSNorm, attention) produce subtly different numerics for the same token depending on the overall batch size and the position within it — they are not batch-invariant. Even greedy argmax can then tip to a different token on a near-tie, and autoregression amplifies the divergence. The fix is engineering batch-invariant kernels so a request's numerics don't depend on what else is in the batch; their accompanying batch_invariant_ops code demonstrates deterministic Qwen3-8B under vLLM, and SGLang/LMSYS later built on it for reproducible inference and RL training. The lesson for this article: the sampler is not your only source of (non)determinism — the serving stack is, and "set temperature to zero" is necessary but far from sufficient.

Key ideas & tradeoffs

• Truncate, then randomize. Every robust open-ended strategy first deletes the unreliable tail (top-k count, top-p mass, or min-p confidence-scaled threshold) and then applies temperature over the survivors. Temperature without truncation fattens the tail you don't want; truncation without temperature is just a narrower greedy.
• Fixed-count vs. dynamic truncation. Top-k's fixed k is wrong in both confidence regimes; top-p (mass) and min-p (confidence-relative) adapt the cut to how peaked the distribution is. The dynamic methods are why static top-k is now rarely used alone.
• Maximization is for closed-ended tasks. Greedy/beam shine where one right answer exists (translation, extraction, short factual QA) and degenerate on open-ended generation — the single most counterintuitive result in the field (Holtzman et al.): higher sequence probability ≠ better text.
• Task determines temperature, not the model. Code/math/tool-args → cold (near-greedy) for stability and parseability; brainstorming/persona/fiction → warm. A single global default is always a compromise between these.
• Sampling and the rest of the stack are coupled. Speculative decoding ([[speculative-decoding]]) only stays lossless if it samples from the target model's exact distribution; structured outputs want cold sampling so schemas hold; caching ([[semantic-caching-for-llms]]) of sampled output freezes one random draw forever.

Honest caveats & open questions

• "Best sampler" claims rarely transfer. Nucleus beat beam on Holtzman's evaluations; min-p's wins are contested (arXiv:2506.13681). What's best depends on model, task, temperature, and how you measure — there is no universal winner. Benchmark on your traffic with your judge.
• Quality vs. diversity is a genuine frontier, not a free lunch. Truncating harder buys coherence at the cost of variety and vice-versa; methods that claim to improve both simultaneously deserve the scrutiny min-p received. Read such claims as "moved the frontier on this benchmark," not "broke the tradeoff."
• Evaluation of open-ended text is hard and partly subjective. Human-eval design flaws are exactly what the min-p critique flagged; automatic metrics (repetition, MAUVE, diversity-n) each capture only a slice. Decoding research is unusually sensitive to evaluation methodology.
• Determinism is a serving-engineering problem, not a sampler flag. Even with a fixed seed and temperature=0, reproducibility requires batch-invariant kernels (Thinking Machines 2025); most hosted endpoints don't provide them, so don't assume greedy = reproducible across calls.
• Penalties and bans are blunt. repetition_penalty, presence_penalty, no_repeat_ngram, and logit bias are common in practice but crude — they can suppress legitimately-repeated tokens (a variable name, a refrain) and their good values are workload-specific and largely folklore.

How it connects to OpenAlice

OpenAlice's agent core is a hardened tool-loop ([[agentic-loops]]) that streams provider output token-by-token, and its behavior depends on the sampling config sent to the provider as much as on the prompt:

• Per-mode temperature is a personality + reliability lever. Alice's documented mode axes (Companion vs. Worker; six personality moods) are, mechanically, partly a sampling decision: Worker/agentic turns that emit tool calls want cold, near-greedy decoding so the JSON args parse and the loop doesn't stall on malformed payloads ([[tool-use-function-calling]]), while Companion/creative turns tolerate a warmer distribution. The same model, opposite knobs, by task.
• Determinism discipline = evals + caching. The house "always verify with the real build/test" and reproducible-eval rules collide directly with the determinism problem: a fixed-seed greedy run is not guaranteed bit-stable across provider calls, so OpenAlice's evals must tolerate small output drift or pin a deterministic-inference path — exactly the gap Thinking Machines' batch-invariant work closes. Cached sampled answers ([[semantic-caching-for-llms]]) also freeze one draw, which is fine for tool results and risky for creative replies.
• Sampling is upstream of every other decoding layer. Constrained decoding ([[constrained-decoding-structured-output]]) masks the legal set; sampling picks within it; speculative decoding ([[speculative-decoding]]) must reproduce that same pick to stay lossless. OpenAlice inherits all three through its Codex/OpenAI- family provider, so a temperature chosen for "warmth" silently widens the space the grammar mask and the tool schema then have to contain.

See also

[[constrained-decoding-structured-output]] · [[speculative-decoding]] · [[tool-use-function-calling]] · [[agentic-loops]] · [[semantic-caching-for-llms]] · [[llm-inference-internals]]