Post-filter starvation: the engine took its usual 100 candidates then filtered, leaving 4 survivors. Fix it by pre-filtering, filter-aware traversal, or aggressive oversampling.
Picture a bookstore with 5 million books. You ask the clerk for the 20 most relevant books on Roman history. The clerk grabs the 100 books that look closest by the cover, then checks which ones are actually history, and only 4 happen to qualify. There are 50,000 history books on other shelves, but the clerk never walked there. Two cures exist. Either walk the history shelves first and only score those books (pre-filter), or build a smarter clerk who follows the history label as part of the walk (filter-aware graph traversal), or just grab 5,000 books upfront so 1,000 survive (oversample). The naive engine grabs a fixed handful and applies the label too late. The same shape repeats in every ANN system, which is why filter cardinality estimation is now table stakes in Qdrant, Weaviate, and pgvector planners.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Filtered ANN search is the single most common production bug shape in vector databases. The query asks for k results that satisfy a metadata predicate, and the system returns far fewer than k even though the corpus contains thousands of matches. The reflex is to blame the index, raise M, or rebuild. Almost always the bug is not graph quality but strategy selection: how the filter interacts with the graph walk.
This walkthrough lays out the failure mechanism, the three strategies that fix it, the cardinality math that selects between them, the engine-specific implementations in 2026, and the operational logging that makes the bug visible before users feel it.
Mental model: an HNSW walk is filter-blind by default. The candidate list is built by distance, and the filter runs after. If matches are sparse in the regions the walker visits, post-filter starves no matter how good the graph is.
What post-filter starvation actually is
Most HNSW implementations expose ef_search, the size of the candidate priority queue maintained during the walk. A typical default is 64 or 128. The walker enters the graph, explores neighbors by distance, and ends with a candidate list of that size. The predicate runs afterward.
If the filter matches 50,000 of 5 million vectors, the average density of matches is 1 percent. A random selection of 100 candidates expects 1 match. The walker is not random, but it is also not filter-aware: it visits the regions closest to the query in raw embedding space, and those regions contain whatever distribution of matches happens to live there. Frequently that distribution is 4 out of 100, not 20 out of 100.
The symptom is precise: delivered k less than requested k, unfiltered queries healthy, recall measurements on the unfiltered index normal. That symptom isolates the bug to filter integration, not graph construction. If you see delivered-k less than requested-k on filtered queries while unfiltered queries return a full list, do not rebuild the index. Audit the filter strategy.
A secondary tell: the bug gets worse as the filter gets more selective. At 50 percent selectivity, post-filter usually fills k. At 5 percent, it sometimes starves. At 0.1 percent, it almost always does.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- Qdrant ships filterable HNSW where the walker honors payload predicates during neighbor expansion, the canonical implementation of filter-aware ANN.
- Weaviate 1.24+ adopted ACORN-style filtered search to handle low-selectivity filters that previously starved the candidate pool.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow would you size ef_search to guarantee k filtered results at 5 percent selectivity?
Model survival as binomial: expected survivors = ef_search times selectivity. For 95 percent confidence of k survivors at p=0.05, set ef_search to roughly k / p times a safety factor of 1.5-2. Then verify on production traffic with delivered-k logging.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Believing the index is broken because k=20 returned 4. The graph is fine; the filter ran on a too-small candidate set, starving the result list.
60 second bullets to scan on the way to the call.
How post-filter starvation actually presents in logs (delivered k less than requested k)
The three strategies and the rough cardinality cutoffs that select between them
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.