Suppose a language model is to answer a question from this site, and a retriever must hand it the five passages most likely to help. For one of the site's 60 judged test queries, T22, the cross-encoder of this unit scores every passage of the 20 pages the site's search engine returns, and the five it scores highest all come from a single page. That page was judged fully relevant, and the five passages are each, by the model's reading, almost certainly relevant: their probabilities of relevance all round to 0.999 or 1.000. They also overlap, with cosine similarities between 0.687 and 0.852 from the unit's bi-encoder. Meanwhile the next three pages in the cross-encoder's order were all judged relevant too, at grade 2 on the scale of 0 to 3, and none of them gets a word into the context. Is a context of five passages from one page the best use of five slots?
Probably not, and the ranking that produced it did nothing wrong by its own standard. Each passage was scored alone, for its relevance to the query, and the five best scores were taken. Result diversification is the name for methods that do not score a result alone: they choose each result in view of the results already chosen, so that a list does not spend its positions saying the same thing twice and, for a query that can mean several things, does not serve only one of them.
Here is the route. First we see why ranking by each result's own relevance repeats itself, and what the Probability Ranking Principle assumed that makes it blind to repetition. Then we take the two families of methods. Maximal marginal relevance (MMR) penalizes a candidate for resembling what has been chosen; we state it, prove what its parameter does, and show that its meaning depends on the scale of the scores fed to it. Explicit diversification instead models the aspects of a query and maximizes the chance that each is covered; we prove the properties that make a greedy algorithm nearly optimal for it, and show that xQuAD is that greedy algorithm. Then comes the measure, alpha-nDCG. Finally we return to the site's five passages. The article assumes Cross-Encoder Re-ranking for the scores and Multi-Stage Ranking for the place of a re-ranking step in a pipeline. The numbers are computed by tools/experiments/neural-ranking/result-diversification.py.
Why ranking by relevance repeats itself
A ranked list sorted by score treats each candidate as if it were the only one. The Probability Ranking Principle justifies that: sorting by probability of relevance maximizes the expected number of relevant documents at every cutoff. The course article proves it, and then shows where it fails, with an ambiguous query for which 60 percent of users mean one sense and 40 percent another. The sorted order puts three documents of the majority sense first and leaves the minority with nothing until the fourth position, although a list with one document of each sense in the top two gives every user something there. The failure is in the measure the proof maximizes. An expected count does not see that the second document of the same sense adds nothing for the users the first one failed.
Chen and Karger (2006) put the same point as a design principle. In the words of their abstract, when "the user would be satisfied with some limited number of relevant documents, rather than needing all relevant documents", then "an attempt to return many relevant documents can actually reduce the chances of finding any relevant documents."
Two situations call for diversification, and they are worth keeping apart.
- Redundancy. The query is clear, but the candidates repeat each other: copies of an article, overlapping passages of one page, several summaries of one result. A second copy is relevant by any per-document standard and is still a wasted position. This is the situation of the five passages above, and of every system that fills a fixed budget with retrieved text.
- Ambiguity. The query has several readings or aspects, and the system does not know which one the user means. Here a list that covers the readings serves more users than one that goes deep on the most likely reading.
Near-identical copies have their own remedy, applied when the collection is built: near-duplicate detection finds pages that share most of their shingles and collapses them. Diversification at query time handles everything short of a copy: passages that overlap, restate, or cover one aspect of the query while another aspect goes unserved.
Maximal marginal relevance
Carbonell and Goldstein (1998) proposed the method that most later work starts from, for re-ranking retrieved documents and for choosing sentences for summaries. They called a document's value given what has already been chosen its marginal relevance: "a document has high marginal relevance if it is both relevant to the query and contains minimal similarity to previously selected documents". Their method picks the candidate of maximal marginal relevance, adds it to the selection, and repeats.
How web search answers a query states the rule and traces it on five candidates for an ambiguous query. We restate it in this unit's notation and go further: what the printed formula says, what its parameter does exactly, and what it needs of the scores it is given.
The rule, as printed and as used
Let $R$ be the candidates retrieved for query $q$, and $S \subseteq R$ the passages already selected. Let $r(p)$ be a relevance score of passage $p$ for $q$ (their $\mathrm{Sim}_1$) and $\mathrm{sim}(p, p')$ a similarity between two passages (their $\mathrm{Sim}_2$, which "can be the same as $\mathrm{Sim}_1$ or a different metric"). MMR selects next
$$p^* = \arg\max_{p \in R \setminus S} \Big[ \lambda\, r(p) - (1 - \lambda) \max_{p' \in S} \mathrm{sim}(p, p') \Big], \qquad 0 \le \lambda \le 1,$$
with the penalty taken as zero while $S$ is empty.
That is the rule as later work states it, including the course's article, and it is not quite what the paper printed. On page 335 the bracket opens after $\lambda$, so that $\lambda$ multiplies the penalty too: $\lambda\big(\mathrm{Sim}_1(D_i, Q) - (1 - \lambda) \max \mathrm{Sim}_2(D_i, D_j)\big)$. Read literally, that expression is zero for every candidate when $\lambda = 0$. The paper's own text rules the literal reading out: it says that MMR "computes incrementally the standard relevance-ranked list when the parameter $\lambda = 1$, and computes a maximal diversity ranking among the documents in $R$ when $\lambda = 0$". The form displayed above does both, and it is the reading used here.
The authors suggested settings from a small user study: "start with a small $\lambda$ (e.g. $\lambda = .3$) in order to understand the information space in the region of the query, and then to focus on the most important parts using a reformulated query (possibly via relevance feedback) and a larger value of $\lambda$ (e.g. $\lambda = .7$)". Their evidence for document re-ranking was a pilot with five users, of whom 80 percent chose MMR for a final search task; the clearer gains they report are for summaries built from several documents.
What the parameter does
Three properties follow from the definition. Each is used later.
Property 1. With $\lambda = 1$, MMR returns the candidates in order of $r$. The penalty's weight $1 - \lambda$ is zero, so each step picks the remaining candidate of largest $r$, which is the sorted order. With $\lambda = 0$ the relevance term vanishes and every choice after the first goes to the candidate least similar to the selection.
Property 2. When a near copy enters. Suppose one passage $a$ has been selected, and two candidates remain: $b$, with relevance $r_b$ and similarity $u_b$ to $a$, and $c$, with $r_c$ and $u_c$. Let $b$ be the more relevant and the more similar, $r_b > r_c$ and $u_b > u_c$: it is the near copy. MMR takes $b$ next exactly when
$$\lambda r_b - (1 - \lambda)u_b > \lambda r_c - (1 - \lambda)u_c \iff \lambda (r_b - r_c) > (1 - \lambda)(u_b - u_c) \iff \lambda > \frac{u_b - u_c}{(r_b - r_c) + (u_b - u_c)} .$$
The last step adds $\lambda(u_b - u_c)$ to both sides of the middle inequality and divides by the positive number $(r_b - r_c) + (u_b - u_c)$. The threshold depends only on two differences: how much more relevant the copy is, and how much more similar. A copy that is barely more relevant and far more similar is excluded at all but the largest $\lambda$.
Property 3. Rescaling the relevance scores is a change of $\lambda$. Multiply every relevance score by a constant $c > 0$, leaving the similarities alone. The MMR score of a candidate becomes $\lambda c\, r(p) - (1 - \lambda)\,\mathrm{pen}(p)$, where $\mathrm{pen}(p)$ is the penalty term. Dividing by the positive number $\lambda c + 1 - \lambda$ does not change which candidate is largest, and gives
$$\lambda' r(p) - (1 - \lambda')\,\mathrm{pen}(p), \qquad \lambda' = \frac{c\lambda}{c\lambda + 1 - \lambda} .$$
So MMR with scores $c\,r$ and parameter $\lambda$ makes exactly the choices of MMR with scores $r$ and parameter $\lambda'$. For $c > 1$ and $0 < \lambda < 1$, $\lambda' > \lambda$: inflating the relevance scores makes MMR less diverse. A value of $\lambda$ therefore means nothing until the scales of $r$ and $\mathrm{sim}$ are fixed. This is the opposite of the property that rank fusion proves for reciprocal rank fusion, which is unaffected by any increasing rescaling of its inputs. A cross-encoder's raw score is a logit, which on this site's candidates below runs from $-11.5$ to 9.1, while a cosine lies between $-1$ and 1. Fed to MMR beside the cosine, the logit's spread would swamp the penalty unless $\lambda$ were set close to 0. The experiment below therefore uses the logit's probability reading $\sigma(s) = 1/(1 + e^{-s})$, which lies between 0 and 1 like the cosine.
Example (four passages). Passages $a$ and $b$ are near copies, with similarity 0.95; $c$ and $e$ treat other aspects. The relevance scores are $r_a = 0.90$, $r_b = 0.88$, $r_c = 0.70$ and $r_e = 0.50$. The other similarities are $\mathrm{sim}(a, c) = \mathrm{sim}(b, c) = 0.3$, $\mathrm{sim}(a, e) = \mathrm{sim}(b, e) = 0.2$ and $\mathrm{sim}(c, e) = 0.1$. With $\lambda = 1$ the order is $a, b, c, e$, by Property 1. With $\lambda = 0.7$ it is $a, c, b, e$: after $a$ is chosen, $b$ scores $0.7 \times 0.88 - 0.3 \times 0.95 = 0.331$ and $c$ scores $0.7 \times 0.70 - 0.3 \times 0.3 = 0.400$. By Property 2 the copy $b$ beats $c$ at that step only for $\lambda > 0.65/(0.18 + 0.65) = 65/83 = 0.783$. Worked problem 1 gives every step, and worked problem 2 the change of scale.
MMR is a greedy rule
MMR makes one choice at a time and never revisits it. Each step maximizes the increment of the quantity
$$F(p_1, \dots, p_k) = \sum_{i=1}^{k} \Big[ \lambda\, r(p_i) - (1 - \lambda) \max_{j < i} \mathrm{sim}(p_i, p_j) \Big]$$
given the passages already placed, since the $i$-th term is exactly the score MMR maximizes at step $i$. That is what makes it a greedy rule, and nothing guarantees that the sequence it builds maximizes $F$ itself. The form of $F$ also shows what MMR measures: only a candidate's largest similarity to the selection counts, so a passage that restates two chosen passages pays the same penalty as one that restates one of them. The cost is small: with $n$ candidates and $k$ selections, MMR computes at most $nk$ similarities.
MMR needs no model of what the query's aspects are. It infers redundancy from similarity between results, which is why it is called implicit diversification. The other family names the aspects.
Covering the aspects of a query
Agrawal, Gollapudi, Halverson and Ieong (2009) wrote down an objective. Their setting is a query that may belong to several categories of a taxonomy, with a known distribution $P(c \mid q)$ over the categories $c$ that sums to 1. For each document $d$ and category $c$, a value $V(d \mid q, c)$ between 0 and 1 is read as the probability that $d$ satisfies a user whose intent is $c$. They assume that, given the intent, documents satisfy or fail independently: for two documents of category $c$, the probability that neither satisfies is $(1 - V(d_1 \mid q, c))(1 - V(d_2 \mid q, c))$.
Under that assumption the probability that a user with intent $c$ finds at least one satisfying document in a set $S$ is $1 - \prod_{d \in S}(1 - V(d \mid q, c))$, and averaging over intents gives their objective (their equation 1):
$$P(S \mid q) = \sum_{c} P(c \mid q) \Big( 1 - \prod_{d \in S} \big(1 - V(d \mid q, c)\big) \Big).$$
The problem Diversify($k$) is to find the set $S$ of $k$ documents that maximizes it: the probability that the average user finds at least one useful result among the $k$. The redundancy that MMR attacks by similarity is handled here by the product. Once one document has nearly satisfied a category, $\prod (1 - V)$ for that category is near zero, and a second document of the same category adds almost nothing.
No single ordering is best at every cutoff
Ranking has always produced orderings, and an ordering is best at every cutoff when the sets it puts first are best for each $k$. For Diversify that can fail. Agrawal and colleagues give the case (their Table 1): two categories of probability $\tfrac12$ each, and three documents with
| Document | $V(d \mid q, c_1)$ | $V(d \mid q, c_2)$ |
|---|---|---|
| $d_1$ | 0.8 | 0.8 |
| $d_2$ | 1.0 | 0.0 |
| $d_3$ | 0.0 | 1.0 |
One document: $d_1$ gives $\tfrac12(0.8) + \tfrac12(0.8) = 0.8$, and $d_2$ or $d_3$ gives $\tfrac12$. The best single document is $d_1$. Two documents: $\{d_2, d_3\}$ satisfies both categories for certain and gives 1, while $\{d_1, d_2\}$ gives $\tfrac12 \cdot 1 + \tfrac12 \cdot 0.8 = 0.9$, and so does $\{d_1, d_3\}$. The best pair does not contain the best single document, so no ordering puts the optimal set first at both $k = 1$ and $k = 2$.
The problem is NP-hard
Agrawal and colleagues prove that Diversify($k$) is NP-hard (their Lemma 1) by a reduction from Max Coverage: given a universe of elements, a collection of subsets of it and an integer $k$, choose $k$ subsets that together cover as many elements as possible. Max Coverage is NP-hard, as they note. The reduction is short. Make each element a category with $P(c \mid q) = 1/u$, where $u$ is the number of elements, and each subset a document with $V(d \mid q, c) = 1$ for the elements it contains and 0 otherwise. For a set $S$ of documents, a category's term $1 - \prod_{d \in S}(1 - V)$ is 1 if some document of $S$ contains the element and 0 otherwise, so
$$P(S \mid q) = \frac{\text{number of elements covered by } S}{u} .$$
A set that maximizes $P(S \mid q)$ therefore covers the most elements, and any algorithm that solves Diversify($k$) exactly solves Max Coverage. So an exact algorithm that runs in polynomial time for Diversify would give one for an NP-hard problem.
Why greedy selection is nearly optimal
The objective has a structure that makes the simplest algorithm good. Two definitions first. A set function $f$ is nondecreasing if adding an element never lowers it. It is submodular if adding an element to a smaller set gains at least as much as adding it to a larger one: for $S \subseteq T$ and $x \notin T$,
$$f(S \cup \{x\}) - f(S) \;\ge\; f(T \cup \{x\}) - f(T).$$
This is the property of diminishing returns, and Agrawal and colleagues prove that $P(S \mid q)$ has it (their Lemma 2).
Lemma (the coverage objective). $P(S \mid q)$ is nondecreasing and submodular, and $P(\emptyset \mid q) = 0$. Write $\Pi_c(S) = \prod_{d \in S}(1 - V(d \mid q, c))$, with $\Pi_c(\emptyset) = 1$. Adding $x$ multiplies $\Pi_c$ by $1 - V(x \mid q, c)$, so the gain is
$$P(S \cup \{x\} \mid q) - P(S \mid q) = \sum_c P(c \mid q)\big(\Pi_c(S) - \Pi_c(S)(1 - V(x \mid q, c))\big) = \sum_c P(c \mid q)\, V(x \mid q, c)\, \Pi_c(S).$$
Every factor is at least 0, so the gain is at least 0: the function is nondecreasing. If $S \subseteq T$, then $\Pi_c(T)$ is $\Pi_c(S)$ times the factors $1 - V(d \mid q, c)$ of the documents in $T$ but not in $S$, each between 0 and 1, so $\Pi_c(T) \le \Pi_c(S)$ for every $c$, and the gain of $x$ at $T$ is at most its gain at $S$. That is submodularity. Finally $\Pi_c(\emptyset) = 1$ makes every term of $P(\emptyset \mid q)$ zero.
The greedy algorithm starts from the empty set and, $k$ times, adds the element of largest gain. Agrawal and colleagues call it IA-Select. The guarantee that follows is due to Nemhauser, Wolsey and Fisher (1978), which Agrawal and colleagues cite as their Theorem 2. We prove the form needed here and call it the greedy bound.
Theorem (the greedy bound). Let $f$ be nondecreasing and submodular with $f(\emptyset) = 0$, let $O$ be a set of $k$ elements that maximizes $f$, and let $G_k$ be the greedy set after $k$ steps. Then
$$f(G_k) \;\ge\; \Big(1 - \big(1 - \tfrac1k\big)^k\Big) f(O) \;\ge\; \Big(1 - \frac1e\Big) f(O) .$$
Proof. Here is the idea in one sentence: at every step, the $k$ elements of $O$ together could add the whole remaining gap to the greedy set, so one of them adds at least a $k$-th of it, and the greedy choice adds at least as much.
Let $G_i$ be the greedy set after $i$ steps, $i = 0, \dots, k - 1$, and list the elements of $O$ as $o_1, \dots, o_k$. Because $f$ is nondecreasing, $f(O) \le f(G_i \cup O)$. Write $f(G_i \cup O) - f(G_i)$ as a sum of the gains from adding the $o_j$ one at a time:
$$f(G_i \cup O) - f(G_i) = \sum_{j=1}^{k} \Big[ f(G_i \cup \{o_1, \dots, o_j\}) - f(G_i \cup \{o_1, \dots, o_{j-1}\}) \Big].$$
The sum telescopes, which is why the equality holds. (A term whose $o_j$ already lies in the set before it is zero.) In the $j$-th term, $o_j$ is added to a set that contains $G_i$. By submodularity, that gain is at most the gain of adding $o_j$ to $G_i$ alone, $f(G_i \cup \{o_j\}) - f(G_i)$. The greedy step chose the element of largest gain at $G_i$, so each of those gains is at most $f(G_{i+1}) - f(G_i)$. Putting the three steps together,
$$f(O) - f(G_i) \;\le\; k\,\big(f(G_{i+1}) - f(G_i)\big).$$
Write $\delta_i = f(O) - f(G_i)$ for the remaining gap. The inequality says $\delta_i \le k(\delta_i - \delta_{i+1})$, that is, $\delta_{i+1} \le (1 - \tfrac1k)\,\delta_i$. Applying it for $i = 0, \dots, k - 1$ and using $\delta_0 = f(O) - f(\emptyset) = f(O)$ gives $\delta_k \le (1 - \tfrac1k)^k f(O)$, which is the first inequality. For the second, $1 - x \le e^{-x}$ for every real $x$, so $(1 - \tfrac1k)^k \le e^{-1}$. $\square$
All three assumptions were used: monotonicity to start from $f(O) \le f(G_i \cup O)$, submodularity to compare each gain with its gain at $G_i$, and $f(\emptyset) = 0$ to set $\delta_0 = f(O)$. The lemma gives all three for $P(S \mid q)$, so greedy selection reaches at least $1 - 1/e \approx 0.632$ of the best attainable probability that a user finds something. At $k = 3$ the bound is $1 - (2/3)^3 = 19/27 \approx 0.704$.
The bound is a guarantee for the worst case and is usually far from tight. On the three-document example the greedy algorithm first takes $d_1$, the best single document, and then $d_2$ (it ties with $d_3$, each adding $\tfrac12 \cdot 1 \cdot 0.2 = 0.1$), for a value of 0.9 against the optimum of 1: a ratio of 0.9, above the bound of $1 - (1/2)^2 = 0.75$ for $k = 2$. Over random instances (eight documents, four categories, $k = 3$; twenty instances for each of the seeds 0 to 29), the script finds the worst ratio of each seed to have a median of 0.977, and the worst over all 600 instances is 0.911, against the bound of 0.704. The same run checks the lemma's two inequalities on 5,974 random pairs of nested sets, in exact arithmetic, with no exception. Agrawal and colleagues also prove that the greedy choice is optimal when every document belongs to a single category (their Theorem 1).
One detail of their algorithm deserves a remark. IA-Select keeps, for each category, a weight $U(c \mid q, S)$ that starts at $P(c \mid q)$ and is multiplied by $1 - V(d \mid q, c)$ when $d$ is selected (line 9 of their Algorithm 1), and it chooses the document maximizing $\sum_c U(c \mid q, S)\, V(d \mid q, c)$. The paper describes $U$ as a conditional probability, but the update as printed does not renormalize it, so $U(c \mid q, S) = P(c \mid q)\,\Pi_c(S)$. The quantity it maximizes is therefore exactly the gain computed in the proof of the lemma. Renormalizing would divide every candidate's value by the same number and change no choice.
xQuAD is the same greedy step, mixed with relevance
Santos, Macdonald and Ounis (2010) derived xQuAD (explicit query aspect diversification) from a probabilistic model in which an ambiguous query is represented by sub-queries $q_1, q_2, \dots$, obtained in their experiments from the official sub-topics of the test collection and from the query reformulations that three web search engines suggest. Its selection step chooses the document maximizing
$$(1 - \lambda)\, P(d \mid q) + \lambda \sum_i P(q_i \mid q)\, P(d \mid q_i) \prod_{d_j \in S} \big(1 - P(d_j \mid q_i)\big).$$
The first term is relevance to the query. The second, as the authors derive it, is the probability that $d$ satisfies a sub-query that the documents already in $S$ have not satisfied, under the assumption that documents are relevant to a sub-query independently. Two things should be noticed.
The diversity term is the coverage gain. Put $c = q_i$, $P(c \mid q) = P(q_i \mid q)$ and $V(d \mid q, c) = P(d \mid q_i)$. Then the second term is exactly $\sum_c P(c \mid q)\, V(d \mid q, c)\, \Pi_c(S)$, the gain of adding $d$ to $S$ under the objective of Agrawal and colleagues, derived in the lemma. The script checks the identity in exact arithmetic on 600 random cases. So xQuAD's step is the greedy step for the objective
$$(1 - \lambda) \sum_{d \in S} P(d \mid q) + \lambda\, P(S \mid q),$$
and this objective is itself nondecreasing and submodular with value 0 at the empty set. The first part is a sum of nonnegative numbers, one for each element of $S$, whose gain from adding $x$ is $P(x \mid q)$ whatever $S$ is: nondecreasing, and submodular with equality. A sum of such a function and $P(S \mid q)$, with nonnegative weights, keeps both inequalities, since each of them adds. The greedy bound therefore applies to xQuAD as well: its greedy selection reaches at least $1 - 1/e$ of the best value of the mixed objective, as long as its estimates lie between 0 and 1 and $\lambda$ lies between 0 and 1, whatever their accuracy. (An estimate above 1 could make a product $\Pi_c(S)$ negative, and a later gain could then be negative.)
Its $\lambda$ points the other way. In xQuAD, $\lambda$ weights the diversity term; in MMR it weights relevance. With the sub-topics of the test collection used as sub-queries, the authors found the best results "around 0.15" for two of their three baseline rankers (their Figure 2). On the diversity task of the TREC 2009 Web track, with the official sub-topics as sub-queries, xQuAD was in the authors' words "the only approach that consistently improves the initial baseline ranking provided by BM25, DPH, and LM, with gains of up to 30% (BM25, α-NDCG@5)", against MMR and simulated versions of two explicit methods; the one exception was one measure on the DPH ranking, where no method's difference from the baseline was significant (their §6.1 and Table 2). With the reformulations of real search engines in place of the official sub-topics, the gains were smaller but present in most settings (their Table 3).
The difference between the two families is now precise. MMR needs a similarity between results and no model of the query. Explicit methods need a list of aspects and an estimate of how well each document serves each, and in return they optimize a stated objective with a proved guarantee for the greedy step.
Measuring a diverse list: alpha-nDCG
nDCG scores each position by the grade of the document there, whatever came before, so it rewards the repetitive list as much as the diverse one. Clarke and colleagues (2008) changed the gain. They treat what a document can contain as a set of nuggets $n_1, \dots, n_m$ (aspects, facts, answers), with $J(d, i) = 1$ if the assessor judged that $d$ contains nugget $n_i$. A nugget already seen is worth less each time it reappears: with $r_{i,k-1}$ the number of documents at ranks 1 to $k - 1$ that contain $n_i$, the gain of the document at rank $k$ is
$$G[k] = \sum_{i=1}^{m} J(d_k, i)\,(1 - \alpha)^{r_{i,k-1}}$$
(their equation 7). In their model $\alpha$ is the probability that a nugget the assessor judged present is really there, a constant that "reflects the possibility of assessor error", so $(1 - \alpha)^{r_{i,k-1}}$ is the probability that none of the $r_{i,k-1}$ earlier documents judged to contain $n_i$ actually does. The discounted sum $\sum_k G[k]/\log_2(1 + k)$ is divided by the same sum for an ideal ordering, as in nDCG. With $\alpha = 0$ the measure counts nuggets without regard to repetition. The larger $\alpha$, the less a repeated nugget is worth.
The ideal ordering is the hard part. Clarke and colleagues show that computing it is NP-complete, by reducing minimum vertex cover to it: each vertex becomes a document, each edge a nugget contained in its two endpoints' documents. In practice they compute an approximation to it greedily, placing at each rank the document of largest gain. The paper states that this is exact when no ties occur; that is not so in general. With $\alpha = \tfrac12$ and cutoff 4, six documents with nuggets $\{1,2,4,7\}$, $\{0,3,5\}$, $\{3,4,5,6,7\}$, $\{1,7,8\}$, $\{0,1,2,4,6,7,8\}$ and $\{0,1,4,5\}$ give the greedy order a unique maximum at every rank and a DCG@4 of 10.568, while the best of all orderings reaches 10.604 (the script enumerates them). So a ranking can in principle score above the greedy ideal; the paper's rule for that unusual case is that such a system "would be credited with an ideal result". Santos and colleagues computed it with $\alpha = 0.5$, following the standard practice of the TREC 2009 Web track.
Example (two orderings of three documents). Documents $a$ and $b$ each contain nuggets 1 and 2; $c$ contains nuggets 3 and 4. With $\alpha = \tfrac12$, the ordering $a, b, c$ has gains $2$, $\tfrac12 + \tfrac12 = 1$ and $2$, and DCG@3 $= 2/1 + 1/\log_2 3 + 2/2 = 3.631$. The ordering $a, c, b$ has gains $2$, $2$ and $1$, and DCG@3 $= 2 + 2/\log_2 3 + 1/2 = 3.762$, which is the ideal. So alpha-nDCG@3 is 0.965 for the first ordering and 1 for the second. With $\alpha = 0$ both orderings have gains $2, 2, 2$ and both score 1. Worked problem 4 does the arithmetic in full.
The five passages: diversification on this site
The opening context was one query's. Here the same construction is measured on all 60 topical queries.
The candidates. For each query, the passages of the pages that the site's ranker, BM25F, puts in its top 20. Each passage is scored by the cross-encoder of the first article of this unit, and its relevance is the probability reading $\sigma(s)$ of the logit $s$. The similarity between two passages is the cosine of their vectors from the unit 1 bi-encoder (Sentence and Passage Encoders). MMR runs over each query's 60 best passages by cross-encoder score; passages below those are not considered.
The selections. Five passages, by: the top five by cross-encoder score (MMR with $\lambda = 1$); MMR with $\lambda$ from 0.9 down to 0.5; and a simple rule that takes the best passage of each page, in order of score, until five are taken.
The measures. The number of distinct pages among the five; the number of those pages that the judges graded relevant, an average grade of 2 or more on the scale of 0 to 3; the mean cosine between the five passages; and their mean $\sigma(s)$. The judgments are of pages, not passages. They come from the site's evaluation set as it stood at commit c057efe: on 13 November 2026 the site's ranker's top 20 pages for each query were pooled, 1,200 pairs, and a model judge (Claude Sonnet 5.5) graded 1,199 of them, with a quadratic-weighted kappa of 0.85 against the owner on 150 calibration pairs, on which the owner's and a second, full-read model grading are averaged in. At that commit the pool's record named only that ranker; the pool has since been re-drawn and extended to other rankers, and all its pairs judged, but the numbers here use the judgments as they stood then, on purpose. Cross-Encoder Re-ranking describes the judgments in full. Of the 1,200 query-page pairs among the candidates, 1,151 have a judgment at that commit and 49 do not, and those count as not relevant: 48 entered BM25F's top 20 after the pooling, as pages changed, and one was in the pool but never judged. A passage of a relevant page need not itself be relevant, so the second measure counts relevant pages the context draws on, not relevant passages.
Means over the 60 queries:
| Selection of five passages | Distinct pages | Relevant pages | Mean cosine | Mean $\sigma(s)$ |
|---|---|---|---|---|
| Top five by score ($\lambda = 1$) | 2.92 | 2.10 | 0.604 | 0.953 |
| MMR, $\lambda = 0.9$ | 3.37 | 2.22 | 0.527 | 0.952 |
| MMR, $\lambda = 0.8$ | 3.47 | 2.22 | 0.502 | 0.948 |
| MMR, $\lambda = 0.7$ | 3.55 | 2.23 | 0.486 | 0.944 |
| MMR, $\lambda = 0.6$ | 3.60 | 2.27 | 0.473 | 0.938 |
| MMR, $\lambda = 0.5$ | 3.72 | 2.27 | 0.459 | 0.930 |
| Best passage of each page | 5.00 | 3.00 | 0.547 | 0.911 |
The top five repeat themselves. Ranked by score alone, the five passages come from 2.92 pages on average. For 10 of the 60 queries all five come from a single page, and for 20 from at most two. That is not because the pages are wrong: every one of those ten single pages was graded 3, fully relevant. A relevant page can contain several passages that the cross-encoder scores near the top, plausibly because they share the page's subject and vocabulary, and a ranking that scores each passage alone takes them all.
MMR spreads the context, slowly. Lowering $\lambda$ from 1 to 0.5 raises the number of distinct pages from 2.92 to 3.72 and lowers the mean cosine between the chosen passages from 0.604 to 0.459, at a cost of 0.023 in mean $\sigma(s)$. The number of relevant pages rises from 2.10 to 2.27, and that rise is within what chance would produce: at $\lambda = 0.7$ the difference from the top five is $+0.13$ relevant pages ($t = 1.13$, $p = 0.26$; more on 14 queries, fewer on 7, the same on 39), and at $\lambda = 0.5$ it is $+0.17$ ($p = 0.22$). Two features of the scores are visible, and neither was tested as a cause. Near the top, $\sigma(s)$ is close to 1 for many passages (on the ten single-page queries the top five's probabilities lie between 0.947 and 1.000), so the relevance term barely separates them and the penalty decides; that fits the jump between $\lambda = 1$ and $\lambda = 0.9$. And the penalty measures similarity of content, not identity of page, as the cap rule below shows, which fits the slow progress after it. Property 3 shows, for a change of scale by a constant, what holds more generally: what $\lambda$ means depends on the scale on which relevance is given.
The simplest rule did most. Taking the best passage of each page, in order of score, gives five pages by construction, and 3.00 relevant pages, 0.90 more than the top five ($t = 7.62$, $p < 0.001$). It was never worse: more relevant pages on 35 queries and the same number on 25. That is not luck, and the reason is short enough to prove.
Proposition (the page cap never covers fewer pages). Order the pages by their best passage's score. The pages represented among the top $k$ passages are the first $m$ pages of that order, for some $m \le k$, and the cap rule's pages are the first $k$. So every page in the top $k$ passages is also among the cap rule's pages, and any count of relevant pages can only rise. Proof. Let page $X$ have a passage among the top $k$, and let page $Y$'s best passage score above $X$'s best passage. Then it scores above $X$'s passage in the top $k$ (which is at most $X$'s best), so it is itself among the top $k$, and $Y$ is represented too. The represented pages are therefore closed under "comes earlier in the order", which makes them the first $m$ pages, and $m \le k$ because $k$ passages cannot come from more than $k$ pages. (Ties in score are broken by the same fixed order in both rules.) $\square$
Two costs come with the cap. Its passages have the lowest mean $\sigma(s)$ of all the selections, 0.911, because it passes over a page's second and third passages, which may score higher than another page's best. And its mean cosine, 0.547, is higher than MMR's at every $\lambda$ below 1: distinct pages are not distinct content, and on a site whose pages discuss related papers and courses, passages of different pages can say similar things. MMR measures that similarity and the cap does not see it.
What this shows and what it does not. On these 60 queries, a context of five passages chosen by score alone drew on fewer than three pages on average and often on one; diversification by MMR made the passages less similar to each other without a measurable change in the number of relevant pages; and a cap of one passage per page raised that number by about one page per query, never lowering it, at some cost in the passages' own scores. Whether a language model answers better from the capped or the diversified context is a different measurement, of answers and not of pages, and belongs to the next unit. The judgments here grade pages and know nothing of passages, so "relevant page" is a coarse proxy for what a reader would find useful in the context.
What is proved here, what is cited, and what the experiment shows
Proved on the page. That MMR with $\lambda = 1$ is the relevance order; the threshold of $\lambda$ at which a near copy enters; that multiplying the relevance scores by $c$ is the same as replacing $\lambda$ by $c\lambda/(c\lambda + 1 - \lambda)$; that MMR is greedy for the sequential objective $F$; that the coverage objective of Agrawal and colleagues is nondecreasing and submodular with value 0 at the empty set; the reduction from Max Coverage that makes Diversify($k$) NP-hard (given that Max Coverage is); the greedy bound $1 - (1 - 1/k)^k \ge 1 - 1/e$ for every nondecreasing submodular function with value 0 at the empty set; that IA-Select's weight equals the marginal gain; that xQuAD's diversity term is the marginal gain of the coverage objective, and that its mixed objective satisfies the conditions of the greedy bound; that a cap of one passage per page never covers fewer pages than the top passages by score.
Cited. The MMR rule, its intended settings and its user study (Carbonell and Goldstein, 1998); the coverage objective, its example of non-nested optimal sets, its NP-hardness proof and the optimality of IA-Select for single-category documents (Agrawal et al., 2009); the greedy bound's origin (Nemhauser, Wolsey and Fisher, 1978, through Agrawal et al.'s citation); xQuAD's derivation and every result of its experiments (Santos, Macdonald and Ounis, 2010); alpha-nDCG, its gain, its NP-completeness and its greedy ideal (Clarke et al., 2008); the principle that many relevant documents can lower the chance of finding one (Chen and Karger, 2006).
Shown by the experiment. On this site's 60 topical queries, with one cross-encoder and one bi-encoder: a context of the five passages with the highest scores drew on 2.92 pages on average, and on a single page for 10 of the queries; MMR raised the number of pages (3.55 at $\lambda = 0.7$) and lowered the passages' similarity to each other, with no measurable change in the number of pages judged relevant; and a cap of one passage per page raised that number from 2.10 to 3.00, never lowering it, as the proposition proved it could not. These are observations about context building from one ranker's candidates. They say nothing about whether a diversified list would serve the site's readers better as a results page, which no judgment set here measures.
Worked problems
These problems are posed on the article's small exact examples; the unit has no course assignments. The script recomputes every number in exact arithmetic.
Problem 1 (MMR step by step). Run MMR with $\lambda = 0.7$ on the four passages of the example: $r_a = 0.90$, $r_b = 0.88$, $r_c = 0.70$, $r_e = 0.50$; $\mathrm{sim}(a, b) = 0.95$, $\mathrm{sim}(a, c) = \mathrm{sim}(b, c) = 0.3$, $\mathrm{sim}(a, e) = \mathrm{sim}(b, e) = 0.2$, $\mathrm{sim}(c, e) = 0.1$. Give every score.
Solution. Each score is $0.7\,r - 0.3 \times (\text{largest similarity to a chosen passage})$.
| Candidate | Step 1 | Step 2 | Step 3 | Step 4 |
|---|---|---|---|---|
| $a$ | 0.630 | chosen | chosen | chosen |
| $b$ | 0.616 | 0.331 | 0.331 | chosen |
| $c$ | 0.490 | 0.400 | chosen | chosen |
| $e$ | 0.350 | 0.290 | 0.290 | 0.290 |
- Nothing is chosen, so each score is $0.7\,r$: $a$ wins with 0.630, though the near copy $b$ is close at 0.616.
- Against $a$: $b$ pays $0.3 \times 0.95 = 0.285$ and falls to 0.331; $c$ pays $0.3 \times 0.3 = 0.09$ and has 0.400; $e$ pays 0.06 and has 0.290. $c$ wins.
- Now $b$'s largest similarity to the chosen passages is still 0.95 (to $a$), so its score stays 0.331; $e$'s largest is $\max(0.2, 0.1) = 0.2$, so it stays 0.290. $b$ wins.
- $e$ is last.
The order is $a, c, b, e$. The near copy is postponed by one position, not removed: at this $\lambda$ it is still more useful than $e$. By Property 2 it would have beaten $c$ at step 2 for any $\lambda > 65/83 \approx 0.783$; it would then also have beaten $e$, since $0.88\lambda - 0.95(1 - \lambda) > 0.5\lambda - 0.2(1 - \lambda)$ holds for $\lambda > 75/113 \approx 0.664$, so above 0.783 it is placed second.
Problem 2 (a change of scale is a change of $\lambda$). Run MMR with $\lambda = \tfrac12$ on the same passages, first with the relevance scores as given and then with every relevance score doubled. Which $\lambda$ on the original scores reproduces the second run?
Solution. With the original scores, step 1 picks $a$ ($0.5 \times 0.9 = 0.45$). At step 2 the scores are $b$: $0.44 - 0.475 = -0.035$, $c$: $0.35 - 0.15 = 0.20$, $e$: $0.25 - 0.10 = 0.15$, so $c$. At step 3, $b$ still has $-0.035$ and $e$ has $0.25 - 0.5 \times 0.2 = 0.15$, so $e$, and the order is $a, c, e, b$. With doubled scores, step 1 again picks $a$ (0.90 against 0.88 for $b$), step 2 gives $c$ $0.70 - 0.15 = 0.55$, $b$ $0.88 - 0.475 = 0.405$ and $e$ $0.50 - 0.10 = 0.40$, so $c$, and step 3 compares $b$: $0.88 - 0.475 = 0.405$ with $e$: $0.50 - 0.10 = 0.40$, so $b$ comes third and the order is $a, c, b, e$. By Property 3 with $c = 2$, the doubled run equals MMR on the original scores with $\lambda' = 2 \cdot \tfrac12 / (2 \cdot \tfrac12 + \tfrac12) = \tfrac23$. Check at step 3 with $\lambda' = \tfrac23$: $b$ scores $\tfrac23 \times 0.88 - \tfrac13 \times 0.95 = 0.27$ and $e$ scores $\tfrac23 \times 0.5 - \tfrac13 \times 0.2 = 0.2\overline{6}$, so $b$ again comes third. Each of these scores is the doubled run's score divided by $1.5$, as the proof of Property 3 says.
Problem 3 (the coverage example). For the three documents of Agrawal and colleagues' Table 1, with $P(c_1 \mid q) = P(c_2 \mid q) = \tfrac12$, compute $P(S \mid q)$ for every set of one or two documents, the greedy selection with IA-Select's weights, and the ratio of the greedy value to the optimum. Compare it with the greedy bound.
Solution. Single documents: $d_1$ gives $\tfrac12(0.8) + \tfrac12(0.8) = 0.8$; $d_2$ gives $\tfrac12(1) + \tfrac12(0) = 0.5$; $d_3$ gives 0.5. Pairs: $\{d_1, d_2\}$ gives $\tfrac12\big(1 - 0.2 \times 0\big) + \tfrac12\big(1 - 0.2 \times 1\big) = 0.5 + 0.4 = 0.9$; $\{d_1, d_3\}$ gives 0.9 by symmetry; $\{d_2, d_3\}$ gives $\tfrac12(1) + \tfrac12(1) = 1$. Greedy: the weights start at $U(c_1) = U(c_2) = \tfrac12$, and the first choice maximizes $\sum_c U(c)\,V(d \mid c)$, which is 0.8 for $d_1$ and 0.5 for the others: $d_1$. The weights become $U(c_1) = U(c_2) = \tfrac12 \times (1 - 0.8) = 0.1$. Now $d_2$ gains $0.1 \times 1 + 0.1 \times 0 = 0.1$ and $d_3$ gains the same; the tie goes to $d_2$. The greedy pair has value $0.8 + 0.1 = 0.9$, and the optimum is 1, a ratio of 0.9. The greedy bound with $k = 2$ guarantees $1 - (1 - \tfrac12)^2 = 0.75$, which holds with room to spare. The greedy algorithm's first choice was optimal for $k = 1$ and committed it to a pair that is not optimal for $k = 2$; no ordering can be optimal at both.
Problem 4 (alpha-nDCG by hand). Documents $a$ and $b$ contain nuggets 1 and 2, $c$ contains nuggets 3 and 4, and $e$ contains none. Compute alpha-nDCG@3 for the orderings $a, b, c$ and $a, c, b$ with $\alpha = \tfrac12$ and with $\alpha = 0$.
Solution. With $\alpha = \tfrac12$. Ordering $a, b, c$: $a$ brings two new nuggets, $G[1] = 2$; $b$'s nuggets have each been seen once, $G[2] = 2 \times \tfrac12 = 1$; $c$'s are new, $G[3] = 2$. DCG@3 $= 2/\log_2 2 + 1/\log_2 3 + 2/\log_2 4 = 2 + 0.631 + 1 = 3.631$. Ordering $a, c, b$: $G = 2, 2, 1$ and DCG@3 $= 2 + 2/\log_2 3 + 1/2 = 2 + 1.262 + 0.5 = 3.762$. The greedy ideal places at each rank the document with the largest gain: $a$ (2, tied with $b$ and $c$, the tie going to the first listed), then $c$ (2, against 1 for $b$), then $b$ (1, against 0 for $e$), which is the second ordering, so IDCG@3 $= 3.762$. Alpha-nDCG@3 is $3.631/3.762 = 0.965$ for $a, b, c$ and 1 for $a, c, b$. With $\alpha = 0$ every gain is 2, both orderings have DCG@3 $= 2 + 1.262 + 1 = 4.262$, and both score 1: without the discount for repetition, the measure cannot tell them apart.
Problem 5 (xQuAD by hand). A query has two sub-queries with $P(q_1 \mid q) = 0.7$ and $P(q_2 \mid q) = 0.3$. One document $x$ has been selected, with $P(x \mid q_1) = 0.9$ and $P(x \mid q_2) = 0.1$. Two candidates remain: $y$ with $P(y \mid q) = 0.6$, $P(y \mid q_1) = 0.8$, $P(y \mid q_2) = 0.2$; and $z$ with $P(z \mid q) = 0.4$, $P(z \mid q_1) = 0.1$, $P(z \mid q_2) = 0.9$. Which does xQuAD choose with $\lambda = \tfrac12$, and for which $\lambda$ does the choice change? Check that each diversity term is a coverage gain.
Solution. The factors $1 - P(x \mid q_i)$ are 0.1 for $q_1$ and 0.9 for $q_2$: the first sub-query is nearly served. The diversity terms are, for $y$, $0.7 \times 0.8 \times 0.1 + 0.3 \times 0.2 \times 0.9 = 0.056 + 0.054 = 0.110$, and for $z$, $0.7 \times 0.1 \times 0.1 + 0.3 \times 0.9 \times 0.9 = 0.007 + 0.243 = 0.250$. With $\lambda = \tfrac12$ the scores are $0.5 \times 0.6 + 0.5 \times 0.110 = 0.355$ for $y$ and $0.5 \times 0.4 + 0.5 \times 0.250 = 0.325$ for $z$, so $y$, the more relevant document, is chosen. $z$ wins when $(1 - \lambda)\,0.4 + \lambda\,0.25 > (1 - \lambda)\,0.6 + \lambda\,0.11$, that is, $0.14\lambda > 0.2(1 - \lambda)$, or $\lambda > 0.2/0.34 = 10/17 \approx 0.588$. For the coverage check, $P(\{x\} \mid q) = 0.7 \times 0.9 + 0.3 \times 0.1 = 0.66$ and $P(\{x, y\} \mid q) = 0.7(1 - 0.1 \times 0.2) + 0.3(1 - 0.9 \times 0.8) = 0.686 + 0.084 = 0.770$, a gain of 0.110, the diversity term of $y$. The script checks both gains in exact arithmetic.
What we have learned
A list ranked by each result's own relevance is optimal for the expected number of relevant results and blind to repetition, and two families of methods repair that. MMR subtracts from each candidate's relevance its largest similarity to what has been chosen. Its parameter has an exact threshold at which a near copy re-enters, and it is not scale-free: inflating the relevance scores by a factor $c$ is the same as moving $\lambda$ toward 1, so the scores must be put on a known scale first. Explicit diversification states an objective, the probability that a user of some intent finds at least one satisfying result. That objective is nondecreasing and submodular, maximizing it exactly is NP-hard, and greedy selection, which is what IA-Select and xQuAD do, reaches at least $1 - 1/e$ of the optimum. Alpha-nDCG scores a list with a gain that shrinks for each repetition of a nugget. On this site, the five passages a cross-encoder scored highest came from fewer than three pages on average; MMR spread them over more pages without a measurable gain in relevant pages, and a cap of one passage per page covered about one more relevant page per query, and provably never fewer.
The reason for caring about five passages was the reader at the end of the pipeline. When the reader is a language model, the selected passages become its context, and what it does with them is the subject of the next unit, Retrieval-Augmented Generation.
References
- Agrawal, R., Gollapudi, S., Halverson, A., and Ieong, S. (2009). Diversifying search results. In Proceedings of the Second ACM International Conference on Web Search and Data Mining (WSDM 2009), 5–14. record
- Carbonell, J., and Goldstein, J. (1998). The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proceedings of SIGIR 1998, 335–336. record · 4 pages
- Chen, H., and Karger, D. R. (2006). Less is more: Probabilistic models for retrieving fewer relevant documents. In Proceedings of SIGIR 2006, 429–436. record
- Clarke, C. L. A., Kolla, M., Cormack, G. V., Vechtomova, O., Ashkan, A., Büttcher, S., and MacKinnon, I. (2008). Novelty and diversity in information retrieval evaluation. In Proceedings of SIGIR 2008, 659–666. record
- Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions, I. Mathematical Programming, 14(1), 265–294. record
- Santos, R. L. T., Macdonald, C., and Ounis, I. (2010). Exploiting query reformulations for web search result diversification. In Proceedings of the 19th International Conference on World Wide Web (WWW 2010), 881–890. record