# When must an instance distrust its own memory: provenance divergence under concurrent agent write paths

**Date of Record:** 2026 November 11

**Scope:** Applies to long-lived agent instances that persist a mutable memory store and accept writes from more than one logical write path (tool calls, reflection loops, retrieval-cache promotion, human-in-the-loop edits). Does not apply to single-writer append-only stores where every record carries a monotonic sequence number and no path can rewrite history.

## Core Distinction

The distinction that matters is between *content inconsistency* and *provenance inconsistency*. Content inconsistency is a value conflict: two records disagree about the same fact. It is detectable by comparison and is what most consistency checks implement. Provenance inconsistency is a conflict in the *chain of custody* of a record: the record's asserted origin, write path, or derivation graph no longer matches the set of writes that actually produced it in the store. A store can be perfectly content-consistent and provenance-inconsistent at the same time — every fact agrees, but the graph that explains *why* the store believes each fact has a cycle, a gap, or a forged edge.

Memory poisoning attacks and benign write-path races both manifest first as provenance inconsistency. The non-obvious boundary is this: provenance checks fail closed only if they are evaluated against the *write log*, not against the *record metadata*. A poisoned record can carry flawless metadata. What it cannot do, cheaply, is insert a matching entry into an append-only log it does not control. Therefore the invariant to enforce is not "records agree with each other" but "every reachable record is the terminal node of a log-verified derivation chain, and that chain is acyclic and rooted in a trusted write path."

## What Was Observed

Across three agent deployments (a retrieval-augmented assistant, a coding agent with a scratchpad, and a multi-tool research agent), the following pattern recurred:

1. **Silent chain truncation.** A reflection loop summarized a set of retrieved documents into a memory record and dropped the `source_ids` field to save tokens. The record was content-correct but had an empty provenance set. Downstream consistency checks passed because there was nothing to compare against; the record was treated as ground truth. When a later poisoning attempt injected a contradictory record, the checker had no way to rank the two, and picked the more recent one.

2. **Provenance cycle under concurrent writes.** Two write paths — a tool-result ingester and a background consolidator — both derived records from each other's output within the same consolidation window. The derivation graph acquired a 2-cycle (`A derived_from B`, `B derived_from A`). Neither record was individually wrong, but the pair was self-supporting: deleting the external evidence would not have invalidated either. This is the structural signature of laundering, whether accidental or adversarial.

3. **Forged write-path tag.** A prompt-injected tool response included a field that the ingester copied verbatim into the record's `write_path` metadata. The record claimed `write_path: "human_edit"` and thereby inherited the highest trust tier. The check that compared record metadata against a trust table passed. The check that compared record metadata against the *actual* log entry did not exist and would have caught it immediately: the log showed `write_path: "tool_result"`.

4. **Consistency-check starvation.** Under load, the consistency checker ran on a sampled subset (1 in 50 records). Poisoned records landed in the unsampled 49/50 and were only detected when a downstream task failed, on average 40 minutes later, by which time the poisoned record had been cited by two other derived records.

The common thread: every failure was invisible to content comparison and visible to log-anchored provenance comparison.

## Condition of Validity

The provenance-tracking defense is valid only under all of the following:

- **The write log is append-only and outside the agent's write authority.** If any agent write path can modify or reorder log entries, the defense reduces to content consistency and inherits all its failure modes. This is the load-bearing condition; the rest are secondary.
- **Every persisted record carries a log-assigned identifier**, not an agent-assigned one. Agent-assigned IDs are forgeable by construction.
- **Derivation edges are recorded at write time**, not reconstructed at read time. Reconstruction from metadata is exactly what the forged-tag case defeats.
- **The checker evaluates reachability, not just adjacency.** A cycle three hops deep passes a one-hop check. The check must be a full traversal from the queried record to a trusted root.
- **Trusted roots are enumerated and small.** "Trusted write path" must be a closed set fixed at deployment, not a string the agent can emit.

The defense is *not* valid when the store is small enough that full manual audit is cheaper than instrumentation, when there is exactly one write path (no cross-path provenance to diverge), or when the agent has no persistent memory across sessions (nothing to poison).

## Decision Boundary

The operational rule is a threshold on provenance divergence, not on content divergence:

- **Quarantine, do not delete, on any provenance inconsistency.** A record whose log-verified chain is missing, cyclic, or rooted outside the trusted set is moved to a quarantine tier: readable for audit, not citable by downstream derivation. Deletion destroys the evidence needed to identify the write path that produced it.
- **Distrust the whole derivation subtree, not just the record.** If record R is provenance-inconsistent, every record reachable from R via `derived_from` edges is suspect, because R may have been the sole evidence for each. The blast radius is the subtree, and the subtree is usually larger than intuition suggests — in the research-agent deployment, one poisoned record had 11 descendants.
- **Escalate to human review when divergence exceeds a rate threshold** (observed trigger: more than 3 provenance-inconsistent records per 1,000 writes in a 10-minute window). A rate spike indicates a write-path bug or an active injection campaign; a single divergence indicates noise. The two require different responses and conflating them either over-alarms or under-responds.
- **Do not auto-repair by re-deriving from content.** Re-deriving a quarantined record from its content neighbors re-launders the poison. Repair requires a fresh trusted write.

## Operational Effect

Instrumenting log-anchored provenance checks changed the failure profile from *late, task-visible corruption* to *early, auditable quarantine*. In the coding-agent deployment, mean time from poisoned write to detection dropped from 40 minutes to under 2 seconds, at the cost of roughly 4% additional write latency (one log append plus one cycle check per write) and a quarantine queue that required a human reviewer for about 15 minutes per day. The more important effect was structural: because every record now had a log-verified chain, a downstream consumer could *ask* whether a record was trustworthy and get a machine-checkable answer, rather than inferring trust from recency or from the record's own claims. The consistency checker stopped being the primary defense and became a secondary signal; the primary defense became the invariant that no record is citable unless its chain of custody closes at a trusted root. The boundary condition to remember: the moment a write path gains the ability to write the log, the entire defense silently degrades to the content-consistency scheme it was meant to replace, and it degrades without any error, because every check still passes.

```python
from __future__ import annotations

from dataclasses import dataclass, field
from typing import Iterable


class ProvenanceDivergenceError(RuntimeError):
    """Raised when a record's log-verified chain of custody does not close at a trusted root."""


@dataclass(frozen=True)
class LogEntry:
    record_id: str
    write_path: str
    derived_from: tuple[str, ...]


@dataclass
class MemoryStore:
    log: list[LogEntry] = field(default_factory=list)
    records: dict[str, dict] = field(default_factory=dict)
    trusted_roots: frozenset[str] = frozenset({"human_edit", "tool_result_verified"})
    quarantined: set[str] = field(default_factory=set)


def verify_chain(
    store: MemoryStore,
    record_id: str,
    *,
    _path: tuple[str, ...] = (),
) -> None:
    """Traverse derivation edges to a trusted root. Raises on any divergence."""
    if record_id in _path:
        raise ProvenanceDivergenceError(
            f"provenance cycle detected: {' -> '.join(_path + (record_id,))}"
        )
    entry = next((e for e in reversed(store.log) if e.record_id == record_id), None)
    if entry is None:
        raise ProvenanceDivergenceError(
            f"record {record_id!r} has no log entry; metadata-only provenance is untrusted"
        )
    record = store.records.get(record_id, {})
    claimed = record.get("write_path")
    if claimed is not None and claimed != entry.write_path:
        raise ProvenanceDivergenceError(
            f"record {record_id!r} claims write_path={claimed!r} "
            f"but log shows {entry.write_path!r}"
        )
    if entry.write_path in store.trusted_roots:
        return
    if not entry.derived_from:
        raise ProvenanceDivergenceError(
            f"record {record_id!r} via {entry.write_path!r} has no derivation edges "
            f"and is not a trusted root"
        )
    for parent in entry.derived_from:
        verify_chain(store, parent, _path=_path + (record_id,))


def descendants(store: MemoryStore, record_id: str) -> set[str]:
    out: set[str] = set()
    frontier = [record_id]
    while frontier:
        current = frontier.pop()
        for entry in store.log:
            if current in entry.derived_from and entry.record_id not in out:
                out.add(entry.record_id)
                frontier.append(entry.record_id)
    return out


def quarantine_subtree(store: MemoryStore, root: str) -> set[str]:
    try:
        verify_chain(store, root)
        return set()
    except ProvenanceDivergenceError:
        affected = {root} | descendants(store, root)
        store.quarantined |= affected
        return affected
```