How to Prove You Deleted a User From a Vector Database

Deleting a user from a vector database is not the same operation as deleting a row from a relational database, even though most engineering teams treat it that way. A vector is derived data: it can outlive the document, message, or record it came from, and destroying the source does nothing to the copy that got embedded and indexed. That mismatch is the entire subject of this piece, and it matters because "we deleted the user" is a legal claim now, not just a technical one.

Engineers carry an intuition from relational systems that a DELETE statement, paired with an audit-log entry, equals erasure. That instinct is not wrong for a relational database. It is wrong for an AI pipeline, where the same user's data fans out across multiple distinct locations, training corpora, fine-tuning sets, retrieval indexes, logs, caches, and more, far beyond a single deletion target (per tianpan.co). Deleting the source documents and the user's auth record makes the job look done. But the vector database still holds embeddings of that user's emails, chunks that mention their name, and context in which they participated, often with no direct identifier tying those vectors back to the person at all (per Twig).

That is the crux of it: an embedding is derived data that lives independently of the object it came from. Removing the source document leaves the vector sitting there, untouched, still searchable, still leaking whatever it was built to represent. The rest of this piece works through why that happens inside the index itself, what an attacker can pull out of a vector that was supposedly deleted, and what it actually takes to prove, in a way a regulator would accept, that a user is gone. Along the way, three terms are going to do a lot of work: soft-delete, hard-delete, and epoch key rotation. Keep them straight, because the difference between them is the difference between a compliance answer and a compliance liability.

How soft-delete works inside HNSW indexes and what it leaves behind

Most production vector databases built on a graph-based approximate nearest neighbor index, including ChromaDB and Weaviate, handle deletion by flipping a metadata flag on the record. FAISS offers only limited deletion support and is not designed to remove vectors in a way that reliably clears them from the index (per Ghost Vectors paper, Chakraborttii et al., Trinity College). None of these systems, by default, remove bytes from disk when a delete call comes in.

The API response looks clean. A query for that user's data returns nothing, the delete call returns success, and the dashboard shows a record was removed. But the raw binary index file on disk is physically unchanged. In ChromaDB specifically, that means files like data_level0.bin, along with header.bin, length.bin, and link_lists.bin, still contain the full vector alongside its original graph connections. An adversary with storage-layer access, someone who can read the disk directly rather than going through the API, can pull those "deleted" vectors out using functions like get_items() and feed them straight into an inversion model. That bypasses every access control the API layer was supposed to enforce, because the control was never applied to the storage layer in the first place.

The threat isn't bounded by time, which makes this worse than a simple oversight. A backup snapshot taken before the API delete call and one taken after produce identical reconstruction quality, ROUGE-L scores of 0.207 in both cases, according to the Ghost Vectors paper. So the timing of when a backup was made offers no protection at all. And this isn't a small-index quirk either. Testing across index sizes from 1,000 vectors up to 100,000, the variance in reconstruction quality stayed at just 0.016; the vulnerability holds steady as systems scale into production-sized deployments.

Calling a delete API is not evidence that data was erased. Calling a delete API is not evidence that data was erased. It is evidence that a suppression flag got set somewhere in a metadata field. Those are two very different claims, and only one of them would survive a forensic audit.

What an attacker can reconstruct from a "deleted" embedding

Embeddings were never designed to be one-way. That's an assumption a lot of engineering teams carry over from hashing, where you assume you can't reverse a cryptographic hash digest back into the original input. Vectors don't work that way. They're lossy, sure, information gets compressed and some of it genuinely disappears, but lossy is not the same as irreversible, and the gap between those two ideas is where the risk lives.

The leading technique for closing that gap is Vec2Text (Morris et al., 2023), which uses iterative refinement, essentially controlled generation that repeatedly guesses text, re-embeds the guess, and compares it against the target vector, tightening the guess each round. On 32-token inputs, Vec2Text recovers original text with startling fidelity: up to 92% exact recovery, BLEU scores above 97, and name-level recovery rates of 94% for first names, 95% for last names, and 89% for full names in clinical data. Those aren't fragments or approximations. That's the original sentence, coming back out of a list of floating-point numbers.

The Ghost Vectors researchers applied Vec2Text directly to soft-deleted HNSW vectors, without any domain-specific fine-tuning, and the results varied by dataset but never landed anywhere reassuring. On a Wikipedia dataset of biographical entries for living persons, 25.5% of exact person names came back, along with 46.4% of geographic locations (ROUGE-L of 0.185, plus or minus 0.062). On NIH's Synthea clinical dataset, patient age and gender markers were recovered at 100%. Facial embeddings gave up top-1 identity matches 99% of the time. Histopathology image embeddings returned correct tissue classification 100% of the time.

One might argue that an attacker at least needs to know which embedding model generated the vector in the first place, since different models produce structurally different vector spaces. That defense doesn't hold either. Reconstructions transferred across structurally different surrogate models with cosine similarity between 0.86 and 0.90; an attacker can succeed without knowing the victim's exact embedding architecture. A newer method, ZSinvert (Zhang et al., 2025), pushes this further with zero-shot inversion that generalizes across architectures without needing per-encoder training the way Vec2Text does. The attack surface is not shrinking. It's broadening.

What about defenses like quantization or noise injection? Some defenses such as quantization or noise injection may lower reconstructability, but the underlying research does not show they eliminate the risk. The privacy risk persists in a weakened form, not an eliminated one.

That has a regulatory consequence that a lot of teams haven't fully absorbed yet. If a vector can be inverted into something identifying, a name, an age, a face, then the vector is personal data, full stop. "We only kept the embedding, not the original text" is not a de-identification argument anymore. And soft-deleting an embedding that can still be inverted is not erasure under any reasonable reading of that word.

Why vectors can't be found in the first place without identity-preserving metadata at ingestion

Here's a separate problem that compounds everything above: even wanting to delete a user's vectors doesn't guarantee finding all of them.

An embedding, on its own, carries no inherent link back to the person it came from. "Email from john.smith@example.com" becomes something like [0.234, -0.567, 0.891, ...], a string of numbers with no name attached, no email address, no user ID. Without metadata sitting alongside that vector, the only way to search for it is by semantic similarity, comparing meaning to meaning. That approach misses variations in phrasing, near-duplicate content, and, critically, third-party content that references the user without being authored by them: an email sent to the user, a comment about them, a collaborative document they edited but didn't write from scratch.

The fix sounds almost too simple. Store metadata alongside every vector at the moment it's created, something like { vector: [...], metadata: { user_id: "12345", document_id: "doc789", source: "email" } }. That structure turns deletion from a semantic search problem into a precise filter operation (per Twig).

But metadata tagging only solves half the problem, because GDPR's scope covers content that identifies a user even when someone else created it. A comment about the user, an email addressed to them, a shared document with their name in it: all of that falls under the same erasure obligation, and semantic search alone won't reliably find it. That's why lineage tracking is essential: every embedding, every fine-tune shard, every eval snapshot needs a back-reference to the human being it traces to (per tianpan.co). Skipping that step at ingestion turns a deletion request arriving under a 30-day legal deadline into forensic archaeology instead of a database query.

Platform capabilities vary here too. Pinecone supports delete by ID, delete by metadata filter, and batch deletion. Weaviate supports delete by filter and cascade deletion, though cross-reference cleanup behavior may still require attention at the application layer. One relational database with a vector extension uses standard SQL DELETE statements with full filtering support, since it's still that same relational database underneath. Chroma supports filter-based deletion through its where clause, though Twig notes this capability is more limited compared to the other platforms. Metadata tagging is necessary everywhere. What a platform lets you do with that metadata is not the same from vendor to vendor.

Once tagging is in place, the real question becomes which deletion mechanism to run against it. That's where the four strategies come in, and they do not all produce the same outcome.

Four deletion strategies and what each one can and cannot prove

The Ghost Vectors paper tested four approaches against 500 soft-deleted Wikipedia vectors, and the results draw a sharp line between strategies that suppress data and strategies that can prove they suppressed it. All figures below come from that paper unless noted otherwise.

Soft-delete is the default behavior described earlier: flip a metadata flag, leave the vector on disk. It's fast, essentially 0 milliseconds, because nothing physically moves. But PII recovery after "deletion" is ROUGE-L 0.207, identical to the unprotected baseline, because nothing was actually removed. It generates zero proof. An API returning 200 OK says nothing about the physical state of the index, and this approach does not satisfy GDPR Article 17's erasure requirement.

Full index rebuild re-indexes the entire dataset from scratch, excluding the deleted records this time. That takes roughly 2,250 milliseconds for the test set, meaningfully slower. And yet PII recovery after the rebuild comes back at ROUGE-L 0.207, again, identical to soft-delete. Why? Because an adversary who copied the binary index before the rebuild ran gets the same reconstruction quality regardless. The threat was never retroactive, so rebuilding after the fact does nothing to stop someone who already has a copy. This strategy is expensive and still generates no proof.

Per-record AES encryption with key destruction takes a different approach: encrypt each vector individually, then destroy that specific vector's key when a deletion request comes in. This one actually works, PII recovery drops to ROUGE-L 0.000, effectively suppressing the content entirely. It runs at about 8 milliseconds per record. But it still generates no auditable proof of deletion. Encryption confirms the data is inaccessible, technically, but there's no verifiable record that ties a specific deletion event to a specific outcome. It's also roughly 3.2 times slower than the fourth approach at scale.

Epoch key rotation is where the paper's results get interesting. Each user gets an independent epoch_id counter, and their vectors get encrypted with AES-256-CTR under a key tied to that epoch. When a deletion request comes in, the epoch key gets discarded and the counter increments. Any vector that was encrypted under the now-discarded key becomes computationally indistinguishable from random noise, and its ciphertext no longer preserves the semantic structure that inversion models like Vec2Text depend on. Speed is 2.5 milliseconds for 500 deleted vectors, about 0.005 milliseconds per record, with the full end-to-end process including proof generation running around 553 milliseconds. PII recovery drops to 0% in the paper's testing.

The part that sets this apart from the other three: it produces an ECDSA-SHA256 signed proof object, signed with the controller's private key using SECP256R1, and verifiable by anyone holding the registered public key. That's an auditable, tamper-evident record that a specific deletion event actually happened, not just a log line saying it did. The epoch key store needs to live in a separate security domain, a KMS or HSM, away from the HNSW binary itself. Otherwise an attacker with access to the index file alone could potentially recover the key too, and the whole scheme collapses.

That separation is also what lets this approach satisfy GDPR Article 5(2)'s accountability requirement: it destroys the cryptographic material needed to recover the data, and it generates a proof that can be independently checked, rather than just trusted on faith.

Laid out side by side, the comparison exposes something teams tend to conflate: "did you delete it?" and "can you prove you deleted it?" are two separate questions with two separate answers. Three of the four strategies answer the first question, at best. Only epoch key rotation answers both.

What a defensible audit trail for vector deletion contains

Not all evidence carries the same weight. An API returning 200 OK is self-reported: the system is simply asserting that it did the thing it was asked to do. A count query returning zero matching records is observable, someone can independently run that query and check. A cryptographic proof, verifiable against a public key, is the strongest of the three, because verifying it doesn't require trusting the system that generated it at all.

A defensible audit trail needs several of these elements layered together, not just one. The cryptographic ECDSA proof from epoch key rotation, described above, is one piece. Count queries run before and after deletion, confirming zero remaining records under a given user_id, are another, and they're the kind of check that can't be faked with a passing result if someone actually runs the query independently (per Twig). A tamper-evident deletion registry, a log that can't be silently edited after the fact, adds a third layer. The data lineage map from the earlier section, the record linking every vector back to its source document and originating user, underlies all of it; without it, no one can even confirm the scope of what should have been deleted in the first place.

Twig's research sketches out what a usable log entry looks like in practice: something like { user_id, deletion_requested (ISO timestamp), vectors_deleted (count), documents_deleted (count), completed (ISO timestamp), verified_by }. That's concrete enough for a regulator or a privacy oversight authority to actually interrogate, line by line, rather than accepting a vague assurance that "the data was removed."

The EDPB's own guidelines (05/2019) set the bar in two words: erasure has to be "verifiable and irreversible." Not one or the other. A log entry alone might demonstrate irreversibility without being independently verifiable. A verifiable proof that only covers part of the data footprint isn't irreversible in any meaningful sense either. The audit trail has to carry both properties at once. A single soft-delete flag was never going to be sufficient on its own.

None of this works as a one-time reconstruction exercise, either. Production-grade erasure depends on a data map that is maintained continuously from the moment data enters the pipeline, linking personal data across every database, embedding store, and cache it touches, not assembled retroactively when a deletion request lands on someone's desk (per research citing suhasbhairav.com). And GDPR adds notification obligations that are easy to overlook: controllers may be required to inform relevant recipients when personal data gets erased, subject to proportionality considerations. A complete audit trail records that outward notification too, not just the internal deletion event.

The vector database is one layer, the rest of the AI stack also holds the user

Everything above concerns one of seven locations where a user's data can end up: training corpus, fine-tuning sets, RLHF preference data, chat logs and telemetry, evaluation datasets, the retrieval index, and derived caches (per tianpan.co). Get the vector index handling exactly right, with epoch key rotation, signed proofs, a full lineage map, and the other six locations sit there completely unaffected. A user "deleted" from the retrieval index can still be sitting fully intact in an eval dataset from six months ago.

That reality points toward a three-tier response, and each tier accomplishes something different from what it merely buys time for.

The first tier is immediate suppression: add the user to a blocklist, filter their records out of retrieval at query time. This can happen within minutes, and it buys breathing room against the one-month deadline that Article 12(3) sets for responding to erasure requests. But it doesn't discharge the underlying obligation. The data is still there. The model parameters, if anything derived from that data was used in training, are unchanged. Suppression stops the bleeding; it doesn't close the wound.

The second tier is pipeline deletion: physically removing the data from every store it touches. This is the honest baseline, the version of "deletion" that actually matches what the word implies, and the vector index work covered in the earlier sections is the hardest single piece of this tier to get right.

The third tier, machine unlearning or targeted retraining, only becomes necessary when a model's parameters have actually memorized something from the user's data, not just retrieved it at query time. That's a meaningfully different problem, and it remains an active area of research rather than a solved, off-the-shelf product feature. It should be reserved for cases where the memorization risk is real and where regulators or genuine risk exposure demand it, not treated as a routine step for every deletion request.

The EDPB's Opinion 28/2024 on AI systems, adopted in December 2024, speaks directly to this tier. It states that the right to erasure, when applied to AI, requires reversing the model's memorization of personal data, which breaks into two distinct requirements: deleting the personal data that was used as training input, and separately, removing that data's influence on the model's parameters. Those are not the same task. Deleting the input data doesn't automatically undo what the model learned from it. Unlearning is treated as its own discipline rather than an extension of database deletion.

And the field is starting to build the same kind of verification apparatus for unlearning that Ghost Vectors built for vector indexes. Research has proposed what's described as the first practical, general-purpose auditing framework for machine unlearning, framed under the label "proof of ignorance" (arXiv:2606.16110). The parallel to epoch key rotation's signed proofs is not a coincidence. Across every layer of the AI stack, the industry is converging on the same conclusion: deletion that can't be verified isn't deletion a regulator, or a user, has any real reason to trust.