How does nucleus sampling work?

Nucleus sampling (also called top-p sampling) works by dynamically choosing a set of likely next tokens whose combined probability reaches a specified threshold, then randomly sampling one token from that set.

Unlike top-k, the number of eligible tokens can change at every generation step.

Step 1: Predict next-token probabilities

For the current context, imagine the LLM produces:

Token A → 0.40
Token B → 0.28
Token C → 0.17
Token D → 0.10
Token E → 0.05

The tokens are sorted from highest to lowest probability.

Step 2: Apply the top-p threshold

Suppose top-p = 0.80.

Add the probabilities in descending order until the total first reaches or exceeds 0.80:

A             → 0.40
A + B         → 0.68
A + B + C     → 0.85  ✓ stop

The nucleus is A, B, and C. Tokens D and E are excluded.

Notice that the retained probability mass is 0.85, not exactly 0.80: the threshold determines when to stop adding complete tokens.

Step 3: Renormalize and sample

The retained probabilities sum to 0.85. Divide each by 0.85 so that the allowed candidates sum to 1:

A → 0.40 / 0.85 ≈ 0.471
B → 0.28 / 0.85 ≈ 0.329
C → 0.17 / 0.85 = 0.200

Sample one token from this new distribution. A is most likely, but B or C can still be selected.

Step 4: Repeat for the next token

Append the sampled token to the generated sequence. The LLM predicts a fresh next-token distribution, and the nucleus is calculated again.

predict probabilities
       ↓
sort from highest to lowest
       ↓
keep smallest prefix with total ≥ p
       ↓
renormalize and sample
       ↓
append token and repeat

Why does the nucleus size change?

• Confident prediction: One or two tokens may already exceed the threshold, leaving a small nucleus.
• Uncertain prediction: Probabilities may be spread across many tokens, so more candidates are needed.

This is the key advantage over top-k, which uses a fixed candidate count.

How does temperature fit in?

Temperature can reshape the probabilities before nucleus filtering. Higher temperature typically makes the distribution flatter, which may increase the number of tokens needed to reach the same top-p threshold.

In short: nucleus sampling sorts tokens by probability, retains the smallest group whose cumulative probability meets the top-p threshold, renormalizes that group, samples a token, and repeats.