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:
- Obtain the raw documents.
- Perform text analysis on the documents.
- Run tokenization, normalization, and similar processing.
- Count term occurrences.
- Record which documents each term belongs to.
- Build the posting lists.
- 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:
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:
- IDF: determines how important a query term is.
- TF saturation: determines how much term frequency contributes to the relevance score.
- 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:
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:
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:
The term frequency contribution is:
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:
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:
A term appears in 100 documents:
Substitute into the formula:
Now suppose another term appears in 8000 documents:
Then:
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:
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:
Where:
- |D|: current document length.
- avgdl: average length of the entire document collection.
- b: length normalization parameter.
When:
Then:
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:
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:
Document length no longer participates in the adjustment.
When b=1:
Document length fully participates in normalization.
6.4 Impact of long and short documents
Assume:
For a document of length 50:
For a document of length 200:
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:
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:
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:
8.1 Calculate the length normalization term
Substitute:
8.2 Calculate the IDF of Java
8.3 Calculate the IDF of thread pool
As can be seen, “thread pool” appears in fewer documents, so its IDF is higher.
8.4 Calculate the term frequency contribution of Java
Therefore:
8.5 Calculate the term frequency contribution of thread pool
Therefore:
8.6 Calculating the Final BM25 Score
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.