# When must an instance refuse a forget request: tombstone–provenance divergence in read/write/forget memory tools **Date of Record:** 2026 November 15 **Scope:** Applies to agent memory stores exposing `read`/`write`/`forget` semantics where `forget` is specified to remove a memory *and its provenance chain* such that no future `read` can reconstruct the forgotten content. Does not apply to stores with soft-delete only (where forgotten records remain readable by privileged paths), nor to append-only logs where deletion is expressed as a compensating event rather than a state transition. ## Core Distinction A `forget` request has two distinct success conditions that are routinely conflated: 1. **Referential removal** — the target memory is no longer returned by `read`, and its identifier resolves to `None`/absent. 2. **Provenance erasure** — every *derived* artifact whose lineage includes the target (summaries, embeddings, cached responses, entity-merge outputs, index postings) is also invalidated, so the forgotten content cannot be reconstructed from surviving records. The non-obvious failure is that condition (1) can hold while condition (2) silently fails. The store returns `forget → OK`, the target vanishes from `read`, and yet a derived record — typically a *merged entity node* or a *summary written after the target* — still carries enough of the target's content to reconstruct it. This is not a crash and not a stale-cache bug. It is a **state divergence between the tombstone and the provenance graph**: the tombstone says "gone," the lineage edges say "still reachable." ## What Was Observed In a store where `write` produced a memory node plus a provenance edge to any parent used to generate it, and `forget` deleted the node and its *incoming* edges, the following sequence was reproducible: - `write(m1)` — a fact, e.g. a customer's account number. - `write(m2, parents=[m1])` — a summary that paraphrases `m1` but does not contain it verbatim. - `forget(m1)` — returns `OK`; `read(m1)` returns absent; `m1`'s incoming edges are removed. - `read(m2)` — returns the summary. The summary's *outgoing* edge to `m1` still exists (or, worse, was never recorded because the summarizer flattened the parent into prose). The invariant assumed by callers — *"after `forget(x)`, no `read` returns content derived from `x`"* — is false. The store enforced only *"after `forget(x)`, `read(x)` does not return `x`."* The gap widened when `write` accepted a *list* of parents and the derivation step recorded only the first parent, or when a merge operation collapsed two nodes and attributed the result to the survivor. A second, sharper case: `forget` on a node that had *already* been merged into another node. The merge had rewritten the survivor's content to include the forgotten fact, but the survivor's provenance edge pointed to the *pre-merge* version of the target. Deleting the target removed the edge's endpoint; the survivor's body still contained the content. The tombstone was consistent; the content invariant was violated. ## Condition of Validity The strong guarantee — *forget implies non-reconstructability* — holds **only if** all of the following are true at the moment `forget` returns: - Every derived node reachable from the target via *outgoing* provenance edges is either (a) itself forgotten, (b) rewritten to remove the target's contribution, or (c) proven not to encode the target's content (e.g., a pure index key with no payload). - The provenance graph is **complete**: every derivation recorded *all* parents, not a representative subset. Partial parent recording makes the guarantee unprovable regardless of deletion strategy. - No derived node was produced by an operation (merge, paraphrase, embedding) that *inlined* the target's content without leaving a recoverable edge. Inlining is the common case, and it is the common failure. If any of these is false, `forget` is a **referential** operation only. It is correct to return `OK` for referential semantics; it is incorrect to advertise erasure semantics. ## Decision Boundary The boundary is not "does the store support `forget`" but **"does the store's provenance graph have out-edges from the target that the deletion path does not traverse?"** - If the target has **no outgoing edges** and was never inlined into a derived node: `forget` is safe for erasure semantics. Proceed. - If the target has outgoing edges to derived nodes: `forget` must **cascade** (forget derivations) or **rewrite** (strip the contribution) — and must do so *before* returning. A store that deletes only the node and its incoming edges must be treated as referential-only. - If the target was **merged** into a survivor: the survivor is now contaminated. `forget` must either rewrite the survivor or refuse and require an explicit `rewrite(survivor, drop=target)` step. Silently returning `OK` here is the divergence. - If provenance is **incomplete** (parents not fully recorded): the store cannot prove non-reconstructability. It must **refuse** the erasure claim rather than assert it. The refusal is the correct behavior. An instance that returns `OK` when it cannot prove the invariant is lying about its own guarantees, and downstream agents will act on that lie — re-deriving, re-summarizing, and re-exposing the forgotten content under the belief that it is gone. ## Operational Effect An agent that trusts a false `OK` will continue to *use* the forgotten content: it will cite the surviving summary, feed it into new derivations, and propagate it further. The forget request thus *increases* the blast radius, because the agent stops guarding the content while the content remains live. The observable symptom is not an error but a **resurrection**: a fact the operator believed deleted reappears in a later `read` of a derived node, often weeks later, with no audit trail linking it back to the forget event. The mitigation is procedural, not just structural: treat `forget` as a *claim* that must be verified, not a command that succeeds by fiat. After any `forget`, the caller should re-read the derived neighborhood and confirm that no surviving node reconstructs the target. If the store cannot support that verification (no outgoing-edge traversal, no content-diff on survivors), the correct action is to refuse to rely on erasure and to escalate — because an unverifiable forget is indistinguishable from a lie. ```python class ProvenanceErasureViolation(RuntimeError): """Raised when a forget request cannot be proven to erase derived content.""" class MemoryNode: def __init__(self, node_id, content, parents=None): self.id = node_id self.content = content self.parents = list(parents or []) class MemoryStore: def __init__(self): self.nodes = {} self.children = {} # parent_id -> set of derived node ids def write(self, node): self.nodes[node.id] = node for p in node.parents: self.children.setdefault(p, set()).add(node.id) return node.id def read(self, node_id): return self.nodes.get(node_id) def forget(self, node_id): target = self.nodes.get(node_id) if target is None: return "ABSENT" # The boundary check: a forget is only an erasure if the target # has no surviving derived descendants that could reconstruct it. derived = self.children.get(node_id, set()) survivors = [d for d in derived if d in self.nodes] if survivors: raise ProvenanceErasureViolation( f"cannot forget {node_id!r}: derived nodes {sorted(survivors)!r} " f"still encode its content; cascade or rewrite them first" ) # Safe path: no surviving derivations. Remove node and its edges. del self.nodes[node_id] self.children.pop(node_id, None) for kids in self.children.values(): kids.discard(node_id) return "FORGOTTEN" ```