Your Vector Database delete() Didn't Delete

What Your Vector Database delete() Actually Does

Start with the honest answer, because most write-ups on vector database deletion never get to it: in an HNSW-backed store, delete() is a visibility operation, not a storage operation. It marks the record and hides it from queries. The vector itself stays in the segment file until something else — a compaction job — decides to rewrite that file.

Qdrant's own documentation says so plainly: “Qdrant does not delete entries immediately after a query. Instead, it marks records as deleted and ignores them for future queries.” This is not a bug or a cut corner. Removing a node from a Hierarchical Navigable Small World graph means finding every neighbour that points at it and re-wiring their edges so the graph stays connected. That is expensive, so every serious engine defers it and batches it up later.

The consequence is the part nobody writes down. “Later” is not a promise — it is a threshold.

Deletion is a scheduler decision, not an API decision

Qdrant's vacuum optimizer runs on two conditions, both configurable and both with defaults most teams never open: deleted_threshold (default 0.2) — the minimal fraction of deleted vectors in a segment required to trigger optimization — and vacuum_min_vector_number (default 1000) — the minimal number of vectors a segment must hold to be considered at all.

Now put a real Art. 17 request through that. A customer asks you to erase their data. You find their seven chunks, you delete them, the API acknowledges. Those seven vectors live in a segment holding 200,000 others. The deleted fraction is 0.0035%. The threshold is 20%. The optimizer looks at that segment, decides there is nothing worth doing, and moves on — and it will keep deciding that until unrelated churn happens to push the segment past one fifth deleted. On a stable knowledge base, that day may never come.

A per-store reality check

The mechanism differs by engine, but the direction is the same. This is what you are actually dealing with:

• Qdrant — tombstones plus the vacuum optimizer described above. Good news: the thresholds are explicit, readable and per-collection, so this is one of the few stores where you can genuinely drive and observe compaction.
• Chroma — delete() updates the metadata in SQLite so queries skip the entry; the HNSW index file is not rewritten. A reported issue on v0.6.3 found that after deleting documents the database grew, with the retained content sitting in the embeddings_queue table “in the form of plain text and embeddings”. Index pruning has been an open feature request rather than a shipped guarantee.
• FAISS — there is no true delete for HNSW indexes at all. remove_ids is supported by index types like IndexFlat, IndexIVFFlat and IDMap (IVF needs its direct map enabled), but for HNSW the documented answer is to rebuild the index. FAISS is a library, not a database; erasure is your job, not its.
• Weaviate — deletes write tombstones that a periodic cleanup removes, governed by cleanupIntervalSeconds on the vector index and tuned with the TOMBSTONE_DELETION_CONCURRENCY and TOMBSTONE_DELETION_MIN_PER_CYCLE / MAX_PER_CYCLE environment variables. It runs on a clock you set, which is better than a threshold you forgot — but it is still not your delete call.
• pgvector — you inherit Postgres MVCC. DELETE makes the row a dead tuple; plain VACUUM makes the space reusable but does not hand it back to the OS; VACUUM FULL rewrites the table. The HNSW index additionally has to re-wire the graph around every removed node, which is what makes the maintenance expensive. See our vector database primer for why pgvector is usually the right default anyway.

What survives is not an anonymous number

A common reply at this point: fine, a float array lingers — so what? It is not readable text.

It is closer to readable text than that argument assumes. Morris et al. at Cornell showed with Vec2Text (“Text Embeddings Reveal (Almost) As Much As Text”, arXiv:2310.06816) that embeddings can be inverted by iteratively generating and re-embedding candidate text: they recovered 92% of 32-token inputs exactly, and pulled full names out of clinical notes.

In June 2026 that got aimed directly at this problem. “Ghost Vectors” (arXiv:2606.18497) tested three HNSW implementations and confirmed that soft-deleted vectors remain physically recoverable by reading the raw index files at the storage layer — bypassing the API entirely. Using Vec2Text with no domain-specific fine-tuning, they recovered 25.5% of exact person names and 46.4% of geographic locations from a Wikipedia biographies dataset, and hit 100% recovery of patient age and gender markers on structured medical data. So the residual is not noise. It is the person, slightly blurred, and readable by anyone with file access.

What the Regulator Assumes — and Where the Premise Breaks

Germany's Datenschutzkonferenz published its Orientierungshilfe zu datenschutzrechtlichen Besonderheiten generativer KI-Systeme mit RAG-Methode (Version 1.0, October 2025). On deletion, section 3.5 says:

Be fair to the DSK here, because the paper is careful elsewhere and the sentence is not wrong. Entries in a vector store are directly addressable — that is exactly the property that makes RAG more tractable than a fine-tuned model, and the DSK explicitly keeps its scepticism for the model, noting that the problems with deleting data from the language model itself remain regardless. Their framing of RAG as the more privacy-friendly architecture is sound, and we agree with it.

The break is narrower and more technical than “the regulator is wrong”. Addressability is an API property. Erasure is a storage property. The guidance describes a system where deleting an entry and removing the data are the same act — which is true of a row in a classical database and is not true of a vector in an HNSW segment. A controller who reads §3.5 literally will call delete(), document that the entry is gone from the index, and reasonably believe they are finished. They will be wrong, and nothing in the wording warns them.

If you want to argue the leftover vector no longer counts as personal data, you are not making a deletion argument any more — you are making an anonymity argument, judged against Recital 26 GDPR and “all the means reasonably likely to be used”. The EDPB's Opinion 28/2024 addresses trained models rather than vector stores, so it does not govern this case directly, but it shows how supervisory authorities apply that test: paragraph 43 requires the likelihood of extraction to be “insignificant” for any data subject, and a footnote counts extraction “with little or no use of the query interfaces” — precisely reading the index file off the disk. Against published inversion results, that is a hard case to make.

Meanwhile Art. 12(3) gives you one month to answer the request. Not one month plus however long until the segment happens to fill up.

How You Actually Delete

Force the compaction, then measure it

The pattern is the same everywhere: delete, force the rewrite, then read the storage layer back and confirm. Never assume the background job did it.

• Qdrant — delete the points, then make the segment qualify: any collection-update operation triggers the optimizers, and you can temporarily tighten deleted_threshold and vacuum_min_vector_number via the collection's optimizer config so a small deletion actually clears the bar. Read segment stats before and after; restore your normal thresholds afterwards.
• pgvector — DELETE, then VACUUM FULL if you need the table physically rewritten, and REINDEX the HNSW index. Be honest about the cost: VACUUM FULL takes an exclusive lock and rewrites the whole table, so this is a maintenance-window operation, not something you fire on request.
• Weaviate — the tombstone cleanup cycle is the mechanism; make sure its interval is short enough that a deletion is physically cleaned inside your response window, and that per-cycle limits are not quietly starving it on a large index.
• Chroma and FAISS — there is no forced-compaction path you should rely on. The defensible move is to rebuild the collection or index from source without the chunk, swap it in, and destroy the old files. Treat “rebuild” as the deletion procedure and budget for it.

What I would not do: set deleted_threshold to near-zero globally so “deletes always compact”. You will make the optimizer rewrite segments continuously on a busy collection and pay for it in latency and I/O forever, to serve a request you get a handful of times a year. Force it per request, prove it, put the thresholds back.

When you cannot force it: crypto-erasure

Where compaction cannot be forced — an append-only index, an immutable backup, a store that simply does not expose the knob — the fallback is to make the bytes useless instead of absent. Encrypt vectors under a key that belongs to an epoch or a data subject, and on erasure destroy the key. The Ghost Vectors authors implement exactly this as Epoch Key Rotation, measuring roughly 0.005 ms per record and reducing recovery of personal data to zero, while emitting a signed cryptographic proof of the deletion event.

The limits deserve saying out loud. Crypto-erasure is only as strong as your key custody: if a copy of the key survives in a key-vault backup, an escrow, or an old KMS snapshot, you have destroyed nothing and merely documented that you meant to. Key-per-epoch also gives you epoch granularity, not person granularity — erasing one subject means keying per subject, which costs you, or re-encrypting the epoch. And whether an authority accepts crypto-erasure as erasure rather than a security measure is not uniformly settled. Treat it as the answer where physical rewrite is impossible, not as the convenient default.

The surfaces everyone forgets

Compacting the live segment is the part people think about and the smaller half of the work. The copies are where Art. 17 requests actually go to die:

• Snapshots — a snapshot taken before the deletion contains the vector, complete and unmarked. Deleting from the live collection does nothing to it.
• Replicas — every node has its own segments and its own optimizer state. Compaction on the leader is not compaction on the follower.
• Backups — especially incremental ones, where the deleted vector lives happily in the chain of earlier increments. This is usually the surface where crypto-erasure earns its keep.
• Write-ahead and ingestion logs — the Chroma issue above is the textbook case: the chunk was gone from the index and still present as plain text in a queue table.
• Retrieval logs — most RAG systems log the retrieved top-k chunks for debugging and evaluation. That log is a plaintext copy of the passage you just erased.
• Stored model outputs — saved conversations where the assistant quoted the chunk back to a user. The vector is gone; the answer that recites it is still in your chat history table.

None of this is exotic. It is the ordinary consequence of building a system that copies data for good reasons, and it is why erasure has to be designed in rather than bolted on — the same argument we make about GDPR as an architecture question.

The Löschnachweis: What the DPO Hands the Authority

When a German supervisory authority asks how you complied, “we called the delete endpoint and it returned 200” is not evidence. It is a claim about an API. What you want on file is a record that shows the storage layer before, the forced compaction in between, and the storage layer after — signed, so it cannot be quietly improved later.

{
  "request_id": "ART17-2026-0142",
  "subject_ref": "hmac-sha256:9f2b8c...e41d",
  // keyed pseudonym, not the name — a bare hash of a
  // name is brute-forceable. Still personal data.
  "received_at": "2026-07-02T09:14:00Z",
  "legal_basis": "GDPR Art. 17(1)(a)",
  "collection": "kb_support_de",
  "chunks_matched": 7,
  "api_delete": {
    "at": "2026-07-02T09:31:12Z",
    "effect": "tombstoned — not yet physically removed"
  },
  "segments_before": [
    {"id": "seg-a1", "vectors": 200000, "deleted": 7}
  ],
  "compaction": {
    "forced": true,
    "method": "optimizer thresholds lowered, then restored",
    "finished_at": "2026-07-02T09:48:57Z",
    "segments_rewritten": ["seg-a1"]
  },
  "segments_after": [
    {"id": "seg-b7", "vectors": 199993, "deleted": 0}
  ],
  "downstream": {
    "replicas_confirmed": ["node-1", "node-2"],
    "snapshots_purged": ["snap-2026-06-30"],
    "backups": {"method": "crypto-erasure",
                "key_epoch": "2026-Q2",
                "key_destroyed_at": "2026-07-02T10:02:00Z"},
    "retrieval_logs_purged": true,
    "stored_outputs_redacted": 2
  },
  "verified_by": "l.friedrich",
  "signature": "ecdsa-p256:MEUCIQD..."
}

The load-bearing lines are segments_before, compaction and segments_after. Everything else is context. Those three turn “we deleted it” into “this segment held the record, we forced the rewrite at this time, and the rewritten segment does not”. That is a Löschnachweis a DPO can put in front of an authority.

Which brings up the uncomfortable part. To produce this you need to read segment statistics, change optimizer configuration, enumerate your replicas and snapshots, and destroy backup keys. On a managed multi-tenant vector service you typically get an API acknowledgement and a data processing agreement — not segment-level evidence you can sign your name under. Some vendors expose more than others, and this is a reasonable thing to demand in procurement; but the reliable version of this artefact needs access to the storage layer, which in practice means running it where you control the disk.

And the honest limit of the artefact itself: it proves the segment was rewritten. It does not prove no copy ever left — an export to someone's laptop, a debug dump, a screenshot. Deletion evidence bounds what your system did. It cannot bound what your people did.

Where Tippel Fits

Most RAG systems are built so that this question cannot be answered afterwards. Retrofitting erasure evidence into a running system is far more expensive than deciding, on day one, which store you use, where it runs, what gets logged, and how a deletion is forced and recorded. That decision costs an afternoon at the start and a project at the end.

If you are running or planning a RAG system with personal data in it and want to know whether you could actually answer an Art. 17 request today, that is a concrete thing to test — and it is the kind of question our AI Readiness Check exists to answer, on your system, with a written verdict. If you would rather just talk it through first, get in touch.

This is engineering guidance, not legal advice. How Art. 17 applies to your processing is a question for your DPO or counsel; what your storage engine physically does with the bytes is a question for your engineer, and that is the half this article is about.