Blame for code/notes/src/0209-variance-components-equivalence.tex

\documentclass[11pt]{article}
\usepackage{common}
\begin{document}
\notehead{0209}{Variance components and equivalence tests for evaluation}{Batch M2, extension of 0208. Companion notebook: \texttt{notebooks/0209-variance-components-equivalence.ipynb} (rational arithmetic, Gauss--Hermite integration, Monte Carlo with stated tolerances; executed, 33 checks).}

\begin{problem}
\question{When two training recipes score within a point of each other on a benchmark, which source of randomness explains the gap, can any amount of extra evaluation remove it, and what would it take to show the recipes are \emph{equivalent} rather than merely not shown to differ?}
Note 0208 treated problems and generated samples as the two random sources and gave exact paired tests for one pair of systems. A real comparison has a third source, \emph{which training run} produced the model, and a fourth hazard, \emph{which checkpoint} was reported. This note separates the sources by their variance components, shows which one survives more problems and more samples, derives the unbiased pass@$k$ estimator's exact variance (0203 gave the estimator), states the paired sign-flip test and its actual null, shows that re-sampling generations on the \emph{same} problems removes only part of a selection bias, and replaces ``no significant difference'' by a two one-sided test (TOST) with its minimum detectable effect (MDE). The answer: the training-seed term is a floor that neither $N$ nor $m$ lowers, regenerating on the same problems keeps the seed$\times$problem share of the selection bias, and equivalence needs a pre-set margin and roughly as many problems as detection does.
\end{problem}
\stepcounter{section}% the problem box counts as section 1: keeps every \S and notebook cross-reference stable

\section{Notation}
\begin{center}
\begin{tabular}{@{}p{0.36\linewidth}p{0.60\linewidth}@{}}
\toprule
Symbol & Meaning \\ \midrule
$N=244,\ S,\ m=16$ & problems, independently trained models (seeds) of one recipe, samples per (seed, problem) \\
$p_{sx}$ & solve probability of model $s$ on problem $x$; $c_{sx}\sim\mathrm{Bin}(m,p_{sx})$ \\
$\sigma_A^2,\sigma_B^2,\sigma_C^2$ & variance components of $p_{sx}=\mu+A_x+B_s+C_{sx}$: problems, seeds, seed$\times$problem \\
$\sigma_e^2=\E\,p(1-p)$ & generation (Bernoulli) noise per sample \\
$Y_s=\frac1{Nm}\sum_xc_{sx}$ & score of run $s$ \\
$e(n,c,k)=1-\binom{n-c}k/\binom nk$ & unbiased pass@$k$ from $c$ successes in $n$ samples (0203) \\
$d_x,\ T=\sum_xd_x$ & per-problem paired difference and its sum \\
$\Delta,\ \alpha$ & equivalence margin, level of each one-sided test \\
$\mathrm{MDE}$ & smallest true difference detected with $80\%$ power at two-sided $5\%$ \\ \bottomrule
\end{tabular}
\end{center}

\section{Derivation}
\subsection{Four sources of variance and a floor}
The array $(p_{sx})$ is exchangeable in $s$ and in $x$ (seeds are i.i.d., problems are i.i.d.), so it has an orthogonal ANOVA decomposition $p_{sx}=\mu+A_x+B_s+C_{sx}$ with $\Var A=\sigma_A^2$, $\Var B=\sigma_B^2$, $\Var C=\sigma_C^2$. The law of total variance applied to $c_{sx}\mid p_{sx}$ gives, for the score of \emph{one} run,
\begin{equation}\label{eq:var1}
\Var Y_s=\frac{\sigma_A^2}N+\sigma_B^2+\frac{\sigma_C^2}N+\frac{\sigma_e^2}{Nm},
\end{equation}
and for the mean of $S$ seeds the second and third terms are divided by $S$ and the last by $NSm$. The problem term is the benchmark-sampling variance of 0208; the last is generation noise (it falls with $m$); the seed term $\sigma_B^2$ has no $N$ or $m$ in the denominator. \emph{Training-seed variance is the only term that no benchmark size and no number of samples reduces}; only more independently trained models reduce it, as $1/S$.

\textbf{Estimation} (balanced crossed design, cell means $\bar y_{sx}=c_{sx}/m$): with $\mathrm{MS}_x,\mathrm{MS}_s,\mathrm{MS}_r$ the usual mean squares for problems, seeds and residual, and $\hat\sigma_e^2$ the mean of the unbiased within-cell estimate $c(m-c)/(m(m-1))$ of $p(1-p)$,
\[
\hat\sigma_C^2=\mathrm{MS}_r-\hat\sigma_e^2/m,\qquad\hat\sigma_A^2=(\mathrm{MS}_x-\mathrm{MS}_r)/S,\qquad\hat\sigma_B^2=(\mathrm{MS}_s-\mathrm{MS}_r)/N .
\]
Each is unbiased because $\E\,\mathrm{MS}_r=\sigma_C^2+\sigma_e^2/m$, $\E\,\mathrm{MS}_x=\sigma_C^2+\sigma_e^2/m+S\sigma_A^2$, $\E\,\mathrm{MS}_s=\sigma_C^2+\sigma_e^2/m+N\sigma_B^2$. With only $S$ small the estimate of $\sigma_B^2$ is noisy (it rests on $S-1$ degrees of freedom): the honest way to know the seed term is to train several seeds.

\textbf{Toy.} Logit-normal model $p_{sx}=\mathrm{expit}(\mu_x+a_s+b_{sx})$ with $\mu_x\sim\mathcal N(0.3,1.5^2)$, $a_s\sim\mathcal N(0,0.25^2)$, $b_{sx}\sim\mathcal N(0,0.5^2)$ (seed sizes chosen for illustration, not measured on any model). Gauss--Hermite integration gives $\E p=0.551$, $\sigma_A^2=0.0674$, $\sigma_B^2=1.80\times10^{-3}$ (sd $0.042$), $\sigma_C^2=8.5\times10^{-3}$, $\sigma_e^2=0.170$. At $N=244,m=16,S=1$ the four terms of (\ref{eq:var1}) are $2.76\times10^{-4}$ (problems), $1.80\times10^{-3}$ (seed), $3.5\times10^{-5}$ (seed$\times$problem), $4.3\times10^{-5}$ (generation): the seed term is $83\%$ of the total.
\ver{the empirical variance of $Y_s$ over $6000$ replications is $2.219\times10^{-3}$ against $2.155\times10^{-3}$ from (\ref{eq:var1}) ($3.0\%$, tolerance $4$ s.e.$=7.3\%$); the four ANOVA estimators averaged over $4000$ replications at $S=4$ are within $1.6$ s.e.\ of the Gauss--Hermite truth ($\hat\sigma_e^2$: $z=+0.95$, $\hat\sigma_C^2$: $-0.15$, $\hat\sigma_A^2$: $-0.66$, $\hat\sigma_B^2$: $-1.57$).}

\subsection{Comparing two recipes: the floor on the MDE}
Take two recipes with $S$ seeds each, evaluated on the same problems, and $\hat\delta=\bar Y_A-\bar Y_B$. Under $H_0$ (same recipe) the shared problem effect $A_x$ cancels, so
\begin{equation}\label{eq:vardiff}
\Var\hat\delta=\frac2S\Bigl[\sigma_B^2+\frac{\sigma_C^2}N+\frac{\sigma_e^2}{Nm}\Bigr],\qquad \mathrm{MDE}=(z_{0.975}+z_{0.8})\sqrt{\Var\hat\delta}\ \xrightarrow{N,m\to\infty}\ 2.80\sqrt{2\sigma_B^2/S}.
\end{equation}
Pairing on problems removes $\sigma_A^2$; nothing on the benchmark side removes $\sigma_B^2$. In the toy the MDE at $N=244$ is $17.2$ points for $S=1$, $9.9$ for $S=3$, $7.7$ for $S=5$, against floors of $16.8$, $9.7$, $7.5$ points: with these (illustrative) seed sizes enlarging the benchmark is pointless and training another seed is not. The seed standard deviation is the number that decides this, and it has to be measured for the recipe at hand. \ver{$\Var\hat\delta$ over $6000$ replications: $3.803\times10^{-3}$ vs $3.757\times10^{-3}$ at $S=1$, $1.237\times10^{-3}$ vs $1.252\times10^{-3}$ at $S=3$ (both within $1.3\%$).}

\subsection{Unbiased pass@$k$: exact moments}
With $c\sim\mathrm{Bin}(n,p)$ the estimator $e(n,c,k)=1-\binom{n-c}k\big/\binom nk$ has $\E\,e=1-(1-p)^k$ (0203), so it is unbiased for $\mathrm{pass@}k=1-(1-p)^k$. The \emph{naive} plug-in $1-(1-c/n)^k$ is not: by Jensen it is biased low (exact bias $-0.076$ at $n=64,k=32,p=0.02$; $-0.021$ at $k=8,p=0.1$; $-0.147$ at $n=k=8$, $p=0.1$ is the extreme). Its variance has no tidy closed form, but it is a finite sum, $\Var e=\sum_c\mathrm{Bin}(c;n,p)\,e(n,c,k)^2-[1-(1-p)^k]^2$, with two checkable limits: $k=1$ gives $p(1-p)/n$ and $k=n$ gives $e=\ind\{c>0\}$, so $\Var=q(1-q)$ with $q=1-(1-p)^n$. Relative spread at $n=64$:
\begin{center}\small
\begin{tabular}{@{}rrrr@{}}
\toprule
$p$ & $k=1$ & $k=8$ & $k=32$ \\ \midrule
$0.02$ & $0.875$ & $0.818$ & $0.681$ \\
$0.10$ & $0.375$ & $0.257$ & $0.076$ \\
$0.50$ & $0.125$ & $0.005$ & $0$ \\ \bottomrule
\end{tabular}
\end{center}
(entries are $\mathrm{sd}(e)/\mathrm{pass@}k$ from the exact sum). Pass@$k$ for hard problems (small $p$) is a high-variance quantity even with $64$ samples. Over the benchmark, with $p_x$ drawn from a population, $\Var\bar e=\frac1N[\Var_x(1-(1-p_x)^k)+\E_x\Var(e\mid p_x)]$, the same two terms as in (\ref{eq:var1}) for a single model. \ver{exact rational arithmetic: $\E e=1-(1-p)^k$ for six $(n,k,p)$, $k=1$ and $k=n$ variances exact; exact $\Var e$ vs $2\times10^6$ draws at $(64,8,0.1)$ within $0.1\%$; benchmark variance of pass@$8$ with $p_x\sim\mathrm{Beta}(1.4,0.7)$, $N=244$, $n=64$: $6.46\times10^{-5}$ empirical vs $6.32\times10^{-5}$ ($2.3\%$).}

\subsection{The paired sign-flip test}
For per-problem differences $d_x=e^A_x-e^B_x$ let $T=\sum_xd_x$. If each $d_x$ is independent and symmetric about $0$, then multiplying any subset by $-1$ does not change the joint law, so the $2^N$ sign vectors are equally likely and
\[
p=2^{-N}\,\#\{\epsilon\in\{\pm1\}^N:\ |\textstyle\sum\epsilon_xd_x|\ge|T|\},
\]
exact for $N\le18$ by enumeration and by Monte Carlo (with the $+1$ correction in numerator and denominator) beyond. For $d_x\in\{-1,0,1\}$ the zeros contribute nothing and $p$ equals the exact McNemar $p$ of 0208; the best $(5,0)$ outcome again gives $0.0625$. Two cautions. The null is \emph{symmetry}, not mean zero: for the skewed mean-zero variable $d=+9$ w.p.\ $0.1$, $-1$ otherwise, at $N=12$ the size is $0.294$ against a nominal $0.05$. And the test is paired at the problem level, so it uses the problem as the unit but ignores the seed term of (\ref{eq:vardiff}): it answers ``on these problems, for these trained models''. \ver{sign-flip $=$ McNemar for all $b,c\le7$ (max difference $0$); Monte Carlo ($B=20000$) vs exact at $N=14$ within $7\times10^{-4}$; size under the null with shared $p_x$, $N=60$, pass@$8$ from $64$ samples: $0.058$ over $1500$ benchmarks (s.e.\ $0.006$).}

\subsection{``Fresh seed on the same problems'' removes sampling noise, not selection bias}
Select the best of $K$ candidate checkpoints on a benchmark and report its score. Suppose all have identical true population quality $\theta$. On the fixed benchmark candidate $k$ has a quenched advantage $\beta_k\sim\mathcal N(0,\sigma_\beta^2)$ with $\sigma_\beta^2=\sigma_C^2/N$ (the seed$\times$problem component: which problems this checkpoint happens to get right) plus generation error $g_k\sim\mathcal N(0,\sigma_g^2)$, $\sigma_g^2=\sigma_e^2/(Nm)$. Select $k^\star=\arg\max_k(\beta_k+g_k)$ and write $\sigma_t^2=\sigma_\beta^2+\sigma_g^2$, $c_K=\E\max_{j\le K}Z_j$. Then
\begin{align*}
&\text{(i) same sample: }\ \E(\beta+g)_{k^\star}-\theta=\sigma_t\,c_K;\\
&\text{(ii) fresh generations, same problems: }\ \E(\beta+g')_{k^\star}-\theta=\E\beta_{k^\star}=\frac{\sigma_\beta^2}{\sigma_t}c_K\qquad(\text{since }\E[\beta\mid\beta+g=y]=\tfrac{\sigma_\beta^2}{\sigma_t^2}y);\\
&\text{(iii) fresh problems: }\ 0 .
\end{align*}
Re-sampling \emph{retains the fraction} $\sigma_\beta^2/\sigma_t^2$ of the bias. In the toy ($K=8$, $c_8=1.4236$, $\sigma_\beta^2=3.5\times10^{-5}$, $\sigma_g^2=4.3\times10^{-5}$) the selected score is inflated by $1.26$ points in (i), by $0.56$ points in (ii) ($44.5\%$ retained), and by $0$ in (iii). The retained share is exactly the seed$\times$problem variance of the \emph{benchmark mean}: it falls like $1/N$ only through $\sigma_C^2/N$ and is irreducible by regeneration. (``Fresh seed'' here means a new generation seed for the same checkpoint; retraining draws a new $a_s,b_{sx}$ and is a fresh-candidate evaluation, which does remove it.) \ver{$4\times10^5$ Monte Carlo selections: $1.262$ vs $1.260$ points in (i), $0.561$ vs $0.561$ in (ii), $0.000$ in (iii), each within $4$ s.e.; $c_8$ by quadrature agrees with Monte Carlo to $7.6\times10^{-4}$.}

\subsection{Equivalence by TOST, and the MDE}
``No significant difference'' is the absence of rejection of $H_0:\delta=0$; it does not support $\delta\approx0$. To claim equivalence within a pre-registered margin $\Delta$, test $H_0:|\delta|\ge\Delta$ against $|\delta|<\Delta$ by two one-sided tests, $p_U=\Phi((\hat\delta-\Delta)/s)$ for $\delta\ge\Delta$ and $p_L=1-\Phi((\hat\delta+\Delta)/s)$ for $\delta\le-\Delta$, and reject when $\max(p_L,p_U)<\alpha$ \cite{schuirmann,lakens}. Facts used: (a) duality, TOST at level $\alpha$ rejects iff the $(1-2\alpha)$ confidence interval lies inside $(-\Delta,\Delta)$; (b) the size is $\alpha$, attained at $\delta=\pm\Delta$ (there $\hat\delta<\Delta-z_{1-\alpha}s$ has probability $\alpha$, and the other tail is negligible); (c) the power at $\delta=0$ is $2\Phi(\Delta/s-z_{1-\alpha})-1$, so $80\%$ power needs $\Delta/s=z_{0.95}+z_{0.90}=2.927$, i.e.
\[
N\ \ge\ \Bigl(\frac{2.927\,\sigma_d}{\Delta}\Bigr)^2\quad(\text{paired per-problem standard deviation }\sigma_d),\qquad \mathrm{MDE}=(z_{0.975}+z_{0.80})\frac{\sigma_d}{\sqrt N}.
\]
With $10\%$ discordance ($\sigma_d^2=0.1$) at $N=244$: $s=0.0202$, MDE $=13.8$ problems ($5.7$ points; 0208's exact trinomial value is $14.3$). To \emph{demonstrate} equivalence within $\Delta=2$ points needs $N\approx2141$ problems; to detect a $5/244$ gain at $80\%$ power needs $1867$ (0208, normal approximation). If the true effect is $3$ points (outside the margin), the difference test misses it $68\%$ of the time while TOST ``accepts'' equivalence in $0.00\%$ of cases. Ordinary benchmarks of a few hundred problems can therefore neither show equivalence within a point or two nor a small gain, and the sensible output is the interval, with the seed term of (\ref{eq:vardiff}) added when recipes (not checkpoints) are compared. \ver{$100000$ random cases: TOST $p<0.05$ iff the $90\%$ CI is inside $(-\Delta,\Delta)$ in all; rejection probability at $\delta=\pm0.02$ is $0.0495$ and $0.0499$ over $4\times10^5$ draws; power at $\delta=0$ $0.6083$ vs $0.6075$; MDE gives power $0.7994$; $N_{80\%}=1866.8$ reproduces 0208's $1867$; $N=2141$ gives $80\%$ TOST power to $2\times10^{-16}$.}

\section{Boxed result}
\begin{result}
\begin{align*}
\Var Y_s&=\tfrac{\sigma_A^2}N+\sigma_B^2+\tfrac{\sigma_C^2}N+\tfrac{\sigma_e^2}{Nm},\qquad
\Var\hat\delta=\tfrac2S\bigl[\sigma_B^2+\tfrac{\sigma_C^2}N+\tfrac{\sigma_e^2}{Nm}\bigr],\\
\E\,e(n,c,k)&=1-(1-p)^k,\qquad \Var e=\textstyle\sum_c\mathrm{Bin}(c;n,p)\,e^2-[1-(1-p)^k]^2,\\
\text{bias after regenerating}&=\tfrac{\sigma_\beta^2}{\sigma_\beta^2+\sigma_g^2}\times\text{bias before},\qquad
p_{\mathrm{TOST}}=\max\{p_L,p_U\},\quad N\ge\Bigl(\tfrac{2.927\,\sigma_d}{\Delta}\Bigr)^2 .
\end{align*}
Toy: seed term $=83\%$ of $\Var Y_s$; MDE floor $9.7$ points at $S=3$; $N\approx2141$ problems to show equivalence within $2$ points at $10\%$ discordance.
\end{result}

\section{What breaks}
\begin{breaks}
\begin{tabular}{@{}p{0.27\linewidth}p{0.30\linewidth}p{0.37\linewidth}@{}}
\toprule
Failure & Assumption violated & Consequence \\ \midrule
One trained model per recipe, error bars from problems only & seed variance is negligible & the dominant term (here $83\%$) is missing; intervals far too narrow \\
Seed variance read off $S=2$ or $3$ runs & $\hat\sigma_B^2$ well estimated & $S-1$ degrees of freedom; the floor itself is uncertain \\
Plug-in $1-(1-c/n)^k$ & unbiased estimator & biased low, worst for large $k/n$ and small $p$ \\
Pass@$k$ for hard problems with few samples & variance small & relative sd $0.7$--$0.9$ at $p=0.02$ even with $n=64$ \\
Sign-flip test on skewed differences & symmetry, not mean zero & size $0.294$ at $N=12$ \\
Re-sample generations to ``confirm'' a selected checkpoint & selection independent of the problems & $44.5\%$ of the bias remains; only fresh problems or fresh candidates remove it \\
``$p>0.05$, so equivalent'' & absence of evidence is evidence & TOST is the only test of equivalence; margin must be fixed before the run \\
Margin chosen after seeing the data & $\Delta$ pre-registered & size of TOST is no longer $\alpha$ \\
Normal approximation at small discordance & many discordant pairs & use the exact tests of 0208; MDE from the normal formula is $3\%$ low at $d=0.10$ \\ \bottomrule
\end{tabular}
\end{breaks}

\nextnote{0210 turns to the \emph{inputs} of training: which web pages, problems and samples enter the corpus, how a selection rule that uses the same samples it is later judged on produces the same kind of bias as the selection above, and how contamination is detected.}

\begin{thebibliography}{9}
\bibitem{miller} E.~Miller. Adding Error Bars to Evals: A Statistical Approach to Language Model Evaluations. arXiv:2411.00640, Secs.~3--5 (variance decomposition, paired analysis, power).
\bibitem{codex} M.~Chen et al. Evaluating Large Language Models Trained on Code. arXiv:2107.03374, Sec.~2.1 (unbiased pass@$k$ estimator).
\bibitem{schuirmann} D.~J.~Schuirmann. A comparison of the two one-sided tests procedure and the power approach for assessing the equivalence of average bioavailability. J.\ Pharmacokinetics and Biopharmaceutics 15:657--680, 1987. \emph{Not on arXiv; not fetched; classical, cited for the TOST procedure.}
\bibitem{lakens} D.~Lakens. Equivalence tests: a practical primer for $t$ tests, correlations, and meta-analyses. Social Psychological and Personality Science 8(4):355--362, 2017. \emph{Not on arXiv; not fetched; cited for the duality with the $(1-2\alpha)$ interval and for margin pre-registration.}
\end{thebibliography}
\end{document}