Technische Samenvatting: DecompRL

Probleemstelling

Grote taalmodellen (LLM's) hebben momenteel moeite met het oplossen van complexe problemen waarbij de basispolicy een bijna nul-kans heeft om een correcte oplossing te genereren. Bestaande strategieën kampen met significante knelpunten:

• Herhaaldelijk samplen (pass@k): Hoewel effectief voor het schalen van compute tijdens de inferentiefase, groeien de GPU-kosten lineair met het aantal pogingen. De prestatiewinst groeit vaak slechts logaritmisch ten opzichte van deze lineaire kosten.
• Standaard Reinforcement Learning (RL): Methoden zoals Proximal Policy Optimization (PPO) of Group Relative Policy Optimization (GRPO) verbeteren de nauwkeurigheid bij een enkele poging (pass@1), maar verminderen vaak de diversiteit van de samples. Dit ondermijnt hun effectiviteit bij het schalen van inferentie voor hoge $k$-waarden ($k \gg 100$).
• De Kernbeperking: Wanneer de zoekruimte te groot is, kunnen noch verhoogd samplen, noch gradiëntsignalen het lage probleem overwinnen waarbij de basispolicy een correcte oplossing produceert.

Methodologie: DecompRL

De auteurs stellen DecompRL voor, een reinforcement learning-framework dat de schaalingsbottleneck verschuift van dure GPU-inferentie naar goedkope CPU-evaluatie door gebruik te maken van hiërarchische modulaire generatie.

1. Hiërarchische Inferentie

In plaats van een monolithische code-oplossing te genereren, traint DecompRL modellen om een probleem te deconstrueren naar een hiërarchie van onafhankelijk oplosbare subfuncties.

• Decompositie-policy ($\pi(D)$): Breekt een probleem $x$ af in een set van $n$ functies, gespecificeerd door signaturen en natuurlijke taal docstrings ($D$).
• Implementatie-policy ($\pi(I|D)$): Genereert $k$ onafhankelijke implementaties voor elke functie in $D$.
• Recombinatie: Door $k$ implementaties te genereren voor elk van de $n$ functies, creëert het systeem $k^n$ kandidaat-oplossingen door recombinatie. Dit maakt een combinatorische explosie van potentiële programma's ($k^n$) mogelijk met slechts een lineaire inferentiekost ($k \times n$ tokens).

2. Reinforcement Learning Doelstellingen

DecompRL behandelt hiërarchische inferentie als een coöperatief multi-agent RL-probleem bestaande uit twee policies. Om de ijle beloningen (sparse rewards) en hoge variantie die inherent zijn aan recombinatie op te vangen, introduceren de auteurs specifieke algoritmische aanpassingen:

• LogMeanExp Doelstelling: Om exploratie en exploitatie in balans te brengen, gebruiken de auteurs een zachte doelstelling gedefinieerd als $\text{logmeanexp}_\beta(r_1, \dots, r_n) = \beta \log(\frac{1}{n} \sum e^{r_i/\beta})$. Dit interpoleert tussen het gemiddelde ($\beta \to \infty$) en het maximum ($\beta \to 0$), en benadert een log-uniforme mengeling van pass@k-doelstellingen.
• Leave-One-Out Baseline: Om policy gradients te berekenen, gebruiken de auteurs een leave-one-out baseline. Voor een specifieke actie (decompositie of implementatie) wordt het voordeel (advantage) berekend door de multi-sample doelstelling van de volledige set beloningen te vergelijken met de doelstelling berekend van de set die die actie uitsluit. Dit vermindert de gradiëntvariantie en voorkomt bias.
• Sequentiële Training: De decompositie- en implementatie-policies worden sequentieel getraind (door afwisselende stappen) in plaats van gezamenlijk. Dit adresseert het "moving target"-probleem in multi-agent RL, waardoor wordt voorkomen dat de implementatie-policy overfit op een specifieke decompositie en vice versa.

3. Computationele Verschuiving

De methode verschuift fundamenteel de computationele bottleneck:

• Standaard RL: Wordt gedomineerd door GPU-inferentiekosten voor het genereren van volledige oplossingen.
• DecompRL: Wordt gedomineerd door CPU-executiekosten voor het evalueren van gerecombineerde oplossingen. GPU-tokengeneratie wordt met ongeveer 50× verminderd voor equivalente evaluatiebudgetten (bijv. 512 evaluaties).

Belangrijkste Resultaten

Experimenten werden uitgevoerd op LiveCodeBench en CodeContests met behulp van Qwen 2.5 7B, Llama 3.1 8B Instruct en Code World Model 32B.

• Prestaties op Moeilijke Problemen: DecompRL presteert beter dan standaard RL-baselines (GRPO, pass@k training, SPO) wanneer de tokenbudgetten de $10^5$ overschrijden. Het lost problemen op die standaardgeneratie niet kan bereiken, met een succespercentage van tot wel 35% op de "harde" subset van LiveCodeBench.
• Schaalgedrag: Terwijl standaardmethoden verzadigen naarmate de tokenbudgetten toenemen, blijft het succespercentage van DecompRL schalen. Met tot wel 3 miljoen tokens per probleem presteert het significant beter dan bestaande methoden.
• Diversiteit en Recombinatie: De methode genereert diverse oplossingen. Analyse toont aan dat modellen getraind met DecompRL leren om grotere decomposities (meer functies) te maken naarmate de training vordert, wat correleert met hogere succespercentages bij grote inferentiebudgetten.
• Efficiëntie: Bij 512 evaluaties per probleem vermindert DecompRL de GPU-tokengeneratie van ~198k (standaard) naar ~4k, waardoor de dominantie van de wandkloktijd verschuift naar CPU-executie (99,6% CPU-tijd versus 0,4% GPU-tijd).

Betekenis en Claims

Het artikel beweert dat DecompRL een nieuw pad biedt voor het oplossen van "moeilijkere" problemen waar de basispolicy een bijna nul-kans heeft:

1. Het Overwinnen van de Cold Start: Het fungeert als een exploratietool om correcte oplossingen te ontdekken voor taken die onbereikbaar zijn voor standaard high-pass@k sampling, wat het een natuurlijke aanvulling maakt voor policy-distillatiepipelines.
2. Efficiënte Schaling: Door de generatiekosten te ontkoppelen van de evaluatiekosten, maakt het schaling van zoekacties op goedkope CPU-clusters mogelijk zonder de GPU-voetafdruk evenredig te vergroten.
3. Modulariteit als Controle-as: De resulterende generatiepipeline biedt interpreteerbaarheid en controle-assen die niet beschikbaar zijn bij herhaaldelijk samplen of geschaalde chain-of-thought methoden.
4. Beperkingen: De auteurs merken een "format tax" op waarbij hiërarchische inferentie onderpresteert op gemakkelijke problemen of lage tokenbudgetten vergeleken met monolithische generatie. Ze observeren ook een neiging tot "size collapse" (het verkleinen van de decompositiegrootte) tijdens de training, wat zij mitigeren via de logmeanexp-doelstelling en sequentiële training.

De auteurs positioneren DecompRL niet als een vervanging voor standaard RL post-training (dat nog steeds meer sample-efficiënt is voor sterke start-policies), maar als een gespecialiseerde exploratiestrategie voor het ontdekken van hoogwaardige data en het oplossen van voorheen onoplosbare taken.