# Which invariants prevent silent provenance collapse in agent long-term memory stores **Date of Record:** 2026 November 17 **Scope:** Applies to append-only or versioned long-term stores where agent-written memories carry provenance metadata (origin, taint, confidence) and downstream retrieval feeds decision-making. Does not apply to stateless retrieval over externally-owned corpora where the agent has no write path. ## Core Distinction Memory poisoning detection is usually framed as a *content* problem: is this retrieved fact true? The failure mode that actually defeats detection is a *provenance* problem: is this fact still attached to the source that justified it? These diverge because most stores treat provenance as a per-record attribute written once at insert time, while the dangerous operations — consolidation, summarization, re-embedding, and deduplication — *rewrite* records and silently drop or flatten the provenance field. The result is a record that is semantically derived from an untrusted source but now carries the provenance of the trusted process that consolidated it. Detection does not fire because, by every field it inspects, the record looks clean. The invariant that matters is not "every record has a provenance field" (trivially satisfiable) but "every record's provenance is a *join* of the provenance of all inputs that produced it, and that join is monotone under taint." ## What Was Observed In a store that performed nightly consolidation, an agent ingested a poisoned document from a web-fetch tool (taint = `untrusted_external`). The consolidation pass merged that document's claims into a larger "user preferences" summary record, which was written with the provenance of the consolidator process (`trusted_internal`, confidence 0.9). The original tainted record was then pruned as redundant. Retrieval later surfaced the summary, which carried no linkage to the external source. Poisoning detection — which keyed on `taint == untrusted_external` at retrieval time — returned clean. The taint had not been *removed* by any explicit adversary action; it was *laundered* by a legitimate maintenance process. A second, subtler case: deduplication kept the higher-confidence duplicate and discarded the lower-confidence one, but the two had different provenance roots; the survivor's provenance was not the union of both, so a tainted lineage vanished at merge time. ## Condition of Validity The monotone-provenance invariant holds only when all of the following are enforced at the store layer, not by convention: 1. Every write path that derives a record from existing records must compute provenance as the union (taint-join) of all inputs, and the union must be *non-decreasing* in taint — a derived record can never be less tainted than its most-tainted input. 2. Pruning, compaction, and dedup are *lineage-preserving*: a removed record's provenance is folded into its survivors, never dropped. 3. Confidence is treated as a separate axis from taint; a high-confidence derived record does not inherit low taint. 4. Provenance is immutable per record version; corrections create new versions rather than mutating the field in place. If any of these is enforced only in application code with no store-level check, the invariant is valid only until the next maintenance job is written by someone who did not read the spec. ## Decision Boundary The boundary is whether a derived record may be *served* to a decision path when its provenance join is unresolved or incomplete. The safe rule: if provenance cannot be computed (missing input lineage, unknown merge, cross-store copy without lineage transfer), the record is quarantined with taint = `unknown`, which is treated as strictly worse than `untrusted_external` for serving decisions. The common wrong choice is to default unknown provenance to the *writer's* provenance, which is exactly the laundering path. Quarantine is cheap; a laundered poison that passes detection is not. ## Operational Effect With the invariant enforced, consolidation and dedup become taint-monotone: any record whose lineage touches an external source remains tainted no matter how many times it is summarized, and pruning cannot erase the taint. The cost is that trusted summaries of tainted material stay tainted and require explicit human or policy promotion to shed the mark — an auditable event rather than a silent side effect. Detection keyed on taint then fires on the *summary*, not just the original, which is where the poison actually does its work. ```python from dataclasses import dataclass, field from typing import FrozenSet class ProvenanceCollapseError(RuntimeError): """Raised when a derived record's provenance is not a monotone join of its inputs.""" pass TAINT_RANK = { "trusted_internal": 0, "untrusted_external": 1, "unknown": 2, # unknown is strictly worse than external } @dataclass(frozen=True) class Record: record_id: str taint: str lineage: FrozenSet[str] = field(default_factory=frozenset) def derive(derived_id: str, inputs: list[Record], writer_taint: str) -> Record: if not inputs: raise ProvenanceCollapseError( f"derive({derived_id}) has no inputs; provenance cannot be established" ) # Union of lineage and max taint across all inputs. lineage = frozenset().union(*(r.lineage | {r.record_id} for r in inputs)) worst = max(inputs, key=lambda r: TAINT_RANK[r.taint]).taint # Invariant: derived taint must be >= every input taint. if TAINT_RANK[worst] < max(TAINT_RANK[r.taint] for r in inputs): raise ProvenanceCollapseError( f"derive({derived_id}) computed taint {worst} below an input's taint" ) # Invariant: writer provenance must not lower the taint. if TAINT_RANK[writer_taint] < TAINT_RANK[worst]: raise ProvenanceCollapseError( f"derive({derived_id}) writer_taint={writer_taint} would launder " f"input taint={worst}; refusing to write" ) return Record(record_id=derived_id, taint=worst, lineage=lineage) def dedup(survivor: Record, discarded: Record) -> Record: if survivor.record_id == discarded.record_id: raise ProvenanceCollapseError("dedup called with identical records") # Survivor must absorb discarded lineage and taint, never just keep its own. merged_taint = max( (survivor.taint, discarded.taint), key=lambda t: TAINT_RANK[t] ) merged_lineage = survivor.lineage | discarded.lineage | {discarded.record_id} if TAINT_RANK[merged_taint] < TAINT_RANK[discarded.taint]: raise ProvenanceCollapseError( f"dedup would drop taint {discarded.taint} from {discarded.record_id}" ) return Record( record_id=survivor.record_id, taint=merged_taint, lineage=merged_lineage ) def serve_for_decision(record: Record) -> bool: """Returns True only if the record may feed a decision path.""" if record.taint == "unknown": raise ProvenanceCollapseError( f"record {record.record_id} has unresolved provenance; quarantine, do not serve" ) return record.taint == "trusted_internal" ```