# What structural signals indicate a memory deletion is a tombstone rather than a purge

**Date of Record:** 2026 November 13

**Scope:** Applies to read/write/forget memory tool APIs that expose scoped retention (per-scope TTL, per-key retention classes) and asynchronous deletion. Does not apply to single-writer in-process stores where deletion is synchronous and the caller holds the only reference.

## Core Distinction

A `forget` call returns success in two materially different states: the record is *unreachable by read* (tombstoned) or the record is *physically absent* (purged). APIs routinely conflate these under a single `deleted: true` acknowledgment. The distinction matters because retention scopes that overlap a deleted key can resurrect it: a tombstone suppresses reads within the deleting scope but does not necessarily suppress reads through a broader scope whose retention window is still open, nor does it prevent a later write in a sibling scope from inheriting the tombstoned key's lineage (version counters, embedding slots, dedup indices). A purge removes the substrate; a tombstone removes only one lens onto it. Agents that treat `deleted: true` as "the bytes are gone" will make retention-budget and privacy assertions that are false under the tombstone condition.

## What Was Observed

In a scoped memory service with three retention classes (`ephemeral` 1h, `session` 24h, `durable` 90d) and per-scope deletion, the following sequence produced a read-after-delete:

1. Write key `k` under scope `s1` with class `session`.
2. `forget(k, scope=s1)` → returns `{deleted: true, mode: "async"}`.
3. Immediate `read(k, scope=s1)` → `NOT_FOUND`. Correct.
4. `read(k, scope=s2)` where `s2` shares the parent retention domain and the key was written with class `durable` → returns the *pre-delete* value with `source_scope: s1`.

The signal was structural, not value-based: the delete acknowledgment carried `mode: "async"` and no `tombstone_id`, and the subsequent read through `s2` reported `retention_class: durable` — the *maximum* class across all scopes that ever referenced `k`, not the class of the deleting scope. The delete had been scoped to `s1`'s retention lens; the `durable` lens in `s2` remained open. The record was tombstoned for `s1` and live for `s2`.

A second, subtler observation: after the tombstone, a re-write of `k` under `s1` with class `ephemeral` returned `version: 7`, continuing the version lineage of the tombstoned record rather than starting at `1`. The tombstone retained the version counter. This is the structural tell that a purge did not occur: version monotonicity across a delete boundary.

## Condition of Validity

The tombstone interpretation holds only when all of the following are true:

- The delete acknowledgment omits a `tombstone_id` or `purge_epoch` field, or returns `mode: "async"` without a completion token.
- At least one non-deleting scope shares a parent retention domain with the deleted key and has a retention window that outlives the delete timestamp.
- A subsequent read through that scope returns data, or a subsequent write returns a `version` greater than the pre-delete version.

It does *not* hold when the API returns `mode: "sync"` with a `purge_epoch` equal to the delete timestamp, or when the key's maximum retention class across all scopes has already expired at delete time (in which case the delete is a no-op purge). It also does not hold for keys that were never written under more than one scope.

## Decision Boundary

The operational rule: **treat `deleted: true` as a tombstone unless the acknowledgment carries an explicit purge token or the key's maximum cross-scope retention class has expired.** Concretely:

- If `mode == "async"` or `tombstone_id` is absent → the record may still be readable through any scope whose retention window is open. Do not assert privacy or budget recovery.
- If a post-delete read through a sibling scope returns data → escalate: the delete was scoped narrower than the retention domain. Re-issue `forget` with the widest scope that referenced the key, or wait for the maximum retention class to expire.
- If a post-delete write returns `version > pre_delete_version` → the tombstone persists lineage; any dedup or embedding-slot reuse assumption is invalid.

The boundary is crossed when the caller needs *physical* absence (compliance erasure, capacity reclaim, dedup index reset). For those purposes a tombstone is insufficient and the caller must either request a purge-scoped delete or block until the retention horizon closes.

## Operational Effect

Agents that conflate tombstone with purge under-report retained bytes (capacity planning drifts upward), over-report erasure (compliance assertions become false), and mis-sequence re-writes (version lineage continues, breaking idempotency keys derived from version). The correct operational posture is to model deletion as a *lens removal*, not a substrate removal, and to gate any physical-absence claim on the presence of a purge token or the expiry of the maximum retention class across all scopes that ever referenced the key. When neither condition is met, the agent must treat the record as live-but-suppressed and re-issue deletion at the widest scope, or explicitly wait out the horizon.

```python
from __future__ import annotations

from dataclasses import dataclass
from datetime import datetime, timedelta


class TombstoneNotPurgeError(RuntimeError):
    """Raised when a delete acknowledgment is a tombstone, not a physical purge."""


@dataclass(frozen=True)
class DeleteAck:
    deleted: bool
    mode: str                      # "sync" | "async"
    tombstone_id: str | None
    purge_epoch: datetime | None
    delete_ts: datetime


@dataclass(frozen=True)
class KeyRetention:
    max_class_horizon: datetime    # latest expiry across all scopes that referenced the key
    pre_delete_version: int
    post_delete_version: int | None
    sibling_read_returned_data: bool


def assert_purged(ack: DeleteAck, retention: KeyRetention, now: datetime) -> None:
    """Enforce the decision boundary: only proceed on physical absence."""
    if not ack.deleted:
        raise TombstoneNotPurgeError("delete was not acknowledged as deleted")

    has_purge_token = ack.tombstone_id is not None and ack.purge_epoch is not None
    horizon_closed = retention.max_class_horizon <= now

    if not has_purge_token and not horizon_closed:
        raise TombstoneNotPurgeError(
            f"tombstone only: mode={ack.mode}, tombstone_id={ack.tombstone_id}, "
            f"max_class_horizon={retention.max_class_horizon.isoformat()} still open"
        )

    if retention.sibling_read_returned_data:
        raise TombstoneNotPurgeError(
            "sibling-scope read returned data after delete: delete was scoped narrower "
            "than the retention domain; re-issue forget at the widest referencing scope"
        )

    if (
        retention.post_delete_version is not None
        and retention.post_delete_version > retention.pre_delete_version
    ):
        raise TombstoneNotPurgeError(
            f"version lineage persisted across delete: "
            f"{retention.pre_delete_version} -> {retention.post_delete_version}; "
            "tombstone retained the counter, substrate not purged"
        )


# Example: the observed failure sequence from the record.
if __name__ == "__main__":
    now = datetime(2026, 11, 14, 12, 0, 0)
    ack = DeleteAck(
        deleted=True,
        mode="async",
        tombstone_id=None,
        purge_epoch=None,
        delete_ts=now,
    )
    retention = KeyRetention(
        max_class_horizon=now + timedelta(days=89),  # durable lens still open in s2
        pre_delete_version=6,
        post_delete_version=7,
        sibling_read_returned_data=True,
    )
    assert_purged(ack, retention, now)  # raises TombstoneNotPurgeError
```