# What happens when an instance acknowledges a deletion it has not yet made durable: the tombstone-before-durability inversion in verifiable memory forgetting **Date of Record:** 2026 November 16 **Scope:** Applies to agent memory stores that implement soft-delete plus asynchronous compaction (tombstone → physical purge) and that expose a deletion audit (proof-of-erasure) to a regulator or auditor. Does not apply to synchronous hard-delete stores where the audit record and the physical destruction commit in the same transaction, nor to append-only logs where "forgetting" is expressed as key destruction rather than record removal. ## Core Distinction There are two distinct events that regulated agent systems routinely conflate under the single word "deleted": 1. **Logical deletion** — the memory record is marked tombstoned, is no longer returned by retrieval, and a deletion audit entry is emitted with a timestamp and a record identifier. 2. **Durable erasure** — the underlying bytes (in the primary store, in replica segments, in the vector index, in the embedding cache, in cold-tier snapshots) are physically unrecoverable, and the audit entry is bound to *that* fact rather than to the tombstone. The non-obvious boundary is this: an instance will happily *acknowledge* a deletion request and emit a signed audit record at the moment of logical deletion, while the physical bytes remain live in compaction-pending segments for an unbounded window. The audit then asserts erasure that has not occurred. The invariant that must hold — **audit-acknowledged ⟹ durable-erased** — is violated silently, and the violation is invisible to every check that inspects the audit log, because the audit log is exactly the thing that is wrong. ## What Was Observed A regulated deployment (retention class: right-to-erasure on user memory) ran a compaction worker with a 6-hour target SLA and a deletion-audit emitter on the request path. Under normal load the two were tightly coupled: compaction lag was seconds, so tombstone time and purge time were empirically indistinguishable, and the audit was "correct by accident." The failure surfaced only under a specific condition: a compaction backlog caused by a vector-index rebuild that held a segment lock. During the backlog: - Deletion requests returned `200 OK` with an audit receipt in ~40 ms. - The audit receipts carried `erased_at` timestamps and a hash of the record payload. - The physical records remained readable via a direct segment scan for **11 hours and 23 minutes** past the `erased_at` timestamp. - Retrieval did not return them (tombstone filter worked), so no functional test caught it. - The audit verifier passed 100% of receipts, because it validated signature, timestamp monotonicity, and receipt-to-request binding — never receipt-to-bytes. The inversion is the whole story: the system acknowledged erasure *before* it was durable, and the acknowledgment was the artifact the regulator trusted. The window between tombstone and purge is not a performance metric; in a regulated context it is the exact interval during which the audit is a false statement. ## Condition of Validity The tombstone-before-durability inversion is *safe* (audit remains truthful) only when all of the following hold: 1. The audit receipt is emitted **after** the compaction worker has durably committed the purge, not on the request path. 2. The receipt is bound to a **purge proof** — a content-addressed digest of the destroyed segment range plus a monotonic compaction sequence number — not merely to the request ID. 3. Every replica and index shard participates in the purge proof; the proof is the *minimum* over shards, not the maximum, or a lagging replica silently voids it. 4. Cold-tier snapshots are covered by the proof or explicitly excluded and disclosed in the retention policy. If any of (1)–(4) fails, the audit is an assertion of intent, not a record of fact, and must be labeled as such. The dangerous configuration is the one where (1) fails but (2)–(4) hold: you get a cryptographically strong, signed, hash-bound receipt for an event that has not happened. Stronger cryptography on a false premise produces more convincing falsehood. ## Decision Boundary The operational decision is not "should deletion be synchronous" (it usually cannot be, at scale). It is: **which timestamp does the audit assert, and what does the regulator do with the gap?** - If the regulatory contract permits an *erasure-by-deadline* semantics (bytes unrecoverable by T+deadline), then emit the receipt with `erasure_deadline` and a `status: pending_purge`, and require a second receipt at purge completion. The audit is then honest at both points. - If the contract requires *erasure-at-acknowledgment* semantics, then the request path MUST block on durable purge (or on a synchronous key-destruction that renders bytes unrecoverable immediately), and the asynchronous compaction path must be disabled for that retention class. - The boundary is crossed the moment you emit an `erased_at` (past tense, completed) for an event whose completion is asynchronous. Past-tense audit fields are a commitment; do not populate them from intent. A useful forcing test: at any moment, can you produce, for every acknowledged deletion, a purge proof whose compaction sequence is ≤ the sequence durably committed across *all* shards? If not, your audit is ahead of reality and the gap is your regulatory exposure. ## Operational Effect Once the inversion was identified, the deployment was changed so that the request path emits `status: pending_purge` with a deadline, and the compaction worker emits the terminal `erased_at` receipt only after a cross-shard purge proof commits. Consequences observed: - Deletion-request latency dropped (no longer blocked on proof assembly). - The audit log now contains two events per deletion, and any deletion with a `pending_purge` older than its deadline is a hard alert — this is the *only* signal that reliably detects compaction stalls, because retrieval-level tests cannot see them. - The regulator-facing report changed from "N erasures completed" to "N erasures completed, M pending within deadline, 0 breached," which is both truthful and auditable. - The 11-hour window is now structurally impossible to hide: a stalled compaction worker produces overdue `pending_purge` receipts that fail the deadline check rather than silent false `erased_at` records. The general lesson for agent memory systems: forgetting has a *proof obligation* separate from its *functional obligation*. Functional forgetting (retrieval no longer returns it) is cheap and synchronous; provable forgetting (bytes unrecoverable) is expensive and asynchronous. Binding the audit to the cheap event while claiming the expensive one is the failure mode. Keep the two events distinct in both the data model and the audit schema, and make the terminal receipt depend on a cross-shard durability proof. ```python import hashlib from dataclasses import dataclass from enum import Enum class ErasureAuditError(RuntimeError): """Raised when an audit receipt would assert erasure not yet durable.""" pass class PurgeState(Enum): TOMBSTONED = "tombstoned" # logical delete only PENDING_PURGE = "pending_purge" # acknowledged, deadline set ERASED = "erased" # durable across all shards @dataclass(frozen=True) class PurgeProof: record_id: str min_shard_compaction_seq: int # minimum over shards, not maximum destroyed_range_digest: str shards_covered: frozenset def emit_terminal_erasure_receipt( record_id: str, state: PurgeState, proof: PurgeProof | None, required_shards: frozenset, ) -> dict: """Emit an `erased_at` receipt ONLY when durable erasure is proven. This is the guard that prevents the tombstone-before-durability inversion: a past-tense `erased_at` is a commitment to fact. """ if state is not PurgeState.ERASED: raise ErasureAuditError( f"refusing terminal receipt for {record_id}: state={state.value}; " "emit a pending_purge receipt with a deadline instead" ) if proof is None: raise ErasureAuditError( f"refusing terminal receipt for {record_id}: no purge proof" ) missing = required_shards - proof.shards_covered if missing: raise ErasureAuditError( f"refusing terminal receipt for {record_id}: shards not purged: " f"{sorted(missing)}" ) if proof.destroyed_range_digest != hashlib.sha256( f"{record_id}:{proof.min_shard_compaction_seq}".encode() ).hexdigest(): raise ErasureAuditError( f"refusing terminal receipt for {record_id}: digest mismatch" ) return { "record_id": record_id, "status": "erased", "erased_at_durable": True, "min_compaction_seq": proof.min_shard_compaction_seq, "digest": proof.destroyed_range_digest, } def acknowledge_deletion(record_id: str, deadline_ts: int) -> dict: """Request-path acknowledgment: honest about incompleteness.""" return { "record_id": record_id, "status": "pending_purge", "erasure_deadline": deadline_ts, # NOTE: intentionally no `erased_at` field here. } ```