Information Retrieval1994foundational12 min read

Okapi at TREC-3

نظام Okapi في مسابقة TREC-3

Robertson, S. E. · Walker, S. · Jones, S. · Hancock-Beaulieu, M. M. · Gatford, M. — TREC

The problem

Early systems either treated linearly (so repeating a word 100 times made a document 100× more relevant) or ignored it entirely (binary presence/absence). Neither matched how relevance actually works. Long documents accumulated unfairly high scores simply by having more words. And common words like "the" drowned out rare, discriminative terms. There was no principled way to combine word importance, word frequency, and document length into a single ranking score.

The contribution

(Best Match 25): a term-weighting and document-ranking function derived from the probabilistic relevance framework. It scores each document by summing over query terms, where each term's contribution combines three factors: (1) IDF — how rare the term is across the collection, (2) a saturating term-frequency component controlled by parameter k₁ so the 10th occurrence matters far less than the 1st, and (3) document-length normalization controlled by parameter b, which penalizes long documents proportionally. The result is a simple, closed-form formula with only two free parameters that outperformed all prior methods on the TREC benchmarks and became the dominant baseline in information retrieval for the next three decades.

The impact

BM25 is the most widely deployed ranking formula in the history of search. Lucene, Elasticsearch, Solr, and virtually every search engine used BM25 or a close variant as their default scorer. It anchored the TREC competitions for years and remains the baseline every neural retrieval model (DPR, ColBERT, SPLADE) is measured against. Its influence extends to RAG pipelines, where BM25 often serves as the first-stage retriever even in systems dominated by dense embeddings. The ideas of term saturation and length normalization it formalized have become standard in information retrieval.

Imagine a librarian who helps you find the best book for your question. A naive approach counts how many times your keyword appears in each book — but a 500-page encyclopedia mentioning "climate" 20 times isn't more relevant than a 10-page research brief that uses "climate" on every page. And the word "the" appears everywhere, so it tells you nothing.

BM25 is the scoring system this librarian uses: it rewards rare words (a book mentioning "permafrost" is more telling than one mentioning "weather"), applies diminishing returns to repetition (the 5th mention matters less than the 1st), and adjusts for book length so a focused pamphlet and a sprawling textbook compete fairly.

The problem: raw word counts mislead

Before BM25, the dominant approach to ranking documents was TF-IDF — multiply how often a term appears in a document (Term Frequency) by how rare it is across the collection (). It was a breakthrough over pure Boolean matching, but it had two critical flaws:

Linear term frequency. If "neural" appears 20 times, TF-IDF scores it twice as high as 10 occurrences. But in reality, a document mentioning "neural" 10 vs 20 times is barely different in relevance — the first few mentions establish the topic, and further repetitions add diminishing evidence.
No length normalization. A 10,000-word survey paper naturally contains more occurrences of any word than a 500-word abstract. Raw TF-IDF systematically biases toward long documents, even when shorter ones are more focused and relevant.

The TREC evaluation campaigns in the early 1990s made these flaws painfully visible: retrieval systems were tested on large, realistic document collections for the first time, and length bias became a dominant source of error.

Open in Lab

Drag the term frequency slider to see how TF-IDF scores grow linearly while BM25 saturates.

The demo wakes as you arrive…

The idea: three forces of relevance

BM25 scores a document for a given query by summing one contribution per query term. Each contribution balances three forces — think of them as three questions the formula asks about each word:

1. How rare is this word? (IDF component) — A term appearing in 5 out of 1,000,000 documents is far more informative than one appearing in 500,000. The word "" tells you more about a document's topic than the word "system." BM25 uses the inverse document frequency to upweight rare, discriminative terms.

2. How often does it appear here? (Saturating TF component) — More occurrences signal stronger topicality, but with diminishing returns. The jump from 0 to 1 occurrence is huge (absent vs present). The jump from 10 to 11 is negligible. The parameter $k_1$ controls how quickly this saturation kicks in.

3. Is this document unusually long or short? (Length normalization) — A long document mentioning "neural" 5 times is less focused than a short one with 5 mentions. The parameter $b$ controls how much to penalize length: at $b = 0$ no normalization occurs; at $b = 1$ full normalization treats the document as if it were average length.

Open in Lab

Adjust k₁ and b to see how the three components interact for different documents.

The demo wakes as you arrive…

The formula: BM25 in full

Now that you understand what BM25 is trying to achieve — reward rare words, saturate repetition, and normalize for length — here is the formula that does it all in one line:

\text{BM25}(D, Q) = \sum_{t \in Q} \text{IDF}(t) \cdot \frac{f(t,D) \cdot (k_1 + 1)}{f(t,D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}

BM25 — the complete ranking formula — f(t,D) = term frequency of t in document D · |D| = document length · avgdl = average document length · k₁ ≈ 1.2–2.0 controls saturation speed · b ≈ 0.75 controls length normalization strength · IDF(t) = log((N − n(t) + 0.5) / (n(t) + 0.5)) where N = total docs, n(t) = docs containing t

Read it as an assembly line: for each query word, the formula stamps out a score that says "this word is this rare × this document uses it this intensely (accounting for length)." Sum those stamps and you have the document's total relevance score.

The denominator is the engine of saturation and normalization. When $f(t,D)$ is very large, the fraction approaches $(k_1 + 1)$ — a ceiling. When $b = 0.75$ and a document is twice average length, the effective term frequency is scaled down, as if the document had fewer mentions than it actually does.

Dissecting the components

Let's walk through each piece with a concrete example. Suppose we have a collection of 1,000,000 news articles and a user searches for "neural network ".

Open in Lab

Enter a query, set k₁ and b, and watch the BM25 score build up term by term.

The demo wakes as you arrive…

Where BM25 comes from: the 2-Poisson model

BM25 wasn't invented by trial and error — it has a principled derivation from probabilistic theory. The key insight is the concept of term eliteness: a document is either "about" a term (elite for it) or not. If a document is elite for "neural", the word appears frequently; if not, it appears rarely or not at all.

Robertson and Walker modeled this with the 2-Poisson model: term frequencies in elite documents follow one Poisson (with high mean $\mu_e$ ), and in non-elite documents follow another (with low mean $\mu_{ne}$ ). The mixture of these two Poissons produces the saturating behavior — as TF grows, the evidence that the document is elite approaches certainty, so additional occurrences add diminishing information.

The closed-form approximation to this mixture is exactly the BM25 TF component: $\frac{f \cdot (k_1 + 1)}{f + k_1}$ , where $k_1$ captures the ratio of the two Poisson means. This is not a heuristic — it is the principled outcome of asking "given this term frequency, how likely is this document to be elite for this term?"

Open in Lab

Toggle between elite and non-elite Poisson distributions. Watch how their mixture produces the BM25 saturation curve.

The demo wakes as you arrive…

How search engines use BM25

BM25 doesn't work alone — it operates within the infrastructure of an . Think of it as the back-of-book index at enormous scale:

For every term in the vocabulary, the index stores a posting list: the IDs of documents containing that term, along with each document's term frequency. When a query arrives, the search engine looks up each query term's posting list, computes the BM25 contribution for each document, and accumulates scores. Documents are then sorted by total score.

This is extremely efficient: instead of scanning every document (which could be billions), BM25 only touches documents that contain at least one query term. Combined with optimizations like early termination (stop scoring once no remaining document can beat the current top-k), BM25 can rank millions of documents in milliseconds.

Open in Lab

Type a query and step through how the inverted index looks up posting lists and accumulates BM25 scores.

The demo wakes as you arrive…

The formula in code

BM25 scoring — complete implementationpython

Simplified to show the idea — not the real implementation.

import math
from collections import Counter

def bm25_score(query_terms, doc_tf, doc_len, avg_doc_len,
               doc_freq, num_docs, k1=1.5, b=0.75):
    """Score a single document for a query using BM25.

    Args:
        query_terms: list of query words, e.g. ["neural", "network"]
        doc_tf: dict mapping term → frequency in this document
        doc_len: number of words in this document
        avg_doc_len: average document length across the collection
        doc_freq: dict mapping term → number of documents containing it
        num_docs: total number of documents in the collection
        k1: saturation parameter (higher = slower saturation)
        b: length normalization (0 = none, 1 = full)
    """
    score = 0.0
    for term in query_terms:
        # 1. IDF — how rare is this term?
        n = doc_freq.get(term, 0)
        idf = math.log((num_docs - n + 0.5) / (n + 0.5) + 1)

        # 2. Term frequency — how often does it appear here?
        tf = doc_tf.get(term, 0)

        # 3. Length normalization — adjust for document size
        norm = 1 - b + b * (doc_len / avg_doc_len)

        # Combine: saturating TF × IDF
        tf_component = (tf * (k1 + 1)) / (tf + k1 * norm)
        score += idf * tf_component

    return score

# That's it. This 8-line scoring function is what powers
# Elasticsearch, Lucene, Solr, and most search engines worldwide.
# The entire ranking model fits in a single for-loop.

BM25 vs dense retrieval: complementary, not competing

Modern retrieval has shifted toward models like DPR and ColBERT, which encode queries and documents as dense vectors and measure relevance via in embedding space. These models capture semantic similarity: they know that "automobile" and "car" are related even though they share no characters.

BM25, by contrast, is lexical: it only matches exact terms (or stems). It has no notion of synonymy or paraphrase. But it has crucial strengths that dense models still struggle to match:

Exact keyword matching. For product names, error codes, proper nouns, and technical terms, exact match is exactly what you want. Dense models sometimes fumble these.
Interpretability. You can look at BM25's score breakdown and see why a document ranked highly: which terms matched, with what IDF and TF. Dense models are opaque.
No training data needed. BM25 works out of the box on any text collection. Dense models need labeled relevance pairs or contrastive training.
Speed at scale. Inverted index lookup is sublinear; search for dense vectors, while fast, is harder to optimize.

The current best practice in production systems is hybrid retrieval: use BM25 as a first-stage retriever to quickly narrow millions of documents to thousands, then re-rank with a dense or model. This combines BM25's efficiency and exact-match precision with neural models' semantic understanding.

Open in Lab

Search the same query with BM25 (lexical) and a dense model (semantic). Notice when each approach wins.

The demo wakes as you arrive…

What BM25 enabled

1994
BM25 (Okapi at TREC-3)
Introduced the saturating TF + length normalization formula. Outperformed all prior methods in the TREC ad-hoc retrieval track.
2000
Lucene adopts BM25-style scoring
The open-source search library that would power Elasticsearch and Solr adopted TF-IDF initially, later switching to BM25 as its default similarity.
2004
BM25F — structured documents
Extended BM25 to weight different document fields (title, body, URL) separately, then combine them. Became the basis of web search ranking at Microsoft and beyond.
2019
DPR — Dense Passage Retrieval
First neural retrieval model to consistently outperform BM25, using BERT-encoded dense vectors. BM25 became the baseline to beat.
2020
ColBERT — late interaction retrieval
Kept per-token representations instead of a single vector, achieving both efficiency and semantic matching. Still benchmarked against BM25.
2020
REALM — retrieval-augmented language model
Showed that pre-training a language model with a retriever produces better QA performance. BM25 served as the initial retriever in many RAG pipelines.
2024
Hybrid retrieval becomes standard
Production RAG systems standardized on BM25 + dense retrieval as complementary first-stage retrievers, combining lexical precision with semantic recall.

Three decades after its introduction, BM25 remains a production workhorse. Every time you search in Elasticsearch, query a RAG pipeline, or use a code search tool, BM25 is likely running as the first pass. Its descendants didn't replace it — they built on top of it.

CitationRobertson, Walker, Jones, Hancock-Beaulieu, Gatford. Okapi at TREC-3. TREC, 1994.

Terms in this paper

BM25BM25
Information Retrievalاسترجاع المعلومات
Inverted Indexالفهرس المقلوب
Term Frequencyتكرار المصطلح
Inverse Document Frequencyالتكرار المعكوس للوثائق
Document Length Normalizationتسوية طول الوثيقة
Sparse Retrievalالاسترجاع المتناثر
Bag of Wordsحقيبة الكلمات
Dense Retrievalالاسترجاع الكثيف