Filtered Vector Search: Why a Filter Collapses Recall

Retrieval works. You add a tenant filter, and the same query that returned ten good documents returns two. Sometimes zero. Nothing errored, latency looks fine, and narrowing the search made it worse.

The intuition that breaks here is a reasonable one: a filter means a smaller haystack, so the search should be easier. For a relational index that is true. For a graph vector index it is exactly backwards, and the reason is structural rather than a bug in anything.

A filter does not narrow the search, it fragments the graph#

A graph index like HNSW answers a query by walking. It starts at an entry point, moves to whichever neighbour is closer to the query vector, and repeats until it stops improving. The whole method depends on the graph being connected: there has to be a path of progressively closer nodes from where you started to the region where the answer lives.

Now apply a filter.

The vectors that satisfy your predicate are scattered through a graph that was built with no knowledge of that predicate. The routes between them run through vectors that do not satisfy it. Remove those from consideration and the walk cannot get from one eligible region to another. It terminates early, in whatever local pocket it happened to reach, and returns what it found there.

That is the collapse. Not a smaller result set because fewer things matched, but a worse result set because the search could not travel.

Selectivity is the variable#

Severity tracks selectivity: the fraction of the corpus that satisfies the filter. As selectivity falls, the number of eligible candidates in any node's neighbourhood shrinks in proportion, and the routes the walk depends on are progressively severed.

Which brings the uncomfortable arithmetic for anyone doing multi-tenancy on a shared index. Ten thousand tenants sharing one index means a typical tenant filter has a selectivity around one hundredth of one percent. That is not the edge of the problem, it is deep inside it.

The same applies to permission filters, and worse: the most restricted users, the ones with access to least, get the most selective filter and therefore the worst retrieval. Your security model and your recall are inversely coupled, and nothing in the system will tell you.

The three strategies#

Post-filtering. Search the index normally, then discard results failing the predicate. Recall within the search is intact because the index was untouched, but you searched the whole corpus and threw most of it away. Ask for ten and you may keep none. The usual workaround is over-fetching, asking for a thousand to keep ten, and over-fetching is a guess: you do not know selectivity in advance, and at low selectivity no affordable factor is enough.

Pre-filtering. Determine the eligible set first, then search only within it. Recall is excellent because the search is not fighting the graph. It needs either a structure that supports it, typically an inverted index producing an allow list, or a set small enough to scan.

Filtering during traversal. The walk is predicate aware, skipping ineligible nodes while still using them to route. This preserves recall best, at the cost of traversing more of the graph, which raises latency and CPU for precisely the highly selective filters that motivated it.

What real stores actually do#

This matters more than the theory, because the collapse is a property of naive filtering, not an inevitable property of graph indexes. Implementations differ enormously in how much of it they absorb, so the operative question is not whether graph indexes suffer this but whether yours mitigates it, and at what cost.

pgvector post-filters by default: with an HNSW or IVFFlat index, the WHERE clause is applied after the index scan. The candidate list is bounded by hnsw.ef_search, which defaults to 40, so a selective filter applied to 40 candidates can easily leave you with nothing. This is the origin of the common report of a LIMIT 10 query returning zero rows.

Version 0.8.0 added iterative index scans for exactly this. When too few rows match, the scan continues walking rather than giving up:

SET hnsw.iterative_scan = relaxed_order;  -- or strict_order

strict_order preserves exact distance ordering; relaxed_order permits slightly out of order results and gets better recall. There is still a ceiling: the scan stops at hnsw.max_scan_tuples, 20,000 by default, so a very selective filter can come back short regardless. For those cases partial indexes, partitioning, or exact search over the eligible set are better answers than tuning.

Weaviate pre-filters. It builds an allow list from an inverted index and the HNSW search adds only matching IDs to its results while still traversing all graph links, which is what preserves routing. Its documentation states that "the recall of a filtered search is typically not any worse than that of an unfiltered search," holding as filters shrink from 100% of the dataset down to 1%. Below a cutoff documented at around 15% of dataset size it switches to a brute force search over the matching subset, because at that point exhaustive search is simply faster.

Two stores, two completely different answers to the same question. Neither is wrong. But if you assumed your store behaved like the other one, your retrieval quality is not what you think it is.

The pleasing inversion#

Line the strategies up against selectivity and there is no single correct answer, there is a correct answer per query:

  high selectivity      post-filter with modest over-fetch is fine
  moderate selectivity  filter during traversal, accept the latency
  low selectivity       pre-filter, or scan the eligible set exhaustively

That last row is the interesting one. At very low selectivity the eligible set is small enough that exhaustive comparison is fast and exact. The regime where the index serves you worst is the regime where you do not need the index.

Which is precisely the reasoning behind an automatic flat search fallback. If your store has one, that row is already handled for you. If it does not, it is a thing you can implement yourself: resolve the eligible set, and if it is below some threshold, skip the index entirely and compare directly.

So what do you do about multi-tenancy#

Diagnosing the shared index as the problem is only useful if there is somewhere to go. There are three structures, and the choice is mostly about how many tenants you have and how uneven they are.

One shared index, filter per query. What most teams start with, because it is the default and it works beautifully in the demo with three tenants. It degrades as tenant count grows, since every new tenant lowers the selectivity of every existing tenant's filter. The failure is gradual and arrives long after the design decision, which is why it is rarely connected back to it.

One index per tenant. Selectivity stops existing as a concept, because there is no filter: each search runs against an index containing only that tenant's vectors, and recall is simply unfiltered recall again. The cost is index count. Every HNSW index carries fixed memory overhead regardless of how few vectors it holds, so ten thousand tenants means ten thousand graphs, most of them tiny and most of them idle. This is excellent for tens or low hundreds of substantial tenants and ruinous for a long tail of small ones.

Namespaces or partitions within one store. The middle option most mature vector stores offer under one name or another, and in Postgres simply partitioning the table or building partial indexes per tenant. Logically separate search spaces, shared infrastructure underneath. Usually the right answer when you have many tenants of wildly different sizes, because the store can treat a large tenant as its own index and a small one as a cheap scan.

The useful question is not which is best in general but where your corpus sits on one axis: tenant count against vectors per tenant. A thousand tenants with a million vectors each is a different system from a million tenants with a thousand vectors each, and only the first one needs an approximate index at all. For the second, per tenant exhaustive search over a thousand vectors is both exact and fast, and the index you were agonising over is pure overhead.

Measure two things nobody measures#

Selectivity, per filter pattern, over real traffic. This is the number that decides your strategy and almost nobody knows it:

SELECT filter_pattern,
       AVG(eligible_count::float / total_vectors) AS selectivity
FROM query_log
GROUP BY filter_pattern
ORDER BY selectivity ASC;

Anything below one percent is in the collapse regime. If tenant or permission filters appear there, your tenancy model is a retrieval quality problem and not just an isolation preference.

Filtered recall, separately from unfiltered recall. Teams benchmark recall once, unfiltered, at setup, and never again. The ground truth for a filtered query is a flat scan over the eligible set, which is cheap precisely because that set is small:

# Exhaustive comparison restricted to eligible ids is the correct answer
# by definition. Compare what the index returned against it.
def filtered_recall(index_results, eligible_ids, query_vec, k=10):
    exact = flat_scan(query_vec, restrict_to=eligible_ids, k=k)
    return len(set(index_results) & set(exact)) / k

Run that across your real filter patterns and you get a number per pattern. Teams who do this for the first time are routinely surprised, and the surprise is always in the same direction.

Quick reference#

Symptom	Likely cause
Filtered query returns fewer rows than LIMIT	Post-filtering against a bounded candidate list
Restricted users get worse answers than admins	Selectivity is inversely coupled to permissions
Recall fine in benchmarks, poor in production	Benchmarked unfiltered, serving filtered
Per-tenant search degraded after onboarding	Selectivity fell as the shared index grew

Decision	Rule
Which strategy	A function of selectivity, not a global setting
Very selective filter	Scan the eligible set. It is small, so it is cheap and exact.
Shared multi-tenant index	Verify filtered recall per tenant before assuming isolation is free
Changing store	Re-measure. Pre-filter and post-filter stores behave nothing alike.

The general shape#

Approximate indexes are approximations of a specific query. Change the query shape and the approximation's guarantees do not automatically follow, because they were never guarantees about your new question.

An ANN index promises approximate nearest neighbours over the corpus it was built on. A filtered query asks for approximate nearest neighbours over a subset chosen at query time, which is a different question the structure was not built to answer. Everything above is the industry working out how to bridge that gap, and the only part you control is knowing which bridge your store built.

---

Related reading: Self-Hosting Langfuse on Kubernetes for tracing the retrieval step so a bad answer can be traced to a bad retrieval, and You Changed the Prompt. Is the Model Better or Worse? for the evaluation discipline this measurement problem belongs to. Index types and the tradeoff triangle, build parameters, sharding and what it does to recall, the embedding pipeline, index lifecycle and measuring recall in production without ground truth are Production RAG Infrastructure on Kubernetes.