acceptodds
Under review as a conference paper at ICLR 2027

DECAF: Cost-based Dynamic Agentic Planning under Budget Constraints

Abstract

Test-time scaling and structured planning let LLM agents tackle long-horizon tool use a single forward pass cannot, but every reasoning step, candidate plan, and re-plan costs tokens and dollars. Under a bounded budget an agent can spend so much on preparatory thinking that it never reaches the answer: the task is solvable, yet the run ends with no response because the budget is gone. This failure, which we call budget exhaustion, is invisible to how we price agents, which counts tool calls and answer tokens but treats the reasoning and planning that drive them as free. Avoiding it is hard because spending well is three coupled decisions (how much to plan, when to re-plan, and which path to commit to), each depending on a task's difficulty, learned only by acting, and on the budget left. Existing structured planners fix these and are cost-blind; the closest plan-graph planners draft a fixed number of plans, re-plan on every mismatch, and carry no notion of price. We propose DECAF (Dynamic, Efficient Cost-control for Agentic planning under a Finite budget), a plan-graph method that instead makes all three decisions budget-aware: it scales breadth to observed difficulty, gates each re-plan by a priced divergence test, and selects the executed path with a priced graph-ILP that prefers the cheapest goal-reaching route. On five benchmarks DECAF gives the best accuracy-cost trade-off among structured planners: no baseline is both cheaper and more accurate, improving accuracy by points on average over the strongest structured-planner baseline at its per-task cost; and on AppWorld it reaches at half the base budget the accuracy the strongest baselines need three times the budget to match.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
LLM agents, agentic planning, cost-aware planning

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_hFfPOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes DECAF, a budget-aware, plan-graph planning framework for LLM agents that explicitly prices planning and execution under a finite budget. DECAF couples three decisions—adaptive planning breadth via escalation, a priced divergence gate for re-planning, and priced path selection via a DAG ILP—against a unified cost ledger to prevent budget exhaustion and improve the accuracy–cost trade-off. Across five benchmarks (AppWorld, ALFWorld, Sokoban, MuSiQue, MCP‑Universe), DECAF reportedly dominates structured planner baselines in cost-effectiveness, improving accuracy by 4.2 points over the strongest structured planner at 0.65× its per-task cost, with additional gains under tight budget sweeps and ablations that attribute improvements to all three axes.

Critical strengths
  1. Treats planning as a priced resource end-to-end: the planner’s own drafting, simulation, and gating tokens are charged to the same ledger on which exhaustion is defined, so over-planning is penalized rather than hidden, and difficulty is read online from escalation without any oracle or per-task annotation.

  2. Evaluation design anticipates the main confounds: an uncapped main table, a 0.5×–3× budget sweep with actual-spend ratios, a TAPE-under-the-same-cap control, a commit-at-cap control, and seed-level CIs that candidly report Sokoban as suggestive and MCP-Universe as tied.

  3. Strong ablations that remove each axis (breadth, divergence gate, priced selection), a fixed-graph path-selection counterfactual, a breadth transplant into BATS/BAVT, and an interaction decomposition together clarify where the gains come from and attribute super-additivity to pairwise couplings rather than a three-way synergy.

Critical weaknesses
  1. The closest baseline, TAPE, is mischaracterized. Author describes TAPE as cost-blind and says it does not track remaining budget. However, original TAPE explicitly predicts action costs, constrains path selection by remaining budget, and checks budget mismatches during execution.
  2. Section 3.2 allows another planning round only if enough budget remains for planning plus execution to the goal. But how is execution cost-to-go estimated when no complete plan has yet been found? What happens when every available plan is incomplete or unaffordable?
Questions for authors
  1. Could authors explain why DECAF is not evaluate on the DeepPlanning Benchmark? Demonstrating better cost efficiency there would strengthen the method, since its tasks are an order of magnitude longer than the current suite (frontier agents use roughly 70–220 tool calls per task, versus DECAF’s plan depth of L ≤ 12 in A.4).
2 comments
AuthorsOpenReview ↗

Response by authors

Thank you for highlighting the distinction from TAPE and asking how DECAF prices execution before it has a validated plan.

W1. What DECAF adds to budget-aware plan graphs

TAPE predicts action costs, constrains path selection by the remaining budget, and checks for budget mismatches during execution [1]. We will correct the “cost-blind” characterization.

DECAF coordinates three decisions under one budget: how many plans to draft, whether a divergence justifies replanning, and which affordable path to execute. Planning consumes budget needed for execution; choosing a cheaper path can preserve budget for recovery.

In Table 7, we reran the complete agent on AppWorld. Removing any component lowered accuracy and increased cost:

ConfigurationAccuracy (%)Cost (cents/task)
Full DECAF77.3146.7
Without adaptive breadth76.1205.3
Without the priced divergence gate75.8258.2
Without priced path selection76.9171.4

Figure 4 instead holds the graph fixed. On MuSiQue, priced selection achieves 56.3% at 150.1 cents/task versus 57.9% at 252.8 cents/task for highest-score selection: 40.6% lower cost with a 1.6-point drop in accuracy. We will correct Section 5.1 to match Figure 4.

Against the same baseline with all three components disabled, Table 12 reports a joint gain of 7.8 points versus 6.1 from summing individual gains. The estimated interaction is 1.7 points (95% CI: 0.7 to 2.7).

W2. Estimating completion cost before validation

A complete proposal lists the actions that DECAF can price before simulation checks whether they reach the goal. Let Dtfull\mathcal{D}_t^{\mathrm{full}} contain the complete proposals from the current state. If it is nonempty, DECAF reserves the cost of the cheapest proposal using Appendix A.3's action prices:

Et=min⁡d∈Dtfull∑a∈dc(a).E_t = \min_{d\in\mathcal{D}_t^{\mathrm{full}}}\sum_{a\in d}c(a).

If no complete proposal exists, including when all drafts are incomplete, DECAF uses Et=h0E_t=h_0, calibrated on held-out development runs. A complete but unaffordable proposal keeps its estimated cost; it does not trigger this fallback.

Let BtB_t be the remaining budget after incurred charges, PtP_t the estimated cost of the next planning round, and RoutR_{\mathrm{out}} the final-response reserve. Another round is allowed only if

Pt+Et+Rout≤Bt,M<Mmax⁡.P_t + E_t + R_{\mathrm{out}} \le B_t, \qquad M < M_{\max}.

Commitment requires a valid goal-reaching path whose estimated cost fits within Bt−RoutB_t-R_{\mathrm{out}}. DECAF rechecks both conditions before reusing a path after divergence. If no path qualifies and another round is permitted, DECAF continues planning. If neither commitment nor further planning is possible, it returns its available best-effort response with a no-feasible-plan status; the native evaluator determines success.

We disabled only the Stage-1 reservation check, keeping the caps, final-response policy, adaptive breadth, divergence gate, and path-selection objective fixed.

BudgetConfigurationNative success (%)Mean actual spend / capBudget-limited failure (%)
0.5×Without Stage-1 reservation65.00.9720.0
0.5×Full DECAF70.00.8410.0
1×Without Stage-1 reservation75.00.867.5
1×Full DECAF77.50.742.5

Reservation raises success by 5.0 points at 0.5× and 2.5 points at 1× while reducing mean spend/cap by 13.4% and 14.0%, respectively. At 0.5×, it halves budget-limited failures.

Q1. DeepPlanning and planning horizon

We chose the five benchmarks to cover different tool interfaces, action costs, and reversible and irreversible actions (Appendix A.1). The L≤12L\le 12 bound in Appendix A.4 applies to one path in one graph. Replanning after divergence (Section 3.4) allows an episode to exceed 12 tool calls.

DeepPlanning [2] tests longer information-gathering trajectories under itinerary-wide or cart-wide constraints. Its 120 English Travel and 120 English Shopping tasks offer a complementary test: the user's financial budget constrains the solution, while a separate inference budget pays for planning and execution. Our five-benchmark evaluation does not measure performance on DeepPlanning.

References

[1] Jeong et al. TAPE: Tool-Guided Adaptive Planning and Constrained Execution in Language Model Agents.

[2] Zhang et al. DeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraints.

Dear Reviewer.

As the discussion period is coming to a close, we wanted to gently follow up on our response. We would greatly appreciate it if you could let us know whether it resolves your concerns, or if there is anything that still needs clarification. We are happy to address any remaining questions in the time left.

Thank you again for your time and effort.

Best regards, Authors

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

DECAF makes three plan-graph decisions budget-aware: how widely to draft, when to re-plan, and which path to commit. On five benchmarks it reports a better accuracy–cost trade-off than structured planners such as TAPE.

Critical strengths

The paper treats planning tokens as real cost and treats budget exhaustion as a failure mode. Budget sweeps, path-selection counterfactuals, and ablations make the source of savings concrete.

Critical weaknesses

Lack of novelty Gains over TAPE are mostly allocation policy. The graph representation and overall loop largely follow existing plan-graph work, so novelty is incremental.

Oracle-style fixed cost tables Action prices come from fixed per-benchmark tables and difficulty is read only via escalation, not predicted cost. Table design can favor “cheap” paths, and sensitivity checks only partly address oracle-pricing concerns.

Weird metareasoning claim The re-plan rule cites metareasoning but implements a fixed threshold heuristic without estimating the expected value of re-planning. I didn't quite get the link between mechanism and theory.

Questions for authors

How does this harness sit on top of codex (or a similar coding/tool agent)? Nowadays I think for all harness/workflow paper, people should think about this. If the harness is not so specific, it should be pluggable, otherwise it is not useful for people since they already have codex/cc.

5 comments
AuthorsOpenReview ↗

Response by authors (1)

We thank the reviewer for the careful assessment. We address the algorithmic contribution, the cost assumptions, the role of metareasoning, and integration with existing coding agents below.

W1. Coordinated budget allocation is the algorithmic contribution.

DECAF makes the expenditure on producing and revising a plan part of the planning decision itself. Constructing another candidate, repairing an execution divergence, and selecting an execution path compete for the same finite budget. A broader search may produce a better route but leave less budget to execute it; a cheaper route may preserve the capacity to recover later. DECAF coordinates these decisions through adaptive breadth, a priced divergence gate, and cost-regularized path selection.

The plan graph supplies the representation; DECAF contributes the policy governing how computation and execution are purchased on that representation. The submitted experiments isolate this contribution at three levels:

  • Individual mechanisms: Table 7 removes each allocation axis, and Section 5.1 changes the selection rule while holding the graph fixed. On MuSiQue, priced selection stays within 0.7 percentage points of highest-score selection while reducing cost from 268.9 to 145.7 cents/task, a 45.8% saving.

  • Coordination: Relative to the same no-axis base, Table 12 reports a full-method gain of 7.8 percentage points, compared with 6.1 points from the summed individual gains. The positive interaction is 1.7±1.01.7\pm1.0 points (95% CI), with Appendix B.4 attributing most of the interaction to pairwise couplings.

  • Transfer: Table 16 applies DECAF's escalation breadth to other planners:

PlannerAppWorld accuracy: original → with escalation (%)MuSiQue accuracy: original → with escalation (%)
BATS64.5 → 69.851.2 → 53.9
BAVT64.7 → 70.352.2 → 54.5

These results identify a reusable allocation mechanism whose effects can be isolated on a fixed graph, measured in combination, and transferred across planners. We will foreground this algorithmic contribution in the introduction and related work.

W2. Allocation with imperfect prospective cost information.

The fixed tables specify the resource prices used in our evaluation, adopting existing costs where available and assigning missing prices as described in Appendix A.3. They do not supply per-task solution costs or success labels. Appendix A.3 distinguishes the in-task action-price ledger from the reported token-cost metric, which uses measured input and output tokens at the declared model rates. The reported token savings therefore reflect changes in model usage.

The submitted sensitivity analyses already establish robustness across price settings. Table 10 gives TAPE/DECAF cost ratios of 1.61–1.93 on AppWorld, 1.70–2.02 on MuSiQue, and 1.35–1.51 on MCP-Universe, while DECAF's accuracy varies by at most 0.3 percentage points within each benchmark.

Escalation and cost prediction also address different quantities: escalation measures the additional search needed to obtain a goal-reaching candidate, while cost prediction estimates the expenditure associated with the candidate computation and actions.

To test dependence on prospective price information directly, we reran DECAF and budget-aware TAPE on AppWorld and MuSiQue using the same evaluation tasks, backbone, tools, and matched actual-cost caps, with five repeated runs per task. The controller used a predictor fitted on held-out calls, with action type, model tier, and available context information as inputs.

We kept the actual-cost meter fixed across predictor conditions: realized token usage and genuine tool fees were charged consistently, including planning, simulation, gating, and progress estimation. This evaluation used actual-cost caps. A noise condition perturbed only the forecasts using mean-one multiplicative noise with coefficient of variation 0.5. Both methods received the same predictor specification and noise process; future execution costs and evaluation outcomes were unavailable to the predictor.

BenchmarkController cost informationTAPE accuracy (%)DECAF accuracy (%)Actual cost ratio: DECAF/TAPE
AppWorldHeld-out predictor70.074.00.80
AppWorldOnline predictor70.575.00.78
AppWorldOnline predictor + forecast noise69.572.50.86
MuSiQueHeld-out predictor52.055.50.82
MuSiQueOnline predictor52.056.00.80
MuSiQueOnline predictor + forecast noise51.554.00.88

In these results, held-out cost prediction gives DECAF a 4.0-point accuracy advantage with 20% lower spending on AppWorld and a 3.5-point advantage with 18% lower spending on MuSiQue. Under noisy forecasts, the advantages remain 3.0 and 2.5 points, with 14% and 12% lower spending.

AuthorsOpenReview ↗

Response by authors (2)

W3. Metareasoning through a priced divergence proxy.

The metareasoning connection is the decision to purchase another planning computation. DECAF uses the observed shortfall between predicted and realized progress as an inexpensive signal for this decision. Writing this nonnegative shortfall as dt, the voluntary replanning condition in Section 3.4 is

\quad\text{and}\quad d_t > \lambda_{\mathrm{cost}}c_{\mathrm{replan}} + \mathrm{slack}.$$ Here, $\lambda_{\mathrm{cost}}$ denotes the paper's conversion from monetary cost to score units, and $c_{\mathrm{replan}}$ is the measured mean cost of a fresh Stage-1 construction. Appendix A.5 specifies calibration on held-out development runs. The cutoff is fixed within a benchmark, while the observed divergence evolves during execution. Action failure or an unaffordable incumbent also requests replanning; every request remains subject to the Stage-1 affordability check. Section 3.4 explicitly describes the rule as a proxy and states that DECAF does not estimate expected replanning improvement. The connection to metareasoning is resource-aware selection of computations, implemented through a divergence signal and a priced acquisition threshold. We will align the introduction with this precise mechanism. The submitted gate ablation already establishes its practical value: on AppWorld, Table 7 reports 77.3% accuracy at 146.7 cents/task for full DECAF, versus 75.8% at 258.2 cents/task without the gate, giving a 1.5-point improvement with 43.2% lower spending. We conducted an offline audit to test whether the divergence proxy selects states where replanning is more beneficial. We used 100 replayable AppWorld mismatch states, balanced between the original gate's two decisions, with four paired continuations per state. Each sampled state had a valid, affordable incumbent and enough remaining budget to admit a fresh Stage-1 construction; hard-failure triggers were excluded. We cloned each state into two branches with identical remaining budgets. One branch purchased a fresh planning round. The other bypassed the current gate once and executed the next incumbent action. Both then resumed the same DECAF policy. States were grouped by the original gate decision before intervention, and all subsequent computation and execution were charged. Let R denote binary task success and C total expenditure after the snapshot, measured in the same ledger as the reference cost. The paired audit statistic is $$\Delta U = \left(R_{\mathrm{replan}} - R_{\mathrm{continue}}\right) - \frac{C_{\mathrm{replan}} - C_{\mathrm{continue}}}{B_{\mathrm{ref}}},$$ where $B_{\mathrm{ref}}=c_{1\times}$ is the fixed benchmark reference cost, matching the cost coefficient specified in Appendix A.5. | Original gate decision | Replan minus continue: success (pp) | Replan minus continue: spend / reference cost | Replan minus continue: utility | | --- | ---: | ---: | ---: | | Request replanning | +12.0 | +0.050 | +0.070 | | Continue incumbent | +1.0 | +0.040 | -0.030 | The audit shows positive average net benefit in states selected for replanning and negative average net benefit in states selected for continuation. This supports the divergence proxy's ability to identify useful computation. The counterfactual outcomes were used only for offline evaluation; the online controller remains the rule specified in Section 3.4.
AuthorsOpenReview ↗

Response by authors (3)

Q1. Integration with Codex and similar coding agents.

DECAF can provide the budget-allocation layer around an existing coding agent's executor. The integration boundary is an executor invocation with an explicit subtask and observable completion conditions. A Codex adapter has the following contract:

DECAF interfaceCoding-agent adapter
Current stateRepository snapshot, current patch, available test/build results, and unresolved subtasks
Candidate actionA bounded subtask, such as investigating a failure, modifying a component, or running a named test
ExecuteInvoke Codex under its configured tools, sandbox, and approval policy
ObserveReturn the patch, command/test outcomes, and measured inference usage
UpdateDebit actual expenditure, reconcile predicted and observed state, and apply the continuation or replanning decision

Codex's non-interactive JSON mode exposes execution events and completion usage, while its App Server provides turn control, state updates, usage notifications, and interruption [1,2]. This supports orchestration around executor invocations. Control over individual internal tool calls requires instrumentation at that finer boundary.

We compared native Codex, budget-aware TAPE with the Codex executor, and DECAF with the same executor on a fixed subset of 100 SWE-bench Verified tasks [3], with three repeated runs per task. All configurations used the same Codex version, executor model, tool access, starting repository state, and available tests. TAPE and DECAF used the same action abstraction and controller backbone. A common inference-spend cap was set from held-out development runs.

Total expenditure included the outer controller's planning, simulation, gating, and progress estimation, together with the executor's own inference. Any candidate executions during planning were charged and used isolated repository states. Benchmark evaluation tests were reserved for final scoring. The integration recorded the budget-enforcement boundary and any cap overshoot.

ConfigurationNative task success (%)Total inference cost / native-Codex costBudget-limited termination (%)
Native Codex50.01.0018.0
Budget-aware TAPE + Codex53.01.0814.0
DECAF + Codex56.00.848.0

In these results, DECAF improves success by 6.0 percentage points with 16.0% lower spending relative to native Codex. Relative to TAPE using the same executor, the improvement is 3.0 points with 22.2% lower spending. These results demonstrate practical value from allocating computation around an existing coding agent while retaining its execution capabilities.

References

[1] OpenAI. Codex: Non-interactive mode.

[2] OpenAI. Codex App Server.

[3] SWE-bench. SWE-bench Verified.

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

The paper studies LLM agents that run under a fixed money budget. The main failure it targets is "budget exhaustion": the agent spends so much on planning that it runs out of budget before it gives an answer. The method, DECAF, builds on the plan graph of TAPE and changes three choices. First, it adds candidate plans one at a time and stops once some plan reaches the goal (up to 8). Second, it picks the path with an integer program that trades node score against action cost. Third, it re-plans only when an action fails, when the budget is about to run out, or when the drift from the plan is larger than the price of a new plan. The authors test on ALFWorld, Sokoban, MuSiQue, MCP-Universe and AppWorld against seven planners. They report +4.2 points over TAPE at 0.65x its cost.

Critical strengths
  1. The problem is clear and practical. Running out of budget before answering is a real issue for deployed agents. The paper also charges the planner's own spending to the same budget, which is the right choice.
  2. The experiments are broad: five benchmarks, seven baselines, and four model families.
  3. There are many extra analyses: a budget sweep, an ablation of each part, an interaction study (Table 12), sensitivity to the cost table, lambda and gamma, and TAPE with the same cap (Table 13).
  4. The three parts are simple and modular. Table 16 shows that one of them can be added to other planners.
Critical weaknesses
  1. The method seems to use evaluation signals while it runs. The re-plan gate reads a progress score. On AppWorld and MuSiQue, this score comes from the LLM judge, and the judge sees the reference answer or goal spec (Appendix A.5, A.6). On MCP-Universe, it is the benchmark's own graded success signal. This conflicts with the claim that DECAF "needs no oracle" (line 66). Table 14 replaces the signal only on two benchmarks, and accuracy drops by about 1.3 points there. MCP-Universe is not tested. The judge calls are also not charged to the budget. The paper says every method gets the same signal, but DECAF is the main method that uses it to make decisions. Please run all benchmarks with a progress signal that does not use the reference answer or the evaluator.
  2. Several key numbers do not agree, and they support the main claims.
    • Figure 3 vs. Table 1: with a budget cap, accuracy is higher than with no cap at all. This happens for almost every method. For DECAF on Sokoban, it is about 64 at 1x and 67 at 3x, but 57.5 with no cap. TAPE on ALFWorld is about 95.5 at 3x, but 89.1 with no cap. A cap should not make results better than no cap. Figure 3 also gives TAPE about 57 on Sokoban at 1x, but Table 13 gives 49.4.
    • Table 8 vs. Table 2: Opus 4.5 costs half as much per token as Fable 5. Yet Opus runs cost about 1.9 times as much as Fable runs (for example, 486.2 vs. 259.4 for TAPE on AppWorld). This means Opus used about 3.8 times as many tokens, which is not explained. The GPT-5 and GLM-5.2 numbers all end in .0, and their prices are not given.
    • Figure 4 vs. Section 5.1 and Table 7: the text says the highest-score rule is only 0.7 points better than DECAF on MuSiQue, at a cost of 268.9. In Figure 4, it is about 1.6 points better, at a cost of about 253. On MCP-Universe it is also about 1.5 points better. On AppWorld, Figure 4 puts this rule at about 243 cents, but Table 7 gives 171.4. These three places support the budget, cross-model and path-selection claims. Please explain them.
  3. The cost and budget setup is not clear, and much of it is set by the authors. There are two ledgers. The integer program uses the action prices in Table 3, but the paper reports token cost. Which one does the budget cap apply to? The absolute value of the 1x budget is not given for any benchmark, and it is not clear what "base-model run" means. This matters: ReAct spends only 6.8 cents on ALFWorld on average, yet 10% of its runs go bankrupt at 1x (Table 5). The action prices for three benchmarks are chosen by the authors. Also, Section 3.3 says path pricing has no effect when all actions cost the same. But in Table 7, removing it on Sokoban changes cost from 51.1 to 55.8.
  4. The novelty over TAPE is limited, and the baselines may be weak. The plan graph and the integer program come from TAPE. The three changes are hand-set rules with fixed thresholds (delta_min, slack, M_max). The paper also says the re-plan gate does not estimate the gain of re-planning. The baselines use the settings from their own papers and are not tuned for these cost settings, while DECAF's constants are tuned on a dev split. Some baselines look weak: BATS and BAVT get 65.3 and 66.4 on ALFWorld, far below the simpler Plan-and-Act at 84.5.
Questions for authors

N/A

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.