Company logo
Previous
Next

What is Block WAND?

Block-Max WAND (BMW) is a dynamic pruning algorithm that accelerates Top K document retrieval in search engines, the kind of query you express in SQL as ORDER BY score DESC LIMIT k. It works with scoring functions like BM25 by dividing inverted index posting lists into fixed-size blocks, precomputing the maximum possible score within each block, and using those scores to skip entire blocks of documents that cannot appear in the final results. In most implementations, the algorithm returns exactly the same results as exhaustive scoring while doing a fraction of the work.

The technique was introduced by Shuai Ding and Torsten Suel in 2011 and has since been adopted by Apache Lucene, Tantivy, and other search engines as a core query optimization.

From WAND to Block WAND

Block WAND builds on two earlier pruning techniques:

  • MaxScore (Turtle & Flood, 1995) stores a single global maximum score per term across the entire posting list. It uses this to classify terms as "essential" or "non-essential" and skip documents that cannot beat the current threshold.
  • WAND (Broder et al., 2003) introduces a pivot mechanism that sorts term pointers by document ID and calculates whether the combined upper-bound scores of aligned terms can exceed the threshold. If not, it advances past those documents without scoring them.

Both techniques rely on a single global upper bound per term: the highest score that term produces across the entire index. This bound can be inflated by a single outlier document, making it loose and limiting how aggressively documents can be skipped.

Block WAND is not a different algorithm; it is WAND with finer-grained upper bounds. Instead of one maximum score for a posting list of millions of documents, it records the maximum score for each block of typically 128 documents. These tighter bounds plug directly into WAND's existing pivot mechanism, allowing far more aggressive pruning.

How Block WAND Works

Index Structure

During indexing, each posting list is divided into fixed-size blocks. For each block, the index stores:

  • The block-max score: the highest score any document in this block can contribute for this term
  • The maximum document ID in the block

These values are stored alongside the compressed posting data with minimal overhead, typically 5-8% additional index size.

Query Processing

When you execute a query for the Top K results, the algorithm maintains a result heap and a dynamic threshold: the minimum score needed to enter the current Top K. Processing follows these steps:

  1. Sort term pointers by their current document ID, smallest first.
  2. Find the pivot document. Walk through the sorted pointers, accumulating block-max scores until their sum exceeds the threshold. The document where the sum first crosses the threshold is the pivot, the earliest document that could possibly score high enough to enter the Top K.
  3. Check block bounds: for each term's posting list, look up the block-max score for the block containing the pivot document. If a term's block-max is too low to help the pivot exceed the threshold, skip that term's iterator ahead to its next block. Different terms may skip different blocks.
  4. Score the document: if the combined block-max bounds survive the check, fully score the pivot document. If it exceeds the threshold, insert it into the Top K heap and raise the threshold.
  5. Repeat until all posting lists are exhausted.

As higher-scoring documents are found, the threshold rises, and pruning becomes more aggressive; the algorithm accelerates as it runs.

Why Per-Block Bounds Matter

Consider a common term like "the" with a posting list spanning millions of documents. Its global maximum score might be 3.5 (from one short document where "the" appears disproportionately often). In most blocks of 128 documents, the actual maximum contribution is much lower, perhaps 0.8. Using 0.8 instead of 3.5 as the upper bound allows the algorithm to skip far more blocks.

This effect compounds across multiple query terms. When every term has a tighter bound, the combined upper-bound estimate drops substantially, and entire regions of the index are eliminated without decompressing a single document ID.

Example: Block WAND in Action

Suppose you search for "machine learning" and want the top 10 results. The index has separate posting lists for each term, and each posting list is divided into blocks. The algorithm walks both lists in parallel, checking whether each block pair can produce a combined score above the current threshold.

threshold = 0.0

Block 1 (docs 1–128):
  "machine" block-max = 4.1, "learning" block-max = 3.8, sum = 7.9
  -> sum > threshold, score documents
  -> threshold rises to 5.3

Block 2 (docs 129–256):
  "machine" block-max = 1.2, "learning" block-max = 2.4, sum = 3.6
  -> sum < threshold (3.6 < 5.3), skip entire block

Block 3 (docs 257–384):
  "machine" block-max = 3.9, "learning" block-max = 4.5, sum = 8.4
  -> sum > threshold, score documents
  -> threshold rises to 6.8

Block 4 (docs 385–512):
  "machine" block-max = 0.9, "learning" block-max = 1.8, sum = 2.7
  -> sum < threshold (2.7 < 6.8), skip entire block

Notice that each term has its own block-max score, and the algorithm sums them to decide whether a block is worth scoring. As the threshold rises, more blocks are pruned.

Performance

Benchmarks across academic and industry implementations show consistent results:

  • 3x to 7x speedup on standard term queries compared to exhaustive scoring (Grand et al., ECIR 2020)
  • In practice, Block WAND typically scores only 10-40% of matching documents, with the rest pruned at the block level
  • Greatest impact on disjunctive (OR) queries with high-frequency terms, where the most documents can be skipped
  • Benefits scale with collection size; larger indexes see proportionally more pruning

The algorithm only applies to Top K queries by score, not exhaustive counts or Top K on fast fields, since it relies on a threshold from the result heap to make pruning decisions. The speedup is greatest when queries contain common terms with long posting lists, where most blocks can be skipped.

Scoring Constraints

Block WAND's pruning is safe only when the scoring function is additive across terms and each term's contribution is non-negative. This holds for BM25, TF-IDF, and most classical retrieval functions. Scoring models that produce negative term contributions or non-additive scores (such as some neural rerankers) cannot use Block WAND for safe pruning, since a negative contribution could make a skipped document score higher than the upper bound suggests.

Adoption in Search Engines

  • Apache Lucene 8.0 (2019) adopted Block WAND for Top K disjunctive queries, bringing the optimization to Elasticsearch and Solr
  • Tantivy implements Block WAND for boolean queries with should clauses, inherited by Quickwit and ParadeDB. Tantivy's block-max values are not always exact: in rare cases a block-max may underestimate the true maximum, which can cause a marginally lower-scoring document to be returned instead of the true top result

Summary

Block WAND accelerates Top K retrieval by replacing loose global score bounds with tight per-block bounds, allowing the search engine to skip large portions of the index without sacrificing result quality. It processes the same query with a fraction of the scoring work, and the speedup grows as the threshold tightens during execution. For search engines handling disjunctive queries over large collections, it is one of the most effective optimizations available.

Previous
Next