PAIR: Pairwise-Aware Inclusion Reweighting for Adaptive Rollout Allocation in RLVR
On the map: LLM reasoning → Reinforcement learning for reasoning
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.
Key facts. Cited by 1 paper 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.
Builds on
33 of 44 references.
Closest ancestors · 18
Same direction, newest first
- 2026Learning as Reasoning Unfolds: Progressive Rollout Allocation for Efficient Reinforcement Learning24 Jul
- 2026Rethinking Groups in Critic-Free RLVR15 Jun
- 2026Where to Spend Rollouts: Hit-Utility Optimal Rollout Allocation for Group-Based RLVR8 May
- 2026Dynamics-Predictive Sampling for Active RL Finetuning of Large Reasoning Models11 Mar
- 2026Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization4 Mar
- 2026Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic1 Mar
- 2026Small Generalizable Prompt Predictive Models Can Steer Efficient RL Post-Training of Large Reasoning Models2 Feb
- 2025Stabilizing Policy Gradients for Sample-Efficient Reinforcement Learning in LLM Reasoning1 Oct
- 2025Improving Sampling Efficiency in RLVR through Adaptive Rollout and Response Reuse30 Sep
- 2025Depth-Breadth Synergy in RLVR: Unlocking LLM Reasoning Gains with Adaptive Exploration19 Aug
- 2025Act Only When It Pays: Efficient Reinforcement Learning for LLM Reasoning via Selective Rollouts2 Jun
- 2025Self-Evolving Curriculum for LLM Reasoning20 May
6 more
- 2025Online Difficulty Filtering for Reasoning Oriented Reinforcement Learning4 Apr
- 2025Understanding R1-Zero-Like Training: A Critical Perspective26 Mar
- 2025DAPO: An Open-Source LLM Reinforcement Learning System at Scale18 Mar
- 2025REINFORCE++: Stabilizing Critic-Free Policy Optimization with Global Advantage Normalization4 Jan
- 2023Let's Verify Step by Step31 May
- 2017Proximal Policy Optimization Algorithms20 Jul
Other references · 15
- 2021Training Verifiers to Solve Math Word Problemscited by 9,743
- 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
- 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
- 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
- 2024HybridFlow: A Flexible and Efficient RLHF Frameworkcited by 1,980
- 2024LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Codecited by 1,906
- 2024OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problemscited by 1,099
- 2026Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewardscited by 15
- 2026GradAlign: Gradient-Aligned Data Selection for LLM Reinforcement Learningcited by 10
- 2026TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learningcited by 9
- 2018Counting Motifs with Graph Samplingcited by 3
- 2026DUET: Optimize Token-Budget Allocation for Reinforcement Learning with Verifiable Rewardscited by 3
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2026Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR
- 2026Where Rollouts Begin: Low-Load, High-Leverage First-Token Diversification for RLVR
- 2026Contextual Rollout Bandits for Reinforcement Learning with Verifiable Rewards
- 2026DataFlex-RL: An Evaluation Platform for RLVR Data Policies
- 2026How to Allocate, How to Learn? Dynamic Rollout Allocation and Advantage Modulation for Policy Optimization
- 2026RolloutPipe: Overlapping Pipelined Rollout and Training in Disaggregated On-Policy LLM Reinforcement Learning
- 2026SALT: When More Rollouts Don't Help in Group-Based Policy Optimization and How to Make Them Matter
- 2026CERO: Where and When to Allocate Rollouts for RL Post-Training