BM25 Term Saturation and Document Length Normalization

A term that appears ten times in a document is not ten times as relevant as a term that appears once. It is more relevant, but the return diminishes quickly, and a scoring function that treats repetitions linearly will happily rank a keyword-stuffed page above a page that answers the question. BM25 is the family of functions that fixed this, and its shape is worth working through because nearly every component of a modern ranking stack inherits its assumptions.

The two quantities BM25 actually tries to estimate

BM25 descends from the binary independence model, which asks a narrow question: what is the probability that a document is relevant given that it contains term t, divided by the probability that it is relevant given that it does not? Under independence assumptions that probability ratio reduces to a weight per term, and the sum of those weights over query terms orders the documents.

The derivation assumes each term is either present or absent. Real text has counts, so the model is extended by replacing the binary presence indicator with a saturation function of the observed count. Two separate corrections are folded into that step.

The first is term frequency saturation. The second is document length: a long document mentions everything more often, so raw counts are not comparable across documents of different sizes. Both corrections live in the same denominator, which is why the parameters interact in ways that make tuning unintuitive.

Why the denominator is built the way it is

The scoring contribution of a query term t in document D is

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

where $f(t,D)$ is the count of t in D, $|D|$ is the document length in tokens, and avgdl is the mean length of the collection. The fraction is the saturating component; the multiplier outside it is the inverse document frequency.

The denominator has two terms. The first is the observed count. The second is a length-scaled constant. When the count is small relative to that constant, the fraction rises roughly linearly with the count. When the count is large, the constant dominates and the fraction approaches $k_1+1$. That ceiling is the entire point: the reward for the tenth occurrence of a term is a small fraction of the reward for the first, and no amount of repetition can push the term past its cap.

With $k_1 = 0$ the function degenerates to a binary indicator multiplied by $k_1+1$, so the model ignores counts entirely and behaves like a pure Boolean match with idf weights. As $k_1$ grows the approach to the ceiling slows, and the model becomes more tolerant of high counts. Values around 1.2 to 2.0 are the conventional range; the default in Lucene-derived systems is 1.2.

The length component $1-b+b,|D|/\text{avgdl}$ is a multiplier on $k_1$, and therefore controls how quickly a document saturates. A short document reaches its term-frequency ceiling at a lower count than a long one, because the length-scaled constant is smaller. This is the desired behaviour: two occurrences in a 200-token document are stronger evidence than two occurrences in a 5,000-token document.

Setting $b=0$ removes length normalization and leaves $k_1$ as the only control. Setting $b=1$ makes the normalization fully proportional to length relative to the collection mean. The conventional value is 0.75, a deliberate compromise: full proportional normalization over-penalizes long documents that are long because they are thorough, and it also interacts badly with collections whose length distribution is skewed.

import math

def bm25_term_score(tf, doc_len, avg_len, doc_freq, n_docs,
                    k1=1.2, b=0.75):
    # Lucene-style idf, always positive for terms that occur
    idf = math.log(1.0 + (n_docs - doc_freq + 0.5) / (doc_freq + 0.5))
    norm = 1.0 - b + b * doc_len / avg_len
    return idf * (tf * (k1 + 1.0)) / (tf + k1 * norm)

The idf term deserves separate attention. The classic form $\log\frac{N-n+0.5}{n+0.5}$ turns negative when a term appears in more than half the collection, and a negative weight means a document is penalized for containing a query term. Implementations that care about this add one inside the logarithm, which keeps the weight positive and monotone decreasing in document frequency, at the cost of compressing the dynamic range for rare terms.

What the parameters trade against each other

$k_1$ and $b$ are not independent, and the reason is structural: $b$ only acts through the product $k_1\cdot\text{norm}$. Raising $k_1$ while lowering $b$ can leave scores nearly unchanged for documents near the average length, while shifting the relative ordering for documents far from it. A grid search over one parameter with the other fixed will land on a different optimum depending on the starting point.

The practical consequence is that parameter tuning is collection-specific and does not transfer well. A collection of short, homogeneous documents (titles, product names) usually wants less length normalization and a smaller $k_1$, because there is little length variance to correct. Long, heterogeneous documents such as crawled web pages benefit from stronger normalization.

There is also an interaction with the query side that the formula hides. BM25 sums independent per-term contributions, so a query with five terms that all appear in a document scores higher than a query with one term appearing in the same document, even if the five-term document is a worse answer. Query term count is therefore a confound, which is why later articles in this cluster treat score normalization as a separate problem rather than something BM25 can solve. See Score Normalization and Rank Fusion for how heterogeneous scores are made comparable.

Where the independence assumption fails

The model treats each query term as an independent piece of evidence. Two consequences follow, and both show up as ranking failures rather than as subtle score differences.

First, phrase structure is invisible. A document containing “library” and “search” anywhere scores well for the query “search library” even if the terms are in unrelated paragraphs. Proximity and phrase features exist to recover this signal, and they are computed separately from BM25 rather than inside it; Query-Document Feature Extraction covers how the position lists are turned into ordered-window features.

Second, term dependence across the query is invisible. “New York” as a query has two terms whose joint occurrence is far more informative than the product of their individual frequencies. BM25 cannot express that; the usual fix is to index multi-word units as single tokens at analysis time, which moves the problem into the tokenizer rather than the scorer.

The saturating term-frequency shape also fails in one specific direction: it is too forgiving of a document that repeats a query term many times in a context where one occurrence would do. Because the ceiling is reached quickly, a document with ten occurrences and a document with fifty converge to nearly the same score. That is usually the intent, but for fields like titles or anchors, where a repeated term is a strong signal of manipulation, a linear or near-linear component is sometimes added on top.

Fields, not documents

BM25 as written scores a document. Real indexes have fields, and a term match in a title is worth more than a match in the body. The direct extension is to compute the saturating component per field with its own length normalization and its own $b$, then combine the per-field counts into a single weighted pseudo-frequency before applying the outer saturation. That arrangement, usually called BM25F, preserves the single-ceiling property while allowing field weights.

The alternative, scoring each field independently with its own BM25 and summing, produces a different and generally worse model: a query term present in five fields gets five separate ceilings, which re-introduces unbounded reward for repetition. The distinction matters when configuring a search engine that exposes both. Lucene’s per-field scoring composes field scores through a disjunction, not through a summed pseudo-frequency, and the tie-breaking behaviour of that composition is the subject of Disjunction-Max Combination for Multi-Field Scoring.

Degenerate cases worth knowing

An empty document has length zero, and the length ratio becomes zero, so norm collapses to $1-b$. With the conventional $b=0.75$ that leaves a positive denominator, but with $b=1$ the denominator is zero and the score is undefined. Implementations clamp the length or the ratio to avoid the division; a scorer that does not will produce infinities on empty fields, which then propagate into any downstream arithmetic.

A term present in every document has document frequency equal to collection size. In the additive form of idf the weight goes to zero, and with the add-one form it goes to a small positive number. Both behaviours mean the term contributes almost nothing to the ranking, which is correct for a stopword-like term but also means a rare-but-universal term in a small collection cannot discriminate.

Finally, fractional term frequencies appear when the index stores positions with gaps or when field weights are folded into the count. The formula accepts them without complaint, but the ceiling is no longer $k_1+1$ in any meaningful unit, and the length normalization is computed on a token count that no longer corresponds to the weighted count. Mixing raw lengths with weighted frequencies is a common source of scores that look plausible and order documents incorrectly.