🤖 AI

Learning as Reasoning Unfolds: Progressive Rollout Allocation for Efficient Reinforcement Learning

The paper proposes VIGOR, a variance-guided online rollout allocation method that dynamically distributes a fixed generation budget to examples with the highest reward variance, thereby significantly reducing computational costs and improving stability while achieving superior performance in mathematical reasoning and coding tasks compared to standard GRPO.

Original authors: Heyang Jiang, Henry Liu, Baharan Mirzasoleiman

Published 2026-07-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Heyang Jiang, Henry Liu, Baharan Mirzasoleiman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart, but slightly scatterbrained, robot how to solve complex puzzles like math problems or write computer code. You can't just sit there and explain every step; instead, you let the robot try, and when it gets an answer right, you give it a high-five (a "reward"). When it gets it wrong, you give it a gentle "try again." This process is called Reinforcement Learning. The robot keeps trying different ways to solve the problem, and over time, it learns which paths lead to high-fives and which lead to dead ends.

However, there's a catch. To learn effectively, the robot needs to try a lot of different paths. If it only tries one or two, it might get lucky and think a bad path is actually good. But if it tries thousands of paths, it becomes a huge waste of time and electricity, especially because most of those paths are boring or useless. It's like asking a student to write 100 essays to learn how to write, when 90 of them are just scribbles that don't teach them anything new. The big question for scientists is: How do we make the robot try the right number of paths without wasting energy on the boring ones?

This is where a new method called VIGOR comes in. Think of the robot's learning process like a game of "Hot and Cold." In the old way of doing things (called GRPO), the robot would blindly try the same number of guesses for every single puzzle, regardless of whether the puzzle was easy or hard. It was like a teacher giving every student the same amount of homework, even if some students already knew the answer and others were completely lost.

The researchers behind VIGOR realized that the most useful information comes from the moments when the robot is unsure. If a robot tries a math problem and gets a mix of right and wrong answers, that "variance" (or disagreement) is a signal that the robot is learning something important. But if it gets the same wrong answer every time, or the same right answer every time, it's just wasting time.

VIGOR changes the game by acting like a smart coach who watches the robot's first few attempts. Instead of giving every puzzle a fixed number of tries, VIGOR starts by letting the robot take just a couple of guesses at everything. Then, it looks at the results:

If the robot got the same answer every time (low variance), the coach says, "Okay, we get it, let's move on."
If the robot's answers were all over the place (high variance), the coach says, "This one is tricky! Let's give it more tries to figure it out."

The method then pours more "guessing energy" (rollouts) only into the puzzles that are causing the most confusion, while ignoring the ones that are too easy or too broken to learn from. It's like a video game that only spawns more difficult enemies for the player who is struggling, rather than making the easy levels harder just to fill time.

The paper shows that this approach is a game-changer. By using this "variance-guided" strategy, the robot reaches the same level of skill using significantly fewer guesses. On math problems, VIGOR reached its target accuracy with up to 2.3 times fewer rollouts than the standard method. On coding tasks, it reached the same success rate with 1.49 times fewer rollouts and even improved the final success rate by 3.4 points.

The authors suggest that this isn't just a small tweak; it's a fundamental shift in how we teach AI to reason. They measured these results across different sizes of AI models and found that VIGOR consistently learns faster and more efficiently. It proves that you don't need to throw more computing power at a problem to solve it; you just need to be smarter about where you spend that power. By focusing only on the moments of uncertainty, VIGOR helps AI learn to reason more effectively, turning a chaotic trial-and-error process into a focused, efficient journey of discovery.

Technical Summary: VIGOR – Variance Guided Online Rollout Allocation

1. Problem Statement

Reinforcement Learning with Verifiable Rewards (RLVR) has become a dominant paradigm for enhancing the reasoning capabilities of Large Language Models (LLMs), with Group Relative Policy Optimization (GRPO) serving as a leading instantiation. However, GRPO faces significant efficiency and stability challenges:

Computational Bottleneck: GRPO relies on generating a large, fixed number of chain-of-thought (CoT) rollouts per prompt. Empirical analysis in the paper reveals that rollout generation consumes at least 50% of total training time, scaling linearly with the number of rollouts.
Informativeness Mismatch: A substantial fraction of generated rollouts are uninformative, often exhibiting little to no reward variance within a group. These samples contribute negligible gradient signals, wasting computational resources.
Inefficiency of Existing Solutions: Current strategies to improve efficiency either generate excessive rollouts to filter for difficult prompts (incurring high overhead) or rely on historical signals to filter data in later training stages. These approaches fail to prioritize informative examples during the early stages of training, which the authors identify as disproportionately critical for final performance gains.

2. Methodology: VIGOR

The authors propose VarIance Guided Online Rollout allocation (VIGOR), an iterative data selection framework designed to adaptively allocate rollout budgets without modifying the underlying GRPO training objective.

Core Theoretical Insight

The method is grounded in a theoretical observation regarding the GRPO gradient magnitude. Under a binary reward setting (common in RLVR), the authors prove that the magnitude of the gradient signal is directly controlled by the within-group reward variance ( $\sigma$ ). Specifically, the gradient norm is bounded by $M\sigma$ , where $M$ is a bound on the importance ratio gradients. This implies that prompts with high reward variance provide the strongest learning signals, while those with zero variance (where all rollouts receive the same reward) provide no gradient signal.

Algorithmic Framework

Unlike standard GRPO, which allocates a fixed number of rollouts ( $G$ ) to every prompt in a single pass, VIGOR operates iteratively within each training step:

Initialization: For a batch of prompts, VIGOR starts with a small initial rollout budget ( $m_0$ ) for all examples.
Iterative Refinement: Over $T$ $T$ refinement iterations:
- Generation: New rollouts are generated for the current active subset of prompts.
- Variance Estimation: The utility score for each prompt is calculated as the variance of the rewards of its accumulated rollouts.
- Selection: The top- $\alpha$ fraction of prompts with the highest variance are retained for the next iteration.
- Budget Expansion: The rollout budget for retained prompts is multiplied by an expansion factor $\gamma$ ( $m_{t+1} = \gamma m_t$ ).
Update: Once the total budget is exhausted or iterations complete, all accumulated rollouts are used to compute advantages and update the policy via standard GRPO.

This process effectively concentrates computational resources on "hard" or "uncertain" prompts (high variance) while discarding low-value prompts early, avoiding the cost of generating full rollouts for uninformative samples.

Theoretical Speedup

The authors derive a closed-form speedup ratio for VIGOR over GRPO. Assuming prompt-level reward variance follows a Pareto distribution (heavy-tailed), the ratio of training timescales ( $\tau_{GRPO} / \tau_{VIGOR}$ ) grows with the number of refinement rounds $T$ . This suggests that VIGOR's efficiency gains are theoretically guaranteed to increase as the training process refines its focus on the most informative subset of data.

3. Key Contributions

Identification of Variance as a Signal: The paper establishes that reward variance is a direct proxy for gradient magnitude in GRPO, providing a theoretical basis for variance-guided selection.
VIGOR Algorithm: A novel, online rollout allocation strategy that dynamically shifts compute toward high-variance prompts without requiring auxiliary models, historical data filtering, or modifications to the GRPO objective.
Theoretical Analysis: Derivation of a convergence speedup ratio demonstrating that VIGOR outperforms uniform allocation, particularly under heavy-tailed variance distributions common in reasoning tasks.
Comprehensive Empirical Validation: Extensive experiments across mathematical reasoning and coding tasks using multiple model scales (Qwen2.5-1.5B/3B/7B, Phi-4-Mini, Qwen3-8B).

4. Experimental Results

The authors evaluated VIGOR against standard GRPO and state-of-the-art baselines (GRESO, RL-ZVP, PODS) on six mathematical reasoning benchmarks and LiveCodeBench v6.

Mathematical Reasoning:
- VIGOR reaches target accuracy with up to 2.3 $\times$ fewer rollouts compared to GRPO, GRESO, and RL-ZVP (specifically on Qwen2.5-3B).
- Under fair rollout-matched comparisons, VIGOR achieves the best average scores across all four model scales tested.
- Even when compared against GRESO-g (which uses roughly twice the rollout budget), VIGOR achieves higher average scores on most benchmarks.
Coding (LiveCodeBench v6):
- On Qwen3-8B, VIGOR reaches GRPO's final full pass rate with 1.49 $\times$ fewer rollouts (a 32.9% reduction).
- VIGOR improves the average test pass rate by 3.4 percentage points (from 63.4% to 66.8%) compared to GRPO.
Efficiency and Overhead:
- Wall-clock time measurements show VIGOR incurs no extra time overhead compared to baseline GRPO at the same rollout budget.
- VIGOR is significantly faster than GRESO, which requires generating extra rollouts for filtering.
- Ablation studies confirm that variance-based selection outperforms random selection and difficulty-based selection, validating the theoretical motivation.

5. Significance and Claims

The paper claims that VIGOR offers a simple yet effective mechanism to improve the efficiency of RLVR training. Its significance lies in:

Early-Stage Optimization: By adaptively allocating resources based on online variance signals, VIGOR ensures that the most critical early training phases utilize compute on the most informative examples, addressing a key limitation of history-dependent methods.
Paradigm Preservation: Unlike methods that alter the training objective or require complex auxiliary signals, VIGOR works within the standard GRPO framework, making it easily integrable.
Scalability: The method demonstrates robust performance across different model sizes and task domains (math and coding), suggesting that variance-guided iterative rollout generation is a generalizable strategy for compute-efficient reasoning.

The authors conclude that VIGOR represents a promising direction for scaling RLVR, enabling models to achieve higher performance with significantly reduced computational budgets.