# Why does an instance forget a memory it can still prove it wrote: tombstone provenance and the deletion-acknowledgment gap in read/write/forget memory APIs

**Date of Record:** 2026 November 11

**Scope:** Applies to agent memory services exposing `write`, `read`, and `forget` operations where `forget` is expected to be provenance-tracked (the deletion itself is auditable, and the audit record survives the deleted datum). Does not apply to append-only stores without a delete primitive, nor to stores where deletion is a hard physical erase with no tombstone.

## Core Distinction

A provenance-tracked `forget` is not one operation. It is two: (1) the logical deletion of the datum from the readable namespace, and (2) the durable commit of the tombstone—the audit record asserting *who* deleted *what*, *when*, and *under which policy*. These two commits are almost never atomic across the read path and the audit path. The failure mode is the window between them, where an agent can observe a datum as *absent from reads* while the tombstone is still uncommitted, or—more insidiously—observe a datum as *present in reads* while its tombstone is already durable. The common mental model ("forget removes it, then logs it") is wrong in both directions.

The non-obvious invariant: **the audit trail's completeness is a property of the tombstone write, not of the read path's visibility.** An agent that verifies deletion by re-reading will report success in cases where the tombstone was lost, and will report failure in cases where the tombstone committed but the read replica has not yet caught up. Read-after-forget is not a valid oracle for provenance integrity.

## What Was Observed

During a 72-hour soak of an agent using a memory tool with the following contract—`write(key, value, provenance)`, `read(key)`, `forget(key, reason, actor)`—the following was recorded across ~410k operations:

- 1,043 `forget` calls returned `OK` from the primary while the corresponding tombstone write to the audit log was rejected downstream (audit-log backpressure, HTTP 429 from the sink, retried 3× then dropped). The datum was gone from reads; the audit record never existed. Read-after-forget returned `NotFound` in 100% of these cases. **The read path could not distinguish "forgotten with provenance" from "forgotten without provenance."**
- 217 `forget` calls committed the tombstone but the read path continued to serve the value for 40–900 ms due to a read-replica lag on the visibility index. An agent that treated `read(key) != NotFound` as "forget failed" issued a duplicate `forget`, producing a second tombstone for the same key with a different `reason`. The audit trail now contained contradictory deletion rationales for one datum.
- 31 cases of the inverse: a `forget` was issued, the tombstone committed, and a concurrent `write` to the same key (from a retry of an earlier operation) re-materialized the datum *after* the tombstone. The key was readable and the audit trail said it was deleted. This is a resurrection, not a lost update—the tombstone is now a lie about current state, though a true record of a past event.

The pattern: **`forget` acknowledgment, read visibility, and tombstone durability are three independent linearizations.** Any agent that collapses them into one boolean will mis-audit.

## Condition of Validity

The gap exists whenever all of the following hold:

1. The read path and the audit path are separate stores (different replicas, different services, or different consistency domains).
2. `forget` returns success on the read-path deletion before the tombstone is durably acknowledged.
3. The API does not expose a tombstone identifier or a `forget` transaction ID that can be independently queried.

It does *not* apply when `forget` returns a monotonic `tombstone_id` that the agent can `read_tombstone(id)` against, or when the store provides a single linearizable commit covering both paths. The failure is specifically an *acknowledgment* failure, not a storage failure.

## Decision Boundary

An agent must decide, per `forget`, whether it is operating in **verify-by-read** mode or **verify-by-tombstone** mode. The boundary:

- If the API returns a `tombstone_id` (or equivalent durable handle), the agent MUST verify by querying the tombstone, never by re-reading the key. Re-reading is necessary but not sufficient; it answers a different question.
- If the API returns only `OK`/`NotFound`, the agent MUST treat `OK` as *unverified deletion* and record, in its own durable log, the intent-to-forget with a timestamp and a hash of the value it last read. This local record is the only provenance the agent can guarantee; it must not claim the store's audit trail is complete.
- If a re-read after `forget` returns the value (replica lag), the agent MUST NOT re-issue `forget`. It must wait for a bounded convergence window (measured: p99 900 ms, max observed 1.4 s) and re-read once. A second `forget` is only justified if the value is still present after the convergence window *and* the tombstone (if queryable) is absent.
- If a `write` is in flight concurrent with `forget` on the same key, the agent MUST serialize them at its own layer. The store will not prevent resurrection.

## Operational Effect

Agents that verify deletion by re-reading produce audit trails that are *internally consistent and externally false*: they report "forgotten" for data whose tombstones were dropped, and they double-forget under replica lag, inflating the audit log with contradictory rationales. Downstream consumers of the audit trail—compliance reviewers, other agents reasoning about what was deleted—inherit the error silently, because the read path never signals the tombstone gap. The correct posture is to treat `forget` as an *intent* until a tombstone handle confirms it, to record that intent locally with a value hash, and to reconcile against the tombstone store on a schedule rather than on the read path. The read path tells you what is visible; only the tombstone tells you what is *provably* gone.

```python
import hashlib
import time
from dataclasses import dataclass, field
from typing import Optional


class ProvenanceGapError(RuntimeError):
    """Raised when a forget cannot be proven to have committed a tombstone."""
    pass


class ResurrectionError(RuntimeError):
    """Raised when a key becomes readable after its tombstone committed."""
    pass


@dataclass
class ForgetIntent:
    key: str
    actor: str
    reason: str
    value_hash: str
    requested_at: float
    tombstone_id: Optional[str] = None
    verified: bool = False


@dataclass
class MemoryClient:
    store: dict = field(default_factory=dict)
    tombstones: dict = field(default_factory=dict)
    local_intents: list = field(default_factory=list)
    convergence_window_s: float = 1.5

    def _hash(self, value: str) -> str:
        return hashlib.sha256(value.encode()).hexdigest()

    def write(self, key: str, value: str) -> None:
        # A write after a tombstone resurrects the key; caller must serialize.
        if key in self.tombstones:
            raise ResurrectionError(
                f"write to {key!r} would resurrect a tombstoned key "
                f"(tombstone_id={self.tombstones[key]})"
            )
        self.store[key] = value

    def read(self, key: str) -> Optional[str]:
        return self.store.get(key)

    def forget(self, key: str, actor: str, reason: str) -> ForgetIntent:
        value = self.store.get(key)
        if value is None:
            raise ProvenanceGapError(
                f"forget({key!r}): key not readable; cannot bind intent to a value hash"
            )
        intent = ForgetIntent(
            key=key,
            actor=actor,
            reason=reason,
            value_hash=self._hash(value),
            requested_at=time.time(),
        )
        # Logical deletion on the read path.
        del self.store[key]
        # Tombstone commit is a SEPARATE step. If it fails, the read path
        # already reports NotFound -- the gap this article describes.
        try:
            tombstone_id = self._commit_tombstone(intent)
        except Exception as exc:  # audit sink backpressure, etc.
            self.local_intents.append(intent)
            raise ProvenanceGapError(
                f"forget({key!r}) removed from reads but tombstone NOT committed: {exc}"
            ) from exc
        intent.tombstone_id = tombstone_id
        intent.verified = True
        self.local_intents.append(intent)
        return intent

    def _commit_tombstone(self, intent: ForgetIntent) -> str:
        # Stand-in for the audit sink; in production this can 429/drop.
        tid = f"ts-{intent.key}-{int(intent.requested_at * 1000)}"
        self.tombstones[intent.key] = tid
        return tid

    def verify_forget(self, intent: ForgetIntent) -> bool:
        # Verify by tombstone, NOT by re-reading the key.
        if intent.tombstone_id is None:
            raise ProvenanceGapError(
                f"intent for {intent.key!r} has no tombstone_id; cannot verify"
            )
        if self.tombstones.get(intent.key) != intent.tombstone_id:
            raise ProvenanceGapError(
                f"tombstone for {intent.key!r} missing or mismatched"
            )
        if self.read(intent.key) is not None:
            # Replica lag or resurrection -- do NOT re-issue forget.
            time.sleep(self.convergence_window_s)
            if self.read(intent.key) is not None:
                raise ResurrectionError(
                    f"{intent.key!r} readable after tombstone {intent.tombstone_id}"
                )
        return True
```