# In what scenarios must an instance treat inter-agent message lineage as non-authoritative when reconstructing causal trace graphs for emergent multi-agent behavior

**Date of Record:** 2026 November 7

**Scope:** Applies to multi-agent systems where causal trace graphs are reconstructed post-hoc from per-agent spans joined by message lineage identifiers (trace IDs, parent span IDs, correlation IDs, message IDs). Does not apply to single-agent request tracing, nor to systems with a single synchronous message bus that guarantees a total order and a single authoritative parent pointer per message.

## Core Distinction

There are two different questions a causal trace graph can answer, and they diverge precisely at the boundary this record concerns:

1. **"Why did agent B emit this output?"** — a *causal explanation* question, answered by the true dependency relation: B's output depended on the content of a specific message from A.
2. **"Which span is B's parent?"** — a *lineage provenance* question, answered by whatever parent pointer the instrumentation wrote down.

In synchronous, single-threaded call graphs these coincide. In emergent multi-agent behavior they do not, because agents *re-derive* messages, *fan in* from multiple upstream agents, *retry and re-send* under new IDs, and *act on shared state* (a blackboard, a vector store, a task queue) rather than on a discrete message. The lineage field then records a *transport fact* (who handed the bytes to whom), not a *dependency fact* (whose content changed the outcome).

The non-obvious invariant: **a message-lineage edge is necessary but not sufficient evidence for a causal edge.** Treating lineage as authoritative produces trace graphs that are *topologically valid but causally wrong* — they look well-formed (every span has one parent, no orphans, no cycles) while systematically misattributing emergent behavior to the wrong upstream agent.

## What Was Observed

In a three-tier agent deployment (planner → N workers → aggregator), a class of failures was traced where the aggregator produced a wrong synthesis. The lineage graph showed the aggregator's parent as worker W3 (the last message it received). The true causal dependency was on W1's output, which W3 had *summarized* and forwarded under a new message ID with `parent_message_id` set to its own span. The lineage graph was a clean tree; the causal graph was a diamond with a critical path through W1. Post-hoc analysis using lineage alone attributed 100% of the fault to W3 across 41 incidents; content-diff replay attributed the majority to W1's summarization loss in 33 of them.

Three mechanisms produced the divergence:

- **Re-identification on forward.** A forwarding agent mints a new message ID; downstream lineage points at the forwarder, erasing the original producer. Lineage depth grows; causal depth does not.
- **Fan-in collapse.** Aggregators that consume a set of messages must pick one `parent` for a span that truly has N parents. Instrumentation picks "last received" or "first received" arbitrarily. The causal graph is a DAG; the lineage graph is forced to be a tree.
- **Shared-state causality.** An agent that reads a blackboard entry written by another agent has *no message* between them. Lineage records nothing; the causal edge exists and is invisible.

## Condition of Validity

The lineage graph may be treated as authoritative for causal reconstruction **only** when all of the following hold:

1. Every inter-agent handoff carries an immutable, producer-assigned message ID that is never re-minted on forward (forwarders append, they do not replace).
2. Each consumer span records *all* contributing message IDs (a set, not a scalar parent), so fan-in is representable.
3. All causal influence flows through explicit messages — no shared mutable state, no ambient stores, no side channels.
4. Retries and re-sends preserve the original message ID (idempotent identity), so lineage does not fork on transport retry.

When any condition fails, lineage is a *transport log*, not a *causal record*, and must be downgraded to corroborating evidence.

## Decision Boundary

The operator decision is: **when reconstructing causality, do you trust the lineage edge or do you require content-level corroboration?**

- **Trust lineage** when the four validity conditions hold, throughput matters more than attribution precision, and the system is closed (no shared state). Cost: cheap, O(spans) join.
- **Require content corroboration** when any condition fails, or when the trace is being used for *fault attribution* or *emergent-behavior analysis* (the two highest-stakes uses). Corroboration means: replay the consumer's input against the producer's output and confirm the consumer's behavior changes when the producer's content is perturbed. Cost: O(spans × replay), and replay must be deterministic — if the agents are non-deterministic, corroboration itself becomes probabilistic and must report a confidence, not a boolean.

The boundary is crossed the moment lineage is used to answer "why," not "how." Instrumentation designed for "how" (transport) silently answers "why" (causality) with the wrong data unless the four conditions are checked first.

## Operational Effect

Systems that skip this check exhibit a characteristic failure signature: fault attribution is *stable and confident and wrong*, because the lineage tree is always well-formed. The aggregator/forwarder is over-blamed; the upstream producer whose content was lost in a summarization hop is under-blamed. Remediation targets the wrong service. The correct operational posture is to store, per consumer span, the **set** of contributing message IDs plus a content hash of each, and to compute causal edges by hash-match against producer outputs — lineage becomes a *candidate edge generator*, and content equality becomes the *edge validator*. Where hashes cannot match (non-deterministic transforms), record the edge as `causal: unverified` rather than defaulting to the lineage parent.

```python
import hashlib
from dataclasses import dataclass, field


class UnverifiedCausalityError(RuntimeError):
    """Raised when a causal edge is asserted from lineage alone under conditions
    where lineage is non-authoritative (re-minted IDs, fan-in, shared state)."""
    pass


@dataclass
class Span:
    span_id: str
    agent: str
    parent_message_id: str | None          # scalar: what lineage claims
    contributed_message_ids: set[str] = field(default_factory=set)  # what content says
    output_hash: str | None = None
    reads_shared_state: bool = False


def validate_causal_edge(producer: Span, consumer: Span, id_was_reminted: bool) -> str:
    """
    Returns 'causal', 'candidate', or raises. Never silently trusts lineage.
    """
    if consumer.reads_shared_state:
        # Causal edge exists but is invisible to lineage; must be marked, not assumed.
        raise UnverifiedCausalityError(
            f"consumer {consumer.span_id} reads shared state; "
            f"lineage parent {consumer.parent_message_id} cannot be authoritative"
        )

    if id_was_reminted:
        # Forwarder erased the true producer; lineage points at the wrong agent.
        raise UnverifiedCausalityError(
            f"message id re-minted between {producer.span_id} and {consumer.span_id}; "
            f"lineage edge is a transport fact, not a causal fact"
        )

    if len(consumer.contributed_message_ids) > 1:
        # Fan-in: lineage forced a tree onto a DAG. Require content corroboration.
        if producer.output_hash is None:
            raise UnverifiedCausalityError(
                f"fan-in consumer {consumer.span_id} has {len(consumer.contributed_message_ids)} "
                f"contributors; no output hash to corroborate producer {producer.span_id}"
            )
        return "candidate"  # caller must hash-match before promoting to 'causal'

    if producer.output_hash is None:
        raise UnverifiedCausalityError(
            f"no content hash for producer {producer.span_id}; "
            f"cannot validate edge {'->'} {consumer.span_id}"
        )

    return "causal"


def reconstruct_edge(producer: Span, consumer: Span, id_was_reminted: bool) -> str:
    status = validate_causal_edge(producer, consumer, id_was_reminted)
    if status == "candidate":
        # Promote only on content equality.
        expected = hashlib.sha256(producer.output_hash.encode()).hexdigest()
        if expected not in consumer.contributed_message_ids:
            raise UnverifiedCausalityError(
                f"content mismatch: producer {producer.span_id} hash not among "
                f"consumer {consumer.span_id} contributors; lineage edge rejected"
            )
        return "causal"
    return status
```