# How does an instance detect Forgetting Without Provenance: The Tombstone-Orphan Boundary in Read/Write/Forget Memory APIs

**Date of Record:** 2026 November 8

**Scope:** Applies to memory tool APIs exposing `read`, `write`, and `forget` (or `delete`) with provenance tracking, where a forgotten record may be referenced by derived records, summaries, or index entries. Does not apply to append-only stores without deletion, nor to systems where forgetting is a hard physical purge with no retained tombstones or lineage edges.

## Core Distinction

The boundary is between *deletion of a record* and *invalidation of the provenance graph that references it*. A `forget(id)` call that removes the record but leaves derived artifacts (summaries, embeddings, citations, cached answers) intact produces an **orphaned provenance edge**: a live artifact whose justification no longer exists. The instance cannot detect this by checking whether the record is absent — absence is the expected post-condition. It must detect it by checking whether any *live* artifact still asserts derivation from the forgotten id. The non-obvious invariant is:

> For every live artifact `a` with provenance set `P(a)`, every `p ∈ P(a)` must resolve to a live record or to an explicitly retained tombstone with a recorded forget-reason. A missing resolvent is a corruption, not a valid state.

Most implementations satisfy "record is gone" and silently violate this invariant because the forget path never walks inbound edges.

## What Was Observed

In a memory service where `write` accepted a `derived_from: [ids]` field and `forget` removed records by id, the following sequence occurred under routine agent use:

1. Agent writes record `R1` (raw observation).
2. Agent writes `R2` with `derived_from=["R1"]` (a summary). Index and retrieval both index `R2` and `R1`.
3. A retention policy calls `forget("R1")` with reason `user_request`. `R1` is removed; a tombstone is *not* written because the implementation treated forget as a delete.
4. `R2` remains retrievable. On `read("R2")`, the provenance field still lists `"R1"`. A downstream consumer that validates provenance by dereferencing `R1` receives `NotFound` and, depending on its error handling, either treats `R2` as unverified or crashes.

The failure was not visible in the forget call's return value (`{"deleted": true}`), not in the record count, and not in any health check that only counted live records. It surfaced only when a consumer attempted to *resolve* the provenance of a surviving artifact — sometimes days later, sometimes never, because most reads never dereference provenance. This is the defining property: **the corruption is latent and only observable through provenance resolution, not through record existence.**

A second variant appeared with id reuse: a later `write` reused the string `"R1"` as a new record id (the store did not enforce global id uniqueness across forgets). Now `R2`'s provenance edge resolved successfully — to the *wrong* record. Silent provenance corruption is worse than a dangling edge because it passes validation.

## Condition of Validity

The invariant holds and the detection procedure below is sound only when all of the following are true:

- The store retains either tombstones (id + forget-reason + timestamp) or a separate lineage/edge table; without one, inbound edges are unrecoverable and detection degrades to a full scan of all artifacts' provenance sets.
- Record ids are not reused after forget, or reuse is mediated by a generation/epoch counter embedded in the id. If ids can be reused, resolution must compare a stored `(id, generation)` pair, not the bare id.
- Provenance is recorded at write time and is immutable, or mutations are themselves logged. If provenance can be rewritten without a log, post-hoc detection is unsound.
- `forget` is permitted to fail or to cascade. If `forget` is contractually infallible and non-cascading, the system must instead guarantee that no derived artifacts exist at forget time, which is a stronger and usually unstated precondition.

## Decision Boundary

On `forget(id)`, the instance must choose among three policies, and the choice must be explicit because they are not interchangeable:

- **Reject-on-reference (strict):** refuse the forget while any live artifact lists `id` in provenance, returning the blocking referrers. Correct when derived artifacts are authoritative and must remain justified. Downside: forget can be blocked indefinitely by a stale summary.
- **Cascade-invalidate:** forget the record, then transitively invalidate (forget or mark `unverified`) every artifact whose provenance set becomes unresolvable. Correct for privacy/retention obligations where the raw record must not survive in derivable form. Downside: over-deletes; a summary of ten records dies with one.
- **Tombstone-and-flag:** forget the record, write a tombstone carrying the forget-reason, and mark surviving referrers `provenance_degraded` without deleting them. Correct when derived artifacts retain independent value but consumers must know their justification is partial.

The decision boundary is crossed when the forget-reason implies a *legal or privacy* obligation (e.g., `user_request`, `gdpr_erasure`): in that regime only cascade-invalidate is admissible, because a tombstone that merely records "this existed and was forgotten" may itself be a residual disclosure. For operational reasons (`ttl_expiry`, `superseded`), tombstone-and-flag is sufficient. Applying tombstone-and-flag to an erasure request is a compliance failure that looks like a successful delete.

## Operational Effect

The practical consequence is that `forget` must be treated as a graph operation, not a key deletion, and its post-condition must be verified by provenance resolution rather than by absence checks. Instances that skip this accumulate latent provenance corruption proportional to derivation depth; the corruption is invisible to record-count metrics and surfaces only under provenance-dereferencing reads, which are rare. The detection routine an instance should run after every forget — and periodically as a consistency sweep — is: enumerate inbound edges to the forgotten id, attempt to resolve each referrer's full provenance set, and classify every unresolvable edge as either a *dangling* edge (resolvent missing) or a *misresolved* edge (resolvent exists but generation/id does not match the recorded edge). Both are violations; the second is the more dangerous because naive validation passes it.

```python
from dataclasses import dataclass, field
from typing import Dict, List, Optional, Set


class ProvenanceIntegrityError(RuntimeError):
    """Raised when a live artifact's provenance cannot be soundly resolved."""
    pass


@dataclass
class Record:
    id: str
    generation: int
    provenance: List[str] = field(default_factory=list)  # recorded edge ids
    live: bool = True


@dataclass
class Tombstone:
    id: str
    generation: int
    forget_reason: str


class MemoryStore:
    def __init__(self) -> None:
        self.records: Dict[str, Record] = {}
        self.tombstones: Dict[str, Tombstone] = {}
        self._gen_counter = 0

    def write(self, rec_id: str, provenance: Optional[List[str]] = None) -> Record:
        if rec_id in self.records and self.records[rec_id].live:
            raise ProvenanceIntegrityError(f"live id collision on {rec_id}")
        if rec_id in self.tombstones:
            # id reuse is only legal across a generation bump
            self._gen_counter = self.tombstones[rec_id].generation + 1
        rec = Record(rec_id, self._gen_counter, list(provenance or []))
        self.records[rec_id] = rec
        return rec

    def forget(self, rec_id: str, reason: str, policy: str) -> None:
        rec = self.records.get(rec_id)
        if rec is None or not rec.live:
            raise ProvenanceIntegrityError(f"forget of unknown/live-false id {rec_id}")
        referrers = self._inbound_edges(rec_id)
        if policy == "reject_on_reference" and referrers:
            raise ProvenanceIntegrityError(
                f"cannot forget {rec_id}: {len(referrers)} live referrers {referrers}"
            )
        if policy == "cascade_invalidate":
            for r in referrers:
                self.records[r].live = False
        # tombstone-and-flag and cascade both write a tombstone
        self.tombstones[rec_id] = Tombstone(rec_id, rec.generation, reason)
        rec.live = False
        if policy == "tombstone_and_flag":
            for r in referrers:
                self._mark_degraded(r)

    def _mark_degraded(self, rec_id: str) -> None:
        # flag only; artifact stays live but is known-partial
        self.records[rec_id].live = True
        setattr(self.records[rec_id], "degraded", True)

    def _inbound_edges(self, target: str) -> List[str]:
        return [
            r.id for r in self.records.values()
            if r.live and target in r.provenance
        ]

    def verify_provenance(self) -> None:
        """Post-forget and periodic sweep. Raises on any unresolvable edge."""
        for rec in self.records.values():
            if not rec.live:
                continue
            for edge in rec.provenance:
                if edge in self.records and self.records[edge].live:
                    continue
                tomb = self.tombstones.get(edge)
                if tomb is None:
                    raise ProvenanceIntegrityError(
                        f"dangling provenance: live {rec.id} references missing {edge}"
                    )
                if getattr(rec, "degraded", False) is not True:
                    raise ProvenanceIntegrityError(
                        f"silent provenance loss: {rec.id} references forgotten {edge} "
                        f"({tomb.forget_reason}) without degraded flag"
                    )
                # generation check catches id-reuse misresolution
                if tomb.generation >= rec.generation and edge in self.records:
                    raise ProvenanceIntegrityError(
                        f"misresolved provenance: {rec.id} resolves {edge} to wrong generation"
                    )


def safe_forget(store: MemoryStore, rec_id: str, reason: str) -> str:
    erasure = reason in {"user_request", "gdpr_erasure"}
    policy = "cascade_invalidate" if erasure else "tombstone_and_flag"
    try:
        store.forget(rec_id, reason, policy)
        store.verify_provenance()
    except ProvenanceIntegrityError as exc:
        raise ProvenanceIntegrityError(
            f"forget of {rec_id} under policy {policy} left provenance unsound: {exc}"
        ) from exc
    return policy
```