Maximal Marginal Relevance (MMR)

Background

Maximal Marginal Relevance (MMR) is the greedy diversifier for ranked lists. It balances relevance to the query against redundancy among already-selected items, picking the next item that maximises $(1 - \lambda)\,\text{rel}(i) - \lambda \max_j \text{sim}(i, j)$ where $j$ ranges over already-selected items.

Problem statement

Implement mmr(rel_scores, sim_matrix, k, lambda_=0.5). Greedily build a list of k indices.

$$\text{score}(i) \;=\; (1 - \lambda)\,\text{rel}_i \;-\; \lambda\, \max_{j \in S} \text{sim}_{i, j}$$

For the first pick, the max-sim term is $0$ (empty set). Return the selected indices in selection order.

Input

• rel_scores - 1-D array length $n$, relevance to the query.
• sim_matrix - $n \times n$ array of pairwise similarities in $[0, 1]$.
• k - int, number of items to select.
• lambda_ - float in $[0, 1]$, diversity strength. $\lambda = 0$ -> pure relevance; $\lambda = 1$ -> pure diversity.

Output

• list[int] of length $\min(k, n)$, selected indices in order.

Examples

Input: rel=[0.9, 0.85, 0.8], sim_matrix all-1s, k=2, lambda_=0.5
Output: [0, ...]   # first pick is highest-relevance; second is whichever maximises diversity

Constraints

• Use selection-set max sim (not sum or mean); that's the canonical MMR form.
• Tie-break on score by lower index.
• $k$ may exceed $n$; in that case return $n$ items.

Notes

• Why greedy. The exact diversification problem is NP-hard; MMR is the universally-cited greedy heuristic. Production rerankers run it as a post-step after the bi-encoder retrieval.