A checkpoint in every block

Suppose the posting list for term $t$ is divided into consecutive blocks. The global term ceiling

$$U_t=\max_d c(t,d)$$

is valid everywhere, but it may be set by one exceptional document. For block $b$, record

$$U_{t,b}=\max_{d\in b}c(t,d).$$

Then every posting in that block satisfies

$$c(t,d)\le U_{t,b}\le U_t.$$

When the current iterators identify a candidate region, sum the ceilings of the blocks that could contribute. If the sum cannot beat threshold $\theta$, advance past the region without decoding and scoring its postings.

Safety is inherited

Let a candidate document $d$ lie in block $b_t(d)$ for each matching term $t$. Define the block bound

$$\widehat S_B(d)=\sum_t U_{t,b_t(d)}$$

and the coarser term bound

$$\widehat S_T(d)=\sum_t U_t.$$

For an additive nonnegative scorer,

$$S(d)\le\widehat S_B(d)\le\widehat S_T(d).$$

Proof. $S(d)\le B_1(d)<\theta$, so $d$ cannot displace a retained result at or above $\theta$. The inequality $B_1\le B_0$ is not needed for correctness; it establishes that the new bound is never looser than the old one. $\square$

This separation is valuable. Correctness asks whether the bound dominates the score. Performance asks how often it is strictly tighter by enough to cross the threshold.

The tax and the refund

Let

• $C_g$ be the cost of reading and combining a global term bound;
• $C_b$ be the additional cost of locating and combining block bounds;
• $C_d$ be the cost of decoding one block;
• $C_s$ be the cost of scoring its surviving postings;
• $p$ be the fraction of visited blocks safely skipped;
• $M$ be the number of block-bound decisions.

A first-order comparison is

$$T_{block}\approx T_{term}+M C_b-pM(C_d+C_s).$$

Block refinement pays when

$$p(C_d+C_s)>C_b.$$

The equation is intentionally local. Cache misses, branch prediction, prefetching, compression state, iterator synchronization, and threshold growth make the measured costs depend on workload and machine. But it tells us which quantities to instrument instead of staring at elapsed time alone.

Why one term cannot compete with itself

Consider a query with one term and a positive local score. Every document in its posting list is a candidate, and the top-k winners are simply the $k$ largest contributions. In document order, the term's block ceiling can say a block lies below the current threshold after the heap is full. That can skip some blocks if score maxima vary.

But ordinary WAND-style competitive pivoting has no second term whose bound can combine with or exclude the first. If the evaluator must traverse the single list to establish its winners, per-term pivot machinery supplies no competitive pruning. A specialized impact-ordered list or block-max traversal may help, but that is a different access order with its own index cost.

The honest lesson is narrower than the slogan “single-term queries can never prune”:

• multi-list WAND machinery cannot earn its coordination tax with one list;
• a document-ordered block-max list can skip only after a threshold exists and only when local maxima fall below it;
• an impact-ordered representation can retrieve high contributions early but pays in construction, storage, and other query shapes.

The machine should therefore report the actual mechanism, not credit every saved posting to “WAND.”

A refinement can be valid and vacuous

Suppose every block in one posting list contains at least one occurrence with the list-wide maximum contribution. Then

$$U_{t,b}=U_t$$

for every block. The hierarchy remains valid, but the middle ceiling has added no information.

This is likely when the bounded quantity has little within-list variation, or when blocks are large enough that nearly every one contains an extreme value. It can also happen when a coarse scoring quantization produces many equal maxima.

Measure the refinement gap

$$G_{t,b}=U_t-U_{t,b}$$

or ratio $U_{t,b}/U_t$, alongside the empirical distribution of local scores. If most gaps are zero, no threshold tuning will make the metadata informative. Smaller blocks may expose variance, but they add more maxima, headers, lookups, and cache pressure.

Block size is a three-way trade

Smaller blocks usually tighten maxima because fewer values compete to set each ceiling. They also increase:

• metadata entries and bytes;
• boundary searches and shallow pointer movements;
• branch and cache pressure;
• construction and update work.

Larger blocks reduce those taxes but approach the global maximum and decode more postings after a failed check. There is no corpus-independent optimum.

For block length $B$ and $N_t$ postings, the uncompressed maximum table holds approximately

$$\left\lceil N_t/B\right\rceil$$

entries. That is only the space term. Query time depends on how $B$ changes the refinement-gap distribution and the number of blocks actually visited.

The top-k problem being solved

This chapter's top-k is a cardinality-constrained selection over independent, already eligible document scores with a deterministic tie order. Under that structure, keeping the $k$ best scalar items is exact.

Do not silently transfer the pruning proof to a different feasible family. A result set with diversity quotas, coverage requirements, per-item costs, or sequence-dependent value is not ordinary scalar top-k. It may be a matroid, knapsack, submodular, or harder selection problem, and its threshold needs a corresponding theorem. Authority and mandatory coverage remain hard constraints, never score bonuses.

This classification prevents a common error: adding a diversity penalty to the heap and assuming a per-document ceiling still proves the best set.

Instrument the survivor funnel

Elapsed time says whether a run was fast. The survivor funnel says why:

Pair those counters with query strata:

• one term, two terms, and many terms;
• rare-only, common-only, and mixed-frequency terms;
• small and large $k$;
• high and low within-list score variance;
• cold and warm cache;
• successful hits and misses.

Report p50, p90, and p99 within each stratum. A mean over a mixture can make a rare spectacular win conceal a common small regression.

BLOCK-CAN-WIN(ITERATORS, THRESHOLD)
Input:  live term ITERATORS with valid global and current-block bounds, THRESHOLD
Output: true only when the current block region may contain a winner

globalBound ← SUM-GLOBAL-BOUNDS(ITERATORS)
if globalBound < THRESHOLD
    return false
blockBound ← SUM-CURRENT-BLOCK-BOUNDS(ITERATORS)
if blockBound < THRESHOLD
    return false
return true

The procedure is deliberately only a decision kernel. A complete Block-Max WAND evaluator also maintains document-ordered iterators, chooses pivots, performs shallow and deep advances, scores admitted candidates, and updates the heap. Chapter 10 already established those invariants; duplicating the full algorithm here would hide the new economic question.

Evidence before adoption

Keep the non-block evaluator and compare ordered top-k results over generated corpora. Then benchmark at least three contestants:

1. exhaustive document-at-a-time scoring;
2. term-bound WAND or MaxScore;
3. block-refined evaluation.

Record index bytes and build time as well as query latency. Use an unchanged control run to estimate benchmark noise. A block-max variant earns adoption only in the workload region where its Pareto point—time, bytes, construction, and complexity—is actually wanted.

The falsifying cases belong in the benchmark corpus:

• all block maxima equal the global maximum;
• one-term queries dominate;
• $k$ is so large that the threshold rises late;
• every block is tiny enough that metadata dominates;
• every block is large enough that bounds become coarse;
• a new scoring factor is omitted from the stored maximum.

The last case is a correctness failure; the others are economic failures. The suite should label them differently.

Lessons

• Per-block maxima refine per-term maxima and inherit the same safety theorem.
• A tighter valid bound can still do no useful work.
• Pruning pays only when skipped decode and scoring work exceeds bound metadata and evaluation cost.
• Multi-list WAND coordination cannot pay on a one-list query; specialized single-list access may still exploit impact or block order.
• Bound refinement pays in proportion to the within-unit variation it exposes.
• Smaller blocks tighten ceilings while increasing metadata and lookup costs.
• Counters explain a skip mechanism; clocks alone do not.
• Ordinary scalar top-k has only a cardinality constraint. Diversity, coverage, cost, or sequence dependence changes the selection problem.
• Exhaustive and coarser evaluators remain differential oracles.

Practice

1. Prove $S(d)\le\widehat S_B(d)\le\widehat S_T(d)$ from the per-term block inequalities.
2. With $C_b=3$, $C_d+C_s=30$, derive the minimum skip fraction predicted to break even.
3. Construct two eight-posting lists with equal global maxima: one whose four-posting block maxima vary and one whose block maxima are all equal.
4. Explain why increasing $k$ usually delays pruning. Give a countervailing workload effect that could complicate the measured result.
5. Design a generated-corpus differential test that inserts an omitted scoring boost and catches the resulting underestimated maximum.
6. Add a diversity quota to top-k and show why independent scalar selection no longer specifies the feasible result sets.

References

1. Shuai Ding and Torsten Suel. “Faster Top-k Document Retrieval Using Block-Max Indexes.” Proceedings of SIGIR, 2011.
2. Andrei Z. Broder, David Carmel, Michael Herscovici, Aya Soffer, and Jason Zien. “Efficient Query Evaluation Using a Two-Level Retrieval Process.” Proceedings of CIKM, 2003.
3. Joel Mackenzie, J. Shane Culpepper, Roi Blanco, Matt Crane, Charles L. A. Clarke, and Jimmy Lin. “Query Driven Algorithm Selection in Early Stage Retrieval.” Proceedings of WSDM, 2017.
4. Antonio Mallia, Michal Siedlaczek, Torsten Suel, and Nicola Tonellotto. “An Experimental Study of Index Compression and DAAT Query Processing Methods.” Proceedings of ECIR, 2019.