What is damaged graph connectivity?

Damaged graph connectivity is when an HNSW index still stores the right vectors but its edges no longer form a reliably navigable small-world: missing long-range bridges, broken neighborhoods after deletes, or overly aggressive pruning leave regions that greedy search cannot reach from the usual entrypoints.

Why does HNSW search depend on connectivity more than on raw vectors?

Exact nearest-neighbor search compares the query to every point. HNSW instead walks a multilayer graph: coarse long links in upper layers hop across the space, then denser layer-zero edges refine locally. That walk only works if there is a path of improving (or at least exploratory) neighbors from the entrypoint into the true neighborhood. The vectors can be perfect and the distance metric correct, yet if the edges that should have linked cluster A to cluster B were never built, were pruned away, or were left pointing at tombstones that cleanup has not rewired, the searcher gets stuck in a local pocket and reports confident wrong neighbors. Connectivity damage is a topology failure – the map’s roads are missing – not an embedding failure.

Several everyday operations quietly erase or never create those roads.

What operational patterns damage the graph?

Sorted or clustered insertion order grows one dense pocket at a time and under-invests in cross-pocket bridges – the same mechanism behind insertion-order recall variance, now visible as structural isolation. Low efConstruction or very tight maxConnections budgets prune candidate edges that would have been the only path between regions. Mass delete/update churn leaves tombstones on critical hubs; until async cleanup reassigns inbound links, traversals waste steps on dead relays or lose the relay entirely. Filtered search that refuses to expand through non-matching nodes can make a healthy graph behave as if disconnected for that predicate – an effective connectivity failure even when the underlying edges exist. Corrupted or partially restored snapshots can drop layers or adjacency blocks. In all of these cases raising query ef helps only while some path still exists; beyond a point, more candidates cannot invent bridges that construction never stored.

The symptoms look like stubborn recall loss concentrated in some queries, not uniform noise.

How does damaged connectivity show up in recall and latency?

Queries whose true neighbors sit in a poorly linked region miss badly even at high ef, while queries inside a well-linked pocket look fine – a regional fingerprint that distinguishes connectivity damage from a global metric mismatch. Latency may stay low (the walk terminates early in the wrong pocket) or spike (the search thrashing through dead or filter-blocked nodes trying to escape). Insufficient top-k pages appear when the reachable component simply has fewer live nodes than requested. Exact brute force on the same vectors recovers the true neighbors, proving the data is present; only the graph walk fails. After a bulk delete wave, expect a temporary connectivity dip until cleanup finishes; if the tombstone gauge stays high and recall stays regionally bad, rewiring never caught up.

Weaviate’s HNSW design tries to keep the live graph navigable under CRUD and filters, but construction quality and cleanup health still matter.

How does Weaviate keep – and restore – navigable connectivity?

Weaviate builds HNSW with configurable efConstruction and maxConnections so inserts discover richer neighborhoods when you pay for them at load time. Deletes tombstone immediately and rely on asynchronous cleanup to reassign edges and drop dead nodes – monitor tombstone metrics so accumulation does not leave the graph haunted. For filtered queries, strategies such as sweeping and acorn exist specifically because skipping non-matching nodes without a connectivity-preserving expansion can strand the search; choose the strategy that matches your selectivity and correlation mix, and use flatSearchCutoff when the allow-list is small enough that exact search over matches beats a fragile walk. After major corpus reshuffles, prefer a shuffled reindex or full rebuild over endless ef inflation. Snapshots and commit logs restore whatever topology was last durable – they do not heal a graph that was already poorly connected when saved.

Confirming damage means proving the vectors are findable by exact search and unfindable by graph walk.

How should you detect damaged graph connectivity?

Hold vectors and metric fixed; compare HNSW results to exact neighbors on a stratified query set. If misses cluster by ingest era, category, or filter predicate, suspect topology. Raise ef sharply: modest gains imply under-search; flat failure implies missing paths. Inspect tombstone and cleanup progress after churn. Rebuild a twin collection with higher efConstruction and shuffled order – a large recall jump on the twin is the connectivity smoking gun. Rule out stale query parameters, dimensionality bugs, and serialization load failures first so you do not rebuild a healthy graph for the wrong reason.

Damaged graph connectivity is a city with the highways removed. Next, read "What is the difference between cosine similarity and cosine distance?" when score polarity confuses debugging, or "What is insertion-order recall variance?" when the damage traces back to how the graph was grown.