Recent work on multi-agent LLM systems reaches sharply different conclusions: some results show that a single agent with the same information and compute should dominate a delegated system, others that multi-agent gains grow with task depth. We argue that much of the disagreement comes from modelling different bottlenecks, and introduce a stylised reliability model built around two trade-offs. Decomposition reduces the burden of long contexts but incurs a handoff tax when information is compressed or transferred between agents. Redundancy gains from multiple samples, but its benefit depends on how much their failures are shared. With reasoning budget, verification, and task structure added, the model yields two crossover conditions: decomposition becomes preferable once the attention cost avoided by resetting context exceeds the handoff cost, and parallel sampling at equal budget is eventually preferable when its shared-failure floor lies below the error floor of one agent thinking longer. We connect these regimes to recent theoretical and empirical results. On a ledger-reconciliation task we measure the context-degradation curve and the handoff tax from single-agent and handoff runs alone. From these the model places the crossover at depth 10 and predicts decomposition to win at depths 20, 50, and 100. It does, on step-level and final-balance accuracy, and the decomposed system's success, which the prediction never sees, lands within 9 percentage points of the predicted rate at every depth.
Figures & tables
Status
Content
Proved, within the model
Theorems 1 to 6 , Corollaries 1 to 4 , and Proposition 2 . Proposition 1 is a derived approximation, numerically checked. Proofs are in Appendix A , and key closed forms and boundary cases are checked numerically in Appendix B .
Assumed
Assumptions 1 to 4 (product form, monotone curve, context growth, handoff monotonicity), a latent-rate mixture model for parallel samples, and the common-shock law used as a worked example. Proposition 3 is conditional on an untested hypothesis about verifiers.
Measured
A padded-context curve for one model (Section 9 ). An in-task curve, a handoff tax at three note lengths, and single-agent and decomposed success at three depths on one task with one model (Section 10 ).
Interpreted
The placement of published results in regimes (Section 8 ), the illustrative crossover depths computed from the pilot curve under assumed handoff costs (Section 9 ), the proposed mechanism for the instruction-compliance decay, and the location of the ledger crossover below depth 20 (Section 10 ).
Table 1: Reading guide. Where each kind of claim lives in the paper.
Symbol
Set in
Meaning
L , t
Sec. 3
task depth in steps, and the step index
c0 , k
Sec. 3
task statement size, and tokens added per step
s , m
Sec. 3
summary length, and steps per agent (chunk size)
b , o , ov
Sec. 3
token budget per step, and tokens reserved per summary and per verifier call
ε(c,b) , g(c,b)
Eq. ( 1 )
per-step failure probability at load c and budget b , and its log-loss −log(1−ε)
h , Δo , heff
Def. 1 , Eqs. ( 2 ), ( 5 )
handoff tax, writer’s overhead penalty, and their sum
Table 2: Notation. Loads and lengths are in tokens, budgets in thinking tokens, and losses in nats.
Figure 1: The three architectures the model expresses. The single agent’s context grows by k per step and its per-step failure follows the curve ε(c,b) . A decomposed system starts its first agent from the task statement, resets context at each boundary, and pays a handoff tax h there. A redundancy node runs N samples whose failures are dependent and combines them with a vote or a selector.
Figure 2: Success probability against depth for a single agent (black) and a single-step-per-agent decomposition at three handoff taxes. Left: a linear curve with g(c)=0.002+5×10−6c , k=400 , s=300 , c0=1000 , o=0 . Decomposition first wins at L=22 for h=0.02 and L=52 for h=0.05 , as ( 11 ) gives. Right: a flat curve, where the single agent never loses (Corollary 1 ). Parameters are illustrative, not fitted.
Figure 3: Failure probability of a majority vote over N samples at four common-shock correlation levels, against one agent given N times the budget, for a thinking curve ε(b)=0.08+0.22e−b at b=1 . The threshold from Theorem 6 is ρ∗=0.08/0.161=0.497 . At every plotted N>1 , correlations of 0 and 0.2 favour parallel sampling and 0.5 and 0.8 favour sequential thinking.
Prior result
Restriction
Recovered
Tightness
Tran and Kiela [1] , DPI
flat curve, equal budget, undegraded
Cor. 1
structural
Ao et al. [2] , Prop. 6, Thm. 8
flat curve, capacity-free centre
Cor. 1 , Def. 1
analogical
Tang et al. [3] , Props. 2.1, 2.2
flat, ρ=0 , selector r , free compute
Thm. 5 per step
structural
Su and Wu [10] , Thms. 4.1 to 4.3
h=0 vs. h>0 on task edges
dependency dichotomy
analogical
Yang et al. [11] , Thm. 4.3
L=1 , exchangeable samples
saturation at the shared-failure mass
analogical
Patel et al. [12]
L=1 , ρ=0
exponential gain, Thm. 5
exact
Table 3: Each prior result as a restriction of the model. Exact : the restricted model’s theorem has the same statement. Structural : the same conclusion under the same premise, reached in a different formal setting. Analogical : the mechanism corresponds, but the quantities differ and no reduction is claimed. Empirical : a measured result the model reproduces qualitatively.
Figure 4: Crossover depth L∗=⌊2(h+λs)/(λk)⌋+1 over the attention tax per step λk and the handoff tax h , at s/k=0.75 . White contours mark L∗∈{5,20,100,1000} . The three annotations are qualitative placements of the benchmark families discussed in the text, not fitted points.
c (tokens)
arithmetic failures
format failures
strict failures
strict ε(c) [95% CI]
107
11
0
11
0.055 [0.025, 0.090]
2,117
10
1
11
0.055 [0.020, 0.095]
8,023
11
10
20
0.100 [0.060, 0.145]
31,641
7
13
20
0.100 [0.060, 0.145]
63,129
12
51
59
0.295 [0.225, 0.365]
Table 4: Pilot on gpt-oss-20b at low reasoning and a 1,024-token budget, 200 calls per load (100 problems, two samples). Arithmetic: wrong final number. Format: required answer line missing. Strict: either. Intervals are 95% cluster-bootstrap intervals over problems.
Figure 5: Left: the three failure definitions against context load, with 95% cluster-bootstrap intervals over problems. Right: log-loss for the arithmetic and strict definitions, with a weighted hinge fit to the strict curve and the linear fit for comparison. The arithmetic curve is flat to within measurement. The strict curve is flat, then not, with the location of the change poorly determined.
load (tokens)
steps
all kinds [95% CI]
stationary kinds
stationary, stop-only
0 to 2k
1,200
0.027 [0.015, 0.042]
0.021
0.021
4k to 6k
1,500
0.071 [0.055, 0.089]
0.049
0.048
8k to 10k
1,100
0.112 [0.087, 0.138]
0.066
0.059
13k to 16k
1,403
0.185 [0.154, 0.219]
0.129
0.104
20k to 25k
1,393
0.294 [0.253, 0.341]
0.227
0.174
30k to 36k
1,509
0.598 [0.543, 0.661]
0.548
0.452
Table 5: The in-task curve from single-agent steps on the ledger task, gpt-oss-20b at a 512-token budget. Failure is the per-step increment failure rate. The stationary column excludes fee steps, and stop-only excludes calls that hit the budget. Seven of the twelve load bins, which together hold 9,178 of the 17,000 steps, are shown. The prediction and Figure 6 use all twelve. Intervals are cluster-bootstrap over ledgers.
predicted, stationary
observed, stationary
observed, final balance
L
single
decomposed
single
decomposed
single
decomposed
paired p (stationary / final)
20
0.46
0.61
0.50
0.69
0.49
0.64
0.014 / 0.049
50
0.01
0.27
0.06
0.24
0.04
0.18
0.001 / 0.003
100
0.00
0.07
0.00
0.11
0.00
0.10
< 0.001 / 0.002
Table 6: Predicted and observed success by depth on the ledger task, 100 paired ledgers per depth. Stationary: every non-fee increment right and every note’s balance carried forward. Final: final balance exactly right. Predictions use the stationary curve, increment tax hinc=0.026 , balance cost hbal=0.010 , and each ledger’s scored steps and boundaries, with every input taken from single-agent and handoff runs. Paired p values are exact McNemar tests.
Figure 6: Left: the in-task curve from single-agent steps, on all kinds, on the stationary kinds, and on stationary kinds with truncated calls removed, with the decomposed agents’ stationary steps at their own loads. Intervals are cluster-bootstrap over ledgers. Right: predicted success against depth for both systems from the curve and the measured handoff tax, evaluated on prefixes of the depth-100 ledgers, with the observed rates at depths 20, 50, and 100 and bootstrap intervals over ledgers. The dotted line is the predicted crossover.
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.
Weixiang Sun, Zehong Wang, Hong Huang +3
University of Notre Dame · Meta Superintelligence Labs · Simon Fraser University
Chain-of-thought prompting has popularized step-by-step reasoning in large language models, yet model performance still degrades as problem complexity and context length grow. By decomposing difficult tasks with long contexts into shorter, manageable ones, recent multi-agent paradigms offer a promising near-term solution to this problem. However, the fundamental capacities of such systems are poorly understood. In this work, we propose a theoretical framework to analyze the expressivity of multi-agent systems. We apply our framework to three algorithmic families: state tracking, recall, and k-hop reasoning. We derive bounds on (i) the number of agents required to solve the task exactly, (ii) the quantity and structure of inter-agent communication, and (iii) the achievable speedups as problem size and context scale. Our results identify regimes where communication is provably beneficial, delineate tradeoffs between agent count and bandwidth, and expose intrinsic limitations when either resource is constrained. We complement our theoretical analysis with a set of experiments on pretrained LLMs using controlled synthetic benchmarks. Empirical outcomes confirm the tradeoffs between key quantities predicted by our theory. Collectively, our analysis offers principled guidance for designing scalable multi-agent reasoning systems.
Michael Rizvi-Martel, Satwik Bhattamishra, Neil Rathi +2
Mila & Universit´e de Montr´eal · University of Oxford · Stanford University +1
Multi-agent LLM systems have shown promise for complex reasoning, yet recent evaluations reveal they often underperform single-model baselines. We identify a structural failure mode in sequential fine-tuning of shared-context teams: updating one agent shifts the team's context distribution, and when subsequent updates are evaluated on cached rollouts, this mismatch compounds. We formalize this as the compounding occupancy shift and prove that stale-occupancy evaluation incurs a penalty that scales quadratically with the number of agents. In contrast, intermediate-occupancy evaluation reduces this to linear scaling. We propose TeamTR, a trust-region framework that resamples trajectories after each component update and enforces per-agent divergence control, yielding rigorous per-update and per-stage improvement lower bounds. Experiments show that TeamTR outperforms single-agent and sequential baselines with 7.1% on average, mitigates coordination regressions, and supports plug-and-play component replacement. Code is available at https://github.com/Yydc/TeamTR.
Yi Xie, Siao Liu, Falong Fan +3
Department of Electrical & Computer Engineering, University of Arizona · Future Science and Engineering College, Soochow University · INSAIT, Sofia University ”St. Kliment Ohridski” +1