PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Michael Noukhovitch, Hamish Ivison, Nathan Lambert, Aaron Courville

arXiv:2609.13443v1cs.LGcs.AI

TL;DR

RL gains are uneven across problem difficulty, favoring tasks an LLM already handles well. The paper introduces Never Give Up (NGU), an adaptive sampling approach, and reports improvements on difficult math and coding tasks. It concludes that better compute allocation can improve difficult-task performance.

  • Problem

    RL training can improve easy problems more than hard ones, leaving a gap in how performance gains are distributed across task difficulty.

    Source: §1 · pp. 1–2

  • Method

    Never Give Up (NGU) iteratively samples prompts until it finds a correct answer or probabilistically stops, using asynchronous RL to allocate fewer samples to easy prompts and more to hard ones.

    Source: §1 · p. 2

  • Results

    NGU outperforms strong RL baselines on the hardest math problems and passes all coding tests where standard RL stalls.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors conclude that simple scalar evaluations may be insufficient for accurate LLM evaluation and argue for denser evaluation signals.

    Source: §8 · p. 10

    NGU may be ineffective when a task distribution leans heavily toward difficult problems, because its iterative sampling can take longer than starting with a larger sample batch.

    Source: B Limitations · p. 16

Abstract

from arXiv · show

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.

1 Introduction

Reinforcement learning is a standard post-training method for LLMs, but its gains can favor problems the model already handles well. The introduction presents the Matthew Effect and proposes adaptive compute allocation as a way to address it.

  • Across three domains, RL gains are disproportionate: easy problems improve more than hard problems, which were problems the initial model was less likely to solve.The paper names this cumulative advantage the Matthew Effect in RL for LLMs.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • Equal compute across problems can exacerbate the effect, while naively sampling more completions for every prompt can add noise from spurious easy-problem failures.Source: §1 · p. 2
  • NGU resamples prompts until a correct answer appears, probabilistically abandons unresolved prompts, and uses asynchronous RL to spend fewer samples on easy problems and more on hard ones.The authors report that filtering stale rollouts from the loss while retaining them in advantage calculations can improve performance.Source: §1 · p. 2
  • On larger-scale math and code tasks, NGU outperforms strong RL baselines on the hardest problems and solves coding tests that standard RL cannot fully pass.Source: §1 · p. 2

2 The Matthew Effect in RL for LLMs

The paper finds that RL improvements track a model’s initial competence across math, code completion, and agentic coding. It frames this cumulative advantage as the Matthew Effect in RL for LLMs.

  • Across math, code completion, and agentic coding, initially easier tasks gain more from RL, while harder tasks show more limited improvement.Source: §2 · p. 2
  • The authors describe this cumulative advantage as analogous to the Matthew Effect in network science.Source: §2 · pp. 2–3
  • Unlike primacy bias studied in training-from-scratch settings, this effect depends on pretrained models’ existing biases and strong priors.Source: §2 · p. 3

3 Causes of the Matthew Effect

The section tests whether signal loss explains the Matthew Effect and finds that simply increasing completions per prompt does not solve it. Instead, completion count changes which prompts are filtered into training, motivating compute allocation that adapts to prompt difficulty.

Signal Loss?

  • In GRPO, a prompt whose K completions all fail receives no gradient, making signal loss a plausible explanation for weak learning on difficult prompts.The experiment tests this explanation by comparing K = 4, 8, 16, and 32 while holding total batch size constant.Source: §3 · p. 3
  • With a fixed total batch size, K = 4 performs best overall and on the hardest problems, so increasing K does not make signal loss the primary driver.The testbed fine-tunes Qwen 2.5 0.5B Instruct on GSM8k Platinum using four difficulty levels.Source: §3 · p. 3, Figure 2 · p. 4

Prompt Filtering

  • Larger K can include already-easy prompts after a single incorrect completion, while smaller K filters easy prompts more aggressively and shifts later batches toward harder examples.By step 200, K = 4 batches are more concentrated on harder examples than K = 32 batches.Source: §3 · p. 4, Figure 3 · p. 4

Signal Efficiency

  • Signal efficiency frames RL as optimizing performance per compute: large K can waste samples on solved prompts, while small K can undersample difficult ones.A low-K then high-K curriculum may address this trade-off, but explicit curricula can be brittle and hyperparameter-sensitive.Source: §3 · pp. 4–5

Never Give Up

  • NGU improves overall pass@1, with gains especially on the hardest subset compared with baseline GRPO.The figure identifies overall pass@1 on the left and the hardest subset on the right.Source: Figure 4 · p. 5

4 Countering the Matthew Effect with Never Give Up

Never Give Up (NGU) dynamically resamples unsolved prompts, quickly filtering easy ones while allocating more sampling to hard prompts. It improves hard-problem performance, but its use of prior completions requires care with stale negatives and advantage baselines.

Not Resampling Easy Prompts

  • Excluding easy prompts from later resampling can improve hard-problem performance at the expense of easy-problem performance.The training runs can regress on problems they had previously solved.Source: §4 · p. 5

Never Give Up

  • NGU resamples a prompt after all completions are wrong, continuing with probability pNGU and giving up otherwise.It stops sampling once it finds a correct answer; the resulting total sample count has a geometric distribution.Source: §4 · p. 5
  • NGU outperforms previous baselines on extra-hard problems while dynamically shifting the training batch toward difficult prompts.Asynchronous replenishment of quickly filtered easy prompts enables this reallocation.Source: §4 · p. 5, Figure 5 · p. 6

NGU: Maintaining Previous Completions

  • Keeping earlier completions lets NGU form a larger GRPO group when a correct answer appears, increasing the advantage for rare positives.Stale negative completions can be harmful, so the method filters them by age.Source: §4 · pp. 5–6
  • Performance improves when retained completions are less than T = 4 steps old, then declines at T = 8 or 16.Older completions can still be used for baselining rather than the update.Source: §4 · p. 6, Figure 6 · p. 6

NGU: Maintaining Counts

  • Anchoring positives outperforms alternative baselines, especially downsampling, which discards useful negative completions.The approach keeps positive advantages fixed and rescales negative advantages to preserve a zero-sum update group.Source: §4 · pp. 6–7

5 Math: Scaling Up NGU

The authors evaluate NGU on a larger-scale Deepscaler math task against compute-matched baselines and a curriculum approach. Varying NGU’s sampling probability improves the hard/easy performance trade-off, while fixed difficulty-based sampling can hurt easy-problem performance.

Experimental Setup

  • The study trains Qwen 3 4B-base on a 10k Deepscaler subset and evaluates on AIME 2025 and BRUMO Nov 2025.Difficulty buckets use initial pass@64; hard prompts have pass@64 = 0.Source: §5 · p. 7
  • Experiments compare K settings with NGU probabilities chosen for theoretical average sampling ranges of K = 32, 64, and 128.Runs are compute-matched at approximately 120 H100 hours, with three seeds per setting.Source: §5 · p. 7

NGU improves the easy/hard performance trade-off

  • Varying pNGU improves hard-problem performance without sacrificing as much easy-problem performance as increasing baseline K.The authors attribute NGU’s success to having more difficult prompts in the training batch.Source: §5 · p. 7

NGU outperforms curriculum learning

  • Fixed larger K for initially hard prompts matches NGU on the hardest subset but degrades performance on easy problems.The results indicate that difficulty estimates can change during training.Source: §5 · p. 7

6 Coding: From Prompt Difficulty to Test Difficulty

Manufactoria places difficulty not only between prompts but among tests within a prompt; after accounting for harness adaptation, the paper finds a Matthew effect and tests NGU against standard GRPO. NGU continues improving on hard tests and eventually passes all tests on full problems.

6 Coding: From Prompt Difficulty to Test Difficulty

  • Manufactoria has 14–30 tests per problem, with final tests frequently hard enough that passing some tests is easier than passing all.The study trains Qwen3 4B Instruct on diverse coding problems and evaluates generalization to a test set.Source: §6 · p. 8
  • Reclassifying prompt difficulty after adaptation around step 100 reveals a Matthew effect that initial harness adaptation had obscured.The paper attributes early training to adapting to the novel task and prompt rather than true task improvement.Source: §6 · p. 8
  • Per-test GRPO learns roughly 80% of tests but rarely completes a problem, with most reward variation coming from inconsistent medium-difficulty tests (Sun et al., 2025).The paper interprets this as compute repeatedly revisiting partially solved tests instead of driving progress on the hardest unresolved tests.Source: §6 · pp. 8–9
  • NGU keeps improving on hard tests and eventually passes all tests on full problems, while standard GRPO stagnates on the hardest tests.The figure reports that GRPO does not pass all tests on even a single example.Source: Figure 9 · p. 9, §6 · p. 9
  • Starting both runs from the final GRPO baseline checkpoint after 3,000 steps, per-test reward with NGU approximately matches all-tests reward in compute efficiency, while showing recovery after suboptimal-objective training.Source: §6 · p. 9

7 Related Work

Related approaches target hard problems through several algorithmic and curriculum strategies. NGU differs by implicitly adapting sampling through asynchronous compute allocation, while Manufactoria results compare per-test NGU with an all-tests reward.

7 Related Work

  • Per-test-reward NGU performs similarly to standard RL with an all-test-pass reward.This comparison is presented in Figure 10.Source: Figure 10 · p. 9
  • Prior LLM methods address hard problems with external information, GRPO-loss changes, test-time search, or explicit curricula (Qu et al., 2026a; Wu et al., 2026; Tajwar et al., 2026).Curriculum approaches include removing easy problems, curating datasets, or adjusting sampled distributions (Shi et al., 2026; Qu et al., 2026b; Zheng et al., 2025).Source: §7 · pp. 9–10
  • NGU implicitly adapts the data distribution for performance per compute and differs from Reinforce-Ada-Seq-Positive’s signal-loss focus; its compute-efficiency benefit relies on asynchronous RL (Xiong et al., 2025).The paper also notes prior online curricula do not study code RL with variable-difficulty tests within one problem.Source: §7 · p. 10

8 Conclusion

The paper concludes that standard RL disproportionately underperforms on the hardest problems and proposes NGU as a way to allocate compute more effectively. It also reviews related work on RL scaling and methods for harder tasks.

8 Conclusion

  • Standard RL yields disproportionately poor performance on the hardest problems, while NGU is presented as a simple approach for substantially improving difficult-task performance through better compute allocation.The paper argues that scalar evaluation may be insufficient and calls for denser evaluation signals.Source: §8 · p. 10
  • Future work could examine more complex multi-step, agentic environments, while RL scaling remains a tradeoff between performance and compute (Khatri et al., 2025).The paper says scaling must continue to find efficient ways to solve increasingly hard problems.Source: §8 · p. 10

A Extended Related Work

B Limitations

NGU’s compute reallocation is most apt when the training distribution contains enough easy tasks to filter quickly.

B Limitations

  • NGU may be ineffective on mostly difficult task distributions, where iterative sampling can take longer and make completed groups more asynchronously off-policy.The paper particularly cautions about negative samples and advises against K = 1 with batch size fully controlled by pNGU.Source: B Limitations · p. 16

C Extra Results

The GSM8k results show that stopping easy prompts from being sampled can degrade their performance, while NGU’s design choices distinguish it from Reinforce-Ada-Seq-Pos. Ablations find that giving up probabilistically, asynchronous RL, and anchoring positives matter for performance.

C.1 Comparison to Reinforce-Ada

  • Reinforce-Ada targets signal loss from same-reward completions, whereas NGU targets signal efficiency by treating unlikely positives as useful and unlikely negatives as noise.Reinforce-Ada-Seq-Balance increases sampling on easy problems to seek unlikely negative samples.Source: §C.1 · p. 16
  • Reinforce-Ada-Seq-Pos continues until a positive completion, like NGU, but uses no giving-up probability, synchronous RL, and downsampling of negatives.It therefore stalls on prompts unsolvable by the model and waits for all completions before sampling another prompt.Source: §C.1 · pp. 16–17
  • On GSM8k, p = 1.0 stalls; synchronous NGU underperforms GRPO, and downsampling is less effective than anchoring positives.Downsampling also performs worse than using no rescaling; Table 1 summarizes the ablations.Source: §C.1 · p. 17, Table 1 · p. 17

C.2 GSM8k

  • The appendix reports overall and per-difficulty GSM8k results for varying completion age, advantage rescaling, and NGU baselining methods.Figures 11–13 cover these comparisons.Source: §C.2 · p. 17
  • Not resampling prompts solved 16/16 times shifts the prompt distribution and degrades easy subsets over training.The authors prefer avoiding explicit, irreversible changes to the prompt distribution.Source: §C.2 · p. 17

C.3 Deepscaler

The Deepscaler results examine final pass@1 and difficulty-specific improvements, alongside compute-allocation and sampling variants. NGU shifts training toward harder prompts, while curriculum and prompt-filtering choices expose trade-offs across difficulty levels.

C.3 Deepscaler

  • The Deepscaler evaluation reports final pass@1 on AIME and BRUMO; N = 16, K = 8 underperforms the other baseline settings.The GRPO baselines outperform those reported in previous work; Table 2 gives final results and Table 3 reports improvement by difficulty.Source: §C.3 · p. 17, Table 2 · p. 19, Table 3 · p. 19
  • Using more stale completions lowers NGU performance overall and by difficulty, so the method must filter completions that are too off-policy.Figure 11 compares outcomes as the maximum completion age varies.Source: Figure 11 · p. 18
  • Filtered completions can improve the GRPO baseline, and anchoring positive completions performs best at the end of training among the tested rescaling approaches.Downsampling underperforms the other two approaches.Source: Figure 13 · p. 18, Figure 12 · p. 18
  • A pass-rate-based difficulty curriculum improves the hardest subset but degrades the easiest and slightly underperforms the GRPO baseline.Prompts receive K = 4, 8, 16, or 32 according to estimated pass rate; the authors suggest easy prompts can change difficulty during training.Source: §C.3 · pp. 18–19
  • Stopping resampling once prompts reach 16/16 correct completions degrades performance on easy problems as training shifts toward harder prompts.Figure 14 shows the resulting degradation across subsets over training.Source: Figure 14 · p. 19
  • NGU decreases the share of easy prompts and increases the share of hard prompts in training, with large K best early and small K best late.The prompt-ratio analysis tracks the four difficulty groups and prompts with non-zero gradient.Source: §C.3 · p. 19, Figure 15 · p. 20

D Experimental Details

The experimental details describe asynchronous training infrastructure, task-specific setups, and NGU’s prompt-sampling procedure. The pseudocode combines fresh and eligible buffered completions, then passes mixed outcomes to GRPO or requeues all-wrong prompts probabilistically.

D Experimental Details

  • Experiments use asynchronous RL with in-flight updates to stay as on-policy as possible, DeepSpeed for training, and vLLM for inference.Source: D Experimental Details · p. 20

D.1 GSM8k

  • GSM8k runs for 2,000 steps on four L40S GPUs and take approximately 10 hours.Table 4 lists the Qwen2.5-0.5B-Instruct hyperparameters.Source: §D.1 · p. 20, Table 4 · p. 20

D.2 Deepscaler

  • Deepscaler uses a random 10k subset, checks overlap with evaluation problems, and assesses difficulty with the initial model before RL evaluation.The initial model uses temperature 0.7 and top-p 0.8 for difficulty estimates; the trained model is evaluated at temperature and top-p 1.Source: §D.2 · p. 20, Figure 16 · p. 21, Table 5 · p. 21

D.3 Manufactoria

  • Manufactoria follows the original Sun et al. (2025) setup, with a noted difference from the paper and code clarified through author communication.Each 3,000-step run uses two nodes of eight H100 GPUs for approximately 28 hours.Source: §D.3 · p. 21, Table 6 · p. 21

E Pseudocode

  • NGU collects K completions and rewards, merges non-stale buffered samples, sends mixed outcomes to GRPO, and requeues all-wrong prompts with probability pNGU.Prompts whose completions are all correct are dropped; an all-wrong prompt is also dropped when the continuation draw fails.Source: E Pseudocode · p. 22

Related papers

Loading 2609.13443v1…