Beam Search › Nucleus Sampling and Top-k Sampling: Stochastic Alternatives

Beam search maximizes probability. For some applications, this is exactly what you want: the most likely translation, the most probable answer. But for creative text generation, the most probable text is often the least interesting. When a language model assigns high probability to the same few words repeatedly, the output becomes repetitive and bland.

Consider generating a short story. The highest-probability continuation of "She walked into the dark room and saw" might be "a light" because those two words appear frequently in the training data after similar contexts. But "a light" is boring. The story might be much more interesting if the model picked a lower-probability but more unexpected continuation, like "her reflection looking back at her from a shattered mirror". Maximizing probability produces the average, the statistically most typical continuation. Creative writing, by definition, should not be average.

Sampling-based methods introduce stochasticity to break this pattern.

Top-k sampling restricts the sampling pool to the $k$ most probable tokens at each step, then samples from that restricted distribution:

$$P'(w) = \begin{cases} \frac{P(w)}{\sum_{w' \in \text{Top-}k} P(w')} & \text{if } w \in \text{Top-}k \\ 0 & \text{otherwise} \end{cases}$$

where:

• $P(w)$: the model's original probability for token $w$
• $\text{Top-}k$: the set of the $k$ tokens with highest probability
• $P'(w)$: the renormalized probability used for sampling

The problem with top-k is that the appropriate value of $k$ varies with context. If the model is very confident (the top-1 probability is 0.99), then sampling from the top-50 includes many very unlikely tokens and can produce incoherent output. If the model is very uncertain (probabilities are nearly uniform), then restricting to top-5 throws away most of the valid continuations.

Nucleus sampling (Holtzman et al., 2020) addresses this by sampling from the smallest set of tokens whose cumulative probability exceeds a threshold $p$:

$$V_p = \min\left\{ V' \subseteq V : \sum_{w \in V'} P(w) \geq p \right\}$$

where:

• $V_p$: the nucleus, the minimal set of tokens covering cumulative probability mass at least $p$
• $V'$: a candidate subset of the vocabulary, sorted by descending probability
• $p$: the probability threshold, typically 0.9 or 0.95

The set is constructed by sorting all tokens in descending probability order and including tokens one by one until the running sum of probabilities reaches $p$.

Tokens outside the nucleus receive zero probability. Those inside are renormalized.

The key advantage is adaptivity. When the model is confident, the nucleus is small (a few tokens cover 0.9 of the probability mass). When the model is uncertain, the nucleus is large (many tokens are needed to accumulate 0.9). The sampling pool automatically adjusts to the local probability distribution.

Nucleus sampling is the default choice for open-ended text generation tasks: story writing, dialogue systems, creative applications. Beam search is better suited for constrained generation tasks where there is a specific correct answer: translation, summarization, question answering. The choice between them reflects a deeper question about what "good output" means for a given task.

Temperature is a parameter $\tau$ that reshapes the probability distribution before sampling:

$$P_{\tau}(w) = \frac{P(w)^{1/\tau}}{\sum_{w'} P(w')^{1/\tau}}$$

where:

• $\tau$: the temperature parameter
• $P(w)^{1/\tau}$: the unnormalized probability with temperature scaling applied

For $\tau < 1$, the distribution sharpens: high-probability tokens become even more likely, low-probability tokens shrink. This makes output more focused and repetitive. For $\tau > 1$, the distribution flattens: probabilities become more uniform, and sampling becomes more exploratory and unpredictable. At $\tau = 1$, sampling is from the unmodified distribution. Temperature is often combined with top-k or nucleus sampling.

In modern large language model APIs, you typically encounter all three of these controls: temperature, top-k, and top-p. A common practical recipe for creative generation is temperature around 0.8 to 1.0 combined with top-p around 0.9. For factual generation, temperature near 0.2 to 0.5 with greedy or small beam search tends to produce more reliable outputs.

A more recent alternative, contrastive decoding (Li et al., 2022), generates text by contrasting the outputs of a strong model and a weak model. At each step, the score for a token is computed as the log-probability difference between the expert (strong) model and the amateur (weak) model:

$$\text{score}_{CD}(w) = \log P_{\text{expert}}(w \mid \cdot) - \log P_{\text{amateur}}(w \mid \cdot)$$

The intuition is that tokens that are highly probable under both models are likely to be generic, high-frequency words that appear frequently in training data regardless of context. Tokens that are much more probable under the expert than the amateur are the ones that reflect the expert's superior understanding of the context. By amplifying this contrast, contrastive decoding produces output that is more informative and contextually appropriate, avoiding the repetition and generic phrasing that characterize maximum-probability decoding.

Contrastive decoding has shown promising results on long-form question answering and knowledge-intensive tasks, where avoiding generic outputs is especially important.