Hybrid Search: BM25 and Dense Retrieval Combined › BM25: The Classical Baseline

Before dense retrieval existed, keyword-based ranking functions dominated information retrieval. The most durable of these is BM25 (Best Match 25), which dates to the 1990s and remains competitive against many modern systems on keyword-heavy benchmarks. Its staying power is not an accident of inertia: BM25 embodies a set of principled statistical insights about how term occurrence patterns relate to relevance, and those insights remain valid even in the age of large language models.

BM25 is a refinement of TF-IDF. Recall from earlier chapters that TF-IDF scores a term in a document by multiplying how often the term appears in the document (term frequency, or TF) by how rare the term is across all documents (inverse document frequency, or IDF). BM25 keeps this core intuition but fixes two structural problems with raw TF-IDF. The fixes are not cosmetic adjustments: they address basic failure modes that make raw TF-IDF unreliable in practice. Understanding these failure modes is the fastest path to understanding why BM25 is designed the way it is.

Think of BM25 as a more careful accountant than TF-IDF. TF-IDF is like an accountant who counts every dollar of evidence and adds it all up, even if the same dollar appears a hundred times. BM25 is like an accountant who correctly recognizes that after the tenth dollar of the same type, each additional dollar is worth only a fraction of the first. It also adjusts for the fact that longer reports naturally contain more dollars, and corrects for that structural bias. The result is a much fairer assessment of which documents truly contain the most relevant evidence.

The first problem is that raw TF grows without bound. If a document mentions the word "python" 100 times rather than 10 times, raw TF scores it 10 times higher. But in practice the relevance gain from the 50th mention of "python" is negligible compared to the gain from the first. BM25 saturates TF so that each additional occurrence contributes less than the previous one.

To make this concrete, imagine reading a book review. If the review mentions "fascinating" once, that tells you something. If it mentions "fascinating" twenty times, that tells you roughly the same thing, just more emphatically. The hundredth mention of "fascinating" adds no new information. BM25 captures this diminishing return mathematically: the scoring function curves upward steeply at first, then flattens to a ceiling as occurrences accumulate. The ceiling is determined by the hyperparameter $k_1$, which you will see shortly.

The second problem is that longer documents naturally accumulate more term occurrences and therefore score higher even when they are no more relevant. A textbook chapter is longer than a blog post and will contain any given term more often, but that does not make the textbook chapter more relevant to a two-word query. BM25 applies a document length normalization that penalizes documents longer than average, keeping the playing field level. The strength of this penalty is controlled by the hyperparameter $b$.

These two fixes, saturation and length normalization, are not independent adjustments bolted onto TF-IDF. They interact through a single elegant fraction at the heart of the BM25 formula. Understanding that fraction is the key to understanding the entire formula.

BM25 computes a relevance score for a document $d$ given a query $Q$ by summing term-level contributions. Each term's contribution multiplies a document-frequency weight (IDF) by a saturated term-frequency weight. For a query $Q$ with terms $q_1, q_2, \ldots, q_n$ and a document $d$, BM25 scores the document as:

$$\text{BM25}(d, Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, d) \cdot (k_1 + 1)}{f(q_i, d) + k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)}$$

where:

• $q_1, q_2, \ldots, q_n$: the individual terms in query $Q$
• $f(q_i, d)$: the raw frequency of term $q_i$ in document $d$ (how many times it appears)
• $|d|$: the length of document $d$ in tokens
• $\text{avgdl}$: the average document length across the entire corpus
• $k_1$: the term frequency saturation parameter, typically set to 1.2 or 1.5; it controls how quickly additional occurrences of a term stop adding to the score
• $b$: the length normalization parameter, typically set to 0.75; it controls how strongly longer documents are penalized relative to the average

It is worth pausing to appreciate the structure of this formula before looking at any of its parts in isolation. The outer sum iterates over every query term. For each term, you compute two independent quantities: how rare the term is across the entire corpus (the IDF factor on the left), and how heavily the term appears in this specific document adjusted for document length (the fraction on the right). These two numbers are multiplied together, and you accumulate the result across all query terms. The final BM25 score for a document is therefore a weighted sum of term-level evidence, where rarer terms contribute more heavily.

This structure shows a clear intuitive principle. A query like "transformer" combined with "myocardial" should give high weight to the term "myocardial" (rare) and lower weight to "transformer" (common in this hypothetical corpus). BM25 accomplishes this weighting automatically through IDF, without any manual synonym mapping or domain knowledge.

The IDF component measures how rare a term is across the corpus. Rare terms that appear in few documents receive high IDF weights, while common terms like "the" receive near-zero weights. The IDF term is computed as:

$$\text{IDF}(q_i) = \log\left(\frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} + 1\right)$$

where:

• $N$: the total number of documents in the corpus
• $n(q_i)$: the number of documents in the corpus that contain term $q_i$
• $0.5$: a smoothing constant added to both numerator and denominator to avoid division by zero and to prevent IDF from going negative for terms appearing in every document
• The $+1$ inside the logarithm ensures the IDF is always non-negative, even when a term appears in all documents

To build intuition for this formula, consider the two extreme cases. When $n(q_i)$ is very small relative to $N$, meaning the term appears in almost no documents, the fraction $\frac{N - n(q_i) + 0.5}{n(q_i) + 0.5}$ becomes large, and the logarithm returns a large positive number. This makes sense: a term that appears in only 3 out of 1 million documents is extraordinarily informative when it does appear. When $n(q_i) \approx N$, meaning the term appears in nearly every document, the numerator approaches 0.5 and the denominator approaches $N + 0.5$, making the fraction nearly zero and the IDF close to $\log(1) = 0$. A term that appears in every document tells you nothing about which documents are more relevant.

The fraction within the BM25 sum handles two effects simultaneously: TF saturation and length normalization. These two effects are coupled through a single expression, and understanding their interaction reveals why BM25 is so reliable across diverse corpora. Focusing on this fraction:

$$\frac{f(q_i, d) \cdot (k_1 + 1)}{f(q_i, d) + k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)}$$

This fraction looks intimidating at first glance, but it has a clean structure once you name its moving parts. The numerator scales the raw term frequency by $(k_1 + 1)$, which is a constant for any given setting of $k_1$. The denominator adds the raw term frequency to a document-length-dependent constant. That constant is where the two effects live.

Define the denominator's length-dependent constant as:

$$K = k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)$$

where:

• $k_1$ and $b$ are the BM25 hyperparameters defined above
• $|d| / \text{avgdl}$: the ratio of document length to average document length; values above 1.0 mean the document is longer than average

Notice what $K$ encodes. The term $b \cdot (|d| / \text{avgdl})$ grows as the document grows relative to the average. When $b = 0.75$ and a document is twice the average length, the ratio is 2.0, and this term contributes $0.75 \times 2.0 = 1.5$ to the expression inside the outer parentheses. When a document is exactly average length, the ratio is 1.0, and the expression inside the parentheses equals $(1 - b + b \times 1) = 1$ exactly. So $K$ equals $k_1$ for an average-length document and grows proportionally for longer documents. This is the length normalization embedded in $K$.

With this substitution, the saturation fraction becomes:

$$\frac{f \cdot (k_1 + 1)}{f + K}$$

This is now recognizable as a hyperbolic function of $f$ (the term frequency). To understand the saturation behavior, consider what happens as term frequency grows:

• As $f \to \infty$, the fraction approaches $k_1 + 1$, not infinity. This is the saturation ceiling: no matter how many times a term appears, the contribution is bounded above by $k_1 + 1$.
• When $f = K$, the fraction equals $(k_1 + 1) / 2$, exactly half the maximum. This means $K$ controls the "half-saturation point": the term frequency at which the score reaches half its ceiling.
• $K$ itself depends on document length via $|d| / \text{avgdl}$. Longer documents have a larger $K$, meaning they need more term occurrences to reach the same score as a shorter document. This is the length normalization effect.

The interplay between saturation and length normalization is elegant: a document that is twice as long as average must also have roughly twice the term frequency to reach the same BM25 score as the shorter document. This keeps the scoring fair across documents of different lengths.

The key insight is that BM25 treats the saturation ceiling and the half-saturation point as linked quantities: both are controlled by the same $K$ expression. When you tune $k_1$ and $b$, you are not adjusting two independent knobs. You are adjusting a single parameterized family of scoring functions where the saturation speed and the length sensitivity move together in a coordinated way. This coupling is what makes BM25 well-behaved across diverse corpora with different length distributions.

The coupling between saturation and length normalization through $K$ makes BM25 a unified formula rather than two separate adjustments patched together. When you increase $b$, you make $K$ more sensitive to document length, which simultaneously raises the half-saturation point for longer documents. When you increase $k_1$, you raise both the saturation ceiling and the scale of $K$, effectively making the saturation happen more slowly everywhere. The two hyperparameters interact in a predictable way.

The logarithmic x-axis reveals the full range of IDF behavior. A term appearing in 10 out of 10,000 documents (0.1% of the corpus) receives an IDF of roughly 6.9, while a term appearing in 9,000 documents (90% of the corpus) receives an IDF near zero. This nonlinear weighting means that going from "appears in 10 documents" to "appears in 100 documents" causes a significant IDF drop, while going from "appears in 5,000 to 9,000 documents" causes almost no change because both are already near zero. BM25 is most sensitive to term rarity at the rare end of the spectrum.

To make the BM25 formula completely concrete, let us trace through all computations step by step on a tiny corpus. This kind of worked example is invaluable because the formula combines several interacting quantities, and watching them interact numerically builds intuition that the formula alone cannot convey.

Consider a tiny corpus with three documents:

• $d_1$: "the cat sat on the mat" (6 tokens)
• $d_2$: "the cat sat on the cat mat mat cat" (9 tokens)
• $d_3$: "the dog chased the cat across the yard" (8 tokens)

Average document length: $(6 + 9 + 8) / 3 = 7.67$ tokens.

Query: "cat mat"

Step 1: Compute IDF for each query term.

For term "cat": appears in all 3 documents, so $n(\text{cat}) = 3$, $N = 3$.

$$\text{IDF}(\text{cat}) = \log\left(\frac{3 - 3 + 0.5}{3 + 0.5} + 1\right) = \log\left(\frac{0.5}{3.5} + 1\right) = \log(1.143) \approx 0.134$$

Since "cat" appears in every document, its IDF is very low. This shows that it is not a discriminating term for this query. Every document contains "cat," so knowing a document contains "cat" tells you almost nothing about which document is most relevant. The IDF correctly suppresses its influence.

For term "mat": appears in $d_1$ and $d_2$, so $n(\text{mat}) = 2$.

$$\text{IDF}(\text{mat}) = \log\left(\frac{3 - 2 + 0.5}{2 + 0.5} + 1\right) = \log\left(\frac{1.5}{2.5} + 1\right) = \log(1.6) \approx 0.470$$

"mat" is rarer (absent from $d_3$), so it receives a higher IDF weight. This makes sense: knowing a document contains "mat" is more informative than knowing it contains "cat," because "mat" narrows the field.

Step 2: Compute the length-dependent constant $K$ for $d_2$.

Using $k_1 = 1.2$, $b = 0.75$, $|d_2| = 9$, $\text{avgdl} = 7.67$:

$$K_{d_2} = 1.2 \cdot \left(1 - 0.75 + 0.75 \cdot \frac{9}{7.67}\right) = 1.2 \cdot (0.25 + 0.881) = 1.2 \cdot 1.131 = 1.357$$

The ratio $9 / 7.67 = 1.174$ tells us $d_2$ is about 17% longer than average. The constant $K_{d_2} = 1.357$ is larger than it would be for an average-length document (where $K$ would equal $k_1 \cdot 1.0 = 1.2$). This larger $K$ raises the half-saturation threshold, meaning $d_2$ needs more term occurrences to reach the same score as an average-length document.

Step 3: Compute TF contributions for "cat" in $d_2$ and $d_1$.

TF contribution of "cat" in $d_2$ (frequency = 3):

$$\frac{3 \cdot (1.2 + 1)}{3 + 1.357} = \frac{6.6}{4.357} \approx 1.515$$

For $d_1$: $K_{d_1} = 1.2 \cdot (1 - 0.75 + 0.75 \cdot 6/7.67) = 1.2 \cdot (0.25 + 0.587) = 0.934$.

TF contribution of "cat" in $d_1$ (frequency = 1):

$$\frac{1 \cdot 2.2}{1 + 0.934} = \frac{2.2}{1.934} \approx 1.138$$

Step 4: Assemble the full BM25 scores.

For $d_1$ (cat: f=1, mat: f=1):

$$\text{BM25}(d_1, Q) = \text{IDF}(\text{cat}) \cdot 1.138 + \text{IDF}(\text{mat}) \cdot \frac{1 \cdot 2.2}{1 + 0.934}$$ $$= 0.134 \cdot 1.138 + 0.470 \cdot 1.138 = 0.152 + 0.535 = 0.687$$

For $d_2$ (cat: f=3, mat: f=2), first computing the mat TF contribution:

$$\text{TF\_contrib}(\text{mat}, d_2) = \frac{2 \cdot 2.2}{2 + 1.357} = \frac{4.4}{3.357} \approx 1.311$$ $$\text{BM25}(d_2, Q) = 0.134 \cdot 1.515 + 0.470 \cdot 1.311 = 0.203 + 0.616 = 0.819$$

For $d_3$ (cat: f=1, mat: f=0), $K_{d_3} = 1.2 \cdot (0.25 + 0.75 \cdot 8/7.67) = 1.2 \cdot 1.032 = 1.238$:

$$\text{BM25}(d_3, Q) = 0.134 \cdot \frac{1 \cdot 2.2}{1 + 1.238} + 0.470 \cdot 0 = 0.134 \cdot 0.983 = 0.132$$

The final ranking is $d_2 > d_1 > d_3$, which matches our intuition perfectly. $d_2$ contains "cat" three times and "mat" twice in a document only slightly longer than average. $d_1$ contains both terms once each. $d_3$ contains "cat" but no "mat" at all. The BM25 formula has automatically combined term frequency evidence, rarity evidence, and document length adjustment into a single, principled score.

$d_2$ gets a higher TF score for "cat" despite its longer length, because its term frequency (3) is much higher than $d_1$'s (1). The length penalty embodied in $K$ slows but does not stop the gain from additional occurrences. The "mat" term, being rarer (IDF = 0.470 vs. 0.134 for "cat"), contributes more per occurrence to the final score than "cat" does. This automatic rarity weighting is BM25's key advantage over simple term counting.