BM25 ranking

Finding matching documents is the easy part. Ranking them is what users notice. BM25 is the scoring function used by Lucene-based engines such as Elasticsearch. It adds one score per query word, and it rewards three things: rare words, repeated words with diminishing returns, and short documents that match.

The big idea

Two intuitions do most of the work.

• A document that mentions "postgres" five times is probably more about Postgres than one that mentions it once. But the tenth mention adds less than the second.
• A match on a rare word tells you more than a match on a common word.

BM25 keeps both ideas and adds a length correction. A match in a 100-word document means more than the same match in a 10,000-word one.

Walking through it

The formula for one term is:

score(term) = IDF × tf × (k1 + 1) / (tf + k1 × (1 − b + b × docLength / avgLength))

IDF = ln(1 + (N − n + 0.5) / (n + 0.5))
N = documents in the index, n = documents containing the term
k1 = 1.2 (saturation), b = 0.75 (length normalization)

Take an index of 1,000 documents with an average length of 200 terms. The query is postgres database. "Postgres" appears in 10 documents, and "database" appears in 300.

• IDF(postgres) = ln(1 + 990.5 / 10.5) ≈ 4.56
• IDF(database) = ln(1 + 700.5 / 300.5) ≈ 1.20

"Postgres" carries almost four times the weight of "database".

The code below scores two documents. Document A is 100 terms long, with "postgres" 3 times and "database" once. Document B is 400 terms long, with "postgres" 6 times and "database" 4 times.

import math

def term_score(tf, n_docs, n_containing, doc_len, avg_len, k1=1.2, b=0.75):
    idf = math.log(1 + (n_docs - n_containing + 0.5) / (n_containing + 0.5))
    norm = k1 * (1 - b + b * doc_len / avg_len)
    return idf * tf * (k1 + 1) / (tf + norm)

def doc_score(tf_postgres, tf_database, doc_len):
    return (term_score(tf_postgres, 1000, 10, doc_len, 200)
            + term_score(tf_database, 1000, 300, doc_len, 200))

print(round(doc_score(3, 1, 100), 2))  # Document A
print(round(doc_score(6, 4, 400), 2))  # Document B

Output:

9.53
9.16

Document A wins. Its length factor is 1 − 0.75 + 0.75 × 100/200 = 0.625, so its "postgres" term scores 3 × 2.2 / (3 + 0.75) ≈ 1.76, which times IDF 4.56 is about 8.02. Document B has more of both words, but it is three times as long, so its repeats saturate.

Under naive TF-IDF, which multiplies TF by IDF with no saturation or length correction, B would win easily, at about 32 against about 15 for A. BM25 is designed to stop long documents from winning by repetition.

Common mistakes

• Treating BM25 as TF-IDF with a new name. Saturation and length normalization change the ranking, as the example shows.
• Assuming longer documents always rank higher. BM25 corrects for length on purpose.
• Hand-tuning boosts without measuring them. Field boosts such as title^3 change the ranking, so test them on judged queries.

Check yourself

1. Under naive TF-IDF, which document wins the example, and what does BM25 change?

Answer: Document B wins, at about 32 to 15. BM25 saturates repeats and corrects for length, so A wins 9.53 to 9.16.

2. Why is "postgres" worth about four times as much as "database" in the example?

Answer: Its IDF is 4.56, against 1.20 for "database", because it appears in far fewer documents.

Key takeaways

• BM25 sums one weighted term score per query word.
• IDF gives rare words more weight.
• Saturation stops repeated words from dominating.
• Length normalization keeps long documents from winning by volume.

Further learning

Next, see how scoring works when the index is split across many machines in distributed search.

Practical BM25, Part 2: The BM25 Algorithm and its VariablesBM25 is the default similarity ranking (relevancy) algorithm in Elasticsearch. Learn more about how it works by digging into the equation and exploring the concepts behind its variables.Elastic Blog