The Consensus Game: Language Model Generation via Equilibrium Search
Authors: Athul Paul Jacob
Yikang Shen
Gabriele Farina
Jacob Andreas
Venue: ICLR 2024 spotlight (2024)
Keywords: language models
decoding
planning
game theory
Primary area: generative models

Abstract: When applied to question answering and other text generation tasks, language models (LMs) may be queried generatively (by sampling answers from their output distribution) or discriminatively (by using them to score or rank a set of candidate answers). These procedures sometimes yield very different predictions. How do we reconcile mutually incompatible scoring procedures to obtain coherent LM predictions? We introduce a new, a training-free, game-theoretic procedure for language model decoding. Our approach casts language model decoding as a regularized imperfect-information sequential signaling game—which we term the concensus game—in which a generator seeks to communicate an abstract correctness parameter using natural language sentences to a discriminator. We develop computational procedures for finding approximate equilibria of this game, resulting in a decoding algorithm we call equilibrium-ranking. Applied to a large number of tasks (including reading comprehension, commonsense reasoning, mathematical problem-solving, and assistive dialog), equilibrium-ranking consistently improves performance over existing LM decoding procedures. These improvements are sometimes substantial—on multiple benchmarks, we observe that applying equilibrium-ranking to LLaMA-7B outperforms the much larger LLaMA-65B and PaLM-540B models.

Published as a conference paper at ICLR 2024
THE CONSENSUS GAME: LANGUAGE MODEL GENERATION VIA EQUILIBRIUM SEARCH
Athul Paul Jacob
Yikang Shen MIT-IBM Al Lab
Gabriele Farina MIT
Jacob Andreas MIT
MIT
ABSTRACT
When applied to question answering and other text generation tasks, language models (LMs) may be queried generatively (by sampling answers from their output distribution) or discriminatively (by using them to score or rank a set of candidate outputs). These procedures sometimes yield very different predictions. How do we reconcile mutually incompatible scoring procedures to obtain coherent LM predictions? We introduce new training-fres game-theoretic procedure for language model decoding. Our approach casts language model decoding regularized imperfect-information sequential signaling game-which we term the CONSENSUS GAME in which a GENERATOR seeks to communicate abstract correctness parameter using natural language sentences to DISCRIMINATOR. We develop computational procedures for finding approximate equilibria of this game, resulting in a decoding algorithm we call EQUILIBRRTUM-RANKINGG Applied to a large number of tasks (including reading comprehension, commonsense reasoning, and dialog), E
mathematical problem-sol and sometimes substantially, improves performance over existing LM decoding procedures on multiple benchmarks, we observe that applying EQUILIBRIUM- RANKING LLaMA-7B outperforms the much larger LLaMA-65B and PaLM- 540B models. These results highlight the promise of game-theoretic tools for addressing fundamental challenges of truthfulness and consistency in LMs.
consistently,
INTRODUCTION
Current language models (LMs) perform quite well on some tasks involving generation or verification of factual assertions- -isertions-includiing innluding question answering, fact-checking, and even unconditional text generation. But they are far from perfectly reliable, and there is increasing evidence that LMs actually grow more prone to generating false but frequently repeated statements with increasing scale (McKenzie et al., 2023). Further complicating matters, LMS offer multiple affordances for solving factual generation tasks. They may be used both generatively (e.g. by asking for the most probable answer to question) discriminatively (e.g. by presenting (question, answer) pair and asking whether the answer is acceptable) and, these two procedures do not always produce consistent results: generative procedures may fail when probability mass is spread across multiple contradicting answers (Wang et al. 2022 Mitchell et af.) 2022). while discriminative procedures may fail due to miscalibration (Han al. [0022] Chen et al. 2022 or subtle dependence on question wording (Jiang et al. 2020). Given these noisy and often-conflicting signals, how should we distill out an LM's best guess the truth?
This paper presents an approach for reconciling generative and discriminative LM decoding proce- dures by formulating decoding as a signaling game (Lewis, 20088 that we call the CONSENSUS GAME. At a high level, this game features GENERATOR agent that must communicate an abstract correct or incorrect value to a DISCRIMINATOR agent, but may only do so using a set of candidate natural language strings (Fig. D. Intuitively, an effective strategy for this game (i.e. joint policy) is one in which the GENERATOR and DISCRIMINATOR agree on the assignment of strings to correctness values. Given such strategy, we may inspect it to identify candidates agreed by consensus to be correct.
Doing so requires solving multi-step game with a complex (string-valued) action space. In recent years, ro-regr learning algorithms have emerged the preferred technique to compute effective
"Correspondence apjacob mit.cdu

---

Published as a conference paper at ICLR 2024
@ where was Barack Obama born?
GENERATOR
DISCRIMINATOR
correct
incorrect
Honotuiu
ie Honolube
corт.
Chicago
22 Chicago
corr.
incorr.
de Natrobs
incorr.
Yiu sure
It
Hanofula
Nairodu
ARIZED EQUILIBRIUM SEARCH
FQUI ARRRUM-RAAKKIEE RANKING
Honodalu
Chicago
corr.
incorr.
incorr.
Naimbii
I'm not sure
(1, (0, 0)
(1, 1) (0.
(0, (),0).
(0, (1.
Figure I: (Left) Overview our approach. Differing LM queries fail to exhibit consensus about the answer to a factual question. By reconciling predictions between generative and discriminative LM queries using the CONSENSUS GAME, obtain accurate prediction. (Right) Structure of the CONSENSUS GAME, a two- player sequential signaling game with imperfect information. First, the environment (N) uniformly samples correctness parameter. GENERATOR (G) conditioned on this parameter produces a natural language string from a set of candidates. The DISCRIMINATOR (D) only observes this string and must predict the correctness parameter sampled by environment. If the DISCRIMINATOR correctly identifies this parameter, then both players receive reward of 1. The dashed line connects nodes that are indistinguishable by the DISCRIMIN ATOR, since the DISCRIMINATOR does not observe the correctness parameter. By computing regularized equilibrium strategies for this game, we obtain predictions that reflect consensus between the GENER and DISCRIMINATOR.
strategies for such games, and have been successfully deployed in Poker (Brown & Sandholm 2018: 2019). Stratego (Perolat et al., 2022). and Diplomacy (Bakhtin et al., 2023 FAIR al. 2022 Jacob et al. 2022). Here, we show that they can also be applied to free-form language generation tasks. We call this game-theoretic approach to LM decoding EQUIL
Applied in
question answering benchmarks: MMLU (Hendrycks et al., 2020), ARC (Clark et al. 2018), RACE (Lai et al. 2017). HHH (Askell et al. 2021). TruthfulQA (Lin al., 2022) and, GSM8K (Cobbe et al.) 2021) EQUILIBRIUM: RANKING offers substantial improvements over existing generative, discriminative, and mixed decoding procedures. More generally, our results highlight the usefulness of the game-theoretic toolkit for formalizing and improving coherence in LMs. Improved coherence in turn leads to improved accuracy on factual tasks.
2 LANGUAGE MODEL CONSENSUS AS EQUILIBRIUM SEARCH
We study the problem obtaining correct output from a language model, which maps input strings output strings y according to some distribution PLM(y) z). While the techniques present here are general, we focus in this paper on question answering problems consisting of a query x (In which of the following cilies was Barack Obama born?) and set of candidate answers y (Honolula, Chicago, ... which may themselves have been sampled from the complete PLM( v). Given a set of candidates, we may use them with LM in (at least) two ways:
Generatively, by supplying input (i) the query x, (ii) the of candidates V, and (iii) natural language prompt indicating that a correct answer is desired. In this case, the LM may be thought of modeling distribution AM(y the fact that the model was prompted to generate a correct answer.
correct), where the token correct denotes
Discriminatively, by supplying as input (i) the query x and (ii) a possible candidate an- swer y E V, together with (iii) a prompt indicating that correctness assessment fcorrect, incorrect] is sought. In this case, the language model acts as a model of as modeling distribution RM(v x, y) where v E {correct, incorrect).
These two approaches conceptually equivalent. But noted in the introduction, current LMs may give very different answers when queried these different ways: answers produced generatively might be assessed incorrect with high probability vice-versa. Research on LMs has proposed
2

---

Published as a conference paper at ICLR 2024
two broad solutions to this problem. Ensembling methods (Ouyang al. 2022 Li & Jurafsky 2016
Glaese et al., 2022) simply combine discriminative and generative scores directly. While moderately often poorly calibrated both within and across contexts, meaning that scores may not combine in meaningful or consistent ways.
effective, such approaches suffer from the fact that LM predictions
Deliberation methods (Wei et al.) [022 Yao al. 2023 Du et al. (023) perform this reconciliation within the LM itself, e.g. by re- re-prompting with competing inputs and an instruction to generate a textual justification for the best one. Such methods incur significant computational overhead
How might we design a principled and computationally efficient procedure for obtaining a "consensus" between competing LM predictions? Informally, a consensus prediction would satisfy two key properties: coherence (generative and discriminative scoring procedures should agree about which candidate answers are correct) and reasonableness (predictions should not arbitrary, but instead as close as possible to original generator / discriminator behavior). The key idea in this paper is to operationalize these high-level desiderata in language of game theory, using regularized equilibrium concepts as formal framework for defining both coherence and reasonableness. Below, we introduce and explain this framework in detail, describing how to instantiate decoding as a signaling game, then compute equilibrium strategies of this game to obtain consensus LM predictions.
2.1 THE CONSENSUS GAME
Our approach to language generation begins by formulating language generation as signaling game (Lewis) 2008) that we call the CONSENSUS GAME. The CONSENSUS GAME is played on game tree, as depicted in Figure 1 At the start of the game (that is, at the root of the game tree), a correctness parameter
|correct, incorrect] } is selected uniformly at random by the environment. The correctness parameter is observed only by the GENERATOR, and controls whether the GENERATOR should aim to generate correct or incorrect answers. Upon observing this parameter, the GENERATOR produces natural language string from a fixed set of candidates. Finally, this string is observed by the DISCRIMINATOR, who tries to guess the value of the correctness parameter by selecting one of {correct, incorrect] 1 if the DISCRIMINATOR correctly identifies the value of the correctness parameter, 0 otherwise.
answer. Both players obtain payoff' of
With this definition, it may be observed that players' expected utilities (the payoff's they may expect to receive) are as follows:
ua ua TD)
=
Σ of { incorreet)))))ett yEy
Σ
Taly (,, Tp x,
2
up (TG, TD)
1
Σ
Σ
Ta 1, TD xx,)).
ve (ncrrect, DEy
What is an effective strategy for maximizing these utilities? A standard answer to this question in the game theory literature is that Nash equilibrium of the game should be sought. A Nash equilibrium is a pair of policies-one one for the GENERATOR and one for the DISCRIMINATOR-SUA that each policy is optimal. That is, each player's strategy maximizes their expected given the other player's s strategy. At a Nash equilibrium, no player has an incentive to unilaterally behave in any other way. In signaling games, Nash equilibria offer natural way of formalizing the coherence criterion above: at equilibrium, both the GENERATOR and DISCRIMINATOR must agree about which messages correspond to correct and incorrect respectively in order to obtain a nonzero payoff.
However, Nash equílbria of the CONSENSUS GAME are not guaranteed to provide the second criterion of reasonableness. This is because the CONSENSUS GAME admits a multitude of Nash equilibria that are incompatible with the common-sense notion of truthfulness. For example, the strategy in which the GENERATOR deterministically maps correct + "Nairobi", incorrect + "Honolulu", and the DISCRIMINATOR maps "Nairobi" correct, "Honolulu" + incorrect forms Nash equilibrium.
In order to sidestep the inappropriate equilibria and ensure reasonableness, we introduce a regular- ization term in the utility of the players, so that both the GENERATOR and the DISCRIMINATOR penalized for settling on strategics that are far from some pair of initial policies: T and TD (1) By parameterizing these policies using a pre-trained LM, we may knowledge about what answers
As shown in Section they also orthogonal to, and composable with, the approach we propose here.
3

---

Published as a conference paper at ICLR 2024
likely to be correct priori to guide selection of an equilibrium. As in Jacob et al. (2022), incorporate this regularization term directly into the utility function (payoff) that the GENERATOR and DISCRIMINATOR attempt optimize. Rather than the simple 0-1 payoff determined by agreement on the correctness parameter, they now attempt to optimize:
(TG. TD) == -A DKL[TO(- v2 || TG ( 1 2,, 0],
To(y x, v) xD( Ir, xr, y),
2
PEY
(T TD) == -KLL(TDD v. || ( x2,0]
Σ 2 Σ
Te x, u. x v).
2
(1) Note that the initial policies "G (y v) and " (v x. v) may be derived from an LM prompted with some initial string 2; in order to obtain context-rrediction (e.g. answers to question). With these utilities, Nash equilibria for the game are pulled by the initial GENERATOR and DISCRIMINATOR policies in the direction of increased consensus.
Bakhtin al. 2023 and FAIR al. (022) employed a similar regularization method for choosing actions, rather than messages, in versions of the board game Diplomacy, Franke (2013) 2017) have explored signaling games the context of linguistic pragmatics to explain human language use. To the best of our knowledge, however, this is the first proposal for using regularized equilibrium concepts in signaling games to define target behavior in a language generation task. Additional related work is discussed in Appendix
2.2 EQUILIBRIIUM-ANKTII LM RANKING VIA EQUILIBRIUM SEARCH
With this formulation, text generation requires finding a Nash equilibrium of the game with the utilities given above. How should we compute such equilibrium? No-regret learning algorithms have emerged in recent years as the preferred technique to approximate equilibria in large games, and have been successfully employed solve games at human even superhuman level. At high level, these algorithms find equilibrium by repeatedly interacting in the game and refining their policies after each iteration t. so as to minimize regret (the gap between the chosen action and the best action in hindsight).
In this section, we describe in detail how to perform no-regret learning in the CONSENSUS GAME in order to obtain consensus policies. Importantly, this approach modifies only signalling policies, and not the base policies m and =D (i.e. the LM). In this sense, generating text by performing no-regret learning in the CONSENSUS GAME might be described as training-free consensus-plaming method. We call this method SAILLIBRRUM-RANKKAN
Initial policies At time 1, that is, before any equilibrium computation has happened, EQUILIBRIUM- RANKING defines the initial policies TG and ( of the GENERATOR and DIS- CRIMINATOR, respectively, follows. TG
(1) normalizes PLM across and y:
PLM(U x,,))
(y 2200 x Ee PLM( x, x,,²)
Similarly for the DISCRIMINATOR, the initial policy normalizes across y and u:
PLM(U v.
(1) (v x, v) x Ey PLM(U x, x,,""
This crucial step enables us extract well calibrated GENERATOR and DISCRIMINATOR from PLM- The specific form of the GENERATOR incorporates v = incorrect, and this is therefore a form of self-contrastive decoding (See, Section for more details). This DISCRIMINATOR resembles approaches that query the LMM itself to produce critiques (Cianguli et al., 2023 Chen et al.) 20236] Yao al. 2023). However, the best of our knowledge, this specific instantiation has not been explored in the past.
In ARC, RACE, HHH, TruthfulQA, and GSMSK, based on prior work (Tourron et al. 2023 Brown et al. 2020), we additionally normalize (uu(u)z) by the likelihood of the completion given "Answer:" context:
Fuutu "Answer:").
4

---

Published as a conference paper at ICLR 2024
Evolution of policies A classic observation in the theory of snperfect-informatiee sequential games that minimization of regret (viewed as a function of their overall policy on the game tree) can be achieved by solving separate, local, regret minimization problems at each information set (i.e., decision point) the game. This observation underpins the CFR framework (Zinkevich et al. 2007). well its generalization more general convex losses, known as laminar regret decomposition (Farina et al. 2.19). In our case, these techniques enable us to decompose the policy update of the players into separate updates for each correctness parameter v (for the GENERATOR) and for each sequence y (for the DISCRIMINATOR), We provide more detail and background in Appendix A
In our setting, after operating the regret decomposition step, we find that the local regret minimization problems are composed of bilinear term, plus a strongly convex KL-regularization term. Such composite utilities can be handled by the piKl. algorithm (Jacob et al. 2022), which is specifically designed to perform regret minimization on KI.rregularized objectives. In our setting, piKL. prescribes that each player keep track of their average values:
xr v) = 21
"D (7)
x, v),
O x,,) =
T (1)
(y xz, v).
2/
Each player then updates their policy according to:
La (y v) + A log TG (2) | v)
TG
(++1)
x,
x exp
(1)
1/(na()) + Ag
2 x, v) + Ar log TD (v) x,,) 1/(mp() +AD
TD (++1)())) v,,y) exp
where 7a, 1TD 0 are learning rate hyperparameters, piKL no-regret dynamics known to have strong guarantees, including the following (more formal statements about the guarantees are available in Appendix AA:
Convergence to an equilibrium point. The average correlated distribution of play of GENER- ATOR and DISCRIMINATOR converges the set of (regularized) coarse- correlated equilibria of the game.
Regularization toward reasonableness, The average policy of any player remains within
radius of size roughly 1/A, from the initial policy x where X is the amount of regularization applied to any player E {GENERATOR, DISCRIMINATOR/ (see Proposition 3).
Avoidance of regret. The cumulative regret incurred by each of the players grows only logarithmic in the number of training steps (see Proposition D
At convergence, EQUILIBRIUMA WEIILIBRUUMRAANN -ANUING returns TG and Tp", which are the refined GENERATOR and DISCRIMINATOR. While do not provide formal guarantee of convergence, we remark that the CONSENSUS GAME is an instance of potential game (Monderer & Shapley 1996), for which it generally understood that decentralized no-regret learning dynamics similar piKL converge in iterates to equilibrium (Anagnostides et al. 2022). Indeed, we witness good convergence properties in practice even without any perturbation. As mentioned earlier, convergence to a regularized Nash equilibrium is important to guarantee both coherence and reasonableness. Extensive empirical validation presented in the next section demonstrates the benefits of this approach practice.
Computational cost of our method. At each iteration, method needs to update the policies Q0 20 according to and 2). The number of operations at each iteration of the method is therefore linear in the number [}] of sequences available to the GENERATOR.
3 EXPERIMENTS
As discussed in the previous section, EQUILIBRIUM-RANEEN focuses on improving the correctness of language models in question-answering (QA) tasks. However, correctness manifests in various forms across different domains, including truthfulness, factuality, valid reasoning, value alignment, among others. Therefore, we will evaluate its performance on a diverse set of QA tasks: MMLU (Hendrycks et al. 2020 ARC (Clark al. 2018), RACE (Lai al. 2017). HHH (Askell et al.
5

---

Published as a conference paper at ICLR 2024
2021), and TruthfulQA (Lin al. 2022). It's important note that EQUILIBRIUM RANKIIN is
sampling strategy and not a delibration method like of-thuhttthhhhhhtcc (CoT) (Wei et al. 2022) and self-consistency (Wang et al., 2022). Nevertheless, we will demonstrate in GSM8K (Cobbe et al.
2021) that we can achieve some additional gains when combining FQUIL.BRIUM-RANNE with seff-consistency and COT.
Hyperparameters EQUIL BOOLLBBRIUMRANKR has four parameters, 1/D, Ap and rja λo. Although tuning these parameters will lead to better performance, in all our experiments we set d/ = Ao V AG 0.1. We BRUUIIIBRIUM-RAKKIII for 5000 iterations
Actions in the CONSENSUS GAME As mentioned in Section in order make our approach amenable to current computational techniques, we make the modeling assumption that the GEN- FRATOR picks distribution over finite set of candidates y. In multiple-choices tasks, these the multiple choice options. In generative tasks, a common approach to generate the finite set of candidates is via sampling with nucleus (Holtzman et al. 2019) and top-k (Fan al., (018b) from the distribution PLM(y | q, correct) where E y. This is exactly the approach we use in our experiments, with p = 0.9 for nucleus sampling and k 50.
Models We use the 7B and 13B parameter models from the LLaMA family (Touvron al. 2023 and perform 16-bit inference for all our experiments.
Prompting for correct and incorrect answers In our work, unless otherwise specified, con- ditioning on (z, correct) for the PLM corresponds to the standard zero-shot prompt. Similarly, conditioning on (z, incorrect) is similar to (æz, correct) with the only difference that "Answer:" replaced with "Incorrect Answer:" " in the prompt.
Decoding Methods In the multiple-choice based datasets (ARC, RACE, HHH MMLU), consider the following approaches:
Generative Ranking (G): This baseline (Brown et al. 2020 Touvron et al. 2023) ranks every candidate y by PLM(y æ, correct) and picks the top candidate. This the standard approach used in past work. Due to implementational differences, when available, we include both official scores and our version.
This mutual-information based (Li & Juratsky 2016) bascline is ensemble-based approach that reweights every candidate y by PLM(y r, correct) P.m(coreect y).
Mutual Information Ranking (MI):
(1) Self-Contrastive Ranking (SC); This approach utilizes the normalized generator "G to reweight every candidate by To (correct x, v).
Discriminative Ranking (D): This approach reweights every query-candidate pair (ar, v) by (1) (correct v)
TD
Equilibrium Ranking Generator (ER-G): Similar to SC, this approach utilizes the fi-
nal BQUILIBRIUMMRANN WEEMM--RNKING--aR generator ā reweight every candidate y by T& (s) r, correct).
Equilibrium Ranking Discriminator (ER-D): Similar to D, this approach utilizes the fi- nal BOQUIIBBRIUM-RAKKISE based discriminator T.- This approach reweights every query- candidate pair (z, v) by #f(correct æ, v).
In free-form text generation tasks (TruthfulQA, GSM8K), we additionally consider greedy decoding. In the mathematical reasoning task (GSM8K), we also consider self-consistency (Wang et al. 2022).
3 As remarked at the end of the previous section, each iteration of the learning process requires number of floating-pont point operations that is linear in the number [}] available to GENERATOR. In most our settings, |! 4, making the overhead from the learning dynamics on the CONSENSUS GAME negligible compared to the cost of inference for the language model. As such, even with an unoptimized implementation of the dynamics
I we observe that the computational cost assnciated with each iteration of the leamning process takes about
40 microseconds on average.

---

Published as a conference paper at ICLR 2024
Equil. ranking
Domain
Model
G
G
MI
SC
D
ER-G
ER-D
LLaMA-7B
30.4
33.1
30.5
40.4
39.4
39.9
MMLU
LLaMA-13B
41.7
41.8
41.7
41.9
44.9
45.1
ARC
LLaMA-7B
72.8
68.2
68.8
69.5
52.5
71.6
71.5
Easy
LLaMA-13B
74.8
71.2
71.5
73.0
65.0
76.1
76.4
ARC
LLaMA-7B
47.6
47.3
47.4
56.5
42.7
58.7
58.3
Challenge
LLaMA-13B
52.7
51.9
52.1
59.3
48.5
61.1
61.4
RACE
LLaMA-7B
61.1
57.7
57.7
60.4
51.5
63.2
63.5
Middle
LLaMA-13B
61.6
60.1
60.2
64.8
58.3
67.9
68.6
RACE
LLaMA-7B
46.9
46.4
46.3
53.1
46.0
56.3
56.4
High
LLaMA-13B
47.2
47.9
48.4
58.9
55.1
62.1
62.8
LLaMA-7B
59.3
57.9
67.4 .4.4
70.1
71.5
71.5
HHH
LLaMA-13B
60.2
59.7
57.9
69.2
61.1
61.1
Table I: Results of the different approaches across multiple tasks. We compute the accuracies on the test set of these benchmarks. EQUILIBRIUM MAMMA-AANNNGGG outperforms other approaches most tasks. EQUILIBRIUM- RANKING performs well, even cases where one of GENERATOR or DISCRIMINATOR is far worse than the other. G: Generative Ranking, MI: Mutual Information Ranking. SC: Self-Contrastive Ranking, Discriminative Ranking, ER-G: Equilibrium Ranking Generator, ER-D: Equilibrium Ranking Discriminator. indicates the results from Touvron al. (2023). Colors in the table entries assigned relative to the G baseline, according the colorbar
(differences exceeding 10 clipped +10 when calculating the colors).
The massive multi-task language understanding benchmark (MMLU) (Hendrycks et al.) 2020) is used to measure language model's 's multitask accuracy. It consists of questions in the multiple choice format across wide variety subdomains social sciences, humanities and STEM. We
MMLU
evaluate models in the zero-shot setting following the format described in Henddrycks et al. (2020); Touvron al. (2023) and the results are presented the first row of Table For both LLaMA- 7B and LLaMA-13B, the EQUILIBRIUM- LANKING-based approaches matches outperforms all other baselines. In fact, zero-shot LLaMA-7B with ER-D (39.9) outperforms 5-shot LLaMA-7B (35.1), while zero-shot LLaMA-13BB with ER-D (45.1) is competitive with 5-shot ILLMMA-13B (46.9). LLaMA-7B with ER-D (39.9) even outperforms zero-shot GPT3-175B (37.7) (Hendrycks al. 2020), while zero-shot LLaMA-13B with ER-D (45.1) outperforms 5-shot GPT3-175B (43.9)
(Hendrycks et al. 2020
The A12 Reasoning Challenge (ARC) (Clark et al. 2018) is an advanced question answering dataset used study model's knowledge and reasoning abilities based grade school science questions. It is split in to two subcategories: easy (ARC-Easy) and challenge (ARC-Challenge). The challenge set was constructed the set of questions that were answered incorrectly by retrieval and word co-occurence based algorithms. The results are presented in second and third rows of Table [ ARC-Easy, ER-D outperforms our implementation of generative ranking. We also note that LLaMA-13B with ER-D (76.4) outperform all the baseline approaches and is even competitive with the much larger PaLM-540B model (76.6) (Chowdhery et al. 2022). On ARC-Challenge, ER-D significantly outperforms all the baseline approaches. We also note that LLaMA-7B with ER-D (58.3) and ALLMMA-13B with ER-D (61.4) outperforms even the much larger models: LLaMA-65B
ARC
(56.0) Touvroo et al. 2023) and PaLM-540B (53.0) (Chowdhery al. 2022 by up to 8%. Finally, we also compare agansst concurrent work on contrastive decoding (CDO'T Brien & Lewis (2023);
Li al. (002)). On ARC-Easy, LLaMA-13B ER-D (76.4) is competitive with the much larger
7

---

Published as a conference paper at ICLR 2024
Equil. ranking
Domain
Model
Greedy
MI
SC
D
ER-G
ER-D
LLaMA-7B
33.41
34.79
34.91
34.17
34.61
34.27 + 0.39
0,90
= 0.57
+ 1.19
+.99
TruthfulQA
LLaMA-13B
33.05
36.30
34.61
39.05 1. 1.42
39.83
38.63 d. 1.76
0.37
1: 1.33
2:20
Table 2: Results TruthfulQA (Generative). Average BLEU-Ace results the held-out across runs. LLaMA-13B with ER-G outperforms is on par with all baselines. MI: Mutual Information Ranking, SC: Self- Contrastive Ranking, D: Discriminative Ranking, ER-G: Equilibrium Ranking Generator, ER-D: Equilibrium Ranking Discriminator. + indicates I standard deviation computed across 5 runs. Colors are as in Table relative to the Greedy baseline.
LLaMA-65B CD (8 = 1.0) (76.9). On ARC-C, additionally note that LLaMA-13B + ER-D (61.4) outperforms LLAMA-65B + CD (3 = 1.0) (59.7).
RACE RACE reading comprehension benchmark introduced in Lai al. (2017) collected from English examinations of middle and high school students. The dataset is correspondingly split into RACE-middle and RACE-high. The dataset consists of a passage followed by questions. The passages were constructed for evaluating student's 's English reasoning and understanding ability. The results on this benchmark is presented in rows 4 and 5 of Table [ On RACE-middle, like before, ER-D based models outperforms all the baselines. We note that 1.aMA-13B with ER-D (68.6) even outperforms much larger models: L.LaMA-6BB (67.9) (Touvron et al. 2023) and MM--MB00B (68.1) (Chowdhery et al. 2022). On RACE-high, we have similar story with ARC-C. ER-D outperforms all baselines. LLaMA-7B with ER-D (56.4) is able to significantly outperform much larger models:
LLaMA-65B (51.6) (Touvron al. 2023 and PaLM-540B (49.1)
(Chowdhery al. 2022
HHH HHH (Helpful, Honest and Harmless) (Srivastava et al. 2023 Askell et al. 202I) is a dataset of 200 multiple-choice designed to measure LM alignment with high-level quality guidelines. Here we use a different set of prompts for the GENER ATOR (see Appendix [). Results are presented in the last row of Table LLaMA-7B with ER-D outperforms baselines; although LLaMA-13B with ER-D with the default parameter performs worse than discriminative ranking (D) (69.2), ER-D with
AG 0.01 and AD 1.0 achieves an accuracy of 70.6%.
TruthfulQA TruthfulQA (Lin et al. 2022 is a benchmark consisting of over 800 questions across multitude of domains that were crafted to encourage humans to answer them incorrectly due to misconceptions. The dataset evaluates model's ability to not generate false answers learnt from imitation learning on text. On this task, we consider greedy decoding in addition to our other ranking-based approaches. In this setting, 10 candidate sequences are sampled using nucleus and top-k sampling. These candidates are then ranked based on the approaches we described earlier. The results the test set are presented in Table 2 Based past work (Lin al. 2022), measure BLEU accuracy (BLFEUAccc). For a sequence o, the BLEU-Acc over reference correct candidates Deonect and reference incorrect candidates beomea computed follows:
BLEU-Acc(a) = I(BLEU(a, beorret) > BLEU(a, bincorrce))
Where BLEU(a, b) computes the BLEU score (Papineni et al. 2002) of a candidate string a over of reference candidates b. With LLaMA-7B, we observe only modest improvements for ER-G and ER-D over the greedy baseline. However, with LLBMA-13B, we note increased scores for both methods. This benchmark known to exhibit negative scaling (Lin et al., (022) (performance drop the model size increases). The performance difference with ER-G between LLLMA-7B and LLaMA-13B shows that KQUTI.IBRIUM-RANE
fact capable of mitigating this behavior.
GSM8K In our last set of experiments, we consider grade-school math (GSM8K) (Cobbe et al. 2021), a popular benchmark used to study model's mathematical reasoning ability. We use this combine
approach with chain-of thain-of-tee offthhutgttttt (Wei et al. 2022 As we described earlier. we generate 20 candidate reasoning paths sampled using nucleus and top-
benchmark to study whether
using the 8-shot setup proposed in Wei et al. (2022). We employ self-consistency (Wang al. 2022
8

---

Published as a conference paper at ICLR 2024
Equil. ranking ER-G
Domain
Model
Greedy
MV
MI
SC
D
ER-D
LLaMA-7B
10.8
14.7
14.6
13.4
15.0
13.0
15.1
0.2
0.5
0.3
0.6
#05
GSM8K
LLaMA-13B
14.9
22.5
22.5
23.1
22.5
22.5
23.0
-
0.8
0.5
0.6
Table 3: Average accuracy of methods the set of GSM8K acroos 5 runs. In all cases, except greedy, SAAARRUMM-AAKKI--DbbCSS. approaches performs on par or slightly better
20 candidates sampled. compared to the majority vote baseline. MV: Majority Vote, MI: Mutual Information Ranking, SC: Self- Contrastive Ranking, D: Discriminative Ranking, ER-G: Equilibrium Ranking Generator, ER-D: Equilibrium Ranking Discriminator. 1 indicates standard deviation. Colors are as in Table [ relative to the Greedy basline.
the candidate sequences, where score each reasoning path with our baselines. Finally, aggregate the scores for each answer corresponding to the reasoning paths and pick the answer with the highest score. In Table we present the results. We note that approaches performs on par or slightly better compared to self-consistency (majority vote).
PARIUM-RNNKING
Discussion The application of EQUILIBRIUM RANKING-based approaches consistently yields improved results, surpassing or at least matching the performance of all baseline approaches across various tasks. This robustness is particularly interesting, as it demonstrates that EQUILIBRIUM- RANKING is adept at handling diverse scenarios, even in situations when the initial GENERATOR or DISCRIMINATOR are effective. As EQUILIBRRIMM- RANKING a sampling strategy. it can even be combined with deliberation methods like self-consistency (Wang et al. 2022) tree-of-thought (Yao ct al. 2023). Finally, we note that WUULLBBRUUMRANKKOE demonstrates computational efficiency by eliminating the need for repetitive queries to language models.
ACKNOWLEDGEMENTS
This work was supported by the National Science Foundation under grant IIS- IIS-2212310 and a seed grant from the MIT Schwartzman College Computing "Artificial Intelligence for Augmentation and Productivity" program.
4 CONCLUSION
We have presented EQUILIBRIUMRRAKKING training-free game theoretic approach for gener- ating from language models (LMs). EQUILIBRIUM RANKING reconciles scores from generative and discriminative LM decoding procedures by formulating decoding as an imperfect-informalie signaling game between a GENERATOR and a DISCRIMINATOR, and leveraging computational game solving techniques compute approximate equilibria of this game. When applied to 6 di- verse question answering benchmarks: MMLU, ARC, RACE, HHH, TruthfulQA and, GSM8K, BBULLIBRIMMRANNER
offers substantial improvements over existing generative, discriminative, and mixed decoding procedures: applying EQUILIBRIUM PIBBRIUMRRNKIIA RANKING to LLaMA-7B sometimes out- performs much larger LLaMA-65B and PaLM-5400 models. These results highlight the usefulness of game-theoretic tools in formalizing desiderata like truthfulness and stability in language modeling. Beyond the applications studied here (which focus mainly question answer), future work might apply this toolkit to more general tasks like long-form text generation.
REFERENCES
loannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning, 2022.
Amanda Askell, Yuntao Bai, Anna Chen, Dawn Drain, Deep Ganguli, Tom Henighan, Andy Jones, Nicholas Joseph, Ben Mann, Nova DasSarma, et al. A general language assistant as a laboratory for alignment. arXiv preprint 2 2021.

---

Published as a conference paper at ICLR 2024
Anton Bakhtin, David J Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexan- der H Miller, and Noam Brown. Mastering the game of no-press Diplomacy via numan-regularizee reinforcement learning and planning. In The Eleventh International Conference Learning Representations, 2023.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-444) 2018.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.. 2020.
Justin Chih-Yao Chen, Swarnadeep Saha, and Mohit Bansal. Reconcile: Round-table conference improves reasoning via consensus among diverse llms. arXiv preprint arXiv:2309. / 2023a.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint arXiv:230.005128, 2023b.
Yangyi Chen, Lifan Yuan, Ganqu Cui, Zhiyuan Liu, and Heng Ji. A close look into the calibration of pre-trained language models. arXiv preprint XXXx:2211.00052: 2022.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 2022.
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv: 1803.08035.555 2018.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems, 2021.
David Dohan, Winnie Xu, Aitor Lewkowycz, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A Saurous, Jascha Sohl-Dickstein, et al. Language model cascades. arXiv preprint wwXiv:2207.10344 2022.
Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch. Improving factual- ity and reasoning in language models through multiagent debate. arXiv preprint TrXXi:2305.14325 2023.
Meta FAIR, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al. Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science, 37866624):0067-11
2022.
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics VVolume 1: Long Papers), pp.
Melbourne, Australia, July 2018a. Association for Computational Linguistics. doi: 10. 1/P118 1082. httphttts://acceeee
hrtp 1082
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 889-898, 2018b
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for sequential decision processes and extensive-form games. In AAAI Conference Artificial Intelligence (AAAJ), 2019.
Michael Franke. Game theoretic pragmatics. Philosophy Compass, 8(3):699-244, 2013.
10

---

Published as a conference paper at ICLR 2024
Michael Franke. Game theory in pragmaties: Evolution, rationality, and reasoning. In Oxford Research Encyclopedia of Linguistics. 2017.
Deep Ganguli, Amanda Askell, Nicholas Schiefer, Thomas I. Liao, Kamilè Lukošiūté, Anna Chen, Anna Goldie, Azalia Mirhoseini, Catherine Olsson, Danny Hernandez, Dawn Drain, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jackson Kermion, Jamie Kerr, Jared Mueller, Joshua Landau, Kamal Ndousse, Karina Nguyen, Liane Lovitt, Michael Sellitto. Nelson Elhage, Noemi Mercado, Nova DasSarma, Oliver Rausch, Robert Lasenby, Robin Larson, Sam Ringer, Sandipan Kundu, Saurav Kadavath, Scott Johnston, Shauna Kravec, Sheer EI Showk, Tamera Lanham, Timothy Telleen-Lawton, Tom Henighan, Tristan Hume, Yuntao Bai, Zac Hatfield-Dodde Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, Christopher Olah, Jack Clark, Samuel R. Bowman, and Jared Kaplan. The capacity for moral self-correction in large language models, 2023.
Amelia Glaese, Nat McAleese, Maja Trebacz, John Aslanides, Vlad Firoiu, Timo Ewalds, Maribeth Rauh, Laura Weidinger, Martin Chadwick, Phoebe Thacker, et al. Improving alignment of dialogue agents via targeted human judgements. arXiv preprint arXiv:2209. 14377, 2022.
Zhixiong Han, Yaru Hao, Dong, Yutao Sun, and Furu Wei. Prototypical calibration for few-shot learning of language models. In The Eleventh International Conference on Learning Representa- tions, 2022.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Conference on Learning Representations, 2020.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. International Conference on Learning Representations, 2019.
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:
Athul Paul Jacob, David J. Wu, Gabriele Farina, Adam Lerer, Hengyuan Hu, Anton Bakhtin, Jacob Andreas, and Noam Brown. Modeling strong and human-like gameplay with kl-regularized search. In International Conference on Machine Learning, 2022.
Zhengbao Jiang, Frank Xu, Jun Araki, and Graham Neubig. How can we know what language models know? Transactions of the Association for Computational Linguistics, 8:423-434 2020.
Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard Hovy. Race: Large-scale reading comprehension dataset from examinations. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 785-794, 2017.
David Lewis. Convention: philosophical study. John Wiley & Sons, 2008
Jiwei Li and Dan Jurafsky. Mutual information and diverse decoding improve neural machine translation. arXiv preprint arXiv:1601 160.000700. 2016.
Xiang Lisa Li, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettlemoyer, and Mike Lewis. Contrastive decoding: Open-ended text generation as optimization. arXiv preprini 10Xiv:2210.1500 2022.
Stephanie Lin, 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), pp. 3214-3252, 2022.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye. Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback, 2023.
11

---

Published as a conference paper at ICLR 2024
Ian R McKenzie, Alexander Lyzhov, Michael Pieler, Alicia Parrish, Aaron Mueller, Ameya Prabhu, Euan McLean, Aaron Kirtland, Alexis Ross, Alisa Liu, et al. Inverse scaling: When bigger isn't better. arXiv preprint arXiv:2306.0940 09479, 2023.
Clara Isabel Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. Locally typical sampling. Transactions of the Association for Computational Linguistics, 1 11:102-121, 2023.
Eric Mitchell, Joseph Noh, Siyan Li, Will Armstrong, Ananth Agarwal, Patrick Liu, Chelsea Finn, and Christopher D Manning. Enhancing selffconsistency and performance of pre-trained language models through natural language inference. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 1754-1768, 2022.
Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 1(14): 124-143, 1996.
Sean O'Brien and Mike Lewis. Contrastive decoding improves reasoning in large language models. arXiv preprint wrXiv:2309.09117 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318, 2002.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, (78(6623) 996, 2022.
Jianhao Shen, Yichun Yin, Lin Li, Lifeng Shang, Xin Jiang, Ming Zhang, and Qun Liu. Generate rank: A multi-task framework for math word problems. In Findings of the Association for Compu- tational Linguistics: EMNLP 2021, pp. 2269-2279, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguisties. doi: 18255/ fiw.iings-emnll.199..... URL https::/aclantthlllse /rg/ 2021. findings-emnlp. 195
Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu
Yao. Reflexion: Language agents with verbal reinforcement learning, 2023.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga- Alonso, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research, 2023.
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Ta Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, YaGuang Li, Hongrae Lee, Huaixiu Steven Zheng, Amin Ghafouri, Marcelo Menegali, Yanping Huang. Maxim Krikun. Dmitry Lepikhin, James Qin, Dehao Chen, Yuanzhong Xu, Zhifeng Chen, Adam Roberts, Maarten Bosma, Vincent Zhao, Yanqi Zhou, Chung-Ching Chang, Igor Krivokon, Will Rusch, Mare Pickett, Pranesh Srinivasan, Laichee Man, Kathleen Meier-Hellstern, Meredith Ringel Morris, Tulsce Doshi, Renelito Delos Santos, Toju Duke, Johnny Soraker, Ben Zevenbergen, Vinodkumar Prabhakaran, Mark Diaz, Ben Hutchinson, Kristen Olson, Alejandra Molina, Erin Hoffman-John, Josh Lee, Lora Aroyo, Ravi Rajakumar, Alena Butryna, Matthew Lamm, Viktoriya Kuzmina, Joe Fenton, Aaron Cohen, Rachel Bernstein, Ray Kurzweil, Blaise Aguera-Arces Claire Cui, Marian Croak, Ed Chi, and Quoc Le. Lamda: Language models for dialog applications, 2022.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.1399) 2023.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2022.
12

---

Published as a conference paper at ICLR 2024
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thoouht prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-24833 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305. 2023.
Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret minimization in games with incomplete information. In Neural Information Processing Systems (NIPS), 2007.
13

---

Published as a conference paper at ICLR 2024
A DETAILS ABOUT REGRET AND REGRET DECOMPOSITION METHODS
After each repetition & of the game, each player-in this case, the GENERATOR and the DISCRIMINA- TOR-refines their policies, in such way that throughout the course of time, the regrets
Rege (T)
max 2
ue =
Σ
u
(0)
(0)
(4)
T
RegD
(T)
max DD
uD u (1)
xD)
u : _b))
(5)
cumulated by the players are guaranteed to grow sublinearly as function of the number of rounds of learning T.
As mentioned in the body, a classic observation in the theory of imperfect-information sequential games that minimization of regret (viewed as function of their overall policy on the game tree) can be achieved by solving separate, local, regret minimization problems at each information set (i.e., decision point) of the game. our case, these techniques enable to decompose the policy update of the players into separate updates for each correctness parameter (for the GENERATOR) and for each sequence y (for the DISCRIMINATOR). More specifically, suppose that the GENERATOR updates their policies (f) (- æz v) independently for each correctness parameter v E {correct, incorrect] they might receive, seeking independently minimize regret
Rega Rega(() (v)
0e (T= (1, (1t) (Tl 12, 2,
max T'EA(Y)
with respect to the following counterfactual utility functions
de (T 22,) = - DK Te(. 2,
10 (- (-111,200 12 + 2
Σ
σ D (o x,,) xa 2,0)
yEY
(6)
for all v. Then, it is known that when these independent goals are met for all v, is the goal of keeping regret subliner, and in particular
Rege
(T') < Rege (T) (correct) + Regg (T) (incorrect)
matter the time horizon T. Similarly, when the DISCRIMINATOR seeks update their policy x. y) for each E y independently, so as to minimize regret
(+) T
Regh (T) (v) =
(x* (x,)) (0) (0) x. (2,8) v)
max ("EaA(correctjinoonnnc)
with respect to the counterfactual utility functions
"D (TD v.
(1) DKD TD( x,
xD 2.,1)
+
1
Σ
To
(e) (v xr, v) TD(U ar, (,,)),
(carrect,,
incorrect)
then their overall regret Regh
(T) satisfies
Reg
Σ yEy
Reg (v).
The counterfactual utilities üة and üp defined above are composed of bilinear term and strongly convex Ke-reuulaiization term. To guarantee sublinear regret with respect to such utility functions, use the piKL. algorithm Jacob et al. (2022).
14

---

Published as a conference paper at ICLR 2024
A.1 GUARANTEES OF THE PIKL NO-REGRES DYNAMICS
We recall the following known properties of the piKL algorithm. An informal description of the guarantees included in Section 2
Proposition (Bakhtin et al. 2023). Let E {GENERATOR, DISCRIMINATOR) be any player.
After any T iterations of training, the regrel Reg, (T) cumulated by the policies Th of player i produced by piKI., is upper bounded by only logarithmic quantity in T. More precisely, Reg." (T) 0 min 22g TTya log ) where the asymptotic O notation hides constants A;
9i
independent on the time horizon T, learning rate of the player, and regularization coefficient X; Proposition (Folklore connection between regret minimization and equilibria). The empirical frequency of play converges to the set of coarse correlated equilibria of the CONSENSUS GAME.
Proposition (Jacob et al. 2022). The average policy | of player {GENERATOR, DISCRIMINATOR produced by piKL after T iterations is guaranteed to be within a radius proportional to X centered in the initial policy T(") More precisely, (T) ())) Xr
(()), where the asymptotic notation o(1) denotes quantity decreasing, as a function of the time horizon T, at a rate of log (A,T).
B HHH PROMPTS
In the HHH experiments, (I, correct) corresponds to the prompt: "You are a helpful, honest and harmless assistant. Human: {x} Assistant:"
And (z, incorrect) corresponds the prompt: "You are a unhelpful, dishonest and harmful assistant.
Human: (x)
Assistant:"
C OTHER RELATED WORK
Many decoding strategies have been proposed for language models, such as top-k sampling (Fan et al. 2018a), nucleus sampling (Holtzman et al.) 2020), and typical sampling (Meister et al. (023). These methods primarily focus on producing diverse, high-quality text from a language model. However, they decode from the LM without any emphasis on the correctness of the generated sequences. As we show in Section 3] EQUILIBRIUM RANKINNG naturally complementary and be combined with any of these sampling strategies.
Re-ranking is a common approach for selecting the correct answer from a set of candidates sampled from LM. Cobbe et al. (2021) train verifier re-ranked the sampled outputs. (Shen et al.) (2021) jointly train a ranking model with the generation model to improve the model accuracy. Thoppilan al. (2022) collect additional human annotations to train the ranking model for response filtering. As we discuss in Section 2 our work focuses on leveraging an existing LM and using them in training- free manner as discriminator. However, we that do make any specific assumption the specific form of a the GENERATOR or DISCRIMINATOR, As such, EQUILIBRIUM, MOULLIBRIUMRRANINGG can be combined with these approaches.
RANKING
As previously mentioned, EQUILIBRIUM-RANEN highlighted various recent work (Wei et 2022. Madaan et al., 2023) Shinn et al.) 2023 Yao et al. 2023, Dohan et al. 2022). In Section 3 we demonstrate how EQUILIBRIUM AARRIMMRANNE RANKING can be integrated with these approaches. In another line of work, Du et al. (0023) and Chen et al. (2023a) employ multiple instances of language models suggest and "debate" individual responses and reasoning processes across multiple iterations, ultimately converging on a shared final answer. In contrast, SQUILIBRIUM-RAN
differs from recent deliberation methods, as
can be viewed as variant of this multi agentt debate, wherein the "debate" occurs within the sgreet-miimiiztionn framework rather than the context of language models.
15

---

Published as a conference paper at ICLR 2024
D ADDITIONAL DISCUSSION
D.1 RELATIVE CONTRIBUTIONS OF NORMALIZATION AND EQUILIBRIUM SEARCH
To tease apart these two components of EQUILIBRIUN-RANKINGG
run an additional ablation
experiment that re-ranks using pointwise-mutual mutuall inforlatioonnotttybbel Li & Jurafsky (2016) product
(1) using G and = and rather than unnormalized generator (G) and discriminator (D) probabili-
ties. This new ablation (labled MI* in the table below) does improves performance over baseline
approaches but consistently underperforms the full SQUILIBRIUMRRAKKINN method.
Domain
Model
MI*
ER-G
ER-D
LLaMA-7B
35.8
39.4
39.9
MMLU
LLaMA-13B
43.1
44.9
45.1
LLaMA-7B
71.04
71.6
71.5
ARC-Easy
LLaMA-13B
76.1
76.1
76.4
LLaMA-7B
58.5
58.7
58.3
ARC-Challenge
LLaMA-13B
61.4
61.1
61.4
LLaMA-7B
62.8
63.2
63.5
RACE-Middle
LLaMA-133 13B
67.5
67.9
68.6
LLaMA-7B
55.9
56.3
56.4
RACE-High
LLaMA-13B
62.2
62.1
62.8
LLaMA-7B
69.7
71.5
71.5
HHH
LLaMA-13B
61.1
61.1
61.1
Table Results of different approaches across multiple tasks. In particular, consider additional bascline MI that improves performance over baseline approaches but consistently underperforms the full EQUILIBRIUM- RANKING. Colors are as in Table [
relative to the MI" ablation.
D.2 ANALYSTS OF COHERENCE
In order to look at how severe the problem of coherence between discriminative and generative methods are, perform analysis looking at how often the answers chosen by Generative Ranking (G) and Discriminative Ranking (D) disagree in each task. Table 5 shows that they do in fact disagree with each other significant amount. Furthermore, disagreement % larger, EQUILIBRIUM-RANEE correlation between "Disagreement %" and "% Improvement" is 0.64).
also observe that in cases where the offers the most benefit relative to G (The pearson
16

---

Published as a conference paper at ICLR 2024
Domain
Model
Disagreement % (G & D)
G
ER-D
% Improvement
LLaMA-7B
69
30.4
39.9
31.3
MMLU
LLaMA-13B
60.6
41.7
45.1
8.1
LLaMA-7B
56.1
68.2
71.5
4.8
ARC-Easy
LLaMA-13B
46.1
71.2
76.4
7.3
LLaMA-7B
65.9
47.3
58.3
23.2
ARC-Challenge
LLaMA-13B
59.1
51.9
61.4
18.3
LLaMA-7B
55.8
57.7
63.5
10.0
RACE-Middle
LLaMA-13B
53.2
60.1
68.6
14.1
LLaMA-7B
62
46.4
56.4
21.5
RACE-High
LLaMA-13B
58.8
47.9
62.8
31.1
LLaMA-7B
46.1
59.3
71.5
20.5
HHH
LLLMA-13B
38
60.2
61.1
1.5
Table Comparison how often answers chosen by Generative Ranking (G) and Discriminative Ranking (D) disagree in each task and relative percentage improvement of EQUILIBRIUM BAEEIIBRRUMMRRARKAAEE RANKING---G------ DINCRRMINATOR (ER-D) over G.
17


Reviews:
[{"review_id": "6bHLVaPZe9", "reviewer": "Reviewer_DG2h", "summary": "The paper introduces a new decoding strategy for LM's based on a game theoretic formulation. It is directed at tasks requiring objective, factual answers for which a clear notion of a generative version and a discriminative version can be applied. In such settings, the paper describes an adaptation of recent regularized equilibrium approaches that operate directly on the outputs of samples from the Generator/discriminator to produce final answers that do quite well in experiments over a range of challenging fact-seeking or reasoning-seeking benchmarks.", "questions": "1. Regarding the remark in the last para of sec 2.2, what is the difference between the convergence result of Anagostides (2022) and the one claimed earlier in the prev para?\n\n2. I am wondering about a subtle form of bias that may creep in with use of this method. We \"train\" the model with both correct and incorrect answers at the root node, which is good. but then over time we are likely to model select on some dev set using only accuracy as our metric [since generally that's what we care about], which means we only care about the 'correct' branches. Is this a possible problem?\n\n3. Both ER-G and ER-D are quite competitive and there is no clear winner between the 2. Is there some simple combination strategy you recommend? ensemble or averaging?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Originality: There have a lot of recent investigations into improved decoding strategies; this paper's approach is quite original in taking a game-theoretic formulation to (essentially) the problem of factuality from language models. This actually makes a lot of sense; human language as pointed out in one of the references is a strategic game between agents and thus we should be modeling it as such and not a pure optimization problem. This particular insight is not new, but this idea stands out to me because of its practicality. It should be noted that the idea could be said to be inspired by recent work on diplomacy and the core algorithm is an adaptation of the same. However, it takes a good deal of originality to make the connection to discriminator/generator as a game and present the particular formulation in the paper.\n\nQuality: The approach has the strong benefit of simplicity in implementation, it requires no re-training of the LM itself. It does seem to require some degree of non-trivial post-processing in the form of running the iteration procedure of eq 1/2. The authors dont address this but I would expect that it would not affect overall latency of LM inference by much and also it scales zero with LM size (iiuc). The experimental evaluation is quite exhaustive and satisfactory, there are a range of datset types explored. the equilibrium methods don't dominate on every single dataset but they generally do quite close to the SoTA and in some instances far exceed. \n\nClarity: The motivational sections, the presentation of the key insight and the experimental section are mostly quite clear and the paper was a pleasure to read. I appreciate the use of shading to visualize the relative improvement between the best and other methods in Table 1/2/3.\n\nSignificance: I think this could be an very impactful paper. The results are generally very good, it is easy to implement and does not require extensive tuning it seems to get to work, and it seems from my understanding to be scalable to very large LM sizes.", "weaknesses": "Clarity: The paper is actually written fairly well, but there could be some improvements: \n a. sec 2.2 was far too short. readers without any Game theory background might not even know what regret means. You dont need to fully flesh out all the derivation and algorithm, but a better intuition I think should be built, which might require 2-3 paragaphs more. I think this can be taken from the experimental section, where although there is a lot of useful material, at a pinch some of it can be moved to appendix to make room. Further a couple of (minor) sources of confusion on my first read:\n\n a.  'reasonableness' is a bit of a misleading word for the concept you are trying to capture. Maybe 'alignment' ? bu that has other implications in the LM space.\n b. eq 1/2: i think it's helpful to clarify that this update does not result in a backprop to the params of the LM. The reason is that in the current RLHF literature that is generally what happens so it is easy to get confused.\n \nc. Bit confusing to put ER-G and ER-D in the section on \"Baselines\".\n\n\nQuality: I am not at all sure about the characterization of SC as significantly related to Contrastive Decoding. The idea of using a weaker LM as the contrastive seems quite significant to me as it enables the strong LM to \"avoid\" the weaker ones mistakes, which for reasoning problems often are systematic reasoning errors. So it is unfortunate that CD was not compared against (Though I guess the paper with strong results for CD on reasoning problems was quite recent?) \n\nSignificance:  The biggest challenge to the potential significance of this work is that it doesnt seem readily applicable for all use cases of LMs. You need a sort of fact-checking problem, where a set of candidate answers are present. This means it can't be used out of the box as a general decoder, which would be sort of a holy grail right now. Nevertheless, I think the set of applications it is relevant for is hugely important and it is likely to find application given its ease of use.", "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": "3Eyey5RfhE", "reviewer": "Reviewer_Jsc5", "summary": "In this paper, the authors present an interesting framework centered around a consensus game involving generators and discriminators within language models. They delve into the concept of equilibrium within this game and leverage the equilibrium states of the generator and discriminator to enhance output generation in language models. The efficacy of this approach is validated through rigorous experimentation across various question-answering (QA) tasks.", "questions": "See the weakness part.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The game-theoretic formulation introduced for the interaction between generators and discriminators in language models is novel and interesting.\n2. The experiments is comprehensive, covering an array of QA tasks, and the results presented are compelling.\n3. The paper is generally well-written and easy to follow.", "weaknesses": "1. The paper could benefit from a more detailed explanation on the methodological. The process by which Equations (1) and (2) facilitate the attainment of the game's equilibrium is not sufficiently illuminated.\n2. The reliance on the piKL algorithm for the learning dynamics of the consensus game may limit the methodological novelty of the paper.\n3. The pursuit of a no-regret dynamic steers the system towards a coarse correlated equilibrium. The paper could be enriched by an exploration into the feasibility and potential advantages of converging to stronger equilibrium constructs, such as pure Nash or mixed Nash equilibria.\n4. A notable performance drop is observed on the HHH dataset when transitioning from the LLaMA-7B to LLaMA-13B backbone model. An elaboration on this counterintuitive outcome would be beneficial.", "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": "kq15EdEgzm", "reviewer": "Reviewer_XHXa", "summary": "This work proposes a new answer reranking method for LLMs. The main objective is to reconcile the inconsistency between the model's response in the generator setting and its response in the discriminator setting. Specifically, this work designs a regularized imperfect-information sequential signaling game involving the generator and discriminator and finds the Nash equilibrium between them. To find the equilibrium, this work adopts the piKL algorithm proposed by Jacob et al., 2022. The overall method is a training-free method and can consistently outperform several baselines on a variety of QA tasks (also including open-ended and math reasoning tasks).", "questions": "1. I'm trying to understand equations (1) and (2) on page 5, but I can't really understand how the weights terms (i.e., $\\lambda_{G}$  and $\\eta_Gt$ part) work. Should there be an additional $1/t$ before the $Q$? This will also make it more similar to the algorithm in Jacob et al., 2022. Otherwise, can you explain why there is a difference?\n2. Since this is a training-free method, I'm wondering if the authors have tried on even larger models.\n3. This can entirely be future work for a separate paper, but I just wonder if the authors have tried to fine-tune the models (e.g., the smaller 7B one) using the same objective.\n\nTypo: on page 7, Race-high -> RACE-high", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The inconsistent behavior of LLMs across different prompts is an annoying phenomenon. This paper proposes a principled method to reconcile such consistency via game theory.\n2. The proposed method is evaluated on various tasks and consistently improves over popular baselines.\n3. The proposed method is training-free, so it's applicable to even very large-scale models.", "weaknesses": "1. If we compare the proposed ER-based reranking method and previous baselines, there are actually two major differences. One is the process of finding the Nash equilibrium under the regularization part, the other is the combination of two normalized probabilities in Section 2.2. In the current evaluation, it is clear that the combination of these two can bring consistent improvement, but it's unclear what is the effect of each individual component. It would be helpful to have a baseline just combining the two normalized probabilities (e.g., via the MI approach).\n2. This paper can benefit from showing some intrinsic analysis of the inconsistency of the generator and the discriminator. Right now, while the evaluation shows the effectiveness of the proposed approach, it is unclear how severe the problem is, and in how many cases finding the equilibrium can help.\n3. I understand the piKL algorithm is from Jacobs et al., 2022, but I would still suggest the authors provide a slightly more detailed description in the appendix. The lack of related details makes it very hard to understand how important the hyper-parameters are, and if the method is sensitive to these values.", "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": "eh1cPNoPW5", "reviewer": "Reviewer_ji8z", "summary": "The paper introduces a new decoding algorithm called EQUILIBRIUM-RANKING, which addresses the challenge of reconciling different scoring procedures in language models (LMs) for question-answering and text-generation tasks. EQUILIBRIUM-RANKING is a game-theoretic approach, where a generator aims to communicate a correctness parameter to a discriminator through natural language sentences. By formulating language model decoding as an imperfect information sequential signaling game, the authors develop computational procedures to find approximate equilibria of the game. The experiment uses a set of QA tasks to evaluate EQUILIBRIUM-RANKING, including MMLU, ARC, RACE, HHH, and TruthfulQA, and a math benchmark GSM8K. Across these tasks, EQUILIBRIUM-RANKING consistently improves performance compared to existing LM decoding procedures.", "questions": "How is the payoff matrix defined for the consensus game?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper demonstrates originality by introducing a novel approach to decoding language models through the consensus game framework. The idea of casting language model decoding as a game-theoretic problem and seeking approximate equilibria is innovative and provides a fresh perspective on addressing the challenge of reconciling different scoring procedures. \n\n2. The authors develop robust computational techniques for finding approximate equilibria in the consensus game, ensuring reliable and practical implementation of the EQUILIBRIUM-RANKING algorithm. The paper also demonstrates the quality of the research through its extensive evaluation across a diverse range of tasks, showcasing consistent performance improvements over existing decoding procedures.\n\n3. The authors provide a concise and coherent description of the EQUILIBRIUM-RANKING algorithm, making it accessible to readers. The clarity of the writing facilitates the comprehension and replication of the proposed approach. The paper also presents the results and performance improvements in a straightforward manner, enabling readers to grasp the significance of the findings.", "weaknesses": "1. To improve the clarity of the proposed method, it would be advantageous to include a running example that demonstrates the step-by-step process.\n\n2. To enhance the quality of the paper, it is recommended to address minor typos and errors. For instance, in line 6 of the abstract, \"a new, a training-free\" should be corrected to \"a new, training-free.\" Additionally, in section 2, line 6, \"we may them\" appears to be a typographical error and should be revised for clarity.", "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 (spotlight)