Learning to Solve Hard Problems in RL for LLMs by Never Giving Up

Learning to Solve Hard Problems in RL for LLMs by Never Giving Up. By Michael Noukhovitch and three others, from Mila, the Université de Montréal, and three other institutions. Published on the eleventh of September. No code repository is linked to it.

Training language models with reinforcement learning does not improve performance equally across a dataset. The gains are large on easy problems that the model is already good at solving, and small on the hard ones. The authors call this the Matthew Effect in RL for LLMs, after the phenomenon of cumulative advantage from economics and network science, usually summarized as the rich get richer. Problems the model can already solve get better; problems it cannot solve stay out of reach.

The naive explanation is that hard problems simply require more compute to find a solution. The authors argue for something more pointed. Modern RL methods, they say, make the problem worse by wasting too much compute on easy problems, and they should instead reallocate their compute dynamically. The issue is not only how much is spent in total, but where it goes.

Never Give Up, or NGU, is a simple adaptive sampling method. For each problem, it keeps generating samples until one of them is correct. A problem is not dropped after a fixed number of failed attempts; it keeps being sampled until it yields a success. Difficulty never has to be estimated in advance. A problem reveals how hard it is by how long it takes to produce a correct sample, and the compute it receives follows from that.

The method leans on asynchronous RL, and the reallocation follows naturally from that. An easy problem produces a correct sample quickly, so it is filtered out using few samples. The compute it would otherwise have taken goes instead to solving harder problems, which keep drawing samples for longer. The authors also investigate the design choices that affect NGU, off-policy robustness among them, and develop a set of best practices for using it.

On the math benchmark Deepscaler, NGU improves performance per unit of compute, especially on the harder problems, which is where the Matthew Effect said gains were missing.

The second test is a recent coding task, Manufactoria, whose problems carry a range of easy and difficult tests. There, standard GRPO with a per-test reward fails to fully solve problems of that kind. NGU improves step by step, solving harder and harder tests, until it learns to fully solve the coding problems.

The diagnosis and the fix share one idea: compute should follow difficulty. Spending the same effort on every problem spends too much where success is cheap and too little where it is rare. Sampling until success lets the easy problems leave early and lets the hard ones stay as long as they need, which is how a method this simple is meant to push against the rich getting richer.