Nucleus Sampling (Top-p)

Unlike top-k sampling, which uses a fixed number of tokens, nucleus sampling dynamically adjusts the candidate set at each generation step. It calculates the cumulative probability distribution of the vocabulary and includes only the smallest set of top tokens whose combined probability mass exceeds the threshold p (e.g., 0.9). This means the size of the candidate pool can vary significantly from one step to the next based on the shape of the probability distribution.

The core parameter p (typically between 0.7 and 0.95) defines the minimum cumulative probability mass from which to sample.

• A high p (e.g., 0.95) includes a broader set of tokens, increasing diversity but also the risk of incoherence.
• A low p (e.g., 0.7) creates a very narrow, high-probability set, leading to more deterministic and conservative outputs. The method effectively cuts off the long tail of improbable tokens, preventing the generation of nonsensical or highly erratic text.

Nucleus sampling introduces controlled randomness by redistributing the probability mass among the selected nucleus of tokens and sampling from this renormalized distribution. This achieves a key balance:

• Avoids pure greediness (always choosing the top-1 token), which leads to repetitive and bland text.
• Mitigates the flaws of top-k, where a fixed k can sometimes include very low-probability tokens (if the distribution is flat) or exclude plausible ones (if it is peaky). The result is text that is both coherent and creatively varied, making it a preferred method for creative writing, dialogue, and other open-ended generation tasks.

Top-k sampling and nucleus sampling are both stochastic decoding methods, but they differ fundamentally in candidate selection:

• Top-k: Always selects the k highest-probability tokens, regardless of their actual probability values. This can be problematic if the distribution is very flat (including many poor tokens) or very sharp (excluding good ones).
• Nucleus (Top-p): Selects tokens based on a probability mass threshold, making the candidate set adaptive to the distribution's shape at each step. In practice, nucleus sampling often outperforms top-k in human evaluations of fluency and diversity, though they can be combined (e.g., top-p after top-k filtering) for additional control.

Within the context of confidence scoring, the nucleus sampling process itself provides a weak signal. The size and total probability mass of the selected nucleus at a given step can be indicative of the model's local uncertainty.

• A small, high-mass nucleus suggests the model is very confident about the next token.
• A large, diffuse nucleus indicates higher uncertainty, with many plausible continuations. While not a formal confidence score, monitoring the nucleus composition can be part of a broader uncertainty quantification strategy for text generation systems.

Nucleus sampling is implemented in most major transformer libraries (e.g., Hugging Face's transformers). A standard implementation involves:

1. Sorting the token probabilities in descending order.
2. Calculating the cumulative sum.
3. Selecting all tokens where the cumulative sum <= p.
4. Renormalizing the probabilities of this subset.
5. Sampling the next token from this new distribution. It is widely used as the default or recommended decoding method for creative and conversational AI applications in models like GPT-3, due to its superior balance of quality and diversity compared to pure greedy or beam search.

A decoding method that restricts random sampling at each step to the k tokens with the highest probabilities.

• Unlike nucleus sampling's dynamic vocabulary, top-k uses a fixed-size shortlist.
• Can be problematic if the probability distribution is flat (too many low-probability candidates in the top-k) or sharp (excluding plausible candidates outside the fixed k).
• Nucleus sampling (top-p) was developed to address these limitations by adapting the candidate set size based on the distribution's shape.

The simplest decoding strategy which, at each step, selects the token with the single highest probability.

• Leads to deterministic outputs but often results in repetitive, dull, and sometimes nonsensical text due to the lack of exploration.
• Contrast with beam search, which is a heuristic search algorithm that explores multiple high-probability sequences in parallel but can still suffer from blandness and repetition.

A heuristic search algorithm that explores the most promising sequences by maintaining multiple hypotheses (beams) at each generation step.

• Expands the beam_width number of most likely sequences at each step, pruning the rest.
• Aims to find a high-probability sequence overall, not just make optimal local choices (like greedy decoding).
• Tends to produce more fluent and grammatically correct text than greedy decoding but can be computationally heavier and still lacks the creativity of stochastic methods like nucleus sampling.

An alternative to nucleus sampling that selects tokens from the smallest set whose information content (surprisal) is typical, given the model's entropy.

• Instead of truncating by cumulative probability (top-p), it truncates by negative log probability (surprisal).
• Aims to match the information content of human-generated text more closely, potentially reducing the likelihood of generating bland or overly eccentric text.
• Defined by the hyperparameter tau (typicality), analogous to p in nucleus sampling.

A sampling method that dynamically adjusts the vocabulary size based on a perplexity threshold, aiming for more consistent output quality across different contexts.

• Modifies the probability distribution by cutting off tokens with probability below η * max_probability at that step.
• Designed to be more robust across diverse prompts and model sizes compared to fixed-parameter methods.
• Represents another approach to the core problem nucleus sampling solves: dynamically determining which tokens are plausible candidates for the next step.