Dynamic Pruning with WAND and Block-Max

A query for three moderately common terms may match two million documents. The user wants ten. Scoring all two million to find the top ten is what a naive implementation does, and dynamic pruning is the family of techniques that gets the exact same ten while scoring a small fraction of them.

The key enabling property is that BM25 and similar scoring functions have a bounded per-term contribution, because term frequency saturates. For each term \(t\), precompute \(\sigma_t\), the maximum score any document can receive from that term. Then any document's score is at most the sum of \(\sigma_t\) over the query terms it contains.

WAND

Maintain a heap of the current top \(k\) candidates, with threshold \(\theta\) equal to the \(k\)-th best score so far. Sort the query terms' postings lists by their current document ID. Walk down the sorted terms accumulating \(\sigma_t\) until the running sum exceeds \(\theta\); the term at which that happens is the pivot.

No document before the pivot's current document ID can possibly reach \(\theta\), because even matching every term up to that point sums to less than the threshold. So all preceding lists skip forward to the pivot document. If every list is aligned there, score it fully and possibly update the heap; otherwise advance and repeat (Broder et al., 2003, Efficient Query Evaluation Using a Two-Level Retrieval Process, CIKM).

The result is exact, which is the property that matters. This is not an approximation that trades recall for speed; the returned top \(k\) is identical to exhaustive scoring, and the only thing lost is the scores of documents outside it.

Block-Max: why the global bound is too loose

WAND's weakness is that \(\sigma_t\) is a single global maximum over the whole postings list. One document containing a term forty times sets a high bound that applies to every region of the list, including long stretches where the term appears once.

Block-Max WAND stores a per-block maximum alongside each compressed block of postings, typically 64 or 128 entries (Ding and Suel, 2011, Faster Top-k Document Retrieval Using Block-Max Indexes, SIGIR). The bound used at any point is then local to the current block, which is much tighter, and whole blocks can be skipped without decompressing them. Since decompression is a large share of query cost, skipping a block avoids both the scoring and the decode.

The refinement composes with the compression layer: block-max requires block-structured postings, which is what modern codecs use anyway, so the extra storage is one float per block.

When it breaks

The threshold starts at zero. Early in query processing \(\theta\) is low, so almost nothing prunes and the algorithm degenerates to exhaustive scanning until the heap fills with reasonable candidates. Seeding \(\theta\) from a static quality score, or processing high-impact blocks first, addresses this and introduces its own complexity.

Large \(k\) destroys the benefit. Pruning power comes from a high threshold, and the \(k\)-th best score falls as \(k\) grows. Retrieving the top 1,000 candidates for a reranker prunes far less than retrieving the top 10, which is a real cost of the retrieve-then-rerank architecture that pipeline diagrams never show.

Long queries weaken the bound. With many terms the sum of maxima is large, so the pivot sits late in the term ordering and few lists skip. Query-length-dependent latency is a direct consequence.

Learned sparse retrieval breaks the assumptions. SPLADE-style models produce query vectors with many more non-zero terms than a keyword query and weight distributions unlike BM25's, so pruning is much less effective and query latency rises substantially relative to BM25 on the same index. This is an active area, and it is the reason learned sparse retrieval's efficiency story is more complicated than "it uses an inverted index, so it is fast".

Approximate variants exist and change the guarantee. Multiplying the threshold by a factor above 1 prunes far more aggressively and no longer returns the exact top \(k\). That is often an acceptable trade, but it should be a stated choice rather than a default nobody noticed.