Skip to content
AI360XpertBeta

BM25 and Inverted Indexes

An inverted index files every word under the documents that hold it, so lookup is instant, and BM25 ranks those matches by how often the word appears, how rare it is, and how long the document runs.

Given the query fox, the inverted index finds D1 and D2, and BM25 ranks D2 first at 0.6811 because fox appears twice in a short document
Given the query fox, the inverted index finds D1 and D2, and BM25 ranks D2 first at 0.6811 because fox appears twice in a short document

Why Does This Exist?

You have a million documents and one query. Reading every document per query is hopeless, and asking a neural model to score each one costs far too much for a first pass. You need something that finds candidates in milliseconds and orders them sensibly. That is the job lexical search has done for decades, and it still does it inside most production RAG systems.

The trick has two halves. An inverted index flips storage around: instead of mapping each document to its words, it maps each word to the documents holding it, so every document with "fox" is one dictionary lookup. BM25 then decides their order. It fixes the two flaws that made plain word counting unreliable: repeats scored without limit, and long documents won by accident of length.

This page covers the lexical half of retrieval: the index structure and the scoring formula, with numbers you can check by hand. The other half is matching by meaning with vectors, in semantic search. Most systems run both and merge the lists, which is hybrid search. Whatever gets retrieved ends up inside the prompt of a RAG pipeline.

Two counts carry the whole idea, so get them straight now. Term frequency is how often the query word appears inside one document. Document frequency is how many documents in the whole collection hold the word at all. Rare words discriminate between documents; words on every page do not. The older weighting built directly on those counts is TF-IDF, and BM25 is best read as its repaired successor.

Think of It Like This

The index at the back of a thick textbook

Say you own a 1,000-page history book and you want every passage about Lincoln. Reading front to back is the naive search. The index at the back is the inverted index in miniature: each name points to a list of page numbers, and those page numbers are document IDs. A whole chapter on Lincoln is high term frequency. A name printed on nearly every page is low inverse document frequency, useless for choosing. Deciding which page to read first is BM25.

Where it stops: a book index lists occurrences and never judges them. It does not discount long chapters, does not tire of the twentieth mention of a name, and drops nothing. BM25 does both kinds of discounting on purpose, and a real search index throws away stop words and word endings through tokenization before anything is stored.

How It Actually Works

From documents to postings

A document is one retrievable unit: a chunk, a page, a row. What counts as a unit matters more than beginners expect, and chunking strategies is where that choice is made. A term is a token after lowercasing, stripping punctuation, and often stemming, so "Fox" and "foxes" file under one key. Each term owns a postings list: the IDs of the documents holding it, plus how many times each one does.

Indexing runs once, before any query arrives. Tokenize each document, and append its ID to every one of its terms' postings lists. Query time mirrors it: tokenize the query the same way, pull each term's postings, and combine them into candidates. Each pull is a hash probe, which is why collections of billions of documents stay searchable in milliseconds. The price is paid up front in disk: every distinct term keeps its own list, and that index is rebuilt or updated whenever the corpus changes.

Scoring one term

Candidates found, they must be ordered. BM25 scores a document DD against a query QQ by summing one contribution per query term, ignoring order and proximity. That bag-of-words blindness is the method's core assumption, and everything in bag of words applies here: what it buys is speed, and what it costs is meaning.

Score(D,Q)=∑q∈QIDF(q)⋅f(q,D)⋅(k1+1)f(q,D)+k1⋅(1−b+b⋅∣D∣avgdl)\text{Score}(D, Q) = \sum_{q \in Q} \text{IDF}(q) \cdot \frac{f(q, D) \cdot (k_1 + 1)}{f(q, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}

Every symbol, in plain words:

  • f(q,D)f(q, D), the term frequency: how many times qq appears in DD. Zero means the term contributes nothing, and the document can only score through other query terms.
  • IDF(q)\text{IDF}(q), the inverse document frequency: how much information a match carries, high for rare terms and near zero for words found everywhere.
  • ∣D∣|D|, the length of DD in tokens, and avgdl\text{avgdl}, the mean document length across the corpus.
  • k1k_1, the saturation knob, almost always left at 1.2. It caps how much repeats can earn.
  • bb, the length knob, almost always left at 0.75. At 0 there is no length penalty; at 1 the penalty is full.

The IDF used with BM25, the Robertson form, is:

IDF(q)=ln⁡ ⁣(N−n(q)+0.5n(q)+0.5+1)\text{IDF}(q) = \ln\!\left(\frac{N - n(q) + 0.5}{n(q) + 0.5} + 1\right)

Here NN is the total document count and n(q)n(q) the number of documents holding qq. Read it as a rarity meter: a term in 2 of 3 documents scores low, a term in 1 of a million scores high. The halves keep it defined at the edges, and the trailing +1+1 keeps it from going negative for terms found nearly everywhere.

Two behaviors fall out of the fraction, and both are worth reading off rather than memorizing. First, saturation: as ff grows, the term factor approaches k1+1k_1 + 1, which is 2.2 at the default. The tenth mention of a word earns almost nothing over the ninth. Second, length normalization: when ∣D∣|D| equals avgdl\text{avgdl} the norm factor is exactly 1, shorter documents get a value below 1 (a lift), and longer ones above 1 (a penalty). A short focused page can outrank a long rambling one holding the same words.

The trade is now visible. BM25 buys speed, exact matching, and scores you can explain term by term, for zero understanding of language. Synonyms, paraphrase, and typos all score exactly zero. So don't use it alone when the query and the documents might say the same thing in different words. That condition is precisely what vectors handle, and the side-by-side evidence is in the dense versus sparse versus hybrid retrieval comparison.

Worked example

Three tiny documents, query "fox", defaults k1=1.2k_1 = 1.2 and b=0.75b = 0.75:

  • D1: "fast fox runs", length 3, fox appears once.
  • D2: "fox fox naps", length 3, fox appears twice.
  • D3: "dog sleeps all day long", length 5, fox absent.

The mean length is avgdl=(3+3+5)/3=11/3≈3.6667\text{avgdl} = (3 + 3 + 5) / 3 = 11/3 \approx 3.6667. With N=3N = 3 and n(fox)=2n(\text{fox}) = 2:

IDF(fox)=ln⁡ ⁣(3−2+0.52+0.5+1)=ln⁡(1.6)≈0.4700\text{IDF}(\text{fox}) = \ln\!\left(\frac{3 - 2 + 0.5}{2 + 0.5} + 1\right) = \ln(1.6) \approx 0.4700

Both hits are shorter than average, so both get the same lift: 1−0.75+0.75⋅3/3.6667≈0.86361 - 0.75 + 0.75 \cdot 3 / 3.6667 \approx 0.8636.

For D1, with f=1f = 1: the term factor is 1⋅2.2/(1+1.2⋅0.8636)=2.2/2.0364≈1.08041 \cdot 2.2 / (1 + 1.2 \cdot 0.8636) = 2.2 / 2.0364 \approx 1.0804, giving 0.4700⋅1.0804≈0.50780.4700 \cdot 1.0804 \approx 0.5078.

For D2, with f=2f = 2: the factor is 2⋅2.2/(2+1.2⋅0.8636)=4.4/3.0364≈1.44912 \cdot 2.2 / (2 + 1.2 \cdot 0.8636) = 4.4 / 3.0364 \approx 1.4491, giving 0.4700⋅1.4491≈0.68110.4700 \cdot 1.4491 \approx 0.6811.

D3 holds no fox, so it scores 0 without any arithmetic. Final order: D2 first, D1 second, D3 last. Notice that doubling the mentions moved the score from 0.5078 to 0.6811, a factor of about 1.34 rather than 2. That shortfall is saturation doing its job. These are the numbers drawn in the diagram above and printed by the snippet below.

Code

The point of this snippet is a check, not the formula retyped. It recomputes the worked example with the standard library only, so you can confirm the arithmetic instead of taking it on faith.

import math

def idf(n_containing: int, n_total: int) -> float:    """Rarity of a term: high when few documents hold it."""    return math.log((n_total - n_containing + 0.5) / (n_containing + 0.5) + 1)

def bm25_term_score(tf: int, doc_len: int, avg_len: float, idf_value: float, k1: float = 1.2, b: float = 0.75) -> float:    """One query term's BM25 contribution for one document."""    length_norm = 1 - b + b * doc_len / avg_len    return idf_value * (tf * (k1 + 1)) / (tf + k1 * length_norm)

docs: list[list[str]] = [    ["fast", "fox", "runs"],    ["fox", "fox", "naps"],    ["dog", "sleeps", "all", "day", "long"],]avg_len = sum(len(d) for d in docs) / len(docs)idf_fox = idf(2, 3)scores = [bm25_term_score(d.count("fox"), len(d), avg_len, idf_fox) for d in docs]print(round(idf_fox, 4))  # -> 0.47print([round(s, 4) for s in scores])  # -> [0.5078, 0.6811, 0.0]

D2 wins for exactly the reason the prose gave: two mentions in a short document. D3 never enters the ranking because "fox" has no postings entry pointing at it.

Watch Out For

Zero scores for words that mean the same thing

Your query says "car" and the document says "automobile". BM25 scores that pair at zero, confidently. Same for a typo like "recieve" against "receive", or "LLM" against "large language model". The symptom in production is exact-match misses sitting next to the right answer in your logs: the document you wanted was retrieved for other terms or not at all, while a weaker literal match ranked.

The cause is structural, not a tuning slip. Postings lists match literal tokens, so anything the analyzer did not reduce to the same token does not match. Fix it in two layers. First, index and query with the same analyzer: lowercase, stem, and strip what your domain treats as noise. Second, when wording genuinely varies, stop asking lexical search to do a semantic job. Pair BM25 with dense retrieval as hybrid search, or move to its learned upgrade in learned sparse retrieval, which expands documents with related terms at index time.

Comparing raw BM25 scores across queries

A cutoff like "keep everything above 5.0" works for one query and empties the next. Averaging a BM25 score with a cosine similarity to merge two systems lets whichever scale runs hotter dominate the ranking for reasons that have nothing to do with relevance. Both look like reasonable engineering until the evaluation numbers come back strange.

BM25 scores are unbounded and query dependent: they inherit the IDF magnitudes of whatever terms happened to match, so a 12.4 and a 0.8 from two queries mean nothing side by side. They rank documents within one query only. Never threshold them across queries, and never average them with another system's raw numbers. Fuse by rank position instead, with reciprocal rank fusion as used in hybrid search, and let a reranker rescore the shortlist on one shared scale before anything reaches the model.

The Quick Version

  • An inverted index files each term under the documents holding it, so finding candidates is a dictionary probe instead of a scan of every document.
  • BM25 scores a document by summing, over query terms, IDF times a term frequency factor that rewards repeats less and less.
  • IDF runs high for rare terms and near zero for words found everywhere, so the rare matches decide the ranking.
  • Term frequency saturates: at the default k1 of 1.2 the factor caps at 2.2, and the tenth mention earns almost nothing over the ninth.
  • Length normalization lifts short documents and penalizes long ones around the corpus average, so focus can beat bulk.
  • BM25 matches literal tokens only, so synonyms and typos score zero. Pair it with vector search when wording varies.