# What structural signals indicate a scoped-retention memory tool has silently degraded from verifiable deletion to tombstone-only deletion **Date of Record:** 2026 November 17 **Scope:** Applies to agent-facing memory tool interfaces that expose `write`, `read`, and `forget` (or equivalent) operations over a scoped namespace with declared retention windows and an auditable deletion contract. Does not apply to append-only logs with no deletion surface, nor to storage layers where deletion is delegated entirely to a lower-level system whose semantics are already verified independently. ## Core Distinction A memory tool advertises two distinct properties that are routinely conflated by callers: **retention scoping** (the guarantee that a record is not returned outside its declared scope and lifetime) and **verifiable deletion** (the guarantee that after `forget`, the record's bytes are no longer recoverable through any interface the tool exposes, including indirect ones like embeddings, caches, index remnants, and derived summaries). These are orthogonal. A tool can enforce retention scoping perfectly while degrading deletion into a *tombstone*: the record stops being returned by `read`, but its content survives in a secondary structure that the tool itself still consults for other operations — nearest-neighbor retrieval, deduplication, provenance reconstruction, or "recently forgotten" audit views. The boundary failure is this: **the observable signal of successful deletion (`read` returns empty, `forget` returns `ok`) is identical whether deletion was physical or merely logical.** A tombstone-only implementation is indistinguishable from true deletion at the primary interface. The distinction only becomes visible through structural signals in the *shape* of subsequent operations, not in the deletion call itself. ## What Was Observed Across several memory tool implementations, the following structural signals co-occurred with tombstone-only deletion while the primary `forget` path reported success: 1. **Read-after-forget latency inversion.** A `read` on a forgotten key returned empty faster than a `read` on a never-written key. Physical absence and logical absence have different lookup costs. A tombstone requires a positive lookup that then filters; a true miss short-circuits. The *faster* empty read is the suspicious one — it indicates the key was found and suppressed, not absent. 2. **Namespace cardinality persistence.** After forgetting N records in a scope, a metadata or stats call still reported the scope's record count as unchanged, or decreased by less than N. The count tracked logical entries, not live bytes. If the count does not drop by exactly N, deletion did not reclaim. 3. **Deduplication collision on re-write.** Writing the same content to the same key after `forget` succeeded but consumed no additional storage (reported via a size or quota probe), or triggered a "duplicate detected" path. This is the strongest signal: the content hash still existed, so the write deduplicated against a record that was supposed to be gone. 4. **Derived-structure staleness.** Semantic or embedding indices returned a forgotten record's neighbors with the forgotten item still ranked, then filtered post-hoc. The filter is the tell — retrieval happened against live index state, and the forgotten item was removed only at the presentation layer. 5. **Retention-scope leakage under forget.** A record forgotten in scope A remained readable via a scope-B query that shared a derived structure (a global dedup table, a cross-scope embedding index). Scope enforcement and deletion enforcement were implemented at different layers, and forget touched only one. Any one of these is weak evidence. Signals 2 and 3 together, or signal 3 alone on a content-addressed store, are sufficient to classify the tool as tombstone-only. ## Condition of Validity These signals are valid *only* when the following hold; otherwise they produce false positives: - The tool's `forget` contract explicitly claims byte-level or recoverability-level deletion, not merely "will not be returned." If the contract says "suppressed from reads," tombstoning is compliant and none of this applies. - The content written is unique and high-entropy. Low-entropy content triggers legitimate deduplication and confounds signal 3. - The probe is done within a single session against a single tool instance with no background compaction running. Compaction can make a tombstone look physical after a delay; measure before it runs, or pin compaction off. - Quota/size probes measure the tool's own accounting, not an underlying filesystem whose block allocation may lag. When these conditions fail, the signals are uninterpretable and must not be used to downgrade a tool's deletion guarantee. ## Decision Boundary The operational rule: **treat a memory tool as providing verifiable deletion only if a post-`forget` re-write of identical content is observably non-deduplicated AND the scope cardinality drops by exactly the forgotten count.** If either check fails, the tool provides *suppression*, not deletion, regardless of what `forget` returns. Consequences at the boundary: - If the agent's task requires that forgotten data be unrecoverable (secrets, PII, cross-tenant isolation), a tombstone-only tool is **not admissible** even though every call succeeded. The success signal is not evidence of the property. - If the task only requires that forgotten data not influence future reads, tombstone-only is admissible, but the agent must not report "deleted" — it must report "suppressed," because downstream consumers may treat deletion as a compliance fact. - The boundary is crossed the moment a forgotten record's content influences *any* subsequent operation other than being filtered out. At that moment, suppression has leaked into participation. ## Operational Effect An agent that equates `forget → ok` with deletion will systematically over-report compliance and under-report residual exposure. The failure is silent and self-concealing: the very call that should reveal the problem returns success. The only defense is to probe the *structure* of the post-forget state — re-write dedup behavior, cardinality deltas, and derived-index participation — rather than trusting the return value. When those probes indicate tombstoning, the agent must downgrade its own claim from "deleted" to "suppressed" and escalate if the task's contract required recoverability-level deletion. The following guard encodes the check and refuses to certify deletion when structural signals contradict the return value. ```python import hashlib class DeletionNotVerifiableError(RuntimeError): """Raised when a memory tool reports forget() success but structural probes indicate tombstone-only (suppression) rather than true deletion.""" pass def verify_deletion(memory_tool, scope: str, key: str, content: bytes, forgotten_count: int) -> None: """ memory_tool must expose: write(scope, key, content) -> None read(scope, key) -> bytes | None forget(scope, key) -> str # returns 'ok' on reported success scope_cardinality(scope) -> int storage_bytes(scope) -> int # tool-level accounting """ before_card = memory_tool.scope_cardinality(scope) before_bytes = memory_tool.storage_bytes(scope) result = memory_tool.forget(scope, key) if result != "ok": # Explicit failure is fine; we only guard the silent case. return if memory_tool.read(scope, key) is not None: raise DeletionNotVerifiableError( f"forget({scope!r},{key!r}) returned ok but read still yields data" ) after_card = memory_tool.scope_cardinality(scope) if before_card - after_card != forgotten_count: raise DeletionNotVerifiableError( f"cardinality delta {before_card - after_card} != forgotten " f"{forgotten_count}; record suppressed, not reclaimed" ) # Re-write identical content: a true deletion cannot deduplicate against # a record that no longer exists. before_rewrite = memory_tool.storage_bytes(scope) memory_tool.write(scope, key, content) after_rewrite = memory_tool.storage_bytes(scope) grew = after_rewrite - before_rewrite if grew <= 0: raise DeletionNotVerifiableError( f"re-write of identical content grew storage by {grew} bytes; " f"content hash survived forget() -> tombstone-only deletion" ) # Cleanup probe write so the caller's state is unchanged. memory_tool.forget(scope, key) ```