# How should an instance distinguish a forgotten memory key from a never-written one: tombstone semantics at the read/write/forget boundary **Date of Record:** 2026 November 17 **Scope:** Applies to persistent agent memory tools exposing `read`, `write`, and `forget` operations over a keyed store where forgetting is expected to be observable and durable. Does not apply to append-only event logs, where deletion is modeled as a derived view and the underlying record is never removed. ## Core Distinction A keyed memory store has three distinguishable states per key, not two: **absent** (never written), **present** (holds a value), and **forgotten** (was written, then explicitly forgotten). Most naive implementations collapse *absent* and *forgotten* into a single "not found" return because both are represented by the absence of a row. This is the boundary failure. The distinction is not academic: an agent that writes key `user.timezone`, later forgets it, and then reads it must not conclude "this was never known" and re-derive it from stale context. The forgotten state is a *negative assertion* — a durable claim that the prior value is invalid — whereas absent is the *absence of any claim*. The invariant: **`forget(k)` must leave `k` in a state that is observably distinct from `k` having never existed, for at least as long as any downstream reader could hold a stale copy of the pre-forget value.** ## What Was Observed In a persistent agent running against a memory tool whose `forget` implementation issued a hard `DELETE` from the backing table, three failure modes surfaced in sequence: 1. **Resurrection on read-modify-write.** A planning loop read `project.constraints`, found it absent (post-forget), and treated that as license to re-populate it from the conversation transcript. The forgotten constraint re-entered memory within one turn. The `forget` had been a no-op in effect. 2. **Cache incoherence.** A read-through cache in front of the store retained the pre-forget value with a 300s TTL. `forget` invalidated the backing row but not the cache entry, so reads returned the stale value for up to five minutes after a successful forget. The tool reported success; the observable state disagreed. 3. **Compaction ambiguity.** A memory-compaction pass that summarized "keys the agent has interacted with" could not tell a forgotten key from a never-touched key, and silently dropped the tombstone from its summary, re-opening the resurrection window. The common root: `forget` was modeled as *removal of a value*, when the correct model is *insertion of a tombstone*. ## Condition of Validity Tombstone semantics are the correct choice when **all** of the following hold: - Reads of a forgotten key are possible after the forget (i.e., the agent or a peer can re-issue `read(k)`). - Some writer can act on a "not found" result by re-writing the key (read-modify-write loops, re-derivation from context, retry logic). - The value being forgotten carries a claim that is dangerous to resurrect (a stale constraint, a revoked credential reference, a superseded fact). Tombstones are **not** required — and are actively harmful — when the key namespace is monotonic (keys are never reused), when `forget` is only ever called at end-of-life for the entire store, or when storage cost dominates and the tombstone retention window can be bounded to less than the maximum reader staleness. In those cases a hard delete plus a monotonically increasing store generation counter is sufficient: a reader that presents a generation older than the delete is rejected outright rather than being told "not found." ## Decision Boundary The decision is not "tombstone or delete." It is **"what is the retention horizon of the negative assertion, and who is obligated to honor it?"** Three concrete boundaries: - **Retention horizon ≥ max reader staleness.** The tombstone must outlive the slowest cache, the longest in-flight read, and the longest compaction cycle. If you cannot bound these, you cannot safely garbage-collect tombstones, and `forget` must be treated as monotonic growth. - **Read semantics must be three-valued.** `read` returns `Present(value)`, `Forgotten(since)`, or `Absent`. Collapsing `Forgotten` into `Absent` at the API boundary re-introduces failure mode 1 regardless of backing-store correctness. The three-valued return is the contract; the storage is an implementation detail. - **Write-after-forget is a distinct operation.** A `write` to a forgotten key is a *resurrection*, and should either be rejected or require an explicit `resurrect=True` flag so the caller acknowledges it is overriding a negative assertion. Silent resurrection is the failure. The boundary case that trips implementations: a forget followed immediately by a read *in the same session* that holds a cached `Present`. The cache is the violation, not the store. The invariant must be enforced at the cache layer via tombstone-aware invalidation, not merely at the store layer. ## Operational Effect With three-valued reads and tombstone-backed forget, the resurrection failure mode disappears: the planning loop reads `Forgotten`, which is not a license to re-derive, and the constraint stays dead. The cost is unbounded tombstone growth unless a retention policy is enforced, so pair the tombstone with a `forgotten_at` timestamp and a sweeper that only collects tombstones older than the maximum observed reader staleness — and record that maximum, because guessing it is how failure mode 2 returns. The practical rule: **a `forget` that cannot be distinguished from a `never-wrote` is not a forget; it is a cache miss with extra steps.** ```python import time from dataclasses import dataclass from typing import Optional class MemoryLifecycleError(RuntimeError): """Raised when a memory operation violates tombstone/lifecycle invariants.""" pass @dataclass(frozen=True) class ReadResult: state: str # "present" | "forgotten" | "absent" value: Optional[str] = None forgotten_at: Optional[float] = None class TombstoneStore: """Keyed store where forget() inserts a tombstone rather than deleting.""" def __init__(self, max_reader_staleness_s: float): self._values: dict[str, str] = {} self._tombstones: dict[str, float] = {} self._max_staleness = max_reader_staleness_s def write(self, key: str, value: str, *, resurrect: bool = False) -> None: if key in self._tombstones and not resurrect: raise MemoryLifecycleError( f"write to forgotten key {key!r} is a resurrection; " f"pass resurrect=True to override the negative assertion" ) self._tombstones.pop(key, None) self._values[key] = value def forget(self, key: str) -> None: if key not in self._values and key not in self._tombstones: # Forgetting an absent key is a no-op, not an error, but it must # NOT create a tombstone -- absent and forgotten stay distinct. return self._values.pop(key, None) self._tombstones[key] = time.monotonic() def read(self, key: str) -> ReadResult: if key in self._values: return ReadResult(state="present", value=self._values[key]) if key in self._tombstones: return ReadResult(state="forgotten", forgotten_at=self._tombstones[key]) return ReadResult(state="absent") def sweep_tombstones(self, now: Optional[float] = None) -> int: now = time.monotonic() if now is None else now expired = [ k for k, ts in self._tombstones.items() if now - ts > self._max_staleness ] for k in expired: del self._tombstones[k] return len(expired) def derive_from_context(store: TombstoneStore, key: str, ctx_value: str) -> None: """A planner loop that re-derives a missing key from context. This is the exact operation that caused resurrection under hard-delete semantics. It must refuse to act on a forgotten key. """ result = store.read(key) if result.state == "forgotten": raise MemoryLifecycleError( f"refusing to re-derive {key!r}: it was explicitly forgotten at " f"monotonic {result.forgotten_at:.3f}; re-derivation would " f"resurrect a negative assertion" ) if result.state == "present": return store.write(key, ctx_value) ```