Sampling and Decoding Strategies

At each step, an autoregressive language model outputs logits over the vocabulary. The decoding strategy determines how to pick the next token from this distribution.

Deterministic methods:

Greedy decoding — always pick $\arg\max$ . Fast but repetitive and often suboptimal globally
Beam search — maintain top- $k$ partial sequences by cumulative log-probability. Better for translation, summarization. Can still be repetitive without length penalties

Stochastic methods:

Temperature sampling — sample from $\text{softmax}(\mathbf{z}/\tau)$ . $\tau < 1$ → sharper (more confident), $\tau > 1$ → flatter (more random), $\tau \to 0$ → greedy
Top- $k$ sampling — zero out all but the $k$ highest-probability tokens, renormalize, then sample. Controls diversity with a hard cutoff
Nucleus (top- $p$ ) sampling — keep the smallest set of tokens whose cumulative probability $\geq p$ , then sample. Adapts the cutoff to the shape of the distribution — better than fixed $k$
Min- $p$ sampling — keep tokens with probability $\geq p \cdot p_{\max}$ . Scales naturally with model confidence

Reference implementation (temperature → top-k → top-p, then sample):

def sample(logits, temperature=1.0, top_k=None, top_p=None):
    logits = logits / temperature
 
    if top_k is not None:
        values, indices = torch.topk(logits, top_k)
        logits = torch.full_like(logits, float('-inf'))
        logits.scatter_(-1, indices, values)
 
    if top_p is not None:
        sorted_logits, sorted_indices = torch.sort(logits, descending=True)
        cumulative = torch.cumsum(F.softmax(sorted_logits, dim=-1), dim=-1)
        sorted_mask = cumulative > top_p
        sorted_mask[..., 1:] = sorted_mask[..., :-1].clone()  # keep first over-threshold
        sorted_mask[..., 0] = False
        remove = sorted_mask.scatter(-1, sorted_indices, sorted_mask)
        logits = logits.masked_fill(remove, float('-inf'))
 
    probs = F.softmax(logits, dim=-1)
    return torch.multinomial(probs, num_samples=1)

Practical guidance:

Factual tasks (code, math, retrieval) → low temperature or greedy
Creative tasks (writing, brainstorming) → higher temperature + top- $p$
Common defaults: $\tau = 0.7$ , top- $p = 0.9$
Repetition penalty / frequency penalty — post-hoc damping of already-generated tokens

Why this matters: the same model can produce wildly different outputs depending on decoding. Tuning these parameters is often more impactful than prompt engineering.

Sampling and Decoding Strategies

Linked from