A Theoretical Framework for Statistical Evaluability of Generative Models

arXiv: 2604.05324v2 [cs.LG], June 2026

The paper addresses a fundamental question in generative model evaluation: Can the performance of generative models be evaluated statistically from finite samples?

The authors motivate this by contrasting generative model evaluation with supervised learning. In supervised learning, performance metrics such as error rate are well-defined, and test error reliably approximates population error given sufficiently large datasets. However, evaluation is more challenging for generative models due to their open-ended nature: it is unclear which metrics are appropriate and whether such metrics can be reliably evaluated from finite samples.

The authors note that while "benchmarks provide standardized and interpretable comparisons, they assess performance on a fixed set of tasks, making it difficult to reason about generalization beyond the benchmark. Human feedback, in contrast, requires costly human labor. Statistical evaluation—assessing models using held-out IID data drawn from a ground truth distribution—remains the simplest, cheapest, and most scalable way to compare models."

The paper highlights concrete failures of common evaluation approaches. For example, "perplexity can fail to evaluate cross-entropy because log q(x) is typically unbounded and possibly heavy-tailed: rare events with small q(x) yield arbitrarily large losses, invalidating standard concentration inequalities. Similarly, for Total Variation Distance, when the domain is huge, TV is not estimable, which means that given two models, we cannot determine which one has lower TV distance to q⋆ even when the test data size is large."

Definition 2.1 (Evaluation Metric): Given a ground-truth model q⋆ and a model q to be evaluated, an evaluation metric f: M2 ↦ R≥0 ∪ ∞ assigns a non-negative real-valued score f(q, q⋆) to the model q.

Definition 2.2 (Score Function): A score function s: M × X* ↦ R ∪ ∞, given a model q and a set of evaluation data Seval, outputs a real-valued score s(q, Seval) of this model.

An evaluation algorithm is induced by a score function by outputting the model with the smaller score, breaking ties randomly.

Definition 2.3 (Evaluability): "For any evaluation metric f: M2 ↦ R≥0 ∪ ∞ and c ≥ 1, we say f is c-weakly evaluable if there exists a function mevl,f: (0,1)2 × R≥1 ↦ N and an evaluation algorithm A such that for every pair of models q1, q2 ∈ M, every ε, δ ∈ (0,1) and every ground-truth model q⋆, given IID evaluation data Seval = x1,..., xm of size m ≥ mevl,f(ε, δ, c) with xi ∼ q⋆, with probability at least 1 − δ, A(q1, q2, Seval) = q1 =⇒ f(q1, q⋆) ≤ c · f(q2, q⋆) + ε, and A(q1, q2, Seval) = q2 =⇒ f(q2, q⋆) ≤ c · f(q1, q⋆) + ε."

We say f is strongly evaluable when c = 1. We say f is not weakly evaluable if it is not c-weakly evaluable for any c ≥ 1.

Definition 2.4 (Estimability): "For any finite-valued evaluation metric f: M2 ↦ R≥0, we say f is estimable if there exists a function mest,f: (0,1)2 ↦ N and a score function s: M × X* ↦ R such that for any ε, δ ∈ (0,1), for any ground-truth model q⋆ and any model q ∈ M, given IID evaluation data Seval = x1,..., xm of size m ≥ mest,f(ε, δ) with xi ∼ q⋆, with probability at least 1 − δ, s(q, Seval) − f(q, q⋆) ≤ ε."

The authors note: If f is estimable by some score function s, then it is strongly evaluable by an evaluation algorithm induced by the same s.

Definition 3.1 (IPMs): Given a class F of X ↦ [0,1] functions, the IPM w.r.t. F is dF(q⋆, q) = sup ϕ∈F E x∼q⋆[ϕ(x)] − E x∼q[ϕ(x)].

The paper establishes results for both binary-valued and real-valued test classes.

Theorem 3.2: "Consider F ⊂ 0,1 X being a class of binary functions. There is a dichotomy of evaluability of dF for all binary function class F:

• If F has finite VC dimension VCdim(F) < ∞, dF is estimable, thus strongly evaluable with sample complexity O((d log(1/ε) + log(1/δ))/ε2), where d = VCdim(F).

• If F has unbounded VC dimension (i.e., F shatters arbitrarily large sets), then dF is 3-weakly evaluable with sample complexity min O((2 + log(1/δ))/ε2), O(8 log 3/2(1/δ)/ε 5/2). And there does not exist a c′ < 3 such that dF(q⋆, ·) is c′-weakly evaluable."

The proof of the first item uses standard concentration inequalities and Sauer's Lemma. For the second item, the proof leverages results from Bousquet et al. (2019) on density estimation, showing that a 3-weak evaluation algorithm can be constructed via the empirical distribution, and that the factor of 3 is optimal by contradiction with known lower bounds.

Definition 3.3 (γ-Fat-Shattering Dimension): "Given a class F ⊂ [0,1] X of real-valued functions that map from X to [0,1], we say that a subset x1,..., xn ⊆ X is γ-shattered by F if there exist thresholds r1,..., rn ∈ [0,1] such that for all labeling vectors y ∈ ±1 n, there exists g ∈ F such that yi = +1 =⇒ g(xi) ≥ ri + γ, yi = −1 =⇒ g(xi) ≤ ri − γ."

Proposition 3.4: "Given a function class F ⊂ [0,1] X, the IPM dF satisfies:

• If F has finite γ-fat-shattering dimension Pdimγ(F) < ∞ for all γ ∈ (0, 1/2), dF is estimable, thus strongly evaluable with sample complexity O((1/ε2)(d log(1/ε2) + log(1/δ))), where d = Pdim ε/24(F).

• If there exists γ ∈ (0, 1/2) such that F has arbitrarily large γ-fat-shattering dimension, dF is 3-weakly evaluable."

The authors note this result is "weaker than Theorem 3.2 since in the second case, we do not establish that dF(q⋆, q) is not c′-weakly evaluable for c′ < 3."

Definition 3.5 (Finite taxonomy of sample complexities): "We say that a class of evaluation metrics C admits a finite taxonomy of sample complexities if there exists a finite (or countable) list of functions M1(ε, δ), M2(ε, δ),... such that for every estimable metric f ∈ C, there exists some index i and an estimator with the property that for every pair of distributions q1, q2 ∈ M, the sample complexity of estimating f(q1, q2) is at most Mi(ε, δ) for all sufficiently small ε, δ > 0."

Theorem 3.6: "There does not exist a finite taxonomy of sample complexities for estimable IPMs. More precisely, for any sequence of functions M1(ε, δ), M2(ε, δ),... (finite or countable), and for any i ∈ N, there exists an estimable IPM dF (with test function class F) and distributions q1, q2 ∈ M such that the estimation sample complexity for dF(q1, q2) is greater than Mi(ε, δ) for all sufficiently small ε, δ > 0."

The proof constructs a domain X = ∪ k≥1 X k partitioned into finite subsets, with F defined as scaled Boolean function classes on each X k. The construction shows that while the IPM is estimable (finite fat-shattering dimension for any fixed γ), the sample complexity can be made arbitrarily large for any prescribed sequence of functions.

Definition 3.7 (Fixed Statistical Test): Given any test function g: X ↦ R, we define the fixed statistical test w.r.t g as f g fixed(q, q⋆) = E x∼q⋆[g(x)] − E x∼q[g(x)].

Theorem 3.8: "Given a test function g: X ↦ R,

• If there exists a fixed B < ∞ such that g(x) ≤ B for all x ∈ X, then f g fixed is estimable, thus strongly evaluable with sample complexity O(B2 log(1/δ)/ε2).

• If there exists x2 ∈ X with 0 0, there exists x1 ∈ X with g(x1) > Bg(x2), then f g fixed is not weakly evaluable."

The proof of the second bullet uses a construction with two models q1 and q2 that are close in total variation (so their sample laws are indistinguishable) but have very different values of the fixed statistical test, creating a contradiction with any claimed weak evaluability.

Definition 4.1 (Rényi divergence): "Given α > 1, the α-Rényi divergence is defined as f α-Rényi(q, q⋆) = (1/(α−1)) log Σ x∈X q⋆(x) α q(x) 1−α."

Theorem 4.2: "For any α > 1, f α-Rényi is not weakly evaluable."

Proof Sketch: The construction uses three points x0, x1, x2 with:

• q1(x0) = 1 − η − ηe−M, q1(x1) = ηe−M, q1(x2) = η

• q2(x0) = 1 − η − ηe−M, q2(x1) = η, q2(x2) = ηe−M

The α-Rényi divergence between q1 and q2 is at least M/2 (by choosing η = e−(α−1)M/2 and M ≥ 2). However, when η is small enough, x1 and x2 will never be observed in finite samples, no matter whether the ground-truth q⋆ is q1 or q2. Thus, any evaluation algorithm will misrank the models with probability approaching 1/2.

Corollary 4.3: fKL is not weakly evaluable.

This follows from the same construction, noting that KL divergence fKL(q, q⋆):= KL(q⋆∥q) is the limit of the α-Rényi divergence as α → 1.

The authors note: "These two divergences share a common pathology that our construction exploits — their value can become unbounded if a model places negligible mass compared to the ground truth on even a single point. Additionally, these metrics are inherently one-sided... these divergences penalize undercoverage of the ground-truth distribution rather than generic mismatch."

Definition 4.4 (Coverage Profile): Given a natural number N ≥ 1, the coverage profile w.r.t. N is defined as f N−Cov(q, q⋆) = P x∼q⋆[q⋆(x)/q(x) ≥ N].

Proposition 4.5: For any N ≥ 2, f N−Cov is not weakly evaluable.

Proof Construction: The proof uses two candidate models q1, q2 and two possible ground truths q3, q4 on a two-point space x0, x1:

• q1(x0) = (1−γ)/N, q1(x1) = 1 − (1−γ)/N

• q2(x0) = 1 − γ/N, q2(x1) = γ/N

• q3(x0) = 1 − γ, q3(x1) = γ

• q4(x0) = 1 − γ − η, q4(x1) = γ + η

Under q3, q2 is much better than q1 in coverage profile, whereas under q4, q1 is better than q2. However, q3 and q4 have total variation distance η, and hence their m-sample laws are indistinguishable when η ≪ 1/m.

The authors note this negative result holds even under the following lower-bound (finite support) assumption on q⋆:

Assumption 4.6: "There exists a γ > 0 such that q⋆(x) ≥ γ for all x ∈ supp(q⋆)."

The authors explain: "At a high level, the coverage profile is not evaluable even under Assumption 4.6 because it is discontinuous around the threshold N. More specifically, it does not penalize models that come arbitrarily close to but remain below the threshold and penalizes models that exceed the threshold equally."

This motivates a margin assumption:

Assumption 4.7: We say (q⋆, q) have an (N, α) margin if q⋆(x)/q(x) − N ≥ α for all x ∈ supp(q⋆).

Theorem 4.8: "Fix N ≥ 2, ε, δ ∈ (0,1), and any two candidate models q1, q2 ∈ M such that (q⋆, q) have an (N, α) margin for some fixed α > 0 for each q ∈ q1, q2. Then, there exists an evaluation algorithm A such that if q⋆ satisfies Assumption 4.6 for some fixed γ > 0, given evaluation data Seval = x1,..., xm of size m ≥ max 3(N+α)2/(α2γ), (4/γ)log(4/(γδ)), (8/ε2)log(2/δ), with xi ∼ q⋆, with probability at least 1 − δ, A(q1, q2, Seval) = q1 =⇒ f N−Cov(q1, q⋆) ≤ f N−Cov(q2, q⋆) + ε and A(q1, q2, Seval) = q2 =⇒ f N−Cov(q2, q⋆) ≤ f N−Cov(q1, q⋆) + ε."

The proof uses the empirical frequency distribution and shows that with high probability, the indicator of whether q⋆(x)/q(x) ≥ N is correctly estimated for all x in the support, using multiplicative Chernoff bounds and union bounds.

The paper analyzes the negative log-likelihood (nll) score: nll(q, Seval) = −(1/m) Σ i=1 m log q(xi), noting that perplexity is simply the exponential of the nll, both scores induce the same ordering over models and are therefore equivalent for the purposes of evaluability.

Definition 5.1 (Restricted KL Divergences): Given a subset E ⊆ X, define the KL divergence restricted to E as KL E(q⋆, q) = E x∼q⋆(·E)[log(q⋆(x)/q(x))].

Definition 5.2: Given β ∈ (0, 1/2), the β-Restricted KL divergence is defined as f β−KL(q, q⋆):= inf E⊆X: q⋆(E)≥1−β KL E(q⋆, q).

Theorem 5.3: fTV is not weakly evaluable by the nll score. Additionally, f β−KL is not weakly evaluable by nll score for any β ∈ (0, 1/2).

The proof for TV distance constructs three distributions on x0, x1, x2 where the nll score systematically misranks models with a constant gap in TV distance to q⋆. The proof for β-restricted KL constructs a scenario where q2 has f β−KL(q2, q⋆) = 0 but nll(q2, Seval) = ∞ whenever a rare point is observed, causing misranking.

The authors explain: "At a high level, both of these metrics are geometrically misaligned from the nll score. In the case of the TV distance, the nll score can be unbounded, while total variation is bounded in [0,1]. Further, the nll score is fundamentally one-sided in the sense that it severely penalizes models for undercounting mass relative to q⋆, whereas TV distance is entirely governed by how much mass is 'moved' by q with respect to q⋆, regardless of the direction."

Theorem 5.4: f β−KL is not strongly evaluable.

The proof constructs a complex scenario with a finite set A of size N, two candidate models q1, q2, and multiple possible ground truths (q0⋆ and qS⋆ for subsets S ⊆ A of size N/2). The construction shows that the ranking of q1 vs q2 flips between different ground truths, but the sample laws of these ground truths are indistinguishable (TV distance < 1/2), creating a contradiction.

Assumption 5.5 (∆-Closeness in Ratio): (q⋆, q) are ∆-close in ratio if there exists fixed ∆ ∈ (0, 1/2) such that (1 − ∆)q⋆(x) ≤ q(x) ≤ (1 + ∆)q⋆(x).

Proposition 5.6: "Fix ε, δ ∈ (0,1) and two candidate models q1, q2 ∈ M such that (q⋆, q) are ∆-close in ratio for some q ∈ q1, q2 and ∆ ∈ (0, 1/2). Then, if ∆ ≤ O(ε2), there exists an evaluation algorithm A such that given evaluation data Seval = x1,..., xm of size m ≥ O((1/ε2)log(1/δ)), with xi ∼ q⋆, with probability at least 1 − δ, A(q1, q2, Seval) = q1 =⇒ fTV(q1, q⋆) ≤ fTV(q2, q⋆) + ε and A(q1, q2, Seval) = q2 =⇒ fTV(q2, q⋆) ≤ fTV(q1, q⋆) + ε."

The proof shows that under the ∆-closeness assumption, the nll score of the good model is close to that of q⋆, and any model far from q⋆ in TV distance is exponentially unlikely to have a good nll score. The proof uses Hoeffding bounds and the relationship between Hellinger distance and TV distance (H2(q⋆, q) ≥ (1/2)TV(q⋆, q)2).

The authors note: Fundamentally, Assumption 5.5 transforms our setting into a semi-realizable one and ensures that one of the models must achieve a bounded nll score close to that of q⋆.

The authors provide a general principle: "The perplexity (nll) score aggregates per-sample penalties of the form −log q(x). The score is highly sensitive to the worst case. A single data point that is assigned extremely small probability by q dominates the score, regardless of the model's behavior on the rest of the distribution. This property of the score is fundamentally misaligned with many distributional metrics, such as TV distance and restricted KL divergence, which are robust to small regions of mass under q⋆."

They conclude: "Overall, our results from this section suggest that the perplexity score is poorly suited as a score function that ranks models by overall distributional similarity... The perplexity score is able to more reliably evaluate these metrics under assumptions about the existence of a 'good' model with respect to the ground-truth, validating its use in practice. However, our results highlight that perplexity cannot be used blindly as an evaluation method without a principled understanding of the underlying candidate models that it is used to rank."

The paper concludes with three open questions:

1. The Relationship Between Estimability and Strong Evaluability: "It is easy to see that when an evaluation metric f is estimable, then it is strongly evaluable... It is unclear whether the converse holds true. That is, does strong evaluability imply estimability, and does such a statement hold in general or for specific classes of evaluation metrics?"

2. Strict Dichotomy of Evaluability for Real-Valued IPMs: "In Proposition 3.4, we establish a weak dichotomy for IPMs with real-valued, bounded test classes... We prove that even if the γ-fat-shattering dimension of the test class is unbounded for some γ, the corresponding IPM is still 3-weakly evaluable. However, we were not able to prove that the factor of 3 is optimal, which would mirror our result in the case where the test class is binary-valued."

3. Evaluability of β-Restricted KL Divergence: "In discussing the limitations of perplexity as an evaluation method, we introduced the β-restricted KL divergence and showed that the nll score cannot evaluate this metric and may not be able to under any reasonable conditions. However, this metric is a robust alternative to the standard KL divergence. Any general evaluability guarantees for the β-restricted KL beyond the nll score are left as an open question."

Evaluation Metric Evaluability Guarantee

IPM w.r.t. binary-valued F Estimable ⇒ strongly evaluable if VC(F) < ∞; 3-weakly evaluable if VC(F) = ∞ (Theorem 3.2)

IPM w.r.t. real-valued F Estimable ⇒ strongly evaluable if Pdimγ(F) < ∞ for all γ ∈ (0, 1/2]; 3-weakly evaluable if Pdimγ(F) is unbounded for some γ (Proposition 3.4)

Fixed Statistical Test Metrics w.r.t test function g Estimable ⇒ strongly evaluable when g is bounded; Not weakly evaluable when g is sufficiently unbounded (Theorem 3.8)

α-Rényi divergence (α > 1) Not weakly evaluable (Theorem 4.2)

Coverage Profile Not weakly evaluable (Proposition 4.5); Strongly evaluable under additional conditions (Theorem 4.8)

Total Variation Distance Not weakly evaluable by perplexity score (Theorem 5.3); Strongly evaluable under additional conditions (Proposition 5.6)

β-Restricted KL Divergence Not weakly evaluable by perplexity score (Theorem 5.3); Not strongly evaluable (Theorem 5.4)

Based on the paper, here are specific improvements that can be made to AI systems, particularly for evaluating generative models:

Current limitation: Perplexity (nll score) is unreliable for ranking models by distributional similarity, as shown in Theorem 5.3.

Improvement: Implement an evaluation system that uses IPMs with bounded test classes (e.g., bounded real-valued functions) instead of perplexity. This provides:

• Strong evaluability when the test class has finite fat-shattering dimension (Proposition 3.4)

• 3-weak evaluability even for complex test classes (Theorem 3.2)

Specific implementation: For language models, define a test class F of bounded functions (e.g., sentence-length functions, topic-classification scores, or bounded sentiment scores). Compute dF(q*, q) empirically using the uniform convergence bounds from Proposition 3.4. This gives guaranteed approximation with sample complexity O((1/ε2)(d log(1/ε2) + log(1/δ))) where d = Pdim ε/24(F).

Specific output: For each model pair, report both the estimated metric value and the confidence interval, clearly stating whether the evaluation is strong or weak.

Practical implementation: Before ranking models by perplexity, compute the empirical likelihood ratios on a validation set. If the ratios are bounded within [1-∆, 1+∆] for some model, proceed with perplexity; otherwise, fall back to IPM-based evaluation.

Specific rule: For a candidate model q and test set S, if max x∈S(-log q(x)) > 10·(median of-log q(x)), flag the evaluation as potentially unreliable.

This prevents under-sampling that leads to unreliable evaluations.

Statistical evaluation aims to estimate the generalization performance of a model using held-out i.i.d. test data sampled from the ground-truth distribution. In supervised learning settings such as classification, performance metrics such as error rate are well-defined, and test error reliably approximates population error given sufficiently large datasets. In contrast, evaluation is more challenging for generative models due to their open-ended nature: it is unclear which metrics are appropriate and whether such metrics can be reliably evaluated from finite samples. In this work, we introduce a theoretical framework for evaluating generative models and establish evaluability results for commonly used metrics. We study two categories of metrics: test-based metrics, including integral probability metrics (IPMs), and R'enyi divergences. We show that IPMs with respect to any bounded test class can be evaluated from finite samples up to multiplicative and additive approximation errors. Moreover, when the test class has finite fat-shattering dimension, IPMs can be evaluated with arbitrary precision. In contrast, R'enyi and KL divergences are not evaluable from finite samples, as their values can be critically determined by rare events. We also analyze the potential and limitations of perplexity as an evaluation method.