NaviAgent: Scalable Tool Orchestration for Oxygen Agents via Graph‑Driven Bilevel Planning

Abstract

Large language models (LLMs) are increasingly used as function‑calling agents, but they typically invoke a single tool at a time and lack a global view of task structure. This leads to error accumulation and poor scalability when the tool pool grows to hundreds or thousands of APIs. NaviAgent addresses these limitations with an explicit double‑layer architecture that decouples task planning from tool execution by modeling tool dependencies as a dynamic graph.

Motivation

Early tool‑enhanced LLMs focus on single‑tool usage: the model selects one appropriate API and generates its parameters. Real‑world tasks often require multiple tools in sequence (e.g., retrieving user info, then order ID, then order status), creating explicit data dependencies between tools. As the number of tools increases, the agent must not only pick the correct API but also verify that each tool’s output satisfies the input requirements of the next tool, turning the problem from "choose one tool" into "plan an executable tool chain".

Limitations of Existing Methods

Current frameworks fall into two categories. The first embeds tool knowledge into model parameters, which requires retraining whenever APIs change. The second builds a tool graph from historical call traces; however, sparse multi‑hop data leads to incomplete coverage and cannot capture parameter flow. Even methods that adapt based on execution feedback still lack a unified global structure, relying on local trial‑and‑error.

Proposed Framework

NaviAgent introduces four capabilities:

Explicitly model API and parameter relationships in a heterogeneous graph.

Learn real‑world calling patterns from historical execution data.

Dynamically update the graph when APIs are added, removed, or restored.

Separate high‑level decision making from complex tool‑chain search.

Interaction Decision

In the planning layer, the LLM does not select a concrete API. Instead, it first decides which of four interaction actions to take:

Direct Response : the model believes it has enough information and generates an answer.

Intent Clarification : the user request is ambiguous and needs further clarification.

ToolChain Retrieval : the model queries the tool graph to plan a subsequent tool chain.

Tool Execution : the model executes a previously determined tool call.

The decision process can be expressed as a function of the previous interaction history, the current observation, and the updated tool‑graph state, producing the next action.

Graph‑Driven Tool Navigation

The Tool World Navigation Model (TWNM) builds a heterogeneous graph G = (V, E, W) where nodes represent APIs and parameters, and edges encode static API specifications and dynamic behavior learned from execution logs. TWNM performs four steps:

Graph Construction : create API and parameter nodes; connect APIs via shared parameters.

Graph Representation Learning : use a Heterogeneous Graph Transformer (HGT) trained with link‑prediction to embed nodes and edges, capturing both static dependencies and learned behavior weights.

Graph Search : given a task, search the graph for a path that satisfies input‑output constraints. Two strategies are offered: Alpha‑Beta Pruning for fast pruning of low‑value paths, and Hybrid Heuristic Pruning that considers edge weights, path length, and parameter coverage for higher‑quality chains.

Graph Evolution : continuously update edge weights with an exponential moving average of recent success rates, add new APIs, and prune obsolete ones, allowing the graph to adapt to a changing API ecosystem.

When a tool call fails, the Path Recombination mechanism attempts local repair by (1) substituting an equivalent API, (2) backtracking to an upstream node and replanning, or (3) retrieving a new sub‑graph if the current one is unusable.

Experiments

Main Results : On the API‑Bank and ToolBench benchmarks, NaviAgent consistently improves Task Success Rate (TSR). For example, on the Hard subset of ToolBench with the DeepSeek‑V3 model, TSR reaches 44.9 %, a gain of 18.2 % over the best baseline. Improvements stem from more accurate planning rather than longer execution sequences.

Ablation Study : Adding only the tool graph to a ReAct baseline raises TSR from 34.5 % to 45.7 %, confirming the benefit of explicit dependency modeling. Incorporating the double‑layer planner further improves performance, and the combination of planner, graph, and heuristic search yields the highest TSR of 55.2 %.

Dynamic Graph Analysis : Replacing a static graph with a dynamic one that incorporates recent call success rates boosts Hard‑task TSR (e.g., Qwen2.5‑32B improves from 26.3 % to 31.4 %). Adding heuristic search on top of the dynamic graph achieves the best overall results.

Behavior Analysis : NaviAgent exhibits higher rates of Intent Clarification and Re‑retrieval on difficult tasks, indicating that it actively refines its plan based on execution feedback rather than relying on a single, possibly erroneous, tool chain.

Conclusion

NaviAgent demonstrates that a "LLM planning + graph navigation" double‑layer design can overcome the scalability and planning challenges of large‑scale tool orchestration. By explicitly modeling API‑parameter structures, continuously learning from execution feedback, and providing robust path recovery, the system achieves higher success rates, fewer steps, and lower latency across both synthetic benchmarks and real‑world API environments.