Decoding strategies

A language model produces a probability distribution over the next token; decoding is the algorithm that converts this distribution into a sequence of tokens. Different decoding strategies make fundamentally different tradeoffs between output quality and diversity.

Greedy decoding

At each step, pick the most probable next token:

Greedy is fast and deterministic. It is suboptimal because a high-probability first token may lead to a poor overall sequence -- greedy commits to a choice before seeing the consequences.

Beam search

Maintain $k$ (the beam width) candidate sequences ("beams") simultaneously. At each step, expand every beam by all vocabulary tokens and keep the $k$ sequences with the highest cumulative log-probability:

Initialize: beams = [([BOS], 0.0)]
For each step t:
    candidates = []
    For each (sequence, log_prob) in beams:
        For each token v in top_K candidates:
            candidates.append((sequence + [v], log_prob + log p(v | sequence)))
    beams = top_k(candidates, k=beam_width)
Return: beam with highest log_prob / length_penalty

Length penalty: sequences tend to have lower log-probability as they grow (each token multiplies by a $< 1$ factor). A length penalty $\alpha$ normalizes: $\text{score}(y) = \log p(y) / |y|^\alpha$.

Advantages: finds higher-probability sequences than greedy.

Disadvantages: computationally $k\times$ more expensive; tends to produce generic, high-probability outputs that are less diverse and sometimes less useful than sampling.

Temperature scaling

Before applying softmax, divide the logits by a temperature $\tau > 0$:

• $\tau \to 0$: $p_\tau \to$ one-hot on the most probable token (greedy).
• $\tau = 1$: original model distribution.
• $\tau > 1$: flatter distribution, more diverse (but lower probability) outputs.
• $\tau \to \infty$: uniform distribution over vocabulary.

Temperature is the simplest diversity knob; typical values are 0.7-1.0 for generation tasks.

Top-k sampling

Sample from the $k$ most probable tokens, renormalized:

Top-k with $k = 1$ is greedy; $k = V$ is unrestricted sampling. A fixed $k$ ignores the shape of the probability distribution: with $k = 50$, if the model is very confident (most mass on 1-2 tokens), you still sample from 50 tokens including many near-zero probability ones.

Nucleus (top-p) sampling

Top-p sampling / nucleus sampling (Holtzman et al., 2020) adapts the cutoff to the distribution shape: keep the smallest set of tokens whose cumulative probability exceeds $p$[1]:

Sample uniformly from $\mathcal{N}_p$. When the distribution is peaked (model is confident), $|\mathcal{N}_p|$ is small. When the distribution is flat (model is uncertain), $|\mathcal{N}_p|$ is large.

Typical value: $p = 0.9$ or $p = 0.95$.

Combined in practice

Production APIs typically combine temperature + top-p (or top-k). A common recipe: temperature $\tau = 0.8$, top-p $= 0.95$ -- temperature flattens the distribution, top-p cuts off the tail.

import numpy as np

def softmax(x):
    e = np.exp(x - x.max())
    return e / e.sum()

def temperature_scale(logits, T):
    return logits / T

def top_k_filter(probs, k):
    """Zero out all but the top-k probabilities."""
    idx = np.argsort(probs)[::-1]
    mask = np.zeros_like(probs, dtype=bool)
    mask[idx[:k]] = True
    filtered = probs * mask
    return filtered / filtered.sum()

def top_p_filter(probs, p):
    """Zero out probabilities below the nucleus cutoff."""
    sorted_idx = np.argsort(probs)[::-1]
    sorted_probs = probs[sorted_idx]
    cumsum = np.cumsum(sorted_probs)
    # Keep tokens until cumulative prob >= p
    cutoff_mask = cumsum - sorted_probs < p   # include the token that crosses p
    keep = np.zeros_like(probs, dtype=bool)
    keep[sorted_idx[cutoff_mask]] = True
    filtered = probs * keep
    return filtered / filtered.sum()

def sample_token(logits, temperature=1.0, top_k=None, top_p=None, seed=None):
    rng    = np.random.default_rng(seed)
    probs  = softmax(temperature_scale(logits, temperature))
    if top_k is not None:
        probs = top_k_filter(probs, top_k)
    if top_p is not None:
        probs = top_p_filter(probs, top_p)
    return rng.choice(len(probs), p=probs)

# Demo: 10-token vocabulary, random logits
V      = 10
logits = np.array([2.0, 1.5, 0.5, 0.3, -0.5, -1.0, -1.5, -2.0, -3.0, -4.0])

print("Greedy:", logits.argmax())
print("Temp=0.5, top-p=0.9:", sample_token(logits, temperature=0.5, top_p=0.9, seed=0))
print("Temp=1.0, top-k=5:  ", sample_token(logits, temperature=1.0, top_k=5,   seed=0))
print("Probs (T=1.0):", softmax(logits).round(3))

Repetition penalty

LLMs in sampling mode often repeat phrases or whole sentences. A repetition penalty (Press et al., 2020) downscales logits of previously generated tokens:

with penalty $> 1$ (typical: 1.1-1.3). This discourages direct repetition without forbidding reuse of common words.

Min-p sampling

Min-p (Nguyen et al., 2024) is a newer alternative to top-p: instead of a fixed cumulative probability cutoff, filter out any token whose probability falls below $p_{\text{min}} \times p_{\text{top}}$ (a fraction of the top token's probability). This adapts the cutoff to both the distribution shape and the top token's confidence.

Exercises

Exercise 1. Logits over a 3-token vocabulary are $l = (2, 1, 0)$. Compute the softmax probabilities at temperature $\tau = 1$ and at $\tau = 0.5$ by hand, and confirm that lowering the temperature sharpens the distribution toward the top token.

Exercise 2. A model assigns next-token probabilities (already sorted) $p = (0.4, 0.3, 0.15, 0.1, 0.05)$. For top-p sampling with $p = 0.8$, find the nucleus set, then write the renormalized sampling probabilities over that set.

Exercise 3 (code). Implement temperature scaling and top-p filtering in numpy and verify two facts on the logits $l = (2, 1, 0)$: temperature $\tau = 0.5$ raises the top token's probability above its $\tau = 1$ value, and top-p with $p = 0.8$ keeps exactly the first three tokens of the sorted distribution in Exercise 2.

import numpy as np

def softmax(x):
    e = np.exp(x - x.max())
    return e / e.sum()

def top_p_keep(probs, p):
    order = np.argsort(probs)[::-1]
    sorted_p = probs[order]
    cumsum = np.cumsum(sorted_p)
    # include the token that crosses p: a token is kept if the mass before it < p
    keep_sorted = (cumsum - sorted_p) < p
    keep = np.zeros_like(probs, dtype=bool)
    keep[order[keep_sorted]] = True
    return keep

logits = np.array([2.0, 1.0, 0.0])
p_t1   = softmax(logits)
p_thalf = softmax(logits / 0.5)
assert p_thalf[0] > p_t1[0]                 # lower temperature sharpens the top token
assert np.isclose(p_t1[0], 0.6652, atol=1e-3)
assert np.isclose(p_thalf[0], 0.8668, atol=1e-3)

probs = np.array([0.4, 0.3, 0.15, 0.1, 0.05])
keep  = top_p_keep(probs, 0.8)
assert keep.tolist() == [True, True, True, False, False]
print(p_t1.round(3), p_thalf.round(3), keep)

The next lesson removes the dominant per-token cost of all these strategies by caching the keys and values of every token already generated.