Provable Sample Efficiency of Curriculum Post-Training for Transformer Reasoning

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.

Modern language models often improve their reasoning after extra training, but this training can be expensive because correct long reasoning traces are rare. Practitioners often use curricula—starting from easier tasks or giving partial hints—yet it has been unclear when such strategies should actually help. We study this question theoretically for post-training with sparse final-answer feedback. Our main message is that curriculum helps when it breaks a hard reasoning task into intermediate stages that are genuinely easier for the base model. Under this condition, we prove that curriculum post-training can reduce the required samples from exponential to polynomial scale, both for reinforcement-learning fine-tuning and for test-time search. We formalize this through a transformer tree-reasoning model that captures depth-increasing curricula, where reasoning length grows gradually, and hint-decreasing curricula, where expert hints are slowly removed. Beyond synthetic parity experiments, we added larger-scale experiments on Countdown, MATH, and Blocksworld using Qwen2.5-1.5B, showing that curriculum fine-tuning generally improves over direct GRPO fine-tuning. To make the idea usable, we also release a plug-and-play module that helps users add depth-increasing or hint-decreasing schedules to their own transformer training pipelines. This work provides both a theoretical explanation and practical tools for designing more sample-efficient post-training methods for reasoning models.