Sparse retrieval and BM25 keyword search explained

Sparse retrieval represents every document and every query as a vector over the vocabulary, where almost every entry is zero. If your vocabulary has 50,000 terms and a chunk of text uses 90 distinct ones, that chunk's vector has 90 non-zero entries and 49,910 zeros. That is what "sparse" names: the representation's sparsity, not the quality of the results. Retrieval then reduces to a set-overlap-and-weighting problem — which documents share terms with the query, and how much should each shared term count?

BM25 ("Best Match 25", the 25th ranking function in a research line that began with probabilistic relevance models in the 1970s and 1980s) is the answer that became the industry default. It is the scoring function underneath Elasticsearch, OpenSearch, Lucene, Solr, and the keyword half of nearly every hybrid search system in production. When a vector database advertises "hybrid search" or "sparse plus dense", the sparse half is almost always BM25 or a close variant.

Three properties make BM25 the one that stuck, and all three are worth memorising as behaviours rather than as formulas:

Compare that to the naïve approach it replaced. Plain term-frequency counting (count the query words, rank by total) rewards long documents and keyword spam. TF-IDF weighting fixes the rare-term problem but keeps term frequency linear and treats length inconsistently across variants. BM25 fixes all three at once with two tunable knobs, and it does so cheaply enough to run over hundreds of millions of documents on commodity CPUs.

The single most useful thing to hold in your head: BM25 matches strings, not meanings. Every strength and every failure it has follows from that one sentence. It will find the chunk containing HTTP 503 when you search HTTP 503, and it will completely miss the chunk that says "the gateway rejected the request because no upstream worker was available" — because that chunk shares no words with your query. Dense retrieval in 07-02 exists to cover exactly that gap, and hybrid search in 07-06 exists because neither one alone is sufficient.

L1 — The intuition you can carry into an exam

Imagine you are ranking pages by hand for the query paged attention memory. You would reason roughly like this:

1. Ignore memory a bit — it's everywhere in this corpus. Weight attention more. Weight paged most, because almost nothing else in the corpus says it.
2. A page that says paged five times is more about paging than one that says it once — but not five times more. Two or three mentions already tell you it's the topic.
3. If a page says paged twice in 150 words, it is more focused on the subject than a page that says it twice in 12,000 words.

Those three steps are BM25. The formula only makes them precise and consistent. If you remember nothing else, remember: rare beats common, repetition saturates, short beats long.

L2 — The mechanism, term by term

BM25 scores a document D against a query Q by summing a per-term contribution over the query's terms. Each term's contribution is a product of two factors:

score(D, Q) = Σ over query terms q :   IDF(q)  ×  weighted_TF(q, D)

The IDF factor measures how surprising the term is. With N documents in the collection and n(q) documents containing term q:

IDF(q) = ln( 1 + (N − n(q) + 0.5) / (n(q) + 0.5) )

The shape is what matters: as n(q) approaches N, IDF approaches zero. A term in every document contributes nothing at all. As n(q) drops toward 1, IDF rises steeply. This is the mathematical reason exact identifiers are BM25's home turf — a part number appearing in 3 of 400,000 chunks gets an enormous weight.

The weighted term-frequency factor implements saturation and length normalisation together:

weighted_TF(q, D) =        f(q, D) × (k1 + 1)
                    ─────────────────────────────────────
                    f(q, D) + k1 × ( 1 − b + b × |D|/avgdl )

where f(q, D) is the raw count of q in D, |D| is the document's length in terms, avgdl is the average document length in the collection, and k1 and b are the two tuning parameters.

Read the parameters as behaviours:

The defaults are the defaults for a reason and you should not tune them before you have an evaluation set. But knowing what they do lets you diagnose a symptom. If your retriever keeps returning enormous concatenated pages, b is too low for your chunk-length distribution — or, far more likely, your chunking in 06-02 produced wildly uneven chunk lengths and BM25 is faithfully reporting that.

L3 — Why it is fast: the inverted index

BM25's practical dominance is as much about data structures as about scoring. A sparse retriever does not compare your query to every document. It uses an inverted index: a dictionary mapping each term to a posting list of the documents containing it, with the per-document frequency stored alongside.

"paged"      → [ (chunk_0412, 3), (chunk_0413, 1), (chunk_9981, 2) ]
"attention"  → [ (chunk_0007, 5), (chunk_0412, 4), (chunk_1188, 2), ... ]
"memory"     → [ (chunk_0002, 1), (chunk_0007, 2), ... 180,000 more ... ]

To score the query, the engine walks only the posting lists of the query's terms and accumulates scores in a small hash map of candidate documents. Documents containing none of the query terms are never touched — they cost nothing. That is why keyword search over tens of millions of documents returns in milliseconds on a CPU with no accelerator, and why a rare-term query is faster than a common-term one.

Two consequences fall out of this that people find surprising:

• Adding documents that don't contain your terms does not slow your query. Sparse retrieval degrades with corpus vocabulary overlap, not corpus size.
• A query with only stopwords is the slow case, because every posting list is enormous and every document is a candidate. This is why classical pipelines strip stopwords — see 02-05 — and why a modern BM25 implementation often keeps them but relies on IDF to make them free.

The text-processing stage that feeds the index is not a detail. Case folding, stemming or lemmatization, and tokenisation choices all change which strings count as "the same term". 02-05 covers the stemming-versus-lemmatization distinction directly, and it matters here concretely: if the index stems retrieving to retriev but the query analyser does not, the term will not match and the document will not be found. The index analyser and the query analyser must be the same analyser. That is the sparse-retrieval analogue of the mismatched-encoder failure you will meet in 07-02, and it fails just as silently.

This table is the highest-value exam asset in the lesson. The confusables here — sparse versus dense, BM25 versus TF-IDF, retrieval versus filtering — are precisely the axes distractors are built on.

Three readings of that table are worth stating explicitly because they are the ones exam items probe.

BM25 is not a different family from TF-IDF; it is a better member of the same family. Both are sparse, lexical, inverted-index methods. If a question contrasts "sparse" with "dense", BM25 and TF-IDF are on the same side. If a question asks which sparse scoring function is the modern standard, the answer is BM25.

Sparse retrieval's explainability is a real operational advantage, not a consolation prize. When BM25 returns a wrong chunk you can see which term caused it. When dense retrieval returns a wrong chunk, you get a cosine similarity of 0.71 and no explanation. For a system that must be debugged by humans — and 07-10 is entirely about debugging RAG — that difference is worth money.

The "cost to change the model" row is the asymmetry people forget. Re-tokenising a BM25 index is cheap and local. Changing an embedding model invalidates every vector you have ever stored. That asymmetry is one of the honest arguments for keeping a sparse index in your architecture permanently.

Everything in this section is a constructed illustrative example, not a measurement from a real system. The numbers are invented so the arithmetic is checkable by hand; they are not benchmark results and should not be quoted as such.

Our miniature corpus has N = 4 chunks from a fictional internal knowledge base. Term counts after case-folding and tokenising:

Average document length: avgdl = (100 + 100 + 1000 + 100) / 4 = 325.

Query: paged attention memory. Parameters: k1 = 1.2, b = 0.75.

Step 1 — document frequencies. paged appears in c1 and c3, so n = 2. attention appears in c1, c2, c3, so n = 3. memory appears in all four, so n = 4.

Step 2 — IDF per term, using IDF = ln(1 + (N − n + 0.5)/(n + 0.5)):

IDF(paged)     = ln(1 + (4 − 2 + 0.5)/(2 + 0.5)) = ln(1 + 2.5/2.5) = ln(2.000) = 0.693
IDF(attention) = ln(1 + (4 − 3 + 0.5)/(3 + 0.5)) = ln(1 + 1.5/3.5) = ln(1.429) = 0.357
IDF(memory)    = ln(1 + (4 − 4 + 0.5)/(4 + 0.5)) = ln(1 + 0.5/4.5) = ln(1.111) = 0.105

Note immediately what has happened. memory — the term a naïve reader would think is central, and the term with by far the highest raw counts — has been weighted down to 0.105, roughly one-seventh of paged's weight. BM25 has decided that memory carries almost no information in this corpus, because everything in this corpus is about memory. That is the single most important behaviour to internalise.

Step 3 — the length-normalisation denominator term k1 × (1 − b + b × |D|/avgdl):

for the 100-term chunks:   1.2 × (0.25 + 0.75 × 100/325)  = 1.2 × (0.25 + 0.2308) = 1.2 × 0.4808 = 0.577
for the 1,000-term chunk:  1.2 × (0.25 + 0.75 × 1000/325) = 1.2 × (0.25 + 2.3077) = 1.2 × 2.5577 = 3.069

The long chunk carries a denominator penalty more than five times heavier. This is b doing its job.

Step 4 — score c1. Weighted TF is f × (k1+1) / (f + 0.577):

paged:      4 × 2.2 / (4 + 0.577) = 8.8 / 4.577 = 1.922   → × 0.693 = 1.332
attention:  4 × 2.2 / (4 + 0.577) = 1.922                 → × 0.357 = 0.686
memory:     2 × 2.2 / (2 + 0.577) = 4.4 / 2.577 = 1.707   → × 0.105 = 0.179
                                                    score(c1) = 2.197

Step 5 — score c3, the long handbook, with the 3.069 denominator term:

paged:      2 × 2.2 / (2 + 3.069) = 4.4 / 5.069 = 0.868    → × 0.693 = 0.602
attention:  3 × 2.2 / (3 + 3.069) = 6.6 / 6.069 = 1.087    → × 0.357 = 0.388
memory:    25 × 2.2 / (25 + 3.069) = 55 / 28.069 = 1.959   → × 0.105 = 0.206
                                                    score(c3) = 1.196

Step 6 — score c2 and c4:

c2:  attention: 1 × 2.2 / (1 + 0.577) = 1.395 → × 0.357 = 0.498
     memory:    6 × 2.2 / (6 + 0.577) = 2.007 → × 0.105 = 0.211
                                        score(c2) = 0.709

c4:  memory:    1 × 2.2 / (1 + 0.577) = 1.395 → × 0.105 = 0.146
                                        score(c4) = 0.146

Final ranking: c1 (2.197) > c3 (1.196) > c2 (0.709) > c4 (0.146).

Four lessons are visible in those numbers, and each one is exam-relevant:

1. c1 wins on the rare term, not the frequent one. Its paged contribution (1.332) alone exceeds c3's entire score. Rare-term matching is where the signal lives.
2. c3 had 25 mentions of memory and it bought almost nothing — 0.206 of a 1.196 score. Saturation plus low IDF neutralised the volume completely. A naïve term-count ranker would have put c3 first by a mile.
3. c3 was penalised for being long even where it did match. Its two paged mentions scored 0.602 where c1's four scored 1.332 — not a 2× ratio but a 2.2× ratio, because length normalisation compounded with saturation.
4. c4 scored non-zero. BM25 always returns something. A top-k retriever with k = 4 hands c4 to your LLM regardless of whether it is relevant. Every retriever has this property, and it is the direct motivation for the score-threshold and reranking discussion in 07-07, and for letting a model decline to answer in 07-11.

BM25's failure modes are as systematic as its strengths, because both descend from the same fact: it matches strings.

The operational rule that follows: run BM25 first, always, as a measured baseline — then decide. Concretely, using the by-hand retrieval evaluation from 03-04 and the eval-set discipline from 01-08:

1. Build the eval set: 20–40 real questions with the chunk id that should be retrieved for each.
2. Index the corpus with BM25. Measure recall@5 and recall@10 — the fraction of questions where the right chunk appears in the top 5 or 10.
3. Only now add dense retrieval, and measure the same numbers on the same set.
4. If dense retrieval does not clearly beat BM25 on your corpus, you have learned something valuable and free: the embedding model, the chunking, or the eval set is the problem, and buying a vector database will not fix it.

Skipping step 2 is the most common methodological error in applied RAG. It is not a small one, because a team without a baseline cannot tell an improvement from a regression, and will spend months tuning a component that was never the bottleneck.

The NCA-GENL blueprint names retrieval-augmented generation three separate times across its objectives [OFFICIAL], and this lesson serves several of them directly:

• 1.3 — Build LLM use cases such as retrieval-augmented generation (RAG), chatbots, and summarizers. You cannot build the retrieval half without knowing what the retrieval options are.
• 1.4 — Curate and embed content datasets for RAGs. The dense side is covered in 07-02, but the curation decisions — analysers, chunk lengths, what counts as a term — determine sparse quality too.
• 1.6 — Familiarity with the capabilities of Python natural language packages (spaCy, NumPy, vector databases, etc.). "Vector databases" is named in the official objective text, and the sparse/dense distinction is what makes the phrase meaningful rather than decorative.

Sitting behind those, the official course index places dense-versus-sparse retrieval explicitly in its vector-databases-and-similarity-search coverage, alongside ANN indexing, the recall/latency trade-off, metadata filtering, hybrid search, and when a vector DB is unnecessary. That last item is a direct descendant of this lesson: the honest answer to "when is a vector database unnecessary?" often begins "when BM25 already gets you the recall you need."

The exam is calibrated to general-level knowledge rather than deep technical derivation [FIELD] — candidate reports converge on the finding that detailed math was overkill and did not appear. Read that as guidance about what to memorise, not permission to skip the mechanism. You should be able to state BM25's three behaviours cold and pick it out of a list; you will almost certainly not be asked to reproduce the formula. The worked example above exists so the behaviours are understood rather than recited, which is what makes them survive a distractor.

Question phrasings you should recognise:

Distractor families to expect:

• The "sparse means low-quality" trap. Options phrased so that "sparse" sounds like a deficiency. Sparse describes the vector, not the result quality.
• BM25 attributed to the wrong layer. Options claiming BM25 is an approximate-nearest-neighbour index, or an embedding model, or a reranker. It is a scoring function over an inverted index. HNSW and IVF (07-04) are ANN indexes; a cross-encoder (07-07) is a reranker; these are three different layers.
• TF-IDF and BM25 presented as opposites. They are the same family; BM25 is the refinement.
• "Semantic search" offered as a synonym for keyword search. Semantic search is the dense side.
• Claiming BM25 handles synonyms. It does not, at all, ever, without an explicit synonym-expansion layer bolted on top.
• Claiming BM25 needs GPU acceleration. It does not. If a question lists resource requirements, sparse retrieval's CPU-only profile is a distinguishing feature.

Note also the widely reported answering heuristic: in scenario questions, when one option proposes building a RAG solution, it is usually the keyed answer [FIELD]. That is candidate-report calibration, not official NVIDIA guidance, and it is a tie-breaker rather than a rule. Its counter-cases — no corpus to retrieve from, a need to change style or format rather than facts, and a hard latency floor — are the subject of 07-12, and you should not reach for the heuristic before checking them.

Mistake 1 is the one this lesson exists to prevent. The others are consequences of forgetting that the analyser, the chunker, and the corpus cleaner are all upstream of the score — a BM25 problem is very often a 06-01 parsing problem, a 06-02 chunking problem, or a 06-04 deduplication problem wearing a retrieval costume.

No, and the evidence is that the systems most invested in dense retrieval keep sparse retrieval anyway. Production search stacks and modern vector databases ship hybrid modes precisely because the two methods fail on disjoint query shapes. NVIDIA's own retrieval tooling is built around retrieval accuracy at scale rather than around any single scoring method [NVIDIA-DOC], and the reference RAG workflows in the NVIDIA AI Blueprint for RAG treat retrieval as a stage to be measured and improved, not as a solved component.

There are three durable reasons BM25 survives:

It is the only method that handles unseen tokens correctly. An embedding model has a fixed vocabulary and fixed training data. A part number coined last Tuesday is, to the encoder, a bag of meaningless subword fragments — see 02-03 on why tokens are not words. To BM25, it is a maximally rare and therefore maximally informative term. New identifiers arrive constantly in every real corpus.

It costs nothing to keep. No GPU, no encoder call at query time, no ANN index to rebuild, no re-embedding when a model version changes. In a hybrid system the sparse leg is the cheap leg.

It is auditable. In regulated settings, "we returned this passage because it contains the statute you cited" is an explanation. "Cosine similarity 0.83" is not.

Because IDF and tokenisation both work in its favour on exact identifiers, and both work against the encoder.

Take a query for ERR_TLS_CERT_ALTNAME_INVALID. In a 400,000-chunk corpus that string might appear in four chunks. BM25 assigns it near-maximal IDF and those four chunks rocket to the top; nothing else can compete, because nothing else contains the term.

The embedding model sees something different. Its tokeniser shatters the identifier into subword pieces — plausibly something like ERR, _, TLS, _, CERT, _, ALT, NAME, _, INVALID — and the resulting vector is a blend of "error", "TLS", "certificate", "name", "invalid". That vector sits close to every chunk about TLS certificate errors. It is a semantically excellent representation and a retrieval disaster, because the specific code has been averaged away into its category. The model returns twelve chunks about certificate problems and the one you needed is ranked seventh, or not in the top-k at all.

The same mechanism explains failures on version numbers (v2.14.1 versus v2.1.41), on drug and chemical names, on legal citations, and on internal ticket ids. Anything whose meaning is its exact string is BM25 territory. This is not a defect in the embedding model; it is the correct behaviour of a system designed to map similar meanings to nearby vectors, applied to a case where near-identical strings must be kept apart.

With a frozen labelled evaluation set and one number, measured before and after. The procedure:

1. Freeze 20–40 real questions. Real ones — from your users, your support tickets, your own colleagues. Invented questions are written in the corpus's vocabulary and quietly favour whichever method you already prefer.
2. Label the answer chunk. For each question, record the chunk id (or ids) that genuinely answer it. This is the labour, and there is no substitute. 03-04 walks the by-hand version of this.
3. Measure retrieval, not answers. Compute recall@5 and recall@10 for BM25 alone. Separating retrieval quality from generation quality is the whole discipline of 07-10 and 09-07; conflating them makes every result uninterpretable.
4. Swap in dense retrieval and re-measure the same numbers on the same questions.
5. Then measure hybrid (07-06) and hybrid plus reranking (07-07), in that order, one change at a time.

You will end with a four-row table: BM25, dense, hybrid, hybrid+rerank. That table is the most useful artefact in the entire project, and it is worth more than any architecture diagram. It also protects you from the failure mode where a team adds four components at once, the system improves, and nobody can say which component did it — or which one is quietly making things worse and being masked by the others.

Neither. BM25 runs on an inverted index — a CPU-friendly data structure that predates GPU computing by decades. A production BM25 index over millions of documents is served by Elasticsearch, OpenSearch, or Lucene on ordinary compute. For a corpus of a few thousand chunks you do not even need that: an in-memory implementation such as a rank_bm25-style library over a Python list is genuinely sufficient, and its output is identical in kind to what a cluster would give you.

That is worth stating plainly because it is the mirror image of a very common over-engineering pattern. Teams stand up a vector database for a corpus of 10,000 chunks, which is a scale at which brute-force exact search over an in-memory NumPy array — see M0.1 on shapes and dot products — is also fine and simpler. 07-04 makes that argument properly. Here it is enough to note that the sparse side of your architecture is the part least likely to need infrastructure, and the part most likely to be skipped anyway.

• Sparse retrieval matches strings; dense retrieval matches meanings. Every strength and weakness of each follows from that sentence.
• BM25's three behaviours are rare-term weighting (IDF), term-frequency saturation (k1), and document-length normalisation (b). Memorise the behaviours; the formula is unlikely to be examined [FIELD].
• The worked example's headline result: memory appeared 25 times in the long chunk and contributed 0.206 out of a 1.196 score. Volume of a common term is nearly worthless. Rarity is the signal.
• BM25 wins on exact identifiers — error codes, part numbers, citations, SKUs, version strings — because subword tokenisation averages those identifiers into their category, while IDF makes them maximally distinctive.
• BM25 fails on synonyms, paraphrase, and cross-lingual queries, because zero lexical overlap means zero score. These failures are the reason 07-02, 07-06, and 07-07 exist.
• It needs no GPU, no training, no re-embedding, and no vector database, which makes it the cheapest permanent component in a retrieval architecture.
• Every retriever always returns its top k, however irrelevant. A weak match is still handed to the model unless you threshold, rerank, or let the model decline.
• Run it first as a baseline. A team that has not measured BM25 recall on its own corpus cannot demonstrate that anything it added afterwards helped.

You now have a retriever that finds the chunk containing your words and cannot find the chunk that means your words. That gap is not a tuning problem and no BM25 parameter closes it — the method has no representation of meaning to work with. Next: 07-02 builds the other half, dense retrieval with embeddings, where a query and a passage are compared as vectors in a learned semantic space. It also introduces the failure that makes dense retrieval more dangerous than sparse retrieval to get wrong: a mismatched query encoder and passage encoder produce plausible nonsense with high similarity scores and no error message anywhere in the stack.