A race with two medals

Suppose a query needs the best two documents. The straightforward plan is:

1. find every matching document;
2. compute every exact score;
3. sort the scores;
4. retain the first two.

That plan is correct, but it answers a larger question than the user asked. To identify the best two, the engine does not need the exact ordering of everyone below second place.

Keep the two best scores seen so far in a min-heap. Once the heap is full, let

$$\theta = \min_{d \in H} S(d)$$

be its smallest score. This is the score to beat. A new candidate can enter the heap only by scoring at least $\theta$; after a deterministic tie-break, one can make the comparison strict, but the conservative version is enough here.

The threshold alone saves nothing. We still need a cheap way to prove that a candidate cannot reach it.

A ceiling, not a guess

Assume the score is a sum of nonnegative query-term contributions:

$$S(d,q) = \sum_{t \in q} s_t(d), \qquad s_t(d) \ge 0.$$

For each query term $t$, precompute a value $U_t$ such that

$$\forall d, \quad s_t(d) \le U_t.$$

Then any candidate that can match only a subset $A$ of the query terms obeys

$$S(d,q) \le \sum_{t \in A} U_t.$$

If that sum is below $\theta$, exact scoring cannot change the top $k$.

Before continuing, decide which quantity may authorize a skip.

Put the cursors on the corpus

Return to the eight documents introduced in The Back of the Book. Consider the disjunctive query

fox field index pages evidence

and suppose its scorer produces these nonzero contributions:

The exact nonzero document scores are therefore:

A full evaluation scores all six candidates. WAND keeps one cursor per postings list and repeatedly orders the cursors by their current document ID. It accumulates term bounds from left to right until their sum reaches $\theta$. The cursor that crosses the threshold is the pivot.

Here is the whole trace for $k=2$. Before two results exist, take $\theta=0$.

The answer is documents 1 and 3, exactly as full evaluation would report. Four candidates were scored and two were rejected by proof.

The pivot algorithm

The following form assumes increasing document IDs, additive nonnegative scores, valid per-term upper bounds, and a heap whose threshold is zero until it contains $k$ results.

WAND-TOP-K(I, U, k)
Input:  postings iterators I[1:m], valid bounds U[1:m], result count k
Output: the k highest-scoring documents under the exact additive scorer

H ← empty min-heap
while at least one iterator is not exhausted
    order live iterators by their current document ID
    θ ← 0 if H has fewer than k items, otherwise H.MIN-SCORE
    bound ← 0
    pivot ← NIL
    for each iterator i in order
        bound ← bound + U[i]
        if bound ≥ θ
            pivot ← i
            break
    if pivot = NIL
        break
    p ← pivot.CURRENT-DOCUMENT
    if order[1].CURRENT-DOCUMENT = p
        score ← 0
        for each iterator i whose current document is p
            score ← score + i.CURRENT-CONTRIBUTION
            i.ADVANCE()
        RETAIN-IF-TOP-K(H, (p, score), k)
    else
        order[1].ADVANCE-TO(p)
return H in descending result order

Sorting $m$ cursors on every turn makes this presentation easy to inspect but is not the only implementation. The interesting operation is ADVANCE-TO(p): a postings iterator can seek to the first document ID at least $p$, often using skip data. The algorithm's benefit depends on how many exact scores and postings advances it avoids, not on the spelling of the cursor container.

Why the advance is sound

The dangerous line is the one that advances the first iterator. It may jump over document IDs without scoring them. We need more than a successful trace.

At the start of each turn, order live iterators by current document ID. Let $p$ be the first pivot document, and let $P$ be the iterators before the pivot. By the definition of “first pivot,”

$$\sum_{i \in P} U_i < \theta.$$

Now consider any document $d$ skipped when the first iterator advances to $p$. Because $d < p$, every iterator at $p$ or later is already past $d$ and cannot contain it. Thus $d$ can receive contributions only from iterators in $P$. Validity of the bounds gives

$$S(d,q) \le \sum_{i \in P} U_i < \theta.$$

So $d$ cannot enter the heap. Advancing past it preserves the top $k$.

If no pivot exists, even the sum of every remaining bound is below $\theta$. The same argument covers every unseen document, so termination is safe. If all iterators before the pivot already point to $p$, the algorithm does not skip: it computes $p$'s exact score and updates the heap. These cases exhaust every turn, which proves that the returned heap matches exhaustive evaluation.

What the proof costs

With $m$ query terms, exhaustive document-at-a-time evaluation visits the union of their postings and computes every candidate's exact score. The teaching algorithm adds cursor ordering and bound additions. If it re-sorts cursors each turn, that bookkeeping can cost $O(m \log m)$ per turn; practical variants keep the small cursor set ordered more carefully. The heap costs $O(\log k)$ for an accepted replacement and $O(k)$ space.

No single asymptotic expression promises a speedup. On the trace above:

WAND paid nine cheap additions to avoid two exact scores. Whether that wins in time depends on the scorer, postings layout, bound tightness, cache behavior, and query. The next chapter measures this crossover instead of assuming it.

Four wrong turns

Where the law stops

The proof above relies on additive nonnegative contributions and bounds that cover the exact scorer. Negative contributions, cross-term interactions, query-dependent features, and a later reranker need their own envelopes. One safe design retrieves a generous candidate set with bounded additive scores, then applies the unconstrained model only to those candidates. That preserves the first stage's theorem; it does not prove that the cascade equals ranking the entire collection with the later model.

MaxScore, introduced by Howard Turtle and James Flood, reaches the same broad goal with a different organization: terms whose maximum contributions cannot change the current top $k$ become nonessential. WAND and MaxScore should not be collapsed into one folklore algorithm. They are distinct ways to spend bounds against a threshold. The useful common abstraction is the proof obligation.

Lessons

• Top-k retrieval needs a threshold: the current kth score.
• A valid upper bound is a ceiling, not an estimate or average.
• Sorted postings prove that iterators at the pivot or later cannot contribute to earlier document IDs.
• An underestimate can change the answer; an overestimate only loses work.
• Dynamic pruning exchanges scoring work for proof work, so correctness alone does not establish a speedup.

Practice

1. Retrieval. Without looking back, state the inequality that licenses a pre-pivot cursor advance.
2. Discrimination. Give one quantity that predicts a score well but is not a valid upper bound.
3. Trace. Set $k=1$ in the six-candidate table. Recompute every threshold, pivot, exact score, and skip.
4. Repair. Suppose one query feature subtracts a penalty. State what must change in the bound before the proof applies.
5. Transfer. Name a non-search top-k system. Identify its score to beat, an admissible upper bound, and the cost of checking that bound.

The remaining question is economic. This chapter proved that skipping is safe; it did not prove that skipping is cheap. The Arithmetic of Skipping asks when a finer proof refunds more work than it consumes.

References

1. Broder, Carmel, Herscovici, Soffer, Zien. “Efficient Query Evaluation Using a Two-Level Retrieval Process.” CIKM 2003, 2003. — introduces WAND and its term-score upper-bound evaluation
2. Turtle and Flood. “Query Evaluation: Strategies and Optimizations.” Information Processing & Management 31(6), 1995. — introduces MaxScore's organization of essential and nonessential terms
3. Edsger W. Dijkstra. “Concern for Correctness as a Guiding Principle for Program Composition.” EWD 288, 1970. — primary source for the epigraph and its argument about what evidence can establish