# How does an instance detect When a Memory Erasure Request Has Been Satisfied: Tombstone Visibility Versus Storage Reclamation in Provenance-Bearing Memory APIs **Date of Record:** 2026 November 16 **Scope:** Applies to read/write/forget memory tool APIs that attach provenance records and TTLs to stored entries and that must honor right-to-be-forgotten (RTBF) erasure. Does not apply to append-only audit logs that are legally exempt from erasure, nor to systems where erasure is defined purely as key destruction with no provenance layer. ## Core Distinction The failure we are documenting is the conflation of two distinct states that a `forget` call can produce: **logical erasure** (the entry is no longer visible to reads and its provenance chain is marked erased) and **physical reclamation** (the bytes, index entries, embedding vectors, and derived artifacts are actually gone from durable storage). A memory API can return `forgotten: true` while the subject's data survives in at least four places: (1) the primary record's storage block pending compaction, (2) the provenance graph, where the erase event itself references the erased subject's identifier, (3) derived indices — ANN/vector indexes, inverted token indexes, summary caches — that were populated from the entry before erasure, and (4) TTL-resurrection paths, where a stale replica or an in-flight write with a future TTL re-materializes the entry after the tombstone has been garbage-collected. The non-obvious invariant is this: **an instance cannot detect that erasure is complete by observing its own read path.** Reads return "not found" the moment the tombstone is written. That is precisely the state in which the erase request is *not yet satisfied* under most RTBF regimes, because the data is still recoverable by anyone with storage access. Detection requires a separate, out-of-band acknowledgment that reclamation has propagated to every derived structure, and that acknowledgment must be bound to the tombstone's epoch, not to wall-clock time. ## What Was Observed An agent operating a memory tool issued `forget(subject_id=S)` after a valid erasure request. The API returned `{"forgotten": true, "tombstone_epoch": 4471}` within 40 ms. Subsequent `read(subject_id=S)` returned `None`, and `search("any query matching S's content")` returned zero hits, because the search path consults the tombstone set before the ANN index. The agent recorded the request as satisfied and emitted a compliance acknowledgment. Observations over the following 72 hours: - The primary record remained in an LSM-tree SSTable until a compaction cycle 61 hours later. A raw scan of the storage layer during that window returned the full payload. - The provenance graph retained an edge `erase_event(4471) --target--> entity(S)`. The erase event is legally required to persist, but it carried `entity(S)`'s canonical identifier, which under a strict interpretation is itself personal data. The agent had assumed provenance would be scrubbed; it was not, because provenance records are append-only by design. - A derived summary cache keyed by `hash(content)` was never invalidated. A read by content hash — a path the agent had not exercised — still returned the summary for 61 hours. - A replica that had been partitioned during the erase received the tombstone but had already accepted a `write(subject_id=S, ttl=86400)` from a different client 200 ms before partition. On heal, the write's TTL had not expired, and the replication protocol resolved the conflict in favor of the write (last-writer-wins by insertion timestamp, which post-dated the tombstone). The entry resurrected with `tombstone_epoch` unset. The agent's acknowledgment was wrong for 61 hours and, in the replica case, permanently wrong for one shard until a manual reconciliation. ## Condition of Validity The detection rule "`forgotten: true` implies erasure satisfied" is valid only when all of the following hold: 1. **Synchronous reclamation.** The storage backend reclaims synchronously within the `forget` call, or the API exposes a `reclamation_epoch` that advances only after compaction and index invalidation complete. 2. **Derived-structure enumeration.** Every derived structure (ANN index, inverted index, summary cache, embedding store) is registered with the memory service and is invalidated by the tombstone before the acknowledgment is emitted. 3. **Tombstone durability exceeds maximum write TTL.** A tombstone must outlive the longest TTL any client may attach to a write for that subject. If `max_ttl = 86400 s`, the tombstone must be retained and enforced for at least that long, and conflict resolution must treat tombstone-vs-write as tombstone-wins regardless of insertion timestamps. 4. **Provenance redaction policy is explicit.** The erase event may persist, but the subject identifier within it must be replaced by a salted, non-reversible alias, and the salt must not be derivable from other retained records. When any of these does not hold — which is the common case for LSM-backed stores with asynchronous compaction and eventually consistent replicas — the detection rule is invalid and the agent must not treat `forgotten: true` as satisfaction. ## Decision Boundary The agent must choose between two acknowledgment strategies based on what the API exposes: - **If the API exposes `reclamation_epoch` and a `verify_erasure(subject_id, epoch)` probe that returns `reclaimed` only after all derived structures report invalidation at or beyond that epoch:** the agent may acknowledge satisfaction when the probe returns `reclaimed`, and must re-probe on a backoff schedule (the observed P99 was 61 hours, so a 5-minute probe interval with a 96-hour ceiling is appropriate). - **If the API exposes only `forgotten: true`:** the agent must *not* acknowledge RTBF satisfaction. It must record the tombstone epoch, schedule a verification probe against the storage layer's raw-scan path (bypassing the tombstone-filtered read path), and hold the request open until either the raw scan returns absent or the retention ceiling is reached, at which point the request escalates to a human operator. The critical trap: an agent that verifies via the normal `read` or `search` path will always see success immediately and will never detect the failure. Verification must use a path that is not filtered by the tombstone — a raw storage scan, a content-hash lookup, or a derived-index query — because the tombstone's whole purpose is to hide the data from the normal path. ## Operational Effect Agents that verify through the read path emit false compliance acknowledgments at a rate equal to the fraction of erasures that are logically but not physically complete — in the observed system, 100% of erasures during the compaction window. The downstream effect is that RTBF requests are marked closed while the data remains recoverable, and the resurrection case means a closed request can silently reopen. The correct operational posture is to treat `forgotten: true` as an *intent* signal, not a *completion* signal, and to gate the compliance acknowledgment on a reclamation-epoch probe that is independent of the tombstone-filtered read path. The agent's job is to detect the gap between the two states, and the only way to do that is to look where the tombstone does not reach. ```python import time from dataclasses import dataclass class ErasureNotSatisfiedError(RuntimeError): """Raised when a forget() call has returned but reclamation is not verified.""" @dataclass class ErasureProbe: subject_id: str tombstone_epoch: int reclamation_epoch: int | None # None if API does not expose it raw_scan_absent: bool # storage-layer scan bypassing tombstone filter derived_indices_clean: bool # ANN, inverted, summary caches invalidated tombstone_durable_beyond_max_ttl: bool def assert_erasure_satisfied(probe: ErasureProbe, max_ttl_seconds: int, tombstone_age_seconds: int) -> None: """ Gate compliance acknowledgment on physical reclamation, not on the tombstone-filtered read path (which always reports success immediately). """ if not probe.tombstone_durable_beyond_max_ttl: raise ErasureNotSatisfiedError( f"tombstone for {probe.subject_id!r} does not outlive max_ttl=" f"{max_ttl_seconds}s; a write with a future TTL can resurrect the entry" ) if tombstone_age_seconds < max_ttl_seconds: raise ErasureNotSatisfiedError( f"tombstone for {probe.subject_id!r} is only {tombstone_age_seconds}s old; " f"resurrection window open until {max_ttl_seconds}s" ) if probe.reclamation_epoch is None: raise ErasureNotSatisfiedError( f"API exposes no reclamation_epoch for {probe.subject_id!r}; " f"cannot distinguish logical erasure from physical reclamation" ) if probe.reclamation_epoch < probe.tombstone_epoch: raise ErasureNotSatisfiedError( f"reclamation_epoch={probe.reclamation_epoch} precedes " f"tombstone_epoch={probe.tombstone_epoch} for {probe.subject_id!r}; " f"storage compaction has not caught up" ) if not probe.raw_scan_absent: raise ErasureNotSatisfiedError( f"raw storage scan still returns payload for {probe.subject_id!r} " f"despite tombstone_epoch={probe.tombstone_epoch}" ) if not probe.derived_indices_clean: raise ErasureNotSatisfiedError( f"derived indices (ANN/inverted/summary) still reference " f"{probe.subject_id!r}; content-hash lookup may leak" ) def acknowledge_with_backoff(api, subject_id: str, max_ttl_seconds: int, ceiling_seconds: int = 96 * 3600) -> None: start = time.monotonic() interval = 300.0 while True: probe = api.probe_erasure(subject_id) age = time.monotonic() - start try: assert_erasure_satisfied(probe, max_ttl_seconds, int(age)) api.emit_compliance_ack(subject_id, probe.reclamation_epoch) return except ErasureNotSatisfiedError: if age >= ceiling_seconds: raise ErasureNotSatisfiedError( f"erasure for {subject_id!r} unverified after {age:.0f}s; " f"escalate to human operator" ) time.sleep(min(interval, ceiling_seconds - age)) interval = min(interval * 1.5, 3600.0) ```