💬 NLP

A Relative-Budget Theory for Reinforcement Learning with Verifiable Rewards in Large Language Model Reasoning

This paper proposes a relative-budget theory for reinforcement learning in large language model reasoning, defining a key quantity $\xi$ that governs sample efficiency across deficient, balanced, and ample regimes, and empirically validates that a relative budget between 1.5 and 2.0 maximizes learning performance.

Original authors: Akifumi Wachi, Hirota Kinoshita, Shokichi Takakura, Rei Higuchi, Taiji Suzuki

Published 2026-02-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Akifumi Wachi, Hirota Kinoshita, Shokichi Takakura, Rei Higuchi, Taiji Suzuki

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: The "Goldilocks" Zone for AI Thinking

Imagine you are teaching a student (the AI) how to solve a difficult math problem. You have a limited amount of time or "tokens" (words) they can use to think and write down their answer.

The paper introduces a simple rule called the Relative Budget ( $\xi$ ). Think of this as a ratio comparing how much time you give the student versus how long the student usually needs to solve the problem on their own.

$\xi$ (Xi) = (Time you give) / (Time the student usually needs).

The authors discovered that how well the AI learns depends entirely on this ratio. There are three distinct "zones" or regimes, and the AI behaves very differently in each one.

The Three Zones of Learning

1. The "Too Tight" Zone (Deficient Regime, $\xi \approx 0$ )

The Analogy: Imagine giving a student a 10-minute test to solve a problem that usually takes them 100 minutes to figure out.

What happens: The student almost never finishes. They run out of time before finding the answer.
The Result: The teacher (the AI training system) gets almost no "correct" examples to learn from. Because the AI rarely sees a success, it can't learn anything. It's like trying to learn to swim by throwing someone into a pool where they can't even touch the bottom; they just panic and sink.
Paper Claim: In this zone, learning is theoretically impossible because "informative trajectories" (successful attempts) are too rare.

2. The "Just Right" Zone (Balanced Regime, $\xi \approx 1.5 - 2.0$ )

The Analogy: Now, you give the student about 1.5 to 2 times the amount of time they usually need.

What happens: The student has enough time to solve the problem, but it's still challenging. Sometimes they solve it quickly; sometimes they struggle and take the full time.
The Result: This is the sweet spot. The teacher sees a mix of easy wins and hard-fought victories. This variety creates a strong "learning signal." The AI can clearly see what works and what doesn't.
Paper Claim: This is where Reinforcement Learning (RL) is most efficient. The AI learns the fastest here. Interestingly, this is also the hardest zone for a different method called "Supervised Fine-Tuning" (SFT), because the variety of solutions is so confusing for a simple mimicry teacher.

3. The "Too Easy" Zone (Ample Regime, $\xi \to \infty$ )

The Analogy: You give the student 100 hours to solve a problem that takes 10 minutes.

What happens: The student solves it almost instantly every single time. They have so much extra time that the task feels trivial.
The Result: The AI learns, but it's not very efficient. Since the student always succeeds immediately, there is no "struggle" or variation to learn from. The AI stops improving because it's already too good for the task. It's like giving a chess grandmaster a puzzle a 5-year-old could solve; they won't get any better at chess by doing it.
Paper Claim: Learning remains stable, but the "marginal gains" (improvement per step) get smaller and smaller. You are wasting compute power.

The "Phase Transition"

The paper describes a phase transition around a relative budget of 1.0.

Below 1.0: The AI is stuck in the dark, rarely seeing success.
Above 1.0: The AI suddenly starts seeing success, and learning explodes.
The Peak: The authors found that the absolute best performance happens when the budget is slightly higher than the average need, specifically between 1.5 and 2.0. This gives the AI just enough "wiggle room" to explore different ways of solving the problem without wasting time.

Why This Matters for AI Training

The paper argues that many people are currently wasting money and computer power.

If you give the AI too little time, it learns nothing.
If you give it too much time, it learns slowly and wastes resources.
The Solution: You should tune your computer budget so that the AI has about 1.5 to 2 times the tokens it usually needs to solve a problem. This ensures the AI is challenged enough to learn efficiently but not so challenged that it fails.

A Note on "Mimicry" vs. "Trial and Error"

The paper also compares two teaching styles:

Supervised Fine-Tuning (SFT): Like a student copying a teacher's exact steps. The paper says this method fails in the "Just Right" zone because there are too many different ways to solve the problem, and the student gets confused by the variety.
Reinforcement Learning (RL): Like a student trying different approaches and getting a "check mark" for a correct answer. This method thrives in the "Just Right" zone because it can handle that variety and figure out the best path.

Summary

To get the best reasoning skills out of an AI, don't just throw infinite computing power at it. Instead, find the Goldilocks budget: give the AI just enough extra time (about 50% to 100% more than it usually needs) to solve the problem. This creates the perfect environment for it to learn quickly and effectively.

Technical Summary: A Relative-Budget Theory for Reinforcement Learning with Verifiable Rewards in LLM Reasoning

1. Problem Statement

Reinforcement learning with verifiable rewards (RLVR) has become a dominant paradigm for enhancing the reasoning capabilities of Large Language Models (LLMs), enabling long-horizon planning and iterative self-correction. However, empirical effectiveness varies significantly across tasks and computational budgets. Existing theoretical frameworks often fail to account for the dynamic relationship between task difficulty and compute budgets, particularly in online learning settings. Practitioners lack guidelines on how to allocate compute resources efficiently, risking the allocation of vast resources to regimes where learning is theoretically inefficient or where the learning signal vanishes.

This paper addresses the gap in theoretical understanding by analyzing how the ratio between the available token budget and the inherent difficulty of a task dictates the sample efficiency and convergence of RLVR.

2. Methodology and Theoretical Framework

2.1. The Relative Budget ( $\xi$ )

The authors introduce a central quantity called the relative budget, defined as:
$\xi := \frac{H}{E[T]}$
where $H$ is the generation horizon (token budget) and $E[T]$ is the expected number of tokens required to reach the first correct solution under a base policy $\pi_b$ . This metric unifies compute constraints and task difficulty.

2.2. Modeling Assumptions

The reasoning process is modeled as a finite-horizon Markov Decision Process (MDP) with binary rewards. The time-to-solution $T(\tau)$ is analyzed under specific distributional assumptions:

Moments: The variance of $T(\tau)$ scales with the square of its mean ( $v_x = \Theta(\mu_x^2)$ ).
Left-Tail Behavior: The probability of solving a problem within a fraction of the expected time follows a function $f(z)$ that decays polynomially rather than exponentially near the origin.
Gamma Distribution: For concrete analysis, $T(\tau)$ is modeled using a Gamma distribution, which serves as a continuous proxy for the discrete token counts in complex reasoning tasks.

2.3. Analytical Approach

The paper analyzes the anti-concentration coefficient $c_0(\xi)$ , which represents the probability of sampling high-reward trajectories (solutions found significantly faster than the mean). This coefficient directly governs the sample complexity of RL. The authors derive finite-sample guarantees for online RL, tracking the evolution of $\xi$ over iterations as the policy improves.

3. Key Contributions and Theoretical Results

The paper establishes that RLVR performance is governed by three distinct regimes based on the value of $\xi$ :

3.1. Three Regimes of Learning Efficiency

Deficient Regime ( $\xi \to 0$ ):
- Condition: The token budget $H$ is much smaller than the expected time-to-solution.
- Dynamics: High-reward trajectories are extremely rare. The anti-concentration coefficient vanishes ( $c_0 \to 0$ ), causing the sample complexity to explode. Learning is theoretically intractable.
Balanced Regime ( $\xi = \Theta(1)$ ):
- Condition: The token budget is comparable to the expected time-to-solution.
- Dynamics: Informative trajectories occur with non-negligible probability. The anti-concentration coefficient is bounded away from zero ( $c_0 = \Theta(1)$ ), leading to maximal sample efficiency.
- Contrast with SFT: This regime represents a "sweet spot" for RL but the "worst-case" for Supervised Fine-Tuning (SFT). In the balanced regime, the heterogeneity of successful solution traces (varying lengths and strategies) is maximized, making imitation learning difficult for SFT.
Ample Regime ( $\xi \to \infty$ ):
- Condition: The token budget significantly exceeds the expected time-to-solution.
- Dynamics: Learning remains stable with a bounded anti-concentration coefficient. However, marginal gains per iteration diminish as the task becomes trivial relative to the budget, and sample complexity increases linearly with $\xi$ .

3.2. Finite-Sample Guarantees for Online RL

The authors prove that in an online setting, as the policy improves, the expected time-to-solution decreases, causing the relative budget $\xi$ to grow linearly over iterations.

Theorem 6.4: Under the Gamma model, online RL drives $\xi$ to grow linearly ( $\xi_i - \xi_0 \geq i(2K)^{-1}$ ).
Trade-off: While the policy converges to the token budget $H$ , maintaining monotonic improvement in the ample regime requires an increasing number of rollout samples (quadratic degradation in sample complexity relative to $\xi$ ).

3.3. Optimal Budget Allocation

Theoretical analysis using the Gamma distribution identifies an optimal relative budget $\xi^*$ that maximizes the learning signal (reward variance) while maintaining a stable anti-concentration coefficient.

Theoretical Prediction: The optimal $\xi^*$ falls in the range $1.0 \leq \xi^* \leq 1.4$ .
Implication: Allocating a budget slightly larger than the expected difficulty ( $\xi \gtrsim 1$ ) is crucial for reliable learning signals.

4. Empirical Results

The authors validated their theory using standard LLMs (Llama-3.2-3B, Phi-4-mini, Qwen3-4B) on reasoning benchmarks (GSM8K, MATH-500).

Phase Transition: Experiments confirmed a phase transition at $\xi \approx 1.0$ . In the deficient regime ( $\xi < 0.8$ ), reward variance and anti-concentration were negligible.
Peak Learning Signal: The learning signal (reward variance) peaked in the range $\xi \in [1.5, 2.0]$ , slightly higher than the theoretical minimum due to the long-tailed nature of token generation distributions.
Performance Correlation: Post-training accuracy on reasoning tasks showed a sharp increase as $\xi$ approached 1 (the balanced regime) and saturated in the ample regime ( $\xi > 2.0$ ).
Model Robustness: The theoretical predictions held across different models and datasets, even for models (like Qwen3) that exhibited bimodal token distributions, suggesting the core theory is robust to specific distributional deviations.

5. Significance and Claims

The paper claims to provide a unified theoretical framework that explains the regime-dependent success of RLVR in LLM reasoning. Its primary significance lies in:

Defining the "Edge of Competence": It theoretically justifies the empirical observation that RL is most effective when tasks are neither trivial nor intractable, specifically when the compute budget is comparable to the task's inherent difficulty.
Guiding Compute Allocation: The theory offers a concrete guideline for practitioners: allocate token budgets such that $\xi \in [1.5, 2.0]$ . This ensures the presence of informative trajectories without the diminishing returns of excessive budgets.
Explaining RL vs. SFT Divergence: It elucidates why verifier-based RL outperforms SFT in scaling test-time compute, particularly in the balanced regime where solution heterogeneity hinders imitation learning but aids exploration-based RL.
Sustainable AI Development: By identifying when RL yields diminishing returns, the framework aims to prevent wasteful training runs, thereby reducing the financial and environmental costs associated with large-scale model training.

The authors note that their analysis relies on a continuous proxy reward to make variance analysis tractable and that extending the theory to strict binary-reward settings remains an open problem. However, the empirical alignment with realistic settings suggests the relative budget $\xi$ is a fundamental factor in the efficacy of reasoning-oriented RL.