What is predicate-robust graph connectivity?

Predicate-robust graph connectivity is the property that an HNSW-style proximity graph remains navigable when search is restricted to nodes that satisfy an arbitrary structured filter – so the subgraph induced by the predicate still has usable paths from entrypoints into the relevant region of the vector space.

Why do ordinary HNSW edges fail under filters?

Unfiltered HNSW assumes every neighbor on an adjacency list is a legal stepping stone. A predicate (price band, tenant, stock flag, language) carves out an allow-list. The edges that made the full graph a small world often run through nodes that fail the filter. If search simply skips non-matching nodes without another way to expand, the walk can strand in a matching island far from the true filtered neighbors – or thrash through gray nodes forever while paying full distance costs. That is the connectivity story behind filtered-query collapse: the vectors and edges exist, but the effective graph for this predicate is broken or nearly empty near the query. Robustness means the index or the search strategy was designed so arbitrary predicates still leave a traversable structure, without building a separate HNSW per possible filter (which is impossible for open-ended predicates such as continuous price ranges).

Two families of ideas try to keep those induced subgraphs usable.

How do construction and search restore predicate-robust paths?

Construction-time approaches densify the graph in a predicate-agnostic way – retaining more neighbors or changing pruning – so that after any filter removes a fraction of nodes, the surviving subgraph still approximates a navigable HNSW. Search-time approaches keep a standard graph but change expansion: multi-hop (two-hop) neighbor exploration jumps over a non-matching bridge to matching nodes beyond it, and filter-matching entry seeds drop the walk into the allowed region faster when vector/predicate correlation is low. Sweeping-style search preserves connectivity by continuing to follow all edges while only admitting matching IDs into the result set – robust for recall, sometimes expensive when almost nothing near the query matches. Specialized filtered indexes that pre-wire edges for known predicates are robust only for the predicates they anticipated. Predicate-robust design prefers agnostic methods: one graph, many unforeseen filters, connectivity that degrades gracefully as selectivity and correlation vary.

Robustness is empirical, not a free theorem, so operators still need to measure it.

When is connectivity robust in name only?

Neither classic HNSW nor ACORN-style variants guarantee that every predicate subgraph is connected on every dataset. Clustering of labels, extremely low selectivity, and negative correlation (matching items live far from the unfiltered query neighborhood) remain hard. A strategy that is robust on one workload can underperform sweeping on another selectivity band. Insufficient densification or disabled multi-hop expansion reintroduces collapse. Flat fallbacks for tiny allow-lists are a complementary form of robustness: when the induced subgraph is too sparse to walk, exact scan over matches beats a disconnected approximate walk. Treat "predicate-robust" as a measured property – filtered recall versus unfiltered recall on the same vectors – not as a checkbox from enabling a flag once.

Weaviate’s filtered HNSW path is built around keeping graph integrity while applying predicates.

How does Weaviate pursue predicate-robust connectivity?

Weaviate pre-filters with the inverted index to build an allow-list, then runs HNSW with that list in context rather than blind post-filtering alone. The historical sweeping strategy follows links normally and only admits allow-listed IDs to results, which preserves structural connectivity at the cost of distance work on non-matches. The acorn strategy (default on recent versions) adds predicate-aware efficiency: skip distance on non-matching objects where safe, use multi-hop expansion to cross non-matching bridges, and seed additional filter-matching entrypoints so negatively correlated queries reach the allowed zone faster – without requiring a denser graph rebuild for existing collections. flatSearchCutoff switches to exact search over small allow-lists when approximate walk would be the wrong tool. Configure filterStrategy per collection, and evaluate filtered ground truth under your real selectivity mix; ACORN tends to shine on large data with low correlation, while sweeping can win on some high-selectivity patterns. HFresh centroid routing also benefits from the same filtered HNSW ideas when predicates apply.

Diagnosing robustness problems looks like filtered collapse with a connectivity fingerprint.

How should you test whether your graph is predicate-robust?

Build a filter-aware eval set: for each query, compute exact neighbors inside the allow-list, then compare HNSW filtered results. Stratify by selectivity and by vector/predicate correlation. A/B acorn versus sweeping and different cutoffs. If unfiltered recall is high and filtered recall collapses only when matches are sparse near the query, you are missing predicate-robust paths – not suffering a metric mismatch. Raise query ef after strategy changes; connectivity and depth interact. Revisit "What is filter selectivity?" and "What is vector/predicate correlation?" when classifying which production predicates stress robustness the most.

Predicate-robust graph connectivity is a small world that still works after the map is punched full of holes. Next, read "What is hardware-aware graph topology?" when the frontier shifts from filters to fitting the graph to CPUs, memory, and disks, or "What is a filtered-query collapse?" when robustness has already failed in production.