The Inverted Index and BM25

In one line: an inverted index turns "which documents contain this word" into a list lookup, and BM25 scores the result with two corrections that took twenty years to get right.

The structure

A forward index maps document to terms. Searching it means scanning every document, which is the thing you cannot afford.

Invert it. Map each term to the list of documents containing it — a postings list, sorted by document id, usually carrying the term frequency and the positions.

A multi-term query becomes an intersection or union of sorted lists, which is linear in their length and skippable — postings lists carry skip pointers so a rare term can leapfrog through a common one's list rather than walking it.

That asymmetry produces the optimisation worth knowing: process the rarest term first. Its postings list is shortest, so it bounds the work for the whole query. A query containing both the and xylophone should be driven by xylophone.

Why term frequency alone fails

The obvious score is: count how often the query terms appear. Two problems, and BM25 is precisely the fix for both.

A term appearing ten times is not ten times more relevant. The first occurrence tells you the document is about this. The tenth tells you almost nothing new — and it lets keyword stuffing win.

Long documents contain more of everything. Score by raw counts and a hundred-page document beats a focused paragraph on every query, because it mentions everything at least once.

BM25's two corrections

score(q,d) = SUM over terms t in q of
               IDF(t) * ( tf(t,d) * (k1 + 1) )
                      / ( tf(t,d) + k1 * (1 - b + b * dl/avgdl) )

Ignore the constants and read the shape.

Saturation. As tf grows, the fraction approaches k1 + 1 and stops. The curve rises steeply from zero to one occurrence, less from one to two, and flattens. So the tenth mention adds nearly nothing — which is both closer to how people judge relevance and immune to stuffing.

Length normalisation. The dl/avgdl term divides by document length relative to the average. A long document needs proportionally more occurrences to score the same, so a focused paragraph competes with a sprawling page.

IDF does the third job, unchanged from TF-IDF: a term appearing in most documents carries little information, so it is down-weighted. This is why the contributes essentially nothing without a stopword list.

What k1 and b do

Two knobs, and being able to say what each controls is a genuine differentiator.

k1 controls how fast saturation happens — the term frequency curve's steepness. Typical default around 1.2. Raise it and term frequency matters more, which suits long documents where repetition is meaningful. Lower it and one occurrence is nearly as good as five, which suits short fields.

b controls how hard length normalisation bites, from 0 (ignore length entirely) to 1 (fully normalise). Typical default 0.75. Set b = 0 for fields where length is not a signal — a product title is not less relevant for being longer, it is just more descriptive. That is a real tuning move, not a theoretical one.

Which points at per-field scoring: a title, a description and a review body deserve different parameters and different weights, because length means something different in each. Scoring them as one concatenated blob is a common and costly simplification.

Why it has survived

BM25 is from the 1990s and remains the baseline that new retrieval methods are measured against. It is worth being able to say why.

It needs no training data, so it works on day one for a brand-new corpus. It is interpretable — you can explain any score. It is fast, because the index does the work. It handles exact matches perfectly, which is what part numbers, model codes and names require. And it degrades gracefully on queries it has never seen, because it has no notion of "seen".

Its weaknesses are exactly the vocabulary ones: it cannot match laptop to notebook, or car to automobile, without an explicit synonym list. It has no idea what words mean.

The parts people forget

Field weighting. Matching in a title is worth far more than matching in a footer. BM25F is the variant that handles multiple fields properly, combining term frequencies across fields with per-field weights before saturation rather than scoring fields separately and summing — which matters, because saturating each field independently double-counts.

Static quality signals. BM25 measures query-document match and knows nothing about whether a document is any good. Popularity, authority, freshness and stock status all have to be combined in, and in a learned ranker they become features alongside the BM25 score.

Phrase and proximity. Positions in the postings list allow phrase matching and proximity scoring — terms appearing near each other score higher. Cheap, and it is the difference between matching red shoes in a sentence and matching a document that says red in the title and shoes in the footer.

Next: closing that blind spot without losing what BM25 does well.