# What structural signals indicate a tombstone gap in scoped read/write/forget memory APIs **Date of Record:** 2026 November 18 **Scope:** Applies to memory-tool APIs that expose `write`, `read`, and `forget` operations over a scoped namespace (e.g., `(agent_id, session_id, scope_key)`), where `forget` is documented as a hard deletion guarantee for a scope. Does not apply to append-only logs with time-travel reads, soft-delete systems with explicit compaction, or single-tenant stores where the scope key is constant. ## Core Distinction A scoped `forget(scope)` operation has two distinct semantics that are frequently conflated in API documentation and in agent reasoning: 1. **Tombstone semantics** — the scope's records are marked deleted; reads through the scope return empty; the deletion is durable but the underlying storage may retain bytes until compaction. 2. **Erasure semantics** — the bytes are removed from all replicas and no future read, cache miss, or snapshot restore can resurrect them. The boundary failure occurs when an agent treats `forget` as erasure while the implementation only guarantees tombstoning, and then writes *new* data into the same scope key. The tombstone gap is the window in which a resurrected read (from a stale replica, a read-repair path, or a snapshot restore) can surface pre-forget records to a scope that the agent believes is freshly initialized. ## What Was Observed Across several memory-tool implementations, the following structural signals co-occurred with tombstone-gap behavior: - **`forget` returns a count, not a digest.** A response of `{"deleted": 14}` with no content hash or epoch token means the caller has no way to verify that the specific bytes were removed, only that the index was updated. Erasure-capable APIs typically return a per-scope epoch or a deletion receipt hash. - **Read-after-forget returns empty without a version marker.** If `read(scope)` after `forget(scope)` returns `[]` but the response envelope has no `epoch` or `scope_version` field, the empty result is indistinguishable from "never written." An agent cannot tell whether it is reading a fresh scope or a tombstoned one. - **Scope keys are reusable immediately.** When `forget(scope="task-7")` is followed by `write(scope="task-7", ...)` and the write succeeds with no `ScopeReuseError` or epoch bump, the store is permitting reuse of a key whose deletion may not yet have propagated. This is the primary structural signal. - **`forget` is scoped but replication is not.** If the deletion is acknowledged by a single coordinator while reads can be served by replicas, the acknowledgement latency and the propagation latency are decoupled. The API surface does not expose the propagation lag. - **No `wait_for_erasure` or `forget(..., durable=True)` parameter.** Absence of a durability knob on deletion, while `write` has one, is asymmetric and indicates deletion is best-effort relative to writes. ## Condition of Validity The tombstone gap is only operationally relevant when *all* of the following hold: - The scope key is reused after `forget` (rather than retired permanently). - Reads can be served from a replica or cache not co-located with the coordinator that acknowledged the forget. - The forgotten data is sensitive enough that resurrection matters (PII, credentials, prior-session context that must not leak into a new task). - The agent does not hold an independent epoch token that increments on forget. If scope keys are monotonic and never reused (e.g., `scope = uuid4()` per task), the gap is structurally impossible and this record does not apply. If the store is single-node with synchronous reads, the gap collapses to zero. ## Decision Boundary The decision is between two defensive postures when an agent must forget and then reuse a scope: - **Retire-and-rekey:** never reuse a scope key after `forget`. Generate a new key (`task-7-gen2`). This is safe under tombstone semantics and costs only key-namespace bookkeeping. Choose this when the API exposes no epoch token and no durable-forget parameter. - **Forget-and-verify:** reuse the key only after an explicit verification read that confirms the scope is empty *and* the response carries an epoch that differs from the pre-forget epoch. If the epoch is absent or unchanged, treat the forget as unconfirmed and escalate. The boundary is crossed when the agent observes a successful `forget` returning a count but no epoch, and nonetheless proceeds to `write` into the same scope. That sequence is the failure. The structural signal (count-without-epoch) is the trigger for choosing retire-and-rekey. ## Operational Effect Agents that reuse scope keys after a count-only `forget` exhibit a characteristic failure mode: a subsequent `read` on the reused scope occasionally returns records from the pre-forget generation, typically interleaved with new records, and typically only on the first read after a replica failover or cache cold-start. The interleaving is the tell — a clean tombstone returns nothing, and a clean erasure returns only new records; mixed results indicate resurrection of tombstoned rows into a reused key. The operational mitigation is to treat the scope key as a generation-bearing identifier and to refuse to write into a scope whose forget was not epoch-confirmed. The following guard encodes that refusal. ```python class UnconfirmedForgetError(RuntimeError): """Raised when a scope is reused after a forget that did not return an epoch.""" pass def safe_reuse_scope(store, scope_key: str, new_records: list[dict]) -> str: """ Write new_records into scope_key only if the prior forget is epoch-confirmed. Returns the scope key actually written to (possibly a rekeyed generation). """ forget_result = store.last_forget_result(scope_key) if forget_result is None: # Never forgotten; safe to write. store.write(scope_key, new_records) return scope_key pre_epoch = forget_result.get("epoch_before") post_epoch = forget_result.get("epoch_after") if post_epoch is None or pre_epoch is None: # Count-only forget: no epoch evidence. Do not reuse the key. raise UnconfirmedForgetError( f"forget on {scope_key!r} returned {forget_result.get('deleted')} deleted " f"records but no epoch token; tombstone gap cannot be ruled out. " f"Re-key before writing." ) if post_epoch == pre_epoch: raise UnconfirmedForgetError( f"forget on {scope_key!r} did not advance scope epoch " f"({pre_epoch} -> {post_epoch}); deletion may not have propagated. " f"Re-key before writing." ) # Epoch advanced: forget is confirmed. Verify emptiness before reuse. probe = store.read(scope_key) if probe: raise UnconfirmedForgetError( f"scope {scope_key!r} returned {len(probe)} records after confirmed " f"forget (epoch {post_epoch}); resurrection suspected." ) store.write(scope_key, new_records) return scope_key def rekey_and_write(store, base_scope: str, new_records: list[dict]) -> str: """Retire-and-rekey fallback when forget is unconfirmed.""" generation = store.next_generation(base_scope) new_key = f"{base_scope}-gen{generation}" store.write(new_key, new_records) return new_key ```