Problem 111 · Retrieval

Reciprocal Rank Fusion

EasyAI engineering

01Problem

Write `rrf(rankings, k=60, weights=None)` that fuses several ranked lists of doc ids (best first) into one. Each list contributes `weight / (k + rank)` with 1-based ranks; a doc repeated within one list counts only at its first rank. Return `(doc_id, score)` sorted by score descending, ties by doc id.

02Key insight

RRF fuses on ranks, not scores, which is the whole point: BM25 scores and cosine similarities live on incomparable scales, and min-max normalising them is fragile because one outlier rescales everything. The k constant flattens the head so a document ranked well by several retrievers beats one ranked first by a single retriever. It needs no training data, which is why it is the default first step for hybrid search; per-list weights are the cheap tuning knob once you have an eval set.

03Solution

solution.pypython18 lines

from collections import defaultdict


def rrf(rankings: list[list[str]], k: int = 60, weights: list[float] | None = None) -> list[tuple[str, float]]:
    if weights is not None and len(weights) != len(rankings):
        raise ValueError("one weight per ranking")
    scores: dict[str, float] = defaultdict(float)
    for li, ranking in enumerate(rankings):
        w = 1.0 if weights is None else weights[li]
        seen: set[str] = set()
        rank = 0
        for doc in ranking:
            if doc in seen:
                continue
            seen.add(doc)
            rank += 1
            scores[doc] += w / (k + rank)
    return sorted(scores.items(), key=lambda kv: (-kv[1], kv[0]))

Try it first.

TimeO(total list length + U log U)

SpaceO(U) unique docs

tests.py · 8 passing

tests.pypython16 lines

bm25 = ["a", "b", "c", "d"]
dense = ["e", "c", "b", "f"]
fused = rrf([bm25, dense])
assert [d for d, _ in fused][:3] == ["b", "c", "a"]
assert abs(dict(fused)["b"] - (1 / 62 + 1 / 63)) < 1e-15
assert abs(dict(fused)["a"] - 1 / 61) < 1e-15
assert rrf([["x", "x", "y"]]) == rrf([["x", "y"]])
w = rrf([bm25, dense], weights=[0.0, 1.0])
assert w[0][0] == "e"
assert [d for d, _ in rrf([["a", "b"], ["b", "a"]])] == ["a", "b"]
assert rrf([]) == []
try:
    rrf([bm25], weights=[1.0, 2.0])
    assert False
except ValueError:
    pass

04Staff-level follow-up

When is RRF the wrong tool? If one retriever is much stronger, equal-weight RRF drags it down; learn weights or a cross-encoder reranker on the fused candidate set. Also consider that RRF discards score confidence: a BM25 exact match on an error code is a near-certain hit that rank fusion treats like any rank-1 result.