📘

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:

Accumulate the RRF score for every document across all lists.
Round each fused score to 6 decimal places.
Sort by rounded score descending; break ties by document id ascending (lexicographic).
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.

Example:

Input:

print(reciprocal_rank_fusion([['a','b','c'], ['b','a','d']], k=1))

Output:

[['a', 0.833333], ['b', 0.833333], ['c', 0.25], ['d', 0.25]]

Reasoning:

With k=1: a is rank 1 then rank 2, giving 1/2 + 1/3 = 0.8333333 -> 0.833333. b is rank 2 then rank 1, the same total. c only appears at rank 3 (1/4 = 0.25) and d only at rank 3 (0.25). Both ties are broken alphabetically.

Constraints:

1 <= len(rankings) <= 20, each inner list has at most 1000 ids
k >= 1; ranks are 1-based (the first element of a list has rank 1)
Round fused scores to exactly 6 decimal places before sorting
Ties on the rounded score are broken by ascending document id
A document missing from a list contributes nothing from that list

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAHard Bootstrap Confidence Interval Width for Eval AccuracyMedium Route to the Cheapest Model Meeting QualityMedium pass@k EstimatorMedium Savings from a Semantic CacheMedium

1. Background Knowledge

Reciprocal Rank Fusion (RRF) is a robust method for combining ranked lists from different retrieval systems. In hybrid search or agent memory contexts, you often have multiple retrievers (e.g., dense vector search, BM25 lexical search, graph traversal) that return results on incompatible scales. Averaging raw scores is impossible because one retriever might output probabilities $[0, 1]$ while another outputs log-likelihoods $[-\infty, \infty]$ . RRF bypasses this by ignoring the scores entirely and relying solely on the rank position of each document within each list.

The core intuition is that a document appearing high in multiple lists is likely more relevant than one appearing high in only one. The formula assigns a score based on the inverse of the rank, dampened by a constant $k$ :

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

Here, $r_i$ is the 1-based index of document $d$ in list $i$ . The constant $k$ (typically 60) prevents any single list from dominating the final score. For instance, if $k=60$ , the top-ranked item gets $1/61 \approx 0.016$ , while the second gets $1/62 \approx 0.016$ . The difference is small, encouraging consensus across retrievers rather than reliance on a single strong signal.

This approach is particularly valuable in Context & Agent Memory systems where an agent might query semantic memory (vectors), factual memory (BM25), and relational memory (graphs) simultaneously. RRF provides a simple, parameter-light way to fuse these heterogeneous signals into a single coherent ranking without requiring complex normalization or training.

2. Algorithm Approach

The problem requires aggregating scores from multiple lists and then sorting based on specific criteria. The general approach involves three main phases:

Aggregation: Iterate through each ranked list and each document within it. Calculate the RRF contribution for that document based on its position (rank) and accumulate it in a dictionary or hash map.
Rounding: After all contributions are summed, round each document's total score to 6 decimal places. This step is critical because floating-point arithmetic can introduce tiny errors, and the problem explicitly requires rounding before sorting to ensure deterministic tie-breaking.
Sorting and Truncation: Convert the aggregated scores into a list of pairs. Sort this list using a composite key: primarily by score (descending) and secondarily by document ID (ascending, lexicographic). Finally, slice the list if top_n is specified.

This pattern is a classic Map-Reduce style operation: map each document occurrence to a score, reduce by summing scores per document, and then post-process (sort/filter).

3. Step-by-Step Strategy

Initialize a Score Dictionary: Create a dictionary scores to store the cumulative RRF score for each document ID. Initialize it as empty or use defaultdict(float).
Iterate Through Rankings:

Loop through each list L in the rankings input.
For each document doc in L, determine its 1-based rank r. You can use enumerate(L, 1) to get both the document and its rank simultaneously.
Calculate the RRF contribution: 1 / (k + r).
Add this contribution to scores[doc].

Round Scores:

Create a new list or update the dictionary to store rounded scores.
Use Python's round(score, 6) function. This ensures that scores like 0.8333333333 become 0.833333.

Prepare for Sorting:

Convert the dictionary items into a list of tuples or lists: [(doc_id, rounded_score),...].

Sort the Results:

Use the sorted() function or .sort() method.
Define a custom key. Since we need descending score but ascending ID, you can use a tuple key: key=lambda x: (-x, x).
The negative sign on the score (-x) ensures higher scores come first (since default sort is ascending). The x ensures that if scores are equal, documents are sorted alphabetically by ID.

Handle top_n:

If top_n is not None, slice the sorted list: result[:top_n].
Otherwise, return the entire sorted list.

Format Output:

Ensure the final output is a list of lists [[doc_id, score],...] as required by the problem statement.

4. Common Pitfalls

0-based vs 1-based Indexing: The RRF formula uses 1-based ranks ( $r_i$ ). If you use enumerate(L), it defaults to 0-based. You must add 1 to the index: r = index + 1.
Rounding Timing: The problem states rounding happens before sorting. If you sort first and then round, you might get incorrect tie-breaking behavior because floating-point precision differences could affect the sort order before rounding equalizes them.
Tie-Breaking Logic: When scores are equal, the document ID must be sorted in ascending lexicographic order. A common mistake is to sort by ID descending or to ignore the secondary sort key entirely. Using (-score, doc_id) in the sort key handles both requirements cleanly.
Floating Point Precision: While round() helps, be aware that 1/3 + 1/2 might not be exactly 0.833333 in binary floating point. Always rely on round(value, 6) for the final comparison and output.
Missing Documents: If a document appears in only one list, it still gets a score. Ensure your aggregation logic handles documents that appear in some lists but not others correctly (i.e., they just don't get additional contributions).

5. Time & Space Complexity

Let $N$ be the total number of documents across all ranked lists (sum of lengths of all inner lists), $D$ be the number of unique documents, and $M$ be the number of ranked lists.

Time Complexity:
Aggregation: Iterating through all documents in all lists takes $O(N)$ time. Dictionary lookups and updates are $O(1)$ on average.
Rounding: Iterating through unique documents takes $O(D)$ time.
Sorting: Sorting $D$ items takes $O(D \log D)$ time.
Total: $O(N + D \log D)$ . Since $D \le N$ , this is effectively dominated by $O(N + D \log D)$ .
Space Complexity:
Storage: We store scores for each unique document, requiring $O(D)$ space.
Output: The result list also stores $O(D)$ elements (or $O(\min(D, \text{top\_n}))$ if truncated).
Total: $O(D)$ auxiliary space.

This approach is efficient and scales well for typical hybrid retrieval scenarios where the number of unique documents is manageable.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.