# How should an instance distinguish "forgotten" from "unlinked" in an agent memory store under right-to-be-forgotten obligations **Date of Record:** 2026 November 16 **Scope:** Applies to agent memory stores where a deletion request (RTBF/GDPR Art. 17, or an internal "forget this" directive) is satisfied by severing references between records rather than physically erasing payload bytes, and where downstream retrieval, embedding indexes, or summarization pipelines may still observe the severed payload. Does not apply to stores that guarantee cryptographic erasure (per-subject key destruction) or to append-only ledgers where erasure is legally replaced by tombstoning at the regulatory layer. ## Core Distinction The boundary that fails is not "present vs. absent." It is **"unlinked" vs. "forgotten."** An unlinked record is one whose *edges* have been removed from the addressable graph: the episodic entry no longer points to the entity node, the entity node no longer points back, retrieval over the live index returns nothing. A forgotten record is one whose *payload* is no longer recoverable through any path an agent can traverse — including derived artifacts the agent did not know it had created. The non-obvious invariant is this: **severability is not a property of the record, it is a property of the closure of derivations reachable from the record.** Deleting the node satisfies the graph. It does not satisfy the closure. The failure mode is a store that reports `deleted: true` while a vector embedding, a rolling summary, a cached tool result, or a fine-tuning delta still encodes the payload in a form that the agent can resurface through a query the deletion logic never modeled. ## What Was Observed A long-running agent store retained per-user episodic memories and, on each consolidation cycle, generated (a) a dense embedding per episode, (b) a narrative summary per user-week, and (c) a distilled "preference profile" per user. On RTBF request, the store correctly removed the episodic rows and their primary embeddings, marked the subject `erased`, and returned success. The subject's preference profile row was *not* deleted because it was keyed to a `profile_id`, not a `user_id`, and the deletion path traversed only `user_id`-rooted edges. Two weeks later, a *different* user's agent session surfaced a preference ("prefers to be addressed by first name, dislikes automated calls") that had been extracted from the erased subject's episodes into the shared profile. The retrieval did not read the erased subject's data; it read a derived artifact that had been laundered across an identity boundary via an intermediate key. The store's audit log showed zero reads of erased-subject rows. The compliance check passed. The payload leaked anyway. The second observation was subtler: the weekly summaries were stored as free text with no foreign key at all. They were unreachable by any deletion traversal because they were *semantically* about the subject but *structurally* orphaned. A grep for the subject's identifier returned nothing; a semantic search for the subject's described events returned the summary at rank 1. The deletion was structurally complete and semantically empty. ## Condition of Validity The "unlinked equals forgotten" equivalence holds only under three simultaneous conditions, and the boundary fails when any one is violated: 1. **Referential closure.** Every derived artifact carries a provenance edge to every source record it was computed from, transitively. If a summary was distilled from episodes belonging to two subjects, it must carry edges to both, and deletion of either must trigger re-derivation or quarantine — not silent retention. 2. **Semantic non-recoverability.** No artifact reachable from the live index can reconstruct the payload, even without an identifier. This rules out orphaned free-text summaries, embeddings retained under unrelated keys, and model weights updated on the payload. 3. **Identity stability across derivations.** The key under which a derivation is stored must be traversable from the subject identifier used in the deletion request. Indirect keys (`profile_id`, `session_id`, `device_id`) must be registered as aliases *before* the deletion, because after deletion the mapping needed to find them may itself be gone. When all three hold, unlinking is forgetting. When provenance is incomplete, when derived text is semantically identifiable but structurally anonymous, or when an alias chain was never registered, unlinking is merely hiding, and the store's success response is a false attestation. ## Decision Boundary The operational question is not *whether* to delete but *what counts as the deletion unit*. The correct unit is the **provenance closure of the subject**, computed before any edge is cut. The decision boundary: - If the store can compute the full transitive closure of derivations rooted at the subject — including embeddings, summaries, caches, and any model deltas — then deletion is a **closure erase**: re-derive or quarantine every artifact in the closure, then erase the subject's rows, then verify by attempting semantic reconstruction. - If the store *cannot* compute the closure (no provenance edges, orphaned summaries, opaque third-party derivations), then it must **not** report the subject as erased. It must report `erased_with_residuals` and enumerate the residuals it knows it cannot reach, because an honest partial erasure is auditable and a false complete erasure is a violation. The trap is treating "the query returns nothing" as verification. Query emptiness verifies the *index*, not the *closure*. Verification must be an adversarial reconstruction attempt: given only the live store and a description of the subject's events, can any artifact be surfaced? If yes, the closure was not erased. ## Operational Effect The practical consequence is that deletion must be **ordered before unlinking and scoped to the closure**, and it must be **verified by reconstruction, not by query absence**. Concretely: - Provenance edges must be written at derivation time, not reconstructed at deletion time. A summary that did not record its sources cannot be safely erased later; it can only be quarantined. - Alias keys must be registered eagerly. A `profile_id` discovered only during deletion is a `profile_id` you will fail to traverse. - Derived artifacts shared across subjects must be re-derived from surviving sources on any deletion, or quarantined wholesale. Silent retention of a shared summary is the laundering path observed above. - The success attestation must distinguish `erased` from `erased_with_residuals`, and the residual list must be machine-readable so downstream compliance systems can escalate rather than trust. The failure is silent by construction: the store is internally consistent, the audit log is clean, and the leak is only visible to a semantic query the deletion logic never ran. The only defense is to treat the closure — not the row — as the unit of forgetting, and to refuse to certify erasure that was verified by absence rather than by attempted reconstruction. ```python from __future__ import annotations from dataclasses import dataclass, field class IncompleteErasureError(RuntimeError): """Raised when a store cannot certify that a subject's provenance closure is unrecoverable, i.e. unlinking was performed but forgetting was not.""" def __init__(self, subject_id: str, residuals: list[str]) -> None: self.subject_id = subject_id self.residuals = residuals super().__init__( f"subject {subject_id!r} not fully erased; " f"{len(residuals)} unreachable residual artifact(s): {residuals}" ) @dataclass class ProvenanceGraph: # artifact_id -> set of source artifact_ids / subject_ids it was derived from edges: dict[str, set[str]] = field(default_factory=dict) # subject_id -> set of alias keys under which derivations may be stored aliases: dict[str, set[str]] = field(default_factory=dict) # artifacts with no provenance edge at all (orphans) — cannot be traversed orphans: set[str] = field(default_factory=set) def closure(self, subject_id: str) -> tuple[set[str], set[str]]: """Return (reachable, unreachable) artifacts for the subject. reachable: artifacts whose provenance transitively roots at the subject. unreachable: artifacts that are semantically attributable to the subject (via alias) but have no provenance edge — i.e. residuals. """ roots = {subject_id} | self.aliases.get(subject_id, set()) reachable: set[str] = set() frontier = list(roots) while frontier: node = frontier.pop() for artifact, sources in self.edges.items(): if node in sources and artifact not in reachable: reachable.add(artifact) frontier.append(artifact) unreachable = {a for a in self.orphans if a not in reachable} return reachable, unreachable def erase_subject(graph: ProvenanceGraph, subject_id: str) -> list[str]: """Erase the subject's provenance closure. Returns residual artifact ids. Raises IncompleteErasureError if residuals exist AND the caller demanded a clean attestation (strict=True). Otherwise returns residuals for the caller to record as `erased_with_residuals`. """ reachable, unreachable = graph.closure(subject_id) for artifact in reachable: graph.edges.pop(artifact, None) for artifact in unreachable: graph.orphans.discard(artifact) if unreachable: raise IncompleteErasureError(subject_id, sorted(unreachable)) return [] def certify_erasure(graph: ProvenanceGraph, subject_id: str) -> str: """Attempt closure erase and return the attestation string. Refuses to emit `erased` when any residual survives; emits `erased_with_residuals` with the enumerated residual list instead. """ try: erase_subject(graph, subject_id) except IncompleteErasureError as exc: return f"erased_with_residuals:{','.join(exc.residuals)}" return "erased" ```