How do deletes degrade an HNSW index over time, and what fixes it?

## Why a graph index cannot just delete a node In a hash index or a B-tree, removing an entry is local. In a proximity graph it is not. Each node's edges are paths that other searches traverse — a node sitting between two dense regions may be the only bridge between them at layer 0. Physically removing it and dropping its edges can disconnect part of the graph, making a region unreachable from the entry point and silently destroying recall for queries that land near it. Repairing properly means re-running the neighbour-selection heuristic for every node that pointed at the deleted one, which is close to the cost of inserting them all again. So implementations take the pragmatic route: **tombstoning**. The node is flagged deleted. Traversal still walks through it and still uses its edges as connectors. The only change is at the end, when results are assembled: tombstoned nodes are filtered out and never returned. ## How the degradation actually shows up The failure is gradual and easy to misdiagnose, because nothing errors. **Latency drifts up.** The beam has a fixed width. Every slot occupied by a tombstoned node is a distance computation and a memory access spent on something that cannot appear in the answer. As the tombstone ratio climbs, more of each query's work is wasted, and p99 rises first because it is the queries that traverse dense deleted regions that suffer most. **Effective recall drifts down.** At a fixed efSearch, the beam holds fewer live candidates, so the true neighbours are more likely to fall out of it. The index's recall against live documents degrades even though the graph over the surviving vectors is untouched. **Result counts go short.** A request for the top 10 that over-fetches only slightly can come back with fewer than 10 live results once a chunk of the neighbourhood is dead, which surfaces as a product bug well before anyone suspects the index. **Memory does not come back.** Tombstoned vectors keep their payload and their adjacency lists. A catalogue that has churned through several times its live size can be paying for a multiple of the memory it needs. Concretely: purge 2M expired listings a night from an 80M-row catalogue and, without reclamation, within a few weeks a substantial fraction of the graph is dead weight, with p99 up and no single deploy to blame. ## The ladder of mitigations **Over-fetch and filter.** Ask for more than k and drop the tombstoned entries. Cheap, immediate, and only a band-aid — it does not recover the recall lost from a beam clogged with dead nodes. **Raise efSearch.** Widening the beam restores some of the live-candidate count. It costs latency, and it is paying twice for work you already own. **Slot reuse.** Some implementations let a new insert take over a tombstoned node's slot, rewiring its edges to the new vector. This keeps the node count flat under steady-state churn — deletes and inserts cancel out — and is the best answer for a corpus with roughly balanced turnover. It does not help a corpus that is net shrinking. **Compaction or full rebuild.** Build a fresh graph containing only live vectors, then swap it in. This is the only mitigation that actually recovers both the memory and the traversal quality, and it costs a full build. Trigger it on a measured tombstone ratio — say, when dead nodes exceed 20-30% — rather than on a fixed schedule, so the cost tracks the actual churn. ## Designing the problem away Systems with high churn generally stop treating deletion as an index operation at all. **Segmented, immutable indexes.** Write to small immutable segments, each with its own graph, and query all of them with a merge of the results. Deletes are recorded in a per-segment liveness bitmap, and a background merge periodically rewrites several segments into one, dropping the dead entries as a side effect. This turns an unbounded degradation into a bounded, continuously-paid background cost — the same pattern log-structured storage engines use, applied to vectors. **Time partitioning.** If deletion correlates with age — expiring listings, retention windows, rolling event data — shard the index by time period. Expiring a period means dropping an entire index, which is free, and the live shards are never polluted. ## Monitoring Whatever the strategy, the tombstone ratio must be an exported metric, and recall should be sampled periodically against a brute-force ground truth over the live set. Without both, this failure mode is invisible until it is a latency incident, and the first instinct — raise efSearch — treats the symptom while the cause keeps growing. ## What interviewers listen for The insight is that deleted nodes remain part of the graph because their edges carry other people's traffic, and that the cost is therefore paid on every query rather than at delete time. Everything else follows: the metric to watch, the rebuild trigger, and the architectural move to segments or time partitions when churn is a permanent feature of the workload.