How Far Are We from Optimal Reasoning Efficiency?

We sincerely appreciate the reviewer's time and feedback. Below, we address the key concerns point-by-point:

1. Large-Scale Efficiency Frontier Estimation
   • To rigorously estimate optimal reasoning efficiency, we conducted large-scale RL experiments spanning 8 algorithms and 15 training configurations, resulting in 180+ and 210+ models for 1.5B and 7B scales, respectively. This far exceeds the limited fine-tuned models mentioned by the reviewer. This large-scale evaluation ensures robust, statistically meaningful efficiency frontiers.
2. Training Efficiency of REO-RL
   • We provide an empirical comparison showing that training efficiency of REO-RL is competitive with baselines.
   • We provide a theoretical analysis explaning why REO-RL is training-efficient.
3. Are the the efficiency frontiers useful in our design of REO-RL?
   • It is through the efficiency frontiers that we found using the exponential budget selection is principled in REO-RL. (Sec 5.2). This further motivates us to propose REO-RL(Exp) ad REO-RL(Exp)-Coef=1 as practical implementations.
   • We show via an ablation study that exponential budget selection is critical for reasoning efficiency. Please see our response to [W3,Q3] below.

To summarize, our work introduces:

• Efficiency frontiers as the first large-scale estimation of optimal reasoning efficiency.
• REG as a practical metric for quantifying gaps to optimality.
• REO-RL(Exp) as a training-efficient and practical algorithm, empirically and theoretically justified.

We hope this clarifies our methodology and adequaetly addresses the reviewer's concern. We appreciate the reviewer's consideration and are happy to address any further questions.

[W1,W4,Q2] Large-Scale Efficiency Frontier Estimation

To ensure representative coverage of the best methods across various token budgets, we run RL training with 3 classes of algorithms, covering 8 distinct algorithms and 15 unique training configurations in total. Each individual run consumes at least 2K and 4K GPU hours for each run in the 1.5B and 7B scales, respectively. For each run, a set of checkpoints are sampled for evaluation. In total, 186 and 218 models in 1.5B and 7B settings, respectively, are evaluated for constructing the efficiency frontiers. Our large-scale experiments provide statistically meaningful frontiers that empirically approximate the optimal reasoning efficiency.

For each model $\pi_{\theta_i}$, we measure the accuracy across benchmarks under token budgets $\{32,64,\cdots,512,1K,2K,\cdots,32K\}$. Finally, the efficiency frontier for each benchmark is derived by selecting the maximum accuracy across all models for each token budget.

The table below summarizes the algorithm classes, configurations, and model counts:

Further details about the algorithms and frontiers can be found in Line 141-151 and Appendix C.

[W3] Training Efficiency of REO-RL

We thank the reviewer for raising concerns about training efficiency. Actually, REO-RL is training-efficient. Here we provide training efficiency comparison with baselines, and a theoretical analysis for the cost of REO-RL.

To start with, REO-RL generates a response and then computes rewards by,

1. generate a response $y\sim\pi_\theta(\cdot|x)$
2. For each truncated response $y_{:L_i}$, an answer $a_i$ is generated, i.e. $a_i\sim \pi_\theta(\cdot|x, y_{:L_i},\text{[The Final Answer is]})$, with a budget of 10 tokens. Reward is then computed by matching the answer with the ground-truth answer.

1. Training Efficiency Comparison

Below, we provide empirical evidence showing that REO-RL is computationally efficient:

(a) Low Overhead from Answer Generation REO-RL uses a small number of token budgets $N=5$ and the answers are short, i.e. $|a_i|\le 10$. The per-question latency breakdown shows that answer generation adds only 6.4% overhead relative to full response generation:

(b) Faster Training Than Baselines

REO-RL trains faster than Vanilla RL and other RL methods with length rewards. This is because overhead from answer generation is low and REO-RL incentivizes shorter response length.

Specially, RL w. Token Budget excessively reduces length at the cost of severe accuracy drop,also having fast training speed.

2. Theoretical Cost Analysis

Following [1] and [2], we analyze the computation cost for a single input. Let $L_{in}$ be the length of the input, $L_{out}$ be the length of generated response $y$ and $L_{ans}$ be the maximum lengths of answers generated from truncated responses. For a transformer with $P$ parameters, KV size $D$ and GQA ratio $r$, the computation in REO-RL consists of three parts:

• Prefill for Input $x$: $2PL_{in}+2DL_{in}^2$
• Decoding Response $y$: $2PL_{out}+r(2L_{in}+L_{out})L_{out}D$
• Decoding Answers $a_1,\cdots,a_N$: $2PNL_{ans}+r(2L_{in}+2L_{out}+L_{ans})NL_{ans}D$

Why REO-RL is Efficient:

1. Negligible Answer Generation Cost. The input length $L_{in}$ is usually small ($\le 500$) and the response length $L_{out}$ is large, spanning from 5K to 32K. In REO-RL, by default we use $N=5$ and $L_{ans}\le 10$. Since $L_{out}\gg NL_{answer}$, the computation cost is dominated by decoding $y$.
2. KV Cache Reuse: The KV cache of $x$ and $y$ could be reused during answer generation. For more details on KV cache, please refer to SGLang Blog.

[1] Kinetics: Rethinking Test-Time Scaling Laws. https://arxiv.org/pdf/2506.05333

[2] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. https://arxiv.org/abs/2407.21787

[W5,Q3] Utility of Frontiers in REO-RL & Novelty of Exponential Budget Selection

We appreciate the reviewer's thoughtful comments questioning the utility of the frontiers. Below, we clarify practical utility and the novelty of the frontiers:

1. In REO-RL, the frontiers reveal that exponential budget selection is principled for efficient reasoning.

As shown in Fig. 3 (Sec 5.2), oracle budget selection naturally follows an exponential spacing pattern. This further motivates exponential spacing as a principled and practical way to select token budgets. Thus, REO-RL (Exp) is not an arbitrary heuristic, but derived from the inherent structure of the frontiers.

2. Exponential budget selection is critical for reasoning efficiency.

We make a comparison with a linear variant of REO-RL (with Coef=1). Clearly using linear budget selection underperforms the exponential budget selection:

[W2, Q1] Pseudo-Code of REO-RL

Input: 
    - LLM π
    - Dataset D consisting of input prompts and ground-truth answers
    - Token budgets L = [L[1], ..., L[N]]
    - Training steps T

Output: Fine-tuned LLM π*

def Generate(π, x, ans, L):
    y ~ π(· | x)  ▷ Generate full response
    a = []  ▷ Stores answers for truncated responses
    
    ▷ Generate truncated answers in parallel for budgets L[i] < |y|
    for i = 1 to N do
        if L[i] < |y| then
            y_trunc = x + y[:L[i]] + "</think> The Final Answer is: "
            a[i] ~ π(· | y_trunc)  ▷ Answer from truncated response
        else:
            a[i] = ExtractAnswer(y) ▷ Answer from the full response
        
    ▷ Compute reward (Eq. (2) and Eq. (9) in paper)
    reward = compute_reward(y, a, ans, L)  
    
    return reward, y

for t = 1 to T do
    ▷ Sample a batch of prompts and answers
    B ← Sample a training batch from D  
    rewards, responses = [], []
    
    ▷ Parallel rollout for each (x, ans) in B
    for (x, ans) in B do
        reward, response <- Generate(π, x, ans, L)
        
    ▷ PPO update step
    π ← Update with PPO
end for
return π

Note that the responses and rewards are generated in parallel to ensure high training efficiency, known as async training in modern LLM training frameworks such as AReaL and veRL.

We sincerely appreciate the reviewer’s thoughtful feedback and are happy to clarify the remaining points. Below, we address each concern in detail:

1.REO-RL Optimizes Across All Token Budgets

The reviewer raises a point about Eq. (9) appearing to focus only on the full response $y$. However, REO-RL inherently optimizes performance at every token budget, as rewards are computed from truncated responses. Crucially, when $N=L_{max}-1$ and $L_i=i,\forall i$, the REO-RL objective (Eq. 9) reduces exactly to the full efficiency objective (Eq. 6):

$L_{REO-RL}(\theta,D)=E_{x\sim D}[E_{y\sim\pi_\theta(\cdot|x)}[\sum_{i=1}^{Lmax}\frac{1}{2}R(x,\text{Answer}(\pi_\theta, x,y_{:i}))]]$

$\quad\quad\quad\quad\quad\quad=\frac{1}{2}\sum_{i=1}^{Lmax}E_{x\sim D}[E_{y\sim\pi_\theta(\cdot|x)}[R(x,\text{Answer}(\pi_\theta, x,y_{:i}))]]$

$\quad\quad\quad\quad\quad\quad=\frac{1}{2}\sum_{i=1}^{Lmax}J(D,\theta,i) =\frac{1}{2} L_{efficiency}(D,\theta)$

This shows that REO-RL is a practical approximation of optimizing across all budgets. As demonstrated in Sec 5.2 and Figure 3, with $N\ge 5$, the approximation error is negligible, meaning REO-RL effectively improves performance across all budgets.

2. Answer Generation from Truncated Responses

The reviewer raises a valid concern about whether the model is trained to generate answers directly from truncated responses $y_{trunc}$. We clarify that explicit training for this is unnecessary because the model naturally generates well-formatted answers when prompted with:

$y_{trunc}$ + ... The Final Answer is \boxed{

In practice, with a small additional budget (e.g., 10 tokens), the model reliably produces the best possible answer without further reasoning. This approach is simple yet effective, avoiding the need for additional training complexity.

3. Connection Between Frontiers and REO-RL

The reviewer notes a perceived disconnection between the empirical frontier and REO-RL. We emphasize that:

• Frontier -> Full Efficiency Objective (Eq. 6): Minimizing the REG metric (Eq. 5) is equivalent to maximizing the full efficiency objective (Eq. 6), which pushes the model toward the frontier.

• Full Efficiency Objective (Eq. 6) -> REO-RL (Eq. 9): REO-RL (Eq. 9) is a tractable approximation of Eq. 6, converging to it as $N$ increases.

We will revise the manuscript to explicitly link these steps (REG (Eq.5) → full efficiency objective (Eq. 6) → REO-RL (Eq. 9)), making the connection clearer. These revisions would be made in Line 170-`174 and Line 187-191.

4. Broader Contributions

Finally, we highlight that REO-RL is just one part of our contribution. Beyond REO-RL, our key advancements include:

• The first large-scale estimation of optimal reasoning efficiency.
• The REG metric which provides practical measurement of the gap to the optimality. These provide a foundation for future work beyond our proposed algorithm.

We appreciate the reviewer’s thoughtful comments and hope these clarifications resolve the concerns.

We sincerely appreciate the reviewer’s time and thoughtful feedback, which has helped us strengthen our work. Below, we address the key concerns raised:

1. Cross-Domain Generalization (Coding Tasks)
   • We evaluate the math-trained models on coding tasks to show the generalizability of REO-RL.
   • We further include additional results applying the REG framework and REO-RL to Qwen3-4B on coding to further demonstrate the adaptability across domains.
2. Scalability to Larger Models
   • To address the lack of evaluation on advanced large reasoning models, we apply REO-RL to Qwen3-32B, showing consistent improvements in efficiency-performance trade-offs
3. Training Efficiency of REO-RL
   • We provide an empirical comparison showing that training efficiency of REO-RL is competitive with baselines.
   • We provide a theoretical analysis showing why REO-RL is training-efficient.
4. Efficiency Frontier Details
   • We included dedicated description including the specific training algorithms and training configuraitons, and construction method for the frontiers.

We hope this clarifies our methodology and adequately addresses the reviewer's concerns. We’re grateful for the opportunity to improve our work and welcome further discussion.

[W1] Cross-Domain Generalization (Coding Tasks)

To demonstrate the generalizability of REG and REO-RL, we conduct cross-domain evaluations on coding tasks using models trained solely on math data. Additionally, we apply the REG framework and REO-RL to coding by fine-tuning Qwen3-4B on DeepCoder data[1].

1. Cross-Domain Evaluation (Math -> Coding)

We evaluate models trained on math (as in the paper) on two coding benchmarks, CodeContests and LiveCodeBench. We construct cross-domain efficiency frontiers by truncating responses under different token budgets and allowing an extra 512-token budget for code generation. We then compute REG based on the cross-domain efficiency frontiers. 8 responses are generated for evaluation.

Though only trained on math, REO-RL achieves strong generalization to coding, significantly improving efficiency (lower REG) while maintaining accuracy.

DeepSeek-R1-Distill-Qwen-1.5B:

DeepSeek-R1-Distill-Qwen-7B:

2. Applying the REG & REO-RL to Coding (Qwen3-4B)

For frontier construction, due to time constraints, we run RL with different token budgets to estimate the efficiency frontier.

Regarding REO-RL, we run REO-RL (Exp) using $N=5$ exponentially spacing token budgets. To obtain length-constrained rewards, we use the model to generate codes from truncated responses with an addtional generation budget of 512 tokens. REO-RL (Exp) reduces REG and response length by 51.14% and 32.49% on coding while maintaining the overall accuracy.

Qwen3-4B Results on Coding:

[1] DeepCoder: A Fully Open-Source 14B Coder at O3-mini Level. https://huggingface.co/agentica-org/DeepCoder-14B-Preview

[W2] Scalability to Larger Models

We apply REO-RL (Exp) to an advanced LRM, Qwen3-32B using N=5 token budgets for training. Each model is evaluated on AIME24/AIME25/AMC23 with 32 responses. The results show that REO-RL can reduce response length of Qwen3-32B by 10.03% while maintaining the accuracy,indicating that REO-RL can effectively scale to larger models.

[W3] Computational Cost Analysis of REO-RL

We thank the reviewer for raising concerns about training efficiency. Here we provide training efficiency comparison with baselines, and a theoretical analysis for the cost of REO-RL.

To start with, REO-RL generates a response and then computes rewards by,

1. generate a response $y\sim\pi_\theta(\cdot|x)$
2. For each truncated response $y_{:L_i}$, an answer $a_i$ is generated, i.e. $a_i\sim \pi_\theta(\cdot|x, y_{:L_i},\text{[The Final Answer is]})$, with a budget of 10 tokens. Reward is then computed by matching the answer with the ground-truth answer.

1. Training Efficiency Comparison

Below, we provide empirical evidence showing that REO-RL is computationally efficient:

(a) Low Overhead from Answer Generation REO-RL uses a small number of token budgets $N=5$ and short answers, i.e. $|a_i|\le 10$. The per-question latency breakdown shows that answer generation adds only 6.4% overhead relative to response generation:

(b) Faster Training Than Baselines

REO-RL trains faster than Vanilla RL and other RL methods with length rewards because REO-RL encourages shorter responses.

Specially, RL w. Token Budget excessively shrinks length at the cost of severe accuracy drop,also having fast training speed.

2. Theoretical Cost Analysis

Following [1] and [2], we analyze the computation cost for a single input $x$. Suppose the LRM is a transformer with $P$ parameters, KV size $D$ and GQA ratio $r$. Let $L_{in}$ be the length of the input, $L_{out}$ be the length of generated response $y$ and $L_{ans}$ be the maximum lengths of answers generated from truncated responses. The computation in REO-RL consists of three parts:

• Prefill for Input $x$: $2PL_{in}+2DL_{in}^2$
• Decoding Response $y$: $2PL_{out}+r(2L_{in}+L_{out})L_{out}D$
• Decoding Answers $a_1,\cdots,a_N$: $2PNL_{ans}+r(2L_{in}+2L_{out}+L_{ans})NL_{ans}D$

Why REO-RL is Efficient:

1. Negligible Answer Generation Cost. The input length $L_{in}$ is small ($\le 500$) and the response length $L_{out}$ could span from 5K to 32K. In REO-RL, we use $N=5$ and $L_{ans}\le 10$. Therefore the computation cost is dominated by decoding $y$ since $L_{out}\gg NL_{answer}$.

2. KV Cache Reuse: The KV cache of $x$ and $y$ could be reused during answer generation. For more details on KV cache, please refer to SGLang Blog.

[1] Kinetics: Rethinking Test-Time Scaling Laws. https://arxiv.org/pdf/2506.05333

[2] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. https://arxiv.org/abs/2407.21787

[Q1] Further Details on Empirical Reasoning Efficiency Frontiers

To ensure representative coverage of the best methods across varying token budgets, we run RL training with 3 classes of algorithms, covering 8 different distinct algorithms and 15 unique training configurations in total. Each training configuration required substantial computational effort to ensure convergence, with individual run at least 2K and 4K GPU hours for each run in the 1.5B and 7B scales, respectively. For each run, a set of checkpoints are sampled for evaluation. In total, 186 and 218 models in 1.5B and 7B settings, respectively, are evaluated for constructing the efficiency frontiers.

For each model $\pi_{\theta_i}$, we first generate $32$ responses under a 32K token budget and then truncate each response under token budgets $\{32,64,\cdots,512,1K,2K,\cdots,32K\}$. We then generate answers from the truncated responses to compute the length-constrained rewards at different token budgets. Finally, the efficiency frontier for each benchmark is derived by selecting the maximum accuracy across all models for every token budget.

The table below summarizes the algorithm classes, configurations, and model counts:

Further details about the algorithms and frontiers can be found in Line 141-151 and Appendix C.

We sincerely thank the reviewer for the thoughtful feedback, which has helped us improve the clarity and scope of our work. Below, we address each concern in detail.

Generalization to Other Tasks

"Only tested on math problems (AMC/AIME). It's unclear if this generalizes to other reasoning tasks like coding or general QA"

To demonstrate the generalizability of REG and REO-RL, we conduct cross-domain evaluations on coding tasks using models trained solely on math data. Additionally, we apply the REG framework and REO-RL to coding by fine-tuning Qwen3-4B on DeepCoder data[1].

1. Cross-Domain Evaluation (Math -> Coding)

We evaluate models trained on math (as in the paper) on two coding benchmarks, CodeContests and LiveCodeBench. We construct cross-domain efficiency frontiers by truncating responses under different token budgets and allowing an extra 512-token budget for python code generation. We then compute REG based on the corss-domain efficiency frontiers. 8 responses are generated for evaluation for each method.

Even when trained only on math, REO-RL achieves strong generalization to coding, significantly improving efficiency (lower REG) while maintaining accuracy.

DeepSeek-R1-Distill-Qwen-1.5B Results:

DeepSeek-R1-Distill-Qwen-7B Results:

2. Applying the REG & REO-RL to Coding (Qwen3-4B)

For frontier construction, due to time constraints, we run RL with different token budgets to estimate the efficiency frontier.

Regarding REO-RL, we run REO-RL (Exp) using $N=5$ exponentially spacing token budgets. To obtain length-constrained rewards, we use the model to generate python codes from truncated responses with an addtional generation budget of 512 tokens. REO-RL (Exp) reduces REG and response length by 51.14% and 32.49% on coding while maintaining the overall accuracy.

Qwen3-4B Results on Coding:

[1] DeepCoder: A Fully Open-Source 14B Coder at O3-mini Level. https://huggingface.co/agentica-org/DeepCoder-14B-Preview

Potential Outdated Issue of REG

"The 'optimal' frontiers depend entirely on which methods they tried. If someone finds a better fine-tuning approach tomorrow, all the REG measurements become outdated. "

We appreciate the reviewer’s insightful observation about the REG metric. Indeed, as with many performance metric in deep learning, REG’s frontiers may require updates as methods improve. We highlight two key points here:

• Our large-scale benchmarking reveals a fundamental gap that no existing method can fully match the estimated frontier. This suggests that surpassing our current frontier would represent a meaningful advance in the field.
• We present a comprehensive framework for estimating the efficiency frontiers. New models or new methods can be seamlessly incorporated into the framework to update the frontiers and REG measurement, keeping REG up-to-date.

Clarity on Metrics (REG vs. Length-Constrained Rewards)

"The paper introduces many metrics (REG, length-constrained rewards, etc.) but it's not always clear which matter most for real applications."

We first would like to clarify the distinction:

• REG (Reasoning Efficiency Gap) proposed as a metric for evaluating reasoning efficiency. It measures how close a model is to the optimal accuracy-length trade-off.
• Length-constrained rewards are not metrics but used as rewards in REO-RL training, and for frontier estimation.

Importantly, our results also suggest that REG captures the trade-off between accuracy and generation length. As shown in Table 1, methods that achieve low accuracy or long generation length tend to have high REG. In practice, REG can be used as an effective metric for measuring reasoning efficiency for any fine-tuned model.

Improving Clarity

We thank the reviewer for pointing out the clarity issue. We have taken the following steps to enhance the presentation:

• Training Efficiency Analysis: We have added a detailed comparison with other methods, including a theoretical analysis of REO-RL’s computational cost, to explicitly demonstrate its training efficiency. (See our response to Reviewer 7ETN for details.)
• Frontier Construction Details: We now include comprehensive statistics on the specific methods and models used for constructing the frontiers. (See our response to Reviewer 7ETN for details.)
• Improved Table Visualization: As suggested by Reviewer s9q1, we have split Table 1 into sub-figures and sub-tables to improve readability and highlight key takeaways.

We thank the reviewer again for the thoughtful comments. Please let us know if additional clarifications or revisions would be helpful.

We thank the reviewer for the valuable review to our work. These valuable feedback could help us better improve the clarity of our work.

[W1] Confusion in Math Notations

We appreciate the reviewer’s helpful suggestions regarding notation clarity. We have accordingly revised the mathematical notations to ensure consistency and readability. Specifically, following the suggestion of the reviwer,

• we use $a=\text{Answer}(\pi_\theta, x, y_{:L})$ to denote the answer for a truncated response $y_{:L}$, ensuring consistency with Eq.(2).
• we use {$(L, \hat{J}_{optimal}(D, \hat{\theta}, L)))$ | $L\in[1, L{max}]$} to denote the reasoning efficiency frontier.

[W2] Confusion in Table 1

We agree with the reviewer that splitting Table 1 into more focused visualizations will enhance clarity. Specifically, in the revised version, we have included:

• A figure comparing REG, showing that REO-RL consistently outperforms baselines in reasoning efficiency.
• A line plot of accuracy vs. token budget, showing that Vanilla RL does not consistently improve accuracy across token bugets.
• A visualization for accuracy, response length, and REG, illustrating how REG effectively balances trade-off between accuracy and response length.

We believe these changes would greatly improve the clarity of our work. We deeply appreciate the reviewer’s time and valuable suggestions.