Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models
Authors: Yiran Guo
Lijie Xu
Jie Liu
Ye Dan
Shuang Qiu
Venue: NeurIPS 2025 poster ()
Keywords: LLM
Deep Learning
Reinforcement Learning
Primary area: deep_learning

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 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.

Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models
Yiran Guot, Lijie Xul: Jie Liu"*, Dan Yel, Shuang Qiu
Institute of Software, Chinese Academy of Sciences
University of Chinese Academy of Sciences CCity University of Hong Kong
{guoyiran23, xulijie, 1jie, yedan)@otcaixz meaxx.sscas iscas ac. shuanqiu@ci tyu edu.hk
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 fine-grained advantage signals but suffer from inaccurate estimation due 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 an intermediate granularity, achieving 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 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 novel probability-mast mask strategy. We further instantiate SPO for two specific scenarios: (1) SPO-chain for short chain-oftthought (CoT), featuring novel cutpoint-base basedd partition and chain-based ad advantage estimation, achieving 6-12 percentage point improvements in accuracy over PPO and GRPO on GSMSK. (2) SPO-tree for long COТ, featuring novel tree-based advantage estimation, which significantly reduces the cost of MC estimation, achieving 7-11 percentage point improvements over GRPO MATH500 under 2K and 4K context evaluation. We make code publicly available at https: /tttps:///ithie giggthu..... com/ AlFrameReseercch/PP0
1 Introduction
Reinforcement learning (RL) has become the cornerstone for training state-of-the-art reasoning large language models (LLMs), such OpenAI ol [11]. DeepSeek R1 [7], Kimi K1.5 [31], and Qwen3 [34]. These models demonstrate RL's unique ability to cultivate advanced reasoning capa- bilities, particularly complex, -TeMerellaed tasks. However, achieving both effectiveness and efficiency in RL training hinges on addressing fundamental challenge: credit assignment, i.e. accurately attributing success or failure to individual actions within sequence [30]. In the context of LLMs, where actions correspond to generated tokens, this challenge is even greater due to sparse and delayed rewards that are typically only available at the end the response. Advantage estimation is the common approach for credit assignment in RL, and existing methods differ in the granularity of advantage estimation, typically operating at two extremes, each with its own limitations.
Corresponding Authors. Lijie Xu, Jie Liu, and Dan Ye are also affiliated with Key Laboratory of System Software (Chinese Academy of Sciences) and University of Chinese Academy of Sciences, Nanjing.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Fine- -reenerrindd token-level methods like Proximal Policy Optimization (PPO) [26] use critic model to estimate advantages for each token. However, accurately predicting state values poses a particular challenge in L.LM training, due to the significant variability among states conditioned on different prompts and the limited per-prompt data to effectively train the critic model. Empirical findings by (12) provide extensive evidence that this difficulty causes the critic model to produce unreliable value predictions, leading to suboptimal credit assignment in practice. Additionally, PPO employs either separate critic model or an additional critic head to predict the value function, leading to extra memory and computation overhead. At the other extreme, coarse-graine granned trajectory-level methods such as Group Relative Policy Optimization (GRPO) [28] bypass the critic model and compute single advantage for the entire generated sequence based solely on the final outcome. While this approach is computationally efficient and unbiased, it leads to imprecise credit assignment over long sequences [12]. Applying a single advantage signal to a large number of tokens makes it challenging for the model to identify which specific tokens contribute positively negatively, resulting in the model failing to reward partial progress or learning redundant solution paths [22]. Moreover, our ex experimental results, consistent with concurrent work [35], find that GRPO can rapidly overfit on a fixed training set, with the number of unique responses decreasing and the performance on the validation set saturating early (see Figure 8).
To overcome the limitations of both token-level and trajectory-level methods, we propose Segment Policy Optimization (SPO), novel RL framework focusing on mid mid-grained, segment-level advantuge estimation. Instead of assigning credit for each token or only at the end of a trajectory, SPO partitions the generated sequence into contiguous segments and estimates advantages at this intermediate gramu- larity. This segment-level estimation offers several key benefits: (1) Improved credit assignment: Segment-level feedback provides more localized information than trajectory- methods, allowing credit assignment to shorter segments. This finer granularity enables the model to reward partial progress even for ultimately unsuccessful responses and penalize redundancy or unnecessary portions within successful responses. (2) More accurate advantage estimation: Compared to token-level advantages, segment-level advantages involve fewer estimation points. This enables SPO to leverage effective Monte Carlo (MC) sampling, yielding accurate and unbiased advantage estimation directly from the policy, thus eliminating the need for an additional, unstable critic model. (3) Flexibility and adaptability: Our segment partition method can be arbitrarily defined without requiring semantic completeness, offering flexible adjustment of granularity from token-level trajectory-Ievel also making it adaptable to a wide range of tasks.
Our SPO framework contains three key components: (1) Flexible segment partition, (2) Segment advantage estimation via MC, and (3) Policy optimization using segment advantages. This modular design allows for various strategies to be implemented within each component, making the framework highly adaptable to different tasks and scenarios. We further instantiate SPO with two specialized instances tailored for different reasoning scenarios. For short chain-of offtthuttt (CoT), we introduce SPO-chain, which employs a cutpoint- based segment partition strategy and chain- based segment advantage estimation. For long CoT, we introduce SPO-tree, featuring a novel tree-based segment advantage estimation strategy specifically designed to significantly improve MC sampling efficiency. Additionally, we propose a novel probability-oe
optimization strategy that selectively compute the loss for key tokens instead of all tokens within a segment, which can be applied to either SPO-chain or SPO-tree further enhance credit assignment. Our experimental evaluations demonstrate the effectiveness of the SPO framework and its specialized instantiation. For short COT, SPO-chain achieves 6-12 percentage point accuracy improvements over PPO and GRPO on GSMSK. For long COT, SPO-tree achieves 7-11 percentage point accuracy improvements over GRPO on MATH500 under 2K and 4K context evaluation. Our major contributions are summarized as follows:
1. We propose Segment Policy Optimization (SPO), a novel segment-level RL training frame- work for LLMs. SPO introduces mid mid-grained advantage estimation to overcome the limita- tions of token-level and trajectory-level methods, and features a modular architecture.
2. We introduce several novel techniques integrated within the SPO framework, including cutpoint-basee segment partition, tree-based segment advantage estimation, and a policy optimization strategy utilizing probability masks.
3. Building on the proposed SPO framework, we introduce two specialized instantiations: SPO-chain and SPO-tree, for short and long CoT scenarios. respectively, and demonstrate their effectiveness through extensive experiments on mathematical reasoning benchmarks, GSM8K and MATH.
2

---

2 Background
Language Generation as an MDP. Language generation tasks can be modeled as a Markov Decision Process (MDP) defined by tuple (S, A. P. R), where S is the state space, A is the action space, P represents transition dynamics, and R the reward function. Specifically, at each time step i, the state 8, E S consists of the prompt tokens a along with previously generated tokens yet = -....... Ut- 1)- that is, 5t = x. y= The action a; E A corresponds to selecting the next token yt. The decision- making process follows policy To( (s)) parameterized by 0, which defines the probability of the next token conditioned on the current state. The transition dynamics IP are deterministic: given state & and action (token) az. the next state S1+1 is obtained by concatenating the selected token to the current state: 8t+1 = (s; ae) = [s,, an]. The reward function assigns 0 intermediate rewards, providing only sparse binary reward R(x, y 1 or 0 at episode termination, where y [y1. 1/2 ................................ yr] is the full generated response, indicating whether the generated response matches the ground truth or not. The value function ((s) represents the expected cumulative reward from state s. The state-action value function ((s, a) corresponds to the expected cumulative reward from choosing action a at state
The advantage function A a), defined as Q(s. a) V(s), measures the improvement in expected reward realized by taking an action at state s. Under deterministic transition dynamics and sparse binary rewards, the advantage function simplifies A(s, a) V(s') (ss,, where s' =P((s, a) is the next state reached deterministically from state & after taking action a.
RL for LLMs. PPO [26, 21] and GRPO [28] are two widely adopted reinforcement learning algorithms for optimizing large language models. PPO introduces a clipped surrogate objective to stabilize training by constraining policy updates near the previous policy:
|
min clip)r)) -,,11))),,)+),)))
(O) = BE D.
you (:1ze)
(I)
where r0) is defined as updates. PPO estimates token-level advantages A, via GAE [25], requiring a critic model to predict token-level values. Compared to PPO, GRPO eliminates the need for the critic model and instead estimates the trajectory-level advantages by normalizing each response's 's reward within the sampled group. These trajectory-level advantages are then assigned uniformly to all tokens in the correspond- ing trajectory obtain Á. Similar PPO, GRPO adopts clipped objective, together with directly imposed KI. penalty term. Recent work [12] highlights that accurately training the critic in PPO is challenging, and proposes VinePPO, critic-free alternative that partitions the reasoning trajectory into discrete steps using heuristic rules (e.g., line breaks) and estimates step-level advantages through Monte Carlo (MC).
no (a(el)))) Resu (s.) and is small hyperparameter that limits excessively large
Compared to VinePPO, our proposed segment-level framework, SPO, adopts a more general concept of segmentation, allowing arbitrary partitions without enforcing semantic coherence. This enables us to freely adjust the granularity anywhere between token-level and trajectory- and also facilitates adaptation broader and less structured tasks such as code generation. Moreover, we introduce a novel tree-based sampling method, where segment advantages are estimated concurrently with trajectory generation. This obviates the need for VinePPO's costly resampling to estimate advantages, thereby substantially improving efficiency and making our approach effective in long CoT scenarios. Notably, VinePPO can be viewed as a special case within our more general SPO framework. More related work is provided in Appendix A.
3 Segment Policy Optimization
In this section, we introduce our segment policy optimization (SPO) framework. Effective credit assignment is crucial for training LLMs in reasoning tasks. Trajectory-level methods such GRPO rely solely on sparse final rewards, making credit assignment challenging. Token-level methods like PPO heavily depend on the critic model, whose value estimation is often inaccurate. The SPO framework aims to balance these extremes by operating at the segment granularity, enabling richer feedback signals compared to GRPO and allowing more accurate Monte Carlo estimates of segment-level advantages, thereby bypassing the need for a critic model.
We develop the SPO framework guided by the following three challenging problems: (1) How to partition the generated sequence into multiple segments? (2) How to accurately and efficiently estimate the advantage for each segment? (3) How to update the policy by using the segment-level
3

---

Flextble Segment Parttton
Segment
Porstion
Segment
Fortiton
Segment 4
Reward
Prompt (Questio))
89
72
1.00
0.85
1000
0.92
0.11
or
Siegment Advensage As
Segmeent 2 Advantage As
Siegment Advanitgg At
Policy Optimizatio Using Segisent.Advantage Advantages
0.99
Token with high probability 0.99 (Noemal tobon)
0.72
Taken with low probabiitty 0.72 (Culpoint Key point)
2: Accurate Segment
Segment..dvvnttg Advantage Estimation
Figure 1: Overview of SPO framework. Our framework consists three components: segment partition, segment advantage estimation, and policy optimization, each of which can be implemented in different ways. This figure illustrates the cutpoint-base partition strategy used SPO-chain, where partitioning occurs after predetermined number of cutpoints. It also illustrates our probability- mask policy optimization method, which assigns the corresponding segment advantages specifically to the cutpoints instead of all tokens within segment.
(a) Chain-based
Prompt (Quserion)
Burples ag. +(] y!!
Tree-based
Prompt [Question)
[Ch(n)]
(A..)
Compute segment advantage A(s) 1
V(Pa(n)) - (1+ 01/3
Compute segmant advantage
(e..) V(..))
((a.))
Seamont Group
Q
segmant tokens
O+
6 1
Segment Group
Sogment Group
Segment Group 3
Figure 2: (a) Chain based advantage estimation method. For each segment, we independently sample N trajectories to estimate value V. The advantage for segment A: is estimated as (st..r) (s (b) brsed advantage estimation method. Trajectories nodes sharing the same parent form a group with identical prompts and token counts (except for leaf nodes, whose token lengths may vary). This hierarchical organization facilitates the calculation of advantages within each group.
organized in tree structure, where
advantage? The proposed SPO framework, illustrated in Figure 1, adopts modular architecture, where each of its components can be implemented using various strategies, allowing the framework to be tailored diverse tasks and scenarios. In what follows, introduce three key components of SPO to answer the above questions and further instantiate SPO with two instances, tailored for short and long CoT scenarios.
(1) Flexible Segment Partition. A segment is defined as a contiguous sequence of generated tokens, denoted as seg, [Mt Mi, +1...... .tt...................... [1-1] k-th segment. Formally, given full generated trajectory y = [3/1- ./..... Mrl. | the partition can be expressed y 1/,, ................................ yrl [seg, seg2 seg J. The SPO framework supports arbitrary partition strategies, allowing flexible definition of segment boundaries, without requiring semantic completeness. This flexibility enables us choose partition granularity between token-level and trajectory-level, allowing a trade-off between computational cost and credit assignment. In this work, consider two main partition strategies, designed for different scenarios: (a) Fixed Token Count Partition: straightforward strategy that divides the sequence into segments of a predetermined fixed number of tokens. (b) Adaptive Cutpoint-basse Partition: An advanced strategy (see Section 4) that defines segments by accumulating fixed number of low probability tokens (i.e., tokens whose probabilities Te (ve (st) less than a threshold p). This strategy places segment boundaries at positions where V values are more likely to change, avoiding the issue in the fixed token count partition strategy where V values may remain unchanged between segment boundaries when each segment is short.
where 4g is the starting token index of the
(2) Segment Advantage Estimation via Monte Carlo. After obtaining each segment segı [yt,, Ul,+1, Mo---11), we define the segment advantage the following way:
A ((5t2.) V(s..) V( .e........ ..gg.,,,,,,s.)) V V[x seg...... scga-1)). (2)

---

which measures the incremental improvement in expected reward resulting from generating the tokens in segg- The core challenge lies in accurately estimating the value function (s)). A common approach is to train a critic model. However, in the L.M scenario, critic-based methods struggle to produce accurate state-value estimates due to large variations across prompts and limited trajectory data per prompt, as empirically illustrated by [12]. Given these considerations, we propose to bypass the critic entirely and instead adopt Monte Carlo (MC) estimation to compute unbiased estimates of segment values directly from sampled trajectories. While high variance is often a concern with MC estimation, in the LLM setting, rewards are typically sparse and binary, significantly mitigating the variance issue. Specifically, most 0.25. We find that the accuracy obtained with a small number of samples (N = or N = 9) is sufficient for effective policy optimization. Our SPO framework supports various MC sampling strategies: (a) Chain-based Advantage Estimation: Independently roll out N trajectories from state s, and estimate V($) as the average reward of these trajectories, further yielding the estimation of the advantage A% following Equation (2). (b) Tree-based Advantage Estimation: An advanced strategy of advantage estimation for improved sample efficiency (see details in Section 5). Unlike the chain-based advantage estimation, which discards MC samples after estimating the V values, this strategy organizes MC samples into tree structure and computes the V values via bottom-up aggregation of rewards along the tree. Nodes sharing the same parent have identical prompts and token counts, forming segment groups, enabling advantage computations within each group. This tree structure allows the reuse of MC samples for policy optimization, significantly enhancing sample efficiency in the long CoT scenario.
can view V as Bernuuli variable, and the MC variance is at
(3) Policy Optimization Using Segment Advantages. Given a set of generated segments (segs) and their corresponding advantages {A*'), ), now focus effectively leveraging training samples to update the policy Ty. Specifically, we can adapt various policy optimization approaches into our SPO framework: (a) Policy Gradient: We can assign A all tokens contained within the k-th segment Masks: An improved version of policy gradient (see details in Section 4), incorporating probability masks. Instead of uniformly assigning A% to all tokens within the segment, this strategy exclusively assigns A% only to low- probabiibiit tokens, based on the intuition that these tokens primarily contribute to the segment's 's ad advantage. This refined approach further enhances the credit assignment to critical tokens; (c) Other Strategies: Our framework can also be adapted to other policy optimization methods such as policy iteration- approach (see discussions in Appendix B) and potentially GFlowNet-based optimization [2].
seg,, and then optimize using the PPO loss; (b) Policy Gradient with
SPO-Chain for Short CoT
For short Shain-of-Thouugh (CoT) scenarios, where the computational overhead of MC sampling is low and segments typically involve a small number of tokens, we designed a tailored instance of SPO by taking into account these characteristics, which we refer to as SPO-chain. The core features of SPO-chain lie in its cutpoint- based segment partition, chain- segment advantage estimation, and policy optimization via policy gradient with probability masks.
(1) Adaptive Cutpoint-based Segment Partition.
The fixed token count partition strategy faces a critical issue in short CoT scenarios that the number of tokens in each segment is not very large. If the token probabilities To (yı (s:) within a segment are high (close to 1), the V values estimated at the beginning and end of the segment will not differ significantly. This can lead to unnecessary partitioning, ultimately resulting in a waste of sampling budget. To address this, we propose an adaptive cutpoint-based partition strategy. Specifically, we first identify the culpoints, defined as positions where token probabilities drop below a pre-defined threshold p. so that we have the set of all cutpoints defined as U4 = {t < T The (s) < p}. These cutpoints represent positions where the model's 's reasoning trajectory could diverge, thus potentially inducing changes in V values. For better credit assignment, we prefer each segment to contain fewer cutpoints. Then, given a fixed segment count K, we find a partition that reflects this principle by solving the following optimization problem: min K E [M4 n [4,, 12. It can be shown that the optimal solution evenly distributes cutpoints across segments (assuming [Mte] is divisible by K for simplicity), that is,
U4 n [L,, 4++1)
Vk K K
K
which corresponds to partitioning the trajectory such that each segment contains the same number of cutpoints, shown in Figure 1. A practical example is provided in Appendix I. Our experiments
5

---

further show that this partition strategy would lead to superior performance (see our comparison of different segment partition strategies Section 6).
(2) Chain-based Segment Advantage Estimation. In the short CoT scenario, the computational overhead of MC estimation is generally manageable. Thus, adopt simple, chain-based MC sampling approach as shown in Figure 2(a). Specifically, at each segment boundary state Sty = (x. you. we independently sample N trajectories from the policy Te. i.e. TI6 TTy(1(s))) J,j I.....N NV and then estimate the value of such a state by averaging the returns from these sampled trajectories, i.e., (ss..
Σソ= R(z, - 1/- The estimated advantage At of each segment k is computed by taking the difference between the state values at consecutive segment boundaries ATte (5 (s...) following Equation (2).
(3) Policy Gradient with BookenProobabilit, Masks. Policy gradient methods have become main- stream for training LLMs using RL. Accordingly, we adopt policy gradient-based approach to optimize the policy. For example, once we have computed the segment advantage A% we can assign it to all tokens within the segment and obtain the token-level advantage A,, then adopt the PPO loss in Equation (1) to optimize the policy. However, since the changes V values between segments are primarily caused by tokens at cutpoints, we assign the segment advantage A only to these critical tokens. Formally, our policy is trained by minimizing the following loss:
Jehainn (0) = EwEDD (egg..
K
(3)
Σ
Mr min (re(0)A7% 1 ee) - (Tel(TTT) Teer)
k=1 t=
where M, the token probability mask whose value is if ( (s)) < - and 0 otherwise, i.c.. M,- : [TTow=a(a (ar(st) (st) p)) In addition, Z is normalization term that equals the total number of tokens where the mask M, is 1: Z = Σ M,. This approach further enhances credit assignment within each segment by concentrating the advantage signals on fewer critical tokens. Our experiments demonstrate that this method improves the accuracy (refer to our ablation study on the probability- mask optimization strategy in Section 6).
5 SPO-Tree for Long CoT
For long Chain-of-Thought (CoT) scenarios, where the sampling cost of chain-based MC estimation in SPO-chain becomes prohibitively high, we propose novel tree-based segment advantage estimation method. This approach drastically reduces sampling overhead, making it feasible to apply our framework effectively in long CoT settings. We refer to this instantiation of our SPO framework as SPO-tree. In particular, SPO-tree features the fixed token count partition, tree-based segment advantage estimation, and policy gradient with probability masks.
(1) Fixed Token Count Segment Partition. In long CoT scenarios, each segment typically contains large number of tokens. As result, it is unlikely that all token transitions within entire segment will have probabilities close to 1. Thus, we employ a partition strategy where segment boundaries made at fixed token intervals, which allows us to generate segments with equal token count, supporting our tree-based segment advantage estimation method proposed in the following subsection.
(2) Trsed Segment Advantage Estimation. The core drawback of the chain-based segment advantage estimation strategy studied in Section 4 that it discards samples used for estimating the values (c.g. (1), T2)) 7(3) in Figure 2(a)), leading to substantial waste of samples in scenarios involving long reasoning trajectories. To address this issue, we propose a tree-based segment advantage estimation strategy, which reuses the samples employed for value estimation in policy optimization, significantly improving the sample efficiency.
As illustrated in Figure 2(b), model the trajectory sampling process (n) as the full history sequence corresponding to node n, including the initial prompt æ and all tokens generated along the path from the root node to node n. Each node n represents a segment seg(n), which is generated by extending the sequence of its parent node, Pa(n). with M newly sampled tokens, i.e.,
structure. We define
seg(n) [8/ (1))
..... JW
=² ~ x hist(Pa(n)), v2))) 2
6

---

Each node n generates set of child nodes, denoted as Ch(n). and has set of siblings, denoted as Sib(n). Nodes among siblings share the same prompts and sequence lengths (except for leaf nodes), ensuring fair comparison under the same token budget. The value of the state represented by node denoted as V(n), which can be estimated recursively from leaves root as follows:
R(xx, hist(n)), Ch(m)] En Ecre) (nn),
if is a leaf node otherwise
((n)=
We denote the advantage of the segment represented by node n as A(n). The estimated advantage A(n) for node n, relative to siblings, computed either in unnormalized or normalized form as:
(n) - mean, m'aan''Sib(r)) (n')
Á(n) (n) meatn/)
(n')
rediie) V (n')
More details about the tree construction are presented in Appendix E. In contrast to the chain-based segment advantage estimation strategy, each node (segment) in the tree can be used training example, substantially improving sample efficiency. In addition, due to extensive node-sharing among trajectories, the actual number of tokens we need sample is significantly less than the sum of tokens across all trajectories, greatly reducing sampling overhead. Within each training iteration, sampling a large number of trajectories from single question can lead the model overfitting to specific samples. To address this, we introduce a replay buffer mechanism that distributes sampled trajectories across multiple iterations in Appendix D.
The width of the tree determines the number of sibling nodes in each group, with a larger width providing more nodes for comparison and thus more nuanced advantage estimates. The depth of the tree controls the granularity of partitions; deeper trees yield finer-grane imer-grained signals. Furthermore, the hierarchical tree structure naturally aligns with the varying uncertainty along the reasoning trajectory. Earlier segments (closer to the root), which have higher uncertainty, aggregate more samples for estimating their V values, while later segments (closer to the leaves), which more certain, aggregate fewer samples.
Masks. To focus model training on segments with discriminative signals, we extract segments with non-zero advantages from the tree for training. We also note that such filtering of non-zero advantage samples aligns with practices in several concurrent works [35, 15]. Thus, we propose to minimize TsPo below for policy optimization:
(3) Policy Gradient with Token-Probablle
seg(n))
Jrree (8) Ex tree Pa
Σ
n(tr
Mas min (0),(())(())
- 1,, - -BDr (Tol (To
where Mn, is the token aaken-probabiling mask whose value is 1 if No (v)" [hist(Pa(n)) ( < and 0 otherwise, i.e., Mn.t := ((To(v(") [hist(Pa(n)), (m]) < p). The ratio term Tn. (0)
(n)
v
I [hist(Pa((a)) 201 and the normalization term Z given by Z Te (v) (aa))
then defined
EngTree: A(n)y Σ
sog(n)] Mn.t-
Experiments on SPO-chain
Experimental Setups. We evaluate SPO-chain with the RhoMath I.IB model [14] on the GSM8K dataset [5] using @ass@1 (accuracy) our primary evaluation metric. Following [12], we first finetune the base model on the GSM8K training set, and then use the obtained SFT model for subsequent RL training. We compare against baseline methods including RestEM, DPO, PPO, GRPO, RLOO, and VinePPO. The experimental hyperparameters largely follow [12], with detailed settings provided in Appendix H. For SPO-chain, we set the number of MC samples to N = 9 and partitioned the model output intervals of every 5 cutpoints, which is referred to as SPO-chain (int5). We also evaluate our SPO-tree method in the short CoT scenario. We adopt a 6-6-6 tree structure, meaning
7

---

(a) GSMBK Text Accuracy (RhoMath 1.1B)
Epicodo Genuration Time (4)
(b) Episode Gomeration Time on GSMBK
(c) Validation Accuracy on GSMBK
Validation Accuracy (%)
56.4
36.7
1259
VinoPOO
70-
6G-
534
SPO chain (int5)
50
1003
66-
46
42.8
Test
40
SPO-chwin (imt5)
250
SFt
Ser dlains mres Sameenn
00000
50
10
20
60
Step
Hour
Figure 3: (a) Test accuracy comparison of different methods on GSM8K. Baseline results are from
[12]. (b) Episode generation time comparison between SPO-chain (int5) and VinePPO during training.
(c) Validation accuracy of SPO-chain (int5) and GRPO during training.
(a) Partition Granularity Variations
(b) Partition Strategy Variations
(c) Probsbility Mask Strategy Ablation
Validation Accuracy (%)
70-
Test Accuracy (%)
Test Accuracy (%)
35
65-
50
50
$5
SPO-chain.uee Jint).
60-
SPO chain (int2)
SPO-chuin (imt5)
SPO-chain (int5) (ne prub-makk)
SPO- chain (int5)
45
VisePPO
10
GRPO
65-
SPO-chain (int100)
Fixed token
GRPO (with prob-mask)
40
80
200
600
200
600
Hour
Iteration
Iteration
Figure 4: (a) Variations of segment partition granularity (different cutpoint intervals). (b) Variations of segment partition strategies. (c) Ablation on probability-mad -makk policy optimization strategy.
the tree consists of three layers and each internal node expands into six child nodes, which is referred to as SPO-tree (6-6-6). For the first two layers, we segment the model output every 30 tokens, while for the final layer, we let the model complete the entire reasoning trajectory.
Comparison with Baseline Methods. As shown in Figure 3(a), our method, SPO-chain (int5), achieves the highest accuracy on the GSM8K test set, outperforming PPO and GRPO by 6-12 percentage points. Furthermore, compared to VinePPO, our method not only delivers higher accuracy but also requires less time for episode generation, as demonstrated in Figure 3(b). This is due to our SPO-chain (int5) method uses fewer advantage estimation points per trajectory compared to VinePPO. Additionally, our SPO-tree (6-6-6) method achieves the second- -iighst accuracy the GSM8K test set, validating its effectivencss and making it an efficient alternative. We also compared our method with GRPO in terms of validation performance under the same wall-clock time? (Figure 3(c)). The results show that our algorithm significantly outperforms GRPO and ultimately converges to a much better solution. We further conduct experiments with additional models, including MeepSeekMath 7B [28), Qwen base and instruct models [34], as well as on the non-matinn non-mathematical Knights-ande aaahhts-and-kee nnvess dataset [33]. The detailed results of these experiments are presented in Appendix F.
Impact of Segmentation Granularity. To investigate how the segment granularity affects model performance, we conducted experiments using various segment intervals, as shown in 4(a). When comparing validation accuracy under the same wall-clock time, interval 5 achieves the highest performance, followed by interval 2, while interval 100 performs the worst. In terms of final accuracy, interval 2 slightly surpasses interval 5, whereas interval 100 lags significantly behind both. These results indicate that a moderate interval (e.g., 5) provides more favorable trade-off, yielding better accuracy given the same training time, while excessively fine-grained intervals (e.g., 2) bring only marginal improvements and overly coarse intervals severely harm the accuracy. This supports the design of our segment-level advantage method, which strikes an effective balance between efficiency and accuracy, achieving substantially better performance than trajectory-Ievel advantage without the high computational cost of token-level estimation.
Comparison of Different Segment Partition Strategies. We compare different trajectory partition methods, including the naive fixed token count partition, the heuristic rules (c.g. line breaks) for partitioning in Vin,PPO, and the cutpoint-based segment partition in SPO-chain. The results are presented in Figure 4(b). For the naive fixed token count partitioning method, we explicitly set each trajectory's segment count at 3, making it higher than the total sampling budget of the SPO-chain
'Evaluation time is also included in the reported wall-clock time. The model is evaluated every 10 iterations.
8

---

(int5). Remarkably, despite having the smallest sampling budget, SPO-chain (int5) achieves the best test accuracy, validating the effectiveness of our cutpoint-bast based segment partition strategy.
Ablation Study on Probability-Mask Optimization Strategy. We conduct an ablation study on our proposed probability-mast optimization technique. As shown in Figure 4(c), removing the probability-mast technique leads to a decreased accuracy for SPO-chain (int5), from 56.7% to 55.0%. Surprisingly, applying the probability mask technique to GRPO results in significant improvement, boosting its accuracy from 45.7%* to 53.6%. We hypothesize that employing the probability- technique enables more precise credit assignment to tokens that are most likely to influence the model's 's reasoning trajectory. Meanwhile, the losses associated with tokens whose probabilities are close to 1 are masked out and thus excluded from the overall loss function, which potentially helps reduce overfitting.
7 Experiments on SPO-tree
Experimental Setups. To evaluate our method in long CoT scenario, we utilize DeepSeck-RI-Distil Qwen-1.50 model as our base model, which has been fine-tuned on huge amount of long CoT data, demonstrating complex reasoning strategies and typically generating long outputs. Given the strong capability of these models, we select the competition-leve MATH [10] dataset for our training and evaluation. We mainly focus on comparing our proposed SPO-uree method against GRPO, as GRPO is the mainstream training approach adopted for reasoning models, particularly favored for long CoT scenarios due its efficiency. We do not compare with VinePPO because its efficiency issue, making it impractical to apply in long CoT settings. For our SPO-tree method, the structure remains identical to the SPO-tree used in the short CoT scenario, as described in Section Detailed hyyer-paramette can be found in Appendix H.
Comparison with Baseline Methods. We initially limit the training context window size to 2K and evaluate model accuracy (Pass @ 1) on MATH500 every 10 iterations. For evaluation, we follow the implementation provided by [12], setting the evaluation context window also to 2K and using greedy decoding (temperature 0). Figure 5(a) shows the training curves of SPO-tree, vanilla GRPO, and GRPO with probability mask. We observe that GRPO with probability-mad
outperforms vanilla GRPO to some extent, demonstrating the effectiveness of this technique in long CoT scenarios. However, SPO-tree still achieves significantly higher accuracy under the same wall-clock time. This validates the effectiveness of SPO-tree and highlights that introducing segment advantage values is crucial for achieving better performance.
To further assess our method, we continue training from the 2K checkpoint and expand the model's context length to 4K. The corresponding model performance is presented in Table 1. We adopt the evaluation script provided by [8] to conduct evaluation on the obtained model checkpoints. As shown in the results, the SPO-tree consistently outperforms GRPO across all context sizes and achieves superior performance under 2K and 4K contexts, which are the context lengths it was trained on. We hypothesize that our segment-level advantage method significantly increases token efficiency due to more precise credit assignment, enabling the model to arrive at correct answers more straightforwardly (see Appendix J). This improvement leads to considerably better performance under limited context sizes. Interestingly, even though our model is trained under context windows up to 4K, it still achieves improved performance under 32K context evaluation, surpassing the base model. We also compared our approach against the most recent works, including DeepScaleR [18] and STILLL33 [4], both of which were trained on DeepSeek-RP R --ii--ttlll-ee -Dissill--wen--1.... STILL-33 adopted larger training datasets and extended context windows for training. Specifically, DeepScaleR progressively increased the context length from 8K to 16K and finally to 24K, whereas our training scales only from 2K to 4K. While DeepScaleR performs best at 32K, we observe the opposite trend in lower-context settings, where DeepSCaleR exhibits the worst performance at 2K and 4K. This finding suggests that GRPO- based training might not optimize token efficiency, potentially leading to redundancy in the generated outputs, and thus negatively affecting the model's 's performance when evaluated under limited context size.
using GRPO. Notably, DeepScaleR and
'Our GRPO implementation achieves slightly higher test accuracy (45.7%) compared to the 44.6% reported in [12].

---

MATH500 Accuracy (%6
(a) MATH500 Accuncy vs. Hour
(b) Tree: Structure Variations
(c) Advantage Method Variations
75
Text Accuracy (%6
00-
Accuracy (%)
20-
30
50-
65-
SPD-trew (6-6-)
-0-
SPO-tree (4-4-4)
45
GRPO
SPO 6.6)
SPO tree w/o
55-
GRPO (with mask)
60-
SPO-tres tree (8-8-8)
SPO-trex (6-6 (--6-) w/ std. norm.
10
100
200
300
800
500
Hour
Iteration
Figure 5: (a) Comparison of SPO-tree (6-6-6) and GRPO on MATH500 with context size of 2K. (b)
Variations of tree structures on GSM8K. (c) SPO-tree with different advantage methods on GSM8K.
Dataset
Eval Context Size
Base
GRPO
SPO-tree
DeepScaleR
STILL-3'
2K
0.566
0.62
0.736
0.538
0.662
MATH500
4K
0.74
0.752
0.828
0.744
0.794
32K
0.838
0.84
0.848
0.878
0.846
2K
0.067
0.033
0.1
0
0.067
AIME24
4K
0.167
0.2
0.2
0.167
0.133
32K
0.267
0.333
0.333
0.333
0.233
These models were trained using larger datasets and longer context windows. Specifically, DeepScaleR uses 1K-+16K-2444 context and STILL-3 sets ggnneaat__mat man__enaaeen to 29000 during training. while our GRPO and SPO-tree use maximum context of 4K during training.
Table 1: Accuracy comparison among methods with various context sizes on MATH500 and AIME24.
Comparison Different Tree Structures and Advantage Computation Methods. To investigate the impact of different tree structures, compared the performance of various tree structures (4-4-4, 6-6-6, 8-8-8) on the GSM8K test set (Figure 5(b)). When using a larger tree structure, each iteration generates a greater number of segments with non-zero advantage. Therefore, Laaieesspr__it_e iteration" for different tree structures: specifically, we set it to 1024 for SPO-tree (8-8-8), 512 for SPO-tred (6-6-6), and 384 for SPO-tree (4-4-4). We found that the performance differences among these tree structures were not substantial under the same wall-clock time, indicating the robustness of the tree structure. Smaller tree structures achieve higher accuracy initially. possibly because they can process more data examples within the same time frame. However, larger tree structures eventually outperform smaller ones at later training stages, they enable more accurate value estimation and benefit from having more segments within each group, leading to more reliable and nuanced advantage estimates. We also compared the performance of different advantage calculation methods with and without standard deviation normalization. As shown in Figure 5(c), both methods perform similarly, while the variant without normalization performs slightly better.
set different values
of the hyperparameter "num_ ciimm__ppode_______
Conclusion
In this work, we propose Segment Policy Optimization (SPO), novel RL training framework for large language models (LLMs) that effectively addresses the limitations of existing RL approaches. SPO provides feedback at the segment level, offering finer granularity than trajectory-level methods for more precise credit assignment, while reducing the number of advantage estimation points compared to token-level approaches. This enables us to leverage Monte Carlo methods to obtain unbiased advantage estimates. Our experiments demonstrate that small number of segment-level advantages can significantly outperform coarse trajectory-lever advantages, validating the effectiveness of our framework. Due to limited computational resources, our current experiments in the long CoT scenario are limited to a maximum context size of 4K tokens. the future, we plan to conduct additional experiments with larger context sizes. Additionally, our current experiments focus primarily on mathematical tasks. We plan to test the effectiveness of SPO in broader application scenarios, such as code generation and RLHF
'Evaluation time is also included in the reported wall-clock time. The model is evaluated every 10 iterations.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the Major Project of ISCAS (ISCAS-ZD-202302) the National Natural Science Foundation of China (Grant No. 42361 144884), and the General Research Fund (GRF 16209124). We would like to thank MiraclePlus for providing the computational resources. The authors declare no competing interests.
References
[1] A. Ahmadian, C. Cremer, M. Gallé, M. Fadace, J. Kreutzer, O. Pietquin, A. Üstün, and S. Hooker. Back basics: Revisiting reinforce-style optimization for learning from human feedback in Ilms. In L. Ku, A. Martins, and V. Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), ACL 2024, Bangkok, Association for Computational Linguisties,
Thailand, August 11-16, 2024, pages 2024.
[2] B. R. Bartoldson, S. Venkatraman, J. Diffenderfer, M. Jain, T. Ben-Nun, S. Lee, M. Kim, J. Obando-Cenna Y. Bengio, and B. Kailkhura. Trajectory balance with asynchrony: Decoupling exploration and learning for fast, scalable IIm post-training. CoRR, abs/2503. 189299 2025.
[3] G. Chen, M. Liao, C. Li, and K. Fan. Alphamath almost zero: Process supervision without process. In A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver. BC, Canada, December 10- 15, 2024, 2024.
[4] Z. Chen, Y. Min, B. Zhang, J. Chen, J. Jiang, D. Cheng, W. X. Zhao, Z. Liu, X. Miao, Y. Lu, L. Fang, Z. Wang, and J.-R. Wen. An empirical study eliciting and improving rl-like reasoning models. arXiv preprini arXiv:2503. 04544, 2025.
[5] K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman. Training verifiers solve math word problems. CoRR, 10./2110.14166 2021.
[6] G. Cui, L. Yuan, Z. Wang, H. Wang, W. Li, B. He. Y. Fan, T. Yu, Q. Xu, W. Chen, J. Yuan, H. Chen, K. Zhang, X. Lv, S. Wang, Yao, Han, H. Peng. Y. Cheng, Z. Liu, M. Sun, B. Zhou, and N. Ding. Process reinforcement through implicit rewards. CoRR, abs/2502.01456, 2025.
[7] DeepSeek-AL D. Guo, D. Yang. H. Zhang, Song, R. Zhang, Xu, Q. 7hu, Ma, Wang, X. Bi, X. Zhang, X. Yu, Y. Wu, Z. F. Wu, Z. Gou, Z. Shao, Z. Li, Z. Gao, A. Liu, B. Xue, B. Wang, B. Wu, B. Feng, C. Lu, C. Zhao, C. Deng, C. Zhang, C. Ruan, D. Dai, D. Chen, D. Ji, E. Li, F. Lin, F. Dai, F. Luo, G. Hao, G. Chen, G. Li, H. Zhang, H. Bao, H. Xu, H. Wang,
H. Ding, H. Xin, H. Gao, H. Qu, H. Li, Guo, J. Li, Wang, Chen, J. Yuan, Qiu, J. Li,
L. Cai, J. Ni, J. Liang, J. Chen, K. Dong, K. Hu, K. Gao, K. Guan, K. Huang, K. Yu, L. Wang,
L. Zhang, L. Zhao, L. Wang. L. Zhang, L. Xu, L. Xia, M. Zhang, M. Zhang, M. Tang, M. Li,
M. Wang, M. Li, N. Tian, P. Huang, P. Zhang, Q. Wang. Q. Chen, Q. Du, R. Ge, R. Zhang, R. Pan, R. Wang, R. J. Chen, R. L. Jin, R. Chen, S. Lu, S. Zhou, S. Chen, S. Ye, S. Wang, S. Yu, S. Zhou, S. Pan, and S. S. Li. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. CORR, abs/2501. 12948, 2025.
[8] H. Face. Open rl: A fully open reproduction of deepseek-rl, January 2025.
[9] T. Foster and J. Foerster. Learning to reason at the frontier of learnability, CoRR, abs/2502.11272. 2025.
[10] D. Hendrycks, C. Burns, S. Kadavath, Arora, S. Basart, Tang, D. Song, and J. Steinhardt. Measuring mathematical problem solving with the math dataset. CoRR, abs/2103.03874, 2021.
[11] A. Jaech, A. Kalai, A. Lerer, A. Richardson, A. El-Kishky, A. Low, A. Helyar, A. Madry, A. Beu- tel, A. Carney, Iftimie, A. Karpenko, A. T. Passos, A. Neitz, A. Prokofiev, A. Wei, A. Tam, A. Bennett, A. Kumar, A. Saraiva, A. Vallone, A. Duberstein, A. Kondrich, A. Mishchenko.

---

A. Applebaum, A. Jiang, A. Nair, B. Zoph, B. Ghorbani, B. Rossen, B. Sokolowsky, B. Barak,
B. McGrew, B. Minaiev, B. Hao, Baker, B. Houghton, B. McKinzie, B. Eastman, C. Lugaresi.
C. Bassin, C. Hudson, C. M. Li, C. de Bourcy, C. Voss, C. Shen, C. Zhang, C. Koch, C. Orsinger,
Selsam, D. Dohan, D. Farhi, D. Mely, D. Robinson, D. Tsipras, D. Li, D. Oprica, E. Freeman, E. Zhang. E. Wong, E. Proehl, E. Cheung, E. Mitchell, E. Wallace, E. Ritter, E. Mays, F. Wang, F. P. Such, F. Raso, F. Leoni,
C. Hesse, C. Fischer, C. Chan, D. Roberts, D. Kappler, D. Levy,
F. Tsimpourlas, F. Song, F. von Lohmann, F. Sulit, G. Salmon, G. Parascandolo, G. Chabot, G. Zhao, G. Brockman, G. Leclerc, H. Salman, H. Bao, H. Sheng, H. Andrin, H. Bagherinezhad.
H. Ren, H. Lightman, H. W. Chung, I. Kivlichan, I. O' Connelll I. Osband, I. C. Gilaberte, and
I. Akkaya. Openai ol system card. CoRR, abs/2412.16720,, 2024.
[12] A. Kazemnejad, M. Aghajohari, E. Portelance, A. Sordoni, S. Reddy, A. C. Courville, and N. L. Roux. Vineppo: Unlocking RL potential for LLM reasoning through refined credit assignment. CoRR. abs/2410.01679, 2024.
[13] H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-1 2024. OpenReview.net, 2024.
[14] Z. Lin, Z. Gou, Y. Gong, X. Liu, Y. Shen, R. Xu, C. Lin, Y. Yang. J. Jiao, N. Duan, and W. Chen. Rho-1: Not all tokens are what you need. CoRR, abs/2404.07965, 2024.
[15] Z. Lin, M. Lin, Y. Xie, and Ji. Cppo: Accelerating the training of group relative policy optimization-based reasoning models. CoRR, abs/2503.22342, 2025.
[16] Z. Liu, C. Chen, W. Li, P. Qi, T. Pang. C. Du, S. Lee, and M. Lin. Understanding r1 -1-zero-like training: A critical perspective. CoRR, abs/2503. 207883, 2025.
[17] L. Luo, Y. Liu, R. Liu, S. Phatale, H. Lara, Y. Li, L. Shu, Y. Zhu, L. Meng, J. Sun, and A. Rastogi. Improve mathematical reasoning in language models by automated process supervision. CoRR, abs/2406.06592, 2024.
[18] M. Luo, S. Tan, J. Wong, X. Shi, W. Y. Tang. M. Roongta, C. Cai, J. Luo, L. E. Li, R. A. Popa, and I. Stoica. Deepscaler: Surpassing ol o1-preview with a 1.5b model by scaling rl. https://gtt thub. com/ wwwccoom/////eeeeeee htt////aaaaaa//aaaa BaaaaaaabaDeeesaalle... 2025.
[19] Q. Ma, H. Zhou, T. Liu, J. Yuan, P. Liu, Y. You, and H. Yang. Let's reward step by step: Step-level reward model as the navigators for reasoning. CoRR, abs/2310. 10080, 2023.
[20] M. Noukhovitch, S. Huang, S. Xhonneux, A. Hosseini, R. Agarwal, and A. Courville. Asynchronous rlhf: Faster and more efficient off-policy rl for language models. CoRR, abs/2410.18252, 2025.
[21] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, Schulman, Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. Christiano, J. Leike, and R. Lowe. Training language models to follow instructions with human feedback. CORR, abs/2203.00 020155,, 2022.
[22] Y. Qu, M. R. Yang, A. Setlur, L. Tunstall, E. E. Beeching, R. Salakhutdinov, and A. Kumar. Optimizing test-time compute via meta reinforcement fine-tuning. CoRR, abs/2503.00572. 2025.
[23] R. Rafailov, J. Hejna, R. Park, and C. Finn. From r to qº Your language model is secretly a q-function. CoRR, abs/2404.12333 2024.
[24] R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn. Direct preference optimization: Your language model is secretly a reward model. In A. Oh, Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
12

---

[25] J. Schulman, P. Moritz, S. Levine, M. I. Jordan, and P. Abbeel. High-dimensionn continuous control using generalized advantage estimation. In Y. Bengio and Y. LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Truck Proceedings, 2016.
[26] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.06347 2017.
[27] A. Setlur, C. Nagpal, A. Fisch, X. Geng, J. Eisenstein, R. Agarwal, A. Agarwal, J. Berant, and A. Kumar. Rewarding progress: Scaling automated process verifiers for Ilm reasoning. CoRR, abs/2410.081455 2024.
[28] Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song. M. Zhang, Y. Li, Y. Wu, and D. Guo. Deepseckmath: Pushing the limits of mathematical reasoning in open language models. CoRR, abs/2402.03300, 2024.
[29] A. Singh, D. Co-Reyes, R. Agarwal, A. Anand, P. Patil, X. Garcia, J. Liu, J. Harrison, J. Lee, K. Xu, A. T. Parisi, A. Kumar, A. A. Alemi, A. Rizkowsky, A. Nova, B. Adlam, B. Bohnet, G. F. Elsayed, H. Sedghi, I. Mordatch, I. Simpson, I. Gur, J. Snoek, J. Pennington, J. Hron, K. Kenealy, K. Swersky, K. Mahajan, L. Culp, L. Xiao, M. L. Bileschi, N. Constant, R. Novak, R. Liu, T. Warkentin, Y. Qian, Y. Bansal, E. Dyer, B. Neyshabur, J. Sohl-Dickstein, and N. Fiedel. Beyond human data: Scaling self-training for problem-solving with language models. Trans. Mach. Learn, Res., 2024, 2024.
[30] R. S. Sutton and A. G. Barto. Reinforcement learning an introduction. Adaptive computation and machine learning. MIT Press, 1998.
[31] K. Team, A. Du, B. Gao. B. Xing, C. Jiang, C. Chen, C. Li, C. Xiao, C. Du, C. Liao, C. Tang, C. Wang, D. Zhang. E. Yuan, Lu, F. Tang. F. Sung. Wei, G. Lai, H. Guo, H. Zhu, H. Ding, H. Hu, H. Yang, H. Zhang, H. Yao. H. Zhao, H. Lu, H. Li, H. Yu, H. Gao, H. Zheng, H. Yuan, J. Chen, J. Guo, J. Su, J. Wang. Zhao, J. Zhang, J. Liu, J. Yan, J. Wu, L. Shi, L.. Ye, L., Yu,
M. Dong, N. Zhang, N. Ma, Q. Pan, Q. Gong, S. Liu, S. Ma, S. Wei, S. Cao, S. Huang. T. Jiang, W. Gao, W. Xiong, W. He, W. Huang, W. Wu, W. He, X. Wei, X. Jia, X. Wu, X. Xu, X. Zu,
X. Zhou, X. Pan, Y. Charles, Y. Li, Y. HU, Y. Liu, Y. Chen, Y. Wang. Y. Liu, Y. Qin, Y. Liu, Yang, Y. Bao, Y. Du, Y. Wu, Y. Wang, Z. Zhou, Z. Wang. Z. Li, Z. Zhu, Z. Zhang, Z. Wang, Z. Yang, Z. Huang. Z. Huang, Z. Xu, and Z. Yang. Kimi k1.5: Scaling reinforcement learning with Ilms. CoRR, abs/2501.12599 2025.
[32] P. Wang, L. Li, Z. Shao, R. Xu, D. Dai, Y. Li, D. Chen, Y. Wu, and Z. Sui. Math-shepherd: Verify and reinforce Iims sy-p-by-step without human annotations. In L. Ku, A. Martins, and V. Srikumar, editors, Proceedings of the 62nd Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), ACL 2024, Bangkok, Thailand, August 11-16, 2024, pages 9426-9439. Association for Computational Linguistics, 2024.
[33] C. Xie, Y. Huang, C. Zhang, D. Yu, X. Chen, B. Y. Lin, B. Li, B. Ghazi, and R. Kumar. On memorization of large language models in logical reasoning. arXiv preprint axXiv:2410.23123, 2024.
[34] A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, C. Zheng,
D. Liu, F. Zhou, F. Huang, F. Hu, H. Ge, H. Wei, H. Lin, J. Tang, J. Yang. J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Zhou, J. Lin, K. Dang, K. Bao, K. Yang, L. Yu, L. Deng, M. Li,
M. Xue, M. Li, P. Zhang, P. Wang, Q. Zhu, R. Men, R. Gao, S. Liu, S. Luo, T. Li, T. Tang, W. Yin, X. Ren, X. Wang, X. Zhang, X. Ren, Y. Fan, Y. Su, Y. Zhang, Zhang, Y. Wan,
Y. Liu, Z. Wang, Z. Cui, Z. Zhang, Z. Zhou, and Z. Qiu. Qwen3 technical report. CoRR, abs/2505.09388 2025.
[35] Q. Yu, Z. Zhang, R. Zhu, Y. Yuan, X. Zuo. Y. Yue, T. Fan, G. Liu, L. Liu, X. Liu, H. Lin, Z. Lin, B. Ma, G. Sheng, Tong, C. Zhang, M. Zhang, W. Zhang, Zhu, J. Zhu, Chen, J. Chen, C. Wang, H. Yu, W. Dai, Y. Song, X. Wei, H. Zhou, J. Liu, W.- Ma, Y.Q. Zhang, L. Yan, M. Qiao, Y. Wu, and M. Wang. Dapo: An open-source Imm reinforcement learning system at scale. CoRR. abs/2503. 14476, 2025.
13

---

[36] L. Yuan, G. Cui, H. Wang, N. Ding, X. Wang. B. Shan, Z. Liu. J. Deng, H. Chen, R. Xie, Y. Lin, Z. Liu, B. Zhou, H. Peng, Z. Liu, and M. Sun. Advancing LLM reasoning generalists with preference trees. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025.
[37] Z. Yuan, H. Yuan, C. Li, G. Dong, C. Tan, and C. Zhou. Scaling relationship on learning mathematical reasoning with large language models. CoRR, fbs/2308.01825, 2023.
[38] D. Zhang, S. Zhoubian, Z. Hu, Y. Yue, Y. Dong, and J. Tang. Rest-mets#: LLM self-training via process reward guided tree search. In A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NewrIPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction explicitly state the paper's key claims and contributions. These claims are clearly supported by experimental results and discussions provided in Section 6, Section 7, and Appendix F.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations of Section and Appendix G.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer:
[NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper fully discloses all the information needed to reproduce the main experimental results. We will include our code in the supplementary material and provide detailed instructions for reproducing our experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
16

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide our code along with detailed instructions in supplementary material to reproduce all major experimental results presented in our paper. Our experiments are conducted using publicly available datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Shbllic/guides/CoeeStttiii
www.ssswwssssoossosoooooooo.. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //niss... /twpps.cc/pppppeee// h //t////ooeeeeesseeeeeeeeee iitmmissionn onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the experimental setup in Section and 7, and listed important hyperparameters Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Due limited computational resources, we were unable to provide error bars, as our reinforcement learning experiments require dozens of hours per run.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We describe the computational resource in Appendix H. In Section 6 and we include training dynamics that show the training time.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : http///eeuuupueeeeeeeeeeee wwtperis..cpp.ulllllleeeee cc/public////cppttcccccccccccclc htc//ubbic//thiiceeeeeeeeeeeeeee htte/Etttiisstieeeeeeeeeeeeee csGuidelines"
Answer: [Yes]
Justification: We have carefully reviewed the NeurlPS Code of Ethics and confirm that our research fully complies with all specified guidelines.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work presents a fundamental reinforcement learning framework and has direct societal impact.
Guidelines:
18

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks it does not release any models or datasets with high potential for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use the widely adopted GSM8K and MATH datasets, clearly cite their original sources, and respect their terms of use and licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comdaatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: /tt////eerippppepe http://rppp..ccomeeeeerre/////// ccc.Confeeenncc///25//////////// for what should or should not be described.
21

---

A Detailed Related Work
Boosting LLM's Reasoning Capacity. Various approaches have been explored to strengthen the reasoning abilities of LLMs. Several methods focus on using high-quality data for training. For instance, RFT [36, 37] fine-tunes the pretrained base model using correct samples generated by a supervised fine-tuned model. Similarly, RestEM [29] adopts an iterative self-training strategy, repeatedly retraining the base model on high-quality reasoning traces produced by previously obtained checkpoints. Preference-basee methods like DPO [24, 23] optimize models by contrasting correct and incorrect reasoning outputs. Search-guided approaches, like Monte Carlo Tree Search (MCTS) [38, 31, help models discover improved reasoning paths during inference. Another significant direction involves RL frameworks, which typically adopt policy gradient-basee methods and differ mainly in advantage estimation granularity. For example, GRPO [28] and RLOO [1] estimate trajectory-level advantages, while PPO [26, 21] estimates token-level advantages using a dedicated critic model. Recent work [12] highlights that accurately training the critic in PPO is challenging, and proposes VinePPO, a critic-free alternative that partitions the reasoning trajectory into discrete steps using heuristic rules (e.g., line breaks) and estimates step-level advantages through Monte Carlo (MC) sampling. PRIME [6] simultaneously trains a process reward model using outcome rewards during policy training, providing process rewards to better guide policy optimization, while our work does not rely on reward models. Most recently, several works have proposed improvements upon the original GRPO method, like DAPO [35] and Dr. GRPO [16], based the trajectory- sejeet advantage estimation.
Fine-Grained Reward Signals. A common approach in prior work assigns single binary reward to the final output of LLMs by comparing it against the ground truth. However, this sparse reward provides limited guidance, resulting in the difficulty of credit assignment during training. To address this challenge, [13] initially proposed "Process Reward", which involves manually judging correctness at every intermediate reasoning step. Subsequent works, such as [32], [17], and [19], automated the process reward generation without manual labeling through rollouts. These methods focus on training an external Process Reward Model (PRM) to provide intermediate rewards for policy optimization and enable Best-of-N (BoN) selection during inference. In practice, when applying PRM for policy optimization, existing approaches typically combine step-level rewards with the final binary correctness rewards and still employ standard RL algorithms such as PPO or GRPO for training. In contrast, our approach differs fundamentally by improving the RL optimization algorithm itself, rather than relying on external reward models. We introduce an MC-based estimation method to directly compute segment-level advantages from the current policy, aiming at potentially reducing gradient estimation variance and enabling finer- sneerggriied credit assignment during optimization. This strategy helps stabilize training and leads to more effective policy updates compared to using sparse, trajectory-level rewards alone. Notably, our MC advantage estimation framework remains fully compatible with the PRM approach: intermediate process reward signals generated via PRMs could be integrated with our trajectory evaluations. Such integration may combine the strengths of both methodologies, providing further potential improvements in overall model performance. In Appendix C, we provide an analysis of integrating the process reward into our framework.
B Policy Learning via Policy Iteration
We can alternatively adopt policy iteration- based approach formulated in the following way for policy learning. The objective of training LLMs via RL can be written as a KL-constrained policy optimization problem:
TTax Tret (an (sh)
( Ex Σ
r(sh,an) an) -Blog
By defining the modified reward F(s, a) = r(s,a) + (arlss, arrive at an equivalent maximum-entrog RL formulation:
H
(TT = Er ddo Σ
(F(sh, an) + (3((=(1sss))
Under this formulation, the Q-function and value function satisfy the soft Bellman equation: Q(sh, an) F(sh, an) + ((s+11).
22

---

Given the above relationships, we can optimize the Q-function via the loss:
(Q an DoD (Qa as) - F(sh, an) - V& (=($n+1))
Given the estimates of Q-function and value function, the optimal policy satisfies:
Qu(Sp, 0n) (a(sn) / log (p (s.))
Substituting this optimal policy relationship back into the Bellman equation results in the following policy optimization objective:
L (0) (ss. (w (Vo(s%) + 3 log To(an)s)) F(sh: on) (5)())1))
Since we have estimated the advantages Ass, an) (($++1) (ss),, explicit estimation of value function V is not necessary. Thus, the policy optimization objective further simplifies to:
B log [T((n)(h)
27
L (0) ann,a
A(s an)
Trer Faer(an
Each iteration of this procedure corresponds to policy improvement step, and after updating the policy, newly sampled trajectories can be employed to update the Q-function estimation.
We conduct preliminary experiments using this objective function, where adopt SPO-tree (6-6- 6) method and introduce an importance weight de to alleviate the off-policy influence. The results, shown in Figure 6, demonstrate that our approach enables steady policy improvement. However, it does not reach the performance achieved by policy gradient with probability masks described in Section 5), which achieves a validation accuracy slightly above 0.7.
SPO-chain with policy iteration optimization
Validation Accuracy (%)
65.0
62.5
60.0
57.5
55.0
52.5
100
200
300
400
500
600
Iteration
Figure 6: Validation accuracy on GSM8K using policy iteration optimizing method.
C Incorporate Process Reward
Our framework is compatible with the process reward. Inspired by the work in [27], we adopt the current policy's BoN as the prover policy l and utilize its advantage the process reward. Specifically, the gradient is computed as follows:
V Vxl(T) V log (an sn) (Q" an) + a (Mh,,, ax))
Unlike the aforementioned work, our method does not require training a separate reward model (PAV). Given that the adopted prover policy y is the current policy's 's BoN, we can compute its value function (*(s)) from the value function of the current policy V*(ss)
(*((s) 1 (1 V* (sn))
where N is the number of MC samples. Then, the prover policy's 's advantage A"(sn, an) can be easily computed follows:
(" an)) = (*($*+1) - (sx)).
Thus, we can directly integrate process rewards into our framework using MC samples generated
from the current policy, simplifying the overall algorithm and effectively circumventing potential
issues that arise from introducing separate reward model, such fitting errors and reward hacking.
23

---

Trejectories question
Question
Iteration 1-3
Question
Question
Ieration i-2
Question
Question
lleration
Question
Question
Iteration i
Question
Trajectories used Iteration
Figure 7: Illustration of the replay buffer. this example, each iteration, we sample two questions, with each question generating four trajectories. These trajectories are distributed across four iterations for optimization. The trajectories used in the i-th iteration are selected in the blue box. In total, there 8 different questions, each with 4 trajectories, ensuring balanced distribution of samples.
D Replay Buffer
Within each iteration, sampling large number of trajectories from single question lead imbalanced training, causing the model to overfit to specific samples. To address this issuc, we introduce replay buffer mechanism that distributes sampled trajectories across multiple iterations, ensuring more balanced question distribution, as shown in Figure 7. Additionally, PPO's clip mechanism helps maintain stable optimization when using these trajectories from previous iterations. Specifically, in our experiments, we use 6-6-6 tree structure for sampling, generating 6 6 216 trajectories per question. In each iteration, we sample 16 distinct questions generate trajectories, and these trajectories are then distributed across the following iterations, with at most 32 trajectories per question processed each iteration. As result, each iteration covers 128 distinct questions 16), ensuring well-balanced sample distribution. We observe that the clip ratio remains around 0. validating the effectiveness our replay buffer strategy.
Our replay buffer mechanism leads to certain degree of off-policy learning, enabling our framework be compatible with the asynchronous RL setting, which first explored by [20]. Leveraging asynchronous RL can further parallelize data collection and policy optimization, potentially leading additional efficiency improvements.
E Pseudo-code of Tree-Structured Advantage Estimation Method
We efficiently construct the tree using Python's asyneio library. For the detailed algorithm procedure, please refer to Algorithm below.
24

---

end if Algorithm Tree-structured Advantage Estimation Method
1: procedure CONSTRUCTTREE(yoonpyy max dep_h, struclure, M, instance, adv aid_meehod) create root node:
2:
3:
root, text < prompt
4: root.full, text <- prompt
5: root, boot.deph + 0
6:
await BUILD(root, prompt, O, max perr_eeph, structure, M, instance) COMPUTEADVANTAGGEEE
7:
None, adv_me (el__mehod)
8: return root
9:
end procedure
procedure BUILD(node, prefix, depth, max max_depth, structure, M, instance)
11:
if depth 2 max__epph then
12:
node.reward <- REWARD_ BARHAARDDFUNCTOOOpprefeooeo node.text, instance) return 14: end
13:
15: K +- structure(depth)
16:
if depth <, mmar_ maax_eeph then
17:
maz_tokene M
18:
else
max mokens None
20:
end if
21:
chiilrrnn await EXPAND(prefies depth, K, mar_lokens)
22:
cooee.childee + children
initialize empty list exponsion tasks for each child in children do if child. reason * "length" then
24:
26:
child.reward t REWARD FUAAADDDUNTTONpprfffa child.tert, instance)
else
28:
create async task + BUILD(child, fhild.full. fullttrftte depth + 1, mar depth, struclure, M, inslunce)
29:
append t to cictonsioottsssee end if
30:
31:
end for
32:
await GATHER(erpansioon) lasks)
33:
node.reward +- mean(rewards of node.children)
node.reward std + std(rewards of node.children)
35:
end procedure
procedure EXPAND(prefiiz depth, K, mar_tokens) construct LLM prompt from template using frefix
37:
create async task calling LLM API requesting K responses, each limited max tokens responses + await task
39:
initialize empty list children for each response in responses do create new node child:
41:
43:
child.text &- response.text
44:
www.ffiiniiaaseeee + response.finish_reene
45:
fill_fful__tee + concatenate_textst setpaattee_tttsteefeeeeeee fiz, child.tert)
46:
append child to children
47:
end for
48:
return children
49:
end procedure
50: procedure COMPUTEADVANTAGE(Iodd. parent, adv adu_method)
51:
if parent is not None then
52:
adv metheeethd = "RLOO" then node.reward parent.reward
53:
node
54:
else if adv adu_method = "GRPO" then
55:
end node..ddvantage (node.reward paree...
56:
58:
end procedure
25

---

GRPO GSMBK
GRPO
GSMIK
GRPO GSMBK
Train Accuracy (%6
Num Unique Responses
mm
Validation Accuracy
80-
60
0.00
800
10.0
0001
9000
1000
2000
10000
5000
1000
Iteration
Iteration
Iteration
(a) Train Accuracy.
(b) Train Num Unique Responses.
(c) Validation Accuracy.
Figure 8: GRPO GSM8K exhibits rapid overfitting: while training accuracy improves steadily (Fig. 8a), but the unique response number constantly drops (Fig. 8b), and validation accuracy saturates early (Fig. 8c).
Additional Experiment Results
We also evaluate our SPO-chain method using DeepSeekMath 7B on the MATH dataset, as shown in Figure 9. Our approach achieves performance comparable to VinePPO and surpasses all other baselines. Due to computational constraints, we initially train with an interval of 10 and later switch to 5. After switching from the interval of 10 to 5, the model performance continues to improve, suggesting that using finer- snee-grained advantage is beneficial for model training. Notably, as shown in Figure 10, method uses significantly fewer segments than VinePPO while attaining similar performance.
DerpSockMath
of sampling points vs iteration
45.0
Num of sampling points
Test Accuracy (96)
from
40.0
VinePPO
37.5
durgal fro 95
35.0
39.5
10000
15000
20000
25000
Step
200
100
600
800
1000
1200
1400
1600
SPO-chain Ini.
RasEM
DPO+
VinPPO
Iteration
Figure 10: Comparison of the number sampling points between our method and VinePPO. Ac- cording to [9], there are approximately 8 reason- ing steps on average for MATH.
Figure Performance SPO-chain on DeepSeekMath 7B evaluated the MATH500. Baseline results are from [12].
In addition, We conduct experiments on instruct and base models. Specifically, we evaluate Qwen2.5- I.SB-Instruct and Qwen2.5-0.55 0..5.5---..-Innstrruc on the GSMSK dataset, and Qwen2.5- 1aren225--ath-L.... 1.5B on the MATH dataset. The results are presented in Figure 11 (a)-cc), Across all these settings, our method consistently outperforms GRPO, achieving higher test accuracy.
We further extend our evaluation beyond mathematical reasoning to the Knights-ands -nav-Knaves dataset [33], classic logic puzzle benchmark where each character either a knight (who always tells the truth) or knave (who always lies), and the task is to deduce each character's 's identity from their statements. For this experiment, we use the 3-people (3ppl) subset and train models based on Swen2.5-11.5--Isstte
The corresponding results are reported in Figure 1 (d). On this dataset as well, our method outperforms GRPO, demonstrating its generality and effectiveness beyond the MATH dataset.
26

---

(a) Qwen2.5-0.5B GSM8K
(b) Qwen2.5-11.5 Instruct -nnssrrurtt
GSM8K
70
Test Accuracy (%)
Test Accuracy (%)
65
60
75-
55
70-
50-
SPO-tree
(6-6-6)
65
SPO-tree (6-6-6)
45
GRPO
GRPO
60
500
1000
1500
2000
500
1000
1500
2000
Interation
Interation
(c) Swen2.5-Math-e MATH
(d) Twen2.5-11.BB-nmss K&K
MATH500 Accuracy (%)
75
1.0
70
Test Reward
0.5
65
0.0
0.5
60
SPO-tree (6-6-6)
SPO-tree (6-6-6)
GRPO
-1.0
GRPO
500
1000
1500
2000
2500
100
200
Interation
Interation
Figure 11: Experimental results across different models and datasets. (a) Qwen2.5-0.55 1ann2.5-0.5B-Intteeee on GSM8K. (b) Qwen2.5-1.5B IBIItruttt on GSM8K. (c) Dewen2.5-1.5BMMe. on MATH. (d) Qwen2.5-
Instruct Knights-and- and-Knaves (3ppl).
G Limitations and Future Work
In long CoT scenario, we propose tree-based advantage estimation strategy that can deliver fine- grained reward signals with lower sampling costs. However, for a single problem, constructing a tree requires sampling large number of trajectories. We use replay buffer to distribute these trajectories across several future iterations. However, this approach is still constrained by on on-policy algorithms, which cannot distribute trajectories too far into future iterations. In the future, off-policy algorithms, achieve more efficient sample utilization. This would allow us reuse the high-quality samples obtained from SPO-chain methods and alleviate the issue of sample imbalance caused by tree-based sampling.
may explore more
H Hyperparameters and Compute Resources
Our code base based on [12]. Most hyperparameters are same as theirs. Here we list important hyperparameters in the following five tables. We perform SPO-chain and SPO-tree experiments with RhoMath I.IB using single A 100 GPU (40GB). For the long-CoT experiments (2K and 4K context) single 1.00 GPU (80GB).
using DeepSeck-RR -------iil---enne-eeee-- 1.5B,
27

---

SPO-chain (int5) Rho
SPO-tree (6-6-6) Rho 1.1B on GSM8K
1.1B on GSM8K
Hyperparameter
Value
Hyperparameter
Value
Target train batch size
64
Target train batch size
128
Num episodes per iteration
512
Num episodes per iteration
512
Dataset samples per iteration
64
Dataset samples per iteration
16
Samples (per prompt)
8
Samples (per prompt)
Cutpoint interval
5
Cuipoint interval
(MC samples)
9
K (MC samples)
M (Tokens per level)
M (Tokens per level)
30
Branch factors
Branch factors
[6,6,6]
Train policy temperature
0.6
Train policy temperature
0.6
Train policy top-p
0.9
Train policy top-p
0.9
Train context size
2047
Train context size
2047
Initial KL coef
0.0001
Initial KL coef
0.0001
Learning rate
10 10-6
6
Learning rate
10-0 1
Epochs per iteration
2
Epochs per iteration Prob mask threshold
Prob mask threshold
0.9
0.9
Eval. context size
2047
Eval. context size
2047
Eval. temperature
0.35
Eval. temperature
0.35
Eval. top-p
0.9
Eval. top-p
0.9
Eval. samples
16
Eval. samples
16
GRPO DeepSeek-R1-Distille R1-Dittil--Qwen
SPO-tree (6-6-6) DeepSeek-RL-Dissll--Ne
1.5B on MATH
1.5B on MATH
Hyperparameter
Value
Hyperparameter
Value
Target train batch size
128
Target train batch size
128
Num episodes per iteration
512
Num episodes per iteration
1024
Dataset samples per iteration
64
Dataset samples per iteration
16
Samples (per prompt)
8
Samples (per prompt)
Cutpoint interval
Cutpoint interval
(MC samples)
(MC samples)
M (Tokens per level)
M (Tokens per level)
600
Branch factors
Branch factors
[6,6,6]
Train policy temperature
0.6
Train policy temperature
0.6
Train policy top-p
1
Train policy top-p
Train context size
2048 => 4096
Train context size
2048
4096
Initial KI. coef
0.0001
Initial KI. coef
0.0001
Learning rate
x 10-5
Learning rate Epochs per iteration Prob mask threshold Eval. context size Eval. temperature
1 10
Epochs per iteration
1
Prob mask threshold
No prob mask
0.9
Eval. context size
2048 => 4096
2048 => 4096
Eval. temperature
Eval. top-p
0.9
Eval. top-p
0.9
Eval. samples
Eval. samples
28

---

SPO-chain (int5=>10) DeepSeekMath
7B on MATH
Hyperparameter
Value
Target train batch size
64
Num episodes per iteration
512
Dataset samples per iteration
64
Samples (per prompt)
8
Cutpoint interval
10=>5 5
(MC samples)
9
M (Tokens per level)
Branch factors
Train policy temperature
0.6
Train policy top-p
0.9
Train context size
4095
Initial KL coef
0.0001
Learning rate
10 10-6 6
Epochs per iteration
2
Prob mask threshold
0.9
Eval. context size
4095
Eval. temperature
0.35
Eval. top-p
0.9
Eval. samples
16
I Segment Partition Example
Prompt: [MATH TASK] Problem: Glonia wants to buy the $129.000 mountain cabin that her friend Allonis is selling. She only has $150 in intends to remaining amount by selling mature trees lumber. cypress trees, 600 pine trees, and 24 maple trees. She will get $100 for each cypress tree, $300 for a maple tree, and $200 pine tree. After paying Alfonso for the cabin, how much money will Gioria have left? Solution:
The total value of the eypress trees that she will sell 020 $100 - $2000.
The total value of the maple that she will sell is 600 $300 $18000.
The total value of the pine trees that she will sell is 24 $200 $4800.
The total value of the trees that she will sell $2000 11:0000+188000 $18000 $4800 - $2 4800.
Alter selling the trees, she will have $24800
$150 $23300 left.
#### 23300
Figure 12: Segment partition based on fixed cutpoiní interval. Each row corresponds to single step. Tokens marked in red indicate cutpoints (tokens with probability lower than 0.9). The blue vertical lines represent SPO segment boundaries.
Figure 12 shows practical segment partition example. As we can see, many of the cutpoints (tokens whose probability below a threshold) correspond to the places where the model makes mistakes. For instance, in the second step, the total value of the maple trees should be 24 $300, but the model outputs 600 * 300 and shows low confidence at the digit 6. If had output 2 in this position, this step might have been correct. Similarly, in the final step, the calculation should be 24800 12900, but the model instead outputs 24800 - 150 and is uncertain at the digit 5. Had it produced equation might have been correct. This case shows that cutpoints reasoning trajectory can shift, and they are the main drivers behind "segment advantage". Therefore, identifying and accurately assigning credit to these cutpoints is essential, which is consistent with our segment partition method (Section 4) and probability mask technique (Section 4).
at this point, the the locations where the model's
It is also worth noting that partitioning by line breaks, as in VinePPO, is not the most effective approach. For example, step three, none of the tokens have probabilities below 0.9, indicating that the transition probabilities for all tokens in this step are very high. As result, the estimated V/ value at the beginning and end of this step will not differ significantly, thus the advantage for this segment will be close to zero. Allocating sampling budget to this step is likely to result in wasted samples.
29

---

Moreover, partitioning by step boundaries can lead to an uneven distribution of cutpoints, i... some segments may contain many, while others include too few. Our goal in segment partition is to have each segment contain roughly the same number of potential "turning points", so that we can assign credit as efficiently as possible within a limited sampling budget. Step-hased partition does not achieve this balance. This may help explain why our SPO-chain method can outperform VinePPO, even with fewer sampling points.
J Model Output Example
Compared to DeepSeek-Be RI--Dsstil---enn- efficiency, requiring fewer tokens to arrive at the correct answer (both models use greedy decod- ing). When the model's s context length is limited, increased token efficiency significantly enhances performance.
our optimized model demonstrates greater token
Problem
What is the smallest positive integer such that 17n 1234 (mod 7)?
SPO-tree
Okay, so I need to find the smallest positive integer such that 17n 1234 (mod 7). Hmm, let me think about how to approach this. remember that when dealing with congruences modulo number, it's often helpful simplify the coefficients modulo that number first. So, maybe should start by reducing 17 and 1234 modulo 7.
Let recall that find number modulo can divide by 7 and find the remainder. So, let's start with 17. Dividing 17 by 7. goes into 17 twice with a remainder. 2 times 7 is 14, and 17 minus 14 is 3. So, 17 is congruent 3 modulo 7. That means 17 = 3 (mod 7). So, the equation 17n = 1234 (mod 7) simplifies to 3n = 1234 (mod 7).
Now, need find 1234 modulo Let me do that. 1234 divided by Hmm. times 176 is 1232 because 176 times 7 is 1232. So, 1234 minus 1232 is 2. Therefore, 1234 = (mod 7). So, now the equation 3n = 2 (mod 7).
Alright, so have 3n 2 (mod 7). need to solve for n. To do that, I think need to find the multiplicative inverse of 3 modulo The multiplicative inverse is number x such that 3z = 1 (mod 7). Once I have that, I can multiply both sides of the equation by to get (mod 7).
So, let me find the inverse of 3 modulo 7. Let's try numbers from 1 upwards:
-3
(mod 7) Not 1. 3 x 2 = 6 = (mod 7) - Not
(mod 7) + Not -
3-x x 4 12 = 5 (mod 7) - Not 1. 3 x 5 = 15 (mod 7) Yes! mod
So, 5 is the inverse because 3*5=15, which
Great, so the inverse of 3 mod 7 is 5. Therefore, multiplying both sides of 3n = 2 (mod 7)
by gives:
5 x 3n 3 x (mod 7)
Simplifying, 15n 10 (mod 7). But 15 mod 7 1, because 7*2=14, so 15-14=1. Similarly, 10 mod 7 is 3, because 7*1=7, 10-7=3. So, this simplifies to:
In = 3 (mod 7)
Which means = 3 (mod 7). So, the smallest positive integer that satisfies this is 3. Let me just verify that.
Calculating 17 3 51. Then, 51 mod 7: 7*7=49, so 51-49=2. And 1234 mod is 2, found earlier. So, 51 mod 7 is 2, which matches 1234 mod 7. So, yes, is the correct answer. **Final * The smallest positive integer is To find the smallest positive integer n such that 17n the coefficients modulo 7.
1234 (mod 7), we start by simplifying
First, we reduce 17 modulo 7:
17 = - remainder 3 - 17 = (mod 7)
Thus, the equation 17n 1234 (mod 7) simplifies to:
3n 1234 (mod 7)
30

---

Next, reduce 1234 modulo 7:
1234 + 7 = 176 remainder
1234 = (mod 7)
So, the equation becomes:
3n = 2 (mod) 7)
To solve for we need the multiplicative inverse of 3 modulo 7. Testing values, we find that:
3 x 5 = 15
(mod) 7)
Thus, the inverse modulo is 5. Multiplying both sides of (mod 7) by 5:
5 3n 5 (mod 7) = 15n 10
(mod
Simplifying, since 15 (mod 7) and 10 (mod 7):
n 3 (mod) 7)
The smallest positive integer n is Verifying, 17 3 51 (mod 7) and 1234 (mod 7), confirming the solution.
Okay, so I have this problem here: find the smallest positive integer such that 17n = 1234 (mod 7). Hmm, modular arithmetic, right? I remember that congruences modulo mean that when you divide 17n - 1234 by 7, there's s no remainder. So, basically, 17n and 1234 leave the same remainder when divided by 7.
First, maybe I should simplify both sides of the congruence modulo 7. That is, find what 17 equivalent to modulo 7, and what 1234 is equivalent modulo 7. That should make the equation easier to handle.
Starting with modulo Let me divide 17 by 7 goes into 17 twice, which 14, and the remainder is 3. So, 17 3 (mod 7). That simplifies the left side of the congruence to 3n. Now, the right side is 1234 modulo 7. Hmm, 1234 is big number, so need a systematic way to find its remainder when divided by 7. Maybe can break it down digit by digit or use some divisibility rules. Alternatively, can use the fact that 10 is congruent modulo so powers of 10 can be simplified.
Wait, another approach: can divide 1234 by 7 and find the remainder. Let me do that. goes into 12 once, with remainder of 5. Bring down the 3 to make 53. 7 goes into 53 seven times, which 49, leaving a remainder of Bring down the to make 44. 7 goes into 44 six times, which is 42, leaving remainder of So, 1234 divided by is 176 with remainder of Therefore, 1234 = 2 (mod 7).
So now, the congruence simplifies to 3n 2p mod 7. Okay, need to solve for in this equation. That is. find the smallest positive integer n such that when multiplied by 3 and then divided by 7. the remainder is 2.
To solve 3n = (mod 7). think I need to find the multiplicative inverse of 3 modulo 7. (mod 7). Once have that, I
The multiplicative inverse of is a number x such that
can multiply both sides of the congruence by æ to isolate
So, let's find the inverse of 3 modulo can test numbers from upwards to see which one satisfies 3z = 1 (mod 7).
-3
(mod - Not 1. x 2 = 6 = 6 (mod 7) - Not -
(mod 7) + Not - x 4 = 12 = 5 (mod 7) - Not 1. - 5 = 15 (mod 7) Yes!
That works.
So. the inverse of 3 modulo is 5. Therefore, multiplying both sides of the congruence
3n 2 (mod 7) by 5 gives:
5 5 2 (mod 7)
Simplifying the left side: 15n = 2 (mod 7). But 15 modulo 7 is 1, since 15 divided by is
2 with remainder of 1. So, this simplifies to:
31

---

In = 2 (mod 7), which is just n (mod 7). Therefore, the smallest positive integer n that satisfies this congruence is 2. Let me double- check to make sure didn't make a mistake.
Plugging = 2 back into the original equation: 17 x 2 = 34. Now, 34 divided by 7 is 4 with a remainder of 6. Wait, but 1234 modulo was 2, so 34 modulo 7 6, which is not equal to 2. Hmm, that's s problem. Did do something wrong?
Wait, hold on. Let me check my steps again. Maybe messed up the inverse or the simplifica- tion.
Starting over: 17n = 1234 (mod 7). found that = (mod 7) and 1234 (mod 7). So, 3n = 2 (mod 7). Then, found the inverse of 3 modulo 7 is because 3 x 15 =
(mod 7). So, multiplying both sides by n = 10 (mod 7). But 10 modulo is 3, so n2 (mod 7). Wait, so earlier I thought it was 2, but that was mistake.
Wait, no, me recast that. If = 10 (mod 7), then 10 divided by 7 is with a remainder
of 3, = 3 (mod 7). So, the smallest positive integer is 3. Let me check that.
Plugging n = into 17n: 17 x 3 = 51. 51 divided by 7 is with a remainder 2f So, 51 modulo 7 is 2, which matches the right side of the congruence. So, that works.
Wait, so earlier thought the inverse was 5, but that led me to n = 10 (mod 7), which 3.
So, the correct answer is 3, not 2. must have made mistake in my initial calculation.
Let me go through the inverse part again. So, to find the inverse of modulo 7, need a number æ such that 3r
(mod 7). Testing:
-3 x 1 = 3 = 3 (mod 7) 3 x 2 = 6 = 6 (mod 7) 3 x 3
= 2 (mod 7)
4 12 5 (mod 7) - x 5 15
(mod 7)
Yes, so is the inverse. So, multiplying both sides by 5: 5 x 3n = 5 x 2 (mod 7). which is
15n 10 (mod 7). But 15 modulo 7 so n 10 (mod 7). 10 divided by is with remainder of 3, n = 3 (mod 7). So, the smallest positive integer is 3.
Wait, so why did get confused earlier? Because I thought 10 modulo is but I thought 10 was 3, but when first thought of 10, thought it was 3, but when I first thought of 10, thought was 3, but when I thought of 10, thought it was 3, but when thought of 10, I thought it was 3, but when I thought of 10, thought it was 3, but when thought of 10, thought it was 3. Wait, no, that's not right.
Wait, 10 divided by 7 is I with remainder of 3, so 10 modulo is 3. So, So, the smallest positive integer is
(mod 7).
Let me verify again: 17 3 = 51. 51 divided by 7 is with remainder of 2. So, 51 modulo 7 is 2, which is equal to 1234 modulo 7, which 2. So, that works.
Wait, earlier, when thought I had 10 modulo 7, thought it was 3, but I think confused myself. So, the correct answer
But just make sure, let try 3: x7 3- 51. 51 divided by 7 is 7*7=49, 51-49-2. So, 51 mod7=2, which is equal to 1234 mod7=2. So, yes, that works.
Wait, but earlier, when thought of 10 modulo7, thought was 3, but that was miscaleula- tion. So, the correct inverse is 5, leading to n = 10 (mod 7), which is 3.
So, the smallest positive integer is 3.
But just to make sure, let me try = 3 in the original equation: 17 x 3 = 51. 51 mod7 is 2, which is equal to 1234 mod7, which is 2. So, yes, that works.
Wait, but let me also check 3 - 7 = -4. 4. But since we'r re looking for positive integers, the smallest.
Alternatively. if had different inverse, but no, is the inverse. Wait, but just to make sure, let me try + 7 10. 17 10 = 170. 170 divided by is 24*7=168, so 1 170-168=2, So, 170 mod7=2, which is equal to 1234 mod7=2, So, that also works, but 10 is larger than 3, so 3 the smallest. Therefore, the answer is 3.
Wait, but hold on, my initial calculation, thought had 10 modulo7=3, but thought 10 was 3, but that was confusion. So, the correct answer is 3. But just to make sure, let me try another approach. Maybe I can solve 3n = 2 (mod 7) by testing n=1,2,3 .... until I find the smallest that satisfies the equation.
n=1: 3 * ++==3 (mod 7). Yes! So, 3 is the smallest positive integer.
3 + 2 (mod 7) n=2: 3 * 2 = * 2 (mod 7) n=3: * =
So, that confirms So, the answer 3.
32

---

Wait, but in my initial thought process, I thought had 10 modulo7=3, but that was miscalculation. So, the correct answer Therefore, the smallest positive integer n is 3.
**Final Answer* The smallest positive integer is 3
To find the smallest positive integer n such that 17n = 1234 (mod 7), we start by simplifying both sides of the congruence modulo 7. First, we simplify 17 mod 7:
17 + 7 2 remainder 3
Thus, = (mod 7). Next, we simplify 1234 mod 7. We can do this by dividing 1234 by 7 and finding the remainder:
1234 + 7 176 remainder 2
Thus, 1234 = 2 (mod 7).
This reduces our original congruence to:
3n = 2 (mod 7)
To solve for n, we need the multiplicative inverse of 3 modulo7. We find this by testing values:
3 x ==
(mod 7)
Thus, the inverse of modulo is 5. Multiplying both sides of the congruence 3n 2 (mod 7) by
5 x 3n 5 (mod 7)
15n = 10 (mod) 7)
Since 15 = (mod 7), this simplifies to:
10 (mod 7)
10 7 remainder 3
Thus, = 3 (mod 7).
The smallest positive integer n is 3. Verifying, we find:
17 3 51
51 + 7 = 7 remainder 2
Thus, 51 = 2 (mod 7), confirming our solution.
The smallest positive integer n is
33


Reviews:
[{"review_id": "YoFwdFzKZT", "reviewer": "Reviewer_wXY9", "summary": "The paper introduces Segment Policy Optimization—an algorithm aiming to have fine-grained advantage estimation similar to PPO without introducing challenges in value estimation for a token-level critic. Therefore, SPO is partially along the spectrum towards GRPO, but instead of providing reward signal only from the termination of a trajectory, SPO partitions a trajectory into several segments, and computes advantage at the last “splitting token” of each segment. The paper offers an intelligent segment splitting strategy at low-probability tokens, and performs policy optimization over variable-length segments. Empirical results indicate boosts over GRPO in both short chain-of-thought and longer reasoning settings.", "questions": "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.\n\nAll 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.\n\nIt 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?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe paper crafts an insightful problem setup in juxtaposing the relative strengths and weaknesses of PPO and GRPO. The probability-guided segment splitting strategy is novel, and in particular focuses on the most “important” decisions in a trajectory that can be informative. \n\nEmpirical results convincingly show the efficacy of both SPO-Chain and SPO-Tree. Ablations are quite valuable—as it is interesting to see that SPO-Tree performance isn’t very affected by hyperparameters tested in Figure 5. \n\nAblations are also performed on the key segment-length parameter. \n\nThe implementation of both chain and tree-based segment advantage estimation is a nice intuitive tradeoff. \n\n**Weaknesses**\n\nNote 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.\n\nAll 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.\n\nIt 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?", "was_revised": true, "final_justification": "I initially had concerns that results were limited to math settings, and was unclear on how to motivate the use of SPO in novel settings, as opposed to GRPO or PPO. In the rebuttal, the authors demonstrate additional experimental results beyond mathematical settings, and additionally provide reasoning on scenarios to use the different RL algorithms. As a result, I raised my score.", "rebuttal": "Thanks for your valuable and constructive comments. Below, we provide detailed responses to the concerns and questions you have raised.\n\n>  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.\n\nThanks 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”.\n\n> 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.\n\nThank 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.\n\n> 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?\n\nThanks for the suggestions. We will discuss more limitations of our method in the future version as follows. \n\nOur 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.\n\n**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. \n\nHowever, 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.\n\n**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."}, {"review_id": "d5oNAYxO8U", "reviewer": "Reviewer_3Avs", "summary": "This paper proposes Segment Policy Optimization (SPO) for training LLM reasoners with better credit assignment. It cuts the CoT into several segments based on token probability values, then conducts monte carlo estimation of the value of each segment by unrolling the current policy in either chain or tree format. Finally, the policy gradient is applied with a probability mask to only train those \"critical\" tokens. Empirical results show that the proposed method achieves better learning efficiency and final performance compared to baselines including VinePPO and GRPO.", "questions": "(1) 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\n\n(2) following (1), i am curious what the result of int1 will be?\n\n(3) 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 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?\n\n(4) have you tried SPO-chain on the long CoT scenario? or SPO-tree on the short CoT scenario? \n\n(4) for fig5a, have you tried GRPO with probability mask? i am very curious its wall-clock time curve", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "strengths:\n- the paper is clearly written and all techniques are simple to understand\n- efficiency-wise the proposed method is better than vinePPO\n\n\n\nweakness:\n- line 357: i do not think evaluate 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].\n- the experiments did not show vineppo with probability mask, which i think is an important baseline to claim that the proposed method does better credit assignment\n\n\n\n[1] https://arxiv.org/pdf/2503.20783", "was_revised": true, "final_justification": "This paper presents a bag of techniques to improve the original VinePPO method.\n\nI would suggest a weak accept given the reasonable motivation of the proposed techniques and good empirical results.", "rebuttal": "Thanks for your valuable and constructive comments. Below, we provide detailed responses to the concerns and questions you have raised.\n\n> 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].\n\nThank 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.\n\n> 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\n\nThank 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.\n\n> 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\n\nThank 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:\n\n- \"int2\" means partitioning the model output at intervals of every 2 cutpoints, which results in the most (finest) segments.\n- \"int5\" means partitioning the model output at intervals of every 5 cutpoints, resulting in fewer (coarser) segments compared to int2.\n- \"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.\n\nAs 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.”\n\n> Q2: following (1), I am curious what the result of int1 will be?\n\nWe 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.\n\n> 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?\n\nThank 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.\n\nAs 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\\>.\n\nWe 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.\n\n| | | |\n|:-:|:-:|:-:|\n|Training hours / Accuracy (%)|2 segments split at \\</think\\>|SPO-tree (6-6-6)|\n|2|63.8|**66.0**|\n|4|69.6|**72.4**|\n|6|71.0|**75.0**|\n|8|74.2|**76.0**|\n|10|74.2|**76.2**|\n\n> Q4: Have you tried SPO-chain on the long CoT scenario? or SPO-tree on the short CoT scenario?\n\n**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.\n\n**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.\n\nThe 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.\n\n> Q5: For fig5a, have you tried GRPO with probability mask? i am very curious its wall-clock time curve.\n\nThank 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.\n\nWe 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.\n\n| | | | |\n|:-:|:-:|:-:|:-:|\n|Training hours / Accuracy (%)|Vanila GRPO|GRPO with probability mask|SPO-tree|\n|10|62.6|63.0|**63.2**|\n|20|65.0|65.4|**71.2**|\n|30|65.0|68.2|**71.2**|\n|40|65.6|68.2|**75.0**|\n|50|66.0|68.2|**75.0**|\n|60|66.2|68.2|**75.8**|"}, {"review_id": "0uadPXjGaP", "reviewer": "Reviewer_vcBi", "summary": "This work innovatively proposes to shift from the calculation of fine-grained token-level advantages to a coarse-grained advantage calculation at the sub-trajectory (fragment) level. As a result, it achieves a better balance between credibility allocation and computational efficiency compared to VinePPO. It provides more accurate credit allocation than the trajectory-level method and requires fewer estimation points than the token-level method, enabling advantage estimation based on the Monte Carlo (MC) method without the need for an evaluation model. The method has been validated for its effectiveness on two simple and moderately difficult datasets.", "questions": "Apart from what has been mentioned above, I noticed that the introduction of the experimental part seems to lack crucial information. 1. As VinePPO is the main comparison method, did it also set the same number of MC rollout to ensure the fairness of the experiment? 2. 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. (3) It seems that the actual response generation of LLM has not been released.", "limitations": "See above", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: The paper is well-written, and the idea is interesting to me. The experimental results are good with clear visualization.\n\nWeakness: 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. (1) 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.\nOverall, the author has provided an intuitive and effective form of advantage calculation and gradient calculation. If the author can address all the concerns raised by the reviewers with high quality, I will consider raising the score.", "was_revised": true, "final_justification": "Thanks to the author for the reply, I'll keep my score", "rebuttal": "Thanks for your valuable and constructive comments. Below, we provide detailed responses to the concerns and questions you have raised.\n\n> 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..\n\n\nThanks 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: \n\n1. **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.\n\n2. **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.\n\n3. **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.\n\n> 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.\n\nThanks 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. \n\n> 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?\n\nYes, we use the same number of rollouts (K=9) for both VinePPO and our SPO-chain. We will clarify it in the experimental setup.\n\n> 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.\n\nThank you for your valuable suggestion regarding the evaluation on base models. We address your concern in two parts:\n\n**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).\n\n**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:\n\nQwen2.5-Math-1.5B (base):\n| | | |\n|:-:|:-:|:-:|\n|Training Steps / Accuracy (%)|GRPO|SPO-tree|\n|100|**68.4**|67.6|\n|200|70.4|**71.4**|\n|300|71.4|**71.8**|\n|400|71.4|**72.8**|\n|500|71.6|**73.6**|\n|600|72.4|**74.2**|\n|700|73.0|**74.2**|\n|800|73.0|**74.2**|\n\nIn 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:\n\nQwen2.5-0.5B-Instruct:\n| | | |\n|:-:|:-:|:-:|\n|Training Steps / Accuracy (%)|GRPO|SPO-tree|\n|100|56.3|**57.8**|\n|200|57.5|**61.1**|\n|300|57.5|**62.0**|\n|400|58.0|**62.4**|\n|500|59.9|**62.9**|\n|600|59.9|**64.1**|\n\nQwen2.5-1.5B-Instruct:\n| | | |\n|:-:|:-:|:-:|\n|Training Steps / Accuracy (%)|GRPO|SPO-tree|\n|100|74.6|**79.1**|\n|200|77.5|**81.7**|\n|300|77.5|**82.6**|\n|400|78.1|**83.5**|\n|500|78.1|**83.5**|\n|600|78.1|**84.0**|\n\nThese results demonstrate that SPO-tree consistently outperforms GRPO across base, instruct, and R1-distill models, as well as different datasets.\n\n\n> Q3: It seems that the actual response generation of LLM has not been released.\n\nThank 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."}, {"review_id": "FnerRa2qov", "reviewer": "Reviewer_L77S", "summary": "The authors propose a new algorithm for training reasoning models with reinforcement learning by improving credit assignment. Token-level methods like PPO has a value network, which is expensive to calculate and can be inaccurate, whereas trajectory-level methods like GRPO is too crude when it comes to assigning credits.\n\nTo help bridge the gap, the authors propose a new method called Segment Policy Optimization (SPO), breaking the trajectory into segments. If the trajectory is typically short, SPO performs the segmentation mostly by identifying token positions where the probabilities drop below a certain threshold, which usually corresponds to where the reasoning trajectory might diverge. These positions are identified as \"cutpoints\". Then they can just perform Monte Carlo on those cutpoints to do value estimation. For longer trajectories, SPO employs a tree based method that attempts to re-use existing calculations.\n\nThe experiments show that SPO methods can outperform many other RL methods like GRPO and PPO when evaluated using the gsm8k test accuracy, when trained on RhoMath 1.1B.", "questions": "* Could the authors provide more runtime or compute budget information on SPO? For example, using interval 5 seems to use a lot more computation than interval 100. However, this is not quantified in Figure 4.\n\n* Can you plot the learning curves using time as the x-axis?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well-motivated; the authors compare several methods for credit assignment on trajectory segments. Furthermore, the authors came up with clever heuristics like determining segment boundaries via \"cutpoints\", where the probability of predicting the next token drops.\n\nExperiments seem well-designed, and ablation studies were provided.\n\nWeaknesses:\n\nWhile 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.\n\nI'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.", "was_revised": true, "final_justification": "The author provided more information on runtime and cutpoint analysis, which answers my question. The paper is well-written and it contributes a new idea for reasoning research. I am raising my score because of this.", "rebuttal": "Thanks for your valuable and constructive comments. Below, we provide detailed responses to the concerns and questions you have raised.\n\n> 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.\n\nIn 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.\n\n>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.\n\nThank you for your suggestion regarding runtime and compute information. \n\nFor the experiments in Figure 4(a), we measured the average wall-clock time per 10 training iterations under different interval settings:\n\n- **Interval 2 (int2):** 1.43 hours per 10 iterations\n- **Interval 5 (int5):** 0.87 hours per 10 iterations\n- **Interval 100 (int100):** 0.58 hours per 10 iterations\n\nWe also measured the validation accuracy against the training wall-clock time for the three settings, as shown in the following table:\n\n| | | | |\n|:-:|:-:|:-:|:-:|\n|Training hours / Accuracy (%)|int2|int5|int100|\n|10|58.1|**62.7**|57.5|\n|20|61.3|**65.7**|60.9|\n|30|64.3|**67.9**|64.0|\n|40|66.4|**69.4**|64.3|\n|50|67.6|**70.7**|64.6|\n|60|68.6|**70.7**|64.6|\n|70|69.1|**70.7**|64.6|\n|80|69.7|**70.7**|64.6|\n|90|70.4|**70.7**|64.6|\n|100|70.4|**70.7**|64.6|\n|110|**70.8**|70.7|64.6|\n|120|**71.7**|70.7|64.6|\n\nThe 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."}]

Author rebuttal:

Meta-review: The paper introduces Segment Policy Optimization—an algorithm aiming to have fine-grained advantage estimation similar to PPO without introducing challenges in value estimation for a token-level critic. Therefore, SPO is partially along the spectrum towards GRPO, but instead of providing reward signal only from the termination of a trajectory, SPO partitions a trajectory into several segments, and computes advantage at the last “splitting token” of each segment. The paper offers an intelligent segment splitting strategy at low-probability tokens, and performs policy optimization over variable-length segments. Empirical results indicate boosts over GRPO in both short chain-of-thought and longer reasoning settings.

Reviewers appreciate the motivation and technical insights of the proposed method. The empirical evaluation is also comprehensive (after adding more during the rebuttal). The AC believes this paper makes a valuable contribution, and thus recommends acceptance.
Decision: Accept (poster)