Causal Past Logic for Runtime Verification of Distributed LLM Agent Workflows

Benedikt Bollig · 2026

Read Causal Past Logic for Runtime Verification of Distributed LLM Agent Workflows by Benedikt Bollig (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-2605-20923.txt.

Introduction

Benedikt Bollig studies runtime monitoring for distributed language-model-agent workflows using causal past logic. In asynchronous execution, a decision can only rest on events causally visible to the lifeline making it. An event earlier in some log may still be hidden locally. He extends the ZipperGen agent-workflow design with Causal Past Logic, adapting past-time logic to guards in if-blocks and while loops. A guard can read the latest causally visible event of other lifeline and chosen variables stored there.

Catalog record

CREATORBenedikt Bollig
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47276
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.20923

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Causal Past Logic for Runtime Verification of Distributed LLM Agent Workflows Benedikt Bollig Abstract Distributed LLM agent workflows should not be monitored as if they produced a single sequential log. In an asynchronous execution, a decision can only depend on events that are causally visible to the lifeline that makes it: an event that appears earlier in some log may still be unknown locally. We extend the ZipperGen agent-workflow framework with Causal Past Logic (CPL), a small past-time temporal logic for guards in conditionals and while loops. In addition to standard past-time modalities such as previous and since, a guard can inspect the latest causally visible event of another lifeline and selected variables stored there. The formula is a source-level guard: it is evaluated online by the owner lifeline and can influence control flow at runtime. We give a vector-clock monitor with latest-value views and prove that the locally computed monitor value coincides with the denotational semantics of the guard at the current event. Thus runtime verification becomes part of the coordination language itself, rather than a post-hoc check over an execution log. 1 Introduction Large language models have led to the development of LLM agents, where language models are equipped with tools and can execute actions. Many useful applications do not rely on a single agent, but on several interacting agents that work on separate tasks and maintain separate contexts. This can improve efficiency and can also make the system easier to structure: each agent has its own role, its own local information, and its own interaction history. In practice, this separation may also reduce unnecessary context growth. However, these agents still need to communicate. They exchange plans, findings, approvals, warnings, and intermediate results over communication channels. At this point, agent workflows become distributed systems. This is useful, but it also brings back the usual difficulties of distributed programming. Failures are not limited to wrong LLM outputs. A committer may merge a patch whose tests have since failed. An executor may rely on an approval that was given for an earlier version. A reviewer may see a message that is locally the latest one received, although it does not contain the latest information available elsewhere in the system. Runtime verification [ 30 , 6 , 4 ] is a natural way to complement static coordination guarantees in this setting. In classical runtime verification, one specifies properties of executions, often in a temporal logic, and monitors check at runtime whether the current execution satisfies the specification. If something goes wrong, the monitor can raise an alarm. For agent workflows, however, it is often not enough to report a violation after the fact. Monitoring should also affect the execution at the point where a decision is made. If a committer has not seen a clean test result in its causal past, the right response is not to merge and report a violation later. The workflow should instead take another branch: block the merge, request a re-run, or escalate. We develop this idea for ZipperGen [ 11 ] . ZipperGen programs are written as global workflows and projected to local agent programs that communicate asynchronously. It follows the general philosophy of choreographic programming [ 14 , 35 , 43 , 24 ] : the programmer writes the coordination from a global point of view, and the framework derives the local behavior of the individual agents. We use the term lifeline for the local participant, usually an agent, that executes its part of the workflow. In ZipperGen, branch and loop decisions have an explicit owner lifeline. The projection inserts control broadcasts so that the lifelines that need to know a decision are informed about it. The point of this paper is that even with such a projection discipline, which guarantees deadlock-freeness, runtime decisions may depend on causal information that is not easy to track by hand. Messages exchanged between agents create causal dependencies. As a result, the latest message received by an agent is not necessarily the latest relevant information produced by another agent. Conversely, information that appears earlier in a sequential log may not be causally visible to the agent that is about to make a decision. Thus, for distributed agent workflows, monitoring should not be interpreted over an arbitrary sequential log. It should be interpreted over causally structured executions. Since guards are evaluated by their owner lifeline, monitoring is distributed as well: a decision cannot rely on a complete sequential log maintained by a central observer. The same issue also arises with per-lifeline parallel composition. Several local actions of the same lifeline may be enabled at the same time, and their actual order may be chosen at runtime rather than fixed statically by the source workflow. Runtime guards should therefore be evaluated against the causal information available at the event where the decision is actually made. To address this, we extend the guard language of ZipperGen with Causal Past Logic (CPL), a small past-time logic interpreted over message sequence charts (MSCs), which depict lifelines and the messages exchanged between them. A guard is written as \varphi\mathord{\mathtt{@}}A and is evaluated locally by lifeline A , which owns the corresponding branch or loop. CPL formulas can express causal-temporal facts such as “the owner has causally seen that the tests passed, and has not seen any later visible failure”. They can also combine such facts with identity checks, for instance whether the visible test result concerns the same merge candidate as the current proposal. Unlike external runtime specifications, CPL formulas are source-level guards. They are not checked beside the workflow after the fact: their truth values choose the next branch or loop step. This is why the logic is past-time: at each decision point, the owner lifeline must determine the guard from the information causally visible to it. An external monitor could only report verdicts on an execution that has already happened. A guard, on the other hand, determines what the execution becomes. This perspective also differs from many guardrail mechanisms for LLM applications, which treat the execution as a sequential log. Such logs are useful for debugging and auditing, but workflow control needs a different notion of past: what matters is what is causally visible at the decision point. Contributions. We extend ZipperGen guards with Causal Past Logic formulas that are evaluated at runtime and influence the control flow at decision points. Formally, CPL formulas are interpreted at runtime events, and guard evaluation is represented by a choice event on the owner lifeline. In addition to standard past-time temporal modalities, such as previous and since along one lifeline, the logic contains causal past modalities and access to the values of variables at the latest visible event of a lifeline. This allows formulas to compare information from different lifelines. We give an online monitoring algorithm based on vector clocks and latest-value views, and prove that local runtime evaluation coincides with the denotational MSC semantics. We also report on a prototype implementation in ZipperGen ( https://zippergen.io ). Mechanization. We mechanized the definitions of MSCs, CPL satisfaction, the local evaluator, latest-value monitor state, receive-update propagation, and the monitor-correctness theorem in Lean 4 [ 37 ] . Clicking a badge or opens the corresponding source file. Outline.

Read the complete text