Reciprocal Rank Fusion over Hybrid Retrievers

Problem Statement

A hybrid agent memory queries several retrievers at once - a dense vector index, a BM25 lexical index, a graph walk - and each returns its own ranked list. Their scores are on incompatible scales, so you cannot simply average them. Reciprocal Rank Fusion (RRF) solves this by throwing the scores away and fusing on rank alone.

Background

For a document $d$ appearing at 1-based rank $r_i$ in ranked list $i$, RRF assigns

$\text{RRF}(d) = \sum_{i \,:\, d \in L_i} \frac{1}{k + r_i}$

The constant $k$ (conventionally 60) damps the influence of the very top of any single list, so a document ranked #1 by one retriever cannot dominate a document ranked #2 or #3 by all of them. That consensus bias is exactly why RRF is the default fusion step in hybrid memory stores.

Your Task

Implement:

def reciprocal_rank_fusion(rankings, k=60, top_n=None):

• rankings: list of ranked lists; each inner list holds document ids (strings), best first, no duplicates within a list.
• k: the RRF damping constant.
• top_n: if not None, return only the first top_n fused results.

Steps:

1. Accumulate the RRF score for every document across all lists.
2. Round each fused score to 6 decimal places.
3. Sort by rounded score descending; break ties by document id ascending (lexicographic).
4. Return a list of [doc_id, rounded_score] pairs, truncated to top_n when given.

Input/Output Format

Returns list[list] - each element is [str, float]. Rounding happens before sorting, so two documents whose scores agree to 6 dp are ordered by id.

Sample

lists = [["a", "b", "c"], ["b", "a", "d"]]
print(reciprocal_rank_fusion(lists, k=1))
# [['a', 0.833333], ['b', 0.833333], ['c', 0.25], ['d', 0.25]]

a scores 1/2 + 1/3 = 0.833333 and b scores 1/3 + 1/2 = 0.833333 - a tie, broken by id.