Learning to solve hard problems in RL for LLMs by never giving up

Introduces the "Matthew Effect" in RL post-training for LLMs: reinforcement learning disproportionately improves problems the model already handles, while the hardest problems stay unsolved. Empirical breakouts of AIME, GSM8K, DeepCoder/DeepSWE, and Manufactoria show aggregate eval gains hide that easy examples drive most progress. Experiments varying sample count k reveal a counterintuitive trade-off: large k finds rare correct solutions early but also wastes compute on rare incorrect completions for easy problems, causing the training batch to be dominated by middling examples. The author frames this as a signal-efficiency problem (spending compute on easy examples) distinct from signal loss (no gradient when no correct samples).

To address this, proposes Never Give Up (NGU): start with small k and, when all k completions fail, with probability p requeue the prompt and sample additional rounds until solved, yielding a geometric retry distribution. NGU preserves small-k filtering on easy prompts while recovering rare corrects for hard prompts; on GSM8K and scaled math (DeepScaler with Qwen 3 4B) NGU with k=4, p=0.9 outperforms fixed-k baselines on hardest subsets without degrading easy-example performance. Practical fixes for async RL staleness include an age threshold for stored completions and rescaling GRPO baselines to include filtered samples. NGU mitigates but does not eliminate the Matthew Effect across math and code domains.