# HS-STaR: Hierarchical Sampling for Self-Taught Reasoners via Difficulty Estimation and Budget Reallocation

arXiv: https://arxiv.org/abs/2505.19866 · HTML: https://mlsanity.com/paper/2505.19866/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 22 of its 59 references that are in the map.
- First posted on arXiv 26 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 22 of 22)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone](https://mlsanity.com/paper/2404.14219/) (2024)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement](https://mlsanity.com/paper/2409.12122/) (2024)
- [SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wild](https://mlsanity.com/paper/2503.18892/) (2025)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [Scaling Relationship on Learning Mathematical Reasoning with Large Language Models](https://mlsanity.com/paper/2308.01825/) (2023)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [GPG: A Simple and Strong Reinforcement Learning Baseline for Model Reasoning](https://mlsanity.com/paper/2504.02546/) (2025)
- [Online Difficulty Filtering for Reasoning Oriented Reinforcement Learning](https://mlsanity.com/paper/2504.03380/) (2025)
- [Stop Summation: Min-Form Credit Assignment Is All Process Reward Model Needs for Reasoning](https://mlsanity.com/paper/2504.15275/) (2025)
- [Enhancing LLM Reasoning with Iterative DPO: A Comprehensive Empirical Investigation](https://mlsanity.com/paper/2503.12854/) (2025)
- [Towards Self-Improvement of LLMs via MCTS: Leveraging Stepwise Knowledge with Curriculum Preference Learning](https://mlsanity.com/paper/2410.06508/) (2024)
- [How Is LLM Reasoning Distracted by Irrelevant Context? An Analysis Using a Controlled Benchmark](https://mlsanity.com/paper/2505.18761/) (2025)
- [To Code or not to Code? Adaptive Tool Integration for Math Language Models via Expectation-Maximization](https://mlsanity.com/paper/2502.00691/) (2025)
- [D3: Diversity, Difficulty, and Dependability-Aware Data Selection for Sample-Efficient LLM Instruction Tuning](https://mlsanity.com/paper/2503.11441/) (2025)
- [DeepDistill: Enhancing LLM Reasoning Capabilities via Large-Scale Difficulty-Graded Data Training](https://mlsanity.com/paper/2504.17565/) (2025)
- [VCSearch: Bridging the Gap Between Well-Defined and Ill-Defined Problems in Mathematical Reasoning](https://mlsanity.com/paper/2406.05055/) (2024)
- [DAST: Difficulty-Aware Self-Training on Large Language Models](https://mlsanity.com/paper/2503.09029/) (2025)

## Built on by (most cited first, 18 of 18)

- [Emergent Hierarchical Reasoning in LLMs through Reinforcement Learning](https://mlsanity.com/paper/2509.03646/) (2025)
- [Code2World: A GUI World Model via Renderable Code Generation](https://mlsanity.com/paper/2602.09856/) (2026)
- [Video-STAR: Reinforcing Open-Vocabulary Action Recognition with Tools](https://mlsanity.com/paper/2510.08480/) (2025)
- [Harder Is Better: Boosting Mathematical Reasoning via Difficulty-Aware GRPO and Multi-Aspect Question Reformulation](https://mlsanity.com/paper/2601.20614/) (2026)
- [Everything in Its Place: Benchmarking Spatial Intelligence of Text-to-Image Models](https://mlsanity.com/paper/2601.20354/) (2026)
- [Position Bias Mitigates Position Bias:Mitigate Position Bias Through Inter-Position Knowledge Distillation](https://mlsanity.com/paper/2508.15709/) (2025)
- [Thinking with Map: Reinforced Parallel Map-Augmented Agent for Geolocalization](https://mlsanity.com/paper/2601.05432/) (2026)
- [FASA: Frequency-aware Sparse Attention](https://mlsanity.com/paper/2602.03152/) (2026)
- [What if Agents Could Imagine? Reinforcing Open-Vocabulary HOI Comprehension through Generation](https://mlsanity.com/paper/2602.11499/) (2026)
- [RLAE: Reinforcement Learning-Assisted Ensemble for LLMs](https://mlsanity.com/paper/2506.00439/) (2025)
- [Memory Grafting: Scaling Language Model Pre-training via Offline Conditional Memory](https://mlsanity.com/paper/2605.20948/) (2026)
- [UPRE: Zero-Shot Domain Adaptation for Object Detection via Unified Prompt and Representation Enhancement](https://mlsanity.com/paper/2507.00721/) (2025)
- [Taming Hallucinations: Boosting MLLMs' Video Understanding via Counterfactual Video Generation](https://mlsanity.com/paper/2512.24271/) (2025)
- [Q-Hawkeye: Reliable Visual Policy Optimization for Image Quality Assessment](https://mlsanity.com/paper/2601.22920/) (2026)
- [AR-MAP: Are Autoregressive Large Language Models Implicit Teachers for Diffusion Large Language Models?](https://mlsanity.com/paper/2602.02178/) (2026)
- [D2Evo: Dual Difficulty-Aware Self-Evolution for Data-Efficient Reinforcement Learning](https://mlsanity.com/paper/2605.17037/) (2026)
- [From Content to Knowledge: Lightning Fast Long-Video Understanding with Neural Knowledge Representations](https://mlsanity.com/paper/2606.11913/) (2026)
- [BIRD: Distilling Decision Boundaries into Rationales for MLLM Adaptation](https://mlsanity.com/paper/2609.33713/) (2026)

## Abstract (arXiv)

Self-taught reasoners (STaRs) enhance the mathematical reasoning abilities of large language models (LLMs) by leveraging self-generated responses for self-training. Recent studies have incorporated reward models to guide response selection or decoding, aiming to obtain higher-quality data. However, they typically allocate a uniform sampling budget across all problems, overlooking the varying utility of problems at different difficulty levels. In this work, we conduct an empirical study and find that problems near the boundary of the LLM's reasoning capability offer significantly greater learning utility than both easy and overly difficult ones. To identify and exploit such problems, we propose HS-STaR, a Hierarchical Sampling framework for Self-Taught Reasoners. Given a fixed sampling budget, HS-STaR first performs lightweight pre-sampling with a reward-guided difficulty estimation strategy to efficiently identify boundary-level problems. Subsequently, it dynamically reallocates the remaining budget toward these high-utility problems during a re-sampling phase, maximizing the generation of valuable training data. Extensive experiments across multiple reasoning benchmarks and backbone LLMs demonstrate that HS-STaR significantly outperforms other baselines without requiring additional sampling budget.