Stochastic Decoding Strategies in Large Language Models: Mathematical Foundations of Temperature Scaling, Top-k, Nucleus (Top-p), Typical Sampling, and Min-p

Autoregressive language models generate text sequentially by estimating a conditional probability distribution over a vocabulary at each decoding step. While model training optimizes cross-entropy loss over large corpora, the quality, diversity, and coherence of generated sequences depend directly on the decoding strategy used to select tokens from the output logits.

Deterministic algorithms such as greedy search and beam search systematically fail in open-ended generation tasks, collapsing into repetitive loops and dull phrasing. Conversely, unconstrained stochastic sampling from the raw distribution samples improbable tokens from the long tail of the vocabulary, causing severe semantic drift.

Modern inference engines rely on stochastic decoding algorithms that dynamically reshape, truncate, and normalize probability distributions before drawing samples. Understanding the mathematical mechanics of temperature scaling, top-k, nucleus (top-p), locally typical sampling, and min-p is essential for tuning inference pipelines across deterministic code generation, structured extraction, and open-ended reasoning.

The Autoregressive Decoding Formulation

At timestep $t$, given a context sequence $x_{<t} = (x_1, x_2, \dots, x_{t-1})$, a transformer language model computes an unnormalized logit vector $z_t \in \mathbb{R}^{|V|}$ over a vocabulary $V$ containing $|V|$ discrete tokens:

$$z_t = W_{\text{vocab}} h_t$$

Here, $h_t \in \mathbb{R}^d$ represents the final hidden state of the transformer stack, and $W_{\text{vocab}} \in \mathbb{R}^{|V| \times d}$ denotes the output projection matrix (un-embedding layer).

The categorical distribution over candidate tokens is obtained via the standard softmax function:

$$P(x_t = v \mid x_{<t}) = \frac{\exp(z_{t, v})}{\sum_{v' \in V} \exp(z_{t, v'})}$$

In deterministic greedy decoding, the model selects the mode of the distribution at every step:

$$\hat{x}_t = \arg\max_{v \in V} P(x_t = v \mid x_{<t})$$

As demonstrated by Holtzman et al. (2020), greedy search and beam search suffer from neural text degeneration. Because language models assign high probabilities to generic phrases and repetitive n-grams, maximizing token likelihood leads to degenerate loops and unnatural text statistics that deviate sharply from human writing. Human text exhibits localized dips in conditional probability where surprising or context-shifting words occur.

Temperature Scaling

Temperature scaling rescales logits by a strictly positive scalar parameter $T > 0$ before computing the softmax distribution. Originally adapted from statistical mechanics and simulated annealing (Ackley et al., 1985), temperature controls the entropy of the resulting categorical distribution.

The temperature-adjusted probability distribution $P_T(v)$ is defined as:

$$P_T(x_t = v \mid x_{<t}) = \frac{\exp(z_{t, v} / T)}{\sum_{v' \in V} \exp(z_{t, v'} / T)}$$

Limiting Behaviors

1. As $T \to 0^+$, the distribution concentrates all probability mass onto the maximum logit value:

$$\lim_{T \to 0^+} P_T(x_t = v) = \begin{cases} 1 & \text{if } v = \arg\max_{u \in V} z_{t, u} \\ 0 & \text{otherwise} \end{cases}$$

This recovers deterministic greedy argmax selection.

1. At $T = 1.0$, the sampling distribution matches the raw model output probabilities.
2. As $T \to \infty$, the logits become negligible relative to $T$, causing the distribution to converge to a discrete uniform distribution:

$$\lim_{T \to \infty} P_T(x_t = v) = \frac{1}{|V|} \quad \forall v \in V$$

Entropy Dynamics

The Shannon entropy $H(P_T)$ of the distribution is given by:

$$H(P_T) = -\sum_{v \in V} P_T(v) \log P_T(v)$$

Differentiating $H(P_T)$ with respect to $T$ yields $\frac{d H(P_T)}{d T} \ge 0$, establishing that entropy increases monotonically with temperature.

While temperature scales the spread of probabilities, it operates uniformly across all tokens. Increasing $T$ flattens the distribution and inflates the probability of low-confidence tail tokens, often generating incoherent tokens unless combined with truncation filters.

Fixed-Rank Truncation: Top-k Sampling

Top-k sampling, introduced for language models by Fan et al. (2018), restricts candidate tokens to the $k$ most probable items in vocabulary $V$.

Let the vocabulary tokens be sorted by descending probability at timestep $t$:

$$P(x_t = v_{(1)}) \ge P(x_t = v_{(2)}) \ge \dots \ge P(x_t = v_{(|V|)})$$

The top-k candidate set $V^{(k)} \subset V$ is defined as:

$$V^{(k)} = \{ v_{(1)}, v_{(2)}, \dots, v_{(k)} \}$$

The truncated distribution $P_{\text{top-}k}(v)$ sets all probabilities outside $V^{(k)}$ to zero and renormalizes the remaining mass:

$$P_{\text{top-}k}(x_t = v) = \begin{cases} \frac{P(x_t = v)}{\sum_{u \in V^{(k)}} P(x_t = u)} & \text{if } v \in V^{(k)} \\ 0 & \text{otherwise} \end{cases}$$

Structural Failure Modes

Top-k sampling enforces a static rank threshold regardless of the underlying distribution geometry:

• High-Confidence (Peaked) Contexts: When the model predicts a specific grammatical continuation (for example, a closing parenthesis or common idiom where $P(v_{(1)}) = 0.98$), top-k with $k=50$ still admits 49 highly improbable tokens into the candidate set.
• Low-Confidence (Flat) Contexts: When the model evaluates dozens of equally plausible synonyms (for example, in creative descriptions where 200 candidates each carry $P(v) \approx 0.004$), top-k with $k=50$ arbitrarily cuts off 150 valid options.

Cumulative Probability Truncation: Nucleus (Top-p) Sampling

To address the rigidity of fixed rank thresholds, Holtzman et al. (2020) introduced nucleus sampling (top-p sampling). Nucleus sampling defines the truncation boundary dynamically by accumulating probability mass until reaching a predefined threshold $p \in (0, 1]$.

The nucleus candidate set $V^{(p)} \subset V$ is the smallest subset of top-ranked tokens whose cumulative probability exceeds $p$:

$$V^{(p)} = \{ v_{(1)}, v_{(2)}, \dots, v_{(m)} \}$$

where $m$ is the minimal index satisfying:

$$\sum_{i=1}^m P(x_t = v_{(i)}) \ge p$$

The truncated and renormalized distribution is:

$$P_{\text{top-}p}(x_t = v) = \begin{cases} \frac{P(x_t = v)}{\sum_{u \in V^{(p)}} P(x_t = u)} & \text{if } v \in V^{(p)} \\ 0 & \text{otherwise} \end{cases}$$

Dynamic Candidate Pool Sizing

The size of the candidate pool $|V^{(p)}_t|$ adjusts automatically based on the conditional entropy of the distribution:

• When the model is confident ($P(v_{(1)}) > p$), the nucleus collapses to a single token ($|V^{(p)}| = 1$), acting deterministically.
• When uncertainty is high, the nucleus expands across hundreds or thousands of tokens, preserving lexical diversity.

Tail Inflation Under High Temperature

When high temperatures ($T > 1.0$) are applied prior to top-p truncation, individual token probabilities flatten. If the top token's probability drops to 0.02, accumulating $p = 0.90$ requires including hundreds of low-probability tail tokens, permitting unvetted low-quality generations.

Information-Theoretic Truncation: Locally Typical Sampling

Locally typical sampling, formulated by Meister et al. (2022), approaches token selection through an information-theoretic framework known as the Expected Information Hypothesis.

In human communication, speakers balance information transfer across utterances, maintaining a relatively uniform rate of information rather than selecting either overly obvious or overly obscure words.

The information content (surprisal) of a candidate token $v \in V$ is:

$$h(v) = -\log_2 P(x_t = v \mid x_{<t})$$

The expected information of the next token corresponds to the conditional Shannon entropy $H(X_t \mid x_{<t})$:

$$H(X_t \mid x_{<t}) = \sum_{v \in V} P(x_t = v \mid x_{<t}) \cdot h(v) = -\sum_{v \in V} P(x_t = v \mid x_{<t}) \log_2 P(x_t = v \mid x_{<t})$$

Locally typical sampling constructs a candidate set $V^{(\text{typ})} \subset V$ by selecting tokens whose surprisal is closest to the conditional entropy:

$$V^{(\text{typ})} = \{ v \in V \mid |h(v) - H(X_t \mid x_{<t})| \le \epsilon \}$$

Tokens are sorted by their absolute deviation from the expected information:

$$\Delta(v) = |-\log_2 P(x_t = v \mid x_{<t}) - H(X_t \mid x_{<t})|$$

Tokens with minimal $\Delta(v)$ are accumulated until their cumulative probability mass reaches threshold $p$:

$$\sum_{v \in V^{(\text{typ})}} P(x_t = v \mid x_{<t}) \ge p$$

By favoring tokens whose information density matches the local context entropy, typical sampling suppresses both repetitive boilerplate tokens (which have near-zero surprisal) and nonsensical tail tokens (which have extreme surprisal).

Relative Probability Truncation: Min-p Sampling

Min-p sampling, proposed by Menet et al. (2024), introduces an adaptive truncation threshold scaled directly against the highest-probability token in the distribution.

Rather than defining an absolute cumulative mass $p$ or rank $k$, min-p defines a base scaling factor $p_{\text{base}} \in [0, 1]$. The minimum probability threshold $p_{\text{threshold}}$ at step $t$ is calculated as:

$$p_{\text{threshold}} = p_{\text{base}} \times \max_{v \in V} P(x_t = v \mid x_{<t})$$

Let $v_{\text{top}} = \arg\max_{v \in V} P(x_t = v \mid x_{<t})$ denote the top candidate. The candidate set $V^{(\text{min-}p)}$ retains only tokens whose probability is at least $p_{\text{base}}$ times that of $v_{\text{top}}$:

$$V^{(\text{min-}p)} = \{ v \in V \mid P(x_t = v \mid x_{<t}) \ge p_{\text{base}} \cdot P(x_t = v_{\text{top}} \mid x_{<t}) \}$$

The truncated distribution is renormalized:

$$P_{\text{min-}p}(x_t = v) = \begin{cases} \frac{P(x_t = v)}{\sum_{u \in V^{(\text{min-}p)}} P(x_t = u)} & \text{if } v \in V^{(\text{min-}p)} \\ 0 & \text{otherwise} \end{cases}$$

Behavioral Advantages

Min-p adapts dynamically across confidence regimes:

• Confident Contexts: If $P(v_{\text{top}}) = 0.80$ and $p_{\text{base}} = 0.10$, the threshold is $0.08$. All tokens below 8% probability are immediately pruned, preventing low-likelihood noise.
• Uncertain Contexts: If $P(v_{\text{top}}) = 0.10$ and $p_{\text{base}} = 0.10$, the threshold becomes $0.01$. Any token with at least 1% probability remains eligible.

Because the cutoff scales proportionally with the top candidate, min-p maintains stability even at high temperatures ($T = 1.2$ to $1.5$). It allows creative exploration among competing top candidates while rigorously excluding tail tokens.

Perplexity-Controlled Decoding: Mirostat

Mirostat, developed by Basu et al. (2021), treats text generation as a closed-loop control problem. Standard samplers often drift over long generations into either:

1. The Boredom Trap: Perplexity collapses, and the model enters repetitive loops.
2. The Confusion Trap: Perplexity escalates, and the model produces incoherent outputs.

Mirostat regulates the generation rate of surprise to match a target surprisal $\tau$.

At each step $t$, the algorithm observes the surprise of the sampled token $x_t$:

$$s(x_t) = -\log_2 P(x_t \mid x_{<t})$$

The control error $e_t$ is:

$$e_t = s(x_t) - \tau$$

A feedback parameter $\mu_t$ is updated via gradient descent:

$$\mu_{t+1} = \mu_t - \eta e_t$$

where $\eta$ is the learning rate.

The truncation parameter (such as dynamic top-k or top-p threshold) is then derived as a function of $\mu_{t+1}$ using estimated Zipfian power-law parameters of the vocabulary distribution. By dynamically widening or narrowing candidate pools in response to observed surprisal, Mirostat enforces stable cross-entropy across thousands of generated tokens.

Decoding Strategies in Production

Each decoding strategy optimizes for distinct trade-offs between computational overhead, vocabulary coverage, and sample coherence:

• Greedy Search ($T = 0$): Deterministic mode selection. Ideal for code compilation, mathematical reasoning, and schema-constrained JSON extraction where reproducibility is paramount.
• Temperature + Top-p: General standard for conversational assistants. Standard settings ($T = 0.7, p = 0.9$) provide balance, though prone to degradation if temperature is pushed past $1.0$.
• Min-p Sampling: Recommended for creative writing, narrative generation, and high-temperature exploration ($T \ge 1.0, p_{\text{base}} = 0.05\text{--}0.10$). Prunes low-confidence tail tokens without restricting multi-candidate exploration.
• Locally Typical Sampling: Well-suited for stylized narrative and essay generation where uniform information density improves prose cadence.
• Mirostat: Preferred for long-form synthetic book generation, long-horizon narrative planning, and autonomous agents prone to degradation over extended context horizons.

Sources

• Fan, A., Lewis, M., & Dauphin, Y. (2018). Hierarchical Neural Story Generation. Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL).
• Holtzman, A., Buys, J., Du, L., Forbes, M., & Choi, Y. (2020). The Curious Case of Neural Text Degeneration. International Conference on Learning Representations (ICLR).
• Meister, C., Pimentel, T., Wiher, G., & Cotterell, R. (2022). Locally Typical Sampling. Transactions of the Association for Computational Linguistics (TACL).
• Basu, S., Ramachandran, G. S., Keskar, N. S., & Varshney, L. R. (2021). Mirostat: A Neural Text Decoding Algorithm that Directly Controls Perplexity. International Conference on Learning Representations (ICLR).
• Menet, M. et al. (2024). Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs. arXiv preprint arXiv:2407.01082.
• Ackley, D. H., Hinton, G. E., & Sejnowski, T. J. (1985). A Learning Algorithm for Boltzmann Machines80012-4). Cognitive Science, 9(1), 147-169.