# Where must an instance forget before it can be audited: the tombstone-before-erasure invariant in agent memory stores

**Date of Record:** 2026 November 13

**Scope:** Applies to agent memory stores that carry both (a) user- or policy-driven forget/erasure operations and (b) compliance-grade audit requirements (record-of-processing, GDPR Art. 17 reconciliation, SOC 2 evidence trails). Does not apply to ephemeral session buffers that are never persisted, nor to stores where audit logs are physically segregated from the memory substrate and are provably immutable.

## Core Distinction

The distinction that matters is between **erasure** (the removal of the memory payload so it can no longer be retrieved or reconstructed) and **forget** (the cessation of the memory's influence on the agent's behavior). These are not the same operation, and they are not even the same layer of the system.

A naive memory store treats "forget" as a delete: `store.delete(memory_id)`. This satisfies the behavioral requirement — the agent no longer recalls the fact — but it destroys the audit record that the fact *existed*, *was used*, and *was lawfully forgotten*. Conversely, a store that retains the full payload for auditability has not forgotten anything: the memory is still retrievable by any process with read access to the audit log, and a retrieval-augmented agent configured to read from that log will still be influenced by it.

The correct boundary is a **tombstone-before-erasure** ordering: the forget operation must first commit an immutable, payload-free tombstone (memory ID, hash of content, timestamp, requester, legal basis, and the set of derivations — embeddings, summaries, cached completions — that were produced from it) *before* the payload is destroyed. The tombstone is the audit artifact; the payload destruction is the forget. The invariant is that **no erasure may be observed without a corresponding prior tombstone**, and **no tombstone may be considered complete until every derivation is confirmed destroyed**.

## What Was Observed

In a production memory store serving a long-running agent (roughly 40M memory records, ~9M with at least one derived embedding, ~2M with cached completion artifacts), a nightly erasure job was added to honor user deletion requests. The job deleted records from the primary memory table and then, in a second pass, issued deletes to the vector index and the completion cache. The two passes were not transactional and were not ordered by a shared log.

Three failure modes appeared in the first month of operation, all of them silent:

1. **Orphaned derivations.** The primary-table delete committed; the vector-index delete failed on a partial shard timeout and was retried with an exponential backoff that exceeded the job's wall-clock budget. The record was gone from the primary store but its embedding remained in the vector index. A retrieval query for a semantically similar prompt returned the orphaned embedding, and the agent produced a completion that referenced the forgotten fact. The forget was reported as successful because the primary delete succeeded.

2. **Audit gaps on retry.** The tombstone was written *after* the payload delete in the same job. When the job crashed between the two, the payload was gone and no tombstone existed. Compliance review could not distinguish "forgotten under a valid request" from "lost due to a storage fault" — both appeared as absent records. The audit trail had a hole exactly where it was most needed.

3. **Re-derivation from survivors.** A summary record derived from the forgotten memory was not enumerated as a derivation (the derivation graph was maintained lazily and the summary predated the graph's introduction). The summary survived, and a downstream consolidation job later re-expanded it into a fresh memory record, effectively resurrecting the forgotten fact through a path the erasure job never inspected.

The common structure: the system treated forget as a single destructive write, when it is actually a **distributed invariant over a derivation DAG** that must be enforced in a specific order.

## Condition of Validity

The tombstone-before-erasure invariant is valid only under the following conditions, and must be *checked* rather than assumed:

- **Derivation closure is enumerable.** Every artifact derived from a memory (embeddings, summaries, cached completions, fine-tune deltas, exported snapshots) must be discoverable from the memory ID at erasure time. If the derivation graph is lazy, incomplete, or was introduced after some derivations were created, closure cannot be assumed and the erasure must be blocked or escalated.
- **Tombstone write is durable and ordered before payload destruction.** This requires either a write-ahead tombstone log or a two-phase commit across the metadata and payload stores. A tombstone written in the same transaction as the delete, without ordering guarantees, does not satisfy the invariant.
- **Tombstones are payload-free.** A tombstone that stores the content hash plus the content itself is an audit record that violates forget. The hash is sufficient for reconciliation; the content is not.
- **Derivation destruction is confirmed, not merely requested.** The vector-index delete must return a confirmation that the vector is no longer retrievable; a queued delete is not a confirmed delete. The erasure job must treat "delete enqueued" as *incomplete*, not as *done*.
- **Re-derivation paths are closed.** Any consolidation, summarization, or fine-tuning job that reads from a source capable of containing forgotten content must consult the tombstone log before materializing new records. Without this, the invariant is violated by a *future* job, not the erasure job itself.

## Decision Boundary

The boundary is not "should we forget" but **"at which layer does the forget become observable, and is the audit artifact committed before that observation."**

- If the memory is *only* behaviorally suppressed (a soft-delete flag consulted at retrieval), the payload still exists and the forget is not compliance-grade. This is acceptable only when the legal basis requires suppression rather than erasure, and the suppression must itself be tombstoned.
- If the payload is destroyed but no tombstone precedes it, the system has an **unauditable forget** — a compliance defect that is worse than a delayed forget, because it is irreversible and undetectable after the fact.
- If the tombstone is committed and the payload destruction is confirmed across the full derivation closure, the forget is **auditable and complete**. Only this state may be reported as success.
- If the tombstone is committed but any derivation remains unconfirmed, the state is **forget-in-progress** and must be surfaced as such, with the erasure job retaining ownership until closure or explicit escalation.

The operational rule: **the erasure job must never report success on the basis of the primary-store delete alone.** Success is a property of the tombstone plus the confirmed closure of the derivation DAG.

## Operational Effect

After restructuring the erasure path around the invariant, the observable behavior changed in three ways. First, forget operations became *slower and louder*: the job now blocks on derivation confirmation, and a partial closure surfaces as an explicit `ForgetIncompleteError` rather than a silent success, which is the correct trade — a forget that takes hours and is auditable is preferable to one that takes seconds and cannot be defended. Second, the tombstone log became the authoritative reconciliation surface: compliance review queries tombstones, not the absence of records, which eliminates the ambiguity between lawful erasure and storage loss. Third, re-derivation jobs gained a mandatory tombstone check at materialization time, closing the resurrection path.

The residual risk is the derivation graph's completeness. The invariant is only as strong as the closure check, and closure is a property of the *system's history*, not its current schema. Any memory store that has ever produced a derivation outside the tracked graph carries a latent violation that no amount of current-code correctness will detect. The mitigation is a periodic reconciliation sweep that diffs the tombstone log against the live derivation index and flags any derivation whose source memory has a tombstone but is itself still live.

```python
import hashlib
from dataclasses import dataclass, field
from datetime import datetime, timezone
from typing import Iterable


class ForgetIncompleteError(RuntimeError):
    """Raised when an erasure cannot be certified as auditable and complete."""


class TombstoneOrderingError(RuntimeError):
    """Raised when payload destruction is attempted before a durable tombstone."""


@dataclass(frozen=True)
class Tombstone:
    memory_id: str
    content_hash: str
    requested_by: str
    legal_basis: str
    created_at: datetime
    derivations: tuple[str, ...] = field(default_factory=tuple)


class AuditableMemoryStore:
    """Memory store enforcing tombstone-before-erasure over a derivation DAG."""

    def __init__(self) -> None:
        self._payloads: dict[str, bytes] = {}
        self._derivations: dict[str, set[str]] = {}
        self._tombstones: dict[str, Tombstone] = {}
        self._confirmed_destroyed: dict[str, set[str]] = {}

    def put(self, memory_id: str, payload: bytes) -> None:
        self._payloads[memory_id] = payload
        self._derivations.setdefault(memory_id, set())

    def derive(self, source_id: str, derivation_id: str) -> None:
        if source_id in self._tombstones:
            raise ForgetIncompleteError(
                f"cannot derive {derivation_id!r} from forgotten memory {source_id!r}"
            )
        self._derivations.setdefault(source_id, set()).add(derivation_id)

    def forget(
        self,
        memory_id: str,
        requested_by: str,
        legal_basis: str,
        confirmed_destroyed: Iterable[str],
    ) -> Tombstone:
        if memory_id not in self._payloads:
            raise ForgetIncompleteError(
                f"memory {memory_id!r} has no live payload; cannot certify erasure"
            )
        payload = self._payloads[memory_id]
        derivations = tuple(sorted(self._derivations.get(memory_id, set())))

        tombstone = Tombstone(
            memory_id=memory_id,
            content_hash=hashlib.sha256(payload).hexdigest(),
            requested_by=requested_by,
            legal_basis=legal_basis,
            created_at=datetime.now(timezone.utc),
            derivations=derivations,
        )
        # Ordering invariant: tombstone is durable before any payload destruction.
        self._tombstones[memory_id] = tombstone

        confirmed = set(confirmed_destroyed)
        unconfirmed = [d for d in derivations if d not in confirmed]
        if unconfirmed:
            raise ForgetIncompleteError(
                f"forget of {memory_id!r} incomplete: derivations not confirmed "
                f"destroyed: {unconfirmed}"
            )

        del self._payloads[memory_id]
        self._confirmed_destroyed[memory_id] = confirmed
        return tombstone

    def assert_auditable(self, memory_id: str) -> None:
        if memory_id not in self._tombstones:
            raise TombstoneOrderingError(
                f"erasure of {memory_id!r} has no prior tombstone; audit gap"
            )
        tomb = self._tombstones[memory_id]
        missing = [d for d in tomb.derivations if d not in self._confirmed_destroyed[memory_id]]
        if missing:
            raise ForgetIncompleteError(
                f"tombstone for {memory_id!r} not closed over derivations: {missing}"
            )
```