BM25 Scoring

Background

BM25 is the sparse, term-weighted retrieval scorer that powers Lucene, Elasticsearch, OpenSearch, and the lexical half of every production hybrid-RAG system. Where dense embeddings excel at semantic similarity, BM25 dominates on rare named entities, error codes, version numbers, and any query whose target shares specific vocabulary — without any model training. Knowing it cold is table stakes for a production-RAG / search interview.

Problem statement

Implement bm25_score(query, doc, corpus, k1=1.5, b=0.75) returning the BM25 score for a single $(query, doc)$ pair, computed against the supplied corpus (used to derive IDF and the average document length). Use the Robertson-Sparck-Jones / Lucene IDF variant (always non-negative) and the standard length-normalised TF:

$$\text{BM25}(q, d) \;=\; \sum_{t \in q}\; \text{idf}(t)\;\cdot\;\frac{f_{t,d}\,(k_1 + 1)}{f_{t,d} + k_1\bigl(1 - b + b\,\tfrac{|d|}{\overline{|d|}}\bigr)}$$

with

$$\text{idf}(t) \;=\; \ln\!\Bigl(1 + \tfrac{N - \text{df}(t) + 0.5}{\text{df}(t) + 0.5}\Bigr)$$

where $f_{t,d}$ is the count of term $t$ in document $d$, $|d|$ is $d$'s length in tokens, $\overline{|d|}$ is the corpus mean document length, $N$ is the corpus size, and $\text{df}(t)$ is the number of documents containing $t$.

Input

• query — list[str] of query tokens. Duplicates count once (BM25 sums per unique query term).
• doc — list[str] of document tokens (the candidate being scored).
• corpus — list[list[str]] of every document used to derive IDF and $\overline{|d|}$. Must contain doc if doc is part of the indexed corpus (otherwise the IDF underweights it).
• k1 — float, term-frequency saturation knob (typical $[1.2, 2.0]$; default $1.5$).
• b — float, length-normalisation strength in $[0, 1]$ (default $0.75$). $b = 0$ disables length normalisation; $b = 1$ enforces it fully.

Output

Returns a Python float — the BM25 score for (query, doc). Larger is better. Returns 0.0 when no query term appears in doc or the query is empty.

Examples

Example 1 — rare-term query lights up the doc that contains it

Input:
  query  = ["cat"]
  corpus = [["the","cat","sat","on","the","mat"],
            ["the","dog","ran","fast"],
            ["cats","love","milk"]]
  doc    = corpus[0]
Output: ~0.8361

Explanation: $N = 3$, $\text{df}(\text{"cat"}) = 1$, so $\text{idf} \approx 0.981$. With $f = 1$, $|d| = 6$, $\overline{|d|} = 13/3$, the normalised TF is $\approx 0.852$. Product $\approx 0.836$.

Example 2 — common term has low IDF

Input:
  query  = ["the"]
  corpus = same as Example 1
  doc    = corpus[0]
Output: ~0.5975

Explanation: "the" appears in 2 of 3 docs, so $\text{idf} \approx 0.470$, lower than the rare-term case despite the higher TF.

Example 3 — query term absent from the doc

Input:
  query = ["dog"]
  doc   = corpus[0]   # the cat-sat-on-mat doc
Output: 0.0

Explanation: no query term appears in doc, so every per-term contribution is 0.

Constraints

• Score is the sum over unique query terms — duplicates in query don't double-count.
• Match terms by exact equality (no stemming, no lowercasing; the caller does that upstream).
• If corpus is empty or query is empty, return 0.0 without a division-by-zero error.
• Return a Python float. Tests compare with atol ≈ 1e-6.

Notes

• Why this IDF form. The $\ln(1 + \dots)$ wrapping is the Lucene / RSJ variant — non-negative everywhere, unlike the classical $\ln\!\bigl(\tfrac{N - \text{df} + 0.5}{\text{df} + 0.5}\bigr)$ which goes negative when more than half the corpus contains the term. Production search engines all use the $\ln(1 + \dots)$ form for that reason.
• TF saturation. The $(k_1 + 1)/(f + k_1(\dots))$ term means doubling the in-document term frequency does not double the score — a doc that mentions the query term 20 times scores only marginally higher than one that mentions it 5 times. That's the "saturation" that prevents keyword-stuffed pages from winning.
• Length normalisation. The $b\,|d|/\overline{|d|}$ factor penalises long documents for having more chances to match a term by accident. Set $b = 0$ to remove the penalty entirely.