DECODING AND SAMPLING

The simplest rule: take argmax(logits). Deterministic, free, and reproducible.

It has two distinct problems, and they are worth separating.

It is locally greedy. The most likely first token may lead into a region of low-probability continuations. The sequence "The" → "cat" might have higher joint probability than "A" → "cat", but if P(A) > P(The) greedy commits to "A" and never looks back. This is the standard search critique, and it motivates beam search.

It produces degenerate text. This one is more surprising and more important. Greedy output on open-ended prompts falls into loops — repeating a phrase, then a sentence, then a paragraph, indefinitely. Not occasionally: reliably. Holtzman et al. documented this carefully in 2019, and the mechanism is a positive feedback loop. A repeated phrase raises the model's estimate that it is in a repetitive context, which raises the probability of repeating again.

The deep point is that high probability is not the objective. Human text is not the most likely text under a language model. Holtzman's Figure 2 is the memorable evidence: the per-token probability of real human writing fluctuates wildly, dipping low constantly, while beam-search output sits at a consistently high probability. Real language is full of surprise — that is what makes it informative. A decoder that maximizes likelihood systematically strips the surprise out.

Where greedy is still right:

• Reproducibility matters — evaluation, regression tests, debugging.
• The output space is narrow — extraction, classification, format conversion. If there is one correct answer, sampling can only hurt.
• Speculative decoding verification — the target model's greedy choice defines acceptance.

Where it is wrong: anything open-ended. Creative writing, dialogue, brainstorming, and — perhaps counterintuitively — long chains of reasoning, where a little diversity helps escape a bad line of argument.

Beam search keeps the k highest-probability partial sequences at each step rather than one. Expand all k, score all k × V continuations by cumulative log-probability, keep the best k. It is a heuristic search for the maximum-probability sequence, and it works — it reliably finds sequences with higher joint probability than greedy.

It dominated neural machine translation for years, and still does. So why is it absent from essentially every chat model's default configuration?

Because it succeeds at the wrong objective. Higher probability means blander, more generic, more repetitive text. Beam search finds the safest possible continuation, which for open-ended generation is exactly the failure mode. The classic symptom: raise the beam width and output quality gets worse, monotonically. That is the signature of a search that is working correctly on a bad objective.

The task distinction is sharp and worth internalizing:

There is also a systems argument, and it is nearly as decisive. Beam search multiplies your memory and compute by k: you maintain k KV caches per request and run k sequences through every forward pass. From Module 2, KV cache is what caps batch size — so beam width 4 cuts your concurrency by roughly 4×. You pay 4× the cost for output most users rate as worse. In a throughput-driven serving business that argument alone ends the discussion.

(Beam search does have one elegant systems property: the beams share a prefix, so with copy-on-write block sharing under PagedAttention the memory cost is far below 4×. vLLM implements this. It softens the cost argument but not the quality one.)

Temperature is a single division applied to the logits before the softmax:

p_i = exp(z_i / T) / sum_j exp(z_j / T)

• T = 1 — the model's own distribution, unmodified.
• T < 1 — sharpens. Gaps between logits are magnified, high-probability tokens get more probability. As T → 0 it converges to greedy.
• T > 1 — flattens. Gaps shrink, the tail gets more mass. As T → ∞ it converges to uniform over the whole vocabulary.

Work a concrete example. Logits [4.0, 3.0, 1.0, 0.0]:

Two things to notice. At T = 0.5 the top token has 87% of the mass and the fourth is effectively unreachable. At T = 2.0 the fourth token — which the model gave 1.2% — now has 6.2%, a 5× increase in the junk.

That is the failure mode at high temperature, and it is why temperature alone is a poor diversity knob. A 128,256-token vocabulary has a very long tail. Even if each tail token has tiny probability, there are 128,000 of them, and flattening the distribution hands them collectively a large share. Sample from that often enough and you get a token that derails the sequence — and because generation is autoregressive, one bad token poisons everything after it.

This is why temperature is almost always combined with a truncation method. Truncation removes the tail; temperature reshapes what remains.

Order of operations matters and is a real source of confusion between libraries. Most implementations (including Hugging Face and vLLM) apply temperature first, then truncate. If you truncate first and then apply temperature, the same nominal settings give different behaviour — because top-p computes its cutoff on the sharpened or flattened distribution rather than the original. When comparing sampling configurations across systems, check the order before concluding the models differ.

All three zero out part of the distribution and renormalize what is left. They differ in how they draw the line.

Top-k. Keep the k highest-probability tokens. Simple, but k is fixed while the distribution is not. When the model is confident (one token at 95%), k = 50 drags in 49 tokens that should never be considered. When the model is genuinely uncertain across 500 plausible tokens, k = 50 cuts off legitimate options.

Top-p (nucleus). Sort descending, accumulate probability, keep tokens until the cumulative sum reaches p. The number of candidates adapts to the shape of the distribution:

confident:  [0.95, 0.03, 0.01, ...]  ->  p=0.9 keeps 1 token
uncertain:  [0.08, 0.07, 0.07, ...]  ->  p=0.9 keeps ~30 tokens

This is the Holtzman et al. contribution and it was a genuine advance. But it has a known flaw: at high temperature the distribution flattens, so reaching cumulative p requires many more tokens, and top-p lets in the tail exactly when the tail is most dangerous. Temperature and top-p interact badly at the extremes.

Min-p. Keep every token whose probability is at least min_p × p_max, where p_max is the top token's probability. The threshold is relative to the model's confidence:

min_p = 0.1
confident:  p_max = 0.95  ->  threshold 0.095  ->  very few survive
uncertain:  p_max = 0.08  ->  threshold 0.008  ->  many survive

This is the behaviour you actually want, and it degrades gracefully under temperature: since the threshold scales with p_max, flattening the distribution does not automatically widen the candidate set the way it does for top-p. Min-p is the reason people can run temperature 1.5+ without the output falling apart, and it has become a common default in local-inference communities.

A rough guide to defaults, offered with the caveat that the right values are task- and model-specific and worth measuring rather than copying:

The cost of all of these is a sort over the vocabulary. A full sort of 128,256 logits per sequence per token is not free at batch 256 — production samplers use partial sorts (top-k selection) and fused kernels for exactly this reason.

Even with good sampling, models loop. The standard patches all modify logits based on what has already been generated.

Repetition penalty (Keskar et al., CTRL) divides the logit of any previously-seen token by r > 1. The implementation detail that catches people:

z_i = z_i / r   if z_i > 0
z_i = z_i * r   if z_i < 0

The sign check exists because dividing a negative logit would increase it. This asymmetry means the penalty's strength depends on the sign of the logit, which is a fairly arbitrary property.

Frequency penalty subtracts alpha × count(token) — scales with how often the token appeared. Presence penalty subtracts a flat beta if the token appeared at all. Both are additive in logit space, which is better behaved than division.

Now the failure modes, which are more serious than they are usually presented:

Function words are punished first. The most-repeated tokens in any English text are "the", "a", "of", "to", ",". A repetition penalty hits them hardest. Set r = 1.2 and the model starts dropping articles and prepositions — output becomes subtly telegraphic in a way that reads as "off" without an obvious cause.

Code and structured output break. Python repeats self, return, def, import, indentation tokens. JSON repeats {, }, ", :. Penalizing repetition in structured output means penalizing correctness. Repetition penalties should be off for code and off for constrained JSON. This is a common and avoidable production bug.

Long contexts poison the penalty. If the penalty applies over the whole context, then in a 32k-token conversation nearly every common token has appeared and is penalized. Good implementations apply it over a sliding window (the last n tokens); many do not, or do not expose the window.

It treats identity, not structure. The real problem is repeated phrases, and a token-level penalty cannot see phrases. It over-penalizes legitimate reuse and under-penalizes a loop built from varied tokens.

The honest summary: penalties are a blunt patch for a symptom whose real cause is the model's distribution. Prefer fixing the distribution — better truncation, min-p, a better prompt — and treat penalties as a last resort with narrow windows and small values (1.05–1.15 for repetition penalty, 0.1–0.5 for frequency). DRY and similar n-gram-aware samplers are attempts at the structural version of this idea.

If you need valid JSON, you can ask nicely, validate, and retry — or you can make invalid output unrepresentable.

The mechanism is a logit mask. At each step, given the tokens generated so far, compute which next tokens could still lead to a valid string. Set every other logit to -inf. Sample from what remains. The output is valid by construction, with no retries.

The machinery:

1. Express the target format as a regular expression or context-free grammar.
2. Compile it to a finite state machine (or a pushdown automaton for CFGs).
3. Precompute, for each FSM state, the set of allowed vocabulary tokens. This is the expensive step and the key insight of the Outlines paper — done ahead of time, it turns per-step constraint checking into an O(1) lookup instead of a scan over 128k tokens.
4. At generation time, track the state, look up the mask, apply, sample, advance.

The hard part is that the FSM is over characters but sampling is over tokens, and BPE tokens span multiple characters and do not align to grammar boundaries. A single token might be "},{" — valid in some JSON states and not others. Handling this token-boundary mismatch correctly is most of the implementation difficulty and the source of most bugs in naive versions.

Costs worth knowing before you turn it on:

• Compilation is not free. A complex grammar can take hundreds of milliseconds to compile. Cache compiled grammars by schema; do not compile per request.
• Masking is per-sequence work in the hot loop. At batch 256 with 128k vocabulary, applying distinct masks is real overhead. It is why structured output is a first-class engineering concern in SGLang and xgrammar rather than a wrapper.
• Constraints do not confer competence. Forcing schema-valid JSON guarantees the shape, not the content. A model that does not know the answer will emit a well-formed wrong one. There is also evidence that heavy constraint can degrade reasoning quality, presumably by pushing the model off its natural distribution — so for reasoning-heavy tasks, prefer letting the model think freely and constraining only a final extraction step.

Set temperature to 0, send the same prompt twice, get different completions. This surprises people, and the explanation has nothing to do with sampling.

Floating-point addition is not associative. In real arithmetic (a + b) + c = a + (b + c). In floating point it is not, because each addition rounds:

(1e10 + 1.0) - 1e10  =  0.0     in fp32
1e10 + (1.0 - 1e10)  =  1.0

A GPU matmul sums thousands of products in parallel and combines partial results in whatever order the kernel's parallel reduction dictates. That order depends on the thread and block configuration, which depends on the tensor shapes, which depend on the batch size and sequence lengths of everyone else in your batch.

So the chain is:

different batch composition
  -> different kernel/tile configuration selected
  -> different floating-point reduction order
  -> logits differ in the last few bits
  -> if the top two logits are close, argmax flips
  -> a different token
  -> a completely different continuation from there on

The divergence is usually rare per token but the consequences compound: one flipped token early changes everything after it.

Contributing factors, roughly in order of how often they bite:

1. Batch-dependent kernel selection. The big one. Your request is batched with different neighbours each time, so the matmul kernel and its reduction order change.
2. Atomics and non-deterministic reductions. Some kernels use atomicAdd, which completes in nondeterministic order by design.
3. Autotuning. Libraries pick algorithms by benchmarking at runtime; the winner can vary.
4. Mixed precision. bf16 has 8 mantissa bits. Ties and near-ties are common, so small perturbations flip argmax more often than you would guess.
5. MoE routing. In a sparse model, batch composition can change expert assignment and capacity-factor dropping, which is a much larger perturbation than a rounding difference.

Getting real determinism requires batch-invariant kernels — kernels whose reduction order does not depend on batch composition. This is achievable (Thinking Machines published a detailed treatment of batch-invariant kernels in 2025) but costs performance, because you give up the freedom to pick the fastest tiling for each shape.

The practical implications: do not build tests that assert exact token equality across runs; assert on semantic properties instead. Do not promise users bit-reproducible output unless you have specifically engineered for it. And when debugging a "flaky" model, check whether you are chasing a bug or chasing floating-point.