Filtered Vector Search: Why HNSW Recall Collapses at 1% Selectivity

You ship a RAG system. Retrieval looks great. Then a customer asks for per-tenant isolation, you add WHERE tenant_id = 'acme' to the vector query, and nothing visibly breaks — the API still returns 10 chunks, the LLM still answers, latency is fine. Six weeks later someone notices the answers got worse for small tenants.

Nothing broke loudly because filtered vector search doesn't fail with an exception. It fails by silently returning the 10 nearest neighbors that the graph traversal happened to reach, which is not the same set as the 10 nearest neighbors that match your filter. Below roughly 1-3% filter selectivity, those two sets barely overlap.

TL;DR

• HNSW is a graph, and a filter deletes nodes from it. Search is greedy traversal over neighbor links; excluded nodes cut the edges the traversal needs to walk.
• The cliff is a percolation threshold. With layer-0 degree M0 = 2M (default M=16 → 32), retaining a fraction p of nodes leaves mean retained degree ≈ 32p. Below p ≈ 1/32 ≈ 3% the matching subgraph shatters into disconnected components and greedy search can only see the component it started in.
• Post-filtering under-returns. Fetch ef_search candidates, then filter, and you get fewer than k rows — pgvector before 0.8.0 did exactly this.
• Fixes, in order of preference: partition/shard by the filter key; use a flat (brute-force) index for small filtered sets; enable iterative index scans (hnsw.iterative_scan in pgvector 0.8+); use filter-aware graphs (Qdrant's payload subgraph links, Weaviate's ACORN strategy).
• Measure filtered recall@k against brute force per selectivity bucket, not global recall. Global recall@10 of 0.98 tells you nothing about the 0.5%-selectivity tenant.

Why does adding a metadata filter break HNSW recall?

Because HNSW recall depends on graph connectivity, and a filter is a node deletion on that graph.

HNSW (Hierarchical Navigable Small World) doesn't scan vectors. It builds a multi-layer proximity graph: every node links to M neighbors chosen to be a mix of near and long-range, layer 0 holds all vectors with up to M0 = 2M links, and upper layers hold exponentially thinning samples that act as an express lane. A query enters at a fixed entry point in the top layer, greedily hops to whichever neighbor is closer to the query vector, descends a layer when it hits a local minimum, and at layer 0 runs a best-first search maintaining a candidate heap of size ef_search.

The whole thing works because of the small-world property: any node is a few hops from any other. That property is a function of the edge set. When you filter, you're asking for nearest neighbors within the induced subgraph on matching nodes — and nobody built an index for that subgraph.

What selectivity is the actual cliff?

Take random (uncorrelated) filters retaining a fraction p of nodes. Each surviving node keeps each of its ≈ M0 neighbors with probability p, so mean retained degree is d̄ ≈ M0 · p. Random graph percolation (Molloy–Reed) says a giant connected component exists roughly when mean degree exceeds 1. So:

p_c ≈ 1 / M0 = 1 / (2M)

M = 16  → M0 = 32 → p_c ≈ 3.1%
M = 32  → M0 = 64 → p_c ≈ 1.6%
M = 64  → M0 = 128 → p_c ≈ 0.8%

Below p_c, the matching set is not one graph — it's confetti. Traversal reaches one fragment and reports whatever is in it as "nearest."

Two caveats make reality worse than this estimate:

Greedy search is not BFS. Even inside a connected component, best-first search with heap size ef_search terminates when no candidate improves the frontier. Getting from fragment to fragment often requires walking through non-matching nodes whose distance is worse — exactly the moves greedy search refuses to make. Degradation starts well above p_c, typically in the 5-20% band.

Real filters are correlated with the embedding space. lang = 'ja', doc_type = 'invoice', tenant_id = 'acme' — these select clusters, not random samples. That cuts both ways: the matching set is more internally connected (good), but it sits in one region of the space while the entry point sits somewhere else (bad). The search descends the hierarchy toward the globally nearest region, and if that region is filtered out, you land in a local minimum with no matching neighbors to escape through.

So you get two distinct failure regimes: shattering on uncorrelated low-selectivity filters, and unreachability on correlated ones. Different fixes.

Why does my filtered query return fewer than k rows?

That's post-filtering. The engine asks HNSW for ef_search candidates by pure vector distance, then discards the ones that fail the predicate. If 1% match, an ef_search=40 scan returns ~0 rows.

pgvector before 0.8.0 did this. The reproduction is embarrassingly simple:

-- pgvector < 0.8.0, or 0.8+ with iterative_scan = off
CREATE INDEX ON chunks USING hnsw (embedding vector_cosine_ops)
  WITH (m = 16, ef_construction = 64);

SET hnsw.ef_search = 40;  -- default

SELECT id FROM chunks
WHERE tenant_id = 'acme'          -- 0.4% of 5M rows
ORDER BY embedding <=> :q
LIMIT 10;
-- returns 0-2 rows. No error. No warning.

pgvector 0.8.0 added iterative index scans, which re-enter the index and keep scanning until LIMIT is satisfied or a budget is exhausted:

SET hnsw.iterative_scan = relaxed_order;  -- off | strict_order | relaxed_order
SET hnsw.max_scan_tuples = 20000;         -- default; raise for very low selectivity
SET hnsw.scan_mem_multiplier = 4;         -- work_mem multiple for the scan buffer
SET hnsw.ef_search = 100;

strict_order guarantees results come back in exact distance order; relaxed_order allows slight reordering and gets better recall for the same budget (re-sort in your app if order matters). max_scan_tuples is the honest knob — it's a hard ceiling on effort, and when you blow through it you get partial results again, just later. For a tenant holding 0.4% of 5M rows, 20k scanned tuples covers ~80 matching rows in expectation. That may be enough for k=10; it is not enough for a reranker that wants 200 candidates.

How do I fix filtered vector search?

In roughly this order:

1. Partition by the filter key when the key is low-cardinality and always present. Multi-tenancy is the obvious case. One index per tenant (or a tenant-aware payload index in Qdrant, a partition key in Milvus, a partitioned table with per-partition HNSW in Postgres) turns a 0.4%-selectivity filtered search into a 100%-selectivity unfiltered search. Selectivity becomes 1.0 and every problem in this post disappears. The cost is index-count overhead and worse behavior on cross-tenant queries.

2. Brute-force below a threshold. If the filtered set is a few thousand vectors, exact scan over 3k × 1024 dims is a handful of milliseconds and gives recall 1.0. Qdrant does this automatically via cardinality estimation and a full_scan_threshold; Weaviate offers a flat index and a dynamic index that switches from flat to HNSW as a collection grows. In Postgres, a partial index or simply letting the planner pick a sequential scan for a highly selective predicate achieves the same thing — check EXPLAIN ANALYZE and stop assuming the index is a win.

3. Filter-aware graph construction. Qdrant builds additional links restricted to payload-defined subgraphs (tuned with payload_m) so that filtered traversal has real edges to walk. ACORN — which Weaviate exposes as filterStrategy: acorn — takes the predicate-agnostic route: it builds a denser graph and, during traversal, expands through the two-hop neighborhood of filtered-out nodes, effectively bridging fragments at query time. Both trade index size and build time for filtered recall.

4. Raise ef_search last. It's the reflex fix and the weakest one. It widens the frontier but cannot cross a disconnected component boundary, so it buys you linear latency for sublinear recall in exactly the regime where you need it.

How do I measure filtered recall@k?

Bucket by selectivity, compare against exact brute force, and never report a single global number.

import numpy as np

def filtered_recall_at_k(index_search, embeddings, mask, queries, k=10):
    """index_search(q, k, mask) -> list[int] of row ids from the vector DB."""
    sub_ids = np.flatnonzero(mask)
    sub = embeddings[sub_ids]
    sub /= np.linalg.norm(sub, axis=1, keepdims=True)

    recalls = []
    for q in queries:
        q = q / np.linalg.norm(q)
        truth = sub_ids[np.argsort(-(sub @ q))[:k]]        # exact, filtered
        got = index_search(q, k, mask)                      # ANN, filtered
        recalls.append(len(set(truth) & set(got)) / k)
    return float(np.mean(recalls)), len(sub_ids) / len(embeddings)

for p in [0.5, 0.2, 0.05, 0.01, 0.004, 0.001]:
    mask = np.random.rand(len(embeddings)) < p
    r, actual_p = filtered_recall_at_k(search, embeddings, mask, queries)
    print(f"selectivity={actual_p:.4f}  recall@10={r:.3f}")

Run it twice: once with a random mask (models the shattering regime) and once with a mask derived from a real metadata field like tenant_id or lang (models the unreachability regime). The two curves look different, and the second one is the one your users experience.

Two things to watch for. First, len(got) < k — count truncation separately from misranking, because under-returning points at post-filtering while low overlap points at graph fragmentation. Second, log selectivity per production query so you know your actual distribution; the aggregate is usually dominated by a few large tenants while the complaints come from the long tail.

The direct answer

Filtered vector search collapses at low selectivity because HNSW retrieves by walking a proximity graph, and a metadata filter deletes nodes from that graph without repairing its edges. With the default M=16 (32 links at layer 0), retaining a fraction p of nodes leaves mean degree ≈ 32p, so around p ≈ 3% the matching subgraph drops below the percolation threshold and fragments — greedy search then returns the best vectors inside whichever fragment it landed in, which are not the true nearest matching neighbors. Post-filtering makes it visible by returning fewer than k rows; pre-filtering hides it by returning k wrong rows. Fix it by partitioning on the filter key when you can, brute-forcing small filtered sets, enabling iterative index scans (hnsw.iterative_scan in pgvector 0.8+) or filter-aware graphs (Qdrant payload links, Weaviate ACORN) when you can't — and validate with filtered recall@k bucketed by selectivity, because a global recall number will never show you the failure.