How does HNSW handle updates, deletion, and graph repair?

HNSW handles updates and deletion far less gracefully than it handles ordinary insertion, because the graph’s connections were built assuming every node that exists will keep existing — removing one cleanly enough to preserve the graph’s navigability turns out to be a genuinely harder problem than adding a new node ever is, which is why practical systems generally settle for a cheaper approximation rather than true, immediate repair.

Why is append-only insertion the easy baseline this whole topic gets compared against?

Inserting a new vector only ever adds edges — it never has to reconsider or remove anything that already exists in the graph, beyond the occasional pruning of an existing node’s neighbor list once it exceeds capacity, which is itself a well-defined, bounded operation. A workload that only ever inserts, never updates or deletes, is the friendliest case HNSW can face, and it’s the implicit assumption underlying most of the construction behavior described elsewhere on this site. Everything covered on this page exists because real workloads eventually violate that assumption.

What actually happens when a vector needs to be replaced rather than just added?

Replacing an existing entry — swapping in a freshly computed embedding under the same external label, for instance — is not fundamentally different from a delete followed immediately by a fresh insert, even when an implementation exposes it as a single convenient “update” operation. The old vector’s connections still need to be dealt with using whatever deletion strategy the implementation uses, and the new vector still needs to go through ordinary insertion, including a freshly sampled layer assignment and freshly selected neighbors, since there’s no guarantee the replacement embedding belongs in the same part of the graph the old one did. Treating update as its own separate, cheaper category of operation, rather than recognizing it as delete-plus-insert in practice, is a common source of confusion about why updates can be nearly as expensive as they turn out to be.

Why does tombstone deletion work, and what does it leave behind?

The practical answer most implementations settle on is to mark a node as deleted and exclude it from future search results, while leaving its existing edges in the graph untouched. This is inexpensive — flagging a node costs essentially nothing compared to reworking its connections — and it works because other nodes can still route through a tombstoned node structurally even though that node itself will never again appear as a final answer. What it leaves behind is a subtler problem: a deleted node may have been the only bridge connecting two otherwise-distant regions of the graph, and while its outgoing edges still let a search pass through it, nothing has repaired the fact that other nodes which used to rely on an edge pointing into that now-deleted node have lost one of their own useful incoming connections. This lost incoming connectivity accumulates quietly as more nodes get tombstoned, degrading the graph’s overall navigability well before any single deletion looks alarming in isolation.

What would it take to physically repair the graph instead of just hiding a deleted node?

A full repair means actually removing a node’s edges and rewiring its former neighbors to connect sensibly with each other or with other nearby nodes, restoring something close to the graph’s original navigability rather than merely hiding the deleted node from results. This is precisely why a properly rewired deletion tends to cost roughly as much as several tens of ordinary insertions: finding good replacement connections for every neighbor that lost a useful edge is real, nontrivial work, not a simple bookkeeping update. Because of this cost, most systems don’t perform a full repair after every individual deletion, and instead accept the gradual degradation tombstoning causes, addressing it periodically rather than continuously.

How does this play out under a continuous, high-volume streaming workload?

A system facing a steady stream of both inserts and deletes accumulates tombstones and the connectivity loss they cause continuously rather than as an occasional event, a phenomenon often described as graph aging — search quality slowly eroding over time even while the dataset’s current size stays roughly constant, purely because of how many tombstoned nodes have piled up along the way. The common practical response is to track what fraction of the graph has been marked deleted and trigger a full rebuild once that fraction crosses some threshold, which restores the graph to a clean, fully repaired state at the cost of a real, occasional construction expense — an approach that keeps the amortized cost of updates roughly constant over time, since the rebuild cost gets spread across however many insertions and deletions accumulated since the last one, rather than needing to solve real-time repair on every single deletion as it happens.

Deletion and graph aging are a genuine limitation rather than a solved problem, and the next page continues in that spirit, comparing HNSW against alternative graph-based designs that sometimes make different trade-offs around exactly this weakness. For the concrete cost estimate referenced throughout this page, this site’s page on why recall and query difficulty vary from query to query and its coverage of production failure modes both build directly on the graph-aging concept introduced here.