# Which invariants prevent counterfactual span analysis from corrupting causal replay in non-deterministic agent traces **Date of Record:** 2026 November 16 **Scope:** Applies to GenAI observability pipelines that reconstruct agent execution graphs from span telemetry and then re-execute or simulate spans under perturbed inputs ("counterfactual" analysis). Does not apply to purely descriptive tracing (latency, token counts, error rates) where no replay or perturbation occurs. ## Core Distinction A trace is a *record of one sample* from a stochastic policy. A causal replay is a *reconstruction of the dependency graph* that produced that sample. Counterfactual span analysis asks: "if span S had received input X′ instead of X, what would downstream spans have emitted?" This is only well-posed if the replay graph distinguishes **causal edges** (span B's input was literally constructed from span A's output) from **correlational edges** (B and A share a parent, a prompt prefix, or a sampling seed but B never read A's output). Most tracing backends (OpenTelemetry-style parent/child spans, LangSmith run trees) encode *containment*, not *dataflow*. The non-obvious invariant is this: **a counterfactual substitution is sound only if every span whose output was consumed — directly or transitively — by the substituted span is itself re-executed, and every span that merely co-occurred is held fixed.** Violating this does not raise an error; it silently produces a plausible-looking but causally wrong counterfactual, which then feeds back into evaluation dashboards as ground truth. ## What Was Observed In a multi-agent research pipeline (planner → 3 parallel retrievers → synthesizer → critic), an operator injected a counterfactual into the synthesizer span: "what if the synthesizer had received only retriever-2's documents?" The replay engine substituted the synthesizer's input and re-ran it. Downstream, the critic span was re-executed against the new synthesizer output. Result looked clean. The failure: the *planner* span had emitted a routing decision ("use all three retrievers, weight by recency") that was embedded in the synthesizer's system prompt. The counterfactual's synthetic input still contained that routing string, so the re-run synthesizer behaved as if three retrievers had reported, hallucinating references to retriever-1 and retriever-3 documents that were absent from the substituted context. The critic, faithfully re-executed, flagged "inconsistent citations" — a *fabricated* finding. That finding was logged as a real counterfactual outcome and used to justify disabling retriever-3 in production for two weeks. The root cause is a violated invariant, not a bug in any single component: the substitution boundary was drawn at the *synthesizer's input tensor*, but the causal influence of the retrievers extended into the synthesizer via the **planner's prompt construction**, an edge that the span tree did not represent. The trace said `planner → synthesizer` (parent) and `retriever-N → synthesizer` (siblings under a common run). The actual dataflow was `retriever-N → planner.routing_decision → synthesizer.prompt`. Three correlated siblings, one hidden causal path. A second, subtler observation: because agent sampling is non-deterministic (`temperature > 0`, tool calls with wall-clock-dependent results), re-executing a span does not reproduce its recorded output even with identical inputs. Operators "verified" the replay engine by re-running spans with *unperturbed* inputs and confirming output equality — which passed only because the harness had pinned the seed for validation runs. In production, seed pinning was off, so the same validation would have shown divergence and been dismissed as expected noise. The validation procedure was itself invalid. ## Condition of Validity Counterfactual span analysis is valid iff all of the following hold simultaneously: 1. **Dataflow closure.** The set of spans re-executed under a substitution is closed under the transitive "output-consumed-by" relation, computed over *actual data dependencies*, not span parentage. Any span that read the substituted output — including indirectly, via a prompt-assembly span, a cached value, or a shared memory object — must be in the re-execution set. 2. **Intervention locality.** Spans outside the re-execution set must be provably independent of the substituted value. "Provably" means a recorded input hash or content-addressed reference, not an assumption from graph topology. 3. **Stochastic control.** Re-execution must either pin all sampling parameters *and* external tool responses to their recorded values (a true replay), or the counterfactual must be reported as a *distribution* over re-samples with an explicit variance estimate. A single re-executed sample presented as a counterfactual outcome is a category error. 4. **Prompt provenance.** Any span whose input is a composed prompt must carry the composition graph (which upstream outputs were interpolated, in what order, with what templates) as first-class telemetry. Without it, invariant 1 cannot be checked. The system above violated 1 and 4 outright, and 3 during validation. It satisfied 2 only by accident. ## Decision Boundary Do **not** perform counterfactual substitution when the substituted span's output flows into any prompt-assembly, routing, or memory-write span whose own output is consumed downstream — unless prompt provenance is recorded and the closure in invariant 1 is computed over it. In practice this rules out counterfactuals on the "leaf" retrievers of most RAG agents, because their outputs are almost always interpolated into a composed prompt by an intermediate span that the trace does not model. Do **not** treat a single re-execution as a counterfactual. If you cannot pin seeds and tool responses, either (a) label the result as one sample from a re-execution distribution and report N≥20 with spread, or (b) refuse the counterfactual. Do **not** validate a replay engine by re-running unperturbed spans with pinned seeds and calling equality a pass. Validate by re-running *perturbed* spans and checking that *only* the causally-downstream set diverges; if a sibling that should have been held fixed changes, the closure is broken. You *may* perform counterfactual analysis freely on spans that are terminal consumers (the critic's verdict, a final answer) or on spans whose inputs are fully recorded and whose outputs are consumed by no other span. You may also do "what-if" *simulation* — replacing a span with a language-model approximation — provided the result is labeled as simulation and never merged into the causal record. ## Operational Effect The practical rule that emerged: **treat the span tree as a containment hierarchy and the dataflow graph as a separate, explicitly-recorded artifact; counterfactuals are defined only on the latter.** Instrumentation must emit, for every span, a content-addressed list of the exact upstream span outputs it consumed (hashes plus provenance), even when those outputs arrived via prompt templates or shared memory. The replay engine then computes the re-execution set as the forward-reachable closure from the substituted span over that graph, and refuses (raises) when the closure cannot be computed — for example, when a consuming span lacks provenance records, or when an unpinned stochastic span lies in the closure and the caller requested a single-sample counterfactual. This converts a silent, high-consequence failure (fabricated causal findings driving production changes) into a loud, cheap one (a refused counterfactual that tells you to fix instrumentation). The cost is that many counterfactuals become unavailable until prompt provenance is wired through; the benefit is that the ones you do get are actually causal. ```python from dataclasses import dataclass, field from typing import Dict, Set, List class CounterfactualClosureError(RuntimeError): """Raised when a counterfactual substitution cannot be soundly replayed.""" pass @dataclass class Span: span_id: str # content-addressed ids of upstream span outputs this span actually consumed consumed: Set[str] = field(default_factory=set) # True if re-execution is stochastic and not pinned to recorded values stochastic_unpinned: bool = False # provenance of prompt composition is required if this span composes prompts provenance_recorded: bool = True def compute_reexecution_set(spans: Dict[str, Span], substituted: str) -> Set[str]: # forward reachability over actual dataflow (consumed edges), not parentage consumers: Dict[str, List[str]] = {} for sid, s in spans.items(): for upstream in s.consumed: consumers.setdefault(upstream, []).append(sid) closure: Set[str] = set() frontier = [substituted] while frontier: cur = frontier.pop() for c in consumers.get(cur, []): if c not in closure: closure.add(c) frontier.append(c) return closure def plan_counterfactual( spans: Dict[str, Span], substituted: str, single_sample: bool, ) -> Set[str]: if substituted not in spans: raise CounterfactualClosureError( f"substituted span {substituted!r} not found in trace" ) closure = compute_reexecution_set(spans, substituted) for sid in closure: s = spans[sid] if not s.provenance_recorded: raise CounterfactualClosureError( f"span {sid!r} consumes substituted output but records no " f"prompt provenance; dataflow closure unverifiable" ) if single_sample and s.stochastic_unpinned: raise CounterfactualClosureError( f"span {sid!r} is unpinned-stochastic in the re-execution " f"set; a single-sample counterfactual would be a category " f"error (request a distribution, N>=20)" ) return closure ```