Verifiable Deletion of Personal Data From Vector Databases

A DELETE call against a vector database removes a pointer, not the personal data underneath it. That gap between what an API confirms and what a storage engine actually does is the subject of this piece: how soft deletion works in HNSW indexes, what a 2026 recovery study found when researchers went looking for supposedly erased vectors, what regulators mean when they demand "erasure," and why fixing the problem takes more than a stricter delete function.

DELETE calls on a vector database versus actual deletion

Most engineers carry a simple mental model of deletion from relational databases: issue a DELETE statement, the row disappears, the audit log records the transaction, and compliance is satisfied. That model holds up reasonably well in a single-table world. It falls apart almost immediately in an AI pipeline, because a person's data rarely lives in just one place by the time anyone asks for it to be removed.

Consider what happens to a single user's data inside a typical retrieval-augmented generation (RAG) system. It can land in the training corpus, in fine-tuning sets, in RLHF or preference data used to shape model behavior, in chat logs and telemetry, in evaluation or "golden" datasets used to benchmark model quality, in the vector retrieval index itself, and in derived caches, things like semantic caches, prompt caches, or materialized retrieval snapshots that exist purely to make the system faster. That is six or seven distinct stores, each one populated by copies or transformations of the original record, not by the record itself.

Deleting the source row changes exactly one of those stores. The rest sit untouched, physically intact, and under most regulatory definitions, still constitute active processing of personal data. Anyone deciding the DELETE call was sufficient needed to first map where the data went. It's whether anyone mapped where the data went before deciding the call was sufficient.

How HNSW soft delete works at the storage layer

HNSW, short for Hierarchical Navigable Small World, is the indexing architecture behind most of the vector databases in production use today. It organizes embeddings into a graph of layers so that nearest-neighbor search can skip through the space efficiently instead of scanning every vector. That efficiency is the whole point of the architecture, and it's also the reason deletion inside it is structurally awkward.

When a vector database performs what it calls a delete, it typically flips a metadata flag on that entry. Future queries check the flag and skip the entry, so from the application's perspective, the record has vanished. But the raw vector bytes never leave the index file on disk. They stay exactly where they were written, physically unchanged, sitting in the same graph structure that other, still-active vectors depend on for traversal.

Physical removal only happens during segment compaction or a full index rebuild, operations that rewrite the underlying files and actually drop the flagged entries. Those events aren't continuous. They might run on a schedule, they might require an operator to trigger them manually, or in a long-lived index that never gets rebuilt, they might never happen. So there's a real gap between "the application says it's gone" and "the storage layer has done anything about it," and that gap can persist indefinitely if nobody forces compaction to run.

What the Ghost Vectors paper found about recoverable embeddings

That gap stopped being theoretical in 2026. A paper titled "Ghost Vectors: Soft-Deleted Embeddings Remain Reconstructible in HNSW Vector Databases" (arXiv:2606.18497), submitted June 16, 2026 by Chakraborttii, García Alvarado, Abdulofizova, and Dwivedi of Trinity College, tested how much information survives a soft delete. The method: pull the raw vector bytes straight out of an HNSW index file after a soft delete, then run Vec2Text inversion against them, with no domain-specific fine-tuning, across three independent HNSW implementations.

The recovery rates show how much survives. On a Wikipedia dataset of biographical entries for living persons, inversion recovered exact person names 25.5% of the time and geographic locations 46.4% of the time. On NIH Synthea, a structured clinical dataset, the recovery rate for patient age and gender markers hit 100%. Histopathology image embeddings from PathMNIST yielded 100% tissue classification accuracy, and facial embeddings produced 99% top-1 identity recovery.

Text reconstruction quality swung depending on the dataset, which makes sense: some embeddings encode messier, more ambiguous information than others. But one finding held constant across every dataset and all three tested systems: the underlying vector itself was always still there, physically present, waiting to be read. As inversion models improve, today's 25.5% on a hard case starts to look like a floor, not a ceiling.

What regulators require when they say "erasure"

Article 17 of the GDPR grants individuals the right to erasure when their data is no longer necessary for the purpose it was collected, when they withdraw consent, or when the data was processed unlawfully. Organizations are obligated to comply "without undue delay," which regulators have consistently interpreted to mean the deletion has to be both timely and actually effective. Not a placeholder. Not a query filter. Effective.

A coordinated body of regional privacy regulators made that distinction concrete in March 2025, when thirty national Data Protection Authorities plus the European Data Protection Supervisor ran a coordinated enforcement action focused specifically on the right to erasure. It was, to date, the clearest signal that Article 17 compliance inside AI systems is being examined directly rather than assumed. Then on October 14, 2025, the EDPB announced that its coordinated enforcement action for 2026 would again focus on the right to erasure. Two consecutive years targeting the same right is a pattern. It's a pattern, and patterns tend to mean sustained scrutiny rather than a passing check.

The EDPB has also been specific about the suppress-versus-erase distinction: suppressing a record from query results is not, on its own, erasure. The regulatory standard is that deletion has to be verifiable and irreversible. A soft-deleted vector sitting untouched in an HNSW index file, recoverable through inversion as the Ghost Vectors paper demonstrated, is the textbook case of suppression being mistaken for erasure.

Deletion also needs to account for what remains inferable, not just what is physically present

Physical removal solves half the problem. What about the half where the data is gone but its effects on everything around it aren't?

Research out of UC Irvine and HPI (arXiv:2604.00326) makes the case that deletion needs a privacy guarantee bounding what remains inferable, not just a guarantee about what's logically or physically removed. That's a meaningfully higher bar. It means asking not "is the record still there" but "can someone reconstruct the record, or something close enough to it, from what's left."

The paper identifies two distinct leakage channels. The first is leakage from the post-deletion state: what the system still exposes even after the target record is gone. The second, less obvious channel is leakage from the deletion pattern itself, the act of deleting something can signal what used to be there.

The paper's own example makes this concrete. Deleting a salary field while leaving team, title, level, and manager intact makes the salary re-inferable through ordinary functional dependencies among those remaining fields. The record technically no longer contains the salary. The information content of the record hasn't actually shrunk. And that creates an awkward secondary problem: if a deletion mechanism tries to close that gap by also deleting the auxiliary fields (team, title, level), the specific pattern of what got deleted alongside the salary can itself reveal that a salary value was being hidden. The deletion footprint becomes a side channel. Erasing more to prevent inference can, paradoxically, leak the fact that something sensitive needed erasing.

The layered technical approaches that together constitute verifiable deletion

There isn't a tool that, deployed once, satisfies Article 17 across a training corpus, a vector index, a semantic cache, and a chat log simultaneously. The right posture is layered, matched to where the data physically sits and what kind of guarantee the situation actually requires.

A practical sequencing framework treats deletion as suppress, then delete, then, in narrower cases, unlearn. Suppression comes first because it's fast: adding an entry to a blocklist or query-time filter can stop exposure within minutes, buying time against a legal deadline while the real remediation catches up. But suppression alone leaves the data physically intact, so it's a stopgap, not a resolution. Deletion from every pipeline store is the actual remediation work, reaching the vector index, any keyword or lexical index running alongside it, semantic caches, conversation history logs, evaluation sets, and system logs. Reaching every one of those stores is the unglamorous, multi-system labor that confirms a deletion request was actually honored. Machine unlearning, the technique of retraining or fine-tuning a model to remove the influence of specific training examples, is typically the most resource-intensive step and applies when the model's parameters themselves need to forget, since it's costly and not always necessary.

None of that sequencing works, though, without knowing where a given user's data actually went. Metadata-tagged ingestion, tagging every vector with a user or document ID at the moment it's created, and propagating that tag through every derived artifact, turns a deletion request from forensic archaeology into a fan-out query. Without that lineage, someone has to reconstruct, under legal deadline pressure, which caches and indices might contain traces of a person's data. With it, the system can just ask each store directly.

At the storage layer, physical compaction or a full index rebuild is the baseline operation that makes a soft delete physically real, rewriting the HNSW index so flagged vectors are actually absent from the file rather than just hidden from queries. It's expensive to run at scale, and compaction proves the vector is gone in the sense that a compliance team can point to it, but it doesn't produce anything like a cryptographic proof of erasure. It's a mechanical fix, not a mathematical guarantee.

Agentic AI pipelines make the deletion surface harder to bound

Everything above assumes the data has a boundable set of locations. Agentic AI systems strain that assumption, because an agent equipped with a memory layer can retain what it learned about a person across sessions, write that into a vector store on its own initiative, or pass it to another agent downstream in a multi-agent pipeline, often with no independent access check happening at that handoff point.

That creates a genuinely awkward duplication: sensitive information about a person can end up living in two categorically different places at once, inside a model's own parameters (through fine-tuning or RLHF) and inside external memory stores, indices, generated summaries, embeddings, caches, that the model or its agents built up independently. Deleting from one doesn't touch the other, and an agent that summarized a now-deleted conversation may have written that summary into a store nobody flagged for review.

Agentic systems sit uneasily inside existing GDPR frameworks for controllers and processors, frameworks that were not designed with autonomous agents in mind. What changes is the degree of autonomy involved, agents making their own decisions about what to store, summarize, or forward, decisions that happen without a human in the loop checking each one against a deletion request that hasn't been filed yet. That autonomy makes the deletion surface hard to bound in advance: the map of where a person's data might end up isn't fixed at design time, it's being drawn continuously by the agents themselves as they operate.