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

Technische Samenvatting: Bewijsbare voordelen van RLVR ten opzichte van SFT voor redeneermodellen

Probleemformulering
Dit werk adresseert een fundamentele kloof in het begrip van waarom Reinforcement Learning met Verifieerbare Beloningen (RLVR) vaak superieure redeneercapaciteiten oplevert in Large Language Models (LLMs) vergeleken met Supervised Fine-Tuning (SFT) op expertdemonstraties. Hoewel empirisch bewijs suggereert dat RLVR-modellen beter generaliseren en robuuster redeneren, ontbrak tot nu toe een fundamenteel theoretisch kader om deze divergentie te verklaren.

De auteurs modelleren Chain-of-Thought (CoT) redeneren als een padvindingsprobleem op een specifieke multigraafstructuur. De graaf bestaat uit een bronknooppunt, een splitsingsknooppunt dat vertakt in $W$ verschillende paden, en $K$ sequentiële "diamant"-subgrafen langs elk tak. Elke diamant bevat $L$ parallelle multiedges. De redeneertaak behelst het navigeren van de bron naar een specifere doelbladknooppunt. Cruciaal is dat de graaf zo is ontworend dat efficiënte navigatie de mogelijkheid vereist om doodlopende wegen te detecteren (een niet-doelgerichte tak binnengaan) en efficiënt terug te keren (backtracken) naar de splitsing om alternatieve takken te verkennen.

Methodologie
Het artikel biedt een dynamische analyse waarbij twee post-training paradigma's worden vergeleken die worden toegepast op een vooraf getraind bigram-model (dat een wereldmodel representeert):

1. Supervised Fine-Tuning (SFT): Het model wordt getraind op "gouden" kortste-pad-trajecten van de bron naar de doelen. Deze trajecten bevatten geen backtracking, exploratie of mislukte pogingen; ze demonstreren enkel het correcte voorwaartse pad. De trainingsdoelstelling is de standaard cross-entropy loss.
2. Reinforcement Learning met Verifieerbare Beloningen (RLVR): Het model wordt getraind via on-policy rollouts. De beloningsfunctie combineert een uitkomstbeloning (het bereiken van het doel) met een lengtestraf (om lange, inefficiënte paden te ontmoedigen). Het model leert via policy gradient updates, waarbij specifiek de dynamica van de gesigneerde gradiëntstroom wordt geanalyseerd.

De auteurs analyseren de evolutie van transitiekansen voor specifieke edge-toestanden:

• Forward states: Dieper in een tak bewegen.
• Backward states: Terug bewegen naar de splitsing (backtracking).

Zij leiden de gradiëntstroomdynamica af voor de logits die deze transities aansturen onder zowel SFT als RLVR, en bewijzen convergentie-eigenschappen in eindige tijd.

Belangrijkste bijdragen en resultaten

1. Het falen van SFT bij het leren van backtracking:
   De auteurs bewijzen dat SFT, uitsluitend getraind op gouden kortste paden, er niet in slaagt om een efficiënte backtracking-strategie te leren. Omdat de trainingsdata het model nooit blootstelt aan doodlopende wegen of de noodzaak om terug te keren, blijven de transitiekansen voor backward states vastgezet op hun vooraf getrainde uniforme waarden. Het model leert met een waarschijnlijkheid van 1 voorwaarts te bewegen, maar behoudt geen mechanisme om efficiënt terug te keren wanneer een tak incorrect is.

2. Het succes van RLVR bij het leren van backtracking:
   In tegen plaats daarvan bewijzen de auteurs dat RLVR-getrainde modellen efficiënt leren backtracken. De on-policy aard van RLVR dwingt het model om rollouts en mislukte trajecten (doodlopende wegen) te genereren en te ervaren. De lengtestraf levert een gradiëntsignaal dat expliciet lange, dwalende paden bestraft, wat het model stimuleert om te leren dat terugwaarts bewegen vanuit een doodlopende weg een noodzakelijke actie is om het doel snel te bereiken. Het model convergeert naar een beleid waarbij zowel de forward als de backward transitiekansen naar 1 benaderen, waardoor het effectief leert een tak te doorlopen en onmiddellijk terug te keren als het niet het doel is.

3. Exponentiële separatie in inference-time compute:
   Het artikel stelt een bewijsbare separatie vast in de verwachte inference-time compute (hitting time) die nodig is om een doel te vinden:

   • RLVR Model: Vereist $\Theta(WK)$ verwachte tijd. Het model verkent takken sequentieel, doorloopt elke tak in $O(K)$ tijd en keert onmiddellijk terug bij falen.
   • SFT Model: Vereist $\Theta(WLK)$ verwachte tijd. Omdat het SFT-model niet efficiënt kan backtracken (het behandelt backward edges als een random walk tussen $L$ opties), duurt het $O(LK)$ tijd om een foutieve tak te verlaten.
     Dit resulteert in een exponentiële separatie ten opzichte van de diepte van de graaf ($K$) en een lineaire separatie ten opzichte van de vertakkingsfactor van de diamanten ($L$).

4. Distillatie van redeneertrajecten:
   De auteurs demonstreren dat de voordelen van RLVR kunnen worden overgedragen naar een basismodel via distillatie. Als een basismodel wordt gefinetuned op de redeneertrajecten (inclusclusief backtracking-stappen) gegenereerd door een geconvergeerd RLVR-model, erft het de efficiënte backtracking-capaciteit, waardoor de $\Theta(WK)$ inference-time complexiteit wordt hersteld. Dit suggereert dat de cruciale factor niet het RL-algoritme zelf is, maar de inclusie van backtracking-data in de trainingsset.

Betekenis en claims
Het artikel claimt het eerste theoretische bewijs te leveren dat de superioriteit van RLVR boven SFT voor redenstaak voortkomt uit het vermogen van on-policy exploratie om efficiënte backtracking te leren. De auteurs stellen dat SFT op expertdemonstraties inherent beperkt is omdat het een gebrek aan blootstelling heeft aan de "negatieve ruimte" van redeneren (mislukte paden), wat leidt tot een model dat niet efficiënt kan herstellen van fouten.

Het werk benadrukt dat:

• Backtracking een leerbare vaardigheid is: Het is geen inherente eigenschap van de architectuur, maar een gedrag dat wordt geïnduceerd door het trainingssignaal.
• De samenstelling van data ertoe doet: De inclusie van mislukte pogingen en backtracking-stappen in de trainingsdata (of het nu via RL-exploratie of distillatie gaat) is cruciaal voor het verminderen van de zoekcomplexiteit.
• Theoretische onderbouwing: De resultaten bieden een dynamisch systeemperspectief op waarom RLVR beter generaliseert, waarbij zij verder gaan dan empirische observaties door middel van bewijsbare garanties op de efficiëntie van de inference-time.

De auteurs concluderen dat hoewel distillatie deze capaciteiten kan overdragen, het RLVR-proces het mechanisme is dat de noodzakelijke data genereert om efficiënte backtracking te leren. De bevindingen ondersteunen het gebruik van RLVR of de distillatie van door RL gegenereerde trajecten om de redeneercapaciteiten van LLM's op complexe, meerstaps-taken te verbeteren.