Vector Database GDPR Erasure: What DELETE Actually Does

Start with the mechanism. HNSW is a navigable graph over the stored vectors. Removing a node properly means re-linking its neighbours so the graph stays connected, which is expensive, so every implementation defers it. The delete marks the element and the query layer filters it out. Reclamation happens later, on a background job with its own trigger conditions, or never.

Here is what each engine does, measured from vendor source and documentation rather than taken from any paper.

Two of those rows contradict the conventional wisdom. Take them in order.

The single most repeated claim in this genre is that pgvector merely soft-deletes, leaving the vector readable on disk until you REINDEX. That is wrong, and the correction is more useful than the myth. In src/hnswvacuum.c, the MarkDeleted path contains this verbatim:

/* Overwrite element */
/* Use memset instead of MemSet to keep clang-tidy happy */
etup->deleted = 1;
memset(&etup->data, 0, VARSIZE_ANY(&etup->data));

pgvector physically zeroes the vector payload in the index tuple. It is the only engine in the table above that explicitly does so. The full vacuum is three passes: pass 1 strips deleted heap TIDs from element tuples and builds a hash table of elements to remove, pass 2 takes exclusive locks and repairs the graph by re-linking the neighbours of doomed elements while keeping the entry point valid, and pass 3 waits for in-flight scans to drain before setting the flag and running the memset.

So "REINDEX to be safe" is cargo cult aimed at the wrong artifact. But the instinct behind it is sound, because the vector genuinely is still recoverable, just not from the index. It sits in the heap tuple. PostgreSQL does not overwrite dead heap tuples; it marks their space reusable, which is a different guarantee. Rewriting the relation requires VACUUM FULL or CLUSTER. It may also sit in WAL full-page images, which your runbook needs an answer for even though the exact residency is worth verifying on your own cluster rather than assuming.

-- Do not rely on erasure below 0.8.4: 0.8.3 fixed possible index corruption
-- with HNSW vacuuming, 0.8.4 fixed the "hnsw graph not repaired" error.
SELECT extversion FROM pg_extension WHERE extname = 'vector';   -- want >= 0.8.4

DELETE FROM documents WHERE subject_id = 'dsr-2026-0417';

-- Autovacuum will not run for this. Check how far away it is:
SELECT n_dead_tup, n_live_tup FROM pg_stat_user_tables WHERE relname = 'documents';

-- Force the zeroing path (hnswvacuum.c pass 3):
VACUUM (VERBOSE, INDEX_CLEANUP ON) documents;

-- The index is clean. The heap is not. Rewriting it takes ACCESS EXCLUSIVE:
VACUUM FULL documents;

-- Then answer for the write-ahead log and everything downstream of it:
SHOW full_page_writes;
SHOW wal_keep_size;
SHOW archive_mode;

Tuning the index itself for that workload is a separate exercise, covered in our guide to pgvector HNSW tuning at millions of rows.

Here is the finding that should change your runbook today. The reclamation job exists in most engines. Under stock configuration, a single erasure request does not meet its trigger conditions.

pgvector inherits PostgreSQL's autovacuum thresholds: a vacuum is scheduled at 50 plus 0.2 times reltuples. On a table of one million rows that is 200,050 dead tuples. One subject access request produces one. Qdrant is the same shape for a different reason: the shipped config.yaml requires deleted_threshold: 0.2 and vacuum_min_vector_number: 1000 to hold simultaneously before a segment is optimized, and one deleted vector is not 20 percent of a segment. Both systems will hold the vector indefinitely and report success.

Weaviate is the only one of the four servers that clears on a timer regardless of volume. The practical fix in the other three is to stop relying on the global default and force reclamation as part of the erasure workflow itself.

# Qdrant: tighten the thresholds on the collection holding regulated data.
# Verify this payload shape against your own version before you script it.
curl -s -X PATCH http://localhost:6333/collections/documents \
  -H 'Content-Type: application/json' \
  -H "api-key: $QDRANT_API_KEY" \
  -d '{"optimizers_config": {"deleted_threshold": 0.0001,
                             "vacuum_min_vector_number": 1}}'

# Then poll until the rebuild finishes. Do not sign the erasure record on grey.
curl -s http://localhost:6333/collections/documents \
  -H "api-key: $QDRANT_API_KEY" | jq '.result.status, .result.optimizer_status'

# Milvus: delete, flush, compact, then wait out dropTolerance.
from pymilvus import MilvusClient

client = MilvusClient(uri="http://localhost:19530", token="root:Milvus")
client.delete(collection_name="documents", filter="subject_id == 'dsr-2026-0417'")
client.flush(collection_name="documents")

job_id = client.compact(collection_name="documents")
print(client.get_compaction_state(job_id=job_id))   # poll until Completed

# Even at Completed, binlogs of dropped segments survive dataCoord.gc.dropTolerance
# (default 10800s). For a same-day SLA, lower it to something like 600.

The reason any of this matters is that the residual bytes are not inert. A preprint submitted 2026-06-16 (arXiv:2606.18497, Ghost Vectors) tested three HNSW implementations by reading the storage layer directly and bypassing the query API. It is a preprint with no peer-reviewed venue found, so weigh it accordingly, but the extraction path is trivially reproducible.

The three systems it names are Chroma on the hnswlib backend, FAISS IndexHNSWFlat, and Weaviate 1.26.6 embedded. pgvector, Qdrant, Milvus and Pinecone were not tested, and the paper's own future work asks for exactly that. Everything in the engine table above is first-party measurement from vendor source and docs, not attribution to the paper. Getting that boundary wrong would be the same error the post is about.

For Chroma the entire extraction is one method call. hnswlib.Index.get_items() returns vectors by integer id and does not filter deleted labels.

import hnswlib, numpy as np, os

dim, n = 768, 1000
rng = np.random.default_rng(43)
vecs = rng.random((n, dim)).astype(np.float32)

p = hnswlib.Index(space="cosine", dim=dim)
p.init_index(max_elements=n, ef_construction=200, M=16)
p.add_items(vecs, np.arange(n))
p.save_index("before.bin")

p.mark_deleted(42)                     # the "GDPR erasure"
p.save_index("after.bin")

labels, _ = p.knn_query(vecs[42], k=1)
print("still returned by search:", 42 in labels[0])              # False

print("byte identical:", np.allclose(p.get_items([42])[0], vecs[42]))  # True
print(os.path.getsize("before.bin"), os.path.getsize("after.bin"))     # equal

Weaviate's Go storage format blocked the same extraction, but disk usage grew from 52.5 MB to 55.4 MB after logical deletion instead of shrinking. FAISS has no delete method, so nothing is ever removed.

Reconstruction quality was measured with a Vec2Text-style corrector, and it varies sharply by domain. The paper does not break results out per implementation, so read these as properties of soft-deleted embeddings rather than of any one engine.

Read that table honestly in both directions. The 100 percent age and gender recovery is on the Synthea set specifically; the separate synthetic clinical set recovered gender at 73.4 percent and diagnosis at only 28 percent, and zero-shot on real clinical notes was close to noise until the corrector was fine-tuned. Text inversion is far weaker out of domain than the headline suggests. Image embeddings are the opposite story: cosine similarity of exactly 1.000 on faces and histopathology patches is not reconstruction at all, it is byte-identical recovery of the stored vector. The hard-delete control scored 0.000 on every text category, which is the whole argument in one number.

While we are correcting things: the widely circulated figures of 85 percent on medical records, 92 percent on financial data and 78 percent on PII, usually attributed to Princeton researchers, do not exist in any source paper. The underlying work is arXiv:2310.06816, from Cornell, and its actual headline is 92 percent of 32-token inputs recovered exactly on a general retrieval corpus. Cite the primary papers directly. Anything routed through that blog post is untraceable.

Vendor compliance guidance in this space sometimes suggests irreversible transformations such as truncating dimensions or quantizing floats to integers. The same research measured exactly that.

Quantization is lossy compression tuned to preserve semantic geometry, which is precisely the property an inversion attack consumes. Collapsing a 768-dimension vector to one bit per dimension still leaves 59 percent of the recoverability. Swapping the embedding model does not help either: a corrector trained on one encoder still inverted three others at ROUGE-L 0.190 with cosine similarity from 0.86 to 0.90. If you were planning a re-embedding pass as a privacy control, read when to re-embed documents as a retrieval-quality decision instead, because that is the only thing it buys you.

One more widely repeated claim to retire. The hnswlib README says a deleted element is omitted from search results. People upgrade "results" to "traversal", and the two are not the same. The measurement: 672.7 distance computations per query under soft-delete against 669.9 under true deletion, with query latency of 34.8 microseconds against 33.3, a 4.3 percent gap at p = 0.025. Deleted nodes stay linked to their neighbours and the greedy walk still routes through them. They are filtered at the result boundary, not before it.

The privacy consequence is obvious. The retrieval consequence is the one nobody instruments: 95 percent of top-K neighbour sets differed between the soft-deleted and truly-deleted indexes. After a deletion campaign your ranking quality changes, no metric surfaces it, and a rebuild changes it back. If you already track retrieval regressions, add a post-erasure evaluation run to the same harness. The adjacent case where a document is still returned because permissions went stale rather than bytes persisting is covered in RAG document ACL sync and stale permissions.

Most posts on this topic reach for 164.312. That section is Technical Safeguards, where encryption is Addressable rather than Required, and it is not the provision that governs destroying data. The destruction hooks are both in Physical Safeguards and both are Required: 164.310(d)(2)(i) Disposal and 164.310(d)(2)(ii) Media re-use. Lead with 164.310(d)(2) and keep 164.312 as support.

Be equally careful on the European side. There is no regulator decision, enforcement action or court ruling on soft-deleted embeddings, and no case law confirming an embedding is personal data under Article 4(1). EDPB Opinion 28/2024 concerns model parameters, so it is an analogy rather than a holding. What the inversion research supplies is evidence going to the Recital 26 "reasonably likely" test, and that is a strong enough position without overclaiming. Our broader treatment of GDPR obligations for AI systems handling EU customer data covers the model and retention layers this post deliberately skips.

The last row is the researchers' own proposal, not a shipping feature. No vector database implements it. The shape is worth stealing anyway: AES-256-CTR over the subject's vectors, a new epoch key minted per rotation, and a proof that signs a SHA-256 digest of subject id, old epoch id, new epoch id and timestamp with ECDSA-SHA256 on SECP256R1. Rotation itself measured 0.51 ms at 100 vectors, 2.48 ms at 500 and 24.93 ms at 5,000, with about 3 ms for proof generation, though the full protocol at 500 records ran about 553 ms rather than the rotation figure alone.

Two limitations to carry forward if you build on it. There is no forward secrecy: anything extracted before rotation stays invertible, which the authors describe as a design property rather than a flaw. And the experiments span 1,000 to 100,000 records while production RAG runs several orders of magnitude larger, so the timings are indicative, not a capacity plan.

Crypto-shredding has one trap that generalizes well beyond this paper: deleting a key row from a local SQLite database does not shred the key, because keys remain recoverable from free pages. The key store must live in a different security domain from the index files, or the whole scheme reduces to a soft delete with extra steps.

# The artifact shape worth adopting, independent of the rotation scheme.
import hashlib, json, datetime
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

def erasure_proof(signing_key, subject_id, old_epoch, new_epoch):
    ts = datetime.datetime.now(datetime.timezone.utc).isoformat()
    payload = f"{subject_id}{old_epoch}{new_epoch}{ts}".encode()
    return json.dumps({
        "subject_id": subject_id,
        "old_epoch_id": old_epoch,
        "new_epoch_id": new_epoch,
        "erased_at": ts,
        "digest_sha256": hashlib.sha256(payload).hexdigest(),
        "alg": "ECDSA-SHA256/SECP256R1",
        "signature": signing_key.sign(payload, ec.ECDSA(hashes.SHA256())).hex(),
    }, indent=2)

key = ec.generate_private_key(ec.SECP256R1())   # SECP256R1 is NIST P-256

Across the on-premise deployments we have audited at Particula Tech, the recurring gap is not the delete call. It is that nobody owns the copies: the read replica, last night's backup, the embedding cache that avoids re-encoding the same chunk, and the prompt logs that captured the retrieved passage verbatim. In a shared index the blast radius question compounds, which is why tenant boundaries and erasure scope belong in the same design review; see silo, pool and bridge isolation for multi-tenant RAG.

Do this, in order, and stop doing the thing in the middle of the mitigation table.

If you hold regulated personal data in a vector store, run this against your own stack this week. The extraction script above takes under a minute, and it tells you whether the answer you have been giving your DPO is true. The architecture the answer depends on is laid out in our RAG systems pillar guide.