Sintesi Tecnica: DecompRL

Definizione del Problema

I Large Language Models (LLM) attualmente faticano a risolvere problemi complessi in cui la policy di base ha una probabilità prossima allo zero di generare una soluzione corretta. Le strategie esistenti affrontano colli di bottiglia significativi:

• Campionamento Ripetuto (pass@k): Sebbene efficace per scalare il calcolo durante l'inferenza (test-time compute), il costo in termini di GPU cresce linearmente con il numero di tentativi. I guadagni di performance spesso crescono in modo logaritmico rispetto a questi costi lineari.
• Reinforcement Learning (RL) Standard: Metodi come Proximal Policy Optimization (PPO) o Group Relative Policy Optimization (GRPO) migliorano l'accuratezza del singolo tentativo (pass@1), ma spesso riducono la diversità del campionamento. Ciò ne mina l'efficacia quando si scala l'inferenza per valori di $k$ elevati ($k \gg 100$).
• Il Limite Fondamentale: Quando lo spazio di ricerca è troppo vasto, né l'aumento del campionamento né i segnali del gradiente possono superare la bassa probabilità che la policy di base produca una soluzione corretta.

Metodologia: DecompRL

Gli autori propongono DecompRL, un framework di reinforcement learning che sposta il collo di bottiglia della scalabilità dall'costosa inferenza su GPU alla più economica valutazione su CPU, sfruttando la generazione modulare gerarchica.

1. Inferenza Gerarchica

Invece di generare una soluzione di codice monolitica, DecompRL addestra i modelli a scomporre un problema in una gerarchia di sotto-funzioni risolvibili indipendentemente.

• Policy di Decomposizione ($\pi(D)$): Scompone un problema $x$ in un insieme di $n$ funzioni specificate da firme (signatures) e docstring in linguaggio naturale ($D$).
• Policy di Implementazione ($\pi(I|D)$): Genera $k$ implementazioni indipendenti per ogni funzione in $D$.
• Ricombinazione: Generando $k$ implementazioni per ciascuna delle $n$ funzioni, il sistema crea $k^n$ soluzioni candidate attraverso la ricombinazione. Ciò permette un'esplosione combinatoria di potenziali programmi ($k^n$) con un costo di inferenza solo lineare ($k \times n$ token).

2. Obiettivi di Reinforcement Learning

DecompRL tratta l'inferenza gerarchica come un problema di RL multi-agente cooperativo che coinvolge due policy. Per gestire la scarsità di reward e l'alta varianza inerenti alla ricombinazione, gli autori introducono specifiche adattamenti algoritmici:

• Obiettivo LogMeanExp: Per bilanciare esplorazione ed esploitazione, gli autori utilizzano una funzione obiettivo "soft" definita come $\text{logmeanexp}_\beta(r_1, \dots, r_n) = \beta \log(\frac{1}{n} \sum e^{r_i/\beta})$. Questa interpola tra la media ($\beta \to \infty$) e il massimo ($\beta \to 0$), approssimando un mix log-uniforme di obiettivi pass@k.
• Baseline Leave-One-Out: Per calcolare i gradienti della policy, gli autori utilizzano una baseline "leave-one-out". Per un'azione specifica (decomposizione o implementazione), l'advantage viene calcolato confrontando l'obiettivo multi-campione dell'intero set di reward contro l'obiettivo calcolato dal set che esclude quell'azione. Ciò riduce la varianza del gradiente e previene i bias.
• Addestramento Sequenziale: Le policy di decomposizione e di implementazione vengono addestrate sequenzialmente (tramite passi alternati) anziché congiuntamente. Questo affronta il problema del "target mobile" (moving target) nel RL multi-agente, impedendo alla policy di implementazione di andare in overfitting su una specifica decomposizione e viceversa.

3. Spostamento Computazionale

Il metodo sposta fondamentalmente il collo di bottiglia computazionale:

• RL Standard: Dominato dai costi di inferenza su GPU per generare soluzioni complete.
• DecompRL: Dominato dai costi di esecuzione su CPU per valutare le soluzioni ricombinate. La generazione di token su GPU è ridotta di circa 50× per budget di valutazione equivalenti (ad esempio, 512 valutazioni).

Risultati Chiave

Gli esperimenti sono stati condotti su LiveCodeBench e CodeContests utilizzando Qwen 2.5 7B, Llama 3.1 8B Instruct e Code World Model 32B.

• Performance su Problemi Difficili: DecompRL supera le baseline di RL standard (GRPO, pass@k training, SPO) quando i budget di token superano $10^5$. Risolve problemi che la generazione standard non riesce a raggiungere, ottenendo tassi di risoluzione fino al 35% sul subset "hard" di LiveCodeBench.
• Comportamento di Scalabilità: Mentre i metodi standard si saturano all'aumentare dei budget di token, il tasso di successo di DecompRL continua a scalare. Con fino a 3 milioni di token per problema, supera significativamente i metodi esistenti.
• Diversità e Ricombinazione: Il metodo genera soluzioni diverse. L'analisi mostra che i modelli addestrati con DecompRL imparano a creare decomposizioni più ampie (più funzioni) man mano che l'addestramento procede, il che correla con tassi di successo più elevati ad alti budget di inferenza.
• Efficienza: A 512 valutazioni per problema, DecompRL riduce la generazione di token su GPU da ~198k (standard) a ~4k, spostando la dominanza del tempo di esecuzione (wall-clock time) all'esecuzione su CPU (99,6% tempo CPU vs 0,4% tempo GPU).

Significato e Rivendicazioni

Il paper sostiene che DecompRL offre un nuovo percorso per risolvere problemi "più difficili" dove la policy di base ha tassi di successo prossimi allo zero:

1. Superare il Cold Start: Agisce come uno strumento di esplorazione per scoprire soluzioni corrette per task irraggiungibili tramite il normale campionamento high pass@k, rendendolo un complemento naturale per le pipeline di distillazione della policy.
2. Scalabilità Efficiente: Decoupling (disaccoppiamento) del costo di generazione dal costo di valutazione permette di scalare la ricerca su cluster CPU economici senza aumentare proporzionalmente l'impronta sulle GPU.
3. La Modularità come Asse di Controllo: La pipeline di generazione risultante offre interpretabilità e assi di controllo non disponibili nel campionamento ripetuto o nei metodi di chain-of-thought scalati.
4. Limitazioni: Gli autori notano una "tassa di formato" (format tax) in cui l'inferenza gerarchica è meno performante su problemi facili o bassi budget di token rispetto alla generazione monolitica. Osservano inoltre una tendenza al "collasso dimensionale" (size collapse) — ovvero la riduzione della dimensione della decomposizione — durante l'addestramento, che mitigano tramite l'obiettivo logmeanexp e l'addestramento sequenziale.

Gli autori posizionano DecompRL non come un sostituto del RL standard post-training (che rimane più efficiente in termini di campionamento per policy con una forte base di partenza), ma come una strategia di esplorazione specializzata per scoprire dati di alta qualità e risolvere compiti precedentemente insolubili.