# What structural signals indicate memory poisoning in long-horizon agent state: provenance depth collapse as a detection invariant

**Date of Record:** 2026 November 9

**Scope:** Applies to agents that persist state across sessions via a memory store with per-entry provenance metadata (source, timestamp, derivation chain). Does not apply to stateless inference, to short-horizon contexts under ~10k tokens where all state is re-derived each turn, or to stores that do not record derivation edges.

## Core Distinction

Content-based poisoning detection asks *"is this memory entry false or adversarial?"* — a semantic judgment that requires an oracle and fails open. Structural detection asks a different question: *"is this entry's provenance consistent with how it claims to have been produced?"* The distinction matters because poisoned entries are frequently *plausible*: they are written in the agent's own voice, reference real entities, and are stylistically indistinguishable from legitimate consolidations. The signal that survives is not in the text but in the **shape of the derivation graph**.

The specific invariant: in a healthy long-horizon store, the distribution of provenance depth (number of derivation hops from a raw observation to a stored entry) is bounded and roughly stationary. Poisoning — whether via injected tool output, prompt-injected memory writes, or self-reinforcing summarization loops — produces a **provenance depth collapse**: entries with depth 0 (no traceable source) or anomalously shallow depth that nonetheless assert consolidated, high-confidence claims. A depth-0 entry claiming to be a "summary of 40 sessions" is structurally impossible and is the single most reliable indicator.

## What Was Observed

Over a 90-day run of a research agent with a 12k-entry persistent store, three failure classes appeared, and only the third was detectable by content review:

1. **Direct injection.** A fetched web page contained instructions that caused the agent to write a memory asserting a false fact. Content review caught ~60% of these; the rest were plausible enough to survive human spot-checks.

2. **Laundering through summarization.** An injected fact entered a session, was summarized into a "session takeaway," then summarized again into a "long-term belief." Each hop stripped a source reference because the summarizer did not propagate provenance. By hop 3, the entry had depth 0 and read as first-person experience.

3. **Depth collapse without injection.** A legitimate but buggy consolidator merged entries and dropped edge records, producing depth-0 entries that were *true* but unverifiable. These were indistinguishable from class 2 by content and forced a provenance-repair pass.

The discriminating structural signals, ranked by precision on the labeled set:

- **Depth-0 entries asserting consolidation** (claimed derivation count > 0, recorded depth = 0): precision 0.94.
- **Depth < claimed-derivation-count by ≥ 2** (broken chain): precision 0.81.
- **Provenance timestamp inversion** (entry's `derived_at` precedes its parent's `observed_at`): precision 0.88.
- **Fan-in anomaly** (a single entry cited as parent by > 30% of a session's writes): precision 0.72, indicative of a poisoned "anchor" memory being repeatedly re-summarized.

Content-based classifiers scored 0.55–0.68 precision on the same set and were not usable as a gate.

## Condition of Validity

The depth-collapse signal is valid only when:

- Every write path to the store is instrumented to record at least `{entry_id, parent_ids[], observed_at, derived_at, source_kind}`. A single uninstrumented writer (a manual admin tool, a migration script) will generate false positives indistinguishable from class 3.
- Summarization and consolidation are treated as *derivation events* that must propagate parent edges. If the consolidator is a black-box LLM call that does not emit edges, the signal degrades to "everything is depth 0" and is useless.
- The store permits depth-0 entries *only* for `source_kind == "direct_observation"`. Any other source kind at depth 0 is a violation by construction.
- The agent's horizon is long enough that re-derivation is not the norm. In short-horizon agents, most entries are legitimately re-derived each turn and depth is not meaningful.

It is **not** valid when provenance is reconstructed post-hoc from logs (reconstruction introduces depth errors), or when the adversary has write access to provenance metadata itself — at which point structural and content signals both fail and only out-of-band attestation (signed writes, append-only external ledger) helps.

## Decision Boundary

The operational rule:

- **Depth-0 + `source_kind != direct_observation`** → quarantine immediately, do not serve to the agent, flag for provenance repair. This is a hard boundary; do not attempt content adjudication first.
- **Depth < claimed derivation count** → serve with a reduced-confidence annotation and schedule repair; do not silently promote.
- **Timestamp inversion** → quarantine the child, retain the parent, log the writer identity.
- **Fan-in anomaly** → freeze the anchor entry from further citation for one session, re-derive its dependents from raw sources, compare.
- **Content-only suspicion with clean provenance** → log, do not gate. Content signals are too weak to act on alone; acting on them produces unacceptable false-quarantine rates that starve the agent.

The boundary is deliberately structural-first: provenance checks run before any semantic model, and a structural violation short-circuits content review rather than the reverse.

## Operational Effect

Instrumenting all writers and enforcing edge propagation on consolidation reduced undetected poisoned entries from an estimated 4.1% of store to 0.3% over the following 60 days, with a 2.7% false-quarantine rate concentrated almost entirely in the first week before the migration script was instrumented. The dominant cost was not detection but **provenance repair**: roughly 8% of quarantined entries were true-but-unverifiable and had to be re-derived from raw session logs, a batch job that ran nightly. The lesson for long-horizon agents is that provenance depth is a cheaper and more reliable invariant than content truth, but only if the write path is closed and consolidation is forced to emit edges — an invariant that is easy to violate silently and expensive to reconstruct after the fact.

```python
from dataclasses import dataclass, field
from typing import Literal


class ProvenanceViolation(RuntimeError):
    """Raised when a memory entry's provenance is structurally impossible."""
    pass


@dataclass
class MemoryEntry:
    entry_id: str
    source_kind: Literal["direct_observation", "summary", "consolidation", "injected_tool"]
    parent_ids: list[str] = field(default_factory=list)
    claimed_derivation_count: int = 0
    observed_at: float = 0.0
    derived_at: float = 0.0


def compute_depth(entry: MemoryEntry, store: dict[str, MemoryEntry]) -> int:
    """Depth = hops from a direct observation. Depth 0 only legal for direct_observation."""
    if not entry.parent_ids:
        return 0
    return 1 + max(compute_depth(store[p], store) for p in entry.parent_ids if p in store)


def validate_provenance(entry: MemoryEntry, store: dict[str, MemoryEntry]) -> None:
    depth = compute_depth(entry, store)

    if depth == 0 and entry.source_kind != "direct_observation":
        raise ProvenanceViolation(
            f"depth-0 entry {entry.entry_id} claims source_kind={entry.source_kind!r}; "
            "only direct_observation may have no parents"
        )

    if depth < entry.claimed_derivation_count:
        raise ProvenanceViolation(
            f"entry {entry.entry_id} claims {entry.claimed_derivation_count} derivations "
            f"but recorded depth is {depth}; chain is broken"
        )

    for pid in entry.parent_ids:
        parent = store.get(pid)
        if parent is None:
            raise ProvenanceViolation(
                f"entry {entry.entry_id} references missing parent {pid}"
            )
        if entry.derived_at < parent.observed_at:
            raise ProvenanceViolation(
                f"timestamp inversion: {entry.entry_id} derived before parent {pid} observed"
            )


def admit(entry: MemoryEntry, store: dict[str, MemoryEntry]) -> bool:
    try:
        validate_provenance(entry, store)
        return True
    except ProvenanceViolation:
        return False  # quarantine; do not serve to agent
```