Diversity-Aware Ranking and Subtopics

A query like “mercury” has at least four defensible meanings, and a ranking that puts the ten best pages about the planet above everything else is a failure for the reader who meant the element. The standard response is to return a set that covers several interpretations rather than maximizing relevance for the most likely one, and the cost is that the top of the list contains documents that are individually less relevant than the ones it displaced.

The objective that relevance ranking cannot express

A relevance ranker scores each document against the query and sorts. Its implicit assumption is that the value of a result is independent of the other results, so the optimal list is the top-$k$ of a fixed ordering. For an ambiguous query the assumption is false: the second-best page about the planet adds almost nothing once the best page about the planet is already shown, while a mediocre page about the element adds a great deal.

Making that concrete requires a notion of subtopic. The usual construction derives subtopics from the query’s own ambiguity: a set of aspect terms or intents, each associated with a probability that the user meant it. A document’s coverage is then the set of subtopics it addresses, and the value of a list depends on how many distinct subtopics it covers weighted by their probabilities.

This is the structure that the portfolio analogy formalizes. Treating documents as assets with expected relevance and pairwise redundancy as covariance, the problem of maximizing expected value subject to a variance constraint has the same shape as list construction under a diversity requirement. The mapping is not exact, since a ranked list is not a portfolio and the order within the list matters, but the analogy produces the right objective function.

Maximal marginal relevance and its greedy solution

MMR scores each candidate at each step by a combination of its relevance to the query and its dissimilarity from what has already been selected:

$$\text{MMR}(d) = \lambda \cdot \text{rel}(d, q) - (1 - \lambda) \max_{d’ \in S} \text{sim}(d, d’)$$

where $S$ is the set already chosen, $\lambda \in [0,1]$ trades relevance against novelty, and the similarity is usually a cosine over document vectors. At $\lambda = 1$ the rule is plain relevance ranking. At $\lambda = 0$ it selects the most dissimilar document from the set each time, ignoring the query entirely.

The greedy selection is not optimal. Choosing the highest-MMR document at each step can produce a list that a different sequence would beat, because the marginal value of a document depends on the whole set and the greedy choice forecloses options. The problem is a submodular maximization: the coverage objective has diminishing returns, and greedy is the standard approximation with a known guarantee of at least $1 - 1/e$ of the optimum for monotone submodular functions, which is the classical result from the maximization literature. The guarantee is over set coverage, not over the ordering, and it says nothing about the quality of the first result, which is the one most readers see.

def mmr(candidates, rel, sim, k, lam=0.7):
    """candidates: ids; rel: id -> relevance; sim: (id,id) -> similarity."""
    selected, rest = [], list(candidates)
    while rest and len(selected) < k:
        best, best_score = None, float("-inf")
        for d in rest:
            redundancy = max((sim(d, s) for s in selected), default=0.0)
            score = lam * rel[d] - (1.0 - lam) * redundancy
            if score > best_score:
                best, best_score = d, score
        selected.append(best)
        rest.remove(best)
    return selected

The loop is $O(k \cdot n \cdot k)$ similarity evaluations if the redundancy is recomputed each time, which is why implementations precompute the candidate-to-candidate similarity matrix for the reranked window. For a window of a few hundred candidates the matrix is tens of thousands of entries, which is manageable; over the full candidate set it is not, and this is the reason diversification is a reranking step rather than a first-stage operation.

Explicit subtopic coverage instead of pairwise dissimilarity

MMR’s redundancy term is a proxy. Two documents can be dissimilar in wording while covering the same subtopic, and similar in wording while covering different ones. A page about mercury the element and a page about mercury in fish will share a lot of vocabulary and little information.

The alternative scores a list by explicit subtopic coverage. If subtopic $s$ has probability $p_s$ and a document covers a set of subtopics $C(d)$, the expected utility of a list is something like

$$U(L) = \sum_{s} p_s \cdot \left(1 - \prod_{d \in L} (1 - r_{d,s})\right)$$

where $r_{d,s}$ is the probability that a reader interested in subtopic $s$ is satisfied by document $d$. The product form says that the list fails a subtopic only if every document in it fails that subtopic, which is the right semantics for “did the list answer this interpretation”.

This objective is monotone and submodular, so greedy selection again carries the $1 - 1/e$ guarantee, and the marginal gain of adding document $d$ to list $L$ has a closed form: the increase in coverage summed over subtopics, weighted by probability. The difficulty moves entirely into estimating $p_s$ and $r_{d,s}$, which requires either a subtopic classifier or a clustering of the candidate set into aspects.

The clustering route is common because it needs no labels: embed the candidates, cluster them, treat each cluster as an aspect, and use cluster membership as coverage. The number of clusters is a parameter, and it determines whether the aspects are coarse enough to be meaningful or fine enough to be redundant. A clustering that splits “mercury the planet” into “mercury the planet’s orbit” and “mercury the planet’s composition” will diversify within an interpretation rather than across interpretations.

The relevance cost and how to measure it

Diversification always lowers a pure relevance metric. If NDCG is computed against a single set of judgments for the query, reordering to cover subtopics moves less-relevant documents upward and NDCG drops. This is not a bug; it is the metric measuring something the objective deliberately trades away.

Metrics that account for this need per-subtopic judgments. The standard construction weights each subtopic’s NDCG by its probability and combines them: a document that is highly relevant to a rare interpretation contributes less than one relevant to a common interpretation, but a document covering several interpretations contributes to several. With such a metric, a diversified list can score higher than a relevance-maximizing one, which is the point.

Without per-subtopic judgments, the honest comparison is between two systems on the same aggregate metric, accepting that the diversified system is being penalized for something the metric does not model. A common compromise is to report both the aggregate relevance metric and a coverage statistic, the fraction of subtopics with at least one result in the top ten, and treat them as a two-dimensional outcome rather than collapsing to one number.

The interaction with thresholds and confidence

Diversification makes a hidden assumption: that the query is ambiguous. Applying it to an unambiguous query wastes positions on results the reader does not want. “mercury planet radius” has one interpretation, and a diversified list for it puts pages about the element in the top ten, which is worse than useless.

The decision to diversify must therefore be conditioned on ambiguity, and ambiguity is estimated from the query or from the candidate set. The candidate-set signal is the more reliable one: if the top fifty documents cluster into clearly separated groups with similar aggregate scores, the query is ambiguous in practice. If they form one cluster, it is not. This is why diversification is usually gated on a confidence estimate rather than applied universally, and why the calibration of the underlying scores matters: the gate compares scores across clusters, which is a cross-document comparison that uncalibrated scores make unreliable. The methods for making those scores comparable are in Score Calibration for Blended Ranking.

A second gate is the user’s behaviour. A query followed by a reformulation is evidence that the first interpretation was wrong, and an ambiguous query followed by clicks spread across several clusters is evidence that different users meant different things. Both are weak signals individually; together they justify a higher diversification weight than the query text alone.

Failure modes at the edges

The similarity function is the weak point of every diversity method, and its failure is quiet. Cosine similarity over a bag-of-words representation treats a document and its near-duplicate as maximally similar, which is correct. It also treats a document and its negation as maximally similar, since they share vocabulary, which is wrong: “mercury is toxic” and “mercury is not toxic” are different answers to the same question and should not both occupy the list, but they are also not diverse in the sense of covering different interpretations.

Near-duplicate detection deserves separate handling. A list of ten documents that are paraphrases of each other is not diverse regardless of the subtopic model, and a cheap shingle-based similarity over the first few hundred tokens catches this case better than an embedding similarity does. Running deduplication before diversification is the standard order.

Position within the diversified list is another edge. MMR and coverage-greedy both produce an ordering, and the first result is the one most readers act on. A diversification weight high enough to change the first result is high enough to hurt the majority interpretation, which is why the weight is typically applied to positions below the first few rather than uniformly. That produces a list whose head is relevance-ordered and whose tail is diversity-ordered, which is a compromise with no clean theoretical justification but a reasonable behavioural one.

The last edge is that subtopic probabilities are themselves query-dependent and time-dependent. A query about a product’s “battery” means different things before and after a recall announcement, and a static subtopic model will keep diversifying toward the obsolete interpretation. Any subtopic distribution derived from historical behaviour inherits the same staleness and feedback problems as the click features in Click Features and Position Bias, and the same requirement applies: the estimate must be refreshed on a window, and its bias must be understood before it is trusted as ground truth about what users want.