How a filter fights the index

Adding a predicate to a similarity search — same category, date after this, this tenant — looks like it should make the work smaller. Fewer eligible vectors, less to search. Instead it is the single most reliable way to make an approximate index behave badly, and the reason is structural: every index in this field precomputes structure over the whole collection, and a filter asks it to search a subset that structure knows nothing about.

The naive approach

Search as usual, then discard results that fail the predicate.

search_then_filter(query, predicate, k):
    results ← index.search(query, k)
    return [ r for r in results if predicate(r) ]

How it fails, and there are two failures stacked. The obvious one is arithmetic: if the predicate matches 1% of the collection, then of your k results you expect about k/100 to survive. Ask for ten, receive zero. Not “fewer” — zero, routinely, while thousands of matching documents sit in the collection unexamined.

The fix that suggests itself is to over-retrieve: fetch k × 100 and filter. That works when the predicate is roughly independent of position in the space, and fails when it isn’t — which is most of the time. If the predicate selects one tenant, one language, one recent time window, the matching vectors occupy particular regions of the space. A similarity search returns the query’s neighbourhood, and if none of the matching regions is near the query, no amount of over-retrieval finds them. You are enlarging a net in the wrong part of the ocean. Worse, the multiplier you’d need is unknowable in advance because it depends on where the query lands relative to the matching subset.

So we need the predicate to influence the search itself. Each index family responds differently, and the differences follow directly from what each one precomputed.

Why a graph index strands

A proximity graph is a set of edges chosen so that greedy descent converges. The edges encode proximity in the full collection. Delete the non-matching nodes and you are left with an arbitrary induced subgraph of a structure that was carefully designed as a whole, and the design properties do not survive the deletion.

The obvious approach is to keep traversing the full graph but only collect nodes that match:

filtered_traverse(query, predicate, breadth):
    # walk the whole graph, but only matching nodes enter the result set
    expand nodes as usual, using every node's edges to navigate
    add n to best only if predicate(n)

The navigation still works — you are using the real graph, so the geometry is intact — but the cost is now wrong. Your budget is spent examining nodes that are discarded on arrival. At 1% selectivity, roughly 99 out of every 100 distance computations produce nothing, and the effective breadth over the matching subset is a hundredth of what you configured. Recall over the subset collapses even though every step of the traversal was correct.

The alternative is to refuse to step through non-matching nodes — traverse only the induced subgraph. That is worse, and the reason is the interesting one:

The induced subgraph is usually disconnected. Node a and node c both match; the only short path between them ran through b, which doesn’t. Forbid b and the two matching regions are separate components. The walk explores whichever component it started in and never learns the other exists. At low selectivity the matching nodes are a scatter of tiny islands, and the search returns whatever island it happened to land on. This is a hard failure, not a graceful degradation: the results are confidently wrong, and raising breadth doesn’t help because breadth widens the frontier within a component and cannot cross to another.

So a graph index has a genuine bind. Traverse everything and waste the budget; traverse the subgraph and lose connectivity. The practical middle ground is what implementations do: walk the full graph for navigation, count only matching nodes against the result budget, and expand the total work allowance to compensate. That is honest and it means a filtered query costs substantially more than an unfiltered one, in inverse proportion to selectivity, until at some selectivity the cost passes what a plain scan of the matching subset would have been.

Which gives the crossover, and it is the one number worth reasoning about. Below some selectivity, the right algorithm is not the index at all: fetch the matching IDs from whatever structure indexes the metadata, and compute exact distances over just those. If a predicate matches a few thousand vectors, that is a few thousand distance computations — cheap, exact, and better than any traversal. Above some selectivity, the filter is barely a constraint and normal traversal with light over-retrieval is fine. The awkward middle is where filter-aware traversal earns its complexity.

Why a cluster index shrugs

A cluster index reacts far more mildly, and the reason is worth stating because it is the clearest case of a structural property predicting behaviour.

The second stage of a cluster search is an exhaustive scan of the vectors in the probed cells. An exhaustive scan does not navigate. It has no dependence on the connectivity of anything. Adding a predicate to a loop that is already visiting every element of a list is nearly free: check the predicate, skip the distance computation if it fails. You lose no structure because you were not using any.

filtered_cluster_search(query, predicate, k, nprobe):
    near ← nprobe centroids closest to query
    for c in near:
        for v in list[c]:
            if predicate(v): consider v
    return top k

The degradation is quantitative rather than structural: at 1% selectivity, a probed cell yields about 1% as many candidates, so you need more probes to accumulate k results. Cost rises roughly in inverse proportion to selectivity, the same as the graph case — but nothing becomes unreachable, and the results stay correct with respect to what was scanned. Cluster indexes don’t handle selective filters well; they handle them predictably, which is a real advantage when a filter is always present.

The strategies, and what each assumes

Four mechanisms in use, each valid under a different condition.

Post-filter with over-retrieval. Assumes the predicate is roughly independent of position in the space. Cheap when true, silently broken when false, and there is no signal telling you which case you’re in beyond an unstable result count.

Pre-filter to a candidate set, then exact scan. Assumes the matching subset is small enough to scan. Exact, predictable, and the correct answer at high selectivity. Requires a metadata index that can produce matching IDs efficiently — typically a bitmap or posting list — and the cost is proportional to the subset, so it is bounded by something you can compute.

Filter-aware traversal. Assumes moderate selectivity and that the matching subset is not scattered. Uses the full graph for navigation while only matching nodes count towards results, sometimes with heuristics that prefer expanding nodes likely to lead to matching regions. The best general answer in the awkward middle, and it costs more than an unfiltered query by a factor that grows as selectivity falls.

Partition by the predicate at build time. Assumes one predicate dominates and is known in advance. Build separate index structures per value of that attribute, and a filtered query becomes an unfiltered query against a smaller index — no degradation at all, because the structure was built over exactly the subset being searched. This is the only approach that makes filtering free, and it buys that by restricting which filters exist: any predicate other than the partitioning one is back to the general case. It also means the graph in each partition is built over fewer vectors, which changes its quality characteristics.

The mechanism worth carrying away

There is one sentence underneath all of this. An index is a precomputed structure over a fixed set, and a filter changes the set. Whether that matters depends entirely on whether the index’s search procedure navigates the structure or merely iterates it.

Navigation depends on connectivity, and connectivity is a property of the whole set, so removing members can destroy it — which is why graph indexes fail sharply and why their failure is invisible from the result set. Iteration depends on nothing, so removing members merely leaves fewer of them — which is why cluster indexes degrade smoothly and why their cost stays computable.

That distinction also predicts the composite case. In a composite index where a graph routes to a coarse region and a scan finishes the job, the filter hurts the routing stage and not the scanning stage, and the mitigation belongs at the routing stage where the problem is.