BM25: Lexical RankingOpen in Colab

BM25: Lexical Ranking

BM25 (Best Matching 25, from the Okapi project) is the ranking function that has powered keyword search for decades. It is the default in Lucene, Elasticsearch, and OpenSearch, and the "sparse" half of most hybrid RAG retrievers. It scores a document against a query using only term overlap: no embeddings, no training, no neural network. Given a query, it ranks every document by a sum of per-term weights that reward matching rare words, reward repeated matches with diminishing returns, and correct for document length.

It is worth understanding precisely because it is an absurdly strong baseline. A well-tuned BM25 index often matches or beats a dense retriever on exact-match queries (names, error codes, IDs, rare jargon) at a tiny fraction of the cost, which is exactly why production systems fuse the two.

From TF-IDF to BM25

Classic TF-IDF scores a query term tt in document dd as tf(t,d)⋅idf(t)\text{tf}(t, d) \cdot \text{idf}(t) — raw term frequency times inverse document frequency. Two problems:

  1. Term frequency grows linearly and unboundedly. A document that says "cat" 100 times looks 100× more relevant than one that says it once. In reality, relevance saturates — the 10th mention adds little over the 2nd.
  2. Long documents win by accident. A long document repeats every term more often, so it out-scores a short, focused one for no good reason.

BM25 fixes both with two ideas: a saturation curve on term frequency, and an explicit length-normalization knob.

The formula

For a query Q={q1,…,qn}Q = \{q_1, \dots, q_n\} and document dd:

BM25(Q,d)=∑i=1nIDF(qi)⋅f(qi,d) (k1+1)f(qi,d)+k1(1−b+b ∣d∣avgdl)\text{BM25}(Q, d) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, d)\,(k_1 + 1)}{f(q_i, d) + k_1\left(1 - b + b\,\dfrac{|d|}{\text{avgdl}}\right)}

where

  • f(qi,d)f(q_i, d) — the raw count of term qiq_i in document dd,
  • ∣d∣|d| — the document length in words, and avgdl\text{avgdl} — the average document length across the corpus,
  • k1k_1 — the saturation parameter (typically 1.21.2–2.02.0),
  • bb — the length-normalization parameter (typically 0.750.75),
  • IDF(qi)\text{IDF}(q_i) — the inverse document frequency of the term (below).

The IDF uses the probabilistic (Robertson–Spärck-Jones) form, with NN documents and n(qi)n(q_i) containing the term:

IDF(qi)=ln⁡ ⁣(N−n(qi)+0.5n(qi)+0.5+1)\text{IDF}(q_i) = \ln\!\left(\frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} + 1\right)

The +1+1 inside the log keeps IDF non-negative even for very common terms (a term in more than half the corpus would otherwise go negative).

Reading the two knobs

k1k_1: term-frequency saturation. Look at the fraction: as f(qi,d)→∞f(q_i, d) \to \infty, the term score approaches its ceiling IDF(qi)⋅(k1+1)\text{IDF}(q_i)\cdot(k_1 + 1). Small k1k_1 saturates fast (presence ≈ enough); large k1k_1 keeps rewarding repeats. At k1=0k_1 = 0 the term frequency drops out entirely and BM25 degenerates to a pure binary IDF score.

Why saturation matters

The saturation curve is BM25's defining feature. The first occurrence of a rare query term should move the ranking a lot; the twentieth should barely move it. A linear TF (plain TF-IDF) lets keyword-stuffed documents dominate — BM25's diminishing returns make it robust to that.

bb: length normalization. The denominator scales k1k_1 by (1−b+b ∣d∣avgdl)\left(1 - b + b\,\frac{|d|}{\text{avgdl}}\right). At b=0b = 0 length is ignored entirely; at b=1b = 1 scores are fully normalized by relative length, so a document twice as long needs twice as many matches to score the same. b=0.75b = 0.75 is the standard compromise — penalize length, but not brutally.

A worked score

Corpus of N=10N = 10 documents, avgdl=12\text{avgdl} = 12 words. Query: "neural retrieval". Take a document dd with ∣d∣=9|d| = 9 words containing "neural" 3× and "retrieval" 1×. Say "neural" appears in n=4n = 4 docs and "retrieval" in n=2n = 2. Use k1=1.5k_1 = 1.5, b=0.75b = 0.75.

First the IDFs:

IDF(neural)=ln⁡ ⁣(10−4+0.54+0.5+1)=ln⁡(2.44)≈0.89\text{IDF}(\text{neural}) = \ln\!\left(\tfrac{10 - 4 + 0.5}{4 + 0.5} + 1\right) = \ln(2.44) \approx 0.89 IDF(retrieval)=ln⁡ ⁣(10−2+0.52+0.5+1)=ln⁡(4.40)≈1.48\text{IDF}(\text{retrieval}) = \ln\!\left(\tfrac{10 - 2 + 0.5}{2 + 0.5} + 1\right) = \ln(4.40) \approx 1.48

The length factor is (1−0.75+0.75⋅912)=0.8125\left(1 - 0.75 + 0.75 \cdot \tfrac{9}{12}\right) = 0.8125, so k1⋅0.8125=1.219k_1 \cdot 0.8125 = 1.219.

"neural" (f=3f = 3):   0.89⋅3 (2.5)3+1.219=0.89⋅7.54.219≈1.58\;0.89 \cdot \dfrac{3 \,(2.5)}{3 + 1.219} = 0.89 \cdot \dfrac{7.5}{4.219} \approx 1.58

"retrieval" (f=1f = 1):   1.48⋅1 (2.5)1+1.219=1.48⋅2.52.219≈1.67\;1.48 \cdot \dfrac{1 \,(2.5)}{1 + 1.219} = 1.48 \cdot \dfrac{2.5}{2.219} \approx 1.67

BM25(Q,d)≈1.58+1.67=3.25\text{BM25}(Q, d) \approx 1.58 + 1.67 = 3.25

Notice the single-occurrence rare term ("retrieval") contributes more than three occurrences of the commoner one ("neural") — saturation plus IDF working together. That is the behavior a linear TF-IDF would get wrong.

Watch it rank

One document scored by hand shows the formula; ranking a corpus shows what the formula is for. Step through BM25 scoring five documents for the query "neural retrieval" — IDF first, then each document term by term, then the final ordering. (This corpus is its own worked example, so its NN, avgdl\text{avgdl} and IDFs differ from the hand-worked numbers above.)

BM25 — scoring and ranking a corpus, term by term

1/21

Five short documents, query "neural retrieval". BM25 needs only three corpus statistics: the number of documents N = 5, the average document length avgdl = 6.8, and each term's document frequency. No training, no embeddings.

python
1corpus = [d.split() for d in DOCS] # 5 short docs
2query = ["neural", "retrieval"]
3k1, b = 1.5, 0.75
4
5N = len(corpus)
6avgdl = sum(len(d) for d in corpus) / N
7
8def idf(term):
9 # document frequency of the term
10 n = sum(1 for d in corpus if term in d)
11 return log((N - n + 0.5) / (n + 0.5) + 1)
12
13def bm25(query, d):
14 score = 0.0
15 for term in query:
16 f = d.count(term)
17 if f == 0:
18 continue # no match, no contribution
19 # length normalization
20 norm = 1 - b + b * len(d) / avgdl
21 score += idf(term) * (f * (k1 + 1)) / (f + k1 * norm)
22 return score
23
24ranked = sorted(corpus, key=lambda d: -bm25(query, d))
state
corpus — N = 5, avgdl = 6.8
doc|d|neuralretrievalscore
d1511—
d2520—
d31312—
d4510—
d5600—

Note d3: it contains the query terms most often (neural ×1, retrieval ×2) but is by far the longest document. Watch whether that wins or loses.

Watch BM25 rank five documents for the query "neural retrieval". The two ideas BM25 adds to TF-IDF are visible in the numbers: IDF makes one match on the rare "retrieval" outweigh two matches on the common "neural", and the length factor drops the long d3 below the short d1 despite d3 matching more terms. The last step re-runs everything with b = 0 so you can see the long document win the moment length normalization is removed.

Both of BM25's corrections change the answer here, and you can watch each one do it:

  • IDF. "neural" appears in 4 of 5 documents and "retrieval" in 2, so one match on "retrieval" is worth roughly 3× one match on "neural". d1's single rare match beats d2's two common ones.
  • Length normalization. d3 contains more query-term occurrences than d1 but is 2.6× longer, so its length factor exceeds 1 and shrinks every contribution — it lands second. The final step re-scores the same corpus with b=0b = 0 and d3 jumps to first, which is exactly the keyword-stuffing failure bb is there to prevent.

BM25 vs dense embeddings

BM25 (lexical / sparse)Embeddings (semantic / dense)
Matchesexact tokens (& stems)meaning / paraphrase
"car" vs "automobile"miss (no shared token)hit
Rare IDs, codes, namesexcellentoften poor
Training needednoneembedding model
Indexinverted indexANN vector index
Costvery cheapembedding + ANN
Out-of-domain termsrobustcan drift

Neither dominates. Embeddings win on synonymy and paraphrase; BM25 wins on precise tokens and unseen jargon, with zero training and near-zero cost. This is why hybrid search fuses both scores — commonly with Reciprocal Rank Fusion (RRF), which combines the two ranked lists by ∑r1k+rankr(d)\sum_r \frac{1}{k + \text{rank}_r(d)} (a small constant k≈60k \approx 60) and needs no score calibration between the incomparable BM25 and cosine scales.

Common mistakes

  1. Comparing BM25 scores across queries. BM25 is a within-query ranking score, not a calibrated probability — a score of 12 for one query is not "more relevant" than 8 for another. Only the order within one query is meaningful.
  2. Skipping tokenization/normalization. BM25 matches surface tokens, so lowercasing, stemming/lemmatization, and stop-word handling directly change recall. Mismatched analyzers between indexing and querying silently tank results.
  3. Leaving k1k_1/bb at defaults for atypical corpora. Very short docs (tweets, titles) or very long ones (manuals) often want different bb; tune on labeled queries.
  4. Expecting semantic matches. BM25 will never connect "heart attack" to "myocardial infarction" — that gap is exactly what the dense half of a hybrid retriever is for.
  5. Feeding negative IDF into the sum. Use the +1+1-inside-log form (above) so ultra-common terms don't subtract from a document's score.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
BM25: Lexical RankingVector Databases & ANN In…HNSW: Hierarchical Naviga…Retrieval-Augmented Gener…RAG Architectures: Which …Embeddings & Semantic Sea…