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

• URL: http://arxiv.org/abs/2505.23564v1
• Date: Thu, 29 May 2025 15:38:19 GMT
• Title: Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models
• Authors: Yiran Guo, Lijie Xu, Jie Liu, Dan Ye, Shuang Qiu,
• Abstract summary: We propose Segment Policy Optimization (SPO), a novel RL framework that leverages segment-level advantage estimation at an intermediate granularity.<n>SPO features three components with novel strategies: (1) flexible segment partition; (2) accurate segment advantage estimation; and (3) policy optimization using segment advantages.<n>SPO-chain for short chain-of-thought (CoT), featuring novel cutpoint-based partition and chain-based advantage estimation, achieves $6$-$12$ percentage point improvements in accuracy over PPO and GRPO on GSM8K.<n>SPO-tree for long chain-of-thought (CoT), featuring novel tree-based advantage
• Score: 10.408501899305262
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 the 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.

Related papers

• Outcome-Grounded Advantage Reshaping for Fine-Grained Credit Assignment in Mathematical Reasoning [60.00161035836637]
  Group Relative Policy Optimization has emerged as a promising critic-free reinforcement learning paradigm for reasoning tasks.<n>We introduce Outcome-grounded Advantage Reshaping (OAR), a fine-grained credit assignment mechanism that redistributes advantages based on how much each token influences the model's final answer.<n>OAR-G achieves comparable gains with negligible computational overhead, both significantly outperforming a strong GRPO baseline.
  arXiv  Detail & Related papers  (2026-01-12T10:48:02Z)
• Segmental Advantage Estimation: Enhancing PPO for Long-Context LLM Training [17.530233901658253]
  Segmental Advantage Estimation mitigates the bias that Generalized Advantage Estimation can incur in Reinforcement Learning with Verifiable Rewards.<n> SAE achieves superior performance, with marked improvements in final scores, stability, and sample efficiency.
  arXiv  Detail & Related papers  (2026-01-12T08:41:47Z)
• PRPO: Aligning Process Reward with Outcome Reward in Policy Optimization [15.965340493880701]
  We introduce Process Relative Policy Optimization (PRPO), which combines outcome reliability with process-level guidance in a critic-free framework.<n>PRPO segments reasoning sequences based on semantic clues, normalizes PRM scores into token-level advantages, and aligns their distribution with outcome advantages.<n>On MATH500, PRPO improves Qwen2.5-Math-1.5B accuracy from 61.2% to 64.4% over GRPO using only eight rollouts and no value network.
  arXiv  Detail & Related papers  (2026-01-12T04:04:43Z)
• Efficient Thought Space Exploration through Strategic Intervention [54.35208611253168]
  We propose a novel Hint-Practice Reasoning (HPR) framework that operationalizes this insight through two synergistic components.<n>The framework's core innovation lies in Distributional Inconsistency Reduction (DIR), which dynamically identifies intervention points.<n> Experiments across arithmetic and commonsense reasoning benchmarks demonstrate HPR's state-of-the-art efficiency-accuracy tradeoffs.
  arXiv  Detail & Related papers  (2025-11-13T07:26:01Z)
• Reinforcing Video Reasoning with Focused Thinking [65.85683941058916]
  We propose TW-GRPO, a novel framework that enhances visual reasoning with focused thinking and dense reward granularity.<n>Specifically, we employ a token weighting mechanism that prioritizes tokens with high informational density.<n>We also reformulate RL training by shifting from single-choice to multi-choice QA tasks.
  arXiv  Detail & Related papers  (2025-05-30T15:42:19Z)
• Accelerating RL for LLM Reasoning with Optimal Advantage Regression [52.0792918455501]
  We propose a novel two-stage policy optimization framework that directly approximates the optimal advantage function.<n>$A$*-PO achieves competitive performance across a wide range of mathematical reasoning benchmarks.<n>It reduces training time by up to 2$times$ and peak memory usage by over 30% compared to PPO, GRPO, and REBEL.
  arXiv  Detail & Related papers  (2025-05-27T03:58:50Z)
• KTAE: A Model-Free Algorithm to Key-Tokens Advantage Estimation in Mathematical Reasoning [19.25257653416883]
  Key-token Advantage Estimation (KTAE) is a novel algorithm that estimates fine-grained, token-level advantages without introducing additional models.<n>We show that models trained with GRPO+KTAE and DAPO+KTAE outperform baseline methods across five mathematical reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-05-22T16:00:33Z)
• DisCO: Reinforcing Large Reasoning Models with Discriminative Constrained Optimization [55.06360285372418]
  Group Relative Policy Optimization is a reinforcement learning method for large reasoning models (LRMs)<n>In this work, we analyze the GRPO objective under a binary reward setting and reveal an inherent limitation of question-level difficulty bias.<n>We introduce a new Discriminative Constrained Optimization framework for reinforcing LRMs, grounded in the principle of discriminative learning.
  arXiv  Detail & Related papers  (2025-05-18T11:08:32Z)
• Token-Efficient RL for LLM Reasoning [0.02488650627593658]
  We propose reinforcement learning strategies tailored for reasoning in large language models (LLMs) under strict memory and compute limits.<n>Building on early policy gradient methods with baseline subtraction, we design critic-free methods that operate on a small, informative subset of output tokens.<n>We show that our methods raise accuracy on the SVAMP benchmark from 46% to over 70% and show strong performance on multi-digit multiplication.
  arXiv  Detail & Related papers  (2025-04-29T14:58:43Z)
• Optimizing Safe and Aligned Language Generation: A Multi-Objective GRPO Approach [2.8626097661711394]
  Reinforcement Learning from Human Feedback has achieved notable success in steering models, but is complex and can be unstable.<n>Recent approaches such as Direct Preference Optimization (DPO) simplify preference-based fine-tuning but may introduce bias or trade-off certain objectives.<n>We propose a Group Relative Policy Optimization framework with a multi-label reward regression model to achieve safe and aligned language generation.
  arXiv  Detail & Related papers  (2025-03-26T05:50:33Z)
• VinePPO: Unlocking RL Potential For LLM Reasoning Through Refined Credit Assignment [66.80143024475635]
  We propose VinePPO, a straightforward approach to compute unbiased Monte Carlo-based estimates. We show that VinePPO consistently outperforms PPO and other RL-free baselines across MATH and GSM8K datasets.
  arXiv  Detail & Related papers  (2024-10-02T15:49:30Z)
• Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning [55.96599486604344]
  We introduce an approach aimed at enhancing the reasoning capabilities of Large Language Models (LLMs) through an iterative preference learning process. We use Monte Carlo Tree Search (MCTS) to iteratively collect preference data, utilizing its look-ahead ability to break down instance-level rewards into more granular step-level signals. The proposed algorithm employs Direct Preference Optimization (DPO) to update the LLM policy using this newly generated step-level preference data.
  arXiv  Detail & Related papers  (2024-05-01T11:10:24Z)
• Learning What Not to Segment: A New Perspective on Few-Shot Segmentation [63.910211095033596]
  Recently few-shot segmentation (FSS) has been extensively developed. This paper proposes a fresh and straightforward insight to alleviate the problem. In light of the unique nature of the proposed approach, we also extend it to a more realistic but challenging setting.
  arXiv  Detail & Related papers  (2022-03-15T03:08:27Z)
• Selective Classification via One-Sided Prediction [54.05407231648068]
  One-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime. We theoretically derive bounds generalization for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.
  arXiv  Detail & Related papers  (2020-10-15T16:14:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.