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

Michael Noukhovitch; Hamish Ivison; Nathan Lambert; Aaron Courville

cs.LGSep 11, 2026

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

Authors: Michael Noukhovitch, Hamish Ivison, Nathan Lambert, Aaron Courville

Organizations: Mila, Université de Montréal · Allen Institute for AI · University of Washington · Trillium Labs

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.

Figures & tables

Figure 1: The Matthew Effect in RL for LLMs. We evaluate how RL improves performance using three different open-source RL-trained models from three domains: Olmo 3.1 RL-Zero Math on AIME, DeepCoder on LCBv5, and DeepSWE on SWEBenchVerified. We compare the RL-trained models to their initial models (Olmo 3 7B Base, Deepseek-Qwen-14B, Qwen3-32B), separating problems by difficulty. RL improves performance in proportion to the initial model’s performance: easy problems improve the most and hard problems improve the least.

Figure 2: More Completions-per-prompt

K

doesn’t necessarily solve harder problems. Under a fixed total batch size, using more completions per prompt (higher

K

, lighter lines) underperforms using 4 completions per prompt (

K=4

), even for harder problems.

Figure 3: Fewer Completions-per-prompt

K

can shift training batches towards harder prompts. Using fewer completions per prompt (darker lines) results in more of the training batch comprising of hard training examples. This is due to more aggressive filtering of easy samples which enables focusing compute towards solving harder problems.

Figure 4: Never Give Up improves on the hardest problems. Using NGU improves overall pass@1 (blue line on left), especially improving performance on the hardest subset of samples (red line on right). Baseline GRPO results from Figure 2 are shaded in grey.

Figure 5: Never Give Up achieves near pareto-optimality for training on hard prompts. Using NGU results in the highest proportion of difficult samples and lowest proportion of easy samples across all training steps, suggesting it gets the benefits of both small and large

K

through its dynamic allocation. Baseline GRPO results shaded in grey (see Figure 3 ).

Figure 6: Never Give Up requires filtering of stale/off-policy completions, but can use them for an improved GRPO baseline. We measure performance across training and across samples of different difficulties. Using older completions (

T>4

steps off-policy) results in deteriorating performance (left), but these completions can be used for baselining. Using them for anchoring the positives outperforms other baselining approaches, especially downsampling (right).

Figure 7: NGU can improve the performance trade-off between hard/easy samples. We train on Deepscaler with different values of

K

and eval on AIME and BRUMO 2025. NGU outperforms all options, especially on the hardest problems. Varying NGU

p

demonstrates a trade-off between improving on hard and easy evals, much like varying

K

. We show mean

\pm

std dev across three seeds.

Figure 8: The Harness-Aware Matthew Effect . Performance on easy, medium, and hard problems over training. We can determine problem difficulty based on the model’s own pass rate either at the start of training (left) or after 100 steps when the model has adapted to the novel prompt/harness (right). Using the adapted difficulty ratings leads to a clear demonstration of the Matthew effect.

Figure 9: Never Give Up enables solving the hardest tests on coding problems. NGU enables continuously improving on all tests even as GRPO plateaus (left). The difference between the two methods is on hard tests (center). NGU improves on the hardest tests and learns to pass all of a problem’s tests, while GRPO remains unable to pass all tests on even a single example (right).

Figure 10: Never Give Up can recover from a suboptimal model overfit to per-test reward . NGU with per-test rewards performs similarly to standard RL with all-test pass reward.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

	easy	medium	hard	extra
Baseline GRPO	100.0 ± 0.0	99.9 ± 0.1	99.6 ± 0.2	47.1 ± 6.4
+ NGU $p=1.0$	83.9 ± 0.7	61.2 ± 2.3	36.3 ± 3.3	2.7 ± 1.0
+ NGU $p=0.75$ + sync RL	99.0 ± 0.5	97.3 ± 0.5	93.8 ± 2.3	14.8 ± 5.2
+ NGU $p=0.75$ + async RL + downsampling	99.5 ± 0.3	96.7 ± 0.7	95.4 ± 0.9	63.9 ± 5.5
+ NGU $p=0.75$ + async RL + Anchor Pos	100.0 ± 0.0	99.2 ± 0.4	98.6 ± 0.3	87.9 ± 2.2

Appendix

Table 1: Ablating the differences between NGU vs Reinforce-Ada-Seq-Pos on GSM8k. Each design decision behind Never Give Up is shown to be crucial to performance: giving up with probability

p

, asynchronous RL, anchoring positives for rescaling reward baseline.

Figure 11: Never Give Up must filter previous completions if they are too stale/off-policy. Both overall (left) and per-difficulty (right), using more stale completions (lighter lines) lowers performance when using NGU.

Figure 12: Never Give Up can leverage filtered completions for an improved GRPO baseline. We compare using stale completions with Anchor Pos rescaling to not using filtered completions for the GRPO baseline and find previous, filtered completions can be beneficial.

Figure 13: Never Give Up can best leverage filtered completions for an improved GRPO baseline by rescaling rewards. We ablate three methods for using stale completions. Downsampling underperforms both other approaches, and anchoring the positive completions performs best at the end of training.

Figure 14: GSM8k with No Resampling of Easy Prompts. Following An et al. (2025) , we don’t resample any prompts that achieve a perfect 16/16 correct completions during training. This fundamentally shifts the data distribution and we quickly see degradation on easy problems as our model shifts to answering exclusively harder prompts.

	AIME 25	BRUMO 25	Average
Qwen 3 4B Base	7.63	16.3	12.6
N=2, K=64	20.3 $\pm$ 0.9	28.8 $\pm$ 0.7	24.5 $\pm$ 0.5
N=4, K=32	21.4 $\pm$ 1.3	29.2 $\pm$ 0.7	25.3 $\pm$ 0.5
N=8, K=16	20.0 $\pm$ 1.5	29.6 $\pm$ 1.4	24.8 $\pm$ 1.0
+ NGU p=0.875	21.8 $\pm$ 0.2	31.2 $\pm$ 1.3	26.5 $\pm$ 0.6
+ NGU p=0.75	21.3 $\pm$ 2.1	31.6 $\pm$ 1.5	26.4 $\pm$ 0.7

Appendix

Table 2: Deepscaler final pass@1 by dataset. We show the pass@1 over three seeds for each setting of our GRPO baselines

K

and our NGU settings

p_{NGU}

. Results are mean

\pm

std dev over three seeds. *Darling results are taken from the original paper which trained on a different 10k random subset.

	Easy	Medium	Hard	Total
N=2, K=64	23.3 $\pm$ 1.9	15.3 $\pm$ 1.5	2.5 $\pm$ 0.2	11.5 $\pm$ 0.5
N=4, K=32	26.0 $\pm$ 2.5	15.4 $\pm$ 1.8	2.5 $\pm$ 1.1	12.2 $\pm$ 0.5
N=8, K=16	26.8 $\pm$ 2.6	14.5 $\pm$ 3.6	1.6 $\pm$ 0.3	11.7 $\pm$ 1.0
+ NGU p=0.875	26.8 $\pm$ 1.7	16.3 $\pm$ 0.9	4.3 $\pm$ 1.2	13.5 $\pm$ 0.6
+ NGU p=0.75	28.1 $\pm$ 0.2	16.8 $\pm$ 3.3	3.0 $\pm$ 1.2	13.4 $\pm$ 0.7
+ NGU p=0.5	25.1 $\pm$ 2.3	17.9 $\pm$ 2.2	3.3 $\pm$ 1.9	13.0 $\pm$ 0.6

Appendix

Table 3: Deepscaler improvement in pass@1 by difficulty subset. We plot the improvement in pass@1 over the initial Qwen 3 4B-base model after RL training, by difficulty splits. Results are mean

\pm

std dev over three seeds.

Figure 15: NGU reallocates compute to more difficult prompts in Deepscaler. As in GSM8k, Figure 3 , we plot the ratios of the easiest and hardest prompts in our update batch over training. NGU increases the proportion of hard prompts and decreases the proportion of easy prompts. As before, NGU achieves the best of large $K$ early in training and small $K$ late in training.

Hyperparameter	Value
KL beta	0.0
Learning rate	$1\times 10^{-6}$
Total Steps	2000
Temperature	1.0
Completions Per Prompt $K$	16
Prompts per Batch $N$	32

Appendix

Table 4: Hyperparameters for the Qwen2.5-0.5B-Instruct on GSM8K

Figure 16: Difficulty of Deepscaler 10k dataset for Qwen 3 4B base. We take 32 samples on each prompt in the dataset and calculate the overall difficulty of the dataset. We find that a significant amount of data has pass@32 = 0 for the initial model. Dashed lines indicate borders between difficulty levels.

Hyperparameter	Value
KL beta	0.0
Learning rate	$1\times 10^{-6}$
Total Steps	1000
Temperature	1.0
Completions Per Prompt	16
Prompts per Batch	8

Appendix

Table 5: Hyperparameters for Qwen3-4B-Base on Deepscaler Math

Hyperparameter	Value
KL beta	0.01
Learning rate	$5\times 10^{-7}$
Total Steps	1500
Temperature	1.0
Completions Per Prompt	16
Prompts per Batch	32

Appendix

Table 6: Hyperparameters for Qwen3-4B-Instruct-2507 on Manufactoria

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,727 papers

IsoCompute Playbook: Optimally Scaling Sampling Compute for LLM RL
Mar 12, 2026Zhoujun Cheng, Yutao Xie, Yuxiao Qu +12Reinforcement Learning RL Post-Training
UC San Diego · MBZUAI-IFM · Carnegie Mellon University
Mechanistically Interpreting the Role of Sample Difficulty in RLVR for LLMs
May 27, 2026Yue Cheng, Jiajun Zhang, Xiaohui Gao +3Reinforcement Learning RL for Language Model Reasoning
Beijing Jiaotong University · AntGroup · Northwestern Polytechnical University +2
DecompRL: Solving Harder Problems by Learning Modular Code Generation
Jul 2, 2026Juliette Decugis, Fabian Gloeckle, Francis Bach +2RL for Code Generation Code Generation
FAIR at Meta · Inria · École Normale Supérieure +2

Mar 12, 2026J/K move · Enter open · S save

IsoCompute Playbook: Optimally Scaling Sampling Compute for LLM RL

Zhoujun Cheng, Yutao Xie, Yuxiao Qu, Amrith Setlur+11

UC San Diego · MBZUAI-IFM · Carnegie Mellon University

Reinforcement Learning RL Post-Training Language Model Scaling Laws

Open paper AskPDF arXiv

While scaling laws guide compute allocation for LLM pre-training, analogous prescriptions for reinforcement learning (RL) post-training of large language models (LLMs) remain poorly understood. We study the compute-optimal allocation of sampling compute for on-policy RL methods in LLMs, framing scaling as a compute-constrained optimization over three resources: parallel rollouts per problem, number of problems per batch, and number of update steps. We find that the compute-optimal number of parallel rollouts per problem increases predictably with compute budget and then saturates. This trend holds across both easy and hard problems, though driven by different mechanisms: solution sharpening on easy problems and coverage expansion on hard problems. We further show that increasing the number of parallel rollouts mitigates interference across problems, while the number of problems per batch primarily affects training stability and can be chosen within a broad range. Validated across base models and data distributions, our results recast RL scaling laws as prescriptive allocation rules and provide practical guidance for compute-efficient LLM RL post-training.

Abstract

Reinforcement Learning

Explore similar work

IsoCompute Playbook: Optimally Scaling Sampling Compute for LLM RL

Mechanistically Interpreting the Role of Sample Difficulty in RLVR for LLMs

DecompRL: Solving Harder Problems by Learning Modular Code Generation