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

Text generation is typically defined by a heuristic decoding procedure, which does not ensure high conditional-likelihood text generation. We formulate generation as a finite game over token positions and define a sequence as a Nash equilibrium when no token benefits from unilateral replacement. We introduce Nash gap decoding, which repeatedly updates the most unstable token. We prove monotone probability improvement and convergence to an $\varepsilon$-equilibrium in $O\left(\log(1/p(x^{(0)}\mid\text{prompt}))/\varepsilon\right)$ updates. We further show that equilibrium sequences can have exponentially higher probability than autoregressive outputs as sequence length grows. Empirically, we show that equilibrium decoding can reach sequences with higher quality and likelihood. Furthermore, Nash gap decoding can turn masked language models into competitive zero-shot text generators, improving F1 and ROUGE on question-answering benchmarks CoQA and CLAPNQ, without any fine-tuning or retraining.