Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies

Authors: Sijin Chen, Omar Hagrass, Jason Matthew Klusowski
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords: decoding strategy, text generation, sampling, optimality, game theory, robust optimization, implicit regularization, sparsity

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.

Decision: accept (poster)
Reviewer scores: 5, 8, 5, 8

Reviews and discussion:
<thread>
creation date:
1729340122644

thread_type:
official_review

<thread_object>
creator: reviewer_d8ex

<content>
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.

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.
* the paper is well-written and neat
* 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).
* 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].

[1] "On Decoding Strategies for Neural Text Generators" [Wiher et al, 2022]

[2] "A Thorough Examination of Decoding Methods in the Era of LLMs" [Shi et al., 2024]

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730130990819

thread_type:
official_review

<thread_object>
creator: reviewer_ivfp

<content>
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.

strengths:
- The analysis of the decoding process of LLMs is thoroughly considered. 
- The proposed decoding is backed up theoretically
- 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.
- It is still ambiguous why the authors define the distance between the two mappings by the way around Line 248.
- 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.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1730683010969

thread_type:
official_review

<thread_object>
creator: reviewer_1fhp

<content>
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.

strengths:
The theoretical framework is well justified and rigorously supported by proofs
Statements are accurate and notation is consistent. Assumptions are clearly stated and natural.
The problem that is addressed is practically significant.
The 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$.
Theorem 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?
While 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).
It’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.

Minor:
Remark at line 339 seems to be more relevant right before Corollary 4.5.
Line 54-55 repeats “From a statistical perspective”
It is worth making explicit that X_0 is a multidimensional object (as opposed to X_{t>0})
Line 243: $N (\hat{P})$ to be $\hat{P}$.. - an extra $\hat{P}$.

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?
Regarding 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.
Is 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.
Can 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
</content>
</thread_object>

</thread>
<thread>
creation date:
1731000603190

thread_type:
official_review

<thread_object>
creator: reviewer_tan5

<content>
summary:
This paper primarily focuses on text generation for language models.
Firstly, 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.
Subsequently, it is demonstrated that the proposed minimax optimization problem can be interpreted as a likelihood maximization problem with implicit regularization.
Finally, the algorithm for solving the minimax optimization problem is introduced and its performance is empirically evaluated through experiments using GPT-2 models.

strengths:
* The problem is appropriately motivated. Considering decoding strategies from a theoretical standpoint is essential for the research community.
* 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.
The 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.
However, 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$.
While 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.

Moreover, 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.
At 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.

questions:
My main concerns and questions are outlined in Weaknesses.
There is a typo in the introduction section:
* (line 55-56) "From a statistical perspective" is repeated.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732169922701

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
We have updated our submission

comment:
Dear reviewers,

Thank you very much for your review. We have made an update to our pdf file submission based on your feedback to improve our presentation and include some new experiment results. The changes reflect our individual replies below.

As we are still working on extra experiments and polishing the presentation further, we anticipate to make one more update by the end of the discussion period. We hope that our current update can help the reviewers know about our progress and facilitate our discussion.

Please let us know if there are further questions and feedback.

Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1732598088063

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
We have updated our submission

comment:
Dear reviewers,

Thank you very much for your review. We have updated our submission to include new experiment results on Llama-2-7B and BA sampling method (Finlayson et al., 2024) and to continue polishing our presentation, as suggested by the reviews.

Please let us know if you have any other questions or feedback. We look forward to engaging in further discussions with you.

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces a game-theoretic framework, coined "Decoding Game", which models text generation as a two-player zero-sum game. The framework is used to explain methods such as Top-k and Nucleus sampling as approximations to the optimal strategy in the decoding game, giving a common theoretical grounding to these approaches. Empirical evaluation on several language models, including GPT-2, GPT-J-6B, and Llama-2-7B, and showing competitive performance according to various metrics, complements the submission.

Some reviewers seemed initially skeptical regarding the potential for practical relevance of the results and certain details of the experimental setup. However, these concerns seem to have been largely resolved through author rebuttals and updates to the submission. The addition of experiments with larger models/baselines was particularly well-received. There appears to be positive consensus towards the value of the paper.

For that, an acceptance decision is recommended.