Skip to content

Decomposition Buys Integrity, Not Yield

Sep 2026 · 0 citations · 15 references
Computer Science

Abstract

Multi-agent systems split a task across a tree of agents and justify the split with folklore: smaller contexts, cleaner separation, parallelism. We ask what the split does to how much of what the leaves discover reaches the root. Model a decomposition as a tree in which an agent handed $b$ items keeps any one with probability $r(b)$. If $r(b)=1/b$, every tree delivers exactly one finding, for every task size and every shape; we verify this to $2.4 \times 10^{-15}$ on 20,000 random irregular trees. If $r(b)=Cb^{-\delta}$, a depth-$k$ tree over $N$ findings yields $C^k N^{1-\delta}$: task size and architecture separate, and architecture contributes only $C \le 1$ per level, so flat is optimal for yield and no arrangement of agents escapes the exponent $\delta$. On 600 production deep-research traces $\delta = 0.34$ [0.30, 0.38], by three identifications that do not share a failure mode. At a hop where item boundaries come from the tool rather than a text heuristic, and where $b=1$ occurs 550 times, $C = 0.571$ [0.527, 0.615] is observed rather than extrapolated, over 16,082 hops. A tier also costs alignment: on 1,012 annotated multi-agent traces one brief in sixteen goes off-target, giving $\mu = 0.939$ and a per-tier penalty $C\mu = 0.536$. Depth is bought on two other axes. The root context is the only state that persists and the only one that cannot cheaply forget, and depth cuts its exposure from $N$ items to $N^{1/k}$. Depth is also cheaper: production flat agents bill as $N^{1.39}$, not the $N^2$ an append-only context predicts, and at equal spend two tiers overtake flat at 403 findings. Across every parameter we measured the model says 0.7% to 11.3% of production sessions are worth delegating, against 7.8% that do. A hazard model on 743,819 production tool calls finds that delegation does not respond to a filling context and is instead an opening move.

View source

Similar papers

#artificial intelligence Review Oct 2026

Viva La Vida: Verification and Accumulation Failures in Multi-Agent Proof Search

When an agentic prover works on an open problem, there is no proof assistant to fall back on: its verifier and lemma library are ultimately language models judging model outputs. We instrumented such a system end to end and analyzed $51{,}754$ traced observations across three full runs ($186$ hours, \$$5{,}694$). We fi...

Ben-Ji Xu, Ken Zheng, Noah Han · 0 citations
Preprint Aug 2026

Complete EFX Allocations Exist for Four Additive Agents and Up to Nine Goods

We prove that every fair-division instance with four agents, additive valuations over the non-negative reals, and at most nine indivisible goods admits a \emph{complete} allocation that is envy-free up to any good in the strong, zero-tolerant sense ($\EFXo$). The case $m=9=n+5$ lies beyond the previously known frontier...

Eyad Alkassar, Mahmoud Fouz, Kurt Mehlhorn · 2 citations
Preprint Sep 2026

Comparison-Based Fair Division of Indivisible Chores

We investigate the query complexity of fairly allocating $m$ indivisible chores among $n$ agents with additive cost functions. We depart from the standard cardinal model and assume only comparison access: an algorithm may ask an agent which of two bundles is less costly, but never observes numerical costs. Our first re...

Ze-Han Lin, Shengxin Liu, Biaoshuai Tao et al. · 0 citations
#artificial intelligence Preprint Sep 2026

Prompted Identity Degrades Cooperation in Multi-Agent LLM Systems

It is argued that when agents are aware of each other's model family, the group splits into clusters, where agents prefer interacting with others carrying their same label, although nothing in the task rewards or asks for such a split.

Xavier Del Giudice, Alessio Palma, Matteo Migliarini et al. · 0 citations
Preprint Sep 2026

Approximating Combinatorial Contracts with Arbitrary Costs

We study single-agent combinatorial contracts under linear payments. Under a reward share $\alpha\in[0,1]$, an agent chooses a subset $S$ of $n$ hidden actions, generating reward $f(S)$ at cost $c(S)$, to maximize $\alpha f(S)-c(S)$, while the principal receives $(1-\alpha)f(S)$. For nonnegative additive rewards and mo...

Xiaotie Deng, Han-Yu Li, Cheng-Hua Liu · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.