PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yinuo Liu

arXiv:2610.39295v1cs.LGcs.AImath.OCstat.ML

TL;DR

The paper asks whether RLVR’s pass@1 gains alongside losses at large sampling budgets signal a failure to add reasoning or a transient effect. It models RLVR as an exponential tilt over shared strategies and proves that gains carry a price, including a pass@k crossover under stated conditions.

  • Problem

    RLVR raises pass@1 while the base model catches up and overtakes it at large sampling budget k, prompting debate over whether this reflects failure to add reasoning or a transient effect.

    Source: §1 · p. 1

  • Method

    The paper models RLVR as an exponential tilt of a base policy over solution strategies shared across prompts.

    Source: §2 · p. 3

  • Results

    Under specialization, every pass@1-improving update lowers some prompt’s success, and fine coverage forces a pass@k crossover whose count is bounded by sign variation.

    Source: §1 · p. 1, §3.2 · p. 6

  • Takeaways & Limitations

    A constrained update traces the pass@1–pass@k frontier, and under specialization removing the crossover also removes the pass@1 gain.

    Source: §1 · p. 1

    The entropy-performance law concerns strategy entropy, which need not track token entropy; claims are model-level rather than about a specific model beyond published curves.

    Source: §1 · p. 2, §4.2 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

The paper models RLVR as an exponential tilt over strategies shared across prompts and proves that improving pass@1 carries a measurable price. It characterizes when prompt losses force pass@k crossovers and traces the trade-off frontier.

1 Introduction

  • A constrained update traces the exact pass@1 versus pass@k frontier; forbidding any prompt regression removes the crossover and, under specialization, the pass@1 gain.An optimal per-prompt floor traces the exchange rate.Source: §1 · pp. 1–2
  • A diversity bonus helps both metrics only when the unmodified update lies off the frontier.Source: §1 · p. 2
  • Under exclusive or dominant specialization, every pass@1-increasing update lowers some prompt’s success; the exact condition is a strictly positive price on prompts.Merely being the unique best strategy on a prompt is insufficient, while a dominating strategy restores a free lunch.Source: §1 · p. 2
  • The number of pass@k crossings is at most the sign variation of the shift in per-prompt success, and this bound is tight.The result uses a totally positive argument.Source: §1 · p. 2
  • When losses reach the hardest, finely covered prompts, a pass@k crossover is forced; without fine coverage, per-prompt loss need not produce a crossover.The order-preserving case recovers the known single-crossover theorem.Source: §1 · pp. 1–2
  • A diagnostic uses per-prompt base and RL success rates from evaluation logs to return the crossing bound, order-preserving test, and price.The authors apply it to published curves and find the predicted structure.Source: §1 · p. 2
  • The claims are stated at the model level, not for any specific language model beyond what published curves show.The paper says its numbers are produced and checked by an accompanying package.Source: §1 · p. 2

2 Model and results

The section models RLVR as an exponential tilt over strategies shared across prompts and states when pass@1 gains require losses under specialization. It derives conditions for a pass@k crossover and an exact pass@1–pass@k price frontier.

2 Model and results

  • Theorem 1 models the population-limit RLVR update as an exponential tilt of a base distribution over shared solution strategies.The setup defines each strategy’s probability of solving each prompt, then evaluates per-prompt and mean success across the prompt distribution.Source: §2 · pp. 2–3

2.2 Statements

  • Theorem 2 gives the no-free-lunch condition: under exclusive specialization, every pass@1-increasing update lowers some prompt’s success.A strictly positive prompt reweighting is the exact Stiemke condition; dominant specialization also suffices, while a unique-best strategy alone does not.Source: §2.2 · p. 4
  • Theorem 3 bounds the number of pass@k crossings by the sign variation of the per-prompt success-CDF shift, and the bound is tight.When training preserves prompt difficulty order, there is at most one crossing, recovering the single-crossover result of Yang and Chen (2609.22547, Thm. 3).Source: §2.2 · p. 4

2.1 Assumptions

  • Fine coverage routes a per-prompt loss to a hardest prompt and forces a pass@k crossover; without it, losses need not produce a crossover.The condition requires strategies covering a minimal-success prompt to have below-base-average fitness.Source: §2.1 · p. 3, §2.2 · p. 4

2.2 Statements

  • Theorem 4 defines the exact pass@1–pass@k frontier by maximizing pass@1 subject to a per-prompt success floor.At γ = 1 the constraint enforces first-order stochastic dominance and, under Assumption 1, zero pass@1 gain; the frontier has a closed form for M = 2.Source: §2.2 · p. 5
  • The section connects the tilt to entropy behavior and reports that GRPO remains close to the best-fit tilt at matched concentration.The entropy bump occurs iff high-fitness strategies are initially underweighted; the near-tilt result is stated with a tested total-variation distance below 3×10−4.Source: §2.2 · pp. 4–5

3 The pass@1 price

The section formalizes the pass@1 gain as a prompt-level price under specialization, then characterizes when that price produces pass@k crossings and how constrained updates trace the exact trade-off.

3 The pass@1 price

  • Probability conservation on the strategy simplex makes prompt-level regressions the price of reinforcement when strategies specialize.A free lunch is a direction that raises pass@1 without any prompt regressing.Source: §3.1 · p. 5, §3 · p. 5

3.1 No free lunch

  • Under exclusive specialization, every pass@1 gain lowers some prompt’s success; the exact no-free-lunch condition is a strictly positive prompt reweighting that equalizes strategy fitness.Unique-best specialization alone is insufficient: a near-generalist can absorb defunded probability and permit a free lunch.Source: §3.1 · p. 6

3.2 The pass@k price

  • The number of pass@k crossings is at most the sign variation of the per-prompt success-CDF shift, a tight bound that recovers the single-crossing result in the order-preserving case.The proof uses the variation-diminishing property of a totally positive kernel.Source: §3.2 · p. 6
  • Under Assumptions 1 and 2, every pass@1-improving update is overtaken by the base model at large k; without Assumption 2, a crossover need not occur.The loss must reach the hardest prompts; if the hard tail retains a high-fitness backup, the minimum success need not fall and no crossover forms.Source: §3.2 · pp. 6–7, Figure 1 · p. 7

3.3 The price frontier

  • Theorem 4’s constrained update traces a monotone frontier between pass@1 gain and worst pass@k loss; at γ = 1, removing prompt regressions also removes the pass@1 gain under specialization.As γ decreases, pass@1 gain rises; the verified frontier has no setting that improves pass@1 while eliminating the crossover.Source: §3.3 · p. 7

4 One identity, two literatures

The exponential tilt links the pass@k price to entropy change. Its entropy-performance law has a crowding-dependent exponent, while entropy collapse and transient growth are characterized at the strategy level.

4 One identity, two literatures

  • The same exponential tilt connects the pass@k price with entropy collapse and the entropy-performance curve.The paper distinguishes its identifiable exponent and crowding interpretation from concurrent work on the exact entropy-mass curve and terminal law.Source: §4 · pp. 7–8, §4.1 · p. 8

4.1 The tilt law

  • The tilt law gives b−R = aκ exp(H/κ)(1+o(1)) in the mesoscopic regime, with κ identifying near-optimal strategy crowding from the entropy-reward slope.The κ = 1 case recovers the exponential form of Cui et al. [15]; the paper limits its claim to the mesoscopic law.Source: §4.1 · p. 8

4.2 Entropy collapse and the bump

  • The tilt’s entropy identity makes entropy nonincreasing under a uniform base and collapsing to log|argmax f|; with a nonuniform base, entropy rises first iff Covw0(f,logw0) < 0.That condition specifies when a transient entropy rise occurs.Source: §4.2 · p. 8

4.1 The tilt law

  • For κ = 0.5, 1, and 2, fitted log(b−R)-versus-H slopes are 2.006, 0.986, and 0.487, respectively, within 2.6% of the predicted 1/κ.The slope identifies κ from a single entropy-reward trace.Source: Figure 3 · p. 9

4.2 Entropy collapse and the bump

  • The entropy-performance law concerns strategy entropy, not token entropy: strategy entropy can fall from 2.77 to 2.14 while token entropy rises from 6.85 to 7.27.The distinction follows because a policy may concentrate on surviving strategies while spreading probability within a surviving strategy.Source: §4.2 · p. 9
  • The entropy identity, predicted bump, and tilt-law slopes were regenerated and checked by the package.The identity holds to 2×10−6 under a uniform base; tilt-law slopes match 1/κ within 2.6%.Source: §4.2 · p. 9

5 Evidence from published curves, and a diagnostic

The diagnostic applies the theory to published pass@k curves and finds the predicted price structure, while the coarse, limited-budget evidence remains indicative rather than proof.

Evidence from published curves

  • The published-curve reading is corroboration, not proof: curves are coarse, values are transcribed or digitized, and five budgets cannot locate a crossing precisely.No model is trained or run, and the analysis claims nothing beyond what the published curves show.Source: §5 · pp. 9–10

The diagnostic

  • The diagnostic takes per-prompt base and RL success rates or their pass@k curves and returns crossings, the sign-variation bound, the order-preserving test, and estimated price.It also reports whether the bound is saturated; the proposed reporting quantities are worst pass@k loss and crossing count.Source: §5 · p. 9

A published case

  • +0.149, +0.144, +0.104, +0.030, and −0.008 are the Omni-MATH GRPO advantages over base at k = 1, 4, 16, 64, and 256, with one crossing between 64 and 256.The figure identifies this single crossing as the order-preserving regime.Source: §5 · p. 10, Figure 4 · p. 10
  • GRPO+PBA improves on raw GRPO at every measured k, delaying the crossing beyond the measured budget without removing the price versus base.The frontier explains this as movement toward the optimal trade from raw GRPO’s interior position.Source: §5 · p. 10, Figure 4 · p. 10
  • On MATH500, neither trained model crosses base for k ≤ 256, so any price lies beyond the measured budget.The authors make no claim about behavior past k = 256.Source: §5 · p. 10, Figure 4 · p. 10

6 Related work

The related work spans the RLVR reversal debate, pass@k evaluation, entropy and policy-optimization theory, and mathematical tools. The paper positions its contribution as pricing the base-to-RL shift and bounding its crossings.

The phenomenon and the debate

  • Yue et al. [93] report a pass@1 gain followed by base-model overtaking, Liu et al. [42] argue prolonged RL expands the boundary, and Zhou [101] proposes a diversity intervention.The paper frames its result as conditional: crossover is forced under fine coverage of a hard tail and absent otherwise.Source: §6 · p. 11

pass@k, sampling, and test-time compute

  • Prior pass@k work studies sampling, inference scaling, and direct optimization, whereas this paper bounds how the base-to-RL shift moves the curve without optimizing the metric.The passage situates pass@k’s origins in code evaluation [10].Source: §6 · p. 11

Entropy, exploration, and diversity

  • Work on entropy collapse and alignment-related diversity loss describes or counters concentration; this paper adds per-prompt accounting and a crossing bound.Source: §6 · p. 11

RLHF and preference-optimization theory

  • The paper casts RL as a one-step contextual bandit and presents its no-free-lunch duality as a Pareto statement on the strategy simplex, which the cited foundations do not address.Source: §6 · p. 11

Mathematical tools

  • The mathematical tools include totally positive kernels, Descartes’ rule, theorem-of-the-alternative duality, and stochastic dominance; the novelty is pricing pass@1 against prompt success and bounding pass@k crossings.The cited tool lineages include,,, and, respectively.Source: §6 · p. 11

7 Concurrent work

The concurrent-work discussion distinguishes partial overlap from this paper’s shared-strategy account and identifies its added crossing bound, no-free-lunch condition, forced-crossover result, and price frontier.

7 Concurrent work

  • Yang and Chen [89] prove a single-crossing result for a restricted function case, while this paper gives a tight sign-variation bound for any shift, including kernels.Their result is the order-preserving corollary; the paper also claims its no-free-lunch result and price frontier have no counterpart there.Source: §7 · p. 12
  • “Winner-Take-All” studies a finite-mode, single-prompt entropy trajectory; this paper claims only the strategy-level mesoscopic context linking entropy to pass@k, with priority credited to that work where they overlap.The paper’s many prompts sharing strategies make pass@k well defined in its setting.Source: §7 · p. 12

Appendix: proofs

  • The appendix assumes q_xj > 0 for every strategy and prompt, noting that specialization instances satisfy this through a baseline and that it makes the rows positively span R^M.Source: Appendix: proofs · p. 17

A Proof of Theorem 1 (tilt identity)

The proof derives the exponential-tilt identity from natural policy gradient or mirror descent on mode logits. It also states GRPO’s approximation to that tilt as a proposition with measured total variation.

Proof of the tilt identity

  • The mode-logit flow yields θ_τ = θ_0 + τβf + c1, so exponentiating and absorbing 1/β into τ gives w_τ ∝ w_0 exp(τf), the stated tilt.The common advantage term shifts logits equally and cancels under the softmax.Source: A Proof of Theorem 1 (tilt identity) · p. 17

GRPO gap

  • GRPO replaces the expected advantage with a group-standardized advantage, making its flow a time-changed tilt up to variation δ over the matched-entropy window.The displayed passage gives the standardization in terms of group mean, standard deviation, and a bounded factor.Source: A Proof of Theorem 1 (tilt identity) · p. 17
  • The GRPO approximation is stated as a proposition with numerical evidence, not a theorem; the package measures total variation below 3×10^-4 and records finite-group transient non-monotonicity separately.Source: A Proof of Theorem 1 (tilt identity) · p. 17

B Proof of Theorem 2 (no free lunch)

The proof characterizes no free lunch through a strictly positive prompt-price vector and shows that exclusive specialization makes every pass@1-improving update regress on some prompt.

B Proof of Theorem 2 (no free lunch)

  • Stiemke’s lemma makes the absence of a free lunch equivalent to a strictly positive prompt-price vector whose weighted strategy success is constant across strategies.The proof derives this condition by restricting shifts to the simplex’s zero-sum directions.Source: B Proof of Theorem 2 (no free lunch) · p. 18
  • Under exclusive specialization, every nonzero probability shift lowers success on a prompt that only its defunded strategy solves, so every pass@1 gain lowers some prompt’s success.The Stiemke alternative characterizes no free lunch by a strictly positive prompt-price vector satisfying Q⊤y = μ1.Source: B Proof of Theorem 2 (no free lunch) · p. 18
  • Dominant specialization also yields no free lunch by constructing positive prices on representative prompts and small positive prices elsewhere.The package finds no free lunch on 2000/2000 dominant-specialized instances.Source: B Proof of Theorem 2 (no free lunch) · p. 18
  • If one strategy dominates every other strategy on every prompt, shifting mass toward it is a free lunch unless all strategy columns coincide..Source: B Proof of Theorem 2 (no free lunch) · p. 18
  • For the displayed shift dw = (−0.6,−0.4,1), Qdw = (0,0.02,0.5) is nonnegative and nonzero, with ⟨f,dw⟩ = +0.173; the near-generalist (column 3, 0.96 on the first two prompts) absorbs mass defunded from specialists.The Stiemke dual is infeasible.Source: B Proof of Theorem 2 (no free lunch) · p. 18

C Proof of Theorem 3 (the pass@k price)

The proof bounds pass@k crossings by sign variation in the per-prompt success-distribution shift, establishes tightness, and gives conditions that force or preclude a crossover.

C Proof of Theorem 3 (the pass@k price)

  • A pass@k crossing can occur no more often than the sign variation of the difference between the base and updated success CDFs.The bound follows from the variation-diminishing property of a strictly totally positive kernel.Source: C Proof of Theorem 3 (the pass@k price) · p. 18
  • The crossing bound is tight: constructed mass shifts realize exactly m crossings for m = 1,...,6.The package realizes each construction without violating the bound.Source: C Proof of Theorem 3 (the pass@k price) · p. 18
  • When the hardest prompts lose success, the tilt forces a crossover: the updated policy eventually has lower pass@k at sufficiently large k.The proof identifies strategy mass loss using the threshold f_j < Λ(τ)/τ.Source: C Proof of Theorem 3 (the pass@k price) · pp. 18–19
  • If updated prompt success is an increasing transformation of base success, the CDF difference changes sign at most once, recovering the single-crossover result [89].This order-preserving condition therefore limits crossings to at most one.Source: C Proof of Theorem 3 (the pass@k price) · p. 19
  • If the hard tail retains a coverage floor, per-prompt losses need not produce a crossover; the package reports crossovers in only 15% of regime B instances despite losses in 96%.In that regime, the CDF difference is nonpositive near zero.Source: C Proof of Theorem 3 (the pass@k price) · p. 19

D Proof of Theorem 4 (price frontier)

The proof traces the pass@1–pass@k trade-off with an optimal update subject to per-prompt success floors.

D Proof of Theorem 4 (price frontier)

  • For γ in [0,1], maximizing pass@1 subject to Qw ≥ γQw0 is a feasible, bounded linear program.The base policy is feasible whenever γ ≤ 1.Source: D Proof of Theorem 4 (price frontier) · p. 19
  • As γ increases, the feasible set shrinks and the optimal pass@1 value is nonincreasing; the worst pass@k loss is also monotone in γ.The first crossover k⋆ moves outward as γ approaches 1.Source: D Proof of Theorem 4 (price frontier) · p. 19
  • At γ = 1, specialization forces Qw = Qw0, so the update has zero pass@1 gain and no pass@k difference.For M = 2, the constraints reduce to intervals in the strategy weight, yielding a closed form for k⋆(γ).Source: D Proof of Theorem 4 (price frontier) · p. 19

E Proof of Theorem 5 and the lemmas

The lemmas connect the exponential strategy tilt to entropy change and performance, while specifying the scope of the entropy law and the role of shared parameters.

E Proof of Theorem 5 and the lemmas

  • Under a uniform base policy, strategy entropy is nonincreasing and converges to the log of the number of reward-maximizing strategies.For a nonuniform base, entropy initially rises exactly when Cov_w0(f, log w0) < 0.Source: E Proof of Theorem 5 and the lemmas · p. 19
  • Near-optimal strategy gaps with density proportional to g^(κ−1) yield b − R = κ/τ (1 + o(1)) and H = const − κ log τ + o(log τ).Eliminating τ gives the entropy-performance law; the exponent κ is identifiable from its slope.Source: E Proof of Theorem 5 and the lemmas · p. 19
  • The entropy-performance derivation is asymptotic and applies in the mesoscopic window τ·gap → 0 and τ log M → ∞.The package confirms the predicted slope 1/κ within 2.6% for κ ∈ {0.5, 1, 2}.Source: E Proof of Theorem 5 and the lemmas · p. 19
  • With independent tabular policies for each prompt, full gradient flow makes every prompt’s success nondecreasing, so pass@k inversion requires parameters shared across prompts.Finite-group stochastic GRPO can violate that monotonicity transiently.Source: E Proof of Theorem 5 and the lemmas · p. 19

Related papers

Loading 2610.39295v1…