./ahmedhashim

BM25 is the default relevance scoring function in Lucene, and by extension Elasticsearch. It’s an evolution of the TF/IDF model, and Wikipedia defines it as:

Given a query $Q$, containing keywords $q_1, q_2, ..., q_n$, the BM25 score of a document $D$ is:

$$\text{score}(D,Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i,D) \cdot (k_1+1)}{f(q_i,D) + k_1 \cdot \left(1-b+b \cdot \frac{|D|}{\text{avgdl}}\right)}$$

where $f(q_i, D)$ is the number of times that the keyword $q_i$ occurs in the document $D$, $|D|$ is the length of the document $D$ in words, and $\text{avgdl}$ is the average document length in the text collection from which documents are drawn.

To understand how it works, it helps to walk through the algorithm as a series of steps:

  graph TD
Query["<strong>Query Q</strong><br/><span class='mermaid-detail'>(q₁, q₂, ..., qₙ)</span>"] --> Terms["<strong>Query Terms</strong><br/><span class='mermaid-detail'>qᵢ</span>"]

    Collection["<strong>Document Collection</strong><br/><span class='mermaid-detail'>N total documents</span>"] --> GlobalStats["<strong>Global Statistics</strong><br/><span class='mermaid-detail'>n(qᵢ): docs containing qᵢ<br/>avgdl: average doc length</span>"]

    GlobalStats --> IDF["<strong>IDF(qᵢ)</strong><br/><span class='mermaid-detail'>ln((N-n(qᵢ)+0.5)/<br/>(n(qᵢ)+0.5)+1)</span>"]

    Terms --> IDF

    Documents["<strong>For each Document D</strong>"] --> DocStats["<strong>Document Statistics</strong><br/><span class='mermaid-detail'>f(qᵢ,D): term frequency<br/>|D|: document length</span>"]

    DocStats --> TF["<strong>TF(qᵢ)</strong><br/><span class='mermaid-detail'>f(qᵢ,D)·(k₁+1) /<br/>(f(qᵢ,D) + k₁·LN)</span>"]

    GlobalStats --> LengthNorm["<strong>Length Normalization</strong><br/><span class='mermaid-detail'>1 - b + b·(|D|/avgdl)</span>"]
    DocStats --> LengthNorm

    Params["<strong>Parameters</strong><br/><span class='mermaid-detail'>k₁ ∈ [1.2, 2.0]<br/>b = 0.75</span>"] --> LengthNorm
    Params --> TF
    LengthNorm --> TF

    IDF --> TermScore["<strong>Term Score</strong><br/><span class='mermaid-detail'>IDF(qᵢ) × TF(qᵢ,D)</span>"]
    TF --> TermScore

    TermScore --> Sum["<strong>Sum query terms</strong><br/><span class='mermaid-detail'>Σᵢ₌₁ⁿ term scores</span>"]

    Sum --> DocScore["<strong>BM25 Score(D,Q)</strong><br/><span class='mermaid-detail'>for each document</span>"]

    DocScore --> Rank["<strong>Sort Documents</strong><br/><span class='mermaid-detail'>by BM25 score</span>"]

    Rank --> Output["<strong>Ranked Results</strong><br/><span class='mermaid-detail'>Doc₁ highest score<br/>Doc₂<br/>Doc₃</span>"]

Query $Q$

The user’s query $Q$ is the starting input. It contains the keywords $(q_1, q_2, ..., q_n)$ that get parsed and tokenized into individual terms before they’re matched against the collection.

Example:

"running shoes for marathoners"

Query terms $q_i$

Parsing breaks the query into individual keywords called query terms $q_i$, and each one is scored against the documents separately. This is also where the field’s analyzer runs. Elasticsearch’s standard analyzer only lowercases and splits on word boundaries, but an analyzer like english adds stemming and removes stop words. The same analyzer runs at index time, so the query terms line up with what’s actually stored.

Example:

["running", "shoes", "for", "marathoners"] → ["run", "shoe", "marathon"]

The stop word for has been removed, and each remaining term has been stemmed to its root form.

Document collection

The collection is everything the search engine has indexed, whether that’s web pages or a product catalog. Its total size $N$ feeds into IDF, which is how BM25 decides how rare each query term is.

Global statistics

BM25 needs two collection-wide numbers:

1. $n(q_i)$: the number of documents containing each query term.
2. $\text{avgdl}$: the average document length.

They let it compare terms of different rarity and documents of different length on the same scale.

Lucene doesn’t recompute these from scratch on every write. Each segment stores its own term statistics when it’s written, and a query sums them across segments. Deleted and updated documents keep counting until a merge cleans them up, so on a corpus that changes constantly the statistics are always a little out of date.

The merge policy already prioritizes segments with a lot of deletes, so in practice the gap stays small. If it matters, a force merge with only_expunge_deletes or a reindex into a fresh index will reset the counts.

Elasticsearch adds a second wrinkle: each shard scores with its own statistics. On a large index with documents spread evenly across shards the difference is negligible, but on a small index split across several shards, identical documents can come back with different scores. The dfs_query_then_fetch search type fixes this by gathering statistics from every shard before scoring, at the cost of an extra round trip.

IDF (inverse document frequency)

IDF measures how rare a term is across the collection. Lucene computes it as:

Where:

1. $N$: the total number of documents in the collection.
2. $n(q_i)$: the number of documents containing term $q_i$.

The 0.5 smoothing keeps the fraction defined when a term appears in no documents. The + 1 inside the logarithm keeps the result positive. Without it, a term that shows up in more than half the documents would get a negative IDF and drag scores down.

Rarer terms get higher IDF scores, so common words like the barely contribute and specific terms carry most of the ranking signal. In a collection of a million documents, our example terms (with for added back to show how little a stop word is worth) might work out to:

For each document $D$

The inverted index finds candidate documents that contain at least one of the query terms, and each candidate gets a BM25 score. This is where the algorithm shifts from collection-level to document-level analysis.

Document statistics

For each candidate, BM25 needs two more numbers:

1. $f(q_i, D)$: the number of times a term appears in the document.
2. $|D|$: the document’s length.

Elasticsearch scores each field separately, so in practice $|D|$ is the number of tokens in the field being searched rather than the whole document.

For example, a post titled “Marathon Training: Choosing the Right Footwear” might have:

{
  "f('run', D)": 12,
  "f('shoe', D)": 3,
  "f('marathon', D)": 8,
  "document_length": 850
}

Parameters

BM25 has two tunable parameters:

1. $k_1$: controls how quickly extra occurrences of a term stop adding to the score.
2. $b$: controls how much document length matters. At 0, length is ignored, and at 1 it’s fully normalized against $\text{avgdl}$.

Elasticsearch defaults to $k_1 = 1.2$ and $b = 0.75$, and they hold up well for most collections. Tuning past them usually means a held-out set of judged queries and an offline evaluation loop.

Treat that as a last resort. Bad rankings usually trace back to how the data is indexed. The wrong analyzer or a title and body crammed into one field will hurt relevance far more than $k_1$ and $b$ can fix, so get the mapping right before reaching for them.

Length normalization $\text{LN}$

Longer documents naturally contain more occurrences of any given term, but they aren’t necessarily more relevant to it. Length normalization corrects for that bias:

A document of exactly average length gets $\text{LN} = 1$. Longer documents get a larger value, which shrinks their TF, and shorter ones get a smaller value, which boosts it. If the collection averages 1,000 words, our 850-word post gets $1 - 0.75 + 0.75 \cdot 0.85 \approx 0.89$, a slight boost.

TF (term frequency)

TF measures how often a query term appears in a specific document, with saturation built in so the first few occurrences matter much more than the next few:

In classic TF-IDF the term frequency grows without limit, so a page that repeats marathon fifty times keeps climbing. BM25’s TF can never exceed $k_1 + 1$, which makes keyword stuffing a lot less rewarding. Our post mentions marathon 8 times and gets $\frac{8 \cdot 2.2}{8 + 1.2 \cdot 0.89} \approx 1.94$, which is already close to the ceiling of 2.2.

Lucene 8.0 dropped the $(k_1 + 1)$ factor from the numerator. The factor multiplies every score by the same constant, so removing it makes Elasticsearch’s scores smaller than the textbook formula without changing the order of the results.

Term score

The term score multiplies global rarity (IDF) by how often the term appears in this document (TF). For marathon in our post, that’s 6.91 × 1.94 ≈ 13.4.

Every query term produces one term score per document, measuring how well that document matches that part of the query.

Sum for all query terms

Term scores are summed into a single document score, so documents that match more of the query usually score higher. Our post picks up 6.05 from run, 8.60 from shoe and 13.4 from marathon, for a total of about 28.1.

Adding them up assumes the terms are independent. BM25 can’t tell that marathon shoe side by side means more than the same two words scattered across a page. To handle that, use a phrase query, which only matches the terms when they appear in order and next to each other. Setting its slop loosens that to “within a few positions”, which turns it into a proximity query.

BM25 score $(D,Q)$

That sum is the final BM25 score for document $D$ given query $Q$. The higher the score, the more relevant the document is to the query.

There’s no fixed scale here. Every query term adds to the score, so longer queries and rarer terms produce bigger numbers. A search for run can’t score above about 6.6, while our three-term query can go past 30. That’s why a fixed cutoff like “hide anything below 10” works for some queries and hides everything for others.

Because of this, you shouldn’t compare scores across queries or use them to judge which query found better results.

Sort documents by BM25 score

Sort the scored documents from highest to lowest. Ties can be broken with secondary criteria like recency or popularity, depending on what matters most for the collection.

Ranked results

The output is an ordered list of documents most likely to match the user’s intent. The top results tend to mention the rarest query terms several times without being unusually long.

For our “running shoes for marathoners” query, the top results might be:

1. “Best Marathon Running Shoes 2023” (Score: 30.9)
2. “Marathon Training: Choosing the Right Footwear” (Score: 28.1)
3. “Runner’s Guide to Marathon Shoes” (Score: 26.4)