BM25: the ranking function behind most search engines

Two fixes to TF-IDF

BM25 ("best matching 25") keeps the idea of weighting rare terms, and adds two corrections:

1. Saturation: the first few occurrences of a term matter a lot; the twentieth barely matters.
2. Length normalisation: a term appearing three times in a tweet means more than three times in a book.

The formula

For a query with terms q, the score of document D is the sum over terms of:

IDF(q) x f(q,D) x (k1 + 1) / ( f(q,D) + k1 x (1 - b + b x |D| / avgdl) )

• f(q,D) is how many times the term occurs in D.
• |D| is the length of D and avgdl the average document length in the index.
• k1 (about 1.2) sets how fast the term saturates.
• b (about 0.75) sets how strongly length matters.
• A common IDF is ln(1 + (N - n + 0.5) / (n + 0.5)), which never goes negative.

100%

Figure SDA-SAG-02-1 · What BM25 adds on top of IDF · © forcsguy.com

A worked example

With k1 = 1.2, b = 0.75 and a term appearing 3 times:

• Average-length document: 3 x 2.2 / (3 + 1.2) = 1.57.
• Twice the average length: 3 x 2.2 / (3 + 1.2 x 1.75) = 6.6 / 5.1 = 1.29.
• Same document but the term appears 30 times at average length: 30 x 2.2 / (30 + 1.2) = 2.12, close to the ceiling of k1 + 1 = 2.2.

So ten times as many occurrences is worth only 35 percent more. That is saturation.

// Minimal BM25 term score, ready to use in a toy engine
function bm25(f: number, len: number, avgLen: number, N: number, n: number, k1 = 1.2, b = 0.75) {
  const idf = Math.log(1 + (N - n + 0.5) / (n + 0.5));
  return idf * (f * (k1 + 1)) / (f + k1 * (1 - b + (b * len) / avgLen));
}

Tuning in practice

• Start with the defaults; they work for general text.
• Short fields such as titles often want a lower b (length matters less), while long bodies keep the default.
• Fields have different value: a match in the title usually counts for more than in the body, so engines let you weight fields (BM25F style) or run separate fields and combine the scores.
• BM25 is a first-stage ranker. Many systems retrieve a few hundred candidates with BM25 and re-rank them with a machine-learned model that also uses freshness, clicks and personalisation.
• Measure changes with the metrics in the evaluation lesson; never tune by looking at three queries.

100%

Figure SDA-SAG-02-2 · Retrieval then re-ranking · © forcsguy.com

Real-world reading