TL;DR
This paper introduces a novel "prioritized replay" system for Reinforcement Learning (RL) post-training of large language models (LLMs). Instead of uniformly sampling training problems, it dynamically prioritizes problems based on their empirical success rate, focusing on those that offer the most learning signal and avoiding those that are too easy or too hard. This approach leads to more efficient training and improved performance.
What Problem Does This Paper Address?
Training large language models with RL, especially for complex reasoning tasks, is computationally expensive and can be inefficient. A key challenge is how to select the most informative training problems at each step to maximize learning speed and final performance. Traditional methods often rely on uniform sampling or manually designed curricula, which may not adapt well to the model's evolving capabilities. This paper tackles the problem of efficiently selecting training problems for RL post-training of LLMs by developing a dynamic, data-driven prioritization strategy.
Methods
The core of the proposed method is a problem-level prioritization framework. Unlike traditional Prioritized Experience Replay (PER) which operates on individual transitions and uses Temporal Difference (TD) errors, this approach focuses on entire problems. The priority of a problem is determined by a simple, model-driven score: $w = p(1-p)$, where $p$ is the empirical success rate of the model on that problem. This score is maximized when $p$ is close to 0.5, meaning problems that are neither consistently solved nor consistently failed are prioritized, as they provide the most informative learning signals for the GRPO (Generalized Relative Policy Gradient Objective) algorithm.
Key mechanisms include:
- Model-Driven Priority Score: Calculated directly from empirical success statistics, making it non-parametric and inexpensive.
- Heap-based Sampling: A binary max-heap efficiently manages and retrieves problems with the highest priority scores.
- Forgetting and Starvation Mitigation: Separate pools for "solved" and "unsolved" problems are maintained. Solved problems are periodically re-tested to guard against regression, and unsolved problems are re-introduced to the training pool to prevent them from being permanently ignored.
- Controlled Exploration: A small fraction of training batches are sampled uniformly at random to ensure exposure to less prioritized problems.
Datasets
The experiments were conducted using the GURU dataset [10], which contains math problems with varying difficulty levels. The authors used a subset of this dataset for training and evaluated their models on the MATH-500 benchmark [14] and the AIME 2024 competition problems [15].
Key Insights and Ideas
- Intermediate Difficulty is Key: The most valuable learning signals for RL post-training come from problems where the model is neither consistently succeeding nor failing. This is because these problems generate the most variance in outcomes, leading to more informative gradients.
- Automatic Curriculum Generation: The prioritization mechanism automatically creates an "emergent curriculum" that adapts to the model's evolving competence, eliminating the need for manual design or predefined difficulty tiers.
- Efficiency Beyond Transition-Level: Prioritizing at the problem level is more suitable for LLM reasoning tasks, which often involve long horizons, compared to traditional transition-level prioritization.
- Practicality Matters: The proposed method is lightweight, requires no auxiliary predictors or external labels, and integrates seamlessly into existing RL pipelines.
Key Results
- The prioritized sampling method consistently outperformed uniform sampling on both the MATH-500 and AIME 2024 benchmarks for pass@1 and pass@4 metrics within the experimental setup.
- The dynamics plots show a healthy training trajectory characterized by a steady flow of problems from the active heap into solved/unsolved pools as the model's competence becomes clearer.
- Despite a small exploration rate (12.5%), the method showed a tendency to focus on solvable problems, suggesting that the exploration strategy might need further tuning for broader coverage of unseen problems.
Limitations and Future Work
- Compute Budget: The empirical evaluation was limited by a constrained compute budget, meaning extensive hyperparameter sweeps or multi-seed studies were not performed. The reported results are a proof of concept rather than fully optimized.
- Exploration Strategy: While a 12.5% random exploration was used, the paper notes that a significant fraction of problems remained unseen. This suggests that the exploration strategy might need refinement to ensure better coverage of the entire dataset, especially in longer training runs.
- Late-Stage Behavior: Preliminary observations suggest that late-stage performance in prioritized sampling can fluctuate and may be sensitive to factors like learning rate, exploration schedule, and the composition of solved/unsolved pools. Further investigation into these aspects is warranted.
- Concise Reasoning Bias: The paper briefly discusses how to introduce a bias towards problems that encourage concise reasoning, suggesting future work could explore this further.
Summary updated