BM25 and keyword search

BM25 is TF-IDF with two corrections, and it has been the standard in search engines for thirty years. It is still hard to beat.

Correction 1 — saturation. In TF-IDF a word occurring 100 times is ten times as relevant as one occurring 10 times. That is not true. After a few occurrences, further ones add almost nothing. BM25 lets the contribution flatten out.

Correction 2 — softer length normalisation. TF-IDF divides straight by the length, which punishes long documents hard. BM25 compares with the average document length and has a parameter for how hard it should bite.

The result is a measure with only two settings (k1 and b), which rarely need changing, and which is nearly always a strong baseline.

$\mathrm{BM25}(q, d) = \sum_{t \in q} \mathrm{IDF}(t)\cdot\frac{f_{t,d}\,(k_1+1)}{f_{t,d} + k_1\left(1 - b + b\dfrac{|d|}{\text{avgdl}}\right)}$

with $\mathrm{IDF}(t) = \ln\!\left(\dfrac{N - n_t + 0.5}{n_t + 0.5} + 1\right)$.

The saturation in figures (with $k_1 = 1.5$, the length factor = 1):

BM25 approaches the ceiling $k_1 + 1 = 2.5$ and never goes above it. That makes the method robust against keyword spam and against documents that happen to repeat a word.

The extreme cases: $b = 0$ gives no length normalisation at all, $k_1 = 0$ makes only the occurrence count (as in Bernoulli).

When keyword search beats vector search:

When vector search wins: paraphrases («car» against «vehicle»), questions formulated in natural language, and cross-language search.

In practice both are used. Hybrid search with reciprocal rank fusion nearly always beats either on its own — and that is the standard setup in modern RAG systems.

import math, re
from collections import Counter

class BM25:
    def __init__(self, corpus, k1=1.5, b=0.75):
        self.k1, self.b = k1, b
        self.docs = [re.findall(r"\w+", d.lower()) for d in corpus]
        self.text = corpus
        self.N = len(self.docs)
        self.length = [len(d) for d in self.docs]
        self.avgdl = sum(self.length) / self.N
        self.df = Counter(t for d in self.docs for t in set(d))
        self.tf = [Counter(d) for d in self.docs]

    def idf(self, t):
        n = self.df.get(t, 0)
        return math.log((self.N - n + 0.5) / (n + 0.5) + 1)

    def score(self, query, i):
        s = 0.0
        for t in re.findall(r"\w+", query.lower()):
            f = self.tf[i][t]
            if not f:
                continue
            denominator = f + self.k1 * (1 - self.b + self.b * self.length[i] / self.avgdl)
            s += self.idf(t) * f * (self.k1 + 1) / denominator
        return s

    def search(self, query, k=3):
        p = sorted(((self.score(query, i), i) for i in range(self.N)), reverse=True)
        return [(self.text[i], round(s, 3)) for s, i in p[:k] if s > 0]

corpus = [
    "Error code E404 means that the page was not found",
    "The page could not be found and the server answered with an error",
    "Error code E500 is an internal server error",
]
bm = BM25(corpus)
for hit, p in bm.search("E404"):
    print(f"{p:.3f}  {hit}")
# 1.833  Error code E404 means that the page was not found
#  ← an exact term: vector search would have ranked the first two almost equally

# The saturation — what separates BM25 from TF-IDF
k1 = 1.5
for f in (1, 2, 5, 20, 100):
    print(f"f={f:>3}  tfidf {f:>5.1f}   bm25 {f * (k1 + 1) / (f + k1):.2f}")
# f=  1  tfidf   1.0   bm25 1.00
# f=  5  tfidf   5.0   bm25 1.92
# f=100  tfidf 100.0   bm25 2.46   ← the ceiling is k1 + 1 = 2.5