Robust Multi-Agent LLMs under Byzantine Faults
Haejoon Lee, Vincent-Daniel Yun, Hyeonho Oh, Dimitra Panagou, Sai Praneeth Karimireddy · 2026
Read Robust Multi-Agent LLMs under Byzantine Faults by Haejoon Lee, Vincent-Daniel Yun, Hyeonho Oh, Dimitra Panagou, Sai Praneeth Karimireddy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-09076.txt.
Introduction
Haejoon Lee and three co-authors study teams of language model agents that check each other's work over a network. Such teamwork can raise reliability, but it also opens the door to faulty or hostile agents that spread wrong answers through the group.
Their protocol, Self-Anchored Consensus, has each agent swap answers with peers, filter out messages that look unreliable, and refine its own answer, with no central controller. The authors give conditions on the network shape under which honest agents keep and spread sound information despite the bad actors. Across math and common-sense tests with many models, the method held up under attack where earlier methods fell apart.
Catalog record
| CREATOR | Haejoon Lee, Vincent-Daniel Yun, Hyeonho Oh, Dimitra Panagou, Sai Praneeth Karimireddy |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.09076
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robust Multi-Agent LLMs under Byzantine Faults Haejoon Lee, Vincent-Daniel Yun, Hyeonho Oh, Dimitra Panagou, Sai Praneeth Karimireddy Abstract Large language model (LLM) agents increasingly collaborate over peer-to-peer networks to improve their reliability. However, these same interactions can also become a source of vulnerability, as unreliable or Byzantine agents may sway neighboring agents toward incorrect conclusions and degrade overall system performance. Existing methods rely on leader-based coordination or self-reported confidence, both of which are susceptible to adversarial manipulation. We study decentralized LLM multi-agent systems (LLM-MAS) and propose Self-Anchored Consensus (SAC), a fully decentralized iterative filter-and-refine protocol in which agents iteratively exchange responses, locally evaluate and filter unreliable messages, and refine their own outputs. We present ( F + 1 ) (F{+}1) -robustness conditions for the communication graph that ensure honest agents preserve and propagate reliable information despite Byzantine influence. Experiments on mathematical and commonsense reasoning benchmarks show that SAC effectively suppresses Byzantine influence and consistently improves performance across diverse communication topologies, whereas prior methods degrade under adversarial conditions. 1 Introduction Large language models (LLMs) are increasingly deployed as communicating agents in multi-agent systems (MAS), where multiple agents exchange intermediate responses, critique one another, and converge on a collective answer ( 4 ; 2 ) . We consider a setting in which LLM agents are connected over a peer-to-peer communication network and aim to solve tasks with objectively verifiable correct answers through consensus. As these systems move into real-world deployment, a central challenge is robustness to faulty and adversarial agents. This concern parallels broader efforts to ensure trustworthy and reliable AI in high-stakes domains ( 26 ) , where uncertainty and unreliability of model outputs directly affect downstream consequences. Individual LLM agents make mistakes : they hallucinate, miscalculate, and mis-apply safety judgments, and some may behave adversarially , injecting strategically crafted responses. Since each agent cannot locally distinguish trustworthy messages from Byzantine messages (shown in Fig. 1 ), such behavior can contaminate otherwise reliable agents. The practical question is therefore whether the system can contain the influence of unreliable agents so that reliable agents preserve their base capability. Figure 1: Decision ambiguity in the presence of Byzantine agents. An agent must decide which responses to trust despite adversarial and indistinguishable neighbor messages. A natural analogue arises through the classical Byzantine-resilient consensus , where a subset of nodes may behave arbitrarily while honest nodes must still reach correct agreement ( 9 ; 10 ; 17 ) . This framework captures the failure modes of an LLM agent that shares an incorrect response, whether unintentional (hallucinations, reasoning failures) or intentional (adversarial manipulation, jailbreaking); from the perspective of other agents, such deviations are indistinguishable from Byzantine faults. Viewing LLM-MAS through this lens makes two structural questions unavoidable: (i) how should agents determine which neighbors’ responses to trust in each round, and (ii) how should the communication graph be designed to limit the influence of Byzantine agents. A recent approach, CP-WBFT ( 29 ) , has each agent attach a self-reported confidence score and aggregates neighbors’ outputs by upweighting high-confidence agents. Two design choices limit its usage. First, “Byzantine” agents are still assumed to report honest confidence scores, departing from the standard Byzantine model in which agents may inject falsified confidence. Second, the communication graph is chosen ad hoc from a small set of generic topologies (e.g., chain, star, tree), without a principled connection to fault-tolerance guarantees, so performance varies significantly across topologies, with some yielding worse performance than no collaboration at all ( 29 ) . We address these limitations by drawing on classical Byzantine-resilient consensus. The Mean-Subsequence-Reduced (MSR) family of algorithms ( 8 ) performs a trimmed mean over neighbor messages, while 10 establish r -robustness as a topological condition ensuring consensus under Byzantine faults. To our knowledge, these tools have not been brought to LLM-MAS. We do so here: we replace sender-reported confidence with receiver-side evaluations computed independently by each agent, and introduce an MSR-inspired filter-and-refine mechanism that selectively aggregates neighbor messages via re-prompting. We then design and analyze a communication network under which honest agents remain robust to Byzantine influence. Contributions. Our contributions are twofold. First, we introduce sac ( sac ), an MSR-inspired algorithm that ensures honest LLM agents remain robust to a bounded number of Byzantine agents while iteratively refining their responses via receiver-side confidence evaluation and a filter-and-refine update tailored to natural-language interactions. Second, we leverage r -robustness to establish graph-theoretic conditions under which non-Byzantine agents contain Byzantine influence under sac . We further show through simulations that our method preserves honest-agent capability under Byzantine faults across varying communication topologies, whereas baseline approaches collapse catastrophically. 2 Related Works LLM multi-agent systems. Multiple LLM instances coordinated as agents have been shown to outperform single-agent inference through debate ( 2 ; 13 ) and role-based frameworks ( 21 ; 5 ; 4 ) . A growing body of work studies the reliability cost when such agents behave incorrectly ( 19 ; 24 ; 27 ) . Our work takes this failure mode as its starting point and asks what aggregation rule and graph structure are needed to contain it. Byzantine-robust consensus in LLM-MAS. Three recent methods are closest to ours. CP-WBFT ( 29 ) relies on self-reported confidence to select high-confidence responses, implicitly assuming Byzantine agents would honestly report their confidence. It also evaluates their method across the six hand-picked graphs, with wildly varying performance. Trusted MultiLLMN ( 15 ) uses a leader-based BFT protocol in which consecutive Byzantine leaders force expensive re-elections. DecentLLMs ( 7 ) removes the leader via a geometric-mean filter over evaluator scores, which is brittle under high-variance scoring and requires a fully-connected evaluator-worker graph. Our method differs on two axes at once: confidence is computed on the receiver side, so Byzantine agents cannot manipulate how others evaluate their output; and our communication topology is grounded on mathematically-driven robustness properties that limit Byzantine influence on any general graph. Classical Byzantine-resilient algorithms. The Byzantine agreement problem ( 9 ; 1 ) has been extensively studied to ensure reliability under arbitrary node failures, inspiring a broad line of work on fault-tolerant distributed computation. In particular, the Weighted Mean-Subsequence-Reduced (W-MSR) algorithm, together with r - and (r,s) -robustness conditions ( 10 ) , provides consensus guarantees despite Byzantine agents. These notions have since been extended beyond consensus to distributed optimization ( 18 ; 25 ) and distributed learning ( 22 ; 23 ) , with applications robotics and smart grids ( 11 ; 25 ) . To our knowledge, this work is the first to bring MSR-type algorithms and robustness conditions into LLM-MAS. 3 Problem Setup 3.1 LLM Multi-Agent System We consider a multi-agent system of n LLM agents, indexed by \mathcal{V}=\{1,\dots,n\} , collaboratively answering a query x drawn from a task distribution \mathcal{D} . Agents exchange messages over an undirected, time-invariant communication graph \mathcal{G}=(\mathcal{V},\mathcal{E}) , where an edge (i,j)\in\mathcal{E} indicates that agents i and j can exchange their responses. The neighbor set of agent i is denoted by \mathcal{N}_{i}=\{j\in\mathcal{V}\mid(i,j)\in\mathcal{E}\} . We additionally consider a directed graph \mathcal{G}^{\prime}=(\mathcal{V},\mathcal{E}^{\prime}) , where a directed edge (i,j)\in\mathcal{E}^{\prime} indicates that agent j can receive responses from agent i . A directed graph contains a rooted out-branching if it has a node p\in\mathcal{V} that can