Vector Search Is Approximate. Add a Filter and It Gets Worse

You ask for the 10 nearest vectors matching WHERE tenant_id = 42. Your database returns four. No error, no warning, and the four are genuinely close. The other six exist, and the index never looked at them. This is not a bug, because vector search is approximate by design.

The behaviour is documented. Yet almost nobody reads the parameter that controls it until results start going missing.

Key takeaways#

• ANN means approximate. An HNSW index trades exactness for speed by design.
• Recall is a tuning parameter, not a property of your database.
• pgvector defaults: m = 16, ef_construction = 64, hnsw.ef_search = 40.
• A filter matching 10% of rows leaves roughly 4 of those 40 candidates. You asked for 10.
• Measure recall against a brute-force baseline. Otherwise you are guessing.

Why is vector search approximate at all?#

Because exact nearest-neighbour search over millions of high-dimensional vectors means comparing the query to every single one. That is linear, and it does not scale.

HNSW, from Malkov and Yashunin's 2016 paper, gets around this with a layered graph. The index builds a hierarchy of proximity graphs. Upper layers are sparse and let the search cover distance quickly. Lower layers are dense and refine the result. Elements get assigned a maximum layer randomly, with an exponentially decaying probability, so few nodes reach the top.

A vector search query enters at the top layer, greedily walks toward the query vector, then drops a level and repeats. The paper's claim is logarithmic complexity scaling, and that is the entire reason the technique won.

The cost is that a greedy walk can miss. If the true nearest neighbour sits behind a poorly connected region of the graph, the search never reaches it. So you get approximate neighbours. Usually very good ones, and not guaranteed ones.

The three parameters that decide recall#

Every HNSW implementation exposes roughly the same three knobs. The pgvector names and defaults are below, though the concepts carry across engines.

m sets graph connectivity. More links mean more paths to any given node, so the greedy walk gets stuck less often. However, the index grows, because every node stores its links.

ef_construction decides how hard the builder works to find good neighbours for each new node. pgvector's documentation is direct about the trade: a higher value "provides better recall at the cost of index build time / insert speed".

hnsw.ef_search is the one that matters most day to day, and the one people never touch. It sets how many candidates the search keeps in flight. Raising it "provides better recall at the cost of speed".

Note the asymmetry. Two of these are baked in at build time, so changing them means rebuilding the index. Only ef_search is adjustable per query, which makes it your main lever in production.

The filter trap, with real numbers#

Here is where the defaults bite hardest, and pgvector's own documentation spells it out.

Suppose your table holds vectors for many tenants, and you query one tenant that owns 10% of the rows. You ask for 10 results.

The index does not know about your WHERE clause. It walks the graph, collects a candidate list of ef_search = 40, and hands those up. Then the filter applies. Roughly 10% of 40 survive.

You asked for 10 and get about 4.

The documentation states this plainly: "If a condition matches 10% of rows, with HNSW and the default hnsw.ef_search of 40, only 4 rows will match on average."

Now scale the selectivity down and the effect gets brutal:

At 1% selectivity you usually get nothing. A per-tenant vector search on a large multi-tenant table is exactly that shape, so this is not a corner case. It is the common case for anyone building a SaaS product on vector search.

The worst part is the silence. There is no error. Your application receives a short list, assumes those were the only matches, and shows the user an empty or thin result.

Fixing the filter problem#

Three approaches, and the right one depends on your selectivity.

Raise ef_search. Simplest, and often enough. If your filter matches 10%, you need roughly ten times the candidates to end up with the same number of results. Set it per query rather than globally, because a query with no filter does not need the extra work.

Use iterative index scans. pgvector supports scanning further when the first pass returns too few rows. The planner keeps pulling candidates until it has enough. This costs latency on selective queries and avoids the guesswork of picking a multiplier.

Partition instead of filtering. If tenancy is your filter, a separate index per tenant removes the problem entirely. Every candidate is already valid, so ef_search behaves as documented. The cost is operational complexity and many small indexes.

There is a fourth option people reach for that usually disappoints. Fetching a large k and filtering in the application is the same post-filter, just moved. You still pay for the candidates and still lose the ones the graph never visited.

The mismatch that turns recall to zero#

One more failure deserves naming, because it looks like a recall problem and is not.

An HNSW index is built for one distance function. pgvector exposes several operators, and each has its own operator class:

The README puts it plainly: add an index for each distance function you want to use. So an index built with vector_l2_ops does nothing for a query written with <=>.

The symptom is not an error. Postgres simply falls back to a sequential scan, which is exact and therefore returns perfect results. Your recall looks flawless while latency quietly collapses, and on a small table nobody notices until the data grows.

Check it with EXPLAIN. If you see a sequential scan where you expected an index scan, the operator and the operator class disagree.

How to actually measure recall#

Recall is measurable, and most teams never measure it. So they tune blind.

The method is straightforward. Take a sample of real query vectors, say 200. For each one, run an exact search with the index disabled, which gives you ground truth. Then run the same query through the index. Recall@k is the fraction of the true top-k that the index returned.

-- ground truth: force a sequential scan
SET enable_indexscan = off;
SELECT id FROM items ORDER BY embedding <=> :q LIMIT 10;
 
-- indexed result
SET enable_indexscan = on;
SET hnsw.ef_search = 40;
SELECT id FROM items ORDER BY embedding <=> :q LIMIT 10;

Compare the two id sets and average across your sample. Then repeat at several ef_search values.

What you are looking for is the knee of the curve. Recall climbs steeply at first, then flattens, and past that point you are buying latency for almost nothing. Where the knee sits depends on your data, which is why a number copied from a blog post is not useful to you.

Run this against production-shaped queries, including the filtered ones. An unfiltered benchmark will look excellent and tell you nothing about the case that is failing.

When higher recall is the wrong goal#

Chasing recall has real costs, so it is worth naming the cases where you should stop.

Latency budgets. Raising ef_search increases work per query roughly in proportion. If you sit at p99 already, the extra recall may cost you more than it returns.

Memory pressure. Raising m grows the index, and HNSW performs well because the graph lives in memory. Pushing it past available RAM turns a fast index into a slow one, and the cliff is sharp.

Recommendation and discovery. If vector search powers a "related items" panel, the difference between the true 10th neighbour and the 14th is invisible to the user. Perfect recall is wasted there.

When rerankers follow. If a cross-encoder reranks your candidates anyway, retrieval only needs to get the right documents into the pool. Order within the pool matters less, and a broad, cheap retrieval feeding a reranker often beats an expensive, precise one. This is the same layering argument as in hybrid search, where fusion decides which documents deserve the expensive model.

What IVFFlat gets right#

HNSW is the default recommendation, so it is worth saying where the alternative wins.

IVFFlat divides vectors into lists and probes only some of them at query time. pgvector describes it as having faster build times and lower memory use than HNSW, with a worse speed-recall tradeoff. Its knobs are lists at build time and ivfflat.probes at query time, and the default probe count is 1.

On list sizing the documentation is specific: start at rows / 1000 for up to a million rows, and sqrt(rows) beyond that.

Two properties make it the better choice sometimes. Build speed matters if you reindex often, and an HNSW build over millions of vectors is slow. Memory matters if your index would not otherwise fit in RAM, since a graph that spills to disk loses the property that made it fast.

One asymmetry catches people out. An HNSW index can be created on an empty table, whereas IVFFlat needs data present because it trains its lists from the existing vectors. Build an IVFFlat index before loading, and the clustering is meaningless.

The filter problem does not disappear either. Probes select lists, the filter applies afterwards, and low selectivity thins the results the same way. ivfflat.probes is the equivalent dial.

Choosing your settings#

That fifth row deserves a note. If a missed document has consequences, approximate search is a decision you are making about correctness, not just performance. Either measure and state the recall, or use exact search on a smaller filtered set.

Detecting the problem you already have#

Two signals point at recall issues, and both are easy to check.

Result counts below the limit. Log how often a query returns fewer rows than the LIMIT requested. If a meaningful fraction comes back short, your candidate list is being eaten by a filter. Aggregate this by filter selectivity and the pattern is usually obvious immediately.

Queries that used to work. Recall degrades as a table grows, because the graph gets deeper while ef_search stays fixed. A system that was fine at 100,000 rows can quietly deteriorate at 10 million. So re-measure after significant growth rather than assuming the settings still hold.

Index build settings deserve a periodic look too. An index built with ef_construction = 64 on a small table may be under-built for the table it has become, and no query-time parameter fully compensates for a poorly constructed graph.

The short version#

Vector search returns approximate neighbours, and how approximate depends on three parameters most teams leave at their defaults. Adding a WHERE clause makes it substantially worse, because the filter applies after the index has already chosen its candidates. With pgvector's default of 40 and a filter matching 10% of rows, you get about four results when you asked for ten, silently. Measure recall against a brute-force baseline on production-shaped queries, tune ef_search to the knee of the curve, and partition rather than filter when selectivity is low.

Sources: Malkov & Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs", arXiv:1603.09320, pgvector documentation