How BM25 Works: Building a Search Engine on an Inverted Index

Type "deep learning" into a search box and something has to decide which of a million documents comes first. Before embeddings and vector databases took over the conversation, that job almost always went to BM25. It still does a lot of it: Elasticsearch, OpenSearch, Lucene, and Tantivy all use BM25 as their default ranking function, and most "hybrid search" systems run it next to their vector search.

The name comes from the Okapi retrieval system at City University London in the 1980s and 90s: "BM" stands for Best Matching, and 25 is the number of the variant that stuck.

This post builds BM25 from scratch in Python in about 50 lines. We'll build it on an inverted index, the data structure real search engines use, so scoring only touches documents that could actually match.

Try it live: bm25.derekzaw.com runs BM25 in your browser and shows every step, from tokens to postings to scores. It also stems words, so its numbers can differ slightly from the simplified code below.

The corpus

We'll use a toy corpus of four documents throughout:

documents = [
    "machine learning is useful",           # doc 0
    "deep learning uses neural networks",   # doc 1
    "machine learning and deep learning",   # doc 2
    "dogs and cats are animals",            # doc 3
]

Our query is "deep learning". Just by reading them, doc 2 looks like the best match, doc 1 is close behind, doc 0 is loosely related, and doc 3 has nothing to do with it. Let's see if BM25 agrees.

Step 1: Tokenize

Search engines don't compare strings. They compare terms. A tokenizer lowercases the text, splits it into words, and drops stopwords, the very common words like "the" and "is" that carry almost no meaning:

import re

STOPWORDS = {"the", "a", "an", "and", "or", "is", "are", "of", "to", "in"}

def tokenize(text):
    tokens = re.findall(r"[a-z0-9]+", text.lower())
    return [t for t in tokens if t not in STOPWORDS]

>>> tokenize("Machine learning and deep learning")
['machine', 'learning', 'deep', 'learning']

Production tokenizers also do stemming (so "networks" and "network" become the same term), but the idea is the same. The query and the documents must go through the same tokenizer. Otherwise their terms won't line up.

Step 2: Build the inverted index

A normal ("forward") index maps each document to the words it contains. An inverted index flips that around and maps each term to the documents that contain it:

term       -> postings {doc_id: term frequency}
animals    -> {3: 1}
cats       -> {3: 1}
deep       -> {1: 1, 2: 1}
dogs       -> {3: 1}
learning   -> {0: 1, 1: 1, 2: 2}
machine    -> {0: 1, 2: 1}
networks   -> {1: 1}
neural     -> {1: 1}
useful     -> {0: 1}
uses       -> {1: 1}

Each entry is called a postings list. Along with which documents contain a term, we also store how many times the term appears in each one, its term frequency (tf). learning -> {2: 2} means "learning" appears twice in doc 2.

That gives us almost everything BM25 needs:

Here's the index:

from collections import Counter, defaultdict

class InvertedIndex:
    def __init__(self, documents):
        self.documents = documents
        self.postings = defaultdict(dict)   # term -> {doc_id: tf}
        self.doc_lengths = []

        for doc_id, text in enumerate(documents):
            tokens = tokenize(text)
            self.doc_lengths.append(len(tokens))
            for term, tf in Counter(tokens).items():
                self.postings[term][doc_id] = tf

        self.num_docs = len(documents)
        self.avg_doc_length = sum(self.doc_lengths) / self.num_docs

>>> index = InvertedIndex(documents)
>>> index.postings["learning"]
{0: 1, 1: 1, 2: 2}
>>> index.doc_lengths, index.avg_doc_length
([3, 5, 4, 3], 3.75)

All the expensive work happens once, at index time. Queries only read from this structure.

Step 3: The BM25 formula

For a query Q made of terms q₁ … qₙ, the score of a document D is a sum over the query terms:

$$\text{score}(D, Q) = \sum_{q \in Q} \text{IDF}(q) \cdot \frac{\text{tf}(q, D) \cdot (k_1 + 1)}{\text{tf}(q, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}$$

where $\text{tf}(q, D)$ is how many times $q$ appears in $D$, $|D|$ is the length of $D$ in terms, and $\text{avgdl}$ is the average document length.

It looks dense, but it's really three ideas multiplied together:

1. IDF: rare terms matter more than common ones.
2. TF saturation: more occurrences help, but less and less each time.
3. Length normalization: a match in a short document counts for more than the same match in a long one.

Let's take them one at a time.

Idea 1: IDF (rare terms matter more)

If a term appears in every document, it tells you nothing about which document to pick. Inverse document frequency rewards terms that appear in only a few documents:

$$\text{IDF}(q) = \ln\left(1 + \frac{N - n(q) + 0.5}{n(q) + 0.5}\right)$$

Here $N$ is the total number of documents and $n(q)$ is how many of them contain $q$. With the inverted index, n(q) is just the length of the postings list:

import math

def idf(index, term):
    n = len(index.postings.get(term, {}))   # document frequency
    N = index.num_docs
    return math.log(1 + (N - n + 0.5) / (n + 0.5))

>>> for term in ["learning", "deep", "dogs"]:
...     print(term, round(idf(index, term), 3))
learning 0.357   # in 3 of 4 docs: weak signal
deep     0.693   # in 2 of 4 docs
dogs     1.204   # in 1 of 4 docs: strong signal

The 1 + inside the log is Lucene's fix to the classic formula. Without it, a term that appears in more than half the corpus gets a negative IDF, which would mean that matching it lowers a document's score.

Idea 2: TF saturation (diminishing returns)

A document that says "learning" twice is probably more about learning than one that says it once. A document that says it 20 times is not 20 times more relevant, though. It might just be keyword stuffing. BM25 caps the benefit of repetition with this term:

$$\frac{\text{tf} \cdot (k_1 + 1)}{\text{tf} + k_1}$$

With k1 = 1.5, here is what repetition is worth (IDF fixed at 1, average-length document):

The curve flattens out and never goes above $k_1 + 1 = 2.5$. k1 controls how quickly it saturates, as the chart shows:

With k1 = 0 term frequency is ignored completely: a term either appears or it doesn't. A large k1 behaves more like raw counting.

Idea 3: Length normalization

A 5,000-word document mentions "learning" once almost by accident. A 5-word title that mentions it once is clearly about learning. BM25 handles this by scaling k1 by how long the document is compared to the average:

$$k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)$$

• A document of average length gets a factor of exactly 1, so there's no adjustment.
• Longer documents get a factor above 1, so they need more occurrences to score the same.
• Shorter documents get a factor below 1, so each occurrence counts for more.

b controls how strong this is. b = 0 turns length normalization off. b = 1 normalizes fully. The usual default is b = 0.75.

To see this effect on its own, here are two documents that each contain "neural" exactly once. One is a 2-term title and the other is a 13-term survey blurb. (This uses the search function we build in Step 4. Skip ahead if you want to see it first.)

docs = [
    "neural networks",
    "neural networks are one of many tools covered in this long survey "
    "of statistics optimization databases compilers",
    "dogs and cats are animals",
]
length_demo = InvertedIndex(docs)    # lengths [2, 13, 3], avgdl 6.0

for b in (0, 0.75, 1.0):
    print(b, search(length_demo, "neural", b=b))

0     [(0, 0.470), (1, 0.470)]   # length ignored: a tie
0.75  [(0, 0.671), (1, 0.308)]   # the short doc pulls ahead
1.0   [(0, 0.783), (1, 0.276)]   # full normalization

(Output rounded to 3 decimals.) Same term, same frequency, and the only thing that changes is b. With b = 0 the title and the long blurb look identical to BM25. As b grows, the single mention in the 13-term document counts for less and less.

Putting all three ideas together, the score for one term in one document is:

def term_score(tf, doc_len, avg_len, idf_value, k1=1.5, b=0.75):
    length_norm = 1 - b + b * doc_len / avg_len
    return idf_value * (tf * (k1 + 1)) / (tf + k1 * length_norm)

Step 4: Search, term by term

This is where the inverted index pays off. The naive approach loops over every document and scores it against the query. With an inverted index we go the other way. We loop over the query terms, walk each term's postings list, and add that term's contribution to a per-document accumulator:

def search(index, query, k=10, k1=1.5, b=0.75):
    scores = defaultdict(float)             # doc_id -> accumulated score

    for term in set(tokenize(query)):
        postings = index.postings.get(term)
        if not postings:
            continue                        # term not in corpus, contributes nothing

        term_idf = idf(index, term)         # computed once per term, not per doc
        for doc_id, tf in postings.items():
            scores[doc_id] += term_score(
                tf,
                index.doc_lengths[doc_id],
                index.avg_doc_length,
                term_idf,
                k1, b,
            )

    ranked = sorted(scores.items(), key=lambda p: (-p[1], p[0]))
    return ranked[:k]

This is called term-at-a-time scoring, and it has a few nice properties:

• Documents that share no terms with the query are never touched. Doc 3 ("dogs and cats are animals") doesn't appear in the postings for deep or learning, so the loop never visits it. It would have scored 0 anyway. On a real corpus that's the difference between scoring a million documents and scoring a few thousand.
• IDF is computed once per query term, not once per (term, document) pair.
• Repeated query words count once. The set(...) means "deep deep learning" scores exactly the same as "deep learning". That's a choice, not a law. If you loop over the raw token list instead, a repeated word adds its contribution again: doc 2 goes from 1.172 to 1.845 and doc 1 from 0.913 to 1.516, so the user effectively gets to upweight a word by typing it twice. The original Okapi papers go further and give query-term frequency its own saturation parameter, $k_3$. For short keyword queries, counting each word once is the simplest and most common choice.
• The work scales with the postings lists you read, not with the size of the corpus.

Step 5: Run it

index = InvertedIndex(documents)

for doc_id, score in search(index, "deep learning"):
    print(f"{score:.3f}  [{doc_id}] {documents[doc_id]}")

1.172  [2] machine learning and deep learning
0.913  [1] deep learning uses neural networks
0.392  [0] machine learning is useful

That matches what we guessed at the start. Let's check where each number comes from.

The worked example

The query tokenizes to ["deep", "learning"]. From the index:

• deep has postings {1: 1, 2: 1} and IDF 0.693
• learning has postings {0: 1, 1: 1, 2: 2} and IDF 0.357
• avgdl = 3.75

The accumulators fill in like this:

Some things to notice:

• Doc 2 wins because it matches both terms and says "learning" twice. Saturation still applies, though: the second "learning" raises that term's contribution from about 0.35 to 0.499, not to double.
• Doc 1 matches both terms too, but loses to doc 2 partly because it's the longest document (5 terms against an average of 3.75), so length normalization pulls its per-term scores down.
• Doc 0 only matches learning, the low-IDF term, so it scores much lower. Missing the rare term deep costs it far more than a missing common term would.
• Doc 3 is never scored. That's the inverted index at work.

Tuning k1 and b

The defaults (k1 between 1.2 and 2.0, b = 0.75) work well on a wide range of text, but they're worth adjusting for your data:

Here's what the extreme settings do to our "deep learning" query:

for params in [{}, {"k1": 0}, {"b": 0}]:
    print(params, search(index, "deep learning", **params))

• Defaults (k1=1.5, b=0.75) are the baseline.
• k1=0 ignores term frequency, so doc 2's second "learning" no longer counts and it ties with doc 1. Doc 1 is listed first only because the tie-break uses doc ID.
• b=0 turns off the length adjustment: doc 1 (the longest) loses its penalty and doc 0 (the shortest) loses its bonus.

Notice that with k1 = 0 the score reduces to "sum of IDF over matched terms," and b stops mattering at all, because the length adjustment only ever scales k1.

Where BM25 falls short

BM25 only knows whether the exact term is in the document. That's its strength (it's fast, predictable, and needs no training), and it's also its biggest weakness:

>>> search(index, "dog")      # the corpus says "dogs"
[]
>>> search(index, "canine")   # a synonym
[]

Doc 3 is obviously about dogs, but neither query finds it.

• Word forms. "dog" and "dogs" are different terms to our tokenizer. Stemming fixes this one by reducing both to dog, which is why every real engine stems.
• Vocabulary mismatch. No amount of stemming turns "canine" into "dog" or "car" into "automobile". BM25 has no notion that two different words can mean the same thing.
• Word order and meaning. "dog bites man" and "man bites dog" have the same terms, so they get exactly the same score for any query.

This is why modern search systems pair BM25 with dense vector search. An embedding model maps text to vectors where "canine" and "dog" land close together, so it catches the paraphrases BM25 misses. BM25 in turn catches what embeddings are weak at: exact names, product codes, error messages, and rare words the model never saw in training. Hybrid search runs both and merges the two ranked lists, often with Reciprocal Rank Fusion. BM25 isn't being replaced. It's half of the answer.

What real engines add

The ~50 lines above are a faithful BM25. Production systems like Lucene add engineering around the same core:

• Compressed postings lists: delta-encoded doc IDs, variable-byte or bit-packed integers.
• Document-at-a-time scoring with skipping (WAND, Block-Max WAND). These walk all the postings lists in parallel and skip over documents that provably can't reach the current top-k.
• Top-k heaps instead of sorting every accumulator.
• Field weighting (BM25F): a match in the title counts for more than one in the body.
• Better analysis: stemming, synonyms, and language-specific tokenizers.

None of these change the scoring. BM25 is still the same three ideas: rare terms matter more, repetition has diminishing returns, and short documents shouldn't be penalized. The inverted index is what makes it fast enough to use.

To watch all of this happen step by step (tokenizing, building the postings lists, and adding up each term's score), try the interactive demo at bm25.derekzaw.com.

Full code

import math
import re
from collections import Counter, defaultdict

STOPWORDS = {"the", "a", "an", "and", "or", "is", "are", "of", "to", "in"}


def tokenize(text):
    tokens = re.findall(r"[a-z0-9]+", text.lower())
    return [t for t in tokens if t not in STOPWORDS]


class InvertedIndex:
    def __init__(self, documents):
        self.documents = documents
        self.postings = defaultdict(dict)   # term -> {doc_id: tf}
        self.doc_lengths = []

        for doc_id, text in enumerate(documents):
            tokens = tokenize(text)
            self.doc_lengths.append(len(tokens))
            for term, tf in Counter(tokens).items():
                self.postings[term][doc_id] = tf

        self.num_docs = len(documents)
        self.avg_doc_length = sum(self.doc_lengths) / self.num_docs


def idf(index, term):
    n = len(index.postings.get(term, {}))
    N = index.num_docs
    return math.log(1 + (N - n + 0.5) / (n + 0.5))


def term_score(tf, doc_len, avg_len, idf_value, k1=1.5, b=0.75):
    length_norm = 1 - b + b * doc_len / avg_len
    return idf_value * (tf * (k1 + 1)) / (tf + k1 * length_norm)


def search(index, query, k=10, k1=1.5, b=0.75):
    scores = defaultdict(float)
    for term in set(tokenize(query)):
        postings = index.postings.get(term)
        if not postings:
            continue
        term_idf = idf(index, term)
        for doc_id, tf in postings.items():
            scores[doc_id] += term_score(
                tf, index.doc_lengths[doc_id], index.avg_doc_length,
                term_idf, k1, b,
            )
    ranked = sorted(scores.items(), key=lambda p: (-p[1], p[0]))
    return ranked[:k]


if __name__ == "__main__":
    documents = [
        "machine learning is useful",
        "deep learning uses neural networks",
        "machine learning and deep learning",
        "dogs and cats are animals",
    ]
    index = InvertedIndex(documents)
    for doc_id, score in search(index, "deep learning"):
        print(f"{score:.3f}  [{doc_id}] {documents[doc_id]}")