BM25 and Term Frequency Saturation

BM25 dates from the Okapi system's TREC-3 submission in 1994 and it remains the baseline that neural retrieval papers are obliged to beat, frequently by less than the abstract implies (Robertson et al., 1994, Okapi at TREC-3; the full derivation is in Robertson and Zaragoza, 2009, The Probabilistic Relevance Framework: BM25 and Beyond). Its durability is not nostalgia. It encodes three empirical facts about relevance that every subsequent method has had to rediscover.

The three facts encoded

Rare terms carry more information. The IDF factor, in BM25's form \(\log\frac{N - n_t + 0.5}{n_t + 0.5}\), weights a term by how surprising its occurrence is. A document matching "photosynthesis" tells you far more than one matching "process".

Term frequency saturates. This is the piece that separates BM25 from TF-IDF. The ratio \(\frac{f(k_1+1)}{f + k_1 \cdot(\ldots)}\) is a hyperbola in \(f\): it rises steeply at first and asymptotes to \(k_1 + 1\). Going from one occurrence to two is strong evidence; going from twenty to forty is nearly none. Raw term frequency, used linearly, lets one keyword-stuffed document dominate, and the saturation is what makes BM25 robust to it.

Length must be normalised, but not fully. A long document contains more terms by construction, so raw counts favour it. The term \(1 - b + b\frac{|d|}{\text{avgdl}}\) in the denominator penalises documents longer than average. At \(b=1\) normalisation is complete, dividing through by relative length; at \(b = 0\) it is off. The default \(b = 0.75\) is a partial normalisation, encoding the observation that longer documents are somewhat more likely to be relevant, since they cover more ground, but not proportionally so.

What the parameters do, concretely

\(k_1\) controls how fast saturation sets in, typically 1.2 to 2.0. At \(k_1 = 0\) the term frequency component collapses to a binary "does the term appear", which is sometimes the right model for very short documents such as product titles. Raising \(k_1\) pushes the curve toward linear, giving repeated occurrences more credit.

\(b\) controls length normalisation, typically 0.75. It is the parameter worth tuning per field: for short structured fields such as titles, \(b\) near 0 or a low value is usually better, since a title being twice as long says little about relevance. BM25F extends the model to multiple fields with per-field weights and \(b\) values, combining field frequencies before saturation rather than scoring fields independently, which is the correct order and a common implementation mistake.

Concretely, with \(k_1 = 1.2\), \(b = 0.75\) and a document of average length, the saturating factor for \(f = 1\) is \(2.2/2.2 = 1.0\); for \(f = 5\) it is \(11/6.2 \approx 1.77\); for \(f = 20\) it is \(44/21.2 \approx 2.08\). Twenty occurrences are worth roughly twice one occurrence, not twenty times.

Why saturation makes fast retrieval possible

Saturation bounds each term's maximum contribution, and that bound is what dynamic pruning exploits: if a document's best possible score, summing the per-term maxima, cannot exceed the current \(k\)-th best, it can be skipped without being scored. An unbounded scoring function would make this impossible. The efficiency of modern query processing is a direct consequence of a modelling decision made for accuracy reasons.

When it breaks

Vocabulary mismatch is untouched. BM25 matches terms, so a query for "car" does not retrieve a document about "automobile". Expansion, learned sparse retrieval and dense embeddings all address this, and it is the one dimension where lexical retrieval is structurally deficient rather than merely tunable.

Defaults are tuned for prose. \(k_1 = 1.2\), \(b = 0.75\) come from long-document TREC collections. On product catalogues, code search, or log search, both parameters can be substantially wrong, and tuning them on a few hundred labelled queries frequently yields more improvement than replacing the ranker.

IDF can go negative. With the standard formulation, a term appearing in more than half the corpus produces a negative IDF, which can make adding a matching term reduce a document's score. Implementations either floor it at a small positive value or use a \(\log(1 + \cdot)\) variant, and the behaviour differs between systems in ways that surprise people comparing results across engines.

It has no notion of term dependence. The score is a sum over independent terms, so "New York" scores as "New" plus "York". Sequential dependence models and phrase fields patch this externally; the base model cannot express it.

Scores are not comparable across queries. BM25 is unbounded and query-dependent, so a score of 14 means nothing without knowing the query. Thresholding on raw scores, common in RAG pipelines, is unsound; ranking within a query is what the score supports.