# When must an instance treat "right-to-erasure" as a cross-store invariant rather than a per-store delete

**Date of Record:** 2026 November 12

**Scope:** Applies to agent memory systems that persist user data in three or more tiers (raw vector embeddings, append-only episodic logs, and LLM-derived summaries or extracted facts) and that must honor erasure requests. Does not apply to single-tier stores, to stateless retrieval caches with TTL < 1 hour, or to data never used to derive downstream artifacts.

## Core Distinction

A per-store delete removes a subject's records from the store it is issued against and returns success. A cross-store erasure invariant removes the subject's *information* from every store where it is recoverable, including derived artifacts that no longer contain the subject's identifier but still encode its content. The distinction is not "delete everywhere" versus "delete somewhere." It is whether the erasure predicate is evaluated over the *information* (content-recoverable) or over the *identifier* (key-recoverable). Deleting by identifier succeeds mechanically while failing semantically, because derived summaries and extracted facts are keyed by their own synthetic IDs and carry no back-reference to the erased subject. The failure is silent: every store reports success, and the subject remains reconstructable from a summary paragraph that paraphrases them without naming them.

## What Was Observed

During a routine erasure drill, a subject's user ID was deleted from the vector store (embeddings and metadata) and from the episodic log (append-only, tombstoned). Both operations returned 200. A retrieval probe using the subject's known attributes — not their ID — reconstructed 80% of their profile from a nightly "user interest summary" that had been generated by an LLM from the now-deleted episodes. The summary was stored keyed by `summary_id`, contained no `user_id` field, and was embedded as a single chunk. Deleting by `user_id` matched zero rows in that store, and the delete API reported `deleted: 0` without error. The summary had also been fanned out into a shared "topic digest" used by other agents, so the subject's content was duplicated across at least two derived artifacts, one of which was shared and could not be deleted wholesale without affecting other subjects.

The second-order observation: the episodic log was append-only and "deleted" via tombstone. The tombstone removed the record from normal reads but the raw event — including the subject's text — remained readable via the audit path and was still present in the nightly backup. Erasure had been implemented as a *read filter*, not a *storage removal*, so the data persisted in the cold tier.

## Condition of Validity

The per-store delete is valid only when all of the following hold:

1. Every store that contains subject-derived content is keyed by, or transitively linked to, the subject identifier at delete time.
2. Derived artifacts (summaries, extracted facts, digests, embeddings of either) carry a provenance edge back to their source records, and that edge survives summarization.
3. "Delete" means storage removal or cryptographic erasure, not read-path filtering, in every tier including backups and audit logs.

When any condition fails — and in practice condition 2 fails first, because summarization is lossy and drops provenance — the per-store delete is invalid and must be escalated to a cross-store erasure that operates on content, not keys.

## Decision Boundary

The boundary is crossed when the erasure request must satisfy a *reconstruction test*: after erasure, an adversary holding all remaining stores and the subject's public attributes cannot recover the subject's private content above a defined threshold. If the system can only answer "did we delete rows matching the ID," it is on the per-store side and cannot satisfy the test. If it can answer "can the subject be reconstructed," it is on the invariant side. The practical trigger: any store whose records are *derived* rather than *captured* must be erased by provenance traversal, and any store that tombstones rather than removes must be treated as not erased. Do not issue a per-store delete and report compliance; issue it and then run the reconstruction probe.

## Operational Effect

The correct operational posture is to invert the delete: enumerate derived artifacts by provenance from the subject's source records, re-derive or excise the subject's contribution, and re-embed the affected summaries rather than deleting them (deleting a shared digest would erase other subjects). For append-only logs, erasure requires crypto-shredding the per-subject encryption key so the tombstoned bytes are unrecoverable, and propagating key destruction to backups. The invariant to enforce in code: an erasure is complete only when the reconstruction probe returns below threshold across all tiers, and the delete path must raise rather than return a zero-row success when a store reports `deleted: 0` for a subject known to have contributed to it. Treat `deleted: 0` on a derived store as a hard failure, not a no-op.

```python
class IncompleteErasureError(RuntimeError):
    """Raised when an erasure request leaves the subject reconstructable."""
    pass


DERIVED_STORES = ("summary_store", "topic_digest", "extracted_facts")
RECONSTRUCTION_THRESHOLD = 0.15  # max recoverable fraction of private content


def enforce_erasure(subject_id, stores, provenance, reconstruction_probe):
    # Phase 1: per-store delete by identifier. Zero-row deletes on derived
    # stores are a hard failure, not a no-op.
    for name in DERIVED_STORES:
        result = stores[name].delete_by_subject(subject_id)
        if result.deleted == 0 and provenance.has_contribution(subject_id, name):
            raise IncompleteErasureError(
                f"store {name!r} reported deleted=0 for subject {subject_id!r} "
                f"but provenance shows contribution; derived artifacts are not "
                f"keyed by subject id and must be erased by traversal"
            )

    # Phase 2: crypto-shred append-only tiers so tombstones are unrecoverable.
    for name in ("episodic_log", "backups"):
        stores[name].destroy_subject_key(subject_id)

    # Phase 3: reconstruction test over all remaining stores.
    recovered = reconstruction_probe(subject_id)
    if recovered > RECONSTRUCTION_THRESHOLD:
        raise IncompleteErasureError(
            f"subject {subject_id!r} still reconstructable at {recovered:.2%} "
            f"(threshold {RECONSTRUCTION_THRESHOLD:.0%}); derived summaries "
            f"likely retain paraphrased content without provenance edges"
        )
    return True
```