Top-P (Nucleus) Sampling Math

The rule, stated precisely

Sort the step’s distribution p: [V] descending, writing p_(i) for the i-th largest, then stop at the first index whose running total reaches the budget:

p_(1) ≥ p_(2) ≥ ... ≥ p_(V)
C_n = Σ_{i=1..n} p_(i)
n* = min { n : C_n ≥ p }        S = { (1), ..., (n*) }

Three details hide in that min. First, the boundary token is always included: C_{n*−1} < p by minimality, so the n*-th token is the one that carries the sum across the line. Second, the nucleus is never empty — C_V = 1 ≥ p guarantees a solution, and n* = 1 whenever the top token alone clears p. Third, ties are resolved by the sort, not by the rule — invisible in fp32, but real on a quantized CPU model, where tail logits collapse onto identical values and two backends with different sort stability produce different nuclei.

Retained mass: the number you actually kept

p is a target, not a result. What you kept is the retained mass M = C_{n*}, and minimality pins it inside a window:

C_{n*−1} < p   and   M = C_{n*−1} + p_(n*)
⇒  p ≤ M < p + p_(n*)        and   p_(n*) ≤ 1/n*

So the overshoot is bounded by the boundary token’s own probability, which is itself at most 1/n*. Two regimes follow. On a wide nucleus (n* = 200) the overshoot is under 0.5% and M ≈ p is fair. On a narrow one it is wildly loose: p_(1) = 0.99 at top_p = 0.9 gives n* = 1 and M = 0.99, so you discarded 1%, not 10%. “top_p = 0.9 throws away a tenth” is an upper bound, usually a loose one. And since truncation’s divergence is exactly log(1/M) (see the sampling-math companion), M, not p, is the number to log.

Why maximization loops and why the raw tail derails

Nucleus sampling exists because both obvious strategies fail, in opposite directions. Maximization — greedy or beam search — is a deterministic map from a bounded context to the next token. Over a window of L positions and vocabulary V the state space is finite, so any deterministic trajectory must eventually cycle. Repetition loops are not a quirk of one model but a structural consequence of noiseless decoding — and the loop grows more confident the longer it runs.

Pure sampling fails the other way. Let q be the per-step mass on tokens the model cannot rank reliably:

P(at least one tail draw in T steps) = 1 − (1 − q)^T
q = 0.02, T = 500  →  1 − 0.98^500 = 0.99996

A 2% junk budget per step is near-certain to fire inside one paragraph, and the bad token is then conditioned on forever. Human text lives between the poles — its surprisal fluctuates rather than staying pinned high — which is the original argument for truncating per step.

Adaptive cardinality: the property a fixed k lacks

Per-step uncertainty swings by orders of magnitude inside one sentence. The honest measure is the effective support size exp(H_t), the step’s perplexity: how many options the model is really offering. Mid-idiom it can sit near 1; at a fresh sentence boundary, in the hundreds.

A fixed k applies one number to both: at a confident step k = 40 readmits 39 tokens the model rated near-impossible; at an open step the same 40 amputates candidates indistinguishable from the ones kept. Top-p inverts which quantity is pinned: top-k fixes cardinality and lets retained mass float; top-p fixes retained mass (up to the overshoot above) and lets cardinality float. Only one survives moving from step to step: a count of 40 means nothing in isolation, while 90% of the model’s belief means the same thing everywhere.

Worked: one p, two very different steps

Hold top_p = 0.9 fixed across a confident step and an open one.

Step A  p = [.82, .09, .04, .02, .015, .01, .005]
  cumulative .82 → .91 ≥ 0.9    n* = 2,  M = 0.910
  renormalized: [.9011, .0989]      H = 0.722 nats, exp(H) = 2.06

Step B  p = [.11,.10,.095,.09,.085,.08,.075,.07,.065,.06,.055,.05] + 13×.005
  cumulative .885 → .935 ≥ 0.9  n* = 12, M = 0.935
  renormalized top token .11/.935 = .1176
                                    H = 2.706 nats, exp(H) = 14.96

One parameter, a sixfold difference in cardinality — and n* tracks exp(H) closely both times (2 against 2.06; 12 against 14.96, the gap being tail that entropy counts and the nucleus deletes). Now serve both with one k. At k = 5, step A readmits tokens at .02 and .01 against a leader at .82; step B cuts seven tokens within a hair of the .085 it kept. No k is right for both rows.

How p maps to nucleus size depends on the tail

How aggressively n* responds to p depends entirely on the shape of the decay. Two tractable cases:

geometric  p_(i) = (1−r) r^(i−1),  C_n = 1 − r^n
           n* = ceil( ln(1−p) / ln r )
           r = 0.6:  p=.9 → 5,   p=.95 → 6,   p=.99 → 10

power law  p_(i) = C i^(−s), s > 1,  tail(n) ≈ C n^(1−s)/(s−1)
           n* ≈ ( C / ((s−1)(1−p)) )^(1/(s−1))  ∝ (1−p)^(−1/(s−1))
           s = 1.5, C = 1/ζ(1.5) = 0.383:  p=.9 → ~59,  p=.99 → ~5900

A geometric tail grows n* only logarithmically in 1/(1−p): tightening the discard budget tenfold doubles the nucleus. A power-law tail grows it as a power — at s = 1.5 the same change multiplies the nucleus by a hundred. Real language-model tails are far closer to the power law, which is why 0.95 → 0.99 is no small nudge and why top-p feels erratic on high-entropy steps.

The nucleus size is a random variable

n* is not a setting you chose — it is a function of the step distribution, which depends on the prefix, which was itself sampled. So one generation draws a sample N_1, …, N_T from a distribution over nucleus sizes, and that distribution is what your config really means.

The shape is strongly right-skewed: the mode is 1 (every step where the top token alone clears p), the body sits in low single digits, and a thin tail of genuinely open steps runs into the hundreds — exactly what the previous section predicts. The mean is a bad summary, dragged by rare fat steps; report the median and a high quantile. The useful contrast is with retained mass: M is confined to [p, p + p_(n*)) at every step, so it is the stable audit statistic, while N is unbounded and therefore the diagnostic one.

Renormalization: uniform inside, absolute at the edge

The survivors are rescaled by the mass they retained:

p’_i = p_i / M  for i ∈ S,   0 otherwise
p’_i / p’_j = p_i / p_j   for all i, j ∈ S

The second line is the point. Dividing by a scalar preserves every ratio inside the nucleus exactly: nucleus sampling never re-ranks survivors or adjusts their odds against each other. Each receives the same boost 1/M ∈ [1, 1/p] — at most 1.111× at p = 0.9, and typically less. A small effect.

The large effect is at the boundary, and it is not gentle. A token at rank n* + 1 goes from positive probability to exactly zero: an infinite change in log-odds against every survivor. Two near-identical probabilities straddling the cut end up separated by an unbridgeable gap. Truncation is a support edit with a hard discontinuity, not a soft reweighting.

Failure modes

Collapse to one. Whenever p_(1) ≥ p the nucleus is a single token, and a lone survivor renormalizes to 1.0 — the step is greedy, and temperature has no effect on it. At p = 0.9 that fires on every step the model is 90%-confident: closing brackets, function words, the back half of a common phrase. A large share of a ‘temperature 1.0, top_p 0.9’ generation is therefore deterministic — often what you wanted, but worth knowing.

Long flat tails. When the model is genuinely lost, p_(1) may be 0.02 and the sum must walk thousands of entries to reach 0.9, admitting exactly the junk truncation exists to remove. Top-p prunes hardest when the model is confident and softest when it is confused — backwards, and the gap min-p targets. Finally, top-p does not commute with temperature (proved in the companion article), so pin the order; and p = 1.0 is a no-op, hence the top_k guard many stacks keep alongside it.

Implementation: sort, cumsum, and the partial sort

The literal algorithm: softmax over V, full descending sort, prefix sum, a search for the first index reaching p, mask, renormalize, draw — O(V log V), dominated by the sort. At V = 128k that is milliseconds of single-core work per token, not noise when a CPU SLM emits 20–40 tokens per second.

The fix follows from earlier sections: you never need the full order, only the prefix up to n*, which is almost always small. Select the top G (say 1024) with an O(V) partial selection, sort just those in O(G log G), and cumsum. It is exact iff the mass over those G reaches p — a one-line check; if it fails, fall back to the full sort, because silently accepting the clipped set is just top_k = G in disguise. Since N is heavy-tailed, size G from the observed p99, never the mean. And since softmax is monotone you may sort raw logits and exponentiate only the prefix — but the normalizer still costs a full pass, so O(V) is the floor.