🤖 machine learning

A Theoretical Framework for Statistical Evaluability of Generative Models

This paper introduces a theoretical framework demonstrating that while integral probability metrics (IPMs) for generative models can be reliably evaluated from finite samples under certain conditions, Rényi and KL divergences are fundamentally un-evaluable due to their sensitivity to rare events.

Original authors: Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao

Published 2026-04-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef who just invented a new recipe for a perfect chocolate cake. You want to know if your cake is actually good. How do you test it?

In the world of Supervised Learning (like teaching a computer to recognize cats in photos), the test is easy. You show the computer 1,000 photos of cats and dogs. If it gets 950 right, you know it's 95% accurate. The "score" is clear, and a small test group tells you everything you need to know about the future.

But in Generative AI (like the computer writing a story or painting a picture), the test is a nightmare. There is no single "right" answer. If the AI writes a poem, how do you know if it's "good"? Is it funny? Is it deep? Is it grammatically correct? And if you only show the AI 1,000 poems to test it, can you really trust that it will write good poems forever?

This paper, "A Theoretical Framework for Statistical Evaluability of Generative Models," asks a fundamental question: Can we ever truly measure how good a generative AI is using just a finite number of test samples?

The authors say: It depends entirely on how you measure it.

Here is the breakdown using simple analogies:

1. The "Test Class" vs. The "Rare Event" Problem

The paper divides evaluation methods into two camps: those that use Tests and those that look at Probability Distributions.

The "Test Class" Approach (The Jury)

Imagine you want to judge a new car. You don't try to calculate the exact physics of every molecule in the engine. Instead, you give it a series of tests:

"Can it stop in 50 feet?"
"Does it fit in a parking spot?"
"Is the radio loud enough?"

If you have a finite list of tests (a "test class"), you can reliably judge the car. Even if the car is weird, as long as you have enough data to run these specific tests, you can say, "This car passes 9 out of 10 tests, so it's good."

The Paper's Finding: If your tests are simple and limited (like checking if code compiles or if an email is too long), you can reliably evaluate the AI. The more complex your list of tests gets, the harder it is, but if the list isn't infinitely complex, you can still get a decent score.

The "Probability Distribution" Approach (The Crystal Ball)

Now, imagine instead of running tests, you try to predict the car's performance by calculating the exact probability of every possible mechanical failure, including the one-in-a-billion chance that a meteorite hits the engine while driving.

The Problem: Generative models often fail on "rare events." If an AI writes a story, it might be 99.9% perfect, but if it accidentally writes one word that is extremely unlikely (a "rare event"), some metrics scream "FAIL!"
The Paper's Finding: Metrics that try to measure the "distance" between the AI's output and reality (like Rényi Divergence or KL Divergence) are impossible to evaluate with finite data. Why? Because a single, incredibly rare event (like a meteorite hitting the engine) can ruin the score, but you will never see that event happen in your test data. You are trying to measure a ghost that only appears once in a million years.

2. The Trap of "Perplexity" (The Perfectionist Judge)

You might have heard of Perplexity. It's the most common way to judge AI language models. Think of Perplexity as a hyper-critical judge who gives you a score based on how surprised they are by your words.

If you say something common, the judge is bored (low score).
If you say something rare, the judge is shocked. If you say something extremely rare, the judge freaks out and gives you a terrible score.

The paper argues that Perplexity is a bad judge for most things because it is obsessed with the "worst-case scenario."

The Analogy: Imagine a restaurant reviewer who says, "This meal was 99% perfect, but you used a slightly weird brand of salt once. Therefore, the meal is a disaster."
The Reality: A good AI might make a tiny, rare mistake that Perplexity hates, but the mistake doesn't actually matter to the user. Conversely, Perplexity might love a model that is boring but safe, while hating a creative model that takes risks.
The Verdict: Perplexity cannot reliably tell you if an AI is "close" to human reality (Total Variation Distance) unless you make very strict, unrealistic assumptions that the AI will never make a weird mistake.

3. The "Coverage Profile" (The Safety Net)

Some people tried to fix the "rare event" problem by saying, "Let's ignore the rare stuff! Let's only look at the common stuff." This is called the Coverage Profile.

The Paper's Finding: This is like saying, "We will only judge the car if it drives on a sunny day." If the car is actually terrible in the rain, this test won't catch it. The paper shows that even this "safety net" is mathematically impossible to evaluate perfectly because the line between "common" and "rare" is blurry. You can't draw a perfect line in the sand without missing something important.

The Big Takeaway

The authors built a theoretical framework to answer: "Can we trust our test scores?"

Yes, if you use simple, bounded tests. If you ask the AI specific questions (Is this code correct? Is this image realistic?), you can get a reliable score, provided your list of questions isn't infinitely complex.
No, if you try to measure "perfect similarity." If you try to measure how close the AI is to reality using complex math that cares about every single rare possibility (like Rényi divergence), you are chasing a ghost. No amount of test data will ever be enough to catch the rare events that break the score.
Be careful with Perplexity. It's a popular tool, but it's a "perfectionist" that often misjudges models because it panics over tiny, rare mistakes that don't actually matter.

In short: We can't measure a generative AI's soul with a ruler. We have to be smart about what we measure. If we measure the right things (simple tests), we can trust the results. If we try to measure everything (including the impossible rare events), our ruler will break.

1. Problem Statement

The paper addresses a fundamental gap in the evaluation of generative models. While supervised learning relies on well-defined metrics (e.g., error rate) that can be reliably estimated from finite test data via uniform convergence, generative model evaluation lacks a rigorous theoretical foundation.

The Core Question: Can the performance of a generative model be statistically evaluated (i.e., reliably ranked or estimated) using finite samples drawn from a ground-truth distribution?
The Challenge: Unlike classification, generative metrics are often ill-specified or sensitive to "rare events." For instance, standard metrics like Perplexity (based on cross-entropy) can be dominated by rare events with extremely low probability, causing standard concentration inequalities to fail. Similarly, metrics like Total Variation (TV) distance or Rényi divergences may be impossible to estimate if the domain is large or if the metric depends on tail events not observed in finite samples.

2. Methodology and Framework

The authors introduce a formal theoretical framework to define and analyze Evaluability.

2.1 Definitions

Evaluation Metric ( $f$ ): A function mapping a pair of distributions (model $q$ , ground truth $q^*$ ) to a non-negative score.
Score Function ( $s$ ): A function that computes a score based on a model and a finite set of empirical data $S_{eval}$ .
Evaluability: A metric $f$ $f$ is $c$ -weakly evaluable if there exists a score function $s$ $s$ such that, with high probability, the ordering of models by $s$ $s$ approximates the ordering by $f$ $f$ within a multiplicative factor $c$ $c$ and an additive error $\epsilon$ $ϵ$ .
- Strong Evaluability: $c=1$ (arbitrary precision).
- Weak Evaluability: $c > 1$ (approximate ranking).
- Not Weakly Evaluable: No finite sample size allows for reliable ranking, regardless of $c$ .
Estimability: A stronger condition where the score function $s$ approximates the true metric value $f(q, q^*)$ directly within $\epsilon$ . Estimability implies strong evaluability.

2.2 Categories of Metrics Studied

The paper analyzes two main categories:

Test-Based Metrics: Metrics defined by a class of test functions $\mathcal{F}$ (e.g., Integral Probability Metrics - IPMs).
Divergence-Based Metrics: Metrics comparing distributions pointwise (e.g., Rényi Divergences, KL Divergence, Coverage Profile).

3. Key Contributions and Results

A. Integral Probability Metrics (IPMs)

IPMs measure the maximum discrepancy between two distributions over a class of test functions $\mathcal{F}$ : $d_{\mathcal{F}}(q^*, q) = \sup_{\phi \in \mathcal{F}} |E_{q^*}[\phi] - E_q[\phi]|$ .

Binary-Valued Tests:
- Strict Dichotomy: There is a sharp transition based on the VC Dimension of $\mathcal{F}$ $F$ .
  - If $\text{VCdim}(\mathcal{F}) < \infty$ : The IPM is strongly evaluable (estimable) with sample complexity $O(\text{VCdim}/\epsilon^2)$ .
  - If $\text{VCdim}(\mathcal{F}) = \infty$ : The IPM is not strongly evaluable, but it is 3-weakly evaluable. No factor $c' < 3$ is achievable.
- Significance: This extends previous results on Total Variation distance, showing that even if exact estimation is impossible, a coarse ranking (factor of 3) is always possible for binary tests.
Real-Valued (Bounded) Tests:
- The complexity is governed by the $\gamma$ -fat-shattering dimension.
- If the dimension is finite for all $\gamma > 0$ , the IPM is strongly evaluable.
- If the dimension is unbounded for some $\gamma$ , the IPM is 3-weakly evaluable.
- Sample Complexity Taxonomy: The authors prove that unlike supervised learning (where sample complexity is governed by a single parameter like VC dimension), estimable IPMs do not admit a finite taxonomy of sample complexity rates. There is no single parameter that captures the sample complexity for all estimable IPMs.

B. Divergence-Based Metrics (Rényi and KL)

The paper investigates metrics that compare distributions directly via likelihood ratios.

$\alpha$ -Rényi Divergences ( $\alpha > 1$ ) and KL Divergence:
- Result: These are not weakly evaluable from finite samples.
- Reasoning: Their values can be critically determined by "rare events" (points where $q^*(x) > 0$ but $q(x) \approx 0$ ). Since these events may never appear in a finite sample, the metric value is undetectable. Even if the ground truth has a minimum probability mass (Assumption 4.6), the unbounded nature of the likelihood ratio prevents reliable estimation.
Coverage Profile:
- A truncated version of Rényi divergence designed to ignore extreme outliers.
- Result: Generally not weakly evaluable due to discontinuity at the truncation threshold.
- Positive Result: It becomes strongly evaluable only under a strict "margin assumption" where the likelihood ratio $q^*(x)/q(x)$ is guaranteed to be far from the threshold $N$ .

C. Analysis of Perplexity (Negative Log-Likelihood)

Perplexity is the standard metric for language models, derived from the Negative Log-Likelihood (NLL) score.

Limitations:
- Perplexity/NLL is not weakly evaluable for Total Variation (TV) distance or $\beta$ -Restricted KL divergence.
- Geometric Misalignment: NLL is one-sided and unbounded (severely penalizing under-coverage of rare events), whereas TV is symmetric and bounded. NLL is hypersensitive to single data points, while TV and Restricted KL are robust to small mass shifts.
Conditions for Success:
- Perplexity can evaluate TV distance only under a $\Delta$ -Closeness Assumption (the model $q$ must be close to $q^*$ in ratio, i.e., $(1-\Delta)q^*(x) \le q(x) \le (1+\Delta)q^*(x)$ ). This essentially forces the setting into a "semi-realizable" regime where rare events are not extreme.
- No reasonable assumption exists that allows NLL to evaluate $\beta$ -Restricted KL, as the metric's definition (ignoring $\beta$ mass) conflicts with NLL's sensitivity to the worst-case point.

4. Significance and Implications

Theoretical Limits of Evaluation: The paper establishes that many popular metrics (Rényi, KL, Coverage Profile) are fundamentally un-evaluable from finite samples because they rely on tail events that are statistically invisible. This explains why high perplexity scores often fail to correlate with downstream task performance.
Role of Test Classes: For test-based metrics (IPMs), the paper provides a complete characterization: evaluability is strictly tied to the statistical complexity (VC/fat-shattering dimension) of the test class.
Guidance for Practitioners:
- Avoid Blind Perplexity: Using perplexity to rank models is risky unless one can guarantee the models are "close" to the ground truth in a ratio sense.
- Metric Selection: If one needs to evaluate distributional similarity, one should choose metrics that are robust to rare events (like TV distance) and pair them with test classes of finite complexity, rather than relying on likelihood-based scores.
- Alignment Principle: A score function must be geometrically aligned with the evaluation metric. Metrics that tolerate rare errors cannot be evaluated by scores that amplify them.

5. Open Questions

The authors leave several questions for future work:

Does strong evaluability imply estimability?
Is the factor-3 approximation for real-valued IPMs with unbounded fat-shattering dimension optimal?
Are there any score functions (other than NLL) that can evaluate $\beta$ -Restricted KL divergence?

In summary, this work provides the first rigorous theoretical framework distinguishing between metrics that can be reliably evaluated from data and those that cannot, highlighting the critical role of statistical complexity and the dangers of relying on unbounded likelihood-based scores.