mlsanityData to 14 Oct 2026

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

arXiv 2606.22938 ↗First posted 22 Jun 2026cs.LG cs.AIcited by 2

On the map: LLM reasoning → Reinforcement learning for reasoning

Abstract (arXiv)

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 an exponential separation in inference-time compute between the two methods, and demonstrates that RLVR leads 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.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 38 of its 47 references that are in the map. First posted on arXiv 22 Jun 2026.

Builds on

38 of 47 references.

Closest ancestors · 9

Same direction, newest first

  1. 2025How Does RL Post-training Induce Skill Composition? A Case Study on Countdown1 Dec
  2. 2025Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectories10 Nov
  3. 2025Reinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMs17 Jun
  4. 2025The Surprising Effectiveness of Negative Reinforcement in LLM Reasoning2 Jun
  5. 2025How Much Backtracking is Enough? Exploring the Interplay of SFT and RL in Enhancing LLM Reasoning30 May
  6. 2025Reinforcement Learning for Reasoning in Large Language Models with One Training Example29 Apr
  7. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning22 Jan
  8. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMs22 Jan
  9. 2023Let's Verify Step by Step31 May

Other references · 29

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  3. 2017Deep reinforcement learning from human preferencescited by 3,912
  4. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  5. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,986
  6. 2025s1: Simple test-time scalingcited by 1,341
  7. 2024OpenAI o1 System Cardcited by 1,244
  8. 2025DeepSeek-V3.2: Pushing the Frontier of Open Large Language Modelscited by 815
  9. 2025SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-trainingcited by 672
  10. 2025Towards Large Reasoning Models: A Survey of Reinforced Reasoning with Large Language Modelscited by 293
  11. 2023Large Language Model Guided Tree-of-Thoughtcited by 221
  12. 2025SFT or RL? An Early Investigation into Training R1-Like Reasoning Large Vision-Language Modelscited by 212
17 more
  1. 2025RL's Razor: Why Online Reinforcement Learning Forgets Lesscited by 176
  2. 2024The pitfalls of next-token predictioncited by 160
  3. 2022Distilling Reasoning Capabilities into Smaller Language Modelscited by 158
  4. 2025LLM Post-Training: A Deep Dive into Reasoning Large Language Modelscited by 135
  5. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 118
  6. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 67
  7. 2025Step Back to Leap Forward: Self-Backtracking for Boosting Reasoning of Language Modelscited by 27
  8. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  9. 2025To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoningcited by 24
  10. 2024Markov Chain of Thought for Efficient Mathematical Reasoningcited by 19
  11. 2025Taming Imperfect Process Verifiers: A Sampling Perspective on Backtrackingcited by 14
  12. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 13
  13. 2024Towards an Understanding of Stepwise Inference in Transformers: A Synthetic Graph Navigation Modelcited by 9
  14. 2025From Reasoning to Super-Intelligence: A Search-Theoretic Perspectivecited by 9
  15. 2026Escaping the Cognitive Well: Efficient Competition Math with Off-the-Shelf Modelscited by 9
  16. 2025Spectral Journey: How Transformers Predict the Shortest Pathcited by 8
  17. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026What Pretraining and Midtraining Make Learnable from Rewards?cited by 0
  2. 2026Learning without Overwriting: A Theory of Self-Distillation and Supervised Fine-Tuning in Continual Reasoningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025RL Squeezes, SFT Expands: A Comparative Study of Reasoning LLMs
  2. 2025Reassessing the Role of Supervised Fine-Tuning: An Empirical Study in VLM Reasoning
  3. 2025Evaluating Parameter Efficient Methods for RLVR
  4. 2025Beyond Two-Stage Training: Cooperative SFT and RL for LLM Reasoning
  5. 2025The Reasoning Boundary Paradox: How Reinforcement Learning Constrains Language Models
  6. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?
  7. 2025Quagmires in SFT-RL Post-Training: When High SFT Scores Mislead and What to Use Instead
  8. 2026SAGE: Shaping Anchors for Guided Exploration in RLVR of LLMs