Hybrid search and filtered ANN

How should two retrievers' results be fused, and why does filtering break ANN in the middle?

Hybrid search and rank fusion

Lexical (word-based) and vector retrieval fail in complementary ways:

BM25 cannot match a paraphrase ("sofa" versus "couch").
Embeddings cannot reliably match an exact identifier, a product code or a rare proper noun, because those carry little semantic signal and the embedding averages them away.

Running both and combining is therefore not a hedge. It is a coverage decision.

Scores are not comparable

The mechanism problem is that the two scores are not on a common scale, and cannot be put on one.

BM25 is unbounded, corpus-dependent and query-dependent. A score of 14 means nothing without knowing the term statistics.
Cosine similarity is bounded, but its useful range is compressed and model-dependent.

Normalizing either requires knowing its score distribution for this query, which you do not have. Min-max normalizing (rescaling to 0..1 using the smallest and largest score seen) over the returned candidates is the common hack. It is unstable precisely because it depends on which documents happened to be returned.

Reciprocal rank fusion

Reciprocal rank fusion (RRF) sidesteps this by discarding magnitudes entirely. Each document scores

DefinitionReciprocal rank fusion →

Σ 1/ (k + rank_{i})

$rank_{i}$: the document's rank in result list i
$k$: a constant that softens the top ranks

Principle: Independence is assumed →

summed across retrievers (rank_i is the document's position in retriever i's list; k is a constant, conventionally about 60).

Only ordinal information survives, because only ordinal information was commensurable in the first place.

Claim type. RRF is empirically robust and theoretically thin. The constant is conventional, not derived. It works because rank is the one thing two independently calibrated systems agree on how to interpret, and its reciprocal shape encodes the reasonable prior that rank 1 versus 2 matters more than rank 50 versus 51.

The costs

Confidence is thrown away. A document that one retriever ranks first by an enormous margin is treated identically to one that barely edged into first. When calibrated scores genuinely exist (typically from a trained reranker rather than two raw retrievers), score fusion beats rank fusion. Rank fusion is the safe default under unknown calibration, not the better method.
Cost doubles. Hybrid runs both retrievers in full. You get the union of their recall and the union of their latencies and failure modes, plus a fusion stage. It roughly doubles retrieval cost, which is usually worth it but should be stated rather than assumed.

One line: two retrievers' scores are incomparable in magnitude and comparable in rank, so fusion on ranks is the safe default and fusion on scores requires calibration you probably do not have.

Filtered ANN: where the family actually breaks

"Nearest neighbours, but only among documents matching this predicate" is the most common real query and the one the index is worst at. (This is Amara's second problem.)

Post-filter

Post-filter: retrieve the top-k by vector, then drop non-matching items. If the predicate has selectivity s (the fraction of items that match), you keep about k·s. To end with k you must fetch k/s.

At s = 0.5, fetch 2k: trivial.
At s = 0.001 (0.1%), fetch 1,000k: for k = 10, that is 10,000 candidates, and the index will not return that many at reasonable cost.

Post-filtering degrades as the filter becomes selective.

Pre-filter

Pre-filter: evaluate the predicate first, then brute-force over the survivors. Cost is |survivors| × d. Excellent when the filter leaves a thousand rows. Catastrophic when it leaves ten million. And it must abandon the ANN index entirely, because the index was built over everything. Pre-filtering degrades as the filter becomes unselective.

The middle is hard, and the middle is common

Each strategy is fine at one end, and both are bad in the middle: roughly the 0.1% to 10% selectivity band, which is exactly where most real filters live. The hard case is the common case. This is the single most useful thing to know about deploying vector search. (Pune + in stock + under 500 rupees might select about 0.5% of 10 million listings: 50,000 items. Post-filtering the top 10 neighbours leaves about 10 × 0.005 = 0.05 items on average: that is why a handful survive, or none.)

Why the middle resists

The ANN structure was fitted to the full corpus. A filter defines a sub-distribution the structure was never built for:

In a graph, the matching nodes may not be connected to each other, so greedy traversal either walks through non-matching nodes at inflated cost or gets trapped in a region containing none.
In IVF, matching vectors are thinly spread across all cells, so nprobe must rise toward k and pruning evaporates.

Escapes, with prices

Escape	Price
Traverse the full graph while collecting only matches	pays in hops; recall still collapses when matches are sparse
Build a separate index per filter value (ordinary partitioning)	works only for low-cardinality, known-in-advance fields; two filter fields mean a combinatorial product of indexes
Interleave the predicate into traversal so the search is guided toward matching regions	the current direction of the field, and genuinely unsettled
Accept degraded recall and say so	lower quality

A law that generalizes far beyond vectors

Examples: IVF centroids under a filter; HNSW connectivity under a filter; cost-model histograms under correlated predicates (the classic cardinality-estimation failure in query optimizers is exactly this); learned indexes under drift; cache eviction heuristics under a workload change; autoscaling predictors under a traffic-shape change. It is related to the independence assumption but distinct: that one is about assuming independence; this is about assuming stationarity (the data does not change its shape) and representativeness. The tell is always the same: the structure does not fail loudly, it silently returns worse answers.

One line: post-filter dies on selective predicates, pre-filter dies on unselective ones, and the middle is hard because a filter defines a sub-distribution the index was never fitted to.

One distributed note

Sharding behaves differently here than in text. In a sharded inverted index, a shard whose dictionary lacks the query term contributes nothing and can be skipped: absence prunes. In a sharded vector index, every shard contains plausible candidates, so every query fans out to every shard, always.

Full fan-out means the query's latency is the maximum over shards, and tail-at-scale arithmetic applies at full strength. Example: if each shard is slow (above its own p99) 1% of the time, a query that waits for 100 shards is hit by at least one slow shard with probability 1 − 0.99¹⁰⁰ ≈ 63%. So the p99 of the fan-out is materially worse than the p99 of any shard, and it worsens as you add shards. Scaling a vector index out degrades tail latency in a way scaling a text index out does not.

The standard mitigations are hedged requests (sending a duplicate request to another replica if the first is slow) and tolerating partial results from slow shards. The second is acceptable only because, once again, the answer was approximate anyway. (Fan-out sharding is the same scatter-gather mechanism as in text, behaving differently because absence no longer prunes.)