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

arXiv: https://arxiv.org/abs/2608.11368 · HTML: https://mlsanity.com/paper/2608.11368/

## Key facts

- Cited by 1 papers in the map (data through 7 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 33 of its 44 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)

## Builds on (most cited first, 30 of 33)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problems](https://mlsanity.com/paper/2402.14008/) (2024)
- [REINFORCE++: Stabilizing Critic-Free Policy Optimization with Global Advantage Normalization](https://mlsanity.com/paper/2501.03262/) (2025)
- [Act Only When It Pays: Efficient Reinforcement Learning for LLM Reasoning via Selective Rollouts](https://mlsanity.com/paper/2506.02177/) (2025)
- [Self-Evolving Curriculum for LLM Reasoning](https://mlsanity.com/paper/2505.14970/) (2025)
- [Online Difficulty Filtering for Reasoning Oriented Reinforcement Learning](https://mlsanity.com/paper/2504.03380/) (2025)
- [Depth-Breadth Synergy in RLVR: Unlocking LLM Reasoning Gains with Adaptive Exploration](https://mlsanity.com/paper/2508.13755/) (2025)
- [Improving Sampling Efficiency in RLVR through Adaptive Rollout and Response Reuse](https://mlsanity.com/paper/2509.25808/) (2025)
- [Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic](https://mlsanity.com/paper/2603.01162/) (2026)
- [Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2602.01601/) (2026)
- [Small Generalizable Prompt Predictive Models Can Steer Efficient RL Post-Training of Large Reasoning Models](https://mlsanity.com/paper/2602.01970/) (2026)
- [GradAlign: Gradient-Aligned Data Selection for LLM Reinforcement Learning](https://mlsanity.com/paper/2602.21492/) (2026)
- [TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning](https://mlsanity.com/paper/2606.11119/) (2026)
- [Dynamics-Predictive Sampling for Active RL Finetuning of Large Reasoning Models](https://mlsanity.com/paper/2603.10887/) (2026)
- [Learning as Reasoning Unfolds: Progressive Rollout Allocation for Efficient Reinforcement Learning](https://mlsanity.com/paper/2607.22002/) (2026)
- [Stabilizing Policy Gradients for Sample-Efficient Reinforcement Learning in LLM Reasoning](https://mlsanity.com/paper/2510.00819/) (2025)
- [Where to Spend Rollouts: Hit-Utility Optimal Rollout Allocation for Group-Based RLVR](https://mlsanity.com/paper/2605.07114/) (2026)
- [Counting Motifs with Graph Sampling](https://mlsanity.com/paper/1802.07773/) (2018)
- [Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization](https://mlsanity.com/paper/2603.04135/) (2026)
- [DUET: Optimize Token-Budget Allocation for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2605.08441/) (2026)
- [sGPO: Trading Inference FLOPs for Training Efficiency in RLVR](https://mlsanity.com/paper/2606.08854/) (2026)

## Built on by (most cited first, 1 of 1)

- [SERA: Scale-Equalized Rollout Allocation for Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2609.36552/) (2026)

## Abstract (arXiv)

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-order U-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 introduce PAIR (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, PAIR improves average accuracy by +1.2 and +1.4 over the strongest pointwise allocator while using 51% and 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.