Determinantal Point Processes for Diverse Subset Selection

702 concepts416 papers1 proposal

The Challenge of Redundancy

A recurring problem across machine learning is subset selection: given a large pool of items, how do we select a smaller subset that maximizes utility? A naive approach is to score each item individually and pick the top-$k$ highest-scoring items. However, this greedy strategy frequently fails because high-quality items tend to be highly correlated, leading to severe redundancy.

For example, in parallel Bayesian optimization, evaluating five slightly different variations of the exact same hyperparameter configuration wastes valuable computational resources (Kathuria et al.). In few-shot prompting for Large Language Models (LLMs), filling a context window with three nearly identical examples fails to show the model the full breadth of the task, leading to suboptimal performance (Ghosal et al.).

To solve this, we need a principled mathematical framework that simultaneously optimizes for individual item quality and minimizes collective redundancy. Determinantal Point Processes (DPPs) provide exactly this mechanism by elegant use of linear algebra and geometry.

The Geometry of Diversity

To understand why DPPs work, we must look at the geometric interpretation of a matrix determinant.

Imagine each item in a dataset is mapped to a feature vector in a high-dimensional space. If we want to evaluate a subset of items $Y$, we can construct a similarity matrix (or kernel matrix) $L_Y$, where each entry $L_{ij}$ measures the similarity between item $i$ and item $j$. A DPP defines the probability of selecting this specific subset $Y$ as being proportional to the determinant of its similarity matrix:

$$\mathcal{P}(Y) \propto \det(L_Y)$$

Geometrically, the determinant of a matrix equals the squared volume of the parallelotope spanned by its feature vectors. This geometric connection is the key to building intuition for DPPs:

  • High Redundancy (Low Volume): If two items are highly similar, their feature vectors point in nearly the same direction. The parallelotope they form collapses, its volume approaches zero, and thus $\det(L_Y)$ drops to zero. The DPP assigns a near-zero probability to selecting this subset.
  • High Diversity (High Volume): If the items are highly distinct (orthogonal to one another), the parallelotope expands to its maximum possible volume. The determinant is maximized, making this diverse subset highly likely to be sampled.

This "repulsive" property is what mathematically forces the selection process to favor coverage over clustering.

Balancing Quality and Diversity

Pure diversity is rarely the goal; we usually need items that are both diverse and high-quality. DPPs elegantly handle this trade-off through the decomposition of the kernel matrix $L$. We can write each entry $L_{ij}$ as:

$$L_{ij} = q_i S_{ij} q_j$$

where $q_i \in \mathbb{R}^+$ is a scalar measuring the individual quality or relevance of item $i$, and $S_{ij} \in [-1, 1]$ is the similarity between item $i$ and item $j$.

When we compute the determinant of the subset matrix $L_Y$, the quality scores factor out cleanly:

$$\det(L_Y) = \left( \prod_{i \in Y} q_i^2 \right) \det(S_Y)$$

This formulation makes the trade-off explicit. The probability of choosing a subset is the product of two distinct terms: the individual qualities of its members ($\prod q_i^2$) and the geometric diversity of their features ($\det(S_Y)$). A subset will only achieve a high sampling probability if it strikes an optimal balance between the two.

Applications Across the Machine Learning Pipeline

Because DPPs offer a mathematically rigorous way to balance quality and diversity, the authors of various papers have deployed them across nearly every stage of modern machine learning workflows.

In-Context Learning and Prompting

When selecting examples to guide LLMs, Ghosal et al. and Cao et al. use DPPs to ensure that prompt examples cover distinct linguistic or structural facets of a problem, preventing redundant information from wasting limited token space. Similarly, Wang et al. leverage DPPs to select canonical examples for human annotation by balancing model uncertainty with data diversity.

Data Curation and Pruning

Training modern models on massive datasets is computationally prohibitive. Zou et al. apply DPPs to curate training configurations for machine learning interatomic potentials, ensuring broad coverage of material behaviors. For instruction tuning, Wang et al. show that sampling data via DPPs based on model weight gradients allows a model to achieve full-dataset performance with only 20% of the data.

In parallel Bayesian optimization, evaluating multiple points simultaneously requires ensuring they do not cluster in the same high-reward region. Kathuria et al. use DPPs to sample batches of evaluation points that explore distinct regions of the search space. Nguyen et al. apply a similar principle to parallel Neural Architecture Search (NAS), balancing predicted performance with structural network diversity.

Model and Input Compression

DPPs are also used to compress models and inputs. Yang et al. employ DPPs to prune redundant visual tokens in Multimodal LLMs, maximizing the feature-space volume of retained tokens to preserve visual diversity. In network compression, Acharyya et al. use DPPs for node selection, ensuring that retained neurons represent non-overlapping features.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 466 papers
  2. Version 1 · 2026-10-04 · 404 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_determinantal_point_process_sampling_41142b0d,
  title = {determinantal point process sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/determinantal-point-process-sampling/rdr_41142b0d56d94714b2c19f0aac0db1b7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_determinantal_point_process_sampling_41142b0d_v2,
  title = {determinantal point process sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/determinantal-point-process-sampling/rdr_41142b0d56d94714b2c19f0aac0db1b7/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake