FINDING NEEDLES · CHAPTER 03
TF-IDF pays a note for every repeat of a word, forever. BM25 stops paying after a few, and charges long notes for their length.
A bike workshop keeps five repair notes. You search for “chain oil”.
| Note | Text | Length | TF-IDF sum |
|---|---|---|---|
| 1 | oil chain | 2 | 2.059 |
| 2 | chain chain chain chain chain chain | 6 | 4.422 |
| 3 | brake cable chain oil gear pads tension index | 8 | 2.059 |
| 4 | tube patch | 2 | 0 |
| 5 | spoke wheel | 2 | 0 |
The last column is chapter 2's weight added up over the query words: raw tf times log2(N / df). Chain is in 3 of 5 notes, so its weight is log2(5/3) = 0.737. Oil is in 2, so log2(5/2) = 1.322. Note 1 gets 0.737 + 1.322 = 2.059. Note 2 never says oil, but six times 0.737 is 4.422. It wins.
That is the wrong note. Note 1 is a two-word instruction that is exactly about oiling a chain. Note 2 is a label someone typed with a stuck key. Note 3 says both words too, but they are two of eight topics.
The first mention of a word tells you the note is about it. The sixth mention tells you almost nothing new. And a word in a short note is a bigger share of what the note says than the same word in a long one. BM25 is TF-IDF with those two facts built in.
Replace the raw count with a fraction that grows fast at first and then flattens. For a note of average length it is:
k1 · b · IDF
repeats · sat · length · lexical
the count on top, the count plus k1 below. As the count grows, top and bottom grow together, and the fraction creeps toward k1 + 1 without reaching it.
With the common default k1 = 1.2 the cap is 2.2. One mention scores exactly 1.000, because the top and bottom are both 2.2.
| tf | Raw tf (TF-IDF) | BM25 tf part, k1 = 1.2 |
|---|---|---|
| 1 | 1 | 1.000 |
| 2 | 2 | 1.375 |
| 3 | 3 | 1.571 |
| 6 | 6 | 1.833 |
| ∞ | ∞ | 2.2 |
k1 sets how fast the curve bends. At k1 = 0 the fraction is 1 for any tf above zero: the note either has the word or it does not. As k1 grows the curve straightens back toward raw tf. Values between 1.2 and 2 are the usual starting points.
Count the terms in each note and take the mean: (2 + 6 + 8 + 2 + 2) / 5, so avgdl = 4. Then compare each note's length dl to that average.
a note of average length gets 1. A shorter note gets less than 1, a longer one more. b says how much of that length ratio to use: b = 0 ignores length, b = 1 uses all of it.
The length factor multiplies k1 in the bottom of the fraction. A long note has a bigger bottom, so the same count earns less. With b = 0.75 and tf = 1:
| Note length dl | norm | tf part for tf = 1 |
|---|---|---|
| 2 (note 1) | 0.625 | 1.257 |
| 4 (the average) | 1 | 1.000 |
| 8 (note 3) | 1.75 | 0.710 |
Notes 1 and 3 both say chain once and oil once. Note 1 is a quarter the length, so each of its words earns 1.257 against note 3's 0.710. Note 2 has six chains in six terms: norm 1.375, and its tf part is 1.725. Still under the 2.2 cap.
the saturation curve from section 2, where a long note has to say the word more times to climb the same distance.
BM25 keeps the idea of idf from chapter 2 but uses a different formula, from the probabilistic model it was derived from. Most engines today, Lucene among them, use this form, with the natural log:
notes without the word, over notes with it, each nudged by a half so nothing divides by zero. The 1 inside the log keeps the result above zero.
| Term | df of 5 | BM25 idf | Without the +1 | Chapter 2, log2(N / df) |
|---|---|---|---|---|
| chain | 3 | 0.539 | -0.336 | 0.737 |
| oil | 2 | 0.875 | 0.336 | 1.322 |
Chain is in 3 of 5 notes, more than half. The original form, without the +1, gives it a negative weight: saying chain would push a note down. That is a real effect, not a rounding issue. Adding 1 inside the log fixes it. A word in every note now gets a weight near zero, never below.
for each word you asked for: how rare it is, times how much this note says it, after the cap and the length charge. Then add.
Note 1, step by step, with k1 = 1.2 and b = 0.75:
| Note | chain part | oil part | BM25 | TF-IDF sum |
|---|---|---|---|---|
| 1 · oil chain | 0.678 | 1.101 | 1.778 | 2.059 |
| 3 · eight-topic note | 0.383 | 0.621 | 1.004 | 2.059 |
| 2 · chain × 6 | 0.930 | 0 | 0.930 | 4.422 |
| 4, 5 | 0 | 0 | 0 | 0 |
The order flips. TF-IDF put note 2 first and could not separate notes 1 and 3. BM25 ranks 1, 3, 2. Six chains in note 2 earn 0.930, less than note 3's single chain plus single oil. Saying both words beats shouting one.
A product page has a title and a body. A word in the title should count for more. BM25F handles this by mixing the term counts from each field with a weight per field, and applying length normalisation per field, before the one saturation step. Adding up separate BM25 scores per field would saturate each field on its own, which over-rewards a word that appears in many fields.
Other variants change one piece. BM25+ adds a small floor so a very long note that contains the word always beats one that does not. Engines also differ in small details: the log base, whether the (k1 + 1) on top is kept (it rescales every score the same way, so it never changes the order), and how idf is clamped. If two systems give different numbers for the same note, check those first.
Interactive · k1 and b on the five notes
Set b to 0, then slide k1 up. When does the six-chain note take the lead?
Three settings worth trying. At b = 0, length is ignored, so notes 1 and 3 tie at 1.414, with note 2 at 0.988. Keep b at 0 and raise k1: repeats pay more and more, and at k1 = 2.9 note 2 overtakes. At k1 = 3 it scores 1.437 against 1.414. Now raise b again and note 2 falls back, because six terms is longer than average. The two knobs together are what keep the stuffed note down.
"""BM25 on five bicycle repair notes.
The query is "chain oil". Plain TF-IDF lets a note that repeats "chain"
six times win. BM25 caps the repeats (k1), charges long notes (b),
and ranks the short note that has both words first.
"""
import math
# Five notes from a bike workshop. Ids match the table on the page.
DOCS = {
1: "oil chain",
2: "chain chain chain chain chain chain",
3: "brake cable chain oil gear pads tension index",
4: "tube patch",
5: "spoke wheel",
}
QUERY = "chain oil"
K1 = 1.2 # how fast repeats stop paying
B = 0.75 # how much a long note is charged for its length
def tokenize(text):
"""Lowercase, split on spaces. Every note here is already clean."""
return text.lower().split()
def avgdl(docs=DOCS):
"""Average note length, in terms. Here (2 + 6 + 8 + 2 + 2) / 5 = 4."""
return sum(len(tokenize(text)) for text in docs.values()) / len(docs)
def document_frequency(term, docs=DOCS):
"""How many notes contain the term at least once."""
return sum(term in tokenize(text) for text in docs.values())
def idf(term, docs=DOCS):
"""BM25 idf with +1 inside the log, so it never goes below 0."""
n, df = len(docs), document_frequency(term, docs)
return math.log(1 + (n - df + 0.5) / (df + 0.5))
def idf_classic(term, docs=DOCS):
"""The original form. Negative when a term is in more than half the notes."""
n, df = len(docs), document_frequency(term, docs)
return math.log((n - df + 0.5) / (df + 0.5))
def tf_part(tf, dl, avg, k1=K1, b=B):
"""Saturated, length-adjusted term frequency. It never reaches k1 + 1."""
norm = 1 - b + b * dl / avg
return tf * (k1 + 1) / (tf + k1 * norm)
def bm25(doc_id, query=QUERY, docs=DOCS, k1=K1, b=B):
"""Sum over query terms: idf times the saturated tf part."""
terms = tokenize(docs[doc_id])
avg = avgdl(docs)
score = 0.0
for term in tokenize(query):
tf = terms.count(term)
if tf:
score += idf(term, docs) * tf_part(tf, len(terms), avg, k1, b)
return score
def tfidf_sum(doc_id, query=QUERY, docs=DOCS):
"""Chapter 2's weight, summed: raw tf times log2(N / df). No cap, no length."""
terms = tokenize(docs[doc_id])
n = len(docs)
return sum(
terms.count(term) * math.log2(n / document_frequency(term, docs))
for term in tokenize(query)
if term in terms
)
def rank(score_fn, **kwargs):
"""Highest score first. Ties keep the lower id first."""
rows = [(doc_id, score_fn(doc_id, **kwargs)) for doc_id in sorted(DOCS)]
return sorted(rows, key=lambda row: -row[1])
Using the idf without the +1. Any word in more than half the notes gets a negative weight, like chain's -0.336 here. A note that mentions it ranks below one that does not. Use the +1 form unless you mean that.
Computing avgdl over the wrong tokens. dl and avgdl must count the same tokens the index stores. If you drop stop words from the postings but count them in the length, every note looks longer than it is.
Treating k1 and b as constants of nature. 1.2 and 0.75 are starting points. A corpus of one-line titles wants a small b. A corpus where repetition is meaningful, such as long manuals, can take a larger k1. Tune them on queries with known good answers.
Comparing BM25 scores across queries. A score of 1.778 means nothing alone. It depends on how many query words there are and how rare they are. Compare scores only inside one result list.
Exactly 1. With norm = 1 the fraction is (k1 + 1) / (1 + k1), whatever k1 is.
Notes 1 and 3. Both have chain once and oil once. With b = 0 their lengths no longer matter, so both score 1.414.
No. The tf part stays below k1 + 1, so chain alone can never earn more than 2.2 × 0.539 at average length.
ln(1 + 0.5 / 5.5), about 0.087. Small and positive. Without the +1 it would be ln(0.5 / 5.5), well below zero.