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

RLVR is a Kernel, Not a Function: Statistical Inference for pass@ $k$ Crossovers
Sep 18, 2026Chen Yang, Jun ChenReinforcement Learning with Verifiable Rewards LLM Evaluation
Department of Statistics, Texas A&M University · Division of Computational Biology, Department of Quantitative Health Sciences, Mayo Clinic
Understanding Diversity Collapse in RLVR via the Lens of Overtraining
Jun 13, 2026Suqin Yuan, Jinkun Chen, Jiyang Zheng +6Reinforcement Learning Reasoning Diversity
Sydney AI Centre, The University of Sydney · Southeast University · Microsoft +3
The Invisible Leash: Why RLVR May or May Not Escape Its Origin
Jul 20, 2025Fang Wu, Weihao Xuan, Danny Xing +5RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards
Stanford University, CA, USA · The University of Tokyo, Japan · RIKEN AIP, Tokyo, Japan +2

Sep 18, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

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