Research map / Large language models / Language, safety and interpretability
Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Decoding Game, a zero-sum game between a Strategist and an adversarial Nature, showing that TV-bounded adversarial distortion induces an l-infinity regularization whose optimal sampler is a tail truncation-normalization rule (Game sampling), validated on open-ended GPT-2/GPT-J/Llama-2 generation.
Problem
Decoding strategies for LLM text generation: likelihood maximization (MAP, greedy, beam) performs poorly in open-ended generation, while heuristic truncation-normalization samplers (Top-k, Nucleus) work well but lack theoretical justification.
Approach
Model text generation as a two-player zero-sum game in which Nature adversarially shifts the predicted next-token distribution within a TV budget. Solving the one-step game in closed form shows the adversary induces an l-infinity regularization on log-likelihood, and the optimal Strategist distribution is a truncated distribution whose first-order approximation is tail truncation plus normalizatio
Key results
- Game sampling (epsilon=0.95, tau=2) on GPT-2 Small achieves MAUVE 0.926 with perplexity 23.59 and repetition 0.002, versus Nucleus (p=0.9) at MAUVE 0.923 and perplexity 25.12.
- On GPT-J-6B, Game sampling reaches MAUVE 0.833 vs. 0.806 for Nucleus (p=0.99) and 0.826 for BA-eta, the best MAUVE in that table.
- On Llama-2-7B, BA-eta (MAUVE 0.890) outperforms Game sampling (MAUVE 0.858), so Game sampling is not best across all models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Game sampling instead of Nucleus sampling | GPT-2 Small · WebText test | MAUVE: 0.923 -> 0.926 | Helped |
| Use Game sampling instead of Nucleus sampling | GPT-2 Medium · WebText test | MAUVE: 0.945 -> 0.945 | No clear effect |
| Use Game sampling instead of Nucleus sampling | GPT-2 Large · WebText test | MAUVE: 0.954 -> 0.947 | Hurt |
| Use Game sampling instead of Nucleus sampling | GPT-2 XL · WebText test | MAUVE: 0.955 -> 0.958 | Helped |
| Use Game sampling instead of Nucleus sampling | GPT-J-6B · WebText test | MAUVE: 0.806 -> 0.833 | Helped |
| Use Game sampling instead of BA-η | Llama-2-7B · WebText test | MAUVE: 0.890 -> 0.858 | Hurt |
| Increase τ from 1.0 to 2.0 (ablation) | Game sampling on GPT-2 Small, ε=0.95 · WebText test | MAUVE: 0.739 -> 0.926 | Helped |
| Increase τ beyond 2.0 to 4.0 (ablation) | Game sampling on GPT-2 Small, ε=0.95 · WebText test | MAUVE: 0.926 -> 0.474 | Hurt |
| Increase ε from 0.95 to 0.99 (ablation) | Game sampling on GPT-2 Small, τ=2.0 · WebText test | MAUVE: 0.926 -> 0.917 | Hurt |
Surprising findings
- Greedy and contrastive search produce highly repetitive text (repetition 0.66-0.89 for GPT-2 models) despite being likelihood maximizers.
- Game sampling is not best on every model: Nucleus is best on GPT-2 Large and BA-eta on Llama-2-7B.
Limitations
- Theory is restricted to the one-step game under TV distance; the multi-step game is handled only via a locally optimal, non-global mechanism.
- Assumption requiring epsilon below the max probability is relaxed in practice, so the empirical algorithm departs from the theory.
- Experiments are limited to open-ended generation with GPT-2 family, GPT-J-6B and Llama-2-7B, using MAUVE and perplexity.
Experimental setup
Datasets: WebText test set (GPT-2 output dataset)
Benchmarks: WebText test set open-ended generation
Metrics: perplexity repetition frequency MAUVE
Baselines: Nucleus sampling Contrastive search Typical sampling Basis-Aware sampling (BA-eta) Greedy sampling Pure sampling
Builds on: Nucleus sampling Top-k sampling temperature sampling Basis-Aware sampling
Closest papers by meaning
- The Consensus Game: Language Model Generation via Equilibrium Search (ICLR 2024 · similarity 0.90)
- Top-H Decoding: Adapting the Creativity and Coherence with Bounded Entropy in Text Generation (NeurIPS 2025 · similarity 0.88)
- Improving Open-Ended Text Generation via Adaptive Decoding (ICML 2024 · similarity 0.88)
- Closing the Curious Case of Neural Text Degeneration (ICLR 2024 · similarity 0.88)
- Model-Based Minimum Bayes Risk Decoding for Text Generation (ICML 2024 · similarity 0.88)
- Reflection-Window Decoding: Text Generation with Selective Refinement (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.