Provable Coordination for LLM Agents via Message Sequence Charts
Benedikt Bollig, Matthias Függer, Thomas Nowak · 2026
Read Provable Coordination for LLM Agents via Message Sequence Charts by Benedikt Bollig, Matthias Függer, Thomas Nowak (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-17612.txt.
Introduction
Bollig, Függer, and Nowak introduce a language for coordinating LLM agent teams, based on message sequence charts. Multi-agent LLM systems are hard to reason about, and coordination errors like deadlocks or type-mismatched messages often escape testing. Their language keeps message-passing structure apart from human control points, LLM calls, and tool calls, whose outcomes stay unpredictable. A syntax-directed projection turns global specs into deadlock-free local programs, shown on a diagnosis consensus protocol, with a runtime planning extension and a Python implementation.
Catalog record
| CREATOR | Benedikt Bollig, Matthias Függer, Thomas Nowak |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118033 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.17612
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Provable Coordination for LLM Agents via Message Sequence Charts Benedikt Bollig, Matthias Függer, Thomas Nowak 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 actions, whose outputs 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. 1 Introduction Multi-agent systems built on large language models (LLMs) are increasingly common. They combine the capabilities of individual AI components with the structural advantages of distributed systems, such as concurrency, separation of concerns, and explicit communication patterns. A typical example is a group of LLM agents that iteratively exchange assessments until they reach agreement on a task, such as giving a medical diagnosis. These systems are, however, hard to design and to reason about. While classical distributed systems are already notoriously error prone, the stochastic nature of LLM outputs further complicates reasoning about such systems. When agents exchange messages and collaborate, problems such as deadlocks or lost messages are difficult to rule out through testing alone. Frameworks like LangGraph [ 18 ] , AutoGen [ 26 ] , and CrewAI [ 5 ] provide convenient infrastructure for building such systems, but offer no formal guarantees. The broader engineering challenges of such systems, such as transparency, traceability, and error attribution, are well-documented [ 8 ] . Applying formal methods to this setting is therefore natural. Contributions. For this purpose, we propose a domain-specific language (DSL) for agent coordination based on message sequence charts (MSCs) [ 17 ] , an International Telecommunication Union (ITU) standard for communication protocols. MSCs combine a visual notation with a formal semantics. They represent both the local progress of individual agents (their lifelines) and the messages exchanged between them, making causal dependencies in a system execution easy to track. Abstractly, an MSC describes a single execution. Higher-level formalisms compose simple MSCs into sets (or languages). They can be thought of as global workflows: specifications of what a distributed system should do, independently of how it is implemented. Much research has addressed the question of how such global specifications can be realized in a distributed fashion. The conceptually cleanest approach is projection: deriving a local program for each participant by restricting the global specification to that participant’s view. This has been pursued both for MSC-based formalisms [ 1 , 11 , 3 ] and for multiparty session types (MPST) [ 16 , 19 ] . These works follow an automata-theoretic route: a realizability condition is checked, local machines are constructed, and correctness is established by language equivalence. Our approach works with structured programs rather than automata and targets LLM components directly. Workflow-level specifications suit LLM agents well: rather than following a finite transition graph, agents maintain variable-length context, evaluate local conditions, and branch based on their own state. Moreover, the projected local programs are programs again: they can be embedded in larger workflows, exposed as APIs, or composed with other components without further translation. Existing LLM-based multi-agent frameworks do not address the synthesis of provably correct distributed agent programs. The same holds when the coordination structure is not fixed in advance but generated at runtime by a planning LLM. Asking such a system to produce deadlock-free distributed code directly is unreasonable: it would have to ensure that every send by one agent is matched by a receive of another, in every branch and under every execution order. With our language, the planner needs only to produce a syntactically valid, well-typed global workflow. Deadlock-freedom is then guaranteed by the projection. The language is therefore not only a programming interface for humans, but also a natural target for LLM-based planning. We extend standard MSCs with two constructs: action blocks, which treat LLM computations as opaque typed functions, and owned control flow, where each conditional and loop has an explicit decider. The first extension separates what can be guaranteed statically (the message-passing structure, which has a precise operational semantics) from what cannot: the stochastic outputs of LLM calls. The second makes projection syntax-directed: it is a structural recursion on the global workflow, and the correctness proof is a structural induction. No automaton is constructed at any point. Related work. Our work connects two lines of research. The first is the formal side: realizability for MSCs and communicating automata [ 1 , 10 , 11 , 3 , 22 , 21 , 20 , 25 , 12 ] addresses the question of whether a global specification admits a deadlock-free distributed implementation. Rather than solving this problem post-hoc, we follow a by-construction approach: the global language is designed so that projection is always syntax-directed and yields well-structured local programs directly. Closest to our approach is [ 10 ] , which also inserts control messages automatically to synthesize local controllers, but works with automaton-based global specifications and is not designed for LLM-based agents. Multiparty session types (MPSTs) [ 15 , 16 , 19 , 7 , 4 , 9 ] also project a global description to local views, but require well-formedness conditions for projection to be defined, notably that uninvolved participants have consistent local behaviors across branches. Scribble [ 27 ] is a prominent practical MPST-based protocol language, and its refinement-typed extension [ 28 ] further adds data-level verification, an orthogonal direction we do not pursue. In contrast, our language is designed so that projection is always defined for its constructs: owned control flow together with explicit control broadcasts eliminates the need for such consistency conditions (often formulated as branch-mergeability [ 9 ] ) in standard MPST settings. Process calculi [ 14 , 23 ] work in the opposite direction: local processes are composed to obtain global behavior, rather than projected from a global specification. The second line concerns practical multi-agent frameworks such as LangGraph, AutoGen, and CrewAI [ 18 , 26 , 5 ] . These treat coordination as an engineering concern, relying on testing and runtime monitoring for correctness. We separate the coordination layer from the LLM layer and reason about the former independently; in particular, deadlock-freedom holds even for runtime-generated workflows, which to our knowledge no existing framework guarantees. Outline. Section 2 presents introductory examples. Sections 3 – 4 define the syntax and semantics of global and local programs. Section 5 presents the projection, proves correctness and deadlock-freedom, and describes the ZipperGen implementation ( https://zippergen.io ). Section 6 illustrates the framework. Section 7 concludes. Proofs are deferred to the appendix. All definitions have been formalized and all results have been machine-checked in the Lean 4 proof assistant [ 6 ] . Clicking a badge or opens the corresponding Lean source file. 2 Introductory Examples We illustrate our language on a