Efficient RLVR Scheduling via Graph-Structured Online Difficulty Estimation

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.17941v1 [cs.LG] 18 Aug 2026

1

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 tianzhiliang@nudt.edu.cn dsli@nudt.edu.cn

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 under matched rollout budgets.

Introduction Reinforcement learning with verifiable rewards (RLVR) improves the reasoning capabilities of large language models through automatically verifiable feedback (Shao et al. 2024; Yu et al. 2026; Zheng et al. 2025). Group-based algorithms, such as Group Relative Policy Optimization (GRPO), generate multiple responses for each training sample and compare their rewards to update the policy (Shao et al. 2024). These rollouts explore alternative solutions but also incur substantial generation cost (Guo et al. 2025; Yao et al. 2026). However, GRPO commonly assigns the same number of rollouts to every selected sample (Shao et al. 2024; Yao

et al. 2026). This uniform allocation treats all samples as if they require the same amount of exploration, although the current policy may easily solve some samples and struggle with others. Additional rollouts on easy samples often repeat predictable outcomes, whereas difficult but learnable samples may receive too few attempts to discover useful solution trajectories (Nguyen et al. 2026a; Yao et al. 2026; Zeng et al. 2026). This budget mismatch motivates difficultyaware scheduling, which uses sample difficulty to decide how to distribute the available exploration budget. Existing studies implement difficulty-aware scheduling in two ways. First, sample-selection methods adjust the training distribution and decide which samples receive exploration (Gao et al. 2026; Qu et al. 2026; Kong et al. 2026). Second, rollout-allocation methods assign different numbers of rollouts to selected samples and determine how much exploration each sample receives (Nguyen et al. 2026a; Yao et al. 2026; Zeng et al. 2026). Although these methods make different scheduling decisions, both need up-to-date difficulty estimates because the policy continually changes which samples it can solve. This requirement makes low-cost online difficulty estimation essential for adaptive RLVR scheduling. However, obtaining such up-to-date and reliable estimates remains challenging. Some researchers explicitly estimate success probabilities for train examples under the current policy by using additional rollout probing (Zeng et al. 2026; Yao et al. 2026; Team et al. 2025). Although this approach provides estimation, it incurs substantial computational overhead and introduces statistical uncertainty due to the limited number of stochastic rollouts1 . Further, some researchers estimate these success probabilities from outcomes collected during previous training steps (Nguyen et al. 2026a,b; Kong et al. 2026; Qu et al. 2026). Although this approach reduces the additional rollout overhead, it struggles with cold start and accuracy because historical results may introduce noise from the variance of stochastic outcomes, and the historical results may become outdated as the policy model evolves during training. Thus, these limitations motivate the following question: How can we continuously estimate the evolving difficulty of all training examples at low cost as the policy evolves during RLVR training? 1 An intuitive analogy: tossing a fair coin 4 times still has a 12.5% chance of coming up all heads or all tails.

We argue that semantic or reasoning structure related samples can provide mutually informative evidence for difficulty estimation. Samples with similar semantic often rely on similar model capabilities and may exhibit exploitable local statistical correlations. Thus, in this paper, we propose a graph-based online difficulty estimation framework for RLVR-based LLM training, which can be integrated into different RL training schedulers to improve their performance. Specifically, we first construct a difficulty-aware sample graph that connects samples with similar semantic and reasoning characteristics. Then, we model sample difficulty as graph-structured latent states and develop an online variational inference algorithm to update these states using rollout feedback collected during training. In this way, related samples can share historical evidence, enabling us to continuously estimate the success probability of all training examples without additional rollout probing. Finally, we integrate our estimator into sample selection or rollout allocation methods to improve RLVR training efficiency. Experiments across different models and datasets demonstrate the accuracy, efficiency, and generality of our method. Our contributions are as follows: (1) We are the first to formulate dynamic difficulty estimation in RLVR as a graphstructured latent-variable inference problem. (2) We propose a low-cost online estimator that propagates rollout feedback among related samples and continuously estimates their success probabilities as the policy evolves. (3) We integrate our estimator into both sample selection and rollout allocation methods. Extensive experiments show that our method is cold start friendly and substantially reduces difficulty estimation overhead while consistently improving the downstream performance of RLVR schedulers.

Related Work Adaptive Sampling and Rollout Allocation in RLVR Curriculum learning order or reweight examples according to difficulty, competence, or learnability (Bengio et al. 2009; Mindermann et al. 2022). This principle is especially relevant to group-based RLVR, where prompts with nearly deterministic group rewards provide little group-relative learning signal (Shao et al. 2024; Yu et al. 2026; Zheng et al. 2025). Prompt-selection methods therefore use estimated difficulty, competence alignment, uncertainty, or reward dynamics to prioritize informative examples (Yu et al. 2026; Gao et al. 2026; Qu et al. 2026; Kong et al. 2026; Zheng et al. 2026; Bae et al. 2026). A complementary line allocates non-uniform rollout counts. GVM, VIP, and CurES use gradient-variance or stability objectives (Yao et al. 2026; Nguyen et al. 2026a; Zeng et al. 2026), whereas recent methods use sequential uncertainty reduction, Bernoulli-variance proxies, or posterior hit utility (Xiong et al. 2025; Fang et al. 2026). Although their scheduling objectives differ, these methods require estimates of current prompt behavior. Our work is complementary: it provides a reusable estimator rather than another scheduling rule.

Dynamic Difficulty Estimation for Reasoning LLMs Difficulty depends not only on an example but also on the policy model. Item response theory explicitly models the interaction between latent ability and item difficulty and has been adapted to NLP evaluation (Lalor, Wu, and Yu 2016; Rodriguez et al. 2021). Training-dynamics methods instead characterize examples through quantities such as confidence and variability across epochs, or prioritize examples that remain learnable and useful (Swayamdipta et al. 2020; Mindermann et al. 2022). RLVR further requires these modeldependent estimates to track an evolving policy. Existing RLVR estimators follow three broad strategies. Model-based methods learn a value or scoring model to predict difficulty without rolling out every candidate (Gao et al. 2026). Probing-based methods estimate current success probabilities from additional on-policy generations, obtaining timely but costly and noisy signals (Yao et al. 2026; Zeng et al. 2026; Team et al. 2025). History-based methods reuse training feedback: MoPPS performs streaming Bayesian inference (Qu et al. 2026); CDAS aggregates historical performance discrepancies (Kong et al. 2026); GRESO exploits temporal regularity in rewards (Zheng et al. 2026); and VIP fits a lightweight predictor to recent rollouts (Nguyen et al. 2026a). Complementary scheduling methods operate at different granularities: Re-Schedule derives a static structurallearnability score from offline reasoning trees for easy-tohard curriculum scheduling (Wang et al. 2026), whereas ARRoL predicts final correctness from partial rollouts and prunes trajectories online to balance binary rewards (Xu et al. 2026). Learned predictors must remain calibrated under policy drift, probing and tree construction incur generation overhead, and historical observations may be sparse or stale. Our approach also draws on graph-based semi-supervised learning and probabilistic graphical models, using spectral structure, Potts priors, and mean-field inference to propagate sparse feedback across related samples; see Appendix H for further discussion. In contrast, our estimator couples related samples through an explicit graph, pools sparse evidence through shared latent difficulty states. Our setting combines these ideas with policy-induced nonstationarity: rollout observations are sparse, while their generating policy changes throughout training. We construct a difficulty-aware graph, associate prompts with time-indexed latent states, aggregate binary outcomes through state-level Beta–Binomial factors, and carry the variational posterior across training steps. This yields sequential probabilistic reasoning over relational and evolving latent states, together with the success-probability estimates required by adaptive RLVR schedulers.

Method 3.1 Overview We propose a graph-based online framework for estimating the evolving difficulty of training examples in RLVR. By leveraging historical rollout outcomes from related examples, our framework predicts the success probability and difficulty of each example under the current policy before each training step. As illustrated in Fig. 1, the framework con-

�0 (Base Model)

������

(a) Difficulty-Aware Sample Graph Top-k Cosine Similarity

Difficulty aware Embedding

Soft Label

W

Spectral Clustering

t=2,3…T

(c) Online Mean-Field Variational Inference

( b) Graph-Structured Latent Difficulty Model

�t−1 History feedback

t-2

T times

��,�−� ��,�−� + ��,�−� x1,t−1 ��2,�−1 = 0.46 ��3,�−1 = 0.92 ��,�−� =

�t

�T (Final Policy)

t-1

x2,t−1

��1,�−1 = 0.05

x3,t−1

(d) Difficulty Estimation for Adaptive RL Schedulers ��1�1 = 89% ��1�2 = 8% ��1�3 = 1% ��1�1 = 5% ��1�2 = 75% ��1�3 = 20% ��1�1 = 2% ��1�2 = 15% ��1�3 = 83%

��,� =

� �=�

���,�−� ��,�−�

Difficulty Estimator

0.09 0.53 0.83

Scheduler

…

Figure 1: The overview of our framework. We first construct a difficulty-aware sample graph (a). During RL training, our graphstructured 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). sists of four sequential modules. First, the Difficulty-aware Sample Graph jointly encodes the semantic and difficulty features of training examples and constructs a sparse train set graph (Sec. 3.3). Second, the Graph-Structured Latent Difficulty Model maps the graph into latent difficulty states that can be dynamically updated by rollouts feedback, with examples in the same state sharing a common success probability (Sec. 3.4). Third, the Online Mean-Field Variational Inference updates the latent-state distribution of each example and the posterior success probability of each latent state (Sec. 3.5). Finally, we use the updated posterior to estimate the success probability and difficulty of candidate samples for the next training step (Sec. 3.6).

3.2 Problem Formulation Let the training dataset for reinforcement learning be D = {xi }N i=1 , where xi denotes the i-th sample. Following the actual training order, we let Ot represent the set of samples for which we generate rollouts at training step t. Under the current policy model πt , each sample i ∈ Ot generates ni,t rollouts, and we denote the binary correctness outcome of the g-th rollout by yi,t,g ∈ {0, 1}. We aggregate the rollout outcomes of theP same sample into the number of successful ni,t rollouts, si,t = g=1 yi,t,g , and define its empirical success rate as ri,t = si,t /ni,t . Our goal is to accurately estimate the probability that the current policy correctly solves each sample before each RL

training step: p̂i,t = PrY ∼πt (Y is correct | xi , s<t , n<t ). We then define the difficulty of sample i at step t as di,t = 1− pi,t . Finally, we feed these probability or difficulty estimates into existing RL scheduling frameworks to guide decisions such as sample selection and rollout allocation.

3.3 Difficulty-Aware Sample Graph In this section, we construct a sparse similarity graph over the training dataset based on semantic and difficulty. This allows samples with few or no prior rollouts to estimate their current expected difficulty by leveraging historical feedback from semantically and difficulty-wise similar neighbors. To encourage the encoder to capture semantic content, reasoning structure, and difficulty-related characteristics of each sample, we introduce a difficulty-aware instruction Iπ : Instruction: Given a prompt, encode it into a dense vector that captures both its semantic content and difficulty level, for the purpose of similarity comparison. \n Prompt: [SAMPLE] Let femb denote a pretrained embedding model. The repree = femb (Iπ , xi ) and sentation of sample xi is computed as ϕ i e e normalized to ϕi = ϕi /∥ϕi ∥2 . For each pair of samples, we measure their similarity with cosine similarity: cij = ϕ⊤ i ϕj . To capture the underlying manifold structure of highdimensional sample embeddings while reducing computational cost, we construct a k-nearest-neighbor graph by retaining the knn nearest neighbors of each node. We then retain only edges where the two nodes are mutual k-nearest neigh-

bors and remove those with negative similarities, yielding a sparse undirected sample graph W ∈ RN ×N . Specifically, Wij = cij if xi and xj are mutual k-nearest neighbors and cij > 0, and 0 otherwise. A larger Wij reflects greater similarity in semantic content, reasoning structure, and difficultyrelated features between xi and xj .

3.4 Graph-Structured Latent Difficulty Model In this section, we aim to perform statistical inference of sample difficulty by leveraging the graph structure and the historical rollout outcomes collected during previous RL training. Specifically, we first construct a graph-structured prior over sample latent states, then model rollout feedback through shared state-level success probabilities, and finally derive the posterior distribution for subsequent difficulty estimation. Graph Prior. Although W captures local similarity relationships among samples, it falls short in describing the overall difficulty structure of the training dataset. To further uncover similarities in both semantic features and difficulty levels across samples, we apply spectral clustering to the sparse undirected sample graph W ∈ RN ×N , and it yields an initial set of static cluster labels ci ∈ {1, . . . , K}. However, spectral clustering relies solely on static sample representations, and its assignments can be affected by representation and clustering errors. More importantly, as we continuously update the policy during RL training, the difficulty of the same sample under the current policy may also change. Therefore, we convert each static cluster label into a smoothed(prior distribution over 1 − ϵ, k = ci , latent states, we define Aik = . This ϵ k ̸= ci , K−1 , conversion retains the structure from spectral clustering, and it also allows subsequent rollout outcomes to refine each sample’s latent assignment. Then, inspired by Besag (1974), we introduce a Potts graph prior (Potts 1952) over the latent assignments to retain the initial clustering structure while encouraging neighboring samples to share the samelatent state. Specifically, p(zt | W, A) = i  h P we define QN N PN β 1 i=1 Ai,zi,t exp 2 i=1 j=1 Wij I(zi,t = zj,t ) , Z(W,A) where zt = (z1,t , . . . , zN,t ) denotes the vector of latent-state assignments at step t, with zi,t ∈ {1, . . . , K} indicating the assignment for sample xi . The hyperparameter β controls the strength of graph propagation, and Z(W, A) is the partition function. State-Level Success Model. To statistically infer sample difficulty and latent-state assignments, we further integrate their relationship with historical rollout feedback into a Bayesian framework. However, estimating an independent success probability for each sample would still require a large number of sample-level rollouts to yield stable estimates. To address this and improve the efficiency of historical feedback utilization, we assume that samples assigned to the same latent state share a common state-level success probability. For each latent state k, following Zeng et al. (2026) and Qu et al. (2026), we model its success probability
at step hist t with a Beta distribution: θk,t ∼ Beta ahist k,t , bk,t . This

distribution jointly captures the estimate of the state-level success probability while enabling sequential Bayesian updates. We set the prior parameters for step t by inheriting the posterior parameters from step t − 1, i.e., ahist k,t = ak,t−1 and bhist = b . Both parameters are initialized to 1: k,t−1 k,t ak,0 = 1, bk,0 = 1. Conditioned on the latent-state assignment zi,t = k and the conditional independence of rollout outcomes, the number of successes si,t out of ni,t rollouts follows a binomial distribution: (si,t | ni,t , zi,t = k, θk,t ) ∼ Binomial(ni,t , θk,t ). Let θ t = (θ1,t , . . . , θK,t ) collect the success probabilities of all latent states. By combining the graph-structured prior over zt , the independent Beta priors over each θk,t , and the sample-level binomial likelihoods, we obtain the joint distribution at step t: QK pt (st , zt , θ
t | nt , W, A) = p(zt | W, A) k=1
Beta θk,t | Q hist hist ak,t , bk,t i∈Ot Binomial si,t | ni,t , θzi,t ,t . Posterior Inference. From this joint distribution, we apply Bayes’ rule to infer the posterior over the latent-state assignments and state-level success probabilities after observing the rollout outcomes. This posterior allows us to jointly update our beliefs about each sample’s latent state and the shared success probabilities, which is essential for subsequent difficulty estimation. It factorizes as pt (zt , θ t | st , nt , W, A) = pt (st ,zt ,θ t |nt ,W,A) t ,zt ,θ t |nt ,W,A) = P Rptp(s . pt (st |nt ,W,A) t (st ,zt ,θ t |nt ,W,A) dθ t zt

3.5 Online Mean-Field Variational Inference In this section, we employ online mean-field variational inference to support sample difficulty estimation for adaptive LLM RL scheduling. At each training step, only selected samples provide rollout feedback. The sample graph allows this feedback to update the latent-state distributions of related samples. Specifically, we approximate the joint posterior of the latent states zt and state-level success probabilities θ t . However, exact posterior inference is intractable. The Potts prior couples the latent states of neighboring samples. This coupling requires a summation over all K N possible assignments. Its computational cost grows exponentially with the number of training samples. To obtain tractable updates, we follow prior work (Zhang 1992; Hoffman et al. 2013) and adopt the mean-field approximation QN QK qt (zt , θ t ) ≈ i=1 qi (zi,t ) k=1 q(θk,t ).Here, qi (zi,t ) represents the latent-state distribution of sample i. We denote its state-assignment probability by qik,t ≡ qi (zi,t = k). We restrict each state-level factor to the Beta family: q(θk,t ) = Beta(ak,t , bk,t ). Let Q denote the variational family defined above. We seek the member of Q that minimizes the Kullback– Leibler (KL) divergence from the exact posterior: qt⋆ = arg minqt ∈Q KL [qt (zt , θ t ) ∥, pt (zt , θ t | st , nt , W, A)] . The exact posterior contains the partition function Z(W, A) of the Potts prior. This makes the KL divergence difficult to evaluate directly. We instead use the evidence lower bound (ELBO): Lt (qt ) = Eqt [log pt (st , zt , θ t | nt , W, A)] − Eqt [log qt (zt , θ t )]. The log marginal likelihood satisfies log pt (st | nt , W, A) = Lt (qt ) + KL [qt (zt , θ t ) ∥, pt (zt , θ t | st , nt , W, A)] . The left-hand side does not depend on qt . Thus, minimizing

the KL divergence is equivalent to maximizing the ELBO: qt⋆ = arg maxqt ∈Q Lt (qt ). We can evaluate the ELBO under the mean-field approximation. In particular, the expected Potts interaction becomes PK Eqt [I(zi,t = zj,t )] = k=1 qik,t qjk,t . Substituting this result and the variational factors into the ELBO gives PN PN PK Lt (q) = (β/2) i=1 j=1 Wij k=1 qik,t qjk,t PN PK PN PK + i=1 k=1 qik,t log Aik − i=1 k=1 qik,t log qik,t  P PK + i∈Ot k=1 qik,t si,t [ψ(ak,t ) − ψ(ak,t + bk,t )] + (ni,t − si,t )[ψ(bk,t ) − ψ(ak,t + bk,t )] PK hist − k=1 KL[Beta(ak,t , bk,t )∥ Beta(ahist k,t , bk,t )]. We omit terms independent of qt . Here, ψ(·) denotes the digamma function. Appendix A provides the detailed derivation. The ELBO contains two groups of variational parameters. The first group contains the assignment probabilities qik,t . The second contains the Beta parameters (ak,t , bk,t ). We optimize one group while keeping the other fixed. This procedure is known as coordinate ascent. Proposition1 derives the assignment update, and Proposition 2 derives the Beta update. We alternate these updates during inference. Proposition 3 establishes the convergence of this alternating procedure. Appendix A provides the proofs. Proposition 1: Coordinate-Optimal Assignment Update Fix q(θ t ) and all qj (zj,t ) for ⋆ j ̸= i. The coordinate-optimal update is qik,t = PN VB Softmaxk [log Aik + β j=1 Wij qjk,t + Ii ∈ Ot )ℓik,t ], where ℓVB ik,t = si,t [ψ(ak,t ) − ψ(ak,t + bk,t )] + (ni,t − si,t ) [ψ(bk,t ) − ψ(ak,t + bk,t )] . Proposition 2: Coordinate-Optimal Beta Update Fix ⋆ q(zt ). The coordinate-optimal factor P is q (θk,t ) = hist Beta(ak,t , bk,t ), where ak,t = ak,t + i∈Ot qik,t si,t , and P bk,t = bhist k,t + i∈Ot qik,t (ni,t − si,t ). Proposition 3: Monotonicity and Convergence At trainhist ing step t, we keep (ahist k,t , bk,t ) fixed. Each update in Propositions 1 and 2 maximizes the ELBO with respect to one group of parameters. Therefore, neither update decreases Lt (q) and the ELBO sequence converges. This convergence provides a stable estimator state at each LLM RL step (though it may not be globally optimal). We now apply Propositions 1 and 2 in an online alternating procedure. After training step t produces rollout feedback for Ot , we initialize inference with the previous estimator state: (0) (0) (0) qik,t = qik,t−1 , ak,t = ak,t−1 , bk,t = bk,t−1 .· We keep hist (ahist k,t , bk,t ) fixed during inference at step t. Each iteration first applies Proposition 1 to update qik,t . It then applies Proposition 2 to update (ak,t , bk,t ). The first step updates the latent-state assignments and serves as an E-like update. The second updates the state-level parameters and serves as an M-like update. We repeat both steps until the ELBO increment falls below a preset threshold or the iteration count

reaches its maximum.2 Proposition 1 updates the assignments of both observed and unobserved samples. Proposition 2 updates the state-level success probabilities using the observed feedback. Together, they transform the feedback from Ot into an updated estimator state for the full training set: St = {qt , at , bt }. The next subsection converts St into sample-level difficulty estimates for adaptive scheduling. We also use St to initialize inference at the next training step.

3.6 Difficulty Estimation for Adaptive RL Schedulers In this section, we aggregate the state-level posterior from the previous training step into sample-level estimates of success probability, difficulty. These estimates then guide adaptive sample selection and rollout allocation. At the beginning of RL training step t, the estimator loads the state St−1 = {qt−1 , at−1 , bt−1 } from the previous step. For each latent state k, we compute the posterior mean of its a success probability as µk,t−1 = ak,t−1k,t−1 +bk,t−1 , We first = form a model-based prediction for sample xi : pbmodel i,t PK k=1 qik,t−1 µk,t−1 . Then we adjust the prediction based on whether the sample has been rolled out before. If xi has no prior rollouts, we directly use the model prediction: pbi,t = pbmodel i,t . If it has been sampled in earlier steps, we average the model prediction with its historical success rate r̄i,<t : pbi,t = γ pbmodel + (1 − γ)r̄i,<t ) (γ = 0.5, see discusi,t sion in Appendix E). Also, the estimated difficulty is then dbi,t = 1 − pbi,t . Overall, before training step t, the estimator predicts the difficulty of every sample. These outputs serve as a plugand-play component for most sample-level scheduling and resource-allocation frameworks in RLVR training.

Experiment Implementation Details Setting. We conduct all training and inference on 4×A100 80G GPUs. To avoid data leakage (Wu et al. 2026), following Yao et al. (2026) and Zeng et al. (2026), we adopt Qwen 2.5 1.5B Math (Yang et al. 2024) and Llama 3 1BInstruct (Grattafiori et al. 2024) as base models. For the main experiments, we keep the environment strictly consistent with the original baselines. We integrate our framework as a plug-and-play component into the original code to demonstrate that it improves the final RL performance. For fairness, we use the same computational budget for all experiments, equivalent to one round of the standard GVM algorithm (∼1.5M rollouts, including pre-sampling). We use Qwen3-0.6B (Zhang et al. 2025) as the sentence embedding model, and set K = 320, knn = 80, γ = 0.5 and β = 2. Guidelines for hyperparameter or embedding model selection across different setting are provided in Appendix E. Dataset. Since all baselines we integrate are based on mathematical problems, we follow the experimental settings of previous works (Yao et al. 2026; Gao et al. 2026; Zheng 2 We use a numerical approximation to accelerate computation. Code and Data Supplement provide the details.

Method Base GVM GVM+Ours PCL PCL+Ours GRESO GRESO+Ours

Qwen-2.5-Math-1.5B (Average@8) MATH500 AIME24 AIME25 Olym 39.3 3.30 3.33 25.2 71.9 11.3 11.3 35.8 74.7 16.7 13.3 38.3 59.7 7.92 4.58 26.1 11.3 6.67 27.1 61.6 66.8 10.0 7.50 30.3 68.2 10.0 10.0 31.9

Llama-3.2-1B-Instruct (Average@8) MATH500 AIME24 AIME25 Olym 17.5 0.00 0.00 3.02 23.9 0.42 0.00 4.59 25.7 3.30 0.00 4.89 26.7 0.42 0.00 5.04 27.4 0.00 0.42 5.81 30.0 2.50 0.00 7.59 32.6 6.67 0.42 8.26

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). et al. 2026) and conduct reinforcement learning on NuminaMath (Li et al. 2024; Cui et al. 2025). We evaluate the resulting models on MATH500 (Hendrycks et al. 2021; Lightman et al. 2024), AIME 2024 (Balunovic et al. 2026), AIME 2025 (Dekoninck et al. 2026), and OlympiadBench (He et al. 2024). We provide detailed descriptions of these datasets in Appendix B and discuss their generalizability to other domains in Appendix D. Baseline. We evaluate our plug-and-play component on three representative baselines from different scheduling paradigms: GVM, a rollout-allocation method (Yao et al. 2026); PCL, a curriculum-learning method that trains a dedicated difficulty predictor (Gao et al. 2026); and GRESO, a curriculum-learning method that uses historical success rates as difficulty signals (Zheng et al. 2026). For each baseline, we replace only its original difficulty estimator with ours. Metric. We use rule-based matching to judge whether the result matches the ground truth (Guo et al. 2025; Sheng et al. 2024). Because a single evaluation on small and challenging datasets such as AIME can be sensitive to sampling randomness, we follow prior work (Yao et al. 2026; Zheng et al. 2026) and sample eight independent rollouts per prompt, reporting Average@8 accuracy.

Overall Performance We integrate our estimator into three representative RL schedulers: GVM for rollout allocation, PCL for curriculum selection, and GRESO for selective rollout. We replace their original difficulty estimators while retaining their scheduling strategies, and compare all methods under the same total generation budget. As shown in Table 1, our estimator improves the overall performance of all three schedulers, with gains in most model–dataset settings. For GVM, GVM+Ours retains presampling only for gradient-related estimation and replaces the original difficulty estimate with ours. It improves performance in seven of the eight settings and matches the baseline in the remaining one. We will provide a more indepth analysis in the next section. When integrated into PCL and GRESO, our estimator also improves the corresponding baselines in most settings. A plausible explanation is that the more stable difficulty estimates help the schedulers identify samples that are likely to yield both correct and incorrect responses within the same rollout group. Such sam-

ples produce nondegenerate group-relative advantages and potentially more informative optimization signals. Although full-history aggregation may introduce temporal lag, graph propagation and shared state-level statistics make its effect largely systematic across related samples, affecting absolute calibration more than relative difficulty ranking. Since adaptive schedulers primarily rely on ranking for sample selection and rollout allocation, this bias has limited impact on scheduling, as supported by the high correlations and downstream gains above. Appendix G further examines a windowed variant that reduces stale historical influence. Overall, these results suggest that our estimator can serve as a reusable component for different RL scheduling strategies and improve downstream performance under a matched generation budget.

Can Our Method Continuously Track Sample Difficulty During RL Training? We evaluate how accurately different methods track evolving sample difficulty along the same GRPO training trajectory. At each evaluation point, we use the empirical success rate from 8 independent rollouts generated by the corresponding policy as the reference empirical success probability. We report sample-level MAE for calibration and batch-level Pearson correlation r (batch size 256) for ranking consistency in Table 2, since sample-level empirical rates are discrete and sparse. Lower MAE and higher r indicate better estimation. We compare two high-cost probing baselines, Sample Before RL (SBR) and Sample Before Step (SBS), with three representative low-cost approaches: PCL (LLM-based difficulty prediction), VIP (historical-feedback-based statistical estimation) , and MoPPS (history-based dynamic modeling). SBS probes samples repeatedly with the current policy; it therefore achieves the highest accuracy but requires roughly 45–48 hours of extra computation. SBR, however, estimates difficulty only once before training, so its predictions quickly become outdated as the policy evolves, highlighting the limitation of static estimates. Our approach performs best overall among low-cost methods, with a particularly clear advantage in the early sparse-feedback stage. Early in training, it achieves Pearson correlations of 0.482 for Qwen and 0.469 for Llama, together with the lowest MAE among the low-cost baselines. These results indicate that the graph structure alleviates observation sparsity by transferring feedback across

Base Model Qwen-2.5 Math-1.5B

Llama-3.2 1B-Instruct

Methods Sample before RL Sample before Step VIP PCL MoPPS Ours Sample before RL Sample before Step VIP PCL MoPPS Ours

Early Steps MAE (↓) r (↑) 0.116 0.544 0.063 0.959 0.373 0.404 0.138 0.373 0.290 0.482 0.116 0.374 0.044 0.986 0.413 0.204 0.467 0.413 0.197 0.469

Middle Steps MAE (↓) r (↑) 0.139 0.856 0.054 0.971 0.094 0.794 0.336 0.407 0.149 0.910 0.133 0.912 0.141 0.648 0.046 0.967 0.107 0.895 0.181 0.404 0.133 0.864 0.100 0.868

Last Steps MAE (↓) r (↑) 0.151 0.865 0.049 0.974 0.084 0.885 0.328 0.474 0.118 0.929 0.123 0.943 0.154 0.671 0.046 0.967 0.084 0.880 0.187 0.525 0.109 0.869 0.075 0.913

Full Steps MAE (↓) r (↑) 0.135 0.522 0.055 0.969 0.184 0.423 0.356 0.281 0.214 0.754 0.183 0.836 0.137 0.394 0.045 0.986 0.201 0.717 0.191 -0.231 0.218 0.606 0.131 0.776

Time (A100*h) ∼29.6 ∼45.3 ∼0.05 ∼7.36 ∼0.12 ∼33.4 ∼47.9 ∼0.05 ∼4.38 ∼0.12

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 Qwen-2.5 Math-1.5B Llama-3.2 1B-Instruct

Methods Ours w/o Spectral Init. w/o Prior Smoothing w/o Graph Sparsification Ours w/o Spectral Init. w/o Prior Smoothing w/o Graph Sparsification

Full Steps MAE (↓) r (↑) 0.183 0.836 0.218 0.710 0.197 0.783 0.187 0.835 0.131 0.776 0.197 0.686 0.144 0.736 0.134 0.742

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

related samples. As more rollout observations accumulate, the full-trajectory correlations increase to 0.836 and 0.776, while the total estimation overhead remains approximately 0.12h. Overall, our method mitigates early-stage observation sparsity and tracks policy-induced difficulty changes with low computational overhead.

retains more reliable relationships between samples.

Do Spectral Clusters Capture Semantic and Difficulty Structure? We use MATH (Hendrycks et al. 2021) for this analysis because it provides standardized annotations of both subject category and difficulty level, allowing us to evaluate the semantic and difficulty information captured by the clusters separately. Following Sec.3.3, we embed the MATH problems and perform spectral clustering. The resulting clusters are strongly associated with subject categories (χ2 = 10,995.84, p < 10−300 ; Cramér’s V = 0.494), indicating the spectral partition effectively captures semantic structure. After controlling for subject category, difficulty distributions still differ significantly across clusters (Kruskal–Wallis, pmax < 5 × 10−3 ). These results show the clusters capture not only problem semantics but also difficulty information beyond subject identity, thereby providing an informative initial structure for subsequent online difficulty inference. We provide the full statistical details in Appendix F.

Ablation Study We ablate spectral initialization, prior smoothing, and graph sparsification. Table 3 reports results over the full training trajectory. Random initialization causes a substantial performance drop. Since our EM-style optimization only guarantees convergence to a local optimum, spectral clustering provides a high-quality starting point that guides inference toward a better solution, whereas random initialization can lead to poor local optima. Replacing the smoothed latentstate prior Aik with hard assignments also degrades performance. As the policy evolves, sample difficulty and its latentstate assignment should evolve accordingly. The smoothed prior preserves the initial clustering structure while allowing rollout feedback to revise the assignments, whereas hard assignments prevent such adaptation. Using a dense graph causes a modest decline because weakly related edges introduce noise into feedback propagation. Graph sparsification

Conclusion In this work, we address inefficient exploration-budget allocation in RLVR through graph-based online difficulty estimation. Our framework connects samples with similar semantic content and reasoning structures and uses rollout feedback to track their evolving difficulty without dedicated probing. The resulting estimates support both sample-selection and rollout-allocation schedulers. Experiments across multiple base models, schedulers, and benchmarks show that our framework improves downstream reasoning performance in most settings under matched rollout budgets while adding little online computational overhead. These results demonstrate the potential of online difficulty estimation to support more efficient RLVR training.

A. ELBO Derivation and Proofs

Then

This section derives the expanded evidence lower bound (ELBO) in Sec. 3.5 and proves Propositions 1–3. For compactness, define δik,t = I(zi,t = k) and let Ct collect all terms that are independent of the variational distribution. The mutual-neighbor graph is undirected, so Wij = Wji , and it has no self-loops, so Wii = 0.

N

Lt (qt ) =

+

−

log pt (st , zt , θ t | nt , W, A) = Ct +

i=1 k=1

+

+

qik,t log qik,t

K XX

qik,t ℓVB ik,t

K X

Beta Dk,t + Ct ,

(9)

k=1

where ℓVB ik,t = si,t [ψ(ak,t ) − ψ(ak,t + bk,t )]

δik,t si,t log θk,t

+ (ni,t − si,t ) [ψ(bk,t ) − ψ(ak,t + bk,t )] .

i∈Ot k=1 K XX

−

k=1

K h i X hist (ahist k,t − 1) log θk,t + (bk,t − 1) log(1 − θk,t ) K XX

N X K X

i∈Ot k=1

K

X β XX δik,t log Aik + Wij δik,t δjk,t 2 i=1 j=1

k=1

+

qik,t log Aik

i=1 k=1

+ N

N X K X i=1 k=1

From the joint model in Sec. 3.4, its log density can be written, up to the constant Ct , as N

K

k=1

A.1 Derivation of the Expanded ELBO

N X K X

N

X β XX Wij qik,t qjk,t 2 i=1 j=1

Dropping Ct , which is independent of qt , gives exactly the expanded ELBO reported in Sec. 3.5.

δik,t (ni,t − si,t )

i∈Ot k=1

× log(1 − θk,t ).

(1)

Here, Ct includes − log Z(W, A), the Beta normalizers, and the binomial coefficients, all of which are fixed with respect to qt . Under the mean-field distribution, Eqt [δik,t ] = qik,t , Eqt [δik,t δjk,t ] = qik,t qjk,t (i ̸= j), Eqt [log θk,t ] = ψ(ak,t ) − ψ(ak,t + bk,t ), Eqt [log(1 − θk,t )] = ψ(bk,t ) − ψ(ak,t + bk,t ).

(2) (3) (4) (5)

The second identity is sufficient for the graph term because Wii = 0. The negative entropy contribution factorizes as −Eqt [log qt ] = −

K N X X

−

Eqt [log q(θk,t )].

A.2 Proof of Proposition 1 Fix q(θ t ) and every assignment factor except qi (zi,t ). Because W is symmetric, the two appearances of node i in the double graph sum combine and cancel the factor 1/2. The terms of Eq. (9) that depend on qik,t are therefore Lt (qi ) =

K X

qik,t hik,t −

k=1

hik,t = log Aik + β

K X

qik,t log qik,t + C,

(6)

k=1

Combining the expected log Beta prior with the corresponding Beta-factor entropy gives   hist Eqt log Beta(θk,t | ahist k,t , bk,t ) − log q(θk,t )   hist = − KL Beta(ak,t , bk,t ) Beta(ahist k,t , bk,t ) . (7) Substituting these identities into Lt (qt ) = Eqt [log pt ] − Eqt [log qt ] yields the expression below. To keep the display compact, let   Beta hist (8) Dk,t = KL Beta(ak,t , bk,t ) Beta(ahist k,t , bk,t ) .

(11)

k=1 N X

Wij qjk,t + I(i ∈ Ot )ℓVB ik,t .

j=1

(12) Introduce a Lagrange multiplier λi for define

qik,t log qik,t

i=1 k=1 K X

(10)

Let (qi ) = Lt (qi ) + λi

K X

PK

k=1 qik,t = 1 and

! qir,t − 1 .

(13)

∂ Let (qi ) = hik,t − log qik,t − 1 + λi . ∂qik,t

(14)

r=1

Differentiating gives

Setting this derivative to zero and normalizing over k yields exp(hik,t ) ⋆ qik,t = PK = Softmaxk (hik,t ), r=1 exp(hir,t ) which is the update in Proposition 1.

(15)

A.3 Proof of Proposition 2 Q

Fix q(zt ) and define q−k,t = q(zt ) r̸=k q(θr,t ). The standard mean-field coordinate identity gives  log q ⋆ (θk,t ) = Eq−k,t log pt (st , zt , θ t  | nt , W, A) + C. (16) Retaining only terms involving θk,t in Eq. (1) gives X qik,t si,t , αk,t = ahist k,t +

(17)

i∈Ot

γk,t = bhist k,t +

X

qik,t (ni,t − si,t ),

(18)

log q ⋆ (θk,t ) = (αk,t − 1) log θk,t + (γk,t − 1) log(1 − θk,t ) + C.

(19)

i∈Ot

This is the log density of a Beta distribution. Hence q ⋆ (θk,t ) = Beta(ak,t , bk,t ), X ak,t = ahist qik,t si,t , k,t +

(20) (21)

i∈Ot

bk,t = bhist k,t +

X

qik,t (ni,t − si,t ),

(22)

i∈Ot

which proves Proposition 2.

A.4 Sequential and Synchronous Implementations Proposition 1 gives the exact coordinate-optimal update for a single assignment factor qi (zi,t ) while all other factors are held fixed. We consider two implementations of this update.

All assignment factors in Eq. (24) are computed in parallel from the same previous iterate, after which the Beta factors are updated using Proposition 2. Unlike the sequential implementation, a synchronous assignment sweep is not an exact block-coordinate maximization of the ELBO. Consequently, Proposition 3 does not directly guarantee that every synchronous sweep is ELBO non-decreasing. We treat the synchronous implementation as a parallel approximation to the theoretically grounded sequential procedure. To evaluate this approximation, we compare the converged sample-level success-probability estimates produced by the two implementations. We define their discrepancy at training step t as ∆t = max pbsync bseq i,t − p i,t . 1≤i≤N

Across the evaluated training checkpoints, the discrepancy remains within 10−2 . At the same time, the synchronous implementation allows the graph-message aggregation and assignment updates to be executed efficiently in parallel, resulting in substantially better wall-clock performance. We therefore use and recommend the synchronous implementation in practice, while retaining the sequential implementation as the reference algorithm for the theoretical analysis.

A.5 Proof of Proposition 3 We prove the result for the strict sequential implementation described in Sec. A.4. Fix a training step t. Throughout the inference procedure at this step, the historical parameters hist (ahist k,t , bk,t ), the graph (W, A), and all rollout observations are fixed. We assume that

Sequential reference implementation. Our reference implementation performs a strict sequential Gauss–Seidel sweep over the samples. Under the update order i = 1, . . . , N , the assignment update at iteration m + 1 is " X X (m+1) (m+1) (m) qik,t = Softmaxk log Aik + β Wij qjk,t + β Wij qjk,t j<i

j>i

# VB,(m) + I(i ∈ Ot )ℓik,t

.

(23)

Thus, each update uses the most recently available values of the previously updated factors. After one complete assignment sweep, the Beta factors are updated according to Proposition 2. Because every assignment factor is optimized while the remaining factors are fixed, this implementation is an exact coordinate-ascent variational inference procedure. The monotonicity and convergence results in Proposition 3 apply to this sequential implementation.

(25)

Aik > 0

for every i, k,

ahist k,t > 0,

bhist k,t > 0

|Wij | < ∞,

(26) for every k,

ni,t < ∞.

(27) (28)

The first condition is satisfied by the smoothed initialization when 0 < ϵ < 1. We further assume that the categorical factors are updated cyclically and that every factor is updated once in each complete sequential sweep. Monotonicity. Fix all variational factors except one categorical factor qi (zi,t ). Proposition 1 gives the unique maximizer of the ELBO with respect to this factor. Therefore, updating qi (zi,t ) cannot decrease the ELBO. Similarly, after fixing q(zt ) and all Beta factors except q(θk,t ), Proposition 2 gives the coordinate-optimal Beta factor. Updating this factor therefore cannot decrease the ELBO. (m) Consequently, if qt denotes the variational distribution after the m-th coordinate update, then

Synchronous accelerated implementation. The strict sequential update is difficult to parallelize over samples. We (m+1) (m) therefore additionally implement a synchronous Jacobi-style Lt (qt ) ≥ Lt (qt ). (29) update: Boundedness of the parameter sequence. Each categor  N ical parameter belongs to the probability simplex: X (m+1) (m) VB,(m)  qeik,t = Softmaxk log Aik + β Wij qjk,t + I(i ∈ Ot )ℓik,t . (qi1,t , . . . , qiK,t ) ∈ ∆K . (30) j=1 (24)

The product of the N categorical simplexes is compact.

Define the total number of observed successes and failures at training step t as X si,t , (31) St = i∈Ot

X

Ft =

(ni,t − si,t ).

(32)

i∈Ot

By Proposition 2 and 0 ≤ qik,t ≤ 1, the Beta parameters satisfy hist ahist k,t ≤ ak,t ≤ ak,t + St ,

(33)

hist bhist k,t ≤ bk,t ≤ bk,t + Ft .

(34)

Therefore, all Beta parameters remain in compact positive intervals. The complete variational-parameter sequence consequently lies in the compact set ! N Y Xt = ∆K i=1

×

K Y 

hist ahist k,t , ak,t + St



k=1

×

K Y 

 hist bhist k,t , bk,t + Ft .

(35) Figure 2: EM iterations

k=1

In particular, the parameter sequence has at least one accumulation point. Convergence of the ELBO values.

Let

ppost = pt (zt , θ t | st , nt , W, A) t

(36)

denote the exact posterior. The ELBO satisfies Lt (qt ) = log pt (st | nt , W, A)   − KL qt ppost . t

(37)

Because the model has a finite number of latent assignments, proper Beta priors, and finite rollout counts, the log evidence is finite. Since the KL divergence is nonnegative, Lt (qt ) ≤ log pt (st | nt , W, A).

(38)

Combining this upper bound with Eq. (29) shows that the ELBO-value sequence is monotone and bounded above. Hence there exists a finite L⋆t such that (m)

lim Lt (qt

m→∞

) = L⋆t .

(39)

Stationarity of accumulation points. Consider the iterates at the boundaries of complete sequential sweeps, and let Tt denote the mapping corresponding to one full sweep of all categorical and Beta-factor updates. Under Eqs. (26)– (28), the softmax assignment update, the Beta update, and the associated digamma expectations are continuous on Xt . Therefore, Tt is continuous. Let q̄t be an accumulation point of the sweep-level variational sequence. Suppose, for contradiction, that Tt (q̄t ) ̸= q̄t . Because every coordinate update is the unique maximizer of

its coordinate subproblem, at least one update in the sweep would produce a strict ELBO increase. Hence Lt (Tt (q̄t )) > Lt (q̄t ).

(40)

By continuity, the same positive improvement would hold in a neighborhood of q̄t . This contradicts the convergence of the ELBO values in Eq. (39), according to which the ELBO improvement over a complete sweep must approach zero. Therefore, Tt (q̄t ) = q̄t .

(41)

Thus, every accumulation point is a fixed point of all exact coordinate updates and is consequently coordinate-wise optimal. Since the categorical updates are strictly positive under Aik > 0, and the Beta parameters remain strictly positive, the ELBO is differentiable at such a fixed point subject to the simplex constraints. The corresponding first-order Karush–Kuhn–Tucker conditions are therefore satisfied. Every accumulation point is hence a stationary point of the ELBO. The argument establishes convergence of the ELBO values and stationarity of every accumulation point.

A.6 EM Iteration Visualization We show the evolution of the ELBO under EM iterations in Figure 2. In general, the M-step performs a notably large update only at the very first iteration. The per-round improvement in the ELBO from the E-step and M-step decays roughly exponentially, and convergence to a local stationary point or local maximum is typically reached within 50 iterations.

B. Details of Datasets and Training NuminaMath. NuminaMath is a large-scale mathematical reasoning dataset comprising approximately 860K problem–solution pairs. It covers problems ranging from Chinese high-school mathematics to U.S. and international mathematical olympiad competitions, with data primarily collected from online examination papers and mathematics discussion forums. Each problem is accompanied by a chain-of-thought solution and a verifiable final answer. Following the dataprocessing protocols of GVM and CurES, we extract approximately 150K problems from the original corpus for RL training (Cui et al. 2025). MATH. MATH is a competition-level mathematical reasoning dataset containing 12.5K problems, each accompanied by a complete step-by-step solution and a final answer. The dataset provides predefined difficulty annotations ranging from Level 1 to Level 5 and category labels covering seven subjects: prealgebra, algebra, number theory, counting and probability, geometry, intermediate algebra, and precalculus. We use these annotations only as external references rather than as training supervision. Specifically, we compare the complete method with variants that remove the clustering or graph-based components and examine how well the learned representations and structural relationships align with the provided category and difficulty labels. This analysis assesses whether the proposed components capture semantic similarity among problems and distinguish problems at different difficulty levels. MATH-500. MATH-500 is a representative subset of 500 problems selected from the original MATH benchmark. It retains the diverse mathematical subjects and difficulty levels of MATH while enabling more efficient and standardized evaluation. Each problem is accompanied by a reference solution and a verifiable final answer. We use MATH-500 to evaluate the models’ general mathematical reasoning ability across a broad range of competition-level problems.

OlympiadBench. OlympiadBench is a bilingual and multimodal scientific reasoning benchmark containing 8,476 problems collected from international olympiads, Chinese olympiads, and the Chinese college entrance examination. The final ACL 2024 version contains 6,142 mathematics problems and 2,334 physics problems, with every problem accompanied by an expert-annotated solution. The benchmark includes both open-ended problems and theoremproving problems and covers English and Chinese questions with textual or visual information. Following the evaluation protocol of GVM and CurES, we use the corresponding mathematics portion of OlympiadBench to evaluate reasoning performance on challenging olympiad-level problems.

C. Significance Analysis of Main Results Question and Comparison Units The main experiments report one Average@8 point estimate for each scheduler–base-model–benchmark combination. We use a two-sided exact sign test (Dixon and Mood 1946) to examine whether the observed improvements are directionally consistent across these heterogeneous experimental settings. This analysis directly evaluates whether integrating our method produces positive changes more frequently than would be expected under an equal-probability null hypothesis. The analysis includes the three full integrations: GVM + Ours, PCL + Ours, and GRESO + Ours. For integration method m, base model b, and benchmark d, define ∆m,b,d = Accm+Ours,b,d − Accm,b,d .

(42)

We record a gain if ∆m,b,d > 0, a loss if ∆m,b,d < 0, and a tie if ∆m,b,d = 0. Let W , L, and T denote the resulting numbers of gains, losses, and ties, respectively. Because ties provide no directional information, they are excluded from the sign-test sample size, yielding n = W + L.

Exact Test and Results

AIME 2024. Our AIME 2024 evaluation set combines the 15 problems from AIME I and the 15 problems from AIME II, yielding 30 problems in total. These problems cover areas such as algebra, geometry, number theory, counting, and probability and generally require multi-step reasoning and nontrivial mathematical insight. Each problem has a unique integer answer between 000 and 999, allowing reliable rulebased evaluation. We use AIME 2024 to assess reasoning performance on challenging competition-level mathematics problems. The general AIME format consists of 15 questions per examination, each requiring an integer answer from 000 to 999.

The two-sided exact p-value is   min(W,L)    X n −n  psign = min 1, 2 2 .   r r=0

AIME 2025. Our AIME 2025 evaluation set similarly combines AIME I and AIME II, resulting in 30 problems. Each problem requires an integer answer between 000 and 999 and involves advanced high-school mathematics across multiple domains. Since these problems were released more recently than most commonly used mathematical reasoning benchmarks, AIME 2025 provides a challenging evaluation of the models’ reasoning and generalization capabilities.

Counting directly from Table 1 gives the following results. For the PCL integration, W = 7, L = 1, and n = 8. Its two-sided exact p-value is     8 8 psign = 2 + 2−8 0 1 18 = 0.0703125. (45) = 256

Under the null hypothesis that a non-tied comparison is equally likely to favor either method, H0 : Pr(∆ > 0 | ∆ ̸= 0) = 12 ,

W ∼ Binomial(n, 12 ). (43)

(44)

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. At the nominal significance level α = 0.10, all three full integrations exhibit statistically significant directional improvements. Specifically, GVM + Ours and GRESO + Ours achieve significance at the α = 0.05 level, while PCL + Ours achieves significance at the α = 0.10 level. These results demonstrate that the positive effect of our method is not confined to a particular scheduler, base model, or benchmark, but is consistently observed across the evaluated configurations. For the pooled analysis, W = 21, L = 1, and n = 22. Equation (44) therefore gives     22 22 + 2−22 psign = 2 1 0 46 = = 1.0967 × 10−5 . (46) 4,194,304 The pooled result provides strong evidence against the null hypothesis that positive and negative changes are equally likely. Across the three full integrations, our method improves 21 of the 22 non-tied experimental comparisons, corresponding to a gain rate of 95.5%. The exact sign test therefore confirms a highly consistent positive improvement direction across the evaluated schedulers, base models, and benchmarks. This cross-setting consistency is particularly valuable because it shows that the benefit of our method generalizes across different integration strategies and experimental conditions rather than depending on a single favorable configuration.

D. Cross-Domain Generalization to Code Base Model

Methods

Qwen2.5-Coder-7B Instruct

VIP PCL MoPPS Ours

Full Steps MAE (↓) r (↑) 0.197 0.504 0.402 0.307 0.224 0.773 0.176 0.845

Table 5: Difficulty-estimation performance on code generation using Qwen2.5-Coder-7B-Instruct. MAE is samplelevel, and r is the batch-level Pearson correlation.

Setting Many existing adaptive RL scheduling methods are developed and evaluated primarily for mathematical reasoning. Extending them to code generation may require domainspecific modifications to reward definitions, sampling strategies, or hyperparameters. Reimplementing these adaptations

may result in unequal levels of optimization across baselines and compromise the fairness of the comparison. Therefore, rather than reproducing all scheduling baselines in the code domain, we examine whether our difficulty estimator can be directly transferred to code generation and track changes in sample difficulty during RL training. We conduct RL training on LiveCodeBench (Jain et al. 2024) release_v2, which contains 511 programming problems, using Qwen2.5-Coder-7B-Instruct. LiveCodeBench collects problems from LeetCode, AtCoder, and Codeforces and provides platform-derived difficulty ratings and executable test cases (Jain et al. 2024). A generated program is considered correct only if it passes all corresponding test cases. Consistent with the main experiments, we generate eight rollouts for each selected sample and use the proportion of correct programs as its empirical success rate. We then replay the estimation process over the complete training trajectory. Before each training step, the estimator predicts sample success probabilities using only rollout feedback available from previous steps, and these predictions are compared with the subsequently observed outcomes.

Results As shown in Table 5, our method consistently tracks the evolving success probabilities of training samples throughout the RL trajectory of Qwen2.5-Coder-7B-Instruct. This result indicates that the proposed estimator does not depend on the exact-match reward commonly used in mathematical reasoning tasks. When the feedback is replaced by program correctness determined through test-case execution, the sample graph and historical rollout outcomes still provide effective information for estimating dynamic sample difficulty. Overall, the experiment provides preliminary evidence that our estimator can be transferred to execution-based code generation without modifications specific to the code domain.

Discussion The practical need for our estimator may be weaker in code generation. Some competitive-programming benchmarks provide platform difficulty ratings and execution feedback, which may already suffice for curriculum learning or rollout allocation in certain settings. This may partly explain the stronger focus of related studies on mathematics. Thus, this experiment establishes transferability rather than a clear advantage in code generation.

E. Hyper Parameter Analysis Guideline of K, kknn and β We discuss three hyperparameters controlling our difficulty estimator. K is the number of latent difficulty states, determining modeling granularity; knn is the neighborhood size for graph construction, controlling feedback propagation range; β is the Potts prior strength, balancing graph smoothing against adaptation to policy changes. Firstly, we analyze the influence of hyperparameters β and K on difficulty estimation, as shown in Table 6, where MAE

is sample-level and r is the batch-level Pearson correlation. When β increases from 2 to 5 or above, all metrics become nearly identical and slightly worse, indicating that an overstrong Potts prior makes the model rely too heavily on neighbor information and neglect the global difficulty structure. In contrast, a smaller K slightly improves the overall correlation r, suggesting that fewer latent states better capture the global difficulty trend, but the sample-level MAE increases, degrading per-sample accuracy. Considering this trade-off, we choose β = 2 and K = 320 in the main experiments. β

K

2 2 2 2 1 5 10 20

320 160 80 40 320 320 320 320

Early Steps r (↑) MAE (↓) 0.482 0.290 0.480 0.306 0.494 0.313 0.507 0.327 0.488 0.302 0.494 0.297 0.490 0.297 0.493 0.298

Full Steps r (↑) MAE (↓) 0.836 0.183 0.838 0.191 0.843 0.194 0.848 0.196 0.849 0.189 0.847 0.186 0.847 0.186 0.847 0.187

Table 6: Sensitivity analysis of β and K on Qwen-2.5-Math1.5B. MAE is sample-level, and r is batch-level Pearson correlation. The neighborhood size knn determines the initial connectivity of the difficulty-aware sample graph, and thereby controls how far rollout feedback can propagate across samples. Experiments show that as long as knn is not set extremely small (e.g., below 10), the estimation accuracy is barely affected: after reciprocal-neighbor and positive-similarity filtering, the graph itself is already sufficiently sparse, so a small number of neighbors suffices for effective feedback propagation. Meanwhile, the ablation study shows that removing graph sparsification leads to only a modest performance drop, indicating that excessively increasing the neighborhood size brings no additional benefit. From a computational perspective, increasing knn raises the cost of message propagation on the graph—in each variational inference iteration, updating the latent-state distribution of each sample requires aggregating information from its neighbors, giving a theoretical complexity of O(N knn ). However, due to random memory access on sparse graphs and edge saturation caused by positive-similarity filtering, the actual wall-clock time does not grow linearly with knn 3 .

Discussion of Embedding Models and Difficulty-Aware Instruction Models Selection We compare several recent textembedding models that support task-aware or instruction3

Theoretically, the complexity grows linearly with knn , but in practice, graph sparsity leads to random memory access, and positive-similarity filtering gradually saturates the actual edge count, so the time does not increase linearly even if knn is increased. In our setting, the wall-clock time when the edge count saturates is about 1.61× that of the proposed method in the main text.

conditioned embedding, including Qwen3-Embedding0.6B, Qwen3-Embedding-4B (Zhang et al. 2025), and BGEM3 (Chen et al. 2024). When their standard dense representations are used to construct the sample graph, the resulting performance is broadly similar (see Table 7), suggesting that our framework is not sensitive to the exact choice among recent embedding models. Among the direct, uncompressed configurations, Qwen3-Embedding-0.6B performs on par with the larger Qwen3-Embedding-4B and BGE-M3 on Qwen-2.5-Math-1.5B (0.183 vs. 0.188 vs. 0.188 MAE), while on Llama-3.2-1B-Instruct it is slightly worse than Qwen3-Embedding-4B (0.131 vs. 0.130). Given that Qwen3Embedding-0.6B is substantially more efficient, we adopt it as the default encoder as a trade-off between accuracy and computational cost. Model scale and raw embedding dimensionality do not exhibit a monotonic relationship with downstream performance. In particular, compressing the Qwen3-Embedding4B output to 1,024 dimensions using its Matryoshkacompatible representation (Kusupati et al. 2022) improves its performance relative to using the full-dimensional representation (0.179 vs. 0.188 MAE on Qwen; 0.121 vs. 0.130 on Llama, as shown in Table 7). Notably, the MRL-compressed Qwen3-Embedding-4B at 1,024 dimensions achieves the best overall results on both base models (0.179/0.844 for Qwen and 0.121/0.787 for Llama), suggesting that a larger encoder combined with dimensionality reduction can further improve graph quality if the additional computational cost is acceptable. Nevertheless, for the main experiments we prioritize low overhead and therefore use Qwen3-Embedding-0.6B as the default. A plausible explanation for the benefit of MRL compression is the curse of dimensionality: in an excessively high-dimensional space, pairwise distances can become less discriminative, which may make nearest-neighbor selection noisier and weaken the local graph structure. Matryoshka Representation Learning (MRL) preserves information at nested dimensionalities, allowing the representation to be shortened without applying an arbitrary post-hoc projection. Our observation is consistent with this explanation, although it does not by itself establish dimensionality as the sole causal factor. In contrast, replacing the recent instruction-aware encoders with earlier Sentence-BERT-family models (Reimers and Gurevych 2019), or with the encoder configuration adopted by VIP (Nguyen et al. 2026a), causes a substantial performance drop. These older representations were primarily optimized for general sentence-level similarity and appear less suitable for capturing the task-specific semantic, reasoning, and difficulty cues required by our graph. Based on these results, we recommend pairing our method with a recent task-aware embedding model. Qwen3-Embedding-0.6B provides a strong default efficiency–performance trade-off, while a larger MRL-compatible encoder truncated to a moderate dimension is a viable alternative. Discussion of Difficulty-Aware Instruction Table 7 shows that removing the difficulty-aware instruction from Qwen3-Embedding-0.6B causes a substantial degradation

Base Model

Qwen-2.5 Math-1.5B

Llama-3.2 1B-Instruct

Methods Qwen3-Embedding-0.6B -Difficulty-Aware Instruction Qwen3-Embedding-4B Qwen3-Embedding-4B MRL(1024 dimensions) BGE-M3 MiniLM Qwen3-Embedding-0.6B -Difficulty-Aware Instruction Qwen3-Embedding-4B Qwen3-Embedding-4B MRL(1024 dimensions) BGE-M3 MiniLM

Full Steps MAE (↓) r (↑) 0.183 0.836 0.309 0.583 0.188 0.827 0.179

0.844

0.188 0.326 0.131 0.302 0.130

0.823 0.407 0.776 0.486 0.749

0.121

0.787

0.139 0.304

0.783 0.407

Table 7: Full-trajectory difficulty-estimation performance of different embedding configurations. The row “-DifficultyAware 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).

in estimation quality. On Qwen-2.5-Math-1.5B, the MAE increases from 0.183 to 0.309 and the correlation drops from 0.836 to 0.583; on Llama-3.2-1B-Instruct, the MAE increases from 0.131 to 0.302 and the correlation drops from 0.776 to 0.486. This confirms that the instruction, which encourages the encoder to capture difficulty-related and reasoning-oriented features beyond pure surface semantics, contributes critically to the graph quality. Without it, the embeddings tend to connect samples that are semantically similar but not necessarily informative for difficulty transfer. The comparison between Qwen3-Embedding-4B and its MRL-truncated 1,024-dimension variant also suggests that reducing dimensionality, when done through a representation-learning-compatible method, can improve the discriminability of nearest-neighbor structure. BGE-M3 achieves comparable performance to the Qwen3 variants, while MiniLM performs poorly, which is consistent with the above observation that older generic encoders lack the taskawareness needed for constructing a difficulty-aware graph.

Discussion of the Interpolation Weight γ For samples with prior rollouts, we combine the graphbased prediction and the sample-level empirical success rate asb pi,t = γ pbmodel + (1 − γ)r̄i,<t The parameter γ controls i,t the balance between transferable graph-based evidence and direct sample-level history. A small γ makes the estimate dominated by (r̄i,<t , which weakens graph propagation and can hurt difficulty ranking. A large γ relies more on the latent-state model and may ignore reliable direct observations, leading to larger estimation error. We set γ = 0.5 as a general default. In our experiments, performance is relatively stable for γ ∈ [0.5, 0.8]. When γ < 0.5, ranking quality tends to decrease; when γ > 0.8, samplelevel estimation error usually increases. This suggests that a moderate interpolation weight is preferable.

A more principled choice would adapt γ according to uncertainty. The uncertainty of latent state (k) can be estimated from the variance of its Beta posterior: ak,t−1 bk,t−1 vk,t−1 = . (ak,t−1 + bk,t−1 )2 (ak,t−1 + bk,t−1 + 1) Combined with assignment uncertainty, this gives K h X
2 i u bi,t = . qik,t−1 vk,t−1 + µk,t−1 − pbmodel i,t k=1

In principle, one could increase γ when the model-based prediction is confident, and decrease it when the sample has sufficient direct observations. However, such a rule also depends on rollout counts, sampling distributions, and the downstream scheduler. These factors vary across integrated frameworks and are hard to fix with limited experiments. We therefore use a fixed γ = 0.5.

F. Discussion of Spectral Clusters Association with Subject Categories For each analyzed MATH problem i, let zi ∈ {1, . . . , K+ } denote its nonempty spectral-cluster assignment and let ci ∈ {1, . . . , U } denote its subject category. We form the K+ × U contingency table n X I(zi = k, ci = u), (47) Oku = i=1

with row totals Ok· , column totals O·u , and total sample size n. Under the null hypothesis that cluster assignment and subject category are independent, the expected count in cell (k, u) is Ok· O·u Eku = . (48) n We measure departure from independence using Pearson’s chi-squared statistic (Pearson 1900), 2

χ =

K+ U X X (Oku − Eku )2 k=1 u=1

Eku

,

(49)

whose asymptotic null distribution has (K+ − 1)(U − 1) degrees of freedom. Applying this calculation to the MATH training split gives n = 7,500, K+ = 16, and U = 7; thus, the contingency table contains 16 × 7 cells and the asymptotic reference distribution has 90 degrees of freedom. The resulting statistic is χ2 = 10,995.84, with asymptotic p < 10−300 , rejecting independence. Because the chi-squared statistic increases with sample size, we additionally report Cramér’s V , a normalized effectsize measure for categorical association (Cramér 1946): s χ2 . (50) V = n min(K+ − 1, U − 1) The resulting V = 0.494 indicates a substantial association between the spectral clusters and the annotated mathematical subjects. This effect-size analysis complements the hypothesis test: the p-value establishes that the association is unlikely under independence, whereas V quantifies its magnitude.

Difficulty Differences Within Subject Categories Subject category and cluster assignment are strongly associated, so a single pooled comparison could confound subject composition with difficulty. We therefore conduct seven separate Kruskal–Wallis tests, one within each MATH subject category (Kruskal and Wallis 1952). This stratification asks whether the annotated difficulty levels differ across spectral clusters among problems from the same subject. For subject u, let nu be its number of problems and nku the number assigned to nonempty cluster k. We rank the ordinal difficulty levels of all nu problems within that subject, assigning midranks to ties. Let Rku be the sum of ranks in cluster k. The uncorrected Kruskal–Wallis statistic is X R2 12 ku Hu(0) = − 3(nu + 1). (51) nu (nu + 1) nku k:nku >0

Because MATH difficulty takes only five ordinal levels, ties are frequent. Let tug be the size of the g-th tied group within subject u. We apply the standard ties correction P 3 (0) Hu g (tug − tug ) Cu = 1 − , H = . (52) u n3u − nu Cu If Ku clusters are nonempty within subject u, the raw asymptotic p-value is computed from a chi-squared reference distribution with Ku − 1 degrees of freedom:
pu = Pr χ2Ku −1 ≥ Hu . (53) The seven raw p-values form one family of hypotheses. We therefore apply the Benjamini–Hochberg procedure to control the false discovery rate (Benjamini and Hochberg 1995). After sorting the raw values as p(1) ≤ · · · ≤ p(m) , where m = 7, the monotone adjusted values are   m pe(r) = min 1, min p(j) . (54) j≥r j

G. Windowed Memory under Non-stationary Policies Windowed Forgetting Mechanism The online inference procedure described in the main text accumulates rollout feedback across training steps by inheriting the state-level Beta posterior, i.e., ahist k,t = ak,t−1 and bhist = b . However, the rollout distribution is k,t−1 k,t non-stationary because the policy parameters continuously change during RL optimization. Consequently, rollout observations collected many training steps earlier may no longer accurately characterize the success probability of the current policy. To reduce the influence of such outdated observations while remaining responsive to the current policy, we introduce a windowed forgetting mechanism. The windowed variant preserves the difficulty-aware sample graph W , the smoothed assignment prior A, the Potts graph prior, and the mean-field variational family introduced in the main method. It only changes how historical rollout evidence is organized: state-level success probabilities are estimated from a recent sliding window, whereas the complete rollout history of each previously observed sample is retained for sample-level prediction. Windowed State-Level Statistics. Before predicting training step t, we define the preceding window of length L ≥ 1 as (L)

Tt

= {τ : max(1, t − L) ≤ τ < t} ,

(55)

where L denotes the window length and is distinguished from the graph adjacency matrix W . For latent state k, the responsibility-weighted numbers of successful and unsuccessful rollouts within this window are X X (L) qik,τ si,τ , (56) Sk,t = (L) i∈Oτ

τ ∈Tt

and Subject Algebra Prealgebra Precalculus Intermediate algebra Counting/probability Number theory Geometry

Raw p ≈0 ≈0 ≈0 2.0 × 10−6 8.0 × 10−6 3.19 × 10−4 4.31 × 10−3

BH-adjusted p ≈0 ≈0 1.0 × 10−6 3.0 × 10−6 1.1 × 10−5 3.72 × 10−4 4.31 × 10−3

(L)

Fk,t =

X

X

All seven subject-specific null hypotheses remain rejected after BH correction, with peu ≤ 4.31×10−3 . Therefore, cluster membership is associated with annotated difficulty even among problems from the same subject category. Together with the cluster–subject association, this result supports the interpretation that the spectral initialization captures both semantic and difficulty-related structure.

(57)

Rather than directly inheriting the complete Beta posterior from the previous step, the windowed variant reconstructs the state-level Beta parameters from a fixed prior and the rollout evidence within the current window: (L)

(L)

ak,t = a0 + Sk,t , 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.

qik,τ (ni,τ − si,τ ) .

(L) i∈Oτ

τ ∈Tt

(L)

(L)

bk,t = b0 + Fk,t .

(58)

In our implementation, we set a0 = b0 = 1, corresponding to the uniform prior Beta(1, 1). This is a standard weak prior for a Bernoulli success probability and does not favor any particular success rate before rollout evidence is observed. It also guarantees that the Beta parameters remain strictly positive. This property is particularly important under a finite window because some latent states may receive no rollout (L) (L) observations in the current window. When Sk,t = Fk,t = 0, the Beta(1, 1) prior still yields a valid posterior and keeps the posterior mean and the digamma terms used in the variational updates well-defined and numerically stable.

Ideally, the prior mean E[θk,t ] =

a0 a0 + b0

(59)

should be close to the average success probability of the current policy. Such a prior would provide a more informative default estimate for latent states with few or no recent observations. However, obtaining a reliable estimate of the current policy’s average ability would require evaluating a sufficiently large and representative subset of the training set at each stage, which would introduce substantial additional rollout cost. Estimating it only from the samples selected by the scheduler would also be potentially biased, because the selected samples are generally not representative of the full training distribution. We therefore adopt Beta(1, 1) as a practical trade-off among prior neutrality, numerical stability, and computational efficiency. The posterior mean success probability of latent state k is then (L)

(L) µk,t =

ak,t (L)

(L)

.

(60)

ak,t + bk,t

The model-based prediction for sample xi retains the same mixture form as in the main method: pbmodel = i,t

K X

(L)

qik,t µk,t .

When the window covers all preceding training steps, the windowed formulation reduces to the cumulative-history variant. With a finite L, rollout observations older than L training steps no longer directly contribute to the current state-level success probabilities. Windowed Variational Updates. The windowed variant retains the mean-field factorization N Y

qi (zi,t )

i=1

K Y

q(θk,t ),

(62)

k=1

where qik,t ≡ qi (zi,t = k) and   (L) (L) q(θk,t ) = Beta ak,t , bk,t .

(63)

The coordinate update for the latent-state assignments preserves the same three sources of (r+1) informationh as the main method: qik  =i PN (r) (L) (L) Softmaxk log Aik + β j=1 Wij qjk + I i ∈ Ot ℓik,t , where [ (L) Ot = Oτ . (64) (L)

τ ∈Tt

For each sample i, we aggregate its rollout outcomes within the current window as X X (L) (L) si,t = si,τ , ni,t = ni,τ , (65) (L)

τ ∈Tt

(L) i∈Oτ

τ ∈Tt

and (L)

X

bk,t = 1 +

(L)

τ ∈Tt

X

qik (ni,τ − si,τ ) .

(67)

(L) i∈Oτ τ ∈Tt

We alternate the assignment and Beta-factor updates using the same stopping criterion as in the main method. Therefore, the windowed variant does not change the coordinate-ascent structure of the inference procedure; it only restricts the temporal support of the rollout evidence used in the likelihood and state-level Beta updates. Persistent Assignment Warm Start. In the cumulative formulation, the complete estimator state St = {qt , at , bt } is passed between consecutive training steps. In the windowed variant, we retain only the previous assignment probabilities as the default initialization: (0)

(61)

k=1

qt (zt , θ t ) ≈

and compute the corresponding log-likelihood h   expected  i (L) (L) (L) (L) (L) as ℓik,t = si,t ψ ak,t − ψ ak,t + bk,t + h    i  (L) (L) (L) (L) (L) ni,t − si,t ψ bk,t − ψ ak,t + bk,t . After updating the assignment probabilities, the state-level Beta factors are recomputed using only the rollout observations within the current window: X X (L) qik si,τ , (66) ak,t = 1 +

qik,t = qik,t−1 .

(68)

The Beta parameters are not directly inherited from the previous step. Instead, they are reconstructed from the fixed Beta(1, 1) prior and the rollout observations within the current window. The persistent initialization of q preserves continuity in the graph-structured latent assignments and provides a warm start for the finite-iteration variational procedure. Importantly, the inherited responsibilities are used only as an optimization initialization. They are not treated as additional successes or failures and therefore do not alter the strict temporal window applied to the state-level sufficient statistics. We additionally consider a reset variant that initializes q from the static soft assignment prior A at every step; unless otherwise specified, the persistent warm-start variant is used by default. Persistent Sample-Level History. The sliding window is applied only to the shared state-level statistics. For each sample xi , we separately retain its complete rollout history before step t: X X all all Si,t = si,τ , Ci,t = ni,τ . (69) τ <t

τ <t

For a previously observed sample, its historical empirical success rate is all Si,t ri,<t = all . (70) Ci,t We then retain the prediction rule from the main method: ( all pbmodel , Ci,t = 0, i,t pbi,t = (71) model all γ pbi,t + (1 − γ)ri,<t , Ci,t > 0.

Consequently, the two components of the final prediction operate at complementary time scales. The model-based term uses recent rollout feedback to track the evolving success probabilities of the shared latent states, whereas the samplelevel empirical term preserves all available direct evidence for each previously observed sample. The windowed mechanism therefore removes stale evidence from transferable state-level statistics without discarding the long-term historical experience associated with individual samples.

Result and Discussion Base Model

Methods

Qwen-2.5 Math-1.5B Llama-3.2 1B-Instruct

Ours Windows Ours Windows

Full Steps MAE (↓) r (↑) 0.183 0.836 0.127 0.712 0.131 0.776 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 Qwen2.5-Math-1.5B and Llama-3.2-1B-Instruct. We evaluate the windowed variant by replaying the full training logs of Qwen-2.5-Math-1.5B and Llama-3.2-1BInstruct, and compare it with the cumulative estimator used in our main experiments. As shown in Table 9, the windowed variant achieves lower sample-level MAE on both models: 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. This indicates that windowed forgetting makes the predicted success probability of each individual sample numerically closer to its reference rollout outcome. Fig. 3 further visualizes the batch-level reference accuracy and predicted accuracy over the full training process. However, Table 9 also shows that the correlation metric r decreases after introducing the windowed mechanism: 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. This suggests a tradeoff: although the windowed estimator improves point-wise numerical accuracy, it weakens the ability to preserve the relative difficulty structure among samples. A likely reason is that the finite window reduces the amount of historical evidence available for state-level estimation, making the estimates more sensitive to sparse recent observations and sampling bias. For our difficulty-aware scheduling setting, stable relative ordering is more important than point-wise calibration alone. Therefore, we retain the cumulative estimator as the default method in the main experiments. Whether to use windowed forgetting should depend on the downstream objective: it is beneficial when current-policy calibration is prioritized, but less suitable when stable sample ranking is critical.

H. Related work of Graph-Based Learning and Probabilistic Inference Graph-based clustering and semi-supervised learning assume that nearby points on a data manifold tend to have compatible latent structure. Spectral methods partition a similarity graph through its eigensystem (Ng, Jordan, and Weiss 2001; Von Luxburg 2007), while Gaussian-field propagation, local-and-global consistency, and manifold regularization diffuse sparse supervision according to graph geometry (Zhu, Ghahramani, and Lafferty 2003; Zhou et al. 2003; Belkin, Niyogi, and Sindhwani 2006). These methods motivate transferring evidence from observed prompts to related but unobserved ones. Probabilistic graphical models additionally represent relational dependence and uncertainty. Potts and Markov random-field priors encourage neighboring discrete variables to take compatible states (Potts 1952; Besag 1974; Geman and Geman 1984). Because graph coupling makes exact posterior inference difficult, variational methods optimize a tractable approximation, with mean-field factorizations yielding scalable coordinate updates (Zhang 1992; McGrory et al. 2009; Wainwright and Jordan 2008; Blei, Kucukelbir, and McAuliffe 2017). Stochastic and streaming variants update approximate posteriors as new observations arrive (Hoffman et al. 2013; Broderick et al. 2013).

References Bae, S.; Hong, J.; Lee, M. Y.; Kim, H.; Nam, J.; and Kwak, D. 2026. Online difficulty filtering for reasoning oriented reinforcement learning. In Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), 700–719. Balunovic, M.; Dekoninck, J.; Petrov, I.; Jovanović, N.; and Vechev, M. 2026. Matharena: Evaluating llms on uncontam-

inated math competitions. Advances in Neural Information Processing Systems, 38. Belkin, M.; Niyogi, P.; and Sindhwani, V. 2006. Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples. Journal of Machine Learning Research, 7(85): 2399–2434. Bengio, Y.; Louradour, J.; Collobert, R.; and Weston, J. 2009. Curriculum Learning. In International Conference on Machine Learning, 41–48. Benjamini, Y.; and Hochberg, Y. 1995. Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing. Journal of the Royal Statistical Society: Series B (Methodological), 57(1): 289–300. Besag, J. 1974. Spatial interaction and the statistical analysis of lattice systems. Journal of the Royal Statistical Society: Series B (Methodological), 36(2): 192–225. Blei, D. M.; Kucukelbir, A.; and McAuliffe, J. D. 2017. Variational Inference: A Review for Statisticians. Journal of the American Statistical Association, 112(518): 859–877. Broderick, T.; Boyd, N.; Wibisono, A.; Wilson, A.; and Jordan, M. 2013. Streaming Variational Bayes. In Burges, C.; Bottou, L.; Welling, M.; Ghahramani, Z.; and Weinberger, K., eds., Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc. Chen, J.; Xiao, S.; Zhang, P.; Luo, K.; Lian, D.; and Liu, Z. 2024. BGE M3-Embedding: Multi-Lingual, MultiFunctionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation. arXiv:2402.03216. Cramér, H. 1946. Mathematical Methods of Statistics. Princeton, NJ: Princeton University Press. Cui, G.; Yuan, L.; Wang, Z.; Wang, H.; Zhang, Y.; Chen, J.; Li, W.; He, B.; Fan, Y.; Yu, T.; et al. 2025. Process reinforcement through implicit rewards. arXiv preprint arXiv:2502.01456. Dekoninck, J.; Jovanović, N.; Gehrunger, T.; Rögnvaldsson, K.; Petrov, I.; Sun, C.; and Vechev, M. 2026. Beyond benchmarks: Matharena as an evaluation platform for mathematics with llms. arXiv preprint arXiv:2605.00674. Dixon, W. J.; and Mood, A. M. 1946. The Statistical Sign Test. Journal of the American Statistical Association, 41(236): 557–566. Fang, Y.; Lin, J.; Fu, X.; Qin, C.; Shi, H.; Hu, C.; Pan, L.; Zeng, K.; and Cai, X. 2026. How to allocate, how to learn? dynamic rollout allocation and advantage modulation for policy optimization. In Findings of the Association for Computational Linguistics: ACL 2026, 14727–14744. Gao, Z.; Kim, J.; Sun, W.; Joachims, T.; Wang, S.; Pang, R. Y.; and Tan, L. 2026. Prompt Curriculum Learning for Efficient LLM Post-Training. In The Fourteenth International Conference on Learning Representations. Geman, S.; and Geman, D. 1984. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, (6): 721–741. Grattafiori, A.; Dubey, A.; Jauhri, A.; Pandey, A.; Kadian, A.; Al-Dahle, A.; Letman, A.; Mathur, A.; Schelten, A.;

Vaughan, A.; Yang, A.; Fan, A.; Goyal, A.; Hartshorn, A.; Yang, A.; et al. 2024. The Llama 3 Herd of Models. arXiv:2407.21783. Guo, D.; Yang, D.; Zhang, H.; Song, J.; Wang, P.; Zhu, Q.; Xu, R.; Zhang, R.; Ma, S.; Bi, X.; et al. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. He, C.; Luo, R.; Bai, Y.; Hu, S.; Thai, Z.; Shen, J.; Hu, J.; Han, X.; Huang, Y.; Zhang, Y.; et al. 2024. Olympiadbench: A challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 3828–3850. Hendrycks, D.; Burns, C.; Kadavath, S.; Arora, A.; Basart, S.; Tang, E.; Song, D.; and Steinhardt, J. 2021. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874. Hoffman, M. D.; Blei, D. M.; Wang, C.; and Paisley, J. 2013. Stochastic variational inference. Journal of machine learning research. Jain, N.; Han, K.; Gu, A.; Li, W.-D.; Yan, F.; Zhang, T.; Wang, S.; Solar-Lezama, A.; Sen, K.; and Stoica, I. 2024. LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code. arXiv preprint arXiv:2403.07974. Kong, D.; Guo, Q.; Xi, X.; Wang, W.; Wang, J.; Cai, X.; Zhang, S.; and Ye, W. 2026. Rethinking the sampling criteria in reinforcement learning for LLM reasoning: A competencedifficulty alignment perspective. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, 31438– 31446. Kruskal, W. H.; and Wallis, W. A. 1952. Use of Ranks in One-Criterion Variance Analysis. Journal of the American Statistical Association, 47(260): 583–621. Kusupati, A.; Bhatt, G.; Rege, A.; Wallingford, M.; Sinha, A.; Ramanujan, V.; Howard-Snyder, W.; Chen, K.; Kakade, S.; Jain, P.; and Farhadi, A. 2022. Matryoshka Representation Learning. In Advances in Neural Information Processing Systems, volume 35. Lalor, J. P.; Wu, H.; and Yu, H. 2016. Building an Evaluation Scale using Item Response Theory. In Su, J.; Duh, K.; and Carreras, X., eds., Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, 648– 657. Austin, Texas: Association for Computational Linguistics. Li, J.; Beeching, E.; Tunstall, L.; Lipkin, B.; Soletskyi, R.; Huang, S.; Rasul, K.; Yu, L.; Jiang, A. Q.; Shen, Z.; et al. 2024. Numinamath: The largest public dataset in ai4maths with 860k pairs of competition math problems and solutions. Hugging Face repository, 13(9): 9. Lightman, H.; Kosaraju, V.; Burda, Y.; Edwards, H.; Baker, B.; Lee, T.; Leike, J.; Schulman, J.; Sutskever, I.; and Cobbe, K. 2024. Let’s verify step by step. In International Conference on Learning Representations, volume 2024, 39578–39601.

McGrory, C. A.; Titterington, D. M.; Reeves, R.; and Pettitt, A. N. 2009. Variational Bayes for estimating the parameters of a hidden Potts model. Statistics and Computing, 19(3): 329–340. Mindermann, S.; Brauner, J. M.; Razzak, M. T.; Sharma, M.; Kirsch, A.; Xu, W.; Höltgen, B.; Gomez, A. N.; Morisot, A.; Farquhar, S.; and Gal, Y. 2022. Prioritized Training on Points that are Learnable, Worth Learning, and not yet Learnt. In Chaudhuri, K.; Jegelka, S.; Song, L.; Szepesvari, C.; Niu, G.; and Sabato, S., eds., Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, 15630– 15649. PMLR. Ng, A.; Jordan, M.; and Weiss, Y. 2001. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14. Nguyen, H. T.; Nguyen, B.; Ma, W.; Zhao, Y.; She, R.; and Nguyen, V. A. 2026a. Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards. In The Fourteenth International Conference on Learning Representations. Nguyen, M.; Venkatesh, S.; Le, H.; et al. 2026b. SPaCe: Unlocking Sample-Efficient Large Language Models Training With Self-Pace Curriculum Learning. In Findings of the Association for Computational Linguistics: ACL 2026, 3480–3507. Pearson, K. 1900. On the Criterion That a Given System of Deviations from the Probable in the Case of a Correlated System of Variables Is Such That It Can Be Reasonably Supposed to Have Arisen from Random Sampling. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 50(302): 157–175. Potts, R. B. 1952. Some generalized order-disorder transformations. In Mathematical proceedings of the cambridge philosophical society, volume 48, 106–109. Cambridge University Press. Qu, Y.; Wang, Q.; Mao, Y.; Hu, V. T.; Ommer, B.; and Ji, X. 2026. Can prompt difficulty be online predicted for accelerating rl finetuning of reasoning models? In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1, 1240–1250. Reimers, N.; and Gurevych, I. 2019. Sentence-BERT: Sentence Embeddings Using Siamese BERT-Networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, 3982– 3992. Association for Computational Linguistics. Rodriguez, P.; Barrow, J.; Hoyle, A.; Lalor, J. P.; Jia, R.; and Boyd-Graber, J. 2021. Evaluation Examples are not Equally Informative: How should that change NLP Leaderboards? In Zong, C.; Xia, F.; Li, W.; and Navigli, R., eds., Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), 4486–4503. Online: Association for Computational Linguistics.

Shao, Z.; Wang, P.; Zhu, Q.; Xu, R.; Song, J.; Bi, X.; Zhang, H.; Zhang, M.; Li, Y.; Wu, Y.; et al. 2024. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Sheng, G.; Zhang, C.; Ye, Z.; Wu, X.; Zhang, W.; Zhang, R.; Peng, Y.; Lin, H.; and Wu, C. 2024. HybridFlow: A Flexible and Efficient RLHF Framework. arXiv preprint arXiv: 2409.19256. Swayamdipta, S.; Schwartz, R.; Lourie, N.; Wang, Y.; Hajishirzi, H.; Smith, N. A.; and Choi, Y. 2020. Dataset Cartography: Mapping and Diagnosing Datasets with Training Dynamics. In Webber, B.; Cohn, T.; He, Y.; and Liu, Y., eds., Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 9275–9293. Online: Association for Computational Linguistics. Team, K.; Du, A.; Gao, B.; Xing, B.; Jiang, C.; Chen, C.; Li, C.; Xiao, C.; Du, C.; Liao, C.; et al. 2025. Kimi k1. 5: Scaling reinforcement learning with llms. arXiv preprint arXiv:2501.12599. Von Luxburg, U. 2007. A tutorial on spectral clustering. Statistics and computing, 17(4): 395–416. Wainwright, M. J.; and Jordan, M. I. 2008. Graphical models, exponential families, and variational inference. Foundations and Trends® in Machine Learning, 1(1-2): 1–305. Wang, H.; Hao, Z.; Luo, J.; Wei, C.; Shu, Y.; Liu, L.; Cheaterlin; Dong, H.; and Chen, J. 2026. Scheduling Your LLM Reinforcement Learning with Reasoning Trees. In The Fourteenth International Conference on Learning Representations. Wu, M.; Zhang, Z.; Dong, Q.; Xi, Z.; Zhao, J.; Jin, S.; Fan, X.; Zhou, Y.; Lv, H.; Zhang, M.; et al. 2026. Reasoning or memorization? unreliable results of reinforcement learning due to data contamination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, 33944– 33952. Xiong, W.; Ye, C.; Liao, B.; Dong, H.; Xu, X.; Monz, C.; Bian, J.; Jiang, N.; and Zhang, T. 2025. Reinforce-ada: An adaptive sampling framework for reinforce-style llm training. arXiv e-prints, arXiv–2510. Xu, H.; Chen, S.; Qiu, R.; Yan, Y.; Luo, C.; Cheng, M.; He, J.; and Tong, H. 2026. Prune as You Generate: Online Rollout Pruning for Faster and Better RLVR. arXiv:2603.24840. Yang, A.; Zhang, B.; Hui, B.; Gao, B.; Yu, B.; Li, C.; Liu, D.; Tu, J.; Zhou, J.; Lin, J.; Lu, K.; Xue, M.; Lin, R.; Liu, T.; Ren, X.; and Zhang, Z. 2024. Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement. arXiv:2409.12122. Yao, J.; Hao, Y.; Zhang, H.; Dong, H.; Xiong, W.; Jiang, N.; and Zhang, T. 2026. Optimizing chain-of-thought reasoners via gradient variance minimization in rejection sampling and rl. Advances in Neural Information Processing Systems, 38: 163245–163284. Yu, Q.; Zhang, Z.; Zhu, R.; Yuan, Y.; Zuo, X.; Yue, Y.; Dai, W.; Fan, T.; Liu, G.; Liu, L.; et al. 2026. Dapo: An open-source llm reinforcement learning system at scale. Advances in Neural Information Processing Systems, 38: 113222–113244.

Zeng, Y.; Sun, Z.; Ji, B.; Min, E.; Cai, H.; Wang, S.; Yin, D.; Zhang, H.; Chen, X.; and Wang, J. 2026. CurES: From Gradient Analysis to Efficient Curriculum Learning for Reasoning LLMs. In The Fourteenth International Conference on Learning Representations. Zhang, J. 1992. The mean field theory in EM procedures for Markov random fields. IEEE Transactions on signal processing, 40(10): 2570–2583. Zhang, Y.; Li, M.; Long, D.; Zhang, X.; Lin, H.; Yang, B.; Xie, P.; Yang, A.; Liu, D.; Lin, J.; Huang, F.; and Zhou, J. 2025. Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models. arXiv:2506.05176. Zheng, C.; Liu, S.; Li, M.; Chen, X.-H.; Yu, B.; Gao, C.; Dang, K.; Liu, Y.; Men, R.; Yang, A.; et al. 2025. Group sequence policy optimization. arXiv preprint arXiv:2507.18071. Zheng, H.; Zhou, Y.; Bartoldson, B.; Kailkhura, B.; Lai, F.; Zhao, J.; and Chen, B. 2026. Act only when it pays: Efficient reinforcement learning for llm reasoning via selective rollouts. Advances in Neural Information Processing Systems, 38: 124321–124346. Zhou, D.; Bousquet, O.; Lal, T.; Weston, J.; and Schölkopf, B. 2003. Learning with Local and Global Consistency. In Thrun, S.; Saul, L.; and Schölkopf, B., eds., Advances in Neural Information Processing Systems, volume 16. MIT Press. Zhu, X.; Ghahramani, Z.; and Lafferty, J. D. 2003. Semisupervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), 912–919.

Related documents

• Ising-based Test Optimization and Benchmarking#10443
• VPTwin: Real-Sim-Real Video Prediction for Robotic Manipulation Planning#1117816
• CP-WSP: A Declarative CP-SAT Framework for Configurable Multi-Constraint Workforce Scheduling#343516
• Redistribution-based Cost Inference Improves Sparse Safe Offline RL#447917
• TOUR: A Trajectory-Level Unlearning Benchmark for Offline Reinforcement Learning#394431