Search & IR · advanced
Top-k Pruning (WAND)
WAND, MaxScore, and block-max — skipping documents that cannot reach the top k.
Mental model
Scoring every posting is wasted work when you only need the top k: once the heap holds k results, any document whose best possible score cannot exceed the current threshold can be skipped without computing it. WAND does this by keeping a per-term upper bound and advancing pointers past documents whose summed bounds fall short; block-max sharpens it by storing a maximum per block rather than per term, so the bound is tight enough to skip far more. This is safe pruning — the top k is identical to the exhaustive answer, only faster.
How to study Top-k Pruning (WAND)
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Top-k Pruning (WAND) with Inverted Index, Reranking. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Skip documents that cannot reach the top k and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
The reason Lucene and Tantivy answer top-10 queries over billions of postings in milliseconds.
Common mistakes
- Confusing safe pruning with approximate retrieval; WAND returns exactly the same top k
- Using a global per-term upper bound when block-level maxima would prune an order of magnitude more
- Assuming pruning helps for a query needing deep result sets — the win shrinks as k grows
- Forgetting the threshold only rises once the heap is full, so early postings are still scored
Learn from primary sources
Use the linked roadmap context and practice prompt.
Practice and explain it back
Skip documents that cannot reach the top k
Implement prune(docs, upperBounds, k) where docs is [{id, terms:[termName], score}] and upperBounds maps term -> max possible contribution. Walk docs in order maintaining a top-k heap; BEFORE scoring a document, skip it when the sum of its terms' upper bounds is <= the current k-th best score. Return { top: ids of the top k by score descending, scored: how many documents you actually scored }.
Expected evidence: Pruning must not change the top k — only how many documents were scored.
Open the interactive drill →Review prompts
- WAND skips documents without scoring them. Why is the returned top-k still exactly the same as an exhaustive scan, and when does the technique stop paying off?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.