Symbolic Guidance for LLM Agents in Distributed Multiagent Coordination

Ben Rachmut; Ning Zhang; Yevgeniy Vorobeychik; William Yeoh

cs.AISep 25, 2026

Symbolic Guidance for LLM Agents in Distributed Multiagent Coordination

Authors: Ben Rachmut, Ning Zhang, Yevgeniy Vorobeychik, William Yeoh

Organizations: Washington University in St. Louis, Saint Louis, MO, United States

Abstract

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

\mathcal{A}

. Showing mean

\ln(1+\mathrm{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

\mathcal{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

\mathcal{A}

. Showing mean

\ln(1+\mathrm{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

\mathcal{A}

. Showing mean

\ln(1+\mathrm{SSE})

by model. Bar colors denote agent types sorted by autonomy level; error bars show SEM.

Local (MIS)
	( $\Delta$ +1)-	Maximal	Minimal
	Coloring	Matching	Vertex Cover
AgentsNet	1.99 $\pm$ 0.43	1.03 $\pm$ 0.34	2.74 $\pm$ 0.44
Function-Description	0.55 $\pm$ 0.26	0.78 $\pm$ 0.31	2.21 $\pm$ 0.34
Function-Pseudocode	0.34 $\pm$ 0.12	0.80 $\pm$ 0.30	3.03 $\pm$ 0.40
Main-Pseudocode	1.05 $\pm$ 0.33	1.85 $\pm$ 0.46	2.34 $\pm$ 0.38

Table 1: Gemini-2.5: mean

\ln(1+\mathrm{SSE})\pm\mathrm{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 LLM Systems

Multi-agent large language model systems coordinate multiple AI agents to solve tasks through communication, specialization, shared tools, and memory.

See all 1,001 papers

Provable Coordination for LLM Agents via Message Sequence Charts
Apr 19, 2026Benedikt Bollig, Matthias Függer, Thomas NowakMulti-Agent LLM Systems Multi-Agent Coordination
Universit´e Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, Gif-sur-Yvette, France · Institut Universitaire de France, Paris, France
Epistemic-Probabilistic Model for Guarded Multi-Agent LLM Coordination
Sep 24, 2026Mehdi Nasiri, Mohammad Saeed Arvenaghi, Sadegh Vaezi +1Multi-Agent LLM Systems Multi-Agent Coordination
Pasargad Institute for Advanced Innovative Solutions · Iran University of Science and Technology
Drop the Hierarchy and Roles: How Self-Organizing LLM Agents Outperform Designed Structures
Mar 30, 2026Victoria DochkinaMulti-Agent Systems Multi-Agent LLMs
Moscow Institute of Physics and Technology (MIPT), Moscow, Russia

Apr 19, 2026J/K move · Enter open · S save

Provable Coordination for LLM Agents via Message Sequence Charts

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 LLM Systems Multi-Agent Coordination LLM Agent Planning

Open paper AskPDF arXiv

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.

Abstract

Multi-Agent LLM Systems

Explore similar work

Provable Coordination for LLM Agents via Message Sequence Charts

Epistemic-Probabilistic Model for Guarded Multi-Agent LLM Coordination

Drop the Hierarchy and Roles: How Self-Organizing LLM Agents Outperform Designed Structures