mlsanityData to 7 Oct 2026

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

arXiv 2511.07372 ↗First posted 10 Nov 2025cs.LGcited by 4

On the map: LLM reasoning → Reinforcement learning for reasoning

Abstract (arXiv)

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 70 of its 82 references that are in the map. First posted on arXiv 10 Nov 2025.

Builds on

70 of 82 references.

Closest ancestors · 10

Same direction, newest first

  1. 2025EvoCoT: Overcoming the Exploration Bottleneck in Reinforcement Learning11 Aug
  2. 2025SPEED-RL: Faster Training of Reasoning Models via Online Curriculum Learning10 Jun
  3. 2025Curriculum Reinforcement Learning from Easy to Hard Tasks Improves LLM Reasoning7 Jun
  4. 2025UFT: Unifying Supervised and Reinforcement Fine-Tuning22 May
  5. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?18 Apr
  6. 2025A Minimalist Approach to LLM Reasoning: from Rejection Sampling to Reinforce15 Apr
  7. 2025Efficient Reinforcement Finetuning via Adaptive Curriculum Learning7 Apr
  8. 2025Online Difficulty Filtering for Reasoning Oriented Reinforcement Learning4 Apr
  9. 2025Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs3 Mar
  10. 2024Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning10 Oct

Other references · 60

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  2. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
  3. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  4. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  5. 2023On the Planning Abilities of Large Language Models : A Critical Investigationcited by 308
  6. 2025MM-Eureka: Exploring the Frontiers of Multimodal Reasoning with Rule-based Reinforcement Learningcited by 294
  7. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  8. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  9. 2021Curriculum Learning: A Surveycited by 257
  10. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  11. 2017Automated Curriculum Learning for Neural Networkscited by 251
  12. 2025Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusionscited by 208
38 more
  1. 2025Light-R1: Curriculum SFT, DPO and RL for Long COT from Scratch and Beyondcited by 175
  2. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 168
  3. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 160
  4. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  5. 2024Stream of Search (SoS): Learning to Search in Languagecited by 141
  6. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 114
  7. 2018Curriculum Learning by Transfer Learning: Theory and Experiments with Deep Networkscited by 113
  8. 2023In-Context Convergence of Transformerscited by 112
  9. 2023Why think step by step? Reasoning emerges from the locality of experiencecited by 103
  10. 2024DART-Math: Difficulty-Aware Rejection Tuning for Mathematical Problem-Solvingcited by 92
  11. 2023A Theory of Emergent In-Context Learning as Implicit Structure Inductioncited by 86
  12. 2020Learning Parities with Neural Networkscited by 77
  13. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  14. 2024On Limitations of the Transformer Architecturecited by 63
  15. 2024Transformers Provably Solve Parity Efficiently with Chain of Thoughtcited by 49
  16. 2019Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov spacecited by 46
  17. 2024Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformerscited by 46
  18. 2024Understanding Factual Recall in Transformers via Associative Memoriescited by 45
  19. 2025Evolving Language Models without Labels: Majority Drives Selection, Novelty Promotes Variationcited by 44
  20. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 43
  21. 2025Rethinking Reflection in Pre-Trainingcited by 43
  22. 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
  23. 2024In-Context Learning with Representations: Contextual Generalization of Trained Transformerscited by 36
  24. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 34
  25. 2025Learning Compositional Functions with Transformers from Easy-to-Hard Datacited by 34
  26. 2018Theory of Curriculum Learning, with Convex Loss Functionscited by 33
  27. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 32
  28. 2025Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thoughtcited by 32
  29. 2025Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challengescited by 30
  30. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  31. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  32. 2021An Analytical Theory of Curriculum Learning in Teacher-Student Networkscited by 27
  33. 2021On the Power of Differentiable Learning versus PAC and SQ Learningcited by 27
  34. 2024Denoising Task Difficulty-based Curriculum for Training Diffusion Modelscited by 26
  35. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  36. 2023Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputscited by 22
  37. 2023White-Box Transformers via Sparse Rate Reduction: Compression Is All There Is?cited by 22
  38. 2023A Mathematical Model for Curriculum Learning for Paritiescited by 19

50 most cited of 60 All 60 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 5
  2. 2026DPRM: A Plug-in Doob h transform-induced Token-Ordering Module for Discrete Diffusion Modelscited by 1
  3. 2026From Blind Spots to Gains: Diagnostic-Driven Iterative Training for Large Multimodal Modelscited by 0
  4. 2026Agentic Transformers Provably Learn to Search via Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Reasoning Curriculum: Bootstrapping Broad LLM Reasoning from Math
  2. 2025Self-Evolving Curriculum for LLM Reasoning
  3. 2026Rethinking Easy-to-Hard: Limits of Curriculum Learning in Post-Training for Deductive Reasoning
  4. 2026TACLer: Tailored Curriculum Reinforcement Learning for Efficient Reasoning
  5. 2026Curriculum Reinforcement Learning Can Incentivize Reasoning Capacity in LLMs Beyond the Base Model
  6. 2025CurES: From Gradient Analysis to Efficient Curriculum Learning for Reasoning LLMs
  7. 2025DUMP: Automated Distribution-Level Curriculum Learning for RL-based LLM Post-training
  8. 2026From Reasoning Chains to Verifiable Subproblems: Curriculum Reinforcement Learning Enables Credit Assignment for LLM Reasoning