How filtered vector search loses recall for tenants

Filtered vector search does not fail on the average query. It fails where one tenant stores millions of documents, another has only a few hundred, and the product promises both an equally reliable answer. The team sees good recall on the combined dataset, acceptable p95 latency, and considers the problem solved. Then a small customer cannot find its own contract, even though the contract is in the database and its embedding is almost identical to the query.

The cause is usually not the embedding model. ANN search builds a limited candidate set in a shared space, while a filter by tenant, permissions, region, or status sharply reduces the eligible set. If the required segment is rare, the candidate budget is spent on neighbors from other segments. After filtering, the result set becomes short or irrelevant. This must be checked with a load test as a separate system property. Do not assume that good global recall covers every case.

Recall must be calculated inside the eligible set

For a query with tenant_id, the ground truth is not the global k nearest vectors followed by filtering. It is the k nearest vectors among documents that pass the same tenant_id and all other mandatory conditions. Otherwise, you are measuring a different task.

Let query q belong to tenant t, and let F(t, q) be the documents allowed by the filter. The exact ground truth is:

truth(q) = top_k by distance(q, d), where d belongs to F(t, q)

The approximate query returns ann(q). For a specific query, calculate recall@k from the intersection of identifiers, not from text similarity or a human score:

recall@k(q) = |truth(q) ∩ ann(q)| / k

If the eligible set contains fewer than k documents, the denominator must be the size of the ground-truth result. This looks like a small detail on paper. In a real multi-tenant system, small and new tenants often have fewer documents than the requested k, and the wrong formula makes an empty result look normal.

You must also distinguish two failures. In the first, the system returns k documents but misses close eligible documents. This is a ranking loss. In the second, the system returns fewer than k documents even though the permitted segment contains enough of them. This is a loss of result-set completeness. Users notice the second one sooner because the interface suddenly shows two results instead of ten. Both matter to engineers, but they are not always fixed in the same way.

The pgvector documentation states this directly: with an approximate index, filtering is applied after the index scan, so a limited hnsw.ef_search may fail to produce the required number of rows. As an example, the documentation gives a filter with 10% selectivity: with the default ef_search = 40, about four matching rows will remain on average. This is not a PostgreSQL bug or an exceptional case. It is the expected mathematics of a limited candidate pool.

The average tenant hides the long tail

Document distribution across tenants is almost never even. One bank uploads years of support history, a SaaS customer adds tens of thousands of records, and a small department contributes a couple hundred policies. If you take a thousand queries in proportion to traffic, large segments will consume the experiment. The overall recall number will look good even when rare tenants consistently lose.

Break results down along at least two independent dimensions:

• the size of the eligible segment after filtering;
• filter selectivity relative to the entire index.

These are not the same thing. A tenant with 10,000 documents may be very small in an index containing one billion vectors. Conversely, a role filter may leave 500 documents, but those documents may be spread across all tenants. Both factors matter to an ANN index: how many acceptable objects exist and how rarely they appear while the structure is being traversed.

A practical bucket grid looks like this: fewer than 100 eligible vectors, 100-1,000, 1,000-10,000, 10,000-100,000, and more than 100,000. For selectivity, create separate buckets: below 0.01%, 0.01-0.1%, 0.1-1%, 1-10%, and above 10%. The boundaries are not sacred. Their purpose is to keep rare operating modes visible on the chart.

Do not confuse tenant size with the size of its corpus before filtering. A tenant may have 50,000 documents, while document_type = policy, language = kk, and active = true leave only 60 for a particular query. Those 60 determine the difficulty of that search. In the test table, store both the original tenant size and the number of rows that pass the complete filter for each query.

There is another unpleasant detail. Small tenants often have less carefully phrased queries, fewer repeat searches, and more varied documents. You cannot blame their poor recall on filtering without manually checking the exact nearest texts. But the opposite mistake is also common: the team improves the prompt or changes the embedding model when ANN search simply never reached the right candidates.

A load test must reproduce inequality, not the average

Distributing the same number of vectors across tenants at random removes the problem from the test. You need a long-tailed corpus: a few very large tenants, a visible group of medium-sized tenants, and many small ones. Synthetic generation is acceptable for volume and imbalance, but the queries and vectors should resemble your production material. Random independent vectors rarely form difficult neighborhoods, so they are poor at revealing quality losses.

Build three query sets. The first contains queries with obvious close documents in the required segment. It measures technical recall. The second contains boundary cases with similar documents belonging to different tenants. It catches errors where the filter was applied in the wrong place or omitted. The third repeats the real mix of conditions: document type, status, language, date, access rights, and tenant_id.

For every query, preserve an immutable record:

{
  "query_id": "q-1842",
  "tenant_id": "tenant-small-17",
  "k": 10,
  "filter": {
    "tenant_id": "tenant-small-17",
    "document_type": "policy",
    "active": true
  },
  "eligible_count": 74,
  "tenant_count": 623,
  "global_count": 18000000
}

The eligible_count field must not be calculated from the ANN result. Obtain it from a separate exact run or a precomputed ground truth. If you record the number of documents actually returned, the test will start validating its own error.

The workload must also be uneven. Large tenants generate most of the traffic, but the test must deliberately provide enough observations for every rare bucket. Otherwise, the confidence interval for small segments will be too wide and a regression will go unnoticed. Keep two summaries in the report: one weighted by real traffic and one unweighted, where every segment class has the same weight. The first describes overall load. The second shows whom the system is quietly underserving.

Do not measure only isolated queries. Concurrent load changes index and data residency in memory, CPU queues, cache behavior, and the latency tail. Run at least several concurrency levels, including one at which the service is close to its production load. Then repeat the exact ground truth offline, not on the same overheated serving path. The purpose of the ground truth is correctness, not speed.

Post-filtering often returns a polished but incomplete result

The most common architectural mistake is simple: run ANN search over all vectors with k = 10, then filter the ten retrieved objects by tenant_id. With a selective filter, this approach cannot guarantee ten results. If eight candidates belong to other tenants, you will show two even when the permitted segment contains thousands of matching documents.

Engineers sometimes try to fix this by increasing the outer k, for example retrieving 200 candidates and keeping ten after filtering. This may be an acceptable temporary solution at moderate selectivity, but it must not be treated as a quality property. For a segment representing 0.01% of the index, even 200 candidates will often produce no documents. As k grows, you also move the cost into the network, memory, reranker, and application code.

OpenSearch clearly distinguishes filtering inside a k-NN query from filtering after the search. Its documentation warns that post-filtering under a restrictive condition can return substantially fewer than k results, while efficient k-NN filtering applies the filter during vector search and aims to return k results when the index contains at least k eligible documents.

But the phrase «filter inside the search» does not mean perfect recall automatically. An implementation may choose between traversing the ANN structure and processing the filtered subset exactly, limit the traversal budget, or change strategy based on estimated selectivity. Therefore, record the semantics of the specific engine and the exact query syntax in your report. Placing the same filter inside or outside the vector condition can change not only latency but also the result set.

Check this with a simple invariant: if eligible_count >= k, the number of rows returned after all mandatory filters must be k. A violation does not always mean low recall, but it always requires an explanation. You may have deliberately set a search limit, the engine may have applied the filter after selecting too few candidates, or the query may contain an error.

A rare tenant needs a separate search strategy

One shared HNSW index is convenient to operate, but it does not have to be the best path for every segment. When the eligible set is large, HNSW usually provides the right trade-off between latency and completeness. When filtering leaves a few dozen or a few hundred vectors, calculating distances exactly over that set may be faster, cheaper, and more predictable than deeply traversing the global graph.

Choose a strategy based on the expected size of the post-filter set and the target latency, not on the document count in the entire table. A conditional policy might look like this:

• for a very small eligible_count, run exact search over the filtered segment;
• for a medium-sized segment, increase the candidate budget or use filtering during ANN traversal;
• for a large segment, use the shared ANN index with its normal configuration;
• for stable large tenants, evaluate partitioning or a separate index.

You cannot take the threshold between these modes from someone else's benchmark. It depends on embedding dimensionality, the distance metric, CPU count, memory, storage subsystem, filter composition, and request queue. Find it on a chart with eligible_count on the X axis and p95 and recall@k for several strategies on the Y axis. The switching point should be where the exact path no longer fits your latency budget or ANN begins to reliably deliver the required completeness.

Pagination does not solve this problem. If the first ANN search did not find the required objects, page two will not make them closer. Reranking likewise cannot return a document that was never in the candidate set. A reranker improves candidate order, while filtered ANN determines whether candidates reach it at all.

Tenant-level separation is not free either. Millions of individual indexes create metadata, background operations, memory imbalance, and difficult update workflows. It is usually more sensible to separate only large or legally isolated tenants and serve the long tail from a shared index with an explicit mode for rare segments. The useful tool is not the slogan «one index» or «one index per tenant», but a decision table with measured boundaries.

Tune the index for the worst bucket

Tuning HNSW against global recall almost guarantees a search budget that is too small for rare filters. In pgvector, hnsw.ef_search limits the size of the dynamic candidate list. The documentation recommends increasing it when filtering, and starting with version 0.8.0 it offers iterative index scans: the engine continues scanning until it collects enough rows or reaches a configured limit on tuples scanned or memory.

Iterative scanning is useful, but it does not remove the budget. If hnsw.max_scan_tuples is too small, a rare tenant will remain without results. If the limit is too high and unprotected, one narrow filter can consume CPU and worsen p99 for everyone else. Test a parameter set, not just one ef_search: initial budget, maximum expansion, memory limit, and permitted latency tail.

For IVFFlat, the same logic applies to the number of lists scanned. A low probes value gives a fast but incomplete search. A high value improves completeness but moves the query toward an expensive scan. IVFFlat has another trap: the number of lists affects how evenly data is distributed across clusters. An index built on a small dataset with an aggressive list count may have poor completeness on its own, even before filtering.

Test configurations as a matrix rather than tuning them manually on one query. For each parameter pair, record:

The last column may contain the number of vectors examined, nodes visited, ef_search, probe count, or another metric provided by your engine. Without it, it is difficult to distinguish a successful configuration from one that bought quality at an unacceptable cost.

Do not accept a configuration that passes the average metric but fails the previously agreed minimum for the rare bucket. The business may genuinely allow a different SLO for a free tier or archive search. If so, record it as a product rule and show the user understandable behavior. Silently returning two results instead of ten for a small tenant is not a policy. It is a defect.

The exact ground truth must live beside the approximate test

Exact search does not have to serve production traffic, but it must exist in the test system. Without it, you cannot know what you lost. Comparing one ANN configuration with another only shows which one more often agrees with its neighboring configuration.

In PostgreSQL with pgvector, you can put the ground-truth and test queries in the same transaction. Disable ANN index usage only for the ground-truth run, not for the entire load-test environment.

BEGIN;

SET LOCAL enable_indexscan = off;
SET LOCAL enable_bitmapscan = off;

SELECT id
FROM chunks
WHERE tenant_id = :tenant_id
  AND document_type = :document_type
  AND active = true
ORDER BY embedding <=> :query_embedding
LIMIT 10;

COMMIT;

Then run the production variant with the index separately and save the two ordered lists of identifiers. pgvector explicitly recommends monitoring recall by comparing approximate search with exact search and shows disabling index scans for this purpose.

For an HNSW experiment, the working query can look like this:

BEGIN;

SET LOCAL hnsw.ef_search = 80;
SET LOCAL hnsw.iterative_scan = strict_order;
SET LOCAL hnsw.max_scan_tuples = 20000;

SELECT id
FROM chunks
WHERE tenant_id = :tenant_id
  AND document_type = :document_type
  AND active = true
ORDER BY embedding <=> :query_embedding
LIMIT 10;

COMMIT;

Do not copy these numbers into production as a recipe. They illustrate the shape of the experiment. For every result row, save query_id, search parameters, the exact ID list, the ANN ID list, duration, number of returned rows, and the segment buckets. You can then calculate recall@10, first-place hit rate, incomplete-result share, and latency without rerunning the entire test.

Verify that the exact query is truly exact. The planner may choose an unexpected path, and the filter may be applied differently from what you assume. Inspect EXPLAIN (ANALYZE, BUFFERS) for several queries from every bucket. Pay particular attention to filters hidden in a join, subquery, or access-control function. Query semantics matter more than an attractive index name.

Data-model errors can look like an ANN problem

Multi-tenant search often joins the vector table with the main document table, a permissions table, and an organization table. If tenant_id exists only in the main table, the filter may be applied after the vector scan and join. That is not always wrong, but you must see it in the plan and measure the consequences. When isolation rules are critical, keeping the immutable search filters needed for retrieval next to the vector is usually simpler and more reliable to analyze.

Do not duplicate everything. Duplicate fields that satisfy all three conditions: they participate in every search restriction, they change in a controlled way, and they can be validated on write. For tenant_id, this is often reasonable. For a complex permission set with thousands of groups, duplication can become a source of drift. In that case, build an explicit set of permitted identifiers and separately verify how the engine executes that variant.

Soft delete is another trap. A document may already be hidden from the product while its vector remains in the index until background cleanup. The search spends candidates on dead rows, and a narrow filter discards them at the end. In the report, separate cases where ANN failed to find live documents from cases where it found deleted or inaccessible documents. Otherwise, the team may raise ef_search when it should first fix the data lifecycle.

Check write invariants: every vector must receive tenant_id, a permission version, and document status before it becomes searchable. Asynchronous indexing may create a short inconsistency, but it must be measurable and bounded. A document that has not yet been indexed is not a recall loss. It is a separate index-freshness metric.

The SLO must prevent silent failure in small segments

For filtered search, a single target such as «recall@10 must be at least 0.95» is not enough. It says nothing about which queries achieved the result or at what latency cost. Set requirements by bucket and define a separate limit for incomplete results.

One formulation to discuss with the team might be: for queries with at least ten eligible documents, the service returns ten documents; recall@10 in every supported selectivity bucket stays above the agreed threshold; and p99 remains within the limit at production concurrency. If very small segments use the exact path, mark that in the metrics rather than mixing them with ANN results.

Monitor changes in tenant distribution. A configuration that worked with several large customers may fail after a large archive migration or the arrival of many new small teams. Recalculate the segment profile after major uploads, embedding-model changes, index rebuilds, and access-filter changes.

AI Router can be the place where the team records the model, query parameters, and LLM route for a reproducible RAG test, but filtered vector-search completeness still has to be measured in your storage system and under your access rules. Model routing cannot recover candidates that the search layer never returned.

The most useful first run does not require a complex test environment. Take several dozen real queries from large, medium-sized, and small tenants. Build the exact top-k for each inside the complete filter. Then compare it with the current ANN path and break down errors by eligible_count and selectivity. If the chart drops sharply in rare segments, do not argue about average recall. Change the search path, data structure, or index budget where users are already receiving poor answers.