New Method Targets Efficient LLM Reasoning Training by Sampling Hard Problems First

Training large language models to solve reasoning problems through reinforcement learning can be computationally expensive, especially when generating many candidate solutions. A new technique called HeaPA (Heap Sampling and On-Policy Query Augmentation) aims to make this process more efficient by being smarter about which training problems to focus on.

The Core Problem#

Existing approaches often rely on fixed pools of training problems or only loosely adapt which problems get prioritized as the model improves. This leads to wasted computational effort: some problems become too easy once the model makes progress, while others remain too hard to be useful yet. Traditional uniform sampling fails to track this moving boundary between what the model can and cannot do.

How HeaPA Works#

The new method maintains a dynamic, bounded pool of training problems that evolves during training. Its key innovations include:

• Frontier-focused sampling: Uses a heap-based approach to identify and concentrate on problems at the boundary of the model's capability—neither trivially easy nor impossibly hard
• On-policy pool growth: Adds new problems to the training pool based on what the model currently generates, without requiring additional teacher models or overhead
• Lightweight validation: Employs asynchronous checking to verify new problems without slowing training
• Stability mechanisms: Re-estimates pool statistics to handle correlated problems and carefully reinserts examples to maintain training stability

Results and Scope#

The researchers tested HeaPA across two training datasets, multiple training frameworks, and seven different benchmarks. The method consistently improved accuracy and reached target performance levels while using fewer total computations. Performance gains were especially pronounced when training mid-to-large scale models. The authors have released their training code publicly.

The work addresses a fundamental efficiency challenge in modern LLM training: allocating limited computational resources where they matter most, rather than spreading them uniformly across problems the model has already mastered or cannot yet solve.