Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training
This provides a theoretical foundation for curriculum learning in LLMs, addressing a gap in understanding for researchers and practitioners in AI, though it is incremental as it builds on existing curriculum and reasoning methods.
The paper tackles the lack of principled understanding of why curriculum techniques improve reasoning in LLMs during post-training, showing theoretically that curriculum post-training avoids exponential complexity bottlenecks and achieves polynomial sample complexity for high accuracy, with analogous benefits for test-time scaling.
Recent curriculum techniques in the post-training stage of LLMs have been widely observed to outperform non-curriculum approaches in enhancing reasoning performance, yet a principled understanding of why and to what extent they work remains elusive. To address this gap, we develop a theoretical framework grounded in the intuition that progressively learning through manageable steps is more efficient than directly tackling a hard reasoning task, provided each stage stays within the model's effective competence. Under mild complexity conditions linking consecutive curriculum stages, we show that curriculum post-training avoids the exponential complexity bottleneck. To substantiate this result, drawing insights from the Chain-of-Thoughts (CoTs) solving mathematical problems such as Countdown and parity, we model CoT generation as a states-conditioned autoregressive reasoning tree, define a uniform-branching base model to capture pretrained behavior, and formalize curriculum stages as either depth-increasing (longer reasoning chains) or hint-decreasing (shorter prefixes) subtasks. Our analysis shows that, under outcome-only reward signals, reinforcement learning finetuning achieves high accuracy with polynomial sample complexity, whereas direct learning suffers from an exponential bottleneck. We further establish analogous guarantees for test-time scaling, where curriculum-aware querying reduces both reward oracle calls and sampling cost from exponential to polynomial order.