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
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)
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×10−5 , see Appendix C).
Base Model
Methods
Early Steps
Middle Steps
Last Steps
Full Steps
Time (A100*h)
MAE ( ↓ )
r ( ↑ )
MAE ( ↓ )
r ( ↑ )
MAE ( ↓ )
r ( ↑ )
MAE ( ↓ )
r ( ↑ )
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
∼ 29.6
Sample before Step
0.063
0.959
0.054
0.971
0.049
0.974
0.055
0.969
∼ 45.3
VIP
0.373
-
0.094
0.794
0.084
0.885
0.184
0.423
∼ 0.05
PCL
0.404
0.138
0.336
0.407
0.328
0.474
0.356
0.281
∼ 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
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.
Figure 2: EM iterations
Full integration
W
L
T
psign
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×10−5
Table 4: Directional sign-test results for the full integrations. Ties are excluded from the exact test.
Base Model
Methods
Full Steps
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.
β
K
Early Steps
Full Steps
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 β 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
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
≈0
≈0
Prealgebra
≈0
≈0
Precalculus
≈0
1.0×10−6
Intermediate algebra
2.0×10−6
3.0×10−6
Counting/probability
8.0×10−6
1.1×10−5
Number theory
3.19×10−4
3.72×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
MAE (↓)
r (↑)
Qwen-2.5 Math-1.5B
Ours
0.183
0.836
Windows
0.127
0.712
Llama-3.2 1B-Instruct
Ours
0.131
0.776
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.
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.
Yue Cheng, Jiajun Zhang, Xiaohui Gao +3
Beijing Jiaotong University · AntGroup · Northwestern Polytechnical University +2
Reinforcement learning with verifiable rewards (RLVR) has become an important approach for improving reasoning during post-training. Recent work suggests that some difficult prompts remain resistant to learning even when they occasionally produce correct solutions. We revisit this unlearnability phenomenon and find that the affected prompts do improve, at roughly one third of the learnable rate, while the difficulty-defined set used to study them is much less reproducible than expected. These difficulty labels are estimated from a limited number of sampled responses. Combining them across seeds can further change which prompts are selected instead of simply reducing measurement noise. We develop a sampling-based framework for quantifying this instability and determining how much evaluation is required for difficulty assignments to reproduce reliably. We also revisit the gradient-similarity evidence proposed to explain unlearnability and show that part of the observed separation arises because difficult prompts provide fewer correct rollouts from which their gradients can be estimated. Matching this sample count weakens the gradient difference but does not remove it. Overall, the slow-learning phenomenon survives our reanalysis, while both the prompts used to define it and the evidence used to explain it require more careful measurement.
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).
Pixel Nomand, Elena Voss, Marcus Hale +1
University of Wisconsin–Madison · University of Washington