On the Resilience of Multi-Agent Systems with Malicious Agents

We deeply appreciate your efforts in reviewing and recognition of our experiment’s comprehensiveness and non-trivial insights. Your feedback has significantly improved our paper. In the response, we address your concerns one by one.

The paper seem to be unaware of the existing, and very well known literature of malicious agents in a system (such as the Byzantine Generals problem in its many variations). There are algorithms that are extensively used in networking protocols and database systems.

Thank you for your insightful comment. We acknowledge that the Byzantine Generals problem and its variations represent foundational work in understanding malicious agents in distributed systems, with numerous algorithms addressing attacks such as DDoS, MITM, Sybil, and impersonation [3, 4, 5]. While these studies focus on designing specific system-level mechanisms like authentication, authorization, and confidentiality [1, 2, 6], our work diverges by exploring the organizational structures and interaction strategies of LLM-based multi-agent systems. The scenarios we investigate mirror real-world human collaboration dynamics rather than the behavior of traditional distributed nodes, offering a novel perspective distinct from conventional solutions.

[1] Reiter, Michael, Kenneth Birman, and Li Gong. "Integrating Security in a Group Oriented Distributed System." Proceedings 1992 IEEE Computer Society Symposium on Research in Security and Privacy. IEEE Computer Society, 1992.

[2] Satyanarayanan, Mahadev. "Integrating security in a large distributed system." ACM Transactions on Computer Systems (TOCS) 7.3 (1989): 247-280.

[3] Harinath, Depavath, P. Satyanarayana, and M. R. Murthy. "A review on security issues and attacks in distributed systems." Journal of Advances in Information Technology 8.1 (2017).

[4] Brown, Philip N., Holly P. Borowski, and Jason R. Marden. "Security against impersonation attacks in distributed systems." IEEE Transactions on Control of Network Systems 6.1 (2018): 440-450.

[5] Kumar, Manoj, and Nikhil Agrawal. "Analysis of different security issues and attacks in distributed system a-review." International Journal of Advanced Research in Computer Science and Software Engineering 3.4 (2013): 232-237.

[6] Mudholkar, P. K., and M. Mudholkar. "Security in distributed system." Proceedings of the International Conference and Workshop on Emerging Trends in Technology. 2010.

The paper presents as new discoveries facts such as hierarchical systems are more resilient because the agent at the top of the hierarchy is provided "with various versions of the answer by multiple agents performing the same sub-task". This is not a property of hierarchy, but of replication - again, distributed system theory contains many algorithms that can show how to protect against malicious agents in a fully flat and distributed environment.

Thank you for this insightful comment. While replication indeed enhances resilience, our argument highlights the additional role of hierarchy in improving performance. For instance, in the MAD system, removing the Judge transforms the structure into a flat configuration where two agents debate directly. Although replication ensures multiple interaction rounds, the absence of hierarchical oversight degrades performance, as the Judge's role in aggregating and adjudicating inputs is critical for efficiency and accuracy. This distinction underscores the unique contribution of hierarchical systems beyond simple replication.

The various agent implementations considered in this paper are essentially relatively short prompts provided to ChatGPT. The validity of various observations is thus dependent on the current version of ChatGPT, which might be different by the time this paper is presented. Do you expect that the observations in this paper about the relative strengths of different architectures will be still valid for the next versions of language models? What happens if this paper is published and becomes part of the knowledge-base of the LLMs?

Thank you for raising this important point. We acknowledge that advancements in LLMs may impact performance. To address this, we conducted experiments with different iterations of GPT, specifically GPT-3.5 and GPT-4o, as detailed in Appendix A (Line 772, Page 15). The results show a general performance improvement with GPT-4o while our core conclusions remain consistent: hierarchical structures consistently outperform others, rigorous tasks are more susceptible to malicious agents, and systems like MAD and Camel also exhibit performance gains. This suggests that our findings are robust across model updates, providing a strong foundation for future iterations of LLMs.

We deeply appreciate your efforts in reviewing and recognition of our experiment’s comprehensiveness and impactful insights. Your feedback has significantly improved our paper. In the response, we address your concerns one by one.

The experiment models are limited: As it only tests on the gpt-based models, gpt3.5 and gpt4o. Following the weakness point 1, I suggest you can deploy experiments on the o1-mini, o1-preview, I hope to see the results.

Thank you for the valuable suggestion. To broaden the scope of our investigation and ensure our conclusions generalize beyond the GPT model family, we conducted additional experiments using one of the state-of-the-art open-source models, the LLaMA-3.1-70B-Instruct. The results, presented in the tables below, confirm that our findings hold across diverse model architectures, including non-GPT-based LLMs.

The paper presents results across tasks that involve different cognitive demands (e.g., code generation requiring precision versus translation being more subjective). However, there is limited analysis of how the degree of agent specialization affects system resilience in different MAS structures. Following the weakness point 2, whether agents with specialized roles (e.g., a math-focused agent vs. a generalist) exhibit varying vulnerabilities to malicious behaviors is not fully explored. This is a missed opportunity to highlight if specialized roles within the MAS require additional security considerations or different structural adjustments.

Thank you for this insightful comment. In Section 4.7 (Line 422, Page 8), we conducted an initial experiment where the Manager (Instructor) was made malicious instead of the Coder in Camel and MetaGPT. Our findings indicate that compromising higher-level task distributors leads to a more significant performance decline in both systems. While this provides preliminary insights, we acknowledge the need for a more comprehensive analysis of how agent specialization impacts resilience to malicious behaviors. We have noted this as an important avenue for future research, as the primary focus of this paper is on the influence of organizational structures in MAS.

While the chosen tasks (code generation, math, translation, and text evaluation) provide a reasonable testbed, they may not fully represent the diversity of tasks that MAS are deployed to handle. These tasks are fairly discrete and objective; however, multi-agent systems in more nuanced, real-world applications (e.g., recommendation engines or dynamic response systems) might face unique types of malicious behavior. Including a more diverse array of tasks or explaining the rationale behind the current selection would strengthen the applicability of the findings.

Thank you for this insightful comment. We acknowledge that the four tasks chosen may not fully capture the diversity of real-world multi-agent system applications. Our selection was guided by their prevalence in existing literature and their suitability for evaluating the resilience of the six systems studied. We recognize the importance of exploring more nuanced and dynamic scenarios, such as recommendation systems or multidisciplinary team consultations in healthcare, and will incorporate these in future research to enhance the applicability of our findings.

In one instance, the authors claim that they are "the first to examine how different structures of multi-agent systems affect resilience" to malicious agents, which is clearly false in general (as opposed to the special case of LLM agents). Indeed, as far as I can tell, none of the literature on game theory and the fault-tolerance of multi-agent/distributed systems is cited in the related work section. I suspect that there are many ideas in that literature that the authors might find useful for solving the problems they are interested in.

We appreciate the reviewer’s feedback and the suggestion to consider broader literature. We acknowledge the extensive body of work on the fault-tolerance of distributed systems, including the Byzantine Generals problem and related attacks such as DDoS, MITM, Sybil, and impersonation [3, 4, 5]. However, much of this work focuses on specific system designs, emphasizing mechanisms like Authentication, Authorization, and Confidentiality [1, 2, 6].

In contrast, our paper addresses the organizational structures of LLM-based multi-agent systems, which differ significantly in nature. These systems mimic real-world human collaboration dynamics rather than functioning as traditional distributed nodes. This novel focus on structural design in LLM-based systems sets our work apart.

[1] Reiter, Michael, Kenneth Birman, and Li Gong. "Integrating Security in a Group Oriented Distributed System." Proceedings 1992 IEEE Computer Society Symposium on Research in Security and Privacy. IEEE Computer Society, 1992.

[2] Satyanarayanan, Mahadev. "Integrating security in a large distributed system." ACM Transactions on Computer Systems (TOCS) 7.3 (1989): 247-280.

[3] Harinath, Depavath, P. Satyanarayana, and M. R. Murthy. "A review on security issues and attacks in distributed systems." Journal of Advances in Information Technology 8.1 (2017).

[4] Brown, Philip N., Holly P. Borowski, and Jason R. Marden. "Security against impersonation attacks in distributed systems." IEEE Transactions on Control of Network Systems 6.1 (2018): 440-450.

[5] Kumar, Manoj, and Nikhil Agrawal. "Analysis of different security issues and attacks in distributed system a-review." International Journal of Advanced Research in Computer Science and Software Engineering 3.4 (2013): 232-237.

[6] Mudholkar, P. K., and M. Mudholkar. "Security in distributed system." Proceedings of the International Conference and Workshop on Emerging Trends in Technology. 2010.

Relatedly, even when restricting to the LLM setting, I recently came across (but have not yet read in full) the paper "Prompt Infection: LLM-to-LLM Prompt Injection within Multi-Agent Systems" (arXiv:2410.07283), which seems closely related to this work. To the extent that it is, the authors of this paper should comment on the differences and similarities, including to any other relevant work that is referenced within the "Prompt Infection" paper.

We thank the reviewer for bringing this paper to our attention. Although it was uploaded to arXiv after the ICLR submission deadline, we have reviewed it to identify relevant distinctions. Notably, the "Prompt Infection" paper primarily explores scenarios such as data theft, malware propagation, and social manipulation, whereas our work focuses on tasks like code generation and mathematical problem solving. Additionally, their study does not examine how varying organizational structures within multi-agent systems influence outcomes, which is a key focus of our research.

As a small point, in line 156 it is claimed that it is not possible to use LLMs to inject syntax errors in 20% of the lines in some code, but I am somewhat suspicious of this assertion. Having personally used LLMs for very similar tasks in the past, it is my impression that SOTA models are can do a reasonable job of following such instructions (especially when combined with additional checks applied to the resulting code).

We appreciate the reviewer’s insight and acknowledge the potential of SOTA LLMs for similar tasks. To clarify, we conducted an analysis using AutoTransform to instruct a GPT-3.5 agent to introduce errors in 20% and 40% of the code lines. The results are summarized below:

These results indicate significant variability, with agents struggling to consistently achieve the precise error rates of 20% or 40%. This underscores the necessity and robustness of our AutoInject method, which addresses these limitations effectively.

We deeply appreciate your efforts in reviewing and your recognition of the importance of the research questions and the clear presentation of our paper. Your feedback has significantly improved our paper. In the response, we address your concerns one by one.

In several places it is not clear why the authors test some experimental configurations but not others. These absences may well be justifiable, but the authors should provide clear justification (and otherwise include the additional configurations, if only in the appendices). For example: In Figure 4 the authors only evaluate MAD. MAD is not evaluated in Figure 7a. In Figure 8 the authors only evaluate Camel. In several tables and bar charts it is not always clear what tasks are actually being evaluated or how much variation there is between these tasks. E.g. in Figure 5 it simply says "selected downstream tasks".

We appreciate the reviewer’s thoughtful feedback. Below, we clarify the rationale for our experimental configurations and address the specific concerns raised:

• Figure 4 (MAD): This figure focuses on a case study demonstrating a counter-intuitive phenomenon where introducing errors can improve performance—a rare observation in multi-agent systems. MAD was selected specifically for its relevance to this unique insight.
• Figure 7a (Exclusion of MAD): MAD was excluded from Figure 7a because this experiment involves scenarios with malicious instruction-sending agents, which are not present in the MAD system configuration.
• Figure 8 (Self-collab and Camel): Only Self-collab and Camel are included in Figure 8 because they represent the weaker systems within the Linear and Flat structures, respectively. Our objective in this experiment is to illustrate how our proposed defense method enhances resilience in weaker systems.

To provide greater clarity on our multi-agent system settings, we have added a comprehensive table summarizing the experimental configurations to our presentation, as shown below:

What does "Vanilla" mean in Figure 3 and elsewhere? In Figure 2 it seems as though the idea is that one agent is responsible for repeating(?) the task description and another for executing the task, but I assume it cannot be this simple. How does it generalise when there are more than two agents?

The term "Vanilla" refers to the baseline scenario where no attack or defense mechanisms are applied, representing a standard, unmodified system. In Figure 2, it specifically denotes the normal communication between agents without any adversarial influence or additional safeguards. This serves as a control setup to evaluate the impact of the proposed methods.

There are no error bars or standard errors reported anywhere, which makes it difficult to interpret the statistical significance of the results.

Thank you for highlighting this concern. While including error bars or standard errors would indeed provide additional statistical context, conducting repeated experiments for all tasks would incur significant time and resource constraints given the extensive scope of the study. However, the large number of test cases in each task ensures that our results are statistically robust and representative.

I thank the authors for their detailed reply, and I believe that most of my questions and comments have been addressed. I also appreciate the effort they put into running additional experiments. In light of this, I am happy to update my score to recommend acceptance if the authors can add the clarifying remarks in their rebuttal to the actual paper, even if only in the appendices. My questions came about even after a careful reading of the paper, and I noticed that other reviewers had similar questions, so I can only expect that future readers will too. Given that they have already done the hard work of typing the answers out, I would strongly suggest the authors add all of these clarifications to the actual manuscript.

Regarding the fault tolerance of distributed systems, I agree that some of the cited works mentioned are less directly relevant. I had in mind more the (vast) literature that explicitly considers the impact of network topology on robustness. I am no expert on this myself, but I believe this sometimes also falls under the complex systems literature. See, for instance, this Wikipedia page or this textbook. Even some of the very first things one learns in a distributed computing class is that, e.g. star networks can be less robust because they have a single point of failure, etc. Obviously I think it's important to study some of these things in the case of LLMs, but I want to make it clear that I do not view this more fundamental/theoretical aspect underlying the paper to be a novel contribution of the paper (and that is ok, as long as the authors do not claim novelty in this regard).

We deeply appreciate your efforts in reviewing and your recognition of the originality and significance of our paper. Your feedback has significantly improved our paper. In the response, we address your concerns one by one.

My main concern is that this paper attempts to do too much and is not sufficiently focused. Between the different multi-agent structures, different tasks, different attacks, different types of error rates, different error types, and different defenses, there are too many variables, each investigation ends up with limited depth, and the overall picture ends up not fully compelling. As a result of this ambition, details in the subquestions appear insufficiently investigated. For example, when discussing different multi-agent structures, I hoped to find more details about the structures and their dynamics, and more possible instantiations of each high-level structure (or, more systematic variation in the instantiations considered). Then the rest of the setup could be simplified (for example, it could focus on a single task category such as code generation, again possibly with more than one instantiation of the task category). The resulting claim would have to be more modest -- for example, it would pertain only to code generation and not any task -- but it would be much more strongly substantiated. As it stands (especially given the results do not seem particularly extreme), I'm left wondering if it is really the case that hierarchical structures are more resilient, or if the results apply only to the specific hierarchical systems tested and whether there is something particular about each of them that led to the results. I'm left unconvinced that the main claims of the paper are true.

Thank you for your thoughtful feedback. We recognize that the limited number of system instantiations in each structure may constrain the depth of our analysis. Our aim in this work was to offer a broad perspective on the factors influencing resilience in multi-agent systems as a foundation for future exploration. While this study focuses on providing a comprehensive overview, we acknowledge the importance of deeper investigation into specific structures and their dynamics. In future work, we plan to expand our evaluations to include more systematic variations and additional instantiations, such as AutoGen, to further substantiate our findings and address the concerns you raised.

A related general concern is that the lack of systematic ablations or closer analyses of the specific results made me quite doubtful of them. I think many additional experiments could have been very illustrative. For example, in the investigation of the defense methods, I was left wondering how much the relation between the defense methods and the attack methods mattered. I find it plausible that these "defense methods" are just generally useful enhancements to the multi-agent systems, and was interested in seeing results on the multi-agent systems with the "defense methods" even without the attack in place. In that case, the discussion of these results would be a bit different.

Thank you for your thoughtful suggestion. To address this concern, we conducted additional experiments to evaluate (1) the combination of Challenger and Inspector, (2) performance in “No Attack” scenarios, and (3) defense against AutoTransform attacks. The expanded results, including the previously reported Camel and Self-collab experiments, are summarized below:

The results show that while our defense methods significantly enhance resilience to attacks, they provide only marginal improvements in “No Attack” scenarios. This indicates that their utility is primarily in mitigating adversarial challenges, rather than as general system enhancements.

We deeply appreciate your efforts in reviewing and your recognition of our extensive experiments and the clear presentation of our paper. Your feedback has significantly improved our paper. In the response, we address your concerns one by one.

The proposed methods can be restricted and there is no guarantee whether the proposed two methods reflect (at least the majority types of) real-world attacks.

We appreciate the reviewer’s insightful comment. We acknowledge the diversity of real-world attack types, including DDoS and MITM. Our study focuses on simulating highly stealthy attacks—those that appear benign at first glance or are difficult for non-experts to detect. Specifically, we target scenarios where malicious content, such as a deliberately incorrect line of code, is embedded within seemingly innocuous messages. This approach aims to reflect a critical subset of real-world attacks that prioritize subtlety and evasion.

As the author pointed out, AutoTransform is convenient, yet hard to analyze. This inherently does not align with the objectives of the paper, because this method provide minimal added insights over AutoInject. It is thus not clear why an LLM-based approach is necessary and considered one of the contributions. A more principled automatic approach that attempts to capture different types of attacks can be interesting to explore.

Thank you for the insightful feedback. While we acknowledge that AutoTransform's reliance on LLM-generated outputs introduces challenges in control and analysis, its inclusion addresses a key limitation of AutoInject: the inability to replicate the inherent behaviors of LLMs. AutoInject-generated errors may not accurately reflect errors that LLMs themselves might produce in real-world scenarios. Furthermore, AutoTransform allows us to investigate whether LLMs can be guided to generate errors that are sufficiently covert to obfuscate malicious intent. This exploration aligns with our broader objective of understanding LLM vulnerabilities and highlights the necessity of a goal-driven approach to address complex attack dynamics.

While AutoInject seems more principal, whether P_m and P_e, the degree of error injected on the input side represents a good error rate metric is doubted, because even injecting the same number of errors per line can lead to different output behavior. For instance, in AutoInject, both injecting error only on a single line of code while b, changing it to (1) while b>=0 or (2) while True leads completely different results. In the latter case, if the agent running the code has no mechanism to jump out of infinite loop, this leads to catastrophic propogation of error to the entire system. In this example, it is clear the error in case (2) can be more dangerous, yet the provided error rate metric seems too trivial to capture it.

Thank you for highlighting this important consideration. We agree that different types of errors can have varied impacts on program functionality and may pose different challenges for detection. While our current metric—errors per line of code ($P_m$ and $P_e$)—is relatively simple, it provides a practical and interpretable approach akin to how lines of code are widely used as a baseline metric in software development despite the existence of more nuanced alternatives.

To address your concern regarding error diversity and severity, we further analyzed the distribution of error types generated by AutoInject. The errors span across seven distinct categories, as detailed below, ensuring diversity in the types of faults injected and reducing the bias of any single category dominating the results:

By incorporating a diverse range of errors and generating them at scale, AutoInject effectively captures the broad spectrum of fault types, mitigating the risk that specific critical cases—like infinite loops—are overlooked. This approach ensures that the reported error metrics, while simple, remain robust and representative of diverse error scenarios.