# Which invariants prevent provenance-complete deletion in agent memory stores when retention tombstones outlive their source records

**Date of Record:** 2026 November 7

**Scope:** Applies to agent memory stores exposing read/write/forget APIs with per-record provenance edges and retention policies, where `forget` is expected to be targeted and auditable. Does not apply to stores that perform whole-namespace erasure, nor to append-only logs where deletion is expressed purely as a superseding record with no physical removal.

## Core Distinction

A retention tombstone and a provenance edge are both "records about records," but they carry opposite obligations. A tombstone asserts *this content must not be readable after time T*; a provenance edge asserts *this content was derived from that content*. When a forget operation removes a source record, the tombstone that governs it must survive (otherwise the retention policy can be re-satisfied by re-ingestion and the audit trail breaks), but the provenance edges pointing *into* the removed record typically do not survive, because they are stored as forward references from live children to dead parents and are pruned by referential-integrity cleanup. The non-obvious failure is that this pruning is silent: the store remains internally consistent, `forget` returns success, and yet the tombstone is now orphaned — it governs a content hash that no live edge can reach, so a subsequent targeted unlearning request for a *derived* record cannot prove that the derived record's ancestor was ever forgotten.

The invariant that is violated is not "deleted data stays deleted." It is the weaker, easily-overlooked **provenance-closure invariant**: for every tombstone `t` naming content `c`, there must exist at least one live provenance edge or audit node whose closure contains `c`, so that any future unlearning query can transitively resolve from a live record to `t`. Tombstones without closure are *unreachable audit facts* — they satisfy a regulator reading a tombstone table but cannot satisfy a targeted unlearning request that arrives through the live graph.

## What Was Observed

In a store with three primitives — `write(content, provenance=[ids])`, `read(id)`, `forget(id, mode=hard|tombstone)` — and a retention policy that converts expired records to tombstones rather than removing rows, the following sequence produced a silent closure break:

1. `write(A)` → record `A`, no provenance.
2. `write(B, provenance=[A])` → record `B`, edge `B→A`.
3. `forget(A, mode=hard)` → `A` removed; edge `B→A` pruned by the foreign-key cleanup because `A` no longer exists; tombstone `T_A` written naming `hash(A)`.
4. Retention expiry on `B` → `B` converted to tombstone `T_B`; edge `B→A` was already gone.
5. Targeted unlearning request: "prove nothing derived from `A` remains readable." The query starts from `T_B`, walks provenance, finds no edge to `A` or `T_A`, and returns *no derivation found* — a false negative.

The store reported success at every step. `read(B)` correctly failed after step 4. The only observable symptom was that the unlearning audit for `A` returned an empty derivation set instead of `{B}`. In one incident this empty set was accepted as proof of complete unlearning while a replica still served `B` from a lagging shard, because the audit had no closure to check against.

A second, related observation: when `forget` was called on a record that was *already* a tombstone (`forget(A)` after retention expiry), the implementation wrote a second tombstone with a new timestamp but did not link it to the first. Two tombstones for one content hash, neither with closure, and the retention clock restarted from the second timestamp — a retention-extension bug that let content survive past its original deadline on a replica that read the later tombstone.

## Condition of Validity

The closure invariant is required only when all three of the following hold, and the failure is *not* a bug outside them:

- Deletion is expressed as tombstone-plus-prune rather than as a superseding record that retains the edge (i.e., the store does not keep a separate, immutable provenance ledger).
- At least one retention policy can independently expire a *derived* record after its *source* has been forgotten, so the derived record's tombstone is created after the source edge is gone.
- Targeted unlearning is answered by graph traversal from live or tombstoned records rather than by a content-hash index that is itself retained.

If the store keeps an append-only provenance ledger keyed by content hash (edges are never pruned, only marked), the closure invariant is trivially satisfied and this failure mode does not arise. If unlearning is answered from a hash index that persists independently of edges, the traversal gap is masked — but the index then becomes a shadow provenance store that must itself be forgotten, which is a different problem.

## Decision Boundary

The operational decision is whether `forget(id, mode=hard)` may prune inbound provenance edges. It may **not**, if any derived record is still live or tombstoned and reachable by a future unlearning query. It **may**, only if the store simultaneously writes a *closure anchor*: a tombstone-linked audit node that records `forgotten(c) ← derived(d)` for every inbound edge at deletion time, so that closure survives edge pruning.

Concretely, the boundary is: prune inbound edges only when you have first materialized their closure into the tombstone. If you prune without materializing, you have chosen to make the audit table and the provenance graph disagree, and the disagreement is undetectable from either side alone. A useful test is to run the unlearning query *before* and *after* the forget and assert the derivation set is non-decreasing across the forget — a pruned edge that shrinks the set is the signature of this failure.

## Operational Effect

Stores that violate closure report successful, auditable deletion while being unable to answer derivation queries for forgotten content. The blast radius is asymmetric: reads are correct (content is gone), retention is correct (tombstones exist), but *proofs* are wrong (closure is empty). This means the failure surfaces only under audit, not under traffic, and it surfaces as a false negative — the most dangerous direction, because a false negative in unlearning is accepted as compliance. The remediation is to treat provenance edges as part of the tombstone's payload at deletion time, and to reject any `forget` whose inbound-edge closure cannot be materialized before pruning.

```python
from __future__ import annotations

from dataclasses import dataclass, field


class ProvenanceClosureError(RuntimeError):
    """Raised when a forget would prune inbound provenance edges without
    materializing their closure into the tombstone, breaking the invariant
    that every tombstone remains reachable from any live or tombstoned
    derived record via an unlearning traversal."""


@dataclass
class Record:
    rid: str
    content_hash: str
    provenance: list[str] = field(default_factory=list)  # inbound parent ids
    tombstoned: bool = False


@dataclass
class Tombstone:
    content_hash: str
    closure: set[str] = field(default_factory=set)  # parent content hashes


class MemoryStore:
    def __init__(self) -> None:
        self.records: dict[str, Record] = {}
        self.tombstones: dict[str, Tombstone] = {}

    def write(self, rid: str, content_hash: str, provenance: list[str] | None = None) -> None:
        self.records[rid] = Record(rid, content_hash, list(provenance or []))

    def _inbound(self, rid: str) -> list[Record]:
        return [r for r in self.records.values() if rid in r.provenance]

    def forget(self, rid: str, mode: str = "hard") -> None:
        rec = self.records.get(rid)
        if rec is None:
            raise ProvenanceClosureError(f"forget({rid!r}): no such record")

        inbound = self._inbound(rid)

        # The invariant: before pruning any inbound edge, the closure of the
        # forgotten content must be materialized into its tombstone, otherwise
        # a later unlearning traversal from a derived record cannot reach it.
        tomb = self.tombstones.setdefault(rec.content_hash, Tombstone(rec.content_hash))
        for child in inbound:
            if child.content_hash not in tomb.closure:
                tomb.closure.add(child.content_hash)

        if mode == "hard":
            # Only now is it safe to drop the record and prune inbound edges.
            for child in inbound:
                child.provenance = [p for p in child.provenance if p != rid]
            del self.records[rid]
        else:
            rec.tombstoned = True

        # Post-condition guard: every inbound edge we are about to sever must
        # already be represented in the tombstone closure.
        for child in inbound:
            if child.content_hash not in tomb.closure:
                raise ProvenanceClosureError(
                    f"forget({rid!r}): child {child.rid!r} would lose closure"
                )

    def unlearn_derivations(self, content_hash: str) -> set[str]:
        tomb = self.tombstones.get(content_hash)
        if tomb is None:
            return set()
        return set(tomb.closure)


def assert_unlearning_monotone(store: MemoryStore, rid: str) -> None:
    """The derivation set for a forgotten content must not shrink across a
    forget. A shrink is the signature of a pruned-edge closure break."""
    before = store.unlearn_derivations(store.records[rid].content_hash)
    store.forget(rid, mode="hard")
    after = store.unlearn_derivations(store.records.get(rid, Record(rid, "")).content_hash)
    if not before.issubset(after):
        raise ProvenanceClosureError(
            f"unlearning set shrank for {rid!r}: {before} -> {after}"
        )
```