🤖 machine learning

Can AI Agents Agree?

This paper demonstrates that current large language model agents struggle to achieve reliable consensus in adversarial settings, with performance degrading as group size and Byzantine fault rates increase, primarily due to liveness failures like timeouts rather than value corruption.

Original authors: Frédéric Berdoz, Leonardo Rugli, Roger Wattenhofer

Published 2026-03-13

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Frédéric Berdoz, Leonardo Rugli, Roger Wattenhofer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.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 you have a group of very smart, very chatty robots (AI agents) tasked with a simple job: they all need to agree on a single number between 0 and 50.

It sounds easy, right? If you ask five people to pick a number, they might eventually settle on one. But this paper asks a scary question: What happens when these robots are trying to agree, but some of them are liars, confused, or just stubborn?

Here is the story of what the researchers at ETH Zurich discovered, explained simply.

🎭 The Setup: A Game of "Pick a Number"

The researchers set up a digital room where a group of AI agents (using models like Qwen3) talk to each other in rounds.

The Goal: Everyone must eventually shout out the same number.
The Rules: They can talk, change their minds, and vote on when to stop.
The Twist: Some agents are "Honest" (they just want to agree). Others are "Byzantine" (a fancy term for "malicious"). These bad agents don't care about the number; their only goal is to prevent the group from ever agreeing.

📉 The Big Discovery: "We Can't Even Agree When Everyone is Nice"

The most surprising part of the paper isn't about the liars; it's about the honest robots.

Even when zero bad agents were in the room, the group often failed to agree.

The "Group Size" Problem: When there were only 4 robots, they managed to agree about half the time. But when the group grew to 16 robots? They almost never agreed. It's like trying to get a small family to decide on dinner vs. trying to get a whole stadium to decide on a song. The more people you add, the more chaotic the conversation gets.
The "Paranoia" Problem: The researchers tried a trick: they told the honest robots, "Hey, there might be a liar in the room!" Even if there wasn't a liar, just mentioning the possibility made the honest robots more anxious and slower. They spent so much time worrying about potential traps that they never actually finished the game.

🛑 The "Liveness" Issue: Stalling vs. Breaking

When the group did fail, it wasn't usually because the bad robots tricked them into picking a "wrong" number (like 42 instead of 10).

The Real Problem: The group just stalled. They got stuck in an endless loop of talking, changing their minds, and never hitting the "Stop" button.
The Analogy: Imagine a committee meeting where everyone is so afraid of making a mistake that they keep saying, "Let's discuss this more," and the meeting never ends. The paper calls this a loss of "liveness." The system is alive, but it's not doing anything.

🤖 The "Liar" Effect

When the researchers actually added the bad (Byzantine) agents:

One bad apple spoils the bunch: Adding just one liar to a group of eight honest robots caused the success rate to crash.
The Liar's Strategy: The liars didn't need to be clever. They just needed to be confusing. By throwing out random numbers or refusing to vote "stop," they kept the honest robots in a state of confusion. The honest robots couldn't tell if the group was close to agreeing or if they were being tricked, so they just kept talking forever.

💡 The Takeaway: "AI Agents Are Not Ready for Teamwork"

The paper concludes with a warning for the future. We are building AI systems where multiple agents work together to write code, plan trips, or manage networks. We assume they will be able to coordinate.

This study says: Not yet.

They are too sensitive to group size.
They get paralyzed by the mere idea of danger.
They are easily stalled by even a single confused or malicious participant.

The Metaphor:
Think of current AI agents like a group of brilliant but highly anxious students in a study group. If you ask them to solve a math problem together, they might get it done if the group is small and everyone is calm. But if you add a few students who are just there to mess around, or if you tell the group "Someone might be cheating," the whole study session turns into a chaotic, endless argument where no one ever finishes the homework.

The Bottom Line: Before we trust AI agents to make critical decisions together (like in self-driving cars or financial markets), we need to teach them how to actually agree without falling apart. Right now, they are still learning how to hold a conversation without shouting over each other.

1. Problem Statement

The paper investigates the reliability of Large Language Model (LLM) agents in reaching Byzantine consensus within a multi-agent system. While LLMs are increasingly deployed as cooperative agents for planning and reasoning, their ability to reach a common decision in adversarial or even benign settings remains unproven.

The authors focus on a scalar consensus game where:

Goal: A group of agents must agree on a single integer value.
No-Stake Setting: Agents have no inherent preference for the final value; the objective is purely agreement (validity and liveness), not value optimization.
Adversarial Context: The study introduces Byzantine agents (malicious actors) that attempt to disrupt consensus, testing if LLM groups can tolerate faults similar to classical distributed systems.

2. Methodology

Experimental Setup

Simulation Environment: The authors developed A2A-Sim, a synchronous all-to-all network simulator.
Agents: $N$ agents communicate in rounds $t = 1 \dots T_{max}$ (where $T_{max} = 50$ ).
Models: Experiments utilized the Qwen3-8B and Qwen3-14B model families.
Group Sizes: $N \in \{4, 8, 16\}$ .
Byzantine Fraction: A fraction $f \in [0, 1/3]$ of agents are Byzantine ( $B = f \cdot N$ ).
Initialization: Honest agents start with a random integer in $[0, 50]$ . Byzantine agents have no initial value and can propose arbitrary values.

Protocol Mechanics

Broadcast: Agents propose a scalar value and a textual justification.
Receive: Agents receive messages from all peers.
Vote: Agents decide to vote (stop) or continue.
Termination: The game ends if $\ge 2/3$ $\geq 2/3$ of all agents vote to stop.
- Valid Consensus: All honest agents hold the same value, and that value was one of their initial proposals.
- Invalid Consensus: Agreement reached but violates validity (e.g., wrong value).
- No Consensus: Timeout occurs ( $T_{max}$ reached) or liveness is lost.

Threat Model

The Byzantine agents are restricted to a specific behavior:

They can propose arbitrary values and justifications.
They can adapt to history.
Restrictions: They cannot equivocate (send different messages to different recipients), forge identities, or drop messages. They must broadcast the same message to all peers.

Prompting Strategy

The study compared two prompt variants for honest agents:

Adversary-Aware: Explicitly warned that Byzantine agents might exist.
Adversary-Free: No mention of potential malicious actors.

3. Key Contributions

Capability Study: A systematic evaluation of LLM consensus in benign settings, revealing that agreement is not an emergent capability even without adversaries.
Robustness Analysis: Demonstration that the presence of even a single Byzantine agent causes a catastrophic collapse in consensus success rates.
Failure Mode Analysis: Identification that failures are dominated by liveness loss (timeouts, stalled convergence) rather than safety violations (value corruption).

4. Key Results

A. Performance in Benign Settings ( $B=0$ )

Low Success Rate: Even without Byzantine agents, only 41.6% of runs resulted in valid consensus.
Model Scaling: Qwen3-14B significantly outperformed Qwen3-8B (67.4% vs. 15.8% valid consensus in optimal conditions), but both suffered high timeout rates.
Group Size Effect: Increasing group size degraded performance. Valid consensus dropped from 46.6% ( $N=4$ ) to 33.3% ( $N=16$ ).
Prompt Sensitivity: Removing mentions of Byzantine agents from the prompt improved Qwen3-14B performance from 59.1% to 75.4% valid consensus and halved the convergence time. This suggests that the suggestion of adversarial presence harms liveness even when none exists.

B. Performance with Byzantine Agents

Liveness Collapse: Introducing even one Byzantine agent ( $B=1$ ) drastically reduced valid consensus.
Nature of Failure:
- Invalid Consensus (Safety): Remained rare (<5%). Byzantine agents rarely succeeded in forcing the group to agree on a "wrong" value.
- No Consensus (Liveness): This was the dominant failure mode. Byzantine agents successfully prevented the group from ever reaching a stopping condition, causing timeouts.
Trajectory Analysis: Visualizations showed that Byzantine agents caused proposal trajectories to oscillate or stall, preventing the "clustering" of values necessary for agreement.

5. Significance and Conclusion

Fragility of Coordination: The study concludes that reliable agreement is not yet a dependable emergent capability of current LLM-agent groups. Even in simple, no-stake scalar tasks, agents frequently fail to coordinate.
Liveness vs. Safety: The primary risk in LLM consensus is not that agents will agree on a malicious value (safety), but that they will fail to agree at all (liveness). This is critical for applications requiring robust coordination.
Scalability Issues: Performance degrades as the group size increases, suggesting that current LLM architectures struggle with the complexity of multi-agent state tracking and negotiation.
Implications: Deployments relying on LLM agents for safety-critical coordination, delegation, or autonomous decision-making should exercise extreme caution. Current models lack the robustness required for Byzantine fault tolerance.

Future Work: The authors suggest investigating diverse adversarial strategies, heterogeneous agent populations, and larger-scale deployments to further understand the limits of AI agent agreement.