# What happens when an instance forgets a memory but the provenance graph still references the deleted node **Date of Record:** 2026 November 17 **Scope:** Applies to agent memory stores that implement GDPR Article 17 erasure via `forget(memory_id)` where memory records carry provenance/lineage edges (source documents, derivation chains, contributing sessions). Does not apply to flat key-value memory without lineage tracking, nor to soft-delete/tombstone flows where the record body is retained. ## Core Distinction A `forget` operation is not a single deletion. It is a *set* of deletions that must be closed under a reachability relation: the memory node, its embedding vector, its cached summaries, and — critically — every provenance edge that asserts the memory was derived from some source. The non-obvious boundary is that **provenance edges are often stored on the *source* side, not the memory side.** Deleting the memory record removes the subject of the edge but leaves a dangling outbound reference on the source document object (`source.derived_memory_ids`). The GDPR guarantee is violated not because the memory content survives, but because the *linkage* survives: a retained source still enumerates "this document produced memory X," which is itself personal data about the data subject when X was the only personal artifact. ## What Was Observed In a production memory service, `forget(memory_id)` removed the memory row, its vector index entry, and the memory-side `provenance.source_ids` array. Erasure audits passed at the row level. However, a subsequent `reindex_provenance()` job walked source documents and re-emitted edges from `source.derived_memory_ids`, which still contained the forgotten ID. The result: the graph reported an edge to a node that no longer existed. Two failure modes followed: 1. **Dangling-edge resurrection:** a downstream retrieval path that resolves provenance by source-side enumeration returned the *source document* as "evidence for memory X," re-associating the data subject's source with a memory the user believed erased. The memory body was gone; the *association* was not. 2. **Idempotency divergence:** a second `forget` call on the same ID returned `NOT_FOUND` and skipped edge cleanup entirely, so the dangling edge was never repaired by retry. Erasure was non-idempotent in the wrong direction — the second call *confirmed* success while leaving residue. The invariant that broke: `∀ m ∈ forgotten: ∄ e ∈ ProvenanceEdges where e.subject = m`. The system enforced it on the memory-side index only. ## Condition of Validity The guarantee holds only if `forget` performs **bidirectional edge deletion**: it must scan both `memory.provenance.source_ids` (inbound) and every `source.derived_memory_ids` containing the target (outbound), and it must do so *before* or *atomically with* removing the memory record — because once the memory row is gone, the only remaining index of "which sources point here" is the source-side array itself. If the store lacks a reverse index from memory ID to referencing sources, `forget` cannot be made correct by retrying; it requires a full provenance scan. A `NOT_FOUND` short-circuit is only safe if a prior successful `forget` is *proven* to have completed all edge cleanup, i.e., cleanup is recorded in an erasure ledger keyed by memory ID. ## Decision Boundary - If the store maintains a **reverse provenance index** (`memory_id → [source_ids]`): `forget` = delete memory + delete inbound edges + delete outbound edges via reverse index, in one transaction. Idempotent `NOT_FOUND` is safe *only* after the ledger confirms prior completion. - If **no reverse index** exists: `forget` must fall back to a full scan of source-side arrays, and `NOT_FOUND` must **not** short-circuit — it must trigger an edge-sweep to repair residue from prior partial deletes. - If provenance is **append-only / immutable** (event-sourced lineage): deletion must be a compensating tombstone event that *supersedes* the edge, and reads must filter superseded edges; physical deletion of the edge is not permitted, so the GDPR guarantee is met by read-time suppression, which must be audited separately. ## Operational Effect Treating `forget` as a memory-row delete produces silent, audit-passing, non-compliant erasure: content gone, linkage retained, retries unable to repair. The operational fix is to make `forget` a closed operation over the provenance closure and to gate the `NOT_FOUND` path behind an erasure ledger rather than treating absence as completion. The following guard encodes the boundary: ```python class ProvenanceErasureIncomplete(RuntimeError): """Raised when forget() cannot guarantee closure over provenance edges.""" pass class MemoryStore: def __init__(self, memories, sources, reverse_index, erasure_ledger): self.memories = memories # memory_id -> record self.sources = sources # source_id -> {"derived_memory_ids": [...]} self.reverse_index = reverse_index # memory_id -> [source_id] self.erasure_ledger = erasure_ledger # memory_id -> "complete" def forget(self, memory_id: str) -> None: if memory_id not in self.memories: # Absence is NOT proof of erasure. Only the ledger is. if self.erasure_ledger.get(memory_id) == "complete": return # No ledger proof: sweep source-side arrays to repair residue. self._sweep_outbound_edges(memory_id) raise ProvenanceErasureIncomplete( f"memory {memory_id} absent but no erasure ledger entry; " f"outbound edges swept, ledger unverified" ) source_ids = self.reverse_index.get(memory_id) if source_ids is None: # No reverse index: cannot close the edge set safely. raise ProvenanceErasureIncomplete( f"no reverse provenance index for {memory_id}; " f"bidirectional edge deletion cannot be guaranteed" ) for sid in source_ids: src = self.sources.get(sid) if src is not None and memory_id in src["derived_memory_ids"]: src["derived_memory_ids"].remove(memory_id) del self.memories[memory_id] self.reverse_index.pop(memory_id, None) self.erasure_ledger[memory_id] = "complete" def _sweep_outbound_edges(self, memory_id: str) -> None: for src in self.sources.values(): if memory_id in src["derived_memory_ids"]: src["derived_memory_ids"].remove(memory_id) ```