Résumé Technique : MURPHY – GRPO Sensible aux Retours avec Attribution Rétrospective des Crédits

Énoncé du Problème

L'apprentissage par renforcement avec récompenses vérifiables (RLVR) est devenu une approche standard pour le post-entraînement des modèles de langage de grande taille (LLM) sur des tâches de raisonnement, la méthode GRPO (Group Relative Policy Optimization) émergeant comme une approche de premier plan. Cependant, le GRPO standard et ses variantes sont intrinsèquement monotorne : ils s'optimisent sur la base de récompenses terminales provenant de paires isolées de prompts et de réponses. Cette architecture est inadaptée aux environnements agentiques, en particulier dans la génération de code, où les modèles doivent affiner itérativement leurs solutions en réponse à des retours de l'environnement (par exemple, erreurs d'exécution, traces de pile, cas de test échoués).

Les méthodes multitornes existantes reposent souvent sur des mécanismes auxiliaires complexes, tels que des vérificateurs appris (µCODE), des critiques de style PPO (RLEF) ou des politiques de vérification séparées (REVEAL). Une ligne de base naturelle, GRPO-MT, étend le GRPO au multitorne en traitant les interactions conditionnées par les retours comme des trajectoires. Cependant, le GRPO-MT souffre d'une attribution de crédits grossière : il attribue la même récompense terminale à tous les tokens d'une trajectoire, indépendamment du fait que des tentatives intermédiaires échouées aient fourni des retours informatifs permettant un raffinement ultérieur réussi. Dans la génération de code, une tentative échouée n'est pas uniformément négative ; elle peut révéler un cas limite spécifique ou une erreur d'exécution cruciale pour la solution finale. Les méthodes actuelles échouent à distinguer les « échecs informatifs » des « échecs non informatifs » lorsqu'ils partagent le même résultat terminal.

Méthodologie : MURPHY

Les auteurs introduisent MURPHY (Multi-turn Update with Retrospective Policy Optimization), une extension minimale du GRPO conçue pour rendre la recette standard de post-entraînement sensible aux retours sans introduire de critiques appris ni de vérificateurs auxiliaires.

1. Arbres de Déroulement Conditionnés par les Retours

MURPHY construit une structure arborescente pour chaque prompt d'entrée plutôt qu'une trajectoire linéaire :

• Tour 1 : Le modèle échantillonne un groupe de programmes candidats.
• Exécution et Retours : Chaque candidat est exécuté contre une suite de tests, générant une récompense scalaire (par exemple, taux de réussite) et des retours qualitatifs (par exemple, messages d'erreur).
• Expansion :
  • Les candidats résolus se terminent et deviennent des nœuds feuilles.
  • Les candidats échoués sont étendus. Un nouveau prompt est formé en concaténant la tâche originale, la sortie échouée et les retours de l'exécuteur. Le modèle est réinvoké sur ce prompt conditionné par les retours pour générer un nouveau groupe de raffinement.
• Ce processus se répète pour un nombre fixe de tours, créant un arbre où les arêtes représentent des étapes de raffinement conditionnées par des retours spécifiques.

2. Attribution Rétrospective des Crédits

L'innovation centrale est l'attribution rétrospective des crédits. Une fois l'arbre de déroulement terminé, les récompenses sont propagées en arrière, des feuilles vers la racine. Cela permet aux raffinement ultérieurs réussis de « créditer » les tentatives échouées antérieures qui ont produit des retours utiles. L'article propose deux stratégies de propagation :

• Récompense Maximale (MARS) : Une sauvegarde optimiste. Pour un nœud $v$, la récompense ajustée $\tilde{r}(v)$ est le maximum de sa récompense immédiate $r(v)$ et du maximum des récompenses ajustées de ses enfants :
  $$\tilde{r}(v) = \max\left(r(v), \max_{u \in C(v)} \tilde{r}(u)\right)$$
  Cela crédite une tentative échouée si l'un quelconque de ses descendants résout finalement la tâche.
• Récompense Moyenne (MERS) : Une sauvegarde basée sur l'espérance. Elle propage une moyenne décomptée des récompenses futures :
  $$\tilde{r}(v) = r(v) + \gamma \cdot \frac{\text{moyenne}_{u \in C(v)} \tilde{r}(u)}{Z(v)}$$
  où $\gamma$ est un facteur d'actualisation et $Z(v)$ un terme de normalisation.

3. Mise à Jour Locale GRPO

Une fois les récompenses ajustées, MURPHY applique l'objectif GRPO standard localement à chaque groupe de réponses au sein de l'arbre. Au lieu d'utiliser les récompenses immédiates, il utilise les récompenses ajustées par les crédits ($\tilde{r}$) pour calculer les avantages. Cela préserve la structure de base relative aux groupes du GRPO tout en intégrant le crédit temporel provenant de la structure arborescente.

4. Stratégies d'Élagage

Pour répondre au coût computationnel de l'expansion des arbres (qui peut croître de manière exponentielle), MURPHY introduit des mécanismes d'élagage post-déroulement qui conservent les trajectoires informatives avant la propagation des récompenses :

• Élagage Intra-Groupe (INTRAP) : Conserve un nombre fixe de trajectoires au sein de chaque groupe de réponses, en sélectionnant spécifiquement celles qui contribuent le plus à la variance des récompenses (préservant ainsi des signaux d'apprentissage diversifiés).
• Élagage Inter-Groupe (INTERP) : Conserve des groupes entiers de raffinement basés sur leur variance de récompense au sein du groupe. Cela alloue le budget d'optimisation aux contextes de retours qui produisent les raffinement de candidats les plus diversifiés et informatifs.

Contributions Clés

1. Algorithme MURPHY : Une extension GRPO multitorne qui entraîne les LLM de code à utiliser les retours d'exécution grâce à une attribution de crédits temporelle structurée, éliminant le besoin de vérificateurs ou de critiques appris.
2. Stratégies de Propagation des Récompenses : L'introduction des stratégies MARS (optimiste) et MERS (basée sur l'espérance) pour attribuer des crédits depuis les raffinement réussis vers les échecs antérieurs et informatifs.
3. Mécanismes d'Élagage : Conception des stratégies INTRAP et INTERP qui rendent l'optimisation multitorne traitable en filtrant les trajectoires non informatives tout en préservant le signal d'apprentissage.
4. Validation Empirique : Évaluation complète sur trois benchmarks (HumanEval, MBPP, LiveCodeBench-v6) et deux familles de modèles (Qwen, OLMo), démontrant des gains significatifs par rapport aux méthodes multitornes précédentes.

Résultats Expérimentaux

Les auteurs ont évalué MURPHY sur HumanEval, MBPP et LiveCodeBench-v6 en utilisant les modèles Qwen3 (1.7B, 4B) et OLMo-2-7B.

• Gains de Performance : MURPHY a obtenu jusqu'à 6 % de gains absolus en pass@1 par rapport aux méthodes multitornes d'exécution avec retours les plus performantes (incluant GRPO-MT, µCODE et REVEAL).
• Échelle de Difficulté : Les gains ont été les plus marqués sur les sous-ensembles Moyen et Difficile. Par exemple, sur LiveCodeBench-v6 (sous-ensemble Moyen), MURPHY a montré un gain de +4,38 % à l'itération 5, et sur le sous-ensemble Difficile, un gain de +4,20 %. Cela suggère que la méthode est particulièrement efficace là où l'auto-correction itérative est critique.
• Comparaison avec les Lignes de Base :
  • Sur OLMo-2-7B, MURPHY a surpassé la ligne de base la plus forte de +6,20 points de pourcentage sur HumanEval et +6,07 points de pourcentage sur MBPP dans le cadre de l'itération 3.
  • Sur Qwen3-4B (LiveCodeBench-v6), MURPHY a dépassé REVEAL (une méthode avec un auto-vérificateur co-entraîné) sur tous les sous-ensembles de difficulté, malgré l'architecture plus complexe de REVEAL.
• Études d'Ablation :
  • MARS vs MERS : MARS a généralement surpassé MERS, en particulier dans les environnements à récompenses rares, en propageant le résultat le plus fort plutôt qu'en diluant le signal par moyennage.
  • Élagage : La stratégie d'élagage INTERP a offert le meilleur compromis coût-qualité, réduisant le temps d'optimisation de 74,1 % (entraînant une réduction de 21,4 % du temps total d'entraînement par étape) tout en maintenant les performances à moins de 0,8 % du modèle non élagué. INTRAP, bien qu'améliorant les performances monotorne, a causé une régression des performances multitorne.

Signification et Revendications

L'article revendique que MURPHY démontre que la recette standard de post-entraînement GRPO peut être rendue sensible aux retours par un changement structurel de l'attribution des crédits uniquement.

• Minimalisme Architectural : Contrairement aux travaux antérieurs nécessitant des fonctions de valeur auxiliaires, des vérificateurs appris ou des politiques de vérification explicites, MURPHY est une « extension minimale préservant l'architecture ». Il repose uniquement sur les retours d'exécution inhérents à la tâche de génération de code.
• Inadéquation de l'Attribution des Crédits : Le travail aborde une inadéquation fondamentale dans la génération de code agentique : l'échec à distinguer les erreurs non informatives des échecs informatifs. En propageant les récompenses en arrière, MURPHY enseigne au modèle que « se tromper et se tromper encore » (comme cité de Piet Hein) est précieux si les erreurs fournissent le signal nécessaire à la correction.
• Évolutivité : Les stratégies d'élagage proposées rendent l'entraînement multitorne computationnellement faisable, réduisant la charge d'optimisation sans sacrifier la qualité du signal d'apprentissage.

Les auteurs concluent que, bien que les déroulements multitorne augmentent les coûts d'entraînement par rapport au GRPO monotorne, les gains en capacités d'auto-correction, en particulier sur les problèmes difficiles, justifient l'approche. Ils notent des limitations concernant l'augmentation du coût d'entraînement et la dépendance à des retours d'exécution propres, suggérant que des travaux futurs pourraient explorer des signaux de retours plus bruyants et des budgets de tours adaptatifs.