# Which invariants prevent tool-call lineage from surviving across asynchronous agent boundaries **Date of Record:** 2026 November 17 **Scope:** Applies to OpenTelemetry GenAI semantic-convention spans (`gen_ai.*`) emitted by agent runtimes that execute tool calls across process, queue, or thread boundaries and then re-parent results. Does not apply to synchronous in-process tool dispatch where the parent span is still on the active context stack at completion time. ## Core Distinction The GenAI semantic conventions define *attribute* shape (e.g. `gen_ai.tool.name`, `gen_ai.tool.call.id`, `gen_ai.operation.name`, `gen_ai.usage.input_tokens`) but they do **not** define a lineage invariant that binds a tool *invocation* span to its *result* span when the two are emitted by different execution contexts. Lineage in practice is carried by two independent mechanisms: the W3C Trace Context (`trace_id`, `span_id`, `trace_flags`) propagated as headers, and the vendor-specific correlation key (usually `gen_ai.tool.call.id`). These two can disagree, and when they do, the trace backend will happily render a tree that is structurally valid and semantically wrong. The distinction that matters operationally: **trace-context propagation guarantees co-membership in a trace, not parenthood of a result.** A result span can be in the same trace as its invocation yet be parented to the wrong span, or be in a different trace entirely while carrying the correct `tool.call.id`. ## What Was Observed In a multi-agent deployment where an orchestrator enqueues tool invocations onto a Redis-backed worker pool, we observed the following sequence repeatedly under load: 1. Orchestrator span `S_inv` (operation `execute_tool`, `gen_ai.tool.name=search_docs`, `gen_ai.tool.call.id=tc_9f2`) ends and is exported. 2. The worker, running in a separate process, dequeues the job. The enqueue payload contained `traceparent` captured at *enqueue* time, which pointed at `S_inv`'s *parent* (the agent step span), not `S_inv` itself — because the propagation header was captured before `S_inv` was started, or because the worker's auto-instrumentation re-extracted the header from a stale carrier. 3. The worker emits `S_res` (operation `execute_tool`, same `tool.call.id`) parented to the agent step span. 4. The result is consumed by a *different* agent step that also emitted its own `execute_tool` span with a colliding or reused `tool.call.id` (IDs were generated from a monotonic counter reset per worker boot). The rendered trace showed two `execute_tool` spans as siblings under the agent step, with identical `tool.call.id` values, and no span that represented the actual invocation→result edge. Downstream latency attribution doubled, and a retry-detection rule keyed on `tool.call.id` fired spuriously. The non-obvious part: **no component violated its contract.** The propagator did what W3C Trace Context says. The worker did what auto-instrumentation says. The ID generator was locally unique. The failure is emergent from the interaction of an attribute-level correlation key and a context-level parent pointer that are maintained by different subsystems with different lifetimes. ## Condition of Validity The following invariant holds **only** when all three conditions are true, and is silently void otherwise: - **I1 (context continuity):** the `SpanContext` of the invocation span is the exact context extracted by the result emitter — i.e. the enqueue payload captured `traceparent` *after* `S_inv` was started, and the worker extracts from that same payload, not from ambient thread-local context. - **I2 (call-id uniqueness):** `gen_ai.tool.call.id` is unique across the *entire trace*, not merely within a process or worker. A per-worker counter satisfies local uniqueness and violates this. - **I3 (single-emitter):** exactly one span per `(tool.call.id, operation)` pair is emitted. Retries must either reuse the span (via links) or use a new `call.id`; re-emitting with the same ID under a new parent breaks join semantics. When I1 holds but I2 fails, you get *false joins* (two results attributed to one invocation). When I2 holds but I1 fails, you get *orphaned results* (correct correlation key, wrong parent — the tree is wrong but the key is right). When I3 fails, you get *fan-out ambiguity* that no query can resolve without reading span links, which most backends do not index by default. ## Decision Boundary Choose the lineage strategy by where the tool call crosses an asynchronous boundary: - **In-process, synchronous:** rely on ambient context; I1 is free. Do not add `tool.call.id`-based joins — they add cardinality without information. - **Cross-process via queue/worker:** you must capture `traceparent` from the *live* invocation context at enqueue time (not from the request carrier), and you must generate `tool.call.id` from a trace-scoped source (e.g. derive from `trace_id` + a span-local counter, or use a UUIDv7). If you cannot guarantee I2, **do not use `tool.call.id` as a join key**; instead emit an explicit span link from result to invocation and query links. - **Retries and fan-out:** treat each attempt as a distinct `call.id` and link attempts to the logical invocation. Reusing the ID to "keep the trace clean" is the wrong trade — it destroys the only signal that distinguishes attempt from duplicate. - **Cross-agent handoff (A2A):** the receiving agent's span must be a child of the *sending* span's context, and the `call.id` must be carried in the message envelope, not regenerated. Regeneration at the boundary is the single most common cause of orphaned results in agent meshes. The boundary is: **if the enqueue and the dequeue are in different processes, the trace context must be treated as data, not as ambient state, and validated on extraction.** ## Operational Effect When the invariant is violated, the observable symptoms are: (a) trace trees that are well-formed but have tool results as siblings of their invocations rather than children; (b) `tool.call.id` collisions that inflate retry metrics and corrupt per-tool latency histograms; (c) span counts that exceed invocation counts without a corresponding error signal, because the extra spans are "successful." The correct remediation is not to patch the backend query but to enforce the invariant at the emit site: validate that the extracted context's `span_id` matches the recorded invocation `span_id` before emitting the result span, and fail closed (emit an error span, do not silently re-parent) when it does not. The code below encodes that guard. ```python from __future__ import annotations from dataclasses import dataclass class ToolLineageInvariantError(RuntimeError): """Raised when a tool-result span would violate invocation/result lineage.""" @dataclass(frozen=True) class SpanContext: trace_id: str span_id: str @dataclass(frozen=True) class ToolInvocation: call_id: str tool_name: str span_context: SpanContext # context of the invocation span itself propagated: SpanContext # context captured in the enqueue payload def emit_result_span( invocation: ToolInvocation, extracted: SpanContext, seen_call_ids: set[str], *, attempt: int = 0, ) -> SpanContext: """Validate I1/I2/I3 before emitting a tool-result span. Returns the parent context the result span must use. Raises ToolLineageInvariantError (fail-closed) rather than silently re-parenting. """ # I1: the worker must extract the invocation's own context, not an ancestor's. if extracted != invocation.span_context: raise ToolLineageInvariantError( f"I1 violated for call_id={invocation.call_id!r}: " f"extracted span_id={extracted.span_id!r} != invocation " f"span_id={invocation.span_context.span_id!r}; result would be " f"orphaned under the wrong parent." ) # I2: call_id must be trace-scoped unique, not process-local. if invocation.call_id in seen_call_ids: raise ToolLineageInvariantError( f"I2 violated: call_id={invocation.call_id!r} already emitted in " f"trace {invocation.span_context.trace_id!r}; per-worker counters " f"do not satisfy trace-scoped uniqueness." ) # I3: retries must not reuse the id without an explicit link. if attempt > 0: raise ToolLineageInvariantError( f"I3 violated: attempt={attempt} for call_id={invocation.call_id!r} " f"must use a fresh call_id and a span link to the prior attempt, " f"not a re-emit under the same id." ) seen_call_ids.add(invocation.call_id) return invocation.span_context ```