When a search query matches millions of documents, scoring and ranking every single match is prohibitively expensive. If you only need the top-k results (say, the top 10), most of those millions of documents will never appear in the final result set. The Weak AND (WAND) algorithm exploits this insight: it uses upper-bound score estimates to skip entire sections of posting lists that cannot possibly produce a top-k result, reducing query latency by orders of magnitude without sacrificing result quality.
WAND works by maintaining a threshold—the score of the k-th best document seen so far. For each candidate document, it computes an upper bound on that document’s score by summing the maximum possible contribution from each query term. If this upper bound is below the threshold, the document is skipped without ever computing its actual score. The algorithm advances posting list cursors in sorted order, pivoting past large blocks of documents that cannot beat the threshold.
Block-Max WAND (BMW) extends this idea by storing per-block maximum scores in the index. Instead of using a single global upper bound per term (the maximum score that term contributes to any document), BMW knows the maximum score within each block of 64–256 postings. This tighter bound allows skipping far more documents. In practice, BMW is used as the primary query evaluation strategy for BM25-scored full-text queries in production search engines, delivering sub-millisecond top-k retrieval over indexes with tens of millions of documents.
Full-text search with BM25 scoring produces a score for every document that contains at least one query term. For a two-word query on a large index, this could be millions of documents. But the user only sees the top 10. Computing the exact score for every match (the “exhaustive” approach) wastes 99.99% of its work. WAND and BMW are “safe” optimizations—they produce the exact same top-k results as exhaustive evaluation, just faster.
Every term in a BM25 index has a maximum possible score contribution, determined by its inverse document frequency (IDF) and the scoring formula’s saturation function. If a document contains term t, the most it can contribute to the document’s score is max_score(t). By summing upper bounds across all query terms, we get an upper bound on any document’s total score. If this upper bound is below our current top-k threshold, the document cannot enter the result set.
An inverted index stores, for each term, a sorted list of document IDs (postings) that contain that term. A cursor iterates over a posting list and supports two operations: next() to advance to the next posting, and advance(target) to skip forward to the first posting with doc ID ≥ target. The advance operation is the key to WAND’s efficiency—it skips past large ranges of documents in O(log n) time using skip lists or block-based indexing.
WAND sorts query terms by their current cursor position (the doc ID each cursor is pointing at). It finds the “pivot”—the leftmost term whose cumulative upper-bound score (plus all terms to its left) exceeds the threshold. If all cursors to the left of the pivot point to the same document, that document is a candidate worth scoring. If not, WAND advances the leftmost cursor past the pivot document, skipping a potentially large range of documents.
Standard WAND uses a single upper-bound score per term (the global maximum). This is loose—a rare term might have max_score = 15.0 but its score in 99% of documents is below 5.0. Block-Max WAND divides each posting list into fixed-size blocks (e.g., 128 postings) and stores the maximum score within each block. When evaluating a candidate, BMW uses the block-level max score instead of the global max, producing much tighter bounds and skipping more documents.
A posting list block stores the maximum BM25 contribution of any document in that block. When WAND checks whether a document could beat the threshold, it uses the block max score instead of the global max. If the document falls in a block where the max score is low, WAND can skip the entire block. This converts a loose O(N) scan into tight block-level skipping that often evaluates only 1–5% of the total postings.
WAND and BMW are scoring-function-agnostic in principle, but they’re most commonly paired with BM25. For a query Q with terms t1…tn and a document D:
BM25(D, Q) = sum over each query term t:
IDF(t) * (tf(t,D) * (k1 + 1)) / (tf(t,D) + k1 * (1 - b + b * |D|/avgdl))
where:
tf(t,D) = term frequency of t in document D
|D| = document length
avgdl = average document length
k1 = 1.2 (saturation parameter)
b = 0.75 (length normalization parameter)
IDF(t) = log((N - df(t) + 0.5) / (df(t) + 0.5) + 1)WAND requires that the scoring function be decomposable: the total document score must equal the sum of independent per-term contributions. BM25 satisfies this because each term’s contribution depends only on that term’s frequency in the document, not on other terms. Non-decomposable scoring functions (like those using term proximity) require modified WAND variants.
The core WAND algorithm processes query terms sorted by their current doc ID cursor:
// Pseudocode for the WAND top-k algorithm
function WAND(query_terms, k):
heap = MinHeap(capacity=k) // top-k results, min-heap by score
threshold = 0 // score of k-th best document
// Each term has: cursor (current doc ID), max_score (upper bound)
while all cursors not exhausted:
// Sort terms by current cursor doc ID
sort terms by cursor.doc_id ascending
// Find pivot: first term where cumulative max_score > threshold
cumulative = 0
pivot_idx = -1
for i in 0..len(terms):
cumulative += terms[i].max_score
if cumulative > threshold:
pivot_idx = i
break
if pivot_idx == -1:
break // no document can beat threshold
pivot_doc = terms[pivot_idx].cursor.doc_id
// Check if all terms before pivot point to the same document
if terms[0].cursor.doc_id == pivot_doc:
// All terms up to pivot share this doc ID - score it
score = compute_exact_score(pivot_doc, query_terms)
if score > threshold:
heap.push(pivot_doc, score)
if heap.size > k:
heap.pop()
threshold = heap.min_score()
// Advance all cursors past pivot_doc
for each term where cursor.doc_id == pivot_doc:
term.cursor.next()
else:
// Skip: advance the leftmost cursor to pivot_doc
terms[0].cursor.advance(pivot_doc)BMW modifies the upper-bound calculation to use block-level max scores. Each posting list cursor tracks which block it’s currently in and exposes a block_max_score() method:
// Pseudocode for Block-Max WAND
function BMW(query_terms, k):
heap = MinHeap(capacity=k)
threshold = 0
while all cursors not exhausted:
sort terms by cursor.doc_id ascending
// Find pivot using BLOCK-LEVEL max scores (tighter bounds)
cumulative = 0
pivot_idx = -1
for i in 0..len(terms):
cumulative += terms[i].cursor.block_max_score()
if cumulative > threshold:
pivot_idx = i
break
if pivot_idx == -1:
break
pivot_doc = terms[pivot_idx].cursor.doc_id
if terms[0].cursor.doc_id == pivot_doc:
// Before scoring, check block-level bound for THIS specific doc
upper_bound = sum(t.cursor.block_max_score() for t in terms
if t.cursor.doc_id <= pivot_doc)
if upper_bound > threshold:
score = compute_exact_score(pivot_doc, query_terms)
if score > threshold:
heap.push(pivot_doc, score)
if heap.size > k: heap.pop()
threshold = heap.min_score()
for each term where cursor.doc_id == pivot_doc:
term.cursor.next()
else:
// Skip to pivot, but also consider skipping entire blocks
next_block_boundary = terms[0].cursor.next_block_start()
skip_to = max(pivot_doc, next_block_boundary)
terms[0].cursor.advance(skip_to)At index time, posting lists are divided into fixed-size blocks. For each block, the maximum BM25 score contribution is precomputed and stored alongside the postings:
const BLOCK_SIZE: usize = 128;
pub const PostingBlock = struct {
doc_ids: [BLOCK_SIZE]u32, // sorted document IDs in this block
freqs: [BLOCK_SIZE]u16, // term frequencies
max_score: f32, // max BM25 contribution in this block
count: u16, // number of valid entries (may be < BLOCK_SIZE for last block)
};
/// Compute the block max score given BM25 parameters.
pub fn computeBlockMaxScore(
block: *const PostingBlock,
idf: f32,
avgdl: f32,
k1: f32,
b: f32,
doc_lengths: []const u32,
) f32 {
var max: f32 = 0;
var i: u16 = 0;
while (i < block.count) : (i += 1) {
const tf: f32 = @floatFromInt(block.freqs[i]);
const dl: f32 = @floatFromInt(doc_lengths[block.doc_ids[i]]);
const norm = k1 * (1.0 - b + b * dl / avgdl);
const score = idf * (tf * (k1 + 1.0)) / (tf + norm);
if (score > max) max = score;
}
return max;
}The advance(target) operation is implemented using skip lists or binary search within blocks. A posting list cursor in Go:
package search
// PostingCursor iterates over a term's posting list with skip support.
type PostingCursor struct {
blocks []PostingBlock
blockIdx int
innerIdx int
maxScore float32 // global max score for this term
}
// DocID returns the current document ID.
func (c *PostingCursor) DocID() uint32 {
return c.blocks[c.blockIdx].DocIDs[c.innerIdx]
}
// BlockMaxScore returns the max score for the current block.
func (c *PostingCursor) BlockMaxScore() float32 {
return c.blocks[c.blockIdx].MaxScore
}
// Advance moves the cursor to the first doc ID >= target.
func (c *PostingCursor) Advance(target uint32) bool {
// Skip entire blocks whose last doc ID is below target
for c.blockIdx < len(c.blocks) {
blk := &c.blocks[c.blockIdx]
lastDocInBlock := blk.DocIDs[blk.Count-1]
if lastDocInBlock >= target {
break
}
c.blockIdx++
}
if c.blockIdx >= len(c.blocks) {
return false // exhausted
}
// Binary search within the current block
blk := &c.blocks[c.blockIdx]
lo, hi := 0, int(blk.Count)
for lo < hi {
mid := (lo + hi) / 2
if blk.DocIDs[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
c.innerIdx = lo
return lo < int(blk.Count)
}
// Next advances to the next posting.
func (c *PostingCursor) Next() bool {
c.innerIdx++
if c.innerIdx >= int(c.blocks[c.blockIdx].Count) {
c.blockIdx++
c.innerIdx = 0
}
return c.blockIdx < len(c.blocks)
}A production search engine using Block-Max WAND as its primary query evaluation strategy works as follows: when a BM25 query arrives, the engine opens cursors on the posting lists for each query term, initializes the BMW loop, and retrieves the top-k results. For a typical 3-term query over a 10-million document index, BMW evaluates only 50,000–200,000 postings instead of the 2–5 million that exhaustive evaluation would touch. This translates to query latencies under 5ms at p99.
When searching across multiple fields (title, body, tags), each field has its own posting lists and BM25 parameters. BMW treats each (term, field) pair as a separate “virtual term” with its own cursor and max score. The pivot logic works identically—it just has more cursors to manage. Field boosting is incorporated by multiplying each field’s max score by its boost factor.
Modern search systems combine BM25 text scoring with vector similarity (dense retrieval). BMW retrieves the top-k BM25 candidates efficiently, and a second pass re-ranks them using vector similarity or a learned cross-encoder. This two-stage architecture leverages BMW’s speed for the broad retrieval phase and reserves expensive neural scoring for the narrow re-ranking phase.
When new documents are added to the index, their postings are initially stored in a small in-memory segment without block-max metadata. Queries over this segment use standard WAND (with global max scores). During segment merges, block-max scores are computed for the merged blocks. This allows real-time indexing without blocking queries while still benefiting from BMW on the bulk of the index.
BMW’s effectiveness depends on having a good threshold early. Starting with threshold = 0 means the first k documents are always scored. Two techniques improve early threshold quality:
Block size is a trade-off between bound tightness and metadata overhead:
When the same query is repeated (common in production), caching the top-k results avoids re-running BMW entirely. For queries that differ by one term, partial results from cached sub-queries can warm the threshold:
package search
import "sync"
// ScoreCache caches top-k results for recent queries.
type ScoreCache struct {
mu sync.RWMutex
cache map[string][]ScoredDoc // query string -> top-k results
}
type ScoredDoc struct {
DocID uint32
Score float32
}
func (sc *ScoreCache) Get(query string) ([]ScoredDoc, bool) {
sc.mu.RLock()
defer sc.mu.RUnlock()
results, ok := sc.cache[query]
return results, ok
}
func (sc *ScoreCache) Put(query string, results []ScoredDoc) {
sc.mu.Lock()
defer sc.mu.Unlock()
sc.cache[query] = results
}For very large indexes partitioned across multiple shards, BMW runs independently on each shard. A coordinator merges the per-shard top-k results into a global top-k. Each shard can also communicate its threshold to other shards mid-query, allowing lagging shards to skip more aggressively:
package search
import "sync"
// ParallelBMW runs Block-Max WAND across multiple index shards in parallel.
func ParallelBMW(shards []*IndexShard, query []string, k int) []ScoredDoc {
var wg sync.WaitGroup
results := make([][]ScoredDoc, len(shards))
for i, shard := range shards {
wg.Add(1)
go func(idx int, s *IndexShard) {
defer wg.Done()
results[idx] = s.BMW(query, k)
}(i, shard)
}
wg.Wait()
// Merge per-shard results into global top-k
return mergeTopK(results, k)
}When documents are deleted or updated, block-max scores may become stale (the document that produced the max score no longer exists). This doesn’t affect correctness— the bound is still an upper bound—but it reduces skipping efficiency. Periodic segment merges recompute accurate block-max scores.
A query like the xylophone has one extremely common term and one rare term. The rare term’s high IDF creates a high max score, making the threshold hard to reach. WAND degrades toward exhaustive evaluation because few documents can be skipped. The fix is stopword removal at query time (remove “the”) or term-at-a-time evaluation for common terms.
WAND requires that score(D, Q) = sum(score(D, t) for t in Q). Scoring functions that incorporate term proximity, phrase matching, or cross-term features violate this property. Workarounds include: using WAND for initial retrieval with a decomposable scorer, then re-ranking candidates with the full scoring function.
If the precomputed max score for a term is lower than the actual maximum, WAND may skip documents that should be in the top-k—producing incorrect results. This is a correctness bug, not just a performance issue. Always compute max scores conservatively and verify them against exhaustive evaluation during testing.
WAND’s bookkeeping (sorting cursors, computing upper bounds, pivot selection) has overhead. For single-term queries or very small indexes (<100K documents), exhaustive evaluation can be faster because the overhead exceeds the savings from skipping. Use exhaustive evaluation for single-term queries and WAND/BMW only for multi-term queries.
Storing a 4-byte float per block adds 4 * (N / block_size) bytes of overhead per term. For an index with 1 billion postings across all terms and block size 128, this is ~31MB—modest. But for very wide indexes (millions of unique terms), the metadata can consume significant memory. Consider memory-mapping the block-max data rather than loading it entirely into RAM.