Maximal Marginal Relevance (MMR)

MMR uses a greedy, iterative selection process because the optimal set selection is NP-hard. The algorithm proceeds as follows:

1. Start with an empty result set S and a full candidate set R.
2. Select the document from R with the highest relevance score to Q and move it to S.
3. For each remaining position k:
   • For every document d_i in R, compute its MMR score.
   • Select the document d_i with the highest MMR score.
   • Remove d_i from R and add it to S.
4. Repeat step 3 until S reaches the desired size.

This greedy approach is computationally efficient, requiring O(kn) similarity computations for k results and n candidates.

MMR is agnostic to the specific similarity functions used for Sim1 (query-document) and Sim2 (document-document). This allows integration with various retrieval backends:

• Sparse Retrieval: Use BM25 or TF-IDF for Sim1 and Sim2.
• Dense Retrieval: Use cosine similarity between vector embeddings (e.g., from Sentence-BERT).
• Hybrid Retrieval: Use a weighted combination of sparse and dense scores for Sim1.
• Cross-Encoder Reranking: Use a more accurate but slower neural model for final Sim1 scoring after an initial fast retrieval.

The choice of similarity function directly impacts the semantic definition of both "relevance" and "novelty."

In Retrieval-Augmented Generation (RAG) and autonomous agent workflows, MMR is critical for context window management.

• Preventing Redundancy: When constructing a context window from multiple retrieved documents, MMR ensures each chunk provides unique information, maximizing the utility of limited model tokens.
• Mitigating Bias: Without MMR, a retriever might return several highly similar documents that reinforce a single perspective or fact, potentially biasing the LLM's synthesis.
• Supporting Multi-Step Reasoning: For agents, diverse context chunks can contain different pieces of evidence required for complex, multi-faceted reasoning, as opposed to repetitive evidence for a single sub-task.

The naive MMR implementation has a complexity of O(kn) for k results and n candidates, with each step requiring a similarity computation against all items in S. For large-scale systems, this can be optimized:

• Pre-computed Document-Document Similarity: For static corpora, a pre-computed similarity matrix can cache Sim2 values, trading memory for speed.
• Approximate Nearest Neighbor (ANN) Search: Use vector indexes like HNSW for fast retrieval of top-relevance candidates (Sim1), reducing n in the initial candidate set R.
• Cluster-Based Pruning: First cluster candidates, then apply MRR to select diverse clusters before selecting within clusters.
• Threshold-Based Novelty: Ignore the max operation if similarity to any doc in S is below a threshold, speeding up the calculation.

A technique often used before retrieval to improve recall, which changes the input to MMR. Query expansion augments a user's original search query with additional related terms or phrases.

• Effect on MMR: By retrieving a broader set of initially relevant documents, the pool for MMR's diversity selection becomes richer and potentially more varied.
• Synergy: Query expansion casts a wider net; MMR refines the catch to avoid repetitive results.

The core infrastructure that enables the similarity calculations MMR relies on. A dense vector index (e.g., in a vector database) stores high-dimensional embeddings of text chunks.

• MMR's Dependency: To compute the "marginal relevance" of a new chunk, MMR must efficiently find its similarity to already-selected chunks. This requires fast Approximate Nearest Neighbor (ANN) search provided by indices like HNSW or IVF.
• Performance: The efficiency of the underlying index directly impacts the latency of an MMR reranking step.

An alternative ranking method to MMR for combining multiple result lists. RRF is a simple, score-free method used in hybrid search:

• It takes ranked lists from different retrievers (e.g., keyword and vector).
• It assigns a score based on the reciprocal of the sum of each item's rank across lists.
• It reranks all items based on this fused score.

Key Difference from MMR: RRF focuses on aggregating rankings from multiple sources but does not explicitly optimize for diversity within the final list, which is MMR's primary objective.

The framework for measuring algorithms like MMR. Key metrics assess the trade-off MMR manages:

• Precision@K: Measures the fraction of relevant items in the top K results. MMR aims to maintain high precision while introducing diversity.
• Recall: Measures the fraction of all relevant items retrieved. MMR typically operates on a pre-retrieved set, so it doesn't directly affect recall.
• Novelty & Diversity: Metrics like Alpha-nDCG or Intent-Aware Metrics explicitly measure the diversity of subtopics covered in a result set, which is what MMR is designed to maximize.