Michael Noukhovitch - Blog

Learning to Solve Hard Problems in RL for LLMs by Never Giving UpSep 15, 2026Table of ContentsWhat is your eval actually measuring?What causes the Matthew Effect?Never Give Up on hard problemsAsync RL staleness and tricks for NGUNGU at a bigger scale: MathNGU on a different scale: CodeThe Matthew Effect is a Primacy Bias, sort ofLimitationsConclusionAcknowledgementsCitationThis is a blog post for my recent paper on RL post-training of LLMs: introducing the Matthew Effect and proposing to solve it with Never Give Up. It is presented interactively and less formally, more like how I give the talk. For a deeper, more technical dive, check out the paper on arxiv and code on github.What is your eval actually measuring? #Every good RL practitioner has no doubt seen an eval curve go up. Here is the AIME 2025 eval during our RL training of Olmo 3.1 RL-Zero Math(1) (1)see Olmo 3.1 blog post and arxivTraining Olmo 3 7B base with RL on Dolci RL-Zero math improves its overall math ability. Or does it?What does this curve really mean?Our eval is an average over 30 AIME questions. Let’s break those 30 questions down into 3 levels of difficulty. Every question that our initial, pre-RL model gets 0 for pass@32 will be labelled “hard”. The other questions we’ll divide evenly by into “medium” and “easy” based on their pass-rates. So our initial pass@1 averages will be 0%, 3.8%, 22.7% for our subsets. How do you think performance on each subset will evolve?Our AIME evals during Olmo 3.1 RL-Zero split into three levels of difficulty by their initial accuracy. Easy AIME problems improve drastically but problems that start with pass@32=0 mostly end with pass@32=0!Averaging our AIME eval was hiding something important: the majority of our improvements are coming from the easiest problems going from somewhat solved to mostly solved. The hardest problems are barely improving. This is clearly visible if you look at how each example’s solve rate changes over time (see plot in the margin). ⊕ Accuracy of each AIME eval example over training. We order examples by difficulty from top (initial model pass@32=0) to bottom (initial model pass@1 > 30%). The hardest examples (top rows) barely improve over training. The model mainly learns to better solve easy and medium-difficulty examples that were already reasonably-well solved. We call this discrepancy the Matthew Effect. But this is for math RL on LLMs. What about other domains?We evaluate code RL and agentic RL using Deepcoder and DeepSWE, two nice open-source projects that released models and logs. We can use the initial model to split each benchmark into difficulty buckets (Deepseek-R1-Distilled-Qwen-14B on LCBv6) or we can use existing task length/difficulty labels (SWEBench).The gains from RL are proportional to how easy the problems are. We connect this bias to a similar phenomenon in network science and economics, the Matthew Effect(2) (2)Merton (1968), also see Wikipedia , generally summarized as “the rich get richer”.We therefore propose The Matthew Effect in RL for LLMsRL improves performance on a task in proportion to a model’s initial competence—making easy tasks easier while hard tasks often remain difficult.What causes the Matthew Effect? #You might assume the issue has to do with GRPO. If we just don’t get a correct answer to our problem in our $k$ sampled completions, then we don’t get any gradient and can’t improve on this problem.(3) (3)Xiong et al (2025) call this signal loss One possible answer is to sample more completions i.e. larger $k$.(4) (4)Other approaches include using priveleged information and curriculum learning. These are generally complimentary to our approach.To test this out, we train Qwen 2.5 0.5B Instruct with GRPO on GSM8k platinum and test on the same. We split our dataset into difficulty levels using initial pass@1: easy (25%), medium (10%), hard (5%), and extra-hard (0%) problems. We vary $k \in \{4, 8, 16, 32\}$ but keep batch size fixed.Smaller k solves harder problems than bigger k. Our GSM8k eval, split by initial difficulty, as previously. Surprisingly, $n=64$ prompts and $k=4$ completions is a better setting for solving hard problems than $n=8$ prompts and $k=32$ completions.It turns out that smaller $k=4$ is actually best! Why is this happening?Lets look at what our training batch is actually composed of. Since we filter any prompt whose completions are all correct or incorrect, our training batch must always be composed of problems with some completions right, some wrong. We plot what percentage of our batch is our easy subset and our extra hard subset and how this changes over time.Larger $k$ increases the chance of finding a rare correct solution to a very hard problem. So, naively, we expect it to have more hard problems in the batch. The issue is that larger $k$ also increases the chances of finding a rare incorrect solution to an easy problem.GSM8k Platinum, prompt difficulty in training batch. Tracking the actual prompts that make it into our training batch, by difficulty. $k=32$ solves more hard problems at the beginning but there’s an inflection point at 200 steps after which $k=4$ overtakes it.Early in training, $k=32$ finds rare solutions to hard problems. But after the inflection point around step 200, $k=4$ does better. $k=4$ filters any problem that is solved in $4/4$ completions. In contrast, for $k=32$ to filter the same problem, it must be solved much more: $32/32$. $k=4$ ends up spending much less compute on easy problem, especially when they get a rare incorrect solution. The inflection point is when the benefit of finding rare correct answers to hard questions is outweighted by wasting compute training on rare incorrect answers to easy questions.Because of our asynchronous RL for LLMs setup(5) (5)Async RLHF (Noukhovitch et al, 2025) is a blatant self-citation but also the first async RL for LLMs paper. See also PipelineRL (Piche et al, 2025) , all the compute we save filtering easy problems is used to train on harder problems. We argue the issue behind the Matthew Effect isn’t just undersampling for hard problems, but spending too much compute on easy problems.(6) (6)In contrast to signal loss, we term this signal efficiencyNever Give Up on hard problems #Our goal is therefore to only use small $k$ for easy problems but have large $k$ for hard problems. We propose a simple, but effective method of adapting asynchronous RL sampling: Never Give Up. We start sampling some small amount $k$. If a prompt is solved within the first $k$ completions, train on it! If a prompt is fully solved in $k/k$ completions, then we can easily and quickly filter it.The tricky part is if all completions are wrong. With probability $p$, we never give up and add the prompt back to our generator in order to sample $k$ more completions. We keep track of our old completions and when we do solve the problem, train on our whole $k * \text{rounds of NGU}$ completions. This creates a geometric distribution for the number of samples we take: if we never solve the prompt, we expect to take $\frac{ \ \ k}{1-p}$ samples, in expectation.This method is implicitly adaptive. Whereas curriculum learning pre-sets the difficulty of a problem, we find that online, adaptive methods do better as easy problems can become more difficulty over training and vice-versa. On GSM8k, $k=4$ with NGU $p=0.9$ outperforms all values of standard GRPO with varied $k$. This is especially evident on the hardest subset.Never Give Up with k=4 outperforms all possible values of k. On GSM8k platinum, NGU with k=4 solve more hard problems than k=4 with the same compute, without degrading performance on easy problems.It does this by achieving the best of large $k$ early in training and small $k$ late in training.Never Give Up gets the best of both k=4 and k=32. NGU allows $k=4$ to keep retrying hard problems, solving them as well as $k=32$ early in training. NGU doesn’t overspend compute on easy problems, filtering them as fast as $k=4$ late in training.Async RL staleness and tricks for NGU #Astute readers might already see a downside to the method: stale completions. This section introduces two tricks for dealing with staleness, but its not necessary to the main message so feel free to skip it.If we take multiple rounds of NGU to get one correct completion, our initial $k$ completions will be pretty stale by the time we train on them. Stale negatives are known to be bad for LLMs and RL(7) (7)Async RLHF argues that data staleness slows down training, this was also true for deep RL. Le Roux et al (2025) show that stale negatives are particularly bad. so its important to filter completions to be below some age threshold.$T=4$ wins out but this leaves another issue: our GRPO baseline. Just because we don’t train on a stale completion doesn’t mean we shouldn’t use it in our GRPO baseline. Suppose we have 4 stale negative completions, 3 new negatives and just 1 new positive. We should treat our positive as the rare phenomenon it is and set our GRPO baseline to $\frac{1}{8}$. But if we only train on the newest 4 completions, our total group’s reward becomes non-zero $\frac{7}{8} - \frac{1}{8} - \frac{1}{8} - \frac{1}{8} = \frac{3}{8}$. Our options are to ignore the filtered completions from our baseline (ignore), to leave the baseline non-zero (no rescale), or to anchor the positive and rescale the negative advantages by $\frac{7}{3}$ to maintain total reward 0 (anchor pos).Overall, it makes sense to use all the samples you have for your GRPO baseline, even if you’re not training on them.(8) (8)This baseline + rescaling may be generally useful for async RL if there’s filtering of samples for being too off-policy.NGU at a bigger scale: Math #We scale up to a bigger math RL setup: DeepScaler with Qwen 3 4B base.(9) (9)generally following the setup of Li et al (2025)