The Consensus Game: Language Model Generation via Equilibrium Search

Thank you for your review!

Clarity of the proposed method

Thank you for the suggestion. To improve clarity, we will include a pseudo-code with a running example in our revision.

Typos

Thank you for catching those typos. We will fix them in our revision.

How is the payoff matrix defined for the consensus game?

Signalling games are sequential in nature, as such, they are typically represented in tree-form as we show in Figure 1 (i.e., D and G both receive a reward of 1 each if D picks the correctness parameter that D was trying to communicate. In all other cases, they receive a reward of 0 each). More specifically, D and G receive a reward of (1, 1) each if and only if G picks the same correctness parameter (correct or incorrect) that D received. In all other cases, they receive (0, 0). So, for example, if D receives the signal "correct" and produces a natural language string "u". And if G, conditioned on "u", produces "correct", they both receive (1, 1). If G instead picks "incorrect", they both receive (0,0).

We hope we have addressed your questions and concerns. Do let us know if you have any other questions!

Question 1 (Equations (1) and (2))

The difference between the way our algorithm is written, and the way piKL-Hedge (Algorithm 1 of Jacob et al.) is written, is just cosmetic and amounts to a change of variable. The policies the two algorithms produce are equivalent.

In the original piKL paper, Algorithm 1 (piKL-Hedge) keeps track of cumulative values in the variable named $\textsf{CV}^{(t)}$ on line 11. Then, the update is

$\pi^{(t+1)}(a) \propto \exp \{ \frac{\eta \textsf{CV}^{(t)}(a) + t \lambda \eta \log \tau(a)} {1 + t\lambda\eta} \}$

(where for us the anchor policy $\tau$ is $\pi^{(1)}$, the initial policy of the language model.) In our paper, we use the same formula above, but divide the numerator and denominator of the fraction inside the exponentiation by the same quantity $\eta t$. This results in an update of the form $\pi^{(t+1)}(a) \propto \exp \{ \frac {(\frac{1}{t}\textsf{CV}^{(t)}(a)) + \lambda \log \tau(a) } {1/(\eta t) + \lambda } \}$

In fact, in our paper we keep track of the average values, which we call $Q$ (indeed, observe in the display equation at the very bottom of page 4, the cumulated values $\sum\frac{1}{2}\pi(\cdots)$ are divided by $t$ on the left of the sum). So, in summary, our updates are equivalent to those of piKL and can be written as $\pi^{(t+1)}(a) \propto \exp \{ \frac {Q^{(t)}(a) + \lambda \log \tau(a) } {1/(\eta t) + \lambda } \}$ which is what we have in the paper.

The reason why we performed this change is that the numerical range of the $Q$ variables we keep track of remains small, whereas the cumulated utilities $\textsf{CV}$ can grow linearly in absolute value.

Question 2 (What about larger models?)

Thank you for the suggestion. Unfortunately, due to the size of the datasets and the number of tasks involved, we have not been able to evaluate our approach on models larger than LLaMA-13B. We leave this to future work!

Question 3 (Could ER be used for fine-tuning?)

We think the idea of fine-tuning the models using this objective is a great idea, but this is not something we have been able to try yet.

Typo

Thanks for the catch. We will fix this in our revision.

Thank you for your review!

What are the relative contributions of normalization and equilibrium search?

This is a great question! To tease apart these two components of EQUILIBRIUM-RANKING, we have run a new ablation experiment that reranks using a pointwise-mutual-information-style product using $\pi_G^{(1)}$ and $\pi_D^{(1)}$ rather than unnormalized generator and discriminator probabilities. This new ablation (labled MI* in the table below) does improves performance over baseline approaches but consistently underperforms the full EQUILIBRIUM-RANKING method. We will include these results in the revised version of the paper that we will upload in the next few days.

Intrinsic Analysis of Inconsistency

Thank you for the suggestion! In order to look at how severe the problem is, we performed an analysis looking at how often the argmax answers from G and D disagree in each task. The table below shows that they do in fact disagree with each other a significant amount. Furthermore, we also observe that in cases where the disagreement % is larger, EQUILIBRIUM-RANKING offers the most benefit relative to G (The pearson correlation between "Disagreement %" and "% Improvement" is 0.64). We will include these results in the revised version of the paper that we will upload in the next few days.

More detailed discussion of piKL in the appendix?

Thank you for your suggestion, we will do that! More context behind the choice and properties of piKL can be found in our response to Reviewer Jsc5.

Thanks for your review!

Methodological notes behind the choice of Equations (1) and (2)

We use Equations (1) and (2) to iteratively refine the policies of the players (generator and discriminator). Such policy-refinement procedures typically go under the name of "learning dynamics" in the theory of learning in games. Methogologically, the learning dynamics we use in our paper were designed to achieve the following desiderata:

1. The update rules in Equation (1) and (2) are very easy to implement in practice, in that they only require elementary operations such as exponentiation and normalization. This enables us to efficiently implement the refinement operations in a framework such as NumPy or PyTorch in only a couple of lines of code.
2. The update rules guarantee strong no-regret properties. Regret is the standard optimality metric for online learning, and intuitively tracks the discrepancy between realized utility and the best utility that could have been realized in hindsight.
3. The update rules ensure that the refined policies do not get arbitrarily far from the initial policies that are produced by the language model. As explained in the paper, this is important to guarantee reasonableness.
4. By virtue of their no-regret properties, the update rules retain strong connections with game-theoretic notions of optimality.

From a technical point of view, Equations (1) and (2) are a form of mirror descent, a generalization of gradient descent that accomodates more specialized geometries, such as the natural geometry of conditional probability distributions, such as in the case of this paper.

On the reliance on piKL

We disagree that reliance on piKL limits the methodological novelty of the paper, for two reasons:

1. The use of game-theoretic learning dynamics for language generation is novel. For historical context, prior uses of piKL were in the direction of providing interpolations between imitation learning (aka. behavioral cloning) and pure self-play learning in the context of multi-agent reinforcement learning. However, we realized that the strong mathematical properties of piKL dynamics could be used to help guide production of language, which led to this paper. (See also above for considerations that help explain the speicifc choice of using piKL dynamics.)
2. From a technical point of view, piKL dynamics were defined in the context of normal-form games (that is, simultaneous-action nonsequential games, such as rock-paper-scissors). Instead, we instantiate piKL as part of a sequential potential (coordination) game.

Why search for coarse correlated equilibria?

The existing analysis of piKL-hedge provides a guarantee of convergence to a coarse correlated equilibrium. However, as we hinted at the very end of Section 2.2, we believe that in the case at hand most no-regret dynamics (including our own) will actually converge to Nash equilibrium. This is because the consensus game is a potential game, and in potential games dynamics based on smooth regularization are known to lead to Nash equilibria. Unfortunately, piKL is not, strictly speaking, an instance of such a dynamics, due to the fact that entropic regularization does not guarantee Lipschitz-continuous gradients. (Very small perturbations of piKL dynamics could fix the issue, but introducing a negligible amount of $\epsilon$-exploration). In practice, we observe excellent convergence properties, and leave the question of ironing out these technical subtleties for future work.

We will add this discussion in the next version of the paper that we will upload in the next few days.

Drop in performance on the HHH dataset

We first note that on this benchmark, other hyperparameter settings of EQUILIBRIUM-RANKING for LLaMA-13B results in the performance that is close to LLaMA-7B. The drop in performance for the larger model could be explained by the fact that HHH dataset tests the alignment of instruction-tuned chatbots. The LLaMA models that we use are not instruction-tuned which makes them poor at following prompts of the form listed in Appendix B. Furthermore, inverse-scaling (where, performance of larger models degrade) has been observed in similar tasks such as TruthfulQA [1].

[1] Lin, Stephanie, Jacob Hilton, and Owain Evans. "TruthfulQA: Measuring How Models Mimic Human Falsehoods." Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022.

Thank you for your response! We have attempted to address all the weaknesses above. Are there any aspects you don't think have been addressed, and is there anything else we could do to address these concerns in our revision?

Thank you for your review!

Clarity

1. Thank you for your suggestion, we will improve section 2.2 to include a more detailed introduction in our revision. a. "Reasonableness": We acknowledge this concern and are open to suggestions! As you pointed out, "alignment" does have usage in this space that could make it confusing. b. We agree and will note this point in our revision. c. You are right. This subsection should be called "decoding methods".

What is the relationship between our CD experiments and [1]?

We agree our CD baseline is sufficiently different from other work that we should clarify in our revision. We were unable to compare against CD for reasoning [1] as it was concurrent with our work. We do note that we can provide a direct comparison to published CD numbers on ARC-E and ARC-C. On ARC-E, LLaMA-13B + ER-D (76.4) is competitive with the (much larger) LLaMA-65B + CD ($\beta=1.0$) (76.9). On ARC-C, LLaMA-13B + ER-D (61.4) outperforms LLaMA-65B + CD ($\beta=1.0$) (59.7).

How does this generalize to other language modeling problems?

Our approach does require using LMs as "sequence-level" discriminators that evaluate complete generations. That said, we are still able to apply it to standard generation tasks by formulating them as generate-and-rerank problems (like we do in GSM8K and TruthfulQA) - that is, we first sample a set of candidates from the language model using top-p and top-k sampling then use EQUILIBRIUM-RANKING on top. It can thus already be applied to open-ended generation problems. We think that recent work in partial reward models [2, 3] is a promising direction for future work that could apply it directly to generation rather than discriminative reranking.

Convergence result of Anagostides et al.

A celebrated result in the theory of learning in games is that the average play of no-regret dynamics converges to the set of coarse correlated equilibria of the game. However, since our game has additional structure (in particular, it is a potential game), most learning dynamics in fact converge to Nash equilibria, which are always a subset of coarse correlated equilibria. Anagnostides et al. provide a general framework for analyzing this phenomenon for a general class of dynamics based on the online mirror descent framework. Unfortunately, while piKL is in the spirit of the algorithms studied by Anagnostides at al., we remark that due to technical conditions (specifically, a lack of Lipschitz continuity of the gradient of the entropy regularizer close to the boundary of the policy space), piKL is not, strictly speaking, an instance of the dynamics studied by Anagnostides et al. In practice, this subtlety seems to be simply a technical detail, and we indeed observe excellent convergence properties. We leave the question of ironing out these technicalities for future work.

Bias in approach

In the gameplay itself, the "correctness parameter" is always uniformly sampled from between "correct" and "incorrect". However, we haven't experimented with fitting this prior on a dev set, which as you pointed out could result in bias of the form you described.

Combining ER-G and ER-D

We do not have strong intuition here but we think that additive or multiplicative ensembling are both great options for combining these two approaches!

[1] O'Brien, Sean, and Mike Lewis. "Contrastive decoding improves reasoning in large language models." arXiv preprint arXiv:2309.09117 (2023).

[2] Wu, Zeqiu, et al. "Fine-Grained Human Feedback Gives Better Rewards for Language Model Training." arXiv preprint arXiv:2306.01693 (2023).

[3] Yang, Kevin, and Dan Klein. "FUDGE: Controlled Text Generation With Future Discriminators." Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021.