Lesson 15 - Hybrid Search, RRF, and Reranking

Code: agentic-course/agentic/retrieval.py Tests: agentic-course/tests/test_retrieval.py Run it: python3 -m unittest tests.test_retrieval -v Concept: Hybrid Search and Reranking covers the theory and the interview framing, without code.

What you will build

• BM25 from scratch — term frequency saturation, length normalization, and the idf that makes rare terms count.
• reciprocal_rank_fusion, which combines ranked lists by position rather than score, plus a demonstration that this is the only sane way to do it.
• HybridRetriever, which puts dense, lexical, fusion, and an optional reranker behind one search call so the agent sees one tool.
• recall_at_k, precision_at_k, and mrr — and the argument for scoring your retriever separately from your answer.

The idea

Dense retrieval has a specific, enumerable set of queries it is bad at, and they are not exotic.

• Exact identifiers. E-4471, order 8802, SKU BRK-2291-XL. An embedding places these near other identifier-shaped strings, because that is what it learned about them. Which one you asked for is barely encoded.
• Product and version strings. v2.14.0-rc3 and v2.14.0 are near-identical in embedding space and completely different in meaning. Same for verbatim error strings — the user pasted connection reset by peer out of a log and wants that line, not a discussion of network reliability.
• Rare proper nouns. An unusual surname or an internal codename appears too rarely in training data to have a well-placed vector.
• Negation. “Refunds are not permitted after 30 days” sits right beside “refunds are permitted within 30 days”, for the reasons in lesson 13.

Lexical search nails every one of these, because it matches the literal token — and it fails on exactly what dense search handles, vocabulary mismatch, where the user says “money back” and the document says “refund”. That asymmetry is the entire justification for hybrid retrieval. Two retrievers with uncorrelated failure modes cover each other; two that fail on the same queries are redundancy with a bigger bill. Before combining anything, answer this: do these two disagree, and on which queries?

BM25, in full

def _idf(self, term: str) -> float:
    n = len(self.chunks)
    df = self._df.get(term, 0)
    # +1 keeps the idf positive for terms present in every document.
    return math.log(1 + (n - df + 0.5) / (df + 0.5))

# ... and the scoring loop inside BM25.search:
for term in q:
    f = tf.get(term, 0)
    if not f:
        continue
    denom = f + self.k1 * (1 - self.b + self.b * length / (self._avg_len or 1))
    score += self._idf(term) * (f * (self.k1 + 1)) / denom

Three ideas, each fixing a flaw in naive term counting. idf weights rarity — a term in every document discriminates nothing, and the 1 + inside the logarithm keeps the result positive even then, so a matching document can never score below a non-matching one. k1 saturates term frequency — a document mentioning “refund” forty times is not forty times more relevant, so the f · (k1 + 1) / (f + k1 · ...) shape rises steeply for the first few occurrences then flattens; k1 = 1.5 means roughly “the third mention barely helps”. b normalizes for length — long documents contain more of everything and would otherwise win every query, so b = 0.75 divides out most of the length advantage, b = 0 ignores length entirely and b = 1 normalizes fully.

The query dense search blurs

from agentic.retrieval import BM25, Chunk

CORPUS = [
    Chunk(id="refund", text="Refunds are accepted within 30 days of delivery.",
          source="policy", section="Refunds"),
    Chunk(id="ship", text="Standard shipping takes three to five working days.",
          source="policy", section="Shipping"),
    Chunk(id="err", text="Error code E-4471 means the payment gateway timed out.",
          source="runbook", section="Errors"),
    Chunk(id="hr", text="Salary bands are reviewed each April by the people team.",
          source="hr", section="Comp", permissions=frozenset({"hr"})),
]

bm = BM25().add(*CORPUS)
for h in bm.search("E-4471", k=3, permitted=frozenset({"hr"})):
    print(h.rank, h.chunk.id, round(h.score, 4))
# 1 err 2.3133

That is test_exact_identifier_is_found, and the 2.3133 is worth tracing. tokenize lowercases and splits on anything outside [a-z0-9], so "E-4471" becomes ["e", "4471"] — test_lowercases_and_splits_on_punctuation pins that. Both tokens appear in exactly one of four chunks, so each gets idf = log(1 + 3.5/1.5) = 1.2040. The err chunk is 12 tokens against an average of 11, so denom = 1 + 1.5·(0.25 + 0.75·12/11) = 2.6023 and each term contributes 1.2040 · 2.5 / 2.6023 = 1.1567. Two terms, 2.3133. Notice what earned it: 4471 is simply a rare token. BM25 never needed to know it was an error code — rarity did the work, which is why lexical search keeps winning on identifiers no matter how good embeddings get.

Reciprocal rank fusion

Now you have two ranked lists and need one. The tempting move is to add or average the scores. Do not — the whole algorithm is one line, and it uses neither:

scores[h.chunk.id] += 1.0 / (smoothing + h.rank)

The reason is that a BM25 score and a cosine score are not on a comparable scale. Cosine is bounded in [-1, 1]. BM25 is unbounded and grows with query length, corpus size, and term rarity — the 2.3133 above would be far larger on a real corpus. Add them and BM25 wins every time; average them and it still wins, just quieter. Min-max normalizing each list looks like a fix and is not: it makes the top hit of three uninformative results look as confident as the top hit of three excellent ones. Rank position is comparable by construction — “this retriever’s best result” means the same thing from either side.

test_rrf_combines_by_rank_not_score makes the point with deliberately absurd scales:

from agentic.retrieval import Chunk, Hit, reciprocal_rank_fusion

a, b = Chunk(id="a", text="alpha"), Chunk(id="b", text="beta")
dense = [Hit(chunk=b, score=0.9, rank=1)]
lexical = [Hit(chunk=a, score=900.0, rank=1)]

fused = reciprocal_rank_fusion(dense, lexical, k=2)
print([(h.chunk.id, round(h.score, 6)) for h in fused])
# [('a', 0.016393), ('b', 0.016393)]

900.0 versus 0.9 — a thousandfold difference — and both fused scores are identical at 1/61. Each was its own retriever’s rank-1 hit, so each gets rank-1 weight. The large number bought nothing.

What smoothing does. The default 60 flattens the curve: rank 1 scores 1/61 = 0.01639, rank 2 1/62 = 0.01613, rank 3 1/63 = 0.01587. Adjacent gaps are tiny, which means agreement across retrievers beats confidence within one — something at rank 1 in one list and absent from the other gets 0.01639, while something at rank 2 in both gets 2/62 = 0.03226 and wins. That is test_agreement_across_retrievers_wins. Lower the constant and top positions dominate; raise it and consensus dominates further.

The two-stage funnel

Fusion improves recall. It does not necessarily put the best document first, and first is where it matters — models attend unevenly across a long context, and a correct document at position nine frequently loses to a plausible one at position one. So you add a second stage.

flowchart LR
    Q[User query]
    D[Dense over whole corpus]
    L[BM25 over whole corpus]
    F[Reciprocal rank fusion]
    C[Shortlist of 20 candidates]
    R[Reranker scores each pair]
    K[Top 5 into the context]
    Q --> D
    Q --> L
    D --> F
    L --> F
    F --> C
    C --> R
    R --> K
    classDef edge fill:#6cf,stroke:#333,color:#000
    classDef service fill:#10b981,stroke:#065f46,color:#fff
    classDef async fill:#b4f,stroke:#333,color:#000
    classDef data fill:#fbbf24,stroke:#92400e,color:#000
    class Q edge
    class D,L,F service
    class R async
    class C,K data

Blue is the incoming query, green is cheap first-stage retrieval over the whole corpus, purple is expensive second-stage scoring, yellow is a result set. Stage one optimises recall and must be cheap, because it touches everything; stage two optimises precision and is allowed to be expensive, because it only ever sees a few dozen candidates. That division is the entire design, and HybridRetriever.search implements it directly:

def search(self, query, k=5, candidates=20, permitted=None, rerank=None):
    d = self.dense.search(query, k=candidates, permitted=permitted)
    l = self.lexical.search(query, k=candidates, permitted=permitted)
    fused = reciprocal_rank_fusion(d, l, k=candidates)
    if rerank:
        fused = rerank(query, fused)
    for i, h in enumerate(fused[:k]):
        h.rank = i + 1
    return fused[:k]

candidates=20 is the funnel width and k=5 is what reaches the model. Both legs receive permitted, so the pre-filtering guarantee from lesson 14 holds on both — test_permissions_hold_through_the_hybrid_path proves it survives fusion.

Bi-encoder versus cross-encoder

This distinction is why stage two exists, and it is mechanical rather than a matter of model quality. A bi-encoder embeds the query and the document independently — two forward passes, two vectors, one cosine. Because the document’s vector does not depend on the query, you compute it at ingest time and store it, which is the only reason vector search is fast. The cost is that the document was encoded without ever seeing the query, so one fixed-size vector must summarise it for every possible question.

A cross-encoder takes the query and document concatenated as one input and reads them jointly, attention running across both, so it can notice that this specific phrase answers that specific clause. It emits a relevance score directly — no vectors, no index. And because the score depends on the pair, nothing can be precomputed: every query-document pair is a fresh forward pass. That is simultaneously why it is far more accurate and why it can only ever run over a shortlist. Twenty pairs is fine; ten million is not a system. Reranking is the trade that asymmetry creates.

The reranker in this repo, honestly

def keyword_overlap_reranker(query: str, hits: list[Hit]) -> list[Hit]:
    q = set(tokenize(query))
    if not q:
        return hits
    out = []
    for h in hits:
        terms = set(tokenize(h.chunk.text))
        coverage = len(q & terms) / len(q)
        out.append(Hit(chunk=h.chunk, score=coverage, retriever="reranked"))
    out.sort(key=lambda h: (-h.score, h.chunk.id))
    ...

This has a cross-encoder’s shape — (query, shortlist) -> reordered shortlist, a drop-in rerank= callable — and none of its behaviour. It counts what fraction of query terms appear in the chunk: no model, no joint attention, no semantics. Swapping in a real cross-encoder changes this one function and nothing else, which is the point of the seam. It does reorder correctly on the obvious case — test_reranker_reorders_the_shortlist queries "30 days delivery refunds", where refund contains all four query terms for coverage 1.0 and ship contains only days for 0.25, so refund takes rank 1 and retriever becomes "reranked".

Measuring the retriever, not the answer

from agentic.retrieval import Hit, mrr, precision_at_k, recall_at_k

hits = [Hit(chunk=CORPUS[1], score=0.9, rank=1),   # ship   - not relevant
        Hit(chunk=CORPUS[0], score=0.8, rank=2)]   # refund - relevant

print(recall_at_k(hits, {"refund"}), recall_at_k(hits, {"refund", "err"}),
      recall_at_k(hits, {"refund"}, k=1))      # 1.0 0.5 0.0
print(precision_at_k(hits, {"refund"}), mrr(hits, {"refund"}))   # 0.5 0.5

Recall at k is the share of relevant documents retrieved — did the answer reach the context at all. Precision at k is the share of what you returned that was relevant — how much noise you are paying for and asking the model to ignore. MRR is the reciprocal position of the first relevant hit, which tells you whether the answer is at the top or buried; here it is 0.5 because the relevant chunk sits second. Note the k=1 rows: the same list scores recall 1.0 at k=2 and 0.0 at k=1, so a retrieval metric quoted without its k is meaningless.

Score these separately from answer quality, always. A RAG system fails in two unrelated places — the retriever did not find the document, or it found it and the model answered badly anyway — and the two have opposite remedies. Low recall with good answers means work on chunking, fusion, and the reranker. Good recall with bad answers means work on the prompt, context assembly, and the abstain path. One aggregate number cannot distinguish them, so teams that track only end-to-end accuracy spend months tuning the wrong half.

Exercise

Query with an exact error code and with a paraphrase, show which retriever wins each, then fuse and confirm both queries still work. Success criterion: BM25 returns nothing at all on the paraphrase, ranks err first on the error code, and the fused list is non-empty for both.

What broke when I wrote this

The paraphrase row above is not what it appears to be. HashingEmbedder is a bag-of-words hash with no semantics, so it cannot know that “money back” relates to “refund” — and it does not. What actually happened is a hash collision: at dim=64 the tokens period and refunds both land in slot 4, and that one accidental overlap produces the 0.2887. Re-run with HashingEmbedder(dim=4096) and the dense leg returns an empty list too.

So this repo’s dense leg cannot demonstrate the paraphrase win that motivates hybrid retrieval, and the one place it appears to is riding an artifact. What the code does demonstrate faithfully is everything model-independent — pre-filtering, the fusion arithmetic, the funnel, the metrics — and those transfer to a real embedder unchanged. The semantic recall does not transfer, because there is none to transfer.

Checkpoint

Why does combining BM25 and dense retrieval help?

Because they fail on different queries. Dense blurs exact identifiers, version strings, verbatim error text, rare proper nouns, and negation; lexical fails on vocabulary mismatch. Uncorrelated failures cover each other. Two retrievers that fail on the same queries add cost and nothing else.

Why fuse by rank instead of score?

BM25 and cosine are not on a comparable scale — cosine is bounded, BM25 is unbounded and grows with query length and corpus size. Adding or averaging hands the result to whichever retriever emits larger numbers. test_rrf_combines_by_rank_not_score uses 900.0 against 0.9 and both rank-1 hits fuse to exactly 1/61.

What does the smoothing constant control?

How flat the rank-position curve is. At 60, rank 1 is 0.01639 and rank 2 is 0.01613 — adjacent positions are nearly equal, so a document ranked 2 by both retrievers beats one ranked 1 by only one. It trades single-retriever confidence for cross-retriever agreement.

Why can a cross-encoder only run on a shortlist?

It reads the query and document jointly in one forward pass, so its score depends on the pair and nothing can be precomputed at ingest time. Every candidate costs a full inference. Twenty is affordable; a whole corpus is not. A bi-encoder encodes each side independently, which is what makes indexing possible and also what limits its accuracy.

Why score the retriever separately from the answer?

Because a RAG system fails in two distinct places with opposite fixes. Low recall points at chunking, fusion, and reranking; good recall with bad answers points at the prompt, context assembly, and the abstain path. An end-to-end number cannot tell you which half is broken.

Theory and interview framing: Become an AI Engineer