Top-k keeps the k most likely tokens. Top-p keeps the smallest set whose probability sums past p. Both sort by probability and cut a prefix. Locally typical sampling asks a different question entirely: not how likely is this token, but how surprising is it — and it keeps the tokens whose information content sits closest to the distribution’s own entropy. That single change of coordinate produces a consequence no truncation method can: a token can be thrown away for being too probable. This piece derives the criterion, works it on a concrete distribution, and is honest about how strong the evidence for it actually is.
Selecting by information content, not by rank
Every sampler chooses a subset S of the vocabulary, zeroes the rest, and renormalizes; the families differ only in how they choose S. Top-k chooses by rank, top-p by cumulative mass, min-p by a floor relative to the peak — and all three questions are about probability.
Typical sampling changes the measured quantity. It works with the surprisal (information content) of a token, I(x) = -log p(x), in nats, and selects tokens whose surprisal is close to the distribution’s entropy H(p). The motivation is an old, stubborn observation: maximum-probability decoding — greedy, beam search — produces bland, looping text, and better models do not fix it. A model that assigns human reference text a perfectly reasonable probability will still assign a degenerate repetition loop a higher one. If ‘most probable’ is reliably the wrong target, the fix cannot be a better cut of the probability ranking. It has to be a different ranking.
The typical set, and why the mode is atypical
Information theory already has the concept. For i.i.d. draws from p, the asymptotic equipartition property says the per-symbol surprisal -(1/n) log p(x_1...x_n) → H(p). The typical set is the sequences within ε of that rate; it carries almost all the probability mass, yet the single most probable sequence is usually not in it.
A biased coin makes this concrete. With P(heads) = 0.9, H = 0.469 bits, so a length-100 sequence should carry about 46.9 bits. The all-heads sequence carries only 15.2 bits — it is the single most likely outcome, and its probability is 0.9^100 ≈ 2.7×10^-5. Meanwhile the outcomes with 85 to 95 heads account for 0.936 of the mass. The mode is a vanishing share of what you actually see. One caveat: the AEP assumes i.i.d. or at least stationary, ergodic sources, and a language model’s conditionals are neither — it motivates the per-step criterion by analogy, it does not prove it.
The uniform information density argument
The second leg of the motivation comes from psycholinguistics rather than coding theory. The uniform information density hypothesis holds that speakers spread information evenly across an utterance, staying near the channel’s capacity without spiking over it. The cited evidence is the shape of optional choices: ‘that’ is retained more often before a hard-to-predict continuation, predictable words are phonetically reduced, contractions cluster where surprisal is low.
If human text really is produced that way, it has roughly constant per-token surprisal near H — and the two failure modes of decoding are deviations from it in opposite directions. Greedy decoding stacks up tokens far below the target, which reads as vacuous and repetitive. Pure sampling occasionally emits a token eight or ten nats above it, which reads as a non-sequitur. A rule that pulls each step toward H attacks both at once. Note what this argument is: UID is a contested hypothesis about human production, and carrying it over into a decoding rule is an argument, not a result.
The criterion, and one exact fact about the mode
At step t the model gives a conditional distribution p over the vocabulary. Compute its entropy, score every token by how far its surprisal falls from that entropy, sort ascending by that deviation, and greedily admit tokens until the accumulated probability reaches a threshold τ. Renormalize over the survivors and sample.
H(p) = Σ_x p(x) · (-log p(x)) # mean surprisal, nats
d(x) = | -log p(x) - H(p) | # deviation from the target
S = smallest set of lowest-d tokens with Σ_(x in S) p(x) ≥ τ
p'(x) = p(x) / Σ_(y in S) p(y) for x in S, else 0The threshold τ ∈ (0,1) is the only knob; τ → 1 recovers pure sampling. Now the fact that gives the method its teeth. Since -log p_max is the minimum surprisal in the distribution and H(p) is the probability-weighted mean of those same surprisals, -log p_max ≤ H(p) always, with equality only when p is uniform. The most probable token is therefore always on the too-predictable side of the target; whether it survives depends only on whether some other token sits closer to H.
The target probability is one over the perplexity
The deviation d(x) is zero exactly when p(x) = e^-H(p). Call that p*. Since the perplexity of the conditional distribution is PPL = e^H(p), that gives p* = 1 / PPL. Typical sampling keeps the tokens whose probability is closest, in log space, to the reciprocal of the local perplexity.
Geometrically the criterion is a multiplicative window: because d(x) = |log p(x) - log p*|, admitting tokens with d(x) ≤ δ means admitting every token whose probability lies in the ratio band [p* · e^-δ, p* · e^δ]. It is centered on an interior point of the distribution and closes from both sides — unlike min-p, whose window is a one-sided floor anchored to p_max. A distribution with H = 1.619 nats has PPL ≈ 5.05 and therefore targets tokens near p = 0.198, however large the peak happens to be.
Worked example: which tokens survive
Take an eight-token distribution p = (0.45, 0.20, 0.12, 0.08, 0.06, 0.04, 0.03, 0.02) for tokens A through H, and compute the criterion column by column.
token p -log p |dev|
A 0.45 0.799 0.820
B 0.20 1.609 0.009
C 0.12 2.120 0.502
D 0.08 2.526 0.907
E 0.06 2.813 1.195
F 0.04 3.219 1.600
G 0.03 3.507 1.888
H 0.02 3.912 2.293
H(p) = 1.6187 nats = 2.335 bits, e^-H = 0.198The admission order is B, C, A, D, E, F, G, H — B first, because its probability 0.20 is almost exactly p* = 0.198, and the mode A only third. Set τ = 0.3: B contributes 0.20, C brings the total to 0.32, the threshold is met, and the kept set is S = {B, C}. A, with 45% of the mass, is discarded. Run top-p at 0.3 on the same vector and A alone already exceeds it: S = {A}. The two sets are disjoint. For balance, run both at 0.9: typical admits B, C, A, D, E for a mass of 0.91, and top-p admits A, B, C, D, E for 0.91 — the identical set. Divergence is a low-τ phenomenon.
Not a prefix, and how entropy governs the effect
The structural difference is exact. Top-k, top-p and min-p all keep a prefix of the probability-sorted order: none of them can discard a token while keeping a strictly less probable one. Typical sampling’s kept set is not a prefix — {B, C} retains two tokens and drops the more probable A. No amount of tuning k or p reproduces that.
How strongly it bites depends on entropy, and the dependence is benign. Take a confident step: p = (0.94, 0.03, 0.015, 0.008, 0.004, 0.003) gives H = 0.305 nats and p* = 0.738. The mode’s deviation is 0.243 against 3.20 for the runner-up, so the mode is admitted first and τ = 0.9 keeps it alone. Low-entropy steps stay effectively greedy; high-entropy steps get reshaped. One warning: published τ values are calibrated to vocabularies of tens of thousands of tokens, where a small mass budget still spans many candidates — do not read them against an eight-token illustration.
What the evidence actually shows
The method comes from Meister et al., Locally Typical Sampling, and the reported results are that it reduces repetition and degeneration relative to nucleus sampling at comparable diversity, with better human ratings on story generation and abstractive summarization. That is a real, carefully argued result, and it is worth holding loosely.
Decoder comparisons are among the least stable measurements in the field. The outcome is dominated by baseline tuning: a well-tuned top-p and a well-tuned typical sit far closer to each other than either does to a poorly tuned version of itself. Automatic metrics disagree and are themselves sensitive to the decoder under test. Human evaluations use small annotator pools on short continuations, with intervals wide enough to swallow the effect. The verdict is visible in adoption: typical_p ships in Hugging Face Transformers and llama.cpp, but it is rarely the first knob anyone reaches for. Treat typicality as a well-motivated alternative on suggestive evidence, not a settled improvement.
Cost, and the pitfall that quietly breaks it
The arithmetic is cheap. You already have log-probabilities from log_softmax, so the entropy is one extra O(V) reduction, the deviations are another O(V) pass, and the sort is O(V log V) — which top-p already pays. For V = 32000 that is a few hundred thousand operations against a forward pass measured in billions: unmeasurable next to the matmuls.
The pitfall is that typicality needs the full distribution. Fast stacks routinely pre-truncate to top-k=40 and then apply top-p to the survivors, which is harmless there (a prefix of a prefix). Do the same before typical sampling and you compute H over 40 tokens instead of 32000 — a smaller entropy, a larger p*, and a silently different criterion. Compute H first, truncate after. Two smaller notes: temperature moves H and therefore p*, so τ and temperature are not independent knobs; and keep a min_tokens_to_keep floor, since a peaked distribution with a small τ can collapse to a single token.
|-log p(x) - H(p)|, take the smallest set under that ordering reaching mass τ, renormalize, sample — equivalently, keep the probabilities closest in log space to 1/PPL. Because the mode’s surprisal is always at or below H, the mode can be dropped while less probable tokens survive: the kept set is not a prefix of the probability ranking, which is exactly what top-k, top-p and min-p can never do. It costs one extra O(V) pass, but H must be computed over the full distribution, before any truncation. The information-theoretic motivation is elegant; the empirical case is suggestive rather than settled.