Filtered vector search and the recall cliff

What it is

Filtered vector search is approximate nearest-neighbour retrieval constrained by a metadata predicate: "the 10 nearest vectors that this user may read", or "in French", or "created in the last 30 days". It sounds like adding a WHERE clause to a similarity query. It is not, and the difference is the reason this topic exists.

The recall cliff is what happens when the filter is selective. An approximate index is a data structure built over the whole corpus, tuned to visit a small number of candidates and stop. Apply a filter that eliminates 99 percent of the corpus and the candidates it visits are almost all rejected, so it returns far fewer than k results, or returns the wrong ones, or degrades to something close to a full scan. Recall does not decline smoothly with selectivity; it falls off a cliff at some selectivity threshold that depends on the index and its parameters.

Two things it is confused with. It is not the same as post-filtering, which is one (bad) implementation strategy rather than the problem itself. And it is not a tuning problem you can always parameter your way out of: past a certain selectivity, no ef_search value makes an HNSW graph traversal efficient, because the graph's connectivity assumes the full node set.

The problem it solves, and the problem it creates

Every real retrieval system has filters. Multi-tenant SaaS filters by tenant. Enterprise RAG filters by document ACL. Multilingual search filters by language. E-commerce filters by category, price and availability. A vector index without filtering is a demo.

The problem it creates is that ANN indexes buy their speed from a structural assumption. HNSW's hierarchical graph is navigable because each node has a carefully chosen set of neighbours; IVF's inverted file works because the corpus partitions into clusters whose centroids you can rank. A filter breaks both assumptions: the graph's neighbours may all be filtered out, and a cluster may contain no surviving members.

And the failure is silent. You get results. They are just not the nearest neighbours, and nothing in the response says so.

Mechanics

The three strategies

Post-filtering. Retrieve top-k from the index, then discard non-matching results.

retrieve k=10 ignoring the filter  ->  10 candidates
apply filter                        ->  0-2 survive

This is wrong for two independent reasons. Recall: with a 1 percent selective filter, the expected number of survivors from a top-10 is 0.1, so you return nothing most of the time. Over-fetching to compensate (retrieve 1,000 to get 10) works only until selectivity gets worse, and the required over-fetch factor is $1/s$ for selectivity $s$, which is unbounded. Security: if the filter is an access-control predicate, the number of results you drop leaks information about documents the user cannot see. A user who searches for a term and gets zero results after filtering has learned that matching documents exist.

Never post-filter an ACL. That is the sentence to say.

Pre-filtering (exact). Evaluate the predicate first, then brute-force search the surviving set.

apply filter  ->  8,000 of 5,000,000 docs
exact k-NN over 8,000  ->  perfect recall

Perfect recall, cost linear in the surviving set. For 8,000 vectors of 768 dimensions this is roughly 6 million multiply-adds, which is a couple of milliseconds and entirely fine. For 8 million survivors it is not.

Filtered traversal (the modern default). Walk the ANN structure but reject non-matching nodes during search, using a bitset of permitted document ids. HNSW visits a node, checks the bitset, and only counts it toward the result set if it passes; IVF probes more lists to compensate for the ones the filter empties.

This is what Lucene, FAISS and the dedicated vector databases actually do, and the important part is the fallback: below some estimated surviving-set size, they abandon the graph and do the exact scan instead, because exact over a small set is both faster and correct.

Why HNSW degrades, precisely

HNSW search is a greedy walk. From an entry point, it examines the current node's neighbours, moves to the closest unvisited one, and maintains a candidate list of size ef_search. It terminates when the candidate list stops improving.

With a selective filter, most neighbours fail the predicate. The walk still has to visit them to find out, so the work per useful candidate rises by roughly $1/s$. Worse, the graph can become disconnected with respect to the filter: a region of matching nodes may be reachable only through non-matching nodes, and a greedy walk that terminates on local improvement never gets there. That is not slowness, it is a wrong answer, and no amount of ef_search reliably fixes it because the termination condition is local.

The practical shape:

Filter selectivity	Behaviour
> 50% pass	Barely distinguishable from unfiltered
5% to 50%	Raise `ef_search` (2x to 5x) and recall holds
0.1% to 5%	The cliff. Graph traversal is both slow and lossy
< 0.1%	Exact scan over survivors is strictly better

The thresholds move with M, ef_construction and corpus size; the shape does not.

How the engines actually do it

// OpenSearch / Elasticsearch: filtered kNN. The engine estimates the number of
// surviving documents and chooses between graph traversal and exact search.
{
  "knn": {
    "field": "embedding",
    "query_vector": [ ... ],
    "k": 10,
    "num_candidates": 200,
    "filter": { "terms": { "acl_group": ["eng", "eng-platform"] } }
  }
}

Lucene's implementation is the clearest to reason about: it materialises the filter as a bitset, and if the cardinality of that bitset is small relative to the segment, it runs exact search over the matching documents instead of traversing the graph. So the fallback is automatic, and the thing you must get right is making the filter cheap to evaluate: a keyword term filter over a doc-values field, not a script.

# FAISS: an IDSelector restricts the search, and nprobe must rise to compensate
# for lists the filter empties out.
sel = faiss.IDSelectorBatch(permitted_ids)
params = faiss.SearchParametersIVF(sel=sel, nprobe=64)   # up from a default of 8
D, I = index.search(query, k, params=params)

The structural fix: partition instead of filter

The strongest answer is often to make the filter unnecessary by putting it in the index topology.

One index per tenant. A filter on tenant_id becomes a routing decision. Perfect recall, no cliff, and blast-radius isolation for free. It stops scaling somewhere in the low thousands of tenants because of per-index overhead, and it is wrong for tenants with ten documents each.
One index per language. Removes a language filter and lets you use the correct analyser and embedding model per language, which improves quality independently.
Time-based indices with routing. A last 30 days filter becomes "query these three indices", which is how log and time-series search has always worked.

The general rule: a high-cardinality, high-selectivity filter that appears in every query is not a filter, it is a partition key. Recognising that is the architectural version of the answer, and it is the one that separates a design review from a parameter-tuning exercise.

A worked example: enterprise RAG with document ACLs

5 million documents, HNSW with M=16, 768-dimensional embeddings. Each user can read on average 8,000 documents, so selectivity is 0.16 percent. Requirement: recall@10 above 0.95, p99 under 150 ms.

Post-filter, k=100. Expected survivors: $100 \times 0.0016 = 0.16$. The user gets zero results for almost every query. Also leaks existence. Rejected in the design, not in production.

Post-filter with over-fetch. To expect 10 survivors you need $10/0.0016 = 6{,}250$ candidates, and to be confident of 10 you need several times that. Retrieving 20,000 candidates from HNSW and discarding 99.84 percent of them is both slow and absurd, and it still fails for a user with 200 accessible documents.

Filtered graph traversal. At 0.16 percent selectivity we are below the cliff. Measured behaviour on this shape: recall@10 lands somewhere around 0.6 to 0.7 depending on ef_search, latency rises several-fold because the walk visits thousands of rejected nodes, and raising ef_search improves recall with steeply diminishing returns. Not viable alone.

Exact search over the permitted set. 8,000 vectors x 768 dimensions = 6.1 million multiply-adds per query. On a single modern core with SIMD that is on the order of 2 to 4 ms, and it is embarrassingly parallel across shards. Recall 1.0. This is the answer, and the surprising part is that the "slow" exact method is faster than the "fast" approximate one at this selectivity, because approximate search over a 5-million-node graph that rejects 99.84 percent of what it visits is not fast.

The architecture that ships. A two-layer authorisation model:

Group-level pre-filter in the index. Documents carry an acl_groups keyword field. The query filters on the user's groups (typically tens of values, not thousands of document ids), which is cheap to evaluate and turns into a bitset the engine can use for the exact-search fallback.
Document-level check after retrieval, against the authoritative permissions service, for the handful of documents actually returned. This catches per-document exceptions and revocations the index has not yet seen.

Layer one makes the search correct and fast; layer two makes it right, because the index is a replica of the permission state and replicas lag. Both layers, always, and the reason is worth saying: the index is eventually consistent with the ACL system, and a stale index that grants access is a security incident rather than a relevance problem.

The remaining lever is index lag as an SLI. Measure the time between a permission change and the index reflecting it, alert on it, and make the document-level check the thing that guarantees correctness in the window.

Production evidence

Lucene (and therefore Elasticsearch and OpenSearch) implements filtered kNN by materialising the filter as a bitset and choosing between graph traversal and exact search based on the surviving cardinality relative to the segment. Both vendors document the behaviour and warn that restrictive filters change the execution strategy, which is the clearest public statement that this is a structural issue rather than a tuning one.

FAISS exposes IDSelector variants for restricted search and its documentation is explicit that filtering interacts with nprobe: with lists emptied by the filter, you must probe more of them to find k results.

ACORN (Patel et al., SIGMOD 2024) is the research response, a predicate-agnostic HNSW variant that builds a denser graph specifically so that filtered traversal stays connected. Its existence is good evidence that the cliff is inherent to vanilla HNSW rather than an implementation defect, and naming it is a strong depth signal.

Weaviate, Qdrant and Pinecone each publish their filtering strategy, and all three converge on the same design: maintain a filterable structure alongside the vector index, estimate selectivity, and switch between filtered traversal and exact search at a threshold. Independent convergence on the same answer is the best kind of evidence.

The debate

The credible alternative to solving this is avoiding it: partition the index so the filter becomes routing. For a tenanted product that is often just correct, and it also gives you noisy-neighbour isolation, per-tenant reindexing and easier deletion for compliance.

Its limits are real. Per-index overhead (memory for the graph, file handles, cluster state) makes thousands of tiny indices expensive, and a query that must span tenants becomes a scatter-gather over all of them. Cardinality decides: partition when the filter has tens to low thousands of distinct values and appears in every query; filter when it has millions of values or varies per query.

Between the search strategies: pre-filter with exact search when the surviving set is small (say under 50,000 vectors), filtered traversal when selectivity is above a few percent, and never post-filter an access-control predicate. The threshold is measurable on your own hardware in an afternoon, and measuring it is the deliverable.

Filtered ANN is the wrong thing to optimise when the filter is a partition key in disguise, when the corpus is small enough that exact search over everything is affordable (below roughly a million vectors, exact brute force with SIMD is often under 50 ms and removes an entire category of tuning), or when the real problem is that first-stage recall is poor for reasons unrelated to filtering.

Follow-up Q&A

"Pre-filter or post-filter, and why?" Pre-filter, always, for two reasons. Recall: post-filtering retrieves top-k from the whole corpus and then discards, so with a 1 percent filter you expect 0.01k survivors and typically return nothing. Security: the count of dropped results leaks the existence of documents the user cannot see, which is an information disclosure even when the content is never returned. The nuance is that "pre-filter" covers two implementations, exact search over the surviving set and filtered graph traversal, and which one is right depends on selectivity.

"Your filtered searches return 3 results when you asked for 10. What is happening?" Either post-filtering (the index returned 10 and 7 were dropped), or filtered traversal that terminated early because the graph walk ran out of matching neighbours before filling the candidate list. Distinguish them by running the query without the filter and seeing whether you get 10. If it is traversal, raise ef_search or num_candidates and see whether recall recovers; if it does not recover with a large increase, you are below the cliff and need exact search over the surviving set.

"How do you decide the threshold between exact and approximate?" Measure it. Take a representative query set, sweep filter selectivity, and plot recall@10 and p99 latency for both strategies. The crossover is where exact search's linear cost exceeds filtered traversal's, and on typical hardware with 768-dimensional vectors it lands somewhere in the tens of thousands of surviving vectors. Then implement the switch based on an estimated surviving count, which most engines do for you, and validate that their estimate is accurate for your filter shapes.

"How does this interact with deletes?" Badly, and it is worth raising unprompted. HNSW does not support true deletion: implementations mark nodes as deleted and skip them during traversal, which is exactly a filter, so a corpus with many deleted nodes has a permanently degraded graph. That is why periodic index rebuilds are operational necessities rather than optimisations, and why a workload with high churn may be better served by IVF-PQ, where rebuilding a single list is cheaper than rebuilding a graph.

"Design the ACL layer for this." Two layers. A group-level filter in the index using a low-cardinality keyword field, because filtering on tens of group ids is cheap and gives the engine a usable bitset; then a document-level authorisation check against the source of truth for the handful of documents you actually return. Layer one gives correctness and speed at query time, layer two covers the window where the index is stale relative to the permission system. Track index lag as an SLI, because that lag is your exposure window, and never return a count of filtered-out results.

Common misconceptions

The most common is that filtering is a WHERE clause. In a relational database the filter reduces work; in an ANN index it can increase work by orders of magnitude and reduce correctness at the same time.

The second is that a large ef_search fixes low recall under a selective filter. It helps in the middle band and does not help below the cliff, because the failure there is graph disconnection under the filter, not insufficient exploration.

The third is that post-filtering is merely inefficient. It is also an information leak whenever the filter is a permission, and that reframes it from a performance bug to a security one.

Interview delivery note

Say this: "Never post-filter, for two reasons. Recall collapses, because with a 1 percent selective filter a top-100 gives you one survivor. And if the filter is an ACL, the number of results you drop leaks the existence of documents the user can't see. Pre-filter instead, and then the choice is between filtered graph traversal and exact search over the surviving set. Below roughly a percent selectivity, HNSW walks off a cliff, because most neighbours fail the predicate and the graph can be disconnected with respect to the filter, so exact search over the survivors is both faster and correct. Above that, raise ef_search and traverse."

The depth signal is naming the disconnection, not just the slowness: "raising ef_search doesn't reliably fix it below the cliff, because the greedy walk terminates on local improvement and a region of matching nodes can be unreachable through non-matching ones." Then close with the architectural move: "and if the filter is high-cardinality and in every query, it isn't a filter, it's a partition key."

The Staff & Team Lead Interview Reference