Résumé Technique : Graphe de Pensées Renforcé (RGoT)

Énoncé du Problème

Les modèles de langage de grande taille (LLM) ont démontré des capacités significatives en matière de résolution de problèmes délibérée grâce à des paradigmes de prompting tels que la Chaîne de Pensée (CoT), l'Arbre de Pensées (ToT) et le Graphe de Pensées (GoT). Bien que le GoT offre un cadre généralisé où les pensées sont structurées sous forme de graphes arbitraires pour permettre l'agrégation et le raisonnement complexe, l'implémentation existante repose sur un graphe d'opérations statique et défini manuellement.

Cette définition manuelle présente deux limitations principales :

1. Accessibilité : La construction d'un graphe GoT nécessite une connaissance approfondie de la solution du problème et de l'ordre spécifique des opérations, créant une barrière à l'entrée élevée pour les utilisateurs.
2. Adaptabilité : Les graphes statiques sont rigides. Ils ne peuvent pas s'adapter à la complexité variable des instances d'entrée ni à la nature non déterministe et entropique des sorties des LLM. Par conséquent, un graphe conçu pour un niveau de complexité spécifique peut échouer lorsqu'il est appliqué à des entrées possédant des propriétés différentes.

Alors que des travaux antérieurs (Ha et al., 2024) ont tenté d'automatiser le GoT, ils reposent sur les capacités logiques du LLM sous-jacent pour construire le graphe. Cet article répond au besoin d'une approche qui ne dépend pas des capacités de planification du LLM pour générer la topologie du raisonnement elle-même.

Méthodologie

Les auteurs proposent le Graphe de Pensées Renforcé (RGoT), une approche automatisée qui utilise l'Apprentissage par Renforcement (RL) pour générer de manière adaptative un graphe d'opérations à partir d'un ensemble défini par l'humain d'opérations disponibles.

Composants Principaux du Cadre

Le système découple le Graphe d'Opérations (GoO) du Graphe de Pensées (GoT) :

• Graphe d'Opérations (GoO) : Un graphe orienté acyclique (DAG) qui définit la séquence et la structure des opérations. Il est contraint par une profondeur maximale ($d_{max}$) et une largeur maximale ($b_{max}$). Pour assurer la convergence, une profondeur de coupure de divergence ($d_{\neg div}$) est imposée, après laquelle le graphe doit converger vers un seul puits.
• Graphe de Pensées (GoT) : La trace d'exécution réelle où les pensées du LLM sont générées. Chaque pensée fait référence à l'opération qui l'a créée.
• Opérations : Définies soit comme des Opérations de Prompt (appels au LLM) soit comme des Opérations d'Exécution (fonctions programmatiques). Une Opération de Score évalue la qualité d'une pensée, renvoyant un score numérique.

Formulation par Apprentissage par Renforcement

L'agent RGoT opère dans un environnement RL personnalisé pour construire la couche GoO couche par couche.

• Espace d'État ($S$) : Une composition d'espaces discrets incluant la profondeur actuelle du graphe, la largeur, la complexité de la tâche, la complexité locale, la séquence des opérations dans le graphe actuel, les actions précédentes et le score précédent.
• Espace d'Action ($A$) : Des actions discrètes incluant stop (terminer la construction du graphe), backtrack (retirer la couche puits) et append(o) (ajouter une nouvelle couche avec l'opération $o$).
• Fonction de Récompense : Conçue via un façonnage de récompense pour pénaliser une profondeur excessive, récompenser les opérations valides et fournir une récompense positive significative pour la résolution réussie de la tâche (état final).
• Simulation : Pour atténuer le coût élevé de l'entraînement avec de vrais appels LLM, le comportement du LLM est simulé. La probabilité de succès d'une opération à une complexité donnée $c$ est modélisée comme une expérience de Bernoulli avec une probabilité $P(c)$, estimée empiriquement en sollicitant le LLM cible (par exemple, gpt-3.5-turbo-0125) 100 fois par niveau de complexité.

Configuration Expérimentale

Les auteurs ont évalué RGoT sur cinq tâches :

1. Somme de Liste : Additionner une liste d'entiers (exemple principal).
2. Tri de Liste : Trier des entiers.
3. Intersection d'Ensemble : Trouver les intersections d'ensembles.
4. Comptage de Mots-clés : Compter les occurrences de mots-clés dans un texte.
5. Fusion de Documents : Fusionner des documents tout en maximisant la rétention et en minimisant la redondance.

Les expériences ont utilisé l'algorithme Proximal Policy Optimization (PPO) avec une architecture de réseau à 2 couches (64 unités). Les agents ont été entraînés sur une plage spécifique de complexités, puis évalués sur des instances à la fois in-distribution et out-of-distribution (complexité plus élevée).

Résultats Clés

• Construction Adaptative : Les agents RL ont appris avec succès à construire des graphes d'opérations qui s'adaptent à la complexité de la tâche. À mesure que la complexité augmentait, les agents augmentaient automatiquement la ramification (divergence) et la profondeur du graphe pour décomposer le problème, un comportement non explicitement programmé mais appris grâce au signal de récompense.
• Performance vs. Référence : Les agents RGoT ont considérablement surpassé la référence standard de prompting Entrée-Sortie (IO). Alors que les stratégies IO échouaient lorsque la complexité dépassait la capacité directe du LLM, les agents RGoT ont maintenu des taux de réussite élevés en décomposant les tâches.
• Généralisation : Les agents ont démontré la capacité à résoudre des complexités out-of-distribution (complexités supérieures à celles rencontrées pendant l'entraînement), atteignant un taux moyen total résolu de $0,7512 \pm 0,1089$.
• Variance : Les auteurs ont observé une variance dans la performance des agents à travers différentes graines aléatoires, en particulier dans les régions out-of-distribution. Cela est attribué au signal de récompense épars aux complexités élevées et à la nature on-policy du PPO, qui limite la capacité de l'agent à se remettre des engagements de trajectoire sous-optimaux précoces.

Importance et Revendications

L'article revendique être le premier travail à présenter une approche automatisée pour construire un graphe de pensées en générant et en parcourant un graphe d'opérations sans dépendre de la capacité du modèle de langage à planifier ou à comprendre les propriétés de la tâche.

Les contributions clés incluent :

1. Automatisation du GoT : Élimination du besoin de définition manuelle du graphe, rendant ainsi le paradigme GoT plus accessible aux utilisateurs qui doivent uniquement définir l'ensemble des opérations disponibles.
2. Adaptabilité : Démonstration qu'un agent automatisé peut ajuster dynamiquement la topologie du raisonnement en fonction de la complexité de l'entrée, surmontant la rigidité des graphes statiques.
3. Agnosticisme du Modèle : Le cadre est agnostique au LLM spécifique utilisé. En simulant les probabilités de succès du LLM, le système peut être entraîné de manière rentable et appliqué à divers modèles, y compris ceux ayant des gammes de capacités différentes.
4. Complémentarité : Les auteurs notent que RGoT (structurer la topologie du raisonnement) est complémentaire au Knowledge Graph of Thoughts (KGoT), qui structure les connaissances récupérées externement, suggérant un potentiel pour des applications futures combinées.

Les auteurs maintiennent un ton modeste, reconnaissant que si l'approche montre des promesses sous des contraintes spécifiques et pour des tâches définies, la variance de performance et la dépendance à la simulation pour l'entraînement restent des domaines à considérer. Ils ne revendiquent pas une supériorité universelle sur toutes les méthodes de prompting, mais mettent en avant l'utilité spécifique de la construction de graphes automatisée et adaptative pour des tâches complexes et décomposables.