Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies

We thank the reviewer very much for their feedback and suggestions, especially on the nuances of the performance of different decoding strategies, both stochastic and deterministic, across different tasks. We address each point below.

Empirical comparison with state-of-the-art variants of greedy decoding: We agree that it is important to compare newer searching methods. As suggested by the reviewer, we have conducted open-ended experiments on Constrastive Search and summarize the results here.

In GPT-2 Small:

In GPT-2 Medium:

In GPT-2 Large:

In GPT-2 XL:

We also experimented on larger models as suggested by other reviewers. In GPT-J-6B:

And we are now evaluating Llama-2-7B models and will update you once it is ready.

These results complement our current Table 1. We observe that Contrastive Search does significantly reduce repetition and improve MAUVE score, especially in the larger models. However, in these open-ended generation tasks, our method still maintains an edge. We believe this corresponds to the reviewer's comments that deterministic strategies tend to perform better in closed-end tasks.

Expanding the scope in introduction: We thank the reviewer for suggesting a more comprehensive summary of the empirical performances of decoding strategies. We have revised our manuscript to present a more nuanced analysis of decoding strategies across different tasks, incorporating recent empirical studies including [Wiher et al., 2022] and [Shi et al., 2024]. Following the reviewer's comments, our expanded literature review now better acknowledges task-specific performance variations between stochastic and deterministic methods.

Thank you again for your comprehensive and helpful review. Based on your feedback, we are now working on a revised version and will update you before the end of discussion period. During this time, please also let us know if there are any further questions.

We thank the reviewer very much for their suggestions and questions, especially on the norm and neighborhood notation in this paper. We address each point below.

Understanding TV-sup norm: We define the TV-sup norm as the maximum total variation distance between pairs of conditional next-token distributions. Formally, $||\mathbb P-\widehat{\mathbb P}||\_{\text{TV},\infty}\leq\epsilon$ means that for all contexts $x\_{<t}$, the conditional next-token distributions has at most $\epsilon$ TV distance: $d_\text{TV}(\mathbb P(\cdot|x_{<t}),\widehat{\mathbb P}(\cdot|x_{<t}))\leq\epsilon$.

We use this particular definition because it naturally extends the one-step game constraint $d_\text{TV}(p,\hat p)\leq\epsilon$ to the multi-step setting. Since our goal is to reduce the multi-step setting back to the one-step setting, such a choice of norm is the most convenient.

Equivalently, if we arrange all conditional next-token distributions as columns of a matrix, our TV-sup norm corresponds to the maximum of the $\ell_1$-norm (by definition, twice as the TV norm) of each column, also known as the $(1,\infty)$ mixed norm:

$||A||\_{1,\infty}=\max_j\sum_{i=1}^{d}|a_{ij}|$.

See, for instance, Example 5.6.4 of [1], a standard textbook in matrix analysis.

This norm finds broad applications in probability and statistics literature. For example, Chapter 3 of [2] on asymptotics of Markov processes, and [3,4] on regression and signal processing.

We acknowledge that we need to improve the readability of our current presentation on TV-sup norm. Based on your feedback, we have revised our presentation to better emphasize how the neighborhood $N(\widehat{\mathbb P})$ builds upon the one-step TV norm and facilitates the reduction to one-step games, and eased the notations involved.

Understanding the direct products in Equation (1): Let us explain how the $(1,\infty)$ mixed norm naturally leads to a direct product decomposition. Consider a matrix $A=[\mathbf a_1,\mathbf a_2,...,\mathbf a_N]\in\mathbb R^{d\times N}$. The following equivalences hold:

||A||\_{1,\infty}\leq\epsilon \Leftrightarrow \max_i\{||\mathbf a_i||_1}\leq\epsilon \Leftrightarrow ||\mathbf a_i||_1\leq\epsilon\ \forall i.

This yields the decomposition:

{$A:||A||_{1,\infty}\leq\epsilon$} $=$ {$\mathbf a_1:||\mathbf a_1||_1\leq\epsilon$} $\times...\times$ {$\mathbf a_N:||\mathbf a_N||_1\leq\epsilon$}.

Equation (1) follows from this fundamental principle: a uniform bound on the maximum implies the same bound holds individually for each component.

Thank you again for your comprehensive and helpful review. Based on your feedback, we are now working on a revised version and will update you before the end of discussion period. During this time, please also let us know if there are any further questions.

References

[1] R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge: Cambridge University Press, 1985.

[2] Daniel W. Stroock. An introduction to Markov processes. Vol. 230. Springer Science & Business Media, 2013.

[3] Matthieu Kowalski. "Sparse regression using mixed norms." Applied and Computational Harmonic Analysis 27.3 (2009): 303-324.

[4] Dongmin Kim, Suvrit Sra, and Inderjit Dhillon. "A scalable trust-region algorithm with application to mixed-norm regression." 27th International Conference on Machine Learning (ICML), 2010.

[1/2]

Thank you for your thorough review and insightful questions. Your feedback has helped us significantly improve the paper, particularly its presentation. We address each of your points below.

In Weaknesses section,

Why we need $\epsilon<\max\hat p$ in Proposition 3.1: We agree that this constraint is crucial, as it prevents the optimal value of the game from becoming $-\infty$. We have added an explanation to this in the revised version.

The structure of optimal $p$ and the role of $\hat w$ in Theorem 4.3: We have added a characterization of the optimal $p$. The core minimization problem, $\min_{p:d_\text{TV}(p,\hat p)\leq\epsilon}q^\top\log p$, involves minimizing a concave function over the polytope defined by the $\epsilon$-ball in total variation distance.

Due to non-convexity, the optimal $p$ may not be unique, and its structure is not trivial. However, it is known that such a problem always attains the minimum at a vertex of the polytope. Specifically, the optimal $p$ belongs to the set {$\hat p-\epsilon e_i+\epsilon e_j:i\neq j$}, where $e_i$ denotes the $i$-th standard basis vector in $\mathbb R^d$. Each candidate solution has the form $(\hat p_1,...,\hat p_i-\epsilon,...,\hat p_j+\epsilon,...,\hat p_d)$.

The optimal $p$ has a more complicated structure than the optimal $q$, because we minimize over a non-convex problem with a concave objective, while maximizing over a convex one. However, our polytope characterization simplifies this analysis considerably. The optimization reduces to selecting the optimal $p$ from a finite set of candidates, expressed as:

$\min_{i\leq\hat\iota}q_{i}(\log (p_i-\epsilon)-\log p_i),$

which, in vector notation, becomes

$\min_{i\leq\hat\iota}q_i(\log (p_i-\epsilon)-\log p_i)=-||q_{1:\hat\iota}/\hat w||_\infty.$

This explains both the role of $\hat w$ and the emergence of the $\ell_\infty$ norm: $\hat w$ effectively vectorizes the vertex selection process, and by doing so we can explicitly see the regularization term. We have added this geometric intuition to the main text to complement the formal proofs.

Interpreting the game as worst-case optimization: Optimizing the worst-case scenario (robust optimization) is definitely an important perspective supplementing our game-theoretic approach. We have strengthened our analysis by explicitly connecting the game-theoretic and robust optimization perspectives.

Clearer presentation of the general case: Following your suggestion, we have reorganized the paper to improve its pedagogical flow. The new Section 3.2 introduces the one-step game. Section 3.3 then extends these ideas to the multi-step case, with simplified notation to enhance readability. We hope this progression from specific to general cases makes the theoretical development more accessible.

[2/2]

In Questions section,

What do we mean by the sentence about truncation threshold: We wanted to express the fact that different decoding methods have different mechanisms for determining $S$. For example, in top-k sampling, $S$ is simply {$1,...,k$}, where $k$ is a fixed size parameter. In nucleus sampling, $S$ is {$1,...,i^*$} where $i^*=\max${$i:\sum_{j=1}^i\hat p_j\leq p$}, with $p$ representing the desired cumulative probability mass.

We have rephrased this sentence to improve clarity: "Here, different designs define the truncation set $\mathcal S$ using distinct criteria: top-$k$ sampling uses a fixed size threshold, Nucleus sampling uses cumulative probability mass, and entropy-based methods use information-theoretic thresholds ($\eta$)."

Empirical comparison with methods dropping non-tail elements: We agree that comparing our approach with non-tail methods like (Finlayson et al., 2024) and Typical sampling [1] would be valuable. We are currently conducting these experiments.

We have obtained results for Typical sampling.

In GPT-2 Small:

In GPT-2 Medium:

In GPT-2 Large:

In GPT-2 XL:

We also experimented on larger models as suggested by other reviewers. In GPT-J-6B:

And we are evaluating Llama-2-7B models and will update you once ready.

Our method has advantages over Typical sampling in open-ended tasks. Experiments on (Finlayson et al., 2024) are in progress. We will share the completed results later.

Interpreting the quantity $C_{I-1}$: Let us clarify how $C_{I-1}=-\log W+\epsilon/W$ influences the growth of the support set {$1,...,I-1$}. An element $I$ is added to the support if its surprisal is less than $H(p_{1:I-1})+C_{I-1}$, where $W$ represents the total probability mass of $p_{1:I-1}$.

While $C_{I-1}$ need not dominate the entropy term, its magnitude varies inversely with $W$. This creates a dynamic threshold: when $I$ is small and $W$ is low, the large value of $C_{I-1}$ encourages support expansion. As $I$ increases and $W$ grows, $C_{I-1}$ decreases to $\epsilon$, making the entropy $H(p_{1:I-1})$ more relevant in constraining further support growth.

Adaptation to other types of distances: The choice of total variation distance is crucial for obtaining closed-form solutions. While our framework could theoretically extend to KL divergence or cross entropy, these metrics present significant analytical challenges.

Under TV distance, despite the non-convexity of the $p$-minimization, the polytope structure of the feasible region enables characterization of the minimizer (We also discussed this in the previous part). In contrast, with KL divergence, the feasible region becomes

{$p:p^\top\log p-p^\top\log\hat p\leq \epsilon$} $\cap$ {$p:p^\top1=1$}.

This geometry is more complicated. As a proposal, it can be approached by introducing the transformation $z_i=\log p_i,z_i\leq0$, yielding:

$\min_q\max_{z\in Z}-q^\top z=\min_q h_Z(-q),$

where $h_Z$ is the support function [2] of the non-convex set

$Z=${$z:\sum e^{z_i}(z_i-\log\hat p_i)\leq\epsilon,\sum e^{z_i}=1$}.

While the $q$-optimization part remains convex (because $h_Z$ is always convex [2]), the $p$-optimization part is not straightforward because characterizing $h_Z(-q)$ is challenging due to the complicated geometry of $Z$. This problem itself may be an interesting future direction, and we are happy to add these discussions to our revision.

Finally,

Thank you again for your comprehensive and helpful review. Based on your feedback, we are now working on a revised version and will update you before the end of discussion period. During this time, please also let us know if there are any further questions.

References

[1] Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. "Locally typical sampling." Transactions of the Association for Computational Linguistics, 11:102–121, 2023.

[2] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

We would like to update you on the experiment results of BA sampling (Finlayson et al., 2024) in GPT-2 models, GPT-J-6B, and Llama-2-7B.

In GPT-2 Small:

In GPT-2 Medium:

In GPT-2 Large:

In GPT-2 XL:

In GPT-J-6B:

In Llama-2-7B:

BA sampling has comparable performance with our method. As a strategy that drops non-tail elements, it scores higher in Llama-2-7B and GPT-2-Large, where our method is at the second place. Our method achieves a higher score in the other models. We also remark that BA involves matrix factorization and operates at a higher computation cost.

We have included these results in our updated submission file. Thank you again for your review, and please let us know if there are further questions.

We are very grateful for your positive evaluation and constructive comments on our submission.

We thank the reviewer for their thoughtful feedback regarding the theoretical interpretability and experimental validation of our framework. We address each point in detail below.

Recovering Top-k or Nucleus sampling:

Both Top-k and Nucleus sampling follow a two-step process, first truncating the probability distribution, then rescaling the remaining probabilities. The key difference lies in how they determine their truncation thresholds. Similarly, other methods like $\eta$-sampling and Mirostat sampling follow this same truncation-rescaling pattern, each with their own threshold selection criteria.

Rather than replicating one single strategy exactly, our primary contribution is understanding the fundamental design principles behind this broad family of strategies -- specifically, why do all of them follow a truncation-rescaling process?

By setting $f(x)=\log x$ in our framework, we show that our approach naturally recovers a sampling method based on truncation and rescaling (Theorem 4.4 and Corollary 4.5). Although our method determines the truncation threshold differently from Top-k or Nucleus sampling, our framework provides key theoretical insights:

1. Truncation emerges as optimal because minimax robustness implicitly requires $\ell_{\infty}$ regularization.
2. Uniform rescaling of the remaining components is effective because it approximates the optimal solution in first order.

Temperature rescaling, instead of uniform rescaling, is obtained when we change the objective $f$ from $\log$.

Experiments on GPT-2 vs larger models: We agree that it is better to incorporate experiments on larger models. Following your suggestions, we have obtained results on GPT-J-6B model:

Here, Contrastive and Typical are new methods suggested by other reviewers. Our method still maintains an edge in terms of having the highest MAUVE score.

We are also evaluating Llama-2-7B model and will update you once it is ready.

At the same time, we would like to clarify that recent works on decoding methods, such as [1], also only evaluated GPT-2 models. In the initial version of our paper, we aimed to follow the existing experiment settings.

Thank you again for your comprehensive and helpful review. Based on your feedback, we are now working on a revised version and will update you before the end of discussion period. During this time, please also let us know if there are any further questions.

References

[1] Finlayson M, Hewitt J, Koller A, Swayamdipta S, Sabharwal A. "Closing the curious case of neural text degeneration." The Twelfth International Conference on Learning Representations (ICLR), 2024.

We would like to update you on the experiment results of Llama-2-7B models.

Here, Contrastive [1], Typical [2], and BA [3] are decoding methods suggested by other reviewers. Our method scores the second highest in Llama-2-7B, next to BA, and maintains an edge over other methods like Nucleus sampling. We also remark that BA involves matrix factorization and operates at a higher computation cost than our method. The results show a consistent performance of our method in larger models such as GPT-J-6B (in our previous reply) and Llama-2-7B.

We have included these results in our updated submission file. Thank you again for your review, and please let us know if there are any further questions.

References

[1] Yixuan Su, Tian Lan, Yan Wang, Dani Yogatama, Lingpeng Kong, and Nigel Collier. A contrastive framework for neural text generation. In Advances in Neural Information Processing Systems, 2022.

[2] Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. Locally typical sampling. Transactions of the Association for Computational Linguistics, 11:102–121, 2023.

[3] Matthew Finlayson, John Hewitt, Alexander Koller, Swabha Swayamdipta, and Ashish Sabharwal. Closing the curious case of neural text degeneration. In The Twelfth International Conference on Learning Representations, 2024.

Thank you for your reply.

First, we would like to clarify that Nucleus sampling is not superior in our experiments (Table 1). Nucleus only performs better than our method in GPT-2 Large, and fails to do so in all the remaining models: Llama-2-7B, GPT-J-6B, GPT-2 XL, GPT-2 Medium, and GPT-2 Small.

Yet we understand it is important to further compare our method with Nucleus sampling. The only difference lies in how each method decides the truncation threshold. In Nucleus sampling, the truncation threshold is $\max${$I:\sum_{i=1}^{I}p_i<P$}. In our method, it is $\max${$I:\sum_{i=1}^{I-1}p_i\log(p_i/p_I)<\epsilon$}. The former is based on probability while the latter has an interpretation from information theory, which we commented at around line 375.

Due to the fact that $f(I)=\sum_{i=1}^{I-1}p_i\log(p_i/p_I)$ is increasing in $I$, we can still replicate Nucleus by setting an appropriate $\epsilon$, depending on $P$ (the hyperparameter of Nucleus) and the probability distribution $p_i$. Doing so, we will need an adaptive $\epsilon$ that changes at every decoding step. We have added these discussions to our paper at around line 383. To reiterate, our method comes from theoretical optimality results, and also performs consistently better than Nucleus in experiments.