BM25
The ranking that refuses to die.
Search has moved on to neural embeddings, large language models, and vectors. Yet a formula from the nineteen nineties still sits inside nearly all of them. It's called BM25. Before you reach for embeddings, you should know what it does, because it's often very hard to beat.
- Neural search everywhere
- A 1990s formula inside
- Very hard to beat
Ranking by rare words
It improves on TF-IDF in two ways. First, repeats have diminishing returns, so the tenth use of a word adds much less than the first. Second, long documents get a penalty, as they contain more words by chance. We rank tickets for a messy query. Run it. Look at the top results. The first matches torn and cover, which are rare words, so they count heavily. The next match money. That's a sensible ranking, with no training at all, and no model to host.
import math
from collections import Counter
from tickets import TICKETS
docs = [t.split() for t, _ in TICKETS]
N, avg = len(docs), sum(map(len, docs)) / len(docs)
df = Counter(w for d in docs for w in set(d))
def bm25(query, doc, k=1.5, b=0.75):
tf = Counter(doc)
s = 0
for w in query.split():
idf = math.log(1 + (N - df[w] + .5) / (df[w] + .5))
s += idf * tf[w] * (k + 1) / (tf[w] + k * (1 - b + b * len(doc) / avg))
return s
query = "refund my money for the torn cover"
for score, d in sorted(((bm25(query, d), d) for d in docs), reverse=True)[:3]:
print(f"{score:.2f} {' '.join(d)}")5.59 cover is torn and the spine is broken 5.08 i want my money back for this book 3.95 please refund the second copy you charged me for
Also uses tickets.py
TICKETS = [
("my order arrived late and the box was crushed", "delivery"),
("the parcel never came, where is my delivery", "delivery"),
("courier left the package in the rain", "delivery"),
("tracking has not moved for a week", "delivery"),
("shipping took three weeks, far too slow", "delivery"),
("delivery driver was rude and threw the parcel", "delivery"),
("package is lost, nobody knows where it went", "delivery"),
("the courier says delivered but nothing arrived", "delivery"),
("i want my money back for this book", "refund"),
("please refund the second copy you charged me for", "refund"),
("you took payment twice, return my money", "refund"),
("how long does a refund take to reach my card", "refund"),
("cancel my order and give me a refund", "refund"),
("i returned the book but got no money back", "refund"),
("charged the wrong price, want the difference back", "refund"),
("refund has not appeared on my statement", "refund"),
("the book has missing pages in chapter four", "quality"),
("cover is torn and the spine is broken", "quality"),
("pages are printed upside down in the middle", "quality"),
("ink is smudged on every page", "quality"),
("the binding fell apart after one read", "quality"),
("this copy has a coffee stain on the cover", "quality"),
("wrong edition, and the print quality is awful", "quality"),
("several pages are stuck together badly", "quality"),
]
QUERIES = [
("where is my parcel, it has not arrived", "delivery"),
("i need my money back please", "refund"),
("the pages are torn and the cover is bent", "quality"),
("courier lost my package", "delivery"),
("refund the payment to my card", "refund"),
("print is smudged and hard to read", "quality"),
]Keywords or meaning?
So do you want keyword search, or vector search? Vectors find meaning, so a search for money back finds refund. Keywords are exact, so a product code like AB twelve thirty four gets found every time. Each one fails where the other's strong. The best modern systems use both together, and that's called hybrid search.
Keyword search
- Exact matches, codes, names
- No model needed
- Misses synonyms
Vector search
- Finds meaning
- Needs an embedding model
- Misses exact codes
Summary
BM25 is simple, free, and strong. Use it alongside your vectors. Next, how a search box can finish your sentence.
Key takeaways- Rare words count more
- Repeats have diminishing returns
- Hybrid search uses both