PaperlayerView exact revision on arXiv

Source-linked AI summary

NaviAgent: Graph-Driven Bilevel Planning for Scalable Tool Orchestration

Yan Jiang, Hao Zhou, Lizhong GU, Tianlong Li, Ruinan Jin, Wanqi Zhou, Ai Han

arXiv:2506.19500v3cs.AIcs.CLcs.LG

TL;DR

Large, changing tool ecosystems make reliable multi-tool composition difficult as mismatches accumulate along invocation chains. NaviAgent separates planning from graph-based execution, and reports the highest TSR across models and task complexities on API-Bank and ToolBench, plus 12% higher TSR than ToolNet on DeepSeek-V3.

  • Problem

    Large, evolving tool ecosystems make multi-tool composition difficult because mismatches can accumulate along invocation chains, leading to brittle behavior and low scalability.

    Source: §1 · p. 1

  • Method

    NaviAgent separates high-level interaction decisions from execution, using TWNM to represent structural and behavioral tool dependencies and feedback to update the model and planning policy.

    Source: §1 · p. 2

  • Results

    NaviAgent achieves the highest TSR across models and task complexities on API-Bank (2k+ tools) and ToolBench (5k+ tools), and 12% higher TSR than ToolNet on DeepSeek-V3.

    Source: §1 · p. 2

  • Takeaways & Limitations

    NaviAgent scales to hundreds or thousands of tools with competitive efficiency and excels in complex, multi-tool tasks and larger models.

    Source: §5 · p. 9

    Handling heterogeneous tool interfaces and dynamic conditions remains a challenge.

    Source: §5 · p. 9

Abstract

from arXiv · show

Large Language Models (LLMs) increasingly act as function-call agents that invoke external tools to tackle tasks beyond their static knowledge. However, they typically invoke tools one at a time without a global view of task structure. As tools often depend on one another, this leads to error accumulation and poor scalability, particularly when scaling to hundreds or thousands of tools. To address these limitations, we propose NaviAgent, an explicit bilevel architecture that decouples task planning from tool execution through graph-based modeling of tool relations. At the planning level, the LLM-based agent decides whether to respond directly, clarify intent, or retrieve and execute a toolchain independent of inter-tool complexity. At the execution level, a Tool World Navigation Model (TWNM) encodes structural and behavioral relations among tools, steering the agent to compose scalable and robust invocation sequences. Incorporating feedback from real tool interactions, NaviAgent achieves closed-loop alignment between planning and execution, enabling adaptive navigation in large-scale tool ecosystems. Evaluations on API-Bank and ToolBench show consistent improvements in task success rate (TSR), with TWNM yielding an average gain of 13.1 points on complex tasks. Further tests on 50 real APIs across 7 domains show consistent gains of 4.3--12.0 points, with fewer steps and latency, demonstrating robust generalization under real-world dynamics.

1. Introduction

NaviAgent pairs high-level interaction decisions with graph-based toolchain construction and execution to address brittle composition in large, changing tool ecosystems. Its evaluations report strong benchmark and live-API performance.

1. Introduction

  • Large, evolving tool ecosystems make multi-tool composition difficult: mismatches can accumulate along invocation chains, producing brittle behavior and low scalability.The passage points to combinatorial growth in possible toolchains and frequent API changes.Source: §1 · p. 1
  • Existing approaches are described as either structured but static or adaptive but unstructured; a tool graph connects APIs through shared parameter nodes to represent dependencies and composability.The stated goal is coherent multi-tool planning across dynamic APIs.Source: §1 · p. 1
  • NaviAgent separates high-level decision making from tool execution, with planning choosing among direct response, clarification, toolchain retrieval, and tool execution.Rather than prescribing a complete API sequence in advance, execution dynamically constructs and revises toolchains.Source: §1 · p. 2
  • NaviAgent achieves the highest TSR across models and task complexities on API-Bank (2k+ tools) and ToolBench (5k+ tools), and 12% higher TSR than ToolNet on DeepSeek-V3.Evaluations also cover live APIs and report efficiency.Source: §1 · p. 2
  • TWNM models structural and behavioral tool dependencies and supports incremental integration of newly introduced or previously unseen tools.The graph supports retrieval, substitution, and multi-tool composition as the ecosystem evolves.Source: §1 · p. 2
  • Execution feedback jointly updates TWNM and the planning policy, forming a closed loop for adaptation to API changes.The paper also reports evaluations on 50 live APIs, with robust performance under dynamic real-world conditions.Source: §1 · p. 2

2. Related Work

Related work moves from single-tool invocation toward multi-tool orchestration and dynamic planning. The paper identifies a remaining gap in adapting tool relations under sparse interaction data and API change.

2. Related Work

  • Single-tool work spans predefined template chains, structured tool descriptions, documentation compression, self-supervised API use, and multimodal tool generalization.The passage names TALM, EasyTool, Toolformer, and GPT4Tools among the approaches.Source: §2 · p. 2
  • Multi-tool orchestration includes staged workflows, modular composition, execution feedback, hierarchical classification, and self-verification, but the cited approaches still face limits in dynamic collaboration.The passage distinguishes small-toolkit methods from approaches aimed at large-scale toolkits.Source: §2 · p. 2
  • Dynamic planning work adds reflection, branching search, hierarchy-guided DFS, or heuristic cost estimates, while the cited methods assume static tool relationships or have sparse multi-hop interaction data.The paper positions TWNM as jointly modeling structural dependencies and behavioral adaptations to capture evolving tool relations.Source: §2 · pp. 2–3

3. Methodology

NaviAgent separates high-level interaction decisions from graph-conditioned tool execution, then uses graph learning, search, feedback, and recovery to adapt toolchains. Its local mechanism-injection analysis characterizes feasible policy correction as a KL-minimal projection.

3.1.1. DEFINITION

  • NaviAgent models agent decisions over four actions—direct response, intent clarification, toolchain retrieval, and tool execution—using recent interaction history, the current observation, and a pruned tool subgraph.The graph is serialized in a tree-structured format for the agent’s decision context.Source: §3.1.1 · p. 3
  • The most recent three observation-action pairs achieve the best balance between accuracy and efficiency in the reported experiments.These pairs supply the agent’s recent decision trajectory.Source: §3.2.1 · p. 3, §3.1.1 · p. 3

3.2.1. GRAPH CONSTRUCTION AND REPRESENTATION

  • The tool graph combines API and parameter nodes with structural schema chains and behavioral dependencies inferred from usage, while a two-layer HGT aggregates information from each node’s 2-hop neighborhood for link prediction.Node features combine semantic and structural information, and attention incorporates statistical edge weights.Source: §3.2.1 · pp. 3–4

3.2.2. GRAPH TRAINING OBJECTIVE

  • The cross-entropy loss weight decays over training as the hybrid objective shifts emphasis from prediction accuracy toward discriminative embeddings for graded dependencies.The objective combines cross-entropy and adaptive-margin losses, with edge weights serving as soft labels and shaping margins for more critical dependencies.Source: §3.2.2 · p. 4

3.2.3. GRAPH SEARCH

  • At inference, predicted link probabilities become graph edge weights for weighted-graph search using either dynamic-threshold Alpha-Beta Pruning or heuristic fitness balancing connectivity, depth, and cumulative weights.The search methods eliminate weak toolchains or score candidate toolchains, respectively.Source: §3.2.3 · p. 4

3.2.4. GRAPH EVOLUTION

  • Graph evolution adds tools through semantic-similarity clustering, prunes obsolete or rarely used tools using failure rates and invocation frequencies, and periodically probes failed APIs for reactivation.Edge weights combine historical trends with recent success rates and serve as soft labels; asynchronous graph updates do not block online inference.Source: §3.2.4 · pp. 4–5

3.3. Dynamic Execution & Path Recombination

  • For complex queries, NaviAgent retrieves a task-relevant graph subgraph and feasible execution path, then recovers from tool failures through I/O-equivalent substitution, upstream rerouting, or subgraph switching.The recovery options address local API replacement, alternative upstream paths, or a new goal-oriented subgraph.Source: §3.3 · p. 5

3.4. A Local Variational View of Mechanism Injection

  • Within a fixed context and nonempty feasible action set, mechanism injection restricts the base policy to admissible actions and renormalizes it, yielding the unique local KL-minimal feasible correction.The theorem describes this local correction, not how graph- and execution-dependent feasible sets are generated or updated.Source: §3.4 · p. 6

4. Experiments

Experiments compare NaviAgent with tool-use baselines on ToolBench and evaluate it on API-Bank and live APIs, using task success and execution efficiency measures. Results cover overall performance, robustness as task difficulty rises, fine-tuning, and ablations of the architecture and TWNM.

4.1. Experimental Settings

  • Experiments use API-Bank and ToolBench simulations, 50 live RapidAPI endpoints, and Easy, Medium, and Hard tasks; TSR, Steps, and TCR measure success, efficiency, and completion.The evaluation also includes several foundation models and a fine-tuned Qwen2.5-14B model.Source: §4.1 · pp. 6–7, Table 1 · p. 7

4.2. Main Results

  • 35.8%, 45.4%, and 55.2% TSR on ToolBench with Qwen2.5-14B, Qwen2.5-32B, and DeepSeek-V3 outperform the strongest baseline by 7.8, 9.0, and 10.3 points, respectively.NaviAgent maintains moderate step counts of 4.38, 4.66, and 4.60 for those models.Source: Figure 4 · p. 7, §4.2 · p. 7
  • On Hard ToolBench tasks, NaviAgent exceeds the strongest baseline by 4.3–18.2 percentage points across backbones, and its TSR declines less from Easy to Hard.On DeepSeek-V3, relative TSR drops are 37.5% for NaviAgent, 57.1% for ToolNet, and 50.6% for α-UMI.Source: §4.2 · p. 7
  • With supervised fine-tuning, Qwen2.5-14B reaches 51.3% TSR versus 45.4% for Qwen2.5-32B, while TCR is 81.2% versus 83.2%.The comparison is reported for the D+N(Heur) row.Source: Figure 5 · p. 8, §4.2 · p. 8

4.3. Real-World Evaluation

  • On 50 live APIs across seven domains, NaviAgent achieves the highest TSR across backbones, beating the strongest baseline by 4.3–12.0 percentage points.The evaluation runs 303 queries, and NaviAgent remains more efficient than ToolNet, ToolPlanner, and α-UMI in steps and runtime.Source: Table 2 · p. 8, §4.3 · p. 8

4.4. Ablation Study

  • On ToolBench with DeepSeek-V3, adding the tool graph to ReAct raises TSR from 34.5% to 45.7%, while the bilevel design alone reaches 42.4%.Combining the designs raises TSR from 50.3% with unpruned search to 53.4% with Alpha-Beta and 55.2% with heuristic search.Source: Table 3 · p. 8, §4.4 · p. 8
  • Dynamic+A outperforms Static+A, especially on hard tasks; Dynamic+H adds consistent 2–3 TSR points across tasks and around 8 points on large-model hard cases.Dynamic+H combines a dynamic graph with heuristic pruning and corresponds to the proposed NaviAgent.Source: §4.4 · p. 8, Table 4 · p. 9
  • Successful trajectories frequently use clarification and re-retrieval, particularly on harder tasks, alongside the most common normal actions.The authors link these actions to resolving ambiguity and recovering from incomplete retrieval during multi-step planning.Source: §4.4 · pp. 8–9, Figure 6 · p. 9

5. Conclusion

NaviAgent separates high-level decisions from low-level execution over a Tool World Navigation Model (TWNM), reporting robust gains on ToolBench and API-Bank. The conclusion also notes remaining challenges in handling heterogeneous interfaces and dynamic conditions.

5. Conclusion

  • NaviAgent separates high-level decision making from low-level execution over a TWNM, with robust gains on ToolBench and API-Bank.The paper also reports real-world tests verifying effectiveness and stability, and says the framework scales to hundreds or thousands of tools with competitive efficiency.Source: §5 · p. 9
  • Heterogeneous tool interfaces and dynamic conditions remain challenges; unified protocols and adaptive graph construction are proposed as possible directions.The conclusion also identifies extending the evolving graph and decision space to multi-agent collaboration as a broader opportunity.Source: §5 · p. 9

Impact Statement

The impact statement presents NaviAgent as a framework for scalable tool reasoning in dynamic ecosystems, while Table 5 is titled as a standardization of API parameters.

Impact Statement

  • NaviAgent is presented as a framework for scalable tool reasoning in dynamic tool ecosystems, intended to enhance robustness to API changes and execution failures.The authors expect these advances to contribute to more reliable and sustainable agent systems in real-world environments.Source: Impact Statement · p. 10

A. Graph Construction

  • Table 5 is titled “Standardization of API Parameter.”The supplied passage gives the table title but not its contents.Source: Table 5 · p. 12

B. Details of Graph Method

The appendix details NaviAgent’s heterogeneous tool graph, graph-search and pruning methods, and case studies illustrating the four planning actions and iterative API use.

B.1. HGT Network

  • The HGT network builds node features from semantic descriptions and invocation statistics, then projects heterogeneous API and parameter nodes into a shared embedding space.It stacks two eight-head HGT layers to aggregate two-hop neighborhood information and uses final node embeddings to predict links.Source: §B.1 · p. 12

B.2. Graph Search Algorithm

  • Alpha-Beta backward pruning searches from a target node, using dynamic thresholds and a depth constraint to keep candidate dependency subgraphs compact.The method applies alpha-pruning at parameter nodes and beta-pruning at API nodes; its stated connectivity constraint limits path length to five.Source: §B.2 · pp. 13–14
  • Hybrid heuristic search combines simulated annealing and genetic-algorithm strategies to select candidate subgraphs using a composite fitness function.The fitness function weighs node compactness, parameter density, depth penalty, edge weights, and path complexity; searches for different target APIs are parallelized.Source: §B.2 · p. 13

C. Case Studies

  • For toolchain retrieval, TWNM receives up to three target APIs plus input and output parameters, searches the graph, and returns a serialized dependency tree to the LLM.The case-study description identifies four planning actions: direct response, intent clarification, toolchain retrieval, and tool execution with parameter validation and state monitoring.Source: C. Case Studies · p. 14

FIRST ROUND: INTENT ANALYSIS

  • The gastroenteritis example answers the general-knowledge question directly, then requests permission to retrieve an API for recording the user’s health data.The requested record includes user ID, blood pressure, heart rate, and timestamp; the example retrieves candidate APIs and invokes TWNM for their call chains.Source: FIRST ROUND: INTENT ANALYSIS · pp. 15–16

SECOND ROUND: ITERATIVE API CHAIN EXECUTION

FOURTH ROUND: API OUTPUT VERBALIZATION

C.2. Case 2

The cases illustrate how NaviAgent separates direct answers from API-dependent requests, clarifies missing information, retrieves toolchains, and verbalizes tool outputs.

C.2. Case 2

  • The Beijing question is answered directly, while the weather request is treated as requiring an API and is matched to candidate weather APIs for TWNM call-chain retrieval.The request supplies latitude and longitude, and the example selects an API using geographic coordinates.Source: §C.2 · pp. 18–19

THIRD ROUND: API OUTPUT VERBALIZATION

C.3. Case 3

  • For the vague tomorrow-weather request, the agent asks which city the user wants before retrieving an API.The example identifies location as a missing required parameter.Source: §C.3 · p. 20

SECOND ROUND: INTENT ANALYSIS

  • After the user specifies Beijing, the agent retrieves candidate forecast APIs and selects api-getweatherforecast for apjoy weather forecast as the target.TWNM is invoked to obtain corresponding call chains for the retrieved APIs.Source: SECOND ROUND: INTENT ANALYSIS · p. 21

LAST ROUND: API OUTPUT VERBALIZATION

D. Data Generation

The data-generation prompts construct API-call chains with strict parameter matching, so generated problems follow realistic API dependency logic.

D. Data Generation

  • Generated questions state leaf-API parameters, require a chain to the root API, and are resolved by the root API’s output.The chain is built from leaf to root, with the root called last.Source: D. Data Generation · p. 22
  • API parameters must inherit verbatim from the question or earlier API outputs, without synthetic values or value transformation.Parent outputs must match child inputs in parameter name and data type, and leaf outputs must be used downstream or in the final result.Source: D. Data Generation · p. 22
  • Generation is rejected when API dependencies, traceable input sources, or output-to-input compatibility are missing.The stated failure cases include missing parameter dependencies and outputs that do not meet the next API’s input requirements.Source: D. Data Generation · p. 22
  • The example call-chain format records API names, inputs, success status, and outputs passed to the next API.It illustrates leaf and root APIs, with values drawn from the question or preceding API responses.Source: D. Data Generation · p. 23

E.1. Dataset

The appendix specifies the datasets, model training, prompts, evaluation, and graph upkeep used to implement and assess NaviAgent.

E.1. Dataset

  • Table 6 reports sample counts and difficulty distributions for ToolBench and API-Bank.The supplied passage gives the table’s scope but no cell values.Source: Table 6 · p. 23, §E.1 · p. 23

E.2. Training

  • The model is fine-tuned from Qwen2.5-14B for 10 epochs using full-parameter tuning and an 8192-token maximum sequence length.Training uses AdamW with a 2e-5 learning rate and runs on 8 Ascend 910B 64G GPUs for 10 hours.Source: §E.2 · p. 23

E.3.1. NAVIAGENT INFERENCE PROMPTS

  • Inference prompts use hierarchical decisions to choose among direct answering, clarification, API retrieval, and API calls while resolving dependencies and parameters.They decompose compound requests into ordered sub-intents, prioritize dependencies, and handle known API failures.Source: §E.3.1 · p. 24

E.3.2. INPUT GENERATION PROMPTS

  • Input-generation prompts combine the user query with observations to produce a complete final response and disclose failed-API data limitations.The output is required to be natural and fluent English.Source: §E.3.2 · p. 27

E.3.3. API SIMULATOR PROMPTS

  • The API simulator prioritizes historical matching, then structural cloning, then contextual simulation when generating standardized JSON responses.For an existing API with identical inputs it returns historical outputs; for a new API it creates mock data, using similar call-chain outputs first.Source: §E.3.3 · p. 27

E.3.4. SIMULATED USER RESPONSE AGENT PROMPTS

  • The simulated user-response agent returns only existing, queried parameter values from the API chain, without modification.It filters out uninvoked or null parameters and merges multiple requested values into one response.Source: §E.3.4 · p. 28

E.4.1. EVALUATION PROMPTS

  • The evaluation prompt checks call-path logic, answer completeness, and output accuracy against reference paths without requiring exact API-name or parameter-format matches.It flags fictitious or illegal parameters, execution errors, and answers that omit core information.Source: §E.4.1 · pp. 28–29

E.5. Graph Maintenance overhead

  • Successful or failed tool calls update local graph-node attributes asynchronously in 55 ms, while new tools are inserted in under 100 ms each.Full graph retraining runs offline in 94 seconds on one NVIDIA P40, then is hot-swapped asynchronously.Source: §E.5 · p. 30

F.1. Runtime Experiments

Runtime experiments report a speed–performance trade-off among NaviAgent variants, improvements from pruning and reactivation, and API-Bank results consistent with ToolBench.

F.1. Runtime Experiments

  • On ToolBench, Dynamic+A consistently achieves lower runtime across models; for DeepSeek-V3, it reduces runtime by 15 seconds versus Base (55.8 seconds), a relative improvement of approximately 26.9%.Dynamic+H demonstrates optimal overall performance but has higher runtime induced by heuristic strategies.Source: §F.1 · p. 30

F.2. Pruning and Reactivation

  • 4.0 percentage points: dynamic pruning and reactivation raise TSR from 44.0% to 48.0% and reduce average steps from 5.12 to 4.72.The setting samples 50 ToolBench queries, makes 10% of APIs unavailable in Phase 1, and assumes recovery in Phase 2.Source: §F.2 · p. 31, Table 8 · p. 31

F.3. Experiments on API-Bank

  • API-Bank outcomes are reported as consistent with the ToolBench-based experiments.The supplied passages do not provide the API-Bank table values.Source: §F.3 · p. 31, Table 9 · p. 31

H. Action-level ablation.

Action-level ablations favor explicit clarification and separated retrieval and execution; the appendix gives a local feasibility-based interpretation of policy correction, not a global model of TWNM evolution.

H. Action-level ablation.

  • 5.8 percentage points: removing clarification lowers ToolBench TSR from 53.4% to 47.6%; merging retrieval and execution lowers it to 50.8%.The ablation uses DeepSeek-V3; its table is identified as Table 11.Source: H. Action-level ablation · p. 32, Table 11 · p. 32

I. A Local Variational View of Mechanism Injection

  • The appendix limits its variational claim to one context-dependent local decision step rather than the full TWNM-driven dynamic policy.Admissible actions can change with graph evolution, retrieval outcomes, runtime failures, and path recombination.Source: §I · p. 32

I.1. Setup: contexts, actions, and feasible sets

  • The setup assigns each context a nonempty feasible action set, which may reflect the current history, observation, graph state, pruning, or recovery operation.A reference policy and a distribution over contexts are also specified.Source: §I.1 · p. 32

I.2. KL-minimal feasible correction

  • Under the support assumption, the unique KL-minimal feasible correction restricts the base policy to feasible actions and renormalizes it.The result identifies the local correction once the feasible set is specified.Source: §I.2 · p. 33

I.3. Idempotence of the feasible projection

  • Once a policy is supported on the feasible set at every context, applying the same projection again produces no further change.The proposition states idempotence whenever its denominator is positive.Source: §I.3 · p. 33

I.4. Graph-conditioned interpretation for NaviAgent

  • The graph-conditioned feasible set represents actions currently admissible under TWNM, but the theorem does not model how graph evolution produces those sets.The full system may generate them through pruning, I/O-equivalent substitution, upstream rerouting, or subgraph switching.Source: §I.4 · p. 34

I.5. Hard-rule result as a singleton special case

I.5 presents the hard rule as a singleton case of context-dependent feasible-set projection; I.6 limits the result to an interpretive abstraction and sketches a soft extension that is not pursued.

I.5. Hard-rule result as a singleton special case

  • The rule requiring q after p is a singleton case of context-dependent feasible-set projection, with the projected policy uniquely solving the stated KL problem.The result assumes the base policy assigns positive probability to q in relevant contexts where the previous action is p.Source: §I.5 · p. 34
  • For contexts following p, projection assigns all probability to q; in other contexts, it leaves the base policy unchanged.The feasible set is {q} after p and the full action space elsewhere.Source: §I.5 · p. 34

I.6. Remarks

  • The result does not characterize the full TWNM dynamics as a fixed convex projection problem; it isolates a local inference-time correction for a specified admissible region.That correction is the smallest KL shift from the base policy that enforces the region.Source: §I.6 · p. 35
  • The projection acts as a gradient-free inference-time wrapper that edits the decision rule’s support and renormalizes probability mass without changing model parameters.This distinguishes the wrapper from fine-tuning.Source: §I.6 · p. 35
  • A proposed soft extension would reweight actions using a context-dependent mechanism score, but the appendix does not pursue it.The hard projection is recovered when the score takes values 0 or −∞.Source: §I.6 · p. 35

Related papers

Loading 2506.19500v3…