Rewarding the Unlikely: Lifting GRPO Beyond Distribution Sharpening

2025/06/03 by Aishan He, He, Andre, Daniel B. Fried +3 · 25 citations
Business, Management and Accounting · Economics, Econometrics and Finance · Mathematics · #Census and Population Estimation #FOS: Computer and information sciences #Healthcare Policy and Management #Machine Learning (cs.LG) #Public Procurement and Policy

paper · pdf · doi:10.48550/arxiv.2506.02355

openalex publication_date 2025/06/03 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28

Abstract

Reinforcement learning is emerging as a primary driver for improving language model reasoning capabilities. A fundamental question is whether current reinforcement learning algorithms -- such as Group Relative Policy Optimization (GRPO), the de facto standard algorithm used to improve language model reasoning -- merely sharpen the base model's distribution around problems it can already solve. We investigate this question in the context of formal theorem proving, which has access to a perfect verifier. We identify a degenerate rank bias in GRPO in which highly probable trajectories are reinforced and rare ones are neglected. This results in distribution sharpening: the model can solve some problems with fewer samples, but underperforms simply sampling more solutions from the original model. To overcome GRPO's rank bias we introduce unlikeliness reward, a simple method for explicitly up-weighting rare but correct solutions. We show that unlikeliness reward mitigates rank bias and improves pass@N across a large range of N in both synthetic and real theorem proving settings. We also uncover an unexpected link between rank bias and a seemingly mundane hyperparameter -- the number of updates per batch -- that leads to a second, complementary mitigation. We combine our insights into a revised GRPO training recipe for formal theorem proving, yielding an open pipeline that achieves competitive performance to DeepSeek-Prover-V1.5-RL on the miniF2F-test benchmark. We release our implementation at https://github.com/AndreHe02/rewarding-unlikely-release

Cited by

• AdaSearch: Balancing Parametric Knowledge and Search in Large Language Models via Reinforcement Learning
• Whatever Remains Must Be True: Filtering Drives Reasoning in LLMs, Shaping Diversity
• Differential Smoothing Mitigates Sharpening and Improves LLM Reasoning
• The Peril of Preference: Why GRPO fails on Ordinal Rewards
• KL-Regularized Reinforcement Learning is Designed to Mode Collapse
• Reasoning with Sampling: Your Base Model is Smarter Than You Think
• Representation-Based Exploration for Language Models: From Test-Time to Post-Training
• RLFR: Extending Reinforcement Learning for LLMs with Flow Environment
• Rethinking Entropy Interventions in RLVR: An Entropy Change Perspective
• GCPO: When Contrast Fails, Go Gold
• Beyond Pass@k: Breadth-Depth Metrics for Reasoning Boundaries
• The Debate on RLVR Reasoning Capability Boundary: Shrinkage, Expansion, or Both? A Two-Stage Dynamic View
• Clip-Low Increases Entropy and Clip-High Decreases Entropy in Reinforcement Learning of Large Language Models
• Nudging the Boundaries of LLM Reasoning
• Polychromic Objectives for Reinforcement Learning
• Random Policy Valuation is Enough for LLM Reasoning with Verifiable Rewards
• Risk-Sensitive RL for Alleviating Exploration Dilemmas in Large Language Models
• Group Critical-token Policy Optimization for Autoregressive Image Generation
• Position: The Hidden Costs and Measurement Gaps of Reinforcement Learning with Verifiable Rewards
• Post-training Large Language Models for Diverse High-Quality Responses
• Jointly Reinforcing Diversity and Quality in Language Model Generations
• GTPO: Stabilizing Group Relative Policy Optimization via Gradient and Entropy Control
• The Invisible Leash: Why RLVR May or May Not Escape Its Origin
• Decomposer: Learning to Decompile Symbolic Music to Programs
• ExPO: Unlocking Hard Reasoning with Self-Explanation-Guided Reinforcement Learning

Related

• Can GRPO Help LLMs Transcend Their Pretraining Origin?
• Sharpness-Guided Group Relative Policy Optimization via Probability Shaping
• λ-GRPO: Unifying the GRPO Frameworks with Learnable Token Preferences
• Stepwise Guided Policy Optimization: Coloring your Incorrect Reasoning in GRPO
• Token Hidden Reward: Steering Exploration-Exploitation in Group Relative Deep Reinforcement Learning