acceptodds
Under review as a conference paper at ICLR 2027

The Variance Cost of Partial Reward Verification in Group-Based Policy Optimization

Abstract

Partial reward verification can preserve a complete-label finite-batch surrogate gradient in expectation while increasing its error at a fixed verification cost. We study when the information purchased by an audit compensates for its cost, taking the fully verified finite-batch surrogate gradient as the target. Using established unbiased estimators, we express this comparison as a threshold on residual-gradient reduction and evaluate it with direct measurements of all 7.37 million trainable LoRA coordinates. A fixed two-stage rule has 2.20–2.77 times the cost-matched whole-group MSE on four BIRD development batches: its first audit creates gradient error in groups whose complete reward vectors are constant. A separate 128-task test shows that cost accounting can reverse the ranking of a frozen whole-group allocation, from an MSE ratio of 0.720 at SQL-body CPU to 1.076 at complete verifier-child CPU. Finally, arithmetic-risk predictors improve development comparisons but do not confirm that gain on 64 tasks from eight additional databases. Together, these fixed-gradient experiments identify residual reduction, the execution cost boundary, and budget transfer as distinct requirements for economical verification.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, reward verification, group-based policy optimization, gradient variance, verification cost

Reviews

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

This paper is about not verifying all responses in GRPO.

Critical strengths

The paper uses a 3B model for experiments.

Critical weaknesses

Introduction: Many terms in the introduction are non-standard and used without any explanation. For example, “reference verification,” “randomized telescoping,” “audit randomization.” Generally the wording is quite dense and difficult to follow.

Problem setup:

rir_i should be defined. What are “reference labels”, and more broadly, what are “labels”? Generally for this kind of setup, there are verifiable rewards, and I am unfamiliar with the terminology of “labels” in RL. Also, the term “stopping variable” is used without definition and should be clearly defined. What is the significance of ℓ^\hat \ell, and why write it as a telescoping sum? What is MSEtwoMSE_{\text{two}} and MSEgroupMSE_{\text{group}}?

On the motivation: To my knowledge and based on works cited, the motivation for this paper is weak. My understanding is that the authors tested whether one needs all rewards in GRPO to approximate the surrogate objective’s gradient, assuming that waiting for verification is a bottleneck. First, the examples of verification given here use CPU resources, which tend to be extremely cheap compared to GPU resources. Second, it is not clear that any solution to requiring fewer verifications would result in a reduced time to train with GRPO. Particularly, authors do not show how reducing CPU cost improves total resource usage or elapsed training time. Methods such as asynchronous GRPO allow GPU usage to be parallelized with CPU verification. Additionally, authors do not report full training runs using any of their methods, and hence it is not sufficiently evaluated. Lastly, not verifying all responses from the LLM brings into question why one would even ask for many responses from the LLM. For example, if one generated fewer responses but verified all responses, would this be a better use of resources?

Questions for authors

See above

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

I found this paper challenging to interpret, so I'll try and provide a more detailed summary of the paper so the authors can clarify whether I my understanding of the content is correct.

This paper examines the issue of partial reward verification in group-based policy optimisation. Specifically, this work aims to examine scenarios where there is compute cost associated with determining the reward of policy outputs, and assesses a number of methods that try to efficiently use a limited cost budget to maximise the accuracy of a gradient estimation, when only partial reward is possible. This work frames this problem around comparing the mean-squared error of gradients computed using partially verified rewards to the gradient computed when all rewards have been verified.

The paper proposes two main Strategies to handling how to use a limited reward verification budget.

  1. Verify a single reward in a group, and infill the rest of the unknown rewards with a fixed value, and compute gradients using this partially-verified group. Then, with probability qq, verify the rest of the group
  2. With probability pp, verify the rewards for the whole group. Otherwise, don't compute gradients.

In Section 5, the authors compare these two methods and examine under what conditions the first strategy. is effectively. Specifically, they highlight that, for Option 1 to be effective, the MSE reduction induced by the single-reward verification must outweigh the additional computation cost by computing this. This section shows that a), at least in this setting, this strategy does not justify the additional compute costs, and b) The strategy can actually increase MSE, depending on what is chosen to infill the unknown rewards.

In Sections 6 and 7, the authors further explore the second strategy (of only verifying whole group rewards). Specifically, the paper considers whether performance improvements can be found by adjusting the probability of group selection based on both predicted cost and predicted risk. Section 6 focuses on just using predicted cost to adjust whole group verification probability, and finds that the effectiveness of this method over the baseline depends on how the verification cost is actually measured (e.g. just the SQL execution, or the complete child process). Section 7 introduces predicted risk into the group selection model, and shows performance improvements over the cost-only model in the development setting, but not when these models are frozen, and transferred to a new set of tests. This section also flags that the cost prediction model underestimates costs, and so the model uses close to the budget of verifying all groups.

Critical strengths

This paper presents an interesting line of research in how to address a limited budget for reward verification, and proposes a number of methods that aim to more efficiently select which specific rewards to verify.

The paper also does provide detailed results on the effectiveness of the methods explored in this paper, with relevant comparisons to baselines. Evaluating gradient MSE seems like a much more interpretable technique of evaluation, compared to alternatives such as evaluating policy performance after training, as the relative performance of each method can be more directly compared.

Critical weaknesses

Lack of Clarity

This paper has a number of weaknesses, but one of the primary issues I had with reading this paper is I found it extremely difficult to follow. This may be reflective of my lack of experience in this specific area of research, but I found the paper to be somewhat jargon-heavy. I would suggest the authors aim to provide a more high-level, interpretable outline of their methodology that introduces the ideas of the paper more clearly.

I found the narrative of the paper to be somewhat disjointed. The introduction of the paper largely focuses on the two-stage verification process (e.g. Section 5), but a large proportion of the paper instead focuses on whole group sampling (Sections 6, 7). I found in my initial reading of the paper that it was not immediately clear that Section 5 was the only part of the paper exploring the two-step verification. It would have been very beneficial if the paper structure had been more clearly established in the introduction. I apologise if I have misinterpreted this - please let me know if this is misrepresenting the paper.

Unsuccessful Empirical Results

The other main weakness of the paper is that the paper is largely only presenting negative, or inconclusive results. Whilst there is clearly some value in presenting results such as these, I don't think the paper currently represents a particularly significant contribution.

Currently, the results presented in Section 5 clearly show that two-step verification is ineffective compared to random, whole group sampling. It also shows that the gradient MSE of groups where only a single reward is verified appears highly dependent on what value is used to infill the unknown rewards. Perhaps the efficacy of this method could be improved with a structured way of choosing the infill value, but this does not appear to have been explored.

The results presented in Sections 6 and 7 do show improvement over naive sampling of which whole groups to verify under certain conditions, but largely show very comparable performance to the naive baseline.

I think for a negative result such as this to represent a significant contribution, the paper would have to convincingly demonstrate that naive sampling of whole groups for verification is consistently the most effective method over a broad range of possible alternatives, and provide a convincing argument as to why this is the case. As it is, the paper provides three alternative methods for partial verification (two-step, cost-only sampling, cost+risk sampling), and shows they are largely ineffective, but this really only convinces me that these specific methods don't work, rather than demonstrating a more general result.

Questions for authors
  1. Is my summary of the work accurate? Please let me know any errors I have made in interpreting this work so I can ensure my understanding of the content of this work is correct. As I outlined above, I found this paper challenging to follow, and so if I have misrepresented the paper in this review, I would appreciate the authors correcting my understanding so I can update my assessment of the paper accordingly.

  2. How does the cost of reward verification actually compare to the cost of computing gradients and performing policy updates? Is verification time a significant proportion of training time in a full RL loop? If you were to increase the size of the model being trained, verification cost surely becomes proportionally less significant to training time. My interpretation of the paper was that the computation cost was specifically focused on verification cost, but please correct me if this is wrong.

  3. Following up on the previous question, is time required to compute gradients considered when comparing partial group reward verification and whole group reward verification (e.g. Section 5), as if only a single reward is verified in a group, it the full gradient still needs to be computed, whereas no gradients need to be computed when a group has no verified rewards.

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

This paper investigates whether partial reward verification can reduce computational cost in group-based policy optimization (such as Group Relative Policy Optimization, or GRPO) without inflating gradient variance. In tasks such as coding (APPS) or text-to-SQL (BIRD), executing every candidate solution in a sandbox is computationally expensive. While unbiased statistical estimators (such as randomized telescoping sums) can mathematically recover the fully verified gradient in expectation, the authors examine whether the variance reduced by partial audits actually justifies their cost, formalizing this tradeoff as a concrete break-even threshold on residual gradient reduction.

Evaluating Qwen2.5-Coder-3B across 7.37 million trainable LoRA parameters, the authors show that partial verification is counter-productive. Because GRPO standardizes rewards within each group, a prompt where all candidates fail should naturally produce a zero gradient. However, checking only one failed candidate while filling in unverified solutions with a default guess (e.g., 0.5) creates an artificial reward spread. This injects substantial artificial gradient noise, causing two-stage partial audits to suffer 2.20× to 2.77× higher Mean Squared Error than simply auditing entire groups at random. Furthermore, any apparent compute savings are easily erased once real-world system overheads, such as process startup and execution boundaries, are accounted for.

Critical strengths

The problem is timely and provides insights into the working of reinforcement learning with verifiable rewards (RLVR).

Critical weaknesses

The paper is extremely difficult to read and follow. In its current form, the paper is difficult to comprehend. It might have some interesting ideas but in its current form it is not publishable.

Questions for authors
  • The paper is very difficult to follow in its current form.

  • The appendix has a dump of python file paths. It is not clear what purpose they solve, as the supplementary material does not have those files.

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

The authors study when partially verifying the rewards of a GRPO batch is economical, taking the fully verified finite-batch surrogate gradient as the target. Relying on established unbiased estimators (randomized telescoping and Horvitz–Thompson whole-group auditing), they derive a simple criterion (Eq. 4): a two-stage audit beats a cost-matched whole-group audit if and only if its first stage removes a larger fraction of the residual gradient error than the fraction of the budget it consumes. They then evaluate exact conditional gradient MSEs over all 7.37M LoRA coordinates of Qwen2.5-Coder-3B on BIRD text-to-SQL, with measured verifier costs. Three findings are reported: (i) a fixed two-stage rule has 2.20–2.77 times the cost-matched whole-group MSE, partly because revealing one label creates a nonzero gradient in groups whose complete reward vector is constant; (ii) the ranking of a frozen allocation reverses with the cost boundary (MSE ratio 0.720 at SQL-body CPU against 1.076 at complete child-process CPU); and (iii) risk predictors that help on development databases fail a frozen eight-database transfer test.

Critical strengths
  • Careful and honest evaluation. The fixed-gradient design gives exact expectations over the audit randomization, the full LoRA gradients are measured directly rather than projected, and failed pre-declared gates are reported as prominently as successes.
  • A clean criterion and an interesting mechanism. Eq. 4 makes the cost of information explicit, and the observation that intermediate normalization creates variance in constant-reward groups, whose complete gradient is zero, is a useful and somewhat counter-intuitive point.
Critical weaknesses
  • Limited methodological contribution. The estimators are established, and the authors acknowledge that the closely related study of Zhang (2026) already covers the target, sequential completion and cost-matched whole-group correction. Moreover, Eq. 4 is a one-line consequence of the variance formulas, so the contribution is mainly a set of measurements.
  • The negative result is narrow. The tested two-stage rule always reveals slot 0, completes the unknown labels with a fixed value and continues with probability one-half. Its failure therefore says little about partial auditing in general, and the posterior completion of Zhang (2026) is explicitly not tested.
  • Weak motivation in the chosen setting. Verification costs well under a second of CPU per group, and the paper itself finds that removable group CPU is only about 9% of the measured verifier CPU. It is thus unclear why partial verification would matter for training cost in this setting, and no setting with expensive verifiers (e.g., LLM judges or long test suites) is studied.
  • Conclusions not statistically supported, and no training outcomes. Every reported bootstrap interval crosses one (e.g., [0.232, 1.658] and [0.373, 1.840] for the "reversal"). The reversal itself follows directly from how the matched control is defined, since the candidate's MSE does not change. In addition, all comparisons are fixed-gradient MSEs at one rollout seed and essentially one adapter, with no effect on learning measured.
  • Presentation. The text is very hard to follow, with lab-specific jargon (B8, cohorts, receipts, gates, child CPU) and heavy qualification of almost every sentence. Besides, the supplement does not reproduce gradient extraction or the confidence intervals.
Questions for authors
  1. In which practical RLVR setting is verification cost large enough relative to generation and backpropagation for partial auditing to matter? Could the study be repeated with an expensive verifier?
  2. Does the conclusion hold for adaptive orderings or posterior completion, rather than a fixed slot and a fixed completion value?
  3. Is the cost-boundary reversal more than an accounting effect, given that both intervals contain one and the candidate MSE is unchanged?
  4. Do the gradient-MSE differences translate into any difference in learning curves at matched verification budgets?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.