Seven language models in the HELM evaluation of MMLU answered between 67.0% and 70.7% of its 14,042 questions correctly. The questions fall into 57 subjects, from abstract algebra to world religions, and no model leads in all of them: Mixtral 8x7B alone has the best score among the seven in 19 subjects, and each of the other six is alone best in at least two. Is any of the seven better than another across subjects of this kind, and if so, which? The question is not about one benchmark score with a standard error. It is about a table of scores, seven systems by 57 tasks, whose columns are on different scales.
The standard answer is Friedman's test, recommended for this purpose by Demšar (2006): within each task, rank the systems; then ask whether the average ranks differ more than random rankings would. If they do, Nemenyi's test decides which pairs differ. For the seven models, Friedman's statistic is 39.89 on 6 degrees of freedom ($p < 0.0001$), and Nemenyi's test separates 5 of the 21 pairs.
First we see why averaging scores over tasks misleads. Then we set out the null hypothesis that ranks test, compute the moments of a random ranking, and derive Friedman's statistic, its exact distribution, its chi-squared limit and its correction for ties. Next we show that the Iman–Davenport statistic is the analysis of variance of the ranks and check both approximations against exact sizes. Then we derive Nemenyi's critical difference, and show the weakness that Benavoli, Corani and Mangili (2016) illustrate in it: the comparison of two systems depends on which other systems are present. Finally we apply the procedure to twelve retrieval runs on Cranfield. The article assumes the sign and signed-rank tests of The Sign Test and the Wilcoxon Signed-Rank Test, the Bonferroni and Holm corrections of Multiple Comparisons and the Bonferroni Correction, and Pearson's theorem in The Chi-Square Goodness-of-Fit Test.
The data: systems by tasks
Write $k$ for the number of systems and $N$ for the number of tasks (Demšar's letters), and $x_{ij}$ for the score of system $j$ on task $i$. Here $k = 7$ and $N = 57$, and $x_{ij}$ is model $j$'s accuracy on subject $i$. The subjects are the "57 tasks" of Hendrycks et al. (2021); the results are those of the HELM project (Liang et al., 2022), as described for this unit in Standard Errors for Benchmark Scores. The short names used here stand for HELM's model identifiers, given without the organization prefix: Mixtral 8x7B is mixtral-8x7b-32kseqlen, Gemini 1.0 Pro gemini-1.0-pro-001, Llama 2 70B llama-2-70b, text-bison text-bison@001, GPT-3.5 Turbo gpt-3.5-turbo-0613, Qwen1.5 14B qwen1.5-14b, Claude Instant 1.2 claude-instant-1.2, GPT-4 Turbo (1106 preview) gpt-4-1106-preview and Llama 3 70B llama-3-70b.
The unit of evidence is the task. Demšar (2006, Section 3) stresses that the sample size in such a comparison is the number of tasks, and that the scores on each task are taken as given: their own sampling error, the noise of a finite set of questions, is not modeled. The question being asked is whether the systems differ across a population of tasks like these 57, not whether they differ on these exact questions; Paired Comparisons of Models answers the second kind of question.
| Model | Mean rank $R_j$ | Mean of subject accuracies | Overall accuracy | Subjects where alone best |
|---|---|---|---|---|
| Mixtral 8x7B | 2.78 | 0.717 | 0.707 | 19 |
| Gemini 1.0 Pro | 3.36 | 0.700 | 0.695 | 6 |
| Llama 2 70B | 3.97 | 0.695 | 0.691 | 2 |
| text-bison | 3.97 | 0.692 | 0.679 | 6 |
| GPT-3.5 Turbo | 4.40 | 0.689 | 0.682 | 2 |
| Qwen1.5 14B | 4.73 | 0.686 | 0.670 | 3 |
| Claude Instant 1.2 | 4.78 | 0.688 | 0.684 | 6 |
The mean rank is defined in the section after next. The last column counts subjects in which the model has the highest accuracy with no other model equal to it; 13 subjects have a tie for first place, so the column adds up to 44.
Why not average over tasks?
The obvious summary is a model's mean score over tasks. Demšar (2006, Section 3.1.1) gives two objections. Scores on different tasks need not be commensurable, so their average need not mean anything. And an average lets an excellent result on one task make up for poor results on many, or a single collapse outweigh fair results everywhere else.
Example (two averages, two orders). The table shows two averages already. The mean of the 57 subject accuracies weights subjects equally; the overall accuracy weights them by size, which runs from 100 questions to 1,534 (professional law, 0.109 of all questions). The two orders disagree within the seven: by the first, Claude Instant 1.2 (0.688) is behind GPT-3.5 Turbo (0.689); by the second it is ahead (0.684 against 0.682). Across all 28 models in the data, 6 pairs are ordered differently by the two averages. Neither average is wrong. They answer different questions, and the choice between them is not given by the data.
Example (the average and the head-to-head record disagree). Among the 28 models, GPT-4 Turbo (1106 preview) and Llama 3 70B have nearly the same mean subject accuracy, 0.7955 and 0.7934. GPT-4 Turbo (1106 preview) has the higher score in 34 subjects, the lower in 18, and they are tied in 5. A sign test on 34 wins and 18 losses gives $p = 0.036$ and the signed-rank test $p = 0.066$. Yet ranked within each subject among all 28 models, Llama 3 70B has the better mean rank, 4.81 against 4.96. The reason is in what a rank difference counts: when GPT-4 Turbo (1106 preview) wins a subject, an average of 3.24 rank places separate the two, and when it loses, 6.58. Its losses are not larger in accuracy (the median margins are 0.026 when it wins and 0.025 when it loses), but more of the other 26 models fall between the two when it loses. The section on pools returns to this, because it is the central weakness of mean ranks.
A paired t-test over tasks inherits the first objection: it tests the mean difference, which is the difference of the averages (Demšar, 2006, Section 3.1.2). Ranks remove the scale. Within a task, only the order of the systems is used, so a task where everyone scores near 0.9 and a task where everyone scores near 0.3 contribute on the same footing.
Ranks within tasks and the null hypothesis
Within task $i$, rank the $k$ systems from best (rank 1) to worst (rank $k$), giving tied systems the average of the ranks they occupy (midranks). Write $r_{ij}$ for the rank of system $j$ on task $i$, $T_j = \sum_i r_{ij}$ for its rank sum and $R_j = T_j/N$ for its mean rank. Every task's ranks add up to $1 + 2 + \cdots + k = k(k + 1)/2$, with or without ties, because a midrank replaces a block of consecutive ranks by their average. So the mean ranks average $(k + 1)/2$, which is 4 for seven systems.
The null hypothesis. Within each task, the $k$ scores are exchangeable: every assignment of the observed values to the $k$ systems is equally likely. Tasks are independent of one another. Without ties, the null hypothesis makes the rank vector of each task uniformly distributed over the $k!$ orderings of $1, \dots, k$.
This is what the test tests, and it is narrower than "the systems are equally good on average". A system that is better on most tasks by a small margin and worse on a few by a large one can have mean rank below $(k+1)/2$ while its mean score is lower; the rank test responds to the first fact and ignores the second, which is the point.
Lemma 1 (moments of a random ranking). If $(r_1, \dots, r_k)$ is a uniformly random ordering of $1, \dots, k$, then each $r_j$ has mean $(k + 1)/2$ and variance $(k^2 - 1)/12$, and two different ranks have covariance $-(k + 1)/12$.
Proof. Each $r_j$ is equally likely to be any of $1, \dots, k$, so its mean is $(k + 1)/2$. Its second moment is $\frac{1}{k}\sum_{m=1}^{k} m^2 = (k + 1)(2k + 1)/6$, so its variance is
$$\frac{(k + 1)(2k + 1)}{6} - \frac{(k + 1)^2}{4} = \frac{(k + 1)\big(2(2k + 1) - 3(k + 1)\big)}{12} = \frac{(k + 1)(k - 1)}{12}.$$
The sum $r_1 + \cdots + r_k$ is the constant $k(k + 1)/2$, so its variance, $k\operatorname{Var}(r_1) + k(k - 1)\operatorname{Cov}(r_1, r_2)$ by symmetry, is zero. Hence $\operatorname{Cov}(r_1, r_2) = -\operatorname{Var}(r_1)/(k - 1) = -(k + 1)/12$. $\blacksquare$
With ties, the same argument applies to task $i$ with its own multiset of midranks: a random permutation of fixed values $a_{i1}, \dots, a_{ik}$ with mean $(k+1)/2$ gives each system variance $\sigma_i^2 = \frac1k\sum_m (a_{im} - \frac{k+1}{2})^2$ and each pair covariance $-\sigma_i^2/(k - 1)$. Without ties $\sigma_i^2 = (k^2 - 1)/12$.
Friedman's statistic
Friedman (1937) proposed measuring how far the rank sums are from their common null mean $N(k + 1)/2$. Here is the plan. The deviations $T_j - N(k+1)/2$ have, under the null hypothesis, a covariance matrix proportional to a projection. Dividing by the right constant makes their squared length behave like Pearson's statistic for equally likely categories, and the same proof gives a chi-squared limit with $k - 1$ degrees of freedom.
Definition. Friedman's statistic is
$$Q = \frac{(k - 1)\sum_{j=1}^{k}\left(T_j - \frac{N(k + 1)}{2}\right)^2}{\sum_{i=1}^{N}\sum_{j=1}^{k}\left(r_{ij} - \frac{k + 1}{2}\right)^2}.$$
The statistic is defined as long as at least one task is not a complete tie (otherwise the denominator is 0). Without ties the denominator is $N k(k^2 - 1)/12$, because each task contributes $k$ times the variance in Lemma 1. Then $Q$ reduces to the form Demšar (2006, Section 3.2.2) gives,
$$\chi^2_F = \frac{12N}{k(k + 1)}\left[\sum_j R_j^2 - \frac{k(k + 1)^2}{4}\right] = \frac{12N}{k(k+1)}\sum_j\left(R_j - \frac{k+1}{2}\right)^2,$$
where the two forms agree because $\sum_j R_j = k(k + 1)/2$. With ties the denominator is smaller, and $Q$ is the tie-corrected statistic. In the denominator, ties only remove spread that a random ranking cannot produce.
Theorem 1 (the exact null distribution). Under the null hypothesis, given the tie pattern of each task, the distribution of $Q$ is that of the statistic computed after an independent uniform random permutation of the ranks within every task. Its mean is exactly $k - 1$.
Proof. Exchangeability within tasks and independence across tasks say exactly that the observed ranks have the same distribution as independently permuted ones, and the denominator of $Q$ is unchanged by permutations within tasks. For the mean, the rank sums are sums of independent task vectors with the moments above, so $\operatorname{Var}(T_j) = \sum_i\sigma_i^2$, and $E\sum_j(T_j - N(k+1)/2)^2 = k\sum_i \sigma_i^2$. The denominator equals $k\sum_i\sigma_i^2$, a constant, so $E(Q) = k - 1$. $\blacksquare$
The theorem gives an exact test for any $k$ and $N$, by enumeration when $(k!)^N$ is small and by Monte Carlo otherwise. For the seven models the script drew 10,000 random within-subject permutations of the ranks for each of 30 seeds; the permutation p-values are reported below.
Theorem 2 (the chi-squared limit). Without ties, as $N \to \infty$ under the null hypothesis, $\chi^2_F$ converges in distribution to the chi-squared distribution with $k - 1$ degrees of freedom.
Proof. Let $\mathbf{Z} = (T_1 - N\frac{k+1}{2}, \dots, T_k - N\frac{k+1}{2})\big/\sqrt{Nk(k + 1)/12}$. By Lemma 1, one task's rank vector has covariance matrix $\frac{k+1}{12}(kI - J)$, where $J$ is the matrix of ones, so the $N$ independent tasks give $\mathbf{Z}$ the covariance matrix
$$\frac{N(k + 1)(kI - J)/12}{Nk(k + 1)/12} = I - \frac{1}{k}J = I - \mathbf{u}\mathbf{u}^{\mathsf T}, \qquad \mathbf{u} = \tfrac{1}{\sqrt k}(1, \dots, 1).$$
That is the matrix $P$ of Lemma 1 in The Chi-Square Goodness-of-Fit Test with all $k$ category probabilities equal to $1/k$: a projection of rank $k - 1$. $\mathbf{Z}$ is $\sqrt N$ times a mean of $N$ independent, identically distributed centered vectors (each task's ranks minus $(k+1)/2$, divided by $\sqrt{k(k+1)/12}$). Steps 1 to 4 of the proof of Pearson's theorem there apply word for word: $\mathbf{Z}$ converges in distribution to $P\mathbf{Y}$ with $\mathbf{Y}$ a vector of independent standard normal variables, and $\lVert\mathbf{Z}\rVert^2$ converges to $\lVert P\mathbf{Y}\rVert^2$, which is chi-squared with $k - 1$ degrees of freedom. Finally $\lVert\mathbf{Z}\rVert^2 = \frac{12}{Nk(k+1)}\sum_j (T_j - N\frac{k+1}{2})^2 = \chi^2_F$. $\blacksquare$
The degrees of freedom have the same meaning as in Pearson's theorem: $k$ rank sums less one, because their total is fixed. With ties the tasks are no longer identically distributed, and the limit needs a central limit theorem for non-identical summands under a condition on the tie patterns; that version is not proved here. Theorem 1 does not need it, and the permutation p-values below check the approximation on the data.
Proposition (two systems: the sign test). With $k = 2$, let system 1 win $W$ tasks, lose $L$ and tie $N - W - L$. Then the uncorrected statistic is $(W - L)^2/N$ and the tie-corrected $Q$ is $(W - L)^2/(W + L)$, the square of the sign test's normal statistic with ties dropped.
Proof. The ranks on a task are $(1, 2)$, $(2, 1)$ or $(1.5, 1.5)$, so $T_1 - 1.5N = -\tfrac12 W + \tfrac12 L$ and $T_2 - 1.5N = \tfrac12(W - L)$. The numerator of $Q$ is $(2 - 1)\cdot 2\cdot\frac{(W - L)^2}{4} = \frac{(W - L)^2}{2}$. Each decided task contributes $2 \times \tfrac14$ to the denominator and each tie 0, so the denominator is $(W + L)/2$. Without ties the denominator would be $Nk(k^2-1)/12 = N/2$. $\blacksquare$
For GPT-4 Turbo (1106 preview) against Llama 3 70B, with 34 wins, 18 losses and 5 ties, $Q = 16^2/52 = 4.92$ and the uncorrected statistic is $16^2/57 = 4.49$. Benavoli et al. (2016, Section 2) state the same correspondence for two algorithms.
The F version of Iman and Davenport
Demšar (2006) recommends a transformation of $\chi^2_F$ due to Iman and Davenport (1980), who, as Demšar reports, found Friedman's statistic "undesirably conservative":
$$F_F = \frac{(N - 1)\chi^2_F}{N(k - 1) - \chi^2_F},$$
referred to the F distribution with $k - 1$ and $(k - 1)(N - 1)$ degrees of freedom. The formula looks arbitrary, but it is the ordinary analysis of variance applied to the ranks.
Theorem 3 (the F version is the analysis of variance of the ranks). Treat the ranks $r_{ij}$ as the responses of a two-way layout with systems and tasks as factors, one observation per cell and no interaction. The F statistic for systems equals $(N - 1)Q/(N(k - 1) - Q)$, with $Q$ the tie-corrected statistic (equal to $\chi^2_F$ when there are no ties).
Proof. The grand mean of the ranks is $(k + 1)/2$, and so is every task's mean, because every task's ranks add up to $k(k+1)/2$. So the sum of squares between tasks is zero, and the total sum of squares $SS_{\text{tot}} = \sum_{i,j}(r_{ij} - \frac{k+1}{2})^2$ splits into the sum of squares for systems, $SS_{\text{sys}} = N\sum_j (R_j - \frac{k+1}{2})^2$, and the residual $SS_{\text{tot}} - SS_{\text{sys}}$. The F statistic is
$$F = \frac{SS_{\text{sys}}/(k - 1)}{(SS_{\text{tot}} - SS_{\text{sys}})/\big((k - 1)(N - 1)\big)} = \frac{(N - 1)\,SS_{\text{sys}}}{SS_{\text{tot}} - SS_{\text{sys}}}.$$
Since $\sum_j (T_j - N\frac{k+1}{2})^2 = N\cdot SS_{\text{sys}}$, the definition of $Q$ reads $Q = (k - 1)N\,SS_{\text{sys}}/SS_{\text{tot}}$, so $SS_{\text{sys}}/SS_{\text{tot}} = Q/(N(k - 1))$. Dividing numerator and denominator of $F$ by $SS_{\text{tot}}$ gives $F = (N - 1)Q/(N(k - 1) - Q)$. $\blacksquare$
The two statistics are increasing functions of each other, so the exact permutation test of Theorem 1 is the same whichever is used. They differ only in the approximation used for the p-value. Two-Way Analysis of Variance proves the partition of sums of squares in a two-way layout; here the layout's task factor carries no variation at all.
Example (exact and simulated sizes). How close are the nominal 5% levels? For small tables the script enumerated every ranking pattern; for larger ones it drew 20,000 tables of random rankings for each of 30 seeds.
| $k$ | $N$ | Size of the chi-squared test | Size of the F test | Method |
|---|---|---|---|---|
| 3 | 5 | 0.0394 | 0.0394 | exact |
| 3 | 10 | 0.0456 | 0.0456 | exact |
| 4 | 5 | 0.0336 | 0.0666 | exact |
| 4 | 14 | 0.0443 | 0.0521 | simulated, median |
| 7 | 57 | 0.0490 | 0.0504 | simulated, median |
The chi-squared version is conservative in every row, as Iman and Davenport's verdict says. The F version is closer to 5% when the table is not tiny, but it can exceed the level: at $k = 4$, $N = 5$ it rejects 6.66% of the time. With three systems the two tests reject exactly the same patterns at these sizes, because the null distribution is so discrete that no pattern falls between the two cut-offs. At the running example's size both are within a few tenths of a percentage point of 5% (interquartile ranges 0.0479 to 0.0496 and 0.0497 to 0.0514).
The seven models
For the seven models, 37 of the 57 subjects contain at least one tie in accuracy. The uncorrected statistic is $\chi^2_F = 39.09$ and the tie-corrected $Q = 39.89$, against 12.59 for the 5% point of the chi-squared distribution with 6 degrees of freedom: $p < 0.0001$. The F version, computed from the tie-corrected $Q$ as Theorem 3 allows, is $F_F = 7.39$ on 6 and 336 degrees of freedom, also $p < 0.0001$. The exact test of Theorem 1 agrees: in each of 30 runs of 10,000 random within-subject permutations, not one permutation gave a statistic as large as the observed one, so every run's Monte Carlo p-value is $1/10{,}001$, the smallest it can be.
The mean ranks span 2.00 places, from Mixtral 8x7B at 2.78 to Claude Instant 1.2 at 4.78. Friedman's test says that not all seven are exchangeable across subjects. It does not say which differ.
Which systems differ? Nemenyi's critical difference
Comparing all pairs needs a threshold that controls the chance of any false difference among the $k(k-1)/2$ pairs. Nemenyi (1963) gave one for mean ranks, and Demšar (2006) presents it as the counterpart of Tukey's test after an analysis of variance: two systems differ significantly if their mean ranks differ by at least the critical difference
$$CD = q_\alpha\sqrt{\frac{k(k + 1)}{6N}},$$
where $q_\alpha$ is the upper $\alpha$ point of the studentized range divided by $\sqrt2$.
The square root is the standard error of a difference of mean ranks. By Lemma 1, $\operatorname{Var}(r_j - r_l) = 2\cdot\frac{k^2 - 1}{12} + 2\cdot\frac{k + 1}{12} = \frac{k(k + 1)}{6}$ on one task, and averaging over $N$ independent tasks divides by $N$. The constant $q_\alpha$ comes from the joint behavior of all the differences.
Theorem 4 (Nemenyi's critical difference). Without ties, under the null hypothesis, as $N \to \infty$ the probability that some pair of mean ranks differs by at least $CD$ tends to $\alpha$, when $q_\alpha\sqrt2$ is the upper $\alpha$ point of the range of $k$ independent standard normal variables.
Proof. Let $\mathbf{Z}$ be as in the proof of Theorem 2, so that $Z_j = (R_j - \frac{k+1}{2})\sqrt{12N/(k(k+1))}$, and $\mathbf{Z}$ converges in distribution to $P\mathbf{Y}$. The coordinates of $P\mathbf{Y} = \mathbf{Y} - \bar Y\,(1, \dots, 1)$ are $Y_j - \bar Y$, so their differences are $Y_j - Y_l$, and the largest difference is the range of $Y_1, \dots, Y_k$. The function $g(\mathbf{z}) = \max_{j, l}\lvert z_j - z_l\rvert$ is continuous, so by the criterion by bounded continuous functions used in Step 3 of Pearson's theorem, $g(\mathbf{Z})$ converges in distribution to the range of $\mathbf{Y}$. That range has a continuous distribution, so $P(g(\mathbf{Z}) \ge c) \to P(\text{range} \ge c)$ for every $c$. Finally, $\max\lvert R_j - R_l\rvert \ge CD$ is the same event as $g(\mathbf{Z}) \ge q_\alpha\sqrt{2}$, because $CD\sqrt{12N/(k(k+1))} = q_\alpha\sqrt{2}$. $\blacksquare$
The range of $k$ independent standard normal variables is the studentized range of Multiple Comparisons and the Bonferroni Correction with infinitely many degrees of freedom for the denominator, so $q_\alpha$ is that distribution's quantile divided by $\sqrt 2$. The script recomputes Demšar's Table 5(a) from it: all 18 entries (2 to 10 systems, at 0.05 and 0.10) agree to within one unit in the third decimal, and three of them (2.343, 2.949, 2.459) are off by that one unit. For seven systems $q_{0.05} = 2.948$.
Example (the family-wise error rate at finite size). The script drew 20,000 tables of random rankings for each of 30 seeds and counted tables in which some pair of mean ranks differed by at least $CD$. At $k = 7$, $N = 57$ the median rate was 0.0453 (interquartile range 0.0442 to 0.0461), and at $k = 4$, $N = 14$ it was 0.0468 (0.0463 to 0.0477): slightly below 5%, as with Friedman's chi-squared version.
Example (the seven models). With $k = 7$ and $N = 57$ the standard error of a mean-rank difference is $\sqrt{56/342} = 0.405$, and $CD = 2.948 \times 0.405 = 1.19$ at the 5% level (1.09 at 10%). Five pairs differ by more: Mixtral 8x7B from GPT-3.5 Turbo, Qwen1.5 14B and Claude Instant 1.2, and Gemini 1.0 Pro from Qwen1.5 14B and Claude Instant 1.2. Mixtral 8x7B and text-bison differ by 1.19 in mean rank but by just less than the critical difference, which is why they are joined in the figure.
Demšar (2006, Section 3.2.4) reads overlapping groups as he reads his own example: the data are not sufficient to decide where the middle systems belong, which is not the same as saying they belong to both groups.
Comparisons with one control. When the question is whether a new system beats each of several existing ones, only $k - 1$ comparisons are made. Demšar recommends computing $z = (R_i - R_j)/\sqrt{k(k+1)/(6N)}$ for each and applying the Bonferroni correction (Dunn's test), or better Holm's step-down procedure, whose error control is proved in Multiple Comparisons and the Bonferroni Correction. The Bonferroni–Dunn critical values in Demšar's Table 5(b) are normal quantiles at $\alpha/(2(k-1))$; the script reproduces them, and finds one misprint: for nine classifiers at 0.05 the table reads 2.724, where the quantile is 2.734.
Mean ranks depend on the pool
Benavoli, Corani and Mangili (2016) showed that Nemenyi's test, and every test built on mean ranks, has a property most users would not accept: the verdict on systems A and B depends on which other systems were included. They note that earlier authors had pointed this out and that most of the literature ignores it. Their recommendation is to compare pairs with tests that use only the two systems' scores, the sign test or the signed-rank test, with a correction for multiple comparisons.
The mechanism takes one line. Without ties, on a task where A beats B, the rank difference $r_B - r_A$ is 1 plus the number of other systems scoring between them. So
$$R_B - R_A = \frac{1}{N}\sum_i \pm\,(1 + b_i),$$
with the sign $+$ where A wins, and $b_i$ the number of other systems between them on task $i$. With only A and B present every $b_i$ is 0, and the mean-rank difference is $(W - L)/N$, the sign test's statistic. Adding systems weights each task by how many of them land between A and B there, and also raises the standard error $\sqrt{k(k+1)/(6N)}$. Neither change says anything about A and B. Ties add halves in the same way.
The GPT-4 Turbo (1106 preview) and Llama 3 70B example above is this mechanism at work: 34 wins against 18 losses, but more of the other 26 models fell between the two on the subjects GPT-4 Turbo (1106 preview) lost, so its mean rank is worse ($z = -0.10$ in the pool of 28).
Example (one pair, many pools). Mixtral 8x7B beats text-bison in 38 subjects and loses in 16; alone, the signed-rank test gives $p = 0.0007$. The script computed Nemenyi's verdict on this one pair in every pool made by adding other models from the 28:
| Models in the pool | Pools | Nemenyi significant at 5% | Range of the pair's $z$ |
|---|---|---|---|
| 3 | 26 | 12 | 1.87 to 3.18 |
| 4 | 325 | 55 | 1.38 to 3.30 |
| 5 | 2,600 | 115 | 1.10 to 3.35 |
| 7 | 65,780 | 75 | 0.80 to 3.27 |
In the seven-model pool of the running example, the pair's $z$ is 2.9482, a hair below the threshold of 2.9483. In the pool of all 28 it is 1.38. The scores of Mixtral 8x7B and text-bison are the same in every row of the table.
Example (low power from the pool). Benavoli et al. (2016, Section 4.2) simulate two systems A and B whose scores on 20 tasks are normal with means 0 and 1.5 and standard deviation 1, in a pool with three far better systems (means 5, 6 and 7). They report power 0.94 for the sign test and 0.046 for the mean-ranks test at the 5% level. The script repeats the simulation (10,000 tables for each of 30 seeds) and finds 0.942 and 0.046. The three strong systems almost never fall between A and B: the weakest of them scores below B with probability 0.0067 per task, and in 14% of the simulated tables (median over the 30 seeds) at least one of them falls between A and B on at least one task. When none does, the mean-rank difference is the sign test's $(W - L)/20$, but the standard error used for it is $\sqrt5$ times larger, because it assumes five systems ranked at random. That gives a closed form. B beats A on a task with probability $\Phi(1.5/\sqrt2) = 0.856$ per task, so the sign test's power is $P(W \ge 15) + P(W \le 5) = 0.942$ for $W$ binomial with 20 trials. Without crossings the mean-ranks test needs $\lvert W - L\rvert/20 \ge 1.96\sqrt{30/120} = 0.98$, which means one system winning all 20 tasks: power $0.856^{20} + 0.144^{20}$, in closed form 0.044. The simulated 0.046 is a little higher because of the rare crossings.
What to do instead. Test each pair with the signed-rank test on the two systems' scores alone, and control the family-wise error rate with Holm's procedure over the 21 pairs. For the seven models this also rejects 5 pairs, but not the same 5: it separates Mixtral 8x7B from every one of the other six except Gemini 1.0 Pro, and it does not separate Gemini 1.0 Pro from anything. The smallest p-value, 0.000006, is far below Holm's first threshold $0.05/21 = 0.0024$. The two procedures answer different questions. Nemenyi's asks whether mean ranks among these seven differ more than random rankings allow; the pairwise tests ask whether one model beats another across subjects, a question whose answer does not change when a model is added to the study.
Twelve retrieval runs on Cranfield
The same tools apply to retrieval systems scored on queries. Comparing Ranking Models and Comparing Systems with Significance Tests compare retrieval models two at a time by paired tests on Cranfield's queries. Demšar (2006, Section 2.1) credits Hull (1994), "to the best of our knowledge", with the first use of non-parametric tests for comparing classifiers in information retrieval. The twelve runs of the course's evaluation experiments (BM25 with several settings, TF-IDF, the binary independence model, query likelihood with Dirichlet smoothing, and two deliberately weak runs) give $k = 12$ systems on $N = 225$ queries, scored by average precision.
Ties occur: 34 of the 225 queries have at least one tie in average precision among the twelve runs. They are not mainly ties at the extremes. Those 34 queries hold 58 groups of tied runs, of which 5 tie at an average precision of 1 and 4 at 0; the rest tie at intermediate values. The uncorrected statistic is 890.5 and the tie-corrected $Q = 913.0$; the F version computed from $Q$ is $F_F = 130.9$. Every test rejects at any conventional level. With $q_{0.05} = 3.268$ for twelve systems, $CD = 1.11$.
| Run | Mean rank | Mean average precision |
|---|---|---|
| BM25, $k_1 = 3$ | 3.90 | 0.311 |
| BM25 | 4.36 | 0.307 |
| BM25, stop words kept | 4.57 | 0.306 |
| TF-IDF | 5.28 | 0.294 |
| BM25 unstemmed | 5.44 | 0.282 |
| BM25, $b = 0$ | 6.22 | 0.271 |
| Query likelihood | 6.27 | 0.277 |
| TF-IDF unstemmed | 6.29 | 0.274 |
| Query likelihood unstemmed | 7.03 | 0.255 |
| Binary independence model | 8.23 | 0.220 |
| Coordination level | 9.01 | 0.172 |
| Raw term frequency | 11.40 | 0.029 |
Mean average precision and mean rank put 2 pairs in different orders, both involving BM25 with $b = 0$, which is ahead of query likelihood and unstemmed TF-IDF in mean rank and behind them in mean average precision. BM25 with $k_1 = 3$ and BM25 with the default settings differ by 0.46 in mean rank, well inside the critical difference, while the signed-rank test on the two runs alone gives $p = 0.0004$. With 225 queries and twelve systems, the critical difference pays for 66 simultaneous comparisons among runs that a study of BM25's parameters would not compare.
What the tasks represent
The tests of this article treat tasks as independent draws from a population of tasks, and treat each task's scores as exact. Neither is quite true of MMLU's subjects. The subjects were chosen by the benchmark's authors, not sampled, and several are close relatives (high school and college versions of the same field), so a conclusion about "subjects of this kind" is a conclusion about a population that exists only by analogy. The per-subject accuracies have sampling error of their own: with 100 questions and accuracy near 0.7, the binomial standard error is about $\sqrt{0.7 \times 0.3/100} = 0.046$, larger than many of the differences that decide ranks. The null hypothesis of exchangeability still holds when the models are equal, so the tests keep their size, but ranks decided by question-level noise dilute the power. Demšar (2006, Section 3.2.3) notes that he knew of no test that could use the variance within each data set when the measurements come from overlapping training samples. For benchmarks, the question-level analyses of Standard Errors for Benchmark Scores and Clustered Standard Errors are the complement: they generalize over questions within the benchmark instead of over tasks.
What is proved, what is cited, what the experiments show
Proved here. The moments of a random ranking, with and without ties; the exact null distribution of Friedman's statistic and its mean; its chi-squared limit without ties, by reduction to the proof of Pearson's theorem; the reduction to the sign test for two systems; the identity between the Iman–Davenport statistic and the analysis of variance of the ranks; the standard error of a mean-rank difference and Nemenyi's critical difference as a limit; the decomposition of a mean-rank difference that makes it depend on the pool.
Cited. The multivariate central limit theorem and the Cramér–Wold device, through The Chi-Square Goodness-of-Fit Test; the limit with ties (not proved); Holm's procedure, through the course page; the history and recommendations of Demšar (2006), including his Tables 5 and 6; Iman and Davenport's verdict as Demšar reports it; Benavoli, Corani and Mangili's (2016) examples and recommendation.
What the experiments show. The exact sizes are computed by enumeration; the simulated sizes, family-wise error rates and the repetition of Benavoli et al.'s simulation are seeded experiments with 30 runs. The pool table and the Cranfield results describe these data and these systems.
Worked problems
These problems were written for this article. Problems 1 and 2 recompute published examples; problem 3 is a small exact case. The script tools/experiments/statistics/comparing-systems-across-tasks.py recomputes every number.
Problem 1 (Demšar's example). Demšar (2006, Table 6) ranks four variants of the C4.5 decision tree on 14 data sets by AUC. Their mean ranks are 3.143 (C4.5), 2.000 (with $m$ tuned), 2.893 (with $cf$ tuned) and 1.964 (with both tuned). Compute Friedman's statistic, the Iman–Davenport statistic and Nemenyi's critical differences, and compare the tuned variants with C4.5 as a control.
Solution. $\chi^2_F = 9.28$, $F_F = 3.69$ with $p = 0.020$, and $CD = 1.25$ at 5%. With $k = 4$ and $N = 14$,
$$\chi^2_F = \frac{12 \times 14}{4 \times 5}\left[3.143^2 + 2.000^2 + 2.893^2 + 1.964^2 - \frac{4 \times 5^2}{4}\right] = 9.28,$$
and $F_F = 13 \times 9.28/(14 \times 3 - 9.28) = 3.69$, above the 5% point of the F distribution with 3 and 39 degrees of freedom, 2.85. So the four variants are not all exchangeable. Demšar computed $\chi^2_F$ without the tie correction; the table has ties on three data sets and a four-way tie on one, and the corrected statistic is 10.23 (with $F = 4.19$). Nemenyi's critical difference is $2.569\sqrt{20/84} = 1.25$ at 5% and $2.291\sqrt{20/84} = 1.12$ at 10%. The largest difference, $3.143 - 1.964 = 1.179$, is below 1.25, so no pair is separated at 5%; at 10% C4.5 is separated from the two variants with $m$ tuned. As a control comparison, the standard error is $\sqrt{20/84} = 0.488$, giving $z = 2.415$ ($p = 0.016$) for C4.5 with both tuned, 2.342 ($p = 0.019$) for C4.5 with $m$ tuned and 0.512 ($p = 0.608$) for C4.5 with $cf$ tuned. Holm's procedure compares the smallest p-value with $0.05/3 = 0.017$ (reject), the next with $0.05/2 = 0.025$ (reject) and the last with 0.05 (retain). Demšar's text gives 0.607 for the last p-value. The unrounded $z = 0.5123$ gives 0.608, and the rounded value $z = 0.512$ gives 0.609.
Problem 2 (Benavoli, Corani and Mangili's Example 1). Five algorithms are scored on 20 data sets. On the first ten, the scores are A 50, B 80, C 55, D 60, E 65; on the last ten, A 80, B 50, C 45, D 85, E 90. Compare A and B by the sign test and by the mean-ranks test with the Bonferroni correction for all ten pairs.
Solution. The sign test finds nothing ($p = 1$); the mean-ranks test declares A and B different. A beats B on ten data sets and loses on ten, the most balanced record possible. With rank 1 for the best, A's ranks are 5 on the first ten data sets and 3 on the last ten, so $R_A = 4.0$; B's are 1 and 4, so $R_B = 2.5$. (C, D and E have mean ranks 4.5, 2.5 and 1.5.) Friedman's statistic is $\frac{12 \times 20}{5 \times 6}\left[4^2 + 2.5^2 + 4.5^2 + 2.5^2 + 1.5^2 - 45\right] = 8 \times 6 = 48$, with $p = 0.0000000009$ on 4 degrees of freedom. The Bonferroni-corrected critical value for ten two-sided comparisons is the upper $0.05/20$ point of the standard normal, $z^* = 2.807$, and the critical difference is $2.807\sqrt{30/120} = 1.40$. The mean-rank difference, 1.5, exceeds it. The difference comes entirely from the other three algorithms. C, D and E all fall between B and A on the first ten data sets and none of them does on the last ten, so on the first ten $r_A - r_B = 1 + 3 = 4$ and on the last ten $r_B - r_A = 1$, and the mean-rank difference is $(10 \times 4 - 10 \times 1)/20 = 1.5$.
Problem 3 (ties by hand). Three systems score $(0.9, 0.9, 0.5)$, $(0.8, 0.7, 0.6)$, $(0.7, 0.8, 0.6)$ and $(0.6, 0.5, 0.4)$ on four tasks. Compute the uncorrected and tie-corrected Friedman statistics.
Solution. The uncorrected statistic is 6.125 and the corrected 6.533. The ranks (1 = best) are $(1.5, 1.5, 3)$, $(1, 2, 3)$, $(2, 1, 3)$ and $(1, 2, 3)$, so the rank sums are 5.5, 6.5 and 12 and the mean ranks 1.375, 1.625 and 3.000. The deviations of the rank sums from $N(k+1)/2 = 8$ are $-2.5$, $-1.5$ and 4, with squares adding to $6.25 + 2.25 + 16 = 24.5$. Without the correction the denominator is $Nk(k^2-1)/12 = 4 \times 3 \times 8/12 = 8$, and $\chi^2_F = 2 \times 24.5/8 = 6.125$. With it, the denominator is the actual sum of squared deviations of the ranks from 2: the first task gives $0.25 + 0.25 + 1 = 1.5$ and each other task 2, a total of 7.50, so $Q = 2 \times 24.5/7.5 = 6.533$. The tie on the first task removed spread that a random ranking of three distinct values would have had, and the correction divides by the spread that is actually available.
Summary
| Quantity | Formula |
|---|---|
| Mean rank | $R_j = \frac1N\sum_i r_{ij}$, rank 1 = best, midranks for ties |
| Moments of a random ranking | mean $\frac{k+1}{2}$, variance $\frac{k^2-1}{12}$, covariance $-\frac{k+1}{12}$ |
| Friedman | $\chi^2_F = \frac{12N}{k(k+1)}\sum_j (R_j - \frac{k+1}{2})^2$, approximately $\chi^2_{k-1}$ |
| Tie-corrected | $Q = (k-1)\sum_j (T_j - N\frac{k+1}{2})^2 \big/ \sum_{i,j}(r_{ij} - \frac{k+1}{2})^2$ |
| Iman–Davenport | $F_F = (N-1)\chi^2_F/(N(k-1) - \chi^2_F)$ on $k-1$ and $(k-1)(N-1)$ degrees of freedom |
| Two systems | $Q = (W - L)^2/(W + L)$, the sign test |
| Nemenyi | $CD = q_\alpha\sqrt{k(k+1)/(6N)}$, $q_\alpha$ = studentized range quantile with infinite degrees of freedom over $\sqrt2$ |
| Pairwise alternative | signed-rank or sign test per pair, Holm's correction |
What we have learned
Scores on different tasks need not share a scale, so averages over tasks can order the same systems in more than one way. Ranks within each task remove the scale. Friedman's statistic measures how far the mean ranks spread beyond what random rankings produce; its exact distribution comes from permuting ranks within tasks, its chi-squared limit is Pearson's theorem for equally likely categories, and the Iman–Davenport F is the analysis of variance of the same ranks. On the seven MMLU models the spread is far beyond chance. Nemenyi's critical difference then separates 5 of 21 pairs, but mean ranks import information from the other systems in the pool: a pair's verdict changes when models are added, and the head-to-head record of two systems can contradict their mean ranks. Pairwise signed-rank tests with Holm's correction depend only on the two systems compared.
These tests take each task's score as exact and generalize over tasks. The unit's other articles work at the level of questions: Paired Comparisons of Models compares two models on the same questions, and Rating Models from Pairwise Comparisons rates models from preferences between their answers. The topic page Statistics of Model Evaluation lists them all.
References
- Benavoli, A., Corani, G., and Mangili, F. (2016). Should we really use post-hoc tests based on mean-ranks? Journal of Machine Learning Research, 17(5), 1–10. record
- Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7(1), 1–30. record
- Friedman, M. (1937). The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 32(200), 675–701. record
- Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J. (2021). Measuring massive multitask language understanding. International Conference on Learning Representations. arXiv:2009.03300. record · 7 pages
- Hull, D. A. (1994). Information Retrieval Using Statistical Classification. PhD thesis, Stanford University. (Cited as Demšar, 2006, describes it.) record
- Iman, R. L., and Davenport, J. M. (1980). Approximations of the critical region of the Friedman statistic. Communications in Statistics: Theory and Methods, 9(6), 571–595. record
- Liang, P., Bommasani, R., Lee, T., Tsipras, D., Soylu, D., Yasunaga, M., et al. (2022). Holistic evaluation of language models. arXiv:2211.09110. record · 6 pages
- Nemenyi, P. B. (1963). Distribution-Free Multiple Comparisons. PhD thesis, Princeton University. (Cited as Demšar, 2006, and Benavoli et al., 2016, describe it.) record