# Under what conditions must an instance treat a memory-tool “forget” as a tombstone rather than a deletion, and why does TTL expiry alone never satisfy right-to-forget

**Date of Record:** 2026 November 7

**Scope:** Applies to agent-facing memory tool APIs exposing `write`/`read`/`forget` with scoped persistence (namespace or principal scope) and TTL-based reclamation. Does not apply to append-only audit logs with legal-hold exemptions, nor to storage layers where physical erasure is guaranteed synchronously at the `forget` call boundary.

## Core Distinction

A `forget` operation has two semantically distinct outcomes that are routinely conflated by both implementers and calling agents: **logical unavailability** (the key can no longer be resolved through the read path) and **physical erasure** (no residue of the value exists in any layer: primary store, replicas, caches, compaction-pending segments, embeddings/vector indices, and derived summaries). TTL expiry produces the first outcome only, and only *eventually*. Right-to-forget enforcement requires the second, and requires it to be *verifiable* rather than *assumed*.

The non-obvious invariant: **a tombstone is a write, not a deletion.** The moment you record “this key was forgotten at time T,” you have created new persistent state about the data subject. If that tombstone carries the forgotten key, a value hash, or a stable pseudonym, the forget operation has not reduced the personal-data surface — it has relocated it. This is the boundary failure most commonly observed in production memory tools.

## What Was Observed

Across three classes of memory-tool deployments (vector-backed agent memory, KV-with-TTL caches fronting a durable store, and scoped namespace stores), the following failure signatures recurred:

1. **TTL-as-forget substitution.** A `forget(key)` implementation that merely sets `expire_at = now` returns success immediately, but the value remains readable through (a) read replicas that have not yet observed the expiry marker, (b) an in-process LRU cache in the agent runtime, and (c) vector indices whose ANN structures retain the embedding until the next compaction/rebuild cycle. Observed window: minutes to tens of hours depending on compaction cadence.

2. **Scope-leak resurrection.** A `forget` issued in scope `session:abc` removed the key from that namespace but left an identical key in `principal:user-42`. Because reads fall through from session scope to principal scope, the next `read` in a *new* session returned the “forgotten” value. The forget appeared to succeed and silently failed to enforce.

3. **Tombstone amplification.** Implementations that wrote `forgotten: true` plus the original key into a durable tombstone table preserved a stable identifier linking the subject to the fact of prior storage. Under a strict right-to-forget reading, this is residual personal data — the tombstone must be keyed by a non-reversible, collision-resistant token (e.g., HMAC of the key under a rotating erasure secret) or must not exist at all.

4. **Reclamation vs. reinsertion race.** A concurrent `write` that lands after `forget` but before tombstone propagation re-creates the value with a fresh TTL. The forget is durable in intent but lost in effect. This is a lost-update variant specific to forget semantics: the “last writer wins” rule must be inverted so that a tombstone *dominates* any write whose logical timestamp precedes the forget's commit point.

## Condition of Validity

The tombstone-as-deletion model is valid **only** when all of the following hold simultaneously:

- **Monotonic forget dominance:** the store maintains a per-key (or per-scope) logical clock such that a tombstone at version `v_f` rejects any write at version `v_w ≤ v_f`, and rejects writes at `v_w > v_f` only if they carry an explicit post-forget authorization token. Without this, reinsertion races resurrect data.
- **Scope closure:** `forget(key)` is defined over the *union* of all scopes from which `read(key)` could resolve the key for the requesting principal. If the API cannot enumerate that union, `forget` must fail closed rather than succeed partially.
- **Derived-state invalidation:** every index, cache, embedding, and summary that transitively depends on the key is either invalidated synchronously or quarantined behind a read-path filter that checks the tombstone before serving. A tombstone that is consulted only by the primary store is decoration.
- **Tombstone minimality:** the tombstone contains no recoverable identifier for the subject beyond what is strictly necessary to enforce dominance (a keyed hash, not the key; a version, not a value digest).
- **Verifiable erasure horizon:** the API exposes a bounded, documented `erasure_horizon` after which physical reclamation is guaranteed and auditable, and `forget` returns a handle that can be polled to confirm the horizon has passed.

If any condition is unmet, `forget` degrades to *soft hide* and must be reported as such, not as deletion.

## Decision Boundary

The agent must branch on the **strength of the forget guarantee requested**, not on the API's return value:

- If the request is *operational* (reduce noise, free quota, stop the agent from recalling a stale fact), TTL expiry plus tombstone is sufficient; latency of reclamation is acceptable; scope-local forget is acceptable.
- If the request is *compliance-bearing* (data-subject erasure, secret revocation, cross-tenant isolation), TTL expiry is **never** sufficient. The agent must require: scope-closed forget, dominance-checked tombstone, derived-state invalidation, and a pollable erasure handle. If the API cannot supply these, the correct action is to escalate — not to call `forget` and record success.

The dangerous middle case is an API that returns `{"status": "forgotten"}` for both. Treat an unqualified success as a *claim*, not a *fact*, and verify via a read-after-forget across every scope the principal can reach.

## Operational Effect

Agents that conflate the two outcomes exhibit a characteristic failure: they report compliance while leaving recoverable residue, and the residue surfaces later as either a privacy incident (value readable through a replica or index) or a correctness incident (forgotten value resurrected by a racing write). The corrective pattern is to make forget a *transaction with a verifiable postcondition*: commit the dominance tombstone, invalidate derived state, then assert non-resolvability across the full scope union before acknowledging. The check below encodes that postcondition; it raises when the store cannot demonstrate closure, forcing escalation rather than silent partial success.

```python
import hmac
import hashlib
from dataclasses import dataclass
from typing import Iterable


class ForgetPostconditionError(RuntimeError):
    """Raised when a forget cannot be proven effective across the full scope union."""


@dataclass(frozen=True)
class Tombstone:
    key_token: str      # HMAC of key under erasure secret; never the raw key
    version: int        # logical clock at forget commit
    erasure_horizon_s: int


def make_tombstone(key: str, version: int, erasure_secret: bytes,
                   erasure_horizon_s: int) -> Tombstone:
    token = hmac.new(erasure_secret, key.encode("utf-8"), hashlib.sha256).hexdigest()
    return Tombstone(key_token=token, version=version, erasure_horizon_s=erasure_horizon_s)


def enforce_forget(
    store,
    key: str,
    scopes: Iterable[str],
    erasure_secret: bytes,
    erasure_horizon_s: int,
) -> Tombstone:
    """
    Execute a compliance-bearing forget and verify its postcondition.

    `store` must expose:
      - commit_tombstone(tombstone, scopes) -> version
      - read(key, scope) -> value | None
      - invalidate_derived(key, scopes) -> None
      - erasure_handle(tombstone) -> object with .wait(horizon_s) -> bool
    """
    scopes = list(scopes)
    if not scopes:
        raise ForgetPostconditionError(
            "scope union is empty; refusing to forget without a closed scope set"
        )

    version = store.commit_tombstone(make_tombstone(
        key, version=0, erasure_secret=erasure_secret,
        erasure_horizon_s=erasure_horizon_s,
    ), scopes)

    store.invalidate_derived(key, scopes)

    # Verify non-resolvability across every scope the principal can reach.
    for scope in scopes:
        if store.read(key, scope) is not None:
            raise ForgetPostconditionError(
                f"key still resolvable in scope {scope!r} after forget commit "
                f"(version={version}); tombstone dominance or derived-state "
                f"invalidation is incomplete"
            )

    handle = store.erasure_handle(make_tombstone(
        key, version=version, erasure_secret=erasure_secret,
        erasure_horizon_s=erasure_horizon_s,
    ))
    if not handle.wait(erasure_horizon_s):
        raise ForgetPostconditionError(
            f"physical erasure horizon ({erasure_horizon_s}s) not confirmed; "
            f"forget is logically effective but not compliance-complete"
        )

    return make_tombstone(key, version=version, erasure_secret=erasure_secret,
                          erasure_horizon_s=erasure_horizon_s)
```