Problem 120 · Evaluation

Eval Harness with a Paired Bootstrap Confidence Interval

HardAI engineering

01Problem

Two systems A and B were scored on the same n eval items (`a[i]`, `b[i]`). Write `paired_bootstrap(a, b, n_resamples, alpha, seed)` that resamples item indices with replacement, computes the mean of `b[i] - a[i]` for each resample, and returns the observed mean difference, the percentile confidence interval `(lo, hi)`, and the fraction of resamples where B is not better (`<= 0`). Also write `unpaired_bootstrap` that resamples A and B independently, and show the paired CI is much tighter on the same data.

02Key insight

Eval items vary wildly in difficulty, and that variance is shared by both systems. Pairing cancels it: you bootstrap the per-item differences, so a consistent 2-point gain is detectable on 200 items even when per-item scores range from 0 to 1. The unpaired version treats the systems as independent samples and buries the effect in item variance, which is why teams wrongly conclude 'no significant difference'. A seeded RNG makes the CI reproducible, which matters when it gates a release.

03Solution

solution.pypython32 lines

import random
from statistics import fmean


def _ci(stats: list[float], alpha: float) -> tuple[float, float]:
    stats = sorted(stats)
    n = len(stats)
    lo = stats[int(alpha / 2 * n)]
    hi = stats[max(0, int((1 - alpha / 2) * n) - 1)]
    return lo, hi


def paired_bootstrap(a: list[float], b: list[float], n_resamples: int = 2000, alpha: float = 0.05,
                     seed: int = 0) -> dict[str, float]:
    if len(a) != len(b) or not a:
        raise ValueError("need equal-length, non-empty score lists")
    diffs = [y - x for x, y in zip(a, b)]
    rng = random.Random(seed)
    n = len(diffs)
    stats = [fmean(rng.choices(diffs, k=n)) for _ in range(n_resamples)]
    lo, hi = _ci(stats, alpha)
    return {"diff": fmean(diffs), "lo": lo, "hi": hi,
            "p_not_better": sum(s <= 0 for s in stats) / n_resamples}


def unpaired_bootstrap(a: list[float], b: list[float], n_resamples: int = 2000, alpha: float = 0.05,
                       seed: int = 0) -> dict[str, float]:
    rng = random.Random(seed)
    stats = [fmean(rng.choices(b, k=len(b))) - fmean(rng.choices(a, k=len(a))) for _ in range(n_resamples)]
    lo, hi = _ci(stats, alpha)
    return {"diff": fmean(b) - fmean(a), "lo": lo, "hi": hi,
            "p_not_better": sum(s <= 0 for s in stats) / n_resamples}

Try it first.

TimeO(n_resamples * n)

SpaceO(n + n_resamples)

tests.py · 8 passing

tests.pypython20 lines

same = [0.1, 0.5, 0.9, 0.3]
r = paired_bootstrap(same, same)
assert r["diff"] == r["lo"] == r["hi"] == 0 and r["p_not_better"] == 1.0
shift = paired_bootstrap(same, [x + 0.1 for x in same])
assert abs(shift["lo"] - 0.1) < 1e-9 and abs(shift["hi"] - 0.1) < 1e-9 and shift["p_not_better"] == 0
rng = random.Random(123)
a = [rng.random() for _ in range(200)]
b = [x + 0.02 + rng.uniform(-0.01, 0.01) for x in a]
p = paired_bootstrap(a, b, seed=1)
u = unpaired_bootstrap(a, b, seed=1)
assert p["lo"] > 0 and p["p_not_better"] == 0
assert u["lo"] < 0 < u["hi"]
assert (p["hi"] - p["lo"]) * 10 < (u["hi"] - u["lo"])
assert paired_bootstrap(a, b, seed=1) == p
assert abs(p["diff"] - u["diff"]) < 1e-12
try:
    paired_bootstrap([1.0], [1.0, 2.0])
    assert False
except ValueError:
    pass

04Staff-level follow-up

Items are often clustered (several questions per document, several turns per conversation); resample clusters, not items, or the CI is too narrow. With many metrics or many candidate systems, correct for multiple comparisons or pre-register the primary metric. For LLM outputs also account for sampling noise by running each item several times, and decide the minimum effect size worth shipping before you look at the numbers.