BM25 and the inverted index

BM25 ranks documents for a text search. Lucene, Elasticsearch and OpenSearch use it by default.

A rare word counts more than a common word.
A repeated word helps, but less each time.
A long document loses points.
An index finds the right documents fast.

Try this: drag b to 0 and watch Doc B. Then switch on the index lookup.

Try it

What just happened

Search for “car repair” in your notes and you would open the best note first. BM25 picks it with three habits. Each picture below shows one.

The index saves work. It keeps one list per word and reads only the lists for your words, so Doc C is never opened. Switch on the index lookup above to see the lists.

Show the formula

Each query word gives points. The score is the sum of the points. This is the version used by Lucene and the bm25s library.

points = rarity × count effect rarity = ln(1 + (N − df + 0.5) / (df + 0.5)) count effect = tf / (tf + k1 × (1 − b + b × length / average length))

Here N is the number of documents, df is how many documents have the word, and tf is how many times this document has it. The original paper also multiplies by (k1 + 1). That number is the same for every document, so the order does not change.

Where you meet it

Say you search a help site for ERR_CONN_RESET. A search by meaning might return pages about network problems in general. BM25 returns the pages that contain that exact code. When the exact word matters, such as an error code, a product name or a person's name, BM25 is hard to beat.

Elasticsearch ranks text results with BM25 by default.
SQLite's full-text search has a built-in bm25() ranking function.
Many AI search and RAG systems run BM25 next to a search by meaning, then merge the two lists.
The BEIR benchmark paper uses BM25 as a strong baseline that newer models must beat.

Where it breaks

BM25 matches spellings. Doc C is about cars, but it says “automobile”, so a search for “car” gives it 0. Pick a search below.

A search for “automobile” finds only Doc C (). Stemming cannot fix this, because the two words share no root. People fix it with a synonym list, by adding words to the query, or with a search that compares meaning using embeddings.

Check yourself

You add 100 unrelated words to a document. What happens to its score? What happens to the other scores?

Its score goes down when b is above 0, because the same matches are now spread over more words. At b = 0 it stays the same. The other documents go up a little, because the average length grew and they now look shorter.

A word is in every document. Does it still add points?

Yes, but very few. With N documents its rarity is ln(1 + 0.5 / (N + 0.5)), which is above 0 and close to it. The older formula gave 0 or less, and Lucene changed that.

What is the score when k1 is 0?

The count effect becomes 1 for any word the document has. The score is then the sum of the rarity of the matching words. Counts and length stop mattering. Drag k1 to 0 and Doc A and Doc B tie.

Used in

Loading…

Go deeper

Robertson and Zaragoza, “The Probabilistic Relevance Framework: BM25 and Beyond” (2009). Where the formula comes from, written by its authors.
Kamphuis, de Vries, Boytsov and Lin, “Which BM25 Do You Mean?” (ECIR 2020). Libraries ship different versions under the name BM25. This paper compares them and finds small differences.
Lù, “BM25S: Orders of magnitude faster lexical search via eager sparse scoring” (2024). The library this page's tests are checked against. It works out scores ahead of time, when it builds the index.