Adaptive Decoding Methods for Token-Efficient Reinforcement Learning

Zhaonan Li; Zelei Cheng; Amritansh Mishra; Chia-Hsuan Lee; Mann Patel; Sambit Sahu; Ben Zhou; William M. Campbell

cs.LGOct 19, 2026

Adaptive Decoding Methods for Token-Efficient Reinforcement Learning

Authors: Zhaonan Li, Zelei Cheng, Amritansh Mishra, Chia-Hsuan Lee, Mann Patel, Sambit Sahu, Ben Zhou, William M. Campbell

Organizations: School of Computing and Augmented Intelligence Arizona State University · AI Foundations Capital One

Abstract

Rollout decoding affects both which trajectories are used for reinforcement learning with verifiable rewards (RLVR) and how many completion tokens are spent collecting them. We study whether candidate-token support should remain fixed or widen during training in the context of rollout sampling efficiency. Our main schedule moves from top-K=10 to K=20 and then to full support as the attempted-token budget increases. In a 4B code-RLVR setting, the schedule has a higher interpolated 150M-token validation value than its matched fixed-K=10 continuation in all three runs, with a mean gain of $1.80{\pm}0.42$ points. The schedule also performs comparably to a separately trained fixed-K=20 baseline, the strongest fixed-support setting in our sweep. Follow-up experiments suggest that late widening to full support is the most promising variant, although the evidence remains noisy, and mixed-reward-group diagnostics do not clearly explain the gain. An exploratory single-run test replay yields identical point estimates for the schedule and fixed $K=10$ . Overall, our results show that rollout support is an important control for sampling efficiency in RLVR and motivate further study of adaptive support schedules.

Figures & tables

Method	Training support	$\widehat{\mathbf{Acc}}\mathbf{@150M}$	$\widehat{\mathbf{AUC}}_{\mathbf{150M}}$	Max bracket (M)
Full support	full	$18.34{\pm}2.51$	$16.26{\pm}1.80$	$105.95$
Fixed support	$10$	$21.49{\pm}2.58$	$18.56{\pm}1.50$	$117.11$
Fixed support	$20$	$23.35{\pm}1.28$	$19.16{\pm}0.89$	$42.92$
Scheduled	$10\!\rightarrow\!20\!\rightarrow\!\mathrm{full}$	$23.29{\pm}2.51$	$19.16{\pm}1.58$	$102.48$
Matched gain	schedule $-$ fixed $K=10$	$\mathbf{+1.80\pm 0.42}$	$\mathbf{+0.60\pm 0.08}$	—

Table 1: Piecewise-linear common-budget validation estimates at

B^{\star}=150

M attempted completion tokens (percentages; three runs per method). Reported

\pm

values are sample standard deviations across runs conditional on the interpolation and do not capture uncertainty from sparse evaluation checkpoints. The bold row reports the matched schedule–fixed-

K=10

difference. “Max bracket” is the widest run level interval between observed validation checkpoints surrounding 150M.

Figure 1: Validation versus attempted completion tokens for the primary support strategies. Lines and bands show mean

\pm 1

sample standard deviation after piecewise-linear interpolation; symbols mark actual evaluations. Vertical lines are nominal transitions; the

y

-axis is truncated. Fixed

K=20

is independently trained.

Matched-parent decomposition
Continuation or gate	$\mathbf{n}$	$\widehat{\mathbf{Acc}}\mathbf{@B^{\star}}$	$\widehat{\textbf{Post-parent AUC}}$	Actor entropy
$K=10$ throughout	3	$22.97{\pm}3.94$	$20.38{\pm}2.68$	$0.348{\pm}0.013$
$10\!\rightarrow\!20$	3	$21.41{\pm}2.78$	$19.70{\pm}1.99$	$0.359{\pm}0.043$
$10\!\rightarrow\!\mathrm{full}$ at 100M	3	$\mathbf{24.23\pm 1.42}$	$\mathbf{20.96\pm 0.97}$	$0.437{\pm}0.074$
$10\!\rightarrow\!20\!\rightarrow\!\mathrm{full}$	3	$23.35{\pm}2.54$	$20.44{\pm}2.03$	$0.447{\pm}0.067$
Exploratory entropy gate

Table 2: Piecewise-linear follow-up estimates at 150M attempted completion tokens. Boldface marks the highest accuracy and AUC within each comparison block. Accuracy and AUC are percentages; actor entropy is the linearly estimated logged token-mean in nats, while

H_{20}

is the gate statistic. The decomposition reports mean

\pm

sample standard deviation. Gate rows are single-run exploratory continuations.

Final-interval support	Mixed groups (%)	Mean length	Mixed groups/M tokens
Fixed $K=10$	$52.33{\pm}5.08$	$8{,}152{\pm}1{,}527$	$8.13{\pm}0.91$
Direct late full	$54.44{\pm}3.64$	$9{,}121{\pm}855$	$7.48{\pm}0.36$
Three-stage schedule	$53.90{\pm}1.98$	$8{,}421{\pm}1{,}463$	$8.13{\pm}1.13$

Table 3: Rollout-group diagnostics over the final 100–150M-token interval (three runs per method). “Mixed” means that a prompt’s eight rollouts contain both correct and incorrect attempts. Wider-support arms have slightly more mixed groups but also longer completions, yielding no clear increase in mixed groups per attempted token.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Run A Acc/AUC	Run B Acc/AUC	Run C Acc/AUC
Full support	20.95 / 18.28	15.95 / 14.83	18.14 / 15.67
Fixed $K=10$	23.17 / 19.79	22.77 / 19.01	18.52 / 16.89
Fixed $K=20$	21.90 / 18.17	23.83 / 19.88	24.33 / 19.42
Scheduled	25.29 / 20.47	24.10 / 19.62	20.47 / 17.41

Appendix

Table 4: Per-run piecewise-linear estimates in percentage points at 150M attempted completion tokens.

Method	Run A (M)	Run B (M)	Run C (M)
Full support	138.1–244.1	116.2–158.4	132.8–225.2
Fixed $K=10$	144.6–261.7	116.2–221.9	135.7–208.8
Fixed $K=20$	108.1–151.0	134.5–153.9	134.8–154.7
Scheduled	51.4–153.5	119.1–221.5	81.9–152.8

Appendix

Table 5: Actual evaluation checkpoints immediately bracketing 150M attempted completion tokens. As a descriptive check, the mean success rates at each run’s nearest raw checkpoint are 17.80, 21.18, 23.62, and 23.20% in row order; those checkpoints occur at different token counts.

Sample-Efficient RL

Sample-efficient reinforcement learning studies how agents learn effective policies from fewer environment interactions, demonstrations, or costly rollouts.

See all 253 papers

Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR
Jul 28, 2026Pixel Nomand, Elena Voss, Marcus Hale +1Reinforcement Learning RL for Language Model Reasoning
University of Wisconsin–Madison · University of Washington
Diversifying RLVR Rollouts via First-Token Exploration
May 27, 2026Soeun Kim, Albert NoRL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards
Department of Artificial Intelligence, Yonsei University
Hindsight-Privileged RLVR: Single-Rollout Token Credit Without Group Sampling
Oct 14, 2026Wei Chen, Yubing Wu, Zhou Xu +9RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards
South China University of Technology · Tsinghua University · The Hong Kong University of Science and Technology +3

Jul 28, 2026J/K move · Enter open · S save

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

Pixel Nomand, Elena Voss, Marcus Hale, Sofia Reyes

University of Wisconsin–Madison · University of Washington

Reinforcement Learning RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards Sample-Efficient RL

Open paper AskPDF arXiv

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

Abstract

Sample-Efficient RL

Explore similar work

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

Diversifying RLVR Rollouts via First-Token Exploration

Hindsight-Privileged RLVR: Single-Rollout Token Credit Without Group Sampling