BM25: The Algorithm That Refuses to Die

BM25 is a ranking function from 1994 that is still the default similarity in Lucene, still the lexical half of most hybrid retrieval systems, and still the baseline that new dense retrievers are expected to beat and sometimes do not. That is a strange thing to be true of a thirty-year-old formula, and the reasons are worth understanding.

Where it comes from

BM25 — the name is short for “Best Match 25”, the twenty-fifth in a series of weighting experiments — came out of the Okapi project at City University London and was described in Okapi at TREC-3 (Robertson, Walker, Jones, Hancock-Beaulieu and Gatford, 1994). It is not a heuristic someone tuned; it is a practical approximation derived from the probabilistic relevance framework, which asks directly for the probability that a document is relevant given the query.

Its staying power is partly institutional. Lucene made BM25 its default similarity in version 6 (2016), which means Elasticsearch, OpenSearch and Solr all default to it, which means a large share of the world’s text search has been BM25 for a decade whether or not anyone chose it.

The two things the formula fixes

Start from TF-IDF and ask what is wrong with it. Two things, and BM25 is exactly the fix for both.

Term frequency should saturate. In TF-IDF, a document mentioning hurricane forty times scores four times one that mentions it ten times. That is not how relevance works: the tenth mention tells you very little that the third did not. BM25 replaces raw frequency with tf / (tf + k1)-shaped saturation, so the contribution rises steeply for the first few occurrences and then flattens towards an asymptote. Keyword stuffing stops paying.

Length should be discounted, but not eliminated. A long document contains more of every term, so it wins on raw counts without being more relevant. Pure length normalisation over-corrects and makes short documents win everything. BM25 interpolates between the two with a parameter, so you can tune how much a document’s length relative to the collection average is held against it.

The scoring function, with the standard notation, is the sum over query terms of IDF(t) × (tf × (k1 + 1)) / (tf + k1 × (1 − b + b × dl/avgdl)). Everything in it is one of those two ideas plus the same inverse document frequency TF-IDF uses. There is no learning, no training data and no corpus-specific fitting beyond counting document frequencies, which is precisely why it behaves the same on a corpus it has never seen.

The BEIR result, stated carefully

The claim that BM25 “still beats vectors” circulates without a source, so here is the source. BEIR — A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models, Thakur, Rücklé, Srivastava and Gurevych, NeurIPS Datasets and Benchmarks, 2021 — assembled eighteen retrieval datasets across different domains and evaluated a range of lexical, dense, sparse and re-ranking models on all of them without in-domain training.

The headline finding was that BM25 is a remarkably strong zero-shot baseline: dense retrievers that outperformed it on the dataset they were trained on frequently failed to do so when moved to a new domain, and the systems that reliably beat BM25 across the board were re-ranking pipelines, which are considerably more expensive to run.

Two qualifications keep this honest. First, it is a 2021 result and embedding models have improved since; treat it as evidence that out-of-domain generalisation is the hard part, not as a current scoreboard. Second, the finding is about zero-shot transfer. With in-domain training data, dense retrieval wins comfortably. The practical reading is that if you have no labelled data for your domain — which is the normal situation — a lexical baseline is not a concession, it is a competitive system you can build in an afternoon, and it is the thing your dense retriever must actually beat before you ship it.

k1 and b, and how to set them

The honest advice on tuning: do not, unless you have relevance judgements. Without labelled query-document pairs you cannot tell whether a parameter change helped, and the defaults were chosen against TREC collections and are decent everywhere. If you do have judgements, a grid over k1 in 0.5 to 2.0 and b in 0.3 to 0.9 covers the useful range and takes minutes, because scoring is cheap.

Where it plainly loses

BM25 matches terms. Everything it cannot do follows from that: a query and a document that share no vocabulary score zero, no matter how plainly they mean the same thing. Cross-language retrieval is impossible. Paraphrased questions — how do I cancel against a document titled ending your subscription — fail exactly. Long natural-language questions dilute across many low-IDF terms. And it cannot use the ordering or structure of the query at all.

The resolution in practice is not to pick. Run both, and fuse the two ranked lists — reciprocal rank fusion (Cormack, Clarke and Buettcher, SIGIR 2009) is the standard method because it needs no score calibration between systems, only their rank orders. That is what hybrid search is, and it works because the two systems fail on disjoint queries. Adding a cross-encoder re-ranker over the fused top-k is the third stage, and it is the one BEIR found actually dominated.