Adaptive planning wins. Estimate filter cardinality per query and pick pre-filter, post-filter, or filter-aware traversal based on the estimate.
Picture searching a library for books on a niche topic in a specific language. If only ten books match the language, you grab those ten and read them. If half the library matches, you cannot pull half the books off the shelves first; you search normally and discard non-matching ones at the end. If a thousand books match, neither extreme works well, so you walk the aisles taking only ones that fit. A smart librarian decides the strategy after asking how rare the language is. A dumb librarian uses the same routine every time and fails badly on the queries at the opposite end of the spectrum.
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 is one of the trickiest parts of vector search, and it is also one of the most common in real workloads: almost every production query has at least one metadata predicate (tenant_id, language, date range, document type). The reason it is tricky is that the optimal algorithm depends on a quantity the system does not know until query time, namely the cardinality of the filter for this specific query.
This explainer walks through the three regimes, why fixed strategies fail at the regime boundaries, and what a production planner looks like. The MCQ answer (adaptive planner) is the only choice that survives both extremes; understanding why is more interesting than memorizing it.
Three regimes, three algorithms
Filter selectivity (the fraction of the corpus that matches the predicate) cleanly divides filtered ANN into three regimes, each with a different winning algorithm.
Tight filter (well under 1 percent). Pre-filter dominates. The optimizer enumerates the matching IDs using a payload index (a B-tree, a bitmap, an inverted index over the attribute), and then runs exact search on the small candidate set. At 0.5 percent of 100 million vectors, that is 500 thousand candidates, well within range of exact search on modern hardware. Recall is 1.0 by construction. ANN traversal at this selectivity would walk through huge non-matching regions and burn the latency budget.
Loose filter (above 10 to 20 percent). Post-filter dominates. The ANN graph search runs normally, and the filter is applied to the returned candidates. With 50 percent selectivity, asking for top 10 with 2x oversampling almost always returns 10 matches; with 20 percent selectivity, 5x oversampling does it. The graph structure is largely intact for the search, so the per-query cost remains roughly logarithmic in corpus size.
Middle band (roughly 1 to 10 percent). Neither extreme is right. Pre-filter pulls too many candidates to run exact search comfortably. Post-filter needs heavy oversampling, and the graph walk wastes time on non-matching regions. The right answer is filter-aware traversal: a modified ANN walk that incorporates the predicate during search, either by biasing neighbor selection toward matching nodes (ACORN style) or by maintaining filtered subgraphs.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- Qdrant ships a filterable HNSW with a planner that switches between pre-filter, post-filter, and filter-aware traversal based on payload index estimates
- Weaviate exposes filter strategies (acorn, sweeping) and lets the engine pick per query based on selectivity
What an interviewer would ask next. Try answering before peeking at the approach.
QHow does the planner estimate filter cardinality without scanning?
Payload indexes (B-tree, bitmap, histograms) over the filtered attributes give cheap estimates. For composite predicates the planner combines per-attribute estimates with independence assumptions or correlated statistics.
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.
Hard-coding a single strategy (always pre-filter, fixed 3x oversampling) and discovering it tanks at the other end of the selectivity range.
60 second bullets to scan on the way to the call.
The three filtered ANN regimes and what selectivity defines each
Why pre-filter wins at tight filters and dies at loose ones
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.