Choosing the Next Token

The decoder is not the model

There is a moment in every forward pass that gets almost no attention and deserves a great deal of it. The transformer has done its work. Attention has mixed the context, the MLPs have done their lookups, the final residual stream has been normalized and projected through the unembedding matrix, and what falls out is a single vector of real numbers, one per vocabulary entry. Call it z_t ∈ ℝ^|V|.

That vector is the entire contribution of the neural network to this timestep. It is not a token. It is not text. It is not even a probability. It is a list of unnormalized scores, and the model's job is over.

What happens next is a separate program, written by an engineer, running on the CPU or in a small kernel at the tail of the graph, and it makes a decision the network never made: which one. That program is the decoder, and it is the subject of this article.

The reason to take this seriously is empirical. Holtzman and colleagues made the point unusually sharply in the paper that introduced nucleus sampling: decoding strategy alone can dramatically change the quality of generated text, even when every sample comes from exactly the same neural language model. Same weights, same prompt, same logits — output ranging from fluent and surprising to a sentence fragment repeated until the context window fills.

Here is the framing to hold for the rest of the article. Training gives you a conditional distribution. Decoding gives you a policy for acting on it. These are different objects with different failure modes, and almost every complaint of the form "the model is repetitive" or "the model is too random" or "the model won't emit valid JSON" is a statement about the second, not the first.

The practical loop is short enough to write in one line, and it has not changed in years:

What the network actually outputs

Start with the object itself. The final hidden state h_t ∈ ℝ^d is multiplied by the unembedding matrix W_U ∈ ℝ^|V|×d:

So a logit is a similarity score: how well does the direction the model has settled on line up with the direction that represents token i? Two consequences follow immediately, and both matter for decoding.

Logits live on an interval scale, not a ratio scale. Only differences carry meaning. Adding a constant c to every logit changes nothing downstream, because softmax is shift-invariant. A logit of 12.4 is meaningless on its own; a gap of 12.4 between two logits is a factor of e^12.4 ≈ 2.4 × 10⁵ in relative probability.

The logits are confined to a low-dimensional set. Since h_t lives in ℝ^d with d ≪ |V|, the logit vector always lies in the column space of W_U — a d-dimensional subspace of a |V|-dimensional space. This is the softmax bottleneck, and it returns in a serious way when we ask why truncation works at all.

Softmax, derived rather than assumed

The standard move is to write down

and move on. But it is worth knowing where the exponential comes from, because the answer explains temperature.

Suppose you want to convert scores into probabilities while satisfying two requirements. First, only differences should matter: shifting all scores by a constant must not change the answer. Second, the mapping should be as noncommittal as possible given the scores — you want the maximum-entropy distribution subject to the constraint that the expected score equals some target value. Solve that constrained optimization with a Lagrange multiplier β and the unique answer is the Boltzmann–Gibbs form p_i ∝ e^βz_i. Softmax is what you get when you refuse to inject any information beyond the scores themselves.

That Lagrange multiplier is not decoration. It is the inverse temperature, β = 1/T, and the entire temperature knob is a choice of how tightly to bind the distribution to the scores. Physicists have been turning this dial since Boltzmann; we are late to it.

Entropy: the one number to hold onto

If you take one quantity from this article, take this one. The Shannon entropy of the next-token distribution,

is the model's own statement about how much it does not know. It is not a confidence score bolted on afterwards; it is a direct readout of the shape of the distribution the network just produced.

The best intuition is the effective support size: 2^H in bits, which is exactly perplexity. If the entropy at this position is 0.1 bits, the model is effectively choosing among about 1.07 options — it has already decided. If the entropy is 5 bits, it is effectively choosing among 32 roughly equal options. If it is 11 bits, it is nearly uniform over a couple of thousand tokens and it genuinely has no idea.

Now the observation that organizes the rest of the article. Entropy is not constant across a sequence. It swings by an order of magnitude between adjacent positions. After import numpy as the model is essentially certain the next token is np; entropy near zero. After The most interesting thing about the model has thousands of live options; entropy high. After a closing brace in JSON, the grammar has already decided; entropy near zero again.

Once you see this, several decoding puzzles collapse into one puzzle. A truncation rule with a fixed cutoff has to work at both extremes: it must not strangle a legitimately high-entropy position down to one option, and it must not admit a long junk tail at a position where the model was already certain. Hewitt, Manning and Liang showed that top-p fails on exactly this axis — it can truncate high-probability words unnecessarily, and in their example a document beginning with "Donald" has everything but "Trump" cut away. That is not an implementation bug. It is what happens when you apply a fixed mass threshold to a distribution whose entropy moves.

Temperature

Temperature rescales the logits before the softmax:

Two limits do most of the explanatory work, and both are worth deriving rather than memorizing.

The cold limit

Let m = argmax_i z_i and assume it is unique. Factor out the top logit:

Every numerator except the top one has z_i − z_m < 0, so as T → 0⁺ each of those terms goes to e^−∞ = 0 while the denominator goes to 1. Therefore p_m → 1 and everything else → 0. Sampling from a point mass is the same thing as taking the argmax, which is why temperature=0 is implemented as greedy decoding rather than by literally dividing by zero.

The rate matters as much as the limit. For the runner-up with gap Δ = z_m − z₂, the odds ratio p₂/p_m = e^−Δ/T collapses exponentially in 1/T. Halving the temperature squares the odds ratio. This is why the interesting behavioural range is roughly T ∈ [0.3, 1.5], and why T = 0.1 is nearly indistinguishable from T = 0.

The hot limit

As T → ∞, every z_i/T → 0, so every numerator → 1 and p_i → 1/|V|. Uniform. Note what that means concretely: at high enough temperature the model's opinion is erased and you are sampling uniformly from a vocabulary that is mostly byte fragments and rare subwords. The output does not become creative; it becomes noise. This is the most under-appreciated fact about the temperature slider.

Between the limits, temperature acts monotonically on entropy. A short calculation gives

So temperature is precisely an entropy dial, and the sensitivity is proportional to the variance of the logits. The same temperature change has a much larger effect on a spread-out distribution than on a peaked one — which is another way of saying that a single global temperature does very different things at different positions in the same sequence.

The mistake temperature invites

Because temperature is a single global scalar, it treats the tail and the head identically. Raising T to get more variety at high-entropy positions also raises the probability of genuinely absurd tokens at low-entropy positions, where the model had good reason to be certain. You cannot buy diversity where you want it without buying incoherence where you don't.

That tension is the entire motivation for the truncation family. Nguyen and colleagues put it directly in the min-p paper: popular methods like top-p struggle to balance quality and diversity, especially at higher temperatures, where they tip into incoherent or repetitive output. The fix in every case has the same shape — decide which tokens are eligible first, then let temperature spread mass within that set.

Greedy decoding and the myopia problem

The simplest decoder takes the mode at every step:

It is deterministic, costs nothing, and is wrong for a reason that has nothing to do with implementation. It answers the wrong question.

What you usually want is the most likely sequence:

Greedy decoding maximizes each term of that sum in isolation, in order, with no ability to revise. There is no reason for the sequence of locally optimal choices to be the globally optimal sequence, and it is easy to construct cases where it is not.

Take a two-step example. Suppose at step one the model gives P(A) = 0.6 and P(B) = 0.4. Greedy takes A. But suppose the continuations differ sharply in how committed they are:

Greedy commits to A because 0.6 > 0.4, and then discovers that A leads into a region where the model is uncertain. B was worse locally and much better globally. This is not a contrived pathology; it is the generic situation whenever a token opens a broad set of continuations and a slightly less likely token opens a narrow, confident one. Function words that admit many completions beat content words that admit few, locally, and lose globally.

The obvious response is to search harder. That response has an interesting history, and it does not end where you expect.

Beam search

Beam search keeps k partial hypotheses alive instead of one. At each step it expands all k beams by every vocabulary token, scores the k·|V| candidates by accumulated log-probability, and keeps the best k. It is a bounded-width breadth-first search over the same objective greedy approximates, and with k = 1 it reduces to greedy exactly.

The length bias, and where it comes from

Every additional token multiplies the sequence probability by a number strictly less than one, so log-probability is strictly decreasing in length. Beam search, ranking by raw cumulative log-probability, therefore has a structural preference for short outputs. It is not a heuristic failure; it is arithmetic.

The standard patch is length normalization — divide by length, or by a smoothed power of length in the form popularized by Google's NMT system:

And here is where the story gets genuinely strange. Stahlberg and Byrne built an exact search procedure for a Transformer translation model and used it to find the true global optimum for an entire WMT test set. Beam search almost never found it — even at beam width 100. That would be a damning result for beam search, except for what the exact optimum turned out to be: for more than half the sentences, the model's globally best-scoring output was the empty string. Longer sentences were worse; the global best was empty for nearly every sentence over about forty tokens.

Meister, Vieira and Cotterell asked the natural follow-up — if beam search is the answer, what was the question? — and gave an answer with real content. They frame beam search as the exact solution to a different objective, and identify its hidden inductive bias as uniform information density: a preference for outputs that spread surprisal evenly across the sequence rather than concentrating it. That property comes from psycholinguistics, where it describes how humans actually distribute information when they speak. Beam search accidentally implements a cognitively motivated regularizer, and that, not mode-seeking, is why it produces good translations.

Diverse beams, and the EOS problem

Standard beam search produces k outputs that typically differ in one or two tokens near the end, because they all descend from the same early prefix. Diverse beam search partitions the beams into groups and adds a dissimilarity penalty between groups at each step, so the groups are pushed apart rather than crowding the same mode.

The end-of-sequence token needs its own handling. When a beam emits EOS it is complete and cannot be extended, so implementations move it to a finished set and either shrink the live beam or backfill from the next-best candidate. Because completed hypotheses are scored under length normalization while live ones are still growing, the stopping rule interacts with the ranking rule, which is why "why did the model stop early" bugs are so often a beam-search bookkeeping issue rather than a model issue.

Why beam search fits translation and not chat

The distinction is about how much of the answer the input determines. Translation, summarization and speech recognition are low-entropy conditional tasks: given the source, there is a small set of adequate outputs, and finding a high-probability member of that set is exactly the goal. Beam search's mode-seeking bias and its uniform-information-density bias both help.

Open-ended generation is different. There is no single right continuation of "write me a story about a lighthouse." The high-probability region of the distribution is not the good region — it is the bland region, because blandness is what many contexts have in common. Holtzman and colleagues showed that maximization-based decoding in this regime produces text that is dull, sometimes incoherent, and prone to falling into repetitive loops. Search harder and you get there faster.

Why sample at all?

Once you accept that the mode is not what you want, sampling is the obvious alternative: draw y_t ∼ p(· | x, y_<t). This is unbiased in a strong sense — sample long enough and your generated text matches the model's distribution exactly.

Which is also the problem. The model's distribution has a very long tail, and matching it exactly means occasionally emitting tokens from the part of the tail the model has no real opinion about.

The arithmetic of the tail

Consider a vocabulary of 128,000 tokens. Suppose the top few hundred hold 0.98 of the mass and the remaining ~127,700 tokens share 0.02 — an average of about 1.6 × 10^-7 each. Any individual tail token is negligible. But the tail as a set has probability 0.02, so over a 500-token generation you expect roughly ten draws from it. Ten times in one paragraph, the decoder emits a token the model assigned essentially arbitrary probability to.

Worse, the damage is not local. Autoregressive generation conditions on its own output. One incoherent token becomes part of the prefix, and the model — trained only on coherent text — is now conditioning on a context it has never seen. Its distribution at the next step is out of distribution, which makes another bad draw more likely. Errors compound multiplicatively rather than averaging out.

Degeneration in the other direction

The mirror failure is repetition, and it has a specific mechanism worth naming. Once a phrase appears in the context, the model's probability of producing that phrase again increases. Attention has an easy job: the pattern is right there. Each repetition raises the probability of the next repetition, and the loop becomes an attractor. Under greedy or beam decoding there is no mechanism to escape, because escaping requires taking a lower-probability token and maximization never does that.

So pure maximization gives you loops and pure sampling gives you noise. Holtzman and colleagues' resolution was to change the support rather than the shape: sample, but only from the part of the distribution the model actually has an opinion about. Nucleus sampling truncates the unreliable tail and samples from the dynamic nucleus that holds the vast majority of the mass. That single move — restricting the candidate set before sampling — is the design pattern that the next eight years of samplers all follow.

It is worth separating two claims that often travel together. The empirical claim is that truncated sampling produces better text than either extreme; this is well established. The mechanistic claim is that the tail is unreliable because the model's probability there is wrong, not merely small. That claim needed a theory, and it got one — later, and from a different direction. We come back to it in a moment.

There is also a training-side response worth knowing about, because it reframes the whole discussion. Welleck and colleagues argued that the likelihood objective itself is at fault: maximum-likelihood training assigns too much probability to sequences containing repeats and frequent words relative to human text, and their unlikelihood objective directly pushes those sequences down during training. On that view, truncation samplers are treating a symptom of the loss function. The question of whether degeneration is fundamentally a decoding problem or fundamentally a training problem is not settled, and both literatures are still active.

A taxonomy of truncation

The samplers are usually presented chronologically, which makes them look like a pile of unrelated tricks. They are not. Every one of them is the same algorithm:

So organize them by that rule. There are exactly four kinds of answer to "which tokens are eligible," and knowing which kind you are using tells you immediately how the sampler will behave when the entropy moves.

Rank rules: top-k

Top-k, introduced for story generation by Fan, Lewis and Dauphin, keeps a fixed number of candidates. Its virtue is that it is trivially cheap and bounded. Its defect follows directly from the entropy discussion: a fixed k is simultaneously too permissive at low entropy and too restrictive at high entropy. If the model is 99.7% sure of the next token, k = 50 admits 49 tokens it does not believe in. If the model is genuinely uncertain across 400 plausible continuations, k = 50 throws away most of the legitimate distribution.

Mass rules: top-p

Nucleus sampling sorts by probability and takes the smallest prefix whose cumulative mass reaches p. The candidate set now has variable size, which is the improvement over top-k: at a confident position the nucleus is tiny, at an uncertain position it is large. This is why top-p became the default almost immediately.

Its failure mode is the one from the entropy section, and it is subtler than "sometimes wrong size." Because the rule is defined on cumulative mass, a single dominant token can consume the entire budget. If p₁ = 0.93 and p = 0.9, the nucleus is exactly {token 1} — every alternative is discarded even where several are genuinely reasonable. Hewitt and colleagues' "Donald → Trump" example is precisely this, and it means top-p can be more deterministic than greedy would suggest at exactly the positions where a small amount of variation would be harmless.

Absolute rules: ε-sampling

Set a floor and drop everything below it: C = { i : p_i > ε }. This directly encodes the intuition that below some probability the model's estimate is noise rather than belief. It fixes top-p's low-entropy problem — a dominant token no longer swallows the budget, because the rule does not have a budget. But it introduces the opposite failure: at a genuinely high-entropy position where a thousand tokens each hold 0.0005, a floor of ε = 0.001 removes the entire distribution.

Relative rules: min-p

Min-p makes the floor proportional to the model's own confidence: keep tokens with p_i ≥ p_base · max_j p_j. When the model is certain, the top probability is large, so the threshold is high and the set is small. When the model is uncertain, the top probability is small, the threshold drops with it, and the set is wide. It is a one-line change to ε-sampling that removes its main defect, and it is cheap — one max, one comparison — which is why it spread quickly through open-source inference stacks.

Min-p's reception is also a useful lesson in reading the literature. The original paper reported gains on benchmarks and in human evaluation and was an ICLR 2025 oral. A subsequent reanalysis re-examined all four of the paper's lines of evidence and reached different conclusions, reporting problems with the human evaluation and finding that min-p did not outperform baselines on quality or diversity once corrected. The sampler is genuinely useful and widely deployed; the claim that it dominates alternatives is contested. Both things are true at once, and the honest summary is that the rule is well-motivated while the magnitude of its advantage is unresolved.

Entropy rules: η-sampling

η-sampling is min-p's idea taken to its logical conclusion, with the adaptivity driven by entropy directly rather than by top-1 probability as a proxy. Hewitt, Manning and Liang define

The min is doing real work. The first argument enforces an absolute floor so that no genuinely negligible token survives. The second relaxes that floor exponentially as entropy rises, so a legitimately uncertain position is not over-truncated. Their reported result is that this breaks out of repetition better than top-p and produces more plausible long documents in human evaluation.

Information rules: typical sampling

Typical sampling is the one with a genuinely different justification, and it is worth slowing down for.

Meister, Pimentel, Wiher and Cotterell start from an information-theoretic view of language production. The information content of a token is −log p(y_t | y_<t), and the conditional entropy H(p) is the expected information content at that position. Their empirical observation is that human text sits close to that expectation: measured on reference text, the per-token deviation between information content and conditional entropy is sharply peaked around zero. Model-generated text under standard decoding schemes is not — it comes out systematically too predictable, carrying less information than expected.

That suggests a different target. Do not select high-probability tokens; select tokens whose surprisal is close to average:

This connects directly back to beam search. Meister and colleagues had earlier identified uniform information density as beam search's hidden bias; typical sampling makes that criterion explicit and applies it per-token instead of accidentally. The two results are the same idea approached from opposite ends — one reverse-engineering a search algorithm, the other designing a sampler from the psycholinguistics up.

There is also an earlier relative, Mirostat, which controls generated perplexity toward a target value with a feedback loop. Typical sampling differs in not requiring you to specify the target: it uses the model's own conditional entropy at each step, which makes it far less sensitive to hyperparameter choice.

Why truncation works at all

Everything so far has been engineering. Truncation obviously helps; the samplers differ in how they choose the cutoff. But why should discarding low-probability tokens improve anything? The model was trained by maximum likelihood on real text. Its tail is its honest estimate. Cutting it away is deliberately sampling from a distribution that is not the model's.

Two lines of theory answer this, and they are complementary.

The desmoothing argument

Hewitt, Manning and Liang propose thinking of the trained model not as an estimate of the true distribution but as a mixture:

Why would a smoothing component be there? Because cross-entropy training punishes zeros catastrophically. If the model assigns exactly zero to a token that appears in the data, the loss is infinite. Gradient descent under that loss will never drive any probability to zero — it will always keep a floor of mass spread across the entire vocabulary as insurance. The model is structurally incapable of expressing "this token is impossible here," even when it is.

On this view, the true distribution over next tokens has limited support: at most positions, the great majority of the 128,000 tokens are genuinely impossible, not merely unlikely. The trained model cannot represent that. It smears a small amount of mass everywhere, and that smear is exactly the tail we have been cutting off.

This reframes the whole family. A truncation sampler is not "throwing away part of the model's belief." It is a support estimator: an attempt to recover which tokens the true distribution actually puts mass on, given a model that was structurally prevented from telling you. Every rule in the last section is a different guess at where the support boundary lies, and the reason the entropy-adaptive rules work better is that the support boundary moves with entropy.

The softmax-bottleneck argument

Finlayson, Hewitt, Koller, Swayamdipta and Sabharwal push this further and get something sharper. They prove that threshold-based truncation methods — the family that discards tokens below some probability — guarantee that every sampled token has nonzero true probability. That is a real theorem about why the most common kind of truncation is safe, and it explains the empirical success of the whole family in one line.

But they also show it is a coarse guarantee. A threshold necessarily discards some tokens that do have nonzero true probability, because a threshold cannot distinguish "small because the true probability is small" from "small because the smoothing put it there."

So they look for a finer instrument, and find it in the softmax bottleneck from §2. Because the logit vector must lie in the d-dimensional column space of the unembedding matrix, not every point on the probability simplex is reachable. The set of achievable distributions is a low-dimensional manifold, and the observed logits are a projection of the true ones onto it. That constraint is informative: given the observed logits and the known geometry, you can prove for certain tokens that their true probability must be nonzero, without appealing to a threshold at all. Their basis-aware threshold sampler is an experimental algorithm built on that proof.

The result is intellectually satisfying because it turns a known model error — the bottleneck, usually cited as a limitation — into a source of information about what the model would have said if it could.

Two honest caveats. First, the mixture framing is a modelling assumption, not something measured — nobody has isolated p_true and p_smooth in a real network. Second, the basis-aware results are presented by their authors as pilot studies, and the practical samplers in production are still the heuristic ones. The theory explains why the heuristics work; it has not yet replaced them.

Degeneration controls

Truncation decides which tokens are eligible. A separate family of interventions changes how much each eligible token is worth, based on what has already been generated. These are the penalties, and they are the least principled part of the stack — which does not stop them from being essential.

The four standard forms

Repetition penalty, introduced with CTRL, divides the logit of any previously-generated token by a factor θ > 1. There is a sign trap here that has bitten most implementations at some point: dividing a negative logit by θ > 1 moves it up toward zero, which increases the token's probability — the opposite of the intent. Correct implementations branch:

That discomfort is warranted. Because logits are shift-invariant, a multiplicative penalty on them is not shift-invariant: adding a constant to all logits before applying repetition penalty changes the result. The operation depends on where the implementation happens to have put the zero point. It works in practice because the zero point of a trained unembedding is stable in practice, not because anything guarantees it.

Frequency penalty is additive and better behaved:

Presence penalty is the same idea with a step function instead of a count:

No-repeat n-gram blocking is not a penalty at all but a hard mask: any token that would complete an n-gram already present in the context has its logit set to −∞. It is the bluntest instrument in the drawer and the most reliable at stopping literal loops.

Bad-token masks and logit bias round out the family — a fixed set of token IDs forced to −∞, or nudged by a constant. This is how "never emit this string" and "prefer this vocabulary" are usually implemented.

What penalties actually are

This is the part that matters, and it is easy to lose.

Three consequences follow. First, the log-probabilities you get back from an API may be computed before or after penalties depending on the implementation, and the two are not the same number — this matters if you are using logprobs for scoring, ranking or evaluation. Second, penalties break the assumptions of anything downstream that expects a proper conditional distribution, including some importance-weighting and RL setups. Third, and most practically: penalties cannot distinguish good repetition from bad.

Real text repeats constantly and legitimately. Code repeats indentation, variable names and closing brackets. Lists repeat structure. Prose repeats the subject of the paragraph. A frequency penalty strong enough to break a degenerate loop is also strong enough to make a model rename a variable halfway through a function, or refuse to use the word "the" enough times. Anyone who has cranked frequency penalty to fix repetition and gotten increasingly baroque synonym substitution has met this directly.

This is why the sampler-level fixes and the penalty-level fixes coexist rather than one replacing the other. Truncation prevents the tail from being sampled; penalties fight the self-reinforcement dynamic in the head. They address different halves of the degeneration problem. And as noted earlier, Welleck and colleagues' unlikelihood training argues both are downstream patches for something the loss function did — a position that has not been refuted so much as left open while the field moved on.

Constrained decoding

Sometimes the output must satisfy a hard specification: valid JSON matching a schema, a syntactically correct SQL query, a function call with the right argument names, a choice from a fixed enum. Prompting for this works most of the time, which is exactly the problem — most of the time is not a guarantee, and a parser downstream does not accept "most of the time."

Constrained decoding makes it a guarantee by making violations impossible rather than unlikely. The mechanism is one line:

The whole engineering problem is computing "the current state" and "permitted" fast enough to keep up with the GPU.

The machinery

The natural formalism is an automaton. Willard and Louf's key move was to reformulate constrained generation as transitions between states of a finite-state machine, which lets you precompute, for each FSM state, the set of vocabulary tokens that are acceptable from it. That precomputation is what makes the approach practical: at generation time you look up a mask instead of testing the entire vocabulary against a regex.

The hierarchy runs from cheap to expressive:

Context-free grammars are where it gets expensive. Executing a CFG means maintaining stack states and, in the naive implementation, checking every token in the vocabulary against them at every step. XGrammar's contribution is to split the vocabulary into context-independent tokens whose validity can be prechecked once and context-dependent tokens that must be interpreted at runtime, plus a persistent stack and overlapping of the grammar computation with GPU execution — enough to get structured generation to near-zero overhead in a serving loop.

The subword complication

Grammars are defined over characters. Models emit tokens, which are multi-character strings chosen by a tokenizer that knows nothing about your grammar. The mismatch causes real problems.

A single token may span a grammar boundary — one token might contain the closing quote of a string, a comma, and the opening quote of the next key. The automaton has to be able to advance several character-level states from one token, and the mask has to be built over token strings, not characters. This is why the FSM-to-vocabulary index is built once at compile time rather than derived at runtime.

Then there is token healing. If the prompt ends mid-token — say the constraint forces the output to begin with {"na — the tokenizer would never have produced that boundary naturally, and forcing it puts the model in a state it never saw during training. The usual fix is to back up one token and re-generate with a prefix constraint, so the model can choose its own tokenization of the forced text.

The part that is usually left out

Masking and renormalizing at each step does not sample from the model conditioned on the constraint. Those are different distributions, and the difference is not small.

What you want is p(y | y ∈ L) for a language L. What masking gives you is a locally greedy approximation: at each step it renormalizes over tokens that are permitted right now, with no knowledge of whether that token leads to a prefix from which the constraint can still be satisfied cheaply. The mask cannot see the future. It can steer generation into a region where every remaining continuation is one the model finds unlikely, and then force it through anyway.

This is a genuine distributional distortion, not a rounding error, and it is the theoretical basis for the observation that structured output can hurt task performance. Tam and colleagues evaluated exactly this and found a significant decline in reasoning ability under format restrictions, with stricter constraints producing greater degradation on reasoning tasks — though on classification tasks the same constraints were competitive or better, plausibly because restricting the answer space removes selection errors. The effect is real and it is task-dependent.

The principled alternative is to treat constrained generation as posterior inference rather than as masking: use sequential Monte Carlo, maintain a population of partial sequences with importance weights, and resample. That gets you closer to the true conditional distribution at the cost of running many partial sequences. It is the correct thing to do and it is not what most production systems do, for the obvious reason.

Contrastive generation

Every method so far uses one distribution. The contrastive family uses two, and scores tokens by the difference:

The intuition is a kind of subtraction of the obvious. A large model and a small model agree on the parts of language that are easy — function words, common continuations, surface fluency, and also the failure modes both share, like falling into repetition. Where they differ is where the large model's extra capacity is actually doing something. Contrastive scoring isolates that difference and decodes from it.

An analogy that holds up: the amateur is a control condition. In an experiment you subtract the control to remove effects that are not attributable to your intervention. Here you subtract a weaker model to remove behaviour that is not attributable to scale.

Contrastive decoding

Li and colleagues formalized this as an optimization problem over sequences, and added a component that turns out to be essential: a plausibility constraint. Without it, the log-ratio is maximized by tokens the expert also considers implausible — a token with expert probability 10^-8 and amateur probability 10^-12 has a wonderful ratio and is complete nonsense. So the candidate set is first restricted to tokens whose expert probability is at least α times the expert's maximum, and only then is the difference maximized.

That constraint should look familiar. It is the min-p rule — a threshold proportional to the top token's probability — arrived at independently, two years earlier, for a different reason. This is a recurring shape in the decoding literature: the same handful of geometric ideas keep reappearing under different names because the underlying problem keeps having the same structure.

Contrastive decoding was introduced for open-ended generation quality, and subsequent work reported gains on reasoning benchmarks as well.

Contrastive search

Confusingly similar name, genuinely different method. Su and colleagues' contrastive search does not use a second model. It takes the top-k candidates from the model and re-ranks them by a combination of the model's own confidence and a degeneration penalty measuring how similar the candidate's representation is to the representations of tokens already in the context. A token whose hidden state is nearly identical to something already generated gets penalized.

This attacks repetition in representation space rather than in token space, which is a meaningfully different mechanism from an n-gram block: it can catch semantic repetition that is not literal repetition. The two "contrastive" methods share a name and almost nothing else, and conflating them is a common error.

DoLa: contrasting layers instead of models

The amateur does not have to be a separate model. Chuang and colleagues' DoLa uses the same model's earlier layers as the amateur, projecting an intermediate layer's residual stream through the unembedding to get a premature distribution and contrasting it with the final layer's.

The motivation is an observation about where factual knowledge lives. In their illustrative example — asking for the capital of Washington State — the probability of the plausible-but-wrong "Seattle" is roughly flat across layers, while the probability of the correct "Olympia" rises through the upper layers. Contrasting a late layer against an early one amplifies exactly the tokens whose probability is still changing, which is a reasonable proxy for the tokens the model is genuinely retrieving rather than pattern-matching. They report improved truthfulness on multiple-choice and open-ended factuality benchmarks.

The practical appeal is obvious: no second model, no second set of weights, one forward pass with an extra head on an intermediate layer. The reported effect sizes vary by benchmark and there is at least one comparison in the literature where beam search outperforms it on a factuality metric, so this is a promising technique rather than a settled default.

Three things people confuse

A great deal of decoding confusion comes from putting unrelated mechanisms in the same mental bucket because they all live in the same config object. Here is the separation that fixes it.

Axis 1 — Distribution shaping

Temperature, repetition and frequency and presence penalties, grammar masks, logit bias, contrastive scoring. These all produce a different distribution from the one the network output. Two of them (masks, contrast) can change which token is most likely; all of them change relative probabilities.

Axis 2 — Token selection

Greedy, beam search, plain sampling, and the entire truncation family. Given a distribution, these choose an action. Truncation sits slightly awkwardly across the boundary — restricting to a candidate set and renormalizing is technically a reshaping — but it belongs here because its purpose is to define the choice, not to change beliefs.

Axis 3 — Decoding acceleration

This is the one that gets miscategorized, and the reason it matters is that a correct acceleration method changes nothing about the output distribution at all.

Speculative decoding is the canonical example. A small draft model proposes several tokens; the large target model verifies them all in a single forward pass, since scoring K tokens in parallel costs roughly what generating one costs in the memory-bound regime. Leviathan, Kalman and Matias introduced it explicitly as a way to sample from autoregressive models faster without any change to the outputs.

The mechanism that makes that guarantee true is a modified rejection sampling step, and it is elegant enough to write out. Let q be the draft distribution and p the target. For a drafted token x:

The result is that the marginal distribution of every emitted token is exactly p — the target model's distribution — even though most tokens were proposed by a much weaker model. You get the small model's speed and the large model's distribution, provably, not approximately.

The variants trade off where the draft comes from. Medusa attaches multiple decoding heads to the target model itself, so there is no separate draft model to run or serve. EAGLE drafts in feature space rather than token space, on the argument that the uncertainty that hurts drafting is better handled one level down. DeepSeek-V3's multi-token prediction objective trains the model to predict several future tokens during pretraining, which both improves the training signal and gives you draft heads for free at inference.

All of them share the same contract: verify against the target, correct on rejection, preserve the distribution. The systems-level story — how this interacts with batching, KV-cache management, and the memory-bandwidth wall that makes the whole thing profitable — belongs to a different article; The Mechanics of LLM Inference covers the inference loop, and The Serving Playbook covers what it costs in production.

Token-level vs trajectory-level

Everything in this article answers one question:

Modern reasoning systems answer a different one:

The shift is not cosmetic. Once a model produces a long chain of intermediate steps before its answer, the unit of decision stops being the token and starts being the whole path. You can sample many trajectories and take a majority vote on the final answer. You can score partial trajectories with a process reward model and prune the bad ones. You can search over trajectories with lookahead rather than committing left to right. You can let the model generate, evaluate its own output, and revise.

These are decoding algorithms in exactly the same sense as beam search — policies for turning a distribution into an output — but they operate at a granularity where the objects being compared are semantic rather than lexical. Token-level decoding asks whether this word is right. Trajectory-level decoding asks whether this approach is right.

The token-level machinery does not become irrelevant — it is the substrate every trajectory is drawn on, and the sampler you choose determines how diverse your trajectories are, which is the entire input to majority voting. A test-time-scaling method that samples 64 solutions and votes is only as good as the diversity of those 64 samples, and that diversity is a decoding-parameter question. Temperature and truncation reappear one level up, as controls on exploration rather than on wording.

That is where this article stops and the next one starts. The trajectory-level story — sample-and-vote, verifier-guided search, sequential revision, and how compute at inference trades against compute at training — is the subject of the companion piece on test-time scaling.

What to take away

Four things, if you keep nothing else.

The decoder is a program, not a property of the model. When behaviour is wrong, ask which of the four stages produced it before you reach for a different checkpoint.

Entropy is the organizing variable. It moves by an order of magnitude within a single sentence, and almost every sampler designed since 2022 is an attempt to make the cutoff track it.

Truncation is support estimation, not censorship. The tail is largely an artifact of a loss function that cannot tolerate zeros and an output layer that cannot reach the whole simplex. Removing it is undoing a distortion, not adding one.

Know which axis you are on. Shaping changes what is likely. Selection changes what is chosen. Acceleration changes neither. Most decoding bugs are a category error between these three.

References

Grouped by topic. Every entry links to its primary source.