NaviAgent: Graph-Driven Bilevel Planning for Scalable Tool Orchestration

Yan Jiang, Hao Zhou, Lizhong Gu, Tianlong Li, Ruinan Jin, Wanqi Zhou, Ai Han
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:53472-53506, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-jiang26be, title = {{N}avi{A}gent: {G}raph-{D}riven Bilevel Planning for Scalable Tool Orchestration}, author = {Jiang, Yan and Zhou, Hao and Gu, Lizhong and Li, Tianlong and Jin, Ruinan and Zhou, Wanqi and Han, Ai}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {53472--53506}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/jiang26be/jiang26be.pdf}, url = {https://proceedings.mlr.press/v306/jiang26be.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T NaviAgent: Graph-Driven Bilevel Planning for Scalable Tool Orchestration %A Yan Jiang %A Hao Zhou %A Lizhong Gu %A Tianlong Li %A Ruinan Jin %A Wanqi Zhou %A Ai Han %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-jiang26be %I PMLR %P 53472--53506 %U https://proceedings.mlr.press/v306/jiang26be.html %V 306 %X 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.
APA
Jiang, Y., Zhou, H., Gu, L., Li, T., Jin, R., Zhou, W. & Han, A.. (2026). NaviAgent: Graph-Driven Bilevel Planning for Scalable Tool Orchestration. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:53472-53506 Available from https://proceedings.mlr.press/v306/jiang26be.html.

Related Material