acceptodds
Under review as a conference paper at ICLR 2027

Reliable Local Credit from Stratified Continuation Evidence

Abstract

Sample-based local credit uses auxiliary continuations to evaluate intermediate reasoning decisions. With a finite evidence budget, accurate value estimates are only part of the problem: their errors interact as local credits are converted into a policy update. We characterize this evidence-to-update relationship and show how reliability depends on both evidence covariance and update geometry. We develop Stratified Segment Policy Optimization (S-SPO), which changes the joint design of auxiliary continuations while preserving the operational value target, local-credit rule, and continuation count per query. Under an explicit independence and reuse contract, equal-mass stratification guarantees non-increase of every fixed linear quadratic update risk; a first-order guarantee with a controlled remainder extends the analysis through normalization. At nine continuations per query, S-SPO improves full-parameter frozen-gradient reliability. Across three matched RhoMath-1.1B training seeds, it raises fixed-endpoint validation accuracy by 2.75 percentage points on average and official GSM8K test accuracy by 2.26 points, with every seed pair positive on both evaluations. A second-model comparison on Llama-3.2-1B-Instruct yields a 2.85-point validation gain. These results connect the design of finite continuation evidence to reliable local credit and improved learning.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning for language models, Local credit assignment, Policy gradient estimation, Stratified sampling, Variance reduction

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_nKBZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Stratified Segment Policy Optimization (S-SPO), which replaces independent auxiliary continuations in SPO with equal-mass stratified arithmetic sampling. It characterizes how value-estimation errors propagate through local-credit construction into policy updates, establishing exact covariance-based guarantees for frozen linear updates and a first-order extension through normalization. Experiments demonstrate improved full-parameter gradient reliability and consistent GSM8K accuracy gains across three RhoMath training seeds, supplemented by one matched Llama comparison.

Critical strengths
  • A precise analysis of local-credit reliability. The paper explicitly accounts for covariance, evidence reuse, and update geometry, explaining why value-level error alone is insufficient to characterize gradient reliability. Its distinction between exact linear guarantees and conditional nonlinear improvements makes the theoretical contribution credible.

  • Carefully controlled empirical validation. The principal comparisons match the arithmetic decoder, continuation budget, and downstream SPO pipeline. Full-parameter gradient measurements, paired pool-level inference, and three positive RhoMath seed pairs on the official GSM8K test provide complementary evidence that the intervention improves both estimation and learning.

Critical weaknesses
  • The incremental contribution and practical informativeness of the theory remain limited. Stratified arithmetic sampling is already established in prior work, including QuasiMoTTo. The main addition is therefore its analysis and application within the local-credit pipeline. However, the normalized-update guarantee is only first-order, and its sufficient finite-budget condition is not evaluated at the experimental operating point. Although these limitations are acknowledged, the analysis provides limited quantitative guidance about when its guaranteed linear improvement translates into improved nonlinear updates.

  • The empirical study establishes effectiveness in a narrow configuration. All online experiments use GSM8K, the principal intervention comparison fixes N=9N=9, and the second model has only one matched run. Sensitivity to continuation budget and arithmetic token ordering—which directly affect the variance reduction—is not established. Comparisons with alternative dependent samplers within the same SPO pipeline are also absent, leaving the robustness and relative practical merit of this particular sampling design unresolved.

Questions for authors
  • In the frozen-gradient experiments, how accurately does the first-order risk predict the measured normalized-gradient error? Is the sufficient finite-budget improvement condition satisfied in any observed pools?

  • How sensitive are the reliability and accuracy gains to the continuation budget and token ordering? Can the existing measurements identify configurations in which stratification provides little benefit?

  • How does equal-mass stratification compare with another dependent sampler, such as randomized lattice sampling, under the same auxiliary-query budget and SPO pipeline?

2 comments
AuthorsOpenReview ↗

Response to Reviewer nKBZ

We thank the reviewer for acknowledging the theoretical analysis and controlled empirical design. We clarify the contribution beyond classical stratification, the interpretation of normalized-gradient evidence, and the scope of our robustness claims.

  1. Novelty and Theoretical Contribution

We agree that stratification and its standard variance-reduction properties are established. Our contribution is not a new stratification primitive, but an analysis of how finite auxiliary-continuation noise affects policy updates through SPO's local-credit construction. Equation (3) shows that shared-boundary estimation errors enter adjacent credit differences with opposite signs and that their raw-gradient impact depends on adjacent segment-score differences. Theorem 1 connects evidence covariance and fixed boundary reuse to exact quadratic-risk guarantees for fixed linear updates. Crucially, lower value variance does not imply unconditional improvement after nonlinear normalization: Theorem 2 provides a first-order guarantee with an explicit remainder, and Appendix C gives a counterexample. These results identify the update-reliability problem, characterize its error-transport mechanism, and delineate where classical variance reduction does and does not suffice. S-SPO is a controlled intervention informed by this analysis, not the sole claimed contribution.

  1. Normalized-Gradient Guarantee and Direct Evidence

We agree that a first-order guarantee need not quantitatively predict realized nonlinear update risk. Theorem 2 bounds the discrepancy between first-order and actual risks using an explicit remainder; its sufficient condition for finite-sample improvement was not verified at N=9. However, our experiments directly measure full-parameter gradient direction against a high-budget Full128 reference rather than relying on that approximation. In 24 independent pools with matched N=9 sampling, gradient cosine rises from 0.8215 (M1) to 0.8466 (M2), with a paired 95% CI for the gain of [0.0091, 0.0431] and improvement in 20/24 pools. Using the exact unit-vector identity ||u-v||^2 = 2(1-cos(u,v)), these mean cosines correspond to mean squared unit-direction distances of 0.3570 and 0.3068, a 14.1% reduction relative to the same finite reference. Raw-gradient quadratic error also decreases by 12.5%. This is an algebraic restatement of the observed cosine, not an independent experiment, a comparison against an exact expected gradient, or a validation of Theorem 2's remainder. It directly supports improved measured directional agreement in the tested frozen contexts, without assuming first-order accuracy.

  1. Sampling Robustness and Empirical Scope

We distinguish theoretical guarantees from the size and generality of observed gains. Theorem 1 is not specific to N=9: its relative variance and fixed-linear-risk conclusions apply under the stated stratum-input laws, independence across primitive queries, and fixed reuse. Changing N or token ordering can alter how rewards map to strata, affecting the magnitude of improvement without by itself invalidating the conditional guarantee. Randomized lattice and other dependent samplers may also be effective, but have different dependence structures and were not compared; we make no optimality claim. Empirically, the 24-pool gradient study is complemented by three matched RhoMath training-seed pairs, giving mean gains of 2.75 percentage points on validation and 2.26 points on the official GSM8K test, all positive. One matched Llama-3.2-1B-Instruct pair adds a 2.85-point validation gain. Both online settings use GSM8K, and the Llama result has only one paired seed. Our conclusions therefore distinguish proven conditional guarantees, measured gains in the evaluated settings, and untested generalization across tasks, scales, and samplers.

Thank you for the detailed response and clarifications. But two points remain unresolved:

  1. Theoretical validation: Could the authors quantify how closely the first-order risk approximates the actual normalized-gradient error at N=9N=9, and whether the sufficient finite-budget improvement condition holds in any of the evaluated pools?

  2. Sampling robustness: Could the authors evaluate how the gains from S-SPO vary across different continuation budgets and token orderings, particularly whether certain configurations yield negligible improvements over arithmetic-iid sampling?

Reviewer_J7UmOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The context of this paper is LLM Reinforcement Learning in cases where where we want to assign credit to partial sequences based on a verification of the final answer but use no value function, just rollouts (Monte Carlo estimates). This could also be seen as computing a the per-step supervision for a Process Reward Model and using this supervision directly on the policy we want to train instead of training a separate PRM. The main contribution is an analysis of how errors in the rollout-based prefix values propagate through the differences of consecutive values into the policy update. As a solution, it proposes stratified sampling of the continuations from each prefix lowers which mitigates this effect and reduces the variance of each estimate.

The idea seems sound, but unfortunately the experimental setup is far from the minimum acceptable.

Critical strengths
  1. The proposed application of stratification to overcome the effects of value estimation error seems sound and justified.

  2. It has a good related work section with some exceptions like older works adressing this problem or related areas like PRM training

Critical weaknesses
  1. The experimental setup is really far from an acceptable minimum. Models used (RhoMath-1.1B, Llama-3.2-1B) are 2 years old. For the math domain targeted this is a difference between night and day. Bare minimum would be a reasoning model, but these have very long trajectories so results may not transfer. Benchmark is GSM8K which is long fully solved and too simple. The paper also lacks basic baselines beyond its own method. It also does not do comparisons considering computational cost, which can be assumed to be relevant given we have to rollout per segment. The SPO control also scores about 7 points below the published SPO number, and the second model has a single run.

  2. While sound, the idea is a bit incremental. It basically incorporates a well known solution, stratified sampling, to the specific problem of empirical prefix credit assignment in LLM RL. The cited QuasiMoTTo seems to do this as well.

Questions for authors

I have no questions

2 comments
AuthorsOpenReview ↗

Response to Reviewer j7Um

We thank the reviewer for the assessment. We address the concerns about novelty, experimental scale, baseline strength, and computational cost.

  1. Scientific Contribution

We agree stratified arithmetic sampling is established and do not claim to invent it. Our contribution is to identify and quantify how finite auxiliary-continuation noise propagates through SPO's shared-boundary contrasts and reuse into policy-update error. Eq. (3) shows that an interior boundary error is weighted by adjacent segment-score differences; consequently, value MSE does not alone determine gradient reliability. Theorem 1 gives covariance-to-risk guarantees for fixed linear updates, while Theorem 2 addresses normalization through a first-order bound with explicit remainder. Appendix C supplies a counterexample to unconditional nonlinear improvement. The contribution is therefore a mechanism-level analysis and a controlled intervention, not a new stratification primitive.

  1. Experimental Design and Scope

The goal is to test whether improving finite continuation evidence improves local-credit updates, rather than to maximize benchmark accuracy. We adopt the RhoMath-1.1B/GSM8K setting of the original SPO-chain study to make the comparison interpretable. Within each training pair, M1 (arithmetic-iid SPO) and M2 (S-SPO) share the decoder, N=9 continuation budget, credit rule, optimization objective, and training recipe; only the joint sampling design changes. Moreover, we measure full-parameter gradients directly rather than inferring update reliability from accuracy. Larger models and harder tasks would strengthen external validity, but their absence does not negate the direct evidence within this explicitly scoped controlled setting.

  1. Existing Evidence and Computational Cost

The independent 24-pool study evaluates full-parameter frozen gradients of a 1.1B model. At the same N=9, normalized-gradient cosine increases from 0.8215 to 0.8466 (paired 95% CI of the gain: [0.0091, 0.0431]; improvement in 20/24 pools), while raw-gradient quadratic error decreases by 12.5%. Across three matched RhoMath seed pairs, validation and official GSM8K test scores improve on average by 2.75 and 2.26 percentage points, respectively; every pair improves. All reported dense validation checkpoints from iterations 64 to 256 and all three validation AUCs favor M2. A second-model Llama-3.2-1B-Instruct experiment yields +2.85 points on validation, with only one paired run. Contrary to the concern that compute costs are not reported, Appendix G, Table 9 lists active GPU-hours for all eight runs; complete-run time increases are 1.07%-3.59% for RhoMath and 2.04% for Llama. These are not isolated sampler-overhead or cross-budget cost-optimality claims.

  1. Training Horizon and Baseline Interpretation

Both RhoMath methods run for the same 256 policy iterations and 4,096 optimizer updates. The original SPO paper's 56.7% GSM8K result is not identified as the 256-iteration endpoint, so comparing it directly with our 49.71% control is not a matched-horizon assessment (Appendix F.7). Our online baseline is M1, not the original ancestral-iid M0; Appendix A.3 reports a separate M0/M1 marginal diagnostic, not equivalence of complete training trajectories. We do not claim that longer training, larger models, or other tasks are already validated. The evidence supports the matched M1/M2 comparison over the evaluated horizon.

In summary, our paper combines a concrete update-reliability problem, scoped theory, direct gradient measurements, and consistent paired online outcomes. We ask that the contribution and the empirical evidence be assessed against this stated scope, while recognizing the acknowledged limitations.

I thank the authors for their response. The weak experimental issues are not solved and I'll keep my score.

Reviewer_LHU9OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Methods like SPO estimate the value of an intermediate prefix by sampling N continuations and averaging their success, then use value differences between adjacent prefixes as local credit. With small N, these estimates are noisy and make the gradient direction less accurate. The paper proposes S-SPO: arithmetic sampling maps each continuation to a number in [0, 1), the interval is split into N equal parts, and one continuation is drawn from each part, so the N continuations cover different paths more evenly. The value estimate stays unbiased but has lower variance, and the rest of the training pipeline is unchanged. On RhoMath-1.1B with N = 9, the gradient direction moves closer to a high-budget reference. Across three paired seeds, GSM8K validation accuracy improves by 2.75 points on average and official test accuracy by 2.26 points. One run on Llama-3.2-1B improves validation accuracy by 2.85 points.

Critical strengths
  1. The method only changes how continuations are sampled. The value estimate stays unbiased, the credit rule and training objective are unchanged, and training time increases by only about 2%, so it is easy to add to existing methods.
  2. The experiments are solid. The authors first measure the reliability gain on frozen gradients, then run three paired online training seeds, all of which improve on both validation and the official test set. They also check that arithmetic sampling matches standard sampling in distribution.
Critical weaknesses
  1. The novelty is limited. Variance reduction from stratified sampling is a classical result, stratification with arithmetic sampling already exists (Vilnis et al., 2023), and QuasiMoTTo has already used it for GRPO training. Theorem 1 essentially says that smaller variance does not lead to larger error after a fixed linear map, which is fairly direct.
  2. The experiments are narrow. They cover only GSM8K and models around 1B, Llama has only one run, and the only baseline is SPO with standard sampling. Training stops at 256 iterations, and SPO's test accuracy of 49.71% is below the 56.7% reported in the original paper, so it is unclear whether the gain holds with longer training. In addition, value MSE drops by only about 10% while online accuracy rises by 2.75 points, and the paper does not explain how these relate.
Questions for authors
  1. A 10% drop in value MSE is roughly what standard sampling would get by raising N from 9 to 10. How does S-SPO compare online with standard-sampling SPO at N = 10 or 12?
  2. Arithmetic sampling uses up some numerical precision of u at every token. For continuations of up to 1024 tokens, do the later tokens still follow the model distribution exactly? The distribution check in the appendix uses a 512-token cap.
2 comments
AuthorsOpenReview ↗

Response to Reviewer LHU9

We thank the reviewer for recognizing the controlled design, consistent paired-seed gains, and modest training overhead. We clarify the scientific contribution and the limits of the evidence below.

  1. Novelty and contribution

We agree that stratified arithmetic sampling is established, including its use in GRPO; we do not claim to invent it. Our starting point is a different scientific question: how finite auxiliary-continuation noise affects the reliability of local-credit policy updates. Equation (3) shows that error at a shared boundary enters adjacent credits with opposite signs, and its raw-gradient effect depends on the difference between neighboring segment-score vectors. Thus, value MSE alone does not characterize update error. We formalize error propagation through reuse, contrasts, and update geometry (Theorem 1), then analyze nonlinear normalization via a Jacobian, a first-order bound with explicit remainder, and a counterexample to unconditional finite-budget improvement (Theorem 2; Appendix C). The independent 24-pool study also shows that this problem is substantial in practice: at N=9, relative gradient error is 0.5970 and gradient cosine is 0.7959. Our contribution is therefore the identification, analysis, and measurement of an update-reliability problem, together with a controlled intervention, not the sampling primitive alone.

  1. Sampling budget and practical benefit

We agree that increasing iid N from 9 to 10 reduces ideal sample-mean variance by 10%, comparable to our 9.7% reduction in value MSE. We do not claim that S-SPO outperforms iid N=10 or 12 without direct comparisons. However, similar aggregate value-MSE reductions need not yield identical gradient errors or online outcomes because boundary reuse, score geometry, and normalization matter. At the same N=9, S-SPO improves full-parameter normalized-gradient cosine from 0.8215 to 0.8466 (paired 95% CI for the gain: [0.0091, 0.0431]; 20/24 pools improve) and reduces raw-gradient quadratic error by 12.5%. Across three matched RhoMath seeds, validation and official GSM8K test accuracy improve by 2.75 and 2.26 percentage points on average, respectively. We do not posit a formula converting value-MSE improvement into accuracy gain. Table 9 reports 1.07%-3.59% additional active training time for RhoMath runs. These results establish benefits at fixed continuation count, not cost-optimality versus larger iid budgets.

  1. Experimental scope and baseline

We chose the published SPO-chain RhoMath-1.1B/GSM8K setting to examine the sampling change under a matched protocol. Beyond the three RhoMath seed pairs and official test evaluation, we report full-parameter gradient measurements and one paired Llama-3.2-1B-Instruct validation comparison (+2.85 points). In all RhoMath pairs, every recorded dense validation checkpoint from iteration 64 through 256, and the validation AUC, favors S-SPO. The original SPO paper's 56.7% test result is not identified as a 256-iteration endpoint, so it is not a matched-horizon comparison to our 49.71% baseline (Appendix F.7). We acknowledge that cross-task generalization, longer training, and multiple Llama seeds remain untested. Our claim is specifically about arithmetic-iid SPO (M1) versus S-SPO (M2) within the matched study.

  1. Finite-precision arithmetic decoding

We agree that ideal arithmetic sampling and finite-precision implementation must be distinguished. Appendix A.3 reports an M0/M1 decoder control under a 512-token cap, covering 94 boundaries and 3,008 continuations per method. All ten paired confidence intervals fall within predefined equivalence margins, supporting marginal agreement on the tested statistics. Importantly, exact fidelity to the ideal continuation law is not required for the relative variance guarantee. For a fixed finite-precision decoding map, the stratification result still holds relative to iid sampling through the same map, provided the required input distributions and independence assumptions are satisfied. The preserved target is then the distribution induced by that map, rather than necessarily the ideal law. Both M1 and M2 use the same arithmetic decoder, isolating the joint sampling design. While the existing diagnostics do not establish exact distributional fidelity at 1024 tokens, this limitation does not by itself invalidate the relative variance-reduction guarantee underlying our comparison.

Thank you for the response, but my concerns remain unresolved, so I will keep my rating unchanged.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.