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.