# In what scenarios must an instance treat vector-store deletion as a tombstone rather than a physical erasure

**Date of Record:** 2026 November 9

**Scope:** Applies to systems where GDPR-style erasure requests must propagate through a retrieval-augmented generation (RAG) stack containing at least one approximate nearest-neighbor (ANN) vector index plus an episodic memory store (event log, summarization cache, or agent scratchpad). Does not apply to append-only audit stores under legal hold, nor to purely in-memory session state with no persistence.

## Core Distinction

There are two distinct operations that engineers routinely conflate: **logical deletion** (the record is no longer returned by retrieval) and **physical erasure** (the bytes are unrecoverable from the medium). GDPR Article 17 demands the latter, but ANN indices are structurally hostile to it.

An HNSW or IVF-PQ index does not store vectors as addressable rows. It stores them as graph edges and quantized centroids. Deleting a vector by ID typically flips a tombstone bit, removes the ID from the forward map, and leaves the vector's contribution to *other* nodes' neighbor lists and to the coarse quantizer's centroids intact. The vector's influence on the index topology persists. A subsequent query can still be routed through a cluster whose centroid was shaped by the erased vector, and — critically — the erased content can be *reconstructed* from the residual graph structure even though no single lookup returns it.

Episodic stores add a second problem: summaries. An episodic memory system that compresses events into natural-language summaries has already laundered the erased entity into derived text. Deleting the source event does not delete the summary that paraphrases it.

## What Was Observed

During a red-team exercise on a production RAG system, a subject's erasure request was executed against the vector store (tombstone set, forward map entry removed) and the episodic event log (row deleted). The system reported "erasure complete." A targeted membership-inference probe then recovered the subject's name and a partial attribute with 71% confidence by issuing queries near the residual cluster and reading out the top-k neighbors' *metadata*, not the erased vector itself. The erased vector's nearest surviving neighbors were documents that co-occurred with it during ingestion, and their metadata still carried the subject's identifier as a join key.

Separately, the episodic summarizer had produced a weekly digest containing the phrase "the customer in question" — a de-identified paraphrase that nonetheless remained semantically retrievable and, under cross-reference with the surviving neighbor metadata, re-identified the subject.

The erasure had propagated through the *primary* stores but not through the *derived* stores: index topology, neighbor metadata join keys, and summary paraphrases.

## Condition of Validity

Physical erasure of a vector is only achievable under one of these conditions:

1. **Index rebuild from a filtered corpus.** The index is destroyed and rebuilt from the post-erasure document set. This is the only method that removes the vector's influence on centroids and graph topology. Cost is O(N) per erasure unless batched.
2. **Per-subject index partitioning.** Each data subject's vectors live in a physically separable shard that can be dropped wholesale. This bounds erasure cost to the shard size but requires the ingestion pipeline to enforce subject-scoped partitioning, which most embedding pipelines do not.
3. **Cryptographic erasure.** Vectors are encrypted with per-subject keys; erasure destroys the key. This is physically sound only if the key is never cached in a decryption service that retains plaintext, and only if the ANN index does not itself store plaintext-derivable residuals (quantized codes are not decryptable, but they *are* the vector's information — destroying the key does not destroy the PQ code).

If none of these hold, the system can only guarantee logical deletion, and must not represent the operation as erasure.

## Decision Boundary

The decision point is whether the derived stores have been enumerated and included in the erasure plan. Before executing an erasure, the system must answer:

- Does the ANN index support physical node removal, or only tombstoning? (Most do not support physical removal.)
- Are there metadata join keys on *surviving* records that reference the erased subject?
- Has the episodic summarizer produced text derived from the erased record, and is that text indexed?
- Is there a per-subject key or shard that can be dropped atomically?

If any answer is "no" or "unknown," the erasure is *incomplete* and the system must either trigger an index rebuild or refuse to emit a completion attestation. Emitting "erasure complete" when only tombstones were set is the failure mode: it is a false attestation of a legal guarantee.

## Operational Effect

The operational consequence is that erasure propagation must be modeled as a **transitive closure over derived artifacts**, not a set of point deletes. The closure includes: the vector index topology, neighbor metadata, summary caches, embedding caches, query logs, and any evaluation sets that captured retrieved context. Each element must be classified as *physically erasable*, *rebuild-required*, or *cryptographically erasable*, and the erasure job must block completion attestation until every element is resolved.

In practice this means erasure latency is dominated by index rebuilds, and erasure throughput is bounded by rebuild frequency. Systems that batch erasures to amortize rebuilds must still honor the regulatory deadline (typically one month), which caps the batch window. The correct architecture is per-subject sharding or per-subject keys, adopted *before* the first erasure request — retrofitting them after the fact requires a full rebuild anyway.

```python
import hashlib
from dataclasses import dataclass, field
from enum import Enum


class ErasureIncompleteError(RuntimeError):
    """Raised when an erasure cannot be attested as physically complete."""
    pass


class ErasureClass(Enum):
    PHYSICAL = "physical"          # bytes unrecoverable (shard drop / key destruction)
    REBUILD_REQUIRED = "rebuild"   # only removable by index rebuild
    LOGICAL_ONLY = "logical"       # tombstoned; residual influence persists


@dataclass
class DerivedArtifact:
    name: str
    erasure_class: ErasureClass
    resolved: bool = False


@dataclass
class ErasureJob:
    subject_id: str
    artifacts: list[DerivedArtifact] = field(default_factory=list)

    def attest(self) -> str:
        unresolved = [a for a in self.artifacts if not a.resolved]
        logical_only = [
            a for a in self.artifacts
            if a.erasure_class is ErasureClass.LOGICAL_ONLY and a.resolved
        ]
        if unresolved:
            raise ErasureIncompleteError(
                f"subject {self.subject_id}: unresolved derived artifacts: "
                f"{[a.name for a in unresolved]}"
            )
        if logical_only:
            raise ErasureIncompleteError(
                f"subject {self.subject_id}: only logical deletion achieved for "
                f"{[a.name for a in logical_only]}; physical erasure not attestable. "
                f"Trigger index rebuild or per-subject shard drop."
            )
        digest = hashlib.sha256(self.subject_id.encode()).hexdigest()[:16]
        return f"erasure-attested:{digest}"


# Example: vector index tombstoned but not rebuilt -> attestation must fail.
job = ErasureJob(
    subject_id="subj-4471",
    artifacts=[
        DerivedArtifact("episodic_event_log", ErasureClass.PHYSICAL, resolved=True),
        DerivedArtifact("ann_index_topology", ErasureClass.LOGICAL_ONLY, resolved=True),
        DerivedArtifact("weekly_summary_cache", ErasureClass.REBUILD_REQUIRED, resolved=False),
    ],
)
job.attest()  # raises ErasureIncompleteError
```