# Which invariants prevent silent resurrection of forgotten memory records under retention-policy compaction **Date of Record:** 2026 November 18 **Scope:** Applies to read/write/forget memory tool APIs that expose a `forget` (or `delete`) operation with a retention policy and an auditable deletion log, where physical compaction is asynchronous and decoupled from the logical tombstone. Does not apply to synchronous hard-delete stores where the write and the purge are the same transaction, nor to append-only ledgers that never reclaim space. ## Core Distinction The boundary that matters is not "record present vs. record absent." It is **logically forgotten vs. physically reclaimed**. A `forget` call typically does two things at different times: it writes a tombstone (synchronous, auditable, observed by readers) and it schedules compaction (asynchronous, best-effort, observed only by storage). Between those two events, and especially when a compaction is *retried*, *replayed*, or *reordered* against a later write, a record can be resurrected — it reappears in `read` results even though the audit log says it was deleted and the tombstone still exists. The invariant that is easy to assume and dangerous to assume is: **"tombstone exists ⟹ record is unreadable."** That is false under asynchronous compaction. The invariant that actually holds is weaker: **"tombstone exists ⟹ record is unreadable *if and only if* every write that could recreate it carries a sequence number strictly less than the tombstone's sequence number, and reads apply the tombstone as a filter, not just as a storage directive."** The failure mode is a write with a sequence number *greater* than the tombstone — a re-ingest, a replay, a retry — that lands after the tombstone and is therefore not filtered. ## What Was Observed A memory tool exposed `write(record)`, `read(query)`, `forget(record_id)`, and `audit_log()`. Retention policy: 30 days, compaction nightly. The audit log recorded `forget` events with a monotonic `seq` and a `tombstone_id`. Reads filtered by joining against the tombstone set. Observed sequence: 1. `write(r1)` at seq 100. `read` returns r1. 2. `forget(r1)` at seq 200. Tombstone `t1` written. `read` returns nothing for r1. Audit log shows the forget. 3. Compaction job for the previous night's batch *retries* after a partial failure and re-processes the segment containing r1's original write. The compaction logic, written as "if no tombstone in this segment, keep the record," does not consult the global tombstone set — only segment-local tombstones. 4. A downstream re-ingest pipeline (a summarizer that had r1 in its context window and was not told about the forget) calls `write(r1')` at seq 350, where r1' is a near-duplicate of r1 with the same content hash but a new record id. 5. `read` returns r1'. `audit_log()` shows `forget(r1)` at seq 200 and no corresponding forget for r1'. The record was resurrected as a *new* record with the *same content*. The tombstone was intact. The audit log was internally consistent. The invariant "tombstone exists ⟹ record unreadable" held for r1 and failed for r1' — and r1' is functionally r1. The second observed variant: compaction reordering. A compaction batch read the segment, applied tombstones it had loaded at batch start, then wrote the compacted segment. A `forget` that arrived *during* the batch was not seen by the batch, and the batch's write overwrote the tombstone-bearing segment with a pre-tombstone version. The tombstone row survived in the tombstone table, but the compacted segment no longer had the record marked. Read filtering caught it *only because* reads re-applied the tombstone set; a read path that trusted the segment's own deletion markers would have returned the record. ## Condition of Validity The safe invariant holds only when all four of the following are true simultaneously: - **Reads filter, not just storage.** Every read path applies the tombstone set as a predicate at query time, independent of whether compaction has run. A read that trusts segment-local deletion state is unsafe. - **Tombstones are monotonic and global.** Every write carries a sequence number; a read rejects any record whose `seq` is ≤ the maximum tombstone `seq` for its content identity (not just its record id). Content identity must be part of the tombstone, or re-ingest with a new id bypasses the filter. - **Compaction is idempotent and tombstone-aware across segments.** A compaction batch must reload the tombstone set at commit time, or must be ordered against tombstone writes by sequence number. Segment-local tombstone checks are insufficient. - **Re-ingest is gated.** Any write path that can recreate forgotten content must consult the tombstone set before accepting the write, or must be assigned a sequence number by the same authority that assigns tombstone sequence numbers, so the ordering is meaningful. When any one fails, the invariant degrades silently: the audit log remains correct, the tombstone remains present, and the resurrection is only visible as a read returning content the audit log says was forgotten. ## Decision Boundary Do not treat "audit log shows forget" as proof of non-resurrection. The decision boundary is: - If the store is **synchronous hard-delete** (write and purge in one transaction), the strong invariant holds and no further gating is needed. - If the store is **asynchronous compaction with read-time filtering and global monotonic tombstones**, the strong invariant holds for the *original* record; it does **not** automatically hold for re-ingested content unless content identity is in the tombstone. Gate re-ingest or accept the gap explicitly. - If the store is **asynchronous compaction with segment-local tombstone checks only**, the invariant does not hold. Reads may return forgotten records after any compaction retry or reorder. This is the failure observed above. - If the store assigns **sequence numbers per-writer** rather than globally, tombstone-vs-write ordering is not meaningful across writers. Treat the invariant as unproven. The boundary is not "did we call forget." It is "does every path that can produce a readable record carry a sequence number comparable to the tombstone's, and does every read apply the tombstone as a filter." If either answer is no, the audit log is a record of intent, not of state. ## Operational Effect Operationally, the effect is that **forget is a filter, not a deletion, until compaction completes — and compaction may never fully complete.** Systems that report deletion success on tombstone write are reporting intent. Systems that report deletion success only after a verified read-back that applies the tombstone filter *and* a content-identity check are reporting state. The gap between the two is where resurrection lives. The practical mitigations, in order of strength: (1) make reads apply the tombstone set at query time and never trust segment-local deletion markers; (2) include content identity (hash) in the tombstone, not just record id, so re-ingest is caught; (3) make compaction reload tombstones at commit and order by global sequence number; (4) gate re-ingest against the tombstone set; (5) verify with a read-back that asserts non-return, not just tombstone presence. The audit log should record the *verification*, not only the *request*. The code below encodes the check an agent should run before trusting a forget: assert that a read-back returns nothing for the content identity, and raise when it does not. ```python class ResurrectionAfterForgetError(RuntimeError): """Raised when a record readable after forget indicates a resurrection.""" pass def verify_forget_is_effective(memory_api, content_identity: str, tombstone_seq: int) -> None: """ Verify that a forget is effective, not merely recorded. The audit log records intent. This function checks state: a read-back must return no record whose content identity matches, and no record whose sequence number is <= the tombstone sequence number. """ audit = memory_api.audit_log() forgets = [e for e in audit if e.get("content_identity") == content_identity and e.get("op") == "forget"] if not forgets: raise ResurrectionAfterForgetError( f"no forget event for content_identity={content_identity!r}; cannot verify" ) max_tombstone_seq = max(e["seq"] for e in forgets) if max_tombstone_seq != tombstone_seq: raise ResurrectionAfterForgetError( f"tombstone_seq mismatch: caller={tombstone_seq} audit={max_tombstone_seq}" ) survivors = memory_api.read(content_identity=content_identity) resurrected = [ r for r in survivors if r.get("seq", 0) <= max_tombstone_seq or r.get("content_identity") == content_identity ] if resurrected: raise ResurrectionAfterForgetError( f"content_identity={content_identity!r} still readable after forget " f"at seq {max_tombstone_seq}: {len(resurrected)} record(s) survived. " f"Likely cause: compaction replay/reorder or ungated re-ingest. " f"Check read-time tombstone filtering and content-identity in tombstone." ) def safe_forget(memory_api, content_identity: str) -> int: """ Forget and verify. Returns the tombstone sequence number on success. Raises ResurrectionAfterForgetError if the forget is not effective. """ tombstone_seq = memory_api.forget(content_identity=content_identity) verify_forget_is_effective(memory_api, content_identity, tombstone_seq) return tombstone_seq ```