Can AI Agents Agree

Executive Summary: This paper investigates whether LLM-based agents can reliably reach consensus in a “no-stake” scalar agreement game, even in the presence of Byzantine (malicious) agents. Using Qwen3-8B and 14B models, the authors find that reliable agreement is NOT a dependable emergent capability; success rates are low even in benign settings and collapse completely when even a single Byzantine agent is introduced. Failures are primarily due to loss of liveness (timeouts/stalled convergence) rather than value corruption.

---

High-Level Overview

• The paper explores the robustness of LLM-based multi-agent systems in adversarial consensus settings. While LLMs are increasingly used for collaboration, their ability to coordinate and agree on a value—especially when some participants are intentionally disruptive—is critical for safety-critical deployments. The study uses a controlled simulation to see if agents can converge on a single value when they have no specific preference for what that value is.

Problem Statement

Traditional Byzantine Fault Tolerant (BFT) consensus provides strong guarantees for deterministic algorithms, but it is unclear if these translate to stochastic, prompt-driven LLMs. The core problem is determining if LLM agents can maintain liveness (eventually reaching a decision) and validity (agreeing on a value that was actually proposed by an honest agent) in the face of adversarial behavior.

Core Approach / Architecture

The authors developed A2A-Sim, a synchronous all-to-all simulation:

• The Game: $N$ agents propose scalar values $v \in [0, 50]$.
• Honest Agents: Initialize with a random value; attempt to converge via iterative proposals and justifications.
• Byzantine Agents: Have no initial value; strategically propose values to disrupt agreement.
• Termination: The game stops if $\ge 66\%$ of agents vote “stop” or if it reaches $T_{max} = 50$ rounds.
• Outcome Metrics:
  • Valid Consensus: All honest agents agree on a value from the initial honest set.
  • Invalid Consensus: Termination occurs, but honest agents do not agree or agree on a corrupted value.
  • No Consensus: The simulation times out.

Evaluation Results

Tests were conducted using Qwen3-8B and Qwen3-14B:

• Benign Settings ($B=0$):
  • Valid consensus is unreliable. Qwen3-14B achieved $\sim 67.4\%$ success, while Qwen3-8B only $\sim 15.8\%$.
  • Success degrades as group size $N$ increases (from $N=4$ to $N=16$).
  • Prompt Effect: Mentioning that Byzantine agents might exist actually harmed liveness, reducing Qwen3-14B’s success from $75.4\%$ to $59.1\%$.
• Adversarial Settings ($B > 0$):
  • Even a single Byzantine agent significantly reduces the likelihood of valid consensus.
  • Invalid consensus (value corruption) remained rare; instead, the system suffered from liveness loss (timeouts).

Key Findings and Insights

1. Liveness is the Bottleneck: LLM agents don’t usually get “tricked” into the wrong value; they simply fail to stop talking and agree before the deadline.
2. Scale Fragility: Consensus success decreases as the number of agents increases, suggesting poor scalability for emergent coordination.
3. Paranoia Penalty: Warning agents about potential adversaries makes them less efficient at reaching agreement even when no adversaries are present.
4. Model Size Matters: Larger models (14B vs 8B) are significantly better at coordination but still far from reliable.

Limitations

• Tested only one family of models (Qwen3) and two sizes.
• Used a restricted Byzantine model (no equivocation—agents must send the same message to everyone).
• Only a single Byzantine strategy was tested.

How It Relates to Prior Work

Unlike previous studies on “negotiation” where agents have preferences/stakes, this study removes stakes to isolate the pure mechanism of agreement. It aligns with recent findings (e.g., Wolf et al., 2025) that a single deceptive agent can nullify the gains of multi-agent systems.

TL;DR

LLM agents are not yet reliable social decision-makers. Even without a “stake” in the outcome, they struggle to reach agreement as group size grows, and a single malicious actor can easily stall the entire process, leading to timeouts rather than incorrect decisions.