Filtered Vector Search

A multi-tenant assistant runs one index of 200M vectors and filters each search to the requesting tenant. Large customers are fine. Customers with 5,000 documents get poor results and three times the latency, and nothing in the dashboards explains why, because the index is healthy, memory is fine and query volume is low.

The cause is that an approximate index and a predicate know nothing about each other. A graph index walks from node to node by vector similarity; the tenant field plays no part in that walk. For a tenant holding one part in 40,000 of the corpus, almost every node the walk visits is discarded after the fact, so the search either returns too few results or expands until it is no longer fast.

Why it matters

Filtering is not an edge case. Access control, tenancy, language, recency windows and document type are present in nearly every production retrieval system, and each is a predicate. Recall measured without the filter is not the recall users get, so a system can benchmark beautifully and behave badly for exactly the customers most likely to notice.

It is also the most common reason a vector search "works in the demo". A demo has one tenant and no filter.

Implementation patterns

• Pre-filter by partition. Give each tenant, language or time bucket its own index or namespace, so the predicate becomes routing rather than filtering. The small-tenant case turns into exhaustive search over a few thousand vectors, which is sub-millisecond with perfect recall.
• Post-filter with an inflated candidate set, viable only for low-selectivity predicates. To land 10 results at one part in 40,000 you need roughly 400,000 candidates, which is no longer approximate search.
• Filter-aware traversal, where the engine evaluates the predicate during the graph walk and keeps expanding until enough passing candidates are found. Several engines support this and it holds recall far lower down the selectivity curve, at a latency cost that grows as the filter tightens.
• Hybrid routing by size. A dedicated index above a document threshold, a shared partition for the long tail of small tenants, searched exhaustively.
• Always report selectivity in the query log: the number of vectors passing the predicate. It is the field that explains every slow query of this class.

Industry example

The behaviour is a property of the graph algorithms rather than of any product. HNSW, published in 2016 and the basis of most production vector indexes since, builds a navigable small-world graph whose edges encode vector proximity only. Every engine that implements it inherits the same interaction with predicates, which is why the major vector databases have each shipped some form of filter-aware traversal or per-partition routing since around 2022 rather than relying on post-filtering.

Failure scenarios

• Silent recall collapse for small tenants, invisible in aggregate metrics because they are a small share of traffic.
• Latency triples under a tight filter while CPU stays moderate, because the walk is expanding rather than saturating.
• A filter applied after the top-k cut, which returns fewer than k results and looks to the application like an empty corpus.
• Access control implemented as a post-filter, where a race between a permission change and a cached candidate set exposes a document. The correct place for authorisation is partition routing, not a predicate on results.
• Recency filters that degrade over time as the corpus grows and "last 30 days" becomes ever more selective.

Trade-offs

Partitioning buys correctness and isolation and pays in per-index overhead: each graph carries fixed memory and each rebuild is a separate job. At tens of thousands of tenants that overhead dominates, and hashing tenants into a bounded number of shards becomes the better shape. Partitioning also forecloses cross-partition search: a query that must span tenants now fans out to every partition and merges, which is the cost you removed reappearing elsewhere.

When not to use it

If the predicate passes more than roughly 10% of the corpus, leave it as a filter on one index. The walk is barely perturbed, recall holds, and partitioning adds operational surface for nothing. Equally, if the filtered subset is small enough to scan exhaustively — under about 50,000 vectors — drop the ANN index for that path entirely and compute exact distances; it is faster, simpler and exactly correct.

Interview question

Q: Your vector search returns good results for your five largest customers and poor results for the other four hundred. Latency is worse for the small ones. Walk me through the diagnosis and the fix, and tell me what you would measure to prove the fix worked.

What a strong answer covers: recognising selectivity rather than corpus size as the variable; explaining why a graph walk cannot honour a predicate it does not encode; rejecting a global ef_search increase as a tax on healthy tenants; proposing partitioning with a size threshold; and proving it with per-tenant recall at 10 against a labelled set plus p95 latency bucketed by predicate selectivity.

Quick check

Quiz: Why does raising ef_search fix filtered recall only partially and at a cost? — It widens the search for every query including the unfiltered ones, so healthy tenants pay latency to partly compensate for a walk that still cannot see the predicate.

Flashcard: A tenant filter selects 1 in 40000 vectors from an HNSW index. What happens? — The graph walk discards almost everything it visits, so recall collapses and latency rises; partition by tenant so the predicate becomes routing.