Back to series
· 11 min read

BM25 Full-Text Search Principles: The Complete Mechanism from Inverted Index to Relevance Scoring


1. What Is BM25?

BM25 (Best Matching 25) is a relevance scoring algorithm based on the probabilistic information retrieval framework, primarily used to measure the degree of relevance between a query and a document.

It is widely used in:

  • Full-text search in search engines.
  • Enterprise knowledge base search.
  • Document management systems.
  • Log and technical document retrieval.
  • Keyword recall in RAG systems.
  • Hybrid recall combining vector retrieval and keyword retrieval.

The core idea of BM25 is:

The more relevant a document is to a query — the more appropriately and discriminatively its query terms appear in it — the higher the relevance score the document should receive.

For example, a user searches for:

How does a Java thread pool control the level of concurrency?

The search system may find the following documents:

Document Content
A Java thread pools control concurrency through the core pool size and maximum pool size
B Thread synchronization mechanisms in Java concurrent programming
C How to use Python thread pools
D Java basic syntax and object-oriented programming

BM25 takes into comprehensive account how the query terms appear in each document, as well as the discriminating power of those terms across the entire document collection, and computes a relevance score for each document.

Unlike simple keyword matching, BM25 does not merely count how many times the query terms occur; it also considers term frequency saturation and document length.

1.1 Core Components of BM25

BM25 mainly involves three concepts:

Concept English Main Role
Term frequency Term Frequency, TF Measures how often the query terms occur in a document
Inverse document frequency Inverse Document Frequency, IDF Measures the discriminating power of a term across the entire document collection
Document length normalization Document Length Normalization Adjusts for scoring bias between documents of different lengths

Together, these three factors determine the relevance score of a document.

1.2 Differences Between BM25 and Simple Keyword Matching

Simple keyword matching usually only determines whether the query terms appear in a document.

For example:

Query: Java thread pool

Document A: Core parameters of a Java thread pool
Document B: Thread management mechanism of a Java thread pool
Document C: Basic Java syntax

If the only criterion is whether the keywords exist, A, B, and C might all yield some level of match.

BM25, by contrast, further considers:

  • How many times the query terms appear.
  • Whether the query terms are common across the entire document collection.
  • How long the document itself is.
  • Whether high-frequency terms have already reached the point of diminishing returns.

As a result, BM25 can rank matched results more reasonably.


2. The Foundation of BM25: The Inverted Index

BM25 is responsible for computing relevance scores, but in large-scale full-text retrieval systems, documents are usually not scanned one by one.

Search engines generally use an inverted index to quickly locate the documents that contain the query terms.

2.1 What Is an Inverted Index?

An inverted index is a data structure that organizes document information using terms as the entry point.

Traditional document storage is usually organized by document:

Document A: Java thread pool, concurrency control
Document B: Java lock mechanism, thread synchronization
Document C: Python thread pool, concurrency handling

An inverted index does the reverse, using terms as the index entry point:

Java:
    Document A
    Document B

Thread pool:
    Document A
    Document C

Concurrency:
    Document A
    Document C

Lock mechanism:
    Document B

With this structure, documents containing a given term can be found quickly without scanning the entire contents of every document.

2.2 Basic Structure of an Inverted Index

An inverted index mainly consists of two parts:

Dictionary

Stores the terms after analysis and processing, together with their index information.

Posting List

Stores the records of documents that contain the term, along with related statistics.

For example:

{
  "java": [
    {
      "doc_id": "A",
      "term_frequency": 3,
      "positions": [1, 5, 9]
    },
    {
      "doc_id": "B",
      "term_frequency": 2,
      "positions": [2, 7]
    }
  ],
  "thread_pool": [
    {
      "doc_id": "A",
      "term_frequency": 2,
      "positions": [3, 8]
    }
  ]
}

Where:

  • doc_id: Document identifier.
  • term_frequency: The number of times the term appears in the document.
  • positions: The positions of the term in the document.

Real-world search engines typically store posting lists using compression, blocking, skip lists, or other optimized structures; they do not necessarily use the JSON form shown above.

2.3 How Is an Inverted Index Built?

Building an inverted index usually involves the following steps:

  1. Obtain the raw documents.
  2. Perform text analysis on the documents.
  3. Run tokenization, normalization, and similar processing.
  4. Count term occurrences.
  5. Record which documents each term belongs to.
  6. Build the posting lists.
  7. Store document lengths and collection statistics.
flowchart TD
    A["Raw document collection"] --> B["Text parsing"]
    B --> C["Tokenization and text normalization"]
    C --> D["Generate term sequence"]
    D --> E["Count term frequencies and term positions"]
    E --> F["Organize document records by term"]
    F --> G["Build posting lists"]
    G --> H["Store document lengths and collection statistics"]
    H --> I["Generate the inverted index"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#EAF3EC,stroke:#83A995,color:#315D49
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#EAF3EC,stroke:#83A995,color:#315D49
    style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style I fill:#E5F0E9,stroke:#83A995,color:#315D49

2.4 The Relationship Between the Inverted Index and BM25

Two concepts need to be distinguished:

  • The inverted index is responsible for quickly finding the candidate documents that contain the query terms.
  • BM25 is responsible for computing the relevance score between the candidate documents and the query.

The two work together.

The inverted index addresses retrieval efficiency, while BM25 addresses relevance ranking.


III. The BM25 Mathematical Formula

The classic BM25 scoring formula is:

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

Where:

Symbol Meaning
D The document currently being scored
Q The user query
q_i The i-th term in the query
f(q_i,D) The term frequency of the query term in document D
( D
avgdl The average document length in the collection
k_1 Parameter controlling the degree of term frequency saturation
b Parameter controlling the degree of document length normalization
IDF(q_i) The inverse document frequency of the query term

The formula can be broken down into three core parts:

  1. IDF: determines how important a query term is.
  2. TF saturation: determines how much term frequency contributes to the relevance score.
  3. Length normalization: adjusts for the scoring bias caused by document length.

Understand these three parts, and you understand the main workings of BM25.


IV. Part One: TF and Term Frequency Saturation

TF (Term Frequency) is the number of times a given term appears in a document.

For example:

Document A:
A Java thread pool can manage threads.
A thread pool supports concurrency control.
A thread pool can reuse threads.

Document B:
Java provides several concurrency programming mechanisms.

If the query term is "thread pool":

  • It appears 3 times in Document A.
  • It appears 0 times in Document B.

From a term frequency perspective, Document A should contribute more to the match.

But scoring based on term frequency alone creates a problem:

The more times a word appears, the higher the score grows — without any limit.

That is not reasonable.

4.1 Why Is Term Frequency Saturation Needed?

Suppose the query term "Java" appears in a document:

Occurrences Raw term frequency
1 1
5 5
10 10
20 20
100 100

If raw term frequency were used directly, a document containing the term 100 times would receive a score 100 times that of a document containing it once.

But for search relevance:

  • Going from 0 occurrences to 1 may be very important.
  • Going from 1 to 2 usually still has value.
  • Going from 20 to 21 may add very little value.

In other words, the contribution of term frequency to relevance should gradually saturate.

4.2 The BM25 term frequency saturation formula

Ignoring document length normalization for now, the term frequency part of BM25 can be written as:

TF_{\text{BM25}} = \frac{f(k_1+1)}{f+k_1}

Where:

  • f: the term frequency of the query term in the document.
  • k_1: the parameter that controls how fast saturation occurs.

As term frequency increases, the TF contribution gradually approaches an upper limit:

\lim_{f\to\infty} \frac{f(k_1+1)}{f+k_1} = k_1+1

Therefore, BM25 will not keep increasing a document's score indefinitely just because a term appears a large number of times.

4.3 The role of the k1 parameter

k_1 controls how quickly term frequency saturates.

In general:

  • Smaller k_1: term frequency saturates faster.
  • Larger k_1: the contribution from additional occurrences persists longer.

Common values are roughly around 1.2 to 2.0, but this is not a fixed standard; it should be evaluated in the context of the specific retrieval task.

4.4 Term frequency saturation example

Assume:

k_1=1.5

The term frequency contribution is:

TF= \frac{2.5f}{f+1.5}

Results for different term frequencies:

Term frequency f TF contribution
1 1.000
2 1.429
3 1.667
5 1.923
10 2.174
20 2.326
100 2.463

We can observe:

Going from a term frequency of 1 to 5, the score contribution grows noticeably; but going from 20 to 100, the growth in contribution is already quite limited.

This is the term frequency saturation mechanism.


Five, Part Two: IDF Inverse Document Frequency

IDF (Inverse Document Frequency) measures a term's ability to discriminate across the entire document collection.

The more documents a term appears in, the less helpful it usually is for distinguishing between documents.

Conversely, the rarer a term is, the more discriminating value it often has.

5.1 Why is IDF needed?

Suppose a knowledge base contains 10,000 documents.

Query:

Java thread pool parameter configuration

The distribution of different terms might be as follows:

Term Number of documents containing the term
Java 6000
Thread pool 800
Parameter 4000
Configuration 3000
ThreadPoolExecutor 50

Where:

  • Java appears in a large number of documents.
  • Parameters and configuration are also relatively common.
  • ThreadPoolExecutor is relatively rare.

If a term appears in almost all documents, its discriminating power is relatively weak.

BM25 assigns different weights to different terms through IDF.

5.2 The Classic IDF Formula

A common form of IDF in BM25 is:

IDF(q_i) = \ln \left( 1+ \frac{ N-n(q_i)+0.5 }{ n(q_i)+0.5 } \right)

Where:

  • N: the total number of documents in the document collection.
  • n(q_i): the number of documents containing at least the query term q_i.
  • \ln: natural logarithm.

Note the following:

n(q_i) counts the number of documents containing the term, not the total number of times the term appears across all documents.

5.3 Example IDF Calculation

Suppose:

N=10000

A term appears in 100 documents:

n(q_i)=100

Substitute into the formula:

IDF(q_i) = \ln \left( 1+ \frac{10000-100+0.5}{100+0.5} \right)
IDF(q_i)\approx4.60

Now suppose another term appears in 8000 documents:

n(q_i)=8000

Then:

IDF(q_i) = \ln \left( 1+ \frac{10000-8000+0.5}{8000+0.5} \right)
IDF(q_i)\approx0.22

By comparison:

  • Terms that appear in only a small number of documents have higher IDF.
  • Terms that appear in a large number of documents have lower IDF.

Therefore, rare terms usually have higher discriminative weight.

5.4 Why is there a 0.5 in the IDF formula?

The 0.5 in the formula is part of smoothing.

It can avoid issues such as division by zero in certain boundary cases and make IDF calculation more stable.

For example:

When a term appears in all documents:

n(q_i)=N

Without appropriate smoothing, the IDF value may exhibit unreasonable boundary behavior.

Note that BM25 may use different IDF implementations or variants in different search systems. The form given above is the classic Robertson-style BM25 IDF; you should not assume that the internal implementations of all search engines are exactly the same.

5.5 Engineering Significance of IDF

IDF is very important for search quality.

For example, query:

ERR_CONNECTION_RESET network error

Where:

  • “network” is a relatively common word.
  • “error” is also a relatively common word.
  • “ERR_CONNECTION_RESET” usually has strong discriminating power.

Reasonable IDF can increase the influence of exact terms in relevance ranking.


6. Part Three: Document Length Normalization

The third important mechanism of BM25 is document length normalization.

It is used to address scoring bias between documents of different lengths.

6.1 Why does document length affect scoring?

Suppose there are two documents:

Document A:
Java thread pools can control the number of threads.

Document B:
Java thread pools can control the number of threads.
Java thread pools can manage task queues.
Java thread pools can reuse worker threads.
Java thread pools can configure rejection policies.
Java thread pools can control concurrent execution.
...

Document B is much longer than Document A.

If only term frequency is considered, long documents often have more opportunities to contain the query terms, and may therefore receive higher scores.

However, a long document is not necessarily more relevant than a short document.

BM25 adjusts for this bias through document length normalization.

6.2 Document Length Normalization Formula

The length adjustment term in BM25 is:

1-b+b\frac{|D|}{avgdl}

Where:

  • |D|: current document length.
  • avgdl: average length of the entire document collection.
  • b: length normalization parameter.

When:

|D|=avgdl

Then:

1-b+b\frac{|D|}{avgdl}=1

In this case, document length no longer additionally changes the denominator of the term frequency part.

6.3 Role of the b parameter

b controls the degree of document length normalization.

Usually:

0\leq b\leq1

Meanings of different values:

b value Effect
0 No document length normalization
0.5 Partial length normalization
0.75 One common default value
1 Normalize fully according to the document length ratio

When b=0:

1-b+b\frac{|D|}{avgdl}=1

Document length no longer participates in the adjustment.

When b=1:

1-b+b\frac{|D|}{avgdl} = \frac{|D|}{avgdl}

Document length fully participates in normalization.

6.4 Impact of long and short documents

Assume:

avgdl=100
b=0.75

For a document of length 50:

1-0.75+0.75\times\frac{50}{100} =0.625

For a document of length 200:

1-0.75+0.75\times\frac{200}{100} =1.75

With all other conditions equal:

  • Short documents have a smaller length adjustment term.
  • Long documents have a larger length adjustment term.

Because the length adjustment term is in the denominator of BM25's term frequency fraction, long documents usually receive a stronger length penalty.

However, the actual score still depends on term frequency, IDF, and other parameters; final ranking cannot be determined by document length alone.


7. Understanding BM25's Scoring Mechanism in Full

Now combine TF, IDF, and document length normalization.

The complete formula:

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

It can be understood as:

Each query term contributes separately, and all query term contributions are summed to obtain the document's final score.

7.1 Breaking down the scoring process

Suppose the query is:

Java thread pool

and the document is:

A Java thread pool can manage worker threads and control the number of concurrent tasks through thread pool parameters.

The system needs to calculate separately:

  • Java's contribution to this document.
  • thread pool's contribution to this document.

Then add the two parts together:

Score(D,Q) = Score(Java,D) + Score(\text{thread pool},D)

Each term's score includes IDF, term frequency, and length normalization.

7.2 Complete scoring process

flowchart TD
    A["User submits query"] --> B["Query text analysis and tokenization"]
    B --> C["Extract query terms"]
    C --> D["Look up candidate documents in the inverted index"]
    D --> E["Read term frequency and document length"]
    E --> F["Calculate IDF of query terms"]
    F --> G["Calculate term frequency saturation"]
    G --> H["Perform document length normalization"]
    H --> I["Sum scores of query terms"]
    I --> J["Obtain BM25 score"]
    J --> K["Sort by score in descending order"]
    K --> L["Return Top-K documents"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#EAF3EC,stroke:#83A995,color:#315D49
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#EAF3EC,stroke:#83A995,color:#315D49
    style H fill:#EAF3EC,stroke:#83A995,color:#315D49
    style I fill:#EAF3EC,stroke:#83A995,color:#315D49
    style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style K fill:#EAF3EC,stroke:#83A995,color:#315D49
    style L fill:#E5F0E9,stroke:#83A995,color:#315D49

8. Complete BM25 Calculation Example

Understand the BM25 calculation process through a concrete example.

Suppose the document collection contains 1000 documents, and the user query is:

Java thread pool

Now we need to calculate the relevance of document A.

Document A:

Java thread pool can manage worker threads, and the thread pool can control the number of concurrent tasks.

Assume that after tokenization, the query contains two terms:

Java
thread pool

Known statistics:

Parameter Java thread pool
Total number of documents in the collection N 1000 1000
Number of documents containing the term n 600 100
Term frequency in the current document f 1 2

In addition:

|D|=80
avgdl=100
k_1=1.5
b=0.75

8.1 Calculate the length normalization term

K= 1-b+b\frac{|D|}{avgdl}

Substitute:

K= 1-0.75+0.75\times\frac{80}{100}
K=0.85

8.2 Calculate the IDF of Java

IDF(Java) = \ln \left( 1+ \frac{1000-600+0.5}{600+0.5} \right)
IDF(Java)\approx0.511

8.3 Calculate the IDF of thread pool

IDF(thread pool) = \ln \left( 1+ \frac{1000-100+0.5}{100+0.5} \right)
IDF(thread pool)\approx2.299

As can be seen, “thread pool” appears in fewer documents, so its IDF is higher.

8.4 Calculate the term frequency contribution of Java

TF(Java) = \frac{1\times(1.5+1)}
TF(Java)\approx1.075

Therefore:

Score(Java) = 0.511\times1.075
Score(Java)\approx0.549

8.5 Calculate the term frequency contribution of thread pool

TF(thread pool) = \frac{2\times(1.5+1)}
TF(thread pool)\approx1.639

Therefore:

Score(thread pool) = 2.299\times1.639
Score(thread pool)\approx3.768

8.6 Calculating the Final BM25 Score

BM25(D,Q) = Score(Java)+Score(thread pool)
BM25(D,Q) \approx0.549+3.768
\boxed{BM25(D,Q)\approx4.317}

This result shows that, under the given statistics and parameters, Document A has some relevance to the query.

Note that a BM25 score is not a probability and has no unified maximum value. It is mainly used to rank candidate documents within the same retrieval system and under the same scoring configuration.


9. Practical Implementation of BM25

After understanding the formula, you can implement a simplified version in Python.

The implementation below assumes that the input has already been tokenized, and that both the query and the documents use the same term normalization rules.