The Collaboration Tax

Multi-agent systems built from language models are deployed on an untested assumption: that collaboration is free. Put two capable models on a problem, give them roles, and the team should do at least as well as either one alone.

We test that assumption directly. Take a problem one model already solves, split it into two halves so that neither half determines the answer, hand one half to each of two copies of that same model, and let them talk until they commit. Compare against the same model solving the merged problem alone. The difference is the collaboration tax.

tax = s_solo-full − s_collab

both terms scored by the same deterministic grader on a continuous [0, 1] scale

Because every task is solo-tractable by construction, the gap cannot be explained by the problem being hard. It is the price of having to coordinate. We measure it on 32 tasks and 11 models from 7 providers, 50 rollouts per cell, and find that it is large, ordered, mechanically predictable, and partly fixable with four clauses of prompt.

1What a split view looks like

Each instance is generated from a seed, then partitioned into two private views whose union is necessary for the answer. The two agents also see the same content in different surface forms, which is the grounding friction we want to stress.

Family Instance

Figure 1. Union-necessary partitions. Left: the full instance, which the solo control sees. Middle and right: what each agent sees. Hover any cell to see who holds it. In Spatial tasks the two agents hold complementary parts of a grid and must align on a reference frame; in Relational tasks they hold disjoint facts over a shared vocabulary; in CSP tasks they hold constraints expressed in different units, formats, or timezones.

Four properties hold for every one of the 32 tasks, and each one is load-bearing: drop it and the number we are about to define stops measuring coordination. Open any of them to see what breaks.

If the solo control is far from ceiling, both terms are capped by problem-solving capacity rather than by coordination quality, and the difference between them mixes two unrelated failure sources. A tax near zero would then be indistinguishable from a regime where the solo agent and the pair both fail simply because the task is hard.

If one view already contained the full instance, the pair could ignore the other agent and reproduce the solo policy exactly. The tax would be zero by construction, no matter how badly the two agents coordinate. Union-necessity is the minimum non-degeneracy that gives the quantity a chance to be positive.

Ground truth comes from BFS, a topological sort, or a constraint check, and path answers are accepted under all sixteen origin, orientation, and axis-order conventions so that a correct route in an unexpected frame is not punished. A stochastic grader would add a noise source to both terms that averaging within a cell never removes, and the estimator would stop converging to the quantity we defined.

If the two views could simply be concatenated in a canonical form both agents already share, the pair could emulate the centralised solver at zero coordination effort and the tax would collapse to zero for trivial reasons. Different origins, axis orders, naming conventions, and timezones mean the views cannot be pasted together before they are aligned, so approaching the upper bound requires actual coordination. That is the competence we are trying to price.

The agents exchange messages prefixed with [other agent]: until one of them emits the termination marker with a candidate answer, or the dialogue hits its turn cap. A grader model only converts free text into a structured answer; the score itself is computed by a deterministic program.

2What the number means

A difference between two success rates is only interesting if you know what its sign means, what it would take for it to be zero, and what it says about the two agents that produced it. Reading a paired execution as a two-player cooperative team with private information answers all three.

Definition · collaboration tax

Write v({1}) and v({2}) for what each agent scores given the whole problem, and v({1,2}) for what the pair scores when the problem is split between them. The tax is

tax = max ( v({1}), v({2}) ) − v({1,2})

It compares the coalition against its own best member, not against the average of its members. For two copies of one model the first term is just that model's solo score, which is the version reported everywhere below.

Three facts follow, and the widget below makes them concrete. Move the sliders, or load one of the real pairs we measured.

Load

agent 1 alone v({1}) 0.869

agent 2 alone v({2}) 0.352

the pair, split v({1,2}) 0.731

Figure 2. The tax as a property of a cooperative game. The grey markers are what each agent achieves alone with the full problem; the dashed line is the best of the two, which is the bar the pair has to clear. Whatever falls short of that line is the tax. The badges track the two structural conditions and the Shapley split of whatever the pair does earn.

x one problem instance

U the deterministic grader, into [0, 1]

v₁(x), v₂(x) the two private views

Π the paired protocol: the whole conversation, ending in one answer

v({i}) what agent i scores alone on the full instance

v({1,2}) what the pair scores on the split instance

The numbered lines below are the proofs as they appear in the appendix of the paper. The notes that open underneath them are written for this page and are not part of the paper. Hover any symbol to highlight it everywhere it appears.

Proposition 1 · information dominance

The tax cannot be negative

If a paired protocol Π produces an answer distribution that is measurable with respect to (v₁(x), v₂(x)), and V_solo is realised by a policy that is optimal among all measurable functions of x, then tax((M₁, M₂), T) ≥ 0.

1Let π^Π : X → Δ(A) be the answer distribution induced by the paired protocol, marginalised over the conversation, as a function of the joint private views (v₁(x), v₂(x)).

Everything the two agents say is integrated out. What survives is one object: a distribution over answers determined by the two private views. The dialogue is a way of computing that distribution, not an extra source of information.

2By union-necessity, (v₁(x), v₂(x)) is a measurable function of x, so π^Π is also a measurable function of x, and E_x[ U(x, a) | a ~ π^Π(x) ] is well-defined.

This is where the task design enters the mathematics. The splitter cuts the two views out of the instance, so composing splitter with protocol yields a policy that takes a full instance and returns an answer distribution. Union-necessity is what guarantees the pair of views carries exactly the instance, nothing more and nothing less.

3Let π^⋆ ∈ argmax_π E_{x, a ~ π(x)}[ U(x, a) ] over all measurable policies π : X → Δ(A).

Name the best policy that maps a full instance to an answer distribution. This is the centralised optimum: whatever any procedure could do with complete information, this policy does at least as well.

4Since π^Π lies in the feasible set, E[ U(x, π^⋆(x)) ] ≥ E[ U(x, π^Π(x)) ].

The whole argument, in one line. Step 2 placed the paired protocol inside the set that step 3 maximises over, so it cannot beat the maximum. Nothing here is about language models: it is a statement about what splitting information can and cannot do.

5Under the assumption, V_solo attains the supremum on the right-hand side, so tax((M₁, M₂), T) ≥ 0.

Note exactly what the assumption is doing: the sign is guaranteed relative to an optimal solo policy. That qualifier is what the paragraph below this proof cashes out, and it is why the measured version behaves differently.

∎

Proposition 2 · max-superadditivity

A positive tax is exactly a broken coalition

For any pair (M₁, M₂) and task T, tax > 0 if and only if the cooperative game with v({1}) = E[U(x, M_i(x))] and v({1,2}) = E[U(x, Π(M₁, M₂; v₁(x), v₂(x)))] violates max-superadditivity: v({1,2}) < max(v({1}), v({2})).

1Substituting the coalition form of the definition, tax > 0 is equivalent to max(v({1}), v({2})) − v({1,2}) > 0,

The definition, written in coalition notation: the first term is the best either member manages alone with the full problem, the second is what they manage together with it split.

2that is, v({1,2}) < max(v({1}), v({2})). This is precisely the failure of max-superadditivity for the cooperative game (N, v).

Move one term across, and that is the entire proof. Its triviality is the point: a positive tax is not merely evidence of a coalition failure, it is the failure of the condition that a coalition should be worth at least its strongest member. That is what licenses the cooperative-game vocabulary, including the Shapley reading below, instead of treating the gap as an isolated benchmark artefact.

∎ drag the sliders above until the red badge flips: it flips exactly here

Proposition 3 · Shapley value of a 2-agent cooperative game

What each member is credited with

For the cooperative game (N, v) with N = {1, 2}, the Shapley value of player i is φ_i = ½( v({i}) + v({1,2}) − v({j}) ), j ≠ i.

1The Shapley value of player i is the average marginal contribution over orderings σ of N: φ_i = (1 / |N|!) ∑_σ [ v(S^σ_i ∪ {i}) − v(S^σ_i) ],

The Shapley value averages what a member adds when it joins, over every order in which the coalition could have formed. It is the unique allocation satisfying efficiency, symmetry, and the null-player axiom.

2where S^σ_i is the set of players preceding i in ordering σ. For |N| = 2 there are two orderings.

With two players the average is over exactly two arrangements, so the sum can be written out in full. This is why the two-player case has a closed form while the general case does not.

3(i, j) contributes v({i}) − v(∅) = v({i}), and (j, i) contributes v({1,2}) − v({j}).

If i arrives to an empty room it contributes what it is worth alone. If it arrives second, it contributes whatever the team is worth minus what its partner had already secured. Those two numbers are usually very different, which is exactly why an averaging rule is needed.

4Averaging yields φ_i = ½( v({i}) + v({1,2}) − v({j}) ).

The table above computes both orderings from whatever the sliders currently say, and averages them into φ.

∎

Proposition 4 · subadditivity implies both members lose Shapley share

When the team underperforms, both members lose the same credit

If v({1,2}) < v({1}) + v({2}), then φ_i < v({i}) for both i ∈ {1, 2}.

1From the Shapley equation, φ_i − v({i}) = ½( v({1,2}) − v({1}) − v({2}) ),

Expand φ_i = ½( v({i}) + v({1,2}) − v({j}) ), subtract v({i}), and collect terms. The question being asked is the only one that matters to a member deciding whether to join: is my credited share bigger or smaller than what I make on my own?

2which is negative under the hypothesis.

Subadditivity says the team produces less than the two members would separately. The right-hand side is then negative, so each member is credited below its own solo value.

3The right-hand side does not depend on i, so both members lose by the same absolute amount.

The index vanished when the terms were collected, and that is the substantive content: the strong partner is not compensated for carrying the weak one. On the nano × gpt-5 configuration, gpt-5 is credited 0.668 against a solo value of 0.932.

∎ all four measured configurations satisfy the hypothesis on the majority of tasks

Why the measured numbers do go negative sometimes

Proposition 1 assumes the solo term is the best any policy could do with the full instance. In practice we substitute a single LLM given the full instance, which is not optimal: it can misread its own complete view. So the estimator can come out negative when the pair happens to beat that particular solo baseline, and a few cells in the next section do exactly that. Those cells are not evidence against Proposition 1; they are evidence that the solo control is a fallible stand-in for the centralised optimum.

One more caveat the theory makes explicit. The classical condition for a zero tax, that the agents can exchange enough messages to reconstruct the union of their views, assumes unbounded conversation. Our dialogues stop at a turn cap, so part of the residual tax that survives the intervention in Section 5 is plausibly a bound effect rather than a competence effect.

3The tax is not a number, it is a landscape

Two orderings hold without a single exception across the eleven models.

Show

Hover a cell for the underlying solo and collaborative scores.

Figure 3. Collaboration tax by model and task family. Each cell is one (model, family) pair, averaged over the tasks in that family at 50 rollouts each. Rows are sorted by each model's overall mean. Red is a positive tax; blue is the small set of cells where the pair beat the solo control.

Along the rows, the ordering is always Spatial ≻ Relational ≻ CSP. Path tasks carry persistent state, so a single misaligned step corrupts everything after it; relational query errors stay local to their query; constraint violations sit in between.

Down the rows, the tax shrinks with capability. The weakest models lose roughly half of their solo success to coordination. The top tier is not exempt either: gpt-5 still gives up 12 points of its solo score on Spatial tasks while being essentially perfect alone. The three weakest rows come from three different providers, so this is not one family's quirk.

Highlight

Hover a task for its solo and collaborative scores.

Figure 4. Per-task ratio gap, averaged across the eleven models. The category effect survives at task resolution: the high end is dominated by Spatial path tasks, the low end by CSP tasks whose answer is a short assignment over named entities. † marks the two tasks whose solo score falls short of the solo-tractability target, where the ratio is inflated by a small denominator; they are reported but treated as exploratory.

4Where the conversation breaks

We asked a model to describe, in open-ended text and under a prompt that names no candidate failure types, what went wrong in 700 failed rollouts. Clustering those descriptions yields 16 behaviourally specific themes, and the themes line up on four stages of conversational grounding.

The important part is what the stages are not. None of them is a reasoning failure. The same model, given the same information in one context, solves these problems. What breaks is the handling of information across two contexts: claiming without a source, not asking, not combining, not checking.

Figure 5. The four-stage cascade. For each stage, the rate at which failed rollouts (light) and successful rollouts (solid) satisfy it, split by task family, over 1,351 homogeneous rollouts. Every stage separates failure from success in every family. Click a stage for its definition.

The stages are separable but not independent: in most failed rollouts at least two fire together, and L3 and L4 are entangled in observational data, since a receiver cannot easily re-derive an answer the proposer never integrated. Four independent expert annotators re-labelled 100 stratified rollouts under a shared guideline; inter-rater agreement is moderate to substantial on all four stages (Fleiss' κ in [0.40, 0.69]), and agreement between the automated judge and the expert majority is substantial on L1, L2, and L3 (Cohen's κ in [0.67, 0.73]) and moderate on L4 (0.51).

If the gap is really driven by mechanical conversational behaviour, it should be predictable from that behaviour alone. It is. A ridge regression on conversation-shape features, with folds grouped by task so that every held-out fold contains tasks never seen in fitting, reaches out-of-fold R² = 0.475 and Spearman ρ = 0.760. Leave-one-task-out keeps positive held-out variance; leave-one-model-out preserves the rank order of cells but not their absolute level. Capability sets the intercept, conversation shape sets the slope.

5Four clauses buy back a third of it

If the four stages are mechanisms rather than correlates, then a clause targeting each one should move the number. We append one clause per stage to the system prompt and change nothing else: no retraining, no tuning, no change to the model.

Show

Figure 6. Stage-targeted prompt intervention, with leave-one-out ablation. The all four row adds every clause; each no Lk row drops one clause and keeps the other three, so reading down a column isolates that clause's marginal contribution. Subscripts are the half-width of the 95% confidence interval. Bold marks the column-wise maximum. Baseline is the unperturbed homogeneous run on the same model, tasks, and rollout count.

The combined clause set recovers 38.3% of the entire tax, with the confidence interval bounded above zero in every family. And each family turns out to be bottlenecked by a different layer: dropping L4 collapses the lift on Spatial, dropping L1 collapses it on Relational, dropping L2 costs the most on CSP.

The Spatial result is the cleanest evidence that L4 is causally separable from L3. In the observational data the two co-occur and L4 carries no separable regression weight beyond L3. Once the L3 clause externally enforces integration, L4 carries the Spatial bottleneck on its own.

Nothing here reaches the solo ceiling. But the fact that a fixed prompt recovers this much is the point: failures of reasoning or capability cannot be patched this cheaply, while failures of grounding, querying, integration, and re-derivation can.

6A strong partner does not average out

Pairing two different models raises an obvious question: does the team land between the two members, or somewhere else? We run two strong-weak contrasts, one cross-family and one within-family, in both slot orderings.

Figure 7. Mixed pairs land above the additive midpoint but below their strongest member. For each configuration: the two members' own homogeneous scores (grey), the midpoint one would predict if pairing simply averaged the two (hollow), and what the pair actually scores (filled). Averaged over the same 32-task suite.

The pair is pulled toward the stronger member rather than toward the midpoint, which is the good news. The bad news is where it stops: below the stronger member acting alone. In cooperative-game terms every configuration violates max-superadditivity, v({1,2}) < max(v({1}), v({2})), on the majority of tasks, and every member's Shapley share falls below what it earns by itself. Adding a weak partner to a strong model is not free; it costs the strong model part of what it could do alone.

With one pair per side, family-level effects are not detectable here; we report this as an existence proof of a qualitative pattern rather than a quantitative characterisation. The cascade of Section 4 continues to separate failure from success in mixed pairs, and the querying stage fires more often than in same-model pairs, as if asymmetry forces a question that identical partners skip.

7Running it

The task suite and the runners are on GitHub. Every task ships its generator, its view splitter, its prompts, and its deterministic grader, and any OpenAI-compatible endpoint works without code changes.

pip install -r requirements.txt
cp .env.example .env

# one task, all three single-model modes
python experiment.py --task maze --num-rollouts 10

# the full 32-task suite for one model
python run_all.py --models gpt-4o-mini --num-rollouts 50

# a mixed pair
python run_all.py --models claude-sonnet-4-5 gpt-4.1-nano --num-rollouts 50

New tasks are welcome. A task that stresses a source of grounding friction the current three families miss is the most useful thing to add: subclass Task, register it, and the runner, the modes, and the grading pipeline come for free.

Citation

The paper appears at EMNLP 2026 (Main Conference). The arXiv preprint and the BibTeX entry are coming soon.