BM25 Keyword Search

Plain vector search misses exact terms: order IDs (SE1042), product codes, brand names, "COD". Embeddings capture meaning, not exact spelling. Keyword search catches exactly these, so good RAG systems use both.

BM25 ("Best Matching 25") is the standard keyword ranking function used by search engines for decades. Given a query, it gives every document a relevance score based on which query words the document contains, how often, and how rare those words are across the collection. It needs no model and no training, runs in milliseconds over millions of documents, and is fully explainable: you can always see which words matched.

Think of the index at the back of a textbook. It lists every important word and the pages where it appears. To answer "COD limit", you look up "COD", find the pages, and prefer the page where it appears most and that is not 40 pages long. BM25 is a careful mathematical version of that habit, built on an inverted index (word → list of documents).

• Term frequency: a document that contains the query word more often scores higher, but with diminishing returns (k1).
• Inverse document frequency: rare words (like "COD") count more than common words (like "the").
• Length normalisation: long documents do not win just because they are long (b).

A worked feel for the numbers: with five documents, a word found in only one of them has IDF = ln((5 − 1 + 0.5)/(1 + 0.5) + 1) = ln(4) ≈ 1.39, while a word found in all five has IDF = ln(0.5/5.5 + 1) ≈ 0.09. So a match on the rare word carries about 16 times the weight of a match on a word every document uses. For term frequency, with k1 = 1.5 the second occurrence of a word adds much less than the first, and the score can never grow past k1 + 1 times the IDF, so repeating "refund" fifty times in a page does not game the ranking. The b = 0.75 setting decides how strongly long documents are penalised (0 = no penalty, 1 = full).

import math, re
from collections import Counter

DOCS = {
    "returns":  "Most items can be returned within 10 days of delivery. Electronics have a 7 day replacement only policy.",
    "refunds":  "Refunds go back to the original payment method within 5 to 7 working days after pickup.",
    "cod":      "Cash on delivery (COD) is available for orders up to 50000 rupees.",
    "shipping": "Standard delivery takes 3 to 5 days. Express delivery in metro cities takes 1 day.",
    "warranty": "Electronics come with a 1 year manufacturer warranty at the brand service centre.",
}

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

class BM25:
    def __init__(self, docs, k1=1.5, b=0.75):
        self.ids = list(docs)
        self.toks = [tok(docs[i]) for i in self.ids]
        self.avgdl = sum(len(t) for t in self.toks) / len(self.toks)
        self.df = Counter(w for t in self.toks for w in set(t))
        self.k1, self.b, self.n = k1, b, len(self.toks)

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

    def score(self, query, i):
        tf, dl, s = Counter(self.toks[i]), len(self.toks[i]), 0.0
        for w in tok(query):
            f = tf.get(w, 0)
            if f:
                s += self.idf(w) * f * (self.k1 + 1) / (f + self.k1 * (1 - self.b + self.b * dl / self.avgdl))
        return s

    def search(self, query, k=3):
        ranked = sorted(((self.score(query, i), d) for i, d in enumerate(self.ids)), reverse=True)
        return [(d, round(s, 3)) for s, d in ranked[:k] if s > 0]

bm25 = BM25(DOCS)
for q in ["COD limit", "electronics replacement", "express delivery days"]:
    print(f"{q!r:28} -> {bm25.search(q)}")

'COD limit'                  -> [('cod', 1.515)]
'electronics replacement'    -> [('returns', 2.061), ('warranty', 0.926)]
'express delivery days'      -> [('shipping', 2.68), ('returns', 0.982), ('cod', 0.589)]

"COD limit" finds only the cod document: "limit" appears nowhere, and "cod" is rare, so it scores well. For "express delivery days", shipping wins clearly because it contains all three words, while returns and cod get small scores from one shared word each. Documents with a score of 0 are dropped.

You rarely write BM25 yourself: PostgreSQL full-text search (tsvector), Elasticsearch/OpenSearch, and the rank_bm25 Python package all provide it. Qdrant and Pinecone support sparse (keyword) vectors next to dense ones.

• BM25 scores documents by term frequency, rarity (IDF) and length.
• It is fast, cheap, explainable and excellent at exact terms like IDs and brand names.
• It misses synonyms and paraphrases, so combine it with embeddings.