PAIR Improves RLVR Accuracy, Reduces Token Generation Costs

Reinforcement Learning with Verifiable Rewards (RLVR) typically incurs substantial computational costs due to generating numerous long reasoning trajectories. Existing allocation strategies aim to reduce this by assigning budgets based on individual prompt, rollout, or token utility. However, these methods overlook a critical statistical mismatch: the gradient of the group-relative score is not a simple sum of independent point contributions but a second-order U-statistic involving pairs of rollouts. This means completing one rollout provides contrastive information against all other completed rollouts. To address this, researchers developed PAIR (Pairwise-Aware Inclusion Reweighting). PAIR models short rollout prefixes as vertices and pair-gradient terms as edges in a contrast graph. It uses a prefix-only predictor to estimate correctness and remaining token cost, then employs a convex design to select positive continuation probabilities under an expected suffix-token budget. Crucially, each edge induced by completed vertices is inverse-weighted by its logged joint inclusion probability. Under specific conditions, this approach yields an unbiased estimator for the complete candidate-pair gradient. In compute-matched RLVR experiments using Qwen3-1.7B/4B models, PAIR improved average accuracy by +1.2 and +1.4 over the strongest pointwise allocator, while simultaneously using 51% and 52% fewer generated tokens than full-group GRPO. An audit confirmed that unweighted adaptive selection introduces bias, whereas PAIR's pair-inclusion correction effectively recovers the complete-pair target at a matched suffix cost.