PaperlayerView exact revision on arXiv

Source-linked AI summary

Train at Moving Edge: Online-Verified Prompt Selection for Efficient RL Training of Large Reasoning Model

Jiahao Wu, Ning Lu, Shengcai Liu, Kun Wang, Yanting Yang, Baijiong Lin, Chen Jason Zhang, Li Qing, Ke Tang

arXiv:2603.25184v3cs.LGcs.AI

TL;DR

RL training spends costly rollouts on prompts that provide little learning signal, while useful prompts shift as the policy changes. HIVE combines historical candidate narrowing with current-policy prompt-entropy verification before rollout. Across math benchmarks and model scales, it reduces cost while preserving or improving accuracy, with up to 2.3× faster total training time reported.

  • Problem

    GRPO-style RL incurs substantial rollout overhead, including rollouts on prompts that provide negligible gradients, motivating selection of useful prompts before rollout.

    Source: §1 · p. 1

  • Method

    HIVE first narrows prompts using historical reward trajectories and response-side entropy, then uses current-policy prompt entropy to filter stale candidates before rollout.

    Source: §1 · p. 2

  • Results

    Across math benchmarks and model scales, HIVE reduces rollout and training costs while preserving or improving final accuracy, reaching up to 2.3× faster total training time.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The results support moving-edge tracking as a way to reduce unnecessary RL post-training rollouts and associated training cost.

    Source: §7 · p. 9, §6 · p. 9

    The rank-consistency analysis is a conservative sufficient condition rather than a tight characterization, and its worst-case bounds may be loose for modern LRMs.

    Source: §7 · p. 9

Abstract

from arXiv · show

Reinforcement learning (RL) has become essential for post-training large language models (LLMs) in reasoning tasks. While scaling rollouts can stabilize training and enhance performance, the computational overhead is a critical issue. In algorithms like GRPO, multiple rollouts per prompt incur prohibitive costs, as a large portion of prompts provide negligible gradients and are thus of low utility. To address this problem, we investigate how to select high-utility prompts before the rollout phase. Our experimental analysis reveals that sample utility is non-uniform and evolving: the strongest learning signals concentrate at the ``learning edge", the intersection of intermediate difficulty and high uncertainty, which shifts as training proceeds. Motivated by this, we propose HIVE (History-Informed and online-VErified prompt selection), a dual-stage framework for data-efficient RL. HIVE utilizes historical reward trajectories for coarse selection and employs prompt entropy as a real-time proxy to prune instances with stale utility. By evaluating HIVE across multiple math reasoning benchmarks and models, we show that HIVE yields significant rollout efficiency without compromising performance.

1 Introduction

RL rollout costs are high, and many prompts yield negligible gradients; the useful learning signal instead concentrates at a dynamic edge. HIVE combines historical narrowing with online verification, and the paper reports lower rollout and training costs while maintaining reasoning performance.

1 Introduction

  • GRPO rollout scaling can waste computation on prompts that are too trivial or too intractable to provide informative gradients.The paper asks how to identify useful-gradient prompts before rollout.Source: §1 · p. 1
  • Existing selectors trade off adaptability and cost: static filters cannot adapt, rollout-based online filters incur rollout cost, and history-based estimates become stale.Auxiliary-model selectors add compute and memory during selection.Source: §1 · pp. 1–2
  • The strongest learning signals occur at a dynamic learning edge: intermediate difficulty combined with high response-side entropy.Historical metadata quickly loses real-time utility as prompts move among utility classes during training.Source: §1 · p. 2
  • HIVE uses historical reward trajectories and response-side entropy to narrow candidates, then current-policy prompt entropy to filter stale prompts before rollout.The two stages are designed to track the changing learning edge while limiting selection overhead.Source: §1 · p. 2, Figure 1 · p. 2
  • Across multiple reasoning benchmarks and models, HIVE reduces rollout and training costs while maintaining reasoning performance.The paper reports up to 2.3× faster total training time and up to 9.2 million fewer rollouts.Source: §1 · p. 2

2 Empirical Observations: The Moving Learning Edge

The section argues that useful RLVR prompts lie at a moving learning edge: intermediate difficulty and high uncertainty. Historical prompt statistics become stale as the policy changes, so candidates need current-policy revalidation.

2 Empirical Observations: The Moving Learning Edge

  • When all sampled responses receive the same reward, reward variance is zero and the prompt provides no informative policy-gradient signal.Such prompts may be too easy for the current policy or too hard to discriminate among sampled responses.Source: §2 · p. 3
  • Gradient utility is strongest where intermediate difficulty and high response-side entropy intersect, making zero-variance filtering alone too coarse.At fixed difficulty, gradient norm rises with entropy; at fixed entropy, utility follows an inverted-U pattern over difficulty.Source: §2 · p. 3
  • Historical metadata yields lower current gradient norms than online selection, and prompts shift among High, Low, and Zero utility classes across training steps.The figure caption reports substantial class shifts across steps 500 and 1000.Source: §2 · pp. 3–4, Figure 2 · p. 3

3 Methodology

HIVE is a two-stage pre-rollout selector: historical reward and entropy traces cheaply narrow prompts, then current-policy prompt entropy verifies candidates before standard rollouts. This design balances efficiency with online adaptation as the learning edge shifts.

3.1 Design Objective

  • HIVE’s design objective is to adapt selection as the policy and learning frontier evolve while avoiding the rollout cost that could erase its computational benefits.Stage 1 cheaply narrows the prompt pool, and Stage 2 verifies candidates under current model parameters before standard rollouts and GRPO updates.Source: §3.1 · p. 4

3.2 Stage 1: History-Informed Coarse Narrowing

  • Stage 1 combines reward-based difficulty-saturation scores with historical response-entropy scores to retain prompts near the learning edge.Repeated zero-variance outcomes exponentially decay retention but do not eliminate exploration, allowing currently intractable prompts to become eligible as the policy improves; entropy normalization makes scores comparable across training stages.Source: §3.2 · pp. 4–5

3.3 Stage 2: Online-Verified Selection

  • Stage 2 computes prompt-side entropy under the current policy and applies a median threshold to select the rollout batch, rejecting stale low-uncertainty candidates.The median gate adapts to the candidate distribution and keeps throughput stable; verification adds 0.82 seconds per iteration, less than 0.4% of step time.Source: §3.3 · pp. 5–6
  • Prompt-side entropy is used as a low-cost verifier, not a complete utility model, with its ranking rationale conditional on stated assumptions and empirical support.The paper cites prompt–response entropy correlations and reports that removing Stage 2 weakens the accuracy–rollout tradeoff.Source: §3.3 · p. 5

4 Experiments

Experiments test whether HIVE preserves reasoning performance while reducing rollout and training cost across math and tool-calling tasks. Results report fewer rollouts at comparable or higher accuracy, alongside efficiency gains linked to online verification and the two-stage design.

4.1 Experimental Settings

  • The evaluation spans math models and corpora, six mathematical reasoning benchmarks, and a separate tool-calling task, with methods compared against online, offline, history-based, and auxiliary selectors.Main math experiments use 1,000 training steps; the rollout-budget comparison uses a two-run protocol for Pre-filter and PCL.Source: §4.1 · pp. 6–7

4.2 Main Results: Accuracy Under Lower Rollout Cost

  • On Qwen2.5-Math-7B, HIVE reduces rollouts by 70% versus DS (13.1M to 3.9M) and achieves 59.7% average accuracy, versus 57.8% for DS and 58.6% for GRESO.The comparison is on DAPO+MATH.Source: §4.2 · p. 7
  • On Qwen2.5-Math-7B trained on Open-R1, HIVE uses 4.7× fewer rollouts than DS; on Qwen2.5-14B over 800 steps, it uses 1.56M versus 1.74M for GRESO and 3.45M for DS.The Open-R1 comparison reports comparable or better average accuracy, and Figure 4 shows similar convergence trajectories at larger scales.Source: §4.2 · p. 7, Table 2 · p. 7, Figure 4 · p. 7
  • On Qwen2.5-Math-7B, HIVE cuts total training time to 85.8 hours from 198.4 hours for DS and 112.3 hours for GRESO, and rollout time to 40.2 hours from 153.7 and 66.3 hours.Across comparisons, HIVE reduces rollout time by up to 3.8× and total training time by up to 2.3× over DS.Source: §4.2 · p. 7
  • On BFCL-V2, HIVE scores 79.26 versus DS at 79.08 while using 1.1M rather than 5.3M rollouts, a 4.8× reduction.Under the same low-rollout regime, HIVE also outperforms Pre-filter, GRESO, and PCL.Source: Table 3 · p. 7, §4.2 · p. 7

4.3 Mechanism Analysis: Efficiency and Moving-Edge Adaptation

  • Stage 2 prompt-side verification adds 0.82 seconds per step, under 0.4% of iteration time, while rollout generation takes 147.46 seconds; HIVE also accumulates effective rollouts fastest per hour and maintains lower generation latency.Figure 5 reports that HIVE uses fewer rollout groups per step, concentrating compute on verified candidates.Source: Figure 5 · p. 8, §4.3 · p. 8
  • HIVE maintains lower easy and hard zero-variance prompt ratios than the compared selectors, tracking changing prompt utility instead of relying on stale historical records.The zero-variance ratio measures how often selected prompts produce no informative gradient.Source: §4.3 · p. 8, Figure 6 · p. 8

4.4 Component Study: Why Both Stages Matter

  • The full two-stage HIVE pipeline gives the best accuracy–rollout tradeoff: removing Stage 2 weakens online precision, while removing Stage 1 burdens verification with low-value candidates.The Stage 2 median entropy threshold decreases as the model becomes more confident.Source: §4.4 · p. 8, Figure 6 · p. 8

5 Related Work

Prior work improves RLVR optimization and prompt selection, but the cited approaches do not fully address efficient pre-rollout allocation under a changing policy. HIVE combines historical narrowing with prompt-side online verification to address that gap.

5 Related Work

  • RLVR and RL optimization work spans value-enhanced PPO, group-based methods, replay, and objective changes, but does not directly decide which prompts merit response generation at the current step.The section frames pre-rollout allocation as distinct from improving optimization stability or sample reuse.Source: §5 · p. 9
  • Offline filters are efficient but policy-agnostic, rollout-based online filters observe current rewards but incur rollout costs, and history- or predictor-based selectors face stale estimates or extra compute and memory.The approaches discussed include Dynamic Sampling, GRESO, Bayesian task selection, DOTS, and PCL.Source: §5 · p. 9
  • HIVE decomposes selection into history-informed coarse narrowing followed by prompt-side online verification, retaining historical filtering efficiency while correcting stale metadata before rollout.Detailed related work is provided in Appendix D.Source: §5 · p. 9

6 Conclusion

The paper frames RLVR prompt selection as tracking a moving edge: prompts must remain informative for the current policy. HIVE combines historical narrowing with prompt-side online verification, and across math benchmarks and model scales reduces cost while preserving or improving final accuracy.

6 Conclusion

  • Across math reasoning benchmarks and model scales, HIVE reduces rollout and training cost while preserving or improving final accuracy.Its dual-stage mechanism narrows candidates using history, then verifies them under the current model.Source: §6 · p. 9

7 Limitations and Broader Impacts

The rank-consistency analysis is a conservative sufficient condition for prompt-side entropy as an online verifier, and its worst-case bounds may be loose for modern LRMs. The appendix formalizes the proxy intuition using assumptions linking observable entropy to internal representations and from prompts to responses.

7 Limitations and Broader Impacts

  • The rank-consistency analysis uses worst-case concentration and bounded-approximation arguments that may yield loose margins for modern LRMs; tighter variance-dependent guarantees remain future work.HIVE requires a useful low-cost entropy signal, not exact prompt-level ranking.Source: §7 · p. 9
  • HIVE is described as reducing unnecessary rollouts, training cost, energy use, and carbon footprint, with potential to make RLVR post-training more accessible to resource-constrained research groups.The authors foresee no specific negative societal impacts beyond general risks associated with stronger LLM capabilities.Source: §7 · p. 9

A Rank-Consistency Analysis for Theorem 3.1

  • The appendix presents the rank-consistency analysis as a formalization under simplifying assumptions, while identifying empirical correlations and ablations as the main support for HIVE.It also lists experimental settings, additional experiments, the algorithm, and other appendix material.Source: A Rank-Consistency Analysis for… · p. 15, Appendix · p. 15

A.1 Preliminaries and Notations

  • Prompt-side entropy V(x) is defined from token-level vocabulary distributions at prompt positions, while response-side entropy U*(x) is an expected entropy under the sampling policy.The response-side estimate is based on generated rollouts.Source: §A.1 · p. 15

A.2.1 From Token to Representation.

  • The theoretical bridge assumes observable token entropy approximates internal representation entropy, drawing on a cited result about deep-layer hidden-state entropy.The cited justification states that deep-layer hidden-state entropy approximately upper-bounds predictive posterior entropy.Source: §A.2.1 · pp. 15–16

A.2.2 Entropy Propagation.

  • The analysis also assumes prompt representation entropy propagates linearly into response generation; across 2,048 prompts, the reported correlation is Pearson r=0.9600 and the binned trend has R2=0.9216.These findings support the assumed linear structure for the regimes studied.Source: §A.2.2 · p. 16

A.3 Concentration Bound

The empirical entropy estimate concentrates around its true expectation, with the stated confidence bound justified by bounded, independent rollouts.

A.3 Concentration Bound

  • Across 2,048 samples, prompt-side and response-side entropy correlate strongly (Pearson r=0.9600; R2 = 0.9216).Binned statistics distinguish the average trend from sample-level generation noise.Source: Figure 7 · p. 16
  • The empirical entropy estimate concentrates around its true expectation with a high-probability bound.The result is stated for any fixed prompt and tolerance; the supplied passages do not include the bound’s full formula.Source: §A.3 · p. 16
  • Hoeffding’s inequality applies because rollout entropies are bounded and the rollouts are i.i.d. under the sampling policy.Each sequence-level entropy lies in [0, log |V|].Source: §A.3 · p. 16

A.4 Main Result: Rank Consistency

Under the stated assumptions, the difference in estimated response entropy is close to a scaled prompt-entropy difference; sufficiently large prompt-entropy margins preserve rankings.

A.4 Main Result: Rank Consistency

  • With probability at least 1 − 2α, |∆U − a∆V| is bounded by 2ϵ + 2(a + 1)δ + 2η(α).Here ∆V is the observable prompt-entropy difference and ∆U is the estimated response-entropy difference.Source: §A.4 · pp. 16–17
  • If |a∆V| exceeds 2ϵ + 2(a + 1)δ + 2η(α), the prompt-entropy margin preserves the pairwise ranking.The theorem gives this guarantee with probability at least 1 − 2α.Source: §A.4 · pp. 16–17
  • The bound combines sampling noise, entropy-propagation residual, and representation-approximation error.The propagation bias cancels when taking the difference between prompts; approximation contributes 2(a + 1)δ.Source: §A.4 · p. 17

B Detailed Experimental Setting for Main Study

The section lays out the main study’s experimental protocol, covering shared training and evaluation, budget-matched baselines, and HIVE-specific selector settings.

B Detailed Experimental Setting for Main Study

B.1 Shared Training and Evaluation Protocol

The appendix specifies the shared model, training, and evaluation setup, then details baseline budget matching and HIVE’s selector configuration and batch-sizing procedure.

B.1 Shared Training and Evaluation Protocol

  • The study evaluates five main models on DAPO+MATH and a 30,000-example Open-R1 math subset, with Qwen2.5-14B/32B added for scaling.The models are Qwen2.5-Math-1.5B, DeepSeek-R1-Distill-Qwen-1.5B, Qwen3-4B-Base, Qwen2.5-Math-7B, and Llama-3.2-3B-Instruct.Source: §B.1 · p. 17
  • Training runs for 1,000 steps with G = 8 rollouts per prompt, learning rate 10−6, and no KL-divergence term.The main models use 8×A100 GPUs and AdamW; evaluation uses six math benchmarks and selects the checkpoint with the best average score.Source: §B.1 · pp. 17–18

B.2 Baselines and Budget Matching

  • Dynamic Sampling is the full-cost online baseline; Pre-filter, GRESO, and PCL provide fixed offline, history-based, and curriculum comparisons.Pre-filter and PCL use a matched-rollout two-run protocol, with the higher average benchmark score reported.Source: §B.2 · p. 18

B.3 HIVE-Specific Hyperparameters and Initialization

  • Table 4 lists HIVE’s selector hyperparameters, deployed values, and roles, generally shared across main and scaling runs.Defaults that are never overridden are marked with †.Source: §B.3 · p. 18, Table 4 · p. 19
  • Unseen prompts receive one initial rollout visit before history-based filtering applies.The profiler starts empty, and Stage 1 accepts prompts without history with probability 1.Source: §B.3 · p. 18
  • HIVE accumulates candidates through Stage 1 filtering and an entropy-band gate, then rolls out survivors and discards zero-variance groups.If the surviving groups are insufficient, candidate accumulation repeats until an exact Bt-prompt update batch can be sliced for GRPO.Source: §B.3 · pp. 18–19
  • The exact-Bt batch guarantee can require inspecting more raw prompts when many rollout groups have zero reward variance.For Qwen2.5-Math-7B, the described configuration inspects about 900 raw prompts for the 256 prompts entering the GRPO update.Source: §B.3 · pp. 19–20

C Experimental Settings for Preliminary Analysis

The preliminary study defines prompt utility and examines how it is measured under a fixed GRPO setup, while the related-work review distinguishes prompt-selection approaches by their efficiency and adaptivity tradeoffs.

C Experimental Settings for Preliminary Analysis

  • The preliminary analysis uses Qwen2.5-Math-1.5B on DAPO+MATH, trained with GRPO group size 8 and temperature 1.0 on eight A100 GPUs.The study is introduced as a focused examination of utility and metadata staleness.Source: C Experimental Settings for… · p. 20
  • Utility is the length-normalized last-layer policy-gradient L2 norm; effective prompts have non-zero reward variance, difficulty uses rollout accuracy, and response entropy averages token entropy over rollouts.Low accuracy denotes hard prompts and high accuracy denotes easy prompts.Source: C Experimental Settings for… · p. 20
  • The figures compare online versus history-only retention, entropy prioritization at matched informative-rollout budgets, utility across difficulty-entropy bins, and utility-class transitions over training.The class-transition analysis samples 515 prompts with non-zero reward variance observed at step 500 or 1000.Source: Figure 2a, Figure 2b, Figure 2c

D Detailed Related Work

  • RL optimization methods improve how selected rollouts update the policy, whereas HIVE focuses on which prompts receive rollouts before the update.The related-work review describes these contributions as complementary.Source: D Detailed Related Work · p. 21
  • Prior selection methods trade off adaptability and cost: static filters cannot track changing competence, rollout-based filters require response generation, and estimators can rely on stale metadata.Auxiliary scorers add computation or memory, while periodic curriculum refreshes lack cheap per-step verification.Source: D Detailed Related Work · p. 21
  • HIVE combines low-overhead historical filtering with prompt-side entropy verification to correct stale metadata without generating responses.The review frames this as addressing the joint online and efficiency requirements that prior selection categories do not satisfy.Source: D Detailed Related Work · p. 21

E Additional Experiments

The additional experiments examine prompt–response entropy under alternative definitions and relate selection behavior to prompt difficulty and uncertainty through a MATH case study. The section also reports checklist disclosures on repeated-run error bars, societal impacts, experimental resources, existing assets, and human subjects.

E.2 Case Study

  • In the MATH case study, frequently selected prompts are moderately difficult, while frequently skipped easy or hard prompts tend to have high or low success, respectively.Prompts selected by Stage 1 but skipped by Stage 2 are mostly easy, suggesting historical information alone is unreliable for filtering.Source: §E.2 · p. 21

E.1 Correlation Between Prompt Entropy and Response Entropy

  • Prompt–response entropy remains strongly linear when response entropy is computed over the top 10%, 20%, 30%, or 40% of response tokens, supporting Assumption A.2’s bounded-noise linear approximation.The study uses binned means over 2,048 prompts, grouped by prompt entropy.Source: §E.1 · p. 21, Figure 8 · p. 22

F Algorithm

  • HIVE combines historical zero-variance counts and response entropy to select a candidate pool, then retains candidates at or above median prompt entropy before GRPO rollouts.After training, rewards and response entropies update the historical trace for future iterations.Source: F Algorithm · pp. 24–25, §E.2 · p. 24

G Asset Licenses

  • The paper reports that it uses publicly available models, datasets, and software frameworks under their original licenses and terms.Table 5 summarizes asset sources and licenses.Source: G Asset Licenses · p. 25, Table 5 · p. 25

NeurIPS Paper Checklist

  • The checklist identifies the prompt-entropy proxy as a limitation and notes that the submission lacks an anonymized code release or runnable reproduction scripts.It also states that Section 4 and Appendix B describe the settings needed to reproduce the main experiments.Source: NeurIPS Paper Checklist · pp. 26–28
  • Main training results lack repeated-run error bars because large-scale RL training is computationally costly, although entropy-propagation validation includes binned mean/std statistics.The paper reports benchmark accuracies and efficiency measurements but does not provide repeated-run error bars for the main training results.Source: NeurIPS Paper Checklist · p. 28
  • Section 4 and Appendix B specify A100 GPUs, and Table 1b reports wall-clock training-time breakdowns.Source: NeurIPS Paper Checklist · p. 29
  • The work studies RL post-training on public math-reasoning resources without human subjects, private data, or deployment decisions, and describes its LLM use in Sections 3 and 4.2.Source: NeurIPS Paper Checklist · pp. 29, 31, 32
  • The paper discusses compute-efficiency and accessibility benefits alongside risks from lowering barriers to training stronger reasoning models.Source: NeurIPS Paper Checklist · p. 30
  • The paper credits its models, datasets, and software frameworks, lists asset licenses and terms in Table 5, and releases no new dataset, benchmark, or model asset.Source: NeurIPS Paper Checklist · pp. 30–31
Loading 2603.25184v3…