# Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies

arXiv: https://arxiv.org/abs/2410.03968 · HTML: https://mlsanity.com/paper/2410.03968/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 4 Oct 2024.

## Builds on (most cited first, 19 of 19)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers](https://mlsanity.com/paper/2102.01454/) (2021)
- [A Contrastive Framework for Neural Text Generation](https://mlsanity.com/paper/2202.06417/) (2022)
- [Breaking the Softmax Bottleneck: A High-Rank RNN Language Model](https://mlsanity.com/paper/1711.03953/) (2017)
- [Offline RL for Natural Language Generation with Implicit Language Q Learning](https://mlsanity.com/paper/2206.11871/) (2022)
- [Unifying Human and Statistical Evaluation for Natural Language Generation](https://mlsanity.com/paper/1904.02792/) (2019)
- [If beam search is the answer, what was the question?](https://mlsanity.com/paper/2010.02650/) (2020)
- [A Thorough Examination of Decoding Methods in the Era of LLMs](https://mlsanity.com/paper/2402.06925/) (2024)
- [Locally Typical Sampling](https://mlsanity.com/paper/2202.00666/) (2022)
- [On Decoding Strategies for Neural Text Generators](https://mlsanity.com/paper/2203.15721/) (2022)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Critic-Guided Decoding for Controlled Text Generation](https://mlsanity.com/paper/2212.10938/) (2022)
- [The Consensus Game: Language Model Generation via Equilibrium Search](https://mlsanity.com/paper/2310.09139/) (2023)
- [Understanding Adversarial Training: Increasing Local Stability of Neural Nets through Robust Optimization](https://mlsanity.com/paper/1511.05432/) (2015)
- [Closing the Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/2310.01693/) (2023)

## Built on by (most cited first, 7 of 7)

- [Game Theory Meets Large Language Models: A Systematic Survey with Taxonomy and New Frontiers](https://mlsanity.com/paper/2502.09053/) (2025)
- [Foundations of Top-k Decoding For Language Models](https://mlsanity.com/paper/2505.19371/) (2025)
- [GUARD: Glocal Uncertainty-Aware Robust Decoding for Effective and Efficient Open-Ended Text Generation](https://mlsanity.com/paper/2508.20757/) (2025)
- [Incentivizing Truthful Language Models via Peer Elicitation Games](https://mlsanity.com/paper/2505.13636/) (2025)
- [Tokenized Bandit for LLM Decoding and Alignment](https://mlsanity.com/paper/2506.07276/) (2025)
- [Composable Decoding on the Probability Simplex: Theory and Implementation](https://mlsanity.com/paper/2609.34992/) (2026)
- [Truncation Samplers Are Nested: Comparing Decoding Rules Is a Measurement Problem](https://mlsanity.com/paper/2610.15570/) (2026)

## Abstract (arXiv)

Decoding strategies play a pivotal role in text generation for modern language models, yet a puzzling gap divides theory and practice. Surprisingly, strategies that should intuitively be optimal, such as Maximum a Posteriori (MAP), often perform poorly in practice. Meanwhile, popular heuristic approaches like Top-k and Nucleus sampling, which employ truncation and normalization of the conditional next-token probabilities, have achieved great empirical success but lack theoretical justifications. In this paper, we propose Decoding Game, a comprehensive theoretical framework which reimagines text generation as a two-player zero-sum game between Strategist, who seeks to produce text credible in the true distribution, and Nature, who distorts the true distribution adversarially. After discussing the decomposibility of multi-step generation, we derive the optimal strategy in closed form for one-step Decoding Game. It is shown that the adversarial Nature imposes an implicit regularization on likelihood maximization, and truncation-normalization methods are first-order approximations to the optimal strategy under this regularization. Additionally, by generalizing the objective and parameters of Decoding Game, near-optimal strategies encompass diverse methods such as greedy search, temperature scaling, and hybrids thereof. Numerical experiments are conducted to complement our theoretical analysis.