# Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models

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

## Key facts

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

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)

## Builds on (most cited first, 30 of 32)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Process Reinforcement through Implicit Rewards](https://mlsanity.com/paper/2502.01456/) (2025)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [Scaling Relationship on Learning Mathematical Reasoning with Large Language Models](https://mlsanity.com/paper/2308.01825/) (2023)
- [Beyond Human Data: Scaling Self-Training for Problem-Solving with Language Models](https://mlsanity.com/paper/2312.06585/) (2023)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [From r to Q^*: Your Language Model is Secretly a Q-Function](https://mlsanity.com/paper/2404.12358/) (2024)
- [Advancing LLM Reasoning Generalists with Preference Trees](https://mlsanity.com/paper/2404.02078/) (2024)
- [AlphaMath Almost Zero: Process Supervision without Process](https://mlsanity.com/paper/2405.03553/) (2024)
- [Rho-1: Not All Tokens Are What You Need](https://mlsanity.com/paper/2404.07965/) (2024)
- [Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuning](https://mlsanity.com/paper/2503.07572/) (2025)
- [On Memorization of Large Language Models in Logical Reasoning](https://mlsanity.com/paper/2410.23123/) (2024)
- [Let's reward step by step: Step-Level reward model as the Navigators for Reasoning](https://mlsanity.com/paper/2310.10080/) (2023)
- [CPPO: Accelerating the Training of Group Relative Policy Optimization-Based Reasoning Models](https://mlsanity.com/paper/2503.22342/) (2025)
- [An Empirical Study on Eliciting and Improving R1-like Reasoning Models](https://mlsanity.com/paper/2503.04548/) (2025)
- [Asynchronous RLHF: Faster and More Efficient Off-Policy RL for Language Models](https://mlsanity.com/paper/2410.18252/) (2024)

## Built on by (most cited first, 30 of 75)

- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [A Survey of Reinforcement Learning for Large Reasoning Models](https://mlsanity.com/paper/2509.08827/) (2025)
- [Tree Search for LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2509.21240/) (2025)
- [TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling](https://mlsanity.com/paper/2508.17445/) (2025)
- [TreeRPO: Tree Relative Policy Optimization](https://mlsanity.com/paper/2506.05183/) (2025)
- [StepHint: Multi-level Stepwise Hints Enhance Reinforcement Learning to Reason](https://mlsanity.com/paper/2507.02841/) (2025)
- [Look Inward to Explore Outward: Learning Temperature Policy from LLM Internal States via Hierarchical RL](https://mlsanity.com/paper/2602.13035/) (2026)
- [From Reasoning to Agentic: Credit Assignment in Reinforcement Learning for Large Language Models](https://mlsanity.com/paper/2604.09459/) (2026)
- [Attention as a Compass: Efficient Exploration for Process-Supervised RL in Reasoning Models](https://mlsanity.com/paper/2509.26628/) (2025)
- [GEAR: Granularity-Adaptive Advantage Reweighting for LLM Agents via Self-Distillation](https://mlsanity.com/paper/2605.11853/) (2026)
- [Unlocking the Power of Multi-Agent LLM for Reasoning: From Lazy Agents to Deliberation](https://mlsanity.com/paper/2511.02303/) (2025)
- [Bringing Value Models Back: Generative Critics for Value Modeling in LLM Reinforcement Learning](https://mlsanity.com/paper/2604.10701/) (2026)
- [Why Tree-Style Branching Matters for Thought Advantage Estimation in GRPO](https://mlsanity.com/paper/2509.24494/) (2025)
- [Beyond High-Entropy Exploration: Correctness-Aware Low-Entropy Segment-Based Advantage Shaping for Reasoning LLMs](https://mlsanity.com/paper/2512.00908/) (2025)
- [TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning](https://mlsanity.com/paper/2606.11119/) (2026)
- [ESPO: Entropy Importance Sampling Policy Optimization](https://mlsanity.com/paper/2512.00499/) (2025)
- [TDRM: Smooth Reward Models with Temporal Difference for LLM RL and Inference](https://mlsanity.com/paper/2509.15110/) (2025)
- [Enhancing Large Language Model Reasoning with Reward Models: An Analytical Survey](https://mlsanity.com/paper/2510.01925/) (2025)
- [Multi-GRPO: Multi-Group Advantage Estimation for Text-to-Image Generation with Tree-Based Trajectories and Multiple Rewards](https://mlsanity.com/paper/2512.00743/) (2025)
- [ATPO: Adaptive Tree Policy Optimization for Multi-Turn Medical Dialogue](https://mlsanity.com/paper/2603.02216/) (2026)
- [Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimization](https://mlsanity.com/paper/2604.07165/) (2026)
- [CAPO: Critic-Guided Action-Aligned Policy Optimization for Advancing LLM Agent Capabilities](https://mlsanity.com/paper/2604.18401/) (2026)
- [CEPO: RLVR Self-Distillation using Contrastive Evidence Policy Optimization](https://mlsanity.com/paper/2605.19436/) (2026)
- [SketchVL: Policy Optimization via Fine-Grained Credit Assignment for Chart Understanding and More](https://mlsanity.com/paper/2601.05688/) (2026)
- [Beyond Uniform Credit: Causal Credit Assignment for Policy Optimization](https://mlsanity.com/paper/2602.09331/) (2026)
- [GRPO-VPS: Enhancing Group Relative Policy Optimization with Verifiable Process Supervision for Effective Reasoning](https://mlsanity.com/paper/2604.20659/) (2026)
- [From "Aha Moments" to Controllable Thinking: Toward Meta-Cognitive Reasoning in Large Reasoning Models via Decoupled Reasoning and Control](https://mlsanity.com/paper/2508.04460/) (2025)
- [Solving the Granularity Mismatch: Hierarchical Preference Learning for Long-Horizon LLM Agents](https://mlsanity.com/paper/2510.03253/) (2025)
- [Blockwise Advantage Estimation for Multi-Objective RL with Verifiable Rewards](https://mlsanity.com/paper/2602.10231/) (2026)
- [Strategy-Aware Optimization Modeling with Reasoning LLMs](https://mlsanity.com/paper/2605.02545/) (2026)

## Abstract (arXiv)

Enhancing the reasoning capabilities of large language models effectively using reinforcement learning (RL) remains a crucial challenge. Existing approaches primarily adopt two contrasting advantage estimation granularities: token-level methods (e.g., PPO) aim to provide fine-grained advantage signals but suffer from inaccurate estimation due to difficulties in training an accurate critic model. On the other extreme, trajectory-level methods (e.g., GRPO) solely rely on a coarse-grained advantage signal from the final reward, leading to imprecise credit assignment. To address these limitations, we propose Segment Policy Optimization (SPO), a novel RL framework that leverages segment-level advantage estimation at an intermediate granularity, achieving a better balance by offering more precise credit assignment than trajectory-level methods and requiring fewer estimation points than token-level methods, enabling accurate advantage estimation based on Monte Carlo (MC) without a critic model. SPO features three components with novel strategies: (1) flexible segment partition; (2) accurate segment advantage estimation; and (3) policy optimization using segment advantages, including a novel probability-mask strategy. We further instantiate SPO for two specific scenarios: (1) SPO-chain for short chain-of-thought (CoT), featuring novel cutpoint-based partition and chain-based advantage estimation, achieving 6-12 percentage point improvements in accuracy over PPO and GRPO on GSM8K. (2) SPO-tree for long CoT, featuring novel tree-based advantage estimation, which significantly reduces the cost of MC estimation, achieving 7-11 percentage point improvements over GRPO on MATH500 under 2K and 4K context evaluation. We make our code publicly available at https://github.com/AIFrameResearch/SPO.