Maximal Marginal Relevance

The problem, from first principles

Retrieving the top-k documents by similarity has a failure mode: if the best five passages are near-duplicates (the same fact on five web pages), they waste the context window and crowd out other useful information. Maximal marginal relevance (MMR) selects documents one at a time, scoring each candidate by how relevant it is to the query minus how similar it is to what has already been chosen. A parameter lam between 0 and 1 controls the balance: lam = 1 is plain top-k relevance, lam = 0 is pure diversity.

From theory to code

Implement mmr_select.

Constraints

• query is a vector and docs is a list of vectors (plain Python lists). Similarity is cosine similarity (0.0 for zero vectors).
• Select k documents greedily. At each step choose the unselected document maximizing lam * sim(query, d) - (1 - lam) * max(sim(d, s) for s in selected), where the max over an empty selection is 0. Ties go to the lower index.
• Return the selected indices in selection order. If k exceeds the number of documents, return all of them.

Hints