Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies
Authors: Sijin Chen
Omar Hagrass
Jason Matthew Klusowski
Venue: ICLR 2025 Poster (2025)
Keywords: decoding strategy
text generation
sampling
optimality
game theory
robust optimization
implicit regularization
sparsity
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We propose a game-theoretic framework that establishes near-optimality results for heuristic sampling strategies of text generation, offering comprehensive theory underpinning the heuristic design.

Abstract: 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.

Published as a conference paper at ICLR 2025
DECODING GAME: ON MINIMAX OPTIMALITY OF HEURISTIC TEXT GENERATION STRATEGIES
Sijin Chen' Omar Hagrass Jason M. Klusowski Princeton University, Princeton, NJ 08540, USA {chens oh2588, jason. klusowsk (eprinceton..ede
ABSTRACT
Decoding strategies play 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 Posteriori (MAP), often perform poorly in practice. Meanwhile, popular heuristic approaches like Top-k and Nucleus sampling, which employ truncation and normalization of the con- ditional next-token probabilities, have achieved great empirical success but lack theoretical justifications. In this paper, we propose Decoding Game, compre- hensive theoretical framework which reimagines text generation as a two-player zero-sum game between Strategist, who seeks 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 adver- sarial Nature imposes an implicit regularization on likelihood maximization, and comcation-normalizae
methods 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 meth- ods such as greedy search, temperature scaling, and hybrids thereof. Numerical experiments conducted complement our theoretical analysis.
INTRODUCTION
Decoding strategies underpin the mechanism of generating a text sequence from a given language model, and therefore become an essential component of modern Large Language Models (OpenAll 2024 Specifically, given autoregressive language model P which encodes the conditional next- token probability Xx(,,|X<<:) one aims generate high-quality sequence (X)...., Xr) by some strategy based on IP. Perhaps one of the most straightforward strategies is Maximum a Posteriori (MAP), looingg for the most probable sequence, i.e., the one with the maximum predicted likelihood P(Xi,..., Xr). Considering the computation cost of exact MAP, one would naturally turn to some local heuristic variants such as greedy search, beam search (Graves 2012 Sutskever et al. 2014 and contrastive search (Su al. 2022).
These deterministic searching methods based on likelihood maximization can achieve state-of-the art performance especially in closed-ended tasks, such as translation, coding, math problem solving, and summarization (Shi et al., (2024). Counter-intuitively, in open-ended text generation tasks, these strategies usually lead to low low-quality, degenerate texts, even with heavily trained tfate-of-the-an language models (Shi et al., [2024] WWiher et al., 2022 Hashimoto et al. (201)). Instead, stochastic sampling methods that randomly select the next token are observed to yield better outputs. Popular strategies include Top-k sampling (Fan et al.) 2018), Nucleus (Top-p) sampling (Holtzman et al. 2020), sampling (Hewitt et al.) (022), and Mirostat sampling (Basu et al. 2021). among others.
They follow truncation-nonnnn normalization design, namely (1) sampling the next token from a truncated distribution by removing the tail probabilities, and (2) rescaling the remaining probabilities by a normalizing constant. Some other methods like Basis-Aware sampling (Finlayson al. 2024) and
DDepartment of Electrical and Computer Engineering
I Department of Operations Research and Financial Engineering

---

Published as a conference paper at ICLR 2025
Typical sampling (Meister al. 2023 also rely on truncation but may discard high-probability tokens besides the tail; see Section 2 for details. Formally, if (fI...., Pu) is the vector of the predicted probability of all candidate next-tokens {1...., d), these methods decide an index set S and sample a token with probability
qi (ieS)
Here, different designs define the truncation set S using distinct criteria: Top-k sampling uses a fixed size threshold, Nucleus sampling uses cumulative probability mass, and entropy- based methods use information-thewne thresholds (17).
Regarding decoding strategies, there is an interesting dichotomy between theory and practice. From a statistical perspective, likelihood maximization approaches are desired to succeed by seeking or approximating the posterior mode of P. but usually underperform in practice on open-ended gener- ation tasks. On the contrary, despite their empirical superiority over likelihood maximization, the design of randomized sampling strategies remains mostly heuristic and the theory behind is poorly understood. To resolve this dichotomy, this paper aims to propose a comprehensive theoretical framework of text generation, where heuristic sampling strategies, rather than likelihood maximiza- tion, are proved to be (near-)optimal.
Now, we shall introduce the motivations behind our framework before presenting it formally.
1.1 MOTIVATION AND OUR FRAMEWORK
First thought. At first sight, statistician may naturally relate these truncation methods with the concept of sparsity and regularization, and further attempt to handcraft a constrained or penalized optimization problem where they are optimal strategies. This is easier than it may sound: for ex- ample, we can design a distance metric so that Top-k sampling is the best sparse approximation to the original distribution according to this metric, such Eo distance that directly controls sparsity. The major flaw of such approaches is that their objectives and constraints mostly come from non- principled, reverse engineering and lack statistical motivations. Therefore, they may not be able to provide theoretical insight into questions like why sparse solutions are favored, and why we should adopt specific regularization term and distance metric.
Second thought. Let us restart from the most significant observation that satihooo-mmaimizztiion approaches fail in practice. What does this imply? If TP is the true distribution of natural language, reasonable to expect that the trained language model PP is away from P. This makes P-llikelihodd an unreliable criterion of generated text, and hence leads to the failure of likelihood maximization. On the other hand, the appropriate criterion a strategy would like to maximize is the P-likelihood of generated sequence.
However, note that for generality, we restrict ourselves from assuming too many structures on the true distribution P. except for its bounded deviation from P. This "model-free" setup brings an adversarial nature to text generation: in the worst case, P can try its best to degrade the quality of our generated text within its distance budget.
Decoding Game. These ideas lead our proposal, Decoding Game, a two-player zero-sum game between Strategist (S) and Nature (N). In this game, player S chooses a (randomized) decoding strategy to generate a text sequence that, in expectation, achieves good log-likelihood in the true distribution. On the other hand, player N is always able to shift the true distribution adversarially to reduce the text quality. Knowing the decoding strategy beforehand, player N chooses the worst-case true distribution P. Formally, a Ttsp Decoding Game is represented by
max min Bg log Q (E)
Xo),
where, conditioned on a given prompt Xo. Q is the probability measure on (XI...., Xr) induced by the decoding strategy of player S. and N(P) refers to neighborhood of P. The objective of the game is the true log-likelihood of a length-T sequence generated from strategy Q, in expectation.
For player S, equivalent perspective is robust optimization (Ben-Tal Tal et al. 2009). Since player has no knowledge of P. aims to find a strategy that can work consistently well for all the possible true distributions. To achieve such robustness against adversarial distributional shift, player
2

---

Published as a conference paper at ICLR 2025
should optimize the log-likelihood in the worst case of P to ensure that its strategy does not lead to poor performance in any case, which corresponds to the minimax formulation.
If there is no adversary (P = always holds), then the game reduces to P-llikelihood maximization, and naive MAP exactly the solution. However, when an adversary is present, MAP becomes sub-optimal and the game invites more interesting consequences.
1.2 CONTRIBUTION
We conduct in-depth investigations into Decoding Game. The main results include:
Criticality of one-step Decoding Game. In Section we identify the role of one-step Decoding Game in understanding the multi-step setting. We build up a recursive structure for the multi-step game, and argue the computational intractability of obtaining global solution modern LLMs. Instead, we construct a locally optimal mechanism that involves solving one-step Decoding Game locally at each timestep, and justify its worst-case per- formance.
Optimality of heuristic strategies under implicit regularization. Under total variation (TV) distance, we provide closed-form solutions to the one-step Decoding Game for both players. Section 4.1 we show that the optimal strategy of player imposes an -type regularization on the log-likelihood. As a result, tail inncattonnnormalizaii sampling strategies emerge as first-order approximations to the optimal strategy of player S; see Section 4.2
Generalizability of the framework. In Section 4.3 we further discuss the consequences of using different objectives for Decoding Game, recovering other types strategies such as temperature-based methods. The exclusive advantage of log-likelihood, in contrast to other objectives, is also highlighted under the general framework.
Empirical evidence. Building on the general theory, in Section [ we propose Game sam- pling (Algorithm D and empirically evaluate its performance in open-ended text genera- tion with GPT-2 models. The experiments suggest that Game sampling is able to outper- form other strategies, which corroborates our optimality results. The code is available at https://gittub.ce com oma hagrass pereoodin--gare
Decoding Game provides comprehensive theoretical framework that rigorously establishes opti- mality results for heuristic sampling strategies. It largely differs from existing interpretations which, to different extents, provide some theoretical viewpoints partial justifications for their design. We will briefly review them in Section
At the same time, we believe that the statistically meaningful motivations and minimal assump- tions behind Decoding Game open up its potential for future research on decoding strategies; see discussions in Section
2 RELATED WORKS
2.1 EXISTING THEORETICAL INTERPRETATIONS
Theoretical explanations for decoding methods have been very sparse and existing works are rela- tively limited. Known perspectives presented in literature include (1) overestimation of token prob- abilities, (2) surprisal and perplexity of generated text, and (3) implicit regularization on MAP.
Following the long-held intuition (Holizman et al. 2020) that language models tend to assign exces- sive probability to the unreliable tail, Finlayson al. (2024) explained truncation as remedy for this problem, showing that it can correctly discard the tokens out of the support of the true distri- bution when overestimation is upper-bounded. They further credited overestimation to the Softmax Bottleneck (Yang et al. 2018) brought by the language model architecture, motivating new trunca- tion mechanism that may remove pioobbbbbby tokens besides the tail. However, this structural assumption may not well account for the broadness of the source of overestimation. Additionally, it unclear why rescaling all the remaining probabilities by the same constant considered the best approach after truncation.
3

---

Published as a conference paper at ICLR 2025
A similar idea of identifying the correct support has also driven prior works such as Hewitt et al. (2022) and et al. (2023). Hewitt et al. (2022) modeled the predictions as a mixture of true dis- tribution and uniform like smoothing distribution, and viewed truncation as way to desmooth the output. Meister et al. (023) proposed to compute the support that better aligns with the information- theoretic metrics of human text measured by token surprisal and entropy, under assumptions on the behavior of human speakers. In this method, high-probabilty tokens may be discarded as well.
Basu et al. (202T) theoretically derived the perplexity of various sampling methods under the statisti- cal assumption that next-token probabilities follow a Zipf distribution, comparing how the hyperpa- mameter of each method influences the order of perplexity. This particular Zipfian assumption may not fully capture the complicated probability distributions encoded by modern language models.
An earlier work (Meister et al. 2020 attempted explain heuristic methods such as beam search as an implicit regularization imposed on MAP. However, the design of regularization term seems to lack statistical motivations. They also suggest a qualitative relationship between the regularization term and the uniformity of surprisal of generated sequences, but the detailed mechanism is not well understood mathematically.
Overall, each of them motivates the design of heuristic decoding methods to a certain extent, but to the best of our knowledge, we are not aware of any comprehensive theoretical framework that establishes optimality results.
2.2 TEXT GENERATION AS DECISION MAKING
Another line of work, though not directly working on the theory of heuristic decoding schemes, views the problem of text generation as optimizing the policy of preiisinnmmking agent working in an environment with or without adversary. This perspective resonates with our rationale behind the Decoding Game. For example, Jacob et al. (2024) proposed a game between a generation strategy and text quality discriminator, and empirically demonstrated the advantage of the decoding strategy at the Nash equilibrium of this game multiple tasks. Other recent works such as [nell et al. (2023);
Kim al. (2023); Mudgal et al. (2024) modeled next-token generation as (token-level) Markov decision processes, and applied reinforcement learning techniques for controlled decoding.
2.3 ROBUST OPTIMIZATION AND REGULARIZATION
Our framework also draws a connection to robust optimization (Ben- Tal et al. 2009). which aims to find solutions with stable performance under data uncertainty perturbations. Given the adversarial nature of uncertainty, robust optimization is typically formulated as a minimax problem that seek the best response to the worst-case data realizations. Interestingly, while the sparsity brought by truncation sampling can be seen as regularization, it is known that regularization and robustness strongly correlated in various machine learning problems (Derman al. 202T Shaham al., 2018 Bertsimas et al. 2)11), as solving an optimization problem with regularization is equivalent solving its non-regularized robust counterpart. For instance, lasso and ridge optimization can be reformulated as robust optimization problems, where the data matrix is subject to different types of perturbations: ridge regression corresponds Frobenius norm- bounded perturbations while lasso corresponds to column- wise fy-norm bounded perturbations (Shaham et al., 2018). The theory developed this paper also confirms such an equivalence between robustness and regularization.
FORMULATION
3.1 NOTATIONS
Throughout, we boldface letters represent vectors and vector-valued mappings, and use blackboard bold letters to represent probability measures and expectations. For a sequence (a),..., ad), ais
(ro, $1,.21...... ..... ,T), we define d (ai,..., a:) is the vector extracting its first i components. The l, norm (p 2 1) of a is defined ||al,, (EL la,l))//p, with fx norm ||a]|oo maxiga layl. The total variation (TV) dis- tance between two probability vectors is defined as drv (p. q) = llp -qll-- For a function TR. R. s(a represents the elementwise application of to the vector a, and a/b represents
(ro....,44-1). For a vector
4

---

Published as a conference paper at ICLR 2025
the elementwise division of a by b. For finite set V. A(V) denotes the probability simplex of dimension [V]. and V denotes the Cartesian product x x (t times). We always assume that optimization variables have to satisfy probability constraints (e.g.. lying in the probability simplex, or the space of probability measures), and will not specify them explicitly for conciseness.
3.2 DECODING GAME
We describe the T-step Decoding Game in full detail. Suppose V (1,2,.., d} is the vocab- ulary of all d tokens, and the natural language follows a true distribution I.. Upon training, we obtain language model IP that approximates the true P.. Beginning with prescribed context Xo = (prompt, (BOS)), ) we generate a sequence (X [X....., XT) with a possibly randomized de- coding strategy, which is represented by another measure such that next tokens selected with probability Q(x, Xxt). We can then evaluate the quality of the generated sequence by testing whether the true distribution IP is also likely yield such a sequence. Specifically, for typical sequence generated from Q we use its log-likelihood in P-mmasure as the criterion
(Q, Eq log P(X XT Xo):
which is also the negative eross-yntropy between Q and P when viewed as distributions VT
The T-step Decoding Game is a two-player zero-sum game on this criterion between Strategist (S) and Nature (N), where player S chooses Q (by choosing decoding strategy) maximize the criterion of the generation, while player N chooses within neighborhood of IP minimize it. This gives rise to the following formulation:
max min PEN(P)
C²) = max min Eq log Q PEN(P)
XT Xo).
(MDG)
In other words, without knowing IP specifically, player S seeks strategy optimize the objective L in the worst case among (TP).
As starting point of further understanding of the multi-steg step game, we build up a picture at = 1. In this case, the probability measure IP is represented by a d-dimensional probability vector p E AVV), where P(X, Xo). Similarly, the one-step strategy Q is represented by q A(V). We use TV distance define the neighborhood N(p) = (p drv (p. S <), leading to the one-step Decoding Game
max min CQ) = max min Q PEN(P)
q logp.
(ODG)
PEN(P)
Our theoretical analysis in Section will be mainly devoted to the one-step setting ODG). Before that, we shall still take deeper look into the general (MDG) and justify why the one-step game is representative case that captures the essence the general setting.
3.3 REDUCTION FROM MULTIPLE STEPS
In the multi-step setting, given context T'ee D4-1 probability measure F computes the condi- tional next-token distribution P( xee)). Similar to one-step setting, such a next-token distribution corresponds to d-dimensional probability vector (I E A(V). We define the neighborhood in (DG) as
(P) drv drv(p Se, Va E V and ST).
which, as an extension from the one-step case, controls the dissimilarity between any pairs of con- ditional next-token distribution in TV distance!!
Then, we can recast MDG as
max min Bq log P(X,, Xy Xo) max min Q (P
Eg log PXX, X
PP)
It can also be interpreted as the e-ball of the TV-sup distance d(P. P max ( ). (x Jet E V < T}. which is half of the (1, 2o) mixed norm (Hom & Johnson 1985) of the matrix concate- nating all the conditional distributions difference (x(we))) (P(e))) its columns.
5

---

Published as a conference paper at ICLR 2025
T
max min Q PEN())
E Ex Bxcraelxx--xxxxxxl00 Xx))
max min Q PEN(P)
R Exarold((Xe) (Xg
t=1
max
Excen
min (x(
qo ge To po
Here, ①1 uses the fact that the minimization problem is inherently separable in each next-token distributions (x))
Directly solving (MDG) or is computationally intractable. Theoretically, one can exploit the recursive structure in ① and apply dynamic programming. but the scale of the problem grows as (dd"). and such an approach would take poly(d") time. Considering the computational cost of working on modern LLM, in this paper we turn local solutions that do not probe into the global structure of the problem. It is given by locally optimal mechanism
Te (x = argmax qu (Ze))
min Pi N(
qe ( log pi (T<+)) Vzec E V--1,
(2)
thus going back to (DG)). In addition to significantly alleviating the computational cost, it turns that such local mechanism also provides the optimal worst-case performance over all decision processes that do not exploit future information of P. We state this result formally next.
Definition 3.1. We say a strategy Q Q(P) has foresight ffr any S T. we have qi (P) (1(ess P') for any P and TP' satisfying (r(ee)) p', (x<x) Vs S
Assumption 3.2. e < (f all S T and xet E Vt-1
Proposition 3.3. Given arbitrary P from the space of probability measures on VT, Q = Q(P) be any strategy with no foresight. Moreover, let F = P (IP, Q) be the optimal strategy of player N against Q. If Assumption 3.2 holds and Q (P) is the strategy induced by Q then
inf L ( inf L (Q.P")
F
P
Here, we make Assumption 3.2 so that the optimal value the game is always well-defined, by staying away from -c. Proposition 3.3 provides worst-case justifications for optimizing the im- minent one-step reward of the game at each timestep t. In what follows, we will be devoted to the one-step game (ODG) for theoretical analysis.
4 THEORETICAL ANALYSIS
In this section, study the optimal strategies for both and q in (ODG). We will show that the optimal imposes an -type regularization on the log-likelihood, and the optimal p solving the regularized maximization yields tail muncation-normalizttioo sampling methods. Finally, tend our analysis from log-likelihood to a general type of objectives, which recovers other heuristic methods and also highlights an exclusive advantage of lig-likelihood.
For ODG we make the following assumptions.
Assumption 4.1. The probabilities are strictly positive and, without loss of generality, sorted in decreasing order, i.e., Pi 2 P2 2 Z Pa > O.
Assumption 4.2. The distance budget satisfies pa S E < P1.
4.1 P-STRATEGY: IMPLICIT REGULARIZATION
For given q, have the following characterization for the optimal strategy of p.

---

Published as a conference paper at ICLR 2025
Theorem 4.3. Under Assumption 4.1 and 4.2 let i max > c}. Define i IR' elementwise
by Wn log bog=e/()=-e) Then, for a given q, the optimal foror (ODG) satisfies
q log p 11 100
ifq: 0, Vi > i;
q log p=
min podr(pp-PSe
q logp
-00,
otherwise.
We give several remarks Theorem
4.3
Tail truncation. Due to the fact that limæyo log(2) -oo, any q possessing a non-zero tail in the index set {i : P. e} will lead to -oo objective value, because setting the corresponding p: to zero is within the reach of the adversary. This implies a hard truncation constraint qi = vi 2 i, namely the optimal must come without such tail. However, more components can be additionally truncated the maximization part, due to the foo regularization effect we derived.
Tackling non-convexity. The minimization problem in p is non-convex, because has concave objective. Therefore, is inherently hard to characterize the structures of the optimal p: it may not even be unique. However, under TV distance, the geometry of the feasible region polytope. This benefits our analysis because the minimum is known to be attained at the vertices (Horst) restrictnng the candidate solutions within finite set. Switching other dissimilarity metries than TV distance, such as KL divergence, would change the geometry and require very different techniques, which left for future work.
Implicit regularization. With optimal P. the remaining part of the game is regularized log- likelihood maximization in terms q:
max q log P c //q1:a///lll q
91 0, Vi
with an -type regularization term |/ fil/ Note that we have ib = Pi:s by applying first- order approximation the function log(1 r). no adversary is present (c 0). there is no regularization effect and trivially, greedy sampling solves the one-step log-likelihood maximization. This establishes an equivalence between regularization and robustness against an adversary, which has been observed in the robust optimization literature; see Section 2.3
4.2 S-STRATEGY: HEURISTIC SAMPLING METHODS
Now we present the optimal solution to the regularized maximization problem.
Theorem 4.4. Under Assumption 4.1 and 4.2 let maxfi p. e). and w; (og(p.(l;-0)) for all < i. Define the threshold
i= max
I
d log(d./ S Do >
Then, the optimal q for (DG is given elementwise by
qi (
Corollary 4.5. By first-order approximation, w; Rs pr, and hence q x ps (isisty where
i= max {1 I: T: p. log(p./0r) S Pr DI>E
{
I-1
i=1
Thus, up to first-order approximation, tail cmunaatinnnoormaliaati sampling strategy optimal.
Clearly, Theorem 4.4 describes a sampling strategy that truncates tail probabilities and keeps only the subset (1..... } as the support. Note that I < i always holds. The new distribution on the support f not a simple rescaling of the original weights Pi:j by normalization constant, which is different from past heuristic designs. However, according to Corollary 4.5 rescaling emerges as a first-order approximation to the optimal strategy.
Under first-order approximation, the truncation threshold of q has an information-theoreii inter- pretation. Note that if belongs the support {1...., Î), then Σ[=1 p, loggl./ppp) S which is equivalent to
log(1/ H(p:.11) Cr,
7

---

Published as a conference paper at ICLR 2025
where (PL:1-1) is the entropy of P1:1-1, and C₁ log (1/ p.) P.)
for large
7 Thus, when constructing the support, for large I, grow the existing support {I,.... 1) by adding / if its self-information (surprisal) log(1/fr) is small compared to the existing entropy plus small amount. In other words, this token selection mechanism modulates the total number of surprisals.
Notably, this truncation threshold different from previous truncation-based methods like Nucleus sampling. However, one can still recover these strategies, say Nucleus sampling, by setting an appropriate that depends on p. the hyperparameter of Nucleus sampling, and also the distribution P::- This involves an adaptive that changes at every decoding step.
4.3 GENERALIZATION FROM LOG-L.KKELTHOOD
Beyond the log-likelinee ligeliieiihod, our analysis can be extended to games with more general objectives, taking the form
min q f(p),
(f-ODG)
4 p-d (p.
where f: + IR is applied elementwise on We assume the following for (-ODG). Assumption 4.6. f non-decreasing and concave. Moreover, (f, satisfies either of the following conditions:
(i) Pa << pr, and lim=10 f() -0;;
(ii) 0 < < < Pa. and Di=1 f(A
1.
Clearly, our previous log-likelihood game (DG), which uses f(x) log(zr), satisfies part (i) of this assumption. The following result establishes the solution to the general game f-ODG), and encompasses Theorem special case.
Theorem 4.7. Under Assumption
4. and 4.6 lel
T-1 S = Σ
f(p)) - f(pr)
f(p:) -f(p:- -c
1=1
and define the threshold Í max (1 S1 1, P1 c). Then, the optimal for f-ODG) is given elementwise by
f(p.) - (p: losishy-
(3)
Corollary 4.8. Suppose f is also differentiable. By first-order approximation on f. we have q o T(0: (usisly where
f(p.) f(p.)- f(pr) S Dr D 1 f'(p:)
i max I
There are two interesting consequences this general result.
Exclusive advantage of log. Log-likelihood is the only objective that makes it optimal to rescale the remaining probabilities by a normalization constant. This is because enforeing T(a) a in Corollary 4.8 leads to fæx (o)(z) (up to constant). Therefore, there is an exclusive connection between log likelihood and rescaling.
Temperature scaling, Second, since rescaling is not necessarily optimal, it is worth understanding how we treat the remaining probabilities under another f. One example f(x) 1-1/ 1/--1
where
p. 1/T hence recovering temperature sampling (Hinton 2015) where the temperature is controlled by т. This shows the general game F-ODG
# Taking the derivative, we have -(P exp p
able express a variety sampling strategies.
Note that min(d, 1/6] <. E1 d: S 111 by Assumption 4.1 and the fact that P. 2 pz > c for all
Note that lim 1-1/7
21-1/r-1 log
8

---

Published as a conference paper at ICLR 2025
5 EXPERIMENTS
Building on the truncation and normalization mechanism given in the general theory, we propose Game sampling as outlined in Algorithm [ and empirically evaluate performance text gen- eration. Regarding the algorithm design, the objectives to our concern are f(z) = ='-1/r-1 1-177 and
fæ) log(z), as a special case of 1. For better practical results, we relax the restrictions on the value of e in Assumption 4.6
Algorithm 1 Game sampling
Input: 0 < e 2 1, and r >
if r then
> log-likelihood objective
compute S = Di=1 Pr log(p./01)
find = max [1: S1 c}
set 9, pill
else 7 + then
D temperature sampling objective
compute 5₁ = (1-1/T) - Pe (i:/pr))-11/))
find = [I S1
set 9: p. (1Sish)
end if
normalize q:: qs - q Σラ=1
sample the next word based on the distribution q
We conduct an open-ended text generation task using web text from the GPT-2 output dataset. For each of the 5,000 articles in the Webtext test set, we use the first 35 tokens as prompts, with maximum generation length of 256 tokens. For each type of GPT-2 model (Small, Medium. Large, XL) [Radford et al. 2019), GPT-J-6B (Wang & Komatsuzaki 2021 and Llama-2-7B (Tourron
al.
2023). we evaluate the following metries:
1. Perplexity: The perplexity of the generated text under the corresponding model.
2. Repetition frequency: The fraction of generations with repetitions. A generation con- sidered repetitive if it contains at least two contiguous copies of the same phrase, of any length, at the token level.
3. MAUVE score (Pillutla et al., 2021 for comparison with human-written text, we use the corresponding human continuations from the test set, up maximum of 256 tokens.
good performance is characterized by high MAUVE score and close-to-human perplexity and repetition.
We compare seven decoding strategies: the proposed Game sampling (Algorithm) D. Nucleus sam- pling (Holtzman al., (2200), Contrastive search (Su al. 2022), Typical sampling (Meister al.)
2023). Basis-Aware sampling (BA-1)) (Finlayson et al. 2024). Greedy sampling (using argmax, P.), and Pure sampling (sampling with probability pz). We use the best-performing hyperparameters for each strategy as determined by the MAUVE score.
Game sampling achieves the best performance in GPT-J-6B, GPT-2 XL, Medium, and Small models, and scores the second highest in GPT-2 Large and Llama-2-7B models, next Nucleus sampling and BA-7 respec- tively. We remark that BA-rj involves matrix decomposition and operates higher computation cost compared to our method.
The results are presented in Table with more detailed breakdown in Appendix B
We also experiment with different values of and r, with details in Appendix B In general, larger values of e tend to produce better results in terms of higher MAUVE score, lower repetition fre- quency, and human-level perplexity. Smaller values reduce perplexity, but at the expense of more repetitions and lower MAUVE scores. terms т, the best performance for each e choice was achieved at 2, yielding the highest MAUVE score. Similar to c, smaller values tend duce perplexity, but produce more repetitions with lower MAUVE scores. MAUVE score begins to decline when exceeds 2.

---

Published as a conference paper at ICLR 2025
Mothod
Perplexity
Repetition
MAUVE
Method
Perplexity
Repetition
MAUVE
Game 0.95, F 2)
23,590
0.002
(e 0.95
0.945
Nucleus = 0.9)
25.116
0.004
0,923
Nucleus (p 0.9)
19.221
0.002
0.945
Contrastive (ar 0.6)
2.267
0.835
0.035
Contrastive (a 0.6)
2.431
0.677
0.049
Typical (p 0.9)
10.785
0,019
0.888
Typical 0.9)
9.018
0.010
0,923
BA-q (q 0.0001)
29.610
0.002
0.917
BA-n (1 = 0.0001)
24.119
0.0006
0.933
Greedy
2.163
0.886
0.0155
Greedy
2.247
0.808
0.029
Pure
62.001
0.0002
0.845
Pure
48.553
0.0004
0.848
Human
21.559
0.002
Human
15.923
0.002
GPT-2 Small
GPT-2 Medium
Method
Perplexily
Repetition
MAUVE
Method
Porplexity
Repetition
MAUVE
Game
2.5)
15,458
Game (e 0.99,
11.33
0.003
0.958
Naclous (p = 0.90)
13.699
0.002
0.954
Nucleus (p 0.93)
14,589
0.003
0.955
Contrastive
Contrastive (a: 0.6)
5.235
0.006
0.912
Typical (p = 0.9)
6,590
0.012
0.924
Typical (p 0.9)
7.342
BA-9 (1- 0.0001)
15.223
0.0008
0,954
BA-7 0.0001)
13.495
0.001
0.946
Greody
2,169
0,760
0.039
Greedy
2.411
0.672
0.065
Pure
21.952
0.0008
0.931
Pure
23.505
0.0004
0,942
Human
13.755
0,002
Human
12.319
0.002
GPT-2 Large
GPT-2 XL
Method
Perplexity
Repetition
MAUVE
Method
Perplexity
Repetition
MAUVE
Game (c 0.90,
2.5)
19:729
0.002
0.833
Game 0.95,
1.5)
14.000
0.128
0.858
Nucleus (p 0.99)
23.149
0.002
0.806
Nucleus (p = 0.95)
31.125
0.154
0.853
Contrastive (a 0.6)
6.573
0.007
0.715
Contrustive
0.6)
5.375
0.236
0.702
Typical (p = 0.9)
8.747
0.016
0.769
Typical (p = 0.9)
5.156
0,209
0.719
BA-q (y 0.0001)
12:307
0.002
0.826
BA-q 0.0001)
8.375
0,002
0.890
Greedy
2.603
0.731
0.043
Greedy
3.109
0.457
0.537
Pure
27.327
0.001
0.798
Pure
44,500
0.016
0,813
Human
9.950
0.002
Human
6.469
0.002
GPT-J-6B
Llama-2-4 2-7B
Table 1: Evaluations on open- open-ended text generation with different decoding strategies. Boldface values indicate the highest MAUVE score and the closest-to-humat perplexity and repetition. The best-performing hyperpa- rameters are selected for each strategy.
6 CONCLUSION
In this paper, we proposed Decoding Game, a two-player zero-sum game where Strategist aims to maximize the log-likelihood of the generated text under the true probability measure, while an adversarial Nature seeks to distort the true measure within an c-error budget to degrade the text. After discussing the decomposibility of multi-step generation, for both players of the typical one-step Decoding Game. We proved that, as Nature enforces its optimal strategy, imposes -type regularization on the log-likelihood maximization problem. By solving this regularized maximization in closed form, we identified tail truncation rimcatiionnormalizatiin sampling as first-order approximation the optimal strategy.
studied the optimal strategies
We also generalized our theory from log-likelihood to a broader class of objectives. In deriving the general solution, we observed that log-likelihood is the only objective that makes optimal rescale the remaining probabilities by normalizing constant. Selecting other types of objectives leads to different ways of treating the remaining probabilities, including temperature sampling. Moreover, we empirically evaluated the performance of Game sampling, a sampling strategy built upon the general theory, open-ended text generation.
We believe that Decoding Game provides comprehensive theoretical understanding for the heuristic design of sampling strategies, by rigorously establishing regularization effect and optimality results. The statistically meaningful motivation and minimal assumptions behind Decoding Game open up its potential for future research, both theoretical and practical, on text generation strategies. For ex- ample, it would be interesting generalize the metric beyond TV distance. Also, our formulation of the multi-step game shares similarities with token-level Markov decision processes, and efficiently tackling multi-step strategy via reinforcement learning would be another direction.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLED
We extend our special thanks to the anonymous reviewers for their insightful comments and sugges- tions that greatly enhanced this work. We are also grateful Danqi Chen for helpful discussions. Klusowski acknowledges financial support from the National Science Foundation through CAREER DMS-2239448.
REFERENCES
Charalambos D. Aliprantis and Kim Border. Infinite dimensional analysis: a hitchhiker's guide. Springer, Berlin, 2006.
Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, and Lav R. Varsh- ney. Mirostat: A neural text decoding algorithm that directly controls perplexity. In International Conference Learning Representations, 2021.
ntt/ wtw.:/reeeieeeeeoorunntt forum?
Aharon Ben-Tal, Arkadi Nemirovski, and Laurent El Ghaoui, Robust optimization. 2009.
Dimitris Bertsimas, David B. Brown, and Constantine Caramanis. Theory and applications of robust
optimization. SIAM Review, 53(3):664-51, 2011. doi: 10.11377080734510. URL https:
7/doi. orrli.org//0 10. 01110011111700731110
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
URL https::/p//... /twe:://wwbb... www.we....a....... ford. wdw. bboyd/ cvxbook/)
Esther Derman, Matthieu Geist, and Shie Mannor. Twice regularized mdps and the M. Ranzato, Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.). Advances in Neural In-
equivalence between robustness and regularization.
formation Processing Systems, volume 34, pp. 22274-22287 Curran Associates, Inc.,
2021. URL httpss://proeeeeding...ot neurips....e............. cttpssccccppppp..ppe fi files/paper/2021/ htll://o.eecccca113967777782ee8 Papeeei.11--PPppeppppppp
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Iryna Gurevych and Yusuke Miyao (eds.), Proceedings of the 56th Annual Meeting of the Associa- tion for Computational Linguistics (Volume 1: Long Papers), pp. 889-898, Melbourne, Aus- tralia, July 2018. Association for Computational Linguistics. doi: 10.18653/w1/P18-11 1082. URL
Matthew Finlayson, John Hewitt, Alexander Koller, Swabha Swayamdipta, and Ashish Sabhar- wal. Closing the curious case of neural text degeneration. In The Twelfth International Confer- Learning Representations, 2024. URL https::/opeerevieeeeeee// net het/forurmfdd
dONpC9GL10
Alex Graves. Sequence transduction with recurrent neural networks, 2012. //arxiv.oro org/ http//al////1111////
URL
https:
Godfrey Harold Hardy, John Edensor Littlewood, and George Pólya. Inequalities. University Press, 1952.
Cambridge
Tatsunori B. Hashimoto, Hugh Zhang, and Percy Liang. Unifying human and statistical evalua- tion for natural language generation. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 1689-1701, Minneapolis, Minnesota, June 2019, Association for Computational Linguistics. doi: 10. 1/N19-1 1169,
hnthh Logy otg/No9- 1169
John Hewitr, Christopher D. Manning, and Percy Liang. Truncation sampling as language model desmoothing, 2022. WRRLlattss//aaaet org/ abs aabs/2210.. 15191
Geoffrey Hinton. Distilling the knowledge in a neural network. arXiv preprint arXiv: arXiv:1503.00 150..0253,, 2015.
11

---

Published as a conference paper at ICLR 2025
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL https: /oopnneeiiiweec.cmoooeeoe
/
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 1985.
Reiner Horst. On the global minimization of concave functions. Opervatons-Reseercchspeeeere
(44):195-005, 1984.
doi: 10.1007/BFO11220068 URL https: htttsss//6el.orr/10...00
BFC1720062
Athul Paul Jacob, Yikang Shen, Gabriele Farina, and Jacob Andreas. The consensus game:
Language model generation via equilibrium search. In The Twelfth International Confer- ence on Learning Representations, 2024. URL https:/ http:s/////pereeeew.weeee wtt.:/wwwwweeeeouuid.......
n9xeGcI4Yg
Minbcom Kim, Hwanhee Lee, Kang Min Yoo, Joonsuk Park, Hwaran Lee, and Kyomin Jung. Critic- guided decoding for controlled text generation. In Anna Rogers, Jordan Boyd Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp. 4598- 4612, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. v1/2023. finn233.indigg-acl.22... URL https: http:///aaaaataltaaaa/ee wwwpathhoooo..or/2222233333 org/ findings acl. 281
Clara Meister, Ryan Cotterell, and Tim Vieira. If beam search is the answer, what the question? In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.). Proceedings of the 2020 Confer- ence on Empirical Methods in Natural Language Processing (EMNLP), pp. 2173-2185, Online, November 2020. Association for Computational Linguistics. doi: 011116653/112222.emmm/ main. 170. URL https::/aclantholloootooo org wtw.://mommmmmmmmaaa............
emnlp-main.
Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. Locally typical sampling. Trans- actions of the Association for Computational Lingnistics, 11:102-121, 2023. doi: 10.1162/ tacl_a005536.
Sidharth Mudgal, Jong Lee, Harish Ganapathy, YaGuang Li, Tao Wang, Yanping Huang, Zhifeng Chen, Heng-Tze Cheng, Michael Collins, Trevor Strohman, Jilin Chen, Alex Beutel, and Ahmad Beirami. Controlled decoding from language models, 2024. URL httpss://arx: org/
abs//310. 17022
OpenAI. Gpt-4 technical report, 2024.
Krishna Pillutla, Swabha Swayamdipta, Rowan Zellers, John Thickstun, Sean Welleck, Yejin Choi, and Zaid Harchaoui. Mauve: Measuring the gap between neural text and human text using diver- gence frontiers. In NeurlPS, 2021.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 188):9 2019.
Ralph Tyrell Rockafellar.
Conver Analysis. Princeton University Press, Princeton, 1970. ISBN
9781400873173. doi: 97814008731
URI. https://doo wrg//0..... 1515/
Uri Shaham, Yutaro Yamada, and Sahand Negahban. Understanding adversarial training: Increasing local stability of supervised models through robust optimization. Neurocomputing, 307:195-204 September 2018. ISSN 0925-2312. doi: 10. 10110006/...ee heucom.2008.044. URL. hhtpp://xx.
doi org..rrg/10 /0. 101 1016/1111111 nww.we.ec..m.mmm 2018 04. 027
Chufan Shi, Haoran Yang. Deng Cai. Zhisong Zhang, Yifan Wang. Yujiu Yang. and Wai Lam. A thorough examination of decoding methods in the era of lims, 2024. URL https:tt/////... //arxiv.
brg/abs/24022 06925
Charlie Victor Snell, Ilya Kostrikov, Yi Su, Sherry Yang, and Sergey Levine. Offline RL for natural language generation with implicit language q learning. In The Eleventh International Conference on Learning Representations, 2023. URL httttt:::///opeet /wwp//weeeweeeccoooo/o /tt/ www.fooommiaaaarr..
DydEvoH
12

---

Published as a conference paper at ICLR 2025
Yixuan Su, Tian Lan, Yan Wang, Dani Yogatama, Lingpeng Kong, and Nigel Collier. A trastive framework for neural text generation. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:
ptttss://ppereeviiee net forum? d= FMH
Ilya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence to sequence learning with neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27, Curran Associates, Inc., 2014. URL.
nww. www.://ggnnnnss.sneeec...... cc/paper #fles/paperr/014 fi alle/aaa 2ecea44ccc5554447772285888842223
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshom, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023. URL
Ben Wang and Aran Komatsuzaki. GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model. https: httt:s:://gituubb..om//////
ol
jax May 2021.
Gian Wiher, Clara Meister, and Ryan Cotterell. On decoding strategies for neural text generators. Transactions of the Association for Computational Linguistics, 10:997-1012, 2022.
Zhilin Yang, Zihang Dai, Ruslan Salakhutdinov, and William W. Cohen. Breaking the softmax bottleneck: A high-rank RNN language model. In International Conference on Learning Repre- sentations, 2018. URL https: / /tttpp::/epperevveew net Forum? 1d=HkW25G-C2
13

---

Published as a conference paper at ICLR 2025
A PROOFS
A. PROOF OF PROPOSITION 3.3
For probability vectors P. E A(V), define M(q. p) (() q logp, and M(p) max, (i)) q" logp. Then, the t-step total rewards of no-foresight strategy ((P) and locally optimal strategy (IP) are respectively given by
P(QP),
E c.. 2
((Q(P), P' (P. Q))
Σ
E Ex..
RP)
Since < ma M(p) is always bounded from below. Moreover, as the set-valued mapping P + (p) satisfies upper and lower hemicontinuity and N(p) is compact, M is continuous in p by Berge's Maximum Theorem (Aliprantis & Border] (006), which further implies the continuity of Rs. Since the space of IP is compact, conclude that infimum of R' can be attained at some P-, namely inf R' (IP) R'(P*)
Now, if q: (x<eiip))) = (((x<tiPt) Vt, we are done. Otherwise, let to be the first step such that Iso (#<1oi PP)) & ( ( IP)). We have
t0
t--1 x M(x
E x 2/ Ma) 2ff
E Ex Q(F IM (X <to) 1.0. Pio (Xcto)) S E
(X Pi (X (X
which implies RA (PP)P), Fr) S R2 (f²*). Consider Tir defined as follows. For each des E V8-1
p (x)))) = p: (x<x))
$ to
to- In words, P.. can be understood as shifting the future structure of f after to. Since the strategy Q(P) is defined to have no foresight, we have qa (x ()=*)== = Q (Z PPt) for s S lo. Hence,
(2r2a) where x²c, argmingev (()))
R. (Q(P)) (T*) < R (P
(4)
holds well.
Due to our construction of fort the future rewards after la satisfy
Σ E Mx
max EV=
s0o+1
s=to+1
p:"
RerEVe-
8=
T
(Xx)) p.(2.))))
X
11
namely
Rº. (Q(P))) - ( p S R2 (P - PP))
(5)
With and ()) we conclude that
inf PR ( S Rd (P' = inf Rタ (P),
which proves the result.
14

---

Published as a conference paper at ICLR 2025
A.2 PROOF OF THEOREM 4.7
We shall only prove the general theorem, as Theorem 4.3 and 4.4 are direct consequences.
Consider the minimization problem
min q fp),
(6)
PEN(P)
where N(p) - {p E A(V) drv(p, Et..
The feasible region N(p) is convex polytope since it is the intersection of two convex polytopes- the probability simplex A(V) and the e-TV-distance ball {p |lp p S e). Moreover, due to concavity of f. it is easy to show that q fp) is concave in p. It is well-known that minimizers of a concave function over a polytope are attained one of the vertices (Horst) 1984). Now, we let 2/ be the set of the vertices of N (p).
We will consider the two cases of the theorem separately, due to their differences in the geometry of the feasibility.
Case 1: e < pa, and 2i=1 1
d-1 f(a.) ((x)-1(p1)) f(pate)
2
Since < pa; the set U can be written U (pp ce; =ej i j}. Hence, have
min q' f(p) = min q (p) PEN(P)
pell
9 f(Ø) + min {a (f(): E) - -((.)) (f(Ø; + ((1,))
f()) max {9.9 (fr) 4,9 (p.)
where g (x) f(x) f(x - c), and g (x) f(x + t) ((x). Taking this result into our game,
the remaining q g-maximization part is equivalent to
q f()) + max {49 (f.) 9,9 ()-+((a))) (A:) min (E
Ordering of the optimal solution. We claim that any optimal q² has ordered elements, with of 2 2 zh- Observe that both g and 9 are non-increasing, since f is a concave and non-decreasing function. Therefore, if q has unordered elements, we can rearrange its elements it in descending order, and rearrangement inequality (Hardy et al. 1952) implics that that the term -q f(p) will decrease. Morcover, by reordering, the term max, juzj (4.9 (f.) 4,9 (p.)) will also decrease. This is because
max {9.g (f.) 9:9 (6,)) max 4.9 (p.) ffj
min 4₁9 (i:)
jーfi
max
max 0:9 (p.) 41g - (i:) 1:1f)
Thus, for any fixed we reorder the rest of the elements, min 9;9" (Φ²) will increase, making the entire term smaller. Further, by fixing j and reordering by placing di in the correct position, maxi4j 4.9 (fx) will decrease. total, rearranging q in descending order will decrease both terms, resulting in lower overall objective.
Analyzing KKT optimality. Introducing dual variables X E R4, E I, the Lagrangian of given by
7 is
d L(q,A,v) == =- f(p) + max {9. (p:) ( (D,)) X q ΣΦ q: -1-11 Lgji
One can check that the objective in is convex in q. Moreover, since there exists q E relint A (V)) with q > O, strong duality holds. Therefore, q" is optimal if and only if there exists X 1² such that the following Karush- Kuhn- Tucker (KKT) conditions are satisfied (Boyd & Vandenberghe 2004))
0 E E-((p) +
max (1ig (fx) - G9 (8g((,,)) X + +11, (.jtt)
(first-order stationarity)
15

---

Published as a conference paper at ICLR 2025
q" E (V), X 2x20 0, \ = 0 Vi,
(primal-dual feasibility) (complementary slackness)
where the subdifferential 0 (Rockafellar 1970) of the nonsmooth function inside represents the convex hull of the subgradients of the maximizing coordinates, given by
max (9/9 (f:) 939 (f,)) conv (D),
D = {o - : i 49 (f.) (p.) 9j (p,)
= max {9r (f:) ([gg((,)) (Øシサ)
Now we show that q" defined by of- = ش (isigr) satisfies KKT conditions for some dual variables X², v", where is normalizing constant. Let
J = (i: 14 (0:) = c) = 11 (1
N = fi g = 0} = (1" <isd..
Then, as Sy non-decreasing in we have
f(px) f(p.)
1 Vie J,
(8)
g (fx)
and
f(ps) f(be) g (Px)
1, Vie
Moreover, since
f(x)) - f(ba) Sa g- (px)
f((x) f(ps + g (px)
2 1,
know that 1 d must hold, and W is always non-empty.
To show that KKT conditions are satisfied, it is equivalent to prove that there exist v², X 2 0 with A 0 for E J, and coefficients "ij for (i,j) E N with EiET EjeN Vi such that
-f(b)) - (p:)
Σn no JEN
I(iEn) - g
Σ NET
7/8
L(iEN) 1 +v² = 0,
which is equivalent to
-f(p) + g((6))
Σ vi
+ v² = 0, iEJ,
(10)
JEN
-f(e)) - (Px)
Σ Pis
+ 23 2020, iEN.
(11)
JEJ
The above linear system is satisfied for
f(Dx)
5¹ Σ
(ix)) -1) 1
KEJ 9- (px)
KEJ
f(b)) 1/¹
9 (p:) ((j=))
A (-f( g (pa) (i=d) v²) (
16

---

Published as a conference paper at ICLR 2025
Moreover, 8 and (9) respectively imply that Mij 2 and X 2 0 for all I < < d. We also have X 2 0 because
f(p)) f(pa)= - -g((e)) (Ba) 9 (px)
f(ix) f(pa + 9 (Pk)
1.
Therefore, the above choices of v², Vij. and X satisfy the linear system and all constraints. Thus, (q" , ,,,",, 1²") satisfy the KKT conditions, and hence q" is the optimal solution to problem (FODD
Case 2: Pa
P1, and lim ((x) -00
Let A {i p. 2 }} and Q = {q E A(V) 9: = = A}. Suppose we use some strategy Q, i.e. there is some j E A such that dj + 0. Since lim f(x) -0, the adversary can always find p = P- - e that makes the objective -o. Thus, an optimal strategy must come from Q. Similar to Case 1, the p-minimization part can be written in terms of the vertex set U as follows:
min q f(p) PEN(#)
min q f()) pell"
min q² f(p)
pElla
= =q¹ f(ø) + min {a (f(p: - c) f(f.) + + (f(e, +c) f(2,)))
(EJ)EC
=q f())
{ag (fi) 459* (b.)
(ijjEC
q f(p)
max 49 (pi).
(12)
*E
where UA -tp ee; + eej : i j $ A}. and C = ( A]. 12 follows because q 0 for any E A. Thus, the problem of interest is equivalent to
min qEa
q f(t)
+ max 9:9 (b:)
ag
In other words, only need to solve q" from lower-dimensional problem
min (VA(VA) [- TT f(p) + max 9:9 (f:)
where VA is a truncated vocabulary with Val = d |A].
Ordering of the optimal solution. Similar to Case 1. an optimal q" is ordered with of 2
G2-
Analyzing KKT optimality. The Lagrangian can be similarly defined as
d-IAI Σ qi -
L)) - f()) f(p + max 9:9 9 (6.) A A + 1
i=1
and strong duality holds as well. The KKT conditions are
0 ffp) + { X 0,
( (B:) X + +11,
(first-order stationarity)
q" E A(VA),
(primal-dual feasibility)
Ng. Vi,
(complementary slackness)
where 2 (max; q. (p:)) = conv (Lg (Di)e: Gig (p.) = max, G (f:))). Let = (i:
J= - (p.) = cf (1sis =
g. (p.) 0} (1" <isd [A]}
where e = max; g (fc). It is sufficient to show that there exist v², X > 0 with X 0 for i E J. and coefficients 7/2 2 for E J with EiEr 7 = 1, such that
-f(p) + ng (6:) (1ET) X7 ((EN) +x* = 0.
17

---

present additional experimental results obtained using various choices of and r Game sampling algorithm. These experiments provide further insights into the performance and sensitivity of the model under different parameter settings. We also explored different values of e E {0.1, 0.3, 0.5, 0.8, 0.9} alongside different values. However, since the best performance was 0.99, report only those values here to highlight the Published as a conference paper at ICLR 2025
This is achieved by setting
Σ (Bn)
Σ f(Dn) KEJ (fx)
-1)
NEJ 9 (iA)
f(i)) - -v"
2 0, for E J,
9 (pi)
A (v' ((())) (GEN) 20. 0.
Moreover, 7V 2 and X 2 follow from the fact that S AA E and S 1 4A N.,
respectively.
B ADDITIONAL EXPERIMENTS
In Tables 2 and
consistently achieved with 0.95 effect of changing т.
As part of this evaluation, also analyzed the point which probabilities truncated and renor- malized in Game sampling and Nucleus sampling for randomly selected article from the WebText test set, using the GPT-2 XL model. The GPT-2 model has total vocabulary size of 50,000 tokens, so truncating the probability distribution can significantly reduce the set of candidate words for the next token. Figures Ia and Ib illustrate how these sampling strategies truncate the probability distri- bution. Figure la shows the distribution for the next word when using only token as context, along with the index where probabilities are truncated and set zero. contrast, Figure Tb presents the distribution for the next word when using the first 35 tokens as context, providing more information for the model to generate the next word. With more context, the model expected to be more certain about the next word, and the figure highlights the corresponding truncation points. Notably, Game sampling truncates a substantial portion of the 50,000-token distribution and dynamically adjusts the cutoff point based on the shape of the distribution (see Algorithm I).
2-0.5.r22 2.
a-0 2-2
(-0.00. L.
66,
0.0. 2D
z-0 222
p-0.2
p-0.00
Inden
[ootec]
(a) context:
token
(b) context: 35 tokens
Figure 1: Next-token probability distribution in GPT-2 XL model and truncation threshold of Game sampling and Nucleus sampling.
18

---

Published as a conference paper at ICLR 2025
Perplexity
Repetition
MAUVE
Perplexity
Repetition
MAUVE
0.95
1.0
6.874
0.087
0.739
0.95
1.0
6.067
0.048
0,858
0.95
7.960
0.058
0.809
6.804
0.037
0,883
0.95
1.5
13.336
0.015
0.898
0.95
1.5
10.423
0.010
0.926
0.95
2.0
23.592
0.003
0.926
0.95
2.0
17.499
0.003
0.945
0.95
2.5
40.129
0.002
0.908
0.95
2.5
28.738
0.001
0,919
0.95
3.0
66.481
0.001
0.815
0.95
3.0
46.973
0.001
0.858
0.95
3.5
107.544
0.001
0.699
0.95
3.5
78.152
0.001
0.721
0.95
4.0
172.822
0.001
0,474
0.95
4.0
132.77
0.001
0,475
0.99
7.067
0.081
0.746
0.99
1.0
6.176
0.047
0.845
0.99
1.1
8.275
0.055
0.820
0.99
1.1
6.947
0.033
0.879
0.99
1.5
14.231
0.012
0.897
0.99
1.5
11.019
0.008
0.941
0.99
2.0
26.783
0.002
0.917
0.99
2.0
19.482
0.002
0.938
0.99
48.508
0.002
0.864
0.99
34.662
0.002
0.911
0.99
3.0
89.308
0.001
0,745
0.99
3.0
63.555
0.001
0.792
0.99
3.5
161.402
0.001
0.529
0.99
3.5
120.889
0
0.497
0.99
4.0
296.453
0.001
0.273
0.99
4.0
243.844
0
0.257
GPT-2 Small
GPT-2 Medium
Perplexity
Repetition
MAUVE
Perplexity
Repetition
MAUVE
0.95
1.0
4.596
0.066
0.823
0.95
1.0
5.146
0.050
0.861
4.972
0.050
0.856
0.95
5.559
0.891
0.95
1.5
6,851
0.013
0.909
0.95
1.5
7.475
0.014
0.935
0.95
2.0
9.883
0.005
0.942
0.95
2.0
10.541
0.004
0.950
0.95
2.5
14,084
0.002
0.942
0.95
2.5
14.636
0.002
0.948
0.95
19.634
0.002
0,930
3.0
20.458
0.002
0,929
0.95
3.5
27.779
0.001
0,913
0.95
3.5
28.410
0.001
0,919
0.95
4.0
39.256
0.001
0.837
0.95
4.0
39.374
0.001
0.873
0.99
1.0
4.683
0.066
0.826
0.99
1.0
5.219
0.044
0.852
0.99
1.1
5,083
0.046
0.861
0.99
1.1
5.660
0.032
0.886
0.99
1.5
7.130
0.010
0.917
0.99
1.5
7.784
0.010
0,943
0.99
2.0
10.629
0.006
0.947
0.99
2.0
11.333
0.003
0.958
0.99
15.958
0.001
0,947
0.99
16.690
0,952
0.99
3.0
24.128
0.001
0.919
0.99
3.0
24.796
0.002
0.924
0.99
3.5
37.613
0.001
0.845
0.99
3.5
38.056
0.001
0.885
0.99
4.0
60.031
0.001
0.685
0.99
4.0
60.236
0.001
0.739
GPT-2 Large
GPT-2 XL
Table 2: Evaluations on the text generated by different types of GPT-2 models using Game sampling under different hyperparameters.
19

---

Published as a conference paper at ICLR 2025
Perplexity
Repetition
MAUVE
Perplexity
Repetition
MAUVE
0.95
5.757
0.069
0.640
0.95
1.0
8,500
0.131
0.842
0.95
1.1
6.285
0.049
0.670
0.95
1.1
9,938
0.134
0.831
0.95
1.5
8.528
0.015
0.759
0.95
1.5
14.000
0.128
0,858
0.95
2.0
12.313
0.005
0.794
0.95
2.0
23.875
0.149
0.843
0.95
2.5
17.210
0.003
0.811
0.95
2.5
36,250
0.162
0.834
0.95
24.362
0.001
0.801
0.95
3.0
52.000
0.173
0.813
0.95
3.5
33.905
0.002
0.778
0.95
3.5
63.750
0.174
0.797
0.95
4.0
48.921
0.001
0.664
0.95
4.0
87.000
0.182
0.753
0.99
1.0
5.897
0.066
0.664
0.99
1.0
8.938
0.130
0.831
0.99
1.1
6.436
0.046
0.687
0.99
1.1
10.250
0.134
0.845
0.99
1.5
8.957
0.013
0.762
0.99
1.5
15.625
0.136
0.854
0.99
2.0
13.263
0.004
0.809
0.99
2.0
26.625
0.153
0.840
0.99
2.5
19.729
0.002
0,833
0.99
2.5
41.750
0.165
0.822
0.99
3.0
29.696
0.002
0.791
0.99
3.0
60.000
0.181
0.806
0.99
3.5
46.506
0
0.720
0.99
3.5
84.500
0.178
0.759
0.99
4.0
77.289
0.001
0.522
0.99
4.0
119.500
0.177
0.686
GPT-J-6B
Llama-2-7B
Table 3: Evaluations on the text generated by GPT-J-6B and Llama-2-42 2-7B models using Game sampling under different hyperparameters.
20


Reviews:
[{"review_id": "s5cYhJhpeG", "reviewer": "Reviewer_Tan5", "summary": "This paper primarily focuses on text generation for language models.\nFirstly, the author presents a novel minimax optimization problem for text generation tasks, where the min-player aims to minimize the worst-case negative cross-entropy.\nSubsequently, it is demonstrated that the proposed minimax optimization problem can be interpreted as a likelihood maximization problem with implicit regularization.\nFinally, the algorithm for solving the minimax optimization problem is introduced and its performance is empirically evaluated through experiments using GPT-2 models.", "questions": "My main concerns and questions are outlined in Weaknesses.\nThere is a typo in the introduction section:\n* (line 55-56) \"From a statistical perspective\" is repeated.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The problem is appropriately motivated. Considering decoding strategies from a theoretical standpoint is essential for the research community.\n* The algorithm proposed to solve the suggested minimax optimization problem appears to be easily implementable in practice.", "weaknesses": "I'm wondering to what extent this study provides new insights for existing decoding strategies that have achieved empirical success.\nThe author states \"To resolve this dichotomy, this paper aims to propose a comprehensive theoretical framework of text generation\" in the introduction section, meaning that one of the main goals of this paper is to theoretically explain the success of these existing strategies.\nHowever, I'm not convinced that the proposed framework can replicate the widely recognized Nucleus sampling and Top-k sampling strategies simply by selecting an objective function $f$.\nWhile it's demonstrated that temperature sampling can be recovered by appropriately choosing the function $f$, I'm interested in knowing if other strategies can also be replicated.\n\nMoreover, since I'm not an expert in this research field, I'm not sure whether experiments using only GPT-2 models are sufficient for validating the proposed framework.\nAt the very least, it should be discussed whether the scale of the experiments conducted in this study is not insufficient compared to the current standards.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L6T4SlKNKm", "reviewer": "Reviewer_1fhp", "summary": "The paper proposes a theoretical framework that captures various decoding strategies used in practice, as well as provides a generalized form of such a technique and some experiments to support it.", "questions": "“Depending on the desired effect, the truncation threshold or S may be determined from various quantities like the truncated vocabulary size, truncated probability weight, entropy, and so on. ” - this is confusing since the truncated vocabulary size, probability weight etc are themselves a function of S. What did you mean here?\nRegarding the experiments, have you tried any of the methods that drop non-tail elements? (such as truncation sampling by Finlayson et al. (2024)). It would be interesting to see how a different-pattern sampling compares.\nIs there any reason in the remark around line 376 for $C_{I-1}$ to not dominate the entropy? It’s not obvious how to interpret that.\nCan your method be adapted to deal with other sorts of measure distances? The most natural one would be bounded cross entropy since this is what training usually optimizes", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The theoretical framework is well justified and rigorously supported by proofs\nStatements are accurate and notation is consistent. Assumptions are clearly stated and natural.\nThe problem that is addressed is practically significant.\nThe framework generalizes previous decoding schemes opening the door to new, theoretically-grounded, heuristics.", "weaknesses": "In Prop 3.1, the authors could mention why we need the $\\epsilon < max \\hat{p}$ - that if we assign non-zero measure to $x_{<t}$, we’d get a cost of $-\\infty$.\nTheorem 4.3 doesn’t say anything about how the $p$ that yields the optimal solution looks like, nor what role $\\hat{w}$ plays (in the min problem; the max one is clear). Does that lack structure or could it be added to the Theorem statement?\nWhile the game approach to it is intuitive to some, it might be worth emphasizing the perspective of optimizing the worst case scenario: there are a couple of places where you phrase the framework, but don’t necessarily argue why nature “should” be adversarial. Optimizing the worst case scenario makes it more clear to people that are not used to thinking about games (since after all you just choose the approach that has the best guarantees under the TV assumption).\nIt’d be helpful to present the more general case secondary to what you get when you use a greedy local approach (which is done in section 3.4 and then used throughout). Once you decide to do local optimization rather than global, you can jump straight to Equation (4) and while Section 3.3 is well-written and objectively accurate, it is the hardest part to read of the whole paper and people may lose the important take-aways because of getting confused there.\n\nMinor:\nRemark at line 339 seems to be more relevant right before Corollary 4.5.\nLine 54-55 repeats “From a statistical perspective”\nIt is worth making explicit that X_0 is a multidimensional object (as opposed to X_{t>0})\nLine 243: $N (\\hat{P})$ to be $\\hat{P}$.. - an extra $\\hat{P}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q5dZ0RF63C", "reviewer": "Reviewer_ivfP", "summary": "The paper explores the gap between theoretical and practical decoding strategies in text generation for language models.The authors introduce a new framework, Decoding Game, which models text generation as a two-player game. They derive the optimal one-step strategy, showing adversarial regularization on likelihood maximization, with popular methods as first-order approximations. The framework also generalizes to include strategies like greedy search and temperature scaling. Numerical experiments support their theoretical findings.", "questions": "N/A", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The analysis of the decoding process of LLMs is thoroughly considered. \n- The proposed decoding is backed up theoretically\n- The experimental results show somewhat better performance than baselines.", "weaknesses": "- What is the motivation for choosing the TV-sup norm to compute the difference between the true distribution and the approximated one by LLMs? Is there any theoretical justification behind this selection? If not, at least an ablation study showing the effectiveness of this norm is necessary.\n- It is still ambiguous why the authors define the distance between the two mappings by the way around Line 248.\n- The result in the Equation (1) is non-trivial. Detailed transformation of it is necessary. At first glance, I questioned the equivalence of the two sides.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wxISMxB0qQ", "reviewer": "Reviewer_d8ex", "summary": "The paper derives stochastic decoding methods as the optimal strategy in an adversarial two-player game. Due to tractability issues, a one-step version of this game and a first order approximation for the resulting strategy is used. An explicit expression for the resulting regularization term added to the maximum likelihood objective is derived.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* It is valuable to have a proper theoretical derivation of heuristic decoding methods that have long been around in practice, and the paper provides this.\n* the paper is well-written and neat\n* the connection to robust optimization is interesting", "weaknesses": "* The empirical comparison is not state-of-the-art. For example, there are newer variants of greedy designed to overcome issues with repetitiveness, see contrastive search (see: https://huggingface.co/blog/introducing-csearch).\n* The introduction sounds a bit like stochastic sampling strategies would always be preferable over deterministic optimization strategies like greedy search or beam search in practice. While there definitely is evidence that they perform better in some settings as given by the citations in the paper, there is also counter-evidence in other settings, e.g. [1], in particular in closed-end tasks. (Btw, the experiments in the paper are also limited to open-end text generation.) I understand that the authors preliminarily want to motivate stochastic decoding strategies in this paper and I do not want to diminish the motivation for them, but I still think it is important to at least acknowledge that the situation is more nuanced. For a recent empirical comparison, also see [2].\n\n[1] \"On Decoding Strategies for Neural Text Generators\" [Wiher et al, 2022]\n\n[2] \"A Thorough Examination of Decoding Methods in the Era of LLMs\" [Shi et al., 2024]", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)