Efficient RLVR Scheduling via Graph-Structured Online Difficulty Estimation

• URL: http://arxiv.org/abs/2608.17941v1
• Date: Tue, 18 Aug 2026 16:01:00 GMT
• Title: Efficient RLVR Scheduling via Graph-Structured Online Difficulty Estimation
• Abstract summary: Reinforcement learning with verifiable rewards (RLVR) improves the reasoning capabilities of large language models.<n>We propose a graph-based online difficulty estimator that shares rollout feedback across related samples.<n>Our framework can be integrated into sample-selection and rollout-allocation schedulers, enabling difficulty-adaptive exploration without dedicated probing.
• Score: 31.644163847918495
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Focus When Necessary: Adaptive Routing and Collaborative Grounding for Training-Free Visual Grounding [56.38477453373368]
  LazyMCoT is a dynamic and training-free framework that adaptively allocates visual grounding efforts based on sample difficulty.<n>LazyMCoT rivals training-based approaches by simultaneously improving reasoning accuracy and reducing average inference latency.
  arXiv  Detail & Related papers  (2026-06-15T03:17:44Z)
• Breaking the Pre-Sampling Barrier: Activation-Informed Difficulty-Aware Self-Consistency [10.079669716138763]
  Self-Consistency (SC) is an effective decoding strategy that improves the reasoning performance of Large Language Models (LLMs)<n>It suffers from substantial inference costs because it requires a large number of samples.<n>We propose Activation-Informed Difficulty-Aware Self-Consistency (ACTSC) to address these limitations.
  arXiv  Detail & Related papers  (2026-02-10T06:05:11Z)
• VADE: Variance-Aware Dynamic Sampling via Online Sample-Level Difficulty Estimation for Multimodal RL [38.782188833641676]
  Group-based policy optimization methods like GRPO and GSPO have become standard for training multimodal models.<n>They suffer from a critical emphgradient vanishing problem when all responses within a group receive identical rewards.<n>We propose textbfVADE, a sampling framework via online sample-level difficulty textbfEstimation.
  arXiv  Detail & Related papers  (2025-11-24T08:59:54Z)
• Your Pretrained Model Tells the Difficulty Itself: A Self-Adaptive Curriculum Learning Paradigm for Natural Language Understanding [53.63482987410292]
  We present a self-adaptive curriculum learning paradigm that prioritizes fine-tuning examples based on difficulty scores predicted by pre-trained language models.<n>We evaluate our method on four natural language understanding (NLU) datasets covering both binary and multi-class classification tasks.
  arXiv  Detail & Related papers  (2025-07-13T19:36:17Z)
• TACO: Think-Answer Consistency for Optimized Long-Chain Reasoning and Efficient Data Learning via Reinforcement Learning in LVLMs [50.820065021136024]
  DeepSeek R1 has significantly advanced complex reasoning for large language models (LLMs)<n>Recent methods have attempted to replicate R1's reasoning capabilities in multimodal settings.<n>We propose TACO, a novel reinforcement learning algorithm for visual reasoning.
  arXiv  Detail & Related papers  (2025-05-27T06:30:48Z)
• Automating Dataset Updates Towards Reliable and Timely Evaluation of Large Language Models [81.27391252152199]
  Large language models (LLMs) have achieved impressive performance across various natural language benchmarks. We propose to automate dataset updating and provide systematic analysis regarding its effectiveness. There are two updating strategies: 1) mimicking strategy to generate similar samples based on original data, and 2) extending strategy that further expands existing samples.
  arXiv  Detail & Related papers  (2024-02-19T07:15:59Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  Cross-modal retrieval relies on well-matched large-scale datasets that are laborious in practice. We introduce a novel noisy correspondence learning framework, namely textbfSelf-textbfReinforcing textbfErrors textbfMitigation (SREM)
  arXiv  Detail & Related papers  (2023-12-27T09:03:43Z)
• Split-PU: Hardness-aware Training Strategy for Positive-Unlabeled Learning [42.26185670834855]
  Positive-Unlabeled (PU) learning aims to learn a model with rare positive samples and abundant unlabeled samples. This paper focuses on improving the commonly-used nnPU with a novel training pipeline.
  arXiv  Detail & Related papers  (2022-11-30T05:48:31Z)
• ZigZag: Universal Sampling-free Uncertainty Estimation Through Two-Step Inference [54.17205151960878]
  We introduce a sampling-free approach that is generic and easy to deploy. We produce reliable uncertainty estimates on par with state-of-the-art methods at a significantly lower computational cost.
  arXiv  Detail & Related papers  (2022-11-21T13:23:09Z)
• Hardness of Samples Need to be Quantified for a Reliable Evaluation System: Exploring Potential Opportunities with a New Task [24.6240575061124]
  Evaluation of models on benchmarks is unreliable without knowing the degree of sample hardness. We propose a Data Scoring task that requires assignment of each unannotated sample in a benchmark a score between 0 to 1.
  arXiv  Detail & Related papers  (2022-10-14T08:26:32Z)
• DiscrimLoss: A Universal Loss for Hard Samples and Incorrect Samples Discrimination [28.599571524763785]
  Given data with label noise (i.e., incorrect data), deep neural networks would gradually memorize the label noise and impair model performance. To relieve this issue, curriculum learning is proposed to improve model performance and generalization by ordering training samples in a meaningful sequence.
  arXiv  Detail & Related papers  (2022-08-21T13:38:55Z)
• On Covariate Shift of Latent Confounders in Imitation and Reinforcement Learning [69.48387059607387]
  We consider the problem of using expert data with unobserved confounders for imitation and reinforcement learning. We analyze the limitations of learning from confounded expert data with and without external reward. We validate our claims empirically on challenging assistive healthcare and recommender system simulation tasks.
  arXiv  Detail & Related papers  (2021-10-13T07:31:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.