Reranking and hybrid search: Exercises — AI-ML deep dive

Before we start, a one-line reminder of the four formulas this page drills, so every symbol below is already defined:

The whole pipeline these tools live in is one picture — keep it in mind as you solve:

Prerequisite notes if you get stuck: BM25 and TF-IDF, Embeddings and Bi-encoders, Cross-encoders and Sentence Transformers, Vector Databases and ANN Search, Evaluation - Recall@k and MRR, Lost in the Middle - LLM context limits, Retrieval-Augmented Generation (RAG).

Level 1 — Recognition

Exercise 1.1 (L1)

Match each symptom to the retriever that causes it, and name the fix: (a) A query for the drug "Metformin" returns a chunk about a different diabetes drug that never names Metformin. (b) A query for "car maintenance" misses a perfect chunk that only ever says "automobile servicing".

Recall Solution

(a) This is dense (vector) search returning a semantically near but literally wrong chunk — embeddings encode meaning, not exact tokens. Fix: add sparse BM25 so the exact token Metformin is matched. (b) This is sparse (keyword) search failing because "car" and "automobile" share no tokens. Fix: add dense embeddings so meaning matches across different words. The moral: each retriever fails exactly where the other succeeds — that is why hybrid combines them.

Exercise 1.2 (L1)

For each quantity, state whether it is unbounded or lives in a fixed range, and give the range precisely: (a) a BM25 score, (b) a cosine similarity, (c) an RRF contribution $\frac{1}{k + rank}$ with $k = 60$ .

Recall Solution

(a) Unbounded above: a BM25 score is a sum over query terms, each term capped at $(k_{1} + 1) \cdot IDF (q_{i})$ , but more matching terms keep adding — so there is no fixed ceiling. Range: $(- \infty, \infty)$ in principle, and in the common case where every matched term is rarer than half the corpus, $[0, \infty)$ . Important caveat: the per-term IDF can be negative when a term appears in more than half the documents (see Ex 2.1, where "the" gives IDF $\approx - 3.55$ ). A matched-but-common term therefore lowers the score, so a single BM25 term score — and hence a total — can be negative. Most engines clamp negative IDF to 0, which restores the clean $[0, \infty)$ range; without clamping the true range is $(- \infty, \infty)$ . (b) Fixed range $[- 1, 1]$ — this is guaranteed only for the cosine of two vectors. For unnormalised embeddings the raw dot product $q \cdot d$ is unbounded, but the division by $∥ q ∥ ∥ d ∥$ is exactly what forces the result back into $[- 1, 1]$ . In practice embedding models are trained so real query–doc pairs land in $[0, 1]$ . (c) Fixed range $(0, \frac{1}{61}]$ : best possible is rank 1 giving $\frac{1}{61} \approx 0.0164$ ; it shrinks toward 0 as rank grows. Changing $k$ shifts this range — a smaller $k$ (say 10) makes rank 1 worth $\frac{1}{11} \approx 0.091$ and sharpens the gap between rank 1 and rank 2; a larger $k$ flattens all contributions toward equality. That is why $k$ is called a smoothing constant. This mismatch — (a) unbounded and possibly signed, (b) bounded — is the reason we cannot add BM25 and cosine directly, and why RRF (which only reads rank) is scale-free.

Level 2 — Application

Exercise 2.1 (L2) — IDF from scratch

A corpus has $N = 1000$ documents. The term "the" appears in $n = 990$ of them; the term "photosynthesis" appears in $n = 8$ . Compute $IDF$ for each using $IDF (q) = ln \frac{N - n + 0.5}{n + 0.5} + 1.$ Which term is more discriminating, and does the sign of the raw log agree?

Recall Solution

"the": $\frac{1000 - 990 + 0.5}{990 + 0.5} = \frac{10.5}{990.5} = 0.010601$ . $ln (0.010601) = - 4.5455$ . Add 1: $IDF = - 3.5455$ . "photosynthesis": $\frac{1000 - 8 + 0.5}{8 + 0.5} = \frac{992.5}{8.5} = 116.7647$ . $ln (116.7647) = 4.7602$ . Add 1: $IDF = 5.7602$ . Interpretation: "photosynthesis" (IDF $\approx 5.76$ ) is hugely more discriminating than "the" (IDF $\approx - 3.55$ ). A negative IDF means the term is in most documents (here 990 of 1000, well over half), so its presence tells you almost nothing — BM25 actively penalises matching it (this is exactly the negative-score case flagged in Ex 1.2a). That is the "the is useless, photosynthesis is gold" rule made quantitative.

Exercise 2.2 (L2) — BM25 saturation

Take $k_{1} = 1.5$ , $b = 0.75$ , a document of length $∣ D ∣ = 200$ with $avgdl = 200$ (so the length factor is exactly 1). Let $IDF = 3$ . Compute the term score for $f = 1, 5, 50$ , and state the theoretical ceiling.

Recall Solution

With $∣ D ∣ = avgdl$ the denominator length factor is $1 - b + b \cdot 1 = 1$ , so $s = IDF \cdot \frac{f ( k _{1} + 1 )}{f + k _{1}} = 3 \cdot \frac{2.5 f}{f + 1.5} .$

$f = 1 : 3 \cdot \frac{2.5}{2.5} = 3.0000$
$f = 5 : 3 \cdot \frac{12.5}{6.5} = 5.7692$
$f = 50 : 3 \cdot \frac{125}{51.5} = 7.2816$ Ceiling: as $f \to \infty$ , $s \to IDF \cdot (k_{1} + 1) = 3 \cdot 2.5 = 7.5$ . Going from 1 to 5 occurrences added $2.77$ ; going from 5 to 50 (ten times more!) added only $1.51$ . That is the "50th cat" diminishing-returns effect the saturation curve is designed to produce.

The figure below plots this curve. The horizontal axis is the term frequency $f$ ; the vertical axis is the term score $s$ . The red curve is $s (f)$ ; the dashed black line is the ceiling $7.5$ . Notice the three black dots at $f = 1, 5, 50$ : they rise fast early, then hug the ceiling — visual proof that extra occurrences buy less and less. This is the single most important shape in BM25.

Exercise 2.3 (L2) — Cosine by hand

Query vector $q = (3, 4)$ , document vectors $d_{1} = (4, 3)$ and $d_{2} = (- 3, - 4)$ . Compute both cosine similarities. Which doc is more relevant, and what does the sign of $d_{2}$ 's score mean geometrically?

Recall Solution

$∥ q ∥ = 9 + 16 = 5$ . $d_{1}$ : dot $= 3 \cdot 4 + 4 \cdot 3 = 24$ ; $∥ d_{1} ∥ = 16 + 9 = 5$ ; $cos = \frac{24}{25} = 0.9600$ . $d_{2}$ : dot $= 3 \cdot (- 3) + 4 \cdot (- 4) = - 25$ ; $∥ d_{2} ∥ = 9 + 16 = 5$ ; $cos = \frac{- 25}{25} = - 1.0000$ . $d_{1}$ is nearly parallel to the query (angle $\approx 16°$ ) → highly relevant. $d_{2}$ points in the exact opposite direction (angle $= 180°$ ) → maximally irrelevant: cosine $= - 1$ . The sign tells you which side of perpendicular you're on; magnitude tells you how aligned.

The picture makes this concrete: the red query arrow and each document arrow, with the angle between them shaded.

Level 3 — Analysis

Exercise 3.1 (L3) — RRF fusion, full ranking

Three documents rank in two retrievers as follows ( $k = 60$ ):

Doc	BM25 rank	Dense rank
A	1	30
B	3	3
C	— (not found)	1

Compute each RRF score and give the final order. Explain why the winner wins.

Recall Solution

Using the edge-case convention from the top of the page: an absent rank is $\infty$ , contributing $0$ , so we simply drop that term.

$RRF (A) = \frac{1}{61} + \frac{1}{90} = 0.016393 + 0.011111 = 0.027505$
$RRF (B) = \frac{1}{63} + \frac{1}{63} = 0.015873 + 0.015873 = 0.031746$
$RRF (C) = \frac{1}{61} = 0.016393$ (only in dense) Final order: B > A > C. Why B wins: it is consistently good in both lists. A was #1 in BM25 but dragged down by its poor dense rank (30). C was #1 in dense but invisible to BM25, so it has only one term. RRF rewards cross-verified agreement over a single strong signal — exactly the behaviour we want, because a chunk found by both keyword and meaning is far more likely to be truly relevant.

Exercise 3.2 (L3) — Recall@k vs MRR under reranking

A pipeline retrieves 100 candidates; the single gold document sits at rank 40 after hybrid fusion. A cross-encoder reranks and moves it to rank 2. We then feed the LLM only the top-5. (a) Did Recall@100 change? (b) Did Recall@5 change? (c) Compute the reciprocal rank before and after (MRR contribution).

Recall Solution

Recall@k = 1 if the gold doc is somewhere in the top-k, else 0. Reciprocal rank $= \frac{1}{rank of gold}$ . (a) Recall@100: gold was at 40 (in), now at 2 (in). Unchanged: 1 → 1. Reranking never adds or removes documents — it only reorders the same 100. (b) Recall@5: before, gold at rank 40 is outside top-5 → 0. After, gold at rank 2 is inside → 1. Changed: 0 → 1. This is the whole point: reranking rescues a relevant doc that the LLM would otherwise never see. (c) Reciprocal rank: before $= \frac{1}{40} = 0.0250$ ; after $= \frac{1}{2} = 0.5000$ . A $20 \times$ improvement in MRR contribution. Takeaway: reranking cannot fix recall if the doc is missing from the 100 — but given it's present, it dramatically improves precision at small k, which is what the LLM actually consumes.

Level 4 — Synthesis

Exercise 4.1 (L4) — Design the cost budget

Your corpus has $1 0^{6}$ chunks. A bi-encoder ANN query costs 2 ms; BM25 costs 1 ms; a cross-encoder forward pass costs 20 ms per (query, doc) pair. Compare two designs for a single query:

Design X: cross-encode the entire corpus, take top-5.
Design Y: hybrid retrieve top-100, cross-encode those 100, take top-5.

Compute total latency for each. State why Y is the standard.

Recall Solution

Design X: cross-encoder on all $1 0^{6}$ docs $= 1 0^{6} \times 20 ms = 2 \times 1 0^{7} ms = 20, 000$ seconds $\approx 5.56$ hours per query. Infeasible. Design Y: dense ANN 2 ms + BM25 1 ms + cross-encode 100 docs $= 100 \times 20 = 2000$ ms. Total $= 2003$ ms $\approx 2$ seconds. Speedup: $\frac{2 \times 1 0 ^{7}}{2003} \approx 9985 \times$ faster. Why Y is standard: the cross-encoder is $O (candidates)$ and cannot be precomputed (query and doc must be encoded jointly). So you spend the expensive model only on a small pre-filtered set. Retrieve broadly and cheaply (bi-encoder + BM25 can be indexed offline), then rerank narrowly and expensively. This is the "cast a wide net, keep the best fish" architecture.

Exercise 4.2 (L4) — Choosing top- $k$ into the LLM

An engineer proposes feeding all 100 hybrid candidates directly to a long-context LLM (skip reranking) to "be safe." Argue against this using two independent failure axes, and propose the corrected design.

Recall Solution

Axis 1 — Lost in the middle. LLMs attend most strongly to the start and end of their context; a relevant chunk buried at position ~50 of 100 is frequently ignored. More context does not monotonically help. (See Lost in the Middle - LLM context limits.) Axis 2 — Noise and cost. 95 of the 100 chunks are irrelevant. They (i) inflate token cost and latency, and (ii) actively increase hallucination by giving the model plausible-but-wrong material to latch onto. Corrected design: rerank the 100 with a cross-encoder and feed only the top-5 high-precision chunks. Fewer, better-ordered documents → the answer sits where the LLM actually reads, cost drops, and hallucination falls. Precision at small $k$ beats raw volume.

Level 5 — Mastery

Exercise 5.1 (L5) — Full pipeline trace with numbers

A query hits both retrievers. Five candidate docs land with these ranks ( $k = 60$ for RRF):

Doc	BM25 rank	Dense rank
P	1	5
Q	2	1
R	5	2
S	3	—
T	—	3

(a) Compute RRF for all five and give the fused order. (b) The cross-encoder then outputs relevance scores: P $= 0.20$ , Q $= 0.95$ , R $= 0.88$ , S $= 0.10$ , T $= 0.30$ . Give the final top-3 sent to the LLM. (c) Explain in one sentence why the fused order and the final order differ, tying it to bi-encoder vs cross-encoder.

Recall Solution

(a) RRF (absent rank ⇒ term dropped, per the convention up top):

$P = \frac{1}{61} + \frac{1}{65} = 0.016393 + 0.015385 = 0.031778$
$Q = \frac{1}{62} + \frac{1}{61} = 0.016129 + 0.016393 = 0.032522$
$R = \frac{1}{65} + \frac{1}{62} = 0.015385 + 0.016129 = 0.031514$
$S = \frac{1}{63} = 0.015873$
$T = \frac{1}{63} = 0.015873$ Fused order: $Q > P > R > (S = T)$ . (S and T tie; break by any stable rule.) (b) Cross-encoder final: sort by relevance score, largest first → Q (0.95), R (0.88), T (0.30), P (0.20), S (0.10). Final top-3 sent to the LLM: Q, R, T — in that order. (c) Why they differ: RRF only knows positions from two coarse bi-encoder/BM25 signals, so P (strong in both lists) ranked 2nd — but the cross-encoder, reading query and document jointly, judges R and T as actually answering the query while P merely overlaps on surface terms, so R and T leapfrog P and P drops out of the top-3.

Exercise 5.2 (L5) — Diagnose a broken pipeline

A team reports: "Our RAG answers are correct only 40% of the time. We already use a cross-encoder reranker on the top-10 from pure dense retrieval." You measure Recall@10 = 0.55 and, on the queries where the gold doc is in the top-10, answer accuracy = 0.90. Diagnose the bottleneck and prescribe fixes in priority order.

Recall Solution

Diagnosis: the reranker is not the problem — when the gold doc is present, accuracy is 0.90. The ceiling is recall: Recall@10 = 0.55 means 45% of the time the answer isn't even in the candidate set, so no reranker can help. Sanity check: overall $\approx 0.55 \times 0.90 \approx 0.495$ , consistent with the observed ~40–50%. Fixes, in priority order:

Add BM25 → hybrid retrieval. Pure dense misses exact terms/codes; hybrid raises recall (the real bottleneck). Highest leverage.
Widen the candidate pool (top-10 → top-100) before reranking, so more gold docs enter the set the cross-encoder can rescue. The cross-encoder cost is only $O (candidates)$ , so 100 is cheap.
Only then tune the reranker / chunking. Improving a reranker that already runs at 0.90 conditional accuracy is the smallest remaining lever. Principle: always fix the first stage that loses signal. Reranking multiplies precision but is bounded above by retrieval recall — accuracy ≤ Recall@k × rerank-quality.