Nestor G Pestelos Jr · Reference · Print this page

BM25 (Best Matching 25)

BM25 (Best Matching 25), frequently designated as Okapi BM25, is a non-linear probabilistic ranking function used in information retrieval to estimate the relevance of a document to a given search query. Developed during the 1990s as part of the Okapi information retrieval system, BM25 refines classical term frequency and inverse document frequency (TF-IDF) scoring by incorporating sublinear term frequency saturation and document length normalization [1]. It operates as the standard scoring algorithm in major inverted-index search systems, including Apache Lucene, Elasticsearch, OpenSearch, and SQLite FTS5 [2].

1. Mathematical Formulation

1.1 The Scoring Function

Given a query \(Q\) consisting of search terms \(q_1, q_2, \dots, q_n\) and a document \(D\) within a collection of \(N\) documents, the BM25 relevance score is calculated as the sum of contributions from each matching term:

The components of the formula represent the following variables:

• \(f(q_i, D)\): The term frequency of query term \(q_i\) within document \(D\).
• \(|D|\): The length of document \(D\), measured by its total word or token count.
• \(\text{avgdl}\): The average document length across all documents in the collection: $$\text{avgdl} = \frac{1}{N} \sum_{d \in \text{Collection}} |d|$$
• \(k_1\): A positive tuning parameter that calibrates term frequency saturation.
• \(b\): A tuning parameter constrained between 0 and 1 that controls document length normalization.
• \(\text{IDF}(q_i)\): The inverse document frequency of query term \(q_i\).

1.2 Inverse Document Frequency

In the original Okapi BM25 formulation developed by Stephen E. Robertson and Karen Spärck Jones, the inverse document frequency is defined as:

where \(N\) denotes the total document count in the collection, and \(n(q_i)\) represents the number of documents containing term \(q_i\). When a term appears in more than half of the corpus (\(n(q_i) > N / 2\)), the quotient inside the logarithm falls below 1, producing a negative IDF weight. While negative weights can serve to penalize common non-informative words, they often destabilize open-domain retrieval.

Modern production search engines, such as Apache Lucene, apply a floor or a non-negative smoothing modification [3]:

This formulation guarantees that the IDF component remains strictly positive for all collection frequencies, smoothly approaching zero for terms present in every document.

1.3 Term Frequency Saturation

Classical vector space models (TF-IDF) treat term frequency linearly or logarithmically (\(1 + \ln(\text{TF})\)). Under linear scaling, a document that repeats a keyword twenty times receives twenty times the weight of a document that mentions it once. In practice, relevance does not scale linearly with repetition.

BM25 resolves this through asymptotic saturation. Holding document length equal to the average collection length (\(|D| = \text{avgdl}\)), the term frequency component reduces to:

As \(f(q_i, D) \to \infty\), this expression converges monotonically to the upper bound \(k_1 + 1\). The first occurrence of a term delivers the steepest marginal relevance gain. Subsequent occurrences yield progressively smaller increments, preventing keyword-stuffed documents from dominating the ranking.

1.4 Document Length Normalization

Long documents possess two competing characteristics in text retrieval:

1. Scope verbosity: A comprehensive document covers multiple unrelated subtopics, using more words to convey the same information as a concise document.
2. Topic breadth: A larger document simply contains more total information.

BM25 accounts for verbosity by scaling term frequency against relative document length, defined as \(|D| / \text{avgdl}\). The denominator term \(1 - b + b \cdot (|D| / \text{avgdl})\) modulates this effect:

• When \(|D| = \text{avgdl}\), the normalization factor equals exactly 1.
• When \(|D| > \text{avgdl}\), the denominator expands, reducing the effective term frequency.
• When \(|D| < \text{avgdl}\), the denominator shrinks, boosting the score of short, dense documents.

2. Historical Context and Theoretical Foundations

2.1 Probabilistic Relevance Framework

BM25 originates from the 2-Poisson indexing model formalized by Stephen E. Robertson, Karen Spärck Jones, and Steve Walker at City University London [1, 4]. The 2-Poisson model assumes that within any document collection, term occurrences follow a mixture of two Poisson distributions: one distribution for documents where the term is substantively "about" the concept (the elite set), and another where the term appears incidentally.

Because fitting the exact parameters of the 2-Poisson model across massive text collections was computationally intractable for real-time indexing, Robertson and Walker constructed simple rational functions that closely approximated the 2-Poisson curve. BM25 represents the 25th experimental variant produced during this parameter approximation sequence.

2.2 Okapi and the TREC Evaluations

The algorithm was introduced during the third Text REtrieval Conference (TREC-3) in 1994, implemented within the Okapi retrieval engine [4]. Across TREC benchmarks spanning news collections, patent filings, and early web corpora, BM25 demonstrated superior mean average precision (MAP) compared to existing vector space and inference network baselines. Its combination of training-free execution, low indexing overhead, and empirical robustness established it as the primary baseline against which subsequent retrieval models are evaluated.

3. Parameter Calibration

BM25 requires setting two free hyperparameters: \(k_1\) and \(b\). Although defaults exist, optimal values depend on corpus composition.

3.1 The k1 Parameter

When \(k_1 = 0\), the term frequency quotient collapses to 1, reducing the algorithm to binary presence-absence scoring weighted only by IDF. When \(k_1\) is set to high values (such as 10 or higher), saturation occurs very slowly, causing the scoring function to approach linear term frequency scaling. In specialized domains such as source code retrieval, where function names or error codes are repeated methodically, setting \(k_1\) between 1.5 and 2.0 frequently yields higher precision.

3.2 The b Parameter

The parameter \(b\) determines how aggressively the engine penalizes documents that exceed \(\text{avgdl}\):

• \(b = 1.0\): Assumes all variation in document length stems from verbosity. A document of twice the average length must contain twice as many keyword occurrences to achieve the same score.
• \(b = 0.0\): Assumes variation in document length reflects topic breadth rather than redundancy. No length normalization is applied.
• \(b = 0.75\): The empirically validated consensus value across heterogeneous natural language collections, striking a balance between concise and long documents.

4. Variants and Extensions

4.1 BM25F (Field-Weighted BM25)

Modern documents contain structured fields, such as titles, section headers, metadata tags, and body text. Scoring each field independently using BM25 and summing the results leads to flawed length normalization, as field lengths vary wildly.

BM25F, formulated by Hugo Zaragoza and Stephen Robertson in 2004, addresses this by combining term frequencies across fields before applying saturation [5]:

The combined pseudo-frequency \(\tilde{f}(q_i, D)\) is then passed through the standard BM25 saturation function. Each field \(c\) maintains its own importance weight \(w_c\) and field-specific length normalization parameter \(b_c\). This prevents brief matches in titles from being diluted by expansive body text.

4.2 BM25+ and Lower-Bounded Term Frequency

Yuanhua Lv and ChengXiang Zhai demonstrated in 2011 that standard BM25 suffers from an overly severe length penalty for very long documents containing few query term occurrences [6]. Specifically, as \(|D| \to \infty\), the term frequency score approaches zero, allowing irrelevant short documents with a single incidental match to outrank comprehensive documents.

BM25+ introduces a constant lower-bound parameter \(\delta\) (typically set to 1.0):

The added parameter ensures that any document containing a query term receives a minimum score contribution regardless of document length.

4.3 BM25L

BM25L modifies the length normalization component directly before saturation, shifting the effective frequency by a floor value so that long documents are not excessively penalized when their term frequencies are modest [7]. It offers an alternative approach to BM25+ for collections characterized by extreme document length variances.

5. Comparison with Dense Semantic Retrieval

5.1 Lexical Precision versus Embedding Drift

The emergence of dense neural retrieval and vector embeddings transformed information retrieval. Dense models encode documents and queries into continuous vector spaces, calculating relevance via cosine similarity or inner products. While dense retrieval excels at semantic generalizations and handling vocabulary mismatches, it exhibits distinct failure modes compared to BM25.

5.2 Hybrid Retrieval and Reciprocal Rank Fusion

Production retrieval systems frequently operate a hybrid architecture that pairs BM25 with dense vector search. Lexical and semantic indices run in parallel, and their candidate result sets are combined using Reciprocal Rank Fusion (RRF) [8]:

where \(M\) represents the set of retrieval models (such as BM25 and a dense vector retriever), \(r_m(d)\) is the rank position of document \(d\) in model \(m\), and \(k\) is a smoothing constant (typically set to 60). By prioritizing documents that rank consistently well across both lexical and semantic methods, hybrid retrieval mitigates the individual weaknesses of both paradigms.

5.3 Computational Efficiency and Inverted Indices

BM25 executes over standard inverted index data structures using block-max WAND (Weak AND) optimizations. WAND algorithms compute upper bounds on potential BM25 contributions per index block, enabling search engines to skip millions of non-competitive document postings without evaluating them. Consequently, BM25 retrieval evaluates queries in single-digit milliseconds across collections containing tens of millions of documents on standard CPU hardware.