Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training

2025/11/10 by Dake Bu, Wei Huang, Bu, Dake +10
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Machine Learning (cs.LG) #Multimodal Machine Learning Applications #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2511.07372

openalex publication_date 2025/11/10 · openalex created_date 2025/11/12 · openalex updated_date 2026/07/28

Abstract

Recent curriculum techniques in the post-training stage of LLMs have been empirically observed to outperform non-curriculum approaches in improving reasoning performance, yet a principled understanding of their effectiveness and limitations remains incomplete. To bridge this gap, we develop an abstract theoretical framework and identify sufficient conditions under which curriculum post-training yields exponential improvements in sample complexity. To substantiate this framework, we model the base model's Chain-of-Thought generation as a state-conditioned autoregressive reasoning tree, and formalize curriculum subtasks as either depth-increasing curricula that progressively extend reasoning horizons or hint-decreasing curricula that gradually remove partial hints. Our analysis shows that reinforcement learning finetuning with both curriculum strategies achieves high accuracy with polynomial sample complexity, whereas non-curriculum counterpart encounters an exponential complexity bottleneck. We further establish analogous guarantees for test-time scaling. Empirical simulations support our theoretical findings. Code is available at https://github.com/DakeBU/Curriculum-Post-training.

Citations

• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
• Evolving Language Models without Labels: Majority Drives Selection, Novelty Promotes Variation
• EvoCoT: Overcoming the Exploration Bottleneck in Reinforcement Learning
• Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descent
• RL for Reasoning by Adaptively Revealing Rationales
• Data Shifts Hurt CoT: A Theoretical Study
• SPEED-RL: Faster Training of Reasoning Models via Online Curriculum Learning
• Curriculum Reinforcement Learning from Easy to Hard Tasks Improves LLM Reasoning
• Learning Compositional Functions with Transformers from Easy-to-Hard Data
• UFT: Unifying Supervised and Reinforcement Fine-Tuning
• How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias
• Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?
• A Minimalist Approach to LLM Reasoning: from Rejection Sampling to Reinforce
• Efficient Reinforcement Finetuning via Adaptive Curriculum Learning
• Rethinking Reflection in Pre-Training
• Online Difficulty Filtering for Reasoning Oriented Reinforcement Learning
• Light-R1: Curriculum SFT, DPO and RL for Long COT from Scratch and Beyond
• Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration
• MM-Eureka: Exploring the Frontiers of Multimodal Reasoning with Rule-based Reinforcement Learning
• Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs
• Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thought
• Task Generalization With AutoRegressive Compositional Structure: Can Learning From D Tasks Generalize to D^T Tasks?
• Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions
• Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
• Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
• Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation
• Ehrenfeucht-Haussler Rank and Chain of Thought
• Understanding Factual Recall in Transformers via Associative Memories
• Transformers Provably Solve Parity Efficiently with Chain of Thought
• Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning
• From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency
• Progressive distillation induces an implicit curriculum
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers
• In-Context Learning with Representations: Contextual Generalization of Trained Transformers
• Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
• DART-Math: Difficulty-Aware Rejection Tuning for Mathematical Problem-Solving
• Tilting the Odds at the Lottery: the Interplay of Overparameterisation and Curricula in Neural Networks
• Stream of Search (SoS): Learning to Search in Language
• Denoising Task Difficulty-based Curriculum for Training Diffusion Models
• How Transformers Learn Causal Structure with Gradient Descent
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
• On Limitations of the Transformer Architecture
• Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscape
• White-Box Transformers via Sparse Rate Reduction: Compression Is All There Is?
• In-Context Convergence of Transformers
• One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attention
• Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs
• Trained Transformers Learn Linear Models In-Context
• On the Planning Abilities of Large Language Models : A Critical Investigation
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective
• Why think step by step? Reasoning emerges from the locality of experience
• A Theory of Emergent In-Context Learning as Implicit Structure Induction
• SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
• The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning
• Generalization on the Unseen, Logic Reasoning and Degree Curriculum
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• On the Power of Differentiable Learning versus PAC and SQ Learning
• Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
• Curriculum Learning: A Survey
• Curriculum Learning: A Survey
• Learning Parities with Neural Networks
• Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space
• Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
• The Expressive Power of Neural Networks: A View from the Width
• Automated Curriculum Learning for Neural Networks
• Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models
• The Expressive Power of Transformers with Chain of Thought

Related

• Curriculum Reinforcement Learning from Easy to Hard Tasks Improves LLM Reasoning
• Self-Evolving Curriculum for LLM Reasoning
• h1: Bootstrapping LLMs to Reason over Longer Horizons via Reinforcement Learning
• CurES: From Gradient Analysis to Efficient Curriculum Learning for Reasoning LLMs
• The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers?