acceptodds
Under review as a conference paper at ICLR 2027

Learning Optimal Agents Across Any Budget via Bilevel Optimization

Abstract

Autonomous agents often achieve stronger task performance by consuming more execution resources, leading to increased deployment cost. To improve efficiency, existing budget-aware approaches train agents under particular budget conditions or expose them to multiple predefined budgets.In practical deployment, however, the available budget can vary substantially across scenarios, motivating agents that can perform well across the entire budget range. In this work, we study how to train an agent that perform reliably across varying budget constraints. We transform the objective of maximizing any-budget capability into minimizing the expected minimum sufficient budget required by individual tasks, which naturally yields a coupled bilevel optimization problem over task-specific budget adaptation and policy improvement. Based on this formulation, we propose BABLE (Bilevel Any-Budget Learning for agEnts), which solves the coupled problem through alternating optimization. BABLE combines a Task-Adaptive Budget Controller (TABC), which adapts task-specific budgets from recent successful executions, with Likelihood-Guided Conditional Advantage Optimization (LCAO), which strengthens policy learning from sparse successes under tight budget conditions. Experiments on four agentic benchmarks under both token-level and tool-call level budgets show that BABLE consistently improves performance across the evaluated budget range compared with standard reinforcement learning and budget-aware baselines.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Budget-Aware Learning, Bilevel Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_v4HDOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the question: “How can we train an agent to achieve consistently strong performance under any budget constraint?” The authors reformulate this problem as finding the minimum budget required for each task to achieve a target reliability level (α\alpha). Based on this formulation, they propose BABLE (Bilevel Any-Budget Learning for Agents), which trains the model by alternately optimizing two components:

  1. Task-Adaptive Budget Controller (TABC): Dynamically tightens the budget required for each task based on observed task success.

  2. Likelihood-Guided Conditional Advantage Optimization (LCAO): Enhances the learning signal in sparse-success scenarios.

The authors evaluate BABLE using the Qwen3-8B model on four benchmarks: MuSiQue, GAIA, WebWalkerQA, and FRAMES. They consider two types of budget constraints, token-level and tool-call-level, and evaluate performance under three budget configurations: Any (average), Max (maximum), and Low (low). BABLE demonstrates clear advantages under the Any and Max budget configurations.

Critical strengths

S1.\textbf{S1.} The problem addressed by the authors is highly relevant to real-world applications. Given the widespread use of agents, developing models that achieve high success rates at low cost is of significant practical importance.

S2.\textbf{S2.} The paper is exceptionally clear and well-organized. The background, motivation, and methodology are presented in an accessible manner, and the experimental results are reasonably interpretable. The authors also provide further explanations and insights into the results, which significantly enhance the overall reading experience.

S3.\textbf{S3.} The proposed alternating optimization scheme for TABC and LCAO is clearly presented and reasonably interpretable. The approach also has the potential for broad applicability.

Critical weaknesses

W1.\textbf{W1.} The discussion of the reliability target ( $ \alpha $ ) requires further elaboration. The paper sets ($ \alpha $ = 0.25), but the rationale for this choice is unclear. The authors should also explain how varying ($ \alpha $) affects the method's performance.

W2.\textbf{W2.} The assumptions underlying practical deployment require further validation. In particular, the paper assumes that the success rate increases monotonically with the budget, but provides insufficient empirical evidence to support this assumption. The authors should discuss whether the proposed method remains applicable when this assumption does not hold.

W3.\textbf{W3.} The paper could further discuss how models trained under different budget constraints can deliver tangible cost savings in real-world applications. In particular, it is unclear how a deployed model identifies the task category corresponding to the training setup and consequently determines how to allocate its budget.

Questions for authors

Q1.\textbf{Q1}. The paper assumes that task success rates increase monotonically with the budget. Is there empirical evidence supporting this assumption? Would the algorithm remain effective if the assumption does not hold, or holds only in expectation?

Q2.\textbf{Q2}. Qwen3-8B supports both /think and /no_think modes. Which mode was used in the experiments? In practice, different budget constraints often correspond to different reasoning efforts and reasoning lengths. Would the proposed method remain effective in such settings?

Q3.\textbf{Q3}. How can the proposed method translate into tangible benefits in real-world applications and inference scenarios?

Q4.\textbf{Q4}. What is the rationale for choosing (α\alpha)? How sensitive is the overall algorithm to this hyperparameter?

Q5.\textbf{Q5}. In Table 1, BABLE underperforms LCPO under the Low budget configuration. What accounts for this gap? Is there room to improve the algorithm's performance in low-budget settings?

4 comments

W2&Q1. Budget monotonicity and its scope

Thank you for asking about budget monotonicity. Appendix D establishes monotonicity for each task under the truncation protocol of Eq. (2) with a fixed policy. For a given task and the same rollout randomness, an execution that finishes with a correct answer within the smaller budget still finishes with that answer under the larger budget. The larger cutoff can also admit additional successful executions, as illustrated in Fig. 5. The success event at the smaller budget is therefore a subset of the success event at the larger budget. Taking probabilities yields pθ(x,b1)≤pθ(x,b2)p_\theta(x,b_1)\le p_\theta(x,b_2) for every task xx and b1≤b2b_1\le b_2.

We evaluated Qwen3-8B Vanilla under token cutoffs from 1K to 10K. Accuracy was nondecreasing with budget on all four benchmarks.

Dataset (accuracy %)1K2K3K4K5K6K7K8K9K10K
MuSiQue1.367.6323.7637.8642.3142.7842.9042.9042.9042.90
GAIA1.927.4113.5817.7919.4921.2022.9124.6226.3228.03
WebWalkerQA0.001.274.106.508.248.498.869.089.089.08
FRAMES3.136.7516.3826.4632.1332.6532.7632.7632.7632.76

Q2. Evaluation with and without thinking

Our main Qwen3-8B BABLE evaluation uses thinking mode. We also evaluated eight configurations on the same four benchmarks with thinking disabled in the chat template.

Each cell reports Low / Any / Max accuracy (%). Max is defined as accuracy on the full saved rollouts.

Token budgets. Low uses 3K tokens. Any averages the results from 2K to 8K in steps of 500 tokens.

MethodMuSiQueGAIAWebWalkerQAFRAMES
Vanilla27.26 / 29.91 / 39.6116.18 / 22.23 / 29.586.55 / 6.99 / 7.9318.02 / 22.62 / 27.99
GRPO31.30 / 36.89 / 43.4318.61 / 24.58 / 33.187.26 / 8.36 / 10.0819.33 / 23.76 / 29.23
LCPO22.13 / 25.03 / 27.6612.04 / 14.54 / 16.296.26 / 6.66 / 7.3015.53 / 17.17 / 19.21
BAMAS32.48 / 37.46 / 43.0417.43 / 21.98 / 28.116.72 / 8.07 / 10.5719.67 / 25.70 / 33.40
BATS31.25 / 37.33 / 44.8719.67 / 24.19 / 28.918.46 / 8.95 / 10.3521.04 / 25.93 / 32.47
BudgetThinker29.72 / 33.99 / 39.3721.32 / 23.49 / 28.778.31 / 8.90 / 10.5721.01 / 25.16 / 30.94
AnytimeReasoner30.80 / 36.22 / 41.6519.33 / 22.33 / 28.136.51 / 7.29 / 8.3919.74 / 24.33 / 29.62
BABLE32.10 / 38.11 / 45.1520.57 / 25.27 / 31.938.90 / 9.16 / 10.9820.59 / 26.50 / 33.34

Tool call budgets. Low allows one call. Any averages the results at the limits of one through five calls.

MethodMuSiQueGAIAWebWalkerQAFRAMES
Vanilla6.10 / 23.69 / 39.616.91 / 16.93 / 29.581.67 / 5.35 / 7.933.23 / 15.89 / 27.99
GRPO6.11 / 25.91 / 43.437.80 / 18.87 / 33.181.90 / 6.17 / 10.082.89 / 16.65 / 29.23
LCPO10.49 / 20.40 / 27.667.90 / 12.11 / 16.292.31 / 5.63 / 7.308.32 / 14.49 / 19.21
BAMAS4.83 / 26.99 / 43.046.69 / 16.71 / 28.112.01 / 6.31 / 10.572.68 / 17.76 / 33.40
BATS6.34 / 25.88 / 44.879.33 / 18.17 / 28.911.34 / 6.03 / 10.352.67 / 17.83 / 32.47
BudgetThinker6.27 / 24.59 / 39.376.84 / 17.81 / 28.772.09 / 6.98 / 10.572.83 / 17.56 / 30.94
AnytimeReasoner6.56 / 26.29 / 41.658.80 / 17.05 / 28.132.19 / 5.59 / 8.392.64 / 17.11 / 29.62
BABLE7.42 / 26.78 / 45.159.36 / 19.65 / 31.932.16 / 6.98 / 10.983.62 / 18.71 / 33.34

With thinking disabled, BABLE achieves the highest Any accuracy under token budgets on all four benchmarks and under tool call budgets on GAIA and FRAMES. It also achieves the highest Max accuracy on MuSiQue and WebWalkerQA in both tables.


W1&Q4. Choice of reliability threshold and sensitivity

We chose α=0.25\alpha=0.25 to require two successes out of eight attempts.

We evaluated Qwen3-8B in thinking mode at α=0.50\alpha=0.50, 0.750.75, and 1.001.00. Each cell reports Low / Any / Max accuracy (%) at the Appendix C cutoffs.

Token budgets

α\alphaMuSiQueGAIAWebWalkerQAFRAMES
0.2531.90 / 41.59 / 48.9718.90 / 28.83 / 36.755.96 / 9.66 / 12.4017.98 / 28.46 / 36.15
0.5024.75 / 36.75 / 46.4918.61 / 26.74 / 32.675.17 / 8.13 / 10.6216.46 / 25.61 / 34.50
0.7522.38 / 35.20 / 43.7815.44 / 27.03 / 35.354.83 / 7.56 / 9.5712.69 / 24.47 / 33.12
1.0022.97 / 34.66 / 44.3422.06 / 27.79 / 34.164.90 / 7.43 / 9.7514.19 / 24.87 / 33.31

Tool call budgets

α\alphaMuSiQueGAIAWebWalkerQAFRAMES
0.2510.68 / 37.57 / 48.9716.94 / 31.12 / 36.752.93 / 9.82 / 12.408.34 / 26.85 / 36.15
0.504.29 / 34.06 / 46.4915.65 / 27.90 / 32.672.16 / 7.93 / 10.624.97 / 24.51 / 34.50
0.757.10 / 33.48 / 43.7816.52 / 29.76 / 35.353.10 / 7.66 / 9.575.77 / 23.90 / 33.12
1.003.50 / 32.44 / 44.3415.72 / 29.68 / 35.032.08 / 7.58 / 9.754.46 / 24.08 / 33.31

The α=0.25\alpha=0.25 reference from Table 1 gives the highest Anytime accuracy in all eight combinations of dataset and budget type, exceeding the best result at a higher target in each combination by 1.04–4.84 percentage points. Among the three higher targets, α=0.50\alpha=0.50 gives the highest Anytime accuracy under both token and tool call budgets on MuSiQue, WebWalkerQA, and FRAMES. On GAIA, the best Anytime results under token and tool call budgets among the three occur at α=1.00\alpha=1.00 and α=0.75\alpha=0.75, respectively.


Q3&W3. Deployment under varying inference budgets

An agent service may receive the same type of request throughout the day, while the compute and API capacity available to each user changes with traffic. For example, during daytime peaks, a search agent may have a smaller budget for tokens or API calls per request to serve more users within the service’s latency target. At night, the same service can raise the cap so the agent has more room to check additional sources or refine its answer when the task calls for it. BABLE aims to make the same trained policy perform well across these budget levels. The service can keep one checkpoint loaded, set a cap for each request based on current load, and enforce it during execution. A tight cap limits how much work each request can consume at peak times. A looser cap allows longer executions to finish when spare capacity is available. The service can change this cap as traffic changes while serving both cases with the same model.


Q5. Performance at low budgets relative to LCPO

LCPO subtracts a scaled token cost penalty λc/s\lambda c/s from the binary correctness reward yy. This favors shorter executions even among correct trajectories and gives cheaper failures a higher reward. The short refusals observed on LLaMA illustrate the resulting incentive for reward hacking (Appendix E). BABLE gives a reward of 1 to correct trajectories within each task's TABC budget and uses LCAO to reinforce them. Training a single policy across budgets requires the policy to finish early when a short solution suffices and to keep reasoning or using tools when the task requires more steps. To maintain strong performance at larger budgets, BABLE gives up some accuracy under tight budgets on some benchmarks. LCPO leads by 0.11 to 0.52 points at 3K on GAIA, WebWalkerQA, and FRAMES. BABLE leads by 2.73 to 10.68 points at Max on those benchmarks and achieves higher Anytime Accuracy under token budgets on all four (Table 1).


We will incorporate your valuable feedback into the revised PDF and upload the updated version shortly.

Thank you for the response. Most of my concerns have been addressed.

Thank you for carefully considering our responses and for your thoughtful follow-up. We are glad that most of your concerns have been addressed. Your constructive feedback has helped us clarify the theoretical arguments and strengthen the experimental analysis. We sincerely appreciate your time and the valuable discussion.

Reviewer_6V7bOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to train agents that can perform well under any given budget constraints. Authors define any-budget capabilities as to maximize "the area that has solvable solutions under the entire valid budget interval", and transform this target to minimizing each task's expected minimal sufficient budget E_x[b_\theta^*(x;\alpha)], and form it as a bilevel optimization problem: estimating the minimal sufficient budget of each task under current policy at lower level, and lower down the budget itself by optimizing the policy in the upper level.

The problem is solved with alternating optimization that includes two modules. The authors use TABC to maintain individual training budget for each task, and use LCAO to amplify the learning signal under tight budget where succeed samples are scarce. The paper compares their proposed budget methods with GRPO, LCPO, BAMAS, BATS, BudgetThinker, and AnytimeReasoner and show promising results.

Critical strengths
  1. The motivation is clear. Single-budget training will specialize the policy to a given interval, which is the real challenge in deployment. The paper also discusses both tool-call and token costs, which is close to real settings.

  2. the proposed TABC is simple and effective. There is only one tunable hyperparameter \alpha and is easy to reproduce.

  3. The ablation is comprehensive, for example, Table 5 gives the 2x2 decomposition of {Fixed, TABC} \times {GRPO, LCAO} and Appendix F evaluates whether budget can be recovered.

Critical weaknesses
  1. the novelty of bilevel optimization may be overclaimed and is less rigorous. For example, there is not a proof in the paprt showing that the surrogate of log p(x, b_{t+1}) could lower E[b*] in the upper level training. The authors have cited hypergradient paper, but the methodology does not show hypergradient itself.

  2. The mechanism of TABC is not very clear and there lacks a close baseline. when \alpha = 0.25 and G = 8, the budget is set to the second smallest cost, and there are only ~2 cheapest trajectories getting positive advantage after truncation. This is similar to a per-task, rank-based length reward. The paper does not compare with methods like ThinkPrune, which gradually minimizes the truncation upper bound.

  3. Experiment robustness can be improved: the performance increase is only 1-2 points and the std is 0.5; the low-budget setting is different (1 tool call for Qwen3-8B, 2 for LLaMA3.1-8B) without explanation; RQ2 does not report the actual cost; the stability report in Figure 4 is only based on single run.

Questions for authors
  1. The max accuracy of all methods are the same under the token and tool-call settings (Tables 1/2/5). Does each method use a single checkpoint for both evals? If yes, which cost type is BABLE trained with?
  2. Could the authors be more clear about the definition of Cost Penalty and Conditional Reward?
  3. LCPO is close to 0 in LLaMA, and AnytimeReasoner is lower than Vanilla under tool call. Is this expected, or are the parameters of the baselines carefully tuned?
  4. What is the average token and tool call for each method under non-constraint?
5 comments

W1. Bilevel formulation

Thank you for asking how the surrogate based on log success probability in Eq. (11) relates to the expected minimum sufficient budget in Eq. (9). To relate Eq. (11) to Eq. (9), we consider the LCAO update, which optimizes the surrogate while holding each task’s TABC budget estimate fixed. A local sufficient condition follows by implicit differentiation. Fix a task xx. Assume that pθp_\theta is continuously differentiable near an interior threshold crossing pθ(x,bθ∗)=αp_\theta(x,b^{\ast}_\theta)=\alpha and that ∂bpθ(x,bθ∗)>0\partial_b p_\theta(x,b^{\ast}_\theta) > 0. Let θ(t)=θ+td\theta(t)=\theta+td follow a policy update direction dd, and set b(t)=bθ(t)∗(x;α)b(t)=b^{\ast}_{\theta(t)}(x;\alpha). The threshold equality pθ(t)(x,b(t))=αp_{\theta(t)}(x,b(t))=\alpha holds locally. In ∇θpθ(x,bθ∗)\nabla_\theta p_\theta(x,b^{\ast}_\theta), the budget is held fixed at bθ∗b^{\ast}_\theta. Differentiating with respect to tt and evaluating at t=0t=0 gives

0=⟨∇θpθ(x,bθ∗),d⟩+∂bpθ(x,bθ∗),b′(0).0 = \langle \nabla_\theta p_\theta(x,b^{\ast}_\theta),d\rangle + \partial_b p_\theta(x,b^{\ast}_\theta)\\,b'(0).

Since b′(0)=⟨∇θbθ∗(x;α),d⟩b'(0)=\langle \nabla_\theta b^{\ast}_\theta(x;\alpha),d\rangle, solving for b′(0)b'(0) yields

⟨∇θbθ∗(x;α),d⟩=−⟨∇θpθ(x,bθ∗),d⟩∂bpθ(x,bθ∗).\langle \nabla_\theta b^{\ast}_\theta(x;\alpha),d\rangle = -\frac{\langle \nabla_\theta p_\theta(x,b^{\ast}_\theta),d\rangle}{\partial_b p_\theta(x,b^{\ast}_\theta)}.

Increasing success at a task's true boundary therefore reduces its sufficient budget to first order. If the update preserves or increases success at every boundary, increases it strictly on a set of tasks with positive probability, and differentiation can pass through the expectation, the mean sufficient budget decreases to first order. On a discrete budget grid, a sufficient condition is to preserve feasibility at the previous budget and make a lower budget feasible for some tasks. Equation (11) uses the budgets estimated by TABC to optimize success near each task’s reliability threshold. Under the conditions above, improvements at the true budget boundaries reduce the mean minimum sufficient budget.

We ran additional experiments to further validate BABLE’s ability to reduce the minimum sufficient budget. Following Appendix I, we estimate the minimum sufficient budgets in Eq. (9) for Qwen3-8B and LLaMA-3.1-8B on MuSiQue, WebWalkerQA, and FRAMES. Qwen3-8B

MethodMuSiQueWebWalkerQAFRAMES
Vanilla3,780 / 2.554,804 / 3.003,334 / 2.28
GRPO3,272 / 2.454,083 / 2.633,307 / 2.34
LCPO3,033 / 2.193,727 / 2.333,179 / 2.41
BAMAS3,379 / 2.234,418 / 2.743,464 / 2.29
BATS3,028 / 2.263,934 / 2.493,337 / 2.32
BudgetThinker2,736 / 2.154,286 / 2.773,418 / 2.35
AnytimeReasoner2,723 / 2.793,143 / 2.613,241 / 3.28
BABLE2,643 / 2.113,122 / 2.033,163 / 2.22

LLaMA-3.1-8B

MethodMuSiQueWebWalkerQAFRAMES
Vanilla5,317 / 9.334,523 / 7.365,267 / 9.63
GRPO4,042 / 5.884,172 / 5.284,323 / 6.56
LCPO10,000 / 20.009,709 / 19.4210,000 / 20.00
BAMAS4,950 / 8.674,811 / 8.306,311 / 11.42
BATS3,957 / 5.634,699 / 7.204,995 / 7.92
BudgetThinker3,467 / 4.814,479 / 7.013,772 / 5.16
AnytimeReasoner3,481 / 5.574,493 / 7.424,011 / 6.97
BABLE3,336 / 4.424,038 / 5.193,770 / 4.90

BABLE achieves the lowest estimated normalized minimum sufficient budget among all evaluated methods in all 12 comparisons, covering two backbones, three datasets, and both token and tool call budgets.


W2. TABC and ThinkPrune

With α=0.25\alpha=0.25 and eight observations, TABC sets the next budget to the second lowest successful cost and keeps the current budget if fewer than two rollouts succeed. With distinct successful costs, exactly two successes in the estimation sample fit the new cap. In each new rollout group, every correct trajectory within the cap receives the same binary reward, and LCAO computes advantages from that group’s success count.

Linear Budget Decay (Sec. 4.2, Fig. 3) adapts iterative ThinkPrune’s global schedule to our agent setting by lowering a shared token cap at preset training steps. All RQ2 variants use LCAO to isolate the effect of the budget schedule. We further compare TABC with alternative budget truncation and tightening strategies. Random Budget samples from preset caps, TABC + Low-Budget adds a final stage with a low cap, and TABC adapts each task’s cap using its successful trajectories. TABC achieves the highest Anytime, Max, and Low accuracy on all four benchmarks. Adding the final stage lowers Low accuracy on all four.

The table below reports results for the four budget schedules in Fig. 3. Each cell gives Anytime / Max / Low accuracy (%) under token budgets.

MethodMuSiQueGAIAWebWalkerQAFRAMES
Linear Budget Decay40.74 / 48.76 / 31.5626.37 / 35.55 / 17.827.71 / 10.15 / 3.9824.83 / 34.70 / 14.67
Random Budget41.34 / 48.18 / 31.5624.01 / 28.87 / 18.039.12 / 11.25 / 5.5226.58 / 33.74 / 17.58
TABC + Low-Budget40.73 / 48.01 / 27.2325.97 / 34.25 / 17.718.87 / 11.09 / 5.2426.28 / 32.68 / 16.00
TABC41.59 / 48.97 / 31.9028.83 / 36.75 / 18.909.66 / 12.40 / 5.9628.46 / 36.15 / 17.98

W3. Checkpoint reuse and the Low and Max points

Yes. Tables 1, 2, and 5 evaluate the same checkpoint for each method and backbone under both token and tool call budgets, yielding identical full-budget Max accuracy. Although BABLE trains with token-based budgets, it improves Anytime Accuracy under both constraints. On Qwen3-8B, BABLE surpasses the strongest baseline by 1.02–2.33 points under tool call budgets (Table 1) and achieves the lowest estimated normalized minimum sufficient tool call budget on three benchmarks for both backbones, suggesting improved efficiency across both resources.

The Low cutoff is set to one tool call for Qwen3-8B and two for LLaMA-3.1-8B, as all 28 LLaMA baseline scores fall below 1% at one call. The table reports LLaMA accuracy (%) as one call / two calls.

MethodMuSiQueGAIAWebWalkerQAFRAMES
Vanilla0.00 / 1.020.00 / 0.000.00 / 0.900.09 / 0.83
GRPO0.34 / 2.030.00 / 0.000.11 / 0.790.00 / 0.95
LCPO0.00 / 0.000.00 / 0.000.22 / 0.220.00 / 0.00
BAMAS0.00 / 2.040.62 / 1.260.34 / 1.120.09 / 0.83
BATS0.34 / 3.390.00 / 1.270.11 / 0.670.00 / 1.78
BudgetThinker0.34 / 3.470.00 / 3.200.56 / 2.160.74 / 1.68
AnytimeReasoner0.34 / 5.140.62 / 1.890.37 / 1.410.28 / 3.58
BABLE0.00 / 3.840.65 / 3.250.33 / 1.480.19 / 2.28

Q2&Q3. Reward definitions and baseline tuning

Cost Penalty uses y−λc/sy-\lambda c/s, where yy is binary correctness, cc is the rollout cost, ss is the cost scale, and λ\lambda is the penalty weight. Conditional Reward uses y 1{c≤b}y\,\mathbf{1}\{c\le b\}, where bb is the task budget. In Fig. 4, Conditional Reward and BABLE share TABC’s budget updates and differ in how they compute policy advantages.

AnytimeReasoner. Both methods train under token budgets and use the same evaluation cutoffs. Compared with Vanilla, AnytimeReasoner improves Anytime Accuracy under token budgets on all four benchmarks, yet scores lower under tool call budgets on MuSiQue, GAIA, and FRAMES (Table 1). We attribute this gap to a limitation of AnytimeReasoner’s ability to transfer across budget types. By adapting budgets to each task and reinforcing successes within them, BABLE outperforms AnytimeReasoner under both budget types on all four benchmarks using a single checkpoint.

Normalized minimum sufficient budget at α=0.25\alpha=0.25

MethodMuSiQueWebWalkerQAFRAMES
Vanilla3,780 / 2.554,804 / 3.003,334 / 2.28
AnytimeReasoner2,723 / 2.793,143 / 2.613,241 / 3.28
BABLE2,643 / 2.113,122 / 2.033,163 / 2.22

LCPO on LLaMA-3.1-8B-Instruct. We used the same penalty settings on both backbones (λ=1\lambda=1, s=10,000s=10{,}000). LCPO continued to solve tasks on Qwen3-8B. On LLaMA, 4,594 of 4,632 rollouts (99.18%) made zero tool calls, and only two answered correctly. Any positive cost penalty rewards cheaper failures more, creating an incentive to terminate early (Appendix E). BABLE assigns zero outcome reward to incorrect rollouts and tightens budgets using successful executions.

We consider these results expected given the baselines’ limitations. We see little evidence that hyperparameter tuning explains these outcomes. BABLE effectively addresses both limitations.


W3&Q4. Realized inference cost and robustness

For Qwen3-8B, each cell reports mean token count in the response sequence / mean tool calls per rollout. We average the actual costs of all saved full rollouts regardless of answer correctness. Lower values indicate lower resource use alone and should be interpreted alongside accuracy. Our optimization target is the minimum sufficient budget b∗b^* reported in Section 1, which measures the budget needed to reach a target reliability.

MethodMuSiQueGAIAWebWalkerQAFRAMES
Vanilla3,305 / 2.394,658 / 2.464,314 / 2.873,618 / 2.46
GRPO3,446 / 2.604,171 / 2.244,215 / 2.843,832 / 2.70
LCPO2,101 / 1.472,753 / 1.173,090 / 2.062,264 / 1.40
BAMAS3,459 / 2.464,244 / 2.193,978 / 2.703,774 / 2.51
BATS3,366 / 2.604,308 / 2.343,980 / 2.713,823 / 2.69
BudgetThinker3,253 / 2.574,109 / 2.263,805 / 2.733,660 / 2.58
AnytimeReasoner3,710 / 4.504,670 / 5.874,991 / 5.054,235 / 5.38
BABLE3,328 / 2.504,234 / 2.314,074 / 2.803,833 / 2.68

For the RQ2 schedules, the following table gives the same cost statistics for the available saved runs.

MethodMuSiQueGAIAWebWalkerQAFRAMES
GRPO3,446 / 2.604,171 / 2.244,215 / 2.843,832 / 2.70
Linear Budget Decay3,160 / 2.484,658 / 2.804,564 / 3.374,245 / 3.12
Random Budget3,710 / 4.504,670 / 5.874,991 / 5.054,235 / 5.38
TABC + Low-Budget3,322 / 2.494,198 / 2.324,041 / 2.783,780 / 2.64
TABC3,328 / 2.504,234 / 2.314,074 / 2.803,833 / 2.68

To address the concern about the single run in Fig. 4, we report LCAO’s Anytime Accuracy on GAIA under token budgets across three runs. At steps 0, 30, 60, 90, 120, and 150, the mean ± standard deviation (%) is 21.59 ± 0.31, 27.59 ± 0.42, 26.78 ± 0.47, 29.80 ± 0.36, 32.30 ± 0.49, and 28.83 ± 0.54, respectively.


We will incorporate your valuable feedback into the revised PDF and upload the updated version shortly.

Reviewer_2DWbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces BABLE to train agents under variable inference budgets. TABC adapts per-task budgets from successful trajectory costs, and LCAO leverages success-rate advantage normalization for sparse-success learning. Targeted at minimizing the expected minimum sufficient budget, the method is tested on four QA benchmarks.

Critical strengths

The problem has practical relevance. Task-aware budget adaptation is intuitive, and experiments cover diverse benchmarks, budget settings and backbones. The component analysis in Appendix H is informative.

Critical weaknesses
  1. The theoretical formulation is insufficiently justified for the proposed algorithm. Optimizing log-success at the current budget does not guarantee a lower expected minimum sufficient budget. Moreover, Anytime Accuracy averages success probabilities, while the theoretical objective concerns solvability above a reliability threshold. Validation in Appendix I is limited to GAIA.
  2. TABC estimates budgets from only 8 rollouts, taking the second-smallest successful cost by default. Rare low-cost successes can trigger over-aggressive budget shrinkage with no recovery mechanism.
  3. LCAO’s novelty over MaxRL-style likelihood optimization is unclear. It reinforces rare observed successes but yields no learning signal when all rollouts fail, so its sparse-success claims require refinement.
  4. Several implementation details are inconsistent or unclear: Appendix C defines the low tool-call budget as one call versus two in Appendix E. Reward and importance ratio computation for budget-truncated trajectories is unspecified.
Questions for authors
  1. Under what conditions does the log-success surrogate minimize the expected minimum sufficient budget?
  2. Please show budget stability across reliability thresholds and rollout numbers, including the share of zero-success training groups.
  3. Clarify LCAO’s distinctions from MaxRL, plus the evaluation and truncation details noted above.
3 comments

W1&Q1. The surrogate based on log success probability and minimum sufficient budgets beyond GAIA

To relate Eq. (11) to Eq. (9), we consider the LCAO update, which optimizes the surrogate while holding each task’s TABC budget estimate fixed. A local sufficient condition follows by implicit differentiation. Fix a task xx. Assume that pθp_\theta is continuously differentiable near an interior threshold crossing pθ(x,bθ∗)=αp_\theta(x,b^{\ast}_\theta)=\alpha and that ∂bpθ(x,bθ∗)>0\partial_b p_\theta(x,b^{\ast}_\theta) > 0. Let θ(t)=θ+td\theta(t)=\theta+td follow a policy update direction dd, and set b(t)=bθ(t)∗(x;α)b(t)=b^{\ast}_{\theta(t)}(x;\alpha). The threshold equality pθ(t)(x,b(t))=αp_{\theta(t)}(x,b(t))=\alpha holds locally. In ∇θpθ(x,bθ∗)\nabla_\theta p_\theta(x,b^{\ast}_\theta), the budget is held fixed at bθ∗b^{\ast}_\theta. Differentiating with respect to tt and evaluating at t=0t=0 gives

0=⟨∇θpθ(x,bθ∗),d⟩+∂bpθ(x,bθ∗),b′(0).0 = \langle \nabla_\theta p_\theta(x,b^{\ast}_\theta),d\rangle + \partial_b p_\theta(x,b^{\ast}_\theta)\\,b'(0).

Since b′(0)=⟨∇θbθ∗(x;α),d⟩b'(0)=\langle \nabla_\theta b^{\ast}_\theta(x;\alpha),d\rangle, solving for b′(0)b'(0) yields

⟨∇θbθ∗(x;α),d⟩=−⟨∇θpθ(x,bθ∗),d⟩∂bpθ(x,bθ∗).\langle \nabla_\theta b^{\ast}_\theta(x;\alpha),d\rangle = -\frac{\langle \nabla_\theta p_\theta(x,b^{\ast}_\theta),d\rangle}{\partial_b p_\theta(x,b^{\ast}_\theta)}.

Increasing success at a task's true boundary therefore reduces its sufficient budget to first order. If the update preserves or increases success at every boundary, increases it strictly on a set of tasks with positive probability, and differentiation can pass through the expectation, the mean sufficient budget decreases to first order. On a discrete budget grid, a sufficient condition is to preserve feasibility at the previous budget and make a lower budget feasible for some tasks. Equation (11) uses the budgets estimated by TABC to optimize success near each task’s reliability threshold. Under the conditions above, improvements at the true budget boundaries reduce the mean minimum sufficient budget.

We ran additional experiments to further validate BABLE’s ability to reduce the minimum sufficient budget. Following Appendix I, we estimate the minimum sufficient budgets in Eq. (9) for Qwen3-8B and LLaMA-3.1-8B on MuSiQue, WebWalkerQA, and FRAMES.

Qwen3-8B

MethodMuSiQueWebWalkerQAFRAMES
Vanilla3,780 / 2.554,804 / 3.003,334 / 2.28
GRPO3,272 / 2.454,083 / 2.633,307 / 2.34
LCPO3,033 / 2.193,727 / 2.333,179 / 2.41
BAMAS3,379 / 2.234,418 / 2.743,464 / 2.29
BATS3,028 / 2.263,934 / 2.493,337 / 2.32
BudgetThinker2,736 / 2.154,286 / 2.773,418 / 2.35
AnytimeReasoner2,723 / 2.793,143 / 2.613,241 / 3.28
BABLE2,643 / 2.113,122 / 2.033,163 / 2.22

LLaMA-3.1-8B

MethodMuSiQueWebWalkerQAFRAMES
Vanilla5,317 / 9.334,523 / 7.365,267 / 9.63
GRPO4,042 / 5.884,172 / 5.284,323 / 6.56
LCPO10,000 / 20.009,709 / 19.4210,000 / 20.00
BAMAS4,950 / 8.674,811 / 8.306,311 / 11.42
BATS3,957 / 5.634,699 / 7.204,995 / 7.92
BudgetThinker3,467 / 4.814,479 / 7.013,772 / 5.16
AnytimeReasoner3,481 / 5.574,493 / 7.424,011 / 6.97
BABLE3,336 / 4.424,038 / 5.193,770 / 4.90

BABLE achieves the lowest estimated normalized minimum sufficient budget among all evaluated methods in all 12 comparisons, covering two backbones, three datasets, and both token and tool call budgets.


W2. Finite sample contraction, recovery, and zero success groups

We tested whether TABC tightens budgets enough that all correct rollouts in a group exceed the cap, removing the group’s positive reward signal within budget. Across six epochs of Qwen3-8B training, we compared the share of groups with no correct rollout within budget to the share with no correct rollout at any cost.

EpochNo success within budgetZero success
149.80%49.80%
249.15%49.15%
348.79%48.79%
447.71%47.69%
547.40%47.33%
646.93%46.77%

Tightening the budget can exclude all correct rollouts in a group, but this was rare in our diagnostic run. Across the first 150 steps, only 31 of 38,400 groups (0.08%) produced correct answers exclusively above the assigned budget. As budgets tightened, the gap between the two rates grew slightly, reaching about 0.15 percentage points across the six epochs.

Appendix F compares BABLE with SLACK, which allows the assigned budget to increase. Table 3 reports the following accuracies under token budgets. Each cell gives Anytime / Max / Low accuracy (%).

MethodMuSiQueGAIAWebWalkerQA
SLACK40.23 / 47.19 / 28.4925.15 / 35.28 / 17.319.05 / 11.39 / 5.43
BABLE41.59 / 48.97 / 31.9028.83 / 36.75 / 18.909.66 / 12.40 / 5.96

BABLE scored higher on all three metrics across the three benchmarks. The comparison measures the combined effect of sampling at the maximum budget and budget recovery. Together with the low frequency of groups whose correct rollouts all exceeded the budget, this supports our choice to omit the SLACK variant tested in Appendix F. Relaxing the budget criterion solely because successes within budget are scarce would give credit to more costly correct rollouts and could make it harder for the policy to learn efficient ways to succeed.


W3. Relation to MaxRL and treatment of groups where every rollout fails

Equation (17) shares MaxRL’s normalization by the mean binary reward. MaxRL uses multiple rollouts to approximate log⁡pθ(x)\log p_\theta(x), the log probability of solving task xx. LCAO extends the objective to log⁡pθ(x,bt(x))\log p_\theta(x,b_t(x)), where success requires a correct answer within the token or tool call budget for a single rollout. Another BABLE’s contribution is to couple this likelihood objective with budget adaptation. TABC updates each task’s budget from the costs of successful rollouts, and LCAO improves the policy at that fixed budget.

Table 5 tests this coupling on Qwen3-8B by pairing GRPO and LCAO with both fixed budgets and budgets that adapt to each task. Each cell below reports

Anytime Accuracy (%) under token / tool call budgets.

MethodMuSiQueGAIAWebWalkerQAFRAMES
FixedGRPO40.63 / 32.7420.36 / 22.937.91 / 7.2125.89 / 22.82
FixedLCAO40.74 / 34.0026.37 / 26.667.71 / 6.9024.83 / 21.86
TABC-GRPO40.36 / 33.9326.60 / 27.039.36 / 8.4427.04 / 23.96
BABLE (TABC + LCAO)41.59 / 37.5728.83 / 31.129.66 / 9.8228.46 / 26.85

To isolate the contributions of TABC and LCAO, we compare BABLE against FixedLCAO (LCAO without adaptive budgets) and TABC+GRPO (TABC without LCAO). BABLE consistently outperforms both variants across all datasets and budget types in Anytime Accuracy. In contrast, replacing GRPO with LCAO under fixed budgets yields mixed results, suggesting that LCAO is most effective when coupled with adaptive budget allocation.

Regarding the reviewer’s question about groups in which every rollout fails, binary outcome rewards in RLVR assign zero reward to every rollout, so both LCAO and GRPO assign zero advantage across the group. This is the intended behavior because giving positive credit to a failed rollout would reinforce an incorrect trajectory. When a group contains a few successes within budget, LCAO gives those rollouts more weight.


W4. Low tool call budgets and truncated rollouts

Low allows one tool call for Qwen3-8B (Table 1) and two for LLaMA-3.1-8B (Table 2). Two calls better distinguish the LLaMA methods, as all 28 baseline scores are below 1% at one call. We will clarify both cutoffs in Appendix C and report the results at one call. The table reports LLaMA-3.1-8B accuracy (%) as one call / two calls.

MethodMuSiQueGAIAWebWalkerQAFRAMES
Vanilla0.00 / 1.020.00 / 0.000.00 / 0.900.09 / 0.83
GRPO0.34 / 2.030.00 / 0.000.11 / 0.790.00 / 0.95
LCPO0.00 / 0.000.00 / 0.000.22 / 0.220.00 / 0.00
BAMAS0.00 / 2.040.62 / 1.260.34 / 1.120.09 / 0.83
BATS0.34 / 3.390.00 / 1.270.11 / 0.670.00 / 1.78
BudgetThinker0.34 / 3.470.00 / 3.200.56 / 2.160.74 / 1.68
AnytimeReasoner0.34 / 5.140.62 / 1.890.37 / 1.410.28 / 3.58
BABLE0.00 / 3.840.65 / 3.250.33 / 1.480.19 / 2.28

For the reward after truncation, Algorithm 1 assigns a reward of 1 only if the rollout produces a correct final answer within budget, and 0 otherwise. If no rollout succeeds within budget, the implementation can use answer correctness alone to compute advantages. If all answers are incorrect, all advantages are zero. For the importance ratio, Eq. (19) divides the current policy probability by the old policy probability for the same sampled action and history. The clipped loss uses only retained tokens generated by the model, with tool outputs and padding masked.

Q2. Sensitivity Analysis

To assess whether TABC tightens budgets too aggressively, we vary the training rollout count per task and the reliability threshold α\alpha for Qwen3-8B. Both tables report Low / Any / Max accuracy (%) under token budgets.

Training rollout count

The rollout comparison uses a nominal reliability target of α=0.25\alpha=0.25. The results for eight training rollouts come from BABLE in Table 1.

Training rollouts per taskMuSiQueGAIAWebWalkerQAFRAMES
425.31 / 38.29 / 48.1117.31 / 24.86 / 32.275.43 / 8.6 / 11.3916.23 / 26.54 / 33.68
831.90 / 41.59 / 48.9718.90 / 28.83 / 36.755.96 / 9.66 / 12.4017.98 / 28.46 / 36.15
1632.84 / 41.87 / 49.6818.61 / 29.45 / 37.736.17 / 10.22 / 13.1218.34 / 29.87 / 37.75

Increasing from 4 to 8 rollouts improves Anytime Accuracy on all four benchmarks. The smaller gains at 16 support using 8 rollouts to balance accuracy and sampling cost.

Reliability threshold

For the three additional reliability targets, TABC uses a budget estimation window with a capacity of eight rollouts per task. The α=0.25\alpha=0.25 reference comes from Table 1.

αMuSiQueGAIAWebWalkerQAFRAMES
0.2531.90 / 41.59 / 48.9718.90 / 28.83 / 36.755.96 / 9.66 / 12.4017.98 / 28.46 / 36.15
0.5024.75 / 36.75 / 46.4918.61 / 26.74 / 32.675.17 / 8.13 / 10.6216.46 / 25.61 / 34.50
0.7522.38 / 35.20 / 43.7815.44 / 27.03 / 35.354.83 / 7.56 / 9.5712.69 / 24.47 / 33.12
1.0022.97 / 34.66 / 44.3415.06 / 27.79 / 34.164.90 / 7.43 / 9.7514.19 / 24.87 / 33.31

The default α=0.25\alpha=0.25 achieves the highest Anytime Accuracy on all four benchmarks. Higher thresholds can delay budget tightening when successes are sparse.


We will incorporate your valuable feedback into the revised PDF and upload the updated version shortly.

Comments on the paper

1 comment

Summary of Rebuttal

We sincerely thank the Area Chair and reviewers for their time and constructive feedback. Below we summarize the concerns addressed, supporting evidence, and core contributions of BABLE. Detailed responses are available in the individual review threads.

Rebuttal Process

The table groups related questions and summarizes the additional experiments and clarifications. A check mark indicates that a reviewer raised at least one question within that group.

Concern2DWb6V7bv4HDLocation in revision / rebuttalMain result or clarification
Theoretical justification and sufficient budget validation✓✓Appendices I, K; Figures 10–11Derived local sufficient conditions and extended sufficient budget validation beyond GAIA, with BABLE lowest in all 12 additional comparisons.
Budget sensitivity, contraction, and recovery✓✓Appendices F, J; Tables 3–4, 7–8Added sensitivity analyses; in the diagnostic run, only 0.08% of groups had correct rollouts exclusively above budget. BABLE outperforms SLACK.
Method distinctions and optimization mechanisms✓✓Section 4.2, Figure 3; Appendix H, Table 6; responses to 2DWb W3 and 6V7b W2Clarified the relation to MaxRL, budget selection versus reward assignment, and zero advantages when all rollouts fail; component ablations and alternative budget schedule comparisons support the combined method.
Evaluation protocol, checkpoint reuse, and thinking modes✓✓✓Appendix E; responses to 2DWb W4, 6V7b W3 & Q2, and v4HD Q2Clarified cutoffs, shared checkpoints, truncation rewards, and importance ratios; added evaluation with thinking disabled across eight configurations and four benchmarks.
Statistical robustness, learning dynamics, and actual costs✓Appendix G, Table 5; response to 6V7b W3 & Q4Reported means, standard deviations, LCAO learning dynamics across three runs, and actual token and tool call costs.
Baseline behavior and low budget tradeoffs✓✓Appendix E; responses to 6V7b Q3 and v4HD Q5Explained LCPO’s collapse, AnytimeReasoner’s limited transfer to tool call budgets, and BABLE’s tradeoffs across budget levels.
Budget monotonicity and its scope✓Appendix D; response to v4HD W2 & Q1Established monotonicity for a fixed policy under truncation, supported by results on four benchmarks.
Deployment under varying inference budgets✓Response to v4HD Q3 & W3Clarified deployment with one checkpoint and execution caps that adapt to available resources, without retraining for each budget.

We regret that we did not have the opportunity for further discussion with Reviewer 2DWb. However, many of their concerns overlap with those raised by Reviewers 6V7b and v4HD, both of whom subsequently stated that most of their concerns had been addressed; 6V7b also raised their rating from 2 to 3. During rebuttal, we devoted nearly 4,000 GPU hours to additional experiments, alongside theoretical and implementation clarifications, making every effort to address the concerns with concrete evidence.

Motivation and Core Contributions

The motivation and contributions of BABLE center on three points:

  1. One checkpoint for any budget. Token and API budgets vary across deployment settings. This motivates learning a single agent that performs well under any budget. BABLE pursues this goal using one checkpoint, without switching models or training separate policies.

  2. We propose a bilevel optimization formulation for budget efficiency. We transform the objective of maximizing reliable solvability across budgets into minimizing the expected minimum sufficient budget. This yields a bilevel problem: the lower level identifies each task’s minimum sufficient budget under the current policy, while the upper level improves the policy to reduce these budgets.

  3. Alternating budget adaptation and policy improvement. BABLE couples two modules: one adapts each task’s budget using successful executions, while the other improves the policy’s likelihood of success within that budget. Ablations support this coupling. Across four benchmarks, the same checkpoint trained under token constraints improves Anytime Accuracy under both token and tool call budgets.

Best regards,

The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.