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

Technical Summary: Provable Benefits of RLVR over SFT for Reasoning Models

Problem Formulation
This work addresses a fundamental gap in understanding why Reinforcement Learning with Verifiable Rewards (RLVR) often yields superior reasoning capabilities in Large Language Models (LLMs) compared to Supervised Fine-Tuning (SFT) on expert demonstrations. While empirical evidence suggests RLVR models generalize better and exhibit more robust reasoning, a principled theoretical framework explaining this divergence has been lacking.

The authors model Chain-of-Thought (CoT) reasoning as a pathfinding problem on a specific multigraph structure. The graph consists of a source node, a fork node branching into $W$ distinct paths, and $K$ sequential "diamond" subgraphs along each branch. Each diamond contains $L$ parallel multiedges. The reasoning task involves navigating from the source to a specific target leaf node. Crucially, the graph is designed such that efficient navigation requires the ability to detect dead ends (entering a non-target branch) and backtrack efficiently to the fork to explore alternative branches.

Methodology
The paper provides a dynamical analysis comparing two post-training paradigms applied to a pretrained bigram model (representing the world model):

1. Supervised Fine-Tuning (SFT): The model is trained on "golden" shortest-path trajectories from the source to the targets. These trajectories contain no backtracking, exploration, or failed attempts; they only demonstrate the correct forward path. The training objective is standard cross-entropy loss.
2. Reinforcement Learning with Verifiable Rewards (RLVR): The model is trained via on-policy rollouts. The reward function combines an outcome reward (reaching the target) with a length penalty (to discourage long, inefficient paths). The model learns via policy gradient updates, specifically analyzing the dynamics of signed gradient flow.

The authors analyze the evolution of transition probabilities for specific edge states:

• Forward states: Moving deeper into a branch.
• Backward states: Moving back toward the fork (backtracking).

They derive the gradient flow dynamics for the logits governing these transitions under both SFT and RLVR, proving convergence properties in finite time.

Key Contributions and Results

1. Failure of SFT to Learn Backtracking:
   The authors prove that SFT trained exclusively on golden shortest paths fails to learn an efficient backtracking strategy. Because the training data never exposes the model to dead ends or the need to retreat, the transition probabilities for backward states remain fixed at their pretrained uniform values. The model learns to move forward with probability 1 but retains no mechanism to efficiently retreat when a branch is incorrect.

2. Success of RLVR in Learning Backtracking:
   In contrast, the authors prove that RLVR-trained models learn to backtrack efficiently. The on-policy nature of RLVR forces the model to generate and experience failed rollouts (dead ends). The length penalty provides a gradient signal that explicitly penalizes long, meandering paths, incentivizing the model to learn that moving backward from a dead end is a necessary action to reach the target quickly. The model converges to a policy where both forward and backward transition probabilities approach 1, effectively learning to traverse a branch and immediately retreat if it is not the target.

3. Exponential Separation in Inference-Time Compute:
   The paper establishes a provable separation in the expected inference-time compute (hitting time) required to find a target:

   • RLVR Model: Requires $\Theta(WK)$ expected time. The model explores branches sequentially, traversing each in $O(K)$ time and retreating immediately upon failure.
   • SFT Model: Requires $\Theta(WLK)$ expected time. Because the SFT model cannot efficiently backtrack (it treats backward edges as a random walk among $L$ options), it takes $O(LK)$ time to exit a wrong branch.
   • This results in an exponential separation relative to the depth of the graph ($K$) and a linear separation relative to the branching factor of the diamonds ($L$).

4. Distillation of Reasoning Traces:
   The authors demonstrate that the benefits of RLVR can be transferred to a base model via distillation. If a base model is fine-tuned on the reasoning traces (including backtracking steps) generated by a converged RLVR model, it inherits the efficient backtracking capability, recovering the $\Theta(WK)$ inference-time complexity. This suggests that the critical factor is not the RL algorithm itself, but the inclusion of backtracking data in the training set.

Significance and Claims
The paper claims to provide the first theoretical proof that the superiority of RLVR over SFT for reasoning tasks stems from the ability of on-policy exploration to teach efficient backtracking. The authors argue that SFT on expert demonstrations is inherently limited because it lacks exposure to the "negative space" of reasoning (failed paths), leading to a model that cannot efficiently recover from errors.

The work highlights that:

• Backtracking is a learnable skill: It is not an inherent property of the architecture but a behavior induced by the training signal.
• Data composition matters: The inclusion of failed attempts and backtracking steps in training data (whether via RL exploration or distillation) is crucial for reducing search complexity.
• Theoretical grounding: The results offer a dynamical systems perspective on why RLVR generalizes better, moving beyond empirical observations to provable guarantees on inference-time efficiency.

The authors conclude that while distillation can transfer these capabilities, the RLVR process is the mechanism that generates the necessary data to learn efficient backtracking in the first place. The findings support the use of RLVR or the distillation of RL-generated traces to improve the reasoning capabilities of LLMs on complex, multi-step tasks.