How Much Backtracking is Enough? Exploring the Interplay of SFT and RL in Enhancing LLM Reasoning

Recent advancements in large language models (LLMs) suggest that reinforcement learning (RL) effectively internalizes search strategies, yielding significant improvements on challenging reasoning tasks through extended chains of thought. While backtracking is widely viewed as the core mechanism enabling this improvement, its precise dynamics, and how SFT and RL interact to optimize for it, remain poorly understood. In this work, we argue that backtracking—the ability to explicitly revisit and revise earlier reasoning steps—is a key operator that enables the transition from linear generation to non-linear tree search for LLMs, unlocking strong performance on combinatorially complex tasks. We motivate this claim by first studying the interplay between supervised fine-tuning (SFT) warm-up and RL across eight reasoning tasks: Countdown, Sudoku, Arc 1D, Geometry, Color Cube Rotation, List Functions, Zebra Puzzles, and Self Reference. We find that a regular SFT warm-up using self-sampled CoT sequences provides a modest boost to subsequent RL compared to training without any SFT warm-up; however, such gains saturate as tasks become more difficult. Motivated by this failure mode, we introduce a backtracking-centric training recipe. By synthetically varying the number of explicit backtracking steps in the SFT warm-up, we show that (i) longer CoTs containing backtracks stabilize and amplify RL, and (ii) the optimal backtrack depth scales with task difficulty—zero for Arc 1D, one for Countdown, and five or more for Sudoku—yielding up to a 28.9\% absolute accuracy boost. Our findings establish that principled backtracking is essential for improving the model's reasoning capability.