Metadata Filtering Inside a Vector Index and the Selectivity Collapse

A query for “documents similar to this one, published after 2024, in German” is a vector query with a boolean constraint attached. Any system serving document retrieval ends up with such constraints, and the way the constraint is applied determines whether the result is correct, whether it is complete, and whether the latency is predictable. The three strategies, filter after search, filter before search, and filter during search, differ not in degree but in kind, and each has a selectivity range where it fails.

The naive strategy and its arithmetic

Post-filtering runs the vector search normally, taking the top $k’$ candidates, then discards those that fail the predicate and returns the survivors. If the caller asked for ten results, the index is asked for some larger number and the survivors are truncated to ten.

The arithmetic of that choice is unforgiving. If a predicate accepts a fraction $s$ of the collection and the filter is applied independently of similarity, the probability that a given result survives is $s$. Asking for $k$ results requires $k/s$ candidates in expectation, and the variance is large: the number of survivors among $k’$ candidates follows a binomial distribution, so with $s = 0.01$ and $k’ = 100$, the expected survivor count is one, and the probability of getting zero is about 0.37.

An implementation that returns whatever survives has therefore silently broken its contract: the caller asked for ten, got three, and no error was raised. The document that satisfies the predicate and is the eleventh-nearest neighbor is simply absent, and nothing in the response indicates it. This is the most common correctness defect in vector search deployments, and it is invisible to recall metrics computed without filters.

The fix within post-filtering is to escalate: request more candidates until enough survive or the candidate count exceeds the collection. Escalation works when $s$ is moderate and fails when it is small, because the required candidate count $k/s$ grows beyond the collection size. At $s = 10^{-4}$ on a million records, ten results need on the order of a hundred thousand candidates, which is a tenth of the collection and defeats the purpose of the index.

Pre-filtering and the traversal problem

Pre-filtering evaluates the predicate first, producing a bitmap or identifier set of qualifying records, and then restricts the vector search to that set. The correctness is immediate: the search only ever considers admissible records, so it returns exactly $k$ if $k$ admissible records exist.

The cost depends entirely on how the index consumes the restriction.

An inverted-file index handles it gracefully. The posting lists for the probed cells are intersected with the bitmap, and the scan proceeds over the intersection. The work is proportional to the number of admissible records in the probed cells, so a selective filter makes the scan faster rather than slower. The index does not need the records to be contiguous or in any particular order, because the scan is a linear pass over a list regardless.

A graph index handles it badly. The walk needs to move through intermediate nodes to reach the target region, and a pre-filter that forbids most nodes leaves the walk with no route. A node may be the only bridge between two regions and may itself fail the predicate; excluding it disconnects the graph. The result is that recall collapses not gradually but abruptly, at the point where the admissible set stops being connected under the graph’s edges. For a predicate accepting half the collection, the graph remains traversable and recall is fine. For one accepting one percent, the admissible nodes form small islands, and a search that starts on the wrong island returns nothing useful. The traversal itself is described in HNSW Layer Assignment and the Greedy Descent, and the connectivity argument applies unchanged to its layered structure.

This is the selectivity collapse, and its threshold is a property of the graph’s degree and the data’s clustering, not a universal constant. A graph with $M = 32$ links per node tolerates a sparser admissible set than one with $M = 8$, because there are more edges and therefore more chances that at least one leads onward. But no degree makes a graph traversable when the admissible fraction is a fraction of a percent and the admissible nodes are scattered.

import numpy as np

def postfilter_escalate(query, index, predicate, k, first=64, cap=None):
    """Ask for progressively more candidates until k survive, or the cap is hit."""
    cap = cap or len(index)
    want = max(k, first)
    while True:
        want = min(want, cap)
        cand = index.search(query, want)
        keep = [c for c in cand if predicate(c)]
        if len(keep) >= k or want == cap:
            return keep[:k]
        want *= 4       # geometric growth: few rounds, bounded overshoot

def prefilter_bitmap(predicate, ids):
    """One bit per record; the index intersects its candidate list with this."""
    bits = np.zeros((len(ids) + 7) // 8, dtype=np.uint8)
    for i in ids:
        if predicate(i):
            bits[i >> 3] |= 1 << (i & 7)
    return bits

The escalation loop is correct in the sense that it eventually returns the right answer when the cap allows it, but the geometric growth means the last request can be four times larger than needed. That overshoot is the latency cost of not knowing $s$ in advance.

Filter-aware construction

The third strategy builds the filter into the index structure. Two published approaches illustrate the space.

One augments each graph node with the metadata that constrains it, so that traversal can skip inadmissible nodes without losing connectivity. A node’s neighbor list is partitioned by attribute value, and the search follows only the partitions that can satisfy the predicate. When a predicate is common, the relevant partitions are dense and traversal works; when it is rare, the partitions are sparse and the same collapse appears. The improvement is that the collapse happens at a lower selectivity than with a plain graph, because the remaining edges are chosen to preserve connectivity within each partition.

Another builds multiple overlapping subgraphs, each covering a random subset of the collection, so that any predicate with enough qualifying records intersects at least one subgraph densely. The cost is that the collection is stored several times over in edge lists, and each query searches several subgraphs. The storage multiplier is the price of making arbitrary predicates traversable.

Both approaches share a limitation: they assume the predicate set is known at build time or that it can be evaluated cheaply during traversal. A predicate that requires a join, a full-text match, or a computation cannot be evaluated per-node inside the inner loop without destroying the loop’s cost model.

Choosing by selectivity

The practical rule is a piecewise strategy keyed on the admissible fraction $s$, with thresholds measured per collection.

At high selectivity, with most of the collection admissible above a few percent, pre-filtering with a graph index is fine and cheapest, since the graph remains connected. At low selectivity, where a tiny fraction is admissible, the admissible set is small enough that a brute-force scan over the admissible records is competitive with any index. Scanning ten thousand admissible records at 768 dimensions is thirty megabytes of memory traffic, which is a fraction of a second at ordinary bandwidth, and it is exact. The index is not needed.

The difficult band is the middle: selective enough that post-filtering needs escalation, not selective enough that a scan is cheap, and sparse enough that graph traversal breaks. In that band, the strategies that preserve connectivity inside the index are the ones that work, and they are the reason the problem has a literature.

An additional consideration is the distribution of the predicate. Independence between the predicate and the vector geometry is the assumption behind the $k/s$ arithmetic, and it is often false. A filter on publication date correlates with topic, which correlates with position in the embedding space. When the predicate selects a spatially contiguous region of the collection, the query’s nearest admissible neighbor may be much farther than its nearest neighbor overall, and post-filtering must search a much wider radius. When the predicate selects a scattered set, the arithmetic holds. Estimating the correlation requires a sample and a comparison of distances, and it changes the required over-fetch by a large factor. Note also that “distance” here means whatever score the index was built around, so a filter that interacts with vector length behaves differently under the normalized cosine of Cosine Similarity and the Geometry of Normalized Embedding Vectors than under raw inner product.

A second consideration is that filters are often multi-valued: a document has several tags, a product belongs to several categories, and the predicate is a union. A union of rare predicates can have a high total selectivity while each individual predicate is rare, so the strategy must be chosen on the union, not on the components. Bitmap intersection makes this cheap to evaluate but does not change the traversal problem.

What the response should say

A filtered vector query has two ways to be honest about incompleteness: return fewer results with an indication that the filter exhausted the collection, or refuse and ask the caller to loosen the constraint. Silently returning a short list is the failure mode to avoid, because the short list looks like a complete answer.

The response should also distinguish “no admissible record is similar” from “the search did not find an admissible record”. The first is a data property; the second is an approximation artifact. A threshold on the returned distance, combined with an exact scan over the admissible set when the candidate count is small, gives a defensible answer either way.

None of this is specific to a particular index family. The same arithmetic applies to hashing, where a filter applied after retrieval has the same binomial thinning, and to quantization, where the candidate list is shorter and the thinning is proportionally worse. What changes between families is only the selectivity at which the structure stops being traversable, and that number is always empirical. The related problem of choosing how many candidates to fetch before reranking, and how that interacts with filters, is treated in Over-Fetch and Exact Reranking in Two-Stage Vector Retrieval.