https://github.com/rycolab/pool-dpp
Introduction
Search engines gave us pages of results; we browsed and chose. In contrast, language models often give us just one authoritative-sounding answer. However, for important questions—where multiple perspectives exist, or the right answer depends on context—we might want that plurality back. For example, when answering ambiguous questions, a model should surface multiple valid interpretations rather than commit to a single one [33 ] . Pushing the language model’s regenerate button 10 times yields 10 distinct outputs, but they often cluster around the same idea, phrased slightly differently.1 This makes sense because the model generates each string independently; it has no notion of what it means for a set of 10 strings to be diverse.
Why do samples cluster? Because nothing in the sampling process discourages similarity. Temperature sampling broadens the distribution over next tokens, but it does not model relationships between outputs—two samples may independently land in the same high-probability region.2 Diverse decoding methods based on beam search [36 , 30 ] inject heuristics during decoding, but they lack a globally coherent notion of what it means for two strings to be similar or for a set to be diverse. These approaches are attractive because they are fast, but they are documented to produce artifacts such as incoherence or sudden shifts in topic [17 , 35 ] . Other work has explored adopting sampling-without-replacement schemes in LMs [23 , 29 ] , but the notion of similarity in these models is exact equality. Thus, these methods tend to cluster like independent samples. To get diverse outputs, we need to define similarity and then explicitly discourage it.
We formalize diverse sampling as a probabilistic model over subsets of strings using determinantal point processes (DPPs; [25 ] ).3 The key ingredient is a similarity function: we represent each string by its embedding (e.g., from a pretrained sentence embedder) scaled by its quality, so that the direction encodes meaning and the magnitude encodes quality. Two strings are similar if their embeddings point in roughly the same direction. A DPP assigns probability to subsets proportional to the squared volume spanned by their quality-scaled embeddings—large when items are high-quality and point in different directions, near-zero when they are redundant. This gives us a well-defined distribution over sets: one that assigns high probability to sets of K K K strings that are individually good and collectively spread out, with a parameter that controls the balance between quality and diversity. Figure 1 illustrates this in the context of generating meaningfully different sorting algorithm implementations.
Figure 1. Diverse implementations of sorting. Each point is a sorting-algorithm implementation, embedded by a code language model and projected to 3D with PCA; colors denote algorithm family. The 3-DPP assigns subset probability proportional to the squared volume of the parallelepiped spanned by the selected quality-scaled embeddings—large when the selected items are individually high-quality (large norms) and mutually dissimilar. The highlighted triple has high probability because it combines implementations from distinct algorithmic strategies, yielding a large spanned volume; by contrast, choosing three variants from the same cluster (e.g., three quicksorts) produces nearly parallel embeddings and thus near-zero volume despite high individual quality.
Since exact inference in this DPP over all strings is intractable, we propose PoolDPP, a finite-pool approximation. PoolDPP draws N N N candidate strings from a tractable proposal, importance-weights them toward a globally tempered quality distribution, and applies a K K K -DPP on the resulting pool. The same pool kernel supports two inference modes: stochastic K K K -DPP sampling (PoolDPP-Sampling) and greedy MAP selection (PoolDPP-MAP). For the sampling mode, we prove a non-asymptotic approximation guarantee: the KL divergence between the marginal output law of PoolDPP-Sampling (its output distribution, averaged over random pools) and the target K K K -DPP decreases as O ( 1 / N ) \mathcal{O}(1/N) O ( 1/ N ) with the pool size. The bound’s constant is explicit, and we evaluate it on each task, on instances built from its pools rather than on the full proposal; the MAP mode has no distributional guarantee. Empirically, PoolDPP extends the quality–diversity frontier on open-ended generation and the precision–recall frontier on ambiguous text-to-SQL. On mathematical reasoning, it raises diversity at about the same pass@K K K (within 0.01; § 6.3 ), and we measure how weakly the embedders separate correct from incorrect reasoning chains.
Language Modeling
A language model p p p is a probability distribution over the set Σ ∗ \Sigma^{*} Σ ∗ of all strings over an alphabet Σ \Sigma Σ . Every language model p p p admits the factorization p ( y ) = p ~ ( E O S ∣ y ) ∏ t = 1 ∣ y ∣ p ~ ( y t ∣ y < t ) p(\boldsymbol{y}) = \tilde{p}(\mathrm{EOS} \mid\boldsymbol{y}) \prod_{t=1}^{\lvert\boldsymbol{y}\rvert} \tilde{p}(y_t \mid y_{<t}) p ( y ) = p ~ ( EOS ∣ y ) ∏ t = 1 ∣ y ∣ p ~ ( y t ∣ y < t ) , where y < t = y 1 , … , y t − 1 \boldsymbol{y}_{<t} = y_1, \ldots, y_{t-1} y < t = y 1 , … , y t − 1 , ∣ y ∣ \lvert\boldsymbol{y}\rvert ∣ y ∣ denotes the string’s length, and E O S ∉ Σ \mathrm{EOS} \notin\Sigma EOS ∈ / Σ is a distinguished end-of-string marker . Here, p ~ ( y ) = ∑ y ′ ∈ Σ ∗ p ( y y ′ ) \tilde{p}(\boldsymbol{y}) = \sum_{\boldsymbol{y}' \in\Sigma^{*}} p(\boldsymbol{y}\boldsymbol{y}') p ~ ( y ) = ∑ y ′ ∈ Σ ∗ p ( y y ′ ) is the prefix probability , the probability that a string drawn from p p p starts with y \boldsymbol{y} y . Its conditionals are p ~ ( y ∣ y ) = p ~ ( y y ) / p ~ ( y ) \tilde{p}(y \mid\boldsymbol{y}) = \tilde{p}(\boldsymbol{y}y)/\tilde{p}(\boldsymbol{y}) p ~ ( y ∣ y ) = p ~ ( y y ) / p ~ ( y ) for y ∈ Σ y \in\Sigma y ∈ Σ and p ~ ( E O S ∣ y ) = p ( y ) / p ~ ( y ) \tilde{p}(\mathrm{EOS} \mid\boldsymbol{y}) = p(\boldsymbol{y})/\tilde{p}(\boldsymbol{y}) p ~ ( EOS ∣ y ) = p ( y ) / p ~ ( y ) (if p ~ ( y ) = 0 \tilde{p}(\boldsymbol{y}) = 0 p ~ ( y ) = 0 , we set p ~ ( y ∣ y ) = 1 { y = E O S } \tilde{p}(y \mid\boldsymbol{y}) = \mathbb{1}\{y = \mathrm{EOS}\} p ~ ( y ∣ y ) = 1 { y = EOS } for all y ∈ Σ ∪ { E O S } y \in\Sigma\cup\{\mathrm{EOS}\} y ∈ Σ ∪ { EOS } ). In our experiments, the language model is conditioned on a prompt x ∈ Σ ∗ x \in\Sigma^{*} x ∈ Σ ∗ : p ( y ∣ x ) = d e f p ( x y ) / p ⃗ ( x ) p(y \mid x) \mathrel{\stackrel{\mathrm{def}}{=}} p(xy)/\vec{p}(x) p ( y ∣ x ) = def p ( x y ) / p ( x ) , the probability that a string starting with x x x continues with y y y and then ends. We write p ( y ) p(y) p ( y ) when the prompt is fixed. This factorization gives a generation procedure, known as ancestral sampling : starting from the empty prefix, we sample tokens left-to-right as y t ∼ p ⃗ ( ⋅ ∣ y < t ) y_t \sim\vec{p}(\cdot\mid y_{<t}) y t ∼ p ( ⋅ ∣ y < t ) until EOS is drawn.
We define local annealing by temperature T ′ T' T ′ as the following change to the conditional distribution, and the locally annealed language model as the product of the annealed conditionals:
p ⃗ T ′ ( y t ∣ y < t ) = d e f p ⃗ ( y t ∣ y < t ) 1 / T ′ ∑ y ∈ Σ ∪ { E O S } p ⃗ ( y ∣ y < t ) 1 / T ′ (1) \vec{p}_{T'}(y_t \mid y_{<t}) \mathrel{\stackrel{\mathrm{def}}{=}} \frac{\vec{p}(y_t \mid y_{<t})^{1/T'}}{\sum_{y \in\Sigma\cup\{\mathrm{EOS}\}} \vec{p}(y \mid y_{<t})^{1/T'}} \tag*{(1)} p T ′ ( y t ∣ y < t ) = def ∑ y ∈ Σ ∪ { EOS } p ( y ∣ y < t ) 1/ T ′ p ( y t ∣ y < t ) 1/ T ′ (1)
p ⃗ T ′ ( y ) = d e f p ⃗ T ′ ( E O S ∣ y ) ∏ t = 1 ∣ y ∣ p ⃗ T ′ ( y t ∣ y < t ) (2) \vec{p}_{T'}(y) \mathrel{\stackrel{\mathrm{def}}{=}} \vec{p}_{T'}(\mathrm{EOS} \mid y)\prod_{t=1}^{|y|}\vec{p}_{T'}(y_t \mid y_{<t}) \tag*{(2)} p T ′ ( y ) = def p T ′ ( EOS ∣ y ) t = 1 ∏ ∣ y ∣ p T ′ ( y t ∣ y < t ) (2)
for all y t ∈ Σ ∪ { E O S } y_t \in\Sigma\cup\{\mathrm{EOS}\} y t ∈ Σ ∪ { EOS } and y ∈ Σ ∗ y \in\Sigma^{*} y ∈ Σ ∗ . Ancestral sampling with the annealed conditionals draws from p ⃗ T ′ \vec{p}_{T'} p T ′ . As T ′ → 0 T' \to0 T ′ → 0 , each conditional concentrates on its mode, yielding greedy decoding; in contrast, as T ′ → ∞ T' \to\infty T ′ → ∞ , each conditional approaches the uniform distribution over Σ ∪ { E O S } \Sigma\cup\{\mathrm{EOS}\} Σ ∪ { EOS } . High local temperatures increase diversity at the cost of coherence; low temperatures increase coherence at the cost of diversity [11 , 15 ] . Local annealing is efficient, as it only requires O ( ∣ Σ ∣ ) O(|\Sigma|) O ( ∣Σ∣ ) additional work per time step to adjust its conditional distribution.
In contrast, global annealing by temperature T T T modifies the probability of entire sequences:
p T ( y ) = d e f p ( y ) 1 / T ∑ y ′ ∈ Σ ∗ p ( y ′ ) 1 / T (3) p_T(y) \mathrel{\stackrel{\mathrm{def}}{=}} \frac{p(y)^{1/T}}{\sum_{y' \in\Sigma^{*}}p(y')^{1/T}} \tag*{(3)} p T ( y ) = def ∑ y ′ ∈ Σ ∗ p ( y ′ ) 1/ T p ( y ) 1/ T (3)
when the sum is finite, which holds for every T ≤ 1 T \le1 T ≤ 1 , since p ( y ) 1 / T ≤ p ( y ) p(y)^{1/T} \le p(y) p ( y ) 1/ T ≤ p ( y ) . Unlike local annealing, which modifies each conditional independently, global annealing linearly scales log-probability differences between sequences: high T T T compresses these differences, while low T T T amplifies them. Global annealing tends to preserve the coherence and fluency of the underlying language model. Kempton and Burrell [20 ] show that local annealing does not generally yield a good approximation to the globally annealed distribution p T p_T p T . Unfortunately, exact sampling from the global distribution is intractable.4
Determinantal Point Processes
Determinantal point processes (DPPs) are distributions over subsets that naturally encode diversity: items that are similar are unlikely to be selected together. We use DPPs to define a distribution over sets of strings where high-probability sets contain strings that are both high-quality and well-dispersed.
The many faces of diversity. There are many ways to operationalize the notion of a diverse set of strings. In natural language, we can distinguish semantic diversity (variation in meaning), syntactic diversity (variation in surface form), and stylistic diversity (variation in tone and register). In specialized domains such as code generation, one can also consider algorithmic diversity, i.e., variation in the underlying algorithms implemented by the generated code. Which notion matters depends on the application. In this work, we focus on notions of diversity that can be expressed through embeddings. This lets us quantify similarity geometrically and swap in a different embedder depending on the domain.
Embeddings. To measure similarity between strings, we represent each string y y y by an embedding ϕ ( y ) ∈ R D \phi(y) \in\mathbb{R}^{D} ϕ ( y ) ∈ R D from a pretrained embedder. The choice of embedder determines what notion of diversity the DPP captures—semantic, syntactic, or domain-specific. We try three options across our experiments: a small off-the-shelf semantic embedder (MiniLM-L6 ), a larger one (Qwen3-Embedding-0.6B ), and the generating LM’s own mean-pooled last-layer hidden states. On open-ended tasks like FineWeb (§ 6.1 ), the two off-the-shelf embedders give very similar quality–diversity Pareto frontiers across language models (Figure 8 ), so we use the smaller MiniLM for these tasks; on more constrained tasks like math reasoning on GSM8K (§ 6.3 ), the larger Qwen3-Embedding-0.6B picks up structural distinctions between reasoning chains that MiniLM blurs, and we adopt it as the default. The self-contained LM-hidden-state variant performs on par with the small semantic embedder in several settings but does not consistently improve over it; layer and pooling choices that we did not exhaustively optimize, and a semantic-oriented fine-tune, are a plausible route to closing that gap.
Figure 8. LM/embedding robustness (FineWeb, K = 10 K = 10 K = 10 , N = 400 N = 400 N = 400 ). Pareto frontiers across two LMs and two embedders. The qualitative ordering is stable across all four configurations.
Building a DPP. Given a base set Y \mathcal{Y} Y , a quality measure κ : Y → R ≥ 0 \kappa:\mathcal{Y}\to\mathbb{R}_{\ge0} κ : Y → R ≥ 0 , and a (unit-norm) embedding ϕ : Y → R D \phi:\mathcal{Y}\to\mathbb{R}^{D} ϕ : Y → R D (i.e., ∥ ϕ ( y ) ∥ 2 = 1 \lVert\phi(y)\rVert_{2}=1 ∥ ϕ ( y ) ∥ 2 = 1 for all y ∈ Y y\in\mathcal{Y} y ∈ Y ),5 we define the (quality–diversity) kernel matrix [25 §3.1] :
L ( x , y ) : d e f = κ ( x ) ϕ ( x ) T ϕ ( y ) κ ( y ) (4) L(x,y) \mathrel{\mathop:}^{\mathrm{def}}=\sqrt{\kappa(x)}\phi(x)^{\mathsf{T}}\phi(y)\sqrt{\kappa(y)} \tag*{(4)} L ( x , y ) : def = κ ( x ) ϕ ( x ) T ϕ ( y ) κ ( y ) (4)
Intuitively, in the quality-scaled embedding κ ( y ) ϕ ( y ) \sqrt{\kappa(y)}\phi(y) κ ( y ) ϕ ( y ) , the direction encodes meaning (for diversity) and the magnitude encodes quality. Let S ⊆ Y S\subseteq\mathcal{Y} S ⊆ Y be a finite set, and L S : d e f = [ L ( x , y ) ] x , y ∈ S ∈ R S × S L_{S}\mathrel{\mathop:}^{\mathrm{def}}=[L(x,y)]_{x,y\in S}\in\mathbb{R}^{S\times S} L S : def = [ L ( x , y ) ] x , y ∈ S ∈ R S × S be the kernel matrix indexed by S S S . A determinantal point process (DPP) is a probability distribution over subsets S ⊆ Y S\subseteq\mathcal{Y} S ⊆ Y where the probability of the set S S S is proportional to det ( L S ) \det(L_{S}) det ( L S ) . This determinant has a geometric interpretation: it equals the squared volume of the parallelepiped spanned by the quality-scaled embeddings { κ ( y ) ϕ ( y ) } y ∈ S \{\sqrt{\kappa(y)}\phi(y)\}_{y\in S} { κ ( y ) ϕ ( y ) } y ∈ S [25 §3] . This volume is large when strings are high-quality and point in different directions, and collapses to zero when two strings are nearly identical. More precisely, under Eq. (4) , the determinant decomposes as
det ( L S ) = ( ∏ y ∈ S κ ( y ) ) det ( Φ S T Φ S ) , \det(L_{S})=\left(\prod_{y\in S}\kappa(y)\right)\det(\Phi_{S}^{\mathsf{T}}\Phi_{S}), det ( L S ) = y ∈ S ∏ κ ( y ) det ( Φ S T Φ S ) ,
where Φ S : d e f = [ ϕ ( y ) ] y ∈ S ∈ R D × S \Phi_{S}\mathrel{\mathop:}^{\mathrm{def}}=[\phi(y)]_{y\in S}\in\mathbb{R}^{D\times S} Φ S : def = [ ϕ ( y ) ] y ∈ S ∈ R D × S . Here, the quality factor ∏ y ∈ S κ ( y ) \prod_{y\in S}\kappa(y) ∏ y ∈ S κ ( y ) rewards individual quality, while the diversity factor det ( Φ S T Φ S ) \det(\Phi_{S}^{\mathsf{T}}\Phi_{S}) det ( Φ S T Φ S ) penalizes collective similarity (the squared volume spanned by the embeddings).
K-DPPs. Our work uses the K K K -DPP variant, which introduces a set-size parameter K K K . This parameter constrains the underlying DPP to generate sets of exactly K K K items; thus, it can be used to encourage diversity by controlling the number of elements. The K K K -DPP’s probability is defined below:6
P ( S ) : d e f = det ( L S ) 1 { ∣ S ∣ = K } Z P(S)\mathrel{\mathop:}^{\mathrm{def}}=\frac{\det(L_{S})\mathbf{1}\{|S|=K\}}{Z} P ( S ) : def = Z det ( L S ) 1 { ∣ S ∣ = K }
where
Z : d e f = ∑ S ∈ ( Y K ) det ( L S ) (5) Z\mathrel{\mathop:}^{\mathrm{def}}=\sum_{S\in\binom{\mathcal{Y}}{K}}\det(L_{S}) \tag*{(5)} Z : def = S ∈ ( K Y ) ∑ det ( L S ) (5)
and ( Y K ) \binom{\mathcal{Y}}{K} ( K Y ) is the set of size-K K K subsets from Y \mathcal{Y} Y . P ( S ) P(S) P ( S ) is only well-defined when 0 < Z < ∞ 0<Z<\infty 0 < Z < ∞ .7
Trading off quality and diversity. We also make use of a parameter T > 0 T>0 T > 0 , the global temperature , to trade off quality and diversity. Specifically, we use
κ ( y ) = p ( y ) 1 / T (6) \kappa(y)=p(y)^{1/T} \tag*{(6)} κ ( y ) = p ( y ) 1/ T (6)
so T T T sets the target’s quality, which connects to globally annealed sampling Eq. (3) .8 Varying T T T smoothly trades off quality and diversity: smaller T T T sharpens κ \kappa κ toward high-likelihood strings (favoring quality); larger T T T flattens κ \kappa κ (favoring diversity). We found the global temperature parameter T T T essential for calibrating the language model’s likelihood to the embedder’s volumes, as T = 1 T=1 T = 1 is rarely optimal.
Inference via the dual. The standard K K K -DPP sampler eigendecomposes the Y × Y \mathcal{Y}\times\mathcal{Y} Y × Y kernel L L L , which costs O ( N 3 ) O(N^{3}) O ( N 3 ) for a base set of size N N N (in §4, the pool). When the embedding dimension D D D is much smaller than N N N , the dual representation avoids this. The kernel factors as L = B T B L=B^{\mathsf{T}}B L = B T B , where the feature matrix B ∈ R D × Y B\in\mathbb{R}^{D\times\mathcal{Y}} B ∈ R D × Y has as columns the quality-scaled embeddings κ ( y ) ϕ ( y ) \sqrt{\kappa(y)}\phi(y) κ ( y ) ϕ ( y ) , and it shares its nonzero eigenvalues with the D × D D\times D D × D dual kernel
C : d e f = B B T = ∑ y ∈ Σ ∗ κ ( y ) ϕ ( y ) ϕ ( y ) T (7) C\mathrel{\mathop:}^{\mathrm{def}}=BB^{\mathsf{T}}=\sum_{y\in\Sigma^{*}}\kappa(y)\phi(y)\phi(y)^{\mathsf{T}} \tag*{(7)} C : def = B B T = y ∈ Σ ∗ ∑ κ ( y ) ϕ ( y ) ϕ ( y ) T (7)
The dual sampler SampleDual of Kulesza and Taskar [25 ] (Alg. 1, described in §C) runs the K K K -DPP sampler on C C C instead of L L L , at cost O ( D 2 N + D 3 + D N K ) O(D^{2}N+D^{3}+DNK) O ( D 2 N + D 3 + D N K ) , which is linear in N N N for fixed D D D .
The dual trick needs the base set in memory, but ours is the infinite set Σ ∗ \Sigma^{*} Σ ∗ . §4 restricts it to a finite pool drawn from a proposal, and §5 analyzes the approximation.
Pool-Based Inference
Exact inference in the K K K -DPP over Σ ∗ \Sigma^* Σ ∗ is intractable.9 We approximate it by drawing a finite pool of candidate strings from a proposal distribution, importance-weighting the pool toward the quality function, and running DPP inference on the induced finite kernel.
Approximate K K K -DPP. Let Y ^ ≔ d e f ( y ( 1 ) , … , y ( N ) ) \widehat{\mathcal{Y}} \mathrel{\mathop{\coloneqq}^{\mathrm{def}}} \left(y^{(1)}, \ldots, y^{(N)}\right) Y : = def ( y ( 1 ) , … , y ( N ) ) with y ( n ) ∼ i . i . d . q y^{(n)} \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} q y ( n ) ∼ i.i.d. q be a pool of candidates.10 We define the pool feature matrix , which importance-weights the embeddings of the drawn strings:
B ^ ≔ d e f [ w ( n ) / N Φ ( y ( n ) ) ] n = 1 N ∈ R D × N where w ( n ) ≔ d e f κ ( y ( n ) ) q ( y ( n ) ) (8) \widehat{\mathbf{B}} \mathrel{\mathop{\coloneqq}^{\mathrm{def}}} \left[\sqrt{w^{(n)}/N}\boldsymbol{\Phi}\left(y^{(n)}\right)\right]_{n=1}^{N} \in\mathbb{R}^{D\times N}
\qquad\text{where} \qquad
w^{(n)} \mathrel{\mathop{\coloneqq}^{\mathrm{def}}} \frac{\kappa\left(y^{(n)}\right)}{q\left(y^{(n)}\right)} \tag*{(8)} B : = def [ w ( n ) / N Φ ( y ( n ) ) ] n = 1 N ∈ R D × N where w ( n ) : = def q ( y ( n ) ) κ ( y ( n ) ) (8)
These weights w ( n ) w^{(n)} w ( n ) correct for the mismatch between the proposal and the target quality distribution κ \kappa κ . If a string is sampled multiple times, each occurrence contributes its own (identical) column to B ^ \widehat{\mathbf{B}} B . Duplicates are thereby handled naturally: any selection containing two copies of the same string has two identical columns and hence a zero determinant, so it receives zero probability, while the copies’ weights add up across selections, preserving the string’s total quality mass. §5 makes both effects precise: collisions are exactly what the constant α N , K \alpha_{N,K} α N , K of Eq. (12) accounts for in the analysis (Theorems A.1 and A.2).
The dual kernel approximation is the following matrix (which satisfies E ω [ C ^ ] = C \mathbb{E}_{\omega}[\widehat{\mathbf{C}}]=\mathbf{C} E ω [ C ] = C ):
C ^ ≔ d e f B ^ B ^ T = 1 N ∑ n = 1 N w ( n ) Φ ( y ( n ) ) Φ ( y ( n ) ) T ∈ R D × D (9) \widehat{\mathbf{C}} \mathrel{\mathop{\coloneqq}^{\mathrm{def}}} \widehat{\mathbf{B}}\widehat{\mathbf{B}}^{\mathsf{T}} = \frac{1}{N}\sum_{n=1}^{N}w^{(n)}\boldsymbol{\Phi}\left(y^{(n)}\right)\boldsymbol{\Phi}\left(y^{(n)}\right)^{\mathsf{T}} \in\mathbb{R}^{D\times D} \tag*{(9)} C : = def B B T = N 1 n = 1 ∑ N w ( n ) Φ ( y ( n ) ) Φ ( y ( n ) ) T ∈ R D × D (9)
The pool K K K -DPP is the K K K -DPP whose base set is the pool indices { 1 , … , N } \{1,\ldots,N\} { 1 , … , N } and whose kernel is the pool kernel L ^ ≔ d e f B ^ T B ^ ∈ R N × N \widehat{\mathbf{L}} \mathrel{\mathop{\coloneqq}^{\mathrm{def}}} \widehat{\mathbf{B}}^{\mathsf{T}}\widehat{\mathbf{B}} \in\mathbb{R}^{N\times N} L : = def B T B ∈ R N × N , which has the same nonzero eigenvalues as C ^ \widehat{\mathbf{C}} C .
Two modes of inference. The pool K K K -DPP is a finite, tractable distribution; we use it in two ways:
PoolDPP-Sampling draws an exact sample from the pool K K K -DPP by invoking Alg. 1 with K K K and B ^ \widehat{\mathbf{B}} B . The base set of this K K K -DPP is the set of pool indices { 1 , … , N } \{1,\ldots,N\} { 1 , … , N } ; given the sampled index set I I I , PoolDPP-Sampling returns the labeled strings { y ( n ) } n ∈ I \{y^{(n)}\}_{n\in I} { y ( n ) } n ∈ I . Theorem A.1 characterizes the distribution of this string set.
PoolDPP-MAP targets the most likely set S ⋆ S^\star S ⋆ in the pool: the size-K K K subset of the pool’s strings that maximizes det L S \det L_S det L S (Eq. (5) ). This objective depends on the quality and the embeddings of the strings and not on how often the proposal drew them, so PoolDPP-MAP needs no importance correction: its feature matrix has the quality-scaled embeddings κ ( y ) Φ ( y ) \sqrt{\kappa(y)}\boldsymbol{\Phi}(y) κ ( y ) Φ ( y ) as columns. Exact maximization is NP-hard ([22 ] ); the greedy algorithm (Alg. 2) returns a set S † S^\dagger S † whose determinant is within a multiplicative factor ( K ! ) 2 (K!)^2 ( K ! ) 2 of optimal, det L S † ≥ det L S ⋆ / ( K ! ) 2 \det L_{S^\dagger} \ge\det L_{S^\star}/(K!)^2 det L S † ≥ det L S ⋆ / ( K ! ) 2 ([8 Thm. 11] ). Note that S ⋆ S^\star S ⋆ is the best size-K K K subset in the pool, not the intractable population optimum over Σ ∗ \Sigma^* Σ ∗ .
The two modes call for different settings of the global temperature T T T in κ ( y ) = p ( y ) 1 / T \kappa(y)=p(y)^{1/T} κ ( y ) = p ( y ) 1/ T : for sampling, the stochasticity of drawing a set of pool indices I I I with probability ∝ det L ^ I \propto\det\widehat{L}_I ∝ det L I already spreads mass across the pool, so κ \kappa κ can be sharp (small T T T , T ∈ [ 0.43 , 1.22 ] T\in[0.43,1.22] T ∈ [ 0.43 , 1.22 ] in our figures); for MAP, the deterministic arg-max would otherwise collapse onto near-clones of the highest-quality item, so κ \kappa κ must be flat (large T T T , T ∈ [ 1 , 500 ] T\in[1,500] T ∈ [ 1 , 500 ] in our figures; see §D).
Instantiation. Our experiments use the quality function of Eq. (6) and locally annealed ancestral sampling (Eq. (1) ) as the proposal, q ( y ) = p T ( y ) q(y)=p_T(y) q ( y ) = p T ( y ) . The importance weights then capture the difference between local and global annealing.
In §5, we show that this procedure is equivalent to a Rao–Blackwellized importance sampler, which marginalizes out the randomness in selecting subsets from Y ^ \widehat{\mathcal{Y}} Y , yielding lower-variance tractable estimates with theoretical guarantees.
Algorithm Analysis
PoolDPP samples from a K K K -DPP restricted to a finite pool Y ^ \widehat{\mathcal{Y}} Y instead of the target K K K -DPP over Σ ∗ \Sigma^* Σ ∗ . We bound the resulting bias in the pool size N N N with a generic tool, the sketched distribution . This section states the results; §A has the proofs, and §A.1 describes their Lean formalization, which is in the code repository linked on the first page.
Sketched distributions. Let f ( S ) ≥ 0 f(S) \ge0 f ( S ) ≥ 0 define an unnormalized target P ( S ) = f ( S ) / Z P(S) = f(S)/Z P ( S ) = f ( S ) / Z on a countable domain D \mathcal{D} D , with 0 < Z = ∑ S ∈ D f ( S ) < ∞ 0 < Z = \sum_{S \in\mathcal{D}} f(S) < \infty 0 < Z = ∑ S ∈ D f ( S ) < ∞ throughout (in our case D = ( Σ ∗ K ) \mathcal{D} = \binom{\Sigma^*}{K} D = ( K Σ ∗ ) ) with f ( S ) = det ( L S ) 1 { ∣ S ∣ = K } f(S) = \det(L_S)\mathbf{1}_{\{|S|=K\}} f ( S ) = det ( L S ) 1 { ∣ S ∣ = K } ). A sketch11 is a pair ( μ , f ^ ) (\mu, \widehat{f}) ( μ , f ) : a distribution μ \mu μ over internal randomness ω \omega ω , together with a (measurable) map f ^ : ω ↦ f ^ ω \widehat{f}\colon\omega\mapsto\widehat{f}_\omega f : ω ↦ f ω that produces an unnormalized weight function f ^ ω ( S ) ≥ 0 \widehat{f}_\omega(S) \ge0 f ω ( S ) ≥ 0 determined by ω \omega ω (the subscript in f ^ ω \widehat{f}_\omega f ω records this dependence). Each realization of ω \omega ω induces the sketched normalizer Z ^ = d e f ∑ S ∈ D f ^ ω ( S ) \widehat{Z} \mathrel{\stackrel{\mathrm{def}}{=}} \sum_{S \in\mathcal{D}} \widehat{f}_\omega(S) Z = def ∑ S ∈ D f ω ( S ) and, when Z ^ > 0 \widehat{Z} > 0 Z > 0 , the sketched distribution P ^ ω ( S ) = d e f f ^ ω ( S ) / Z ^ \widehat{P}_\omega(S) \mathrel{\stackrel{\mathrm{def}}{=}} \widehat{f}_\omega(S)/\widehat{Z} P ω ( S ) = def f ω ( S ) / Z . We suppose without loss of generality that Z ^ > 0 \widehat{Z} > 0 Z > 0 almost surely (footnote 12). One run draws one ω ∼ μ \omega\sim\mu ω ∼ μ and then S ∼ P ^ ω S \sim\widehat{P}_\omega S ∼ P ω , so its output follows the marginal output law :
P ‾ ( S ) = d e f E ω [ P ^ ω ( S ) ] (10) \overline{P}(S) \mathrel{\stackrel{\mathrm{def}}{=}} \mathbb{E}_{\omega}\left[\widehat{P}_\omega(S)\right] \tag*{(10)} P ( S ) = def E ω [ P ω ( S ) ] (10)
which marginalizes the sketch’s internal randomness ω \omega ω . A sketch is well-behaved if E ω [ f ^ ω ( S ) ] = f ( S ) \mathbb{E}_{\omega}[\widehat{f}_\omega(S)] = f(S) E ω [ f ω ( S )] = f ( S ) for every S S S and E ω [ Z ^ 2 ] < ∞ \mathbb{E}_{\omega}[\widehat{Z}^2] < \infty E ω [ Z 2 ] < ∞ .12
Theorem 5.1 (Variance controls bias). For any well-behaved sketch ( μ , f ^ ) (\mu, \widehat{f}) ( μ , f ) ,
χ 2 ( P ∥ P ‾ ) ≤ V ω ( Z ^ ) Z 2 and KL ( P ∥ P ‾ ) ≤ log ( 1 + V ω ( Z ^ ) Z 2 ) ≤ V ω ( Z ^ ) Z 2 (11) \chi^2(P\|\overline{P}) \le\frac{\mathop{\mathrm{V}}\nolimits_{\omega}(\widehat{Z})}{Z^2}
\qquad\text{and}\qquad
\operatorname{KL}(P\|\overline{P}) \le\log\left(1+\frac{\mathop{\mathrm{V}}\nolimits_{\omega}(\widehat{Z})}{Z^2}\right) \le\frac{\mathop{\mathrm{V}}\nolimits_{\omega}(\widehat{Z})}{Z^2} \tag*{(11)} χ 2 ( P ∥ P ) ≤ Z 2 V ω ( Z ) and KL ( P ∥ P ) ≤ log ( 1 + Z 2 V ω ( Z ) ) ≤ Z 2 V ω ( Z ) (11)
▶ Proof in §A.3.
PoolDPP is a sketch. We now instantiate the sketch ( μ , f ^ ) (\mu, \widehat{f}) ( μ , f ) for PoolDPP. The internal randomness is the pool of §4: ω = ( y ( 1 ) , … , y ( N ) ) ∼ i . i . d . q \omega= (y^{(1)}, \ldots, y^{(N)}) \mathrel{\mathop{\sim}^{\mathrm{i.i.d.}}} q ω = ( y ( 1 ) , … , y ( N ) ) ∼ i.i.d. q . The pool supplies the randomness, and the sketch is the deterministic map from a realized pool to the weight function f ^ ω \widehat{f}_\omega f ω that defines P ^ ω \widehat{P}_\omega P ω ; drawing a subset from P ^ ω \widehat{P}_\omega P ω is a second, separate stage of randomness. Writing [ N ] = d e f { 1 , … , N } [N] \mathrel{\stackrel{\mathrm{def}}{=}} \{1, \ldots, N\} [ N ] = def { 1 , … , N } for the set of pool indices, the sketched weight of a subset S ⊆ Σ ∗ S \subseteq\Sigma^* S ⊆ Σ ∗ aggregates every way the pool can realize S S S :
f ^ ω ( S ) = d e f α N , K ∑ I ⊆ [ N ] , ∣ I ∣ = K { y ( n ) ∣ n ∈ I } = S det ( L ^ I ) where α N , K = d e f N K ( N ) K , ( N ) K = d e f N ( N − 1 ) ⋯ ( N − K + 1 ) (12) \widehat{f}_\omega(S) \mathrel{\stackrel{\mathrm{def}}{=}} \alpha_{N,K} \sum_{\substack{I \subseteq[N],\,|I|=K\\ \{y^{(n)}\mid n\in I\}=S}} \det(\widehat{L}_I)
\qquad\text{where}\qquad
\alpha_{N,K} \mathrel{\stackrel{\mathrm{def}}{=}} \frac{N^K}{(N)_K},\quad
(N)_K \mathrel{\stackrel{\mathrm{def}}{=}} N(N-1)\cdots(N-K+1) \tag*{(12)} f ω ( S ) = def α N , K I ⊆ [ N ] , ∣ I ∣ = K { y ( n ) ∣ n ∈ I } = S ∑ det ( L I ) where α N , K = def ( N ) K N K , ( N ) K = def N ( N − 1 ) ⋯ ( N − K + 1 ) (12)
where I I I ranges over size-K K K sets of pool indices , L ^ \widehat{L} L is the pool kernel (§4), and the constant α N , K = 1 / Pr [ K uniform draws from [ N ] are all distinct ] \alpha_{N,K} = 1/\Pr[K\text{ uniform draws from }[N]\text{ are all distinct}] α N , K = 1/ Pr [ K uniform draws from [ N ] are all distinct ] makes the weights unbiased.13
PoolDPP-Sampling returns the strings of an index set I I I that Alg. 1, invoked with B ^ \widehat{B} B , draws with probability proportional to det ( L ^ I ) \det(\widehat{L}_I) det ( L I ) . These strings follow P ^ ω \widehat{P}_\omega P ω (Theorem A.1): index sets that repeat a string have determinant 0 0 0 , and the set-independent constant α N , K \alpha_{N,K} α N , K cancels in P ^ ω = f ^ ω / Z ^ \widehat{P}_\omega= \widehat{f}_\omega/\widehat{Z} P ω = f ω / Z . A pool has Z ^ = 0 \widehat{Z} = 0 Z = 0 exactly when rank ( C ^ ) < K \operatorname{rank}(\widehat{C}) < K rank ( C ) < K , and PoolDPP then redraws it (footnote 12).
Inclusion ratios. The analysis compares the target with the proposal through inclusion ratios : for c ≤ K c \le K c ≤ K distinct strings,
u c ( y 1 , … , y c ) = d e f P ( { y 1 , … , y c } ⊆ S ) ( K c ) q ( y 1 ) ⋯ q ( y c ) , ( K ) c = d e f K ( K − 1 ) ⋯ ( K − c + 1 ) (13) u_c(y_1,\ldots,y_c) \mathrel{\stackrel{\mathrm{def}}{=}} \frac{P(\{y_1,\ldots,y_c\}\subseteq S)}{\binom{K}{c}q(y_1)\cdots q(y_c)},
\qquad
(K)_c \mathrel{\stackrel{\mathrm{def}}{=}} K(K-1)\cdots(K-c+1) \tag*{(13)} u c ( y 1 , … , y c ) = def ( c K ) q ( y 1 ) ⋯ q ( y c ) P ({ y 1 , … , y c } ⊆ S ) , ( K ) c = def K ( K − 1 ) ⋯ ( K − c + 1 ) (13)
and u c = d e f 0 u_c \mathrel{\mathop{=}^{\mathrm{def}}} 0 u c = def 0 on tuples with a repeat and on tuples outside the support of q q q (there, κ = 0 \kappa= 0 κ = 0 because κ ≪ q \kappa\ll q κ ≪ q , so the target never contains them). The ratio u c u_c u c has mean 1 under q ⊗ K q^{\otimes K} q ⊗ K and is unchanged by rescaling κ \kappa κ . We write ρ = d e f E y ∼ q [ u 1 ( y ) 2 ] \rho\mathrel{\mathop{=}^{\mathrm{def}}} \mathbb{E}_{y\sim q}[u_1(y)^2] ρ = def E y ∼ q [ u 1 ( y ) 2 ] for the second moment of u 1 u_1 u 1 . For any K ≥ 1 K \ge1 K ≥ 1 , N ≥ K N \ge K N ≥ K , and proposal q q q with κ ≪ q \kappa\ll q κ ≪ q , the sketch is unbiased, E ω [ f ^ ω ( S ) ] = det ( L S ) 1 { ∣ S ∣ = K } \mathbb{E}_{\omega}[\widehat{f}_{\omega}(S)] = \det(L_S)1\{|S| = K\} E ω [ f ω ( S )] = det ( L S ) 1 { ∣ S ∣ = K } , and if ρ < ∞ \rho< \infty ρ < ∞ , then E ω [ Z ^ 2 ] < ∞ \mathbb{E}_{\omega}[\widehat{Z}^2] < \infty E ω [ Z 2 ] < ∞ , so PoolDPP is well-behaved (Theorem A.2).
Finite-sample bound. Combining Theorems A.2 and 5.1 reduces bounding the KL to bounding the relative variance V ω ( Z ^ ) / Z 2 \mathop{\mathrm{V}}_{\omega}(\widehat{Z})/Z^2 V ω ( Z ) / Z 2 . Since Z ^ \widehat{Z} Z is a U U U -statistic of order K K K (Eq. (48) ), its variance has an exact formula ([14 ] ), whose terms are variances of the inclusion ratios u c u_c u c of Eq. (13) .
Theorem 5.2 (Finite-sample bound). For any K ≥ 1 K \ge1 K ≥ 1 , N ≥ K N \ge K N ≥ K , and proposal q q q with κ ≪ q \kappa\ll q κ ≪ q ,
V ω ( Z ^ ) Z 2 = ∑ c = 1 K a c V q ⊗ c ( u c ) , a c = d e f ( K c ) ( N − K K − c ) ( N K ) (14) \frac{\mathop{\mathrm{V}}_{\omega}(\widehat{Z})}{Z^2}
= \sum_{c=1}^{K} a_c \mathop{\mathrm{V}}_{q^{\otimes c}}(u_c), \qquad
a_c \mathrel{\mathop{=}^{\mathrm{def}}} \frac{\binom{K}{c}\binom{N-K}{K-c}}{\binom{N}{K}} \tag*{(14)} Z 2 V ω ( Z ) = c = 1 ∑ K a c V q ⊗ c ( u c ) , a c = def ( K N ) ( c K ) ( K − c N − K ) (14) If ρ < ∞ \rho< \infty ρ < ∞ , then for any fallback
KL ( P ∥ P ‾ ) ≤ log ( e θ − 1 + a 0 ) ≤ θ = d e f K 2 ρ N − K + 1 (15) \operatorname{KL}(P\mathbin{\|}\overline{P}) \le\log(e^\theta- 1 + a_0) \le\theta\mathrel{\mathop{=}^{\mathrm{def}}} \frac{K^2\rho}{N-K+1} \tag*{(15)} KL ( P ∥ P ) ≤ log ( e θ − 1 + a 0 ) ≤ θ = def N − K + 1 K 2 ρ (15) where a 0 = ( N − K K ) / ( N K ) a_0 = \binom{N-K}{K}/\binom{N}{K} a 0 = ( K N − K ) / ( K N ) is the formula of Eq. (14) at c = 0 c = 0 c = 0 .
▶ Proof in §A.7.
The coefficients a c a_c a c are the hypergeometric law of the overlap of two independent uniform K K K -subsets of [ N ] [N] [ N ] , so the bound decays as 1 / N 1/N 1/ N (Eq. (45) ). The c = 1 c = 1 c = 1 term measures how far π 1 ( y ) = d e f P ( y ∈ S ) / K \pi_1(y) \mathrel{\mathop{=}^{\mathrm{def}}} P(y \in S)/K π 1 ( y ) = def P ( y ∈ S ) / K , the law of a uniformly chosen member of a target set, is from the proposal: since E q [ u 1 ] = 1 \mathbb{E}_q[u_1] = 1 E q [ u 1 ] = 1 , ρ = 1 + V q ( u 1 ) = 1 + χ 2 ( π 1 ∥ q ) \rho= 1 + \mathop{\mathrm{V}}_q(u_1) = 1 + \chi^2(\pi_1\mathbin{\|}q) ρ = 1 + V q ( u 1 ) = 1 + χ 2 ( π 1 ∥ q ) .
Applying the same bound to every term of Eq. (14) gives a sharper bound, Theorem A.4, which we use in the numerical evaluation (§B).
Bound scope. Theorem 5.2 bounds the KL divergence between the target and the law of the single set that PoolDPP-Sampling emits, at every pool size. PoolDPP-MAP is a deterministic function of the pool and inherits no distributional guarantee; its only guarantee is the ( K ! ) 2 (K!)^2 ( K ! ) 2 volume factor of the greedy algorithm relative to the best set in the pool (§4). The bound depends on the target only through the inclusion probabilities P ( y ∈ S ) P(y \in S) P ( y ∈ S ) . For a language model, these need C C C summed over all strings, which we cannot compute, so §B evaluates the bound on a finite instance built from our pools: the strings that the pools drew, with their observed frequencies as the proposal. These instances hold a median proposal mass of 0.68 on Ambrosia, 0.0017 on GSM8K, and 0.0003 on FineWeb. On them, the bound is small on Ambrosia and on FineWeb at T = 1 T=1 T = 1 and exceeds 1 nat on GSM8K at N = 100 N=100 N = 100 . These values are the bound on the instance, not a bound on the sampler on the full proposal.
Rao–Blackwell interpretation. PoolDPP is the Rao–Blackwellization of the naive sampler that draws K K K strings i.i.d. from the proposal, with relative variance at least a factor N / K N/K N / K lower (Theorem A.3).
Experiments
Unless otherwise noted, we sample sets of size K = 10 K=10 K = 10 (Figure 7 ablates this choice). PoolDPP-Sampling is the mode that Theorem 5.2 covers, while PoolDPP-MAP is its deterministic counterpart to be compared against the deterministic pool rerankers.
Figure 7. Subset size K K K ablation (FineWeb, N = 400 N = 400 N = 400 , local sampling temperature 1, PoolDPP-Sampling at T = 0.82 T=0.82 T = 0.82 , PoolDPP-MAP at T = 50 T=50 T = 50 ). Quality falls with K K K for the pool-based methods, and the log-determinant falls for every method.
We report results primarily for Gemma-2-9B-Instruct , paired with MiniLM-L6 on FineWeb and Ambrosia and Qwen3-Embedding-0.6B on GSM8K (§3). We also evaluated Qwen3-8B and Llama-3.1-8B-Instruct on the FineWeb intrinsic experiment: Figure 8 compares Gemma and Qwen3-8B with both embedders, and the three-model Pareto comparison with MiniLM-L6 is in Figure 9 . The qualitative ordering of methods is the same on every model. The LM-hidden-state embedding variant is discussed in §3, and §D shows the pool size N N N , subset size K K K , and global temperature T T T , and reports per-stage wall-clock time (4 and 5). Pool construction dominates runtime; PoolDPP-MAP and PoolDPP-Sampling selection cost is negligible compared to LM sampling.
Figure 9. Three-model robustness (FineWeb, MiniLM-L6, K = 10 K = 10 K = 10 ). Quality vs. diversity for Gemma-2-9B-Instruct (as in the main experiments), Qwen3-8B, and Llama-3.1-8B-Instruct; curves follow the same sweep protocol as Figure 2 (ancestral and K K K -means sweep local sampling temperature; PoolDPP-Sampling and PoolDPP-MAP draw the pool at local sampling temperature 1 and sweep the global temperature T T T ). PoolDPP-MAP (red) dominates K K K -means (purple) at higher local sampling temperatures.
We report PoolDPP in both inference modes (PoolDPP-Sampling and PoolDPP-MAP). We compare against the following baselines:
Temperature sampling: Ancestral sampling with local annealing at various temperatures.
Naive DPP: Samples a pool at T ′ = 1 T'=1 T ′ = 1 , then applies DPP selection using the proposal likelihood p ( y ) p(y) p ( y ) as the quality score. It isolates the DPP without the global temperature correction.
Diverse beam search (DivBS) (Vijayakumar et al., [36 ] ): A decoding heuristic that penalizes sibling beams for producing similar tokens.
Determinantal beam search (DetBS) (Meister et al., [30 ] ): A beam-search variant that replaces the top-K K K step with a local K K K -DPP MAP query over a string-subsequence-kernel similarity matrix. We report both DivBS and DetBS in §F; neither matches sampling-based methods on quality–diversity, so we omit them from Figure 2 .
Figure 2. Intrinsic evaluation (FineWeb). Quality vs. diversity; higher is better. Curves sweep the local sampling temperature (ancestral sampling, K K K -means) or the global temperature T T T (PoolDPP-Sampling, PoolDPP-MAP). PoolDPP-Sampling lies below the K K K -means frontier at intermediate diversity and produces different sets across runs. Error bars are 95% t t t -intervals over 10 pools (Gemma-2-9B, MiniLM-L6, K = 10 K=10 K = 10 , N = 400 N=400 N = 400 ).
Set-level baselines: Stochastic beam search (SBS; Kool et al., [23 ] ) and conditional Poisson SBS (CPSBS; Meister et al., [29 ] ), which sample sets without replacement during decoding, and two rerankers on the same pools and embeddings as PoolDPP: minimum Bayes risk (MBR; Bickel and Doksum, [3 ] ; Kumar and Byrne, [26 ] ) and maximal marginal relevance (MMR; Carbonell and Goldstein, [5 ] ). §G.1 reports them on all three tasks.
K K K -means reranking (K K K -means): The deterministic pool-reranking baseline. We sample the same pool Y ~ \widetilde{Y} Y as for PoolDPP, cluster the embeddings { ϕ ( y ) } y ∈ Y ~ \{\phi(y)\}_{y\in\widetilde{Y}} { ϕ ( y ) } y ∈ Y into K K K clusters with K K K -means (Arthur and Vassilvitskii, [2 ] ), and return the highest-likelihood item per cluster. K K K -medoids returns nearly identical subsets, so we report only K K K -means.
LLM-based selection (LLM-Select): The pool-reranking baseline that replaces the DPP with a language model. We present 40 pool items to Qwen3-8B and ask it to select K = 10 K=10 K = 10 diverse completions, without access to log-probabilities or log-determinants. Its result is reported in §D.
Each prompt is evaluated on independently sampled pools (10 on FineWeb, 100 on Ambrosia and GSM8K), and error bars are 95% confidence intervals over pools for every method. We do not run naive DPP on Ambrosia since 461 of the 10,000 (prompt, pool) pairs have Z ^ = 0 \widehat{Z}=0 Z = 0 and the results are unreliable. The methods differ only in their remaining sources of randomness: K K K -means and PoolDPP-MAP are deterministic given a pool, so their variability is driven by pool sampling alone, whereas PoolDPP-Sampling additionally redraws its DPP sample on each call.
Experiment 1: Intrinsic Evaluation
We first evaluate whether PoolDPP improves the intrinsic quality–diversity Pareto frontier. We use 50 open-ended prompts from FineWeb (Penedo et al., [32 ] ) and sample K = 10 K=10 K = 10 completions per prompt. For each prompt x x x , we sample M = 10 M=10 M = 10 sets S ( 1 ) , … , S ( M ) \mathcal{S}^{(1)},\ldots,\mathcal{S}^{(M)} S ( 1 ) , … , S ( M ) and report quality as mean LM log-probability and diversity as the log-determinant of the normalized embedding Gram matrix, averaged over the 50 prompts:
Diversity = 1 M ∑ m = 1 M log det ( Φ S ( m ) Φ S ( m ) T ) , Quality = 1 M ∑ m = 1 M 1 K ∑ y ∈ S ( m ) log p ( y ∣ x ) (16) \operatorname{Diversity}=\frac{1}{M}\sum_{m=1}^{M}\log\det\left(\Phi_{\mathcal{S}^{(m)}}\Phi_{\mathcal{S}^{(m)}}^{\mathsf{T}}\right),\qquad\operatorname{Quality}=\frac{1}{M}\sum_{m=1}^{M}\frac{1}{K}\sum_{y\in\mathcal{S}^{(m)}}\log p(y\mid x) \tag*{(16)} Diversity = M 1 m = 1 ∑ M log det ( Φ S ( m ) Φ S ( m ) T ) , Quality = M 1 m = 1 ∑ M K 1 y ∈ S ( m ) ∑ log p ( y ∣ x ) (16)
Each curve in Figure 2 is traced by varying one parameter: for ancestral sampling and K K K -means, we vary the local sampling temperature; for PoolDPP-Sampling and PoolDPP-MAP, we draw the pool at local sampling temperature 1 and vary the global temperature T T T .
Results. Figure 2 shows that PoolDPP improves the intrinsic quality–diversity frontier. Ancestral sampling traces the expected baseline: increasing local temperature improves diversity but sharply degrades quality. K K K -means provides a strong deterministic pool-reranking baseline. PoolDPP-MAP reaches a higher log-determinant with almost no quality loss, while K K K -means keeps the absolute higher quality at a lower log-determinant. PoolDPP-Sampling does not dominate K K K -means on the intrinsic objective, which is expected: PoolDPP-MAP directly optimizes the determinant objective over the pool, whereas PoolDPP-Sampling samples from the corresponding pool distribution. The sampling mode instead provides stochastic diverse sets; across repeated draws from the same pool, 20–60% of selected items differ, while K K K -means and PoolDPP-MAP are deterministic given the pool.
We omit beam-search baselines from the plot because they fall outside the displayed quality–diversity range; full numbers are in §F, and additional baselines and ablations are in §D.
Experiment 2: Ambiguity Resolution (Ambrosia)
We evaluate whether the intrinsic improvements translate to meaningful coverage of semantically distinct outputs. The Ambrosia dataset [33 ] provides natural language queries with annotated ambiguities—each query admits multiple valid SQL interpretations corresponding to different readings of the ambiguous text.
The Ambrosia dataset contains queries exhibiting scope, attachment, and vagueness ambiguities. Each example includes human-annotated SQL queries representing distinct valid interpretations, along with a database for execution. Since each query has up to 3 annotated interpretations, we sample K = 3 K=3 K = 3 SQL queries per prompt. For instance, given the query “Show me employees with managers in the NYC office ”, two valid interpretations arise:
Employees whose managers are located in NYC: WHERE manager.office = ’NYC’
Employees themselves in NYC who have managers: WHERE employee.office = ’NYC’ AND manager_id IS NOT NULL
A successful diverse sampler should generate SQL queries that cover both interpretations, rather than producing minor syntactic variations of just one.
Figure 3. Extrinsic evaluation (Ambrosia, K = 3 K=3 K = 3 , N = 200 N=200 N = 200 ). Recall vs. precision; higher is better. Precision counts a query only if its whole execution result matches a golden result. PoolDPP-MAP sweeps the global temperature T T T at local sampling temperature 1.5 and holds the high-recall end of the frontier above K K K -means; PoolDPP-Sampling lies above K K K -means; ancestral sampling at low local temperature holds the high-precision end. Error bars are 95% t t t -intervals over 100 pools (Gemma-2-9B, MiniLM-L6).
Metrics. We measure recall (golden-query coverage ) as the fraction of annotated golden intents matched by the K K K selected SQL queries, and precision (golden-query accuracy ) as the fraction of selected queries whose entire execution result equals a golden query’s result. Both metrics are computed by executing the generated SQL and comparing execution results.
Results. § 6.2 shows that PoolDPP pushes the recall–precision Pareto frontier above ancestral and the pool-reranking baseline. PoolDPP-MAP at T = 1 T=1 T = 1 reaches precision 0.392 at recall 0.238, above the best K K K -means precision, and its sweep holds the high-recall end of the frontier. Lowering T T T trades recall for precision. PoolDPP-Sampling lies above K K K -means across the sweep. Ancestral sampling at local temperature ≤ 0.7 \le0.7 ≤ 0.7 holds the high-precision, low-recall end: at high local temperature, ancestral sampling produces malformed SQL that fails to execute, so its recall gains stall, while quality reweighting lets the DPP gain recall without that collapse; with a flat quality term (large T T T ), the DPP loses precision before it gains recall. §H shows example sets.
Experiment 3: Math Reasoning (GSM8K)
We evaluate whether modeling diversity improves performance on mathematical reasoning, where generating multiple solution paths can increase the probability of finding a correct answer. We use the GSM8K dataset [9 ] , sampling K = 10 K=10 K = 10 reasoning chains per problem. We measure diversity as the average log-determinant of the embedding Gram matrix and report two accuracy metrics: pass@K K K , the fraction of problems where at least one generated chain is correct, and per-chain accuracy, the fraction of generated chains that are correct. The two metrics together separate a method that improves coverage by spreading mass across the answer space (high pass@K K K , possibly lower mean) from one that improves average chain quality.
Results. Figure 4 shows that PoolDPP raises diversity past the plotted ancestral settings and gives up at most 0.01 pass@K K K . The best ancestral pass@K K K is 0.925 ± 0.002 0.925 \pm0.002 0.925 ± 0.002 , at local sampling temperature 1.2 and log-det − 20.0 -20.0 − 20.0 . PoolDPP-Sampling reaches 0.915 ± 0.003 0.915 \pm0.003 0.915 ± 0.003 (T = 1.05 T=1.05 T = 1.05 , log-det − 15.8 -15.8 − 15.8 ), and PoolDPP-MAP reaches 0.915 ± 0.005 0.915 \pm0.005 0.915 ± 0.005 (T = 500 T=500 T = 500 , log-det − 9.6 -9.6 − 9.6 ). At equal diversity, neither mode has a higher pass@K K K than ancestral sampling, so the gain is in diversity, not in coverage.
Figure 4. Math reasoning (GSM8K). Diversity (log-det Gram matrix) vs. pass@K = 10 K=10 K = 10 . Point labels are the local sampling temperature for ancestral sampling, naive DPP, and K-means, and the global temperature T T T for PoolDPP-Sampling and PoolDPP-MAP. PoolDPP-Sampling and PoolDPP-MAP hold local sampling temperature 1.2. At its largest T T T , each is more diverse than any plotted ancestral or K-means setting (log-det − 12.4 -12.4 − 12.4 and − 9.6 -9.6 − 9.6 , against − 20.0 -20.0 − 20.0 and − 13.8 -13.8 − 13.8 ). Error bars are 95% t t t -intervals over 100 pools.
Pure-diversity selection (T = 500 T=500 T = 500 ) lowers per-chain accuracy (0.502 vs. 0.682), much more than it lowers pass@K K K (0.915 vs. 0.925), which separates coverage from per-chain quality. K-means, has the lowest pass@K K K of the four methods in Table 9 , below both PoolDPP modes, suggesting that DPP repulsion generalizes better to downstream metrics than cluster-based selection. See §H.3 for example reasoning chains showing how diversity-targeted selection covers competing interpretations of ambiguous problem statements.
Table 9.
Conclusion
We presented a method that natively models diversity in language model outputs using determinantal point processes. On FineWeb, determinantal repulsion alone (naive DPP) already improves on ancestral sampling at matched temperature (log-det − 6.3 -6.3 − 6.3 vs. − 8.2 -8.2 − 8.2 at local temperature 0.6, with quality − 40.1 -40.1 − 40.1 vs. − 39.4 -39.4 − 39.4 ), and sweeping the global temperature T T T traces the rest of the frontier. On FineWeb, the combined approach extends the quality–diversity frontier (through PoolDPP-MAP; PoolDPP-Sampling lies below the K K K -means frontier at intermediate diversity, Figure 2 ), and on Ambrosia, the precision–recall frontier; on GSM8K, it extends only the diversity axis, whether or not the Qwen3-Embedding-0.6B embedder is given a task instruction (§E.1).
Limitations. PoolDPP selects from a pool, so it cannot return an output the proposal never samples: on Ambrosia, the pools contain at most 42% of the gold interpretations on average, and both PoolDPP modes recover 52–53% of their pools’ coverage (§G.3). What counts as diverse is fixed by the embedder; the paired-edit probe of §E.1 is a cheap check of whether an embedder separates the distinctions a task cares about. The best global temperature T T T differs across tasks and between the two modes, so choosing an operating point requires task labels or a target diversity level. On FineWeb and GSM8K, the pools approximate the global-temperature target poorly away from T = 1 T=1 T = 1 (ESS below K K K for most prompts, §D). Finally, the bound of Theorem A.4 is evaluated only on instances built from our pools, so its values are not a bound on the sampler’s KL for our runs (§5).
Acknowledgments and Disclosure of Funding
The authors thank Robin Shing Moon Chan, Ben Lipkin, and other members of the GenLM consortium for helpful discussions that improved this work. We also thank the anonymous reviewers for their valuable feedback, including suggesting the K K K -means baseline and asking us to evaluate our earlier KL bound numerically, which led to the sharper bound of Theorem A.4. Manuel was supported by Fundación Barrié and the Max Planck ETH Center for Learning Systems during parts of this work.
AI-use disclosure. We used agentic coding utilities to edit and draft parts of the text, to write analysis code, to double-check proofs, and to help write the Lean formalization of §A.1. The authors reviewed every change and take full responsibility for this paper’s content.
Deferred Proofs
This appendix gives the proofs deferred from the main text. We use the main-text notation: ω ∼ μ \omega\sim\mu ω ∼ μ is the sketch’s internal randomness (for PoolDPP, the pool), f ^ ω \widehat{f}_{\omega} f ω and Z ^ \widehat{Z} Z are the random unnormalized weight and normalizer, P ^ ω = f ^ ω / Z ^ \widehat{P}_{\omega} = \widehat{f}_{\omega}/\widehat{Z} P ω = f ω / Z is the sketched distribution, and P ‾ \overline{P} P is the marginal output law of Eq. (10) . As there, Z ^ > 0 \widehat{Z} > 0 Z > 0 almost surely; footnote 12 reduces the general case to this one.
We formalized Theorems A.4, 5.1 and 5.2 and Theorem A.2 in Lean 4 with Mathlib, and the code is available in the repository.
Redrawing degenerate pools and the constant α N , K \alpha_{N,K} α N , K
Redraw. If Pr ω [ Z ^ = 0 ] > 0 \Pr_{\omega}[\widehat{Z} = 0] > 0 Pr ω [ Z = 0 ] > 0 , then f ^ ω ≡ 0 \widehat{f}_{\omega} \equiv0 f ω ≡ 0 on those ω \omega ω (the weights are nonnegative), and PoolDPP redraws ω \omega ω . For a well-behaved sketch, γ d e f = Pr ω [ Z ^ > 0 ] \gamma\mathrel{\mathop{\rm def}}= \Pr_{\omega}[\widehat{Z} > 0] γ def = Pr ω [ Z > 0 ] is positive, since E ω [ Z ^ ] = Z > 0 \mathbb{E}_{\omega}[\widehat{Z}] = Z > 0 E ω [ Z ] = Z > 0 . So redrawing until Z ^ > 0 \widehat{Z} > 0 Z > 0 , which is rejection sampling, ends with probability 1, and it runs the sketch ( μ + , f ^ ) (\mu_{+},\widehat{f}) ( μ + , f ) , where μ + \mu_{+} μ + is μ \mu μ conditioned on Z ^ > 0 \widehat{Z} > 0 Z > 0 . This sketch has Z ^ > 0 \widehat{Z} > 0 Z > 0 almost surely, it is well-behaved for f / γ f/\gamma f / γ , which defines the same target P P P , and E μ + [ Z ^ 2 ] / ( Z / γ ) 2 = γ E μ [ Z ^ 2 ] / Z 2 \mathbb{E}_{\mu_{+}}[\widehat{Z}^{2}]/(Z/\gamma)^{2} = \gamma\mathbb{E}_{\mu}[\widehat{Z}^{2}]/Z^{2} E μ + [ Z 2 ] / ( Z / γ ) 2 = γ E μ [ Z 2 ] / Z 2 . Any other rule for these ω \omega ω (a fallback : some measurable distribution over sets) has an output law at least γ \gamma γ times the redraw law P ‾ + \overline{P}_{+} P + pointwise, so compared with P ‾ + \overline{P}_{+} P + , it multiplies 1 + χ 2 1+\chi^{2} 1 + χ 2 by at most 1 / γ 1/\gamma 1/ γ and adds at most log ( 1 / γ ) \log(1/\gamma) log ( 1/ γ ) to KL. Either way, Theorem 5.1 for ( μ + , f ^ ) (\mu_{+},\widehat{f}) ( μ + , f ) gives its bounds for ( μ , f ^ ) (\mu,\widehat{f}) ( μ , f ) , with V ω ( Z ^ ) V_{\omega}(\widehat{Z}) V ω ( Z ) under μ \mu μ . With embeddings in general position, which holds generically for neural embedders, Z ^ > 0 \widehat{Z} > 0 Z > 0 exactly when the pool contains at least K K K distinct strings of positive quality. On Ambrosia, a prompt whose pool is degenerate takes its pool from the next of our pools that is not.
A pool has Z ^ = 0 \widehat{Z} = 0 Z = 0 exactly when its weighted embeddings span fewer than K K K directions (Theorem A.1). On Ambrosia, 25 of 10,000 (prompt, pool) pairs at local sampling temperature 1 are degenerate.
The constant α N , K \alpha_{N,K} α N , K . Although α N , K \alpha_{N,K} α N , K cancels in P ^ ω \widehat{P}_{\omega} P ω (Theorem A.1), Theorem 5.1 requires E ω [ f ^ ω ( S ) ] = f ( S ) \mathbb{E}_{\omega}[\widehat{f}_{\omega}(S)] = f(S) E ω [ f ω ( S )] = f ( S ) , and α N , K \alpha_{N,K} α N , K is the constant that gives it (Theorem A.2). The 1 / N 1/N 1/ N in each column of B ^ \widehat{B} B (Eq. (8) ) normalizes as though all N K N^{K} N K ordered index tuples contributed to Eq. (12) , but only the ( N K ) K ! \binom{N}{K}K! ( K N ) K ! tuples with distinct indices do, since a repeated index repeats a column and gives determinant 0. Thus, 1 / α N , K 1/\alpha_{N,K} 1/ α N , K is the probability that K K K uniform draws from [ N ] [N] [ N ] are all distinct, and α N , K → 1 \alpha_{N,K} \to1 α N , K → 1 as N → ∞ N \to\infty N → ∞ .
Proof of thm:var-kl-mixture
Theorem 5.1 (Variance controls bias). For any well-behaved sketch ( μ , f ^ ) (\mu,\widehat{f}) ( μ , f ) ,
χ 2 ( P ∥ P ‾ ) ≤ V ω ( Z ^ ) Z 2 and KL ( P ∥ P ‾ ) ≤ log ( 1 + V ω ( Z ^ ) Z 2 ) ≤ V ω ( Z ^ ) Z 2 (17) \chi^{2}(P\mathbin{\|}\overline{P}) \le\frac{V_{\omega}(\widehat{Z})}{Z^{2}}
\quad\text{and}\quad
\operatorname{KL}(P\mathbin{\|}\overline{P}) \le\log\left(1+\frac{V_{\omega}(\widehat{Z})}{Z^{2}}\right) \le\frac{V_{\omega}(\widehat{Z})}{Z^{2}} \tag*{(17)} χ 2 ( P ∥ P ) ≤ Z 2 V ω ( Z ) and KL ( P ∥ P ) ≤ log ( 1 + Z 2 V ω ( Z ) ) ≤ Z 2 V ω ( Z ) (17)
The bound is general—it does not require i.i.d. proposals—and reduces to Theorem 2.1 of Huggins [16 ] when specialized to that case.
Proof.
Define the joint distribution P \mathbb{P} P of a pair ( ω , S ) (\omega,S) ( ω , S ) by first drawing the sketch randomness ω ∼ μ \omega\sim\mu ω ∼ μ and then drawing S ∼ P ^ ω ( ⋅ ) S \sim\widehat{P}_{\omega}(\cdot) S ∼ P ω ( ⋅ ) ; throughout, S S S denotes this random outcome and s s s a fixed value. Equivalently,
P ( ω , S ) = μ ( ω ) P ^ ω ( S ) (18) \mathbb{P}(\omega,S) = \mu(\omega)\widehat{P}_{\omega}(S) \tag*{(18)} P ( ω , S ) = μ ( ω ) P ω ( S ) (18)
Under P \mathbb{P} P , the marginal law of S S S is exactly P ‾ \overline{P} P :
P ( S = s ) = E ω [ P ^ ω ( s ) ] = P ‾ ( s ) (19) \mathbb{P}(S = s) = \mathbb{E}_{\omega}\left[\widehat{P}_{\omega}(s)\right] = \overline{P}(s) \tag*{(19)} P ( S = s ) = E ω [ P ω ( s ) ] = P ( s ) (19)
Define the nonnegative random variable
A ( ω ) ≔ Z ^ Z (20) A(\omega) \coloneqq\frac{\widehat{Z}}{Z} \tag*{(20)} A ( ω ) : = Z Z (20)
Note that A A A depends only on ω \omega ω . Using unbiasedness of f ^ ω \widehat{f}_{\omega} f ω ,
E ω [ Z ^ ] = E ω [ ∑ S f ^ ω ( S ) ] (21) \mathbb{E}_{\omega}[\widehat{Z}] = \mathbb{E}_{\omega}\left[\sum_{S}\widehat{f}_{\omega}(S)\right] \tag*{(21)} E ω [ Z ] = E ω [ S ∑ f ω ( S ) ] (21)
= ∑ S E ω [ f ^ ω ( S ) ] (22) = \sum_{S}\mathbb{E}_{\omega}[\widehat{f}_{\omega}(S)] \tag*{(22)} = S ∑ E ω [ f ω ( S )] (22)
Tonelli, since f ^ ω ( S ) ≥ 0 \widehat{f}_{\omega}(S) \ge0 f ω ( S ) ≥ 0
= ∑ S f ( S ) (23) = \sum_{S}f(S) \tag*{(23)} = S ∑ f ( S ) (23)
f ^ ω \widehat{f}_{\omega} f ω is unbiased (well-behaved)
= Z (24) = Z \tag*{(24)} = Z (24)
hence E ω [ A ( ω ) ] = 1 \mathbb{E}_{\omega}[A(\omega)] = 1 E ω [ A ( ω )] = 1 .
Crucially, for any fixed S S S ,
E ( ω , S ) ∼ P [ A ( ω ) 1 { S = S } ] = E ω ∼ μ [ A ( ω ) P ^ ω ( S ) ] (25) \mathbb{E}_{(\omega,S)\sim\mathbb{P}}[A(\omega)\mathbf{1}\{S=S\}]
= \mathbb{E}_{\omega\sim\mu}\left[A(\omega)\widehat{P}_{\omega}(S)\right] \tag*{(25)} E ( ω , S ) ∼ P [ A ( ω ) 1 { S = S }] = E ω ∼ μ [ A ( ω ) P ω ( S ) ] (25)
given ω \omega ω , S ∼ P ^ ω S\sim\widehat{P}_{\omega} S ∼ P ω
= E ω [ Z ^ Z ⋅ f ^ ω ( S ) Z ^ ] (26) = \mathbb{E}_{\omega}\left[\frac{\widehat{Z}}{Z}\cdot\frac{\widehat{f}_{\omega}(S)}{\widehat{Z}}\right] \tag*{(26)} = E ω [ Z Z ⋅ Z f ω ( S ) ] (26)
definitions of A A A and P ^ ω \widehat{P}_{\omega} P ω
= 1 Z E ω [ f ^ ω ( S ) ] (27) = \frac{1}{Z}\mathbb{E}_{\omega}[\widehat{f}_{\omega}(S)] \tag*{(27)} = Z 1 E ω [ f ω ( S )] (27)
canceling Z ^ > 0 \widehat{Z}>0 Z > 0
= f ( S ) Z (28) = \frac{f(S)}{Z} \tag*{(28)} = Z f ( S ) (28)
unbiasedness of f ^ ω \widehat{f}_{\omega} f ω
= P ( S ) (29) = P(S) \tag*{(29)} = P ( S ) (29)
For any S S S with P ‾ ( S ) > 0 \overline{P}(S)>0 P ( S ) > 0 , by definition of conditional expectation,
E ( ω , S ) ∼ P [ A ( ω ) ∣ S = S ] = E ( ω , S ) ∼ P [ A ( ω ) 1 { S = S } ] P ( S = S ) = P ( S ) P ‾ ( S ) (30) \mathbb{E}_{(\omega,S)\sim\mathbb{P}}[A(\omega)\mid S=S]
= \frac{\mathbb{E}_{(\omega,S)\sim\mathbb{P}}[A(\omega)\mathbf{1}\{S=S\}]}{\mathbb{P}(S=S)}
= \frac{P(S)}{\overline{P}(S)} \tag*{(30)} E ( ω , S ) ∼ P [ A ( ω ) ∣ S = S ] = P ( S = S ) E ( ω , S ) ∼ P [ A ( ω ) 1 { S = S }] = P ( S ) P ( S ) (30)
where the numerator uses step 3 and the denominator uses Eq. (19) from step 1.
Let r ( S ) ≔ P ( S ) / P ‾ ( S ) r(S)\coloneqq P(S)/\overline{P}(S) r ( S ) : = P ( S ) / P ( S ) be the likelihood ratio; it is defined P ‾ \overline{P} P -almost everywhere, since (29) forces P ( S ) = 0 P(S)=0 P ( S ) = 0 whenever P ‾ ( S ) = 0 \overline{P}(S)=0 P ( S ) = 0 , that is, P ≪ P ‾ P\ll\overline{P} P ≪ P . Then, E P ‾ [ r ] = ∑ S ∈ D P ( S ) = 1 \mathbb{E}_{\overline{P}}[r]=\sum_{S\in\mathcal{D}}P(S)=1 E P [ r ] = ∑ S ∈ D P ( S ) = 1 and
χ 2 ( P ∥ P ‾ ) = E P ‾ [ ( r − 1 ) 2 ] = E P ‾ [ r 2 ] − 1 (31) \chi^2(P\mathbin\Vert\overline{P})=\mathbb{E}_{\overline{P}}[(r-1)^2]=\mathbb{E}_{\overline{P}}[r^2]-1 \tag*{(31)} χ 2 ( P ∥ P ) = E P [( r − 1 ) 2 ] = E P [ r 2 ] − 1 (31)
By (30) and Jensen’s inequality applied to g ( x ) = x 2 g(x)=x^2 g ( x ) = x 2 ,14
E S ∼ P ‾ [ r ( S ) 2 ] = E S ∼ P ‾ [ ( E P [ A ( ω ) ∣ S = S ] ) 2 ] ≤ E P [ A ( ω ) 2 ] \begin{aligned}
\mathbb{E}_{S\sim\overline{P}}[r(S)^2]
= \mathbb{E}_{S\sim\overline{P}}\left[\left(\mathbb{E}_{\mathbb{P}}[A(\omega)\mid S=S]\right)^2\right] \\
&\le\mathbb{E}_{\mathbb{P}}[A(\omega)^2]
\end{aligned} E S ∼ P [ r ( S ) 2 ] = E S ∼ P [ ( E P [ A ( ω ) ∣ S = S ] ) 2 ] ≤ E P [ A ( ω ) 2 ]
Jensen on g ( x ) = x 2 g(x)=x^2 g ( x ) = x 2 , tower property
= E ω [ ( Z ^ Z ) 2 ] = \mathbb{E}_{\omega}\left[\left(\frac{\widehat{Z}}{Z}\right)^2\right] = E ω ( Z Z ) 2
A A A depends only on ω \omega ω
= E ω [ Z ^ 2 ] Z 2 = 1 + V a r ω ( Z ^ ) Z 2 (32) = \frac{\mathbb{E}_{\omega}[\widehat{Z}^2]}{Z^2}
= 1+\frac{\mathop{\mathrm{Var}}_{\omega}(\widehat{Z})}{Z^2} \tag*{(32)} = Z 2 E ω [ Z 2 ] = 1 + Z 2 Var ω ( Z ) (32)
E ω [ Z ^ ] = Z \mathbb{E}_{\omega}[\widehat{Z}]=Z E ω [ Z ] = Z from step 2
Substituting (32) into (31) gives the χ 2 \chi^2 χ 2 bound in (11).
For the KL bound, we use K L ( P ∥ P ‾ ) ≤ log ( 1 + χ 2 ( P ∥ P ‾ ) ) \mathrm{KL}(P\|\overline{P}) \le\log(1+\chi^2(P\|\overline{P})) KL ( P ∥ P ) ≤ log ( 1 + χ 2 ( P ∥ P )) .15
K L ( P ∥ P ‾ ) ≤ log E P ‾ [ r 2 ] = log ( 1 + χ 2 ( P ∥ P ‾ ) ) (33) \mathrm{KL}(P\|\overline{P}) \le\log\mathbb{E}_{\overline{P}}[r^2] = \log(1+\chi^2(P\|\overline{P})) \tag*{(33)} KL ( P ∥ P ) ≤ log E P [ r 2 ] = log ( 1 + χ 2 ( P ∥ P )) (33)
Combining (33) with (32) gives the first KL inequality in (11); the second follows from log ( 1 + x ) ≤ x \log(1+x) \le x log ( 1 + x ) ≤ x .
Proof of Theorem A.1
Proposition A.1 (PoolDPP-Sampling samples the sketched distribution). Fix a pool ω \omega ω . Then, Z ^ = α N , K ⋅ e K ( eig ( C ^ ) ) \widehat{Z} = \alpha_{N,K} \cdot e_K(\operatorname{eig}(\widehat{C})) Z = α N , K ⋅ e K ( eig ( C )) , so Z ^ = 0 \widehat{Z} = 0 Z = 0 exactly when rank ( C ^ ) < K \operatorname{rank}(\widehat{C}) < K rank ( C ) < K . If Z ^ > 0 \widehat{Z} > 0 Z > 0 , then the string set S = { y ( n ) } n ∈ I S = \{y^{(n)}\}_{n \in I} S = { y ( n ) } n ∈ I returned by PoolDPP-Sampling satisfies S ∼ P ^ ω S \sim\widehat{P}_{\omega} S ∼ P ω .
Proof. Throughout the proof, the pool ω = ( y ( 1 ) , … , y ( N ) ) \omega= (y^{(1)}, \ldots, y^{(N)}) ω = ( y ( 1 ) , … , y ( N ) ) is fixed, and all remaining randomness is due to Alg. 1. For the sampling claim, let Z ^ > 0 \widehat{Z} > 0 Z > 0 ; the derivation of Eq. (36) below does not use this. Invoked with the feature matrix B ^ ∈ R D × N \widehat{B} \in\mathbb{R}^{D \times N} B ∈ R D × N , Alg. 1 is an exact sampler for the K K K -DPP whose base set is the set of column indices [ N ] [N] [ N ] and whose kernel is L ^ = B ^ T B ^ \widehat{L} = \widehat{B}^{\mathsf{T}}\widehat{B} L = B T B ([25 Alg. 3] ); it returns an index set I ∈ ( [ N ] K ) I \in\binom{[N]}{K} I ∈ ( K [ N ] ) with probability (we write Pr L ^ \Pr_{\widehat{L}} Pr L for this law)
Pr L ^ [ I ] = det ( L ^ I ) ∑ I ′ ∈ ( [ N ] K ) det ( L ^ I ′ ) (34) \Pr_{\widehat{L}}[I] = \frac{\det(\widehat{L}_I)}{\sum_{I' \in\binom{[N]}{K}} \det(\widehat{L}_{I'})} \tag*{(34)} L Pr [ I ] = ∑ I ′ ∈ ( K [ N ] ) det ( L I ′ ) det ( L I ) (34)
By the standard identity relating the sum of principal K × K K \times K K × K minors of a symmetric matrix to the elementary symmetric polynomial of its eigenvalues ([25 §5.2.2] ), and because L ^ = B ^ T B ^ \widehat{L} = \widehat{B}^{\mathsf{T}}\widehat{B} L = B T B and C ^ = B ^ B ^ T \widehat{C} = \widehat{B}\widehat{B}^{\mathsf{T}} C = B B T share the same nonzero eigenvalues, the denominator of Eq. (34) equals e K ( eig ( L ^ ) ) = e K ( eig ( C ^ ) ) e_K(\operatorname{eig}(\widehat{L})) = e_K(\operatorname{eig}(\widehat{C})) e K ( eig ( L )) = e K ( eig ( C )) .
Now push Eq. (34) forward through the labeling map ι ( I ) : = { y ( n ) ∣ n ∈ I } \iota(I) \mathrel{\mathop:}= \{y^{(n)} \mid n \in I\} ι ( I ) : = { y ( n ) ∣ n ∈ I } , which sends the sampled index set to the string set that PoolDPP-Sampling returns. Two observations:
Collisions carry no mass. If I I I contains indices n ≠ n ′ n \ne n' n = n ′ with y ( n ) = y ( n ′ ) y^{(n)} = y^{(n')} y ( n ) = y ( n ′ ) , then columns n n n and n ′ n' n ′ of B ^ \widehat{B} B are identical (the weight w w w and the embedding ϕ \phi ϕ depend only on the string), so det ( L ^ I ) = 0 \det(\widehat{L}_I) = 0 det ( L I ) = 0 and Pr L ^ [ I ] = 0 \Pr_{\widehat{L}}[I] = 0 Pr L [ I ] = 0 . Hence, every index set with positive probability satisfies ∣ ι ( I ) ∣ = K |\iota(I)| = K ∣ ι ( I ) ∣ = K .
The index sum is partitioned. Each index set I ∈ ( [ N ] K ) I \in\binom{[N]}{K} I ∈ ( K [ N ] ) with ∣ ι ( I ) ∣ = K |\iota(I)| = K ∣ ι ( I ) ∣ = K appears in the inner sum of Eq. (12) for exactly one string set, namely S = ι ( I ) S = \iota(I) S = ι ( I ) ; index sets with ∣ ι ( I ) ∣ < K |\iota(I)| < K ∣ ι ( I ) ∣ < K appear in none, and contribute 0 0 0 wherever they would appear by observation 1.
Therefore, for any S ∈ ( Σ ∗ K ) S \in\binom{\Sigma^*}{K} S ∈ ( K Σ ∗ ) ,
Pr L ^ [ ι ( I ) = S ] = ∑ I : ι ( I ) = S det ( L ^ I ) ∑ I ′ ∈ ( [ N ] K ) det ( L ^ I ′ ) = α N , K − 1 f ^ ω ( S ) α N , K − 1 Z ^ = P ^ ω ( S ) (35) \Pr_{\widehat{L}}[\iota(I) = S] = \frac{\sum_{I:\iota(I)=S}\det(\widehat{L}_I)}{\sum_{I' \in\binom{[N]}{K}}\det(\widehat{L}_{I'})} = \frac{\alpha_{N,K}^{-1}\widehat{f}_{\omega}(S)}{\alpha_{N,K}^{-1}\widehat{Z}} = \widehat{P}_{\omega}(S) \tag*{(35)} L Pr [ ι ( I ) = S ] = ∑ I ′ ∈ ( K [ N ] ) det ( L I ′ ) ∑ I : ι ( I ) = S det ( L I ) = α N , K − 1 Z α N , K − 1 f ω ( S ) = P ω ( S ) (35)
where the numerator uses the definition of f ^ ω \widehat{f}_{\omega} f ω in Eq. (12) , and the denominator uses
Z ^ = ∑ S ∈ ( Σ ∗ K ) f ^ ω ( S ) = α N , K ∑ S ∈ ( Σ ∗ K ) ∑ I : ι ( I ) = S det ( L ^ I ) = α N , K ∑ I ∈ ( [ N ] K ) det ( L ^ I ) = α N , K ⋅ e K ( eig ( C ^ ) ) (36) \widehat{Z} = \sum_{S \in\binom{\Sigma^*}{K}}\widehat{f}_{\omega}(S) = \alpha_{N,K}\sum_{S \in\binom{\Sigma^*}{K}}\sum_{I:\iota(I)=S}\det(\widehat{L}_I) = \alpha_{N,K}\sum_{I \in\binom{[N]}{K}}\det(\widehat{L}_I) = \alpha_{N,K}\cdot e_K(\operatorname{eig}(\widehat{C})) \tag*{(36)} Z = S ∈ ( K Σ ∗ ) ∑ f ω ( S ) = α N , K S ∈ ( K Σ ∗ ) ∑ I : ι ( I ) = S ∑ det ( L I ) = α N , K I ∈ ( K [ N ] ) ∑ det ( L I ) = α N , K ⋅ e K ( eig ( C )) (36)
with the third equality by observation 2. This proves the sampling claim and the identity for Z ^ \widehat{Z} Z , which holds for every pool. Since C ^ \widehat{C} C is positive semidefinite, its eigenvalues are nonnegative, so e K ( eig ( C ^ ) ) = 0 e_K(\operatorname{eig}(\widehat{C})) = 0 e K ( eig ( C )) = 0 exactly when fewer than K K K of them are positive, that is, when rank ( C ^ ) < K \operatorname{rank}(\widehat{C}) < K rank ( C ) < K . Note that Eq. (36) also shows that Z ^ \widehat{Z} Z is computable in O ( D 3 + D K ) O(D^3 + DK) O ( D 3 + D K ) time from the eigenvalues of C ^ \widehat{C} C (see footnote 16), although PoolDPP needs only whether it is zero. ▪
Proof of prop:PoolDPP-well-behaved
Proposition A.2 (PoolDPP is well-behaved). For any K ≥ 1 K \ge1 K ≥ 1 , N ≥ K N \ge K N ≥ K , and proposal q q q with κ ≪ q \kappa\ll q κ ≪ q , the construction in Eq. (12) is unbiased: E ω [ f ^ ω ( S ) ] = det ( L S ) 1 { ∣ S ∣ = K } \mathbb{E}_{\omega}[\widehat{f}_{\omega}(S)] = \det(L_S)\mathbf{1}\{|S|=K\} E ω [ f ω ( S )] = det ( L S ) 1 { ∣ S ∣ = K } . If, additionally, ρ < ∞ \rho< \infty ρ < ∞ , then E ω [ Z ^ 2 ] < ∞ \mathbb{E}_{\omega}[\widehat{Z}^{2}] < \infty E ω [ Z 2 ] < ∞ and PoolDPP is well-behaved.
Proof. The sketch randomness is ω = ( y ( 1 ) , … , y ( N ) ) \omega= (y^{(1)}, \ldots, y^{(N)}) ω = ( y ( 1 ) , … , y ( N ) ) with y ( n ) ∼ i . i . d . q y^{(n)} \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} q y ( n ) ∼ i.i.d. q . We verify the two requirements of being well-behaved (Theorem 5.1’s preconditions): unbiasedness and a finite second moment.
Unbiasedness: E ω [ f ^ ω ( S ) ] = f ( S ) \mathbb{E}_{\omega}[\widehat{f}_{\omega}(S)] = f(S) E ω [ f ω ( S )] = f ( S ) for every S S S .
If ∣ S ∣ ≠ K |S| \ne K ∣ S ∣ = K , both sides vanish: f ( S ) = 0 f(S)=0 f ( S ) = 0 by the size indicator, and f ^ ω ( S ) = 0 \widehat{f}_{\omega}(S)=0 f ω ( S ) = 0 because any index set I I I with ∣ I ∣ = K |I|=K ∣ I ∣ = K whose image is S S S must repeat a string, which repeats a column of B ^ \widehat{B} B and forces det ( L ^ I ) = 0 \det(\widehat{L}_I)=0 det ( L I ) = 0 .
So fix S = { y 1 , … , y K } ∈ ( Σ ∗ K ) S=\{y_1,\ldots,y_K\}\in\binom{\Sigma^*}{K} S = { y 1 , … , y K } ∈ ( K Σ ∗ ) , a set of K K K distinct strings, whence f ( S ) = det ( L S ) f(S)=\det(L_S) f ( S ) = det ( L S ) . Fix also an index set I ∈ ( [ N ] K ) I\in\binom{[N]}{K} I ∈ ( K [ N ] ) and consider the event { y ( n ) ∣ n ∈ I } = S \{y^{(n)}\mid n\in I\}=S { y ( n ) ∣ n ∈ I } = S . Because ∣ I ∣ = ∣ S ∣ = K |I|=|S|=K ∣ I ∣ = ∣ S ∣ = K , this event holds if and only if the K K K i.i.d. draws at the positions of I I I realize the K K K elements of S S S under some bijection; there are K ! K! K ! bijections, each occurring with probability ∏ j = 1 K q ( y j ) \prod_{j=1}^{K}q(y_j) ∏ j = 1 K q ( y j ) , so
Pr ω [ { y ( n ) ∣ n ∈ I } = S ] = K ! ∏ j = 1 K q ( y j ) (37) \Pr_{\omega}\left[\{y^{(n)}\mid n\in I\}=S\right]=K!\prod_{j=1}^{K}q(y_j) \tag*{(37)} ω Pr [ { y ( n ) ∣ n ∈ I } = S ] = K ! j = 1 ∏ K q ( y j ) (37)
On this event, det ( L ^ I ) \det(\widehat{L}_I) det ( L I ) takes the same value under every bijection: the columns of B ^ \widehat{B} B indexed by I I I are { w ( y j ) / N Φ ( y j ) } j = 1 K \{\sqrt{w(y_j)/N}\Phi(y_j)\}_{j=1}^{K} { w ( y j ) / N Φ ( y j ) } j = 1 K up to a permutation, which leaves the Gram determinant unchanged, and factoring w ( y j ) / N \sqrt{w(y_j)/N} w ( y j ) / N out of each row and column,
det ( L ^ I ) = det ( [ w ( y i ) w ( y j ) N Φ ( y i ) T Φ ( y j ) ] i , j = 1 K ) = N − K ∏ j = 1 K w ( y j ) ⋅ det ( Φ S T Φ S ) (38) \det(\widehat{L}_I)=\det\left(\left[\frac{\sqrt{w(y_i)w(y_j)}}{N}\Phi(y_i)^{\mathsf T}\Phi(y_j)\right]_{i,j=1}^{K}\right)=N^{-K}\prod_{j=1}^{K}w(y_j)\cdot\det(\Phi_S^{\mathsf T}\Phi_S) \tag*{(38)} det ( L I ) = det [ N w ( y i ) w ( y j ) Φ ( y i ) T Φ ( y j ) ] i , j = 1 K = N − K j = 1 ∏ K w ( y j ) ⋅ det ( Φ S T Φ S ) (38)
Combining (29) and (30) with the cancellation q ( y ) w ( y ) = κ ( y ) q(y)w(y)=\kappa(y) q ( y ) w ( y ) = κ ( y ) and the determinant decomposition det ( L S ) = ∏ j = 1 K κ ( y j ) ⋅ det ( Φ S T Φ S ) \det(L_S)=\prod_{j=1}^{K}\kappa(y_j)\cdot\det(\Phi_S^{\mathsf T}\Phi_S) det ( L S ) = ∏ j = 1 K κ ( y j ) ⋅ det ( Φ S T Φ S ) from §3,
E ω [ det ( L ^ I ) 1 { { y ( n ) ∣ n ∈ I } = S } ] = K ! ∏ j = 1 K q ( y j ) N − K ∏ j = 1 K w ( y j ) ⋅ det ( Φ S T Φ S ) = K ! N K det ( L S ) (39) \mathbb{E}_{\omega}\left[\det(\widehat{L}_I)\mathbf{1}\left\{\{y^{(n)}\mid n\in I\}=S\right\}\right]
=K!\prod_{j=1}^{K}q(y_j)N^{-K}\prod_{j=1}^{K}w(y_j)\cdot\det(\Phi_S^{\mathsf T}\Phi_S)
=\frac{K!}{N^K}\det(L_S) \tag*{(39)} E ω [ det ( L I ) 1 { { y ( n ) ∣ n ∈ I } = S } ] = K ! j = 1 ∏ K q ( y j ) N − K j = 1 ∏ K w ( y j ) ⋅ det ( Φ S T Φ S ) = N K K ! det ( L S ) (39)
This value does not depend on I I I , and there are ( N K ) \binom{N}{K} ( K N ) index sets, so
E ω [ f ^ ω ( S ) ] = α N , K ∑ I ∈ ( [ N ] K ) E ω [ det ( L ^ I ) 1 { { y ( n ) ∣ n ∈ I } = S } ] = α N , K ⋅ ( N K ) ⋅ K ! N K ⋅ det ( L S ) = α N , K ⋅ ( N ) K N K ⋅ det ( L S ) = det ( L S ) = f ( S ) (40) \begin{aligned}
\mathbb{E}_{\omega}[\widehat{f}_{\omega}(S)]
&=\alpha_{N,K}\sum_{I\in\binom{[N]}{K}}\mathbb{E}_{\omega}\left[\det(\widehat{L}_I)\mathbf{1}\left\{\{y^{(n)}\mid n\in I\}=S\right\}\right]\\
&=\alpha_{N,K}\cdot\binom{N}{K}\cdot\frac{K!}{N^K}\cdot\det(L_S)\\
&=\alpha_{N,K}\cdot\frac{(N)_K}{N^K}\cdot\det(L_S)\\
&=\det(L_S)=f(S) \tag*{(40)}
\end{aligned} E ω [ f ω ( S )] = α N , K I ∈ ( K [ N ] ) ∑ E ω [ det ( L I ) 1 { { y ( n ) ∣ n ∈ I } = S } ] = α N , K ⋅ ( K N ) ⋅ N K K ! ⋅ det ( L S ) = α N , K ⋅ N K ( N ) K ⋅ det ( L S ) = det ( L S ) = f ( S ) (40)
The counting in Eq. (40) is exactly the mismatch described in §5: the raw index sum recovers only the fraction ( N ) K / N K (N)_K/N^K ( N ) K / N K of the mass that the 1 / N 1/N 1/ N -normalization of B ^ \widehat{B} B presumes—the collision-free fraction of ordered index tuples—and α N , K \alpha_{N,K} α N , K restores the remainder. Summing Eq. (40) over S S S then gives E ω [ Z ^ ] = ∑ S ∈ D f ( S ) = Z \mathbb{E}_{\omega}[\widehat{Z}]=\sum_{S\in\mathcal{D}}f(S)=Z E ω [ Z ] = ∑ S ∈ D f ( S ) = Z .
Finite second moment: E ω [ Z ^ 2 ] < ∞ \mathbb{E}_{\omega}[\widehat{Z}^{2}] < \infty E ω [ Z 2 ] < ∞ .
Theorem 5.2 derives the finite second moment from ρ < ∞ \rho< \infty ρ < ∞ , which holds whenever E q [ w 2 ] < ∞ \mathbb{E}_{q}[w^{2}] < \infty E q [ w 2 ] < ∞ (§A.7). With ρ < ∞ \rho< \infty ρ < ∞ , the hypothesis of the proposition, the proof of Eq. (15) also gives the explicit bound E ω [ Z ^ 2 ] / Z 2 ≤ e θ − 1 + a 0 \mathbb{E}_{\omega}[\widehat{Z}^{2}]/Z^{2} \le e^{\theta} - 1 + a_{0} E ω [ Z 2 ] / Z 2 ≤ e θ − 1 + a 0 , with θ = K 2 ρ / ( N − K + 1 ) \theta= K^{2}\rho/(N - K + 1) θ = K 2 ρ / ( N − K + 1 ) .
■
Proof of rem:rao-blackwell
Remark A.3 (Rao–Blackwellization interpretation). The sketch in Eq. (12) admits a Rao–Blackwell interpretation. Consider the naive importance sampler that draws K K K strings y 1 , … , y K y_1,\ldots,y_K y 1 , … , y K i.i.d. from the proposal, i.e., one draw of a K K K -tuple from the product distribution q ⊗ K q^{\otimes K} q ⊗ K , and estimates f ( S ) f(S) f ( S ) by f ~ ( S ) ≔ 1 K ! ∏ j = 1 K w ( y j ) ⋅ det ( Φ S T Φ S ) ⋅ 1 { { y 1 , … , y K } = S } \tilde{f}(S) \coloneqq\frac{1}{K!}\prod_{j=1}^{K}w(y_j)\cdot\det(\boldsymbol{\Phi}_{S}^{\mathsf{T}}\boldsymbol{\Phi}_{S})\cdot\mathbb{1}\{\{y_1,\ldots,y_K\}=S\} f ~ ( S ) : = K ! 1 ∏ j = 1 K w ( y j ) ⋅ det ( Φ S T Φ S ) ⋅ 1 {{ y 1 , … , y K } = S } , which is unbiased by the same cancellation q ⋅ w = κ q\cdot w=\kappa q ⋅ w = κ as in Theorem A.2. One way to realize the K K K i.i.d. draws is to draw the pool of N ≥ K N\ge K N ≥ K i.i.d. samples first, and then read off the strings at K K K pool positions chosen uniformly at random without replacement. The sketched weight f ~ ω ( S ) \tilde{f}_{\omega}(S) f ~ ω ( S ) is precisely the conditional expectation of f ~ ( S ) \tilde{f}(S) f ~ ( S ) given the pool, with α N , K \alpha_{N,K} α N , K emerging as the ratio between the 1 / N K 1/N^K 1/ N K normalization inside B ^ \widehat{B} B and the 1 / ( N K ) K ! 1/\binom{N}{K}K! 1/ ( K N ) K ! probability of each ordered position choice. The Rao–Blackwell theorem then guarantees variance reduction: V ω ( f ~ ω ( S ) ) ≤ V q ⊗ K ( f ~ ( S ) ) \mathbb{V}_{\omega}(\tilde{f}_{\omega}(S))\le\mathbb{V}_{q^{\otimes K}}(\tilde{f}(S)) V ω ( f ~ ω ( S )) ≤ V q ⊗ K ( f ~ ( S )) for every S S S . Theorem 5.2 quantifies the gain: the naive sampler is PoolDPP with N = K N=K N = K , where a K = 1 a_K=1 a K = 1 and the relative variance is V q ⊗ K ( u K ) \mathbb{V}_{q^{\otimes K}}(u_K) V q ⊗ K ( u K ) ; in a pool of size N N N , this term enters with weight a K = 1 / ( N K ) a_K=1/\binom{N}{K} a K = 1/ ( K N ) . By Eq. (45) , the relative variance at pool size N N N is at most ( K / N ) V q ⊗ K ( u K ) (K/N)\mathbb{V}_{q^{\otimes K}}(u_K) ( K / N ) V q ⊗ K ( u K ) , a factor of at least N / K N/K N / K below the naive sampler’s.
Proof. Let ω = ( y ( 1 ) , … , y ( N ) ) ∼ i . i . d . q \omega=(y^{(1)},\ldots,y^{(N)})\mathrel{\stackrel{\mathrm{i.i.d.}}{\sim}}q ω = ( y ( 1 ) , … , y ( N ) ) ∼ i.i.d. q be the pool, and—independently of the pool—draw an ordered tuple ( n 1 , … , n K ) (n_1,\ldots,n_K) ( n 1 , … , n K ) of distinct positions, uniformly among the ( N K ) K ! \binom{N}{K}K! ( K N ) K ! such tuples. Reading off y ~ j ≔ y ( n j ) \tilde{y}_j\coloneqq y^{(n_j)} y ~ j : = y ( n j ) yields K K K strings that are marginally i.i.d. from q q q : the strings at any K K K fixed distinct positions of an i.i.d. pool are i.i.d., and the positions are chosen independently of the pool. This is therefore a valid realization of the draw from q ⊗ K q^{\otimes K} q ⊗ K used by the naive sampler of Theorem A.3.
Fix S ∈ ( Y ∗ K ) S\in\binom{\mathcal{Y}^{*}}{K} S ∈ ( K Y ∗ ) and take the conditional expectation of the naive weight f ~ ( S ) \tilde{f}(S) f ~ ( S ) over the position choice, holding the pool fixed. Grouping the ( N K ) K ! \binom{N}{K}K! ( K N ) K ! ordered position tuples by their underlying index set I ∈ ( [ N ] K ) I\in\binom{[N]}{K} I ∈ ( K [ N ] ) —K ! K! K ! orderings each, all yielding the same summand—we obtain
E [ f ~ ( S ) ∣ ω ] = 1 ( N K ) ∑ I ∈ ( [ N ] K ) 1 K ! ∏ j = 1 K w ( n j ) ⋅ det ( Φ S T Φ S ) ⋅ 1 { { y ( n 1 ) , … , y ( n K ) } = S } (41) \mathbb{E}\left[\tilde{f}(S)\mid\omega\right]
=\frac{1}{\binom{N}{K}}\sum_{I\in\binom{[N]}{K}}\frac{1}{K!}\prod_{j=1}^{K}w^{(n_j)}
\cdot\det(\boldsymbol{\Phi}_{S}^{\mathsf{T}}\boldsymbol{\Phi}_{S})\cdot\mathbb{1}\left\{\{y^{(n_1)},\ldots,y^{(n_K)}\}=S\right\} \tag*{(41)} E [ f ~ ( S ) ∣ ω ] = ( K N ) 1 I ∈ ( K [ N ] ) ∑ K ! 1 j = 1 ∏ K w ( n j ) ⋅ det ( Φ S T Φ S ) ⋅ 1 { { y ( n 1 ) , … , y ( n K ) } = S } (41)
= 1 ( N K ) ∑ I ∈ ( [ N ] K ) ∏ n ∈ I w ( n ) ⋅ det ( Φ S T Φ S ) ⋅ 1 { { y ( n ) ∣ n ∈ I } = S } (42) =\frac{1}{\binom{N}{K}}\sum_{I\in\binom{[N]}{K}}\prod_{n\in I}w^{(n)}
\cdot\det(\boldsymbol{\Phi}_{S}^{\mathsf{T}}\boldsymbol{\Phi}_{S})\cdot\mathbb{1}\left\{\{y^{(n)}\mid n\in I\}=S\right\} \tag*{(42)} = ( K N ) 1 I ∈ ( K [ N ] ) ∑ n ∈ I ∏ w ( n ) ⋅ det ( Φ S T Φ S ) ⋅ 1 { { y ( n ) ∣ n ∈ I } = S } (42)
= N K ( N K ) ∑ I ∈ ( [ N ] K ) { y ( n ) ∣ n ∈ I } = S det ( L I ) (43) =\frac{N^K}{\binom{N}{K}}\sum_{\substack{I\in\binom{[N]}{K}\\\{y^{(n)}\mid n\in I\}=S}}\det(\boldsymbol{L}_I) \tag*{(43)} = ( K N ) N K I ∈ ( K [ N ] ) { y ( n ) ∣ n ∈ I } = S ∑ det ( L I ) (43)
= α N , K ∑ I ⊆ [ N ] , ∣ I ∣ = K { y ( n ) ∣ n ∈ I } = S det ( L ^ I ) = f ~ ω ( S ) (44) =\alpha_{N,K}\sum_{\substack{I\subseteq[N],\,|I|=K\\\{y^{(n)}\mid n\in I\}=S}}\det(\widehat{\boldsymbol{L}}_I)=\tilde{f}_{\omega}(S) \tag*{(44)} = α N , K I ⊆ [ N ] , ∣ I ∣ = K { y ( n ) ∣ n ∈ I } = S ∑ det ( L I ) = f ~ ω ( S ) (44)
So the sketched weight is precisely the conditional expectation of the naive weight given the pool, with α N , K = N K / ( N K ) \alpha_{N,K}=N^K/\binom{N}{K} α N , K = N K / ( K N ) arising as the ratio between the N − K N^{-K} N − K normalization inside det ( L ^ I ) \det(\widehat{\boldsymbol{L}}_I) det ( L I ) (via the 1 / N 1/N 1/ N factor in each column of B ^ \widehat{B} B ) and the 1 / ( N K ) K ! 1/\binom{N}{K}K! 1/ ( K N ) K ! probability of each ordered position choice. Since conditioning preserves the mean and cannot increase variance (law of total variance), E ω [ f ~ ω ( S ) ] = E q ⊗ K [ f ~ ( S ) ] = f ( S ) \mathbb{E}_{\omega}[\tilde{f}_{\omega}(S)]=\mathbb{E}_{q^{\otimes K}}[\tilde{f}(S)]=f(S) E ω [ f ~ ω ( S )] = E q ⊗ K [ f ~ ( S )] = f ( S ) and V ω ( f ~ ω ( S ) ) ≤ V q ⊗ K ( f ~ ( S ) ) \mathbb{V}_{\omega}(\tilde{f}_{\omega}(S))\le\mathbb{V}_{q^{\otimes K}}(\tilde{f}(S)) V ω ( f ~ ω ( S )) ≤ V q ⊗ K ( f ~ ( S )) , as claimed.■
Proof of thm:zfree
Throughout, ( n ) k ≔ n ( n − 1 ) ⋯ ( n − k + 1 ) (n)_k \coloneqq n(n-1)\cdots(n-k+1) ( n ) k : = n ( n − 1 ) ⋯ ( n − k + 1 ) .
Overlap intuition. For K = 2 K = 2 K = 2 , Z ^ \widehat{Z} Z averages contributions from all pool pairs. The pairs { 1 , 2 } \{1,2\} { 1 , 2 } and { 3 , 4 } \{3,4\} { 3 , 4 } use independent draws. The pairs { 1 , 2 } \{1,2\} { 1 , 2 } and { 1 , 3 } \{1,3\} { 1 , 3 } share only the first draw: once it is fixed, their remaining draws are independent, so their covariance is the variance of their common conditional mean. For general K K K , the same calculation groups pairs of subsets by how many positions they share.
Remarks on the statement. The coefficients a c a_c a c are the hypergeometric law of the overlap ∣ I ∩ J ∣ |I \cap J| ∣ I ∩ J ∣ between two independent uniform K K K -subsets of [ N ] [N] [ N ] , with mean K 2 / N K^2/N K 2 / N . Since Z ^ \widehat{Z} Z is an average of one symmetric function over all size-K K K subsets of pool positions, and the pool is i.i.d., two terms covary only through the positions they share; the pool size enters only through the probability of each overlap. Since V q ⊗ c ( u c ) / c \mathbb{V}_{q^{\otimes c}}(u_c)/c V q ⊗ c ( u c ) / c is nondecreasing in c c c ([14 ] ), at every pool size
K 2 N V q ( u 1 ) ≤ V ω ( Z ^ ) Z 2 ≤ K N V q ⊗ K ( u K ) (45) \frac{K^2}{N}\mathbb{V}_q(u_1) \le\frac{\mathbb{V}_\omega(\widehat{Z})}{Z^2} \le\frac{K}{N}\mathbb{V}_{q^{\otimes K}}(u_K) \tag*{(45)} N K 2 V q ( u 1 ) ≤ Z 2 V ω ( Z ) ≤ N K V q ⊗ K ( u K ) (45)
and the lower bound is attained up to O ( 1 / N 2 ) O(1/N^2) O ( 1/ N 2 ) as N → ∞ N \to\infty N → ∞ (§A.7). At K = 1 K = 1 K = 1 , Eq. (14) is the importance-sampling relative variance V q ( w ) / ( N E q [ w ] 2 ) \mathbb{V}_q(w)/(N\mathbb{E}_q[w]^2) V q ( w ) / ( N E q [ w ] 2 ) . In general, u 1 = π 1 / q u_1 = \pi_1/q u 1 = π 1 / q is at most C 0 w C_0w C 0 w for a constant C 0 C_0 C 0 set by the spectrum of C C C , so ρ ≤ C 0 2 E q [ w 2 ] \rho\le C_0^2\mathbb{E}_q[w^2] ρ ≤ C 0 2 E q [ w 2 ] (§A.7). To interpret the numerator divided by ( K ) c (K)_c ( K ) c , draw a target set and choose c c c of its members uniformly without replacement, in order: the ratio is the probability of obtaining the tuple ( y 1 , … , y c ) (y_1,\ldots,y_c) ( y 1 , … , y c ) . Thus, u c u_c u c compares this target tuple distribution with c c c independent proposal draws, has mean 1 1 1 , and is unchanged by rescaling κ \kappa κ .
Theorem 5.2 (Finite-sample bound). For any K ≥ 1 K \ge1 K ≥ 1 , N ≥ K N \ge K N ≥ K , and proposal q q q with κ ≪ q \kappa\ll q κ ≪ q ,
V ω ( Z ^ ) Z 2 = ∑ c = 1 K a c V q ⊗ c ( u c ) , a c ≔ ( K c ) ( N − K K − c ) ( N K ) (46) \frac{\mathbb{V}_\omega(\widehat{Z})}{Z^2} = \sum_{c=1}^{K} a_c \mathbb{V}_{q^{\otimes c}}(u_c), \qquad a_c \coloneqq\frac{\binom{K}{c}\binom{N-K}{K-c}}{\binom{N}{K}} \tag*{(46)} Z 2 V ω ( Z ) = c = 1 ∑ K a c V q ⊗ c ( u c ) , a c : = ( K N ) ( c K ) ( K − c N − K ) (46) If ρ < ∞ \rho< \infty ρ < ∞ , then for any fallback
KL ( P ∥ P ‾ ) ≤ log ( e θ − 1 + a 0 ) ≤ θ ≔ K 2 ρ N − K + 1 (47) \operatorname{KL}(P\Vert\overline{P}) \le\log(e^\theta- 1 + a_0) \le\theta\coloneqq\frac{K^2\rho}{N-K+1} \tag*{(47)} KL ( P ∥ P ) ≤ log ( e θ − 1 + a 0 ) ≤ θ : = N − K + 1 K 2 ρ (47) where a 0 = ( N − K K ) / ( N K ) a_0 = \binom{N-K}{K}/\binom{N}{K} a 0 = ( K N − K ) / ( K N ) is the formula of Eq. (14) at c = 0 c = 0 c = 0 .
Proof. We prove the identity (14) first, and then the bound (15).
Proof of the identity (14). Subset average. Write Y I = ( y ( n ) ) n ∈ I Y_I = (y^{(n)})_{n\in I} Y I = ( y ( n ) ) n ∈ I and Φ = [ ϕ ( y 1 ) , … , ϕ ( y K ) ] \Phi= [\phi(y_1),\ldots,\phi(y_K)] Φ = [ ϕ ( y 1 ) , … , ϕ ( y K )] . Pulling the factor w ( y ( n ) ) / N \sqrt{w(y^{(n)})/N} w ( y ( n ) ) / N of each column of B ^ \widehat{B} B out of each determinant in Eq. (12) and using α N , K N − K = 1 / [ ( N K ) K ! ] \alpha_{N,K}N^{-K} = 1/[\binom{N}{K}K!] α N , K N − K = 1/ [ ( K N ) K !] gives
h ( y 1 , … , y K ) ≔ 1 K ! ∏ j = 1 K w ( y j ) det ( Φ T Φ ) h(y_1,\ldots,y_K) \coloneqq\frac{1}{K!}\prod_{j=1}^{K}w(y_j)\det(\Phi^\mathsf{T}\Phi) h ( y 1 , … , y K ) : = K ! 1 j = 1 ∏ K w ( y j ) det ( Φ T Φ )
Z ^ = 1 ( N K ) ∑ I ⊆ [ N ] ∣ I ∣ = K h ( Y I ) (48) \widehat{Z} = \frac{1}{\binom{N}{K}}\sum_{\substack{I\subseteq[N]\\ |I|=K}} h(Y_I) \tag*{(48)} Z = ( K N ) 1 I ⊆ [ N ] ∣ I ∣ = K ∑ h ( Y I ) (48)
The function h h h is symmetric and vanishes on repeated strings, because a repeated string repeats a column of Φ \Phi Φ .
Conditional mean. Fix distinct y 1 , … , y c y_1,\ldots,y_c y 1 , … , y c and let S 0 = { y 1 , … , y c } S_0 = \{y_1,\ldots,y_c\} S 0 = { y 1 , … , y c } . Averaging over the remaining K − c K-c K − c independent proposal draws cancels their proposal factors, since q w = κ qw = \kappa q w = κ . Each completed set containing S 0 S_0 S 0 has ( K − c ) ! (K-c)! ( K − c )! orderings of its remaining members, so
E Y c + 1 , … , Y K ∼ i . i . d . q [ h ( y 1 , … , y c , Y c + 1 , … , Y K ) ] = ( K − c ) ! K ! ∏ j ≤ c q ( y j ) ∑ S ⊇ S 0 ∣ S ∣ = K det ( L S ) = Z u c ( y 1 , … , y c ) (49) \begin{aligned}
\mathbb{E}_{Y_{c+1},\ldots,Y_K\stackrel{\mathrm{i.i.d.}}{\sim}q}\left[h(y_1,\ldots,y_c,Y_{c+1},\ldots,Y_K)\right]
= \frac{(K-c)!}{K!\prod_{j\le c}q(y_j)}
\sum_{\substack{S\supseteq S_0\\ |S|=K}}\det(L_S) \\
&= Zu_c(y_1,\ldots,y_c) \tag*{(49)}
\end{aligned} E Y c + 1 , … , Y K ∼ i.i.d. q [ h ( y 1 , … , y c , Y c + 1 , … , Y K ) ] = K ! ∏ j ≤ c q ( y j ) ( K − c )! S ⊇ S 0 ∣ S ∣ = K ∑ det ( L S ) = Z u c ( y 1 , … , y c ) (49)
Both sides are zero on repeated strings. The ordered-tuple interpretation of Eq. (13) gives E q ⊗ c [ u c ] = 1 \mathbb{E}_{q\otimes c}[u_c] = 1 E q ⊗ c [ u c ] = 1 , hence E q ⊗ K [ h ] = Z \mathbb{E}_{q\otimes K}[h] = Z E q ⊗ K [ h ] = Z .
Covariances and overlap counts. If I ∩ J = ∅ I\cap J = \varnothing I ∩ J = ∅ , the contributions are independent and their covariance is zero. Otherwise, condition on their c = ∣ I ∩ J ∣ c = \lvert I\cap J\rvert c = ∣ I ∩ J ∣ shared draws. The remaining draws are independent, and both conditional means equal Z u c ( Y I ∩ J ) Z u_c(Y_{I\cap J}) Z u c ( Y I ∩ J ) by Eq. (49) , giving
Cov ( h ( Y I ) , h ( Y J ) ) = V q ⊗ c ( E [ h ( Y I ) ∣ Y I ∩ J ] ) = Z 2 V q ⊗ c ( u c ) (50) \operatorname{Cov}(h(Y_I),h(Y_J))=\mathbb{V}_{q\otimes c}\left(\mathbb{E}[h(Y_I)\mid Y_{I\cap J}]\right)=Z^2\mathbb{V}_{q\otimes c}(u_c) \tag*{(50)} Cov ( h ( Y I ) , h ( Y J )) = V q ⊗ c ( E [ h ( Y I ) ∣ Y I ∩ J ] ) = Z 2 V q ⊗ c ( u c ) (50)
For each I I I , choose c c c shared positions from I I I and K − c K-c K − c other positions from its complement: there are ( K c ) ( N − K K − c ) \binom{K}{c}\binom{N-K}{K-c} ( c K ) ( K − c N − K ) choices of J J J . Expanding the variance in Eq. (48) and grouping these pairs therefore gives
V ω ( Z ^ ) Z 2 = ∑ I , J Cov ( h ( Y I ) , h ( Y J ) ) ( N K ) 2 Z 2 = ∑ c = 1 K a c V q ⊗ c ( u c ) (51) \begin{aligned}
\frac{\mathbb{V}_{\omega}(\widehat{Z})}{Z^2}
=
\frac{\sum_{I,J}\operatorname{Cov}(h(Y_I),h(Y_J))}
{\binom{N}{K}^2Z^2} \\
&=\sum_{c=1}^{K}a_c\mathbb{V}_{q\otimes c}(u_c) \tag*{(51)}
\end{aligned} Z 2 V ω ( Z ) = ( K N ) 2 Z 2 ∑ I , J Cov ( h ( Y I ) , h ( Y J )) = c = 1 ∑ K a c V q ⊗ c ( u c ) (51)
where I I I and J J J each range over ( [ N ] K ) \binom{[N]}{K} ( K [ N ] ) . This is Hoeffding’s variance formula for U U U -statistics [14 ] , with the conditional means given by Eq. (49) . This computation assumes E q ⊗ K [ u K 2 ] < ∞ \mathbb{E}_{q\otimes K}[u_K^2] < \infty E q ⊗ K [ u K 2 ] < ∞ , which makes every covariance finite, since u c u_c u c is a conditional mean of u K u_K u K and so V q ⊗ c ( u c ) ≤ V q ⊗ K ( u K ) \mathbb{V}_{q\otimes c}(u_c) \le\mathbb{V}_{q\otimes K}(u_K) V q ⊗ c ( u c ) ≤ V q ⊗ K ( u K ) . If E q ⊗ K [ u K 2 ] = ∞ \mathbb{E}_{q\otimes K}[u_K^2] = \infty E q ⊗ K [ u K 2 ] = ∞ , both sides are + ∞ +\infty + ∞ : since h ≥ 0 h \ge0 h ≥ 0 , E ω [ Z ^ 2 ] ≥ ( N K ) − 2 ∑ I ∈ ( [ N ] K ) E Y I [ h ( Y I ) 2 ] = ∞ \mathbb{E}_{\omega}[\widehat{Z}^2] \ge\binom{N}{K}^{-2}\sum_{I\in\binom{[N]}{K}}\mathbb{E}_{Y_I}[h(Y_I)^2] = \infty E ω [ Z 2 ] ≥ ( K N ) − 2 ∑ I ∈ ( K [ N ] ) E Y I [ h ( Y I ) 2 ] = ∞ , and a K = 1 / ( N K ) > 0 a_K = 1/\binom{N}{K} > 0 a K = 1/ ( K N ) > 0 .
Bounds from Hoeffding’s ordering. Hoeffding [14 ] shows that V q ⊗ c ( u c ) / c \mathbb{V}_{q\otimes c}(u_c)/c V q ⊗ c ( u c ) / c is nondecreasing in c c c , so c V q ( u 1 ) ≤ V q ⊗ c ( u c ) ≤ ( c / K ) V q ⊗ K ( u K ) c\mathbb{V}_{q}(u_1) \le\mathbb{V}_{q\otimes c}(u_c) \le(c/K)\mathbb{V}_{q\otimes K}(u_K) c V q ( u 1 ) ≤ V q ⊗ c ( u c ) ≤ ( c / K ) V q ⊗ K ( u K ) . Since ∑ c = 0 K c a c = K 2 / N \sum_{c=0}^{K}ca_c = K^2/N ∑ c = 0 K c a c = K 2 / N , the mean of the hypergeometric overlap, Eq. (14) gives Eq. (45) . As N → ∞ N\to\infty N → ∞ for a fixed instance, a 1 = K 2 / N + O ( 1 / N 2 ) a_1 = K^2/N + O(1/N^2) a 1 = K 2 / N + O ( 1/ N 2 ) and a c = O ( N − c ) a_c = O(N^{-c}) a c = O ( N − c ) , so the lower bound is attained up to O ( 1 / N 2 ) O(1/N^2) O ( 1/ N 2 ) when the V q ⊗ c ( u c ) \mathbb{V}_{q\otimes c}(u_c) V q ⊗ c ( u c ) are finite.
Proof of the bound (15). A K K K -DPP is a determinantal measure conditioned on ∣ S ∣ = K \lvert S\rvert= K ∣ S ∣ = K ; determinantal measures are strongly Rayleigh, the property survives conditioning on the number of elements, and strongly Rayleigh measures are negatively associated [4 , 1 ] . We use negative association only for inclusion events, and the paragraph “Negative correlation without strongly Rayleigh measures” below proves that case directly, with linear algebra and Newton’s inequality. These results are stated for finite base sets, and we extend the inequality below to Σ ∗ \Sigma^* Σ ∗ by truncation. Fix a finite set S 0 S_0 S 0 of strings. Restricted to the first n n n strings of a fixed enumeration of Σ ∗ \Sigma^* Σ ∗ and renormalized, P P P is a K K K -DPP on a finite base set once these n n n strings include S 0 S_0 S 0 and some K K K -set with det ( L S ) > 0 \det(L_S)>0 det ( L S ) > 0 , so the inequality holds for the restriction. As n → ∞ n\to\infty n → ∞ , the unnormalized inclusion sums ∑ S ⊇ S 1 det ( L S ) \sum_{S\supseteq S_1}\det(L_S) ∑ S ⊇ S 1 det ( L S ) , for S 1 = S 0 S_1=S_0 S 1 = S 0 and for S 1 = { y } S_1=\{y\} S 1 = { y } , and the normalizer Z Z Z increase to their values under P P P by monotone convergence. Since 0 < Z < ∞ 0<Z<\infty 0 < Z < ∞ , the inequality passes to the limit. Negative association, applied to the increasing indicators { 1 { y ∈ S } } \{\mathbb{1}\{y\in S\}\} { 1 { y ∈ S }} on disjoint coordinates and iterated, gives P ( S 0 ⊆ S ) ≤ ∏ y ∈ S 0 P ( y ∈ S ) P(S_0\subseteq S)\le\prod_{y\in S_0}P(y\in S) P ( S 0 ⊆ S ) ≤ ∏ y ∈ S 0 P ( y ∈ S ) , hence
u c ( y 1 , … , y c ) ≤ K c ( K ) c ∏ j = 1 c u 1 ( y j ) (52) u_c(y_1,\ldots,y_c)\le\frac{K^c}{(K)_c}\prod_{j=1}^{c}u_1(y_j) \tag*{(52)} u c ( y 1 , … , y c ) ≤ ( K ) c K c j = 1 ∏ c u 1 ( y j ) (52)
On tuples with a repeat, u c = 0 u_c=0 u c = 0 and Eq. (52) is trivial. Both sides are nonnegative, so squaring Eq. (52) and taking the expectation over c c c independent draws from q q q gives
E q ⊗ c [ u c 2 ] ≤ ( K c ( K ) c ) 2 ρ c (53) \mathbb{E}_{q^{\otimes c}}[u_c^2]\le\left(\frac{K^c}{(K)_c}\right)^2\rho^c \tag*{(53)} E q ⊗ c [ u c 2 ] ≤ ( ( K ) c K c ) 2 ρ c (53)
and, because u c u_c u c has mean 1 1 1 , V q ⊗ c ( u c ) ≤ ( K c / ( K ) c ) 2 ρ c − 1 \mathbb{V}_{q\otimes c}(u_c)\le(K^c/(K)_c)^2\rho^c-1 V q ⊗ c ( u c ) ≤ ( K c / ( K ) c ) 2 ρ c − 1 ; every term of Eq. (14) is then finite, so E ω [ Z ^ 2 ] < ∞ \mathbb{E}_{\omega}[\widehat{Z}^2]<\infty E ω [ Z 2 ] < ∞ and PoolDPP is well-behaved. For the closed form, expanding the binomials gives a c = ( K c ) ( K c ) ( N − K ) K − c / ( N ) K ≤ ( K c ) ( K ) c / ( N ) c a_c=\binom{K}{c}\binom{K}{c}(N-K)_{K-c}/(N)_K\le\binom{K}{c}(K)_c/(N)_c a c = ( c K ) ( c K ) ( N − K ) K − c / ( N ) K ≤ ( c K ) ( K ) c / ( N ) c , so with θ = K 2 ρ / ( N − K + 1 ) \theta=K^2\rho/(N-K+1) θ = K 2 ρ / ( N − K + 1 ) ,
a c E q ⊗ c [ u c 2 ] ≤ ( K c ) K 2 c ρ c ( K ) c ( N ) c = K 2 c ρ c c ! ( N ) c ≤ θ c c ! (54) a_c\mathbb{E}_{q\otimes c}[u_c^2]
\le
\frac{\binom{K}{c}K^{2c}\rho^c}{(K)_c(N)_c}
=
\frac{K^{2c}\rho^c}{c!(N)_c}
\le
\frac{\theta^c}{c!} \tag*{(54)} a c E q ⊗ c [ u c 2 ] ≤ ( K ) c ( N ) c ( c K ) K 2 c ρ c = c ! ( N ) c K 2 c ρ c ≤ c ! θ c (54)
using ( K c ) = ( K ) c / c ! \binom{K}{c} = (K)_c/c! ( c K ) = ( K ) c / c ! and ( N ) c ≥ ( N − K + 1 ) c (N)_c \ge(N-K+1)^c ( N ) c ≥ ( N − K + 1 ) c . Summing, and keeping the − 1 -1 − 1 of each V q ⊗ c ( u c ) = E q ⊗ c [ u c 2 ] − 1 \mathbb{V}_{q\otimes c}(u_c) = \mathbb{E}_{q\otimes c}[u_c^2] - 1 V q ⊗ c ( u c ) = E q ⊗ c [ u c 2 ] − 1 with ∑ c = 0 K a c = 1 \sum_{c=0}^{K} a_c = 1 ∑ c = 0 K a c = 1 , gives 1 + V ω ( Z ˉ ) / Z 2 ≤ a 0 + ∑ c = 1 K θ c / c ! ≤ e θ − 1 + a 0 1 + \mathbb{V}_{\omega}(\bar{Z})/Z^2 \le a_0 + \sum_{c=1}^{K} \theta^c/c! \le e^\theta- 1 + a_0 1 + V ω ( Z ˉ ) / Z 2 ≤ a 0 + ∑ c = 1 K θ c / c ! ≤ e θ − 1 + a 0 , and Theorem 5.1 gives K L ≤ log ( e θ − 1 + a 0 ) ≤ θ \mathrm{KL} \le\log(e^\theta- 1 + a_0) \le\theta KL ≤ log ( e θ − 1 + a 0 ) ≤ θ , since a 0 ≤ 1 a_0 \le1 a 0 ≤ 1 . ■
Finiteness of ρ \rho ρ . Let λ 1 , … , λ D \lambda_1,\ldots,\lambda_D λ 1 , … , λ D and v 1 , … , v D \mathbf{v}_1,\ldots,\mathbf{v}_D v 1 , … , v D be the eigenpairs of C = ∑ y κ ( y ) ϕ ( y ) ϕ ( y ) ⊤ \mathbf{C} = \sum_y \kappa(y)\phi(y)\phi(y)^\top C = ∑ y κ ( y ) ϕ ( y ) ϕ ( y ) ⊤ , and λ − d \lambda_{-d} λ − d the eigenvalues with λ d \lambda_d λ d omitted. Writing the primal eigenvectors of L = B ⊤ B \mathbf{L} = \mathbf{B}^\top\mathbf{B} L = B ⊤ B through the dual ones gives the K K K -DPP marginal formula
P ( y ∈ S ) = κ ( y ) ∑ d = 1 D ⟨ v d , ϕ ( y ) ⟩ 2 e K − 1 ( λ − d ) e K ( λ ) (55) P(y \in S) = \kappa(y) \sum_{d=1}^{D} \langle\mathbf{v}_d,\phi(y)\rangle^2 \frac{e_{K-1}(\lambda_{-d})}{e_K(\lambda)} \tag*{(55)} P ( y ∈ S ) = κ ( y ) d = 1 ∑ D ⟨ v d , ϕ ( y ) ⟩ 2 e K ( λ ) e K − 1 ( λ − d ) (55)
Because ∥ ϕ ( y ) ∥ 2 = 1 \|\phi(y)\|_2 = 1 ∥ ϕ ( y ) ∥ 2 = 1 and the v d \mathbf{v}_d v d are an orthonormal basis, the weights ⟨ v d , ϕ ( y ) ⟩ 2 \langle\mathbf{v}_d,\phi(y)\rangle^2 ⟨ v d , ϕ ( y ) ⟩ 2 sum to 1 1 1 , so u 1 ( y ) = P ( y ∈ S ) / ( K q ( y ) ) ≤ w ( y ) max d e K − 1 ( λ − d ) / ( K e K ( λ ) ) u_1(y) = P(y \in S)/(Kq(y)) \le w(y)\max_d e_{K-1}(\lambda_{-d})/(Ke_K(\lambda)) u 1 ( y ) = P ( y ∈ S ) / ( K q ( y )) ≤ w ( y ) max d e K − 1 ( λ − d ) / ( K e K ( λ )) . Hence, ρ ≤ E q [ w 2 ] ( max d e K − 1 ( λ − d ) / ( K e K ( λ ) ) ) 2 \rho\le\mathbb{E}_q[w^2]\left(\max_d e_{K-1}(\lambda_{-d})/(Ke_K(\lambda))\right)^2 ρ ≤ E q [ w 2 ] ( max d e K − 1 ( λ − d ) / ( K e K ( λ )) ) 2 . Here, e K ( λ ) = Z > 0 e_K(\lambda) = Z > 0 e K ( λ ) = Z > 0 (by Cauchy–Binet, Z = ∑ ∣ S ∣ = K det ( L S ) = e K ( λ ) Z = \sum_{|S|=K}\det(L_S) = e_K(\lambda) Z = ∑ ∣ S ∣ = K det ( L S ) = e K ( λ ) ), so ρ \rho ρ is finite whenever E q [ w 2 ] < ∞ \mathbb{E}_q[w^2] < \infty E q [ w 2 ] < ∞ , in particular whenever the weights are bounded. The bound is invariant to rescaling κ \kappa κ , as ρ \rho ρ is. On the infinite base set Σ ∗ \Sigma^* Σ ∗ , Eq. (55) and Z = e K ( λ ) Z = e_K(\lambda) Z = e K ( λ ) follow from their finite versions by the truncation argument above: C \mathbf{C} C is finite because ∑ y κ ( y ) = E q [ w ] ≤ E q [ w 2 ] 1 / 2 \sum_y \kappa(y) = \mathbb{E}_q[w] \le\mathbb{E}_q[w^2]^{1/2} ∑ y κ ( y ) = E q [ w ] ≤ E q [ w 2 ] 1/2 , the truncated dual kernels increase to C \mathbf{C} C , and both sides converge.
Negative correlation without strongly Rayleigh measures. The proof of Eq. (15) uses negative association only for inclusion events, through P ( S 0 ⊆ S ) ≤ ∏ y ∈ S 0 P ( y ∈ S ) P(S_0 \subseteq S) \le\prod_{y\in S_0}P(y \in S) P ( S 0 ⊆ S ) ≤ ∏ y ∈ S 0 P ( y ∈ S ) , and this inequality has a short self-contained proof that uses only linear algebra and Newton’s inequality. We give it because the cited theorem is more than we need: it rests on the theory of real stable polynomials. By the truncation argument, it suffices to take a finite base set V V V . Write ψ ( y ) = d e f κ ( y ) ϕ ( y ) \psi(y) \overset{\mathrm{def}}{=} \sqrt{\kappa(y)}\phi(y) ψ ( y ) = def κ ( y ) ϕ ( y ) , so that L ( x , y ) = ψ ( x ) ⊤ ψ ( y ) L(x,y) = \psi(x)^\top\psi(y) L ( x , y ) = ψ ( x ) ⊤ ψ ( y ) , and let Z K ( V ) Z_K(V) Z K ( V ) be the sum of det ( L S ) \det(L_S) det ( L S ) over K K K -sets S ⊆ V S \subseteq V S ⊆ V .
(i) Normalizers. Let C V = d e f ∑ y ∈ V ψ ( y ) ψ ( y ) ⊤ \mathbf{C}_V \overset{\mathrm{def}}{=} \sum_{y\in V}\psi(y)\psi(y)^\top C V = def ∑ y ∈ V ψ ( y ) ψ ( y ) ⊤ . Expanding det ( I + x L V ) \det(\mathbf{I} + x\mathbf{L}_V) det ( I + x L V ) in principal minors and using det ( I + M M ′ ) = det ( I + M ′ M ) \det(\mathbf{I} + \mathbf{M}\mathbf{M}^\prime) = \det(\mathbf{I} + \mathbf{M}^\prime\mathbf{M}) det ( I + M M ′ ) = det ( I + M ′ M ) gives ∑ K Z K ( V ) x K = det ( I + x L V ) = det ( I + x C V ) \sum_K Z_K(V)x^K = \det(\mathbf{I} + x\mathbf{L}_V) = \det(\mathbf{I} + x\mathbf{C}_V) ∑ K Z K ( V ) x K = det ( I + x L V ) = det ( I + x C V ) .
(ii) Two strings. Fix a ≠ b a \ne b a = b in V V V and let V ′ = V ∖ { a , b } V^\prime= V \setminus\{a,b\} V ′ = V ∖ { a , b } . Rotating every ψ ( y ) \psi(y) ψ ( y ) by the same orthogonal matrix leaves L L L unchanged, so we may take C V ′ = diag ( η ) \mathbf{C}_{V^\prime} = \operatorname{diag}(\eta) C V ′ = diag ( η ) with η ≥ 0 \eta\ge0 η ≥ 0 . Let s = ψ ( a ) s = \psi(a) s = ψ ( a ) , t = ψ ( b ) t = \psi(b) t = ψ ( b ) , g d = e K − 1 ( η − d ) g_d = e_{K-1}(\eta_{-d}) g d = e K − 1 ( η − d ) , and δ d d ′ = e K − 2 ( η − d d ′ ) \delta_{dd^\prime} = e_{K-2}(\eta_{-dd^\prime}) δ d d ′ = e K − 2 ( η − d d ′ ) , where η − d \eta_{-d} η − d omits η d \eta_d η d . By (i), the sums of det ( L S ) \det(L_S) det ( L S ) over K K K -sets S ⊆ V S \subseteq V S ⊆ V containing neither string, only a a a , only b b b , and both are read off from the coefficients of x K x^K x K in det ( I + x C W ) \det(\mathbf{I} + x\mathbf{C}_W) det ( I + x C W ) for W = V ′ W = V^\prime W = V ′ , V ′ ∪ { a } V^\prime\cup\{a\} V ′ ∪ { a } , V ′ ∪ { b } V^\prime\cup\{b\} V ′ ∪ { b } , and V V V , respectively. Here, C V = diag ( η ) + s s ⊤ + t t ⊤ \mathbf{C}_V = \operatorname{diag}(\eta) + ss^\top+ tt^\top C V = diag ( η ) + s s ⊤ + t t ⊤ , and the matrix determinant lemma (for x ≥ 0 x \ge0 x ≥ 0 , I + x diag ( η ) \mathbf{I} + x\operatorname{diag}(\eta) I + x diag ( η ) is invertible) gives the four sums as
Z ∅ = e K ( η ) , Z a = ∑ d ∈ [ D ] s d 2 γ d , Z b = ∑ d ∈ [ D ] t d 2 γ d , Z a b = 1 2 ∑ d , d ′ ∈ [ D ] ( s d t d ′ − s d ′ t d ) 2 δ d d ′ (56) Z_{\varnothing} = e_K(\eta), \qquad Z_a = \sum_{d\in[D]} s_d^2\gamma_d, \qquad Z_b = \sum_{d\in[D]} t_d^2\gamma_d, \qquad Z_{ab} = \frac{1}{2}\sum_{d,d^\prime\in[D]}(s_dt_{d^\prime}-s_{d^\prime}t_d)^2\delta_{dd^\prime} \tag*{(56)} Z ∅ = e K ( η ) , Z a = d ∈ [ D ] ∑ s d 2 γ d , Z b = d ∈ [ D ] ∑ t d 2 γ d , Z ab = 2 1 d , d ′ ∈ [ D ] ∑ ( s d t d ′ − s d ′ t d ) 2 δ d d ′ (56)
The inequality P ( a , b ∈ S ) ≤ P ( a ∈ S ) P ( b ∈ S ) P(a,b \in S) \le P(a \in S)P(b \in S) P ( a , b ∈ S ) ≤ P ( a ∈ S ) P ( b ∈ S ) reads Z a b ( Z ∅ + Z a + Z b + Z a b ) ≤ ( Z a + Z a b ) ( Z b + Z a b ) Z_{ab}(Z_{\varnothing}+Z_a+Z_b+Z_{ab}) \le(Z_a+Z_{ab})(Z_b+Z_{ab}) Z ab ( Z ∅ + Z a + Z b + Z ab ) ≤ ( Z a + Z ab ) ( Z b + Z ab ) , that is, Z ∅ Z a b ≤ Z a Z b Z_{\varnothing}Z_{ab} \le Z_aZ_b Z ∅ Z ab ≤ Z a Z b . Expanding,
Z a Z b − Z ∅ Z a b = ( ∑ d ∈ [ D ] s d t d γ d ) 2 + 1 2 ∑ d , d ′ ∈ [ D ] ( s d t d ′ − s d ′ t d ) 2 ( γ d γ d ′ − Z ∅ δ d d ′ ) (57) Z_aZ_b - Z_{\varnothing}Z_{ab} = \left(\sum_{d\in[D]}s_dt_d\gamma_d\right)^2 + \frac{1}{2}\sum_{d,d^\prime\in[D]}(s_dt_{d^\prime}-s_{d^\prime}t_d)^2(\gamma_d\gamma_{d^\prime}-Z_{\varnothing}\delta_{dd^\prime}) \tag*{(57)} Z a Z b − Z ∅ Z ab = d ∈ [ D ] ∑ s d t d γ d 2 + 2 1 d , d ′ ∈ [ D ] ∑ ( s d t d ′ − s d ′ t d ) 2 ( γ d γ d ′ − Z ∅ δ d d ′ ) (57)
For d ≠ d ′ d \ne d^\prime d = d ′ and ν = η − d d ′ \nu= \eta_{-dd^\prime} ν = η − d d ′ , we have g d = e K − 1 ( ν ) + η d ′ e K − 2 ( ν ) g_d = e_{K-1}(\nu) + \eta_{d^\prime}e_{K-2}(\nu) g d = e K − 1 ( ν ) + η d ′ e K − 2 ( ν ) , likewise for g d ′ g_{d^\prime} g d ′ , and Z ∅ = e K ( ν ) + ( η d + η d ′ ) e K − 1 ( ν ) + η d η d ′ e K − 2 ( ν ) Z_{\varnothing} = e_K(\nu) + (\eta_d+\eta_{d^\prime})e_{K-1}(\nu) + \eta_d\eta_{d^\prime}e_{K-2}(\nu) Z ∅ = e K ( ν ) + ( η d + η d ′ ) e K − 1 ( ν ) + η d η d ′ e K − 2 ( ν ) , so g d g d ′ − Z ∅ δ d d ′ = e K − 1 ( ν ) 2 − e K ( ν ) e K − 2 ( ν ) ≥ 0 g_dg_{d^\prime} - Z_{\varnothing}\delta_{dd^\prime} = e_{K-1}(\nu)^2 - e_K(\nu)e_{K-2}(\nu) \ge0 g d g d ′ − Z ∅ δ d d ′ = e K − 1 ( ν ) 2 − e K ( ν ) e K − 2 ( ν ) ≥ 0 by Newton’s inequality. Hence, Z ∅ Z a b ≤ Z a Z b Z_{\varnothing}Z_{ab} \le Z_aZ_b Z ∅ Z ab ≤ Z a Z b . (For K ≤ 1 K \le1 K ≤ 1 , P ( a , b ∈ S ) = 0 P(a,b \in S) = 0 P ( a , b ∈ S ) = 0 .) This step is where the two routes meet. The strongly Rayleigh route gets the same conclusion by noting that the generating polynomial ∑ S ⊆ V det ( L S ) ∏ y ∈ S z y \sum_{S\subseteq V}\det(L_S)\prod_{y\in S}z_y ∑ S ⊆ V det ( L S ) ∏ y ∈ S z y in all variables at once. Here, one variable suffices: setting z y = x z_y = x z y = x for every y ∈ V ′ y \in V^\prime y ∈ V ′ gives det ( I + x C V ′ ) = ∏ d ∈ [ D ] ( 1 + x η d ) \det(\mathbf{I} + x\mathbf{C}_{V^\prime}) = \prod_{d\in[D]}(1+x\eta_d) det ( I + x C V ′ ) = ∏ d ∈ [ D ] ( 1 + x η d ) , whose roots are real, and Newton’s inequality holds for the coefficients of any polynomial with real roots. The rest of Z a Z b − Z ∅ Z a b Z_aZ_b - Z_{\varnothing}Z_{ab} Z a Z b − Z ∅ Z ab is a sum of squares. (iii) Conditioning. For any R ⊆ V ∖ { a } R \subseteq V \setminus\{a\} R ⊆ V ∖ { a } , the Schur complement gives det ( L R ∪ { a } ) = ∥ ψ ( a ) ∥ 2 det ( L R ′ ) \det(L_{R\cup\{a\}}) = \|\psi(a)\|^2\det(L^\prime_R) det ( L R ∪ { a } ) = ∥ ψ ( a ) ∥ 2 det ( L R ′ ) , where L ′ L^\prime L ′ is the kernel of the vectors ψ ( y ) \psi(y) ψ ( y ) projected onto the orthogonal complement of ψ ( a ) \psi(a) ψ ( a ) . So given a ∈ S a \in S a ∈ S , the set S ∖ { a } S \setminus\{a\} S ∖ { a } is a ( K − 1 ) (K-1) ( K − 1 ) -DPP of the same form on V ∖ { a } V \setminus\{a\} V ∖ { a } . (iv) Induction on ∣ S 0 ∣ |S_0| ∣ S 0 ∣ . We induct for every K K K , finite V V V , and Gram kernel at once, since (iii) changes all three. For ∣ S 0 ∣ ≤ 1 |S_0| \le1 ∣ S 0 ∣ ≤ 1 , the claim is an equality. For a ∉ S 0 a \notin S_0 a ∈ / S 0 with P ( a ∈ S ) = 0 P(a \in S) = 0 P ( a ∈ S ) = 0 , both sides of the step below are 0; otherwise, ψ ( a ) ≠ 0 \psi(a) \ne0 ψ ( a ) = 0 , so (iii) applies, and the induction hypothesis for the conditional ( K − 1 ) (K-1) ( K − 1 ) -DPP of (iii), and then (ii), give P ( S 0 ∪ { a } ⊆ S ) = P ( a ∈ S ) P ( S 0 ⊆ S ∣ a ∈ S ) ≤ P ( a ∈ S ) ∏ y ∈ S 0 P ( y ∈ S ∣ a ∈ S ) ≤ ∏ y ∈ S 0 ∪ { a } P ( y ∈ S ) P(S_0 \cup\{a\} \subseteq S) = P(a \in S)P(S_0 \subseteq S \mid a \in S) \le P(a \in S)\prod_{y\in S_0}P(y \in S \mid a \in S) \le\prod_{y\in S_0\cup\{a\}}P(y \in S) P ( S 0 ∪ { a } ⊆ S ) = P ( a ∈ S ) P ( S 0 ⊆ S ∣ a ∈ S ) ≤ P ( a ∈ S ) ∏ y ∈ S 0 P ( y ∈ S ∣ a ∈ S ) ≤ ∏ y ∈ S 0 ∪ { a } P ( y ∈ S ) . We have not found this argument in the literature.
Proof of cor:kl-sum
Because the target’s inclusion events are negatively correlated, E q ⊗ c [ u c 2 ] ≤ ( K c ( K ) c ) 2 ρ c \mathbb{E}_{q\otimes c}[u_c^2] \le\left(\frac{K^c}{(K)_c}\right)^2 \rho^c E q ⊗ c [ u c 2 ] ≤ ( ( K ) c K c ) 2 ρ c for every c c c (Eq. (53) , §A.7), with equality at c = 1 c=1 c = 1 . Applying this to every term of Eq. (14), with the exact coefficients a c a_c a c , gives a sharper upper bound.
Corollary A.4 (Sharper bound). Under the conditions of Theorem 5.2 , if ρ < ∞ \rho< \infty ρ < ∞ , then
K L ( P ∥ P ‾ ) ≤ log ∑ c = 0 K a c ( K c ( K ) c ) 2 ρ c \mathrm{KL}(P\Vert\overline{P}) \le\log\sum_{c=0}^{K} a_c \left(\frac{K^c}{(K)_c}\right)^2 \rho^c KL ( P ∥ P ) ≤ log c = 0 ∑ K a c ( ( K ) c K c ) 2 ρ c = log ( 1 + a 1 V q ( u 1 ) + ∑ c ≥ 2 K a c ( ( K c ( K ) c ) 2 ρ c − 1 ) ) (58) = \log\left(1+a_1\mathbb{V}_q(u_1)+\sum_{c\ge2}^{K}a_c\left(\left(\frac{K^c}{(K)_c}\right)^2\rho^c-1\right)\right) \tag*{(58)} = log ( 1 + a 1 V q ( u 1 ) + c ≥ 2 ∑ K a c ( ( ( K ) c K c ) 2 ρ c − 1 ) ) (58) where a 0 = ( N − K K ) / ( N K ) a_0=\binom{N-K}{K}/\binom{N}{K} a 0 = ( K N − K ) / ( K N ) is the formula of Eq. (14) at c = 0 c=0 c = 0 , so the sum is an expectation over the hypergeometric overlap c c c . The right-hand side is at most log ( e θ − 1 + a 0 ) \log(e^\theta-1+a_0) log ( e θ − 1 + a 0 ) , the bound (15), since the proof of Theorem 5.2 bounds the term at each c ≥ 1 c\ge1 c ≥ 1 by θ c / c ! \theta^c/c! θ c / c ! .
Proof. The c = 1 c=1 c = 1 ratio is the one-point inclusion marginal against the proposal, u 1 ( y ) = P ( y ∈ S ) / ( K q ( y ) ) u_1(y)=P(y\in S)/(Kq(y)) u 1 ( y ) = P ( y ∈ S ) / ( K q ( y )) , computable, on a finite base set, from one D × D D\times D D × D eigendecomposition of C C C via Eq. (55) . Bounding every term of Eq. (14) by Eq. (53) , an equality at c = 1 c=1 c = 1 , and using ∑ c = 0 K a c = 1 \sum_{c=0}^{K}a_c=1 ∑ c = 0 K a c = 1 yields Theorem A.4:
K L ( P ∥ P ‾ ) ≤ log ( 1 + a 1 V q ( u 1 ) + ∑ c ≥ 2 a c ( ( K c ( K ) c ) 2 ρ c − 1 ) ) (59) \mathrm{KL}(P\Vert\overline{P}) \le\log\left(1+a_1\mathbb{V}_q(u_1)+\sum_{c\ge2}a_c\left(\left(\frac{K^c}{(K)_c}\right)^2\rho^c-1\right)\right) \tag*{(59)} KL ( P ∥ P ) ≤ log ( 1 + a 1 V q ( u 1 ) + c ≥ 2 ∑ a c ( ( ( K ) c K c ) 2 ρ c − 1 ) ) (59)
and, because Eq. (14) is an equality, the relative variance is at least ( K 2 / N ) V q ( u 1 ) (K^2/N)\mathbb{V}_q(u_1) ( K 2 / N ) V q ( u 1 ) (Eq. (45) ), which exceeds the c = 1 c=1 c = 1 term a 1 V q ( u 1 ) a_1\mathbb{V}_q(u_1) a 1 V q ( u 1 ) : at a pool size where log ( 1 + K 2 V q ( u 1 ) / N ) \log(1+K^2\mathbb{V}_q(u_1)/N) log ( 1 + K 2 V q ( u 1 ) / N ) exceeds a target, the bound log ( 1 + V ω ( Z ^ ) / Z 2 ) \log(1+\mathbb{V}_\omega(\widehat{Z})/Z^2) log ( 1 + V ω ( Z ) / Z 2 ) exceeds it too. This is a statement about the bound, not about the KL, which can be smaller. Two special cases: at K = 1 K=1 K = 1 , a 1 = 1 / N a_1=1/N a 1 = 1/ N , Eq. (14) is the classical importance-sampling relative variance, and the bound above is an equality, since only the c = 1 c=1 c = 1 term remains; for the proposal matching the target’s marginals, q ( y ) ∝ P ( y ∈ S ) q(y)\propto P(y\in S) q ( y ) ∝ P ( y ∈ S ) , the leading term vanishes identically (u 1 ≡ 1 u_1\equiv1 u 1 ≡ 1 ), so what the leading term rewards is matching the target’s inclusion marginals , not its quality. ▪
Evaluating the Bound on Pool-Built Instances
The bound on instances built from our pools. We evaluate the bounds on instances built from the pools of §6 (base set the pooled distinct strings, q q q their empirical frequency, and quality p 1 / T p^{1/T} p 1/ T of Eq. (6) ). On instances small enough to enumerate every pool, the two sides of Eq. (14) agree to 12 significant digits. Each instance has the real embeddings, spectrum, and weight dispersion at the experimental K K K , D D D , and N N N , but its base set is the observed support, the distinct strings in the union of the pools, whose exact proposal mass is 0.68 on Ambrosia, 0.0017 on GSM8K, and 0.0003 on FineWeb (medians over prompts, from the proposal’s log-probabilities of the drawn strings), so almost every string of the proposal is missing on GSM8K and FineWeb. The columns of Table 1 therefore evaluate the bound on the instance at the experimental scale. They are not a bound on the KL of the sampler on the full proposal, and they can understate it: for T > 1 T>1 T > 1 at local sampling temperature 1, the weights w = p 1 / T − 1 w=p^{1/T-1} w = p 1/ T − 1 are largest on low-probability strings, which the instance mostly lacks, and including them would raise ρ \rho ρ . The Monte Carlo estimate draws pools from the instance and evaluates V ω ( Z ^ ) / Z 2 \mathbb{V}_{\omega}(\widehat{Z})/Z^2 V ω ( Z ) / Z 2 directly; at the sharp FineWeb setting (T = 0.82 T=0.82 T = 0.82 ), its estimate of E ω [ Z ^ ] / Z \mathbb{E}_{\omega}[\widehat{Z}]/Z E ω [ Z ] / Z , which should be 1, is 0.49, so that estimate is unreliable.
Table 1. Bounds on the KL, in nats, evaluated on the instances built from the pools under the kernel of Eq. (6) , at two values of T T T per task (medians over prompts). The instance of each prompt keeps only the strings the pools drew, with proposal mass 0.68 on Ambrosia, 0.0017 on GSM8K, and 0.0003 on FineWeb (medians over prompts); the values are bounds on the instance, not on the sampler’s KL on the full proposal. The bound (45) is within 1.06–1.07× of log ( 1 + V ^ ) \log(1+\widehat{V}) log ( 1 + V ) at K = 3 K=3 K = 3 and 1.5–2.0× at K = 10 K=10 K = 10 , excluding the parenthesized column. log ( 1 + V ^ ) \log(1+\widehat{V}) log ( 1 + V ) is a Monte Carlo estimate of the smallest value that the variance argument of Theorem 5.1 can give. Parenthesized values are unreliable: there, the Monte Carlo estimate of E ω [ Z ^ ] / Z \mathbb{E}_{\omega}[\widehat{Z}]/Z E ω [ Z ] / Z , which should be 1, is 0.49 on FineWeb and below 10 − 20 10^{-20} 1 0 − 20 on GSM8K. The ρ \rho ρ row and the lower-bound row follow exactly from the median of V q ( u 1 ) \mathbb{V}_q(u_1) V q ( u 1 ) .
Table 2. Pool size for a bound of 0.1 nats on the KL (medians over prompts): the smallest pool at which the lower bound of Eq. (45) allows it, and a pool at which (45) reaches it. At T = 1 T=1 T = 1 , the bound reaches 0.1 nats with pools of 43 strings on Ambrosia, 149 on FineWeb and 3,492 on GSM8K; at settings, it needs 142 strings on Ambrosia (T = 0.67 T=0.67 T = 0.67 ), 95,816 on FineWeb (T = 0.82 T=0.82 T = 0.82 ), and 941,451 on GSM8K (T = 1.05 T=1.05 T = 1.05 ).
Running GSM8K with larger pools. The pool size trades accuracy against cost, so we ran GSM8K with pools of N = 2,500 N=2{,}500 N = 2 , 500 . When we extrapolate the instance built from the N = 100 N=100 N = 100 pools through the N N N -independent V q ( u 1 ) \mathbb{V}_q(u_1) V q ( u 1 ) , the bound falls below 0.1 nats at N ≈ 3,500 N\approx3{,}500 N ≈ 3 , 500 for T = 1 T=1 T = 1 , while T = 1.05 T=1.05 T = 1.05 needs N ≈ 941,000 N\approx941{,}000 N ≈ 941 , 000 ; at N = 2,500 N=2{,}500 N = 2 , 500 , it is 0.140 and 21.5 nats:
Table 3. The bound (58) on the pool-built instance, in nats, as a function of the pool size (medians over prompts; Figure 5 ). All columns extrapolate the instance built from the N = 100 N=100 N = 100 pools through the N N N -independent V q ( u 1 ) V_q(u_1) V q ( u 1 ) .
Figure 5. The bound (58) on the pool-built instance vs. pool size N N N on GSM8K (medians over prompts; dots mark the bound at N = 2,500 N=2{,}500 N = 2 , 500 , the pool size of the separate run below; like the curves, they are extrapolated from the N = 100 N=100 N = 100 pools).
Additional Algorithms
For completeness, we include pseudocode for dual sampling.
SampleDual. SampleDual takes K K K and B \mathbf{B} B and returns an exact sample from the K K K -DPP; see Kulesza and Taskar [25 ] for proofs of correctness. Phase 1 selects a size-K K K subset J \mathcal{J} J of eigenvector indices of C \mathbf{C} C with the elementary symmetric polynomials of its eigenvalues.16 Phase 2 samples K K K items: at each step an item is chosen with probability proportional to how much its embedding lies in the subspace spanned by the selected eigenvectors, and the subspace is then projected away from the chosen item. This projection is what makes similar items compete. Forming C \mathbf{C} C costs O ( D 2 N ) O(D^2N) O ( D 2 N ) , the eigendecomposition O ( D 3 ) O(D^3) O ( D 3 ) , Phase 1 is negligible, and Phase 2 costs O ( D N K ) O(DNK) O ( D N K ) . The primal eigendecomposition is faster for small pools (§D.3).
Algorithm 1 SampleDual: Draws exact samples from the K K K -DPP using the dual representation trick; pseudocode adapted from Kulesza and Taskar [25 ] . The base set Y \mathcal{Y} Y is the set of column indices of the input feature matrix B \mathbf{B} B . In particular, when PoolDPP invokes it with B ^ \widehat{\mathbf{B}} B (Eq. (8) ), the base set is the pool indices { 1 , … , N } \{1,\ldots,N\} { 1 , … , N } , and the returned subset is an index set that PoolDPP maps to its labeled strings (Theorem A.1).
Input: Subset size K K K , feature matrix B ∈ R D × Y \mathbf{B} \in\mathbb{R}^{D \times\mathcal{Y}} B ∈ R D × Y with rank ( B ) ≥ K \operatorname{rank}(\mathbf{B}) \ge K rank ( B ) ≥ K .
Output: Subset S ∈ ( Y K ) S \in\binom{\mathcal{Y}}{K} S ∈ ( K Y ) .
C ← B B ⊤ \mathbf{C} \leftarrow\mathbf{B}\mathbf{B}^{\top} C ← B B ⊤
Eigendecompose C \mathbf{C} C with eigenvalues λ 1 , … , λ D \lambda_1,\ldots,\lambda_D λ 1 , … , λ D and eigenvectors v 1 , … , v D \mathbf{v}_1,\ldots,\mathbf{v}_D v 1 , … , v D
// Phase 1: Select K K K eigenvectors using elementary symmetric polynomials (e k ( ⋅ ) e_k(\cdot) e k ( ⋅ ) ; footnote 16).
J ← ∅ \mathcal{J} \leftarrow\varnothing J ← ∅
for d = D , … , 1 d = D,\ldots,1 d = D , … , 1 :
Let λ j 1 , … , λ j r \lambda_{j_1},\ldots,\lambda_{j_r} λ j 1 , … , λ j r be the eigenvalues s.t. j < d j < d j < d , j ∉ J j \notin\mathcal{J} j ∈ / J
ξ ← λ d ⋅ e K − ∣ J ∣ − 1 ( λ j 1 , … , λ j r ) e K − ∣ J ∣ ( λ d , λ j 1 , … , λ j r ) \xi\leftarrow\lambda_d \cdot\frac{e_{K-\lvert\mathcal{J}\rvert-1}(\lambda_{j_1},\ldots,\lambda_{j_r})}{e_{K-\lvert\mathcal{J}\rvert}(\lambda_d,\lambda_{j_1},\ldots,\lambda_{j_r})} ξ ← λ d ⋅ e K − ∣ J ∣ ( λ d , λ j 1 , … , λ j r ) e K − ∣ J ∣ − 1 ( λ j 1 , … , λ j r )
Add d d d to J \mathcal{J} J with probability ξ \xi ξ
if ∣ J ∣ = K \lvert\mathcal{J}\rvert= K ∣ J ∣ = K : break
// Phase 2: Sample K K K items from the selected eigenspace.
S ← ∅ , V ← { 1 v j ⊤ C v j v j ∣ j ∈ J } S \leftarrow\varnothing,\quad\mathcal{V} \leftarrow\left\{\frac{1}{\sqrt{\mathbf{v}_j^{\top}\mathbf{C}\mathbf{v}_j}}\mathbf{v}_j \mid j \in\mathcal{J}\right\} S ← ∅ , V ← { v j ⊤ C v j 1 v j ∣ j ∈ J }
while ∣ S ∣ < K \lvert S\rvert< K ∣ S ∣ < K :
Sample y y y with Pr ( y ) = 1 ∣ V ∣ ∑ v ∈ V ( v ⊤ B : , y ) 2 \Pr(y) = \frac{1}{\lvert\mathcal{V}\rvert}\sum_{\mathbf{v}\in\mathcal{V}}(\mathbf{v}^{\top}\mathbf{B}_{:,y})^2 Pr ( y ) = ∣ V ∣ 1 ∑ v ∈ V ( v ⊤ B : , y ) 2
S ← S ∪ { y } S \leftarrow S \cup\{y\} S ← S ∪ { y } ; b ← B : , y \mathbf{b} \leftarrow\mathbf{B}_{:,y} b ← B : , y
Pick any vector v 0 ∈ V \mathbf{v}_0 \in\mathcal{V} v 0 ∈ V with v 0 ⊤ b ≠ 0 \mathbf{v}_0^{\top}\mathbf{b} \ne0 v 0 ⊤ b = 0
V ← { v − v ⊤ b v 0 ⊤ b v 0 ∣ v ∈ V − { v 0 } } \mathcal{V} \leftarrow\left\{\mathbf{v} - \frac{\mathbf{v}^{\top}\mathbf{b}}{\mathbf{v}_0^{\top}\mathbf{b}}\mathbf{v}_0 \mid\mathbf{v} \in\mathcal{V} - \{\mathbf{v}_0\}\right\} V ← { v − v 0 ⊤ b v ⊤ b v 0 ∣ v ∈ V − { v 0 } }
Orthonormalize V \mathcal{V} V with respect to the inner product ⟨ u , v ⟩ : = u ⊤ C v \langle\mathbf{u},\mathbf{v}\rangle\mathrel{\mathop:}= \mathbf{u}^{\top}\mathbf{C}\mathbf{v} ⟨ u , v ⟩ : = u ⊤ Cv
return S S S
Algorithm 2 GreedyMAP: greedy approximation to the K K K -DPP MAP, with the multiplicative volume guarantee of Çivril and Magdon-Ismail [8 ] . Schur-complement greedy expressed in the feature-matrix basis (cf. [6 ] for the kernel-basis Cholesky form). Maintains, for each pool item, the squared distance of its embedding to the span of the currently chosen items, and at each step picks the item with the largest such distance. Runs in O ( D N K ) O(DNK) O ( D N K ) time. As in Alg. 1, the base set Y \mathcal{Y} Y is the set of column indices of B \mathbf{B} B ; when the algorithm is invoked with B ^ \widehat{\mathbf{B}} B , the returned subset is a set of pool indices, which PoolDPP maps to its labeled strings.
Input: Subset size K K K , feature matrix B ∈ R D × Y \mathbf{B} \in\mathbb{R}^{D \times\mathcal{Y}} B ∈ R D × Y with rank ( B ) ≥ K \operatorname{rank}(\mathbf{B}) \ge K rank ( B ) ≥ K .
Output: Subset S ∈ ( Y K ) S \in\binom{\mathcal{Y}}{K} S ∈ ( K Y ) .
S ← ∅ S \gets\varnothing S ← ∅
for y ∈ Y y \in\mathcal{Y} y ∈ Y :
d y ← ∥ B : , y ∥ 2 d_y \gets\lVert\mathbf{B}_{:,y} \rVert^2 d y ← ∥ B : , y ∥ 2 // squared residual norm = L y y L_{yy} L y y
while ∣ S ∣ < K \lvert S \rvert< K ∣ S ∣ < K :
y ∗ ← argmax y ∉ S d y y^* \gets\operatorname*{argmax}_{y \notin S} d_y y ∗ ← argmax y ∈ / S d y // largest remaining contribution to log det
S ← S ∪ { y ∗ } S \gets S \cup\{y^*\} S ← S ∪ { y ∗ }
b ← B : , y ∗ / d y ∗ \mathbf{b} \gets\mathbf{B}_{:,y^*} / \sqrt{d_{y^*}} b ← B : , y ∗ / d y ∗ // unit residual direction
for y ∉ S y \notin S y ∈ / S :
α ← ⟨ b , B : , y ⟩ \alpha\gets\langle\mathbf{b}, \mathbf{B}_{:,y} \rangle α ← ⟨ b , B : , y ⟩
B : , y ← B : , y − α b \mathbf{B}_{:,y} \gets\mathbf{B}_{:,y} - \alpha\mathbf{b} B : , y ← B : , y − α b // project out chosen direction
d y ← d y − α 2 d_y \gets d_y - \alpha^2 d y ← d y − α 2 // shrink residual norm
return S S S
Experimental Ablations
Unless otherwise stated, all ablations use the FineWeb intrinsic setup from § 6.1 ; results use one pool and, for stochastic methods, 10 selection runs.
Pool size N N N . We sweep N ∈ { 25 , 50 , 100 , 150 , 200 , 400 } N \in\{25, 50, 100, 150, 200, 400\} N ∈ { 25 , 50 , 100 , 150 , 200 , 400 } at K = 10 K = 10 K = 10 and local sampling temperature 1, with PoolDPP-Sampling at global temperature T = 0.82 T=0.82 T = 0.82 and PoolDPP-MAP at T = 50 T=50 T = 50 (Figure 6 ). Theorem 5.2 predicts that PoolDPP-Sampling’s approximation error decreases as O ( 1 / N ) O(1/N) O ( 1/ N ) . Since the exact KL to the population K K K -DPP is intractable, we instead report the sum of the selected set’s mean log-probability and log-determinant, together with mean log-probability. This sum rises with N N N at a decreasing rate and has not saturated at N = 400 N=400 N = 400 .
Figure 6. Pool size N N N ablation (FineWeb, K = 10 K = 10 K = 10 , local sampling temperature 1, PoolDPP-Sampling at T = 0.82 T=0.82 T = 0.82 , PoolDPP-MAP at T = 50 T=50 T = 50 ). Mean log-probability and the full objective, its sum with the log-determinant, rise with N N N at a decreasing rate.
Subset size K K K . We sweep K ∈ { 3 , 5 , 10 , 15 , 20 } K \in\{3, 5, 10, 15, 20\} K ∈ { 3 , 5 , 10 , 15 , 20 } at N = 400 N = 400 N = 400 and local sampling temperature 1, with PoolDPP-Sampling at T = 0.82 T=0.82 T = 0.82 and PoolDPP-MAP at T = 50 T=50 T = 50 (Figure 7 ). At every K K K , PoolDPP-MAP has the highest full-score log-determinant, with quality at or above K K K -means.
Embedder and language model. We replicate the FineWeb experiment with all four combinations of
{ Gemma-2-9B-Instruct , Qwen3-8B } × { MiniLM-L6 , Qwen3-Embedding-0.6B } \{\text{Gemma-2-9B-Instruct}, \text{Qwen3-8B}\} \times\{\text{MiniLM-L6}, \text{Qwen3-Embedding-0.6B}\} { Gemma-2-9B-Instruct , Qwen3-8B } × { MiniLM-L6 , Qwen3-Embedding-0.6B }
Figure 8 shows the same ordering in all four configurations. PoolDPP-MAP dominates K K K -means at local sampling temperatures 1, 1.2, and 1.5 and every ancestral point, and it reaches a higher log-determinant, while K K K -means at keeps higher quality at a lower log-determinant. K K K -means dominates most PoolDPP-Sampling settings. Thus, the DPP construction is not tied to a single LM or embedding geometry.
Generalization across language models. Beyond the 2 × 2 2 \times2 2 × 2 LM/embedding ablation, we additionally validate the main FineWeb intrinsic experiment on Llama-3.1-8B-Instruct . Figure 9 reports the quality–diversity Pareto frontier on all three language models with a fixed embedding (MiniLM-L6, K = 10 K = 10 K = 10 ), following the same sweep protocol as Figure 2 : ancestral and K K K -means sweep the local sampling temperature, while PoolDPP-Sampling and PoolDPP-MAP draw the pool at local sampling temperature 1 and sweep the global temperature T T T . On every language model, PoolDPP-MAP dominates K K K -means at higher local sampling temperatures, while K K K -means keeps higher quality at a lower log-determinant. This indicates that the construction is not tied to a particular model family or post-training recipe.
Global temperature T T T . The Pareto curves in Figure 2 sweep T T T . Smaller T T T sharpens the quality score toward high-likelihood strings, while larger T T T flattens it and gives the geometric diversity term more influence. The best T T T differs across tasks and between the two modes: PoolDPP-MAP explicitly optimizes the determinant objective and typically does best with a flatter kernel than PoolDPP-Sampling, to avoid collapsing toward likelihood-dominated selections.
Weight diagnostics. The ESS of PoolDPP-Sampling’s weights w = p 1 / T / q w = p^{1/T}/q w = p 1/ T / q measures how well the pool approximates the globally annealed target. Away from T = 1 T=1 T = 1 at local sampling temperature 1, where w ≡ 1 w \equiv1 w ≡ 1 , the per-prompt ESS is below K K K for most prompts on FineWeb (36 to 49 of 50 at every plotted T ≠ 1 T \ne1 T = 1 ) and on GSM8K at local sampling temperature 1.2 (36 to 50 of 50 at every plotted T T T except T = 1 T=1 T = 1 ), and a 20- to 25-fold larger pool does not fix this at T > 1 T > 1 T > 1 (§D.1). On Ambrosia (K = 3 K=3 K = 3 ), no prompt is below K K K . Here the pool is a poor approximation of the target, yet the quality and diversity metrics still vary smoothly with T T T , so T T T remains a usable knob for the quality–diversity frontier. A high ESS can be achieved by changing the target: the ESS is high whenever the target stays close to the proposal, for example when the proposal is added into the target.
LLM-based selection. We compare against LLM-Select, the pool-reranking baseline that replaces the DPP with a language model (§6): we present 40 pool items, drawn at local sampling temperature 1 and evenly spaced in the pool’s ranking by log-probability, to Qwen3-8B and ask it to select K = 10 K=10 K = 10 diverse, high-quality completions. Over 10 pools, K K K -means on the same 40 items dominates the LLM on both axes: quality −69.4 and log-determinant −3.58, against −71.5 and −6.16. We omit LLM-Select from Figure 2 for legibility.
Efficiency. Pool construction dominates runtime; selection is a small fraction of total wall-clock time. Table 4 reports per-stage wall-clock time at the main configuration (N = 400 N=400 N = 400 , K = 10 K=10 K = 10 , Gemma-2-9B-Instruct on a single A100), and Table 5 reports selection time as N N N varies. PoolDPP-MAP is the cheapest selection method in our implementation: the greedy update uses K K K sequential updates against the pool feature matrix or dual kernel, and its measured cost is substantially below that of K K K -means across the tested pool sizes.
Table 4. Wall-clock per stage (N = 400 N=400 N = 400 , K = 10 K=10 K = 10 , A100). Selection is small relative to LM sampling.
Table 5. Selection-time scaling with pool size N N N (K = 10 K=10 K = 10 ). PoolDPP-MAP has the smallest measured selection cost across the tested pool sizes.
Weight Diagnostics
Table 6 reports, per task and plotted T T T , the effective sample size of the weights of PoolDPP-Sampling, w = p 1 / T / q w=p^{1/T}/q w = p 1/ T / q , and, for PoolDPP-MAP on Ambrosia, of the quality κ = p 1 / T \kappa=p^{1/T} κ = p 1/ T that takes the place of w w w . With self-normalized weights w ^ n = w ( y ( n ) ) / ∑ n ′ = 1 N w ( y ( n ′ ) ) \hat{w}_n=w(y^{(n)})/\sum_{n'=1}^{N}w(y^{(n')}) w ^ n = w ( y ( n ) ) / ∑ n ′ = 1 N w ( y ( n ′ ) ) , where a string drawn several times contributes one term per draw, E S S = 1 / ∑ n = 1 N w ^ n 2 \mathrm{ESS}=1/\sum_{n=1}^{N}\hat{w}_n^2 ESS = 1/ ∑ n = 1 N w ^ n 2 . At local sampling temperature 1, w = 1 w=1 w = 1 at T = 1 T=1 T = 1 , so ESS = N =N = N . At the other T T T , ESS is below K K K for most prompts on FineWeb and GSM8K at the run pool size. The larger pool raises it at T ≤ 1 T\leq1 T ≤ 1 but not above: at T = 1.22 T=1.22 T = 1.22 on FineWeb and at T = 1.05 T=1.05 T = 1.05 and 1.22 on GSM8K, all 50 prompts still have ESS below K K K . On Ambrosia, only PoolDPP-MAP at T = 1 T=1 T = 1 and T = 3 T=3 T = 3 has prompts below K K K at the run pool size (18 and 1 of 100).
Table 6. Table 6: Weight diagnostics per task and temperature. ESS/N N N is a mean over prompts; ESS med. [IQR] is the median and interquartile range over prompts, and # < K \#<K # < K counts prompts with ESS below K K K , at the run pool size N N N and at a larger pool N ′ N^{\prime} N ′ . Gemma-2-9B-Instruct throughout; 50 prompts for FineWeb and GSM8K, 100 for Ambrosia. Ambrosia at local sampling temperature 1.5 is PoolDPP-MAP. N N N : one pool of each task. N ′ N^{\prime} N ′ : two independent pools of 1,250 (GSM8K) or 4,000 (FineWeb) draws per prompt, merged, and on Ambrosia the union of the 100 pools of N = 200 N=200 N = 200 .
Intrinsic Evaluation with Held-Out and Embedder-Free Diversity Metrics
Both axes of Figure 2 are terms of the objective that PoolDPP-MAP maximizes, so its position there is partly a consequence of the objective. We re-score the FineWeb selections on one of the 10 FineWeb pools with diversity metrics outside the kernel: the log-det and the mean pairwise cosine distance under a held-out embedder (Qwen3-Embedding-0.6B, whereas the kernel uses MiniLM-L6), and two lexical metrics that use no embedder, Distinct-n n n (distinct whitespace-token n n n -grams divided by all n n n -grams in the set) and the mean pairwise Jaccard similarity of the strings’ token sets (lower is more diverse). Quality is the mean log p p p of § 6.1 . Across all 25 settings, the Spearman rank correlation with the kernel log-det is 0.979 for the held-out log-det, 0.988 for the held-out cosine distance, 0.946, 0.897, and 0.878 for Distinct-1, -2, and -3, and −0.975 for the Jaccard similarity (Table 7 ).
Table 7: FineWeb selections under non-kernel diversity metrics (Gemma-2-9B-Instruct, MiniLM-L6 kernel, K = 10 K=10 K = 10 , 50 prompts, one of the 10 pools of Figure 2 , N = 400 N=400 N = 400 ). Quality: mean log p p p per string. Kernel: log-det of the MiniLM-L6 Gram matrix, the axis of Figure 2 . Held-out : log-det and mean pairwise cosine distance under Qwen3-Embedding-0.6B. D-1, D-2: Distinct-1, Distinct-2. Jaccard: mean pairwise Jaccard similarity of token sets (lower is more diverse). Means over selected sets: 10 runs per prompt (500 sets) for every method except PoolDPP-MAP (deterministic, 50 sets). Rows are a subset of the 25 settings (ancestral sampling, K K K -means, and naive DPP at local sampling temperatures { 0.6 , 0.8 , 1.0 , 1.2 , 1.5 } \{0.6, 0.8, 1.0, 1.2, 1.5\} { 0.6 , 0.8 , 1.0 , 1.2 , 1.5 } ; PoolDPP-Sampling and PoolDPP-MAP at local temperature 1 and the five values of T T T of Figure 2 ); r s r_s r s is computed over all 25. Frontier: number of settings on the quality–diversity Pareto frontier, with the number of PoolDPP-MAP settings among them in parentheses. No uncertainty estimates.
Table 7.
A setting is on the Pareto frontier if no other setting is at least as good on quality and diversity and better on one of them. Under the kernel log-det and both held-out embedding metrics, the frontier is the five PoolDPP-MAP settings and K K K -means at local temperatures 0.6 and 0.8; under the four lexical metrics it also contains settings of the other methods (Table 7 ). No setting of another method dominates any PoolDPP-MAP setting under any of the seven metrics, so the high-diversity end of
Figure 2 does not depend on the MiniLM-L6 geometry; the quality axis remains the LM log-probability that also enters the objective.
Dual versus Primal Cost
Table 8 measures where the dual kernel C of §3 becomes faster than the primal kernel in our implementation. We time exact K K K -DPP sampling with K = 10 K=10 K = 10 on synthetic pools of N N N random unit-norm embeddings in R D \mathbb{R}^{D} R D , on one CPU thread. The dual time covers forming C, its eigendecomposition, and one draw of Alg. 1; the primal time covers forming the N × N N \times N N × N kernel and its eigendecomposition only, so it is a lower bound on the cost of a
Table 8: Wall-clock time for exact K K K -DPP sampling (K = 10 K=10 K = 10 , milliseconds, one CPU thread). Synthetic pools: N N N embeddings, each a Gaussian vector in R D \mathbb{R}^{D} R D with a shared mean direction, normalized to unit norm, and quality weights from synthetic log-probabilities. Dual : form C C C , eigendecompose it, and draw one sample with Alg. 1. Primal eig. : form the N × N N \times N N × N kernel and eigendecompose it (the sampling phase is not timed). Primal MAP : form the N × N N \times N N × N kernel and run the greedy algorithm (Alg. 2) as implemented in our code. Median of 5 repetitions for N ≤ 800 N \le800 N ≤ 800 and a single repetition for N ≥ 2,000 N \ge2{,}000 N ≥ 2 , 000 ; no uncertainty estimates.
Table 8.
In every reported experiment, PoolDPP-Sampling uses the dual sampler of Alg. 1, and a pool with Z ^ = 0 \hat{Z}=0 Z ^ = 0 is redrawn (footnote 12), so every prompt contributes. PoolDPP-MAP runs the greedy algorithm (Alg. 2) on the primal kernel over the unique pool strings, whose number is at most N N N . Its measured cost, which includes forming that kernel, is 13.7 ms at D = 384 D=384 D = 384 , N = 400 N=400 N = 400 and grows to 1.4 s (D = 384 D=384 D = 384 ) and 2.5 s (D = 1024 D=1024 D = 1024 ) at N = 10 4 N=10^{4} N = 1 0 4 .
The dual therefore pays off for pools of a few thousand strings or more, such as the N = 2,500 N=2{,}500 N = 2 , 500 pools of the pool-size experiment (§B). At the pool sizes of the main experiments, either representation costs at most 0.2 s per prompt, which is small next to LM sampling (Table 4 ).
GSM8K Extended Results
Table 9 : GSM8K per-chain accuracy vs. pass@K K K with K = 10 K=10 K = 10 . All rows use 100 pools at local sampling temperature 1.2 with the plain Qwen3-Embedding-0.6B kernel (no task instruction; §E.1); the two PoolDPP rows are at each mode’s highest pass@K K K in Figure 4 . Values are means over 50 questions and 100 pools.
Embedding Geometry and Solution Diversity on GSM8K
Embedder probe. We test whether an embedder separates correctness-critical changes from surface changes with paired edits whose labels are verified: on SQL by executing both queries, on GSM8K by the final answer and the stated arithmetic.
Each probe item is a pool string y \mathbf{y} y (Gemma-2-9B-Instruct, local sampling temperature 1, one pool) with one critical edit y c \mathbf{y}_c y c and one surface edit y s \mathbf{y}_s y s . On GSM8K, the critical edit flips the final answer token, or replaces the operator of the last correct arithmetic step (e.g., + ↔ − +\leftrightarrow- + ↔ − ) and shifts the stated final answer accordingly. The surface edit renames list markers, substitutes connectives (“So” → \to → “Therefore”), and normalizes whitespace, and it is kept only if the final answer and the stated arithmetic are unchanged. On Ambrosia, the critical edit changes one predicate (e.g., AND ↔ \leftrightarrow ↔ OR, = = = → \to → !=), and the surface edit lowercases keywords and normalizes whitespace. An item is kept only if the critical edit changes the query’s execution result and the surface edit does not.
With d ( y , y ′ ) = 1 − Φ ( y ) T Φ ( y ′ ) d(\mathbf{y},\mathbf{y}')=1-\boldsymbol{\Phi}(\mathbf{y})^{\mathsf{T}}\boldsymbol{\Phi}(\mathbf{y}') d ( y , y ′ ) = 1 − Φ ( y ) T Φ ( y ′ ) , the separation AUC (area under the ROC curve) is Pr [ d ( y , y c ) > d ( y ′ , y s ) ] \Pr[d(\mathbf{y},\mathbf{y}_c)>d(\mathbf{y}',\mathbf{y}_s)] Pr [ d ( y , y c ) > d ( y ′ , y s )] for independently drawn items y , y ′ \mathbf{y},\mathbf{y}' y , y ′ , with ties counted as 1 / 2 1/2 1/2 . A value of 0.5 means that the embedder cannot tell the two kinds of edit apart.
The instructed variant embeds the unchanged string in the Qwen3-Embedding query format with a one-line instruction. For GSM8K it reads “Given a step-by-step solution to a math word problem, represent it by its final numeric answer and the sequence of arithmetic operations it performs, ignoring wording, phrasing, and formatting. ”; for SQL, it asks to represent the query by the result set it returns.
Under the baseline GSM8K kernel (Qwen3-Embedding-0.6B), surface edits move the embedding further than correctness-critical edits (Table 10 ): the AUC is 0.051 for answer flips and 0.353 for operator flips. MiniLM-L6 has lower AUCs on both GSM8K edit types. On SQL, MiniLM-L6 reaches AUC 1.000, but its distance for the SQL surface edits is zero up to floating-point error, consistent with its uncased tokenizer, so this value follows from the choice of surface edits. The instruction raises the Qwen3-Embedding-0.6B AUC to 0.151 (answer flips), 0.842 (operator flips), and 0.892 (SQL). A one-hot encoding of the extracted final answer separates both GSM8K edit types by construction.
Table 10.
Table 10 : Embedder probe. Separation AUC = Pr [ d c r i t i c a l > d s u r f a c e ] \Pr[d_{\mathrm{critical}}>d_{\mathrm{surface}}] Pr [ d critical > d surface ] , where d d d is the cosine distance between an edited string and its original; 0.5 means the embedder does not distinguish the two edit types, and values below 0.5 mean surface edits move the embedding further. Probe strings come from one Gemma-2-9B-Instruct pool at local sampling temperature 1 (n = 582 n=582 n = 582 , 549, and 468 items per column); all embedders score the same items. Brackets: 95% percentile bootstrap CIs over probe items (2,000 resamples; resampling ignores clustering of items by question).
Instructed kernel downstream. Table 11 runs the same selection on the same 100 pools (local sampling temperature 1.2, K = 10 K=10 K = 10 , 50 questions) under the plain and the instructed kernel; Figure 10 shows the frontier under the instructed kernel. The instruction raises the number of distinct final answers that PoolDPP-MAP selects (1.75 → \to → 1.94 per set at T = 500 T=500 T = 500 , 1.65 → \to → 1.84 at T = 50 T=50 T = 50 ), but does not raise pass@10: no PoolDPP setting under either kernel exceeds ancestral sampling at the matched local temperature, and the differences at T = 10 T=10 T = 10 are negative (question-paired p q = 0.016 p_q=0.016 p q = 0.016 , §G.2).
Figure 10. Math reasoning (GSM8K) with the instructed kernel. Diversity (log-det Gram matrix) vs. pass@K = 10 K=10 K = 10 , on the 100 pools of Table 11 . Ancestral, naive DPP, and K K K -means sweep the local sampling temperature. PoolDPP-Sampling and PoolDPP-MAP hold local sampling temperature 1.2 and sweep the global temperature T T T . Error bars are 95% t t t -intervals over pools. The instruction also defines the diversity axis, so the horizontal axis is not comparable with Figure 4 .
Table 11. GSM8K under the plain and the instructed kernel (Gemma-2-9B-Instruct, local sampling temperature 1.2, K = 10 K=10 K = 10 , N = 100 N=100 N = 100 , 100 pools, 50 questions). Pass@10 ± a 95% t t t -interval over pools; per-chain accuracy as in § 6.3 ; answers is the number of distinct canonicalized final answers per set. Δ \Delta Δ : pass@10 minus ancestral, paired over questions (positive favors the row), with the two-sided sign-flip p p p -value (10 5 10^5 1 0 5 flips). Log-det is measured in each row’s own kernel and is not comparable across the two blocks.
Appending a one-hot encoding of each chain’s extracted final answer to the embedding (weight 0.99) raised PoolDPP-MAP at T = 25 T=25 T = 25 to a pass@10 of 0.975, against 0.925 for ancestral sampling and a pool ceiling of 0.987 (question-paired p = 0.0002 p=0.0002 p = 0.0002 ). This kernel encodes the evaluation’s answer key, so it is a domain-specific reference, not a general method.
Role of the determinant on GSM8K. To test whether the selected chains differ in reasoning or only in wording, we split each selected set into its 45 pairs and label every pair in which both chains state a final answer in the #### format. A pair is different answer if the canonicalized answers differ (decided by the parser). Every same-answer pair is labeled same answer, different derivation or surface only by Gemini 3.6 Flash (temperature 0), which is asked whether the two chains use different intermediate quantities or strategy, or the same underlying arithmetic.
On a stratified validation sample of 300 pairs, the judge agreed with the parser on 100 of 100 different-answer pairs. For same-answer pairs, it agreed with a deterministic rule (different multiset of stated arithmetic facts) on 90 of 100 pairs that the rule calls surface only, but on only 13 of 100 that the rule calls different derivations (it labeled the other 87 surface only). We therefore report the judge’s labels for same-answer pairs.
The selections use the instructed kernel on one pool. Table 12 shows that the different-answer share rises from 0.120 (ancestral) to 0.307 (PoolDPP-MAP), and the surface-only share falls from 0.786 to 0.579 (21 points). The same-answer, different-derivation share is 0.09–0.12 for every method: the determinant adds chains with different final answers, and it does not add more distinct derivations of the same answer.
Table 12. Pair decomposition of selected GSM8K sets (instructed Qwen3-Embedding-0.6B kernel, Gemma-2-9B-Instruct, K = 10 K=10 K = 10 , one pool, one selection run, 50 questions). Shares of the labeled pairs; each row sums to 1. Pairs counts pairs in which both chains have a #### final answer, out of at most 50 × 45 = 2,250 50 \times45 = 2{,}250 50 × 45 = 2 , 250 ; the excluded pairs contain a chain without such an answer. Agreement : fraction of same-answer pairs on which the judge’s label equals that of the deterministic arithmetic-multiset rule. Ancestral and K -means use local sampling temperature 1; PoolDPP-Sampling and PoolDPP-MAP use local sampling temperature 1.2 and T = 500 T=500 T = 500 , so the rows are not at matched local temperature. No uncertainty estimates.
Saturation Check: MATH-500
On GSM8K, ancestral pass@10 is 94% of the pool ceiling, the fraction of pools that contain a correct chain (0.925 vs. 0.987 at local sampling temperature 1.2), which leaves a selector little to gain. MATH-500 [13 , 27 ] has more headroom. We ran the same pipeline on 100 of its problems (20 per difficulty level), with Gemma-2-9B-Instruct, 10 pools of N = 100 N=100 N = 100 at each local sampling temperature 0.5, 0.8, and 1.2, Qwen3-Embedding-0.6B with the GSM8K instruction of §E.1 reworded to “math problem”, “final answer”, and “mathematical operations”, and answers checked with the math-verify package. At local sampling temperature 1.2, ancestral pass@10 is 0.735, 83% of the pool ceiling of 0.889, and a pool holds 21.5 distinct answers on average.
PoolDPP-MAP reaches the highest pass@10 (Figure 11 ): 0.777 at T = 100 T=100 T = 100 , 4.2 points above ancestral sampling at local sampling temperature 1.2 (question-paired p q < 0.001 p_q < 0.001 p q < 0.001 , §G.2), at log-det − 17.4 -17.4 − 17.4 against − 22.8 -22.8 − 22.8 . The gain comes from levels 3 to 5 (+8.6, +5.2, and +5.5 points), against +0.5 and +1.1 points at levels 1 and 2. K -means reaches 0.763 at local sampling temperature 0.8 (log-det − 23.5 -23.5 − 23.5 ), and the test does not resolve its 1.4-point gap to PoolDPP-MAP (p q = 0.12 p_q=0.12 p q = 0.12 ). PoolDPP-Sampling improves on ancestral sampling only at T = 1 T=1 T = 1 (+1.3 points, p q = 0.02 p_q=0.02 p q = 0.02 ). Above T = 1.03 T=1.03 T = 1.03 its pass@10 falls below that of ancestral sampling, down to 0.702 at T = 1.22 T=1.22 T = 1.22 (−3.4 points, p q = 0.01 p_q=0.01 p q = 0.01 , log-det − 19.9 -19.9 − 19.9 ).
Figure 11. MATH-500 saturation check (Gemma-2-9B-Instruct, 100 problems, K = 10 K=10 K = 10 , 10 pools of N = 100 N=100 N = 100 , instructed Qwen3-Embedding-0.6B kernel). Diversity (log-det of the Gram matrix) vs. pass@10, with 95% bootstrap intervals over pools. Ancestral sampling and K -means vary the local sampling temperature T ′ T' T ′ . PoolDPP varies the global temperature T T T on the pools drawn at T ′ = 1.2 T'=1.2 T ′ = 1.2 . Point labels give the varied temperature.
Beam-Search Baselines
Diverse beam search (Vijayakumar et al., [36 ] ) and determinantal beam search (Meister et al., [30 ] ) are both designed to fix vanilla beam search’s tendency to return near-identical hypotheses. Both succeed at that narrow goal, but neither matches sampling-based methods on the quality–diversity trade-off: DivBS has lower semantic and token diversity, and DetBS reaches sampling-level diversity only by collapsing quality. Table 13 reports both alongside ancestral sampling and representative PoolDPP operating points; the sampling rows are the lowest-temperature points we ran.
Table 13. Beam-search baselines vs. PoolDPP (intrinsic, FineWeb). G G G : number of beam groups of DivBS. Quality is the mean per-sequence log p ( y ∣ x ) p(\mathbf{y}\mid\mathbf{x}) p ( y ∣ x ) ; semantic diversity is log det ( Φ T Φ + 10 − 6 I ) \log\det(\mathbf{\Phi}^{\mathsf{T}}\mathbf{\Phi}+10^{-6}I) log det ( Φ T Φ + 1 0 − 6 I ) , where Φ \mathbf{\Phi} Φ collects the K = 10 K=10 K = 10 unit-norm sentence embeddings as columns; token diversity is Distinct-2, the fraction of unique whitespace bigrams across the K K K outputs. Means over 50 prompts (the sampling rows: one pool, 500 sets for ancestral sampling and PoolDPP-Sampling, 50 for PoolDPP-MAP), Gemma-2-9B-Instruct with MiniLM-L6 embeddings; higher is better on all three axes.
DivBS keeps quality high (−15.0, comparable to greedy beam search) but has the lowest semantic and token diversity of all rows. DetBS reaches sampling-level diversity only by collapsing quality to −161.8, against −33.6 to −39.6 for the sampling rows. PoolDPP-MAP at T = 10 T=10 T = 10 matches DetBS on both diversity metrics with quality −34.4 instead of −161.8, and it has higher diversity than DivBS at lower quality (−34.4 against −15.0). PoolDPP-Sampling at T = 0.43 T=0.43 T = 0.43 likewise gives up 19 nats of quality relative to DivBS for higher diversity.
Configurations. For DivBS, we use num_beams=10, num_beam_groups=10, diversity_penalty=1.0, and do_sample=False, via the transformers-community/group-beam-search HuggingFace custom_generate module. For DetBS, we use a port of Meister et al. [30 ] with the string-subsequence kernel of subsequence length n = 2 n=2 n = 2 and gap decay λ D e t B S = 0.5 \lambda_{\mathrm{DetBS}}=0.5 λ DetBS = 0.5 , beam_size=10, sub_beam_size=10, and decoding temperature T ′ = 1.0 T^{\prime}=1.0 T ′ = 1.0 . The interaction weight w D e t B S w_{\mathrm{DetBS}} w DetBS scales the kernel against the candidate scores, and w D e t B S = 0 w_{\mathrm{DetBS}}=0 w DetBS = 0 is beam search. The DetBS rows of Table 14 use a cosine Gram matrix over hashed n n n -gram counts instead (§G.1).
Table 14. Set-level baselines , each at its best setting over its own sweep (selection rule in §G.1). Gemma-2-9B-Instruct throughout. GSM8K : K = 10 K=10 K = 10 , 50 questions; pool-based methods use 100 pools of N = 100 N=100 N = 100 at local sampling temperature 1.2; answers/set counts distinct numerically canonicalized final answers; log-det uses the Qwen3-Embedding-0.6B Gram matrix. Ambrosia : K = 3 K=3 K = 3 , 100 questions, 100 pools of N = 200 N=200 N = 200 ; precision requires the whole execution result to match a golden result. FineWeb : K = 10 K=10 K = 10 , 50 prompts, 10 pools of N = 400 N=400 N = 400 (the pools of Figure 2 ); quality is mean log p ( y ∣ x ) p(y \mid x) p ( y ∣ x ) in nats and log-det uses MiniLM-L6. T ′ T' T ′ is the local sampling temperature of the pool or, for SBS and CPSBS, of the decoder, and T T T the global temperature; λ M M R \lambda_{\mathrm{MMR}} λ MMR is the MMR trade-off and w D e t B S w_{\mathrm{DetBS}} w DetBS the DetBS interaction weight. ± \pm ± is a 95% confidence interval over 10 independent decoding runs (SBS, CPSBS) or, for the pool-based rows, a 95% t t t -interval of the per-pool means over the 100 (GSM8K, Ambrosia), or 10 (FineWeb) pools.
We swept w D e t B S ∈ { 0.05 , 0.1 , 0.3 , 0.5 , 1.0 , 2.0 } w_{\mathrm{DetBS}}\in\{0.05,0.1,0.3,0.5,1.0,2.0\} w DetBS ∈ { 0.05 , 0.1 , 0.3 , 0.5 , 1.0 , 2.0 } and T ′ ∈ { 0.7 , 1.0 , 1.3 } T^{\prime}\in\{0.7,1.0,1.3\} T ′ ∈ { 0.7 , 1.0 , 1.3 } on the first 8 prompts. The resulting T ′ × w D e t B S T^{\prime}\times w_{\mathrm{DetBS}} T ′ × w DetBS Pareto frontier sits strictly below ancestral sampling at every diversity level. The w D e t B S = 1.0 w_{\mathrm{DetBS}}=1.0 w DetBS = 1.0 row, run on all 50 prompts, is the operating point on that frontier closest to the sampling rows on diversity.
The code, the sweep, and the outputs are in baselines/detbs_ssk and analysis/beam_baselines_intrinsic.json of the repository.
Why DetBS falls short. DetBS’s string-subsequence kernel measures bigram overlap, not semantic similarity, so it promotes a different kind of diversity than the embedding-based metric rewards.
Set-Level Baselines, Significance Tests, and Pool Coverage
Set-Level Baselines
We compare PoolDPP with five set-level baselines. MMR and MBR rerank the same pools, embeddings, and K K K as PoolDPP; SBS, CPSBS, and DetBS are decoding-time methods that produce a size-K K K set directly from the language model.
MMR (Carbonell and Goldstein [5 ] ) starts from the highest-likelihood pool item and greedily adds the item maximizing λ M M R ℓ ( y ) − ( 1 − λ M M R ) max y ′ ∈ S cos ( ϕ ( y ) , ϕ ( y ′ ) ) \lambda_{\mathrm{MMR}}\ell(y)-(1-\lambda_{\mathrm{MMR}})\max_{y^{\prime}\in S}\cos(\phi(y),\phi(y^{\prime})) λ MMR ℓ ( y ) − ( 1 − λ MMR ) max y ′ ∈ S cos ( ϕ ( y ) , ϕ ( y ′ )) , where ℓ \ell ℓ is log p p p min–max normalized within the pool. We sweep λ M M R ∈ { 0 , 0.1 , 0.3 , 0.5 , 0.7 , 0.9 , 1 } \lambda_{\mathrm{MMR}} \in\{0, 0.1, 0.3, 0.5, 0.7, 0.9, 1\} λ MMR ∈ { 0 , 0.1 , 0.3 , 0.5 , 0.7 , 0.9 , 1 } ; λ M M R = 1 \lambda_{\mathrm{MMR}}=1 λ MMR = 1 is quality top-K K K .
MBR (Kumar and Byrne [26 ] ) with a cosine-similarity utility returns the K K K pool items with the highest mean cosine similarity to the pool. Its only setting is the pool’s local sampling temperature.
Stochastic beam search (SBS) (Kool et al. [23 ] ) draws K K K distinct sequences without replacement from the locally annealed model with the Gumbel-top-K K K trick. We sweep the local sampling temperature T ′ T^{\prime} T ′ .
Conditional Poisson SBS (CPSBS) (Meister et al. [29 ] ) replaces the per-step top-K K K of beam search with a conditional Poisson sample of size K K K over the candidate extensions, with inclusion probabilities set by the annealed prefix probabilities. We sweep T ′ T^{\prime} T ′ and draw each per-step sample from the highest-weight candidates, which changes the per-step distribution by at most 10 − 7 10^{-7} 1 0 − 7 in total variation.
Determinantal beam search (DetBS) (Meister et al. [30 ] ) replaces the per-step top-K K K with a greedy K K K -DPP MAP step on the candidate scores plus w D e t B S w_{\mathrm{DetBS}} w DetBS times a similarity Gram matrix; w D e t B S = 0 w_{\mathrm{DetBS}}=0 w DetBS = 0 is beam search. We use a cosine Gram matrix over hashed unigram and bigram counts, the gapless limit of the string-subsequence kernel, whose cost is quadratic in sequence length. We sweep w D e t B S w_{\mathrm{DetBS}} w DetBS .
SBS and CPSBS use 10 independent runs per prompt and temperature; DetBS is deterministic. Our SBS, CPSBS, and DetBS implementations reproduce exact enumeration on small enumerable models, and the released code includes these tests.
Table 14 reports each method at its best setting over its own sweep: the highest pass@10 on GSM8K (ties broken by per-chain accuracy), the highest recall on Ambrosia, and on FineWeb the most diverse setting whose quality is at least that of K K K -means at local sampling temperature 1 (− 40.3 -40.3 − 40.3 nats). MBR has a single FineWeb point, below this quality, and is shown there.
On Ambrosia, PoolDPP-MAP has the highest recall (0.251), followed by MMR (0.246), PoolDPP-Sampling (0.244), and K K K -means (0.240). The best decoding-time recall is SBS at 0.235, against 0.233 for ancestral sampling; SBS, CPSBS, DetBS, and MBR reach higher precision (0.392–0.417 against 0.322 for PoolDPP-MAP).
On GSM8K, SBS at T ′ = 1.2 T^{\prime}=1.2 T ′ = 1.2 has the highest pass@10 (0.938 ± 0.009) and 2.91 distinct final answers per set, against 0.912–0.915 and 1.68–1.75 for MMR and both PoolDPP modes; CPSBS and DetBS reach at most 0.820. MBR has the highest per-chain accuracy (0.773) and, among the reranking methods, the fewest distinct answers (1.26) and the lowest log-determinant (−29.6), because it selects the chains that agree with the pool consensus.
On FineWeb, among settings above the quality threshold, PoolDPP-MAP has the highest log-determinant (−2.36) and MMR the next (−3.75, at 2.3 nats higher quality), so neither dominates the other; SBS at T ′ = 0.6 T^{\prime}=0.6 T ′ = 0.6 matches ancestral sampling at the same temperature in quality (−39.5 vs. −39.4), and CPSBS and DetBS stay below −25.
Paired Significance Tests
Every method is evaluated on the same pools and questions, so we test each comparison with a paired sign-flip permutation test instead of comparing the marginal confidence intervals of § 6.2 and Figure 4 . For methods A A A and B B B , we compute one paired difference A − B A-B A − B per unit and its mean over units. The null distribution flips the sign of each unit’s difference independently with probability 1 / 2 1/2 1/2 (100,000 random sign vectors), and p p p is the two-sided fraction of draws whose absolute mean is at least the observed one, so p p p cannot resolve below 10 − 5 10^{-5} 1 0 − 5 . Positive differences favor A A A , the PoolDPP variant.
We use two pairing units. Question-paired tests average each method over pools and runs, giving one value per question (n = 50 n=50 n = 50 on GSM8K, n = 100 n=100 n = 100 on Ambrosia), and test whether the difference holds over questions. Pool-paired tests average over questions, giving one value per pool (n = 100 n=100 n = 100 ), and test reproducibility over pool draws for a fixed question set. We treat the question-paired test as primary. The reported interval is a 95% percentile bootstrap over questions (10,000 resamples) of the mean paired difference, which is the same under both pairings.
Table 15 lists every comparison. On GSM8K, with either kernel, no tested PoolDPP setting improves pass@10 over ancestral sampling at the matched local sampling temperature 1.2, and PoolDPP-MAP at T = 500 T=500 T = 500 does not significantly exceed K K K -means under the question-paired test.
Table 15: Paired differences, first method minus second; positive values favor the first. Set metric: pass@10 (GSM8K) or recall (Ambrosia). Item metric: per-chain accuracy (GSM8K) or precision (Ambrosia). CI: 95% bootstrap interval over questions of the set-metric difference. p q p_q p q and p p o o l p_{\mathrm{pool}} p pool : two-sided sign-flip permutation tests with 10 5 10^5 1 0 5 random sign vectors, paired over questions and over pools; < 10 − 5 <10^{-5} < 1 0 − 5 marks the resolution limit. GSM8K : Gemma-2-9B-Instruct, K = 10 K=10 K = 10 , 50 questions, 100 pools of N = 100 N=100 N = 100 ; every method draws its pool at local sampling temperature T ′ = 1.2 T'=1.2 T ′ = 1.2 . Ambrosia : K = 3 K=3 K = 3 , 100 questions, 100 pools of N = 200 N=200 N = 200 .
Table 15.
On Ambrosia, PoolDPP-Sampling at T = 0.82 T=0.82 T = 0.82 and PoolDPP-MAP at T = 10 T=10 T = 10 have higher recall and lower precision than ancestral sampling at its highest-recall local temperature (recall p q = 6 × 10 − 5 p_q=6\times10^{-5} p q = 6 × 1 0 − 5 and 0.015). Against K K K -means at local temperature 1, the question-paired test does not resolve the recall difference of either mode, while the pool-paired test resolves both.
Ambrosia Pool Ceiling
Every pool-based method selects from the pool, so its recall is bounded by the fraction of gold interpretations that the pool contains. We call this fraction the pool coverage of a (question, pool) cell: a pool string covers a gold interpretation if executing it on the question’s database returns exactly the gold query’s result, the strict rule of § 6.2 . The 100 questions have 2 (56 questions) or 3 (44 questions) gold interpretations.
Table 16 a gives the coverage by local sampling temperature. It is highest at 1.3 (0.418), against 0.384 at local temperature 1, and it still increases from N = 100 N=100 N = 100 to N = 200 N=200 N = 200 at every local temperature, so it has not saturated at the pool size we use. Relative to this ceiling (Table 16 b), all four methods recover between 0.508 (ancestral sampling) and 0.528 (PoolDPP-Sampling) of their pools’ coverage at their settings in Table 14 . Both baselines recover the largest fraction at the coldest pool, where coverage is lowest.
Table 16. Ambrosia pool ceiling (Gemma-2-9B-Instruct, MiniLM-L6, K = 3 K=3 K = 3 , 100 pools, 100 questions). (a) Pool coverage: fraction of a question’s gold interpretations matched by execution by at least one pool string, averaged over questions and pools; for N < 200 N < 200 N < 200 , averaged over 10 random subsamples of the pool. None and All : fraction of (question, pool) cells with coverage 0 and 1 at N = 200 N=200 N = 200 . 95% bootstrap CI half-widths over pools are at most 0.0023 for every coverage entry. (b) Each method at its setting in Table 14 . Recall: fraction of gold interpretations matched by the K K K selected queries. Fraction of coverage: recall divided by the question’s mean coverage over the 100 pools at the same local temperature, averaged over questions with nonzero coverage, then over runs and pools. ±: half-width of the 95% bootstrap CI over the 100 pools (10 4 10^4 1 0 4 resamples).
Sequence Length and the Quality Term
The quality term uses the raw sequence probability p ( y ) p(y) p ( y ) without length normalization, so log p \log p log p decreases with length: over the unique strings of one pool, the Pearson correlation between character length and log p \log p log p is negative on every task and close to − 1 -1 − 1 on Ambrosia at local sampling temperature 1.5 (Table 17 ). Within a prompt, the coupling comes from a tail of long, low-quality strings: on Ambrosia at local temperature 1.5, the longest fifth of each prompt’s pool averages 2,742 characters and 0.5% of it executes, against 71% of the shortest fifth.
Table 17. Length and log-probability (Gemma-2-9B-Instruct). r r r : Pearson correlation between character length and log p \log p log p over all unique strings of one pool, pooled across prompts (n = 4 , 999 n = 4,999 n = 4 , 999 GSM8K strings; 15,045 and 19,150 Ambrosia strings at local temperatures 1.0 and 1.5). Remaining columns: statistics over the unique strings of each prompt’s pool, averaged over prompts and the 100 pools. Quality by length quintile : fraction of strings with the quality label in each within-prompt length quintile, shortest (Q1) to longest (Q5); Chars : mean characters in Q1 and Q5; r s r_s r s : Spearman correlation between log p \log p log p and length; AUC: Pr [ log p ( y + ) > log p ( y − ) ] \Pr[\log p(y^+) > \log p(y^-)] Pr [ log p ( y + ) > log p ( y − )] for a string y + y^+ y + with the label and y − y^- y − without it. Arrows: full pool → shorter half (length at most the prompt’s median). r r r and r s r_s r s do not depend on the label and are shown once per task and local temperature. Single computation; no uncertainty estimates.
Restricting each prompt’s pool to its shorter half removes most of the coupling (the Spearman correlation r s r_s r s in Table 17 ), and log p \log p log p still ranks strings by quality there: the AUC changes little at local temperature 1 and falls from 0.856 to 0.747 for golden Ambrosia queries at 1.5, because part of the full-pool separation is the separation of the long, non-executing tail.
A length-only selection does not reproduce the FineWeb frontier. On pools drawn at local sampling temperature 1, splitting each prompt’s pool into K = 10 K=10 K = 10 equal-width length bins and keeping the most probable string in each nonempty bin reaches quality − 41.8 -41.8 − 41.8 and log-det − 4.59 -4.59 − 4.59 (one pool), and PoolDPP-MAP at T = 50 T=50 T = 50 , on the same pool, is better on both axes, with quality − 39.7 -39.7 − 39.7 and log-det − 2.30 -2.30 − 2.30 .
Generation length. Our pools are drawn with a cap on generation length: at most 50 new tokens on FineWeb, 800 on Ambrosia, and 4,000 tokens of prompt and output together on GSM8K. A string that reaches the cap without generating EOS is kept and scored by its prefix probability. This is exactly PoolDPP for the capped language model p L p_L p L , which agrees with p p p on strings that end within the cap and assigns each capped string its prefix probability. p L p_L p L is a language model, so §5 applies to it as stated; the target is the K K K -DPP with quality p L 1 / T p_L^{1/T} p L 1/ T .
Qualitative Examples
We provide sample outputs comparing ancestral sampling and PoolDPP. These are representative examples; aggregate statistics are in the main text.
Open-Ended Generation (FineWeb)
Example 1: Rolling Stones. Prompt: “The Rolling Stones in Concert has since been released solely by ABKCO Records. The band would remain incensed with Klein for decades for that act. Klein died in 2009. ”
Ancestral sampling produces continuations focused on the Klein controversy:
“Following Klein’s death, the Stones published their memoir ‘Life’ in 2010...”
“‘There was a lot of bad blood,’ Scorsese told TheWrap...”
“The Rolling Stones have a tumultuous relationship with their music catalog...”
PoolDPP covers distinct topics:
“The Rolling Stones have played many legendary concerts at Madison Square Garden...” (concert venues )
“The Rolling Stones haven’t sought to reclaim the rights to the Monterey Pop concert footage...” (specific concert )
“The live album ‘Get Yer Ya-Ya’s Out!’ also remains controversial...” (specific album )
“Early in their career, the band signed with Decca Records...” (different era )
Example 2: Creative writing. Prompt: “It is a field that is both fascinating, misunderstood, and in some cases resented. Arguably the best division in the Foundation. ”
Ancestral sampling shows variance in quality, including off-topic drift:
“Xenosanthropologists dedicate their lives to the study of alien life...”
“The Division of Genetics holds the secrets to life itself...”
“If you mean a good deal on a product, you would tell someone that you got a steal. Knives, particularly Damascus steel knives...” (off-topic drift )
PoolDPP produces diverse yet coherent continuations, each picking a distinct “division”:
“Black Ops—the shadows, the rumors, the whispered commands...” (covert operations )
“I speak of course of the Screws... tasked with maintaining order...” (social control )
“I’m talking about Ethics. What good is power without a moral compass?” (philosophy )
“The Genesis Project is about ensuring survival for millions of years...” (long-term planning )
PoolDPP produces structured diversity (meaningful variations) rather than noisy variance (random drift including failure modes like the knife tangent).
SQL Generation (Ambrosia)
Example 1: Airport terminals. Query: “Which terminals are in airports? ”
This query is ambiguous between universal quantification (terminals in all airports) and existential quantification (terminals in any airport).
Ancestral sampling produces only the universal interpretation:
SELECT terminal_id FROM Airports_Terminals GROUP BY terminal_id HAVING COUNT(DISTINCT airport_id) = (SELECT COUNT(*) FROM Airports);
SELECT DISTINCT t.id FROM Terminals t JOIN Airports_Terminals at ON t.id = at.terminal_id GROUP BY t.id HAVING COUNT(DISTINCT at.airport_id) = (SELECT COUNT(*) FROM Airports);
(All 3 samples use variants of the GROUP BY ... HAVING COUNT pattern)
PoolDPP captures both interpretations:
SELECT terminal_id FROM Airports_Terminals GROUP BY terminal_id HAVING COUNT(DISTINCT airport_id) = (SELECT COUNT(*) FROM Airports); (universal: in all airports )
SELECT DISTINCT terminal_id FROM Airports_Terminals; (existential: in any airport )
Example 2: Fashion designs. For the query “Which terminals are in airports? ”, ancestral sampling produces three variants of the universal interpretation (terminals in all airports): ... GROUP BY terminal_id HAVING COUNT(DISTINCT airport_id) = (SELECT COUNT(*) FROM Airports). PoolDPP captures both the universal and the existential reading (terminals in any airport): SELECT DISTINCT terminal_id FROM Airports_Terminals.
Query: “What are the fashion designs? ”
Ancestral sampling repeats the same interpretation:
SELECT design_name FROM Fashion_Design; (just names )
SELECT design_name, color_name, fabric_type FROM Fashion_Design JOIN Color_Palette ON ... JOIN Fabric_Choice ON ...; (enriched )
SELECT design_name FROM Fashion_Design; (duplicate )
PoolDPP covers three distinct interpretations:
SELECT design_name FROM Fashion_Design; (projection: just names )
SELECT * FROM Fashion_Design; (raw table dump )
SELECT design_name, color_name, fabric_type FROM Fashion_Design fd JOIN Color_Palette cp ON ... JOIN Fabric_Choice fc ON ...; (human-interpretable descriptions via joins )
These are three valid but conceptually different answers to “what are the designs?”; PoolDPP finds all three, while ancestral sampling produces a duplicate.
Math Reasoning (GSM8K)
Example 1: Freelance blogger. Prompt: “Meredith is a freelance blogger who writes about health topics... A blog article takes an average of 4 hours to research and write about. Last week, she wrote 5 articles on Monday and 2 / 5 2/5 2/5 times more articles on Tuesday than on Monday. On Wednesday, she wrote twice the number of articles she wrote on Tuesday. Calculate the total number of hours she spent writing articles in the three days. ”
The phrase “2 / 5 2/5 2/5 times more” is linguistically ambiguous.
Ancestral sampling predominantly produces one interpretation:
PoolDPP finds both interpretations:
“Tuesday: 5 + 2 = 7 5 + 2 = 7 5 + 2 = 7 articles → \rightarrow → 104 hours” (additive: “2 / 5 2/5 2/5 more” = add 2 / 5 2/5 2/5 of Monday )
“Tuesday: ( 2 / 5 ) × 5 = 2 (2/5)\times5 = 2 ( 2/5 ) × 5 = 2 articles → \rightarrow → 44 hours” (multiplicative: “2 / 5 2/5 2/5 times” = 2 / 5 2/5 2/5 as many )
Even when the model’s mode favors one interpretation, the DPP enhances coverage of both readings, which is valuable for pass@K K K .
Example 2: Dog walking. Prompt: “John takes care of 10 dogs. Each dog takes .5 hours a day to walk and take care of their business. How many hours a week does he spend taking care of dogs? ”
Both methods arrive at the correct answer (35 hours), but PoolDPP produces a much wider range of formatting and presentation styles.
Ancestral sampling produces uniform structure:
All 10 samples follow the same two-step pattern with minor wording variations
Consistent formatting: numbered steps, same answer format
PoolDPP produces format outliers alongside standard solutions:
Standard prose explanation
Bullet points with inline math: “10 × 0.5 = 5 10 \times0.5 = 5 10 × 0.5 = 5 hours/day”
Heavy LATEX display math formatting
Russian-language output (Cyrillic “Answer: 35.0”)
Placeholder template with no actual computation
Non-standard answer formats: $$35$$, ***35***
Some outliers (placeholder templates, wrong language) are failure modes, but this diversity can aid pass@K K K when downstream systems parse outputs flexibly. It illustrates how the DPP explores the full space of model behaviors rather than collapsing to the mode.
Notation and Terminology
Conventions. Strings are bold italic (y \mathbf{y} y , Y \mathbf{Y} Y ); vectors and matrices are bold upright (ϕ ( y ) \boldsymbol{\phi}(\mathbf{y}) ϕ ( y ) , Φ S \boldsymbol{\Phi}_{S} Φ S , L \mathbf{L} L , I \mathbf{I} I ); a set of strings is S S S . Where a random string or set must be told apart from a fixed one of the same name, the random one is capital and bold italic (Y j \mathbf{Y}_{j} Y j vs. y j \mathbf{y}_{j} y j , S \mathbf{S} S vs. S S S ), which also keeps it apart from matrices; elsewhere, the law under which a quantity is drawn (y ( n ) ∼ q \mathbf{y}^{(n)} \sim q y ( n ) ∼ q , ω ∼ μ \omega\sim\mu ω ∼ μ ) says what is random. Each symbol names one object; a baseline’s hyperparameters carry the baseline’s name (λ M M R \lambda_{\mathrm{MMR}} λ MMR , w D e t B S w_{\mathrm{DetBS}} w DetBS ). Each accent has one meaning: a hat marks a quantity computed from a pool or by Monte Carlo (B ^ \widehat{B} B , C ^ \widehat{C} C , L ^ \widehat{L} L , Z ^ \widehat{Z} Z , P ^ ω \widehat{P}_{\omega} P ω , w ^ n \widehat{w}_{n} w n , V ^ \widehat{V} V ); a bar marks a law averaged over the pool (P ‾ \overline{P} P ); a tilde marks the naive sampler of Theorem A.3 and its estimate (f ~ \widetilde{f} f ). Expectations, variances, and probabilities carry their random variable or law as a subscript (E ω \mathbb{E}_{\omega} E ω , V q ⊗ c V_{q \otimes c} V q ⊗ c , Pr L b \Pr_{L_b} Pr L b ), and sums carry their domain; generic probability facts stated for arbitrary random variables are the exception. Index letters are fixed: t t t is a token position, n n n and n ′ n' n ′ are pool positions, j j j indexes the members of a K K K -tuple, d d d and d ′ d' d ′ index eigenvectors or coordinates of R D \mathbb{R}^{D} R D , and m m m indexes repeated sets. p p p is the language model and q q q the proposal. T T T is the global temperature in κ = p 1 / T \kappa= p^{1/T} κ = p 1/ T , and T ′ T' T ′ is the local sampling temperature, at which a pool is drawn.
Notation.
Table 18.
Terminology.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
Answer: [Yes]
Justification: The abstract and § 1 state three claims, each substantiated in the body: the pool-based DPP sampler with two inference modes (§4), a finite-sample O ( 1 / N ) \mathcal{O}(1/N) O ( 1/ N ) KL bound with an exact variance identity (Theorem 5.2 ), and quality–diversity frontier gains on FineWeb (from PoolDPP-MAP) and Ambrosia, together with higher diversity at about the same pass@K K K on GSM8K, with and without an instructed embedder (§§ E.1 and 6).
Guidelines:
The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The Conclusion collects the limitations in one paragraph, and each is discussed where it arises. The LM-hidden-state embedding variant does not consistently improve over off-the-shelf embedders (§3). On GSM8K, neither the baseline nor the instructed embedder lets either PoolDPP mode improve pass@K K K at matched temperature (§§ E.1 and 6.3). The weights of PoolDPP-Sampling have an effective sample size below K K K for most prompts on FineWeb and GSM8K away from T = 1 T=1 T = 1 (§D). The bound is evaluated only on instances built from our pools, where it is vacuous on GSM8K at the pool size we run (§5). Achievable diversity is bounded by the pool’s coverage, and the MAP mode is a greedy approximation to the pool’s mode, not the population’s. The dominant cost is pool construction: drawing N N N sequences from the LM is much more expensive than the subsequent selection (Table 4 ). The paper’s scope is set at the sequence level, to ground a principled diversity objective with finite-sample guarantees; we leave further extensions to future work.
Guidelines:
The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate “Limitations” section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that
preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Theorem 5.1, Theorem A.2, Theorem 5.2 , and Theorem A.4 state their assumptions inline; complete proofs are in §A, and machine-checked Lean proofs are described in §A.1.
Guidelines:
The answer [N/A] means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Pseudocode for both inference modes is provided in 1 and 2; all language models, embedding models, and datasets used are publicly available; pool sizes, subset sizes, temperature settings, and per-method parameter sweeps are reported in §§ D and 6, and the code and the commands that reproduce each table and figure are released (next item).
Guidelines:
The answer [N/A] means that the paper does not include experiments.
If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All datasets used (FineWeb, Ambrosia, GSM8K) and all language and embedding models (Gemma-2-9B-Instruct, Qwen3-8B, Llama-3.1-8B-Instruct, MiniLM-L6, Qwen3-Embedding-0.6B) are publicly available under their original licenses. Our implementation of PoolDPP, the experiment scripts, the outputs quoted in the paper, and the Lean proofs are released at https://github.com/rycolab/pool-dpp , whose README lists the command that produces each table and figure; pseudocode for the algorithms is also provided in 1 and 2.
Guidelines:
The answer [N/A] means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy ) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy ) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?
Answer: [Yes]
Justification: §6 specifies the language models, embedding models, datasets, subset size K K K , pool size N N N , and metric definitions; the per-method parameter sweep traced by each Pareto curve is described inline (§§ § 6.1 to § 6.3 ); ablations over N N N , K K K , the embedding/LM choice, and the global temperature T T T are in §D.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All Pareto figures display 95% t t t -intervals over independently sampled pools (10 on FineWeb, 100 on Ambrosia and GSM8K); the pool count, interval type, and quantity are stated in each caption and in §6. Comparisons that support claims use paired sign-flip permutation tests over questions and over pools (§G.2).
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Tab. 4 reports per-stage wall-clock time for N = 400 N=400 N = 400 and K = 10 K=10 K = 10 on a single A100 GPU, and Tab. 5 reports selection-time scaling with the pool size. Pool construction via vLLM dominates total runtime; the DPP selection step itself is two orders of magnitude cheaper.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?
Answer: [Yes]
Justification: The research uses publicly released language models and public-domain or appropriately licensed datasets, and it involves no human subjects. We have reviewed the NeurIPS Code of Ethics and find no conflict.
Guidelines:
The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [N/A]
Justification: This is a foundational, technical paper on inference-time sampling from pretrained language models. It has no direct path to a specific application or deployment, and the impacts would be inherited from whatever downstream system uses it. The paper does not introduce new societal risks beyond those of the underlying base models.
Guidelines:
The answer [N/A] means that there is no societal impact of the work performed.
If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that
an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?
Answer: [N/A]
Justification: The paper introduces an inference-time sampling algorithm that operates on top of publicly released language models. It does not release a new pretrained model, scraped dataset, or generative system that would carry distinct misuse risks beyond those of the underlying base models.
Guidelines:
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All language models (Gemma-2-9B-Instruct, Qwen3-8B, Llama-3.1-8B-Instruct), embedding models (MiniLM-L6, Qwen3-Embedding-0.6B), datasets (FineWeb, Ambrosia, GSM8K), and baseline implementations (DivBS, DetBS) are cited with their original references in §6. We use each asset under its original license.
Guidelines:
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The new assets are our code, the outputs quoted in the paper, and the Lean formalization of the theorems, released at https://github.com/rycolab/pool-dpp . The README documents installation and the command for each experiment, and the lean/ and baselines/detbs_ssk/ folders have their own READMEs. The paper releases no new dataset or pretrained model; pseudocode and analysis for the proposed sampler are in 1 and 2 and §5.
Guidelines:
The answer [N/A] means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [N/A]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [N/A]
Justification: The paper does not involve research with human subjects.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: Two analyses use LLMs as components: Qwen3-8B is the LLM-based selection baseline (§D), and Gemini 3.6 Flash is the judge that labels pairs of GSM8K chains as differing in answer, derivation, or surface only (§ 1 ); both are described with their settings and validated in the appendix. Our use of AI agents to edit and draft text, to double-check proofs, and to help write the Lean formalization is described in the AI-use disclosure at the end of the Conclusion. Pretrained language models are otherwise the object of study, not a component of the method.
Guidelines: