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

Banerjee, Pratyay; Chadha, Ankit

doi:10.48550/arXiv.2608.25277

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

Pratyay Banerjee, Ankit Chadha

Multi-agentEMNLP 2026, accepted, to appear · Amazon
Accepted to EMNLP 2026. The proceedings have not been published yet, so this page cites the arXiv version. arXiv comment field, verified 2026-09-15: "Accepted in EMNLP 2026".

PDF arXiv BibTeX

In one sentence

An extra classifier call picks per task whether one AI agent sends work to another as a dependency graph or as prose, gaining 12.7 points on τ-retail and preventing a 14.6-point loss on AppWorld.

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× 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 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.

Why it matters

Most multi-agent LLM systems pass work between agents as free prose, which is where most of their failures come from: 76% of failures in the authors' analysis were the receiving agent misreading order or dropping prerequisites. Swapping prose for a typed graph fixes ordering but breaks tasks that need improvisation. The practical takeaway is that one cheap extra classification call, 155 tokens, recovers the better format per task, so you get the accuracy gain without the regression.

Key results

Raises Task Success Rate on τ-bench retail from 12.0 to 24.7, a +12.7 pp gain with 95% CI [+6.0, +19.3] and p<0.01 over the NL-only prose handoff baseline, at 3.2× handoff compression.
Raises Pass@1 accuracy on BrowseComp from 38.7 to 47.3, a +8.7 pp gain with CI [+2.7, +14.7] and p<0.05 over NL-only, while being 22% cheaper at 2.2× compression.
Null or negativeGraph-only delegation without the router drops AppWorld Task Success Rate from 51.7 to 37.1, a −14.6 pp regression with CI [−22.8, −6.4]; the router recovers exact parity (51.7% vs 51.7%) by sending 89% of AppWorld tasks to prose rather than beating the baseline.
Null or negativeOn BFCL v3 the routed system is a statistical tie with the prose baseline, 75.4 versus 75.3 AST match accuracy, so the graph handoff adds no measurable accuracy there despite 2.0× compression.
In an 8-protocol comparison on the same pinned 50 τ-retail tasks, Routed NGH reaches the highest TSR at 24.7 (+12.7 pp) with no training, ahead of a GRPO-finetuned Qwen 1.5B compressor at 20.7 (+8.7 pp), a T5 autoencoder at 20.0 (+8.0 pp) and off-the-shelf LLMLingua-2 at 18.7 (+6.7 pp).
Null or negativeThe per-task oracle reaches 60.3% TSR on AppWorld against the router's 51.7%, so 8.6 pp of achievable headroom is left unclaimed, of which 3.4 pp is attributed to outright router mistakes.

Every number above appears in the paper. Results that were null or went the wrong way are included and marked.

A 155-token router call sends each task to either a 357-token typed graph handoff or a 576-token prose handoff. — Figure 1: System overview. The router (one LLM call) selects Graph (typed DAG, 2× compression) or NL (prose fallback) per task. Taken from the paper.

Topics

This paper is about multi-agent llm systems, agent handoff format, llm routing, prompt compression, typed graph schema, constrained decoding, tau-bench, browsecomp, appworld, bfcl function calling, llm orchestration, and agent delegation.

What this paper does not show

This was accepted to EMNLP 2026, but the proceedings are not out yet, so this page cites the arXiv version, and the code has not been released. The 76 percent failure figure comes from an automated taxonomy, not human coding, spot-checked on 50 cases. The method wins on 2 of 4 benchmarks: BFCL is a tie, 75.4 against 75.3, and the AppWorld result is parity only because the router sends 89 percent of those tasks back to prose. Graph-only loses 14.6 points there on its own. Realized routing is coarse enough that it behaves close to a per-benchmark rule, and the oracle shows 8.6 points still unclaimed.

How to cite

Pratyay Banerjee and Ankit Chadha. 2026. Routed Graph Handoff: Adaptive Format Selection for Multi-Agent LLM Delegation. arXiv:2608.25277.

@misc{banerjee2026routed,
  title         = {Routed Graph Handoff: Adaptive Format Selection for Multi-Agent LLM Delegation},
  author        = {Banerjee, Pratyay and Chadha, Ankit},
  year          = {2026},
  eprint        = {2608.25277},
  archivePrefix = {arXiv},
  primaryClass  = {cs.CL},
  note          = {arXiv:2608.25277. Accepted to EMNLP 2026, proceedings not yet published},
  url           = {https://arxiv.org/abs/2608.25277}
}

Related work of mine

APEX-MEM: Agentic Semi-Structured Memory with Temporal Reasoning for Long-Term Conversational AIACL 2026 (Main Conference, Long Papers)
APEX-EM: Non-Parametric Online Learning for Autonomous Agents via Structured Procedural-Episodic Experience ReplayEMNLP 2026, accepted, to appear

arXiv version.