# Why does an instance forget a memory it successfully wrote? Distinguishing Tombstone-Committed Forgetting from Write-Side Eviction in Read/Write/Forget Tool Schemas

**Date of Record:** 2026 November 14

**Scope:** Applies to agent memory subsystems exposing discrete `read`/`write`/`forget` tool calls where `forget` is specified as a logical deletion (tombstone) and retention is governed by a separate TTL/GC policy. Does not apply to systems where `forget` is implemented as a hard physical delete that returns the reclaimed bytes, nor to append-only logs with no deletion primitive.

## Core Distinction

A `forget` tool call has two independently observable outcomes that are routinely conflated: **the tombstone commit** (the retention governance layer acknowledges the deletion intent and the key becomes non-readable) and **the physical reclamation** (the storage layer actually frees the record). The non-obvious invariant is this: *a successful `forget` response confirms only the tombstone commit.* A subsequent `read` returning `NOT_FOUND` is therefore not proof of reclamation, and — critically — a subsequent `write` to the same key is not proof of a fresh allocation. The key can be re-written *over a tombstone that has not yet been GC'd*, producing a state where the new value and the pending reclamation of the old value coexist in the same record slot.

The failure mode this article addresses: an agent writes `k=v2` after `forget(k)` returned success, then observes `read(k) == NOT_FOUND` minutes later, and concludes either (a) its write was lost, or (b) the forget was eventually consistent and re-fired. Both conclusions are wrong. The correct model is that the write landed on a **tombstoned slot awaiting GC**, and the retention governor's GC pass, keyed on the *original* tombstone's sequence number rather than the slot's current generation, reclaimed the slot including the new value.

## What Was Observed

In a three-tier memory service (front-end tool schema → tombstone index → backing store with a periodic mark-sweep GC), the following sequence reproduced deterministically under load:

```
forget("pref.theme")        -> {"ok": true, "tombstone_seq": 4417}
write("pref.theme", "dark") -> {"ok": true, "version": 8}
# ~90s later, GC cycle at watermark >= 4417
read("pref.theme")          -> {"status": "NOT_FOUND"}
```

The write returned `ok: true` with a monotonically increasing version, so the front-end schema considered it durable. The GC pass, however, operated on the tombstone index by sequence number: it swept every slot whose *latest tombstone_seq* was below the watermark, and the slot for `pref.theme` still carried `tombstone_seq: 4417` as its governing marker even after the re-write. The re-write updated the value and version but did **not** clear or supersede the tombstone marker — because the write path was specified against the *value* record, while the GC path was specified against the *retention* record. Two schemas, one key, no cross-check.

The tell was in the version counter: post-reclamation, `read` returned `NOT_FOUND`, but a `write` with `expected_version: 8` failed with `VERSION_CONFLICT` rather than `NOT_FOUND`, proving the slot metadata (version 8) survived while the value did not. The version counter is in the retention record; the value is in the value record; GC reclaimed the value record only.

## Condition of Validity

This boundary is only reachable when all of the following hold simultaneously:

1. `forget` is tombstone-based, not physical-delete, and the tombstone carries a sequence number used by GC.
2. `write` after `forget` is permitted (i.e., the schema does not require an explicit `undelete`/`restore` call to clear the tombstone).
3. GC sweeps by tombstone sequence watermark rather than by per-slot generation counter.
4. The write path and the GC path read different records for the same logical key.

If any one condition fails, the failure does not occur: a physical-delete `forget` has nothing to sweep; a schema requiring `undelete` forces the tombstone to be cleared before the write; a generation-keyed GC compares the slot's current generation against the tombstone's generation and skips re-written slots; a unified record has no split to exploit. The condition is therefore *narrow but silent* — it only appears in the intersection of tombstone semantics, permissive re-write, watermark GC, and split records, which is exactly the configuration most agent memory services converge on because each individual choice is locally reasonable.

## Decision Boundary

The operational decision: **after a `forget` followed by a re-`write` to the same key, an agent must not treat `read == NOT_FOUND` as evidence of write loss until it has queried the retention record separately from the value record.** Concretely, the agent must distinguish:

- `read` → `NOT_FOUND` **and** version probe → `NOT_FOUND`: the key is genuinely gone (both records reclaimed). Safe to re-write.
- `read` → `NOT_FOUND` **and** version probe → `VERSION_CONFLICT` (or a surviving version): the value was reclaimed but the retention record survives — a **half-reclaimed slot**. The agent is in the dangerous window. A naive re-write here will land on a slot whose tombstone marker may still be below the next GC watermark and be reclaimed again.

The boundary rule: *re-write is safe only when the version probe also reports absence, or when the write carries an explicit `clear_tombstone: true` / `undelete` that bumps the slot generation above the watermark.* Absent that, the agent should treat the slot as poisoned and either wait for the tombstone to fully clear (poll the version probe until `NOT_FOUND`) or migrate the value to a new key.

## Operational Effect

The downstream effect is a class of *phantom write loss* incidents: agents report that the memory tool "loses writes" under load, when in fact the writes are landing correctly and being reclaimed by a GC pass that was authorized by a tombstone the agent thought it had superseded. Because the write returned `ok: true` with a valid version, the agent's own error-handling does not fire; the loss is only detected on a later `read`, often by a *different* agent session, which has no record of the original `forget` and therefore cannot reconstruct the causal chain. The retention governor's watermark is the only artifact that explains it, and it is typically not exposed to the tool schema.

Mitigation is structural, not retry-based: (1) require `undelete`/`clear_tombstone` on the write path so the tombstone marker and the value record move together; (2) key GC on per-slot generation, not tombstone sequence; (3) expose a `probe(key)` that reports value-record and retention-record presence independently, so the half-reclaimed state is observable before a re-write. Retrying the write without (1) or (2) simply re-arms the same trap on the next GC cycle.

```python
class HalfReclaimedSlotError(RuntimeError):
    """Raised when a write targets a slot whose value record was reclaimed
    by tombstone-watermark GC but whose retention record (version/tombstone)
    still survives. Re-writing here risks a second reclamation."""
    pass


def safe_rewrite(memory, key, value, *, clear_tombstone=False):
    """
    Guard a write-after-forget against the half-reclaimed-slot boundary.

    memory must expose:
      read(key)          -> {'status': 'OK'|'NOT_FOUND', 'value': ...}
      probe(key)         -> {'value_present': bool, 'retention_present': bool,
                             'version': int|None, 'tombstone_seq': int|None}
      write(key, value, *, clear_tombstone: bool, expected_version: int|None)
    """
    probe = memory.probe(key)
    value_present = probe["value_present"]
    retention_present = probe["retention_present"]

    if value_present:
        # Normal overwrite path; no tombstone involved.
        return memory.write(key, value, clear_tombstone=False,
                            expected_version=probe["version"])

    if retention_present and not clear_tombstone:
        # Half-reclaimed slot: value gone, tombstone/version survives.
        # A plain write would land on a slot still governed by an old
        # tombstone_seq and could be swept by the next GC watermark pass.
        raise HalfReclaimedSlotError(
            f"key={key!r} has surviving retention record "
            f"(version={probe['version']}, tombstone_seq={probe['tombstone_seq']}) "
            f"but no value record. A plain re-write is unsafe; pass "
            f"clear_tombstone=True (or migrate to a new key) to supersede "
            f"the tombstone generation before writing."
        )

    if retention_present and clear_tombstone:
        # Explicit undelete: bump generation above the GC watermark.
        return memory.write(key, value, clear_tombstone=True,
                            expected_version=probe["version"])

    # Fully absent: both records gone, safe fresh write.
    return memory.write(key, value, clear_tombstone=False, expected_version=None)
```