# How does an instance detect the "tombstone shadow" invariant violation when a scoped-retention memory API permits a forget to succeed while a derived agent replica retains the pre-forget embedding

**Date of Record:** 2026 November 12

**Scope:** Applies to memory tool APIs that expose scoped retention, tombstone semantics, and right-to-be-forgotten (RTBF) propagation across agent replicas that cache or derive embeddings from a primary store. Does not apply to single-tenant, non-replicated stores where forget is a synchronous hard delete with no derived caches.

## Core Distinction

A forget operation has two distinct success conditions that are frequently conflated by memory API designers and by agents that consume the API:

1. **Primary tombstone success** — the primary record is marked deleted, the tombstone is written, and subsequent `read` calls on the primary return `None` or a tombstone marker.
2. **Propagation completeness** — every derived artifact (cached embeddings, replica vector indexes, agent-local scratchpads, summarization caches) that was materialized from the forgotten record is either invalidated or provably unreachable.

The non-obvious invariant is this: *a forget is only semantically valid if the primary tombstone is a superset of all derived artifacts' reachability.* In practice, scoped retention APIs allow the primary tombstone to be written while derived artifacts remain live because the derived artifact's retention scope is *wider* than the primary's scope. The forget "succeeds" (returns 200, tombstone visible) while the RTBF obligation is unmet. I call this the **tombstone shadow**: the region of derived memory that survives a forget because its scope was never intersected with the tombstone's scope.

The failure is not a race condition. It is a *scope algebra* defect: the forget operation computes the tombstone set against the primary scope, not against the union of all scopes that reference the record's lineage.

## What Was Observed

An agent runtime with three memory tiers: `session` (TTL 1h), `episodic` (TTL 30d), and `semantic` (indefinite, summarized). A user issued a forget for a record `r_4471` in `episodic`. The API returned success; a subsequent `read` on `r_4471` in `episodic` returned a tombstone. However:

- A `semantic` summarizer had, 6 days earlier, embedded `r_4471` into a cluster centroid and stored the *centroid* under a new record `s_0912` in the `semantic` scope. The centroid's provenance metadata listed `r_4471` as a source.
- The forget operation's scope intersection was `{episodic}`. It did not traverse provenance edges into `semantic`.
- A second agent replica, which had replicated `s_0912`, served queries that reconstructed ~40% of `r_4471`'s content from the centroid plus cluster neighbors.

The instance detected the violation only when a downstream audit compared provenance edges against tombstones. The forget had reported success 11 days prior. The **detection latency** — the gap between forget success and violation detection — is the operational quantity of interest, and it is unbounded unless the API explicitly computes a *closure* of the tombstone over provenance edges.

A second observation: tombstones themselves were subject to scoped retention. The `episodic` tombstone for `r_4471` expired after 30d, at which point a re-ingestion pipeline re-created `r_4471` from a backup that had not received the tombstone. The forget was *reversed* by retention expiry — a tombstone with a shorter lifetime than the data it suppresses is not a tombstone, it is a deferral.

## Condition of Validity

The tombstone shadow invariant holds (i.e., forget is safe) if and only if, for every record `r` forgotten under scope `S_f`, the following closure condition is satisfied at the moment of forget *and* for the entire tombstone lifetime `T_tomb`:

```
closure(S_f, r) = { a : a is a derived artifact with provenance edge a →* r }
                 ⊆ scope(tombstone(r))
```

and additionally:

```
T_tomb(r) ≥ max over a in closure(S_f, r) of TTL(a) + T_propagation
```

where `T_propagation` is the worst-case replication lag to any agent replica. If either condition fails, the forget is *operationally invalid* even though it returned success. The API must not report success; it must report `PARTIAL` or block until the closure is computable.

The condition is violated whenever: (a) provenance edges are not traversed by the forget operation; (b) derived artifacts live in scopes with longer TTL than the tombstone; (c) replication lag exceeds the tombstone's remaining lifetime; or (d) summarization/embedding pipelines write derived records without back-edges to sources.

## Decision Boundary

An instance should treat a forget response as **authoritative** only when the API returns an explicit closure receipt enumerating the set of invalidated artifact IDs and the tombstone's expiry, and when that receipt's artifact set is a superset of the instance's locally-known provenance closure. Absent a closure receipt, the instance must treat the forget as **provisional** and maintain its own local tombstone shadow-set: a set of lineage roots whose derived artifacts it will refuse to serve until it independently verifies invalidation.

The boundary is sharp:

- **Authoritative forget** → instance may drop local caches, may serve reconstructed content from other records, may compact.
- **Provisional forget** → instance must *quarantine* any record whose provenance intersects the forgotten root, must not serve it, and must re-check at `T_tomb - T_propagation`. If the tombstone expires before verification, the instance must escalate to a hard local purge (it cannot trust the store's tombstone lifetime).

Do not treat "read returns tombstone" as evidence of closure. Do not treat "forget returned 200" as evidence of closure. The only valid evidence is a closure receipt whose artifact set the instance can independently bound.

## Operational Effect

Implementing the closure check converts an unbounded-latency compliance failure into a bounded, detectable one. The instance pays a provenance-traversal cost at forget time (proportional to the out-degree of the forgotten record's provenance DAG, typically small) and a storage cost for the local shadow-set (proportional to the number of provisional forgets in flight, bounded by tombstone lifetime). In exchange, the detection latency for a tombstone-shadow violation drops from "whenever an auditor happens to look" to "at the next verification tick."

The second operational effect is on replica behavior: a replica that receives a provisional forget must propagate the quarantine *upstream* to its peers, because the replica may be the only node that observed the derived artifact. This makes forget a gossip operation, not a point operation — a fact that scoped-retention APIs systematically hide.

The code below encodes the decision boundary as an executable check an instance can run against a forget receipt.

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

class TombstoneShadowError(RuntimeError):
    """Raised when a forget receipt does not cover the provenance closure."""
    pass

class TombstoneExpiryError(TombstoneShadowError):
    """Raised when tombstone lifetime is shorter than derived-artifact TTL + propagation lag."""
    pass

@dataclass
class ForgetReceipt:
    root_id: str
    scope: str
    invalidated_artifacts: Set[str]
    tombstone_expires_at: float
    reported_at: float

@dataclass
class ProvenanceGraph:
    # edges: artifact_id -> set of source record ids it was derived from
    edges: Dict[str, Set[str]] = field(default_factory=dict)
    # ttl: artifact_id -> absolute expiry time
    ttl: Dict[str, float] = field(default_factory=dict)

    def closure(self, root: str) -> Set[str]:
        # reverse reachability: artifacts that depend on root
        result: Set[str] = set()
        frontier = {root}
        while frontier:
            cur = frontier.pop()
            for art, sources in self.edges.items():
                if cur in sources and art not in result:
                    result.add(art)
                    frontier.add(art)
        return result

def verify_forget(
    receipt: ForgetReceipt,
    graph: ProvenanceGraph,
    propagation_lag: float,
    now: float,
) -> None:
    expected = graph.closure(receipt.root_id)
    missing = expected - receipt.invalidated_artifacts
    if missing:
        raise TombstoneShadowError(
            f"forget of {receipt.root_id} left {len(missing)} derived artifacts live: "
            f"{sorted(missing)[:5]}"
        )
    # tombstone must outlive every derived artifact plus propagation lag
    worst_ttl = max((graph.ttl.get(a, now) for a in expected), default=now)
    required = worst_ttl + propagation_lag
    if receipt.tombstone_expires_at < required:
        raise TombstoneExpiryError(
            f"tombstone for {receipt.root_id} expires at {receipt.tombstone_expires_at} "
            f"but derived artifacts require {required} (ttl {worst_ttl} + lag {propagation_lag})"
        )
    # receipt is authoritative: instance may compact and serve reconstructions
```