Provable Coordination for LLM Agents via Message Sequence Charts

• URL: http://arxiv.org/abs/2604.17612v1
• Date: Sun, 19 Apr 2026 20:54:30 GMT
• Title: Provable Coordination for LLM Agents via Message Sequence Charts
• Abstract summary: We introduce a domain-specific language for specifying agent coordination based on message sequence charts (MSCs)<n>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.<n>An open-source Python implementation of our framework is available as ZipperGen.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Inference-Time Graph Engineering for Multi-Agent LLM Workflows [51.56038180639833]
  We introduce ReActNet, a training-free framework that compiles a query and a set of role-specialized agents into a sequence of directed communication graphs.<n>We show that ReActNet consistently improves over fixed-topology and learned-topology baselines while maintaining competitive inference cost.
  arXiv  Detail & Related papers  (2026-09-04T23:32:11Z)
• MARC v1: An Open-Source Multi-Agent Framework for Clinical AI Reasoning and Coordination [2.3475925378848124]
  MARC coordinates role-specialized agents for extraction, reasoning, answer generation, and evaluation.<n>Decomposer module generates task-specific agent prompts from a plain-language description.<n>MARC is designed to be model-agnostic, interpretable, and accessible to clinical domain experts without programming expertise.
  arXiv  Detail & Related papers  (2026-08-13T17:00:08Z)
• STeP: Signal Temporal Logic for Precise Specifications for Action Generation with Vision Language Models [9.560201418658144]
  Vision-language-action (VLA) models have shown impressive generalization, but often lack interpretability.<n>We propose a hierarchical framework that uses Signal Temporal Logic (STL) as a shared representation connecting high-level language understanding with low-level robot execution.<n>We evaluate the approach on a real-world tabletop domain, demonstrating how formal specifications can improve the precision, reliability, and interpretability of language-conditioned robot planning.
  arXiv  Detail & Related papers  (2026-07-20T23:26:32Z)
• When LLMs Develop Languages: Symbolic Communication for Efficient Multi-Agent Reasoning [85.36421257648294]
  Chain-of-Thought (CoT) improves large language models (LLMs) on difficult reasoning tasks.<n>We propose Communicative Language Symbolism Routing (R)<n>R treats each Language Symbolism Framework as a reusable symbolic protocol with compact symbols, usage rules, and a message-passing contract.<n>R reduces latency-oriented generated token completion by $3sim 6times$ compared to standard CoT.
  arXiv  Detail & Related papers  (2026-06-28T12:02:42Z)
• A Language for Describing Agentic LLM Contexts [24.406399255415113]
  Agentic Context Description Language (ACDL) provides constructs for specifying context aspects.<n>ACDL diagrams can be hand drawn on a whiteboard, or written in formal language which can then be rendered.<n>Tooling, examples and documentation are available at www.acdlang.org.
  arXiv  Detail & Related papers  (2026-05-03T15:02:44Z)
• RunAgent: Interpreting Natural-Language Plans with Constraint-Guided Execution [36.644786364066796]
  RunAgent is a multi-agent plan execution platform that interprets natural-language plans and enforces stepwise execution through constraints and rubrics.<n>We show that RunAgent outperforms baseline LLMs and state-of-the-art PlanGEN methods.
  arXiv  Detail & Related papers  (2026-05-01T17:29:45Z)
• Job Skill Extraction via LLM-Centric Multi-Module Framework [51.37063712967151]
  We present SRICL, an LLM-centric framework that combines semantic retrieval, in-context learning, and supervised fine-tuning.<n>On six public span-labeled corpora of job-ad sentences, SRICL achieves substantial STRICT-F1 improvements over GPT-3.5 prompting baselines and sharply reduces invalid tags and hallucinated spans.
  arXiv  Detail & Related papers  (2026-04-23T10:46:07Z)
• CBCL: Safe Self-Extending Agent Communication [0.0]
  We present CBCL (Common Business Communication Language), an agent communication language that constrains all messages, including runtime language extensions, to the deterministic context-free language (DCFL) class.<n> CBCL allows agents to define, transmit, and adopt domain-specific "dialect" extensions as first-class messages; three safety invariants (R1-R3), machine-checked Lean 4 and enforced in a Rust reference implementation.
  arXiv  Detail & Related papers  (2026-04-16T00:57:48Z)
• From Agent Loops to Structured Graphs:A Scheduler-Theoretic Framework for LLM Agent Execution [1.8222732878503212]
  The dominant paradigm for building LLM based agents is the Agent Loop, an iterative cycle where a single language model decides what to do next by reading an ever growing context window.<n>This perspective places Agent Loops and graph based execution engines on a single semantic continuum.<n>We propose SGH, which lifts control flow from implicit context into an explicit static DAG.
  arXiv  Detail & Related papers  (2026-04-13T12:16:45Z)
• ProtocolLLM: RTL Benchmark for SystemVerilog Generation of Communication Protocols [45.66401695351214]
  We introduce ProtocolLLM, the first benchmark suite specifically targeting widely used SystemVerilog protocols.<n>We observe that most of the models fail to generate SystemVerilog code for communication protocols that follow timing constrains.
  arXiv  Detail & Related papers  (2025-06-09T17:10:47Z)
• Type-Constrained Code Generation with Language Models [51.03439021895432]
  We introduce a type-constrained decoding approach that leverages type systems to guide code generation.<n>For this purpose, we develop novel prefix automata and a search over inhabitable types, forming a sound approach to enforce well-typedness on LLM-generated code.<n>Our approach reduces compilation errors by more than half and significantly increases functional correctness in code synthesis, translation, and repair tasks.
  arXiv  Detail & Related papers  (2025-04-12T15:03:00Z)
• DECIDER: A Dual-System Rule-Controllable Decoding Framework for Language Generation [57.07295906718989]
  Constrained decoding approaches aim to control the meaning or style of text generated by pre-trained large language (Ms also PLMs) for various tasks at inference time.<n>These methods often guide plausible continuations by greedily and explicitly selecting targets.<n>Inspired by cognitive dual-process theory, we propose a novel decoding framework DECIDER.
  arXiv  Detail & Related papers  (2024-03-04T11:49:08Z)
• If LLM Is the Wizard, Then Code Is the Wand: A Survey on How Code Empowers Large Language Models to Serve as Intelligent Agents [81.60906807941188]
  Large language models (LLMs) are trained on a combination of natural language and formal language (code) Code translates high-level goals into executable steps, featuring standard syntax, logical consistency, abstraction, and modularity.
  arXiv  Detail & Related papers  (2024-01-01T16:51:20Z)
• Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs [46.721838623748816]
  We propose a new inference-time approach to enforcing syntactic and semantic constraints on the outputs of large language models. Key idea is to specify language generation tasks as posterior inference problems in a class of discrete probabilistic sequence models. For a computational cost similar to that of beam search, SMC can steer LLMs to solve diverse tasks.
  arXiv  Detail & Related papers  (2023-06-05T17:55:05Z)
• Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning [27.59524153097858]
  grammar-constrained decoding (GCD) can be used to control the generation of large language models (LMs) GCD can serve as a unified framework for structured NLP tasks in general. We show that grammar-constrained LMs substantially outperform unconstrained LMs or even beat task-specific finetuned models.
  arXiv  Detail & Related papers  (2023-05-23T11:54:37Z)
• CAPE: Corrective Actions from Precondition Errors using Large Language Models [8.547766794082184]
  We propose a novel approach that attempts to propose corrective actions to resolve precondition errors during planning. CAPE improves the quality of generated plans by leveraging few-shot reasoning from action preconditions. Our improvements transfer to a Boston Dynamics Spot robot with a set of skills (specified in language) and associated preconditions, where CAPE improves the correctness metric of the executed task plans by 76.49% compared to SayCan.
  arXiv  Detail & Related papers  (2022-11-17T23:14:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.