Reciprocal Rank Fusion (RRF)

Reciprocal Rank Fusion (RRF)

Reciprocal Rank Fusion (RRF) is a popular method for combining the rankings from multiple search systems (such as dense vector retrieval and sparse keyword search) without needing to normalize their raw relevance scores.

The formula to compute the RRF score for a document $d$ is:

$RRF(d) = \sum_{m \in M} \frac{1}{k + r_m(d)}$

Where:

• $M$ is the set of rank lists (e.g., one from vector search, one from keyword search).
• $r_m(d)$ is the 1-indexed rank of document $d$ in the rank list $m$.
• $k$ is a constant hyperparameter (defaulting to 60) that penalizes lower ranks and ensures scores don't drop off too rapidly.

Tasks

Implement the function reciprocal_rank_fusion(vector_results, keyword_results, k) to:

1. Calculate the RRF score for all unique documents appearing in either list.
2. Rank the documents based on their accumulated RRF score in descending order.
3. Resolve ties by sorting the document IDs alphabetically in ascending order.
4. Return a list of tuples containing (document_id, rrf_score).

Example

vector_results = ["doc1", "doc2"]
keyword_results = ["doc2", "doc3"]
k = 60

# doc1: rank 1 in vector -> score = 1/(60+1) = 0.01639
# doc2: rank 2 in vector, rank 1 in keyword -> score = 1/(60+2) + 1/(60+1) = 0.03252
# doc3: rank 2 in keyword -> score = 1/(60+2) = 0.01613

# Returns: [("doc2", 0.03252...), ("doc1", 0.01639...), ("doc3", 0.01613...)]