Retrieval Evaluation and Experimentation

Introduction

An information retrieval (IR) system is useful only when it retrieves information that satisfies a user’s information need. Indexing speed, query latency, model sophistication, and infrastructure scale matter, but they do not by themselves establish retrieval quality. Evaluation provides the empirical basis for comparing retrieval models, diagnosing failures, selecting operating points, and deciding whether a system should be deployed.

Retrieval evaluation is more difficult than it first appears. Relevance is usually dependent on the user, task, context, document presentation, and time. A document may be topically related but not answer the query; it may be correct but inaccessible; or it may be useful for one purpose and unsuitable for another. Consequently, evaluation combines formal metrics, human judgments, statistical inference, and—when a system is deployed—business and user outcomes.

This chapter develops a complete evaluation framework, beginning with test collections and relevance judgments, progressing through ranked-retrieval metrics, and concluding with offline experiments, online experimentation, and cost-sensitive decision-making.

Learning Objectives

After studying this chapter, you should be able to:

1. Construct and critique test collections for retrieval evaluation.
2. Explain relevance judgments, pooling, assessor agreement, and judgment bias.
3. Calculate and interpret precision, recall, F-measure, MAP, MRR, and nDCG.
4. Select metrics according to retrieval task and user behavior.
5. Design statistically defensible offline and online experiments.
6. Interpret confidence intervals, significance tests, and effect sizes.
7. Incorporate latency, computational cost, risk, and business value into evaluation.
8. Identify ethical, governance, and reproducibility issues in IR experiments.

1. Evaluation as an Experimental Process

A retrieval evaluation should be regarded as an experiment rather than as a single score. A typical process contains five linked components:

1. Task definition: specify the user population, information need, query type, and success condition.
2. Data construction: assemble documents, queries, metadata, and relevance judgments.
3. System execution: run competing systems under controlled conditions.
4. Metric calculation: compute measures appropriate to the task.
5. Inference and decision: quantify uncertainty, assess practical importance, and decide whether the difference justifies deployment.

The unit of evaluation is commonly a query. Let Q be a set of queries, and let R(q) be the set of documents judged relevant to query q. A system returns a ranked list for each q. Evaluation must preserve this query-level structure: averaging all retrieved documents together can allow frequent queries to dominate the result and can conceal instability across queries.

A strong evaluation also distinguishes validity from reliability. Validity asks whether the experiment measures the intended user outcome. Reliability asks whether the procedure produces stable results under repeated measurement. A metric may be computed precisely while still being a poor representation of usefulness.

2. Test Collections and Relevance Judgments

2.1 Components of a test collection

A traditional test collection contains:

• a document corpus;
• a set of information needs or topics;
• one or more queries for each information need;
• relevance judgments connecting documents to topics; and
• a protocol describing retrieval, judging, and evaluation procedures.

A topic should be more informative than a short keyword string. It may include a title, a narrative describing the user’s need, and an explicit description of what counts as relevant. For example, the topic “renewable energy” is ambiguous, whereas “recent peer-reviewed evidence on offshore wind impacts on marine ecosystems” defines a more assessable need.

2.2 Binary and graded relevance

In binary relevance, a document is either relevant or non-relevant. This is appropriate when the task has a clear yes/no outcome, such as detecting whether a document contains a legally required disclosure.

In graded relevance, documents receive levels such as 0 (not relevant), 1 (partially relevant), 2 (highly relevant), and 3 (ideal). Graded judgments better represent search situations in which usefulness varies in quality, completeness, credibility, or freshness. They are essential for metrics such as normalized discounted cumulative gain (nDCG).

Relevance may be topical, situational, or utility-based. Topical relevance concerns subject matter. Situational relevance considers the user’s circumstances and task. Utility-based relevance additionally considers effort, authority, timeliness, and actionability. The chosen definition should be stated before judging begins.

2.3 Pooling and incomplete judgments

Large collections often cannot judge every document for every query. In pooling, the top results from several submitted systems are combined, duplicates are removed, and assessors judge the resulting pool. Pooling is efficient and encourages system comparison, but unjudged documents create risks. A document outside the pool may be relevant, and treating every unjudged document as non-relevant can unfairly penalize systems that retrieve novel material.

Common responses include deeper pools, random sampling, inferred evaluation, additional judging of disagreements, and metrics that distinguish unjudged from judged non-relevant documents. Collection design should also avoid allowing one highly similar family of systems to determine the pool.

2.4 Assessor agreement

When multiple assessors judge the same items, agreement provides evidence about judgment consistency. Simple percentage agreement is easy to interpret but does not account for agreement expected by chance. Cohen’s κ is commonly used for two assessors assigning categorical labels:

Here P_o is observed agreement and P_e is agreement expected under the assessors’ marginal label frequencies. κ is applicable to categorical judgments and should not be interpreted as a universal quality scale: it is affected by prevalence, label imbalance, and the number of categories.

For more than two assessors, Fleiss’ κ or related multi-rater methods may be used. For ordered grades, weighted κ gives partial credit to near agreement. Krippendorff’s α is flexible across numbers of assessors, missing values, and measurement levels. Agreement statistics should accompany, not replace, analysis of the judging guidelines and disagreement patterns.

A practical judging protocol includes assessor training, examples of borderline cases, independent judging, adjudication rules, and periodic quality checks. Assessors should not know which system produced a result where blinding is feasible.

3. Classical Effectiveness Measures

Let k be a cutoff rank. Let retrieved@k denote the first k results, and let relevant documents be defined according to the judgment protocol.

3.1 Precision and recall

Precision at k is the proportion of the first k retrieved documents that are relevant:

Recall at k is the proportion of all known relevant documents that appear in the first k results:

Precision measures result cleanliness; recall measures coverage. Precision is especially important when users inspect only a few results or when false positives are costly. Recall is important when missing a relevant item is costly, such as in legal discovery, systematic review, or safety monitoring.

Recall depends on the completeness of the relevance judgments. If only a pool has been judged, measured recall is recall against known relevant documents, not necessarily against every relevant document in the corpus.

Worked example. Suppose a system returns 10 documents, of which 6 are relevant, and the collection contains 15 judged relevant documents. Then P@10 = 6/10 = 0.60 and R@10 = 6/15 = 0.40.

3.2 F-measure

The harmonic mean combines precision and recall:

More generally, the weighted F-measure is:

P is precision, R is recall, and β > 0 controls the relative emphasis. β > 1 emphasizes recall; β < 1 emphasizes precision. The harmonic mean is appropriate when a low value in either component should substantially reduce the combined score. It is not appropriate when precision and recall have unrelated business value or when ranking position is central.

For P = 0.60 and R = 0.40, F₁ = 2(0.60)(0.40)/(1.00) = 0.48.

3.3 Reciprocal rank and MRR

For a query whose first relevant result occurs at rank r, reciprocal rank is 1/r. If no relevant result is retrieved, it is conventionally 0. Mean reciprocal rank (MRR) averages reciprocal rank over N queries:

The formula assumes rᵢ is the rank of the first relevant result for query i, with contribution zero when none is found. MRR is well suited to navigational questions, known-item search, and support queries where one satisfactory answer is sufficient. It ignores relevant results after the first.

3.4 Average precision and MAP

For a query with R(q) known relevant documents, average precision is:

Here rel(k) is 1 if the document at rank k is relevant and 0 otherwise; the sum is over ranks containing retrieved documents. If no relevant documents are known, AP requires a stated convention, often zero or exclusion from the average.

Mean average precision (MAP) is the arithmetic mean of AP over queries:

Worked example. Assume five known relevant documents exist, and a system retrieves relevant documents at ranks 1, 3, 4, 7, and 10. The precisions at those ranks are 1/1, 2/3, 3/4, 4/7, and 5/10. Therefore:

AP = (1 + 0.667 + 0.750 + 0.571 + 0.500)/5 ≈ 0.698.

MAP gives every query equal weight, regardless of the number of relevant documents. It rewards retrieving relevant documents early, but it requires binary judgments or a clearly defined conversion from graded judgments.

3.5 Discounted cumulative gain and nDCG

Discounted cumulative gain incorporates graded relevance and decreasing attention with rank. One common formulation is:

relᵢ is the relevance grade at rank i. The logarithmic discount is a modeling choice, not a natural law. Some evaluations use relᵢ rather than 2^{relᵢ} − 1; the choice should be reported.

Let IDCG@k be the DCG@k of the ideal ranking, obtained by sorting documents by decreasing relevance grade. Then:

If IDCG@k = 0 because the query has no judged relevant documents, the score requires a predefined handling rule. nDCG is between 0 and 1 when gains and discounts are non-negative, and it is useful when highly relevant results should receive more credit than marginally relevant ones.

Worked example. Consider grades [3, 2, 0] at ranks 1–3. Using the gain 2^rel − 1:

DCG@3 = 7/1 + 3/log₂3 + 0/log₂4 ≈ 7 + 1.893 = 8.893.

The ideal ordering is also [3, 2, 0], so IDCG@3 = 8.893 and nDCG@3 = 1.00. If the grades were [0, 2, 3], DCG@3 ≈ 0 + 3/1.585 + 7/2 = 5.393, while nDCG@3 ≈ 0.607.

3.6 Choosing a metric

No single metric is universally best. Metric selection should follow the task, user interface, and cost of errors. Reporting several complementary metrics is often more informative than optimizing one number.

4. Experimental Design and Statistical Inference

4.1 Offline comparison

An offline comparison should use identical queries, documents, preprocessing assumptions, and judgment sets for all systems. Queries are paired units: system A and system B are evaluated on the same query. This pairing usually improves sensitivity because query difficulty is controlled.

Report the number and source of queries, judgment completeness, metric cutoffs, parameter-tuning procedure, random seeds where relevant, and excluded cases. Tuning on the test queries creates optimistic estimates. Use separate training, development, and test collections, or use cross-validation when the data and task permit it.

4.2 Variability, confidence intervals, and significance

A mean metric alone is incomplete. Report query-level dispersion, confidence intervals, and the absolute and relative difference between systems. A paired bootstrap can resample queries with replacement, recompute the difference, and form an empirical confidence interval. A randomization or permutation test can test the null hypothesis that system labels are exchangeable across paired query outcomes.

The paired t-test may be reasonable when per-query differences are approximately suitable for its assumptions; otherwise, a Wilcoxon signed-rank test or randomization test may be preferable. Statistical significance depends on sample size and variance. Practical significance depends on whether the improvement changes user outcomes enough to justify implementation cost.

If many metrics, cutoffs, query subsets, and systems are examined, the probability of a false positive increases. Pre-specify primary outcomes where possible and control multiplicity using methods such as Holm correction or false-discovery-rate procedures.

A useful reporting pattern is: “System B improved MAP by 0.021 over System A; the 95% paired-bootstrap confidence interval for the difference was [0.008, 0.034], with a corrected p-value of 0.03.” The confidence interval communicates magnitude and uncertainty; the p-value alone does not.

4.3 Reproducibility

Reproducible evaluation requires versioned documents and judgments, stable preprocessing, accessible query definitions, deterministic configuration where possible, and complete metric definitions. Containerized execution and evaluation scripts reduce environmental variation. When data cannot be released, publish schemas, aggregate statistics, synthetic examples, and a precise description of access restrictions.

5. Online Evaluation and Experimentation

Offline evaluation cannot fully capture interaction, trust, reformulation, abandonment, or changing information needs. Online evaluation measures behavior in a live or realistic environment.

Important online measures include click-through rate, successful-session rate, query reformulation rate, abandonment, dwell time, task completion, conversion, and explicit satisfaction. Clicks are not pure relevance judgments: position bias, presentation quality, brand familiarity, and snippet attractiveness influence them. Long dwell time may indicate useful engagement or difficulty finding an answer. Metrics therefore require interpretation and, where possible, calibration against human judgments or task outcomes.

5.1 A/B testing

In an A/B test, eligible traffic is randomly assigned to a control or treatment. Randomization should occur at an appropriate unit, such as user, session, or query. User-level assignment prevents one user from receiving inconsistent experiences, while query-level assignment can increase sample size but risks contamination through repeated users.

Before launch, define the primary metric, guardrail metrics, minimum detectable effect, sample-size assumptions, stopping rule, exposure criteria, and safety rollback conditions. Monitor latency, errors, fairness indicators, and revenue-related outcomes in addition to relevance.

Early stopping whenever a favorable result appears can inflate false-positive risk. Sequential testing or a predeclared fixed horizon should be used instead. Treatment effects should be examined across meaningful segments, but subgroup analyses must be interpreted cautiously because small samples and multiple comparisons produce unstable estimates.

5.2 Interleaving

Interleaving combines results from two rankers in one user-facing list and infers preference from interactions. It can be more sensitive than a conventional A/B test for pairwise ranking comparisons and may require less traffic. However, interleaving methods can have presentation and credit-assignment biases, and they are less suitable when systems differ in more than ranking order or when outcomes extend beyond immediate clicks.

Online experiments must respect user autonomy and privacy. Users should not be exposed to materially unsafe or discriminatory retrieval merely to obtain experimental evidence. Logging should minimize personal data, enforce access controls, and define retention limits.

6. Cost-Sensitive and Business Evaluation

A retrieval improvement is not automatically a good product decision. The system may increase compute cost, latency, moderation workload, or exposure to harmful content. A decision framework should combine effectiveness with operational and economic consequences.

Let ΔV be the expected incremental value per unit of traffic, ΔC the incremental cost, and ΔR the expected risk or harm expressed in the organization’s decision framework. A simple net-value model is:

This is a decision model, not a universal accounting identity. Its terms must be defined consistently, and risk should not be reduced to money when legal, safety, or human-rights constraints require hard limits.

A confusion-cost model can be used for binary decisions. If FN and FP are false-negative and false-positive counts, and c_FN and c_FP are their respective costs, then:

The model assumes costs are sufficiently comparable and that the decision context identifies the relevant error types. In medical, legal, or safety applications, a weighted cost should supplement—not replace—minimum recall, fairness, and safety requirements.

Latency is also a business metric. A ranker with higher nDCG but unacceptable response time may reduce task completion. Evaluate quality–latency curves, infrastructure utilization, cache behavior, and cost per thousand queries. For commercial search, downstream conversion can be informative, but optimizing conversion alone may promote manipulation or reduce long-term trust.

7. Illustrative Case: Evaluating a University Digital Library Search System

Background

A university library replaces a lexical BM25 ranker with a hybrid ranker combining BM25, dense-vector retrieval, and a learning-to-rank stage. The goal is to improve discovery of scholarly articles without reducing precision for known-item searches.

Problem

Initial demonstrations show better semantic matches, but librarians report that some results are outdated or only loosely related. The library must determine whether the new system should be deployed.

Analysis

The evaluation team defines 120 topics across known-item search, exploratory literature search, and systematic-review-style discovery. Three trained assessors judge pooled results using four grades: 0 (not useful), 1 (marginal), 2 (useful), and 3 (highly useful). Ten percent of topics are double-judged to estimate agreement. The primary offline metric is nDCG@10 because ranking quality and graded usefulness matter; recall@100 is a secondary metric for discovery. MRR is reported for known-item topics.

The team separates 80 development topics from 40 held-out test topics. Neither ranking parameters nor metric selection is changed after inspecting test results. Query-level paired bootstrap intervals are used for system differences.

Approach and results

The hybrid system increases test nDCG@10 from 0.612 to 0.648 and recall@100 from 0.731 to 0.781. Its MRR on known-item topics changes from 0.842 to 0.846, a practically negligible improvement. Median latency rises from 180 ms to 265 ms. Agreement is strong for grade 0 versus non-zero but weaker in distinguishing grades 1 and 2.

A two-week controlled online experiment measures successful task completion, reformulation, latency, and librarian-reported problematic results. The hybrid system improves successful completion by 2.4%, but increases the 95th-percentile latency by 48 ms. It also produces a small increase in outdated-result complaints because document freshness was not included in the reranking features.

Solution and outcome

The library does not deploy the first hybrid version unchanged. It retains the semantic candidate generator, adds a freshness constraint for time-sensitive topics, and imposes a latency budget on reranking. A second experiment confirms the quality gain while reducing the latency increase and complaint rate. The final decision is based on both effectiveness and guardrails rather than nDCG alone.

Learning points

1. Different query classes require different metrics.
2. Offline gains may expose online costs or new failure modes.
3. Graded judgments reveal distinctions hidden by binary relevance.
4. A statistically reliable improvement may still be operationally unacceptable.
5. Evaluation should include user, infrastructure, and governance outcomes.

8. Challenges, Ethics, and Contemporary Developments

8.1 Dataset shift and temporal validity

A test collection may not represent future documents, language, users, or adversarial behavior. News and product search change especially rapidly. Temporal splits, continual evaluation, and monitoring of drift are necessary. Reusing a famous benchmark can encourage progress on the benchmark rather than on the underlying task.

8.2 Fairness and representation

Evaluation should examine whether quality differs across languages, dialects, accessibility needs, demographic contexts, and content domains. Aggregate scores can hide poor performance for smaller groups. Group analysis must avoid exposing sensitive personal data and should involve affected communities in defining usefulness and harm.

8.3 Large language models and generative retrieval

Generative systems create new evaluation concerns: factuality, citation correctness, completeness, attribution, refusal behavior, and susceptibility to prompt injection. A retrieved passage may be relevant while the generated answer is unsupported. Evaluation should therefore separate retrieval quality from answer quality and include adversarial, temporal, and out-of-distribution tests. Human preference alone is insufficient when correctness and safety are critical.

8.4 Best-practice checklist

Before accepting an evaluation, ask:

• Is the information need and relevance definition explicit?
• Are judgments sufficiently complete and consistently assigned?
• Is the test set isolated from tuning?
• Are metrics aligned with user behavior and error costs?
• Are query-level results, uncertainty, and effect sizes reported?
• Were multiple comparisons and stopping rules controlled?
• Were latency, resource cost, safety, and subgroup performance measured?
• Can another researcher reproduce the experiment?
• Are privacy, consent, data governance, and assessor welfare addressed?

Chapter Summary

Retrieval evaluation is an evidence-building process involving task definition, test-collection construction, relevance judgment, metric selection, statistical inference, and deployment monitoring. Precision and recall describe complementary aspects of binary retrieval; F-measure combines them under an explicit trade-off. MRR emphasizes the first relevant result, MAP rewards relevant documents throughout a ranked list, and nDCG handles graded relevance with rank discounting. No metric is universally adequate.

Pooling and incomplete judgments limit claims about recall, while assessor agreement reveals the reliability of relevance labels. Offline experiments should use held-out data, paired query-level analysis, confidence intervals, effect sizes, and correction for multiple comparisons. Online A/B tests and interleaving capture interaction and product outcomes but require careful randomization, guardrails, and privacy protection. Finally, decisions should incorporate latency, compute cost, error costs, business value, fairness, and safety. A system is successful when it improves meaningful user outcomes under realistic operational and ethical constraints.

Key Terms

Test collection: A corpus, topic set, relevance judgments, and evaluation protocol used for controlled retrieval experiments.

Information need: The underlying problem or goal motivating a user’s search.

Relevance judgment: An assessor’s label describing how useful a document is for a specified information need.

Binary relevance: A relevance scheme with relevant and non-relevant labels.

Graded relevance: A scheme assigning ordered levels of usefulness.

Pooling: Combining top results from multiple systems for efficient assessment.

Precision: The proportion of retrieved items that are relevant.

Recall: The proportion of known relevant items that are retrieved.

F-measure: A harmonic-mean family combining precision and recall.

Reciprocal rank: The inverse rank of the first relevant result.

MRR: Mean reciprocal rank across queries.

Average precision: The mean of precision values at ranks containing relevant documents.

MAP: Mean average precision across queries.

DCG: Discounted cumulative gain for ranked graded relevance.

nDCG: DCG normalized by the ideal ranking’s DCG.

Inter-annotator agreement: Consistency among assessors assigning judgments.

A/B test: A randomized online comparison between control and treatment experiences.

Guardrail metric: A measure that must not deteriorate beyond an acceptable limit.

Effect size: The magnitude of a difference between systems or conditions.

Cost-sensitive evaluation: Evaluation that weights errors, resources, risks, and benefits according to their consequences.

Review Questions

Short Answer Questions

1. What are the principal components of a traditional retrieval test collection?
2. Why can pooling create biased estimates of recall?
3. State the difference between precision and recall at rank k.
4. What type of retrieval task is particularly suited to MRR?
5. Why should an evaluation report confidence intervals as well as mean scores?

Long Answer Questions

1. Explain binary and graded relevance, and discuss how the choice affects metric selection.
2. Derive the logic of MAP and compare it with nDCG for ranked retrieval.
3. Discuss the design of a statistically defensible offline retrieval experiment.
4. Explain the benefits and limitations of A/B testing and interleaving.
5. Develop a framework for combining retrieval effectiveness, latency, cost, fairness, and safety in a deployment decision.

Analytical / Application Questions

1. A search system retrieves 8 results, 5 of which are relevant. There are 20 known relevant documents in the collection. Calculate P@8, R@8, and F₁, and interpret the result.
2. For two systems evaluated on the same 50 queries, propose an appropriate statistical analysis and explain how you would handle multiple metrics and cutoffs.
3. A semantic ranker improves nDCG@10 by 6% but increases 95th-percentile latency by 40%. Design an experiment and decision rule that determines whether deployment is justified.

Multiple Choice Questions with Answers

Question 1

Which metric is most directly suited to a task where the user needs one satisfactory result as early as possible?

A. Recall@100

B. MRR

C. MAP

D. F-measure

Correct Answer: B. MRR

Question 2

A system retrieves 6 relevant documents in its first 10 results. What is its precision at 10?

A. 0.40

B. 0.50

C. 0.60

D. 0.67

Correct Answer: C. 0.60

Question 3

Which measure is designed to evaluate ranked lists with graded relevance judgments?

A. nDCG

B. Binary recall only

C. Exact-match accuracy

D. Latency

Correct Answer: A. nDCG

Question 4

In average precision, precision values are summed at ranks where:

A. The document is non-relevant

B. The document is relevant

C. The rank is even

D. The query was reformulated

Correct Answer: B. The document is relevant

Question 5

What is the main purpose of normalizing DCG to obtain nDCG?

A. To remove all rank discounts

B. To compare a ranking with the ideal ranking for that query

C. To convert graded labels into binary labels

D. To estimate assessor agreement

Correct Answer: B. To compare a ranking with the ideal ranking for that query

Question 6

Cohen’s κ differs from simple percentage agreement because κ:

A. Uses ranking position as its only input

B. Accounts for agreement expected by chance

C. Can only be used with continuous measurements

D. Measures retrieval latency

Correct Answer: B. Accounts for agreement expected by chance

Question 7

Why is query-level pairing useful when comparing two retrieval systems offline?

A. It ensures every query is relevant

B. It controls for differences in query difficulty

C. It eliminates the need for relevance judgments

D. It guarantees statistical significance

Correct Answer: B. It controls for differences in query difficulty

Question 8

Which practice can inflate false-positive risk in online experimentation?

A. Predefining a stopping rule

B. Using a held-out test set

C. Stopping whenever an apparently favorable result appears

D. Reporting guardrail metrics

Correct Answer: C. Stopping whenever an apparently favorable result appears

Question 9

If false negatives cost more than false positives, which change is generally favored in a cost-sensitive evaluation, all else equal?

A. A change that improves recall even if precision falls modestly

B. A change that reduces recall to maximize precision

C. A change that ignores error counts

D. A change that measures only latency

Correct Answer: A. A change that improves recall even if precision falls modestly

Question 10

Which statement about unjudged documents in a pooled collection is correct?

A. They are always irrelevant

B. They are always highly relevant

C. Their status is unknown and treating them as non-relevant can bias evaluation

D. They should be counted as assessor disagreements automatically

Correct Answer: C. Their status is unknown and treating them as non-relevant can bias evaluation