acceptodds
Under review as a conference paper at ICLR 2027

Token-Constrained Mission Completion in Agentic AI: Capacity Curves and Budget-Aware Reasoning Allocation

Abstract

An agentic system is given a task and an allowance. Benchmarks score the first and ignore the second: a run that would have been correct with twice the tokens scores exactly like one that was affordable. We make the allowance part of the state. Writing an architecture as a budget-augmented stochastic Petri net with state , the workflow marking and the remaining budget, makes the constraint structural: a transition the budget cannot pay for is disabled, so its call is never attempted, and exhaustion joins success and error as a third absorbing outcome. The capacity curve , the least budget attaining reliability , becomes computable rather than sampled. Four results follow. Accuracy does not order missions: a strictly more accurate reasoner is strictly worse over an interval of budgets exactly as wide as its price premium, so the inversion is generic, not a counterexample. Every fixed configuration has a reliability ceiling no budget crosses. Two capacity curves must cross whenever the higher-scoring configuration starts paying off later, so a score-ordered leaderboard is budget-invariant only under a condition no benchmark reports. And because spending is irreversible, the decision process is acyclic, so the optimal budget-aware policy is one backward pass. We then test the claims on 8,190 published agent trajectories. Reconstructing what each run spent turns every leaderboard entry into a capacity curve, and the ordering changes with the allowance: the top-scoring configuration has zero observed success below 23,126 tokens (exact paired test against a lower-ranked one, ) and 41 pairs cross. Selecting on capacity rather than score reaches the same reliability with 88% fewer tokens, and 45.7% of that benchmark's recorded failures turn out to be runs that produced no answer at all.

Primary area:
foundation or frontier models, including LLMs
Keywords:
agentic AI, LLM agents, inference-time compute, token budgets, budget-aware reasoning, capacity curves, stochastic Petri nets, resource-aware evaluation, adaptive model routing

Reviews

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

The paper models agent workflows as budget-augmented stochastic Petri nets and introduces capacity curves to measure the minimum token budget required for a target success rate. It derives conditions under which budget constraints reverse configuration rankings and characterizes optimal budget-aware allocation in the model. An analysis of 8,190 published AppWorld trajectories shows substantial ranking changes under counterfactual budget caps, although adaptive budget-aware agents are not evaluated through new deployments.

Critical strengths
  1. Task-level token budgeting is a practically valuable research topic. The paper incorporates the remaining budget into the workflow state and uses capacity curves to characterize the budget needed for a target success rate, informing system selection and resource planning.
  2. The analysis is systematic, covering simplified-model calculations, cost reconstruction from published trajectories, ranking changes under budget constraints, failure types, and cascade strategies. These analyses yield several findings about the relationships among token budgets, accumulated context costs, and task completion.
Critical weaknesses
  1. The evaluation mainly applies budget cutoffs to existing trajectories from agents that were not informed of their remaining budget. An important missing comparison is to run agents with the remaining budget provided at each decision step, allowing them to adjust their plans and spending. This would help assess whether the offline results reflect performance under actual budget-aware execution.
  2. The main empirical findings come from a single benchmark, leaving their generalizability unclear. The ranking reversals and the reported 88% token-budget saving from configuration selection are demonstrated on AppWorld, whose code-execution interface, tool-output lengths, and history-trimming rules may substantially affect the costs of different architectures. The supplementary OpenManus analysis mainly examines cost-growth patterns rather than validating similar ranking reversals.
Questions for authors
  1. How do the capacity curves and rankings change when agents are informed of their remaining budget at each decision step and allowed to adapt their behavior?
  2. Do similar ranking reversals and token-budget savings occur on another benchmark with different tool interfaces and context-management rules?
2 comments
AuthorsOpenReview ↗

Response to E3Ef: both gaps are real — what the paper does and does not show; the 88% re-checked on held-out tasks

Thank you for the constructive review. You identify the two gaps we most want to close, and we agree with both.

W1/Q1: agents told their remaining budget. We have not run this comparison, and it is the paper's main limitation: every empirical result concerns budget-blind configurations, as §6 says (l.326–328, 446–447; Limitations l.484–486). Within that scope the replay is exact, because a budget-blind agent's trajectory does not depend on BB, but it does not tell us what an informed agent would do. The comparison we consider right uses one ReAct agent on AppWorld test_normal in three arms at matched hard caps (around the crossing region of Fig. 2):

  • (a) budget-blind with a hard cap (the replay semantics);
  • (b) told the remaining budget at every step;
  • (c) told the remaining budget plus the reserve rule from our backward induction ("keep enough for the terminal action").

Arm (b) is the idea of Budget Tracker (Liu et al., 2025), which shows search agents their remaining tool-call budget at every step and improves their budget scaling; we will cite it. Our own model predicts gains mainly near the onset: π⋆\pi^\star gains nothing at the 0.90 target and 0.042 at B=14B=14 (§5, l.310–315). We therefore claim no deployment benefit for budget-aware allocation; §5 is a normative model, and we label its allocation results as model-based. If we can complete this comparison before the discussion closes, we will post it here.

W2/Q2: a second benchmark. We agree, and test_challenge does not answer it: it shares AppWorld's interface and trimming rules, so it shows only that the reversal is not an artifact of one task split (Table M14: the top configuration has zero success below 29k tokens, the third returns 0.165 at 10k). OpenManus (E6) validates the cost reconstruction only. Our own E14 shows why your concern matters: removing AppWorld's history trimming moves the cost tail by orders of magnitude (Table M12). We will state the single-benchmark scope in the abstract and §6.

The 88% figure, checked for selection effects (new). We selected on one random half of test_normal and evaluated on the other (1,000 splits), and we selected on test_normal and evaluated on test_challenge:

TargetHeld-out saving, median [95% range]test_normal → test_challenge
0.1090% [87, 96]same choice (93% saving), though neither pick reaches 0.10 at budgets set on test_normal
0.2091% [85, 97]undefined: the pick's ceiling there is 0.192
0.30 (the 88%)88% [0, 96]undefined
0.400% [0, 68]—

The 88% sits where the pick's ceiling (0.339) barely exceeds the target. We will lead with about 90% at targets 0.10–0.20 and report these intervals.

Theory. Reviewers Q1wf and 6FPy found that Theorem 2 needs an extra hypothesis once costs are stochastic; we fix it (general response). The crossing condition (Thm 3), the inversion interval (Thm 1), and all model and replay numbers stand.

We would welcome your view on whether the three-arm design above is the comparison you had in mind.

Dear Reviewer,

Thank you again for your great work on reviewing this paper submission to ICLR 2027.

The authors have now submitted their rebuttal. The open reviewer-author discussion phase will end soon, on November 18 at 11:59 PM AoE.

Please read the authors' responses, determine whether any further clarification is needed, and respond to the rebuttal at your earliest convenience. Please be sure to acknowledge the authors' responses and update your review accordingly.

Best regards, Your AC

Reviewer_Q1wfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper brings the remaining token budget into agent workflows, studying success rates under different budgets and the minimum budget needed to reach a target reliability. The main contributions are analyzing reasoning, verification, and action under a single resource constraint, and using public trajectories to show how system rankings change with budget.

Critical strengths
  1. Evaluating total cost and success on complete tasks helps identify cases where reasoning consumes too much budget for later actions to finish.
  2. The fixed-cost examples clearly show the role of budget allocation, and the cost analysis of public trajectories offers a useful complement to single success-rate evaluations.
Critical weaknesses
  1. The general reliability result conflicts with the model definition. Under the stochastic cost model the paper allows, a larger budget can enable failure branches that were previously excluded, so the success rate can decrease. The claim that success rises monotonically with budget and never exceeds the unconstrained success rate therefore does not hold under the current assumptions.
  2. The link between theory and experiments is not established. The replay truncates logged trajectories once their reconstructed cost exceeds the budget, which corresponds to routing overruns to exhaustion, whereas the theory’s default semantics conditions costs on affordability and can change the distribution of outcomes. The empirical curves and the theorems therefore rest on different budget semantics. The authors acknowledge that the replay imposes budgets on policies that were not budget-aware, and the reported 88% saving comes from choosing among fixed configurations, so the deployment benefit of budget-aware allocation remains unvalidated.
Questions for authors
  1. What additional assumptions or changes to budget handling are needed for the reliability result to hold, and which downstream results would need to be revised?
  2. How is the cost of escalating to the next stage determined before it is called? Do the reported gains still hold with a deployable cost predictor or hard budget truncation?
4 comments
AuthorsOpenReview ↗

Response to Q1wf (1/2): Theorem 2 — you are right; counterexample, corrected Theorem 2′ with proof, and a downstream audit

Thank you for a precise review and for identifying this error. On W1 you are correct.

W1/Q1: why the statement fails. §2 (l.147–156) splits a stochastic call into cost branches of rate λipi(k)\lambda_i p_i(k), and Eq. (1) disables a branch with k>bk>b. Raising BB therefore adds a branch back to the race. (C1) does not prevent this: the rates stay constant, but the set of enabled competitors changes.

  • Counterexample. One call with two branches of rate 1/2: cost 1 → Σ\Sigma, cost 2 → FF. Then σ1=1\sigma_1=1, while σB=12=σˉ\sigma_B=\tfrac12=\bar\sigma for B≥2B\ge2. (C1)–(C3) hold, yet success falls as the budget grows and exceeds the "ceiling" at B=1B=1.
  • The same effect in our own E5. With the paper's model_exact.py, the ±6 split gives σ17=0.992\sigma_{17}=0.992 but σ18=0.496\sigma_{18}=0.496 (0.981 and 0.496 at the paper's deadline D=25D=25): at b=16b=16 the cost-16 branch re-enters the race and, half the time, leaves nothing to verify with.
  • Where the proof breaks. App. J proves path inclusion. But a path's probability is ∏iλti/Λ(xi)\prod_i\lambda_{t_i}/\Lambda(x_i), and the total enabled rate Λ\Lambda is nondecreasing in bb, so path inclusion does not give probability inclusion.

What is needed (your Q1). Either of two conditions:

  • (S) overrun-to-exhaustion: a chosen call draws its cost unconditionally, and a draw above bb ends in E\mathcal E. §2 already lists this as the alternative convention (l.153–155).
  • (C4): transitions that can race at a marking all have the same cost. This holds when each call is charged an amount known when it is issued (assembled input plus output cap), and output-size variability enters as outcomes paid for by later calls.

Theorem 2′. For a budget-blind π\pi under (C1), (C3) and [(S) or (C4)]: σBπ(D)=PπuncτΣ≤D, ZΣ≤B,\sigma^\pi_B(D)=\mathbb P^{\rm unc}_\pi\\{\tau_\Sigma\le D,\ Z_\Sigma\le B\\}, where ZΣZ_\Sigma is the cumulative cost at success. Proof: couple with one unconstrained run. Under either condition the constrained run coincides with it until the first step that would push spend above BB; spend is nondecreasing, so success at BB ⇔ ZΣ≤BZ_\Sigma\le B. Monotonicity, σB≤σˉ\sigma_B\le\bar\sigma and σB↑σˉ\sigma_B\uparrow\bar\sigma follow. We add a lemma that π⋆\pi^\star is also monotone under (S): at B′>BB'>B a policy can mimic the BB-optimal one shifted by B′−BB'-B. Budget-dependent heuristics need not be monotone; E12 shows one that is not (Table M9, 0.500 → 0.488).

Downstream audit (your Q1).

  • Unchanged: Cor. 1 (unconstrained chain); Thm 1 (reachability); Thm 4 (acyclicity, either semantics); all §5 numbers (Table L3, Fig. L2, ceilings 0.854/0.957/0.992). Costs there are deterministic and (C4) holds, so the gate and (S) give identical curves; Tables L3 and L4 agree to 10−1510^{-15}.
  • Re-justified: Thm 3's monotonicity hypothesis now follows from Thm 2′; replay curves satisfy it by construction. Thm 5's capacity inequality needs only pointwise dominance; App. J wrongly invoked Thm 2 for it.
  • Recomputed: E5 (App. L), B=20B=20, D=25D=25:
E5 spreadgate (paper)(S)
deterministic0.9800.980
±20.9800.980
±40.9860.983
±60.4960.493

Under (S) the ±6 curve is monotone (0.490 for B∈[10,14]B\in[10,14], 0.493 for [15,21][15,21], 0.983 at 22, rising to 0.992). The conclusion stands.

  • Covered only under (S): the streaming variant (App. K) races a cost-1 against a cost-0 transition, so (C4) fails there; it reports no numbers.
  • Rewritten: under (S) a call of unknown cost is attempted and an overrun ends the mission. The abstract and contribution (i), which describe unaffordable calls as never attempted, and §2 change accordingly; the abstract (l.023), contribution (iii) (l.070) and App. F gain the qualifier "budget-blind, under (S)".

We also correct the exhaustion set flagged by 6FPy: as typeset it is empty, and the fix uses the workflow-enabled set, as the prose of §2 intends.

AuthorsOpenReview ↗

Response to Q1wf (2/2): replay and theory now share one semantics; E12 used a look-ahead — without a fallback the gain is 0.000; allocation results scoped as model-based

W2: replay vs. theory semantics. You are right; after the fix they coincide.

  • The replay cuts a run off where its bill first exceeds BB (l.361–364): (S) applied to a budget-blind policy.
  • Prop. 1 (l.182–188) already defines σ(B)=P(Z≤B)\sigma(B)=\mathbb P(Z\le B), the population quantity in Thm 2′.
  • So each replay curve is the empirical CDF of exactly the object Thm 2′ and Thm 3 describe, and Prop. 1's band and the McNemar tests are inference on it.

We will make (S) the default for any cost not known before a call, keep the gate for known costs (where the two coincide under (C4)), and add a "semantics" box to §2. This is a change in how the paper describes its semantics, not only in Thm 2's hypotheses (see Part 1).

W2: the deployment benefit of budget-aware allocation is unvalidated. Agreed. The 88% (Table M7) comes from choosing among fixed configurations, as its caption says; held out, it is 90–91% at targets 0.10–0.20 but fragile at 0.30 (our reply to E3Ef). We have not evaluated agents that are told their budget. We therefore present §5's allocation results as model-based and state this as the main limitation.

Q2: how is the escalation cost known before the call? It is not. You correctly identified a look-ahead. The trigger tests c1+c2≤Bc_1+c_2\le B with stage 2's realized cost c2c_2. Without a fallback, or with a cost predictor, the gain is 0.000. The +0.077 requires keeping stage 1's answer when stage 2 cannot finish, which in AppWorld means restoring stage 1's environment state. The reported column equals, task by task, that predictor-free rule (hard cap B−c1B-c_1, keep stage 1 if cut off), because a budget-blind stage 2 finishes under the cap exactly when c2≤B−c1c_2\le B-c_1. Gain is the maximum over nine budgets of the gain over the better fixed configuration:

Escalation ruleNeeds c2c_2 in advance?test_normaltest_challenge
As reported (realized c2c_2)yes+0.077 [0.036, 0.119]+0.031 [0.007, 0.055]
Hard cap B−c1B-c_1, keep stage 1 if cut offnoidentical (0 of 1,512 cells differ)identical (0 of 3,753)
Hard cap, cut-off stage 2 counts as failureno0.0000.000
Cross-fitted quantile c^2\hat c_2, no fallbackno0.0000.000
Cross-fitted c^2\hat c_2, with fallbackno≤ 0.018≤ 0.024
Confidence trigger (Table M9)no0.0000.007

The fallback rule spends more (79k vs 34k tokens per task at 100k), always within BB.

The pair (FullCode/GPT-4-turbo → ReAct/GPT-4o) was selected by a rule in our analysis code (cheapest median spend first, highest ceiling second), but we cannot document that the rule predates the pair search, and it picks the best of 182 pairs on test_normal. We therefore treat +0.077 as in-sample and report test_challenge (+0.031, rank 11 of 182) as the out-of-sample figure. We drop the caption's "not a search artifact" and withdraw §6's sentence that "the signal nobody consults is the one with predictive value".

In the model, §5 costs are deterministic, so π⋆\pi^\star knows each tier's price (the assumption of l.484).

Presentation. We add a notation and semantics box and separate controlled transitions (router) from outcome branches (race) in A(M,b)A(M,b) (l.133–137).

We would be grateful to know whether Theorem 2′ and the aligned semantics resolve your soundness concern.

Dear Reviewer,

Thank you again for your great work on reviewing this paper submission to ICLR 2027.

The authors have now submitted their rebuttal. The open reviewer-author discussion phase will end soon, on November 18 at 11:59 PM AoE.

Please read the authors' responses, determine whether any further clarification is needed, and respond to the rebuttal at your earliest convenience. Please be sure to acknowledge the authors' responses and update your review accordingly.

Best regards, Your AC

Thank you for your candid and detailed response. I appreciate the theoretical fixes and your transparent clarifications regarding the experiments. However, given the substantial revisions needed for the core claims and the remaining gaps in practical validation, I think the paper would benefit from another round of review. I will maintain my current rating.

Reviewer_6FPyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to evaluate and allocate token budgets for agentic systems. The authors argue that traditional benchmarks mainly focus on task success rates but do not sufficiently consider whether agents can complete their tasks under limited token budgets.

To address this problem, the authors introduce a budget-augmented stochastic Petri net to model the agent's workflow and remaining token budget. They also propose capacity-related metrics to measure task success under different budgets and distinguish budget exhaustion from other failures.

The paper provides several theoretical results about reasoning costs, reliability limits, capacity curve crossings, and optimal budget-aware allocation. The authors also analyze 8,190 published agent trajectories from AppWorld to evaluate how token budgets affect agent performance and benchmark rankings.

I think considering token budgets when evaluating agentic systems is meaningful and practical. However, I have some concerns about the theoretical assumptions, the practical validation, and the novelty of the proposed approach.

Critical strengths
  1. This work studies a meaningful and practical problem. I think evaluating agents only by task success rates is not sufficient. Considering limited token budgets can help us better understand the actual performance and cost of agentic systems. The idea of analyzing resource allocation at the mission level is useful, especially for agents that need multiple reasoning steps and tool calls.

  2. The authors provide detailed theoretical analysis and experimental results. They analyze 8,190 published agent trajectories and report how agent performance rankings change under different token budgets. The paper also provides several capacity-related metrics and statistical analyses. I think these results provide useful information about the limitations of traditional agent benchmarks and help us better understand the relationship between token budgets and task success.

Critical weaknesses
  1. I think one important problem is the gap between the theoretical framework and the experimental validation. The authors propose an optimal budget-aware allocation policy, but the main empirical experiments are based on previously recorded trajectories from fixed agent configurations.

I understand that these experiments can show how token budgets affect benchmark rankings. However, they do not directly demonstrate whether the proposed optimal allocation policy can improve the performance of real agents. I am not convinced that the current experimental results are sufficient to support the practical effectiveness of the proposed adaptive allocation method.

  1. The paper provides several mathematical results, but I have concerns about some of their definitions and assumptions. For example, in Section 2, the definition of budget exhaustion seems inconsistent with the definition of enabled transitions. I also have questions about the monotonicity result in Theorem 2. When token consumption is stochastic, increasing the budget may enable additional costly transitions and change the probabilities of different outcomes.

I think these issues are important because the theoretical results are a major part of the paper's contributions. The authors should clarify the assumptions and explain whether these results hold under the full model described in the paper.

  1. I think the idea of considering token budgets in agent evaluation is meaningful. However, previous studies have already considered the relationship between task success and computational cost, as well as budget-aware model selection and resource allocation.

The authors introduce capacity curves and a mathematical framework to analyze these problems. However, I am not convinced that the paper sufficiently explains what new benefits this approach provides compared with existing methods. I think the authors should better clarify the novelty and significance of their contributions.

  1. Another concern is that model capabilities, token costs, and agent execution policies may change over time. For example, a cheaper model may perform better than a more expensive one. Model upgrades and policy improvements may also change the relationship between token consumption and task success.

Although the proposed framework can be updated with new parameters, I am not convinced that the paper sufficiently demonstrates how practical this process would be in real agentic systems. The capacity curves and optimal allocation policies may need to be recalculated when these conditions change, which could limit their practical usefulness.

Questions for authors

Q1: How does the proposed framework improve budget allocation in practical agentic systems?

I understand that the paper provides theoretical results about optimal budget-aware allocation. However, the main empirical experiments analyze historical trajectories from fixed agent configurations.

Could the authors explain how these results support the practical effectiveness of the proposed adaptive policy? What evidence shows that it can improve task success under limited token budgets compared with simpler budget-aware methods?

Q2: Could the authors clarify the mathematical definitions and assumptions?

In Section 2, the definition of budget exhaustion seems inconsistent with the definition of enabled transitions. Also, I am not sure whether the monotonicity result in Theorem 2 always holds when additional stochastic cost branches become affordable as the budget increases.

Could the authors clarify these definitions and explain the conditions under which the theoretical results hold?

Q3: What are the main contributions compared with existing budget-aware agent research?

Previous studies have already considered cost-aware evaluation and budget-aware resource allocation for agentic systems. Could the authors explain more clearly what new insights or practical benefits the proposed capacity curves and mathematical framework provide compared with these existing approaches?

Q4: How does the proposed method handle changes in model capabilities, costs, and agent policies?

A cheaper model may perform better than a more expensive model, and agent performance may change after model or policy upgrades. Could the authors explain how these changes would affect the proposed capacity curves and optimal allocation policies? How practical is it to estimate and update the required parameters in real systems?

5 comments
AuthorsOpenReview ↗

Response to 6FPy (1/3): both definitional points are correct — corrected exhaustion set and Theorem 2′; what the paper shows about real agents

Thank you for the careful review. Your two definitional points are both correct, and we fix both.

W2/Q2(a): budget exhaustion vs. enabled transitions. The inconsistency is real. Since ct∈Nc_t\in\mathbb N, TEn(M,0)T_{\rm En}(M,0) is the set of workflow-enabled zero-cost transitions, which is contained in TEn(M,b)T_{\rm En}(M,b) for every bb. As typeset, E\mathcal E (l.140–142) is therefore empty, and genuine exhaustion falls under "deadlock". What we meant is E=(M,b)∉Σ∪F: Twf(M)≠∅, TEn(M,b)=∅,Twf(M)=t:M≥Pre(:,t),\mathcal E=\\{(M,b)\notin\Sigma\cup F:\ T_{\rm wf}(M)\neq\emptyset,\ T_{\rm En}(M,b)=\emptyset\\},\qquad T_{\rm wf}(M)=\\{t: M\ge \mathrm{Pre}(:,t)\\}, with deadlock iff Twf(M)=∅T_{\rm wf}(M)=\emptyset. This matches the prose of §2, App. B and the glossary ("the workflow has moves and the budget affords none"), and no reported number changes. We also define E\mathcal E relative to the policy's chosen transition and add an overrun sink under (S).

W2/Q2(b): Theorem 2 under stochastic costs. You are right. A larger budget can re-enable costly branches and reweight outcomes; the general response gives a one-call counterexample, and our reply to Q1wf gives the full argument. The fix: for any budget-blind policy, under overrun-to-exhaustion (S), or under Eq. (1) when racing transitions share a cost (C4), σBπ(D)=PπuncτΣ≤D, ZΣ≤B,\sigma^\pi_B(D)=\mathbb P^{\rm unc}_\pi\\{\tau_\Sigma\le D,\ Z_\Sigma\le B\\}, where ZΣZ_\Sigma is the cumulative cost at success; monotonicity and the ceiling follow at once.

On "whether these results hold under the full model":

  • Unaffected: Thms 1 and 4, Cor. 1, and all §5 numbers (deterministic costs; (C4) holds).
  • Re-justified: Thm 3's monotonicity follows from Thm 2′ and holds by construction for replay curves; Thm 5 needs only pointwise dominance, not Thm 2.
  • Recomputed: E5 under (S) gives 0.980, 0.980, 0.983 and 0.493 for its four spreads (gate: 0.980, 0.980, 0.986, 0.496); the conclusion stands.
  • Covered only under (S): the streaming variant (App. K), which reports no numbers.

In the final version, §2 will contain a box listing each result's assumptions.

W1/Q1: does the framework improve real agents, versus simpler budget-aware methods? The paper does not show this, and we say so. §5 is a normative model: it says what an optimal budget-aware policy can gain and where. There, π⋆\pi^\star ties the best fixed level at the 0.90 target and gains 0.042 at B=14B=14 (§5, l.310–315; Table L3), so any gain is concentrated near the onset. §6 tests only claims about fixed, budget-blind configurations (l.326–328, 446–447). The one budget-aware rule we evaluate on real runs (E12) selects between two configurations, and its gain comes from keeping the first answer when the second cannot finish (our reply to Q1wf). The simple budget-aware baseline you ask for, telling the agent its remaining budget, is Budget Tracker (Liu et al., 2025); we will cite it and state the absence of a live comparison as the main limitation. If we can complete one before the discussion closes, we will post it here.

AuthorsOpenReview ↗

Response to 6FPy (2/3): what capacity curves add over cost-aware evaluation, routing, token-budget reasoning and budget-aware agents

W3/Q3: what is new? We agree that none of the machinery is new, and §7 (l.476–480) says so. Thm 3 is elementary. Its use is that the quantity deciding whether a ranking survives a budget, the onset, can be read from logs. The question we study is whether a multi-step mission finishes under a stated token cap, and which configuration should get the cap. Answering it needs three things:

  • (a) success as a function of the cap, including where success starts (the onset);
  • (b) coupling across the steps of one mission, because early spending decides whether later steps can run;
  • (c) separating "never finished" from "finished wrong".
Line of work(a)(b)(c)
Cost-aware evaluation: cost–accuracy frontiers (Kapoor et al., 2024), cost-of-pass, HALmean cost and accuracy——
Routers and cascades: FrugalGPT, RouteLLM, Hybrid LLM, AutoMixper query——
Token-budget reasoning: TALE, s1 budget forcing, L1per generation——
Budget-aware agents: Budget Tracker/BATS (Liu et al., 2025)success vs. tool-call budgetadapts within a run—
Capacity curves (ours)σB\sigma_B with onset β\beta (Prop. 1), from existing logsThm 1E\mathcal E vs FF

"—" means outside that line's scope, not a shortcoming. Budget Tracker/BATS is closest: it builds budget-aware agents, whereas we evaluate and rank given configurations under token caps whose cost grows with context. On real data:

  1. (a) Onsets decide rankings. The AppWorld leaderboard has 41 crossing pairs. Its top entry has zero success below 23,126 tokens, while the third returns 0.339 at 10k (paired McNemar p=1.4×10−17p=1.4\times10^{-17}, §6 l.367–374). A frontier point, an average, cannot show this.
  2. (b) Step-local optima can be mission-fatal. Thm 1 shows this happens over a budget interval exactly as wide as the price premium, which per-query routing cannot see.
  3. (c) Non-conclusion is common and hidden. 45.7% of AppWorld's recorded failures produced no answer (Table M8), and at least 1,300 of them (18.8% of all failures) stopped at their configuration's observed cap; a success rate or mean cost counts them as wrong answers.
  4. Cheap to adopt. The capacity triple (β,σˉ,η)(\beta,\bar\sigma,\eta) needs only per-trajectory cost and the termination bit (§6 l.449–456).

We will expand §7 with these lines of work (adding cost-of-pass, HAL, TALE, s1, L1, Hybrid LLM, AutoMix and Budget Tracker/BATS to the existing FrugalGPT, RouteLLM and Kapoor et al.) and state for each how capacity curves differ.

AuthorsOpenReview ↗

Response to 6FPy (3/3): changing models and prices — drift shows in curves, not scores; B* needs a safety margin

W4/Q4: changing models, prices and policies. We agree this matters.

Cheaper models beating expensive ones is the crossing phenomenon itself, and curves can show it where a score cannot. Our data contains model upgrades. For ReAct and Plan+Execute, GPT-4-turbo → GPT-4o raises the ceiling but lowers σB\sigma_B over a budget band (FunctionCalling shows small scattered drops, FullCode none):

ArchitectureCeilingBand where σB\sigma_B dropsLargest dropAt the pre-chosen test budgetB⋆(0.10)B^\star(0.10)
ReAct0.268 → 0.48825k–46k−0.071 at 33k30k: 0.077 → 0.042, McNemar p=0.15p=0.15+30%
Plan+Execute0.327 → 0.44651k–144k−0.089 at 74k100k: 0.167 → 0.113, p=0.064p=0.064+34%

These deficits are not significant at n=168n=168; the ReAct band recurs on test_challenge (26k–58k, p=0.039p=0.039 at 30k). They illustrate what to monitor, not a settled effect.

Re-estimation cost.

  • A curve for a fixed configuration needs per-task cost, success and the termination bit. Harnesses that log provider usage already record these; where they do not, as in AppWorld's published logs (l.661), cost can be reconstructed as in §6.
  • Prop. 1 sizes the suite: a uniform ±0.05 band at α=0.05\alpha=0.05 needs n≈738n\approx738 tasks (±0.105 at our 168). Paired tests detect large differences with fewer tasks, but not small shifts like those above.
  • Recomputing π⋆\pi^\star is one backward pass (Thm 4): at most 488 states and about a second for the running mission (App. L). The bottleneck is estimating (c,p,q)(c,p,q), as App. G says.

Sensitivity (new). We perturbed all ten parameters of the running mission jointly by up to ±20% (2,000 draws):

B=12B=12B=14B=14B=16B=16B=20B=20
Mean regret, nominal π⋆\pi^\star0.0560.0030.2720.000
Mean regret, best fixed level0.0560.0260.4520.007

The nominal π⋆\pi^\star agrees with the true one on a median 91% of budgets and is never worse on average than the best fixed level. At budgets that sit exactly on a cost sum (B=16B=16), parameter error hurts both. B⋆B^\star is fragile for the same reason: provisioning at the nominal B⋆B^\star meets the target in only 18–54% of draws, while planning for the +20% worst case (B⋆B^\star 17–23 instead of 11–16) meets it in all draws. We will recommend that margin in a new section, "Keeping capacity curves current". Continuous monitoring infrastructure is beyond this paper's scope, and we will say so.

We hope this clarifies the contribution. We would welcome your view on whether the corrected definitions and Theorem 2′ answer Q2.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: Theorem 2 corrected (Theorem 2′), semantics aligned, new offline analyses, and what remains open

We thank the reviewers for careful and constructive reviews. We are glad they found task-level budgeting a practically valuable topic (E3Ef), whole-task cost and success a useful complement to success rates (Q1wf), and the problem meaningful and practical (6FPy).

Summary of concerns and what we did

ConcernRaised byWhat we didStatus
Thm 2 fails under stochastic costsQ1wf W1, 6FPy W2Counterexample; corrected Thm 2′ with proof; audit of downstream resultsIn final version
Exhaustion set empty as typeset6FPy W2Corrected definition; no number changesIn final version
Theory and replay use different semanticsQ1wf W2The replay is overrun-to-exhaustion (S), the semantics of Thm 2′; abstract, contribution (i) and §2 revised to matchIn final version
E5 used the gated semanticsQ1wf, 6FPyRecomputed under (S); conclusion unchangedNew analysis
Is the escalation cost known in advance? (E12)Q1wf Q2No: the trigger used the realized cost. Without a fallback, or with a cost predictor, the gain is 0.000New analysis; claim withdrawn
Deployment benefit of budget-aware allocationQ1wf W2, 6FPy W188% re-checked on held-out tasks (holds at targets 0.10–0.20, fragile at 0.30); allocation results labeled model-basedNew analysis
Agents told their remaining budgetE3Ef W1, Q1wf W2, 6FPy W1Not evaluatedLimitation
Single benchmarkE3Ef W2Not addressed by test_challenge, which shares AppWorld's interfaceLimitation
Novelty vs cost-aware evaluation, routing, budget-aware agents6FPy W3Positioning (6FPy 2/3); expanded §7In final version
Model and price changes, re-estimation6FPy W4Drift across model upgrades; ±20% sensitivity of π⋆\pi^\star and B⋆B^\starNew analysis

The central correction. Under §2's default, an unaffordable cost branch leaves the race, so raising BB can re-enable a costly branch and lower success. One call with two branches of rate 1/2 (cost 1 → success, cost 2 → error) gives σ1=1\sigma_1=1 but σB=1/2\sigma_B=1/2 for B≥2B\ge2. App. J proves path inclusion, but a path's probability also depends on the total enabled rate, which grows with bb. The final version states:

Theorem 2′. For any budget-blind policy π\pi (incl. πℓ\pi_\ell and every logged agent), under (C1), (C3) and either (S) overrun-to-exhaustion (cost drawn unconditionally; a draw exceeding bb ends in E\mathcal E) or Eq. (1) with (C4) races only among equal-cost transitions: σBπ(D)=PπuncτΣ≤D, ZΣ≤B\sigma^\pi_B(D)=\mathbb P^{\rm unc}_\pi\\{\tau_\Sigma\le D,\ Z_\Sigma\le B\\}, with ZΣZ_\Sigma the cumulative cost at success. Hence σBπ\sigma^\pi_B is nondecreasing, ≤σˉπ\le\bar\sigma_\pi, and ↑σˉπ\uparrow\bar\sigma_\pi.

The proof is a coupling with the unconstrained run. Cor. 1, Thms 1 and 4, and every §5 number are unaffected (deterministic costs; (C4) holds). Thms 3 and 5 no longer rely on Thm 2 as stated. The replay already implements (S).

What remains open. We have not evaluated agents that are told their remaining budget, and all empirical results come from one benchmark. We state both as limitations. We present §5 as a normative model and label its allocation results as model-based. §6 tests only claims about fixed, budget-blind configurations: rankings, onsets and crossings. If we can complete a budget-informed comparison before the discussion closes, we will post it here.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.