Learning to Solve Hard Problems in RL for LLMs by Never Giving Up
Paper introduces Never Give Up adaptive sampling, fixing RL's 'Matthew Effect' where compute is wasted on easy problems and hard problems see little improvement.
Researchers identify a 'Matthew Effect' in reinforcement learning for LLMs, where RL yields large gains on easy problems but minimal improvement on hard ones because compute is misallocated. They propose Never Give Up (NGU), an adaptive sampling method that keeps generating samples for a problem until one is correct, using asynchronous RL to filter easy problems cheaply and concentrate compute on hard ones. NGU improves performance per compute on the Deepscaler math benchmark and iteratively solves the Manufactoria coding task where standard GRPO with per-test reward fails.
- RL training disproportionately improves easy problems, dubbed the Matthew Effect
- NGU samples until correct, reallocating compute from easy to hard problems
- Uses asynchronous RL and off-policy robustness best practices
- Fully solves Manufactoria coding tasks that GRPO cannot complete
Full article223 words · extracted from huggingface.co · click to collapse
We demonstrate that training LLMs with RL does not improve performance equally across a dataset. RL shows large improvements on easy problems that an LLM is already good at solving, but small improvements on hard problems. We call this the Matthew Effect in RL for LLMs, after the phenomenon of cumulative advantage from economics and network science summarized as "the rich get richer". The naive explanation is that hard problems require more compute to find a solution. We argue that modern RL methods are exacerbating the issue by wasting too much compute on easy problems and instead should dynamically reallocate how they use compute. We introduce Never Give Up (NGU), a simple adaptive sampling method that keeps generating samples for a problem until one is correct. By leveraging asynchronous RL, this naturally uses fewer samples to filter out easy problems and allocates more compute to solving harder problems. We investigate the design choices that affect NGU, such as off-policy robustness, and develop a set of best practices. On the math benchmark Deepscaler, NGU improves performance per compute, especially on harder problems. On a recent coding task, Manufactoria, standard GRPO with a per-test reward fails to fully solve problems that have a range of easy and difficult tests. NGU iteratively improves, solving harder and harder tests, until it learns to fully solve coding problems.
Text extracted automatically; images, tables and formatting may be missing. Original: https://huggingface.co/papers/2609.13443