MaxPO Cuts Gradient Variance by 77% When Training AI to Self-Improve
MaxPO introduces a Leave-Two-Out baseline that cuts gradient variance by 77% and boosts math reasoning pass@256 by up to 5.2% over existing methods
Takeaways
- MaxPO introduces a Leave-Two-Out (L2O) baseline for max@K policy gradient training, fixing a centering flaw in existing methods like PKPO.
- The L2O baseline reduces gradient variance by 77.4% on Llama-3.2-3B-Instruct compared to PKPO during RL fine-tuning.
- MaxPO improves pass@256 by 5.2% on Qwen2.5-Math-7B and 2.4% on Llama-3.2-3B-Instruct across five math benchmarks.
- The paper provides a unified theoretical framework showing existing estimators (PKPO, Entropy-Adv) are uncentered, while MaxPO achieves exact batch centering.
- Implementation is an O(B²) vectorized operation that plugs into any GRPO-style training loop with no other changes required.
- A companion library, OrderGrad, generalizes the approach to arbitrary rank-weighted objectives (CVaR, top-M, trimmed means) under MIT license.
Most LLM post-training work today optimizes for pass@1: can the model get the right answer on a single try? But for real deployment, what often matters more is pass@K or max@K -- can the model produce at least one correct answer (or the best possible answer) across K independent attempts? A new paper, "On Advantage Estimates for Max@K Policy Gradients", zeroes in on a subtle but consequential flaw in how existing methods compute gradient signals for these objectives, and proposes a cleaner fix called MaxPO.
Why optimizing for "best of K" is hard
Reinforcement learning with verifiable rewards is widely used for post-training reasoning models, but sparse outcome rewards make exploration difficult. The standard workaround is GRPO (Group Relative Policy Optimization), which samples a group of responses per prompt and uses their relative rewards as gradient weights. GRPO samples multiple responses and uses standard scores of their rewards as gradient weights, eliminating the need for training an additional model for advantage estimation.
But GRPO optimizes for the average response quality. When you care about the best response in a group -- the max@K objective -- you need a different gradient signal. Existing policy-gradient estimators for these objectives use different signals, baselines, and normalizations, making their relationships unclear. The field has produced several competing methods (PKPO, Entropy-Adv, EI-based estimators) with no clear unifying theory explaining when and why one beats another.
The centering problem nobody talked about
To understand the paper's contribution, you need to know what an advantage is in this context: it's the signal that tells the policy gradient update which responses to push up and which to push down. A well-designed advantage should be centered -- meaning the positive and negative signals in a training batch should cancel out to zero. This matters because uncentered advantages introduce a systematic bias in the gradient direction that inflates variance and destabilizes training.