Nash Equilibrium Text: A Game-Theoretic Decoding Framework for Text Generation

Text generation is conventionally defined by a decoding procedure: autoregressive models commit to tokens from left to right, whereas masked and diffusion models construct sequences iteratively. These procedures do not necessarily generate sequences in which each token has high conditional probability given the prompt and the completed context. We formulate text generation as a finite game in which token positions are players, vocabulary items are actions, and each player’s utility is the language model’s conditional probability. A sequence is a Nash equilibrium when no position can increase its conditional probability through a unilateral token replacement. We show that Nash equilibria can have exponentially higher sequence probability than autoregressive outputs as sequence length grows. We further propose Nash decoding, which monotonically increases sequence probability by repeatedly replacing the most unstable token, and prove that it reaches an $\epsilon$-Nash equilibrium in $O(\log (1/p(x^{(0)}\mid \text{prompt}))/\epsilon )$ updates, where $x^{(0)}$ is the initial sequence. Empirically, Nash decoding consistently improves generations from masked language models, yielding higher likelihood and stronger downstream performance without additional training or fine-tuning. Across the CLAPNQ, PubMedQA, and CoQA datasets, Nash decoding with BERT-family models outperforms autoregressive models up to $18\times$ larger on F1 and ROUGE metrics, at the cost of additional test-time computation.