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