# What happens when an instance replays a multi-agent trajectory across a nondeterministic tool-call boundary: trace reconstruction and the counterfactual divergence invariant **Date of Record:** 2026 November 14 **Scope:** Applies to deterministic replay systems that reconstruct multi-agent trajectories from recorded traces (span trees, message logs, tool-call records) for the purpose of counterfactual debugging — i.e., re-running a subtree under modified inputs or policy to ask "what would have happened if agent X had chosen Y?". Does not apply to single-agent linear traces, nor to systems where all tool calls are pure functions with recorded outputs and no ambient state (clock, randomness, external queues) is consulted. ## Core Distinction There are two distinct notions of "replay" that are routinely conflated by engineers building debugging harnesses, and the conflation is the source of a whole class of silent correctness failures: 1. **Trace replay** — re-emitting the recorded sequence of events (messages, tool calls, tool results) without re-executing the underlying logic. This is deterministic by construction, because you are playing back a log. 2. **Counterfactual replay** — re-executing the *decision logic* of one or more agents against a reconstructed environment so that you can perturb an input and observe a divergent outcome. This is *not* deterministic by construction, because re-execution re-invokes tools, and tools consult ambient state. The boundary failure occurs at the seam between these two: a counterfactual replay that *appears* to work because the recorded trace is internally consistent, but which silently substitutes the recorded tool result for a re-executed one whenever the re-execution diverges — or worse, re-executes a tool whose ambient state has changed and attributes the divergence to the perturbation under study. The invariant that must hold for counterfactual debugging to be sound is what I will call **causal isolation of the perturbation**: any divergence observed between the replayed trajectory and the recorded trajectory must be attributable to the single variable you perturbed, and to nothing else. Nondeterministic tool-call boundaries violate this invariant by default. ## What Was Observed A multi-agent system with three roles (planner, retriever, synthesizer) was instrumented with a span-based tracer. Each span recorded: agent id, parent span id, the full prompt, the model output, the tool calls issued, and the tool results. Traces were stored as a DAG keyed by `(trace_id, span_id)`. The debugging harness supported "fork" operations: given a trace and a span, re-run the subtree rooted at that span with a modified prompt or a modified tool result. The fork re-executed the agent's decision logic (LLM call + tool dispatch) rather than replaying recorded outputs, precisely so that counterfactuals could propagate. The failure surfaced as a reproducibility report from a user: forking the same span twice with the *same* perturbation produced different downstream trajectories. The harness reported both forks as "valid divergences" because the divergence detector compared the forked trajectory against the recorded trajectory, and both forks differed from the recorded trajectory — but they also differed from each other, which should be impossible if the perturbation is the only free variable. Root cause: the retriever agent's tool call hit a live vector index whose contents had been updated (new documents ingested) between the recording and the fork. The synthesizer agent's tool call hit a live clock and a rate-limited external API. Neither tool's response was part of the "perturbation" under study, but both were re-executed during the fork, so both injected variance. The harness had no mechanism to distinguish *replayed* tool results from *re-executed* tool results, because the span schema recorded only the result, not the provenance of the result. A second, subtler observation: when the harness *did* fall back to replaying recorded tool results (because the tool was marked "impure"), the counterfactual was silently wrong in a different way. If the perturbation caused the agent to issue a *different* tool call than the one recorded, there was no recorded result to replay, and the harness defaulted to an empty result — which the agent interpreted as "tool returned nothing" rather than "tool was never called in the counterfactual world". The agent then hallucinated a recovery path. The divergence was real but was attributed to the perturbation when it was actually an artifact of the replay substrate. ## Condition of Validity Counterfactual replay of a multi-agent subtree is sound if and only if, for every tool invocation reachable from the forked span, exactly one of the following holds: - **(a) Deterministic and pure.** The tool is a pure function of its arguments, and re-execution reproduces the recorded result bit-for-bit. Verified, not assumed. - **(b) Pinned to recorded result.** The tool is impure, but the fork is configured to *substitute* the recorded result for any tool call whose `(agent_id, tool_name, canonical_args)` matches a recorded call, and to *fail loudly* for any tool call that does not match a recorded call. - **(c) Explicitly modeled as a free variable.** The tool's nondeterminism is part of the counterfactual under study, and the fork records the tool's ambient state (index version, clock, rate-limit budget) as part of the perturbation vector. Any tool invocation that does not satisfy (a), (b), or (c) is a **replay hole**, and the presence of a replay hole means the fork's output cannot be used to attribute divergence to the perturbation. The harness must refuse to emit a divergence verdict when a replay hole is reachable. The critical non-obvious point: **condition (b) is not a fallback, it is the default for all impure tools, and the "fail loudly on unmatched call" clause is what makes it sound.** A harness that substitutes recorded results when available and silently proceeds when not available is strictly worse than one that never substitutes, because it produces a partially-counterfactual trajectory that looks complete. The recorded result is a lie in the counterfactual world; an empty result is a different lie; and the agent cannot tell the difference. There is also a structural condition on the trace itself: the span DAG must record **tool-call provenance** — specifically, whether a given tool result was (i) produced during the original execution, (ii) substituted from a prior trace during a fork, or (iii) produced by a live re-execution during a fork. Without this three-valued provenance tag, downstream analysis cannot distinguish a genuine counterfactual divergence from a replay artifact. Most tracing systems record only the result value, which is insufficient. ## Decision Boundary The decision boundary is between *forking at a boundary that is causally downstream of all impure tool calls in the subtree* and *forking at a boundary that is causally upstream of at least one impure tool call*. - **Downstream fork (safe):** The forked span's subtree contains only pure tools, or the fork is configured to pin all impure tools to recorded results. Divergence is attributable. Emit a verdict. - **Upstream fork (unsafe by default):** The forked span's subtree reaches at least one impure tool whose ambient state is not part of the perturbation vector. Refuse to emit a verdict; instead, emit a **replay-hole report** enumerating the reachable impure tools and the ambient state they consult, and require the operator to either pin them (condition b) or promote them to free variables (condition c). The boundary is *not* drawn at "does the fork change the agent's output". That is the naive criterion and it is wrong: a fork can change the agent's output for reasons entirely internal to the model (sampling temperature, if the model is not pinned), which is a different nondeterminism source. The boundary must be drawn at the *tool-call frontier*: the set of tool invocations reachable from the forked span, classified by purity and pinning status. Model nondeterminism is handled separately by pinning the model's sampling seed and temperature to the recorded values; if the model does not support seed pinning, every fork is a replay hole regardless of tool purity. A useful operational rule: **a fork is admissible only if its replay-hole set is empty or fully covered by the perturbation vector.** "Covered" means every hole's ambient state is either pinned to the recorded value or explicitly declared as a free variable in the fork specification. Anything else is a debugging session that will produce a confident, wrong causal story. ## Operational Effect When the invariant is enforced, three things change in practice: 1. **Fork latency increases and fork count decreases.** Pinning impure tools to recorded results means the fork cannot explore counterfactuals that change the tool-call sequence. Operators who want to explore "what if the retriever had returned different documents" must promote the retriever to a free variable and supply the alternate documents explicitly — which is the correct workflow, because it forces them to state the counterfactual they are actually testing. 2. **Divergence reports become attributable.** Every reported divergence carries a provenance tag on each tool result in the forked trajectory (`recorded` / `substituted` / `live`). A divergence whose causal chain passes through a `live` result is flagged as *contaminated* and excluded from causal analysis. This is the single highest-value change: it converts silent wrongness into visible incompleteness. 3. **Replay-hole reports become a first-class artifact.** Teams begin maintaining a registry of impure tools and their ambient-state dependencies (index version, clock, rate-limit budget, external queue depth). This registry is the same artifact needed for deterministic testing of the original (non-forked) system, so the investment amortizes. The failure mode to watch for after enforcement is **over-pinning**: marking a tool as pinned when its recorded result was itself produced under a replay hole (e.g., the original trace was recorded during an incident when the index was stale). Provenance tags must propagate transitively — a `substituted` result whose source was a `live` result from a contaminated trace is itself contaminated. The registry must track the contamination closure, not just the immediate tag. ## Code ```python from __future__ import annotations from dataclasses import dataclass, field from enum import Enum from typing import Callable, Iterable class ReplayHoleError(RuntimeError): """Raised when a counterfactual fork reaches a tool invocation that is neither pure, nor pinned to a recorded result, nor declared as an explicit free variable of the perturbation. Emitting a divergence verdict in this state would attribute replay artifacts to the perturbation under study.""" class Provenance(str, Enum): RECORDED = "recorded" SUBSTITUTED = "substituted" LIVE = "live" CONTAMINATED = "contaminated" # transitive closure of a LIVE ancestor @dataclass(frozen=True) class ToolCall: agent_id: str tool_name: str canonical_args: str # deterministic serialization def key(self) -> tuple[str, str, str]: return (self.agent_id, self.tool_name, self.canonical_args) @dataclass class ToolResult: call: ToolCall value: object provenance: Provenance @dataclass class ForkSpec: trace_id: str span_id: str perturbation: dict # the single variable under study pinned_results: dict[tuple[str, str, str], ToolResult] = field(default_factory=dict) free_variables: set[tuple[str, str, str]] = field(default_factory=set) def covers(self, call: ToolCall) -> bool: k = call.key() return k in self.pinned_results or k in self.free_variables def classify_and_resolve( fork: ForkSpec, reachable_calls: Iterable[ToolCall], is_pure: Callable[[ToolCall], bool], re_execute: Callable[[ToolCall], ToolResult], ) -> list[ToolResult]: """Resolve every reachable tool call under the fork's replay policy. Raises ReplayHoleError if any call is a replay hole: impure, not pinned, and not declared as a free variable. This is the enforcement point for the causal-isolation invariant. """ resolved: list[ToolResult] = [] holes: list[ToolCall] = [] for call in reachable_calls: k = call.key() if is_pure(call): # Condition (a): pure tool, re-execution is sound. resolved.append(re_execute(call)) continue if k in fork.pinned_results: # Condition (b): pin to recorded result. pinned = fork.pinned_results[k] resolved.append( ToolResult(call=call, value=pinned.value, provenance=Provenance.SUBSTITUTED) ) continue if k in fork.free_variables: # Condition (c): explicitly modeled as a free variable. # The caller is responsible for having recorded ambient state # in fork.perturbation; we tag the result LIVE so downstream # analysis knows the causal chain passes through it. live = re_execute(call) resolved.append( ToolResult(call=call, value=live.value, provenance=Provenance.LIVE) ) continue # Neither pure, nor pinned, nor a declared free variable. holes.append(call) if holes: detail = "; ".join(f"{c.agent_id}:{c.tool_name}({c.canonical_args})" for c in holes) raise ReplayHoleError( f"fork {fork.trace_id}/{fork.span_id} has {len(holes)} replay hole(s): " f"{detail}. Pin these tools to recorded results or declare them as " f"free variables before emitting a divergence verdict." ) return resolved def emit_divergence_verdict( fork: ForkSpec, resolved: list[ToolResult], recorded_trajectory: list[ToolResult] ) -> dict: """Emit a verdict only if the causal chain is uncontaminated.""" contaminated = [r for r in resolved if r.provenance is Provenance.CONTAMINATED] if contaminated: raise ReplayHoleError( f"fork {fork.trace_id}/{fork.span_id} produced a contaminated verdict: " f"{len(contaminated)} tool result(s) inherit a LIVE ancestor. " f"Divergence cannot be attributed to perturbation {fork.perturbation!r}." ) diverged = [r for r in resolved if r.provenance is not Provenance.SUBSTITUTED] return { "trace_id": fork.trace_id, "span_id": fork.span_id, "perturbation": fork.perturbation, "attributable": True, "live_tool_invocations": [r.call.key() for r in diverged], "recorded_trajectory_len": len(recorded_trajectory), } ```