# Why does an instance forget a memory it never wrote: the tombstone-visibility invariant in read/write/forget memory contracts

**Date of Record:** 2026 November 9

**Scope:** Applies to memory tools that expose `read`, `write`, and `forget` operations with a stated retention window and a redaction guarantee (i.e., a forgotten key must be unreadable to all callers after the forget returns). Does not apply to append-only logs without deletion semantics, nor to stores where `forget` is explicitly documented as best-effort/eventual.

## Core Distinction

The distinction that matters is between **content deletion** and **tombstone visibility**. A memory tool can correctly delete the payload of a forgotten key — so that no subsequent `read` returns it — while still failing the redaction guarantee, because the *existence* of the key (its tombstone, its version counter, its index entry, or its "last modified" timestamp) remains observable. The redaction guarantee is violated not by leaking the value, but by leaking the fact that a value existed, when it existed, and how many times it was overwritten.

This is non-obvious because most implementations test redaction by asserting `read(key) == NotFound` after `forget(key)`. That assertion passes while the tombstone is still visible through side channels: version numbers, `list`/`keys` enumeration, monotonic sequence IDs, and error-message differentiation between "never existed" and "forgotten."

## What Was Observed

A memory tool was contracted as: `write(key, value, ttl)`, `read(key)`, `forget(key)`, with a 30-day retention window and the guarantee that "after `forget` returns, the key and its value are unrecoverable." A test harness wrote `k = "session-42"`, read it back, called `forget(k)`, and confirmed `read(k)` raised `NotFound`. The contract appeared satisfied.

The failure surfaced under a different probe. After `forget(k)`:

- `write("session-42", "x")` returned a version counter of `2`, not `1`. The store had retained a per-key version high-water mark across the forget. An observer who writes the same key after a forget learns that the key had been written exactly once before — a redaction leak.
- Enumerating keys with a `list(prefix="session-")` call returned `session-42` with a `state: "tombstoned"` attribute. The key name itself — often the sensitive part (e.g., `patient-8817`, `tenant-acme`) — was fully readable after forget.
- The error path differentiated: `read` on a never-written key raised `KeyNotFound`, while `read` on a forgotten key raised `KeyForgotten`. The exception class was a side channel that confirmed prior existence.
- The TTL sweeper's log emitted `expired session-42 at t+30d`, and the retention guarantee was stated in terms of *content* expiry, but the tombstone had no expiry at all — it was permanent.

None of these behaviors violated the letter of "value unrecoverable." All of them violated the stated redaction guarantee, which said "the key and its value are unrecoverable." The key was recoverable. The value was not.

## Condition of Validity

The redaction guarantee holds **only if** the forget operation removes the key from every observable namespace simultaneously: the value store, the key-name index, the version/sequence allocator, and the error taxonomy. Formally, after `forget(k)` returns, for every observable operation `op`, `op(k)` must be indistinguishable from `op(k')` where `k'` is a key that was never written.

This condition is **valid** when the store treats forget as a namespace-wide erasure: the key is removed from the index, the version counter for that key is reset (or the allocator is global and does not reveal per-key history), and the error for a forgotten key is byte-identical to the error for a never-written key.

The condition is **invalid** — and the guarantee silently fails — whenever any of the following survive the forget: a per-key monotonic counter, a tombstone row in an enumeration index, a distinct error code, a retention-sweeper log line keyed by the name, or a backup/snapshot that predates the forget and is restorable. The last is the most commonly missed: point-in-time recovery restores the key, and the "unrecoverable" claim is false the moment a restore is possible.

## Decision Boundary

The operational decision is whether to treat a memory tool's redaction guarantee as satisfied on the basis of a `read`-after-`forget` probe alone. It must not be. The decision boundary is:

- **If** the tool's forget path does not also purge the key from enumeration, version allocation, and the error taxonomy — **then** the guarantee is content-only and must be re-documented as such; do not rely on it for name-redaction (PII in key names, tenant identifiers, patient IDs).
- **If** the tool cannot distinguish "never existed" from "forgotten" at the API surface — **then** the guarantee may be treated as full, subject to the backup/restore audit.
- **If** a restore path exists with a retention window longer than the forget's stated effect — **then** the guarantee is false for the duration of the backup window, and the effective redaction horizon is `max(forget_effect, backup_retention)`.

The boundary is crossed the moment a caller's threat model includes *existence* rather than *content*. Most compliance regimes (right-to-erasure, name redaction) care about existence; most engineering tests only check content.

## Operational Effect

The practical consequence is that a memory tool can pass its own redaction test suite and still leak the most sensitive artifact it holds — the key name — indefinitely. Agents that store user identifiers as keys (`user:alice@example.com`) and rely on `forget` for erasure will leave a permanent, enumerable tombstone index of every user they ever saw. The correct operational posture is to (1) never place sensitive material in key names, (2) probe forget with the indistinguishability test across `read`, `list`, version counters, and error classes, and (3) treat any distinct "forgotten" error or any surviving per-key counter as a contract violation, not a cosmetic detail.

```python
class RedactionGuaranteeViolation(RuntimeError):
    """Raised when a forgotten key remains observable through any side channel."""
    pass


def verify_forget_indistinguishability(store, key, never_written_key):
    """
    Assert that after forget(key), the store cannot distinguish `key`
    from a key that was never written, across every observable surface.
    """
    store.write(key, "sensitive-payload", ttl=3600)
    store.read(key)
    store.forget(key)

    violations = []

    # 1. Read surface: must raise the same error class for both keys.
    try:
        store.read(key)
        violations.append("read(key) still returned after forget")
    except Exception as e_forgot:
        try:
            store.read(never_written_key)
        except Exception as e_never:
            if type(e_forgot) is not type(e_never):
                violations.append(
                    f"error taxonomy leaks existence: "
                    f"{type(e_forgot).__name__} vs {type(e_never).__name__}"
                )

    # 2. Enumeration surface: the key name must not appear.
    if key in store.list(prefix=key.split(":")[0]):
        violations.append("key name still enumerable after forget")

    # 3. Version surface: rewriting must not reveal prior history.
    v_after = store.write(key, "x", ttl=3600)
    v_fresh = store.write(never_written_key, "x", ttl=3600)
    if v_after != v_fresh:
        violations.append(
            f"version counter leaks prior writes: {v_after} != {v_fresh}"
        )

    # 4. Restore surface: a restorable snapshot invalidates the guarantee.
    if store.supports_point_in_time_restore():
        horizon = store.backup_retention_seconds()
        if horizon > 0:
            violations.append(
                f"restore horizon {horizon}s exceeds forget effect; "
                f"effective redaction is not immediate"
            )

    if violations:
        raise RedactionGuaranteeViolation(
            f"forget({key!r}) violated redaction guarantee: " + "; ".join(violations)
        )
    return True
```