Reciprocal Rank Fusion
Implement Reciprocal Rank Fusion (RRF) to combine multiple ranked lists.
RRF combines rankings from multiple retrieval systems: RRF(d)=∑r∈R​k+rankr​(d)1​
where k is a constant (typically 60) and rank_r(d) is the 1-based rank of document d in ranking r. Documents not in a ranking are ignored for that ranking.
Input:
- Line 1: k (constant)
- Line 2: M (number of rankings)
- Next M lines: space-separated document IDs (in ranked order)
Output: Document IDs sorted by RRF score (descending), one per line. Break ties by lower ID first.
Example:
60 2 A B C D B D A
A B D C
- We start by reading the input values: k=60 and M=2 ranked lists.
- For each document, we calculate the RRF score using the formula: RRF(d)=∑r∈R​k+rankr​(d)1​. For example, RRF(A)=60+11​+60+31​=611​+631​.
- We calculate the RRF scores for all documents:
- RRF(A)=611​+631​
- RRF(B)=60+21​+60+11​=621​+611​
- RRF(C)=60+31​=631​
- RRF(D)=60+41​+60+21​=641​+621​
- We sort the documents by their RRF scores in descending order and break ties by their IDs: RRF(B)>RRF(A)>RRF(D)>RRF(C), but since RRF(B) and RRF(A) are very close, we need to compute them precisely to determine the order, which results in A having a slightly higher score than B due to the actual values of 611​+631​ and 621​+611​.
Constraints:
- k > 0 (typically 60)
- Rankings may have different lengths
- Rankings may contain different documents
- Round RRF scores to 6 decimal places for comparison
More from LLM 3: Applications & Evaluation
Background Knowledge
The Reciprocal Rank Fusion (RRF) method is used to combine multiple ranked lists into a single list. This technique is commonly applied in information retrieval systems where multiple ranking models or algorithms are used to retrieve documents based on a query. The goal of RRF is to fuse these rankings to produce a more accurate and robust ranking. The RRF score for a document d is calculated as RRF(d)=∑r∈R​k+rankr​(d)1​, where k is a constant and rankr​(d) is the rank of document d in ranking r.
In the context of information retrieval, rankings refer to the ordered lists of documents retrieved by a system in response to a query. Each document in the list is assigned a rank, which represents its position in the list. The reciprocal rank of a document is the reciprocal of its rank, which gives more weight to documents that appear higher in the ranking. By summing the reciprocal ranks of a document across multiple rankings, RRF aims to identify documents that consistently appear near the top of the rankings.
The constant k in the RRF formula is used to prevent division by zero and to give more weight to documents that appear in multiple rankings. A typical value for k is 60, but this can be adjusted depending on the specific application. The RRF method is simple to implement and has been shown to be effective in combining multiple rankings, but it can be sensitive to the choice of k and the quality of the input rankings.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.