Learn · Evaluation

budding

How Do You Know It Got Better?

A tuning change becomes knowledge only when a pinned evaluator can prove or refute it.

search, evaluation, relevance, ndcg, metamorphic-testing, metrics, experiments, learn

“Relevance judgments, or the ‘right answers’, are a vital part of a test collection.”

— U.S. National Institute of Standards and Technology, TREC Relevance Judgments

This is the twenty-fourth chapter in a book about search from first principles. You will begin evaluation before labels with metamorphic relations, construct generators that actually reach search behavior, compare optimized and exhaustive rankers on their shared surface, and assemble a pinned test collection. You will derive precision, recall, reciprocal rank, and normalized discounted cumulative gain; name what each metric cannot see; pair every target with an independent guard; and emit a query receipt that makes an observation reproducible. You will diagnose corpus drift with rebuilds and held-out documents, keep hard constraints outside scalar rewards, and make flakes and skips loud. The next chapter treats a result list for a machine reader as a context budget rather than a row count.

The first evaluator costs no judgments

Ranker A and Ranker B both put convincing documents near the top. Someone prefers A. Someone else prefers B. Without a task, corpus, judgments, or law, neither opinion can lose.

Before paying for human labels, ask what relationships must hold between two runs. A bag-of-words ranker promises that query term order does not matter. If

$q=(t_1,t_2,\ldots,t_m)$

and $\pi$ is any permutation, then

$R(q)=R(\pi(q)),$

including the deterministic tie order. One run need not have a known correct answer. Their relationship is the oracle.

A metamorphic relation states how outputs from related inputs must relate when the correct output is difficult to enumerate. Chen, Cheung, and Yiu introduced the testing method in their 1998 technical report.

Prediction — identify a law that needs no relevance labels.

Phrase and proximity rankers do not satisfy that relation. Their declared law is narrower: permuting terms may change only the features that depend on order, while unordered contributions remain equal. A test is strong because its precondition is precise, not because it applies everywhere.

Other relations can recover earlier chapters:

indexing and querying with the same analyzer must agree on normalized terms;
decoding encoded posting gaps must recover the original increasing positions;
a pruned top-k path must equal an exhaustive path when both settle completely;
adding a term absent from every document must not reorder existing survivors under a model that ignores zero-evidence terms; and
raising a safe pruning bound may do more work but must not change the answer.

Each relation is a previous proof turned into a permanent test.

A generator must construct the coincidence

Suppose a phrase feature activates only when adjacent query tokens occur in a document. Generate a random corpus and an independent random query. The chance of the required coincidence collapses as the alphabet and token space grow. Thousands of green trials can execute the empty branch thousands of times.

Construct reachability instead:

generate a bounded corpus;
choose one generated document;
choose a nonempty adjacent token window from it;
use that window as the phrase query; and
derive a prefix case by clipping the final chosen token.

Now every trial reaches the promised branch by construction. Mutation provides the falsification check: weaken adjacency, disable the prefix continuation, or make a safe bound unsound and confirm that the suite becomes red.

Algorithm — reachable differential evaluation

CHECK-PRUNED-RANKER(SEED, TRIALS, LIMIT)
Input:  deterministic SEED, positive TRIALS, positive LIMIT
Output: first counterexample or verified receipt

for trial ← 0 to TRIALS - 1
    corpus ← GENERATE-BOUNDED-CORPUS(SEED, trial)
    source ← CHOOSE-NONEMPTY-DOCUMENT(corpus, SEED, trial)
    query ← CHOOSE-TOKEN-WINDOW(source, SEED, trial)
    expected ← EXHAUSTIVE-TOP-K(corpus, query, LIMIT)
    observed ← PRUNED-TOP-K(corpus, query, LIMIT)
    if IDENTITIES(expected) ≠ IDENTITIES(observed)
        return SHRINK-REACHABLE-CASE(corpus, query, LIMIT)
return VERIFIED(SEED, TRIALS, LIMIT)

The test also records that the pruning branch ran. Equality on a shared input proves nothing about code neither side reached. A second implementation and a fast path both owe two witnesses: agreement on shared observations and coverage of the path whose agreement is being claimed.

Compare exactly the shared surface

Parity is broader than language ports. It includes:

an optimized ranker against a simple exhaustive oracle;
a compressed postings reader against an uncompressed model;
an incremental query path against a clean full recomputation; and
two runtime implementations of the same analyzer or scorer.

The comparison pins every semantic input: analyzer, corpus, ranking policy, tie grammar, budgets, settlement requirement, and feature set. If one side has a feature the other lacks, either disable it and record the exclusion or do not claim parity for that feature.

Calling one side “the reference” does not make it eternally authoritative. One implementation can lead on a resource bound while another leads on pruning. The oracle is the declared shared behavior, not seniority. Divergence prompts investigation of both sides.

A test collection gives opinions a common object

The Cranfield tradition reduces a retrieval experiment to three pinned parts:

a document collection;
information needs, expressed as topics or queries; and
relevance judgments connecting each need to documents.

TREC scaled this laboratory object with pooled judgments: systems contribute high-ranked candidates to a pool, and assessors judge that selected subset. Pooling makes large collections tractable, but unjudged documents are not the same fact as judged irrelevant documents. A new system that retrieves outside the pool can expose holes.

Relevance is also task dependent. “Useful for writing a report” differs from “the command I intend to execute,” “the setting I want to change,” and “the single known page I want to revisit.” A fixture therefore records the task and the judgment scale, not only query text and document identifiers.

Two assessors may disagree honestly. Report the judging protocol, assessor count, adjudication, and agreement or disagreement pattern. A judgment set has uncertainty; a metric calculated to six decimals does not remove it.

Four metrics tell four different stories

For a ranked list and cutoff $k$ , let $rel_i$ be a binary or graded judgment at rank $i$ .

Precision at k

$P@k=\frac{\sum_{i=1}^{k}[rel_i>0]}{k}.$

Precision asks how much of the visible budget is relevant. It can be gamed by returning very few conservative results if the denominator is allowed to shrink, so the cutoff and missing-row policy must be fixed. Pair it with recall or coverage of required intents.

Recall at k

$R@k=\frac{\sum_{i=1}^{k}[rel_i>0]}{|D_{relevant}|}.$

Recall asks how much known relevant material arrived. It can be gamed by widening acceptance until irrelevant neighbors flood the list. Pair it with precision and explicit hard negatives.

Reciprocal rank

If $r$ is the first rank with positive relevance, then reciprocal rank is $1/r$ , or zero if there is no hit. Mean reciprocal rank averages that value over queries. It is appropriate for a first-answer task and blind to everything after the first hit. Pair it with a deeper-list metric when more than one result matters.

Normalized discounted cumulative gain

Choose a gain function $G(rel)$ and rank discount $D(i)$ . A common policy is

$DCG@k=\sum_{i=1}^{k}\frac{2^{rel_i}-1}{\log_2(i+1)}.$

Normalize by the ideal ordering of the same judged gains:

$nDCG@k=\frac{DCG@k}{IDCG@k},$

with an explicit convention when ideal gain is zero.

The logarithm is not a natural law. It encodes an examination model whose attention decays roughly with logarithmic rank. A linear discount encodes a finite horizon and falls at a constant rate. The exponential gain likewise turns ordinal judgment levels into a cardinal claim: grade 3 is worth much more than grade 2, not merely one label higher. Järvelin and Kekäläinen's gain-based framework makes those choices visible; the evaluator still must justify them for its task.

Reveal — interpret a disagreement instead of averaging it away.

Every target needs an independent guard

A metric is a proxy. Write its gaming strategy beside it before optimizing.

Primary target	How it can look better falsely	Independent guard
recall@5	widen until near-miss documents flood the list	precision@5 plus hard negatives
MRR	perfect the easiest first hit and neglect the rest	nDCG@10 or recall@10
nDCG	tune to one judged corpus and gain policy	held-out topics and another domain
latency	serve stale, partial, or cached answers as current	generation correctness and settlement under load
branch coverage	execute assertions that cannot fail	mutation kill and differential oracle

If the primary improves while its guard worsens, stop. That divergence is not a minor caveat; it is evidence that optimization found the proxy's blind spot.

A fixture containing only positive judgments cannot evaluate a widening matcher. Recall, MRR, and nDCG can all improve together because none sees the new false positives. Add hard negatives: documents deliberately close to the relevant class but explicitly judged not relevant. Then report precision deep enough to expose the trade.

Hold out topics from tuning. Better still, test a domain with different query lengths, vocabulary, and relevance structure. A ranker that improves only on the design corpus has produced a local result, not a general search claim.

Pin the experiment, not only the score

A threshold such as “nDCG@5 must exceed 0.91” is a regression gate only when the corpus and judgments are pinned. Adding a document changes document frequencies and average length. The same ranking code can then produce a different score.

Against a live corpus, the threshold measures publishing activity and ranking behavior together. That can be a monitoring signal, but it cannot attribute a regression. Keep two different instruments:

a pinned corpus, topics, judgments, and policy for deterministic regression;
a current-corpus monitor whose drift is investigated without pretending the input stayed fixed.

When a quality gate goes red, rebuild the index at each candidate revision. An index is a build artifact; checking out source without rebuilding can measure the same stale artifact repeatedly. Once a range is isolated, hold out one changed document, rebuild, and compare. If removal restores the baseline, the content change—not unchanged scoring code—explains the movement.

A remeasured floor records which stratum moved, why, and what was traded. A number lowered without that receipt is indistinguishable from normalizing a defect.

A query receipt makes the observation reproducible

A ranker toggle is a demonstration until it emits enough identity to repeat the run. Record:

task and query identifier, with raw text omitted where privacy requires;
corpus and index-artifact digests;
analyzer identity and configuration;
ranker, fuzzy matcher, expansion policy, and their versions;
every parameter, feature flag, and deterministic tie grammar;
query-wide budget and child settlements;
ordered result identities, scores, and explanations; and
evaluator, judgment-set, and metric versions.

The receipt is immutable and canonical. A screenshot travels with its receipt, not as evidence by itself. Results cached under one policy version cannot be adopted as evidence for another.

An interactive preference may let a reader compare rankers. That experiment must not silently alter a grounding or evidence pipeline. The pipeline pins its retrieval policy; changing it is a versioned experimental intervention with a new receipt.

Paired queries are the unit of comparison

Compute metric difference $d_j=B_j-A_j$ for each query $j$ . Report the distribution, not only the mean: wins, ties, losses, median, tails, and strata. A paired randomization or bootstrap procedure can quantify uncertainty under its assumptions because both rankers face the same queries.

Statistical significance is not practical importance. A tiny consistent change over many topics can be precisely nonzero and operationally irrelevant. State the smallest consequential effect before looking at results. Examine losing queries and hard-negative failures even when the aggregate is positive.

Do not tune repeatedly on the held-out set and continue calling it held out. Each decision leaks information. Reserve a final untouched evaluation set or collect a new one after exploratory tuning.

Continuation edges need vectors, not one reward

Search may offer a next action: open a document, change a setting, execute a command, or continue into another source. Click-through rate cannot summarize that edge honestly. Record a bounded semantic vector:

offers and activations;
destination admissions and terminal commits;
refusals, failures, abandonment, and reversal;
latency distribution and context loss;
scope delta and evidence window; and
privacy grade.

A named objective may derive a score from eligible observations. Accessibility, authority, semantic reachability, privacy, and explicit user choice remain hard constraints outside the score. No reward compensates for violating them.

Aggregate tallies can compare two already-declared offers. Discovering a useful multi-step path requires ordered evidence, and even then it proposes a product hypothesis rather than silently authorizing a new executable edge. Project receipts into bounded observations after discarding raw query text and stable human identity.

Transfer — repair a unanimously misleading metric table.

A red signal must remain credible

A nondeterministic test turns a real regression into a coin flip. Re-running until green trains everyone to ignore red. Control seeds, clocks, ports, execution order, fixtures, and external dependencies; when nondeterminism is the subject, enumerate or replay it deterministically.

A skipped evaluator is quieter and often worse. If its index fixture is absent, the suite can report green on every machine that never built the artifact. Use two explicit modes:

optional mode emits a loud named diagnostic and the exact artifact-producing action; and
required evaluation mode treats absence as a hard failure.

Count executed queries, judgments, strata, metamorphic relations, parity paths, and mutations killed in the receipt. Zero work is not a pass.

Negative results

Temptation	Failure
tune by screenshots	plausible lists cannot falsify one another
generate query and corpus independently	coincidence-dependent branches stay unreachable
compare outputs without path evidence	both implementations agree on the path neither exercised
test against the live corpus	content drift masquerades as ranking regression
watch only MRR	every result after the first hit becomes invisible
use positive judgments for widening	false-positive harm is absent from every metric
optimize one scalar	the system learns its blind spot
reuse a cache across policy versions	old semantics masquerade as new evidence
rerun a flake until green	red loses its meaning
silently skip a missing fixture	a gate that never ran looks like a pass

Lessons

Begin with law and metamorphic tests that require no relevance judgments.
Construct generators from the corpus so the intended branch is reachable.
Differential parity needs both shared-output agreement and path evidence.
A test collection pins documents, information needs, judgments, and task.
Precision, recall, reciprocal rank, and nDCG observe different harms.
Gain and discount functions encode a user model; they are not natural laws.
Every primary metric names a gaming strategy and an independent guard.
Hard negatives are required to evaluate a widening matcher.
A regression floor pins the corpus; a live-corpus number is monitoring.
Query receipts bind every result to artifact, analyzer, policy, budget, and judgment identity.
Paired uncertainty does not replace a threshold for practical consequence.
Hard constraints remain outside continuation-edge rewards.
Flakes and silent skips corrupt the credibility of every later failure.

Practice

Write three metamorphic relations for an unordered lexical ranker and state the precondition that would invalidate each.
Construct a generator for prefix matching that reaches both a hit and a hard negative on every trial.
Calculate precision@5, recall@5, reciprocal rank, and nDCG@5 for one graded list; then remove the result at rank 4 and explain the disagreement.
Choose a different gain or discount function and state the behavior model it encodes.
Design a query receipt that permits reproduction without retaining raw query text or stable human identity.
Diagnose a red metric after one document was added, using artifact rebuild and held-out-document evidence.
Name the gaming strategy and independent guard for a latency target.
Specify when a missing evaluation artifact warns and when it fails.

References

Cyril W. Cleverdon, Jack Mills, and Michael Keen. “Factors Determining the Performance of Indexing Systems.” College of Aeronautics, Cranfield, 1966.
Ellen M. Voorhees. “Variations in Relevance Judgments and the Measurement of Retrieval Effectiveness.” Information Processing & Management 36.5, 2000.
Ellen M. Voorhees and Donna Harman. “Overview of the Eighth Text REtrieval Conference.” NIST, 1999.
Kalervo Järvelin and Jaana Kekäläinen. “Cumulated Gain-Based Evaluation of IR Techniques.” ACM Transactions on Information Systems 20.4, 2002.
T. Y. Chen, S. C. Cheung, and S. M. Yiu. “Metamorphic Testing: A New Approach for Generating Next Test Cases.” Technical Report HKUST-CS98-01, 1998.

Two rankers and a confident opinion do not make an experiment. Start with laws that need no relevance labels, then pin the corpus, task, judgments, policy, budget, and output identities in a query receipt. A metric means something only when its blind spot and independent guard are written beside it.