BM25 Algorithm for Text Retrieval

BM25 (Best Matching 25)

BM25 is a probabilistic ranking function that scores how relevant a document is to a query from three signals: how rare the query terms are, how often they appear in the document, and how long the document is. It is the default scorer in Elasticsearch and Lucene, and it stays competitive with neural retrievers on keyword search — which is why it remains the sparse half of most hybrid systems.

Try it: BM25 decomposed

Type a query, click a result to see the formula compute term-by-term, and drag the two knobs — k1 (term saturation) and b (length normalization). The ranking and every number update live; it is real BM25 over the documents shown.

Three things drive every score: a rare term outweighs a common one (try quick fox — the rarer "quick" beats "fox" even against five repeats), repeating a term has diminishing returns (raise k1), and a short document beats a long one with the same term count (raise b).

The formula

The BM25 score of document D for query Q sums one contribution per query term:

Inverse document frequency weights each term by rarity, with +0.5 smoothing so it never goes negative:

where N is the number of documents and n(q_i) is how many contain qᵢ.

The three forces

Term-frequency saturation (k1)

Unlike TF-IDF's linear term frequency, BM25 saturates: the first occurrence of a word matters most, and each repeat adds less. The k1 knob sets how fast it flattens.

def saturation(tf, k1):
    # → tf=0:0, tf=1:1.0, then diminishing returns toward k1+1
    return tf * (k1 + 1) / (tf + k1)

k1 = 0 ignores repetition entirely (a binary "contains the term"); larger k1 keeps rewarding it. This is what stops keyword stuffing from dominating.

Document-length normalization (b)

Longer documents accumulate term matches just by being long. The b knob discounts that by scaling the saturation denominator with the document's length ratio:

def length_factor(doc_len, avgdl, b):
    return 1 - b + b * (doc_len / avgdl)   # b=0 → 1 (off); b=1 → full

A document shorter than average gets a boost; a longer one gets a penalty. At b = 0 length is ignored; b = 0.75 is the standard balance.

Inverse document frequency

IDF is the multiplier on every term and is unaffected by the knobs. A term in nearly every document carries almost no signal; a term in one document carries a lot — which is why, in the playground, the rare "quick" out-contributes the common "fox".

Implementation

The whole algorithm is a precomputed index plus the scoring sum:

import math
from collections import Counter

class BM25:
    def __init__(self, corpus, k1=1.2, b=0.75):
        self.k1, self.b = k1, b
        self.docs = [doc.lower().split() for doc in corpus]
        self.doc_len = [len(d) for d in self.docs]
        self.avgdl = sum(self.doc_len) / len(self.docs)
        self.N = len(self.docs)
        self.df = Counter(t for d in self.docs for t in set(d))

    def idf(self, term):
        n = self.df.get(term, 0)
        return math.log(1 + (self.N - n + 0.5) / (n + 0.5))

    def score(self, query, i):
        tf = Counter(self.docs[i])
        B = 1 - self.b + self.b * self.doc_len[i] / self.avgdl
        s = 0.0
        for term in query.lower().split():
            f = tf.get(term, 0)
            if f:
                s += self.idf(term) * f * (self.k1 + 1) / (f + self.k1 * B)
        return s

To search, score the documents returned by an inverted index (the term → postings map that lets BM25 touch only documents containing a query word) and keep the top-k.

Variants

• BM25F — for multi-field documents (title, body, abstract): combine per-field term frequencies with field weights before saturation, so a title match counts more than a body match.
• BM25+ — adds a lower bound δ to each term's contribution, fixing a bias where very long documents could be over-penalized to near zero.
• Learned sparse (SPLADE) — a transformer predicts term weights across the vocabulary, giving BM25-style sparse vectors with dense-like semantics that still drop into an inverted index.

BM25 vs dense embeddings

The two are complementary — see sparse vs dense for the head-to-head and hybrid retrieval for fusing them.

Tuning and pitfalls

• Parameters by domain. Long documents (legal) like higher b; short texts (tweets, product titles) like low k1 and b. Grid-search k1 ∈ [0.5, 2.0], b ∈ [0, 1] against labeled relevance (nDCG).
• Vocabulary mismatch. BM25 cannot match synonyms — pair it with stemming, query expansion, or a dense retriever.
• Negative IDF. With the unsmoothed log(N/n) form, terms in more than half the documents go negative; the +0.5 … +1 smoothing above avoids it.

Production

Elasticsearch and Lucene ship BM25 as the default similarity, with k1 and b tunable per field:

{
  "settings": {
    "index": {
      "similarity": {
        "tuned_bm25": { "type": "BM25", "k1": 1.2, "b": 0.75 }
      }
    }
  },
  "mappings": {
    "properties": {
      "content": { "type": "text", "similarity": "tuned_bm25" }
    }
  }
}

At scale, BM25 stays cheap: shard the inverted index, cache IDF values and hot queries, and use top-k approximation (e.g. WAND / block-max) to skip documents that cannot enter the result set.

Conclusion

BM25's staying power comes from doing three simple things well — weighting by rarity, saturating term frequency, and normalizing for length — with two interpretable knobs and no training. Master those three forces and you understand not just BM25, but the sparse half of every modern hybrid search system.

Related concepts