Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently

Sintesi Tecnica: Benefici Provabili di RLVR rispetto a SFT per Modelli di Ragionamento

Formulazione del Problema
Questo lavoro affronta una lacuna fondamentale nella comprensione del perché il Reinforcement Learning con Verifiable Rewards (RLVR) produca spesso capacità di ragionamento superiori nei Large Language Models (LLM) rispetto al Supervised Fine-Tuning (SFT) su dimostrazioni esperte. Mentre l'evidenza empirica suggerisce che i modelli RLVR generalizzino meglio e mostrino un ragionamento più robusto, mancava un quadro teorico fondato per spiegare questa divergenza.

Gli autori modellano il ragionamento Chain-of-Thought (CoT) come un problema di ricerca di un percorso su una specifica struttura di multigrafo. Il grafo consiste in un nodo sorgente, un nodo di biforcazione che si dirama in $W$ percorsi distinti, e $K$ sottografi "diamante" sequenziali lungo ogni ramo. Ogni diamante contiene $L$ multilegami paralleli. Il compito di ragionamento consiste nel navigare dal nodo sorgente a un nodo foglia target specifico. Fondamentalmente, il grafo è progettato in modo tale che la navigazione efficiente richieda la capacità di rilevare i vicoli ciechi (entrare in un ramo non target) e di effettuare il backtracking in modo efficiente verso la biforcazione per esplorare altri rami.

Metodologia
Il documento fornisce un'analisi dinamica confrontando due paradigmi di post-training applicati a un modello bigramma pre-addestrato (che rappresenta il modello del mondo):

1. Supervised Fine-Tuning (SFT): Il modello viene addestrato su traiettorie "golden" (ottimali) di percorso breve dal sorgente ai target. Queste traiettorie non contengono backtracking, esplorazione o tentativi falliti; esse dimostrano solo il percorso corretto in avanti. L'obiettivo di addestramento è la standard cross-entropy loss.
2. Reinforcement Learning con Verifiable Rewards (RLVR): Il modello viene addestrato tramite rollout on-policy. La funzione di reward combina un reward di esito (raggiungere il target) con una penalità di lunghezza (per scoraggiare percorsi lunghi ed inefficienti). Il modello apprende tramite aggiornamenti di policy gradient, analizzando specificamente la dinamica del flusso di gradiente con segno.

Gli autori analizzano l'evoluzione delle probabilità di transizione per specifici stati di legame:

• Stati forward (in avanti): Muoversi più in profondamente in un ramo.
• Stati backward (indietro): Muoversi all'indietro verso la biforcazione (backtracking).

Derivano le dinamiche del flusso di gradiente per i logit che governano queste transizioni sotto SFT e RLVR, provando le proprietà di convergenza in tempo finito.

Contributi Chiave e Risultati

1. Fallimento di SFT nell'apprendere il Backtracking:
   Gli autori dimostrano che l'SFT addestrato esclusivamente su percorsi brevi "golden" fallisce nell'apprendere una strategia di backtracking efficiente. Poiché i dati di addestramento non espongono mai il modello a vicoli ciechi o alla necessità di ritirarsi, le probabilità di transizione per gli stati backward rimangono fissate ai loro valori uniformi pre-addestrati. Il modello impara a muoversi in avanti con probabilità 1, ma non possiede alcun meccanismo per ritirarsi efficientemente quando un ramo è errato.

2. Successo di RLVR nell'apprendere il Backtracking:
   Al contrario, gli autori dimostrano che i modelli addestrati con RLVR imparano a eseguire il backtracking in modo efficiente. La natura on-policy di RLVR costringe il modello a generare ed esperire rollout falliti (vicoli ciechi). La penalità di lunghezza fornisce un segnale di gradiente che penalizza esplicitamente i percorsi lunghi e tortuosi, incentivando il modello a imparare che muoversi all'indietro da un vicolo cieco è un'azione necessaria per raggiungere il target rapidamente. Il modello converge a una policy in cui sia le probabilità di transizione forward che quelle backward tendono a 1, imparando efficacementamente a attraversare un ramo e ritirarsi immediatamente se non è quello target.

3. Separazione Esponenziale nel Calcolo al Tempo di Inferenza:
   Il documento stabilisce una separazione provabile nel calcolo atteso al tempo di inferenza (hitting time) richiesto per trovare un target:

   • Modello RLVR: Richiede un tempo atteso di $\Theta(WK)$. Il modello esplora i rami sequenzialmente, attraversandone ciascuno in $O(K)$ tempo e ritirandosi immediatamente in caso di fallimento.
   • Modello SFT: Richiede un tempo atteso di $\Theta(WLK)$. Poiché il modello SFT non può eseguire il backtracking in modo efficiente (tratta i legami backward come un random walk tra $L$ opzioni), impiega $O(LK)$ tempo per uscire da un ramo errato.
   • Ciò risulta in una separazione esponenziale rispetto alla profondità del grafo ($K$) e una separazione lineare rispetto al fattore di ramificazione dei diamanti ($L$).

4. Distillazione delle Tracce di Ragionamento:
   Gli autori dimostrano che i benefici di RLVR possono essere trasferiti a un modello base tramite distillazione. Se un modello base viene sottoposto a fine-tuning sulle tracce di ragionamento (incluse le fasi di backtracking) generate da un modello RLVR convergente, esso eredita la capacità di backtracking efficiente, recuperando la complessità temporale di $\Theta(WK)$. Ciò suggerisce che il fattore critico non è l'algoritmo di RL in sé, ma l'inclusione di dati di backtracking nel set di addestramento.

Significato e Rivendicazioni
Il documento sostiene di fornire la prima prova teorica del fatto che la superiorità di RLVR rispetto a SFT per i compiti di ragionamento derivi dalla capacità dell'esplorazione on-policy di insegnare un backtracking efficiente. Gli autori sostengono che l'SFT su dimostrazioni esperte è intrinsecamente limitato perché manca l'esposizione allo "spazio negativo" del ragionamento (percorsi falliti), portando a un modello che non può recuperare efficientemente dagli errori.

Il lavoro evidenzia che:

• Il backtracking è una competenza apprendibile: Non è una proprietà inerente all'architettura, ma un comportamento indotto dal segnale di addestramento.
• La composizione dei dati è importante: L'inclusione di tentativi falliti e passi di backtracking nei dati di addestramento (sia tramite esplorazione RL che tramite distillazione) è cruciale per ridurre la complessità della ricerca.
• Fondamento Teorico: I risultati offrono una prospettiva di sistemi dinamici sul perché RLVR generalizzi meglio, andando oltre le osservazioni empiriche per offrire garanzie provabili sull'efficienza del tempo di inferenza.

Gli autori concludono che, sebbene la distillazione possa trasferire queste capacità, il processo di RLVR è il meccanismo che genera i dati necessari per apprendere il backtracking efficiente in primo luogo. Le conclusioni supportano l'uso di RLVR o della distillazione di tracce generate da RL per migliorare le capacità di ragionamento degli LLM su compiti complessi e multi-step.