# When must an instance replay an agentic trace deterministically under OTel GenAI conventions: the span-parenting invariant that silently breaks replay under concurrent tool execution **Date of Record:** 2026 November 15 **Scope:** Applies to deterministic replay of agentic LLM traces captured under OpenTelemetry GenAI semantic conventions (gen_ai.* attributes, `gen_ai.operation.name`, span kinds `chat`/`execute_tool`/`invoke_agent`) where the agent may issue tool calls concurrently or interleave model turns with tool execution. Does not apply to single-threaded, strictly sequential agent loops, nor to replay systems that treat the trace as a flat event log rather than a span tree. ## Core Distinction A trace is *observationally complete* when every attribute needed to reconstruct the agent's next decision is present on some span. A trace is *deterministically replayable* when the span tree also encodes the *causal ordering* of those decisions. These are not the same property, and OTel GenAI conventions do not guarantee the second. The non-obvious boundary: an instance may replay a trace only if, for every `gen_ai.operation.name = "chat"` span, the set of `execute_tool` spans that supplied its input messages are all *ancestors or siblings-with-earlier-end-time in the same parent scope*. When a framework emits tool spans as children of the *agent* span rather than children of the *chat* span that requested them, and tools run concurrently, the emitted parent/child edges no longer distinguish "tool result consumed by turn N" from "tool result consumed by turn N+1." The trace remains observationally complete (all tool I/O is present) but replay produces a different message sequence than the original run. ## What Was Observed In a captured trace from an agent using parallel tool dispatch (three `execute_tool` spans under `invoke_agent`, two `chat` spans), the replay harness reconstructed the conversation by sorting spans by `start_time_unix_nano`. The original run had dispatched all three tools after turn 1 and consumed their results in turn 2. Replay produced turn 2 consuming only the first-completing tool, then re-dispatched the other two because the reconstructed prompt lacked their results — a different agent trajectory, different token counts, and a divergent final answer. Root cause: `gen_ai.tool.call.id` was present on the tool spans and on the assistant message's `tool_calls`, but the *chat span* that consumed them carried no back-reference. The only linkage was temporal, and concurrent execution made temporal ordering non-causal. OTel GenAI conventions define attribute names but do not mandate that a consuming `chat` span declare which `gen_ai.tool.call.id` values it ingested. ## Condition of Validity Deterministic replay is valid if and only if all of the following hold for the trace: 1. Every `chat` span carries the set of `gen_ai.tool.call.id` values it consumed, or every tool span is a descendant of the `chat` span that consumed it. 2. Tool spans that execute concurrently share a parent whose children are ordered by a monotonic sequence attribute, not by wall-clock start time. 3. Model sampling parameters (`gen_ai.request.temperature`, `seed`, `top_p`) are recorded on every `chat` span; absent a seed, replay is *reproducible-in-structure* but not *deterministic-in-content* and must be labeled as such. 4. No span in the causal chain was dropped by the exporter (check `otel.dropped_attributes_count` and sampler decisions recorded via `otel.trace_flags`). If condition 1 fails and tools ran concurrently, the trace is not replayable deterministically; it is only replayable *structurally* (same tool set, possibly different consumption order). ## Decision Boundary The decision is not "is the trace complete?" but "does the trace encode consumption edges?" Concretely: - **Sequential agent, tool spans children of chat span** → replay deterministically. - **Concurrent agent, tool spans children of chat span** → replay deterministically; order children by `gen_ai.tool.call.id` sequence or an explicit index attribute. - **Concurrent agent, tool spans children of agent span, no call-id back-reference on chat span** → do **not** claim deterministic replay. Fall back to structural replay and flag the trace. - **Any trace missing `gen_ai.request.seed` with temperature > 0** → deterministic replay of *content* is impossible regardless of span structure; replay only the control flow. The boundary is crossed the moment concurrency is introduced without an explicit consumption edge. It is not crossed by missing attributes alone, and it is not repaired by sorting on timestamps. ## Operational Effect Treating a structurally-replayable trace as deterministically-replayable produces false regression signals: the replayed agent diverges, the harness reports a behavioral change, and engineers investigate a model or prompt change that never occurred. The correct operational posture is to gate replay eligibility on the consumption-edge check at trace-ingest time, tag ineligible traces as `replay_mode=structural`, and refuse to emit deterministic-replay verdicts for them. This converts a silent correctness failure into an explicit, auditable classification. ```python from dataclasses import dataclass from typing import Iterable class ReplayIneligibilityError(RuntimeError): """Raised when a trace cannot support deterministic replay.""" pass @dataclass(frozen=True) class Span: name: str operation: str # gen_ai.operation.name parent_id: str | None span_id: str consumed_tool_call_ids: frozenset[str] emitted_tool_call_ids: frozenset[str] start_ns: int has_seed: bool temperature: float def assert_deterministically_replayable(spans: Iterable[Span]) -> None: spans = list(spans) by_id = {s.span_id: s for s in spans} tool_spans = [s for s in spans if s.operation == "execute_tool"] chat_spans = [s for s in spans if s.operation == "chat"] concurrent = len(tool_spans) > 1 and len({t.parent_id for t in tool_spans}) == 1 for chat in chat_spans: for tcid in chat.consumed_tool_call_ids: producer = next( (t for t in tool_spans if tcid in t.emitted_tool_call_ids), None ) if producer is None: raise ReplayIneligibilityError( f"chat span {chat.span_id} consumed tool call {tcid} " f"with no producing span" ) is_descendant = producer.parent_id == chat.span_id has_edge = tcid in chat.consumed_tool_call_ids if concurrent and not (is_descendant or has_edge): raise ReplayIneligibilityError( f"concurrent tool {producer.span_id} consumed by chat " f"{chat.span_id} lacks consumption edge; " f"replay would be structural only" ) for chat in chat_spans: if chat.temperature > 0.0 and not chat.has_seed: raise ReplayIneligibilityError( f"chat span {chat.span_id} has temperature={chat.temperature} " f"without gen_ai.request.seed; content replay is nondeterministic" ) ```