When a language model is trained with reinforcement learning on math problems, each training step first has the model write several answers ("rollouts") to a batch of prompts. The step cannot finish until the longest answer is done. Answer lengths range from tens of tokens to many thousands, so most GPUs sit idle while a few long chains of thought finish. Recent schedulers decide how many rollouts each prompt gets, and they charge every rollout the same unit cost. We propose to charge each batch what it actually costs in wall-clock time. Most of that cost comes from the longest rollout, and the expected maximum length of a set of rollouts has diminishing returns: adding one more rollout to a batch that already contains a long one adds little extra time. This makes the batch cost a submodular set function. Trading it off against the learning value of the rollouts is then a difference of two submodular functions. That problem can be solved with a well-behaved local-descent method whose inner step is exact convex minimization of the Lovász extension, the standard continuous relaxation of a submodular function.
In two sentences: existing rollout allocators ask how to spend a fixed number of rollouts, but the resource that actually runs out is wall-clock time per step, which is set by the slowest rollout. We model that time as a submodular function of the chosen rollouts and optimize value minus time exactly in its convex relaxation. The result allocates fewer samples to prompts whose answers have heavy length tails and more to prompts that are informative and quick to answer, without penalizing length inside any answer.
Where the idea sits relative to prior work
Three recent papers motivate this proposal by showing that uniform rollout allocation in group-based RL wastes compute. Group-based RL here means GRPO or RLOO: methods that estimate advantages by comparing several answers to the same prompt instead of training a critic network.
Knapsack RL scores the value of giving $N$ rollouts to a prompt with success rate $p$ as the probability of a nonzero gradient times an information term. It observes that this value has diminishing returns in $N$ and allocates a fixed rollout budget by greedy water-filling. VIP models per-prompt gradient variance as $p(1-p)$, tracks $p$ with a Gaussian process over prompt embeddings, solves a continuous relaxation, and rounds greedily. Contextual Rollout Bandits prunes and replays rollouts after they have been generated, using a learned scorer.
All three treat a rollout as one unit of cost. Knapsack RL names token-length disparity as its open limitation. We keep their value models and change the cost model.
The first version of this idea we considered was to use the Lovász extension to relax Knapsack RL's own objective. We dropped it. The objective there is a sum of per-prompt concave functions under a count budget, and for that separable problem greedy water-filling is already exactly optimal, so a relaxation adds nothing. The Lovász machinery earns its place only when the objective couples prompts. A straggler-dominated time cost does exactly that.
The method comes from classical work. Hazan and Kale and Jegelka et al. show that submodular minimization is equivalent to convex minimization of the Lovász extension over the unit cube. They use subgradients obtained by sorting and rounding by thresholding, which loses nothing. Discrete and Continuous Difference of Submodular Minimization supplies the outer algorithm for value-minus-cost objectives.
The Lovász-Softmax loss and the Lovász hinge show that sorting-based Lovász subgradients are cheap enough, at $O(p\log p)$, to sit inside deep-learning training loops. Our use differs: they relax a loss over predictions, while we relax a scheduling decision. Submodular RL optimizes submodular rewards over state trajectories with greedy marginal gains. It never uses the Lovász extension and does not address training compute.
Core Claim
Let the ground set $V$ contain one element $(i,j)$ for the $j$-th potential rollout of prompt $i$ in a candidate pool, for example 512 prompts times at most 32 rollouts. For a chosen set $S$, let $L_e$ be the random token length of rollout $e$. We define the step cost as
$$C(S) = a \sum_{e\in S} \mathbb{E}[L_e] + b\, \mathbb{E}\big[\max_{e\in S} L_e\big].$$
Here $a$ is the per-token throughput cost under batched decoding, and $b$ is the per-token sequential latency that gates the end of the step. The real cost is roughly the larger of these two terms; the sum is an upper bound within a factor of two. The second term is submodular because the maximum of nonnegative weights is submodular for every sampled realization of lengths, and taking an expectation preserves submodularity. The first term is modular, meaning additive over elements, so $C$ is submodular.
Let $U(S)=\sum_i V(|S\cap V_i|, \hat p_i)$ be Knapsack RL's value summed over prompts, where $V_i$ is prompt $i$'s block of candidate rollouts. Because each $V$ is concave in the count, $U$ is submodular. The per-step problem is
$$\min_{S\subseteq V}\; C(S) - \lambda\, U(S),$$
where $\lambda$ converts learning value into seconds.
We solve it by difference-of-submodular descent. At the current set $S_k$, we replace $U$ by a modular lower bound that equals $U$ at $S_k$, read off a greedy chain through $S_k$. The remaining problem, $C$ minus a modular function, is submodular. We minimize it exactly by projected subgradient descent on the Lovász extension of $C$, estimating $\mathbb{E}[\max]$ with a fixed set of Monte Carlo length samples so that subgradients cost one sort. We then round by picking the best level set. The objective never increases across iterations.
Prompts that are not scheduled are deferred to later steps rather than dropped. This keeps hard, long prompts in the curriculum.
The substantive prediction is this. The expected maximum of $N$ draws from a heavy-tailed length distribution grows with $N$ like a tail quantile, not like $N$ times the mean. The allocator should therefore cap sample counts on long-tail prompts and spend the saved latency on informative short prompts. Neither a unit-cost nor a token-cost knapsack can express this trade.
Research Program
We would build the allocator as a drop-in replacement for the budget step in a GRPO/RLOO trainer. It has three parts.
The first part is a length model: a per-prompt empirical length distribution from earlier epochs on DAPO-Math-17K. For unseen prompts it falls back to a small regressor on prompt embeddings, in the spirit of VIP's Gaussian process.
The second part is the success-rate tracker, reused from Knapsack RL.
The third part is the difference-of-submodular solver. With 16,384 ground elements and a few hundred Monte Carlo length samples, each subgradient is a few sorts. We expect the solver to add well under one percent of step time, comparable to VIP's reported ~0.8–1.1% overhead. We will measure this rather than assume it.
The analysis has three parts. We will characterize when the straggler term dominates, by measuring the fraction of generation time GPUs spend idle as a function of length dispersion. We will show that with deterministic lengths the inner problem collapses to a scan over length thresholds, which tells us exactly what uncertainty adds. We will also check whether excluding long prompts shifts response lengths or accuracy on hard problems. This is the exploration-versus-efficiency risk raised by Short-RL.
Baselines
The naive reference is standard GRPO with uniform allocation of 8 rollouts per prompt. It is what practitioners run, and it defines the idle-GPU problem we target.
The strongest existing method is Knapsack RL. On DAPO-Math-17K with Qwen2.5-7B and DeepSeek-R1-Distill-1.5B, it reports matching standard GRPO's performance at 4,096 rollouts using 2,048 rollouts, a 2x efficiency gain in rollout count. It also reports average improvements of 2–4 points, up to 9 on AMC. No reported result was found on Lacuna for Knapsack RL measured in wall-clock time per step, and that gap is what we exploit. We will rerun Knapsack RL with the same models, data, success-rate estimator, and total generation-time budget per step. Beating it means reaching its final average accuracy on AIME24/25, AMC23, MATH500, Minerva, and OlympiadBench in measurably less wall-clock time, and reporting accuracy at matched wall-clock.
VIP is a second strong competitor. It reports +12.3 Pass@32 and +6.3 Mean@32 on AIME2024 for Qwen2.5-Math-1.5B with RLOO. We will run it on that model under the same time budget.
The key ablation is a token-cost knapsack. It keeps everything but replaces $C$ with its modular part alone, so cost equals expected tokens, and it is solved exactly by greedy methods. This isolates whether the max-length term, the only reason for the Lovász machinery, matters.
A second ablation runs plain greedy selection on the full objective $C-\lambda U$. It tests whether the exact inner minimization beats a cheap heuristic on the same objective.
Why not just…?
Why not just charge each rollout its expected token count in Knapsack RL? This is the most natural fix for Knapsack RL's stated limitation. When throughput rather than latency gates the step, it should work as well as our method, because then $b$ is near zero and the problem is separable. Our claim holds only if the maximum-length term carries real weight. The token-cost ablation settles this directly. We will also report the measured ratio of $b$ to $a$ on our hardware, so readers can see when the simpler method suffices.
Why not just cap rollout length or add a length penalty? Truncation turns long correct answers into zero reward, and brevity pressure early in training suppresses exploration of hard problems. Short-RL conditions penalties on correctness for exactly this reason, and DRQA reports that truncation-style training erodes deep reasoning. Our allocator changes how many answers a prompt gets, never how long any answer may be. We will include a hard-cap baseline at the 95th-percentile length to show the accuracy it loses on AIME.
Why not just generate asynchronously so stragglers never block the step? This is a genuine threat. Pipelining with partially stale policies removes much of the idle time at the systems level, and nothing in our file evaluates it. Our method targets synchronous on-policy training, which the cited baselines all use. It is complementary in principle, because asynchrony still pays for long tails through staleness. We will run a bounded-staleness variant and report honestly whether our gain shrinks to noise there.
Why not just use one rollout per prompt with a repaired critic? BPCO matches 16-sample GRPO with a single response per prompt, but it adds critic memory and relies on privileged answers. It also still waits for the longest rollout in each batch, so our prompt-level scheduling applies to it too. We treat it as orthogonal rather than competing.
Proposed Experiments
We train Qwen2.5-Math-1.5B, DeepSeek-R1-Distill-1.5B, and Qwen2.5-7B on DAPO-Math-17K. The distilled model matters most here because its long chains of thought make length dispersion extreme. We evaluate on AIME24/25, AMC23, MATH500, Minerva, and OlympiadBench. Metrics are accuracy against wall-clock time, idle-GPU fraction during generation, effective gradient ratio, and tokens generated per step.
The first decisive check is whether our method beats the token-cost knapsack in time to target accuracy on the distilled model. If it does not, the submodular cost buys nothing and the idea fails.
The second is whether the gain grows with the dispersion of rollout lengths. We test this by comparing Qwen2.5-Math, where lengths vary less, against R1-Distill.
The third is whether deferral prevents accuracy loss on the hardest AIME problems relative to uniform GRPO. We also track response-length drift to catch any hidden brevity bias.
References
- Knapsack RL: Compute-Efficient Reinforcement Learning via Heterogeneous Rollout Allocation
- Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards
- Contextual Rollout Bandits for Reinforcement Learning with Verifiable Rewards
- Beyond Convexity: Online Submodular Minimization
- Online Submodular Minimization for Combinatorial Structures
- Discrete and Continuous Difference of Submodular Minimization
- The Lovász-Softmax Loss: A Tractable Surrogate for the Optimization of the Intersection-Over-Union Measure in Neural Networks
- Learning Submodular Losses with the Lovasz Hinge
- Submodular Reinforcement Learning
- Efficient RL Training for Reasoning Models via Length-Aware Optimization
- DRQA: Dynamic Reasoning Quota Allocation for Controlling Overthinking in Reasoning Large Language Models
- Best Practice Critic Optimization