Causal-Temporal Event Graphs: A Formal Model for Recursive Agent Execution Traces

Formal Modeling of Recursive Agent Execution Traces with Causal-Temporal Event Graphs

Introduction and Motivation

This paper presents a rigorous formal model, the Causal-Temporal Event Graph (CTEG), for encoding execution traces in recursive agentic systems under strict single-parenthood semantics (2604.17557). CTEGs are motivated by agent-driven AI workflows—particularly those using LLMs—where auditable, explainable, and robust provenance for sequences of events and agent interactions is increasingly required by regulatory and reliability concerns. Standard linear temporal trace logs are inadequate for this setting because they fail to capture the nested, causally branching, and recursive structure of agent and subagent interactions. The CTEG formalism provides a concrete mathematical foundation that encodes both the causal and temporal structure of recursive agent traces, ensures well-formedness under composition, and supports essential infrastructural features such as relational database encoding and cryptographic commitment.

Structure of Causal-Temporal Event Graphs

A CTEG is defined as a rooted, directed acyclic graph (arborescence) where every non-root node has a unique parent, and each node is annotated with a strictly increasing timestamp and a type. The graph reflects the parent-child causality in event emission: each event is either directly emitted by an agent or arises as the outcome of a subagent invocation, with causality and temporality tightly coupled by a compatibility constraint (timestamps must strictly increase along causal paths).

The arborescent property of CTEGs admits robust properties:

• Each event’s full causal ancestry is uniquely specified.
• Composition is naturally defined via grafting: a subagent’s trace can be atomically attached at the invocation event in the parent, provided the causal-temporal compatibility criterion is satisfied.

This is exemplified in the recursive agent execution process and its global composition.

Figure 1: Recursive $\E_2$-agent execution, showcasing the nested invocation and emission structure (timestamps and types omitted).

The global trace formed by recursively composing subagent traces via grafting operations is as follows:

Figure 2: Global $\E_2$-execution trace for a multi-level agent-subagent computation (timestamps and types omitted).

A core lemma establishes that the graft of two CTEGs is again a CTEG if and only if the parent node’s timestamp is less than the root timestamp of the subagent’s CTEG, ensuring compositional closure and structural inductiveness.

Relational and Cryptographic Encodings

The CTEG structure is directly compatible with a natural relational database schema, supporting robust session tracking, pointer-based reconstruction, and serialization. Each node maps to a row indexed by session, type, timestamp, and causal parent, supporting efficient queries and stable storage—even in the face of partial agent failure.

Additionally, the arborescent structure aligns with Merkle tree commitments, enabling tamper-evident cryptographic receipts for agent session histories. This feature supports compliance and auditability guarantees critical for regulated AI deployment.

Agent Execution Dynamics and Hierarchical Closure

The execution semantics are constructed as two local operations:

• Direct Event Emission: An agent extends its trace by emitting events causally downstream from current nodes.
• Recursive Subagent Invocation: An agent delegates to a subagent, receives its completed trace, and grafts the result atomically into its own trace at the invocation node.

These operations are formalized as state transitions over sequences of typed temporal graphs, generating the ambient space $\mathcal{G}$ of finite-length execution sequences.

The recursive execution closure $\E_\infty$ is precisely the set of all sequences of CTEGs built by iterating these local operations from single causal roots, formalized via a monotone operator $\varphi$ on the power set of $\mathcal{G}$. This operator encodes the logical progression through direct emissions and subagent invocations, mirroring the actual recursive execution pattern of agentic systems.

The entire construction is characterized as an ascending Kleene chain: $\E_0 \subseteq \E_1 \subseteq \cdots \subseteq \E_\infty$ where each $\E_{d+1}$ is defined as the set of execution sequences allowing up to $d+1$ levels of nested subagent invocation.

Importantly, stabilization occurs at depth one: $\E_1 = \E_\infty$. Once subagent invocation is permitted, further recursive nesting does not expand the class of attainable (well-formed) execution traces. All possible traces can be reconstructed through an $\E_2$0 (i.e., direct emission) construction by appropriate topological sorting, reflecting the opacity of the subagent invocation interface—only the subagent’s completed trace, not its construction history, is exposed at the parent’s level.

This process, and the resulting evolution of the agent execution state, is depicted in:

Figure 3: Evolution from state $\E_2$1 to $\E_2$2 by direct event emission (left) and by subagent invocation (right).

Robustness, Limitations, and Extensions

The CTEG model is append-only: traces only grow, never retract, ensuring that every prefix of an execution sequence is also a valid CTEG. This property guarantees that incomplete or partially failed sessions retain full causal and temporal integrity and are directly serialisable.

The model distinguishes well-formed causal structure (as guaranteed by CTEG compositionality) from correct causal attribution, which is determined by specific local parenthood semantics—left explicitly open in this paper. Extensions to multi-parenthood or direct agent-to-agent communication scenarios may require generalization beyond strict arborescences.

CTEGs can accommodate richer type hierarchies at the application layer, but are flat at the formal level. The model is immediately extensible to alternative representations by treating subagent invocations as atomic nodes or by serializing broader classes of causality.

A crucial observation is that causal structure cannot, in general, be reconstructed from temporal event ordering alone, as demonstrated in:

Figure 4: Two causal structures yielding the same temporal projection, highlighting the impossibility of reconstructing causality from timestamps alone.

This underscores the operational need to build and maintain causal links as first-class citizens during agent execution rather than inferring them retroactively.

Implications and Future Directions

Practically, this work provides a foundation for designing agent-based AI workflows with robust traceability, composability, and compliance features in high-consequence environments. It defines the maximal space of well-formed execution traces under single-parenthood semantics, enables provable auditability via cryptographic receipts, and offers a direct serialization pathway for session history storage and replay.

Theoretically, the clean fixed-point characterization via monotone operators on complete lattices connects agent execution semantics to established results in domain theory and recursion, facilitating future extension and analysis. The transparency regarding compositional invariants and stabilization depth offers avenues for further research into observable recursion depth, locally-attributed causal semantics, and generalized compositional formalisms.

Conclusion

The CTEG formalism fills a gap in the formal modeling of recursive agentic execution, yielding compositional, robust, and cryptographically tractable traces that reflect both causality and temporality. Its closure and stabilization properties illuminate the structural invariants of agent interactions, providing a sound mathematical platform for further research and applied development in explainable, auditable agent-based AI systems.