# Stratified GRPO: Handling Structural Heterogeneity in Reinforcement Learning of LLM Search Agents

arXiv: https://arxiv.org/abs/2510.06214 · HTML: https://mlsanity.com/paper/2510.06214/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 7 Oct 2025.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)
- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 13 of 13)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [A Survey of Large Language Models](https://mlsanity.com/paper/2303.18223/) (2023)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [Search-o1: Agentic Search-Enhanced Large Reasoning Models](https://mlsanity.com/paper/2501.05366/) (2025)
- [R1-Searcher: Incentivizing the Search Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2503.05592/) (2025)
- [DeepResearcher: Scaling Deep Research via Reinforcement Learning in Real-world Environments](https://mlsanity.com/paper/2504.03160/) (2025)
- [ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning](https://mlsanity.com/paper/2503.19470/) (2025)

## Built on by (most cited first, 6 of 6)

- [Blockwise Advantage Estimation for Multi-Objective RL with Verifiable Rewards](https://mlsanity.com/paper/2602.10231/) (2026)
- [PDCR: Perception-Decomposed Confidence Reward for Vision-Language Reasoning](https://mlsanity.com/paper/2605.13467/) (2026)
- [Knowledge-Graph Paths as Intermediate Supervision for Self-Evolving Search Agents](https://mlsanity.com/paper/2605.05702/) (2026)
- [MetaResearcher: Scaling Deep Research via Self-Reflective Reinforcement Learning in Adversarial Virtual Environments](https://mlsanity.com/paper/2606.19893/) (2026)
- [Dissecting Advantage-Guided Post-Training for Vision-Language-Action Policies](https://mlsanity.com/paper/2609.28161/) (2026)
- [CLIFT: Conformal Self-Verification for Web Agent Training and Test-Time Scaling](https://mlsanity.com/paper/2610.06829/) (2026)

## Abstract (arXiv)

Large language model (LLM) agents increasingly rely on external tools such as search engines to solve complex, multi-step problems, and reinforcement learning (RL) has become a key paradigm for training them. However, the trajectories of search agents are structurally heterogeneous, where variations in the number, placement, and outcomes of search calls lead to fundamentally different answer directions and reward distributions. Standard policy gradient methods, which use a single global baseline, suffer from what we identify and formalize as cross-stratum bias-an "apples-to-oranges" comparison of heterogeneous trajectories. This cross-stratum bias distorts credit assignment and hinders exploration of complex, multi-step search strategies. To address this, we propose Stratified GRPO, whose central component, Stratified Advantage Normalization (SAN), partitions trajectories into homogeneous strata based on their structural properties and computes advantages locally within each stratum. This ensures that trajectories are evaluated only against their true peers. Our analysis proves that SAN eliminates cross-stratum bias, yields conditionally unbiased unit-variance estimates inside each stratum, and retains the global unbiasedness and unit-variance properties enjoyed by standard normalization, resulting in a more pure and scale-stable learning signal. To improve practical stability under finite-sample regimes, we further linearly blend SAN with the global estimator. Extensive experiments on diverse single-hop and multi-hop question-answering benchmarks demonstrate that Stratified GRPO consistently and substantially outperforms GRPO by up to 11.3 points, achieving higher training rewards, greater training stability, and more effective search policies. These results establish stratification as a principled remedy for structural heterogeneity in RL for LLM search agents.