Reciprocal Rank Fusion (RRF)

Background

Production RAG and search systems rarely trust a single retriever. Hybrid retrieval runs a lexical retriever (BM25) and a dense embedding retriever in parallel, then has to fuse their two ranked lists into one. The problem: BM25 scores are unbounded term weights while dense scores are cosine similarities in $[-1, 1]$ — different scales, so you cannot simply add them. Reciprocal Rank Fusion (RRF) sidesteps this entirely by throwing away the raw scores and using only each document's rank in each list. It is the production default because it needs no score calibration and no tuning, and it rewards a document that ranks well across several retrievers over one that merely tops a single retriever.

Problem statement

Implement reciprocal_rank_fusion(rankings, k=60) that fuses several ranked lists of document IDs into one combined ranking. For a document $d$:

$$\text{RRF}(d) = \sum_{q} \frac{1}{k + \text{rank}_q(d)}$$

where the sum is over every input list $q$ that contains $d$, $\text{rank}_q(d)$ is $d$'s 1-indexed position in list $q$ (the top item has rank 1), and $k$ is a smoothing constant (the original paper uses 60). A list that does not contain $d$ contributes nothing. Return the document IDs ordered by descending RRF score.

Input

• rankings — list[list[str]]. Each inner list is one retriever's results, best first (index 0 = rank 1). Different lists may contain different documents; each list has no repeats.
• k — int, the RRF constant (default 60). A larger k flattens the contribution of the top ranks.

Output

• list[str] — the deduplicated union of all document IDs, sorted by descending RRF score. Ties in score are broken deterministically by ascending document ID.

Examples

Example 1 — consensus beats a single-list leader

Input:  rankings = [["B", "A"], ["C", "D", "E", "F", "A"]],  k = 60
Output: ["A", "B", "C", "D", "E", "F"]

Explanation: A is rank 2 in list 1 and rank 5 in list 2, so $\text{RRF}(A)=\frac{1}{60+2}+\frac{1}{60+5}=0.0315$. B tops list 1 only: $\frac{1}{60+1}=0.0164$. C tops list 2 only: $\frac{1}{60+1}=0.0164$. Even though A never ranked first, appearing in both lists makes it the consensus winner. B and C tie, so the ascending-ID rule puts B before C.

Example 2 — a single list is returned unchanged

Input:  rankings = [["x", "y", "z"]],  k = 60
Output: ["x", "y", "z"]

Explanation: with one list the scores are strictly decreasing ($\frac{1}{61} > \frac{1}{62} > \frac{1}{63}$), so RRF preserves the original order.

Constraints

• Ranks are 1-indexed: the document at index 0 contributes $\frac{1}{k+1}$.
• A document absent from a list adds 0 to its score (no special-casing, no error).
• The output is the union of all IDs, each appearing once.
• Break score ties by ascending document ID so the result is fully deterministic.
• k >= 1; assume each inner list contains unique IDs.

Notes

• Why ranks, not scores. Because RRF reads only positions, it never has to reconcile BM25's scale with cosine similarity — which is exactly why hybrid search reaches for it instead of a learned weighted sum.
• The role of $k$. With $k=60$, rank 1 contributes $\frac{1}{61}$ and rank 2 contributes $\frac{1}{62}$ — close together, so the method is forgiving of small ordering differences and rewards documents surfaced by many retrievers.