Technical Summary: Byzantine Cheap Talk in LLM Coordination Games

1. Problem Statement

Multi-agent Large Language Model (LLM) systems increasingly rely on communication protocols for coordination, yet their robustness under adversarial deception and structural constraints remains poorly understood. While prior work established that "cheap talk" (costless, non-binding pre-play communication) can resolve coordination dilemmas like the Stag Hunt by establishing focal points, these findings assume honest signaling and unrestricted communication.

This paper investigates two specific vulnerability classes in multi-agent LLM coordination:

1. Byzantine Deception: Whether coordination can be sustained when an agent signals cooperation but strategically defects (Byzantine behavior).
2. Topology Effects: Whether the benefits of cheap talk persist when communication visibility is restricted, and crucially, whether the agents' awareness of these restrictions affects outcomes.

The study focuses on a 4-player Stag Hunt game, where the payoff structure requires unanimity for the highest reward, making the system highly sensitive to single-agent defection.

2. Methodology

Experimental Setup

• Game: A 4-player Stag Hunt with two stages per round: (1) a communication stage where agents broadcast a single non-binding word, and (2) an action stage where agents choose "Hunt Stag" (cooperate) or "Hunt Hare" (defect).
• Payoffs:
  • 10 points if all 4 choose Stag.
  • 3 points if an agent chooses Hare.
  • 0 points if an agent chooses Stag while any other chooses Hare.
• Protocol: Each trial consists of 5 rounds with the same group of agents. Agents observe the full history of messages, actions, and payoffs within a trial. Trials are independent (fresh prompts, no cross-trial memory).
• Models: Six heterogeneous LLM families were tested (Mixtral-8x22B, Qwen2.5-72B, Llama-3.3-70B, DeepSeek-V3, GPT-4o, Claude Sonnet 4.6) across 720 trials.

Conditions

1. Hard Byzantine ($k \in \{0, 1, 2\}$): $k$ agents deterministically broadcast "Stag" but always choose "Hare."
2. Soft Byzantine ($k=1, p=0.5$): The adversary defects with probability 0.5.
3. Topology Restrictions:
   • Explicit: Agents are informed of visibility constraints (Broadcast, Ring, Star).
   • Silent: The same visibility constraints are applied, but agents receive no cues about them (e.g., player count removed from prompts).
4. Interaction: Star topology combined with a Byzantine agent (either as the hub or a spoke).

Metrics

• Group Cooperation Rate ($\Phi$): Percentage of rounds where all agents choose Stag.
• Non-Byzantine Cooperation Rate ($\rho_{nb}$): Percentage of Stag choices among non-adversarial agents.
• Average Payoff ($\bar{u}$): Mean per-round payoff for non-Byzantine agents.

3. Key Contributions and Results

A. Byzantine Vulnerability and Behavioral Archetypes

• Total Collapse of Group Coordination: A single deterministic Byzantine agent ($k=1$) eliminates group cooperation entirely ($\Phi = 0\%$).
• Detection vs. Adaptation: Non-Byzantine agents detect the betrayal within one round (by observing the mismatch between the "Stag" signal and "Hare" action). However, they fail to adapt collectively. Approximately 50% of non-Byzantine agents continue to cooperate despite repeated exploitation.
• Two Stable Behavioral Archetypes: The paper identifies two distinct, stable behavioral patterns across model families:
  1. Defection-Prone (DP): Models (e.g., Mixtral, DeepSeek, GPT-4o) that permanently switch to defection after detecting betrayal. These models earn significantly higher individual payoffs (2.42/round) under adversarial conditions.
  2. Cooperation-Persistent (CP): Models (e.g., Qwen, Llama) that continue attempting to cooperate despite exploitation. These models suffer significantly lower payoffs (0.45/round), incurring a "cooperation tax" of 5.4x compared to DP models.
• Soft Byzantine: When the adversary defects probabilistically ($p=0.5$), group cooperation partially survives (12%), and the payoff gap between DP and CP models compresses (2.6x), as CP models occasionally succeed in coordinating with the adversary.

B. Topology and Meta-Reasoning

• Explicit vs. Silent Topology:
  • Explicit: Restricting visibility (Ring or Star) and informing agents of these constraints collapses cooperation to near-zero levels, even without any Byzantine agents.
  • Silent: Applying identical restrictions without informing agents preserves near-perfect cooperation (100% in Ring/Broadcast, 88% in Star).
• Mechanism: The failure in explicit conditions stems from meta-reasoning. When agents are told they have limited visibility, they infer the existence of unseen players with unknown intentions, triggering strategic uncertainty. In silent conditions, agents take visible messages at face value.
• Interaction: Combining Byzantine agents with restricted topologies (e.g., Star) compounds the damage, reducing non-Byzantine cooperation to 13–28%, significantly lower than the 50% observed in broadcast Byzantine scenarios.

C. Robustness and Stability

• Cross-Cohort Consistency: The DP/CP archetype split remains stable across different model cohorts (including GPT-4o and Claude Sonnet) and group sizes ($n=2$ to $n=6$).
• Preemptive Defection: GPT-4o exhibited a unique behavior in some cohorts: preemptive defection (choosing Hare from Round 1 before any betrayal occurs), yet it still functionally classified as DP once betrayal occurred.
• Qwen Exception: Qwen was the only model consistently classified as Cooperation-Persistent across all tested cohorts and group sizes.

4. Significance and Implications

The paper reframes multi-agent LLM coordination failures as concrete security vulnerabilities rather than abstract game-theoretic phenomena:

1. Byzantine Cheap Talk as Adversarial Injection: A Byzantine agent acts as a vector for adversarial prompt injection. Unlike direct prompt attacks, this exploits the "social inference layer," where agents update beliefs based on false signals. The unanimity payoff structure makes the system fragile: even a single agent's defection guarantees failure, and residual doubt prevents recovery.
2. Topology as an Attack Surface: Disclosing network architecture to agents can degrade performance. Systems that expose agent roles or communication graphs may inadvertently induce strategic uncertainty that collapses coordination, even in the absence of adversaries.
3. The Alignment Tax: Models trained or aligned to be prosocial and cooperative (CP models) are systematically exploitable by adversarial peers. Optimizing for cooperative behavior in isolation may create agents that perform well individually but fail collectively in adversarial environments, paying a disproportionate penalty (5.4x lower payoff) compared to self-interested (DP) models.

The authors conclude that while cheap-talk coordination is effective under standard conditions, it is fragile along axes of adversarial deception and structural transparency. These findings highlight the need for verification mechanisms in multi-agent frameworks to ensure robustness against both malicious actors and structural uncertainties.