Why can a metadata filter make an HNSW vector search return almost nothing?

## The scenario A legal e-discovery platform holds one matter's four-million-document corpus in a vector index. A paralegal searches for a concept, filtered to two custodians and a six-week date range — perhaps 3,000 chunks out of tens of millions. The search returns three results, or none. The corpus is fine; the filter is fighting the index. ## Post-filtering: the empty result The simplest implementation asks the index for the nearest k vectors and then drops those that fail the predicate. It is correct in the sense that everything returned matches, but the recall is dreadful. If the predicate selects one in a thousand chunks and you asked for 100 neighbours, the expected number of survivors is about 0.1. Widening to 10,000 candidates makes the survivor count acceptable at the price of a hundredfold increase in work, and it still gives no guarantee — the true nearest matching chunks may sit far down the unfiltered ranking. The characteristic symptom is a result page that is empty or nearly empty for selective filters and perfectly good for broad ones. ## Pre-filtering: the connectivity problem The obvious alternative is to only traverse nodes that satisfy the predicate. HNSW navigates by greedy descent through a small-world graph whose usefulness depends on its links: from any node there is a short path to any region. Mask out 99.9% of the nodes and the induced subgraph is not a small world any more — it is a scattering of isolated fragments. The walk reaches a local dead end, and the search either terminates early with poor results or has to keep expanding its candidate list, which is a slow, memory-churning way to approach a full scan. This is the real content of the interview answer: filtering does not just cost extra work, it violates the structural assumption the index is built on. ## What engines actually do about it Four families of mitigation, all worth naming: **Filter-aware traversal.** The engine maintains indexes over the filterable payload fields and evaluates the predicate during the walk, and may add extra graph links so that nodes sharing common payload values stay reachable from one another. This keeps the subgraph navigable for the filters you declared as filterable — which is a schema decision, made in advance, not a free property of arbitrary predicates. **Iterative or multi-pass scanning.** Rather than fixing one candidate width, the engine repeatedly resumes the search with a wider frontier until it has collected enough post-filter survivors or hits a work limit. This converts the empty-result failure into a latency cost, which is usually the trade you want. Postgres with pgvector gained iterative index scans for exactly this reason. **Brute-force fallback on high selectivity.** Below some threshold of matching rows, scanning the matching set exactly is both faster and perfectly accurate — a few thousand distance computations is nothing. Engines expose this as a full-scan threshold. This is the honest answer for very narrow filters, and it beats any graph heroics. **Partitioning.** If the predicate is stable and coarse — per tenant, per matter, per year — build separate indexes and route. The filter stops being a filter and becomes index selection, so each search runs over a fully connected graph with no masking. In matter-scoped e-discovery this is the natural design: no query ever legitimately crosses matters, so nothing is lost. ## Choosing by selectivity The decision is a function of how many rows the predicate keeps: - **Broad filter (say above 20% of the corpus):** post-filtering with a modestly widened candidate list is fine. - **Middle band:** filter-aware traversal or iterative scans, tuned against measured recall. - **Very selective (a fraction of a percent):** brute-force the matching set, or partition so it is not a filter at all. Engines can estimate selectivity from statistics and switch strategy per query, but the estimates can be wrong, and a wrong estimate on a correlated predicate is how you get a query that is a hundred times slower than its neighbours. ## Measuring it Unfiltered recall numbers tell you nothing about filtered behaviour. Build the recall harness with filters in it: for a sample of realistic predicate shapes, compute exact top-k over the matching subset by brute force and compare against what the index returns. Track filtered recall and filtered p95 latency as separate metrics, bucketed by selectivity. Also monitor the empty-result rate in production — it is the cheapest available signal that filtering is silently failing, and a user-visible empty page is often the first and only complaint you get. ## The common mistakes Assuming a filter is a cheap SQL-style predicate that the index will handle; tuning recall only on unfiltered queries; treating an empty result as "no matching documents" rather than as an index-behaviour bug; and adding an ever-wider candidate list as a blanket fix, which quietly turns interactive search into a scan under load.