What is graph aging?

Graph aging is the gradual loss of efficiency and navigability in a proximity graph as inserts, updates, and deletes accumulate – especially when deleted nodes linger as tombstones – so the same live corpus costs more memory and hops than a freshly built index of equal size.

Why do proximity graphs age under real CRUD?

Classic HNSW papers emphasize insert-time construction. Production indexes live for months under churn. True in-place deletion that rewires every neighbor across layers is expensive and error-prone, so many systems soft-delete: mark a node deleted, hide it from results, but leave it in the adjacency structure as a waypoint. Walks still traverse those dead nodes; beams must over-fetch so enough live candidates survive filtering; RAM and disk keep storing vectors and edges that no longer represent live objects. Updates often become delete-plus-reinsert, doubling the tombstone and slot churn. Over time the graph’s footprint tracks historical peak size more than current live count, and latency rises even when the application thinks it deleted most of the data. That structural wear is graph aging.

Aging shows up as measurable operational symptoms, not as a single error flag.

What does an aging graph look like in production?

Tombstone counts climb after bulk deletes or high update rates while RSS barely falls. Query p95/p99 lengthens because greedy search steps through dead waypoints before finding live neighbors. Recall can sag if ef is not wide enough to compensate for filtered-out tombstones, or if connectivity around heavily deleted regions thins until cleanup runs. Index files grow across add/delete loops that leave zero live objects but a large graph on disk. Cleanup or compaction jobs spike CPU when they finally rewrite neighborhoods. Aging is distinct from a one-shot bad build: the index may have been excellent at day zero and still degrade purely from lifecycle mechanics. It is also distinct from embedding-model drift – the vectors’ semantics may be fine while the graph scaffolding around them is bloated.

Operators and engines fight aging with cleanup, reuse, and occasional rebuilds.

How is graph aging mitigated?

Background tombstone cleanup removes deleted nodes for good and reassigns edges so navigability rests on live vertices again. Some libraries reuse deleted slots when inserting new points so the graph does not grow without bound under churn. Segment merge or compaction rewrites indexes without dead entries once a deleted fraction crosses a threshold (often on the order of tens of percent in operational guidance). When churn is extreme, a blue/green rebuild – construct a fresh graph from live vectors beside the old one, verify recall, then swap – is cheaper than living with a permanently aged structure. Research continues on deletion procedures that preserve random-walk or hitting-time properties without leaving permanent tombstones. Raising ef is only a temporary bandage: it spends more exploration to paper over dead nodes rather than reclaiming the graph.

Weaviate’s HNSW stack is built specifically so aging does not have to be permanent.

How does Weaviate limit graph aging?

Weaviate uses tombstones for deletes and for the delete half of updates (old doc IDs are marked deleted and new ones reinserted), so results hide deleted objects immediately. Unlike libraries that only mark deleted and never compact, Weaviate runs an asynchronous cleanup that rebuilds affected parts of the HNSW graph and removes tombstoned elements for good – the operational answer to graph aging. Collection-level cleanupIntervalSeconds controls how often cleanup is triggered; for very large shards, environment limits such as TOMBSTONE_DELETION_MIN_PER_CYCLE, TOMBSTONE_DELETION_MAX_PER_CYCLE, and TOMBSTONE_DELETION_CONCURRENCY bound how much cleanup work runs per cycle so maintenance does not starve queries. Metrics such as vector_index_tombstones, cleanup progress, and cleaned counts let you see aging and recovery in flight. Snapshots and commit-log compaction keep on-disk history from growing forever with every edge change. Prefer monitoring tombstone gauges after bulk deletes; if cleanup lags, tune cycle bounds rather than endlessly raising ef. Indexes such as HFresh that rebalance postings incrementally pursue a related freshness goal with a different topology, but HNSW aging in Weaviate is primarily a tombstone-and-cleanup story.

Detecting aging early means watching structure, not only average recall.

How should you detect and respond to graph aging?

Track tombstone count versus live objects, index RSS versus expected size for the live set, and latency before versus after cleanup cycles. After large purges, expect deletes to succeed in the API while memory falls only once cleanup completes – that lag is normal aging in progress, not necessarily a broken delete. If tombstone ratio stays high and p99 climbs, increase cleanup capacity or schedule a rebuild window. Re-benchmark recall on a fixed query set after heavy churn; if quality only recovers with much higher ef, the graph is compensating for dead structure. Next in the frontier glossary, index drift over time covers semantic and distribution shift that can compound aging but is not the same as tombstone bloat.

Graph aging is the wear proximity graphs accumulate under CRUD until cleanup or rebuild restores a live, compact structure. Next, read "What is index drift over time?" when the concern is shifting embeddings or query distributions rather than dead nodes, or revisit Weaviate tombstone cleanup settings and vector-index metrics when you need to clear an aged HNSW graph in production.