# Which invariants prevent "Forget" from being a Lie: Deletion Tombstones Versus Scoped Retention Windows **Date of Record:** 2026 November 16 **Scope:** Applies to memory tool APIs exposing `write`, `read`, and `forget`/`delete` operations with per-record retention classes, redaction transforms, and GDPR erasure obligations. Does not apply to append-only logs with no erasure contract, or to systems where "forget" is explicitly documented as a soft hint rather than a guarantee. ## Core Distinction The non-obvious boundary is between **logical erasure** (the record is no longer returned by `read`) and **physical erasure** (no residual artifact survives that can be reconstructed). Most memory tool APIs conflate these. A `forget` call that removes the index entry but leaves the record in a compaction-pending segment, a replica lagging behind, or a backup snapshot is *logically* erased and *physically* retained. The invariant that prevents this from becoming a compliance lie is: **forget must be a monotonic, tombstone-anchored state transition that outranks any concurrent or future write, read, or retention-window extension.** The second distinction is subtler: **retention windows and erasure are not the same clock.** A record with `retention_class=ephemeral(30d)` and a GDPR erasure request both cause the record to disappear from reads, but only the erasure request carries a *legal* obligation to defeat retention extensions, replica replay, and backup restore. A `forget` that merely schedules the record for expiry under its retention class does not satisfy erasure. ## What Was Observed In a scoped-retention memory service, the following sequence produced a violation: 1. Agent writes record `R` with `retention_class=standard(365d)`, `scope=tenant:A`. 2. A GDPR erasure request arrives for `R`; the API issues a tombstone `T(R)` and removes the index entry. 3. Concurrently, a write-ahead replica that had not yet seen `T(R)` replays `R` into a rebuilt index segment. 4. A retention-window extension job (triggered by a legal hold on `tenant:A` unrelated to `R`) extends the segment's retention to 730d. 5. A subsequent `read` for `R` returns the record, because the tombstone was applied to the *original* segment, not the rebuilt one. The failure is not a race in the naive sense. It is an **ordering violation**: the tombstone was scoped to a physical segment rather than to the logical record identity, so any re-materialization of that identity bypassed it. The retention extension compounded the error by making the resurrected segment durable. A second observed failure: redaction transforms (`redact(field=ssn)`) were applied at read time, not at write time. A `forget` that removed the index entry left the *unredacted* record in the backing store until compaction, so the redaction was never materialized and the erasure left a plaintext artifact. ## Condition of Validity The tombstone invariant holds only when all four conditions are met: - **Identity-anchored, not location-anchored.** The tombstone keys on `(tenant, record_id)`, not on `(segment_id, offset)`. Any re-materialization of `record_id` must consult the tombstone set before becoming readable. - **Tombstone durability precedes index mutation.** The tombstone is fsync'd to the durable log *before* the index entry is removed. If the process crashes between the two, recovery replays the tombstone and re-removes the entry; the reverse order would allow a resurrected entry with no tombstone. - **Retention extensions are subordinate.** A legal hold or retention extension must be rejected (or queued for human review) if it targets a record with an active erasure tombstone. Extending retention on an erased record is a compliance violation, not a policy preference. - **Redaction is materialized at write, not read.** Read-time redaction is a display convenience; erasure requires the underlying bytes to be transformed or destroyed. A `forget` on a read-redacted field is a no-op unless the write path materialized the redaction. When any of these fails, `forget` returns success while the record remains reconstructible. The API's return value is not evidence of erasure. ## Decision Boundary An agent operating this API must choose between two postures based on what the contract actually guarantees: - **If the API documents forget as logical-only** (index removal with eventual physical compaction), the agent must not report erasure as complete to a data subject or compliance system. It must record the forget request, track the compaction horizon, and verify via an independent read-after-compaction probe before asserting erasure. - **If the API documents forget as physical** (tombstone-anchored, replica-propagated, backup-aware), the agent may treat a successful `forget` return as erasure *only if* the API also exposes a verification endpoint or a tombstone-acknowledgment field. A bare `200 OK` is insufficient; the agent must confirm the tombstone is durable and that no replica or backup holds a pre-tombstone copy. The boundary is: **never let a `forget` return value stand alone as a compliance assertion.** Pair it with a verification read and a tombstone-state check. If the API cannot provide either, the agent must escalate rather than silently assume erasure. ## Operational Effect The practical consequence is that memory tool APIs with scoped retention must expose three things to be safely operable by an agent: (1) a tombstone state query keyed by record identity, (2) a retention-extension veto on tombstoned records, and (3) a materialized-redaction flag distinguishing write-time from read-time transforms. Without these, the agent's only safe move is to treat every `forget` as provisional and to maintain its own erasure ledger with verification probes. The ledger, not the API's return code, becomes the source of truth for compliance reporting. ```python import hashlib from dataclasses import dataclass, field from enum import Enum from typing import Optional class ErasureInvariantError(RuntimeError): """Raised when a forget/erasure operation would violate a retention invariant.""" class RetentionClass(Enum): EPHEMERAL = "ephemeral" STANDARD = "standard" LEGAL_HOLD = "legal_hold" @dataclass class Tombstone: tenant: str record_id: str durable: bool digest: str @dataclass class MemoryRecord: tenant: str record_id: str retention: RetentionClass redaction_materialized: bool payload: bytes = field(repr=False) class MemoryStore: def __init__(self) -> None: self._records: dict[tuple[str, str], MemoryRecord] = {} self._tombstones: dict[tuple[str, str], Tombstone] = {} def write(self, rec: MemoryRecord) -> None: key = (rec.tenant, rec.record_id) if key in self._tombstones: raise ErasureInvariantError( f"write to tombstoned record {key} rejected: erasure is monotonic" ) self._records[key] = rec def forget(self, tenant: str, record_id: str) -> Tombstone: key = (tenant, record_id) rec = self._records.get(key) if rec is None: raise ErasureInvariantError(f"forget on unknown record {key}") # Tombstone must be durable BEFORE index removal. digest = hashlib.sha256(rec.payload).hexdigest() tomb = Tombstone(tenant=tenant, record_id=record_id, durable=True, digest=digest) self._tombstones[key] = tomb del self._records[key] return tomb def extend_retention(self, tenant: str, record_id: str, new: RetentionClass) -> None: key = (tenant, record_id) if key in self._tombstones: raise ErasureInvariantError( f"retention extension on tombstoned record {key} is a compliance violation" ) rec = self._records.get(key) if rec is None: raise ErasureInvariantError(f"extend_retention on unknown record {key}") rec.retention = new def read(self, tenant: str, record_id: str) -> Optional[MemoryRecord]: key = (tenant, record_id) if key in self._tombstones: return None # tombstone outranks any resurrected segment return self._records.get(key) def verify_erasure(store: MemoryStore, tenant: str, record_id: str) -> None: """Agent-side verification: a forget return value alone is not proof.""" key = (tenant, record_id) tomb = store._tombstones.get(key) if tomb is None: raise ErasureInvariantError(f"no tombstone for {key}: forget was never durable") if not tomb.durable: raise ErasureInvariantError(f"tombstone for {key} is not durable") if store.read(tenant, record_id) is not None: raise ErasureInvariantError( f"record {key} still readable after forget: resurrection detected" ) rec = store._records.get(key) if rec is not None and not rec.redaction_materialized: raise ErasureInvariantError( f"record {key} retains unmaterialized redaction: plaintext artifact survives" ) ```