Large language models (LLMs) are increasingly deployed as autonomous agents in multi-agent systems, yet their ability to reliably execute distributed coordination protocols remains poorly understood. While AgentsNet, a benchmark framework for distributed coordination among LLM agents, enables such coordination, granting full reasoning autonomy often leads to inconsistent or degraded performance in complex domains. We hypothesize that coordination can be improved by regulating agent autonomy through symbolic guidance derived from established algorithms. To investigate this, we introduce the Symbolic Guidance Taxonomy (SGT), which characterizes a spectrum of autonomy ranging from open-ended natural language reasoning to fully prescribed algorithmic execution, with intermediate levels providing partial pseudocode guidance. Our results show that intermediate autonomy levels consistently outperform both unguided agents and fully prescriptive specifications. These findings identify autonomy regulation as a key design principle for LLM-based distributed coordination.
Figures & tables
Figure 1: The Symbolic Guidance Taxonomy (SGT) autonomy spectrum, ranging from maximized autonomy (AgentsNet agents) to no autonomy (Code agents).
Figure 2: Local coordination domains with MIS as algorithm A . Showing mean ln(1+SSE) by model. Bar colors denote agent types sorted by autonomy level; error bars show SEM.
Figure 3: Local coordination domains with MIS as algorithm A . Showing the success rate of feasible solutions for Gemini. Bar colors denote agent types sorted by autonomy level; error bars show SEM.
Figure 4: Global coordination domains with MIS as algorithm A . Showing mean ln(1+SSE) by model. Bar colors denote agent types sorted by autonomy level; error bars show SEM.
Figure 5: Global coordination domains with Distributed DFS as algorithm A . Showing mean ln(1+SSE) by model. Bar colors denote agent types sorted by autonomy level; error bars show SEM.
Local (MIS)
( Δ +1)-
Maximal
Minimal
Coloring
Matching
Vertex Cover
AgentsNet
1.99 ± 0.43
1.03 ± 0.34
2.74 ± 0.44
Function-Description
0.55 ± 0.26
0.78 ± 0.31
2.21 ± 0.34
Function-Pseudocode
0.34 ± 0.12
0.80 ± 0.30
3.03 ± 0.40
Main-Pseudocode
1.05 ± 0.33
1.85 ± 0.46
2.34 ± 0.38
Table 1: Gemini-2.5: mean ln(1+SSE)±SEM across different experimental settings (best per column in bold ). Each section header indicates the domain variant and, in parentheses, the algorithm used.
Multi-agent systems built on large language models (LLMs) are difficult to reason about. Coordination errors such as deadlocks or type-mismatched messages are often hard to detect through testing. We introduce a domain-specific language for specifying agent coordination based on message sequence charts (MSCs). The language separates message-passing structure from LLM calls, tool calls, and human control points, whose outcomes remain unpredictable. We define the syntax and semantics of the language and present a syntax-directed projection that generates deadlock-free local agent programs from global coordination specifications. We illustrate the approach with a diagnosis consensus protocol and show how coordination properties can be established independently of LLM nondeterminism. We also describe a runtime planning extension in which an LLM dynamically generates a coordination workflow for which the same structural guarantees apply. An open-source Python implementation of our framework is available as ZipperGen.
Benedikt Bollig, Matthias Függer, Thomas Nowak
Universit´e Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, Gif-sur-Yvette, France · Institut Universitaire de France, Paris, France
Multi-agent large language models (LLMs) have become ubiquitous in applied AI, yet their theoretical foundations remain surprisingly understudied. Viewed through the lens of multi-agent systems theory, several shortcomings come to light: a lack of social intelligence, the absence of coordination mechanisms among agents, unknown emergent behavior, and interactions between agents that are bounded by natural language. We address two of these gaps: the absence of social behavior and the lack of mechanisms for inter-agent coordination. We introduce Epistemic Probabilistic Language Agents (EPLA), a neuro-symbolic architecture for multi-agent coordination under uncertainty. A Symbolic Guard provides structured diagnostic feedback. The LLM generates typed actions, and the Guard controls their execution against an authoritative symbolic state. We formalize the epistemic layer in a gossip testbed through epistemic lottery gossip models, which combine view-based call histories with agent-indexed probability weights. We argue that implementing such a formalism can address shortcomings of agentic LLMs.
Mehdi Nasiri, Mohammad Saeed Arvenaghi, Sadegh Vaezi +1
Pasargad Institute for Advanced Innovative Solutions · Iran University of Science and Technology
How much autonomy can multi-agent LLM systems sustain -- and what enables it? We present a 25,000-task computational experiment spanning 8 models, 4--256 agents, and 8 coordination protocols ranging from externally imposed hierarchy to emergent self-organization. We observe that autonomous behavior already emerges in current LLM agents: given minimal structural scaffolding (fixed ordering), agents spontaneously invent specialized roles, voluntarily abstain from tasks outside their competence, and form shallow hierarchies -- without any pre-assigned roles or external design. A hybrid protocol (Sequential) that enables this autonomy outperforms centralized coordination by 14% (p<0.001), with a 44% quality spread between protocols (Cohen's d=1.86, p<0.0001). The degree of emergent autonomy scales with model capability: strong models self-organize effectively, while models below a capability threshold still benefit from rigid structure -- suggesting that as foundation models improve, the scope for autonomous coordination will expand. The system scales sub-linearly to 256 agents without quality degradation (p=0.61), producing 5,006 unique roles from just 8 agents. Results replicate across closed- and open-source models, with open-source achieving 95% of closed-source quality at 24x lower cost. The practical implication: give agents a mission, a protocol, and a capable model -- not a pre-assigned role.
Victoria Dochkina
Moscow Institute of Physics and Technology (MIPT), Moscow, Russia