Stopping Human Annotation Early: Anytime-Valid Confidence Sequences for Rank Agreement

Automatic metrics and LLM judges are routinely chosen by checking which one's scores best agree in ordering with human ratings. The usual measure is a rank correlation such as Kendall's tau, which asks, over all pairs of items, how often the metric and the humans order the pair the same way. Human labels are expensive and arrive in batches. Practitioners therefore look at the running correlation, decide it is "clearly" better, and stop. That habit invalidates every standard confidence interval. The problem is sharpest in the case that matters most: two strong judges that agree with each other on most pairs, so their correlation gap is small but also very stable.

We propose a confidence sequence for the difference in Kendall's tau between two judges, measured against human labels. A confidence sequence is an interval that stays valid at every sample size simultaneously, so it may be checked after every new label. Ours has two further properties. It shrinks according to the observed variance of the pairwise disagreement signal rather than its worst-case range. It also uses all pairs of labeled items rather than a disjoint subset. The practical payoff is a stopping rule: annotators can stop once the interval excludes zero, with a guaranteed error rate. When two judges mostly agree, it should stop substantially earlier than any range-based or pair-discarding method.

Core Claim

Consider human labels $y$ and two judges' scores $a$ and $b$ on each item. The paired comparison statistic is an order-2 U-statistic: an average of a kernel over all pairs of items. Its kernel is $h(Z_i,Z_j)=\mathrm{sign}(y_i-y_j)\,[\mathrm{sign}(a_i-a_j)-\mathrm{sign}(b_i-b_j)]$, with values in $[-2,2]$. Its mean $\theta$ is the gap $\tau_a-\tau_b$. When the judges agree on most pairs, $h$ is zero almost everywhere, so its variance is far below the range bound of 4. This is exactly the regime where variance-adaptive (empirical Bernstein) bounds beat range-based (Hoeffding) bounds.

The difficulty is combining three things that no existing result delivers together: U-statistic structure, empirical variance, and time-uniform validity. Empirical Bernstein Inequalities for U-Statistics handles the first two at a fixed sample size. It shows much narrower intervals than Hoeffding on UCI Banana for bipartite ranking risk. However, it uses a symmetric split of the error probability. Sharp Matrix Empirical Bernstein Inequalities proves that such a symmetric split is provably loose. Martinez-Taboada and Ramdas give sharp anytime-valid empirical Bernstein bounds built from nonnegative supermartingales, which are betting-style processes whose values stay small under the null. Their bounds cover sums of individual bounded variables, not pairwise averages. We claim that a supermartingale can be built for the gradually accumulating pairwise statistic. That supermartingale's width should be governed, to first order, by the variance of the single-item projection $h_1(z)=\mathbb{E}[h(z,Z)]$. The estimation penalty and the pairwise-dependence correction should vanish at a faster rate, mirroring the vanishing-penalty principle of Maurer and Pontil.

Research Program

The starting point is the Hoeffding decomposition. It splits $U_t-\theta$ into a linear part, $\frac{2}{t}\sum_{i\le t}(h_1(Z_i)-\theta)$, and a degenerate part built from $h_2(z,z')=h(z,z')-h_1(z)-h_1(z')+\theta$. The linear part is a sum of independent bounded terms. The degenerate part, $\sum_{s<t}h_2(Z_s,Z_t)$, is a forward martingale in $t$, because each new term has conditional mean zero given the past.

The construction has three components. First, we run an empirical Bernstein supermartingale on the linear part. Since $h_1$ is unknown, we use the predictable plug-in estimate $\hat h_1(Z_t)=\frac{1}{t-1}\sum_{s<t}h(Z_t,Z_s)$, in the style of the predictable plug-in sequences of Martinez-Taboada and Ramdas. The plug-in introduces a drift equal to the running average of past projections. We treat that drift as an additional averaged martingale and control it within the same process. Second, we bound the degenerate part with its own time-uniform maximal inequality. Its size should scale like $\sqrt{\log t}/t$ relative to the target, which is lower order than the $1/\sqrt{t}$ leading term. Third, we allocate the error probability unevenly between the pieces, following the imbalanced split of Wang and Ramdas. The target result is a width of the form

$$ |U_t-\theta|\;\le\;\sqrt{\frac{8\,\hat V_t\,\log(\ell(t)/\delta)}{t}}\;+\;O\!\left(\frac{\log(\ell(t)/\delta)}{t}\right), $$

valid for all $t$ simultaneously with probability at least $1-\delta$. Here $\hat V_t$ is the running empirical variance of the projection estimates, $\ell(t)$ is an iterated-logarithm-type factor from the time-uniform construction, and the constant 8 comes from the factor of 2 in the linear term of the decomposition. The theoretical deliverable is this inequality, with a first-order constant matching the oracle CLT width up to the time-uniform factor.

The algorithmic deliverable is an update of $\hat h_1(Z_t)$ and $\hat V_t$ in polylogarithmic time per new label. Doing so requires counting, among past items, how many are concordant with the new one on both the human and judge axes. That count is a two-dimensional dominance query, answerable with a Fenwick tree over sorted ranks. This extends the sorting trick of Peel et al., which relied on binary labels, to continuous ranks with ties. It also sidesteps the naive fourth-order cost of U-statistic variance.

Baselines

The naive reference point is what practitioners actually do. They report the running point estimate, as the SemEval-2024 relatedness systems do: BITS Pilani reports Spearman 0.832 on English and HausaNLP reports 0.82 for an unsupervised model. They then stop annotating when one judge looks ahead, or they attach a fixed-sample normal-approximation interval and check it repeatedly. We run this peeking protocol on the same streams to measure its realized false-selection rate. Beating it means holding the nominal error rate where it fails. No reported result was found on Lacuna for repeated-look coverage of rank-correlation intervals. The closest evidence is fixed-sample: ROCKET reports that Gaussian-based intervals for rank-derived quantities dropped to 12% to 36% coverage at a nominal 95% on heavy-tailed data.

The range-based anytime baseline is a Hoeffding-style confidence sequence on the same U-statistic. It uses only the kernel range, so it is valid but blind to low disagreement variance.

The strongest existing fixed-sample method is the U-statistic empirical Bernstein bound of Peel et al.. We make it anytime-valid by a union bound over a geometric grid of sample sizes. Peel et al. report only graphical interval-width comparisons against Hoeffding on UCI Banana; no numeric table was found on Lacuna.

The strongest anytime method is the betting-based empirical Bernstein confidence sequence of Martinez-Taboada and Ramdas, applied to kernel values on disjoint consecutive pairs. Those values are independent, so the method applies directly. It is also the key ablation, since it isolates our contribution of using all pairs. A related version applies the same confidence sequence to within-block U-statistics over blocks of size $m$. This echoes the block partitioning of Frey et al..

A second ablation keeps our all-pairs construction but uses a symmetric error split. This isolates the effect of the imbalanced allocation.

All methods see identical label streams in identical order, use $\delta=0.05$, and receive the same small grid of tuning choices (betting-fraction truncation, block size). Tuning happens on held-out synthetic streams only. Winning means strictly smaller median stopping time and width at every horizon, with realized time-uniform miscoverage at or below 5%.

Why not just…?

Why not just bootstrap the tau difference? For a single analysis at a fixed sample size, the paired bootstrap will likely give intervals as tight as ours or tighter, and we do not claim otherwise. We will report it in the fixed-sample comparison. Its weakness is sequential: bootstrap intervals are asymptotic and cannot be checked after every batch without an uncontrolled error rate, as Martinez-Taboada and Ramdas note for non-supermartingale intervals. Recomputing it after each of thousands of labels on a stream the size of the New Yorker caption data is also costly. The peeking experiment below measures its realized false-selection rate directly.

Why not just pair up disjoint items and use an existing empirical Bernstein confidence sequence? This is the most serious competitor, because it is valid immediately. Its cost is statistical efficiency. With $n$ items it uses $n/2$ independent kernel values, whose variance is $\mathrm{Var}(h)$. The all-pairs statistic's first-order variance is $4\mathrm{Var}(h_1)/n$. For plain Kendall's tau under independence these are 1 and $4/9$, so disjoint pairing needs roughly 2.25 times as many labels for the same width. If on real judge-disagreement kernels the measured ratio $\mathrm{Var}(h)/(4\mathrm{Var}(h_1))$ is close to 1, the idea loses its point. We will report this ratio on every dataset before anything else.

Why not just use blocks with a full U-statistic inside each? Blocks recover efficiency as block size grows, but they can stop only at block boundaries. Frey et al. also show that block constructions face rate limits when converted to high-probability statements. We sweep block size to see whether a well-chosen block matches the all-pairs sequence. If it does, the block method is the recommendation and the new theory is only a unifying explanation.

Proposed Experiments

The first testbed is the LLM-judge rubric data of What makes the whole?: ELLIPSE, TL;DR, USR and ASAP++. That paper reports Kendall's tau between LLM and human trait orderings of only −0.07 to 0.20, and per-trait Spearman gaps such as roughly 0.55 for coverage versus 0.24 for coherence on TL;DR. These are precisely the small, decision-relevant gaps where annotation budgets matter. Pairs of judges become the $a$ and $b$ in our kernel. The second testbed is SemEval-2024 Task 1, where competing embedding models, for example the ones compared by HausaNLP, are ranked against human relatedness scores. The third is the New Yorker caption ranking data from Humor in AI. Its 2.2 million captions test whether per-label update cost stays practical, and compare an LLM judge's scores with aggregated human funniness ratings.

To obtain ground truth, each full dataset is treated as the population. We draw thousands of random label orderings, with and without replacement, and compute the true $\theta$ from the full data. Synthetic streams with controlled judge agreement and heavy-tailed score noise complete the grid.

The measured quantities are four: realized time-uniform miscoverage, width as a function of labels seen, labels needed until the interval excludes zero, and wall-clock update cost. The decisive checks are three. First, our sequence must keep miscoverage at or below 5% while the peeking normal interval does not. Second, its stopping time must beat the disjoint-pair confidence sequence by a margin consistent with the measured variance ratio. Third, its width should approach the oracle CLT width as labels accumulate, with excess over the oracle shrinking at large sample sizes. For reference, Wang and Ramdas report 10.5% excess over the oracle at $n=1{,}000$ and 2.2% at $n=10{,}000$ for their matrix supermartingale bound. That is the level of sharpness we aim to approach for the pairwise case. Failure on the second check, with the efficiency ratio near 1, would show that the pairwise structure buys nothing for judge comparison. We would report that result as a negative finding.