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

AI summary

Overview

Research area: Reinforcement learning (RL) for large language model post-training, specifically how compute is allocated across problems of varying difficulty.

Technical level: Intermediate. The paper assumes familiarity with GRPO-style policy gradient methods, advantage estimation, group baselines, and on-policy versus off-policy rollouts.

Scope: The paper documents a systematic bias in how RL improves LLMs across a difficulty distribution, diagnoses its cause as inefficient compute allocation, and proposes a sampling method, Never Give Up (NGU), that reallocates compute from easy to hard problems.

What This Paper Is About

Practitioners assume that training an LLM with RL on a mix of easy and hard problems will improve performance across the whole distribution. The authors show this is false: RL improves performance roughly in proportion to how well the model already performed, so easy problems improve a lot and hard problems improve very little. They name this the Matthew Effect in RL for LLMs and propose Never Give Up, an adaptive sampling scheme that keeps drawing completions for an unsolved problem instead of giving up and moving on.

Key Contributions

1. Names and demonstrates the Matthew Effect in RL for LLMs. Across three open-source RL-trained models and three domains, the authors show that RL gains scale with the initial model's accuracy, calling this a form of cumulative advantage after Merton (1968).

2. Rejects the "signal loss" explanation and proposes "signal efficiency" instead. Increasing completions per prompt K under a fixed total batch size (K ∈ {4, 8, 16, 32}, N ∈ {64, 32, 16, 8}) does not fix the effect; K = 4 performs best overall, especially on the hardest problems, because large K wastes compute re-admitting already-solved prompts into the batch.

3. Introduces Never Give Up (NGU). NGU resamples a prompt with probability p_NGU until a correct completion is found, giving a geometric distribution of samples with an average of K/(1-p). Combined with asynchronous RL, this filters easy prompts quickly and shifts training batches toward hard prompts.

4. Identifies design practices for NGU and extends the effect to per-test difficulty. The authors ablate off-policy staleness windows, advantage rescaling schemes ("anchoring the positives"), and reward shaping, and propose the Harness-Aware Matthew Effect for coding tasks where difficulty varies between tests within a single problem.

Main Findings

• The Matthew Effect holds across domains and models. Using Olmo 3.1 RL-Zero Math on AIME, DeepCoder on LCBv5, and DeepSWE on SWEBenchVerified, compared to their initial models (Olmo 3 7B Base, Deepseek-Qwen-14B, Qwen3-32B), RL improves easy problems most and hard problems least.

• More completions per prompt does not fix hard problems. With total batch size N × K held constant, K = 4 outperforms K = 8, 16, and 32, with the gap clearest on the hardest GSM8k Platinum problems. Increasing K also increases the chance of catching a spurious failure on an easy prompt, which re-includes that prompt in training.

• Smaller K shifts training batches toward harder prompts over time. Partitioning the training set into four equal difficulty quartiles shows that by step 200 the K = 4 setting has filtered easy prompts more aggressively than K = 32, concentrating batches on harder examples.

• NGU improves the hardest subset. On the GSM8k Platinum testbed with N = 64, K = 4, and p_NGU = 0.95, NGU yields pass@1 gains concentrated on the extra-hard subset, which the baseline struggles with.

• NGU needs a staleness filter, but stale negatives can still help as a baseline. Performance rises from T = 1 to T = 4 steps of retained completions, then falls at T = 8 and T = 16. Reusing older completions only for the GRPO baseline helps rather than hurts.

• "Anchoring the positives" beats downsampling. Ablations on GSM8k show baseline GRPO at extra-hard 47.1 ± 6.4; NGU with p = 1.0 collapses to 2.7 ± 1.0; NGU p = 0.75 with synchronous RL reaches 14.8 ± 5.2; NGU p = 0.75 with asynchronous RL and downsampling reaches 63.9 ± 5.5; NGU p = 0.75 with asynchronous RL and anchoring the positives reaches 87.9 ± 2.2.

• Never resampling easy prompts degrades them. Excluding prompts solved in 16/16 completions (following An et al., 2025) causes the easiest prompts to degrade early in training and eventually all subsets except the hardest to degrade.

• NGU scales to harder math. Training Qwen 3 4B-base on a 10k subset of Deepscaler math and evaluating on AIME 2025 and BRUMO Nov 2025, NGU with p_NGU ∈ {0.5, 0.75, 0.875} (theoretical average K of 32, 64, 128) improves the hard/easy trade-off relative to baseline K ∈ {16, 32, 64} with N ∈ {8, 4, 2}. With difficulty buckets defined by pass@64 (hard = 0, medium averaging 2.9%, easy averaging 46.1%), NGU beats fixed larger K on the hardest subset without sacrificing as much on easy problems.

• NGU outperforms an explicit curriculum. A baseline that sets K per prompt from the model's initial performance matches NGU on the hardest subset but degrades easy-problem performance, since difficulty changes over training.

• The Harness-Aware Matthew Effect appears in coding. On Manufactoria with Qwen3 4B Instruct, no Matthew Effect is visible when difficulty is assigned at step 0, but re-classifying difficulty after roughly 100 steps of prompt/harness adaptation reveals the effect clearly.

• NGU solves coding problems end to end. Standard GRPO with per-test reward solves roughly 80% of coding tests but rarely passes all tests for any problem and rarely exceeds 20% success on the hardest tests. With p_NGU = 0.95, NGU continues improving on hard tests until it learns to pass all tests for full problems.

• NGU recovers from a suboptimal objective. Starting both runs from the final GRPO baseline checkpoint after 3000 steps, per-test reward with NGU approximately matches all-tests reward in compute efficiency, suggesting RL for LLMs does not suffer the plasticity loss that characterizes the primacy bias in RL trained from scratch.

Methodology in Plain English

The authors first audit existing RL-trained models, grouping evaluation prompts into difficulty buckets based on the initial model's own pass rates, then plotting how much RL improved each bucket. That establishes the effect.

To isolate the cause, they build a controlled testbed: Qwen 2.5 0.5B Instruct trained on GSM8k Platinum, with evaluation problems sampled from 1024 initial-model completions into four difficulty levels at pass@1 of 25% (easy), 10% (medium), 5% (hard), and 0% (extra-hard), where 3/4 of extra-hard problems are never solved in 1024 samples. Training uses GRPO with asynchronous off-policy rollouts, filtering prompts that produce no gradient (all-correct or all-incorrect groups) and using active sampling to refill the batch.

They then test the "signal loss" explanation by sweeping K from 4 to 32 while keeping total batch size constant, and track which difficulty quartiles appear in the training batch over time.

NGU is defined simply: sample K completions; if all are correct, drop the prompt; if all are wrong, keep sampling with probability p_NGU instead of giving up. This produces a geometric sample count with mean K/(1-p). Because the pipeline is asynchronous, filtered easy prompts are immediately replaced by harder ones rather than stalling the batch. The authors then ablate what to do with the accumulating off-policy completions: how old a completion may be before it is discarded (T), and how to rescale advantages when old negatives are dropped. Their preferred scheme, "anchoring the positives," keeps positive-completion advantages and rescales negatives to (n+/n−)(1 − r̄) so the update group's advantages still sum to zero.

The method is then validated at larger scale — Qwen 3 4B-base on a 10k Deepscaler subset, compute-matched at roughly 120 H100 hours with three seeds — and on the Manufactoria coding benchmark, where difficulty exists between tests inside a single problem rather than only between problems.

Why This Matters

The paper reframes RL post-training as a performance-per-compute allocation problem, and shows that a widely used default (fixed K completions per prompt) systematically misallocates that compute. It also argues that single scalar benchmark scores hide this failure, motivating denser evaluation signals.

Real-world applications:

• Reasoning assistants for math. The AIME and BRUMO results show that targeting the hardest unsolved competition-style problems is where NGU-style sampling buys the most, relevant to tutoring and scientific reasoning tools.
• Code generation and repair. Solutions that pass most tests but not all are a common failure mode; NGU's ability to drive full test-suite completion directly targets this.
• Agentic software engineering. DeepSWE on SWEBenchVerified is used as one of the three motivating domains, and the failure mode of partial progress maps onto multi-step software agents.
• Post-training compute budgeting. Labs paying for H100 hours can use the compute-matching methodology and NGU's adaptive allocation to get more capability per unit of compute.

Industry relevance: Any organization running GRPO or similar group-baseline RL on LLMs has a default K setting, and this paper suggests that default is likely too large — and that asynchronous infrastructure unlocks compute savings that synchronous pipelines cannot capture.

Future Directions

• Extending to multi-step, agentic environments. The authors explicitly call out this as future work; the current setting is a simple contextual bandit rather than an MDP.
• Characterizing when NGU fails. The limitations section notes that if a training distribution skews heavily toward difficult problems, NGU's iterative sampling produces more asynchronously off-policy groups and yields a worse training signal. The exact boundaries are not established.
• Combining NGU with curricula and other methods. The authors state their approach is orthogonal to difficulty curricula, loss modifications, and test-time search, but combinations are not evaluated.
• Denser evaluation signals. The conclusion argues that scalar values are insufficient for accurate LLM evaluation, implying a need for difficulty-stratified reporting, but no concrete scheme is proposed.

Target Audience

Researchers and engineers working on RL post-training for LLMs will get the most from this paper, particularly those who own sampling configuration (K, N, batch construction) or asynchronous rollout infrastructure. It is also useful for evaluation researchers interested in why aggregate benchmark numbers can mask difficulty-dependent failure, and for practitioners on math-reasoning or code-generation teams deciding where to spend post-training compute. Readers without a background in policy gradient methods and advantage baselines will find the middle sections demanding.

Authors’ 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.