Learning to Solve Hard Problems in RL for LLMs by Never Giving Up
Michael Noukhovitch, Hamish Ivison, Nathan Lambert and Aaron Courville (Mila and Ai2) show that RL for LLMs improves easy problems far more than hard ones, a pattern they call the Matthew Effect, and propose Never Give Up (NGU), which keeps sampling a problem until one rollout is correct.
Ask this paper
Matthew Effect: Standard RL gives large gains on problems the model already solves and small gains on hard problems, because fixed per-problem sampling spends most compute on easy problems.
Never Give Up: NGU keeps generating samples for each problem until one is correct. With asynchronous RL, easy problems finish in a few samples and the saved compute goes to harder problems.
Results: On Deepscaler NGU improves performance per unit of compute, with the largest gains on harder problems. On the Manufactoria coding task, standard GRPO with a per-test reward never fully solves problems mixing easy and hard tests, while NGU keeps progressing until it solves them fully.
Best practices: The paper studies the design choices behind NGU, including robustness to off-policy samples, and argues that scalar pass rates hide how poorly RL does on the hardest problems.
Abstract
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.