BM25 › The Probabilistic Foundation

BM25 didn't emerge from nowhere. It's the result of decades of research in probabilistic information retrieval, a field that asks: given a query, what's the probability that a document is relevant?

The story begins with the Binary Independence Model (BIM), developed in the 1970s. BIM makes two key assumptions:

1. Binary: Each term either appears in a document or it doesn't (we ignore term frequency)
2. Independence: Terms occur independently of each other given the relevance of a document

Under BIM, we want to rank documents by $P(R|D,Q)$, the probability that document $D$ is relevant given query $Q$. Using Bayes' theorem and the independence assumption, this leads to ranking by:

$$\sum_{t \in Q \cap D} \log \frac{P(t|R) \cdot (1 - P(t|\bar{R}))}{P(t|\bar{R}) \cdot (1 - P(t|R))}$$

where:

• $t$: a term in both the query and document
• $Q \cap D$: the set of terms appearing in both query $Q$ and document $D$
• $P(t|R)$: probability of term $t$ appearing in a relevant document
• $P(t|\bar{R})$: probability of term $t$ appearing in a non-relevant document
• $R$: the event that a document is relevant
• $\bar{R}$: the event that a document is not relevant

The expression inside the logarithm is the odds ratio: it measures how much more likely a term is to appear in relevant documents compared to non-relevant ones. A term that's common in relevant documents but rare in non-relevant ones will have a high odds ratio, contributing positively to the score. A term equally common in both will have an odds ratio near 1, contributing little (since $\log(1) = 0$). We sum these contributions over all terms that appear in both the query and the document.

The difficulty is that we rarely have relevance judgments to estimate these probabilities. Robertson and Spärck Jones showed that with some simplifying assumptions, this reduces to something familiar: inverse document frequency.

The key simplifying assumption is to treat $P(t|R)$ as constant across terms (say 0.5, meaning any relevant document is equally likely to contain any given term), and to estimate $P(t|\bar{R})$ from the empirical document frequency in the collection. With these substitutions and a little algebra, the log-odds expression becomes proportional to the familiar IDF formula. The probabilistic model gives us a principled justification for something that might otherwise seem like a heuristic.

The Binary Independence Model ignores term frequency entirely, which is clearly a limitation. If a document mentions "machine learning" ten times, that should matter more than mentioning it once.

Robertson and Walker addressed this in the 1990s through a series of papers that culminated in BM25. The key insight was to incorporate term frequency in a principled way while maintaining the probabilistic foundation.

The derivation involves the 2-Poisson model, which assumes that term frequencies in relevant and non-relevant documents follow different Poisson distributions. Relevant documents are assumed to have a mixture of two Poisson processes: one for "elite" documents (those about the topic) and one for non-elite documents that happen to contain the term. Working through the math, this mixture model leads to a term frequency weighting that saturates. Additional occurrences provide diminishing returns, which is exactly the behavior we want.

The name "BM25" refers to the 25th model in a series of experiments conducted at the Robertson/Sparck Jones research group. BM11 and BM15 were earlier attempts; BM25 proved to be the most effective formulation. The number has no other special significance.