Awesome Search KG

BM25

5 min read

BM25

Definition

BM25 (Best Match 25) is the dominant lexical retrieval algorithm — the scoring function behind Elasticsearch’s default relevance, Solr, Lucene, and most production search engines. It is a probabilistic term-frequency weighting model that improves on TF-IDF by accounting for document length and term-frequency saturation.

Formula

BM25(d,q) = Σ_{t∈q} IDF(t) × (tf(t,d) × (k1+1)) / (tf(t,d) + k1×(1-b+b×|d|/avgdl))

Where:

  • tf(t,d) = term frequency of term t in document d
  • IDF(t) = inverse document frequency = log((N-n+0.5)/(n+0.5)+1)
  • |d| = document length in tokens
  • avgdl = average document length in the corpus
  • k1 ∈ [1.2, 2.0] = term frequency saturation parameter
  • b ∈ [0, 1] = document length normalization (typically 0.75)

Key Innovations Over TF-IDF

1. Term Frequency Saturation

In TF-IDF: score scales linearly with tf (10 occurrences = 10× weight of 1 occurrence).
In BM25: the k1 parameter saturates tf — going from 1 to 2 occurrences increases score a lot; going from 10 to 20 occurrences adds little.

Intuition: Mentioning “python” once signals relevance; mentioning it 50 times doesn’t mean 50× more relevant.

2. Document Length Normalization

The b parameter penalizes long documents. Without it, long documents would score higher simply because they contain more terms — even if they’re less dense with the topic.

b=0: no length normalization
b=1: full normalization
b=0.75: standard compromise

Parameters

BM25 parameters are tunable:

ParameterDefaultEffect
k1=1.2LowTerm saturation happens quickly
k1=2.0HighMore benefit from repeated terms
b=0.0—Ignore document length
b=1.0—Strong length normalization

Elasticsearch defaults: k1=1.2, b=0.75. Tuning can improve NDCG by 2–5%.

”BM25” in a results table is not one number

When a paper reports beating BM25, it beat somebody’s BM25. From Improving Zero-Shot Ranking with Vespa Hybrid Search - part two — k1=0.9, b=0.4, with the scoring function applied independently to title and text and the two combined linearly, against the BM25 figures published alongside BEIR:

DatasetPublished BM25Tuned BM25
TREC-COVID0.6560.690
HotpotQA0.6030.623
ArguAna0.3150.393
BEIR average0.4400.453

The ArguAna gap is a quarter of the baseline’s value. Two practical consequences: tune the lexical baseline before adding a neural component, since it is the cheapest gain on the table; and discount reported neural improvements measured against a default-configured BM25. The per-field scoring matters as much as the parameters — see Linear Score Combination and, for the multi-field generalization, BM25F below.

BM25F

BM25F (BM25 with Fields) extends BM25 to handle multi-field documents (title, body, URL):

  • Different field weights (title match more important than body match)
  • Field-specific length normalization

Essential for e-commerce (product name vs. description) and enterprise search (email subject vs. body).

Bayesian BM25 (BB25)

A probabilistic recasting by Doug Turnbull that converts a raw BM25 score into an estimate of P(relevant | score), so it can be combined with other probability-calibrated signals (embedding similarity, CTR, recency) without a hand-tuned mixing weight.

  • The BM25 score enters as a likelihood, passed through a sigmoid
  • A prior is derived from term frequency and field-length normalization
  • Bayes’ theorem gives the posterior probability of relevance
  • The sigmoid’s steepness and midpoint are fit from relevance labels; the midpoint is typically the corpus median BM25 score, making it collection-specific

See Bayesian BM25 for the full treatment, and Score Normalization for the alternative of rescaling scores rather than calibrating them.

DimensionBM25Semantic (Bi-Encoder)
Vocabulary mismatchFailsHandles
Exact term matchExcellentCan miss
SpeedVery fastSlower (ANN)
InterpretabilityHighLow
OOV termsFailsHandles

The standard combination: Hybrid Search (BM25 + bi-encoder).

Unboundedness, and Why It Matters in Fusion

BM25 has no upper bound. The same three properties that make it a good lexical ranker — term frequency, IDF, and length normalization — mean a short document repeating a distinctive term can emit an arbitrarily large score. Saturation via k1 damps the growth from repetition; it does not cap the score.

That is harmless when BM25 ranks alone, because only the ordering matters. It becomes a problem the moment BM25 is added to a bounded score such as cosine similarity, which sits in a narrow band typically well under 1: the unbounded branch can dominate the sum and the bounded one stops affecting the ranking. Normalize before combining — Linear Score Combination, Relative Score Fusion — or fuse on ranks instead (Reciprocal Rank Fusion).

A second, subtler bias shows up in the same setting. BM25’s ideal profile — short and repetitive — describes explanatory writing, while reference material tends to state a fact once inside a long document. When the reference is the thing that answers the query, BM25 systematically prefers the wrong document. Worked example: Hybrid Fusion Failure - BM25 Displacing Reference Documents.

People

Graph View

Backlinks