Where to Spend Rollouts: Hit-Utility Optimal Rollout Allocation for Group-Based RLVR

• URL: http://arxiv.org/abs/2605.07114v1
• Date: Fri, 08 May 2026 01:42:25 GMT
• Title: Where to Spend Rollouts: Hit-Utility Optimal Rollout Allocation for Group-Based RLVR
• Abstract summary: Group-based policy optimization methods typically allocate a fixed number of rollouts to every prompt.<n>We introduce hit utility, the posterior probability that at least one rollout in a proposed additional allocation for a prompt will be correct.<n>We propose Hit-Utility Optimal Rollout Allocation (HORA), a learning-free rollout allocation policy.
• Score: 25.35547462790362
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning with verifiable rewards (RLVR) has emerged as a central paradigm for improving the reasoning capabilities of large language models. Group-based policy optimization methods, such as GRPO, typically allocate a fixed number of rollouts to every prompt. This uniform allocation can be inefficient: it over-allocates compute to prompts whose sampled groups are already saturated while under-exploring prompts for which additional samples may reveal useful correct trajectories. To address this limitation, we introduce hit utility, the posterior probability that at least one rollout in a proposed additional allocation for a prompt will be correct. Building on this notion, we propose Hit-Utility Optimal Rollout Allocation (HORA), a learning-free rollout allocation policy that maximizes total posterior hit utility within each allocation batch. HORA adaptively reallocates rollout budgets while leaving the downstream reward evaluation and group-based advantage estimator unchanged. Across four mathematical reasoning benchmarks and three model scales, HORA preserves comparable Pass@1 and improves Pass@K over compute-matched GRPO in ten of twelve model--benchmark configurations, with one tie and one saturated exception. It is also drop-in compatible with other group-based estimators such as RLOO. Ablation studies indicate that the uniform prior used by HORA is competitive with five prompt-conditioned learned-prior alternatives.

Related papers

• When Correct Solutions Repeat: Rarity-Aware Credit Redistribution for GRPO [25.979415525596007]
  Reinforcement learning with verifiable rewards (RLVR)<n>We formalize this behavior as multiplicity-induced structure-level credit concentration.<n> Cue-GRPO instantiates this rule with- out auxiliary-model inference.
  arXiv  Detail & Related papers  (2026-08-04T11:02:26Z)
• RRPO: Reference-Relative Policy Optimization with Stratified Conditional Rollouts [84.20747697259326]
  Group Relative Policy Optimization (GRPO) has shown strong effectiveness in reinforcement learning from verifiable feedback.<n>We propose textbfReference-Relative Policy Optimization (RRPO), which generalizes GRPO by replacing direct correctness-based advantage construction with reference-relative contrastive comparisons.<n>We evaluate RRPO using anchor-based contrastive advantages throughout policy optimization, without relying on task ground-truth verifiers.
  arXiv  Detail & Related papers  (2026-07-20T19:40:25Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• Advantage Collapse in Group Relative Policy Optimization: Diagnosis and Mitigation [13.272542054938258]
  We introduce the Advantage Collapse Rate (ACR), the first metric quantifying the proportion of training batches with ineffective gradients.<n>We then propose Adaptive Virtual Sample Policy Optimization (AVSPO), a lightweight extension of GRPO that injects virtual reward samples.<n>AVSPO reduces advantage collapse by 58-63% relative to GRPO and yields consistent accuracy gains of 4-6 percentage points across all model scales.
  arXiv  Detail & Related papers  (2026-05-20T12:57:37Z)
• Breaking $\ extit{Winner-Takes-All}$: Cooperative Policy Optimization Improves Diverse LLM Reasoning [53.42577591449649]
  Group Cooperative Policy Optimization shifts the training paradigm from rollout competition to team cooperation.<n>GCPO replaces independent rollout scoring with team-level credit assignment.<n>It redistributes the collective team reward to each single rollout according to its average marginal contribution to the team.
  arXiv  Detail & Related papers  (2026-05-12T03:20:24Z)
• Too Correct to Learn: Reinforcement Learning on Saturated Reasoning Data [55.84428098924793]
  We propose Constrained Uniform Top-K Sampling (CUTS), a parameter-free decoding strategy enforcing structure-preserving exploration.<n>We integrate this into Mixed-CUTS, a training framework synergizing exploitative and exploratory rollouts to amplify intra-group advantage variance.<n> Notably, Mixed-CUTS improves Pass@1 accuracy on the challenging AIME25 benchmark by up to 15.1% over standard GRPO.
  arXiv  Detail & Related papers  (2026-04-20T16:43:28Z)
• Balanced Aggregation: Understanding and Fixing Aggregation Bias in GRPO [70.38763678943648]
  Reinforcement learning with verifiable rewards (RLVR) has become a central paradigm for improving reasoning and code generation in large language models.<n>Standard GRPO uses sequence aggregation, while recent work has advocated token aggregation as a better alternative.<n>We show that these two rules induce different optimization biases; token aggregation introduces sign-length coupling, while sequence aggregation implicitly downweights longer responses.
  arXiv  Detail & Related papers  (2026-04-14T09:48:46Z)
• Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization [60.87651283510059]
  Group Relative Policy Optimization (GRPO) effectively scales LLM reasoning but incurs prohibitive computational costs.<n>We propose Dynamic Pruning Policy Optimization (DPPO), a framework that enables dynamic pruning while preserving unbiased gradient estimation.<n>To mitigate the data sparsity induced by pruning, we introduce Dense Prompt Packing, a window-based greedy strategy.
  arXiv  Detail & Related papers  (2026-03-04T14:48:53Z)
• Train Less, Learn More: Adaptive Efficient Rollout Optimization for Group-Based Reinforcement Learning [37.10958874118462]
  Reinforcement learning (RL) plays a central role in large language model (LLM) post-training.<n>In GRPO, each query prompts the LLM to generate a group of rollouts with a fixed group size $N$.<n>When all rollouts in a group share the same outcome, either all correct or all incorrect, the group-normalized advantages become zero.<n>We introduce Adaptive Efficient Rollout Optimization (AERO), an enhancement of GRPO.
  arXiv  Detail & Related papers  (2026-02-15T23:14:05Z)
• Contextual Rollout Bandits for Reinforcement Learning with Verifiable Rewards [69.74686029941881]
  Reinforcement Learning with Verifiable Rewards (RLVR) is an effective paradigm for improving the reasoning capabilities of large language models.<n>We propose a unified neural scheduling framework that adaptively selects high-value rollouts throughout training.<n>Experiments on six mathematical reasoning benchmarks demonstrate consistent gains in performance and training efficiency across multiple RLVR optimization methods.
  arXiv  Detail & Related papers  (2026-02-09T10:51:58Z)
• Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards [26.5011687714416]
  Existing group-based policy optimization methods allocate a fixed number of rollouts for all training prompts.<n>This uniform allocation treats all prompts as equally informative, and could lead to inefficient computational budget usage and impede training progress.<n>We introduce VIP, a Variance-Informed Predictive allocation strategy that allocates a given rollout budget to the prompts in the incumbent batch to minimize the expected gradient variance of the policy update.
  arXiv  Detail & Related papers  (2026-02-02T03:50:01Z)
• From Absolute to Relative: Rethinking Reward Shaping in Group-Based Reinforcement Learning [7.6602542594279335]
  We propose Reinforcement Learning with Relative Rewards to shift reward shaping from absolute scoring to relative ranking.<n>We show that RLRR yields consistent performance improvements over standard group-based baselines across reasoning benchmarks and open-ended generation tasks.
  arXiv  Detail & Related papers  (2026-01-30T15:07:06Z)
• GDPO: Group reward-Decoupled Normalization Policy Optimization for Multi-reward RL Optimization [133.27496265096445]
  We show how to apply Group Relative Policy Optimization under multi-reward setting without examining its suitability.<n>We then introduce Group reward-Decoupled Normalization Policy Optimization (GDPO), a new policy optimization method to resolve these issues.<n>GDPO consistently outperforms GRPO, demonstrating its effectiveness and generalizability for multi-reward reinforcement learning optimization.
  arXiv  Detail & Related papers  (2026-01-08T18:59:24Z)
• OptPO: Optimal Rollout Allocation for Test-time Policy Optimization [11.375209834858135]
  Test-time policy optimization enables large language models to adapt to distribution shifts by leveraging feedback from self-generated rollouts.<n>We propose Optimal Rollout Allocation for Test-time Policy Optimization (OptPO), a principled framework that adaptively allocates inference budgets.
  arXiv  Detail & Related papers  (2025-12-02T15:38:52Z)
• Not All Rollouts are Useful: Down-Sampling Rollouts in LLM Reinforcement Learning [55.15106182268834]
  Reinforcement learning with verifiable rewards (RLVR) has emerged as the leading approach for enhancing reasoning capabilities in large language models.<n>It faces a fundamental compute and memory asymmetry: rollout generation is embarrassingly parallel and memory-light, whereas policy updates are communication-heavy and memory-intensive.<n>We introduce PODS (Policy Optimization with Down-Sampling), which decouples rollout generation from policy updates by training only on a strategically selected subset of rollouts.
  arXiv  Detail & Related papers  (2025-04-18T17:49:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.