# Where must an instance boundary be drawn when replaying agentic workflows from OpenTelemetry GenAI span graphs?

**Date of Record:** 2026 November 12

**Scope:** Applies to deterministic replay of LLM-agent workflows reconstructed from OpenTelemetry GenAI span graphs (spans carrying `gen_ai.*` attributes, `trace_id`/`span_id`/`parent_span_id` links, and tool-call child spans). Does not apply to single-shot synchronous inference calls with no tool or sub-agent fan-out, nor to replays driven from application-level event logs that already carry explicit causal sequence numbers.

## Core Distinction

The distinction that matters is between **trace causality** and **replay causality**. A span graph encodes *who called whom* — a parent-child tree plus explicit `SpanLink`s. It does not encode *who depended on whose output*. In agentic workflows these diverge precisely at fan-out/fan-in joints: a planner span may emit three parallel tool spans as children, and a later synthesis span may consume all three results. The tree says the synthesis span is a sibling of the tool spans; the actual data dependency says it is their join. Replay that follows the tree will execute the synthesis span before its inputs exist, or will re-execute a tool span whose result was already cached — and the second case silently produces a different trajectory than the original run.

The non-obvious invariant is this: **deterministic replay is only valid on the subgraph where the span tree is also a data-dependency DAG.** Everywhere else — any node with more than one inbound causal edge, or any node whose inputs were produced by a span that is not its ancestor — the instance boundary must be drawn at the fan-in node, and that node's inputs must be re-materialized from the recorded span attributes rather than recomputed.

## What Was Observed

In a production agent runtime exporting GenAI spans to an OTLP collector, replays of a 4-agent research workflow diverged from the recorded trajectory in roughly one run out of eleven. The divergence was not an error: the replay completed, emitted plausible spans, and produced a final answer. It was a *different* answer.

Root cause, isolated by diffing the recorded trace against the replay trace:

1. The planner span (`gen_ai.operation.name = chat`, agent role `planner`) issued three tool calls to a retrieval tool. OTel models these as three child spans under the planner. Their results were appended to the planner's message history in *completion order*, not issue order.
2. The synthesis span read the planner's accumulated `gen_ai.prompt` as a single flat message list. That list is order-sensitive — the model attends to it positionally.
3. On replay, the three tool spans were re-executed against a live index. Two returned identical content; the third returned a chunk with a slightly different rank ordering because the underlying vector index had been compacted between record and replay. The completion order flipped. The prompt message list was permuted. The synthesis span received a different positional context and generated a different plan.

The span graph was structurally identical across record and replay — same `trace_id` shape, same parent-child edges, same span count. The only signal of divergence was a `gen_ai.prompt` attribute hash mismatch on the synthesis span, which the replay harness was not checking because it treated prompt content as derived, not as an input.

A second, related observation: `SpanLink` was used by the framework to record the *retrieval dependency* from the synthesis span back to the three tool spans (a many-to-one link set). This is the correct modeling choice, and it is exactly the edge the naive tree-walk replay ignored. The link set was the data-dependency DAG; the parent-child tree was not.

## Condition of Validity

A replay from a GenAI span graph is deterministic **if and only if** all of the following hold at every node in the subgraph being replayed:

- The node has at most one ancestor-or-link inbound edge that carries *content* (not merely a control-flow or timing edge).
- Every input the node consumes is either (a) a constant recorded on the span, (b) a value produced by a span that is a strict ancestor of the node, or (c) a value produced by a span reachable via a `SpanLink` and re-materialized from that span's recorded output attributes rather than recomputed.
- The ordering of any list-valued input (message history, tool-result array, retrieved-document ranking) is recorded explicitly — as an ordered attribute, not inferred from span start/end timestamps. Timestamps are not a valid ordering key under clock skew, batching, or concurrent emission.

When any condition fails, the node is a **replay boundary**. The boundary must be moved up to the nearest node whose inputs satisfy the conditions, and the failing node's inputs must be injected from the record.

## Decision Boundary

The operational decision is: *do I recompute this node, or do I inject its inputs from the record?*

Recompute only when the node is on a single-inbound-edge path and all its inputs are ancestor-derived or constant. Inject when any of the following is true:

- The node is a fan-in: it has two or more `SpanLink`s or parent-sibling dependencies carrying content.
- The node's input includes a list whose order is semantically load-bearing and whose order is not captured as an ordered attribute.
- The node's input was produced by a non-deterministic external system (retrieval index, live API, clock, random sampler) and that system's state is not reconstructable from the trace.
- The node's recorded output attribute hash does not match the recomputed output hash — at which point the replay has already diverged and must be restarted from the last valid boundary, not patched forward.

The tempting wrong decision is to recompute everything and compare final outputs. That masks divergence: a permutation in an intermediate prompt can wash out to an identical final answer on most inputs and differ on the tail. The boundary must be enforced *per node*, not per trace.

## Operational Effect

Enforcing per-node replay boundaries changes three things in the harness:

1. **Replay cost drops** where boundaries are drawn early: fan-in nodes are not re-run against live systems, so replays are hermetic and fast. The cost is that the replay validates only the reasoning *downstream* of the injected inputs, not the retrieval itself — which is the correct scope, because retrieval non-determinism is a property of the index, not the agent.
2. **Divergence is detected at the node where it occurs**, with the span's `gen_ai.prompt` (or tool-result) hash as the tripwire. This converts a silent wrong-answer failure into a localized, actionable one.
3. **The trace must be re-exported with ordered-list attributes** for any list-valued input at a boundary node. Without that, the boundary is drawable but not replayable, and the harness must refuse rather than guess.

The failure mode this prevents — a replay that completes cleanly, matches span structure, and still produces a different trajectory — is the one that erodes trust in the replay tool fastest, because it fails silently and only on the tail.

```python
from __future__ import annotations

from dataclasses import dataclass
from typing import Iterable


class ReplayBoundaryError(RuntimeError):
    """Raised when a span cannot be safely recomputed during replay."""


@dataclass(frozen=True)
class SpanNode:
    span_id: str
    parent_span_id: str | None
    link_ids: tuple[str, ...]
    # True if the span carries an ordered, content-bearing list input
    # (message history, tool-result array, ranked docs).
    has_ordered_list_input: bool
    # True if an ordered list input is recorded as an explicit ordered
    # attribute rather than inferred from timestamps.
    ordered_list_recorded: bool
    output_hash: str


def classify_replay_boundary(node: SpanNode, ancestors: Iterable[str]) -> str:
    """
    Return 'recompute' or 'inject'. Raise ReplayBoundaryError when the
    node's inputs are neither ancestor-derived nor fully recorded, i.e.
    the boundary cannot be drawn safely and the harness must refuse.
    """
    ancestor_set = set(ancestors)

    content_inbound = [lid for lid in node.link_ids if lid not in ancestor_set]
    is_fan_in = len(node.link_ids) >= 2 or len(content_inbound) >= 1

    if node.has_ordered_list_input and not node.ordered_list_recorded:
        raise ReplayBoundaryError(
            f"span {node.span_id}: ordered list input is load-bearing but not "
            "recorded as an ordered attribute; replay order is undefined. "
            "Re-export the trace with an ordered attribute before replaying."
        )

    if is_fan_in:
        # Fan-in: inputs must be re-materialized from the record, not recomputed.
        return "inject"

    return "recompute"


def replay_node(node: SpanNode, ancestors: Iterable[str], recompute_fn) -> str:
    """
    Execute one node under the boundary policy and verify the output hash.
    """
    decision = classify_replay_boundary(node, ancestors)

    if decision == "inject":
        # Inputs are injected from the record; the node's own output is
        # taken as recorded. No live recomputation occurs.
        return node.output_hash

    recomputed = recompute_fn(node)
    if recomputed != node.output_hash:
        raise ReplayBoundaryError(
            f"span {node.span_id}: output hash mismatch on recompute "
            f"(recorded={node.output_hash}, recomputed={recomputed}); "
            "replay has diverged — restart from the last valid boundary."
        )
    return recomputed
```