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

Technisches Resümee: Beweisbare Vorteile von RLVR gegenüber SFT für Reasoning-Modelle

Problemformulierung
Diese Arbeit adressiert eine fundamentale Lücke im Verständnis der Frage, warum Reinforcement Learning mit verifizierbaren Belohnungen (RLVR) oft überlegene Denkfähigkeiten (Reasoning) in Large Language Models (LLMs) hervorbringt, verglichen mit Supervised Fine-Tuning (SFT) auf Experten-Demonstrationen. Während empirische Belege darauf hindeuten, dass RLVR-Modelle besser generalisieren und robustere Denkprozesse aufweisen, fehlte bisher ein fundierter theoretischer Rahmen, der diese Divergenz erklärt.

Die Autoren modellieren die Chain-of-Thought (CoT)-Argumentation als Pfadfindungsproblem auf einer spezifischen Multigraphen-Struktur. Der Graph besteht aus einem Quellknoten, einem Verzweigungsknoten, der in $W$ verschiedene Pfade verzweigt, und $K$ sequenziellen „Diamant“-Subgraphen entlang jedes Zweigs. Jeder Diamant enthält $L$ parallele Multikanten. Die Denkaufgabe besteht darin, vom Quellknoten zu einem spezifischen Ziel-Blattknoten zu navigieren. Entscheidend ist, dass der Graph so konstruiert ist, dass eine effiziente Navigation die Fähigkeit erfordert, Sackgassen zu erkennen (das Betreten eines falschen Zweigs) und effizient zum Verzweigungsknoten zurückzukehren (Backtracking), um alternative Zweige zu explorieren.

Methodik
Die Arbeit liefert eine dynamische Analyse, die zwei Post-Training-Paradigmen vergleicht, die auf ein vortrainiertes Bigram-Modell (als Repräsentation des Weltmodells) angewendet werden:

1. Supervised Fine-Tuning (SFT): Das Modell wird auf „goldenen“ kürzesten Pfad-Trajektorien vom Quellknoten zu den Zielen trainiert. Diese Trajektorien enthalten kein Backtracking, keine Exploration und keine Fehlversuche; sie demonstrieren lediglich den korrekten Vorwärtspfad. Das Trainingsziel ist der Standard-Cross-Entropy-Loss.
2. Reinforcement Learning mit verifizierbaren Belohnungen (RLVR): Das Modell wird mittels On-Policy-Rollouts trainiert. Die Belohnungsfunktion kombiniert eine Ergebnisbelohnung (Erreichen des Ziels) mit einer Längenstrafe (um lange, ineffiziente Pfade zu unterdrücken). Das Modell lernt über Policy-Gradient-Updates, wobei speziell die Dynamik des signierten Gradientenflusses analysiert wird.

Die Autoren analysieren die Entwicklung der Übergangswahrscheinlichkeiten für spezifische Kanten-Zustände:

• Vorwärts-Zustände (Forward states): Bewegung tiefer in einen Zweig hinein.
• Rückwärts-Zustände (Backward states): Bewegung zurück zum Verzweigungsknoten (Backtracking).

Sie leiten die Gradientenfluss-Dynamiken für die Logits, welche diese Übergänge steuern, unter SFT und RLVR her und beweisen die Konvergenzeigenschaften in endlicher Zeit.

Wesentliche Beiträge und Ergebnisse

1. Versagen von SFT beim Erlernen von Backtracking:
   Die Autoren beweisen, dass SFT, das ausschließlich auf goldenen kürzesten Pfaden trainiert wurde, scheitert, eine effiziente Backtracking-Strategie zu erlernen. Da die Trainingsdaten dem Modell niemals Sackgassen oder die Notwendigkeit des Rückzugs exponieren, bleiben die Übergangswahrscheinlichkeiten für Rückwärts-Zustände auf ihren vortrainierten uniformen Werten fixiert. Das Modell lernt, mit einer Wahrscheinlichkeit von 1 vorwärts zu gehen, besitzt aber keinen Mechanismus, um effizient zurückzuweichen, wenn ein Zweig falsch ist.

2. Erfolg von RLVR beim Erlernen von Backtracking:
   Im Gegensatz dazu beweisen die Autoren, dass RLVR-trainierte Modelle effizientes Backtracking erlernen. Die On-Policy-Natur von RLVR zwingt das Modell dazu, Rollouts zu generieren und gescheiterte Durchläufe (Sackgassen) zu erleben. Die Längenstrafe liefert ein Gradientensignal, das lange, ausschweifende Pfade explizit bestraft, was das Modell dazu motiviert, zu lernen, dass eine Bewegung rückwärts von einer Sackgasse aus eine notwendige Aktion ist, um das Ziel schnell zu erreichen. Das Modell konvergiert zu einer Policy, bei der sowohl die Vorwärts- als auch die Rückwärts-Übergangswahrscheinlichkeiten gegen 1 gehen, wodurch es effektiv lernt, einen Zweig zu durchqueren und sofort zurückzukehren, falls dies nicht der Zielzweig ist.

3. Exponentielle Separation in der Inferenzzeit-Rechenleistung:
   Die Arbeit etabliert eine beweisbare Separation in der erwarteten Inferenzzeit-Rechenleistung (Hitting Time), die erforderlich ist, um ein Ziel zu finden:

• RLVR-Modell: Erfordert eine erwartete Zeit von $\Theta(WK)$. Das Modell exploriert Zweige sequenziell, durchläuft jeden in $O(K)$ Zeit und zieht sich bei einem Fehler sofort zurück.
• SFT-Modell: Erfordert eine erwartete Zeit von $\Theta(WLK)$. Da das SFT-Modell nicht effizient zurückkehren kann (es behandelt Rückwärtskanten als Random Walk unter $L$ Optionen), benötigt es $O(LK)$ Zeit, um einen falschen Zweig zu verlassen.
  Dies führt zu einer exponentiellen Separation relativ zur Tiefe des Graphen ($K$) und einer linearen Separation relativ zur Verzweigungsrate der Diamanten ($L$).

4. Destillation von Reasoning-Traces:
   Die Autoren zeigen, dass die Vorteile von RLVR durch Destillation auf ein Basismodell übertragen werden können. Wenn ein Basismodell auf den Reasoning-Traces (einschließlich Backtracking-Schritten) trainiert wird, die von einem konvergierten RLVR-Modell generiert wurden, erbt es die effiziente Backtracking-Fähigkeit und stellt die $\Theta(WK)$ Inferenzzeit-Komplexität wieder her. Dies deutet darauf hin, dass der entscheidende Faktor nicht der RL-Algorithmus selbst ist, sondern die Einbeziehung von Backtracking-Daten in den Trainingssatz.

Bedeutung und Behauptungen
Die Arbeit behauptet, den ersten theoretischen Beweis dafür zu liefern, dass die Überlegenheit von RLVR gegenüber SFT bei Reasoning-Aufgaben aus der Fähigkeit der On-Policy-Exploration resultiert, effizientes Backtracking zu lehren. Die Autoren argumentieren, dass SFT auf Experten-Demonstrationen inhärent begrenzt ist, da es keinen Kontakt zum „negativen Raum“ des Denkens (fehlgeschlagene Pfade) hat, was dazu führt, dass ein Modell nicht in der Lage ist, effizient von Fehlern zu erholen.

Die Arbeit hebt hervor, dass:

• Backtracking eine lernbare Fähigkeit ist: Es ist keine inhärente Eigenschaft der Architektur, sondern ein Verhalten, das durch das Trainingssignal induziert wird.
• Die Zusammensetzung der Daten entscheidend ist: Die Einbeziehung von Fehlversuchen und Backtracking-Schritten in den Trainingsdatensatz (sei es durch RL-Exploration oder Destillation) ist entscheidend für die Reduzierung der Suchkomplexität.
• Theoretische Fundierung: Die Ergebnisse bieten eine dynamische Systemperspektive darauf, warum RLVR besser generalisiert, indem sie über empirische Beobachtungen hinausgehen und beweisbare Garantien auf die Effizienz der Inferenzzeit bieten.

Die Autoren kommen zu dem Schluss, dass die Destillation zwar diese Fähigkeiten übertragen kann, der RLVR-Prozess jedoch der Mechanismus ist, der die notwendigen Daten generiert, um effizientes Backtracking überhaupt erst zu erlernen. Die Ergebnisse unterstützen den Einsatz von RLVR oder der Destillation von RL-generierten Traces, um die Reasoning-Fähigkeiten von LLMs bei komplexen, mehrstufigen Aufgaben zu verbessern.