Why does a metadata filter matching 0.01% of vectors slow ANN search down?

## The shape of the problem Graph-based ANN search works by greedy descent: start at an entry point, repeatedly move to whichever neighbours are closer to the query, and stop when the candidate frontier stops improving. It is fast because it converges — a few hundred distance computations over a fifty-million-vector index is typical, and the result is a short list of genuinely near vectors. Adding a metadata predicate changes the termination condition. The search is no longer done when it has k near vectors; it is done when it has k near vectors *that satisfy the predicate*. Non-matching nodes are still visited, because the graph's connectivity depends on them — you often must pass through a non-matching region to reach a matching one — but they never fill the result heap. So the number of visits needed scales roughly inversely with how often the predicate is satisfied among the nodes the traversal naturally encounters. At a match rate of one in ten thousand, this is catastrophic in the ordinary sense: to collect ten results, the traversal must in expectation visit on the order of a hundred thousand nodes, assuming matching vectors are spread uniformly through the space. It is worse than that when they are not. If the matching slice is semantically clustered — one department's documents, one product version — it occupies a small region of the graph that the entry point may be far from, and the traversal spends its budget in the wrong neighbourhood entirely. And it can be worse still in the other direction: the engine may exhaust its exploration budget and return fewer than k results, or none, even though matching documents exist. That is a recall failure disguised as a latency problem. ## Why brute force wins at the extreme The saving grace is that high selectivity means a small absolute set. Take 0.01% of a fifty-million-vector collection: five thousand vectors. Computing five thousand distances is microseconds-to-single-digit-milliseconds of straight-line vectorised arithmetic, with no graph overhead, no revisits, and no approximation — recall is 1.0 by construction. The crossover is not subtle; it is orders of magnitude in the engine's favour once the matching set drops into the thousands. This is why the mature answer to "my filtered queries got slow" is usually not "tune the traversal harder" but "stop traversing". Mainstream vector engines estimate the number of matching vectors from payload index statistics and switch to exhaustive scoring of the matching subset below a configurable threshold. Some also build additional graph links among vectors sharing common payload values, so that frequently-used filters do not fragment the neighbourhood structure. ## The three regimes It helps to hold the whole curve rather than the pathological point. **Weak selectivity** — the predicate admits most of the collection, say a `status = "published"` filter that removes 3%. Ordinary ANN search plus a light post-filter is fine; almost every visited node matches. **Moderate selectivity** — the predicate admits a few percent to a few tens of percent. Filtering during traversal is the right tool: it costs somewhat more exploration than an unfiltered query, and it returns a full in-scope k without an over-fetch multiplier to guess. **Extreme selectivity** — the predicate admits a tiny slice. Pre-filter and score exhaustively. The crucial operational point is that **selectivity is a property of the query, not of the collection**. The same index serves a filter on a large tenant that admits 30% of vectors and a filter on a small tenant that admits 0.005%. A system that picks one strategy globally will be wrong for a large share of its traffic, and the failures will be concentrated on exactly the small tenants whose queries are cheapest to serve correctly. ## Diagnosing it in production The signature is a bimodal or heavy-tailed latency distribution that correlates with the predicate rather than with the query text — p50 unremarkable, p99 many times worse, and the slow queries all carrying narrow filters. Confirm by logging the estimated and actual match count per query alongside latency and result count. Two things frequently show up alongside: queries that came back short of k for no obvious reason (the traversal budget ran out), and a correlation between slowness and one particular tenant or version value. Common fixes in order of leverage: ensure the engine's selectivity estimate is accurate, since a wrong estimate is why it failed to take the brute-force path; adjust the threshold at which it switches; ensure payload fields used in predicates are actually indexed rather than scanned; and, for scopes that dominate the workload and are naturally disjoint — a large tenant, an archived partition — consider physically separating them into their own collection so the predicate disappears from the hot path entirely.