Filtered Vector Search
Why combining a metadata filter with a nearest-neighbour search is harder than either alone, the two naive strategies and how each fails, and what a native implementation does instead.
"Find the ten most similar documents where tenant is X and status is published" is the query every production retrieval system actually issues, and it is substantially harder than unfiltered nearest-neighbour search. The difficulty is structural: the index was built over the whole collection, and the filter changes which points are eligible after that structure was fixed.
The two naive strategies
Pre-filtering applies the metadata predicate first, then searches within the matching set. Correct by construction, and it cannot use the approximate index, because the index's graph or partitions were built over all points and restricting to a subset breaks their connectivity. Falling back to a brute-force scan is fine when the filter is highly selective and returns a few thousand candidates, and catastrophic when it returns ten million.
Post-filtering runs the approximate search first, retrieving \(k' > k\) candidates, then discards those failing the filter. It uses the index fully and can return too few results, or none. If the filter matches one percent of the collection, retrieving 100 candidates yields roughly one match, so \(k'\) must be inflated enormously and the required inflation depends on a selectivity nobody knows in advance.
Neither is adequate across the range of selectivities a real system sees, which is why this became a distinguishing capability rather than a configuration option.
What native filtering does
Filter-aware graph traversal. In a graph index such as HNSW, evaluate the predicate during traversal and only accept matching nodes as results while still traversing through non-matching ones to preserve connectivity. This is the dominant approach and it degrades as selectivity falls, because the traversal spends most of its work on ineligible nodes.
Partitioned indexes. Build a separate index per value of a low-cardinality, frequently-filtered attribute, so a filtered query becomes an unfiltered search in the right partition. Excellent for tenant isolation, and it multiplies index count and does not generalise to arbitrary predicates.
Predicate-aware entry points. Begin the graph traversal at a node satisfying the filter rather than at the global entry point, which avoids wasting the early hops in an ineligible region.
Hybrid cost-based planning. Estimate the filter's selectivity and choose pre-filtering, post-filtering or native traversal accordingly, which is what a mature system does and requires selectivity statistics the vector store must maintain.
When it breaks
Recall degrades silently under filtering. A system reporting 95 percent recall unfiltered can drop far below that on a selective filter, and nothing in the response indicates it. Recall must be measured with the filters production actually uses, not on the unfiltered benchmark.
Selectivity varies enormously across queries. One tenant has a million documents and another has fifty, so the same query shape has different optimal strategies per request, and a single configured strategy is wrong for one end of the distribution.
Complex predicates defeat native filtering. Range conditions, disjunctions and joins against other collections are far harder to evaluate during traversal than an equality check, and most implementations support a restricted predicate language for exactly this reason.
Deletions behave like a filter. A soft-deleted point still occupies the index and must be filtered from results, so a collection with heavy deletion carries a permanent implicit filter that degrades recall until compaction removes the tombstones.
14 flashcards for this concept
Click a card to reveal the answer.