Reciprocal Rank Fusion

The problem, from first principles

Different retrievers are good at different things. Keyword search (BM25) finds exact terms and rare identifiers, vector search finds paraphrases. Hybrid search runs both and merges the lists, but their scores live on incompatible scales (BM25 scores are unbounded, cosine similarities are in [-1, 1]), so adding raw scores is meaningless. Reciprocal rank fusion (RRF) ignores scores and uses only ranks: a document earns 1 / (k + rank) from each list it appears in, and documents are sorted by their total. A document ranked well by several retrievers rises to the top, and the constant k (typically 60) softens the advantage of rank 1.

From theory to code

Implement reciprocal_rank_fusion.

Constraints

• rankings is a list of ranked lists of document ids, best first. Ranks start at 1.
• The score of a document is the sum over the lists in which it appears of 1 / (k + rank). Documents missing from a list get nothing from it.
• Return the list of all document ids sorted by score descending, ties broken by id ascending (ids are sortable).

Hints