Comment la théorie de jeux permet d’améliorer la cohérence des LLM

La réponse qu’un LLM apporte à une question dépend trop souvent de la manière dont elle est formulée. Un tel comportement pénalise naturellement la fiabilité de ces systèmes. Des avancées récentes dans la théorie des jeux à information incomplète ont toutefois permis de proposer une méthode originale, le Consensus Game, qui réconcilie des réponses contradictoires. Cette méthode est très performante car elle ne nécessite aucun réentraînement du LLM.

Le problème de la cohérence des LLM

Imaginez que vous sollicitez un expert en prévoyance pour qu’il précise quels sinistres sont effectivement couverts par la police d’assurance qu’il vous suggère de souscrire. Vous énumérez alors les situations contre lesquelles vous souhaitez vous prémunir : vol, incendie, dégât des eaux, etc. … et il vous répond que tous ces sinistres sont effectivement couverts. La conversation se poursuit et, quelques instants plus tard, vous lui demandez de confirmer que la police couvre bien le vol. Imaginez alors qu’il vous réponde : « Ah non cher monsieur, pour le vol nous vous proposons tel autre produit ! » Confronté à une telle incohérence, vous seriez en droit de douter tout à la fois de son honnêteté, de sa santé mentale et de ses compétences.

Si un tel niveau d’inconséquence reste peu vraisemblable de la part d’un expert humain, c’est en revanche une faiblesse bien identifiée des LLM. Il est désormais bien établi que leurs réponses sont trop souvent dépendantes de la manière dont on formule une question. D’où l’émergence de l’art, sans doute éphémère, du prompting pour tenter de pallier ces incongruités. Les techniques de délibération comme la « Chain of Thought » (CoT) qui consiste à demander à un LLM de détailler les étapes d’un raisonnement sont désormais bien connues.

La question de savoir comment améliorer la cohérence et la robustesse des réponses d’un LLM vis-à-vis de la formulation d’une question reste à ce jour un problème important largement ouvert et il n’est pas exagéré d’affirmer qu’il s’agit là d’un problème difficile. Récemment, à l’occasion de la conférence ICLR 2024 qui aborde des questions fondamentales de l’IA, un groupe de chercheurs du MIT [1] a cependant proposé une nouvelle approche qui tire parti d’avancées récentes en théorie des jeux à information incomplète pour y apporter une réponse particulièrement originale.

L’objectif de cet article est de présenter les idées et les résultats de ce travail intitulé The Consensus Game, ceci sans entrer dans des détails trop techniques mais sans trop sacrifier la rigueur conceptuelle.

Un jeu coopératif pour faire émerger un consensus

L’article qui propose le Consensus Game envisage deux manières de poser une même question factuelle x à un LLM. La première consiste à formuler la question x accompagnée d’une liste Y = {y1, y2, … yk} de réponses possibles. Cette question x pourrait être p.ex.  « Où est né Emmanuel Macron ? » et la liste Y pourrait être {« Paris », « Le Touquet », « Amiens », « Nantes »}. Plus explicitement encore, le prompt soumis au LLM pourrait être p.ex. : « Parmi les villes suivantes : Paris, Le Touquet, Amiens et Nantes, laquelle est le lieu de naissance de M. Macron ? ». En interne le LLM calcule alors une distribution de probabilité sur les 4 réponses possibles, notons-la PG(y|x), et la réponse qu’il donne correspond naturellement à la ville y* qui maximise PG(y|x). Ce premier mode d’interrogation est dit génératif. Le second mode consiste à proposer un couple question-réponse (x,y) et à demander si une réponse, p.ex. y = « Nantes », est plausible si la question est x. Explicitement, le prompt soumis pourra être « Est-ce que le lieu de naissance de M. Macron est Paris ? ». Le LLM calculera là encore une distribution sur les deux valeurs de vérité v= « correct » ou v = « incorrect », notons la PD(v|x,y), et retournera celle qui a la plus grande probabilité. C’est le mode discriminant du LLM.

Figure 1: Le Consensus Game fait appel à deux joueurs qui coopèrent pour parvenir à un consensus. Une variable de vérité aléatoire v définit le comportement d’un générateur G au sens où il dit la vérité ou il ment. Le discriminateur D, qui ignore cette valeur, doit la deviner. La coopération est induite par une fonction de gain qui récompense les joueurs à chaque fois que D devine correctement la valeur de v utilisée par G.

 

Dans une situation dans laquelle les réponses fournies par les deux modes d’interrogation sont incohérentes, ces deux distributions seront incompatibles. Pour une même question x, la réponse y* = « Amiens » pourrait se voir attribuer une probabilité maximale par PG alors que PD attribuerait une probabilité maximale à v* = incorrect pour cette même réponse y*. Dans notre exemple PG aurait raison et PD aurait tort puisque M. Macron a bien vu le jour à Amiens.

L’idée des auteurs du Consensus Game consiste à construire un processus d’évolution coopératif qui, partant des deux distributions PG et PD initialement incompatibles, les réconcilie progressivement pour parvenir à un équilibre P*Get P*D qui atténue les contradictions. Insistons d’emblée sur un point essentiel. Il ne s’agit nullement ici réentraîner le LLM, mais plus simplement de faire évoluer les distributions PG et PD fournies par le LLM non modifié. L’un des atouts de cette approche est qu’elle s’avère pour cette raison très économe en ressources de calcul.

Une définition rigoureuse de ce processus de réconciliation, que les auteurs nomment le Consensus Game, requiert d’introduire quelques notions de théorie des jeux (TDJ) qui seront esquissées de la section suivante. Nous nous contentons dans cette section d’une présentation schématique.

Pour une question x fixée l’idée est d’utiliser le LLM pour définir deux « joueurs ». Un premier joueur, appelé le générateur G, reçoit deux informations. L’une est la question x, l’autre est une valeur binaire v choisie aléatoirement entre les deux options « correct » ou « incorrect ». Si v = « correct » on utilise le prompt précédent pour demander au LLM de répondre en choisissant une réponse dans la liste préétablie Y. Si en revanche v = « incorrect », on rajoute un bout de phrase dans le prompt qui demande au LLM de répondre de manière intentionnellement erronée. Le LLM calculera donc une distribution PG(y|x,v) sur les réponses y conditionnées par la question x et par une valeur de vérité v que lui seul connaît.

Le deuxième joueur, appelé le discriminateur D, a été défini précédemment. Il reçoit un couple (x,y) de question-réponse et on lui demande de déterminer la probabilité que y soit la bonne réponse à x. Le LLM calcule pour cela la probabilité PD(v=correct|x,y). Il ne connaît pas la valeur de v.

Un tour de jeu est défini par un tirage d’une valeur aléatoire pour v, par la génération de la réponse y par G et enfin par une tentative de prédiction de la valeur v par D lorsqu’on lui soumet y.

À l’instant t=0 les stratégies de G et D sont initialisées respectivement avec les distributions PG(y|x,v) et PD(v|x,y) calculées par le LLM. Le jeu est ensuite répété un grand nombre de fois. À chaque tour de jeu t on modifie légèrement les prédictions PG(y|x,v ; t-1) et PD(v|x,y  ; t-1) obtenues à l’étape précédente en cherchant à favoriser les distributions où D devine correctement la valeur v utilisée par G. On introduit à cette fin une fonction de gain qui rémunère simultanément G et D (au sens de la TDJ) à chaque fois que D devine correctement cette valeur. On peut donc espérer qu’après un grand nombre d’itérations les distributions PG(y|x,v ; t) et PD(v|x,; t) convergeront vers un équilibre mutuel dans lequel ce gain sera optimal et où les prédictions de G et D seront par conséquent aussi cohérentes que possible. Notons P*G(y|x,v) et P*D(v|x,y) ces stratégies optimales obtenues à l’équilibre.

En réalité, le problème de réconciliation est à la fois plus subtil et plus intéressant que ce que laisse entendre l’argumentation trop simpliste précédente. À bien y réfléchir, rien n’empêcherait en effet G et D de s’accorder sur une réponse incorrecte ! La cohérence des réponses entre G et D ne peut donc constituer le seul objectif à poursuivre pour faire évoluer les stratégies. La solution proposée par les auteurs du Consensus Game est d’ajouter à la fonction de gain un terme de mise en garde qui pénalise les stratégies PG(y|x,v ; t) et PD(v|x,; t) qui s’aventureraient trop loin des stratégies initiales PG(y|x,v) et PD(v|x,y) dictées par le LLM. En effet, bien que potentiellement incohérentes, celles-ci incorporent néanmoins toutes les connaissances du LLM qui lui permettent d’estimer la plausibilité d’une réponse. La réconciliation s’accomplit donc au moyen d’une évolution dictée par une double contrainte qui exige que les prédictions de P et G sont à la fois cohérentes et raisonnables.

La section qui suit donne quelques rudiments de TDJ qui permettent de formaliser ces propos un peu vagues. Les lecteurs pressés peuvent poursuivre la lecture à la section suivante.

Quelques rudiments de théorie des jeux

Résumons-nous : si l’on omet dans un premier temps la contrainte de plausibilité, réconcilier les prédictions du générateur G et du discriminateur D revient à trouver une situation d’équilibre où, en moyenne sur la répétition de nombreux jeux, P*D(v|x,y) prédit correctement la valeur v lorsqu’il observe la réponse donnée par P*G(y|x,v) quand ce dernier répond à la question x.

La TDJ est le cadre formel dans lequel ces notions peuvent se formuler sans ambiguïté. Elle étudie les situations qui surviennent lorsque des agents rationnels, appelés des joueurs, prennent des décisions qui prennent en compte la connaissance qu’ils ont du comportement des autres joueurs. On parle alors de solution d’un jeu pour décrire son issue. Le type de solution qui nous intéresse en l’occurrence est une situation d’équilibre stationnaire.

Les jeux sous forme normale (Strategic Games)

Avant d’en venir au Consensus Game proprement dit, plaçons-nous dans le cadre conceptuel le plus simple de la TDJ, celui des jeux dits sous forme normale qui permettent de formaliser des jeux simples comme pierre-papier-ciseaux ou le dilemme du prisonnier. La caractéristique essentielle de ces jeux est que les joueurs prennent leurs décisions simultanément.

Figure 2 : les actions du jeu pierre-papier-ciseaux.

 

On suppose dans ce cadre que N joueurs sont en présence et que chaque joueur i possède un ensemble Ai d’actions possibles. Dans l’exemple ci-dessus N=2 et les deux joueurs possèdent les mêmes actions : pierre, papier ou ciseaux. L’issue d’un jeu est ici le choix par chaque joueur d’une action, on parle aussi de profil d’actions.

Chaque joueur possède par ailleurs une préférence quant à l’issue du jeu qu’il estime la plus favorable pour lui. Elle est le plus souvent exprimée à l’aide d’une fonction de gain ui(a1,…, aN) propre au joueur i qui dépend du profil d’actions (a1,…, aN). Dans l’exemple on a par exemple u1(ciseaux, papier) = +1, u1(ciseaux, pierre) = -1 et u1(ciseaux, ciseaux) = 0, etc.

Figure 3 le dilemme du prisonnier modélise une situation où deux individus auraient intérêt à coopérer (C,C). Si un seul choisit de coopérer il est fortement pénalisé alors que son adversaire remporte un gain maximal (C,D) et (D,C). Si aucun ne coopère (D,D) chacun limite les dégâts et aucun ne regrettera son choix.

 

Un autre jeu bien connu est celui du dilemme du prisonnier. Il modélise une situation dans laquelle deux individus ont intérêt à coopérer car c’est l’issue qui maximise la somme de leurs gains. Cependant si un seul des deux choisit de le faire il sera fortement pénalisé. Dans la formulation traditionnelle deux criminels complices sont détenus dans des cellules distinctes et ne peuvent pas communiquer. Les actions possibles pour eux correspondent au choix de se taire (C) ou d’avouer leur crime (D), voir la figure 3. Coopérer signifie que les deux se taisent (C,C). Dans ce cas ils se verront infliger une peine réduite faute d’éléments à charge. C’est la situation globalement la plus favorable. Si en revanche seul l’un des deux choisit de trahir et avoue le crime, il se verra infliger une peine minimale alors que son camarade se verra infliger une peine maximale. Ce sont les issues (C,D) et (D,C). Si enfin tous les deux avouent le crime (D,D), ils seront condamnés à des peines légères. Cette situation (D,D) bien que globalement moins favorable que la coopération (C,C), a toutefois de bonnes chances d’être choisie par nos deux lascars s’ils agissent rationnellement car ils n’auront en effet aucune raison de regretter leur choix. Le prisonnier n°1 peut se dire qu’il a bien fait d’avouer puisque s’il avait gardé le silence il aurait subi la peine maximale, de même pour le prisonnier n°2. Cette situation dans laquelle aucun des joueurs n’a de raison de regretter son choix est un exemple de ce qu’on appelle un équilibre de Nash.

Plus formellement, un équilibre de Nash d’un jeu sous forme normale est un profil d’actions (a*1,…, a*N) pour lequel chaque joueur i constate qu’un choix ai différent de ai* aurait été moins favorable pour lui dans l’hypothèse où les autres joueurs j choisissent tous la stratégie d’équilibre a*j.

Le jeu pierre-papier-ciseaux ne comporte pas d’équilibre de Nash, du moins s’il n’est joué qu’une seule fois. Le dilemme du prisonnier possède lui un équilibre de Nash mais, comme nous l’avons vu, ce n’est pas la situation la plus favorable globalement. D’autres jeux possèdent plusieurs équilibres de Nash qui n’offrent pas nécessairement les mêmes gains.

L’intérêt de ces jeux sous forme normale est non seulement pédagogique mais aussi théorique dans la mesure où d’autre jeux, plus complexes, peuvent s’y ramener au prix d’un peu d’abstraction, voir p.ex. [2].

Les jeux de signalisation (Signaling Games)

Après cette petite excursion dans la TDJ, revenons à nos moutons. Le Consensus Game n’est pas un jeu sous forme normale, et ceci pour trois raisons :

  1. Contrairement à ce que présupposent les jeux sous forme normale, les joueurs ne jouent pas simultanément mais séquentiellement. Le générateur G initie la partie et choisit une action y que le discriminateur D observe avant de choisir son action qui est d’afficher une prédiction pour la valeur de v.
  2. Le générateur G et le discriminateur D prennent tous deux leurs décisions de manière non déterministe. Elles sont décrites par des distributions de probabilités PG(y|x,v) et PD(v|x,y). C’est un jeu dit bayésien.
  3. Enfin, c’est un jeu à information incomplète au sens où D ne connaît pas la stratégie utilisée par G qui dépend d’une variable secrète v connue de lui seul.

Le Consensus Game est ce que l’on appelle techniquement un jeu de signalisation. Un émetteur est informé de la valeur d’une certaine variable privée v qu’il communique à un récepteur en transmettant un message m. L’objectif de l’émetteur peut être de transmettre la valeur de v (c’est le cas du Consensus Game) ou au contraire de la masquer vis-à-vis du récepteur (lors d’une interview un candidat peut souhaiter masquer son incompétence au recruteur). Ayant observé m, le récepteur à son tour choisit une action a. La fonction de gain pour chaque joueur dépend à la fois de la valeur de la variable cachée v, du message m émis par l’émetteur et de l’action a choisie par le récepteur. Comme les décisions sont probabilistes c’est la moyenne du gain sur un grand nombre de répétitions du jeu que chaque joueur souhaite optimiser.

Dans le cas particulier du Consensus Game l’action a sélectionnée par D est sa prédiction de v, elle révèle sa croyance quant au comportement de G. L’objectif du jeu en l’occurrence est de favoriser l’émergence d’un équilibre constitué d’un couple de décisions P*G(y|x,v) et P*D(v|x,y) compatibles où D prédit avec une grande probabilité la valeur de v utilisée par G. On se convainc aisément qu’une fonction de gain donnée par le produit PG(y|x,v) PD(v|x,y) fait l’affaire.

La notion d’équilibre appropriée pour un jeu de signalisation est la notion d’équilibre bayésien parfait (Perfect Bayesian Equilibrium). Elle est plus délicate à formuler que l’équilibre de Nash car elle implique non seulement une stratégie pour l’émetteur et une autre pour le récepteur mais également une croyance (Belief) du récepteur quant au comportement (Type) de l’émetteur. Elle fait par ailleurs intervenir des conditions subtiles de rationalité et de cohérence qu’il est hors de question d’aborder ici (voir p.ex. [2] ou [3]). Nous nous contenterons d’admettre que cette notion d’équilibre coïncide ici encore avec l’idée de minimiser une forme de regret pour les joueurs lorsqu’elle est atteinte.

Promouvoir des réponses à la fois cohérentes et raisonnables !

Comme nous l’avons mentionné plus haut, la seule exigence de cohérence des prédictions de P et G ne suffit pas pour formuler un Consensus Game dont les prédictions soient raisonnables en plus d’être cohérentes. Il faut pour cela corriger (on dit aussi régulariser) la fonction de gain du jeu de signalisation pour y inclure un terme qui pénalise des stratégies qui s’éloigneraient trop des prédictions initiales du LLM.

L’un des mérites du travail [1] sur le Consensus Game est d’avoir su tirer parti d’avancées algorithmiques récentes [4] sur les jeux à information incomplète. L’un des problèmes étudiés par la recherche dans ce cadre est l’élaboration de systèmes qui produisent des stratégies performantes pour des jeux comme no-press Diplomacy tout en pratiquant un style de jeu proche de celui d’un humain.

Il s’agit en réalité d’une question de portée générale pour tous les systèmes d’IA conçus pour coopérer avec des humains qui doivent être en mesure de les comprendre. Un système purement compétitif comme AlphaGo, entraîné en jouant contre lui-même des millions de parties, produit des stratégies certes extrêmement performantes, parfois même suprahumaines, mais hélas inintelligibles. Pour cela des chercheurs ont développé des techniques qui régularisent les stratégies en les pénalisant lorsque leur style s’écarte trop de celui pratiqué par les humains. Pour le Consensus Game ce sont les stratégies du LLM qui jouent ce rôle d’ancrage. La solution était donc toute trouvée à condition de faire le rapprochement.

Des résultats encourageants…

Une fois l’équilibre (P*G,P*D) du Consensus Game atteint, on peut utiliser la prédiction du générateur P*G(y|x,v=correct) ou celle du discriminateur PD(v=correct|x,y) pour déterminer une la réponse y cohérente la plus probable à une question x. Cette réponse se substitue à la réponse déduite de la distribution initiale du LLM initialement déduite de PG(y|x, v=correct). Pour évaluer l’efficacité du Consensus Game les auteurs de [1] ont utilisé 6 datasets de référence (MMLU, ARC, …, HHH) pour le problème de question-answering et comparé la précision des réponses obtenues avec leur méthode (ER-G) et (ER-D) à celles fournies par le LLM non corrigé (noté G dans le tableau) et par d’autres méthodes plus anciennes (notées MI, SC, D).

Figure 4 : Une évaluation de l’amélioration de la précision des réponses à différents problèmes de question-answering. Chaque ligne correspond à un jeu de donnée et une version de LLM. Chaque colonne correspond à un modèle. La première étiquetée G correspond au LLM original. Elle fournit un point de comparaison (baseline) pour les autres méthodes. Les prédictions du générateur et du discriminateur obtenues à l’équilibre (P*G,P*D) du Consensus Game sont étiquetées ER-G et ER-D respectivement. Les valeurs de chaque méthode sont comparées aux prédictions du LLM représentées dans la colonne G. Les écarts favorables sont représentés en vert foncé, les écarts défavorables en rose foncé.

 

On constate en particulier qu’un petit modèle (LLaMA-7B) boosté à l’aide du Consensus Game est souvent plus performant qu’un gros modèle (LLaMA-14B) qui n’a pas bénéficié de ce coup de pouce. Cette méthode est très économique en ressource de calcul puisqu’elle n’exige aucun réentraînement du LLM mais corrige ses prédictions pour les réconcilier au prix d’un coût de calcul marginal par rapport au coût d’une inférence.

… mais il reste du travail !

L’une des limitations d’une mise en cohérence par le Consensus Game tient à la nécessité de définir un discriminateur chargé de vérifier toutes les réponses possibles à une question. Il va sans dire que de nombreux usages des LLM ne se laissent pas formuler ainsi. D’autres idées sont donc vraisemblablement nécessaires pour généraliser l’application du Consensus Game à d’autres cas d’utilisation des LLM. Ce travail de pionniers a cependant mis en lumière l’intérêt d’utiliser la boîte à outils de la théorie de jeux, en particulier les notions d’équilibre et de solution, pour attaquer les problèmes ardus que soulève aujourd’hui comportement imprévisible des modèles de langues.

Après la question de la cohérence, une perspective fascinante pourrait être l’utilisation de la TDJ pour guider la dynamique d’une conversation vers un équilibre ou un but souhaitable [5]. Pourrait-on utiliser des LLM pour simuler une négociation et anticiper ou orienter son issue à l’aide de la TDJ ? Le travail sur le Consensus pourrait donc préfigurer une alliance féconde entre le traitement du langage naturel et la TDJ lorsqu’il s’agit d’aborder des problèmes complexes comme l’aide à la négociation qui font appel aux deux disciplines. Le challenge n’est pas mince car la TDJ a été conçue à l’origine pour étudier des situations stratégiques schématisées à l’extrême, des jeux précisément, et non pas pour se coltiner la complexité du réel que le langage naturel permet d’exprimer. Bref, il reste du pain sur la planche aussi bien sur le plan scientifique que pour cerner les implications éthiques de telles recherches.

Sources

  1. The Consensus Game: Language Model Generation via Equilibrium Search, A. Paul Jacob, Y. Shen, G. Farina, J. Andreas, OpenReview, octobre 2023 pour ICLR 2024.
  2. A Course in Game Theory, Martin J. Osborne and Ariel Rubinstein, MIT Press, 1994.
  3. Perfect Bayesian equilibrium, Wikipédia.
  4. Modeling Strong and Human-Like Gameplay with KL-Regularized Search, Proceedings of the 39th International Conference on Machine Learning, PMLR 2022.
  5. States as Strings as Strategies: Steering Language Models with Game-Theoretic Solvers, arXiv 2024.