./ahmedhashim

BM25 is what’s used by default in Lucene (and therefore Elasticsearch) to calculate relevance. It builds off the concept of the TF/IDF model and is described by Wikipedia 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.

By breaking the BM25 algorithm down into individual steps, we can begin to understand how it works:

  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$

First we have our query from the user $Q$. This will consist of one or many keywords $(q_1, q_2, ..., q_n)$ that are parsed and turned into terms. These terms are then compared to the documents in our collection.

For example:

"running shoes for marathoners"

Query terms $q_i$

The query is parsed into keywords known as query terms $q_i$. Each query term will be scored against the documents. This is where the analyzers for the field come into play. The standard analyzer that Elasticsearch uses will simply lowercase and split on word boundaries. If you were to use something like the english analyzer, you’d also stem and remove stop words. Analyzers are also applied when indexing your documents, so your query terms will match those of your documents.

For example:

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

As you can see, the stop word for was removed and each term was stemmed.

Document collection

Your collection is simply the documents that you’ve indexed, whether that be web pages or a list of products. We’ll use the size of our collection $N$ to determine how infrequent our query terms are using IDF.

Global statistics

BM25 has 2 stats it needs to know about the collection:

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

These allow BM25 to fairly compare terms of different rarity and documents of different lengths.

Lucene doesn’t calculate these statistics every time a document is written. They’re calculated when a segment is created, and when you perform a query, the values are added together from each segment. Documents that have been deleted or updated will still count towards these stats until they’re merged, so on an index that’s being updated frequently, your stats will be slightly inaccurate.

Because the merge policy will favor segments that have many deletes, this usually isn’t too big of an issue. You can force merge with only_expunge_deletes or reindex into a new index if you want to recalculate these stats.

Elasticsearch adds another complexity because it’ll calculate these stats for each shard. If your index is large enough and documents are spread across each shard, it won’t matter. But if you have a small index spread over many shards, you may see different scores for the same document. Using the dfs_query_then_fetch search type will give you accurate scores, at the cost of an additional round trip.

IDF (inverse document frequency)

IDF stands for inverse document frequency and is used to measure how rare a term is within a collection. It’s calculated by Lucene using the following formula:

Where:

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

We add 0.5 so that we don’t divide by zero if a term doesn’t appear in any documents. We also add 1 so that our value will always be positive. Otherwise, if a term was contained in more than 50% of the documents, our IDF would be negative.

The less frequent terms will have a larger IDF value. Words like the will be very close to zero, while other terms will have a much higher value. If we were to have 1,000,000 documents, our example terms (with for added back to show how little a stop word is worth) may get values like:

For each document $D$

Using an inverted index, we can pull out all documents that have at least 1 of our terms, and each document we find gets a BM25 score. This is where we start calculating on a document level.

Document statistics

BM25 requires us to calculate two additional values per document:

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

Because Elasticsearch calculates this for each field, $|D|$ will most likely be the number of tokens in your field, not the entire document.

You may have a document with the title “Marathon Training: Choosing the Right Footwear” that has:

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

Parameters

There are 2 values that you can tweak in BM25:

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}$.

By default, Elasticsearch will use $k_1 = 1.2$ and $b = 0.75$. These will work for most cases. If you do want to tune them, you’ll need a test set of queries that you’ve manually scored and an offline process to test these values.

You should only do this as a last resort. Most of the time, if you have bad relevance, it’s due to your indexing. Using the wrong analyzer or stuffing your title and description in the same field will hurt your results more than tweaking $k_1$ and $b$ can ever fix.

Length normalization $\text{LN}$

Longer documents will have higher counts for a term. However, longer documents may not be more relevant to the term. We can normalize for document length:

Documents that are the average length will receive $\text{LN} = 1$. Longer documents get a higher number, which lowers their TF, and shorter ones get a lower number, which raises it. If our corpus had an average length of 1,000 words, our document with 850 words would receive $1 - 0.75 + 0.75 \cdot 0.85 \approx 0.89$, which is a slight boost.

TF (term frequency)

Term frequency (TF) tells you how many times the query term appears in the document. It also has saturation built into it, meaning the first few times a term appears in a document are weighted higher than the next few times:

With classic TF-IDF, the value will keep increasing as the term appears more in the document. So if you had a page that contained marathon 50 times, your value would continue to go up. BM25’s TF will never be higher than $k_1 + 1$, which discourages keyword stuffing. Our document has marathon 8 times and will receive a score of $\frac{8 \cdot 2.2}{8 + 1.2 \cdot 0.89} \approx 1.94$, which is pretty close to our max of 2.2.

As of Lucene 8.0, the $(k_1 + 1)$ value was removed from the numerator. Since this value just multiplies the score by the same amount for each document, removing it makes Elasticsearch scores lower than what you’d calculate by hand without changing the order of the results.

Term score

We take our IDF value and multiply it by our TF value to get our term score. For marathon in our document, we’d get 6.91 × 1.94 ≈ 13.4.

We will have one term score for each term in our query. Each score represents how well the document matches that part of the query.

Sum for all query terms

We add these together to get our document score, so documents that match more of the query usually score higher. Our document scored 6.05 for run, 8.60 for shoe and 13.4 for marathon, giving us a total of around 28.1.

If you add them together, you’re assuming that the terms have no correlation. BM25 has no idea that marathon shoe next to each other is more relevant than those terms scattered across the document. You can use a phrase query to account for this. It’ll only return results if the terms are in order and next to each other. If you set the slop on the phrase query, you can relax this to within a few positions, which turns it into a proximity query.

BM25 score $(D,Q)$

So adding those values together gives us the final score for document $D$ with our query $Q$. The larger the number, the more relevant the document is to the query.

There’s no scale to compare these numbers to. You’ll always have more points added to your score if you have more terms in your query. So searching for run will never have a score higher than about 6.6, but our query with 3 terms can have a score of over 30. This is why you should never set a minimum score of 10 and hide all results below that number. It may work for some queries but not others.

For this reason, you shouldn’t use the score to compare queries or see which query is returning the best results.

Sort documents by BM25 score

Take all your scored documents and sort them by score descending. You can always use other factors to break ties, such as date created or how many likes a document has.

Ranked results

You now have a list of documents sorted by how relevant they are to your query. Typically you’ll see documents that contain your rarest terms many times and aren’t too long.

For our query “running shoes for marathoners”, we may get back the following results:

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)