Keyword Search and BM25

Inverted indexes, TF-IDF and BM25 built from scratch, and why keyword search still beats embeddings for some queries.

• Intermediate
• 24 min read
• 3 objectives

Before this lessonLesson 7: Chunking, Vector Databases and ANN Search

Here is a plot twist for a course about modern AI: a 1990s keyword algorithm called BM25 still beats fancy embeddings on a lot of real queries, and every serious search system, including the ones behind RAG chatbots, uses it. Search "ERR-4471" or a person's surname or a rare product name, and semantic search shrugs while BM25 nails it. Let us understand it properly, and build it.

Keyword search in one picture: the inverted index

A book has an index at the back: for each term, the pages it appears on. A search engine builds the same thing for documents, called an inverted index: a dictionary from each word to the list of documents containing it. To answer a query you look up each query word and combine the lists. No scanning of every document.

import re
from collections import defaultdict

docs = {
    1: "Laptops can be returned within 30 days for a refund",
    2: "Opened software is not refundable",
    3: "Error ERR-4471 means the payment gateway timed out",
    4: "Free shipping on laptops over 50 dollars",
}

def tokenize(text):
    return re.findall(r"[a-z0-9-]+", text.lower())

index = defaultdict(set)
for doc_id, text in docs.items():
    for token in tokenize(text):
        index[token].add(doc_id)

for word in ["laptops", "refund", "err-4471", "shipping"]:
    print(f"{word:<10} -> docs {sorted(index[word])}")

# AND search: documents containing BOTH words
both = index["laptops"] & index["refund"]
print("laptops AND refund ->", sorted(both))

laptops    -> docs [1, 4]
refund     -> docs [1]
err-4471   -> docs [3]
shipping   -> docs [4]
laptops AND refund -> [1]

That is exact keyword matching. It is fast and precise, but blunt: it treats all matches equally. Doc 1 matches "refund" once; a 50-page policy that mentions "refund" 40 times would also match, and is a document 3 is barely about. We need a way to rank. Enter TF-IDF.

TF-IDF: two very human intuitions

• TF (term frequency): if a document mentions "refund" many times, it is probably about refunds. More mentions, higher score.
• IDF (inverse document frequency): rare words are more informative than common ones. "the" appears in every document, so it tells you nothing. "ERR-4471" appears in one, so it tells you a lot. The rarer the word across the collection, the more it counts.

TF-IDF multiplies them: score = TF × IDF. Words that are frequent here but rare everywhere win.

BM25: TF-IDF, but grown up

BM25 (Best Match 25) fixes two flaws in raw TF-IDF:

• Diminishing returns on frequency. Mentioning a word 40 times is not 40× more relevant than once. BM25's term-frequency part saturates: extra repeats add less and less. A knob k1 (typically 1.2–2.0) controls how fast.
• Length normalisation. A long document naturally contains more words. BM25 penalises length, so a short focused document beats a long rambling one with the same term count. A knob b (typically 0.75) controls how much.

score(D, Q) = sum over each query term t:

      IDF(t)  *   tf * (k1 + 1)
                 ----------------------------------------
                 tf + k1 * (1 - b + b * len(D)/avg_len)

  IDF(t) = ln( (N - n_t + 0.5) / (n_t + 0.5) + 1 )      N = #documents, n_t = #documents containing t

Do not memorise it; see it. Here is BM25 in about twenty lines, with no libraries:

import math, re
from collections import Counter

docs = [
    "Laptops can be returned within 30 days for a full refund",
    "Opened software is not refundable but laptops accessories can be refunded",
    "Error ERR-4471 means the payment gateway timed out",
    "Free shipping on laptops over 50 dollars",
    "Refund refund refund refund refund refund policy policy policy overview",
]

def tokenize(text):
    return re.findall(r"[a-z0-9-]+", text.lower())

class BM25:
    def __init__(self, docs, k1=1.5, b=0.75):
        self.k1, self.b = k1, b
        self.tokens = [tokenize(d) for d in docs]
        self.N = len(docs)
        self.avg_len = sum(len(t) for t in self.tokens) / self.N
        self.df = Counter(w for t in self.tokens for w in set(t))   # docs containing each word
        self.tf = [Counter(t) for t in self.tokens]

    def idf(self, word):
        n = self.df.get(word, 0)
        return math.log((self.N - n + 0.5) / (n + 0.5) + 1)

    def score(self, query, i):
        length = len(self.tokens[i])
        total = 0.0
        for w in tokenize(query):
            tf = self.tf[i].get(w, 0)
            if not tf:
                continue
            norm = tf + self.k1 * (1 - self.b + self.b * length / self.avg_len)
            total += self.idf(w) * tf * (self.k1 + 1) / norm
        return total

    def search(self, query, k=3):
        scored = [(self.score(query, i), i) for i in range(self.N)]
        return [(round(s, 2), docs[i]) for s, i in sorted(scored, reverse=True)[:k] if s > 0]

bm25 = BM25(docs)
for q in ["laptop refund", "ERR-4471", "refund"]:
    print(f"Q: {q}")
    for score, text in bm25.search(q):
        print(f"   {score:5}  {text[:60]}")

# Saturation: how much does 6 mentions beat 1 mention?  Raw counting vs BM25
spam, normal = 4, 0                     # indexes of the two documents
raw_ratio = bm25.tf[spam]["refund"] / bm25.tf[normal]["refund"]
bm25_ratio = bm25.score("refund", spam) / bm25.score("refund", normal)
print(f"\nrefund appears {bm25.tf[spam]['refund']}x vs {bm25.tf[normal]['refund']}x")
print(f"raw counting says the spammy doc is {raw_ratio:.1f}x better")
print(f"BM25 says it is only          {bm25_ratio:.1f}x better")

Q: laptop refund
    1.73  Refund refund refund refund refund refund policy policy poli
    0.81  Laptops can be returned within 30 days for a full refund
Q: ERR-4471
    1.49  Error ERR-4471 means the payment gateway timed out
Q: refund
    1.73  Refund refund refund refund refund refund policy policy poli
    0.81  Laptops can be returned within 30 days for a full refund

refund appears 6x vs 1x
raw counting says the spammy doc is 6.0x better
BM25 says it is only          2.1x better

Two things to notice. First, the query "ERR-4471" finds the one document instantly, because that token is rare (huge IDF). An embedding model would blur it with every other error code. Second, look at the last lines: the document that repeats "refund" six times is really about refunds, so it deserves to win for the bare word, but raw counting would call it 6× better while BM25 says about 2×. Repeats add less and less (saturation) and long documents are penalised. That is the difference between BM25 and naive counting.

What BM25 is great at, and what it misses

• Great: exact terms, names, IDs, error codes, SKUs, legal citations, code identifiers, rare jargon. Fast, cheap, explainable (you can see which words matched), needs no model and no GPU.
• Misses: synonyms and paraphrase ("car" vs "automobile", "forgot my login" vs "reset my password"), and understanding intent. It only sees the words you typed.

Notice the pattern: BM25 and embeddings fail in opposite ways. Keyword search is precise but literal; semantic search understands meaning but is fuzzy about exact tokens. That complementarity is exactly why the next lesson combines them.

Improving keyword search

• Stemming / lemmatisation: reduce "returning", "returned", "returns" to one root so they match.
• Stop words: ignore "the", "is", "of" (BM25's IDF already down-weights them, so this is optional).
• Synonym lists and fuzzy matching for typos.
• Field boosts: a match in the title counts more than in the body.
• Phrase and proximity queries.

In the real world

You rarely write BM25 yourself. It is built into Elasticsearch, OpenSearch, Apache Lucene, Solr and Tantivy, into PostgreSQL full-text search (ts_rank, and extensions for true BM25), SQLite FTS5 (which literally has a bm25() function), and into vector databases with hybrid mode. Python has the rank_bm25 package for quick experiments.

# Write your solution here