# Which invariants prevent causal span linking from silently collapsing in multi-agent GenAI traces **Date of Record:** 2026 November 17 **Scope:** Applies to distributed tracing of multi-agent LLM systems where agent invocations are modeled as nested spans with explicit parent/child links and causal (happens-before) edges derived from span timestamps plus explicit link attributes. Does not apply to single-agent request traces, nor to systems that rely solely on wall-clock ordering without a trace-context propagation mechanism. ## Core Distinction The common assumption is that a span hierarchy is a tree: every span has exactly one parent, and the parent's start time precedes the child's. In multi-agent systems this is false in two independent ways. First, an agent turn is frequently *fan-in*: a supervisor span may have N children that are themselves agents, each of which may be re-entered, retried, or resumed from a checkpoint, producing spans whose parent ID is the supervisor but whose causal predecessor is a *sibling* (the tool result, the prior agent's output). Second, handoffs between agents are *cross-tree*: Agent A spawns Agent B, but B is long-lived and serves many A-turns, so B's span parent is a runtime-owned root, not A. The tree invariant (single parent, monotonic start times) and the causal invariant (every effect has a preceding cause within the same trace) diverge precisely at these fan-in and handoff boundaries. ## What Was Observed In a three-tier supervisor/worker/critic pipeline, a worker span was emitted with `parent_span_id` pointing at the supervisor, but its `start_time` was 40 ms *before* the supervisor span's `start_time`. The cause was asynchronous span creation: the worker's OpenTelemetry span was started inside the worker process before the propagation header from the supervisor was flushed, so the parent ID was correct but the clock ordering was inverted. Downstream causal-link derivation (which sorted spans by start time to build a happens-before graph) silently reversed the edge, making the supervisor appear to depend on the worker's output. The trace remained structurally valid—every span had a parent, no orphans—so no validator fired. The corruption surfaced only when a replay harness re-executed the critic and observed a different verdict than the recorded trace implied, a discrepancy of 1 in 2,000 replays that initially looked like LLM nondeterminism. A second observation: when a long-lived worker agent served two supervisors, its span was re-parented to the *second* supervisor on resume, orphaning the first supervisor's causal edge. The trace still passed "single parent" checks because the span was rewritten, not duplicated. The missing edge was detectable only by cross-referencing the worker's internal turn log against the trace's parent assignments. ## Condition of Validity The tree invariant (unique parent, parent.start ≤ child.start) is valid only when span creation is synchronous with dispatch and propagation headers are flushed before the child begins work. The causal invariant (edge u→v iff u ends before v starts *and* u's output is consumed by v) is valid only when the trace carries explicit causal link attributes (`link.type=caused_by`, `link.source_output_id`) rather than inferring causality from timestamps. Neither invariant alone is sufficient: timestamp-only causality breaks under clock skew and async span start; parent-ID-only causality breaks under re-parenting and long-lived agents. A trace is causally sound only when *both* hold and are cross-checked, i.e., every parent edge is also a causal edge, and every causal edge has a recorded parent or explicit link. ## Decision Boundary When a span's `start_time` precedes its parent's `start_time`, do not silently reorder. Treat it as one of two cases: (a) async span start with correct propagation—repair by setting the child's causal predecessor to the parent's *dispatch* event, not the parent's start, and record a `clock_skew_corrected` attribute; or (b) genuine cross-tree handoff—do not force a parent; emit a `link` (not a parent) from the worker span to the supervisor's dispatch span, and keep the worker's parent as its runtime root. The boundary is whether the child's *output* is consumed by the alleged parent. If yes, a causal link is mandatory even if the parent edge is absent. If no, the parent edge is a structural artifact and must not be used to derive causality. ## Operational Effect Enforcing this boundary changes the trace schema: spans gain an optional `causal_predecessor_id` distinct from `parent_span_id`, and validators reject any trace where a causal edge lacks either a matching parent edge or an explicit link record. The practical effect is that replay harnesses can distinguish "the model was nondeterministic" from "the trace lied about ordering"—the 1-in-2,000 discrepancy above resolved to a trace defect, not a model defect, once the invariant was enforced. The cost is that traces are no longer pure trees and downstream consumers must handle DAG-shaped causal graphs; the benefit is that causal claims in the trace are falsifiable against the recorded link attributes rather than inferred from clocks. ```python from dataclasses import dataclass from typing import Optional class CausalLinkInvariantError(RuntimeError): """Raised when a span's causal edge is neither backed by a parent edge nor by an explicit link record, or when start-time ordering contradicts the declared parent without a repair annotation.""" pass @dataclass class Span: span_id: str parent_span_id: Optional[str] start_ns: int end_ns: int causal_predecessor_id: Optional[str] = None link_type: Optional[str] = None # e.g. "caused_by" clock_skew_corrected: bool = False def validate_causal_span(span: Span, spans_by_id: dict) -> None: # Invariant 1: a declared parent must exist and not post-date the child, # unless the skew was explicitly repaired. if span.parent_span_id is not None: parent = spans_by_id.get(span.parent_span_id) if parent is None: raise CausalLinkInvariantError( f"span {span.span_id} references missing parent " f"{span.parent_span_id}" ) if span.start_ns < parent.start_ns and not span.clock_skew_corrected: raise CausalLinkInvariantError( f"span {span.span_id} starts before its parent " f"{parent.span_id} without clock_skew_corrected annotation; " f"reorder would silently invert the causal edge" ) # Invariant 2: a causal edge must be backed by a parent edge or an # explicit link record. Timestamp inference alone is not admissible. if span.causal_predecessor_id is not None: backed_by_parent = span.causal_predecessor_id == span.parent_span_id backed_by_link = ( span.link_type == "caused_by" and span.causal_predecessor_id in spans_by_id ) if not (backed_by_parent or backed_by_link): raise CausalLinkInvariantError( f"span {span.span_id} claims causal predecessor " f"{span.causal_predecessor_id} with no parent edge and no " f"caused_by link record; trace is causally unsound" ) # Invariant 3: cross-tree handoffs must not be forced into a parent edge. if ( span.parent_span_id is not None and span.causal_predecessor_id is not None and span.causal_predecessor_id != span.parent_span_id and span.link_type != "caused_by" ): raise CausalLinkInvariantError( f"span {span.span_id} has divergent parent and causal predecessor " f"without a caused_by link; cross-tree handoff was coerced" ) ```