PaxLabs Research
Andres G. and the PaxLabs Research Team · PaxLabs Inc.
Multi-Agent Coordination: Typed Messages, Shared State, and Provenance in LLM Orchestration
Andres G. and the PaxLabs Research Team PaxLabs Inc. Correspondence: legal@paxeer.app
Large language model (LLM) based multi-agent systems have moved from research prototypes to production orchestration layers. Yet coordination failures remain poorly characterized and largely unaddressed by existing frameworks. We argue that reliable multi-agent coordination requires three architectural primitives: typed messages for unambiguous inter- agent communication, shared state for maintaining a coherent world model across agents, and provenance for attributing every artifact to its source agent, inputs, and governing specification. We formalize each primitive, present a taxonomy of coordination patterns (sequential dispatch, parallel fan-out/fan-in, hierarchical delegation, auction- based bidding, and consensus/debate), identify failure modes that arise when any primitive is absent, and propose an evaluation protocol for measuring coordination quality. Our analysis draws on recent work in LLM-based multi-agent orchestration, agent communication languages, and distributed systems provenance. We show that without all three pillars, multi-agent systems degrade into loosely coupled generators with no accountability and no mechanism for debugging coordination failures.
shared state, provenance, coordination patterns, agent communication
The past two years have seen a rapid proliferation of multi-agent systems built on large language models. Frameworks such as AutoGen [1], CrewAI [2], LangGraph [3], and CAMEL [4] allow developers to compose multiple LLM-backed agents into pipelines that decompose complex tasks into subtasks distributed across specialized agents. The appeal is straightforward: a single LLM call may lack the context window, domain expertise, or tool access to solve a problem, but a team of coordinated agents can divide labor and synthesize results.
Despite this appeal, we observe that most deployed multi-agent systems suffer from coordination failures that are neither well-understood nor systematically addressed. Agents exchange free-form text, maintain no shared world model, and produce artifacts with no traceability to their originating inputs or governing instructions. When a multi-agent system produces an incorrect result, the failure cannot be attributed to a specific agent boundary, a specific miscommunication, or a specific state divergence.
We propose that reliable multi-agent coordination rests on three architectural primitives:
1) Typed Messages: Every inter-agent message conforms to a declared schema with explicit input types, output types, and semantic contracts. Free-form natural language is permitted only within the body of a typed envelope.
2) Shared State: All agents read from and write to a common state store that is journaled, versioned, and subject to consistency constraints. No agent maintains a private world model that diverges from the shared state without explicit branching.
3) Provenance: Every artifact (a message, a state mutation, a final output) carries metadata recording which agent produced it, which inputs it consumed, which specification governed its production, and at what point in the orchestration it was generated.
Our contributions are as follows. We present a taxonomy of five coordination patterns used in practice. We formalize each of the three pillars as mathematical objects. We catalog failure modes that arise when any pillar is missing. We propose an evaluation protocol with concrete metrics. We ground our claims in recent empirical work on multi-agent LLM systems.
AutoGen [1] provides a conversation-based programming model where agents exchange messages in directed conversations. An orchestrator agent (called the "user proxy") can route messages, invoke code execution, and manage conversation flow. AutoGen supports two-agent and group chat topologies. Its message format is free-form text with optional function-calling semantics.
CrewAI [2] organizes agents into "crews" with defined roles, goals, and backstories. Agents are assigned tasks and can delegate subtasks to other crew members. CrewAI emphasizes role-playing as a coordination mechanism: each agent is given a persona that shapes its behavior. The framework provides sequential and hierarchical process modes.
LangGraph [3] models agent workflows as state machines (directed graphs) where nodes are agent actions and edges are conditional transitions. It extends LangChain with explicit state management, checkpointing, and human-in-the-loop interrupt points. LangGraph provides the closest approximation to shared state among popular frameworks, though its state is application-defined rather than schema-enforced.
CAMEL [4] (Communicative Agents for "Mind" Exploration of Large Language Model Society) introduced the role-playing framework for autonomous cooperation between two agents. An "assistant" agent and a "user" agent collaborate through inception prompting, where each agent is given a task and a role, and cooperation emerges from the dialogue structure.
Du et al. [5] demonstrated that having multiple LLM instances debate a question can improve factual accuracy over single-model responses. Each agent proposes an answer, critiques the proposals of others, and revises its position. This approach treats coordination as a consensus process and has been extended by Liang et al. [6] to multi-agent discussions with structured rounds.
Minsky's society of mind theory [7] posits that intelligence emerges from the interaction of many simple agents, each specialized for a narrow function. This conceptual framework directly informs modern LLM multi-agent architectures, where each agent is specialized (e.g., a code-writing agent, a testing agent, a documentation agent) and coordination produces emergent capability. Recent work by Talebirad and Nadiri [8] formalized this connection for LLM-based agent societies.
The Foundation for Intelligent Physical Agents (FIPA) standardized agent communication languages (ACLs) in the early 2000s [9]. FIPA-ACL messages carry performative verbs (inform, request, propose), sender, receiver, content, and metadata. While FIPA-ACL saw limited adoption outside academic multi-agent systems, its design principles (typed performatives, explicit content language declarations) directly inform our typed message primitive. More recently, Wu et al. [10] surveyed LLM-based agent communication and found that most systems use ad hoc natural language exchange with no type safety.
We identify five coordination patterns that appear across existing frameworks and research systems. Each pattern has distinct failure modes and different requirements with respect to our three pillars.
In sequential dispatch, a controller agent passes a task to agent A, receives A's output, and passes it to agent B, and so on in a linear chain. This is the simplest pattern and is the default mode in many frameworks. The controller may or may not transform outputs between stages.
Failure characteristic: errors propagate linearly and compound at each stage. Without provenance, identifying which stage introduced an error requires re-running the entire chain.
A controller dispatches the same task (or subtasks) to N agents in parallel, collects their outputs, and merges them. This pattern is used in ensemble approaches and multi-agent debate [5, 6]. The merge step may use voting, concatenation, or a dedicated synthesis agent.
Failure characteristic: the merge step is a coordination bottleneck where semantic drift is most likely. If agents produce outputs in incompatible formats (due to absent typing), the merge step must perform implicit format reconciliation.
A top-level agent decomposes a task into subtasks and delegates each subtask to a subordinate agent. Subordinates may further delegate. This pattern mirrors organizational hierarchies and is the primary mode in CrewAI's hierarchical process [2].
Failure characteristic: delegation depth correlates with coordination loss. Without shared state, subordinate agents may develop inconsistent views of the task context. Without provenance, the top-level agent cannot verify that subordinates executed the intended specification.
Agents "bid" on tasks by estimating their suitability or cost. A controller awards the task to the highest bidder. This pattern draws on distributed systems research in market-based coordination [11] and has been adapted for LLM agent selection by Hong et al. [12] in the MetaGPT system.
Failure characteristic: bidding accuracy depends on agents' self- assessment capability, which is unreliable for LLMs. Without typed capability declarations, bids are based on free-form self-reports.
Multiple agents independently reason about a problem, exchange arguments, and converge on a shared conclusion through iterative discussion. This pattern is used in multi-agent debate [5, 6] and in systems like ChatEval [13].
Failure characteristic: convergence is not guaranteed, and agents may anchor on early proposals rather than exploring the solution space. Without shared state tracking which arguments have been considered, agents may revisit exhausted positions.
We now define each architectural primitive in detail.
Definition 1 (Typed Message): A typed message m is a tuple m = (type, sender, receiver, content, metadata) where: - type is a declared schema specifying the structure of content, including field names, field types, and semantic constraints - sender and receiver are agent identifiers - content is a structured object conforming to type - metadata includes a timestamp, a conversation identifier, and a reference to the specification version under which the message was produced
Motivation. LLMs generate free-form text, which is their primary strength. But when one agent's output is another agent's input, free- form text introduces ambiguity. Agent A may produce a JSON object while agent B expects a markdown table. Agent A may use "yes" where agent B expects "true". Agent A may include caveats and qualifications that agent B interprets as contradictory signals. These are not hypothetical failures; they are the routine coordination problems observed in practice [10].
Typed messages do not constrain what an agent thinks or generates internally. They constrain what crosses the agent boundary. An agent may produce a long chain of reasoning internally, but the message it sends must conform to the declared type. This is analogous to function signatures in typed programming languages: the internal implementation is unconstrained, but the interface is contractually specified.
Implementation. In practice, a typed message system requires: (a) a schema registry where message types are declared and versioned, (b) a validation layer that checks every outgoing message against its declared type before delivery, and (c) a serialization format (such as JSON Schema or Protocol Buffers) that supports rich type annotations.
Definition 2 (Shared State): A shared state S is a versioned, journaled key-value store accessible to all agents in an orchestration, subject to the following constraints: - Every state mutation is an atomic transaction - Every mutation is journaled with the agent that performed it, the previous value, the new value, and the reason for the mutation - State values conform to declared schemas (tying back to typed messages) - Agents may read any key but may write only to keys within their declared write scope
Motivation. Without shared state, each agent in a multi-agent system maintains an implicit internal model of the task context. These models diverge. Agent A learns a fact from its tool use and incorporates it into its subsequent reasoning. Agent B, lacking access to A's discovery, continues reasoning under outdated assumptions. This is the state inconsistency problem, and it is pervasive in systems where agents communicate only through messages and maintain no common ground truth.
LangGraph [3] provides application-defined state that is threaded through graph execution, which is a step in the right direction. But without schema enforcement and journaling, the state is a mutable data bag that provides no consistency guarantees and no audit trail.
Definition 3 (Provenance Record): A provenance record p for an artifact a is a tuple p = (a, agent, inputs, spec, timestamp, lineage) where: - a is the artifact identifier - agent is the identifier of the agent that produced a - inputs is the set of artifact identifiers that the agent consumed in producing a - spec is the identifier of the specification (prompt, function definition, or task description) that governed the agent's behavior - timestamp is the wall-clock time of production - lineage is the transitive closure of provenance records for all inputs, forming a directed acyclic graph (DAG)
Motivation. In a single-agent system, debugging is straightforward: the agent received input X, ran prompt P, and produced output Y. In a multi-agent system, the final output may be the product of a chain of five, ten, or twenty agent invocations. Without provenance, answering the question "why did the system produce this output?" requires replaying the entire orchestration and manually inspecting intermediate outputs.
Provenance has been well-studied in database and scientific workflow systems [14]. The W3C PROV standard [15] defines a data model for provenance that includes entities, activities, and agents. We adapt this model to the LLM multi-agent setting, where "activities" are LLM inference calls and "entities" are messages, state entries, and final outputs.
We now present a formal model that integrates the three pillars.
Definition 4 (Agent): An agent is a typed function alpha: (M*, S_t) -> (M', S_{t+1}) where M* is a sequence of typed messages, S_t is the current shared state, M' is a set of outgoing typed messages, and S_{t+1} is the updated shared state. Every invocation of alpha is journaled as a provenance record.
Definition 5 (Orchestration): An orchestration O = (A, G, S_0, M_0) consists of: - A = {alpha_1, ..., alpha_n}, a set of agents - G, a coordination graph defining which agents may communicate and in what order (the topology from Section III) - S_0, the initial shared state - M_0, the initial message set
An orchestration proceeds by executing agents according to G. At each step, the executing agent receives its input messages from the message queue, reads the current shared state, produces output messages, and may update the shared state. All three operations are journaled.
Definition 6 (State Transition): A state transition is a tuple delta = (t, agent, S_before, S_after, messages_in, messages_out, spec) where t is a step counter, agent is the executing agent, S_before and S_after are state snapshots, messages_in and messages_out are the typed messages consumed and produced, and spec is the specification governing this step.
Proposition 1 (Deterministic Replay): Given an orchestration O and a complete journal of state transitions J = {delta_1, ..., delta_k}, the orchestration can be deterministically replayed from any step delta_i by restoring S_before from delta_i and re-executing from that point.
Proof sketch: Since each delta records the complete state snapshot, messages consumed, and the specification version, replay from delta_i requires only the state S_before and the specification version. The agent's internal computation is a deterministic function of its inputs (assuming the LLM inference is seeded, which is a standard implementation requirement for reproducibility).
Proposition 2 (Provenance Completeness): If every agent invocation is journaled and every message carries a provenance record, then for any final output artifact a_k, the complete provenance DAG can be constructed by traversing the lineage field transitively.
Proof: By induction on the depth of the provenance DAG. Base case: an artifact with no inputs has a trivial provenance record. Inductive step: if artifact a_j has provenance record p_j with inputs {a_1, ..., a_m}, and each a_i has a complete provenance record by the inductive hypothesis, then the provenance DAG for a_j is complete.
We catalog the principal failure modes that arise when one or more pillars are absent.
When agents exchange free-form text, the semantic interpretation of messages drifts over the course of an orchestration. Agent A uses the term "validated" to mean "checked for syntax" while agent B interprets it as "checked for correctness." This drift is silent: neither agent detects the misalignment because both believe they are communicating successfully. Empirical studies of LLM-based agent communication [10] show that semantic drift accumulates over conversation turns and is a primary source of coordination failure.
When agents maintain private state, their world models diverge. Agent A discovers that a dependency has been updated and incorporates this fact into its subsequent reasoning. Agent B, working in parallel, continues to assume the old dependency version. The resulting outputs are individually plausible but jointly inconsistent. This failure mode is analogous to cache coherence problems in distributed systems and requires similar architectural solutions (a shared, versioned state store with consistency guarantees).
When artifacts carry no provenance metadata, the orchestration becomes a black box. A downstream consumer of the final output cannot determine which agent contributed which component, which inputs were used, or which specification governed the production. This makes debugging impossible in practice: the only recourse is to re-run the entire orchestration with logging, which may not reproduce the original failure if the system is non-deterministic.
The absence of all three pillars creates a cascading failure mode. An early agent produces an output with a subtle semantic error (semantic drift). A downstream agent incorporates this output into its state without detecting the error (state inconsistency). The error propagates through several more agents. By the time the final output is produced, the error has been transformed, amplified, and mixed with correct components. Without provenance, the error cannot be traced back to its origin. This cascading failure mode is the primary motivation for our architectural proposal: each pillar addresses a specific link in the failure chain.
We ground our claims in recent empirical and theoretical work.
Wu et al. [10] conducted a comprehensive survey of LLM-based agent communication and found that the majority of systems use unstructured natural language for inter-agent communication. They identified semantic drift, hallucination propagation, and context loss as the three most common failure modes. Their findings directly support our typed message primitive.
Talebirad and Nadiri [8] analyzed LLM-based agent societies and found