vault

MMR

5 min read

MMR

MMR (Maximal Marginal Relevance) is a re-ranking algorithm introduced by Jaime Carbonell and Jade Goldstein (Carnegie Mellon) in their 1998 SIGIR paper “The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries”. The algorithm was originally designed for information retrieval (re-ranking search results to balance relevance with non-redundancy) and was later adopted as a standard re-ranking technique in recommender systems for the same purpose: take a relevance-scored candidate list and produce a re-ranked list that trades off per-item relevance against pairwise dissimilarity from already-selected items. MMR is the most widely-deployed diversity re-ranker because of its simplicity (a single tunable parameter), its greedy O(N · K) complexity, and its empirically reasonable behavior. Most production recommender re-ranking pipelines use either MMR directly or some descendant of it.

1. The Re-Ranking Problem

A relevance model produces, for each request, a candidate list of items ranked by predicted relevance. Naively returning the top-K of this list often produces redundant recommendations — five near-duplicate items at the top, all relevant but providing little incremental value to the user.

The re-ranking problem: given the relevance-scored candidates and a similarity function between items, produce a re-ranked top-K list that balances relevance (each item should be predicted relevant) against diversity (selected items should differ from each other). The re-ranker operates on the relevance-model output and so is cheap — it does not need to score against the full catalog.

MMR is the standard answer to this problem. It is greedy: at each step, select the next item to maximize a linear blend of relevance and dissimilarity from already-selected items.

2. The Algorithm

Given a candidate set C (the relevance-model’s top-N candidates), a relevance score Rel(i) for each candidate, and a similarity function Sim(i, j) between any pair, MMR builds the re-ranked list S iteratively.

S = []
while |S| < K:
    next_item = argmax_{i ∈ C \ S}  MMR(i)
    where MMR(i) = λ · Rel(i)  −  (1 − λ) · max_{j ∈ S}  Sim(i, j)
    S.append(next_item)

Where:

  • Rel(i) is the relevance score from the upstream model (typically normalized to [0, 1] for clean trade-off interpretation).
  • Sim(i, j) is a similarity measure between items (typically cosine similarity on item embeddings, in [0, 1]).
  • max_{j ∈ S} Sim(i, j) is the highest similarity between candidate i and any item already in the selected list S. If S is empty (first iteration), this term is 0.
  • λ ∈ [0, 1] is the trade-off parameter:
    • λ = 1 recovers pure relevance ranking (no diversity adjustment).
    • λ = 0 selects items only by their dissimilarity from already-chosen items (no relevance consideration; effectively random).
    • λ = 0.5 weights relevance and diversity equally.
    • In practice, λ ∈ [0.5, 0.9] is common, with the exact value tuned empirically.

The algorithm is greedy — it picks the locally-best item at each step, not the globally-optimal subset. Globally-optimal subset selection under the MMR objective is NP-hard (it’s a submodular maximization problem); the greedy algorithm gives a (1 − 1/e) ≈ 63% approximation guarantee.

3. Computational Complexity

For a candidate set of size N and a target re-ranked list of size K:

  • Each step iterates over the remaining candidates (O(N)) and for each computes the max similarity to the selected items (O(K) in the worst case, where K is the current selection size).
  • Total cost: O(N · K · K) = O(N · K²).

For typical production sizes (N = 200, K = 10), this is 200 × 100 = 20,000 operations — trivially fast.

The dominant production cost is computing the pairwise similarities Sim(i, j). For dense embedding similarities, this is a few microseconds per pair; for catalog-size precomputed similarity tables, it is a single hash lookup.

4. Variants

Window-based MMR. Some variants restrict the max to the most recently-selected w items rather than all of S. This reduces the per-step cost and produces more “local” diversity (items diverse within nearby positions but not necessarily globally).

MMR with multiple similarity measures. Some applications combine multiple diversity dimensions (topical diversity + temporal diversity + creator diversity). The score becomes:

MMR(i) = λ · Rel(i)  −  Σ_d  α_d · max_{j ∈ S} Sim_d(i, j)

with separate tradeoff weights per diversity dimension.

Calibrated MMR. Adjusts λ per request based on user characteristics or context (e.g., higher diversity for new users, lower for users with established preferences).

5. When to Use MMR

MMR is appropriate when:

  • The upstream relevance model produces redundant recommendations.
  • A simple, interpretable diversity adjustment is preferred over more complex methods like Determinantal Point Processes.
  • Latency is constrained — MMR is O(N · K²) and very fast.
  • The diversity objective can be expressed as “items should be dissimilar to each other.”

Do not use MMR when:

  • The diversity objective is more nuanced (e.g., must cover specific topics with specific exposure ratios) — use a constrained re-ranker.
  • The accuracy-diversity trade-off requires more sophisticated handling — use Determinantal Point Processes.

6. Strengths

  • Simple and well-understood — single hyperparameter λ.
  • Fast — O(N · K²) per request.
  • Theoretical approximation guarantee for submodular variants of the objective.
  • Widely deployed — production re-ranker default at many companies.

7. Weaknesses

  • Greedy, not globally optimal.
  • Single-shot diversity adjustment — does not handle complex constraints.
  • λ is a single global parameter — the optimal value may differ per user or context.
  • Requires a similarity measure — must define what “diverse” means via Sim(·, ·).

8. See Also

Graph View

Backlinks