What is dynamic graph-topology maintenance?

Dynamic graph-topology maintenance is the ongoing work of inserting, deleting, and repairing edges in an ANN proximity graph so the index stays navigable as the live vector set changes – without rebuilding the entire graph from scratch after every churn event.

Why can’t a static HNSW graph survive production churn?

Classic proximity-graph papers often assume a fixed corpus: build once, query forever. Production collections insert new embeddings, overwrite old ones, and delete documents continuously. Each insert must weave a new node into the multilayer small-world; each delete removes a vertex that may have been a bridge for many inbound neighbors. If you only tombstone the node and leave edges untouched, searches still walk through dead relays, memory inflates, and reachable components fragment. If you tear the node out without repairing neighbors, you create unreachable pockets – damaged connectivity that no amount of query-time ef can fully heal. Dynamic topology maintenance is the discipline of local structural repair: update only the neighborhoods that the change actually touches, preserve degree bounds, and keep long-range navigability alive while queries continue.

Maintenance strategies differ in how much of the graph they rewrite per change.

What techniques keep topology healthy under inserts and deletes?

Inserts typically run the same hierarchical search used at query time, then link the new node to selected neighbors under a pruning heuristic that caps degree. Deletes are harder. Soft-delete (tombstone) hides the ID from results immediately, then a background pass rewires neighbors that pointed at the dead node – sometimes by re-searching candidates (search-based repair), sometimes by splicing the deleted node’s outgoing neighbors into the inbound neighbors’ lists and re-pruning. Research continues on cheaper localized repairs that only touch mutual neighbors, topology-aware page-local updates for disk-resident graphs, and connectivity-aware pruning that avoids cutting the last bridge into a region. Cluster-style indexes maintain topology differently: they split, merge, and reassign posting lists or partitions as sizes drift, so "maintenance" is incremental rebalancing of regions rather than per-edge HNSW surgery. Across all of these, the goal is the same – freshness without a global rebuild – with a cost paid in background CPU, temporary recall dips, and operational complexity.

When maintenance lags or is too aggressive, the failure modes are familiar.

What happens when topology maintenance falls behind or over-prunes?

Slow cleanup produces delete accumulation: tombstones pile up, traversal wastes work, and RSS stays near peak historical size. Incomplete repair leaves unreachable points that exact search would still find offline – regional recall cliffs that look like insertion-order damage. Over-eager local pruning under a narrow candidate view can remove globally important bridges, fragmenting the graph even though every local degree constraint is satisfied. Async queues that trail ingest create windows where objects exist in the document store but not yet in the searchable topology (or the reverse after delete). Monitoring must therefore track both churn rate and maintenance progress – not only query latency.

Weaviate’s production indexes embody dynamic maintenance rather than immutable snapshots.

How does Weaviate practice dynamic graph-topology maintenance?

Weaviate’s HNSW implementation supports full CRUD: inserts link into the live graph; updates tombstone the old internal document ID and reinsert; deletes attach a tombstone immediately so results hide the ID, then asynchronous cleanup reassigns edges and removes dead nodes for good. Cycle timing follows cleanupIntervalSeconds, with optional bounds on tombstones processed per cycle and cleanup concurrency so large shards do not stall the box. Asynchronous indexing can queue graph mutations behind object-store writes, trading a short visibility lag for ingest throughput. For memory-sensitive, billion-scale regimes, Weaviate’s HFresh index keeps a compact in-memory centroid HNSW and stores posting lists on disk, maintaining quality through background incremental rebalancing – splitting oversized postings, merging undersized ones, and reassigning vectors as boundaries shift – instead of periodic full rebuilds. In both designs, operators should watch tombstone and queue metrics, size cleanup for their churn, and treat a full reindex as a recovery tool when maintenance debt and regional recall loss compound beyond what local repair can clear.

Frontier work extends these ideas toward cheaper, connectivity-aware repairs under heavier streaming loads.

How should you evaluate whether maintenance is doing its job?

Compare recall on a churned index to a rebuild from the same live export; a large gap that shrinks after cleanup catches up points to maintenance lag, not bad embeddings. Track unreachable or empty-result rates after delete storms. Log cleanup cycle duration versus delete arrival rate. After enabling async indexing, measure the lag until new objects become vector-searchable. Prefer shuffled bulk loads when rebuilding so construction itself does not bake in weak bridges that maintenance must later fight.

Dynamic graph-topology maintenance is keeping the roads open while the city keeps changing. Next, read "What is predicate-robust graph connectivity?" when the hard part is staying navigable under filters, or "What is delete accumulation?" when tombstones outrun the repair loop you just learned about.