Efficient RLVR Scheduling via Graph-Structured Online Difficulty Estimation

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

cs.LGAug 18, 2026

Efficient RLVR Scheduling via Graph-Structured Online Difficulty Estimation

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

Organizations: PDL Lab, College of Computer Science and Technology, National University of Defense Technology No.109 Deya Road, Kaifu District, Changsha Hunan 410073, P.R. China

Abstract

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.

Figures & tables

Figure 1: The overview of our framework. We first construct a difficulty-aware sample graph (a). During RL training, our graph-structured latent model aggregates rollout feedback across related samples (b), while online mean-field variational inference updates their evolving difficulty (c). The resulting estimates guide adaptive sample selection and rollout allocation (d).

Method	Qwen-2.5-Math-1.5B (Average@8)				Llama-3.2-1B-Instruct (Average@8)
Method	MATH500	AIME24	AIME25	Olym	MATH500	AIME24	AIME25	Olym
Base	39.3	3.30	3.33	25.2	17.5	0.00	0.00	3.02
GVM	71.9	11.3	11.3	35.8	23.9	0.42	0.00	4.59
GVM+Ours	74.7	16.7	13.3	38.3	25.7	3.30	0.00	4.89
PCL	59.7	7.92	4.58	26.1	26.7	0.42	0.00	5.04
PCL+Ours	61.6	11.3	6.67	27.1	27.4	0.00	0.42	5.81

Table 1: The Average@8 accuracy of different RL scheduling methods on four mathematical reasoning benchmarks using two base models. The first column lists the original schedulers and their variants integrated with our difficulty estimator. Underlined results indicate improvements over the corresponding original scheduler (

p<5\times 10^{-5}

, see Appendix C).

Base Model	Methods	Early Steps		Middle Steps		Last Steps		Full Steps		Time (A100*h)
Base Model	Methods	MAE ( $\downarrow$ )	r ( $\uparrow$ )	MAE ( $\downarrow$ )	r ( $\uparrow$ )	MAE ( $\downarrow$ )	r ( $\uparrow$ )	MAE ( $\downarrow$ )	r ( $\uparrow$ )	Time (A100*h)
Qwen-2.5 Math-1.5B	Sample before RL	0.116	0.544	0.139	0.856	0.151	0.865	0.135	0.522	$\sim$ 29.6
	Sample before Step	0.063	0.959	0.054	0.971	0.049	0.974	0.055	0.969	$\sim$ 45.3
	VIP	0.373	-	0.094	0.794	0.084	0.885	0.184	0.423	$\sim$ 0.05
	PCL	0.404	0.138	0.336	0.407	0.328	0.474	0.356	0.281	$\sim$ 7.36
	MoPPS	0.373	-	0.149	0.910	0.118	0.929	0.214	0.754	-

Table 2: Difficulty-estimation accuracy and overhead at different stages of GRPO training (batch size =256). MAE is computed at the sample level and Pearson correlation

r

at the batch level. Bold denotes the best overall result, underlining denotes the best result among low-cost methods, and Time (including embedding, clustering and inference) denotes additional estimation overhead for over 3 epochs on 150K training samples.

Base Model	Methods	Full Steps
Base Model	Methods	MAE (↓)	r (↑)
Qwen-2.5 Math-1.5B	Ours	0.183	0.836
	w/o Spectral Init.	0.218	0.710
	w/o Prior Smoothing	0.197	0.783
	w/o Graph Sparsification	0.187	0.835
Llama-3.2 1B-Instruct	Ours	0.131	0.776

Table 3: Full-trajectory ablation results for difficulty estimation on two base models. Lower MAE and higher Pearson correlation

r

indicate better estimation.

Full integration	$W$	$L$	$T$	$p_{\mathrm{sign}}$
GVM + Ours	7	0	1	0.0156
PCL + Ours	7	1	0	0.0703
GRESO + Ours	7	0	1	0.0156
Pooled	21	1	2	$1.10\times 10^{-5}$

Table 4: Directional sign-test results for the full integrations. Ties are excluded from the exact test.

Base Model	Methods	Full Steps
Base Model	Methods	MAE (↓)	r (↑)
Qwen2.5-Coder-7B Instruct	VIP	0.197	0.504
	PCL	0.402	0.307
	MoPPS	0.224	0.773
	Ours	0.176	0.845

Table 5: Difficulty-estimation performance on code generation using Qwen2.5-Coder-7B-Instruct. MAE is sample-level, and

r

is the batch-level Pearson correlation.

$\beta$	K	Early Steps		Full Steps
$\beta$	K	r (↑)	MAE (↓)	r (↑)	MAE (↓)
2	320	0.482	0.290	0.836	0.183
2	160	0.480	0.306	0.838	0.191
2	80	0.494	0.313	0.843	0.194
2	40	0.507	0.327	0.848	0.196
1	320	0.488	0.302	0.849	0.189

Table 6: Sensitivity analysis of

\beta

and

K

on Qwen-2.5-Math-1.5B. MAE is sample-level, and

r

is batch-level Pearson correlation.

Base Model	Methods	Full Steps
Base Model	Methods	MAE (↓)	r (↑)
Qwen-2.5 Math-1.5B	Qwen3-Embedding-0.6B	0.183	0.836
	-Difficulty-Aware Instruction	0.309	0.583
	Qwen3-Embedding-4B	0.188	0.827
	Qwen3-Embedding-4B MRL(1024 dimensions)	0.179	0.844
	BGE-M3	0.188	0.823

Table 7: Full-trajectory difficulty-estimation performance of different embedding configurations. The row “-Difficulty-Aware Instruction” removes the instruction from the default encoder. MAE: sample-level mean absolute error (lower is better);

r

: batch-level Pearson correlation (higher is better).

Subject	Raw $p$	BH-adjusted $p$
Algebra	$\approx 0$	$\approx 0$
Prealgebra	$\approx 0$	$\approx 0$
Precalculus	$\approx 0$	$1.0\times 10^{-6}$
Intermediate algebra	$2.0\times 10^{-6}$	$3.0\times 10^{-6}$
Counting/probability	$8.0\times 10^{-6}$	$1.1\times 10^{-5}$
Number theory	$3.19\times 10^{-4}$	$3.72\times 10^{-4}$

Table 8: Within-subject Kruskal–Wallis tests of difficulty differences across spectral clusters. Values displayed as zero are below the reporting precision; BH correction uses the unrounded raw values.

Base Model	Methods	Full Steps
Base Model	Methods	MAE (↓)	r (↑)
Qwen-2.5 Math-1.5B	Ours	0.183	0.836
Qwen-2.5 Math-1.5B	Windows	0.127	0.712
Llama-3.2 1B-Instruct	Ours	0.131	0.776
Llama-3.2 1B-Instruct	Windows	0.119	0.747

Table 9: Sample-level difficulty estimation performance of the cumulative estimator (Ours) and the windowed variant (Windows) over all training steps. MAE measures the absolute prediction error, while batch-level

r

denotes the Pearson correlation between the predicted and reference success probabilities. Lower MAE and higher

r

indicate better performance.

Figure 3: Batch-level reference accuracy and predicted accuracy of the cumulative and windowed estimators on Qwen-2.5-Math-1.5B and Llama-3.2-1B-Instruct.

RL for Language Models

Reinforcement learning for language models uses feedback-driven policy updates to improve reasoning, alignment, and interactive behavior.

See all 435 papers

Mechanistically Interpreting the Role of Sample Difficulty in RLVR for LLMs
May 27, 2026Yue Cheng, Jiajun Zhang, Xiaohui Gao +3Reinforcement Learning RL for Language Model Reasoning
Beijing Jiaotong University · AntGroup · Northwestern Polytechnical University +2
Unlearnable, or Unmeasured? On the Reliability of Difficulty Labels in RLVR
Sep 30, 2026Chandak Chakma, Syed Nazmus Sakib, Nafiul Haque +1Reinforcement Learning RL for Language Model Reasoning
Department of Robotics and Mechatronics Engineering, University of Dhaka
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

May 27, 2026J/K move · Enter open · S save

Mechanistically Interpreting the Role of Sample Difficulty in RLVR for LLMs

Yue Cheng, Jiajun Zhang, Xiaohui Gao, Weiwei Xing+2

Beijing Jiaotong University · AntGroup · Northwestern Polytechnical University+2

Reinforcement Learning RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards

Open paper AskPDF arXiv

Reinforcement Learning with Verifiable Reward (RLVR) is empirically shown to notably enhance the reasoning performance of large language models (LLMs), particularly in mathematics and programming. However, the mechanistic role of Sample Difficulty in RLVR remains poorly understood. In this paper, we investigate RLVR through the lens of difficulty-wise and one-sample analysis. We find that sample difficulty has a non-monotonic effect on RLVR: easy and medium-difficulty problems yield the strongest and most stable reasoning improvements, whereas overly hard problems often provide weak learning signals, induce degenerate behaviors such as answer repetition or skipping necessary computation, and can ultimately degrade the model's pre-existing capabilities. Beyond the obverse of response, we further analyze the model's internal feature dynamics using Temporal Sparse Autoencoders (T-SAE). Easy problems mainly reinforce direct-answer and basic-computation features while suppressing deliberative-reasoning features; hard problems activate reasoning-related features but become useful only when successful trajectories are sampled; medium-difficulty problems provide a more balanced signal, strengthening both computation and multi-step reasoning features. Motivated by these findings, we propose difficulty-adaptive strategies for hard-sample utilization, using backward-reasoning reformulation and T-SAE-guided training signals to improve reward density and credit assignment during RLVR. Overall, our results identify sample difficulty as a key factor governing both the optimization dynamics and representation evolution of RLVR.

Abstract

RL for Language Models

Explore similar work

Mechanistically Interpreting the Role of Sample Difficulty in RLVR for LLMs

Unlearnable, or Unmeasured? On the Reliability of Difficulty Labels in RLVR

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