🤖 AI

Robust Multi-Agent LLMs under Byzantine Faults

This paper introduces Self-Anchored Consensus (SAC), a fully decentralized iterative filter-and-refine protocol that enables large language model multi-agent systems to robustly resist Byzantine faults and maintain reliable performance across diverse communication topologies without relying on vulnerable leader-based coordination or self-reported confidence.

Original authors: Haejoon Lee, Vincent-Daniel Yun, Hyeonho Oh, Dimitra Panagou, Sai Praneeth Karimireddy

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC0 1.0

Original authors: Haejoon Lee, Vincent-Daniel Yun, Hyeonho Oh, Dimitra Panagou, Sai Praneeth Karimireddy

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to solve a difficult puzzle together. They are all smart, but some are tired, some are confused, and unfortunately, one or two might be "troublemakers" trying to steer the group toward the wrong answer on purpose. This is the problem the paper tackles: How can a team of AI agents (digital "friends") work together to find the right answer when some of them are unreliable or malicious?

Here is a simple breakdown of the paper's story, using everyday analogies.

The Problem: The "Confidence" Trap

In the past, researchers tried to solve this by asking every AI agent to say, "How sure am I about my answer?"

The Flaw: Imagine a troublemaker in your friend group who is actually wrong about the puzzle but loudly shouts, "I am 100% sure I'm right!" The other friends, trusting that loud confidence, might change their minds and follow the wrong path.
The Paper's Finding: The authors show that relying on an agent's own report of how confident it is is a huge security hole. A malicious agent can easily lie about its confidence to trick the whole group.

The Solution: "Self-Anchored Consensus" (SAC)

The authors propose a new way of working called Self-Anchored Consensus (SAC). Instead of asking, "How sure are you?", the system asks, "How sure am I that your answer is right?"

Think of it like a Peer Review Party:

The Broadcast: Everyone writes down their answer to the puzzle and shares it with their neighbors.
The Local Judge: Instead of trusting the writer's confidence, every agent acts as a judge for its neighbors. It looks at the neighbor's answer and asks its own internal logic: "Does this make sense? Is it correct?" It gives the neighbor a score based on its own judgment.
The Filter (The "Bottom F" Rule): This is the most important part. If an agent has 5 neighbors, and it knows there might be up to 3 troublemakers (a concept called the "Byzantine" limit), it simply ignores the 3 lowest-scoring answers. It doesn't matter if the troublemaker shouted "I'm 100% sure!"—if the local judge thinks the answer is bad, it gets thrown out.
The Refine: The agent then takes its own answer and the remaining "good" answers from its neighbors to create a new, better answer.

The Safety Net: The "Robust" Network

For this system to work, the friends need to be connected in a specific way. The paper uses a mathematical concept called $(F+1)$ -robustness.

The Analogy: Imagine you are in a room with a group of people. If you want to be sure you aren't surrounded by liars, you need to make sure that even if you cut off your connections to the worst 3 people, you still have at least one honest person left to talk to.
The paper proves that if the network is designed with this specific "safety margin," the honest agents will always be able to find at least one good answer to hold onto, preventing the troublemakers from dragging the whole group down.

What Happened in the Experiments?

The researchers tested this on two types of puzzles: Math problems (like solving equations) and Commonsense questions (like "Is a tomato a fruit or a vegetable?").

The Old Way (CP-WBFT): When a troublemaker lied about their confidence, the whole group collapsed. The smart agents got confused and started giving wrong answers. The group's performance actually got worse than if they had just worked alone.
The New Way (SAC): The troublemakers were successfully filtered out.
- The Strong Agents: The smartest agents stayed smart. They didn't get dragged down by the noise.
- The Weak Agents: The less confident agents actually got better because they learned from the filtered, high-quality answers of their neighbors.
- The Result: The group reached the correct answer much more often, even with the troublemakers present.

The Bottom Line

This paper introduces a method where AI agents don't trust each other's "boasting" (self-reported confidence). Instead, they trust their own ability to judge their neighbors' work. By filtering out the worst answers and keeping the network connected in a specific, robust way, the group can stay on track and solve problems correctly, even when some members are trying to sabotage them.

In short: Don't listen to who shouts the loudest; listen to who has the best evidence, and make sure you have enough good friends around you to ignore the bad ones.

Technical Summary: Robust Multi-Agent LLMs Under Byzantine Faults

Problem Statement
Large Language Model (LLM) agents are increasingly deployed in peer-to-peer multi-agent systems (LLM-MAS) to solve tasks through collaborative consensus. However, these systems face a critical vulnerability: unreliable or Byzantine agents (those that are faulty due to hallucinations or adversarial due to intentional manipulation) can sway honest agents toward incorrect conclusions. Existing approaches, such as CP-WBFT, rely on agents self-reporting confidence scores to weight neighbor responses. This approach is fundamentally flawed because Byzantine agents can falsify their confidence scores to dominate the aggregation process. Furthermore, prior methods often lack principled communication topologies, leading to performance degradation that can be worse than operating without collaboration. The core challenge is to design a decentralized protocol where honest agents can iteratively refine their responses and reach correct consensus despite the presence of Byzantine agents that may inject arbitrary or misleading information.

Methodology: Self-Anchored Consensus (SAC)
The authors propose Self-Anchored Consensus (SAC), a fully decentralized, iterative filter-and-refine protocol. Unlike previous methods that trust sender-reported confidence, SAC shifts the evaluation burden to the receiver. The protocol operates in four stages per round:

Broadcast: Each agent broadcasts its current response to its neighbors.
Receiver-Side Scoring: Upon receiving neighbor responses, each agent $i$ independently computes an evaluation score $s_{i \to j}$ for each neighbor $j$ using its own LLM. This score is derived from a verification prompt assessing the correctness of the neighbor's response relative to the query, completely decoupling the score from any self-reported confidence by the sender.
Filtering: Agent $i$ identifies neighbors whose scores are strictly lower than its own self-score. It then discards the $F$ lowest-scoring neighbors from this set (where $F$ is the bound on the number of Byzantine neighbors). This step ensures that potentially malicious or low-quality inputs are removed before refinement.
Refinement: Agent $i$ refines its response by re-prompting its LLM with the original query, its current response, and the retained set of neighbor responses, weighted by their receiver-side scores.

Theoretical Framework and Topological Conditions
To guarantee that honest agents preserve reliable information, the authors leverage classical Byzantine-resilient consensus theory, specifically the Mean-Subsequence-Reduced (MSR) family of algorithms and $r$ -robustness.

$(F+1)$ -Robustness: The authors establish that if the communication graph $G$ $G$ is $(F+1)$ $(F + 1)$ -robust, the filtering mechanism ensures two critical properties:
1. Local Resilience: After filtering, every honest agent retains at least one neighbor whose response is at least as reliable as the minimum score among all reliable agents. This prevents Byzantine agents from corrupting the refinement process.
2. Global Connectivity: The subgraph induced by honest agents remains connected (specifically, it contains a rooted out-branching) even after filtering, ensuring that information propagates correctly across the network without fragmentation.
The paper proves that $(F+1)$ -robustness is a necessary condition to contain the influence of $F$ local Byzantine agents in this setting, offering a mathematically grounded alternative to ad-hoc topology selection.

Key Contributions

Self-Anchored Consensus (SAC): The introduction of a fully decentralized algorithm that replaces vulnerable sender-reported confidence with receiver-side evaluation and an MSR-inspired filtering mechanism tailored for natural language interactions.
Graph-Theoretic Guarantees: The establishment of $(F+1)$ -robustness conditions as the theoretical foundation for ensuring that non-Byzantine agents can contain Byzantine influence and converge to correct answers.
Empirical Validation: Demonstration that SAC effectively suppresses Byzantine influence across diverse communication topologies (MERG, Complete, Erdős–Rényi) and reasoning benchmarks, whereas prior methods collapse under adversarial conditions.

Experimental Results
The authors evaluated SAC on two challenging benchmarks: MATH500 (Level 4 symbolic reasoning) and Commonsense170k (heterogeneous commonsense reasoning). The setup involved $n=7$ agents (4 strong honest, 2 weak honest/faulty, 1 adversarial Byzantine) with $F=3$ .

Performance Degradation of Baselines: The baseline method, CP-WBFT, suffered catastrophic failure under Byzantine influence. On MATH500, it showed negative Byzantine Fault Tolerance Improvement (BFTI) ranging from $-10.4\%$ to $-24.8\%$ , meaning collaboration degraded performance below the agents' standalone capabilities. Strong agents were dragged down significantly (e.g., accuracy dropping from $84\%$ to $49\%$ ).
SAC Effectiveness: In contrast, SAC achieved positive BFTI ( $+3.8\%$ to $+7.6\%$ on MATH500) across all topologies. It successfully preserved the performance of strong agents while lifting the performance of weak agents.
Robustness Metrics: SAC maintained high "Honest Majority" (the fraction of queries where the majority of honest agents agree with the ground truth), reaching $83.3\%$ to $96.7\%$ on MATH500, compared to $36.7\%$ to $46.7\%$ for CP-WBFT.
Stability: Per-round analysis showed that CP-WBFT contamination occurred immediately in the first round and persisted, whereas SAC showed stable or improving accuracy over iterations without progressive degradation.

Significance and Claims
The paper claims that the primary vulnerability in current decentralized LLM collaboration is the reliance on sender-reported confidence, which creates an attack surface for adversarial manipulation. By shifting to receiver-side evaluation, SAC removes the ability of Byzantine agents to manipulate trust signals. Furthermore, the work highlights that topology design is not merely a heuristic but a mathematical necessity; satisfying $(F+1)$ -robustness is essential for containing Byzantine influence. The authors conclude that for decentralized LLM collaboration to be reliable, systems must integrate receiver-side trust evaluation with robustness-aware network topologies. The paper acknowledges limitations, noting that the current evaluation is restricted to static networks of small size ( $n=7, 9$ ) and single-turn responses, and that the robustness relies on the quality of the receiver's scoring function.