# NaviAgent: Graph-Driven Bilevel Planning for Scalable Tool Orchestration

arXiv: https://arxiv.org/abs/2506.19500 · HTML: https://mlsanity.com/paper/2506.19500/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 39 references that are in the map.
- First posted on arXiv 24 Jun 2025.

## Builds on (most cited first, 30 of 31)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [API-Bank: A Comprehensive Benchmark for Tool-Augmented LLMs](https://mlsanity.com/paper/2304.08244/) (2023)
- [Chameleon: Plug-and-Play Compositional Reasoning with Large Language Models](https://mlsanity.com/paper/2304.09842/) (2023)
- [GPT4Tools: Teaching Large Language Model to Use Tools via Self-instruction](https://mlsanity.com/paper/2305.18752/) (2023)
- [Tool Learning with Large Language Models: A Survey](https://mlsanity.com/paper/2405.17935/) (2024)
- [Convolutional Neural Networks for Medical Image Analysis: Full Training or Fine Tuning?](https://mlsanity.com/paper/1706.00712/) (2017)
- [TALM: Tool Augmented Language Models](https://mlsanity.com/paper/2205.12255/) (2022)
- [EASYTOOL: Enhancing LLM-based Agents with Concise Tool Instruction](https://mlsanity.com/paper/2401.06201/) (2024)
- [ToolChain*: Efficient Action Space Navigation in Large Language Models with A* Search](https://mlsanity.com/paper/2310.13227/) (2023)
- [Small LLMs Are Weak Tool Learners: A Multi-LLM Agent](https://mlsanity.com/paper/2401.07324/) (2024)
- [Making Language Models Better Tool Learners with Execution Feedback](https://mlsanity.com/paper/2305.13068/) (2023)
- [Confucius: Iterative Tool Learning from Introspection Feedback by Easy-to-Difficult Curriculum](https://mlsanity.com/paper/2308.14034/) (2023)
- [ToolNet: Connecting Large Language Models with Massive Tools via Tool Graph](https://mlsanity.com/paper/2403.00839/) (2024)
- [ControlLLM: Augment Language Models with Tools by Searching on Graphs](https://mlsanity.com/paper/2310.17796/) (2023)
- [Can Graph Learning Improve Planning in LLM-based Agents?](https://mlsanity.com/paper/2405.19119/) (2024)
- [Tool-Planner: Task Planning with Clusters across Multiple Tools](https://mlsanity.com/paper/2406.03807/) (2024)
- [TOOLVERIFIER: Generalization to New Tools via Self-Verification](https://mlsanity.com/paper/2402.14158/) (2024)
- [Learning Evolving Tools for Large Language Models](https://mlsanity.com/paper/2410.06617/) (2024)
- [Concise and Precise Context Compression for Tool-Using Language Models](https://mlsanity.com/paper/2407.02043/) (2024)
- [ToolFactory: Automating Tool Generation by Leveraging LLM to Understand REST API Documentations](https://mlsanity.com/paper/2501.16945/) (2025)

## Built on by (most cited first, 3 of 3)

- [ToolLIFT: Lifting Tool-Specific Trajectories into Function-Level Graphs for Generalizable Tool Planning](https://mlsanity.com/paper/2608.03468/) (2026)
- [Learning What to Activate: Combinatorial Capability Allocation for Long-Horizon Multimodal Agents](https://mlsanity.com/paper/2609.27869/) (2026)
- [Towards Reliable AI Data Scientists: Data Agents with Workflow Harnesses](https://mlsanity.com/paper/2609.35255/) (2026)

## Abstract (arXiv)

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.