A Task-centric Theory for Iterative Self-Improvement with Easy-to-Hard Curricula

Iterative self-improvement fine-tunes an autoregressive large language model (LLM) on reward-verified outputs generated by the LLM itself. In contrast to the empirical success of self-improvement, the theoretical foundation of this generative, iterative procedure in a practical, finite-sample setting remains limited. We make progress toward this goal by modeling each round of self-improvement as maximum-likelihood fine-tuning on a reward-filtered distribution and deriving finite-sample guarantees for the expected reward. Our analysis reveals an explicit feedback loop where better models accept more data per iteration, supporting sustained self-improvement while explaining eventual saturation of such improvement. Adopting a task-centric view by considering reasoning tasks with multiple difficulty levels, we further prove quantifiable conditions on model initialization, task difficulty, and sample budget where easy-to-hard curricula provably achieve better guarantees than training on fixed mixtures of tasks. Our analyses are validated through Monte-Carlo simulations and experiments spanning a synthetic graph-based reasoning task and multiple standard mathematical reasoning benchmarks.

Modern large language models demonstrate appealing yet surprising self-improvement capability where the models learn from their own outputs, filtered by some external verifiers. We study the fundamental problems of when self-improvement is possible and when such self-improvement loops may stall and even hurt performance from a mathematical perspective. Our analysis highlights a feedback loop: a better model produces more correct attempts, which gives the model more useful practice in the following self-improvement iterations. The analysis also casts light on why the self-improvement gain tends to level off. We further investigate when it helps to organize practice from easier problems to harder ones (known as easy-to-hard curricula) instead of mixing all problems together. We show that easy-to-hard curricula work best when the problem difficulty increases at a moderate pace. Experiments on mathematical reasoning tasks support these predictions. Overall, our work can help guide how to schedule tasks and sample budgets across rounds before running iterative self-improvement, so the model can make better use of its generated data.