A test set may already be in the training data: accurate evaluation is possible only when the distribution concentrates on few points
Synopsis
Large-model training corpora often cover public benchmarks, so evaluators can no longer assume a fresh test set. This work formalizes evaluability without assuming the test set was held out and without constraining the model or its training algorithm, showing that accurate evaluation from model outputs on the test set alone is feasible if and only if the distribution is close to small support, with sample-complexity bounds tight up to logarithmic factors; allowing extra queries to the model, via self-correctors from program testing, widens the evaluable distributions.
Interpretation
Whether evaluation is possible reduces to a property of the data distribution: whether it concentrates most of its probability mass on a few points. Evaluation has relied on a fresh test set not seen during training, assumed to be i.i.d. draws from the target distribution; when training corpora cover the internet, that freshness assumption becomes hard to justify. When the evaluator only sees model outputs on the test set, accurate evaluation is feasible if and only if the distribution is close to small support, and the sample count needed is determined quantitatively by the distribution's concentration parameters and the target error, tight up to logarithmic factors in the worst case.
The evaluator needs no knowledge of how the model was trained: it writes the target metric as an expectation of per-example scores, estimates scores on points seen in the sample, and uses a pessimistic default for unseen points. This treats accuracy, squared loss, log loss, inaccuracy allowing abstentions, per-group accuracy and hallucination rate as one class of estimable quantities. For distribution classes with a given concentration sequence, the algorithm estimates the score to a given error with a corresponding number of samples and controlled failure probability; the sample count drops further when the concept class is deterministic, the score is linear in the prediction, or the score vector is sparse.
If the distribution does not concentrate, test-set outputs alone cannot support reliable evaluation, but letting the evaluator query the model additionally can partly compensate. Extra queries previously appeared in program testing as self-correctors, which recover a value close to the target function using few queries. On concrete function classes such as parities and juntas with matching distribution classes, an evaluator given a few labeled samples and fresh unlabeled samples produces estimates with far fewer samples than the standard requirement.
Perspective
The results cover metrics expressible as expectations of per-example scores, under several access settings: only test-set outputs, additional model queries, and fresh unlabeled samples; the analysis assumes a fixed distribution and does not address distribution shift.
The main negative result relies on a deliberately adversarial learner, and the authors raise the question of which verifiable restrictions on the learner could be imposed; the evaluation algorithms need no cooperation from the model, and the power of evaluators when models are designed to be easier to evaluate or take part in evaluation remains open; the interpretation of a metric is also outside the framework.