skip to content

How do you build a paired permutation test for the log-loss gap between two models?

level: seniorimportance: should knowfreq 36%

answer

  1. work with per-example differences
  2. the model labels are what is arbitrary
  3. swapping labels negates one difference
  4. flip signs, do not shuffle across examples
  5. add one to numerator and denominator

basics

~20 s

Take the per-example loss differences on the shared test set. The null makes the two models interchangeable, so flip each difference's sign at random thousands of times and count how often the resampled mean is as extreme.

solid answer

~50 s

Score both models on the same held-out set and form `d_i = loss_A(i) - loss_B(i)` for every example. The observed statistic is the mean of the `d_i`. The null says the model labels are arbitrary, and swapping the two labels on one example flips the sign of that example's difference - so the permutation group here is independent sign flips, not shuffling values between two lists. Draw a few thousand sign patterns, recompute the mean each time, and report `p = (1 + number of resampled means at least as extreme as the observed one) / (B + 1)`, two-sided on absolute value. The add-one keeps you from ever reporting p = 0. The appeal is that it assumes nothing about the shape of the loss differences, which for log-loss are heavy-tailed and badly skewed. If the test examples are clustered, flip signs at the cluster level.

code

python · 21 lines
python
import random

random.seed(0)
# Per-example loss differences on the shared test set: loss_A(i) - loss_B(i).
# Stand-in numbers here; in practice these come from scoring both models.
d = [random.gauss(-0.02, 0.3) for _ in range(1000)]

def mean(xs):
    return sum(xs) / len(xs)

observed = mean(d)
B = 2000
extreme = 0
for _ in range(B):
    flipped = mean([x if random.random() < 0.5 else -x for x in d])
    if abs(flipped) >= abs(observed):
        extreme += 1

p = (1 + extreme) / (B + 1)
print("observed mean difference:", round(observed, 5))
print("two-sided permutation p:", round(p, 4))

go deeper

for a junior

Know that a permutation test builds its own null distribution by rearranging the data you already have, and that here the rearrangement is applied to per-example differences rather than to raw scores.

for a middle

Explain the mechanics end to end: form the differences, flip signs, recompute the mean, count the extremes, and use the add-one p-value. Be able to say why the smallest reportable p is 1/(B+1).

for a senior

Justify sign flipping from model-label exchangeability, spot clustered test data and move the flip to the cluster level, and insist on reporting a paired interval on the gap next to the p-value.

for a principal

Frame what such a p-value is worth as evidence for a release decision, and be clear about the uncertainty it excludes - seed variance, selection on the same test set, and distribution shift - when setting the bar for acting on offline results.

## The unit of analysis is the per-example difference Both models score the same held-out set, so every example yields a pair of losses and hence one difference: ``` d_i = loss_A(i) - loss_B(i) ``` Everything downstream operates on the vector of `d_i`. This is what makes the test paired: the shared difficulty of each example is subtracted away inside the example, and only the model-to-model contrast survives. The observed statistic is usually `mean(d)`, though the median or a trimmed mean works identically if you prefer robustness. ## Why sign flipping is the right permutation The null hypothesis is that the two models are exchangeable - the label "A" or "B" attached to the two loss values on a given example is arbitrary. If you swap those two labels on example `i`, `d_i` becomes `-d_i` and nothing else changes. So the set of relabellings consistent with the null is exactly the `2^n` sign patterns, and a valid permutation null is generated by flipping each sign independently with probability 0.5. Shuffling the loss values *between* examples would be a different and wrong procedure: it destroys the pairing, tests a null about two unrelated samples, and typically produces a much wider null distribution than the data warrant. Getting this distinction right is most of what the question is testing. Formally, sign flipping is valid when each `d_i` has a distribution symmetric about zero under the null. Model-label exchangeability delivers that symmetry, which is why the argument is clean here even though log-loss differences are wildly non-normal. ## The procedure 1. Compute `d_1 ... d_n` and the observed `t_obs = mean(d)`. 2. Repeat `B` times: draw a sign `s_i` in {-1, +1} independently for each example, compute `t_b = mean(s_i * d_i)`. 3. Count how many `t_b` satisfy `|t_b| >= |t_obs|`. 4. Report `p = (1 + count) / (B + 1)`. The add-one in numerator and denominator is not cosmetic: it makes the p-value valid as a Monte Carlo estimate and stops you from reporting an impossible `p = 0` when no resample was more extreme. It also sets the resolution floor - with `B = 10,000` you cannot report anything below about `1e-4`, so choose `B` with the threshold you care about in mind. ## Which metrics this works for Any metric that decomposes as a mean over examples: log-loss, squared error, absolute error, 0/1 correctness, per-example reward. Metrics defined over *pairs* or as ratios of aggregates - ranking-based scores and metrics assembled from a full confusion matrix - do not decompose that way, and sign flipping per example is not defined for them. For those, resample the test examples themselves and recompute both models' metric on each identical resample. ## Reporting the effect, not just the p-value A permutation test gives a p-value and nothing else. Pair it with a paired interval on `mean(d)` - resample examples with replacement, scoring both models on each shared resample, and take percentiles of the differences - so the write-up carries the size of the gap and its uncertainty, not just a verdict. "Model B's mean log-loss is 0.014 lower, interval 0.004 to 0.024" is a far more useful sentence than "p = 0.006". ## Assumptions and failure modes - **Independence across examples.** If the test set has several examples per user, document or session, the exchangeable unit is the cluster. Flip one sign per cluster and apply it to all that cluster's differences; flipping per example produces a null that is too narrow and a p-value that is too small. - **Scope of the uncertainty.** The procedure accounts for the randomness of *which examples are in the test set*. It says nothing about training-seed variation, hyperparameter choices, or the difference between your test distribution and the one the model will meet later. - **A frozen comparison.** The test is a statement about these two fixed models on this fixed data. If either model was selected by looking at this same test set, the p-value is optimistic. - **Ties and zeros.** Examples where the two models produce identical losses have `d_i = 0` and contribute nothing under any sign flip, which is correct and harmless. ## Why bother rather than assuming a shape Per-example log-loss is bounded below by zero and unbounded above; a single confidently-wrong prediction can contribute an enormous term. The differences inherit that heavy tail and strong skew. A permutation test never needs the sampling distribution of the mean to be well behaved - it constructs the null from your own data - which is why it is the default recommendation for offline head-to-head comparisons on loss-based metrics.

  • Why flip signs rather than shuffle the loss values between the two models' lists?
    Because the data are paired. Each example contributes one difference, and the null says only the model label on that example is arbitrary - swapping it negates that example's difference. Shuffling values across examples breaks the pairing, tests a null about two unrelated samples, and produces a null distribution far wider than the design justifies.
  • How many permutations should you draw?
    Enough that the resolution floor sits well below the threshold you care about: the smallest reportable p is 1/(B+1). A thousand resamples is fine for deciding whether you are near 0.05; ten thousand or more if you want a stable small p-value. Report the add-one form rather than zero when nothing exceeds the observed statistic.
  • The test set has twenty examples per user. What changes?
    The exchangeable unit becomes the user, not the example. Draw one sign per user and apply it to all of that user's differences. Flipping independently per example pretends you have far more independent observations than you do, shrinking the null distribution and producing p-values that are too small.
  • What does the permutation p-value not cover?
    Only the randomness of which examples landed in the test set. It ignores training-seed and data-order variation, any hyperparameter choice made while looking at this data, and any shift between the test distribution and the one the model will actually face. Two models re-trained with different seeds can move by more than the gap you just certified.

saying these in an interview costs you the question

  • Shuffles loss values across examples instead of flipping signs
  • Reports p = 0 because no resample beat the observed value
  • Applies per-example sign flips to a metric defined over pairs
  • Ignores clustering and flips signs example by example
  • Quotes a precise p-value after a few hundred resamples
  • Treats the p-value as covering training-seed variability

context

resolving links…