Top-k pruning with score upper bounds

Deep dive

How it works

Parts:

• Posting list per term — ascending docids with an integer score each, in blocks of B ids with skip data (Sorted-list intersection, Inverted index).
• List maximum and block maxima — largest score per list and per block; the block value sits beside the block's last docid, readable without decoding.
• Cursors — one per query term: doc() and next_geq(d).
• Top-k heap — min-heap of the best k; its minimum is the threshold θ (0 until full).

Operations, repeated until no pivot exists:

1. Sort the cursors by current docid.
2. Add list maxima in that order until the sum exceeds θ. That cursor is the pivot, its docid pd the first candidate: no smaller id can beat θ. None: stop.
3. (Block-Max) Shallow move: sum the maxima of the blocks holding pd in the cursors up to the pivot. At most θ: move one cursor to min(block ends + 1, next cursor's docid), go to 1.
4. First cursor at pd: score pd (sum the scores of all cursors there), push to the heap, advance them. Otherwise move one earlier cursor to next_geq(pd). Go to 1.

θ = 15            list_max   running sum
 t3  doc  12          4          4
 t1  doc  40          7         11
 t2  doc  95  <- pivot 9        20 > 15      docs 12..94 cannot reach 15
 t4  doc 300          5         25
shallow: blocks around 95 have maxima 2 + 3 + 7 = 12 <= 15
  -> skip to min(block ends + 1, 300); no posting block is decoded

MaxScore (Turtle and Flood, 1995) splits lists by maximum: essential lists (maxima sum above θ) generate candidates; non-essential lists are only probed per candidate. WAND (Broder et al., CIKM 2003) re-derives the pivot each step. Block-Max WAND (Ding and Suel, SIGIR 2011) adds step 3. Comparing against θ·F, F > 1, is unsafe pruning: faster, may lose true top-k hits.

Code

use std::{cmp::Reverse, collections::BinaryHeap};
const B: usize = 64; // postings per block
const END: u32 = u32::MAX;
pub struct List { docs: Vec<u32>, sc: Vec<u32>, bmax: Vec<u32>, blast: Vec<u32>, lmax: u32 }
impl List {
    pub fn new(docs: Vec<u32>, sc: Vec<u32>) -> List {
        let bmax = sc.chunks(B).map(|c| *c.iter().max().unwrap()).collect();
        let blast = docs.chunks(B).map(|c| *c.last().unwrap()).collect();
        let lmax = *sc.iter().max().unwrap();
        List { docs, sc, bmax, blast, lmax }
    }
    /// (max score, last docid) of the block holding the first docid >= d; reads no postings.
    fn shallow(&self, d: u32) -> (u32, u32) {
        let b = self.blast.partition_point(|&x| x < d);
        if b == self.blast.len() { (0, END) } else { (self.bmax[b], self.blast[b]) }
    }
}
struct Cur<'a> { l: &'a List, i: usize }
impl Cur<'_> {
    fn doc(&self) -> u32 { self.l.docs.get(self.i).copied().unwrap_or(END) }
    fn next_geq(&mut self, d: u32) { self.i += self.l.docs[self.i..].partition_point(|&x| x < d); }
}
struct TopK { k: usize, h: BinaryHeap<Reverse<(u32, u32)>> }
impl TopK {
    fn theta(&self) -> u32 { if self.h.len() < self.k { 0 } else { self.h.peek().unwrap().0 .0 } }
    fn push(&mut self, s: u32, d: u32) {
        if self.h.len() < self.k { self.h.push(Reverse((s, d))) }
        else if s > self.theta() { self.h.pop(); self.h.push(Reverse((s, d))) }
    }
    fn scores(self) -> Vec<u32> { self.h.into_sorted_vec().iter().map(|r| r.0 .0).collect() }
}
/// Sum the scores of all cursors at `d` and step them past it.
fn take(cur: &mut [Cur], d: u32) -> u32 {
    cur.iter_mut().filter(|c| c.doc() == d).map(|c| { c.i += 1; c.l.sc[c.i - 1] }).sum()
}
/// Baseline: score every document in any list. Returns (top-k scores, docs scored).
pub fn exhaustive(q: &[&List], k: usize) -> (Vec<u32>, usize) {
    let mut cur: Vec<Cur> = q.iter().map(|l| Cur { l, i: 0 }).collect();
    let (mut top, mut scored) = (TopK { k, h: BinaryHeap::new() }, 0);
    loop {
        let d = cur.iter().map(|c| c.doc()).min().unwrap();
        if d == END { break; }
        scored += 1;
        top.push(take(&mut cur, d), d);
    }
    (top.scores(), scored)
}
/// WAND, or Block-Max WAND if `blocks`. f > 1.0 prunes unsafely.
pub fn wand(q: &[&List], k: usize, blocks: bool, f: f64) -> (Vec<u32>, usize) {
    let mut cur: Vec<Cur> = q.iter().map(|l| Cur { l, i: 0 }).collect();
    let (mut top, mut scored) = (TopK { k, h: BinaryHeap::new() }, 0);
    loop {
        cur.sort_by_key(|c| c.doc());
        let th = top.theta() as f64 * f;
        // pivot: first cursor where the running sum of list maxima exceeds the threshold
        let (mut ub, mut p) = (0u64, None);
        for (j, c) in cur.iter().enumerate() {
            if c.doc() == END { break; }
            ub += c.l.lmax as u64;
            if ub as f64 > th { p = Some(j); break; }
        }
        let Some(mut p) = p else { break };
        let pd = cur[p].doc();
        while p + 1 < cur.len() && cur[p + 1].doc() == pd { p += 1; }
        if blocks {
            let (mut bub, mut next) = (0u64, END);
            for c in &cur[..=p] { let (m, last) = c.l.shallow(pd); bub += m as u64; next = next.min(last.saturating_add(1)); }
            if bub as f64 <= th { // no document up to the end of these blocks can win
                if p + 1 < cur.len() { next = next.min(cur[p + 1].doc()); }
                let j = (0..=p).find(|&j| cur[j].doc() < next).unwrap();
                cur[j].next_geq(next);
                continue;
            }
        }
        if cur[0].doc() == pd {
            scored += 1;
            top.push(take(&mut cur, pd), pd);
        } else {
            let j = (0..p).find(|&j| cur[j].doc() < pd).unwrap();
            cur[j].next_geq(pd);
        }
    }
    (top.scores(), scored)
}
fn main() {
    let mut x = 0x9E3779B97F4A7C15u64;
    let mut rnd = move || { x ^= x << 13; x ^= x >> 7; x ^= x << 17; x };
    let lists: Vec<List> = (0..200u64).map(|t| {
        let mut docs: Vec<u32> = (0..(500_000 / (t + 1)).max(500)).map(|_| (rnd() % 2_000_000) as u32).collect();
        docs.sort_unstable(); docs.dedup();
        let w = 40.0 * (1 + t / 25) as f64; // rarer terms weigh more
        let sc = docs.iter().map(|_| 1 + (w * ((rnd() % 1000) as f64 / 1000.0).powi(4)) as u32).collect();
        List::new(docs, sc)
    }).collect();
    let queries: Vec<Vec<&List>> = (0..300).map(|_| {
        let mut ids: Vec<usize> = (0..4).map(|_| (rnd() % 200).min(rnd() % 200) as usize).collect();
        ids.sort(); ids.dedup();
        ids.into_iter().map(|i| &lists[i]).collect()
    }).collect();
    let run = |name: &str, f: &dyn Fn(&[&List]) -> (Vec<u32>, usize)| {
        let r: Vec<_> = queries.iter().map(|q| f(q)).collect();
        println!("{name}: scored {}", r.iter().map(|x| x.1).sum::<usize>());
        r
    };
    let e = run("exhaustive", &|q| exhaustive(q, 10));
    let w = run("WAND", &|q| wand(q, 10, false, 1.0));
    let b = run("BMW", &|q| wand(q, 10, true, 1.0));
    let a = run("BMW f=1.1", &|q| wand(q, 10, true, 1.1));
    for i in 0..300 { assert_eq!(e[i].0, w[i].0); assert_eq!(e[i].0, b[i].0); }
    println!("f=1.1 exact in {} of 300", (0..300).filter(|&i| a[i].0 == e[i].0).count());
}

main asserts that WAND and BMW return the exhaustive top-10 scores on 300 queries (scores, not docids: ties may differ).

Complexity and constants

• Worst case O(Σ|L|) plus sorting n cursors per step (n = query terms); gains depend on the score distribution.
• Measured on this Mac (Apple M4 Pro, one thread, in memory, uncompressed): 2M docids, 200 lists, 2.84M postings, blocks of 64, skewed integer scores, 300 queries of 3.95 distinct terms (biased to long lists), k = 10.

• Time was 0.7-1.6 ms/query for all four (five runs, busy machine): no speedup, since scoring here is one integer add. Pruning pays where scoring means decoding and computing a similarity.

Efficiency

• Cost: per step n cursor loads, a small sort and block-max lookups; full scoring only for survivors. Bound: memory latency and decoding of unskipped blocks. Scoring work fell 18.6x (WAND) and 49x (BMW) (measured, above). Vespa's docs: one MS MARCO passage query over 8.8M documents ranks 7,926,256 with OR, 196,900 with WAND.
• Levers:
  • block maxima on top of list maxima — 2.6x fewer documents than WAND (measured, above) — scoring or decoding is costly
  • variable-sized blocks — faster than fixed blocks per the paper's title (Mallia et al., SIGIR 2017) — you control index building
  • MaxScore split — no per-step re-sort of cursors (reasoning, not measured) — queries with many terms
  • F > 1 — 2.4x fewer documents at F = 1.1 but exact in only 44 of 300 queries (measured, above) — recall can be traded
• Naive → standard → state of the art:
  • exhaustive DAAT · 84,467 documents scored per query (above)
  • WAND or MaxScore, list maxima · 4,556 per query (above)
  • block maxima in skip data · 1,728 per query (above)

Implementation notes

• Integer scores keep sums exact; float sums in different cursor orders differ in the last bits.
• Block maxima go in the skip data beside the last docid, so a shallow move leaves bit-packed ids undecoded. Lucene's codecs store per-block impacts (CHANGES: LUCENE-4198).
• A shallow move must not advance the cursor. Share θ across segments or shards.

Pitfalls

• Stored maxima go stale when the similarity or index statistics change; store raw frequency and norm.
• >= instead of > against θ makes ties flip between methods.
• Per-document boosts or proximity terms break the bound unless their maximum is added.

Variants and alternatives

In production

Apache Lucene: Boolean queries use block-max WAND since 8.0 (CHANGES entry LUCENE-8135), filtered disjunctions run via MaxScoreBulkScorer (GITHUB#14014); tantivy: block-WAND for unions and intersections; PISA: research engine with a block-max WAND query (block_max_wand_query.hpp); Vespa: WAND for accelerated OR retrieval.

Implementations

Sources

• Howard Turtle, James Flood, Query evaluation: strategies and optimizations, Information Processing & Management 31(6), 1995. paper
• Andrei Z. Broder et al., Efficient query evaluation using a two-level retrieval process, CIKM 2003. paper
• Shuai Ding, Torsten Suel, Faster top-k document retrieval using block-max indexes, SIGIR 2011. paper
• Antonio Mallia et al., Faster BlockMax WAND with variable-sized blocks, SIGIR 2017. paper
• Antonio Mallia et al., PISA: Performant indexes and search for academia, OSIRRC 2019. paper
• Joel Mackenzie, Andrew Trotman, Jimmy Lin, Efficient document-at-a-time and score-at-a-time query evaluation for learned sparse representations, ACM TOIS 2022. paper
• Vespa documentation, WAND: Accelerated OR search. docs