Hybrid Retrieval with Reciprocal Rank Fusion

The problem

Hybrid retrieval runs two retrievers, for example BM25 (which looks at words) and a dense retriever (which looks at meaning), and merges their rankings. Their scores are on different scales, so you cannot just add them. RRF (reciprocal rank fusion) uses only ranks, which are comparable.

Reciprocal rank fusion

where the sum runs over the rankings $r$, $\mathrm{rank}_r(d)$ is the position of document $d$ in ranking $r$ (starting at 1), and $k$ is a constant (Elasticsearch uses 60). A document absent from a ranking adds nothing for it. A document ranked well by several retrievers gets a high total.

Example. Ranking 1 is ["A", "B", "C"], ranking 2 is ["B", "D", "A"], $k = 60$.

document	ranking 1	ranking 2	RRF
A	$1/61$	$1/63$	$0.03227$
B	$1/62$	$1/61$	$0.03252$
C	$1/63$	missing	$0.01587$
D	missing	$1/62$	$0.01613$

Sorted: ["B", "A", "D", "C"]. B was second in the first ranking and first in the second: it beats A, which was first in one and last in the other.

The prompt

After retrieval, the passages go in the prompt. build_prompt(question, passages) numbers them so that the model can cite them:

[1] first passage
[2] second passage

Question: ...
Cite the passages like [1].

Example. build_prompt("Who?", ["p1", "p2"]) is the four lines [1] p1, [2] p2, an empty line, Question: Who?, and Cite the passages like [1]. (the exact format above, with the passages one per line).

What to implement

• rrf(rankings, k=60): rankings is a list of rankings, each a list of document ids, best first. Return all documents that appear in any ranking, sorted by RRF score, best first; on ties, the document that appears first (scanning the rankings in order) comes first.
• build_prompt(question, passages): the string above.

Requirements

• Standard library only for rrf.

Hint

A dict from document to score, filled while scanning the rankings in order, keeps the order of first appearance. sorted is stable, so ties keep that order.