Why do multi-agent systems fail to coordinate at scale?

AgentsNet is a benchmark that applies classical distributed computing problems (graph coloring, leader election) to LLM multi-agent systems. The setup uses the LOCAL model: synchronous rounds, each agent communicates only with immediate neighbors, decisions based exclusively on locally aggregated information. This is the most fundamental distributed coordination setting.

Three findings reveal how LLM agents behave as distributed systems:

Finding 1: Strategy coordination is the essential challenge. Agents fail to coordinate in two distinct ways: (a) they agree on a common strategy too late during message-passing, leaving insufficient rounds for implementation, and (b) they assume a strategy in their initial chain-of-thought and follow it throughout without informing neighbors — private reasoning that never becomes shared coordination.

Finding 2: Agents generally accept neighbor information uncritically. When neighbors share information about the network, proposed strategies, or candidate solutions, agents accept it without verification. This enables effective coordination when information is correct, but propagates errors when agents share incorrect assumptions about network topology or ineffective strategies.

Finding 3: Agents can detect and resolve inter-neighbor inconsistencies. Despite uncritical acceptance, agents demonstrate capability to detect conflicting solutions (e.g., conflicting color assignments) between neighbors and assist in resolving them. This reactive error detection contrasts with the proactive error propagation in Finding 2.

Frontier LLMs demonstrate strong performance for small networks but fall off as network size scales. The benchmark supports up to 100 agents and is practically unlimited in size, designed to scale with future model generations.

The connection to Why do multi-agent LLM systems converge without genuine deliberation? is direct: uncritical acceptance of neighbor information is the distributed-systems manifestation of silent agreement. Agents converge on shared solutions without genuine deliberation, whether through accepting neighbor assertions (AgentsNet) or through premature convergence in debate rounds (silent agreement).