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

Pratyay Banerjee, Ankit Chadha


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 Tau-retail at 3.2 X compression (p<0.01), +8.7,pp on BrowseComp at 2.2 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 load-bearing: 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.
Anthology ID:
2026.findings-emnlp.2008
Volume:
Findings of the Association for Computational Linguistics: EMNLP 2026
Month:
October
Year:
2026
Address:
Budapest, Hungary
Editors:
Hung-Yi Lee, Sunipa Dev, Jessy Li, Desmond Elliott
Venue:
Findings
SIG:
SIGDAT
Publisher:
Association for Computational Linguistics
Note:
Pages:
42756–42765
Language:
URL:
https://aclanthology.org/2026.findings-emnlp.2008/
DOI:
Bibkey:
Cite (ACL):
Pratyay Banerjee and Ankit Chadha. 2026. Routed Graph Handoff: Adaptive Format Selection for Multi-Agent LLM Delegation. In Findings of the Association for Computational Linguistics: EMNLP 2026, pages 42756–42765, Budapest, Hungary. Association for Computational Linguistics.
Cite (Informal):
Routed Graph Handoff: Adaptive Format Selection for Multi-Agent LLM Delegation (Banerjee & Chadha, Findings 2026)
Copy Citation:
PDF:
https://aclanthology.org/2026.findings-emnlp.2008.pdf