Research map / Multi-agent systems and games / LLM agents

NaviAgent: Graph‑Driven Bilevel Planning for Scalable Tool Orchestration

ICML 2026 · Multi-agent systems and games › LLM agents · approach: LLM multi-agent collaboration and safety · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes NaviAgent, a bilevel LLM tool-use agent that chooses among four actions while a graph model (TWNM, HGT-based link prediction plus graph search) plans toolchains and recovers from API failures, evaluated on ToolBench, API-Bank and 50 live RapidAPI endpoints.

Problem

LLM function-call agents invoke tools one at a time without global task structure, so errors accumulate and scaling to hundreds or thousands of tools is poor; tool dependencies are also brittle to API changes.

Approach

Decouple high-level action selection (direct response, clarification, toolchain retrieval, execution) from low-level execution over a tool graph (TWNM) that combines structural API-schema edges and behavioral invocation-statistics edges, learned with a hybrid CE/adaptive-margin link-prediction loss and searched with alpha-beta or heuristic search, with closed-loop updates from execution feedback.

Key results

• On ToolBench overall, NaviAgent reaches 55.2% TSR with DeepSeek-V3 versus 44.9% for the strongest baseline (ToolNet), and 35.8% with Qwen2.5-14B.
• On 50 live RapidAPI endpoints, NaviAgent achieves 64.6% TSR with DeepSeek-V3, 4.3 to 12.0 points above the strongest baseline.
• Ablation on ToolBench with DeepSeek-V3 shows ReAct at 34.5% TSR rising to 55.2% with bilevel design, tool graph and heuristic search combined.

Surprising findings

• Under SFT, the 14B model reaches TSR comparable to the 32B model (51.3% vs 45.4%), though TCR is nearly the same (81.2% vs 83.2%).
• Some baseline rows on ToolBench have TSR values lower than their own Easy-tier values on Hard tasks with higher TCR, suggesting TCR and TSR decouple substantially.

Limitations

• Evaluation relies on simulated environments for ToolBench and API-Bank, and only 50 live APIs for real-world tests.
• TSR is judged via LLM comparison with ground truth, so evaluation depends on an unnamed judge model.
• Many hand-set hyperparameters (alpha, beta, temperature, fitness weights) with limited justification.

Experimental setup

Datasets: API-Bank ToolBench RapidAPI live APIs (50 APIs, 303 queries)

Benchmarks: ToolBench API-Bank RapidAPI live APIs

Metrics: TSR TCR Steps Time

Baselines: ReAct ToolLLM ToolNet ToolPlanner alpha-UMI ToolChain

Builds on: ReAct ToolLLM ToolNet Heterogeneous Graph Transformer

Closest papers by meaning

• ToolChain*: Efficient Action Space Navigation in Large Language Models with A* Search (ICLR 2024 · similarity 0.88)
• ToolTree: Efficient LLM Tool Planning via Dual-Feedback Monte Carlo Tree Search and Bidirectional Pruning (ICLR 2026 · similarity 0.87)
• T1: A Tool-Oriented Conversational Dataset for Multi-Turn Agentic Planning (NeurIPS 2025 · similarity 0.87)
• Beyond Accuracy: A Cognitive Load Framework for Mapping the Capability Boundaries of Tool-use Agents (AAAI 2026 · similarity 0.86)
• JADE: Bridging the Strategic-Operational Gap in Dynamic Agentic RAG (ICML 2026 · similarity 0.86)
• Tool-Planner: Task Planning with Clusters across Multiple Tools (ICLR 2025 · similarity 0.86)