Decoupling Correctness from Policy: A Deterministic Causal Structure for Multi-Agent Systems

Zhiyuan Ren, Tao Zhang, W. ChenarXiv 2025 · DOI · arXiv

Abstract

In distributed multi-agent systems, correctness is often entangled with operational policies such as scheduling, batching, or routing, which makes systems brittle since performance-driven policy evolution may break integrity guarantees. This paper introduces the Deterministic Causal Structure (DCS), a formal foundation that decouples correctness from policy. We develop a minimal axiomatic theory and prove four results: existence and uniqueness, policy-agnostic invariance, observational equivalence, and axiom minimality. These results show that DCS resolves causal ambiguities that value-centric convergence models such as CRDTs cannot address, and that removing any axiom collapses determinism into ambiguity. DCS thus emerges as a boundary principle of asynchronous computation, analogous to CAP and FLP: correctness is preserved only within the expressive power of a join-semilattice. All guarantees are established by axioms and proofs, with only minimal illustrative constructions included to aid intuition. This work establishes correctness as a fixed, policy-agnostic substrate, a Correctness-as-a-Chassis paradigm, on which distributed intelligent systems can be built modularly, safely, and evolvably.

Introduction: The Entanglement Problem

In traditional distributed multi-agent systems (MAS), correctness and policy are deeply entangled. "Correctness" typically refers to the integrity of the system's history—knowing exactly what happened and in what order. "Policy" refers to the mechanics of execution: how messages are batched, which agent gets priority, or how data is routed.

The problem is that when these two are intertwined, the system becomes brittle. If an engineer updates a routing policy to improve latency, they might inadvertently break the guarantees of the causal history, leading to non-deterministic outcomes or "structural ambiguity." Current models like Conflict-free Replicated Data Types (CRDTs) ensure that everyone eventually agrees on a final value, but they often ignore the causal path taken to get there. This paper argues that for complex, collaborative agents, the "how" (the structure of the history) is just as important as the "what" (the final state).

The Deterministic Causal Structure (DCS)

To resolve this entanglement, we propose a minimal axiomatic theory consisting of five core constraints required to guarantee a unique, deterministic history:

  1. Localized Weak Fairness: Ensures all relevant information is eventually delivered.
  2. Directed-Complete Join-Semilattice: Requires the state update mechanism to be order-agnostic (associative, commutative, and idempotent).
  3. Contribution as an Immutable Fact: Every event must have a globally unique ID (rid) and immutable content.
  4. Immutability of Causal Linkage: The "parents" (predecessors) of an event must be fixed at creation.
  5. Causal Well-Formedness: An agent can only reference events it has already observed, preventing causal loops.
Figure 2: The structure of a contribution $c_i$, illustrating the axioms of immutable identifiers, payloads, and fixed causal links to parent contributions.

Using these axioms, we provide formal proofs for the existence and uniqueness of the DCS—represented as a Provenance Directed Acyclic Graph (DAG). As long as these axioms are met, any two executions with the same set of events will result in isomorphic (identical) causal graphs, regardless of the underlying delivery policies.

Correctness-as-a-Chassis

This is the paper's central metaphor: correctness is the rigid, verifiable frame (the DCS), while the operational policy is the "engine" mounted upon it. You can swap the engine for a more powerful one without redesigning the frame.

Figure 1: The DCS framework allows heterogeneous operational policies to converge on a unique deterministic causal structure, decoupling performance optimizations from system integrity.

By separating these layers, we distinguish between Layer 1 (Causal History Correctness)—did we agree on what happened?—and Layer 2 (Application Semantic Correctness)—does that history violate business rules (e.g., a double-spend)? DCS automates Layer 1, allowing developers to focus purely on the logic of Layer 2. Simulations confirmed that radically different agent behaviors (from simple heuristics to complex reinforcement learning) converged to the exact same Provenance DAG in 100% of test cases where the generated event set was the same.

Key Results and Insights

  • Existence & Invariance: We have proven that the DCS is unique up to isomorphism and completely independent of scheduling, batching, or routing policies.
  • Axiom Minimality: Through counterexamples, we show that removing any of the five axioms causes the system to collapse into ambiguity (a 100% "ambiguity rate" in simulations).
  • Superiority over CRDTs: DCS provides a "strictly stronger" guarantee than CRDTs. While CRDTs resolve value conflicts, they are "causally indifferent." DCS resolves "Structural Ambiguity," ensuring that the specific relationship between events is preserved.
  • A Boundary Principle: Much like the CAP theorem or FLP impossibility result, DCS represents a boundary of asynchronous computation: deterministic correctness is only preserved within the expressive power of a join-semilattice.

Limitations and Future Work

The current theory assumes "honest-but-fallible" agents (crash-stop model) and does not yet account for malicious agents intentionally trying to subvert the history. Furthermore, maintaining a complete Provenance DAG introduces storage and communication overhead. Future work will focus on extending the theory to Byzantine-aware DCS by integrating cryptographic signatures and developing "graph pruning" techniques for real-world engineering trade-offs. We aim to develop a dedicated programming framework to help engineers build "DCS-native" applications that are modular, safe, and evolvable.

Summary updated

Abstract

In distributed multi-agent systems, correctness is often entangled with operational policies such as scheduling, batching, or routing, which makes systems brittle since performance-driven policy evolution may break integrity guarantees. This paper introduces the Deterministic Causal Structure (DCS), a formal foundation that decouples correctness from policy. We develop a minimal axiomatic theory and prove four results: existence and uniqueness, policy-agnostic invariance, observational equivalence, and axiom minimality. These results show that DCS resolves causal ambiguities that value-centric convergence models such as CRDTs cannot address, and that removing any axiom collapses determinism into ambiguity. DCS thus emerges as a boundary principle of asynchronous computation, analogous to CAP and FLP: correctness is preserved only within the expressive power of a join-semilattice. All guarantees are established by axioms and proofs, with only minimal illustrative constructions included to aid intuition. This work establishes correctness as a fixed, policy-agnostic substrate, a Correctness-as-a-Chassis paradigm, on which distributed intelligent systems can be built modularly, safely, and evolvably.
BibTeX
@misc{ren2025decoupling,
  author = {Zhiyuan Ren and Tao Zhang and W. Chen},
  title = {{Decoupling Correctness from Policy: A Deterministic Causal Structure for Multi-Agent Systems}},
  year = {2025},
  eprint = {2510.05621},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.05621},
  howpublished = {arXiv},
}

Loading related content...

Figure