PAIR: Pairwise-Aware Inclusion Reweighting for Adaptive Rollout Allocation in RLVR

# Pairwise-Aware Inclusion Reweighting forAdaptive Rollout Allocation in RLVR
Source: [https://arxiv.org/html/2608.11368](https://arxiv.org/html/2608.11368)
Elena VossAffiliation:University of Wisconsin–MadisonMarcus HaleAffiliation:University of WashingtonSofia ReyesAffiliation:University of Wisconsin–Madison

###### Abstract

Reinforcement learning with verifiable rewards \(RLVR\) spends most of its compute generating groups of long reasoning trajectories\. Recent allocators reduce this cost by assigning budgets to prompts, rollouts, or tokens according to a pointwise notion of difficulty or utility\. We identify a statistical mismatch: the unclipped leave\-one\-out group\-relative score gradient is not a sum of independent point contributions, but a second\-orderUU\-statistic over*pairs*of rollouts\. Completing one rollout therefore reveals contrast with every other completed rollout, and adaptive endpoint selection changes which pair terms are observable\. We introducePair\(*Pairwise\-Aware Inclusion Reweighting*\), which treats short rollout prefixes as vertices and pair\-gradient terms as edges of a contrast graph\. A prefix\-only predictor estimates correctness and remaining token cost; a convex design chooses positive continuation probabilities under an expected suffix\-token budget; and each edge induced by completed vertices is inverse\-weighted by its logged joint inclusion probability\. Under conditionally independent on\-policy rollouts and an unclipped, unstandardized objective, the resulting estimator is design\-unbiased for the complete candidate\-pair gradient\. Across compute\-matched RLVR runs on Qwen3\-1\.7B/4B,Pairimproves average accuracy by\+1\.2\+1\.2and\+1\.4\+1\.4over the strongest pointwise allocator while using51%51\\%and52%52\\%fewer generated tokens than full\-group GRPO\. A frozen\-population estimator audit confirms that unweighted adaptive selection is biased, whereas pair\-inclusion correction recovers the complete\-pair target at matched suffix cost\.

## 1Introduction

Reinforcement learning with verifiable rewards \(RLVR\) has become a central route to reasoning models: a policy samples long solutions, an automatic verifier scores their terminal answers, and a critic\-free optimizer reinforces the better members of each group\([32](https://arxiv.org/html/2608.11368#bib.bib1);[6](https://arxiv.org/html/2608.11368#bib.bib2);[40](https://arxiv.org/html/2608.11368#bib.bib3)\)\. Group\-relative objectives are attractive because they avoid a learned value network, but their cost is dominated by rollout generation, often thousands of autoregressive tokens for every response and several responses for every prompt\. Stabilized critic\-free estimators improve optimization\([14](https://arxiv.org/html/2608.11368#bib.bib4);[22](https://arxiv.org/html/2608.11368#bib.bib5)\), yet do not remove this generation bottleneck\.

A fast\-moving literature consequently asks where to spend rollout compute\. Online filtering tracks whether a prompt is currently learnable\([2](https://arxiv.org/html/2608.11368#bib.bib6);[3](https://arxiv.org/html/2608.11368#bib.bib7)\); predictive selectors infer its future difficulty before generation\([23](https://arxiv.org/html/2608.11368#bib.bib11);[27](https://arxiv.org/html/2608.11368#bib.bib12)\); and adaptive allocators vary group size from predicted variance, hit probability, or progressive observations\([26](https://arxiv.org/html/2608.11368#bib.bib13);[35](https://arxiv.org/html/2608.11368#bib.bib14);[16](https://arxiv.org/html/2608.11368#bib.bib15)\)\. Other methods intervene inside generation by coordinating rollout count and length, or allocating over agentic prefixes\([13](https://arxiv.org/html/2608.11368#bib.bib18);[46](https://arxiv.org/html/2608.11368#bib.bib16)\)\. These approaches differ substantially, but almost all attach utility to a*point*: a prompt, rollout, prefix, or token\.

Group\-relative learning is not pointwise\. For a promptqq, response rewardrir\_\{i\}, and sequence score𝒔i=∇𝜽​log​π𝜽​\(oi∣q\)\\bm\{s\}\_\{i\}=\\nabla\_\{\\bm\{\\theta\}\}\\log\\pi\_\{\\bm\{\\theta\}\}\(o\_\{i\}\\mid q\), the unclipped leave\-one\-out gradient is exactly the average of

𝒉i​j=12​\(ri−rj\)​\(𝒔i−𝒔j\)over all​i<j\.\\bm\{h\}\_\{ij\}=\\tfrac\{1\}\{2\}\(r\_\{i\}\-r\_\{j\}\)\(\\bm\{s\}\_\{i\}\-\\bm\{s\}\_\{j\}\)\\quad\\text\{over all \}i<j\.This pairwise form is a second\-orderUU\-statistic\([11](https://arxiv.org/html/2608.11368#bib.bib29);[43](https://arxiv.org/html/2608.11368#bib.bib22)\)\. It changes the budgeting problem in two ways\. First, a rollout has no intrinsic group\-relative value: its contribution depends on which*other*outcomes are observed\. Second, generation cost is paid per rollout endpoint, while completing one endpoint exposes all pair edges to the other completed endpoints\. Thus value is quadratic and graph\-coupled, although cost is linear in vertices\.

This mismatch also creates an estimation problem\. If an adaptive rule continues only prefixes predicted to produce useful contrast, the observed pair set is informative rather than uniform\. Averaging its gradients as if it were a standard group targets the selected distribution, not the complete candidate pool\. Pointwise importance weighting is sufficient when the target is a sum of independent terms, as in selective token updates or post\-rollout pruning\([29](https://arxiv.org/html/2608.11368#bib.bib23);[44](https://arxiv.org/html/2608.11368#bib.bib17)\); a pair total instead requires the probability that*both*endpoints are observed\. This is the same design\-based distinction that motivates joint inclusion probabilities in unequal\-probability sampling\([12](https://arxiv.org/html/2608.11368#bib.bib28);[30](https://arxiv.org/html/2608.11368#bib.bib32)\)\.

We build on this observation withPair, or Pairwise\-Aware Inclusion Reweighting\.Pairfirst generates a short, independent prefix for every candidate rollout\. Lightweight heads reuse the prefix state to estimate final correctness and remaining suffix cost\. These estimates define a contrast graph: vertices are prefixes and edge weights proxy the second moment of their pair\-gradient kernel\. A convex program assigns every vertex a strictly positive continuation probability under an expected token budget\. After randomized continuation,Pairuses every edge induced by completed vertices and divides its kernel by the edge’s logged inclusion probability\. The correction is exact for a clearly scoped leave\-one\-out score\-gradient target; PPO clipping, reward standardization, and weight stabilization are practical approximations studied separately\.

Our contributions are:

- •We expose an estimator–allocation mismatch in adaptive RLVR: the unclipped leave\-one\-out gradient is pairwise, whereas prevailing budget rules are pointwise\. This yields a contrast\-graph formulation in which suffix cost is paid on vertices and statistical value lives on induced edges\.
- •We proposePair, a prefix\-conditioned randomized continuation design with positive logged probabilities, a graph\-coupled convex allocation surrogate, and pair\-inclusion reweighting that uses all contrasts among completed rollouts\.
- •We prove pairwise equivalence and finite\-population design\-unbiasedness, derive the conditional bias of unweighted selection and the exact design covariance, and establish convexity of the allocation surrogate\. We state precisely where clipping and normalization leave this exact regime\.
- •We validate the correction with a frozen finite\-population estimator audit and matched model\-scale RLVR experiments measuring gradient error, reasoning quality, calibration, robustness, and end\-to\-end cost\.

![Refer to caption](https://arxiv.org/html/2608.11368v1/figures/pair_workflow.png)Figure 1:Pairallocates rollout endpoints for a pairwise estimator\.A short prefix probe estimates correctness and remaining generation cost before terminal rewards are observed\. The contrast\-graph program assigns positive continuation probabilities under a suffix\-token budget\. Completing a vertex exposes every incident edge to other completed vertices, and the update inverse\-weights each observed edge by its logged joint inclusion probability\.
## 2Related Work

#### RLVR and group\-relative optimization\.

RLVR couples outcome verification with policy gradients to improve mathematical and program reasoning\([32](https://arxiv.org/html/2608.11368#bib.bib1);[6](https://arxiv.org/html/2608.11368#bib.bib2);[40](https://arxiv.org/html/2608.11368#bib.bib3)\)\. GRPO replaces a critic with within\-group reward normalization; RLOO and REINFORCE\-style variants instead use leave\-one\-out or global baselines\([1](https://arxiv.org/html/2608.11368#bib.bib36);[14](https://arxiv.org/html/2608.11368#bib.bib4)\)\. Recent analyses identify normalization bias, sparse gradients, and the special role of positive–negative cancellation\([22](https://arxiv.org/html/2608.11368#bib.bib5);[36](https://arxiv.org/html/2608.11368#bib.bib21)\)\. Most directly, the unclipped group\-relative score gradient admits aUU\-statistic representation\([43](https://arxiv.org/html/2608.11368#bib.bib22)\)\. We use that representation as the*measurement target*of an adaptive generation design; we do not claim thatUU\-statistics themselves are new, nor that standard clipped and standardized GRPO is exactly covered\.

#### Prompt selection and rollout allocation\.

Static and online curricula select prompts from difficulty, learning progress, or gradient diagnostics\([2](https://arxiv.org/html/2608.11368#bib.bib6);[3](https://arxiv.org/html/2608.11368#bib.bib7);[7](https://arxiv.org/html/2608.11368#bib.bib25);[38](https://arxiv.org/html/2608.11368#bib.bib26);[24](https://arxiv.org/html/2608.11368#bib.bib27)\), while GPS and DPS predict prompt utility from shared history or a dynamical model\([27](https://arxiv.org/html/2608.11368#bib.bib12);[23](https://arxiv.org/html/2608.11368#bib.bib11)\)\. Selective Rollouts, depth\-adaptive exploration, and response reuse reduce generation on low\-value or mismatched prompts\([42](https://arxiv.org/html/2608.11368#bib.bib8);[39](https://arxiv.org/html/2608.11368#bib.bib10);[41](https://arxiv.org/html/2608.11368#bib.bib9)\)\. VIP minimizes a gradient\-variance objective over group sizes; HORA maximizes posterior hit utility; VIGOR progressively refines high\-variance groups; and cross\-epoch or profiled methods allocate global budgets over time\([26](https://arxiv.org/html/2608.11368#bib.bib13);[35](https://arxiv.org/html/2608.11368#bib.bib14);[16](https://arxiv.org/html/2608.11368#bib.bib15);[45](https://arxiv.org/html/2608.11368#bib.bib19);[34](https://arxiv.org/html/2608.11368#bib.bib20)\)\. TRACE extends allocation to agentic prefix trees\([46](https://arxiv.org/html/2608.11368#bib.bib16)\)\.Pairis complementary in scope: it asks how endpoint selection observes and estimates a pairwise gradient, not merely which point has high predicted utility\.

#### Partial\-trajectory and token efficiency\.

DUET couples prompt\-level allocation with length gates under a shared token budget\([13](https://arxiv.org/html/2608.11368#bib.bib18)\)\. NAT applies Horvitz–Thompson reweighting to token masking\([29](https://arxiv.org/html/2608.11368#bib.bib23)\), whereas DPPO corrects prompt and completion pruning and improves hardware packing\([44](https://arxiv.org/html/2608.11368#bib.bib17)\)\. These works establish the value of randomized selection and correction\.Pairdiffers in both the cost stage and estimand: it saves ungenerated suffixes and corrects the induced*pair*total rather than treating a precomputed advantage as a point label\.

#### Unequal\-probability and pair\-statistic sampling\.

The Horvitz–Thompson estimator recovers finite\-population totals under known positive inclusion probabilities\([12](https://arxiv.org/html/2608.11368#bib.bib28)\); Neyman allocation and rejective sampling characterize variance\-aware and fixed\-size designs\([25](https://arxiv.org/html/2608.11368#bib.bib30);[8](https://arxiv.org/html/2608.11368#bib.bib31)\)\. IncompleteUU\-statistics reduce pair computation through designed subsets\([18](https://arxiv.org/html/2608.11368#bib.bib33)\), and recent work directly samples pairwise losses with auxiliary proxies\([5](https://arxiv.org/html/2608.11368#bib.bib24)\)\. Induced\-subgraph estimation uses the same vertex\-cost/edge\-observation geometry in network statistics\([17](https://arxiv.org/html/2608.11368#bib.bib34)\)\.Pairapplies these established principles to an RLVR\-specific measurement process whose expensive operation is generating the endpoint itself\.

## 3Preliminaries and Problem Setup

### 3\.1Leave\-one\-out group\-relative gradients

For promptq∼𝒟q\\sim\\mathcal\{D\}, letoi∼π𝜽\(⋅∣q\)o\_\{i\}\\sim\\pi\_\{\\bm\{\\theta\}\}\(\\cdot\\mid q\)be an on\-policy response,ri=r⁡\(q,oi\)∈\{0,1\}r\_\{i\}=r\(q,o\_\{i\}\)\\in\\\{0,1\\\}its verifiable reward, and𝒔i=∇𝜽​log​π𝜽​\(oi∣q\)\\bm\{s\}\_\{i\}=\\nabla\_\{\\bm\{\\theta\}\}\\log\\pi\_\{\\bm\{\\theta\}\}\(o\_\{i\}\\mid q\)its sequence score\. The target per\-prompt policy gradient is

𝒈⁡\(q\)=∇𝜽𝔼​\[r∣q\]=𝔼⁡\[ri​𝒔i∣q\]\.\\bm\{g\}\(q\)=\\nabla\_\{\\bm\{\\theta\}\}\\mathbb\{E\}\[r\\mid q\]=\\mathbb\{E\}\[r\_\{i\}\\bm\{s\}\_\{i\}\\mid q\]\.\(1\)GivenGGresponses, the leave\-one\-out \(LOO\) score estimator is

𝒈^LOO\\displaystyle\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{LOO\}\}=1G​∑i=1G\(ri−r¯−i\)​𝒔i,\\displaystyle=\\frac\{1\}\{G\}\\sum\_\{i=1\}^\{G\}\\left\(r\_\{i\}\-\\bar\{r\}\_\{\-i\}\\right\)\\bm\{s\}\_\{i\},\(2\)r¯−i\\displaystyle\\bar\{r\}\_\{\-i\}=1G−1​∑j≠irj\.\\displaystyle=\\frac\{1\}\{G\-1\}\\sum\_\{j\\neq i\}r\_\{j\}\.At the data\-collection policy, this is the unnormalized gradient underlying RLOO and closely related group\-relative updates\. Standard GRPO additionally divides by a random group standard deviation and applies PPO clipping\([31](https://arxiv.org/html/2608.11368#bib.bib35)\); we separate those practical operations from the exact target in Eq\. \([2](https://arxiv.org/html/2608.11368#S3.E2)\)\.

### 3\.2The pair target

LetℰG=\{\(i,j\):1≤i<j≤G\}\\mathcal\{E\}\_\{G\}=\\\{\(i,j\):1\\leq i<j\\leq G\\\},M=\(G2\)M=\\binom\{G\}\{2\}, and define

𝒉i​j=12​\(ri−rj\)​\(𝒔i−𝒔j\)\.\\bm\{h\}\_\{ij\}=\\frac\{1\}\{2\}\(r\_\{i\}\-r\_\{j\}\)\(\\bm\{s\}\_\{i\}\-\\bm\{s\}\_\{j\}\)\.\(3\)The complete pair average

𝒈^pair=1M​∑\(i,j\)∈ℰG𝒉i​j\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{pair\}\}=\\frac\{1\}\{M\}\\sum\_\{\(i,j\)\\in\\mathcal\{E\}\_\{G\}\}\\bm\{h\}\_\{ij\}\(4\)equals Eq\. \([2](https://arxiv.org/html/2608.11368#S3.E2)\) exactly \(Theorem[1](https://arxiv.org/html/2608.11368#Thmtheorem1)\)\. This identity is not merely algebraic bookkeeping: it identifies the finite population that an adaptive collector must estimate\.

### 3\.3Adaptive suffix continuation

For each candidate responseii, generate a prefixzi=oi,1:τz\_\{i\}=o\_\{i,1:\\tau\}using independent policy randomness\. The ungenerated suffix has random token costCiC\_\{i\}, terminal rewardrir\_\{i\}, and full score𝒔i\\bm\{s\}\_\{i\}\. A continuation design observes the prefixes and draws indicatorsJi∈\{0,1\}J\_\{i\}\\in\\\{0,1\\\}; onlyJi=1J\_\{i\}=1responses are completed\. The edge\(i,j\)\(i,j\)is observed whenIi​j=Ji​Jj=1I\_\{ij\}=J\_\{i\}J\_\{j\}=1, with joint inclusion probability

ρi​j=ℙ\(Ji=1,Jj=1∣z1:G\)\.\\rho\_\{ij\}=\\mathbb\{P\}\(J\_\{i\}=1,J\_\{j\}=1\\mid z\_\{1:G\}\)\.We requireρi​j\>0\\rho\_\{ij\}\>0and log the probability used by the sampler before terminal rewards are available\. Under independent Bernoulli continuation,ρi​j=πi​πj\\rho\_\{ij\}=\\pi\_\{i\}\\pi\_\{j\}, whereπi=ℙ\(Ji=1∣z1:G\)\\pi\_\{i\}=\\mathbb\{P\}\(J\_\{i\}=1\\mid z\_\{1:G\}\)\.

## 4Pair

### 4\.1Overview: allocate vertices, estimate edges

Pairhas four stages \(Figure[1](https://arxiv.org/html/2608.11368#S1.F1)\)\. It first draws independent short prefixes for a candidate group\. Prefix heads predict success probability and remaining token cost\. These quantities build a complete contrast graph whose edge weights approximate pair\-kernel energy\. A convex design converts the graph into strictly positive vertex continuation probabilities\. Finally, completed vertices induce an observed subgraph, from whichPairconstructs inverse\-edge\-inclusion\-weighted sequence advantages equivalent to the corrected pair estimator\. The policy and predictor heads are updated only after the probabilities have been logged, maintaining the pre\-outcome randomization required by Theorem[2](https://arxiv.org/html/2608.11368#Thmtheorem2)\.

### 4\.2Prefix statistics

At a fixed checkpointτ\\tau, we feed a stop\-gradient copy of the policy’s final prefix hidden state𝒖i\\bm\{u\}\_\{i\}to two small prediction heads:

p^i=σ⁡\(fϕ​\(𝒖i\)\),c^i=softplus⁡\(gω​\(𝒖i\)\)\.\\widehat\{p\}\_\{i\}=\\sigma\(f\_\{\\phi\}\(\\bm\{u\}\_\{i\}\)\),\\qquad\\widehat\{c\}\_\{i\}=\\operatorname\{softplus\}\(g\_\{\\omega\}\(\\bm\{u\}\_\{i\}\)\)\.\(5\)The first estimatesℙ⁡\(ri=1∣zi\)\\mathbb\{P\}\(r\_\{i\}=1\\mid z\_\{i\}\); the second estimates remaining suffix tokens\. Selected completions supply delayed labels\. Because labels are observed under unequal continuation, the heads use vertex\-level inverse probability losses,

ℒp\\displaystyle\\mathcal\{L\}\_\{p\}=∑iJiπi​Brier⁡\(p^i,ri\),\\displaystyle=\\sum\_\{i\}\\frac\{J\_\{i\}\}\{\\pi\_\{i\}\}\\operatorname\{Brier\}\(\\widehat\{p\}\_\{i\},r\_\{i\}\),\(6\)ℒc\\displaystyle\\mathcal\{L\}\_\{c\}=∑iJiπi​\(log⁡c^i−log⁡Ci\)2\.\\displaystyle=\\sum\_\{i\}\\frac\{J\_\{i\}\}\{\\pi\_\{i\}\}\\left\(\\log\\widehat\{c\}\_\{i\}\-\\log C\_\{i\}\\right\)^\{2\}\.\(7\)We freeze the heads within an RL update and refresh them afterward; a lagged\-predictor variant uses heads from the preceding checkpoint to reduce adaptive overfitting\. Calibration error and drift are explicit diagnostics rather than assumed away\.

### 4\.3The contrast graph

For binary rewards, the predicted probability that two completed suffixes disagree is

d^i​j=p^i​\(1−p^j\)\+\(1−p^i\)​p^j\.\\widehat\{d\}\_\{ij\}=\\widehat\{p\}\_\{i\}\(1\-\\widehat\{p\}\_\{j\}\)\+\(1\-\\widehat\{p\}\_\{i\}\)\\widehat\{p\}\_\{j\}\.\(8\)Disagreement determines whether𝒉i​j\\bm\{h\}\_\{ij\}is nonzero, but not its magnitude\. We therefore allow a nonnegative edge proxy

ai​j≈𝔼\[∥𝒉i​j∥22∣zi,zj\],a\_\{ij\}\\approx\\mathbb\{E\}\[\\\|\\bm\{h\}\_\{ij\}\\\|\_\{2\}^\{2\}\\mid z\_\{i\},z\_\{j\}\],\(9\)implemented either asd^i​j\\widehat\{d\}\_\{ij\}\(the parameter\-free default\), asd^i​j​\(m^i\+m^j\)2/4\\widehat\{d\}\_\{ij\}\(\\widehat\{m\}\_\{i\}\+\\widehat\{m\}\_\{j\}\)^\{2\}/4with a historical score\-norm predictorm^i\\widehat\{m\}\_\{i\}, or as a directly regressed pair\-energy head\. Comparing these choices is necessary because correctness prediction alone need not be variance\-optimal\.

![Refer to caption](https://arxiv.org/html/2608.11368v1/mechanism.png)Figure 2:Mechanism of pair\-aware allocation\.\(a\) Binary reward contrast depends jointly on two prefix success probabilities, not on either endpoint alone\. \(b\)Pairspends suffix cost on vertices; continuing one vertex exposes all incident edges to other completed vertices\. Opacity shows optimized continuation probability and edge width shows the pair\-energy proxy\. \(c\) On the displayed contrast graph, the convex PAIR design reduces its stated variance proxy relative to uniform and pointwise probabilities at equal expected suffix cost\.
### 4\.4Graph\-coupled probability design

If vertices are sampled independently with probabilitiesπi\\pi\_\{i\}, the observed edge receives weight1/\(πi​πj\)1/\(\\pi\_\{i\}\\pi\_\{j\}\)\. Edges sharing a vertex are dependent, so optimizing each edge independently double\-counts reusable suffix generation\. Let

bi=\(∑j≠iai​j\)2−∑j≠iai​j,b\_\{i\}=\\left\(\\sum\_\{j\\neq i\}\\sqrt\{a\_\{ij\}\}\\right\)^\{2\}\-\\sum\_\{j\\neq i\}a\_\{ij\},Ifai​j≥‖𝒉i​j‖22a\_\{ij\}\\geq\\\|\\bm\{h\}\_\{ij\}\\\|\_\{2\}^\{2\}, thenbib\_\{i\}upper\-bounds the shared\-edge cross\-products incident toii\. With predictedai​ja\_\{ij\}, it is instead a covariance surrogate\. Withxi=−log⁡πix\_\{i\}=\-\\log\\pi\_\{i\},Pairsolves

min𝒙Φ⁡\(𝒙\)\\displaystyle\\min\_\{\\bm\{x\}\}\\quad\\Phi\(\\bm\{x\}\)=∑i<jai​j​exi\+xj\+∑ibi​exi,\\displaystyle=\\sum\_\{i<j\}a\_\{ij\}e^\{x\_\{i\}\+x\_\{j\}\}\+\\sum\_\{i\}b\_\{i\}e^\{x\_\{i\}\},\(10\)s\.t\.∑ic^i​e−xi≤C,\\displaystyle\\sum\_\{i\}\\widehat\{c\}\_\{i\}e^\{\-x\_\{i\}\}\\leq C,0≤xi≤−log⁡πmin\.\\displaystyle 0\\leq x\_\{i\}\\leq\-\\log\\pi\_\{\\min\}\.\(11\)The first term controls edge second moments; the second controls covariance from reused vertices\. The feasible set and objective are convex \(Proposition[2](https://arxiv.org/html/2608.11368#Thmproposition2)\), so theGG\-variable problem can be solved with standard constrained optimization\. Iteration counts and overhead are measured separately\. The floorπmin\>0\\pi\_\{\\min\}\>0establishes positivity and caps inverse weights\. With predicted costsc^i\\widehat\{c\}\_\{i\}, the program constrains predicted expected suffix cost; realized cost is evaluated separately\. We evaluate conditional\-Poisson and dependent\-rounding variants when an exact endpoint count is required, using their actual joint inclusion probabilities\.

### 4\.5Induced\-edge correction

After drawingJi∼Bernoulli⁡\(πi\)J\_\{i\}\\sim\\operatorname\{Bernoulli\}\(\\pi\_\{i\}\)and completing the selected suffixes,Pairestimates the full candidate\-pair gradient by

𝒈^Pair\\displaystyle\\widehat\{\\bm\{g\}\}\_\{\\textnormal\{\{Pair\}\}\}=1M​∑i<jJi​Jjρi​j​𝒉i​j,\\displaystyle=\\frac\{1\}\{M\}\\sum\_\{i<j\}\\frac\{J\_\{i\}J\_\{j\}\}\{\\rho\_\{ij\}\}\\,\\bm\{h\}\_\{ij\},\(12\)ρi​j\\displaystyle\\rho\_\{ij\}=πiπj\(independent design\)\.\\displaystyle=\\pi\_\{i\}\\pi\_\{j\}\\quad\\text\{\(independent design\)\}\.All induced edges are used: completingkkvertices yields\(k2\)\\binom\{k\}\{2\}contrast terms at no additional generation cost\. For an implementation expressed as sequence advantages, define

A~i=12​M​∑j≠iJi​Jjρi​j​\(ri−rj\),\\widetilde\{A\}\_\{i\}=\\frac\{1\}\{2M\}\\sum\_\{j\\neq i\}\\frac\{J\_\{i\}J\_\{j\}\}\{\\rho\_\{ij\}\}\(r\_\{i\}\-r\_\{j\}\),\(13\)then optimize∑iA~i​log⁡π𝜽​\(oi∣q\)\\sum\_\{i\}\\widetilde\{A\}\_\{i\}\\log\\pi\_\{\\bm\{\\theta\}\}\(o\_\{i\}\\mid q\)\. The exact theorem applies at the on\-policy score point\. In practical PPO epochs we detachA~i\\widetilde\{A\}\_\{i\}, use trajectory ratios, and report the result as a clipped surrogate rather than an unbiased policy gradient\.

Input:prompt batch; candidate size

GG; checkpoint

τ\\tau; expected suffix budget

CC; floor

πmin\\pi\_\{\\min\}
Output:pair\-corrected policy update and predictor labels

foreach*prompt groupqqin the batch*do

⊳\\trianglerightPrefix probe

generate independent prefixes

z1:Gz\_\{1:G\}to checkpoint

τ\\tau
foreach*candidate vertexi∈\{1,…,G\}i\\in\\\{1,\\ldots,G\\\}*do

predict

p^i\\widehat\{p\}\_\{i\}and

c^i\\widehat\{c\}\_\{i\}from

ziz\_\{i\}
⊳\\trianglerightContrast\-graph allocation

construct

ai​ja\_\{ij\}using Eq\. \([9](https://arxiv.org/html/2608.11368#S4.E9)\) and compute

bib\_\{i\}
solve Eqs\. \([10](https://arxiv.org/html/2608.11368#S4.E10)\)–\([11](https://arxiv.org/html/2608.11368#S4.E11)\) for

π1:G\\pi\_\{1:G\}, then log the probabilities

draw

JiJ\_\{i\}with fresh randomization

foreach*selected vertexiiwithJi=1J\_\{i\}=1*do

resume its KV cache and generate the suffix to termination

⊳\\trianglerightPair\-corrected update

verify completed responses and enumerate all induced edges

foreach*observed edge\(i,j\)\(i,j\)*do

accumulate

𝒉i​j/ρi​j\\bm\{h\}\_\{ij\}/\\rho\_\{ij\}into

A~i,A~j\\widetilde\{A\}\_\{i\},\\widetilde\{A\}\_\{j\}
update the policy with Eq\. \([13](https://arxiv.org/html/2608.11368#S4.E13)\)

update prefix heads with Eq\. \([7](https://arxiv.org/html/2608.11368#S4.E7)\)

Algorithm 1Pairfor one group\-relative RLVR update#### Cost\.

Prefix probing costsG​τG\\tautokens\. The allocation constrains predicted expected suffix cost byCC\. Graph construction isO⁡\(G2\)O\(G^\{2\}\), probability optimization usesGGvariables, and forming observed pair advantages isO⁡\(K2\)O\(K^\{2\}\)forK=∑iJiK=\\sum\_\{i\}J\_\{i\}\. Whether these CPU\-side terms are negligible relative to autoregressive generation atG≤32G\\leq 32remains a wall\-clock question\. Batched continuation and paged KV\-cache management follow modern RL training systems\([33](https://arxiv.org/html/2608.11368#bib.bib45);[19](https://arxiv.org/html/2608.11368#bib.bib46)\)\.

## 5Theoretical Analysis

###### Theorem 1\(Pairwise representation\)\.

Leto1:Go\_\{1:G\}be conditionally i\.i\.d\. on\-policy rollouts with integrable sequence scores and parameter\-independent rewards\. Then

1M​∑i<j𝒉i​j\\displaystyle\\frac\{1\}\{M\}\\sum\_\{i<j\}\\bm\{h\}\_\{ij\}=1G​∑i\(ri−r¯−i\)​𝒔i,\\displaystyle=\\frac\{1\}\{G\}\\sum\_\{i\}\(r\_\{i\}\-\\bar\{r\}\_\{\-i\}\)\\bm\{s\}\_\{i\},𝔼⁡\[𝒈^pair∣q\]\\displaystyle\\mathbb\{E\}\[\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{pair\}\}\\mid q\]=𝒈⁡\(q\)\.\\displaystyle=\\bm\{g\}\(q\)\.The group\-mean baseline estimator is\(G−1\)/G\(G\-1\)/Gtimes this quantity\.

###### Theorem 2\(Design\-unbiased induced\-edge estimator\)\.

Condition on the candidate prefixes and their potential completed rollouts\. Suppose the continuation design uses fresh randomization, has stable potential outcomes, and logsρi​j=ℙ\(JiJj=1∣z1:G\)\>0\\rho\_\{ij\}=\\mathbb\{P\}\(J\_\{i\}J\_\{j\}=1\\mid z\_\{1:G\}\)\>0before terminal rewards are observed\. Then

𝔼design\[𝒈^Pair∣o1:G\]=𝒈^pair\.\\mathbb\{E\}\_\{\\mathrm\{design\}\}\[\\widehat\{\\bm\{g\}\}\_\{\\textnormal\{\{Pair\}\}\}\\mid o\_\{1:G\}\]=\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{pair\}\}\.Together with Theorem[1](https://arxiv.org/html/2608.11368#Thmtheorem1), the estimator is unconditionally unbiased for Eq\. \([1](https://arxiv.org/html/2608.11368#S3.E1)\)\.

###### Proposition 1\(Bias and covariance\)\.

If the inverse inclusion factor is omitted while retaining the complete\-pair denominator, the conditional bias is

1M​∑i<j\(ρi​j−1\)​𝒉i​j\.\\frac\{1\}\{M\}\\sum\_\{i<j\}\(\\rho\_\{ij\}\-1\)\\bm\{h\}\_\{ij\}\.For independent Bernoulli vertices, the exact conditional design covariance is

1M2\[\\displaystyle\\frac\{1\}\{M^\{2\}\}\\Bigg\[∑i<j\(1πi​πj−1\)​𝒉i​j​𝒉i​j⊤\\displaystyle\\sum\_\{i<j\}\\left\(\\frac\{1\}\{\\pi\_\{i\}\\pi\_\{j\}\}\-1\\right\)\\bm\{h\}\_\{ij\}\\bm\{h\}\_\{ij\}^\{\\\!\\top\}\+2∑i∑j<kj,k≠i\(1πi−1\)𝒉i​j𝒉i​k⊤\],\\displaystyle\+2\\sum\_\{i\}\\sum\_\{\\begin\{subarray\}\{c\}j<k\\\\ j,k\\neq i\\end\{subarray\}\}\\left\(\\frac\{1\}\{\\pi\_\{i\}\}\-1\\right\)\\bm\{h\}\_\{ij\}\\bm\{h\}\_\{ik\}^\{\\\!\\top\}\\Bigg\],with symmetric completion of the second term\.

###### Proposition 2\(Convex allocation surrogate\)\.

Forai​j,bi,c^i≥0a\_\{ij\},b\_\{i\},\\widehat\{c\}\_\{i\}\\geq 0, the objective in Eq\. \([10](https://arxiv.org/html/2608.11368#S4.E10)\) and feasible set in Eq\. \([11](https://arxiv.org/html/2608.11368#S4.E11)\) are convex in𝐱\\bm\{x\}\. If everyc^i\>0\\widehat\{c\}\_\{i\}\>0,πmin\>0\\pi\_\{\\min\}\>0, andC≥πmin​∑ic^iC\\geq\\pi\_\{\\min\}\\sum\_\{i\}\\widehat\{c\}\_\{i\}, a minimizer exists\.

The proofs are in Appendix[A](https://arxiv.org/html/2608.11368#A1)\. The theorems deliberately do not cover deterministic outcome pruning \(which violates positivity\), estimated or clipped inverse weights \(which introduce propensity error\), self\-normalization \(a ratio estimator\), random reward standardization, or an active PPO clipping boundary\. Appendix[B](https://arxiv.org/html/2608.11368#A2)derives each deviation\.

## 6Experiments

The evaluation addresses four questions: \(Q1\) does correction recover the intended finite\-pool gradient; \(Q2\) does graph\-aware allocation reduce gradient error per generated suffix token; \(Q3\) does this translate to compute\-matched reasoning quality; and \(Q4\) when do predictor error and inverse weights erase the gain?

### 6\.1Setup

#### Models and tasks\.

We train Qwen3\-1\.7B and Qwen3\-4B\([37](https://arxiv.org/html/2608.11368#bib.bib44)\)\. The mathematics track trains on the MATH training split\([10](https://arxiv.org/html/2608.11368#bib.bib37)\)and evaluates MATH500\([21](https://arxiv.org/html/2608.11368#bib.bib39)\), AIME24, AMC23, and OlympiadBench\([9](https://arxiv.org/html/2608.11368#bib.bib41)\)\. The code track trains on TACO\([20](https://arxiv.org/html/2608.11368#bib.bib40)\)and evaluates the post\-cutoff subset of LiveCodeBench\([15](https://arxiv.org/html/2608.11368#bib.bib42)\)\. Additional out\-of\-domain stress tests use GSM8K\([4](https://arxiv.org/html/2608.11368#bib.bib38)\)and GPQA\([28](https://arxiv.org/html/2608.11368#bib.bib43)\)\. Exact\-answer and execution verifiers provide binary rewards\. Appendix[D](https://arxiv.org/html/2608.11368#A4)fixes data versions, decontamination, prompts, extraction, and failure handling\.

#### Baselines and fairness\.

We compare GRPO, DPPO, VIP, HORA, VIGOR, and DUET\([44](https://arxiv.org/html/2608.11368#bib.bib17);[26](https://arxiv.org/html/2608.11368#bib.bib13);[35](https://arxiv.org/html/2608.11368#bib.bib14);[16](https://arxiv.org/html/2608.11368#bib.bib15);[13](https://arxiv.org/html/2608.11368#bib.bib18)\)\. Every method uses the same policy initialization, candidate prompt stream, verifier, maximum response length, optimizer, effective update batch, and total generation\-token accounting\. We report both equal\-token and equal\-wall\-clock budgets\.

Table 1:Compute\-matched RLVR comparison\.Accuracy/pass@1 is reported in percent; generated rollout tokens \(relative to full\-group GRPO\) and wall\-clock hours are lower\-is\-better\. All methods share the same policy initialization, verifier, maximum response length, optimizer, and total generation\-token accounting\. Best per backbone and column inbold; second bestunderlined\.Table[1](https://arxiv.org/html/2608.11368#S6.T1)summarizes the compute\-matched comparison\. On Qwen3\-1\.7B,Pairreaches49\.2%49\.2\\%average accuracy versus48\.0%48\.0\\%for DUET and45\.0%45\.0\\%for full\-group GRPO, while using0\.49×0\.49\{\\times\}the GRPO token budget and28\.128\.1wall\-clock hours \(42%42\\%less than GRPO\)\. Gains are consistent across mathematics and code: AIME24 improves by\+1\.3\+1\.3over DUET and LiveCodeBench by\+1\.2\+1\.2\. On Qwen3\-4B the same pattern holds:Pairattains57\.1%57\.1\\%average accuracy at0\.48×0\.48\{\\times\}tokens, exceeding DUET by\+1\.4\+1\.4absolute points\. Pointwise allocators \(VIP, HORA, VIGOR, DUET\) already beat full\-group GRPO under the shared budget, but leave a residual gap that pair\-aware design closes\.

Figure 3:Accuracy–cost trade\-off and mechanism ablations\.\(a\) Across both backbones,Pair\(stars\) sits on the Pareto frontier of mean accuracy versus relative generated tokens\. \(b\) Removing pair\-inclusion correction or replacing the graph design with pointwise/uniform rules increases frozen\-policy gradient MSE\.

### 6\.2Frozen\-policy estimator audit

To separate estimation quality from optimization, each checkpoint fully generates a candidate group and stores the exact complete\-pair gradient on a fixed parameter block\. We then replay each sampling design against this frozen population\. Metrics include bias norm, trace MSE, cosine error, effective sample size \(ESS\), completed vertices, observed edges, suffix tokens, and wall\-clock\. The comparison includes uniform vertex HT, pointwise vertex HT, direct edge sampling, unweighted adaptive selection, marginal\-only weights, andPair\.

Figure 4:Controlled estimator audit on a frozen candidate population\.Adaptive unweighted selection changes the target; inverse pair\-inclusion weighting recovers the complete\-pair gradient in expectation\. MSE remains nonzero because unbiasedness does not remove design variance\. Means are over 50,000 randomized design draws with logged inclusion probabilities\.Table 2:Frozen finite\-population estimator audit\.Values are means over 50,000 randomized sampling\-design draws on one fixed candidate population with logged inclusion probabilities\. Adaptive unweighted selection attains lower MSE by changing the estimand; pair\-inclusion HT recovers the complete\-pair target at matched suffix cost\.Table[2](https://arxiv.org/html/2608.11368#S6.T2)and Figure[4](https://arxiv.org/html/2608.11368#S6.F4)show the central statistical finding\. At roughly46%46\\%relative suffix cost, unweighted adaptive selection attains the lowest MSE \(0\.0500\.050\) but with bias2\.27×10−22\.27\{\\times\}10^\{\-2\}: it optimizes a different estimand\. Uniform and pointwise vertex HT remain nearly unbiased yet leave MSE at0\.1540\.154and0\.1740\.174\.Pairrecovers near\-zero bias \(1\.90×10−31\.90\{\\times\}10^\{\-3\}\) with MSE0\.1450\.145, improving on both unbiased baselines at matched cost\. The gap between biased low\-MSE selection and corrected estimation is exactly the bias–variance trade\-off predicted by Proposition[1](https://arxiv.org/html/2608.11368#Thmproposition1)\.

### 6\.3Training Curves, Mechanism Tests, and Ablations

For Q3, the primary endpoint is accuracy at equal generated tokens; secondary endpoints are time to a pre\-registered accuracy threshold, final accuracy, total wall\-clock, and pass@kk\. Figure[3](https://arxiv.org/html/2608.11368#S6.F3)\(a\) places every method in the accuracy–token plane:Pairdominates the frontier on both backbones, reaching the target accuracy threshold16\.716\.7hours earlier than GRPO on 1\.7B and23\.623\.6hours earlier on 4B\.

Mechanism tests measure prefix\-head Brier score and calibration error, realized versus predicted suffix cost, the distribution ofπi\\pi\_\{i\}andρi​j\\rho\_\{ij\}, edge coverage, inverse\-weight ESS, and the correlation betweenai​ja\_\{ij\}and measured‖𝒉i​j‖2\\\|\\bm\{h\}\_\{ij\}\\\|^\{2\}\. The decisive comparison is gradient MSE per suffix token against \(i\) uniform vertices, \(ii\) pointwisep⁡\(1−p\)p\(1\-p\)allocation, and \(iii\) direct edge sampling that cannot reuse endpoints\.

Table 3:Mechanism ablations on Qwen3\-1\.7B\.Accuracy is the five\-benchmark average from Table[1](https://arxiv.org/html/2608.11368#S6.T1)\. Gradient MSE is measured against the full candidate\-pool leave\-one\-out estimator on frozen checkpoints\. Tokens are relative to full\-group GRPO\. Removing pair\-inclusion correction yields the largest accuracy and MSE regressions\.Table[3](https://arxiv.org/html/2608.11368#S6.T3)and Figure[3](https://arxiv.org/html/2608.11368#S6.F3)\(b\) isolate the mechanism\. Dropping pair\-inclusion correction costs2\.12\.1accuracy points and raises gradient MSE from0\.1450\.145to0\.2180\.218\. Marginal\-only weights recover only part of the gap \(47\.6%47\.6\\%, MSE0\.1950\.195\), confirming that joint inclusion—not merely per\-rollout propensity—is required\. Replacing the graph design with uniform or pointwise allocation raises MSE to0\.1680\.168and0\.1610\.161and lowers accuracy\. Removing the shared\-vertex covariance term or the suffix\-cost regularizer produces smaller regressions, while self\-normalized weights slightly reduce MSE \(0\.1390\.139\) at a modest accuracy cost, consistent with a biased ratio estimator\.

#### Robustness and failure analysis\.

We sweep prefix checkpointτ\\tau, candidate sizeGG, budget ratio,πmin\\pi\_\{\\min\}, policy drift, calibration temperature, binary versus partial credit, and expected versus fixed\-size sampling\. Hard cases include near\-deterministic groups, miscalibrated predictors, long\-tail suffix costs, and low ESS\. A method fails the pre\-registered gate if it raises gradient MSE at equal tokens, exceeds the budget by more than5%5\\%on average, or gains accuracy only by receiving more verified tokens\. Full matrices appear in Appendix[E](https://arxiv.org/html/2608.11368#A5); the recommended operating pointτ=256\\tau\{=\}256,G=16G\{=\}16, budget ratio0\.50\.5, andπmin=0\.05\\pi\_\{\\min\}\{=\}0\.05is stable across both domains\.

## 7Discussion

#### Estimator\-aware allocation\.

The main conceptual change is to define “useful compute” relative to the estimator being approximated\. Difficulty, variance, and predicted correctness remain valuable auxiliaries, but their role is to design an observation distribution over the actual gradient terms\. For group\-relative learning those terms are pairwise: a medium\-difficulty rollout is not automatically useful if all other completed rollouts predict the same outcome, while an endpoint near an extreme can be valuable when it completes a complementary contrast\.

#### Why vertex sampling matters\.

Sampling pair edges independently would match theUU\-statistic algebra but misrepresent generation cost\. A suffix is reusable: once rolloutiiis complete, it participates in every observed\(i,j\)\(i,j\)\.Pairtherefore samples vertices and corrects induced edges\. This graph externality is the part that differentiates the RLVR measurement problem from generic pair\-loss subsampling\.

#### Unbiasedness is not the whole objective\.

Small inclusion probabilities can make an unbiased estimator unusably noisy\. The probability floor and graph\-coupled surrogate mitigate this trade\-off, while ESS diagnoses it; neither guarantees low realized variance when the proxy is inaccurate\. Self\-normalization or clipping can reduce variance at the cost of explicit bias\. Our ablations report these trade\-offs rather than treat “unbiased” as synonymous with “best\.” Likewise, an estimator advantage need not translate to wall\-clock speedup if synchronization or prefix probing dominates; in our runs the prefix overhead remains below4%4\\%of total generation time\.

## 8Conclusion

Adaptive rollout allocation should respect the statistical unit of the policy update\. For the unclipped leave\-one\-out group\-relative gradient, that unit is a rollout pair: suffix cost is paid on vertices, while contrastive learning signal appears on induced edges\.Pairturns this observation into a prefix\-conditioned randomized design, a graph\-coupled token allocation, and an inverse pair\-inclusion estimator with a finite\-population guarantee\. The theory establishes design\-unbiasedness for the scoped target; the frozen audit confirms the correction; and compute\-matched RLVR experiments show that estimator\-aware allocation improves reasoning accuracy while cutting generated tokens roughly in half relative to full\-group GRPO\.

## Limitations

The exact guarantee concerns an on\-policy, sequence\-level, unclipped, unstandardized leave\-one\-out score gradient\. Standard GRPO divides by a random within\-group standard deviation and typically performs several clipped PPO epochs, so its practical PAIR variant is an approximation to that target\. Prefix predictors may drift with the policy, and severe miscalibration can assign low probabilities to valuable endpoints, creating high\-variance inverse weights despite the positivity floor\. The convex objective is a valid upper bound only under the stated domination condition onai​ja\_\{ij\}; with learned proxies, it is a surrogate for the unknown design variance\. Independent Bernoulli continuation controls expected, not exact, token cost\. Gains may shrink when responses are short, prefix probes are expensive, or groups are near\-deterministic so that predicted disagreement collapses\.

## Ethical Considerations

Pairis an efficiency technique for training reasoning models and inherits the capabilities and misuse risks of the underlying models and datasets\. Lower training cost can broaden access to reproducible RLVR research, but can also lower the cost of adapting models for harmful applications\. The benchmark protocol uses public mathematical and programming benchmarks with automatic verifiers and no human\-subject data\. Dataset licenses, benchmark contamination, generated\-token counts, accelerator hours, and failed runs are reported\. No private chain\-of\-thought traces or personally identifying data are required by the method\. Because adaptive selection can hide systematic failures on rare prompts, final reporting includes per\-difficulty and failure\-group coverage rather than aggregate accuracy alone\.

## References

- Ahmadianet al\.\(2024\)A\. Ahmadian, C\. Cremer, M\. Gallé, M\. Fadaee, J\. Kreutzer, O\. Pietquin, A\. Üstün, and S\. HookerBack to basics: revisiting reinforce style optimization for learning from human feedback in llms\.arXiv preprint arXiv:2402\.14740\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px1.p1.1)\.
- Baeet al\.\(2025\)S\. Bae, J\. Hong, M\. Y\. Lee, H\. Kim, J\. Nam, and D\. KwakOnline difficulty filtering for reasoning oriented reinforcement learning\.arXiv preprint arXiv:2504\.03380\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Chenet al\.\(2025\)X\. Chen, J\. Lu, M\. Kim, D\. Zhang, J\. Tang, A\. Piché, N\. Gontier, Y\. Bengio, and E\. KamallooSelf\-evolving curriculum for llm reasoning\.arXiv preprint arXiv:2505\.14970\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Cobbeet al\.\(2021\)K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano,et al\.Training verifiers to solve math word problems\.arXiv preprint arXiv:2110\.14168\.Cited by:[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px1.p1.1)\.
- Davyet al\.\(2026\)L\. Davy, S\. Clémençon, and C\. LaclauDoing well with less\! on sampling techniques for empirical pairwise loss estimation/minimization\.arXiv preprint arXiv:2606\.02345\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px4.p1.1)\.
- DeepSeek\-AI \(2025\)DeepSeek\-AIDeepSeek\-r1: incentivizing reasoning capability in llms via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p1.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px1.p1.1)\.
- Fanet al\.\(2026\)M\. Fan, W\. Han, D\. Wang, C\. Chen, Z\. Zhang, and J\. ZhouWhen sharpening becomes collapse: sampling bias and semantic coupling in reinforcement learning with verifiable rewards\.arXiv preprint arXiv:2601\.15609\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Hájek \(1964\)J\. HájekAsymptotic theory of rejective sampling with varying probabilities from a finite population\.The Annals of Mathematical Statistics35\(4\),pp\. 1491–1523\.Cited by:[Appendix B](https://arxiv.org/html/2608.11368#A2.SS0.SSS0.Px4.p1.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px4.p1.1)\.
- Heet al\.\(2024\)C\. He, R\. Luo, Y\. Bai, S\. Hu, Z\. L\. Thai, J\. Shen, J\. Hu, X\. Han, Y\. Huang, Y\. Zhang,et al\.OlympiadBench: a challenging benchmark for promoting agi with olympiad\-level bilingual multimodal scientific problems\.arXiv preprint arXiv:2402\.14008\.Cited by:[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px1.p1.1)\.
- Hendryckset al\.\(2021\)D\. Hendrycks, C\. Burns, S\. Kadavath, A\. Arora, S\. Basart, E\. Tang, D\. Song, and J\. SteinhardtMeasuring mathematical problem solving with the math dataset\.arXiv preprint arXiv:2103\.03874\.Cited by:[§D\.1](https://arxiv.org/html/2608.11368#A4.SS1.SSS0.Px1.p1.1),[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px1.p1.1)\.
- Hoeffding \(1948\)W\. HoeffdingA class of statistics with asymptotically normal distribution\.The Annals of Mathematical Statistics19\(3\),pp\. 293–325\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p3.2)\.
- Horvitz and Thompson \(1952\)D\. G\. Horvitz and D\. J\. ThompsonA generalization of sampling without replacement from a finite universe\.Journal of the American Statistical Association47\(260\),pp\. 663–685\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p4.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px4.p1.1)\.
- Huet al\.\(2026\)H\. Hu, X\. Zhao, X\. “\. Xu, and N\. JacobyDUET: optimize token\-budget allocation for reinforcement learning with verifiable rewards\.arXiv preprint arXiv:2605\.08441\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px3.p1.1),[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px2.p1.1)\.
- Huet al\.\(2025\)J\. Hu, J\. K\. Liu, H\. Xu, and W\. ShenREINFORCE\+\+: stabilizing critic\-free policy optimization with global advantage normalization\.arXiv preprint arXiv:2501\.03262\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p1.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px1.p1.1)\.
- Jainet al\.\(2024\)N\. Jain, K\. Han, A\. Gu, W\. Li, F\. Yan, T\. Zhang, S\. Wang, A\. Solar\-Lezama, K\. Sen, and I\. StoicaLiveCodeBench: holistic and contamination free evaluation of large language models for code\.arXiv preprint arXiv:2403\.07974\.Cited by:[§D\.1](https://arxiv.org/html/2608.11368#A4.SS1.SSS0.Px2.p1.1),[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px1.p1.1)\.
- Jianget al\.\(2026\)H\. Jiang, H\. Liu, and B\. MirzasoleimanLearning as reasoning unfolds: progressive rollout allocation for efficient reinforcement learning\.arXiv preprint arXiv:2607\.22002\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1),[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px2.p1.1)\.
- Klusowski and Wu \(2018\)J\. M\. Klusowski and Y\. WuCounting motifs with graph sampling\.InProceedings of the 31st Conference on Learning Theory,Vol\.75,pp\. 1966–2011\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px4.p1.1)\.
- Kong and Zheng \(2021\)X\. Kong and W\. ZhengDesign based incomplete u\-statistics\.Statistica Sinica31\(3\),pp\. 1593–1618\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px4.p1.1)\.
- Kwonet al\.\(2023\)W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. E\. Gonzalez, H\. Zhang, and I\. StoicaEfficient memory management for large language model serving with pagedattention\.InProceedings of the 29th ACM Symposium on Operating Systems Principles,pp\. 611–626\.Cited by:[§D\.2](https://arxiv.org/html/2608.11368#A4.SS2.p1.1),[§4\.5](https://arxiv.org/html/2608.11368#S4.SS5.SSS0.Px1.p1.1)\.
- Liet al\.\(2023\)R\. Li, J\. Fu, B\. Zhang, T\. Huang, Z\. Sun, C\. Lyu, G\. Liu, Z\. Jin, and G\. LiTACO: topics in algorithmic code generation dataset\.arXiv preprint arXiv:2312\.14852\.Cited by:[§D\.1](https://arxiv.org/html/2608.11368#A4.SS1.SSS0.Px2.p1.1),[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px1.p1.1)\.
- Lightmanet al\.\(2023\)H\. Lightman, V\. Kosaraju, Y\. Burda, H\. Edwards, B\. Baker, T\. Lee, J\. Leike, J\. Schulman, I\. Sutskever, and K\. CobbeLet’s verify step by step\.arXiv preprint arXiv:2305\.20050\.Cited by:[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px1.p1.1)\.
- Liuet al\.\(2025\)Z\. Liu, C\. Chen, W\. Li, P\. Qi, T\. Pang, C\. Du, W\. S\. Lee, and M\. LinUnderstanding r1\-zero\-like training: a critical perspective\.arXiv preprint arXiv:2503\.20783\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p1.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px1.p1.1)\.
- Maoet al\.\(2026\)Y\. Mao, Y\. Qu, Q\. Wang, H\. Zou, and X\. JiDynamics\-predictive sampling for active rl finetuning of large reasoning models\.InInternational Conference on Learning Representations,Vol\.2026,pp\. 25242–25270\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Meloet al\.\(2025\)L\. C\. Melo, A\. Abate, and Y\. GalStabilizing policy gradients for sample\-efficient reinforcement learning in llm reasoning\.arXiv preprint arXiv:2510\.00819\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Neyman \(1934\)J\. NeymanOn the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection\.Journal of the Royal Statistical Society97\(4\),pp\. 558–625\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px4.p1.1)\.
- Nguyenet al\.\(2026\)H\. T\. Nguyen, B\. Nguyen, W\. Ma, Y\. Zhao, R\. She, and V\. A\. NguyenAdaptive rollout allocation for online reinforcement learning with verifiable rewards\.arXiv preprint arXiv:2602\.01601\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1),[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px2.p1.1)\.
- Quet al\.\(2026\)Y\. Qu, Q\. Wang, Y\. Mao, H\. Zou, Y\. Jiang, W\. Liu, C\. Bai, K\. Yang, Y\. Chen, S\. Yang,et al\.Small generalizable prompt predictive models can steer efficient rl post\-training of large reasoning models\.arXiv preprint arXiv:2602\.01970\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Reinet al\.\(2023\)D\. Rein, B\. L\. Hou, A\. C\. Stickland, J\. Petty, R\. Y\. Pang, J\. Dirani, J\. Michael, and S\. R\. BowmanGPQA: a graduate\-level google\-proof q&a benchmark\.arXiv preprint arXiv:2311\.12022\.Cited by:[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px1.p1.1)\.
- Sanget al\.\(2026\)H\. Sang, Y\. Xu, Z\. Zhou, R\. He, and Z\. WangNot all tokens are needed: token\-efficient reinforcement learning\.arXiv preprint arXiv:2603\.06619\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p4.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px3.p1.1)\.
- Särndalet al\.\(1992\)C\. Särndal, B\. Swensson, and J\. WretmanModel assisted survey sampling\.Springer\-Verlag\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p4.1)\.
- Schulmanet al\.\(2017\)J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. KlimovProximal policy optimization algorithms\.arXiv preprint arXiv:1707\.06347\.Cited by:[§3\.1](https://arxiv.org/html/2608.11368#S3.SS1.p1.3)\.
- Shaoet al\.\(2024\)Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. K\. Li, Y\. Wu,et al\.DeepSeekMath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p1.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px1.p1.1)\.
- Shenget al\.\(2025\)G\. Sheng, C\. Zhang, Z\. Ye, X\. Wu, W\. Zhang, R\. Zhang, Y\. Peng, H\. Lin, and C\. WuHybridFlow: a flexible and efficient rlhf framework\.InProceedings of the Twentieth European Conference on Computer Systems,Cited by:[§D\.2](https://arxiv.org/html/2608.11368#A4.SS2.p1.1),[§4\.5](https://arxiv.org/html/2608.11368#S4.SS5.SSS0.Px1.p1.1)\.
- Sudalairajet al\.\(2026\)S\. Sudalairaj, K\. Xu, A\. Srivastava, and G\. GiannoneSGPO: trading inference flops for training efficiency in rlvr\.arXiv preprint arXiv:2606\.08854\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Wanget al\.\(2026\)T\. Wang, S\. Li, Y\. Sun, D\. Ding, and E\. DobribanWhere to spend rollouts: hit\-utility optimal rollout allocation for group\-based rlvr\.arXiv preprint arXiv:2605\.07114\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1),[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px2.p1.1)\.
- Wuet al\.\(2026\)Y\. Wu, L\. Ma, L\. Xiao, M\. Li, X\. Wang, Y\. Zhang, and J\. NieRethinking groups in critic\-free rlvr\.arXiv preprint arXiv:2606\.17250\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px1.p1.1)\.
- Yanget al\.\(2025a\)A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv,et al\.Qwen3 technical report\.arXiv preprint arXiv:2505\.09388\.Cited by:[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px1.p1.1)\.
- Yanget al\.\(2026\)N\. Yang, W\. Du, W\. Sun, S\. Welleck, and Y\. YangGradAlign: gradient\-aligned data selection for llm reinforcement learning\.arXiv preprint arXiv:2602\.21492\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Yanget al\.\(2025b\)Z\. Yang, Z\. Guo, Y\. Huang, Y\. Wang, D\. Xie, H\. Li, Y\. Wang, X\. Liang, and J\. TangDepth\-breadth synergy in rlvr: unlocking llm reasoning gains with adaptive exploration\.arXiv preprint arXiv:2508\.13755\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Yuet al\.\(2025\)Q\. Yu, Z\. Zhang, R\. Zhu, Y\. Yuan, X\. Zuo, Y\. Yue, W\. Dai, T\. Fan, G\. Liu, L\. Liu,et al\.DAPO: an open\-source llm reinforcement learning system at scale\.arXiv preprint arXiv:2503\.14476\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p1.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px1.p1.1)\.
- Zhanget al\.\(2025\)Y\. Zhang, W\. Yao, C\. Yu, Y\. Liu, Q\. Yin, B\. Yin, H\. Yun, and L\. LiImproving sampling efficiency in rlvr through adaptive rollout and response reuse\.arXiv preprint arXiv:2509\.25808\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Zhenget al\.\(2025\)H\. Zheng, Y\. Zhou, B\. R\. Bartoldson, B\. Kailkhura, F\. Lai, J\. Zhao, and B\. ChenAct only when it pays: efficient reinforcement learning for llm reasoning via selective rollouts\.arXiv preprint arXiv:2506\.02177\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Zhouet al\.\(2026\)H\. Zhou, K\. Ye, E\. Xu, J\. Zhu, Y\. Yang, S\. Gong, and C\. ShiDemystifying group relative policy optimization: its policy gradient is a u\-statistic\.arXiv preprint arXiv:2603\.01162\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p3.2),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px1.p1.1)\.
- Zhuet al\.\(2026\)H\. Zhu, Y\. Ren, Y\. Li, M\. Lin, L\. Yang, X\. Liu, X\. Zhen, H\. Liu, and B\. ZhangUnbiased dynamic pruning for efficient group\-based policy optimization\.arXiv preprint arXiv:2603\.04135\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p4.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px3.p1.1),[§6\.1](https://arxiv.org/html/2608.11368#S6.SS1.SSS0.Px2.p1.1)\.
- Zonget al\.\(2026\)Y\. Zong, Y\. Wang, and J\. JiangCross\-epoch adaptive rollout optimization for rl post\-training\.arXiv preprint arXiv:2606\.05606\.Cited by:[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.
- Zouet al\.\(2026\)H\. Zou, Q\. Wang, Y\. Qu, Y\. Jiang, L\. Cai, Y\. Mao, R\. Peng, X\. Xu, W\. Liu, K\. Yang,et al\.TRACE: a unified rollout budget allocation framework for efficient agentic reinforcement learning\.arXiv preprint arXiv:2606\.11119\.Cited by:[§1](https://arxiv.org/html/2608.11368#S1.p2.1),[§2](https://arxiv.org/html/2608.11368#S2.SS0.SSS0.Px2.p1.1)\.

## Appendix AProofs

### A\.1Score\-function preliminaries

Fix a promptqq\. Assume the support ofπ𝜽\(⋅∣q\)\\pi\_\{\\bm\{\\theta\}\}\(\\cdot\\mid q\)is locally independent of𝜽\\bm\{\\theta\}, reward has no direct derivative with respect to𝜽\\bm\{\\theta\}, and differentiation may pass through the expectation\. Then

𝔼⁡\[𝒔i∣q\]\\displaystyle\\mathbb\{E\}\[\\bm\{s\}\_\{i\}\\mid q\]=∫π𝜽​\(o∣q\)​∇𝜽​log⁡π𝜽​\(o∣q\)​𝑑o\\displaystyle=\\int\\pi\_\{\\bm\{\\theta\}\}\(o\\mid q\)\\nabla\_\{\\bm\{\\theta\}\}\\log\\pi\_\{\\bm\{\\theta\}\}\(o\\mid q\)\\,do=∇𝜽∫π𝜽\(o∣q\)do=0,\\displaystyle=\\nabla\_\{\\bm\{\\theta\}\}\\int\\pi\_\{\\bm\{\\theta\}\}\(o\\mid q\)\\,do=0,\(14\)∇𝜽𝔼​\[ri∣q\]\\displaystyle\\nabla\_\{\\bm\{\\theta\}\}\\mathbb\{E\}\[r\_\{i\}\\mid q\]=𝔼⁡\[ri​𝒔i∣q\]\.\\displaystyle=\\mathbb\{E\}\[r\_\{i\}\\bm\{s\}\_\{i\}\\mid q\]\.\(15\)These are the only policy\-gradient identities needed below\.

### A\.2Proof of Theorem[1](https://arxiv.org/html/2608.11368#Thmtheorem1)

For any vectors𝒂i\\bm\{a\}\_\{i\}and scalarsbib\_\{i\},

∑i<j\(bi−bj\)​\(𝒂i−𝒂j\)\\displaystyle\\sum\_\{i<j\}\(b\_\{i\}\-b\_\{j\}\)\(\\bm\{a\}\_\{i\}\-\\bm\{a\}\_\{j\}\)=G​∑i\(bi−b¯\)​\(𝒂i−𝒂¯\)\.\\displaystyle\\qquad=G\\sum\_\{i\}\(b\_\{i\}\-\\bar\{b\}\)\(\\bm\{a\}\_\{i\}\-\\bar\{\\bm\{a\}\}\)\.\(16\)To verify the identity, expand the left side over ordered pairs and collect the coefficient of𝒂i\\bm\{a\}\_\{i\}:

12​∑i≠j\(bi−bj\)​\(𝒂i−𝒂j\)\\displaystyle\\frac\{1\}\{2\}\\sum\_\{i\\neq j\}\(b\_\{i\}\-b\_\{j\}\)\(\\bm\{a\}\_\{i\}\-\\bm\{a\}\_\{j\}\)=G​∑ibi​𝒂i−\(∑ibi\)​\(∑i𝒂i\)\.\\displaystyle\\quad=G\\sum\_\{i\}b\_\{i\}\\bm\{a\}\_\{i\}\-\\left\(\\sum\_\{i\}b\_\{i\}\\right\)\\left\(\\sum\_\{i\}\\bm\{a\}\_\{i\}\\right\)\.Takingbi=rib\_\{i\}=r\_\{i\}and𝒂i=𝒔i\\bm\{a\}\_\{i\}=\\bm\{s\}\_\{i\}, and using∑i\(ri−r¯\)=0\\sum\_\{i\}\(r\_\{i\}\-\\bar\{r\}\)=0, gives

1M​∑i<j𝒉i​j\\displaystyle\\frac\{1\}\{M\}\\sum\_\{i<j\}\\bm\{h\}\_\{ij\}=1G−1​∑i\(ri−r¯\)​𝒔i\\displaystyle=\\frac\{1\}\{G\-1\}\\sum\_\{i\}\(r\_\{i\}\-\\bar\{r\}\)\\bm\{s\}\_\{i\}=1G​∑i\(ri−r¯−i\)​𝒔i\.\\displaystyle=\\frac\{1\}\{G\}\\sum\_\{i\}\(r\_\{i\}\-\\bar\{r\}\_\{\-i\}\)\\bm\{s\}\_\{i\}\.\(17\)This proves the deterministic equivalence\.

For unbiasedness, take two independent rolloutsi≠ji\\neq j\. Using Eq\. \([14](https://arxiv.org/html/2608.11368#A1.E14)\),

2​𝔼​\[𝒉i​j∣q\]\\displaystyle 2\\mathbb\{E\}\[\\bm\{h\}\_\{ij\}\\mid q\]=𝔼⁡\[ri​𝒔i\]\+𝔼⁡\[rj​𝒔j\]\\displaystyle=\\mathbb\{E\}\[r\_\{i\}\\bm\{s\}\_\{i\}\]\+\\mathbb\{E\}\[r\_\{j\}\\bm\{s\}\_\{j\}\]−𝔼⁡\[ri​𝒔j\]−𝔼⁡\[rj​𝒔i\]\\displaystyle\\quad\-\\mathbb\{E\}\[r\_\{i\}\\bm\{s\}\_\{j\}\]\-\\mathbb\{E\}\[r\_\{j\}\\bm\{s\}\_\{i\}\]=2​𝒈​\(q\)−2​𝔼​\[ri\]​𝔼​\[𝒔j\]=2​𝒈​\(q\)\.\\displaystyle=2\\bm\{g\}\(q\)\-2\\mathbb\{E\}\[r\_\{i\}\]\\mathbb\{E\}\[\\bm\{s\}\_\{j\}\]=2\\bm\{g\}\(q\)\.\(18\)Every pair has the same expectation, so their average is unbiased\. Finally,

1G​∑i\(ri−r¯\)​𝒔i=G−1G​𝒈^pair,\\frac\{1\}\{G\}\\sum\_\{i\}\(r\_\{i\}\-\\bar\{r\}\)\\bm\{s\}\_\{i\}=\\frac\{G\-1\}\{G\}\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{pair\}\},which establishes the finite\-GGshrinkage of the group\-mean baseline\.□\\square

### A\.3Proof of Theorem[2](https://arxiv.org/html/2608.11368#Thmtheorem2)

Condition on the complete finite populationℱ=\{\(zi,oi,ri,𝒔i\)\}i=1G\\mathcal\{F\}=\\\{\(z\_\{i\},o\_\{i\},r\_\{i\},\\bm\{s\}\_\{i\}\)\\\}\_\{i=1\}^\{G\}\. Stable potential outcomes mean that the value of𝒉i​j\\bm\{h\}\_\{ij\}does not change with which other vertices are continued\. Pre\-outcome randomized selection and logged propensities imply

𝔼design​\[Ii​j∣ℱ\]=ρi​j\>0\.\\mathbb\{E\}\_\{\\mathrm\{design\}\}\[I\_\{ij\}\\mid\\mathcal\{F\}\]=\\rho\_\{ij\}\>0\.Therefore, term by term,

𝔼design​\[Ii​jρi​j​𝒉i​j\|ℱ\]=𝒉i​j\.\\mathbb\{E\}\_\{\\mathrm\{design\}\}\\\!\\left\[\\frac\{I\_\{ij\}\}\{\\rho\_\{ij\}\}\\bm\{h\}\_\{ij\}\\,\\middle\|\\,\\mathcal\{F\}\\right\]=\\bm\{h\}\_\{ij\}\.Summing the finite edge population and dividing byMMproves conditional design\-unbiasedness\. Taking expectation over the i\.i\.d\. rollout population and applying Theorem[1](https://arxiv.org/html/2608.11368#Thmtheorem1)yields𝔼⁡\[𝒈^Pair∣q\]=𝒈⁡\(q\)\\mathbb\{E\}\[\\widehat\{\\bm\{g\}\}\_\{\\textnormal\{\{Pair\}\}\}\\mid q\]=\\bm\{g\}\(q\)\.□\\square

### A\.4Naive selection bias

Consider first the estimator that keeps the complete\-pair denominator but omits inverse probabilities:

𝒈~0=1M​∑i<jIi​j​𝒉i​j\.\\widetilde\{\\bm\{g\}\}\_\{0\}=\\frac\{1\}\{M\}\\sum\_\{i<j\}I\_\{ij\}\\bm\{h\}\_\{ij\}\.Conditionally,

𝔼design​\[𝒈~0−𝒈^pair∣ℱ\]=1M​∑i<j\(ρi​j−1\)​𝒉i​j\.\\mathbb\{E\}\_\{\\mathrm\{design\}\}\[\\widetilde\{\\bm\{g\}\}\_\{0\}\-\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{pair\}\}\\mid\\mathcal\{F\}\]=\\frac\{1\}\{M\}\\sum\_\{i<j\}\(\\rho\_\{ij\}\-1\)\\bm\{h\}\_\{ij\}\.Even constant edge inclusionppattenuates the target bypp\. If instead one divides by the random observed\-edge countKE=∑Ii​jK\_\{E\}=\\sum I\_\{ij\}, then

𝔼⁡\[∑Ii​j​𝒉i​jKE\|KE\>0\]=∑i<jwi​j​𝒉i​j,\\displaystyle\\mathbb\{E\}\\\!\\left\[\\frac\{\\sum I\_\{ij\}\\bm\{h\}\_\{ij\}\}\{K\_\{E\}\}\\,\\middle\|\\,K\_\{E\}\>0\\right\]=\\sum\_\{i<j\}w\_\{ij\}\\bm\{h\}\_\{ij\},wi​j=𝔼⁡\[Ii​j/KE∣KE\>0\],\\displaystyle\\hskip 25\.00003ptw\_\{ij\}=\\mathbb\{E\}\[I\_\{ij\}/K\_\{E\}\\mid K\_\{E\}\>0\],which equals the uniform pair average only for a self\-weighting design\. Deterministically retaining pairs after seeing their terminal rewards gives excluded pairs conditional probability zero and cannot be repaired by a prefix\-only marginal propensity\.

### A\.5Design covariance

Writee=\(i,j\)e=\(i,j\),f=\(k,ℓ\)f=\(k,\\ell\), andΔe​f=ℙ⁡\(Ie=If=1\)−ρe​ρf\\Delta\_\{ef\}=\\mathbb\{P\}\(I\_\{e\}=I\_\{f\}=1\)\-\\rho\_\{e\}\\rho\_\{f\}\. The general Horvitz–Thompson covariance is

Covdesign⁡\(𝒈^Pair∣ℱ\)=1M2​∑e,fΔe​fρe​ρf​𝒉e​𝒉f⊤\.\\operatorname\{Cov\}\_\{\\mathrm\{design\}\}\(\\widehat\{\\bm\{g\}\}\_\{\\textnormal\{\{Pair\}\}\}\\mid\\mathcal\{F\}\)=\\frac\{1\}\{M^\{2\}\}\\sum\_\{e,f\}\\frac\{\\Delta\_\{ef\}\}\{\\rho\_\{e\}\\rho\_\{f\}\}\\bm\{h\}\_\{e\}\\bm\{h\}\_\{f\}^\{\\\!\\top\}\.\(19\)Under independent Bernoulli vertices, disjoint edges have zero covariance\. Fore=\(i,j\)e=\(i,j\),

Var⁡\(Ji​Jjπi​πj\)=1πi​πj−1\.\\operatorname\{Var\}\\\!\\left\(\\frac\{J\_\{i\}J\_\{j\}\}\{\\pi\_\{i\}\\pi\_\{j\}\}\\right\)=\\frac\{1\}\{\\pi\_\{i\}\\pi\_\{j\}\}\-1\.For two edges sharingii,e=\(i,j\)e=\(i,j\),f=\(i,k\)f=\(i,k\),

Cov⁡\(Ji​Jjπi​πj,Ji​Jkπi​πk\)=1πi−1\.\\operatorname\{Cov\}\\\!\\left\(\\frac\{J\_\{i\}J\_\{j\}\}\{\\pi\_\{i\}\\pi\_\{j\}\},\\frac\{J\_\{i\}J\_\{k\}\}\{\\pi\_\{i\}\\pi\_\{k\}\}\\right\)=\\frac\{1\}\{\\pi\_\{i\}\}\-1\.Substitution into Eq\. \([19](https://arxiv.org/html/2608.11368#A1.E19)\) yields Proposition[1](https://arxiv.org/html/2608.11368#Thmproposition1)\. The dependence is exactly why selecting edges independently and charging an additive edge cost is the wrong systems model\.

### A\.6Variance upper bound and convexity

Supposeai​j≥‖𝒉i​j‖22a\_\{ij\}\\geq\\\|\\bm\{h\}\_\{ij\}\\\|\_\{2\}^\{2\}\. By Cauchy–Schwarz,

∑j<kj,k≠i\|⟨𝒉i​j,𝒉i​k⟩\|≤\(∑j≠iai​j\)2−∑j≠iai​j=bi\.2\\\!\\\!\\sum\_\{\\begin\{subarray\}\{c\}j<k\\\\ j,k\\neq i\\end\{subarray\}\}\\\!\\left\|\\langle\\bm\{h\}\_\{ij\},\\bm\{h\}\_\{ik\}\\rangle\\right\|\\leq\\left\(\\sum\_\{j\\neq i\}\\sqrt\{a\_\{ij\}\}\\right\)^\{2\}\-\\sum\_\{j\\neq i\}a\_\{ij\}=b\_\{i\}\.Dropping constants independent of the design, the trace of the covariance is upper\-bounded by

∑i<jai​jπi​πj\+∑ibiπi\.\\sum\_\{i<j\}\\frac\{a\_\{ij\}\}\{\\pi\_\{i\}\\pi\_\{j\}\}\+\\sum\_\{i\}\\frac\{b\_\{i\}\}\{\\pi\_\{i\}\}\.Substituteπi=e−xi\\pi\_\{i\}=e^\{\-x\_\{i\}\}to obtain Eq\. \([10](https://arxiv.org/html/2608.11368#S4.E10)\)\. Each term is a nonnegative multiple of an exponential of an affine function, hence convex\. The cost constraint is the sublevel set of∑ic^i​e−xi\\sum\_\{i\}\\widehat\{c\}\_\{i\}e^\{\-x\_\{i\}\}, also convex; box constraints are convex and compact\. Feasibility follows fromC≥πmin​∑ic^iC\\geq\\pi\_\{\\min\}\\sum\_\{i\}\\widehat\{c\}\_\{i\}, and continuity on the compact feasible set gives existence\.□\\square

## Appendix BPractical Departures from the Exact Estimator

#### Reward standardization\.

If the group\-relative advantage divides by a random sample standard deviationσ^r\\widehat\{\\sigma\}\_\{r\}, the gradient is proportional to𝒈^pair/σ^r\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{pair\}\}/\\widehat\{\\sigma\}\_\{r\}\. Since numerator and denominator depend on the same rewards,𝔼⁡\[𝒈^pair/σ^r\]\\mathbb\{E\}\[\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{pair\}\}/\\widehat\{\\sigma\}\_\{r\}\]is not generally𝒈/σr\\bm\{g\}/\\sigma\_\{r\}\. Saturated groups make the denominator degenerate, so this is not a negligible technicality\. We therefore report LOO/Dr\.GRPO experiments that match the theorem and standardized GRPO experiments that measure practical transfer\.

#### PPO clipping and multiple epochs\.

At𝜽=𝜽old\\bm\{\\theta\}=\\bm\{\\theta\}\_\{\\mathrm\{old\}\}, trajectory ratios equal one and clipping is inactive\. Away from that point, the clipped objective intentionally targets a trust\-region surrogate rather than Eq\. \([1](https://arxiv.org/html/2608.11368#S3.E1)\)\. PAIR advantages can be inserted into that surrogate, but “design\-unbiased policy gradient” is then replaced by the narrower statement “pair\-corrected data\-collection target\.”

#### Estimated and stabilized propensities\.

If the true edge inclusion isρe\\rho\_\{e\}but the update usesρ^e\\widehat\{\\rho\}\_\{e\}, conditional bias is

1M​∑e\(ρeρ^e−1\)​𝒉e\.\\frac\{1\}\{M\}\\sum\_\{e\}\\left\(\\frac\{\\rho\_\{e\}\}\{\\widehat\{\\rho\}\_\{e\}\}\-1\\right\)\\bm\{h\}\_\{e\}\.With clipped weightmin⁡\(1/ρe,wmax\)\\min\(1/\\rho\_\{e\},w\_\{\\max\}\), the multiplier becomesmin⁡\(1,wmax​ρe\)−1\\min\(1,w\_\{\\max\}\\rho\_\{e\}\)\-1\. Self\-normalizing by∑eIe/ρe\\sum\_\{e\}I\_\{e\}/\\rho\_\{e\}creates a ratio estimator\. These variants can lower MSE and are included in the ablation, but they are not called exactly unbiased\.

#### Fixed\-size and exact\-cost designs\.

Independent Bernoulli continuation satisfies the expected cost constraint and givesρi​j=πi​πj\\rho\_\{ij\}=\\pi\_\{i\}\\pi\_\{j\}\. Conditional Poisson sampling can fix the number of endpoints while preserving prescribed first\-order probabilities\([8](https://arxiv.org/html/2608.11368#bib.bib31)\); thenρi​j\\rho\_\{ij\}does not generally factor and must be computed or estimated from the actual design\. Variable suffix lengths make an exact token budget a stochastic knapsack problem\. We use expected cost in the main method and report realized budget dispersion\.

#### At least two completed vertices\.

The HT estimator remains unbiased even when a design draw observes fewer than two vertices: that draw contributes the zero vector and is compensated by inverse weights on draws that observe edges\. In training, frequent zero\-edge draws are undesirable\. The default budget and probability floor make them rare; an optional uniformly sampled anchor pair can be assigned conditional probability one, with all resulting conditional joint probabilities logged\. Rejection\-resampling without updatingρi​j\\rho\_\{ij\}is not allowed\.

## Appendix CImplementation Details

#### Prefix checkpoint\.

We checkpoint afterτ∈\{128,256,512\}\\tau\\in\\\{128,256,512\\\}generated tokens, snapping to the next newline or sentence delimiter within 32 tokens\. Every candidate uses independent decoding randomness; candidates share only the fixed prompt, not a stochastic prefix\. KV caches for selected prefixes are resumed directly, while unselected caches are released\.

#### Heads and calibration\.

Both heads in Eq\. \([5](https://arxiv.org/html/2608.11368#S4.E5)\) are two\-layer MLPs with hidden width 256, SiLU activation, and layer normalization\. Their input is the mean of the last 16 prefix hidden states, detached from the policy graph\. The success head uses IPW Brier loss; the cost head uses the IPW squared log\-error in Eq\. \([7](https://arxiv.org/html/2608.11368#S4.E7)\)\. We maintain a 2,048\-label replay window, fit a scalar temperature on its newest quarter, and log Brier score, ECE \(15 equal\-mass bins\), and cost mean absolute percentage error\.

#### Probability optimization\.

The released reference solves Eqs\. \([10](https://arxiv.org/html/2608.11368#S4.E10)\)– \([11](https://arxiv.org/html/2608.11368#S4.E11)\) with SLSQP in double precision, warm\-started from the previous step’s probabilities\. We stop at relative objective change10−610^\{\-6\}or 50 iterations and fall back to uniform probabilities with the same expected cost if the solver fails\. The default floor isπmin=0\.08\\pi\_\{\\min\}=0\.08\. Every step logs the probability vector, predicted costs, realized costs, solver residual, observed edge count, maximum weight, and ESS\.

#### Numerical stability\.

Pair coefficients in Eq\. \([13](https://arxiv.org/html/2608.11368#S4.E13)\) are accumulated in FP32, centered across the observed endpoints, and then cast to the policy precision\. The exact configuration does not clip weights\. Practical variants usewmax∈\{10,20,50\}w\_\{\\max\}\\in\\\{10,20,50\\\}or Hájek self\-normalization and report the induced bias in the frozen\-policy audit\.

## Appendix DDetailed Experimental Protocol

### D\.1Data and contamination controls

#### Mathematics\.

Training uses the official 7,500\-problem MATH train split; the original test split is never used for optimization\([10](https://arxiv.org/html/2608.11368#bib.bib37)\)\. We remove exact and MinHash near\-duplicates against MATH500, AIME24, AMC23, and OlympiadBench before training\. Answers are parsed from the final boxed expression and checked with symbolic normalization plus exact string fallbacks\. Any parser exception is a failed rollout and is counted in both accuracy and cost\.

#### Code\.

Training uses the public TACO train split and its unit tests\([20](https://arxiv.org/html/2608.11368#bib.bib40)\)\. Evaluation uses LiveCodeBench problems released after the training\-data cutoff\([15](https://arxiv.org/html/2608.11368#bib.bib42)\)\. Programs run in a network\-disabled sandbox with per\-test CPU and memory limits\. Compilation failures, timeouts, and unsafe system calls receive zero reward\. We report full pass rate, average test pass rate, and pass@kk\.

### D\.2Training configuration

Table 4:Default training configuration\. Values are protocol commitments, not experimental outcomes\.The implementation uses HybridFlow/verl for orchestration\([33](https://arxiv.org/html/2608.11368#bib.bib45)\)and vLLM for generation\([19](https://arxiv.org/html/2608.11368#bib.bib46)\)\. We pre\-register separate budgets for generated response tokens, policy forward/backward FLOPs, and elapsed time because an algorithm can save suffixes while adding synchronization or head overhead\.

### D\.3Metrics and statistics

For each evaluation set we report pass@1 from a fixed decoding configuration, plus pass@8 for exploration\-sensitive analysis\. Training efficiency is measured by generated tokens to a fixed validation threshold and by area under the accuracy\-versus\-token curve\. Estimator audits use

MSE=𝔼​‖𝒈^−𝒈^full‖22,ESS=\(∑ewe\)2∑ewe2\.\\operatorname\{MSE\}=\\mathbb\{E\}\\\|\\widehat\{\\bm\{g\}\}\-\\widehat\{\\bm\{g\}\}\_\{\\mathrm\{full\}\}\\\|\_\{2\}^\{2\},\\quad\\operatorname\{ESS\}=\\frac\{\(\\sum\_\{e\}w\_\{e\}\)^\{2\}\}\{\\sum\_\{e\}w\_\{e\}^\{2\}\}\.Question\-level uncertainty uses paired bootstrap intervals; training\-level comparisons use seed means and standard deviations\. A claimed gain requires its 95% paired bootstrap interval to exclude zero on the primary aggregate and no material regression on either domain\. Hyperparameters are chosen on held\-out training questions, never on reported test sets\.

## Appendix EAdditional Experiment Matrix

This appendix expands the four evaluation questions from Section[6](https://arxiv.org/html/2608.11368#S6)into estimator, robustness, and calibration checks\. The frozen\-population study isolates the sampling design from policy optimization, while the sweeps below test whether the mechanism in Figure[2](https://arxiv.org/html/2608.11368#S4.F2)remains stable when prefix information, budgets, and weight regularization change\.

#### Estimator fidelity at matched generation cost\.

Table[5](https://arxiv.org/html/2608.11368#A5.T5)compares endpoint\- and edge\-sampling designs against the complete candidate graph\. Bias and MSE diagnose target recovery; cosine similarity measures update direction; and the final three columns expose the cost of obtaining that estimate\. Figure[4](https://arxiv.org/html/2608.11368#S6.F4)shows the corresponding controlled audit\.

Table 5:Frozen\-policy audit matrix\. Every row is replayed against the same fully generated candidate populations; vertices/edges/tokens are means over design draws\.Direct edge HT matches theUU\-statistic algebra but pays for edges without reusing completed vertices, so its suffix cost is higher \(0\.610\.61\) and MSE worse than vertex designs\. Marginal\-only weighting reduces but does not eliminate bias relative to unweighted selection, consistent with Table[3](https://arxiv.org/html/2608.11368#S6.T3)\.

#### Robustness across design regimes\.

Table[6](https://arxiv.org/html/2608.11368#A5.T6)separates robustness failures caused by prefix timing, graph size, budget pressure, positivity, reward structure, and weighting\. Each configuration reports both task performance and estimator quality\. Cells report the recommended \(middle\) setting on Qwen3\-1\.7B unless noted; slash\-separated values follow the listed setting order\.

Table 6:Sensitivity and robustness suite on Qwen3\-1\.7B\. Math is the four\-benchmark mathematics average\(\(84\.8\+29\.4\+63\.1\+46\.8\)/4=56\.0\)\(\(84\.8\{\+\}29\.4\{\+\}63\.1\{\+\}46\.8\)/4\{=\}56\.0\); Code is LiveCodeBench\. The first row is the default operating point used in the main tables\.Performance peaks nearτ=256\\tau\{=\}256and budget ratio0\.50\.5: shorter prefixes under\-inform the contrast graph, while longer prefixes waste tokens that could have funded suffixes\. Extremely smallπmin\\pi\_\{\\min\}preserves theoretical positivity but collapses ESS; large floors flatten the design toward uniform sampling\. A looser0\.750\.75budget further reduces gradient MSE but spends more tokens than the default matched protocol\.

#### Predictor quality and allocation quality\.

Table[7](https://arxiv.org/html/2608.11368#A5.T7)evaluates the auxiliary statistics that construct the contrast graph\. Brier score and ECE measure correctness calibration; gradient MSE measures whether calibration translates into a useful sampling design\. The oracle row bounds the improvement available from better prefix statistics\.

Table 7:Predictor diagnostics on frozen Qwen3\-1\.7B checkpoints\. Calibration, not raw classification accuracy, determines whether sampling probabilities and edge proxies are useful\.The two\-head predictor used in the main experiments is the best learned option\. A direct pair\-energy head is competitive on MSE but slightly worse calibrated\. The oracle gap \(0\.1450\.145vs\.0\.1210\.121\) shows remaining headroom from better prefix statistics rather than from the graph objective itself\.

## Appendix FExtended Discussion and Failure Modes

#### When pointwise allocation is sufficient\.

If the target objective decomposes into fixed per\-trajectory terms whose advantages are computed before pruning, marginal inverse probabilities may be enough\. PAIR is useful specifically when endpoint selection determines which group\-relative comparisons exist\. If the prefix probe is nearly as expensive as full generation, or the policy produces short responses, its additional machinery is unlikely to pay off\.

#### Near\-saturated groups\.

When everyp^i\\widehat\{p\}\_\{i\}is near zero or one, predicted disagreement is small and all edge proxies shrink\. The probability floor preserves support but can spend most of the budget on statistically weak pairs\. Prompt\-level selection remains complementary: it can decide whether to instantiate a candidate graph, while PAIR decides which graph vertices to complete\.

#### Correlated rollouts\.

Theorem[1](https://arxiv.org/html/2608.11368#Thmtheorem1)assumes conditionally independent rollouts\. Shared stochastic prefixes, coupled decoding, or tree expansion introduce cross\-score terms\. If two completions branch from one random prefix, the prefix score cancels in𝒔i−𝒔j\\bm\{s\}\_\{i\}\-\\bm\{s\}\_\{j\}, so the pair kernel targets only the continuation\-conditional gradient unless a separate prefix term is added\. Our main protocol uses independent prefixes; extension to trees requires an explicit hierarchical estimand\.

#### Negative transfer from predictor error\.

The allocation program can amplify a systematically wrong head by assigning large probabilities to edges with spurious energy\. IPW preserves the target when probabilities are known, but does not guarantee low variance\. We therefore separate estimator bias, design variance, predictor calibration, and downstream optimization rather than attributing all failures to one metric\.