Block-max WAND, explained

A naive multi-term search scores every document that contains at least one query term, then sorts by score and keeps the top K. That's correct, and for short postings lists it's fine. It stops being fine once postings lists get long: scoring a candidate document means computing its full BM25 score across every query term, and doing that for every candidate is wasted work the moment a document has no realistic chance of making the top K anyway.

Block-max WAND (Weak AND) is a query execution strategy that skips that wasted work — without changing which documents end up in the results.

The core idea: an upper bound you can trust

For each query term, Tachyon's postings are stored in fixed-size blocks, each carrying per-block skip metadata: the maximum document ID in the block, and the maximum term frequency any document in that block achieves for that term. From max term frequency, an upper bound on the highest possible BM25 contribution any document in that block could score for that term is cheap to compute — cheaper than actually scoring anything in it.

That upper bound is the whole trick. If you sum the per-term upper bounds for a block across all query terms, and that sum can't beat the current lowest score already sitting in your top-K results, then nothing in that block — no matter which specific document, no matter its actual term frequencies — can possibly make the top K. The block can be skipped entirely: no decoding, no per-document scoring, nothing.

Why this doesn't change the results

This is the property that makes it worth doing at all: block-max WAND produces the exact same top-K ranked results as scoring every candidate document individually would. It isn't an approximation, and it isn't a different ranking function — it's the same BM25 scoring, applied to a smaller set of candidates, because every candidate it skips has been mathematically proven incapable of affecting the outcome. Nothing that could have ranked is left out; nothing gets skipped based on a heuristic that might occasionally be wrong.

Where it actually saves work

The savings scale with how skewed your term frequencies are, and how deep your postings lists are. A two-term query where one term is rare and one is extremely common is the textbook case: the common term's postings list is long, but once the top-K is populated with a handful of good matches from the combination of both terms, huge stretches of the common term's postings — blocks where its max term frequency isn't nearly high enough to compensate for not matching the rare term at all — get skipped without ever being decoded.

For short queries against small collections, the effect is negligible; there's not enough postings-list depth for skipping to matter. It pays off precisely where naive scoring gets expensive: multi-term queries against large, skewed collections — which is the common case for real production search traffic, not the edge case.

Where it fits in the pipeline

Query execution in Tachyon: parse the query, run it against the inverted index with filters applied in parallel, rank with BM25 (pruned by block-max WAND for multi-term queries), return the top K. See Architecture for the full pipeline and how the on-disk block layout — including the skip metadata this relies on — is structured, and Relevance & BM25 for the scoring function itself.