Explore the BM25 scoring algorithm and document length normalization implemented from first principles in Tiny Search Engine (Inverted Index, Compression & BM25).
Under the Hood: Why Okapi BM25 Replaced TF-IDF
While TF-IDF laid the foundation for information retrieval, raw-TF variants grow linearly with repetition, while the logarithmically damped TF taught in the previous lesson grows more slowly. BM25 makes saturation and document-length normalization explicit and tunable. Okapi BM25 (Best Matching 25) introduced non-linear term frequency saturation and tunable document length penalties, becoming the default similarity in Lucene, Elasticsearch and OpenSearch; Vespa offers it as the bm25 rank feature, though its default text ranking is nativeRank.
The BM25 Mathematical Formula
BM25(D, Q) = Σ IDF(qᵢ) × [ (f(qᵢ, D) × (k₁ + 1)) / (f(qᵢ, D) + k₁ × (1 - b + b × (|D| / avgdl))) ]BM25 Term Frequency Saturation Curve
Under the Hood: The Parameters k₁ and b
- Term Saturation Parameter
k₁(Default: ≈ 1.2): Calibrates how quickly the term frequency score saturates. As the count of a keyword in a document increases, its incremental score addition diminishes, preventing keyword-stuffed spam pages from winning ranking. - Document Length Normalization
b(Default: ≈ 0.75): Penalizes long documents. If a 100,000-word book mentions "Kafka" 5 times, it is far less relevant than a 50-word tweet that mentions "Kafka" 5 times. Whenb = 1.0, the score is fully scaled by length; whenb = 0, length normalization is disabled.
Worked example: saturation and length in numbers
Use the defaults k1 = 1.2 and b = 0.75, with average document length avgdl = 100 terms. The per-term TF component is f x (k1 + 1) divided by f + k1 x (1 - b + b x dl / avgdl). Its ceiling is k1 + 1 = 2.2.
| Term count f | Short doc, 50 terms | Average doc, 100 terms | Long doc, 1,000 terms |
|---|---|---|---|
| 1 | 1.26 | 1.00 | 0.21 |
| 3 | 1.76 | 1.57 | 0.54 |
| 10 | 2.05 | 1.96 | 1.14 |
| 100 | 2.19 | 2.17 | 2.02 |
Two lessons: going from 10 to 100 mentions barely moves the score, so keyword stuffing stops paying off; and a single mention in a 1,000-term document is worth about one fifth of a mention in an average document.
Multiply by IDF. Lucene uses IDF = ln(1 + (N - n + 0.5) / (n + 0.5)). For N = 1,000,000 and n = 1,000 documents containing the term, IDF is about 6.9; for a term in 400,000 documents it is about 0.4. The rare term still dominates.
Tuning trade-offs
| Setting | Effect | Good for |
|---|---|---|
| Lower k1, around 0.5 | Saturates after one or two mentions | Short fields such as titles and product names |
| Higher k1, around 2 | Repetition keeps helping longer | Long technical documents |
| b = 0 | No length penalty | Fields with uniform length, tags |
| b = 1 | Full length normalisation | Corpora mixing tweets and books |
Production notes
- BM25 has been Lucene's default similarity since Lucene 6 and Elasticsearch 5. Lucene 8 dropped the constant (k1 + 1) factor from the numerator; this rescales scores but does not change ranking.
- Multi-field search, for example title and body, needs care: BM25F-style combination or per-field boosts, because each field has its own avgdl.
- Per-shard statistics mean the same document can score slightly differently on different shards until term stats converge.