🤖 machine learning

DecompRL: Solving Harder Problems by Learning Modular Code Generation

L'article présente DecompRL, un algorithme d'apprentissage par renforcement qui permet aux grands modèles de langage de résoudre des problèmes de codage auparavant insolubles en apprenant à décomposer les tâches en sous-fonctions modulaires, lesquelles sont ensuite recombinées pour étendre de manière exponentielle l'espace de recherche et réduire considérablement les coûts d'inférence GPU.

Auteurs originaux : Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

Publié 2026-07-03

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

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

Le gros problème : le goulot d'étranglement du « One-Shot »

Imaginez que vous essayez de résoudre un puzzle très difficile. Vous avez un robot super intelligent (un grand modèle de langage) qui peut essayer de le résoudre pour vous.

Actuellement, la méthode standard pour demander au robot de résoudre des puzzles difficiles est de lui demander d'essayer encore et encore.

L'ancienne méthode : Vous demandez au robot : « Écris-moi une solution complète. » S'il échoue, vous demandez à nouveau. S'il échoue encore, vous demandez encore.
Le problème : Chaque fois que vous demandez au robot d'écrire une nouvelle solution entière en partant de zéro, cela coûte beaucoup d'argent et de temps (puissance GPU). Si le puzzle est vraiment difficile, le robot pourrait avoir besoin d'essayer des millions de fois pour en réussir une seule. C'est comme embaucher un chef étoilé pour cuisiner un repas complet de 10 services à partir de rien, chaque fois que vous voulez simplement voir s'il peut faire une omelette correcte. C'est trop coûteux.

La nouvelle idée : L'approche « Lego » (DecompRL)

Les auteurs de cet article ont réalisé qu'au lieu de demander au robot de construire tout le château d'un coup, nous devrions lui apprendre à construire le château pièce par pièce.

Pensez à un problème de codage complexe comme à la construction d'un immense château en Lego.

Méthode standard : Le robot essaie de construire tout le château en une seule fois. S'il se trompe dans le toit, tout l'ensemble échoue.
Méthode DecompRL : On apprend au robot à décomposer le château en petites parties indépendantes : « Voici un mur », « Voici une porte », « Voici une fenêtre ».

Une fois que le robot a appris à fabriquer ces petites parties, quelque chose de magique se produit : la Recombinaison.

Imaginez que le robot fabrique 5 versions différentes d'un « mur », 5 versions d'une « porte » et 5 versions d'une « fenêtre ».
Au lieu de construire 5 châteaux complets (ce qui est coûteux), vous pouvez les mélanger et les assortir. Vous pouvez prendre le Mur n°1, la Porte n°3 et la Fenêtre n°5 pour créer un nouveau château. Puis le Mur n°2, la Porte n°1 et la Fenêtre n°4.
Avec seulement 15 petites pièces, vous pouvez créer 125 châteaux différents (5 x 5 x 5).

Comment ça marche : La danse en deux étapes

L'article présente une nouvelle méthode d'entraînement appelée DecompRL qui apprend au robot à adopter cette approche « Lego ». Elle utilise deux rôles spécialisés (politiques) :

L'Architecte (Politique de décomposition) : Cette partie du robot regarde le problème difficile et dit : « D'accord, pour résoudre cela, nous avons besoin d'une fonction de tri, d'une fonction mathématique et d'une fonction d'impression. » Elle décompose le gros problème en petites tâches gérables.
Le Bâtisseur (Politique d'implémentation) : Cette partie du robot écrit le code pour chacune de ces petites tâches.

Le tour de magie :
Le système génère de nombreuses versions du « plan de l'Architecte » et de nombreuses versions du « code du Bâtisseur ». Ensuite, il utilise un ordinateur peu coûteux (CPU) pour mélanger et assortir toutes les combinaisons.

Le transfert de coût : Écrire le code est coûteux (comme embaucher un architecte de haut niveau). Vérifier si le code fonctionne est peu coûteux (comme un simple contrôle de qualité).
Le résultat : En générant moins de solutions « entières » mais en mélangeant et assortissant de nombreuses « parties », le système peut tester des milliers de solutions potentielles pour le prix de la génération de seulement quelques-unes. Cela déplace le goulot d'étranglement de la « puissance cérébrale » coûteuse (GPU) vers la « puissance de vérification » peu coûteuse (CPU).

Pourquoi c'est important

L'article montre que pour des problèmes très difficiles où le robot échoue habituellement 99,9 % du temps :

Les méthodes standards se heurtent à un mur. Peu importe le nombre de fois où vous demandez au robot d'essayer une solution entière, il continue d'échouer.
DecompRL continue de s'améliorer. Parce qu'il peut tester des milliers de combinaisons en mélangeant et assortissant de petites parties, il trouve des solutions que la méthode de la « solution entière » ne pourrait jamais trouver.

Le revers de la médaille (Limites)

L'article est honnête sur les inconvénients :

La « taxe de format » : Pour les problèmes faciles, décomposer est en fait plus lent et moins efficace. C'est comme démonter un sandwich pour manger le pain et la viande séparément alors que vous auriez pu simplement manger le sandwich. Le robot doit être entraîné spécifiquement pour savoir quand décomposer.
Difficulté d'entraînement : Le robot ne sait pas naturellement faire cela. Il doit être réentraîné de zéro en utilisant un processus spécial d'apprentissage par renforcement pour apprendre les rôles d'« Architecte » et de « Bâtisseur ».

Résumé

DecompRL est une nouvelle façon d'apprendre à l'IA à résoudre des problèmes difficiles en lui demandant d'arrêter d'essayer d'écrire la réponse entière d'un coup. Au lieu de cela, on lui apprend à construire une boîte à outils de petites parties réutilisables. En mélangeant et assortissant ces parties, l'IA peut tester des millions de possibilités sans payer le coût élevé de la génération de millions de réponses complètes. Cela transforme un jeu de « deviner et vérifier » coûteux en un jeu de « mélanger et assortir » peu coûteux.

Résumé Technique : DecompRL

Énoncé du Problème

Les grands modèles de langage (LLM) peinent actuellement à résoudre des problèmes complexes où la politique de base a une probabilité quasi nulle de générer une solution correcte. Les stratégies existantes font face à des goulots d'étranglement importants :

Échantillonnage répété (pass@k) : Bien qu'efficace pour l'augmentation du calcul au moment de l'inférence (test-time compute), le coût GPU croît linéairement avec le nombre de tentatives. Les gains de performance croissent souvent de manière logarithmique par rapport à ces coûts linéaires.
Apprentissage par renforcement (RL) standard : Les méthodes comme PPO (Proximal Policy Optimization) ou GRPO (Group Relative Policy Optimization) améliorent la précision à la première tentative (pass@1) mais réduisent souvent la diversité des échantillons. Cela compromet leur efficacité lors de la mise à l'échelle de l'inférence pour des valeurs de $k$ élevées ( $k \gg 100$ ).
La limitation fondamentale : Lorsque l'espace de recherche est trop vaste, ni l'augmentation de l'échantillonnage ni les signaux de gradient ne peuvent surmonter la faible probabilité que la politique de base produise une solution correcte.

Méthodologie : DecompRL

Les auteurs proposent DecompRL, un cadre d'apprentissage par renforcement qui déplace le goulot d'étranglement de l'inférence GPU coûteuse vers l'évaluation CPU peu coûteuse en exploitant une génération modulaire hiérarchique.

1. Inférence Hiérarchique

Au lieu de générer une solution de code monolithique, DecompRL entraîne les modèles à décomposer un problème en une hiérarchie de sous-fonctions résolvables indépendamment.

Politique de Décomposition ( $\pi(D)$ ) : Décompose un problème $x$ en un ensemble de $n$ fonctions spécifiées par des signatures et des docstrings en langage naturel ( $D$ ).
Politique d'Implémentation ( $\pi(I|D)$ ) : Génère $k$ implémentations indépendantes pour chaque fonction de $D$ .
Recombinaison : En générant $k$ implémentations pour chacune des $n$ fonctions, le système crée $k^n$ solutions candidates par recombinaison. Cela permet une explosion combinatoire de programmes potentiels ( $k^n$ ) avec un coût d'inférence seulement linéaire ( $k \times n$ tokens).

2. Objectifs d'Apprentissage par Renforcement

DecompRL traite l'inférence hiérarchique comme un problème de RL multi-agents coopératif impliquant deux politiques. Pour gérer la rareté des récompenses et la haute variance inhérentes à la recombinaison, les auteurs introduisent des adaptations algorithmiques spécifiques :

Objectif LogMeanExp : Pour équilibrer l'exploration et l'exploitation, les auteurs utilisent une fonction d'objectif douce définie par $\text{logmeanexp}_\beta(r_1, \dots, r_n) = \beta \log(\frac{1}{n} \sum e^{r_i/\beta})$ . Cela interpole entre la moyenne ( $\beta \to \infty$ ) et le maximum ( $\beta \to 0$ ), approximant un mélange log-uniforme des objectifs pass@k.
Baseline "Leave-One-Out" : Pour calculer les gradients de politique, les auteurs utilisent une base de référence de type "laisser de côté un élément" (leave-one-out). Pour une action spécifique (décomposition ou implémentation), l'avantage est calculé en comparant l'objectif multi-échantillon de l'ensemble complet des récompenses contre l'objectif calculé à partir de l'ensemble excluant cette action. Cela réduit la variance du gradient et évite les biais.
Entraînement Séquentiel : Les politiques de décomposition et d'implémentation sont entraînées séquentiellement (étapes alternées) plutôt que conjointement. Cela répond au problème de la "cible mouvante" dans le RL multi-agents, empêchant la politique d'implémentation de surapprendre une décomposition spécifique et vice versa.

3. Changement de Calcul

La méthode déplace fondamentalement le goulot d'étranglement computationnel :

RL Standard : Dominé par les coûts d'inférence GPU pour la génération de solutions complètes.
DecompRL : Dominé par les coûts d'exécution CPU pour l'évaluation des solutions recombinées. La génération de tokens par GPU est réduite d'environ 50× pour un budget d'évaluation équivalent (ex: 512 évaluations).

Résultats Clés

Des expériences ont été menées sur LiveCodeBench et CodeContests en utilisant Qwen 2.5 7B, Llama 3.1 8B Instruct et Code World Model 32B.

Performance sur les problèmes difficiles : DecompRL surpasse les bases de référence RL standard (GRPO, entraînement pass@k, SPO) lorsque les budgets de tokens dépassent $10^5$ . Il résout des problèmes que la génération standard ne peut atteindre, atteignant jusqu'à 35 % de taux de résolution sur le sous-ensemble "difficile" de LiveCodeBench.
Comportement de mise à l'échelle : Alors que les méthodes standard saturent à mesure que les budgets de tokens augmentent, le taux de réussite de DecompRL continue de croître. Avec jusqu'à 3 millions de tokens par problème, il surpasse significativement les méthodes existantes.
Diversité et Recombinaison : La méthode génère des solutions diverses. L'analyse montre que les modèles entraînés avec DecompRL apprennent à créer des décompositions plus larges (plus de fonctions) au fur et mesure de l'entraînement, ce qui est corrélé à des taux de réussite plus élevés pour les grands budgets d'inférence.
Efficacité : À 512 évaluations par problème, DecompRL réduit la génération de tokens GPU de ~198k (standard) à ~4k, déplaçant la dominance du temps d'exécution réel vers l'exécution CPU (99,6 % du temps CPU contre 0,4 % du temps GPU).

Signification et Revendications

L'article affirme que DecompRL offre une nouvelle voie pour résoudre des problèmes "plus difficiles" où la politique de base a des taux de succès proches de zéro :

Surmonter le "Cold Start" : Il agit comme un outil d'exploration pour découvrir des solutions correctes pour des tâches inaccessibles par un échantillonnage standard à haut pass@k, ce qui en fait un complément naturel aux pipelines de distillation de politique.
Mise à l'échelle efficace : En découplant le coût de génération du coût d'évaluation, il permet de mettre à l'échelle la recherche sur des clusters CPU peu coûteux sans augmenter proportionnellement l'empreinte GPU.
La Modularité comme Axe de Contrôle : Le pipeline de génération résultant offre une interprétabilité et des axes de contrôle non disponibles dans l'échantillonnage répété ou les méthodes de chaîne de pensée (chain-of-thought) mises à l'échelle.
Limites : Les auteurs notent une "taxe de format" où l'inférence hiérarchique est moins performante sur les problèmes faciles ou les faibles budgets de tokens par rapport à la génération monolithique. Ils observent également une tendance à l'effondrement de la taille ("size collapse") (réduction de la taille de la décomposition) pendant l'entraînement, qu'ils atténuent via l'objectif logmeanexp et l'entraînement séquentiel.

Les auteurs positionnent DecompRL non pas comme un remplacement du RL standard post-entraînement (qui reste plus efficace en termes d'échantillonnage pour les politiques de départ fortes) mais comme une stratégie d'exploration spécialisée pour découvrir des données de haute qualité et résoudre des tâches auparavant insolubles.