Reinforcement learning improves first try at a cost to later attempts
There Is No Free Lunch in RLVR: Every pass@1 Gain Has a pass@k Price
Machine LearningArtificial Intelligence
Summary
Sometimes when a language AI is trained to get better at solving problems on its first try, it actually performs worse when given many chances to solve the same problem. The authors show this trade-off is inevitable, not a mistake or fixable by more training. They prove that improving success on the first try means losing some success on other problems or tries, and they measure exactly how this trade-off happens. This means reinforcement learning can move the model along a fixed boundary of reasoning ability but cannot improve it freely in all cases.
What this means in practice
- •For machine learning engineers: Assess trade-offs between improving first-try success and overall performance for language model updates using precise metrics from evaluation logs.
- •For ai system designers: Use the theoretical boundaries established to design reinforcement learning strategies that navigate the reasoning-performance frontier without expecting free improvements.
A theory result. No direct application yet.
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.