Technical Summary: On the Optimization Dynamics of RLVR

Problem Statement

Reinforcement Learning with Verifiable Rewards (RLVR) has emerged as a dominant paradigm for post-training Large Language Models (LLMs) on tasks with automatically checkable outcomes, such as mathematical reasoning and code generation. Unlike traditional Reinforcement Learning from Human Feedback (RLHF), RLVR relies on sparse, binary success/failure signals rather than learned reward models or human preferences. While algorithms like Group Relative Policy Optimization (GRPO) and its variants (e.g., DAPO, Dr. GRPO) have demonstrated significant empirical success, the theoretical understanding of their optimization dynamics remains limited. Practitioners often rely on heuristics—such as length normalization or variance-based reward scaling—to stabilize training, yet the conditions under which these methods converge, stagnate, or catastrophically fail are not rigorously characterized. This paper addresses the gap between empirical performance and theoretical understanding by analyzing the convergence guarantees of policy gradient methods under binary rewards.

Methodology

The authors develop a theoretical framework to analyze the training dynamics of RLVR at two levels of granularity: the trajectory level (treating the entire response as a single unit) and the token level (accounting for the autoregressive generation process).

Core Concepts

1. Gradient Gap: The paper introduces a novel quantity, the Gradient Gap ($g^+_q - g^-_q$), defined as the difference between the expected score functions (log-probability gradients) over the space of correct responses ($O^+_q$) and incorrect responses ($O^-_q$). This gap formalizes the true direction of improvement required to shift the policy from low-reward to high-reward regions.
2. Gap Alignment: The authors define the Gap Alignment ($\Delta\mu_q$) as the inner product between the actual update direction ($w_k$) and the Gradient Gap. This metric quantifies how well the algorithm's update aligns with the true objective.
3. Cumulative Gap Alignment: To characterize long-term behavior, the paper defines a cumulative metric ($M_q(K)$) that aggregates the alignment signal over training iterations, weighted by the step size.

Theoretical Analysis

The analysis relies on standard regularity assumptions regarding the smoothness and boundedness of the policy score function (Assumptions 1 and 2) and the sub-exponential nature of response lengths (Assumption 3).

• Trajectory-Level Analysis: The authors derive bounds on the change in the log-odds of the success rate ($J_q$) per update step. They establish that the first-order improvement is driven by the Gap Alignment, while second-order variance terms (specifically the variance of the negative space) can cause instability if the step size is too large.
• Token-Level Analysis: By decomposing the gradient into token-wise contributions, the authors refine the convergence bounds. This analysis explicitly incorporates response length ($T_\infty, T_{\psi_1}$), revealing that the effective step size must scale inversely with sequence length to prevent divergence.

Key Contributions

1. Unified Theoretical Framework for RLVR

The paper provides a principled framework applicable to any policy-gradient-based method (including REINFORCE, GRPO, and Dr. GRPO) operating under binary rewards. It unifies the analysis of these algorithms by characterizing their dynamics through the lens of the Gradient Gap and Gap Alignment.

2. Sharp Step-Size Thresholds

A central theoretical contribution is the derivation of a sharp step-size threshold that separates convergence from divergence.

• Convergence: The paper proves that if the step size ($\eta_k$) is adaptively scaled to be proportional to the Gap Alignment and inversely proportional to the variance and response length, the policy converges to the optimal solution ($J_q \to 1$).
• Catastrophic Failure: Conversely, the authors prove that if the step size exceeds a specific threshold (even if the update direction is perfectly aligned), the optimization process will overshoot, causing the success rate to strictly decrease and converge to zero. This explains the "collapse" phenomena observed in practice.

3. Explanation of Practical Heuristics

The theory offers a rigorous justification for common engineering practices:

• Length Normalization: The token-level analysis demonstrates that the effective learning rate must shrink as response length increases. This provides a theoretical basis for why length normalization (used in GRPO) stabilizes training, whereas methods lacking this normalization (like certain formulations of Dr. GRPO) may struggle with longer sequences.
• Stagnation: The paper explains why fixed learning rates can lead to stagnation at success rates strictly below 100%. As the policy improves, the variance structure changes, and a fixed step size may eventually violate the convergence threshold, causing the algorithm to stall or oscillate.

4. Empirical Validation

The theoretical predictions are validated through:

• Contextual Bandit Simulations: Experiments on synthetic bandit problems demonstrate the logistic relationship between Cumulative Gap Alignment and accuracy, confirming the existence of distinct convergence and stagnation regimes.
• LLM Experiments: The authors fine-tuned the Qwen2.5-Math-7B model on GSM8K, DeepScaleR, and DAPO-17k datasets using GRPO. The empirical data shows a strong correlation between the Cumulative Gap Alignment and the model's accuracy, aligning closely with the theoretical lower bounds.

Results

• Convergence Guarantees: The paper establishes that convergence to perfect performance is guaranteed if the Cumulative Gap Alignment diverges to infinity ($M_q(K) \to \infty$).
• Stagnation Bounds: If the alignment signal is weak or the step size is too large, the performance is bounded strictly below 1, preventing the model from reaching 100% accuracy.
• Failure Modes: The authors construct specific problem instances where a constant step size, despite positive alignment, leads to monotonic performance decay to zero, confirming the existence of a "catastrophic failure" regime.
• Gradient Norms vs. Reward: The paper notes that the sum of policy gradient norms may converge even when the reward does not, suggesting that standard gradient-based convergence criteria are insufficient for RLVR; the Gap Alignment metric is a sharper indicator of reward improvement.

Significance

The paper claims to provide the first rigorous theoretical foundation for the optimization dynamics of RLVR. By moving beyond black-box empirical observations, it identifies the Gradient Gap as the fundamental driver of learning and the step-size threshold as the critical control parameter for stability.

The significance lies in its ability to:

1. Demystify RLVR: It explains why certain algorithms (like GRPO with length normalization) work while others fail, moving the field from intuition-based tuning to theory-guided design.
2. Guide Hyperparameter Tuning: It provides concrete, mathematically derived conditions for step-size selection, offering a path to avoid catastrophic collapse and stagnation.
3. Characterize Algorithm Behavior: It clarifies the limitations of fixed learning rates and the necessity of adaptive scaling relative to response length and task difficulty, offering a theoretical explanation for the observed stagnation of correction rates in current RLVR pipelines.

The authors conclude that their framework characterizes the dynamics of popular approaches and suggests future directions, such as prompt-adaptive updates and curriculum-based training, to further enhance stability and convergence in diverse prompt distributions.