Basic sampling techniques

Resources

• Overview of samplers by author of min-p: https://gist.github.com/kalomaze/4473f3f975ff5e5fade06e632498f73e

Basics

• Formally, given a sequence of tokens $x=(x_1,x_2,\dots ,x_n)$ and a finite vocabulary $V$, where each token $x_i\in V$, an autoregressive language model models the probability distribution $P(x_t|x_1,x_2,\dots ,x_{t-1})$, for each token $x_t$ in the sequence.

How to get the next token

• $x_t=\arg {\max }_{v\in V}P(x_t=v|x_1,x_2,\dots ,x_{t-1})$. (greedy decoding)
• $x_t\sim P(x_t={\hat{x}}_t|x_1,x_2,\dots ,x_{t-1})$ (stochastic sampling)

Temperature sampling

• Temperature sampling first divides the logits by a temperature parameter $\tau >0$ before passing them through the softmax function to obtain a modified probability distribution $P_{\tau }(x_t=v|x_1,\dots ,x_{t-1})$: $P_{\tau }(x_t=v|x_1,\dots ,x_{t-1})=\frac{\exp (z_v/\tau )}{{\sum }_{v^{\prime }\in V}\exp (z_{v^{\prime }}/\tau )}$ where $z_v=\log P(x_t=v|x_1,x_2,\dots ,x_{t-1})$ is the (unnormalized) log probability of token $v$.

• The temperature parameter $\tau$ controls the randomness of the sampling process.

  • $\tau >1$ result in a more uniform probability distribution, increasing the chances of sampling lower-probability tokens and generating more diverse output.
  • $\tau <1$ make the distribution sharper, favoring higher-probability tokens and more conservative and deterministic outputs.

Top-p sampling (nucleus sampling)

• Given $P_{\tau }(x_t=v|x_1,x_2,\dots ,x_{t-1})$ over the vocabulary $V$ at position $t$, top-p sampling first sorts the tokens in descending order of their probabilities.
• It then selects the smallest set of tokens whose cumulative probability exceeds a predefined threshold $p$, where $p\in (0,1]$.
• It finally samples according to the re-normalized probabilities.

Sampler Orders

• The order in which samplers are applied matters and can meaningfully change the output.
  • For example, if Temperature comes first in the order before top P, then your Temperature value would change the output probabilities that top P judges, and it will truncate differently.
  • If top P comes before Temperature, then the original probabilities are measured first, which means Temperature will only affect the tokens you decided to keep using top P.
• It’s usually assumed that temperature sampling is applied first

Beam search

• Beam search is a heuristic search algorithm
  • modification of breadth-first seach (BFS) to reduce memory requirements
• How it proceeds
  • Start with an initial state (e.g. partly completed generation)
  • Generate the next top K candidates (e.g. for tokens, probabilities define the ranking) where K is the beam width
  • From each of those K candidates, score all possible states (i.e. tokens)
  • Keep only the top K candidates overall
  • Start over until a stopping criterion is met (e.g. maximum length or end of text token)
• A beam search with K=1 is equivalent to greedy decoding
• How do you score candidates deeper in the search tree?
  • Sum of log probabilities (may tend to favor shorter sequences)
  • Average log prob
  • Length normalized score

Min-P

• https://arxiv.org/abs/2407.01082

Motivation

• Objectives for min-p are to

  • (1) match or outperform the state-of-the-art top-p sampling across various reasoning and performance benchmarks at standard temperature settings between 0 and 1
  • (2) better handle the creativity-coherence trade-off at higher temperatures
  • (3) provide a simple, effective sampling method without relying on additional techniques like repetition penalties to address the externalities of high-temperature sampling.

• Top-p sampling does not work well for higher temperatures: here, tokens from the “unreliable tail” can still enter the sampling pool

  • 
  • When using top-p sampling, it is recommended to adjust either the value of p or the temperature τ , but not both simultaneously (OpenAI API, 2024) as they can lead to conflicting effects.

Definition

• The method uses a relative probability threshold $p_{base}\in (0,1]$ to scale the maximum token probability $p_{max}$ to determine the absolute probability threshold $p_{scaled}$. One can think that $p_{base}\approx 0.1$
  • Sampling is then performed on tokens with probability greater than or equal to $p_{scaled}$.
• Formally, given the maximum probability over the token distribution $p_{max}={\max }_{v\in V}P(v|x_1,\dots ,x_{t-1})$, the absolute probability threshold $p_{scaled}$ is calculated as: $p_{scaled}=p_{base}\times p_{max}$
  • The sampling pool $V_{min}$ is then defined as the set of tokens whose probability is greater than or equal to $p_{scaled}$: $V_{min}=\{v\in V:P(v|x_1,x_2,\dots ,x_{t-1})\ge p_{scaled}\}$ Finally, the next token ${\hat{x}}_t$ is randomly sampled from the set $V_{min}$ according to the normalized probabilities: ${\hat{x}}_t\sim \frac{P(v|x_1,\dots ,x_{t-1})}{{\sum }_{v^{\prime }\in V_{min}}P(v^{\prime }|x_1,\dots ,x_{t-1})}\text{ for }v\in V_{min}$
• A lower top-p value results in more selective token choices and a bias towards more likely outputs.

Effects

• High-confidence predictions: When the model assigns high probability to a particular next token, min-p filters out low-probability alternatives. This preserves coherence by avoiding sampling from the “unreliable tail” that could derail generation
  • 
• Low-confidence predictions: When there is no clear front-runner, min-p relaxes its filter. This allows the model to sample from a more diverse set of plausible continuations, enabling creativity in open-ended settings.
  •