Keyword Search: BM25

The inverted index tells you which documents match. It says nothing about which match best. That second question, ranking, is where a search engine earns its keep. For text, the answer has been the same for decades: BM25.

Imagine flipping through a stack of newspapers to find every article about a flood in your town. One that mentions the flood ten times is probably more about it than one that mentions it once, but after the third or fourth time you are already sure, and each extra mention tells you less. And a rare word, like your town's name, is a much stronger signal than a common one like "water". BM25 is that everyday instinct written down as a formula.

From matching to scoring

In How Search Works the pipeline split into two halves. Matching narrows a million documents to a few thousand candidates using the inverted index. Ranking then scores those candidates and returns the best few. This piece is about the scoring function, and for keyword search the default, in Lucene, Elasticsearch, and OpenSearch, is BM25.

BM25 is not magic. It is a careful version of an old intuition: a document is a good match for a term when the term shows up a lot, in a short document, and the term is rare across the collection. Three forces. That is the whole idea, and the rest is making each force behave.

The three forces

Term frequency, with diminishing returns. Search for payment. A document that says "payment" five times is a better match than one that says it once. But the jump from one mention to two matters far more than the jump from twenty to twenty-one. If frequency counted linearly, a spam page that repeats "payment payment payment" two hundred times would outrank the actual documentation. BM25 lets frequency help while saturating, so repetition gives fast-diminishing returns and cannot win on its own.

Document length. The word payment appears once in a 20-word support ticket and once in a 5,000-word contract. Same raw count, but in the ticket it is almost certainly the topic, while in the contract it is one incidental mention. A long document contains more of every word just by being long, so a raw count quietly favors it. BM25 divides that advantage out: the same term counts for more in a short, focused document than in a sprawling one.

Term rarity (IDF). Consider the query the photosynthesis process. The word "the" is in essentially every document, so matching it tells you nothing at all. "photosynthesis" might appear in 10 documents out of 1,000, so matching it is a strong signal about what the document is about. Inverse document frequency, IDF, is the number that captures this. Using BM25's formula below, the IDF of "the" (in nearly all 1,000 documents) is about 0.0005, essentially zero, while the IDF of "photosynthesis" (10 of 1,000) is about 4.6. The rare word carries the entire match; the common word is silently ignored.

The formula

Put the three forces together and you get BM25. For a query, it sums a per-term score over every query term:

score(D, Q) = sum over query terms t of:
    IDF(t) * ( f * (k1 + 1) ) / ( f + k1 * (1 - b + b * |D|/avgdl) )

IDF(t) = ln( 1 + (N - n + 0.5) / (n + 0.5) )

That looks dense, so walk one term through it. Take photosynthesis, appearing f = 3 times in a document of average length, with the usual k1 = 1.2 and b = 0.75.

• IDF comes from N = 1000 total documents and n = 10 that contain the term: ln(1 + 990.5/10.5) ≈ 4.6. Rare term, high weight.
• The fraction is the saturating term-frequency part. With average length, 1 - b + b*(|D|/avgdl) is just 1, so it is 3 * 2.2 / (3 + 1.2) ≈ 1.57.
• The score for this term is 4.6 * 1.57 ≈ 7.2.

Now the key idea. No matter how many times the term repeats, that fraction can never pass k1 + 1 = 2.2, so the term's score can never pass IDF * (k1 + 1) = 4.6 * 2.2 ≈ 10.1. That is the ceiling, and just three good occurrences already got us to 7.2 of it. The gap between 7.2 and 10.1 is all that infinite extra repetition could ever buy. That is saturation, made concrete.

The two knobs: k1 and b

Everything tunable in BM25 lives in two parameters, and each has a plain effect.

k1 controls saturation. Keep the same term (IDF 4.6) in an average-length document and add occurrences one at a time:

• 1 occurrence scores about 4.6
• 2 occurrences: 6.3
• 5 occurrences: 8.1
• 20 occurrences: 9.5

The first extra mention adds 1.7 points. Going from 5 mentions to 20, fifteen more, adds barely 1.4. k1 sets how fast that curve flattens: raise it and frequency keeps paying off for longer, lower it and it saturates almost immediately. The default is 1.2 in Lucene and Elasticsearch.

b controls length normalization. Take the same three occurrences of photosynthesis. In a document half the average length the score is about 8.0; in one twice the average length it is about 5.9. Same term, same count, but the long document is penalized. b sets how hard, from 0 to 1: at b = 0 length is ignored entirely (both documents would score the same), at b = 1 it is fully normalized. The default is 0.75, a deliberate middle ground: penalize long documents, but not so hard that a thorough, legitimately long document is buried.

Now play with it

The concept is on the table, so here is all of it in one place. Drag the sliders and watch the pieces move: the curve bends as k1 changes how fast frequency saturates, the whole score sinks as b punishes length, and the ceiling drops as the term gets more common (higher rarity count means lower IDF).

Why BM25 is still the baseline

BM25 is old, cheap, has no training, and needs no GPU. It also remains stubbornly hard to beat. Modern neural rankers and vector search improve on it for meaning and paraphrase, but they are almost always measured against BM25, and hybrid systems keep it in the loop precisely because it is so strong on exact terms, rare words, and the codes and names that embeddings fumble. Knowing what BM25 rewards is knowing what "good keyword match" formally means.

What it still cannot do is forgive a typo or match a synonym. The next part is about the first of those: fuzzy and prefix search, matching through misspellings and as you type.