TL;DR
Reinforcement Learning with Verifiable Reward (RLVR) is highly effective for training reasoning LLMs, but popular algorithms like GRPO suffer from a mathematical bias that underweights difficult problems. This paper introduces Difficulty Adaptive Rollout Sampling (DARS) to dynamically allocate more exploration to harder tasks, combining it with large-batch training to achieve simultaneous breakthroughs in both single-shot accuracy (Pass@1) and upper-bound capability (Pass@K).
What Problem Does This Paper Address?
When training large language models (LLMs) to reason using reinforcement learning, frameworks like GRPO (Group Relative Policy Optimization) rely on verifiable rewards—such as checking if a math answer matches the ground truth or if code passes unit tests.
However, the authors uncover a fundamental flaw in GRPO: its cumulative advantage bias. Because GRPO normalizes rewards within a local group of sampled answers, it mathematically funnels optimization weight toward medium-difficulty problems. For highly difficult problems where the model rarely finds a correct path, the rare successful gradients are drowned out, leading to "depth neglect." Naively increasing the number of sampled paths across the board doesn't fix this; it can actually destabilize training and hurt the model's performance.
The paper addresses how to scale LLM training along two critical, orthogonal dimensions: Depth (tackling harder problems through adaptive exploration) and Breadth (maximizing unique training instances per batch).
Methods
To solve the depth neglect problem, the authors propose Difficulty Adaptive Rollout Sampling (DARS). Instead of using a fixed number of rollouts for every problem, DARS operates in two distinct phases:
- Pre-Rollout Difficulty Estimation: The model generates a small, lightweight set of initial trajectories ($N_{pre}$) to estimate the empirical accuracy of a question. If accuracy is low, the problem is flagged as high-difficulty.
- Multi-Stage Rollout Re-Balancing: DARS dynamically allocates additional rollouts ($\Delta n_j$) to these harder problems to explicitly amplify their sparse reward signals.
The authors design two re-balancing schedules:
- Equal-Treatment (ET): Raises the cumulative advantage of all hard problems to match a medium-difficulty baseline (implicitly optimizing a Log-Odds objective).
- Hardness-Weighted (HW): Scales the compute budget linearly with hardness, allocating the most rollouts to the lowest-accuracy problems (implicitly optimizing a Maximum Likelihood objective).
Because dynamic rollout allocation creates uneven ("ragged") batch sizes that break standard PPO mini-batch chunking, the authors replace mini-batches with Full-Batch Updates over multiple PPO epochs. This architectural shift allows them to scale up the training Breadth (batch sizes up to 3072), which acts as an implicit entropy regularizer and reduces gradient noise. The combined approach is called DARS-Breadth.
Datasets
- Training Data: OpenR1-45K (a verified, high-quality subset of OpenR1-Math-220k). For Llama models, the training split of the standard MATH dataset was used.
- Evaluation Benchmarks: Five mathematical reasoning datasets: MATH-500, OlympiadBench, MinervaMath, AIME24, and AMC23.
- Generalization Benchmarks: To ensure the method wasn't over-specialized to math, they evaluated models on GPQA-Diamond (science) and HumanEval (coding).
Key Insights and Ideas
- The GRPO Bottleneck: Group-relative advantage estimation inherently penalizes hard problems. If a model only gets a problem right 5% of the time, the cumulative gradient push is too weak to shift the policy effectively.
- Breadth Sustains Entropy: Scaling up the batch size (breadth) keeps token-level entropy high during training. This prevents the model from converging prematurely and directly boosts single-shot (Pass@1) performance.
- Orthogonal Levers: Depth (DARS) primarily drives Pass@K performance by expanding the model's capability ceiling, while Breadth drives Pass@1. They are complementary, not competing, resources.
Key Results
The unified DARS-Breadth approach consistently outperformed baselines across all benchmarks and model scales (Qwen2.5-Math-1.5B/7B and Llama-3.1-8B).
- Performance Boosts: For Qwen2.5-Math-7B, DARS-HW-Breadth improved the average Pass@1 from 55.3% to 58.4% and Pass@128 from 81.4% to 83.4%. On the brutal AIME24 benchmark, it lifted Pass@1 from 26.8% to 33.0%.
- Llama-3.1 Breakthroughs: The gains were particularly massive for Llama-3.1-8B, where DARS-Breadth boosted Pass@128 from 56.5% to 68.7%.
- Compute Efficiency: DARS achieved these gains while reducing the average number of rollouts per prompt by 25% to 60% compared to naive uniform scaling, significantly lowering wall-clock training time.
- Eliciting Deeper Thought: Tracking the models' internal dynamics showed that DARS-trained models naturally learned to generate longer, more thorough reasoning traces to solve complex tasks.
Limitations and Future Work
- Over-training Degradation: The authors observed that Pass@K performance often peaks early and then declines if RLVR training is prolonged, suggesting that over-training can harm the model's broader solution space.
- Annealing Schedules: While a fixed rollout cap ($N_{max}$) was primarily used, preliminary results showed that annealing $N_{max}$ (starting high to explore hard problems, then shrinking it to refine single-shot paths) improved Pass@1 but slightly degraded Pass@128. Developing more principled, dynamic curriculum schedules for these hyperparameters remains an open area for future research.
Summary updated