TL;DR
As large foundation models are increasingly trained on "the whole internet," the classical assumption of a pristine, held-out test set is dying. This paper introduces a formal theory of Evaluability, proving that while black-box evaluation is impossible for most data distributions under contamination, it remains feasible for "amenable" distributions (like those following power laws) or when evaluators are granted query access to the model.
What Problem Does This Paper Address?
In traditional machine learning, we evaluate a model by checking its performance on a "held-out" test set—data it has never seen during training. This ensures the model has actually learned to generalize rather than just memorizing answers.
However, for modern Large Language Models (LLMs), this "clean" separation is vanishing. Because these models are trained on massive crawls of the web, public benchmarks (and even "hidden" ones) often leak into the training data. This is known as data contamination. If a model has seen the test set, its 99% accuracy might be a result of memorization, not intelligence. The author, Kunal Talwar, asks a fundamental question: Is it mathematically possible to accurately evaluate a model’s properties (like safety, fairness, or accuracy) if we suspect the model was trained on our test samples?
Methods
The paper formalizes the concept of Evaluability through a game between a "Learner" (who builds the model) and an "Evaluator" (who tries to estimate its performance).
- Black-Box Setting: The evaluator only sees the model's output on a specific set of samples. The paper introduces the concept of Amenability—a property where a distribution is largely concentrated on a small number of points (like a Zipfian or power-law distribution).
- Query-Access Setting: The evaluator is "empowered" to query the model on new, unlabeled points.
- Self-Correctors: To handle non-amenable distributions, the author borrows a technique from program testing called "self-correction." This allows an evaluator to compute what a model should have predicted by querying it on related points, effectively bypassing the model's potential "cheating" or memorization on specific contaminated points.
Datasets
As a theoretical paper, it does not introduce a new benchmark dataset or train a specific model. Instead, it uses statistical analysis of existing data to justify its definitions:
- Reddit Dataset: Used to demonstrate amenability; 1,000 words account for 75% of word occurrences, and 100,000 words cover 99%.
- ChatGPT Prompts: References studies showing that over 30% of real-world prompts fall into just 66 "tasks," suggesting real-world usage distributions are highly amenable.
Key Insights and Ideas
- Amenability is the "Whole Game": For black-box evaluation, the paper proves that accurate evaluation is possible if and only if the underlying distribution is amenable. If the data is "heavy-tailed" or concentrated on a few common cases, you can still get a good estimate of performance even if the model memorized those cases.
- The Impossibility of General Evaluation: If a distribution is not amenable (e.g., a uniform distribution over a massive space), a "cheating" model can easily fool an evaluator by memorizing the test set while performing poorly on everything else.
- The Power of Unlabeled Queries: One of the most "aha" moments is that you don't necessarily need more labeled data to fix evaluation. If you have fresh unlabeled samples and the model belongs to a certain class (like linear functions or "juntas"), you can use self-correctors to verify the model's behavior.
- Evaluation vs. Benchmarking: The paper distinguishes between the two. Benchmarks are good for comparing models (relative performance), but "Evaluability" is concerned with absolute performance on a specific distribution.
Key Results
- Sample Complexity Bounds: The paper provides tight upper and lower bounds on how many samples ($n$) are needed to evaluate a model to a certain accuracy ($\alpha$). For amenable distributions, the complexity depends on the "amenability parameters" of the distribution.
- Strong vs. Weak Evaluability: The author defines "Strong Evaluability" as an estimate that remains a valid upper bound on error even if the data distribution assumptions are totally wrong.
- The Self-Correction Boost: The paper proves that for specific concept classes (like parity functions), an evaluator can achieve accurate results with $O(d/\alpha^2)$ samples, even when the model is potentially adversarial.
Limitations and Future Work
- Adversarial Learners: The negative results (impossibility proofs) rely on a very "adversarial" learner who is specifically trying to trick the evaluator. Real-world models might not be intentionally deceptive in this way.
- Restricted Function Classes: The positive results for query-access evaluation currently apply to specific mathematical classes (linear functions, polynomials, juntas). Extending this to the complex, non-linear world of neural networks is a major open challenge.
- Distribution Shift: The theory assumes a fixed distribution. It does not yet account for "distribution shift," where the model is evaluated on data that looks different from what the evaluator originally sampled.
- Interactive Evaluation: The author suggests that future work could involve "interactive protocols" where the model must provide a proof of its own correctness (e.g., using a language like LEAN).
Summary updated