Information retrieval & BM25

Bag-of-words and TF-IDF tell you how to represent a document. Information retrieval (IR) is the system that uses those representations to answer a query — find the documents most relevant to “best italian restaurant,” out of millions, in milliseconds. Two pieces make it work: an inverted index for speed, and a ranking function for relevance.

The inverted index: don’t scan, look up

Checking every document against the query is O(N) — hopeless at web scale. The trick is to invert the data. Instead of “document → its words,” build “word → the documents containing it” — a postings list per term. A query then jumps straight to the documents that contain its terms, never touching the rest.

BM25: a smarter TF-IDF for ranking

Once you have the candidate documents, you rank them. Plain TF-IDF works, but BM25 (Best Matching 25) — the long-standing default in Lucene, Elasticsearch, and friends — fixes two things TF-IDF gets wrong:

• TF saturation — ten occurrences of a word don’t make a document ten times more relevant. BM25 lets term frequency saturate (a k1 parameter), so the benefit of repeats levels off.
• Length normalization — a term in a short, focused document is more telling than the same term buried in a long one. BM25 normalizes by document length (a b parameter).

import math

corpus = ["the cat sat on the mat", "the dog chased the cat", "dogs and cats are common pets"]
docs = [d.split() for d in corpus]
N = len(docs); avgdl = sum(len(d) for d in docs) / N

def idf(term):
    df = sum(term in d for d in docs)
    return math.log(1 + (N - df + 0.5) / (df + 0.5))

def bm25(query, d, k1=1.5, b=0.75):
    s = 0.0
    for term in query:
        tf = d.count(term)
        if tf:
            s += idf(term) * (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * len(d) / avgdl))
    return s

for i in sorted(range(N), key=lambda i: bm25(["cat"], docs[i]), reverse=True):
    print(f"doc{i} score={bm25(['cat'], docs[i]):.3f}  {corpus[i]!r}")

doc1 score=0.496  'the dog chased the cat'
doc0 score=0.458  'the cat sat on the mat'
doc2 score=0.000  'dogs and cats are common pets'

Two things to notice. doc1 outranks doc0 even though both contain cat exactly once — because doc1 is shorter, so length normalization gives its match more weight. And doc2 scores zero: it contains cats, not cat, and BM25 only matches exact terms.

The lexical gap — and hybrid search

That zero is the whole limitation. BM25 (like all bag-of-words methods) matches surface terms, so it misses morphology (cat vs cats — which is why you stem first) and is blind to meaning (car vs automobile, a query and a paraphrase). It can’t retrieve a document that’s clearly relevant but shares no exact words.

In one breath

• Information retrieval finds relevant documents for a query at scale with two pieces: an inverted index (speed) and a ranking function (relevance).
• The inverted index maps term → documents containing it, turning search from an O(N) scan into a direct lookup of the query terms’ postings.
• BM25 refines TF-IDF for ranking with TF saturation (repeats give diminishing returns, k1) and length normalization (terms in short docs count more, b) — the demo’s shorter doc1 outranks doc0.
• BM25 matches exact terms only — the lexical gap: it misses morphology (cat/cats, scoring doc2 zero) and meaning (synonyms), so stem first and don’t expect semantics.
• Modern search is hybrid: BM25 (exact/rare terms) + dense retrieval (meaning), scores fused — a decades-old baseline that’s still essential.

Quick check

Next

BM25 is the lexical half of retrieval; the semantic half is dense embeddings and RAG. The morphology gap that zeroed doc2 is why you preprocess and stem first.