Foundations — Reranking and hybrid search

This page builds — from nothing — every symbol, letter and piece of notation that the parent note throws at you. If the parent wrote $\sum$, $\mathbf{q}\cdot \mathbf{d}$, or $\text{avgdl}$ and you blinked, this is where each one is earned.

0. The stage: what are we even counting?

Before any formula, fix the actors. We have:

• A query $Q$ — the question you type. It is made of terms (words): $q_1,q_2,\dots ,q_n$.
• A pile of documents — for us, small chunks of text. We call one of them $D$ (or $d$).
• A corpus — the whole collection of documents. Its total count is $N$.

Look at the figure: the query on the left is broken into terms, and each term is a searchlight that may or may not land on a given document. Relevance is just "how brightly do the searchlights land?"

1. The counting symbols: $\sum$, $f$, $|D|$, $\text{avgdl}$

1.1 $\sum$ — "add up a bunch of things"

The big Greek "S" ($\Sigma$, sigma) means sum. When you see ${\sum }_{i=1}^n(\text{something involving }{q}_i)$ read it as a sentence: "start at $i=1$, work out the something for $q_1$, then for $q_2$, … up to $q_n$, and add all those numbers together." The $i$ is just a counter that walks through the terms.

1.2 $f(q_i,D)$ — term frequency (how often a word appears)

$f(q_i,D)$ reads: "how many times does term $q_i$ appear inside document $D$?" If $D$ says "cat" five times, then $f(\text{"cat"},D)=5$.

• Picture: a highlighter passing over $D$, ticking each hit.
• Why we need it: a word mentioned often is probably central to the document. (With a catch we handle in D2 — diminishing returns.)

1.3 $|D|$ and $\text{avgdl}$ — length and average length

The bars $|D|$ mean the length of $D$ — its word count. It is not absolute value here; it is a "size of" measure.

$\text{avgdl}$ = average document length = the mean word count across the whole corpus.

Why both? A long document racks up word-hits just by being long, not by being more relevant. Comparing $|D|$ to $\text{avgdl}$ tells us "is this document unusually long?" so we can cancel that unfair advantage. That's the fraction $\frac{|D|}{\text{avgdl}}$ inside BM25.

2. Rareness: $N$, $n(q_i)$, $\ln$, and IDF

Some words are everywhere ("the"), some are rare and precious ("photosynthesis"). We need a symbol for rareness.

• $N$ :: total documents in the corpus.
• $n(q_i)$ :: document frequency — how many documents contain term $q_i$ at least once.

If $n(q_i)$ is small (the word lives in few docs), the word is rare and discriminating. The ratio $\frac{N}{n(q_i)}$ is large for rare words, small for common ones.

2.1 Why $\ln$ (the natural logarithm)?

$\ln x$ is the natural logarithm — a function that squashes big numbers. $\ln 1=0$, $\ln 10\approx 2.30$, $\ln 1000\approx 6.91$. Notice: multiplying $x$ by 10 only adds about 2.3 to $\ln x$.

The figure shows $\ln$ flattening: doubling the input barely nudges the output once you're out on the right. That gentleness is exactly why IDF uses it.

3. Vectors: $\mathbf{q}$, $\mathbf{d}$, ${\mathbb{R}}^m$, the dot product, and $\Vert \cdot \Vert$

Keyword matching can't see that "car" and "automobile" mean the same thing. For meaning, we turn text into vectors — lists of numbers — and compare directions.

3.1 What is a vector here?

A bi-encoder (a neural net) reads a piece of text and spits out a fixed list of numbers, say 768 of them. That list is a point/arrow in space.

• $\mathbf{q}$ :: the query's vector (bold = it's a whole list, not one number).
• $\mathbf{d}$ :: a document's vector.
• ${\mathbb{R}}^m$ :: "the space of lists of $m$ real numbers." $m$ is the embedding dimension (e.g. 768). $\mathbb{R}$ is the symbol for real numbers; the exponent $m$ means "$m$ of them."

3.2 The dot product $\mathbf{q}\cdot \mathbf{d}$

The dot means: multiply matching entries, then add them up. $\mathbf{q}\cdot \mathbf{d}=q_1{d}_1+q_2{d}_2+\cdots +q_m{d}_m$ Geometrically, the dot product is large and positive when the two arrows point the same way, zero when they're perpendicular, negative when opposite. It measures alignment.

3.3 The norm $\Vert \mathbf{q}\Vert$ — length of an arrow

The double bars $\Vert \mathbf{q}\Vert$ mean the length (magnitude) of the arrow: $\Vert \mathbf{q}\Vert =\sqrt{q_1^2+q_2^2+\cdots +q_m^2}$ This is just the Pythagorean theorem generalised to $m$ dimensions.

3.4 Putting them together: cosine similarity

The raw dot product mixes two things: direction and how long the arrows are. We only care about direction (meaning), not length. So we divide out the lengths:

4. Ranks and fusion: ${\text{rank}}_r(d)$, $k$, and the RRF sum

After each retriever runs, it produces an ordered list: best document first. The position in that list is a rank.

• ${\text{rank}}_r(d)$ :: the position of document $d$ in retriever $r$'s list. Rank $1$ = best.
• $r$ :: which retriever we mean (BM25, or dense). The RRF sum runs over both.
• $k$ :: a smoothing constant (commonly $60$) — not the same $k$ as top-$k$, and not BM25's $k_1$. Notation collides in this field; watch the subscripts.

The figure plots $\frac{1}{k+\text{rank}}$ against rank: a steep drop near the top, then a long flat tail — which is precisely why the top few positions dominate and deep positions barely matter.

5. The map of prerequisites

Read it top to bottom: symbols on the left become scores, scores become ranked lists, ranked lists fuse, and the fused shortlist gets one expensive final judge before reaching the language model.

6. Where each foundation lives in the vault

• Sparse counting ($f$, IDF, $\ln$) → BM25 and TF-IDF
• Vectors, dot product, cosine → Embeddings and Bi-encoders
• The joint scorer that replaces separate encoding → Cross-encoders and Sentence Transformers
• Where the ranked lists actually get searched fast → Vector Databases and ANN Search
• Why we keep the final list small → Lost in the Middle - LLM context limits
• How we score whether the pipeline worked → Evaluation - Recall@k and MRR
• The whole assembled system → Retrieval-Augmented Generation (RAG)
• This foundation's parent → Reranking and hybrid search (index 4.4.14)

Equipment checklist

Test yourself — cover the right side and answer aloud.