Anytime-Valid Class-Prior Tracking Under Delayed Labels

Deployed classifiers often fail because class proportions drift. Readmission rates rise in winter, a news category grows, a coding rule changes. A common fix is to estimate the current class mix from the model's own predictions on unlabeled incoming data, then shift the classifier's decision thresholds toward it. In practice nobody can say how fast that estimate should move. A slow moving average misses sudden shocks. A fast one chases noise and can collapse onto a few classes. The reported gains of these trackers are usually measured with the decay rate already tuned on labels from the very stream being evaluated, which quietly borrows information from the future. We propose to run a small bank of class-prior trackers in parallel, together with a "no correction" option. A running statistical test, fed by true labels as they arrive late, decides which tracker to trust. The test controls false alarms however long the stream runs and however often it is checked. It also never uses a label before that label would actually have arrived.

The opportunity lies where two results meet. Anytime-Valid Confirmation of Label-Shift Corrections turns the log-loss gap between a corrected and a base model into a test martingale. This is a running wealth process whose large values certify, with guaranteed error control under optional stopping, that the correction helps. That paper requires the correction to be fixed before the stream starts. On Pitfalls of Test-Time Adaptation shows that online adaptation is extremely sensitive to hyperparameters (accuracy drops of over 60% from small deviations) and has no label-free model-selection procedure. We show that the fixed-weight restriction can be relaxed to predictable weights, meaning corrections computed only from information available before each label is revealed. That relaxation is exactly what an online prior tracker produces, so learning and verifying the correction on the same stream become compatible.

Core Claim

Model the deployment stream honestly. At time $t$ the model sees an unlabeled input $x_t$ and outputs a corrected prediction. The true label $y_t$ arrives only at time $t+d$, as in clinical outcomes or delayed fraud labels. Each tracker $k$ maintains a class-prior estimate $\hat p^{(k)}_t$ built from unlabeled inputs up to $t$ and from labels that have already arrived. It applies the standard prior-ratio reweighting of Lipton et al., which is equivalent to logit adjustment. Let $\ell^{0}_s$ and $\ell^{k}_s$ be the clipped log-losses of the base and $k$-th corrected predictions on example $s$. The test statistic, updated in the order labels arrive, is

$$E^{(k)}_t = \prod_{s:\, s+d \le t} \left(1 + \lambda^{(k)}_s \,(\ell^{0}_s - \ell^{k}_s)\right),$$

where $\lambda^{(k)}_s \in [0, 1/c)$ is a betting fraction and $c$ bounds the absolute loss gap after clipping. Both the fraction and the correction applied to example $s$ are fixed before $y_s$ is revealed.

Consider the null hypothesis that tracker $k$ does not reduce expected loss given everything observed so far, including the unlabeled inputs. Under that null, $E^{(k)}$ is a nonnegative supermartingale. Ville's inequality then gives $P(\sup_t E^{(k)}_t \ge 1/\alpha) \le \alpha$. The guarantee needs no fixed sample size and survives continuous monitoring and arbitrary label delay. The construction reuses the e-process of Anytime-Valid Confirmation. The new part is the conditioning argument that makes stream-learned corrections admissible, plus a mixture over trackers with different decay rates and reset rules.

A deployment rule follows directly. Apply the base model until some tracker's wealth crosses $1/\alpha$, with $\alpha$ split across the bank. Then switch to that tracker. Restart its wealth on a second, "it now hurts" test, so reverting shocks are handled.

The empirical claim has two parts. First, on real temporal streams, existing fixed-decay trackers look better under the usual evaluation, where decay is tuned with full-stream labels, than under a leakage-free one. We will measure how large that optimism is. Second, under the leakage-free protocol, the e-process selector matches or beats the best tracker that could have been chosen in advance, and it keeps empirical false-switch rates at or below $\alpha$ on streams where correction should not help.

Positioning

The trackers we wrap are existing methods. Exponential moving averages of soft predictions come from Park et al. and Logit-Adjusted TTA under Partial Class Imbalance. The latter fixes the decay and temperature globally and evaluates on synthetic corruptions, not time. First-in-first-out prediction queues come from Yang et al. and Malialis et al.. Label Shift Adapter feeds such an average into a hypernetwork and admits a cold-start lag after shifts. OT3A fuses predictions with graph propagation on static TableShift slices. We do not propose a better estimator. We propose a valid way to choose among estimators and to switch them on or off over time, which none of these papers provides.

Four results motivate the work. Wild-Time documents an average 20% drop from training years to future years. EMDOT shows random splits hide administrative shocks such as SEER coding changes. TableShift finds that in-distribution accuracy together with label shift explains $R^2 = 0.993$ of out-of-distribution accuracy, so the class mix is a dominant lever. Gap 1 of the literature points out that any single decay rate is wrong for streams that trend, jump and revert, a pattern Insup Lee describes for covariate shift.

Two results constrain the design. On Pitfalls of TTA reports collapse when feature extractors are updated online. We therefore touch only output logits and never normalization layers, which also sidesteps the β-drift failure. Gap 4 of the file identifies a further hazard: when a dormant class's estimated prior goes to zero, the $-\log \hat p(y)$ penalty permanently suppresses that class if it re-emerges. All trackers therefore floor priors, and the "no correction" arm is always in the bank.

Benchmark contamination enters as an evaluation threat, not as a method. Several Wild-Time streams (HuffPost, arXiv) are public web text. Contamination work shows models do well on material from before their training cutoff and degrade after it (Haoang Chi et al.; Snoopy). A pretrained encoder may therefore look well calibrated on pre-cutoff years for the wrong reason. We stratify every result by whether a period precedes the backbone's pretraining cutoff, and we also run training-from-scratch backbones. If tracker gains concentrate in post-cutoff periods only for pretrained backbones, contamination is confounding the drift story.

Research Program

We will build three things. The first is a leakage-free streaming harness over Wild-Time Eval-Stream and EMDOT cohorts. It replays each dataset in timestamp order with a configurable label delay $d$ and forbids any statistic, normalization or hyperparameter from touching labels before their arrival time. This addresses the global-preprocessing leakage described by Horn et al.. The second is the predictable-correction e-process and the bank-selection rule, with a short proof that stream-learned corrections preserve validity under delayed, out-of-order label arrival. The third is a leakage audit. We rerun each tracker with its decay rate tuned on full-stream labels, as is common in test-time adaptation papers, and report the gap to chronologically tuned and e-process-selected versions.

Baselines

The naive reference point is the base model with no prior correction. This is Wild-Time's ERM, which that paper finds "surprisingly difficult to beat." It reports OOD accuracy of about 79% on Yearbook (about 98% in-distribution) and in-hospital mortality AUC falling from 0.90 to 0.72 on MIMIC-IV. We train it once on the pre-deployment period with identical architecture and data for every arm. On EMDOT's tabular cohorts we also include a tuned gradient-boosted tree with the same budget, because EMDOT and TableShift both show such models are strong. A second naive point is static BBSE-style reweighting (Lipton et al.), estimated once on the first deployment window and then frozen.

The strongest existing competitors are fixed-decay logit-adjusted trackers in the style of Logit-Adjusted TTA and the queue-based estimators. Their decay or queue length is chosen by chronological validation on the last pre-deployment year. Each gets the same 20-configuration grid that forms our bank, and all arms adapt only the output layer. That paper reports, on ImageNet-C at class imbalance ratio 0.1, TENT+LA all-class accuracy of 34.4% with peak-to-average reduction of 4.68%, against 64.2% for plain TENT. Label Shift Adapter reports 72.97% on VisDA-C RSUT versus 48.68% for TENT. OT3A reports 71.29% balanced accuracy on TableShift Diabetes versus a 55.22% baseline. No reported result found on Lacuna for any online prior tracker on Wild-Time or EMDOT streams, so we establish those numbers ourselves.

We also include a delayed-label frequency tracker. It is a moving average of the true labels that have already arrived, so it is supervised but lagged by $d$.

Beating the strongest baseline means one of two outcomes. One is lower time-averaged log-loss and higher balanced accuracy than the chronologically tuned best tracker, with paired bootstrap intervals over periods excluding zero, while empirical false-switch rate stays at or below $\alpha$. The other is equal loss with strictly fewer harmful switches after shocks.

The key ablation isolates the statistical test. It uses the same bank, but selects the tracker with lowest cumulative delayed-label loss so far ("follow the leader"), with no error control. A second ablation removes the "no correction" arm.

Why not just…?

Why not just tune the decay rate on a held-out earlier period? This is the most serious competitor and is in our baseline set. Its weakness is structural. One rate chosen in a calm year must also serve the post-shock year. EMDOT shows the right recency trade-off flips between COVID-like shocks and data-scarce periods. If chronological tuning matches the e-process selector on all streams, we will report that the contribution reduces to error control and the leakage audit.

Why not just track the class mix from delayed labels directly? When $d$ is short, the frequency of recently arrived labels is a near-unbiased, simple estimate and may win outright. We sweep $d$ from zero to a full seasonal cycle. We expect unlabeled-prediction trackers to help only once $d$ exceeds the time scale of prior change. Locating that crossover is itself a practical result, and the e-process can include the delayed-label tracker as one arm.

Why not just pick the tracker with best recent loss, without a formal test? Follow-the-leader may match our accuracy. Its cost is uncontrolled switching on stationary stretches. We measure this on null streams built by permuting time within periods, where no correction should help, and we count spurious switches for both selectors. If follow-the-leader's false-switch rate is also low, the guarantee adds little in practice, and we will say so.

Why not just trigger resets with a drift detector such as the incremental KS test? The incremental KS test detects feature change, not whether a correction lowers loss. Unsupervised alarms fire on harmless variation. Our test bets directly on the quantity that matters. We include an IKS-triggered reset of the EMA tracker as an additional arm.

Decisive Checks

Four checks decide the outcome. The first is validity: across thousands of null-stream replays, the fraction ever crossing $1/\alpha$ must stay at or below $\alpha$ for every label delay. The second is the leakage audit. If full-stream-tuned trackers do not beat chronologically tuned ones by a measurable margin on Wild-Time HuffPost, arXiv and MIMIC-IV, our framing of temporal optimism is wrong for this setting. The third is shock response on SEER lung (the coding change) and CDC COVID. Here we measure, in labeled-sample units, how long until the selector switches, and how much excess loss accrues relative to an oracle that knows each period's true class mix. The fourth is the contamination stratification. Results are split by pre- and post-cutoff periods for pretrained versus from-scratch backbones. Tracker gains that appear only post-cutoff for pretrained text encoders would show that part of the apparent temporal drift is a training-cutoff edge.