Metadata Filtering Inside Vector Search

Every realistic retrieval query carries a predicate that has nothing to do with vector distance. Restrict to documents the caller is permitted to read. Restrict to the current version of a policy, not the three superseded ones. Restrict to a locale, a product line, a tenant, or a date range. Those constraints are exact, they are usually selective, and they are not expressible as a distance in embedding space. The vector index ranks by similarity and knows nothing about them, so the predicate has to be enforced somewhere, and where it is enforced decides both the correctness and the cost of the query.

The naive placement is after the search: retrieve the top k by similarity, then discard results that fail the predicate. This is wrong in a way that is easy to demonstrate. Take a corpus where 2 percent of chunks belong to the tenant issuing the query, and ask for the top 10 after filtering. The search returns the 10 nearest chunks overall; on average one of them belongs to the tenant, so the caller receives one result. Raising k to 500 recovers about 10 tenant chunks, at the cost of a 500-candidate search and a 490-item discard. For a predicate that selects 0.1 percent, k must exceed 10,000 to return 10 results. The failure is not gradual degradation; it is that the number of results is a product of the predicate’s selectivity and the search depth, and nothing in the interface says so.

The security version of this failure is worse than the quality version. A pipeline that filters after retrieval has already computed and, in some implementations, logged the identities and scores of documents the caller may not see. Filtering after the fact is a leak in the audit trail even when the response is clean.

The cost model for the whole arrangement follows from the shape of the index. The first stage is an approximate search whose work grows with how much of the space it must cover, described in Approximate Nearest Neighbour Indexes and the Recall They Trade Away, and a predicate changes that coverage requirement rather than the search algorithm.

Pre-filtering and its interaction with graph walks

The opposite placement applies the predicate first: compute the set of document identifiers that satisfy it, then search only among those. For an inverted index this is natural, since the predicate is itself an index lookup and the result is a posting list that can be intersected with the term lists.

For a graph-based vector index it is not natural at all. The walk moves from node to node through adjacency, and if the predicate excludes most nodes, the walk arrives at a node with no admissible neighbours and stops. The graph’s connectivity was built over the whole corpus; removing 98 percent of nodes leaves a graph whose remaining nodes may be in disconnected fragments, and greedy descent from an entry point can terminate in a fragment that is nowhere near the query. Pre-filtering a graph index with a selective predicate therefore produces low recall for a reason that has nothing to do with the beam width: the search never reaches the relevant region.

Cluster-based indexes behave differently. The predicate can be applied at the cell level first, discarding cells whose membership is entirely excluded, and the remaining cells are scanned normally. When the predicate correlates with the clustering, which happens when the predicate is something the encoder implicitly captured, such as language or document type, this is efficient. When it does not, the surviving cells are scattered and the number of cells that must be probed rises toward the number of cells that exist, at which point the index has degenerated into a scan with extra steps.

The strategies that actually get used

Four approaches cover the design space, and they differ in which quantity they bound.

The first is a bitmap or bitset of admissible identifiers, maintained alongside the index and passed into the search. Each node in the graph or each vector in a cell is checked against the bitset during the walk, and excluded nodes are traversed but not returned. Traversal-but-not-return is the key detail: the graph stays connected because excluded nodes remain as waypoints, and the cost is the check itself, one bit lookup per visited node. This preserves recall at the price of walking through material that will be discarded, so it degrades when the predicate is selective and the walk must cover many nodes to accumulate k admissible results. A dense bitset costs one bit per document, so a corpus of a hundred million documents needs 12.5 MB, which is small enough to keep resident.

The second is filtered insertion, where the predicate is part of the index key. Building a separate index per tenant, per locale, or per version makes every query a plain search inside a small index, which is the cleanest possible outcome. The cost is multiplied build time and memory when the number of partitions is large, and poor behaviour when partitions are small, because an index over a few thousand vectors has little structure to exploit. Partitioning by a low-cardinality attribute such as language is usually worth it; partitioning by a high-cardinality attribute such as user is usually not.

The third is iterative expansion. Search for k, apply the predicate, and if fewer than k survive, search again with a larger k or with a wider beam. This is post-filtering with a retry loop, and it is correct as long as the loop terminates and the depth limit is high enough. Its cost is unpredictable by construction: a query with a highly selective predicate pays several search rounds, and the latency tail is exactly the queries that were hardest to satisfy. Bounding the retries bounds the tail and accepts that some queries return fewer than k results, which is often the right trade as long as the caller is told.

The fourth is a two-index arrangement: a large unfiltered index for recall, and a small filtered index over the subsets that are queried most often. The common subsets, such as the current version of everything, are served from the small index; the rest fall back to bitmap filtering. This is the arrangement that follows from measuring which predicates dominate, and it is a maintenance cost rather than an algorithmic one.

def filtered_search(index, query, allowed, k, min_k):
    # allowed: set of ids the predicate admits; may be very selective
    # index exposes search(query, depth) -> (score, id) pairs and a size attribute
    depth = k
    while True:
        hits = index.search(query, depth)          # approximate, depth candidates
        kept = [(s, i) for s, i in hits if i in allowed]
        if len(kept) >= min_k or depth >= index.size:
            return kept[:k]
        depth = min(depth * 4, index.size)         # grow geometrically, bounded

Geometric growth is the detail that keeps the loop from becoming linear in corpus size for every selective query, and the min_k threshold is what allows a query to return fewer than k rather than scanning everything. Setting min_k equal to k makes the loop exhaustive in the worst case.

Selectivity is the number that predicts behaviour

The behaviour of every strategy above is governed by the fraction of the corpus the predicate admits, and by whether that fraction is spread evenly through the embedding space or concentrated.

A predicate admitting 50 percent of the corpus is nearly free under any strategy: post-filtering with a modest depth overshoot recovers k results, bitmap filtering discards half the visited nodes, and the index walk is unaffected. A predicate admitting 5 percent costs a factor of twenty in search depth under post-filtering and a factor of twenty in visited nodes under bitmap filtering. Below roughly 1 percent, post-filtering stops being viable and pre-filtering stops preserving recall, and the only workable answer is a dedicated index for the subset.

The distribution matters as much as the fraction. Access control predicates are often correlated with content: a tenant’s documents share vocabulary, a locale’s documents share a language, a version’s documents share terminology. When the predicate correlates with the embedding geometry, the admissible vectors form a coherent region, and a filtered walk stays inside it. When the predicate is uncorrelated, as with a random per-user permission set, the admissible vectors are scattered uniformly and every strategy pays the full factor.

The measurement that makes this tractable is a per-predicate selectivity histogram from real query logs, not an average. An average selectivity of 10 percent can hide a bimodal distribution where most queries admit 40 percent and a tenth admit 0.2 percent, and it is the small tail that determines the latency tail and the recall floor.

Where filtering belongs relative to reranking

A predicate can be applied at several points in the pipeline, and applying it later is always cheaper in search terms and always riskier in correctness terms.

Applying it at the index is safest: excluded material is never scored and never enters any log. Applying it after fusion but before reranking is nearly as safe and saves reranker work, which matters because reranking cost is linear in the candidate count. Applying it after reranking saves the most search work and is the arrangement that produces the “zero results” bug, because the reranker’s top 8 may contain nothing admissible while admissible material sat at ranks 30 to 60.

There is one case where late filtering is correct: when the predicate is not a restriction but a preference. Boosting recent documents, or preferring one locale when the query’s locale is ambiguous, is a reordering rather than a filter, and applying it after retrieval is exactly what a reordering is. Confusing the two is how a preference becomes a silent exclusion. A predicate that must never be violated is a filter; a predicate that merely influences order is a score adjustment, and the two belong in different stages.

The operational rule that follows: every predicate is classified as mandatory or preferential at query construction, mandatory predicates are pushed to the index or to a pre-search identifier set, and preferential ones become score adjustments applied after ranking. The classification is a property of the predicate, not of the query, and it should be recorded where the predicate is defined rather than re-decided at each call site.

The maintenance side

Filtered indexes are harder to keep correct than unfiltered ones because the predicate and the vector can change independently. A document moves from draft to published, which changes its admissible set but not its embedding. A document is edited, which changes both. The index update path must handle the case where only the attribute changed, since re-embedding is wasteful and skipping the update leaves the index serving the old attribute.

The usual design stores attributes in the same record as the vector, so an attribute change rewrites the record without re-running the encoder. That keeps the two consistent at the cost of making the record mutable, which conflicts with index structures that prefer immutable segments, and it pushes the problem into the compaction path covered in Incremental Index Maintenance. The alternative, a separate attribute store joined at query time, avoids mutability but adds a lookup per candidate, which is cheap for a shortlist and expensive inside a graph walk.