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

Thanks for your valuable and constructive comments. Below, we provide detailed responses to the concerns and questions you have raised.

W1: While motivated, I'd like to see more visual examples. For example, the authors identify the cutpoints. I wonder if they could share actual examples of these cutpoints. I also wonder if these cutpoints always correspond to the end of a reasoning step, or could they be something else entirely.

In the previously submitted Appendix, we provided examples of cutpoints in Appendix I—please see Figure 11, where the red tokens indicate cutpoints. Many cutpoints correspond to numbers in the equations, and there are also cases where a cutpoint occurs at the beginning of a reasoning step or within a reasoning step.

W2: I'd also like to see more runtime / compute information being provided for SPO. For example, in Figure (4), interval 5 seems a lot more expensive to run than interval 100. However, this is not quantified, and in a way it's not a fair comparison between interval 5 and interval 100. One char that's useful is using the compute units (e.g., FLOPS or a crude runtime) on the x-axis, and the accuracy on the y-axis, using a scatter plot. Could the authors provide more runtime or compute budget information on SPO? For example, using an interval 5 seems to use a lot more computation than an interval 100. However, this is not quantified in Figure 4.

Thank you for your suggestion regarding runtime and compute information.

For the experiments in Figure 4(a), we measured the average wall-clock time per 10 training iterations under different interval settings:

• Interval 2 (int2): 1.43 hours per 10 iterations
• Interval 5 (int5): 0.87 hours per 10 iterations
• Interval 100 (int100): 0.58 hours per 10 iterations

We also measured the validation accuracy against the training wall-clock time for the three settings, as shown in the following table:

The results show that, within the first 100 hours of training, interval 5 achieves the highest validation accuracy, followed by interval 2, with interval 100 being the lowest. In terms of final accuracy, interval 2 achieves slightly higher accuracy than interval 5, while interval 100 trails further behind. Overall, these results indicate that using a moderate interval (such as interval 5) offers a more efficient trade-off, achieving better validation accuracy given the same training time compared to very short or very long intervals.

Thanks for the detailed reply. I appreciate the example on cutpoints and wall clock time.

Thanks for your valuable and constructive comments. Below, we provide detailed responses to the concerns and questions you have raised.

W1: The design details of the method are rather detailed, but the design motivation is too vague and empirical. It is more like a heuristic adjustment for the calculation scale of the advantages of Vine PPO..

Thanks for this feedback. The motivation of SPO is to find a new way to solve the critical credit assignment problem in RL for LLM, which is not well solved by the existing token-level and trajectory-level approaches. Our main insight is to adopt segment-level (medium-level) advantage estimation. This approach provides richer feedback signals than GRPO and eliminates the need for a critic model. However, the segment-level approach introduces new problems: (1) how to perform the segment partition? (2) how to compute the segment-level advantage efficiently, especially for long CoT? (3) how to do policy update within each segment? The solutions proposed in VinePPO are inadequate to solve these problems. Compared to VinePPO, our SPO is more general, effective, and efficient, as described below:

1. Generality: VinePPO uses semantic partitioning, i.e., splitting the response into steps based on semantic cues such as line breaks. This approach is limited to scenarios where the model’s responses can be easily divided into semantically meaningful steps. However, for many tasks, such as code generation or complex reasoning, it is challenging or even impossible to identify such semantic boundaries, which severely limits the applicability of VinePPO. In contrast, our method supports flexible segment partitioning without requiring semantic completeness, making it applicable to almost any task. Moreover, our framework allows seamless adjustment of segment granularity, from token-level (i.e., PPO) to trajectory-level (i.e., GRPO). Essentially, VinePPO can be regarded as a special case of our SPO-chain, using a straightforward semantic partitioning strategy without probability guidance.

2. Effectiveness: Compared to VinePPO, our method introduces a novel probability-guided segment partition strategy and a probability-mask technique. These allow us to partition the response at positions where the $V$ value is more likely to change, and to focus the optimization on critical tokens. Experimental results show that our method not only reduces sampling cost but also achieves higher accuracy than VinePPO. Furthermore, we analyze from a variance perspective and explain why using Monte Carlo estimation for segment advantage computation is effective.

3. Efficiency: Both VinePPO and our SPO-chain incur substantial sampling costs when dealing with long CoT, making them impractical for such scenarios. To address this, we propose SPO-tree, a novel tree-based structure that significantly improves efficiency and enables our method to be effectively applied in long CoT settings.

W2: It does not provide a good explanation for why the paragraphs formed by fixed-length tokens represent different semantics. (2) It does not explain why dividing paragraphs according to token probabilities is feasible and related to semantics.

Thanks for your comments. In our method, segment advantage values are estimated using Monte Carlo sampling rather than being predicted by a reward model. As a result, our SPO does not require each segment to have coherent or distinct semantics, nor do we rely on explicit semantic boundaries. Instead, the main objective of our segmentation is to ensure that the value function ($V$-value) at segment boundaries is likely to change, so that the computed advantage is non-zero. A non-zero advantage indicates whether generating the segment increases or decreases the probability of task success, thereby providing meaningful learning signals for model optimization. In the short chain-of-thought scenario, we identify tokens with low generation probability as cutpoints, which often correspond to positions where the model’s reasoning trajectory may branch and thus where the $V$-value may change. We then segment the response at regular intervals of these cutpoints, increasing the likelihood that the $V$-values at segment boundaries are different. In the long chain-of-thought scenario, each segment naturally contains a large number of cutpoints. Therefore, using a fixed-token-count partition strategy is a reasonable simplification for this setting, which also makes it compatible with our tree-based sampling method.

Q1: As VinePPO is the main comparison method, did it also set the same number of MC rollout to ensure the fairness of the experiment?

Yes, we use the same number of rollouts (K=9) for both VinePPO and our SPO-chain. We will clarify it in the experimental setup.

Q2: The basic model is too simple and has already been distilled using R1's mathematical data in advance. This makes the base model itself already have very good scores in mathematics (as shown in the author's experimental comparison table). The author should conduct experiments and verification in 1.5-base or qwen-1.6b-base, align with other RL-zero papers.

Thank you for your valuable suggestion regarding the evaluation on base models. We address your concern in two parts:

Motivation for using distilled models: Our primary motivation for choosing R1-distilled models is to evaluate our method’s effectiveness in long CoT scenarios. Specifically, the R1-Distill model demonstrates significantly longer output sequences compared to base or instruct models, which enables assessment of our approach in terms of both efficiency and model accuracy in long CoT reasoning settings. Furthermore, there are many recent works that perform RL training on R1-distilled models (e.g. DeepScaleR and STILL-3 in Table 1).

Experiments on Base Models: According to your suggestion, we have additionally conducted experiments on the MATH dataset using the Qwen2.5-Math-1.5B (base) model, which is also used in the recent zero-RL papers like Dr. GRPO. The results are listed below:

Qwen2.5-Math-1.5B (base):

In addition, we evaluated our approach with both Qwen2.5-0.5B-Instruct and Qwen2.5-1.5B-Instruct models on the GSM8K dataset. The results are shown below:

Qwen2.5-0.5B-Instruct:

Qwen2.5-1.5B-Instruct:

These results demonstrate that SPO-tree consistently outperforms GRPO across base, instruct, and R1-distill models, as well as different datasets.

Q3: It seems that the actual response generation of LLM has not been released.

Thank you for your comment. We have provided examples of model outputs in the previously submitted Appendix, including a short CoT exmaple in Appendix I with cutpoints and segment demonstration, as well as a long CoT output in Appendix J.

Thanks for your valuable and constructive comments. Below, we provide detailed responses to the concerns and questions you have raised.

W1: line 357: I do not think evaluating DeepScaleR under 2k or 4k budget is a fair comparison, since it is trained with much longer context size. it is also not directly related to token efficiency because of that reason. But GRPO indeed leads to redundancy and token inefficiency, as suggested by [1].

Thank you for pointing out this issue. We agree that evaluating DeepScaleR under a 2K or 4K context budget is not a fair comparison, as it was trained with a much longer context length and on a larger dataset. We plan to remove the DeepSacleR result from Table 1. To make our comparisons fair and meaningful, we focus primarily on GRPO and SPO models that are trained with the same context length and the same dataset. As shown in Table 1, across 2K, 4K, and 32K context settings, models trained with SPO consistently achieve higher accuracy than those trained with GRPO. This demonstrates the effectiveness of the SPO.

W2: The experiments did not show VinePPO with a probability mask, which I think is an important baseline to claim that the proposed method does better credit assignment

Thank you for your suggestion to include the results of VinePPO with the probability mask. In our new experiments, after adding our probability mask strategy, VinePPO improves its accuracy from 53.4% to 55.6%, demonstrating that our probability-mask strategy is generally effective. However, our SPO-chain (int5) method still achieves a higher accuracy of 56.7%, which indicates that our probability-guided segment partition strategy provides better credit assignment than VinePPO’s semantic split. Furthermore, as illustrated in Figure 3(b), our SPO-chain uses fewer segments and results in shorter training time compared to VinePPO, also highlighting its better efficiency than VinePPO.

Q1: line 297 - 299 & fig4: int2 is better than int5 from the figure, but the text says "whereas an overly coarse interval can severely degrade accuracy", which is confusing to me

Thank you for your comments and for pointing out this potential confusion regarding the interval settings. We would like to clarify the meaning of "int2", "int5", and "int100" in our experiments as follows:

• "int2" means partitioning the model output at intervals of every 2 cutpoints, which results in the most (finest) segments.
• "int5" means partitioning the model output at intervals of every 5 cutpoints, resulting in fewer (coarser) segments compared to int2.
• "int100" is an extreme setting: We partition the model output at intervals of every 100 cutpoints, which, given the total number of cutpoints, results in only one segment.

As Figure 4(a) shows, both int2 and int5 achieve high and similar accuracy, with int2 offering a marginal improvement. This suggests that an excessively fine-grained interval (e.g., int2 versus int5) provides limited benefits. However, int100 (only one segment) exhibits a significant performance drop, which supports our statement that “an overly coarse interval can severely degrade accuracy.”

Q2: following (1), I am curious what the result of int1 will be?

We suppose that int1 refers to only a single segment in your question. If so, this setting corresponds to what we refer to as int100 in our experiments (given the total number of cutpoints, int100 results in only one segment). As shown in Figure 4(a), the performance under this setting is significantly degraded, demonstrating the negative impact of having an overly coarse interval, as discussed above.

Q3: How did you ensure that the comparison with GRPO is fair? For example, given a question, GRPO unrolls 8 responses, while the proposed method unrolls 8 responses + K samples for MC value estimation. GRPO could do a similar thing: given the 8 responses, keep the thinking process and resample the final answer K times to estimate the value (this probably can be int1 mentioned in (2)). Have you considered this setting for a fairer comparison?

Thank you for this insightful and thoughtful suggestion. We would like to clarify that the method you described, while interesting, does not align with the standard GRPO setting, as commonly used in previous works and open-source frameworks.

As mentioned by the reviewer, the reviewer's proposed method can actually be seen as a special case of our SPO-tree (specifically "8-K") with two layers: the first layer contains 8 nodes, and each node has K leaves. The main difference lies in how the response is partitioned: the reviewer's proposed method partitions the response at </think> tokens, whereas our SPO partitions the response by fixed token count rather than specific delimiters like </think>.

We compare the test accuracy of the reviewer's method and SPO-tree (6-6-6) as follows. As shown in the table below, the accuracy of the reviewer’s proposed method is lower than that of our SPO-tree (6-6-6). This may be because using only two segments provides less feedback than three segments, and strictly segmenting at </think> may not be optimal, since the final answer's quality is heavily dependent on the preceding thinking process.

Q4: Have you tried SPO-chain on the long CoT scenario? or SPO-tree on the short CoT scenario?

SPO-tree for short CoT: Yes, we have conducted experiments with SPO-tree in the short CoT scenario, as shown in Figure 3(a). The results show that SPO-tree achieves 56.4% test accuracy, which is comparable to SPO-chain (56.7%) and outperforms all other baselines. This validates the effectiveness of SPO-tree in short CoT scenarios and shows that it can serve as an efficient alternative.

SPO-chain for long CoT: For the long CoT scenario, we did not evaluate SPO-chain, due to its computational inefficiency in this scenario. Specifically, at each segment boundary, SPO-chain samples K independent trajectories for value estimation. As each trajectory can be quite long in the long CoT scenario (i.e., involving thousands of tokens), the overhead for value estimation becomes prohibitively large, making it impractical for long CoT settings. Moreover, in SPO-chain, the samples used for value estimation are simply discarded, leading to substantial sample waste in the long CoT scenario.

The above issue inspired us to develop SPO-tree for long CoT. By organizing the sampling process into a tree structure and aggregating rewards from the bottom up, SPO-tree enables all samples used for value estimation can also contribute to policy optimization, substantially reducing the wastage inherent in SPO-chain. This design choice enables SPO-tree to be effectively applied to long CoT scenarios.

Q5: For fig5a, have you tried GRPO with probability mask? i am very curious its wall-clock time curve.

Thank you for your interest in this question. As suggested, we conduct new experiments by adding probability mask to GRPO, using the same configuration as GRPO in Fig. 6(a). The results are shown in the table below.

We observe that GRPO with probability mask outperforms vanilla GRPO to some extent, which demonstrates the effectiveness of the probability mask in long CoT scenarios. However, SPO-tree still achieves a significant advantage compared to GRPO with probability mask. This indicates that introducing the segment advantage value is crucial for achieving better performance.

Thanks for your valuable and constructive comments. Below, we provide detailed responses to the concerns and questions you have raised.

Q1: Note on intro: PPO can be implemented using shared backbone for actor and critic, so the requirement for a separate critic model in Line 40 isn’t accurate.

Thanks for pointing out this issue. We will change the statement in Line 40 from "Additionally, PPO requires maintaining a separate critic model, typically as large as the actor, which doubles the memory footprint and computational cost, making it less efficient for large-scale training" to “Additionally, PPO employs either a separate critic model or an additional critic head to predict value function, leading to extra memory and computation overhead”.

Q2: All experiments are performed on mathematical benchmarks—so it would be great to see experiments in non-math settings to see the generality of the methods.

Thank you for your insightful suggestion regarding the evaluation of our methods on non-mathematical benchmarks to assess their generality. Due to limited time and computational resources, we have not yet conducted experiments on other computationally heavy non-math tasks. We recognize the importance of verifying the general applicability of our approach and plan to include evaluations on non-mathematical tasks in our future work. We appreciate your suggestion and believe that extending our evaluation beyond mathematical tasks will further demonstrate the versatility and robustness of our method.

Q3: It would be great to have a longer discussion of limitations of the method—what are some settings where segment-splitting might not be as effective as having token-level advantages from PPO? Or where is value estimation too challenging and GRPO a superior option?

Thanks for the suggestions. We will discuss more limitations of our method in the future version as follows.

Our SPO framework provides a unified perspective that encompasses both GRPO (when segment length equals the entire response) and PPO (when segment length is set to 1). This design allows SPO to flexibly adapt to the characteristics of various tasks by tuning the segment granularity and advantage estimation method.

PPO better than SPO: PPO is particularly effective in environments where the agent frequently revisits similar or identical states during training. A classic example is traditional reinforcement learning tasks, such as playing a video game, where the environment resets and comparable states are encountered repeatedly. This frequent revisitation enables the critic model to learn and refine accurate predictions for the same or similar states, allowing for fine-grained, token-level feedback to guide learning. In such scenarios, fine-grained token-level supervision, as provided by PPO, is more suitable.

However, in scenarios like LLM-based mathematical problem solving, different prompts often lead to entirely different trajectory distributions. This means that the agent rarely sees similar states across examples. Consequently, the critic model cannot reliably predict value estimates for states it seldom encounters, which reduces PPO's effectiveness. In these cases, critic-free approaches like GRPO or SPO may be more effective.

GRPO better than SPO: For very short responses, further segmenting can result in segments containing only a few tokens, where the value at the start and end of each segment may be essentially the same. This can lead to unnecessary splitting and introduce extra computational overhead for advantage estimation. In such cases, the simplicity of GRPO, which relies solely on the overall reward, leads to better computational efficiency.