The inverted index & BM25 — lexical retrieval that still wins
Before you reach for embeddings, understand the data structure and scoring function that have carried production search for forty years: a term→document map and a length-normalised, saturation-aware bag-of-words score. Cheap, exact, interpretable, and still the backbone of every serious search engine.
- The data structure. Term dictionary → posting lists (docid, tf, positions). Why "inverted," how it's built at scale (SPIMI / external merge), and how postings are compressed (gap encoding + variable-byte) with a concrete byte count.
- Boolean + phrase/proximity retrieval, and why positions earn their storage cost.
- Scoring, built up: tf intuition → TF-IDF → the full BM25 formula, deriving the engineering intent of k₁ (tf saturation) and b (length normalisation), then BM25F for fields.
- Efficiency: term-at-a-time vs document-at-a-time, and WAND / block-max WAND top-k pruning, with a worked threshold-skip example.
- Where lexical fails — vocabulary mismatch and semantics — which is exactly the hand-off to dense & hybrid retrieval next door.
This lesson depends on lesson 41 (query understanding): the query that arrives here has already been tokenised, lowercased, stemmed, and stop-word-filtered into a list of analysed terms. The index was built by running documents through the same analyzer. That symmetry — query and document analysed identically — is the quiet precondition for everything below; break it and exact matches silently disappear. We set up lesson 43 (dense & hybrid retrieval), where embeddings cover the cases BM25 cannot, and lesson 49 (serving), which shards and replicates the index you build here.
Why "inverted," and what's in a posting list
A document is naturally a forward map: doc → terms it contains. To find the documents containing a term, you'd scan every document — O(N) per query term, hopeless at scale. The inverted index flips it: term → list of documents containing it. "Inverted" is relative to that forward map. The query "find docs with term t" becomes a single dictionary lookup followed by a walk down a precomputed list.
Two structures:
- Term dictionary — every distinct term, mapping to (document frequency df, a pointer to its posting list). Held in memory or a compact on-disk structure (an FST / sorted block index). Lookups must be O(1)-ish.
- Posting list — for one term, the documents that contain it, in ascending docid order. Each posting is at minimum a docid; for scoring we also store the term frequency tf (occurrences in that doc); for phrase/proximity queries we also store the positions (token offsets within the doc).
The phrase "neural network" is not just "both terms present." In doc 7, "neural" sits at positions {4, 19} and "network" at {5}; since 5 = 4 + 1, the bigram is adjacent — a true phrase match. Without positions you could only answer the Boolean question (both terms somewhere in the doc), which is why positions exist despite roughly doubling the index size.
Building the index at scale: SPIMI
You cannot sort a web-scale <term, docid, tf> stream in RAM. The production algorithm is SPIMI (Single-Pass In-Memory Indexing) feeding an external merge sort:
- Stream documents. Maintain an in-memory dictionary mapping term → growing posting list (a real list, not a sorted array — append is O(1)).
- When memory fills, sort the dictionary's terms, write the whole block to disk as a sorted run, free RAM, continue. Each run is a self-contained mini-index.
- After the pass, k-way merge the sorted runs: terms appearing in multiple runs have their posting lists concatenated (already in docid order within each run because we processed documents in id order). The merge is sequential disk I/O — the regime disks are good at.
The key property: SPIMI never holds the global vocabulary in RAM and never random-writes — it's append + sequential-merge, so it scales to indices far larger than memory. Index builds are embarrassingly parallel by document shard; merge happens per shard. (Lesson 49 returns to sharding for serving; here it's a build concern.)
Posting-list compression: gaps + variable-byte
Posting lists dominate index size, and they're full of redundancy: docids are ascending, so store gaps (deltas) instead of absolute ids. A list [7, 88, 140, 512, 901] becomes gaps [7, 81, 52, 372, 389]. Gaps are smaller than ids, and for frequent terms (dense lists) the gaps are tiny. Then encode each gap with variable-byte (varbyte): 7 bits of payload per byte, the top bit a continuation flag, so a number < 128 costs 1 byte, < 16384 costs 2 bytes, etc.
Naïve fixed 32-bit: 5 × 4 B = 20 bytes.
Gap-encode: first id stored as-is, rest as deltas → [7, 81, 52, 372, 389].
Varbyte each gap (1 byte if < 128, else 2 bytes):
| gap | < 128? | bytes |
|---|---|---|
| 7 | yes | 1 |
| 81 | yes | 1 |
| 52 | yes | 1 |
| 372 | no (needs 2 bytes: 372 = 2·128 + 116) | 2 |
| 389 | no | 2 |
Skip pointers
Intersecting two posting lists (an AND query) walks both in docid order. If list A is short and list B is huge, you waste time stepping through B's postings that A will never match. Skip pointers — a sparse forward index laid over a list, typically one skip every √(list length) postings — let you leap past blocks whose entire docid range is below the docid you're seeking. For a list of length L, √L skips give the classic O(√L) seek. Modern engines generalise this to block-max indexes (store, per block, the max docid and the max score contribution), which power the WAND pruning below.
Boolean, phrase, and proximity retrieval
The matching layer answers "which docs are eligible," before scoring ranks them:
- AND ("neural" AND "network"): intersect posting lists. Walk both, advance the cursor on the smaller docid, emit on equality. Skip pointers accelerate. Cost is dominated by the shorter list.
- OR: union — emit any docid in either list. The candidate set is large; this is where top-k pruning (WAND) pays off most.
- NOT: exclude a list's docids from the candidate set.
- Phrase ("machine learning"): AND the lists, then for surviving docs check positions — does "learning" occur at position(of "machine") + 1? Uses the positions array.
- Proximity ("machine" NEAR/5 "learning"): like phrase but allow a window — any pair of positions within distance 5. More forgiving than a strict phrase; useful for query understanding's looser intents.
Phrase and proximity are why positions are stored. They roughly double posting-list size (a tf-only posting is ~1 byte compressed; adding positions adds one varbyte gap per occurrence) — the classic precision-vs-storage trade. Many engines store positions in a separate file read only when a query needs them, so Boolean/scored-only queries never pay the cost.
Scoring: tf intuition → TF-IDF → BM25
Matching gives a candidate set; scoring orders it. Build the intuition in three steps.
1. Term frequency (tf). A doc that says "jaguar" five times is probably more about jaguars than one that says it once. So score rises with tf. But not linearly forever — the 20th occurrence tells you almost nothing the 5th didn't. We want saturation.
2. Inverse document frequency (idf). A term in almost every document ("the") discriminates nothing; a rare term ("photosynthesis") is highly informative. Weight each term by how rare it is across the corpus. The BM25 idf form:
where N is the number of docs and df is how many contain t. The +0.5 smoothing and the 1 + keep it non-negative even for terms in most documents — unlike the classic ln(N/df) which can go negative.
3. TF-IDF multiplies them: tf · idf, summed over query terms. It captures both intuitions but has two flaws BM25 fixes: tf grows unboundedly (no saturation), and a long document accumulates more term occurrences just by being long (no length normalisation). BM25 (Robertson & Spärck Jones, "Okapi BM25") repairs both:
Read it as IDF(t) (how informative the term is) times a saturating, length-normalised tf term. Two knobs:
| Knob | What it controls | Engineering intent |
|---|---|---|
| k₁ (typ. 1.2–2.0) |
tf saturation. As tf → ∞, the tf term → (k₁+1), a hard ceiling. k₁ sets how fast you approach it. Small k₁ ⇒ saturates almost immediately (presence matters, count barely does). Large k₁ ⇒ closer to linear tf. | Diminishing returns on repeated terms. The 2nd occurrence of "jaguar" should add more than the 12th. Without it, keyword-stuffing a word 100 times would dominate ranking — exactly the spam BM25 resists by design. |
| b (typ. 0.75) |
length normalisation. The denominator scales tf by (1 − b + b · |d|/avgdl). At b = 0: no normalisation, raw tf. At b = 1: full normalisation by relative length. b = 0.75 is a calibrated middle. | A long document shouldn't win just by being long. If |d| > avgdl the effective tf is discounted; if shorter, boosted. Without it, a 10,000-word page mentioning your term 8 times outranks a tight 200-word page mentioning it 8 times — usually the wrong call. |
Step 1 — IDF.
IDF = ln(1 + (N − df + 0.5)/(df + 0.5)) = ln(1 + (1,000,000 − 1,000 + 0.5)/(1,000.5))
= ln(1 + 999,000.5 / 1,000.5) = ln(1 + 998.50) = ln(999.50) ≈ 6.907.
Step 2 — length-normalisation factor (the bracket in the denominator):
1 − b + b·|d|/avgdl = 1 − 0.75 + 0.75 × (300/250) = 0.25 + 0.75 × 1.2 = 0.25 + 0.90 = 1.15.
So k₁ · 1.15 = 1.2 × 1.15 = 1.38. (Because |d| > avgdl, this is > k₁ = 1.2 — the doc is penalised for being longer than average.)
Step 3 — tf component at tf = 5:
(tf · (k₁+1)) / (tf + k₁·1.15) = (5 × 2.2) / (5 + 1.38) = 11.0 / 6.38 = 1.724.
score = IDF × 1.724 = 6.907 × 1.724 ≈ 11.91.
Step 4 — double tf to 10 (saturation check):
(10 × 2.2) / (10 + 1.38) = 22.0 / 11.38 = 1.933.
score = 6.907 × 1.933 ≈ 13.35.
The point: doubling tf from 5→10 raised the tf component only 1.724 → 1.933 (+12%), and the score 11.91 → 13.35 (+12%) — not +100%. The ceiling is k₁+1 = 2.2; at tf = 5 we're already at 1.724/2.2 = 78% of it. This is k₁ doing its job: the marginal value of one more occurrence collapses. Set k₁ higher (say 2.0) and the curve straightens; set it near 0 and the 1st occurrence is nearly everything. (The widget below lets you watch this curve bend.)
BM25F — fields don't deserve equal weight
Real documents have fields: a title, a body, anchor text, headers. A query term in the title is far stronger evidence than the same term buried in the body. The naïve fix — score each field with BM25 and add — is wrong, because tf saturation is non-linear: saturating each field separately then summing double-counts and breaks the single-saturation property. BM25F does it correctly: combine the per-field term frequencies first into a single weighted, per-field-length-normalised pseudo-tf, then apply BM25's saturation once:
with per-field boost wf (e.g. title 3.0, body 1.0) and per-field length norm bf. Then plug tf̃ into the BM25 numerator/denominator with a global k₁. The senior point: saturate once, after combining fields — otherwise a term in title and body gets two near-ceiling contributions, over-rewarding redundancy.
Query processing efficiency: TAAT vs DAAT vs WAND
Given the candidate set, you need the top k by score — fast. Two evaluation orders, then the pruning trick.
| Strategy | How | Trade-off |
|---|---|---|
| Term-at-a-time (TAAT) | Process one term's whole posting list, accumulating partial scores into a per-doc accumulator hash, then the next term, then sort. | Simple; but needs an accumulator for every doc that matches any term (huge for OR queries) and can't prune early — you touch every posting. |
| Document-at-a-time (DAAT) | Advance all term cursors together in docid order; for each docid, sum the contributions of the terms present, push into a top-k heap. | Bounded memory (just the heap), and — crucially — it knows the current k-th best score (the threshold), which enables skipping. The default in Lucene/modern engines. |
WAND and block-max WAND
WAND (Weak AND / Weighted AND, Broder et al. 2003) makes DAAT skip postings that cannot make the top k. Precompute, per term, its maximum possible contribution UBt (the largest BM25 term-score any doc could get from this term — driven by the term's IDF and best tf). Keep the term cursors sorted by current docid. To find the next candidate that could beat the threshold θ:
- Sort cursors by docid. Walk a running sum of UBt down the sorted cursors until the partial sum exceeds θ. The cursor at which the sum crosses θ is the pivot — its docid is the earliest doc that could possibly clear θ.
- Advance all earlier cursors to at least the pivot docid (skip pointers make this cheap). Fully score the pivot only if all required terms align; otherwise repeat.
Can a doc with only "network" + "the" beat θ? Upper bound = 4.2 + 0.3 = 4.5 < 8.0. No. So any docid where "neural" is absent is hopeless — WAND advances the "network" and "the" cursors past every docid below the next "neural" docid. If "neural" next appears at docid 9,000 and "network" was sitting at docid 600, we skip ~8,400 postings of "network" in one seek instead of scoring each.
Pivot logic: sort cursors by docid, accumulate UBs: 6.9 (neural) → still < 8.0; 6.9 + 4.2 = 11.1 ≥ 8.0 → pivot is the "network" cursor's docid. Only docs at/after that docid where the UB sum clears θ get fully scored. Every posting skipped is BM25 arithmetic and I/O not performed.
Block-max WAND (BMW) sharpens this: instead of one global UBt per term, store a per-block max score (from the block-max index). The upper bound for a region uses the local block maxima, which are far tighter than the global max, so the pivot advances faster and skips more. BMW is the standard top-k algorithm in modern Lucene/PISA-class engines — it can prune 80–95% of postings on common multi-term queries while returning the exact top k (it's safe pruning, not approximate).
Interactive · BM25 score explorer
Move the sliders and watch the three pieces of BM25 update live: the IDF (rarity weight), the length-normalisation factor (the denominator bracket), and the tf-saturation component. The bar chart sweeps tf from 1 to 20 at your current settings so you can see the saturation ceiling bend down as k₁ shrinks, and the whole curve sink as b penalises an over-length document. This is the real BM25 arithmetic, not an approximation.
Where lexical retrieval fails
BM25 is a bag-of-words, exact-term scorer. Its strengths are precisely its blind spots:
- Vocabulary mismatch. Query "car" won't match a document that only says "automobile." BM25 sees two different terms with zero overlap. Synonym expansion (lesson 41) and dense retrieval (lesson 43) exist to bridge this.
- Synonymy & morphology. "running shoes" vs "shoe for runners" — stemming helps a little, but lexical matching can't know "NYC" ≈ "New York City" without an explicit synonym map.
- No semantics / no word order beyond phrases. "dog bites man" and "man bites dog" score identically (same bag of words). BM25 cannot represent meaning, only term overlap.
- Polysemy. "jaguar" (animal vs car) — BM25 has no notion of sense; it matches the surface string regardless of intent.
And yet it still wins constantly: it is exact (a doc with your literal rare term will be found — no recall cliff for tail/long-tail and exact-phrase queries), interpretable (you can read off why a doc scored what it did — IDF × saturated tf, term by term), cheap (no GPU, milliseconds, trivially shardable), and zero-shot (no training, works on a brand-new corpus instantly). The modern answer is not "replace BM25 with embeddings" but hybrid: run lexical and dense in parallel and fuse. That's exactly where lesson 43 goes, and why lesson 03's ANN index is the dense complement to the inverted index here — two retrieval engines, fused, each covering the other's failures.
Interview prompts you should be ready for
- "Why does BM25 saturate term frequency, and what controls it?" (The 20th occurrence of a word adds almost nothing the 5th didn't — and unbounded tf invites keyword-stuffing spam. k₁ sets the approach rate to the ceiling k₁+1. A junior says "tf × idf"; a senior names the saturation and the spam-resistance it buys.)
- "Walk me through a full BM25 score for given N, df, tf, |d|, avgdl." (Compute IDF = ln(1+(N−df+0.5)/(df+0.5)), the length-norm bracket 1−b+b·|d|/avgdl, then the saturating tf term. The signal is doing the arithmetic cleanly and noting |d| > avgdl penalises the doc.)
- "How would you combine title and body relevance — just add two BM25 scores?" (No — saturate once. BM25F combines per-field tf into a single normalised pseudo-tf first, then applies saturation once, so a term in both fields isn't double-counted near the ceiling.)
- "Top-k over a billion-doc OR query is slow. How do you make it fast without losing correctness?" (DAAT + WAND / block-max WAND: precompute per-term (per-block) max contributions, maintain the top-k threshold θ, skip any docid whose upper-bound score ≤ θ. It's safe pruning — exact top-k, 80–95% postings skipped.)
- "Your index doubled in size and you didn't add positions. Where did the bytes go, and how do you get them back?" (Probably stored absolute docids or fp32 ids instead of gap + varbyte; or stored positions inline. Fixes: delta-encode, varbyte/PForDelta, split positions into a lazily-read file. Cite a concrete ratio — e.g. 20 B → 7 B on a short list, 4–8× on real lists.)
- "BM25 returns nothing for a query you know has good answers. Diagnose." (Vocabulary mismatch — query terms don't literally appear; or an analyzer asymmetry between index and query time (different stemming/tokenisation) silently killing exact matches. Senior move: check the analyzer symmetry first, then reach for synonyms / dense hybrid, not more BM25 tuning.)