Xiaoyin Chen

Reinforcement learning (RL) has proven effective for fine-tuning large language models (LLMs), significantly enhancing their reasoning abilities in domains such as mathematics and code generation. A crucial factor influencing RL fine-tuning success is the training curriculum: the order in which training problems are presented. While random curricula serve as common baselines, they remain suboptimal; manually designed curricula often rely heavily on heuristics, and online filtering methods can be computationally prohibitive. To address these limitations, we propose \textit{Self-Evolving Curriculum (SEC)}, an automatic curriculum learning method that learns a curriculum policy concurrently with the RL fine-tuning process. Our approach formulates curriculum selection as a non-stationary Multi-Armed Bandit problem, treating each problem category (e.g., difficulty level or problem type) as an individual arm. We leverage the absolute advantage from policy gradient methods as a proxy measure for immediate learning gain. At each training step, the curriculum policy selects categories to maximize this reward signal and is updated using the TD(0) method. Across three distinct reasoning domains: planning, inductive reasoning, and mathematics, our experiments demonstrate that SEC significantly improves models' reasoning capabilities, enabling better generalization to harder, out-of-distribution test problems. Additionally, our approach achieves better skill balance when fine-tuning simultaneously on multiple reasoning domains. These findings highlight SEC as a promising strategy for RL fine-tuning of LLMs.

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, Advanced 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. Our findings establish that principled backtracking is essential for improving the model's reasoning capability.