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

Recent advances in large language models (LLMs) have demonstrated that reinforcement fine-tuning of pretrained base models can lead to significant gains in reasoning performance at inference time. In this work, we theoretically analyze why reinforcement fine-tuning induces better reasoning ability than purely supervised fine-tuning (SFT) methods. We model chain-of-thought (CoT) reasoning as a pathfinding problem on graphs and compare the popular method of reinforcement learning with verifiable rewards (RLVR) against traditional SFT. We prove that SFT, when trained on golden shortest paths without negative examples, fails to learn how to efficiently backtrack. In contrast, an RLVR-trained model can learn how to efficiently backtrack from dead ends using only outcome reward. This leads to a provable inference-time compute separation between the two methods, and demonstrates that RLVR allows the model to learn the location of difficult decisions in a reasoning chain, ultimately allowing for better allocation of inference-time compute. Finally, we show that the reasoning traces of an RLVR model can be distilled to train a base model to backtrack efficiently as well.

LLMs are often post-trained to obtain significant gains in downstream tasks, such as reasoning. In our work, we model reasoning as a path-finding task in order to provide a toy setting that yields tractable mathematical analysis. Specifically, we analyze RLVR (reinforcement learning with verifiable rewards) vs. SFT (supervised fine-tuning) for post-training. Our work shows that RLVR provably learns the necessary backtracking ability that is not natively present in the base model. In our setting, this corresponds to an exponential speedup at inference time compared to a LLM that is trained with SFT on perfect examples.