Multi-Agent Distributed Tracing: 5 Gaps That Break Your Spans

Every team building multi-agent systems hits the same wall on the same day: the first production failure they cannot debug. The orchestrator dispatches a task to three workers. One worker calls an MCP tool server. Something upstream returns garbage. The final output is wrong. You open Jaeger. Five root spans. None of them connect.

This is not a skill gap. It's a structural one. Distributed tracing for multi-agent systems breaks at five specific points microservice tracing never had to handle: MCP server boundaries, async queue handoffs, missing orchestrator span hierarchy, cost attributed at the wrong level, and head-based sampling that throws away the failure traces you needed.

The OpenTelemetry GenAI semantic conventions (v1.41.0 as of May 2026) cover the LLM call cleanly — gen_ai.request.model, gen_ai.usage.input_tokens, gen_ai.usage.output_tokens, tool spans. What they don't yet cover is automatic context propagation across MCP servers and message queues.^[1] Single-agent traces are clean. Multi-agent traces are broken — until you close the gaps yourself.

This article maps the five gaps, the minimal code to close each, and the build order that produces a working trace tree at every phase.

Distributed tracing in a multi-agent system means preserving a single trace_id and a 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 one connected causal graph instead of orphaned fragments.^[4]

Microservice tracing solved this for HTTP services: propagate a traceparent header on every request and spans self-assemble into a tree. It works because instrumented HTTP clients propagate headers by default and service boundaries are explicit synchronous calls.

Multi-agent systems break that assumption in four ways. Some calls go through MCP servers that don't receive HTTP headers automatically. Some handoffs go through message queues with no headers at all. Parallel agents running concurrently create span relationships that are DAGs, not trees — parent-child is the wrong model. And a head-based sampler decides before knowing whether the trace will matter, discarding the slow, looping, or failing traces that were the entire reason for instrumenting.

The consistent symptom: 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 can name what triggered it.

Note: these are propagation gaps, not framework bugs. AG2, LangChain, and CrewAI emit OTel-compliant spans natively for LLM calls. The gaps live at the boundaries those frameworks don't own.

When an agent invokes an MCP server to execute a tool, the MCP protocol doesn't receive or propagate the traceparent header from the calling agent. Every MCP server operation lands as an isolated root span unless you inject the header manually at the invocation site.^[1]

Two things have changed in 2026 that make this easier but don't eliminate the gap. First, the OTel GenAI spec now defines MCP-specific span attributes: mcp.method.name, mcp.session.id, mcp.protocol.version, and gen_ai.tool.name — so MCP tool calls get proper semantic labeling when they do reach the backend.^[10] Second, SEP-414 (merged into the MCP protocol spec) standardizes W3C trace context propagation via the params._meta field, locking down the traceparent, tracestate, and baggage key names so traces can correlate across SDKs and gateways.^[11] But neither change makes propagation automatic. You still inject at the call site.

The fix is two lines: inject the current OTel context into a carrier dictionary, pass it as request headers. For HTTP transport, carriers become headers. For stdio transport (the common local MCP case), the carrier goes into params._meta — the protocol-standard location now that SEP-414 is merged.

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

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

The pattern is consistent across every queue implementation — SQS, Kafka, RabbitMQ, Redis Streams: serialize the OTel propagator state into the message metadata before enqueue, extract it before creating any spans on the consumer side. The propagator state is just a dict of strings (traceparent and optional tracestate), so it rides in any payload format.

The OpenTelemetry GenAI semantic conventions now define four agent operation types: create_agent, invoke_agent, invoke_workflow, and execute_tool.^[9] As of Semantic Conventions v1.41.0 (May 2026), these are still labeled Development — not Stable — but Datadog, Honeycomb, and New Relic already ingest them without SDK changes.^[2]

The distinction that matters for span hierarchy: invoke_agent span kind is CLIENT when the agent runs in a remote process (OpenAI Assistants API, AWS Bedrock Agents, any agent-over-HTTP pattern) and INTERNAL when it runs in-process (LangChain agents, CrewAI agents, AutoGen within the same process). The span kind determines how backends render parent-child relationships and calculate latency attribution. Getting it wrong produces misleading waterfall views.

For orchestration frameworks that treat a "crew" or "workflow" as distinct from individual agents — CrewAI is the canonical example — invoke_workflow is the right span for the top-level coordinator. Underneath it, individual agent invocations get invoke_agent.

What the spec still doesn't cover: per-agent cost attribution attributes, delegation depth, and a standard gen_ai.agent.role attribute (orchestrator vs. specialist). Use app.agent.* for those. When the spec adds them — which the GenAI SIG is actively working on — the migration is find-and-replace on attribute names, not re-instrumentation.^[1]

Cost attribution at the wrong level is the span design mistake most teams make on the first build. The instinct is to track token cost at the orchestrator span — the one that initiates the workflow. That gives you aggregate cost per request and nothing else. When a 5-agent workflow runs over budget, you need to know which worker is expensive.

The correct level is the invoke_agent span for each worker, with gen_ai.usage.input_tokens and gen_ai.usage.output_tokens recorded on the LLM call spans nested beneath it. A 50-step task with 5 agents and 10 tool calls each produces 250+ spans in a correctly instrumented trace.^[6] Query by app.agent.name and per-worker cost is a single aggregation — no post-processing, no log correlation.

Sampling is more consequential. Head-based sampling decides at trace ingestion — before the trace has completed. For fast-completing requests, that's efficient. For multi-agent workflows that loop, retry, or cascade into failures, it discards the precise traces you needed most. A 1% head-based sample that drops every slow or failed trace is worse than no sampling. It produces false confidence: only normal traces in the sample, baseline skewed toward success.

Tail-based sampling decides after the trace completes. Configure the OTel Collector's tailsamplingprocessor to retain 100% of traces with errors, traces that exceeded a latency threshold, and traces where total token cost exceeded the per-request budget. Clean, cheap traces get sampled aggressively.^[13]

Memory sizing matters. The processor buffers spans until decision_wait elapses. The formula: num_traces = expected_new_traces_per_sec × decision_wait_seconds × safety_factor. At 100 traces/sec and decision_wait: 10s with a 2× safety factor, you need num_traces: 2000 and roughly 40–100 MB of buffer RAM (at 20–50 KB per trace).^[12] Under-size the buffer and the processor starts evicting traces before they're sampled — silently, with no error.

Opening Jaeger to a wall of disconnected root spans is the diagnostic equivalent of finding a stack trace with no line numbers. The gap is there — you just need to find where the context dropped.

Start with span count. A 4-agent workflow should produce one root span. If you see N > 1 root spans, you have N − 1 propagation gaps. The gaps are almost always at process boundaries. Count the boundaries in your architecture: each MCP server call, each queue consumer, each HTTP client call to another service. Check them in order.

Second: look at span attributes on the orphaned root span. A root span with app.agent.role: worker means the queue consumer extracted nothing. A root span with gen_ai.tool.name: <something> means an MCP call didn't receive the carrier header. An orphaned span with no gen_ai.* attributes means the agent framework emitted the span but the calling context was already lost upstream.

Third: check the sampling pipeline. If error traces are missing from the backend entirely — not just disconnected, but absent — head-based sampling is dropping them before they arrive. Switch to tail-based before investigating further. Debugging propagation with a 1% head-based sampler that preferentially drops slow or failing traces is the equivalent of debugging a production outage with logs disabled.

The five gaps don't require a complete observability overhaul. Three lines of Python close the MCP boundary. Four lines close the queue context. The GenAI spec gives you the span names — you just need the correct span kind and the right namespace for custom attributes. Tail-based sampling is a Collector config change.

The harder problem is knowing which gaps exist in your architecture before a production failure surfaces them. The checklist above catches them in staging, where debugging a disconnected trace tree is annoying but not urgent. Finding out in production — tracing a live failure across 4 agents, 20 steps, and 8 orphaned root spans — is the expensive version of the same lesson.

Run a test request through your system today. Count the root spans. More than one means you already know where to start.