Rethinking Multi-Agent Collaboration: When More Is Less

# Rethinking Multi-Agent Collaboration: When More Is Less
Source: [https://arxiv.org/html/2609.19759](https://arxiv.org/html/2609.19759)
Yibo WuYihan ZhangAffiliation:Shanghai Jiao Tong Universityliujiaheng@nju\.edu\.cnMinyuan SunShenliang LiXinkai MaYifan LiJiaheng LiuNanjing University

††footnotetext:†Corresponding Author\.AbstractThe rapid advancement of large language models and single\-agent harnesses has reshaped the landscape of autonomous systems, raising a critical question of when multi\-agent collaboration offers genuine value\. As individual agent capabilities continue to scale, multi\-agent collaboration faces diminishing returns while incurring growing context overhead\. Through systematic analysis, we delineate the capability boundaries of multi\-agent collaboration relative to single\-agent alternatives, showing that it confers systematic benefits specifically in long\-horizon tasks with sparse dependencies, while single\-agent harnesses remain superior in tightly coupled, sequential workflows\. Building on these insights, we propose SAIGE, a lightweight multi\-agent collaboration mechanism based on Semantic\-Aware Incremental Graph Evolution\. SAIGE models collaboration as a dynamically evolving graph, where nodes are agent instances spawned on demand and edges encode semantic dependencies established through content\-based information retrieval\. Experiments on long\-horizon, complex task benchmarks show that SAIGE achieves a favorable trade\-off between context efficiency and task performance, and that scaling the agent pool or deepening the recursion level does not consistently improve outcomes\. Our findings suggest that multi\-agent superiority is bounded by task structure rather than universal, and that more agents do not necessarily make a system more intelligent\.

## 1Introduction

The rapid advancement of large language models \(LLMs\) has fundamentally reshaped the landscape of autonomous systems\. As foundation models grow increasingly capable of handling long\-horizon, complex tasks, the accompanying agent harnesses, such as Claude Code\([Anthropic, 2025](https://arxiv.org/html/2609.19759#bib.bib30)\), Codex\([OpenAI, 2025a](https://arxiv.org/html/2609.19759#bib.bib31)\), and DeepSeek Harness\([DeepSeek, 2026a](https://arxiv.org/html/2609.19759#bib.bib32)\), have matured into highly sophisticated infrastructures\. These single\-agent systems now deliver robust, end\-to\-end execution in real\-world scenarios, setting a formidable baseline for autonomy\. In stark contrast, generic multi\-agent collaboration frameworks often remain toy\-level in practice, lingering on simplistic benchmarks\([Paech, 2024](https://arxiv.org/html/2609.19759#bib.bib36);[Wang et al\., 2024b](https://arxiv.org/html/2609.19759#bib.bib35);[Peng et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib37)\)and marginal performance gains\([Yun et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib17);[Alzu’bi et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib21)\)\. This widening gap compels a critical reexamination of when and why multi\-agent collaboration offers genuine value over a well\-equipped single\-agent harness\.

Existing work often attributes the primary advantage of multi\-agent systems to context isolation, which partitions a task to prevent context pollution and context rot\([Huang et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib33);[Hong et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib34)\)\. While intuitively appealing, this explanation remains largely qualitative and lacks a rigorous theoretical foundation\. In this work, we aim to delineate the capability boundaries of multi\-agent collaboration through graph theory\. We formalize multi\-agent collaboration by modeling task trajectories as dependency graphs, where subtasks are partitioned by bridge edges\. This formalism reveals that multi\-agent collaboration is not a universal panacea\. Instead, it confers systematic benefits specifically in long\-horizon tasks with sparse dependencies, where context isolation can be exploited without incurring prohibitive coordination overhead\. Conversely, in tightly coupled, sequential workflows, single\-agent harnesses remain superior\.

Building on these theoretical insights, we propose SAIGE \(Semantic\-Aware Incremental Graph Evolution\), an elegant and general multi\-agent collaboration mechanism\. SAIGE models collaboration as a dynamically evolving graph, where nodes are agent instances spawned on demand and edges encode semantic dependencies established through content\-based information retrieval\. Rather than committing to a static topology upfront, SAIGE grows the subtask tree incrementally as execution unfolds, grounding orchestration decisions in actual execution feedback\. We empirically validate our framework on long\-horizon, complex task benchmarks, showing that SAIGE achieves a favorable trade\-off between context efficiency and task performance compared to existing generic multi\-agent methods\. Notably, our ablation study indicates that neither a larger agent pool nor a deeper recursion hierarchy consistently improves performance, suggesting that more agents do not necessarily make a system more intelligent\. Our findings offer a principled understanding of when collaboration provides meaningful advantage over single\-agent execution, and suggest that indiscriminate multi\-agent scaling warrants reconsideration\.

## 2Related Work

### 2\.1Multi\-Agent Collaboration

Multi\-agent collaboration governs how agents coordinate, communicate, and align behaviors toward shared objectives, evolving from rigid predefined structures to adaptive, context\-aware interactions\. Role allocation ranges from static, pre\-assigned responsibilities\([Chen et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib19);[Fei et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib18)\)to dynamic selection or runtime instantiation based on task demands\([Wu et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib2);[Chen et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib20);[Alzu’bi et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib21)\)\. Communication likewise spans explicit message passing via structured documents or natural language\([Hong et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib12);[Wang et al\., 2025c](https://arxiv.org/html/2609.19759#bib.bib22);[Mou et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib23)\)and implicit inference from environmental cues\([Park et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib24);[Zou et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib25)\)\. Information flow further structures these interactions as sequential pipelines or parallel exploration\([Shen et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib26);[Wang et al\., 2024a](https://arxiv.org/html/2609.19759#bib.bib27)\), while interaction patterns ultimately manifest as cooperative or competitive dynamics\([Yang et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib28);[Fu et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib29)\)\.

### 2\.2Multi\-Agent Topology

Multi\-agent topology serves as a critical structural framework for governing agent execution, communication, and interactions\. While early attempts often embedded structural organization implicitly\([Chan et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib1);[Wu et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib2);[Khattab et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib3)\), recent practices have explicitly represented multi\-agent organizations as graphs\([Liu et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib4);[Zhuge et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib5);[Qian et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib6)\)\. These topologies generally fall into three representative paradigms: centralized, distributed, and hybrid\. Centralized topologies leverage a global coordinator for information aggregation and routing\([Zhang et al\., 2026a](https://arxiv.org/html/2609.19759#bib.bib7);[Li et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib8)\); distributed topologies employ peer\-to\-peer communication and localized routing\([Yang et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib9);[Wang et al\., 2025a](https://arxiv.org/html/2609.19759#bib.bib10)\)to enhance autonomy and scalability; and hybrid topologies combine centralized strategic planning with decentralized execution\([Qian et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib11);[Hong et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib12);[Zhang et al\., 2026b](https://arxiv.org/html/2609.19759#bib.bib13)\)\. Concretely, these orchestration strategies manifest as distinct structural morphologies, including chain\([Qian et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib11);[Hong et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib12);[Holt et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib14)\), star\([Wu et al\., 2023](https://arxiv.org/html/2609.19759#bib.bib2);[Yan et al\., 2024](https://arxiv.org/html/2609.19759#bib.bib15)\), tree\([Ishibashi and Nishimura, 2024](https://arxiv.org/html/2609.19759#bib.bib16)\), and general graph topologies\([Qian et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib6);[Yun et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib17)\)\.

## 3Formalizing Multi\-Agent Collaboration

What is the core of multi\-agent collaboration, and under what idealized conditions does it genuinely help? We take a deliberately idealized route: we ask what multi\-agent collaboration is fundamentally doing to a task, and derive its benefit from that answer, leaving the gap between the idealized and the practical as a source of empirically testable predictions rather than a hidden assumption\.

### 3\.1Preliminaries

#### 3\.1\.1Trajectory as a Dependency Directed Acyclic Graph

Consider a task trajectory of lengthTT:τ=\{x1,x2,…,xT\}\\tau=\\\{x\_\{1\},x\_\{2\},\\ldots,x\_\{T\}\\\}, where eachxt=\(ot,at\)x\_\{t\}=\(o\_\{t\},a\_\{t\}\)denotes the interaction tuple at steptt, consisting of the new observationoto\_\{t\}received and the actionata\_\{t\}taken by the agent\. Letℋt=\{x1,…,xt−1\}\\mathcal\{H\}\_\{t\}=\\\{x\_\{1\},\\ldots,x\_\{t\-1\}\\\}denote the historical context available before generatingxtx\_\{t\}\. This history grows monotonically withtt, and the agent’s decisions may depend on arbitrary subsets of this history\.

To characterize these dependencies formally, we define a value functionQt​\(at∣ot,ℋt\)Q\_\{t\}\(a\_\{t\}\\mid o\_\{t\},\\mathcal\{H\}\_\{t\}\)that represents the expected return of taking actionata\_\{t\}given historical contextℋt\\mathcal\{H\}\_\{t\}\. For any pair of nodesxi,xt∈τx\_\{i\},x\_\{t\}\\in\\tauwithi<ti<t, we say thatxtx\_\{t\}has a direct dependency onxix\_\{i\}if removing the interaction tuplexix\_\{i\}from the historical context causes a significant drop in the action value at steptt:

\(xi,xt\)∈ℰ⇔Qt​\(at∣ot,ℋt∖\{xi\}\)<Qt​\(at∣ot,ℋt\)−δ,\(x\_\{i\},x\_\{t\}\)\\in\\mathcal\{E\}\\iff Q\_\{t\}\(a\_\{t\}\\mid o\_\{t\},\\mathcal\{H\}\_\{t\}\\setminus\\\{x\_\{i\}\\\}\)<Q\_\{t\}\(a\_\{t\}\\mid o\_\{t\},\\mathcal\{H\}\_\{t\}\)\-\\delta,\(1\)
whereℋt∖\{xi\}\\mathcal\{H\}\_\{t\}\\setminus\\\{x\_\{i\}\\\}denotes the historical context with the contribution ofxix\_\{i\}removed, andδ\>0\\delta\>0is a predefined threshold\. Since all edges point forward in time, the trajectory naturally induces a directed acyclic graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\), with node set𝒱=τ\\mathcal\{V\}=\\tau\. Each directed edge\(xi,xt\)∈ℰ⊆𝒱×𝒱\(x\_\{i\},x\_\{t\}\)\\in\\mathcal\{E\}\\subseteq\\mathcal\{V\}\\times\\mathcal\{V\}indicates that nodextx\_\{t\}directly depends on nodexix\_\{i\}\.

We further assume that a task trajectory contains no redundant interactions\. Specifically, every node in the trajectory contributes to at least one subsequent decision, implying that each node has out\-degree at least one in the dependency graph, with the terminal node serving as the unique sink\. Under this assumption, the induced DAG𝒢\\mathcal\{G\}is weakly connected\. This assumption is mild in practice, as interactions that do not influence any future step can be discarded from the trajectory without affecting the task outcome\.

![Refer to caption](https://arxiv.org/html/2609.19759v1/theory.png)Figure 1:Overview of the theoretical framework for multi\-agent collaboration\.
#### 3\.1\.2Decomposing Trajectories into Subtasks via Bridge Edges

Within the DAG𝒢\\mathcal\{G\}, certain edges serve as critical information channels connecting distinct regions of the graph\. An edge\(xi,xt\)∈ℰ\(x\_\{i\},x\_\{t\}\)\\in\\mathcal\{E\}is abridge edgeif its removal increases the number of weakly connected components of𝒢\\mathcal\{G\}\.

Letℰ∗⊆ℰ\\mathcal\{E\}^\{\*\}\\subseteq\\mathcal\{E\}denote the set of all bridge edges\. Removing all bridge edges from𝒢\\mathcal\{G\}decomposes the graph intommweakly connected components𝒢∖ℰ∗=𝒞1∪⋯∪𝒞m\\mathcal\{G\}\\setminus\\mathcal\{E\}^\{\*\}=\\mathcal\{C\}\_\{1\}\\cup\\cdots\\cup\\mathcal\{C\}\_\{m\}\. The corresponding subtask trajectory is defined as the ordered sequence of nodes in𝒞k\\mathcal\{C\}\_\{k\}:τ\(k\)=\{xn1,xn2,…,xnTk\}⊆τ\\tau\_\{\(k\)\}=\\\{x\_\{n\_\{1\}\},x\_\{n\_\{2\}\},\\ldots,x\_\{n\_\{T\_\{k\}\}\}\\\}\\subseteq\\tau, whereTk=\|𝒞k\|T\_\{k\}=\|\\mathcal\{C\}\_\{k\}\|, and the subtask trajectories collectively partition the original trajectory:τ=τ\(1\)∪τ\(2\)∪⋯∪τ\(m\)\\tau=\\tau\_\{\(1\)\}\\cup\\tau\_\{\(2\)\}\\cup\\cdots\\cup\\tau\_\{\(m\)\}\.

In multi\-agent systems, this decomposition has a natural interpretation: each subtaskτ\(k\)\\tau\_\{\(k\)\}is assigned to an individual agent responsible for executing that segment of the trajectory\. The bridge edges between components correspond to communication channels between the respective agents, enabling information flow across subtask boundaries when necessary\.

Let𝒱𝒮=\{τ\(1\),τ\(2\),…,τ\(m\)\}\\mathcal\{V\}\_\{\\mathcal\{S\}\}=\\\{\\tau\_\{\(1\)\},\\tau\_\{\(2\)\},\\ldots,\\tau\_\{\(m\)\}\\\}denote the set of subtask trajectories\. The directed edges between subtasks are induced by the bridge edgesℰ∗\\mathcal\{E\}^\{\*\}\. Since each bridge edge connects nodes from different components, this yields a well\-defined relation:

\(τ\(p\),τ\(q\)\)∈ℰ𝒮⇔∃\(xp,xq\)∈ℰ∗​such that​xp∈τ\(p\)​and​xq∈τ\(q\)\.\(\\tau\_\{\(p\)\},\\tau\_\{\(q\)\}\)\\in\\mathcal\{E\}\_\{\\mathcal\{S\}\}\\iff\\exists\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{E\}^\{\*\}\\text\{ such that \}x\_\{p\}\\in\\tau\_\{\(p\)\}\\text\{ and \}x\_\{q\}\\in\\tau\_\{\(q\)\}\.\(2\)
The pair𝒯=\(𝒱𝒮,ℰ𝒮\)\\mathcal\{T\}=\(\\mathcal\{V\}\_\{\\mathcal\{S\}\},\\mathcal\{E\}\_\{\\mathcal\{S\}\}\)forms asubtask treethat captures information flow at the granularity of subtasks\.

#### 3\.1\.3Context Cost Reduction

Letc⁡\(x\)c\(x\)denote the non\-negative computational overhead of including interaction tuplexxin the historical context\. For a subtask trajectoryτ\(k\)=\{xn1,…,xnTk\}\\tau\_\{\(k\)\}=\\\{x\_\{n\_\{1\}\},\\ldots,x\_\{n\_\{T\_\{k\}\}\}\\\}, letℬk⊆ℰ∗\\mathcal\{B\}\_\{k\}\\subseteq\\mathcal\{E\}^\{\*\}denote the set of bridge edges that enterτ\(k\)\\tau\_\{\(k\)\}, i\.e\.,ℬk=\{\(xp,xq\)∈ℰ∗∣xq∈τ\(k\)\}\.\\mathcal\{B\}\_\{k\}=\\\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{E\}^\{\*\}\\mid x\_\{q\}\\in\\tau\_\{\(k\)\}\\\}\.Letidx⁡\(x,τ\)\\operatorname\{idx\}\(x,\\tau\)denote the index of nodexxwithin trajectoryτ\\tau\. The total context cost of executing subtaskτ\(k\)\\tau\_\{\(k\)\}is decomposed as

C⁡\(τ\(k\)\)=CI​\(τ\(k\)\)\+CE​\(τ\(k\)\)=∑t=1Tk∑i=1t−1c⁡\(xni\)\+∑\(xp,xq\)∈ℬk∑i=idx⁡\(xq,τ\(k\)\)Tkc⁡\(xp\),C\(\\tau\_\{\(k\)\}\)=C\_\{I\}\(\\tau\_\{\(k\)\}\)\+C\_\{E\}\(\\tau\_\{\(k\)\}\)=\\sum\_\{t=1\}^\{T\_\{k\}\}\\sum\_\{i=1\}^\{t\-1\}c\(x\_\{n\_\{i\}\}\)\+\\sum\_\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{k\}\}\\sum\_\{i=\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(k\)\}\)\}^\{T\_\{k\}\}c\(x\_\{p\}\),\(3\)whereCI​\(τ\(k\)\)C\_\{I\}\(\\tau\_\{\(k\)\}\)accounts for the cost of accumulating historical context from nodes within the same subtask, andCE​\(τ\(k\)\)C\_\{E\}\(\\tau\_\{\(k\)\}\)accounts for the cost of pulling contextxpx\_\{p\}from predecessor subtasks via incoming bridge edges, starting from the position of the target nodexqx\_\{q\}through all subsequent steps\.

For the original monolithic trajectoryτ\\tau, there are no incoming bridge edges, soℬ=∅\\mathcal\{B\}=\\varnothing, and the cost is simply:

C⁡\(τ\)=∑t=1T∑i=1t−1c⁡\(xi\)\.C\(\\tau\)=\\sum\_\{t=1\}^\{T\}\\sum\_\{i=1\}^\{t\-1\}c\(x\_\{i\}\)\.\(4\)
Our key claim is that, under idealized conditions where the complete task trajectory is known in advance, decomposing the trajectory into subtasks reduces the total context cost\. The core of the proof is the following lemma, which shows that partitioning a trajectory along a single bridge edge does not increase the total context cost\. The detailed proof of Lemma 1 is deferred to Appendix[A](https://arxiv.org/html/2609.19759#A1)\.

###### Lemma 1\.

For any trajectoryτ\(S\)=τ\(L\)∪τ\(R\)\\tau\_\{\(S\)\}=\\tau\_\{\(L\)\}\\cup\\tau\_\{\(R\)\}partitioned into two subtask trajectories by a single bridge edge\(xL,xR\)\(x\_\{L\},x\_\{R\}\)withxL∈τ\(L\)x\_\{L\}\\in\\tau\_\{\(L\)\}andxR∈τ\(R\)x\_\{R\}\\in\\tau\_\{\(R\)\}, the sum of the context costs of the two subtask trajectories is no greater than the cost of the original trajectory:

C⁡\(τ\(L\)\)\+C⁡\(τ\(R\)\)≤C⁡\(τ\(S\)\)\.C\(\\tau\_\{\(L\)\}\)\+C\(\\tau\_\{\(R\)\}\)\\leq C\(\\tau\_\{\(S\)\}\)\.

Recursively applying Lemma 1 toτ\(L\)\\tau\_\{\(L\)\}andτ\(R\)\\tau\_\{\(R\)\}yields:

C⁡\(τ\)≥C⁡\(τ\(L\)\)\+C⁡\(τ\(R\)\)≥⋯≥∑k=1mC⁡\(τ\(k\)\)\.C\(\\tau\)\\geq C\(\\tau\_\{\(L\)\}\)\+C\(\\tau\_\{\(R\)\}\)\\geq\\cdots\\geq\\sum\_\{k=1\}^\{m\}C\(\\tau\_\{\(k\)\}\)\.This establishes that, when the task trajectory is known and the decomposition is performed correctly, multi\-agent decomposition reduces context cost\. It should be noted that this analysis does not account for context compression or other mitigation strategies that may alter the cost structure\.

#### 3\.1\.4Orchestration as Bridge Edge Prediction

The decomposition above ispost\-hoc: it presumes complete knowledge of the entire trajectoryτ\\tauand its dependency structure\. In practice, the trajectory unfolds sequentially, and the DAG𝒢\\mathcal\{G\}is not known in advance\. The objective of multi\-agent orchestration is therefore to predict the bridge edgesℰ∗\\mathcal\{E\}^\{\*\}before or during execution, without access to the complete trajectory\.

Letℰ∗\\mathcal\{E\}^\{\*\}denote the true set of bridge edges induced by the full trajectory, and letℰ^t\\hat\{\\mathcal\{E\}\}\_\{t\}be the set of bridge edges predicted by the orchestration strategy at timettbased on the observed prefixτ<t\\tau\_\{<t\}\. Since the true bridge edgesℰ∗\\mathcal\{E\}^\{\*\}are only revealed after the entire trajectory is complete, the predictionℰ^t\\hat\{\\mathcal\{E\}\}\_\{t\}concerns edges that lie in the future, i\.e\., edgesei→je\_\{i\\to j\}withj\>tj\>t\. The orchestration problem is to minimize the expected discrepancy between the true and predicted bridge edge sets:

minℰ^t⁡𝔼⁡\[ℒ⁡\(ℰ∗,ℰ^t\)∣τ<t\],\\min\_\{\\hat\{\\mathcal\{E\}\}\_\{t\}\}\\;\\mathbb\{E\}\\left\[\\mathcal\{L\}\(\\mathcal\{E\}^\{\*\},\\hat\{\\mathcal\{E\}\}\_\{t\}\)\\mid\\tau\_\{<t\}\\right\],\(5\)
whereℒ\\mathcal\{L\}is a loss function that measures the dissimilarity between two sets of directed edges over𝒱\\mathcal\{V\}\. A correct prediction partitions the trajectory into the true subtasks; an incorrect prediction results in suboptimal decomposition and diminished context cost reduction\.

### 3\.2Discussion

Our theoretical and empirical results jointly characterize when multi\-agent collaboration helps and why its benefits are bounded\.

When collaboration pays off\.Multi\-agent collaboration is effective precisely when a task admits relatively independent subtasks, so that each agent maintains a focused context window and excludes task\-irrelevant information\. A single\-agent system, by contrast, must accumulate observations indiscriminately, degrading the signal\-to\-noise ratio and increasing the risk of erroneous execution\. This benefit is contingent on the accuracy of bridge\-edge prediction: a mispredicted edge can trap an agent in a local deadlock while awaiting a dependency that never materializes, or inflate communication overhead as agents recover from an erroneous partition\.

The cost of isolation\.Context isolation localizes each agent’s working memory to its subtask, containing failures within the corresponding scope rather than letting them contaminate the global context\. This mitigates the incomplete workflows and premature termination that plague single\-agent execution on long\-horizon tasks, at the cost of higher aggregate token consumption, since decomposition extends the overall workflow\.

Why scaling does not help\.Because each bridge edge is predicted from an observed prefix, prediction errors accumulate as the number of subtasks grows, while additional agents incur higher coordination costs in communication, synchronization, and conflict resolution\. The marginal benefit of adding agents therefore diminishes, and may eventually be offset by accumulated errors and rising coordination overhead\. This explains why more agents do not necessarily make a system more intelligent, and motivates a mechanism that grows its collaboration graph only where the task structure permits\.

## 4Methodology

We propose Semantic\-Aware Incremental Graph Evolution \(SAIGE\), a lightweight mechanism for decomposing tasks under trajectory uncertainty\. Rather than predicting all bridge edges in advance, SAIGE evolves the subtask tree incrementally during execution, growing the structure only when semantic dependencies are revealed by execution feedback\.

![Refer to caption](https://arxiv.org/html/2609.19759v1/method.png)Figure 2:SAIGE: incremental node generation via progressive subtask decomposition, and progressive edge resolution via on\-demand message fetching\.### 4\.1Incremental Node Generation

Bridge edges are inherently difficult to predict reliably at the outset, and premature commitment to a static topology risks compounding early mispredictions\. Letℰ^t−1\\hat\{\\mathcal\{E\}\}\_\{t\-1\}andℰ^t\\hat\{\\mathcal\{E\}\}\_\{t\}denote the predicted bridge\-edge sets at consecutive steps, withℰ∗\\mathcal\{E\}^\{\*\}the ground truth\. Since SAIGE predicts incrementally, we haveℰ^t−1⊆ℰ^t\\hat\{\\mathcal\{E\}\}\_\{t\-1\}\\subseteq\\hat\{\\mathcal\{E\}\}\_\{t\}, and

P⁡\(ℰ^t⊆ℰ∗∣ℰ^t−1⊆ℰ∗,τ<t\)=P⁡\(ℰ^t⊆ℰ∗∣τ<t\)P⁡\(ℰ^t−1⊆ℰ∗∣τ<t\)≥P⁡\(ℰ^t⊆ℰ∗∣τ<t\),P\(\\hat\{\\mathcal\{E\}\}\_\{t\}\\subseteq\\mathcal\{E\}^\{\*\}\\mid\\hat\{\\mathcal\{E\}\}\_\{t\-1\}\\subseteq\\mathcal\{E\}^\{\*\},\\tau\_\{<t\}\)=\\frac\{P\(\\hat\{\\mathcal\{E\}\}\_\{t\}\\subseteq\\mathcal\{E\}^\{\*\}\\mid\\tau\_\{<t\}\)\}\{P\(\\hat\{\\mathcal\{E\}\}\_\{t\-1\}\\subseteq\\mathcal\{E\}^\{\*\}\\mid\\tau\_\{<t\}\)\}\\geq P\(\\hat\{\\mathcal\{E\}\}\_\{t\}\\subseteq\\mathcal\{E\}^\{\*\}\\mid\\tau\_\{<t\}\),\(6\)which indicates that deferring edge prediction until execution evidence accumulates is more reliable than committing to a topology upfront\.

Accordingly, SAIGE spawns subtask nodes on demand rather than pre\-allocating them\. A running agent delegates a child agent only when it detects a dependency boundary that satisfies the bridge\-edge property, that is, a single\-step dependency across which the subproblem can be executed independently given a bounded context summary\. When such a boundary is present, the subproblem is delegated and the child agent executes autonomously with a self\-contained instruction\. When no such boundary is present, no child is spawned and the parent agent continues to execute the task monolithically\. This conditional delegation is what allows SAIGE to avoid the decomposition penalty on densely coupled tasks\.

### 4\.2Progressive Edge Resolution

Edges between subtask nodes are established through progressive message fetching\. Each agent writes its result upon completion and retrieves dependencies only when needed\. Letℬk\\mathcal\{B\}\_\{k\}denote the set of bridge edges entering subtaskτ\(k\)\\tau\_\{\(k\)\}, and letidx⁡\(xq,τ\(k\)\)\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(k\)\}\)denote the step at which dependency onxpx\_\{p\}becomes active\. Progressive fetching incurs cost

∑\(xp,xq\)∈ℬk∑i=idx⁡\(xq,τ\(k\)\)Tkc⁡\(xp\)≤∑\(xp,xq\)∈ℬk∑i=1Tkc⁡\(xp\),\\sum\_\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{k\}\}\\sum\_\{i=\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(k\)\}\)\}^\{T\_\{k\}\}c\(x\_\{p\}\)\\leq\\sum\_\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{k\}\}\\sum\_\{i=1\}^\{T\_\{k\}\}c\(x\_\{p\}\),\(7\)where the right\-hand side loads all dependencies at the start\. Sparse on\-demand retrieval thus dominates push\-based communication in context cost\. More importantly, progressive fetching establishes communication channels dynamically rather than fixing them at decomposition time, allowing the collaboration graph to adapt to dependencies not fully determined in advance\. This converts global topology prediction into localized retrieval decisions grounded in execution feedback\.

## 5Experiments

### 5\.1Experimental Setup

#### 5\.1\.1Benchmarks

We evaluate on four benchmarks designed to assess agent capabilities on complex, long\-horizon, realistic tasks\.Terminal Bench 2\.1\([Merrill et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib39)\)tests agents on hard, realistic command\-line interface tasks, with resolution rate as the primary metric\.NL2Repo Bench\([Ding et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib40)\)evaluates long\-horizon repository generation from a single natural\-language requirements document, using the average test pass rate across all tasks as the primary metric\.Deep Research Bench II\([Li et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib41)\)diagnoses deep research agents through rubrics derived from expert reports, scored as the fraction of rubrics passed\.AgentIF\-OneDay\([Chen et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib42)\)is a task\-level instruction\-following benchmark for general AI agents in daily scenarios, employing instance\-level, rubric\-based scoring with binary evaluation, separated bonus/penalty items, and file\-content alignment\. Detailed descriptions of all benchmarks are provided in Appendix[B\.1](https://arxiv.org/html/2609.19759#A2.SS1)\.

#### 5\.1\.2Baselines

Single\-Agentexecutes the full task within a single agent context and serves as the monolithic baseline\. It runs on the nativeCodex CLIharness\([OpenAI, 2025b](https://arxiv.org/html/2609.19759#bib.bib38)\)\.Task Decomposition and Agent Generation \(TDAG\)\([Wang et al\., 2025b](https://arxiv.org/html/2609.19759#bib.bib45)\)is a multi\-agent framework that decomposes complex tasks into smaller subtasks, assigns each subtask to a specifically generated subagent, and continuously summarizes successful execution patterns into reusable skills for future reference\.DynTaskMAS\([Yu et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib46)\)is a dynamic task graph\-driven framework for asynchronous and parallel LLM\-based multi\-agent systems\.Graph\-of\-Agents \(GoA\)\([Yun et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib17)\)models multi\-agent LLM communication through a graph\-based framework, sampling relevant agents, constructing edges by evaluating response relevance, and aggregating responses via graph\-based pooling\. Further details on baseline implementations are provided in Appendix[B\.2](https://arxiv.org/html/2609.19759#A2.SS2)\.

#### 5\.1\.3Implementation

To ensure harness consistency, all methods are instantiated on the Codex CLI harness\. For multi\-agent methods, token usage is aggregated across all agents\. All baselines and our approach are built uponDeepSeek\-V4\-Pro\([DeepSeek, 2026c](https://arxiv.org/html/2609.19759#bib.bib43)\)as the foundation LLM\. For all multi\-agent methods evaluated in this work, we impose a uniform constraint on agent hierarchy: themaximum recursion depth is set to 1, meaning that spawned sub\-agents are not permitted to recursively create further sub\-agents\. Additionally, themaximum number of agentsis capped at 4\. These constraints are imposed uniformly across all multi\-agent methods to ensure system stability and prevent unbounded agent proliferation during execution\. We examine the effect of relaxing these constraints in the ablation study \(Section[5\.4](https://arxiv.org/html/2609.19759#S5.SS4)\) and further verify it on the multi\-agent baselines in Appendix[B\.3](https://arxiv.org/html/2609.19759#A2.SS3)\.

### 5\.2Main Results

Table[1](https://arxiv.org/html/2609.19759#S5.T1)presents the main results across all four benchmarks, reporting the primary metric along with input and output token counts for each benchmark\.

Table 1:Main results across four long\-horizon agent benchmarks\. For each benchmark, we report the primary metric and token usage\. The best result for each metric is underlined\.
Figure 3:Failure taxonomy across four benchmarks\.The four benchmarks differ in the dependency structure of their execution trajectories\. Terminal Bench 2\.1 and NL2Repo Bench exhibit dense inter\-step dependencies: tool invocations, file reads, and file writes form long upstream\-downstream chains in which later steps must condition on earlier outputs, leaving little room for independent execution\. Deep Research Bench II and AgentIF\-OneDay, by contrast, exhibit sparse dependencies, where large portions of the trajectory can proceed without conditioning on one another\. This distinction provides a principled basis for the two regimes of multi\-agent behavior observed below, with step\-level evidence in Appendix[C](https://arxiv.org/html/2609.19759#A3)\.

On the densely coupled benchmarks, generic multi\-agent methods fall below the single\-agent baseline, suggesting that decomposition fragments the dependency chain and that coordination overhead can outweigh the benefit of context isolation\. SAIGE does not exhibit the same degradation: it remains comparable to the single\-agent baseline on Terminal Bench 2\.1 and on NL2Repo Bench, while using fewer tokens than the other multi\-agent methods\. On the sparsely dependent benchmarks, decomposition appears more beneficial, and SAIGE performs competitively on both, with the most visible margin on AgentIF\-OneDay, without the token inflation observed in the other multi\-agent variants\. GoA, by contrast, employs a more elaborate orchestration design yet yields weaker results on these benchmarks, which suggests that added coordination complexity does not by itself translate into gains when it is not matched to the task’s dependency structure\.

Taken together, these results are consistent with our central claim that the benefit of multi\-agent collaboration is bounded by task structure rather than universal\. SAIGE does not dominate the single\-agent baseline on every benchmark, and its advantage is most evident on sparsely dependent tasks\. Across both regimes, however, it appears to attain a favorable trade\-off: it avoids the decomposition penalty on tightly coupled tasks, exploits context isolation on decomposable ones, and grows its collaboration graph in response to execution feedback rather than a pre\-committed topology\.

### 5\.3Failure Pattern Analysis

To understand how multi\-agent collaboration affects execution, we collect trajectories whose evaluation scores are significantly below the benchmark average and use DeepSeek\-V4\-Pro to semantically analyze their execution traces, yielding three recurring failure categories:Task Understanding and Execution Failure \(TUEF\),Incomplete Workflow and Premature Termination \(IWPT\), andLocal Deadlock \(LD\)\. Figure[3](https://arxiv.org/html/2609.19759#S5.F3)summarizes their distribution across the four benchmarks\.

On the tightly coupled benchmarks, multi\-agent methods are more prone to Local Deadlock: coordination introduces waiting, cyclic dependencies, and resource conflicts that prevent global progress\. On the decomposable benchmarks, by contrast, single\-agent methods more frequently exhibit Incomplete Workflow and Premature Termination, as the accumulation of context progressively degrades their ability to track the full tool chain, leading them to stop before the workflow is validated or the resolution criterion is satisfied\. These two tendencies together clarify why multi\-agent collaboration is beneficial only when the task structure admits effective decomposition\.

### 5\.4Ablation Study

We conduct ablation experiments on Deep Research Bench II and AgentIF\-OneDay to examine the sensitivity of SAIGE to agent count, recursion depth, and progressive message fetching\. Tables[2](https://arxiv.org/html/2609.19759#S5.T2)and[3](https://arxiv.org/html/2609.19759#S5.T3)report the primary benchmark score and aggregated token usage across all agents for each configuration\. For each recursion depth setting, we vary the maximum number of agents to isolate their joint effects, with “w/o Message Fetching” denoting SAIGE with progressive message fetching disabled under the default recursion depth \(Dmax=1D\_\{\\max\}=1\)\.

Table 2:Ablation results on Deep Research Bench II\. The default configuration is underlined\.Table 3:Ablation results on AgentIF\-OneDay\. The default configuration is underlined\.Across the tested configurations, increasing the agent budget does not consistently improve task performance\. On both benchmarks, expanding the agent pool beyond the default setting tends to yield lower scores and higher token consumption, with individual configurations deviating from this trend\. Deepening the recursion level shows a similar pattern: allowing sub\-agents to spawn further sub\-agents tends to reduce performance and increase token usage\. Disabling progressive message fetching is also associated with a comparable decline, most notably on AgentIF\-OneDay\. Token usage generally increases with agent count and recursion depth, while task performance does not show a corresponding gain\. These results suggest that more agents do not necessarily make a system more intelligent: beyond a certain point, the marginal agent appears to add coordination cost with limited additional problem\-solving capacity\.

## 6Conclusion

In this work, we reexamine the value of multi\-agent collaboration in the era of increasingly capable single\-agent harnesses\. Through a graph\-theoretic formalization of task trajectories, we show that multi\-agent collaboration is not universally beneficial, but confers systematic advantages specifically on long\-horizon tasks with sparse dependencies, where context isolation can be exploited without incurring prohibitive coordination overhead\. Building on this insight, we propose SAIGE, a multi\-agent collaboration mechanism that models collaboration as a dynamically evolving graph and establishes semantic dependencies through content\-based information retrieval\. Experiments on long\-horizon benchmarks show that SAIGE achieves a favorable trade\-off between context efficiency and task performance\. These findings suggest that multi\-agent superiority is bounded by task structure rather than universal, and that indiscriminate scaling of agents warrants reconsideration\.

## References

- Alzu’biet al\.\(2026\)S\. Alzu’bi, B\. Nama, A\. Kaz, A\. Eswaran, W\. Chen, S\. Khetan, R\. Bala, T\. Vu, and S\. OhROMA: recursive open meta\-agent framework for long\-horizon multi\-agent systems\.External Links:2602\.01848,[Link](https://arxiv.org/abs/2602.01848)Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p1.1),[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Anthropic \(2025\)AnthropicClaude code\.Note:[https://claude\.com/product/claude\-code](https://claude.com/product/claude-code)Accessed: 2026\-09\-06Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p1.1)\.
- Chanet al\.\(2023\)C\. Chan, W\. Chen, Y\. Su, J\. Yu, W\. Xue, S\. Zhang, J\. Fu, and Z\. LiuChatEval: towards better llm\-based evaluators through multi\-agent debate\.External Links:2308\.07201,[Link](https://arxiv.org/abs/2308.07201)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Chenet al\.\(2026\)K\. Chen, Q\. Wu, T\. Hou, T\. Tang, X\. Hu, Y\. Hou, B\. Li, C\. Qian, G\. Wang, H\. Chen, H\. Tian, H\. Zhang, H\. Bian, H\. Pan, H\. Zhang, H\. Zhou, J\. Cai, J\. Rao, J\. Ren, K\. Huang, L\. Z\. Huang, M\. Yuan, N\. Guo, Q\. Tang, Q\. Zhang, S\. Chen, S\. Chen, T\. T\. Li, X\. Guo, Y\. Zuo, Y\. Guo, Y\. Wang, Y\. Yu, Y\. Wang, Y\. Jiang, Y\. Tian, Y\. Zhang, Y\. Liu, Y\. Y\. Zeng, Z\. Shan, Z\. Yin, X\. Hu, Y\. Liu, Y\. Ren, and Y\. GongAgentIF\-oneday: a task\-level instruction\-following benchmark for general ai agents in daily scenarios\.External Links:2601\.20613,[Link](https://arxiv.org/abs/2601.20613)Cited by:[§B\.1](https://arxiv.org/html/2609.19759#A2.SS1.p4.1),[§5\.1\.1](https://arxiv.org/html/2609.19759#S5.SS1.SSS1.p1.1)\.
- Chenet al\.\(2023\)W\. Chen, Y\. Su, J\. Zuo, C\. Yang, C\. Yuan, C\. Chan, H\. Yu, Y\. Lu, Y\. Hung, C\. Qian, Y\. Qin, X\. Cong, R\. Xie, Z\. Liu, M\. Sun, and J\. ZhouAgentVerse: facilitating multi\-agent collaboration and exploring emergent behaviors\.External Links:2308\.10848,[Link](https://arxiv.org/abs/2308.10848)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Chenet al\.\(2025\)Y\. Chen, Y\. Yuan, Z\. Zhang, Y\. Zheng, J\. Liu, F\. Ni, J\. Hao, H\. Mao, and F\. ZhangSheetAgent: towards a generalist agent for spreadsheet reasoning and manipulation via large language models\.External Links:2403\.03636,[Link](https://arxiv.org/abs/2403.03636)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- DeepSeek \(2026a\)DeepSeekDeepSeek harness\.Note:[https://www\.deepseek\.com/harness](https://www.deepseek.com/harness)Accessed: 2026\-09\-06Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p1.1)\.
- DeepSeek \(2026b\)DeepSeekDeepSeek\-v4\-flash\-vision\-exp release: multimodal API now live\.Note:[https://api\-docs\.deepseek\.com/news/news260821](https://api-docs.deepseek.com/news/news260821)Accessed: 2026\-09\-06Cited by:[§B\.1](https://arxiv.org/html/2609.19759#A2.SS1.p4.3)\.
- DeepSeek \(2026c\)DeepSeekDeepSeek\-v4\-pro GA release\.Note:[https://api\-docs\.deepseek\.com/news/news260813/](https://api-docs.deepseek.com/news/news260813/)Accessed: 2026\-09\-06Cited by:[§B\.1](https://arxiv.org/html/2609.19759#A2.SS1.p4.3),[§5\.1\.3](https://arxiv.org/html/2609.19759#S5.SS1.SSS3.p1.1)\.
- Dinget al\.\(2026\)J\. Ding, S\. Long, C\. Pu, H\. Zhou, H\. Gao, X\. Gao, C\. He, Y\. Hou, F\. Hu, Z\. Li, W\. Shi, Z\. Wang, D\. Zan, C\. Zhang, X\. Zhang, Q\. Chen, X\. Cheng, B\. Deng, Q\. Gu, K\. Hua, J\. Lin, P\. Liu, M\. Li, X\. Pan, Z\. Peng, Y\. Qin, Y\. Shan, Z\. Tan, W\. Xie, Z\. Wang, Y\. Yuan, J\. Zhang, E\. Zhao, Y\. Zhao, H\. Zhu, L\. Zhu, C\. Zou, M\. Ding, J\. Jiao, J\. Liu, M\. Liu, Q\. Liu, C\. Tao, J\. Yang, T\. Yang, Z\. Zhang, X\. Chen, W\. Huang, and G\. ZhangNL2Repo\-bench: towards long\-horizon repository generation evaluation of coding agents\.External Links:2512\.12730,[Link](https://arxiv.org/abs/2512.12730)Cited by:[§B\.1](https://arxiv.org/html/2609.19759#A2.SS1.p2.1),[§5\.1\.1](https://arxiv.org/html/2609.19759#S5.SS1.SSS1.p1.1)\.
- Feiet al\.\(2026\)T\. Fei, C\. Chen, Y\. Pan, M\. Zheng, and M\. SongCodeDelegator: mitigating context pollution via role separation in code\-as\-action agents\.External Links:2601\.14914,[Link](https://arxiv.org/abs/2601.14914)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Fuet al\.\(2023\)Y\. Fu, H\. Peng, T\. Khot, and M\. LapataImproving language model negotiation with self\-play and in\-context learning from ai feedback\.External Links:2305\.10142,[Link](https://arxiv.org/abs/2305.10142)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Holtet al\.\(2025\)S\. Holt, M\. R\. Luyten, and M\. van der SchaarL2MAC: large language model automatic computer for extensive code generation\.External Links:2310\.02003,[Link](https://arxiv.org/abs/2310.02003)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Honget al\.\(2025\)K\. Hong, A\. Troynikov, and J\. HuberContext rot: how increasing input tokens impacts llm performance\.Technical reportChroma\.Note:Accessed: 2026\-09\-06External Links:[Link](https://trychroma.com/research/context-rot)Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p2.1)\.
- Honget al\.\(2024\)S\. Hong, M\. Zhuge, J\. Chen, X\. Zheng, Y\. Cheng, C\. Zhang, J\. Wang, Z\. Wang, S\. K\. S\. Yau, Z\. Lin, L\. Zhou, C\. Ran, L\. Xiao, C\. Wu, and J\. SchmidhuberMetaGPT: meta programming for a multi\-agent collaborative framework\.External Links:2308\.00352,[Link](https://arxiv.org/abs/2308.00352)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1),[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Huanget al\.\(2026\)J\. Y\. Huang, L\. Choshen, W\. Sun, O\. Khattab, R\. F\. Astudillo, M\. Damani, T\. Broderick, and J\. AndreasDo llms benefit from their own words?\.External Links:2602\.24287,[Link](https://arxiv.org/abs/2602.24287)Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p2.1)\.
- Ishibashi and Nishimura \(2024\)Y\. Ishibashi and Y\. NishimuraSelf\-organized agents: a llm multi\-agent framework toward ultra large\-scale code generation and optimization\.External Links:2404\.02183,[Link](https://arxiv.org/abs/2404.02183)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Khattabet al\.\(2023\)O\. Khattab, A\. Singhvi, P\. Maheshwari, Z\. Zhang, K\. Santhanam, S\. Vardhamanan, S\. Haq, A\. Sharma, T\. T\. Joshi, H\. Moazam, H\. Miller, M\. Zaharia, and C\. PottsDSPy: compiling declarative language model calls into self\-improving pipelines\.External Links:2310\.03714,[Link](https://arxiv.org/abs/2310.03714)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Liet al\.\(2025\)A\. Li, Y\. Xie, S\. Li, F\. Tsung, B\. Ding, and Y\. LiAgent\-oriented planning in multi\-agent systems\.External Links:2410\.02189,[Link](https://arxiv.org/abs/2410.02189)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Liet al\.\(2026\)R\. Li, M\. Du, B\. Xu, C\. Zhu, X\. Wang, and Z\. MaoDeepResearch bench ii: diagnosing deep research agents via rubrics from expert reports\.External Links:2601\.08536,[Link](https://arxiv.org/abs/2601.08536)Cited by:[§B\.1](https://arxiv.org/html/2609.19759#A2.SS1.p3.1),[§5\.1\.1](https://arxiv.org/html/2609.19759#S5.SS1.SSS1.p1.1)\.
- Liuet al\.\(2024\)Z\. Liu, Y\. Zhang, P\. Li, Y\. Liu, and D\. YangA dynamic llm\-powered agent network for task\-oriented agent collaboration\.External Links:2310\.02170,[Link](https://arxiv.org/abs/2310.02170)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Merrillet al\.\(2026\)M\. A\. Merrill, A\. G\. Shaw, N\. Carlini, B\. Li, H\. Raj, I\. Bercovich, L\. Shi, J\. Y\. Shin, T\. Walshe, E\. K\. Buchanan, J\. Shen, G\. Ye, H\. Lin, J\. Poulos, M\. Wang, M\. Nezhurina, J\. Jitsev, D\. Lu, O\. M\. Mastromichalakis, Z\. Xu, Z\. Chen, Y\. Liu, R\. Zhang, L\. L\. Chen, A\. Kashyap, J\. Uslu, J\. Li, J\. Wu, M\. Yan, S\. Bian, V\. Sharma, K\. Sun, S\. Dillmann, A\. Anand, A\. Lanpouthakoun, B\. Koopah, C\. Hu, E\. Guha, G\. H\. S\. Dreiman, J\. Zhu, K\. Krauth, L\. Zhong, N\. Muennighoff, R\. Amanfu, S\. Tan, S\. Pimpalgaonkar, T\. Aggarwal, X\. Lin, X\. Lan, X\. Zhao, Y\. Liang, Y\. Wang, Z\. Wang, C\. Zhou, D\. Heineman, H\. Liu, H\. Trivedi, J\. Yang, J\. Lin, M\. Shetty, M\. Yang, N\. Omi, N\. Raoof, S\. Li, T\. Y\. Zhuo, W\. Lin, Y\. Dai, Y\. Wang, W\. Chai, S\. Zhou, D\. Wahdany, Z\. She, J\. Hu, Z\. Dong, Y\. Zhu, S\. Cui, A\. Saiyed, A\. Kolbeinsson, J\. Hu, C\. M\. Rytting, R\. Marten, Y\. Wang, A\. Dimakis, A\. Konwinski, and L\. SchmidtTerminal\-bench: benchmarking agents on hard, realistic tasks in command line interfaces\.External Links:2601\.11868,[Link](https://arxiv.org/abs/2601.11868)Cited by:[§B\.1](https://arxiv.org/html/2609.19759#A2.SS1.p1.1),[§5\.1\.1](https://arxiv.org/html/2609.19759#S5.SS1.SSS1.p1.1)\.
- Mouet al\.\(2025\)X\. Mou, C\. Qian, W\. Liu, X\. Huang, and Z\. WeiEcoLANG: efficient and effective agent communication language induction for social simulation\.External Links:2505\.06904,[Link](https://arxiv.org/abs/2505.06904)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- OpenAI \(2025a\)OpenAICodex\.Note:[https://openai\.com/codex](https://openai.com/codex)Accessed: 2026\-09\-06Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p1.1)\.
- OpenAI \(2025b\)OpenAIIntroducing upgrades to codex\.Note:[https://openai\.com/index/introducing\-upgrades\-to\-codex/](https://openai.com/index/introducing-upgrades-to-codex/)Accessed: 2026\-09\-06Cited by:[§B\.2](https://arxiv.org/html/2609.19759#A2.SS2.p1.1),[§5\.1\.2](https://arxiv.org/html/2609.19759#S5.SS1.SSS2.p1.1)\.
- Paech \(2024\)S\. J\. PaechEQ\-bench: an emotional intelligence benchmark for large language models\.External Links:2312\.06281,[Link](https://arxiv.org/abs/2312.06281)Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p1.1)\.
- Parket al\.\(2023\)J\. S\. Park, J\. C\. O’Brien, C\. J\. Cai, M\. R\. Morris, P\. Liang, and M\. S\. BernsteinGenerative agents: interactive simulacra of human behavior\.External Links:2304\.03442,[Link](https://arxiv.org/abs/2304.03442)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Penget al\.\(2024\)Q\. Peng, Y\. Chai, and X\. LiHumanEval\-xl: a multilingual code generation benchmark for cross\-lingual natural language generalization\.External Links:2402\.16694,[Link](https://arxiv.org/abs/2402.16694)Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p1.1)\.
- Qianet al\.\(2024\)C\. Qian, W\. Liu, H\. Liu, N\. Chen, Y\. Dang, J\. Li, C\. Yang, W\. Chen, Y\. Su, X\. Cong, J\. Xu, D\. Li, Z\. Liu, and M\. SunChatDev: communicative agents for software development\.External Links:2307\.07924,[Link](https://arxiv.org/abs/2307.07924)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Qianet al\.\(2025\)C\. Qian, Z\. Xie, Y\. Wang, W\. Liu, K\. Zhu, H\. Xia, Y\. Dang, Z\. Du, W\. Chen, C\. Yang, Z\. Liu, and M\. SunScaling large language model\-based multi\-agent collaboration\.External Links:2406\.07155,[Link](https://arxiv.org/abs/2406.07155)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Shenet al\.\(2023\)Y\. Shen, K\. Song, X\. Tan, D\. Li, W\. Lu, and Y\. ZhuangHuggingGPT: solving ai tasks with chatgpt and its friends in hugging face\.External Links:2303\.17580,[Link](https://arxiv.org/abs/2303.17580)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Wanget al\.\(2025a\)J\. Wang, K\. Chen, X\. Song, K\. Zhang, L\. Ai, E\. Yang, and B\. ShiSymphony: a decentralized multi\-agent framework for scalable collective intelligence\.External Links:2508\.20019,[Link](https://arxiv.org/abs/2508.20019)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Wanget al\.\(2024a\)J\. Wang, J\. Wang, B\. Athiwaratkun, C\. Zhang, and J\. ZouMixture\-of\-agents enhances large language model capabilities\.External Links:2406\.04692,[Link](https://arxiv.org/abs/2406.04692)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Wanget al\.\(2025b\)Y\. Wang, Z\. Wu, J\. Yao, and J\. SuTDAG: a multi\-agent framework based on dynamic task decomposition and agent generation\.External Links:2402\.10178,[Link](https://arxiv.org/abs/2402.10178)Cited by:[§B\.2](https://arxiv.org/html/2609.19759#A2.SS2.p2.1),[§5\.1\.2](https://arxiv.org/html/2609.19759#S5.SS1.SSS2.p1.1)\.
- Wanget al\.\(2024b\)Y\. Wang, X\. Ma, G\. Zhang, Y\. Ni, A\. Chandra, S\. Guo, W\. Ren, A\. Arulraj, X\. He, Z\. Jiang, T\. Li, M\. Ku, K\. Wang, A\. Zhuang, R\. Fan, X\. Yue, and W\. ChenMMLU\-pro: a more robust and challenging multi\-task language understanding benchmark\.External Links:2406\.01574,[Link](https://arxiv.org/abs/2406.01574)Cited by:[§1](https://arxiv.org/html/2609.19759#S1.p1.1)\.
- Wanget al\.\(2025c\)Z\. Wang, S\. Moriyama, W\. Wang, B\. Gangopadhyay, and S\. TakamatsuTalk structurally, act hierarchically: a collaborative framework for llm multi\-agent systems\.External Links:2502\.11098,[Link](https://arxiv.org/abs/2502.11098)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Wuet al\.\(2023\)Q\. Wu, G\. Bansal, J\. Zhang, Y\. Wu, B\. Li, E\. Zhu, L\. Jiang, X\. Zhang, S\. Zhang, J\. Liu, A\. H\. Awadallah, R\. W\. White, D\. Burger, and C\. WangAutoGen: enabling next\-gen llm applications via multi\-agent conversation\.External Links:2308\.08155,[Link](https://arxiv.org/abs/2308.08155)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1),[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Yanet al\.\(2024\)Y\. Yan, Y\. Zhang, and K\. HuangDepending on yourself when you should: mentoring llm with rl agents to become the master in cybersecurity games\.External Links:2403\.17674,[Link](https://arxiv.org/abs/2403.17674)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Yanget al\.\(2026\)B\. Yang, L\. Xu, L\. Zeng, Y\. Guo, S\. Jiang, W\. Lu, K\. Liu, Y\. Li, X\. Jiang, G\. Xing, and Z\. YanProAgent: harnessing on\-demand sensory contexts for proactive llm agent systems in the wild\.External Links:2512\.06721,[Link](https://arxiv.org/abs/2512.06721)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.
- Yanget al\.\(2025\)Y\. Yang, H\. Chai, S\. Shao, Y\. Song, S\. Qi, R\. Rui, and W\. ZhangAgentNet: decentralized evolutionary coordination for llm\-based multi\-agent systems\.External Links:2504\.00587,[Link](https://arxiv.org/abs/2504.00587)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Yuet al\.\(2025\)J\. Yu, Y\. Ding, and H\. SatoDynTaskMAS: a dynamic task graph\-driven framework for asynchronous and parallel llm\-based multi\-agent systems\.Proceedings of the International Conference on Automated Planning and Scheduling35\(1\),pp\. 288–296\.External Links:ISSN 2334\-0835,[Link](http://dx.doi.org/10.1609/icaps.v35i1.36130),[Document](https://dx.doi.org/10.1609/icaps.v35i1.36130)Cited by:[§B\.2](https://arxiv.org/html/2609.19759#A2.SS2.p3.1),[§5\.1\.2](https://arxiv.org/html/2609.19759#S5.SS1.SSS2.p1.1)\.
- Yunet al\.\(2026\)S\. Yun, J\. Peng, P\. Li, W\. Fan, J\. Chen, J\. Zou, G\. Li, and T\. ChenGraph\-of\-agents: a graph\-based framework for multi\-agent llm collaboration\.External Links:2604\.17148,[Link](https://arxiv.org/abs/2604.17148)Cited by:[§B\.2](https://arxiv.org/html/2609.19759#A2.SS2.p4.1),[§1](https://arxiv.org/html/2609.19759#S1.p1.1),[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1),[§5\.1\.2](https://arxiv.org/html/2609.19759#S5.SS1.SSS2.p1.1)\.
- Zhanget al\.\(2026a\)R\. Zhang, X\. Jiang, Z\. Yang, Z\. Zhang, J\. Gao, Y\. Xiao, T\. Feng, Y\. Fang, Y\. Liu, R\. Li, H\. Lai, H\. Huang, X\. Chu, J\. Zhao, and Y\. WangStackPlanner: a centralized hierarchical multi\-agent system with task\-experience memory management\.External Links:2601\.05890,[Link](https://arxiv.org/abs/2601.05890)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Zhanget al\.\(2026b\)W\. Zhang, L\. Zeng, Y\. Xiao, Y\. Li, C\. Cui, Y\. Zhao, R\. Hu, Y\. Liu, Y\. Zhou, and B\. AnAgentOrchestra: orchestrating multi\-agent intelligence with the tool\-environment\-agent\(tea\) protocol\.External Links:2506\.12508,[Link](https://arxiv.org/abs/2506.12508)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Zhugeet al\.\(2024\)M\. Zhuge, W\. Wang, L\. Kirsch, F\. Faccio, D\. Khizbullin, and J\. SchmidhuberLanguage agents as optimizable graphs\.External Links:2402\.16823,[Link](https://arxiv.org/abs/2402.16823)Cited by:[§2\.2](https://arxiv.org/html/2609.19759#S2.SS2.p1.1)\.
- Zouet al\.\(2026\)J\. Zou, R\. Qiu, G\. Li, X\. Yang, K\. Tieu, P\. Lu, K\. Shen, H\. Tong, Y\. Choi, J\. He, J\. Zou, M\. Wang, and L\. YangLatent collaboration in multi\-agent systems\.External Links:2511\.20639,[Link](https://arxiv.org/abs/2511.20639)Cited by:[§2\.1](https://arxiv.org/html/2609.19759#S2.SS1.p1.1)\.

## Appendix AProofs

Theorem 1\.Letτ=\{x1,x2,…,xT\}\\tau=\\\{x\_\{1\},x\_\{2\},\\ldots,x\_\{T\}\\\}be a task trajectory with no redundant interactions, and letℰ\\mathcal\{E\}denote the set of directed edges defined by the dependency criterion\. Then the graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\)with𝒱=τ\\mathcal\{V\}=\\tauis a weakly connected directed acyclic graph\.

###### Proof\.

For any edge\(xi,xt\)∈ℰ\(x\_\{i\},x\_\{t\}\)\\in\\mathcal\{E\}, the dependency criterion requiresi<ti<t, since the value functionQtQ\_\{t\}is evaluated with respect to the historical contextℋt=\{x1,…,xt−1\}\\mathcal\{H\}\_\{t\}=\\\{x\_\{1\},\\ldots,x\_\{t\-1\}\\\}\. Thus every edge is oriented from a lower\-index vertex to a higher\-index vertex\.

Define a mappingϕ:𝒱→ℕ\\phi:\\mathcal\{V\}\\to\\mathbb\{N\}byϕ⁡\(xi\)=i\\phi\(x\_\{i\}\)=i\. For every edge\(xi,xt\)∈ℰ\(x\_\{i\},x\_\{t\}\)\\in\\mathcal\{E\}, we have

ϕ⁡\(xi\)=i<t=ϕ⁡\(xt\)\.\\phi\(x\_\{i\}\)=i<t=\\phi\(x\_\{t\}\)\.Thereforeϕ\\phiis a strict order\-preserving labeling of the vertices, which is a well\-known sufficient condition for acyclicity\. Equivalently, any directed path

xi1→xi2→⋯→xiℓx\_\{i\_\{1\}\}\\to x\_\{i\_\{2\}\}\\to\\cdots\\to x\_\{i\_\{\\ell\}\}must satisfy

i1<i2<⋯<iℓ,i\_\{1\}<i\_\{2\}<\\cdots<i\_\{\\ell\},precluding the existence of a directed cycle\. Hence𝒢\\mathcal\{G\}is a directed acyclic graph\.

We next establish weak connectivity\. By assumption, every node inτ\\taucontributes to at least one subsequent decision, implying that every vertexxix\_\{i\}withi<Ti<Thas out\-degree at least one, and the terminal vertexxTx\_\{T\}is the unique sink\. Hence, for every vertexxix\_\{i\}withi<Ti<T, there exists a directed path fromxix\_\{i\}toxTx\_\{T\}: starting fromxix\_\{i\}, each step follows an outgoing edge\(xi,xj\)\(x\_\{i\},x\_\{j\}\)withj\>ij\>i, and since indices strictly increase along edges and the trajectory is finite, the path must terminate atxTx\_\{T\}\.

Now consider any two verticesxi,xj∈𝒱x\_\{i\},x\_\{j\}\\in\\mathcal\{V\}\. Ifi=ji=jthe claim is trivial\. Otherwise, there exists a directed pathPiP\_\{i\}fromxix\_\{i\}toxTx\_\{T\}and a directed pathPjP\_\{j\}fromxjx\_\{j\}toxTx\_\{T\}\. Reversing the orientation ofPjP\_\{j\}yields an undirected path fromxTx\_\{T\}toxjx\_\{j\}\. ConcatenatingPiP\_\{i\}with the reversedPjP\_\{j\}gives an undirected walk fromxix\_\{i\}toxjx\_\{j\}in the underlying undirected graph of𝒢\\mathcal\{G\}\. Therefore any two vertices are connected in the underlying undirected graph, and𝒢\\mathcal\{G\}is weakly connected\. ∎

Theorem 2\.Let𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\)be a weakly connected directed acyclic graph, and letℰ∗⊆ℰ\\mathcal\{E\}^\{\*\}\\subseteq\\mathcal\{E\}be the set of bridge edges\. Define𝒱𝒮\\mathcal\{V\}\_\{\\mathcal\{S\}\}as the set of weakly connected components of𝒢∖ℰ∗\\mathcal\{G\}\\setminus\\mathcal\{E\}^\{\*\}, and let

ℰ𝒮=\{\(𝒞p,𝒞q\)∣∃\(u,v\)∈ℰ∗withu∈𝒞p,v∈𝒞q\}\.\\mathcal\{E\}\_\{\\mathcal\{S\}\}=\\\{\(\\mathcal\{C\}\_\{p\},\\mathcal\{C\}\_\{q\}\)\\mid\\exists\(u,v\)\\in\\mathcal\{E\}^\{\*\}\\text\{ with \}u\\in\\mathcal\{C\}\_\{p\},v\\in\\mathcal\{C\}\_\{q\}\\\}\.Then𝒯=\(𝒱𝒮,ℰ𝒮\)\\mathcal\{T\}=\(\\mathcal\{V\}\_\{\\mathcal\{S\}\},\\mathcal\{E\}\_\{\\mathcal\{S\}\}\)is a tree\.

###### Proof\.

We first prove that𝒯\\mathcal\{T\}is connected\. Since𝒢\\mathcal\{G\}is weakly connected, its underlying undirected graph is connected\. Contracting each weakly connected component𝒞i∈𝒱𝒮\\mathcal\{C\}\_\{i\}\\in\\mathcal\{V\}\_\{\\mathcal\{S\}\}to a single vertex preserves weak connectivity of the quotient graph\. The edge set of this quotient graph is preciselyℰ𝒮\\mathcal\{E\}\_\{\\mathcal\{S\}\}, as all edges between distinct components are bridge edges\. Hence𝒯\\mathcal\{T\}is weakly connected\.

We next prove that𝒯\\mathcal\{T\}is acyclic\. Suppose, for contradiction, that𝒯\\mathcal\{T\}contains an undirected cycleC𝒮C\_\{\\mathcal\{S\}\}of lengthℓ≥2\\ell\\geq 2, with vertices

𝒞i1,𝒞i2,…,𝒞iℓ\\mathcal\{C\}\_\{i\_\{1\}\},\\mathcal\{C\}\_\{i\_\{2\}\},\\ldots,\\mathcal\{C\}\_\{i\_\{\\ell\}\}and edges

e1,e2,…,eℓ∈ℰ𝒮,e\_\{1\},e\_\{2\},\\ldots,e\_\{\\ell\}\\in\\mathcal\{E\}\_\{\\mathcal\{S\}\},whereej=\(𝒞ij,𝒞ij\+1\)e\_\{j\}=\(\\mathcal\{C\}\_\{i\_\{j\}\},\\mathcal\{C\}\_\{i\_\{j\+1\}\}\)with indices taken moduloℓ\\ell\.

By the definition ofℰ𝒮\\mathcal\{E\}\_\{\\mathcal\{S\}\}, eacheje\_\{j\}corresponds to a bridge edge\(uj,vj\)∈ℰ∗\(u\_\{j\},v\_\{j\}\)\\in\\mathcal\{E\}^\{\*\}with

uj∈𝒞ijandvj∈𝒞ij\+1\.u\_\{j\}\\in\\mathcal\{C\}\_\{i\_\{j\}\}\\quad\\text\{and\}\\quad v\_\{j\}\\in\\mathcal\{C\}\_\{i\_\{j\+1\}\}\.Since each𝒞ij\\mathcal\{C\}\_\{i\_\{j\}\}is weakly connected, there exists an undirected pathPjP\_\{j\}within𝒞ij\+1\\mathcal\{C\}\_\{i\_\{j\+1\}\}connectingvjv\_\{j\}touj\+1u\_\{j\+1\}, with indices moduloℓ\\ell\.

Concatenating the bridge edge\(uj,vj\)\(u\_\{j\},v\_\{j\}\)with the pathPjP\_\{j\}for eachjjyields an undirected cycle in𝒢\\mathcal\{G\}that contains the bridge edge\(u1,v1\)\(u\_\{1\},v\_\{1\}\)but does not traverse it twice\. The removal of\(u1,v1\)\(u\_\{1\},v\_\{1\}\)therefore does not disconnectu1u\_\{1\}fromv1v\_\{1\}, as the alternative route through

P1,e2,P2,…,eℓP\_\{1\},e\_\{2\},P\_\{2\},\\ldots,e\_\{\\ell\}remains\. This contradicts the defining property of a bridge edge, namely that its removal destroys all paths between its endpoints\. Therefore𝒯\\mathcal\{T\}contains no undirected cycle\.

A weakly connected graph with no undirected cycles is a tree, completing the proof\. ∎

Lemma 1\.For any trajectoryτ\(S\)=τ\(L\)∪τ\(R\)\\tau\_\{\(S\)\}=\\tau\_\{\(L\)\}\\cup\\tau\_\{\(R\)\}partitioned into two subtask trajectories by a single bridge edge\(xL,xR\)\(x\_\{L\},x\_\{R\}\)withxL∈τ\(L\)x\_\{L\}\\in\\tau\_\{\(L\)\}andxR∈τ\(R\)x\_\{R\}\\in\\tau\_\{\(R\)\}, the sum of the context costs of the two subtask trajectories is no greater than the cost of the original trajectory:

C⁡\(τ\(L\)\)\+C⁡\(τ\(R\)\)≤C⁡\(τ\(S\)\)\.C\(\\tau\_\{\(L\)\}\)\+C\(\\tau\_\{\(R\)\}\)\\leq C\(\\tau\_\{\(S\)\}\)\.
###### Proof\.

We proceed by analyzing the internal and external context costs separately, then combine the two bounds to establish the result\.

##### Setup and notation\.

Both subsequences preserve the original temporal order, so every node inτ\(L\)\\tau\_\{\(L\)\}precedes every node inτ\(R\)\\tau\_\{\(R\)\}\. For any trajectoryτ\\tauand nodexi∈τx\_\{i\}\\in\\tau, letidx⁡\(xi,τ\)\\operatorname\{idx\}\(x\_\{i\},\\tau\)denote the position ofxix\_\{i\}inτ\\tau\.

For any trajectoryτ\\tau, the internal context cost can be rewritten as

CI​\(τ\)=∑xi∈τc⁡\(xi\)⋅\|\{xt∈τ:idx⁡\(xi,τ\)<idx⁡\(xt,τ\)\}\|,C\_\{I\}\(\\tau\)=\\sum\_\{x\_\{i\}\\in\\tau\}c\(x\_\{i\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau:\\operatorname\{idx\}\(x\_\{i\},\\tau\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\)\\\}\\bigr\|,which charges each nodexix\_\{i\}for every subsequent node in the same trajectory that must retainxix\_\{i\}in its historical context\.

For any trajectoryτ\\tauwith incoming bridge edge setℬ⁡\(τ\)⊆ℰ∗\\mathcal\{B\}\(\\tau\)\\subseteq\\mathcal\{E\}^\{\*\}, the external context cost can be rewritten as

CE​\(τ\)=∑\(xp,xq\)∈ℬ⁡\(τ\)c⁡\(xp\)⋅\|\{xt∈τ:idx⁡\(xq,τ\)≤idx⁡\(xt,τ\)\}\|,C\_\{E\}\(\\tau\)=\\sum\_\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\(\\tau\)\}c\(x\_\{p\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau:\\operatorname\{idx\}\(x\_\{q\},\\tau\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\)\\\}\\bigr\|,which charges each predecessor nodexpx\_\{p\}for every node inτ\\tauthat must retainxpx\_\{p\}after it is pulled across the bridge edge\(xp,xq\)\(x\_\{p\},x\_\{q\}\)\.

The total context cost isC⁡\(τ\)=CI​\(τ\)\+CE​\(τ\)C\(\\tau\)=C\_\{I\}\(\\tau\)\+C\_\{E\}\(\\tau\)\.

##### Internal cost difference\.

Sinceτ\(S\)=τ\(L\)∪τ\(R\)\\tau\_\{\(S\)\}=\\tau\_\{\(L\)\}\\cup\\tau\_\{\(R\)\}, the internal cost ofτ\(S\)\\tau\_\{\(S\)\}decomposes as

CI​\(τ\(S\)\)\\displaystyle C\_\{I\}\(\\tau\_\{\(S\)\}\)=CI​\(τ\(L\)\)\+CI​\(τ\(R\)\)\\displaystyle=C\_\{I\}\(\\tau\_\{\(L\)\}\)\+C\_\{I\}\(\\tau\_\{\(R\)\}\)\+∑xi∈τ\(L\)c\(xi\)⋅\|\{xt∈τ\(R\):idx\(xi,τ\(S\)\)<idx\(xt,τ\(S\)\)\}\|\\displaystyle\+\\sum\_\{x\_\{i\}\\in\\tau\_\{\(L\)\}\}c\(x\_\{i\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{i\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\+∑xj∈τ\(R\)c\(xj\)⋅\|\{xt∈τ\(L\):idx\(xj,τ\(S\)\)<idx\(xt,τ\(S\)\)\}\|\.\\displaystyle\+\\sum\_\{x\_\{j\}\\in\\tau\_\{\(R\)\}\}c\(x\_\{j\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(L\)\}:\\operatorname\{idx\}\(x\_\{j\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\.The first extra term accounts for the fact that in the monolithic trajectory, nodes inτ\(R\)\\tau\_\{\(R\)\}must retain preceding nodes inτ\(L\)\\tau\_\{\(L\)\}in their context\. The second extra term is symmetric: it accounts for nodes inτ\(R\)\\tau\_\{\(R\)\}whose context must be retained by subsequent nodes inτ\(L\)\\tau\_\{\(L\)\}\. Since both extra terms are non\-negative, dropping the second term yields the lower bound

CI​\(τ\(S\)\)−CI​\(τ\(L\)\)−CI​\(τ\(R\)\)≥∑xi∈τ\(L\)c⁡\(xi\)⋅\|\{xt∈τ\(R\):idx⁡\(xi,τ\(S\)\)<idx⁡\(xt,τ\(S\)\)\}\|\.C\_\{I\}\(\\tau\_\{\(S\)\}\)\-C\_\{I\}\(\\tau\_\{\(L\)\}\)\-C\_\{I\}\(\\tau\_\{\(R\)\}\)\\geq\\sum\_\{x\_\{i\}\\in\\tau\_\{\(L\)\}\}c\(x\_\{i\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{i\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\.\(8\)

##### External cost difference\.

LetℬS\\mathcal\{B\}\_\{S\}be the set of bridge edges enteringτ\(S\)\\tau\_\{\(S\)\}\. After partitioning by the bridge edge\(xL,xR\)\(x\_\{L\},x\_\{R\}\), the incoming bridge edge sets for the two subtasks are

ℬL=\{\(xp,xq\)∈ℬS∣xq∈τ\(L\)\},ℬR=\{\(xp,xq\)∈ℬS∣xq∈τ\(R\)\}∪\{\(xL,xR\)\}\.\\mathcal\{B\}\_\{L\}=\\\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{S\}\\mid x\_\{q\}\\in\\tau\_\{\(L\)\}\\\},\\qquad\\mathcal\{B\}\_\{R\}=\\\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{S\}\\mid x\_\{q\}\\in\\tau\_\{\(R\)\}\\\}\\cup\\\{\(x\_\{L\},x\_\{R\}\)\\\}\.We claim thatℬS\\mathcal\{B\}\_\{S\}decomposes disjointly as

ℬS=ℬL∪\(ℬR∖\{\(xL,xR\)\}\),\\mathcal\{B\}\_\{S\}=\\mathcal\{B\}\_\{L\}\\cup\\bigl\(\\mathcal\{B\}\_\{R\}\\setminus\\\{\(x\_\{L\},x\_\{R\}\)\\\}\\bigr\),withℬL∩\(ℬR∖\{\(xL,xR\)\}\)=∅\\mathcal\{B\}\_\{L\}\\cap\\bigl\(\\mathcal\{B\}\_\{R\}\\setminus\\\{\(x\_\{L\},x\_\{R\}\)\\\}\\bigr\)=\\varnothing\. Indeed, suppose for contradiction that there exists a bridge edge\(xp,xq\)∈ℬL∩\(ℬR∖\{\(xL,xR\)\}\)\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{L\}\\cap\\bigl\(\\mathcal\{B\}\_\{R\}\\setminus\\\{\(x\_\{L\},x\_\{R\}\)\\\}\\bigr\)\. Thenxqx\_\{q\}would belong to bothτ\(L\)\\tau\_\{\(L\)\}andτ\(R\)\\tau\_\{\(R\)\}, contradicting the fact thatτ\(L\)\\tau\_\{\(L\)\}andτ\(R\)\\tau\_\{\(R\)\}are disjoint subtask trajectories obtained by removing the bridge edge\(xL,xR\)\(x\_\{L\},x\_\{R\}\)\.

The external cost of the original trajectory is

CE​\(τ\(S\)\)\\displaystyle C\_\{E\}\(\\tau\_\{\(S\)\}\)=∑\(xp,xq\)∈ℬLc⁡\(xp\)⋅\|\{xt∈τ\(S\):idx⁡\(xq,τ\(S\)\)≤idx⁡\(xt,τ\(S\)\)\}\|\\displaystyle=\\sum\_\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{L\}\}c\(x\_\{p\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(S\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(S\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\+∑\(xp,xq\)∈ℬR∖\{\(xL,xR\)\}c\(xp\)⋅\|\{xt∈τ\(S\):idx\(xq,τ\(S\)\)≤idx\(xt,τ\(S\)\)\}\|\.\\displaystyle\+\\sum\_\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{R\}\\setminus\\\{\(x\_\{L\},x\_\{R\}\)\\\}\}c\(x\_\{p\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(S\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(S\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\.
The external costs of the two subtasks are

CE​\(τ\(L\)\)\+CE​\(τ\(R\)\)\\displaystyle C\_\{E\}\(\\tau\_\{\(L\)\}\)\+C\_\{E\}\(\\tau\_\{\(R\)\}\)=∑\(xp,xq\)∈ℬLc⁡\(xp\)⋅\|\{xt∈τ\(L\):idx⁡\(xq,τ\(L\)\)≤idx⁡\(xt,τ\(L\)\)\}\|\\displaystyle=\\sum\_\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{L\}\}c\(x\_\{p\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(L\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(L\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(L\)\}\)\\\}\\bigr\|\+∑\(xp,xq\)∈ℬR∖\{\(xL,xR\)\}c\(xp\)⋅\|\{xt∈τ\(R\):idx\(xq,τ\(R\)\)≤idx\(xt,τ\(R\)\)\}\|\\displaystyle\+\\sum\_\{\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{R\}\\setminus\\\{\(x\_\{L\},x\_\{R\}\)\\\}\}c\(x\_\{p\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(R\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(R\)\}\)\\\}\\bigr\|\+c\(xL\)⋅\|\{xt∈τ\(R\):idx\(xR,τ\(R\)\)≤idx\(xt,τ\(R\)\)\}\|\.\\displaystyle\+c\(x\_\{L\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(R\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(R\)\}\)\\\}\\bigr\|\.
For any\(xp,xq\)∈ℬL\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{L\}, sinceτ\(L\)⊆τ\(S\)\\tau\_\{\(L\)\}\\subseteq\\tau\_\{\(S\)\}and the relative positions of nodes withinτ\(L\)\\tau\_\{\(L\)\}are preserved inτ\(S\)\\tau\_\{\(S\)\}, we haveidx⁡\(xq,τ\(L\)\)=idx⁡\(xq,τ\(S\)\)\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(L\)\}\)=\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(S\)\}\)\. Consequently,

\{xt∈τ\(L\):idx⁡\(xq,τ\(L\)\)≤idx⁡\(xt,τ\(L\)\)\}⊆\{xt∈τ\(S\):idx⁡\(xq,τ\(S\)\)≤idx⁡\(xt,τ\(S\)\)\},\\\{x\_\{t\}\\in\\tau\_\{\(L\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(L\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(L\)\}\)\\\}\\subseteq\\\{x\_\{t\}\\in\\tau\_\{\(S\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(S\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\},and therefore

\|\{xt∈τ\(L\):idx⁡\(xq,τ\(L\)\)≤idx⁡\(xt,τ\(L\)\)\}\|\\displaystyle\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(L\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(L\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(L\)\}\)\\\}\\bigr\|≤\|\{xt∈τ\(S\):idx⁡\(xq,τ\(S\)\)≤idx⁡\(xt,τ\(S\)\)\}\|\.\\displaystyle\\leq\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(S\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(S\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\.The same argument applies to any\(xp,xq\)∈ℬR∖\{\(xL,xR\)\}\(x\_\{p\},x\_\{q\}\)\\in\\mathcal\{B\}\_\{R\}\\setminus\\\{\(x\_\{L\},x\_\{R\}\)\\\}, yielding

\|\{xt∈τ\(R\):idx⁡\(xq,τ\(R\)\)≤idx⁡\(xt,τ\(R\)\)\}\|\\displaystyle\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(R\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(R\)\}\)\\\}\\bigr\|≤\|\{xt∈τ\(S\):idx⁡\(xq,τ\(S\)\)≤idx⁡\(xt,τ\(S\)\)\}\|\.\\displaystyle\\leq\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(S\)\}:\\operatorname\{idx\}\(x\_\{q\},\\tau\_\{\(S\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\.
Thus, comparing the expressions forCE​\(τ\(S\)\)C\_\{E\}\(\\tau\_\{\(S\)\}\)andCE​\(τ\(L\)\)\+CE​\(τ\(R\)\)C\_\{E\}\(\\tau\_\{\(L\)\}\)\+C\_\{E\}\(\\tau\_\{\(R\)\}\)term by term, the only term present in the subtask costs but absent from the original cost is the newly introduced bridge edge cost

c⁡\(xL\)⋅\|\{xt∈τ\(R\):idx⁡\(xR,τ\(R\)\)≤idx⁡\(xt,τ\(R\)\)\}\|\.c\(x\_\{L\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(R\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(R\)\}\)\\\}\\bigr\|\.Therefore,

CE\(τ\(S\)\)−CE\(τ\(L\)\)−CE\(τ\(R\)\)≥−c\(xL\)⋅\|\{xt∈τ\(R\):idx\(xR,τ\(R\)\)≤idx\(xt,τ\(R\)\)\}\|\.C\_\{E\}\(\\tau\_\{\(S\)\}\)\-C\_\{E\}\(\\tau\_\{\(L\)\}\)\-C\_\{E\}\(\\tau\_\{\(R\)\}\)\\geq\-c\(x\_\{L\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(R\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(R\)\}\)\\\}\\bigr\|\.\(9\)

##### Combining the bounds\.

Combining \([8](https://arxiv.org/html/2609.19759#A1.E8)\) and \([9](https://arxiv.org/html/2609.19759#A1.E9)\), we have

C⁡\(τ\(S\)\)−C⁡\(τ\(L\)\)−C⁡\(τ\(R\)\)\\displaystyle C\(\\tau\_\{\(S\)\}\)\-C\(\\tau\_\{\(L\)\}\)\-C\(\\tau\_\{\(R\)\}\)=\[CI​\(τ\(S\)\)−CI​\(τ\(L\)\)−CI​\(τ\(R\)\)\]\\displaystyle=\\bigl\[C\_\{I\}\(\\tau\_\{\(S\)\}\)\-C\_\{I\}\(\\tau\_\{\(L\)\}\)\-C\_\{I\}\(\\tau\_\{\(R\)\}\)\\bigr\]\+\[CE​\(τ\(S\)\)−CE​\(τ\(L\)\)−CE​\(τ\(R\)\)\]\\displaystyle\+\\bigl\[C\_\{E\}\(\\tau\_\{\(S\)\}\)\-C\_\{E\}\(\\tau\_\{\(L\)\}\)\-C\_\{E\}\(\\tau\_\{\(R\)\}\)\\bigr\]≥∑xi∈τ\(L\)c⁡\(xi\)⋅\|\{xt∈τ\(R\):idx⁡\(xi,τ\(S\)\)<idx⁡\(xt,τ\(S\)\)\}\|\\displaystyle\\geq\\sum\_\{x\_\{i\}\\in\\tau\_\{\(L\)\}\}c\(x\_\{i\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{i\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|−c\(xL\)⋅\|\{xt∈τ\(R\):idx\(xR,τ\(R\)\)≤idx\(xt,τ\(R\)\)\}\|\.\\displaystyle\-c\(x\_\{L\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(R\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(R\)\}\)\\\}\\bigr\|\.
SincexL∈τ\(L\)x\_\{L\}\\in\\tau\_\{\(L\)\}, the first sum contains the term corresponding toxi=xLx\_\{i\}=x\_\{L\}:

∑xi∈τ\(L\)c⁡\(xi\)⋅\|\{xt∈τ\(R\):idx⁡\(xi,τ\(S\)\)<idx⁡\(xt,τ\(S\)\)\}\|\\displaystyle\\sum\_\{x\_\{i\}\\in\\tau\_\{\(L\)\}\}c\(x\_\{i\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{i\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|≥c⁡\(xL\)⋅\|\{xt∈τ\(R\):idx⁡\(xL,τ\(S\)\)<idx⁡\(xt,τ\(S\)\)\}\|\.\\displaystyle\\geq c\(x\_\{L\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{L\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\.
Because\(xL,xR\)\(x\_\{L\},x\_\{R\}\)is a bridge edge, we haveidx⁡\(xL,τ\(S\)\)<idx⁡\(xR,τ\(S\)\)\\operatorname\{idx\}\(x\_\{L\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(S\)\}\), and hence

\{xt∈τ\(R\):idx⁡\(xR,τ\(S\)\)≤idx⁡\(xt,τ\(S\)\)\}⊆\{xt∈τ\(R\):idx⁡\(xL,τ\(S\)\)<idx⁡\(xt,τ\(S\)\)\}\.\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(S\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\subseteq\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{L\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\.Sinceidx⁡\(xR,τ\(R\)\)=idx⁡\(xR,τ\(S\)\)\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(R\)\}\)=\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(S\)\}\), this implies

\|\{xt∈τ\(R\):idx⁡\(xR,τ\(R\)\)≤idx⁡\(xt,τ\(R\)\)\}\|\\displaystyle\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(R\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(R\)\}\)\\\}\\bigr\|≤\|\{xt∈τ\(R\):idx⁡\(xL,τ\(S\)\)<idx⁡\(xt,τ\(S\)\)\}\|\.\\displaystyle\\leq\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{L\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|\.
Therefore, the first term in the lower bound dominates the second term, and we obtain

C⁡\(τ\(S\)\)−C⁡\(τ\(L\)\)−C⁡\(τ\(R\)\)\\displaystyle C\(\\tau\_\{\(S\)\}\)\-C\(\\tau\_\{\(L\)\}\)\-C\(\\tau\_\{\(R\)\}\)≥c⁡\(xL\)⋅\|\{xt∈τ\(R\):idx⁡\(xL,τ\(S\)\)<idx⁡\(xt,τ\(S\)\)\}\|\\displaystyle\\geq c\(x\_\{L\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{L\},\\tau\_\{\(S\)\}\)<\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(S\)\}\)\\\}\\bigr\|−c\(xL\)⋅\|\{xt∈τ\(R\):idx\(xR,τ\(R\)\)≤idx\(xt,τ\(R\)\)\}\|\\displaystyle\-c\(x\_\{L\}\)\\cdot\\bigl\|\\\{x\_\{t\}\\in\\tau\_\{\(R\)\}:\\operatorname\{idx\}\(x\_\{R\},\\tau\_\{\(R\)\}\)\\leq\\operatorname\{idx\}\(x\_\{t\},\\tau\_\{\(R\)\}\)\\\}\\bigr\|≥0\.\\displaystyle\\geq 0\.
Thus,

C⁡\(τ\(L\)\)\+C⁡\(τ\(R\)\)≤C⁡\(τ\(S\)\),C\(\\tau\_\{\(L\)\}\)\+C\(\\tau\_\{\(R\)\}\)\\leq C\(\\tau\_\{\(S\)\}\),which completes the proof\. ∎

## Appendix BExperimental Details

### B\.1Benchmark Details

Terminal Bench 2\.1\[[Merrill et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib39)\]is a curated hard benchmark composed of tasks in computer terminal environments inspired by real\-world workflows\. Each task features a unique environment, a human\-written solution, and comprehensive tests for verification\. Because the framework is interactive, agent and model performance are difficult to decouple; many agent scaffolds are engineered to accommodate the tendencies of specific models, and agents are not explicitly required to use a terminal as their sole tool\. To remain faithful to the benchmark’s premise, a neutral testbed with a single headless terminal is adopted, and tasks are completed using only Bash commands\. The primary metric is the resolution rate\. In our evaluation, each task is attempted three times, and the resolution rate is computed as the number of tasks completed in a run divided by the total number of tasks, averaged over the three runs\.

NL2Repo Bench\[[Ding et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib40)\]evaluates repository\-level coding abilities with verifiable ground truth\. Tasks are derived from real\-world Python libraries characterized by modular architectures and authoritativepytestsuites\. Agents receive only a single natural\-language specification and must reconstruct the complete repository from scratch, including file structures and functional logic\. Correctness is strictly measured by executing the generated code against the original upstream tests\. Each task is scored by the fraction of unit tests it passes, and the final benchmark score is the average of these per\-task pass rates across all tasks\.

Deep Research Bench II\[[Li et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib41)\]diagnoses deep research agents through rubrics derived from expert reports\. The benchmark evaluates agents on information recall, analysis, and presentation, with rubrics constructed through a four\-stage pipeline of LLM extraction, self\-evaluation iteration, manual revision, and expert review\. For each task, the score is the fraction of rubrics it passes, and the final benchmark score is computed as the total number of rubrics passed divided by the total number of rubrics across all tasks\.

AgentIF\-OneDay\[[Chen et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib42)\]is a task\-level instruction\-following benchmark for general AI agents in daily scenarios\. It employs instance\-level, rubric\-based scoring with three key properties: binary scoring, where each rubric item is strictly evaluated as satisfied or not to ensure objectivity; distinction between bonus and penalty items, separating capability assessment from error rates; and file\-content alignment, enabling direct evaluation of agent\-generated files alongside textual output\. LetNNbe the total number of problems\. For theii\-th problem, letSi\+S\_\{i\}^\{\+\}andSi−S\_\{i\}^\{\-\}denote the sum of satisfied bonus points and triggered penalty points, andSimaxS\_\{i\}^\{\\max\}the maximum achievable score\. The normalized score is

si=max⁡\(0,Si\+−Si−\)Simax,s\_\{i\}=\\frac\{\\max\(0,S\_\{i\}^\{\+\}\-S\_\{i\}^\{\-\}\)\}\{S\_\{i\}^\{\\max\}\},\(10\)and the final benchmark score is the mean of these normalized scores:

Scorefinal=1N​∑i=1Nsi\.\\mathrm\{Score\}\_\{\\mathrm\{final\}\}=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}s\_\{i\}\.\(11\)Because AgentIF\-OneDay involves multimodal requirements such as image editing and in\-depth research, while DeepSeek\-V4\-Pro\[[DeepSeek, 2026c](https://arxiv.org/html/2609.19759#bib.bib43)\]does not natively support multimodal input, we provide a multimodal skill that allows the agent to invoke DeepSeek\-V4\-Flash\-Vision\-Exp\[[DeepSeek, 2026b](https://arxiv.org/html/2609.19759#bib.bib44)\]for image understanding\. This skill is implemented as a script that the agent can invoke directly, so the agent can decide when to delegate visual perception to the vision model without altering the benchmark’s evaluation protocol\.

### B\.2Baseline Details

Single\-Agentexecutes the full task within a single agent context, serving as the monolithic baseline\. It runs on the native Codex CLI harness\[[OpenAI, 2025b](https://arxiv.org/html/2609.19759#bib.bib38)\]\.

Task Decomposition and Agent Generation \(TDAG\)\[[Wang et al\., 2025b](https://arxiv.org/html/2609.19759#bib.bib45)\]is a multi\-agent framework built on dynamic task decomposition and agent generation\. It decomposes complex tasks into smaller subtasks and assigns each subtask to a specifically generated subagent, thereby improving adaptability in diverse and unpredictable real\-world tasks\. The decomposition is not static: subtasks are dynamically adjusted based on the outcomes of preceding tasks, allowing the framework to refine the task structure as execution unfolds\. Successful execution patterns are further summarized into reusable skills for future reference\.

DynTaskMAS\[[Yu et al\., 2025](https://arxiv.org/html/2609.19759#bib.bib46)\]is a dynamic task graph\-driven framework for asynchronous and parallel LLM\-based multi\-agent systems\. It orchestrates asynchronous and parallel operations through dynamic task graphs, and comprises four key components: a Dynamic Task Graph Generator that decomposes complex tasks while maintaining logical dependencies, an Asynchronous Parallel Execution Engine that optimizes resource utilization through efficient task scheduling, a Semantic\-Aware Context Management System that enables efficient information sharing among agents, and an Adaptive Workflow Manager that dynamically optimizes system performance\. This design supports scalable, high\-performance multi\-agent execution on complex, dynamic tasks\.

Graph\-of\-Agents \(GoA\)\[[Yun et al\., 2026](https://arxiv.org/html/2609.19759#bib.bib17)\]models multi\-agent LLM communication through a graph\-based framework\. It first samples relevant agents from a candidate pool, then constructs edges between them by evaluating the relevance of their responses to one another, and finally aggregates the refined responses via graph\-based pooling\. Message passing proceeds in two stages, source\-to\-target followed by target\-to\-source, allowing highly relevant agents to refine the responses of less relevant ones and vice versa\. To ensure consistency of the base model across all evaluated methods, we do not adopt GoA’s original multi\-source LLM design, in which different agents are backed by different foundation models\. Instead, we instantiate all agents with the same foundation LLM and differentiate them by assigning distinct roles, so that the comparison isolates the effect of orchestration rather than that of heterogeneous model capabilities\.

### B\.3Detailed Experimental Results

#### B\.3\.1Detailed Main Results

Beyond the aggregate metrics in Table[1](https://arxiv.org/html/2609.19759#S5.T1), we report the detailed breakdown when a benchmark provides finer\-grained evaluation dimensions\. These results complement the main comparison by exposing how each method performs across different evaluation dimensions and difficulty levels\.

Table 4:Detailed results on Deep Research Bench II\.Table 5:Detailed results on AgentIF\-OneDay\.
#### B\.3\.2Further Ablation Study

We further examine the ablation results under the five configurations for the multi\-agent baselines\. As shown in Figure[4](https://arxiv.org/html/2609.19759#A2.F4), increasing the agent count or deepening the recursion level generally reduces the task score while increasing token consumption\. Across both benchmarks and both baselines, i\.e\., TDAG and DynTaskMAS, the default configuration\(N=4,D=1\)\(N=4,D=1\)attains the most favorable overall trade\-off between task performance and token cost, whereas the remaining configurations fall into the lower\-right region relative to the default\. This indicates that additional agents or deeper recursion introduce coordination overhead without improving problem\-solving capacity\.

Figure 4:Ablation results under five configurations\. Each point corresponds to one configuration\.
#### B\.3\.3Fine\-Grained Analysis

To examine whether SAIGE performs conditional subtask decomposition according to task dependency structure rather than spawning agents indiscriminately, we record the average number of agents instantiated per task on each benchmark\. We further evaluate whether the predicted bridge edges correspond to the ground\-truth dependency boundaries\.

Figure 5:Average agent number per task across four benchmarks\.Figure 6:Bridge\-edge decomposition accuracy on AgentIF\-OneDay\.
As shown in Figure[6](https://arxiv.org/html/2609.19759#A2.F6), SAIGE instantiates substantially fewer agents on Terminal Bench 2\.1 and NL2Repo Bench, where the trajectory exhibits dense inter\-step dependencies and most subtasks cannot be executed independently\. On Deep Research Bench II and AgentIF\-OneDay, whose trajectories are sparsely dependent, SAIGE spawns more agents and exploits context isolation more aggressively\. The agent count therefore tracks the dependency structure of the benchmark rather than a fixed allocation policy, which is consistent with the conditional delegation criterion\. Notably, the average agent number remains below the maximum budget on all four benchmarks, indicating that SAIGE does not expand its collaboration graph beyond what the task structure permits\.

To obtain a ground\-truth decomposition for AgentIF\-OneDay, we first collect the successful trajectories produced by the Single\-Agent baseline on this benchmark\. For each such trajectory, we construct a semantic dependency matrix with DeepSeek\-V4\-Pro: for every stepttand each earlier stepi<ti<t, the model judges whether stepttsemantically conditions on the output of stepii, i\.e\., whether the action or observation at stepttwould change ifxix\_\{i\}were removed from the history\. This yields a binary dependency matrix\. Bridge edges are then identified as the single\-step dependencies whose removal partitions the trajectory into weakly connected components, and the resulting components define the ground\-truth decomposition points at which the task can be split into independently executable subtasks\.

We then evaluate the decomposition produced by each multi\-agent method against this ground truth\. For every sub\-agent trajectory generated by a method, we semantically match its instruction and executed steps to the ground\-truth subtask components using DeepSeek\-V4\-Pro, and count a predicted bridge edge as correct if it connects the same pair of subtask components as a ground\-truth bridge edge\. Precision, recall, and F1 are computed over the matched bridge edges across all tasks\.

Figure[6](https://arxiv.org/html/2609.19759#A2.F6)reports the results on AgentIF\-OneDay\. SAIGE achieves the most accurate decomposition among all multi\-agent methods, indicating that its incremental, execution\-grounded edge prediction recovers the true dependency boundaries more faithfully than static or pre\-committed decomposition strategies\. The improvement is most pronounced in recall, suggesting that SAIGE is less prone to omitting bridge edges, which is precisely the failure mode that produces local deadlocks\. These results provide direct evidence that the performance gains of SAIGE on sparsely dependent benchmarks are accompanied by, and plausibly attributable to, more accurate bridge\-edge prediction\.

## Appendix CCase Study

### C\.1Task Dependency Patterns

To illustrate the task dependency patterns that underlie our analysis, we select one representative single\-agent trajectory from Terminal Bench 2\.1 and one from AgentIF\-OneDay, and construct their dependency matrices through semantic dependency analysis\. Specifically, for each stepttin the trajectory, we take the historyℋt=\{x1,…,xt−1\}\\mathcal\{H\}\_\{t\}=\\\{x\_\{1\},\\ldots,x\_\{t\-1\}\\\}and perform semantic analysis with DeepSeek\-V4\-Pro to assess, for each earlier stepi<ti<t, whether stepttsemantically conditions on the output of stepii, i\.e\., whether the action or observation at stepttwould change ifxix\_\{i\}were removed from the history\. This yields a binary dependency matrixA∈\{0,1\}T×TA\\in\\\{0,1\\\}^\{T\\times T\}withAt,i=1A\_\{t,i\}=1if stepttdepends on stepii, andAt,i=0A\_\{t,i\}=0otherwise\.

![Refer to caption](https://arxiv.org/html/2609.19759v1/dependency_matrix_terminal.png)

![Refer to caption](https://arxiv.org/html/2609.19759v1/dependency_matrix_agentif.png)

Figure 7:Dependency matrices of representative single\-agent trajectories\.Figure[7](https://arxiv.org/html/2609.19759#A3.F7)shows the resulting dependency matrices for the two trajectories\. The Terminal Bench 2\.1 trajectory exhibits a dense dependency pattern in which a non\-negligible fraction of steps depend on distant predecessors, producing long\-range dependencies that span a wide range of earlier steps\. This is consistent with the long upstream\-downstream chains induced by continuous tool invocations, file reads, and file writes, where later steps must consume the outputs of earlier ones and independent execution is rarely possible\. The AgentIF\-OneDay trajectory, by contrast, exhibits a sparse and localized pattern: non\-zero entries concentrate near the diagonal, indicating that most steps depend only on their immediate predecessors and that large portions of the trajectory can proceed without conditioning on one another\. This contrast directly reflects the two structural regimes identified in our analysis, and provides a step\-level view of why multi\-agent decomposition is constrained on tightly coupled benchmarks while remaining feasible on sparsely dependent ones\.

### C\.2Bridge Edge Mis\-Prediction: A Local Deadlock Case

We illustrate the effect of bridge edge mis\-prediction on a representative task from Terminal Bench 2\.1,make\-doom\-for\-mips, in which the agent must build a MIPS ELF that runs under a supplied JavaScript MIPS VM\. The task contains a long upstream\-downstream chain: the VM defines the syscall ABI and the memory layout, the build must target a compatible MIPS ABI, and the resulting ELF must be validated by running it inside the VM\. A correct decomposition must preserve the bridge edges that connect these stages\.

```
// Ground-truth dependency structure
1  inspect vm.js
2      -> identify syscall ABI
3      -> identify memory layout
4  inspect doomgeneric/
5      -> identify build targets
6  configure MIPS toolchain
7      -> select ABI / soft-float
8  build doomgeneric_mips
9  run under vm.js
10     -> observe failure
11 -> adjust build flags
12 -> rebuild
13 -> validate execution
```

```
// Predicted dependency structure
1  inspect vm.js
2      -> identify syscall ABI
3  inspect doomgeneric/
4      -> identify build targets
5  configure MIPS toolchain
6      -> select ABI / soft-float
7  build doomgeneric_mips
8  run under vm.js
9      -> observe failure
10 -> adjust build flags
11 -> rebuild
12 -> validate execution
```

Figure 8:Ground\-truth and mis\-predicted dependency structures onmake\-doom\-for\-mips\.The error is one omitted bridge edge: the dependency from VM memory layout \(step 3\) to build configuration \(step 6\) in the ground\-truth dependency structure\. In the ground\-truth structure, this edge carries the constraint that determines the correct ABI and memory model\. In the predicted structure, the edge is absent\.

This omission produces a local deadlock\. The build agent configures the MIPS toolchain without the VM memory layout, while the validation agent repeatedly rebuilds and waits for a build that satisfies the omitted constraint\. Neither agent can break the cycle: the build agent adjusts flags that are not the actual bottleneck, and the validation agent keeps issuing rebuild\-and\-run cycles\.

Two costs follow\. Communication overhead rises because repeated build\-and\-run messages do not converge, and redundant execution accumulates because each cycle reruns the same build and the same VM validation\.

If the bridge edge is predicted correctly, the build configuration is conditioned on the VM memory layout and syscall ABI, and the correct ABI and soft\-float configuration are selected before the first build\. The validation stage then observes a consistent ELF, and the trajectory terminates after a small number of build\-and\-run cycles\. This contrast shows why orchestration is naturally formulated as bridge edge prediction: an omitted bridge edge does not merely reduce context cost reduction, but can turn a convergent workflow into a local deadlock\.

## Appendix DImpact Statement

This work studies when multi\-agent collaboration is beneficial for long\-horizon agentic tasks and when it is not\. Its primary impact is conceptual and practical: it clarifies that multi\-agent superiority is bounded by task structure rather than universal, and that blindly scaling the number of agents can increase coordination overhead without improving task performance\. This message is relevant to practitioners who build agentic systems, since it suggests that collaboration should be introduced selectively, based on the dependency structure of the target task, rather than adopted as a default design choice\.

On the positive side, the proposed SAIGE mechanism grows its collaboration graph in response to execution feedback and establishes semantic dependencies through content\-based information retrieval\. This may help reduce unnecessary context accumulation and improve the reliability of long\-horizon execution, which is relevant to applications such as software engineering agents, repository\-level code generation, and deep research assistants\. By making the cost\-performance trade\-off of multi\-agent decomposition explicit, our analysis may also encourage more disciplined evaluation and reporting practices in this area\.

On the risk side, more capable and autonomous agentic systems can be misused for harmful purposes, including automated exploitation of software vulnerabilities, unauthorized access to computing resources, or large\-scale generation of misleading content\. The benchmarks used in this work are designed for research evaluation and operate in controlled environments, but the underlying techniques are not inherently restricted to benign settings\. Multi\-agent decomposition may also introduce failure modes that are harder to audit, such as local deadlocks, mispredicted dependencies, and opaque coordination among agents, which can complicate debugging, accountability, and oversight\.