Graph of Thoughts (FR)

Graph-of-Thoughts (GoT) est un concept dans le domaine du travail avec les grands modèles de langage (LLM, Large Language Models), qui propose de représenter le processus de raisonnement d'un modèle sous la forme d'un graphe arbitraire de « pensées » (étapes intermédiaires de la solution) interconnectées. Cette approche a été proposée par un groupe de chercheurs dirigé par Maciej Besta de l'ETH Zurich et publiée en 2024 lors de la conférence AAAI. L'objectif de Graph-of-Thoughts est d'étendre les capacités du prompt engineering (ingénierie des prompts) au-delà des schémas existants tels que la Chain-of-Thought (chaîne de pensées) et le Tree-of-Thoughts (arbre de pensées). Contrairement à ces derniers, l'approche GoT permet à tout fragment de raisonnement généré par le modèle (une pensée) de faire référence à n'importe quel autre, formant ainsi un réseau d'idées plutôt qu'une structure strictement linéaire ou arborescente. Ceci, selon les auteurs, reflète plus fidèlement la nature complexe et non linéaire de la pensée humaine et rapproche potentiellement le mécanisme de raisonnement des LLM du fonctionnement du cerveau humain (avec ses connexions neuronales récurrentes).

Graph-of-Thoughts est un cadre de prompting (prompting framework), ce qui signifie qu'il ne nécessite pas d'entraînement supplémentaire ou de mise au point (fine-tuning) du modèle lui-même. Au lieu de cela, il organise le dialogue avec le LLM d'une manière spécifique, guidant le modèle à travers une série d'étapes-« pensées » connectées selon un schéma de graphe. Une telle structure permet de combiner et de réutiliser différentes branches de raisonnement : par exemple, le modèle peut examiner plusieurs hypothèses ou parties d'un problème en parallèle, puis agréger les plus réussies en une seule solution. Dans un style encyclopédique, Graph-of-Thoughts peut être défini comme une généralisation des stratégies précédentes de raisonnement structuré avec les LLM, offrant une flexibilité maximale dans l'organisation des processus de pensée au sein d'une seule requête complexe.

Prérequis : Chain-of-Thought et Tree-of-Thoughts

La méthode Graph-of-Thoughts est issue d'approches antérieures qui utilisaient une structure de raisonnement explicite pour interagir avec les modèles de langage. L'approche de base est la Chain-of-Thought (CoT) – la « chaîne de pensées ». Dans la méthode CoT, l'utilisateur est invité à inclure dans sa requête au modèle non seulement l'énoncé du problème, mais aussi les étapes de raisonnement intermédiaires menant à la réponse. Des études ont montré qu'une telle présentation du matériel améliore considérablement la capacité des LLM à résoudre des tâches complexes, comme des problèmes mathématiques ou des énigmes logiques, sans modifier les paramètres du modèle lui-même. En fait, la CoT incite le modèle à décomposer un problème complexe en étapes plus simples, imitant ainsi un processus de pensée séquentiel.

Le développement de cette idée a conduit à la technique de Self-Consistency : au lieu d'une seule chaîne de pensées, plusieurs chaînes indépendantes sont générées, après quoi la plus convaincante est sélectionnée. Cela permet au modèle d'envisager différentes approches pour résoudre le problème et réduit le risque d'obtenir une réponse erronée en suivant une seule ligne de raisonnement incorrecte. Néanmoins, même plusieurs chaînes CoT ne permettent pas de « combiner des idées » : chaque chaîne est considérée de manière isolée, et le modèle ne fait que choisir la meilleure, sans combiner leurs contenus.

Pour surmonter cette limitation, le schéma Tree-of-Thoughts (ToT) – « l'arbre de pensées » – a été proposé. Dans le ToT, le processus de raisonnement est organisé comme un arbre : à chaque point, le modèle peut générer plusieurs variantes de développement de la pensée (embranchements), après quoi ces états intermédiaires sont évalués et les plus prometteurs sont sélectionnés pour une exploration plus approfondie. En utilisant une recherche dans l'arbre (par exemple, en largeur — BFS, ou en profondeur – DFS) et la possibilité de revenir à des nœuds précédents pour développer une autre branche, le Tree-of-Thoughts offre au modèle de langage un mécanisme de résolution de problèmes complexes plus puissant que la CoT linéaire. De nouvelles possibilités apparaissent, telles que le retour en arrière et la révision : si une branche mène à une impasse, il est possible de revenir au nœud précédent et d'essayer une autre voie. Cette méthodologie a prouvé son efficacité dans la résolution de problèmes logiques et de recherche où l'exploration des options et la planification jouent un rôle majeur.

Cependant, l'arbre de pensées impose également des contraintes strictes : chaque pensée (nœud de l'arbre) n'appartient qu'à une seule branche, l'interaction se produit uniquement entre les nœuds parents et enfants, et les différentes branches ne peuvent pas fusionner ou échanger des informations. En d'autres termes, la pollinisation croisée des idées (cross-pollination) entre différentes hypothèses au sein d'une même solution est difficile : les branches de l'arbre se développent indépendamment et ne se rejoignent qu'à la racine, lorsqu'est choisie la meilleure chaîne de raisonnement. Pourtant, dans la pensée créative ou analytique réelle, un être humain revient souvent à une idée précédemment examinée et la combine avec une autre branche de raisonnement. Un tel enchevêtrement de pensées dépasse la structure d'un arbre.

Ces observations ont conduit les chercheurs à envisager une structure plus flexible – un graphe, où les liens entre les pensées ne sont pas limités et peuvent former un réseau complexe. Comme le note une revue analytique de 2024, l'émergence des chaînes, arbres et graphes de pensées reflète la naissance d'une nouvelle classe de méthodes capables d'améliorer considérablement les capacités des LLM grâce à une structuration explicite du processus de raisonnement. En particulier, les prompts structurés ont permis d'améliorer notablement les résultats des LLM dans de nombreux domaines, de la résolution de problèmes mathématiques et d'énigmes logiques à la planification et même à l'écriture créative. C'est dans ce contexte général qu'est apparu le schéma Graph-of-Thoughts, comme la prochaine étape dans le développement des méthodes de prompting structuré.

Concept du Graph-of-Thoughts : une structure de pensées en graphe

Le Graph-of-Thoughts propose de représenter le déroulement des tâches par un modèle de langage sous la forme d'un graphe orienté arbitraire. Formellement, un graphe de pensées dans GoT est un ensemble de sommets (pensées) et d'arêtes (dépendances entre les pensées). Un sommet du graphe représente une pensée unique du modèle – ce terme désigne toute unité de contenu pertinente pour le contexte de la tâche : il peut s'agir d'une affirmation, d'une étape de résolution, d'un fragment de texte, d'un paragraphe, d'un bloc de code, etc., formulé par le modèle en réponse à une requête. Une arête entre des sommets signifie qu'une pensée a été utilisée pour en générer une autre – c'est-à-dire que le prompt indique explicitement que le modèle doit s'appuyer sur un certain résultat précédent pour en obtenir un nouveau. Ainsi, les arêtes capturent les dépendances : de quelles données obtenues précédemment dépend l'étape actuelle du raisonnement.

La principale différence entre GoT et les structures plus simples est la possibilité d'agréger et de fusionner les pensées. Dans un graphe, il est permis qu'un sommet (une nouvelle pensée) ait plusieurs prédécesseurs. Cela correspond à une situation où deux ou plusieurs chaînes de raisonnement distinctes sont combinées : le modèle reçoit en entrée plusieurs fragments générés précédemment et, sur cette base, formule une sortie synthétisée. Par exemple, en résolvant un problème, le modèle peut examiner deux hypothèses en parallèle, puis créer une nouvelle pensée qui combine les aspects positifs des deux et élimine leurs inconvénients. De telles opérations d'agrégation étaient impossibles dans le cadre d'un schéma arborescent (où chaque nœud n'a qu'un seul parent), mais sont naturellement réalisables dans un graphe. En plus de la fusion d'idées, un graphe permet d'introduire des boucles de rétroaction (feedback loops) : en principe, la structure de GoT n'interdit pas les cycles, ce qui signifie que le modèle peut renvoyer un certain résultat à une étape antérieure du raisonnement pour un retraitement ou un affinement. Les auteurs associent cela à l'analogie avec les connexions récurrentes dans les réseaux de neurones du cerveau, où la sortie d'un groupe de neurones peut influencer en retour les couches précédentes, formant des circuits de réflexion fermés.

En pratique, la mise en œuvre de Graph-of-Thoughts nécessite une organisation particulière du dialogue avec le modèle. Les chercheurs ont développé un cadre architectural modulaire pour GoT. Il distingue des composants pour : (1) un contrôle fin sur les étapes individuelles (pensées) — un « contrôleur » gère l'ordre et la logique de génération des pensées ; (2) la formation dynamique des prompts — pour chaque étape, un module spécialisé génère un prompt en fonction du contexte actuel et des sommets du graphe sélectionnés (prédécesseurs) ; (3) l'analyse et l'évaluation des réponses du modèle — les fragments obtenus du LLM sont analysés et évalués en termes de qualité, d'utilité ou de conformité aux critères de la tâche. L'architecture de GoT permet ainsi de construire le graphe de raisonnement de manière interactive : après chaque étape, une décision est prise sur les nouveaux sommets à ajouter, comment les relier aux précédents, quelles branches continuer ou fusionner. Grâce à sa modularité, un tel cadre peut être étendu avec de nouveaux types de « transformations de pensées » (par exemple, des opérations spéciales sur le graphe) et adapté à différents modèles (les auteurs ont testé avec succès GoT avec des LLM des familles GPT-3.5, GPT-4, LLAMA 2, etc.). Une propriété importante est que GoT ne nécessite pas de modifier les paramètres du modèle de langage lui-même — toutes les améliorations sont obtenues grâce à une construction plus intelligente des requêtes et au traitement des réponses. Cela signifie que les puissants LLM existants peuvent être utilisés « tels quels », et Graph-of-Thoughts agit comme une surcouche qui dirige leur fonctionnement.

Il convient de noter que le terme Graph-of-Thought est également apparu dans un autre développement indépendant, différent de l'approche de Besta et ses collègues. En 2023, Yao Yao et co-auteurs ont proposé une méthode pour améliorer le raisonnement des LLM via un module encodeur de graphe de pensées supplémentaire, ce qui nécessitait un réentraînement du modèle. Leur travail, intitulé « Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models », décrit une architecture en deux étapes : d'abord, un graphe d'affirmations intermédiaires interconnectées est généré, puis il est transformé par un encodeur spécial et intégré au modèle via un mécanisme de fusion contrôlée (gated fusion). Cette approche hybride avec entraînement a montré une certaine amélioration de la précision sur des tâches, par exemple, sur l'ensemble de questions multimodales ScienceQA, la précision est passée de 85,2 % à 87,6 % en utilisant le modèle T5-base. Cependant, cette approche, bien que similaire par son nom, est fondamentalement différente : elle nécessite une modification du modèle (fine-tuning) et n'est pas un schéma de prompt engineering. Les auteurs de l'approche GoT originale (AAAI 2024) précisent explicitement qu'ils ne considèrent pas dans leur travail le modèle de Yao et al., car ils se concentrent sur des méthodes sans mise à jour des paramètres du LLM. Ainsi, Graph-of-Thoughts dans le contexte de cet aperçu est spécifiquement un cadre au niveau des prompts, et non une modification de l'architecture du réseau de neurones.

Application et résultats

Les auteurs de GoT ont démontré ses avantages sur une série de tâches difficiles à résoudre avec un simple prompt direct (input-output prompting) ou même avec une chaîne de pensées. Une caractéristique de ces tâches est qu'elles peuvent être décomposées en plusieurs parties (sous-tâches), résolues séparément, puis la réponse complète est synthétisée à partir des résultats partiels. Parmi les exemples examinés figurent : le tri d'une liste non ordonnée, le comptage de mots-clés dans un texte (par exemple, pour résumer un document), l'exécution d'opérations sur les ensembles (union, intersection de listes, etc.), ainsi que la fusion de documents textuels (combinaison d'informations provenant de plusieurs sources). Dans tous ces cas, Graph-of-Thoughts permet de décomposer la tâche de manière naturelle. Par exemple, pour le tri, la liste est divisée en parties, chaque partie est triée séparément comme une branche de pensées indépendante, après quoi les résultats sont fusionnés (imitant un algorithme comme le tri fusion) ; ou lors de l'analyse de textes, le modèle peut extraire des informations de différents documents en parallèle, puis les regrouper.

Les résultats expérimentaux confirment l'efficacité du schéma GoT. Selon le rapport de Besta et ses collègues, dans la tâche de tri, le graphe de pensées a permis d'améliorer considérablement la qualité de la solution par rapport aux approches précédentes. Ainsi, la précision du tri avec GoT s'est avérée supérieure de 70 % à celle obtenue avec une simple chaîne de pensées (CoT), et supérieure de 62 % à celle de l'arbre de pensées (ToT). Simultanément, la méthode réduit les coûts en ressources de calcul : le nombre d'appels au modèle (et, par conséquent, le volume de requêtes tokenisées) a diminué de 31 % par rapport au Tree-of-Thoughts pour la même tâche. Cela signifie que l'organisation du raisonnement en graphe a non seulement amélioré le résultat final, mais a également rendu la solution plus économique, en évitant les calculs redondants grâce à une combinaison judicieuse des conclusions intermédiaires. Des gains similaires ont été obtenus sur d'autres tâches de test, en particulier celles qui nécessitent d'agréger des informations hétérogènes. Les chercheurs notent que GoT est particulièrement efficace pour les tâches composites, composées de plusieurs éléments : « Graph-of-Thoughts est particulièrement bien adapté aux tâches qui se décomposent naturellement en sous-tâches plus petites, résolues séparément avec une fusion ultérieure des résultats ». Dans de tels cas, le graphe de pensées est capable de couvrir tous les aspects du problème et de synthétiser une solution plus complète que celle obtenue en suivant une seule ligne de raisonnement.

Pour une compréhension plus fine des raisons pour lesquelles une méthode de construction de prompt est meilleure qu'une autre, un article de 2024 a proposé une métrique spéciale : le « volume d'une pensée » (volume of a thought). Le volume est défini pour chaque pensée individuelle (sommet du graphe) comme le nombre d'autres pensées à partir desquelles on peut l'atteindre en suivant les arêtes orientées (en termes plus simples, à combien d'étapes intermédiaires elle doit son information). Dans la Chain-of-Thought, chaque pensée ne dépend que d'un seul prédécesseur, son volume est donc égal à 1 (chaîne linéaire). Dans l'arbre de pensées, le volume peut être plus grand, mais reste limité par la structure d'une branche individuelle. Dans le graphe, grâce à l'agrégation, un seul sommet peut accumuler la contribution de nombreuses autres pensées — son « volume » est considérablement plus élevé. Il a été démontré que GoT permet aux conclusions finales de se baser sur un volume beaucoup plus important de pensées antérieures, en agrégeant leur contenu. Ce fait reflète une couverture plus profonde de l'espace des solutions et sert d'explication quantitative aux avantages du raisonnement en graphe par rapport à des schémas plus simples.

Comparaison et importance

Graph-of-Thoughts représente à ce jour la forme la plus généralisée de prompting structuré pour les LLM. Dans les tableaux comparatifs des différents schémas (CoT, CoT avec auto-cohérence, ToT et GoT), il est souligné que seul GoT prend en charge une topologie arbitraire du processus de pensée. Il inclut les capacités de toutes les approches précédentes : il peut fonctionner comme une seule chaîne, comme un arbre avec des ramifications, ou comme une combinaison de plusieurs chaînes, si cela convient à la résolution de la tâche. L'essentiel est qu'il n'y a pas de contraintes rigides sur les liens entre les étapes, ce qui, en théorie, rend l'espace des stratégies de raisonnement possibles aussi large que possible.

Il est important de comprendre que la flexibilité de GoT se paie par une plus grande complexité de contrôle. La mise en œuvre d'un graphe de pensées nécessite un algorithme orchestrateur externe qui décidera quand et quelles pensées générer, lesquelles sélectionner ou combiner, quand arrêter le processus et fournir une réponse. Dans une simple CoT, de telles décisions ne sont pas nécessaires — le modèle génère lui-même un raisonnement linéaire jusqu'à la fin. Dans le ToT, une partie du contrôle incombe à l'algorithme de recherche dans l'arbre (par exemple, le choix du nœud à développer). Dans GoT, le degré de liberté est plus élevé, et l'efficacité de la méthode dépend de la qualité des heuristiques évaluant les résultats intermédiaires et de la construction correcte des prompts à chaque étape. Ainsi, Graph-of-Thoughts peut être considéré non seulement comme un format de requête, mais comme une structure de raisonnement superposée au processus d'interaction avec un LLM — une sorte de plan dynamique selon lequel le modèle résout la tâche, tandis que l'utilisateur (ou un programme contrôleur) dirige ce processus.

L'émergence de Graph-of-Thoughts reflète une tendance visant à rendre le fonctionnement des grands modèles de langage plus interprétable et contrôlable. En définissant explicitement la structure de la solution, les chercheurs obtiennent non seulement une meilleure qualité, mais aussi la possibilité d'analyser comment le modèle est parvenu à une conclusion donnée. Cela rapproche les approches en TAL des méthodes classiques de recherche algorithmique et de planification, mais l'exécution des étapes est désormais confiée à un modèle de réseau de neurones. Un certain nombre d'experts considèrent les prompts structurés (chaînes, arbres, graphes de pensées) comme une direction prometteuse, capable de surmonter les limitations de la « boîte noire » des modèles profonds et d'améliorer la fiabilité de leur performance sur des tâches complexes.

La méthodologie Graph-of-Thoughts continue de se développer activement. Les auteurs ont rendu le code et les exemples pour la mise en œuvre de GoT accessibles au public, ce qui a permis à la communauté d'expérimenter cette nouvelle approche. Des extensions apparaissent également : par exemple, des versions multimodales du graphe de pensées, combinant texte, images et autres types de données, ainsi que des tentatives d'intégrer les idées de GoT directement dans l'architecture des modèles (comme dans le travail susmentionné de Yao et al., 2023). En 2025, une revue taxonomique détaillée des méthodes Chain-of-Thought, Tree-of-Thoughts et Graph-of-Thoughts a été publiée, systématisant les connaissances accumulées et décrivant les fondements théoriques de ces approches. Tout cela témoigne du grand intérêt de la communauté scientifique pour la gestion structurée de la pensée des LLM. Graph-of-Thoughts s'est déjà imposé comme un outil efficace pour résoudre des problèmes complexes et deviendra probablement la base de futures innovations dans le domaine des solutions d'IA, combinant la puissance des grands modèles de langage avec la transparence et la logique des algorithmes classiques.

Liens

• Article original «Graph of Thoughts: Solving Elaborate Problems with Large Language Models» sur arXiv
• Version HTML de l'article original
• Revue «Demystifying Chains, Trees, and Graphs of Thoughts» sur arXiv
• Article «Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models» sur arXiv
• Multimodal Graph-of-Thoughts — article de Deepgram
• LLMs Graph of Thoughts Framework — article sur Medium

Bibliographie

• Besta, M. et al. (2024). Graph of Thoughts: Solving Elaborate Problems with Large Language Models. arXiv:2308.09687.
• Yao, S. et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601.
• Yao, Y. et al. (2023). Beyond Chain-of-Thought: Effective Graph-of-Thought Reasoning in Language Models. arXiv:2305.16582.
• Wei, J. et al. (2022). Chain of Thought Prompting Elicits Reasoning in Large Language Models. arXiv:2201.11903.
• Wang, X. et al. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models. arXiv:2203.11171.
• Wei, J. et al. (2024). Demystifying Chains, Trees, and Graphs of Thoughts. arXiv:2401.14295.
• Huang, S. et al. (2023). Language Is Not All You Need: Aligning Perception with Language Models (Kosmos-1). arXiv:2302.14045.
• Mitra, C. et al. (2024). Compositional Chain-of-Thought Prompting for Large Multimodal Models. In CVPR 2024. PDF.
• Zheng, G. et al. (2023). DDCoT: Duty-Distinct Chain-of-Thought Prompting for Multimodal Reasoning in Language Models. arXiv:2310.16436.
• Mu, J. et al. (2023). Learning to Compress Prompts with Gist Tokens. arXiv:2304.08467.

Notes

Category:Artificial intelligence