💻 computer science

GraphPO: Graph-based Policy Optimization for Reasoning Models

GraphPO introduit un nouveau cadre d'apprentissage par renforcement basé sur les graphes qui représente les déroulements de raisonnement sous forme de graphes acycliques dirigés afin de fusionner les chemins sémantiquement équivalents et de partager l'information entre les branches, réduisant ainsi l'exploration redondante et la variance de l'estimation de l'avantage tout en surpassant les méthodes existantes basées sur des chaînes ou des arbres sur les tests de référence de raisonnement.

Auteurs originaux : Yuliang Zhan, Xinyu Tang, Jian Li, Dandan Zheng, Weilong Chai, Jingdong Chen, Jun Zhou, Ge Wu, Wenyue Tang, Hao Sun

Publié 2026-06-19

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yuliang Zhan, Xinyu Tang, Jian Li, Dandan Zheng, Weilong Chai, Jingdong Chen, Jun Zhou, Ge Wu, Wenyue Tang, Hao Sun

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous enseignez à un étudiant très intelligent mais légèrement répétitif comment résoudre un problème de mathématiques complexe ou écrire un morceau de code. Vous ne lui donnez pas d'instructions étape par étape ; au lieu de cela, vous le laissez essayer différentes approches, et vous ne lui dites à la toute fin : « Correct ! » ou « Incorrect ».

C'est ainsi que les modèles d'IA actuels (appelés Grands Modèles de Raisonnement) apprennent. Ils devinent, devinent et devinent jusqu'à obtenir la bonne réponse. Mais il existe deux problèmes majeurs avec cette méthode, que l'article appelle GraphPO visant à corriger.

Le Problème : L'« Explorateur Solitaire » et la « Méthode de l'Arbre »

1. L'Effort Gaspillé (Méthode de la Chaîne)
Imaginez envoyer 100 étudiants dans un labyrinthe. Chaque étudiant suit un chemin complètement séparé.

Le Problème : Même s'ils sont sur des chemins différents, 50 d'entre eux pourraient se retrouver coincés exactement dans la même impasse ou traverser le même couloir déroutant. Ils gaspillent du temps et de l'énergie à faire exactement la même chose encore et encore. En termes d'IA, c'est une « exploration redondante ».

2. La Méthode de l'« Arbre » (L'Amélioration, mais pas parfaite)
Pour corriger ce gaspillage, les chercheurs ont essayé une méthode d'« Arbre ». Imaginez que les étudiants commencent ensemble, et au premier embranchement de la route, ils se séparent. Si deux étudiants prennent le même premier tournant, ils marchent ensemble pendant un certain temps.

Le Problage : Cela aide un peu, mais une fois qu'ils se séparent à un second embranchement, ils sont de nouveau livrés à eux-mêmes. Si deux branches différentes de l'arbre mènent finalement au même couloir déroutant (même s'ils y sont arrivés par des itinéraires différents), les étudiants ne savent pas qu'ils sont au même endroit. Ils continuent d'explorer ce couloir séparément, gaspillant plus de temps. Ils ne peuvent pas non plus partager la « bonne nouvelle » si un étudiant trouve la sortie de ce couloir ; les autres continuent de deviner.

La Solution : La « Carte Intelligente » (GraphPO)

Les auteurs proposent GraphPO, qui est comme donner aux étudiants une carte vivante et partagée au lieu de simplement un arbre.

Comment cela fonctionne :

La Carte (Le Graphe) : Au lieu de simplement dessiner des lignes (branches), l'IA dessine une carte où chaque « pièce » (une étape du raisonnement) est un nœud.
Repérer les Jumeaux (Fusion Sémantique) : À mesure que l'IA explore, elle examine les « pièces » que différents chemins ont atteintes. Si deux chemins différents arrivent dans une pièce qui semble être la même (même si les mots utilisés pour y arriver étaient légèrement différents), l'IA dit : « Hé, vous deux êtes au même endroit ! » et les fusionne en un seul point sur la carte.
Partager la Bonne Nouvelle (Partage de Suffixe) : Une fois que deux chemins sont fusionnés, ils partagent tout ce qui vient après ce point. Si un chemin trouve la bonne réponse à partir de ce point fusionné, l'autre chemin reçoit instantanément le crédit de ce succès sans avoir à parcourir le reste du chemin à nouveau.
Le Bonus d'« Efficacité » : L'IA apprend également à préférer le chemin le plus court pour arriver à une « pièce » spécifique. Si le Chemin A prend 10 étapes pour arriver à un bon endroit, et que le Chemin B prend 15 étapes pour arriver au même endroit, l'IA apprend à favoriser le Chemin A. C'est comme récompenser l'étudiant qui prend le raccourci.

Le Résultat : Plus Intelligent, Plus Rapide et Moins Gaspilleur

En utilisant cette approche de « Carte Intelligente », GraphPO atteint trois choses principales :

Plus de Pas Gaspillés : Cela empêche l'IA d'explorer deux fois les mêmes impasses. Cela redirige le « budget » (puissance de calcul) vers l'exploration de nouvelles zones au lieu de répéter les anciennes.
Un Meilleur Apprentissage des Erreurs : Parce qu'il fusionne les chemins similaires, il peut dire à l'IA, « Cette étape spécifique était bonne », beaucoup plus tôt qu'auparavant, même si la réponse finale n'est pas encore parfaite. Cela transforme un vague « Tu as réussi à la fin » en un clair « Ce mouvement spécifique était intelligent ».
Des Réponses Plus Courtes : Puisqu'il récompense le chemin le plus court vers une solution, l'IA apprend à être plus concise et efficace, coupant les bavardages inutiles.

L'Essentiel

L'article a testé cela sur trois modèles d'IA différents à travers des problèmes de mathématiques, de codage et des tâches de recherche. Les résultats ont montré que GraphPO bat systématiquement les anciennes méthodes (tant les explorateurs solitaires que les arbres de branchement). Il résout plus de problèmes, utilise moins de mots pour le faire et apprend plus vite, tout en utilisant la même quantité de puissance de calcul.

En bref, GraphPO apprend à l'IA à arrêter de marcher en cercles et à commencer à partager une carte, rendant le processus d'apprentissage beaucoup plus intelligent et moins gaspilleur.

Résumé Technique : GraphPO - Optimisation de Politique Basée sur les Graphes pour les Modèles de Raisonnement

1. Énoncé du Problème

L'apprentissage par renforcement avec récompenses vérifiables (RLVR) est devenu le paradigme standard pour améliorer les grands modèles de raisonnement (LRM). Cependant, les méthodes RLVR actuelles font face à deux limitations principales :

Exploration Redondante : L'échantillonnage indépendant des réponses entraîne souvent des trajectoires différentes contenant des étapes de raisonnement intermédiaire similaires. Cela conduit à un gaspillage de calcul et limite la diversité de l'exploration.
Signaux de Récompense Épars : Le RLVR repose généralement sur des récompenses binaires basées sur la réponse finale. Cette parcité rend difficile l'attribution de crédit à des étapes de raisonnement intermédiaires spécifiques qui contribuent à la réponse finale.

Bien que les méthodes basées sur les arbres (ex: TreeRL, PROS) traitent une partie de la redondance en partageant des préfixes et en fournissant des signaux plus fins aux points de branchement, elles traitent toujours les branches divergentes comme des chemins indépendants. Par conséquent, si différentes branches atteignent des états intermédiaires sémantiquement similaires, elles ne peuvent pas partager d'informations, ce qui entraîne une exploration répétée et une variance plus élevée dans l'estimation de l'avantage.

2. Méthodologie : GraphPO

Les auteurs proposent GraphPO, un nouveau cadre de RL qui modélise les déroulements de raisonnement comme un Graphe Orienté Acyclique (DAG) plutôt que comme une chaîne ou un arbre.

2.1 Construction et Fusion du Graphe

Structure : Dans GraphPO, les étapes de raisonnement sont représentées par des arêtes, et les états sémantiques intermédiaires (résumés à partir du chemin de raisonnement débutant par le prompt) sont représentés par des nœuds.
Classes d'Équivalence : Le cadre construit progressivement le graphe en détectant des états sémantiquement similaires à travers différents chemins en utilisant des plongements de nœuds (via la similitude cosinus). Lorsque la similitude dépasse un seuil $\kappa$ , les nœuds sont fusionnés en classes d'équivalence.
Réallocation du Budget : Lorsqu'un chemin atteint une classe d'équivalence existante, l'expansion ultérieure est jugée probablement redondante. GraphPO réduit de moitié le budget de la couche suivante pour ce chemin (en conservant au moins une continuation) et réalloue le calcul économisé vers de nouveaux états de frontière, encourageant ainsi une exploration plus large.

2.2 Récompense de Graphe (Supervision de Processus à partir de l'Issue)

GraphPO convertit les récompenses d'issue éparses en récompenses par étape denses sans nécessiter d'étiquettes de processus annotées :

Notation des États : Chaque nœud se voit attribuer un score basé sur les réponses vérifiées atteignables à partir de lui. Si un nœud appartient à une classe d'équivalence, son score est agrégé avec les scores des autres nœuds de cette classe, pondéré par un coefficient de regroupement $w$ .
Récompenses d'Étapes : La récompense pour une arête spécifique (étape) est calculée comme la différence entre les scores d'état des nœuds de destination et de source, pondérée par la similitude entre les deux extrémités. Cela permet aux branches arrêtées prématurément de recevoir du crédit de la part de partenaires équivalents ayant réussi à atteindre une réponse correcte.

2.3 Avantage Dual-Groupe de Graphe

Pour améliorer à la fois l'efficacité du raisonnement et l'attribution de crédit, GraphPO introduit une estimation d'avantage à double groupe :

Groupe de Correction ( $A_{cor}$ ) : Compare les étapes sortantes provenant du même état sémantique. Il calcule l'avantage d'une étape spécifique par rapport aux autres étapes sortant du même état, fournissant une attribution de crédit fine.
Groupe d'Efficacité ( $A_{eff}$ ) : Compare les chemins entrants qui atteignent le même état fusionné. Il récompense les chemins plus courts (moins de tokens/étapes) qui atteignent un état sémantique utile, encourageant la politique à trouver des trajectoires de raisonnement plus efficaces.

2.4 Optimisation de la Politique

La politique est optimisée à l'aide d'un objectif de type PPO qui combine l'avantage dual-groupe ( $A_{dual} = A_{cor} + \lambda_{eff} A_{eff}$ ). La fonction objectif maximise le rendement attendu tout en maintenant une contrainte de divergence KL par rapport à une politique de référence.

3. Contributions Clés

Cadre de Déroulement Basé sur les Graphes : GraphPO est le premier cadre de RL qui représente les déroulements de raisonnement comme un DAG, agrégeant explicitement les états de raisonnement équivalents pour permettre le partage de suffixes et la réallocation de budget.
Estimation d'Avantage Dual-Groupe : Le papier propose une méthode pour optimiser simultanément la correction du raisonnement (en comparant les étapes sortantes) et l'efficacité du raisonnement (en comparant les chemins entrants), réduisant ainsi la variance de l'estimation de l'avantage.
Supervision de Processus sans Annotations : La méthode dérive une supervision par étape dense à partir de récompenses d'issue éparses en exploitant la structure du graphe et les classes d'équivalence, éliminant le besoin de coûteuses annotations de Modèles de Récompense de Processus (PRM).

4. Résultats Expérimentaux

Des expériences ont été menées sur trois LLM (Qwen2.5-7B-Math, Qwen3-8B-Base, Deepseek-R1-Distill-Qwen-7B) sur des benchmarks de raisonnement mathématique (AIME24/25, MATH500, GPQA, LiveCodeBench) et des tâches de recherche agentique.

Performance : GraphPO a systématiquement surpassé les bases de comparaison basées sur les chaînes (GRPO, DAPO) et les arbres (TreeRL, SPO, PROS, TreePO) sur tous les modèles et jeux de données sous les mêmes budgets de tokens et de réponses. Par exemple, sur le modèle Qwen2.5-7B-Math, GraphPO a atteint une précision moyenne de 40,9 %, dépassant la meilleure base de comparaison basée sur l'arbre (PROS à 37,7 %).
Efficacité de l'Exploration : GraphPO a démontré une plus grande efficacité d'exploration, ce qui signifie qu'une plus grande proportion de calcul a été allouée à des progrès de raisonnement utiles plutôt qu'à des expansions redondantes. Il a maintenu une entropie plus élevée pendant l'entraînement par rapport aux méthodes basées sur les arbres, qui ont tendance à s'effondrer plus rapidement vers des schémas de raisonnement spécifiques.
Longueur de Réponse : GraphPO a produit des réponses plus courtes que les méthodes basées sur les arbres en fusionnant les états équivalents et en récompensant les chemins plus courts, améliorant ainsi l'efficacité de l'inférence.
Tâches Agentiques : La méthode a montré une performance supérieure dans les tâches de recherche profonde et agentique (General AI Assistant, WebWalker, BrowseComp, XBench), validant son applicabilité aux processus de prise de décision séquentielle.
Comparaison avec les PRM : GraphPO a surpassé les méthodes basées sur les PRM (ReasonFlux-PRM) sans utiliser de données de processus annotées supplémentaires.

5. Signification et Revendications

Le papier affirme que GraphPO fournit un mécanisme pratique pour obtenir une supervision de processus auto-émergente à partir des seules récompenses d'issue. En modélisant les déroulements comme un graphe, il répond aux limitations structurelles des arbres, qui ne peuvent pas représenter des états équivalents atteints par différents chemins.

Les auteurs affirment que GraphPO :

Réduit la Variance : La fusion des états équivalents et le regroupement des preuves en aval abaissent la variance de l'estimation de l'avantage.
Améliore l'Efficacité : Il réalloue les budgets de calcul loin des expansions redondantes vers une exploration diversifiée et récompense les chemins de raisonnement plus courts.
Améliore l'Utilisation : Il stabilise les mises à jour de la politique en permettant aux branches arrêtées prématurément de recevoir du crédit de la part de partenaires de succès équivalents, améliorant ainsi l'utilisation du budget de déroulement.

Ce travail suggère que les déroulements structurés en graphes offrent une alternative robuste aux méthodes basées sur les arbres pour augmenter les capacités de raisonnement des grands modèles de langage dans des contextes de récompenses vérifiables.