Practical Certification of Binary-Score Leaderboards

Leaderboards report orderings between models, rarely with a guarantee that the reported directions are right. We study certification of the population ranking of a fixed set of models scored correct or incorrect on shared, independently sampled items. We derive instance-specific lower bounds on the number of items any procedure needs to certify the ranking: one for a single comparison, given by an exact finite sum, and a mixture bound that prices several comparisons at once without assumptions on their dependence. We then show that testing all $K$ pairs of $M$ models with McNemar's test at $\delta /(M-1)$ in place of $\delta /K$, and releasing the order only when all pass, certifies a complete ranking with error at most $\delta$. On eighteen configurations from five benchmark families, resampling each benchmark's own items, this certificate needs $1.61$ to $1.81$ times the larger lower bound to certify the complete ranking correctly $95\%$ of the time, and McNemar's test on the hardest single comparison alone is within $2\%$ of its bound.