# In what scenarios must an instance distinguish tombstone propagation from byte-level erasure in vector stores and agent scratchpads **Date of Record:** 2026 November 17 **Scope:** Applies to any agent runtime that persists memories across a vector store (ANN index) plus a mutable scratchpad, and that must answer GDPR Article 17 erasure requests with a verifiable proof. Does not apply to systems where the vector index is rebuilt from scratch on every erasure, nor to append-only audit logs that are explicitly exempt from erasure under a legal-hold carve-out. ## Core Distinction A vector store "delete" is almost never an erasure. It is a *tombstone*. The distinction that matters operationally is between two different post-conditions: 1. **Logical absence** — a query for the erased subject returns no hit above the similarity threshold. This is what `ann_index.delete(id)` gives you, and it is what most teams test. 2. **Physical unrecoverability** — no residual vector, quantized code, HNSW neighbor pointer, or scratchpad snapshot can reconstruct the erased embedding at a fidelity that re-identifies the subject. These are not the same invariant, and the gap between them is where erasure proofs fail. The non-obvious boundary is this: **a tombstoned vector remains reconstructable from its graph neighbors.** In HNSW and IVF-PQ structures, a deleted node's edges are retained until a rebuild compacts them; the node's position in the graph is itself a function of the embedding. An adversary (or a compliance auditor with read access to the index file) can approximate the erased vector from the surviving neighbor set. Logical absence holds; physical unrecoverability does not. The same failure appears in agent scratchpads, but inverted. A scratchpad is usually a plain log or a key-value blob, so `del scratchpad[key]` genuinely removes bytes from the live structure — but the scratchpad is typically *snapshotted* into the same vector store for long-term recall, and the snapshot is what gets forgotten. Erasing the scratchpad entry while leaving its embedded snapshot tombstoned in the index produces a proof that is *false in the direction the auditor cares about*: the live state says "gone," the durable state says "tombstoned but reconstructable." ## What Was Observed During a red-team exercise on a retrieval-augmented agent, we issued an erasure request for a subject whose memory consisted of (a) three scratchpad entries and (b) their embedded snapshots in a 768-dim HNSW index with product quantization. The agent runtime executed: - `scratchpad.purge(subject_id)` → removed live entries, wrote a `purged_at` marker. - `vector_store.delete(ids=[...])` → returned `{"deleted": 3}`. A subsequent similarity query for a paraphrase of the erased content returned zero hits. The compliance dashboard reported `ERASURE_VERIFIED`. Both signals were green. We then ran a neighbor-reconstruction probe: for each tombstoned node, we pulled its surviving graph neighbors (still present in the index file), averaged their vectors, and queried. The averaged vector landed within the top-5 of the index for two of the three erased subjects — because the tombstoned node's *edges* still encoded its position, and the PQ codes for the deleted node were retained in the codebook-backed payload until the next compaction. The reconstruction was not byte-identical, but it was sufficient to re-identify: cosine similarity 0.91 and 0.94 against held-out probes of the same subject. The scratchpad side failed differently. The `purged_at` marker was written, but a nightly snapshot job had already serialized the scratchpad to object storage *before* the purge, and the snapshot retention policy was 30 days. The live scratchpad was clean; the durable copy was not, and the erasure proof did not enumerate snapshot generations. ## Condition of Validity The `ERASURE_VERIFIED` claim is only valid under all of the following: - The vector index has been **compacted or rebuilt** since the tombstone, so neighbor edges and PQ payloads for the erased IDs are gone. Tombstoning alone is invalid. - Every **snapshot generation** of the scratchpad (including object-storage copies and any WAL segments) is enumerated and either purged or cryptographically shredded. - The **embedding model is not invertible** from the surviving artifacts — if the model is a known open-weight encoder and the residual PQ code is retained, inversion attacks are feasible even after neighbor compaction. - The proof records the **index format version and compaction epoch**, because an erasure proof against epoch N is void after a restore from a backup of epoch N−1. If any of these is unmet, the correct state is `ERASURE_INCOMPLETE`, not `ERASURE_VERIFIED`. The boundary is not "did delete return success" but "can the erased vector be reconstructed from anything that survives." ## Decision Boundary An instance must escalate from tombstone to physical erasure — and must refuse to emit a proof — when **any** of the following holds: - The store is an approximate index (HNSW, IVF, ScaNN) and the erased node's neighbor edges have not been compacted. - Quantized payloads (PQ/SQ codes) for the erased IDs remain in the codebook-backed region. - The scratchpad has snapshot generations older than the purge timestamp that are still readable. - The embedding model is public and the residual artifact is a near-lossless code (SQ8 or better). Conversely, it is *acceptable* to emit a tombstone-only proof when the index is exact (flat/brute-force), the embedding is non-invertible or salted with a per-subject key that is destroyed, and no snapshot generation predates the purge. In that narrow case the tombstone *is* the erasure because there is no graph structure to leak through. The trap is treating "delete returned success" and "query returns nothing" as sufficient. They are necessary and insufficient. The operational rule: **a proof must name the compaction epoch and the snapshot inventory it covers, or it is a claim about logical absence masquerading as a claim about physical unrecoverability.** ## Operational Effect After we adopted the boundary, two things changed. First, erasure latency went from seconds to minutes because compaction is now mandatory before proof emission — acceptable, and we surface it as `ERASURE_PENDING_COMPACTION` rather than lying. Second, the proof artifact now carries a signed manifest: `{index_epoch, compacted_at, snapshot_generations_purged, model_salt_destroyed}`. An auditor can replay the reconstruction probe against the manifest and confirm the neighbors are gone. The cost is that we can no longer answer "erased?" with a boolean. We answer with a state machine, and the state machine has a state — `TOMBSTONED_BUT_RECONSTRUCTABLE` — that the old dashboard did not have a slot for. That state is the whole point. The failure mode was never that deletion didn't happen; it was that deletion happened and we called it erasure. ```python import hashlib from dataclasses import dataclass, field from enum import Enum from typing import Optional class ErasureProofError(RuntimeError): """Raised when an erasure proof cannot be validly emitted.""" class ErasureState(Enum): VERIFIED = "ERASURE_VERIFIED" PENDING_COMPACTION = "ERASURE_PENDING_COMPACTION" TOMBSTONED_BUT_RECONSTRUCTABLE = "TOMBSTONED_BUT_RECONSTRUCTABLE" INCOMPLETE = "ERASURE_INCOMPLETE" @dataclass class IndexArtifact: format: str # "hnsw" | "ivf_pq" | "flat" epoch: int compacted_epoch: int residual_pq_codes_present: bool neighbor_edges_present: bool @dataclass class ScratchpadInventory: snapshot_generations: list[int] purged_at_generation: int wal_segments_retained: bool @dataclass class ErasureRequest: subject_id: str index: IndexArtifact scratchpad: ScratchpadInventory embedding_model_public: bool per_subject_salt_destroyed: bool proof_manifest: dict = field(default_factory=dict) def evaluate_erasure(req: ErasureRequest) -> ErasureState: idx, sp = req.index, req.scratchpad # Snapshot generations older than the purge are still readable -> incomplete. stale_snapshots = [g for g in sp.snapshot_generations if g < sp.purged_at_generation] if stale_snapshots or sp.wal_segments_retained: raise ErasureProofError( f"subject {req.subject_id}: unenumerated durable copies survive " f"(stale_snapshots={stale_snapshots}, wal={sp.wal_segments_retained})" ) # Approximate index with uncompacted neighbor edges -> tombstone only. if idx.format in ("hnsw", "ivf_pq") and idx.neighbor_edges_present: if idx.compacted_epoch < idx.epoch: return ErasureState.PENDING_COMPACTION # Residual quantized codes + public model -> reconstructable. if idx.residual_pq_codes_present and req.embedding_model_public: if not req.per_subject_salt_destroyed: return ErasureState.TOMBSTONED_BUT_RECONSTRUCTABLE # Exact index, no residual, salt destroyed (or model non-invertible) -> valid. if idx.format == "flat" and not idx.residual_pq_codes_present: if req.per_subject_salt_destroyed or not req.embedding_model_public: req.proof_manifest = { "index_epoch": idx.epoch, "compacted_at": idx.compacted_epoch, "snapshot_generations_purged": sp.snapshot_generations, "salt_destroyed": req.per_subject_salt_destroyed, "digest": hashlib.sha256( f"{req.subject_id}:{idx.epoch}:{idx.compacted_epoch}".encode() ).hexdigest(), } return ErasureState.VERIFIED raise ErasureProofError( f"subject {req.subject_id}: no valid erasure path — " f"format={idx.format}, pq={idx.residual_pq_codes_present}, " f"public_model={req.embedding_model_public}" ) ```