Sampling text

How a probability distribution becomes an actual word. Inverse-CDF sampling, greedy and beam search, temperature, top-k, top-p and min-p, and the Gumbel-max trick, with what each one does to the distribution you're really sampling from.

Key idea: Sampling from a categorical distribution, decoding strategies, truncation, and the Gumbel-max trick
Real world: A raffle drum holds 100 tickets: 40 say "mat", 15 "floor", the rest other words. Drawing a ticket is sampling. Removing every ticket that appears fewer than 3 times before drawing is truncation.
In an LLM: The model outputs about 100,000 probabilities for the next token. A decoding rule turns them into one token, then repeats. Change the rule (temperature 0.7, top-p 0.95) and you have changed the distribution over whole answers, which matters for evals and for RL.

From probabilities to one token

A computer's random number generator gives a number $u$ uniformly between 0 and 1. To turn it into a token:

Line the tokens up and stack their probabilities end to end, from 0 to 1.
See which token's stretch $u$ landed in.

Each token gets chosen with exactly its probability, because its stretch is exactly that long. This is inverse-CDF sampling, the cumulative distribution from random variables read backwards.

example · a spinner

A board-game spinner is divided into slices: 40% red, 35% blue, 25% green. Spinning is drawing $u$ ; the slice it stops in is the sample. Resizing slices changes the odds without changing the spinner.

example · one token

Probabilities: " mat" 0.40, " floor" 0.15, " sofa" 0.08, and the rest. Stacked: " mat" covers 0 to 0.40, " floor" 0.40 to 0.55, " sofa" 0.55 to 0.63. Draw $u = 0.47$ : the token is " floor".

Greedy and beam search

Greedy decoding always takes the most likely token. It's deterministic, and it's what "temperature 0" means. It finds a likely answer, but not necessarily the most likely: committing to the best first token can lead into a branch with no good continuations (the MCMC page has a worked example).

Beam search keeps the $B$ best partial answers at each step and extends all of them. It finds higher-probability answers than greedy, which for open-ended text is often a bad thing: the most probable text is repetitive and bland. For translation, it works well.

Temperature

Dividing the logits by a temperature $T$ before the softmax sharpens ( $T \lt 1$ ) or flattens ( $T \gt 1$ ) every token's distribution. Note what temperature does not do: lowering it doesn't sample from a sharpened distribution over whole answers. It sharpens each step separately, which is a different thing.

Truncation

The long tail is the problem with plain sampling. Each rare token is unlikely, but there are 100,000 of them, and across a 500-token answer, the chance of hitting at least one garbage token adds up. Truncation removes the tail, then renormalises what's left so it adds to 1:

Method	Keeps	Behaviour
Top-k	the k most likely tokens	Same k whether the model is sure or unsure
Top-p (nucleus)	the smallest set whose probability adds up to p	Few tokens when confident, many when unsure
Min-p	tokens at least min-p × the top token's probability	Cut-off scales with confidence; robust at high temperature

example · a drawer of socks

You want a sock that goes with your outfit. Top-k: always consider your 5 favourite socks, even when only 2 match. Top-p: consider the favourites that make up 90% of how often you wear socks. Min-p: consider any sock you like at least a tenth as much as your favourite.

example · sampling at temperature 1.5

A creative-writing setting raises temperature to 1.5. The tail gets fatter: " banana" after "My favourite colour is" goes from about 0.1% to 0.6%. Top-p 0.9 now keeps more tail tokens, because the top ones no longer add to 90% by themselves. Min-p 0.1 still cuts " banana", because it's far below a tenth of the top token.

Try it

temperature1.00p0.90

after temperatureafter truncation, renormalised

Each token owns a stretch of 0 to 1 as long as its probability; u lands in one.

tokens kept7 of 12

probability kept92.6%

entropy of what’s sampled2.40 bits

Top-p keeps the smallest set of tokens whose probability adds up to p. It adapts to the shape: few tokens when the model is confident, many when it isn’t. At high temperature the long tail gets enough mass to sneak in.

The model’s next-token distribution after “My favourite colour is”. Temperature is applied first, then truncation, then the survivors are renormalised to add up to 1.

The Gumbel-max trick

A second way to sample: add independent Gumbel noise to each logit and take the largest. The winner is distributed exactly as the softmax. It sounds like a curiosity, but it's useful:

It turns sampling into an argmax, which GPUs do fast and which parallelises across a vocabulary split over devices.
Taking the top-k after adding noise gives a sample of k distinct items without replacement (the Gumbel-top-k trick), used for stochastic beam search.
With fixed noise, the sample is a deterministic function of the logits, which is what Gumbel-softmax relaxes to make sampling differentiable.

Why this matters beyond chat

Evals: "pass@1 at temperature 0.6, top-p 0.95" and "greedy" measure different distributions. Results aren't comparable unless the decoding settings match.
RL: the policy being trained is the truncated, tempered distribution the sampler actually used. If the trainer computes log-probabilities without the same truncation, every token's importance ratio is off. This is one source of the sampler–trainer mismatch.
Exploration: lower temperature during RL rollouts means less entropy and less exploration.

going deeper

Definitions

For logits $z \in \mathbb{R}^V$ and temperature $T$ :

p_T(i) = \frac{\exp(z_i / T)}{\sum_j \exp(z_j / T)}

Top-p keeps the set $V_p$ , the smallest prefix of tokens sorted by probability with $\sum_{i \in V_p} p_T(i) \ge p$ . Min-p keeps $\{i : p_T(i) \ge p_\text{min} \cdot \max_j p_T(j)\}$ . Either way, the sampling distribution is

\tilde p(i) = \frac{p_T(i)\, \mathbb{1}[i \in V]}{\sum_{j \in V} p_T(j)}

The sequence distribution is the product of these per-step distributions, $\tilde p(y) = \prod_t \tilde p(y_t \mid y_{\lt t})$ , which is generally not proportional to $p(y)^{1/T}$ .

Gumbel-max

If $g_i \sim \text{Gumbel}(0, 1)$ i.i.d., i.e. $g_i = -\log(-\log u_i)$ with $u_i$ uniform, then

\arg\max_i\,(z_i + g_i) \sim \operatorname{softmax}(z)

and the indices of the $k$ largest values of $z_i + g_i$ are a sample of size $k$ without replacement.

Papers

The Curious Case of Neural Text Degeneration (Holtzman et al., 2019): top-p, and why beam search text is bland
Hierarchical Neural Story Generation (Fan et al., 2018): top-k
Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs (Nguyen et al., 2024)
Locally Typical Sampling (Meister et al., 2022): keep tokens whose surprise is close to the entropy
Stochastic Beams and Where to Find Them (Kool et al., 2019): the Gumbel-top-k trick