NaviAgent: Tool Orchestration for Oxygen Agents via LLM Planning and Graph Navigation

Motivation

Existing tool‑enhanced language models typically invoke a single tool at a time and make decisions based only on local information. Real‑world tasks often require a chain of dependent tools (e.g., retrieving user info, then order ID, then order status), leading to parameter mismatches, error accumulation, and poor scalability when the number of available APIs reaches hundreds or thousands.

Limitations of Prior Approaches

Most methods fall into two categories:

Embedding tool knowledge into model parameters, which requires retraining when APIs change.

Building static tool graphs from historical co‑occurrence, which cannot cover unseen multi‑hop paths or capture dynamic execution feedback.

Both lack a unified global view of tool dependencies and rely on local trial‑and‑error planning.

Proposed Framework: NaviAgent

NaviAgent adopts a double‑layer architecture:

Planning Layer : an LLM decides the next interaction action—direct response, intent clarification, tool‑chain retrieval, or tool execution—without selecting a concrete API.

Execution Layer : the Tool World Navigation Model (TWNM) encodes the dynamic graph of tool and parameter nodes and searches for feasible tool chains.

Interaction Action Space

Direct Response – the model answers directly when it has sufficient information.

Intent Clarification – the model asks the user to resolve ambiguity.

ToolChain Retrieval – the model queries the tool graph to plan the next chain.

Tool Execution – the model executes the selected API call.

Tool World Navigation Model (TWNM)

TWNM consists of four stages:

Graph Construction : Build a heterogeneous graph G = (V, E, W) where V includes API nodes and parameter nodes, and edges represent static API specifications and dynamic execution feedback.

Graph Representation Learning : Use a Heterogeneous Graph Transformer (HGT) trained with link‑prediction to learn node embeddings that capture both static dependencies and learned execution reliability.

Graph Search : Given a task, search the graph for a path satisfying input‑output constraints. Two strategies are provided: Alpha‑Beta Pruning for fast pruning and Hybrid Heuristic Pruning that balances edge weight, path length, and parameter coverage.

Graph Evolution : Continuously update edge weights using an exponential moving average of recent success rates, allowing the graph to adapt to newly added APIs, deprecated APIs, or changing reliability.

During execution, the model observes three symbols: historical interaction (

), current observation (

), and the updated graph state (

). The model outputs the next action based on this combined information.

Dynamic Execution and Path Recovery

When a tool call fails, NaviAgent employs a Path Recombination mechanism with three recovery strategies:

Replace the failed API with an equivalent one that has matching input/output signatures.

Backtrack to an upstream node and re‑plan the remaining path.

If the sub‑graph is entirely unusable, retrieve a new sub‑graph to complete the task.

This localized repair reduces the need for full re‑planning and improves latency.

Experiments

Main Results

Evaluated on API‑Bank and ToolBench, NaviAgent consistently raises the Task Success Rate (TSR). On ToolBench, TWNM alone improves average TSR by 13.1 points on complex tasks. Testing on 50 real APIs across seven domains shows TSR gains of 4.3–12.0 points, fewer steps, and lower latency.

Table 1 compares NaviAgent with ReAct, ToolLLM, ToolPlanner, etc., using three base LLMs (Qwen2.5‑14B, Qwen2.5‑32B, DeepSeek‑V3). NaviAgent achieves the highest TSR on all models, especially on Hard tasks where it outperforms the best baseline by up to 18.2 %.

Ablation Study

Table 3 isolates each component. Adding only the tool graph raises TSR from 34.5 % to 45.7 %; adding only the dual‑layer planner also improves performance. Combining graph, dual‑layer planning, and search yields the best TSR of 55.2 %.

Table 4 examines static vs. dynamic graphs and search strategies. Dynamic graphs with historical feedback (Dynamic + A) improve Hard‑task TSR (e.g., Qwen2.5‑32B from 26.3 % to 31.4 %). Adding heuristic search (Dynamic + H) achieves the overall peak performance, confirming that both dynamic structure and sophisticated search are essential.

Behavior Analysis

Figure 6 shows that NaviAgent executes a higher proportion of Intent Clarification and Re‑retrieval actions than baselines, especially on difficult tasks, indicating its ability to adaptively refine tool chains based on execution feedback.

Conclusion

NaviAgent addresses the lack of global planning and poor scalability in large‑scale tool orchestration by decoupling LLM interaction decisions from graph‑driven tool search. The explicit modeling of API‑parameter dependencies, continuous graph evolution, and dual‑layer planning together deliver higher success rates, fewer steps, and lower latency across both benchmark and real‑world API environments.