Search Result Diversity and Filter Bubbles

A ranker that maximises relevance for each position independently will fill the first page with variations of the same document, and every metric it optimises will say it did well. Diversity is the correction, and it is one greedy loop.

Why pure relevance produces boring lists

Scoring is per document. The ranker computes rel(d, q) for each candidate and sorts. Nothing in that procedure knows what is already at rank 1 when it places rank 2, so if the three most relevant documents are near-duplicates, they occupy the top three slots and the user gets one document three times.

It is worse than aesthetically annoying. A query like “jaguar speed” has two populations of answers, and a list that is entirely about the animal has zero utility for the half of users who meant the car — even though every document on it is highly relevant to somebody. Ranking by expected relevance to the average user optimises for a user who does not exist.

This is also the mechanism behind the recommendation version of the complaint. A system that ranks purely by predicted affinity, retrained on the interactions it produced, converges on a narrow band — the feedback loop in personalisation versus relevance and the popularity trap in collaborative filtering are the same failure arriving from two directions.

It helps to separate the two things people mean by diversity, because they need different fixes. Redundancy is several results saying the same thing — three articles syndicated from one wire story, four listings of the same product. Coverage is whether the list spans the different things the query could have meant. MMR addresses redundancy directly and coverage only by proxy, because it measures dissimilarity between documents rather than dissimilarity of the intents they serve. That distinction is the whole content of the intent-aware section below, and getting it wrong means deploying a technique that solves a problem you did not have.

MMR, step by step

Maximal marginal relevance (Carbonell and Goldstein, 1998) builds the list greedily, and at each step picks the candidate that maximises relevance minus its similarity to whatever has already been selected:

next = argmax over d in (Candidates - Selected) of

    lambda * rel(d, q)  -  (1 - lambda) * max over s in Selected of sim(d, s)

  rel(d, q)  relevance of d to the query, normalised to [0, 1]
  sim(d, s)  similarity between two documents
  lambda     1 = pure relevance, 0 = pure novelty
  Selected   the list built so far; empty at the first step

Work it. Four candidates, with d2 a near-duplicate of d1, and lambda = 0.7:

relevance   d1 = 0.90   d2 = 0.88   d3 = 0.85   d4 = 0.60

similarity  sim(d1,d2) = 0.95      sim(d1,d3) = 0.30
            sim(d1,d4) = 0.10      sim(d2,d3) = 0.32
            sim(d2,d4) = 0.12      sim(d3,d4) = 0.15

STEP 1  Selected is empty, so the penalty term is zero.
        Pick the most relevant: d1.        Selected = [d1]

STEP 2  d2: 0.7*0.88 - 0.3*0.95 = 0.616 - 0.285 = 0.331
        d3: 0.7*0.85 - 0.3*0.30 = 0.595 - 0.090 = 0.505   <-- highest
        d4: 0.7*0.60 - 0.3*0.10 = 0.420 - 0.030 = 0.390
        Pick d3.                           Selected = [d1, d3]

STEP 3  d2: max sim to selected = max(0.95, 0.32) = 0.95
            0.616 - 0.285 = 0.331
        d4: max sim to selected = max(0.10, 0.15) = 0.15
            0.420 - 0.045 = 0.375                    <-- highest
        Pick d4.                           Selected = [d1, d3, d4]

STEP 4  d2 is all that remains.

MMR order      d1, d3, d4, d2
Relevance order d1, d2, d3, d4

The near-duplicate has moved from rank 2 to rank 4, and the fourth-most-relevant document — which pure relevance would have buried — has moved up because it is unlike everything above it. Note that d2 is never removed. MMR reorders; it does not filter, and that matters because the near-duplicate may be the better document for a user who wants exactly that.

A practical detail that decides whether this works at all: the two similarity functions do not have to be the same measure, and often should not be. rel can be your full ranking score while sim is cosine over document embeddings, or even a cheap surface measure like shingle overlap when the redundancy you are fighting is literal near-duplication. The cost is one similarity computation per candidate per selected item, so O(k * n) for a list of k from n candidates — negligible at the sizes a reranker operates on.

Choosing lambda

lambda is not a hyperparameter to be tuned against nDCG, and this catches people out. Standard nDCG has no notion of redundancy: a list of five identical perfect documents scores 1.0. Optimising lambda against it will always push it to 1 and remove the diversification entirely.

Two ways out. Use a diversity-aware metric — alpha-nDCG (Clarke and colleagues, 2008) discounts the gain of a document for each aspect already covered by documents above it, so redundancy is penalised in the metric rather than assumed away. Or set lambda from the query’s ambiguity, using the same click-entropy estimate that gates personalisation: unambiguous query, lambda near 1; ambiguous query, lower. The second is cruder and it requires no new judgement data, which usually decides it.

One more consideration decides the value in practice, and it is about the surface rather than the algorithm. The number of visible slots sets how much diversity is affordable: on a page of ten results a diversifying swap costs one relevant document and buys one different one, while in a three-slot mobile carousel it costs a third of everything the user will see. Diversify in proportion to how much room there is, and on very small surfaces prefer covering the single most likely alternative intent over spreading across several.

When redundancy is not the problem

MMR diversifies by surface dissimilarity, which is a proxy. What you usually want is coverage of the query’s possible intents, and two documents can be textually different while serving the same intent.

The intent-aware line of work attacks this directly. IA-Select (Agrawal and colleagues, 2009) assumes a distribution over categories the query might belong to and greedily selects documents to maximise the probability that the user finds something for their category. xQuAD (Santos and colleagues, 2010) does the same over explicit query sub-aspects, typically taken from query reformulations in a log. Both need something MMR does not: a model of what the intents are. If you have a taxonomy, or a log of what people reformulate this query into, you have that model and these methods will beat MMR. If you do not, MMR is what is available and it is a genuinely good default.

Where diversification hurts

• Navigational queries. One right answer, and diversifying pushes near-misses up next to it. Gate on intent, and when in doubt do not diversify.
• Deliberately narrow queries. A user who has applied four filters has told you exactly what they want. Diversity within that set is fine; diversity that reaches outside it contradicts an explicit instruction.
• Diversity as a substitute for deduplication. If two results are the same document at two URLs, that is a canonicalisation bug and MMR is papering over it. Fix it in the index — the threshold selection in semantic deduplication is the right tool — and diversify only what is genuinely distinct.
• Diversity applied before the reranker. The candidate set is where you want breadth, and the final list is where you want it managed. Diversifying candidates and then reranking them by pure relevance undoes the work.