- 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
-
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.
-
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.
-
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
- 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.
- 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
- 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
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
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:
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 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=mind∈Dtfull∑a∈dc(a).
If no complete proposal exists, including when all drafts are incomplete, DECAF uses Et=h0, calibrated on held-out development runs. A complete but unaffordable proposal keeps its estimated cost; it does not trigger this fallback.
Let Bt be the remaining budget after incurred charges, Pt the estimated cost of the next planning round, and Rout the final-response reserve. Another round is allowed only if
Pt+Et+Rout≤Bt,M<Mmax.
Commitment requires a valid goal-reaching path whose estimated cost fits within Bt−Rout. 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.
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≤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.