Paper deep dive
Causal-Temporal Event Graphs: A Formal Model for Recursive Agent Execution Traces
Simon Foldvik
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/27/2026, 8:15:20 AM
Summary
The paper introduces Causal-Temporal Event Graphs (CTEGs) as a formal model for recording recursive agent execution traces. CTEGs are defined as rooted arborescences where nodes possess timestamps and types, ensuring timestamps strictly increase along causal paths. The model supports compositional construction through 'grafting' subagent traces into parent traces, maintaining a single-parenthood causal semantic. The authors prove that the recursive closure of these execution dynamics forms a hierarchy that stabilizes at the first level of recursion due to the opacity of subagent execution units. The formalism is compatible with relational database encoding and Merkle tree-based cryptographic commitments for session verification.
Entities (9)
Relation Signals (8)
CTEG → admits → Relational Database Encoding
confidence 100% · admits a natural relational database encoding
Causal-Temporal Event Graph → compatiblewith → Merkle Tree
confidence 100% · The arborescent structure of CTEGs is further compatible with cryptographic Merkle tree commitments
Causal-Temporal Event Graph → isa → Rooted Arborescence
confidence 100% · A CTEG is a rooted arborescence whose nodes carry timestamps and event types
Causal-Temporal Event Graph → isa → Rooted Arborescence
confidence 100% · A CTEG is a rooted arborescence whose nodes carry timestamps and event types
CTEG → supports → Merkle Tree
confidence 100% · The arborescent structure of CTEGs is further compatible with cryptographic Merkle tree commitments
Causal-Temporal Event Graph → uses → Single-Parenthood Causal Semantics
confidence 100% · under single-parenthood causal semantics
Grafting → composes → Causal-Temporal Event Graph
confidence 90% · The graft G1 ⊕ p (G2, r2) of two causal graphs... is again a causal graph
Grafting → preserves → CTEG Structure
confidence 90% · This is the case iff the adjoined grafting edge respects the causal-temporal compatibility criterion.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We introduce causal-temporal event graphs (CTEGs) as a formal model for fully resolved recursive agent execution records under single-parenthood causal semantics. We formalise direct event emissions and recursive subagent invocations as extension procedures on generic typed temporal graphs and show that the recursive closure $\mathscr{E}_\infty$ of the induced maximal dynamics starting from single causal roots consists entirely of finite sequences of CTEGs. A CTEG is a rooted arborescence whose nodes carry timestamps and event types, subject to the constraint that timestamps be strictly increasing along causal paths. We realise $\mathscr{E}_\infty$ as the increasing union of a recursive hierarchy $\mathscr{E}_0 \subseteq \mathscr{E}_1 \subseteq \cdots$ of agent execution levels parametrised by recursion depth, which is recognised as the ascending Kleene chain of a monotone operator $\varphi$ admitting $\mathscr{E}_\infty$ as its least fixed point. Although the introduction of the full hierarchy is natural, stabilisation occurs already at $\mathscr{E}_1$ if one insists that the internal construction of a subagent execution trace be a delegated and opaque computational unit. The CTEG formalism supports compositional construction of globally well-formed execution traces from local agent behaviour without centralised coordination, preserves well-formedness under partial execution failure, and admits a natural relational database encoding. The arborescent structure of CTEGs is further compatible with cryptographic Merkle tree commitments for tamper-evident session verification.
Tags
Links
- Source: https://arxiv.org/abs/2604.17557v1
- Canonical: https://arxiv.org/abs/2604.17557v1
Trouble viewing inline? Open PDF directly →
Full Text
44,375 characters extracted from source content.
Expand or collapse full text
Causal-Temporal Event Graphs: A Formal Model for Recursive Agent Execution Traces Simon Foldvik111Independent researcher: research@simonfoldvik.no April 19, 2026 Abstract. We introduce causal-temporal event graphs (CTEGs) as a formal model for fully resolved recursive agent execution records under single-parenthood causal semantics. We formalise direct event emissions and recursive subagent invocations as extension procedures on generic typed temporal graphs and show that the recursive closure ℰ∞ E_∞ of the induced maximal dynamics starting from single causal roots consists entirely of finite sequences of CTEGs. A CTEG is a rooted arborescence whose nodes carry timestamps and event types, subject to the constraint that timestamps be strictly increasing along causal paths. We realise ℰ∞ E_∞ as the increasing union of a recursive hierarchy ℰ0⊆ℰ1⊆⋯ E_0 E_1 ·s of agent execution levels parametrised by recursion depth, which is recognised as the ascending Kleene chain of a monotone operator φ admitting ℰ∞ E_∞ as its least fixed point. Although the introduction of the full hierarchy is natural, stabilisation occurs already at ℰ1 E_1 if one insists that the internal construction of a subagent execution trace be a delegated and opaque computational unit. The CTEG formalism supports compositional construction of globally well-formed execution traces from local agent behaviour without centralised coordination, preserves well-formedness under partial execution failure, and admits a natural relational database encoding. The arborescent structure of CTEGs is further compatible with cryptographic Merkle tree commitments for tamper-evident session verification. Contents 1 Introduction 1.1 Outline 1.2 Notation 2 Causal-Temporal Event Graphs 2.1 Causal, Temporal, and Type Structures 2.2 Grafting 3 Recursive Execution and Stabilisation 3.1 Local Dynamics 3.2 The Recursive Execution Hierarchy 4 Conclusion References 1. Introduction Recent years have seen a surge in the use of agentic workflows, wherein large language models (LLMs) play a central role in guiding artificial intelligence systems into solving generic, open-ended problems from natural language inputs. These systems are by their nature probabilistic, hence possess an inherent element of nondeterminism. This poses a challenge when such workflows are deployed to real-world decision-making systems in fields where regulatory frameworks impose requirements on explainability, auditability, and compliance with business and legal requirements. A common response is to capture the sequence (ek)(e_k) of events produced by an agentic system (its execution log), enabling the reconstruction of full agent session chronologies for downstream inspection and replay. This is suitable for studying the temporal relationships in agentic executions, but we demonstrate by means of example in Remark˜2.13 that plain linear traces alone, without explicitly encoded causal parent structure, are not well-suited to also capture the underlying causal relationships between events in agentic workflows. A tool output is the result of a tool invocation, and it matters not only in which order they come, but also which tools caused which outcomes. While agent execution tracing is an increasingly active engineering practice and area of research (see for instance [undefc, undefd] and the references therein), formal treatments of recursive agent causal structure appear to remain limited. We introduce causal-temporal event graphs (CTEGs) as a formal model for fully resolved recursive agent execution records under strict single-parenthood causal semantics. A CTEG is a rooted arborescence with typed nodes and timestamps, subject to the constraint that timestamps be strictly increasing along causal paths (Definition˜2.4). The formalism is motivated by distributed agentic production systems, wherein agents first declare their event type hierarchies and then asynchronously emit typed events in response to previous execution states, forming potentially independent cascading causal chains. The present version focuses on the formal model and its basic closure properties, with broader positioning relative to adjacent tracing frameworks deferred to future revisions. Figure 1. Recursive ℰ2 E_2-agent execution. Timestamps and types are omitted for clarity. The computational model we have in mind is that of a parent agent invoking any number of worker agents (the subagents), which in turn may invoke further subagents as part of their own executions. Subagents are responsible for the construction of their own internal execution traces, passing the finished subtraces up to the invoking parent agents as completed units. The parents then atomically graft the subagent traces into their own execution records at the subagent invocation nodes. This creates an opaque subagent invocation interface and a natural separation of concerns: Each subtrace construction remains small and records precisely the causal relationships the corresponding agent is in a position to assert. The procedure is illustrated in Fig.˜1, with the resulting global execution trace depicted in Fig.˜2. The main contribution of this paper is the identification and formalisation of CTEGs as natural objects for capturing fully resolved global execution traces in recursive agentic systems under single-parenthood causal semantics, together with a local-to-global compositional model of their construction. We formalise two local dynamical operations (direct event emissions and recursive subagent invocations) and show that the smallest set ℰ∞ E_∞ of execution sequences closed under these operations starting from single causal roots (the recursive closure) consists entirely of finite sequences of CTEGs (Theorem˜3.14). This gives a formal account of how globally well-formed causal structure can be assembled in recursive agentic systems from delegated subagent trace constructions without centralised coordination, and this remains true even in the face of partial agent failure. The resulting arborescent traces admit natural relational database encodings and support tamper-evident cryptographic commitments via Merkle tree computations. The proof proceeds by introducing a recursive hierarchy (1.1) ℰ0⊆ℰ1⊆⋯ E_0 E_1 ·s of agent execution levels parametrised by recursion depth, whose union ℰ∞=⋃ℰd E_∞= E_d is shown to be the least fixed point of a monotone operator φ on the power set of all finite sequences of typed temporal graphs. Level ℰ0 E_0 contains only direct event emissions, while ℰd+1 E_d+1 is constructed from level ℰd E_d by additionally allowing recursive ℰd E_d-subagent invocations. The causal links are built and maintained at this local level through child node pointers to either the newly emitted events or the causal root of the recursive ℰd E_d-subagent invocation. Even though the introduction of the full ℰd E_d-hierarchy is natural, stabilisation occurs already at ℰ1 E_1. This is a consequence of the opacity of the subagent invocation interface, wherein parent agents receive only the completed subagent execution records and not their construction histories. Any CTEG admits an ℰ0 E_0-construction by topological sorting, hence any ℰd E_d-invocation with d≥1d≥ 1 might as well have been an ℰ0 E_0-invocation from the parent’s point of view. The single-parenthood semantics is partly motivated by the following. Suppose a parent agent invokes a subagent, after whose completion the parent decides to emit a continuation event. Although events internal to the subagent execution may have influenced the parent’s decision to produce the continuation, or even informed the contents of the continuation event itself, the parent agent has no principled basis (short of inspecting the subagent’s internal execution) for determining which internal subagent events should be causally linked to the continuation. To remedy this tension one could either relax the insistence that global execution traces be fully resolved in place (allowing subagent invocations as atomic execution graph nodes), or parent agents could break epistemic locality and inspect subagents’ internal affairs. We discuss these limitations and alternatives further in Section˜4. Figure 2. Global ℰ2 E_2-execution trace for the agentic computation outlined in Fig.˜1. Timestamps and types are omitted for clarity. Our theory thus addresses the additional challenge of building and maintaining well-formed global causal structure in recursive agentic systems and shows that it suffices to solve this locally: Each agent manages its own (small) execution trace internally, subagent traces are grafted in at the parent agent’s execution root upon completion (or failure), and the resulting global trace is guaranteed to be a well-formed CTEG. The question of what constitutes correct (as opposed to well-formed) causal structure must be determined against choices of local parenthood semantics, which are orthogonal to the CTEG formalism in its current form. Instead of asserting which local semantics are most appropriate, CTEGs encode those local assignments once made and are sufficiently general to accommodate different semantic choices. Discussing which local semantic choices should be made is therefore beyond the scope of the current paper. 1.1. Outline The paper is organised as follows. In Section˜2 we introduce causal-temporal event graphs, the criterion under which two CTEGs may be composed to preserve the CTEG structure, along with their relational encoding and cryptographic commitments via Merkle hashes. In Section˜3 we formalise the recursive ℰd E_d-hierarchy model of cascading agent executions based on direct event emissions and subagent invocations, characterise their union ℰ∞ E_∞ both as the least fixed point of a monotone operator and the recursive closure of the maximal dynamics, and prove that all agent execution sequences arising in this way are finite sequences of CTEGs. We conclude in Section˜4 with a brief discussion of limitations and natural extensions of the current work. 1.2. Notation We write ‘iff’ in place of ‘if and only if’, 0∈ℕ0 is a natural number, (G)N(G) denotes the set N of nodes of a directed graph G=(N,E)G=(N,E), and ℰ(G)⊆N×NE(G) N× N its set E of edges. If f:A→Cf A→ C and g:B→Cg B→ C are maps with disjoint domains, then f⊔gf g is the unique map A∪B→CA∪ B→ C which restricts to f,gf,g on A,BA,B, respectively. (X) P(X) denotes the power set of X. 2. Causal-Temporal Event Graphs In this section we present the static view of causal-temporal event graphs (CTEGs), a formal model for encoding causal and temporal relationships in recursive agent execution traces along with their event types under single-parenthood causal semantics. We state a fundamental lemma on when two CTEGs may be composed to preserve the CTEG structure, and show that causal structure may not be faithfully recovered from temporal structure alone. We observe that CTEGs admit natural relational database encodings and support tamper-evident cryptographic commitments via Merkle hashes. This lays the foundation for the formal treatment of the agent execution graph dynamics presented in Section˜3. 2.1. Causal, Temporal, and Type Structures By a causal graph we mean a finite, non-empty directed acyclic graph G=(N,E)G=(N,E) (where (G)≔NN(G) N is the node set and ℰ(G)≔E⊆N×NE(G) E N× N the edge set), with a distinguished root node r∈(G)r (G) (called the causal root and henceforth denoted rG≔r_G r) such that G is an arborescence with root r: (1) All nodes n∈(G)∖rn (G) \r\ are reachable from r. (2) Every n∈(G)∖rn (G) \r\ has exactly one incoming edge. (3) There are no edges into r. Remark 2.1. In a causal graph G, the causal path from the root r to any n∈(G)∖rn (G) \r\ is in fact unique. If not, choose n≠rn≠ r admitting two distinct directed walks w,w′w,w from r minimising ℓ(w)+ℓ(w′) (w)+ (w ) (sum of lengths) by well-ordering. Since n has a unique incoming edge, both walks must pass through the same immediate predecessor, yielding a smaller counterexample. Contradiction. By a temporal structure on a causal graph G we mean an assignment t:(G)→ℝt (G) of timestamps to the nodes. It is causally compatible with G iff it is strictly increasing along causal paths: If m,n∈(G)m,n (G) and n is reachable from m, then t(m)<t(n)t(m)<t(n). It is enough to verify this criterion along directed edges (m,n)∈ℰ(G)(m,n) (G) by transitivity. Remark 2.2 (Cause-effect). Hence for a causally compatible temporal structure, a cause must strictly precede its effects, but sibling nodes sharing the same causal parent are allowed to be simultaneous. Remark 2.3 (Tie-breaking). Our temporal structures assume real-valued timestamps with strict ordering along causal paths. In practice, finite clock resolution may require tie-breaking mechanisms when two causally related events receive identical timestamps from the system clock. Let T be a finite, non-empty set of types. By a type map on a causal graph G we mean an assignment τ:(G)→Tτ (G)→ T of types to its nodes. Combining all of the above, we obtain the central structure of this paper. Definition 2.4 (Causal-temporal event graphs). A causal-temporal event graph (CTEG) over a type set T is a causal graph G equipped with a causally compatible temporal structure t:(G)→ℝt (G) and a type map τ:(G)→Tτ (G)→ T. The full CTEG is denoted (G,r,t,τ)(G,r,t,τ), where r is the unique causal root. Remark 2.5 (Flat type structures). The type set T is flat by design: A CTEG records event types but imposes no relations between them. Richer type structures, such as partially ordered type hierarchies, are treated as application-layer concerns rather than part of the causal-temporal formalism. Remark 2.6 (Cryptographic session commitments). The arborescent structure of CTEG execution graphs admits tamper-evident cryptographic commitments of agent session histories, partial or complete, via Merkle tree computations. The Merkle hash [undefb] of a CTEG may thus serve as a cryptographically verifiable receipt of an agentic computation. Remark 2.7 (Relational database encoding). CTEG session traces admit natural relational representations in standard database formats. This is robust also in the face of agent failure, as even partial execution traces of agentic computations following the assumptions of this paper are guaranteed to be CTEGs. To represent a CTEG (G,r,t,τ)(G,r,t,τ) in relational database format, first register the session to receive a globally unique session identifier. Each node of G is then written into an append-only node table, receiving a unique node identifier, a timestamp derived from the temporal structure t, a reference to the session identifier, the node type derived from the type map τ, and an opaque payload column for the node data. Each non-root node additionally stores a reference to its unique causal parent node, which exists and is unique by the arborescence property. The root node has no parent reference. With agentic CTEG session persistence as outlined above, full causal and temporal session reconstruction reduces to a single query fetching all nodes with a given session identifier followed by pointer resolution. 2.2. Grafting Given two causal graphs (G1,r1)(G_1,r_1) and (G2,r2)(G_2,r_2) with disjoint node sets, there is a natural grafting operation attaching the root of G2G_2 to a select node p∈(G1)p (G_1) (see Fig.˜3). It is denoted G1⊕p(G2,r2)G_1 _p(G_2,r_2) and defined as follows. Figure 3. Illustrating the graft of a causal graph G2G_2 into G1G_1. Definition 2.8 (Graft). The graft G1⊕p(G2,r2)G_1 _p(G_2,r_2) of two causal graphs G1G_1 and G2G_2 with disjoint node sets at p∈(G1)p (G_1) is the directed graph G defined by (2.1) (G) (G) ≔(G1)∪(G2), (G_1) (G_2), ℰ(G) (G) ≔ℰ(G1)∪ℰ(G2)∪(p,r2). (G_1) (G_2)∪ \(p,r_2) \. Remark 2.9. The graft G defined in Definition˜2.8 is thus a directed graph consisting of the same nodes and edges as its constituent subgraphs, but with a new edge joining p∈(G1)p (G_1) to r2∈(G2)r_2 (G_2) adjoined. It is again a causal graph with causal root r1r_1. This follows since the grafting operation only realises the following structural changes: • The in-degree changes from zero to one at the causal root r2r_2 of G2G_2. • All other nodes retain their in-degrees. • Reachability of all nodes from r1r_1 holds by transitivity through p. • No cycles are created, since any cycle would be pushed into one of the acyclic subgraphs G1G_1 or G2G_2 since it could not have traversed the new edge (p,r2)(p,r_2) whilst starting and ending at the same node. The following lemma answers the question of when the graft of two CTEGs preserves the CTEG structure. This is the case iff the adjoined grafting edge respects the causal-temporal compatibility criterion. Lemma 2.10 (CTEG composition lemma). Let (Gi,ri,ti,τi)(G_i,r_i,t_i, _i) for i=1,2i=1,2 be two CTEGs with type sets TiT_i and disjoint node sets. Let (2.2) G≔G1⊕p(G2,r2)G G_1 _p(G_2,r_2) be their graft at p∈(G1)p (G_1). Then G equipped with the temporal structure t1⊔t2t_1 t_2, type map τ1⊔τ2 _1 _2, and causal root r1r_1 is a CTEG over T1∪T2T_1∪ T_2 iff (2.3) t1(p)<t2(r2).t_1(p)<t_2(r_2). We call this the causal-temporal compatibility criterion for CTEG grafting. Remark 2.11. Recall that t1⊔t2:(G)→ℝt_1 t_2 (G) is the unique map which restricts to tit_i on (Gi)N(G_i) for i=1,2i=1,2, and similarly for τ1⊔τ2 _1 _2. Proof. Immediate. ∎ Remark 2.12 (Type contracts). This lemma mirrors the setup in production systems wherein agent A1A_1 first declares its type set T1T_1 to communicate its possible event types to type checkers, and similarly agent A2A_2 declares T2T_2. The execution of A1A_1 alone would produce a CTEG over T1T_1, whereas the execution of A1A_1 invoking A2A_2 as a subagent would produce a CTEG over T1∪T2T_1∪ T_2. This avoids the need for a centralised type hierarchy and makes the streaming contract between agents and their invokers explicit. Remark 2.13. We conclude this section by observing that causal structure may not be faithfully reconstructed from temporal structure alone. A counterexample will suffice. By a temporal projection of a causal graph G with respect to a causally compatible temporal structure t:(G)→ℝt (G) , we mean a bijective enumeration (ni)i=0m(n_i)_i=0^m of its node set (G)N(G) such that (2.4) t(n0)≤⋯≤t(nm).t(n_0)≤·s≤ t(n_m). It is now easy to see that (r,a,b,c)(r,a,b,c) is the temporal projection of both G and G′G in Fig.˜4, even though these have different causal structures. Figure 4. Two causal structures with the same temporal projection. This precludes the hope of any strategy reconstructing a causal structure from the temporal structure alone. In particular, any implementation attempting to reconstruct a CTEG by observing the temporal sequence of events emitted by an agent (for instance, by externally decorating an asynchronous generator and listening to the temporal sequence of emitted events) will lose causal information unless it is also willing to inspect internal agent states (or those of its emitted events) in an attempt to infer the missing causal links. The causal structure is therefore best constructed and maintained internally by agents during execution, rather than inferred after the fact. 3. Recursive Execution and Stabilisation In this section we demonstrate how CTEGs arise naturally under the iterated local dynamics of direct event emissions and recursive subagent invocations starting from single causal roots. More precisely, we prove that the smallest set ℰ∞ E_∞ closed under these operations starting from single causal roots (its recursive closure) consists entirely of finite sequences of CTEGs. For set-theoretic reasons we fix an infinite set A of actions throughout this section to constrain the size of sets constructed in the following procedure. We also fix a finite type set T. These will be left implicit in the notation. We start by introducing the ambient space G of all finite sequences (Gk)k=0n(G_k)_k=0^n of typed temporal graphs. These are directed graphs with types and timestamps, bearing no assumptions of being rooted or of compatibility between the causal and temporal structures. The idea is that a dynamical model of agent execution sequences recording types along with causal and temporal relationships must necessarily live in this space. We then single out ℰ∞⊂ E_∞ as the smallest set of such sequences (3.1) G0≼⋯≼GnG_0 ·s G_n starting from a single causal root G0G_0 and evolving by either direct emissions or self-invocations at each step. Theorem˜3.14 proves that ℰ∞ E_∞ then consists entirely of finite sequences of CTEGs. We further introduce a recursive hierarchy ℰ0⊆ℰ1⊆⋯ E_0 E_1 ·s of subagent execution levels parametrised by recursion depth and show that ℰ∞ E_∞ may be realised as the union ⋃ℰd E_d over all sublevels. In this connection we identify a monotone operator φ on the power set () P(G) of G exhibiting the ℰd E_d as iterates ℰd=φ(d+1)(∅) E_d= ^(d+1)( ) of the empty set and admitting ℰ∞ E_∞ as its smallest fixed point. Thus φ(ℰ∞)=ℰ∞ ( E_∞)= E_∞ and ℰ∞⊆ℱ E_∞ F whenever ℱ⊆ F and φ(ℱ)=ℱ ( F)= F. This realises the (ℰd)d∈ℕ( E_d)_d execution hierarchy as a simple recursion on () P(G) under φ starting at ∅ yielding ℰ∞ E_∞ as the canonical limit. The operator φ encodes the logical progression between successive recursion levels: At each step, an agent either emits new events directly, or invokes a subagent whose internally completed execution sequence (Hi)(H_i) yields a final element HmH_m to be grafted in at the invocation root. The step-by-step temporal dynamics of the subagent’s construction are not reflected in the parent’s execution sequence (Gk)(G_k): From the parent’s perspective, the subagent’s execution graph is received as a completed unit upon subagent termination and grafted atomically to enable separation of concerns. Even though the introduction of the full ℰd E_d-hierarchy is natural, it turns out that stabilisation occurs already at level ℰ1 E_1, in the sense that ℰd=ℰ1 E_d= E_1 for all d≥1d≥ 1 (but ℰ0≠ℰ1 E_0≠ E_1). The underlying reason is that the subagent invocation interface is opaque to construction history: It inspects only the final element HmH_m of a subagent trace sequence (Hi)(H_i). Any CTEG admits an ℰ0 E_0-construction by topological sorting, hence every ℰd E_d-invocation step can be replicated as an ℰ0 E_0-invocation step by substituting an ℰ0 E_0-sequence with the same final element. The construction of the ℰd E_d-hierarchy by means of simple recursion of φ from the empty set can be seen in relation to Kleene’s theorem in the complete lattice ((),⊆) ( P(G), ). A compactness argument gives the continuity of φ , and (ℰd)d∈ℕ( E_d)_d sits in the ascending Kleene chain (3.2) ∅⊆φ(∅)⊆φ(φ(∅))⊆⋯ ( ) ( ) ·s converging to the least fixed point ℰ∞=⋃ℰd E_∞= E_d of φ in the limit. 3.1. Local Dynamics We write G≤G′G≤ G when G,G′G,G are directed graphs and G′G extends G in the sense that (G)⊆(G′)N(G) (G ) and ℰ(G)⊆ℰ(G′)E(G) (G ). All nodes and edges of G are thus also in G′G when G is a subgraph of G′G , but not necessarily the other way around. A node map f:(G′)→Xf (G )→ X on G′G thus restricts to a node map (G)→XN(G)→ X on G when G≤G′G≤ G , an object we denote by f|Gf|_G. By a typed temporal graph (over T, with nodes in A) we mean a triple (G,t,τ)(G,t,τ), where G is a directed graph over A with temporal structure t:(G)→ℝt (G) and type map τ:(G)→Tτ (G)→ T. We make no assumptions that these be rooted and will for notational simplicity write G in place of (G,t,τ)(G,t,τ) when t and τ are clear from the context. The subgraph relation extends to typed temporal graphs to include compatibility conditions on the temporal and type structures under restrictions: We declare (3.3) (G,t,τ)≼(G′,t′,τ′)(G,t,τ) (G ,t ,τ ) iff G≤G′G≤ G and the compatibility conditions t′|G=t |_G=t and τ′|G=τ |_G=τ hold. Definition 3.1. We let G denote the set of all finite sequences (Gk)k=0n(G_k)_k=0^n of typed temporal graphs (Gk,tk,τk)(G_k,t_k, _k) over A with type set T. The next definition models the direct emission of new nodes by an agent in its current execution state (see Fig.˜5). This defines the first of the two local dynamical assumptions of our paper. We deliberately choose not to model simultaneous emissions from distinct roots, since this would complicate the arguments that follow without enlarging the class of attainable execution states. Definition 3.2 (Direct emissions). We say G≼G′G G by direct emissions for typed temporal graphs G,G′G,G iff there exists a finite, non-empty set A⊂A of new actions disjoint from (G)N(G) and an emission root p∈(G)p (G) such that (3.4) G′=G⊕pAG =G _pA with t(p)<t′(a)t(p)<t (a) for all a∈Aa∈ A. Figure 5. Evolution from state GkG_k to Gk+1G_k+1 by direct emissions. Remark 3.3. Of course, G⊕pAG _pA (where (G)∩A=∅N(G)∩ A= ) denotes the directed graph with node set (G)∪AN(G)∪ A and edge set ℰ(G)∪(p,a):a∈AE(G)∪\(p,a):a∈ A\. The second dynamical mode of our paper is the recursive invocation of a subagent, awaiting its execution graph, and grafting the resulting structure in at the parent agent’s invocation root (see Fig.˜6). So as to not make any a priori assumptions on the structure of these recursive invocations, we state our definition with respect to general finite sequences (Gk)k=0n(G_k)_k=0^n of typed temporal graphs (Gk,tk,τk)(G_k,t_k, _k) and recall that G denotes the set of all such. Figure 6. Evolution from state GkG_k to Gk+1G_k+1 by ℰd E_d-subagent invocation. Definition 3.4 (Subagent invocations). Given a set of sequences ℰ⊆ E and typed temporal graphs G,G′G,G , we say G≼G′G G by ℰ E-invocation iff there exists an invocation root p∈(G)p (G) along with some (Hi)i=0m∈ℰ(H_i)_i=0^m∈ E with node sets disjoint from G, and some qm∈(Hm)q_m (H_m) of in-degree zero, such that (3.5) G′=G⊕p(Hm,qm),G =G _p(H_m,q_m), where t′=t⊔tmt =t t_m, τ′=τ⊔τmτ =τ _m, and t(p)<tm(qm)t(p)<t_m(q_m) for compatibility. Remark 3.5. Here tm:(Hm)→ℝt_m (H_m) and τm:(Hm)→T _m (H_m)→ T denote the temporal and type structures of HmH_m, respectively. Note also that when HmH_m is a CTEG, there is exactly one choice of qmq_m, namely its causal root. 3.2. The Recursive Execution Hierarchy We now introduce the agent execution hierarchy (ℰd)d∈ℕ( E_d)_d . A directed graph G will be said to be A-trivial iff there exists r∈r such that (G)=rN(G)=\r\ and ℰ(G)=∅E(G)= . In other words, G is A-trivial iff it has a single causal root in A and no edges. (1) Let ℰ0⊂ E_0 be the set of all finite sequences (Gk)k=0n∈(G_k)_k=0^n of typed temporal graphs such that G0G_0 is A-trivial and (3.6) G0≼⋯≼GnG_0 ·s G_n by direct emissions at each step. (2) Supposing recursively that ℰd⊂ E_d has been defined for some d∈ℕd , define ℰd+1 E_d+1 to be the set of all finite sequences (Gk)k=0n∈(G_k)_k=0^n such that G0G_0 is A-trivial and (3.7) G0≼⋯≼GnG_0 ·s G_n by either direct emissions or ℰd E_d-invocations at each step. Remark 3.6. The recursion depth indexes an abstraction boundary: An ℰd E_d-computation is a self-contained unit of causal structure, composable into any ℰd+1 E_d+1-computation meeting the causal-temporal compatibility criterion without the parent inspecting the subagent’s internal execution history. This may be viewed as a simple recursion on the power set () P(G) of G. Let φ:()→() P(G)→ P(G) take a set ℰ⊆ E of (candidate) execution sequences to the set φ(ℰ)⊆ ( E) of all (Gk)∈(G_k) with G0G_0 A-trivial and G0≼⋯≼GnG_0 ·s G_n by either direct emissions or ℰ E-invocations at each step. Then (3.8) ℰ0=φ(∅)andℰd+1=φ(ℰd)(d∈ℕ). E_0= ( ) E_d+1= ( E_d) (d ). Hence ℰd=φ(d+1)(∅) E_d= ^(d+1)( ) (compositions) for all d∈ℕd . Lemma 3.7. φ is monotone: If ℰ⊆ℰ′ E E in () P(G), then φ(ℰ)⊆φ(ℰ′) ( E) ( E ). Proof. Immediate. ∎ Clearly ℰ0⊆ℰ1⊆⋯ E_0 E_1 ·s follows, and we put (3.9) ℰ∞≔⋃d∈ℕℰd. E_∞ _d E_d. Definition 3.8. ℰ∞ E_∞ is the set of agent execution sequences. Remark 3.9. See Figs.˜1 and 2 for a concrete example of an agent-subagent execution sequence to help unpack the formalism. We now give an intrinsic characterisation of ℰ∞ E_∞ without reference to its construction through the ℰd E_d-hierarchy. Lemma 3.10 (Recursive closure). ℰ∞ E_∞ is the smallest fixed point of φ : (3.10) φ(ℰ∞)=ℰ∞, ( E_∞)= E_∞, and if ℱ⊆ F is such that φ(ℱ)=ℱ ( F)= F, then ℰ∞⊆ℱ E_∞ F. Remark 3.11. The same holds if merely φ(ℱ)⊆ℱ ( F) F. Proof. For each d∈ℕd it holds that ℰd⊆ℰd+1=φ(ℰd)⊆φ(ℰ∞) E_d E_d+1= ( E_d) ( E_∞), hence ℰ∞=⋃ℰd⊆φ(ℰ∞) E_∞= E_d ( E_∞), and this takes care of the first inclusion. To prove φ(ℰ∞)⊆ℰ∞ ( E_∞) E_∞, note that any (Gk)∈φ(ℰ∞)(G_k)∈ ( E_∞) evolves from G0G_0 A-trivial by either direct emissions or ℰ∞ E_∞-invocations at each step. Since there are finitely many steps, there exists d∈ℕd (compactness) such that (Gk)∈φ(ℰd)=ℰd+1⊆ℰ∞(G_k)∈ ( E_d)= E_d+1 E_∞. This proves that ℰ∞ E_∞ is a fixed point of φ . To prove it is the smallest, assume ℱ⊆ F satisfies φ(ℱ)=ℱ ( F)= F, and observe first that ℰ0=φ(∅)⊆φ(ℱ)=ℱ E_0= ( ) ( F)= F. Furthermore, if ℰd⊆ℱ E_d F for some d∈ℕd , then also ℰd+1=φ(ℰd)⊆φ(ℱ)=ℱ E_d+1= ( E_d) ( F)= F, hence ℰ∞=⋃ℰd⊆ℱ E_∞= E_d F by induction. ∎ Remark 3.12. Similar fixed point arguments are standard in domain theory. The reader can find in Abramsky & Jung [undef, Theorem 2.1.19] the more general statement that every Scott-continuous (monotone) operator f on a pointed DCPO (partially ordered set in which every directed subset has a supremum) (P,⊥)(P, ) admits a least fixed point realised as the supremum of the ascending f-chain (f(k)(⊥))k∈ℕ(f^(k)( ))_k starting at the bottom element ⊥∈P ∈ P. Tarski [undefe] gives fixed points for monotone operators on complete lattices without continuity assumptions, at the expense of less constructive realisations, and contains interesting pointers to similar results in the literature. See also Kleene [undefa]. The compactness argument in the proof of Lemma˜3.10 in fact generalises to establish continuity, recovering the connections outlined in Remark˜3.12. Corollary 3.13. φ is Scott-continuous on the power set lattice () P(G). Proof. To see this, let (ℱi)( F_i) be a directed family in () P(G), and we need to prove φ(⋃ℱi)=⋃φ(ℱi) ( F_i)= ( F_i). The inclusion φ(ℱj)⊆φ(⋃ℱi) ( F_j) ( F_i) holds for all j since φ is monotone, and from this follows the first inclusion ⋃φ(ℱj)⊆φ(⋃ℱi) ( F_j) ( F_i). To prove the reverse inclusion, consider (Gk)∈φ(⋃ℱi)(G_k)∈ ( F_i), so that G0G_0 is A-trivial and we pick for each k for which Gk+1G_k+1 is obtained from GkG_k by ⋃ℱi F_i-invocation an index iki_k such that the invocation sequence lies in ℱik F_i_k. Since (ℱi)( F_i) is directed and there are finitely many steps, there is l such that ℱik⊆ℱl F_i_k F_l for all k, and from this follows (Gk)∈φ(ℱl)⊆⋃φ(ℱj) (G_k)∈ ( F_l) ( F_j). ∎ The following theorem characterises the objects contained in ℰ∞ E_∞. Theorem 3.14. ℰ∞ E_∞ is the smallest set of execution sequences (subsets of G) closed under direct emissions and self-invocations starting at A-trivial causal roots. All its elements are finite sequences of CTEGs over T with nodes in A, evolving according to the emission and invocation semantics of Section˜3.1. Proof. If all initial states of elements of ℱ⊆ F are A-trivial and φ(ℱ)⊆ℱ ( F) F, it is proved as in Lemma˜3.10 that in fact ℰ∞⊆ℱ E_∞ F. Hence ℰ∞ E_∞ is the smallest subset of G closed under direct emissions and self-invocations starting from single causal roots. That ℰ∞ E_∞ consists entirely of finite sequences of CTEGs is an induction on recursion depth in the decomposition ℰ∞=⋃ℰd E_∞= E_d. One checks it holds for ℰ0 E_0 since any (Gk)∈ℰ0(G_k)∈ E_0 starts at G0G_0 A-trivial (and is therefore a CTEG) and proceeds only by direct emissions which preserve the CTEG structure at each step. If d∈ℕd is such that the claim holds for ℰd E_d, one argues as for ℰ0 E_0 that the same must be true for ℰd+1 E_d+1 as well. Indeed, if (Gk)∈ℰd+1(G_k)∈ E_d+1, the only change in the argument is when Gk+1G_k+1 is obtained by grafting in the final element HmH_m of some subagent trace sequence (Hi)∈ℰd(H_i)∈ E_d. In this case, HmH_m is a CTEG by the induction hypothesis (with qmq_m the causal root), hence the same is true of Gk+1G_k+1 by the inner induction on k and the CTEG composition lemma (Lemma˜2.10). ∎ Remark 3.15 (Robustness to partial failure). Since well-formedness is preserved at each agent execution step, any prefix of an agent execution sequence produces a valid CTEG. In particular, if a session terminates prematurely due to failure, the partial trace retains full causal and temporal integrity up to that point and therefore remains directly serialisable. As promised, we prove stabilisation of the ℰd E_d-hierarchy already at ℰ1 E_1. Theorem 3.16. One has ℰ0≠ℰ1=ℰ∞ E_0≠ E_1= E_∞, hence ℰd=ℰ1 E_d= E_1 for all d≥1d≥ 1. Proof. The inclusion ℰ0⊂ℰ1 E_0⊂ E_1 is strict: An ℰ0 E_0-sequence (Hi)(H_i) of two successive emission steps may produce a final CTEG HmH_m of height at least 22. Grafting HmH_m in a single ℰ0 E_0-invocation step at an appropriate leaf node of the parent agent’s execution graph may increase its height by more than one. Since this is not possible by direct emissions alone, it follows that ℰ0≠ℰ1 E_0≠ E_1. To prove ℰ1=ℰ∞ E_1= E_∞, it suffices to show that φ(ℰ1)=ℰ1 ( E_1)= E_1 since ℰ∞ E_∞ is the smallest fixed point of φ and ℰ1⊆ℰ∞ E_1 E_∞. Let (Gk)∈φ(ℰ1)(G_k)∈ ( E_1). Each invocation step grafts the final element HmH_m of some ℰ1 E_1-construction sequence (Hi)(H_i). Since HmH_m is a CTEG, hence a finite arborescence with causally compatible timestamps, a topological sort yields an ℰ0 E_0-sequence with HmH_m as the final element. Hence every ℰ1 E_1-invocation step is also an ℰ0 E_0-invocation step, and so (Gk)∈φ(ℰ0)=ℰ1(G_k)∈ ( E_0)= E_1. This proves that φ(ℰ1)⊆ℰ1 ( E_1) E_1, and the reverse inclusion follows from (3.8) onwards. ∎ 4. Conclusion The present work has introduced causal-temporal event graphs (CTEGs) as a formal model for fully resolved recursive agent execution records under single-parenthood causal semantics. We formalised direct event emissions and recursive subagent invocations and proved that the recursive closure ℰ∞ E_∞ of these operations from single causal roots in the ambient space G of finite sequences of typed temporal graphs consists entirely of finite sequences of CTEGs. We further observed that ℰ∞ E_∞ is the least fixed point of a monotone operator φ on () P(G), the power set of G, obtained as the limit of the ascending φ -chain ∅⊆ℰ0⊆ℰ1⊆⋯ E_0 E_1 ·s. Although the full hierarchy arises naturally, stabilisation occurs already at ℰ1 E_1. This reflects the opacity of the subagent invocation interface, wherein only the final subagent execution structure HmH_m is exposed to the parent, while its construction history (Hi)(H_i) is discarded. Every CTEG admits an ℰ0 E_0-construction by topological sorting, hence HmH_m might as well have come from an ℰ0 E_0-invocation from the parent’s point of view. The central practical consequence is the identification of a compositional mechanism by which well-formed global causal structure may be assembled from delegated local subagent trace constructions without centralised coordination. The execution model is append-only by design: No operation retracts or modifies existing nodes, preserving the recorded causal structure. The arborescent structure of CTEGs enables natural relational database encodings of agent session histories as well as tamper-evident cryptographic commitments via Merkle tree hashes. Interrupted sessions preserve these properties and therefore remain fully serialisable under the same encoding. Capturing recursion depth as a structurally observable global execution trace invariant is an interesting direction for future work and can likely be achieved by carefully preserving more of the subagent execution history at the invocation interfaces or by treating subagent invocations as atomic nodes in the parent agents’ execution graphs. The latter would entail global execution records no longer be fully resolved in place, instead giving rise to trees of local views. We have also left open the investigation of direct agent-to-agent communications outside strict parent-child relationships, as well as the paradigm of more general multi-parenthood causal semantics. We have distinguished between well-formed and correct causal structure, arguing that the latter must be assessed relative to a choice of local parenthood semantics, the selection of which is orthogonal to the CTEG formalism as the encoding layer and outside the scope of the current paper. A natural extension of this work would be to formalise such a notion of local semantics, constraining the admissible parenthood attributions available at each step in accordance with well-founded causal principles. From this perspective, the theory developed herein describes the maximal case, in which every generically available local parenthood attribution is allowed. References [undef] Samson Abramsky and Achim Jung “Domain Theory” In Handbook of Logic in Computer Science 3 Oxford: Clarendon Press, 1994, p. 1–168 [undefa] Stephen Cole Kleene “Introduction to Metamathematics”, Bibliotheca Mathematica: A Series of Monographs on Pure and Applied Mathematics 1 Amsterdam: North-Holland Publishing Company, 1952 [undefb] Ralph C. Merkle “A Certified Digital Signature” In Advances in Cryptology — CRYPTO ’89 435, Lecture Notes in Computer Science New York, NY: Springer, 1990, p. 218–238 [undefc] Renan Souza et al. “PROV-AGENT: Unified Provenance for Tracking AI Agent Interactions in Agentic Workflows” In 2025 IEEE International Conference on eScience (eScience), 2025, p. 467–473 [undefd] Lukasz Szpruch, Agus Sudjianto, Tanveer Bhatti and Gary Ang “Scalable Runtime Governance for Agentic AI in Financial Services”, 2026 [undefe] Alfred Tarski “A Lattice-Theoretical Fixpoint Theorem and Its Applications” In Pacific Journal of Mathematics 5.2, 1955, p. 285–309