Distributed Tracing for Multi-Agent Systems: Closing the 5 Propagation Gaps

There's a specific moment every team building multi-agent systems hits: the first production failure they can't debug. The orchestrator sent a task to three workers. One worker called an MCP tool server. Something upstream produced garbage, and the final output is wrong. You open Jaeger. You see five root spans. None of them connect.

This isn't an instrumentation skill gap. It's a structural problem. Distributed tracing for multi-agent systems breaks at five specific points that microservice tracing never had to handle: MCP server boundaries, async queue handoffs, missing orchestrator span hierarchy, cost attribution at the wrong level, and head-based sampling that discards your most important failure traces.

The OpenTelemetry GenAI semantic conventions cover the LLM call itself well — gen_ai.request.model, gen_ai.usage.input_tokens, gen_ai.usage.output_tokens, and tool spans. What they don't yet standardize is the agent-to-agent relationship layer. There's no gen_ai.agent.role attribute in the 2026 spec, no standard for orchestrator delegation depth, and no automatic context propagation across MCP servers.^[1] You get solid single-agent traces and broken multi-agent traces — unless you close the gaps yourself.

This article covers exactly those five gaps and the minimal code required to close each one.

Distributed tracing in a multi-agent system means preserving a single trace_id and coherent parent-child span hierarchy across N agent processes, tool calls, message queues, and MCP servers — so every reasoning step, delegation, and invocation appears as a connected causal graph rather than isolated fragments.^[4]

Microservice tracing solves the same problem for HTTP services: propagate a traceparent header through every request, and the spans self-assemble into a tree. It works because HTTP clients propagate headers by default when instrumented, and service boundaries are explicit synchronous calls.

Multi-agent systems break this assumption in four ways. Some calls go through MCP servers that don't receive HTTP headers automatically. Some handoffs go through message queues where there are no headers at all. Agent frameworks may not emit the invoke_agent span structure the GenAI conventions specify. And when the system is under load, a head-based sampler will make its decision before it knows whether the trace will be interesting — discarding the slow, looping, or failing traces you most need.

The result teams consistently report: a 4-agent workflow that fails halfway produces 3–10 orphaned root spans in Jaeger or Zipkin with no way to reconstruct the causal chain.^[1] Each agent did something. Nobody knows what triggered it.

Model Context Protocol servers are the clearest example of the MCP boundary problem. When an agent invokes an MCP server to execute a tool, the MCP protocol doesn't automatically receive and propagate traceparent headers from the calling agent. Each MCP server operation appears as an isolated root span unless you manually inject the header at the invocation site.^[1]

This produces the specific symptom teams report: a query to a multi-agent system that should produce one connected trace instead produces 3–10 orphaned root spans in Jaeger or Zipkin, with no way to join them in the dashboard. The orchestrator span shows the call was made. The MCP server span shows the tool ran. There's no parent-child relationship between them.

The fix requires two steps. Before making the HTTP call to the MCP server, inject the current OTel context into a carrier dictionary and pass that dictionary as request headers. One function, one extra argument.

Message queues are the second most common trace-severing boundary. When an orchestrator enqueues a task for a worker agent, the trace context — specifically the current trace_id and span_id — has no automatic path to the consumer side. The worker starts processing and emits its first span, which becomes a new root span with no connection to the orchestrator.

The gap is silent. No error is thrown. The queue sends and receives messages correctly. The worker completes its task. The traces are just permanently disconnected.^[4]

The pattern for closing this gap is consistent across all queue implementations: serialize the OTel propagator state into the message metadata before enqueue, and extract it before creating any spans on the consumer side.

The OpenTelemetry GenAI semantic conventions define invoke_agent spans for agent execution and execute_tool spans for tool invocations. As of early 2026, the conventions cover individual LLM calls, tool invocations, and session-level metrics with reasonable consistency. Major vendors — Datadog, Honeycomb, New Relic — already support them natively.^[2]

What the spec doesn't yet cover is the relationship between orchestrator and worker agents. There's no standard gen_ai.agent.role attribute (orchestrator vs. specialist), no standard way to represent delegation depth, and no standard for cost attribution across a full agent DAG.^[1] The OTel GenAI SIG is working on this, but multi-agent orchestration spans are experimental heading into 2026. If you start emitting spans with gen_ai.agent.role attributes today, you'll likely need to rename them when the standard stabilizes.

The practical approach: use the app.agent.* namespace for all orchestrator-specific attributes. This separates your custom attributes from the gen_ai.* namespace and won't conflict with whatever attribute names the spec eventually standardizes. The invoke_agent span name itself follows the GenAI convention and should stay as-is.^[2]

For in-process agent calls, the startActiveSpan API handles parent-child relationships automatically — any spans created inside the callback become children of the current span without explicit parent references.^[3] The propagation gaps described in Sections 1 and 2 only apply at process and service boundaries.

Cost attribution is the span design decision most teams get wrong first. The natural instinct is to track token costs at the orchestrator span level — the span that initiates the whole workflow. But that gives you aggregate cost per request, not cost per agent call. When a 5-agent workflow runs over budget, you need to know which worker is expensive, not just that the request was.

The correct level is the invoke_agent span for each worker, where you record gen_ai.usage.input_tokens and gen_ai.usage.output_tokens on the LLM call spans nested beneath it. In a 50-step task with 5 agents and 10 tool calls each, a correctly instrumented trace produces 250+ spans.^[6] Query them by app.agent.name and you get per-worker cost breakdown without post-processing.

Sampling is more consequential. Head-based sampling makes its decision at trace ingestion — before the trace has completed. For fast-completing requests, this is efficient. For multi-agent workflows that loop, retry, or cascade into failures, it will discard the precise traces you need to debug. A 1% head-based sample that drops all slow or failed traces is worse than no sampling — it produces false confidence that everything is running cleanly.^[7]

Tail-based sampling decides after the trace completes. Configure it to retain 100% of traces with errors, traces that exceeded a latency threshold, or traces where total token cost exceeded your per-request budget. Traces that completed cleanly and cheaply get sampled aggressively. The ones that matter get kept.

Adaptive sampling adjusts the rate based on observed error rates and latency anomalies — recommended for production systems where traffic and failure modes vary.^[6] More complex to configure than tail-based, but it substantially reduces storage costs at scale. Start with tail-based and migrate to adaptive once you have a clear picture of your failure distribution.

The five propagation gaps don't require a complete observability overhaul. Three lines of Python close the MCP boundary gap. Four lines close the queue context gap. Namespace discipline costs nothing. Tail-based sampling is a Collector config change.

What's harder is knowing which gaps exist in your architecture before a production failure surfaces them. The checklist above is designed to catch them in staging, where debugging a disconnected trace tree is frustrating but not urgent. Finding out in production — while tracing a live failure across 4 agents, 20 steps, and 5 orphaned root spans — is the expensive version of the same lesson.

Run a test request through your system today. Count the root spans in your trace backend. If you see more than one, you know exactly where to start.