🤖 machine learning

DecompRL: Solving Harder Problems by Learning Modular Code Generation

Das Paper stellt DecompRL vor, einen Reinforcement-Learning-Algorithmus, der es Large Language Models ermöglicht, zuvor unlösbare Programmieraufgaben zu lösen, indem er lernt, Aufgaben in modulare Teilfunktionen zu zerlegen, die dann rekombiniert werden, um den Suchraum exponentiell zu erweitern und die GPU-Inferenzkosten signifikant zu senken.

Ursprüngliche Autoren: Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

Veröffentlicht 2026-07-03

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Problem: Der „One-Shot“-Engpass

Stellen Sie sich vor, Sie versuchen, ein sehr schwieriges Rätsel zu lösen. Sie haben einen superintelligenten Roboter (ein Large Language Model), der versuchen kann, es für Sie zu lösen.

Derzeit ist die Standardmethode, einen Roboter dazu zu bringen, schwierige Rätsel zu lösen, ihn immer und immer wieder probieren zu lassen.

Der alte Weg: Sie fragen den Roboter: „Schreibe mir eine komplette Lösung.“ Wenn er scheitert, fragen Sie erneut. Wenn er wieder scheitert, fragen Sie erneut.
Das Problem: Jedes Mal, wenn Sie den Roboter bitten, eine komplette neue Lösung von Grund auf neu zu schreiben, kostet das viel Geld und Zeit (GPU-Leistung). Wenn das Rätsel wirklich schwer ist, muss der Roboter vielleicht Millionen Mal versuchen, um eine einzige richtige Lösung zu finden. Das ist so, als würde man einen Meisterkoch engagieren, um jedes Mal ein komplettes 10-Gänge-Menis von Grund auf neu zu kochen, nur um zu sehen, ob er ein ordentliches Omelett zubereiten kann. Das ist zu teuer.

Die neue Idee: Der „Lego“-Ansatz (DecompRL)

Die Autoren dieser Arbeit haben erkannt, dass wir den Roboter nicht fragen sollten, das ganze Schloss auf einmal zu bauen, sondern ihm beibringen sollten, das Schloss Stück für Stück zu bauen.

Betrachten Sie ein komplexes Programmierproblem wie den Bau eines riesigen Lego-Schlosses.

Standardmethode: Der Roboter versucht, das gesamte Schloss auf einmal zu bauen. Wenn er das Dach falsch macht, scheitert das gesamte Projekt.
DecompRL-Methode: Dem Roboter wird beigebracht, das Schloss in kleine, unabhängige Teile zu zerlegen: „Hier ist eine Wand“, „Hier ist eine Tür“, „Hier ist ein Fenster“.

Sobald der Roboter gelernt hat, diese kleinen Teile herzustellen, geschieht etwas Magisches: Rekombination.

Stellen Sie sich vor, der Roboter erstellt 5 verschiedene Versionen einer „Wand“, 5 verschiedene Versionen einer „Tür“ und 5 verschiedene Versionen eines „Fensters“.
Anstatt 5 ganze Schlösser zu bauen (was teuer ist), können Sie diese mischen und kombinieren. Sie können Wand Nr. 1, Tür Nr. 3 und Fenster Nr. 5 nehmen, um ein neues Schloss zu bauen. Dann Wand Nr. 2, Tür Nr. 1, Fenster Nr. 4.
Mit nur 15 kleinen Teilen können Sie 125 verschiedene Schlösser erstellen (5 x 5 x 5).

Wie es funktioniert: Der Zwei-Schritte-Tanz

Das Paper stellt eine neue Trainingsmethode namens DecompRL vor, die den Roboter lehrt, diesen „Lego“-Ansatz anzuwenden. Es verwendet zwei spezialisierte Rollen (Policies):

Der Architekt (Decomposition Policy): Dieser Teil des Roboters betrachtet das schwierige Problem und sagt: „Okay, um dies zu lösen, brauchen wir eine Sortierfunktion, eine mathematische Funktion und eine Druckfunktion.“ Er zerlegt das große Problem in kleine, handhabbare Aufgaben.
Der Baumeister (Implementation Policy): Dieser Teil des Roboters schreibt den Code für jede dieser kleinen Aufgaben.

Der magische Trick:
Das System generiert viele verschiedene Versionen des „Architektenplans“ und viele verschiedene Versionen des „Baumeister-Codes“. Dann nutzt es einen günstigen Computer (CPU), um alle Kombinationen miteinander zu mischen und zu kombinieren.

Die Verschiebung der Kosten: Das Schreiben des Codes ist teuer (wie das Engagieren eines hochbezahlten Architekten). Das Überprüfen, ob der Code funktioniert, ist günstig (wie eine einfache Qualitätskontrolle).
Das Ergebnis: Indem das System weniger „Gesamtlösungen“ generiert, aber viele „Teile“ mischt und kombiniert, kann es tausende potenzielle Lösungen testen, und das zum Preis der Generierung nur weniger vollständiger Antworten. Es verschiebt den Engpass von der teuren „Denkleistung“ (GPU) zur günstigen „Prüfleistung“ (CPU).

Warum das wichtig ist

Das Paper zeigt, dass für sehr schwere Probleme, bei denen der Roboter normalerweise 99,9 % der Zeit scheitert:

Standardmethoden gegen eine Wand laufen. Egal wie oft man den Roboter bittet, eine vollständige Lösung zu versuchen, er scheitert immer wieder.
DecompRL immer besser wird. Da es tausende Kombinationen durch das Mischen und Kombinieren kleiner Teile testen kann, findet es Lösungen, die die „Gesamtlösung“-Methode niemals finden könnte.

Der Haken (Einschränkungen)

Das Paper ist ehrlich über die Nachteile:

Die „Format-Steuer“: Für einfache Probleme ist das Zerlegen tatsächlich langsamer und weniger effizient. Es ist, als würde man ein Sandwich auseinandernehmen, um Brot und Fleisch separat zu essen, obwohl man das Sandwich einfach hätte essen können. Der Roboter muss speziell trainiert werden, um zu wissen, wann er Dinge zerlegen soll.
Schwierigkeit des Trainings: Der Roboter weiß nicht von Natur aus, wie er das machen soll. Er muss von Grund auf neu mit einem speziellen Reinforcement-Learning-Prozess trainiert werden, um die Rollen „Architekt“ und „Baumeister“ zu erlernen.

Zusammenfassung

DecompRL ist eine neue Art, KI beizubringen, schwierige Probleme zu lösen, indem man ihr verbietet, zu versuchen, die ganze Antwort auf einmal zu schreiben. Stattdessen bringt man der KI bei, einen Werkzeugkasten aus kleinen, wiederverwendbaren Teilen zu bauen. Durch das Mischen und Kombinieren dieser Teile kann die KI Millionen von Möglichkeiten testen, ohne den hohen Preis für die Generierung von Millionen voller Antworten zu zahlen. Es verwandelt ein teures „Raten und Prüfen“-Spiel in ein günstiges „Mischen und Kombinieren“-Spiel.

Technisches Resümee: DecompRL

Problemstellung

Große Sprachmodelle (LLMs) haben derzeit Schwierigkeiten, komplexe Probleme zu lösen, bei denen die Basis-Policy eine verschwindend geringe Wahrscheinlichkeit aufweist, eine korrekte Lösung zu generieren. Bestehende Strategien stehen vor signifikanten Engpässen:

Wiederholtes Sampling (pass@k): Obwohl dies effektiv für die Skalierung der Test-Compute ist, steigen die GPU-Kosten linear mit der Anzahl der Versuche. Die Leistungssteigerungen wachsen oft nur logarithmisch im Verhältnis zu diesen linearen Kosten.
Standard-Reinforcement-Learning (RL): Methoden wie Proximal Policy Optimization (PPO) oder Group Relative Policy Optimization (GRPO) verbessern die Genauigkeit eines Einzelversuchs (pass@1), reduzieren jedoch oft die Stichproben-Diversität. Dies untergräbt ihre Effektivität beim Skalieren der Inferenz für hohe $k$ -Werte ( $k \gg 100$ ).
Die Kernlimitierung: Wenn der Suchraum zu groß ist, können weder gesteigertes Sampling noch Gradientensignale die geringe Wahrscheinlichkeit überwinden, mit der die Basis-Policy eine korrekte Lösung produziert.

Methodik: DecompRL

Die Autoren schlagen DecompRL vor, ein Reinforcement-Learning-Framework, das den Skalierungsengpass von teurer GPU-Inferenz zu günstiger CPU-Evaluierung verschiebt, indem es hierarchische modulare Generierung nutzt.

1. Hierarchische Inferenz

Anstatt eine monolithische Code-Lösung zu generieren, trainiert DecompRL Modelle darauf, ein Problem in eine Hierarchie von unabhängig lösbaren Sub-Funktionen zu zerlegen.

Zerlegungs-Policy ( $\pi(D)$ ): Zerlegt ein Problem $x$ in eine Menge von $n$ Funktionen, die durch Signaturen und natürliche Sprach-Docstrings ( $D$ ) spezifiziert sind.
Implementierungs-Policy ( $\pi(I|D)$ ): Generiert $k$ unabhängige Implementierungen für jede Funktion in $D$ .
Rekombination: Durch das Generieren von $k$ Implementierungen für jede der $n$ Funktionen erzeugt das System durch Rekombination $k^n$ Kandidatenlösungen. Dies ermöglicht eine kombinatorische Explosion potenzieller Programme ( $k^n$ ) bei nur linearen Inferenzkosten ( $k \times n$ Token).

2. Reinforcement-Learning-Zielsetzungen

DecompRL behandelt hierarchische Inferenz als ein kooperatives Multi-Agenten-RL-Problem, das zwei Policies umfasst. Um die spärlichen Belohnungen (sparse rewards) und die hohe Varianz zu handhaben, die bei Rekombination auftreten, führen die Autoren spezifische algorithmische Anpassungen ein:

LogMeanExp-Zielsetzung: Um Exploration und Exploitation auszubalancieren, verwenden die Autoren eine Soft-Objective-Funktion definiert als $\text{logmeanexp}_\beta(r_1, \dots, r_n) = \beta \log(\frac{1}{n} \sum e^{r_i/\beta})$ . Diese interpoliert zwischen dem Durchschnitt ( $\beta \to \infty$ ) und dem Maximum ( $\beta \to 0$ ) und approximiert eine log-uniforme Mischung von pass@k-Zielsetzungen.
Leave-One-Out-Baseline: Um Policy-Gradienten zu berechnen, verwenden die Autoren eine Leave-One-Out-Baseline. Für eine spezifische Aktion (Zerlegung oder Implementierung) wird der Vorteil (Advantage) berechnet, indem der Multi-Sample-Objective des vollständigen Satzes von Belohnungen mit dem Objective verglichen wird, das aus dem Satz ohne diese Aktion berechnet wurde. Dies reduziert die Gradientenvarianz und verhindert Bias.
Sequentielles Training: Die Zerlegungs- und Implementierungs-Policies werden sequentiell trainiert (abwechselnde Schritte) statt gemeinsam. Dies adressiert das „Moving Target“-Problem in Multi-Agenten-RL und verhindert, dass die Implementierungs-Policy auf eine bestimmte Zerlegung überoptimiert und umgekehrt.

3. Kompensation des Engpasses

Die Methode verschiebt den Rechenengpass grundlegend:

Standard-RL: Dominiert von GPU-Inferenzkosten für die Generierung vollständiger Lösungen.
DecompRL: Dominiert von CPU-Ausführungskosten für die Evaluierung rekombinierter Lösungen. Die GPU-Token-Generierung wird um etwa den Faktor 50× reduziert (für äquivalente Evaluierungsbudgets, z. B. 512 Evaluierungen).

Kernergebnisse

Experimente wurden auf LiveCodeBench und CodeContests mit Qwen 2.5 7B, Llama 3.1 8B Instruct und Code World Model 32B durchgeführt.

Performance bei schwierigen Problemen: DecompRL übertrifft Standard-RL-Baselines (GRPO, pass@k Training, SPO), wenn die Token-Budgets $10^5$ überschreiten. Es löst Probleme, die durch Standard-Generierung nicht erreichbar sind, und erreicht bis zu 35 % Erfolgsraten auf dem „Hard“-Subset von LiveCodeBench.
Skalierungsverhalten: Während Standardmethoden mit steigenden Token-Budgets stagnieren, skaliert die Erfolgsrate von DecompRL kontinuierlich weiter. Mit bis zu 3 Millionen Token pro Problem übertrifft es bestehende Methoden signifikant.
Diversität und Rekombination: Die Methode generiert diverse Lösungen. Analysen zeigen, dass Modelle, die mit DecompRL trainiert wurden, im Verlauf des Trainings lernen, größere Zerlegungen (mehr Funktionen) zu erstellen, was mit höheren Erfolgsraten bei großen Inferenz-Budgets korreliert.
Effizienz: Bei 512 Evaluierungen pro Problem reduziert DecompRL die GPU-Token-Generierung von ~198k (Standard) auf ~4k, wodurch die Wandzeit (Wall-Clock Time) zur Dominanz der CPU-Ausführung wird (99,6 % CPU-Zeit vs. 0,4 % GPU-Zeit).

Bedeutung und Behauptungen

Das Paper behauptet, dass DecompRL einen neuartigen Weg bietet, um „schwierigere“ Probleme zu lösen, bei denen die Basis-Policy eine nahezu Null-Erfolgsrate hat:

Überwindung des Kaltstarts: Es fungiert als Explorationstool, um korrekte Lösungen für Aufgaben zu entdecken, die durch Standard-High-pass@k-Sampling unerreichbar sind, was es zu einer natürlichen Ergänzung für Policy-Distillations-Pipelines macht.
Effiziente Skalierung: Durch die Entkopplung von Generierungskosten und Evaluierungskosten ermöglicht es die Skalierung der Suche auf günstigen CPU-Clustern, ohne die GPU-Footprints proportional zu erhöhen.
Modularität als Kontrollachse: Die resultierende Generierungspipeline bietet Interpretierbarkeit und Kontrollachsen, die bei Repeated Sampling oder skalierten Chain-of-Thought-Methoden nicht verfügbar sind.
Limitierungen: Die Autoren merken eine „Format-Steuer“ (Format Tax) an, bei der hierarchische Inferenz bei einfachen Problemen oder niedrigen Token-Budgets schlechter abschneidet als monolithische Generierung. Sie beobachten zudem eine Tendenz zum „Size Collapse“ (Reduzierung der Zerlegungsgröße) während des Trainings, was sie durch die LogMeanExp-Zielsetzung und sequentielles Training mildern.

Die Autoren positionieren DecompRL nicht als Ersatz für Standard-RL-Post-Training (welches für starke Ausgangs-Policies weiterhin sampleffizienter ist), sondern als spezialisierte Explorationsstrategie zur Entdeckung hochwertiger Daten und zur Lösung bisher unlösbarer Aufgaben.