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

TL;DR. This paper gives a clean theoretical answer to a live empirical question: why does RL with verifiable rewards (RLVR) produce better reasoners than supervised fine-tuning (SFT) on expert solutions? The answer they prove, in a graph-pathfinding sandbox with a tabular softmax policy, is almost embarrassingly simple once you see it: SFT on golden (shortest-path) solutions produces literally zero gradient on the states you visit when you're stuck, so the model's ability to retreat from a dead end stays frozen at its pretrained value — and worse, the forward habits SFT does strengthen actively sabotage retreat. RLVR's own failed rollouts visit those stuck states, generating signal to backtrack efficiently. The result is a provable exponential gap in inference-time compute: \Theta(WK) steps for RLVR vs \Theta(WL^K) for SFT on a graph with W branches of depth K and L-way ambiguity per step. And distilling the RLVR model's traces back into a base model via plain supervised learning recovers the fast behavior — a theoretical account of why R1-style distillation works.

The debate this addresses

Empirically, people keep finding that SFT on high-quality reasoning traces underperforms RLVR: SFT memorizes, produces "pseudo-reasoning," generalizes worse out of distribution. But the explanations on offer have been mostly vibes ("RL explores," "SFT imitates") or statistical arguments about distribution shift. What's been missing is a mechanistic, training-dynamics account: what does the RLVR gradient actually teach the parameters that the SFT gradient does not?

The authors pick a specific capability to make this concrete: backtracking — recognizing you've committed to a bad branch and efficiently retreating to the last real decision point. Backtracking collapses search-space size, it's demonstrably central to long-CoT models, and it has a lovely property for analysis: golden solutions, by definition, never contain it. An expert's shortest path never walks into a dead end, so a dataset of expert paths contains exactly zero examples of getting unstuck.

The sandbox

The world is a multigraph (Figure 1 of the paper): a source s_0 feeds a fork f, which splits into W branches. Each branch is a chain of K "diamonds" — pairs of nodes joined by L parallel undirected edges — ending in a leaf t_i. The task: given a target leaf, output a valid path from the source. The L multiedges are the local ambiguity: at each step of a branch there are L indistinguishable ways forward, so a wanderer without direction diffuses.

The policy is deliberately minimal: a bigram over directed edge-states. Each state is "which edge am I on, and which way am I facing" — one-hot in \mathbb{R}^{2|E|} — and a single softmax layer \pi_\Theta(\cdot \mid x) = \mathrm{softmax}(\langle \Theta, x\rangle) maps it to a next edge-state. This is strictly more expressive than a trigram over nodes and, crucially, it's tabular: every state has its own logit row. Pretraining (Theorem 1: gradient flow on next-state prediction over the graph converges) leaves the model as a uniform random walker that knows the graph but has no strategy: from any edge, all valid continuations are equally likely.

One important design choice to keep in mind: generation does not condition on the prompted target. The policy is a pure Markov chain from the source. So "solving" the task means exploring branches efficiently, not navigating to a known goal — the fork choice stays uniform even after training, which is where the \Theta(W) factor comes from for everyone.

The aha: SFT's gradient is exactly zero where backtracking lives

For a softmax row and cross-entropy loss, the gradient has the familiar form

where d_{\mathcal{Q}}(s) is the probability the training distribution visits state s and p_{\mathcal{Q}}(a\mid s) is the empirical next-state distribution. If d_{\mathcal{Q}}(s)=0, the entire row is frozen for all time.

Golden shortest paths never contain a backward-facing edge-state — you never see the state "on edge u \leftrightarrow v, facing back toward the fork." So SFT (Theorem 2) drives every forward transition probability to 1 in finite time, and leaves every backward transition at its pretrained random-walk value. The model doesn't learn backtracking badly; the relevant parameters are never touched.

Now the second, nastier half of the mechanism. Suppose the SFT-trained model enters a wrong branch (probability \frac{W-1}{W} at the fork, since the policy is target-blind). It zips to the wrong leaf in \Theta(K) steps — forward transitions are deterministic now. To exit, it must chain K backward moves through the diamonds, each with pretrained success probability roughly \frac{1}{L+1}. And here's the trap: when it slips — accidentally re-crosses a diamond in the forward direction — it lands in a forward-facing state, where SFT has burned in probability 1 of continuing forward. One slip means a deterministic express ride all the way back to the dead-end leaf, and the retreat restarts from scratch.

The recursion for escape time (Appendix C) gives g_{K+1} = \Theta\!\big((\tfrac{(L+1)^2}{L})^K\big) = \Omega(L^K) per wrong branch, hence \Theta(WL^K) total. Even handing the SFT model a search agent that blocks revisiting any directed edge only improves it to \Theta(WKL) (Corollary 1) — an exponential rescue, but still a factor L behind.

Why RLVR learns it

RLVR runs on-policy rollouts from the source with reward r(x,y) = \mathbf{1}\{y \text{ hits target } x\} - \beta|y| — outcome verification plus a length penalty (analysis at \beta = 1; sign policy-gradient flow). The rollouts inevitably enter wrong branches, so the backward-facing states get visited: d_x(s) > 0, and the policy gradient \frac{\partial J}{\partial \Theta_{s,a}} = \mathbb{E}_x[d_x(s)\,\pi(a|s)\,A_x(s,a)] delivers advantage-weighted signal. The length penalty makes the advantage of a retreat move exactly the hitting-time saving, so backtracking gets reinforced. Theorem 3: all four transition types — forward-at-right-node (a_j), backward-at-right-node (b_j), forward-at-left-node (c_j), backward-at-left-node (d_j) — converge to 1. The converged policy sweeps each branch in \Theta(K), out in \Theta(K), and tries \Theta(W) branches: \Theta(WK) total.

The dynamics themselves (Section 5, Appendix B) are the most interesting technical content, because they're not monotone. At initialization, forward states always want to go more forward. But backward states at middle depths initially have a negative gradient — the paper calls them "confused." Facing backward mid-branch is ambiguous evidence: are you deliberately retreating from a checked leaf, or did you just U-turn off a promising forward march? Near the leaf, backward means you've checked the leaf (retreat is right); near the fork, retreating buys optionality; in the middle, the advantage of retreating can be negative. The proof splits into Phase I — showing this confused middle interval shrinks and all gradients become positive by a bounded time T_{\mathrm{meet}}, via a quantity \Gamma_j satisfying \frac{d^+}{dt}\log \Gamma_j \geq 2 while it's below 1 — and Phase II, a self-reinforcing regime where all probabilities march to 1. That "confusion resolves as forward states commit" story is a genuinely mechanistic picture of how coherent backtracking crystallizes during RL, and it matches their simulations: a brief early dip in b_j, d_j at middle depths.

Their simulations (W = K = 15, L = 5, sign gradient descent, lr 0.01) confirm the RLVR hitting time converges to exactly 4WK = 900. The appendix goes further than the theorem's idealizations: PPO with sampled rollouts and a small realistic length penalty (\beta = 3\times 10^{-4}) converges to the same policy; a single-layer transformer initialized at the bigram does too (slightly better, having more expressivity); and non-symmetric graphs with varying branch lengths converge to the analogous optimum 4\sum_i k_i.

Distillation, and what the result actually says

Theorem 5 closes the loop: take the converged RLVR model's traces — which do contain backward-facing states, because efficient exploration includes efficient retreats — and run plain SFT on them from the pretrained base. The frozen-row problem vanishes (d(s) > 0 everywhere on the traces), and the distilled model recovers \Theta(WK). This is a tidy theoretical account of why distilling reasoning traces from RL-trained models (the DeepSeek-R1 recipe) transfers so well: the traces carry the negative-experience data that golden solutions structurally lack.

That framing is the real takeaway, and it's sharper than "RL beats SFT." The separation is a statement about data coverage, not about the RL algorithm having magic gradients: SFT with backtracking demonstrations would work fine, and Appendix Figure 5 confirms this directly — supervising a random fraction p of backward states steadily collapses the SFT hitting time as p grows. RLVR's advantage is that on-policy rollouts manufacture that coverage automatically, and the length penalty converts it into a signal for efficient (not just eventual) retreat.

What to be skeptical about

Be clear-eyed about the sandbox. The policy is tabular — one logit row per edge-state — so "no data at state s" translates literally into "parameters at s frozen." Real LLMs share parameters massively; SFT on forward-only traces reshapes representations that also govern behavior in unvisited states, for better or worse. The freeze argument is exact here and only suggestive there. The exponential separation is also, at the mechanism level, close to tautological once you accept the setup: a golden-paths-only dataset provably contains zero backtracking states by construction. The paper's contribution is not that this is surprising but that it's quantified (the L^K blowup, driven by the slip-and-replay dynamic, is worse than mere ignorance) and that the RLVR side — nonmonotone two-phase dynamics converging in finite time from pure outcome reward — is actually proven, which is the hard part.

Other idealizations: sign gradient flow rather than SGD (they argue this avoids fringe non-convergence; the PPO experiment softens the concern), population gradients, a symmetric graph exploited heavily for the closed forms (relaxed only empirically in Appendix Fig. 8), fork logits fixed by fiat, and a length penalty that does real work — pure sparse outcome reward with no length term or horizon wouldn't produce the efficiency gradient. And note the policy never conditions on the target, so this models "learn a good universal search procedure," not goal-directed reasoning; both models pay the \Theta(W) branch-sampling cost.

If the picture transfers even loosely to LLMs, the practical implications are the ones practitioners have been converging on empirically: curate SFT data that includes recoveries and dead ends, not just polished solutions; expect RLVR's chief value to be generating exactly that data on-policy; and expect distillation from RL-trained teachers to keep beating distillation from golden answers.

What to read: Section 5 is the highest-value part — the policy-gradient decomposition into visit counts and hitting-time advantages, and especially the four-way intuition after Lemma 2 about why middle-depth backward states start out confused. Then Corollary 1 (the search-agent variant) and Appendix E for the robustness checks that keep the toy model honest.