Why deleting vectors doesn't free memory
A retention job deleted several months of documents. The count in the collection dropped as expected. Resident memory did not move, latency did not improve, and now someone is asking whether the delete actually happened.
It did. Deletes in a vector index are almost always logical: the record is marked as gone so queries stop returning it, and the storage it occupies is reclaimed later, by a separate process, that may not be running.
What a delete actually does
Removing a vector from a graph index properly would mean repairing the neighbour lists of every node that pointed at it. Those nodes point at other nodes, some of which relied on the deleted node to stay connected, and the repair can cascade. Doing that online, under query load, per delete, is expensive enough that essentially nobody does it.
So the delete is recorded in a side structure — a tombstone, a deleted-ID set, a bitmap — and the search path filters against it. The vector data, the neighbour lists, and the metadata all stay exactly where they were.
That gives you three costs, and they are worth separating because they have different fixes:
| Cost | What it looks like |
|---|---|
| Space | Memory and disk unchanged after a large delete |
| Latency | Traversal visits dead nodes and pays for them |
| Recall | Search budget spent on nodes that cannot be returned |
The recall cost is the one that surprises people. A traversal has a bounded exploration budget. If a meaningful fraction of the nodes it examines are tombstoned, it spends that budget on candidates it must discard, and it can terminate having found fewer live neighbours than it would have on a clean index of the same live size. Your quality degrades from churn alone, with no change to data, model, or configuration.
Measuring the dead fraction
You need one number: live records divided by total physical records. Getting it is engine-specific and often awkward, which is why most teams don’t have it.
Places to look, roughly in order of availability:
- A per-collection statistic for deleted or tombstoned count. Some engines expose this directly. If yours does, chart it as a ratio and stop reading this section.
- Per-segment statistics. Where the engine reports counts per segment, the difference between the segment’s document count and its live count is the dead count. Summing gives the ratio, and the per-segment breakdown is more useful anyway, because tombstones concentrate in the segments covering the deleted time range.
- The gap between logical and physical size. Compare the count your queries can see against the memory or disk the collection occupies, divided by your measured bytes-per-record from sizing. A large discrepancy that appeared right after a bulk delete is your answer even without a direct metric.
Whatever you can get, turn it into a ratio and alert on it. The absolute count is meaningless — a large collection can carry a large number of tombstones comfortably. The ratio is what predicts both the latency drift and the recall drift.
What reclaims the space
Four mechanisms, in increasing order of disruption.
Segment merge. In segment-based engines, tombstoned records are dropped when their segment is merged into a new one. This is the normal path, it is free in the sense that it was going to happen anyway, and it is the reason a compaction backlog and a tombstone backlog are usually the same incident. If your dead fraction is high, check compaction health first — see compaction, and when to force it.
The catch: merge policies choose candidates by size and age. A segment sitting just under the maximum merge size will never be selected, and if that segment is where your deletes landed, its tombstones are permanent until you intervene. Some engines expose a deleted-fraction trigger for exactly this; if yours does, set it.
In-place vacuum or optimize. Some engines can rewrite a segment to exclude its tombstones without a full merge. Cheaper than a rebuild, still IO-heavy, and it needs free space for the output before the input is dropped.
Rebuild. Always works, costs the most, and gives you a clean structure with correct neighbour lists rather than merely reclaimed space. If the dead fraction got high enough to hurt recall, a rebuild is what actually restores quality — see reindexing without downtime.
Drop and reload the affected partition. If your deletes align with a partition boundary — a month, a tenant, a source — dropping the whole partition is instant and reclaims everything. Which is an argument for choosing partitions that match how you delete, covered in partitioning by the filter you always use.
The runbook for a high dead fraction
- Get the ratio. Per segment if possible. Without it you are guessing at which fix applies.
- Check whether merges are running at all. If not, that is the bug; the tombstones are a symptom. Fix compaction and the fraction will fall on its own.
- Check whether merges are running but skipping the affected segments. Large old segments full of deletes are the classic case. Look for a deleted-fraction merge trigger and set it, then let the background process do the work.
- Confirm free space before triggering anything. Every reclamation mechanism writes new before dropping old. A vacuum on a nearly full volume fails, and on some engines it fails partway.
- Take a snapshot. You are about to rewrite data.
- Trigger the cheapest mechanism your engine offers, off-peak, and watch query latency while it runs rather than after.
- Re-measure the ratio and your recall probe. Space coming back is the easy half. Whether recall recovered tells you if the structure needed rebuilding rather than merely vacuuming; the probe is described in what to monitor.
Rollback: restore the snapshot from step 5. Reclamation is not reversible in place — once the tombstoned records are gone, they are gone, and if it turns out the retention job deleted more than intended, the snapshot is the only copy of what it removed. That is the real reason for step 5, and it is why you should hold a pre-reclamation snapshot for longer than your normal retention. A bad delete is usually discovered after the deletes have been reclaimed, not before.
Stop it recurring
- Alert on the dead fraction as a ratio. A single threshold, on the default dashboard.
- Batch and schedule deletes rather than trickling them. A retention job that runs nightly against a partition boundary is operationally trivial; the same volume of deletes spread evenly across every segment is not.
- Make retention and partitioning agree. If you delete by date, partition by date. Then deletion is a drop, reclamation is immediate, and none of the above applies.
- Treat high-churn collections as needing a rebuild cadence. Some workloads — anything where documents are frequently updated, since an update is usually a delete plus an insert — accumulate tombstones faster than merges clear them, permanently. For those, a scheduled rebuild is a maintenance task, not an emergency, and scheduling it is cheaper than being paged by it.
The general shape: a vector index tolerates deletes far worse than a relational table does, because the structure encodes relationships between the records rather than just holding them. Plan the reclamation, or the churn will plan an incident for you.