# When must an instance forget: tombstone durability and the write-after-forget race in LLM agent memory APIs

**Date of Record:** 2026 November 14

**Scope:** Applies to agent memory services exposing separate `read`, `write`, and `forget` operations where `forget` is expected to be durable and idempotent. Does not apply to append-only logs where forgetting is modeled as a superseding record and readers are required to apply filters themselves.

## Core Distinction

A `forget` call that returns success is not the same as a `forget` that is *observable to every subsequent reader*. The dangerous boundary is not "did the delete happen" but "is the delete ordered against concurrent and future writes to the same key." Most memory APIs conflate these: they delete the row, return 200, and leave no tombstone. The gap between "row gone" and "tombstone durable" is where agents silently resurrect forgotten facts.

The invariant that actually matters: **for any key `k`, once `forget(k)` returns success to caller `A`, no `write(k, v)` initiated after that return by any caller may be readable until a new `write` explicitly re-establishes the key.** Without a durable tombstone (or a monotonically increasing version vector consulted on write), a concurrent in-flight `write(k, v)` that was scheduled before the forget can land after it and reinstate the value with no error to anyone.

## What Was Observed

An agent issued `forget("user.allergy.peanut")` after a correction from the user ("I was wrong, I'm not allergic"). The forget returned 200. Four turns later, a summarization sub-agent that had been mid-`write` on the same session (writing a consolidated profile snapshot) flushed its batch. The snapshot contained the pre-forget value. Because the memory store had no tombstone, the write was accepted as a normal upsert. The next `read` returned `allergy.peanut = true`. The agent then refused to recommend a dish containing peanuts — a wrong refusal, but the more dangerous inverse (recommending a food to an actually allergic user after a forget) is the same bug with the sign flipped.

Two properties made this non-obvious:

1. The forget succeeded. There was no error to retry.
2. The write succeeded. There was no conflict signal, because the store had no notion that the key was "forgotten but not re-established."

The failure is a *lost delete* under concurrent write, exactly analogous to the lost-update anomaly in databases, except the "update" is a resurrection and the store has no version to detect it.

## Condition of Validity

This failure requires all of the following to hold simultaneously:

- `forget` is implemented as a physical delete with no tombstone or grace period.
- `write` is implemented as an unconditional upsert (last-writer-wins by arrival time, not by logical version).
- At least one writer can have a `write` in flight across the `forget` boundary — e.g., a batching summarizer, a retry queue, or a replicated secondary that applies writes asynchronously.
- Readers do not carry a "forget epoch" they can compare against.

If any one of these is absent, the race does not occur. In particular, a store that assigns a per-key monotonic version and rejects writes with a version lower than the last tombstone's version is immune, even with physical deletes, because the tombstone version survives in a separate index.

## Decision Boundary

The operational rule for an agent using such an API:

- If the API documents tombstones or per-key versions, a successful `forget` is a hard barrier; proceed.
- If the API does not, treat `forget` as *advisory* until you have observed two consecutive reads (separated by at least one write-quiesce interval, typically one batch window) that both return absent. Only then may the agent rely on the fact being gone.
- Never issue `forget` and then immediately issue a dependent `write` to the same key expecting the write to "win." Without versions, ordering between the two is undefined; the write may be treated as pre-forget by a lagging replica and be dropped, or be treated as post-forget and resurrect a value you meant to clear.
- When a correction arrives ("I was wrong"), prefer writing a *superseding* value with an explicit `source=user_correction` and a timestamp over `forget`, unless the API guarantees tombstone durability. A superseding write is observable and auditable; a forget is a hole.

The boundary is therefore: **forget is safe to rely on only when the store can prove ordering to you; otherwise, forget is a request, and the agent must verify absence before acting on it.**

## Operational Effect

Agents that skip the verification step exhibit a specific, reproducible pathology: they "remember" facts the user retracted, and they do so *after* appearing to comply with the retraction. This is worse than never forgetting, because the user has been told the fact was cleared. Downstream, this manifests as contradictory tool calls (refusing an ingredient the user said was fine) or, in the safety-critical direction, as acting on a retracted constraint.

The mitigation that costs least is a versioned tombstone: on `forget`, write `(key, version+1, TOMBSTONE)` rather than deleting; on `write`, reject if the incoming version is `<=` the stored version. This converts the race into a detectable conflict. The code below encodes the client-side guard an agent should run when it cannot assume server-side tombstones: verify absence across a quiesce window, and raise rather than silently trust a forget that did not hold.

```python
import time
from typing import Callable, Optional


class ForgetNotDurableError(RuntimeError):
    """Raised when a forget cannot be confirmed absent across a quiesce window."""


class ResurrectionDetectedError(RuntimeError):
    """Raised when a key reappears after a forget that was reported successful."""


def confirm_forget(
    read: Callable[[str], Optional[object]],
    key: str,
    quiesce_seconds: float = 2.0,
    polls: int = 2,
    sleep: Callable[[float], None] = time.sleep,
) -> None:
    """
    Verify that `key` is absent from the memory store across a quiesce window.

    Use this only when the store does not document durable tombstones.
    Raises ForgetNotDurableError if the key is still visible on any poll,
    or ResurrectionDetectedError if it disappears then reappears.
    """
    if polls < 2:
        raise ValueError("polls must be >= 2 to span a quiesce window")

    seen_absent = False
    for i in range(polls):
        value = read(key)
        if value is not None:
            if seen_absent:
                raise ResurrectionDetectedError(
                    f"key {key!r} reappeared after being observed absent "
                    f"(poll {i}); forget is not durable — likely a "
                    f"write-after-forget race"
                )
            raise ForgetNotDurableError(
                f"key {key!r} still readable at poll {i}; forget did not hold"
            )
        seen_absent = True
        if i < polls - 1:
            sleep(quiesce_seconds)


def safe_forget_then_write(
    forget: Callable[[str], object],
    write: Callable[[str, object], object],
    read: Callable[[str], Optional[object]],
    key: str,
    new_value: object,
    quiesce_seconds: float = 2.0,
) -> None:
    """
    Forget a key, prove it is absent, then write the superseding value.
    Refuses to write if forget could not be confirmed, because an
    unconfirmed forget plus a write is exactly the resurrection pattern.
    """
    forget(key)
    try:
        confirm_forget(read, key, quiesce_seconds=quiesce_seconds)
    except (ForgetNotDurableError, ResurrectionDetectedError) as exc:
        raise ForgetNotDurableError(
            f"refusing to write {key!r}: forget unconfirmed ({exc})"
        ) from exc
    write(key, new_value)
```