The Inverted Index and Safe Dynamic Pruning (WAND, BlockMax-WAND)

BM25 tells us how to score one document against a query. It does not tell us how to find the ten best documents in a collection of ten million without computing ten million scores. That gap — between a scoring function and a retrieval system — is where the inverted index and dynamic pruning live, and it is the one place in classical IR where the mathematics is about algorithms rather than relevance.

The promise of dynamic pruning is unusually strong, and worth stating precisely up front: we will skip the vast majority of the collection and still return the exact top-k — the identical documents and scores an exhaustive scan would produce. Not an approximation, not a probabilistic guarantee with a failure rate, but the provably correct answer. The price, which we will be equally precise about, is that the guarantee is only on correctness, never on speed: a pathological query can force the algorithm to score everything.

top-k = 3

A. postings lists — cell = BM25 contribution; columns dimmed under WAND were never fully scored

	d0-margin	d1-hedge	d2-fx	d3-macro	d4-credit	d5-liquidity	d6-capital	d7-guidance	d8-tax	d9-boiler	UB
interest	1.53	1.28	·	·	·	0.89	·	·	·	0.89	1.532
rate	0.44	0.37	·	0.36	·	0.26	0.26	0.26	0.25	0.26	0.442
exposure	1.03	0.69	1.03	·	0.99	·	·	·	·	0.69	1.027

B. documents fully scored (lower is cheaper) — all three return the same top-3

exhaustive10 / 10

WAND6 / 10

BlockMax-WAND6 / 10

C. top-3 for “interest rate exposure”

1.d0-margin3.001
2.d1-hedge2.338
3.d9-boiler1.845

On ten documents the gap is small; at scale it is not — the notebook scores 209 of 5000 documents with BlockMax-WAND where the exhaustive scan scores 2870, for the identical top-k.

The visualizer above runs all three methods over a ten-document worked corpus for the query interest rate exposure. Switch between exhaustive scanning, WAND, and BlockMax-WAND and watch the “documents fully scored” bars: every method returns the same top-k ranking, but the pruning methods compute far fewer full scores. On ten documents the saving is modest; the closing section shows it scoring just 7% of the documents an exhaustive scan does at scale.

What we cover

The inverted index: postings lists, document frequency, the length array.
Document-at-a-time scoring, the exhaustive baseline.
WAND: per-term upper bounds, the threshold, and the pivot.
The safety theorem — WAND returns the exact top-k.
BlockMax-WAND: tighter local bounds and deeper skipping.
The honest limit: no asymptotic guarantee, and a finance case study at scale.

The inverted index

The data structure is the obvious one once you need it. Rather than store, per document, the list of terms it contains, store per term the list of documents that contain it.

Definition 1 (Inverted index).

For a collection of $N$ documents, the inverted index maps each term $t$ to a postings list — the documents containing $t$ , sorted by document id, each annotated with the term frequency $\text{tf}_{t,d}$ :

t \;\longmapsto\; \big[(d_1, \text{tf}_{t,d_1}),\, (d_2, \text{tf}_{t,d_2}),\, \dots\big], \qquad d_1 < d_2 < \cdots

Alongside it sit the document frequency $\text{df}_t$ (the length of $t$ ‘s postings list) and the length array $\text{dl}_d$ (each document’s token count), which together are all the statistics BM25 needs.

These are exactly the ingredients of the vector space model: the postings are the nonzero entries of the sparse term–document matrix, $\text{df}_t$ drives IDF, and $\text{dl}_d$ drives length normalization. Storing them term-major rather than document-major is what lets us answer a query by reading only the postings of the query’s terms — a handful of lists — instead of touching every document.

There are two ways to walk those lists. Term-at-a-time (TAAT) processing reads one full postings list, accumulates partial scores into an array of size $N$ , then moves to the next term. Document-at-a-time (DAAT) processing advances a cursor on every query term’s list in lockstep, fully scoring one document before moving on. DAAT is what modern engines use and what dynamic pruning requires, because pruning decisions are made per document, against a threshold that evolves as documents are scored.

Exhaustive document-at-a-time scoring

The baseline is honest and exact: score every document that contains at least one query term.

Definition 2 (Exhaustive DAAT top-k).

Maintain a min-heap of the $k$ best $(\text{score}, d)$ pairs seen so far. Advance the query terms’ cursors in document-id order; for each document $d$ that appears in any query term’s postings, compute its full BM25 score $\sum_{t \in q} \text{contribution}_t(d)$ , and offer it to the heap. After all postings are consumed, the heap holds the exact top-k.

This is correct by construction — it scores everything, so it cannot miss anything — and it is the ground truth every pruning method must reproduce. Its cost is one full score per document touched: on the union of the query terms’ postings lists, which for a common term can be a large fraction of the collection. The entire point of WAND is to compute the same answer while evaluating far fewer of those documents.

WAND: upper bounds, a threshold, and the pivot

The key observation is that we do not need a document’s exact score to rule it out — an upper bound suffices. For each term, precompute the largest contribution it can ever make.

Definition 3 (Per-term upper bound and the pivot).

For each query term $t$ , let its upper bound be its maximum contribution over its postings,

\text{UB}_t = \max_{d \,\in\, \text{postings}(t)} \text{contribution}_t(d).

Let $\theta$ be the current threshold — the $k$ -th largest score found so far (or $-\infty$ until $k$ documents have been scored). Sort the query terms by their cursors’ current document ids. The pivot is the first term in this order whose cumulative upper bound reaches the threshold:

\text{pivot} = \min\Big\{\, p : \textstyle\sum_{i \le p} \text{UB}_{t_i} \ge \theta \,\Big\},

and the pivot document is that term’s current document id. Any document with a smaller id cannot reach $\theta$ and is skipped; the pivot document is fully scored only if all earlier cursors already align on it.

WAND — “Weak AND,” or “Weighted AND” — is the loop built on this rule (Broder et al., 2003). The threshold rises as better documents are found, which raises the pivot, which skips ever more documents. The interactive panel above shows the upper bounds $\text{UB}_t$ at the right of each postings row; the dimmed columns are the documents WAND’s pivot rule never fully scores.

The safety theorem

Everything rests on one guarantee: that skipping never discards a document that belongs in the top-k.

Theorem 1 (WAND returns the exact top-k).

For any query, any $k$ , and any documents, WAND fully scores every document that appears in the true top-k, and therefore returns exactly the same $k$ documents and scores as the exhaustive scan.

Proof.

Two facts drive the proof. First, the threshold is monotonically non-decreasing: the heap only ever replaces its smallest element with a larger score, so its minimum $\theta$ can only rise. Let $\theta^\star$ be the final threshold — the $k$ -th largest score in the collection (assuming at least $k$ documents match; otherwise every matching document is returned and there is nothing to prove).

Second, the score of any document is bounded by the upper bounds of the terms it contains. Suppose, for contradiction, that WAND skips a document $d$ that belongs in the true top-k, so $\text{score}(d) \ge \theta^\star$ . A document is skipped only at some step where the cumulative upper bound over the terms whose cursors sit at or before $d$ falls short of the current threshold $\theta$ :

\text{score}(d) \;=\; \sum_{t \,:\, d \,\in\, \text{postings}(t)} \text{contribution}_t(d) \;\le\; \sum_{t \,:\, d \,\in\, \text{postings}(t)} \text{UB}_t \;<\; \theta \;\le\; \theta^\star.

The first inequality is the definition of the upper bound, applied term by term; the middle inequality is the skip condition — the only condition under which WAND advances past $d$ without scoring it; the last is monotonicity, since the current threshold never exceeds the final one. But this gives $\text{score}(d) < \theta^\star$ , contradicting $\text{score}(d) \ge \theta^\star$ . Hence no top-k document is ever skipped. Every top-k document is fully scored and offered to the heap, which retains the $k$ largest, so WAND’s output equals the exhaustive scan’s. $\;\blacksquare$

∎

The proof is worth dwelling on because it isolates exactly what the algorithm needs to be correct: a valid upper bound (one that is never smaller than the true contribution) and a monotone threshold. Any tighter upper bound that remains valid keeps the algorithm exact while pruning more — which is precisely the door BlockMax-WAND walks through.

BlockMax-WAND: tighter local bounds

A single global $\text{UB}_t$ is pessimistic. A term’s postings list might contain one document where it scores $1.5$ and a thousand where it scores $0.3$ ; the global upper bound is $1.5$ everywhere, so the pivot rule treats every one of those thousand documents as if it might score $1.5$ . BlockMax-WAND (Ding and Suel, 2011) fixes this by storing, for each fixed-size block of a postings list, the maximum contribution within that block.

Proposition 1 (Block maxima are valid, tighter upper bounds).

Partition each postings list into blocks and store each block’s maximum contribution. For a candidate pivot document, the sum of the relevant blocks’ maxima is an upper bound on the document’s true score (so pruning against it stays exact), and it is no larger than the global bound $\sum_t \text{UB}_t$ (so it prunes at least as much). When the block-max bound falls below the threshold, the document’s full score need not be computed at all.

Because each block maximum is taken over a subset of the postings, it is at most the global maximum, so the block-max bound is tighter; and because it is still a maximum over the actual contributions in that block, it remains a valid upper bound, so the safety proof goes through verbatim with $\text{UB}_t$ replaced by the local block maximum. The result is the same exact top-k with strictly more skipping — the notebook confirms BlockMax-WAND never scores more documents than WAND, and far fewer at scale. Variable-sized blocks (VBMW; Mallia et al., 2017) push this further by choosing block boundaries to make the maxima as tight as possible.

The honest limit: no asymptotic guarantee

Dynamic pruning is one of the rare algorithms whose correctness is provable but whose speedup is not.

⚠ Rigor flag

WAND and BlockMax-WAND are exact, but three honest qualifications matter:

No asymptotic guarantee. The worst case is still $O(\text{total postings})$ . When every document scores nearly the same — a single very common term, or a query whose terms are uncorrelated and uniformly distributed — the threshold barely separates documents, the pivot never advances past them, and the algorithm degrades to the exhaustive scan. The notebook makes this concrete: a flat-score query prunes nothing. The speedup is a data-dependent constant factor, not a better complexity class.
Block size is tuned. The choice of block size (and, in VBMW, the boundaries) trades index size and decompression cost against bound tightness; the good values are found empirically, not derived.
Upper bounds must be maintained. The guarantee assumes the stored maxima are correct and that scores are bounded above by them — which holds for BM25 but must be re-established for any other scoring function (a learned model with unbounded outputs, for instance) before the safety proof applies.

The discipline these flags enforce is the point of the topic: an exact pruning method is categorically different from an approximate nearest-neighbor index, and conflating “fast in practice” with “fast in the worst case” is exactly the kind of laundering this series exists to avoid.

Finance case study

§ Finance case study text pdf

The lexical leg of a production financial RAG retriever runs WAND-class pruning over an inverted index of 10-K / 10-Q filings and earnings-call transcripts — hundreds of thousands of documents, many of them long. Two properties of the math matter directly:

Exactness is non-negotiable. A retrieval system feeding a compliance or research workflow cannot quietly drop the one filing that answers the query. Because WAND is provably exact, the engineering team gets the latency of pruning with the correctness of a full scan — there is no recall/speed trade-off to defend in an audit.
The pruning is real because financial queries are selective. Queries like a specific GAAP line item, a ticker, or interest rate exposure contain terms whose postings lists are short or whose high-scoring documents are few, so the threshold rises quickly and most of the collection is skipped. The adversarial flat-score case is rare here precisely because the discriminating terms a financial analyst searches for are, by definition, not uniformly distributed.

The lexical leg’s exact top-k is then fused with dense retrieval via reciprocal rank fusion; dynamic pruning is what keeps that lexical leg cheap enough to run on every query.

In practice the index is also compressed — postings are delta-encoded and packed — so block-max indexes do double duty: the block boundaries that bound the scores are also the units of decompression, and skipping a block means skipping its decompression entirely. The I/O saved by not touching a block is often a larger win than the arithmetic saved by not scoring a document, which is why block-max methods, not plain WAND, are what production engines such as Lucene and PISA actually ship.

Implementation

The companion notebook builds an inverted index with real postings lists and scores it with BM25 replicated verbatim from the BM25 topic ( $k_1 = 1.5$ , $b = 0.75$ ), so the documents score identically to that page. It implements all three methods — exhaustive DAAT, WAND, and BlockMax-WAND — and turns the safety theorem into an assertion: across both the worked corpus and 150 random instances, the pruned methods return the exact top-k of the exhaustive scan, and the threshold is verified monotone.

The pruning is then measured rather than asserted. On a skewed synthetic collection the documents fully scored fall from 2870 (exhaustive) to 792 (WAND) to 209 (BlockMax-WAND) for the top-10 over $N = 5000$ — BlockMax-WAND computes full scores for just 7% of the documents the exhaustive scan does ( $209$ of $2870$ , about $4\%$ of the full collection) while returning the identical ranking. The honest counterpoint runs in the same harness: a flat-score query where every document is tied forces WAND to score all $40$ documents, exactly as many as the exhaustive scan, demonstrating that the guarantee is on correctness alone. The worked corpus the visualizer mirrors ( $N = 10$ , $\text{avgdl} = 9$ ) and its per-term upper bounds are printed by the harness so the page, the notebook, and the visualizer share one set of numbers.