Decoding Strategies & Sampling

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Greedy Decoding
5. Beam Search
6. Temperature Scaling
7. Top-k Sampling
8. Top-p (Nucleus) Sampling
9. Repetition Penalty
10. Contrastive Decoding
11. Common Pitfalls
12. Summary
13. Exercises

Learning Objectives

1. Analyze why maximization-based decoding produces degenerate text.
2. Derive top-k and top-p truncation and their probability mass guarantees.
3. Explain temperature as an entropy controller.
4. Prove that beam search approximates MAP but not the human distribution.
5. Describe contrastive decoding and its theoretical motivation.

Notation

• $p(x_t|x_{<t})$ — next-token distribution
• $\tau$ — temperature
• $k$ — top-k cutoff
• $p_{\text{nuc}}$ — nucleus probability threshold

Core Intuition

Language models output a probability distribution over the next token. How we select from this distribution dramatically affects output quality. Counterintuitively, choosing the most probable token at each step (greedy) produces worse text than sampling from a truncated distribution. Human language is stochastic — always picking the "best" word creates repetitive, boring text.

Greedy Decoding

Problem: Produces degenerate text — repetitive loops, lack of diversity. The most probable sequence is often not the most natural (just as the most common word in English isn't what every sentence uses).

Beam Search

Maintain top-$B$ partial sequences, extend each by all tokens, keep top-$B$:

Length normalization: Divide score by $t^\alpha$ ($\alpha \approx 0.6$) to avoid favoring short sequences.

When useful: Tasks with a single correct answer (translation, summarization). NOT for open-ended generation.

Why it fails for generation: Beam search approximates the MAP sequence, but the MAP sequence of natural language is typically degenerate (short, repetitive) because probability mass is spread across many valid continuations.

Temperature Scaling

Sharpen or flatten the distribution before sampling:

• $\tau < 1$: Sharper (more deterministic, less diverse).
• $\tau = 1$: Original model distribution.
• $\tau > 1$: Flatter (more random, more diverse).
• $\tau \to 0$: Greedy decoding.
• $\tau \to \infty$: Uniform distribution.

Entropy control: $H(p_\tau) = H(p)/\tau$ approximately — temperature linearly scales entropy.

Top-k Sampling

Only sample from the $k$ most probable tokens:

Problem: Fixed $k$ doesn't adapt to distribution shape. When the model is confident (peaked distribution), $k=50$ includes many low-probability tokens (adds noise). When uncertain (flat distribution), $k=50$ may exclude reasonable tokens.

Top-p (Nucleus) Sampling

Adaptive truncation: Include the smallest set of tokens whose cumulative probability exceeds $p_{\text{nuc}}$:

Sample from $V_p$ with renormalized probabilities.

Advantage over top-k: Adapts to distribution shape:

• Peaked distribution → few tokens in nucleus (precise).
• Flat distribution → many tokens in nucleus (diverse).

Typical values: $p_{\text{nuc}} = 0.9$–$0.95$.

Repetition Penalty

Penalize tokens that have already appeared in the generated text:

where $\theta > 1$ penalizes repetition.

Frequency penalty (alternative): Subtract $\alpha \cdot \text{count}(x_t)$ from the logit. Proportional to how often the token has appeared.

Presence penalty: Binary penalty for any token that has appeared at all.

Contrastive Decoding

Idea (Li et al., 2023): Use a small "amateur" model to identify and suppress generic/boring tokens:

Intuition: Tokens scored highly by both models are generic (common phrases). Tokens scored highly by the expert but not the amateur are more distinctive and interesting.

Implementation: Expert = large model, amateur = smaller model of same family.

Common Pitfalls

Pitfall 1. Using beam search for chatbots. Beam search produces the most probable response, which is often a generic non-answer ("I'm not sure"). Sampling produces diverse, specific responses.

Pitfall 2. Setting temperature too high for factual tasks. $\tau > 1$ increases randomness — bad for math, coding, or factual QA where there's one correct answer.

Pitfall 3. Applying top-k with temperature together incorrectly. Temperature should be applied before top-k/top-p truncation (it changes the distribution shape).

Summary

• Greedy/beam search: Maximize probability → degenerate, repetitive text.
• Temperature: Controls entropy/randomness. Low for factual tasks, higher for creative.
• Top-k: Fixed number of candidates. Simple but not adaptive.
• Top-p (nucleus): Adaptive truncation based on cumulative probability. Standard choice.
• Repetition penalty: Prevents loops and repetition.
• Contrastive decoding: Expert minus amateur to encourage distinctive outputs.

Exercises

Exercise 1. For a vocabulary of 50K tokens with $p = [0.3, 0.2, 0.1, 0.05, \ldots]$: compute the nucleus set for $p_{\text{nuc}} = 0.9$.

Exercise 2. Prove that as $\tau \to 0$, temperature sampling converges to greedy decoding.

Exercise 3. Explain why the MAP sequence under an autoregressive model is often degenerate (short/repetitive), even when the model is well-calibrated.

Exercise 4. Design a decoding strategy that uses low temperature for factual claims and high temperature for creative elaboration within the same response.

Exercise 5. Compute the effective vocabulary size (number of tokens with $>0.01$ probability) before and after temperature scaling with $\tau=0.5$ and $\tau=2.0$.