PaperlayerView exact revision on arXiv

Source-linked AI summary

The Collaboration Tax: How Much LLM Multi-Agent Systems Pay to Coordinate

Weixiang Sun, Zehong Wang, Hong Huang, Colby Nelson, Yanfang Ye

arXiv:2608.22152v1cs.CL

TL;DR

The paper asks how much performance LLMs lose when coordinating with another agent on problems each can solve alone, addressing a lack of structured evidence about coordination cost. It defines and measures this collaboration tax across tasks and models, finding a predictable four-stage conversational cascade, systematic capability and category orderings, and partial recovery through prompting.

  • Problem

    The paper addresses whether paired LLMs incur a systematic coordination cost and where that cost originates, amid limited model- and task-agnostic evidence.

  • Method

    The paper defines collaboration tax as the success-rate gap between full-information solo and split-view paired execution, then measures it across 32 tasks and 11 models using solo and heterogeneous-pair comparisons.

  • Results

    The tax follows no-exception orderings by task category and model capability, arises through a four-stage conversational cascade rather than reasoning failure, and is mechanically predictable from conversation features.

  • Takeaways & Limitations

    A single stage-targeted prompt intervention recovers a substantial fraction of the collaboration tax without retraining, while heterogeneous-pair costs are pulled toward the stronger member.

  • Takeaways & Limitations

    The evaluation uses procedurally generated puzzles rather than deployment workloads, so its setting does not directly correspond to applications such as collaborative code editing or interactive document drafting.

Abstract

from arXiv · show

Multi-agent systems built from large language models are deployed widely, yet how much performance is lost when two LLMs must coordinate rather than act alone remains unclear. We formulate the collaboration tax as the team-decentralisation loss of a two-player cooperative game with private information, with two propositions characterising its sign and its equivalence to a max-superadditivity violation. We operationalise this definition on 32 solo-tractable tasks grouped by source of grounding friction and measure it on 11 models from 7 providers. The tax is structured along two no-exception axes: a category ordering across every model and a monotonic decrease with capability. The proximate mechanism is not a reasoning deficit but a four-stage conversational cascade in which agents make ungrounded claims, fail to query the partner, skip integrating both views, and accept the answer without re-derivation. The tax is mechanically predictable from conversation features and partly tractable: a prompt intervention targeting all four stages closes a substantial fraction of the gap, with the dominant bottleneck differing across categories. In heterogeneous pairs the tax is pulled toward the stronger partner rather than the additive midpoint, empirically realising the max-superadditivity violation predicted by our framework. Together these results recast collaboration in LLM systems as a measurable, predictable, and partly tractable cost.

1 Introduction

The paper asks whether LLMs lose performance when coordinating on problems each could solve alone, and develops a structured account of that coordination cost. Across tasks and models, it identifies a four-stage conversational cascade and shows that targeted prompting can partially reduce the loss.

  • Motivation: The study tests whether paired LLM execution has a structural coordination cost and where failures originate in the conversation.It distinguishes reasoning, information access, communication, and verification as possible failure locations.
  • Findings: The tax follows no-exception orderings across task categories and model capability and is mechanically predictable from conversation shape features.Capability sets the gap’s intercept, while conversation shape sets its slope.
  • Findings: Failures form a four-stage cascade—grounding, querying, integration, and re-derivation—rather than a reasoning failure.Agents make ungrounded claims, fail to ask for missing facts, skip combining views, and accept answers without recomputation.
  • Intervention: A combined prompt intervention targeting all four stages partially closes the collaboration gap, while leave-one-out analysis finds category-specific bottlenecks.The intervention is designed as four stage-targeted clauses appended to the system prompt.
  • Contributions: The collaboration tax is defined as the success-rate gap between full-information solo and split-view paired execution.The definition uses a cooperative-game interpretation to isolate coordination cost from problem-solving capacity.
  • Contributions: The evaluation covers 32 solo-tractable tasks across Spatial, Relational, and CSP families, using 11 models from 7 families.Configurations include solo, homogeneous, and slot-swapped heterogeneous pairs.

2 Related Work

Prior work studies LLM coordination through domain-specific benchmarks, orchestration methods, and asymmetric-information cooperative games. This paper connects those lines with a broader account of coordination cost and evaluates it across structured task families.

  • LLM agent collaboration: Recent LLM collaboration benchmarks examine split-view mazes, turn-count effects, Overcooked-style cooperation, agentic tasks, partner pairs, cooperation games, and failure taxonomies.The cited studies probe distinct coordination settings rather than one unified cost measure.
  • Cooperative games with asymmetric information: Asymmetric-information cooperation research includes Hanabi, unseen-partner coordination, embodied Overcooked-AI, and textual referent games.These settings test cooperation under partial observability, private context, or grounding demands.
  • Positioning: The paper’s setup preserves partial progress as a graded outcome and attributes collaborative performance to coordination rather than underlying task-solving ability.This supports comparison of coordination cost across the paper’s structured evaluation settings.

3 The Collaboration Tax

The paper generalizes split-view evaluation into a task-agnostic collaboration-tax measure grounded in team decentralization. The measure compares full-information solo performance with homogeneous paired performance and includes a normalized ratio.

  • Definition: The collaboration tax generalizes split-view comparisons into a task-agnostic quantity with a known sign and structural interpretation.The construction is motivated by coordination-cost comparisons across tasks, models, and pair configurations.
  • Operational form: The operational setup partitions each task instance into two views whose union is necessary for determining the answer.Instances are scored by a deterministic grader, and neither private view alone admits the canonical answer.
  • Operational form: The homogeneous tax is ssolo-full(M, T) − shomo(M, T), comparing mean full-instance solo score with mean split-view paired score.Each score is averaged over 50 rollouts with independent seeds; a ratio version normalizes across different solo ceilings.

4 Tasks and Protocols

The paper uses a 32-task suite designed to isolate coordination costs from individual problem-solving difficulty, evaluating solo, homogeneous, and heterogeneous collaboration modes.

  • Task design: The suite partitions each instance into complementary views whose union is necessary because neither view alone admits the canonical answer.
  • Task design: Tasks span Spatial, Relational, and CSP families, representing distinct grounding frictions and error-propagation patterns.
  • Evaluation protocol: Four evaluation modes compare single-agent controls with two-agent collaborations, scoring every final answer against deterministic ground truth.
  • Evaluation protocol: In solo-full, one model receives the merged instance and receives a critic pass intended to keep the comparison focused on coordination cost.
  • Evaluation protocol: Homogeneous pairs use independent contexts with split views, while heterogeneous pairs substitute different models or checkpoints into the same protocol.
  • Evaluation protocol: Each task-mode-model or pair cell averages 50 independently seeded rollouts, with deterministic program scoring rather than model-assigned scores.

5 Experiment

Across eleven models, the collaboration gap follows consistent capability and category patterns, is associated with a four-stage conversational cascade, and can be partly reduced by targeted prompts.

  • Gap landscape: Within every model, the ratio-gap ordering is Spatial ≻ Relational ≻ CSP, while weaker models lose roughly half their solo success to coordination.
  • Mechanism: The four-stage analysis evaluates grounding, querying, integration, and re-derivation as binary dimensions of homogeneous rollouts.
  • Prediction and intervention: A ridge model predicts the gap out of fold with R2 = 0.475, Spearman ρ = 0.760, and Pearson r = 0.705; capability sets its intercept while conversation shape sets its slope.
  • Mechanism: Grounding is a necessary condition: fabricated information cannot be recovered by downstream stages.
  • Mechanism: Querying distinguishes failures from successes across categories, with its largest gap on CSP, where partners must elicit latent cross-half facts.
  • Mechanism: Integration is the strongest single-variable predictor of the tax, especially for Spatial tasks, while re-derivation correlates strongly but adds little beyond integration.
  • Prediction and intervention: The all-four prompt intervention recovers a substantial fraction of the tax without retraining, with responsiveness highest for CSP, followed by Relational and Spatial.
  • Prediction and intervention: Leave-one-out results identify different bottlenecks by category: L4 for Spatial, L1 for Relational, and L2 for CSP.

6 Heterogeneous-Pair Matrix

The heterogeneous-pair analysis tests whether coordination costs depend on partner identity and finds that pair gaps track the stronger member rather than an additive midpoint. Across the evaluated configurations, the pairs violate max-superadditivity on most tasks.

  • Pair design: Two strong-weak contrasts pair gpt-4.1-nano with claude-sonnet-4-5 or gpt-5 while varying family identity.The capability gap is held roughly fixed across cross-family and same-family comparisons.
  • Cooperative-game results: Every heterogeneous pair violates max-superadditivity, and every member’s Shapley value falls below its singleton payoff.Table 2 reports characteristic-function and Shapley values averaged across the 32 tasks.
  • Gap structure: The actual hetero ratio gap is systematically below the midpoint prediction and well below the additive line y = x.The four off-diagonal cells cluster near the strong-tier diagonal rather than averaging between strong and weak.
  • Robustness: Same-family and cross-family pairs are not visibly separated, but one pair per comparison prevents detecting family-level effects.The heterogeneous results are presented as an existence proof of a qualitative pattern rather than a quantitative characterisation.

7 Conclusion

The paper defines and measures the collaboration tax across dyadic LLM teams, then links its structure to conversational failures and heterogeneous-pair effects. It concludes that collaboration cost is measurable, predictable, and partly tractable.

  • Conclusion: The collaboration tax is formulated as team-decentralisation loss and measured across 32 tasks and 11 models.The framework includes two propositions characterising the tax’s sign and its cooperative-game interpretation.
  • Conclusion: The tax follows no-exception orderings by capability and task category.
  • Conclusion: A four-stage conversational cascade, rather than a reasoning deficit, drives the proximate coordination failure.The stages involve grounding, querying, integration, and re-derivation.
  • Conclusion: The tax is mechanically predictable from conversation features and partly tractable through a single stage-targeted prompt intervention.The intervention targets all four conversational stages.
  • Conclusion: In heterogeneous pairs, the tax is pulled toward the stronger member, empirically realising the framework’s max-superadditivity violation.

Limitations

The study’s limitations concern scope: it evaluates dyadic collaboration and procedurally generated puzzles rather than broader multi-agent settings or deployment workloads. The authors identify extending the framework and designing production-like tasks as future work.

  • Two-agent only: The suite measures collaboration tax only for dyadic pairs with N = 2.Whether the cascade and rank-survives, level-fails decomposition generalise to N ≥3 settings remains unstudied.
  • Two-agent only: Beyond dyads, both the private-information partition and conversational dynamics change qualitatively in multi-party dialogue.The authors are extending the framework to multi-agent collaboration.
  • Synthetic tasks rather than deployment workloads: All tasks are procedurally generated puzzles, so the setting does not directly correspond to collaborative code editing, issue resolution, debugging, or document drafting.Future work will re-measure the tax on tasks closer to these production workloads.

Ethics Statement

The paper formalises paired LLM execution as a cooperative game with private information and defines the collaboration tax by comparing paired performance with full-information solo performance. Its propositions establish when the tax is nonnegative and when it corresponds to max-superadditivity failure.

  • Formal framework: Each paired execution is modelled as a two-agent cooperative team problem with private information.The characteristic function assigns values to singleton agents and the paired coalition.
  • Formal framework: The singleton value is full-instance solo performance, while the paired value is performance from the protocol on complementary private views.The union-necessary partition ensures the two private views reconstruct the full instance.
  • Propositions: Under an optimal full-information solo policy, the collaboration tax is nonnegative by information dominance.The paired protocol is measurable from the joint private views and therefore is feasible as a function of the full instance.
  • Estimator caveat: The operational estimator can be negative because its single-agent baseline is an LLM policy rather than the optimal centralised policy.Such negative cells occur when the paired protocol outperforms that single-agent baseline.
  • Propositions: A positive collaboration tax is equivalent to violating max-superadditivity: paired value falls below the stronger singleton value.

A.5 Shapley value and subadditivity

The paper uses Shapley values to connect two-agent cooperative-game payoffs with the collaboration tax. Under subadditivity, both agents receive less than their solo payoffs, and the empirical heterogeneous pairs mostly exhibit this condition.

  • The Shapley value allocates the joint payoff between two cooperative-game members under efficiency, symmetry, and the null-player axiom.
  • For two agents, each Shapley value averages the marginal contributions from the two possible orderings.
  • Subadditivity, v({1, 2}) < v({1}) + v({2}), implies that both members’ Shapley values fall below their singleton payoffs by the same absolute amount.
  • On the majority of tasks, all four heterogeneous pair configurations satisfy subadditivity, so both members’ Shapley values are strictly below their singleton payoffs.
  • For the nano × gpt-5 configuration, ϕgpt-5 = 0.668 versus v({gpt-5}) = 0.932, illustrating the stronger member’s reduced marginal contribution under Shapley fairness.

C Human Validation of the Cascade Judge

The cascade judge was checked against blinded human annotation and showed moderate-to-substantial agreement, while failure examples illustrate how grounding, querying, integration, and re-derivation break down in practice.

  • Validation design: The validation used 100 rollouts stratified by outcome, category, and automated cascade labels, with four annotators blind to model identity, scores, and automated labels.
  • Human agreement: Human agreement was moderate to substantial across all four stages, with L2 and L3 substantial and L1 and L4 moderate.
  • Judge alignment: Automated-judge agreement with expert majority was substantial for L1 (κ = 0.707), L2 (0.668), and L3 (0.725), and moderate for L4 (0.508).
  • Cascade co-occurrence: 67% of failed rollouts fired at least two cascade stages, showing that the stages are separable but not independent.
  • Cascade co-occurrence: L3 and L4 co-fired most strongly at Jaccard 0.67, whereas L2 had the highest sole-fire rate at 13.9% and L3 never fired alone.
  • Illustrative failures: In an illustrative spatial failure, fabricated walls propagated into the route despite querying, integration, and stepwise verification.
  • Illustrative failures: In the CSP example, agents stated private clues without asking targeted questions, producing a final score of 0.083.

E.4 L4 Re-derivation: blueprintmaze, DeepSeek-V4-Pro

The L4 blueprint-maze example shows a pair that constructs an explicit combined map but accepts a contradictory route without receiver-side recomputation. The paper presents re-derivation as the structural fix for this final-stage failure.

  • E.4 L4 Re-derivation: The blueprint-maze pair proceeds through grounding, querying, and explicit integration before proposing a route.
  • E.4 L4 Re-derivation: The receiver does not re-walk the path before acceptance, and the proposer self-terminates with ACTI!.
  • E.4 L4 Re-derivation: The combined map lists (3, 4) as #, while the route check immediately below says (3, 4) is ., creating an internal contradiction.
  • E.4 L4 Re-derivation: The example supports the broader cascade distinction: L1 errors invent content, L2 omits questions, L3 omits merged-state integration, and L4 accepts prematurely.
  • E.4 L4 Re-derivation: The L4 intervention requires recomputation work immediately before ACTI!, rejecting bare agreement or confirmation.

H Additional Results

Additional analyses preserve the paper’s main patterns: task category orders the ratio gap, heterogeneous pairs track the stronger tier, cascade signatures transfer across pair types, and the solo critic has little effect.

  • Per-task decomposition: Spatial path tasks occupy the high end of per-task ratio gaps, while CSP assignment tasks occupy the low end; numberlink and crossword are exploratory because they miss the solo-tractability target.
  • Heterogeneous pairs: The four off-diagonal heterogeneous-pair cells cluster near the strong-tier diagonal rather than averaging between strong and weak baselines.
  • Cascade transfer: Successful heterogeneous pairs ground, query, integrate, and re-derive more often than failed pairs across categories.
  • Cascade transfer: Heterogeneous pairs query more often than homogeneous pairs on Spatial and Relational tasks, suggesting pair asymmetry prompts explicit queries that homogeneous pairs skip.
  • Critic ablation: Removing the critic prompt lowers gpt-4o-mini’s mean solo-full score from 0.575 to 0.569, a 0.006-point cost.
Loading 2608.22152v1…