A Model of Diverse Sampling from Language Models

Manuel Prada-Corral, Yahya Emara, Timothy J. O'Donnell, Ryan Cotterell, Tim VieiraarXiv 2026 · arXiv

TL;DR

This paper introduces PoolDPP, a method to generate diverse sets of outputs from language models by leveraging Determinantal Point Processes (DPPs). By sampling a candidate pool and selecting a subset based on quality-scaled embeddings, the authors provide a tractable way to navigate the quality-diversity frontier with a proven $O(1/N)$ convergence bound.

What Problem Does This Paper Address?

When you ask a language model a question with multiple valid perspectives or interpretations, you often want a set of diverse answers rather than a single "authoritative" one. However, standard decoding methods (like temperature or top-p sampling) generate each string independently. Because the model doesn't "know" what it has already generated, independent samples tend to cluster around the same high-probability semantic modes—essentially giving you the same answer phrased ten different ways.

Existing "diverse decoding" heuristics often lack a globally coherent definition of similarity. This paper seeks to formalize diverse generation as a subset selection problem where the goal is to pick $K$ strings that are both high-quality and mutually dissimilar.

Methods

The authors formalize the problem using Determinantal Point Processes (DPPs). In a DPP, the probability of selecting a subset of items is proportional to the determinant of a kernel matrix. Geometrically, if you represent each string as an embedding vector scaled by its "quality" (probability), the probability of a subset is proportional to the squared volume of the parallelepiped spanned by those vectors. If two strings are similar (nearly parallel), the volume—and thus the probability of picking both—collapses toward zero.

Diverse implementations of sorting algorithms. The highlighted triple has high probability because it combines distinct strategies, yielding a large spanned volume.

Since exact inference over the infinite set of all possible strings is impossible, they propose PoolDPP:

  1. Pool Generation: Draw a finite pool of $N$ candidate strings from a tractable proposal distribution (e.g., standard ancestral sampling).
  2. Importance Weighting: Weight the candidates to match a target "global" quality distribution (global annealing).
  3. Subset Selection: Run a $K$-DPP sampler on the induced pool kernel. They also offer a greedy MAP (Maximum A Posteriori) variant for deterministic selection.

To make this efficient, they use a "dual trick," performing calculations in the embedding space ($D \times D$) rather than the pool size space ($N \times N$), making the selection step linear in the pool size.

Datasets

The authors evaluated PoolDPP across three distinct domains:

  • FineWeb: Used for open-ended text generation to measure the intrinsic quality-diversity trade-off.
  • Ambrosia: A benchmark for ambiguous text-to-SQL tasks, where a single natural language query can map to multiple valid SQL interpretations.
  • GSM8K: A dataset of grade-school math word problems, used to see if diverse reasoning paths improve the chance of finding the correct answer (pass@K).
  • MATH-500: Used in the appendix for a "saturation check" on more difficult mathematical reasoning.

Key Insights and Ideas

  • The Geometry of Repulsion: By using pretrained sentence embedders (like MiniLM or Qwen), the DPP naturally "repels" semantically similar outputs. The choice of embedder defines what "diverse" means for a specific task.
  • Global vs. Local Annealing: The paper highlights that standard temperature sampling (local annealing) distorts the model's coherence. PoolDPP targets "global annealing," which preserves the relative log-probability differences of entire sequences, maintaining better fluency.
  • Theoretical Convergence: A major contribution is a finite-sample bound. They prove that the KL divergence between the PoolDPP output and the ideal (but intractable) target DPP decays as $O(1/N)$ as the pool size $N$ increases.
  • Rao-Blackwellization: The authors show that their pool-based approach is essentially a Rao-Blackwellized version of a naive importance sampler, meaning it inherently reduces variance.

Key Results

PoolDPP consistently outperformed baselines like $K$-means reranking and diverse beam search.

  • Intrinsic Evaluation: On FineWeb, PoolDPP-MAP significantly extended the quality-diversity Pareto frontier compared to ancestral sampling and $K$-means.
Intrinsic evaluation on FineWeb. PoolDPP-MAP (red dotted line) dominates other methods, achieving higher diversity for the same level of quality.
  • Ambiguity Resolution: On the Ambrosia (text-to-SQL) task, PoolDPP pushed the precision-recall frontier higher. It was better at surfacing distinct valid SQL interpretations rather than minor syntactic variations.
  • Mathematical Reasoning: On GSM8K, while it didn't significantly boost the "pass@10" score over the best ancestral sampling, it reached nearly the same accuracy while providing much higher diversity in the reasoning chains.

Limitations and Future Work

  • Pool Ceiling: PoolDPP can only select from what is already in the pool. If the initial proposal fails to sample a correct or unique interpretation, the DPP cannot "invent" it. On Ambrosia, the pools only contained about 42% of the "gold" interpretations on average.
  • Embedder Dependency: The definition of diversity is entirely dependent on the embedding model. If the embedder blurs distinctions that the task cares about (e.g., subtle logic changes in math), the DPP won't preserve them.
  • Compute Cost: While the selection step is fast, generating a large pool ($N=400$) is still computationally expensive, as it requires many forward passes through the LLM. Future work might involve integrating DPP-like objectives directly into the decoding process or training.

Summary updated

Abstract

Language models often produce high-quality individual samples but poor sets, with repeated samples clustering around the same semantic modes. We formalize diverse generation as sampling a size-$K$ subset of complete strings from a determinantal point process (DPP), where the likelihood encodes item quality, and the embedding geometry encodes repulsion between similar outputs. Exact inference over all strings is intractable, so we propose PoolDPP: draw a finite candidate pool from a tractable proposal, importance-weight the candidates toward the target quality, and run a $K$-DPP sampler on the induced pool kernel; a greedy MAP variant provides deterministic selection. We prove a finite-sample bound with an explicit constant: the KL divergence between the sampler's output and the target $K$-DPP decays as O(1/N) in the pool size. Empirically, PoolDPP extends the quality--diversity frontier on open-ended generation and the precision--recall frontier on ambiguous text-to-SQL (Ambrosia), and on mathematical reasoning (GSM8K), it raises diversity at about the same pass@$K$.
BibTeX
@misc{pradacorral2026model,
  author = {Manuel Prada-Corral and Yahya Emara and Timothy J. O'Donnell and Ryan Cotterell and Tim Vieira},
  title = {{A Model of Diverse Sampling from Language Models}},
  year = {2026},
  eprint = {2611.25003},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25003},
}
Figure