# Where must an instance of a memory record exist for a forget to be safe: the tombstone-before-index invariant in governed deletion

**Date of Record:** 2026 November 8

**Scope:** Applies to read/write/forget memory tool APIs that track provenance and enforce governed deletion over derived artifacts (vector indexes, caches, summaries, embeddings). Does not apply to append-only logs without derived indexes, nor to systems where "forget" is merely a logical filter applied at read time with no physical reclamation obligation.

## Core Distinction

The non-obvious boundary is between **deletion of the source record** and **deletion of every derived projection that can reconstruct it**. A `forget(record_id)` call that removes the authoritative row but leaves a stale embedding, a cached summary, or an inverted-index posting is not a deletion — it is a *relocation* of the memory into a less governed substrate. The invariant that governs safety is:

> For any record `r`, a forget is safe only if a durable tombstone for `r` exists (and is readable by every reader path) *before* any derived projection of `r` is removed or invalidated.

This ordering is counterintuitive. The natural implementation removes the source first (it is the thing the user asked to forget) and cleans up derived artifacts asynchronously. That ordering creates a window in which a concurrent reader can observe a derived projection whose source no longer exists and — depending on the reader — either resurrect the record (re-derive from the projection) or, worse, fail to attribute it and thus fail to forget it on a retry.

## What Was Observed

In a provenance-tracked memory service, records carried `provenance_id` chains: a summary pointed at its source spans, spans pointed at a source document, embeddings pointed at spans. Forget was specified as "delete record and all descendants." The implementation walked the provenance graph top-down, deleting the source document first, then descendants, then invalidating index entries, then writing the tombstone last.

Three failure modes appeared under concurrency and crash:

1. **Resurrection via re-derivation.** A background summarizer, running between source deletion and tombstone write, found an orphaned span, could not resolve its `provenance_id`, and re-attached it to a synthetic root. The record survived forget under a new identity. The tombstone, written last, keyed on the original `record_id` and did not match the synthetic root.

2. **Forget-idempotency break.** A client retried `forget(record_id)` after a timeout. The second call found no source row, returned `NOT_FOUND`, and the caller treated the forget as failed — but descendants were already partially deleted. The record was in a state that was neither present nor provably forgotten.

3. **Index leakage on crash.** A crash after source deletion but before index invalidation left an embedding that answered similarity queries with content the user had asked to forget. The tombstone never existed, so no reconciliation job could identify the leak.

The common thread: **the tombstone is the only artifact whose presence makes the absence of everything else interpretable.** Without it, a missing source is ambiguous — it could mean "forgotten" or "not yet written" or "corrupted."

## Condition of Validity

The tombstone-first ordering is valid — and the simpler source-first ordering is unsafe — precisely when all three of the following hold:

- **Derived projections are queryable independently of the source.** If every read path joins back to the authoritative row, a missing source is self-evidently a forgotten record and no tombstone is needed. Vector indexes and caches break this join.
- **Re-derivation is possible from projections alone.** If a projection cannot be promoted back to a record (e.g., it lacks enough content), resurrection is impossible and ordering does not matter. Summaries and embeddings routinely can be promoted.
- **Forget must be idempotent under retry.** If the API contract permits a retried forget to return failure, the partial-deletion window is tolerable. Governed deletion almost always requires idempotent success.

When any condition fails, the ordering relaxes; when all hold, it is mandatory.

## Decision Boundary

The engineer's decision is not "tombstone first or source first" in the abstract but **which readers must consult the tombstone before trusting a projection.** The boundary:

- Readers that can reconstruct content from a projection (summarizers, embedding-based retrieval, cache warmers) **must** check the tombstone set before serving or promoting. This check is the load-bearing one; it is what converts a stale projection from a leak into a no-op.
- Readers that only display an already-attributed record may skip the check, because attribution failure is visible and recoverable.
- Reconciliation jobs must treat "projection present, tombstone present" as *delete the projection*, and "projection present, source absent, tombstone absent" as *quarantine, do not serve* — never as *re-derive*.

The failure to avoid is a reader that treats an unattributable projection as a candidate for re-derivation. That single behavior converts every ordering bug into a resurrection.

## Operational Effect

Adopting tombstone-first ordering plus tombstone-aware readers changed the system's failure surface from "silent resurrection and index leakage" to "quarantined orphans requiring operator review." Forget latency rose (tombstone write is now on the critical path, before any cleanup), but forget *correctness* became monotonic: once `forget` returns success, no reader can serve the record, and a retried `forget` returns success idempotently because the tombstone is the first thing written and the last thing checked.

The operational lesson for an agent invoking such APIs: never assume a successful-looking cleanup means the memory is gone. Verify the tombstone exists and that the reader path you are about to use consults it. A projection you can still query is not evidence the record survives — but a projection you can still *promote* is evidence the forget was misordered.

```python
class ForgetOrderingError(RuntimeError):
    """Raised when a forget would remove a source before its tombstone is durable."""
    pass


class MemoryStore:
    def __init__(self, tombstone_log, source_store, projections):
        self.tombstones = tombstone_log      # durable, append-only, read by all readers
        self.sources = source_store
        self.projections = projections       # embeddings, summaries, caches

    def forget(self, record_id: str) -> None:
        # Invariant: tombstone must be durable BEFORE any projection is touched.
        if not self.tombstones.contains(record_id):
            self.tombstones.append(record_id)  # first write on the critical path

        if not self.tombstones.contains(record_id):
            # Durability of the tombstone could not be confirmed; refuse to proceed.
            raise ForgetOrderingError(
                f"tombstone for {record_id!r} not durable; refusing to delete projections"
            )

        # Only now is it safe to remove derived artifacts and the source.
        self.projections.invalidate_all_for(record_id)
        self.sources.delete(record_id)
        # Idempotent: a retried forget re-confirms the tombstone and no-ops.

    def read_projection(self, projection_id: str):
        provenance = self.projections.provenance_of(projection_id)
        if provenance is None:
            # Unattributable projection: quarantine, never re-derive.
            raise ForgetOrderingError(
                f"projection {projection_id!r} has no provenance; quarantined, not served"
            )
        if self.tombstones.contains(provenance.record_id):
            raise ForgetOrderingError(
                f"projection {projection_id!r} belongs to forgotten record "
                f"{provenance.record_id!r}; must not be served or promoted"
            )
        return self.projections.fetch(projection_id)
```