PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient RLVR Scheduling via Graph-Structured Online Difficulty Estimation

Zhizhao Liu, Zhiliang Tian, Xi Wang, Zhihua Wen, Yihang Xiong, Zhiquan Lai, Dongsheng Li

arXiv:2608.17941v1cs.LGcs.AIcs.CL

TL;DR

RLVR schedulers often allocate exploration uniformly despite differing sample difficulty, while existing online estimates incur probing overhead or suffer from cold starts and stale feedback. This paper introduces a graph-based estimator that shares rollout evidence among related samples and improves downstream scheduler performance across most settings under matched rollout budgets with little overhead.

  • Problem

    RLVR difficulty-aware scheduling lacks reliable, up-to-date sample estimates without costly probing, while historical estimators face cold starts, noise, and stale feedback.

  • Method

    A graph-structured latent-state model propagates rollout feedback among related samples and uses online variational inference to update their difficulty estimates.

  • Results

    Across multiple models, schedulers, and benchmarks, the framework improves downstream reasoning performance in most settings under matched rollout budgets with little online computational overhead.

  • Takeaways & Limitations

    Graph-based online difficulty estimation can support more efficient RLVR exploration through both sample selection and rollout allocation without dedicated probing.

  • Takeaways & Limitations

    Full-history aggregation can introduce temporal lag, primarily affecting absolute calibration rather than relative difficulty ranking.

Abstract

from arXiv · show

Reinforcement learning with verifiable rewards (RLVR) improves the reasoning capabilities of large language models but relies on costly rollout exploration. Assigning the same exploration budget to samples with different difficulty levels is inefficient: easy samples may receive redundant rollouts, whereas difficult but learnable samples may receive too little exploration. Existing adaptive schedulers address this mismatch through curriculum-based sample selection or non-uniform rollout allocation based on estimated sample difficulty. However, obtaining reliable online difficulty estimates remains challenging: dedicated probing adds substantial generation overhead, whereas history-based estimators face a cold start with no initial observations and stale feedback, and typically ignore relations among samples. To address these limitations, we propose a plug-and-play graph-based online difficulty estimator that shares rollout feedback across related samples and continuously updates their difficulty estimates, mitigating cold start and staleness without dedicated probing. Specifically, we first construct a difficulty-aware sample graph based on semantic and reasoning similarities. Based on this graph, we introduce latent difficulty states and use a Potts prior to encourage neighboring samples to share the same state. We then employ a state-level Beta-Binomial model to aggregate the rollout outcomes associated with each state. Finally, we use an online mean-field variational algorithm to continuously update the latent-state assignments and state-level difficulty as new feedback arrives. Our framework can be integrated into sample-selection and rollout-allocation schedulers, enabling difficulty-adaptive exploration without dedicated probing. Experiments across multiple base models, RL schedulers, and benchmarks demonstrate that our framework achieves better performance.

Introduction

The introduction motivates difficulty-aware RLVR scheduling because uniform rollout budgets waste exploration on easy samples and underserve difficult but learnable ones. It proposes a graph-based online estimator that propagates rollout feedback among related samples for low-cost, continuously updated difficulty estimation integrated with existing schedulers.

  • Motivation: Uniform rollout allocation wastes attempts on easy samples while giving difficult but learnable samples too little exploration.This mismatch motivates difficulty-aware scheduling.
  • Prior approaches: Difficulty-aware schedulers either select which samples receive exploration or allocate different rollout counts to selected samples.These are the two established scheduling approaches described in the introduction.
  • Estimation challenge: Reliable online difficulty estimation remains challenging because rollout probing adds computational overhead and statistical uncertainty.The uncertainty arises from limited stochastic rollouts.
  • Method: The proposed framework constructs a graph connecting semantically or reasoning-related samples so their rollout feedback provides mutually informative evidence for difficulty estimation.Related samples may share model capabilities and local statistical correlations.
  • Method: The estimator formulates dynamic difficulty estimation as graph-structured latent-variable inference and continuously estimates success probabilities as the policy evolves.It propagates rollout feedback among related samples without dedicated probing.
  • Integration: The framework integrates with both sample-selection and rollout-allocation methods to improve RLVR training performance.The introduction describes the estimator as low-cost and cold start friendly.

Related Work

Prior work adapts curriculum learning, difficulty estimation, and training-dynamics signals to prioritize informative examples, while recognizing that difficulty depends on interactions between items and policy models. This work addresses sparse, policy-induced nonstationary rollout observations with a relational, evolving latent-state model.

  • Curriculum and prompt selection: Curriculum methods order or reweight examples by difficulty, competence, or learnability to prioritize informative prompts in group-based RLVR.Prompts with nearly deterministic group rewards provide little group-relative learning signal.
  • Difficulty estimation: Difficulty-estimation approaches model item–policy interactions through item response theory or characterize examples using confidence, variability, and learnability across training.Item response theory explicitly represents latent ability and item difficulty and has been adapted to NLP evaluation.
  • Positioning of this work: The proposed setting combines relational difficulty modeling with policy-induced nonstationarity, using time-indexed latent states, state-level Beta–Binomial aggregation, and posterior carryover across training steps.The framework constructs a difficulty-aware graph and performs sequential probabilistic reasoning over relational and evolving latent states.

Method

The method estimates evolving RLVR sample difficulty online by sharing rollout feedback across a difficulty-aware sample graph. It combines graph-structured latent states, state-level Bayesian success modeling, and online mean-field inference to guide adaptive scheduling.

  • Difficulty-aware Sample Graph: A difficulty-aware graph encodes semantic content, reasoning structure, and difficulty-related features, retaining positive-similarity mutual k-nearest-neighbor edges in a sparse undirected graph.Edge weights equal cosine similarities for mutual neighbors, and larger weights indicate greater similarity across these features.
  • Graph-Structured Latent Difficulty Model: The model maps samples to dynamically updated latent difficulty states and uses a Potts graph prior to preserve initial clustering while encouraging neighboring samples to share states.Spectral clustering supplies initial static labels, which later rollout outcomes can refine.
  • State-Level Bayesian Modeling: Samples assigned to the same latent state share a common success probability, allowing rollout feedback to be pooled instead of estimating each sample independently.For state k, successful outcomes follow a Binomial model with state-level probability θ_k,t, while Beta priors inherit posterior parameters across training steps.
  • Online Mean-Field Variational Inference: Online mean-field variational inference updates related samples’ latent-state distributions and state-level Beta factors when selected samples provide rollout feedback.The approximation is needed because the Potts prior makes exact posterior inference intractable.
  • Online Mean-Field Variational Inference: Each coordinate update maximizes the ELBO without decreasing it, so the ELBO sequence converges and provides a stable estimator state at each LLM RL step.The converged estimator may not be globally optimal.

Experiment

Experiments integrate the estimator into three RL scheduling paradigms and evaluate downstream accuracy, difficulty tracking, overhead, and component ablations. Across matched-budget settings, the estimator improves scheduler performance while tracking evolving difficulty with low overhead.

  • Experimental setup: Experiments train on NuminaMath and evaluate on MATH500, AIME 2024, AIME 2025, and OlympiadBench using Average@8 accuracy.Average@8 reports accuracy from eight independent rollouts per prompt, judged by rule-based matching.
  • Experimental setup: The estimator replaces only the difficulty estimators in GVM, PCL, and GRESO while retaining their scheduling strategies under the same total generation budget.GVM allocates rollouts, PCL performs curriculum selection, and GRESO performs selective rollout.
  • Downstream performance: The estimator improves overall performance for all three schedulers, with gains in most model–dataset settings; GVM+Ours improves seven of eight settings and matches the baseline in one.The evaluated base models are Qwen 2.5 1.5B Math and Llama 3 1B-Instruct.
  • Difficulty-estimation accuracy: Full-trajectory correlations increase to 0.836 and 0.776 while total estimation overhead remains approximately 0.12h.The evaluation uses sample-level MAE for calibration and batch-level Pearson correlation r for ranking consistency; the method addresses early observation sparsity and policy-induced difficulty changes.
  • Ablation and cluster analysis: Ablations show that random initialization substantially degrades performance, while spectral clustering provides a better starting point for local EM-style optimization and graph sparsification retains reliable sample relationships.On MATH, the spectral clusters are strongly associated with subject categories (χ2 = 10,995.84, p < 10−300; Cramér’s V = 0.494).

Conclusion

The paper presents graph-based online difficulty estimation for RLVR, using related samples and rollout feedback to improve exploration-budget allocation without dedicated probing.

  • Conclusion: The framework connects samples with similar semantic content and reasoning structures to estimate evolving difficulty from rollout feedback.It avoids dedicated probing while tracking sample difficulty online.
  • Conclusion: The resulting difficulty estimates support both sample-selection and rollout-allocation schedulers.
  • Conclusion: Experiments across multiple base models, schedulers, and benchmarks show that the framework improves downstream performance.

A. ELBO Derivation and Proofs … A.3 Proof of Proposition 2

The appendix derives the expanded ELBO under the mean-field distribution and proves the coordinate updates for latent assignments and Beta factors. The derivation uses graph symmetry, no self-loops, and constants independent of the variational distribution to simplify the objective and updates.

  • A. ELBO Derivation and Proofs: The section defines assignment indicators and collects variationally independent terms into C_t, while assuming a symmetric mutual-neighbor graph without self-loops.These assumptions enable simplifications in the graph contribution and ELBO derivation.
  • A.1 Derivation of the Expanded ELBO: Combining expected log-prior and Beta-factor entropy terms, then dropping C_t, yields exactly the expanded ELBO reported in Sec. 3.5.C_t contains −log Z(W, A), Beta normalizers, and binomial coefficients fixed with respect to q_t.
  • A.1 Derivation of the Expanded ELBO: The expanded ELBO follows by taking expectations of assignment indicators, pairwise indicator products, and Beta log terms under the mean-field distribution.The expectations use q_i,k,t for assignment factors and digamma-function expressions for Beta factors.
  • A.1 Derivation of the Expanded ELBO: Because W_ii = 0, the pairwise mean-field identity suffices for the graph term, while the entropy contribution factorizes.The no-self-loop condition removes diagonal pair terms.
  • A.2 Proof of Proposition 1: For Proposition 1, graph symmetry combines the two appearances of node i in the double sum and cancels its factor 1/2.After fixing the other variational factors, the remaining objective terms depending on q_i,k,t include the entropy term q_i,k,t log q_i,k,t + C.
  • A.2 Proof of Proposition 1: Setting the derivative with respect to q_i,k,t to zero and normalizing over k produces the update stated in Proposition 1.The update follows from the coordinate-wise optimization of the ELBO.
  • A.3 Proof of Proposition 2: For Proposition 2, the mean-field coordinate identity reduces the variational log density for q(θ_t) to the log density of a Beta distribution.The resulting Beta form establishes the claimed variational factor and proves Proposition 2.

A.4 Sequential and Synchronous Implementations

The paper provides a strict sequential Gauss–Seidel implementation as the theoretically grounded reference and a synchronous parallel approximation. Although synchronous updates lack the same ELBO monotonicity guarantee, their estimates stay close while offering substantially better wall-clock performance.

  • Sequential and synchronous implementations: Proposition 1 gives the exact coordinate-optimal update for one assignment factor while holding all other factors fixed.This update underlies both implementation variants.
  • Sequential implementation: The reference implementation performs a strict sequential Gauss–Seidel sweep over samples in the order i = 1, . . . , N.Each assignment factor is updated sequentially at iteration m + 1.
  • Synchronous implementation: The synchronous implementation computes all assignment factors in parallel from the same previous iterate, then updates the Beta factors.This provides a parallel approximation to the sequential procedure.
  • Synchronous implementation: Synchronous sweeps are not exact block-coordinate ELBO maximizations, so Proposition 3 does not guarantee that every sweep is ELBO non-decreasing.The synchronous method is therefore treated as a parallel approximation rather than the theoretically exact procedure.
  • Empirical comparison: Across evaluated training checkpoints, the discrepancy between converged sample-level success-probability estimates remains within 10^-2.The comparison evaluates the estimates produced by the sequential and synchronous implementations at training step t.
  • Empirical comparison: The synchronous implementation is recommended in practice because parallel graph-message aggregation and assignment updates provide substantially better wall-clock performance.The sequential implementation remains the reference algorithm for theoretical analysis.

A.5 Proof of Proposition 3 · A.6 EM Iteration Visualization

The strict sequential implementation is exact coordinate-ascent variational inference, yielding monotone ELBO values and stationary accumulation points under the stated positivity conditions. EM visualization shows rapidly diminishing per-round improvements and typical convergence within 50 iterations.

  • A.5 Proof of Proposition 3: Sequential updates use the most recently updated factors and exactly perform coordinate-ascent variational inference.Each assignment update is followed by Beta-factor updates from Proposition 2.
  • A.5 Proof of Proposition 3: Each coordinate update cannot decrease the ELBO because it uniquely maximizes its corresponding variational subproblem.This applies to both categorical factors and Beta factors.
  • A.5 Proof of Proposition 3: The variational-parameter sequence remains in a compact set and therefore has at least one accumulation point.Categorical factors lie in probability simplexes, while Beta parameters remain in compact positive intervals.
  • A.5 Proof of Proposition 3: The ELBO sequence is monotone and bounded above, so its values converge to a finite limit.Finiteness follows from finite latent assignments, proper Beta priors, and finite rollout counts.
  • A.5 Proof of Proposition 3: Every accumulation point is a fixed point of the exact coordinate updates and consequently a stationary point of the ELBO.Strictly positive categorical assignments and Beta parameters ensure differentiability under simplex constraints, yielding the KKT conditions.
  • A.6 EM Iteration Visualization: The first EM iteration produces the notably largest M-step update.Subsequent per-round ELBO improvements from both the E-step and M-step decay roughly exponentially.
  • A.6 EM Iteration Visualization: Within 50 iterations, EM typically converges to a local stationary point or local maximum.The convergence behavior is illustrated by the ELBO evolution in Figure 2.

B. Details of Datasets and Training … OlympiadBench.

The evaluation uses diverse mathematical reasoning datasets spanning large-scale training data, competition benchmarks, recent AIME contests, and bilingual multimodal olympiad problems. These datasets provide verifiable answers, difficulty or subject diversity, and challenging reasoning settings for evaluation.

  • B. Details of Datasets and Training: NuminaMath contains approximately 860K problem–solution pairs spanning high-school mathematics and international olympiad problems.Each problem includes a chain-of-thought solution and verifiable final answer.
  • B. Details of Datasets and Training: MATH contains 12.5K competition-level problems with step-by-step solutions, final answers, difficulty levels 1–5, and seven subject categories.Its difficulty and category annotations are used only as external references, not training supervision.
  • B. Details of Datasets and Training: MATH-500 is a 500-problem subset of MATH retaining its subject and difficulty diversity for standardized evaluation.It evaluates general mathematical reasoning across competition-level problems using reference solutions and verifiable final answers.
  • AIME 2024.: AIME 2024 combines 15 AIME I problems and 15 AIME II problems, yielding 30 multi-step competition problems with unique integer answers from 000 to 999.The set covers algebra, geometry, number theory, counting, and probability and supports reliable rule-based evaluation.
  • AIME 2025.: AIME 2025 similarly combines AIME I and AIME II into 30 recent problems requiring integer answers between 000 and 999.It evaluates reasoning and generalization on advanced high-school mathematics across multiple domains.
  • OlympiadBench.: OlympiadBench is a bilingual, multimodal benchmark containing 8,476 scientific reasoning problems from international and Chinese olympiads and the Chinese college entrance examination.Its final ACL 2024 version includes 6,142 mathematics problems and 2,334 physics problems, each with an expert-annotated solution.

C. Significance Analysis of Main Results · Question and Comparison Units

The analysis tests whether integrating the proposed method yields directionally consistent improvements across heterogeneous scheduler–base-model–benchmark settings. It evaluates three full integrations using an exact two-sided sign test on Average@8 outcomes, excluding ties from the test sample.

  • Question and Comparison Units: Each scheduler–base-model–benchmark combination contributes one Average@8 point estimate to the analysis.The experiments therefore provide one comparison unit per heterogeneous setting.
  • Question and Comparison Units: The analysis evaluates whether observed improvements occur more frequently than expected under an equal-probability null hypothesis.This directly tests directional consistency rather than relying on aggregate magnitude alone.
  • Question and Comparison Units: A two-sided exact sign test, following Dixon and Mood (1946), is used for the comparisons.The test is applied across the heterogeneous experimental settings reported in the main experiments.
  • Question and Comparison Units: The integrations analyzed are GVM + Ours, PCL + Ours, and GRESO + Ours.These are the three full integrations included in the significance analysis.
  • Question and Comparison Units: For each integration method m, base model b, and benchmark d, the analysis defines a comparison outcome.The indexed units correspond to the integration method, base model, and benchmark dimensions.
  • Question and Comparison Units: A positive delta is recorded as a gain, a negative delta as a loss, and a zero delta as a tie.The resulting counts are denoted W, L, and T for gains, losses, and ties.
  • Question and Comparison Units: Ties are excluded because they provide no directional information, leaving a sign-test sample size of n = W + L.Only gains and losses determine the effective sample size.

Exact Test and Results … Discussion

Exact sign tests show consistent positive improvements across full integrations, while a code-generation experiment indicates that the estimator transfers without domain-specific modifications. The authors qualify this transferability result because existing execution feedback and platform difficulty ratings may already support scheduling in some code benchmarks.

  • Exact Test and Results: For PCL integration, direct counting yields W = 7, L = 1, and n = 8 for the non-tied comparisons.The passage reports that its two-sided exact p-value is obtained from these counts, but the supplied text does not include the value.
  • Exact Test and Results: At α = 0.10, all three full integrations show statistically significant directional improvements.GVM + Ours and GRESO + Ours are significant at α = 0.05, while PCL + Ours is significant at α = 0.10.
  • Exact Test and Results: The pooled exact sign test records W = 21, L = 1, and n = 22, with improvements in 21 of 22 non-tied comparisons.This corresponds to a gain rate of 95.5% across schedulers, base models, and benchmarks.
  • Setting: The code-generation study transfers the estimator to 511 LiveCodeBench release_v2 programming problems using Qwen2.5-Coder-7B-Instruct.Correctness requires generated programs to pass all corresponding test cases.
  • Setting: Using eight rollouts per selected sample, the estimator predicts success probabilities from prior feedback and compares them with subsequent observed outcomes throughout RL training.The estimation process is replayed over the complete training trajectory.
  • Results: On Qwen2.5-Coder-7B-Instruct, the estimator consistently tracks evolving sample success probabilities under execution-based program-correctness feedback.The result suggests that its graph and historical rollout information remain effective beyond exact-match mathematical rewards.
  • Results: The experiment provides preliminary evidence that the estimator transfers to execution-based code generation without code-domain-specific modifications.The authors frame this as transferability evidence rather than a comparison against all adaptive scheduling baselines.
  • Discussion: The authors caution that platform difficulty ratings and execution feedback may already suffice for scheduling in some code-generation benchmarks.Accordingly, the experiment establishes transferability rather than a clear advantage in code generation.

E. Hyper Parameter Analysis … Persistent Sample-Level History.

The analysis finds that estimator quality depends on balanced graph smoothing, latent-state granularity, and task-aware embeddings, while windowed memory tracks non-stationary policies without discarding persistent sample-level evidence. Spectral clusters also show substantial subject association and within-subject difficulty differences.

  • Guideline of K, kknn and β: K controls latent-state granularity, knn controls feedback propagation range, and β balances graph smoothing against adaptation to policy changes.Increasing β to 5 or above makes metrics nearly identical and slightly worse, while smaller K slightly improves batch-level correlation but increases sample-level MAE.
  • Guideline of K, kknn and β; Models Selection: Graph estimation accuracy is largely insensitive to knn unless it is extremely small, because reciprocal-neighbor and positive-similarity filtering already produce a sparse graph.In practice, saturated edge counts make wall-clock time about 1.61× the main method rather than increasing linearly with knn.
  • Models Selection: Recent task-aware embeddings yield broadly similar performance, whereas MRL compression to 1,024 dimensions improves Qwen3-Embedding-4B over its full-dimensional representation.The reported improvements are 0.179 vs. 0.188 MAE on Qwen and 0.121 vs. 0.130 on Llama.
  • Discussion of Difficulty-Aware Instruction: Removing the difficulty-aware instruction substantially degrades estimation, with Qwen MAE rising from 0.183 to 0.309 and correlation falling from 0.836 to 0.583.On Llama, MAE rises from 0.131 to 0.302 and correlation falls from 0.776 to 0.486; older generic encoders similarly perform poorly.
  • Discussion of the Interpolation Weight γ: The interpolation weight γ balances transferable graph evidence with direct sample history; γ = 0.5 is the default, and performance is relatively stable for γ ∈[0.5, 0.8].Values below 0.5 tend to reduce ranking quality, whereas values above 0.8 usually increase sample-level estimation error.
  • Association with Subject Categories: Spectral cluster assignment is strongly associated with subject category, with χ2 = 10,995.84, asymptotic p < 10−300, and Cramér’s V = 0.494.The analysis uses n = 7,500 samples, K+ = 16 clusters, U = 7 subjects, and 90 degrees of freedom.
  • Difficulty Differences Within Subject Categories: All seven subject-specific Kruskal–Wallis null hypotheses remain rejected after Benjamini–Hochberg correction, with epu ≤4.31×10−3.Thus, cluster membership remains associated with annotated difficulty even among problems within the same subject category.
  • Windowed Forgetting Mechanism; Windowed State-Level Statistics.; Windowed Variational Updates.; Persistent Assignment Warm Start.; Persistent Sample-Level History.: Under non-stationary policies, windowed inference restricts shared state-level statistics to recent rollout evidence while persistent assignments provide warm starts and sample histories retain all direct evidence.The model-based term tracks evolving latent-state success probabilities, whereas the sample-level term preserves long-term observations, removing stale transferable evidence without discarding sample experience.

Result and Discussion · H. Related work of Graph-Based Learning and Probabilistic Inference

The results show that windowed forgetting improves sample-level numerical accuracy but weakens correlation with relative difficulty, revealing a trade-off in historical evidence. The related-work context grounds the graph approach in methods that propagate compatible latent structure through similarity graphs and data manifolds.

  • Result and Discussion: The cumulative and windowed estimators are evaluated using sample-level MAE and batch-level Pearson correlation r, where lower MAE and higher r indicate better performance.Table 9 reports performance over all training steps.
  • Result and Discussion: Windowed estimation lowers sample-level MAE on both evaluated models, improving from 0.183 to 0.127 on Qwen-2.5-Math-1.5B and from 0.131 to 0.119 on Llama-3.2-1B-Instruct.The evaluation replays full training logs and compares the windowed variant with the cumulative estimator.
  • Result and Discussion: The windowed variant makes each sample’s predicted success probability numerically closer to its reference rollout outcome.Figure 3 visualizes batch-level reference and predicted accuracy across the full training process.
  • Result and Discussion: Correlation r decreases from 0.836 to 0.712 on Qwen-2.5-Math-1.5B and from 0.776 to 0.747 on Llama-3.2-1B-Instruct after windowing.The decline indicates weaker preservation of relative difficulty structure among samples.
  • Result and Discussion: The windowed estimator trades improved point-wise accuracy for weaker preservation of relative difficulty structure among samples.A likely explanation is that the finite window reduces historical evidence available for state-level estimation.
  • H. Related work of Graph-Based Learning and Probabilistic Inference: Graph-based clustering and semi-supervised learning assume nearby points on a data manifold have compatible latent structure.This assumption motivates using graph geometry to relate samples with similar underlying structure.
  • H. Related work of Graph-Based Learning and Probabilistic Inference: Spectral methods partition similarity graphs through their eigensystems, while propagation and manifold-regularization methods diffuse sparse supervision according to graph geometry.The passage cites spectral clustering, Gaussian-field propagation, local-and-global consistency, and manifold regularization as related approaches.
Loading 2608.17941v1…