PROSE: Enhancing Sample Efficiency in Code Generation via Plan-Aware Rollout Reorganization

Group Relative Policy Optimization (GRPO) and related execution-based RL methods for code generation subtract a flat group-relative baseline from every rollout in a group; this baseline is variance-suboptimal as soon as rewards carry latent-plan structure. Programs instantiating the same latent plan tend to succeed or fail together, so execution rewards follow a one-way random-effects mixture whose within-plan intraclass correlation (ICC) ${\rho }_r$ is ANOVA-measurable (${\rho }_r\approx 0.72$ on APPS+, ${\rho }_r\approx 0.48$ on GSM8K). GRPO's i.i.d. rollouts remain marginally exchangeable, so the deficiency lies in the estimator and not in the sampling, but under this mixture the efficient subtractive baseline is plan-conditioned rather than flat. We propose PROSE, which couples explicit plan clustering, posterior-UCB budget reallocation across plans, and an allocation-aware training objective through a single shared plan posterior. Its hierarchical advantage is the uniformly minimum-variance unbiased (UMVU) estimator within the symmetric subtractive class, with a variance-reduction fraction set by ${\rho }_r$. We test this prediction directly: at the training operating point ($k=M=4$, $N=16$) the theory predicts an advantage-variance ratio of $0.262$ against the flat estimator recomputed on the same batch; the measured value on stored rollouts is $0.26$. On LiveCodeBench pass@1, PROSE at $N=16$ ($22.4\pm 0.3$) exceeds GRPO+CoT at $N=32$ ($21.1\pm 0.4$) — strict superiority at half the execution budget — and PROSE at $N=8$ ($20.1\pm 0.3$) exceeds GRPO+CoT at $N=16$ ($18.4\pm 0.4$); against vanilla GRPO, and in execution budget only, PROSE at $N=8$ matches GRPO at $N=32$ under a pre-specified equivalence margin of $\delta =1.0$ pass@1. On mathematical reasoning, where the ICC is lower, the gain is correspondingly smaller, as the diagnosis predicts.