You type two words into a search box and get back the ten most relevant pages out of millions, in a few milliseconds. Before embeddings and vector search, all of this was keyword search, and a lot of it still is. BM25 is still the default ranking in Lucene, Elasticsearch and OpenSearch, and it's the baseline every new retrieval model gets compared against.

So what exactly do I know about search? In this one, I start from the dumbest approach, scanning every document, and fix it one problem at a time: the inverted index for speed, TF-IDF for ranking, and then the three fixes that turn TF-IDF into BM25.

We have 100s of documents, and we need to find the documents related to a given search query, for now, a single word. What we do is search for that word in all the documents one by one, reading each whole document. We need relevant documents. This is a brute-force way to know. For each given word, we run through $N \times L$ words ($N$ documents × $L$ words in each doc).

And we want relevance-ranked documents. So, a naive way to add ranking is to count the number of times that word appears in the document: term frequency (TF).

The inverted index

Now this brute-force way is too slow; you go through the same docs every time you have a new word. If there are millions of docs with 100s of words in each, you know how slow it could be, and search engines are supposed to be fast, returning results in milliseconds.

How about we save some details about each doc or each word beforehand and just use those details, rather than looping over all the docs again and again? The solution is to organise documents by words, rather than going from documents to words. For every unique word in the collection, we save a list of the documents containing that word. This is the word's posting list. (What counts as a "word" here is decided by a preprocessing step that cleans up the text before indexing.)

This inversion, organising docs by words, is called an inverted index. We build it once by traversing all the docs in the collection, updating every word's posting list. So you don't scan the whole collection on each search.

Now this gives us one more thing: when searching for a query with multiple words, we get the posting lists of all the words in the query and intersect them, and we find the docs containing all of them (well, not exactly: for ranking, we take the union, so any doc with at least one query word gets scored, and docs matching more words just score higher. Intersecting is what a strict AND search does).

And again, for relevance, we use term frequency, how many times a word occurred in each doc, and we rank the final list of documents according to it. Documents with higher counts are assumed to be more relevant.

TF-IDF

Then Searchacians realised that these raw counts are flawed. How? Some words appear in almost every doc and don't help distinguish anything. Say your collection is a bunch of recipes and you search "add salt to pasta". Nearly every recipe says "add" and "salt", often many times, so they pile up the score, while "pasta", the word that actually matters, gets drowned. So inverse document frequency (IDF) was introduced. According to it, words that are common across the collection are downweighted and rare words are upweighted. Multiply TF and IDF and it gives you the ranking. Happy.

$$\text{TF-IDF}(q, D) = \text{TF}(q, D) \times \text{IDF}(q)$$ $$\text{IDF}(q) = \ln \frac{N}{n(q)}$$

Here $\text{TF-IDF}(q, D)$ is the score of query word $q$ in document $D$, $N$ is the total number of docs, and $n(q)$ is the number of docs containing $q$.

Where TF-IDF falls short

Now take this raw version of TF-IDF, and suppose two documents: document A is 10 words long and contains $q$ once, and document B is 1000 words long and contains it 10 times. $\text{TF}(B) > \text{TF}(A)$, but logically A should get more priority, because the word appears once in 10 words rather than 10 times in 1000 (1 in 100, ratio-wise). So calculating TF without considering document length is not realistic.

Second, if you look at TF-IDF's dependency on TF, the derivative is a constant:

$$\frac{\partial\, \text{TF-IDF}}{\partial\, \text{TF}} = \text{IDF}(q)$$

It should be some function of TF. Example: "cat" appearing twice in a document makes the document 2 times more important, but "cat" appearing 50 times should not make the document 50 times more important. There should be some cap on this importance, after which it saturates.

BM25

So all these issues led to the Best Matching formulas from the Okapi system, and number 25 of them, BM25, is the one that stuck. It solves the issues above.

For a word in a query, BM25 computes its contribution to the final score. This contribution has 3 parts.

1. IDF

First, the same IDF (total number of docs divided by the number of docs containing the word), taking the log to compress this ratio into a more reasonable, slowly growing number. This is classic IDF. BM25 uses probabilistic retrieval theory. The idea is that you are not just measuring rarity; rather, you are estimating an odds ratio: the odds that a word appears in a relevant document versus a non-relevant one. This leads to $N - n(q)$ in the numerator. Yeah, I didn't fully get this part either, but okay, we accept it.

Then 0.5 is added to both the numerator and the denominator (a Laplace-style continuity correction). This handles the $N = n(q)$ case, where a word is in all docs, and you know, $\log(0)$. So it stabilises the formula for extremely common words. Now if you look at the $\log(x)$ graph, for $x < 1$, $\log(x)$ is negative, so we add $1$ to keep the input at least 1 (this $+1$ is Lucene's version; Robertson's original IDF goes negative for very common words):

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

2. Saturated term frequency

Now the second term of BM25 is the saturated term frequency; here we solve the directly proportional TF issue. We need something that matters at low (actual) TF and saturates at higher TF, approaching a ceiling, which we call $k + 1$. So the second term is now:

$$\frac{\text{TF} \cdot (k + 1)}{\text{TF} + k}$$

$k$ (usually written $k_1$) is a tunable constant, usually somewhere around 1.2 to 2. If you plot this new term against TF, it is significant at low TF and approaches $k + 1$ as TF increases.

3. Length normalisation

Now the third part, the last issue: length normalisation. We calculate

$$\theta = \frac{|D|}{\text{avgdl}}$$

the length of this document divided by the average document length across the whole collection. We tune θ's effect using another constant $b$ (usually 0.75). Now if a document is shorter than average, θ is small, and its effective TF should be boosted a little; each word in it carries more weight. If it's longer than average, the effective TF gets dampened. So the second term becomes:

$$\frac{\text{TF} \cdot (k + 1)}{\text{TF} + k \cdot (1 - b + b \cdot \theta)}$$

Putting it together

For a query $Q$ containing words $q$:

$$\text{BM25}(D, Q) = \sum_{q \in Q} \text{IDF}(q) \cdot \frac{\text{TF}(q, D) \cdot (k + 1)}{\text{TF}(q, D) + k \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}$$

So for every word in the query: how rare it is in the collection, how many times it shows up in this doc (with a ceiling), and how long this doc is compared to the rest. Add these up across the query words and you get the doc's score. Sort by score, return the top ten.

What BM25 doesn't see

BM25 is still a bag of words. All it knows is whether the exact query word is in the doc, how many times, and how long the doc is. That leaves a couple of gaps:

• Exact words only. For BM25, "car" and "automobile" are two unrelated words. If the query says one and the doc says the other, that word adds 0 to the score. This is called the vocabulary mismatch problem. Stemming (cutting "running" down to "run") and hand-made synonym lists help a bit, but only a bit.
• No word order. "dog bites man" and "man bites dog" get the same score.

There are also variants for smaller issues. The full BM25 has one more factor for words repeated in the query, with its own constant $k_3$, but queries are short, so it's usually dropped. BM25F scores fields like the title and the body separately and weighs them. BM25+ adds a small constant so that a very long doc containing the word never scores almost the same as a doc without it.

What's next

Still, BM25 is fast, needs no training, and works out of the box on any collection. That's why it's still the baseline. So the next question is: can we keep the inverted index and the speed, but let a model decide which words a doc should match and how much each one should count? That's learned sparse retrieval, and that's what Part 2 is about: SPLADE.

---

References

1. BM25: The Most Important Text Metric in Data Science (video)