Capability-Grounded Agentic Planning

Shikha Shrestha; William Yeoh; Ning Zhang; Yevgeniy Vorobeychik

cs.AIOct 29, 2026

Capability-Grounded Agentic Planning

Authors: Shikha Shrestha, William Yeoh, Ning Zhang, Yevgeniy Vorobeychik

Organizations: Washington University in St. Louis

Abstract

LLM agents serve natural-language requests through tools, data sources, and other agents, and even simple requests often need several interdependent calls. Typically, the LLM picks these calls by trial and error, with no guarantee of an executable plan. We present Capability-Grounded Agentic Planning (CGAP), which instead reasons about what a request requires and what tools provide. CGAP compiles the tool catalog deterministically into a PDDL model, uses an LLM to turn the request into goals, and solves the model with a classical planner. Since tool outputs are unknown in advance, the model is abstract, tracking which inputs are available, not their values. During execution, an LLM adds entity-specific calls that abstract plans omit, and deterministic checks reject any that break the plan. Every argument is drawn from a cited source, such as a conversation span or an earlier tool response, and each requested result counts as delivered only after an LLM verifier checks it against the request. With three LLMs on ToolSandbox, ComplexFuncBench, BFCL multi-turn, and $τ^2$ -bench retail, CGAP outperforms a standard tool-calling agent by up to 28.9 points.

Figures & tables

Figure 1: One user turn of CGAP. LLM components (top: the request parser

M_{\theta}

, the execution LLM

E_{\phi}

, and the verifier) interpret the request, choose each call, and judge its result. Deterministic components (bottom) build the planning model, search for a shortest plan, check every proposed call before it runs, and record which results are complete. Grey text shows each component’s work on the weather request. The planner ablations (§ 3.3 ) replace only the planner, with an LLM or a dependency-graph planner.

Figure 2: Why the abstract plan is shorter than its execution. (a) Search plans one city lookup and one date resolution, which make every input of the three requested forecasts (shaded) available. (b) During execution,

E_{\phi}

adds a lookup for Nice and a date resolution for Tuesday (dashed) through validated refinements, so five planned actions become seven calls.

			ComplexFuncBench
Model	Method	ToolSandbox	Success	Call Acc.	BFCL-MT	$\tau^{2}$ -Retail
gpt-oss-20b	Plain agent	52.3 [47.2, 57.5]	47.6 [41.6, 53.6]	66.0 [61.6, 70.5]	34.0 [27.5, 40.5]	47.4 [38.6, 56.1]
	+ dependency notes	58.4 [53.2, 63.3]	–	–	–	–
	compute-matched	57.1 [52.0, 62.2]	50.8 [45.2, 56.4]	–	37.0 [30.5, 43.5]	51.8 † [43.0, 60.5]
	ReWOO	54.1 [47.5, 60.6]	46.4 [41.2, 51.6]	–	33.5 [27.0, 40.0]	44.7 [36.0, 53.5]
	LLMCompiler	54.2 [47.7, 60.6]	40.4 [34.4, 46.4]	50.7 [46.2, 55.2]	21.0 [15.5, 27.0]	30.7 [22.8, 39.5]

Table 1: Main results (%). ToolSandbox reports the average milestone similarity score, ComplexFuncBench the success rate and call accuracy, BFCL-MT the accuracy on BFCL multi-turn, and

\tau^{2}

-Retail the success rate on all 114

\tau^{2}

-bench retail tasks, over three runs per task (§ 3.1 ). Brackets give 95% bootstrap intervals over tasks. The four additional baselines run with gpt-oss-20b only, the dependency-notes agent on ToolSandbox only, and three lack call accuracy (–); † without a token budget (Appendix E.3 ). Bold: best per model; Table 4 gives paired differences.

Variant	Avg.	State	CFB	BFCL-MT	$\tau^{2}$ -Retail
	ToolSandbox
CGAP (search)	81.2	98.4	58.0	52.0	61.4
LLM planning	$-$ 16.8 [ $-$ 20.5, $-$ 13.2]	$-$ 27.7 [ $-$ 33.0, $-$ 22.4]	$-$ 4.4 [ $-$ 8.0, $-$ 0.8]	$-$ 10.0 [ $-$ 16.0, $-$ 4.0]	$-$ 7.9 [ $-$ 14.9, $-$ 0.9]
graph planning	$-$ 3.1 [ $-$ 6.0, +0.4]	$-$ 8.9 [ $-$ 14.5, $-$ 3.6]	$-$ 0.4 [ $-$ 2.8, +2.0]	+0.5 [ $-$ 2.5, +3.5]	$-$ 1.8 [ $-$ 7.0, +3.5]
$-$ provenance	$-$ 5.4 [ $-$ 8.3, $-$ 2.4]	$-$ 4.3 [ $-$ 8.1, $-$ 0.8]	$-$ 3.6 [ $-$ 7.2, $-$ 0.4]	$-$ 5.0 [ $-$ 9.5, $-$ 1.0]	$-$ 5.3 [ $-$ 11.4, +0.9]
$-$ verifier	$-$ 2.7 [ $-$ 4.9, $-$ 0.6]	$-$ 1.8 [ $-$ 4.4, +0.6]	$-$ 1.6 [ $-$ 4.0, +0.4]	$-$ 2.0 [ $-$ 5.0, +0.5]	$-$ 2.6 [ $-$ 7.9, +2.6]

Table 2: Ablations with gpt-oss-20b : changes from CGAP with search (95% paired bootstrap intervals). The first two rows replace the planner; the last two remove a runtime component.

Figure 3: Deterministic planning versus LLM planning. Gain of CGAP (with search) over its LLM-planning ablation for each LLM and metric, with 95% paired bootstrap intervals (Table 4 ).

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

	Input $q_{t}$ , $H_{t}$ , $\mathcal{C}$ , previous operations $\mathcal{O}_{t-1}$ and their completion records, budgets $B,N,L$
1	Compile base actions (Equation 1 ), run request parsing (Equation 3 ), and inherit completion records of unchanged operations
2	Construct $\mathcal{P}_{t,0}$ by Equation 4 ; set $k\leftarrow 0$ and remaining plan $\bar{\pi}\leftarrow\bot$
3	for at most $N$ execution decisions do
4	if $G_{t}\subseteq I_{t,k}$ then return completed goals $G_{t}$ and unresolved requests $U_{t}$
5	if $\bar{\pi}=\bot$ or $\bar{\pi}$ is invalid from $I_{t,k}$ then $\bar{\pi}\leftarrow\operatorname{Search}(\mathcal{P}_{t,k},B)$
6	if search returns NoPlan or Limit then return incomplete with that status

Appendix

Algorithm 1 Planning and execution within turn

t

. The loop counts execution decisions;

k

counts invocations.

Symbol	Meaning
$q_{t}$ , $H_{t}$ , $H_{t,k}$	instruction of turn $t$ ; history before turn $t$ ; history after $k$ invocations of turn $t$
$\mathcal{C}$ , $c(\mathbf{v})$	capability catalog; invocation of $c$ with arguments $\mathbf{v}$
$\mathcal{X}$ , $\mathcal{F}$	fields (normalized input/output names); facts
$\operatorname{Available}(p)$ , $\operatorname{Success}(i)$	a value for field $p$ has a source; operation $i$ is complete
$\In(c)$ , $\Out(c)$	required input fields and candidate output fields of $c$
$K_{c}^{\mathrm{pre}},K_{c}^{+},K_{c}^{-}$	application-supplied domain preconditions, add effects, delete effects

Appendix

Table 3: Notation.

	Input Planning problem $\mathcal{P}_{t,k}$ , expansion budget $B$
	Output Action sequence $\bar{\pi}_{t,k}$ , NoPlan , or Limit
1	Initialize FIFO queue $\mathit{Open}\leftarrow[I_{t,k}]$ , visited set $\mathit{Seen}\leftarrow\{I_{t,k}\}$ , and expansion count $b\leftarrow 0$
2	while $\mathit{Open}\neq\varnothing$ do
3	Remove the first state $s$ from $\mathit{Open}$
4	if $G_{t}\subseteq s$ then return $\operatorname{Reconstruct}(s)$ using predecessor pointers
5	if $b=B$ then return Limit

Appendix

Algorithm 2 Forward state-space search

Model	CGAP	ToolSandbox	CFB success	CFB call acc.	BFCL-MT	$\tau^{2}$ -Retail
gpt-oss-20b	vs. plain agent	+28.9 [24.5, 33.4]	+10.4 [4.8, 16.0]	+8.9 [6.1, 11.8]	+18.0 [10.0, 26.0]	+14.0 [5.3, 22.8]
gpt-oss-20b	vs. LLM planning	+16.8 [13.2, 20.5]	+4.4 [0.8, 8.0]	+4.5 [2.2, 6.9]	+10.0 [4.0, 16.0]	+7.9 [0.9, 14.9]
Qwen3-32B	vs. plain agent	+24.5 [20.2, 28.8]	+10.8 [5.2, 16.4]	+9.1 [6.4, 11.9]	+14.0 [7.0, 21.0]	+11.4 [3.5, 20.2]
Qwen3-32B	vs. LLM planning	+11.8 [8.5, 15.2]	+5.6 [1.6, 9.6]	+5.3 [3.0, 7.7]	+7.0 [2.0, 12.0]	+5.3 [0.9, 10.5]
GPT-5 mini	vs. plain agent	+13.9 [10.2, 17.5]	+5.2 [1.6, 9.2]	+5.1 [3.2, 7.0]	+6.0 [1.5, 11.0]	+8.8 [0.9, 16.7]
GPT-5 mini	vs. LLM planning	+4.8 [2.1, 7.4]	+3.2 [0.0, 6.4]	$-$ 0.1 [ $-$ 1.8, 1.7]	+2.0 [ $-$ 0.5, 5.0]	+3.5 [ $-$ 2.6, 9.6]

Appendix

Table 4: Paired differences between CGAP and the plain agent (§ 3.2 ) and between CGAP and its LLM-planning ablation (§ 3.3 ), with 95% paired bootstrap intervals over tasks. Differences are computed from task-level scores before rounding.

ToolSandbox
Method	Average	State dependency	Canonicalization	Insufficient info.
Plain agent	52.3 [47.2, 57.5]	62.8 [54.0, 71.1]	59.9 [51.7, 68.0]	34.2 [25.0, 43.6]
LLM planning	64.4 [59.6, 69.1]	70.7 [62.5, 78.4]	66.7 [58.7, 74.1]	55.8 [46.7, 64.5]
CGAP (ours)	81.2 [77.4, 84.8]	98.4 [95.1, 99.7]	81.6 [74.6, 87.7]	63.6 [55.7, 71.0]

Appendix

Table 5: Category and domain results with gpt-oss-20b, with 95% bootstrap intervals over tasks. LLM planning is the ablation of Section 3.3 .

		CGAP vs.
Tasks	Model	plain agent	LLM planning
Two or more orders (64)	gpt-oss-20b	+14.1 [1.6, 26.6]	+10.9 [0.0, 21.9]
	Qwen3-32B	+15.6 [4.7, 26.6]	+6.3 [1.6, 12.5]
	GPT-5 mini	+9.4 [1.6, 18.8]	+3.1 [ $-$ 4.7, 12.5]
One or no order (50)	gpt-oss-20b	+14.0 [2.0, 26.0]	+4.0 [ $-$ 4.0, 12.0]
	Qwen3-32B	+6.0 [ $-$ 6.0, 18.0]	+4.0 [ $-$ 4.0, 12.0]

Appendix

Table 6: Paired differences of CGAP on

\tau^{2}

-bench retail, split by whether the benchmark’s reference actions for a task name two or more orders, counting lookups (36 of the 64 tasks write to two or more), with 95% paired bootstrap intervals over the tasks of each part.

Method	Average	State dependency	CFB success	BFCL-MT	$\tau^{2}$ -Retail
	ToolSandbox
Plain agent	52.3 [47.2, 57.5]	62.8 [54.0, 71.1]	47.6 [41.6, 53.6]	34.0 [27.5, 40.5]	47.4 [38.6, 56.1]
+ dependency notes	58.4 [53.2, 63.3]	79.6 [70.6, 88.1]	–	–	–
compute-matched	57.1 [52.0, 62.2]	68.9 [60.6, 77.1]	50.8 [45.2, 56.4]	37.0 [30.5, 43.5]	51.8 † [43.0, 60.5]
ReWOO	54.1 [47.5, 60.6]	65.1 [55.6, 74.6]	46.4 [41.2, 51.6]	33.5 [27.0, 40.0]	44.7 [36.0, 53.5]
LLMCompiler	54.2 [47.7, 60.6]	66.4	40.4 [34.4, 46.4]	21.0 [15.5, 27.0]	30.7 [22.8, 39.5]

Appendix

Table 7: Additional baselines with gpt-oss-20b (Appendix E.3 ), with 95% bootstrap intervals over tasks. These intervals are marginal; Table 8 gives paired differences. The dependency-notes agent runs on ToolSandbox only, and we have no interval for LLMCompiler’s state-dependency score. The plain agent and CGAP rows repeat Table 1 , and the LLM-planning row repeats Table 5 (except

\tau^{2}

-Retail, which that table does not include). † The compute-matched agent had no token budget on

\tau^{2}

-bench retail and used 17% more tokens per task than CGAP (Appendix E.3 ).

CGAP vs.	Average	State dependency	Success	Call acc.	BFCL-MT	$\tau^{2}$ -Retail
	ToolSandbox		ComplexFuncBench
Dependency-notes agent	+22.8 [18.5, 27.0]	+18.8 [12.0, 25.7]	–	–	–	–
Compute-matched agent	+24.1 [19.8, 28.3]	+29.5 [22.7, 36.1]	+7.2 [2.8, 11.6]	–	+15.0 [8.5, 21.5]	+9.6 † [1.8, 17.5]
ReWOO	+27.1 [21.8, 32.3]	+33.3 [25.5, 41.1]	+11.6 [6.4, 16.8]	–	+18.5 [12.0, 25.5]	+16.7 [7.9, 25.4]
LLMCompiler	+27.0 [21.7, 32.2]	–	+17.6 [12.0, 23.2]	+24.2 [20.1, 28.4]	+31.0 [23.5, 38.5]	+30.7 [20.2, 41.2]

Appendix

Table 8: Paired differences between CGAP and the additional gpt-oss-20b baselines of Table 7 , in percentage points, with 95% paired bootstrap intervals over tasks. Dashes mark measures not available for a baseline (Table 1 ) and LLMCompiler’s state-dependency difference, for which we have no paired interval. † The compute-matched agent had no token budget on

\tau^{2}

-bench retail.

Method	ToolSandbox	CFB	BFCL-MT
Plain agent	61.7	104.3	128.6
+ dependency notes	64.9	–	–
compute-matched	92.8	152.3	160.0
ReWOO	53.1	77.2	101.6
LLMCompiler	141.9	159.6	245.6
LLM planning	104.8	145.5	183.2

Appendix

Table 9: Mean tokens per task (thousands) with gpt-oss-20b, averaged over the three runs. LLM planning is the ablation of Section 3.3 . The dependency-notes agent runs on ToolSandbox only. The compute-matched agent’s limits were set on held-out tasks (Appendix E.3 ); on the evaluation tasks it is within 5% of CGAP on every benchmark in this table. On

\tau^{2}

-bench retail, which this table omits, it had no budget and used 17% more tokens per task than CGAP.

Benchmark	Input information	Return information	Additional modeling inputs
ToolSandbox	Tool names, descriptions, and parameter schemas with required and optional arguments	Schemas converted from Python return-type annotations; their detail depends on the annotation	Hand-written field names for tools that return scalars; device-dependency annotations and $\operatorname{CalendarConverted}$ (Appendix A.1 )
ComplexFuncBench	Names, descriptions, and JSON parameter schemas; some descriptions name the endpoint that supplies a parameter	No return schemas; output fields named in descriptions give limited connections, and observed responses supply the values	Producer–consumer connections and output aliases from those endpoint references; deterministic date, time, and string resolvers; no domain annotations
BFCL multi-turn	Function names, descriptions, and parameter schemas	Return or response contracts where supplied, normalized by the adapter; coverage varies	None
$\tau^{2}$ -bench retail	Tool names, descriptions, and parameter schemas; the domain policy	Typed return values of the tool implementations (orders, users, products)	None

Appendix

Table 10: Catalog inputs and additional modeling information for each benchmark.

Classical Planning

See all 22 papers

Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents
Jun 3, 2026Haoyu Sun, Wenxuan Wang, Mingyang Song +5Tool-Augmented Language Model Agents LLM Agent Evaluation
Tongji University · Shanghai AI Laboratory · Harbin Institute of Technology +5
PlanBench-XL: Evaluating Long-Horizon Planning of LLM Tool-Use Agents in Large-Scale Tool Ecosystems
Jun 21, 2026Jiayu Liu, Qihan Lin, Cheng Qian +8Tool Discovery for LLM Agents Long-Horizon Agent Evaluation
University of Illinois Urbana-Champaign
ToolTree: Efficient LLM Agent Tool Planning via Dual-Feedback Monte Carlo Tree Search and Bidirectional Pruning
Mar 13, 2026Shuo Yang, Soyeon Caren Han, Yihao Ding +2Tool-Use Planning Tree Search
School of Computing and Information Systems, The University of Melbourne · School of Physics, Mathematics and Computing, The University of Western Australia

Jun 3, 2026J/K move · Enter open · S save

Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents

Haoyu Sun, Wenxuan Wang, Mingyang Song, Jujie He+4

Tongji University · Shanghai AI Laboratory · Harbin Institute of Technology+5

Tool-Augmented Language Model Agents LLM Agent Evaluation AI Agent Benchmarks LLM Agent Planning LLM Agent Reliability

Open paper AskPDF arXiv

Planning is central to LLM agents: before acting, an agent must decompose goals, select tools, reason over constraints, and decide when a task is infeasible. Yet existing agent evaluations often report only end-to-end success, making it difficult to determine whether failures stem from planning or execution. We introduce Agent Planning Benchmark (APB), a planning-specific diagnostic benchmark with 4,209 multimodal cases across 22 domains and five settings, covering holistic planning, feedback-conditioned step-wise planning, and robustness under extraneous tools, broken tools, and unsolvable tasks. Across 12 MLLMs, APB reveals systematic weaknesses in long-horizon planning, tool-noise robustness, calibrated refusal, and inference-time refinement. We further validate APB on 200 ToolSandbox tasks and 200

τ^2

-bench tasks, where APB-guided refinement consistently improves plan correctness, plan grade, and downstream execution metrics across three representative models. APB thus serves as an upstream diagnostic complement to execution benchmarks. The APB benchmark and code are available in this URL.

Abstract

Classical Planning

Explore similar work

Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents

PlanBench-XL: Evaluating Long-Horizon Planning of LLM Tool-Use Agents in Large-Scale Tool Ecosystems

ToolTree: Efficient LLM Agent Tool Planning via Dual-Feedback Monte Carlo Tree Search and Bidirectional Pruning