BM25 - The Industry Standard

TF-IDF is a great conceptual starting point, but it has two fatal flaws that break down at scale:

1. Keyword Stuffing (Linear Scaling): In TF-IDF, if a document repeats a word 100 times, its score is 100x higher than a document mentioning it once. This makes it trivially easy for spammers to game the system by stuffing keywords at the bottom of a page.
2. Length Bias: A 1,000-page Terms of Service document that casually mentions “apple” 50 times will completely outrank a 2-page apple pie recipe that mentions it 40 times. TF-IDF does not care how long the document is; it only cares about raw counts.

It’s time to upgrade your engine to the industry standard used by Elasticsearch and Lucene: Okapi BM25.

The Concepts

BM25 fixes TF-IDF by introducing two new concepts:

• Term Frequency Saturation: Using a constant k_1, BM25 curves the TF score. After a certain number of occurrences, repeating the word over and over stops increasing the score. It plateaus.
• Document Length Normalization: Using a constant b, BM25 penalizes long documents. If a document is much longer than the average document in the index, its term frequency counts for less.

The Math

You will replace your score = TF * IDF calculation with the BM25 formula.

First, calculate the standard IDF exactly as before: $$ \text{IDF}(t) = 1 + \ln \left(\frac{N}{\text{df}(t) + 1} \right) $$

Then, calculate the BM25 score for a term t in document d: $$ \text{Score}(t, d) = \text{IDF}(t) \cdot \frac{\text{TF}(t, d) \cdot (k_1 + 1)}{\text{TF}(t, d) + k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)} $$

Where:

• TF(t, d): Term Frequency of term t in document d.
• |d|: The length of document d (total number of tokens after normalization and stop word removal).
• avgdl: The average document length across the entire corpus.
• k_1 = 1.2 (Standard tuning constant).
• b = 0.75 (Standard tuning constant).

Your Task

1. Track the length |d| of every document when it is ingested.
2. Track the sum of all document lengths so you can calculate avgdl dynamically at query time.
3. Replace your query-time TF-IDF calculation with the BM25 calculation above.
4. As always, sort the results descending by this score.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until bm25