RL and the set of solvable problems

Pass@k
$x;$ $\rho_x$	a problem; probability that one sample solves it
$k$	samples allowed per problem
$n,$ $c$	samples drawn per problem for the estimate; how many of them are correct
$\Delta_{\rm SE}$	sampling efficiency gap: base pass@256 minus RL pass@1
Training
$\pi_\theta,$ $\pi_{\rm ref}$	policy being trained; reference policy of the KL penalty
$\beta$	weight of the KL penalty
$\epsilon_{\rm low},$ $\epsilon_{\rm high}$	lower and upper clipping widths of the probability ratio (0.2 and 0.4 in ProRL)

Context. RLVRreinforcement learning with verifiable rewards: RL on problems whose answers a program can check, with reward 1 for a correct final answer or passing all unit tests and 0 otherwise is how the recent reasoning models are trained, and the hope behind it comes from games, where RL found strategies no human had shown it. For a language model the question is what the trained model can solve that its starting model cannot, and average accuracy cannot answer it, because a model that solves a problem once in 500 attempts scores as failing it. Yue et al. (2025) measure pass@ $k$ the chance that at least one of $k$ independent samples is correct, averaged over the problems of a benchmark with $k$ up to 1024 for pretrained models and their RLVR-trained versions, and find that the trained model solves almost no problem its starting model cannot. Liu et al. (2025) train with ProRLprolonged RL: thousands of RL steps on a broad mix of verifiable tasks, kept stable by a KL penalty whose reference model is reset from time to time, RL run for thousands of steps on many kinds of tasks, and find that it does solve new ones.

For one problem $x$ , write $\rho_x$ the probability that a single sample from the model solves problem $x$ ; its benchmark average is pass@1 for the chance that one sample solves it; then pass@ $k$ on that problem is $1-(1-\rho_x)^k$ . At $k=1$ the benchmark average is the mean of $\rho_x$ , and as $k$ grows it approaches the fraction of problems with $\rho_x>0$ , the ones the model can solve at all (its coverage). Training on a 0/1 reward raises $\rho_x$ where the model already succeeds fairly often and can push it to zero where it rarely does, so it can raise pass@1 and lower pass@ $k$ at large $k$ at the same time. Yue et al. find exactly this after a few hundred steps of standard RLVR on math, code and visual reasoning. The trained model samples correct answers more often, the problems it solves are nearly a subset of those its starting model solves, and the starting model overtakes it as $k$ grows. Liu et al. find that the set of solvable problems does grow when RL runs for thousands of steps on tasks the starting model does badly at; the gain is largest where the starting model's pass@128 is lowest, and smallest, sometimes negative, on math it already does well.

Setting. For math, Yue et al. use the zero-RLRL applied directly to a pretrained base model, with no supervised fine-tuning first setting: Qwen2.5 base models at 7B, 14B and 32B and LLaMA-3.1-8B, against their RLVR versions released by SimpleRLZoo, trained with GRPOgroup relative policy optimization: a PPO-style policy-gradient method with no learned value function, whose advantage is a response's reward standardized within the group of responses sampled for the same prompt on GSM8K and MATH problems with a correctness reward only, plus two models strong on AIME, Oat-Zero-7B and DAPO-32B. For code and visual reasoning, where zero-RL is unstable, the starting model of each pair is already fine-tuned (instruction-tuned, or for DeepCoder-14B, DeepSeek-R1-Distill-Qwen-14B), and the steps below still call it the base model. Both models of a pair are sampled with the same zero-shot prompt at temperature 0.6 (top-p 0.95, up to 16,384 tokens). Pass@ $k$ is computed per problem from $n\ge k$ samples, $c$ of them correct, with the unbiased estimator $\widehat{\text{pass@}k}=1-\binom{n-c}{k}\Big/\binom{n}{k},$ averaged over problems, with $n$ the largest $k$ plotted (128, 256 or 1024). For controlled comparisons they retrain Qwen2.5-7B with six RL algorithms in one codebase, with no KL penalty $\beta\,\mathrm{KL}(\pi_\theta\|\pi_{\rm ref})$ subtracted from the objective: $\beta$ times the Kullback-Leibler divergence of the trained policy $\pi_\theta$ from a fixed reference policy $\pi_{\rm ref}$ , which keeps the two close, on 2,000 Omni-MATH problems, testing on 821 held-out ones and on MATH500. Liu et al. start instead from DeepSeek-R1-Distill-Qwen-1.5B, a small model already distilledtrained by supervised fine-tuning to imitate the outputs of a stronger teacher model, here the long reasoning traces of DeepSeek-R1 from DeepSeek-R1, and train it for more than 2,000 steps (about 16,000 GPU hours) on 136,000 problems in math, code, STEM, instruction following and logic puzzles from Reasoning Gyman open collection of about 100 procedurally generated puzzle tasks with automatic verifiers, such as graph coloring, mazes and family-relationship questions, with GRPO, a KL penalty and periodic resets of its reference (Step 5). They evaluate at temperature 0.6 with up to 32,000 tokens, comparing the starting model, an intermediate checkpoint and the final model.

Main findings (all empirical). In every model family and benchmark Yue et al. test, the RLVR model leads at small $k$ and the starting model leads at large $k$ ; with the 32B model on Minerva, the starting model solves about 9% more of the problems at $k=128$ . On AIME24 at $k=1024$ , 63.3% of the problems are solved by both models, 13.3% only by the starting model and none only by the RLVR model; on MATH500 at $k=128$ the shares are 92.4%, 3.6% and 1.0%. Six RL algorithms end a few points apart in pass@1 and all leave the starting model ahead at large $k$ , training longer raises pass@1 while pass@256 falls, and the one intervention that lifts the curve at every $k$ is distillation from a stronger model. Liu et al.'s 1.5B model improves average pass@1 over its starting model by 15.7 points on math, 14.4 on code, 25.9 on GPQA Diamond, 22.0 on IFEval and 54.8 on Reasoning Gym puzzles, and on tasks where the starting model is weak its pass@ $k$ rises at every $k$ , including on a puzzle type left out of training that the starting model never solves.

Consequences and limits. The two papers agree on the mechanism and differ on where it applies. RLVR as usually run, a few hundred steps from a model that already does the task, mostly moves probability toward solutions the model already produces; it reduces the number of samples needed to find a solution, and its coverage is bounded by what the starting model reaches by sampling. A claim that RL adds a capability therefore needs pass@ $k$ at large $k$ , with the starting model given the same prompt and sampling budget. Coverage grows when the starting model has $\rho_x$ near zero on a task it can learn, and Liu et al.'s largest gains come on puzzles and code where the 1.5B model starts weak, after long training kept stable by a KL penalty with resets. Liu et al.'s comparison has confounds. Some of the starting model's zero pass rates are formatting failures (Step 7); the starting point is a distilled 1.5B model with much room to grow, where Yue et al. use pretrained base models; and longer training, the resets, the task mix and the longer context are never separated. Yue et al.'s large- $k$ numbers on problems with a numeric answer can include lucky guesses, which they check by hand only on subsets, and their runs are a few hundred steps, mostly on math, where models may be heavily trained on similar data before RL.

Step 1 (Yue et al.)

The crossover appears in every family, task and benchmark. On GSM8K, MATH500, Minerva, OlympiadBench, AIME24 and AMC23, for Qwen2.5 at three sizes and LLaMA-3.1-8B, the RLVR curve starts higher and is flatter, so the base curve crosses it at $k$ in the tens or hundreds. Oat-Zero-7B and DAPO-32B, nearly 30 points above their base models on AIME24 at $k=1$ , are also overtaken at large $k$ . Code is the cleanest test, since passing every unit test by chance is nearly impossible, and Code-R1 and DeepCoder-14B show the same pattern on LiveCodeBench, HumanEval+ and MBPP+, as does a vision-language model on MathVista and MathVision. On math a correct final answer can come from a wrong chain of thoughtthe written reasoning a model produces before its final answer, so they read the solutions to the hardest solved problems (solve rate below 5%): on GSM8K, 24 of the 25 such problems the base model solves have at least one correct chain (23 of 25 for the RLVR model), and on AIME24, 5 of 6 (4 of 6). The base model's lead at large $k$ is therefore not mostly guessing, though the check covers only a few problems.

Step 2 (Yue et al.)

RLVR reweights solutions the base model already samples. Per problem, RLVR moves accuracy toward 1 on problems the base model solves fairly often and moves more problems to exactly 0, which is how pass@1 rises while coverage falls. A two-group example (mine) shows the arithmetic. Of 100 problems, half have $\rho_x=0.02$ and half 0.6 under the base model, and after RL 40 of the first half sit at 0, the other 10 at 0.2, and the second half at 0.95; pass@1 rises from 0.31 to about 0.50 while pass@256 falls from 0.997 to 0.60. In the data, the rare problems that only the RLVR model solves on MATH500 at $k=128$ , about 5, are all solved by the base model within 1024 samples. Perplexity $\exp\big(-\frac1T\sum_{t=1}^T\log P(y_t\mid x,y_{\lt t})\big)$ for a response $y$ of $T$ tokens: the exponentiated average negative log-likelihood, low when the model would likely write that response makes the same point for whole solutions: under the base model, the RLVR model's sampled solutions have perplexities in the low part of the range of the base model's own samples, so they are solutions the base model was already likely to write, and their perplexity falls further as training continues. The figure below uses a simple model of sharpening, not the paper's data.

Step 3 (Yue et al.)

Algorithm, training length, rollouts, KL and temperature move the curves but keep the crossover. With Qwen2.5-7B retrained by PPO, GRPO, REINFORCE++, RLOO, ReMax and DAPO, in-domain pass@1 ranges from 23.8 to 28.1 against 10.2 for the base model, while pass@256 stays near the base model's 69.1 (67.0 to 69.7). They define the sampling efficiency gap $\Delta_{\rm SE}$ = the base model's pass@256 minus the RL model's pass@1: how far RL is from making the base model's coverage reachable in one sample $\Delta_{\rm SE}$ , which is above 40 points for every algorithm. Training longer trades one for the other. From step 150 to step 450 of GRPO, training-set pass@1 rises from 26.1 to 42.5 and pass@256 falls from 66.3 to 64.3, below the base model's 67.2. Sampling 32 responses per prompt in place of 8 raises pass@ $k$ a little, and a KL penalty with coefficient 0.001 keeps pass@1 and lowers pass@128. RL also lowers output entropy, so they raise the RL model's temperature until its entropy matches the base model's at 0.6; its pass@ $k$ improves slightly and stays below the base model's, so lost entropy accounts for only part of the narrowing of coverage. At larger scale, Magistral-Medium, trained by RL alone from Mistral-Medium-3, solves about 7 more AIME24 and 8 more AIME25 problems at $k=1$ , and the gap shrinks steadily as $k$ grows.

Step 4 (Yue et al.)

Distillation from a stronger model raises the whole curve. DeepSeek-R1-Distill-Qwen-7B, trained to imitate DeepSeek-R1's reasoning traces, lies well above its base model Qwen2.5-Math-7B at every $k$ . Imitating a stronger teacher brings in solutions the student did not sample before, while RL on the student's own samples can only reinforce solutions the student already produces. The authors explain RLVR's limit the same way. The pretrained model's distribution is what makes exploration feasible in an enormous space of outputs, but samples far from it are almost always wrong and get reward 0, so policy gradient mostly strengthens what the pretrained model already proposes.

Step 5 (Liu et al.)

Long RL needs entropy kept up and a reference that moves. The obstacle to long runs is entropy collapsethe output distribution becoming sharply peaked early in RL, so sampled responses stop varying and the policy stops exploring. Once GRPO's samples for a prompt all agree, advantages computed within the group carry little signal. A high sampling temperature (1.2) only delays it. Two pieces come from DAPOa variant of GRPO (Yu et al., 2025) with several changes for long reasoning runs, among them the two below, clip-higherPPO's clipping range $[1-\epsilon_{\rm low},1+\epsilon_{\rm high}]$ on the probability ratio (a token's probability under the policy being updated over its probability under the policy that sampled it), with $\epsilon_{\rm high}\gt\epsilon_{\rm low}$ , so that low-probability tokens with positive advantage can grow more per update with $\epsilon_{\rm low}=0.2$ and $\epsilon_{\rm high}=0.4$ , and dynamic samplingdropping prompts whose sampled responses are all correct or all wrong, which give zero advantage to every response. They keep a KL penalty to a reference policy against the recent practice of dropping it, arguing that dropping suits pretrained base models while their starting model already writes coherent reasoning. As training goes on the KL term comes to dominate the loss and updates shrink, so whenever validation performance stalls or degrades they reset the reference to the current policywhy: the KL term then measures distance from a recent policy, so it still keeps each stretch of training stable but no longer pulls the model back to its start and reinitialize the optimizer. The final model comes out of eight runs separated by such resets, with instruction-following data added in the third, a penalty for responses that never terminate in the fourth and fifth, 32 rollouts per prompt in place of 16 in the sixth and seventh, and a 16,000-token context only in the last, about 200 steps. Entropy stays up, and validation pass@1 and pass@16 keep rising for more than 2,000 steps. The schedule was set by watching validation curves, and the paper reports no ablation of its pieces.

Step 6 (Liu et al.)

The weaker the starting model on a task, the more RL expands its coverage. Re-evaluating with 256 samples per problem on math, code, STEM, instruction following and 18 randomly chosen Reasoning Gym tasks, they find a strong negative correlation between the starting model's pass@128 on a task and the change in it after training. The curves fall into three kinds. On math benchmarks and LiveCodeBench, where the starting model's pass@128 is already high, pass@1 improves while pass@128 falls or stays put, as Yue et al. find. On tasks such as GPQA Diamond and mazes both improve, but early, and the final model adds little over the intermediate checkpoint. On Codecontests, TACO and some puzzles, pass@ $k$ keeps rising with training at every $k$ . To check that small gains go with familiar tasks, they score the starting model's answers by the Creativity Indexa measure of how little of a text can be pieced together from spans found in a reference corpus, here the Dolma pretraining corpus; low means heavy overlap, and the math and code tasks with small gains score low, consistent with the model having seen much similar text in pretraining.

Step 7 (Liu et al.)

Coverage grows on an unseen task type and on harder instances. On boxnet, a Reasoning Gym planning puzzle left out of training, the starting model's pass@ $k$ is 0 at every $k$ up to 256, while the final model's rises from 0.077 at $k=1$ to 1.000 at $k=256$ , above the intermediate checkpoint's (0.029 to 1.000) at every $k$ below 256. On graph coloring, trained only on 10-node graphs, accuracy falls with graph size for every model, but the final model keeps the highest pass@1 and pass@128 at every size from 6 to 20 nodes. Across prompts, the distribution of pass@1 on Codeforces and on the family-relationships puzzle moves from mostly zero to spread out or peaked at 1. These are cases Yue et al.'s setting does not reach. In them the starting model's $\rho_x$ is essentially zero, and RL finds solutions that sampling from it would not. On Reasoning Gym, though, the starting model often puts its answer in a LaTeX box where the verifier expects answer tags, which the authors note is easy to learn, so some zero pass rates there measure instruction following rather than reasoning; the paper does not check how much of the boxnet result this explains.

Terms

Pass@ $k$ per problem: $1-(1-\rho_x)^k$ ; its average is pass@1 at $k=1$ and tends to the share of problems with $\rho_x>0$ as $k$ grows
Unbiased estimator: $1-\binom{n-c}{k}/\binom nk$ from $n\ge k$ samples with $c$ correct
RLVR: RL against a program that checks answers or runs unit tests; reward 1 or 0
Crossover: RL model ahead at small $k$ , starting model ahead at large $k$ (Yue et al., all families and tasks)
Coverage: share of problems solved at least once in $k$ samples; RLVR's solved set is nearly a subset of the base model's
Sampling efficiency gap: $\Delta_{\rm SE}$ = base pass@256 minus RL pass@1; above 40 points for six algorithms
Matched-entropy test: raising the RL model's temperature to the base model's entropy narrows the gap only a little
Distillation: imitating a stronger teacher lifts pass@ $k$ at every $k$ , unlike RLVR
ProRL recipe: GRPO with clip-higher and dynamic sampling, a KL penalty whose reference is reset, eight runs, 136K diverse problems
Reference reset: set $\pi_{\rm ref}$ to the current policy and reinitialize the optimizer when validation stalls
Weak start, large gain: ProRL's change in pass@128 is strongly negatively correlated with the starting model's pass@128
Formatting confound: some starting-model zeros on Reasoning Gym come from answers in the wrong format

Quiz

A team reports that RL fine-tuning gives their model a new capability, citing a large gain in pass@1. What evidence would test the claim most directly?
In Yue et al., which way of training the small model raises pass@ $k$ at every $k$ , and why?
ProRL periodically resets the KL reference policy to the current policy. What problem does this address?

Sources

Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Yang Yue, Shiji Song, and Gao Huang. Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model? NeurIPS, 2025.
Mingjie Liu, Shizhe Diao, Ximing Lu, Jian Hu, Xin Dong, Yejin Choi, Jan Kautz, and Yi Dong. ProRL: Prolonged Reinforcement Learning Expands Reasoning Boundaries in Large Language Models. arXiv preprint, 2025.

Qiying Yu et al. DAPO: An Open-Source LLM Reinforcement Learning System at Scale. arXiv preprint, 2025.