Confidence Intervals for Accuracy on Small Evaluation Sets

A benchmark score is a fraction: some number of items correct out of some number attempted. The fraction is an estimate of a rate, and like any estimate made from a finite sample it has an uncertainty attached. Reporting 71.5 percent without that uncertainty invites the reading that the underlying rate is 0.715, which it is not; the underlying rate is somewhere in an interval, and the interval’s width is set by the number of items.

The arithmetic is standard and the formulas are short. The reason it goes wrong in practice is that the binomial model assumes items are independent draws from one population, and evaluation sets are not built that way. Items cluster by topic, by annotator, by template, and by difficulty, and clustering widens the interval beyond what the binomial formula reports.

Three intervals and which one to use

For $k$ correct out of $n$ items, the textbook interval is the normal approximation: $\hat{p} \pm z\sqrt{\hat{p}(1-\hat{p})/n}$, with $z$ about 1.96 for a 95 percent interval. It fails at the extremes, where $\hat{p}$ is near 0 or 1 and the interval extends outside the unit range, and it fails at small $n$, where the normal approximation to the binomial is poor. A score of 0 out of 20 produces an interval of zero width under this formula, which is obviously wrong.

The Wilson score interval inverts the normal approximation in a way that stays inside the unit range and behaves sensibly at the extremes. Its center is not $\hat{p}$ but a point pulled toward one half, and its width at $\hat{p} = 0$ is not zero. For 0 out of 20, the 95 percent Wilson interval runs from 0 to roughly 0.16, which is the honest statement: the data are consistent with a rate as high as one in six.

The exact Clopper-Pearson interval uses the binomial tail directly and is conservative, meaning its actual coverage is at least the nominal level. It is wider than Wilson and is the appropriate choice when a claim of the form “the error rate is below $x$” has to hold, since the conservative direction is the safe one there.

import math

def wilson_interval(k, n, z=1.96):
    if n == 0:
        return 0.0, 1.0
    p = k / n
    denom = 1 + z * z / n
    centre = (p + z * z / (2 * n)) / denom
    half = z * math.sqrt(p * (1 - p) / n + z * z / (4 * n * n)) / denom
    return max(0.0, centre - half), min(1.0, centre + half)

def normal_interval(k, n, z=1.96):
    p = k / n
    half = z * math.sqrt(p * (1 - p) / n)
    return p - half, p + half

The width scales as $1/\sqrt{n}$. Quadrupling the item count halves the interval. To narrow a 95 percent interval around a rate near 0.7 from roughly $\pm 4.5$ points to $\pm 2$ points takes about five times the items, from around four hundred to around two thousand. This is the arithmetic that makes small benchmark differences uninformative: two systems differing by two points on a five-hundred-item set are inside each other’s intervals, and the difference is not evidence of anything.

Paired items, not independent samples

The two-interval comparison above is the wrong test when the same items are used to score both systems. Overlapping intervals are a weak signal even for independent samples, and for paired data the correct analysis looks at the per-item difference, which is much less noisy than the two separate scores.

The natural test is McNemar’s, which counts the items where the systems disagree. Let $b$ be the number of items only system A gets right and $c$ the number only system B gets right. Items both get right or both get wrong carry no information about the difference. Under the null hypothesis of equal rates, $b$ and $c$ are draws from a binomial with probability one half over $b + c$ trials, so the test reduces to whether $b$ is far from $(b+c)/2$. With $b = 40$ and $c = 25$, the difference of 15 out of 65 is not significant at the 5 percent level by the exact binomial test, which is a stronger statement than the raw accuracy gap suggests.

The paired structure is why a small evaluation set can still detect a real improvement. If two systems agree on 90 percent of items and differ on the remaining 10 percent, only that 10 percent carries signal, but the signal is a difference of proportions over the disagreements, and if one system wins most of them the evidence is concentrated. Conversely, two systems with a large accuracy gap on unpaired items can show no paired evidence if the gap comes from items where both fail differently.

Clustering breaks the independence assumption

Evaluation items are rarely independent draws. Many benchmarks contain several questions about the same passage, several examples of the same task template, or several annotators’ judgments of the same output. Items within a cluster share difficulty and share whatever the model’s behaviour on that cluster is. Positive correlation within clusters means the effective sample size is smaller than the item count, and the binomial interval is too narrow.

The correction is a clustered or design-effect adjustment: compute the variance of the per-cluster means, then scale the standard error by the ratio of the cluster-level variance to what independent sampling would predict. When clusters are of equal size $m$, the design effect is approximately $1 + (m-1)\rho$, where $\rho$ is the intra-cluster correlation. Even a modest $\rho$ of 0.2 with clusters of 8 items inflates the variance by a factor of 2.4, which widens the interval by more than half.

A bootstrap over clusters handles the same problem without requiring a parametric model. Resample clusters with replacement, recompute the score on each resample, and take percentiles of the resulting distribution. The resampling unit has to be the cluster, not the item, or the procedure reproduces the independence assumption it was meant to relax. This is the standard bootstrap prescription: resample at the level at which the data were generated, which for a benchmark built from documents means resampling documents.

import random

def cluster_bootstrap(clusters, iterations=2000, seed=0):
    """clusters: list of lists of 0/1 item outcomes, one list per document."""
    rng = random.Random(seed)
    scores = []
    for _ in range(iterations):
        sample = [rng.choice(clusters) for _ in clusters]
        total = sum(sum(c) for c in sample)
        count = sum(len(c) for c in sample)
        scores.append(total / count)
    scores.sort()
    lo = scores[int(0.025 * iterations)]
    hi = scores[int(0.975 * iterations) - 1]
    return lo, hi

Multiplicity and the search for a win

The other way small evaluation sets mislead is by being queried repeatedly. A comparison run over many prompt variants, many decoding settings, or many subsets of the test data will produce some differences that look large by chance. With a 5 percent significance threshold and twenty independent comparisons, one false positive is expected even when no system differs from another. The standard corrections, Bonferroni’s division of the threshold by the number of comparisons or the Benjamini-Hochberg procedure for controlling the false discovery rate, apply directly, and the honest alternative is to pre-register the comparison and report only that one.

Subgroup analysis carries the same hazard with an extra twist. Splitting a set into categories and reporting the best-performing category selects the maximum over noisy estimates, and the maximum of several noisy estimates is biased upward. A subgroup that shows a large gain after the split may show none on fresh data. The fix is either a held-out split for the subgroup claim or a shrinkage estimate that pulls small subgroups toward the overall rate.

Reporting practice that survives scrutiny

Three numbers make a score auditable: the point estimate, the interval, and the item count with the clustering unit. A fourth helps for comparisons: the paired disagreement counts, since they carry the actual evidence about a difference.

It is worth stating explicitly what the interval does not cover. It does not cover annotation error, since the gold labels are treated as ground truth; the ceiling imposed by annotator disagreement is a separate quantity and is the subject of inter-annotator agreement. It does not cover variation from sampling prompts, if the prompt set is itself a sample from a larger space, which is a second clustering level. And it does not cover the selection of the evaluation set itself, which is the problem of contamination when the set was drawn from a distribution the model has already seen. An interval on a biased estimate is a precise statement about the wrong number, and the precision makes it more convincing, not less.

The same caution applies to intervals built over sampling randomness rather than items. A system that samples multiple completions per prompt and reports the best one has an evaluation whose variance comes from two sources: which items were drawn and which completions were sampled. The second source shrinks as the sample count grows and the first does not, so an interval that only accounts for sampling variance understates the uncertainty that remains. Reporting the number of samples per prompt alongside the item count is what lets a reader separate them, and the estimator used for the best-of-$k$ score needs its own correction, described under the pass@k estimator, before the two sources can be combined.