Truncation and Sampling Strategies for Language Model Decoding

150 concepts115 papers1 proposal

When generating text with an autoregressive language model, the model's primary output at each step is a probability distribution over the entire vocabulary. The challenge lies in how we select tokens from this distribution to form coherent, natural sentences.

Intuitively, one might assume that always picking the most likely token—a strategy known as greedy decoding—or optimizing for the most probable sequence via beam search would yield the best results. However, in practice, pure likelihood maximization often fails. As observed by Deguchi et al. and Zhou et al., maximizing probability frequently causes models to fall into repetitive loops, degenerate patterns, or local optima. Furthermore, human language does not naturally consist of a sequence of the highest-probability tokens; instead, it exhibits a rich variety of phrasing and unexpected choices that pure maximization strategies fail to capture, leading to stylistic blandness (Zhang et al.).

Introducing Randomness via Stochastic Decoding

To inject variety and mimic the natural diversity of human text, researchers use stochastic decoding, or multinomial sampling. Instead of deterministically choosing the top token, the system treats the model's output scores as a true probability distribution and samples from it randomly (Peric et al., Chung et al.).

However, vanilla sampling introduces a severe vulnerability: the "long tail" of the vocabulary distribution. Even a well-trained model assigns tiny, non-zero probabilities to thousands of completely irrelevant or ungrammatical tokens. If the system samples from the entire distribution, it will eventually pick one of these highly improbable tokens. Because autoregressive models condition each new token on all previous choices, a single nonsensical token can permanently derail the logical coherence of the entire generation.

To resolve this, the distribution must be truncated before sampling occurs, filtering out the unreliable tail while preserving the viable candidates.

Fixed-Rank vs. Dynamic Thresholding

The two primary paradigms for truncating the vocabulary distribution are Top-$k$ sampling and Top-$p$ (nucleus) sampling. They differ fundamentally in how they adapt to the model's confidence.

Top-$k$ Sampling: Fixed-Rank Truncation

As detailed by Kumar et al., Top-$k$ sampling restricts the next-token selection to a rigid, pre-determined number ($k$) of the highest-probability candidates. The remaining tokens are zeroed out, and the distribution is re-normalized.

While this strategy effectively balances logical coherence with linguistic variety (Grosjean et al.), its primary flaw is its structural rigidity. The shape of a language model's probability distribution changes drastically depending on the context:

  • Sharp Distributions: When the model is highly confident (e.g., completing a common idiom like "piece of..."), the probability mass is concentrated entirely on one or two tokens (like "cake"). If $k=50$, the model is forced to include 48 highly improbable tokens in its sampling pool, risking an unnatural choice.
  • Flat Distributions: When the next word is highly ambiguous (e.g., starting a new sentence), there might be dozens of equally valid nouns or verbs, spreading the probability mass flatly across hundreds of options. In this scenario, a rigid $k=50$ prematurely cuts off many high-quality, grammatically correct candidates.

Top-$p$ (Nucleus) Sampling: Cumulative Probability Thresholding

To address the limitations of fixed-rank truncation, nucleus sampling introduces a dynamic threshold based on cumulative probability mass. Instead of choosing a fixed number of tokens, the algorithm selects the minimal set of top tokens whose combined probability meets a specified target threshold $p$ (where $0 < p \le 1$) (Kumar et al., Budzianowski et al.).

Sharp Distribution (High Confidence)
Tokens:   [ "cake", "paper", "art", "work", ... ]
Prob:     [  0.92 ,  0.02  ,  0.01 ,  0.01 , ... ]
Top-p pool (p=0.95): Only [ "cake", "paper" ] (Window contracts)

Flat Distribution (Low Confidence)
Tokens:   [ "The" , "A"   , "They", "She" , ... ]
Prob:     [  0.10 ,  0.09  ,  0.08 ,  0.08 , ... ]
Top-p pool (p=0.95): Dozens of tokens included (Window expands)

This mechanism allows the selection window to expand or contract fluidly based on the model's certainty. When the model is confident, the nucleus of tokens exceeding $p$ is small, preventing bad choices. When the model is uncertain, the nucleus expands, allowing for creative and diverse paths without sacrificing grammatical structure.

Stochastic Candidate Generation and Reranking

Beyond direct text generation, stochastic truncation strategies serve as a powerful engine for multi-candidate generation pipelines. Rather than relying on a single deterministic output, modern architectures often "over-sample" a massive pool of diverse candidates using nucleus or Top-$k$ sampling and then apply a secondary evaluation or post-processing step (Ippolito et al., Zhou et al.).

This paradigm shift is highly effective for complex tasks like machine translation and open-ended reasoning. As demonstrated by Fernandes et al. and Rooshenas, generating a broad set of hypotheses via stochastic sampling provides a wider linguistic search space. A secondary quality-aware reranker can then evaluate these complete sequences, often discovering high-quality, natural outputs that would have been pruned early on by standard beam search due to lower initial word-level probabilities. Similarly, Song et al. show that leveraging "Best-of-N" stochastic sampling allows smaller language models to achieve significant performance gains on reasoning and coding tasks, outperforming single greedy outputs from much larger models.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_nucleus_sampling_f0c43dee,
  title = {nucleus sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nucleus-sampling/rdr_f0c43dee6b194ed496551928690ce97c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_nucleus_sampling_f0c43dee_v1,
  title = {nucleus sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nucleus-sampling/rdr_f0c43dee6b194ed496551928690ce97c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake