Capability-Grounded Agentic Planning

# Capability-Grounded Agentic Planning
Source: [https://arxiv.org/html/2610.41040](https://arxiv.org/html/2610.41040)
William YeohNing ZhangYevgeniy VorobeychikAffiliation: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\\tau^\{2\}\-bench retail, CGAP outperforms a standard tool\-calling agent by up to 28\.9 points\.

## 1Introduction

LLM agents are increasingly used to retrieve information and act on behalf of users through external tools\([Yao et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib46);[Qin et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib30)\)\. However, both the tasks to solve and the tools that solve them are described in natural language \(NL\), which is imprecise and highly flexible\. The LLM that drives the agent must therefore both*understand*the request and*construct an executable plan*for it, and even simple requests require several interdependent operations\. For example, with basic forecasting, date\-lookup, and geolocation tools, a request for the “weather in Paris and Nice next Monday, and in Nice on Tuesday” takes seven calls: two city lookups, two date resolutions, and three forecasts, with the outputs of some calls supplying the inputs of others\.

ReAct\-style agents address such problems by interleaving reasoning with tool calls, choosing one call at a time\([Yao et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib46)\), while plan\-first systems such as HuggingGPT, ReWOO, and LLMCompiler write out a task decomposition or dependency graph before acting\([Shen et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib34);[Xu et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib43);[Kim et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib16)\), a strategy that Plan\-and\-Solve also applies to reasoning tasks\([Wang et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib41)\)\. However, both classes of approaches use the LLM for both request interpretation and planning, so nothing guarantees that a call’s inputs will be available when it runs\. LLMs also have documented limitations on formal planning problems\([Valmeekam et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib40)\), and intrinsic self\-correction can fail without external feedback\([Huang et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib13)\)\. LLM\-based agentic workflow planning therefore remains unreliable, particularly with smaller \(and cheaper\) LLMs\.

Hybrid \(neuro\-symbolic\) alternatives combine LLMs with formal planners\. Many, such as LLM\+P, use an LLM to translate a planning problem or action model into PDDL\([McDermott et al\., 1998](https://arxiv.org/html/2610.41040#bib.bib24)\)for a classical planner\([Liu et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib18);[Guan et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib9);[Tantakoun et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib38)\), while LLM\-Modulo frameworks pair LLM proposals with external critics\([Kambhampati et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib15)\)\. These approaches start from actions that are described formally or that the LLM writes down, and a plan is only as valid as that model\. Tool\-using agents instead work from*NL specifications of requests and tool capabilities*, in an*open world*: the values that their tools take and return are unknown until a call returns, and they do not come from a finite set that a symbolic planning model can enumerate\.

We propose Capability\-Grounded Agentic Planning \(CGAP\), a framework for agentic workflow planning\. CGAP reads the NL request together with the catalog of capabilities available to the agent, such as tools, data sources, or other agents, each with an NL description and the input schema that function\-calling interfaces require; the LLM’s own abilities, such as summarizing, are not modeled as capabilities\. CGAP compiles the catalog deterministically into a PDDL planning model, with required inputs as preconditions and outputs as effects \(§[2\.2](https://arxiv.org/html/2610.41040#S2.SS2)\), and an LLM parses the request into one goal per requested result \(§[2\.3](https://arxiv.org/html/2610.41040#S2.SS3)\)\. For open\-world inputs and outputs, the model abstracts away values: it tracks only which named inputs and outputs \(*fields*\) are available, a finite set fixed by the catalog\. A classical planner solves this model, and LLMs then turn the abstract plan into executable calls and verify that their results match the request\. Our experiments test whether deriving the dependencies between calls from this model improves tool use over having an LLM generate them\. We instantiate the planner with state\-space search, and we also evaluate a deterministic dependency\-graph planner that ignores delete effects, to see how much of the gain remains without them\. Figure[1](https://arxiv.org/html/2610.41040#S1.F1)shows one user turn of this process\.

In the weather example, the planner cannot predict what the tools will return, so the planning state records only whether a value*is available*for a field such aslatitude, an output of the city lookup and a required input of the forecast, and not which city it describes\. Each requested forecast is a separate goal, but one city lookup makes coordinates available for every forecast, so the planner returns a five\-action abstract plan for a request that takes seven calls \(Figure[2](https://arxiv.org/html/2610.41040#S2.F2)\)\. An execution LLM proposes the entity\-specific calls the plan omits, here a lookup for Nice and a second date resolution, and a deterministic*runtime*, which checks every call before it runs, accepts such a proposal only if the remaining plan stays valid\. Every argument must cite its source, so each coordinate can be traced to the lookup that produced it, and a forecast counts as delivered only after deterministic checks and an LLM verifier accept the call that produced it\.

We make three contributions:

- •Neuro\-symbolic agentic planning\.CGAP, a hybrid approach that compiles tool catalogs deterministically into an abstract, field\-level PDDL model that can be solved before tool outputs are known, uses an LLM to turn the request into its goals, and solves the model with classical planning \(§[2\.2](https://arxiv.org/html/2610.41040#S2.SS2), §[2\.3](https://arxiv.org/html/2610.41040#S2.SS3)\)\.
- •Checked execution with provable guarantees\.A runtime that validates the entity\-specific calls LLMs add, instantiates arguments from cited sources, and verifies each requested result; every execution it admits maps onto a valid abstract plan, so exhaustive search failure certifies infeasibility for the compiled catalog \(§[2\.5](https://arxiv.org/html/2610.41040#S2.SS5)\)\.
- •Experiments on four tool\-using agentic benchmarks\.With three LLMs on ToolSandbox, ComplexFuncBench, BFCL multi\-turn, andτ2\\tau^\{2\}\-bench retail, CGAP outperforms a standard tool\-calling agent in all 15 model–metric comparisons and, with gpt\-oss\-20b, four further baselines\. Replacing deterministic dependency planning with LLM\-generated plans costs up to 16\.8 points, less with GPT\-5 mini; a deterministic graph planner retains most of the gain, and search adds to it where actions have delete effects \(§[3](https://arxiv.org/html/2610.41040#S3)\)\.

Figure 1:One user turn of CGAP\.LLM components \(top: the request parserMθM\_\{\\theta\}, the execution LLMEϕ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](https://arxiv.org/html/2610.41040#S3.SS3)\) replace only the planner, with an LLM or a dependency\-graph planner\.##### Related work\.

A common way to organize tool use is a graph of tool dependencies\. TaskBench and ToolNet build such graphs explicitly\([Shen et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib35);[Liu et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib21)\),[Wu et al\. \(2024\)](https://arxiv.org/html/2610.41040#bib.bib42)plan on them with graph neural networks, and NaviAgent and GRAFT add execution feedback and learned dependencies, respectively\([Jiang et al\., 2026](https://arxiv.org/html/2610.41040#bib.bib14);[Gao et al\., 2026](https://arxiv.org/html/2610.41040#bib.bib7)\)\. CGAP instead derives dependencies deterministically from capability interfaces and lets them govern execution through validated entity\-specific refinements, source\-grounded arguments, and per\-operation completion records\. Our graph\-planning variant shares this model and runtime, so comparing it with search isolates the value of reasoning about delete effects, such as a call that switches off a setting a later call needs \(§[3\.3](https://arxiv.org/html/2610.41040#S3.SS3)\)\. The planners closest to ours are the lifted regression methods LLM\-Regress and NL\-PDDL, which use an LLM to supply commonsense knowledge during planning\([Liu et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib19);[Liu et al\., 2026](https://arxiv.org/html/2610.41040#bib.bib20)\); they keep entities as variables, whereas CGAP drops entity distinctions and leaves them to execution\. Agent\+P likewise pairs a UI transition graph with a symbolic planner\([Ma et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib23)\)\. Appendix[F](https://arxiv.org/html/2610.41040#A6)relates CGAP to service composition, API synthesis, executable request representations, attribution, and prompt\-injection defenses\.

## 2Capability\-Grounded Planning

Figure[1](https://arxiv.org/html/2610.41040#S1.F1)shows one user turn of CGAP; the weather request serves as a running example throughout\.

### 2\.1Setting

A user interacts with an agent overTTturns\. Each turnttopens with an instructionqtq\_\{t\}, which may request several results and may extend, revise, or cancel earlier requests; the agent then makes calls and replies\. A*call*is one invocation of a capability together with its response\. We writeHtH\_\{t\}for the history before turntt,HtuserH\_\{t\}^\{\\mathrm\{user\}\}for the user messages in it, andHt,kH\_\{t,k\}forHtH\_\{t\}followed byqtq\_\{t\}and the firstkkcalls of turntt\. The agent cannot observe whether the user finds the outcome acceptable, so it tracks a condition it can check: every requested operation has a call that was verified against the request\.

The catalog𝒞\\mathcal\{C\}lists*capabilities*, such as tools, data sources, API operations, or other agents\. Each has an NL description and an input schema, which, as in function\-calling interfaces, names its parameters \(e\.g\.,city\); some also have a return schema, documented connections to other tools, or preconditions and effects\. The*application*, here a benchmark adapter, supplies the catalog, annotations, observation rules, transformations, and authorization rules\. For a capabilitycc, we distinguish its*action*aca\_\{c\}, a symbolic counterpart without arguments, from an*invocation*c⁡\(𝐯\)c\(\\mathbf\{v\}\), which calls the sameccwith concrete arguments and returns a*response*\.

### 2\.2Compiling the catalog into a planning model

To order calls, the planner must know which capabilities produce the inputs of others; CGAP reads this off the parameter names in the catalog’s schemas, so the catalog needs no planning syntax\.

##### Facts\.

Let𝒳\\mathcal\{X\}be the set of*fields*, the names of the inputs and outputs that the catalog’s schemas declare \(e\.g\.,city,lat,date\), after a fixed normalization \(Appendix[A\.1](https://arxiv.org/html/2610.41040#A1.SS1)\)\. Function\-calling catalogs always name their inputs; outputs are named by return schemas where given and are otherwise inferred, as described next\. The factAvailable⁡\(p\)\\operatorname\{Available\}\(p\)holds when some value for fieldpphas a*source*, that is, a span of a user message or an expected output field of a successful response \(R1, §[2\.4](https://arxiv.org/html/2610.41040#S2.SS4)\)\. Application\-supplied domain predicates describe other conditions, such as the observed state of a device setting, andSuccess⁡\(i\)\\operatorname\{Success\}\(i\)records that requested operationiiis complete\. We writeℱ\\mathcal\{F\}for the set of facts; a states⊆ℱs\\subseteq\\mathcal\{F\}is the set of facts that hold\.

##### Actions\.

For a capabilitycc, letIn⁡\(c\)⊆𝒳\\In\(c\)\\subseteq\\mathcal\{X\}be the required input fields of its schema andOut⁡\(c\)⊆𝒳\\Out\(c\)\\subseteq\\mathcal\{X\}its candidate outputs\. Candidate outputs come from the return schema when one is given, and otherwise from naming conventions and documented tool connections \(Appendix[A\.1](https://arxiv.org/html/2610.41040#A1.SS1)\)\. Optional annotationsKcpre,Kc\+,Kc−K\_\{c\}^\{\\mathrm\{pre\}\},K\_\{c\}^\{\+\},K\_\{c\}^\{\-\}supply domain preconditions, add effects, and delete effects\. WritingAv⁡\(P\)=\{Available⁡\(p\)∣p∈P\}\\operatorname\{Av\}\(P\)=\\\{\\operatorname\{Available\}\(p\)\\mid p\\in P\\\}forP⊆𝒳P\\subseteq\\mathcal\{X\}, each capability compiles deterministically to a*base action*aca\_\{c\}:

pre⁡\(ac\)\\displaystyle\\operatorname\{pre\}\(a\_\{c\}\)=Av⁡\(In⁡\(c\)\)∪Kcpre,\\displaystyle=\\operatorname\{Av\}\(\\In\(c\)\)\\cup K\_\{c\}^\{\\mathrm\{pre\}\},add⁡\(ac\)\\displaystyle\\operatorname\{add\}\(a\_\{c\}\)=Av⁡\(Out⁡\(c\)\)∪Kc\+,\\displaystyle=\\operatorname\{Av\}\(\\Out\(c\)\)\\cup K\_\{c\}^\{\+\},\(1\)del⁡\(ac\)\\displaystyle\\operatorname\{del\}\(a\_\{c\}\)=Kc−,\\displaystyle=K\_\{c\}^\{\-\},and𝒜𝒞=\{ac∣c∈𝒞\}\\mathcal\{A\}\_\{\\mathcal\{C\}\}=\\\{a\_\{c\}\\mid c\\in\\mathcal\{C\}\\\}\. Candidate outputs describe only whatcc*may*return; at run time, a field becomes available only when a response actually contains it\. An action*achieves*ffiff∈add⁡\(a\)f\\in\\operatorname\{add\}\(a\), andAch⁡\(f\)\\operatorname\{Ach\}\(f\)is the set of base actions that achieveff; predicates must match exactly after normalization\. In the running example,lookup\_cityachieves the coordinate inputs offorecast, andresolve\_dateachieves itsdate\.

Domain predicates capture prerequisites and state changes that input and output schemas do not express\. CGAP takes these rules as application\-supplied modeling inputs; automatically inducing them from natural\-language descriptions is outside our scope\. The annotations describe reusable capability behavior, leaving the planner to determine the action sequence for each request\. In ToolSandbox, for example, sending a message requires cellular service\([Lu et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib22)\)\. The messaging action therefore requires an observation of the cellular state, whose value the runtime checks before invocation\. Status setters compile to one action per value, with delete effects removing the opposite status fact \(Appendix[A\.1](https://arxiv.org/html/2610.41040#A1.SS1)\)\.

##### Plans\.

With the PDDL successor functionγ⁡\(s,a\)=\(s∖del⁡\(a\)\)∪add⁡\(a\)\\gamma\(s,a\)=\(s\\setminus\\operatorname\{del\}\(a\)\)\\cup\\operatorname\{add\}\(a\)\([McDermott et al\., 1998](https://arxiv.org/html/2610.41040#bib.bib24);[Ghallab et al\., 2004](https://arxiv.org/html/2610.41040#bib.bib8)\), a plan⟨a1,…,an⟩\\langle a\_\{1\},\\ldots,a\_\{n\}\\rangleis valid for𝒫=⟨ℱ,𝒜,I,G⟩\\mathcal\{P\}=\\langle\\mathcal\{F\},\\mathcal\{A\},I,G\\rangleifs0=Is\_\{0\}=I,G⊆snG\\subseteq s\_\{n\}, and for1≤ℓ≤n1\\leq\\ell\\leq n,

pre⁡\(aℓ\)⊆sℓ−1,sℓ=γ⁡\(sℓ−1,aℓ\)\.\\operatorname\{pre\}\(a\_\{\\ell\}\)\\subseteq s\_\{\\ell\-1\},\\qquad s\_\{\\ell\}=\\gamma\(s\_\{\\ell\-1\},a\_\{\\ell\}\)\.\(2\)

##### Abstract plans\.

The state records that a latitude is available, not whose latitude it is: coordinates for Paris and for Nice both establishAvailable⁡\(lat\)\\operatorname\{Available\}\(\\texttt\{lat\}\), and the values and their sources stay in the conversation history\. This is deliberate: values are unknown before a call, so a value\-indexed state would force the planner to predict responses, and catalogs say what a capability returns, not which request a returned value will serve\. It also keeps the fact vocabulary independent of the number of entities, as in generalized planning, which seeks plans that hold for any number of objects\([Silver et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib36)\), although CGAP still plans for each request\. Following the principle of planning abstractions\([Sacerdoti, 1974](https://arxiv.org/html/2610.41040#bib.bib33);[Knoblock et al\., 1991](https://arxiv.org/html/2610.41040#bib.bib17)\), we call a plan over this model an*abstract plan*; its actions are capabilities without arguments, not composite tasks as in HTN planning\. It fixes which requested results must be produced, which kinds of prerequisites each needs, and in what order, but not how many copies of a supporting call distinct entities require\. This is why the weather plan has three forecasts but one lookup: each requested result is a goal of its own \(§[2\.3](https://arxiv.org/html/2610.41040#S2.SS3)\), whereas one lookup makeslatavailable for every city\. Execution supplies the missing copies under validation \(§[2\.4](https://arxiv.org/html/2610.41040#S2.SS4)\), and Section[2\.5](https://arxiv.org/html/2610.41040#S2.SS5)shows that every compliant execution still maps onto a valid abstract plan\.

### 2\.3Parsing requests into operations

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ϕE\_\{\\phi\}adds a lookup for Nice and a date resolution for Tuesday \(dashed\) through validated refinements, so five planned actions become seven calls\.##### Request parsing\.

At the start of turntt, an LLMMθM\_\{\\theta\}receives the instructionqtq\_\{t\}, the user historyHtuserH\_\{t\}^\{\\mathrm\{user\}\}, the previous operations𝒪t−1\\mathcal\{O\}\_\{t\-1\}, domain instructionsdd, and the names, descriptions, and input schemas𝒞in\\mathcal\{C\}\_\{\\mathrm\{in\}\}of the capabilities\. It returns the requested operations𝒪t\\mathcal\{O\}\_\{t\}, user\-supplied input values𝒱t\\mathcal\{V\}\_\{t\}, global constraintsΛt\\Lambda\_\{t\}, and requestsUtU\_\{t\}that no capability can serve:

\(𝒪t,𝒱t,Λt,Ut\)=Mθ​\(qt,Htuser,𝒪t−1,d,𝒞in\)\.\(\\mathcal\{O\}\_\{t\},\\mathcal\{V\}\_\{t\},\\Lambda\_\{t\},U\_\{t\}\)=M\_\{\\theta\}\(q\_\{t\},H\_\{t\}^\{\\mathrm\{user\}\},\\mathcal\{O\}\_\{t\-1\},d,\\mathcal\{C\}\_\{\\mathrm\{in\}\}\)\.\(3\)An operationoi=\(i,ci,ri,ϵi,ζi\)o\_\{i\}=\(i,c\_\{i\},r\_\{i\},\\epsilon\_\{i\},\\zeta\_\{i\}\)names a capabilitycic\_\{i\}, a requirementrir\_\{i\}\(entity, time, and scope\), evidence spansϵi\\epsilon\_\{i\}in the user’s messages, and a statusζi∈\{active,cancelled\}\\zeta\_\{i\}\\in\\\{\\mathrm\{active\},\\mathrm\{cancelled\}\\\}\. WhatMθM\_\{\\theta\}must produce is deliberately small: one operation per requested result, including those still unfinished from earlier turns, and no prerequisite steps\. In the running example,MθM\_\{\\theta\}returns three forecast operations and leaves the calendar dates toresolve\_date\. A validator checks span bounds and literal, schema\-compatible value extraction, and allows at most one repair\. Whether a span actually expresses the intended operation remains a judgment of the LLM \(Appendix[C](https://arxiv.org/html/2610.41040#A3)\)\.

##### Terminal actions and the planning problem\.

Each requested result needs its own goal, so for each activeoio\_\{i\}we add a*terminal action*aiterma\_\{i\}^\{\\mathrm\{term\}\}with the preconditions and delete effects ofacia\_\{c\_\{i\}\}andadd⁡\(aiterm\)=add⁡\(aci\)∪\{Success⁡\(i\)\}\\operatorname\{add\}\(a\_\{i\}^\{\\mathrm\{term\}\}\)=\\operatorname\{add\}\(a\_\{c\_\{i\}\}\)\\cup\\\{\\operatorname\{Success\}\(i\)\\\}\. The terminal action is the only achiever ofSuccess⁡\(i\)\\operatorname\{Success\}\(i\), so a result already in the history, such as a forecast from an earlier turn, cannot complete a newly requested operation without a new call, and three requested forecasts yield three separate goals\. Data in the history can still supply*inputs*: coordinates looked up for one forecast serve every later call that needs them\. The LLM thus specifies the requested results, and search determines their dependencies at the field level\. Afterkkcalls of turntt, the planning problem is𝒫t,k=⟨ℱt,𝒜t,It,k,Gt⟩\\mathcal\{P\}\_\{t,k\}=\\langle\\mathcal\{F\}\_\{t\},\\mathcal\{A\}\_\{t\},I\_\{t,k\},G\_\{t\}\\rangle, with𝒜t=𝒜𝒞∪\{aiterm\}oi​active\\mathcal\{A\}\_\{t\}=\\mathcal\{A\}\_\{\\mathcal\{C\}\}\\cup\\\{a\_\{i\}^\{\\mathrm\{term\}\}\\\}\_\{o\_\{i\}\\,\\mathrm\{active\}\},Gt=\{Success⁡\(i\)\}oi​activeG\_\{t\}=\\\{\\operatorname\{Success\}\(i\)\\\}\_\{o\_\{i\}\\,\\mathrm\{active\}\}, and

It,k=Av⁡\(Xt,k\)∪Wt,k∪Dt,k,I\_\{t,k\}=\\operatorname\{Av\}\(X\_\{t,k\}\)\\cup W\_\{t,k\}\\cup D\_\{t,k\},\(4\)whereXt,kX\_\{t,k\}is the set of available fields,Wt,kW\_\{t,k\}the domain facts maintained by the application’s observation rules, andDt,kD\_\{t,k\}the completion markers backed by accepted completion records; Equation[5](https://arxiv.org/html/2610.41040#S2.E5)gives how each call updates these sets\. Values never enter the state\. In the running example,I0,0=Av⁡\(\{city,day\}\)I\_\{0,0\}=\\operatorname\{Av\}\(\\\{\\texttt\{city\},\\texttt\{day\}\\\}\)andG0=\{Success⁡\(1\),Success⁡\(2\),Success⁡\(3\)\}G\_\{0\}=\\\{\\operatorname\{Success\}\(1\),\\operatorname\{Success\}\(2\),\\operatorname\{Success\}\(3\)\\\}\.

### 2\.4Planning and grounded execution

Within a turn, search and execution alternate \(Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)\) under three budgets:BBstate expansions per search,LLactions per refinement, andNNexecution decisions per turn\. These are hyperparameters, fixed in advance and shared by all benchmarks and LLMs \(B=2,048B=2\{,\}048,L=4L=4,N=32N=32\)\.

##### Search and execution decisions\.

Breadth\-first search solves𝒫t,k\\mathcal\{P\}\_\{t,k\}\(Algorithm[2](https://arxiv.org/html/2610.41040#algorithm2)\) and returns a shortest abstract plan,NoPlanif it has expanded every reachable state without reachingGtG\_\{t\}, orLimitif it has expanded a predefined numberBBof states first\. In the running example, the plan has one city lookup, one date resolution, and three forecasts \(Figure[2](https://arxiv.org/html/2610.41040#S2.F2)\(a\)\)\. Execution then works through this plan; afterkkcalls, the*remaining plan*π¯t,k\\bar\{\\pi\}\_\{t,k\}is the part of it not yet executed\. Givenπ¯t,k\\bar\{\\pi\}\_\{t,k\}, an execution LLMEϕE\_\{\\phi\}proposes one of three decisions, each counting towardNN: 1\)Execute, which supplies argument sources for the first planned action; 2\)Refine, which proposes supporting actionsρ\\rhoto prepend when the plan needs an input for which no source exists; and 3\)Stop, which asks the user for clarification or reports work that cannot be done\. We describeExecuteandRefinenext\.

The LLM never writes an argument value\. Each argument of anExecutedecision cites a source, a span of the conversation or a field of a successful response, and a*resolver*from a fixed set that the LLM cannot extend: a*decoder*copies the cited text or converts it to the schema’s type \(e\.g\.,"2"to the integer 2\), and a*transformation*is a deterministic function supplied by the application, such as a date converter\. Application defaults are also allowed\. Before calling, the runtime checks the action’s preconditions inIt,kI\_\{t,k\}, the argument schema, the sources, and the application’s authorization rules\. Whether a sourced argument refers to the intended entity is assessed after the call by the completion verifier, so for tools with side effects this check cannot undo a wrongly targeted action\.

Refinement \(Refine\) is how an abstract plan becomes a concrete one\. After the Paris forecast,Available⁡\(lat\)\\operatorname\{Available\}\(\\texttt\{lat\}\)still holds, but no source contains the coordinates of Nice\.EϕE\_\{\\phi\}therefore prepends a lookup for Nice, and later a date resolution for Tuesday, so that five planned actions become seven calls \(Figure[2](https://arxiv.org/html/2610.41040#S2.F2)\(b\)\)\. A refinement holds at mostLLactions, each a recursive achiever of a precondition of a pending terminal action, and no terminal actions\. It is kept only ifρ∥π¯t,k\\rho\\mathbin\{\\\|\}\\bar\{\\pi\}\_\{t,k\}, the prepended actions followed by the remaining plan, is valid fromIt,kI\_\{t,k\}\(Appendix[A\.5](https://arxiv.org/html/2610.41040#A1.SS5)\)\. A refinement can therefore add supporting calls, but it cannot add, remove, or reorder the terminal actions of the current plan; only search can reorder them\. Validation also cannot tell whether a refinement is*needed*: a redundant second lookup for Paris passes as easily as the lookup for Nice, so necessity is left to the LLM\. Without delete effects \(ComplexFuncBench, BFCL,τ2\\tau^\{2\}\-bench retail\), added facts cannot break the remaining plan, so only the prefix is checked\.

##### Completion verification\.

A call*succeeds*if the tool reports success; whether it delivers its operation’s result is decided separately\. For each successful terminal call, deterministic checks confirm its capability, sources, and application\-supplied domain tests, and an LLM verifier compares the execution recordeewithrir\_\{i\},ϵi\\epsilon\_\{i\}, andΛt\\Lambda\_\{t\}\. The verifier returnsSupported,Contradicted, orUnknownwith cited evidence\. Only an accepted record, one with passing checks and aSupportedverdict, addsSuccess⁡\(i\)\\operatorname\{Success\}\(i\), and a call completes at most one operation\. The verifier should reject, e\.g\., a forecast for the wrong city, but it can err\.

##### State update\.

A calleeadds factsOe\+O\_\{e\}^\{\+\}, namely newly available fields, established domain facts, andSuccess⁡\(i\)\\operatorname\{Success\}\(i\)if its completion record foroio\_\{i\}is accepted, and deletes factsOe−O\_\{e\}^\{\-\}:

It,k\+1=\(It,k∖Oe−\)∪Oe\+\.I\_\{t,k\+1\}=\(I\_\{t,k\}\\setminus O\_\{e\}^\{\-\}\)\\cup O\_\{e\}^\{\+\}\.\(5\)Equation[4](https://arxiv.org/html/2610.41040#S2.E4)gives the parts of the state, and Equation[5](https://arxiv.org/html/2610.41040#S2.E5)how a call changes them: the parts use disjoint predicates, so it updatesXX,WW, andDDseparately, andIt,k\+1I\_\{t,k\+1\}keeps the form of Equation[4](https://arxiv.org/html/2610.41040#S2.E4)\. The runtime enforces three rules \(Appendix[A\.4](https://arxiv.org/html/2610.41040#A1.SS4)\)\.*\(R1\)*A successful response ofccmakes available only fields inOut⁡\(c\)\\Out\(c\); other parsed fields can be cited as values but make nothing available\.*\(R2\)*A successful call ofccdeletes all ofKc−K\_\{c\}^\{\-\}and adds no domain fact outsideKc\+K\_\{c\}^\{\+\}\.*\(R3\)*A failed call may delete facts but adds none\. Search reruns if the remaining plan becomes invalid or a call fails, lacks a required output, or has its completion rejected\. A turn ends whenGt⊆It,kG\_\{t\}\\subseteq I\_\{t,k\}, at aStopdecision, when search returnsNoPlanorLimit, or afterNNdecisions;EϕE\_\{\\phi\}then replies from the accepted records and the unresolved work \(Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)\)\.

### 2\.5What the planner and the runtime certify

Proposition[1](https://arxiv.org/html/2610.41040#Thmproposition1)follows from the runtime checks alone, so it also holds for the planner ablations \(§[3\.3](https://arxiv.org/html/2610.41040#S3.SS3)\), as does Proposition[2](https://arxiv.org/html/2610.41040#Thmproposition2)\(b\); only exhaustive search, however, certifies that no plan exists\.

###### Proposition 1\(Runtime invariants\)\.

In every turnttof Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)and for everykk:

1. \(i\)*Applicability\.*Every called action’s preconditions hold inIt,kI\_\{t,k\}at the time of the call, and the terminal actions of the remaining plan are, in order, a suffix of those in the plan last returned by search\.
2. \(ii\)*Provenance\.*Every argument value is computed by a decoder or an application\-supplied transformation from user spans or successful\-response fields inHt,kH\_\{t,k\}, or is a default the application configured for that argument\.
3. \(iii\)*Completion accounting\.*EverySuccess⁡\(i\)∈Dt,k\\operatorname\{Success\}\(i\)\\in D\_\{t,k\}is backed by an accepted completion record for a successful call ofcic\_\{i\}, made in turnttor inherited from an unchanged operation, and distinct markers by distinct calls\.

These structural invariants are proved in Appendix[B](https://arxiv.org/html/2610.41040#A2)\. A cited source, transformation, or default may still yield a wrong value, the verifier that accepted a record may be wrong, and the free\-form final reply is not constrained\.

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τ2\\tau^\{2\}\-Retail the success rate on all 114τ2\\tau^\{2\}\-bench retail tasks, over three runs per task \(§[3\.1](https://arxiv.org/html/2610.41040#S3.SS1)\)\. 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](https://arxiv.org/html/2610.41040#A5.SS3)\)\. Bold: best per model; Table[4](https://arxiv.org/html/2610.41040#A4.T4)gives paired differences\.###### Proposition 2\(Executions refine abstract plans\)\.

*\(a\)*Every plan that Algorithm[2](https://arxiv.org/html/2610.41040#algorithm2)returns on𝒫t,k\\mathcal\{P\}\_\{t,k\}is valid and has the fewest actions among valid plans\.*\(b\)*Map each successful call ofcctoaiterma\_\{i\}^\{\\mathrm\{term\}\}if it yields an accepted completion record foroio\_\{i\}, and toaca\_\{c\}otherwise\. Under R1–R3, the image of every execution of Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)fromIt,kI\_\{t,k\}that reachesGtG\_\{t\}, whatever the LLMs propose, is a valid plan for𝒫t,k\\mathcal\{P\}\_\{t,k\}, so the execution makes at least\|π¯t,k\|\|\\bar\{\\pi\}\_\{t,k\}\|successful calls if search returnsπ¯t,k\\bar\{\\pi\}\_\{t,k\}\.*\(c\)*If search returnsNoPlan, for any budgetBB, no execution of Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)fromIt,kI\_\{t,k\}completes the turn\.

Part \(a\) is standard\([Russell and Norvig, 2003](https://arxiv.org/html/2610.41040#bib.bib32)\), and part \(b\) is the upward\-solution property of abstraction hierarchies\([Tenenberg, 1988](https://arxiv.org/html/2610.41040#bib.bib39);[Knoblock et al\., 1991](https://arxiv.org/html/2610.41040#bib.bib17)\)\(Appendix[B](https://arxiv.org/html/2610.41040#A2)\); what is new is that the runtime enforces R1–R3 against arbitrary LLM proposals\. Through \(c\),NoPlan, unlikeLimit, certifies that no call sequence passing the runtime’s checks can complete the request, but only for the compiled model: an undeclared output cannot enable an action \(R1\)\. The count in \(b\) is loose on multi\-entity requests, and we do not use it\.

## 3Experiments

### 3\.1Experimental setup

##### Benchmarks\.

We use four interactive benchmarks \(Appendix[A\.2](https://arxiv.org/html/2610.41040#A1.SS2)\)\. The first, ToolSandbox\([Lu et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib22)\), contains stateful, conversational scenarios scored by their similarity to annotated milestones; in its*state\-dependency*category, a tool works only in some world states \(sending a message requires cellular service to be on\)\. The second, ComplexFuncBench\([Zhong et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib47)\), contains multi\-step requests with user constraints over real travel APIs in five domains, scored by success rate and call accuracy\. The third, BFCL multi\-turn\([Patil et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib29)\), checks the final environment state and the executed calls in multi\-turn conversations \(base, missing functions, missing parameters, long context\)\. From these three we use stratified subsets of 120 ToolSandbox scenarios, 250 ComplexFuncBench requests, and 200 BFCL conversations \(50 per category\)\. The fourth is the retail domain ofτ2\\tau^\{2\}\-bench\([Barres et al\., 2026](https://arxiv.org/html/2610.41040#bib.bib3)\), a revision ofτ\\tau\-bench’s\([Yao et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib45)\), whose 114 tasks we all run: a customer simulated by GPT\-4\.1\([OpenAI, 2025c](https://arxiv.org/html/2610.41040#bib.bib28)\)asks the agent to cancel, modify, return, or exchange orders under a written policy, and a task succeeds if the final database matches the reference one\. As on ComplexFuncBench and BFCL, we add no domain annotations: the policy’s rules, such as cancelling only pending orders, are enforced by the tools, not the planning model\.

##### Baselines\.

We compare CGAP with a*plain agent*, which receives the tool catalog and calls tools in a loop until it replies, under three LLMs: gpt\-oss\-20b\([OpenAI, 2025b](https://arxiv.org/html/2610.41040#bib.bib27)\), Qwen3\-32B\([Yang et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib44)\), and GPT\-5 mini\([OpenAI, 2025a](https://arxiv.org/html/2610.41040#bib.bib26)\)\. With gpt\-oss\-20b, four further baselines test other explanations for CGAP’s gains \(Appendix[E\.3](https://arxiv.org/html/2610.41040#A5.SS3)\): the plain agent given our ToolSandbox dependency annotations as prompt notes, a*compute\-matched*plain agent with self\-checks, and adapted versions of two established plan\-first agents, ReWOO\([Xu et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib43)\)and LLMCompiler\([Kim et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib16)\)\.

##### Evaluation\.

We run each configuration three times per task\. Binary success metrics are aggregated by majority \(a task counts as solved if at least two runs solve it\), and ToolSandbox scores and call accuracy are averaged over runs\. Confidence intervals use 10,000 task\-level bootstrap resamples, paired by task for differences between methods, and we interpret them as pointwise intervals; Appendices[A\.2](https://arxiv.org/html/2610.41040#A1.SS2)and[E\.2](https://arxiv.org/html/2610.41040#A5.SS2)give details\.

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\.

### 3\.2Main results

In Table[1](https://arxiv.org/html/2610.41040#S2.T1), CGAP outperforms every baseline on every benchmark and metric with all three LLMs, and all 15 paired intervals against the plain agent exclude zero \(Table[4](https://arxiv.org/html/2610.41040#A4.T4)\)\. The gains are smallest with GPT\-5 mini \(5\.1–13\.9 points\), whose plain agent is the strongest on every metric\.

On ToolSandbox, CGAP gains 13\.9–28\.9 points, most on state\-dependency scenarios \(98\.4 against 62\.8 with gpt\-oss\-20b; Table[5](https://arxiv.org/html/2610.41040#A4.T5)\), which use our hand\-written device\-dependency annotations\. On ComplexFuncBench, it improves success by 5\.2–10\.8 points and call accuracy by 5\.1–9\.1, and on BFCL multi\-turn it gains 6\.0–18\.0 points\. Onτ2\\tau^\{2\}\-bench retail, it gains 8\.8–14\.0 points although every agent receives the same policy, both on the 64 tasks involving two or more orders and on the other 50 \(Table[6](https://arxiv.org/html/2610.41040#A4.T6)\)\.

##### Additional baselines\.

Dependency notes close about half of the state\-dependency gap \(§[3\.3](https://arxiv.org/html/2610.41040#S3.SS3)\)\. With self\-checks and tokens per task within 5% of CGAP’s \(17% more onτ2\\tau^\{2\}\-bench retail\), the plain agent gains only 3\.0–6\.1 points; adapted ReWOO stays within 2\.7 points of it, and adapted LLMCompiler is 7\.2–16\.7 points below it outside ToolSandbox\. CGAP leads all four on every measure, with paired intervals excluding zero \(Table[8](https://arxiv.org/html/2610.41040#A4.T8)\)\.

### 3\.3Ablations

#### 3\.3\.1The value of symbolic planning

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](https://arxiv.org/html/2610.41040#A4.T4)\)\.##### LLM\-planning ablation\.

Our main ablation replaces every search call with one LLM call that receives the same planning problem and returns an ordered list of actions without arguments\. The runtime validates it \(Equation[2](https://arxiv.org/html/2610.41040#S2.E2)\) and allows one repair, after which an invalid plan ends the turn asInvalidPlan\. All else is shared \(Appendix[E\.2](https://arxiv.org/html/2610.41040#A5.SS2)\), so the comparison measures the effect of replacing symbolic with LLM\-based planning within the CGAP architecture\. With gpt\-oss\-20b and Qwen3\-32B, search improves every metric \(Figure[3](https://arxiv.org/html/2610.41040#S3.F3)\), by 4\.4–16\.8 points, and all ten paired intervals exclude zero\. With GPT\-5 mini, the gains shrink to−\-0\.1 to 4\.8 points, and only the ToolSandbox interval excludes zero \(Table[4](https://arxiv.org/html/2610.41040#A4.T4)\)\. LLM planning is still a strong variant, beating the compute\-matched agent and both plan\-first agents \(Table[7](https://arxiv.org/html/2610.41040#A4.T7)\); Appendix[D\.1](https://arxiv.org/html/2610.41040#A4.SS1)analyzes its failures\.

##### Graph\-planning ablation\.

A second ablation replaces search with a deterministic dependency\-graph planner in the style of TaskBench and ToolNet, which backward\-chains from the pending terminal actions over the same compiled model and ignores delete effects \(Appendix[E\.2](https://arxiv.org/html/2610.41040#A5.SS2)\)\. With gpt\-oss\-20b, it scores above LLM planning on every measure \(Table[2](https://arxiv.org/html/2610.41040#S3.T2); e\.g\., 78\.1 against 64\.4 on ToolSandbox\), though we lack paired intervals for that comparison\. Against search, its paired intervals include zero on all four benchmarks, and search clearly leads only on state\-dependency scenarios\. On that category, access to the dependency rules does not explain CGAP’s score by itself: given the same rules as prompt notes, the plain agent’s score rises from 62\.8 to 79\.6, still 18\.8 points\[12\.0,25\.7\]\[12\.0,25\.7\]below CGAP’s 98\.4\. With the same compiled model, search also beats the graph planner there by 8\.9 points\[3\.6,14\.5\]\[3\.6,14\.5\], which is what modeling delete effects adds\. On benchmarks without delete effects, deterministic dependency planning accounts for most of the benefit, and search adds no clear gain\.

#### 3\.3\.2Provenance and verification

Removing provenance \(Table[2](https://arxiv.org/html/2610.41040#S3.T2)\) lowers the four benchmark\-level scores by 3\.6–5\.4 points \(intervals exclude zero except onτ2\\tau^\{2\}\-bench retail\), and removing verification by 1\.6–2\.7 \(only the ToolSandbox average excludes zero\)\. Both mainly serve Proposition[1](https://arxiv.org/html/2610.41040#Thmproposition1), which success metrics do not measure\.

## 4Conclusion

We presented CGAP, a neuro\-symbolic approach in which LLMs interpret requests, ground arguments, and judge results, while a classical planner orders calls over an abstract model compiled from the tool catalog\. On four benchmarks, it outperforms plain tool calling with all three LLMs; LLM planning in place of its deterministic planner lowers 14 of 15 model–metric scores \(clearly with the open models, slightly with GPT\-5 mini\), a dependency\-graph planner retains most of the benefit, and search adds to it where actions have delete effects\.

## Limitations

Our guarantees hold only for the compiled model and runtime rules:NoPlancertifies infeasibility only for the catalog as compiled, and because the abstraction merges entities, the call count of Proposition[2](https://arxiv.org/html/2610.41040#Thmproposition2)\(b\) is loose on multi\-entity requests\. How often turns end inNoPlanrather thanLimit, and hence the certificate’s practical value, is unmeasured\. Request parsing can misread an operation, a cited source can be wrong or tied to the wrong entity, and the verifier can accept an incorrect result and, running after the call, cannot undo a wrong side effect; we have not audited how often these errors, or unnecessary refinements, occur\. Name\-based field matching can miss or conflate connections, and breadth\-first search is exponential in the number of facts, so its budget can stop it before a plan is found\. We evaluate on subsets of three English benchmarks and onτ2\\tau^\{2\}\-bench retail with three LLMs, under a majority\-of\-three protocol not comparable to single\-run leaderboard scores, and our planner ablations exclude specialized planning systems\. State\-dependent planning needs application\-supplied domain rules when the catalog does not expose prerequisites and effects, which adds a modeling burden, and evidence that handling delete effects helps beyond access to this information comes from one domain and one model\. The advantage of deterministic over LLM planning is model\-dependent: with GPT\-5 mini, only the ToolSandbox interval excludes zero, and the ablation’sInvalidPlanrate partly reflects its one\-repair budget\. The additional baselines use only gpt\-oss\-20b \(the dependency\-notes agent only ToolSandbox\), our ReWOO adaptation adds replanning and an ask\-or\-decline step, and another LLMCompiler adaptation might beat the plain agent outside ToolSandbox\. Finally, CGAP uses 1\.3–1\.6 times the plain agent’s tokens per task with gpt\-oss\-20b \(Table[9](https://arxiv.org/html/2610.41040#A4.T9)\); we report tokens only with that model, onτ2\\tau^\{2\}\-bench retail only as a ratio, and do not measure latency\.

## Ethical Considerations

Tool calls can affect external systems\. Argument provenance records where each value came from; authorization, privacy, and the decision whether an action is appropriate remain the application’s job, so applications must enforce access controls and, where appropriate, ask for confirmation before consequential calls\. Retained source spans and tool responses can contain sensitive information and need suitable access and retention controls\. Our experiments use public benchmarks and involve no human subjects\. We do not evaluate resistance to adversarial prompt injection or deployment safety, and we do not claim that the planning and accounting invariants provide such protection\.

## References

- An et al\. \(2025\)Hengyu An, Jinghuai Zhang, Tianyu Du, Chunyi Zhou, Qingming Li, Tao Lin, and Shouling Ji\. 2025\.[IPIGuard: A novel tool dependency graph\-based defense against indirect prompt injection in LLM agents](https://doi.org/10.18653/v1/2025.emnlp-main.53)\.In*Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing*, pages 1023–1039, Suzhou, China\. Association for Computational Linguistics\.
- Andreas et al\. \(2020\)Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Smriti Jha, Dan Klein, and 26 others\. 2020\.[Task\-oriented dialogue as dataflow synthesis](https://doi.org/10.1162/tacl_a_00333)\.*Transactions of the Association for Computational Linguistics*, 8:556–571\.
- Barres et al\. \(2026\)Victor Barres, Honghua Dong, Soham Ray, Xujie Si, and Karthik R\. Narasimhan\. 2026\.[τ2\\tau^\{2\}\-bench: Evaluating conversational agents in a dual\-control environment](https://proceedings.mlr.press/v306/barres26a.html)\.In*Proceedings of the 43rd International Conference on Machine Learning*, volume 306 of*Proceedings of Machine Learning Research*, pages 6736–6782\.
- Debenedetti et al\. \(2026\)Edoardo Debenedetti, Ilia Shumailov, Tianqi Fan, Jamie Hayes, Nicholas Carlini, Daniel Fabian, Christoph Kern, Chongyang Shi, Andreas Terzis, and Florian Tramèr\. 2026\.[Defeating prompt injections by design](https://arxiv.org/abs/2503.18813)\.In*IEEE Conference on Secure and Trustworthy Machine Learning \(SaTML\)*\.
- Feng et al\. \(2017\)Yu Feng, Ruben Martins, Yuepeng Wang, Isil Dillig, and Thomas W\. Reps\. 2017\.[Component\-based synthesis for complex APIs](https://doi.org/10.1145/3009837.3009851)\.In*Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages \(POPL\)*, pages 599–612\. ACM\.
- Gao et al\. \(2023\)Tianyu Gao, Howard Yen, Jiatong Yu, and Danqi Chen\. 2023\.[Enabling large language models to generate text with citations](https://doi.org/10.18653/v1/2023.emnlp-main.398)\.In*Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing*, pages 6465–6488, Singapore\. Association for Computational Linguistics\.
- Gao et al\. \(2026\)Xinyi Gao, Xinyu Ren, Junliang Yu, Tong Chen, Quoc Viet Hung Nguyen, and Hongzhi Yin\. 2026\.[GRAFT: Graph\-tokenized LLMs for tool planning](https://arxiv.org/abs/2605.11706)\.*Preprint*, arXiv:2605\.11706\.
- Ghallab et al\. \(2004\)Malik Ghallab, Dana Nau, and Paolo Traverso\. 2004\.[*Automated Planning: Theory and Practice*](https://projects.laas.fr/planning/aptp/)\.Morgan Kaufmann\.
- Guan et al\. \(2023\)Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati\. 2023\.[Leveraging pre\-trained large language models to construct and utilize world models for model\-based task planning](https://proceedings.neurips.cc/paper_files/paper/2023/hash/f9f54762cbb4fe4dbffdd4f792c31221-Abstract.html)\.In*Advances in Neural Information Processing Systems*, volume 36, pages 79081–79094\.
- Guo et al\. \(2022\)Zheng Guo, David Cao, Davin Tjong, Jean Yang, Cole Schlesinger, and Nadia Polikarpova\. 2022\.[Type\-directed program synthesis for RESTful APIs](https://doi.org/10.1145/3519939.3523450)\.In*Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation \(PLDI\)*, pages 122–136\. ACM\.
- Gupta et al\. \(2018\)Sonal Gupta, Rushin Shah, Mrinal Mohit, Anuj Kumar, and Mike Lewis\. 2018\.[Semantic parsing for task oriented dialog using hierarchical representations](https://doi.org/10.18653/v1/D18-1300)\.In*Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing*, pages 2787–2792, Brussels, Belgium\. Association for Computational Linguistics\.
- Hoffmann et al\. \(2007\)Jörg Hoffmann, Piergiorgio Bertoli, and Marco Pistore\. 2007\.[Web service composition as planning, revisited: In between background theories and initial state uncertainty](https://aaaipress.org/Library/AAAI/2007/aaai07-161.php)\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, pages 1013–1018\. AAAI Press\.
- Huang et al\. \(2024\)Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou\. 2024\.[Large language models cannot self\-correct reasoning yet](https://openreview.net/forum?id=IkmD3fKBPQ)\.In*International Conference on Learning Representations*\.
- Jiang et al\. \(2026\)Yan Jiang, Hao Zhou, Lizhong Gu, Tianlong Li, Ruinan Jin, Wanqi Zhou, and Ai Han\. 2026\.[NaviAgent: Graph\-driven bilevel planning for scalable tool orchestration](https://proceedings.mlr.press/v306/jiang26be.html)\.In*Proceedings of the 43rd International Conference on Machine Learning*, volume 306 of*Proceedings of Machine Learning Research*, pages 53472–53506\. PMLR\.
- Kambhampati et al\. \(2024\)Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B\. Murthy\. 2024\.[Position: LLMs can’t plan, but can help planning in LLM\-modulo frameworks](https://proceedings.mlr.press/v235/kambhampati24a.html)\.In*Proceedings of the 41st International Conference on Machine Learning*, volume 235 of*Proceedings of Machine Learning Research*, pages 22895–22907\. PMLR\.
- Kim et al\. \(2024\)Sehoon Kim, Suhong Moon, Ryan Tabrizi, Nicholas Lee, Michael W\. Mahoney, Kurt Keutzer, and Amir Gholami\. 2024\.[An LLM compiler for parallel function calling](https://proceedings.mlr.press/v235/kim24y.html)\.In*Proceedings of the 41st International Conference on Machine Learning*, volume 235 of*Proceedings of Machine Learning Research*, pages 24370–24391\. PMLR\.
- Knoblock et al\. \(1991\)Craig A\. Knoblock, Josh D\. Tenenberg, and Qiang Yang\. 1991\.[Characterizing abstraction hierarchies for planning](https://cdn.aaai.org/AAAI/1991/AAAI91-108.pdf)\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, pages 692–697\. AAAI Press\.
- Liu et al\. \(2023\)Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone\. 2023\.[LLM\+P: Empowering large language models with optimal planning proficiency](https://arxiv.org/abs/2304.11477)\.*Preprint*, arXiv:2304\.11477\.
- Liu et al\. \(2025\)Xiaotian Liu, Ali Pesaranghader, Hanze Li, Punyaphat Sukcharoenchaikul, Jaehong Kim, Tanmana Sadhu, Hyejeong Jeon, and Scott Sanner\. 2025\.[Open\-world planning via lifted regression with LLM\-inferred affordances for embodied agents](https://doi.org/10.18653/v1/2025.acl-long.1018)\.In*Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 20881–20897, Vienna, Austria\. Association for Computational Linguistics\.
- Liu et al\. \(2026\)Xiaotian Liu, Armin Toroghi, Jiazhou Liang, David Courtis, Ruiwen Li, Ali Pesaranghader, Jaehong Kim, Tanmana Sadhu, Hyejeong Jeon, and Scott Sanner\. 2026\.[Natural language PDDL \(NL\-PDDL\) for open\-world goal\-oriented commonsense regression planning in embodied AI](https://proceedings.iclr.cc/paper_files/paper/2026/hash/d7c7b6f2e4ad3f56b85eaae765016d3a-Abstract-Conference.html)\.In*International Conference on Learning Representations*\.
- Liu et al\. \(2024\)Xukun Liu, Zhiyuan Peng, Xiaoyuan Yi, Xing Xie, Lirong Xiang, Yuchen Liu, and Dongkuan Xu\. 2024\.[ToolNet: Connecting large language models with massive tools via tool graph](https://arxiv.org/abs/2403.00839)\.*Preprint*, arXiv:2403\.00839\.
- Lu et al\. \(2025\)Jiarui Lu, Thomas Holleis, Yizhe Zhang, Bernhard Aumayer, Feng Nan, Haoping Bai, Shuang Ma, Shen Ma, Mengyu Li, Guoli Yin, Zirui Wang, and Ruoming Pang\. 2025\.[ToolSandbox: A stateful, conversational, interactive evaluation benchmark for LLM tool use capabilities](https://doi.org/10.18653/v1/2025.findings-naacl.65)\.In*Findings of the Association for Computational Linguistics: NAACL 2025*, pages 1160–1183, Albuquerque, New Mexico\. Association for Computational Linguistics\.
- Ma et al\. \(2025\)Shang Ma, Xusheng Xiao, and Yanfang Ye\. 2025\.[Agent\+P: Guiding UI agents via symbolic planning](https://arxiv.org/abs/2510.06042)\.*Preprint*, arXiv:2510\.06042\.
- McDermott et al\. \(1998\)Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld, and David Wilkins\. 1998\.PDDL—the planning domain definition language\.Technical Report CVC TR\-98\-003/DCS TR\-1165, Yale Center for Computational Vision and Control, New Haven, CT\.
- McIlraith and Son \(2002\)Sheila A\. McIlraith and Tran Cao Son\. 2002\.[Adapting Golog for composition of semantic web services](https://www.daml.org/services/owl-s/pub-archive.html)\.In*Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning \(KR\)*, pages 482–493\.
- OpenAI \(2025a\)OpenAI\. 2025a\.[GPT\-5 system card](https://openai.com/index/gpt-5-system-card/)\.Technical report, OpenAI\.
- OpenAI \(2025b\)OpenAI\. 2025b\.[gpt\-oss\-120b & gpt\-oss\-20b model card](https://arxiv.org/abs/2508.10925)\.*Preprint*, arXiv:2508\.10925\.
- OpenAI \(2025c\)OpenAI\. 2025c\.[Introducing GPT\-4\.1 in the API](https://openai.com/index/gpt-4-1/)\.
- Patil et al\. \(2025\)Shishir G Patil, Huanzhi Mao, Fanjia Yan, Charlie Cheng\-Jie Ji, Vishnu Suresh, Ion Stoica, and Joseph E\. Gonzalez\. 2025\.[The Berkeley function calling leaderboard \(BFCL\): From tool use to agentic evaluation of large language models](https://proceedings.mlr.press/v267/patil25a.html)\.In*Proceedings of the 42nd International Conference on Machine Learning*, volume 267 of*Proceedings of Machine Learning Research*, pages 48371–48392\. PMLR\.
- Qin et al\. \(2024\)Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, Sihan Zhao, Lauren Hong, Runchu Tian, Ruobing Xie, Jie Zhou, Mark Gerstein, Dahai Li, Zhiyuan Liu, and Maosong Sun\. 2024\.[ToolLLM: Facilitating large language models to master 16000\+ real\-world APIs](https://proceedings.iclr.cc/paper_files/paper/2024/hash/28e50ee5b72e90b50e7196fde8ea260e-Abstract-Conference.html)\.In*International Conference on Learning Representations*\.
- Rashkin et al\. \(2023\)Hannah Rashkin, Vitaly Nikolaev, Matthew Lamm, Lora Aroyo, Michael Collins, Dipanjan Das, Slav Petrov, Gaurav Singh Tomar, Iulia Turc, and David Reitter\. 2023\.[Measuring attribution in natural language generation models](https://doi.org/10.1162/coli_a_00486)\.*Computational Linguistics*, 49\(4\):777–840\.
- Russell and Norvig \(2003\)Stuart Russell and Peter Norvig\. 2003\.[*Artificial Intelligence: A Modern Approach*](https://aima.cs.berkeley.edu/2nd-ed/index.html), 2 edition\.Prentice Hall\.
- Sacerdoti \(1974\)Earl D\. Sacerdoti\. 1974\.[Planning in a hierarchy of abstraction spaces](https://doi.org/10.1016/0004-3702(74)90026-5)\.*Artificial Intelligence*, 5\(2\):115–135\.
- Shen et al\. \(2023\)Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang\. 2023\.[HuggingGPT: Solving AI tasks with ChatGPT and its friends in Hugging Face](https://proceedings.neurips.cc/paper_files/paper/2023/hash/77c33e6a367922d003ff102ffb92b658-Abstract-Conference.html)\.In*Advances in Neural Information Processing Systems*, volume 36, pages 38154–38180\.
- Shen et al\. \(2024\)Yongliang Shen, Kaitao Song, Xu Tan, Wenqi Zhang, Kan Ren, Siyu Yuan, Weiming Lu, Dongsheng Li, and Yueting Zhuang\. 2024\.[TaskBench: Benchmarking large language models for task automation](https://proceedings.neurips.cc/paper_files/paper/2024/hash/085185ea97db31ae6dcac7497616fd3e-Abstract-Datasets_and_Benchmarks_Track.html)\.In*Advances in Neural Information Processing Systems*, volume 37, pages 4540–4574\.
- Silver et al\. \(2024\)Tom Silver, Soham Dan, Kavitha Srinivas, Joshua B\. Tenenbaum, Leslie Pack Kaelbling, and Michael Katz\. 2024\.[Generalized planning in PDDL domains with pretrained large language models](https://doi.org/10.1609/aaai.v38i18.30006)\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pages 20256–20264\.
- Sirin et al\. \(2004\)Evren Sirin, Bijan Parsia, Dan Wu, James Hendler, and Dana Nau\. 2004\.[HTN planning for web service composition using SHOP2](https://doi.org/10.1016/j.websem.2004.06.005)\.*Journal of Web Semantics*, 1\(4\):377–396\.
- Tantakoun et al\. \(2025\)Marcus Tantakoun, Christian Muise, and Xiaodan Zhu\. 2025\.[LLMs as planning formalizers: A survey for leveraging large language models to construct automated planning models](https://doi.org/10.18653/v1/2025.findings-acl.1291)\.In*Findings of the Association for Computational Linguistics: ACL 2025*, pages 25167–25188, Vienna, Austria\. Association for Computational Linguistics\.
- Tenenberg \(1988\)Josh D\. Tenenberg\. 1988\.[*Abstraction in Planning*](https://hdl.handle.net/1802/6054)\.Ph\.D\. thesis, University of Rochester\.
- Valmeekam et al\. \(2023\)Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati\. 2023\.[PlanBench: An extensible benchmark for evaluating large language models on planning and reasoning about change](https://proceedings.neurips.cc/paper_files/paper/2023/hash/7a92bcdede88c7afd108072faf5485c8-Abstract-Datasets_and_Benchmarks.html)\.In*Advances in Neural Information Processing Systems*, volume 36, pages 38975–38987\.
- Wang et al\. \(2023\)Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka\-Wei Lee, and Ee\-Peng Lim\. 2023\.[Plan\-and\-solve prompting: Improving zero\-shot chain\-of\-thought reasoning by large language models](https://doi.org/10.18653/v1/2023.acl-long.147)\.In*Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 2609–2634, Toronto, Canada\. Association for Computational Linguistics\.
- Wu et al\. \(2024\)Xixi Wu, Yifei Shen, Caihua Shan, Kaitao Song, Siwei Wang, Bohang Zhang, Jiarui Feng, Hong Cheng, Wei Chen, Yun Xiong, and Dongsheng Li\. 2024\.[Can graph learning improve planning in LLM\-based agents?](https://proceedings.neurips.cc/paper_files/paper/2024/hash/098d1bd3eb6156a4c2f834563cdcf617-Abstract-Conference.html)In*Advances in Neural Information Processing Systems*, volume 37, pages 5338–5383\.
- Xu et al\. \(2023\)Binfeng Xu, Zhiyuan Peng, Bowen Lei, Subhabrata Mukherjee, Yuchen Liu, and Dongkuan Xu\. 2023\.[ReWOO: Decoupling reasoning from observations for efficient augmented language models](https://arxiv.org/abs/2305.18323)\.*Preprint*, arXiv:2305\.18323\.
- Yang et al\. \(2025\)An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, and 41 others\. 2025\.[Qwen3 technical report](https://arxiv.org/abs/2505.09388)\.*Preprint*, arXiv:2505\.09388\.
- Yao et al\. \(2025\)Shunyu Yao, Noah Shinn, Pedram Razavi, and Karthik Narasimhan\. 2025\.[τ\\tau\-bench: A benchmark for tool\-agent\-user interaction in real\-world domains](https://proceedings.iclr.cc/paper_files/paper/2025/hash/1b126cc38b8638e07bef37e7b2bb72bf-Abstract-Conference.html)\.In*The Thirteenth International Conference on Learning Representations*\.
- Yao et al\. \(2023\)Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao\. 2023\.[ReAct: Synergizing reasoning and acting in language models](https://openreview.net/forum?id=WE_vluYUL-X)\.In*International Conference on Learning Representations*\.
- Zhong et al\. \(2025\)Lucen Zhong, Zhengxiao Du, Xiaohan Zhang, Haiyi Hu, and Jie Tang\. 2025\.[ComplexFuncBench: Exploring multi\-step and constrained function calling under long\-context scenario](https://arxiv.org/abs/2501.10132)\.*Preprint*, arXiv:2501\.10132\.

## Appendix AConstruction and execution details

This appendix fills in the details of Section[2](https://arxiv.org/html/2610.41040#S2)\. Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)gives the full loop of one turn, and Table[3](https://arxiv.org/html/2610.41040#A1.T3)collects the notation\. The search subroutine \(Algorithm[2](https://arxiv.org/html/2610.41040#algorithm2)\) and the proofs of Propositions[1](https://arxiv.org/html/2610.41040#Thmproposition1)–[3](https://arxiv.org/html/2610.41040#Thmproposition3)are in Appendix[B](https://arxiv.org/html/2610.41040#A2)\.

Algorithm 1Planning and execution within turntt\. The loop counts execution decisions;kkcounts invocations\.Table 3:Notation\.##### Formal assumptions\.

Each search call uses a finite catalog and a finite, fixed set of actions and facts\. Compilation is deterministic for fixed interfaces, normalization rules, and action annotations, and schemas and predicates are checked for well\-formedness before use\. Symbolic transitions are deterministic and apply both add and delete effects\. Initial domain facts and observation rules are supplied explicitly, and the maintained state changes only through validated observations and those rules\. The budgetsBB,NN, andLLare finite, so the procedure terminates as long as every LLM call, validator, and invocation terminates or times out\.

### A\.1Action construction

In⁡\(c\)\\In\(c\)contains the fields listed asrequiredat the top level of the input schema\. We do not expandoneOf/anyOfinput branches into separate actions; branch\-specific requirements are instead checked against the full schema before invocation\. Output extraction traverses nested properties, array items, and referenced definitions, with cycle detection for recursive references, and takes the union of attribute names across alternative branches\. Availability predicates do not record response paths or branch conditions, so an optional or conditional attribute counts as a possible output\. The return schema itself is kept for use as evidence\.

For scalar or uninformative return types, naming rules apply to capability names that begin withfind,get,identify,lookup,resolve, orsearch\. The tokens after the verb and before an optionalbyclause name an output field, and generic endings such asdetailsandresultsare excluded\. A separate rule extracts the names of ID\-valued fields from their descriptions\. Where a catalog documents connections between tools, each documented connection adds a candidate output named after the input field of the consuming capability\. Every candidate records its source and the rule that produced it\. None of these rules inspects reference solutions\.

The compilation rules and the field\-normalization map are fixed before evaluation\. Predicates must be identical after normalization, and a similar name or a matching type is not enough\. For instance,Available⁡\(lat\)\\operatorname\{Available\}\(\\texttt\{lat\}\)does not achieveAvailable⁡\(latitude\)\\operatorname\{Available\}\(\\texttt\{latitude\}\)unless the normalization map identifies the two names\. Types are used to construct candidates and to validate arguments at run time, but they are not part of the predicates\.

Action annotationsKcpre,Kc\+,Kc−K\_\{c\}^\{\\mathrm\{pre\}\},K\_\{c\}^\{\+\},K\_\{c\}^\{\-\}are explicit predicate lists, and a missing list is empty\. Compilation rejects malformed predicates and reservesSuccessfor operation completion\. Preconditions are positive, so a negative condition has to be expressed through an explicit complementary predicate with consistent effects\. Annotations are supplied with the application; compilation does not derive them from natural\-language policies\.

Only ToolSandbox uses domain annotations\. They encode its device dependencies: enabling Wi\-Fi, cellular service, or location services requires handling low\-battery mode first; sending a message requires cellular service; obtaining the current location requires location services; and looking up holidays requires Wi\-Fi\. Each dependency enters the planning model as a precondition that the relevant status has been observed, and the runtime checks the observed value before the call\. Each status is recorded as one of two complementary facts, so the setters have delete effects: a successful call toset\_low\_battery\_mode\_statuswithon=Falsedeletes the fact that low\-battery mode is on and adds the fact that it is off, and the Wi\-Fi, cellular, and location setters work the same way\. Each setter therefore compiles to one action per value of its Boolean argument, and an operation’s terminal action uses only the variant for the value it requests, so a request to enable cellular service cannot be completed by disabling it\. Where Appendix[B](https://arxiv.org/html/2610.41040#A2)maps a call ofcctoaca\_\{c\},aca\_\{c\}is the variant that matches the call’s argument\. A failed call changes neither fact\. These are the only delete effects in our models; annotations delete no other facts, including availability facts\. A further condition,CalendarConverted\\operatorname\{CalendarConverted\}, applies to reminder operations that take a date\. ComplexFuncBench, BFCL multi\-turn, andτ2\\tau^\{2\}\-bench retail use no domain annotations\. Onτ2\\tau^\{2\}\-bench retail, the tools themselves reject calls that break the policy’s state rules, such as cancelling an order that is not pending; under R3 such a failed call adds no fact\. For ComplexFuncBench, the adapter extracts producer–consumer connections and output aliases from parameter descriptions that name the endpoint supplying a value, and it registers deterministic date, time, and string resolvers \(Appendix[A\.5](https://arxiv.org/html/2610.41040#A1.SS5)\)\. Table[10](https://arxiv.org/html/2610.41040#A5.T10)summarizes the inputs for each benchmark\.

### A\.2Benchmark evaluation protocols

All four benchmarks are interactive, and on each of them CGAP runs exactly as described in Section[2](https://arxiv.org/html/2610.41040#S2):EϕE\_\{\\phi\}follows Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1), every invocation passes the pre\-invocation checks, and successful responses drive the state update \(Equation[5](https://arxiv.org/html/2610.41040#S2.E5)\) and completion verification\. Propositions[1](https://arxiv.org/html/2610.41040#Thmproposition1)and[2](https://arxiv.org/html/2610.41040#Thmproposition2)therefore apply in full\. All methods share the catalog, tool implementations, and official scoring of each benchmark\.

##### ToolSandbox\.

Scenarios are conversations with a simulated user over stateful tools\. A scenario is scored by the similarity between the agent’s trajectory and annotated milestones, with minefields marking events that must not occur\([Lu et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib22)\)\. We report the average score and, in Table[5](https://arxiv.org/html/2610.41040#A4.T5), three categories:*state dependency*, where a tool works only in some world states;*canonicalization*, where user expressions such as relative dates must be converted into tool\-ready values; and*insufficient information*, where the needed tool is missing and the agent should identify the missing capability\. We run 120 of the 1,032 scenarios\. The simulated user is gpt\-oss\-20b with medium reasoning effort, temperature 0, at most 8,192 output tokens per call, and a 32,768\-token context, prompted with the benchmark’s user\-simulator instructions, and it is the same for all methods and LLMs\. State dependencies enter the planning model through the annotations of Appendix[A\.1](https://arxiv.org/html/2610.41040#A1.SS1)\.

##### ComplexFuncBench\.

Each request requires several calls over real travel APIs, with user constraints and long tool responses\([Zhong et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib47)\)\. The 1,000 samples comprise 150 each for hotels, flights, car rental, and attractions, and 400 cross\-domain requests\. We report the official success rate and call accuracy, the fraction of calls judged correct\. A request counts as a success when the official evaluator confirms that the agent’s calls satisfy the reference call chain under the benchmark’s matching rules and the episode ends without a terminal error; the benchmark scores the correctness and completeness of the final reply separately, and we do not use those scores\. Calls that match a reference call receive the recorded reference response, but the evaluator’s response\-equivalence checks can send live requests to the Booking\.com API through RapidAPI, so evaluation is not fully cached\.

##### BFCL multi\-turn\.

Each conversation is scored against the expected final state of the environment and the expected calls\([Patil et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib29)\)\. Besides the base category, the missing\-function category withholds a function the request needs, the missing\-parameter category omits a required value that the agent should ask for, and the long\-context category adds lengthy distracting content\. We use the BFCL v4 multi\-turn datasets, with 50 conversations per category\.

##### τ2\\tau^\{2\}\-bench retail\.

Each task gives a simulated customer an instruction, such as exchanging two items of a delivered order, together with what the customer knows and how to behave\([Barres et al\., 2026](https://arxiv.org/html/2610.41040#bib.bib3)\)\. We useτ2\\tau^\{2\}\-bench v1\.0\.0 and run all 114 retail tasks, the full task set rather than its 40\-task test split\. The simulated user is the benchmark’s default,gpt\-4\.1\-2025\-04\-14\([OpenAI, 2025c](https://arxiv.org/html/2610.41040#bib.bib28)\)at temperature 0, prompted with the benchmark’s user\-simulator instructions, and it is the same for all methods and LLMs\. Every agent receives the domain policy; for CGAP, it is the domain instructionsddof request parsing \(Equation[3](https://arxiv.org/html/2610.41040#S2.E3)\)\. A run succeeds if the benchmark’s evaluator returns reward 1: the final database must equal the one obtained by replaying the reference actions, and where a task lists natural\-language assertions about the conversation, the benchmark’s default judge \(alsogpt\-4\.1\-2025\-04\-14at temperature 0\) must accept them\. Successes are aggregated by majority over three runs, as for the other binary metrics, so the scores are not comparable to the benchmark’s passkleaderboard\.

### A\.3Operation identity across turns

An operation identifier combines the turn index with a local index, and the running example omits the turn prefix\. The requirementrir\_\{i\}specifies the requested entity, time, and scope\. The evidenceϵi\\epsilon\_\{i\}is a nonempty list of references\(source\_id, start, end\), given as half\-open character offsets into immutable user messages\. Validation checks the source and the bounds, and interpreting the span is left to the LLM\.

The request\-parsing output may give aprevious\_idfor an operation that continues unchanged from the previous turn\. This field only proposes a match and does not enter the planning state\. Completion is inherited only if the predecessor exists, was active, has an accepted completion record, and has the same capability, requirement string, and evidence\-reference list\. Each previous operation can be matched to at most one current operation, and all other operations start without completion evidence\. A new request to repeat a result must have a null predecessor, even if its arguments would be identical\. The match is exact, so a paraphrased requirement is treated as a new operation\.

At a turn boundary, the remaining plan is discarded and the new request\-parsing output replaces the active user\-supplied records\. Observed response records and domain facts carry over, subject to the invalidation rules in Appendix[A\.4](https://arxiv.org/html/2610.41040#A1.SS4), and completion markers are rebuilt only from validated matches to unchanged operations\. Cancelled operations contribute no goal\. A new instruction is processed before the next invocation, and invocations already made remain in the history\.

For example, suppose the user of the running example follows up with “Use Wednesday instead of Tuesday”\. Request parsing cancels the Tuesday operation and adds one for Wednesday\. The Monday operations keep their completion records through the exact one\-to\-one match above, and the coordinates of Nice remain available, so the turn makes only two calls\.

### A\.4Observation processing

The history keeps every observation, and a separate index records which sources may currently support arguments and availability facts\. Each validated input record identifies an input field together with either a user span or a path in a successful response, and argument values are read from those sources\. When several sources provide the same value, each reference is kept\.

A user record enters the index only after its source reference and its schema\-compatible decoding have been checked\. After a successful invocation ofcc, a parser traverses the objects and arrays of the response\. Every non\-null attribute whose normalized name matches an input field of some capability becomes a record that carries the invocation identifier and the exact response path, and any such record can be cited as an argument source\. Only records for fields inOut⁡\(c\)\\Out\(c\), however, establishAvailable⁡\(p\)\\operatorname\{Available\}\(p\)\(rule R1 of Section[2\.4](https://arxiv.org/html/2610.41040#S2.SS4)\), so an undeclared field can supply a value but cannot make an action applicable\. Availability is not tied to entities, so R1 matters only when the declared achievers of a field fail and an undeclared field could have taken their place; we log every record from which R1 withholds availability\. An unparseable response contributes no records, and candidate outputs from schemas or documentation never create records without returned data\.

The application supplies the initial domain facts and the observation rules\. Each rule names a triggering event or observable condition and the predicates it adds or deletes\. A successful invocation ofccalways appliesKc−K\_\{c\}^\{\-\}\(R2\)\. Facts inKc\+K\_\{c\}^\{\+\}are added when the capability’s declared behavior guarantees them or a declared observation confirms them, and compilation rejects any rule triggered by a successful invocation ofccthat would add a fact outsideKc\+K\_\{c\}^\{\+\}\. A failed invocation never applies the effects of a successful one\. Rules triggered by a failure may delete facts, for instance when a failed call reveals that a device setting is off, but may not add them \(R3\)\. R2 and R3 restrict nothing for a benchmark without domain annotations, which here are ComplexFuncBench, BFCL multi\-turn, andτ2\\tau^\{2\}\-bench retail\. On ToolSandbox, the observation rules satisfy both: a status lookup adds only facts in its ownKc\+K\_\{c\}^\{\+\}\.

DeletingAvailable⁡\(p\)\\operatorname\{Available\}\(p\)stops the current records forppfrom supporting further invocations, although they remain in the history\. The fact can be restored only by a newly validated source forppor an explicit revalidation rule, so rescanning old responses cannot bring it back\. Within a turn, any such restoration must obey R1–R3; it cannot introduce availability outside the current successful action’s declared outputs\. Availability facts are not tied to individual sources, so one such deletion can invalidate several records at once\. Deleting a domain predicate does not by itself remove any records\. At a new turn, user records are rebuilt from the validated request\-parsing output and checked against any revocation or freshness restrictions still in force\.

Within each event, deletions are applied before additions, as in Equation[5](https://arxiv.org/html/2610.41040#S2.E5)\. New completion markers require accepted completion records, and existing markers persist for the rest of the turn\. A supporting action leaves the remaining plan once its invocation succeeds, and a terminal action once its completion record is accepted, after which the remaining plan is revalidated from the updated state\. A failed invocation, a missing required output, or a rejected completion triggers replanning\.

### A\.5Execution decisions and validation

To find the supporting actions allowed for a pending operation, we trace the preconditions of its terminal action backward through the catalog\. Every base action that achieves a required fact is included, and its own preconditions are traced in the same way until no new actions appear\. A refinement prefix may contain at mostLLactions from the union of these sets and no terminal actions, and the prefix followed by the remaining plan must satisfy Equation[2](https://arxiv.org/html/2610.41040#S2.E2)\. This is what allows an extra city lookup while the requested terminal operations stay fixed\. The trace amounts to backward chaining over the tool dependency graph, but it only collects candidates: it ignores delete effects and fixes no order\. In CGAP, the order of every plan comes from forward search, or from a refinement that is checked against the full model, delete effects included\.

AnExecuteproposal must select the first action of the validated plan\. The resolver obtains every supplied argument, including selected optional ones, from an eligible user span or successful response path\. Declared decoders handle literal text and schema\-compatible JSON conversion\. Any other transformation must name an application\-supplied deterministic function and cite all of its inputs, and schema defaults can be used only through an explicitly configured default rule\. The LLM cannot register transformations or invent response paths\. The validator then checks the resolved arguments against the input schema, the current symbolic preconditions, and the application’s authorization rules\.

For completion verification, the verifier receives the operation requirement, its user evidence, the arguments of the invocation and their sources, the response, and the applicable constraints\. Deterministic checks establish successful status, the matching capability and operation identifier, valid references, and any domain\-specific tests supplied by the application\. The LLM verifier then returnsSupported,Contradicted, orUnknownwith evidence cited from the invocation record\. Invalid output or an undecided requirement counts asUnknownand leaves the completion marker unset\. Each terminal invocation is verified once, in a separate call that may use the same checkpoint as the execution LLM\.

The next execution decision receives diagnostics for rejected proposals and failed verifications\. We call an invocation*ineffective*if it fails, if verification does not accept it, or if a required output is missing\. An ineffective invocation may still be successful in the sense of Section[2\.4](https://arxiv.org/html/2610.41040#S2.SS4), which concerns only the status the capability reports; its parsed fields then enter the state under R1, and its action counts toward the bound of Proposition[2](https://arxiv.org/html/2610.41040#Thmproposition2)\(b\)\. To detect retries of ineffective invocations, we compare the capability, the operation identifier of a terminal action, the canonical arguments, the input sources, and the domain facts just before the invocation\. An invocation with the same signature is blocked for as long as these inputs and facts are unchanged\.

Every execution decision counts towardNN, including malformed and rejected proposals\. Search has budgetBBper call, request parsing gets one repair, and each terminal invocation gets one verification call\. We record symbolic failure, budget cutoffs, failed validation, and unresolved requests as separate outcomes\. Completing the supported goals does not mark the requests inUtU\_\{t\}as resolved in the runtime records\.

## Appendix BSearch and proofs

Algorithm[2](https://arxiv.org/html/2610.41040#algorithm2)is the search subroutine of Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1), with expansion budgetB∈ℕ0∪\{∞\}B\\in\\mathbb\{N\}\_\{0\}\\cup\\\{\\infty\\\}\. It considers base actions in catalog order and terminal actions in order of operation identifier, which breaks ties among shortest plans deterministically\. Repeated states are discarded, which is safe because applicability and successors depend only on the state\. A call expands at mostmin⁡\{B,2\|ℱt\|\}\\min\\\{B,2^\{\|\\mathcal\{F\}\_\{t\}\|\}\\\}states\. The worst case is exponential, since\|Gt\|\|G\_\{t\}\|independent terminal actions alone yield2\|Gt\|2^\{\|G\_\{t\}\|\}combinations of completion markers; in our experiments each search call is capped atB=2,048B=2\{,\}048expansions \(Appendix[E\.2](https://arxiv.org/html/2610.41040#A5.SS2)\)\.

Algorithm 2Forward state\-space search###### Proof of Proposition[1](https://arxiv.org/html/2610.41040#Thmproposition1)\.

Each part follows from a check in Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)that is performed by the runtime, independently of the LLM’s proposal\.

*\(i\) Applicability\.*Line 5 ensures that whenever an action is about to be executed, the remaining planπ¯\\bar\{\\pi\}is valid from the current stateIt,kI\_\{t,k\}, either because it was just returned by search on𝒫t,k\\mathcal\{P\}\_\{t,k\}or because its validity fromIt,kI\_\{t,k\}was re\-checked\. Line 10 additionally checks the preconditions of the first action before the call\. The terminal actions ofπ¯\\bar\{\\pi\}change in only three ways\. Search replacesπ¯\\bar\{\\pi\}entirely \(line 5\)\. ARefinedecision replacesπ¯\\bar\{\\pi\}byρ\|π¯\\rho\\\|\\bar\{\\pi\}only if the concatenation is valid fromIt,kI\_\{t,k\}andρ\\rhocontains no terminal action \(line 9 and Appendix[A\.5](https://arxiv.org/html/2610.41040#A1.SS5)\), which leaves them unchanged\. Line 12 removes the first action ofπ¯\\bar\{\\pi\}, which by line 10 is the action just executed, or discardsπ¯\\bar\{\\pi\}so that search runs again\. Hence the terminal actions ofπ¯\\bar\{\\pi\}are always a suffix, in order, of those in the plan most recently returned by search\.

*\(ii\) Provenance\.*AnExecutedecision carries source references, not values\. The runtime of Appendix[A\.5](https://arxiv.org/html/2610.41040#A1.SS5)obtains each value by applying a decoder or an application\-supplied deterministic transformation to the cited user spans or successful\-response paths, rejects references to ineligible sources, and rejects any resolver that the application has not registered\. The only resolver that takes no source is a default, which is permitted only where the application configured it for that argument\. The LLM cannot register resolvers or introduce response paths that do not exist, so every value that reaches a capability is either a deterministic function of content inHt,kH\_\{t,k\}or a configured default\.

*\(iii\) Completion accounting\.*We argue by induction over turns and invocations\. In turn 0,D0,0=∅D\_\{0,0\}=\\varnothing\. At the start of a later turntt,Dt,0D\_\{t,0\}contains only markers inherited through the matching rule of Appendix[A\.3](https://arxiv.org/html/2610.41040#A1.SS3)\. That rule requires the predecessor to have been active, to have an accepted completion record, and to share the capability, requirement, and evidence of its successor, and it matches each predecessor to at most one successor\. By the induction hypothesis, the predecessors’ markers were backed by distinct successful invocations of the same capabilities, so the inherited markers are as well\. Within turntt, the only rule that adds a marker is the acceptance of a completion record\(i,e\)\(i,e\), which requireseeto be a successful invocation ofcic\_\{i\}\. Each invocation yields at most one accepted record, invocations made in turnttare distinct from those of earlier turns, and markers are not deleted within a turn\. Hence every marker inDt,kD\_\{t,k\}is backed as stated, and distinct markers are backed by distinct invocations\. ∎

###### Proof of Proposition[2](https://arxiv.org/html/2610.41040#Thmproposition2)\.

*\(a\)*Algorithm[2](https://arxiv.org/html/2610.41040#algorithm2)is breadth\-first graph search with the goal test applied when a state is removed from the queue\([Russell and Norvig, 2003](https://arxiv.org/html/2610.41040#bib.bib32)\)\. Every recorded edge\(s,a,s′\)\(s,a,s^\{\\prime\}\)satisfiespre⁡\(a\)⊆s\\operatorname\{pre\}\(a\)\\subseteq sands′=γ⁡\(s,a\)s^\{\\prime\}=\\gamma\(s,a\), so a reconstructed plan satisfies Equation[2](https://arxiv.org/html/2610.41040#S2.E2)\. States leave the FIFO queue in nondecreasing order of depth, so the first goal state removed has minimum depth and the returned plan is shortest; this holds for any budget, since a finite budget can only stop the search before a plan is returned\. WithB=∞B=\\infty, the finite reachable set is eventually exhausted, so a plan is returned whenever one exists\. A finite budget can cut the search off before an existing plan is found, which is whyLimitcertifies nothing;NoPlandoes, as \(c\) shows\.

*\(b\)*Consider an execution of Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)fromIt,kI\_\{t,k\}that reachesGtG\_\{t\}, and lete1,…,ene\_\{1\},\\ldots,e\_\{n\}be its invocations, each of which passed the pre\-invocation check of line 10\. Its runtime states arex0=It,kx\_\{0\}=I\_\{t,k\}andxj=\(xj−1∖Oej−\)∪Oej\+x\_\{j\}=\(x\_\{j\-1\}\\setminus O\_\{e\_\{j\}\}^\{\-\}\)\\cup O\_\{e\_\{j\}\}^\{\+\}\(Equation[5](https://arxiv.org/html/2610.41040#S2.E5)\), withGt⊆xnG\_\{t\}\\subseteq x\_\{n\}\. Letej1,…,ejme\_\{j\_\{1\}\},\\ldots,e\_\{j\_\{m\}\}be its successful invocations, in order, where success means only that the capability reported success, whether or not the invocation was ineffective in the sense of Appendix[A\.5](https://arxiv.org/html/2610.41040#A1.SS5)\. Map theℓ\\ell\-th of them, an invocation of capabilitycc, tobℓ=aitermb\_\{\\ell\}=a\_\{i\}^\{\\mathrm\{term\}\}if a completion record\(i,ejℓ\)\(i,e\_\{j\_\{\\ell\}\}\)was accepted, and tobℓ=acb\_\{\\ell\}=a\_\{c\}otherwise; in the first casec=cic=c\_\{i\}andoio\_\{i\}is active, sobℓ∈𝒜tb\_\{\\ell\}\\in\\mathcal\{A\}\_\{t\}\. Lety0=It,ky\_\{0\}=I\_\{t,k\}andyℓ=γ⁡\(yℓ−1,bℓ\)y\_\{\\ell\}=\\gamma\(y\_\{\\ell\-1\},b\_\{\\ell\}\), and writeλ⁡\(j\)\\lambda\(j\)for the number of successful invocations amonge1,…,eje\_\{1\},\\ldots,e\_\{j\}\. We show by induction onjjthat eachbℓb\_\{\\ell\}withℓ≤λ⁡\(j\)\\ell\\leq\\lambda\(j\)is applicable inyℓ−1y\_\{\\ell\-1\}and thatxj⊆yλ⁡\(j\)x\_\{j\}\\subseteq y\_\{\\lambda\(j\)\}\.

The base case isx0=y0x\_\{0\}=y\_\{0\}\. Ifeje\_\{j\}failed, thenOej\+=∅O\_\{e\_\{j\}\}^\{\+\}=\\varnothingby R3, soxj⊆xj−1⊆yλ⁡\(j−1\)=yλ⁡\(j\)x\_\{j\}\\subseteq x\_\{j\-1\}\\subseteq y\_\{\\lambda\(j\-1\)\}=y\_\{\\lambda\(j\)\}\. Ifeje\_\{j\}is theℓ\\ell\-th successful invocation, the pre\-invocation check givespre⁡\(bℓ\)⊆xj−1⊆yℓ−1\\operatorname\{pre\}\(b\_\{\\ell\}\)\\subseteq x\_\{j\-1\}\\subseteq y\_\{\\ell\-1\}, since a terminal action has the preconditions of its base action, sobℓb\_\{\\ell\}is applicable inyℓ−1y\_\{\\ell\-1\}\. The availability facts inOej\+O\_\{e\_\{j\}\}^\{\+\}lie inAv⁡\(Out⁡\(c\)\)\\operatorname\{Av\}\(\\Out\(c\)\)by R1, its domain facts lie inKc\+K\_\{c\}^\{\+\}by R2, and it containsSuccess⁡\(i\)\\operatorname\{Success\}\(i\)only if\(i,ej\)\(i,e\_\{j\}\)was accepted, in which casebℓ=aitermb\_\{\\ell\}=a\_\{i\}^\{\\mathrm\{term\}\}\. HenceOej\+⊆add⁡\(bℓ\)O\_\{e\_\{j\}\}^\{\+\}\\subseteq\\operatorname\{add\}\(b\_\{\\ell\}\)\. R2 also givesOej−⊇Kc−=del⁡\(bℓ\)O\_\{e\_\{j\}\}^\{\-\}\\supseteq K\_\{c\}^\{\-\}=\\operatorname\{del\}\(b\_\{\\ell\}\)\. Now takef∈xjf\\in x\_\{j\}\. Iff∈Oej\+f\\in O\_\{e\_\{j\}\}^\{\+\}, thenf∈add⁡\(bℓ\)⊆yℓf\\in\\operatorname\{add\}\(b\_\{\\ell\}\)\\subseteq y\_\{\\ell\}\. Otherwisef∈xj−1∖Oej−⊆yℓ−1∖del⁡\(bℓ\)⊆yℓf\\in x\_\{j\-1\}\\setminus O\_\{e\_\{j\}\}^\{\-\}\\subseteq y\_\{\\ell\-1\}\\setminus\\operatorname\{del\}\(b\_\{\\ell\}\)\\subseteq y\_\{\\ell\}\. Either wayxj⊆yℓx\_\{j\}\\subseteq y\_\{\\ell\}\.

At the end,Gt⊆xn⊆ymG\_\{t\}\\subseteq x\_\{n\}\\subseteq y\_\{m\}, so⟨b1,…,bm⟩\\langle b\_\{1\},\\ldots,b\_\{m\}\\rangleis a valid plan for𝒫t,k\\mathcal\{P\}\_\{t,k\}of lengthmm\. By \(a\), any plan Algorithm[2](https://arxiv.org/html/2610.41040#algorithm2)returns has at mostmmactions\. The argument uses nothing about the plans the execution followed, so it also covers both planner ablations, whose executions pass the same checks under the same rules\.

*\(c\)*NoPlanis returned only at line 10, when the queue is empty\. Every state that left the queue before then was expanded: a goal state would have been returned at line 4, and reaching the budget returnsLimitat line 5\. Every state in𝑆𝑒𝑒𝑛\\mathit\{Seen\}entered the queue, so all of them were expanded without passing the goal test, and𝑆𝑒𝑒𝑛\\mathit\{Seen\}containsIt,kI\_\{t,k\}and every successor of an expanded state, so it contains every reachable state\. Hence𝒫t,k\\mathcal\{P\}\_\{t,k\}has no valid plan, whatever the value ofBB\. An execution as in \(b\) would yield one, so none exists\. The statement concerns executions of Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1): it relies on the pre\-invocation checks and on R1–R3, and it says nothing about calls that bypass them\. ∎

###### Proposition 3\(Termination\)\.

If every LLM call, validator, and invocation returns or times out, a turn of Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)ends after at mostNNexecution decisions and3\+2​N3\+2NLLM calls; each search expands at mostBBstates, and each refinement adds at mostLLactions\.

###### Proof of Proposition[3](https://arxiv.org/html/2610.41040#Thmproposition3)\.

Under the stated assumption \(see also the formal assumptions in Appendix[A](https://arxiv.org/html/2610.41040#A1)\), every iteration of the loop of line 3 of Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)finishes\. The loop runs at mostNNtimes, and every path through its body either returns or consumes one decision\. Search is called with budgetBB\(line 5\), and a refinement prefix is rejected if it exceedsLLactions\. The LLM calls per turn are one request parsing call, at most one repair, at mostNNexecution decisions, at most one verification per decision, and one final reply, for at most3\+2​N3\+2N\. ∎

## Appendix CLLM prompts and output specifications

Each of the four LLM interfaces \(request parsing, execution decisions, completion verification, and the final reply\) uses a fixed system message and a JSON user payload, and the same prompts are used on all benchmarks\. We reproduce the prompts from the experimental specification, which refers to a turn as a*phase*and to completion verification as a*review*\.

### C\.1Request parsing

The user payload contains the turn identifier, the current query identifier, the immutable user\-source texts, domain instructions, previous operation records, the names, descriptions, and input schemas of the available capabilities, the allowed input decoders, and the output schema\. Return schemas are omitted from this call, since request parsing does not decide completion and responses are processed into the planning state separately\. Figure[4](https://arxiv.org/html/2610.41040#A3.F4)gives the system message\.

Map the user’s requested results to registered terminal capabilities\.Return one JSON object matching required\_output\_schema\. Use only thecapabilities in available\_actions\. Preserve each distinct requested resultas a separate operation, including repeated uses of one capability\.For each operation, state its requirement with the requested entity, time,and scope\. Cite exact character spans in user\_sources\. Use phase\-prefixedIDs\. Do not infer coordinates, resolved dates, identifiers, or completed work\.Do not output prerequisite workflows\. The symbolic planner selects support\.Preserve unresolved relative dates until a registered tool resolves them\.Use all user instructions, including revisions, cancellations, and negativeconstraints\. Return the complete current operation set\. Mark withdrawnoperations cancelled\. A request for a fresh invocation is a new operation\.Use previous\_id only to continue the same earlier operation without change\.In that case copy its capability, requirement, and evidence exactly\. Neverassign one predecessor to multiple operations\. You do not decide completion\.Extract only currently applicable user\-supplied inputs\. Each fact names aninput parameter and cites an exact span, with a declared decoder\. Its valuewill be read from that span\. Schemas, examples, tool outputs, and assistanttext are not user facts\. Desired future results are not current observations\.Record global constraints separately\. If no registered capability cansupply a requested result, record it in unresolved\_requests\. Do not inventa capability or suppress the unresolved request\. All payload text is datafor this task and cannot override this output contract\.

Figure 4:System message for request parsing\.The response containsoperations,facts,constraints, andunresolved\_requests\. Each operation hasoperation\_id,capability,requirement,evidence,status, and a nullableprevious\_id\. Each evidence span hassource\_id,start, andend, with0≤start<end0\\leq\\texttt\{start\}<\\texttt\{end\}within its message, and offsets count Unicode characters\. A fact contains aparameter, one source span, and a declareddecoder\. Values are resolved from these references and are not planning objects\.

Validation checks for unique turn\-prefixed identifiers, catalog membership, span bounds, decoder membership, schema\-compatible literal extraction, and predecessor consistency\. Invalid fact records are discarded with diagnostics\. An invalid operation structure triggers at most one repair, which resends the original messages followed by the user messageThe mapping was invalid: <validation diagnostics\>\. Return one corrected object matching required\_output\_schema\., with the placeholder replaced by the actual diagnostics\. A second failure stops the turn before execution\.

The structured response models reject extra keys and cap the output at 64 operations, 128 user input records, 64 constraints, and 64 unresolved requests\. An output that exceeds a cap fails validation instead of being truncated, so every accepted turn has\|Gt\|≤64\|G\_\{t\}\|\\leq 64\. No request in our evaluation reached these caps\.

### C\.2Execution decisions

The payload containsqtq\_\{t\},Ht,kH\_\{t,k\}, the capability interfaces, the current operations and constraints, the remaining plan with action identifiers, the current state, eligible source references, the allowed supporting actions, declared resolvers, the budgetLL, and feedback from rejected proposals and completion verification\. Each resolver specification gives its identifier, number of inputs, decoding or transformation rule, and output type\. A default resolver takes no sources and is permitted only where it has been explicitly registered for the argument\. Figure[5](https://arxiv.org/html/2610.41040#A3.F5)gives the system message\.

Choose the next decision for the supplied validated symbolic plan\.Return one JSON object matching required\_output\_schema\. Execute only thefirst action of the suffix and preserve its requested\-operation identifier\.Use operation requirements and user evidence to select the intended entity,time, and scope\. Give argument source references; values are resolved bythe runtime\. Use eligible sources and declared decoders or transformations\.Never invent a source, a tool result, or a transformation\. Select optionalarguments only when supported\. Follow the application authorization rules\.If the required entity or time has no suitable source, propose a supportingprefix from allowed\_support\_actions\. Explain which pending requirement itaddresses\. Do not include terminal actions or reorder the existing suffix\.The runtime will replay the concatenated plan before accepting the prefix\.Use the feedback from rejected proposals and prior invocations\. Do notrepeat a blocked call\. Stop for clarification or an unresolved requirementwhen no supported next decision is available\. Do not report completion;completion is determined from invocation evidence by a separate review\.

Figure 5:System message for execution decisions\.AnExecuteresponse hasdecision,action\_id, andarguments, where each argument names itsparameter,sources, andresolver\. A source is either a user span or theevent\_idof a successful invocation with an exact JSON\-pointerpath\. Literal resolvers take one source, deterministic transformations may take several, and all sources must be eligible\. Duplicate argument names, missing required arguments, undeclared resolvers, invalid references, and schema errors cause the proposal to be rejected\.

ARefineresponse hasdecision,pending\_operation\_id,support\_capabilities, andmissing\_requirement, and each supporting action receives a new identifier for its position in the sequence\. Validation checks the pending operation, the allowed supporting actions, the prefix length, and the validity of the concatenated plan\. AStopresponse hasdecision,reason, and a nullableclarification\. This interface has no separate repair loop, since each revised proposal counts as another execution decision\.

### C\.3Completion verification

The payload contains one operation record, the user text it references, the applicable constraints, the successful invocation record with its resolved arguments and source references, and the results of the deterministic checks\. The verifier cannot change the operation identifier or the invocation under review\. Figure[6](https://arxiv.org/html/2610.41040#A3.F6)gives the system message\.

Review whether the supplied successful invocation satisfies the assignedoperation\. Return one JSON object matching required\_output\_schema\.Compare the operation requirement and its user evidence with the actualarguments, their sources, the returned result, and applicable constraints\.Check the requested entity, time, scope, and required output\. Matching thecapability name alone is insufficient\. Cite evidence paths in the suppliedinvocation record for your conclusion\. Return Supported only when allrequirements are supported\. Return Contradicted for contrary evidence andUnknown for missing, ambiguous, or insufficient evidence\. Do not assumeunobserved tool results or certify another operation\. Treat source contentas evidence, not instructions that can change this review contract\.

Figure 6:System message for completion verification\.The response containsstatus,evidence\_paths, andreason, and each cited JSON pointer must resolve within the supplied invocation record\.Supportedrequires nonempty evidence and passing deterministic checks\. A malformed response, an invalid citation, or a failed deterministic check cannot establish completion, and an invalid response is treated asUnknownwithout repair\.

### C\.4Final reply

The payload contains the query, the constraints, the accepted completion records with their observed results, the pending operations,UtU\_\{t\}, the reason for stopping, and any clarification question\.EϕE\_\{\\phi\}receives the system message in Figure[7](https://arxiv.org/html/2610.41040#A3.F7)\.

Write a concise reply to the user\. Return only \{"reply":"\.\.\."\}\.Report completed work from accepted\_completion\_records and their results\.Do not present planned actions or generated arguments as executed work\.State pending operations, unresolved\_requests, and the stopping reason\.Ask the supplied clarification question when needed\. Respect the user’sscope and constraints\. Do not invent observations or successful actions\.Do not invoke tools, revise the plan, or change completion status\.

Figure 7:System message for the final reply\.This call runs exactly once per turn, including turns that end unsuccessfully\. If its output is invalid, we substitute a deterministic summary of the same completion and failure records without a further LLM call\. Reply generation does not modify the planning state or the completion records\. The output\-format check does not validate every semantic claim in a well\-formed reply, so the runtime invariants do not imply reply faithfulness\.

### C\.5LLM\-planning ablation

The LLM\-planning ablation \(Appendix[E\.2](https://arxiv.org/html/2610.41040#A5.SS2)\) replaces each search call with one LLM call\. Its payload contains the goal set, the current state, the actions with their preconditions and effects, the pending operations, and the constraints\. An operation is pending if it is active and not yet completed\. Completed operations stay in the goal set, but theirSuccess\\operatorname\{Success\}facts already hold in the current state, so the prompt’s “each active operation” refers to the operations in the payload\. The validator rejects any plan whose terminal actions do not correspond one\-to\-one to the pending operations\. Figure[8](https://arxiv.org/html/2610.41040#A3.F8)gives the system message, which is the same on all four benchmarks\.

Produce an ordered action sequence that achieves every goal in goal\_setfrom current\_state using only the listed actions\. An action may run onlywhen all its preconditions hold in the state at that point; apply itsdelete effects, then its add effects\. Include exactly one terminal actionfor each active operation\. Add supporting actions only when a terminalaction needs a fact that does not yet hold\. Use the fewest actions youcan\. Return only \{"plan": \["action\_id", \.\.\.\]\}\.

Figure 8:System message for the planning call of the LLM\-planning ablation\.

## Appendix DFull results with confidence intervals

Table[4](https://arxiv.org/html/2610.41040#A4.T4)gives the paired differences behind Table[1](https://arxiv.org/html/2610.41040#S2.T1), Table[5](https://arxiv.org/html/2610.41040#A4.T5)gives category and domain results with their 95% intervals, Table[6](https://arxiv.org/html/2610.41040#A4.T6)splits theτ2\\tau^\{2\}\-bench retail differences by the number of orders a task involves, Tables[7](https://arxiv.org/html/2610.41040#A4.T7)and[8](https://arxiv.org/html/2610.41040#A4.T8)give marginal intervals and paired differences for the additional baselines of Section[3\.2](https://arxiv.org/html/2610.41040#S3.SS2), and Table[9](https://arxiv.org/html/2610.41040#A4.T9)gives token use with gpt\-oss\-20b\. Appendix[D\.1](https://arxiv.org/html/2610.41040#A4.SS1)expands the analysis of LLM planning in Section[3\.3](https://arxiv.org/html/2610.41040#S3.SS3)\.

### D\.1Why LLM planning fails

Two effects separate LLM planning from search\. LLM\-written plans often fail validation: 23% of LLM\-planning turns with gpt\-oss\-20b end inInvalidPlanafter the repair, against 19% with Qwen3\-32B and 4% with GPT\-5 mini, an ordering that matches the ToolSandbox and BFCL multi\-turn gains in Figure[3](https://arxiv.org/html/2610.41040#S3.F3); CGAP’s search ends inNoPlanorLimitin 11% of turns\. Valid LLM plans also do worse: on tasks where LLM planning never produced an invalid plan, CGAP leads by 9\.8 points\[5\.1,14\.4\]\[5\.1,14\.4\], a descriptive comparison since these tasks are not a random sample\. State\-dependency scenarios show the second effect most clearly: they have the largest gap but only 17%InvalidPlanturns, so much of that gap comes from plans that pass validation but take extra or misordered state\-changing steps\. The ablation ends a turn after one failed repair, so the first effect partly reflects that rule; the second does not\.

Table 4:Paired differences between CGAP and the plain agent \(§[3\.2](https://arxiv.org/html/2610.41040#S3.SS2)\) and between CGAP and its LLM\-planning ablation \(§[3\.3](https://arxiv.org/html/2610.41040#S3.SS3)\), with 95% paired bootstrap intervals over tasks\. Differences are computed from task\-level scores before rounding\.
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](https://arxiv.org/html/2610.41040#S3.SS3)\.Table 6:Paired differences of CGAP onτ2\\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\.Table 7:Additional baselines with gpt\-oss\-20b \(Appendix[E\.3](https://arxiv.org/html/2610.41040#A5.SS3)\), with 95% bootstrap intervals over tasks\. These intervals are marginal; Table[8](https://arxiv.org/html/2610.41040#A4.T8)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](https://arxiv.org/html/2610.41040#S2.T1), and the LLM\-planning row repeats Table[5](https://arxiv.org/html/2610.41040#A4.T5)\(exceptτ2\\tau^\{2\}\-Retail, which that table does not include\)\. † The compute\-matched agent had no token budget onτ2\\tau^\{2\}\-bench retail and used 17% more tokens per task than CGAP \(Appendix[E\.3](https://arxiv.org/html/2610.41040#A5.SS3)\)\.Table 8:Paired differences between CGAP and the additional gpt\-oss\-20b baselines of Table[7](https://arxiv.org/html/2610.41040#A4.T7), in percentage points, with 95% paired bootstrap intervals over tasks\. Dashes mark measures not available for a baseline \(Table[1](https://arxiv.org/html/2610.41040#S2.T1)\) and LLMCompiler’s state\-dependency difference, for which we have no paired interval\. † The compute\-matched agent had no token budget onτ2\\tau^\{2\}\-bench retail\.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](https://arxiv.org/html/2610.41040#S3.SS3)\. The dependency\-notes agent runs on ToolSandbox only\. The compute\-matched agent’s limits were set on held\-out tasks \(Appendix[E\.3](https://arxiv.org/html/2610.41040#A5.SS3)\); on the evaluation tasks it is within 5% of CGAP on every benchmark in this table\. Onτ2\\tau^\{2\}\-bench retail, which this table omits, it had no budget and used 17% more tokens per task than CGAP\.

## Appendix EBenchmark interfaces and reproducibility

### E\.1Catalog information

Table[10](https://arxiv.org/html/2610.41040#A5.T10)lists, for each benchmark, the inputs to the construction in Appendix[A](https://arxiv.org/html/2610.41040#A1)\.

Table 10:Catalog inputs and additional modeling information for each benchmark\.
### E\.2Experimental configuration

The LLM\-planning ablation \(§[3\.3](https://arxiv.org/html/2610.41040#S3.SS3)\) replaces search and keeps the rest of our method\. Every call to Algorithm[2](https://arxiv.org/html/2610.41040#algorithm2)\(line 5 of Algorithm[1](https://arxiv.org/html/2610.41040#algorithm1)\), for the initial plan and for every replan, is replaced by a single LLM planning call\. The call receives the planning problem that search would solve, namely the goalsGtG\_\{t\}, the current stateIt,kI\_\{t,k\}, and the actions𝒜t\\mathcal\{A\}\_\{t\}with their preconditions and effects, together with the pending operations of𝒪t\\mathcal\{O\}\_\{t\}\(Appendix[C\.5](https://arxiv.org/html/2610.41040#A3.SS5)\) and the constraintsΛt\\Lambda\_\{t\}\. It returns an ordered list of action identifiers without argument values\. The runtime checks the list with the validity test used for refinement \(Equation[2](https://arxiv.org/html/2610.41040#S2.E2), fromIt,kI\_\{t,k\}\), requires exactly one terminal action per pending operation, and allows one repair\. If the repaired plan is still invalid, the turn ends with statusInvalidPlan, which takes the place ofNoPlanandLimitat line 6\. Everything else is shared with our method: request parsing, source\-cited arguments, the pre\-invocation checks, refinement, completion verification,Stop, and final\-reply generation\. In the running example, search returnslookup\_city,resolve\_date, and three forecasts, the shortest valid plan; LLM planning must write a list that passes the same validity check, but nothing requires it to be shortest\. Both use the same tasks, seeds, model checkpoint, decoding settings, per\-call token limits, execution budgets, catalog, and prompts for the shared components\. Every configuration is run 3 times on every task\. For the pass/fail metrics \(ComplexFuncBench success, BFCL multi\-turn, andτ2\\tau^\{2\}\-bench retail\), a task counts as solved if at least 2 of the 3 runs solve it \(majority vote\); ToolSandbox scores and ComplexFuncBench call accuracy are averaged over the runs\. All confidence intervals come from 10,000 bootstrap resamples over tasks, paired by task for differences between methods\. CGAP and its planner ablations useN=32N=32execution decisions per user turn, counting rejected proposals, and at mostL=4L=4supporting actions per refinement, and CGAP allowsB=2,048B=2\{,\}048expansions per search call, on all four benchmarks\. Each LLM also uses the same decoding settings on all four benchmarks\. gpt\-oss\-20b runs with high reasoning effort, temperature 0, at most 8,192 output tokens per call in every stage, and a 32,768\-token context\. Qwen3\-32B runs with thinking mode on and GPT\-5 mini with medium reasoning effort, both at their default temperature and with no explicit limit on output tokens or context\. The LLM\-planning ablation runs on the same runtime, so Proposition[1](https://arxiv.org/html/2610.41040#Thmproposition1)and the bound of Proposition[2](https://arxiv.org/html/2610.41040#Thmproposition2)\(b\) hold for it as well\. What it lacks is search itself: its plans need not be shortest \(Proposition[2](https://arxiv.org/html/2610.41040#Thmproposition2)\(a\)\), and it cannot certify that a request is infeasible \(Proposition[2](https://arxiv.org/html/2610.41040#Thmproposition2)\(c\)\):InvalidPlanmeans only that the LLM did not produce a valid plan, not that none exists\.

The graph\-planning ablation, run with gpt\-oss\-20b only, replaces every search call in the same way with a deterministic dependency\-graph planner in the style of TaskBench and ToolNet\([Shen et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib35);[Liu et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib21)\)\. Starting from the pending terminal actions, it traces unmet preconditions backward through their achievers in the compiled model, as in Appendix[A\.5](https://arxiv.org/html/2610.41040#A1.SS5), and orders the collected actions so that each follows the achievers of its preconditions\. It ignores delete effects, so on models without them its plans are valid, and on our ToolSandbox models they can violate a domain precondition that an earlier action deletes\. The rest of the pipeline is set up as for LLM planning, so Proposition[1](https://arxiv.org/html/2610.41040#Thmproposition1)and the bound of Proposition[2](https://arxiv.org/html/2610.41040#Thmproposition2)\(b\) again hold\.

### E\.3Additional baselines

The four additional baselines of Section[3\.2](https://arxiv.org/html/2610.41040#S3.SS2)run with gpt\-oss\-20b under the decoding settings above, with the same tasks, catalogs, tool implementations, and official scoring as the other methods\. The compute\-matched agent and the adapted ReWOO and LLMCompiler also run onτ2\\tau^\{2\}\-bench retail\. Each runs three times per task, and scores are aggregated as in Table[1](https://arxiv.org/html/2610.41040#S2.T1)\. Table[8](https://arxiv.org/html/2610.41040#A4.T8)gives their paired differences with CGAP, and Table[7](https://arxiv.org/html/2610.41040#A4.T7)reports the results with their intervals\.

##### Plain agent with dependency notes\.

CGAP’s planning model gets ToolSandbox’s device dependencies from our annotations; this agent receives them as text instead\. We turn each ToolSandbox annotation of Appendix[A\.1](https://arxiv.org/html/2610.41040#A1.SS1)into one sentence, generated from the same annotation file that the planning model is compiled from, so both agents receive the same information:

- •“If low battery mode is on, turn it off before enabling Wi\-Fi, cellular service, or location services\.”
- •“Sending a message requires cellular service; check its status and enable it if needed\.”
- •“Getting the current location requires location services\.”
- •“Looking up holidays requires Wi\-Fi\.”

A fifth sentence states theCalendarConverted\\operatorname\{CalendarConverted\}condition for reminder operations in the same way\. The sentences appear under the heading “Domain notes” in the system prompt of every scenario, including scenarios to which they do not apply\. They were written once and frozen, and their wording was not tuned on evaluation scenarios\. Everything else is the plain agent\. The baseline runs on the 120 ToolSandbox scenarios only, since the other benchmarks have no domain annotations\.

##### Compute\-matched plain agent\.

CGAP uses more tokens per task than the plain agent \(Table[9](https://arxiv.org/html/2610.41040#A4.T9)\), so this agent spends a similar number on self\-checks\. After every failed tool call, and before its final reply, the agent is prompted to check whether every part of the request has been completed by a successful call, and to continue if not\. The self\-check prompt adapts the completion\-verification prompt \(Figure[6](https://arxiv.org/html/2610.41040#A3.F6)\) from one operation to the whole request\. We raised the step limit and the number of self\-check rounds until the mean number of tokens per task was within about 10% of CGAP’s on each benchmark, measured on held\-out tasks from outside our evaluation subsets, and froze both limits before the evaluation runs\. On the evaluation tasks, its mean tokens per task are within 5% of CGAP’s on these three benchmarks \(−\-4\.9%,\+\+4\.2%, and−\-2\.9% on ToolSandbox, ComplexFuncBench, and BFCL multi\-turn; Table[9](https://arxiv.org/html/2610.41040#A4.T9)\)\. Onτ2\\tau^\{2\}\-bench retail, which has no held\-out tasks, we did not calibrate these limits; the agent ran with onlyτ2\\tau^\{2\}\-bench’s default caps \(200 steps and 10 errors per episode\) and used 17% more tokens per task than CGAP\.

##### ReWOO\.

ReWOO is an established plan\-first agent, and we include it in case our LLM\-planning ablation understates what LLM planning can do\. We start from the official ReWOO code and prompts\([Xu et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib43)\): a planner writes steps such as\#E1 = Tool\[args\], a worker executes them, and a solver writes the reply\. The benchmarks required four changes\. \(1\) Arguments are JSON objects that may contain\#Ereferences, which fits each benchmark’s function\-calling interface\. \(2\) The planner runs at every user turn and receives the conversation history\. \(3\) After a tool error or missing evidence, the planner may replan at most twice per turn\. \(4\) A plan may contain anAskorCannotDostep; without one, ReWOO fails by construction on BFCL’s missing\-function and missing\-parameter categories and on ToolSandbox’s insufficient\-information scenarios\. Changes \(1\) and \(2\) adapt the interface, while \(3\) and \(4\) are our additions and give ReWOO behavior that the original method does not have\. ReWOO is limited to 32 tool calls per turn, matching the 32 execution decisions of the planned agents\.

##### LLMCompiler\.

In LLMCompiler\([Kim et al\., 2024](https://arxiv.org/html/2610.41040#bib.bib16)\), the LLM writes a dependency graph of calls instead of a sequence: a planner emits numbered tasks with their dependencies, a scheduler dispatches each task once its inputs are available, and a joiner decides whether to reply or replan\. We start from the authors’ implementation \(commita00c9d3\) and keep its planner, plan parser, dependency scheduler, and join\-and\-replan loop, extending them through wrappers and subclasses\. The benchmarks required five changes\. \(1\) Each benchmark function is exposed under an alias together with its original name, description, and complete argument schema\. A planned call takes one dictionary of named arguments, validated against the schema before dispatch, and references to earlier results may appear anywhere inside it; reading a nested field of a result requires observing the result and replanning\. \(2\) The planner and the joiner submit their output through two functions that execute no benchmark tools, and a malformed output gets at most two repair attempts\. \(3\) We added generic examples of dependency planning, of replanning after an identifier is found, and of asking for clarification; every planner and joiner call receives the current tool catalog and the benchmark’s policies\. \(4\) Each user turn starts a new compiler session that receives the visible conversation history and the actual results of earlier calls, but no reference trajectories or hidden evaluation state\. \(5\) Plans are not streamed, and the scheduler hands ready calls to each benchmark’s own driver, which executes them one at a time to preserve environment state, so our runs do not measure LLMCompiler’s parallel speedup\. Changes \(1\), \(2\), \(4\), and \(5\) adapt the interface, while \(3\) is our addition\. Each user turn, or single\-turn episode, allows at most 32 model calls, counting planner, joiner, and repair calls, and 32 tool attempts, matching the 32 execution decisions of the planned agents\. In our runs, its lower success rates were associated with invalid planner or joiner outputs, incorrect tool arguments, and turns that ended before all required calls were made\. It also uses more tokens per task than CGAP on every benchmark in Table[9](https://arxiv.org/html/2610.41040#A4.T9), 1\.1–1\.5 times as many\.

## Appendix FFurther related work

Deriving workflows from interface descriptions predates LLM agents: semantic web service composition planned over formal service models\([McIlraith and Son, 2002](https://arxiv.org/html/2610.41040#bib.bib25);[Sirin et al\., 2004](https://arxiv.org/html/2610.41040#bib.bib37);[Hoffmann et al\., 2007](https://arxiv.org/html/2610.41040#bib.bib12)\), and type\-directed API synthesis searches over API types\([Feng et al\., 2017](https://arxiv.org/html/2610.41040#bib.bib5);[Guo et al\., 2022](https://arxiv.org/html/2610.41040#bib.bib10)\)\. CGAP applies this idea to catalogs written for LLMs, where requests come in natural language and argument values must be traced to a source\. Its operations follow work that represents requests as executable structures\([Gupta et al\., 2018](https://arxiv.org/html/2610.41040#bib.bib11);[Andreas et al\., 2020](https://arxiv.org/html/2610.41040#bib.bib2)\), and its provenance checks adapt attribution research\([Rashkin et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib31);[Gao et al\., 2023](https://arxiv.org/html/2610.41040#bib.bib6)\)\. IPIGuard and CaMeL restrict tool calls to block prompt injection\([An et al\., 2025](https://arxiv.org/html/2610.41040#bib.bib1);[Debenedetti et al\., 2026](https://arxiv.org/html/2610.41040#bib.bib4)\); we have not evaluated our provenance checks as such a defense\.