Reasoning over Longer Horizons via RL

Analysis

Why This Paper Matters

Large language models (LLMs) have shown remarkable proficiency in short-horizon reasoning tasks, but their performance degrades significantly as the reasoning horizon lengthens. This limitation is critical for real-world applications that require multi-step planning, complex problem-solving, or long-context understanding. Existing solutions, such as inference-time scaffolding or costly step-level supervision, do not scale easily and often require extensive human annotation or computational overhead. This paper addresses a fundamental bottleneck in AI reasoning: how to bootstrap long-horizon capabilities from abundant short-horizon data without additional supervision.

The significance lies in its practical and theoretical contributions. Practically, it offers a scalable method that leverages synthetic composition and curriculum reinforcement learning (RL) to train models on increasingly complex reasoning chains using only outcome rewards. Theoretically, it proves that curriculum RL with outcome rewards achieves exponential improvement in sample complexity compared to full-horizon training, providing a training signal comparable to dense supervision. This work opens a path toward more efficient and generalizable long-horizon reasoning, which is crucial for advancing AI systems in domains like mathematics, science, and autonomous planning.

Technical Contributions

• Synthetic Composition of Problems: The method composes simple, short-horizon problems (e.g., from GSM8K) into multi-step dependency chains of arbitrary length, creating a rich training curriculum without requiring new data collection.
• Curriculum RL with Outcome Rewards: Training uses only outcome-based rewards (correct/incorrect final answer) under a curriculum that automatically increases in complexity, avoiding the need for step-level supervision.
• Exponential Sample Complexity Improvement: The authors provide a theoretical proof that curriculum RL with outcome rewards achieves exponential improvement in sample complexity over full-horizon training, matching the efficiency of dense supervision.
• Generalization Across Domains: The method transfers significantly to out-of-distribution ReasoningGym domains and long-context benchmarks, indicating broader generalization beyond the training distribution.
• Scalability: The approach allows RL training to be scaled much further without saturating, as the curriculum prevents the model from plateauing on simple tasks.

Results

• Accuracy Gains: Curriculum training on composed 6th-grade level math problems (GSM8K) boosts accuracy on longer, competition-level benchmarks (GSM-Symbolic, MATH-500, AIME) by up to 2.06x.
• Transfer Performance: The method shows significant transfer to diverse out-of-distribution ReasoningGym domains and long-context benchmarks, demonstrating broader generalization.
• High pass@k: Long-horizon improvements are significantly higher than baselines even at high pass@k, showing that models can learn new reasoning paths under RL.
• Baseline Comparison: The method outperforms existing approaches that rely on inference-time scaffolding or step-level supervision, particularly in terms of scalability and generalization.

Significance

This work has broad implications for the AI field. By demonstrating that long-horizon reasoning can be efficiently bootstrapped from short-horizon data using curriculum RL, it reduces the dependency on expensive human annotations and computational resources. The theoretical result on exponential sample complexity improvement provides a principled foundation for future research in RL-based reasoning. Practically, the method can be applied to various domains requiring multi-step reasoning, such as mathematical problem-solving, code generation, and scientific discovery. It also suggests a path toward more autonomous and generalizable AI systems that can handle complex, long-horizon tasks without extensive manual engineering.