BM25 - How It Actually Works: Probabilistic Relevance, Term Saturation, and Length Normalization

BM25 was developed by Stephen Robertson, Karen Spärck Jones and colleagues for the Okapi system at City University London in the early-to-mid 1990s. It has two tunable constants and nothing learned, it ignores word order, and it knows nothing about meaning. It is also the default ranking function in Lucene, Elasticsearch and OpenSearch, it is the first stage of a huge number of production search systems, and it is still a strong baseline for neural retrieval. On the BEIR benchmark (Thakur et al., 2021), which tests retrievers zero-shot on 18 diverse datasets, BM25 outperformed many dense retrievers that had beaten it on their own training domain.

Knowing why the formula works is useful in two ways. It explains when BM25 should be trusted and when it should be combined with something else. And many ideas in modern retrieval, including learned sparse models, hybrid search and even the way dense retrievers are evaluated, are defined in relation to it.

The formula

Given a query $Q$ with terms $t_1, \dots, t_n$ and a document $d$ , BM25 scores the document as a sum over query terms:

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

where

$f(t, d)$ is the number of times term $t$ occurs in $d$ (term frequency),
$|d|$ is the length of $d$ in terms, and $\text{avgdl}$ is the average document length in the collection,
$k_1$ controls term-frequency saturation (typically 1.2–2.0),
$b$ controls length normalization (typically 0.75),
$\text{IDF}(t)$ is an inverse document frequency weight, discussed below.

The formula has three ideas multiplied together: rare terms matter more (IDF), repeated occurrences help with diminishing returns (saturation), and occurrences in a long document are worth less than in a short one (length normalization). Each one comes from a specific modelling argument, and each one can be switched off with a parameter.

The machinery underneath: the inverted index

BM25 is fast because of the data structure it is computed over. An inverted index maps each term to a postings list: the documents that contain it, with the term frequency in each (and often positions, for phrase queries). Alongside it, the index stores each document’s length and collection statistics: the number of documents $N$ , the document frequency $n(t)$ of each term, and $\text{avgdl}$ .

"cache"    -> [(doc 3, tf 2), (doc 17, tf 1), (doc 42, tf 6), ...]   n = 100
"eviction" -> [(doc 17, tf 3), (doc 90, tf 1)]                        n = 2
doc_len    -> {3: 120, 17: 45, 42: 300, ...}                           avgdl = 100

Scoring a query only touches the postings lists of the query terms. A document that contains none of them is never visited, and its score is implicitly zero. A query over a billion-document index might read a few thousand postings for rare terms and a few million for common ones, instead of a billion documents.

Query evaluation can traverse the lists term-at-a-time (accumulate each term’s contributions into a score table) or document-at-a-time (walk all lists in parallel by document ID and score each document completely). Document-at-a-time enables dynamic pruning. Algorithms such as WAND and Block-Max WAND store an upper bound on each term’s maximum possible contribution, and skip over documents that cannot possibly enter the current top- $k$ . This is why BM25 retrieval stays fast even for long queries over huge collections: most documents are never scored at all.

import math
from collections import Counter, defaultdict

class BM25:
    def __init__(self, docs, k1=1.2, b=0.75):
        self.k1, self.b = k1, b
        self.postings = defaultdict(list)          # term -> [(doc_id, tf)]
        self.doc_len = []
        for doc_id, tokens in enumerate(docs):
            self.doc_len.append(len(tokens))
            for term, tf in Counter(tokens).items():
                self.postings[term].append((doc_id, tf))
        self.N = len(docs)
        self.avgdl = sum(self.doc_len) / self.N

    def idf(self, term):
        n = len(self.postings.get(term, ()))
        return math.log(1 + (self.N - n + 0.5) / (n + 0.5))   # Lucene-style, always >= 0

    def search(self, query_tokens, k=10):
        scores = defaultdict(float)
        for term in set(query_tokens):              # term-at-a-time accumulation
            w = self.idf(term)
            for doc_id, tf in self.postings.get(term, ()):
                norm = self.k1 * (1 - self.b + self.b * self.doc_len[doc_id] / self.avgdl)
                scores[doc_id] += w * tf * (self.k1 + 1) / (tf + norm)
        return sorted(scores.items(), key=lambda x: x[1], reverse=True)[:k]

Where IDF comes from

The intuition for IDF is familiar: a term that appears in every document tells you nothing about which document is relevant, and a term that appears in three documents tells you a lot. BM25’s particular form of IDF comes from the probabilistic relevance framework, which asks: given what a document contains, what are the odds it is relevant?

The binary independence model treats each document as a set of present or absent terms, assumes terms are independent given relevance, and ranks documents by the log-odds of relevance. Under those assumptions the ranking reduces to a sum, over the query terms present in the document, of the Robertson–Spärck Jones weight:

w(t) = \log \frac{p_t\,(1 - q_t)}{q_t\,(1 - p_t)},

where $p_t$ is the probability that $t$ appears in a relevant document and $q_t$ the probability that it appears in a non-relevant one. With no relevance judgements available, two approximations are made: $p_t$ is treated as a constant ( $0.5$ ), and since almost every document in a large collection is non-relevant to a given query, $q_t$ is estimated from the whole collection as $n(t)/N$ . With $0.5$ added to the counts for smoothing, this gives

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

So IDF is not just a heuristic. It is the evidence weight a term carries about relevance when nothing else is known.

One detail matters in practice. For a term that appears in more than half the documents, $N - n(t) < n(t)$ and this IDF becomes negative, so matching a very common word lowers a document’s score. That follows from the model (such a term is more typical of non-relevant documents), but it causes strange rankings. Lucene and most modern implementations use

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

which is always positive and close to the original for rare terms.

Term-frequency saturation

The binary model ignores how often a term appears. Raw term frequency is the obvious fix, as in TF-IDF, but it is a poor one: a document that mentions “cache” 40 times is not 40 times more relevant than one that mentions it once, and linear TF lets a single repeated term dominate the score.

Robertson and Walker motivated a better shape with the 2-Poisson model of eliteness. The idea is that for a given term, documents are either about the concept (“elite”) or not. Within each group, occurrences follow a Poisson distribution with a different rate. A high count is strong evidence that a document is elite, but once it is clearly elite, extra occurrences add little. The full model has too many parameters to estimate, so BM25 approximates its shape with a simple saturating function:

\text{tf-component}(f) = \frac{f\,(k_1 + 1)}{f + k_1}.

It is 0 when $f = 0$ , equals 1 when $f = 1$ , increases with $f$ , and approaches $k_1 + 1$ as $f \to \infty$ . With $k_1 = 1.2$ and a document of average length:

Occurrences $f$	1	2	5	10	∞
tf-component	1.00	1.38	1.77	1.96	2.20

BM25 term-frequency component against number of occurrences for three values of k1, compared with linear term frequency

Figure 1. BM25’s term-frequency component saturates toward k1 + 1, while raw term frequency grows without limit. Smaller k1 saturates sooner.

The second occurrence adds 38%, going from five to ten adds 11%, and no number of repetitions can more than double the score of a single occurrence. $k_1$ sets how fast saturation happens. At $k_1 = 0$ , frequency does not matter at all, and the model becomes binary. With large $k_1$ , frequency keeps mattering for longer, and the function approaches raw TF.

Saturation also makes BM25 fairer across query terms. Without it, a document repeating one query term many times can outscore a document that contains every query term once. With it, matching more distinct terms is usually worth more than repeating one.

Length normalization

Long documents contain more terms and more repetitions simply by being long. Two hypotheses explain why, and they need different treatment:

Verbosity: some authors use more words to say the same thing. Term counts in a verbose document should be scaled down.
Scope: some documents are longer because they cover more topics. Their term counts are genuine, and penalizing length would hurt them.

BM25 does not decide between them. It interpolates with $b$ . It replaces $k_1$ in the saturation function with a length-adjusted value:

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

For a document of average length, $K = k_1$ . For a document twice the average length with $b = 0.75$ , $K = 1.75\,k_1$ , so it needs more occurrences to reach the same tf-component. For a short document, $K < k_1$ and fewer occurrences are needed.

At $b = 1$ , normalization is full: term frequency is effectively divided by relative length (the verbosity view).
At $b = 0$ , length is ignored (the scope view).
$b = 0.75$ is a compromise that works well on typical collections.

Term-frequency component for three occurrences as document length varies, for b = 0, 0.5, 0.75 and 1

Figure 2. The same three occurrences are worth more in a short document and less in a long one. b sets how strongly length matters; at b = 0 it does not matter at all.

A worked example

Take a collection of $N = 1{,}000$ documents with $\text{avgdl} = 100$ , and the query kv cache. Suppose “kv” appears in 20 documents and “cache” in 100. With the Lucene IDF:

\text{IDF}(\text{kv}) = \ln\!\left(1 + \tfrac{980.5}{20.5}\right) \approx 3.89, \qquad \text{IDF}(\text{cache}) = \ln\!\left(1 + \tfrac{900.5}{100.5}\right) \approx 2.30.

Now compare two documents, with $k_1 = 1.2$ :

Document A, a focused 50-term passage: “kv” twice, “cache” once.
Document B, a 300-term page: “kv” 5 times, “cache” 6 times.

	Document A (50 terms)	Document B (300 terms)
$K(d)$ with $b = 0.75$	$1.2 \times 0.625 = 0.75$	$1.2 \times 2.5 = 3.0$
Score with $b = 0.75$	$3.89 \times 1.60 + 2.30 \times 1.26 \approx$ 9.11	$3.89 \times 1.38 + 2.30 \times 1.47 \approx$ 8.72
Score with $b = 0$	$3.89 \times 1.38 + 2.30 \times 1.00 \approx$ 7.65	$3.89 \times 1.77 + 2.30 \times 1.83 \approx$ 11.11

With standard parameters, the short, focused passage ranks first despite having fewer matches: relative to its length, it is denser in the query terms. With length normalization switched off, the long page wins on raw counts. Neither answer is universally right, which is exactly why $b$ is a tunable parameter. This also shows that “kv”, the rarer term, carries more of each score than “cache”.

Tuning $k_1$ and $b$

The defaults ( $k_1 \approx 1.2$ , $b = 0.75$ ) are robust, but tuning on a set of labelled queries often gives real gains. Some patterns:

Short, uniform documents (product titles, tweets, names): lower $b$ , often toward 0.3 or below. When every document is short, length differences are mostly noise, and normalization hurts.
Long documents of very different lengths (web pages, books split into chapters): $b$ near 0.75 or higher.
Domain-specific corpora with lots of repetition (logs, boilerplate-heavy legal or medical text): lower $k_1$ , so repeated terms do not dominate.
Corpora where repetition really signals topicality (long technical articles): higher $k_1$ , up to about 2.

A simple grid search over $k_1 \in [0.5, 2.0]$ and $b \in [0.3, 1.0]$ , scored with nDCG@10 or recall@100 on even a few hundred labelled queries, is usually enough.

Text analysis matters as much as the formula

BM25 scores whatever tokens it is given, so the analysis chain, which turns text into index terms, has a large effect on quality:

Normalization: lowercasing, Unicode normalization, removing accents.
Stemming or lemmatization: mapping “caching”, “cached” and “caches” to one term. This improves recall but can merge words with different meanings (“university” and “universe” under aggressive stemmers).
Stopwords: removing very common words shrinks the index, but breaks queries where they matter (“to be or not to be”, “The Who”). With IDF already down-weighting common words, many modern systems keep stopwords.
Tokenization of identifiers: splitting getUserById or kv_cache_size into parts, keeping version numbers together, and handling hyphens are often the difference between a useful and a useless code or product search.
Synonyms: expanding “laptop” to “notebook” at index or query time partly addresses vocabulary mismatch, at the cost of precision when synonyms are context-dependent.

Variants and extensions

BM25F (fields). Documents often have structured fields, such as title, headings, body and anchor text, and a match in the title is worth more than one in the body. The naive approach scores each field with BM25 and adds up weighted scores. That breaks saturation: a term appearing once in the title and once in the body gets two unsaturated contributions. BM25F instead combines weighted term frequencies across fields first, with per-field length normalization, and applies saturation once to the combined frequency.

BM25+ and BM25L. Lv and Zhai (2011) showed that for very long documents, the normalized term-frequency component can become so small that a long document containing a query term scores barely higher than one that does not contain it. BM25+ adds a small constant $\delta$ to the tf-component of every matching term to enforce a lower bound.

Query term frequency. The original Okapi formula also has a saturating component for repeated query terms, with its own parameter $k_3$ . Since most queries are short and rarely repeat words, it is often dropped.

Pseudo-relevance feedback. Methods such as RM3 assume the top few results are relevant, extract their most characteristic terms, and expand the query with them. This often improves recall noticeably at the cost of a second retrieval pass and occasional topic drift.

Learned sparse retrieval. Neural models can work with the inverted index rather than replace it. doc2query and docT5query generate likely questions for each document and append them before indexing, which adds missing vocabulary. DeepCT learns term weights from context instead of using raw term frequency. SPLADE uses a masked-language-model head to produce a sparse, weighted vector over the whole vocabulary for each document and query, including expansion terms that never appear in the text. These keep the efficiency and exact-match behaviour of an inverted index while learning which terms matter.

Complexity and scaling

Index size is proportional to the number of (term, document) pairs, which is usually a fraction of the raw text size after compression (postings are delta-encoded and bit-packed).
Query cost is proportional to the total length of the postings lists for the query terms, reduced substantially by dynamic pruning. Rare terms are cheap, very common terms are expensive, which is one argument for keeping IDF and pruning together.
Updates are cheap compared to vector indexes: a new document is tokenized and appended to postings lists, and Lucene-style systems merge immutable segments in the background.
Distributed statistics need care. When an index is split into shards, each shard computes its own $N$ , $n(t)$ and $\text{avgdl}$ by default. On small or unevenly distributed shards, the same document can score differently depending on where it lives. Elasticsearch, for example, offers a mode that gathers global term statistics before scoring, at the cost of an extra round trip.

Limitations

Vocabulary mismatch. BM25 cannot match a query to a document that uses different words for the same idea: “cheap flight” against “low-cost airline”, “heart attack” against “myocardial infarction”. This is the main weakness that dense retrieval addresses.
No word order or proximity. “dog bites man” and “man bites dog” are identical to BM25. Proximity features and phrase queries can be added, but they are outside the basic formula.
No understanding of negation or context. A document about “not using a cache” matches cache as well as one about using one.
Scores are not comparable across queries. A BM25 score of 12 means nothing in absolute terms. It depends on query length, term rarity and the collection. Thresholding on raw scores, or combining them directly with dense similarity scores, is unreliable without normalization.
Statistics depend on the collection. Adding many documents on one topic changes IDF for everything.

When BM25 wins

Exact keyword matches: product names, author names, error messages, function names, legal citations, technical terms.
Rare or out-of-vocabulary terms: new product names, identifiers, codes and jargon that an embedding model has never seen, or splits into meaningless pieces.
Queries where the user knows exactly what word they are looking for.
Out-of-domain data, where embedding models were not trained on similar text. BEIR made this point clearly: zero-shot, BM25 is hard to beat on many specialized collections.
Cost-sensitive or frequently updated systems: no GPU, no embedding pipeline, no re-indexing when a model changes, and results that are easy to explain.

Points that are often misunderstood

BM25 is sometimes described as outdated, but it is the baseline most neural retrievers are measured against, and on out-of-domain data it often still wins. Most strong production systems run it alongside dense retrieval rather than replacing it.

It is also not the same as TF-IDF. TF-IDF uses linear term frequency and usually a crude length correction. The saturation curve and the tunable length normalization are what make BM25 work better, and both come from a probabilistic model of relevance.

The default parameters are a reasonable starting point, not an optimum. Collections of short or very uniform documents often do better with noticeably different values. And a BM25 score only means something relative to other scores for the same query.

BM25 in modern systems

In current search and retrieval-augmented generation pipelines, BM25 usually appears in one of three roles:

First-stage candidate generation, retrieving a few hundred or thousand candidates cheaply, which a cross-encoder then reranks.
One half of hybrid search, combined with a dense retriever. Because raw scores are not comparable, results are often merged by rank with reciprocal rank fusion (Cormack et al., 2009):

\text{RRF}(d) = \sum_{r \in \text{retrievers}} \frac{1}{k + \text{rank}_r(d)}, \qquad k = 60 \text{ by convention}.

A document ranked highly by either retriever rises to the top, and one ranked well by both rises further. 3. A baseline and a sanity check. Any new retriever should be compared with tuned BM25 on the target data before it is trusted.