HyperAgent: Planning and Acting over Tool-Schema Hypergraphs for Tool-Use LLM Agents

# HyperAgent: Planning and Acting over Tool-Schema Hypergraphs for Tool-Use LLM Agents
Source: [https://arxiv.org/html/2608.02650](https://arxiv.org/html/2608.02650)
###### Abstract

Large language model \(LLM\) agents increasingly rely on external tools to complete complex real\-world tasks\. However, reliable tool\-use planning remains challenging due to the limitations of implicit reasoning and the evolving nature of real\-world execution environments\. Existing tool\-use agents typically rely on LLMs to infer tool compositions from textual descriptions, which can lead to inefficient exploration and unreliable execution in complex tasks\. To address these challenges, we model tool relations at the schema level and construct a directed Tool–Schema Hypergraph, in which tools are represented as hyperedges from their required input\-schema nodes to their output\-schema nodes\. Furthermore, we propose HyperAgent, a Tool–Schema Hypergraph\-guided framework for dynamic planning and execution\. Given a task, HyperAgent first extracts a task\-relevant tool context graph and uses it to guide the construction of a schema\-aware Task DAG\. During execution, HyperAgent dynamically realizes each subtask by constructing a state\-conditioned tool support graph through deficit\-oriented expansion, which identifies unresolved requirements and retrieves supporting producer tools according to the current agent state\. Experiments on AppWorld demonstrate that HyperAgent improves task completion performance while reducing redundant API calls, LLM interactions, and token consumption compared with existing agent baselines\.

## Introduction

With continued improvements in the reasoning capabilities of large language models \(LLMs\)\(OpenAI[2023](https://arxiv.org/html/2608.02650#bib.bib1); Yanget al\.[2024](https://arxiv.org/html/2608.02650#bib.bib2)\), LLM\-based autonomous agents are increasingly deployed to perform complex real\-world tasks\(Yaoet al\.[2022](https://arxiv.org/html/2608.02650#bib.bib3); Kimet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib4)\)\. Equipped with tool\-use capabilities, these agents can invoke external APIs, manipulate operating systems, and interact with software services to satisfy user requests\. Such capabilities extend LLMs beyond language generation, allowing agents to take concrete actions and affect their environments\(Yanget al\.[2023](https://arxiv.org/html/2608.02650#bib.bib6); Qinet al\.[2023](https://arxiv.org/html/2608.02650#bib.bib5); Patilet al\.[2023](https://arxiv.org/html/2608.02650#bib.bib7)\)\. In many practical scenarios, however, fulfilling a user request requires the agent to interpret the task and determine several actions toward the intended goal\(Zhanget al\.[2025](https://arxiv.org/html/2608.02650#bib.bib8); Yuet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib9)\)\. For tool\-using agents, this further entails selecting tools that are aligned with the current objective and executable under the available information, resources, and environment state\(Liuet al\.[2024a](https://arxiv.org/html/2608.02650#bib.bib20); Lumeret al\.[2025](https://arxiv.org/html/2608.02650#bib.bib10)\)\.

To enhance the task\-solving capabilities of LLM agents, numerous approaches have been proposed\. Existing studies have primarily advanced tool\-using agents along two complementary directions\. The first focuses on online acting, where the agent repeatedly selects tools, observes its execution result, and determines the next action from the updated state\(Yaoet al\.[2022](https://arxiv.org/html/2608.02650#bib.bib3); Kimet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib4)\)\. This interaction loop enables the agent to incorporate runtime observations and adapt subsequent actions to execution outcomes\. The second focuses on task planning, where the LLM agent decomposes a user request into intermediate goals or generates a sequence of intended actions before execution\(Sunet al\.[2023](https://arxiv.org/html/2608.02650#bib.bib11); Erdoganet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib12)\)\. Such plans provide useful global guidance and help alleviate the myopic behavior of agents that select actions step by step\.

Despite this progress, existing approaches have two main limitations\. First, relying on LLMs to infer executable tool chains implicitly from textual tool descriptions is unreliable\. Specifically, for a target operation, the model must identify not only a semantically relevant tool but also the upstream tools required to produce its input parameters\. This dependency reasoning becomes particularly fragile when the agent must process a large volume of tool documentation\. Second, although recent tool\-retrieval methods preserve tools directly related to the user request, they may exclude semantically distant yet operationally indispensable prerequisites for the target tools\. Once omitted, these tools can only be recognized during online execution when the chosen tool is found to be non\-executable\.

These limitations have motivated a growing research interest in graph\-based approaches\. For example, at the tool level, ToolNet constrains each tool selection through transitions in a directed tool graph\(Liuet al\.[2024a](https://arxiv.org/html/2608.02650#bib.bib20)\), while Graph RAG–Tool Fusion expands semantically retrieved tools along dependency edges to recover prerequisite tools\(Lumeret al\.[2025](https://arxiv.org/html/2608.02650#bib.bib10)\)\. At the task level, GNN4TaskPlan employs graph neural networks to select structurally coherent subtasks\(Wuet al\.[2024](https://arxiv.org/html/2608.02650#bib.bib13)\), and GTool encodes request\-specific tool dependencies to guide the generation of complete tool trajectories\(Chenet al\.[2025b](https://arxiv.org/html/2608.02650#bib.bib15)\)\. These methods explicitly model tool relations that need to be inferred implicitly by LLMs, and allow the planner to recover prerequisite tools beyond semantic retrieval\.

Nevertheless, existing graph\-based approaches remain limited in two critical aspects\. First, current graphs capture only coarse tool dependencies and do not specify which upstream outputs satisfy the inputs of a downstream tool\(Leeet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib16)\)\. When multiple tools can produce the same required parameter, this ambiguity makes it difficult to identify the necessary producers and avoid redundant calls\. Second, executable tool composition is state\-dependent rather than fixed\. Some required inputs may already be available from the user request or previous executions, thereby changing which upstream tools are still needed\. A statically planned tool path may therefore become redundant or incomplete during execution\.

To this end, we first construct a directed Tool–Schema Hypergraph \(TSH\) to model fine\-grained parameter\-level relations among tools\. Each tool is represented as a directed hyperedge from its input schema nodes to its output schema and effect nodes\. We further annotate port links between output and input schema nodes to capture schema\-level data flow across tools\. Based on the constructed TSH, we propose HyperAgent, a planning and execution framework operating over the TSH\. Before execution, HyperAgent retrieves a tool context graph that contains potentially useful tools selected according to semantic relevance and hypergraph structure, and uses it to guide the decomposition of the task into a Task DAG whose nodes are connected by identified schema\-level dependencies\. During execution, HyperAgent realizes each ready subtask with a Tool Support Subgraph selected according to the current agent state\. The resulting observations update the agent state and are used to refine the remaining Task DAG, so that subsequent tool compositions adapt to the evolving execution context\.

In summary, our main contributions are summarized as follows:

- •We construct a directed Tool–Schema Hypergraph using a real\-world API dataset, which models tool relations as fine\-grained schema dependencies\.
- •We propose HyperAgent, a two\-stage planning and execution framework that extracts a task\-relevant Tool Context Graph and uses it to construct a schema\-level Task DAG before execution\.
- •We introduce deficit\-oriented support graph expansion to construct state\-conditioned Tool Support Subgraphs for ready subtasks, enabling tool compositions to adapt to the dynamical agent state\.
- •Extensive experiments on AppWorld show that HyperAgent improves task completion while reducing redundant API calls, LLM interactions, and token consumption compared with the selected baselines\.

## Related Work

Tool\-Use Planning\. Tool\-use planning enables language agents to select and compose tools into multi\-step action sequences\. Early methods rely on language\-model reasoning to guide tool use\. ReAct\(Yaoet al\.[2022](https://arxiv.org/html/2608.02650#bib.bib3)\)interleaves reasoning with actions, whereas ART\(Paranjapeet al\.[2023](https://arxiv.org/html/2608.02650#bib.bib17)\)constructs reasoning programs from retrieved demonstrations\. However, direct trajectory generation provides limited exploration of alternative tool sequences\. Search\-based methods instead evaluate multiple candidates through depth\-first search in ToolLLM\(Qinet al\.[2023](https://arxiv.org/html/2608.02650#bib.bib5)\)and A\*\-style search in ToolChain\(Zhuanget al\.[2024](https://arxiv.org/html/2608.02650#bib.bib18)\)\. Yet trajectory search still relies on textual descriptions to infer tool dependencies, which may lead to invalid tool selections or infeasible plans\.

Graph\-Augmented Agents\. Graph\-based methods make tool dependencies explicit by organizing tool relations and invocation paths into structured graphs\(Beiet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib23)\)\. ControlLLM\(Liuet al\.[2024b](https://arxiv.org/html/2608.02650#bib.bib19)\)searches tool graphs encoding parameter dependencies, while ToolNet\(Liuet al\.[2024a](https://arxiv.org/html/2608.02650#bib.bib20)\)organizes large tool collections through directed transitions\. However, tool graphs may be incomplete, irrelevant to a request, or insensitive to the evolving execution trajectory\(Chenet al\.[2026](https://arxiv.org/html/2608.02650#bib.bib21); Patelet al\.[2026](https://arxiv.org/html/2608.02650#bib.bib22)\)\. GTool\(Chenet al\.[2026](https://arxiv.org/html/2608.02650#bib.bib21)\)reduces irrelevant relations through request\-specific construction and addresses incompleteness through missing\-edge prediction, while Dynamic Tool Dependency Retrieval\(Patelet al\.[2026](https://arxiv.org/html/2608.02650#bib.bib22)\)updates retrieval using both the query and current trajectory\. Ordinary graphs represent dependencies through pairwise edges, whereas hypergraphs naturally capture higher\-order relations involving multiple entities\(Antelmiet al\.[2023](https://arxiv.org/html/2608.02650#bib.bib24)\)\. However, their use for executable tool\-schema planning under different agent states remains underexplored\.

## Preliminaries

Tool\-Schema Hypergraph \(TSH\)\. Letℋ=\(𝒱,ℰ,𝒟\)\\mathcal\{H\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathcal\{D\}\)denote a Tool\-Schema Hypergraph, where𝒱\\mathcal\{V\}represents schema and effect nodes,ℰ\\mathcal\{E\}contains tool hyperedges, and𝒟\\mathcal\{D\}contains port\-level schema\-dependency links between tool hyperedges\. The node set contains input\-schema nodes, output\-schema nodes, and tool\-effect nodes, i\.e\.,𝒱=𝒱I∪𝒱O∪𝒱F\\mathcal\{V\}=\\mathcal\{V\}\_\{I\}\\cup\\mathcal\{V\}\_\{O\}\\cup\\mathcal\{V\}\_\{F\}\. For simplicity, we use𝒱O\\mathcal\{V\}\_\{O\}to denote both output schemas and effect nodes\. Each tool hyperedgee∈ℰe\\in\\mathcal\{E\}is directed from a set of input nodes to a set of output and effect nodes, i\.e\.,Ee​\(VI\)=\{VO\}\.E\_\{e\}\(V\_\{I\}\)=\\\{V\_\{O\}\\\}\.The TSH contains port\-level schema\-dependency links𝒟⊆𝒱O×𝒱I,\\mathcal\{D\}\\subseteq\\mathcal\{V\}\_\{O\}\\times\\mathcal\{V\}\_\{I\},where each dependencyD​\(vo,vi\)=wD\(v\_\{o\},v\_\{i\}\)=windicates that the output schemavov\_\{o\}may support the input schemaviv\_\{i\}with weightww\. A subhypergraphℋS=\(𝒱S,ℰS,𝒟S\)\\mathcal\{H\}\_\{S\}=\(\\mathcal\{V\}\_\{S\},\\mathcal\{E\}\_\{S\},\\mathcal\{D\}\_\{S\}\)is induced by a subset of tool hyperedgesℰS⊆ℰ\\mathcal\{E\}\_\{S\}\\subseteq\\mathcal\{E\}, where𝒱S=⋃e∈ℰSV​\(e\),\\mathcal\{V\}\_\{S\}=\\bigcup\_\{e\\in\\mathcal\{E\}\_\{S\}\}V\(e\),and𝒟S=\{D​\(vo,vi\)=w∈𝒟∣vo,vi∈𝒱S\}\.\\mathcal\{D\}\_\{S\}=\\\{D\(v\_\{o\},v\_\{i\}\)=w\\in\\mathcal\{D\}\\mid v\_\{o\},v\_\{i\}\\in\\mathcal\{V\}\_\{S\}\\\}\.

###### Definition 1\(Neighbor Tools\)\.

Given two tool hyperedgesei,ej∈ℰe\_\{i\},e\_\{j\}\\in\\mathcal\{E\},eie\_\{i\}is an upstream neighbor ofeje\_\{j\}if at least one of the output schemas ofeie\_\{i\}can support at least one of the input schemas ofeje\_\{j\}through dependency edges, i\.e\.,ei∈Nbr−⁡\(ej\)⇔∃vo∈O​\(ei\),∃vi∈I​\(ej\),∃w\>0​s\.t\.​\(vo,vi\)∈𝒟\.e\_\{i\}\\in\\operatorname\{Nbr\}^\{\-\}\(e\_\{j\}\)\\iff\\exists v\_\{o\}\\in O\(e\_\{i\}\),\\exists v\_\{i\}\\in I\(e\_\{j\}\),\\exists w\>0\\ \\text\{s\.t\.\}\\ \(v\_\{o\},v\_\{i\}\)\\in\\mathcal\{D\}\.Symmetrically,eje\_\{j\}is a downstream neighbor ofeie\_\{i\}, andej∈Nbr\+⁡\(ei\)⇔ei∈Nbr−⁡\(ej\)\.e\_\{j\}\\in\\operatorname\{Nbr\}^\{\+\}\(e\_\{i\}\)\\iff e\_\{i\}\\in\\operatorname\{Nbr\}^\{\-\}\(e\_\{j\}\)\.

## Method

### HyperGraph Construction

Graph Conversion\. We construct the TSH based on In\-N\-Out\(Leeet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib16)\), an expert\-annotated parameter\-level API graph\. In the original graph, API tools and their input and output parameters are represented as nodes\. Directed intra\-API links connect input parameters to the corresponding API and the API to its output parameters\. In addition, directed inter\-API schema\-dependency links connect an output parameter of one API to an input parameter of another when the returned value can serve as a valid argument for the downstream API\. These links are constructed through LLM\-based filtering and expert annotation\. Although their tool–schema graph captures schema\-level data dependencies across tools, it does not explicitly represent the joint constraints of real\-world tool invocation\. Specifically, an API is executable only when all of its required inputs are jointly available and its outputs are jointly produced by the same invocation\. To encode these constraints, we convert the original graph into a directed Tool–Schema Hypergraph\. For each API tool, we represent it as a hyperedge and preserve the original schema nodes𝒱\\mathcal\{V\}and inter\-tool schema\-dependency links𝒟\\mathcal\{D\}\.

![Refer to caption](https://arxiv.org/html/2608.02650v1/x1.png)Figure 1:The framework of HyperAgent\.Graph Refinement\. Some tools do not return reusable parameters but primarily change the environment state, such as sending a message and creating a transaction\. Conversely, the execution of a tool may depend on an environment precondition, which is often described in its documentation but is not explicitly presented by input parameters\. For example, a login tool may establish an authenticated session that is required before invoking a protected API\. To represent such precondition and effect dependencies, we extract additional effect and condition nodes from API documentation\. First, we use GPT\-4o to extract candidate state changes and execution preconditions from each tool description and align them with the existing input and output schemas\. Expert annotators then validate the proposed alignments\. State predicates that are not represented by the original schema nodes are introduced into the node set as additional effect or condition nodes\. We preserve the original port–level schema dependency links in In–N–Out\. For the newly introduced effect and condition nodes, we enumerate candidate effect–precondition pairs and remove pairs with incompatible domains or entities\. Then, we use GPT\-4o to score the semantic relevance of the remaining pairs and further filter the irrelevant pairs\. Subsequently, human annotators verify the filtered candidates and label valid links as strong or weak state dependencies, while other pairs are discarded\. The retained effect–condition links are incorporated into the port–level dependency link set\. Due to space limitations, we provide implementation details for the refinement procedure and graph statistics in Appendix A\.

### Task\-Level Planning

Given a user request, HyperAgent first extracts a task\-relevant Tool Context Graph from the full TSH\. The context graph restricts the planning space to potentially useful tools while retaining the schema\-level connections among them\. Conditioned on this context graph, the agent is prompted to decompose the request into a schema–level Task DAG, where each node represents a subtask and each edge specifies data, effect, or ordering dependencies between subtasks\.

Task Interpretation\. User requests are often expressed at a high level, leaving the intended operations, relevant entities, constraints, and desired environment changes only implicit\. To help the agent locate the relevant region of the TSH, we prompt it to produce a structured task interpretation\. Formally, given a user requesttt, the agent is asked to output a structured representationdt=\(dtop,dtsch\)d\_\{t\}=\\left\(d\_\{t\}^\{\\mathrm\{op\}\},d\_\{t\}^\{\\mathrm\{sch\}\}\\right\), wheredtopd\_\{t\}^\{\\mathrm\{op\}\}captures the intended operations, anddtschd\_\{t\}^\{\\mathrm\{sch\}\}identifies candidate schemas, values, constraints, and desired outcomes expressed or implied by the request\. We use the components ofdtd\_\{t\}as retrieval signals to anchor relevant tool hyperedges and schema nodes in the TSH\.

Seed Hyperedge Anchoring\. To identify initial task\-relevant tools, we retrieve tool hyperedges based on the operation\-level interpretationdto​pd\_\{t\}^\{op\}\. Specifically, for each hyperedgee∈ℰe\\in\\mathcal\{E\}, we use its functional description and compute the semantic similarity withdto​pd\_\{t\}^\{op\}, which is denoted as

sim⁡\(e,dto​p\)=cos⁡\(𝐳​\(e\),𝐳​\(dto​p\)\),\\operatorname\{sim\}\(e,d\_\{t\}^\{op\}\)=\\cos\\left\(\\mathbf\{z\}\(e\),\\mathbf\{z\}\(d\_\{t\}^\{op\}\)\\right\),\(1\)where𝐳​\(⋅\)\\mathbf\{z\}\(\\cdot\)denotes the embedding function\. We select the Top\-KKhyperedges whose similarity scores exceed a thresholdθe\\theta\_\{e\}to form the seed hyperedge setℰseed\\mathcal\{E\}\_\{\\mathrm\{seed\}\}\.

Seed Node Anchoring\. We distinguish input and precondition nodes𝒱I\\mathcal\{V\}\_\{I\}from output and effect nodes𝒱O\\mathcal\{V\}\_\{O\}\. The schema\-level interpretationdtschd\_\{t\}^\{\\mathrm\{sch\}\}may contain entities, constraints, required values, and desired outcomes that correspond directly to these schema nodes\. We therefore usedtschd\_\{t\}^\{\\mathrm\{sch\}\}to anchor relevant nodes in the TSH\. For each nodev∈𝒱v\\in\\mathcal\{V\}, we compute the semantic similarity between its description anddtschd\_\{t\}^\{\\mathrm\{sch\}\}using the same embedding\-based similarity function in Equation[1](https://arxiv.org/html/2608.02650#Sx4.E1)\. We select the top\-KvK\_\{v\}input\-side and output\-side nodes whose similarity scores exceedθv\\theta\_\{v\}, yielding𝒱seedI⊆𝒱I\\mathcal\{V\}\_\{\\mathrm\{seed\}\}^\{I\}\\subseteq\\mathcal\{V\}\_\{I\}and𝒱seedO⊆𝒱O\\mathcal\{V\}\_\{\\mathrm\{seed\}\}^\{O\}\\subseteq\\mathcal\{V\}\_\{O\}, respectively\. The final seed node set is the union of both sides, i\.e\.,𝒱seed=𝒱seedI∪𝒱seedO\.\\mathcal\{V\}\_\{\\mathrm\{seed\}\}=\\mathcal\{V\}\_\{\\mathrm\{seed\}\}^\{I\}\\cup\\mathcal\{V\}\_\{\\mathrm\{seed\}\}^\{O\}\.

Context Graph Extraction\. Starting from the seed hyperedges and nodes, we perform bounded backward search over the TSH to construct a compact, task\-relevant context graph\. The expansion reduces the global tool space while retaining the schema–level dependencies connecting the retrieved tools\. We first augment the seed hyperedge set with tools directly associated with the anchored schema nodes\. For each output\-side seed node, tools satisfyingvo∈O​\(e\)v\_\{o\}\\in O\(e\)are considered as its direct producer candidates\. Similarly, for each input\-side seed node, tools satisfyingvi∈I​\(e\)v\_\{i\}\\in I\(e\)are considered direct consumer candidates\. Among the producer and consumer hyperedge candidates, we compute the operation\-level similarity defined in Equation[1](https://arxiv.org/html/2608.02650#Sx4.E1)and add the top\-KKcandidates for each seed node to the seed hyperedge setℰseed\\mathcal\{E\}\_\{\\mathrm\{seed\}\}\. We then initialize the backward frontier asℬ0=𝒱seedI∪\{vi∣vi∈I​\(e\),e∈ℰseed\}\\mathcal\{B\}\_\{0\}=\\mathcal\{V\}\_\{\\mathrm\{seed\}\}^\{I\}\\cup\\\{v\_\{i\}\\mid v\_\{i\}\\in I\(e\),\\ e\\in\\mathcal\{E\}\_\{\\mathrm\{seed\}\}\\\}\. At each hophh, the backward expansion follows dependency linksDDin reverse towards the output and effect nodes\. Formally, ifvi∈ℬhv\_\{i\}\\in\\mathcal\{B\}\_\{h\},D​\(vo,vi\)=w\>0D\(v\_\{o\},v\_\{i\}\)=w\>0, andvo∈O​\(ep\)v\_\{o\}\\in O\(e\_\{p\}\), thenepe\_\{p\}is considered as a producer candidate forviv\_\{i\}\. We rank producer candidates by jointly considering the strength of the schema\-level dependency and their semantic relevance to the operation–level task interpretation:

sback​\(e,dtop\)=w​\(vo,vi\)⋅cos​\(𝐳​\(e\),𝐳​\(dtop\)\)\.s\_\{\\mathrm\{back\}\}\(e,d\_\{t\}^\{\\mathrm\{op\}\}\)=w\(v\_\{o\},v\_\{i\}\)\\cdot\\mathrm\{cos\}\\bigl\(\\mathbf\{z\}\(e\),\\mathbf\{z\}\(d\_\{t\}^\{\\mathrm\{op\}\}\)\\bigr\)\.\(2\)For each frontier node, we retain the top\-KKproducer candidates and add them to the retrieved hyperedge set\. The input nodes of the newly added producers form the next backward frontierℬh\+1\\mathcal\{B\}\_\{h\+1\}\. This expansion continues until the hop budget is exhausted or no new producer is retrieved, inducing the Tool Context Graph\.

###### Definition 2\(Tool Context Graph\)\.

A Tool Context Graph is the task\-relevant subgraphℋs=\(𝒱s,ℰs,𝒟s\)\\mathcal\{H\}\_\{s\}=\(\\mathcal\{V\}\_\{s\},\\mathcal\{E\}\_\{s\},\\mathcal\{D\}\_\{s\}\)of the TSH induced by the seed set, whereℰs=ℰseed,𝒱s=⋃e∈ℰs\(I​\(e\)∪O​\(e\)\),\\mathcal\{E\}\_\{s\}=\\mathcal\{E\}\_\{\\mathrm\{seed\}\},\\mathcal\{V\}\_\{s\}=\\bigcup\_\{e\\in\\mathcal\{E\}\_\{s\}\}\\bigl\(I\(e\)\\cup O\(e\)\\bigr\),and𝒟s=\{\(vo,vi\)∈𝒟∣vo∈𝒱s,vi∈𝒱s\}\.\\mathcal\{D\}\_\{s\}=\\\{\(v\_\{o\},v\_\{i\}\)\\in\\mathcal\{D\}\\mid v\_\{o\}\\in\\mathcal\{V\}\_\{s\},\\ v\_\{i\}\\in\\mathcal\{V\}\_\{s\}\\\}\.The graphℋs\\mathcal\{H\}\_\{s\}provides the LLM planner with a compact context that preserves both task relevance and the schema\-level dependency topology among the retrieved tools\.

Task Decomposition\. After constructing the tool context graphℋs\\mathcal\{H\}\_\{s\}, we serialize it into a compact textual description, where each hyperedge is represented by its API name and description, and each schema node is described by its associated API tool, name, and concise description\. Moreover, the dependency links are serialized as directed links from the output schemas of producer hyperedges to the input schemas of consumer hyperedges\. We provide the prompt illustration in Appendix B\. Based on this serialized context, the LLM planner is prompted to construct a Task DAG\(Yanget al\.[2025](https://arxiv.org/html/2608.02650#bib.bib25); Donget al\.[2024](https://arxiv.org/html/2608.02650#bib.bib26)\), where each node represents a subtask and each edge encodes the identified dependencies among subtasks, including schema\-level data and effect dependencies from the Tool Context Graph\. For each subtask, the planner specifies its local goal, target output schemas or effects, and a set of candidate terminal tools\. For each dependency between subtasks, the planner identifies relevant schema\-dependency links from the Tool Context Graph that connect the output schemas or effects of the upstream subtask to the input schemas required by the downstream subtask\.

###### Definition 3\(Task DAG\)\.

Given the Tool Context Graphℋs\\mathcal\{H\}\_\{s\}, a Task DAG is an LLM\-generated directed acyclic graph𝒢=\(𝒬,ℒ\)\\mathcal\{G\}=\(\\mathcal\{Q\},\\mathcal\{L\}\)\. Each nodeqi∈𝒬q\_\{i\}\\in\\mathcal\{Q\}represents a subtask and is defined asqi=\(gi,τi,ℰ^i,ϕi\),q\_\{i\}=\(g\_\{i\},\\tau\_\{i\},\\widehat\{\\mathcal\{E\}\}\_\{i\},\\phi\_\{i\}\),wheregig\_\{i\}is the local goal,τi⊆𝒱O\\tau\_\{i\}\\subseteq\\mathcal\{V\}\_\{O\}denotes the target output schemas or effects,ℰ^i⊆ℰs\\widehat\{\\mathcal\{E\}\}\_\{i\}\\subseteq\\mathcal\{E\}\_\{s\}is a small set of candidate terminal tools, andϕi\\phi\_\{i\}records the execution status of the subtask\. Each edgeℓi​j∈ℒ\\ell\_\{ij\}\\in\\mathcal\{L\}represents a data or effect dependency fromqiq\_\{i\}toqjq\_\{j\}\. Such a dependency is grounded in schema\-level links fromℋs\\mathcal\{H\}\_\{s\}that connect outputs associated withqiq\_\{i\}to inputs required byqjq\_\{j\}\.

### Task Execution

Topological Execution\. Once the initial Task DAG is constructed, the agent executes subtasks following the dependency topology\. At execution stepℓ\\ell, the agent identifies the frontier subtasks whose predecessors have been completed and selects one for execution\. Here, we formally define the agent state\.

###### Definition 4\(Agent State\)\.

Given the current Task DAG𝒢ℓ=\(𝒬ℓ,ℒℓ\)\\mathcal\{G\}\_\{\\ell\}=\(\\mathcal\{Q\}\_\{\\ell\},\\mathcal\{L\}\_\{\\ell\}\)before theℓ\\ell\-th execution iteration, the runtime agent state is defined asSℓ=\(𝒞ℓ,ℛℓ,ℐℓ\),S\_\{\\ell\}=\(\\mathcal\{C\}\_\{\\ell\},\\mathcal\{R\}\_\{\\ell\},\\mathcal\{I\}\_\{\\ell\}\),where𝒞ℓ\\mathcal\{C\}\_\{\\ell\}records the execution history,ℛℓ\\mathcal\{R\}\_\{\\ell\}records the execution status of subtasks, andℐℓ\\mathcal\{I\}\_\{\\ell\}stores the runtime schema–value bindings and achieved effects accumulated during execution\.

For the selected subtask, the agent retrieves a tool support subgraph from the TSH for its concrete tool\-level realization, which is introduced in the following subsection\. After executing the selected subtask, the newly grounded schema–value bindingsΔ​ℐℓ\\Delta\\mathcal\{I\}\_\{\\ell\}and achieved effects update the agent state:Sℓ\+1=StateUpdate​\(Sℓ,Δ​ℐℓ\)\.S\_\{\\ell\+1\}=\\text\{StateUpdate\}\(S\_\{\\ell\},\\Delta\\mathcal\{I\}\_\{\\ell\}\)\.The updated state is then used either to execute the next subtask or to refine the remaining Task DAG, yielding𝒢ℓ\+1\\mathcal\{G\}\_\{\\ell\+1\}\.

Subtask Verification\. A successful tool call alone is insufficient to verify subtask completion\. After executing the selected tool support graph, HyperAgent determines whether the execution results satisfy the expected outputs, effects, and constraints of the current subtask\. Specifically, it aligns the execution trace with the selected support graph and examines the successful API calls, schema–value bindings, intermediate computation results, and achieved effects\. A subtask is marked as completed only when its required outputs are materialized with valid schema\-level evidence or its target effects are supported by the execution trace\. The verified terminal outputs are then incorporated intoℐℓ\+1\\mathcal\{I\}\_\{\\ell\+1\}, allowing HyperAgent to determine the initial state of subsequent subtasks\. Otherwise, HyperAgent retains the observed outputs and effects and refines the current Task DAG\. Due to space limitations, the prompt templates and detailed procedure are provided in the Appendix B, C, respectively\.

### Tool–Level Planning

The Task DAG specifies the subtasks and candidate terminal tools for each subtask\. However, HyperAgent does not determine an executable tool composition in advance, as the agent state evolves with newly obtained values and effects during execution, which may change the required tools\. Instead, HyperAgent dynamically constructs a Tool Support Subgraph for each subtask by identifying unresolved input requirements of candidate terminal tools and expanding producer tools according to the current state\.

Tool–Schema Support\. Before presenting the detailed expansion algorithm, we define Tool\-Schema Support to quantify the support strength between tools and input schemas\.

###### Definition 5\(Tool\-Schema Support\)\.

Given a Tool\-Schema Hypergraphℋ=\(𝒱,ℰ,𝒟\)\\mathcal\{H\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathcal\{D\}\), lete∈ℰe\\in\\mathcal\{E\}be a tool hyperedge andr∈𝒱Ir\\in\\mathcal\{V\}\_\{I\}be an input\-schema node\. The Tool\-Schema Support fromeetorrmeasures the strongest support of the outputs ofeeto the input schemarr, and is defined as

ρ​\(e,r\)=maxo∈O​\(e\)⁡W​\(o,r\),\\rho\(e,r\)=\\max\_\{o\\in O\(e\)\}W\(o,r\),\(3\)where

W​\(o,r\)=\{w,\(o,r\)∈𝒟,0,otherwise\.W\(o,r\)=\\begin\{cases\}w,&\(o,r\)\\in\\mathcal\{D\},\\\\ 0,&\\text\{otherwise\}\.\\end\{cases\}

Ifρ​\(e,r\)\>0\\rho\(e,r\)\>0, theneecan serve as a producer tool for schemarr\. For efficient lookup during online execution, we precompute the support between each input\-schema node and each tool hyperedge and store the scores in a sparse producer matrix𝐀prod∈ℝ\|𝒱I\|×\|ℰ\|\.\\mathbf\{A\}\_\{\\mathrm\{prod\}\}\\in\\mathbb\{R\}^\{\|\\mathcal\{V\}\_\{I\}\|\\times\|\\mathcal\{E\}\|\}\.Each row corresponds to an input schemarrand contains the support scores of its candidate producer tools, i\.e\.,𝐀prod​\(r,e\)=ρ​\(e,r\)\.\\mathbf\{A\}\_\{\\mathrm\{prod\}\}\(r,e\)=\\rho\(e,r\)\.

Deficit–Oriented Expansion\. For each candidate terminal toolet∈ℰ^ie\_\{t\}\\in\\widehat\{\\mathcal\{E\}\}\_\{i\}, Deficit–Oriented Expansion \(DOE\) performs beam search over the TSH to construct a Tool Support Subgraph conditioned on the current agent stateSℓS\_\{\\ell\}\. Starting from each proposed terminal tool, DOE maintains a deficit set that records input\-schema requirements not satisfied by the current agent state or the selected producer tools\. It iteratively expands candidate subgraphs by adding producer hyperedges to satisfy the deficit set and terminates when a complete support subgraph is found\. For readability, we omit the subtask superscriptqiq\_\{i\}in this subsection\.

###### Definition 6\(Deficit Set\)\.

Given an agent stateSℓ=\(𝒞ℓ,ℛℓ,ℐℓ\)S\_\{\\ell\}=\(\\mathcal\{C\}\_\{\\ell\},\\mathcal\{R\}\_\{\\ell\},\\mathcal\{I\}\_\{\\ell\}\)and a candidate support subgraph𝒢h=\(𝒱h,ℰh,𝒟h\)\\mathcal\{G\}\_\{h\}=\(\\mathcal\{V\}\_\{h\},\\mathcal\{E\}\_\{h\},\\mathcal\{D\}\_\{h\}\), the deficit setM𝒢hM\_\{\\mathcal\{G\}\_\{h\}\}contains input\-schema nodes required by the selected tools that are neither available in the current agent state nor supported by the output\-schema nodes of𝒢h\\mathcal\{G\}\_\{h\}through the retained dependency links\.

For the candidate terminal toolete\_\{t\}, DOE initializes the candidate subgraph𝒢0=\(𝒱0,ℰ0,𝒟0\)\\mathcal\{G\}\_\{0\}=\(\\mathcal\{V\}\_\{0\},\\mathcal\{E\}\_\{0\},\\mathcal\{D\}\_\{0\}\)with the current agent stateSℓS\_\{\\ell\}, where𝒱0=I​\(et\),ℰ0=\{et\},\\mathcal\{V\}\_\{0\}=I\(e\_\{t\}\),\\mathcal\{E\}\_\{0\}=\\\{e\_\{t\}\\\},and𝒟0=∅\.\\mathcal\{D\}\_\{0\}=\\emptyset\.The initial deficit setM𝒢0M\_\{\\mathcal\{G\}\_\{0\}\}is determined by the input schemas ofete\_\{t\}that are not grounded in the current agent state\. We encode the deficit set as a sparse binary vector𝐦𝒢h∈\{0,1\}\|𝒱I\|×1\\mathbf\{m\}\_\{\\mathcal\{G\}\_\{h\}\}\\in\\\{0,1\\\}^\{\|\\mathcal\{V\}\_\{I\}\|\\times 1\}, where each dimension indicates whether the corresponding input\-schema node belongs to the current deficit set:

𝐦𝒢h​\(r\)=\{1,r∈M𝒢h,0,r∉M𝒢h,r∈𝒱I\.\\mathbf\{m\}\_\{\\mathcal\{G\}\_\{h\}\}\(r\)=\\begin\{cases\}1,&r\\in M\_\{\\mathcal\{G\}\_\{h\}\},\\\\ 0,&r\\notin M\_\{\\mathcal\{G\}\_\{h\}\},\\end\{cases\}\\qquad r\\in\\mathcal\{V\}\_\{I\}\.\(4\)At each expansion step, DOE selects producer hyperedges that can resolve the current deficits\. Since the output headO​\(e\)O\(e\)of a producer hyperedge may jointly support multiple unresolved input\-schema nodes, DOE prioritizes hyperedges whose outputs have greater overlap with the current deficit setM𝒢hM\_\{\\mathcal\{G\}\_\{h\}\}\. This overlap is defined as

Ω​\(e,M𝒢h\)=∑r∈M𝒢hρ​\(e,r\),\\Omega\(e,M\_\{\\mathcal\{G\}\_\{h\}\}\)=\\sum\_\{r\\in M\_\{\\mathcal\{G\}\_\{h\}\}\}\\rho\(e,r\),\(5\)whereρ​\(e,r\)\\rho\(e,r\)denotes the Tool\-Schema Support defined above\. The top\-KKproducer hyperedges with positive support are selected as expansion directions\. For each selected producerepe\_\{p\}, DOE adds the hyperedge together with its input and output schema nodes and retains the dependency links through which its outputs support the nodes in the current deficit set\. The deficit set is then updated after expansion by deleting the resolved deficits and introducing input schemas required byepe\_\{p\}that are not already grounded in the current state or supported by the expanded subgraph\. At each expansion depth, the subgraph candidates are ranked according to the number of unresolved schema nodes in the deficit set, i\.e\.,\|M𝒢h\+1\(ep\)\|\|M\_\{\\mathcal\{G\}\_\{h\+1\}^\{\(e\_\{p\}\)\}\}\|, and the top\-BBcandidates with the smallest deficit sets are retained for the next expansion\. Candidates with empty deficit sets are considered complete support subgraphs and are no longer expanded\.

Support Graph Selection\. Given a subtaskqiq\_\{i\}, let𝕊ℓqi\\mathbb\{S\}\_\{\\ell\}^\{q\_\{i\}\}denote the set of complete support subgraphs returned by DOE for the proposed candidate terminal tools inℰ^i\\widehat\{\\mathcal\{E\}\}\_\{i\}\. HyperAgent selects a support subgraph𝒢qi∈𝕊ℓqi\\mathcal\{G\}\_\{q\_\{i\}\}\\in\\mathbb\{S\}\_\{\\ell\}^\{q\_\{i\}\}as the schema\-complete tool composition for realizingqiq\_\{i\}\. If no feasible support subgraph is available or the execution fails, the outcome is incorporated into the agent state and the remaining Task DAG is refined accordingly\.

## Experiments

### Dataset

We evaluate HyperAgent on the AppWorld dataset\(Trivediet al\.[2024](https://arxiv.org/html/2608.02650#bib.bib14)\), a benchmark that evaluates an LLM agent’s ability to complete user\-directed tasks by interacting with APIs from simulated consumer applications, including email, payment, music, shopping, phone, and file\-management services\. The agent operates through a stateful Python interpreter and performs tasks of varying difficulty\. Task correctness is determined by unit tests that verify whether the requested changes were successfully applied, whether any unintended modifications were introduced, and whether the final answer matches the reference answer when applicable\. The benchmark contains 250 task scenarios, each instantiated with three variants, resulting in 750 tasks in total\. These tasks are divided into a training set of 35 scenarios \(105 tasks\), a development set of 20 scenarios \(60 tasks\), a normal test set \(Test\-N\) of 56 scenarios \(168 tasks\), and a challenge test set \(Test\-C\) of 139 scenarios \(417 tasks\)\. Compared withTest\-N,Test\-Crequires longer and more complex interaction sequences and may involve applications that are unseen during training\. Performance is measured using Task Goal Completion \(TGC\), which reports the proportion of successfully completed tasks, and Scenario Goal Completion \(SGC\), which counts a scenario as solved only when all of its task variants are completed successfully\.

![Refer to caption](https://arxiv.org/html/2608.02650v1/x2.png)Figure 2:Tool call and token usage for HyperAgent\.
### Baselines

Supervised Fine\-Tuning \(SFT\)\. We include three supervised baselines that learn from successful agent trajectories\. SFT\-GT transforms gold AppWorld traces into ReAct\-style interaction trajectories for supervised training\. RFT\(Yuanet al\.[2023](https://arxiv.org/html/2608.02650#bib.bib32)\)samples trajectories from the base agent and fine\-tunes the model only on successful rollouts\. EI\(Anthonyet al\.[2017](https://arxiv.org/html/2608.02650#bib.bib31)\)performs RFT iteratively, using the improved policy from each round to collect training trajectories for the next round\.

Direct Preference Optimization \(DPO\)\. We also compare HyperAgent with preference\-based methods\. DPO\-MCTS\(Puttaet al\.[2024](https://arxiv.org/html/2608.02650#bib.bib29)\)uses Monte Carlo tree search to discover alternative action trajectories and constructs preference pairs from their estimated returns\. DMPO\(Shiet al\.[2024](https://arxiv.org/html/2608.02650#bib.bib30)\)extends preference optimization to multi\-turn interaction by jointly modeling the decisions within preferred and rejected trajectories\.

Reinforcement Learning \(RL\)\. We include policy\-gradient methods that optimize agents directly from environment rewards\. PPO\(Schulmanet al\.[2017](https://arxiv.org/html/2608.02650#bib.bib33)\)trains policies using a learned value model for advantage estimation\. RLOO\(Ahmadianet al\.[2024](https://arxiv.org/html/2608.02650#bib.bib34)\)estimates trajectory\-level advantages by comparing multiple rollouts sampled for the same task\. GRPO\(Shaoet al\.[2024](https://arxiv.org/html/2608.02650#bib.bib35)\)performs clipped group\-relative updates using normalized rewards among rollouts of the same task, while LOOP reuses old sampled trajectories through clipped policy updates and assigns credit at trajectory \(bandit\), turn, or token\-level\(Chenet al\.[2025a](https://arxiv.org/html/2608.02650#bib.bib27)\)\.

Non\-Fine\-Tuning Methods \(NFT\)\. For NFT methods, we perform four agent scaffolds\. ReAct\(Yaoet al\.[2022](https://arxiv.org/html/2608.02650#bib.bib3)\)solves tasks through iterative reasoning, execution, and observation\. Plan and Execution \(PlanExec\)\(Erdoganet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib12)\)generates a plan which consists subtasks before ReAct execution, whereas Reflexion \(FullCodeRefl\)\(Kimet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib4)\)explicitly writes and revises execution feedback after each execution\. Traj \(SetBSR\+Snippet\)\(Guptaet al\.[2025](https://arxiv.org/html/2608.02650#bib.bib28)\)augments the agent with few\-shot trajectory demonstrations before the test task and inserts a state\-matched snippet into the context before each action decision\.

Table 1:Performance comparison with different paradigms on AppWorld\.Table 2:Performance comparison on AppWorld under different agent optimization methods\.
### Agent Implementation

We use GPT\-4o as the backbone for all LLM\-based components in the main experiments, including hypergraph construction, task interpretation, semantic DAG planning and refinement, support\-graph selection, and ReAct\-Code execution\. Tool context extraction, Deficit\-Oriented Expansion, and runtime binding validation are implemented as deterministic modules and do not invoke the LLM unless semantic ambiguity remains\. Each task is executed in a freshly initialized AppWorld environment with a persistent restricted Python REPL, allowing intermediate variables and tool outputs to be reused across subgoals\. The prompt templates for the Planner, Refiner, and Executor, together with their decoding configurations, are provided in Appendix A\. We also vary the LLM backbone, using GPT\-4–Turbo and Llama\-3–70B–Instruct, to evaluate HyperAgent against other agent frameworks\.

![Refer to caption](https://arxiv.org/html/2608.02650v1/x3.png)\(a\)Task Performance\.
![Refer to caption](https://arxiv.org/html/2608.02650v1/x4.png)\(b\)Token Usage\.
![Refer to caption](https://arxiv.org/html/2608.02650v1/x5.png)\(c\)API Calls\.

Figure 3:Ablation study with two variants\.
### Main Results

RQ1: Does HyperAgent improve end\-to\-end task performance\. First, we compare HyperAgent with methods from the SFT, DPO, RL, and NFT paradigms\. All SFT, DPO, and RL baselines are trained with the Qwen\-2\.5\-32B LLM backbone, whereas the NFT methods are based on GPT\-4o\. As shown in Table[2](https://arxiv.org/html/2608.02650#Sx5.T2), by using a more comprehensive planning context and detailed schema\-level Tool Support Subgraphs, HyperAgent outperforms the other NFT methods and is competitive with trained agents\. Second, we compare HyperAgent with different agent scaffolds\. From Table[1](https://arxiv.org/html/2608.02650#Sx5.T1), we observe that, with schema\-level dependencies, HyperAgent consistently outperforms ReAct, PlanExec, and FullCodeRefl across the evaluated LLM backbones\.

RQ2: Does HyperAgent reduce tool\-document and total costs\. We compare HyperAgent with ReAct in terms of LLM interaction turns, API calls, and total token consumption on Test\-Normal and Test\-Challenge\. As shown in Fig\.[2](https://arxiv.org/html/2608.02650#Sx5.F2), HyperAgent consistently reduces costs on both types of tasks\. We further present a representative execution rollout \(with additional examples in the Appendix D\), from which we observe that ReAct repeatedly explores API documentation and retries actions before resolving the necessary constraints, whereas HyperAgent follows dependency\-grounded tool sequences to accomplish planned subgoals, such as retrieving roommates’ contact information, identifying matching payment requests, and issuing reminders\. With the TSH, HyperAgent constructs prerequisite\-complete support paths for individual subgoals, reducing costly online exploration over the action space\.

### Ablation Study

RQ3: Are the main components of HyperAgent essential and effective\. First, we compare HyperAgent with two variants\. InVariant 1, we remove the retrieved graph context, including tool\-schema dependencies, and retain only simplified tool descriptions during DAG planning and refinement\. InVariant 2, we remove the Tool Support Subgraphs for each subtask and use the top\-KKtools with the highest semantic similarity to the subgoal\. As shown in Figure[3](https://arxiv.org/html/2608.02650#Sx5.F3), HyperAgent achieves higher task performance while using fewer tokens and API calls\. Removing either component consistently degrades end\-to\-end task performance on both Test\-N and Test\-C\. This trend suggests that graph context and tool support graphs reduce redundant tool exploration by exposing schema\-level relations across tools\. Moreover, HyperAgent can construct more complete execution paths and avoid semantically related but operationally unsuitable tools, leading to fewer API invocations and less exploration\. Second, we study the impact of the hop count in the Tool Context Graph and the top\-KKsupport parameter used in support\-graph expansion, as shown in Figure[4](https://arxiv.org/html/2608.02650#Sx5.F4)\. Increasing the hop count from 1 to 2 and the top\-KKvalue from 1 to 3 improves both TGC and SGC by recovering more valid prerequisite paths\. However, further expansion provides negligible gains while substantially increasing token consumption due to additional irrelevant tools and dependencies\.

![Refer to caption](https://arxiv.org/html/2608.02650v1/x6.png)\(a\)Task Performance\.
![Refer to caption](https://arxiv.org/html/2608.02650v1/x7.png)\(b\)Token Usage\.

Figure 4:Key hyperparameter analysis in HyperAgent\.
### More Experiments

RQ4: Does HyperAgent construct a compact tool context that preserves the gold tools\.

![Refer to caption](https://arxiv.org/html/2608.02650v1/x8.png)Figure 5:Quality evaluation of HyperAgent\.To evaluate the effectiveness of the proposed Tool Context Graphs, we extract task\-level gold tool sets from the official AppWorld solutions and compare HyperAgent with semantic top\-KKtool retrieval and In\-N\-Out graph retrieval under the same context budget of 20 tools\. Based on the results in Figure[5](https://arxiv.org/html/2608.02650#Sx5.F5), HyperAgent significantly outperforms In\-N\-Out and semantic retrieval\. This result indicates that, with schema\-node anchoring and dependency\-guided expansion, the extracted tool context recovers implicit prerequisite tools that are not directly aligned with the task semantics, thereby providing a reliable planning and execution space for task completion\.

RQ5: Can HyperAgent Propose Better Tool\-Use Sequences under Dynamical States\.

![Refer to caption](https://arxiv.org/html/2608.02650v1/x9.png)Figure 6:Subgoal completion rate under dynamic states\.We evaluate the constructed tool support graphs by examining whether they improve subgoal completion while reducing LLM calls\. We compare HyperAgent with ReAct using semantic Top–K retrieval under the same tool budget\. For a fair comparison, both methods operate on the same frozen set of subgoals\. Before executing either method, we manually annotate completion contracts for a predefined subset of subgoals, specifying their expected effects and outputs\. A subgoal is considered completed only when its contract is supported by runtime observations or verified changes to the environment\. Based on the results in Figure[6](https://arxiv.org/html/2608.02650#Sx5.F6), HyperAgent achieves a higher subgoal completion rate while reducing the average number of LLM calls per subgoal\. This result suggests that the state\-conditioned support graphs expose prerequisite tools and intermediate schemas before execution, thereby reducing trial\-and\-error tool selection and repeated exploration relative to the baseline\.

## Conclusion

In this paper, we present HyperAgent, a Tool\-Schema Hypergraph\-guided framework for dynamic tool\-use planning with LLM agents\. We extract schema\-level dependencies among tools and represent the available tool space as a directed Tool\-Schema Hypergraph\. Given a task, HyperAgent retrieves a task\-relevant Tool Context Graph that preserves schema\-level dependencies and guides the decomposition of the task into a fine\-grained Task DAG\. During execution, we further introduce deficit\-based support graph expansion to construct a state\-conditioned and structurally grounded tool composition for each subtask\. Experiments on AppWorld demonstrate that HyperAgent improves task completion while reducing redundant API calls, LLM interactions, and token consumption compared with the selected baselines\. These findings suggest that explicitly modeling tool dependencies can complement the semantic reasoning capabilities of LLMs, enabling more reliable and efficient tool\-use planning under dynamically changing agent states\.

## References

- A\. Ahmadian, C\. Cremer, M\. Gallé, M\. Fadaee, J\. Kreutzer, O\. Pietquin, A\. Üstün, and S\. Hooker \(2024\)Back to basics: revisiting reinforce style optimization for learning from human feedback in llms\.External Links:2402\.14740,[Link](https://arxiv.org/abs/2402.14740)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p3.1)\.
- A\. Antelmi, G\. Cordasco, M\. Polato, V\. Scarano, C\. Spagnuolo, and D\. Yang \(2023\)A survey on hypergraph representation learning\.ACM Comput\. Surv\.56\(1\)\.External Links:ISSN 0360\-0300,[Link](https://doi.org/10.1145/3605776),[Document](https://dx.doi.org/10.1145/3605776)Cited by:[Related Work](https://arxiv.org/html/2608.02650#Sx2.p2.1)\.
- T\. W\. Anthony, Z\. Tian, and D\. Barber \(2017\)Thinking fast and slow with deep learning and tree search\.InNeural Information Processing Systems,External Links:[Link](https://api.semanticscholar.org/CorpusID:19449905)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p1.1)\.
- Y\. Bei, W\. Zhang, S\. Wang, W\. Chen, S\. Zhou, H\. Chen, Y\. Li, J\. Bu, S\. Pan, Y\. Yu, I\. King, F\. Karray, and P\. S\. Yu \(2025\)Graphs meet ai agents: taxonomy, progress, and future opportunities\.External Links:2506\.18019,[Link](https://arxiv.org/abs/2506.18019)Cited by:[Related Work](https://arxiv.org/html/2608.02650#Sx2.p2.1)\.
- K\. Chen, M\. Cusumano\-Towner, B\. Huval, A\. Petrenko, J\. Hamburger, V\. Koltun, and P\. Krahenbuhl \(2025a\)Reinforcement learning for long\-horizon interactive llm agents\.ArXivabs/2502\.01600\.External Links:[Link](https://api.semanticscholar.org/CorpusID:276106993)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p3.1)\.
- W\. Chen, W\. Li, D\. Yao, X\. Meng, C\. Gong, and J\. Bi \(2025b\)GTool: graph enhanced tool planning with large language model\.ArXivabs/2508\.12725\.External Links:[Link](https://api.semanticscholar.org/CorpusID:280677907)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p4.1)\.
- W\. Chen, D\. Yao, W\. Li, X\. Meng, C\. Gong, and J\. Bi \(2026\)GTool: graph enhanced tool planning with large language model\.InThe Fourteenth International Conference on Learning Representations,Cited by:[Related Work](https://arxiv.org/html/2608.02650#Sx2.p2.1)\.
- Y\. Dong, X\. Zhu, Z\. Pan, L\. Zhu, and Y\. Yang \(2024\)VillagerAgent: a graph\-based multi\-agent framework for coordinating complex task dependencies in minecraft\.InAnnual Meeting of the Association for Computational Linguistics,External Links:[Link](https://api.semanticscholar.org/CorpusID:270371956)Cited by:[Task\-Level Planning](https://arxiv.org/html/2608.02650#Sx4.SSx2.p6.1)\.
- L\. E\. Erdogan, H\. Furuta, S\. Kim, N\. Lee, S\. Moon, G\. Anumanchipalli, K\. Keutzer, and A\. Gholami \(2025\)Plan\-and\-act: improving planning of agents for long\-horizon tasks\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=ybA4EcMmUZ)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p2.1),[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p4.1)\.
- S\. Gupta, S\. Singh, A\. Sabharwal, T\. Khot, and B\. Bogin \(2025\)Leveraging in\-context learning for language model agents\.ArXivabs/2506\.13109\.External Links:[Link](https://api.semanticscholar.org/CorpusID:279403121)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p4.1)\.
- J\. Kim, S\. Rhee, M\. Kim, D\. Kim, S\. Lee, Y\. Sung, and K\. Jung \(2025\)ReflAct: world\-grounded decision making in llm agents via goal\-state reflection\.InConference on Empirical Methods in Natural Language Processing,External Links:[Link](https://api.semanticscholar.org/CorpusID:278783024)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1),[Introduction](https://arxiv.org/html/2608.02650#Sx1.p2.1),[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p4.1)\.
- S\. Lee, N\. Kim, and Y\. Jo \(2025\)In\-n\-out: a parameter\-level api graph dataset for tool agents\.ArXivabs/2509\.01560\.External Links:[Link](https://api.semanticscholar.org/CorpusID:281079083)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p5.1),[HyperGraph Construction](https://arxiv.org/html/2608.02650#Sx4.SSx1.p1.2)\.
- X\. Liu, Z\. Peng, X\. Yi, X\. Xie, L\. Xiang, Y\. Liu, and D\. Xu \(2024a\)ToolNet: connecting large language models with massive tools via tool graph\.External Links:2403\.00839,[Link](https://arxiv.org/abs/2403.00839)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1),[Introduction](https://arxiv.org/html/2608.02650#Sx1.p4.1),[Related Work](https://arxiv.org/html/2608.02650#Sx2.p2.1)\.
- Z\. Liu, Z\. Lai, Z\. Gao, E\. Cui, Z\. Li, X\. Zhu, L\. Lu, Q\. Chen, Y\. Qiao, J\. Dai, and W\. Wang \(2024b\)ControlLLM: augment language models with tools by searching on graphs\.InComputer Vision – ECCV 2024,pp\. 89–105\.External Links:[Document](https://dx.doi.org/10.1007/978-3-031-73254-6%5F6)Cited by:[Related Work](https://arxiv.org/html/2608.02650#Sx2.p2.1)\.
- E\. Lumer, P\. H\. Basavaraju, M\. Mason, J\. A\. Burke, and V\. K\. Subbiah \(2025\)Graph rag\-tool fusion\.ArXivabs/2502\.07223\.External Links:[Link](https://api.semanticscholar.org/CorpusID:276258711)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1),[Introduction](https://arxiv.org/html/2608.02650#Sx1.p4.1)\.
- OpenAI \(2023\)GPT\-4 technical report\.External Links:[Link](https://api.semanticscholar.org/CorpusID:257532815)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1)\.
- B\. Paranjape, S\. Lundberg, S\. Singh, H\. Hajishirzi, L\. Zettlemoyer, and M\. T\. Ribeiro \(2023\)ART: automatic multi\-step reasoning and tool\-use for large language models\.External Links:2303\.09014,[Link](https://arxiv.org/abs/2303.09014)Cited by:[Related Work](https://arxiv.org/html/2608.02650#Sx2.p1.1)\.
- B\. Patel, D\. Belli, A\. Jalalirad, M\. Arnold, A\. Ermolov, and B\. Major \(2026\)Dynamic tool dependency retrieval for lightweight function calling\.InFindings of the Association for Computational Linguistics: ACL 2026,M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),San Diego, California, United States,pp\. 33649–33672\.External Links:[Link](https://aclanthology.org/2026.findings-acl.1680/),[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.1680),ISBN 979\-8\-89176\-395\-1Cited by:[Related Work](https://arxiv.org/html/2608.02650#Sx2.p2.1)\.
- S\. G\. Patil, T\. Zhang, X\. Wang, and J\. E\. Gonzalez \(2023\)Gorilla: large language model connected with massive apis\.ArXivabs/2305\.15334\.External Links:[Link](https://api.semanticscholar.org/CorpusID:258865184)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1)\.
- P\. Putta, E\. Mills, N\. Garg, S\. R\. Motwani, C\. Finn, D\. Garg, and R\. Rafailov \(2024\)Agent q: advanced reasoning and learning for autonomous ai agents\.ArXivabs/2408\.07199\.External Links:[Link](https://api.semanticscholar.org/CorpusID:271865516)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p2.1)\.
- Y\. Qin, S\. Liang, Y\. Ye, K\. Zhu, L\. Yan, Y\. Lu, Y\. Lin, X\. Cong, X\. Tang, B\. Qian, S\. Zhao, R\. Tian, R\. Xie, J\. Zhou, M\. H\. Gerstein, D\. Li, Z\. Liu, and M\. Sun \(2023\)ToolLLM: facilitating large language models to master 16000\+ real\-world apis\.ArXivabs/2307\.16789\.External Links:[Link](https://api.semanticscholar.org/CorpusID:260334759)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1),[Related Work](https://arxiv.org/html/2608.02650#Sx2.p1.1)\.
- J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. Klimov \(2017\)Proximal policy optimization algorithms\.ArXivabs/1707\.06347\.External Links:[Link](https://api.semanticscholar.org/CorpusID:28695052)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p3.1)\.
- Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, M\. Zhang, Y\. K\. Li, Y\. Wu, and D\. Guo \(2024\)DeepSeekMath: pushing the limits of mathematical reasoning in open language models\.ArXivabs/2402\.03300\.External Links:[Link](https://api.semanticscholar.org/CorpusID:267412607)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p3.1)\.
- W\. Shi, M\. Yuan, J\. Wu, Q\. Wang, and F\. Feng \(2024\)Direct multi\-turn preference optimization for language agents\.ArXivabs/2406\.14868\.External Links:[Link](https://api.semanticscholar.org/CorpusID:270688227)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p2.1)\.
- S\. Sun, Y\. Liu, S\. Wang, C\. Zhu, and M\. Iyyer \(2023\)PEARL: prompting large language models to plan and execute actions over long documents\.ArXivabs/2305\.14564\.External Links:[Link](https://api.semanticscholar.org/CorpusID:258866190)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p2.1)\.
- H\. Trivedi, T\. Khot, M\. Hartmann, R\. R\. Manku, V\. Dong, E\. Li, S\. Gupta, A\. Sabharwal, and N\. Balasubramanian \(2024\)AppWorld: a controllable world of apps and people for benchmarking interactive coding agents\.ArXivabs/2407\.18901\.External Links:[Link](https://api.semanticscholar.org/CorpusID:271516633)Cited by:[Dataset](https://arxiv.org/html/2608.02650#Sx5.SSx1.p1.1)\.
- X\. Wu, Y\. Shen, C\. Shan, K\. Song, S\. Wang, B\. Zhang, J\. Feng, H\. Cheng, W\. Chen, Y\. Xiong, and D\. Li \(2024\)Can graph learning improve planning in llm\-based agents?\.Advances in Neural Information Processing Systems 37\.External Links:[Link](https://api.semanticscholar.org/CorpusID:270094995)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p4.1)\.
- Q\. A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Li, D\. Liu, F\. Huang, G\. Dong, H\. Wei, H\. Lin, J\. Yang, J\. Tu, J\. Zhang, J\. Yang, J\. Yang, J\. Zhou, J\. Lin, K\. Dang, K\. Lu, K\. Bao, K\. Yang, L\. Yu, M\. Li, M\. Xue, P\. Zhang, Q\. Zhu, R\. Men, R\. Lin, T\. Li, T\. Xia, X\. Ren, X\. Ren, Y\. Fan, Y\. Su, Y\. Zhang, Y\. Wan, Y\. Liu, Z\. Cui, Z\. Zhang, Z\. Qiu, S\. Quan, and Z\. Wang \(2024\)Qwen2\.5 technical report\.ArXivabs/2412\.15115\.External Links:[Link](https://api.semanticscholar.org/CorpusID:274859421)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1)\.
- Y\. Yang, H\. Chai, S\. Shao, Y\. Song, S\. Qi, R\. Rui, and W\. Zhang \(2025\)AgentNet: decentralized evolutionary coordination for llm\-based multi\-agent systems\.ArXivabs/2504\.00587\.External Links:[Link](https://api.semanticscholar.org/CorpusID:277468263)Cited by:[Task\-Level Planning](https://arxiv.org/html/2608.02650#Sx4.SSx2.p6.1)\.
- Z\. Yang, L\. Li, J\. Wang, K\. Lin, E\. Azarnasab, F\. Ahmed, Z\. Liu, C\. Liu, M\. Zeng, and L\. Wang \(2023\)MM\-react: prompting chatgpt for multimodal reasoning and action\.ArXivabs/2303\.11381\.External Links:[Link](https://api.semanticscholar.org/CorpusID:257637012)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1)\.
- S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. Cao \(2022\)ReAct: synergizing reasoning and acting in language models\.ArXivabs/2210\.03629\.External Links:[Link](https://api.semanticscholar.org/CorpusID:252762395)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1),[Introduction](https://arxiv.org/html/2608.02650#Sx1.p2.1),[Related Work](https://arxiv.org/html/2608.02650#Sx2.p1.1),[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p4.1)\.
- J\. Yu, Y\. Ding, and H\. Sato \(2025\)DynTaskMAS: a dynamic task graph\-driven framework for asynchronous and parallel llm\-based multi\-agent systems\.ArXivabs/2503\.07675\.External Links:[Link](https://api.semanticscholar.org/CorpusID:276928831)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1)\.
- Z\. Yuan, H\. Yuan, C\. Li, G\. Dong, C\. Tan, and C\. Zhou \(2023\)Scaling relationship on learning mathematical reasoning with large language models\.ArXivabs/2308\.01825\.External Links:[Link](https://api.semanticscholar.org/CorpusID:260438790)Cited by:[Baselines](https://arxiv.org/html/2608.02650#Sx5.SSx2.p1.1)\.
- S\. Zhang, X\. Ma, Z\. Cao, Z\. Zhang, and H\. Zhao \(2025\)Plan\-over\-graph: towards parallelable llm agent schedule\.ArXivabs/2502\.14563\.External Links:[Link](https://api.semanticscholar.org/CorpusID:276482589)Cited by:[Introduction](https://arxiv.org/html/2608.02650#Sx1.p1.1)\.
- Y\. Zhuang, X\. Chen, T\. Yu, S\. Mitra, V\. Bursztyn, R\. A\. Rossi, S\. Sarkhel, and C\. Zhang \(2024\)ToolChain\*: efficient action space navigation in large language models with A\* search\.InThe Twelfth International Conference on Learning Representations,Cited by:[Related Work](https://arxiv.org/html/2608.02650#Sx2.p1.1)\.