BM25 › The BM25 Formula

The full BM25 formula looks intimidating at first glance, but every piece exists for a reason. Rather than presenting it all at once, let's build it up from the three core problems any good retrieval function must solve:

1. Which terms matter? Not all words are equally informative. "The" appears everywhere; "quantum" is rare and specific.
2. How much does repetition help? If a document mentions your query term once, that's good. But is mentioning it 100 times really 100 times better?
3. How do we handle document length? A 10,000-word document naturally contains more vocabulary than a 100-word document. Should we penalize it for that?

BM25 addresses each of these problems with a specific component. Let's examine them one by one, then see how they combine into the complete formula.

Consider searching for "the cat sat on the mat." The word "the" appears in virtually every English document. Finding it tells you almost nothing. But "mat"? That's much more specific.

The Inverse Document Frequency (IDF) quantifies this intuition. A term that appears in many documents gets a low IDF; a rare term gets a high IDF. BM25 uses a specific IDF formulation derived from its probabilistic foundations:

$$\text{IDF}(t) = \log \frac{N - n(t) + 0.5}{n(t) + 0.5}$$

where:

• $N$: total number of documents in the collection
• $n(t)$: number of documents containing term $t$
• The $+0.5$ terms provide smoothing to avoid division by zero and extreme values

This formulation differs from the standard $\log(N/n(t))$ IDF you might have seen in TF-IDF. The $N - n(t)$ in the numerator comes directly from the probabilistic derivation, representing the number of documents that don't contain the term. Intuitively, the formula computes a log-odds ratio: the numerator approximates the probability that a relevant document doesn't contain term $t$, while the denominator approximates the probability that a non-relevant document does contain it.

For very common terms appearing in more than half the documents, this IDF becomes negative. The formula effectively penalizes ubiquitous terms rather than just ignoring them. If a term appears in 80% of documents, matching on it might hurt your score slightly, pushing you to focus on more discriminative terms. Standard TF-IDF simply assigns a low positive weight to common terms; BM25's probabilistic derivation says such terms should actively count against a match.

Let's visualize how IDF varies with document frequency:

The plot reveals an important difference: standard IDF is always positive, merely approaching zero for common terms. BM25's IDF crosses zero at exactly 50% document frequency and becomes increasingly negative beyond that. This means stopwords like "the" or "a" that appear in nearly every document will have strongly negative IDF, effectively penalizing documents that match only on these terms. In practice, this is why BM25 implementations often include a floor at zero or simply filter out negative-IDF terms before scoring.

If a document mentions "machine learning" once, that's evidence of relevance. What about ten times? A hundred times?

Raw term frequency treats each occurrence equally: ten mentions = ten times the score. But this creates problems. A document that repeats a term obsessively (keyword stuffing) would dominate results. More fundamentally, there's a diminishing returns effect: the first mention tells you the document is about the topic; additional mentions provide less and less new information. The gap in relevance between a document that mentions a term once and a document that mentions it twice is much larger than the gap between 20 and 21 mentions.

BM25 captures this with a saturation function:

$$\frac{f(t, D) \cdot (k_1 + 1)}{f(t, D) + k_1}$$

where:

• $f(t, D)$: frequency of term $t$ in document $D$
• $k_1$: saturation parameter controlling how quickly the function approaches its asymptote

The full formula includes length normalization in the denominator, which we'll add shortly.

To understand why this formula creates saturation, consider the mathematical behavior. When $f(t, D) = 0$ (term doesn't appear), the formula yields 0. When $f(t, D) = 1$ (term appears once), we get $(1 \cdot (k_1 + 1))/(1 + k_1) = 1$. As $f(t, D)$ grows very large, both the numerator and denominator grow at the same rate, so the ratio approaches $(k_1 + 1)$, an asymptote that cannot be exceeded no matter how many times the term appears.

You can verify this limit directly: as $f \to \infty$,

$$\frac{f(k_1 + 1)}{f + k_1} \to \frac{f(k_1 + 1)}{f} = k_1 + 1$$

So the maximum possible contribution of any single query term, no matter how often it appears, is bounded by $k_1 + 1$ times the IDF weight. This cap makes BM25 resistant to keyword stuffing in a way that TF-IDF is not.

The intuition is this: the first occurrence of a term is strong evidence of relevance. Each additional occurrence provides weaker and weaker evidence, until eventually more occurrences barely matter at all.

The parameter $k_1$ controls how quickly you approach this ceiling:

• $k_1 = 0$: Instant saturation. Any non-zero term frequency gives the same score (like the Binary Independence Model)
• $k_1 \to \infty$: No saturation. Score is linear in term frequency (like raw TF-IDF)
• $k_1 \approx 1.2$ to $2.0$: The empirically validated sweet spot for most collections

Let's visualize this saturation effect:

The visualization reveals the saturation behavior clearly. With $k_1 = 0.5$, the curve flattens quickly: by term frequency 5, you've captured most of the possible score. With $k_1 = 5.0$, the curve is nearly linear over this range, meaning repetition continues to help. The default value of $k_1 = 1.2$ provides a principled middle ground: the first few occurrences matter a lot, but the score doesn't keep climbing indefinitely.

Here's a subtle but important issue. Imagine two documents about machine learning:

• Document A: A focused 200-word abstract that mentions "neural network" twice
• Document B: An extensive 10,000-word survey that mentions "neural network" twenty times

Which is more relevant to a query about neural networks? Raw term frequency would strongly favor Document B. But that's not necessarily right. Document B mentions the term more often simply because it's longer. The density of the term, its frequency relative to document length, might be a better signal.

But even this isn't the full story. Sometimes a long document has more relevant content: a detailed guide to neural networks should rank above a tweet that mentions the phrase once. The right approach is somewhere between ignoring length entirely and fully normalizing for it. BM25 lets you tune this tradeoff explicitly.

BM25 addresses this through length normalization, which adjusts term frequency based on how a document's length compares to the collection average:

$$1 - b + b \cdot \frac{|D|}{\text{avgdl}}$$

where:

• $b$: length normalization parameter (typically between 0 and 1)
• $|D|$: length of document $D$ (number of terms)
• $\text{avgdl}$: average document length across the collection

This expression appears in the denominator of the BM25 formula, multiplied by $k_1$. Let's trace through what happens for different document lengths:

• Average-length document ($|D| = \text{avgdl}$): The ratio $|D|/\text{avgdl} = 1$, so the expression becomes $1 - b + b \cdot 1 = 1$. No adjustment.
• Longer document ($|D| > \text{avgdl}$): The ratio exceeds 1, so the expression is greater than 1. This increases the denominator, reducing the score.
• Shorter document ($|D| < \text{avgdl}$): The ratio is less than 1, so the expression is less than 1. This decreases the denominator, boosting the score.

The parameter $b$ controls how aggressively we normalize:

• $b = 0$: No length normalization. The expression always equals 1, and document length is ignored entirely.
• $b = 1$: Full length normalization. A document twice the average length has its term frequencies effectively halved.
• $b \approx 0.75$: The typical default. This provides moderate normalization that accounts for length without removing its effect.

The intuition behind $b = 0.75$ is that document length is partially informative. Some of the extra length in a long document reflects relevant content; some of it is just verbosity. The 0.75 setting is calibrated to discount verbosity while retaining some of the signal from long, content-rich documents.

Let's see how length normalization affects scoring:

The visualization confirms our intuition. When $b = 0$, document length doesn't matter at all: all curves are flat. With $b = 1$, a document that's three times average length gets significantly penalized. The default $b = 0.75$ provides a reasonable middle ground, acknowledging that longer documents might naturally contain more occurrences without completely ignoring the length difference.

Now we can assemble the complete BM25 formula. For each query term, we multiply three components:

1. IDF: How informative is this term?
2. Saturated TF: How often does it appear (with diminishing returns)?
3. Length adjustment: Normalized by document length

The final formula sums these contributions across all query terms:

$$\text{BM25}(D, Q) = \sum_{t \in Q} \text{IDF}(t) \cdot \frac{f(t, D) \cdot (k_1 + 1)}{f(t, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}$$

where:

• $D$: the document being scored
• $Q$: the query (set of query terms)
• $t$: a term in the query
• $\text{IDF}(t)$: inverse document frequency of term $t$
• $f(t, D)$: frequency of term $t$ in document $D$
• $k_1$: saturation parameter (typically 1.2 to 2.0)
• $b$: length normalization parameter (typically 0.75)
• $|D|$: length of document $D$ (number of terms)
• $\text{avgdl}$: average document length in the collection

Each component addresses one of our original problems. The IDF weights rare terms more heavily. The saturation function ensures diminishing returns from repetition. The length normalization factor in the denominator adjusts for document size. Together, they create a scoring function that has worked well across decades of information retrieval research.

This formula does not include query term frequency. The original BM25 paper includes a query-side term frequency component as well (sometimes called BM25 with query term weighting), but in practice most implementations drop it. For typical short web queries, query terms appear at most once, making the query TF component degenerate to a constant. For longer queries, you could re-add it, but the gain is usually marginal.

The parameters $k_1$ and $b$ interact in interesting ways. Let's visualize how different combinations affect the score for a document with a fixed term frequency: