Best Match 25

This is a better version of dumb Keyword Search! Gives you ranking and fixes a lot of other problems.

It may be combined with Vector Search for something better (hybrid search). No synonyms, no meaning, no idea what “denies” means. It just counts words smarter.

Why “25”? It’s the 25th attempt in a series of “Best Match” scoring functions from the Okapi search system at City University London in the 1990s lol. Here’s the Wikipedia page.

People like this since it’s fast and explainable. But, again, it is dumb and has a problem with synonyms just like Keyword Search.

Why not Just Count yo?

Consider the dumbest possible keyword search: score each document by how many times the query words show up in it. Cool. But there are some problems:

1. Repetition wins.
   A note that says “allergy” 10 times beats one that says it once. But the 10th mention tells you way less than the 1st.
2. All words are equal.
   ”allergy” shows up in half your notes. “penicillin” shows up in two. A match on the rare word should count for more.
3. Long documents win.
   A 2,000-word discharge summary will contain something matching your query just by being long.

BM25 (and its extensions) attempt to fix these problems.

The Formula

For a query $Q$ with words $q_1, \dots, q_n$ and a document $D$:

$$\text{BM25}(D, Q) = \sum_{i=1}^{n} \underbrace{\text{IDF}(q_i)}_{\text{rarity}} \cdot \underbrace{\frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}}_{\text{saturating, length-adjusted count}}$$

where

• $f(q_i, D)$ = how many times word $q_i$ appears in $D$ (the term frequency)
• $|D|$ = length of $D$ in words; $\text{avgdl}$ = average document length across the collection
• $k_1$ = how fast the count saturates (usually $1.2$)
• $b$ = how much to punish long documents (usually $0.75$; $0$ = don’t care about length, $1$ = full punishment)

Phew! How does it address the problems?

Fix 1: Rare Words Matter More (IDF)

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

$N$ = number of documents, $n(q)$ = number of documents containing $q$. A word in every document gets IDF close to $0$. A word in one document gets a big IDF. The $0.5$s are there so nothing blows up when $n(q) = 0$, and the $+1$ keeps it from going negative¹.

Fix 2: Diminishing Returns (Saturation)

Ignore length for a second (pretend $|D| = \text{avgdl}$, so the denominator’s messy part is just $k_1$). With $k_1 = 1.2$, the count term is $\frac{2.2 f}{f + 1.2}$:

times word appears ($f$)	1	2	3	10	1,000,000
raw count	1	2	3	10	1,000,000
BM25 count term	1.00	1.375	1.571	1.964	~2.2

++It can never go above $k_1 + 1$.++ The first mention is worth 1, the second adds 0.375, the third adds 0.2, and then you’re mostly done. Spamming a word gets you nowhere.

Fix 3: Length Normalization

The $1 - b + b \cdot \frac{|D|}{\text{avgdl}}$ bit is $1$ for an average-length document, bigger for a long one, smaller for a short one. It sits in the denominator, so a match in a short document is worth more than the same match in a long one. Makes sense: “penicillin” in a 3-word note is probably the point of that note. In an 18-word note it’s one thing among many.

We’ll need an example…

---

Example

Take 5 tiny notes. Query is “penicillin allergy”. (Real systems also drop stop words and stem. Just counting every word to keep it simple.)

Note	Text	length
D1	Penicillin allergy: hives.	3
D2	Seasonal allergy to pollen. Allergy worse in spring. Allergy meds helping.	11
D3	Started amoxicillin for strep throat.	5
D4	Annual physical. No known allergy.	5
D5	Admitted with chest pain. Troponin negative. History of hypertension and diabetes. Allergy to penicillin noted. Discharged on metformin.	18

$N = 5$, $\text{avgdl} = \frac{3 + 11 + 5 + 5 + 18}{5} = 8.4$.

Dumb counting says: D2 (3 hits) > D1, D5 (2 hits each) > D4 (1 hit). The pollen note wins a penicillin search. Lol.

Step 1: IDF

“penicillin” is in 2 notes (D1, D5). “allergy” is in 4 (D1, D2, D4, D5).

$$\begin{aligned} \text{IDF}(\text{penicillin}) & = \ln\left(\frac{5 - 2 + 0.5}{2 + 0.5} + 1\right) = \ln(2.4) & \approx 0.875 \\ \text{IDF}(\text{allergy}) & = \ln\left(\frac{5 - 4 + 0.5}{4 + 0.5} + 1\right) = \ln(1.333) & \approx 0.288 \end{aligned}$$

A “penicillin” match is worth ~3× an “allergy” match.

Step 2: Length Factor

$K(D) = k_1\left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right) = 1.2\left(0.25 + 0.75 \cdot \frac{|D|}{8.4}\right)$

note	$\lvert D \rvert$	$K(D)$
D1	3	0.621
D2	11	1.479
D4	5	0.836
D5	18	2.229

(D3 has no query words so it scores $0$ regardless.)

Step 3: Count Terms and Final Score

Count term $= \frac{2.2 f}{f + K(D)}$.

note	$f$ penicillin	$f$ allergy	count term(s)	score
D1	1	1	$\frac{2.2}{1.621} = 1.357$	$1.357(0.875 + 0.288) = \mathbf{1.578}$
D5	1	1	$\frac{2.2}{3.229} = 0.681$	$0.681(0.875 + 0.288) = \mathbf{0.793}$
D2	0	3	$\frac{6.6}{4.479} = 1.474$	$1.474 \times 0.288 = \mathbf{0.424}$
D4	0	1	$\frac{2.2}{1.836} = 1.198$	$1.198 \times 0.288 = \mathbf{0.345}$
D3	0	0	—	$\mathbf{0}$

What happened:

• D1 wins. Both words, and it’s short, so each match counts double what it does in D5.
• D5 beats D2 even though D5 is the longest note. It has the rare word “penicillin”; D2 only has the common word “allergy”.
• D2’s three “allergy”s only got it to $1.474$, barely more than D4’s single one ($1.198$). Saturation.
• D4 still scores. “No known allergy” matches “allergy”. BM25 has no clue what “no” means. Neither does any keyword search. That’s what the LLM in RAG is for.
• D3 scores zero. Amoxicillin is a penicillin, but BM25 doesn’t know that. That’s what vector search (or query expansion) is for.

BM25 vs. TF-IDF

TODO: Finish this.

Other Cool Stuff

When you set $b = 0$, length stops mattering. $K(D) = k_1$ for every document, so D1 and D5 would get the exact same score.

As $k_1 \to 0$, count term becomes $\frac{f}{f} = 1$ for any $f > 0$. Repetition is worthless; a word is either present or not (binary). CooL!

Here’s another super-cool thing: If a word appears in every single document, $\ln\left(\frac{0.5}{N + 0.5} + 1\right) \approx 0$ for big $N$. Matching it barely moves the score, like a stop word.

Footnotes

1. The original Robertson–Spärck Jones IDF doesn’t have the $+1$, so a word in more than half the documents gets a negative weight. Lucene (and so Elasticsearch) added the $+1$. Libraries differ slightly here, which is why the same query can give different BM25 numbers in different tools. ↩