Before an embedding model ever mapped a sentence to a point in space, search worked by counting words. Sparse retrieval is that older, sturdier idea made precise: represent every document as a huge, mostly-zero vector over the vocabulary, and score a query by how well its terms line up with a document’s terms. The reigning formula, BM25, is a TF-IDF variant tuned with two knobs — saturation and length normalization — and it remains a brutally strong baseline that dense neural retrievers still struggle to beat outright. This piece builds sparse retrieval from the ground up: the bag-of-words vector and the inverted index, the full BM25 formula worked through a numeric example, why exact-term matching is simultaneously a superpower and a blind spot, and how learned sparse models like SPLADE bridge to the dense world without leaving the vocabulary behind.
Sparse, dense, and what , '’': sparse’ means
Retrieval turns a query into a ranked list of documents. Two families do this. Dense retrieval encodes text into a few hundred continuous dimensions where every coordinate is nonzero and meaning lives in geometric proximity. Sparse retrieval encodes text into a vector with one dimension per vocabulary term — tens or hundreds of thousands of dimensions — almost all of them exactly zero, because a document contains only a few hundred distinct words.
That zero-heaviness is the defining property, and it is a gift. A document vector over a 100,000-word vocabulary might have 200 nonzero entries. You never store or touch the zeros, and scoring a query against millions of documents reduces to visiting only the documents that share at least one query term. Sparsity is not an accident of the representation; it is the very thing that makes exact-term search over web-scale corpora possible — and everything that follows is machinery built to exploit it.
The bag-of-words vector and the inverted index
Sparse retrieval starts by throwing away word order. A document becomes a bag of words: a mapping from each term it contains to a count. ‘The cat sat on the cat mat’ becomes {the:2, cat:2, sat:1, on:1, mat:1}. Conceptually this is a vector d of length |V| (the vocabulary size) that is nonzero only at those term positions.
Storing millions of such vectors as dense arrays would be absurd — almost all entries are zero. Instead we transpose the problem into an inverted index: for each term t, keep a postings list of the documents containing it, with the per-document frequency f(t,d). To answer ‘quasar redshift’ you fetch only two short postings lists and merge them, rather than scanning the corpus. This is the same structure that powers Lucene, Elasticsearch, and OpenSearch. The index also stores per-term document counts and per-document lengths — exactly the statistics BM25 needs. Sparsity turns global search into a handful of list lookups.
TF-IDF: the two forces behind a term’s weight
Not all matches are worth the same. TF-IDF weights a term by the product of two intuitions. Term frequency (tf): a term that appears often in a document is more central to it — five mentions of ‘redshift’ signal a document is about redshift. Inverse document frequency (idf): a term that appears in nearly every document carries little information, while a term appearing in a handful of documents is highly discriminating.
Classic IDF is idf(t) = log(N / n(t)), where N is the collection size and n(t) the number of documents containing t. A word in all N documents scores log(1) = 0; a rare word scores high. The TF-IDF weight is tf × idf. This already captures the core of lexical ranking: reward documents that mention query terms often and reward rare query terms more. But raw tf is too eager, and it ignores that long documents accumulate mentions for free. BM25 fixes both.
BM25: saturating term frequency with k1
BM25’s first refinement is saturation. A document that says ‘jaguar’ ten times is more relevant than one that says it once — but not ten times more relevant. Relevance should rise with frequency and then flatten. BM25 replaces raw tf with a saturating transform:
tf_weight = f(t,d) · (k1 + 1)
÷ ( f(t,d) + k1 ) (before length normalization)As f(t,d) → ∞, this ratio approaches k1 + 1 — a hard ceiling. The parameter k1 (typically 1.2 to 2.0) controls how quickly the curve saturates. Small k1 means the count barely matters past the first occurrence (nearly binary presence/absence); large k1 keeps the response closer to linear for longer. With k1 = 1.5, going from one mention to five raises the weight only about two-fold, not five-fold. This diminishing return is the single most important thing BM25 adds over naive TF-IDF, and it is what stops keyword-stuffed documents from dominating.
BM25: length normalization with b, and the full formula
The second refinement is length normalization. A long document accumulates term occurrences simply by being long, which unfairly inflates its tf. BM25 divides by a length factor that compares the document length |d| to the collection average avgdl, modulated by b (usually 0.75):
score(d, Q) = Σ_{t ∈ Q} IDF(t) · ----------------- f(t,d) · (k1 + 1) -----------------
f(t,d) + k1 · ( 1 − b + b · |d| / avgdl )
IDF(t) = ln( ( N − n(t) + 0.5 ) / ( n(t) + 0.5 ) + 1 )When b = 0, length is ignored entirely; when b = 1, the document is fully normalized to average length. At b = 0.75 a document longer than average is penalized, a shorter one rewarded. Note the BM25 IDF uses a smoothed, ‘probabilistic’ form with + 0.5 terms and a + 1 inside the log to keep it non-negative. The whole score is a sum over query terms, each contributing independently — exactly what lets the inverted index evaluate it one postings list at a time.
A worked BM25 scoring example
Take a collection of N = 10 documents with avgdl = 100 tokens, and parameters k1 = 1.5, b = 0.75. Query: ‘quasar redshift’. Candidate document d has length |d| = 120. In d: ‘quasar’ appears 5 times and occurs in only n = 2 documents; ‘redshift’ appears 2 times and occurs in n = 8 documents.
length factor K = k1 · (1 − b + b · |d|/avgdl)
= 1.5 · (0.25 + 0.75 · 1.2) = 1.725
IDF(quasar) = ln( (10−2+0.5)/(2+0.5) + 1 ) = ln(4.40) = 1.482
IDF(redshift) = ln( (10−8+0.5)/(8+0.5) + 1 ) = ln(1.29) = 0.258
quasar : 1.482 · [5·2.5 / (5 + 1.725)] = 1.482 · 1.859 = 2.754
redshift : 0.258 · [2·2.5 / (2 + 1.725)] = 0.258 · 1.342 = 0.346
BM25(d, Q) = 2.754 + 0.346 = 3.10The lesson is stark: the rare term ‘quasar’ supplies 2.75 of the 3.10 total, dwarfing common ‘redshift’. And saturation shows in the tf weights: one occurrence of quasar scores 0.917, five score only 1.859 — five times the count, roughly twice the weight.
Why exact matching is a strength
Because BM25 matches surface terms, it is exact where it counts. If a user searches for an error code ORA-00933, a product SKU A1278, a function name malloc, a person Znaimer, or a legal citation, they mean that exact string, and any document containing it is a hit — ranked highly precisely because such tokens are rare and thus carry huge IDF.
This is where dense retrievers are weak. An embedding model may never have seen ORA-00933 in training and will map it to some vague region of space, blurring it against similar-looking codes. Sparse retrieval has no such problem: a token either matches or it does not, and rare tokens are exactly the high-signal ones. Names, identifiers, acronyms, version numbers, out-of-domain jargon — the long tail no neural model has memorized — is BM25’s home turf. For search over logs, code, catalogs, and legal or medical corpora full of precise terminology, lexical matching is often the more correct answer, not a legacy fallback.
Why exact matching is a weakness: vocabulary mismatch
The same literalness is BM25’s Achilles’ heel. It scores only terms that literally co-occur, so it is blind to synonymy and paraphrase. A query for ‘heart attack’ will not match a document that only says ‘myocardial infarction’; ‘car’ misses ‘automobile’; ‘how do I fix a slow laptop’ misses a page titled ‘improving sluggish notebook performance’. This is the classic vocabulary-mismatch problem.
Stemming, lemmatization, and stopword removal patch the edges — folding ‘running’ to ‘run’, dropping ‘the’ — and hand-built synonym lists help narrow domains. But none of these give BM25 a real notion of meaning; they only expand the set of literal matches. The gap is fundamental: two texts can be about the identical concept with zero shared content words, and a bag-of-words model has nothing to bridge them. This is exactly the weakness dense retrieval was invented to solve.
Learned sparse retrieval: SPLADE-style expansion
Learned sparse retrieval keeps the inverted index but lets a transformer decide the weights — and, crucially, expand the vocabulary. SPLADE runs a document (or query) through a BERT-style masked-language-model head, producing for every input token a distribution over the entire vocabulary. Aggregating and sparsifying these gives a sparse vector whose nonzero entries include not only the terms actually present but also related terms the model predicts.
A document about a ‘heart attack’ can thus acquire nonzero weight on ‘myocardial’, ‘cardiac’, and ‘infarction’ even if those words never appear. An L1/FLOPS regularizer during training forces most weights to zero, keeping the vectors sparse enough to serve from a standard inverted index. The result is a hybrid in spirit: it bridges vocabulary mismatch like a dense model yet indexes and scores like BM25, so exact-match precision on rare tokens survives — the natural meeting point of the two worlds.
Sparse and dense: siblings, not rivals
It is tempting to frame dense embeddings as the modern replacement for ‘old’ BM25, but the honest picture is two complementary tools with opposite failure modes. BM25 nails exact terms, rare identifiers, and precise jargon but misses paraphrase. Dense retrieval captures meaning but smears rare tokens and can confidently retrieve something merely ‘on topic’ rather than actually answering.
Because their errors are largely uncorrelated, combining them wins. The standard move is hybrid search: run both retrievers and fuse the ranked lists — commonly with Reciprocal Rank Fusion, which sums 1 / (k + rank) across systems and needs no score calibration. A document that both a lexical and a semantic system rank highly is a strong candidate; one that only BM25 finds is likely an exact-term hit worth surfacing. Production retrieval-augmented systems rarely choose — they run sparse and dense side by side, letting each cover the other’s blind spot. Sparse retrieval is not a relic; it is one half of a well-designed pipeline.
k1 knob, so the tenth mention barely beats the second) and length normalization (the b knob, so long documents don’t win by sprawl). The inverted index makes it fast, and rare terms dominate the score, which is why exact matching shines on names, codes, and jargon and fails on synonyms and paraphrase — the vocabulary-mismatch gap. SPLADE-style learned sparse models close part of that gap by expanding documents into related terms while still serving from an inverted index. Treat sparse and dense as siblings, not rivals: their errors are uncorrelated, so hybrid search with rank fusion beats either alone. BM25 is not a legacy baseline you graduate from — it is half of a serious retrieval stack.