FINDING NEEDLES · CHAPTER 03

BM25

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.

~15 min read5 notesTested Python

What you'll learn

  • Why the tenth mention of a word should count less than the first
  • How k1 sets where repeats stop paying
  • How b charges a long note for being long
  • Why BM25's idf has a +1 inside the log
  • How a short note with both words beats a note that shouts one

Before you start

  • TF-IDF — tf times idf, the score BM25 repairs
  • How search works — where df and the lengths come from
  • The natural log, ln

The note that says “chain” six times

A bike workshop keeps five repair notes. You search for “chain oil”.

NoteTextLengthTF-IDF sum
1oil chain22.059
2chain chain chain chain chain chain64.422
3brake cable chain oil gear pads tension index82.059
4tube patch20
5spoke wheel20

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.

Repeats stop paying: k1

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

MANIM BM25: k1 saturates TF; b damps long documents.

repeats · sat · length · lexical

MANIM BM25 saturates term frequency and normalizes length.

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.

tfRaw tf (TF-IDF)BM25 tf part, k1 = 1.2
111.000
221.375
331.571
661.833
∞∞2.2
cap k1 + 1 = 2.2 raw tf BM25, k1 = 1.2 1236 8 0123
Term count along the bottom. Raw tf (pink) keeps climbing. The BM25 tf part (teal) bends and stays under the dashed cap.

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.

Long notes pay more: b

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 dlnormtf part for tf = 1
2 (note 1)0.6251.257
4 (the average)11.000
8 (note 3)1.750.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.

The rare-word weight, with a +1

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.

Termdf of 5BM25 idfWithout the +1Chapter 2, log2(N / df)
chain30.539-0.3360.737
oil20.8750.3361.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.

Add up one bounded part per query word

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:

  1. dl = 2 and avgdl = 4, so norm = 0.25 + 0.75 × 0.5 = 0.625.
  2. Each word has tf = 1, so each tf part is 2.2 / (1 + 1.2 × 0.625) = 1.257.
  3. Chain: 0.539 × 1.257 = 0.678. Oil: 0.875 × 1.257 = 1.101.
  4. Sum: 1.778 (the parts are rounded; the code adds the full values).
Notechain partoil partBM25TF-IDF sum
1 · oil chain0.6781.1011.7782.059
3 · eight-topic note0.3830.6211.0042.059
2 · chain × 60.93000.9304.422
4, 50000

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.

TF-IDF sum (chapter 2)

  • tf counts in a straight line
  • Length is ignored, unless you add cosine
  • idf = log2(N / df)
  • Order here: 2, then 1 and 3 tied

BM25

  • tf bends and caps at k1 + 1
  • Length is charged inside every term, by b
  • idf = ln(1 + (N − df + 0.5) / (df + 0.5))
  • Order here: 1, 3, 2
Fields and other variants

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.

Move the two knobs

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.

The scores you can re-run

bm25.pyBM25 1 > 3 > 2, TF-IDF 2 first
"""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])

Mistakes learners make

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.

What to remember

  • The tf part tf(k1 + 1) / (tf + k1) grows fast, then flattens under k1 + 1. With k1 = 1.2: 1.000, 1.375, 1.571 for one, two, three mentions, and 1.833 for six.
  • b scales k1 by the note's length over the average. Here avgdl = 4: the 2-term note earns 1.257 per word, the 8-term note 0.710.
  • BM25's idf is ln(1 + (N − df + 0.5) / (df + 0.5)). The +1 keeps a common word from going negative.
  • On “chain oil”, TF-IDF ranks the six-chain note first at 4.422. BM25 ranks oil chain 1.778, the long note 1.004, the six-chain note 0.930.

Check yourself

1. What does a single mention score in the tf part, for a note of average length?

Exactly 1. With norm = 1 the fraction is (k1 + 1) / (1 + k1), whatever k1 is.

2. You set b = 0. Which two notes tie, and why?

Notes 1 and 3. Both have chain once and oil once. With b = 0 their lengths no longer matter, so both score 1.414.

3. Can any number of repeats of chain in one note beat the cap?

No. The tf part stays below k1 + 1, so chain alone can never earn more than 2.2 × 0.539 at average length.

4. A new word appears in all five notes. What is its BM25 idf?

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.

Go to the source

Keep going