Scoring and top-k skipping

Why does the algebra of the score set the cost of search?

Scoring, and why its algebra decides the cost model

From TF-IDF to BM25

TF-IDF comes from two observations.

1. A term that appears more often in a document says more about it, but sublinearly: the tenth occurrence adds much less than the second. This is term frequency (TF).
2. A term's informativeness is its rarity. -log(df/N), where df is the number of documents containing the term and N is the total number of documents, is the term's surprisal (how unexpected it is). This is inverse document frequency (IDF). A term appearing in 0.1% of documents discriminates roughly three orders of magnitude better than one appearing in most of them.

BM25 is TF-IDF with its two obvious defects patched:

• an explicit saturation curve, so term frequency cannot grow without bound;
• length normalization, so a long document does not accumulate relevance merely by being long.

Claim type. BM25's functional form has a probabilistic derivation, but its parameters are fitted constants with conventional defaults, and its three decades of dominance are empirical, not derived. It survived because it is cheap, robust across corpora without tuning, and, the part that matters for architecture, decomposable.

Decomposability: the property that makes search affordable

The score of a document is a sum of independent per-term contributions, each with a computable maximum. That algebraic property, and not any storage decision, is what makes search affordable.

Why. A user wants ten results. There may be a million candidates. The engine keeps a heap (a structure that always lets you read the smallest of its items quickly) of the current best ten, and a threshold equal to the tenth-best score so far. For any block of postings:

• precomputed and stored in the index is the maximum achievable score of any document in that block;
• add the maximum contributions of the remaining query terms;
• if the total cannot exceed the threshold, skip the block entirely without reading it.

This is the WAND / block-max family of algorithms (WAND = Weak AND). In pseudo-code:

# heap holds the best 10 (score, doc) pairs seen so far
threshold = heap.min_score()          # tenth-best score so far
for block in postings_blocks(query_terms):
    best_possible = block.max_score + sum(t.max_score for t in other_terms)
    if best_possible <= threshold:
        continue                      # skip: no document here can enter the top 10
    for doc in block:
        s = score(doc, query_terms)
        if s > threshold:
            heap.push(s, doc)
            threshold = heap.min_score()

This is zone maps applied to scores instead of values. It is the same mechanism as min/max statistics and page skipping, with the same one-sided guarantee, applied to a different quantity. What generalized: the bound need not be over a stored value. It only needs to be over a computable function of it.

Three consequences

1. The index becomes coupled to the ranker. Stored score bounds are valid only for the scoring function they were computed under. Change the ranking formula and either the skipping metadata is wrong or the index must be rewritten. Ranking changes are heavier operations than they look.

2. Query latency becomes strongly data-dependent. A selective query terminates after reading a fraction of its postings. A query of common terms with a flat score distribution reads almost everything. Same query shape, two orders of magnitude apart in cost. Variance costs more than volume here: variance, not volume, is what sizes the cluster. (This explains Amara's "the red kurta": the word "the" is in nearly every document, so its postings are huge and its bound is useless for skipping.)

3. Any score you cannot bound per term costs you all of this. Which brings us to phrases.

The general form reaches well beyond search: what can be skipped, pushed down, parallelized, merged or precomputed is determined by the algebra of the function, not the layout of the data. Block-max skipping requires a decomposable score with per-term bounds. Partial aggregation (computing sums on each shard and then adding them) requires associativity (the grouping of operations does not change the result). Predicate pushdown requires the predicate to be expressible in the remote system's dialect. Proximity scoring has none of these properties and therefore gets none of the optimizations. The same question later decides which time-series aggregates can be rolled up.

How you know the ranking is good

Nothing in the index can say. The tools are judgement sets (humans label which results are relevant for sample queries), NDCG (a score that rewards putting highly relevant results near the top), and interleaved online tests (mixing results of two rankers on one page and counting which gets more clicks). Relevance is measured, not asserted.

One line: the score's algebra, not the storage layout, sets the cost model. Decomposable and boundable means skippable.