BM25 Scoring

Start from brute force

The obvious approach applies the formula literally, and it is what the reference does: for every document and every query term, scan all n documents to count df, then count tf with d.count(term). It is correct because it computes exactly the stated sum. With T total tokens it costs O(n·q·T) time for q query terms, since each df is a full pass over the corpus, and O(1) extra space. The waste is that df and idf depend only on the term, never on the document being scored, so the same corpus scan is repeated once per document.

The approach

Split the formula by what each part depends on. idf = ln(1 + (n − df + 0.5) / (df + 0.5)) needs only the term, so compute it once per query term. The length factor k1 · (1 − b + b · len/avglen) needs only the document, so compute it once per document. Each (document, term) pair is then one tf lookup in that document’s token counts.

Saturation comes from tf sitting in both the numerator and the denominator of tf·(k1+1) / (tf + K): the factor is 0 at tf = 0, equals exactly 1 for one occurrence in an average-length document, and climbs toward k1 + 1 = 2.5 without reaching it. The reference uses these names (n, avglen, df, idf, tf, denom) but computes df inside for d in docs. Moving the df and idf lines above that loop gives the optimal bound and changes no score.

Walk through an example

Scoring query = ["cat", "sat"] over three documents (n = 3, avglen = 8/3, “cat” in two of them, “sat” in one) returns [1.374, 0.0, 0.730]: the short d2 says “cat” twice, yet d0 wins by also matching the rarer “sat”.

Complexity

With df and idf hoisted and each document’s tokens counted once, scoring costs O(T + n·q) time for T total tokens, with O(q) space for the idf table plus one document’s counts. The literal version recomputes df for every document: O(n·q·T) time, O(1) extra space. An inverted index lets a query touch only documents containing its terms.

Edge cases to test

• A term in every document: bm25_scores(["the"], [["the","cat","sat"], ["the","dog","ran"]]) returns [0.1823…, 0.1823…]. The +1 inside the log keeps idf = ln 1.2 positive; the classic ln((N − df + 0.5) / (df + 0.5)) turns negative whenever df is more than N/2.
• A term in no document: ["zebra"] on the same docs returns [0.0, 0.0]. Its idf is a finite ln 6 and tf = 0 zeroes it, so no special case is needed.
• A repeated query term counts twice: ["cat", "cat"] on the first example returns [1.3862…, 0.0], double the single-term score, because the reference sums over the query list as given.
• An empty document scores 0: bm25_scores(["cat"], [[], ["cat"]]) returns [0.0, 0.478…]. If every document is empty, avglen is 0 and the reference raises ZeroDivisionError; an empty docs list raises it too.
• Membership is exact: term in doc tests list equality, so "cat" does not match "cats". Tokenizing and stemming happen before BM25, not inside it.

Common mistakes

• Using raw term frequency without saturation, so a term repeated many times in a long document dominates unfairly.
• Dropping the document-length normalization — long documents then score artificially high.
• Mishandling IDF edge cases (a term in every document, or in none).

Follow-ups an interviewer asks next

How do you make this fast over a million documents?

Build an inverted index once: for each term, its postings list of (document, tf) pairs, plus every document’s length. A query then reads only its own terms’ postings, and df is a postings-list length. Engines go further with dynamic pruning such as WAND and block-max WAND, which skip documents whose best possible score cannot enter the current top k.

How would you choose k1 and b?

Tune them against labeled queries. k1 = 0 reduces tf to presence or absence, and a large k1 approaches raw tf; b = 0 ignores length and b = 1 normalizes fully. A common starting range is k1 from 1.2 to 2.0 with b = 0.75, then grid-search on your own data.

How do you combine BM25 with vector search?

Run both retrievers and fuse the ranked lists. Reciprocal Rank Fusion gives each document the sum of 1 / (60 + rank) over the lists, which needs no score calibration. Blending raw scores linearly also works but needs normalization and tuning, because BM25 scores have no fixed range and grow with query length, while cosine scores sit in [−1, 1].

Where this shows up

BM25 is the default lexical ranking function in production search (Lucene, Elasticsearch, OpenSearch) and the lexical half of hybrid retrieval. It nails the exact identifiers, names, SKUs, and error codes that embeddings blur, which is why serious RAG systems run BM25 and vector search together and fuse the results.

Reference solution

import math

def bm25_scores(query, docs, k1=1.5, b=0.75):
    n = len(docs)
    avglen = sum(len(d) for d in docs) / n
    scores = []
    for d in docs:
        s = 0.0
        for term in query:
            df = sum(1 for doc in docs if term in doc)
            idf = math.log(1 + (n - df + 0.5) / (df + 0.5))
            tf = d.count(term)
            denom = tf + k1 * (1 - b + b * len(d) / avglen)
            s += idf * tf * (k1 + 1) / denom
        scores.append(s)
    return scores


print(bm25_scores(['cat'], [['the','cat','sat'], ['the','dog','ran']]))

function bm25Scores(query: string[], docs: string[][], k1 = 1.5, b = 0.75): number[] {
  const n = docs.length;
  const avglen = docs.reduce((a, d) => a + d.length, 0) / n;
  return docs.map((d) => {
    let s = 0;
    for (const term of query) {
      const df = docs.filter((doc) => doc.includes(term)).length;
      const idf = Math.log(1 + (n - df + 0.5) / (df + 0.5));
      const tf = d.filter((t) => t === term).length;
      const denom = tf + k1 * (1 - b + (b * d.length) / avglen);
      s += (idf * tf * (k1 + 1)) / denom;
    }
    return s;
  });
}

console.log(bm25Scores(['cat'], [['the','cat','sat'], ['the','dog','ran']]));