Paper deep dive
Efficient RLVR Scheduling via Graph-Structured Online Difficulty Estimation
Zhizhao Liu, Zhiliang Tian, Xi Wang, Zhihua Wen, Yihang Xiong, Zhiquan Lai, Dongsheng Li
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/22/2026, 1:48:44 AM
Summary
The paper proposes a graph-based online difficulty estimation framework for Reinforcement Learning with Verifiable Rewards (RLVR) in large language models. It constructs a difficulty-aware sample graph based on semantic and reasoning similarities, uses a Potts prior to encourage neighboring samples to share latent difficulty states, and employs a Beta-Binomial model with online mean-field variational inference to continuously update these states. This approach mitigates cold start and staleness issues in difficulty estimation without requiring dedicated probing, thereby improving the efficiency of sample selection and rollout allocation schedulers.
Entities (8)
Relation Signals (6)
Graph-based Online Difficulty Estimator → uses → Difficulty-Aware Sample Graph
confidence 95% · Specifically, we first construct a difficulty-aware sample graph based on semantic and reasoning similarities. Based on this graph, we introduce latent difficulty states...
Difficulty-Aware Sample Graph → basedon → semantic and reasoning similarities
confidence 94% · Specifically, we first construct a difficulty-aware sample graph based on semantic and reasoning similarities.
Graph-based Online Difficulty Estimator → uses → Online Mean-Field Variational Inference
confidence 93% · Finally, we use an online mean-field variational algorithm to continuously update the latent-state assignments and state-level difficulty as new feedback arrives.
Graph-based Online Difficulty Estimator → uses → Potts Prior
confidence 92% · we introduce latent difficulty states and use a Potts prior to encourage neighboring samples to share the same state.
Graph-based Online Difficulty Estimator → uses → Beta-Binomial Model
confidence 92% · We then employ a state-level Beta-Binomial model to aggregate the rollout outcomes associated with each state.
Graph-based Online Difficulty Estimator → improves → RLVR
confidence 90% · Our framework can be integrated into sample-selection and rollout-allocation schedulers, enabling difficulty-adaptive exploration... Experiments... demonstrate that our framework achieves better performance.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.17941v1
- Canonical: https://arxiv.org/abs/2608.17941v1
Trouble viewing inline? Open PDF directly →
Full Text
115,748 characters extracted from source content.
Expand or collapse full text
Efficient RLVR Scheduling via Graph-Structured Online Difficulty Estimation Zhizhao Liu Zhiliang Tian Xi Wang Zhihua Wen Yihang Xiong Zhiquan Lai Dongsheng Li 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 (39; 51; 55). 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 (39). These rollouts explore alternative solutions but also incur substantial generation cost (18; 50). However, GRPO commonly assigns the same number of rollouts to every selected sample (39; 50). 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 (32; 50; 52). This budget mismatch motivates difficulty-aware 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 (15; 36; 23). Second, rollout-allocation methods assign different numbers of rollouts to selected samples and determine how much exploration each sample receives (32; 50; 52). 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 (52; 50; 42). Although this approach provides estimation, it incurs substantial computational overhead and introduces statistical uncertainty due to the limited number of stochastic rollouts11 1 An intuitive analogy: tossing a fair coin 4 times still has a 12.5% chance of coming up all heads or all tails.. Further, some researchers estimate these success probabilities from outcomes collected during previous training steps (32; 33; 23; 36). 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? 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 graph-structured 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 Figure 1: The overview of our framework. We first construct a difficulty-aware sample graph (a). During RL training, our graph-structured latent model aggregates rollout feedback across related samples (b), while online mean-field variational inference updates their evolving difficulty (c). The resulting estimates guide adaptive sample selection and rollout allocation (d). Adaptive Sampling and Rollout Allocation in RLVR Curriculum learning order or reweight examples according to difficulty, competence, or learnability (4; 30). This principle is especially relevant to group-based RLVR, where prompts with nearly deterministic group rewards provide little group-relative learning signal (39; 51; 55). Prompt-selection methods therefore use estimated difficulty, competence alignment, uncertainty, or reward dynamics to prioritize informative examples (51; 15; 36; 23; 56; 1). A complementary line allocates non-uniform rollout counts. GVM, VIP, and CurES use gradient-variance or stability objectives (50; 32; 52), whereas recent methods use sequential uncertainty reduction, Bernoulli-variance proxies, or posterior hit utility (47; 14). 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 (26; 38). Training-dynamics methods instead characterize examples through quantities such as confidence and variability across epochs, or prioritize examples that remain learnable and useful (41; 30). RLVR further requires these model-dependent 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 (15). Probing-based methods estimate current success probabilities from additional on-policy generations, obtaining timely but costly and noisy signals (50; 52; 42). History-based methods reuse training feedback: MoPPS performs streaming Bayesian inference (36); CDAS aggregates historical performance discrepancies (23); GRESO exploits temporal regularity in rewards (56); and VIP fits a lightweight predictor to recent rollouts (32). Complementary scheduling methods operate at different granularities: Re-Schedule derives a static structural-learnability score from offline reasoning trees for easy-to-hard curriculum scheduling (45), whereas ARRoL predicts final correctness from partial rollouts and prunes trajectories online to balance binary rewards (48). 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 consists 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 =xii=1ND=\x_i\_i=1^N, where xix_i denotes the i-th sample. Following the actual training order, we let tO_t represent the set of samples for which we generate rollouts at training step t. Under the current policy model πt _t, each sample i∈ti _t generates ni,tn_i,t rollouts, and we denote the binary correctness outcome of the g-th rollout by yi,t,g∈0,1y_i,t,g∈\0,1\. We aggregate the rollout outcomes of the same sample into the number of successful rollouts, si,t=∑g=1ni,tyi,t,gs_i,t= _g=1^n_i,ty_i,t,g, and define its empirical success rate as ri,t=si,t/ni,tr_i,t=s_i,t/n_i,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,<t,<t) p_i,t= _Y _t(Y is correct x_i,s_<t,n_<t). We then define the difficulty of sample i at step t as di,t=1−pi,td_i,t=1-p_i,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π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. Prompt: [SAMPLE] Let fembf_emb denote a pretrained embedding model. The representation of sample xix_i is computed as ϕ~i=femb(Iπ,xi) φ_i=f_emb(I_π,x_i) and normalized to ϕi=ϕ~i/‖ϕ~i‖2 φ_i= φ_i/\| φ_i\|_2. For each pair of samples, we measure their similarity with cosine similarity: cij=ϕi⊤ϕjc_ij= φ_i φ_j. To capture the underlying manifold structure of high-dimensional sample embeddings while reducing computational cost, we construct a k-nearest-neighbor graph by retaining the knnk_n nearest neighbors of each node. We then retain only edges where the two nodes are mutual k-nearest neighbors and remove those with negative similarities, yielding a sparse undirected sample graph W∈ℝN×NW ^N× N. Specifically, Wij=cijW_ij=c_ij if xix_i and xjx_j are mutual k-nearest neighbors and cij>0c_ij>0, and 00 otherwise. A larger WijW_ij reflects greater similarity in semantic content, reasoning structure, and difficulty-related features between xix_i and xjx_j. 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∈ℝN×NW ^N× N, and it yields an initial set of static cluster labels ci∈1,…,Kc_i∈\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 latent states, we define Aik=1−ϵ,k=ci,ϵK−1,k≠ci, A_ik= cases1-ε,&k=c_i,\\ εK-1,&k≠ c_i, cases. This conversion retains the structure from spectral clustering, and it also allows subsequent rollout outcomes to refine each sample’s latent assignment. Then, inspired by 6, we introduce a Potts graph prior (35) over the latent assignments to retain the initial clustering structure while encouraging neighboring samples to share the same latent state. Specifically, we define p(t∣W,A)=1Z(W,A)(∏i=1NAi,zi,t)exp[β2∑i=1N∑j=1NWij(zi,t=zj,t)],p(z_t W,A)= 1Z(W,A) ( _i=1^NA_i,z_i,t ) [ β2 _i=1^N _j=1^NW_ij\,I(z_i,t=z_j,t) ], where t=(z1,t,…,zN,t)z_t=(z_1,t,…,z_N,t) denotes the vector of latent-state assignments at step t, with zi,t∈1,…,Kz_i,t∈\1,…,K\ indicating the assignment for sample xix_i. The hyperparameter β controls the strength of graph propagation, and Z(W,A)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 52 and 36, we model its success probability at step t with a Beta distribution: θk,t∼Beta(ak,thist,bk,thist) _k,t (a_k,t^hist,b_k,t^hist ). 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−1t-1, i.e., ak,thist=ak,t−1a_k,t^hist=a_k,t-1 and bk,thist=bk,t−1b_k,t^hist=b_k,t-1. Both parameters are initialized to 11: ak,0=1a_k,0=1, bk,0=1b_k,0=1. Conditioned on the latent-state assignment zi,t=kz_i,t=k and the conditional independence of rollout outcomes, the number of successes si,ts_i,t out of ni,tn_i,t rollouts follows a binomial distribution: (si,t∣ni,t,zi,t=k,θk,t)∼Binomial(ni,t,θk,t)(s_i,t n_i,t,z_i,t=k, _k,t) (n_i,t, _k,t). Let t=(θ1,t,…,θK,t) θ_t=( _1,t,…, _K,t) collect the success probabilities of all latent states. By combining the graph-structured prior over tz_t, the independent Beta priors over each θk,t _k,t, and the sample-level binomial likelihoods, we obtain the joint distribution at step t: pt(t,t,t∣t,W,A)=p(t∣W,A)∏k=1KBeta(θk,t∣ak,thist,bk,thist)∏i∈tBinomial(si,t∣ni,t,θzi,t,t)p_t(s_t,z_t, θ_t _t,W,A)=\;p(z_t W,A) _k=1^KBeta ( _k,t a_k,t^hist,b_k,t^hist ) _i _tBinomial (s_i,t n_i,t, _z_i,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(t,t∣t,t,W,A)=pt(t,t,t∣t,W,A)pt(t∣t,W,A)=pt(t,t,t∣t,W,A)∑t∫pt(t,t,t∣t,W,A)dtp_t(z_t, θ_t _t,n_t,W,A)= p_t(s_t,z_t, θ_t _t,W,A)p_t(s_t _t,W,A)= p_t(s_t,z_t, θ_t _t,W,A) _z_t p_t(s_t,z_t, θ_t _t,W,A)\,d θ_t. 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 tz_t and state-level success probabilities t θ_t. However, exact posterior inference is intractable. The Potts prior couples the latent states of neighboring samples. This coupling requires a summation over all KNK^N possible assignments. Its computational cost grows exponentially with the number of training samples. To obtain tractable updates, we follow prior work (53; 21) and adopt the mean-field approximation qt(t,t)≈∏i=1Nqi(zi,t)∏k=1Kq(θk,t).q_t(z_t, θ_t)≈ _i=1^Nq_i(z_i,t) _k=1^Kq( _k,t).Here, qi(zi,t)q_i(z_i,t) represents the latent-state distribution of sample i. We denote its state-assignment probability by qik,t≡qi(zi,t=k).q_ik,t≡ q_i(z_i,t=k). We restrict each state-level factor to the Beta family: q(θk,t)=Beta(ak,t,bk,t).q( _k,t)=Beta(a_k,t,b_k,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⋆=argminqt∈KL[qt(t,t)∥,pt(t,t∣t,t,W,A)].q_t = _q_t KL [q_t(z_t, θ_t)\, \|,p_t(z_t, θ_t _t,n_t,W,A) ]. The exact posterior contains the partition function Z(W,A)Z(W,A) of the Potts prior. This makes the KL divergence difficult to evaluate directly. We instead use the evidence lower bound (ELBO): ℒt(qt)=qt[logpt(t,t,t∣t,W,A)]−qt[logqt(t,t)].L_t(q_t)=E_q_t[ p_t(s_t,z_t, θ_t _t,W,A)]-E_q_t[ q_t(z_t, θ_t)]. The log marginal likelihood satisfies logpt(t∣t,W,A)=ℒt(qt)+KL[qt(t,t)∥,pt(t,t∣t,t,W,A)]. p_t(s_t _t,W,A)=L_t(q_t)+KL [q_t(z_t, θ_t)\,\|,p_t(z_t, θ_t _t,n_t,W,A) ]. The left-hand side does not depend on qtq_t. Thus, minimizing the KL divergence is equivalent to maximizing the ELBO: qt⋆=argmaxqt∈ℒt(qt).q_t = _q_t L_t(q_t). We can evaluate the ELBO under the mean-field approximation. In particular, the expected Potts interaction becomes qt[(zi,t=zj,t)]=∑k=1Kqik,tqjk,t.E_q_t [I(z_i,t=z_j,t) ]= _k=1^Kq_ik,tq_jk,t. Substituting this result and the variational factors into the ELBO gives ℒt(q) _t(q) =(β/2)∑i=1N∑j=1NWij∑k=1Kqik,tqjk,t =(β/2) _i=1^N _j=1^NW_ij _k=1^Kq_ik,tq_jk,t +∑i=1N∑k=1Kqik,tlogAik−∑i=1N∑k=1Kqik,tlogqik,t + _i=1^N _k=1^Kq_ik,t A_ik- _i=1^N _k=1^Kq_ik,t q_ik,t +∑i∈t∑k=1Kqik,tsi,t[ψ(ak,t)−ψ(ak,t+bk,t)] + _i _t _k=1^Kq_ik,t \s_i,t[ψ(a_k,t)-ψ(a_k,t+b_k,t)] +(ni,t−si,t)[ψ(bk,t)−ψ(ak,t+bk,t)] +(n_i,t-s_i,t)[ψ(b_k,t)-ψ(a_k,t+b_k,t)] \ −∑k=1KKL[Beta(ak,t,bk,t)∥Beta(ak,thist,bk,thist)]. - _k=1^KKL[Beta(a_k,t,b_k,t)\|Beta(a_k,t^hist,b_k,t^hist)]. We omit terms independent of qtq_t. 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,tq_ik,t. The second contains the Beta parameters (ak,t,bk,t)(a_k,t,b_k,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)q( θ_t) and all qj(zj,t)q_j(z_j,t) for j≠ij≠ i. The coordinate-optimal update is qik,t⋆=Softmaxk[logAik+β∑j=1NWijqjk,t+i∈t)ℓik,tVB],q_ik,t =Softmax_k[ A_ik+β _j=1^NW_ijq_jk,t+Ii _t) _ik,t^VB], where ℓik,tVB=si,t[ψ(ak,t)−ψ(ak,t+bk,t)]+(ni,t−si,t)[ψ(bk,t)−ψ(ak,t+bk,t)]. _ik,t^VB=s_i,t [ψ(a_k,t)-ψ(a_k,t+b_k,t) ]+(n_i,t-s_i,t) [ψ(b_k,t)-ψ(a_k,t+b_k,t) ]. Proposition 2: Coordinate-Optimal Beta Update Fix q(t)q(z_t). The coordinate-optimal factor is q⋆(θk,t)=Beta(ak,t,bk,t),q ( _k,t)=Beta(a_k,t,b_k,t), where ak,t=ak,thist+∑i∈tqik,tsi,t,a_k,t=a_k,t^hist+ _i _tq_ik,ts_i,t, and bk,t=bk,thist+∑i∈tqik,t(ni,t−si,t).b_k,t=b_k,t^hist+ _i _tq_ik,t(n_i,t-s_i,t). Proposition 3: Monotonicity and Convergence At training step t, we keep (ak,thist,bk,thist)(a_k,t^hist,b_k,t^hist) fixed. Each update in Propositions 1 and 2 maximizes the ELBO with respect to one group of parameters. Therefore, neither update decreases ℒt(q)L_t(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 tO_t, we initialize inference with the previous estimator state: qik,t(0)=qik,t−1q_ik,t^(0)=q_ik,t-1, ak,t(0)=ak,t−1a_k,t^(0)=a_k,t-1, bk,t(0)=bk,t−1.b_k,t^(0)=b_k,t-1.· We keep (ak,thist,bk,thist)(a_k,t^hist,b_k,t^hist) fixed during inference at step t. Each iteration first applies Proposition 1 to update qik,tq_ik,t. It then applies Proposition 2 to update (ak,t,bk,t)(a_k,t,b_k,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.22 2 We use a numerical approximation to accelerate computation. Code and Data Supplement provide the details. 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 tO_t into an updated estimator state for the full training set: t=qt,at,bt.S_t=\q_t,a_t,b_t\. The next subsection converts tS_t into sample-level difficulty estimates for adaptive scheduling. We also use tS_t to initialize inference at the next training step. Method Qwen-2.5-Math-1.5B (Average@8) Llama-3.2-1B-Instruct (Average@8) MATH500 AIME24 AIME25 Olym MATH500 AIME24 AIME25 Olym Base 39.3 3.30 3.33 25.2 17.5 0.00 0.00 3.02 GVM 71.9 11.3 11.3 35.8 23.9 0.42 0.00 4.59 GVM+Ours 74.7 16.7 13.3 38.3 25.7 3.30 0.00 4.89 PCL 59.7 7.92 4.58 26.1 26.7 0.42 0.00 5.04 PCL+Ours 61.6 11.3 6.67 27.1 27.4 0.00 0.42 5.81 GRESO 66.8 10.0 7.50 30.3 30.0 2.50 0.00 7.59 GRESO+Ours 68.2 10.0 10.0 31.9 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−5p<5× 10^-5, see Appendix C). 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 t−1=qt−1,at−1,bt−1S_t-1=\q_t-1,a_t-1,b_t-1\ from the previous step. For each latent state k, we compute the posterior mean of its success probability as μk,t−1=ak,t−1ak,t−1+bk,t−1 _k,t-1= a_k,t-1a_k,t-1+b_k,t-1 , We first form a model-based prediction for sample xix_i: p^i,tmodel=∑k=1Kqik,t−1μk,t−1 p_i,t^model= _k=1^Kq_ik,t-1 _k,t-1. Then we adjust the prediction based on whether the sample has been rolled out before. If xix_i has no prior rollouts, we directly use the model prediction: p^i,t=p^i,tmodel p_i,t= p_i,t^model. If it has been sampled in earlier steps, we average the model prediction with its historical success rate r¯i,<t r_i,<t: OPENp^i,t=γp^i,tmodel+(1−γ)r¯i,<t) p_i,t=γ p_i,t^model+(1-γ) r_i,<t) (γ=0.5γ=0.5, see discussion in Appendix E). Also, the estimated difficulty is then d^i,t=1−p^i,t d_i,t=1- p_i,t. Overall, before training step t, the estimator predicts the difficulty of every sample. These outputs serve as a plug-and-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 (46), following 50 and 52, we adopt Qwen 2.5 1.5B Math (49) and Llama 3 1B-Instruct (17) 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 (54) as the sentence embedding model, and set K=320K=320, knn=80k_n=80, γ=0.5γ=0.5 and β=2β=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 (50; 15; 56) and conduct reinforcement learning on NuminaMath (27; 11). We evaluate the resulting models on MATH500 (20; 28), AIME 2024 (2), AIME 2025 (12), and OlympiadBench (19). 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 (50); PCL, a curriculum-learning method that trains a dedicated difficulty predictor (15); and GRESO, a curriculum-learning method that uses historical success rates as difficulty signals (56). 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 (18; 40). Because a single evaluation on small and challenging datasets such as AIME can be sensitive to sampling randomness, we follow prior work (50; 56) 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 pre-sampling 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 in-depth 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 samples 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? Base Model Methods Early Steps Middle Steps Last Steps Full Steps Time (A100*h) MAE (↓ ) r (↑ ) MAE (↓ ) r (↑ ) MAE (↓ ) r (↑ ) MAE (↓ ) r (↑ ) Qwen-2.5 Math-1.5B Sample before RL 0.116 0.544 0.139 0.856 0.151 0.865 0.135 0.522 ∼ 29.6 Sample before Step 0.063 0.959 0.054 0.971 0.049 0.974 0.055 0.969 ∼ 45.3 VIP 0.373 - 0.094 0.794 0.084 0.885 0.184 0.423 ∼ 0.05 PCL 0.404 0.138 0.336 0.407 0.328 0.474 0.356 0.281 ∼ 7.36 MoPPS 0.373 - 0.149 0.910 0.118 0.929 0.214 0.754 - Ours 0.290 0.482 0.133 0.912 0.123 0.943 0.183 0.836 ∼ 0.12 Llama-3.2 1B-Instruct Sample before RL 0.116 0.374 0.141 0.648 0.154 0.671 0.137 0.394 ∼ 33.4 Sample before Step 0.044 0.986 0.046 0.967 0.046 0.967 0.045 0.986 ∼ 47.9 VIP 0.413 - 0.107 0.895 0.084 0.880 0.201 0.717 ∼ 0.05 PCL 0.204 0.467 0.181 0.404 0.187 0.525 0.191 -0.231 ∼ 4.38 MoPPS 0.413 - 0.133 0.864 0.109 0.869 0.218 0.606 - Ours 0.197 0.469 0.100 0.868 0.075 0.913 0.131 0.776 ∼ 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. 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.4820.482 for Qwen and 0.4690.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 related samples. As more rollout observations accumulate, the full-trajectory correlations increase to 0.8360.836 and 0.7760.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. Ablation Study Base Model Methods Full Steps MAE (↓) r (↑) Qwen-2.5 Math-1.5B Ours 0.183 0.836 w/o Spectral Init. 0.218 0.710 w/o Prior Smoothing 0.197 0.783 w/o Graph Sparsification 0.187 0.835 Llama-3.2 1B-Instruct Ours 0.131 0.776 w/o Spectral Init. 0.197 0.686 w/o Prior Smoothing 0.144 0.736 w/o Graph Sparsification 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. 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 latent-state prior AikA_ik with hard assignments also degrades performance. As the policy evolves, sample difficulty and its latent-state 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 retains more reliable relationships between samples. Do Spectral Clusters Capture Semantic and Difficulty Structure? We use MATH (20) 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χ^2=10,995.84, p<10−300p<10^-300; Cramér’s V=0.494V=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−3p_max<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. 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 This section derives the expanded evidence lower bound (ELBO) in Sec. 3.5 and proves Propositions 1–3. For compactness, define δik,t=(zi,t=k) _ik,t=I(z_i,t=k) and let CtC_t collect all terms that are independent of the variational distribution. The mutual-neighbor graph is undirected, so Wij=WjiW_ij=W_ji, and it has no self-loops, so Wii=0W_i=0. A.1 Derivation of the Expanded ELBO From the joint model in Sec. 3.4, its log density can be written, up to the constant CtC_t, as logpt(t,t,t∣t,W,A) p_t(s_t,z_t, θ_t _t,W,A) = = Ct+∑i=1N∑k=1Kδik,tlogAik+β2∑i=1N∑j=1NWij∑k=1Kδik,tδjk,t C_t+ _i=1^N _k=1^K _ik,t A_ik+ β2 _i=1^N _j=1^NW_ij _k=1^K _ik,t _jk,t +∑k=1K[(ak,thist−1)logθk,t+(bk,thist−1)log(1−θk,t)] + _k=1^K [(a_k,t^hist-1) _k,t+(b_k,t^hist-1) (1- _k,t) ] +∑i∈t∑k=1Kδik,tsi,tlogθk,t + _i _t _k=1^K _ik,ts_i,t _k,t +∑i∈t∑k=1Kδik,t(ni,t−si,t) + _i _t _k=1^K _ik,t(n_i,t-s_i,t) ×log(1−θk,t). × (1- _k,t). (1) Here, CtC_t includes −logZ(W,A)- Z(W,A), the Beta normalizers, and the binomial coefficients, all of which are fixed with respect to qtq_t. Under the mean-field distribution, qt[δik,t] _q_t[ _ik,t] =qik,t, =q_ik,t, (2) qt[δik,tδjk,t] _q_t[ _ik,t _jk,t] =qik,tqjk,t(i≠j), =q_ik,tq_jk,t (i≠ j), (3) qt[logθk,t] _q_t[ _k,t] =ψ(ak,t)−ψ(ak,t+bk,t), =ψ(a_k,t)-ψ(a_k,t+b_k,t), (4) qt[log(1−θk,t)] _q_t[ (1- _k,t)] =ψ(bk,t)−ψ(ak,t+bk,t). =ψ(b_k,t)-ψ(a_k,t+b_k,t). (5) The second identity is sufficient for the graph term because Wii=0W_i=0. The negative entropy contribution factorizes as −qt[logqt]= -E_q_t[ q_t]= −∑i=1N∑k=1Kqik,tlogqik,t - _i=1^N _k=1^Kq_ik,t q_ik,t −∑k=1Kqt[logq(θk,t)]. - _k=1^KE_q_t[ q( _k,t)]. (6) Combining the expected log Beta prior with the corresponding Beta-factor entropy gives qt[logBeta(θk,t∣ak,thist,bk,thist)−logq(θk,t)] _q_t\! [ ( _k,t a_k,t^hist,b_k,t^hist)- q( _k,t) ] =−KL[Beta(ak,t,bk,t)∥Beta(ak,thist,bk,thist)]. =-KL\! [Beta(a_k,t,b_k,t)\, \|\,Beta(a_k,t^hist,b_k,t^hist) ]. (7) Substituting these identities into ℒt(qt)=qt[logpt]−qt[logqt]L_t(q_t)=E_q_t[ p_t]-E_q_t[ q_t] yields the expression below. To keep the display compact, let Dk,tBeta=KL[Beta(ak,t,bk,t)∥Beta(ak,thist,bk,thist)]. D_k,t^Beta=KL\! [Beta(a_k,t,b_k,t)\, \|\,Beta(a_k,t^hist,b_k,t^hist) ]. (8) Then ℒt(qt)= _t(q_t)= β2∑i=1N∑j=1NWij∑k=1Kqik,tqjk,t β2 _i=1^N _j=1^NW_ij _k=1^Kq_ik,tq_jk,t +∑i=1N∑k=1Kqik,tlogAik + _i=1^N _k=1^Kq_ik,t A_ik −∑i=1N∑k=1Kqik,tlogqik,t - _i=1^N _k=1^Kq_ik,t q_ik,t +∑i∈t∑k=1Kqik,tℓik,tVB + _i _t _k=1^Kq_ik,t _ik,t^VB −∑k=1KDk,tBeta+Ct, - _k=1^KD_k,t^Beta+C_t, (9) where ℓik,tVB= _ik,t^VB= si,t[ψ(ak,t)−ψ(ak,t+bk,t)] s_i,t [ψ(a_k,t)-ψ(a_k,t+b_k,t) ] +(ni,t−si,t)[ψ(bk,t)−ψ(ak,t+bk,t)]. +(n_i,t-s_i,t) [ψ(b_k,t)-ψ(a_k,t+b_k,t) ]. (10) Dropping CtC_t, which is independent of qtq_t, gives exactly the expanded ELBO reported in Sec. 3.5. A.2 Proof of Proposition 1 Fix q(t)q( θ_t) and every assignment factor except qi(zi,t)q_i(z_i,t). Because W is symmetric, the two appearances of node i in the double graph sum combine and cancel the factor 1/21/2. The terms of Eq. (9) that depend on qik,tq_ik,t are therefore ℒt(qi)= _t(q_i)= ∑k=1Kqik,thik,t−∑k=1Kqik,tlogqik,t+C, _k=1^Kq_ik,th_ik,t- _k=1^Kq_ik,t q_ik,t+C, (11) hik,t= h_ik,t= logAik+β∑j=1NWijqjk,t+(i∈t)ℓik,tVB. A_ik+β _j=1^NW_ijq_jk,t+I(i _t) _ik,t^VB. (12) Introduce a Lagrange multiplier λi _i for ∑k=1Kqik,t=1 _k=1^Kq_ik,t=1 and define ℒ~t(qi)=ℒt(qi)+λi(∑r=1Kqir,t−1). L_t(q_i)=L_t(q_i)+ _i ( _r=1^Kq_ir,t-1 ). (13) Differentiating gives ∂ℒ~t(qi)∂qik,t=hik,t−logqik,t−1+λi. ∂ L_t(q_i)∂ q_ik,t=h_ik,t- q_ik,t-1+ _i. (14) Setting this derivative to zero and normalizing over k yields qik,t⋆=exp(hik,t)∑r=1Kexp(hir,t)=Softmaxk(hik,t), q_ik,t = (h_ik,t) _r=1^K (h_ir,t)=Softmax_k(h_ik,t), (15) which is the update in Proposition 1. A.3 Proof of Proposition 2 Fix q(t)q(z_t) and define q−k,t=q(t)∏r≠kq(θr,t)q_-k,t=q(z_t) _r≠ kq( _r,t). The standard mean-field coordinate identity gives logq⋆(θk,t)= q ( _k,t)= q−k,t[logpt(t,t,t _q_-k,t [ p_t(s_t,z_t, θ_t ∣t,W,A)]+C. _t,W,A) ]+C. (16) Retaining only terms involving θk,t _k,t in Eq. (1) gives αk,t _k,t =ak,thist+∑i∈tqik,tsi,t, =a_k,t^hist+ _i _tq_ik,ts_i,t, (17) γk,t _k,t =bk,thist+∑i∈tqik,t(ni,t−si,t), =b_k,t^hist+ _i _tq_ik,t(n_i,t-s_i,t), (18) logq⋆(θk,t)= q ( _k,t)= (αk,t−1)logθk,t ( _k,t-1) _k,t +(γk,t−1)log(1−θk,t)+C. +( _k,t-1) (1- _k,t)+C. (19) This is the log density of a Beta distribution. Hence q⋆(θk,t) q ( _k,t) =Beta(ak,t,bk,t), =Beta(a_k,t,b_k,t), (20) ak,t a_k,t =ak,thist+∑i∈tqik,tsi,t, =a_k,t^hist+ _i _tq_ik,ts_i,t, (21) bk,t b_k,t =bk,thist+∑i∈tqik,t(ni,t−si,t), =b_k,t^hist+ _i _tq_ik,t(n_i,t-s_i,t), (22) 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)q_i(z_i,t) while all other factors are held fixed. We consider two implementations of this update. Sequential reference implementation. Our reference implementation performs a strict sequential Gauss–Seidel sweep over the samples. Under the update order i=1,…,Ni=1,…,N, the assignment update at iteration m+1m+1 is qik,t(m+1)=Softmaxk[ q_ik,t^(m+1)=Softmax_k [ logAik+β∑j<iWijqjk,t(m+1)+β∑j>iWijqjk,t(m) A_ik+β _j<iW_ijq_jk,t^(m+1)+β _j>iW_ijq_jk,t^(m) +(i∈t)ℓik,tVB,(m)]. +I(i _t) _ik,t^VB,(m) ]. (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. Synchronous accelerated implementation. The strict sequential update is difficult to parallelize over samples. We therefore additionally implement a synchronous Jacobi-style update: q~ik,t(m+1)=Softmaxk[logAik+β∑j=1NWijqjk,t(m)+(i∈t)ℓik,tVB,(m)]. q_ik,t^(m+1)=Softmax_k [ A_ik+β _j=1^NW_ijq_jk,t^(m)+I(i _t) _ik,t^VB,(m) ]. (24) 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=max1≤i≤N|p^i,tsync−p^i,tseq|. _t= _1≤ i≤ N | p_i,t^sync- p_i,t^seq |. (25) Across the evaluated training checkpoints, the discrepancy remains within 10−210^-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 (ak,thist,bk,thist)(a_k,t^hist,b_k,t^hist), the graph (W,A)(W,A), and all rollout observations are fixed. We assume that Aik>0for every i,k, A_ik>0 every i,k, (26) ak,thist>0,bk,thist>0for every k, a_k,t^hist>0, b_k,t^hist>0 every k, (27) |Wij|<∞,ni,t<∞. |W_ij|<∞, n_i,t<∞. (28) The first condition is satisfied by the smoothed initialization when 0<ϵ<10<ε<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)q_i(z_i,t). Proposition 1 gives the unique maximizer of the ELBO with respect to this factor. Therefore, updating qi(zi,t)q_i(z_i,t) cannot decrease the ELBO. Similarly, after fixing q(t)q(z_t) and all Beta factors except q(θk,t)q( _k,t), Proposition 2 gives the coordinate-optimal Beta factor. Updating this factor therefore cannot decrease the ELBO. Consequently, if qt(m)q_t^(m) denotes the variational distribution after the m-th coordinate update, then ℒt(qt(m+1))≥ℒt(qt(m)). _t(q_t^(m+1)) _t(q_t^(m)). (29) Boundedness of the parameter sequence. Each categorical parameter belongs to the probability simplex: (qi1,t,…,qiK,t)∈ΔK. (q_i1,t,…,q_iK,t)∈ _K. (30) The product of the N categorical simplexes is compact. Define the total number of observed successes and failures at training step t as St S_t =∑i∈tsi,t, = _i _ts_i,t, (31) Ft F_t =∑i∈t(ni,t−si,t). = _i _t(n_i,t-s_i,t). (32) By Proposition 2 and 0≤qik,t≤10≤ q_ik,t≤ 1, the Beta parameters satisfy ak,thist≤ak,t≤ak,thist+St, a_k,t^hist≤ a_k,t≤ a_k,t^hist+S_t, (33) bk,thist≤bk,t≤bk,thist+Ft. b_k,t^hist≤ b_k,t≤ b_k,t^hist+F_t. (34) Therefore, all Beta parameters remain in compact positive intervals. The complete variational-parameter sequence consequently lies in the compact set t= _t= (∏i=1NΔK) ( _i=1^N _K ) ×∏k=1K[ak,thist,ak,thist+St] × _k=1^K [a_k,t^hist,a_k,t^hist+S_t ] ×∏k=1K[bk,thist,bk,thist+Ft]. × _k=1^K [b_k,t^hist,b_k,t^hist+F_t ]. (35) In particular, the parameter sequence has at least one accumulation point. Convergence of the ELBO values. Let ptpost=pt(t,t∣t,t,W,A) p_t^post=p_t(z_t, θ_t _t,n_t,W,A) (36) denote the exact posterior. The ELBO satisfies ℒt(qt)= _t(q_t)= logpt(t∣t,W,A) p_t(s_t _t,W,A) −KL[qt∥ptpost]. -KL [q_t\, \|\,p_t^post ]. (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, ℒt(qt)≤logpt(t∣t,W,A). _t(q_t)≤ p_t(s_t _t,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 ℒt⋆L_t such that limm→∞ℒt(qt(m))=ℒt⋆. _m→∞L_t(q_t^(m))=L_t . (39) Stationarity of accumulation points. Consider the iterates at the boundaries of complete sequential sweeps, and let TtT_t 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 tX_t. Therefore, TtT_t is continuous. Let q¯t q_t be an accumulation point of the sweep-level variational sequence. Suppose, for contradiction, that Tt(q¯t)≠q¯tT_t( 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 ℒt(Tt(q¯t))>ℒt(q¯t). _t(T_t( q_t))>L_t( q_t). (40) By continuity, the same positive improvement would hold in a neighborhood of q¯t 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. T_t( 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>0A_ik>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 Figure 2: EM iterations 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 data-processing protocols of GVM and CurES, we extract approximately 150K problems from the original corpus for RL training (11). 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. AIME 2024. Our AIME 2024 evaluation set combines the 15 problems from AIME I and the 15 problems from AIME I, 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 rule-based 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. AIME 2025. Our AIME 2025 evaluation set similarly combines AIME I and AIME I, 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. 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 theorem-proving 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 (13) 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. _m,b,d=Acc_m+Ours,b,d-Acc_m,b,d. (42) We record a gain if Δm,b,d>0 _m,b,d>0, a loss if Δm,b,d<0 _m,b,d<0, and a tie if Δm,b,d=0 _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+Ln=W+L. Exact Test and Results 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). H_0: ( >0 ≠ 0)= 12, W (n, 12). (43) The two-sided exact p-value is psign=min1, 2∑r=0min(W,L)(nr)2−n. p_sign= \1,\;2 _r=0 (W,L) nr2^-n \. (44) Counting directly from Table 1 gives the following results. Full integration W L T psignp_sign GVM + Ours 7 0 1 0.0156 PCL + Ours 7 1 0 0.0703 GRESO + Ours 7 0 1 0.0156 Pooled 21 1 2 1.10×10−51.10× 10^-5 Table 4: Directional sign-test results for the full integrations. Ties are excluded from the exact test. For the PCL integration, W=7W=7, L=1L=1, and n=8n=8. Its two-sided exact p-value is psign p_sign =2[(80)+(81)]2−8 =2 [ 80+ 81 ]2^-8 =18256=0.0703125. = 18256=0.0703125. (45) At the nominal significance level α=0.10α=0.10, all three full integrations exhibit statistically significant directional improvements. Specifically, GVM + Ours and GRESO + Ours achieve significance at the α=0.05α=0.05 level, while PCL + Ours achieves significance at the α=0.10α=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=21W=21, L=1L=1, and n=22n=22. Equation (44) therefore gives psign p_sign =2[(220)+(221)]2−22 =2 [ 220+ 221 ]2^-22 =464,194,304=1.0967×10−5. = 464,194,304=1.0967× 10^-5. (46) 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%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 Full Steps MAE (↓) r (↑) Qwen2.5-Coder-7B Instruct VIP 0.197 0.504 PCL 0.402 0.307 MoPPS 0.224 0.773 Ours 0.176 0.845 Table 5: Difficulty-estimation performance on code generation using Qwen2.5-Coder-7B-Instruct. MAE is sample-level, and r is the batch-level Pearson correlation. Setting Many existing adaptive RL scheduling methods are developed and evaluated primarily for mathematical reasoning. Extending them to code generation may require domain-specific 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 (22) 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 (22). 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, knnk_knn and β We discuss three hyperparameters controlling our difficulty estimator. K is the number of latent difficulty states, determining modeling granularity; knnk_n 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 22 to 55 or above, all metrics become nearly identical and slightly worse, indicating that an over-strong 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β=2 and K=320K=320 in the main experiments. β K Early Steps Full Steps r (↑) MAE (↓) r (↑) MAE (↓) 2 320 0.482 0.290 0.836 0.183 2 160 0.480 0.306 0.838 0.191 2 80 0.494 0.313 0.843 0.194 2 40 0.507 0.327 0.848 0.196 1 320 0.488 0.302 0.849 0.189 5 320 0.494 0.297 0.847 0.186 10 320 0.490 0.297 0.847 0.186 20 320 0.493 0.298 0.847 0.187 Table 6: Sensitivity analysis of β and K on Qwen-2.5-Math-1.5B. MAE is sample-level, and r is batch-level Pearson correlation. The neighborhood size knnk_n 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 knnk_n 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 knnk_n 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(Nknn)O(Nk_n). 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 knnk_n33 3 Theoretically, the complexity grows linearly with knnk_n, 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 knnk_n is increased. In our setting, the wall-clock time when the edge count saturates is about 1.61×1.61× that of the proposed method in the main text.. Discussion of Embedding Models and Difficulty-Aware Instruction Models Selection We compare several recent text-embedding models that support task-aware or instruction-conditioned embedding, including Qwen3-Embedding-0.6B, Qwen3-Embedding-4B (54), and BGE-M3 (9). 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 Qwen3-Embedding-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-Embedding-4B output to 1,024 dimensions using its Matryoshka-compatible representation (25) 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 (37), or with the encoder configuration adopted by VIP (32), 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 Base Model Methods Full Steps MAE (↓) r (↑) Qwen-2.5 Math-1.5B Qwen3-Embedding-0.6B 0.183 0.836 -Difficulty-Aware Instruction 0.309 0.583 Qwen3-Embedding-4B 0.188 0.827 Qwen3-Embedding-4B MRL(1024 dimensions) 0.179 0.844 BGE-M3 0.188 0.823 MiniLM 0.326 0.407 Llama-3.2 1B-Instruct Qwen3-Embedding-0.6B 0.131 0.776 -Difficulty-Aware Instruction 0.302 0.486 Qwen3-Embedding-4B 0.130 0.749 Qwen3-Embedding-4B MRL(1024 dimensions) 0.121 0.787 BGE-M3 0.139 0.783 MiniLM 0.304 0.407 Table 7: Full-trajectory difficulty-estimation performance of different embedding configurations. The row “-Difficulty-Aware Instruction” removes the instruction from the default encoder. MAE: sample-level mean absolute error (lower is better); r: batch-level Pearson correlation (higher is better). Table 7 shows that removing the difficulty-aware instruction from Qwen3-Embedding-0.6B causes a substantial degradation 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 task-awareness needed for constructing a difficulty-aware graph. Discussion of the Interpolation Weight γ For samples with prior rollouts, we combine the graph-based prediction and the sample-level empirical success rate asp^i,t=γp^i,tmodel+(1−γ)r¯i,<t p_i,t=γ p_i,t^model+(1-γ) r_i,<t The parameter γ controls the balance between transferable graph-based evidence and direct sample-level history. A small γ makes the estimate dominated by (r¯i,<tCLOSE( 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γ=0.5 as a general default. In our experiments, performance is relatively stable for γ∈[0.5,0.8]γ∈[0.5,0.8]. When γ<0.5γ<0.5, ranking quality tends to decrease; when γ>0.8γ>0.8, sample-level 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: vk,t−1=ak,t−1bk,t−1(ak,t−1+bk,t−1)2(ak,t−1+bk,t−1+1).v_k,t-1= a_k,t-1b_k,t-1(a_k,t-1+b_k,t-1)^2(a_k,t-1+b_k,t-1+1). Combined with assignment uncertainty, this gives u^i,t=∑k=1Kqik,t−1[vk,t−1+(μk,t−1−p^i,tmodel)2]. u_i,t= _k=1^Kq_ik,t-1 [v_k,t-1+ ( _k,t-1- p_i,t^model )^2 ]. 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γ=0.5. F. Discussion of Spectral Clusters Association with Subject Categories For each analyzed MATH problem i, let zi∈1,…,K+z_i∈\1,…,K_+\ denote its nonempty spectral-cluster assignment and let ci∈1,…,Uc_i∈\1,…,U\ denote its subject category. We form the K+×UK_+× U contingency table Oku=∑i=1n(zi=k,ci=u), O_ku= _i=1^nI(z_i=k,c_i=u), (47) with row totals Ok⋅O_k·, column totals O⋅uO_· 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)(k,u) is Eku=Ok⋅O⋅un. E_ku= O_k·O_· un. (48) We measure departure from independence using Pearson’s chi-squared statistic (34), χ2=∑k=1K+∑u=1U(Oku−Eku)2Eku, χ^2= _k=1^K_+ _u=1^U (O_ku-E_ku)^2E_ku, (49) whose asymptotic null distribution has (K+−1)(U−1)(K_+-1)(U-1) degrees of freedom. Applying this calculation to the MATH training split gives n=7,500n=7,500, K+=16K_+=16, and U=7U=7; thus, the contingency table contains 16×716× 7 cells and the asymptotic reference distribution has 9090 degrees of freedom. The resulting statistic is χ2=10,995.84χ^2=10,995.84, with asymptotic p<10−300p<10^-300, rejecting independence. Because the chi-squared statistic increases with sample size, we additionally report Cramér’s V, a normalized effect-size measure for categorical association (10): V=χ2nmin(K+−1,U−1). V= χ^2n (K_+-1,U-1). (50) The resulting V=0.494V=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 (24). This stratification asks whether the annotated difficulty levels differ across spectral clusters among problems from the same subject. For subject u, let nun_u be its number of problems and nkun_ku the number assigned to nonempty cluster k. We rank the ordinal difficulty levels of all nun_u problems within that subject, assigning midranks to ties. Let RkuR_ku be the sum of ranks in cluster k. The uncorrected Kruskal–Wallis statistic is Hu(0)=12nu(nu+1)∑k:nku>0Rku2nku−3(nu+1). H_u^(0)= 12n_u(n_u+1) _k:n_ku>0 R_ku^2n_ku-3(n_u+1). (51) Because MATH difficulty takes only five ordinal levels, ties are frequent. Let tugt_ug be the size of the g-th tied group within subject u. We apply the standard ties correction Cu=1−∑g(tug3−tug)nu3−nu,Hu=Hu(0)Cu. C_u=1- _g(t_ug^3-t_ug)n_u^3-n_u, H_u= H_u^(0)C_u. (52) If KuK_u clusters are nonempty within subject u, the raw asymptotic p-value is computed from a chi-squared reference distribution with Ku−1K_u-1 degrees of freedom: pu=Pr(χKu−12≥Hu). p_u= \! (χ^2_K_u-1≥ H_u ). (53) The seven raw p-values form one family of hypotheses. We therefore apply the Benjamini–Hochberg procedure to control the false discovery rate (5). After sorting the raw values as p(1)≤⋯≤p(m)p_(1)≤·s≤ p_(m), where m=7m=7, the monotone adjusted values are p~(r)=min1,minj≥rmjp(j). p_(r)= \1,\; _j≥ r mjp_(j) \. (54) Subject Raw p BH-adjusted p Algebra ≈0≈ 0 ≈0≈ 0 Prealgebra ≈0≈ 0 ≈0≈ 0 Precalculus ≈0≈ 0 1.0×10−61.0× 10^-6 Intermediate algebra 2.0×10−62.0× 10^-6 3.0×10−63.0× 10^-6 Counting/probability 8.0×10−68.0× 10^-6 1.1×10−51.1× 10^-5 Number theory 3.19×10−43.19× 10^-4 3.72×10−43.72× 10^-4 Geometry 4.31×10−34.31× 10^-3 4.31×10−34.31× 10^-3 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. All seven subject-specific null hypotheses remain rejected after BH correction, with p~u≤4.31×10−3 p_u≤ 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. 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., ak,thist=ak,t−1a_k,t^hist=a_k,t-1 and bk,thist=bk,t−1b_k,t^hist=b_k,t-1. However, the rollout distribution is 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≥1L≥ 1 as t(L)=τ:max(1,t−L)≤τ<t, _t^(L)= \τ: (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 Sk,t(L)=∑τ∈t(L)∑i∈τqik,τsi,τ, S_k,t^(L)= _τ _t^(L) _i _τq_ik,τs_i,τ, (56) and Fk,t(L)=∑τ∈t(L)∑i∈τqik,τ(ni,τ−si,τ). F_k,t^(L)= _τ _t^(L) _i _τq_ik,τ (n_i,τ-s_i,τ ). (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: ak,t(L)=a0+Sk,t(L),bk,t(L)=b0+Fk,t(L). a_k,t^(L)=a_0+S_k,t^(L), b_k,t^(L)=b_0+F_k,t^(L). (58) In our implementation, we set a0=b0=1a_0=b_0=1, corresponding to the uniform prior Beta(1,1)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 observations in the current window. When Sk,t(L)=Fk,t(L)=0S_k,t^(L)=F_k,t^(L)=0, the Beta(1,1)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 [θk,t]=a0a0+b0 [ _k,t]= a_0a_0+b_0 (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)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 μk,t(L)=ak,t(L)ak,t(L)+bk,t(L). _k,t^(L)= a_k,t^(L)a_k,t^(L)+b_k,t^(L). (60) The model-based prediction for sample xix_i retains the same mixture form as in the main method: p^i,tmodel=∑k=1Kqik,tμk,t(L). p_i,t^model= _k=1^Kq_ik,t _k,t^(L). (61) 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 qt(t,t)≈∏i=1Nqi(zi,t)∏k=1Kq(θk,t), q_t(z_t, θ_t)≈ _i=1^Nq_i(z_i,t) _k=1^Kq( _k,t), (62) where qik,t≡qi(zi,t=k)q_ik,t≡ q_i(z_i,t=k) and q(θk,t)=Beta(ak,t(L),bk,t(L)). q( _k,t)=Beta (a_k,t^(L),b_k,t^(L) ). (63) The coordinate update for the latent-state assignments preserves the same three sources of information as the main method: qik(r+1)=Softmaxk[logAik+β∑j=1NWijqjk(r)+(i∈t(L))ℓik,t(L)],q_ik^(r+1)=Softmax_k [ A_ik+β _j=1^NW_ijq_jk^(r)+I (i _t^(L) ) _ik,t^(L) ], where t(L)=⋃τ∈t(L)τ. _t^(L)= _τ _t^(L)O_τ. (64) For each sample i, we aggregate its rollout outcomes within the current window as si,t(L)=∑τ∈t(L)si,τ,ni,t(L)=∑τ∈t(L)ni,τ, s_i,t^(L)= _τ _t^(L)s_i,τ, n_i,t^(L)= _τ _t^(L)n_i,τ, (65) and compute the corresponding expected log-likelihood as ℓik,t(L)=si,t(L)[ψ(ak,t(L))−ψ(ak,t(L)+bk,t(L))]+(ni,t(L)−si,t(L))[ψ(bk,t(L))−ψ(ak,t(L)+bk,t(L))]. _ik,t^(L)=s_i,t^(L) [ψ (a_k,t^(L) )-ψ (a_k,t^(L)+b_k,t^(L) ) ]+ (n_i,t^(L)-s_i,t^(L) ) [ψ (b_k,t^(L) )-ψ (a_k,t^(L)+b_k,t^(L) ) ]. After updating the assignment probabilities, the state-level Beta factors are recomputed using only the rollout observations within the current window: ak,t(L)=1+∑τ∈t(L)∑i∈τqiksi,τ, a_k,t^(L)=1+ _τ _t^(L) _i _τq_iks_i,τ, (66) and bk,t(L)=1+∑τ∈t(L)∑i∈τqik(ni,τ−si,τ). b_k,t^(L)=1+ _τ _t^(L) _i _τq_ik (n_i,τ-s_i,τ ). (67) 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 t=qt,at,btS_t=\q_t,a_t,b_t\ is passed between consecutive training steps. In the windowed variant, we retain only the previous assignment probabilities as the default initialization: qik,t(0)=qik,t−1. q_ik,t^(0)=q_ik,t-1. (68) The Beta parameters are not directly inherited from the previous step. Instead, they are reconstructed from the fixed Beta(1,1)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 xix_i, we separately retain its complete rollout history before step t: Si,tall=∑τ<tsi,τ,Ci,tall=∑τ<tni,τ. S_i,t^all= _τ<ts_i,τ, C_i,t^all= _τ<tn_i,τ. (69) For a previously observed sample, its historical empirical success rate is r¯i,<t=Si,tallCi,tall. r_i,<t= S_i,t^allC_i,t^all. (70) We then retain the prediction rule from the main method: p^i,t=p^i,tmodel,Ci,tall=0,γp^i,tmodel+(1−γ)r¯i,<t,Ci,tall>0. p_i,t= cases p_i,t^model,&C_i,t^all=0,\\[4.0pt] γ p_i,t^model+(1-γ) r_i,<t,&C_i,t^all>0. cases (71) 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 sample-level 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 Full Steps MAE (↓) r (↑) Qwen-2.5 Math-1.5B Ours 0.183 0.836 Windows 0.127 0.712 Llama-3.2 1B-Instruct Ours 0.131 0.776 Windows 0.119 0.747 Table 9: Sample-level difficulty estimation performance of the cumulative estimator (Ours) and the windowed variant (Windows) over all training steps. MAE measures the absolute prediction error, while batch-level r denotes the Pearson correlation between the predicted and reference success probabilities. Lower MAE and higher r indicate better performance. Figure 3: Batch-level reference accuracy and predicted accuracy of the cumulative and windowed estimators on Qwen-2.5-Math-1.5B and Llama-3.2-1B-Instruct. We evaluate the windowed variant by replaying the full training logs of Qwen-2.5-Math-1.5B and Llama-3.2-1B-Instruct, 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.1830.183 to 0.1270.127 on Qwen-2.5-Math-1.5B, and from 0.1310.131 to 0.1190.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.8360.836 to 0.7120.712 on Qwen-2.5-Math-1.5B, and from 0.7760.776 to 0.7470.747 on Llama-3.2-1B-Instruct. This suggests a trade-off: 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 (31; 43), while Gaussian-field propagation, local-and-global consistency, and manifold regularization diffuse sparse supervision according to graph geometry (58; 57; 3). 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 (35; 6; 16). Because graph coupling makes exact posterior inference difficult, variational methods optimize a tractable approximation, with mean-field factorizations yielding scalable coordinate updates (53; 29; 44; 7). Stochastic and streaming variants update approximate posteriors as new observations arrive (21; 8). References Bae et al. (2026) S. Bae, J. Hong, M. Y. Lee, H. Kim, J. Nam, and D. Kwak 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), p. 700–719. Cited by: Adaptive Sampling and Rollout Allocation in RLVR. Balunovic et al. (2026) M. Balunovic, J. Dekoninck, I. Petrov, N. Jovanović, and M. Vechev Matharena: evaluating llms on uncontaminated math competitions. Advances in Neural Information Processing Systems 38. Cited by: Implementation Details. Belkin et al. (2006) M. Belkin, P. Niyogi, and V. Sindhwani Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research 7 (85), p. 2399–2434. External Links: Link Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Bengio et al. (2009) Y. Bengio, J. Louradour, R. Collobert, and J. Weston Curriculum Learning. In International Conference on Machine Learning, p. 41–48. External Links: Document, Link Cited by: Adaptive Sampling and Rollout Allocation in RLVR. Benjamini and Hochberg (1995) Y. Benjamini and Y. Hochberg Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal Statistical Society: Series B (Methodological) 57 (1), p. 289–300. External Links: Document Cited by: Difficulty Differences Within Subject Categories. Besag (1974) J. Besag Spatial interaction and the statistical analysis of lattice systems. Journal of the Royal Statistical Society: Series B (Methodological) 36 (2), p. 192–225. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference, Graph Prior.. Blei et al. (2017) D. M. Blei, A. Kucukelbir, and J. D. McAuliffe Variational inference: a review for statisticians. Journal of the American Statistical Association 112 (518), p. 859–877. External Links: Document, Link, https://doi.org/10.1080/01621459.2017.1285773 Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Broderick et al. (2013) T. Broderick, N. Boyd, A. Wibisono, A. Wilson, and M. Jordan Streaming variational bayes. In Advances in Neural Information Processing Systems, C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger (Eds.), Vol. 26, p. . External Links: Link Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Chen et al. (2024) J. Chen, S. Xiao, P. Zhang, K. Luo, D. Lian, and Z. Liu BGE M3-Embedding: multi-lingual, multi-functionality, multi-granularity text embeddings through self-knowledge distillation. External Links: 2402.03216, Link Cited by: Models Selection. Cramér (1946) H. Cramér Mathematical methods of statistics. Princeton University Press, Princeton, NJ. Cited by: Association with Subject Categories. Cui et al. (2025) G. Cui, L. Yuan, Z. Wang, H. Wang, Y. Zhang, J. Chen, W. Li, B. He, Y. Fan, T. Yu, et al. Process reinforcement through implicit rewards. arXiv preprint arXiv:2502.01456. Cited by: Implementation Details, NuminaMath.. Dekoninck et al. (2026) J. Dekoninck, N. Jovanović, T. Gehrunger, K. Rögnvaldsson, I. Petrov, C. Sun, and M. Vechev Beyond benchmarks: matharena as an evaluation platform for mathematics with llms. arXiv preprint arXiv:2605.00674. Cited by: Implementation Details. Dixon and Mood (1946) W. J. Dixon and A. M. Mood The statistical sign test. Journal of the American Statistical Association 41 (236), p. 557–566. External Links: Document Cited by: Question and Comparison Units. Fang et al. (2026) Y. Fang, J. Lin, X. Fu, C. Qin, H. Shi, C. Hu, L. Pan, K. Zeng, and X. Cai 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, p. 14727–14744. Cited by: Adaptive Sampling and Rollout Allocation in RLVR. Gao et al. (2026) Z. Gao, J. Kim, W. Sun, T. Joachims, S. Wang, R. Y. Pang, and L. Tan Prompt curriculum learning for efficient LLM post-training. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: Introduction, Adaptive Sampling and Rollout Allocation in RLVR, Dynamic Difficulty Estimation for Reasoning LLMs, Implementation Details, Implementation Details. Geman and Geman (1984) S. Geman and D. Geman Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence (6), p. 721–741. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Grattafiori et al. (2024) A. 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, et al. The llama 3 herd of models. External Links: 2407.21783, Link Cited by: Implementation Details. Guo et al. (2025) D. Guo, D. Yang, H. Zhang, J. Song, P. Wang, Q. Zhu, R. Xu, R. Zhang, S. Ma, X. Bi, et al. Deepseek-r1: incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. Cited by: Introduction, Implementation Details. He et al. (2024) C. He, R. Luo, Y. Bai, S. Hu, Z. Thai, J. Shen, J. Hu, X. Han, Y. Huang, Y. Zhang, et al. 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), p. 3828–3850. Cited by: Implementation Details. Hendrycks et al. (2021) D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874. Cited by: Implementation Details, Do Spectral Clusters Capture Semantic and Difficulty Structure?. Hoffman et al. (2013) M. D. Hoffman, D. M. Blei, C. Wang, and J. Paisley Stochastic variational inference. Journal of machine learning research. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference, 3.5 Online Mean-Field Variational Inference. Jain et al. (2024) N. Jain, K. Han, A. Gu, W. Li, F. Yan, T. Zhang, S. Wang, A. Solar-Lezama, K. Sen, and I. Stoica LiveCodeBench: holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.07974. Cited by: Setting. Kong et al. (2026) D. Kong, Q. Guo, X. Xi, W. Wang, J. Wang, X. Cai, S. Zhang, and W. Ye Rethinking the sampling criteria in reinforcement learning for llm reasoning: a competence-difficulty alignment perspective. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 31438–31446. Cited by: Introduction, Introduction, Adaptive Sampling and Rollout Allocation in RLVR, Dynamic Difficulty Estimation for Reasoning LLMs. Kruskal and Wallis (1952) W. H. Kruskal and W. A. Wallis Use of ranks in one-criterion variance analysis. Journal of the American Statistical Association 47 (260), p. 583–621. External Links: Document Cited by: Difficulty Differences Within Subject Categories. Kusupati et al. (2022) A. Kusupati, G. Bhatt, A. Rege, M. Wallingford, A. Sinha, V. Ramanujan, W. Howard-Snyder, K. Chen, S. Kakade, P. Jain, and A. Farhadi Matryoshka representation learning. In Advances in Neural Information Processing Systems, Vol. 35. External Links: Link Cited by: Models Selection. Lalor et al. (2016) J. P. Lalor, H. Wu, and H. Yu Building an evaluation scale using item response theory. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, J. Su, K. Duh, and X. Carreras (Eds.), Austin, Texas, p. 648–657. External Links: Link, Document Cited by: Dynamic Difficulty Estimation for Reasoning LLMs. Li et al. (2024) J. Li, E. Beeching, L. Tunstall, B. Lipkin, R. Soletskyi, S. Huang, K. Rasul, L. Yu, A. Q. Jiang, Z. Shen, et al. Numinamath: the largest public dataset in ai4maths with 860k pairs of competition math problems and solutions. Hugging Face repository 13 (9), p. 9. Cited by: Implementation Details. Lightman et al. (2024) H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe Let’s verify step by step. In International Conference on Learning Representations, Vol. 2024, p. 39578–39601. Cited by: Implementation Details. McGrory et al. (2009) C. A. McGrory, D. M. Titterington, R. Reeves, and A. N. Pettitt Variational bayes for estimating the parameters of a hidden potts model. Statistics and Computing 19 (3), p. 329–340. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Mindermann et al. (2022) S. Mindermann, J. M. Brauner, M. T. Razzak, M. Sharma, A. Kirsch, W. Xu, B. Höltgen, A. N. Gomez, A. Morisot, S. Farquhar, and Y. Gal Prioritized training on points that are learnable, worth learning, and not yet learnt. In Proceedings of the 39th International Conference on Machine Learning, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato (Eds.), Proceedings of Machine Learning Research, Vol. 162, p. 15630–15649. External Links: Link Cited by: Adaptive Sampling and Rollout Allocation in RLVR, Dynamic Difficulty Estimation for Reasoning LLMs. Ng et al. (2001) A. Ng, M. Jordan, and Y. Weiss On spectral clustering: analysis and an algorithm. Advances in neural information processing systems 14. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Nguyen et al. (2026a) H. T. Nguyen, B. Nguyen, W. Ma, Y. Zhao, R. She, and V. A. Nguyen Adaptive rollout allocation for online reinforcement learning with verifiable rewards. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: Introduction, Introduction, Introduction, Models Selection, Adaptive Sampling and Rollout Allocation in RLVR, Dynamic Difficulty Estimation for Reasoning LLMs. Nguyen et al. (2026b) M. Nguyen, S. Venkatesh, H. Le, et al. SPaCe: unlocking sample-efficient large language models training with self-pace curriculum learning. In Findings of the Association for Computational Linguistics: ACL 2026, p. 3480–3507. Cited by: Introduction. Pearson (1900) K. Pearson 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), p. 157–175. External Links: Document Cited by: Association with Subject Categories. Potts (1952) R. B. Potts Some generalized order-disorder transformations. In Mathematical proceedings of the cambridge philosophical society, Vol. 48, p. 106–109. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference, Graph Prior.. Qu et al. (2026) Y. Qu, Q. Wang, Y. Mao, V. T. Hu, B. Ommer, and X. Ji 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, p. 1240–1250. Cited by: Introduction, Introduction, Adaptive Sampling and Rollout Allocation in RLVR, Dynamic Difficulty Estimation for Reasoning LLMs, State-Level Success Model.. Reimers and Gurevych (2019) N. Reimers and I. Gurevych 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, p. 3982–3992. External Links: Document, Link Cited by: Models Selection. Rodriguez et al. (2021) P. Rodriguez, J. Barrow, A. Hoyle, J. P. Lalor, R. Jia, and J. Boyd-Graber Evaluation examples are not equally informative: how should that change NLP leaderboards?. In 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), C. Zong, F. Xia, W. Li, and R. Navigli (Eds.), Online, p. 4486–4503. External Links: Link, Document Cited by: Dynamic Difficulty Estimation for Reasoning LLMs. Shao et al. (2024) Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. Li, Y. Wu, et al. Deepseekmath: pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Cited by: Introduction, Introduction, Adaptive Sampling and Rollout Allocation in RLVR. Sheng et al. (2024) G. Sheng, C. Zhang, Z. Ye, X. Wu, W. Zhang, R. Zhang, Y. Peng, H. Lin, and C. Wu HybridFlow: a flexible and efficient rlhf framework. arXiv preprint arXiv: 2409.19256. Cited by: Implementation Details. Swayamdipta et al. (2020) S. Swayamdipta, R. Schwartz, N. Lourie, Y. Wang, H. Hajishirzi, N. A. Smith, and Y. Choi Dataset cartography: mapping and diagnosing datasets with training dynamics. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), B. Webber, T. Cohn, Y. He, and Y. Liu (Eds.), Online, p. 9275–9293. External Links: Link, Document Cited by: Dynamic Difficulty Estimation for Reasoning LLMs. Team et al. (2025) K. Team, A. Du, B. Gao, B. Xing, C. Jiang, C. Chen, C. Li, C. Xiao, C. Du, C. Liao, et al. Kimi k1. 5: scaling reinforcement learning with llms. arXiv preprint arXiv:2501.12599. Cited by: Introduction, Dynamic Difficulty Estimation for Reasoning LLMs. Von Luxburg (2007) U. Von Luxburg A tutorial on spectral clustering. Statistics and computing 17 (4), p. 395–416. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Wainwright and Jordan (2008) M. J. Wainwright and M. I. Jordan Graphical models, exponential families, and variational inference. Foundations and Trends® in Machine Learning 1 (1-2), p. 1–305. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Wang et al. (2026) H. Wang, Z. Hao, J. Luo, C. Wei, Y. Shu, L. Liu, Cheaterlin, H. Dong, and J. Chen Scheduling your LLM reinforcement learning with reasoning trees. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: Dynamic Difficulty Estimation for Reasoning LLMs. Wu et al. (2026) M. Wu, Z. Zhang, Q. Dong, Z. Xi, J. Zhao, S. Jin, X. Fan, Y. Zhou, H. Lv, M. Zhang, et al. Reasoning or memorization? unreliable results of reinforcement learning due to data contamination. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 33944–33952. Cited by: Implementation Details. Xiong et al. (2025) W. Xiong, C. Ye, B. Liao, H. Dong, X. Xu, C. Monz, J. Bian, N. Jiang, and T. Zhang Reinforce-ada: an adaptive sampling framework for reinforce-style llm training. arXiv e-prints, p. arXiv–2510. Cited by: Adaptive Sampling and Rollout Allocation in RLVR. Xu et al. (2026) H. Xu, S. Chen, R. Qiu, Y. Yan, C. Luo, M. Cheng, J. He, and H. Tong Prune as you generate: online rollout pruning for faster and better rlvr. External Links: 2603.24840, Link Cited by: Dynamic Difficulty Estimation for Reasoning LLMs. Yang et al. (2024) A. Yang, B. Zhang, B. Hui, B. Gao, B. Yu, C. Li, D. Liu, J. Tu, J. Zhou, J. Lin, K. Lu, M. Xue, R. Lin, T. Liu, X. Ren, and Z. Zhang Qwen2.5-math technical report: toward mathematical expert model via self-improvement. External Links: 2409.12122, Link Cited by: Implementation Details. Yao et al. (2026) J. Yao, Y. Hao, H. Zhang, H. Dong, W. Xiong, N. Jiang, and T. Zhang Optimizing chain-of-thought reasoners via gradient variance minimization in rejection sampling and rl. Advances in Neural Information Processing Systems 38, p. 163245–163284. Cited by: Introduction, Introduction, Introduction, Introduction, Adaptive Sampling and Rollout Allocation in RLVR, Dynamic Difficulty Estimation for Reasoning LLMs, Implementation Details, Implementation Details, Implementation Details, Implementation Details. Yu et al. (2026) Q. Yu, Z. Zhang, R. Zhu, Y. Yuan, X. Zuo, Y. Yue, W. Dai, T. Fan, G. Liu, L. Liu, et al. Dapo: an open-source llm reinforcement learning system at scale. Advances in Neural Information Processing Systems 38, p. 113222–113244. Cited by: Introduction, Adaptive Sampling and Rollout Allocation in RLVR. Zeng et al. (2026) Y. Zeng, Z. Sun, B. Ji, E. Min, H. Cai, S. Wang, D. Yin, H. Zhang, X. Chen, and J. Wang CurES: from gradient analysis to efficient curriculum learning for reasoning LLMs. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: Introduction, Introduction, Introduction, Adaptive Sampling and Rollout Allocation in RLVR, Dynamic Difficulty Estimation for Reasoning LLMs, State-Level Success Model., Implementation Details. Zhang (1992) J. Zhang The mean field theory in em procedures for markov random fields. IEEE Transactions on signal processing 40 (10), p. 2570–2583. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference, 3.5 Online Mean-Field Variational Inference. Zhang et al. (2025) Y. Zhang, M. Li, D. Long, X. Zhang, H. Lin, B. Yang, P. Xie, A. Yang, D. Liu, J. Lin, F. Huang, and J. Zhou Qwen3 embedding: advancing text embedding and reranking through foundation models. External Links: 2506.05176, Link Cited by: Models Selection, Implementation Details. Zheng et al. (2025) C. Zheng, S. Liu, M. Li, X. Chen, B. Yu, C. Gao, K. Dang, Y. Liu, R. Men, A. Yang, et al. Group sequence policy optimization. arXiv preprint arXiv:2507.18071. Cited by: Introduction, Adaptive Sampling and Rollout Allocation in RLVR. Zheng et al. (2026) H. Zheng, Y. Zhou, B. Bartoldson, B. Kailkhura, F. Lai, J. Zhao, and B. Chen Act only when it pays: efficient reinforcement learning for llm reasoning via selective rollouts. Advances in Neural Information Processing Systems 38, p. 124321–124346. Cited by: Adaptive Sampling and Rollout Allocation in RLVR, Dynamic Difficulty Estimation for Reasoning LLMs, Implementation Details, Implementation Details, Implementation Details. Zhou et al. (2003) D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Schölkopf Learning with local and global consistency. In Advances in Neural Information Processing Systems, S. Thrun, L. Saul, and B. Schölkopf (Eds.), Vol. 16, p. . External Links: Link Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference. Zhu et al. (2003) X. Zhu, Z. Ghahramani, and J. D. Lafferty Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), p. 912–919. Cited by: H. Related work of Graph-Based Learning and Probabilistic Inference.