Lab 11

Hybrid Retrieval, Reciprocal Rank Fusion and Reranking

Multi-stage retrieval Hybrid RRF Cross-encoders

Work in progress These notes are still being written and reviewed: content may change, and some parts may still contain mistakes.

Overview of the lab

We have seen two strong but different retrieval paradigms: lexical retrieval (BM25, Lab 04) and dense retrieval (embeddings and vector search, Labs 08–10). BM25 is often strong when exact wording, rare terms or identifiers matter; dense retrieval when semantic similarity matters, wording differs, paraphrases occur. Why choose only one? Modern retrieval systems often combine several retrievers, then apply a more expensive reranker to the best candidates.

BM25 candidates + dense candidates → fusion → larger candidate set → cross-encoder reranking → final top-k

Why hybrid retrieval? Complementary failure modes.
Multi-stage retrieval: candidate generation, then reranking.
Combining BM25 and dense retrieval: score fusion and rank fusion.
Reciprocal Rank Fusion, with a worked example.
Cross-encoder reranking.
Hybrid retrieval on Cranfield and reranking on Cranfield.
Evaluation and trade-offs: stages, latency, ablations.
Summary, and optional exercises.

Learning objectives

By the end you should be able to explain:

why lexical and dense retrieval are complementary, and what hybrid retrieval means;
why combining raw BM25 and dense scores directly can be problematic, and how rank fusion differs from score fusion;
how Reciprocal Rank Fusion works;
why candidate generation and reranking are separate stages;
what a cross-encoder does, and why it is more expensive than a bi-encoder;
how to choose candidate-set sizes, and how to evaluate multi-stage retrieval systems.

Part I

Why hybrid retrieval?

Query A

RFC 9309 robots exclusion protocol

BM25 is likely to do well: RFC 9309 is a very distinctive lexical signal. In Lab 09 the dense model ranked other RFCs above the text that mentions RFC 9309.

Query B

how to fix a broken car engine

A relevant document may say automobile maintenance and engine servicing. Dense retrieval may help, because the wording differs.

Different failure modes: BM25 may miss relevant documents because the query and the document use different vocabulary; dense retrieval may miss them because exact identifiers or rare terms are poorly represented. So the systems are complementary.
The hybrid idea: not "BM25 or dense" but "BM25 and dense": run both retrievers, then combine their candidate rankings. This is hybrid retrieval.

See it: complementary on Cranfield

Part II

Multi-stage retrieval

A modern retrieval pipeline is often not one ranking model but a sequence of stages:

Query

1. Candidate generation

BM25, a dense retriever or a hybrid: a reasonably small set with high recall, e.g. the top 100 of 1,000,000 documents

2. Reranking

a slower, more accurate model applied only to the 100 candidates

Top 10

This is a fundamental IR systems pattern. Why not use the best model on everything? If a sophisticated relevance model takes 20 ms per query–document pair, scoring 1,000,000 documents is impossible; 100 candidates is feasible. That is the key engineering idea.

Try it: the cost of scoring everything

collection size

time per pair

candidates

Recall first, precision later

The stages optimize different goals (Lab 05). Candidate generation should avoid missing relevant material: high Recall@k. Reranking should improve the ordering near the top: nDCG@10, MRR, P@10.

Part III

Combining BM25 and dense retrieval

BM25 returns D8, D2, D5, D9, D1; dense retrieval returns D3, D8, D5, D7, D2. How should we combine them?

Naive score addition

A first idea: \(score(d) = BM25(d) + Dense(d)\). But the two scores live on different scales. For the first Cranfield query, the top five BM25 scores are 27.71, 27.33, 24.74, 22.22, 21.90; the top five dense cosines are 0.719, 0.649, 0.634, 0.612, 0.594. Adding them directly is arbitrary: the sum is decided by BM25, and the cosine barely matters. On all 225 queries the naive sum gets MAP 0.2450, next to BM25's 0.2406 and far from dense retrieval's 0.3207.

Score normalization

Normalize the scores first (min-max: \(\frac{s - \min}{\max - \min}\) over the collection, or z-scores), then combine:

score(d) = \alpha\, s_{BM25}(d) + (1 - \alpha)\, s_{dense}(d)

This can work, but now we must choose the normalization and \(\alpha\), and these choices may depend on the dataset.

Try it: min-max fusion on Cranfield

Every \(\alpha\) from 0 to 1 in steps of 0.05, evaluated with ir_measures on all 225 queries (precomputed in Python).

\(\alpha\)

MAP nDCG@10

Rank fusion

An alternative: ignore the raw score magnitudes and combine the rankings instead. This is rank fusion, attractive because BM25 and dense scores no longer need to be comparable.

Part IV

Reciprocal Rank Fusion

📐 Reciprocal Rank Fusion (RRF)

RRF(d) = \sum_{r \in R} \frac{1}{k + rank_r(d)}

\(R\) = the set of ranked lists; \(rank_r(d)\) = the position of document \(d\) in ranking \(r\); \(k\) = a constant that reduces the effect of very high ranks, commonly \(k = 60\) (Cormack, Clarke & Büttcher, SIGIR 2009).

Intuition: a document gets more credit if it appears high in one ranking, and even more if it appears high in several. Documents absent from a ranking get nothing from it.
RRF is simple, robust, score-scale independent, easy to implement.

Try it: the worked example

The two rankings above, with \(k = 60\): \(RRF(D8) = \frac{1}{61} + \frac{1}{62}\), \(RRF(D2) = \frac{1}{62} + \frac{1}{65}\), \(RRF(D5) = \frac{1}{63} + \frac{1}{63}\), \(RRF(D3) = \frac{1}{61}\). The exact decimals matter less than the point: documents supported by both retrievers accumulate evidence. Edit the lists or change \(k\).

BM25 ranking dense ranking

\(k\)60

rrf.py Python

from collections import defaultdict

def reciprocal_rank_fusion(rankings, k=60):
    scores = defaultdict(float)
    for ranking in rankings:
        for rank, doc_id in enumerate(ranking, start=1):
            scores[doc_id] += 1.0 / (k + rank)
    return sorted(scores.items(), key=lambda x: x[1], reverse=True)

bm25_results = ["D8", "D2", "D5", "D9", "D1"]
dense_results = ["D3", "D8", "D5", "D7", "D2"]
for doc_id, score in reciprocal_rank_fusion([bm25_results, dense_results], k=60):
    print(doc_id, round(score, 5))      # RRF uses only rank positions, not raw scores
# D8 0.03252
# D5 0.03175
# D2 0.03151
# D3 0.01639
# D9 0.01562
# D7 0.01562
# D1 0.01538

💡 The outline also works this example with four-document lists (dense: D3, D8, D5, D2), where D2 is 4th and \(RRF(D2) = \frac{1}{62} + \frac{1}{64}\). This page uses the five-document lists throughout, where D2 is 5th for dense retrieval. Both give D8 > D5 > D2 > D3.

First-half recap

BM25 + dense → candidate fusion → a larger candidate set

Once we have only 50–100 candidates, can we do better than either retriever's original score? Yes: with a model that examines the query and each candidate together. That leads to cross-encoder reranking.

Part V

Cross-encoder reranking

Connect back to Labs 08 and 09

A Transformer produces contextual token representations. A bi-encoder uses that machinery separately: query → Transformer encoder → query vector; document → Transformer encoder → document vector; then a vector similarity. ❗ The crucial constraint: the query and the document do not directly interact before each is compressed into a vector. A cross-encoder changes that: it places the query and the document into the same Transformer input ([CLS] query [SEP] document [SEP]), so token-level interactions can be modeled before a relevance score is produced.

bi-encoder (Lab 09)query↓encoder↓query vectorsimilaritydocument vector↑encoder↑document

cross-encoder[query] + [document]↓one transformer over both texts↓relevance score

Bi-encoder: the query and the document are encoded separately. That is efficient.
Cross-encoder: processes query + document jointly, so it can model interactions between the words of the query and of the document directly, instead of compressing each text into one vector first. For "treatment for myocardial infarction" and "therapy after a heart attack", the model sees both texts simultaneously.
Why it is expensive: for every query–document pair the transformer runs again, and no document score can be precomputed independently of the query. 1 query × 1,000,000 documents is too expensive; 1 query × 100 candidates is practical. This is why reranking is a second-stage operation.

See it: who can attend to whom

The 16 input tokens of the pair treatment for myocardial infarction / therapy after a heart attack. In a bi-encoder, query tokens can only use query tokens and document tokens only document tokens (in fact two separate inputs). In the cross-encoder cross-encoder/ms-marco-MiniLM-L-6-v2 every token attends to every token; the shading is its real attention (average of the 12 heads). Click a row.

layer5

within the same text across query and document ✕ impossible in a bi-encoder

💡 In layer 5, treatment attends most to therapy among the document tokens (0.14), the pieces of myocardial to heart, and ##ction to attack. The weights are small and spread out (much goes to [CLS] and [SEP]); attention shows where information can flow, not a proof of what the model understood. A bi-encoder has none of these cross cells: the only contact between the two texts is one dot product at the end.

Property	Bi-encoder	Cross-encoder
Query / document encoded separately	yes	no
Document vectors precomputable	yes	no
Fast large-scale retrieval	yes	no
Direct query–document interaction	limited	strong
Good for candidate generation	yes	no
Good for reranking	sometimes	yes

query → BM25 + dense → RRF → top 50 → cross-encoder → top 10

cross_encoder.py Python

# pip install sentence-transformers
from sentence_transformers import CrossEncoder

reranker = CrossEncoder("cross-encoder/ms-marco-MiniLM-L-6-v2")
query = "treatment for myocardial infarction"
reranker.predict([(query, "therapy after a heart attack"),
                  (query, "banana nutrition and healthy diets"),
                  (query, "myocardial infarction is not a topic of this document")])
# array([ -6.145, -11.219,  -0.547], dtype=float32)     (rounded)

💡 The scores are unnormalized relevance scores (logits): only their order matters. The paraphrase beats the unrelated text, but the sentence that denies being about myocardial infarction scores highest: this model was trained on MS MARCO web queries and still leans heavily on shared words. Rerankers are stronger, not infallible.

Part VI

Hybrid retrieval on Cranfield

Reuse the systems of earlier labs: BM25 (Lab 04) and dense retrieval with all-MiniLM-L6-v2 (Lab 10), each returning (doc_id, title, score).

search_hybrid.py Python

def search_hybrid(query, k=10, depth=50):
    bm25 = search_bm25(query, k=depth)
    dense = search_dense(query, k=depth)
    bm25_ids = [doc_id for doc_id, _, _ in bm25]
    dense_ids = [doc_id for doc_id, _, _ in dense]
    fused = reciprocal_rank_fusion([bm25_ids, dense_ids], k=60)
    return fused[:k]

Try it: BM25, dense and hybrid, side by side

For one query, the three top-10 lists with their relevance grades; the hybrid list marks where each document came from (B+D both, B BM25 only, D dense only). The table evaluates all 225 queries with the current number of candidates from each retriever and \(k\), in your browser.

candidates from each

RRF \(k\)

💡 Checked against ir_measures. On Cranfield, where dense retrieval is much stronger than BM25, RRF with \(k = 60\) mostly improves the top (MRR 0.5706 against 0.5482 for dense) while MAP and Recall@100 stay slightly below dense retrieval (0.3155 vs 0.3207, 0.7716 vs 0.7783): fusing with a weaker system costs a little. Tuned min-max fusion (\(\alpha\) between 0.15 and 0.3) did better here, and a smaller \(k\) (10) gives nDCG@10 0.3591: fusion also has hyperparameters.

Part VII

Reranking on Cranfield

rerank.py Python

def rerank(query, candidate_ids, top=50):
    candidate_texts = [f"{titles[i]}. {docs[i].text}" for i in candidate_ids[:top]]
    pairs = [(query, text) for text in candidate_texts]
    scores = reranker.predict(pairs, batch_size=64)
    reranked = sorted(zip(candidate_ids[:top], scores), key=lambda x: x[1], reverse=True)
    return [i for i, _ in reranked] + candidate_ids[top:]    # the rest keeps its order

# 36,256 query-document pairs (every BM25 or dense top-100 candidate of the 225 queries):
# 187 s on a laptop GPU, 5.2 ms per pair; 12.6 ms per pair on its CPU

❗ The reranker does not search the full collection; it only reorders a candidate set. Retriever → broad candidate generation; reranker → precise ordering. So candidate size matters: if the retriever returns only the top 10 and the relevant document was 17th, the reranker can never recover it. A common pattern: retrieve the top 50 or 100, rerank, keep the top 5 or 10.

Try it: rerank the hybrid candidates

Real ms-marco-MiniLM-L-6-v2 scores, computed in Python for every candidate. The arrows show each document's rank before reranking.

candidates reranked

Part VIII

Evaluation and trade-offs

Candidate-generation quality

Recall@50, Recall@100

Did the candidate generator include the relevant documents?

Final-ranking quality

nDCG@10, MRR, P@10, MAP

Did the reranker put the best candidates at the top?

End-to-end comparison and ablation

If the final system improves, ask why: was it dense retrieval, RRF or reranking? An ablation removes one component at a time, which is much more informative than evaluating only the final pipeline. Computed in your browser, identical to ir_measures:

Reranking the hybrid does not help on Cranfield: nDCG@10 drops from 0.3545 to 0.3515. The reranker learned relevance from MS MARCO web questions, not from aeronautics abstracts: a domain shift, one of the embedding failures listed in Lab 09.
Reranking BM25 helps a lot (nDCG@10 0.2822 → 0.3356): the stronger the first stage, the less room the reranker has, and the more its own mistakes show.
Only evaluation tells which components earn their cost.

Latency also matters

Stage	Cost (measured on a laptop, Cranfield)	Grows with
BM25	3.4 ms per query (`rank_bm25`, pure Python)	the postings of the query terms
Dense ANN	one query encoding, then a few µs of index search (Lab 10)	fast after indexing
Cross-encoder	12.6 ms per pair on CPU: 0.63 s for 50 candidates	the number of candidates

A reranked system may be more accurate but slower. A real system balances effectiveness, latency, compute cost and memory: the architecture is designed around computational constraints.

Summary: key takeaways

query → BM25 + dense retrieval → RRF → top 50 → cross-encoder → top 10

BM25 and dense retrieval are complementary candidate generators.
Rank fusion combines rankings without requiring comparable raw scores.
RRF is a simple and robust hybrid-retrieval baseline.
Cross-encoders are too expensive for full-corpus retrieval but strong for reranking; they still need evaluation on your collection.
Multi-stage retrieval separates high-recall candidate generation from high-precision final ranking.

Optional exercises

Four systems on Cranfield: BM25, dense, hybrid RRF, hybrid RRF + cross-encoder, evaluated with Recall@100, MRR, MAP and nDCG@10 (the ablation table above). Then:

1Does hybrid retrieval improve Recall@100?

Over BM25, clearly (0.6513 → 0.7716). Over dense retrieval, no: 0.7716 against 0.7783. With 100 candidates from each and 100 kept, fusion pushes out some documents that only dense retrieval ranked lower.

2Does reranking improve nDCG@10? Does it ever hurt?

For the hybrid top 50, on average it hurts slightly (0.3545 → 0.3515), and per query it helps and hurts about equally often (the note under the ablation table). For BM25 it helps a lot, for dense retrieval a little (0.3555 → 0.3634).

3Are there queries where BM25 alone is still strongest? Where dense retrieval contributes unique relevant documents?

Yes to both: see the counts in Part I. BM25 has the higher AP on dozens of queries, and each system finds relevant documents the other misses. Use the side-by-side widget to inspect them.

RRF parameter: test \(k\) = 10, 30, 60, 100 with nDCG@10 and Recall@100 (the hybrid widget's slider). The purpose is not a universal best value, but to see that fusion also has hyperparameters.
Candidate size: rerank the top 10, 20, 50, 100; measure reranking latency, nDCG@10 and Recall@candidates. Too few candidates → the reranker cannot recover missed relevant documents; too many → more computation.
Failure analysis: find three queries where BM25 beats dense retrieval and three where dense wins; inspect the hybrid result, and look for exact lexical matches, rare technical terms, paraphrases, vocabulary mismatch, short or ambiguous queries.