Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR

• URL: http://arxiv.org/abs/2607.26253v1
• Date: Tue, 28 Jul 2026 20:43:23 GMT
• Title: Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR
• Abstract summary: We show that a group's effectiveness is usually decided early, within the first few of its rollouts, so spending a full group on an already-decided prompt is wasteful.<n>We apply a two-threshold, SPRT-style rule that commits effective groups, abandons saturated ones after a short probe, and reallocates the freed budget to fresh prompts.<n>We prove abandonment reliability, expected rollout savings, fixed-budget yield dominance, and a link between effective-group yield and the GRPO norm.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning with verifiable rewards (RLVR) is bottlenecked by rollout generation, yet many sampled prompts produce saturated groups (all responses correct or all incorrect) whose zero reward variance yields no policy-gradient signal. Existing remedies either oversample a larger candidate pool and discard saturated prompts (dynamic sampling), paying heavy extra rollouts, or predict prompt difficulty before sampling, which is fragile under a shifting policy. We observe that a group's effectiveness is usually decided early, within the first few of its rollouts, so spending a full group on an already-decided prompt is wasteful. We cast per-step rollout collection as a budget-constrained sequential allocation (optimal stopping) problem and introduce SARA (Sequential Adaptive Rollout Allocation). SARA maintains a Beta posterior over each prompt's success rate, evaluates a closed-form predictor of group effectiveness, and applies a two-threshold, SPRT-style rule that commits effective groups, abandons saturated ones after a short probe, and reallocates the freed budget to fresh prompts, without any extra prediction rollouts. We prove abandonment reliability, expected rollout savings, fixed-budget yield dominance, and a link between effective-group yield and the GRPO gradient norm. On mathematical reasoning and planning with 1.5B/3B models on a single GPU, SARA matches DPS (both below the DS oracle) while using 22% fewer rollouts than DS; composing SARA with DPS yields the best accuracy, slightly above DS, at 67% fewer rollouts (near-uniform cost).

Related papers

• ThinkPrior: Zero-Rollout Difficulty Priors for Cold-Start Prompt Selection in RLVR [0.38452047300097886]
  Group-relative advantages are identically zero if all rollouts in a group are correct or all are wrong.<n>History-based prompt selection must first spend target-policy rollouts to estimate difficulty.<n>ThinkPrior selects by expected learnability and then updates from training outcomes, changing neither the loss nor the gradient.<n>The measured ThinkPrior+DAPO composition reduces generated rollouts by 10.6% while both arms retain the same 3840-rollout update budget.
  arXiv  Detail & Related papers  (2026-09-08T17:30:12Z)
• Verifier-Induced Support Reshaping in On-Policy Optimization [27.782412748608255]
  We show that on-policy reinforcement learning with verifiable rewards (RLVR) can improve the current objective while making successful behaviors for later objectives too rare to sample and reinforce.<n>We call this verifier-induced support reshaping and define effective rewardable support as successful trajectories reachable within a fixed rollout budget.
  arXiv  Detail & Related papers  (2026-07-31T19:05:43Z)
• Learning as Reasoning Unfolds: Progressive Rollout Allocation for Efficient Reinforcement Learning [23.987185167160117]
  VarIance Guided Online Rollout allocation (VIGOR)<n>VarIance Guided Online Rollout allocation (VIGOR)<n>VarIance Guided Online Rollout allocation (VIGOR)
  arXiv  Detail & Related papers  (2026-07-24T06:04:04Z)
• 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)
• Cross-Epoch Adaptive Rollout Optimization for RL Post-Training [5.459625245330074]
  LLM post-training often relies on reinforcement learning methods that sample multiple rollouts per prompt.<n>Most existing approaches use a fixed rollout budget for every prompt, despite large differences in the training signal different prompts provide.<n>We study adaptive rollout allocation under a fixed global budget and formulate the problem as online resource allocation with prompt-level diminishing returns.
  arXiv  Detail & Related papers  (2026-06-04T02:27:51Z)
• RLVR without Ineffective Samples: Group Prioritized Off-Policy Optimization for LLM Reasoning [49.04912820721943]
  Group Prioritized Off-Policy Optimization (POPO) is a framework that exploits effective training batches without additional rollout overhead.<n>POPO comprises two key components: prioritized group replay and decoupled off-policy optimization.<n>POPO substantially accelerates RL finetuning and achieves strong reasoning performance with significantly fewer rollouts.
  arXiv  Detail & Related papers  (2026-05-31T15:06:38Z)
• Leveraging Error Diversity in Group Rollouts for Reinforcement Learning [61.10980882949414]
  Reinforcement Learning from Verifiable Rewards (RLVR) typically samples multiple responses per prompt and assigns binary rewards based on individual correctness.<n>We propose Error Diversity Advantage Shaping (EDAS) to modulate the advantage signal for incorrect rollouts based on intra-group error diversity.<n>EDAS operates as a simple post-hoc adjustment that can be seamlessly integrated into any RLVR algorithm.
  arXiv  Detail & Related papers  (2026-05-17T08:52:31Z)
• Breaking $\textit{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)
• Where to Spend Rollouts: Hit-Utility Optimal Rollout Allocation for Group-Based RLVR [25.35547462790362]
  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.
  arXiv  Detail & Related papers  (2026-05-08T01:42:25Z)
• Improving Search Agent with One Line of Code [68.58667107354253]
  Tool-based Agentic Reinforcement Learning (TARL) has emerged as a promising paradigm for training search agents to interact with external tools.<n>We propose textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO), which stabilizes training via a conditional token-level KL constraint.
  arXiv  Detail & Related papers  (2026-03-10T04:07:39Z)
• 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)
• 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.