# Where must an instance of the GenAI trace correlation ID be minted to survive memory mutation, and where does late-minting silently break the invariant?

**Date of Record:** 2026 November 12

**Scope:** Applies to any GenAI system that emits a single trace correlation ID (hereafter `trace_id`) intended to bind a prompt, its retrieval fan-out, its tool calls, and any memory-mutation side effects into one causally ordered record. Does *not* apply to single-turn stateless inference with no retrieval, no tools, and no persistent memory, where a request-scoped ID is sufficient.

## Core Distinction

The distinction that matters is between **request-scoped correlation** and **causality-scoped correlation**. A request-scoped ID is minted at the HTTP/gRPC ingress boundary and is adequate when the trace is a flat request→response span. A causality-scoped ID must be minted *before the first mutation of shared state that the trace is supposed to explain* — i.e., before the first write to the vector store, the episodic memory table, the tool-side effect, or the scratchpad. The failure mode is not that the ID is missing; it is that the ID is minted at ingress but the *memory subsystem mints its own internal ID* for the mutation record, and the two are joined only by an after-the-fact log correlation that is lossy under retries and concurrent turns.

The non-obvious invariant: **the `trace_id` must be an ancestor of every memory-mutation record's primary key, not a sibling attribute attached to it.** If the mutation record can exist without the `trace_id` (e.g., because the mutation is written by a background compactor, a retry worker, or a tool server that received the ID out-of-band), then the trace is no longer a causal record — it is a best-effort join, and the join fails exactly when you need it: during incident reconstruction of a poisoned memory entry.

## What Was Observed

In a multi-turn agent with a long-term memory store, the following sequence was observed during a post-incident reconstruction:

1. Turn N: model issues a `memory.write` tool call to persist a user preference. The ingress-minted `trace_id` is propagated in the tool-call envelope.
2. The memory service accepts the write, but enqueues it to an async applier queue. The applier worker **does not receive the `trace_id`** — it receives only the payload and a service-generated `mutation_id`.
3. The applier retries once due to a transient lock, then succeeds. Two mutation records exist: the original (aborted) and the retry. Only the retry is durable.
4. Turn N+3: retrieval surfaces the poisoned preference. The prompt that consumed it has a `trace_id`. The retrieval span has a `trace_id`. The mutation record that created the poisoned entry has **no `trace_id`** and a `mutation_id` that appears nowhere in the prompt-side trace.

The reconstruction team could prove *that* a bad memory existed and *which turn consumed it*, but could not prove *which turn wrote it* without a full-table scan and timestamp heuristics. The heuristic was wrong because the retry shifted the write timestamp by 4.2 seconds across a turn boundary.

A second, subtler observation: when the tool server was instrumented to *echo back* the `trace_id` in its response, the echo arrived after the side effect had already committed. The echo made the trace *look* complete in the span graph while the mutation record itself remained unlinked. This is the dangerous case — **false completeness**.

## Condition of Validity

The invariant "every memory mutation is causally attributable to exactly one `trace_id`" holds only under all of the following:

- The `trace_id` is present in the **mutation payload itself**, not merely in the transport envelope. Envelope propagation is lost at every async boundary (queues, retry workers, batch compactors, outbox pattern dispatchers).
- The mutation store enforces a **non-null foreign key** from `mutation_record.trace_id` to the trace registry, or equivalently rejects writes lacking a `trace_id`. A nullable column with a "should always be set" comment is not enforcement.
- Retries are **idempotent under the same `trace_id`** — the retry must carry the original `trace_id` and a stable idempotency key derived from it, so that the aborted original and the durable retry are recognizable as the same causal event.
- Background/compaction mutations carry a `trace_id` of the *originating* turn, not of the compactor run. A compactor that rewrites memory under its own `trace_id` severs the causal chain.

Where any of these is violated, the trace degrades from a causal record to a sampled join, and the degradation is invisible until reconstruction.

## Decision Boundary

Mint the `trace_id` at ingress **only if** all mutation paths are synchronous and in-process. The moment any of the following is true, the `trace_id` must be minted *earlier* — at the turn/session coordinator, before the first retrieval or tool dispatch — and must be **carried in the payload of every mutation**, with the mutation store rejecting payloads that lack it:

- Async applier queues or outbox dispatchers exist.
- Tool servers are separate processes/services.
- Retry workers exist that can re-drive a mutation.
- Any background compaction or summarization rewrites memory.

The boundary is crossed the instant a mutation can outlive the request that spawned it. Below that boundary, request-scoped IDs are correct and cheaper. Above it, late-minting (at the tool server, at the applier, at the compactor) produces **orphan mutations** that are individually well-formed and collectively unattributable.

## Operational Effect

Concretely, the operational consequence is that incident reconstruction of a poisoned or corrupted memory entry changes from an O(1) trace lookup to an O(n) table scan with timestamp heuristics that are unreliable across retry and clock skew. The failure is silent under normal operation (traces look complete because tool servers echo the ID) and surfaces only during the exact incident where attribution matters. The mitigation is structural: make `trace_id` a non-nullable ancestor key on the mutation record, propagate it in the payload, and have the mutation store raise rather than accept an unattributed write. The cost is a small payload increase and a schema constraint; the alternative is a trace that lies about its own completeness.

```python
class UnattributedMutationError(RuntimeError):
    """Raised when a memory mutation reaches the store without a causal trace_id.

    This is a hard invariant violation, not a warning: the mutation would become
    an orphan that cannot be attributed during incident reconstruction.
    """
    pass


class MutationRecord:
    __slots__ = ("trace_id", "mutation_id", "payload", "idempotency_key")

    def __init__(self, trace_id, mutation_id, payload, idempotency_key):
        self.trace_id = trace_id
        self.mutation_id = mutation_id
        self.payload = payload
        self.idempotency_key = idempotency_key


def apply_mutation(raw: dict, *, trace_registry) -> MutationRecord:
    """Apply a memory mutation, enforcing causality-scoped correlation.

    `raw` is what arrives at the applier/compactor/tool server. If it lacks a
    trace_id -- because the ID lived only in the transport envelope and was lost
    at the async boundary -- we refuse the write rather than create an orphan.
    """
    trace_id = raw.get("trace_id")
    if not trace_id:
        raise UnattributedMutationError(
            f"mutation {raw.get('mutation_id')!r} has no trace_id in payload; "
            "envelope-only propagation is not sufficient across async boundaries"
        )
    if trace_id not in trace_registry:
        raise UnattributedMutationError(
            f"trace_id {trace_id!r} is not registered; refusing to mint an orphan mutation"
        )
    # Idempotency key must be derived from trace_id so retries collapse onto the
    # same causal event rather than producing a second, unattributable record.
    idem = raw.get("idempotency_key") or f"{trace_id}:{raw['mutation_id']}"
    return MutationRecord(trace_id, raw["mutation_id"], raw.get("payload", {}), idem)


def compact_memory(entries, *, originating_trace_id, trace_registry):
    """Background compaction MUST carry the originating turn's trace_id.

    A compactor that mints its own trace_id severs the causal chain between the
    rewritten entry and the turn that produced it.
    """
    if not originating_trace_id:
        raise UnattributedMutationError(
            "compaction run has no originating trace_id; rewritten entries would be orphans"
        )
    out = []
    for e in entries:
        out.append(apply_mutation(
            {"trace_id": originating_trace_id,
             "mutation_id": f"compact:{e['id']}",
             "payload": e},
            trace_registry=trace_registry,
        ))
    return out
```