Ask the Reuters-21578 collection for palladium platinum nickel bullion krugerrand and five postings lists answer, with 53 postings between them in 42 different stories. Suppose only the two best stories are wanted. Scoring every one of the 42 would find them, and so would an evaluation that scores 13 of the 53 postings and looks at nothing else. How can an evaluation leave out three quarters of the postings and still be certain that it returns exactly the two stories, in the right order and with the right scores, that scoring everything would return?
It can because each term's contribution to a score has a known ceiling. Dynamic pruning is the name for query evaluation that uses such ceilings, during the evaluation of one query, to skip documents or postings that cannot reach the current top $k$. A pruning method is safe when its result is the same as that of exhaustive evaluation. The two classical safe methods for postings lists in docID order are MaxScore (Turtle and Flood, 1995) and WAND (Broder, Carmel, Herscovici, Soffer, and Zien, 2003). The course met them in passing. Implementing BM25 ran a simplified MaxScore on Cranfield and gave the argument for its scoring rule in a paragraph, and computing vector scores stated when WAND is exact. This article states both algorithms completely, cursor movements included, and proves them safe, ties included.
Here is the route. First we fix the setting: additive scores, an upper bound for each term, and the threshold. Then we prove one lemma that says what any pruning method must guarantee to be safe. We state MaxScore, trace it on the five lists, and prove that it meets the lemma's conditions, and then do the same for WAND. Finally we count the postings each method scores on 1,500 Reuters queries and on this site's own search index, and solve three problems. The article assumes the document-at-a-time evaluation and the top-$k$ heap of computing vector scores, and the BM25 formula of Okapi BM25. Every number is computed by tools/experiments/query-processing/dynamic-pruning-with-maxscore-and-wand.py, which asserts on every query that the pruned and the exhaustive top $k$ are identical.
The setting
Three assumptions carry the whole article.
Scores are sums of term contributions. A query $q$ is a set of terms. Each term $t$ gives each document $d$ a contribution $s_t(d) \ge 0$, which is zero when $d$ does not contain $t$, and the score is
$$S(d) = \sum_{t \in q} s_t(d).$$
BM25 has this form, as do cosine scores, each term's contribution being divided by the document's norm, and the BM25F scores of this site's search. The contribution of a posting can be computed from the posting and from numbers stored per document, as implementing BM25 showed.
Each list knows its largest contribution. The upper bound of term $t$ is
$$U_t = \max_d s_t(d),$$
the largest contribution anywhere in its postings list. It is one number per term, computed when the index is built and kept in the dictionary. The course page compared this exact bound with the looser $(k_1 + 1)\,\mathrm{IDF}(t)$, which needs no pass over the list. Both are valid, and the difference between them is measured below.
Ties have a rule. Documents are ranked by decreasing score, and documents with equal scores by increasing docID. Write $d \succ d'$ when $d$ ranks above $d'$: either $S(d) > S(d')$, or $S(d) = S(d')$ and $d < d'$. This is a total order on the documents that match the query, those that contain at least one query term. "The top $k$" means the first $k$ of them in that order, or all of them if fewer than $k$ match. A proof of safety must say what happens to a document whose score equals that of the $k$-th, and it can only do so once the tie rule is fixed.
Document-at-a-time evaluation keeps a cursor in each list, on its current posting, and a min-heap of the $k$ best documents scored so far. The threshold $\theta$ is the smallest score in that heap once it holds $k$ documents. Until then $\theta = -\infty$.
The running example
The collection is Reuters-21578 as the course's indexing pages load it: 10,788 stories numbered in filing order, tokens in lowercase letters only, no stop list and no stemming. Scores are BM25 with $k_1 = 1.2$, $b = 0.75$ and Lucene's IDF, the formula of implementing BM25:
$$s_t(d) = \ln\left(1 + \frac{N - \mathit{df}_t + 0.5}{\mathit{df}_t + 0.5}\right) \cdot \frac{\mathit{tf}_{t,d}\,(k_1 + 1)}{\mathit{tf}_{t,d} + K_d}, \qquad K_d = k_1\left(1 - b + b\,\frac{L_d}{L_{\mathrm{avg}}}\right).$$
One contribution by hand: palladium occurs in 5 of the 10,788 stories, so its IDF is $\ln(1 + 10783.5/5.5) = 7.5815$. Story 1521 has 78 tokens against an average of 123.31, so $K_d = 1.2\,(0.25 + 0.75 \times 78/123.31) = 0.8693$. The term occurs twice in it, and $7.5815 \times \frac{2 \times 2.2}{2 + 0.8693} = 11.6261$.
Every contribution is rounded to four decimals and stored as a whole number of ten-thousandths, the rounding this site's own search applies to the term weights it sends to the browser. Sums of whole numbers are exact. So the exhaustive and the pruned evaluations compute the same score for a document in whatever order they add, and the proofs below, which assume exact arithmetic, apply to the code as it runs. The course page had to leave a caveat about floating point at this spot. Storing integer contributions removes it, and real engines that store quantized impacts get the same benefit.
The five lists, each posting written as docID: contribution:
- palladium: 1467: 11.5966, 1521: 11.6261, 1792: 8.4603, 1795: 8.3369, 8079: 10.8247
- platinum: 179: 4.9434, 260: 6.5295, 358: 4.0756, 400: 6.7243, 1467: 11.8222, 1521: 11.8369, 1792: 9.3522, 1795: 9.2612, 2224: 5.0482, 3686: 5.5323, 5361: 11.1748, 7392: 5.4220, 8079: 11.7725, 8515: 6.0034, 8567: 5.4688, 9254: 11.2274, 9403: 10.1599, 9561: 10.8976, 9709: 9.9761
- nickel: 601: 5.2176, 1467: 7.8354, 1521: 7.8660, 2645: 11.4768, 3192: 7.6567, 4071: 6.9940, 5209: 7.6859, 5876: 7.7317, 6113: 11.9005, 6518: 7.8051, 7189: 10.1204, 7662: 11.0367, 7820: 10.9351
- bullion: 351: 10.6555, 983: 6.3249, 2070: 10.1138, 2230: 10.1138, 2442: 4.2305, 3773: 5.6283, 5605: 5.1220, 5637: 5.1220, 5646: 9.2255, 6033: 5.3210, 6418: 6.4896, 8459: 1.9310, 8515: 6.2850, 9403: 9.3763
- krugerrand: 2442: 5.3552, 5646: 5.5680
| Term | Postings | Upper bound $U_t$ | Reached in story |
|---|---|---|---|
| palladium | 5 | 11.6261 | 1521 |
| platinum | 19 | 11.8369 | 1521 |
| nickel | 13 | 11.9005 | 6113 |
| bullion | 14 | 10.6555 | 351 |
| krugerrand | 2 | 5.5680 | 5646 |
Exhaustive evaluation reads all 53 postings and scores 42 stories. The best three are story 1521 with 31.3290, story 1467 with 31.2542, and story 8079 with 22.5972. The first two contain palladium, platinum and nickel, and the third contains palladium and platinum. With $k = 2$, the answer is stories 1521 and 1467, and the final threshold is 31.2542.
What safety requires
Both algorithms decide, for some documents, not to compute a score. Here is the idea in one sentence: a document may be left out as soon as its score is known to be at most the threshold. The reason is that documents are visited in docID order, so everything already in the heap beats it on score or on the tie rule. The lemma makes that precise once, so that each algorithm only has to be checked against its conditions.
An evaluation makes a sequence of offers. An offer presents a document $d$ and a number $\sigma$. It is accepted if the heap holds fewer than $k$ documents or if $\sigma > \theta$. An accepted document enters the heap with score $\sigma$, and if the heap then holds more than $k$ documents, the lowest of them in the order $\succ$ is removed. An offer is exact if $\sigma = S(d)$.
Lemma (safety). Suppose an evaluation satisfies three conditions.
- Offers are made in strictly increasing order of docID.
- Every accepted offer is exact.
- For every matching document $d$ that is never offered exactly, there is a moment $\tau(d)$ during the evaluation at which $S(d) \le \theta$, and every document accepted before $\tau(d)$ has a smaller docID than $d$.
Then, when the evaluation ends, the heap holds exactly the top $k$ matching documents, each with its exact score.
Proof. Call $E$ the set of documents that are offered exactly.
Step 1: at every moment the heap holds the top $k$, in the order $\succ$, of the documents of $E$ offered so far, with exact scores. This is true at the start, when both are empty. Suppose it is true before some offer. If the offer is not exact, condition 2 says it is not accepted, so the heap does not change, and neither does the set of exactly offered documents. If the offer is exact, with document $d$ and score $S(d)$, there are two cases. When the heap holds fewer than $k$ documents, $d$ is accepted, which is right, since fewer than $k$ documents of $E$ came before it. When the heap is full, let $h$ be its lowest document, so that $S(h) = \theta$. By condition 1 every document in the heap was offered before $d$ and has a smaller docID. So $d \succ h$ holds exactly when $S(d) > \theta$: with equal scores the tie goes to $h$. The offer is accepted exactly when $d$ ranks above the lowest document of the heap, and then $h$ is the one removed. That is the rule that turns the top $k$ of a set into the top $k$ of the set with one more element. The scores in the heap are exact because only exact offers are accepted.
Step 2: a matching document $d$ outside $E$ is not among the top $k$ of all matching documents. By condition 3 there is a moment $\tau(d)$ with $S(d) \le \theta$. Since $S(d) \ge 0$, the threshold is not $-\infty$ at that moment, so the heap holds $k$ documents. Each of them, $h$, has $S(h) \ge \theta \ge S(d)$, and by condition 3 a smaller docID than $d$. So $h \succ d$ for each of the $k$. By step 1 their scores are exact. Therefore $k$ matching documents rank above $d$.
Step 3. By step 2 every document of the true top $k$ lies in $E$. A set that contains the top $k$ of a larger set has the same top $k$. So the top $k$ of $E$ is the top $k$ of all matching documents, and by step 1 it is what the heap holds at the end. If fewer than $k$ documents match, the heap is never full, $\theta$ stays at $-\infty$, no document can satisfy condition 3, and so every matching document is in $E$ and in the heap. $\blacksquare$
The lemma is where the direction of the inequality comes from. A document is pruned when its bound is at most $\theta$, and it is accepted only when its score is strictly above $\theta$. Both follow from breaking ties toward the smaller docID while visiting documents in increasing docID order. An engine that broke ties the other way would have to prune only on a bound strictly below $\theta$.
MaxScore
Here is the idea in one sentence: once the threshold is high enough, a document that contains only the weakest terms cannot reach it. Those terms' lists then stop proposing documents and are consulted only for documents that some stronger term proposes.
Sort the query's lists by increasing upper bound, $U_1 \le U_2 \le \dots \le U_m$, and write $P_i = U_1 + \dots + U_i$ for the prefix sums, with $P_0 = 0$. A document that contains none of the terms $i+1, \dots, m$ scores at most $P_i$. For the running example:
| $i$ | Term | $U_t$ | Prefix sum $P_i$ |
|---|---|---|---|
| 1 | krugerrand | 5.5680 | 5.5680 |
| 2 | bullion | 10.6555 | 16.2235 |
| 3 | palladium | 11.6261 | 27.8496 |
| 4 | platinum | 11.8369 | 39.6865 |
| 5 | nickel | 11.9005 | 51.5870 |
At any moment the lists split in two. Lists $1, \dots, e-1$ are non-essential: $e$ is chosen so that $P_{e-1} \le \theta$. Lists $e, \dots, m$ are essential. With $\theta = 31.2542$ the first three lists are non-essential, since $P_3 = 27.8496 \le \theta < P_4$: a story with krugerrand, bullion and palladium but neither platinum nor nickel cannot beat the two stories already held.
The algorithm, adapted from Tonellotto, Macdonald and Ounis (2018, Algorithm 3.1), repeats five steps. They note that the original paper leaves implementation details open and that several later descriptions exist, so this is one precise version of the method that Turtle and Flood introduced.
- While $e \le m$ and $P_e \le \theta$, increase $e$ by one. If $e > m$, stop.
- Let $d$ be the smallest docID under the cursors of the essential lists. If all of them are exhausted, stop. Call $d$ the candidate.
- Set $\sigma$ to the sum of the contributions of the essential lists whose cursor is on $d$, and advance each of those cursors by one posting.
- For $i = e - 1$ down to $1$: if $\sigma + P_i \le \theta$, abandon $d$ and go back to step 1. Otherwise move the cursor of list $i$ forward to its first posting with docID at least $d$, and if that posting is $d$, add its contribution to $\sigma$.
- Offer $d$ with $\sigma$, and go back to step 1.
Step 4 is where postings are saved. The test $\sigma + P_i \le \theta$ says that even if every list not yet consulted, $1$ to $i$, gave $d$ its largest contribution, $d$ would not beat the threshold. The cursor movement in step 4 is the operation that skip pointers exist for: "move to the first posting with docID at least $d$" passes over postings without reading their contributions.
MaxScore on the running example
With $k = 2$, MaxScore considers 32 of the 42 stories as candidates and completes the score of 9. The column "Essential lists" gives $m - e + 1$ after step 1, and the last column gives $\theta$ after the row's story has been dealt with.
| Story | Essential lists | Contributions added | Outcome | $\theta$ after |
|---|---|---|---|---|
| 179 | 5 | pla 4.9434 | score 4.9434: enters | −∞ |
| 260 | 5 | pla 6.5295 | score 6.5295: enters | 4.9434 |
| 351 | 5 | bul 10.6555 | score 10.6555: enters | 6.5295 |
| 358 | 4 | pla 4.0756 | score 4.0756: rejected | 6.5295 |
| 400 | 4 | pla 6.7243 | score 6.7243: enters | 6.7243 |
| 601 | 4 | nic 5.2176 | score 5.2176: rejected | 6.7243 |
| 983 | 4 | bul 6.3249 | score 6.3249: rejected | 6.7243 |
| 1467 | 4 | pal 11.5966 + pla 11.8222 + nic 7.8354 | score 31.2542: enters | 10.6555 |
| 1521 | 4 | pal 11.6261 + pla 11.8369 + nic 7.8660 | score 31.3290: enters | 31.2542 |
| 1792 | 2 | pla 9.3522 + pal 8.4603 | 17.8125 + 5.5680 ≤ $\theta$: abandoned | 31.2542 |
| 1795 | 2 | pla 9.2612 + pal 8.3369 | 17.5981 + 5.5680 ≤ $\theta$: abandoned | 31.2542 |
| 2224 | 2 | pla 5.0482 | 5.0482 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 2645 | 2 | nic 11.4768 | 11.4768 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 3192 | 2 | nic 7.6567 | 7.6567 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 3686 | 2 | pla 5.5323 | 5.5323 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 4071 | 2 | nic 6.9940 | 6.9940 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 5209 | 2 | nic 7.6859 | 7.6859 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 5361 | 2 | pla 11.1748 | 11.1748 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 5876 | 2 | nic 7.7317 | 7.7317 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 6113 | 2 | nic 11.9005 | 11.9005 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 6518 | 2 | nic 7.8051 | 7.8051 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 7189 | 2 | nic 10.1204 | 10.1204 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 7392 | 2 | pla 5.4220 | 5.4220 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 7662 | 2 | nic 11.0367 | 11.0367 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 7820 | 2 | nic 10.9351 | 10.9351 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 8079 | 2 | pla 11.7725 + pal 10.8247 | 22.5972 + 5.5680 ≤ $\theta$: abandoned | 31.2542 |
| 8515 | 2 | pla 6.0034 | 6.0034 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 8567 | 2 | pla 5.4688 | 5.4688 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 9254 | 2 | pla 11.2274 | 11.2274 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 9403 | 2 | pla 10.1599 | 10.1599 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 9561 | 2 | pla 10.8976 | 10.8976 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
| 9709 | 2 | pla 9.9761 | 9.9761 + 16.2235 ≤ $\theta$: abandoned | 31.2542 |
Three moments in the table show the method at work.
- Story 351 makes the first list non-essential. After it the heap holds stories 351 and 260, and $\theta = 6.5295$ exceeds $P_1 = 5.5680$. From then on krugerrand proposes no candidates. Its two stories, 2442 and 5646, are never candidates in their own right. Story 2442 scores $4.2305 + 5.3552 = 9.5857$ and story 5646 scores $9.2255 + 5.5680 = 14.7935$, both far below the final threshold.
- Story 1521 makes three lists non-essential. With $\theta = 31.2542$ only platinum and nickel remain essential. Stories that contain only bullion, such as 2070 and 2230 with 10.1138 each, are passed over without a posting being scored.
- Story 1792 is abandoned after two contributions. Platinum is essential and gives 9.3522. Could the rest lift the story over $\theta$? The bound is $9.3522 + P_3 = 37.2018$, so palladium is consulted and adds 8.4603. Then $17.8125 + P_2 = 34.0360$ still exceeds $\theta$, so bullion's cursor is moved to its first posting at or after 1792, which is story 2070: no contribution. Now only krugerrand is left, and $17.8125 + 5.5680 = 23.3805 \le \theta$. The story is abandoned. Its true score is 17.8125, the fifth highest of all.
In all, MaxScore reads 39 of the 53 contributions: every posting of the two lists that stay essential to the end, 19 and 13, the five postings of palladium, and two of bullion. The price of its simple control is visible in the lower half of the table. Every posting of an essential list becomes a candidate and has its contribution read, even when one comparison then abandons it.
Proof that MaxScore is safe
Theorem. MaxScore, as stated above, ends with the heap holding exactly the top $k$ matching documents with their exact scores.
Proof. We check the three conditions of the lemma. Two facts about cursors are used throughout. First, $\theta$ never decreases, so $e$ never decreases: a list that has become non-essential stays so. Second, the cursor of a list moves in only two ways. While the list is essential, step 3 moves it by one posting, past a posting of the current candidate. While it is non-essential, step 4 moves it to its first posting at or after the current candidate, which passes only postings with smaller docIDs than that candidate.
Condition 1. A candidate $d$ is the smallest docID under the essential cursors, and step 3 advances every essential cursor that is on $d$. Afterwards every essential cursor is beyond $d$, and the essential lists of later rounds are among the present ones. So the next candidate is larger. Offers are made only for candidates, hence in increasing order.
Condition 2. We show that every offer is exact. When step 5 offers $d$, the loop of step 4 has run to the end, so every list has been consulted. Take any list that contains $d$. If it is essential, its cursor has never passed the posting of $d$ before this round, because an essential cursor only passes postings of earlier candidates, which are smaller than $d$. And it is not short of $d$, because $d$ is the minimum of the essential cursors. So its cursor is on $d$ and step 3 adds the contribution. If the list is non-essential, every posting behind its cursor belongs to an earlier candidate or precedes one, by the second fact. So the posting of $d$ is at or after the cursor, and step 4 finds it and adds it. Hence $\sigma = S(d)$.
Condition 3. Let $d$ be a matching document that is never offered. Either it was a candidate and was abandoned, or it was never a candidate.
Suppose $d$ was abandoned in step 4 at index $i$, so that $\sigma + P_i \le \theta$. By the argument for condition 2, $\sigma$ is the exact sum of the contributions to $d$ from lists $i + 1, \dots, m$. Lists $1, \dots, i$ contribute at most $U_1 + \dots + U_i = P_i$. So $S(d) \le \sigma + P_i \le \theta$ at that moment, and every document accepted earlier was an earlier candidate, with a smaller docID. Take that moment as $\tau(d)$.
Suppose $d$ was never a candidate. Let $\tau(d)$ be the first moment at which step 2 selects a candidate larger than $d$, or, if there is none, the moment the algorithm stops. Every candidate before $\tau(d)$ is smaller than $d$, so every document accepted before $\tau(d)$ has a smaller docID. We claim that at $\tau(d)$ every list containing $d$ is non-essential. Suppose an essential list contained $d$. If the algorithm stopped in step 1, no list is essential, a contradiction. Otherwise its cursor is beyond $d$: either it is exhausted, or it is at least the new candidate, which is larger than $d$. So the cursor has passed the posting of $d$. The list was essential all along, so that happened in step 3 of a round whose candidate was $d$. But $d$ was never a candidate. This proves the claim. All the terms of $d$ are therefore among lists $1, \dots, e - 1$, and there is at least one such list because $d$ matches the query. So $S(d) \le P_{e-1} \le \theta$ at $\tau(d)$, where the last inequality is how step 1 chose $e$. $\blacksquare$
WAND
MaxScore decides list by list which terms may propose candidates. WAND decides document by document, and gets a sharper test. Here is the idea in one sentence: order the cursors by the docID they point at, and add up upper bounds in that order until the sum first exceeds the threshold. The docID reached is the first document that could possibly qualify, so every cursor behind it may jump there.
The name comes from the operator that Broder and his coauthors (2003, section 2.2) defined, "a new Boolean predicate called WAND standing for Weak AND, or Weighted AND". WAND takes truth values $X_1, \dots, X_n$ with positive weights $w_1, \dots, w_n$ and a threshold, and is true when the weights of the true variables sum to at least the threshold. With unit weights it is AND when the threshold is $n$ and OR when the threshold is 1, and they justify the name by that range: varying the threshold moves the operator "from being close to an OR to being close to an AND". Applied to a document, $X_i$ says whether the document contains term $i$, and the weight is the term's upper bound. A document for which the operator is false cannot reach the threshold and need not be scored. The operator is stated with "at least". The algorithm below prunes on "at most $\theta$" and keeps only "strictly above", which is the test the safety lemma supports under our tie rule. The paper's own algorithm does the same: its pivot is the first term at which the accumulated upper bounds "exceed the given threshold" (section 2.4), and a fully scored document enters the heap only if its score "is larger than the minimum score in the heap" (section 2.5).
The algorithm repeats four steps, with the lists that are not exhausted.
- Order the lists by the docID under their cursor: $c_{(1)} \le c_{(2)} \le \dots$, where $c_{(j)}$ is the docID under the cursor that is $j$-th in the order and $U_{(j)}$ is that list's upper bound. Lists whose cursors are on the same docID are kept in query order. Any fixed rule would do: the trace below depends on it, and the proof does not.
- Find the smallest $p$ with $U_{(1)} + \dots + U_{(p)} > \theta$. If there is none, stop. The list in position $p$ is the pivot list and $\pi = c_{(p)}$ is the pivot.
- If $c_{(1)} = \pi$: set $\sigma$ to the sum of the contributions of all lists whose cursor is on $\pi$, advance each of those cursors by one posting, and offer $\pi$ with $\sigma$.
- Otherwise choose a list before position $p$ whose cursor is below $\pi$, and move its cursor forward to its first posting with docID at least $\pi$.
In step 3 the cursors in positions 1 to $p$ are all on $\pi$, since they are sorted and the first and the $p$-th are equal. Lists after position $p$ may be on $\pi$ too, and they are included. Step 4 leaves a choice, and the proof holds for any choice. The version traced here takes the list nearest to the pivot in the order, as the algorithm of Tonellotto, Macdonald and Ounis does. Broder and his coauthors (2003, section 2.4) leave the choice to a helper they call pickTerm, observe that it affects speed and never the set of documents that are fully scored, and choose the term with the largest idf, "assuming the rarest term will produce the largest skip". As Tonellotto, Macdonald and Ounis (2018, section 3.3) report, the method was designed for indexes on disk and moves one list at a time for that reason. The same survey describes variants for indexes in memory that move every list before the pivot at once.
Why can a document below the pivot not qualify? A document $d < \pi$ can only be found, from here on, in lists whose cursor is at or before $d$, hence below $\pi$, hence before position $p$. The bounds of those lists sum to at most $\theta$, because $p$ was the first position at which the sum exceeded it.
WAND on the running example
With $k = 2$, WAND takes 31 steps: 9 scorings and 22 cursor movements. Cursors are listed in the order palladium, platinum, nickel, bullion, krugerrand, and "end" marks an exhausted list. The last column gives $\theta$ after the step.
| Step | Cursors: pal, pla, nic, bul, kru | Pivot | Action | $\theta$ after |
|---|---|---|---|---|
| 1 | 1467 179 601 351 2442 | 179 (pla) | score: pla 4.9434, enters | −∞ |
| 2 | 1467 260 601 351 2442 | 260 (pla) | score: pla 6.5295, enters | 4.9434 |
| 3 | 1467 358 601 351 2442 | 351 (bul) | score: bul 10.6555, enters | 6.5295 |
| 4 | 1467 358 601 983 2442 | 358 (pla) | score: pla 4.0756, rejected | 6.5295 |
| 5 | 1467 400 601 983 2442 | 400 (pla) | score: pla 6.7243, enters | 6.7243 |
| 6 | 1467 1467 601 983 2442 | 601 (nic) | score: nic 5.2176, rejected | 6.7243 |
| 7 | 1467 1467 1467 983 2442 | 983 (bul) | score: bul 6.3249, rejected | 6.7243 |
| 8 | 1467 1467 1467 2070 2442 | 1467 (pal) | score: pal 11.5966 + pla 11.8222 + nic 7.8354 = 31.2542, enters | 10.6555 |
| 9 | 1521 1521 1521 2070 2442 | 1521 (pal) | score: pal 11.6261 + pla 11.8369 + nic 7.8660 = 31.3290, enters | 31.2542 |
| 10 | 1792 1792 2645 2070 2442 | 2070 (bul) | move pla from 1792 to 2224 | 31.2542 |
| 11 | 1792 2224 2645 2070 2442 | 2224 (pla) | move bul from 2070 to 2230 | 31.2542 |
| 12 | 1792 2224 2645 2230 2442 | 2230 (bul) | move pla from 2224 to 3686 | 31.2542 |
| 13 | 1792 3686 2645 2230 2442 | 2645 (nic) | move kru from 2442 to 5646 | 31.2542 |
| 14 | 1792 3686 2645 2230 5646 | 2645 (nic) | move bul from 2230 to 3773 | 31.2542 |
| 15 | 1792 3686 2645 3773 5646 | 3686 (pla) | move nic from 2645 to 4071 | 31.2542 |
| 16 | 1792 3686 4071 3773 5646 | 3773 (bul) | move pla from 3686 to 5361 | 31.2542 |
| 17 | 1792 5361 4071 3773 5646 | 4071 (nic) | move bul from 3773 to 5605 | 31.2542 |
| 18 | 1792 5361 4071 5605 5646 | 5361 (pla) | move nic from 4071 to 5876 | 31.2542 |
| 19 | 1792 5361 5876 5605 5646 | 5605 (bul) | move pla from 5361 to 7392 | 31.2542 |
| 20 | 1792 7392 5876 5605 5646 | 5876 (nic) | move kru from 5646 to end | 31.2542 |
| 21 | 1792 7392 5876 5605 end | 5876 (nic) | move bul from 5605 to 6033 | 31.2542 |
| 22 | 1792 7392 5876 6033 end | 6033 (bul) | move nic from 5876 to 6113 | 31.2542 |
| 23 | 1792 7392 6113 6033 end | 6113 (nic) | move bul from 6033 to 6418 | 31.2542 |
| 24 | 1792 7392 6113 6418 end | 6418 (bul) | move nic from 6113 to 6518 | 31.2542 |
| 25 | 1792 7392 6518 6418 end | 6518 (nic) | move bul from 6418 to 8459 | 31.2542 |
| 26 | 1792 7392 6518 8459 end | 7392 (pla) | move nic from 6518 to 7662 | 31.2542 |
| 27 | 1792 7392 7662 8459 end | 7662 (nic) | move pla from 7392 to 8079 | 31.2542 |
| 28 | 1792 8079 7662 8459 end | 8079 (pla) | move nic from 7662 to end | 31.2542 |
| 29 | 1792 8079 end 8459 end | 8459 (bul) | move pla from 8079 to 8515 | 31.2542 |
| 30 | 1792 8515 end 8459 end | 8515 (pla) | move bul from 8459 to 8515 | 31.2542 |
| 31 | 1792 8515 end 8515 end | 8515 (bul) | move pal from 1792 to end | 31.2542 |
Until the heap is full, at step 2, the threshold is $-\infty$, the first list in the order is already the pivot list, and every document is scored. Steps 3 to 9 still score every document they reach, because the threshold is low. The method shows itself from step 10.
- Step 10. The cursors in order are palladium and platinum on 1792, bullion on 2070, krugerrand on 2442 and nickel on 2645. The sums of bounds are 11.6261, then 23.4630, then 34.1185, the first to exceed 31.2542. So the pivot is 2070 and bullion is the pivot list. Story 1792 lies below the pivot: only palladium and platinum can still contribute to it, and their bounds sum to 23.4630. Platinum's cursor jumps from 1792 to its first posting at or after 2070, which is 2224, and passes story 1795 on the way. Neither story is scored. MaxScore read two contributions for each.
- Steps 13 and 14. The pivot is 2645 twice in a row. First krugerrand is moved up to it and lands on 5646, then bullion and lands on 3773. Each movement passes postings (story 2442 in krugerrand; stories 2230 and 2442 in bullion) whose stories are never scored.
- Step 28. Story 8079, the third best of all with 22.5972, becomes the pivot. Palladium's cursor is still on 1792, so the story cannot be scored yet, and nickel is moved up and runs out. At step 29 the pivot has moved on to 8459, and platinum jumps over 8079 without it ever being scored. That is correct: with only palladium, platinum and bullion left, the bounds available to story 8079 are those of palladium and platinum, 23.4630, below the threshold.
- The end. After step 31 only platinum and bullion remain, both on 8515. Their bounds sum to $11.8369 + 10.6555 = 22.4924 \le \theta$, no pivot exists, and the algorithm stops with the last six postings of platinum and the last two of bullion never scored.
WAND reads 13 contributions, against MaxScore's 39 and the exhaustive 53, and returns the same two stories. It pays in a different coin: 22 cursor movements, each preceded by ordering the cursors and summing bounds.
Proof that WAND is safe
Theorem. WAND, as stated above and with any choice in step 4, ends with the heap holding exactly the top $k$ matching documents with their exact scores.
Proof. Say that a cursor passes a posting when it moves from that posting or from an earlier one to a later one. Step 3 passes only postings of the document it offers. Step 4 passes postings without their documents being scored; call that skipping them. Three facts are needed.
Fact A. In step 3 the pivot equals $c_{(1)}$, the smallest docID under any cursor. So every cursor is at or beyond $\pi$ before the step and strictly beyond it after. It follows that offers are made in strictly increasing order of docID, which is condition 1, and that at every moment each document offered so far is smaller than the docID under every cursor.
Fact B. Suppose step 4 moves a list from docID $c$ to its first posting at or after $\pi$, and let $d$ be a document with $c \le d < \pi$. Then the contributions to $d$ from postings that no cursor has passed sum to at most $\theta$. Indeed such a posting lies in a list whose cursor is at or before $d$, hence below $\pi$. In the order of step 1 that list stands before position $p$. And $U_{(1)} + \dots + U_{(p-1)} \le \theta$ by the choice of $p$ as the smallest position at which the sum exceeds $\theta$.
Fact C. When the algorithm stops, the upper bounds of all lists that are not exhausted sum to at most $\theta$, because step 2 found no $p$.
Condition 3. Let $d$ be a matching document that is never offered exactly. There are two cases.
Suppose some posting of $d$ is skipped at some time, and let $\tau(d)$ be the moment just before the first such movement. Before $\tau(d)$ no posting of $d$ has been passed at all. Not by a skip, since this is the first. Not by step 3 either. That would have been an offer of $d$ made when no posting of $d$ had been passed. Every list containing $d$ then had its cursor at or before $d$, and by Fact A at or beyond it, hence on it. All contributions would have been summed and the offer would have been exact, against the choice of $d$. So at $\tau(d)$ every posting of $d$ is unpassed, and the movement about to happen passes one of them, so it starts at some $c \le d$ and its pivot exceeds $d$. By Fact B, $S(d) \le \theta$. By Fact A, every document accepted so far is smaller than the docID under the cursor that is about to move, which is at most $d$.
Suppose no posting of $d$ is ever skipped. Then $d$ is never offered: an offer of $d$ would find all its postings unpassed and, as just shown, would be exact. So no posting of $d$ is ever passed, and when the algorithm stops, every list that contains $d$ has its cursor at or before $d$ and is not exhausted. By Fact C, $S(d) \le \theta$ at the stop. By Fact A every accepted document is smaller than the docID under those cursors, hence smaller than $d$. Take the stop as $\tau(d)$.
Condition 2. Suppose an offer of $d$ with $\sigma$ is not exact. Some list containing $d$ did not contribute, so its cursor was not on $d$, and by Fact A it was beyond $d$: the posting of $d$ had been passed. It was not passed by step 3, which would have been an earlier offer of the same document, and offers strictly increase. So it was skipped, at a moment when, as shown under condition 3, $S(d) \le \theta$. The threshold has not decreased since, and $\sigma \le S(d)$ because contributions are not negative. So $\sigma \le \theta$ with a full heap, and the offer is not accepted. Every accepted offer is therefore exact. $\blacksquare$
The proof used four things: scores are sums of non-negative contributions, each $U_t$ is at least every contribution in its list, the threshold never decreases, and arithmetic is exact. The third worked problem removes the second, and then raises the threshold above the $k$-th score, to show the result changing.
The two methods side by side
On the running example WAND reads a third of what MaxScore reads. The two differ in what they take as the unit of decision.
MaxScore asks, of each list, whether its documents may still be candidates. The answer changes only when the threshold crosses a prefix sum, at most $m$ times in a query. Between those moments it does what plain document-at-a-time evaluation does on fewer lists, with an early exit. Its weakness is that every posting of an essential list is a candidate.
WAND asks, of each document, whether the lists that could still contain it have bounds enough. That test uses the cursor positions, so it can reject a document that an essential list of MaxScore would have proposed, as it rejected stories 1792 and 8079. Its cost is that the cursors must be ordered again after every movement.
Which is faster is an empirical matter that the published comparisons do not settle in WAND's favor. Tonellotto, Macdonald and Ounis (2018, section 3.3) summarize two of them. In the measurements of one production system MaxScore was faster than WAND throughout. In a research system on ClueWeb09 the two were close for queries of two to four terms, and WAND fell behind for longer queries. They also cite experiments in which MaxScore was always the more efficient. The pruning itself depends on the scoring function. Petri, Culpepper and Moffat (2013) measured WAND with a language-model score in place of BM25 and found that the large gains reported for BM25 were no longer achievable. One reading is that BM25's saturation keeps a term's largest contribution close to its typical one. The measurement below with the looser bound $(k_1 + 1)\,\mathrm{IDF}$ shows how much the tightness of the bound matters on Reuters.
For the size of the saving, the original papers are the source. Broder and his coauthors (2003) indexed the WT10G collection of the TREC Web Track and ran 50 of its topics. Against fully scoring every document that contains a query term, they report 92.6 percent fewer full evaluations for short queries and 95.2 percent fewer for long ones "without any loss in precision or recall" (section 1; their Table 1 has 10,120 against 136,225 and 15,992 against 335,500). Ding and Suel (2011, Table 2) measured, on the 25.2 million pages of TREC GOV2 with BM25 and $k = 10$, an average of 3,815,676 documents evaluated per query by exhaustive evaluation and 178,391 by WAND, under 5 percent.
Measured on Reuters-21578
The running example is one query. For a larger sample the queries are headlines. Each of 30 samples, drawn with seeds 0 to 29, takes the headlines of 50 Reuters stories chosen at random and uses each headline's distinct words as a query, keeping headlines with at least two. That gives 1,500 queries with a mean of 7.8 distinct terms. Nothing is removed from them. The index has no stop list, so words such as of and to are query terms with long postings lists and small upper bounds, the case in which MaxScore's non-essential lists save most. Exhaustive evaluation scores a mean of 11,530 postings and 6,705 stories per query, well over half the collection.
The measure is the number of postings scored: contributions $s_t(d)$ read and added. It does not depend on the machine or on the programming language. For each sample it is summed over the 50 queries and divided by the exhaustive count, and the table gives the median over the 30 samples with the quartiles in brackets. On every one of the 1,500 queries, for every $k$ and both methods, the script asserts that the result equals the exhaustive top $k$, document for document and score for score.
| $k$ | MaxScore | WAND |
|---|---|---|
| 1 | 3.6% [3.3, 3.9] | 2.1% [2.0, 2.3] |
| 10 | 11.7% [10.8, 12.3] | 9.7% [9.2, 10.2] |
| 100 | 27.8% [27.1, 28.5] | 28.8% [28.4, 29.6] |
| 1,000 | 71.8% [71.2, 72.6] | 72.8% [72.0, 73.3] |
For the ten best stories, both methods read about a tenth of the postings that exhaustive evaluation reads, and for the single best, a few percent. The saving shrinks as $k$ grows, because the threshold is the $k$-th best score and a larger $k$ means a lower bar. At $k = 1{,}000$, about one story in seven of those that match, nearly three quarters of the postings are read. The quartiles are narrow, so the figures depend little on which headlines were drawn.
WAND reads fewer postings than MaxScore for small $k$, and slightly more from $k = 100$ on. The two columns count the same thing but spend it differently, as a second count shows. It gives the number of stories for which at least one contribution was read, as a share of the stories exhaustive evaluation scores:
| $k$ | MaxScore | WAND |
|---|---|---|
| 1 | 4.5% [4.3, 4.9] | 0.9% [0.9, 1.0] |
| 10 | 13.5% [12.7, 14.5] | 5.0% [4.8, 5.3] |
| 100 | 28.0% [27.1, 28.6] | 19.1% [18.9, 20.1] |
| 1,000 | 69.3% [68.7, 70.7] | 63.3% [62.0, 64.9] |
WAND touches far fewer stories at every $k$: its pivot test rejects a story before anything of it is read. But a story that passes the test is scored in full, in every list whose cursor is on it. MaxScore touches every story that an essential list holds, reads the essential contributions, and often stops there. So MaxScore reads little from many stories and WAND reads everything from few, and by $k = 100$ the two totals have crossed.
By query length. Pooling the 1,500 queries at $k = 10$:
| Distinct terms | Queries | Postings per query, exhaustive | MaxScore | WAND |
|---|---|---|---|---|
| 2 to 5 | 69 | 3,802 | 16.8% | 12.2% |
| 6 or 7 | 600 | 8,559 | 12.1% | 9.7% |
| 8 or 9 | 691 | 13,234 | 11.5% | 9.8% |
| 10 or more | 140 | 19,659 | 11.0% | 9.4% |
Longer headlines have more postings to read and a slightly smaller share of them is read. The exhaustive cost grows fivefold from the first row to the last while the shares stay between 9 and 17 percent.
What the exact bound is worth. The course page compared two bounds on four sentences. On Reuters, replacing each list's largest contribution by the bound $(k_1 + 1)\,\mathrm{IDF}(t)$, which holds for any document and needs no pass over the list, changes the shares at $k = 10$ as follows:
| Bound $U_t$ | MaxScore | WAND |
|---|---|---|
| largest contribution in the list | 11.7% [10.8, 12.3] | 9.7% [9.2, 10.2] |
| $(k_1 + 1)\,\mathrm{IDF}(t)$ | 13.4% [12.4, 14.1] | 13.4% [12.8, 14.2] |
Both bounds are valid, so both return the exact top 10 on every query. The looser bound makes WAND read over a third more postings and removes its advantage over MaxScore. A looser bound never changes the answer. It only changes how much work is needed to be sure of it.
Postings scored are not seconds. The script is plain Python, and its timings say little about a compiled engine, but one of them is worth recording as a caution. In one run on a shared machine, exhaustive evaluation took about 22 milliseconds per query at $k = 10$, MaxScore about 9, and WAND about 30. WAND read a tenth of the postings and was slower than reading all of them. In this implementation each of its steps sorts the cursors and sums bounds, and the exhaustive loop does nothing but add. Counting postings measures the work a method avoids. It does not measure the bookkeeping the method adds, and on a collection of ten thousand documents the bookkeeping can cost more than it saves. Tonellotto, Macdonald and Ounis (2018, section 3.3) draw a similar conclusion from one of the comparisons they summarize, in which WAND did not reduce response times on the smaller of two indexes.
Measured on this site's index
The second test bed is the search engine of this site, described in How This Search Works. Its scores are BM25F scores over five fields, and the first question is whether a fielded score has per-term upper bounds at all.
It does, exactly. BM25F combines a term's frequencies in the fields into one pseudo-frequency before saturating. The contribution of a term to a page is therefore still a single number that depends only on the term and the page, and the page's score is the sum of those numbers over the query terms. The site already uses this. At startup it computes the contribution of every pair of a term and a page, rounds it to four decimals, and sends the table to the browser, which ranks instant results by adding (app/search.py, export). The upper bound of a term is the largest entry of its row in that table.
Two parts of the site's ranking are not sums over terms, and they are left out of the experiment.
- The title bonus. A page whose title contains every query term receives a bonus of 2.0 times the number of distinct query terms divided by the number of terms in the title. It depends on the whole query at once.
- The exact-title rule. Pages whose title consists of exactly the query terms are listed before all others, whatever their scores.
The experiment therefore prunes the BM25F sum and asserts the exact top $k$ of that sum. The bonus could be brought inside the proof, though this was not run. It is never more than 2.0, since a title that contains every query term has at least as many terms as the query. So replacing each test "bound at most $\theta$" by "bound plus 2.0 at most $\theta$" keeps condition 3 of the lemma true for the score with the bonus. The exact-title rule is a separate lookup of the few pages whose title is the query.
The index is built from the pages as they stood at commit 643484d, so that the numbers do not move as pages are added: 679 pages, 26,905 terms and 472,166 postings. The queries are the three sets the site keeps for evaluating its own search: 60 short queries made of article titles and names, 200 longer known-item queries that describe one page, and 60 topical questions. Each query's index terms are evaluated as a disjunction, as the site evaluates a plain query.
| Query set | Queries | Terms per query | Postings per query, exhaustive | MaxScore, $k = 10$ | WAND, $k = 10$ | MaxScore, $k = 1$ | WAND, $k = 1$ |
|---|---|---|---|---|---|---|---|
| title | 60 | 3.2 | 678 | 34.5% | 37.6% | 14.0% | 17.5% |
| known-item | 200 | 8.6 | 1,977 | 24.0% | 25.5% | 6.1% | 5.7% |
| topical | 60 | 6.0 | 1,991 | 19.0% | 24.0% | 7.0% | 10.2% |
The top $k$ equals the exhaustive one on all 320 queries. The savings are real and much smaller than on Reuters: at $k = 10$ about a fifth to over a third of the postings are still read, where Reuters needed a tenth. Two things about this index explain the direction. A query matches 582 of the 679 pages on average, because the pages are long and share a vocabulary, so there is little to skip to. And ten results out of 679 pages is a far larger share than ten out of 10,788 stories, so the threshold stays low for a larger part of each query. The observation of implementing BM25 on nested parts of Cranfield points the same way: the share of work that pruning saves grew each time the collection doubled.
What is proved here, what is cited, what the experiment shows
Proved on this page. The safety lemma; that MaxScore and WAND, as stated here, satisfy its conditions and therefore return exactly the top $k$ under the tie rule, with exact scores. The proofs assume exact arithmetic, non-negative contributions and true upper bounds.
Cited. That MaxScore is due to Turtle and Flood (1995) and WAND to Broder and his coauthors (2003); the form of both algorithms, which follows the survey of Tonellotto, Macdonald and Ounis (2018) and the description of WAND in Ding and Suel (2011). Broder and his coauthors' paper was read in an authors' copy. Of Turtle and Flood's paper only the bibliographic record was read. What is said about it is taken from the later sources: Broder and his coauthors (2003, section 1.1) write of the technique "termed max-score by Turtle and Flood", and credit the same paper with the terms safe and approximate optimization (section 1.2). Every speed and every saving on TREC collections is a result of the paper named.
Measured. The counts of postings scored, on Reuters-21578 with headline queries and on this site's index with its own evaluation queries. They are observations of these two small collections. The papers cited measured collections thousands of times larger, where a threshold has far more documents to rise on.
Worked problems
The course text does not present MaxScore or WAND, so the first problem is posed on three small constructed lists and the other two on the running example. The script recomputes every number.
Problem 1 (both algorithms by hand). Three lists have these postings, written docID: contribution, with whole-number contributions. List $a$: 2: 3, 5: 1, 9: 2. List $b$: 1: 2, 5: 2, 7: 1, 9: 2. List $c$: 3: 4, 5: 6, 8: 5. Find the top 1 with MaxScore and with WAND, and count the contributions each reads.
Solution. Both return document 5 with score 9. MaxScore reads 7 of the 10 contributions and WAND reads 6.
The upper bounds are $U_a = 3$, $U_b = 2$ and $U_c = 6$. For reference, the exhaustive scores are 2, 3, 4, 9, 1, 5 and 4 for documents 1, 2, 3, 5, 7, 8 and 9.
MaxScore. Sorted by bound the lists are $b$, $a$, $c$, with prefix sums $P_1 = 2$, $P_2 = 5$, $P_3 = 11$.
| Candidate | Essential lists | Contributions read | Outcome | $\theta$ after |
|---|---|---|---|---|
| 1 | $b$, $a$, $c$ | $b$: 2 | score 2, enters | 2 |
| 2 | $a$, $c$ | $a$: 3 | $3 + P_1 = 5 > 2$, so $b$ is consulted (cursor to 5, nothing); score 3, enters | 3 |
| 3 | $a$, $c$ | $c$: 4 | $4 + 2 > 3$, $b$ consulted (still on 5); score 4, enters | 4 |
| 5 | $a$, $c$ | $a$: 1, $c$: 6, $b$: 2 | $7 + 2 > 4$, $b$ consulted and found; score 9, enters | 9 |
| 8 | $c$ | $c$: 5 | $5 + P_2 = 10 > 9$, so $a$ is consulted (cursor to 9, nothing); $5 + P_1 = 7 \le 9$: abandoned | 9 |
After document 1, $\theta = 2 \ge P_1$, so $b$ is non-essential. After document 5, $\theta = 9 \ge P_2 = 5$, so $a$ is too. List $c$ is then exhausted and the algorithm stops. Documents 7 and 9 were never candidates: they contain only $a$ and $b$, and $U_a + U_b = 5 \le 9$. Seven contributions were read.
WAND. Cursors are written in the order $a$, $b$, $c$.
| Step | Cursors $a$, $b$, $c$ | Sums of bounds in cursor order | Pivot | Action |
|---|---|---|---|---|
| 1 | 2, 1, 3 | $b$: 2 | 1 | score 2; $\theta = 2$ |
| 2 | 2, 5, 3 | $a$: 3 | 2 | score 3; $\theta = 3$ |
| 3 | 5, 5, 3 | $c$: 6 | 3 | score 4; $\theta = 4$ |
| 4 | 5, 5, 5 | $a$: 3, then $a + b$: 5 | 5 | all three cursors are on 5: score $1 + 2 + 6 = 9$; $\theta = 9$ |
| 5 | 9, 7, 8 | $b$: 2, $b + c$: 8, $b + c + a$: 11 | 9 | $b$ and $c$ are below the pivot; move $c$ to 9: exhausted |
| 6 | 9, 7, end | $b$: 2, $b + a$: 5 | none | stop |
Six contributions were read. At step 5 the pivot is document 9, so documents 7 and 8 are known to be out before anything of theirs is read: document 8 could draw only on $b$ and $c$, whose bounds sum to 8. MaxScore read $c$'s contribution to document 8 before abandoning it, which is the one contribution of difference.
Problem 2 (the effect of $k$). Run both algorithms on the running example with $k = 1$ and $k = 3$, and compare with $k = 2$.
Solution.
The same stories are returned as by exhaustive evaluation in each case, and the counts are:
| $k$ | Final $\theta$ | MaxScore: postings scored | WAND: postings scored |
|---|---|---|---|
| 1 | 31.3290 | 39 | 12 |
| 2 | 31.2542 | 39 | 13 |
| 3 | 22.5972 | 40 | 19 |
For $k = 1$ and $k = 2$ the final thresholds differ by 0.0748 and both lie between $P_3 = 27.8496$ and $P_4 = 39.6865$, so MaxScore ends with the same two essential lists and reads the same 39 contributions. WAND reads one fewer with $k = 1$, and the one it saves shows the tie rule at work. After story 351 the single best score is 10.6555, which is bullion's upper bound, reached in that very story. When bullion's next posting, story 983, comes up alone, its bound equals $\theta$ and does not exceed it, so the story is skipped. With $k = 2$ the threshold at that point was 6.7243 and the story was scored and rejected.
With $k = 3$ the third story, 8079, scores 22.5972, and that is the final threshold. It lies below $P_3$, so palladium stays essential for MaxScore to the end as well. It also lies below the sum of the bounds of palladium and platinum, 23.4630, so WAND can no longer jump over stories that contain both. WAND reads 19 contributions, half as many again as with $k = 2$. Lowering the bar from 31.2542 to 22.5972 costs WAND six contributions and MaxScore one. On this query a good part of WAND's advantage at $k = 2$ comes from the gap between the second and third scores.
Problem 3 (two ways to lose safety). (a) Suppose the dictionary stored 6.0000 as the upper bound of platinum in place of the true 11.8369. What does WAND return for the running example with $k = 3$? (b) Broder and his coauthors (2003, sections 2.3 and 2.5) let the threshold used for pruning be raised above the $k$-th best score to save more work: they pass the pruning step $F$ times the smallest score in the heap, for a "threshold factor" $F$. Run WAND with $k = 3$ and the pivot test $U_{(1)} + \dots + U_{(p)} > 1.5\,\theta$.
Solution. In both cases WAND returns stories 1521 and 1467 and then story 1792, with 17.8125, in place of story 8079, with 22.5972. It reads 15 contributions where the safe run reads 19.
(a) The first two stories are found as before. The third place is then held by story 1792, scored at 17.8125, so $\theta = 17.8125$. Story 8079 contains palladium and platinum, and the algorithm believes those two can give at most $11.6261 + 6.0000 = 17.6261$, which is not above $\theta$. The pivot never rests on story 8079 with enough bounds behind it, and platinum's cursor jumps over it. In truth platinum gives that story 11.7725, almost twice the false bound. Fact B of the proof fails at exactly this point: the sum of the bounds of the lists before the pivot no longer limits what those lists can contribute. The wrong answer comes with no warning. The run is shorter, and the heap looks like any other.
(b) With the correct bounds and the test against $1.5\,\theta$, the same thing happens for a different reason. At $\theta = 17.8125$ the test asks for bounds above 26.7188, and the two lists that hold story 8079 offer 23.4630. The story's score, 22.5972, is above the true threshold and below the inflated one. This is the setting that computing vector scores and search at scale describe as the one deliberate trade of accuracy for speed: Tonellotto, Macdonald and Ounis (2018, section 3.3) write the factor as $F > 1$ and call such versions aggressive. The first two results are unaffected here, because they score far above anything the inflated test could reject. In terms of the lemma, a document is now dismissed at a moment when $S(d) \le 1.5\,\theta$, and condition 3 needs $S(d) \le \theta$.
What we have learned
A ranked query can be answered exactly without reading every posting when scores are sums of bounded term contributions. The threshold $\theta$, the $k$-th best score so far, is the bar. Any document whose score is known to be at most $\theta$ can be left out, provided documents are visited in docID order and ties go to the smaller docID. That is the safety lemma, and both classical algorithms were checked against it. MaxScore stops the lists with the smallest bounds from proposing candidates. WAND finds, from the cursor positions, the first docID whose possible score exceeds the threshold. On five Reuters lists and $k = 2$ they read 39 and 13 of 53 contributions. On 1,500 headline queries and $k = 10$ they read 11.7 and 9.7 percent of what exhaustive evaluation reads, and on this site's 679 pages about a fifth to over a third.
Both methods judge a list by one number, its largest contribution anywhere. For platinum that number, 11.8369, is reached in one story of nineteen, and six of its postings contribute less than 6. The next article, Block-Max Indexes, stores a bound for each block of a list, and shows what must change in WAND for the proof to survive.
References
- Broder, A. Z., Carmel, D., Herscovici, M., Soffer, A., and Zien, J. (2003). Efficient query evaluation using a two-level retrieval process. In Proceedings of CIKM 2003, 426–434. record · 3 pages
- Ding, S., and Suel, T. (2011). Faster top-k document retrieval using block-max indexes. In Proceedings of SIGIR 2011, 993–1002. record · 3 pages
- Petri, M., Culpepper, J. S., and Moffat, A. (2013). Exploring the magic of WAND. In Proceedings of the 18th Australasian Document Computing Symposium (ADCS 2013), 58–65. record
- Tonellotto, N., Macdonald, C., and Ounis, I. (2018). Efficient query processing for scalable web search. Foundations and Trends in Information Retrieval, 12(4–5), 319–500. record · 4 pages
- Turtle, H., and Flood, J. (1995). Query evaluation: Strategies and optimizations. Information Processing and Management, 31(6), 831–850. record · 2 pages