Search relevance evaluation

A search system lives or dies on relevance measurement. There are two regimes — human judgments offline and behaviour online — and the central hazard is mistaking biased click data for ground-truth relevance.

This lesson depends on three earlier ones. We are evaluating the learned ranker of lesson 44 — that is the thing under test. We lean on lesson 7 for why clicks are biased and lesson 8 for the metric and A/B foundations (NDCG/MAP definitions, power/MDE, the offline-is-a-proxy argument). This lesson extends lesson 8 into the search-specific story: graded judgments and pooling, the full graded-NDCG arithmetic, interleaving as the high-sensitivity online tool, and the search metric vocabulary. It sets up lesson 49, where these metrics become the dashboards and guardrails that gate a serving system.

Two regimes, one loop

Search relevance is measured in two complementary regimes. Offline judgments ask a human (or a model standing in for one) "is this document relevant to this query?" — a verdict about the query–document pair that is, by construction, independent of where the document was shown. Online behaviour watches what real users do with real result pages. Offline is cheap to iterate, reproducible, and free of position bias — but it is stale, expensive to refresh, and blind to the parts of the corpus nobody judged. Online is the ground truth of "did users succeed" — but it is slow, confounded by novelty, and contaminated by the very biases lesson 7 catalogued. Neither alone is enough; the loop below ties them together.

Human judgments and qrels

A judgment (the relevance-assessment literature calls the file of them qrels — "query relevance judgments") is a human verdict on a (query, document) pair. The cheapest version is binary — relevant / not. Search uses graded relevance instead, because "relevant" is not one thing: a query [running shoes] has a perfect answer (a running-shoe category page), several good answers (specific running-shoe products), several marginal ones (athletic socks), and a sea of irrelevant ones. A standard five-point scale:

Grades are the input to graded-NDCG and ERR below. The scale only has value if two judges given the same pair produce nearly the same grade — which is what judging guidelines exist to enforce: a written rubric with worked examples for each grade, explicit handling of query intent (is [apple] the fruit, the company, or ambiguous?), freshness rules, and adult/spam policy. Without guidelines, "relevance" drifts between judges and the qrels are noise.

Pooling — you cannot judge the corpus

NDCG wants, in principle, a relevance grade for every document so the ideal ranking is exact. That is impossible: a web corpus has billions of documents, and even an e-commerce catalogue has millions, while a query has only a handful of truly relevant ones. Judging the whole corpus per query is both unaffordable and wasteful — 99.99% of pairs are obvious 0s.

The pooling method (from TREC) solves this. For each query, run all the systems you want to compare, take the top-k from each (say k = 20), union and de-duplicate the results into a pool, and judge only that pool. Everything not in any system's top-k is assumed irrelevant (grade 0). The pool for a query might be 60–120 documents instead of billions, and it provably contains every document any compared system ranks highly — which is exactly the set the metrics are sensitive to.

Inter-annotator agreement

Before trusting a qrel set you measure how much the judges agree. Raw agreement overstates it, because two judges agree by chance a lot when grades are skewed (most pairs are 0). Cohen's κ corrects for chance: κ = (p_o − p_e) / (1 − p_e), where p_o is observed agreement and p_e is the agreement expected from each judge's marginal grade frequencies.

Cost, staleness, and LLM-as-judge

Human qrels are expensive (trained judges, hours per query for ambiguous intents) and stale: the corpus changes daily (new products, new pages, prices, stock), intent drifts (a query that meant a movie last month means its sequel today), and a fixed qrel set silently rots. You cannot re-judge the whole pool every week.

The modern substitute is LLM-as-judge: prompt a large language model with the judging guidelines, the query, and the document, and have it emit a grade. It is ~100–1000× cheaper than humans, instant, and reproducible — which lets you re-judge a refreshed pool daily. But it inherits the model's biases: it favours documents that look authoritative and verbose, is sensitive to prompt phrasing and position-in-prompt, and cannot reliably judge intent it was never told about. Treat it as a fast, biased estimator: calibrate it against a small human-judged gold set (track its κ with the humans), use it to triage and to refresh stale grades, and keep humans in the loop for the high-stakes head-to-head launches. The mechanism and trade-offs of LLM scoring are in lesson 26.

Offline metrics — all computed on one shared list

To make the formulas concrete rather than symbolic, fix one ranked list and one qrel set and compute every metric on it. The arithmetic below is reproduced exactly by the widget.

Shared list — query A = [running shoes]. The lesson-44 ranker returns 8 documents; the qrels give each a graded relevance:

There are 5 relevant documents in this list (positions 1, 2, 4, 5, 7). We treat "relevant" for the binary metrics as grade ≥ 1, and "relevant" for recall's denominator as the total relevant known in the qrels (assume 6 exist for this query — one relevant doc sits outside the returned 8).

Precision@k and recall@k

Precision@k = (relevant in top k) / k. Recall@k = (relevant in top k) / (total relevant for the query). At k = 5 the top five are grades [3, 2, 0, 3, 1] → 4 relevant:

P@5 = 4 / 5 = 0.800    R@5 = 4 / 6 = 0.667

Precision asks "of what I showed, how much was good?"; recall asks "of what was good, how much did I show?" Neither cares about order within the top k — swap positions 1 and 5 and both are unchanged. That blindness to order is why ranking uses the position-discounted metrics below.

MRR — mean reciprocal rank

MRR scores a query by the reciprocal of the rank of its first relevant result, then averages over queries: MRR = (1/Q) Σ_q 1/rank₁(q). For query A the first relevant doc is at position 1, so 1/1 = 1.000. If the first relevant had been at position 3 it would be 1/3 = 0.333. MRR is the right metric for single-answer / navigational intent (find the one official page, the one definition) and is deliberately blind to everything past the first hit — useless for a browsing or shopping result page where the user scans many items.

AP and MAP — average precision

Average precision (AP) for a query is the mean of the precision values computed at each rank where a relevant document appears, divided by the total number of relevant documents:

AP = (1 / R) Σ_{i: rel} P@i

For query A, relevant docs sit at positions 1, 2, 4, 5, 7 and R = 5 (relevant within the list). Compute precision at each of those ranks:

AP_A = (1.0000 + 1.0000 + 0.7500 + 0.8000 + 0.7143) / 5 = 4.2643 / 5 = 0.8529

AP rewards putting relevant docs early (each early hit lifts the precision of every later relevant rank) and is binary-relevance only — it ignores the grade magnitude. MAP is AP averaged over a query set. Take a second query B = [trail shoes review] with returned grades [0, 3, 2, 0, 1] (relevant at 2, 3, 5; R = 3):

AP_B = (0.5000 + 0.6667 + 0.6000) / 3 = 1.7667 / 3 = 0.5889

MAP = (AP_A + AP_B) / 2 = (0.8529 + 0.5889) / 2 = 0.7209

NDCG@5 with graded relevance — the search default

NDCG is the metric search teams quote first, because it does the two things the others each do separately: it uses the graded label (a grade-3 hit beats a grade-1 hit) and it discounts by position (a hit at rank 1 beats the same hit at rank 5). The standard "exponential gain" form:

DCG@k = Σ_i=1..k (2^rel_i − 1) / log₂(i + 1)

The numerator 2^rel − 1 turns grades into gains [0→0, 1→1, 2→3, 3→7, 4→15] — convex, so a single perfect result is worth more than several mediocre ones. The denominator log₂(i+1) is the position discount: rank 1 divides by 1, rank 2 by 1.585, and so on. IDCG is the DCG of the ideal ordering (grades sorted descending), and NDCG = DCG / IDCG normalises into [0, 1] so queries with different numbers of relevant docs are comparable.

DCG@5 on query A (grades [3, 2, 0, 3, 1]):

DCG@5 = 7.0000 + 1.8927 + 0 + 3.0148 + 0.3868 = 12.2943

IDCG@5 — sort all eight grades descending: [3, 3, 2, 2, 1, 0, 0, 0], take the top 5 → [3, 3, 2, 2, 1]:

IDCG@5 = 7.0000 + 4.4164 + 1.5000 + 1.2921 + 0.3868 = 14.5953

NDCG@5 = DCG@5 / IDCG@5 = 12.2943 / 14.5953 = 0.8424

The list scores 0.842 — good, but the grade-0 at position 3 and the grade-3 stranded at position 4 cost it. Move the position-4 grade-3 up to position 3 (swap with the 0) and DCG@5 becomes 7.0000 + 1.8927 + 7/2 + 0 + 0.3868 = 12.7795, NDCG@5 = 0.8756. The top positions dominate: because the discount is steepest there, the same swap matters far more between ranks 1–2 than 7–8. The widget makes this sensitivity tangible.

ERR — expected reciprocal rank, in one breath

NDCG's position discount is fixed (it ignores what the user already saw). ERR (Chapelle et al. 2009) uses a cascade model instead: the user scans top-down, and the probability of being satisfied at position i — and thus stopping — rises with that document's grade, R_i = (2^rel_i − 1) / 2^rel_max. ERR is the expected reciprocal of the stopping rank: ERR = Σ_i (1/i) · R_i · Π_j<i(1 − R_j). The point versus NDCG: a strong result early discounts the value of everything after it, because a satisfied user never reaches it. ERR models "one good answer is enough"; NDCG models "more good answers keep adding value." Use ERR for navigational/single-answer surfaces, NDCG for browse/shop surfaces — which is why NDCG is the search default.

The bias problem: clicks are not relevance

Online, the cheap and abundant signal is the click — and the tempting shortcut is to treat "clicked" as "relevant" and feed click-NDCG straight into evaluation. This is the central hazard of the whole lesson. Lesson 7 derived why clicks are biased; the two that wreck naive click-relevance:

• Position bias. Users click the top result far more often regardless of relevance, because they look there first and trust the ranking. A document at rank 1 can out-click a more relevant document at rank 5 purely from position. Evaluate by raw click-through and you reward the ranking you already have — a feedback loop that ossifies the current order.
• Presentation bias. A rich snippet, a thumbnail, a price badge, or a bolded query-term match pulls clicks independent of the landing page's relevance. Clickbait titles are the adversarial case (the lesson-8 watch-time example).

Click models are the principled patch: model the click as examination × relevance. In the position-based model, P(click | doc at rank i) = ν_i · ρ_doc, where ν_i is the position's examination probability and ρ_doc is the click-relevance you actually want. Cascade models add the stop-after-satisfied dynamic ERR uses. Fit the examination curve (from randomised position swaps, RandPair, or intervention harvesting) and you can divide it out.

That division is counterfactual / IPS evaluation — the bridge from biased logs back to unbiased relevance, using the importance-weighting machinery of lesson 8. Inverse-propensity-score weighting reweights each logged click by 1/ν_i (one over the probability the user examined that position): a click at a rarely-examined low rank is strong evidence and gets up-weighted; a click at the always-examined top is weak evidence and gets down-weighted. The result is an estimate of relevance-driven engagement stripped of position bias — turning the firehose of logs into something you can rank candidates on without an A/B test, at the cost of the variance blow-up lesson 8 warned about (clip the weights). Counterfactual estimates triage which candidates earn online traffic; they do not replace the online test.

Online evaluation

The online regime has two tools. Interleaving is the high-sensitivity scalpel for comparing two rankings; an A/B test is the blunt, general instrument for comparing two systems on business metrics. Search teams use both: interleave to screen ranking changes fast, A/B to confirm the winner moves the numbers that matter.

Interleaving — credit assignment within a single result page

A standard A/B test shows arm A to one set of users and arm B to a disjoint set, then compares aggregate metrics between populations. The between-user variance is enormous: users differ wildly in query volume, intent, and click propensity, and that noise swamps a small ranking improvement. Interleaving eliminates the between-user variance by showing both rankings to the same user on the same query, merged into one result page, and letting the user's clicks vote for a list.

Team-draft interleaving builds the merged list like captains picking a playground team. Flip a fair coin each round to decide which ranking "drafts" first; that ranking contributes its highest not-yet-used document; the other ranking then contributes its highest not-yet-used document; repeat. Each slot is tagged with the team (A or B) that contributed it. When the user clicks a result, the click is credited to that result's team. Whichever team accumulates more clicks on that impression wins that query.

Why does this need 10–100× less traffic than an A/B test to detect the same ranking difference? Three compounding reasons, all about variance:

• Paired / within-user. The comparison is a paired difference on the same user and query, so all the between-user variance (the dominant term in A/B) cancels — like a paired t-test versus a two-sample one.
• Same query, controlled intent. A/B compares pages across different queries in each arm; interleaving compares two rankings on the identical query, removing query-mix variance.
• Direct preference signal. The outcome is a clean per-query A-or-B vote, not a noisy continuous metric you must difference across millions of sessions. The effective sample is "queries where the rankings differed," and each contributes a high-information binary vote.

Concretely: detecting a tiny CTR difference between two rankings might need millions of sessions per arm in A/B (lesson 8's MDE formula — variance dominated by σ across users), while interleaving resolves the same preference from tens of thousands of differing queries. The cost: interleaving measures a ranking preference, not a business metric. It tells you which ranking users prefer click-for-click; it does not tell you revenue, retention, or whether the preference survives presentation bias. So it is a screening tool — promising interleaving results graduate to an A/B test.

A/B testing with search metrics

The A/B mechanics, power/MDE, SRM, novelty, CUPED, and guardrails are all in lesson 8 and the deep dive in lesson 33 — do not re-derive them. What is search-specific is the metric vocabulary, because "did search work?" is not a single click rate. The session-level signals:

Guardrails. Even a relevance win ships only if it does not regress the things you are not trying to change: serving latency / p99 (a slower but more relevant ranker can lose net — lesson 49), revenue / ads load, result diversity, and abuse/safety rates. Guardrails are evaluated for non-inferiority (the new arm must not be detectably worse by more than a margin), not for lift. A relevance metric that moves +1% while p99 latency moves +40 ms and revenue moves −0.5% is not a launch — it is a trade-off decision that goes up the chain.

Interactive · search metrics calculator

An 8-document ranked list with editable graded relevance (0–4). Adjust the grades or swap adjacent documents and watch every metric move live. The numbers match the prose formulas exactly: load the default grades [3,2,0,3,1,0,2,0] and you get NDCG@5 ≈ 0.842 (0.8423 at full precision; the prose table rounds intermediate terms to 0.8424), MRR = 1.000, AP = 0.8529, P@5 = 0.800. Watch how moving a high grade to position 1 versus position 8 changes NDCG by very different amounts — the top-position sensitivity made visible.

Interview prompts you should be ready for