acceptodds
Under review as a conference paper at ICLR 2027

Beyond averaged policy gradients: RLVR learns dense parity from final rewards

Abstract

While reinforcement learning with verifiable rewards (RLVR) has achieved striking empirical success, a fundamental theoretical question remains open: when/how can final correctness alone provide an effective learning signal? In this work, we demonstrate that the limitation of ordinary Group Relative Policy Optimization (GRPO) in this setting is an optimization failure rather than an information deficit. Focusing on dense parity as a benchmark, we first prove that the population policy gradient underlying standard GRPO suffers from exponential decay, leaving an exponentially weak learning signal under the standard relative-reward mechanism. To resolve this, we introduce Verifier Posterior Transport (VPT), a sequential RLVR framework that executes a KL-regularized policy update after every example. Unlike GRPO, VPT guarantees a fixed, non-vanishing log-odds gain between successful and failed executions using only the exact same binary final reward. We construct a recursive transformer that realizes VPT exactly and prove that the example complexity required for target recovery scales linearly with input dimension at fixed confidence. Our results demonstrate that dense parity can be learned with linear sample complexity without intermediate supervision. Ultimately, this reveals that the bottleneck in final-reward RLVR is not whether the verifier holds sufficient signal, but how the update rule transforms that information into a learning signal.

Primary area:
learning theory
Keywords:
RLVR, policy gradient, parity learning, learning theory

Reviews

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

This paper studies learning from final rewards over a finite class of parity programs. By parity orthogonality, the ordinary population policy gradient is proportional to the current probability assigned to the target program. The proposed Verifier Posterior Transport (VPT) update instead exponentially reweights programs according to their reward on each example. The authors prove concentration on the target after O(d) examples, construct a recursive transformer that represents these updates, and illustrate the separation numerically.

Critical strengths
  • The distinction between information available in the feedback and information preserved by an update rule is worth studying. The dense parity setting makes the cancellation in the population gradient particularly transparent.

  • The central calculations are relatively easy to inspect. The gradient identity, KL-regularized update, and finite-class concentration argument fit together coherently. I did not identify an issue with the basic reward-separation argument in Theorem 4.

  • The paper explicitly states several important modeling choices, including the restricted program class and the exclusion of Gaussian elimination. This helps clarify the scope of the results.

Critical weaknesses
  • The results establish sample efficiency, but computational efficiency remains unresolved. The experiments enumerate an exponentially large candidate class, and the paper does not provide an efficient procedure for sampling from the resulting policy or recovering the target program.

  • The comparison changes both the aggregation of examples and the policy update rule, making the source of the improvement difficult to isolate. In particular, batch and sequential VPT yield the same final distribution, so the results do not establish that sequential processing itself is responsible for the improvement.

  • The analysis does not fully substantiate the claims about standard GRPO. Theorem 1 assumes input-independent program probabilities, excludes finite-group normalization and clipping, and bounds the gradient only at uniform initialization. A small gradient at initialization is insufficient on its own to establish slow learning over the course of training.

  • The standard-transformer experiment introduces a separate trainable bias for every candidate program. These biases alone can parameterize the distribution over candidates, leaving the transformer's contribution unclear. A bias-only baseline is needed to determine whether the reported behavior depends on the transformer.

Questions for authors
  • What is the computational cost of sampling a program from the updated policy and using it to make a prediction without enumerating the candidate class? If no polynomial-time guarantee is available, could the abstract and conclusions consistently distinguish sample efficiency from computational efficiency?

  • Under the same reward access and computational accounting, how do population KL improvement and ordinary policy gradient applied example by example compare with VPT? Which of the claimed separations remain under these comparisons?

  • Can a model containing only the per-program biases reproduce Figure 1(a)? After including this control, what evidence remains for a learning phenomenon specific to the transformer?

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

The paper proposes VPT for dense parity learning from final rewards and proves linear example complexity. However, the claimed explanation of GRPO’s limitations and broader RLVR implications exceed the evidence.

Critical strengths

The distinction between informative verifier feedback and effective optimization is theoretically relevant.

The stylized analysis is clear, and numerical checks support the exact construction.

Critical weaknesses

The comparison confounds sample aggregation with optimization geometry. Remark 3 establishes batch–sequential equivalence, while population natural-gradient updates also avoid the target-probability factor.

VPT uses classical exponential weights followed by a standard concentration argument, the theoretical contribution is unclear.

Theorem 1 does not establish a learning-complexity barrier for actual GRPO.

Independent program biases can represent the entire policy, leaving the transformer's contribution unverified. I think bias-only and shared-network-only ablations are needed for clear pre.

Experiments enumerate exponentially many candidate programs. The linear example bound therefore leaves computational efficiency and applicability to finite-rollout RLVR unresolved.

Questions for authors

refer the weakness

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

This paper studies whether dense parity can be learned from binary final correctness rewards despite the exponentially weak population policy gradient at uniform initialization. The authors show that, under a program-distribution parameterization, the population gradient underlying ordinary policy gradient is proportional to the target program's probability. They propose Verifier Posterior Transport (VPT), a sequential KL-regularized update that multiplicatively reweights candidate programs according to their correctness on each example. They construct a recursive transformer that exactly realizes this update and establish an O(d + log(1/δ)) sample-complexity guarantee for target recovery under the stated assumptions. Experiments with small parity dimensions support the predicted gradient separation and linear sample scaling. The main contribution is a theoretical distinction between verifier information and how optimization incorporates that information.

Critical strengths

1. A precise characterization of the population-gradient bottleneck.

Theorem 1 establishes that the population gradient reduces to qθ(p)∇θlog⁡qθ(p)q_\theta(p)\nabla_\theta\log q_\theta(p), explaining its exponential decay at uniform initialization under the stated parameter-gradient bound. Theorem 2 then shows that the KL-regularized update produces a fixed 2β2\beta log-odds gain between successful and unsuccessful programs. This provides a clean mathematical illustration of how informative verifier feedback can be poorly utilized by a particular optimization geometry.

2. A concrete realization with a provable sample-complexity guarantee.

Theorem 3 explicitly realizes VPT through a recursive transformer, while Theorem 4 proves target concentration after O(d+log⁡(1/δ))O(d+\log(1/\delta)) examples. These are constructive results rather than purely heuristic arguments. Figure 1 supports the theoretical separation, and the sample-scaling experiment reports successful recovery across all 20 trials at each tested dimension. This gives the work a solid theoretical core despite its restrictive setting.

Critical weaknesses

1. The positive result relies on a particularly informative reward interface and an exponentially large hypothesis representation.

VPT in Eq. (17) reweights every candidate using its reward ρt(A)\rho_t(A). In this binary parity setting, the correctness bit for a sampled program, together with its known prediction, determines the true label: yt=(2Rt(A)−1)A(xt)y_t=(2R_t(A)-1)A(x_t). Consequently, one verifier response effectively reveals the rewards of all candidate programs. Appendix A.1 explicitly supplies the full signed-reward vector and enumerates all M=(dk)M=\binom{d}{k} candidates. Furthermore, Theorem 3 uses fixed parity-computing features and directly sets ct=βytc_t=\beta y_t, rather than learning this update through ordinary gradient optimization.

These choices are legitimate for the stated construction, but substantially limit its relevance to general RLVR, where a failed execution usually does not reveal the correct response or the rewards of alternative executions. The result establishes sample efficiency in a specialized full-information-equivalent setting, not computational efficiency or a generally implementable RLVR training algorithm. The additional contribution beyond standard exponentiated-weights learning over a finite hypothesis class should also be clarified.

2. The comparison does not establish a corresponding limitation of practical GRPO.

Theorem 1 concerns the population gradient in Eq. (14), explicitly excluding finite-group advantage normalization and clipping. Its exponential norm bound also depends on the parameterization and a polynomial bound on score gradients. Appendix A.4 provides a useful same-example comparison with ordinary logit policy gradient, but this still does not analyze actual finite-group GRPO.

More importantly, Figure 1(a) compares an exact population-gradient update with a natural-gradient implementation of VPT. Appendix A.1 confirms that both methods enumerate all candidates, while the VPT branch uses an approximate linear-system solve. The experiments therefore demonstrate a separation between particular update geometries, not necessarily between deployable GRPO and VPT under comparable computational or verifier-query budgets. The paper itself acknowledges that natural policy gradient can avoid the exponential probability factor. A controlled comparison against finite-group GRPO and appropriate natural-gradient baselines would substantially strengthen the claimed optimization contribution.

Questions for authors

1. Reward information and its generality.

In the parity setting, observing a single correctness bit for a known program appears sufficient to reconstruct yty_t, and hence the complete reward vector ρt(A)\rho_t(A). Is this reconstruction the intended implementation of VPT? Could the authors clarify which conclusions extend to tasks where a binary verifier cannot reveal the correct output or evaluate unexecuted candidate programs?

2. What exactly is learned by the recursive transformer?

Theorem 3 directly assigns ct=βytc_t=\beta y_t, while the transformer uses fixed parity features and an input representation containing the complete training horizon. What should be considered the learned component of this construction? Please clarify its parameter, memory, and computational complexity, and distinguish the new transformer-specific result from standard exponential-weights learning with O(log⁡M)O(\log M) samples.

3. Comparison with GRPO and natural-gradient optimization.

Could the authors provide a small-scale comparison using actual finite-group GRPO, per-example ordinary policy gradient, and natural-gradient or VPT updates under the same parity instances and explicit verifier-query and computational budgets? In particular, it would be helpful to separate the effects of per-example updates, full reward-vector access, and gradient geometry. This would clarify whether the empirical advantage is specific to VPT or follows from known natural-gradient behavior.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.