Provable Coordination for LLM Agents via Message Sequence Charts
Benedikt Bollig, Matthias F\"ugger, Thomas Nowak
Why It Matters
What makes this one worth your time
This work provides a structured approach to managing coordination in LLM-based multi-agent systems, potentially reducing errors like deadlocks and improving reliability.
A new language for coordinating LLM-based multi-agent systems using message sequence charts.
Summary
The paper introduces a domain-specific language for specifying coordination in multi-agent systems using message sequence charts, aiming to separate message-passing structure from unpredictable elements like LLM calls. It defines the language's syntax and semantics, and presents a method to generate deadlock-free local agent programs from global specifications. The approach is illustrated with a diagnosis consensus protocol, and a runtime planning extension is described where an LLM dynamically generates a coordination workflow. An open-source implementation is provided.
Key contributions
- Introduction of a domain-specific language for agent coordination using message sequence charts.
- Syntax-directed projection method for generating deadlock-free local agent programs.
- Runtime planning extension for dynamic coordination workflow generation by LLMs.
Notable insights
- Separating message-passing structure from LLM calls can help manage unpredictability in multi-agent systems.
- Using message sequence charts allows for provable coordination properties independent of LLM nondeterminism.
Possible limitations
- Not stated in the abstract
Abstract
arXiv:2604.17612v3 Announce Type: replace-cross Abstract: 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.