Rank Fusion: Reciprocal Rank Fusion and the Geometry of Rank Aggregation

Overview & motivation

BM25 gives us a lexical ranking: it scores a document by the exact query terms it contains, weighted by how rare and how saturated those terms are. A dense dual-encoder gives us a semantic ranking: it embeds query and document into a shared vector space and scores by cosine similarity, so a passage that paraphrases the query without sharing its words can still rank highly. Each catches what the other misses — BM25 nails the literal ticker, CUSIP, and line-item match that a paraphrase-trained embedding smears into near-synonyms; the dense leg recovers the relevant passage that shares no surface tokens with the query at all. Production hybrid retrieval runs both and must combine their rankings into one.

The obstacle is that the two scores are not commensurable. BM25 is an unbounded sum of per-term weights; cosine similarity lives in $[-1, 1]$. The naive fix — add the two scores per document — lets whichever list has the wider numeric range dictate the result, so the combination depends on an accident of scale rather than on agreement between the retrievers. The method that dominates in practice sidesteps this entirely by throwing the scores away and keeping only the positions: it reads off each document’s rank in each list and fuses those. That method is Reciprocal Rank Fusion (RRF), and it is the doorway to a genuinely rich piece of mathematics — the theory of rank aggregation, where rankings are points in a metric space, the “best combination” is a median permutation, and the cheap heuristic everyone ships sits at a measurable distance from the optimum it does not even try to reach.

Before any algebra, drag the fusion constant and switch between methods to watch positions beat scores:

The corpus in the laboratory is the same finance setup we will analyze throughout: a query, interest rate exposure, run against a small mix of 10-K filing text and earnings-call passages. The lexical leg (BM25) ranks a concise, interest-heavy disclosure first; the dense leg ranks a term-dense call passage first; and each leg buries the other leg’s favorite. The fused column reconciles them. Switch the method to CombSUM and scale the lexical scores up, and watch the fused order collapse onto the lexical list — the failure RRF is built to avoid.

What we cover

1. Score fusion (CombSUM/CombMNZ) and exactly why incompatible scales break it.
2. Reciprocal Rank Fusion: the definition, the reciprocal-rank decay $1/(k+r)$, and what the constant $k$ controls.
3. RRF as a positional voting rule, and the Borda count it converges to as $k \to \infty$.
4. The geometry of rankings: permutations as points, the Kendall-τ distance and Spearman footrule, and the Diaconis–Graham inequality tying them together.
5. The Kemeny consensus — the median permutation — and why computing it is NP-hard.
6. The footrule-optimal aggregate as a polynomial-time 2-approximation of Kemeny.
7. Evaluation over the finance corpus, a finance case study, and the honest caveats.

Score fusion, and why it breaks

The earliest combination methods fuse scores. Given retrievers $\ell = 1, \dots, L$ each assigning document $d$ a score $s_\ell(d)$, CombSUM ranks by the sum $\sum_\ell s_\ell(d)$, and CombMNZ multiplies that sum by the number of lists in which $d$ appears, rewarding documents many retrievers agree on (Fox and Shaw, 1994). Both are reasonable when the scores are commensurable — several runs of the same retriever, say. They fail when the scores are not.

Make the failure concrete. Suppose BM25 scores a relevant filing at $1.9$ and a strong dense match at cosine $0.68$. CombSUM adds them. Now imagine we re-express BM25 in millibels, or simply tune a different saturation constant, so every BM25 score is multiplied by a thousand: the filing now scores $1900$. Nothing about the ranking BM25 produces has changed — the documents are in the same order — yet CombSUM’s output flips entirely, because the BM25 term now dwarfs every cosine value and the sum is, to three significant figures, the BM25 score alone. The combination was never reading agreement between the retrievers; it was reading their units. A practitioner can paper over this with per-list normalization — min–max or $z$-scoring each list before summing — but normalization is brittle in its own way: it is sensitive to outliers and to the score distribution, and a single anomalously high score compresses everything else toward zero. We want a combination rule that cannot be fooled by scale at all. The way to get one is to discard the scores and keep only what survives any rescaling: the order itself.

Reciprocal Rank Fusion

Write $r_\ell(d)$ for the rank of document $d$ in list $\ell$ — its 1-based position, so the top document has rank $1$. RRF scores a document by summing a decaying function of its rank across the lists.

Two design choices are doing the work. First, the contribution from a list depends only on the document’s rank there, never on its score — this is the whole point, and the next section makes its consequence precise. Second, the contribution decays reciprocally in rank: the gap between rank $1$ and rank $2$ is $\frac1{k+1} - \frac1{k+2}$, far larger than the gap between rank $50$ and rank $51$. RRF is therefore top-heavy — being first in a list matters much more than the difference between fortieth and forty-first — which matches what we want from retrieval, where only the head of each list is trustworthy.

The constant $k$ tunes exactly how top-heavy the rule is. Because the reciprocal $1/(k+r)$ is steepest when $k$ is small, a small $k$ exaggerates the advantage of the top ranks: at $k \to 0$ the score is dominated by any list that places $d$ first. A large $k$ flattens the decay toward a straight line in rank, so every position contributes almost equally and only the sum of ranks matters. The celebrated default $k = 60$ is a single empirically chosen number — and, as the rigor flag insists, that is all it is. Drag the $k$ slider in the laboratory and watch the fused order shift as the rule slides between these two regimes; hover any document to see its $1/(k+r)$ contribution from each list, the same decomposition the formula sums.

Scale invariance is the precise statement of why position beats score. It also explains why RRF fuses heterogeneous retrievers so gracefully: a BM25 list, a cosine list, and a learned-sparse list need no shared calibration, because their numeric ranges never enter the computation. Only their orderings do.

RRF as a positional voting rule: the Borda limit

Reading only positions places RRF inside social choice theory: each retriever is a “voter” submitting a ranked ballot over the “candidate” documents, and RRF is a positional scoring rule — it awards each candidate points that depend only on the positions it receives, then sorts by total points. The most classical positional rule is the Borda count, in which a candidate ranked $r$ (1-based) out of $n$ on a ballot earns $n - r$ points. RRF is a different positional rule, with reciprocal weights $1/(k+r)$ in place of Borda’s linear $n - r$ — but the two coincide in a limit.

The distinctness caveat is not a technicality to wave away — it is visible in our finance instance, where the two prize disclosures and the consensus filing all share the same Borda total, a three-way tie. There the limit order is decided not by Borda but by the next term in the expansion, the curvature of $1/(k+r)$, which is exactly why the companion harness verifies the Borda limit on strict random instances rather than on the tied finance one. The lesson is the useful one: at the large-$k$ end RRF is a Borda count, and at the small-$k$ end it is winner-take-the-top; the shipped $k = 60$ interpolates between these, closer to the top-heavy end.

The geometry of rankings

To say what the best combination of ballots is, we need to measure how far two rankings are from each other. A ranking of $n$ documents is a permutation $\sigma$ — equivalently, the rank vector $(\sigma(1), \dots, \sigma(n))$ recording each document’s position — and the set of all $n!$ permutations becomes a metric space once we choose a distance. A permutation is itself a familiar object from statistics: the rank vector of a sample is a deterministic function of its order statistics, so the space rank fusion operates over is exactly the space of orderings that order statistics induce. Two distances matter here.

The Kendall distance is the number of adjacent transpositions needed to turn one ranking into the other — the bubble-sort count, the smallest number of swaps of neighboring items that reconciles them. It is the natural notion of disagreement for rankings: each discordant pair is one “this should be above that, but the other ballot says otherwise.” Counting concordant and discordant pairs is the same machinery that defines the rank statistics of nonparametric testing — Kendall’s τ is a U-statistic, and the Mann–Whitney U is built from the identical pair count — so the geometry here and the inference there share a combinatorial core. The footrule, by contrast, asks how far each item had to move. These two ways of measuring disarray are not independent; they are pinned to each other within a factor of two.

The inequality says the two measures of disarray are equivalent up to a constant: a ranking with many inversions has large displacement and vice versa, and neither can be small while the other is large. We are about to spend that equivalence. The “right” notion of consensus is defined through the Kendall distance, but the Kendall distance is hard to optimize; the footrule is easy to optimize; and Diaconis–Graham is the bridge that lets a footrule answer stand in for a Kendall answer.

The Kemeny consensus

With a distance in hand, the best combination of ballots has a clean definition: the ranking that disagrees least, in total, with the input lists.

The Kemeny consensus is the median permutation under the Kendall metric, and it has a strong optimality property: it satisfies the extended Condorcet criterion — if a majority of lists rank document $a$ above document $b$, then so does the consensus, whenever this is consistent. It is, in a precise sense, the ranking the retrievers “vote for.” In our finance instance this exposes a subtlety worth being precise about. Brute-forcing the consensus shows the Kemeny optimum is not unique — six orderings tie at the minimum total Kendall distance of $3$, and RRF’s own output is one of them. One of those co-optimal orderings lifts the consensus filing — the disclosure ranked second by both legs — to the top, since being everyone’s second is one way to minimize total disagreement; RRF’s positional weights instead break the tie toward each leg’s idiosyncratic leader, scoring the shared-second document by $\frac1{62} + \frac1{62}$ and leaving it third. So RRF is not a worse approximation of the consensus here — it is itself a Kemeny consensus, and the difference is only which co-optimal tie each rule selects. This is still the point of the rigor flag: RRF is a heuristic that never computes the consensus set, so it cannot know its ordering is one optimum among several, nor choose deliberately among them.

The reason it never computes it is decisive.

For the six-document toy corpus we can find the Kemeny optimum by brute force over all $6! = 720$ permutations — the companion harness does — but $n!$ makes that hopeless at retrieval scale. We need a consensus we can actually compute, and Diaconis–Graham tells us where to find one.

A computable surrogate: the footrule 2-approximation

Swap the hard distance for the easy one. Define the footrule-optimal aggregate as the ranking minimizing total footrule distance to the inputs — and observe that, unlike Kemeny, this minimization is a polynomial-time problem.

This is the payoff of the geometry. We cannot compute the median permutation, but we can compute the footrule median in cubic time, and the bridge inequality guarantees it lands within $2\times$ of the true optimum’s disagreement. The companion harness checks the bound directly: across the finance instance and hundreds of random multi-list instances, the footrule aggregate’s Kemeny cost never exceeds twice the brute-force optimum. Where does RRF sit in this picture? Nowhere on the guarantee. RRF is neither the Kemeny optimum nor the footrule 2-approximation; it is a positional heuristic with no proven bound on its distance to consensus. It is fast, it is scale-invariant, and it works extremely well empirically — but the rigorous statements above are about the Kendall–footrule geometry and the matching-based aggregate, not about RRF. Honesty about that distinction is the difference between explaining rank fusion and selling it.

Evaluation: does fusion actually help?

Geometry aside, the practical question is whether fusing two retrievers retrieves better than either alone. Against graded relevance judgments we measure NDCG, the discounted cumulative gain normalized by its ideal. On the finance corpus the answer is clean and is asserted in the harness: each leg, by burying one of the two genuinely relevant disclosures down at rank three, scores NDCG@6 $= 0.980$; RRF, by interleaving the two leaders so both prize disclosures land in the top two, recovers the ideal ordering at NDCG@6 $= 1.000$, strictly beating both legs. The fusion wins not because it is cleverer than either retriever but because the two retrievers fail differently — the lexical leg misses the semantically phrased passage, the dense leg misses the term-exact filing — and a position-based combination keeps whatever either leg ranked highly while discarding the idiosyncratic mistakes neither leg corroborates.

A candid note on the companion code: its dense leg is a deterministic toy embedding — a seeded random projection of bag-of-words counts, scored by cosine — chosen so the notebook is self-contained, CPU-only, and reproducible to the decimal with no model download. By the Johnson–Lindenstrauss lemma a random projection approximately preserves cosine, so this stand-in is really a length-normalized lexical-cosine ranking that disagrees with BM25 because it carries no IDF weighting; it is not a trained semantic encoder, and we do not pretend it captures synonymy a real bi-encoder would. The rank-aggregation mathematics above is entirely indifferent to how the second list is produced — that independence is precisely why the geometry, not the encoder, is the rigorous content of this topic.

Honest caveats

Implementation

The companion notebook (notebookPath) imports the BM25 lexical leg from the BM25 topic, builds the deterministic toy dense leg, and implements RRF, Borda, CombSUM, the Kendall-τ and footrule distances, the footrule aggregate via scipy’s linear_sum_assignment, and an exact brute-force Kemeny consensus. Its verification harness asserts every claim the topic makes, each assert a pedagogical statement made executable: RRF’s order is unchanged when the BM25 scores are scaled by a thousand while CombSUM’s order collapses onto them (Proposition 1); $K \le F \le 2K$ holds across thousands of random permutation pairs (Theorem 1); the RRF order at large $k$ equals the Borda order on strict instances (Proposition 2); the footrule aggregate’s Kemeny cost stays within twice the brute-force optimum across the finance instance and hundreds of random ones (Theorem 2); and NDCG@6 of the RRF fusion strictly exceeds that of either leg on the finance corpus. The FusionLaboratory component above mirrors that corpus, the two input rankings, and the $k = 60$ fused order to the decimal, so the three pillars — math, viz, and code — agree by construction.