💻 computer science

Causal Past Logic for Runtime Verification of Distributed LLM Agent Workflows

This paper introduces Causal Past Logic (CPL), a source-level temporal logic integrated into the ZipperGen framework that enables distributed LLM agents to perform online runtime verification of control flow based on causally visible events rather than sequential logs, using a vector-clock monitor to ensure semantic correctness.

Original authors: Benedikt Bollig

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benedikt Bollig

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a team of specialized AI agents working together on a big project, like reviewing a piece of code before it gets merged into a software system. In the old way of thinking, we might imagine these agents talking to each other in a single, perfect line of conversation, like a transcript of a phone call where everyone hears everything in the exact same order.

But in reality, these agents are like people in different time zones working asynchronously. They send messages, do their own work, and make decisions at different speeds. Sometimes, Agent A makes a decision based on a message they received, not realizing that Agent B has already found a critical error and sent a new message that just hasn't arrived at Agent A's desk yet.

This paper introduces a new way to handle these decisions so the team doesn't make mistakes based on incomplete or outdated information. Here is the breakdown using simple analogies:

The Problem: The "Out-of-Order" Mailbox

Imagine you are a manager (the "Committer") waiting for reports from two inspectors: a "Test Runner" and a "Security Guard."

The Trap: You receive a report saying "Tests Passed." You are about to approve the project.
The Reality: The Security Guard actually found a huge bug after the test passed, but their new report is still stuck in the mail.
The Mistake: If you just look at a simple list of messages in the order they arrived, you might think everything is fine. But if you look at the causal reality (what you actually know at this exact moment), you don't know about the bug yet.

The paper argues that we shouldn't judge the team's decisions based on a "perfect, global log" of everything that happened. Instead, we must judge them based on what is causally visible to the person making the decision right now.

The Solution: "Causal Past Logic" (CPL)

The authors created a new "language" for the agents to use when making decisions. Think of this as a smart checklist that an agent can read before they click "Approve."

Instead of just asking, "Did I get a 'Pass' message?" the agent asks:

"Has the Test Runner causally seen that the tests passed, and have I causally seen any message saying they failed since then?"

This logic allows an agent to say: "I see the 'Pass' message, and I haven't seen a 'Fail' message yet, so I can proceed." It also allows them to check specific details, like: "Is this 'Pass' message about the same version of the code I'm looking at right now?"

How It Works: The "Vector Clock" Backpack

To make this work without a central boss watching everyone, every agent carries a backpack (called a "Vector Clock").

Every time an agent does something or receives a message, they update their backpack.
When they send a message to a friend, they zip their backpack inside the envelope.
When the friend receives the envelope, they unzip it and merge the sender's backpack with their own.

This backpack tells the agent exactly: "I know about 3 things the Test Runner did, and 2 things the Security Guard did." It doesn't matter if the messages arrived late; the backpack ensures the agent knows exactly what information is available to them at this specific moment.

The "Guard" Mechanism

In this system, the "Guard" isn't a security guard standing outside checking a logbook after the fact. The Guard is a rule written directly into the workflow.

Old Way: The workflow runs, finishes, and then a monitor checks, "Hey, you made a mistake because you missed a message!" (Too late to fix).
New Way (CPL): The workflow pauses at the decision point. The agent checks their "Causal Past Logic" rule. If the rule says, "I haven't seen the latest failure," the workflow automatically stops and asks for a re-check. It prevents the mistake before it happens.

The Real-World Example: The Code Review

The paper uses a code review scenario to prove this works:

The Setup: A "Committer" waits for a "Test Runner" and a "Security Agent."
The Scenario: The Test Runner says "Pass." The Committer is ready to merge.
The Twist: The Test Runner later finds a failure, but that message hasn't reached the Committer yet.
The Result: Because the Committer uses CPL, they look at their "causal past." They see the "Pass" and do not see the "Fail" (because it hasn't arrived). So, they proceed.
- Wait, isn't that dangerous? The paper says: No. The policy is "Merge if you haven't seen a failure." If the failure had arrived, the guard would have blocked the merge. If the failure arrives later, the system is designed to handle that (perhaps by re-checking later), but the Committer shouldn't be blamed for not knowing the future.

Summary

This paper gives distributed AI agents a way to make smart, safe decisions based on what they actually know right now, rather than what a perfect observer would know later. It uses a "backpack" system to track information flow and a special "logic language" to ensure agents only move forward when the causal evidence supports it. This turns runtime monitoring from a "post-mortem" (looking at the body after the crime) into a "traffic light" (stopping the car before the crash).

Technical Summary: Causal Past Logic for Runtime Verification of Distributed LLM Agent Workflows

Problem Statement
Distributed Large Language Model (LLM) agent workflows, where multiple agents interact asynchronously without shared memory, cannot be effectively monitored as if they produced a single sequential log. In asynchronous executions, a decision made by an agent (a "lifeline") depends only on events that are causally visible to it. An event appearing earlier in a global sequential log may not yet be known locally, while a locally recent event may not reflect the latest state of a remote agent.

Existing runtime verification approaches often rely on sequential traces or post-hoc log analysis. However, for agent workflows, this is insufficient because monitoring should influence the execution at the point of decision. If a decision-maker (e.g., a Committer) has not causally seen a clean test result, the system should not merge and report a violation later; it should block the merge or request a re-run immediately. Furthermore, standard guard mechanisms in LLM applications often treat execution as a sequential log, ignoring the causal structure required for correct distributed decision-making.

Methodology
The authors extend the ZipperGen framework, a choreographic programming system for distributed LLM agents, by introducing Causal Past Logic (CPL).

Formal Model (MSCs): Executions are modeled as Message Sequence Charts (MSCs), where events are distributed over lifelines. The causal order is defined by the reflexive transitive closure of local succession and message delivery. Each event carries a valuation of local variables.
Causal Past Logic (CPL): CPL is a small past-time temporal logic designed as a source-level guard language.
- Syntax: Formulas include standard past-time modalities (Previous $Y$ , Since $S$ ) interpreted along a single lifeline, and a causal modality $@A(\phi)$ which evaluates $\phi$ at the latest event of lifeline $A$ that is causally visible to the current event.
- Variable Access: The logic supports terms like $@A.x$ , which read the value of variable $x$ at the latest causally visible event of lifeline $A$ .
- Semantics: A guard $\phi@A$ is evaluated locally by the owner lifeline $A$ at a decision point (branch or loop). The truth value determines the control flow. The logic is non-strict: if no event of $A$ is visible, the formula evaluates to false.
Online Monitoring Algorithm:
- The authors propose a distributed monitoring algorithm where each lifeline maintains a vector clock and latest-value views.
- State: Each agent maintains a vector clock to track the number of events seen from every other lifeline. It also maintains a partial map of "latest-value views" for boolean formulas and variable values from other lifelines.
- Propagation: When an agent sends a message, it attaches its current vector clock and latest-value views. Upon receiving a message, the agent merges these views with its local state, updates its vector clock, and re-evaluates all guards bottom-up.
- Correctness: The algorithm ensures that the locally computed monitor value coincides with the denotational semantics of the guard over the MSC.

Key Contributions

Causal Past Logic (CPL): A novel logic for distributed agent workflows that combines standard past-time operators with causal access to the latest visible state of other agents. It allows guards to express conditions like "the required tests passed and no failure has been seen since, in the causal past."
Source-Level Guards: Unlike external monitors that check logs post-hoc, CPL formulas are integrated into the workflow source code. They are evaluated online by the decision-maker to influence control flow directly.
Distributed Monitoring with Vector Clocks: An efficient online monitoring algorithm that uses vector clocks and latest-value views to track causal visibility without requiring a central observer or a global sequential log.
Formal Verification: The definitions of MSCs, CPL satisfaction, the local evaluator, and the monitor-correctness theorem are mechanized and verified in Lean 4. The paper proves that the local runtime evaluation of a guard matches its denotational semantics at the current event.
Prototype Implementation: A prototype implementation in the ZipperGen framework (Python) demonstrates the feasibility of the approach, showing how guards can compare variables across lifelines (e.g., ensuring a test result corresponds to the current merge candidate).

Results

Theoretical: The paper proves Lemma 1 (Local evaluation correctness) and Lemma 2 (Monitor-state invariants), culminating in Theorem 1 (Monitor correctness). These proofs establish that the distributed algorithm correctly computes the truth value of any CPL formula based on the causal past visible to the owner lifeline.
Practical: The prototype implementation in ZipperGen successfully handles the example of a distributed code review, where a Committer decides to merge a patch only if it causally sees passing tests and security scans for the specific candidate, blocking the merge if a failure is visible in the causal past.

Significance
The paper argues that runtime verification for distributed LLM agent workflows must move beyond sequential log analysis. By treating monitoring as an integral part of the coordination language (via source-level guards), the system can make correct decisions based on the causally visible information available at the decision point, rather than waiting for a global log or a central observer. This approach addresses the fundamental difficulty of distributed programming where local decisions depend on partial causal views. The work bridges the gap between choreographic programming (global specifications projected to local agents) and runtime enforcement, ensuring that safety and coordination properties are enforced dynamically and causally correctly.