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

1. TL;DR #

When two LLMs each hold half of a solo-trivial puzzle and must talk to solve it,

they lose performance versus one agent given the whole thing. This "collaboration

tax" obeys two no-exception orderings (Spatial ≻ Relational ≻ CSP; shrinks with

capability), is driven by a 4-stage conversational cascade not a reasoning deficit,

is regression-predictable ($R^2=0.475$), and a prompt fix recovers ~38%.

2. Q1 / Q2 / Q3 #

Q1 — 痛点 (what problem) #

Multi-agent LLM systems are deployed everywhere, but there is no **model- and

task-agnostic* account of what coordination costs* when two LLMs that could each

solve a task alone must instead split the information and talk. Prior work measures

coordination on one task type at a time (mazes, Overcooked, debate) and reports an

isolated number with no known sign, no decomposition across task structure, and no

mechanism. Three concrete unknowns: (RQ1) does a systematic cost exist and what sets

its size — capability, task structure, or their interaction; (RQ2) where in a

conversation does it fail — reasoning, information access, communication, or

verification; (RQ3) is it reducible by prompting alone, without retraining.

Scope: closed, dyadic, multi-turn cooperation under private information. Each

agent is fully autonomous (no human in the loop); the only interaction channel is a

turn-based text dialogue capped at 50 exchanges. Task class is *solo-tractable by

construction* — the difficulty is manufactured entirely by splitting the instance.

Q2 — 方法 (the approach) #

1. Formalise the cost as the team-decentralisation loss of a two-player

cooperative game with private views (Marschak 1955; Shapley 1953). Tax =

best-single-agent value − paired value. Two propositions pin its sign (≥0 under

information-dominance) and its meaning (positive tax ⇔ max-superadditivity

violation).

2. Operationalise on 32 tasks in 3 families chosen for *distinct grounding

friction*: Spatial (reference-frame alignment), Relational (lexical/category

alignment), CSP (indexing/ordinal alignment). Each task is solo-trivial,

union-necessary, algorithmically graded in $[0,1]$, and multiply expressible.

3. Measure across 11 models / 7 providers in solo-full, homogeneous, and

heterogeneous modes, 50 rollouts/cell.

4. Explain with a 4-stage LLM-judge cascade (Grounding → Querying → Integration

→ Re-derivation), validated against 4 human annotators.

5. Predict the tax from conversation features (ridge regression) and fix it

with four stage-targeted prompt clauses, ablated leave-one-out.

核心技术壁垒 (the single hardest-to-replicate insight): the *task-construction discipline* that turns "coordination cost" into a clean, decomposable scalar. The binding requirement is multiply-expressible — the same content has several equivalent surface forms (coordinate origins, axis orderings, naming conventions), so an agent cannot win by blindly concatenating the partner's raw view. That single property converts the measurement from an information-accessibility probe into a coordination-competence probe, and it is what makes every other result (the two orderings, the cascade, the intervention deltas) attributable to coordination rather than to missing bits. Reproducing the headline numbers without reproducing this property silently measures a different quantity. See §7.

Q3 — 结果 (what was shown) #

• Two no-exception orderings. Within every one of the 11 models: Spatial ≻

Relational ≻ CSP. Across models: the gap shrinks monotonically with capability —

weakest models lose ~half their solo success, top-tier models still pay a positive

tax.

• Mechanism is conversational, not cognitive. Four grounding stages each

discriminate success from failure; Integration (L3) is the strongest single

predictor and the only stage with positive marginal contribution in a

multi-feature regression.

• Predictable. Out-of-fold ridge $R^2 = 0.475$ (Spearman $\rho=0.760$); transfers

to held-out heterogeneous cells at $R^2 = 0.41$. "Capability sets the intercept;

conversation shape sets the slope."

• Partly fixable. The all-four prompt intervention closes 38.3% of the tax

overall (CI above zero on every category), and each category has a different

bottleneck layer: Spatial→L4, Relational→L1, CSP→L2.

• Heterogeneous pairs pull toward the strong member, not the midpoint; yet all

six pairs violate max-superadditivity and both members' Shapley values fall below

their solo payoffs — the weak agent cannot free-ride, and the strong agent is

taxed for pairing.

---

3. 架构 / 方法图 #

3.1 The measurement pipeline #



Paper's Figure 1. Top ("Real-world intuition"): two agents with private views of a

shared software issue are expected to outperform either alone. Bottom ("What

actually happens"): paired performance falls below the solo upper bound, and the

shortfall — the collaboration tax — decomposes into the four conversational stages

(grounding, querying, integration, re-derivation) that the rest of the paper

measures. This figure is load-bearing: it frames the tax as a *gap below a solo

ceiling*, which is exactly what Eq.1 estimates.

The experimental scaffold is deliberately minimal so that any measured loss is

coordination, not capability:

• solo-full — one agent gets the merged instance $v_1 \cup v_2$, answers in one

completion, then a critic pass may revise it (the critic also exists in collab

mode, so it is a fairness control, not an advantage).

• homogeneous — two instances of the same model get $v_1$ and $v_2$; they

exchange messages (each prefixed [other agent]:) until one emits the termination

marker ACTI! with a candidate answer, or 50 exchanges elapse.

• heterogeneous — identical, but the two roles are different models.

3.2 The agent loop (one turn) #

The per-turn state machine each agent runs, annotated with the four cascade stages

that can silently fail. A failure at any stage is not an exception the agent sees —

it manifests only as a wrong final answer, which is why the authors must recover the

stages post-hoc from the transcript.

stateDiagram-v2 [*] --> Observe Observe --> Ground: read own view v_i + partner messages Ground --> Query: L1 — is every claim traceable to a stated source? Query --> Integrate: L2 — did I ask the partner for a specific missing fact? Integrate --> Rederive: L3 — did I combine BOTH views into one state before deciding? Rederive --> Decide: L4 — did I recompute the partner's proposal against my view? Decide --> Emit: propose answer + ACTI! Decide --> Observe: not confident / turn budget remains Emit --> [*]: graded by deterministic U in [0,1] note right of Ground Memory = context window only (no vector DB / file). Tool set = a single tool: send_message(text) to partner. Env is deterministic; the grader U is hidden from agents. note left of Rederive Error surface: a skipped stage throws no exception — it surfaces only as a low U score. No retry wrapper. end note

Planning style is implicit ReAct-without-tools: think in natural language, "act"

only by messaging the partner, verify by re-derivation. There is no backtracking

primitive — an agent cannot undo a committed message; the only recovery is further

dialogue within the 50-turn budget. Decomposition is bottom-up: agents assemble a

joint answer from two partial views rather than top-down subtask allocation.

---

4. 作者证明 #

Unusually for an agent paper, the core construct is backed by a formal cooperative-game

model (Definition 1 + Propositions 1–4), not only empirics. Below is the notation,

the physical meaning of each equation, and the minimum checks.

Notation table #

Symbol	Meaning
$T=(\mathcal{X},\mu,U)$	task: instance space, instance distribution, deterministic grader
$U:\mathcal{X}\times\mathcal{A}\to[0,1]$	grader; continuous partial-credit score
$v_1(x),v_2(x)$	the two private views; $v_1(x)\cup v_2(x)=x$ (union-necessary)
$\Pi(M_1,M_2;v_1,v_2)$	paired execution protocol (the dialogue)
$V_\text{solo}$	best single-agent value on the full instance
$V_\text{pair}$	expected paired value on split views
$v(\{i\}),v(\{1,2\})$	characteristic-function values: singleton / coalition payoff
$\phi_i$	Shapley value (fair share) of player $i$
$\hat{\tau}(M,T)$	operational estimator: 50-rollout cell-mean of the tax

Equations & physical meaning #

Operational estimator (what is actually measured):

$$\hat{\tau}(M, T) = s_{\text{solo-full}}(M, T) - s_{\text{homo}}(M, T)$$

Theoretical tax as a cooperative-game gap:

$$\text{tax}((M_1, M_2), T) = V_{\text{solo}} - V_{\text{pair}} = \max(v(\{1\}), v(\{2\})) - v(\{1,2\})$$

Shapley allocation in a 2-player game (average marginal contribution over 2 orderings):

$$\phi_i = \tfrac{1}{2}\big(v(\{i\}) + v(\{1,2\}) - v(\{j\})\big),\quad j\neq i$$

Subadditivity ⇒ both members lose, equally:

$$\phi_i - v(\{i\}) = \tfrac{1}{2}\big(v(\{1,2\}) - v(\{1\}) - v(\{2\})\big) < 0$$

The first equation is the measurement; the second gives it a sign and a name (gap

below the best coalition member); the Shapley pair shows that a subadditive team

docks both players below their solo value by the same absolute amount,

independent of who is stronger — which is why even a weak agent paired with gpt-5

cannot free-ride.

Six minimum checks #

1. Dimensional consistency — every term lives in $[0,1]$ (score space); $\hat\tau$

and $\text{tax}$ are differences of scores, so bounded in $[-1,1]$. ✓

2. Sign/limit — non-negativity. Prop 1: if the paired answer is measurable in

$(v_1,v_2)$ and $V_\text{solo}$ is realised by the optimal measurable policy on

$x$, then the paired policy lies in the same feasible set, so $V_\text{solo}\ge

V_\text{pair}\Rightarrow\text{tax}\ge0$. ✓

3. Degenerate limit — union-necessity. If the partition is degenerate ($v_1=x$),

the paired protocol can emulate solo exactly, forcing $\text{tax}=0$ by

construction (App A.6). The construct only measures something when neither view

determines the answer. ✓

4. Equivalence check. Prop 2: $\text{tax}>0 \iff v(\{1,2\})<\max(v(\{1\}),v(\{2\}))$

— a positive tax is a max-superadditivity violation, not merely correlated with

one. ✓

5. Estimator consistency. With a deterministic grader, the only variance is

agent stochasticity, absorbed by within-cell 50-rollout averaging; a stochastic

grader would add an independent noise source making $\hat\tau$ inconsistent at

finite sample (App A.6). ✓

6. Boundary / failure of the guarantee. The non-negativity is a policy-consistency

claim; empirically $\hat\tau<0$ for claude-sonnet-4-5 and DeepSeek-V4-Pro on CSP,

because real LLM policies are stochastic and context-dependent — the paired context

can activate a better decision distribution than solo. The authors flag this as

expected, not a contradiction (App A.7). ✓

*What could have been bounded but was not*: the residual tax under the all-four

intervention. The classical equality (tax = 0 iff communication suffices to

reconstruct $v_1\cup v_2$) needs unbounded message exchange; the 50-turn cap makes

the residual partly a protocol-bound artefact rather than a pure coordination

deficit. No convergence rate in turns is proven — the agent-paper norm (success is

measured, not bounded) holds here for the intervention, even though the tax itself

is formalised.

---

5. 实验与数据 #

5.1 The gap landscape — two orderings #



Paper's Figure 3. Rows are the 11 models sorted by overall mean; columns are the

three families. Reading across any row gives Spatial > Relational > CSP (e.g.

gpt-4.1-nano: +63 / +50 / +38). Reading down any column the gap grows as

capability falls (Spatial: gpt-5 +12 → gpt-4.1-nano +63). Notice the two blue cells —

Sonnet-4.5 (−6) and DS-V4-Pro (−5) on CSP — the empirically negative tax that

check #6 above anticipates: strong models on the lowest-friction family occasionally

do better paired than solo.

5.2 Mechanism — the four-stage cascade #



Paper's Figure 2. Each panel is one cascade stage; bars give the rate at which

homogeneous failures (light) vs successes (saturated) satisfy that stage, by

category. Every stage separates the two outcomes, but the gap is largest where the

category's bottleneck lives: L2 queried shows the widest success/failure split on

CSP (0.39 vs 0.29 — successful CSP pairs explicitly elicit cross-half capacity

facts), while L1 grounded is near-ceiling for successes everywhere (≈0.98–1.00).

L3 integrated has the largest absolute separation (e.g. CSP 0.90 vs 0.50), matching

the claim that integration carries the unique predictive signal.

5.3 Predictability #



Paper's Figure 4. Each marker is a (model, task) cell; folds are grouped by task

(leave-one-task-out). The regression on conversation features (cascade-stage presence,

turn counts) hits out-of-fold $R^2 = 0.475$, Spearman $\rho=0.760$, with the OLS fit

$y=0.60x+0.12$ tracking the $y=x$ diagonal. The near-zero mean offset

($\overline{y}-\overline{x}=+0.007$) means the predictor is unbiased in level — it

captures the shape of a conversation well enough to forecast its tax before grading

the answer.

5.4 Intervention — stage-targeted prompt clauses #

Table 1 — Stage-targeted prompt-intervention ablation (reproduced from the paper;

$\Delta s_\text{homo}$ = absolute lift vs no-intervention baseline; % closed =

fraction of the tax recovered; ± = half-width of 95% CI; bold = column max):

Condition	Spatial Δs	Spatial %closed	Relational Δs	Relational %closed	CSP Δs	CSP %closed	Overall Δs	Overall %closed
All four	+0.051±.026	+27.1±12.3	+0.072±.029	+41.4±38.0	+0.111±.074	+52.5±32.3	+0.079±.031	+38.3±14.1
no L1	+0.066±.027	+37.3±16.2	−0.005±.038	−2.4±25.4	+0.093±.065	+45.6±35.3	+0.051±.033	+27.7±15.1
no L2	+0.034±.048	+12.1±26.0	+0.030±.030	+18.4±21.2	+0.055±.028	+28.2±20.5	+0.040±.022	+18.4±13.4
no L3	+0.059±.018	+30.3±9.9	+0.044±.042	+27.5±36.8	+0.119±.078	+55.2±22.1	+0.075±.035	+36.3±13.5
no L4	−0.004±.027	+2.3±12.5	+0.015±.035	+2.8±37.5	+0.064±.063	+29.4±25.6	+0.027±.030	+9.9±13.4

The leave-one-out rows localise each category's bottleneck: dropping L4 collapses

Spatial lift to +2.3% (re-derivation is what fixes spatial paths); dropping L1

flips Relational negative (−2.4%, grounding is the lexical-alignment bottleneck);

dropping L2 halves CSP lift. One genuinely counterintuitive cell: on CSP, no L3

(+55.2%) slightly beats all four (+52.5%) — adding the integration clause

marginally hurts CSP, unexplained in the main text (within overlapping CIs).

5.5 Heterogeneous pairs & the cooperative-game audit #



Paper's Figure 5. Each point is a (pair, task) cell: $x$ = mean of the two members'

homogeneous gaps, $y$ = actual hetero gap. Points sit systematically below the

$y=x$ additive line (mean offset $\Delta=-0.19$; OLS slope 1.57), i.e. the pair gap is

pulled toward the stronger member rather than the average. The Shapley audit

confirms the cost is shared, not free-ridden:

Table 2 — Cooperative-game values & Shapley allocations (six hetero pairs):

Pair	$v(\{1\})$	$v(\{2\})$	$v(\{1,2\})$	$\phi_1$	$\phi_2$
Sonnet × nano	0.869	0.352	0.731	0.624	0.107
nano × Sonnet	0.352	0.869	0.732	0.108	0.624
nano × gpt-5	0.352	0.932	0.756	0.088	0.668
gpt-5 × nano	0.932	0.352	0.706	0.643	0.063
DeepSeek × nano	0.802	0.352	0.728	0.589	0.139
nano × DeepSeek	0.352	0.802	0.718	0.134	0.584

Every row satisfies $v(\{1,2\})<\max(v(\{1\}),v(\{2\}))$ (max-superadditivity

violated), and every $\phi_i

flesh.

5.6 Backbone sensitivity & failure classes #

• Backbone requirement (§7-style read): the ordering holds across 11 models from

Qwen3-8B up to gpt-5 — the method of measurement needs no special backbone, but

the magnitude of the tax is strongly backbone-dependent (weak models pay ~2× the

strong-model tax). No minimum model size is required for the phenomenon to appear;

it appears most in small models.

• Failure-mode taxonomy (App B): 700 failure descriptions → 16 behaviour clusters

→ mapped onto the 4 cascade stages. Dominant cluster is L3

moved_without_confirming_layout (n=109, Spatial/cube), confirming integration as

the single largest failure class. Judge validated at Cohen's κ ∈ [0.67,0.73] for

L1–L3, κ=0.51 for L4 (re-derivation is the fuzziest to define).

---

6. 论证链 (paper-internal) #

#	Step	Mechanism / evidence in the paper
1	Define the construct	Tax = $\max(v(\{1\}),v(\{2\}))-v(\{1,2\})$; Prop 1 gives sign ≥0 under information-dominance; Prop 2 equates positive tax with a max-superadditivity violation (§3, App A).
2	Isolate coordination from capability	Four task-design requirements — solo-trivial, union-necessary, algorithmically graded, multiply-expressible — force any measured loss to be coordination, not problem difficulty or missing information (§4.1, App A.6).
3	Measure structure	32 tasks × 11 models × modes, 50 rollouts/cell → two no-exception orderings: Spatial≻Relational≻CSP within each model, monotone-with-capability across models (Fig 3, §5.2).
4	Locate the failure	A 4-stage LLM-judge cascade separates success from failure in every stage; L3 integration is the strongest single predictor and only positive marginal feature (Fig 2, §5.3).
5	Show it is lawful, not noise	Ridge regression on conversation features predicts the tax out-of-fold at $R^2=0.475$, transferring to hetero cells at 0.41 — "capability sets the intercept, conversation shape sets the slope" (Fig 4, §5.4).
6	Make it actionable	Four stage-targeted prompt clauses recover 38.3% of the tax overall, with a category-specific dominant bottleneck exposed by leave-one-out (Table 1, §5.5).
7	Generalise to mixed pairs	Hetero gap is pulled below the additive midpoint toward the strong member; all six pairs violate max-superadditivity and both Shapley shares drop below solo (Fig 5, Table 2, §6).

---

7. 实现 cross-reference #

[实现未公开] — the L1 record carries no public code/repo URL for the task suite,

the cascade judge, or the evaluation harness. The reproducible artefacts are the

verbatim specifications inside the paper's appendices:

• Intervention clauses (the entire §5.5 result) are given word-for-word in

Appendix G.1 — e.g. the L3 Integration Block: *"Before proposing final answer, send

a message combining your view with your partner's view. Explicitly list: (1) facts

from my view, (2) facts from partner's view, (3) derived conclusions using both."*

These four strings are the implementation of the intervention.

• Hyperparameters fully pinned in Appendix J: agents temperature 0.7 / top-p 0.95

/ max 2000 tokens/turn; graders temperature 0.2 / top-p 1.0 / max 500 tokens;

turn cap 50; 50 rollouts/cell.

• Graders are deterministic procedures named per family (Appendix F): BFS for

Spatial shortest paths, a relational query against a ground schema for Relational,

a constraint checker with partial credit for CSP.

核心技术壁垒 — dedicated note #

The irreplaceable piece is multiply-expressible task construction (§4.1 req 4,

App A.6). The maze grader, for instance, enumerates *16 equivalent coordinate

representations (origins × axis orderings) and accepts the move sequence if any*

scheme interprets it correctly. This is what defeats the trivial "pass-through"

strategy where an agent just forwards its partner's raw view: because the two views

can be expressed in different reference frames, concatenation without re-grounding

produces a wrong answer. Remove this property and the tax collapses to an

information-accessibility measure (any sufficiently long dialogue reconstructs

$v_1\cup v_2$ and tax→0). Reproducing it requires, per family, (a) a canonical

ground-truth solver and (b) a representation enumerator that certifies equivalence

across surface forms — the part a re-implementer is most likely to skip, which would

silently change what is being measured.

关键实现细节 (easy-to-miss tricks) #

1. ACTI! + critic symmetry. Termination requires the explicit marker ACTI!

with a candidate; crucially the solo-full control also gets a critic pass

(App H: ~1–2 pp lift, far below the tax), so the critic is a fairness equaliser —

without it, solo-full would be under-powered and the tax over-stated.

2. Anti-bias cluster naming (App B). When auto-naming the 16 failure clusters, a

black-list forbids generic words (verify, share, communicate, cross-check, …),

forcing concrete behavioural names (failed_to_confirm_wall_layout). Skipping

this black-list lets the LLM relabel every cluster as "poor communication" and the

cascade mapping becomes circular.

---

关系 #

• Predecessor / baseline: Davidson et al. 2025, "The Collaboration Gap"

(arXiv:2511.02687) — split-view mazes; this paper generalises from one task type to

a 32-task, 3-family suite with a heterogeneous-pair matrix and a formal game model.