Top-p (Nucleus) Sampling: Adaptive Vocabulary Truncation for Language Model Decoding

Nucleus sampling (top-p sampling), introduced by Holtzman et al. (2020), selects a context-dependent subset of the vocabulary before sampling. Unlike top-k sampling which always selects a fixed number of candidates, nucleus sampling adapts to the predicted distribution’s shape at each decoding step.

The Algorithm

Given predicted logits z and temperature T:

1. Compute probabilities: p_i = exp(z_i / T) / Σ exp(z_j / T)
2. Sort tokens by probability (descending): p_{(1)} ≥ p_{(2)} ≥ … ≥ p_{(V)}
3. Find nucleus: smallest set N such that Σ_{i∈N} p_{(i)} ≥ p (typically p=0.9)
4. Renormalize: p̃_i = p_i / Σ_{j∈N} p_j for i ∈ N; zero for all others
5. Sample token from renormalized distribution p̃

Dynamic Vocabulary Adaptation

Distribution Type	Top-k (k=50)	Nucleus (p=0.9)
Peaked (one token > 90%)	Includes 49 near-zero tokens	Includes 1–3 tokens
Moderate (top token ~30%)	Includes 50 of ~3000 plausible	Includes ~10–20 tokens
Flat (uniform over 1000 tokens)	Includes 50 of 1000	Includes ~900 tokens

Comparison of Decoding Methods

Method	Vocabulary Size	Determinism	Human Rating
Greedy (T→0)	1	Fully deterministic	Worst (repetitive)
Top-k (k=50)	Fixed k per step	Stochastic	Good
Top-p (p=0.9)	1 to ~50K	Stochastic	Best (Holtzman et al.)
Beam search (k=5)	Full, 5 hypotheses	Near-deterministic	Good for MT, poor for story

The “Unreliable Tail” Problem

Without truncation, language models assign non-negligible probability to thousands of semantically inappropriate tokens. At each step, the probability mass is distributed as:

• Reliable nucleus (~90%): tokens the model genuinely considers plausible
• Unreliable tail (~10%): low-probability tokens that are semantically inconsistent

Sampling from the tail even occasionally degrades coherence over many decoding steps, since errors compound across the sequence. Top-p removes the tail while respecting the model’s confidence in each specific context.

Combining Temperature and Nucleus Sampling

In practice, temperature is applied before nucleus selection:

1. Scale logits: z̃_i = z_i / T
2. Compute softmax: p_i = softmax(z̃_i)
3. Select nucleus at cumulative threshold p
4. Renormalize and sample

Lower T narrows the distribution before nucleus selection, yielding a smaller nucleus. Higher T widens it, yielding a larger nucleus.

See temperature-sampling for the logit scaling step applied before nucleus selection, beam-search for deterministic multi-hypothesis search, and autoregressive-decoding for how these methods fit into the generation loop.