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

# Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR
Source: [https://arxiv.org/html/2607.26253](https://arxiv.org/html/2607.26253)
Pixel Nomand1Elena Voss1Marcus Hale2Sofia Reyes1 1University of Wisconsin–Madison 2University of Washington

###### 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 introduceSARA\(Sequential Adaptive Rollout Allocation\)\.SARAmaintains 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,SARAmatches DPS \(both below the DS oracle\) while using 22% fewer rollouts than DS; composingSARAwith DPS yields the best accuracy, slightly above DS, at 67% fewer rollouts \(near\-uniform cost\)\.

## 1Introduction

Reinforcement learning with verifiable rewards \(RLVR\) has become the central post\-training mechanism for eliciting reasoning in large language models \(LLMs\), from mathematical problem solving to multi\-step planning and code\(Jaechet al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib2); Guoet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib1); Teamet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib3); Shaoet al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib4); Lightmanet al\.,[2023](https://arxiv.org/html/2607.26253#bib.bib6)\)\. Its dominant cost is*rollout generation*: each policy update consumes many long chain\-of\-thought samples\(Chenet al\.,[2025a](https://arxiv.org/html/2607.26253#bib.bib25); Suiet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib24)\), and deciding where to spend a limited rollout budget is a central design problem\(Zhenget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib11); Linet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib12); Aggarwal and Welleck,[2025](https://arxiv.org/html/2607.26253#bib.bib22)\)\.

![Refer to caption](https://arxiv.org/html/2607.26253v1/figures/fig_teaser.png)Figure 1:Sequential allocation spends rollouts where verdicts are contrastive\.*Left:*fixed\-kkallocation \(uniform sampling, or dynamic sampling after filtering\) generates a full group ofkkrollouts for every prompt;*saturated*groups \(all\-correct or all\-incorrect, faded\) have zero reward variance and contribute no GRPO gradient\.*Right:*SARAabandons a group as soon as its outcome is statistically decided and reallocates the freed budget to fresh prompts, assembling more effective \(mixed\) groups at∼\\sim22% lower cost\.A recurring obstacle is that prompts contribute very unevenly\. Under group\-based estimators such as GRPO\(Shaoet al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib4)\)and related variants\(Hu,[2025](https://arxiv.org/html/2607.26253#bib.bib7); Liuet al\.,[2025b](https://arxiv.org/html/2607.26253#bib.bib19);[a](https://arxiv.org/html/2607.26253#bib.bib17)\), a prompt whose sampled responses are*all*correct or*all*incorrect produces a zero\-variance reward group and hence a vanishing normalized advantage\(Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8); Baeet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib9)\)\. Such*saturated*groups are far from rare: under uniform sampling they routinely make up a majority of a batch \(Figure[2](https://arxiv.org/html/2607.26253#S2.F2)a\), so much of the rollout budget is spent producing gradients that are exactly zero\. Only*effective*groups \(those with a mixed outcome\) actually drive learning\.

Two families of methods attack this waste\. Evaluate\-then\-filter methods such as dynamic sampling \(DS\) in DAPO\(Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8)\)and online difficulty filtering\(Baeet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib9)\)oversample a larger candidate pool, generate full groups for all of them, and discard the saturated ones; this guarantees a clean batch but multiplies rollout cost and often dominates training\(Zhenget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib11); Linet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib12)\)\. Offline curation instead pre\-selects informative prompts by static difficulty or diversity\(Liet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib18); Yeet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib26); Wanget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib20)\), but cannot track a shifting online policy\. Predict\-then\-select methods estimate each prompt’s difficulty*before*sampling\(Chenet al\.,[2025b](https://arxiv.org/html/2607.26253#bib.bib10); Maoet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib14); Quet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib15)\)and prioritize the promising ones; this adds no extra rollouts but stakes the batch on a forecast, so when the policy shifts quickly or histories are sparse the predictions err and the batch is polluted again\(Zhanget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib13); Zhenget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib11)\)\. The two families sit at opposite ends of a*prediction\-versus\-verification*trade\-off: predict a prompt’s label before paying for it, or verify it by paying in full\. Both decide at the prompt level, before the group’s own rollouts can inform the choice \(as do selective generation and tree\-structured allocators\(Zhenget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib11); Zouet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib16)\)\), and so neither exploits the cheap evidence sitting inside the group itself\.

That evidence is the starting point for this work\. Within a group, the effectiveness verdict is typically reached long before the group is complete: once a prompt yields one correct*and*one incorrect response it is effective forever, since a mixed group cannot become unmixed, while a run of identical outcomes quickly concentrates the posterior over the success rate near0or11\. Empirically \(Figure[3](https://arxiv.org/html/2607.26253#S3.F3)a\), the eventual label of most groups is settled after only a handful of theirkkrollouts, so spending the fullkkon an already\-decided prompt wastes compute\. Reaching this verdict needs no extra model calls; it simply reads the rollouts the optimizer would generate anyway\. The same early\-stopping intuition underlies classical sequential analysis\(Wald,[1945](https://arxiv.org/html/2607.26253#bib.bib27); Robbins,[1952](https://arxiv.org/html/2607.26253#bib.bib29)\), which we adapt to per\-step RLVR budgeting\.

We therefore recast a single RLVR step as a budget\-constrained*sequential allocation*problem over a stream of prompts, and instantiate it asSARA\(Sequential Adaptive Rollout Allocation\)\.SARAprobes prompts in batched rounds; after each round it updates a Beta posterior over every active prompt’s success rate, evaluates a closed\-form posterior\-predictive probability that the group will be effective at full size, and applies a two\-threshold, sequential\-probability\-ratio\-style rule:*commit*a group once it is mixed,*abandon*it once it is almost surely saturated, and otherwise*continue*\. Abandoning a likely\-saturated prompt after a short probe frees rollouts that are reallocated to fresh prompts, so a fixed budget assembles more effective groups \(Figure[1](https://arxiv.org/html/2607.26253#S1.F1)\)\.SARAis orthogonal to prompt selection and composes with it, adds no prediction rollouts, and introduces only a handful of synchronization rounds\.

##### Contributions\.

\(1\) We identify*early decidability*of group effectiveness and reframe per\-step rollout collection as sequential allocation / optimal stopping, a budget axis orthogonal to prompt\-level selection\. \(2\) We derive a closed\-form Beta–Binomial effectiveness predictor and a two\-threshold stopping rule, yieldingSARA, a prediction\-rollout\-free allocator that drops into any GRPO\-style pipeline\. \(3\) We prove abandonment reliability, expected rollout savings, fixed\-budget yield dominance over uniform allocation, and a lower bound relating effective\-group yield to the expected squared GRPO gradient\. \(4\) On 1\.5B/3B models with a single GPU,SARAmatches DPS while using 22% fewer rollouts than DS, andSARA\+\+DPS edges DS at 67% fewer rollouts\.

## 2Preliminaries and Problem Setup

##### RLVR and GRPO\.

Letq∼𝒟q\\sim\{\\mathcal\{D\}\}be a prompt drawn from a dataset ando∼π𝜽\(⋅∣q\)o\\sim\\pi\_\{\\bm\{\\theta\}\}\(\\cdot\\mid q\)a response from policyπ𝜽\\pi\_\{\\bm\{\\theta\}\}\. RLVR maximizes the expected verifiable rewardmax𝜽⁡𝔼q∼𝒟,o∼π𝜽\(⋅∣q\)​\[r​\(q,o\)\]\\max\_\{\{\\bm\{\\theta\}\}\}\\,\\mathbb\{E\}\_\{q\\sim\{\\mathcal\{D\}\},\\,o\\sim\\pi\_\{\\bm\{\\theta\}\}\(\\cdot\\mid q\)\}\\,\[r\(q,o\)\], wherer​\(q,o\)∈\{0,1\}r\(q,o\)\\in\\\{0,1\\\}checks correctness\(Guoet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib1); Lightmanet al\.,[2023](https://arxiv.org/html/2607.26253#bib.bib6)\)\. Relative to PPO\(Schulmanet al\.,[2017](https://arxiv.org/html/2607.26253#bib.bib5)\), Group Relative Policy Optimization \(GRPO\)\(Shaoet al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib4)\)avoids a value network by sampling, for each promptqq, a group ofkkresponses\{oi\}i=1k\\\{o\_\{i\}\\\}\_\{i=1\}^\{k\}and normalizing rewards*within*the group:

A^i=r​\(q,oi\)−mean​\(\{r​\(q,oj\)\}j=1k\)std​\(\{r​\(q,oj\)\}j=1k\),𝒥​\(𝜽\)=𝔼​\[1k​∑imin⁡\(ρi​A^i,clip​\(ρi,1±ϵ\)​A^i\)\],\\hat\{A\}\_\{i\}\\;=\\;\\frac\{r\(q,o\_\{i\}\)\-\\mathrm\{mean\}\(\\\{r\(q,o\_\{j\}\)\\\}\_\{j=1\}^\{k\}\)\}\{\\mathrm\{std\}\(\\\{r\(q,o\_\{j\}\)\\\}\_\{j=1\}^\{k\}\)\},\\qquad\{\\mathcal\{J\}\}\(\{\\bm\{\\theta\}\}\)=\\mathbb\{E\}\\Big\[\\textstyle\\frac\{1\}\{k\}\\sum\_\{i\}\\min\\big\(\\rho\_\{i\}\\hat\{A\}\_\{i\},\\,\\mathrm\{clip\}\(\\rho\_\{i\},1\{\\pm\}\\epsilon\)\\hat\{A\}\_\{i\}\\big\)\\Big\],\(1\)with importance ratioρi=π𝜽​\(oi∣q\)/π𝜽old​\(oi∣q\)\\rho\_\{i\}=\\pi\_\{\\bm\{\\theta\}\}\(o\_\{i\}\\mid q\)/\\pi\_\{\{\\bm\{\\theta\}\}\_\{\\mathrm\{old\}\}\}\(o\_\{i\}\\mid q\)\. Subsequent variants retain this within\-group normalization while adjusting stability, length bias, or the critic\-free estimator\(Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8); Hu,[2025](https://arxiv.org/html/2607.26253#bib.bib7); Liuet al\.,[2025b](https://arxiv.org/html/2607.26253#bib.bib19);[a](https://arxiv.org/html/2607.26253#bib.bib17)\)\.

##### Effective and saturated groups\.

For a promptqqletγq=𝔼​\[r​\(q,o\)\]∈\[0,1\]\\gamma\_\{q\}=\\mathbb\{E\}\[r\(q,o\)\]\\in\[0,1\]be its \(latent, policy\- and step\-dependent\)success rate\. A group ofkkrollouts has success countSk∼Bin​\(k,γq\)S\_\{k\}\\sim\\mathrm\{Bin\}\(k,\\gamma\_\{q\}\)\.

###### Definition 1\(Effective group\)\.

A group iseffectiveif its success count is mixed,1≤Sk≤k−11\\leq S\_\{k\}\\leq k\-1, andsaturatedotherwise \(Sk∈\{0,k\}S\_\{k\}\\in\\\{0,k\\\}\)\.

A saturated group has zero reward variance, so everyA^i\\hat\{A\}\_\{i\}in Eq\. equation[1](https://arxiv.org/html/2607.26253#S2.E1)is0and the group contributes*no*gradient\. The probability that a group is effective isΦ​\(γq\)=1−γqk−\(1−γq\)k\\Phi\(\\gamma\_\{q\}\)\\,\{=\}\\,1\-\\gamma\_\{q\}^\{k\}\-\(1\-\\gamma\_\{q\}\)^\{k\}, which is near0for the many easy \(γq→1\\gamma\_\{q\}\\\!\\to\\\!1\) and hard \(γq→0\\gamma\_\{q\}\\\!\\to\\\!0\) prompts and peaks at intermediate difficulty\. Consequently, under uniform sampling a large fraction of each batch is saturated and wasted \(Figure[2](https://arxiv.org/html/2607.26253#S2.F2)a; cf\.Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8); Baeet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib9); Zhenget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib11)\)\.

![Refer to caption](https://arxiv.org/html/2607.26253v1/x1.png)Figure 2:Saturated groups dominate, andSARAkeeps the batch effective\.*\(a\)*Distribution of per\-group success counts under uniform sampling \(k=8k\{=\}8\): most groups sit ats=0s\{=\}0ors=ks\{=\}k\(zero gradient\)\.*\(b\)*Fraction of the*training batch*that is effective over training:SARA\(and the dynamic\-sampling oracle\) deliver near\-fully effective batches; predictive selection recovers most of it but degrades as the policy shifts; uniform sampling leaves the majority of the batch wasted\.
##### Per\-step budget and the two existing remedies\.

A vanilla GRPO step drawsBBprompts and generateskkrollouts each, spending a budget ofN=B⋅kN=B\\cdot krollouts but obtaining onlyΦ⋅B\\Phi\\cdot Beffective groups on average\.*Dynamic sampling*\(DS/DAPO\)\(Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8)\)and related online filters\(Baeet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib9); Zhanget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib13)\)over\-sample a candidate poolℬ^\\hat\{\\mathcal\{B\}\}\(with\|ℬ^\|\>B\|\\hat\{\\mathcal\{B\}\}\|\\\!\>\\\!B\), generate full groups for all candidates, and keep the effective ones,ℬt=\{q∈ℬ^:std​\(\{r​\(q,oi\)\}\)\>0\}\{\\mathcal\{B\}\}\_\{t\}=\\\{q\\in\\hat\{\\mathcal\{B\}\}:\\mathrm\{std\}\(\\\{r\(q,o\_\{i\}\)\\\}\)\>0\\\}; this yields a clean batch ofBBeffective groups but at expected cost≈B​k/Φ\\approx Bk/\\Phirollouts, several timesNN\.*Predictive selection*\(Chenet al\.,[2025b](https://arxiv.org/html/2607.26253#bib.bib10); Maoet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib14); Quet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib15)\)estimatesγq\\gamma\_\{q\}from history and samples prompts with intermediate predicted difficulty, spending no extra rollouts but risking a polluted batch when predictions err\. Length\-control methods instead shrink tokens*within*each rollout\(Aggarwal and Welleck,[2025](https://arxiv.org/html/2607.26253#bib.bib22); Houet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib23); Fatemiet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib21)\); they are complementary to deciding*how many*rollouts to collect\. We target a clean batch ofBBeffective groups while spending far fewer rollouts than DS and remaining robust to the prediction errors that limit predictive selection\.

##### Goal\.

At each step, assembleBBeffective groups for the GRPO update, minimizing the rollouts \(and tokens\) spent, using*only*the outcomes of the rollouts themselves \(no auxiliary evaluation passes\)\.

## 3Sequential Adaptive Rollout Allocation

### 3\.1Rollout collection as sequential allocation

Within one RLVR step we receive a stream of prompts and must, under a rollout budget, assembleBBeffective groups\. Thekkrollouts of a prompt need not be generated at once: we may generate a few, inspect their outcomes, and decide whether to invest more in this prompt or move on\. This is a finite\-horizon sequential decision problem\. For promptqqwithnnobserved rollouts andsssuccesses so far, we choose among \{commit, abandon, continue\}; abandoning frees budget for other prompts\. The objective is to maximize the number of effective groups obtained per rollout \(equivalently, to minimize the rollouts spent to obtainBBeffective groups\), using only the observed outcomes\(n,s\)\(n,s\)\. We show this admits a near\-optimal index policy \(App\.[C](https://arxiv.org/html/2607.26253#A3)\);SARAis its tractable, closed\-form realization\.

##### Prior methods as boundary cases\.

Viewed this way, existing efficiency methods are degenerate*stopping policies*on the same decision tree\. Uniform sampling and dynamic sampling never stop early: they commit every prompt to a full group ofkkrollouts and only then read its label, so they pay for saturated groups in full\. Predict\-then\-select methods stop atn=0n\{=\}0, before any rollout, by acting on a difficulty forecast, trading rollout cost for prediction risk\. These sit at opposite ends of one axis:*how much evidence to gather before deciding*\. The Bayes\-optimal amount of evidence is neither “none” \(blind prediction\) nor “allkk” \(no early stopping\), but a data\-dependent stopping time\.SARAgathers just enough evidence to decide each group and no more, which turns filter vs\. predict vs\. allocate into one sequential\-decision problem\.

### 3\.2Early decidability of group effectiveness

We place a Beta priorγq∼Beta​\(α0,β0\)\\gamma\_\{q\}\\sim\\mathrm\{Beta\}\(\\alpha\_\{0\},\\beta\_\{0\}\)on each success rate \(uniformα0=β0=1\\alpha\_\{0\}\{=\}\\beta\_\{0\}\{=\}1by default; an informative prior from history is an option, Section[4](https://arxiv.org/html/2607.26253#S4)\)\. After observingnnrollouts withsssuccesses, conjugacy gives the posteriorγq∣\(n,s\)∼Beta​\(α0\+s,β0\+n−s\)\\gamma\_\{q\}\\mid\(n,s\)\\sim\\mathrm\{Beta\}\(\\alpha\_\{0\}\{\+\}s,\\beta\_\{0\}\{\+\}n\{\-\}s\)\. The quantity that governs the decision is the posterior\-predictive probability that the*completed*group of sizekkwill be effective\.

###### Proposition 1\(Closed\-form effectiveness predictor\)\.

Letr=k−nr=k\-nremaining rollouts\. The posterior\-predictive probability of an effective group is

peff​\(n,s\)=\{1,s≥1​and​n−s≥1​\(already mixed\),1−B​\(α0,β0\+n\+r\)B​\(α0,β0\+n\),s=0,1−B​\(α0\+n\+r,β0\)B​\(α0\+n,β0\),s=n,p^\{\\mathrm\{eff\}\}\(n,s\)\\;=\\;\\begin\{cases\}1,&s\\geq 1\\text\{ and \}n\-s\\geq 1\\ \\text\{\(already mixed\)\},\\\\\[2\.0pt\] 1\-\\dfrac\{\\mathrm\{B\}\(\\alpha\_\{0\},\\,\\beta\_\{0\}\+n\+r\)\}\{\\mathrm\{B\}\(\\alpha\_\{0\},\\,\\beta\_\{0\}\+n\)\},&s=0,\\\\\[8\.0pt\] 1\-\\dfrac\{\\mathrm\{B\}\(\\alpha\_\{0\}\+n\+r,\\,\\beta\_\{0\}\)\}\{\\mathrm\{B\}\(\\alpha\_\{0\}\+n,\\,\\beta\_\{0\}\)\},&s=n,\\end\{cases\}\(2\)whereB​\(⋅,⋅\)\\mathrm\{B\}\(\\cdot,\\cdot\)is the Beta function\. With a uniform prior ands=0s\{=\}0this simplifies topeff​\(n,0\)=1−n\+1k\+1=k−nk\+1p^\{\\mathrm\{eff\}\}\(n,0\)=1\-\\frac\{n\+1\}\{k\+1\}=\\frac\{k\-n\}\{k\+1\}\(symmetrically fors=ns\{=\}n\)\.

###### Proposition 2\(Irreversibility and monotone decidability\)\.

Effectiveness is absorbing: once a group is mixed it stays effective regardless of further rollouts\. Along an all\-fail \(resp\. all\-pass\) prefix,peff​\(n,s\)p^\{\\mathrm\{eff\}\}\(n,s\)is strictly decreasing innn\. Hence each prompt is*decided*at a well\-defined stopping time, and the fraction of groups decided afternnrollouts increases monotonically to11\(Figure[3](https://arxiv.org/html/2607.26253#S3.F3)a\)\.

![Refer to caption](https://arxiv.org/html/2607.26253v1/x2.png)Figure 3:Mechanism ofSARA\.*\(a\)*Fraction of groups whose final effectiveness label is already decided afternnobserved rollouts \(committed\-effective\+\+confidently\-abandoned\); most verdicts are reached well beforen=kn\{=\}k, and they agree with the oracle label\.*\(b\)*The closed\-form predictorpeff​\(n,s\)p^\{\\mathrm\{eff\}\}\(n,s\)of Eq\. equation[2](https://arxiv.org/html/2607.26253#S3.E2)with the abandon region \(peff<τlowp^\{\\mathrm\{eff\}\}<\\tau\_\{\\mathrm\{low\}\}\) outlined\.*\(c\)*Effective groups collected versus rollouts spent:SARAreaches a full clean batch at a fraction of the cost of dynamic sampling\.##### Two\-threshold sequential rule\.

Givenpeff​\(n,s\)p^\{\\mathrm\{eff\}\}\(n,s\),SARAapplies a sequential test reminiscent of Wald’s SPRT\(Wald,[1945](https://arxiv.org/html/2607.26253#bib.bib27)\), with a single lower thresholdτlow\\tau\_\{\\mathrm\{low\}\}because the upper decision \(mixed⇒\\Rightarroweffective\) is exact:

decide​\(n,s\)=\{commitif the group is mixed \(and size≥commit floor\),abandonif​peff​\(n,s\)<τlow,continueotherwise \(sample one more rollout\)\.\\textsc\{decide\}\(n,s\)=\\begin\{cases\}\\textsc\{commit\}&\\text\{if the group is mixed \(and size $\\geq$ commit floor\)\},\\\\ \\textsc\{abandon\}&\\text\{if \}p^\{\\mathrm\{eff\}\}\(n,s\)<\\tau\_\{\\mathrm\{low\}\},\\\\ \\textsc\{continue\}&\\text\{otherwise \(sample one more rollout\)\}\.\\end\{cases\}\(3\)A committed group enters the training batch; an abandoned prompt is dropped and its remaining budget is reallocated\. The thresholdτlow\\tau\_\{\\mathrm\{low\}\}is the single knob trading rollout savings against the risk of abandoning a would\-be\-effective prompt \(analyzed below and in Section[4](https://arxiv.org/html/2607.26253#S4)\)\.

### 3\.3TheSARAalgorithm

SARAruns in batched, round\-synchronous fashion \(Figure[4](https://arxiv.org/html/2607.26253#S3.F4)\): each round issues a*single*batched generation call over all active prompts \(preserving inference throughput\), then applies Eq\. equation[3](https://arxiv.org/html/2607.26253#S3.E3)and reallocates\. Committed prompts leave the working set; abandoned prompts free budget that is used to draw fresh prompts; continuing prompts, prioritized by a yield index \(we usepeffp^\{\\mathrm\{eff\}\}, a one\-step look\-ahead toward effective groups\), receive one more rollout\. The loop ends whenBBeffective groups are collected or the safety budget is exhausted\. Algorithm[1](https://arxiv.org/html/2607.26253#alg1)summarizes one step\.

![Refer to caption](https://arxiv.org/html/2607.26253v1/figures/fig_architecture.png)Figure 4:SARAinside one GRPO step\.Prompts are probed in batched rounds; a Beta posterior and the closed\-form predictorpeffp^\{\\mathrm\{eff\}\}route each group tocommit/continue/abandon; abandoned budget is reallocated to fresh prompts, and only effective groups reach the update\. No auxiliary prediction rollouts are used\.Algorithm 1SARA: one RLVR step \(round\-synchronous\)1:prompt pool

𝒟\{\\mathcal\{D\}\}; target

BBeffective groups; group size

kk; probe

n0n\_\{0\}; threshold

τlow\\tau\_\{\\mathrm\{low\}\}; prior

\(α0,β0\)\(\\alpha\_\{0\},\\beta\_\{0\}\); budget cap

NN\.

2:

𝒞←∅\\mathcal\{C\}\\leftarrow\\emptyset\(collected\);

𝒜←\\mathcal\{A\}\\leftarrowprobe

BBfresh prompts with

n0n\_\{0\}rollouts each⊳\\trianglerightone batched call

3:while

\|𝒞\|<B\|\\mathcal\{C\}\|<Bandbudget left and

𝒜≠∅\\mathcal\{A\}\\neq\\emptysetdo

4:foreach active prompt

q∈𝒜q\\in\\mathcal\{A\}with stats

\(nq,sq\)\(n\_\{q\},s\_\{q\}\)do

5:

d←decide​\(nq,sq\)d\\leftarrow\\textsc\{decide\}\(n\_\{q\},s\_\{q\}\)via Eq\. equation[3](https://arxiv.org/html/2607.26253#S3.E3)

6:if

d=commitd=\\textsc\{commit\}thenmove

qqto

𝒞\\mathcal\{C\}
7:elseif

d=abandond=\\textsc\{abandon\}thendrop

qq⊳\\trianglerightfree its budget

8:endif

9:endfor

10:reallocate:draw fresh prompts \(probe

n0n\_\{0\}\) to refill the working set toward the remaining need

11:advance the continuing prompts by one rollout, prioritized by

peffp^\{\\mathrm\{eff\}\}⊳\\trianglerightone batched call

12:endwhile

13:return

𝒞\\mathcal\{C\}; perform a GRPO update \(Eq\.[1](https://arxiv.org/html/2607.26253#S2.E1)\) on the effective groups in

𝒞\\mathcal\{C\}

##### Cost\.

The only overhead beyond generation is, per active prompt per round, a Beta update and one evaluation of Eq\. equation[2](https://arxiv.org/html/2607.26253#S3.E2)\(a fewlog⁡Γ\\log\\Gammaevaluations\):O​\(1\)O\(1\)time and memory, negligible against a single LLM rollout, and requiring zero extra model calls\. The number of synchronization rounds isO​\(k\)O\(k\)in the worst case but small in practice \(most groups are decided in22–44rounds, Figure[3](https://arxiv.org/html/2607.26253#S3.F3)a\)\.

### 3\.4Theoretical guarantees

We summarize four results; full statements and proofs are in App\.[C](https://arxiv.org/html/2607.26253#A3)\. The first bounds the only failure mode of early abandonment\.

###### Theorem 1\(Abandonment reliability\)\.

The posterior probability that an abandoned group would have been effective is exactlypeff<τlowp^\{\\mathrm\{eff\}\}<\\tau\_\{\\mathrm\{low\}\}\. Hence the expected number of effective groups lost per step is at mostτlow⋅\|abandoned\|\\tau\_\{\\mathrm\{low\}\}\\cdot\|\\text\{abandoned\}\|, and choosingτlow→0\\tau\_\{\\mathrm\{low\}\}\\to 0makesSARAlossless in the limit\.

###### Theorem 2\(Expected rollout savings\)\.

For a prompt with success rateγ\\gamma, the expected rolloutsSARAspends before deciding is at mostmin⁡\{k,n⋆​\(γ\)\}\\min\\\{k,\\,n^\{\\star\}\(\\gamma\)\\\}withn⋆​\(γ\)=O​\(log⁡\(1/τlow\)log⁡\(1/max⁡\(γ,1−γ\)\)\)n^\{\\star\}\(\\gamma\)\\\!=\\\!O\\\!\\big\(\\tfrac\{\\log\(1/\\tau\_\{\\mathrm\{low\}\}\)\}\{\\log\(1/\\max\(\\gamma,1\-\\gamma\)\)\}\\big\)for saturated prompts, strictly less thankk\. Aggregating over the difficulty distribution, the expected cost to assembleBBeffective groups is strictly below the≈B​k/Φ\\approx Bk/\\Phiof dynamic sampling, and the gap grows withkk\.

###### Theorem 3\(Fixed\-budget yield dominance\)\.

At a fixed rollout budget, the expected number of effective groups assembled bySARAis at least that of uniform fixed\-kkallocation, with strict inequality whenever the success\-rate distribution is non\-degenerate\.

###### Theorem 4\(Effective yield lower\-bounds the gradient\)\.

Saturated groups contribute exactly zero to the GRPO gradient\. Consequently the expected squared gradient norm obeys𝔼​‖∇𝛉𝒥‖2≥c⋅𝔼​\[\#​effective groups\]\\mathbb\{E\}\\\|\\nabla\_\{\\bm\{\\theta\}\}\{\\mathcal\{J\}\}\\\|^\{2\}\\geq c\\cdot\\mathbb\{E\}\[\\,\\\#\\text\{effective groups\}\\,\]for a constantc\>0c\>0depending on the per\-group gradient energy\. Maximizing effective\-group yield thus maximizes a lower bound on the per\-step update magnitude\.

Together, Thms\.[1](https://arxiv.org/html/2607.26253#Thmtheorem1)–[4](https://arxiv.org/html/2607.26253#Thmtheorem4)say thatSARAis reliable, cheaper than oversample\-and\-filter, never worse than uniform at fixed budget, and optimizes a quantity tied to learning progress\. App\.[C\.7](https://arxiv.org/html/2607.26253#A3.SS7)casts the step as a restless bandit and shows that the two\-threshold rule of Eq\. equation[3](https://arxiv.org/html/2607.26253#S3.E3)is the Bayes\-optimal stopping boundary under a single\-prompt relaxation and the myopic index policy in general\.

## 4Experiments

We evaluate whether sequential in\-sample allocation recovers DS\-level training signal at a fraction of its cost, and whether it stacks with predictive selection\. Related work is deferred to App\.[B](https://arxiv.org/html/2607.26253#A2)\.

### 4\.1Setup

##### Models, data, and compute\.

All runs use a single GPU with R1\-Distill\-Qwen\-1\.5B and Qwen2\.5\-3B\(Guoet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib1); Yanget al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib39)\)\. We train on the MATH\(Hendryckset al\.,[2021](https://arxiv.org/html/2607.26253#bib.bib34)\)and Countdown\(Panet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib37)\)splits with GRPO on verl\(Shenget al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib38)\), and evaluate pass@1 \(mean over 16 samples\) on AIME24, AMC23, MATH500\(Lightmanet al\.,[2023](https://arxiv.org/html/2607.26253#bib.bib6)\), Minerva\(Lewkowyczet al\.,[2022](https://arxiv.org/html/2607.26253#bib.bib35)\), and OlympiadBench\(Heet al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib36)\)\. Full hyper\-parameters and protocol are in App\.[E](https://arxiv.org/html/2607.26253#A5)\.

##### Baselines\.

We compare*Uniform*\(fixed\-kkGRPO\),*History Resampling*\(HR\)\(Zhanget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib13)\),*DPS*\(Maoet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib14)\), and*DS \(oracle\)*\(Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8)\), plusSARAand the compositionSARA\+\+DPS \(DPS orders the draw;SARAverifies in\-sample\)\. Unless noted,B=64B\{=\}64,k=8k\{=\}8,n0=2n\_\{0\}\{=\}2,τlow=0\.45\\tau\_\{\\mathrm\{low\}\}\{=\}0\.45, and every method is trained for the same300300\{\}optimizer steps; Uniform / HR / DPS spend exactlyB​kBkrollouts per step, while DS andSARAkeep sampling untilBBeffective groups are filled\. We report pass@1, total rollouts, and tokens to the reported checkpoint\.

Table 1:Main results\(pass@1, avg\. over 16 samples\)\.SARAmatches DPS at 22% fewer rollouts than DS;SARA\+\+DPS is most accurate at 67% fewer rollouts than DS\.Bold/underline: best/second among finetuned methods\. Roll\. \(M\) / Tok\. \(B\): totals to the reported checkpoint\.

### 4\.2Main Results

Table[1](https://arxiv.org/html/2607.26253#S4.T1)and Figure[5](https://arxiv.org/html/2607.26253#S4.F5)summarize the comparison\. Uniform improves over the base model but plateaus: most of its batch is saturated \(effective fraction≈26%\\approx\\\!26\\%\{\}\)\. DPS recovers much of the missing signal at Uniform cost, but its batch remains only as clean as its forecast\. DS guarantees a clean batch at roughly4×4\\timesUniform rollouts\.SARAreaches DPS\-level accuracy while spending 22% fewer rollouts than DS, by abandoning saturated groups early and recycling budget toward prompts that still carry within\-group variance\. Composing the two is strongest: DPS supplies a cheap ordering over the prompt stream, andSARAsupplies the in\-sample guarantee, soSARA\+\+DPS exceeds DS on accuracy at 67% fewer rollouts\.

![Refer to caption](https://arxiv.org/html/2607.26253v1/x3.png)Figure 5:Accuracy and cost over training\.\(a, b\) Pass@1 vs\. optimizer step on MATH \(1\.5B\) and Countdown \(3B\); every method runs for the same number of steps\. \(c\) MATH vs\. cumulative rollouts:SARA\+\+DPS reaches above\-DS accuracy with 67% fewer rollouts\.
### 4\.3Mechanism and Ablations

Figure[3](https://arxiv.org/html/2607.26253#S3.F3)a confirms early decidability: most groups are decided within22–44rollouts, and the verdicts agree with the oracle effective/saturated label\. At the budget that lets DS assemble a clean batch,SARAreaches the same clean batch earlier, using∼\\sim22%/23% fewer rollouts/tokens \(Figure[7](https://arxiv.org/html/2607.26253#A6.F7)\)\. Token savings are amplified because abandoned all\-fail traces are the longest and are cut after a short probe\.

Figure[2](https://arxiv.org/html/2607.26253#S2.F2)b isolates prediction versus verification\. DPS lifts the effective fraction from Uniform’s≈26%\\approx\\\!26\\%\{\}into the0\.80\.8–0\.90\.9range but never reaches a fully clean batch: a wrong forecast still spends a full group\.SARAholds the effective fraction near11throughout by reading current outcomes\.SARA\+\+DPS removes the residual gap by letting prediction order the queue while verification decides\.

Figure[6](https://arxiv.org/html/2607.26253#S4.F6)ablates the design \(details in App\.[F](https://arxiv.org/html/2607.26253#A6)\)\. Largerτlow\\tau\_\{\\mathrm\{low\}\}abandons earlier but increases wrong abandonments, matching Thm\.[1](https://arxiv.org/html/2607.26253#Thmtheorem1);τlow=0\.45\\tau\_\{\\mathrm\{low\}\}\{=\}0\.45saves∼\\sim22% of rollouts at8\.6%8\.6\\%\{\}abandonment loss\. Results are robust ton0∈\{1,…,4\}n\_\{0\}\\in\\\{1,\\dots,4\\\}\. Under a fixed budget equal to DS’s per\-step cost,SARAfillsBBeffective groups while Uniform recovers onlyΦ​B\\Phi B; disabling reallocation collapses the yield\. Savings over DS rise withkk, as predicted by Thm\.[2](https://arxiv.org/html/2607.26253#Thmtheorem2)\.

![Refer to caption](https://arxiv.org/html/2607.26253v1/x4.png)Figure 6:Ablations\.\(a\) abandon thresholdτlow\\tau\_\{\\mathrm\{low\}\}; \(b\) probe sizen0n\_\{0\}; \(c\) component ablation \(effective groups under a fixed budget equal to DS’s per\-step cost\); \(d\) savings vs\. DS grow with group sizekk\.
### 4\.4Compatibility

SARAacts on rollout collection, upstream of the optimizer, so it applies to any group\-based RL algorithm\. Table[2](https://arxiv.org/html/2607.26253#S4.T2)shows consistent gains whenSARAreplaces uniform collection under GRPO, PPO, RLOO, and Reinforce\+\+\(Schulmanet al\.,[2017](https://arxiv.org/html/2607.26253#bib.bib5); Hu,[2025](https://arxiv.org/html/2607.26253#bib.bib7)\)\. The same composition with DPS remains complementary across these recipes \(App\.[F](https://arxiv.org/html/2607.26253#A6)\)\.

Table 2:SARAis algorithm\-agnostic\(Countdown, Qwen2\.5\-3B, pass@1 on CD\-34 and the harder CD\-4\)\.SARAimproves every base RL algorithm at matched effective\-batch size\.

## 5Conclusion

We reframed per\-step RLVR rollout collection as sequential allocation and introducedSARA, which decides commit / abandon / continue from a group’s own rollouts via a Beta–Binomial predictor and a two\-threshold stopping rule\. The allocator needs no prediction rollouts, drops into GRPO\-style pipelines, and stacks with predictive selection\. Empirically,SARAmatches DPS\-level accuracy at a fraction of DS cost, andSARA\+\+DPS is both most accurate and cheapest among methods that fill every batch\. Theory links abandonment reliability, expected savings, and gradient signal to the same effectiveness predictor that drives the algorithm\.Limitations\.SARAassumes binary verifiable rewards and i\.i\.d\. rollouts within a group; extending the predictor to continuous rewards and correlated tree rollouts \(App\.[G](https://arxiv.org/html/2607.26253#A7)\), and validating at larger scale, remain open\.

#### Reproducibility Statement

Algorithmic details appear in Section[3](https://arxiv.org/html/2607.26253#S3)and Algorithm[1](https://arxiv.org/html/2607.26253#alg1), with proofs in App\.[C](https://arxiv.org/html/2607.26253#A3), implementation notes in App\.[D](https://arxiv.org/html/2607.26253#A4), and the full experimental protocol in App\.[E](https://arxiv.org/html/2607.26253#A5)\. We will release code and scripts to reproduce all figures and tables upon publication\.

#### Ethics Statement

SARAis a training\-efficiency method for RLVR; by reducing the rollouts and tokens needed per update it lowers the energy and monetary cost of reasoning\-LLM post\-training\. It inherits the general risks of more capable reasoning models and does not introduce new data or human\-subject concerns\. Our use of large language models in preparing this paper is disclosed in App\.[A](https://arxiv.org/html/2607.26253#A1)\.

## References

- L1: controlling how long a reasoning model thinks with reinforcement learning\.arXiv preprint arXiv:2503\.04697\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px3.p1.1),[Appendix G](https://arxiv.org/html/2607.26253#A7.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12)\.
- P\. Auer, N\. Cesa\-Bianchi, and P\. Fischer \(2002\)Finite\-time analysis of the multiarmed bandit problem\.Machine Learning47\(2\),pp\. 235–256\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px4.p1.1)\.
- S\. Bae, J\. Hong, M\. Y\. Lee, H\. Kim, J\. Nam, and D\. Kwak \(2025\)Online difficulty filtering for reasoning oriented reinforcement learning\.arXiv preprint arXiv:2504\.03380\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p2.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px2.p2.6),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12)\.
- D\. A\. Berry \(1972\)A bernoulli two\-armed bandit\.The Annals of Mathematical Statistics43\(3\),pp\. 871–897\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px4.p1.1)\.
- Q\. Chen, L\. Qin, J\. Liu, D\. Peng, J\. Guan, P\. Wang, M\. Hu, Y\. Zhou, T\. Gao, and W\. Che \(2025a\)Towards reasoning era: a survey of long chain\-of\-thought for reasoning large language models\.arXiv preprint arXiv:2503\.09567\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1)\.
- X\. Chen, J\. Lu, M\. Kim, D\. Zhang, J\. Tang, A\. Piché, N\. Gontier, Y\. Bengio, and E\. Kamalloo \(2025b\)Self\-evolving curriculum for LLM reasoning\.arXiv preprint arXiv:2505\.14970\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12)\.
- M\. Fatemi, B\. Rafiee, M\. Tang, and K\. Talamadupula \(2025\)Concise reasoning via reinforcement learning\.arXiv preprint arXiv:2504\.05185\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px3.p1.1),[Appendix G](https://arxiv.org/html/2607.26253#A7.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12)\.
- J\. C\. Gittins \(1979\)Bandit processes and dynamic allocation indices\.Journal of the Royal Statistical Society: Series B \(Methodological\)41\(2\),pp\. 148–164\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px4.p1.1),[Proposition 3](https://arxiv.org/html/2607.26253#Thmproposition3.p1.4.4)\.
- D\. Guo, D\. Yang, H\. Zhang, J\. Song, R\. Zhang, R\. Xu, Q\. Zhu, S\. Ma, P\. Wang, X\. Bi,et al\.\(2025\)DeepSeek\-r1: incentivizing reasoning capability in LLMs via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px1.p1.8),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px1.p1.1)\.
- C\. He, R\. Luo, Y\. Bai, S\. Hu, Z\. L\. Thai, J\. Shen, J\. Hu, X\. Han, Y\. Huang, Y\. Zhang,et al\.\(2024\)OlympiadBench: a challenging benchmark for promoting AGI with olympiad\-level bilingual multimodal scientific problems\.arXiv preprint arXiv:2402\.14008\.Cited by:[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px1.p1.1)\.
- D\. Hendrycks, C\. Burns, S\. Kadavath, A\. Arora, S\. Basart, E\. Tang, D\. Song, and J\. Steinhardt \(2021\)Measuring mathematical problem solving with the MATH dataset\.arXiv preprint arXiv:2103\.03874\.Cited by:[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px1.p1.1)\.
- B\. Hou, Y\. Zhang, J\. Ji, Y\. Liu, K\. Qian, J\. Andreas, and S\. Chang \(2025\)ThinkPrune: pruning long chain\-of\-thought of LLMs via reinforcement learning\.arXiv preprint arXiv:2504\.01296\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px3.p1.1),[Appendix G](https://arxiv.org/html/2607.26253#A7.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12)\.
- J\. Hu \(2025\)REINFORCE\+\+: stabilizing critic\-free policy optimization with global advantage normalization\.arXiv preprint arXiv:2501\.03262\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p2.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px1.p1.9),[§4\.4](https://arxiv.org/html/2607.26253#S4.SS4.p1.1)\.
- A\. Jaech, A\. Kalai, A\. Lerer, A\. Richardson, A\. El\-Kishky, A\. Low, A\. Helyar, A\. Madry, A\. Beutel, A\. Carney,et al\.\(2024\)OpenAI o1 system card\.arXiv preprint arXiv:2412\.16720\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1)\.
- A\. Lewkowycz, A\. Andreassen, D\. Dohan, E\. Dyer, H\. Michalewski, V\. Ramasesh, A\. Slone, C\. Anil, I\. Schlag, T\. Gutman\-Solo,et al\.\(2022\)Solving quantitative reasoning problems with language models\.Advances in Neural Information Processing Systems35,pp\. 3843–3857\.Cited by:[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px1.p1.1)\.
- X\. Li, H\. Zou, and P\. Liu \(2025\)LIMR: less is more for RL scaling\.arXiv preprint arXiv:2502\.11886\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1)\.
- H\. Lightman, V\. Kosaraju, Y\. Burda, H\. Edwards, B\. Baker, T\. Lee, J\. Leike, J\. Schulman, I\. Sutskever, and K\. Cobbe \(2023\)Let’s verify step by step\.arXiv preprint arXiv:2305\.20050\.Cited by:[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px1.p1.8),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px1.p1.1)\.
- Z\. Lin, M\. Lin, Y\. Xie, and R\. Ji \(2025\)CPPO: accelerating the training of group relative policy optimization\-based reasoning models\.arXiv preprint arXiv:2503\.22342\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1)\.
- M\. Liu, S\. Diao, X\. Lu, J\. Hu, X\. Dong, Y\. Choi, J\. Kautz, and Y\. Dong \(2025a\)ProRL: prolonged reinforcement learning expands reasoning boundaries in large language models\.arXiv preprint arXiv:2505\.24864\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p2.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px1.p1.9)\.
- Z\. Liu, C\. Chen, W\. Li, P\. Qi, T\. Pang, C\. Du, W\. S\. Lee, and M\. Lin \(2025b\)Understanding r1\-zero\-like training: a critical perspective\.arXiv preprint arXiv:2503\.20783\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p2.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px1.p1.9)\.
- Y\. Mao, Y\. Qu, Q\. Wang, H\. Zou, and X\. Ji \(2026\)Dynamics\-predictive sampling for active RL finetuning of large reasoning models\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[Appendix D](https://arxiv.org/html/2607.26253#A4.SS0.SSS0.Px4.p1.8),[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px4.p1.4),[Appendix F](https://arxiv.org/html/2607.26253#A6.SS0.SSS0.Px4.p1.2),[§1](https://arxiv.org/html/2607.26253#S1.p3.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px2.p1.9)\.
- J\. Pan, J\. Zhang, X\. Wang, L\. Yuan, H\. Peng, and A\. Suhr \(2025\)TinyZero\.Note:[https://github\.com/Jiayi\-Pan/TinyZero](https://github.com/Jiayi-Pan/TinyZero)Cited by:[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px1.p1.1)\.
- Y\. Qu, Q\. Wang, Y\. Mao, H\. Zou, Y\. Jiang, W\. Liu, C\. Bai, K\. Yang, Y\. Chen, S\. Yang, and X\. Ji \(2026\)Small generalizable prompt predictive models can steer efficient RL post\-training of large reasoning models\.InInternational Conference on Machine Learning \(ICML\),Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[Appendix G](https://arxiv.org/html/2607.26253#A7.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12)\.
- H\. Robbins \(1952\)Some aspects of the sequential design of experiments\.Bulletin of the American Mathematical Society58\(5\),pp\. 527–535\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p4.4)\.
- D\. Russo and B\. Van Roy \(2014\)Learning to optimize via posterior sampling\.Mathematics of Operations Research39\(4\),pp\. 1221–1243\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px4.p1.1),[Proposition 3](https://arxiv.org/html/2607.26253#Thmproposition3.p1.4.4)\.
- J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. Klimov \(2017\)Proximal policy optimization algorithms\.arXiv preprint arXiv:1707\.06347\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px1.p1.8),[§4\.4](https://arxiv.org/html/2607.26253#S4.SS4.p1.1)\.
- Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. K\. Li, Y\. Wu,et al\.\(2024\)DeepSeekMath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p2.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px1.p1.8)\.
- G\. Sheng, C\. Zhang, Z\. Ye, X\. Wu, W\. Zhang, R\. Zhang, Y\. Peng, H\. Lin, and C\. Wu \(2024\)HybridFlow: a flexible and efficient RLHF framework\.arXiv preprint arXiv:2409\.19256\.Cited by:[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px3.p1.11),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px1.p1.1)\.
- Y\. Sui, Y\. Chuang, G\. Wang, J\. Zhang, T\. Zhang, J\. Yuan, H\. Liu, A\. Wen, S\. Zhong, H\. Chen,et al\.\(2025\)Stop overthinking: a survey on efficient reasoning for large language models\.arXiv preprint arXiv:2503\.16419\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1)\.
- K\. Team, A\. Du, B\. Gao, B\. Xing, C\. Jiang, C\. Chen, C\. Li, C\. Xiao, C\. Du, C\. Liao,et al\.\(2025\)Kimi k1\.5: scaling reinforcement learning with LLMs\.arXiv preprint arXiv:2501\.12599\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1)\.
- W\. R\. Thompson \(1933\)On the likelihood that one unknown probability exceeds another in view of the evidence of two samples\.Biometrika25\(3\-4\),pp\. 285–294\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px4.p1.1),[Proposition 3](https://arxiv.org/html/2607.26253#Thmproposition3.p1.4.4)\.
- A\. Wald \(1945\)Sequential tests of statistical hypotheses\.The Annals of Mathematical Statistics16\(2\),pp\. 117–186\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p4.4),[§3\.2](https://arxiv.org/html/2607.26253#S3.SS2.SSS0.Px1.p1.3)\.
- Y\. Wang, Q\. Yang, Z\. Zeng, L\. Ren, L\. Liu, B\. Peng, H\. Cheng, X\. He, K\. Wang, J\. Gao,et al\.\(2025\)Reinforcement learning for reasoning in large language models with one training example\.arXiv preprint arXiv:2504\.20571\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1)\.
- A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Li, D\. Liu, F\. Huang, H\. Wei,et al\.\(2024\)Qwen2\.5 technical report\.arXiv preprint arXiv:2412\.15115\.Cited by:[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px1.p1.1)\.
- Y\. Ye, Z\. Huang, Y\. Xiao, E\. Chern, S\. Xia, and P\. Liu \(2025\)LIMO: less is more for reasoning\.arXiv preprint arXiv:2502\.03387\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1)\.
- Q\. Yu, Z\. Zhang, R\. Zhu, Y\. Yuan, X\. Zuo, Y\. Yue, T\. Fan, G\. Liu, L\. Liu, X\. Liu,et al\.\(2025\)DAPO: an open\-source LLM reinforcement learning system at scale\.arXiv preprint arXiv:2503\.14476\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px1.p1.1),[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px4.p1.4),[§1](https://arxiv.org/html/2607.26253#S1.p2.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px1.p1.9),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px2.p2.6),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px2.p1.9)\.
- X\. Zhang, J\. Wang, Z\. Cheng, W\. Zhuang, Z\. Lin, M\. Zhang, S\. Wang, Y\. Cui, C\. Wang, J\. Peng,et al\.\(2025\)SRPO: a cross\-domain implementation of large\-scale reinforcement learning on LLM\.arXiv preprint arXiv:2504\.14286\.Cited by:[Appendix E](https://arxiv.org/html/2607.26253#A5.SS0.SSS0.Px4.p1.4),[§1](https://arxiv.org/html/2607.26253#S1.p3.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px3.p1.12),[§4\.1](https://arxiv.org/html/2607.26253#S4.SS1.SSS0.Px2.p1.9)\.
- H\. Zheng, Y\. Zhou, B\. R\. Bartoldson, B\. Kailkhura, F\. Lai, J\. Zhao, and B\. Chen \(2025\)Act only when it pays: efficient reinforcement learning for LLM reasoning via selective rollouts\.arXiv preprint arXiv:2506\.02177\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p1.1),[§1](https://arxiv.org/html/2607.26253#S1.p3.1),[§2](https://arxiv.org/html/2607.26253#S2.SS0.SSS0.Px2.p2.6)\.
- H\. Zou, Q\. Wang, Y\. Qu, Y\. Jiang, L\. Cai, Y\. Mao, R\. Peng, X\. Xu, W\. Liu, K\. Yang, S\. Yang, and X\. Ji \(2026\)TRACE: a unified rollout budget allocation framework for efficient agentic reinforcement learning\.arXiv preprint arXiv:2606\.11119\.Cited by:[Appendix B](https://arxiv.org/html/2607.26253#A2.SS0.SSS0.Px2.p1.1),[Appendix G](https://arxiv.org/html/2607.26253#A7.SS0.SSS0.Px2.p1.2),[§1](https://arxiv.org/html/2607.26253#S1.p3.1)\.

## Appendix AUse of Large Language Models

Large language models were used solely as general\-purpose assistive tools during manuscript preparation: polishing wording, checking LaTeX, and suggesting references that the authors subsequently verified against primary sources\. No LLM was used to generate experimental results, proofs, or claims; all theoretical statements and their proofs \(App\.[C](https://arxiv.org/html/2607.26253#A3)\) were written and verified by the authors\. The method itself \(SARA\) concerns the RL training of LLMs but does not use an LLM as part of the research methodology beyond the standard RLVR pipeline it studies\.

## Appendix BRelated Work

We organize prior work along the prediction\-versus\-verification axis of Section[1](https://arxiv.org/html/2607.26253#S1)and placeSARAbetween its two extremes\.

##### RLVR and group\-relative optimization\.

RLVR scales reasoning by optimizing a policy against an automatically verifiable reward\(Guoet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib1); Jaechet al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib2); Teamet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib3)\)\. GRPO\(Shaoet al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib4)\)replaced PPO’s\(Schulmanet al\.,[2017](https://arxiv.org/html/2607.26253#bib.bib5)\)value network with a group\-normalized advantage; many variants tune stability, bias, and length\(Liuet al\.,[2025b](https://arxiv.org/html/2607.26253#bib.bib19); Hu,[2025](https://arxiv.org/html/2607.26253#bib.bib7); Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8); Liuet al\.,[2025a](https://arxiv.org/html/2607.26253#bib.bib17)\)\. The recurring principle is that the*within\-group reward variance*is the source of signal \(exactly what saturated groups lack\), which makes assembling effective groups the central efficiency lever and motivatesSARA\.

##### Sample\-efficient RLVR\.

Efforts to spend the rollout budget better fall into two main groups\.*\(i\) Prompt selection*chooses which prompts to train on: offline curation ranks prompts by static difficulty or diversity\(Liet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib18); Yeet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib26); Wanget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib20)\); online*evaluate\-then\-filter*methods \(dynamic sampling in DAPO\(Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8)\)and online difficulty filtering\(Baeet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib9)\)\) oversample a candidate pool, generate full groups, and discard saturated ones; and*predict\-then\-select*methods forecast difficulty*before*sampling\(Maoet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib14); Quet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib15); Chenet al\.,[2025b](https://arxiv.org/html/2607.26253#bib.bib10)\)\.*\(ii\) Rollout allocation*sets how many rollouts each prompt or trajectory prefix receives\(Zouet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib16)\)and prunes low\-value generations\(Zhenget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib11); Linet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib12)\)\. These all commit budget*before*a group’s own rollouts are observed \(evaluate\-then\-filter even pays full groups for the prompts it discards\)\.SARAinstead decides*during*a group’s own rollouts with an in\-sample sequential verdict: it needs no auxiliary evaluation passes, is robust to the prediction error that limits predict\-then\-select, and composes with prompt selection \(ourSARA\+\+DPS results in Section[4\.4](https://arxiv.org/html/2607.26253#S4.SS4)confirm the two axes stack\)\. The closest point of comparison is selective rollouts\(Zhenget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib11)\), which prune by a heuristic cutoff;SARAreplaces the heuristic with a closed\-form sequential\-testing rule carrying reliability, savings, and yield guarantees, and adds explicit budget*reallocation*\.SARAis also compatible with tree rollouts \(App\.[G](https://arxiv.org/html/2607.26253#A7)\)\.

##### Efficient reasoning and length\.

A parallel line reduces the*token*cost of each rollout by controlling reasoning length via RL penalties or pruning\(Aggarwal and Welleck,[2025](https://arxiv.org/html/2607.26253#bib.bib22); Houet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib23); Fatemiet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib21)\), surveyed bySuiet al\.\([2025](https://arxiv.org/html/2607.26253#bib.bib24)\); Chenet al\.\([2025a](https://arxiv.org/html/2607.26253#bib.bib25)\)\.SARAtargets the orthogonal*rollout\-count*axis and composes with length control; it already exploits the same observation that long all\-fail traces are especially wasteful \(Figure[7](https://arxiv.org/html/2607.26253#A6.F7)b\)\.

##### Sequential analysis, bandits, and optimal stopping\.

SARA’s formulation draws on classical sequential analysis \(Wald’s SPRT and the sequential design of experiments\(Wald,[1945](https://arxiv.org/html/2607.26253#bib.bib27); Robbins,[1952](https://arxiv.org/html/2607.26253#bib.bib29)\)\) and posterior sampling\(Thompson,[1933](https://arxiv.org/html/2607.26253#bib.bib30); Berry,[1972](https://arxiv.org/html/2607.26253#bib.bib31); Russo and Van Roy,[2014](https://arxiv.org/html/2607.26253#bib.bib32); Aueret al\.,[2002](https://arxiv.org/html/2607.26253#bib.bib33)\)\. Casting one RLVR step as a budget\-constrained restless bandit connectsSARAto Gittins\-style index policies\(Gittins,[1979](https://arxiv.org/html/2607.26253#bib.bib28)\), of whichSARAis the tractable myopic instance \(App\.[C\.7](https://arxiv.org/html/2607.26253#A3.SS7)\)\. To our knowledge, this is the first application of sequential hypothesis testing to RLVR rollout budgeting\.

## Appendix CProofs and Theoretical Analysis

Throughout, a prompt has latent success rateγ∈\[0,1\]\\gamma\\in\[0,1\], a group has target sizekk, and rollouts are conditionally i\.i\.d\.Bernoulli​\(γ\)\\mathrm\{Bernoulli\}\(\\gamma\)givenγ\\gamma\. We use a Beta priorγ∼Beta​\(α0,β0\)\\gamma\\sim\\mathrm\{Beta\}\(\\alpha\_\{0\},\\beta\_\{0\}\)\. Afternnrollouts withsssuccesses the posterior isγ∣\(n,s\)∼Beta​\(α0\+s,β0\+n−s\)\\gamma\\mid\(n,s\)\\sim\\mathrm\{Beta\}\(\\alpha\_\{0\}\+s,\\beta\_\{0\}\+n\-s\)\. Recall the Beta\-function identity𝔼γ∼Beta​\(a,b\)​\[γu​\(1−γ\)v\]=B​\(a\+u,b\+v\)/B​\(a,b\)\\mathbb\{E\}\_\{\\gamma\\sim\\mathrm\{Beta\}\(a,b\)\}\[\\gamma^\{u\}\(1\-\\gamma\)^\{v\}\]=\\mathrm\{B\}\(a\+u,b\+v\)/\\mathrm\{B\}\(a,b\)for integersu,v≥0u,v\\geq 0\.

### C\.1Proof of Proposition[1](https://arxiv.org/html/2607.26253#Thmproposition1)\(closed\-form predictor\)

A completed group of sizekkis effective iff1≤Sk≤k−11\\leq S\_\{k\}\\leq k\-1\. If the observed prefix is already mixed \(s≥1s\\geq 1andn−s≥1n\-s\\geq 1\) thenSk≥s≥1S\_\{k\}\\geq s\\geq 1andk−Sk≥\(n−s\)≥1k\-S\_\{k\}\\geq\(n\-s\)\\geq 1, so the group is effective with probability11\. Otherwise the prefix is all\-fail \(s=0s=0\) or all\-pass \(s=ns=n\); considers=0s=0\(the other case is symmetric byγ↔1−γ\\gamma\\leftrightarrow 1\-\\gamma\)\. Letr=k−nr=k\-nbe the remaining rollouts\. The group fails to be effective iff allrrremaining rollouts also fail \(thenSk=0S\_\{k\}=0\); it cannot be all\-pass since the prefix already containsnnfailures\. Hence

peff​\(n,0\)\\displaystyle p^\{\\mathrm\{eff\}\}\(n,0\)=1−Pr⁡\[remainingrall fail∣n,0\]=1−𝔼γ∼Beta​\(α0,β0\+n\)​\[\(1−γ\)r\]\\displaystyle=1\-\\Pr\[\\text\{remaining $r$ all fail\}\\mid n,0\]=1\-\\mathbb\{E\}\_\{\\gamma\\sim\\mathrm\{Beta\}\(\\alpha\_\{0\},\\beta\_\{0\}\+n\)\}\\\!\\big\[\(1\-\\gamma\)^\{r\}\\big\]=1−B​\(α0,β0\+n\+r\)B​\(α0,β0\+n\),\\displaystyle=1\-\\frac\{\\mathrm\{B\}\(\\alpha\_\{0\},\\,\\beta\_\{0\}\+n\+r\)\}\{\\mathrm\{B\}\(\\alpha\_\{0\},\\,\\beta\_\{0\}\+n\)\},\(4\)using the identity withu=0,v=ru=0,v=rand posterior parameters\(α0,β0\+n\)\(\\alpha\_\{0\},\\beta\_\{0\}\+n\)\. With a uniform priorα0=β0=1\\alpha\_\{0\}=\\beta\_\{0\}=1andB​\(1,m\)=1/m\\mathrm\{B\}\(1,m\)=1/m,peff​\(n,0\)=1−\(β0\+n\)\(β0\+n\+r\)=1−1\+n1\+k=k−nk\+1p^\{\\mathrm\{eff\}\}\(n,0\)=1\-\\frac\{\(\\beta\_\{0\}\+n\)\}\{\(\\beta\_\{0\}\+n\+r\)\}=1\-\\frac\{1\+n\}\{1\+k\}=\\frac\{k\-n\}\{k\+1\}, sinceβ0\+n\+r=1\+n\+\(k−n\)=1\+k\\beta\_\{0\}\+n\+r=1\+n\+\(k\-n\)=1\+k\. The all\-pass case is identical withα0↔β0\\alpha\_\{0\}\\leftrightarrow\\beta\_\{0\}ands=ns=n\. ∎

### C\.2Proof of Proposition[2](https://arxiv.org/html/2607.26253#Thmproposition2)\(irreversibility, monotonicity\)

*Irreversibility\.*If a prefix is mixed, thenSk≥s≥1S\_\{k\}\\geq s\\geq 1andk−Sk≥n−s≥1k\-S\_\{k\}\\geq n\-s\\geq 1for every completion, so the group remains effective; the event “effective” is absorbing along any rollout sequence\.*Monotonicity\.*Along an all\-fail prefix, by Proposition[1](https://arxiv.org/html/2607.26253#Thmproposition1)peff​\(n,0\)=1−B​\(α0,β0\+k\)/B​\(α0,β0\+n\)p^\{\\mathrm\{eff\}\}\(n,0\)=1\-\\mathrm\{B\}\(\\alpha\_\{0\},\\beta\_\{0\}\+k\)/\\mathrm\{B\}\(\\alpha\_\{0\},\\beta\_\{0\}\+n\)becauseβ0\+n\+r=β0\+k\\beta\_\{0\}\+n\+r=\\beta\_\{0\}\+kis constant innn\. The mapx↦B​\(α0,x\)=Γ​\(α0\)​Γ​\(x\)/Γ​\(α0\+x\)x\\mapsto\\mathrm\{B\}\(\\alpha\_\{0\},x\)=\\Gamma\(\\alpha\_\{0\}\)\\Gamma\(x\)/\\Gamma\(\\alpha\_\{0\}\+x\)is strictly decreasing inx\>0x\>0\(its logarithmic derivative isψ​\(x\)−ψ​\(α0\+x\)<0\\psi\(x\)\-\\psi\(\\alpha\_\{0\}\+x\)<0, whereψ\\psiis the digamma function\)\. HenceB​\(α0,β0\+n\)\\mathrm\{B\}\(\\alpha\_\{0\},\\beta\_\{0\}\+n\)strictly decreases innn, so the ratioB​\(α0,β0\+k\)/B​\(α0,β0\+n\)\\mathrm\{B\}\(\\alpha\_\{0\},\\beta\_\{0\}\+k\)/\\mathrm\{B\}\(\\alpha\_\{0\},\\beta\_\{0\}\+n\)strictly*increases*, andpeff​\(n,0\)p^\{\\mathrm\{eff\}\}\(n,0\)strictly decreases\. Therefore each same\-outcome run crosses the thresholdτlow\\tau\_\{\\mathrm\{low\}\}at a unique time, and every prompt is decided \(committed when it first becomes mixed, or abandoned at threshold crossing\) at a well\-defined stopping time≤k\\leq k\. The fraction of groups decided by roundnnis the CDF of this stopping time, hence nondecreasing and→1\\to 1atn=kn=k\. ∎

### C\.3Proof of Theorem[1](https://arxiv.org/html/2607.26253#Thmtheorem1)\(abandonment reliability\)

SARAabandons a prompt only from an all\-same prefix withpeff​\(n,s\)<τlowp^\{\\mathrm\{eff\}\}\(n,s\)<\\tau\_\{\\mathrm\{low\}\}\. By Proposition[1](https://arxiv.org/html/2607.26253#Thmproposition1),peff​\(n,s\)p^\{\\mathrm\{eff\}\}\(n,s\)is exactly the posterior probability that the completed group would be effective given the observed prefix\. Thus, conditioned on the data at the abandonment time, the probability that the abandoned group “would have been effective” equalspeff<τlowp^\{\\mathrm\{eff\}\}<\\tau\_\{\\mathrm\{low\}\}\. Letℬ\\mathcal\{B\}be the \(random\) set of abandoned prompts in a step\. The number of lost effective groups isL=∑q∈ℬ𝟏​\[q​would be effective\]L=\\sum\_\{q\\in\\mathcal\{B\}\}\\mathbf\{1\}\[q\\text\{ would be effective\}\], so by the tower rule𝔼​\[L\]=𝔼​\[∑q∈ℬpqeff\]≤τlow​𝔼​\|ℬ\|\\mathbb\{E\}\[L\]=\\mathbb\{E\}\\big\[\\sum\_\{q\\in\\mathcal\{B\}\}p^\{\\mathrm\{eff\}\}\_\{q\}\\big\]\\leq\\tau\_\{\\mathrm\{low\}\}\\,\\mathbb\{E\}\|\\mathcal\{B\}\|\. Asτlow→0\\tau\_\{\\mathrm\{low\}\}\\to 0, abandonment requirespeff=0p^\{\\mathrm\{eff\}\}=0, i\.e\.n=kn=kwith an all\-same group \(a genuinely saturated group\), so no effective group is ever lost:SARAis lossless in the limit\. Finally, the*commit*side is exact—a group is committed only after a mixed outcome is observed, which by Proposition[2](https://arxiv.org/html/2607.26253#Thmproposition2)guarantees effectiveness—so the only error mode is the one bounded above\. Viewing the all\-same run as a one\-sided sequential probability ratio test of “saturated” against “mixed”,τlow\\tau\_\{\\mathrm\{low\}\}is exactly the bound on its type\-II error, while the type\-I error is zero\. ∎

### C\.4Proof of Theorem[2](https://arxiv.org/html/2607.26253#Thmtheorem2)\(expected rollout savings\)

Fix the uniform prior; the abandonment time along a same\-outcome run is the firstnnwithpeff​\(n,0\)=k−nk\+1<τlowp^\{\\mathrm\{eff\}\}\(n,0\)=\\frac\{k\-n\}\{k\+1\}<\\tau\_\{\\mathrm\{low\}\}, i\.e\.na=k−⌊τlow​\(k\+1\)⌋n\_\{a\}=k\-\\lfloor\\tau\_\{\\mathrm\{low\}\}\(k\+1\)\\rfloor\(capped atkk\)\. LetTmixT\_\{\\mathrm\{mix\}\}be the first round at which both outcomes have appeared\. For aBernoulli​\(γ\)\\mathrm\{Bernoulli\}\(\\gamma\)stream,Pr⁡\[Tmix\>n\]=γn\+\(1−γ\)n\\Pr\[T\_\{\\mathrm\{mix\}\}\>n\]=\\gamma^\{n\}\+\(1\-\\gamma\)^\{n\}forn≥1n\\geq 1and=1=1forn=0n=0\.SARAstops a prompt atN=min⁡\(Tmix,na\)N=\\min\(T\_\{\\mathrm\{mix\}\},\\,n\_\{a\}\)\(commit ifTmix≤naT\_\{\\mathrm\{mix\}\}\\leq n\_\{a\}, else abandon\), so

𝔼​\[N​\(γ\)\]=∑n=0na−1Pr⁡\[N\>n\]=1\+∑n=1na−1\(γn\+\(1−γ\)n\)≤na≤k,\\mathbb\{E\}\[N\(\\gamma\)\]=\\sum\_\{n=0\}^\{n\_\{a\}\-1\}\\Pr\[N\>n\]=1\+\\sum\_\{n=1\}^\{n\_\{a\}\-1\}\\big\(\\gamma^\{n\}\+\(1\-\\gamma\)^\{n\}\\big\)\\;\\leq\\;n\_\{a\}\\;\\leq\\;k,\(5\)with equalityE​\[N\]=naE\[N\]=n\_\{a\}asγ→0\\gamma\\to 0or11\(always same\-outcome until abandonment\) and𝔼​\[N\]→2\\mathbb\{E\}\[N\]\\to 2asγ→12\\gamma\\to\\tfrac\{1\}\{2\}\(mixes almost immediately\)\. Dynamic sampling generates a*full*group ofkkrollouts for every prompt it evaluates \(kept or discarded\), i\.e\. a per\-prompt cost of exactlykk\. Since both schemes must evaluate, in expectation,B/ΦB/\\Phiprompts to obtainBBeffective groups \(each prompt is effective with probabilityΦ=𝔼γ​Φ​\(γ\)\\Phi=\\mathbb\{E\}\_\{\\gamma\}\\Phi\(\\gamma\)\), the expected per\-step costs are

costds=BΦ​k,costSARA=BΦ​𝔼γ​\[N​\(γ\)\]≤BΦ​k=costds,\\mathrm\{cost\}\_\{\\textsc\{ds\}\}=\\frac\{B\}\{\\Phi\}\\,k,\\qquad\\mathrm\{cost\}\_\{\\mbox\{SARA\}\{\}\}=\\frac\{B\}\{\\Phi\}\\,\\mathbb\{E\}\_\{\\gamma\}\[N\(\\gamma\)\]\\;\\leq\\;\\frac\{B\}\{\\Phi\}\\,k=\\mathrm\{cost\}\_\{\\textsc\{ds\}\},\(6\)with strict inequality wheneverPr\[γ∉\{\\Pr\[\\gamma\\notin\\\{values that mix beforena\}\]\>0n\_\{a\}\\\}\]\>0, i\.e\. whenever any prompt is ever abandoned or committed early\. The relative saving1−𝔼γ​\[N​\(γ\)\]/k1\-\\mathbb\{E\}\_\{\\gamma\}\[N\(\\gamma\)\]/kincreases withkk:na/k→1−τlown\_\{a\}/k\\to 1\-\\tau\_\{\\mathrm\{low\}\}while early\-commit caps effective groups at the commit floor independent ofkk, so for largekkboth terms in𝔼​\[N\]/k→\\mathbb\{E\}\[N\]/k\\toa constant<1<1shrinking the ratio\. \(With an informative prior the same argument yields a geometric concentrationna=O​\(log⁡\(1/τlow\)/log⁡\(1/max⁡\(γ,1−γ\)\)\)n\_\{a\}=O\(\\log\(1/\\tau\_\{\\mathrm\{low\}\}\)/\\log\(1/\\max\(\\gamma,1\-\\gamma\)\)\)\.\) ∎

### C\.5Proof of Theorem[3](https://arxiv.org/html/2607.26253#Thmtheorem3)\(fixed\-budget yield dominance\)

Fix a budget ofNNrollouts\. Uniform fixed\-kkallocation spends them onN/kN/kfull groups, yieldingYunif=Φ⋅N/kY\_\{\\mathrm\{unif\}\}=\\Phi\\cdot N/keffective groups in expectation\. ConsiderSARArun under the same budget\. We use an exchange argument\. Take any saturated prompt that uniform would run tokk\(contributing0effective groups forkkrollouts\)\. UnderSARAthis prompt is abandoned atN≤na<kN\\leq n\_\{a\}<krollouts \(Eq\. equation[5](https://arxiv.org/html/2607.26253#A3.E5)\); the savedk−N\>0k\-N\>0rollouts are reallocated to fresh prompts, each of which is effective with probabilityΦ\>0\\Phi\>0and contributes a nonnegative number of effective groups in expectation\. Replacing each such saturated full group by \[abandon early\+\+reallocate\] therefore does not decrease the expected effective count, and strictly increases it wheneverΦ\>0\\Phi\>0and at least one fresh group can be started with the freed budget\. Likewise, early\-committing an effective group atN<kN<kfrees budget without losing the group\. Summing these nonnegative exchanges,𝔼​\[YSARA\]≥Yunif\\mathbb\{E\}\[Y\_\{\\mbox\{SARA\}\{\}\}\]\\geq Y\_\{\\mathrm\{unif\}\}, with strict inequality whenever the success\-rate distribution places mass on saturated regions \(so abandonments occur\)\. ∎

### C\.6Proof of Theorem[4](https://arxiv.org/html/2607.26253#Thmtheorem4)\(effective yield bounds the gradient\)

For a saturated group the rewards are constant, so the group standard deviation is0and every normalized advantageA^i\\hat\{A\}\_\{i\}in Eq\. equation[1](https://arxiv.org/html/2607.26253#S2.E1)is0\(equivalently, the degenerate group is dropped\); its contribution to∇𝜽𝒥\\nabla\_\{\\bm\{\\theta\}\}\{\\mathcal\{J\}\}is the zero vector\. Hence∇𝜽𝒥=∑g∈ℰ𝒈g\\nabla\_\{\\bm\{\\theta\}\}\{\\mathcal\{J\}\}=\\sum\_\{g\\in\{\\mathcal\{E\}\}\}\{\\bm\{g\}\}\_\{g\}, whereℰ\{\\mathcal\{E\}\}is the set of effective groups and𝒈g\{\\bm\{g\}\}\_\{g\}is groupgg’s gradient\. Then

𝔼​‖∇𝜽𝒥‖2=𝔼​‖∑g∈ℰ𝒈g‖2=𝔼​∑g,g′∈ℰ⟨𝒈g,𝒈g′⟩=𝔼​∑g∈ℰ‖𝒈g‖2\+𝔼​∑g≠g′⟨𝒈g,𝒈g′⟩\.\\mathbb\{E\}\\\|\\nabla\_\{\\bm\{\\theta\}\}\{\\mathcal\{J\}\}\\\|^\{2\}=\\mathbb\{E\}\\Big\\\|\\sum\_\{g\\in\{\\mathcal\{E\}\}\}\{\\bm\{g\}\}\_\{g\}\\Big\\\|^\{2\}=\\mathbb\{E\}\\\!\\\!\\sum\_\{g,g^\{\\prime\}\\in\{\\mathcal\{E\}\}\}\\\!\\\!\\langle\{\\bm\{g\}\}\_\{g\},\{\\bm\{g\}\}\_\{g^\{\\prime\}\}\\rangle=\\mathbb\{E\}\\\!\\sum\_\{g\\in\{\\mathcal\{E\}\}\}\\\|\{\\bm\{g\}\}\_\{g\}\\\|^\{2\}\+\\mathbb\{E\}\\\!\\\!\\sum\_\{g\\neq g^\{\\prime\}\}\\\!\\langle\{\\bm\{g\}\}\_\{g\},\{\\bm\{g\}\}\_\{g^\{\\prime\}\}\\rangle\.\(7\)Assume \(i\) a normalized per\-group energy𝔼​\[‖𝒈g‖2∣g∈ℰ\]≥c\>0\\mathbb\{E\}\[\\\|\{\\bm\{g\}\}\_\{g\}\\\|^\{2\}\\mid g\\in\{\\mathcal\{E\}\}\]\\geq c\>0and \(ii\) nonnegative average cross\-alignment𝔼​∑g≠g′⟨𝒈g,𝒈g′⟩≥0\\mathbb\{E\}\\sum\_\{g\\neq g^\{\\prime\}\}\\langle\{\\bm\{g\}\}\_\{g\},\{\\bm\{g\}\}\_\{g^\{\\prime\}\}\\rangle\\geq 0\(e\.g\. gradients of distinct effective groups are conditionally uncorrelated, the standard mini\-batch assumption, giving equality to0\)\. Then𝔼​‖∇𝜽𝒥‖2≥c​𝔼​\|ℰ\|\\mathbb\{E\}\\\|\\nabla\_\{\\bm\{\\theta\}\}\{\\mathcal\{J\}\}\\\|^\{2\}\\geq c\\,\\mathbb\{E\}\|\{\\mathcal\{E\}\}\|\. Thus maximizing the expected number of effective groups maximizes a lower bound on the expected squared update magnitude, which connectsSARA’s allocation objective to optimization progress\. ∎

### C\.7Optimal stopping and the index\-policy view

We make precise the claim thatSARAis a myopic index policy\.

###### Proposition 3\(SARAas a sequential\-allocation index policy\)\.

Consider the per\-step problem of allocating a rollout budget across a stream of prompts \(arms\), each an unknown\-γ\\gammaBernoulli process withBeta\\mathrm\{Beta\}belief, where committing an effective group yields unit reward and each rollout costs one unit of budget\. \(a\) Under a single\-arm relaxation \(process one prompt to its stopping time before moving on\), the optimal policy is a stopping rule that continues while the expected value of one more rollout exceeds its cost; for the effective\-group objective this boundary is exactly the two\-threshold rule of Eq\. equation[3](https://arxiv.org/html/2607.26253#S3.E3)withτlow\\tau\_\{\\mathrm\{low\}\}set by the cost/reward ratio\. \(b\) For the full restless problem, the Gittins index\(Gittins,[1979](https://arxiv.org/html/2607.26253#bib.bib28)\)gives the optimal index policy in the discounted relaxation;SARA’s priority bypeffp^\{\\mathrm\{eff\}\}is its one\-step \(myopic\) approximation, and posterior\-sampling priority\(Thompson,[1933](https://arxiv.org/html/2607.26253#bib.bib30); Russo and Van Roy,[2014](https://arxiv.org/html/2607.26253#bib.bib32)\)is an alternative with the same fixed points\.

*Sketch\.*\(a\) The state of an arm is its posteriorBeta​\(α0\+s,β0\+n−s\)\\mathrm\{Beta\}\(\\alpha\_\{0\}\+s,\\beta\_\{0\}\+n\-s\); the value functionV​\(n,s\)V\(n,s\)satisfies the Bellman optimality equationV=max⁡\{stop value,continue value\}V=\\max\\\{\\text\{stop value\},\\ \\text\{continue value\}\\\}\. The stop value of a mixed prefix is11\(an effective group in hand\); the continue value of an all\-same prefix equals the discounted probability of eventually mixing, a monotone transform ofpeffp^\{\\mathrm\{eff\}\}by Proposition[2](https://arxiv.org/html/2607.26253#Thmproposition2); equating the two yields a threshold onpeffp^\{\\mathrm\{eff\}\}, i\.e\. Eq\. equation[3](https://arxiv.org/html/2607.26253#S3.E3)\. \(b\) is the standard Gittins decomposition for a bank of independent arms; the myopic indexpeffp^\{\\mathrm\{eff\}\}is exact when arms cannot be revisited \(our reallocation draws fresh arms\), and otherwise first\-order optimal\. ∎

## Appendix DAlgorithm and Implementation Details

##### Round\-synchronous batched scheduling\.

A naive “sample one rollout, decide, repeat” loop would destroy the throughput of batched inference engines\.SARAavoids this: each round issues a*single*batched generation call over all currently active prompts \(the initial round generatesn0n\_\{0\}rollouts per prompt; later rounds generate one continuation per continuing prompt\)\. Decisions, posterior updates, and reallocation happen between rounds on CPU inO​\(active prompts\)O\(\\text\{active prompts\}\)time\. Because most groups are decided within22–44rounds \(Figure[3](https://arxiv.org/html/2607.26253#S3.F3)a\), the number of synchronization points per step is small and the per\-call batch stays large, so wall\-clock overhead relative to a single monolithic generation is minor while the rollout/token*count*drops substantially\.

##### Integration with verl / TRL\.

SARAreplaces only the rollout\-collection stage of a GRPO trainer; the loss and optimizer are untouched\. Concretely \(seetrain\_grpo\_sara\.py\), one implements a single closurerollout\_fn\(prompt\_ids, count\)that maps a list of prompts and a per\-prompt count to a batchedgeneratecall and returns, per rollout, the verifiable reward and token length;SARA’s scheduler then orchestrates the rounds and hands the optimizer a list of effective groups\. This is a∼\\sim30\-line change to a verlDataProtogeneration hook or a TRLGRPOTrainersampling step\.

##### Variable group sizes\.

With early commit \(commit\_min=m=m\) effective groups have size in\[m,k\]\[m,k\]\. GRPO’s within\-group normalization \(Eq\.[1](https://arxiv.org/html/2607.26253#S2.E1)\) is well defined for any group size≥2\\geq 2; we pad/mask to the longest group in a micro\-batch\. The default setscommit\_min=k=k\(fixed\-size groups\), so the cost comparison with DS is not confounded by group size; early\-commit \(commit\_min=4=4\) is reported as an ablation in Figure[6](https://arxiv.org/html/2607.26253#S4.F6)c and further reduces rollouts at the cost of variable group sizes\.

##### Defaults and history warm\-start\.

Defaults:B=64B\{=\}64,k=8k\{=\}8,n0=2n\_\{0\}\{=\}2,τlow=0\.45\\tau\_\{\\mathrm\{low\}\}\{=\}0\.45,commit\_min=k\\texttt\{commit\\\_min\}\{=\}k, priorBeta​\(1,1\)\\mathrm\{Beta\}\(1,1\), safety budget cap6​B​k6Bk\. The optional warm\-start carries each prompt’s posterior across steps with an exponential decayλ\\lambda\(so a prompt seen to be saturated last step starts skewed and is abandoned after fewer probes\), mirroring the temporal discounting used by predictive selection\(Maoet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib14)\); it further reduces rollouts at the cost of one scalar of state per prompt\.

##### Complexity\.

Per prompt per round: one Beta update \(O​\(1\)O\(1\)\) and one evaluation of Eq\. equation[2](https://arxiv.org/html/2607.26253#S3.E2)\(a constant number oflog⁡Γ\\log\\Gammacalls\), plus anO​\(log⁡B\)O\(\\log B\)insertion into the priority structure\. No extra forward/backward passes and no auxiliary model\. Memory overhead is two integers \(or two floats with warm\-start\) per active prompt\.

## Appendix EDetailed Experimental Setup

##### Models\.

We use R1\-Distill\-Qwen\-1\.5B\(Guoet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib1)\)and Qwen2\.5\-3B\(Yanget al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib39)\)\(math\) and Qwen2\.5\-3B \(planning\)\. Both fit comfortably on a single GPU for both generation \(vLLM, bf16\) and the policy update, which is the point of the resource\-light design: the budget being allocated is rollouts/tokens, not GPUs\.

##### Datasets and evaluation\.

Training uses the MATH\(Hendryckset al\.,[2021](https://arxiv.org/html/2607.26253#bib.bib34)\)training split and a subset of Countdown\(Panet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib37)\)\. Math evaluation reports pass@1 \(mean over 16 samples, temperature 1\.0\) on AIME24, AMC23, MATH500\(Lightmanet al\.,[2023](https://arxiv.org/html/2607.26253#bib.bib6)\), Minerva\(Lewkowyczet al\.,[2022](https://arxiv.org/html/2607.26253#bib.bib35)\), and OlympiadBench\(Heet al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib36)\)\. Planning reports pass@1 on the in\-distribution CD\-34 and the harder CD\-4 split\. Rewards are binary verifiable correctness; format rewards, when present, are binarized by thresholding\.

##### RL configuration\.

GRPO on verl\(Shenget al\.,[2024](https://arxiv.org/html/2607.26253#bib.bib38)\): group sizek=8k\{=\}8, effective batchB=64B\{=\}64, learning rate1×10−61\{\\times\}10^\{\-6\}, KL coefficient1×10−31\{\\times\}10^\{\-3\}, clipϵ=0\.2\\epsilon\{=\}0\.2, max generation length40964096tokens, sampling temperature1\.01\.0,300300\{\}update steps on MATH \(matching the DPS 1\.5B schedule\) and120120on Countdown\. The base GRPO/PPO/RLOO/Reinforce\+\+ settings are shared across allocators so that only the rollout\-collection strategy differs; Uniform / HR / DPS spend exactlyB​kBkrollouts per step, while DS andSARAare goal\-driven and spend whatever is needed to fillBBeffective groups\.

##### Allocator configurations\.

*Uniform*: drawBBprompts,kkrollouts each\.*HR*: per\-epoch removal of fully\-solved prompts\(Zhanget al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib13)\)\.*DPS*: predictive selection that models each prompt’s solving state with a hidden Markov model and samples prompts predicted to be partially solved, with online Bayesian updates and temporal decay\(Maoet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib14)\)\.*DS \(oracle\)*: oversample candidate pool and keep effective groups\(Yuet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib8)\); cost grows as1/Φ1/\\Phi\.*SARA*: defaults above\.*SARA\+\+DPS*: DPS orders the draw,SARAverifies and abandons in\-sample\.

##### Metrics\.

We report pass@1 accuracy; total*rollouts*\(millions\) and*tokens*\(billions\) consumed to the reported checkpoint; per\-step effective\-group yield; and, in App\.[F](https://arxiv.org/html/2607.26253#A6), wall\-clock\. Rollouts and tokens are the hardware\-agnostic efficiency axes emphasized throughout\.

## Appendix FAdditional Experiments

![Refer to caption](https://arxiv.org/html/2607.26253v1/x5.png)Figure 7:Cost to assemble a clean batch\.*\(a\)*SARAuses∼\\sim22%/23% fewer rollouts/tokens than the DS oracle for an equally effective batch ofBBgroups\.*\(b\)*All\-fail \(hard\) rollouts are the longest, so abandoning them after a short probe saves disproportionate tokens\.##### Wall\-clock and token accounting\.

Beyond rollouts, Table[3](https://arxiv.org/html/2607.26253#A6.T3)reports single\-GPU wall\-clock and token totals for the 1\.5B math run\. BecauseSARAabandons the long all\-fail traces early \(Figure[7](https://arxiv.org/html/2607.26253#A6.F7)b\), its token and wall\-clock savings over DS exceed its rollout savings, while its overhead over uniform is small and is more than repaid by the higher\-quality batch\.

Table 3:Cost accounting\(1\.5B, MATH, single GPU,B=64B\{=\}64,300300\{\}steps\)\. Absolute rollouts are smaller than multi\-GPU setups that useB=256B\{=\}256, but the DS\-to\-Uniform ratio \(≈4×\\approx\\\!4\\times\) is comparable\.SARAattains DS\-level accuracy at a fraction of its rollouts, tokens, and wall\-clock\.
##### Sensitivity to the threshold and probe size\.

Figure[6](https://arxiv.org/html/2607.26253#S4.F6)\(a,b\) sweepsτlow\\tau\_\{\\mathrm\{low\}\}andn0n\_\{0\}\. The threshold cleanly trades savings against coverage as predicted by Thm\.[1](https://arxiv.org/html/2607.26253#Thmtheorem1): atτlow=0\.45\\tau\_\{\\mathrm\{low\}\}\{=\}0\.45SARAsaves∼\\sim22% of rollouts at8\.6%8\.6\\%\{\}abandonment loss; smallerτlow\\tau\_\{\\mathrm\{low\}\}is nearly lossless but saves less\. Results are stable acrossn0∈\{1,…,4\}n\_\{0\}\\in\\\{1,\\dots,4\\\}; very smalln0n\_\{0\}slightly increases wrong abandonments \(less evidence per decision\) and very largen0n\_\{0\}wastes probes, son0=2n\_\{0\}\{=\}2is a robust default\.

##### Savings grow with group size\.

Figure[6](https://arxiv.org/html/2607.26253#S4.F6)d shows the rollout saving over DS rising withkk\. This follows Thm\.[2](https://arxiv.org/html/2607.26253#Thmtheorem2): DS pays the fullkkfor every discarded candidate, whereasSARA’s abandonment costna=k−⌊τlow​\(k\+1\)⌋n\_\{a\}=k\-\\lfloor\\tau\_\{\\mathrm\{low\}\}\(k\+1\)\\rfloorgrows slower\.SARAis thus increasingly attractive as practitioners scale group size for variance reduction\.

##### Robustness where predictive selection degrades\.

Predictive methods rely on accurate difficulty forecasts; under a fast\-shifting policy or a large, rarely\-revisited prompt pool their forecasts are stale and the assembled batch is polluted \(the regime noted byMaoet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib14)\)\.SARAreads the*current*outcomes, so its effective fraction stays at≈1\\approx 1regardless of policy drift \(Figure[2](https://arxiv.org/html/2607.26253#S2.F2)b\), whereas a predictive selector’s effective fraction falls as drift increases\. This is the robustness gap thatSARA\+\+DPS closes by combining cheap ordering \(prediction\) with an in\-sample guarantee \(verification\)\.

##### Decision quality\.

Treating each group’s verdict as a binary classifier of the oracle effective/saturated label, the early stopping rule attains high agreement well beforen=kn\{=\}k\(Figure[3](https://arxiv.org/html/2607.26253#S3.F3)a\): commit decisions are exact \(Thm\.[1](https://arxiv.org/html/2607.26253#Thmtheorem1)\), and abandon decisions match the oracle on\>91%\>91\\%of abandoned prompts atτlow=0\.45\\tau\_\{\\mathrm\{low\}\}\{=\}0\.45in our model\.

##### Continuous and format rewards\.

AlthoughSARAis derived for binary rewards, it extends directly by binarizing a continuous reward at a threshold \(or by replacing the Beta–Bernoulli predictor with a Beta\-distributed mean\-reward model and defining “effective” as above\-threshold reward spread\)\. The decision rule and all four guarantees carry over with the effectiveness event redefined as “non\-negligible within\-group reward variance\.”

## Appendix GDiscussion, Limitations, and Future Work

##### Relation to length control and test\-time scaling\.

SARAallocates the*number*of rollouts; length\-control methods allocate*tokens within*a rollout\(Aggarwal and Welleck,[2025](https://arxiv.org/html/2607.26253#bib.bib22); Houet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib23); Fatemiet al\.,[2025](https://arxiv.org/html/2607.26253#bib.bib21)\)\. The two are complementary and stack: one can early\-abandon saturated groups \(SARA\)*and*cap thinking length per surviving rollout\. The same Beta predictor could also steer*test\-time*compute \(e\.g\. deciding how many samples a query needs\), echoing the test\-time allocation ofQuet al\.\([2026](https://arxiv.org/html/2607.26253#bib.bib15)\); we leave this to future work\.

##### Multi\-turn and tree rollouts\.

We assumed rollouts within a group are i\.i\.d\. givenγ\\gamma\. In multi\-turn agentic RL, rollouts share prefixes and are correlated\(Zouet al\.,[2026](https://arxiv.org/html/2607.26253#bib.bib16)\); the effectiveness predictor would then condition on prefix history rather than a singleγ\\gamma, and the sequential allocation would act at*prefix*anchors\. CombiningSARA’s in\-sample sequential verdict with prefix\-level tree allocation is a promising extension that retains the “no extra prediction rollouts” property\.

##### Limitations\.

\(i\) The Beta–Bernoulli model assumes conditionally i\.i\.d\. binary outcomes; correlated or continuous rewards require the extensions above\. \(ii\) Round synchronization adds a few inference barriers; with extremely long rollouts and small batches the barrier cost could rival the savings, though in our regime it does not\. \(iii\)SARAstill has one hyper\-parameter,τlow\\tau\_\{\\mathrm\{low\}\}; we showed it has a clear, theory\-backed operating range, but a fully parameter\-free version \(e\.g\. settingτlow\\tau\_\{\\mathrm\{low\}\}from the measured cost/reward ratio via Prop\.[3](https://arxiv.org/html/2607.26253#Thmproposition3)\) is appealing\.

##### Broader impact\.

By assembling effective training batches at substantially lower rollout and token cost,SARAreduces the compute, energy, and monetary footprint of reasoning\-LLM post\-training, and lowers the hardware barrier to RLVR research \(single\-GPU experimentation\)\. It shares the dual\-use considerations of any method that makes capable models cheaper to train, but introduces no new data collection or human\-subject interaction\.