TL;DR
Most reinforcement learning research evaluates algorithms by the number of training updates, but this ignores the massive "compute tax" required to generate intermediate feedback. This paper introduces a matched-compute protocol and reveals that popular "dense rewards" (which score intermediate steps) actually underperform simple outcome-only training by up to 14.3 points when accounting for token costs, while smart prompt selection provides a genuine, compute-efficient boost.
What Problem Does This Paper Address?
In Reinforcement Learning with Verifiable Rewards (RLVR), models learn to reason by solving problems (like math) where the final answer can be automatically checked. A popular algorithm, Group-Relative Policy Optimization (GRPO), typically rewards every token in a correct solution equally.
Researchers have proposed "dense rewards" to give more specific credit to good intermediate steps. One common way to estimate a step's value is the Monte-Carlo (MC) reward: from a partial solution, you sample multiple "continuations" to see how often they lead to a correct final answer.
The catch? These continuations cost a lot of tokens. If you only compare algorithms by the number of training updates, dense rewards look superior. However, this ignores the "hidden cost" of the tokens generated just to calculate the reward. The authors argue that we should instead validate interventions at matched compute—giving every method the same budget of total generated tokens and GPU hours.
Methods
The authors reimplemented GRPO and conducted a massive study (1,668 runs across six models) using two primary case studies:
- Dense Rewards: They tested Monte-Carlo rewards (sampling $k$ continuations at various "cuts" in a solution) and learned-critic rewards (using a model to predict the value of a step without extra sampling).
- Prompt Selection: Instead of changing how steps are rewarded, they changed which problems the model trains on. They used a "critic" to score candidate prompts and prioritized those where the model's predicted success was near 50%—the "Goldilocks zone" where the model has the most to learn.
Crucially, they used a matched-compute protocol. If a dense reward method uses 90% of its tokens just for "thinking" (continuations), it is allowed far fewer training updates than a baseline that spends 100% of its tokens on actual training rollouts.
Datasets
The study focused on mathematical reasoning using:
- MATH: A dataset of challenging competition-level math problems.
- GSM8K: Used to test how well the training gains transfer to different types of math problems.
- Models: They tested six small-to-medium models, including the Qwen2.5, Qwen3, and Llama-3.2 families (ranging from 0.6B to 4B parameters).
Key Insights and Ideas
- The 91% Tax: For the Monte-Carlo reward ($k=4$), the continuations alone accounted for 91% of all generated tokens. This means that for the same "token budget," standard outcome-only GRPO could perform 584 updates while the MC method could only manage 50.
- Gradient Tests are Deceptive: A common "cheap" way to vet a reward is a gradient test (checking if the reward's update points in the right direction). MC rewards pass these tests easily, but the tests fail to predict that the high token cost will eventually make the method lose to a simpler baseline that just trains more often.
- The "Goldilocks" Rule for Prompts: Prompt selection works, but only under a specific condition: the candidate prompts must be predicted to fail more often than not. If the model is already too good at the prompts, filtering for the "hardest" ones doesn't help.
- Baselines are often Under-tuned: The authors found that simply doubling the learning rate of the standard outcome-only baseline closed the gap with the "fancy" prompt selection method to within 0.5 points.
Key Results
- Dense Reward Reversal: On Qwen2.5-1.5B, the Monte-Carlo reward looked better "per update," but ended 14.3 percentage points lower than standard GRPO at equal tokens and 7.8 points lower at equal training time.
- Prompt Selection Wins: Choosing prompts near 1/2 success improved accuracy by 1.7 points on Qwen3-0.6B and 0.8 points on Qwen2.5-1.5B at matched compute.
- Efficiency Gains: Prompt selection reached the same accuracy as the baseline while using ~22% fewer tokens and ~15% less training time.
Limitations and Future Work
- Scale: The study used relatively small models (up to 4B parameters). It remains to be seen if these trade-offs shift for 70B+ parameter models where the ratio of generation cost to update cost might differ.
- Task Variety: The focus was strictly on math. Other reasoning tasks (like coding or logic) might benefit differently from dense rewards.
- Reward Sources: The study focused on automated rewards (MC and Critics). It did not evaluate human-labeled process rewards, which have a different cost structure (expensive human time vs. cheap inference tokens).
- Future Direction: The authors suggest that instead of discarding MC continuations, future work should focus on "continuation reuse"—training on the very tokens generated to score the reward.
Summary updated