CS Paper Radar

There Is No Free Lunch in RLVR: Every pass@1 Gain Has a pass@k Price

Yinuo Liu

cs.LG cs.AImath.OCstat.ML ·submitted 2026-10-29 03:43 UTC · v1
theorycode/data

Abstract

Reinforcement learning with verifiable rewards (RLVR) makes a language model solve more problems on the first try and fewer when given many tries: it raises pass@1 while the base model overtakes it at large sampling budget k. Is this a failure of RL to add reasoning, or a transient that more training removes? We settle the question with a theorem. The reversal is a price, and we compute its exact rate. Modeling RLVR as an exponential tilt of a base policy over strategies shared across prompts, we prove that under exclusive specialization every update that raises pass@1 strictly lowers the success of some prompt; a strictly positive price on prompts (Stiemke duality) is the exact condition, and being merely the best strategy on a prompt is provably not enough. When the loss reaches the hardest prompts, it forces a pass@k crossover, and the number of crossings is at most the sign variation of the shift in per-prompt success, a totally positive bound that is tight and that recovers the known single-crossover result as its order-preserving case. The crossover is not a bug to patch: a constrained update traces the exact pass@1 versus pass@k frontier, and removing the crossover entirely costs the entire pass@1 gain. The same tilt identity yields entropy collapse and the entropy-performance law with an identifiable exponent, unifying two literatures under one mechanism. Reinforcement cannot widen the reasoning frontier; it can only move along it, at a price we make measurable by a diagnostic that reads the bound, the order-preserving test, and the price from any evaluation log. There is no free lunch, only a price.

Comment
19 pages, 4 figures. Code and verification package (34/34 automated checks): https://github.com/yliusci/no-free-lunch-rlvr

Closest papers

Nearest neighbours by meaning across the whole index.

Wrong the Same Way: Cross-Prompt Sharing Both Suppresses and Amplifies Reward Hacking in RLVR

cs.LG cs.AI ·2026-11-09 ·Michael Li, Rohan Pandey, Ray Chen
published similarity 0.78
Abstract · Accepted at the Transitioning from Pre-Training to Post-Training Workshop at NeurIPS 2026

Two accounts of how reinforcement learning with verifiable rewards (RLVR) interacts with an imperfect verifier coexist: in one, reward hacking is inherited from the base model; in the other, RL amplifies it. We study both in a controlled environment small enough to compute the entire response distribution exactly. We vary the universality of a leak, or the fraction of prompts that accept the same wrong response, and the verifier's static false-positive rate. At its KL-regularized optimum, RLVR acts as a filter that reweights the accepted set without altering its composition, so the hack rate is inherited exactly. Taking that as a null model, a known decomposition writes the drift from it as a sum over prompts of covariances between reward and the empirical tangent kernel. The terms from other prompts vanish without parameter sharing. With sharing, every prompt that accepts a wrong answer pushes it up and every prompt that rejects it pushes it down through the baseline, in proportion to the model's probability of producing it there. A shared-parameter policy thus drives a leak that few prompts accept below the base rate and amplifies one that most prompts accept. At every convergent learning rate under Adam, SGD, and sampled GRPO, hacking ends higher at high universality than at low, but whether either end crosses the base rate depends on the step size. Independent per-prompt copies remove the dependence. The direction of this push depends on neither the verifier's error rate nor universality alone, but on how much of the model's kernel-weighted probability of a wrong answer falls on prompts that accept it, which frozen base model controls support. Verifier fixes should target the mistakes the model repeats across prompts: two patches that remove equally many errors differ by up to 38 points of true accuracy. We propose this alignment as a hypothesis for why earlier studies disagree.

0.14

When Pass@$k$ Crossovers Are Real - and Why: Paired Inference and the Markov Kernel of RLVR

cs.LG stat.ML ·2026-09-18 ·Chen Yang
highly cited similarity 0.75
Abstract · 47 pages, 8 figures. Revised title, expanded experiments and analysis, and updated author list

Reinforcement learning with verifiable rewards (RLVR) typically improves pass@1 but can fall behind its base model at large sampling budgets $k$, commonly interpreted as sharpening existing solutions. Because adjacent pass@$k$ estimates reuse generations, pointwise error bars cannot establish a crossover. We formulate paired inference on the RL-minus-base difference curve: a prompt-level multiplier bootstrap yields a one-sided dominance test and simultaneous confidence bands requiring both an early gain and a later loss. Among nine public RLVR checkpoints at 3k-16k token limits, only one narrowly meets this criterion before multiplicity adjustment; asymmetric truncation can create, mask, or reverse crossovers. On 1,060 deduplicated competition problems at 32k tokens, two 1.5B models exhibit certified crossovers around $k\approx10$-$60$, while two 7B models show no supported loss. A paired variance decomposition shows why adding prompts improves power more than deeper sampling. Prompts with identical base success probability diverge after RLVR, with dispersion replicating across independent generation halves and violating Lipschitz slope bounds for reasonable deterministic maps. Modeling RLVR as a Markov kernel, Jensen's inequality shows that conditional dispersion depresses pass@$k$ for $k\ge2$. Once dispersion is modeled, the conditional-mean log-odds slope is below one in every pair: RLVR improves hard prompts on average, while late-$k$ loss comes from a 2%-3% minority of base-solved prompts collapsing onto a repeated modal wrong answer and resisting prefix rescue up to 4,096 tokens. In controlled runs from one base model on 3,000 new problems, all four GRPO arms fall behind near $k\approx200$ and remain behind through $k=4096$, while SFT stays significantly ahead throughout.

0.47

On the Primacy Bias in RLVR Training

cs.AI ·2026-11-02 ·Phuc Minh Nguyen, Ngoc-Hieu Nguyen, Parshin Shojaee, Chinh Duc La, Duy Minh Ho Nguyen +4 more
similarity 0.74
Abstract

Reinforcement Learning with Verifiable Reward (RLVR) has emerged as a promising approach for enhancing the reasoning capabilities of large language models. However, it still remains unclear whether RLVR can extend reasoning capabilities beyond what is already encoded in the base model. In this paper, we study this question through the lens of primacy bias: the tendency of models to over-rely on already-learned representations, disproportionately improving performance on problems they already handle well while underexploring harder ones that require departing from those representations. Through our controlled experiments and large-scale analysis, we show that RLVR training on mixed data tends to further sharpen performance on easier problems while yielding only marginal gains on harder ones. We find that although hard problems lead to modest gains overall, they are actually the ones that help most in expanding the model's reasoning capabilities and pushing the representations. However, prolonged training on these hard problems may also hurt and lead to forgetting on easy problems. These findings help to better understand some of the prior conflicting observations about RLVR, specifically, why on (OOD) domains where the base model performs poorly, improvements on hard problems can expand reasoning; while on well-trained domains, forgetting can reduce performance and mask genuine gains obtained from hard problems.

0.08

What RL Brings to Reasoning: A Few Decisions the Base Model Would Not Make

cs.CL cs.LG ·2026-10-17 ·Siyu Zhang, Yuquan Lu, Yoshua Y. Li, Yifan Ding, Kun Zeng +5 more
code/data similarity 0.73
Abstract · 26 Pages, 8 figures Code: https://github.com/CyrusZhang04/WhatRLBrings

Reinforcement learning with verifiable rewards (RLVR) substantially improves mathematical reasoning, but what it adds to the base model remains unclear. We investigate this through a sequence of generation-time interventions on Qwen3-4B-Base, measuring how much of its RL-trained counterpart's gain each intervention recovers on 120 AIME problems. Power sampling with the same 8,192-token output limit brings no gain beyond greedy decoding. Yet borrowing the RL model's token only where the two models' greedy choices differ, roughly 4% of generated positions, recovers 90.5% of the pass@1 gain, with similar recovery across three model pairs on MATH-500. We find that even a single opening token has a substantial effect: forcing the base model to begin with "Alright" recovers 35% of the RL gain. The opening alone is insufficient, however. Later replacements after the same opening add another 5.2 percentage points to pass@1, and the fixed rules we test for inserting reflective words such as "Wait" do not reproduce this benefit. Sparse replacement also retains much of the base model's diversity while staying close to the RL model at pass@1. At k=256, it solves 67.5% of the problems, significantly more than the RL model (61.4%) and a mixture of whole responses matched in pass@1 (61.45%). The comparison is at equal attempt counts rather than equal compute, since rl-replace consults both models at every decoding step. These results show that the opening can recover a meaningful part of the RL gain, but a larger contribution comes from later choices, which can be borrowed while retaining much of the base model's diversity. Code is available at https://github.com/CyrusZhang04/WhatRLBrings.

0.39

From Base Rollouts to RL Reasoning: A Budgeted Search Perspective

cs.CL ·2026-09-01 ·Wenhe Sun, Cunxiang Wang, Zijun Yao, Yixin Cao
top venuebenchmark similarity 0.72
Abstract · Accepted to Findings of EMNLP 2026

Reinforcement learning with verifiable rewards (RLVR) improves language-model reasoning, but how these gains relate to inference-time decoding and search remains unclear. Does RL create reasoning the base model lacks, or shift the rollout distribution toward trajectories it can already reach but rarely samples? We study this behaviorally with a Unified Decoding Framework (UDF), which expresses token-level sampling, beam-like search, tree search, and sequence-level resampling as executable policies over a shared budgeted operating space, scored post hoc with pass@$k$, self-consistency, best-of-$N$, and first-finish success. Using paired Base/RL checkpoints from SimpleRL-Zoo, we ask whether an RL default-policy curve can be approximated by a structured path of Base operating points. On Math500, AIME, GPQA, and IFEval, the pass@$k$ recovery path follows a Budgeted Operating-Point Transition Rule (BOPTR), $N_{\mathrm{Base}} \approx αN_{\mathrm{RL}}^β$, with benchmark-conditioned exponents. On Qwen2.5-7B, BOPTR gives the lowest transfer error among the non-oracle rules we test, 3.41 pp (95% CI [2.32, 5.53]); a three-seed replication gives 3.07 $\pm$ 0.39 pp. The rule extends to ten models across four families (3.28 to 4.87 pp on checkpoints added after fitting), to four benchmarks it was never fitted on (5.03 pp vs. 4.44 pp in fit), and holds without an RL checkpoint for the target model (4.19 pp) or without RL supervision of any kind (5.08 pp). These results support a qualified internalized-search reading: under the recipe we test, much of the measured RL gain corresponds to a change in sampling efficiency toward operating points the base model can already reach under search. We treat the scaling patterns as descriptive of this recipe and cohort, report where they break down, and use UDF and BOPTR as behavioral diagnostics rather than evidence of parameter-level equivalence.

0.38

How RL Reshapes LLM Reasoning: Transferability, Coverage, and Scaling Laws

cs.LG cs.AIstat.ML ·2026-10-03 ·Ziheng Cheng, Yixiao Huang, Hanlin Zhu, Somayeh Sojoudi
theory similarity 0.72
Abstract

Recent studies on reinforcement learning (RL) report seemingly conflicting evidence about large language model (LLM) reasoning. Training on mathematics can improve performance in other domains, yet gains in Pass@1 can coincide with lower Pass@$N$ than the base model. This raises a fundamental question: does RL expand an LLM's reasoning boundary, or merely reweight its existing reasoning space? We revisit these phenomena across Qwen and Gemma model families, showing both cross-domain gains and forgetting, while coverage at large sampling budgets increases on some tasks and decreases on others. Detailed analysis of solution traces before and after RL indicates a shift in the reasoning strategies the model employs, motivating a two-stage autoregressive policy model that separates \emph{strategy selection} from problem-specific execution. Within this framework, we prove how RL's implicit bias reshapes strategy preferences, allowing gains on some tasks while suppressing strategies required by others. This mechanism can also broaden or narrow coverage at a given sampling budget even without expanding strategy support. We further provide theoretical justifications for log-sigmoid and log-linear scaling laws in RL compute, and evaluate their predictive power. Together, these results connect changes in strategy selection to cross-domain transfer, reasoning coverage, and compute scaling.

0.42

On Language Drift during RLVR Post-Training

cs.LG cs.AI ·2026-10-01 ·Michael Sullivan, Alexander Koller
theory similarity 0.71
Abstract · 22 pages; 15 figures; 4 tables

Recent advances in LLM reasoning models---driven primarily by the paradigm of post-training via reinforcement learning with verifiable reward (RLVR)---have enabled them to accomplish impressively complex tasks. However, in parallel with their rising capabilities, LLMs have increasingly displayed signs of language drift in their chains of thought (CoTs): unusual, non-standard, and seemingly nonsensical language use. Although it is well-documented---and can potentially impair CoT monitorability---the causes of language drift are thus far poorly understood. In this paper, we identify the conditions under which language drift occurs: we prove theoretically that RLVR optimization pressure permits unbounded language drift, while supervised fine-tuning does not. We then show empirically that language drift specifically arises during RLVR on novel reasoning tasks---i.e. when the target behavior cannot be drawn out of the base model. Finally, we prove that it is not possible to constrain language drift without constraining expected reward, suggesting that CoT monitorability cannot be improved without harming performance during RLVR post-training at the frontier.

0.24

Where RL Breaks: Localizing and Repairing Failures via Targeted Continued Pretraining

cs.CL cs.AI ·2026-10-19 ·Xinyi Wang, Danqi Chen
similarity 0.70
Abstract · 9 pages

Reinforcement learning with verifiable rewards (RLVR) is widely used to improve reasoning in language models, yet growing evidence suggests that it mostly sharpens what the base model can already do. This raises a practical question: when RL fails, what is the base model missing? We look inside the RL policy's own rollouts and find that failures are localized: whether a rollout fails is strongly predicted by a small set of characteristic n-grams, ranging from reflection phrases such as "let's recheck" to specific operations such as "the inverse of A". These failures persist throughout RL training, although they are not beyond the model's reach: other sampled answers to the same question are often correct. Building on this observation, we use the failure $n$-grams to retrieve text from the pretraining corpus and continue pretraining the base model on it before RL. The resulting corpus has only 35M tokens, 3--4 orders of magnitude smaller than typical mid-training. We evaluate this approach on OLMo2 and Qwen3 models trained with RL on (1) GSM8K; (2) a mixture of math, commonsense, and knowledge questions; and (3) general math and science reasoning. Despite its size, the corpus yields consistent gains: our approach outperforms continued pretraining on the same amount of text sampled from the pretraining corpus across 10 out of 11 settings, including by $2.0$ points on GSM8K when inserted before mid-training. The retrieved text also transfers across model families: text retrieved for OLMo2-1B's failures improves Qwen3-4B on the mixture by $1.9$ points over the same baseline. Together, our results suggest that where RL fails is a cheap and effective signal for selecting pretraining data.

0.10