BM25

BM25 is a lexical scoring function: it ranks documents by how well the words of a query match the words of each document, with no learned vectors involved. It remains a standard baseline and a component of hybrid retrieval because it needs no training, is exact on rare terms such as identifiers, and can be explained term by term.

The formula

For a query \(q\) and document \(d\), BM25 sums a weight over each query term \(t\):

\[ \mathrm{BM25}(q,d)=\sum_{t\in q}\mathrm{idf}(t)\cdot\frac{\mathrm{tf}(t,d)\,(k_1+1)}{\mathrm{tf}(t,d)+k_1\left(1-b+b\,\dfrac{|d|}{\mathrm{avgdl}}\right)}. \]

Here \(\mathrm{tf}(t,d)\) is how many times \(t\) occurs in \(d\), \(|d|\) is the document length in terms, \(\mathrm{avgdl}\) is the average length over the collection, and \(\mathrm{idf}(t)\), the inverse document frequency, is large for terms that appear in few documents. One common form is \(\ln\!\big(1+\frac{N-\mathrm{df}(t)+0.5}{\mathrm{df}(t)+0.5}\big)\) with \(N\) documents and \(\mathrm{df}(t)\) of them containing \(t\). The textbook version by Manning, Raghavan, and Schütze uses \(\log(N/\mathrm{df}_t)\) and an optional query-term-frequency factor, so implementations differ in details but share the structure.

The three ingredients each address a separate problem.

Rare terms matter more (idf). A match on “refund” tells you more than a match on “the”, because most documents contain the latter. The idf weight scales a term’s contribution by how discriminating it is.

Repetition helps, with diminishing returns (\(k_1\)). The fraction \(\mathrm{tf}\,(k_1+1)/(\mathrm{tf}+k_1\cdot\text{norm})\) rises with tf but flattens. With \(k_1=1.2\) and no length effect, tf values 1, 2, 3, 10, and 100 give factors 1.0, 1.375, 1.571, 1.964, and 2.174, approaching the ceiling \(k_1+1=2.2\). A document that says a word 100 times does not score 100 times higher than one that says it once. Setting \(k_1=0\) removes frequency entirely and leaves a binary match; large \(k_1\) approaches raw counting.

The same count means less in a long document (\(b\)). The denominator multiplies \(k_1\) by \(1-b+b\,|d|/\mathrm{avgdl}\). With \(b=0\) length is ignored. With \(b=1\) the count is fully normalized by relative length. The program below fixes idf at 1, average length at 100, and a single occurrence of the term.

idf=1.0; avg=100
def w(tf,L,k1=1.2,b=0.75): return idf*tf*(k1+1)/(tf+k1*(1-b+b*L/avg))
for b in (0.0,0.75,1.0):
    print("b",b,"tf=1: L=50",round(w(1,50,b=b),3),"L=100",round(w(1,100,b=b),3),"L=400",round(w(1,400,b=b),3))

Output:

b 0.0 tf=1: L=50 1.0 L=100 1.0 L=400 1.0
b 0.75 tf=1: L=50 1.257 L=100 1.0 L=400 0.449
b 1.0 tf=1: L=50 1.375 L=100 1.0 L=400 0.379

With \(b=0.75\), a single mention in a 400-term document is worth less than half of the same mention in an average-length one, because a long document is more likely to contain the word by chance. The values commonly recommended when nothing else is known are \(k_1\) between 1.2 and 2 and \(b=0.75\); both are best tuned on a development set.

A worked trace

Take a hypothetical five-document collection, with \(N=5\), \(\mathrm{avgdl}=8.2\), and the query “refund”. Document d1 is “refund requests are processed within five days” (7 terms, one occurrence), and d4 is “refund refund refund policy” (4 terms, three occurrences). Only these two contain the term, so \(\mathrm{df}=2\) and \(\mathrm{idf}=\ln(1+3.5/2.5)=0.875\). With \(k_1=1.2,b=0.75\) the scores are 0.931 for d1 and 1.545 for d4. The program that produced them also shows the \(k_1\) effect: at \(k_1=0\) both score 0.875, at \(k_1=3\) they score 0.954 and 2.167.

Where it works and where it fails

• It is exact on rare strings: error codes, part numbers, and names have high idf and match only where present.
• It matches strings, not meaning. A query for “reimbursement” scores zero against a document that says “refund”. This vocabulary mismatch is why dense retrieval exists.
• What counts as a term depends on the tokenizer. Lowercasing, splitting on punctuation, stemming, or subword splitting change what can match, and an identifier written two ways may never match.
• Scores have no fixed scale. They depend on the collection’s statistics and query length, so they are not comparable across indexes or against cosine similarities; combine them by rank (see Reciprocal Rank Fusion) or normalize carefully.

References

• Manning, C. D., Raghavan, P., Schütze, H., Introduction to Information Retrieval, section on Okapi BM25 — https://nlp.stanford.edu/IR-book/html/htmledition/okapi-bm25-a-non-binary-model-1.html