NaviAgent: Graph‑Driven Bilevel Planning for Scalable Tool Orchestration

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.

Large language models can now use external tools, such as search engines, calculators, or online APIs, to answer questions they cannot solve from memory alone. But they often choose and call these tools one at a time, without planning the overall process. When many tools are available and some depend on others, this can cause mistakes to compound and make the system slow or unreliable. We introduce NaviAgent, a framework that separates high-level planning from tool execution. It first decides whether to answer directly, ask for clarification, or use a sequence of tools. It then uses a graph of tool relationships to decide which tools to use and in what order, while adapting based on real interaction feedback. Across benchmark datasets and 50 real-world APIs from 7 domains, NaviAgent completes tasks more successfully while using fewer steps and less time. These results suggest that better planning can help AI systems use large collections of tools more reliably in realistic settings.