HS-STAR - Hierarchical Sampling for Self-Taught Reasoners via Difficulty Estimation and Budget Reallocation - Research paper summary

Sep 15, 2026

Uploaded by Melati

Self-taught reasoners (STaRs) improve large language models’ mathematical reasoning by training on self-generated responses. Prior reward-guided approaches focus on response quality yet allocate a uniform sampling budget, ignoring that problem difficulty affects learning utility. HS-STAR studies this effect and finds boundary-level problems yield substantially higher learning value than easy or overly hard ones. With a fixed budget, HS-STAR uses lightweight presampling for difficulty estimation and then reallocates remaining samples to high-utility boundary problems, improving training data quality across benchmarks and backbone LLMs.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages17

Reading Time43 min

AccessFree to download

Introduction

Problem profiling and allocation

HS-STAR framework

Difficulty estimation

Budget reallocation

Experiments and results

HS-STAR: Hierarchical Sampling for Self-Taught Reasoners via Difficulty Estimation and Budget Reallocation Feng Xiong1 * , Hongling Xu* , Yifei Wang1,2 , Runxi Cheng3 , Yong Wang1†, Xiangxiang Chu1 1AMAP, Alibaba Group 2University of Chinese Academy of Sciences 3Tsinghua University [jingxun.xf@icloud.com](jingxun.xf@icloud.com) , [wangyong.lz@alibaba-inc.com](wangyong.lz@alibaba-inc.com) Abstract Self-taught reasoners (STaRs) enhance the mathematical reasoning abilities of large language models (LLMs) by leveraging selfgenerated 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 SelfTaught Reasoners. Given a fixed sampling budget, HS-STAR first performs lightweight presampling with a reward-guided difficulty estimation strategy to efficiently identify boundarylevel 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. 1 Introduction Large language models (LLMs) can improve their capabilities by training on self-generated data, characterizing them as self-taught reasoners (STaRs) (Zelikman et al., 2022 ; Yuan et al., 2023 ; Hosseini et al., 2024) . This paradigm is also referred to as reinforced self-training (Gulcehre et al., 2023) (ReST) or self-improvement (Huang et al., 2023) . For mathematical reasoning (Yang et al., * Equal contribution. † Corresponding author and project lead. 2025 ; Tian et al., 2025a ; Wang et al., 2025a), pioneer STaRs generally follow an iterative process: (1) generating candidate responses for a given math problem via temperature sampling; (2) selecting responses based on answer correctness; and (3) updating the model using either SFT or DPO (Singh et al., 2024 ; Pang et al., 2024 ; Wu et al., 2025) . Building on previous efforts, recent work has focused on enhancing STaRs by leveraging additional reward models, which can be categorized into two main directions. One line of work, known as reward-guided selection, introduces an auxiliary reward model to re-rank or filter responses based on their estimated quality, encouraging the model to exploit higher-quality trajectories (Yang et al., 2024 ; Zeng et al., 2025b ; Tu et al., 2025) . Another line of work, reward-guided decoding, leverages Monte Carlo Tree Search (MCTS), in which a process reward model (PRM) (Wang et al., 2024a) is trained and used to guide the decoding process, aiming to improve both final answer accuracy and the quality of intermediate reasoning steps (Zhang et al., 2024 ; Chen et al., 2024a) . However, these studies primarily focus on response quality through such reward-guided approaches, neglecting the utility of the problems themselves. Specifically, a uniform allocation of sampling budget across all problems fails to account for the varying difficulty levels of individual problems and their differential impacts on the learning process (Zhu et al., 2024) . Since autoregressive decoding is the principal bottleneck in STaRs, such an indiscriminate allocation strategy is highly inefficient. This issue raises two critical questions: (i) Profiling: Which difficulty level of problems are most beneficial for self-taught reasoners? Intuitively

FAQs

What problem does HS-STAR address in self-taught reasoners?

HS-STAR targets the inefficiency of uniform sampling budgets that ignore how different problem difficulty levels contribute varying learning utility to STaRs.

Why are boundary-level problems especially valuable?

Empirical findings show problems near the LLM’s reasoning capability boundary provide significantly greater learning utility than both easy and overly difficult problems.

How does HS-STAR use a fixed sampling budget effectively?

HS-STAR first performs lightweight presampling with reward-guided difficulty estimation to identify boundary-level problems, then dynamically reallocates the remaining budget to these high-utility problems during re-sampling.

Sep 15, 2026

Uploaded by Melati