[ETH Zurich] Can AI Agents Agree? The Fragility of LLM Consensus

TL;DR

Even in the simplest "no-stake" scenarios, AI agents struggle to reach a consensus. A new study from ETH Zurich demonstrates that as the number of agents grows, the probability of agreement plummets. More alarmingly, adding just one malicious "Byzantine" agent—who strategically acts to disrupt the group—can completely paralyze the decision-making process, leading to perpetual stalls rather than reached agreements.

The Consensus Crisis: Why This Matters

For years, we have envisioned a future where "swarms" of LLM-based agents (like AutoGen or ChatDev) work together to write code, manage supply chains, or govern decentralized autonomous organizations (DAOs). However, these systems rely on a fundamental assumption: that the agents can actually agree on a state.

In classical computer science, Byzantine Fault Tolerance (BFT) defines the ability of a system to reach consensus even if some nodes are failing or malicious. The authors of "Can AI Agents Agree?" argue that while we have math for deterministic algorithms, we have almost no understanding of how stochastic, prompt-influenced LLMs behave when the "Byzantine" threat is real.

Methodology: The A2A-Sim Framework

The researchers created A2A-Sim, a synchronous simulator where $N$ agents attempt to agree on a scalar value (0-50).

• The Protocol: Agents propose a value and a "justification" text.
• The Goal: Reach a supermajority (66%+) "stop" vote where all honest agents hold the same initial value.
• The Twist: A fraction of agents ($f$) are "Byzantine," meaning they are prompted to disrupt the consensus while appearing cooperative.

Figure 1: The all-to-all communication structure of the A2A-Sim game.

Key Insights: Why Agents Fail

The study produced three counter-intuitive findings that challenge the current optimism regarding multi-agent systems:

1. Scale is the Enemy of Agreement

One might expect more agents to provide more "wisdom of the crowd." Instead, larger groups (N=16) were significantly less likely to reach consensus than smaller ones (N=4). The "noise" of multiple justifications makes convergence harder for the LLM's limited context window.

2. "Liveness" vs. "Validity"

In typical BFT research, the fear is Value Corruption (the traitor tricks everyone into agreeing on a bad value). However, LLM agents suffer from Liveness Loss: they simply stop making progress. They enter "infinite loops" of negotiation or time out because they cannot resolve minor differences in proposals.

3. The Paradox of Awareness

The researchers tested two prompt styles: one where agents were warned about potential traitors, and one where they were told everyone was honest. Surprisingly, warning agents about traitors made performance worse, even when no traitors were present. The "paranoia" introduced by the prompt led honest agents to second-guess each other, stalling the consensus.

Figure 2: Performance metrics showing how larger group sizes and "adversary-aware" prompts degrade success rates.

Experimental Results

Using the Qwen3-8B/14B family, the researchers showed a stark contrast in robustness. While the 14B model is more "competent" at reaching consensus in benign settings, its performance collapses the moment a Byzantine agent is introduced.

Figure 3: Success rate of Qwen3-14B with 8 honest agents. Note how the "valid consensus" (blue) disappears as the number of Byzantine agents increases.

Critical Analysis: The Road Ahead

The "no-stake" nature of this study is its most profound takeaway. If agents cannot agree even when they have nothing to lose, how can we expect them to coordinate in financial, legal, or military contexts where strategic incentives are much stronger?

Limitations:

• The study only used one model family (Qwen3).
• The Byzantine strategy was relatively simple (no identity forging or message dropping).

Conclusion: The industry's move toward "Agentic Workflows" needs a reality check. We cannot rely on the "natural intelligence" of LLMs to solve the consensus problem. Future robust multi-agent systems will likely require a hybrid approach: using LLMs for reasoning, but anchoring their decisions in classical, verifiable cryptographic or consensus protocols.