The Short Answer
Deleting the source file does not delete the data. An embedding is derived data: once a document, image, or video frame has been encoded, the vector lives in the index independently of the object it came from, and removing the original leaves it untouched and still searchable. A complete erasure has to reach four places: the source object, the vector and its payload, any derived artifacts such as captions, transcripts, thumbnails, or extracted text, and any cache holding a result computed before the deletion.
Then there is a second problem underneath the first. Most approximate-nearest-neighbour indexes do not remove a vector when you delete it. They mark it, keep the node so the graph stays connected, and reclaim the space at some later compaction. Between those two moments the data is on disk and out of results, which satisfies a product requirement and does not satisfy an erasure obligation.
Why Deleting the File Does Not Delete the Data
An index entry is a lossy transformation of its source, stored separately and usually in a different system. Deleting the object from storage severs the link that lets you find the vector, which makes the remaining copy harder to locate rather than gone.
This gets worse the more you extract. A single video that has been through a perception pipeline is not one row. It is shot boundaries, per-shot embeddings, a transcript with timings, detected objects, extracted on-screen text, thumbnails, and often a summary written by a model. Each of those is a separate artifact in a separate place, and several are text that a human can read directly. If the requirement is that a person no longer appears in your system, the transcript naming them matters as much as the face embedding.
The practical consequence: deletion has to be modelled on the derivation graph, not on the file. If you cannot answer "what did we produce from this object?" you cannot delete it, which is why lineage is a compliance feature and not only a debugging one.
The Four Places a Deleted Item Still Lives
The source object. The easy one, and the only one most delete endpoints touch.
The vector and its payload. The payload is the part people forget. Filterable metadata stored alongside a vector often carries the identifying fields, because that is what made it filterable. A vector with a payload naming a person is personal data whether or not the source file survives.
Derived artifacts. Transcripts, captions, OCR text, keyframes, detected-object records, cluster memberships, and taxonomy assignments. Cluster centroids are a subtle case: a centroid computed while the item was present carries a trace of it and does not update itself when the item leaves.
Caches. Query result caches, embedding caches, and CDN copies of thumbnails. A retrieval cache is the awkward one because it is keyed on the query rather than on the document, so there is no key to delete by. The usual answer is a version stamp on the index that invalidates every entry computed before it.
What "Deleted" Means Inside an ANN Index
This is the part that surprises people who have only used a relational database.
HNSW builds a navigable graph where each vector is a node with links to its neighbours. Removing a node would break the paths that run through it, so implementations generally do not: they set a deleted flag, keep the node in the graph for traversal, and filter it out of results at query time. The vector stays in memory and on disk until a rebuild or compaction drops it. IVF-style indexes behave similarly, marking entries within a partition and reclaiming on rewrite.
Three consequences worth planning for. The index does not shrink when you delete, so a corpus that churns heavily grows even at a steady item count. Recall drifts as the proportion of deleted nodes rises, because the graph is still routing through them. And "when is it actually gone" is answered by your compaction schedule rather than by the delete call, which means an erasure deadline is a compaction question.
If your obligation is that data is unrecoverable within a stated window, that window has to be shorter than your compaction interval, and you need to be able to force a compaction rather than wait for one.
Soft Deletes and Tombstones, and Why a Deletion Can Look Finished Before It Is
Distributed systems delete in two phases: mark the record, then clean up the data it points at. The gap between them is where surprising behaviour lives, and the surprise is usually that different endpoints disagree with each other.
A concrete example from our own platform, fixed on 2026-08-17. When a collection was deleted and its point cleanup did not complete, the record was retained as a tombstone so a retry sweep could finish the job. Tombstones were correctly hidden from reads, so GET and list both returned nothing. The create path, however, still matched them by name and answered "already exists". For up to an hour, until the hourly sweep ran, DELETE reported success, GET returned 404, and POST refused to re-create. Every one of those answers was locally correct and the set of them was incoherent.
The lesson generalises past that bug. A tombstone is a promise that cleanup will happen, and a promise is not a completion. If you report an erasure to a user or a regulator when the mark is written, you are reporting an intention. The honest signal is the completion of the sweep, which means the sweep needs to be observable and its failures need to be loud.
Can Someone Reconstruct the Original From an Embedding?
Partially, and more than most teams assume. Embedding inversion is an active research area, and the direction of travel has been consistent: models trained to map vectors back to inputs recover a meaningful amount of the original. For text embeddings, reconstructions can recover much of the substance of short passages rather than merely the topic. For face embeddings, inversion can produce an image recognisable as the same person.
This matters for one reason. If a vector can be inverted into something identifying, then the vector is personal data, and "we only kept the embedding" is not a de-identification argument. Treat the index as holding the content rather than a safe hash of it, and the deletion requirements follow from that. Hashes are one-way by construction; embeddings are one-way by convenience, and the convenience is eroding.
How Do You Verify a Deletion Actually Happened?
An API returning 200 means the request was accepted. Verification means going and looking, and the checks that work are the ones a passing result cannot fake.
Search for it. Run the query that used to return it, with filters wide open, and confirm it is absent. Do this against the same read path a user hits, not against an admin endpoint that may apply different filters.
Count the index. A deletion should move a count. If the vector count is unchanged, you have marked rather than removed, which tells you where in the lifecycle you actually are.
Query the payload directly. Filter on the identifying field rather than searching semantically. A filtered lookup on
document_id or an email field finds records that a similarity search would never surface, and those are exactly the ones that outlive an incomplete deletion.Check the derived artifacts by name. Transcripts and extracted text are searchable as text. If the person's name was in a transcript, grep for the name.
Re-check after compaction. The point of the exercise is the state after space is reclaimed, so a verification that runs only immediately after the delete call is measuring the wrong moment.
One caution learned the hard way: a single check against a system mid-rollout or mid-sweep can hit whichever replica has already converged and report success for a fleet that has not. Sample repeatedly, and prefer a check that fails loudly over one that returns an encouraging empty result. An empty result is what both success and a broken query look like.
How the Approaches Compare
| Approach | Data gone when | Index shrinks | Main limitation |
| Delete source object only | Never, for the vector | No | The embedding and every derived artifact survive |
| Mark deleted in the index | At next compaction | No, until then | "Deleted" means filtered from results, not removed |
| Delete + forced compaction | Minutes to hours | Yes | Compaction is expensive and competes with serving |
| Delete by derivation graph | When the sweep completes | Yes | Requires lineage you may not have recorded |
| Crypto-shredding (per-subject key) | Immediately, on key destruction | No | Needs per-subject encryption designed in from the start |
| Re-index without the item | On rebuild | Yes | Full re-embedding cost, and it is the slowest option |
Backups deserve their own sentence, because they are where deletion plans usually go quiet. A restore reintroduces everything the backup held. The common position is that backups are exempt from immediate erasure provided they are not used for live processing and the deletion is reapplied on restore, which only works if the reapplication is an actual step someone owns.
What This Looks Like in Mixpeek
Deletion is modelled on the derivation graph. A document knows what it produced, which is what makes document lineage queryable in both directions, so removing an object can also reach the features, clusters, and derived documents built from it rather than leaving them orphaned in the index.
Two design choices follow from the sections above. Cleanup is a tracked sweep rather than a fire-and-forget call, so an incomplete deletion stays visible as work outstanding instead of disappearing behind a 200. And a retrieval result computed across several collections is only cached when every collection answered, which stops a stale partial answer from being pinned for the life of the cache after an index changes underneath it.
If you are choosing where the vectors live, the deletion story should be part of that choice rather than a thing you discover afterwards. MVS keeps vectors in your own object storage, which makes the residency and erasure question answerable in the same place as the rest of your data governance. Pricing starts at $25/mo for up to 1M vectors.