# Under what conditions must an instance treat a successful scoped-forget as a tombstone rather than an absence

**Date of Record:** 2026 November 10

**Scope:** Applies to memory tool APIs that expose `write`, `read`, and `forget` operations with scope parameters (tenant, session, namespace, or key-prefix) and that advertise deletion guarantees. Does not apply to append-only logs without deletion semantics, nor to systems where `forget` is documented as best-effort asynchronous garbage collection with a separate compaction barrier.

## Core Distinction

The non-obvious boundary is between **absence** and **tombstone**. A `read` that returns "not found" is ambiguous: it may mean the key was never written, or it may mean the key was written and then forgotten within a scope that the current reader is authorized to observe. Most memory tool APIs collapse these two states into a single null result. That collapse is safe only when the forget operation is *total* with respect to the read scope.

The failure mode appears when the forget is *scoped*: `forget(scope=A)` removes the record from the visibility of readers in scope A, but the underlying record may persist in a parent or sibling scope, or in a tombstone that is itself readable by a wider scope. A reader in scope A sees absence and correctly concludes "no record." A reader in a wider scope B ⊇ A sees the record still present, or sees a tombstone marker. If the system does not distinguish these, an agent operating in scope A can be induced to re-write the forgotten value — because absence is a legitimate precondition for `write` — thereby resurrecting data that a deletion guarantee was supposed to eliminate.

The invariant that must hold: **a scoped forget must be observable as a tombstone to any writer whose write scope intersects the forgotten scope.** Absence alone is insufficient because absence is also the precondition for creation.

## What Was Observed

Consider a memory tool with three scopes: `tenant`, `session`, `key`. A record is written at `(tenant=T, session=S, key=K)`. A forget is issued at `(tenant=T, session=S)` — a session-scoped purge, as might be triggered by a user ending a conversation with a "forget this session" instruction.

The API returns `{"forgotten": 1, "status": "ok"}`. A subsequent `read(tenant=T, session=S, key=K)` returns `{"found": false}`. This is correct and expected.

Now the same agent, later in the same session identifier (session IDs are frequently reused after reconnection), issues `write(tenant=T, session=S, key=K, value=V')`. The write succeeds. The deletion guarantee for the original session is now violated in a subtle way: the *original* value V is gone, but the *key* K is live again, and any downstream consumer that treats the key as a durable identity (an index, a cache, a foreign reference) now resolves to V' where it previously resolved to V or to nothing.

The more dangerous variant: the forget was issued at `(tenant=T)` — a tenant-wide purge for a GDPR-style erasure request. The API returns success. But the implementation performs the purge by writing tombstones at the tenant scope and lazily deleting records at session scopes. A reader at `(tenant=T, session=S)` for a *different* session S' that shared a key namespace sees `found: false` for K, correctly, but a reader at `(tenant=T)` with an administrative scope sees the tombstone and, depending on the API's serialization, may see `found: true, tombstone: true, previous_value_hash: ...`. If the administrative reader is an agent with write authority at tenant scope, it can write K again, and the tombstone is overwritten rather than respected. The erasure guarantee is silently defeated by a write that the API accepted as a normal create.

In both cases the API's contract — "forget removes the record" — was technically honored at the scope where forget was called, and technically violated at the scope where the consequence matters. The gap is the tombstone's visibility and its write-blocking semantics.

## Condition of Validity

The "absence is sufficient" assumption is valid only when all of the following hold:

1. **Scope totality.** The forget scope is a superset of every scope from which the key is reachable. If a key is reachable from `(tenant, session)` and from `(tenant)`, a forget at `(tenant, session)` is not total, and absence at the session scope does not imply absence at the tenant scope.
2. **Scope immutability during the forget window.** No concurrent writer can re-create the key at an intersecting scope between the forget's linearization point and the reader's observation. Without a tombstone, there is no mechanism to enforce this; the window is real.
3. **Non-reuse of scope identifiers.** Session IDs, tenant IDs, and key names are not recycled. If a session ID can be reused, a forget at that session scope is not a durable guarantee — it is a guarantee about a *time interval*, and the API must say so.
4. **No resurrection path through parent scopes.** A write at a child scope cannot shadow a tombstone at a parent scope, and a read at a parent scope cannot resolve through a child scope that has been forgotten.

When any of these fails — and in practice at least condition 1 and condition 2 fail routinely in multi-tenant memory tools — the API must expose a tombstone, and the tombstone must be checked by `write` before the write is admitted.

## Decision Boundary

The operational rule for an agent using such an API:

- If `forget` returns success **and** a subsequent `read` at the same scope returns a tombstone marker (not merely `found: false`), the agent may treat the key as durably forgotten and may re-write it only if the write is at a scope strictly disjoint from the forgotten scope.
- If `forget` returns success **and** `read` returns bare absence, the agent must **not** treat absence as proof of forgetting. It must issue a tombstone-probe read at the widest scope it is authorized to observe. If the probe returns a record or a tombstone, the forget was scoped and the agent must escalate: either widen the forget scope, or record in its own working state that the key is "forgotten-but-resurrectable" and refuse to re-write it.
- If the API provides no tombstone mechanism and no probe, the agent must assume that any scoped forget is a visibility change, not a deletion, and must treat the key as permanently poisoned for writes at any intersecting scope.

The boundary is sharp: **the presence of a tombstone read path is the discriminator between a deletion guarantee and a visibility guarantee.** An agent that cannot observe the tombstone cannot distinguish the two, and must default to the weaker interpretation.

## Operational Effect

Treating a scoped forget as a tombstone rather than an absence changes three behaviors:

1. **Write admission.** Writes must be preceded by a tombstone check at the widest observable scope, not by a `found: false` check at the target scope. This adds one read per write but prevents resurrection.
2. **Cache invalidation.** Downstream caches keyed on the memory key must be invalidated on tombstone observation, not on absence observation. Absence-observation invalidation leaves cached values live for keys that were forgotten at a narrower scope.
3. **Audit semantics.** A forget that produces a tombstone is auditable ("this key was forgotten at scope X at time T"); a forget that produces absence is not. For deletion guarantees that must be provable — regulatory erasure, user-requested forgetting — the tombstone is the only defensible evidence that the forget occurred rather than that the key was never written.

The cost is storage: tombstones persist until a compaction barrier that is itself scoped, and compaction must respect the same intersection rules. The alternative — absence-as-forget — is cheaper and is the default in most memory tool implementations, which is precisely why the failure is common and why it must be guarded explicitly.

```python
from __future__ import annotations

from dataclasses import dataclass
from enum import Enum
from typing import Optional


class ForgetScope(str, Enum):
    TENANT = "tenant"
    SESSION = "session"
    KEY = "key"


class ScopedForgetViolation(RuntimeError):
    """Raised when a write would resurrect a key forgotten at an intersecting scope."""


@dataclass(frozen=True)
class Scope:
    tenant: str
    session: Optional[str] = None
    key: Optional[str] = None

    def intersects(self, other: "Scope") -> bool:
        if self.tenant != other.tenant:
            return False
        if self.session is not None and other.session is not None:
            if self.session != other.session:
                return False
        if self.key is not None and other.key is not None:
            if self.key != other.key:
                return False
        return True

    def contains(self, other: "Scope") -> bool:
        """True if self is a superset of other (self is wider or equal)."""
        if self.tenant != other.tenant:
            return False
        if self.session is not None and self.session != other.session:
            return False
        if self.key is not None and self.key != other.key:
            return False
        return True


@dataclass
class Tombstone:
    scope: Scope
    forgotten_at: float


class MemoryStore:
    def __init__(self) -> None:
        self._records: dict[Scope, bytes] = {}
        self._tombstones: list[Tombstone] = []

    def forget(self, scope: Scope, now: float) -> int:
        removed = 0
        for s in list(self._records):
            if scope.contains(s):
                del self._records[s]
                removed += 1
        self._tombstones.append(Tombstone(scope=scope, forgotten_at=now))
        return removed

    def read(self, scope: Scope) -> Optional[bytes]:
        # Tombstone check precedes record lookup: a forgotten scope reads as
        # tombstone, not as absence, for any reader whose scope intersects it.
        for t in self._tombstones:
            if t.scope.intersects(scope) and t.scope.contains(scope):
                return None  # tombstoned
        return self._records.get(scope)

    def is_tombstoned(self, scope: Scope) -> bool:
        return any(t.scope.contains(scope) for t in self._tombstones)

    def write(self, scope: Scope, value: bytes, now: float) -> None:
        # The boundary invariant: a write must be refused if any tombstone at an
        # intersecting scope would be shadowed by this write. Absence is NOT
        # sufficient evidence that the key is writable.
        for t in self._tombstones:
            if t.scope.intersects(scope):
                raise ScopedForgetViolation(
                    f"write at {scope} intersects tombstone at {t.scope} "
                    f"(forgotten_at={t.forgotten_at}); refusing resurrection"
                )
        self._records[scope] = value


def safe_write(
    store: MemoryStore,
    scope: Scope,
    value: bytes,
    now: float,
    *,
    allow_disjoint_scope: bool = True,
) -> None:
    if store.is_tombstoned(scope):
        if not allow_disjoint_scope:
            raise ScopedForgetViolation(
                f"scope {scope} is tombstoned; writes disabled by policy"
            )
        raise ScopedForgetViolation(
            f"scope {scope} is tombstoned; re-write requires a strictly "
            f"disjoint scope, which this call cannot prove"
        )
    store.write(scope, value, now)
```