Hybrid search and rank fusion

Deep dive

How it works

In: a ranked list of (doc id, score) from each retriever, weights, k or α · Out: one ranked list of the top n doc ids · State: none · Cost: O(L + L log L) for L total hits, order of 25 ns per hit

1. Run BM25 and ANN search (HNSW) independently, in parallel, each returning its top W hits (the window).
2. Join the lists by document id. A hit missing from a list contributes 0 for it.
3. Score: RRF adds w/(k + rank); convex combination (CC) adds w · normalized score, with w_dense = α, w_lexical = 1 − α.
4. Sort, keep the top n, optionally pass to a cross-encoder.

BM25 list : A(1) B(2) C(3)        dense list: C(1) D(2) A(3)      k = 60
A = 1/61 + 1/63 = 0.03227   C = 1/63 + 1/61 = 0.03227   B = 1/62 = 0.01613   D = 1/62
fused: A, C (tie), then B, D

RRF discards score gaps: a hit at rank 2 in both lists (2/62 = 0.03226) scores a hair below ranks 1 and 3 (0.03227).

Code

use std::collections::HashMap;

/// Reciprocal rank fusion. Each input list is best-first doc ids, ranks are 1-based.
/// score(d) = sum over lists of w / (k + rank). Returns the top `n` as (doc, score).
pub fn rrf(lists: &[&[u32]], weights: &[f64], k: f64, n: usize) -> Vec<(u32, f64)> {
    let mut acc: HashMap<u32, f64> = HashMap::new();
    for (list, &w) in lists.iter().zip(weights) {
        for (i, &d) in list.iter().enumerate() {
            *acc.entry(d).or_insert(0.0) += w / (k + (i + 1) as f64);
        }
    }
    finish(acc, n)
}

/// Min-max normalize each list's scores to [0, 1], then take a convex combination.
/// A document missing from a list contributes 0 for that list.
pub fn convex_minmax(lists: &[&[(u32, f64)]], weights: &[f64], n: usize) -> Vec<(u32, f64)> {
    let mut acc: HashMap<u32, f64> = HashMap::new();
    for (list, &w) in lists.iter().zip(weights) {
        let lo = list.iter().map(|x| x.1).fold(f64::INFINITY, f64::min);
        let hi = list.iter().map(|x| x.1).fold(f64::NEG_INFINITY, f64::max);
        let span = hi - lo;
        for &(d, s) in list.iter() {
            // a constant list (span 0) carries no ranking information: give every hit 1.0
            let z = if span > 0.0 { (s - lo) / span } else { 1.0 };
            *acc.entry(d).or_insert(0.0) += w * z;
        }
    }
    finish(acc, n)
}

fn finish(acc: HashMap<u32, f64>, n: usize) -> Vec<(u32, f64)> {
    let mut v: Vec<(u32, f64)> = acc.into_iter().collect();
    // tie-break on doc id so results are deterministic
    v.sort_unstable_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
    v.truncate(n);
    v
}

Checked by tests: BM25 scores (18, 12, 4) with cosines (0.92, 0.90, 0.30) make a raw score sum follow BM25 magnitude, while min-max CC and RRF each pick by agreement.

Complexity and constants

• Time O(L + L log L) for L = Σ list lengths; space O(distinct docs), about 12-16 B per entry plus hash overhead.
• Measured here (code above, std SipHash HashMap, one Apple M-series core, random ids from 5,000): two lists of 100 hits take 5.4 µs, two of 1,000 take 50 µs. Order of 25 ns per hit.
• The cost drivers are upstream: one BM25 pass over posting lists plus one ANN search (order of 0.1-1 ms on millions of vectors, see HNSW), and a cross-encoder forward pass per reranked document (order of ms each).
• Network: per retriever W · (id + score) bytes, e.g. 100 hits × 12 B = 1.2 KB; fetch document bodies only after fusion.

Efficiency

• Cost: fusion is microseconds: measured here (code above, one Apple M-series core) 5.4 µs for two lists of 100 hits, 50 µs for two of 1,000, order of 25 ns per hit; about 12-16 B per entry. The retrievers dominate: one BM25 pass plus one ANN search (order of 0.1-1 ms on millions of vectors, see HNSW), then order of ms per document for a cross-encoder. Bound: retrieval latency and, when sharded, network round trips.
• Levers:
  • parallel retrievers — wall time is the max, not the sum, of the two legs (Elasticsearch fuses on the coordinating node) — always
  • small window W (start around 50-200) — bounds work in both legs and in any rerank (Elasticsearch docs, rank_window_size) — measure recall on judged queries
  • ids and ranks only until the end — RRF needs nothing else; fetch bodies for the final n (about 1.2 KB per leg for 100 hits) — sharded or remote stores
  • route exact-identifier queries to lexical only; cache query embeddings — skips a leg or a model pass — repeated or exact queries
  • fusion before reranking — near-zero latency versus a model call per document — decide first whether a reranker pays
• Naive → standard → state of the art:
  • sequential legs, raw scores added · latency sum of both, larger-magnitude list wins silently
  • parallel legs, RRF with k = 60 · max of the legs plus about 5 µs
  • tuned convex combination or weighted RRF, then a cross-encoder on the top 20-50 · best quality (Bruch et al. 2023), model cost per candidate

Implementation notes

• Use a fast hasher (FxHash/ahash) or sort-merge on ids; with W ≤ 200 a Vec + sort beats a hash map's allocations. Pre-size the map to Σ W.
• Ranks must be 1-based after de-duplication; if a retriever returns chunks, collapse to document id first (best chunk or sum) and say which.
• Weights: RRF with w_i lets you favour one retriever (Qdrant exposes per-prefetch RRF weights, default 1.0).
• CC normalization: min-max over the window is the common choice; it is unstable when the window holds few hits, since the extremes define the scale. Alternatives: z-score or a theoretical bound (cosine → (s+1)/2).
• Make ties deterministic (doc id) so pagination does not shuffle; keep W fixed across pages, as Elasticsearch requires for from/size paging.
• In SQL, RRF is a FULL OUTER JOIN of two ranked CTEs with COALESCE(1.0/(k+rank), 0) (pgvector's example uses k = 60).

Pitfalls

• Adding raw BM25 and cosine scores: the larger-magnitude list wins, silently.
• Treating RRF's k = 60 as sacred. Bruch et al. report RRF is sensitive to its parameters and that a tuned CC beats it in- and out-of-domain; with a small judged set, tune.
• Min-max on a tiny or constant list: divide by zero, or one outlier flattening everything else (handled above for span 0 only).
• Fusing lists from different candidate pools: a document absent from one list is penalized only because that retriever's window was short; widen W or let filtered search apply the same filter in both.
• Postgres ts_rank is not BM25; the lexical leg's quality then differs from what benchmarks assume.
• Fusing near-duplicates: agreement is inflated when both lists return the same document in many chunks.
• No evaluation set: any weight is a guess. Measure nDCG@10 or recall@k on a few dozen judged queries.

Variants and alternatives

In production

Search engines: Elasticsearch (rrf retriever, rank_constant default 60), OpenSearch (normalization-processor with min_max or l2 normalization and arithmetic_mean, geometric_mean or harmonic_mean combination; a score-ranker processor for RRF), Qdrant (RRF, weighted RRF and DBSF fusion in the Query API), Weaviate (hybrid query with alpha: 0 keyword only, 1 vector only; ranked and relative-score fusion), Milvus (hybrid search with RRF and weighted rankers). Databases: Postgres with pgvector plus full-text search. ML retrieval: RAG first stages built on any of the above.

Implementations

Sources

• G. V. Cormack, C. L. A. Clarke, S. Büttcher, Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods, SIGIR 2009. paper
• S. Bruch, S. Gai, A. Ingber, An Analysis of Fusion Functions for Hybrid Retrieval, ACM TOIS 2023. paper
• E. A. Fox, J. A. Shaw, Combination of Multiple Searches, TREC-2, 1994. paper
• Elasticsearch reference, Reciprocal rank fusion. docs
• pgvector-python, hybrid search example with RRF in SQL. code
• Qdrant docs, Hybrid queries. docs
• OpenSearch docs, Normalization processor. docs