Hybrid Search: Reciprocal Rank Fusion + Reranking

BM25 (sparse, lexical) and embedding cosine (dense, semantic) each catch what the other misses: BM25 nails exact terms and rare codes, dense retrieval catches paraphrases. Production systems run both and combine the results. The catch is that their scores live on totally different scales, so you cannot just add them. The standard fix is to combine by rank, not score.

Reciprocal Rank Fusion (RRF) does exactly that. Each retriever gives you an ordered list of document ids. An item's fused score is the sum, across the lists, of 1 / (k + rank), where rank is its 1-based position in that list and k is a constant (60 is the common default that softens the gap between ranks 1 and 2):

score(item) = sum over lists of  1 / (k + rank_in_that_list)

An item near the top of both lists collects two large contributions and wins. An item that only one retriever found still gets partial credit. Then sort by fused score descending. For determinism when two items tie, break the tie by the item id.

The second stage is reranking. Fusion is cheap and approximate; a cross-encoder reads the query and a candidate together and scores their relevance directly, which is far more accurate but too slow to run over the whole corpus. So you fuse to get a short candidate list, then rerank just those few with the expensive model. We cannot run a real cross-encoder here (no model, no GPU), so you are handed its output as a score table mapping each candidate to its relevance score, and you re-sort by it.

For context, a real reranker call looks like this (NOT used in grading):

# a real cross-encoder, requires a model download and is NOT run here
from sentence_transformers import CrossEncoder
ce = CrossEncoder("cross-encoder/ms-marco-MiniLM-L-6-v2")
scores = ce.predict([(query, doc) for doc in candidates])

Build two functions. rrf(rank_lists, k=60) takes a list of ranked id lists and returns the fused ids sorted by RRF score descending (ties broken by id). rerank(candidates, score_table) returns the candidates re-sorted by their score in score_table descending (ties broken by id).