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

Stanley Wei, Juno Kim
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:133778-133815, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-wei26o, title = {Provable Benefits of {RLVR} over {SFT} for Reasoning Models: Learning to Backtrack Efficiently}, author = {Wei, Stanley and Kim, Juno}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {133778--133815}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/wei26o/wei26o.pdf}, url = {https://proceedings.mlr.press/v306/wei26o.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently %A Stanley Wei %A Juno Kim %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-wei26o %I PMLR %P 133778--133815 %U https://proceedings.mlr.press/v306/wei26o.html %V 306 %X 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.
APA
Wei, S. & Kim, J.. (2026). Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:133778-133815 Available from https://proceedings.mlr.press/v306/wei26o.html.

Related Material