Ranking with TF-IDF and BM25
Compute TF-IDF and BM25 scores by hand and explain how k1 and b change a ranking.
Which page should come first?
Search the Kaveri Institute's pages for "hostel fees" and several pages match. The Hostel Fees page does, but so do the Hostel Timings page, the academic calendar (which mentions that hostels stay open over Diwali) and a notice about hostel committee elections. A Boolean search only tells you which pages match. It cannot tell you that the fee page is the one the student wants.
Ranking solves this by giving every matching page a number, its relevance score, and sorting by that number. The ranking methods that powered search for decades, and still run behind most search boxes today, build that score from three simple clues:
- How many times the query words appear on the page.
- How rare those words are across all the pages.
- How long the page is.
This topic builds the score one clue at a time.
Clue 1: count the words (term frequency)
The first idea is simple. A page that mentions "fee" four times is probably more about fees than a page that mentions it once. The number of times a word appears on a page is its term frequency, written tf.
On the Kaveri pages, the Hostel Fees page contains "fee" 4 times and "hostel" 3 times (counting its title). That sounds like a good sign, and it is. But counting has a weakness. The Hostel Committee Notice contains "hostel" 8 times, not because it is about fees, but because it is about the hostel committee. If every mention earns the same credit, a page can win just by repeating a word.
Clue 2: rare words matter more (inverse document frequency)
The second idea is about which words are useful clues. On the Kaveri pages, "student" appears on 9 of the 13 pages. Knowing a page contains "student" tells you almost nothing. "Warden" appears on only 2 pages, so a page that contains it is very likely about hostel life.
Inverse document frequency, or idf, turns this into a number. If there are N pages and a word appears on df of them:
Do not worry about the logarithm (ln). Its job is just to keep the numbers in a sensible range. The pattern is what matters: the rarer the word, the bigger its idf.
| Word | Pages it appears on (df) | idf = ln(13 ÷ df) | How useful a clue? |
|---|---|---|---|
| student | 9 | 0.37 | weak |
| hostel | 4 | 1.18 | medium |
| fee | 3 | 1.47 | good |
| warden | 2 | 1.87 | strong |
A word that appears on every page gets an idf of ln(1) = 0, so it stops affecting the ranking at all. That is the same job a stop-word list does, but done automatically.
TF-IDF: put the two clues together
Multiply the two clues for each query word, then add them up. That gives the classic score called TF-IDF:
For the query "hostel fees":
- Hostel Fees page: hostel 3 × 1.18 + fee 4 × 1.47 = 3.54 + 5.86 = 9.40
- Hostel Committee Notice: hostel 8 × 1.18 + fee 0 = 9.43
The committee notice wins, narrowly, without mentioning fees once. TF-IDF fixed the problem of common words, but it still believes that the eighth mention of a word is worth as much as the first. Early web search engines were flooded with pages that repeated popular words for exactly this reason.
BM25: repeats count less and less
BM25 (short for "Best Matching 25") keeps the TF-IDF idea and fixes the repetition problem. It came from the Okapi search system at City University London in the mid-1990s, and it is still the most widely used ranking method of its kind.
It makes two changes.
Repeats count less and less
The first time a word appears is strong evidence. The second time adds a bit more, the third a bit less, and so on. After a few mentions, extra repeats add almost nothing, because the page has already shown it is about that word. This is called term saturation. Think of it like marks for an answer: writing the same correct point eight times does not earn eight times the marks.
Long pages are judged fairly
A long page mentions everything more often simply because it has more words. BM25 compares each page's length with the average length and gives a little less credit per mention to long pages, and a little more to short ones. This is called length normalisation.
Each extra mention adds less than the one before. That is term saturation.
The formula and its two settings
The full BM25 formula has two settings you can tune. k1 controls how quickly repeats stop counting (a common default is 1.2), and b controls how much page length matters (a common default is 0.75). You do not need to memorise the formula; it is shown below for reference.
Worked example: BM25 for “hostel fees”
With k1 = 1.2 and b = 0.75, and both pages close to the average length, the numbers come out as follows (BM25 uses a slightly different idf: 1.135 for "hostel" and 1.386 for "fee").
Hostel Fees page: "hostel" appears 3 times, which earns 1.58 × 1.135 = 1.79. "fee" appears 4 times, which earns 1.70 × 1.386 = 2.35. The total is 4.14.
Committee notice: "hostel" appears 8 times, but saturation means that only earns 1.89 × 1.135 = 2.15. There is no "fee". The total is 2.15.
Eight mentions earned the notice only about 1.2 times what three mentions earned the fee page. Under TF-IDF, it was 8 ÷ 3, or about 2.7 times.
TF-IDF lets eight repeats of “hostel” win. BM25 limits the value of repeats and puts the fee page first.
The lab below ranks the 13 Kaveri pages live. Start with TF-IDF and "hostel fees" and check that the committee notice comes first. Then switch to BM25 and watch the order change. Under each result you can see how many times each query word appears on that page.
You can also see saturation directly. The code below prints how much credit a word earns as it repeats, under plain counting and under BM25. Change k1 and run it again.
Expected output:
mentions plain count BM25 credit
1 1 1.00
2 2 1.38
3 3 1.57
5 5 1.77
8 8 1.91
20 20 2.08
The line that computes bm25 is the fraction from the formula with the page-length part removed, because for a page of average length that part equals 1. As tf grows, the top and the bottom of the fraction grow together, so the result creeps towards k1 + 1, which is 2.2, and never passes it.
Why BM25 is still everywhere
BM25 is fast, needs no training data, and works well on almost any kind of text. Lucene, the search library behind Elasticsearch, OpenSearch and Solr, made it the default ranking method in 2016. When researchers compared many modern AI-based search methods across very different collections in 2021 (the BEIR benchmark), plain BM25 was still a strong competitor that many newer methods failed to beat outside the kind of data they were trained on.
Its weaknesses are just as clear. BM25 only rewards pages that contain the exact query words (after stemming). A search for "hostel curfew" gives no credit to a page that says "gates close at 10:00 PM". It also ignores word order, so "fee late" and "late fee" score the same, and it knows nothing about what the words mean. Even so, it is always the first ranking method worth trying on a new collection, and the one any fancier method should beat.