Four functions hiding one loop

Imagine four implementations:

1. Boolean weighted coverage adds one unit for each matched query term.
2. TF–IDF multiplies rarity by a local frequency weight and adds the products.
3. BM25F substitutes the saturated, field-normalized local weight from Chapter
4. sparse-vector cosine divides an accumulated dot product by precomputed vector norms.

Written independently, each traverses query terms, postings, and documents. The repeated control flow hides their common structure and makes later changes depend on memory: a new source weight or explanation term reaches only the functions somebody remembers to edit.

Write the shared contribution instead. For query-term group $g$ and document $d$, let

$$c(g,d)=e_g\times r_g\times \ell(g,d),$$

where $e_g$ is an expansion or query weight, $r_g$ is collection rarity, and $\ell(g,d)$ is the ranker's local document evidence. Then

$$S(d)=\sum_{g\in G}c(g,d).$$

Only the policies differ.

The table is not a claim that all relevance models are equivalent. It says these models share a traversal and combination law while choosing different evidence maps.

The smallest useful algebra

For nonnegative scores, use

$$\langle\mathbb R_{\ge0},\oplus,\otimes,0,1\rangle =\langle\mathbb R_{\ge0},+,\times,0,1\rangle.$$

This is a commutative semiring: addition and multiplication are associative, each has an identity, multiplication distributes over addition, and zero annihilates multiplication.

In retrieval, the two operations have concrete jobs:

• $\otimes$ combines independent factors for one evidence item;
• $\oplus$ accumulates evidence items for one document;
• $1$ means a factor has no effect;
• $0$ means absent evidence contributes nothing.

The identity values are engineering tools. When one ranker has no expansion penalty, set $e_g=1$. When a new field-weight parameter is generalized from a fixed implementation, its default $1$ should reproduce the old behavior. A byte-for-byte identity case is a cheap regression oracle—and often reveals places that had quietly hardcoded the old assumption.

What associativity buys—and what floating point takes back

Mathematically,

$$(a\oplus b)\oplus c=a\oplus(b\oplus c).$$

That licenses grouping contributions into blocks, shards, or explanation trees and combining their partial sums. Commutativity says the mathematical answer does not depend on enumeration order.

IEEE 754 addition is not exactly associative. For example, a large magnitude can absorb a small addend before another operation exposes it. Therefore a bit-identical implementation refactor preserves iteration and association order even when the mathematical model permits regrouping. A parallel engine that chooses a fixed reduction tree can be deterministic without reproducing a left fold, but that is a declared numerical contract, not an algebraic freebie.

The distinction is useful throughout the book:

• the semantic law explains which regroupings preserve the real-number model;
• the machine contract explains which evaluation order defines the published floating-point value.

Explanations are not a second scorer

If the reported score is

$$S(d)=c(g_1,d)+\cdots+c(g_m,d),$$

then its explanation can retain the labeled contributions

$$[(g_1,c(g_1,d)),\ldots,(g_m,c(g_m,d))].$$

Folding their numeric projection must reproduce the score in the same order. The explanation is therefore a richer carrier mapped homomorphically to the number, not prose generated later from a second approximation.

This gives three tests:

1. every reported contribution names its term group and factors;
2. folding contributions in the score's evaluation order equals the exact reported score;
3. evidence absent from the explanation is absent from the score.

A finalizer such as a coverage boost can consume two parallel monoids: the score sum $\langle\mathbb R_{\ge0},+,0\rangle$ and coverage count $\langle\mathbb N,+,0\rangle$. Allocate and expose the count only when the policy actually uses it.

One query idea should contribute once

Suppose the query term color expands to colour and a stem variant. If one document contains all variants, adding every posting rewards spelling redundancy rather than query coverage.

Group alternatives by the original query idea. Within a group use exact-else-maximum:

When exact evidence exists, define

$$C(g,d)=c(\operatorname{exact},d).$$

Otherwise, if alternatives match, define

$$C(g,d)=\max_{a\in\operatorname{alternatives}(g)}c(a,d).$$

If neither exists, $C(g,d)=0$.

Maximum is associative, commutative, and idempotent:

$$\max(x,x)=x.$$

So discovering the same alternative twice or enumerating alternatives in a different order cannot inflate the group score. Exactness is a lexicographic priority, not merely another additive bonus that enough alternatives can overcome.

Monotonicity is the pruning license

Order evidence vectors coordinatewise. If $x\le y$ means every contribution in $x$ is no larger than the corresponding contribution in $y$, an accumulator $F$ is monotone when

$$x\le y\Longrightarrow F(x)\le F(y).$$

Nonnegative addition is monotone. Adding evidence cannot lower the score. This allows an upper bound on unseen contributions to bound the final score.

Let $s(d)$ be the exact score and let $\widehat s(d)$ be a computable bound such that

$$\widehat s(d)\ge s(d)$$

for every candidate. Let $\theta$ be the current score of the $k$th retained document under the declared total tie order.

Proof. From validity, $s(d)\le\widehat s(d)$. From the skip test, $\widehat s(d)<\theta$. Hence $s(d)<\theta$. At least $k$ retained documents score at or above $\theta$, so $d$ cannot displace one. A nondecreasing threshold cannot make the skipped candidate eligible later. $\square$

Those four lines are the intellectual center of dynamic pruning. An underestimate is not a small performance error. It can silently discard the true winner. An overestimate preserves correctness but saves less work.

When ties matter, replace the scalar comparison with the same total order used by top-k—for example score descending, then stable document identity ascending. The bound must be conservative for that admission rule too.

How a ranking change breaks the proof

Several common additions require a new proof:

• a negative weight makes “more evidence cannot hurt” false;
• a diversity penalty depends on which other documents have already won;
• a cross-document normalization changes when the candidate population changes;
• a learned or nonlinear combiner may not expose a valid coordinatewise bound;
• an after-the-fact freshness rule can reorder documents after the threshold was established;
• a bound computed from stale field statistics may fall below the score it is meant to dominate.

These features are not forbidden. They announce that the simple additive pruning theorem no longer applies. Keep the monotone first-stage retriever and apply a non-monotone reranker to an explicitly bounded candidate set, or derive and test a stronger bound for the new function.

Rank fusion maps positions, not incomparable scores

Two retrievers may publish scores on unrelated scales: a BM25 value of 12 and a vector similarity of 0.82 do not become commensurable because both are numbers. Adding normalized scores introduces a calibration policy.

Reciprocal rank fusion first maps a document's position in each complete component ranking to

$$\rho(r)=\frac{1}{K+r},$$

then adds those mapped values:

$$\operatorname{RRF}(d)=\sum_{R\in\mathcal R}\frac{1}{K+r_R(d)}.$$

The additive fold survives, but the homomorphism begins from rank positions, not component scores. This discards scale while retaining within-run order. The empirical choice of $K$ remains a policy to evaluate; it is not derived by the semiring laws.

Component rankings must be complete relative to their declared candidate universe and cutoff. Filtering inside one component changes its positions and therefore changes fusion policy. Eligibility can instead be enforced while accumulating the fused result, provided forbidden identities never affect an observable component run for that principal.

One scorer, closed policies

The reusable evaluator needs a per-term stage and a per-posting stage:

SCORE-DOCUMENT(GROUPS, DOCUMENT, POLICY)
Input:  query-term GROUPS, one DOCUMENT, closed scoring POLICY
Output: final score and ordered explanation contributions

sum ← 0
coverage ← 0
explanation ← empty sequence
for each group g in GROUPS in declared order
    termPolicy ← PREPARE-TERM(POLICY, g)
    contribution ← CHOOSE-GROUP-CONTRIBUTION(g, DOCUMENT, termPolicy)
    if contribution exists
        sum ← sum + contribution.value
        coverage ← coverage + 1
        explanation ← APPEND(explanation, contribution)
return FINALIZE(POLICY, sum, coverage), explanation

The policy record is closed: every ranker configuration must state its rarity, local-weight, expansion-choice, and finalization behavior. A new ranker that cannot fit the fold has supplied useful evidence that it needs different laws, not a reason to smuggle another branch into the traversal.

Keep the slow scorer forever

The exhaustive implementation is not scaffolding to delete after pruning works. It is the executable specification.

Generate small corpora, queries, filters, field statistics, expansion groups, and tie cases. Compare full ordered results and full-precision scores from the optimized evaluator with the exhaustive fold. When the bound is wrong, the optimized output looks plausible; only the missing candidate reveals the bug.

Also check the laws directly:

• identity: multiplying by 1 and adding 0 preserve the result;
• group idempotence: duplicating an alternative does not change the score;
• enumeration invariance: permuting alternatives does not change group choice;
• explanation projection: ordered contribution folding reproduces the score;
• bound dominance: every generated exact score is at most its bound;
• top-k parity: optimized and exhaustive ordered winners are identical.

For refactors, “same ranking” is weaker than “same scores.” Preserve group, match, and posting iteration order and the association order of products, then diff full-precision outputs. A rounded display can hide a changed threshold.

Lessons

• Several lexical rankers are one product-then-sum fold with different policy parameters.
• Identities make generalization backward-checkable and expose hardcoded assumptions.
• Mathematical associativity licenses regrouping; floating-point evaluation still needs a declared deterministic reduction order.
• Explanations retain the same contributions the scorer folds; they are not a second approximate narrative.
• Alternate witnesses for one query idea combine by exact-else-max, an idempotent and order-independent choice.
• Monotonicity plus a valid upper bound turns skipped work into a proof.
• An underestimated bound is a correctness bug; an overestimate is a missed optimization.
• Reciprocal rank fusion combines mapped rank positions, not incomparable raw scores.
• The exhaustive scorer remains the permanent oracle for every optimized path.

Practice

1. Express weighted Boolean coverage, logarithmic TF–IDF, and BM25F as choices of $e_g$, $r_g$, $\ell(g,d)$, and finalization.
2. Give three floating-point values for which left and right association produce different machine results. Which order should an explanation use?
3. Construct a scoring rule with a negative contribution and show precisely where coordinatewise monotonicity fails.
4. A candidate has exact score 8, recorded upper bound 7, and current threshold 7.5. Trace the skip and identify the missing winner.
5. Generate expansion groups with duplicates and permutations. Test that exact-else-max is invariant while additive expansion scoring is not.
6. Fuse two rankings with $K=60$. Then filter one component before assigning positions. Exhibit a document whose fused score changes even though its own component membership did not.

References

1. Andrei Z. Broder, David Carmel, Michael Herscovici, Aya Soffer, and Jason Zien. “Efficient Query Evaluation Using a Two-Level Retrieval Process.” Proceedings of CIKM, 2003.
2. Todd J. Green, Gregory Karvounarakis, and Val Tannen. “Provenance Semirings.” Proceedings of PODS, 2007.
3. Gordon V. Cormack, Charles L. A. Clarke, and Stefan Büttcher. “Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods.” Proceedings of SIGIR, 2009.
4. Stephen Robertson and Hugo Zaragoza. “The Probabilistic Relevance Framework: BM25 and Beyond.” Foundations and Trends in Information Retrieval 3, no. 4, 2009.