BM25 and Inverted Indexes

Why Does This Exist?

Before the era of dense vector embeddings and neural networks, search engines relied entirely on lexical (keyword-based) search. If you typed "red shoes" into a search bar, the engine looked for documents that contained the exact words "red" and "shoes".

Even today, in the age of generative AI and semantic search, lexical search remains a foundational technology. It is exceptionally fast, highly explainable, and excels at exact-match queries where semantic search often fails (e.g., searching for a specific product ID, a rare technical term, or a person's name).

The industry standard for lexical search is built on two core components: the Inverted Index (the data structure that makes searching fast) and BM25 (the mathematical formula that scores how relevant a document is to a query). Modern retrieval systems, particularly Retrieval-Augmented Generation (RAG) pipelines, almost always use a hybrid approach that combines BM25 for exact keyword matching with dense embeddings for semantic understanding.

Think of It Like This

How It Actually Works

The Inverted Index

An inverted index is a hash map (or dictionary) where the keys are every unique term (word or token) in your entire corpus, and the values are lists of document IDs that contain that term.

1. Tokenization: Every document in the database is split into tokens. Punctuation is removed, words are lowercased, and often reduced to their root forms (stemming). Stop words (like "the", "is", "and") are frequently discarded.
2. Indexing: For each token, the document's ID is appended to the token's list in the index.
3. Retrieval: When a query arrives (e.g., "fast car"), the engine splits it into "fast" and "car". It looks up "fast" in the inverted index and gets a list of document IDs (e.g., [Doc1, Doc4, Doc9]). It looks up "car" and gets [Doc4, Doc7]. The intersection or union of these lists determines the candidate documents.

Because hash map lookups are $O(1)$, an inverted index allows a search engine to instantly find all documents containing a keyword, even if the database contains billions of records.

The BM25 Algorithm

Once you have the candidate documents, you need to rank them. Best Matching 25 (BM25) is a robust variation of TF-IDF (Term Frequency-Inverse Document Frequency) that fixes some of its flaws. It scores a document $D$ for a query $Q$ (containing terms $q_i$) based on three main factors:

1. Term Frequency (TF): How many times does the query term appear in the document? More appearances = higher score.
2. Inverse Document Frequency (IDF): How rare is the query term across the entire database? If a word appears in every document (like "the"), it is useless for distinguishing relevance, so it gets a low IDF. If a word is rare (like "chupacabra"), finding a document that contains it is a strong signal, so it gets a high IDF.
3. Document Length Normalization: This is where BM25 shines compared to raw TF-IDF. A 10,000-word document is more likely to contain the word "apple" just by chance than a 50-word document. BM25 penalizes long documents, leveling the playing field so short, highly-focused documents can rank well.

The BM25 Formula

The score of document $D$ for query $Q$ is the sum of the scores for each term $q_i$:

• $f(q_i, D)$ is the term frequency of $q_i$ in $D$.
• $|D|$ is the length of the document.
• $\text{avgdl}$ is the average document length in the corpus.
• $k_1$ is a tuning parameter (usually 1.2 to 2.0) that caps the effect of term frequency. (Seeing a word 10 times is better than 1 time, but seeing it 100 times isn't much better than 10 times).
• $b$ is a tuning parameter (usually 0.75) that controls how much document length penalizes the score.

Show Me the Code

You don't usually implement an inverted index from scratch (you'd use Elasticsearch or OpenSearch). However, the rank_bm25 Python package allows us to easily compute BM25 scores to see how it works in memory.

1from rank_bm25 import BM25Okapi2
3# 1. Our corpus of documents4corpus = [5    "The quick brown fox jumps over the lazy dog",6    "A fast brown fox",7    "The dog is lazy",8    "Artificial intelligence is fascinating",9    "The fast fox is not lazy"10]11
12# 2. Tokenize the corpus (simple whitespace split for demonstration)13tokenized_corpus = [doc.lower().split(" ") for doc in corpus]14
15# 3. Initialize the BM25 index16bm25 = BM25Okapi(tokenized_corpus)17
18# 4. Our query19query = "fast fox"20tokenized_query = query.lower().split(" ")21
22# 5. Get the BM25 scores for each document23scores = bm25.get_scores(tokenized_query)24
25print("BM25 Scores:")26for i, score in enumerate(scores):27    print(f"Doc {i}: {score:.4f} - '{corpus[i]}'")28
29# -> BM25 Scores:30# -> Doc 0: 0.1705 - 'The quick brown fox jumps over the lazy dog'31# -> Doc 1: 1.5833 - 'A fast brown fox'32# -> Doc 2: 0.0000 - 'The dog is lazy'33# -> Doc 3: 0.0000 - 'Artificial intelligence is fascinating'34# -> Doc 4: 1.1396 - 'The fast fox is not lazy'35
36# Doc 1 wins because it contains both terms ("fast" and "fox") 37# and is shorter than Doc 4, meaning those words represent a 38# higher density of the document's total content.

Watch Out For

The Quick Version

• Lexical search relies on exact keyword matching, which is fast and explainable.
• An Inverted Index is a hash map connecting every unique word to a list of documents containing that word, enabling $O(1)$ lookup times.
• BM25 is the industry-standard algorithm used to score the relevance of the documents found in the inverted index.
• BM25 improves upon TF-IDF by capping the reward for repeating the same word, and by penalizing long documents that contain the word simply by chance.

What to Read Next

• Read Learned Sparse Retrieval (like SPLADE) to see how neural networks can inject synonyms and contextual weights directly into an inverted index.
• Read Hybrid Search to understand how BM25 scores are mathematically combined with dense embedding scores (via Reciprocal Rank Fusion) in modern RAG pipelines.
• Read Embedding Models to understand the semantic alternative to lexical search.