Filtering Is the Hard Problem
In one line: every production query has constraints — this tenant, in stock, after this date — and combining them with approximate search is genuinely hard in a way that does not announce itself.
Why it is hard
An ANN index is built over the whole dataset. Its speed comes from structure — a graph whose links assume every node is reachable, or partitions built from the full distribution.
A filter removes an arbitrary subset from consideration, and that structure was not built for the subset. The graph's paths route through nodes that are now excluded; the partitions contain a mixture of eligible and ineligible vectors.
The two naive strategies, and how each fails
Post-filtering. Run the vector search normally, then discard results failing the predicate. Simple, and it collapses when the filter is selective: ask for 10, retrieve 100, and if only 2% of the corpus matches you may retain nothing.
The usual patch is over-fetching — request many more than you need. That works while the filter is lenient and degrades exactly as the filter gets strict, which is the opposite of what you want.
Pre-filtering. Determine the eligible set first, then search only within it. Correct, and it forfeits the index: an arbitrary subset has no prebuilt structure, so you are back to scanning. Fine when the filter leaves a thousand candidates, unusable when it leaves ten million.
| Post-filter | Pre-filter | |
|---|---|---|
| Order | Search, then discard | Restrict, then search |
| Fails when | The filter is selective — you keep nothing | The eligible set is large — you scan it |
| Patch | Over-fetch | Exact scan of the subset |
| Result quality | Silently incomplete | Exact, if you can afford it |
| Good for | Lenient filters, most rows pass | Very selective filters, small subsets |
The shape to notice: they fail at opposite ends of selectivity, which is why systems that support both pick between them per query based on an estimate of how many rows the predicate matches. That estimate is exactly the cardinality estimation a query planner does, and getting it wrong is how a filtered vector query occasionally takes a hundred times longer than usual.
The selectivity cliff
Modern vector stores integrate the filter into the traversal — skipping ineligible nodes during the graph walk rather than before or after it. That is the right design, and it has a limit worth knowing precisely.
Below roughly 5% selectivity, traversal paths begin to fragment and recall degrades. Below about 1%, recall collapses: the number of predicate-satisfying nodes in each node's one- and two-hop neighbourhood shrinks in proportion to selectivity, so the walk runs out of eligible neighbours and the graph effectively disconnects.
The number to carry: under about 1% selectivity, stop using the ANN index and scan the subset exactly. At that selectivity the eligible set is small enough that brute force is fast, and it is exact rather than badly approximate. That crossover is the practical answer.
What actually works
Partition instead of filtering. If a filter is almost always present and always the same field — tenant_id in a B2B product — do not filter, shard. One index per tenant means the filter is expressed by which index you query, selectivity is 100% within it, and you get data isolation for free. This is the strongest answer whenever the access pattern allows it, and it is the one most often missed.
Route by estimated selectivity. Estimate how many rows the predicate matches, then choose: exact scan below ~1%, filtered ANN in the middle, post-filter with over-fetch when the filter is lenient.
Reduce the filter's role. Some constraints can move into the vector — embedding a category token with the text so similar categories cluster — trading exactness for a filter you no longer need. Partial, and useful where the constraint is soft.
Denormalise into partitions for common combinations. If 90% of queries filter to active documents, maintain a separate index of only active documents. It costs storage and duplicated writes and turns the common case into an unfiltered query.
Key takeaway
Filters and approximate indexes conflict structurally: the index's speed comes from global structure that an arbitrary subset invalidates. Post-filtering fails when the filter is selective, pre-filtering fails when the eligible set is large, and integrated traversal — the right design — has a cliff at roughly 5% selectivity and collapses below 1%, because the walk runs out of eligible neighbours. Below that, scan exactly. And when a filter is always on the same field, shard by it, which eliminates the problem instead of mitigating it.
Next: why dense retrieval alone is not the production answer.