Never Give Up: why easy problems eat the RL budget
A deep dive into the Matthew Effect, and how adaptive sampling gives hard problems another chance.
The key idea is actually deeper than "hard problems need more samples." The paper argues that standard RL has a compute-allocation problem: its training mechanism naturally keeps spending compute on problems that already have useful learning signal, while problems that need exploration are often discarded too early.
First: what is RL actually doing here?
For an LLM, imagine the prompt is:
"Solve this math problem."
The model generates several completions:
The verifier says which answers are correct.
Methods such as GRPO use the relative rewards of these samples to determine which generated behaviors should become more or less likely.
Very roughly:
So RL needs contrast.
If every sample is wrong:
there isn't a successful trajectory in that group to reinforce.
Likewise, if everything is correct:
there is little useful distinction between the samples.
So the interesting case is:
because now RL has a signal saying:
"Something about this successful trajectory is worth learning."
This is crucial to understanding the Matthew Effect.
Why do easy problems naturally win?
Suppose the model currently has:
Easy problem
Probability of solving = 80%
Hard problem
Probability of solving = 2%
You give both problems 4 attempts.
For the easy problem:
✓ ✓ ✗ ✓
You almost certainly get a successful trajectory.
For the hard problem:
✗ ✗ ✗ ✗
Most of the time, you get no successful trajectory at all.
So even though the hard problem is precisely the one where the model has more to learn, the RL algorithm has much less usable signal from it.
That's the first part of the Matthew Effect.
The model already has a foothold on easy problems, so RL can find successful behavior and reinforce it.
The hard problem has no foothold yet, so RL struggles to get the first successful trajectory that would allow it to learn.
The authors explicitly observe this pattern across math, coding, and agentic coding: problems the base model could already solve tend to improve substantially, while the hardest problems improve much less.
And this creates a feedback loop
This is where the "rich get richer" analogy becomes useful.
Imagine the model has:
Why?
Because every time RL encounters the easy problem, it frequently gets successful examples.
Those successful examples reinforce useful behavior.
So the model becomes even better at the easy problem.
But the hard problem keeps producing:
Therefore it doesn't get comparable reinforcement.
So you get:
Already-good capability → more successful samples → more learning signal → even better capability.
while:
Weak capability → few successful samples → little learning signal → remains weak.
That's the Matthew Effect the paper identifies.
But wait... why not just increase K?
This is the really interesting part of the paper.
You might say:
"Fine. If hard problems aren't producing enough successful samples, just sample 32 times instead of 4."
That sounds completely reasonable.
For a hard problem with 2% success probability:
4 samples
Probability of at least one success:
1 − 0.98⁴ ≈ 7.8%
32 samples
1 − 0.98³² ≈ 47.5%
So yes, 32 samples gives the hard problem a much better chance of discovering a successful trajectory.
But there is a catch.
The same thing happens to easy problems
Suppose an easy problem has:
95% chance of success.
With K=4:
✓ ✓ ✓ ✓
It gets filtered because there's nothing particularly interesting left to learn.
Great.
The compute can move elsewhere.
But with K=32, you might get:
There is one wrong sample.
Now the problem is no longer an all-correct group.
It can enter the RL update.
So you've just spent 32 rollouts on a problem that was already almost solved.
This is the paper's important insight:
The authors' experiments found that simply increasing K from 4 to 32, while keeping total compute fixed, did not solve the Matthew Effect. In their setup, K=4 could actually perform better, particularly on the hardest problems.
This is where "signal loss" becomes "signal efficiency"
This distinction is probably the most important conceptual takeaway from the paper.
The obvious diagnosis is:
Hard problems don't get enough positive samples.
That's signal loss.
But the authors argue there's another problem:
We're wasting too much compute extracting signal from easy problems.
That's signal inefficiency.
Imagine you have 100 GPU-hours.
Standard fixed sampling
You might effectively spend:
But the marginal value of another rollout on an easy problem may be tiny.
The hard problem might need 20 attempts before the model happens to discover the key reasoning trajectory.
So the question shouldn't be:
"How many samples should every problem get?"
It should be:
"How much compute does this particular problem need?"
That's the conceptual shift NGU makes.
What does Never Give Up actually do?
Instead of saying:
"Every problem gets K=32."
or
"Every problem gets K=4."
NGU says:
Start small. Observe what happened. Decide whether this problem deserves more compute.
For example:
Problem A
Clearly easy.
Stop.
Don't waste another 28 samples.
Problem B
Standard GRPO would normally discard this group because there is no positive sample.
NGU says:
Not solved yet. Try again.
Now you've finally found a successful trajectory.
That successful trajectory can become the seed for learning.
That's the core idea behind Never Give Up.
The clever part is asynchronous RL
This is what makes the compute reallocation actually work.
Imagine you have 100 GPU workers.
With ordinary synchronous training, everyone effectively works in batches.
So you can end up with:
NGU instead uses an asynchronous queue.
So when an easy problem finishes:
The compute isn't sitting around waiting.
This gives NGU something like dynamic compute allocation:
So the number of samples becomes a function of difficulty.
That's why the method can get something close to the benefits of large K for hard problems while retaining the efficiency of small K on easy ones.
There's an even deeper RL reason
Here's the part I'd emphasize if you're trying to really understand the paper.
RL isn't simply:
"Train on everything."
It is:
"Use sampled experience to change the policy."
Therefore, the distribution of experiences you feed into RL matters enormously.
Suppose your training distribution gradually becomes:
Then your model is receiving disproportionately more optimization pressure from the easy region.
And there's another subtle feedback loop.
As the model improves:
Easy → even easier
Those problems become increasingly close to deterministic success.
Their marginal learning value drops.
But a fixed sampling system doesn't necessarily recognize that.
It keeps asking:
"Give me another 32 samples."
NGU effectively asks:
"Did this problem still teach us anything?"
If the answer is no, move on.
Why coding makes this especially interesting
Imagine a programming problem has 10 hidden tests.
The model currently passes:
The model is mostly right.
Standard RL can happily reinforce the behavior because it receives substantial reward.
But the last two tests represent the difficult edge cases.
So the model can settle into:
"I have a pretty good solution."
NGU's repeated sampling gives it more opportunities to encounter trajectories that eventually handle those difficult cases.
The training process can therefore move:
rather than repeatedly reinforcing the already-correct majority.
The paper reports exactly this qualitative behavior on Manufactoria: standard GRPO with per-test rewards improves but fails to fully solve certain problems, whereas NGU continues improving on harder tests until it can fully solve problems.
So what does RL "do by nature" that supports this?
It's not that RL inherently must have the Matthew Effect.
It's that common LLM RL setups create conditions that favor already-solvable problems.
Three mechanisms matter:
① RL needs informative reward variation
If all sampled trajectories are wrong:
0 0 0 0
there's little direct positive behavior to reinforce.
Easy problems naturally produce mixed/correct samples more often.
② Fixed rollout budgets ignore problem difficulty
Giving every problem:
K = 16
assumes every problem has roughly the same compute requirement.
They obviously don't.
Some problems need 2 attempts.
Some need 100.
Fixed K therefore inevitably overcomputes some and undercomputes others.
③ Learning reinforces what the model can already discover
If the model has a 30% chance of finding a successful reasoning trajectory, RL sees those trajectories relatively often.
If it has a 0.1% chance, RL almost never sees one.
So the learning process has an asymmetry:
That's essentially the rich-get-richer loop.
And this is why the paper's name is actually quite good
Never Give Up isn't saying:
"Keep sampling every problem forever."
It's saying:
Don't throw away a problem merely because the first few attempts failed.
There's a massive difference.
NGU essentially says:
while traditional fixed-budget sampling says:
Problem → K attempts → whatever happened → NEXT PROBLEM
That tiny change turns the training system from:
static compute allocation
into:
adaptive compute allocation.
The deepest takeaway
The problem isn't simply that RL doesn't sample hard problems enough. It's that fixed-budget RL has no reason to spend more compute on a problem just because it's hard.
"Stop letting the easy ones eat the budget" is a good summary.
The interesting contribution isn't merely "sample hard problems more."
It's:
Let each problem earn the right to consume more compute.
Easy problems prove they're easy and leave.
Hard problems fail, stay in the queue, and get more chances.
That is what breaks the feedback loop behind the Matthew Effect.
One technical caveat: NGU isn't literally "keep sampling until correct" with no safeguard. The paper uses probabilistic requeueing, so genuinely impossible or extremely unproductive problems don't consume compute forever, and it also discusses stale/off-policy samples in the asynchronous setup.