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

Yinuo Liu

cs.LGOct 29, 2026

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

Authors: Yinuo Liu

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.

Figures & tables

Figure 1: Per-prompt loss is inevitable under specialization, but the aggregate pass@ $k$ crossover is conditional on Assumption 2 . Regime A (fine coverage) has a genuinely hard tail that the tilt starves, so $\Delta_{k}$ turns negative and the curves cross; $S^{-}(G)=1$ and the single crossing saturates the bound. Regime B gives every prompt backup coverage, so the hard tail keeps a floor, $\Delta_{k}$ stays nonnegative, and there is no crossover. Both regimes have a per-prompt loss; only A has an aggregate crossover.

Figure 2: The no-free-lunch frontier. Each point is the best pass@1 gain achievable at a given per-prompt floor $\gamma$ , against the price it pays, the worst pass@ $k$ loss $\max_{k}(\mathrm{base}-\mathrm{RL})$ . The unconstrained GRPO update (top right) buys the largest gain at the largest price; tightening $\gamma$ slides down the curve; $\gamma=1$ reaches the origin, where the only way to pay nothing is to gain nothing (Theorem 4 ). The curve is the exchange rate; its slope is the marginal price of a unit of pass@1.

Figure 3: The tilt law. For base-fitness crowding exponents $\kappa\in\{0.5,1,2\}$ , $\log(b-R)$ is linear in the entropy $H$ with slope $1/\kappa$ . Fitted slopes are $2.006,\,0.986,\,0.487$ against the predicted $2,\,1,\,0.5$ (within $2.6\%$ ). The slope identifies $\kappa$ from a single entropy-reward trace.

Figure 4: Published GRPO pass@ $k$ for Qwen2.5-7B (Zhou, 2607.20543, Table 2; transcribed, indicative). Left, Omni-MATH: GRPO (red) is overtaken by base at the largest budget, a single crossing, while the diversity intervention GRPO+PBA (green) stays above through the measured range. Right, MATH500: no crossing for $k\leq 256$ . The pattern matches the price (Theorem 3 ) and the frontier (Theorem 4 ); it does not establish behavior beyond the reported budgets.

RL for Language Model Reasoning

Reinforcement learning for language model reasoning uses reward-driven training to improve multi-step problem solving, tool use, and reliable answers.

See all 1,103 papers

Sep 18, 2026

RLVR is a Kernel, Not a Function: Statistical Inference for pass@ $k$ Crossovers

Reinforcement learning with verifiable rewards (RLVR) often improves pass@1 while falling behind its base model at larger sampling budgets

k

, a crossover read as evidence that RLVR only sharpens existing capability. We identify two limits to this reading. First, a visible crossing need not be statistically established: comparing models on the same prompts, we build confidence bands across sampling budgets

k

that require evidence of both an early gain and a later loss. Across five public RLVR pairs no crossing is statistically established in the initial evaluations, while a 32k-token evaluation on fresh prompts locates a reversal with first loss between 11 and 61 samples; power analysis shows why failure to detect a crossing need not mean no crossing, and why more prompts can help more than more answers per prompt. Second, base success alone does not determine what RLVR does to a prompt: prompts with the same base success rate have different post-RL success rates, and these differences repeat across independent generation halves. The relationship is a conditional distribution---a Markov kernel---rather than a single curve, and fitting it predicts crossings in independent generations for the same prompts and corrects the simple model's power estimates. Theory further shows how losses on a minority of the hardest prompts can overturn an early lead even when training improves other prompts, separating evidence that a crossover exists from claims about what it means for capability.

Chen Yang, Jun Chen

Department of Statistics, Texas A&M University · Division of Computational Biology, Department of Quantitative Health Sciences, Mayo Clinic

Reinforcement Learning with Verifiable Rewards LLM Evaluation

Ask PDF

Jun 13, 2026

Understanding Diversity Collapse in RLVR via the Lens of Overtraining

Reinforcement learning with verifiable rewards (RLVR) has become a key approach for enhancing the reasoning abilities of large language models. However, RLVR often suffers from diversity collapse: Pass@

1

improves while high-

k

Pass@

k

degrades, which is viewed as a narrowing of the model's reasoning boundary. We formalize this diversity collapse through the lens of overtraining: once a problem's contribution to the reference metric has effectively saturated, further updates no longer expand what the model can solve but still concentrate probability mass on the trajectories favored by on-policy sampling. Under a standard setup with few rollouts per problem, even a single observed success places a problem in a nearly saturated regime for high-

k

Pass@

k

, so most updates in standard RLVR are overtraining from the boundary perspective. This perspective also suggests a reading of whether RLVR can expand the model's reasoning abilities beyond the base model: since RLVR is structurally biased against high-

k

Pass@

k

, its aggregate decline does not by itself mean that no new reasoning gains occurred. Interventionally, restricting updates to problems with zero observed success lifts Pass@

256

above the base model on difficult benchmarks; observationally, a non-trivial fraction of initially unsolvable problems become solvable during standard RLVR training. Building on these findings, we propose Bayesian Boundary Gating (BBG), which redirects optimization away from overtraining by estimating each problem's marginal contribution to the reasoning boundary. Across multiple reasoning benchmarks, BBG improves average Pass@

k

across a wide range of

k

Suqin Yuan, Jinkun Chen, Jiyang Zheng +6

Sydney AI Centre, The University of Sydney · Southeast University · Microsoft +3

Reinforcement Learning Reasoning Diversity RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards

Ask PDF

Jul 20, 2025

The Invisible Leash: Why RLVR May or May Not Escape Its Origin

Recent advances highlight Reinforcement Learning with Verifiable Rewards (RLVR) as a promising approach to enhancing LLM capabilities. However, it remains unclear whether the current practice of RLVR truly expands models' reasoning boundary or mainly amplifies high-reward outputs that base models already know. We introduce empirical support dynamics, a framework that quantifies how RLVR preserves, expands, and shrinks access to verified solutions. Applied across models, reasoning tasks, and training checkpoints, it matches verified successes question by question to reveal changes that aggregate accuracy can conceal. Across the evaluated model-level benchmark aggregates, the shrinkage of observed support outweighs its expansion: more questions lose a verified success than gain one at the stated sampling budgets. These losses occur alongside gains in pass@1. Some RLVR models increase average token-level entropy while reducing final-answer entropy: their token choices become more uncertain on average even as their final answers become more concentrated. Together, these findings reveal an ``invisible leash'' in current RLVR practice: it can make existing successes more reliable while losing access to other verified solutions. Empirical support dynamics make this imbalance measurable and motivate exploration strategies that reach underrepresented solutions while retaining prior successes.

Fang Wu, Weihao Xuan, Danny Xing +5

Stanford University, CA, USA · The University of Tokyo, Japan · RIKEN AIP, Tokyo, Japan +2

RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards

Ask PDF

Abstract

RL for Language Model Reasoning

Explore similar work

RLVR is a Kernel, Not a Function: Statistical Inference for pass@kkk Crossovers

Understanding Diversity Collapse in RLVR via the Lens of Overtraining

The Invisible Leash: Why RLVR May or May Not Escape Its Origin

RLVR is a Kernel, Not a Function: Statistical Inference for pass@ $k$ Crossovers