Statistical Significance With Non-Deterministic Models

Two systems, four hundred eval items, pass rates of 70.0% and 74.3%. Real or noise? The answer depends entirely on a fact most eval harnesses throw away — that both systems saw the same items — and using it changes the p-value in this example from 0.18 to 0.017.

Pair everything, always

Eval items differ enormously in difficulty. Some are trivial and every model passes; some are impossible and none do. That variation is the dominant source of spread in any eval score, and it is entirely shared between the two systems you are comparing — which means it can be cancelled out, but only if you keep track of which item is which.

An unpaired analysis treats your two runs as two independent samples and pays for item difficulty twice. Take the numbers above: 400 items, baseline passes 280, candidate passes 297.

Unpaired two-proportion z-test
  p1 = 280/400 = 0.7000      p2 = 297/400 = 0.7425
  pooled p = 0.72125
  se = sqrt(2 * 0.72125 * 0.27875 / 400) = 0.03171
  z  = 0.0425 / 0.03171 = 1.34        ->  p = 0.18   "no evidence"

The same data, paired
  both pass          a = 266
  candidate only     b =  31     <- candidate fixed 31 items
  baseline only      c =  14     <- candidate broke 14 items
  both fail          d =  89
                          400

The 266 items both systems pass and the 89 both fail carry no information about which is better. All the evidence lives in the 45 discordant pairs, and the question reduces to a coin-flip test: if the two systems were equivalent, a discordant pair would fall either way with probability one half. Getting 31 out of 45 is a big deviation from that. Getting 297 out of 400 versus 280 out of 400 does not look like much. Same data.

McNemar’s test, worked

McNemar’s test is exactly that coin-flip test on the discordant pairs. With continuity correction:

chi2 = (|b - c| - 1)^2 / (b + c)
     = (|31 - 14| - 1)^2 / 45
     = 16^2 / 45
     = 5.69     on 1 degree of freedom   ->  p ~ 0.017

Exact version (preferred when b + c < 25):
  p = 2 * P(X >= 31)  where  X ~ Binomial(45, 0.5)   ->  p ~ 0.017

Below roughly 25 discordant pairs, use the exact binomial form rather than the chi-squared approximation; above it the two agree closely. Either way the implementation is a dozen lines and needs no library:

from math import comb

def mcnemar_exact(b, c):
    """Two-sided exact p-value. b = candidate-only wins, c = baseline-only."""
    n = b + c
    if n == 0:
        return 1.0
    k = max(b, c)
    tail = sum(comb(n, i) for i in range(k, n + 1)) / 2 ** n
    return min(1.0, 2 * tail)

print(round(mcnemar_exact(31, 14), 4))   # 0.0171

Two things this makes obvious that a pass-rate comparison hides. First, c — the count of items the candidate broke — is a number you should always look at directly, whatever the p-value says. Fourteen previously-working items now failing may be unacceptable even inside a net improvement, and the aggregate score cannot express that. Second, a change that fixes 31 and breaks 31 is a net zero on the score while having rewritten the behaviour of 62 items. That is not a no-op, and only the paired table shows it.

How many items do you need?

This is the calculation that should happen before the eval set is built, and almost never does. You need two guesses, both of which a 40-item pilot run will give you: the proportion of items the candidate is expected to fix (pi_b) and the proportion it is expected to break (pi_c).

The test is a binomial proportion test on the discordant pairs against 0.5, so the required number of discordant pairs is:

p          = pi_b / (pi_b + pi_c)          the discordance split
n_disc     = ( z_a/2 * 0.5 + z_b * sqrt(p(1-p)) )^2 / (p - 0.5)^2
N_items    = n_disc / (pi_b + pi_c)

Scenario A -- a real improvement you would ship
  pi_b = 0.08, pi_c = 0.03    pi_d = 0.11    p = 0.08/0.11 = 0.7273
  alpha = 0.05 two-sided -> z = 1.960 ;  power 0.80 -> z = 0.8416

  numerator   = (1.960 * 0.5 + 0.8416 * sqrt(0.7273 * 0.2727))^2
              = (0.9800 + 0.8416 * 0.4454)^2
              = (0.9800 + 0.3748)^2  =  1.3548^2  =  1.8355
  denominator = (0.7273 - 0.5)^2 = 0.2273^2 = 0.05165

  n_disc  = 1.8355 / 0.05165 = 35.5   ->  36 discordant pairs
  N_items = 36 / 0.11        = 327.3  ->  328 items

Scenario B -- a marginal change
  pi_b = 0.05, pi_c = 0.04    pi_d = 0.09    p = 0.5556

  numerator   = (0.9800 + 0.8416 * 0.4969)^2 = 1.3982^2 = 1.9549
  denominator = 0.05556^2 = 0.003086

  n_disc  = 1.9549 / 0.003086 = 633.4  ->  634 discordant pairs
  N_items = 634 / 0.09                 =  7,044 items

Read those two results together, because the pair of them is the whole lesson. A change that fixes 8% and breaks 3% — a large, obvious, worth-shipping improvement — needs about 330 items to establish at conventional levels. A change that fixes 5% and breaks 4% needs something on the order of seven thousand. There is no eval set you are going to build that can resolve the second case, which means the correct response to a marginal candidate is not a bigger eval; it is to decide on cost, latency or maintainability instead and stop pretending the quality question is answerable.

It also reframes the fifty-item set. Fifty items with pi_d = 0.11 yields about five discordant pairs. Five coin flips cannot reach significance at any split. A fifty-item eval is a debugging instrument and a large-regression tripwire, and treating its three-point movements as findings is the most common statistical error in this field.

More items or more samples per item?

With a stochastic system you can spend your call budget on more eval items or on more samples per item. The answer follows from a variance decomposition. Let each item i have a true pass probability p_i, and score it with the mean of k samples. Then the variance of that per-item estimate has two parts:

Var(item score) = sigma_between^2 + E[p(1-p)] / k
       between-item spread ---^          ^--- sampling noise, shrinks with k

Var(overall mean over n items) = ( sigma_between^2 + E[p(1-p)]/k ) / n

Suppose a pilot gives sigma_between^2 = 0.060 and E[p(1-p)] = 0.150:

  k = 1   per-item var 0.210    n=200 -> SE 0.0324
  k = 3               0.110     n=200 -> SE 0.0235
  k = 5               0.090     n=200 -> SE 0.0212
  k = 10              0.075     n=200 -> SE 0.0194
  k = inf             0.060     n=200 -> SE 0.0173   <- the floor

Now hold the CALL BUDGET fixed at 1000 calls:
  n = 200, k = 5   ->  SE = sqrt(0.090 / 200)  = 0.0212
  n = 1000, k = 1  ->  SE = sqrt(0.210 / 1000) = 0.0145   <- better

The general result: substituting n = B/k into the variance gives (sigma_between^2 · k + E[p(1-p)]) / B, which is increasing in k. For estimating an overall mean under a fixed budget, k = 1 on more items always wins. Between-item variance never averages away no matter how many times you resample the same item, so repeats buy you a shrinking share of the total.

That is not an argument for k = 1 everywhere, because some questions are not about the mean:

• Per-item reliability. “Does this item pass consistently?” is only answerable with repeats, and it is the right question for contract assertions, where an intermittent violation matters as much as a constant one.
• Metrics defined over repeats. pass@k, majority-vote accuracy and consistency rates are functions of the sampling distribution. There is no single-sample version of them.
• Small fixed eval sets. When you cannot get more items — the whole set is 120 hand-curated cases — repeats are the only lever you have, and the ceiling in the table above tells you where they stop helping. Past k = 5 or so you are buying very little.

A sensible default: k = 1 for the broad quality estimate, k = 3 or 5 for contract checks and for the subset of items you know are borderline.

Report intervals, not points

Every score in an eval report should carry an interval, and the cheapest correct one is a bootstrap over items — resample item indices with replacement, recompute the statistic, take the 2.5th and 97.5th percentiles. It handles judge scores, rubric sums and pass rates identically, it needs no distributional assumption, and it is fifteen lines. Resample items, not individual calls: items are the independent unit, and resampling calls understates the uncertainty by pretending the item sample was fixed.

For a single proportion, the Wilson score interval is the closed-form answer and is markedly better behaved than the textbook normal interval at small n or extreme rates, where the normal interval happily produces bounds above 1. It is the right default for “40 of 50 passed”.

Four ways to manufacture significance

• Peeking. Running the eval, seeing p = 0.09, adding 50 items, running again. Optional stopping inflates the false positive rate well above the nominal 5% — with enough peeks you can reach significance on a null effect almost surely. Fix the sample size in advance using the calculation above, or use a sequential method designed for it. Do not eyeball a growing set.
• Unpaired analysis on paired data. The opening example, in reverse: it usually costs you power rather than manufacturing significance, but it also makes the result depend on an item sample you have effectively randomised twice. Keep the per-item vectors.
• Slicing until something is significant. Twenty slices at α = 0.05 gives you roughly a 64% chance of at least one spurious “significant” slice under a pure null. If you report per-stratum, per-language and per-customer-tier results, control the false discovery rate: Benjamini-Hochberg is to sort the m p-values ascending and find the largest i with p(i) <= (i/m)·q, then reject everything up to it. Six lines of code, and it turns a fishing expedition back into an analysis.
• Reusing one eval set for a hundred decisions. Every decision made against the same items overfits them a little. The set stops estimating your task and starts estimating itself. Hold back a sealed slice used only for final go/no-go calls, and rotate items in from production so the set is not the same set forever.