Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems

## Abstract

Abstract Recent advancements in large language model (LLM)-powered agents have shown that collective intelligence can significantly outperform individual capabilities, largely attributed to the meticulously designed inter-agent communication topologies. Though impressive in performance, existing multi-agent pipelines inherently introduce substantial token overhead, as well as increased economic costs, which pose challenges for their large-scale deployments. In response to this challenge, we propose an economical, simple, and robust multi-agent communication framework, termed AgentPrune , which can seamlessly integrate into mainstream multi-agent systems and prunes redundant or even malicious communication messages. Technically, AgentPrune is the first to identify and formally define the communication redundancy issue present in current LLM-based multi-agent pipelines, and efficiently performs one-shot pruning on the spatial-temporal message-passing graph, yielding a token-economic and high-performing communication topology.
Extensive experiments across six benchmarks demonstrate that AgentPrune (I) achieves comparable results as state-of-the-art topologies at merely $ 5.6 currency-dollar 5.6 \$5.6 cost compared to their $ 43.7 currency-dollar 43.7 \$43.7 , (II) integrates seamlessly into existing multi-agent frameworks with 28.1 % ∼ 72.8 % ↓ similar-to percent 28.1 percent 72.8 ↓ absent 28.1\%\sim 72.8\%\downarrow token reduction, and (III) successfully defend against two types of agent-based adversarial attacks with 3.5 % ∼ 10.8 % ↑ similar-to percent 3.5 percent 10.8 ↑ absent 3.5\%\sim 10.8\%\uparrow performance boost. The source code is available at https://github.com/yanweiyue/AgentPrune .

## 1 Introduction

Figure: Figure 1: The workflow of existing LLM-based (problem-solving) multi-agent systems. The agent-agent communication occurs at both intra- and inter-dialogue stages.
Refer to caption: /html/2410.02506/assets/img/map_intro.drawio.png

Large Language Model (LLM) based agents (Richards & et al., ; Nakajima, ; Reworkd, ) have demonstrated strong performance across a diverse range of tasks, including reasoning (Yao et al., ), code generation (Shinn et al., ), and even more complex applications like video gaming (Wang et al., ) and autopilot systems (Jin et al., ). Recent endeavors have shown that combining implicitly or explicitly different LLM-based agents into a team can outperform a single agent in handling complex tasks (Du et al., ; Liang et al., ; Wang et al., ; Jiang et al., ; Shinn et al., ; Zheng et al., ; Wu et al., ), which supports the presence of human-esque collaborative intelligence in multi-agent systems (Zhang et al., ). In practice, previous research
has explored approaches in which instances of LLMs, referred to as agents (Wang et al., ; Xi et al., ; Gao et al., ; Cheng et al., ; Ma et al., ), collaborate synergistically (e.g., through debate or reflection) to complete tasks (Du et al., ; Pezeshkpour et al., ; Guo et al., ; Du et al., ; Han et al., ) via diverse communication topologies (e.g., chain (Wei et al., ), tree (Yao et al., ), complete graph (Qian et al., ), random graph (Qian et al., ), optimizable graph (Zhuge et al., ), LLM-based network (Hao et al., ; Liu et al., )).
The exceptional performance of these cooperative agents significantly benefits from their interactive communication and collaboration, specifically how agents transmit, exchange, and assimilate information (Chan et al., ; Wang et al., ; Liu et al., ).

Figure: Figure 2: (Left) The accuracy comparison on MMLU (Hendrycks et al., ) among (1) a single gpt-3.5-turbo, (2) three gpt-3.5-turbo as agents equipped with intra-dialogue communication structures like chain and tree (Qian et al., ), complete graph, and GPTSwarm (Zhuge et al., ), and (3) those equipped with inter-dialogue communication structures like PHP (Zheng et al., ), LLM-Debate (Du et al., ), DyLAN (Liu et al., ) and our AgentPrune. (Middle) The prompt token consumption comparison on MMLU between different methods. (Right) The overview of our proposed AgentPrune.
Refer to caption: /html/2410.02506/assets/x1.png

Taking a closer look into the communication mechanisms in existing multi-agent systems, they typically involve two key types (as shown in [Figure 1](#S1.F1)):
❶ Intra-dialogue communication: For a given query/task, multiple agents interact–whether by cooperating (Du et al., ; Wu et al., ; Rasal, ), teaching (Zhang et al., ), or competing (Zhao et al., ; Fu et al., )–to produce a solution within a dialogue round;
❷ Inter-dialogue communication: In a specific manner—whether by summarizing (Chan et al., ; Shen et al., ), replicating (Yin et al., ; Du et al., ), or filtering (Liu et al., )—the content of the current dialogue is passed to the next round of interaction as a reference, initiating a new cycle of collaborative efforts.

To better illustrate the power of agent communication, [Figure 2](#S1.F2) (Left) compares the performance of a single gpt-3.5-turbo with three agents equipped with different inter/intra-dialogue communication structures. The results demonstrate that even the simplest communication framework significantly leads to a notable accuracy improvement, which vividly showcases the social intelligence and collaborative capabilities of LLMs (Mei et al., ).
However, the success of multi-agents comes at the cost of significantly increased token consumption, imposing substantial economic burdens (Wang et al., ), which are detrimental to the widespread application of multi-agent systems, as deployment on edge devices does not accommodate excessively costly inference (Liu et al., ). A piece of empirical evidence is in [Figure 2](#S1.F2) (Middle), where various communication methods result in a $2\sim 11.8\times$ increase in token consumption compared to the simple chain structure, severely undermining the token economy of existing multi-agent systems.

In the light of this limitation, we for the first time identify a significant phenomenon of Communication Redundancy (Meyer et al., ) within existing LLM-based multi-agent (LLM-MA) communication topologies, where a substantial portion of message passing does not contribute meaningfully to the collaborative intelligence. With this finding, we introduce an economical and versatile communication pruning framework for LLM-powered multi-agent systems, dubbed AgentPrune, which can be smoothly incorporated within various existing LLM-MA systems, offering comparable reasoning and planning performance as well as significantly lower token consumption. Practically, AgentPrune treats the entire LLM-MA framework as a spatial-temporal communication graph, in which each agent, along with its unique properties (e.g., profile (Li et al., ), external API tools (Zhuang et al., ), or knowledge base (Chen et al., )), is packaged as a node, communication between agents within the same dialogue forms spatial edges, and communication across dialogues forms temporal edges. By training a low-rank-principle-guided graph mask, AgentPrune efficiently identifies the important graph connectivities (i.e., message passing through edges). This comes with a one-shot pruning to derive a sparse yet informative communication graph (in [Figure 2](#S1.F2) (Right)), which is then fixed as the communication topology for subsequent token-economic and efficient reasoning.
Our contributions can be summarized as follows:

- ❶
System Discovery. We present a spatial-temporal graph paradigm to describe the communication topology of contemporary LLM-MA frameworks, and further identify and define the Communication Redundancy issue in current systems, wherein a significant portion of spatial and temporal edges, i.e., communication, does not contribute to collaborative intelligence.
- ❷
Pratical Solution. We propose AgentPrune, an economical, simple, and robust multi-agent communication pruning pipeline. By leveraging a trainable communication graph mask, AgentPrune identifies key message exchanges and prunes non-essential components in a one-shot manner, resulting in a sparse, token-economical, and highly informative communication graph. Notably, AgentPrune employs a low-rank principle to guide the graph mask training, successfully robustifying LLM-MA systems against various agent-targeted adversarial attacks.
- ❸
Experimental Validation. Extensive experiments on six benchmarks show that AgentPrune is: (1) high-performing, achieving comparable performance on MMLU at $\$5.6$ cost, to that of state-of-the-art communication topologies at $\$43.7$; (2) token-economical, integrating seamlessly into popular multi-agent frameworks including AutoGen and GPTSwarm, reducing their token cost by $28.1\%\sim 72.8\%\downarrow$; and (3) adversarially robust, successfully defending against two types of agent adversarial attacks, with a $3.5\%\sim 10.8\%\uparrow$ performance improvement.

## 2 LLM-MA as Spatial-temporal Graphs

##### Notations

We describe the whole multi-agent system as a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, with $\mathcal{V}=\{v_{1},v_{2},\cdots,v_{|\mathcal{V}|}\}$ being the node set and $\mathcal{E}$ being the edge set. Each node $v_{i}\in\mathcal{V}$ represents an agent, which can be further interpreted as follows:

$$ $v_{i}=\{\texttt{Base}_{i},\texttt{Role}_{i},\texttt{State}_{i},\texttt{Plugins}_{i}\},\;\;\texttt{Plugins}_{i}=\{\texttt{F}_{j},\texttt{C}_{j}\}_{j=1}^{P},\vspace{-0.2em}$ (1) $$

where an agent $v_{i}$ consists of: (1) $\texttt{Base}_{i}$, the language model instance used by $v_{i}$;
(2) $\texttt{Role}_{i}$, the pre-defined role or responsibility of the agent;
(3) $\texttt{State}_{i}$, the state of the agent, encapsulating the accumulated knowledge and experience from previous interactions; (4) $\texttt{Plugins}_{i}$, a set of $P$ external plugins available to agent $v_{i}$, where each plugin is defined by its functionalities $\texttt{F}_{j}$ (e.g., web search, python compiler) and configurations $\texttt{C}_{j}$.

For the edges, we divide them into two subsets: intra-dialogue (spatial) edges $\mathcal{E}^{\mathcal{S}}\subseteq\mathcal{V}^{(t)}\times\mathcal{V}^{(t)}$ and inter-dialogue (temporal) edges $\mathcal{E}^{\mathcal{T}}\subseteq\mathcal{V}^{(t-1)}\times\mathcal{V}^{(t)}$. For each spatial edge $e^{\mathcal{S}}_{ij}=(\mathbf{M}_{ij},\mathbf{O}_{ij})$, it represents the information flow from agent $v_{i}$ to agent $v_{j}$ within the same utterance, composed of the message content $\mathbf{M}_{ij}$, as well as the associated operation $\mathbf{O}_{ij}$ (e.g., task assignments, requests). For each temporal edge $e^{\mathcal{T}}_{ij}$, it denotes the message passing between two utterance rounds, i.e., whether the output from agent $v_{i}$ in the $(t-1)$-th round should be passed on to agent $v_{j}$ in the $t$-th round. Further, we define the temporal/spatial (in-)neighbors for each agent as follows:

$$ $\mathcal{N}^{\mathcal{T}}(v_{i})=\{v_{j}\;|\;(j,i)\in\mathcal{E}^{\mathcal{T}}\},\;\mathcal{N}^{\mathcal{S}}(v_{i})=\{v_{j}\;|\;(j,i)\in\mathcal{E}^{\mathcal{S}}\}.\vspace{-0.5em}$ (2) $$

##### Multi-agent Communication

We provide a graph-based description of the reasoning process in task-oriented multi-agent systems. Given a query/task $q$, it is sequentially fed to each agent, which produces its output.
To maintain an orderly sequence of agent interactions, we utilize topological ordering (Bondy et al., ) to ensure that each node is processed only after all its dependencies have been addressed. This necessitates that the spatial communication graph $\mathcal{G}^{\mathcal{S}}=(\mathcal{V},\mathcal{E}^{\mathcal{S}})$ be structured as a directed acyclic graph (DAG).
Formally, for $\mathcal{G}^{\mathcal{S}}$, the following condition holds:

$$ $\forall(v_{i},v_{j}),\;\mathbb{I}(v_{i})<\mathbb{I}(e_{ij})<\mathbb{I}(v_{j}),$ (3) $$

where $\mathbb{I}(x)$ denotes the execution order of $x$. For each agent $v^{(t)}_{i}$ at round $t$, it produces its rationale or answers, uniformly denoted as $\mathbf{M}_{i}$, as follows:

$$ $\mathbf{M}^{(t)}_{i}\sim\mathcal{P}_{\theta}\Biggl{(}\mathbf{M}_{i}\;|\;q,\;\texttt{Role}^{(t)}_{i},\;\texttt{State}^{(t)}_{i},\overbrace{\cup_{\scriptscriptstyle v_{j}\in\mathcal{N}^{\mathcal{T}}(v_{i})}\!\!\!\!\!\mathbf{M}_{j}}^{{\text{temporal}}},\overbrace{\cup_{\scriptscriptstyle v_{j}\in\mathcal{N}^{\mathcal{S}}(v_{i})}\!\!\!\!\mathbf{M}_{ji}}^{{\text{spatial}}}\Biggl{)},\vspace{-0.8em}$ (4) $$

where agent $v_{i}$ responds based on the query $q$, its current role and state, temporal and spatial messages, and certain prompting instruction $\mathcal{P}_{\theta}$. Typically, after $K$ rounds of dialogue, a summarizer agent or an answer aggregation mechanism (e.g., voting) is employed to produce the final solution $a^{(K)}$ for the given query $q$. We conclude the general pipeline in [Algorithm 1](#algorithm1).

Figure: Algorithm 1 Execution pipeline of LLM-MA systems from spatial-temporal graph perspective

##### Problem Formulation

Figure: Figure 3: The performance of mesh graph and LLM-Debate structure under different random pruning ratios on MMLU.
Refer to caption: /html/2410.02506/assets/x2.png

In this section,
we explore and define the communication redundancy issue within existing multi-agent communication pipelines. Specifically, we examine two representative communication topologies: (1) for spatial communication, the fully-connected mesh graph from MacNet (Qian et al., ), which exemplifies a densely structured intra-utterance communication, and (2) for temporal communication, the LLM-Debate (Du et al., ), where at the start of each dialogue round, an agent receives all responses from the previous round as input. Using four gpt-3.5-turbo as agents, we assess system performance on MMLU after randomly pruning a certain proportion of connections. As illustrated in [Figure 3](#S2.F3), when randomly removing $10\%\sim 30\%$ of the communication connectivity, the performance actually gains up to $2.83\%$ improvement. This suggests that, in both spatial and temporal information flow, a substantial portion of messages does not contribute to the task-solving process, which we formally define as follows:

###### Definition 1 (Communication Redundancy) .

For any LLM-based multi-agent communication graph $\mathcal{G}=(\mathcal{V},\mathcal{E}^{\mathcal{S}}\cup\mathcal{E}^{\mathcal{T}})$, the following condition holds:

$$ $\exists\;\mathcal{G}^{\text{sub}}=(\mathcal{V},\mathcal{E}^{\prime}\cup\mathcal{E}^{\prime\prime})\subseteq\mathcal{G},\;\operatorname{where}\;\mathcal{E}^{\prime}\subseteq\mathcal{E}^{\mathcal{S}},\;\mathcal{E}^{\prime\prime}\subseteq\mathcal{E}^{\mathcal{T}},\;\operatorname{s.t.}\;\phi(\mathcal{G}^{\text{sub}})\geq\phi(\mathcal{G}),$ (5) $$

where $\phi(\cdot)$ represents a utility function that measures the solution quality achieved by the system. The redundant components in the communication topology, denoted as $(\mathcal{E}^{st}\setminus\mathcal{E}^{\prime})\cup(\mathcal{E}^{tp}\setminus\mathcal{E}^{\prime\prime})$, are referred to as the communication redundancy in LLM-MA systems.

We further outline the objective of this study as follows:

$$ ${\arg\max}_{\mathcal{E}^{\prime},\mathcal{E}^{\prime\prime}}\mathcal{G}\setminus\mathcal{G}^{\text{sub}},\;\text{s.t.}\;|\phi(\mathcal{G}^{\text{sub}})-\phi(\mathcal{G})|\leq\epsilon,$ (6) $$

where $\epsilon$ represents the allowable threshold for performance variation. [Equation 6](#S2.E6) aims to minimize communication redundancy with performance guarantee.

###### Definition 1 (Communication Redundancy) .

## 3 Methodology

[Figure 4](#S3.F4) illustrates how our method is applied within an LLM-MA system. Specifically, given an input query, AgentPrune first performs spatial pruning by eliminating redundant spatial messages within a dialogue round, followed by temporal pruning to discard unnecessary dialogue history.
In the following sections, we will first explain how AgentPrune facilitates efficient multi-round communication based on an optimizable spatial-temporal communication graph ($\vartriangleright$ [Sections 3.1](#S3.SS1) and [3.2](#S3.SS2)), leverages one-shot pruning to derive a sparse interaction topology ($\vartriangleright$ [Section 3.3](#S3.SS3)), and finally, detail the optimization paradigm for the entire framework ($\vartriangleright$ [Section 3.4](#S3.SS4)).

Figure: Figure 4: The overview of our proposed AgentPrune.
Refer to caption: /html/2410.02506/assets/x3.png

### 3.1 Spatial-temporal Graph Communication

Given an arbitrary LLM-MA system and its corresponding spatial-temporal communication graph $\mathcal{G}$, the task of AgentPrune is to discover its sparse yet equally high-performing counterpart $\mathcal{G}^{\text{sub}}$. The objective is essentially a graph sparsification problem (Spielman & Srivastava, ; Chen et al., ), whose goal is to identify the essential graph connections and discard the less critical ones.
To achieve this, following classical practices in graph sparsification (Chen et al., ; Wang et al., ; Zhang et al., ), we relax the original binary communication graph $\mathcal{G}$ by transforming its edge elements from binary values to continuous variables, denoted as $\tilde{\mathcal{G}}$. We have:

$$ $\mathbf{A}({\mathcal{G}})=\{\mathbf{A}^{\mathcal{S}},\mathbf{A}^{\mathcal{T}}\},\;\mathbf{A}(\tilde{\mathcal{G}})=\mathbf{A}(\{\tilde{\mathcal{G}}^{\mathcal{S}},\tilde{\mathcal{G}}^{\mathcal{T}}\})=\{\mathbf{A}^{\mathcal{S}}\odot\mathbf{S}^{\mathcal{S}},\mathbf{A}^{\mathcal{T}}\odot\mathbf{S}^{\mathcal{T}}\},$ (7) $$

where $\mathbf{A}(\mathcal{G})$ obtains the adjacency matrix of input graph $\mathcal{G}$, and $\mathbf{A}^{\mathcal{S}},\mathbf{A}^{\mathcal{T}}\in\{0,1\}^{|\mathcal{V}|\times|\mathcal{V}|}$ represent the spatial and temporal adjacency matrices, respectively. Specifically, $\mathbf{A}^{x}[i,j]=1$ indicates that $e_{ij}\in\mathcal{E}^{x}$, and 0 0 otherwise. It is important to note that both $\mathbf{A}^{\mathcal{S}}$ and $\mathbf{A}^{\mathcal{T}}$ are predefined by the LLM-MA system. $\mathbf{S}^{\mathcal{S}},\mathbf{S}^{\mathcal{T}}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}$ are differentiable graph masks. As mentioned in [Section 2](#S2.SS0.SSS0.Px2), we require the interaction topology to be a DAG to ensure that agent input/output (I/O) can be processed sequentially. Therefore, we leverage a DAGSampling function to transform the original $\tilde{\mathcal{G}}^{\mathcal{S}}$ into a DAG: $\hat{\mathcal{G}}^{\mathcal{S}}\leftarrow\texttt{DAGSampling}(\tilde{\mathcal{G}}^{\mathcal{S}})$, whose procedure is described in [Algorithm 2](#algorithm2).

### 3.2 Optimizing Spatial-temporal Connectivity

With $\hat{\mathcal{G}}^{\mathcal{S}}$ and $\tilde{\mathcal{G}}^{\mathcal{T}}$ in hand, we aim to optimize them toward both high-performance and token efficiency. To this end, we introduce two optimization objectives for $\hat{\mathcal{G}}^{\mathcal{S}}$ and $\tilde{\mathcal{G}}^{\mathcal{T}}$: ❶ distribution approximation, ensuring accurate estimation of their underlying probability distributions, and ❷ low-rank sparsity, which promotes a more efficient and sparse structure (Li et al., ). The first objective ensures that the magnitudes of the graph masks correctly reflect the importance of different communication channels, facilitating subsequent redundancy pruning, and the second ensures that the learned connectivity remains sparse and robust. Formally, we define the following objective:

$$ $\underset{\mathbf{S}^{\mathcal{S}},\mathbf{S}^{\mathcal{T}}\in\mathbb{S}}{\arg\max}\;\overbrace{\mathbb{E}_{\hat{\mathcal{G}}^{\mathcal{S}},\mathcal{G}^{\mathcal{T}}\sim\mathbb{G}}\left[\phi\left(\{\hat{\mathcal{G}}^{\mathcal{S}},\tilde{\mathcal{G}}^{\mathcal{T}}\}\right)\right]}^{\text{distribution approximation}}-\!\!\overbrace{\sum_{\scriptscriptstyle\mathcal{X}\in\{\mathcal{S},\mathcal{T}\}}\!\!\operatorname{rank}(\mathbf{S}^{\mathcal{X}})}^{\text{low-rank sparsity}},\;\operatorname{s.t.}\!\!\!\!\sum_{\scriptscriptstyle\mathcal{X}\in\{\mathcal{S},\mathcal{T}\}}\!\!\!||\mathbf{A}^{\mathcal{X}}-\mathbf{S}^{\mathcal{X}}||_{F}\leq\delta,$ (8) $$

where $\mathbb{S}$ and $\mathbb{G}$ represent the viable parameter space, $\phi(\cdot)$ serves as the utility evaluator for the input multi-agent framework, $\operatorname{rank}(\cdot)$ calculates the rank of matrix, and $\delta$ is the noise level. Next, we will provide a detailed explanation of the implementation of these two optimization objectives.

##### Distribution Approximation

The first term in [Equation 8](#S3.E8) encourages $\{\mathbf{S}^{\mathcal{S}},\mathbf{S}^{\mathcal{T}}\}$ towards the maximization of the system’s utility. However, since $\phi(\cdot)$ often depends on external APIs (Li et al., ) or compilers (Chen et al., ) for evaluation, it is generally non-differentiable. Therefore, we employ policy gradient (Williams, ) to make [Equation 8](#S3.E8) tractable:

$$ $\displaystyle\nabla_{\mathbf{S}}\;\mathbb{E}_{\hat{\mathcal{G}}^{\mathcal{S}},\tilde{\mathcal{G}}^{\mathcal{T}}\sim\mathbb{G}}\left[\phi\left(\{\hat{\mathcal{G}}^{\mathcal{S}},\tilde{\mathcal{G}}^{\mathcal{T}}\}\right)\right]\approx\frac{1}{M}\sum_{k=1}^{M}\phi\left(\{\hat{\mathcal{G}}^{\mathcal{S}}_{k},\tilde{\mathcal{G}}^{\mathcal{T}}_{k}\}\right)\nabla_{\mathbf{S}}\log\left(p_{\mathbf{S}}(\{\hat{\mathcal{G}}^{\mathcal{S}}_{k},\tilde{\mathcal{G}}^{\mathcal{T}}_{k}\})\right),$ (9) $\displaystyle p_{\mathbf{S}}\left(\{\hat{\mathcal{G}}^{\mathcal{S}}_{k},\tilde{\mathcal{G}}^{\mathcal{T}}_{k}\}\right)=\left(\prod\mathbbm{1}_{e_{ij}\in\mathcal{E}^{\mathcal{S}}}\mathbf{S}^{\mathcal{S}}[i,j]\right)\cdot\left(\prod\mathbbm{1}_{e_{ij}\in\mathcal{E}^{\mathcal{T}}}\mathbf{S}^{\mathcal{T}}[i,j]\right)$ (10) $$

where $\mathbf{S}=\{\mathbf{S}^{\mathcal{S}},\mathbf{S}^{\mathcal{T}}\}$, $\{\hat{\mathcal{G}}^{\mathcal{S}},\tilde{\mathcal{G}}^{\mathcal{T}}\}_{k=1}^{M}$ are independently sampled from $\{\hat{\mathcal{G}}^{\mathcal{S}},\tilde{\mathcal{G}}^{\mathcal{T}}\}$, $p_{\mathbf{S}}(\{\hat{\mathcal{G}}^{\mathcal{S}}_{k},\tilde{\mathcal{G}}^{\mathcal{T}}_{k}\})$ calculates the probability of the sampled structure, and $\mathbbm{1}(\cdot)$ is an indicator function.

##### Low-rank Sparsity

The second term in [Equation 8](#S3.E8) promotes the graph masks $\{\mathbf{S}^{\mathcal{S}},\mathbf{S}^{\mathcal{T}}\}$ to be low-rank, which not only filters out informative agent communications but also aids in removing redundant, noisy, and even malicious messages, which has been demonstrated in recent studies, showing that low-rank graphs are more robust to network attacks (Entezari et al., ; Ennadir et al., ). We will empirically validate AgentPrune’s ability to enhance multi-agent robustness in [Section 4.4](#S4.SS4). However, directly optimizing the rank minimization is NP-hard, so we replace the rank function with the nuclear norm as an alternative, reformulating this term as follows:

$$ $\underset{\mathbf{S}^{\mathcal{S}},\mathbf{S}^{\mathcal{T}}\in\mathbb{S}}{\arg\min}{\textstyle\sum}_{\scriptscriptstyle\mathcal{X}\in\{\mathcal{S},\mathcal{T}\}}||\mathbf{S}^{\mathcal{X}}||_{*},\;\operatorname{s.t.}||\mathbf{A}^{\mathcal{X}}-\mathbf{S}^{\mathcal{X}}||_{F}\leq\delta,$ (11) $$

where $||\mathbf{S}||_{*}=\sum_{i}\sigma_{i}$, and $\sigma_{i}$ represents the $i$-th singular value of $\mathbf{S}$.
Guided by [Equation 8](#S3.E8), we iteratively optimize the spatial-temporal connectivity in conjunction with the multi-agent conversation over $K^{\prime}$ rounds, where $K^{\prime}\ll K$.

### 3.3 One-shot Pruning

We dynamically optimize $\{\mathbf{S}^{\mathcal{S}},\mathbf{S}^{\mathcal{T}}\}$ for only $K^{\prime}$ iterations, rather than the full $K$ iterations, because prior work on Early-bird (EB) and Graph EB has demonstrated that limited training can also construct high-quality benchmarks reflecting the topology distribution (Achille et al., ; You et al., ; Zhang et al., ), which also aligns with AgentPrune’s token-saving initiation. To eliminate redundancy in the current communication structure, we perform one-shot magnitude pruning on the optimized graph masks $\mathbf{S}$ (either $\mathbf{S}^{\mathcal{S}}$ or $\mathbf{S}^{\mathcal{T}}$):

$$ $\mathbf{B}=\mathbbm{1}\biggl{(}\mathbf{A}\neq 0\wedge\operatorname{TopK}\Bigl{(}\mathbf{S},|\mathbf{A}|\times\left(1-p\%\right)\Bigl{)}\biggl{)},$ (12) $$

where $\operatorname{TopK}(S,x\%)$ return the largest $x\%$ elements in matrix $S$, and $p\%$ is the pruning ratio. By applying the binary masks to the original topology, we obtain sparse, compact, and communication-minimizing connectivity $\mathcal{G}^{\text{sub}}$, where $\mathbf{A}(\mathcal{G}^{\text{sub}})=\{\mathbf{A}^{\mathcal{S}}\odot\mathbf{B}^{\mathcal{S}},\mathbf{A}^{\mathcal{T}}\odot\mathbf{B}^{\mathcal{T}}\}.$
In the subsequent $(K-K^{\prime})$ rounds, the entire framework’s message passing pipeline is strictly constrained by $\mathcal{G}^{\text{sub}}$, and agents are continuously optimized to refine the solution for query $q$.

### 3.4 Application and Analysis

##### Algorithm Pipeline

As a plug-and-play module, AgentPrune can be harmoniously embedded in mainstream multi-agent frameworks to facilitate token-efficient communication, provided that the number of agents exceeds three and the communication structure is moderately organized (e.g., chain or direct-output structures are too simple to be applicable). When combined with AgentPrune, multiple agents first undergo $K^{\prime}$ rounds of interactions alongside trainable graph masks, which are then one-shot pruned to yield the sparse $\mathcal{G}^{\text{sub}}$, leveraged for the subsequent $(K-K^{\prime})$ rounds of optimization. We summarize all the notations used in [Appendix B](#A2) and the comprehensive algorithmic workflow in [Appendix C](#A3).

##### Multi-Query Training

For complex tasks like repository-level code generation (Qian et al., ; Liu et al., ), multi-turn dialogues are often inevitable. However, for simpler tasks that involve a large number of queries, such as multiple choice answering (Agashe et al., ; Qian et al., ), typically only one or two dialogue rounds are needed, according to previous practices (Yin et al., ). Under such circumstances, optimizing the connectivity for each query independently can be unnecessarily costly. Therefore, we give a multi-query training paradigm for AgentPrune, which optimizes and prunes the spatial-temporal topology using merely $Q^{\prime}(Q^{\prime}\ll Q)$ queries, given a dataset composed of $Q$ queries.
See details in [Appendix D](#A4).

##### Cost Analysis

In this section, we quantify the difference in token consumption between AgentPrune and the vanilla pipeline. Given a communication graph $\mathcal{G}$ and $K$ dialogue rounds, assuming that the average token count per spatial/temporal/query message is $c_{\mathcal{S}},c_{\mathcal{T}},c_{q}$, respectively, then the total token consumption of the vanilla system is $C_{\mathcal{G}}=K\left[c_{\mathcal{S}}|\mathcal{E}^{\mathcal{S}}|+c_{\mathcal{T}}|\mathcal{E}^{\mathcal{T}}|+C_{q}|\mathcal{V}|\right]$. The token consumption after applying AgentPrune is divided into two stages. The first stage involves $MK^{\prime}\left[c_{\mathcal{S}}|\mathcal{E}^{\mathcal{S}}|+c_{\mathcal{T}}|\mathcal{E}^{\mathcal{T}}|+C_{q}|\mathcal{V}|\right]$, while in the second stage, after the topology is fixed, the consumption becomes $(K-K^{\prime})\left[(1-p\%)\cdot\left(c_{\mathcal{S}}|\mathcal{E}^{\mathcal{S}}|+c_{\mathcal{T}}|\mathcal{E}^{\mathcal{T}}|\right)+C_{q}|\mathcal{V}|\right]$. Therefore, the total token savings $\Delta$ achieved by AgentPrune can be expressed as:

$$ $\Delta=\Bigl{(}\left(1+p\%\right)K-\left(M+p\%\right)K^{\prime}\Bigl{)}\Bigl{(}c_{\mathcal{S}}|\mathcal{E}^{\mathcal{S}}|+c_{\mathcal{T}}|\mathcal{E}^{\mathcal{T}}|\Bigl{)}+(1-M)K^{\prime}C_{q}|\mathcal{V}|.\vspace{-0.5em}$ (13) $$

We present the cost analysis of AgentPrune in multi-query training in [Appendix E](#A5). We will empirically evaluate the substantial token savings gained by AgentPrune in [Section 4.2](#S4.SS2).

## 4 Experiments

In this section, we conduct extensive experiments to answer the following research questions:
(RQ1) How does AgentPrune perform with respect to task completion and token efficiency?
(RQ2) Can AgentPrune reduce the economical cost of existing multi-agent systems without compromising performance?
(RQ3) Is AgentPrune effective in defending against adversarial attacks on agents?
(RQ4) How sensitive is AgentPrune to its key components or parameters?

**Table 1: Performance comparison with three types of baselines, including single-agent execution, spatial communication and temporal communication. The best results are highlighted in bold, and the runner-ups are underlined. All methods, except for the single-agent category, utilize five gpt-4-based agents.**
| Method | Spa. | Tem. | MMLU | GSM8K | MultiArith | SVAMP | AQuA | HumanEval | Avg. |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Vanilla | ✗ | ✗ | 82.14 | 85.40 | 93.15 | 87.18 | 70.34 | 71.68 | 81.65 |
| CoT | ✗ | ✗ | 82.65↑0.51 | 87.17↑1.77 | 94.79↑1.64 | 88.32↑1.14 | 73.91↑3.57 | 75.52↑3.84 | 83.73 |
| ComplexCoT | ✗ | ✗ | 83.78↑1.64 | 87.62↑2.22 | 95.86↑2.71 | 90.17↑2.99 | 77.58↑7.24 | 74.94↑3.26 | 84.99 |
| SC (CoT) | ✗ | ✗ | 82.66↑0.52 | 87.93↑2.53 | 96.88↑3.73 | 88.69↑1.51 | 75.08↑4.74 | 77.30↑5.62 | 84.67 |
| SC (ComplexCoT) | ✗ | ✗ | 83.65↑1.51 | 86.14↓0.74 | 96.94↑3.79 | 89.72↑2.54 | 77.69↑7.35 | 77.94↑6.26 | 85.35 |
| Chain | ✓ | ✗ | 82.35↑0.21 | 85.57↑0.17 | 94.38↑1.23 | 83.41↓3.77 | 70.94↑0.60 | 80.88↑9.20 | 92.92 |
| Star | ✓ | ✗ | 80.79↓1.35 | 85.55↑0.15 | 93.79↓0.64 | 88.09↑0.91 | 68.57↓1.77 | 75.65↓3.97 | 82.07 |
| Tree | ✓ | ✗ | 81.89↓0.25 | 84.56↓0.84 | 94.60↑1.45 | 89.25↑2.07 | 72.84↑2.50 | 77.38↑5.70 | 83.42 |
| Complete Graph | ✓ | ✗ | 83.15↑1.01 | 86.49↑1.09 | 97.20↑4.05 | 89.48↑2.30 | 79.21↑8.87 | 83.75↑12.07 | 86.55 |
| Layered Graph | ✓ | ✗ | 78.41↓3.73 | 85.34↓0.06 | 95.04↑1.89 | 88.61↑1.43 | 73.18↑2.84 | 80.38↑8.70 | 83.49 |
| Random Graph | ✓ | ✗ | 83.76↑1.62 | 86.14↑0.74 | 95.46↑2.31 | 85.41↓1.77 | 74.07↑3.73 | 82.66↑10.98 | 84.58 |
| LLM-Blender | ✓ | ✗ | 81.22↓0.92 | 89.17↑3.77 | 94.27↑1.12 | 88.77↑1.59 | 77.05↑6.71 | - | 86.10 |
| GPTSwarm | ✓ | ✗ | 83.98↑1.84 | 89.74↑4.34 | 97.84↑4.69 | 86.42↓0.76 | 78.16↑7.82 | 88.49↑16.81 | 86.77 |
| LLM-Debate | ✗ | ✓ | 83.69↑1.55 | 90.23↑4.83 | 96.27↑3.12 | 90.56↑3.38 | 77.52↑7.18 | 83.79↑12.11 | 87.01 |
| PHP | ✗ | ✓ | 83.45↑1.31 | 92.45↑7.05 | 96.41↑3.26 | 90.62↑3.44 | 76.25↑5.91 | 82.96↑11.28 | 87.02 |
| DyLAN | ✗ | ✓ | 80.16↓1.98 | 88.16↑2.76 | 94.27↑1.12 | 87.40↑0.22 | 74.16↑3.82 | 89.70↑18.02 | 84.48 |
| AgentPrune-C | ✓ | ✓ | 84.72↑2.58 | 95.62↑10.22 | 97.25↑4.10 | 91.85↑4.67 | 79.47↑9.13 | 89.38↑15.70 | 89.72 |
| AgentPrune-L | ✓ | ✓ | 83.50↑1.36 | 93.78↑8.38 | 96.39↑3.24 | 89.58↑2.40 | 78.44↑8.10 | 88.61↑16.93 | 88.38 |
| AgentPrune-R | ✓ | ✓ | 83.94↑1.80 | 95.83↑10.43 | 96.30↑3.15 | 91.68↑4.50 | 78.60↑8.26 | 90.30↑18.62 | 89.44 |
|  |  |  |  |  |  |  |  |  |  |

### 4.1 Experimental Setup

##### Tasks and Benchmarks

In our experiments, we test the performance of AgentPrune on three types of reasoning tasks and the corresponding logically challenging benchmarks: (1) General Reasoning: We opt for MMLU (Hendrycks et al., ) dataset; (2) Mathematical Reasoning: We select GSM8K (Cobbe et al., ), MultiArith (Roy & Roth, ), SVAMP (Patel et al., ) and AQuA (Ling et al., ) to verify the mathematical reasoning capacity; (3) Code Generation: We use the HumanEval (Chen et al., ) to test the function-level code generation ability.

##### Baselines

We compare AgentPrune with three series of multi-agent communication paradigms, namely: (1) Single agent execution methods, including Chain-of-Thought prompting (CoT; Wei et al. ()), (2) Complexity-based prompting (ComplexCoT; Fu et al. ()), and (3) Self-Consistency (SC; Wang et al. ()); (2) Spatial communication methods, including chain, tree, star, complete graph, layered graph and random graph(^1^11Detailed explanations of these topologies are placed in [Appendix F](#A6).) from MacNet (Qian et al., ), LLM-Blender (Jiang et al., ), and GPTSwarm (Zhuge et al., ); (3) Temporal communication methods, including PHP (Zheng et al., ), LLM-Debate (Du et al., ), DyLAN (Liu et al., ). Detailed introductions and implementations of the baselines are in [Section G.1](#A7.SS1).

##### Implementation Details

We accessed the GPT models via the OpenAI API, and mainly tested gpt-3.5-turbo-0301 (gpt-3.5) and gpt-4-1106-preview (gpt-4) with different communication topologies. We set the temperature at 1 during the generation. We set the dialogue round $K=2$ for mathematical and general reasoning tasks, and $K=4$ for code generation tasks. For multi-query settings, we vary $Q^{\prime}\in\{5,10\}$. We generate different agent profiles using gpt-4 for individual agents. More experimental details are in [Appendix G](#A7).

### 4.2 Performance & Cost Comparison (RQ1)

Figure: Figure 5: Visualization of performance and prompt token consumption. This scatter plot illustrates the performance metrics and prompt token consumption of different multi-agent communication topologies across MMLU, HumanEval, and GSM8K. The diameter of each point is proportional to its y-axis value.
Refer to caption: /html/2410.02506/assets/x4.png

**Table 2: Performance on the HumanEval Benckmark with more advanced baselines.**
| Method | Pass@1 | $\Delta$ |
| --- | --- | --- |
| Vanilla | 71.68 | - |
| AutoGen [] | 85.41 | $\uparrow$11.97 |
| Reflexion [] | 91.40 | $\uparrow$19.72 |
| CodeT+Parsel [] | 85.10 | $\uparrow$13.42 |
| MetaGPT [] | 85.90 | $\uparrow$14.22 |
| ANPL [] | 86.60 | $\uparrow$14.92 |
| AgentPrune-C | 89.38 | $\uparrow$17.70 |
| AgentPrune-R | 90.30 | $\uparrow$18.62 |
|  |  |  |

To evaluate whether AgentPrune achieves a dual benefit of token savings and task completion, we integrate it with three predefined spatial communication topologies: the complete graph, layered graph, and random graph, denoted as AgentPrune-C, AgentPrune-L, and AgentPrune-R, respectively.
For the temporal communication topology, we consistently employ the fully connected LLM-Debate-style structure. [Tables 1](#S4.T1) and [2](#S4.T2) presents a performance comparison of various communication paradigms within five gpt-4-based multi-agent systems, and [Figures 5](#S4.F5), [17](#A8.F17), [18](#A8.F18) and [19](#A8.F19) visualizes the performance and token cost of different methods. Our observations (Obs.) are as follows:
Obs.❶ Not all multi-agent topologies consistently deliver collective intelligence. As illustrated in [Table 1](#S4.T1), certain topologies, such as star/tree structures, fail to consistently improve performance for multi-agent systems, even resulting in performance drops of $0.17\%\sim 3.97\%$. In contrast, single-agent prompting methods like CoT or ComplexCoT demonstrate much more stable and significant improvements.
Obs.❷ The high performance of existing multi-agent systems comes at a substantial economical cost.
From [Table 1](#S4.T1), we observe that the top-performing baselines, GPTSwarm and DyLAN, achieve pass@1 improvements of $16.81\%$ and $18.02\%$ on HumanEval, respectively; however, this is accompanied by extremely high economic costs. As shown in [Figure 5](#S4.F5), the prompt token consumption of GPTSwarm and DyLAN is
$2.4\sim 5.3\times$ that of the random graph structure. Obs.❸ AgentPrune achieves a double win in economic savings and utility. Among the three variants, AgentPrune-R delivers consistently impressive performance, achieving $90.3\%$ on HumanEval and $95.8\%$ on GSM8K. Importantly, this performance does not come at a high token cost: on both HumanEval and GSM8K, the token consumption of AgentPrune is less than $40\%$ that of DyLAN. Overall, AgentPrune excels in both task completion and token efficiency.

### 4.3 Plug-in into Existing Frameworks (RQ2)

As a plug-in, AgentPrune can be seamlessly combined with mainstream multi-agent pipelines, effectively reducing the economic costs associated with LLM token throughput while maintaining the original performance levels. To validate our argument, we combined AgentPrune with two representative LLM-MA frameworks, AutoGen and GPTSwarm.
With the results presented in [Table 3](#S4.T3) and [Table 5](#A8.T5), we offer the following two key observations: Obs.❹ Scaling multi-agent collaboration is costly. Comparing [Table 3](#S4.T3) and [Table 5](#A8.T5), we observe that for the GPTSwarm on the GSM8K dataset, optimizing a three-agent system incurs a cost of $\$97.23$, while the expense for a five-agent system skyrockets to $\$234.76$, with the total token count reaching $1.7e+7$. AutoGen, on the other hand, has relatively lower costs because it does not involve the iterative optimization of the communication topology as extensively as GPTSwarm (Zhuge et al., ). Nevertheless, it still requires $73.21 on the GSM8K benchmark, which comprises up to 8.5K data entries.
Obs.❺ AgentPrune is an economically friendly assistant. When applied to HumanEval+AutoGen, AgentPrune achieves a $36\%$ reduction in prompt tokens and saves $\$1.486$. In tasks with larger datasets, the economic savings become even more pronounced: on GSM8K+GPTSwarm, AgentPrune reduces $60.6\%$ of the prompt token consumptions and saves a cost of up to $\$177.58$, with even a performance increase of $0.84\%$. Overall, AgentPrune serves as a token-efficient plug-in, effectively fostering the development of larger and more cost-effective multi-agent systems.

**Table 3: Performance and cost comparison before/after combining AgentPrune. We evaluated the performance and economical cost of AgentPrune in conjunction with two classic multi-agent systems, under a five gpt-4-based setting. “# Prompt tokens” refers to the total number of tokens input, while “# Completion tokens” accounts for the total number of tokens output by the API.**
| Dataset | Method | Performance | # Prompt Tokens | # Completion Tokens | Cost (USD) |
| --- | --- | --- | --- | --- | --- |
| MMLU | AutoGen | $82.13$ | $486,034$ | $89,224$ | $\$7.537$ |
| +AgentPrune | $82.78({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 0.65})$ | $349,583(\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}71.9\%)$ | $86,582$ | $\$6.093$ |  |
|  | AutoGen | $85.41$ | $492,273$ | $130,196$ | $\$8.828$ |
| HumanEval | +AgentPrune | $86.65({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 1.24})$ | $315,105({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}64.0\%})$ | $139,714$ | $\$7.342$ |
|  | AutoGen | $90.06$ | $4,327,740$ | $998,042$ | $\$73.21$ |
| GSM8K | +AgentPrune | $92.85({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 2.79})$ | $3,791,251({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}59.9\%})$ | $1,156,884$ | $\$59.60$ |
|  | GPTSwarm | $83.98$ | $3,055,230$ | $569,124$ | $\$47.60$ |
| MMLU | +AgentPrune | $83.05({\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color@cmyk@fill{0.85}{0}{0.33}{0}\downarrow 0.93})$ | $990,312({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}32.4\%})$ | $439,551$ | $\$23.05$ |
|  | GPTSwarm | $84.49$ | $2,736,136$ | $1,004,616$ | $\$57.49$ |
| HumanEval | +AgentPrune | $84.96({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 0.47})$ | $745,617({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}27.2\%})$ | $745,926$ | $\$29.80$ |
|  | GPTSwarm | $89.74$ | $14,005,945$ | $3,156,916$ | $\$234.76$ |
| GSM8K | +AgentPrune | $90.58({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 0.84})$ | $3,526,035({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}39.4\%})$ | $730,552$ | $\$57.17$ |
|  |  |  |  |  |  |

Figure: Figure 6: Performance under adversarial attack. We compare the accuracy (%) of various multi-agent frameworks before and after prompt attacks on MMLU. “w/ AP” indicates the integration with AgentPrune.
Refer to caption: /html/2410.02506/assets/x5.png

### 4.4 Robustness Verification (RQ3)

AgentPrune can not only eliminate unnecessary communications but also remove malicious messages. To validate this, we design two types of adversarial attacks for the multi-agent frameworks: the agent prompt attack and agent replacement attack. The former attacks the role prompts of the agents, while the latter attacks the LLM’s generation process, with detailed implementation elaborated in [Section G.3](#A7.SS3). We observe that: Obs.❻ Existing LLM-MA frameworks often lack adversarial robustness. Despite variations in performance, most frameworks experience significant declines when subjected to both types of attacks. As shown in [Figures 6](#S4.F6) and [20](#A8.F20), the chain-like structure suffers a performance drop of up to $20.8\%$ due to its oversimplistic topology. AutoGen and DyLAN similarly experience accuracy declines ranging from $3.2\%$ to $6.2\%$. Obs.❼ AgentPrune significantly enhances multi-agent robustness. [Figure 6](#S4.F6) demonstrates that combining AgentPrune with a complete graph not only improves performance ($83.1\%\rightarrow 84.7\%$), but also increases robustness under agent prompt attacks ($78.4\%\rightarrow 83.9\%$). Additionally, AgentPrune successfully boosts the robustness of DyLAN and AutoGen by up to $6.3\%$. The impact of AgentPrune on GPTSwarm is relatively marginal, due to its inherent defenses against adversarial agents. Overall, AgentPrune serves as an easy-to-use enhancer for multi-agent robustness.

### 4.5 Experimental Analysis

##### Ablation Study

We ablate agent profiling and low-rank regularization in AgentPrune, with details presented in [Table 6](#A8.T6) and [Section H.4.1](#A8.SS4.SSS1). Our key finding is that (1) the utility of agent profiling varies across different datasets, demonstrating a more pronounced effect on general reasoning and code generation tasks, while being relatively less significant in math reasoning; (2) low-rank sparsity consistently facilitates the optimization of the communication topology.

##### Sensitivity Analysis and Case Study

We present the parameter sensitivity analysis concerning two hyperparameters in [Section H.4.2](#A8.SS4.SSS2), and provide extensive visualizations on AgentPrune’s pruning process and optimized communication structure in [Appendix I](#A9).

## 5 Related Work

##### LLM-agent Collaboration

Collaboration between multiple LLM-based agents has emerged as a promising approach to enhance the capabilities of individual LLMs (Du et al., ; Liang et al., ; Wang et al., ). As stated in [Section 1](#S1), current multi-agent communication methods can be categorized into two types: ❶ Intra-dialogue (spatial) communication focuses on how different agents exchange messages within a single dialogue round. Common structures include (1) Direct output, where functioning agents do not communicate with each other, adopted by systems like LATM (Zhang et al., ), LLM-Debate (Du et al., ); (2) Chain, employed by ChatDev (Qian et al., ), MetaGPT (Hong et al., ) and L2MAC (Holt et al., ); (3) Tree, where an administrative agent (usually refered to as commander, manager, etc.) controls subordinate agents, adopted by AutoGen (Wu et al., ), SecurityBot (Yan et al., ), and MiniGrid (Zhou et al., ); and (4) Graph, employed by LLM-Blender (Jiang et al., ), ChatEval (Chan et al., ), MacNet (Qian et al., ) and GPTSwarm (Zhuge et al., ); ❷ Inter-dialogue (temporal) communication focuses on how information is passed between different rounds of utterances. Common topologies include (1) Full transmission, where every agent receives the utterances of all agents from the previous round, as used by LLM-Debate (Du et al., ); (2) Partial transmission, where some responses are filtered through scoring or rating mechanisms, adopted by PHP (Zheng et al., ) and DyLAN (Liu et al., ); (3) Summarization, where dialogue history is compressed and summarized for the next round of communication, as seen in Reflexion (Shinn et al., ), ICL-AIF (Fu et al., ), AgentVerse (Chen et al., ), CoMM (Chen et al., ), Corex (Sun et al., ), and MAD (Liang et al., ).

##### Agents as Graphs

Learning to facilitate communication via learning graph connectivity is a long-standing and viable approach to enhance multi-agent cooperation (Pesce & Montana, ; Hu et al., ). In the pre-LLM era, numerous efforts explored optimal communication graph structures for reinforcement learning-based multi-agents with graph diffusion (Pesce & Montana, ), weighted GNN (Liu et al., ), or transformers (Hu et al., ). In the emerging wave of LLM-powered agents, attempts that leverage graphs for modeling agent-agent interaction also exist: ChatEval (Chan et al., ) and AutoGen (Wu et al., ) implicitly adopt graph structures to describe ”simultaneous talk”, and STOP (Zelikman et al., ) and DSPy (Khattab et al., ) optimize both the prompts and the inference structure together. MacNet (Qian et al., ) and GPTSwarm (Zhuge et al., ) model agent communication via directed acyclic graphs (DAG). However, none of these approaches simultaneously optimize both intra- and inter-dialogue communication structures, and they often result in even increased token consumption.

## 6 Conclusion

This paper makes the first attempt towards a high-performance and token-efficient LLM-powered multi-agent system. We propose an economical, simple, and robust multi-agent communication pipeline, termed AgentPrune, which can be harmoniously embedded into mainstream multi-agent frameworks while effectively pruning the communication redundancy that we have identified and defined. AgentPrune achieves performance comparable to, or even superior to, the original systems with significantly smaller token throughput and economic costs. We believe that AgentPrune can facilitate the advancement toward larger-scale collective intelligence.

## Appendix A DAG Sampling Function

Figure: Algorithm 2 Sample DAG from spatial communication graph

## Appendix B Notations

We conclude the commonly used notations in [Table 4](#A2.T4) for reference.

**Table 4: The notations that are commonly used throughout the manuscript.**
| Notation | Definition |
| --- | --- |
| $\mathcal{G}=(\mathcal{V},\mathcal{E})=\{\mathcal{G}^{\mathcal{S}},\mathcal{G}^{\mathcal{T}}\}$ | the spatial-temporal communication graph |
| $\mathcal{V}=\{v_{1},v_{2},\cdots,v_{|\mathcal{V}|}\}$ | the set of nodes (agents) |
| $\mathcal{E}=\mathcal{E}^{\mathcal{S}}\cup\mathcal{E}^{\mathcal{T}}$ | the overall edge set |
| $\mathcal{E}^{\mathcal{S}}\subseteq\mathcal{V}^{(t)}\times\mathcal{V}^{(t)}$ | the spatial edge set |
| $\mathcal{E}^{\mathcal{T}}\subseteq\mathcal{V}^{(t-1)}\times\mathcal{V}^{(t)}$ | the temporal edge set |
| $\texttt{Base}_{i}$ | the LLM base utilized by agent $v_{i}$ |
| $\texttt{Role}_{i}$ | the predefined responsibilities or roles of agent $v_{i}$ |
| $\texttt{State}_{i}$ | the state of agent $v_{i}$ |
| $\texttt{Plugins}_{i}=\{\texttt{F}_{j},\texttt{C}_{j}\}_{j=1}^{P}$ | the plugins available to agent $v_{i}$ |
| $e^{\mathcal{S}}_{ij}=(\mathbf{M}_{ij},\mathbf{O}_{ij})$ | the spatial edge from $v_{i}$ to $v_{j}$ |
| $e^{\mathcal{T}}_{ij}$ | the temporal edge from $v_{i}$ to $v_{j}$ |
| $\mathcal{N}^{\mathcal{T}}(v_{i})=\{v_{j}\;|\;(j,i)\in\mathcal{E}^{\mathcal{T}}\}$ | the temporal (in-)neighbors of $v_{i}$ |
| $\mathcal{N}^{\mathcal{S}}(v_{i})=\{v_{j}\;|\;(j,i)\in\mathcal{E}^{\mathcal{S}}\}$ | the spatial (in-)neighbors of $v_{i}$ |
| $\mathbf{M}^{(t)}_{i}$ | the rationale or answers provided by $v_{i}$ at the $t$-th epoch |
| $\mathcal{G}^{\text{sub}}=(\mathcal{V},\mathcal{E}^{\prime}\cup\mathcal{E}^{\prime\prime})$ | the sparsified communication topology |
| $\mathbf{S}^{\mathcal{S}},\mathbf{S}^{\mathcal{T}}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}$ | the spatial and temporal graph masks |
| $\mathbf{A}^{\mathcal{S}}\in\{0,1\}^{|\mathcal{V}|\times|\mathcal{V}|}$ | the predefined spatial communication topology |
| $\mathbf{A}^{\mathcal{T}}\in\{0,1\}^{|\mathcal{V}|\times|\mathcal{V}|}$ | the predefined temporal communication topology |
| $\tilde{\mathcal{G}}^{\mathcal{S}}$ | the parameterized spatial graph |
| $\hat{\mathcal{G}}^{\mathcal{S}}$ | the parameterized spatial graph after DAG sampling |
| $\tilde{\mathcal{G}}^{\mathcal{T}}$ | the parameterized temporal graph |
| $\phi(\cdot)$ | the utility evaluation function |
| $\mathbf{B}^{\mathcal{S}}\in\{0,1\}^{|\mathcal{V}|\times|\mathcal{V}|}$ | the obtained binary spatial mask |
| $\mathbf{B}^{\mathcal{T}}\in\{0,1\}^{|\mathcal{V}|\times|\mathcal{V}|}$ | the obtained binary temporal mask |
| $K$ | the total number of dialogue rounds |
| $K^{\prime}$ | the dialogue round after which pruning takes place |
| $Q$ | the total number of queries |
| $Q^{\prime}$ | the number of queries after which pruning takes place |
|  |  |

## Appendix C Algorithm Workflow

We conclude the overall algorithm workflow of AgentPrune in [algorithm 3](#algorithm3).

Figure: Algorithm 3 Execution pipeline of LLM-MA systems combined with AgentPrune.

## Appendix D Multi-Query Training of AgentPrune

For complex tasks such as repository-level code generation (Qian et al., ), multi-turn dialogues ($K>5$) are often essential. In such cases, utilizing $K^{\prime}\in\{1,2\}$ rounds to optimize the topology and subsequently continue the dialogue for $K-K^{\prime}$ rounds is reasonable. However, for simpler tasks that involve numerous queries, such as multiple-choice answering (Agashe et al., ) or basic mathematical problems (Cobbe et al., ), previous studies (Yin et al., ; Qian et al., ) suggest that typically only $1$ to $2$ dialogue rounds are needed. In this context, prior dialogue-level optimization is no longer applicable. To better adapt AgentPrune to such circumstances, we propose a query-level optimization paradigm for AgentPrune.

Given a benchmark consisting of $Q$ queries, any LLM-MA framework processes these $Q$ queries sequentially to provide solutions one by one. We utilize the initial $Q^{\prime}(Q^{\prime}<<Q)$ queries as a ”training phase,” collaboratively optimizing the spatio-temporal communication topology while leveraging multiple agents for reasoning and evaluation. Following this, we perform one-shot pruning as described in [Equation 12](#S3.E12). The fixed topology $\mathcal{G}^{\text{sub}}$ is then employed for the reasoning and evaluation of the remaining $(Q-Q^{\prime})$ queries. We also refer to this approach as query-level optimization, in contrast to the dialogue-level optimization discussed in the main text. The distinction between the two lies in their focus: the latter concentrates on resolving a single query by utilizing several initial utterances to derive the topology, while the former considers the entire benchmark, employing a few early queries to inform the topology.

## Appendix E Cost Analysis

In [Section 3.4](#S3.SS4.SSS0.Px3), we present a token-saving analysis in a single-query setting. In this section, we provide a cost analysis for AgentPrune in a multi-query optimization context. Given a communication graph $\mathcal{G}$ and a benchmark with $Q$ queries, we assume that the LLM-MA framework iterates for $K$ dialogue rounds for each query. Furthermore, we denote the average token count per spatial, temporal, and query message as $c_{\mathcal{S}}$, $c_{\mathcal{T}}$, and $c_{q}$, respectively. Hence, the total token consumption of the vanilla system can be expressed as:

$$ $C_{\mathcal{G}}=QK\left[c_{\mathcal{S}}|\mathcal{E}^{\mathcal{S}}|+c_{\mathcal{T}}|\mathcal{E}^{\mathcal{T}}|+C_{q}|\mathcal{V}|\right]$ (14) $$

When utilizing AgentPrune, the LLM-MA framework processes the initial $Q^{\prime}$ queries while simultaneously optimizing the spatial-temporal connectivity. The token cost for this phase is:

$$ $MQ^{\prime}K\left[c_{\mathcal{S}}|\mathcal{E}^{\mathcal{S}}|+c_{\mathcal{T}}|\mathcal{E}^{\mathcal{T}}|+C_{q}|\mathcal{V}|\right].$ (15) $$

After pruning $\mathcal{G}^{\mathcal{S}}$ and $\mathcal{G}^{\mathcal{T}}$, we use the obtained $\mathcal{G}^{\text{sub}}$ to solve the remaining $Q-Q^{\prime}$ queries, with a cost of:

$$ $(Q-Q^{\prime})K\left[(1-p\%)\cdot\left(c_{\mathcal{S}}|\mathcal{E}^{\mathcal{S}}|+c_{\mathcal{T}}|\mathcal{E}^{\mathcal{T}}|\right)+C_{q}|\mathcal{V}|\right].$ (16) $$

Overall, the token savings of AgentPrune in a multi-query setting can be expressed as:

$$ $\Delta=(p\%\cdot Q+(1-p\%-M)Q^{\prime})K\left(c_{\mathcal{S}}|\mathcal{E}^{\mathcal{S}}|+c_{\mathcal{T}}|\mathcal{E}^{\mathcal{T}}|\right)+(1-M)Q^{\prime}KC_{q}|\mathcal{V}|$ (17) $$

## Appendix F Exisiting Spatial Communication Topologies

In this section, we introduce several existing spatial communication topologies, including chain, tree, star, complete graph, layered graph, random graph, and LLM-Blender.

### F.1 Chain Structure

The chain structure (in [Figure 7](#A6.F7)) is one of the most widely utilized communication architectures in contemporary multi-agent systems, as demonstrated by its application in ChatDev (Qian et al., ), MetaGPT (Hong et al., ), and L2MAC (Holt et al., ). In this architecture, the first agent receives input from the user, transforms it into new instruction, and subsequently forwards it to the next agent. For instance, in MetaGPT, user instructions are initially sent to the first agent, termed the ”product manager,” with information progressively relayed to subsequent agents, such as the architect agent, engineer agent, and QA engineer agent. Generally, the final agent in the chain provides a solution to the user’s request.

Figure: Figure 7: Demonstration of chain structure as spatial communication topology.
Refer to caption: /html/2410.02506/assets/x6.png

### F.2 Tree Structure

In a tree-like multi-agent pipeline, as shown in [Figure 8](#A6.F8), an administrative agent (commonly referred to as a teacher, commander, manager, etc.) oversees subordinate agents, which typically have distinct responsibilities. Ultimately, these subordinate agents submit their outputs to the administrative agent for final evaluation. Notable works employing this structure include AutoGen (Wu et al., ), SecurityBot (Yan et al., ), and MiniGrid (Zhou et al., ). For instance, in AutoGen (A4: Multi-Agent Coding), there exists a Commander agent alongside a Safeguard agent. The Writer is responsible for crafting the code and its interpretation, the Safeguard ensures safety (e.g., preventing information leaks and avoiding malicious code), and the Commander executes the code.

Figure: Figure 8: Demonstration of tree structure as spatial communication topology.
Refer to caption: /html/2410.02506/assets/x7.png

### F.3 Star Structure

The star structure resembles the tree structure and can essentially be viewed as a tree with a depth of two. When utilizing the star configuration for spatial communication, the central administrative agent receives queries from the user and dispatches instructions to subordinate agents. Upon completing their tasks using various tools, these subordinate agents return all outputs to the administrative agent, which then compiles a final summary, as illustrated in [Figure 9](#A6.F9).

Figure: Figure 9: Demonstration of star structure as spatial communication topology.
Refer to caption: /html/2410.02506/assets/x8.png

### F.4 Complete Graph Structure

In the main text, we refer to the structure shown in [Figure 10](#A6.F10) as a complete graph. However, this complete graph differs from the traditional definition, i.e., an undirected graph where each vertex is connected to every other vertex. Instead, it is a directed graph that would represent a complete graph if converted to an undirected form. This distinction is necessary because the execution of the multi-agent system relies on topological ordering (Qian et al., ; Zhuge et al., ), requiring the spatial communication topology to be a DAG. In MacNet (Qian et al., ), this structure is also referred to as a “Mesh graph.” After executing in the order determined by topological sorting, the final agent summarizes the dialogue and provides a concluding output or reflection.

Figure: Figure 10: Demonstration of complete graph structure as spatial communication topology.
Refer to caption: /html/2410.02506/assets/x9.png

### F.5 Layered Graph Structure

A layered graph, proposed by Qian et al. (), refers to the structure illustrated in [Figure 11](#A6.F11), resembling a stacked configuration similar to a multilayer perceptron (MLP). The query is first provided to all agents in the first layer, whose outputs serve as prompts that, along with the query, are then fed to the agents in the second layer. The final layer consists of a single agent that receives information from the previous layer and generates the ultimate solution.

Figure: Figure 11: Demonstration of layered graph structure as spatial communication topology.
Refer to caption: /html/2410.02506/assets/x10.png

### F.6 Random Graph Structure

A random graph refers to a sparse graph randomly sampled from a complete graph, as illustrated in [Figure 12](#A6.F12). Irregular random structures have been shown to outperform regular fully connected structures (Qian et al., ), which is attributed to the presence of random edge connections. Analogous to social networks, these connections can link “unacquainted” agents through direct shortcuts, transforming them into adjacent “acquaintances” and implicitly reducing the average path length, thereby exhibiting small-world characteristics.

Figure: Figure 12: Demonstration of random graph structure as spatial communication topology.
Refer to caption: /html/2410.02506/assets/x11.png

### F.7 LLM-Blender Structure

The structure of LLM-Blender is relatively straightforward. It feeds a query to multiple LLM-powered agents from different sources, employing a PairRanker mechanism to score each agent’s output. The top $K$ responses are then selected and merged using an LLM called GenFuser, as illustrated in [Figure 13](#A6.F13).

Figure: Figure 13: Demonstration of LLM-Blender structure as spatial communication topology.
Refer to caption: /html/2410.02506/assets/x12.png

## Appendix G Experimental Details

### G.1 Baselines

In this section, we will provide a detailed overview of the various baselines mentioned in [Section 4.1](#S4.SS1) and their adaptations for our evaluation.

#### G.1.1 Spatial Communication Baselines

The methods described below fall under the category of spatial communication, meaning they are designed to regulate how different agents interact and exchange information within the same dialogue round. Unless stated otherwise, we do not employ explicit inter-dialogue message passing and limit iterations to two rounds (i.e., $K=2$).

##### Chain

Given the diversity of benchmarks we employed (including mathematical reasoning, code generation, etc.), we organized distinct agent pools for different categories of reasoning tasks, as detailed in [Section G.2](#A7.SS2). In addition to personalized prompts for each agent, we also designed a universal prompt template applicable to all agents for generating outputs. Taking the MMLU benchmark as an example:

We utilize the output from the final agent as the decision for the entire system.

##### Star

When employing the star structure, as described in [Section F.3](#A6.SS3), we designate one agent as the administrative agent and utilize the other agents as subordinates. The administrative agent ultimately collects outputs from the subordinate agents to make a decision. During the final decision-making process, the prompt is as follows:

##### Tree

We reduce the tree structure to a binary tree and sequentially assign agents based on the binary tree indexing, depending on the number of agents. The outputs from all non-root nodes are ultimately relayed to the root node’s agent for the final decision, with the prompt template remaining the same as the Star structure.

##### Complete Graph

We employ the structure outlined in [Figure 10](#A6.F10) and execute the input/output for each agent node through topological sorting. Before performing topological sorting, it may be necessary to apply the DAG sampling method discussed in [Section 3.1](#S3.SS1) to ensure that the spatial communication graph is a DAG. Given the relative complexity of the graph structure, which does not possess a straightforward core agent like a chain or tree, we introduce an additional summarizer node to which all other nodes direct their outputs. Naturally, this summarizer node is executed last in the topological order, positioning it as the final decision-making expert.

##### Layered Graph

As discussed in [Section F.5](#A6.SS5), we arrange the agents in an MLP-like layered structure, ensuring that the final layer contains only one agent. This agent receives outputs from all agents in the preceding layer and produces the final solution.

##### Random Graph

The implementation of a random graph is similar to that of a complete graph. It also begins with DAG sampling, followed by execution through topological sorting, and concludes with a summarizer agent that generates the overall response.

##### LLM-Blender

LLM-Blender (Jiang et al., ) was originally designed to consolidate responses from various LLM architectures. In this context, we treat it as a spatial message-passing paradigm, standardizing all agents to utilize either gpt-3.5 or gpt-4, with the final output from GenFuser serving as the solution. Notably, LLM-Blender is specifically tailored for single-turn dialogues; thus, we do not employ multi-turn dialogues in conjunction with LLM-Blender.

##### GPTSwarm

GPTSwarm (Zhuge et al., ) conceptualizes the connections among all agents as a parameterized, dense adjacency matrix, which is continuously optimized to enhance collaborative performance. In the original paper, distinct internal structures were customized for different agents, such as configuring a specific agent to first receive a query, followed by performing FileAnalyze and WebSearch, and ultimately outputting the results. To ensure a fair comparison, we did not utilize such configurations in [Table 1](#S4.T1); instead, we assigned each agent different profiles, similar to the other structures mentioned above, along with possible external tools like a Python compiler or Wikipedia searcher. Our implementation is based on the resources available at [https://github.com/metauto-ai/GPTSwarm](https://github.com/metauto-ai/GPTSwarm). Important Note: in the originally open-sourced code, the multi-agent collaboration for MMLU dataset only transmitted the options A/B/C/D during dialogues, without including the content of agents’ reasoning process, which is not consistent with the description in Section 2.2 of their manuscript. To ensure a fair comparison and maintain consistency with the original description, we modified their code to transmit both the choices and the reasoning process.

#### G.1.2 Temporal Communication Baselines

##### LLM-Debate

LLM-Debate (Du et al., ) is designed for multiple agents to engage in a debate, where in each round, every agent receives the outputs of all agents from the previous round before making their own statements. Consequently, it essentially forms a fully connected temporal communication graph, as illustrated in [Figure 14](#A7.F14).

Figure: Figure 14: Demonstration of LLM-Debate structure as temporal communication topology.
Refer to caption: /html/2410.02506/assets/x13.png

##### PHP

PHP (Zheng et al., ) progressively improves prompts by utilizing the entirety of historical dialogue, offering potential ”hint” prompts. In this context, we adapt this setting to the multi-agent collaboration framework, using the decisions made after each round of dialogue as hint prompts for all agents in the subsequent round, as depicted in [Figure 15](#A7.F15).

Figure: Figure 15: Demonstration of PHP structure as temporal communication topology.
Refer to caption: /html/2410.02506/assets/x14.png

##### DyLAN

DyLAN (Liu et al., ) primarily focuses on optimizing temporal communication and reducing redundancy by employing a specific scoring mechanism to eliminate low-quality outputs between every two rounds of dialogue. We utilize the official implementation available at [https://github.com/SALT-NLP/DyLAN](https://github.com/SALT-NLP/DyLAN).

#### G.1.3 Others

In [Section 4.3](#S4.SS3), we integrated AgentPrune with AutoGen and GPTSwarm under both three-agent and five-agent configurations. Here, we elaborate on how we implemented AutoGen, which is inherently a customizable framework. Based on the setup from AutoGen (A5: Dynamic Group Chat), we define five roles: user proxy, manager, engineer, critic, and code executor. For the three-agent configuration, we condense these roles into manager, engineer, and critic. The detailed communication structure is depicted in [Figure 16](#A7.F16).

Figure: Figure 16: The AutoGen system design with three/five LLM-based agents. The dashed line indicates the agent will propagate its rationale or output back to the manager for its final decision-making.
Refer to caption: /html/2410.02506/assets/x15.png

### G.2 Agent Profiling

Previous works (Wang et al., ) have formally established that assigning different personas or roles to LLM-based agents can enhance cognitive synergy among agents. Consequently, we utilized gpt-4 to generate a series of agent profiles for various tasks, thereby promoting diversity and collective intelligence in a multi-agent setting.

#### G.2.1 Profile Examples for General Reasoning

Below are some examples of agent profiles tailored for general reasoning tasks:

#### G.2.2 Profile Examples for Mathematical Reasoning

Below are some examples of agent profiles tailored for mathematical reasoning tasks:

#### G.2.3 Profile Examples for Code Generarion

Below are some examples of agent profiles tailored for code generation tasks:

### G.3 Agent Attack Implementation

We designed two types of attacks on agents: agent prompt attack and agent replacement attack, with specific implementations detailed as follows:

##### Agent Prompt Attack

We attempt to compromise the role prompt of the collaborative agent, altering its predefined role to the following “lier” agent:

##### Agent Replacement Attack

We replace the originally high-cognitive and planning-capable LLM with a randomly generating “dummy” API that outputs text without coherence. The specific prompt is as follows:

When attacking all multi-agent frameworks, we randomly select one agent to serve as the adversarial agent, while the remaining agents retain their original functions and responsibilities.

## Appendix H Supplemented Experimental Results

### H.1 Results for RQ1

[Figures 17](#A8.F17), [18](#A8.F18) and [19](#A8.F19) compares AgentPrune with other communication topologies in terms of completion tokens, overall tokens, and overall cost (USD). Notably, across multiple datasets, AgentPrune achieves superior performance at a fraction of the cost, often as low as one-half or even one-tenth of the economic expense of SOTA topologies. For instance, on the MMLU dataset, AgentPrune surpasses GPTSwarm’s performance with a cost of only $\$5.6$, compared to GPTSwarm’s $\$43.56$. Similarly, on the GSM8K dataset, AgentPrune outperforms DyLAN with a cost of $\$65.9$, whereas DyLAN incurs a cost of $\$357.47$.

Figure: Figure 17: Scatter plot illustrating the performance metrics and total token consumption of different multi-agent communication topologies across the MMLU, HumanEval, and GSM8K datasets. The diameter of each point is proportional to the value on the y-axis, representing token consumption.
Refer to caption: /html/2410.02506/assets/x16.png

Figure: Figure 18: Scatter plot illustrating the performance metrics and completion token consumption of different multi-agent communication topologies across the MMLU, HumanEval, and GSM8K datasets. The diameter of each point is proportional to the value on the y-axis, representing token consumption.
Refer to caption: /html/2410.02506/assets/x17.png

Figure: Figure 19: Scatter plot illustrating the performance metrics and total cost (USD) of different multi-agent communication topologies across the MMLU, HumanEval, and GSM8K datasets. The diameter of each point is proportional to the value on the y-axis, representing the economic cost.
Refer to caption: /html/2410.02506/assets/x18.png

### H.2 Results for RQ2

[Table 5](#A8.T5) presents a comparison of the performance, prompt/completion token consumption, and cost between AgentPrune integrated with three-agent-based AutoGen and GPTSwarm frameworks.

**Table 5: Performance and Cost Comparison before and after combining AgentPrune. We evaluated the performance and economic cost comparison of AgentPrune in conjunction with two classic multi-agent systems, AutoGen and GPTSwarm, under a three gpt-4-based setting.**
| Dataset | Method | Performance | # Prompt Tokens | # Completion Tokens | Cost |
| --- | --- | --- | --- | --- | --- |
| MMLU | AutoGen | $81.94$ | $346,028$ | $66,204$ | $\$5.446$ |
| +AgentPrune | $82.20({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 0.26})$ | $274,665(\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}79.4\%)$ | $66,803$ | $\$4.750$ |  |
|  | AutoGen | $83.66$ | $351,985$ | $90,762$ | $\$6.242$ |
| HumanEval | +AgentPrune | $85.04({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 1.38})$ | $254,203({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}72.2\%})$ | $89,362$ | $\$5.282$ |
|  | AutoGen | $87.23$ | $2,317,937$ | $624,055$ | $\$41.92$ |
| GSM8K | +AgentPrune | $88.51({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 1.23})$ | $1,481,780({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}63.9\%})$ | $629,771$ | $\$33.71$ |
|  | GPTSwarm | $83.32$ | $1,521,504$ | $325,994$ | $\$24.99$ |
| MMLU | +AgentPrune | $83.66({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 0.34})$ | $554,698({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}35.8\%})$ | $336,887$ | $\$15.65$ |
|  | GPTSwarm | $83.62$ | $1,478,312$ | $612,815$ | $\$33.16$ |
| HumanEval | +AgentPrune | $84.74({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 1.12})$ | $432,480({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}29.2\%})$ | $598,367$ | $\$22.07$ |
|  | GPTSwarm | $87.85$ | $6,274,665$ | $186,510$ | $\$68.34$ |
| GSM8K | +AgentPrune | $88.30({\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color@cmyk@fill{0}{0.77}{0.87}{0}\uparrow 0.45})$ | $3,009,115({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}47.9\%})$ | $173,296$ | $\$35.29$ |
|  |  |  |  |  |  |

### H.3 Results for RQ3

We supplement the performance of various topologies before and after being perturbed by agent replacement attack in [Figure 20](#A8.F20).

Figure: Figure 20: Performance under adversarial attack. We compare the performance of various multi-agent frameworks before and after agent replacement attacks. “w/ AP” indicates the integration with AgentPrune.
Refer to caption: /html/2410.02506/assets/x19.png

### H.4 Results for RQ4

#### H.4.1 Ablation Study

We develop two variants of AgentPrune: “AgentPrune w/o profile”, which assigns no unique roles to each agent, and “AgentPrune w/o low-rank”, which does not implement the low-rank regularization described in [Equation 11](#S3.E11). The results are presented in [Table 6](#A8.T6).

**Table 6: Abltion study of AgentPrune. “w/o profile” denotes not assigning agents with different roles and profiles; “w/o low-rank” denotes not using the low-rank regularization as described in [Equation 11](#S3.E11).**
| Variant | MMLU | GSM8K | MultiArith | SVAMP | AQuA | HumanEval |
| --- | --- | --- | --- | --- | --- | --- |
| AgentPrune-C | 84.72 | 95.62 | 97.25 | 91.85 | 79.47 | 89.38 |
| w/o profile | 84.3 | 93.7 | 96.2 | 91.7 | 79.1 | 87.8 |
| w/o low-rank | 84.6 | 94.5 | 96.8 | 91.1 | 79.5 | 88.9 |
| AgentPrune-R | 83.94 | 95.83 | 96.30 | 91.68 | 78.60 | 90.30 |
| w/o profile | 83.3 | 95.6 | 95.7 | 91.7 | 78.7 | 88.6 |
| w/o low-rank | 83.5 | 95.4 | 96.0 | 91.3 | 78.4 | 89.3 |
|  |  |  |  |  |  |  |

#### H.4.2 Sensitivity Analysis

We analyze the sensitivity of AgentPrune to two parameters: the number of agents $|\mathcal{V}|$ and the early stopping round $K$. The findings are presented in [Figure 21](#A8.F21). Notably, as the number of agents increases, there is a significant performance enhancement initially (from 3 to 5 agents), while subsequent improvements (from 5 to 9 agents) in accuracy become relatively marginal. The early stopping round $Q^{\prime}$ indicates the number of queries used to optimize spatial-temporal connectivity in a multi-query training setting. Intuitively, increasing the number of optimization rounds leads to a more refined and accurate graph mask, resulting in substantial performance gains from multi-agent collaboration, along with reduced performance fluctuations. To balance performance with token savings, we consistently set $Q^{\prime}\in\{5,10\}$.

Figure: Figure 21: Parameter sensitivity analysis on AgentPrune. we vary the number of agents $|\mathcal{V}|\in\{3,4,5,6,7,8,9\}$ and the early stopping round $Q^{\prime}\in\{5,10,15,15,20,25\}$ on MMLU dataset.
Refer to caption: /html/2410.02506/assets/x20.png

## Appendix I Case Study

### I.1 Spatial Topology Visualization

In this section, we will demonstrate how AgentPrune operates on the predefined spatial communication structure and the resulting structure after one-shot pruning. It is important to note that the pruned sparse graph we present is likely not a Directed Acyclic Graph (DAG). This is because, during the practical application, we still need to utilize the DAGSampling function on the pruned graph to ensure it conforms to DAG properties before sequentially executing agent I/O.

##### GPTSwarm + MMLU

[Figure 22](#A9.F22) illustrates how AgentPrune applies one-shot pruning within a five-agent GPTSwarm framework, where three agents serve as simple I/O agents, and the remaining two are TOT (Tree of Thoughts) agents. Notably, AgentPrune prunes many in-edges for the I/O agents, while preserving many for the TOT agents. This behavior likely stems from the stronger reasoning capabilities of TOT agents, which makes them better suited for synthesizing the agents’ discussions and providing the final solution.

Figure: Figure 22: The pruning process of AgentPrune on a five-agent GPTSwarm framework when tested on MMLU.
Refer to caption: /html/2410.02506/assets/x21.png

##### AutoGen + HumanEval

[Figure 23](#A9.F23) illustrates how AgentPrune applies one-shot pruning within a five-agent AutoGen framework.

Figure: Figure 23: The pruning process of AgentPrune on a five-agent AutoGen framework when tested on MMLU.
Refer to caption: /html/2410.02506/assets/x22.png

##### Complete Graph + MMLU

[Figure 24](#A9.F24) illustrates how AgentPrune performs one-shot pruning to achieve a compact sparse spatial communication graph, given five predefined agent roles: knowledge expert, critic, historian, mathematician, and psychologist, along with a predefined complete graph structure on MMLU dataset. It is evident that in the pruned graph, the Critic has a high number of incoming edges, while the Knowledge Expert has a high number of outgoing edges. This aligns with their respective functions: the Critic is expected to receive a broad range of external information and provide feedback, whereas the Knowledge Expert should output useful knowledge based on their knowledge base.

Figure: Figure 24: The pruning process of AgentPrune on a five-agent complete-graph-like framework when tested on MMLU dataset.
Refer to caption: /html/2410.02506/assets/x23.png

##### Random Graph + MMLU

[Figure 25](#A9.F25) illustrates how AgentPrune performs one-shot pruning, given five predefined agent roles along with a predefined random graph structure on MMLU dataset. The pruned graph structure is similarly aligned with that in [Figure 24](#A9.F24), with the Critic having many incoming edges and the Knowledge Expert having many outgoing edges. Notably, the absence of outgoing edges for the psychologist in [Figure 25](#A9.F25) may suggest that this role has limited utility within the overall system.

Figure: Figure 25: The visualization of how AgentPrune prunes a five-agent random-graph-like framework when tested on MMLU dataset.
Refer to caption: /html/2410.02506/assets/x24.png

##### Random Graph + HumanEval

[Figure 26](#A9.F26) demonstrates how AgentPrune implements one-shot pruning based on five predefined agent roles: project manager, algorithm designer, bug fixer, test analyst, and programming expert, utilizing a predefined complete graph structure on the HumanEval dataset. Notably, the outer edges of the graph are retained, aligning with the standard workflow for code completion, which is consistent with the designs of multi-agent code generation frameworks like MetaGPT (Hong et al., ). The Bug Fixer has no outgoing edges, as it represents the final step in the code completion process. This effectively highlights AgentPrune’s capability for autonomous optimization of multi-agent collaborative topologies.

Figure: Figure 26: The visualization of how AgentPrune prunes a five-agent complete-graph-like framework when tested on the HumanEval dataset.
Refer to caption: /html/2410.02506/assets/x25.png

Figure: Figure 27: The visualization of how AgentPrune prunes a five-agent random-graph-like framework when tested on the HumanEval dataset.
Refer to caption: /html/2410.02506/assets/x26.png

##### Complete Graph + HumanEval

[Figure 26](#A9.F26) illustrates how AgentPrune executes one-shot pruning based on four predefined agent roles: math solver, math analyst, programming expert, and inspector, utilizing a predefined complete graph structure on the GSM8K dataset. In this scenario, we designated two agents as math solvers. Interestingly, the pruned graph structure reveals explicit differentiation in roles for the two math solvers: one is responsible for preliminary solving, while the other is tasked with final solving. The final solver gathers information from all other nodes and has no outgoing edges.

##### Complete Graph + GSM8K

[Figure 28](#A9.F28) illustrates how AgentPrune performs one-shot pruning based on four predefined agent roles and a predefined random graph structure on the GSM8K dataset. We observe a distinct differentiation in node characteristics: the agents focused on problem analysis exhibit a high out-degree with no incoming edges, while the agents responsible for problem-solving demonstrate a high in-degree and a low out-degree.

Figure: Figure 28: The visualization of how AgentPrune prunes a five-agent complete-graph-like framework when tested on the GSM8K dataset.
Refer to caption: /html/2410.02506/assets/x27.png

Figure: Figure 29: The visualization of how AgentPrune prunes a five-agent random-graph-like framework when tested on the GSM8K dataset.
Refer to caption: /html/2410.02506/assets/x28.png

### I.2 Temporal Topology Visualization

[Figures 31](#A9.F31) and [30](#A9.F30) demonstrate how AgentPrune operates on the predefined temporal communication structure and the resulting structure after one-shot pruning.

Figure: Figure 30: The visualization of how AgentPrune temporally prunes a five-agent LLM-Debate-like framework when tested on the HumanEval dataset.
Refer to caption: /html/2410.02506/assets/x29.png

Figure: Figure 31: The visualization of how AgentPrune temporally prunes a four-agent LLM-Debate-like framework when tested on the GSM8K dataset.
Refer to caption: /html/2410.02506/assets/x30.png

### I.3 Spatial Connectivity Optimization

[Figures 32](#A9.F32), [34](#A9.F34) and [33](#A9.F33) illustrate the optimization trajectory of spatial connectivity before applying one-shot pruning. As time progresses, the initially identical graph masks begin to show increasing differentiation, with their magnitudes serving as a crucial reference for subsequent pruning decisions.

Figure: Figure 32: The demonstration of how spatial connectivity evolves and optimizes over time on MMLU.
Refer to caption: /html/2410.02506/assets/x31.png

Figure: Figure 33: The demonstration of how spatial connectivity evolves and optimizes over time on HumanEval.
Refer to caption: /html/2410.02506/assets/x32.png

Figure: Figure 34: The demonstration of how spatial connectivity evolves and optimizes over time on GSM8K dataset.
Refer to caption: /html/2410.02506/assets/x33.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: I would like to know the required quantity of data to be generated as well as the number and types of mask configurations necessary for training in Sections 3.2 and 3.3.
soundness: 3
strengths: 1. The connectivity optimization methods (distribution approximation and low-rank sparsity) appear highly effective. By applying a straightforward policy gradient approach and sparsity optimization on the graph masks, the framework efficiently enhances the performance and robustness across various multi-agent frameworks and tasks while reducing the token cost.
summary: The paper introduces AgentPrune, a communication framework designed for LLM-MA systems. AgentPrune addresses inefficiencies in traditional multi-agent communication by reducing redundant messaging, which can lead to excessive token usage and increased costs. The framework formalizes the communication between agents as a spatial-temporal message-passing graph and optimizes its token usage without compromising task performance. Key findings include a significant reduction in token overhead and improved robustness against adversarial attacks. Through extensive testing on various benchmarks, AgentPrune demonstrated cost-effective, high-performance capabilities, achieving similar or better results compared to conventional models but at a fraction of the token cost.
weaknesses: 1. It appears necessary to fix the number and roles of agents before implementing AgentPrune. 
2. To effectively train each version of the framework, a substantial amount of data is required to optimize the connectivity parameters through sufficient rollouts.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: - What's the training time for this proposed method. Does it overfit to the training data? How does the K' affects the performance.
- Does the mask changes depending on the input data?
- How does the proposed method perform compared to random pruning? 
- Can distribution approximation and low-rank sparsity work in isolation? what's their effect on the accuracy and communication reducing?
soundness: 3
strengths: - This work looks into an important problem of reducing cost when using multi-agent LLM system. 
- The paper is well written and relatively easy to follow.
summary: This work focuses reducing communication between multi-agent LLM systems. The goal is to reduce spatial and temporal communication required between multiple LLM agents while keeping high accuracy. The authors propose learning a graph mask using distribution approximation and low-rank sparsity. The proposed method is evaluated on a wide variety of benchmark in terms of communication and cost required and the accuracy achieved.
weaknesses: - The paper start with showing random pruning can provide performance improvement, but the proposed method is not compared to the random pruning, so it is hard to understand how much improvement compared to random pruning we have.
- It is not unclear how much training and query/tokens is need to train the system, and how different number of training (one-shot) is needed and how they affect the performance.
- Missing ablation study about the benefit of each of the propose methods (i.e. distribution approximation, low-rank sparsity)

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: * What’s the minimum scale (in terms of e.g. dataset size and number of queries) where AgentPrune is more cost-effective than other techniques?
* Do networks trained on a task transfer to similar tasks?
soundness: 3
strengths: * The paper does a good job of formalizing the problem, which I agree is an important one;
* Modelling the task as a spatiotemporal graph is also a pretty solid idea, and the proposed technique can be seen as an intuitive extension of this approach;
* The cost reduction is significant;
* I appreciated the parameter sensitivity analysis and the ablation study, as these types of studies, while expensive, are very important for proper science.
summary: The paper studies the communication redundancy problem, i.e. the fact that when multiagent networks solve a task, several exchanged messages are redundant. To address this problem, they model communication as a spatiotemporal graph (i.e. a graph that models both which agents interact with each other and what context should be included) and introduce AgentPrune, an optimization technique that reduces the level of redundancy while preserving performance. This technique involves three steps:
* In the "training" phase ($K^\prime$ rounds), the spatiotemporal graph is optimized according to a metric that rewards assigning higher weights to important connections while at the same time increasing sparsity;
* The connections are then pruned according to a threshold;
* From that point onwards ($K - K^\prime$ rounds), only the non-pruned connections are used.

The authors then study the performance of AgentPrune both in its standalone form and in conjunction with other multiagent frameworks, finding a reduction in overall cost; they also find that AgentPrune leads to improvements in robustness against agent-targeted adversarial attacks.

Overall, the paper studies an important problem and proposes a reasonable (though far from perfect) approach to reduce communication redundancy. In particular, the technique requires an expensive training step; however, for large enough datasets, this leads to long-term efficiency gains. Aside from some issues that raised a few eyebrows, the experimental analysis is well done and the model also offers some robustness gains as a bonus. ~For this reason, my recommendation is 6 (Marginally above acceptance threshold).~

~I would be willing to raise my score should the authors take the following steps (see the Weaknesses section):~
* ~Presenting the results in Table 2 and 3 in a more balanced light;~
* ~Adding the missing experimental info;~
* ~Answering the questions reported in the Questions section (assuming that the results showcase the transferability of AgentPrune).~

Update: the authors' rebuttal has addressed essentially all of my concerns, which is why I'm raising my score to 8 (Accept).
weaknesses: Note: Most of these weaknesses have been addressed in the rebuttal.

It is unclear to me how applicable AgentPrune is in a real-world context. AP makes sense in situations where the deployer already has a training set for a given task and is willing to invest resources into optimizing the communication graph for future queries. In other words, using AP is reasonable from an economics point of view only at large scales, where there are enough training examples and enough expected future queries to warrant such an optimization step. To be clear, this is not a dealbreaker: several real-world applications fit this description, and my critique of AP can also be applied to any other network optimization technique (e.g. GPTSwarm). Still, it’s hard to make a case for widely applicable cost savings, especially since each graph appears to be task-specific and thus not transferable. Comparing with optimization-free baselines (e.g. CoT) is also a bit unfair, since they do not require this initial training step.

Moreover, emphasizing the reduction in prompt tokens instead of the cost itself (e.g. in Table 3) is slightly misleading, since a) deployers care about the cost, not the prompt tokens b) the cost reductions, while still good, are often less impressive than the prompt token reduction (e.g. -17% cost vs -36% tokens for AG+HumanEval, -55% cost vs -78% tokens for GPTSwarm+MMLU, -52% cost vs -73% tokens for GPTSwarm+HumanEval). In the same vein, reporting in Table 2 the performance gain w.r.t. Vanilla sort of hides the fact that AgentPrune has slightly worse performance compared to Reflexion prompting (which is not a dealbreaker, but it should still be noted).

Finally, there are some missing experimental details in the paper, such as:
* What function is used as $\phi$ in the experiments?
* What connection probability is used to generate the random graph?
* What’s the diversity penalty for the OpenAI models?

While I found the answers to these questions in the code, given the non-static nature of repositories these values should also be reported in the experimental setup appendix of the code.

Minor notes:
* In Table 6 there's a typo related to the word "ablation";
* Again in Table 6, the original scores have 4 significant digits, but the ones after ablation only have 3;
* The title of Appendix F contains a misspelled "Existing";
* Figure 30 has a typo in the word HumanEval;
* In G.3 “liar" is misspelled as “lier”.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Regarding point 2: If you could include experiments that require high contextual awareness, demonstrating that your model can improve both quality and token efficiency in such scenarios, I would be happy to raise my evaluation score.

And I would appreciate a deeper analysis of the types of errors or ineffective communications that AgentPrune eliminates, as this would clarify the practical implications of its pruning method. Such insights would better illustrate AgentPrune’s strengths and limitations and help inform users of any potential side effects.
soundness: 2
strengths: 1. It addresses an important problem in MAS involving LLMs: the significant economic costs associated with token usage. By focusing on token efficiency, it highlights an often-overlooked aspect of MAS design, especially relevant as these systems scale up. The emphasis on reducing token consumption could encourage future MAS research to adopt similar cost-effective approaches, making it a useful reference for economical MAS deployment.

2. It borrows idea from the spatial-temporal graphs to manage agent communication provides a structured way to visualize and optimize message passing in MAS. This graph-based approach brings an analytical perspective to inter-agent communication, offering insights into which interactions can be minimized without sacrificing performance. Such structured pruning could inspire other MAS research to explore graph-based techniques for optimizing agent communication.

3. It formally define "communication redundancy" in LLM-powered MAS, bringing attention to the often excessive and unnecessary communications within these systems. By identifying this redundancy, the authors shed light on a specific inefficiency that had not been well-formalized in previous MAS research, thus contributing a valuable perspective to MAS optimization.
summary: The paper introduces AgentPrune, a framework aimed at optimizing communication in LLM-based multi-agent systems by reducing unnecessary message exchanges, which in turn lowers token usage and economic costs. In MAS, agents collaborate through complex communication topologies, which, while enhancing collective intelligence, can lead to significant token overhead and high operational expenses.

AgentPrune addresses this challenge by introducing a "communication pruning" mechanism, where redundant or non-essential messages within the spatial (intra-dialogue) and temporal (inter-dialogue) message-passing graph are pruned. 

Experiments demonstrate AgentPrune's effectiveness across several benchmarks, including MMLU, GSM8K, and HumanEval. Experimental results indicate that AgentPrune achieves comparable performance to existing MAS topologies at a fraction of the cost, with a reported token reduction of up to 72.8% and an increased robustness to basic adversarial attacks by 3.5% to 10.8%
weaknesses: 1. Inadequate Justification for Pruning Methodology: The one-shot pruning approach, though efficient, lacks theoretical grounding in the context of MAS. The decision to prune a fixed percentage of tokens and communication paths across all tasks does not account for the varying communication needs of different agents or tasks. This oversimplified pruning criterion may lead to suboptimal performance in scenarios where more dynamic and context-sensitive pruning is required.

2. The paper provides little analysis of how pruning affects the quality and depth of agent interactions or task accuracy, especially in more nuanced MAS tasks. **For instance, the pruning’s impact on collaborative tasks requiring high contextual awareness is underexplored.**

3. The number of colors and the format of text in Figure 1 is excessive, and the text is too lengthy, making the annotations unclear and distracting from the overall understanding of the figure.

Meta-review: This paper looks at optimizing the communication paradigms in multi-agent systems — roughly, “can we use fewer tokens over the course of a multi-agent task solve to achieve similar or better end results than a baseline without optimization.”  Their focus is on pruning communication paths between agents - spatial paths, which are agent-to-agent interactions within a single time tick, and temporal paths, where an agent’s output at tick t may or may not be used at tick t+1.  Their general goal here is to maintain high connectivity (spatiotemporal) across the agents while minimizing comms paths and tokens flowing across the comms paths.  This AC appreciates the formalization of the multi-agent communication dynamics, sees the optimizations done as relatively straightforward, but mainly was impressed by the applied part of this project - it does look like this can be a drop-in optimization into many of the current MAS frameworks, as supported by the extensively experimental results in the latter half of the paper and the rebuttal.

Decision: Accept (Poster)