Why Filtered Vector Search Quietly Destroys HNSW Recall

Your RAG eval passes at 95% recall@10. You ship. A month later, support says answers go missing for some customers — but only the ones on the Enterprise plan, and only when they filter by document_type = "contract". Same index, same embeddings, same query. Recall for those queries is closer to 40%, and nothing in your dashboard says so.

Filtered vector search is where HNSW quietly stops being an approximate nearest neighbor index and starts being a random sampler. The failure is structural, not a tuning accident, and it does not show up in unfiltered benchmarks — which is exactly what everyone measures.

TL;DR

HNSW recall degrades under selective filters because greedy graph traversal can only walk through nodes that pass the filter; a sparse predicate shatters the graph into disconnected components and the search gets trapped in one of them.
Post-filtering (search top-k, then drop non-matches) returns fewer than k results and collapses toward zero as selectivity drops — a 1%-selective filter needs roughly 100x overfetch to survive.
Pre-filtering (mask nodes during traversal) keeps k results but silently loses recall, and cranking ef_search does not fix a disconnected subgraph.
The fix is a hybrid plan: brute-force the filtered subset when it is small, use filter-aware graph links or two-hop expansion (ACORN-style) when it is medium, and physically partition by tenant instead of filtering when the predicate is a tenant ID.
Measure recall per selectivity bucket against exact search. Aggregate recall hides this completely.

Why does HNSW lose recall when you add a filter?

Because HNSW search is a greedy walk over a graph, and a filter deletes most of that graph's edges.

Recall how the index works. Each vector is a node with roughly M bidirectional neighbor links per layer, chosen so the graph is navigable: from any entry point, greedy descent toward the query reaches the true neighborhood in a logarithmic number of hops. That guarantee is a property of the whole graph. It assumes every node is reachable through its neighbors.

Now add WHERE tenant_id = 42. The engine can still traverse the full graph and just discard non-matching results at the end (post-filtering), or it can refuse to expand into nodes that fail the predicate (pre-filtering). Pre-filtering is what most engines do for selective predicates, and it means the search now runs on the induced subgraph of matching nodes.

That subgraph was never built to be navigable. If 1% of your vectors match, each surviving node keeps on average 0.01 * M matching neighbors. With a typical M = 16, that is 0.16 — the expected number of usable outgoing edges is well below one. The subgraph is not a small world anymore; it is dust. Greedy search starts at the entry point, finds nearly nothing to expand into, exhausts its candidate list, and returns whatever local blob it landed in.

The tell is that raising ef_search barely helps. ef_search widens the beam, but a wider beam over a disconnected component still cannot cross to a component it has no edge into. You burn latency and get the same wrong answers.

When is a filter actually safe?

A filter is safe when it is either weakly selective or strongly correlated with the embedding space.

Three regimes, and they behave completely differently:

High selectivity (say >20% of rows match). Fine. The induced subgraph keeps enough edges to stay connected. Recall drops a point or two. Ship it.

Correlated filters. If language = "ja" matches 5% of the corpus, but Japanese documents cluster tightly in embedding space, the matching nodes are mostly neighbors of each other. The induced subgraph is locally dense and stays navigable, even at low selectivity. This is why some teams filter aggressively and never notice a problem — they got lucky with correlation.

Uncorrelated + sparse. The killer. created_at > '2026-01-01', tenant_id = 42, status = "published" — predicates that slice orthogonally through the semantic clusters. Matching nodes are scattered uniformly, every one of them is surrounded by non-matching neighbors, and the graph disintegrates. This is the case that quietly returns garbage.

So the question is never "is my filter selective?" It is "is my filter selective and uncorrelated with the vectors?" A random 1% sample of your corpus is the worst possible predicate.

Should you pre-filter or post-filter?

Neither, unconditionally. Post-filtering fails loudly; pre-filtering fails silently. Pick per query based on estimated selectivity.

Post-filtering has a clean cost model: to get k results at selectivity s, you must retrieve about k/s candidates. At s = 0.01 and k = 10, that is 1000 candidates from the ANN index — expensive but correct-ish. At s = 0.001, it is 10,000, and you are brute-forcing with extra steps. The nice property is that you know when it failed: you got back fewer than k rows.

Pre-filtering always returns k rows. They are just not the right ones. In production this is far more dangerous, because a RAG pipeline downstream will happily generate a confident answer from the wrong five chunks.

The plan every mature engine converges on:

Estimate the number of matching rows from a payload/attribute index.
If that count is below a threshold (a few thousand), skip the graph entirely and exact-scan the matching subset. Brute force over 5,000 vectors is sub-millisecond with SIMD.
If the count is large, use the HNSW graph with the filter applied as a mask.
Only the awkward middle band needs real cleverness.

Qdrant exposes this directly: full_scan_threshold in the HNSW config (expressed in KB of vector data) is the cutover point below which it brute-forces the filtered subset instead of walking the graph. It also builds additional links among points sharing a payload value, so the induced subgraph for indexed payload fields is navigable by construction. That second part matters more than the threshold — it is the difference between a filtered graph that works and one that shatters.

from qdrant_client import QdrantClient, models

client.create_collection(
    collection_name="docs",
    vectors_config=models.VectorParams(size=1024, distance=models.Distance.COSINE),
    hnsw_config=models.HnswConfigDiff(
        m=32,                      # more links = subgraph survives sparser filters
        ef_construct=256,
        full_scan_threshold=20000, # KB; below this, exact-scan the filtered subset
    ),
)

# THIS is the part people skip. Without a payload index, the engine cannot
# estimate selectivity and cannot build filter-aware links.
client.create_payload_index(
    collection_name="docs",
    field_name="tenant_id",
    field_schema=models.KeywordIndexParams(
        type="keyword",
        is_tenant=True,   # co-locate points by tenant on disk + in the graph
    ),
)

For pgvector, the equivalent lever is iterative index scans, added in 0.8.0. Without them, pgvector post-filters: the index returns ef_search candidates, the executor applies your WHERE, and you get back however few survive.

-- Without this, a selective WHERE clause silently returns < LIMIT rows.
SET hnsw.iterative_scan = strict_order;   -- or relaxed_order for better recall
SET hnsw.max_scan_tuples = 40000;         -- cap on how far it will keep scanning
SET hnsw.ef_search = 100;

SELECT id, chunk
FROM   documents
WHERE  tenant_id = 42 AND doc_type = 'contract'
ORDER  BY embedding <=> $1
LIMIT  10;

strict_order guarantees results come back in true distance order; relaxed_order lets the scan return slightly out-of-order results and generally recovers more recall for the same work. max_scan_tuples is your latency guard — and your silent-truncation risk, so log when you hit it.

How do you fix the sparse-uncorrelated case?

Three approaches, in increasing order of engineering cost.

Partition instead of filter. If the predicate is a tenant ID, it is not a filter — it is a namespace. Build one index per tenant (or use a tenant-aware payload index, as above). Search inside the partition is unfiltered, so the graph guarantees hold. This solves the single most common production case outright, and it is boring on purpose.

Two-hop expansion (ACORN-style). When a node's matching neighbors are too few, expand to neighbors-of-neighbors and keep the ones that pass the predicate. Since M^2 is typically 256+, two-hop expansion restores enough connectivity to survive selectivity around 1% without building a filter-specific index. Cost: more distance computations per hop, but far fewer wasted hops overall.

Raise M for filtered workloads. Each doubling of M roughly doubles the selectivity floor the graph tolerates, because the expected matching-neighbor count is s * M. Going from M=16 to M=48 lets you keep an expected edge at ~2% selectivity instead of ~6%. You pay in index size and build time. It is a blunt instrument, but it is one config line.

How do you actually measure this?

Compute exact recall per selectivity bucket. Do not trust an aggregate number.

import numpy as np

def recall_at_k(engine, exact, queries, filters, k=10):
    buckets = {}
    for q, f in zip(queries, filters):
        truth = set(exact.search(q, f, k))          # brute force over matching rows
        got   = set(engine.search(q, f, k))
        s = exact.selectivity(f)                     # fraction of corpus matching
        b = "%.0e" % (10 ** np.floor(np.log10(s)))
        buckets.setdefault(b, []).append(len(truth & got) / max(len(truth), 1))
    return {b: (np.mean(v), len(v)) for b, v in sorted(buckets.items())}

Run it with real production filters, not synthetic ones — the correlation structure is the whole game, and randomly generated predicates will not reproduce your tenant_id pathology. You want a table that reads: selectivity 1e-1 → 0.97, 1e-2 → 0.71, 1e-3 → 0.34. That table is the artifact. Once you have it, pick the brute-force cutover threshold from the point where graph recall falls below your bar, and set it there.

Also log, per query, the number of candidates examined and whether you hit max_scan_tuples or a full-scan fallback. Filtered ANN failures are invisible without that telemetry, because the API returns exactly k plausible-looking rows either way.

The short answer

Filtered vector search destroys HNSW recall because HNSW's navigability guarantee applies to the whole graph, and a selective predicate leaves you searching a sparse induced subgraph with fewer than one usable edge per node — so greedy traversal gets trapped in a disconnected component and returns confident, wrong neighbors. Post-filtering fails visibly (too few results); pre-filtering fails silently (wrong results). Fix it by making the engine choose per query: exact-scan small filtered subsets, use filter-aware payload indexes or two-hop expansion in the middle band, physically partition when the predicate is really a tenant, and measure recall bucketed by filter selectivity so the failure has somewhere to show up before your users find it.