Filtered Vector Search: Why Metadata Filters Break HNSW Recall

Your retrieval eval scores 0.94 recall@10. You ship it. Then a customer with 400 documents in a 4-million-document index runs a query and gets three results back instead of ten — and the three are junk. Nothing errored. No log line. The ANN index just quietly stopped working for that tenant.

Filtered vector search is where most production RAG systems silently degrade, and the reason is structural: HNSW is a graph, and a metadata filter deletes most of the nodes from it.

TL;DR

• Post-filtering searches the full index, then drops rows that fail the predicate. If the filter passes 1% of rows, a top-100 ANN search returns roughly 1 matching row. You get short result sets and terrible recall.
• Pre-filtering (traversing only nodes that pass the predicate) breaks HNSW's navigability. The graph was built on the full dataset; removing nodes removes the edges that made it a small world.
• The collapse point is predictable. With expected degree D (2·M at layer 0), the filtered subgraph fragments into disconnected components around selectivity s ≈ 1/D — roughly 3% for the common M=16 default.
• Correlated filters (tenant, language, date range) are far worse than random ones at the same selectivity, because the surviving nodes cluster in one region the entry point can't reach.
• The fixes, in order of how much they actually work: partition the index by the high-cardinality filter key, brute-force below a size threshold, use iterative scan (pgvector 0.8+) or predicate-aware traversal (Qdrant filterable HNSW, ACORN-style two-hop expansion).

Why do metadata filters break HNSW recall?

Because HNSW navigates by following edges, and a filter deletes nodes without repairing the edges.

HNSW search is greedy descent over a proximity graph. You start at a fixed entry point in the top layer, hop to the neighbor closest to your query, descend a layer, repeat, and at layer 0 run a best-first search with a candidate list of size ef_search. It works because the graph is a navigable small world: long-range links at upper layers get you to the right neighborhood in O(log N) hops, and dense short-range links at layer 0 refine within it.

Now add WHERE tenant_id = 'acme'. Two options, both bad:

Post-filter. Run the ANN search normally, then discard non-matching rows. The index returns ef_search candidates ranked by distance; if the predicate passes fraction s of the corpus and matching rows aren't preferentially close to the query, you keep about s · ef_search of them. With pgvector's default hnsw.ef_search = 40 and s = 0.01, that's an expected 0.4 rows. You asked for 10. This is why the result set comes back short — a symptom people usually misdiagnose as "the data isn't there."

Pre-filter during traversal. Only expand nodes satisfying the predicate. Now the effective graph is the induced subgraph on the surviving nodes. Each survivor kept its edges only to other survivors: expected out-degree drops from D to s·D. The long-range links that made descent efficient are exactly the ones most likely to point at a deleted node, because they were chosen for distance diversity, not for your predicate.

The greedy search doesn't know it's stuck. It reaches a local optimum in a tiny connected fragment, exhausts its candidate list, and returns whatever it found. High confidence, wrong answer.

What selectivity does filtered vector search collapse at?

Around s ≈ 1/D, where D is the layer-0 degree. This is a percolation threshold, not a tuning artifact.

Deleting nodes independently with survival probability s from a graph with mean degree D gives a subgraph with mean degree s·D. Random graph theory says a giant connected component exists only when mean degree exceeds 1. Below that, the graph shatters into O(log N)-sized fragments.

HNSW's M parameter sets max neighbors per node at upper layers and 2·M at layer 0. With the near-universal M = 16, D ≈ 32, so the threshold is:

s* ≈ 1 / 32 ≈ 0.03   →  3% selectivity

Above ~10% selectivity, filtered search degrades gracefully — you lose some recall, you pay more hops. Between 1% and 10% it falls off a cliff. Below 1% the graph is confetti and recall is effectively random.

This is the single most useful number in this article, because it tells you the fix: either raise the effective degree, or stop using the graph.

Raising M to 48 moves the threshold to ~1%, at the cost of a much larger index and slower build. Two-hop expansion — the core idea in ACORN-style predicate-agnostic search — is better: when expanding a node, if a neighbor fails the predicate, expand its neighbors instead of discarding it. Effective degree becomes ~D²·s for the two-hop step, pushing the threshold near 1/D² ≈ 0.1% without storing more edges. You pay extra distance computations on the hops you would otherwise have wasted.

Why is a tenant filter worse than a random filter?

Because percolation math assumes nodes are deleted independently. Real filters are correlated with vector geometry, and correlated deletion is strictly worse at the same selectivity.

tenant_id, language, source, doc_type — all of these correlate strongly with embedding position. One tenant's documents occupy a tight region of the space. So the surviving subgraph isn't a thinned-out version of the original; it's one dense blob plus stragglers, sitting somewhere far from the global entry point.

The descent now has to cross a region where every node fails the predicate. Under strict pre-filtering there's no legal path. Under two-hop expansion there may be, if the blob is within two hops of somewhere reachable. Under post-filtering you'd need ef_search in the thousands.

Date-range filters are the sneaky one. created_at > now() - interval '7 days' looks like a cheap predicate, but if your corpus grows over time and embeddings drift with topic, recent documents cluster too. Every "search only recent" feature is a correlated filter.

How do you fix filtered vector search in pgvector?

Use iterative index scans (pgvector 0.8+) and know their cutoff. Before 0.8, pgvector post-filtered, full stop — the index returned ef_search rows, the executor applied the WHERE, and you got whatever survived.

-- Diagnose: does the plan filter after the index scan?
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, embedding <=> :q AS distance
FROM chunks
WHERE tenant_id = 'acme'
ORDER BY embedding <=> :q
LIMIT 10;
-- "Index Scan using chunks_embedding_hnsw ... Filter: (tenant_id = 'acme')"
-- with "Rows Removed by Filter: 39"  ->  classic post-filter starvation

-- pgvector 0.8+: keep pulling from the index until LIMIT is satisfied
SET hnsw.ef_search = 100;
SET hnsw.iterative_scan = strict_order;   -- or relaxed_order + outer re-sort
SET hnsw.max_scan_tuples = 20000;         -- hard stop; silently truncates past this

-- relaxed_order is faster but returns rows slightly out of distance order.
-- Re-sort in a materialized CTE if you care about exact ranking:
WITH candidates AS MATERIALIZED (
  SELECT id, embedding <=> :q AS distance
  FROM chunks
  WHERE tenant_id = 'acme'
  ORDER BY embedding <=> :q
  LIMIT 50
)
SELECT * FROM candidates ORDER BY distance LIMIT 10;

Iterative scan fixes the short result set. It does not fix recall below the percolation threshold — it just keeps walking a shattered graph until it hits max_scan_tuples and gives up. Check for that truncation explicitly; it's the failure mode that looks like success.

For a partitionable key like tenant_id, PostgreSQL declarative partitioning with a per-partition HNSW index beats every clever traversal trick. Each index contains only matching rows, so selectivity inside it is 1.0 and the graph is intact.

When should you skip the index entirely?

When the filtered candidate set is small enough that exact search is memory-bandwidth-bound and fast. This is more often than people expect.

Exact search is a dense matrix-vector product: n × d floats streamed once. For 100k vectors at 768 dims in float32 that's ~300 MB — a few tens of milliseconds on a single core at realistic memory bandwidth, and near-linear across cores. With int8 or binary quantization for a first pass, 4× to 32× less traffic.

So the routing rule is a size estimate, not a guess:

def choose_search_path(estimated_matches: int, dim: int, m: int = 16) -> str:
    """Route a filtered query. estimated_matches from a cheap COUNT or
    the DB's own cardinality statistics for the predicate."""
    degree = 2 * m
    corpus = get_corpus_size()
    selectivity = estimated_matches / corpus

    # Exact scan: bounded work, guaranteed recall.
    if estimated_matches * dim * 4 < 512 * 1024 * 1024:   # ~512 MB streamed
        return "brute_force"

    # Graph is shattered; ANN recall is unreliable regardless of ef_search.
    if selectivity < 2.0 / degree:                        # ~6% for M=16
        return "partitioned_index"                         # or brute_force

    return "hnsw_prefilter"

Qdrant does exactly this internally: it keeps payload indexes for filterable fields, estimates the cardinality of the filter, and falls back to exact search when the matching set is below a configurable full_scan_threshold. Above it, its "filterable HNSW" builds additional graph links constrained to payload-index partitions at build time, so the subgraph for a known filter stays connected. That works when your filters are declared up front; it does nothing for arbitrary runtime predicates.

IVF-family indexes degrade differently: a filter doesn't disconnect anything, it just makes each probed list yield fewer matches, so you raise nprobe and pay linearly. Slower ceiling, gentler cliff. For heavy filtering, that trade is often correct.

How do you catch this before production?

Evaluate recall stratified by filter selectivity. An aggregate recall@10 number averages a 0.99 unfiltered case with a 0.2 tail and reports 0.94.

Build ground truth with exact search on the filtered set, then measure per bucket:

BUCKETS = [(0, 0.001), (0.001, 0.01), (0.01, 0.05), (0.05, 0.25), (0.25, 1.0)]

for lo, hi in BUCKETS:
    queries = sample_queries_with_selectivity(lo, hi, n=200)
    r = []
    for q in queries:
        exact = brute_force(q.vec, q.filter, k=10)          # ground truth
        approx = index.search(q.vec, q.filter, k=10)
        r.append(len(set(exact) & set(approx)) / 10)
    print(f"s in [{lo},{hi}): recall@10={mean(r):.3f} n_returned={...}")

Two things to log alongside recall: how many rows the index actually returned (short results signal post-filter starvation) and whether any scan hit its tuple cap. Both are visible before recall moves, and both are unambiguous.

So: why do metadata filters break HNSW recall? Because HNSW's speed comes from graph navigability, and a filter deletes nodes from a graph whose edges were built without knowing about the filter. Post-filtering starves the result set at low selectivity; pre-filtering fragments the graph into disconnected components once selectivity drops below roughly 1/(2·M) — about 3% at the default M=16 — and correlated filters like tenant or date make it worse at the same selectivity. Fix it by partitioning the index on high-cardinality filter keys, brute-forcing small filtered sets where exact search is bandwidth-bound and cheap, and using iterative scan or predicate-aware two-hop traversal for the middle range. Then verify with recall measured per selectivity bucket, because the aggregate number will hide the failure.