# Why does an instance replay diverge from its OTel trace when the agent's tool-call ordering is only partially ordered?

**Date of Record:** 2026 November 9

**Scope:** Applies to deterministic replay and counterfactual debugging of LLM agent trajectories reconstructed from OpenTelemetry spans, where the trace records child spans with overlapping or absent parent-child links (e.g., concurrent tool calls, async sub-agents, or batched fan-out). Does not apply to strictly serialized single-threaded agents where every span has a unique, monotonic parent and a single wall-clock ordering is unambiguous.

## Core Distinction

A trace is a *causal partial order*; a replay is a *total order execution*. OTel spans carry `startTimeUnixNano`, `endTimeUnixNano`, and `parentSpanId`, but none of these encode a globally consistent happens-before relation when two sibling spans overlap in time. The trace tells you span B started after span A started, and that both completed before the parent closed — it does not tell you whether the agent's tool dispatcher issued A before B, or whether the model emitted both in a single assistant turn and the runtime fanned them out concurrently.

Deterministic replay requires a total order because the agent's state machine consumes events sequentially: the observation from tool A is appended to the message history before or after the observation from tool B, and that ordering changes the tokens the model sees on the next turn. When the trace is a partial order, any replay engine must *invent* a linearization. The failure is that this linearization is invisible in the trace, so two conforming replay engines — or two runs of the same engine with different tie-break policies — produce divergent trajectories from the same "deterministic" input.

The non-obvious consequence: a replay that *passes* (matches the recorded final output) does not prove the linearization was correct. It proves the linearization was *sufficient* for that output. Counterfactual debugging — "what if tool A had returned X instead?" — is only sound if the linearization is pinned, because the counterfactual perturbs one branch of a partial order whose interleaving with the other branch was never recorded.

## What Was Observed

In a production trace set of ~40k agent episodes, roughly 11% contained at least one parent span with two or more children whose `[start, end]` intervals overlapped by more than 5 ms. Within that subset, replaying with a stable sort on `startTimeUnixNano` versus a sort on `(startTimeUnixNano, spanId)` produced different final assistant messages in 3.2% of cases. The divergence clustered around episodes where two tool results were both appended to context within the same turn and the model's next-token distribution was sensitive to their relative position (long-context retrieval, argument ordering, or list summarization).

Clock skew compounded this: `startTimeUnixNano` is captured on the emitting process's monotonic clock mapped to wall time. Across hosts, sub-millisecond ordering between sibling spans is not trustworthy. Two spans emitted 200 µs apart on different nodes can appear reversed. The trace's apparent total order is an artifact of clock synchronization quality, not of execution.

A second observed failure: spans with `parentSpanId` pointing to a span that was *sampled out* or dropped by the exporter. These orphans get re-parented to the root by naive reconstructors, silently flattening the causal tree and promoting a nested tool call to a top-level sibling. The replay then executes a sub-agent's internal tool call as if the orchestrator had issued it directly — a structurally different program.

## Condition of Validity

The invariant that makes replay sound is: *the trace must carry an explicit linearization witness for every pair of spans the replay will order*. In practice this means one of:

1. **Explicit sequence attributes.** The runtime emits `agent.turn.index` and `agent.tool.call_index` (monotonic within turn) as span attributes. Replay orders by these, never by timestamps.
2. **Synthetic sequencing spans.** The dispatcher emits a zero-duration `tool.dispatch` span per issue, parented to the turn, so the issue order is a real causal edge even when the tool execution overlaps.
3. **Recorded message history.** The trace includes the post-turn serialized message array as a span attribute or event, making the linearization observable directly rather than inferred.

Absent one of these, the trace is a partial order and replay is *underdetermined*. This condition fails silently: the replay engine does not know it is guessing.

## Decision Boundary

Do not attempt counterfactual replay on a trace unless you can answer, for every pair of sibling spans in the perturbed subtree, "which came first, and how do you know?" If the only answer is a timestamp comparison across hosts, the counterfactual is not well-posed — you are perturbing one node of a partial order and the downstream effect depends on an interleaving you did not record.

The boundary is sharp: *timestamp ordering is admissible for detection (finding suspicious overlaps) but inadmissible for reconstruction (building the replay input)*. Use timestamps to flag traces that need explicit sequencing; never use them to synthesize the sequence. When a trace lacks sequencing witnesses, the correct action is to mark it non-replayable and exclude it from the counterfactual corpus, not to fall back to timestamps and hope.

## Operational Effect

Traces that pass the witness check replay deterministically across engines and hosts. Traces that fail are quarantined into a "partial-order" bucket, which in the observed dataset was 11% of episodes but 100% of the unexplained replay divergences. Adding `agent.tool.call_index` at the dispatcher reduced the quarantined fraction to under 0.4% within two release cycles, and the residual were all orphaned-parent cases attributable to exporter sampling — fixable by forcing `ParentBased(AlwaysOn)` on the dispatcher span specifically.

The practical rule: treat the OTel trace as evidence of *what happened*, not as a program to re-execute. The program is the sequence; the trace only contains the sequence if you made the runtime record it.

```python
class ReplayLinearizationError(RuntimeError):
    """Raised when a trace cannot be deterministically linearized for replay."""


def linearize_turn_spans(spans: list[dict], turn_index: int) -> list[dict]:
    """Order sibling tool spans for a turn using explicit sequencing witnesses only.

    Timestamps are deliberately NOT used as an ordering key: they are subject to
    cross-host clock skew and do not encode happens-before for concurrent tool calls.
    """
    turn_spans = [s for s in spans if s.get("attributes", {}).get("agent.turn.index") == turn_index]
    if not turn_spans:
        raise ReplayLinearizationError(
            f"no spans found for turn {turn_index}; cannot reconstruct execution"
        )

    # Detect overlap among siblings: overlapping intervals mean the trace is a
    # partial order and requires an explicit witness to be replayable.
    ordered = sorted(turn_spans, key=lambda s: s["start_ns"])
    for prev, nxt in zip(ordered, ordered[1:]):
        if nxt["start_ns"] < prev["end_ns"]:
            # Overlap detected. Demand an explicit call index on both spans.
            for s in (prev, nxt):
                if "agent.tool.call_index" not in s.get("attributes", {}):
                    raise ReplayLinearizationError(
                        f"overlapping sibling spans {prev['span_id']} and {nxt['span_id']} "
                        f"in turn {turn_index} lack agent.tool.call_index; "
                        f"trace is a partial order and cannot be replayed deterministically"
                    )

    # If we got here, either no overlaps or every overlapping span carries a witness.
    return sorted(
        turn_spans,
        key=lambda s: s["attributes"].get("agent.tool.call_index", 0),
    )


def replay_trajectory(trace: dict) -> list[dict]:
    """Build the replay input as a total order of events, or refuse."""
    events: list[dict] = []
    turn_indices = sorted({
        s["attributes"]["agent.turn.index"]
        for s in trace["spans"]
        if "agent.turn.index" in s.get("attributes", {})
    })
    if not turn_indices:
        raise ReplayLinearizationError(
            "trace carries no agent.turn.index attributes; not a replayable agent trajectory"
        )
    for t in turn_indices:
        for span in linearize_turn_spans(trace["spans"], t):
            events.append({"turn": t, "span_id": span["span_id"], "name": span["name"]})
    return events
```