BM25 (Lexical Search) in Machine Learning

The Origins of Relevance Ranking

Before BM25, search engines used raw TF-IDF (term frequency–inverse document frequency) to rank documents. TF-IDF was groundbreaking in the 1970s — it formalized the intuition that a term appearing frequently in a document but rarely in the corpus is probably important. But raw TF-IDF has a critical flaw: unbounded term frequency.

If a document mentions "machine learning" 50 times, raw TF-IDF gives it 50× the score of a document mentioning it once. But does repeating a term 50 times really make a document 50× more relevant? Of course not. After a few occurrences, additional mentions provide diminishing returns. This is the term saturation problem.

The Probabilistic Revolution

In the late 1980s and early 1990s, Stephen Robertson and Karen Spärck Jones at City University London developed a probabilistic framework for information retrieval. Their key insight was to model relevance as a probability: given a query $q$ and a document $d$, what's the probability that $d$ is relevant to $q$?

This led to the BM (Best Match) family of ranking functions. BM1 through BM24 were experimental variants. BM25 — the 25th iteration — introduced the elegant combination of saturating term frequency (controlled by parameter $k_1$) and document length normalization (controlled by parameter $b$) that proved empirically superior across dozens of retrieval benchmarks.

The algorithm was validated extensively through the TREC (Text REtrieval Conference) evaluations organized by NIST, where BM25-based systems consistently topped the rankings throughout the 1990s and 2000s.

Why BM25 Still Dominates

Three decades later, BM25 remains the foundation of production search for several reasons:

1. Zero training cost: Unlike neural retrievers that require labeled query-document pairs and GPU training, BM25 works out of the box on any text corpus
2. Millisecond latency: Inverted index lookup is $O(\\sum |posting\\_list|)$, typically under 5ms even on billion-document corpora
3. Exact match precision: When users search for specific terms (product IDs, error codes, proper nouns), BM25 achieves near-perfect precision
4. Robustness: BM25's performance doesn't degrade on out-of-domain data the way neural models can

For Indian companies operating at scale — Flipkart processing 1.5 billion search queries per month, Razorpay indexing millions of transaction records, or IRCTC handling train booking queries — BM25 provides the fast, reliable retrieval baseline that more expensive methods refine.

The Library Analogy

Imagine you're a librarian at a massive library. A patron walks in and asks for books about "quantum entanglement experiments". How would you find the most relevant books?

You'd mentally apply three heuristics:

1. Term frequency: Books that mention "quantum entanglement" many times are probably more relevant than those that mention it once in passing. But there's a ceiling — a book repeating the phrase 100 times isn't necessarily better than one mentioning it 10 times in context.

2. Rarity: The word "experiments" appears in many books, so it's not very discriminating. But "entanglement" is rare — books containing it are likely relevant. You'd weight rare terms more heavily.

3. Document length: A 1000-page encyclopedia might mention "quantum entanglement" 5 times, but that's just because it covers everything. A focused 50-page monograph mentioning it 5 times is much more relevant. You'd adjust for document length.

BM25 formalizes exactly these three heuristics into a mathematical formula. The $k_1$ parameter controls how quickly term frequency "saturates" (heuristic 1), the IDF component handles rarity (heuristic 2), and the $b$ parameter controls length normalization (heuristic 3).

The Saturation Curve

The key innovation of BM25 over raw TF-IDF is the saturation function. Instead of term frequency growing linearly, BM25 maps it through:

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

This is a concave function that starts steep (first few occurrences matter a lot) and flattens out (additional occurrences contribute less and less). When $k_1 = 0$, all non-zero term frequencies are treated equally (binary model). When $k_1 \\to \\infty$, you get raw TF-IDF back. The typical value of $k_1 = 1.2$ provides a nice middle ground.

Think of it like hot sauce: The first few drops transform a dish. But after a certain point, adding more doesn't make it "more spicy" — it just makes it inedible. BM25's saturation function captures this diminishing returns effect for term frequency.

The BM25 Scoring Function

Given a query $q$ consisting of terms $q_1, q_2, \\ldots, q_n$ and a document $d$, the BM25 score is:

$\\text{BM25}(q, d) = \\sum_{i=1}^{n} \\text{IDF}(q_i) \\cdot \\frac{f(q_i, d) \\cdot (k_1 + 1)}{f(q_i, d) + k_1 \\cdot \\left(1 - b + b \\cdot \\frac{|d|}{\\text{avgdl}}\\right)}$

where:

• $f(q_i, d)$ is the term frequency of query term $q_i$ in document $d$
• $|d|$ is the document length (number of tokens in $d$)
• $\\text{avgdl}$ is the average document length across the corpus
• $k_1$ is the term frequency saturation parameter (typically 1.2–2.0)
• $b$ is the document length normalization parameter (typically 0.75)

IDF Component

The inverse document frequency is computed as:

$\\text{IDF}(q_i) = \\ln\\left(\\frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} + 1\\right)$

where $N$ is the total number of documents in the corpus and $n(q_i)$ is the number of documents containing term $q_i$. The $+1$ inside the logarithm ensures non-negative IDF values even for terms appearing in more than half the corpus.

Parameter Interpretation

$k_1$ (term saturation):

• $k_1 = 0$: Binary model — only presence/absence matters, not frequency
• $k_1 = 1.2$: Standard value — moderate saturation, good general-purpose setting
• $k_1 \\to \\infty$: Recovers raw TF (no saturation)

$b$ (length normalization):

• $b = 0$: No length normalization — long documents are not penalized
• $b = 0.75$: Standard value — moderate normalization
• $b = 1$: Full normalization — document score scales inversely with length

BM25F (Field-Weighted Variant)

For structured documents with fields (title, body, anchor text), BM25F extends the formula by computing a weighted term frequency across fields:

$\\tilde{f}(q_i, d) = \\sum_{f \\in \\text{fields}} w_f \\cdot \\frac{f_{f}(q_i, d)}{1 - b_f + b_f \\cdot \\frac{l_f}{\\text{avgdl}_f}}$

This allows assigning higher weight to title matches vs. body matches, which is critical in web and e-commerce search.

Complexity Analysis

• Indexing: $O(T)$ where $T$ is total tokens across all documents
• Query: $O(\\sum_{i} |\\text{posting}(q_i)|)$ — sum of posting list lengths for query terms
• Space: $O(T)$ for the inverted index (plus optional compression)

With skip pointers and block-max algorithms (BMW), query processing on billion-document indexes stays under 10ms.

BM25 (Best Match 25) is the foundational lexical retrieval algorithm that has powered production search systems for three decades. By combining term frequency saturation, inverse document frequency weighting, and document length normalization into an elegant formula with just two tunable parameters ($k_1$ and $b$), BM25 delivers fast, interpretable, and training-free document retrieval.

In modern ML systems, BM25's role has evolved from standalone ranking function to first-stage retriever in hybrid pipelines. The retrieve-then-rerank architecture — BM25 for recall, cross-encoder for precision — remains the dominant pattern in production RAG systems. BM25's strengths (exact match, zero training cost, millisecond latency) perfectly complement dense retrieval's strengths (semantic matching, vocabulary gap bridging), making hybrid search the recommended approach for any serious retrieval system.

For ML engineers building RAG pipelines, the key takeaway is: never skip BM25. Even when using state-of-the-art dense retrievers, a BM25 component improves recall for keyword queries, provides a safety net for out-of-domain inputs, and costs essentially nothing in additional latency when run in parallel. Start with BM25, measure where it fails, and add dense retrieval to cover the gaps.