Routed Graph Handoff: Adaptive Format Selection for Multi-Agent LLM Delegation

Pratyay Banerjee; Ankit Chadha

cs.CLAug 26, 2026

Routed Graph Handoff: Adaptive Format Selection for Multi-Agent LLM Delegation

Authors: Pratyay Banerjee, Ankit Chadha

Organizations: Amazon, AGI / Sunnyvale, USA

Abstract

Multi-agent LLM systems coordinate through natural-language messages that consume 40--60% of their token budget. Replacing these with structured graphs reduces cost but fails on tasks requiring adaptive reasoning. We propose Routed Graph Handoff, where a lightweight LLM router (155 tokens, 0.15% overhead) selects between a typed dependency graph and natural language for each delegation. On four benchmarks (1,050+ trajectories), the routed system matches or exceeds NL-only on every task: +12.7,pp on $τ$ -retail at 3.2 $\times$ compression ( $p{<}0.01$ ), +8.7,pp on BrowseComp at 2.2 $\times$ compression ( $p{<}0.05$ ), and parity on BFCL and AppWorld. Without the router, graph-only delegation regresses 14.6,pp on AppWorld; the router eliminates this at near-zero cost. A graph-aware executor prompt is required: the same schema without interpretation guidance yields no gain. An oracle analysis reveals 8.6,pp of additional headroom, motivating execution-time adaptive routing as future work.

Figures & tables

Panel of Figure 1 — Figure 1: System overview. The router (one LLM call) selects Graph (typed DAG, 2 $\times$ compression) or NL (prose fallback) per task.

System	Browse.	$\boldsymbol{\tau}$ -ret.	BFCL	AppW.
NL only	38.7	12.0	75.3	51.7
NGH only	47.3	24.7	75.4	37.1
Routed	47.3	24.7	75.4	51.7
Oracle	—	—	—	60.3

Table 1: Main results (task success / accuracy %). Routed matches or exceeds NL on all four benchmarks.

\tau

-retail: +12.7 pp (150 paired trials,

p{<}0.01

). BrowseComp: +8.7 pp, CI [+2.7, +14.7],

p{<}0.05

. AppWorld NGH-only regresses

-

14.6 pp; the router recovers parity.

	Protocol	TSR	$\Delta$	95% CI	Comp.
	NL baseline	12.0	—		1.0 $\times$
schema	Routed NGH	24.7	+12.7	[+6.0, +19.3]	3.2 $\times$
	RL Qwen 1.5B	20.7	+8.7	[2.0, 15.3]	10.7 $\times$
	T5 Autoenc.	20.0	+8.0	[1.3, 14.7]	7.7 $\times$
	Hybrid	19.3	+7.3	[0.7, 14.0]	6.2 $\times$
	LLMLingua-2	18.7	+6.7	[0.7, 13.3]	5.2 $\times$

Table 2:

\tau

-retail protocol comparison (50 tasks

\times

3 seeds = 150 trials each). Bold CIs exclude zero. All schema-aware methods outperform all schema-unaware methods. Routed NGH is the only zero-training protocol in the top 5.

Pattern	n	NL%	NGH%	$\Delta$
aggregate	15	46.7	53.3	+6.7
iterate	43	27.9	20.9	$-$ 7.0
simple	50	68.0	52.0	$-$ 16.0
multi_app	33	48.5	39.4	$-$ 9.1
conditional	11	54.5	36.4	$-$ 18.2

Table 3: AppWorld by task computational pattern (152 paired). Graph helps only on aggregate tasks; NL dominates on all patterns requiring adaptive reasoning.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	NL	Routed	$\Delta$
BrowseComp	65	68	+3
BFCL	82	85	+3
AppWorld	50	52	+2

Appendix

Table 4: Task success / accuracy (%) with GPT-5 mini as orchestrator. Routed improves over the NL handoff on every family, matching the direction of the main Sonnet 4.5 results and adding accuracy portability to the format-portability check in Appendix F .

Per delegation ( $\tau$ -retail)	NL	Routed
Router call	—	155
Handoff tokens generated	730	226
Graph-aware executor prefill	—	${\sim}$ 80
Total tokens	730	461 (1.6 $\times$ )
Est. handoff latency	${\sim}$ 12 s	${\sim}$ 5 s

Appendix

Table 5: Full per-delegation token and latency accounting on

\tau

-retail. Token counts are measured; latency is estimated at standard Sonnet 4.5 decoding (

{\sim}

65 output tok/s after

{\sim}

0.5 s to first token). Even after adding the router call and the graph-aware executor prefill, the graph path totals fewer tokens than NL.

Explore similar work

GraphPlanner: Graph Memory-Augmented Agentic Routing for Multi-Agent LLMs
Apr 26, 2026Tao Feng, Haozhen Zhang, Zijie Lei +2Multi-Agent LLM Systems LLM Agent Orchestration
Department of Computer Science University of Illinois Urbana-Champaign Urbana, IL, USA
RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning
Mar 6, 2026Yuhang Liu, Ruijie Wang, Yunlong Chu +4LLM Reasoning with Graphs Efficient Language Model Reasoning
School of New Media and Communication, Tianjin University, Tianjin, China · School of Computer Science and Engineering, Beihang University, Beijing, China · Shanghai Jiao Tong University, Shanghai, China
Focus Is All You Need: Adaptive Goal-aware Attention Orchestration for Multi-Agent Graph Systems
Jul 26, 2026Mingzhou Fan, Siyuan Xu, Mingxuan YuanMulti-Agent System Optimization LLM Agent Orchestration

Apr 26, 2026J/K move · Enter open · S save

GraphPlanner: Graph Memory-Augmented Agentic Routing for Multi-Agent LLMs

Tao Feng, Haozhen Zhang, Zijie Lei, Peixuan Han+1

Department of Computer Science University of Illinois Urbana-Champaign Urbana, IL, USA

Multi-Agent LLM Systems LLM Agent Orchestration LLM Agent Workflow Optimization Graph-Based Agent Memory LLM Routing LLM Agent Routing+1

Open paper AskPDF arXiv

LLM routing has achieved promising results in integrating the strengths of diverse models while balancing efficiency and performance. However, to support more realistic and challenging applications, routing must extend into agentic LLM settings, where task planning, multi-round cooperation among heterogeneous agents, and memory utilization are indispensable. To address this gap, we propose GraphPlanner, a heterogeneous graph memory-augmented agentic router for multi-agent LLMs that generates routing workflows for each query and supports both inductive and transductive inference. GraphPlanner formulates workflow generation as a Markov Decision Process (MDP), where at each step it selects both the LLM backbone and the agent role, including Planner, Executor, and Summarizer. By leveraging a heterogeneous graph, denoted as GARNet, to capture interaction memories among queries, agents, and responses, GraphPlanner integrates historical memory and workflow memory into richer state representations. The entire pipeline is optimized with reinforcement learning, jointly improving task-specific performance and computational efficiency. We evaluate GraphPlanner across 14 diverse LLM tasks and demonstrate that: (1) GraphPlanner outperforms strong single-round and multi-round routers, improving accuracy by up to 9.3% while reducing GPU cost from 186.26 GiB to 1.04 GiB; (2) GraphPlanner generalizes robustly to unseen tasks and LLMs, exhibiting strong zero-shot capabilities; and (3) GraphPlanner effectively leverages historical memories, supporting both inductive and transductive inference for more adaptive routing. Our code for GraphPlanner is released at https://github.com/ulab-uiuc/GraphPlanner.

Abstract

Explore similar work

GraphPlanner: Graph Memory-Augmented Agentic Routing for Multi-Agent LLMs

RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning

Focus Is All You Need: Adaptive Goal-aware Attention Orchestration for Multi-Agent Graph Systems