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

As large language models (LLMs) are increasingly used for complex reasoning, the method of post-training—specifically the choice between supervised fine-tuning (SFT) and reinforcement learning with verifiable rewards (RLVR)—has become a critical design decision. While SFT is the standard for imitating expert demonstrations, it is often prone to memorization and lacks a mechanism for handling errors. This paper investigates why RLVR often outperforms SFT in reasoning tasks, specifically focusing on the ability to backtrack—the process of returning to an earlier decision point when a path is identified as incorrect.

The authors model chain-of-thought (CoT) reasoning as a pathfinding problem on a multigraph. In this framework, a model must navigate from a source node to a target leaf node through a series of 'diamonds' (subgraphs with multiple edges). The researchers compare SFT, which is trained only on golden shortest-path demonstrations, against RLVR, which learns via on-policy exploration and outcome-based rewards. By analyzing the dynamical systems of gradient flow for SFT and policy-gradient flow for RLVR, the authors derive the convergence behavior of each method.

The study proves that SFT, when trained exclusively on optimal paths, fails to learn how to backtrack because it never encounters negative examples or dead ends. In contrast, RLVR naturally generates and learns from its own unsuccessful rollouts, allowing it to internalize an efficient backtracking strategy. This leads to an exponential separation in inference-time compute: an RLVR-trained model can reach a target in logarithmic time relative to the search space, whereas an SFT-trained model requires exponential time. Finally, the authors demonstrate that the reasoning traces generated by an RLVR model can be distilled into a base model, effectively transferring the ability to backtrack efficiently.