PaperlayerView exact revision on arXiv

Source-linked AI summary

AgentsNet: Coordination and Collaborative Reasoning in Multi-Agent LLMs

Florian Grötschla, Luis Müller, Jan Tönshoff, Mikhail Galkin, Bryan Perozzi

arXiv:2507.08616v1cs.MAcs.LG

TL;DR

AGENTSNET addresses the lack of benchmarks for whether multi-agent LLM systems can coordinate, communicate, and exploit network structure at scale. It builds a distributed-computing benchmark with five graph-based tasks, scalable message passing, and evaluations reaching 100 agents. Frontier models perform strongly on some small-network settings but face challenging tasks and broader scalability demands.

  • Problem

    Existing multi-agent benchmarks do not explicitly assess structured coordination, decentralized communication, and collaborative reasoning across scalable network topologies.

  • Method

    AGENTSNET evaluates graph coloring, minimal vertex cover, maximal matching, leader election, and consensus using scalable message passing across varied graph instances and sizes.

  • Results

    Frontier models are compared on AGENTSNET, which evaluates graphs from 4 to 16 nodes and scales the setup to 100 agents; even the best models find the tasks challenging.

  • Takeaways & Limitations

    AGENTSNET provides a practically scalable way to study how multi-agent LLMs coordinate, communicate, and self-organize as network size and problem complexity increase.

  • Takeaways & Limitations

    The implementation uses synchronous LOCAL message passing and JSON answer parsing, although the authors characterize these as replaceable implementation choices rather than limitations inherent to AGENTSNET.

Abstract

from arXiv · show

Large-language models (LLMs) have demonstrated powerful problem-solving capabilities, in particular when organized in multi-agent systems. However, the advent of such systems also raises several questions on the ability of a complex network of agents to effectively self-organize and collaborate. While measuring performance on standard reasoning benchmarks indicates how well multi-agent systems can solve reasoning tasks, it is unclear whether these systems are able to leverage their topology effectively. Here, we propose AgentsNet, a new benchmark for multi-agent reasoning. By drawing inspiration from classical problems in distributed systems and graph theory, AgentsNet measures the ability of multi-agent systems to collaboratively form strategies for problem-solving, self-organization, and effective communication given a network topology. We evaluate a variety of baseline methods on AgentsNet including homogeneous networks of agents which first have to agree on basic protocols for organization and communication. We find that some frontier LLMs are already demonstrating strong performance for small networks but begin to fall off once the size of the network scales. While existing multi-agent benchmarks cover at most 2-5 agents, AgentsNet is practically unlimited in size and can scale with new generations of LLMs. As such, we also probe frontier models in a setup with up to 100 agents.

1 Introduction

AGENTSNET addresses the missing evaluation of scalable coordination, decentralized communication, and collaborative reasoning in multi-agent LLM networks. It builds on distributed-computing problems, scalable message passing, diverse graph instances, and evaluations extending to 100 agents.

  • AGENTSNET fills a benchmark gap by testing scalable coordination, decentralized communication, and collaborative reasoning across network structures and sizes.
  • The benchmark comprises graph coloring, minimal vertex cover, maximal matching, leader election, and consensus to evaluate self-organization, coordination, and communication.
  • AGENTSNET uses a scalable agent-to-agent message-passing protocol and graph instances sampled from models including small-world and preferential attachment networks.
  • The evaluation covers open-source, frontier, and reasoning models on graphs of 4, 8, and 16 nodes, scaling to 100 agents beyond existing agentic benchmarks.
  • The paper adds qualitative analysis of coordinative and collaborative challenges to guide improvements in multi-agent systems.

2 Related Work

Prior work shows that multi-agent collaboration and network topology can improve LLM performance, but studies differ in how interaction structures are fixed or adapted.

  • Ensembling agents to negotiate solutions improves LLM performance, while subsequent work studies predetermined and automatically adapting network topologies.
  • Experiments report that different topologies perform best for specific tasks, alongside large-scale agent networks exhibiting known social phenomena.

3 Tasks, Evaluation, and Graph Models

AGENTSNET maps five distributed-computing problems onto agentic tasks spanning local information exchange to global decision-making. It evaluates these tasks on graph models representing varied structural properties.

  • 3 Tasks, Evaluation, and Graph Models: AGENTSNET evaluates aggregation, self-organization, and coordination through distributed problems spanning local exchange to global decision-making.
  • 3 Tasks, Evaluation, and Graph Models: The benchmark includes coloring, minimal vertex cover, maximal matching, leader election, and consensus as its core task families.
  • 3.1 Benchmarking Tasks: COLORING assigns agents to groups so neighboring agents differ, modeling distributed role assignment with at most Δ + 1 colors.
  • 3.1 Benchmarking Tasks: VERTEXCOVER selects a minimal coordinator set that covers every graph edge, representing compact monitoring or gateway responsibility.
  • 3.1 Benchmarking Tasks: LEADERELECTION selects exactly one leader, whereas CONSENSUS requires every agent to output the same value from {0, 1}.
  • Graph Models: The graph suite uses Watts–Strogatz small-world, preferential-attachment scale-free, and Delaunay-style structural variation rather than relying only on random graphs.

4 Agent-to-Agent Communication via Message-Passing

AGENTSNET implements synchronous neighbor-only communication in the LOCAL model, with agents exchanging structured messages before producing task-specific final responses. The protocol uses prompts, chat histories, JSON message exchange, retries for malformed outputs, and fixed-round evaluation.

  • 4 Agent-to-Agent Communication via Message-Passing: Agents communicate synchronously with immediate graph neighbors, basing decisions on messages received in successive rounds under the LOCAL model.
  • 4 Agent-to-Agent Communication via Message-Passing: Each agent receives task, protocol, and neighbor information in its system prompt and interacts through a structured chat history.
  • 4 Agent-to-Agent Communication via Message-Passing: At every round, agents generate neighbor-specific messages as flat JSON, optionally elaborating their chain of thought before output.
  • 4 Agent-to-Agent Communication via Message-Passing: Malformed JSON triggers a retry using the full chat history, and final benchmark scores are computed from the resulting task-specific answers.
  • 4 Agent-to-Agent Communication via Message-Passing: After a fixed number of message-passing rounds, models produce simpler string-based task responses such as Yes or No for leader election.

5 Experiments

AGENTSNET evaluates frontier and open-source LLMs on distributed-computing tasks across graph sizes, revealing task-specific strengths, declining performance with scale, and coordination failures.

  • 5.1 Setup: AGENTSNET benchmarks models on 27 graph topologies spanning small-world, scale-free, and Delaunay graphs with 4, 8, and 16 nodes.Global tasks use 2D + 1 communication rounds, while local-task rounds increase from 4 to 6 with graph size.
  • 5.1 Setup: The benchmark uses strict binary scoring for fully correct network-wide solutions, supplemented by standard errors across repeated graph samples.Partial correctness is discussed separately because soft scores are not directly comparable across tasks.
  • 5.2 Results on AGENTSNET: Claude 3.7 Sonnet, Gemini 2.5 Pro, and Gemini 2.5 Flash perform best overall, while Gemini 2.5 Flash is about 20× cheaper than Claude 3.7 Sonnet.Performance generally decreases as graph size increases, and no model performs consistently strongly across all tasks.
  • 5.2 Results on AGENTSNET: Consensus is solved by most models, whereas Vertex Cover is difficult, especially on 8- and 16-node graphs.Figure 4 provides a task-level breakdown by model and graph size, separating reasoning from non-reasoning models.
  • 5.3 Scaling the Agent Network: At 100-agent networks, performance drops to near zero across the board, while the benchmark remains extensible to larger networks without changing its task definition.Figure 5 tracks Gemini 2.0 Flash as graph size increases from 20 to 100 agents.
  • 5.4 Qualitative Analysis: Qualitative analysis identifies late or absent strategy coordination, uncritical acceptance of neighbor information, and assistance with resolving inconsistent candidate solutions.Agents sometimes adopt initial strategies without communicating them, accept erroneous topology assumptions, and correct conflicting color assignments.

6 Limitations

AGENTSNET currently uses synchronous LOCAL-model communication and JSON answer parsing, both of which impose implementation-specific limitations.

  • 6 Limitations: Synchronous message passing delays replies by one round, and JSON parsing can be ambiguous or error-prone.The authors characterize these as implementation choices rather than inherent limitations of AGENTSNET.

7 Conclusion

AGENTSNET is a scalable benchmark for testing whether agentic networks can coordinate and collaborate on distributed-computing problems. Its extensible graph sizes and message-passing protocol support evaluation of frontier models as capabilities advance.

  • 7 Conclusion: AGENTSNET assesses agentic networks using fundamental distributed-computing problems and supports benchmark instances scaling to 100 agents.The benchmark is practically unlimited in size and can generate increasingly complex problems.
  • 7 Conclusion: The benchmark combines multi-step message passing, diverse graph models, and varying graph sizes to compare frontier LLMs, which remain challenged by the tasks.The design is intended to evolve alongside future model capabilities.

A Implementation Details

AGENTSNET implements synchronous, local message passing over graph neighborhoods, with agents exchanging structured JSON messages for a fixed number of rounds before solving the task.

  • Message-Passing: The implementation describes message generation, sending, and receiving through Generate, SendMessage, and ReceiveMessage operations.Retries and JSON parsing are omitted from the pseudocode for clarity.
  • Evaluation Setup: The benchmark evaluates models and versions from multiple API providers, as documented in Table 3.
  • Agent Setup: Each agent is assigned a unique name and receives the total number of agents, its own name, and its neighbor list.
  • Message-Passing: AGENTSNET uses synchronous rounds in which each agent receives neighbors’ previous messages and sends responses visible in the next round.Agents communicate only with immediate neighbors, so information can travel through the network via relays.
  • Message-Passing: Agents decide independently what to share or request and return response messages as JSON objects keyed by neighboring agents.Messages to particular neighbors may be omitted when no communication is needed.

B Benchmark Tasks

AgentsNet instantiates distributed coordination problems as agentic tasks over network topologies, requiring local agents to jointly satisfy global structural constraints. It evaluates coloring, matching, leader election, consensus, and minimal vertex cover, using task-specific scores and mean solved-instance fractions for aggregate benchmarking.

  • Task suite: AgentsNet includes graph-coordination tasks for coloring, matching, leader election, consensus, and minimal vertex cover, translating classical distributed problems into multi-agent communication settings.The benchmark asks agents to coordinate through message passing and produce locally stated decisions that jointly satisfy global constraints.
  • COLORING: Coloring requires neighboring agents to choose different groups from exactly Δ+1 available groups, with Δ resolved as the network’s maximum degree.The final assignment must place every pair of neighboring agents in distinct groups.
  • VERTEXCOVER and scoring: Minimal vertex cover scores edge coverage together with violations caused by non-essential coordinators, while benchmark results use mean solved-instance fractions because task scores are not comparable.Soft scores remain task-specific and are therefore not aggregated into a total score.
  • MATCHING: Matching requires agents to form disjoint pairs through reciprocal neighbor selections, while inconsistencies include unilateral or conflicting pair choices.Agents may answer None when all eligible neighbors are already paired.
  • LEADERELECTION and CONSENSUS: Leader election and consensus require, respectively, exactly one Yes leader and unanimous selection of either 0 or 1 after communication rounds.Both tasks evaluate whether local responses converge to a globally valid outcome.
  • Network topology: The benchmark also uses geometric graphs generated from Delaunay triangulations, which are planar, connected, relatively low-degree, and spatially local.These properties target settings such as geographic networks, wireless communication, and distributed sensor systems.

E.1 K4 or Star?

The examples show that multi-agent coordination can fail when agents do not synchronize strategies, challenge inconsistent information, or account for simultaneous message exchange. They also show occasional self-initiated assistance and implicit strategy inference, while the benchmark scales to networks of up to 100 agents.

  • E.1 K4 or Star?: Contradictory late information caused agents to abandon a correct K4-based vertex-cover strategy, producing a selection that was not a vertex cover.Douglas and Stephen accepted Jeremy’s conflicting star description, while Danielle retained the original view; only Jeremy answered Yes, so the final selection failed the task.
  • E.2 Matching: Agents also failed at matching because Kyle and Dorothy relied on outdated neighbor information and stopped negotiating after both initially pursued other partners.Their persistent trust in stale messages left both agents unmatched despite the possibility that their neighbors’ situations had changed.
  • E.3 Synchronization: Synchronous message passing created inconsistent views, as agents recognized that simultaneous exchanges and message lag could make received information difficult to synchronize.Samuel and Tyler independently discussed crossed messages and conflicting color proposals with their neighbors.
  • E.5 Priority 42: Agents sometimes inferred an unstated priority-based strategy and proactively helped resolve conflicts, while AGENTSNET supports experiments that scale from small graphs to 100 agents.Kayla independently warned two neighboring agents about their conflicting color choice, and neighboring agents inferred Henry’s priority request despite limited explanation.
  • E.4 Strategy Coordination: Strategy coordination remained difficult because agents announced one coloring strategy but later selected different groups after hearing neighbors’ choices.This behavior demonstrates that agents may apply distributed algorithms inconsistently across rounds even after communicating an initial plan.

G Limitations

AGENTSNET’s fixed synchronous protocol and binary correctness metric simplify evaluation but limit ecological validity and obscure partial progress. Homogeneous agents further narrow the setting relative to real-world multi-agent systems.

  • G Limitations: The benchmark fixes synchronous LOCAL-style communication and a predetermined number of rounds, limiting transfer to asynchronous or dynamically constrained multi-agent systems.The authors identify this protocol choice as theoretically grounded but less ecologically valid than many real-world settings.
  • G Limitations: Binary instance-level correctness gives a clear coordination signal but can hide substantial reasoning progress in near-correct solutions.The paper notes that strict task-specific success criteria may obscure partial progress.
  • G Limitations: Agents are homogeneous within each experiment, sharing architecture, capabilities, and prompting style, which simplifies analysis but narrows evaluation scope.

H Extended Results

Extended results show improved performance for Gemini 2.5 Pro while indicating that AGENTSNET remains unsaturated and scalable for distinguishing model capabilities. Soft scores add within-task information but are not comparable across tasks.

  • H Extended Results: Gemini 2.5 Pro reaches a new state-of-the-art mean AGENTSNET score of 0.80 with consistently improved results.The reported 0.80 mean is based on the benchmark’s binary fully solved-instance evaluation.
  • H Extended Results: AGENTSNET remains well calibrated to distinguish models of varying capabilities, and its results do not indicate saturation.The authors point to small standard errors and the continued separation of model performance as evidence for this conclusion.
  • H Extended Results: Increasing graph size allows AGENTSNET to extend with future models and continue providing meaningful performance differentiation.The benchmark’s generative setup supports scaling beyond the current evaluated problem sizes.
Loading 2507.08616v1…