Research map / Large language models / Reasoning and chain of thought

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

ICML 2026 · Large language models › Reasoning and chain of thought · approach: RL with verifiable rewards for reasoning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Theoretical analysis on a graph pathfinding model showing RLVR (outcome reward with length penalty, sign policy-gradient flow) learns efficient backtracking while SFT on golden shortest paths does not, yielding an exponential inference-time compute separation, and that RLVR traces distilled into a base model transfer this ability.

Problem

Why RL with verifiable rewards induces better reasoning and backtracking than SFT on gold solutions; SFT on shortest paths is shown not to learn backtracking, leading to exponential inference-time cost on graph pathfinding.

Approach

Models CoT as pathfinding on a multigraph (path-star-like with W branches of K diamonds of L multiedges) with a linear-softmax bigram world model, and proves dynamical results: gradient flow SFT on golden paths leaves backward transitions untouched (exponential Theta(W L^K) hitting time), while sign policy-gradient RLVR with length penalty converges to Theta(WK) backtracking behavior; distilling R

Key results

• RLVR model hitting time converges to Theta(WK); the experiment reports 4WK = 900 for W=K=15, L=5.
• SFT on golden shortest paths leaves backward transition probabilities b_j, d_j fixed at L/(L+1) and 1/(L+1), so backtracking is not learned.
• Theory gives an exponential separation: RLVR requires Theta(WK) expected inference time versus Theta(W L^K) for SFT.

Surprising findings

• Even with search agent that forbids revisiting directed edges, SFT still needs Theta(WKL) time versus Theta(WK) for RLVR, so the separation shrinks to a factor of L.

Limitations

• Analysis is on a toy bigram/linear-softmax model with exact pretraining assumption.
• Uses gradient flow and signed policy gradient rather than practical optimizers.
• Experiments are limited to synthetic graph pathfinding; no LLM experiments reported.

Experimental setup

Datasets: synthetic multigraph pathfinding instances

Benchmarks: synthetic multigraph pathfinding (W=15, K=15, L=5)

Metrics: expected hitting time transition probabilities a_j,b_j,c_j,d_j

Baselines: SFT on golden shortest paths

Builds on: path-star graph policy gradient world model bigram pretraining analysis

Closest papers by meaning

• RL Squeezes, SFT Expands: A Comparative Study of Reasoning LLMs (ICLR 2026 · similarity 0.92)
• Reinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMs (ICLR 2026 · similarity 0.92)
• Generalization of RLVR Using Causal Reasoning as a Testbed (ICLR 2026 · similarity 0.91)
• Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model? (NeurIPS 2025 · similarity 0.91)
• The Reasoning Boundary Paradox: How Reinforcement Learning Constrains Language Models (NeurIPS 2026 · similarity 0.91)
• Outcome Rewards Do Not Guarantee Verifiable or Causally Important Reasoning (ICML 2026 · similarity 0.91)