PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Pratyay Banerjee, Ankit Chadha

arXiv:2608.25277v1cs.CLcs.AI

TL;DR

Multi-agent systems often use natural-language handoffs even though coordination depends on preserving structure, while graphs can over-constrain adaptive reasoning. Routed Graph Handoff uses a lightweight router to choose typed graphs or natural language per delegation, matching or exceeding NL-only across four benchmarks with significant gains on τ-retail and BrowseComp and parity elsewhere.

  • Problem

    Multi-agent frameworks default to natural-language handoffs, although inter-agent misalignment arises from misinterpreted ordering constraints, dropped prerequisites, and ambiguous instructions.

  • Method

    Routed Graph Handoff uses a domain-agnostic 155-token router to select typed graph or natural-language delegation based on task content and computational pattern.

  • Results

    The routed system achieves significant gains on τ-retail and BrowseComp and zero regressions on the other two benchmarks, matching or exceeding NL-only overall.

  • Takeaways & Limitations

    Adaptive format selection preserves graph benefits on dependency-chain tasks while avoiding graph-only regressions on adaptive tasks.

  • Takeaways & Limitations

    Routing is coarse on these benchmarks, and finer-grained instance-level adaptation would require execution-time signals; 8.6 pp of oracle headroom remains.

Abstract

from arXiv · show

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 \textbf{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: \textbf{+12.7\,pp} on $τ$-retail at 3.2$\times$ compression ($p{<}0.01$), \textbf{+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.

1 Introduction

Multi-agent frameworks typically default to natural-language handoffs, despite coordination failures caused by misinterpreted dependencies and ordering. Routed Graph Handoff addresses the structure–flexibility tradeoff by selecting typed graphs or natural language per task.

  • Motivation: 76% of failures in 345 multi-agent trajectories stem from inter-agent misalignment, including dropped prerequisites, misordered steps, and looping on ambiguity.These findings motivate treating handoff format as a coordination mechanism rather than an afterthought.
  • Structure–flexibility tradeoff: Typed graphs make dependencies explicit and improve dependency-chain performance, yielding +8.7 pp on BrowseComp.The graph schema uses depends_on edges, precondition nodes, and tool-call sequences.
  • Structure–flexibility tradeoff: Graph-only delegation regresses 14.6 pp on AppWorld, where adaptive iteration and conditional branching require flexibility.Rigid plans prevent the executor from deviating when steps fail unexpectedly.
  • Routed Graph Handoff: Routed Graph Handoff uses a lightweight router to select graph or natural language according to each task’s computational pattern.The router costs approximately 155 tokens and 0.15% overhead, defaults to natural language, and routes dependency-chain tasks to graphs.
  • Routed Graph Handoff: The routed system achieves +12.7 pp on τ-retail and +8.7 pp on BrowseComp while avoiding regressions on the other evaluated benchmarks.The contribution combines structured handoffs with adaptive format selection rather than applying one format universally.

2 Method

The method represents delegations as typed DAGs and uses graph-aware execution guidance, while a domain-agnostic router selects graphs or natural language per task. The schema and router are designed to preserve dependency structure without imposing rigidity on adaptive tasks.

  • Native Graph Handoff Schema: Each delegation is encoded as a typed DAG with 8 node types and 7 edge relations.The node types include goals, constraints, actions, preconditions, postconditions, tool calls, and tool arguments.
  • Native Graph Handoff Schema: The schema was refined to expose prerequisite checks and enforce ordering in multi-step API sequences.Precondition and postcondition nodes address skipped checks, while tool_call and tool_arg nodes with depends_on edges address incorrect call order.
  • Native Graph Handoff Schema: Graph emission uses constrained decoding to produce valid DAG-conforming JSON without finetuning or an auxiliary encoder.The approach is zero-shot and inference-time only.
  • Graph-Aware Execution: Graph-aware executor guidance is essential: the same JSON with a standard executor prompt yields no gain.The guidance defines node types, edge semantics, and topological traversal; restoring it lifts NGH to +12.7 pp on τ-retail.
  • LLM Router: The router spends approximately 155 tokens per delegation to choose graph for ordered dependency tasks and natural language for iteration, conditionals, or adaptive reasoning.It defaults conservatively to natural language and uses temperature 0 with a domain-agnostic prompt.
  • LLM Router: The same classifier decides from task content alone, routing 100% of BrowseComp, τ-retail, and BFCL tasks to graphs while routing 89% of AppWorld tasks to natural language.These benchmark-level rates are aggregates of blind per-task decisions, not benchmark-specific rules.

3 Experiments

The experiments evaluate routed, graph-only, natural-language, and oracle handoffs across diverse benchmarks using a common orchestrator-to-executor harness. Routed Graph Handoff improves dependency-chain performance, preserves performance on adaptive tasks, and provides compression with minimal routing overhead.

  • Benchmarks and Setup: 1,052 trajectories span BrowseComp, BFCL v3, τ-bench retail, and AppWorld, covering web search, API sequences, customer service, and conditional multi-app tool use.Each benchmark is cast as an orchestrator-to-executor handoff so message format is the isolated variable.
  • Benchmarks and Setup: The comparison includes NL-only, NGH-only, Routed, and Oracle systems, with Claude Sonnet 4.5 as the orchestrator.Metrics are Pass@1, AST match accuracy, and Task Success Rate, depending on the benchmark.
  • Main Results: +12.7 pp on τ-retail and +8.7 pp on BrowseComp are significant NGH gains, while NGH-only loses 14.6 pp on AppWorld.The τ-retail gain is reported over 150 paired trials; BrowseComp reports CI [+2.7, +14.7].
  • Main Results: The routed system achieves significant gains on two benchmarks with zero regressions on the other two.It defaults to NL on 89% of AppWorld tasks and routes 100% of BrowseComp and τ-retail tasks to graph.
  • Robustness: Routed improves over NL with GPT-5 mini on BrowseComp, BFCL, and AppWorld, indicating the direction of gains transfers across orchestrator backbones.Reported changes are 65→68%, 82→85%, and 50→52%, respectively.
  • Efficiency: Average handoff compression is 2.1×, while the router adds 0.15% overhead and the graph path remains shorter than NL after accounting for executor prefill.On τ-retail, the full per-delegation budget is 461 versus 730 tokens, or 1.6× compression.
  • Task Patterns: AppWorld results show that graph helps aggregate tasks, whereas NL dominates patterns requiring adaptive reasoning.The task-pattern comparison covers 152 paired trials.
  • Protocol Comparison: On τ-retail, all schema-aware protocols outperform schema-unaware protocols regardless of compression ratio, and Routed NGH is the only zero-training protocol in the top five.The comparison uses 50 tasks × 3 seeds, or 150 trials per protocol.

4 Analysis and Related Work

The analysis identifies complementary strengths and failures of graph and natural-language handoffs. It attributes graph gains to explicit structure, graph losses to rigidity, and positions the routed approach against prior communication methods.

  • Failure Mechanisms: 76% of multi-agent failures are inter-agent misalignment involving ordering errors, dropped prerequisites, or retry loops from ambiguous instructions.The share is reported from 345 τ-bench trajectories and is robust to taxonomy thresholds.
  • Failure Mechanisms: +6.7 pp on AppWorld aggregate tasks reflects graph-enforced fetch-before-compute ordering.The aggregate subset contains 15 tasks.
  • Adaptive Routing: The oracle reaches 60.3% TSR, leaving 8.6 pp of headroom that requires execution-time signals and motivates mid-trajectory format switching.NGH rescues 9.9% of NL failures, while NL rescues 19.7% of NGH failures.
  • Ablation: The typed graph’s +12.7 pp gain exceeds schema-unaware explicit-plan alternatives, while encoder supervision and schema formatting changes do not explain the result.Schema-unaware re-encodings gain only +4.7 to +5.3 pp; identical T5-small encoders differ by 28 pp with versus without graph supervision.
  • Related Work: Prior frameworks define orchestration topology but generally leave handoff format unstructured; latent communication compresses more aggressively but sacrifices readability and portability.The paper places NGH between prose compression and latent communication, reporting 2× compression with interpretability and cross-family transfer.

5 Conclusion

Routed Graph Handoff addresses the structure-flexibility tradeoff by selecting graph or natural language per task. It improves dependency-chain benchmarks, avoids regressions elsewhere, and identifies execution-time routing as future work.

  • Conclusion: Typed graphs prevent misordering on dependency-chain tasks but over-constrain adaptive reasoning.The routed system uses a 155-token router with 0.15% overhead to select the format per task.
  • Conclusion: Schema-aware communication outperforms schema-unaware compression because task-critical structure matters more than minimizing token count.The graph artifact supports both zero-training emission and trained compression approaches.
  • Conclusion: The oracle identifies 8.6 pp of headroom achievable only through execution-time routing signals.The paper motivates mid-trajectory adaptive format switching as future work.

Limitations

The router’s decisions are coarse, clustering by task type rather than adapting at the individual-instance level. The schema may also fail to generalize to domains with fundamentally different coordination patterns.

  • Routing granularity: The router performs per-task-type rather than fine-grained per-instance adaptation.Its decisions cluster by task type on the evaluated benchmarks.
  • Generalization: The schema may not generalize to domains with fundamentally different coordination patterns, such as open-ended creative tasks.

Ethical Considerations

The study evaluates communication protocols using existing public benchmarks and commercially available foundation models, without collecting new data or involving human subjects. The supplied passages also include illustrative success and failure cases, but do not establish additional ethical risks.

  • Study scope: The evaluation uses existing public benchmarks: τ-bench, BrowseComp, BFCL, and AppWorld.No new data was collected and no human subjects were involved.
  • Study scope: Experiments use commercially available foundation models through standard API access.
  • Data considerations: The benchmarks include synthetic customer-service scenarios and web-search tasks with no personally identifiable information.
  • Illustrative cases: The τ-retail example shows dependency edges enforcing the sequence lookup → get_orders → respond.The graph prevents a retry loop caused by calling get_orders before lookup.
  • Illustrative cases: The AppWorld example involves updating a playlist from siblings’ free-text suggestions, which requires flexible interpretation.The graph’s rigid parse can miss suggestions and cannot backtrack, whereas natural-language delegation can request flexibility.

C Misalignment Annotation Methodology

The study classifies failures with a deterministic taxonomy applied to 345 trajectories across three protocols. Most NL/NGH failures are labeled inter-agent misalignment, and a manual audit provides 92% agreement with the automated labels.

  • Dataset and protocols: The taxonomy analyzes 345 τ-bench trajectories across single-agent, NL multi-agent, and graph multi-agent protocols.The dataset comprises 115 tasks with three seeds each.
  • Taxonomy categories: 76% of NL/NGH failures are classified as inter-agent misalignment, while 24% are task verification errors.Specification issues account for 0% of NL/NGH failures and 6% of single-agent failures.
  • Annotation procedure: Misalignment is assigned when logs show missing prerequisites, at least three consecutive retries on the same action, or ordering contradictions.The rule-based procedure is deterministic and reproducible from raw JSONL traces.
  • Validation: A manual audit of 50 randomly sampled failures agreed with automated labels in 92% of cases.The four disagreements were borderline retry loops caused by API timeouts rather than misinterpretation.

D Router Decision Analysis

The router is a deterministic classifier whose routing rates vary by task pattern, sending dependency-chain tasks to graphs and most AppWorld tasks to natural language. Its decisions recover the better format on evaluated task types, but oracle analysis shows remaining routing errors and headroom.

  • Observed routing: Routing rates are 100% graph on BrowseComp, τ-retail, and BFCL, versus 11% graph and 89% NL on AppWorld.The τ-airline rate is 2% graph and 98% NL.
  • AppWorld routing: The 11% of AppWorld tasks routed to graphs correspond exactly to aggregate tasks, where NGH outperforms NL by +6.7 pp.This comprises 15 of 152 AppWorld tasks.
  • Router behavior: The router makes deterministic decisions at temperature 0, identical across three independent runs.Its per-instance accuracy analysis covers AppWorld’s 152 tasks.
  • Router accuracy: On AppWorld, the router identifies 15/15 aggregate tasks and defaults to NL on 122/137 non-aggregate tasks.It misclassifies 15 non-aggregate tasks as graph because simple heuristics cannot distinguish partial ordering from pure aggregation.
  • Oracle analysis: The oracle gap is 8.6 pp: 5.2 pp comes from graph rescues among NL-routed tasks and 3.4 pp from NL rescues among graph-routed tasks.The 3.4 pp component represents router errors.
  • Executor requirements: The graph-aware executor prompt instructs the receiver to parse typed nodes and edges and execute the graph step by step.Without this prompt, the receiver treats the JSON as opaque; with it, the executor traverses nodes topologically.
  • Cross-vendor validation: Constrained decoding produced 0% invalid JSON across all four Claude Sonnet 4.5 × Nova Pro sender/receiver configurations.Compression remained 3.1–3.6× across model pairings.

G Second Orchestrator Backbone (GPT-5 mini)

A GPT-5 mini replication preserves the routed handoff’s direction of improvement over natural-language delegation across re-runnable benchmark families. The routed approach also retains token savings after accounting for routing and graph-executor overhead.

  • The replication uses GPT-5 mini with the same router prompt, schema, and graph-aware executor prompt as the comparison harness.
  • Routed improves over the NL handoff on every GPT-5 mini benchmark family.This matches the direction of the main Claude Sonnet 4.5 results and supports portability across model families.
  • Even after adding router and graph-aware executor costs, the graph path totals fewer tokens than NL on τ-retail.Table 5 measures full per-delegation tokens and estimates latency using standard Sonnet 4.5 decoding.
  • On AppWorld, the router keeps NL on 89% of tasks, avoiding the ∼18% overhead incurred by graph-only delegation from failed graph executions.

I Error-Taxonomy Threshold Sensitivity

The reported 76% misalignment share depends partly on a thresholded retry-loop rule, but an audit bounds its sensitivity and preserves the qualitative conclusion. The study’s reproducibility artifacts and public-benchmark setup support checking these analyses.

  • The 76% misalignment share depends on one thresholded taxonomy rule: at least three consecutive retry steps on the same action.Missing-prerequisite errors and ordering contradictions are threshold-free criteria.
  • Automated and manual labels agreed on 92% of 50 randomly sampled failures, with all four disagreements involving API-timeout retry loops.These borderline cases are the ones affected by stricter or looser retry thresholds.
  • Across retry thresholds of 2, 3, and 4, inter-agent misalignment remains the dominant multi-agent failure mode.The audit bounds relabeling changes to at most 4 of 50 sampled failures, approximately 8%.
  • The released study artifacts include the schema, prompts, models, statistical procedures, scorer, and configurations for public-benchmark evaluation.No new data was collected and no personally identifying information is involved.
Loading 2608.25277v1…