# Faster Greedy MAP Inference for Determinantal Point Processes

arXiv: https://arxiv.org/abs/1703.03389 · HTML: https://mlsanity.com/paper/1703.03389/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2017.

## Built on by (most cited first, 15 of 15)

- [Compositional Exemplars for In-context Learning](https://mlsanity.com/paper/2302.05698/) (2023)
- [Determinantal Beam Search](https://mlsanity.com/paper/2106.07400/) (2021)
- [Neural Design for Genetic Perturbation Experiments](https://mlsanity.com/paper/2207.12805/) (2022)
- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes](https://mlsanity.com/paper/2109.00727/) (2021)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Beyond Top-k Skill Retrieval: Diversity-Aware Skill Routing for LLM Agents](https://mlsanity.com/paper/2609.05824/) (2026)
- [FlexRouter: Learning Complementary Model Sets for Flexible LLM Routing](https://mlsanity.com/paper/2609.38585/) (2026)
- [Determinantal Point Process Attention Over Grid Cell Code Supports Out of Distribution Generalization](https://mlsanity.com/paper/2305.18417/) (2023)
- [Adaptive Quality-Diversity Trade-offs for Large-Scale Batch Recommendation](https://mlsanity.com/paper/2602.02024/) (2026)
- [MetaMoE: Diversity-Aware Proxy Selection for Privacy-Preserving Mixture-of-Experts Unification](https://mlsanity.com/paper/2605.14289/) (2026)
- [Spectral Certificates and Projection-DPP Rounding for Determinantal MAP Selection](https://mlsanity.com/paper/2606.19411/) (2026)
- [Fair Multi-View Determinantal Coresets via Adaptive NEPv](https://mlsanity.com/paper/2608.18181/) (2026)
- [Adaptive Determinantal Client Scheduling in Federated Learning](https://mlsanity.com/paper/2609.23843/) (2026)
- [CopRoute: Dependence-Aware Conformal Routing for Language Models](https://mlsanity.com/paper/2610.13276/) (2026)

## Abstract (arXiv)

Determinantal point processes (DPPs) are popular probabilistic models that arise in many machine learning tasks, where distributions of diverse sets are characterized by matrix determinants. In this paper, we develop fast algorithms to find the most likely configuration (MAP) of large-scale DPPs, which is NP-hard in general. Due to the submodular nature of the MAP objective, greedy algorithms have been used with empirical success. Greedy implementations require computation of log-determinants, matrix inverses or solving linear systems at each iteration. We present faster implementations of the greedy algorithms by utilizing the complementary benefits of two log-determinant approximation schemes: (a) first-order expansions to the matrix log-determinant function and (b) high-order expansions to the scalar log function with stochastic trace estimators. In our experiments, our algorithms are orders of magnitude faster than their competitors, while sacrificing marginal accuracy.