A Temporal Algebraic Framework for Data Stream Evaluation Under Delayed Labels and Distribution Shifts

Ronaldo C. Prati, Elaine Ribeiro de FariaarXiv 2026 · arXiv

Evaluating machine learning models in a static batch environment is straightforward. But in the real world—where data flows in high-velocity streams—things get messy. Labels might arrive weeks late (think fraud detection), classes might suddenly vanish from your evaluation window, and the data distribution itself might shift under your feet.

In their paper, "A Temporal Algebraic Framework for Data Stream Evaluation Under Delayed Labels and Distribution Shifts," Ronaldo C. Prati and Elaine Ribeiro de Faria introduce a rigorous mathematical framework to handle these streaming headaches. By extending an algebraic approach based on indicator matrices, they provide a unified way to track model performance that is both computationally efficient and robust to the quirks of live data.

TL;DR

The authors present a unified algebraic framework for evaluating data streams that handles delayed labels and distribution shifts with $O(m^2)$ update efficiency. By monitoring "prior-free" coordinates like recall and specificity, the system can distinguish between a failing model (concept drift) and a simple change in class prevalence (prior shift), significantly reducing false alarms in monitoring dashboards.

What Problem Does This Paper Address?

Standard evaluation metrics like Accuracy and $F_1$ are "prior-dependent"—they change if the ratio of classes in your data changes, even if the model's decision logic remains perfect. In a data stream, this leads to "spurious alarms" where a monitoring system thinks a model is failing just because a specific class became more or less common.

Furthermore, real-world streams suffer from verification latency. If you predict a transaction is fraudulent, you might not know the truth for weeks. Most streaming evaluators either ignore unlabelled data (introducing selection bias) or wait for labels (introducing a lag). Finally, rare classes often disappear from short evaluation windows, leading to "zero-division" errors that break standard metric calculations.

Methods

The core of the paper is the Temporal Reduction Operator ($\Sigma_t$). This operator allows the system to maintain a single evolving state—a confusion matrix—that is updated at every time step using either exponential fading (weighting recent data more heavily) or a sliding window.

The framework pipeline shows how features, predictions, and delayed labels feed into a single temporal operator to produce consistent metrics.

Key methodological innovations include:

  • Interim Estimates ("Stand-ins"): Until a true label arrives, the framework uses the model’s own calibrated class probabilities to provide a temporary estimate. This prevents "holes" in the evaluation state and corrects for selection bias.
  • Prior-Free Coordinates: The authors identify recall and specificity as "canonical" coordinates that are invariant to changes in class prevalence.
  • Jacobian Decomposition: They use a first-order Jacobian decomposition to mathematically attribute a change in a metric (like $F_1$) to two distinct sources: concept drift (the model is getting worse) and prior shift (the data distribution changed).
  • Formal Verification: Impressively, 25 of the paper's mathematical statements were formally checked using the Lean 4 proof assistant, ensuring the algebraic foundations are rock-solid.

Datasets

The framework was evaluated on a mix of synthetic and real-world benchmarks:

  • Synthetic Streams (S1-S10): Designed to simulate specific challenges like continuous prior drift, abrupt concept drift, and bursty arrivals of rare classes.
  • Real-World Streams:
    • Elec2: Electricity market records with seasonal drift.
  • Airlines: Flight delays where the "label" (the actual arrival) is naturally delayed by the flight duration.
  • Credit Card Fraud: A highly imbalanced stream with clustered arrivals.
  • NSL-KDD: A standard network intrusion detection dataset.
  • Covertype: Forest cover type data.

Key Insights and Ideas

  • Separating the "What" from the "Where": The framework cleanly separates how you summarize data (Micro vs. Macro averaging) from where you look (per-class projections). This ensures that pooled measures remain a consistent weighted combination of per-class measures, even as weights shift over time.
  • The Power of Calibration: The accuracy of the "interim estimate" for delayed labels is directly tied to the model's calibration error. This creates a virtuous cycle: a well-calibrated model is easier to evaluate accurately in real-time.
  • Zero-Division Auditing: Rather than using silent defaults (like setting $0/0$ to $0$), the framework explicitly audits "voids." It provides policies (exclude, zero, or nan) that ensure transparency in automated monitoring dashboards.
The algebraic architecture separates functional reduction (summarization) from structural per-class projections (diagnostics).

Key Results

  • Efficiency: The update cost is $O(m^2)$ per step (where $m$ is the number of classes), regardless of the stream length. This makes it suitable for embedded or high-velocity applications.
  • Robustness: In tests on synthetic and real data, a detector monitoring prior-free coordinates raised no excess false alarms under label shift, whereas standard error-rate detectors fired frequently.
  • Bias Correction: The interim estimate strategy successfully recovered recall in real-world settings (like the Credit Card Fraud stream), though the authors note the correction is only partial for metrics like precision and $F_1$ when delays are label-dependent.

Limitations and Future Work

While the framework is powerful, the authors acknowledge several limitations:

  • Label-Dependent Delays: If the delay itself depends on the true label (e.g., fraud is confirmed faster than non-fraud), the current correction is only partial.
  • Independence Assumptions: The variance model for the drift detector assumes independent arrivals, which is often violated by "bursty" real-world data.
  • Future Directions: The authors suggest developing interim estimators that can adapt to calibration drift online, further improving the accuracy of performance estimates for unverified data.

The code for this framework is available in the aggmetrics Python package.

Summary updated

Abstract

In data streams, labels often arrive late or only for some instances, class prevalence drifts, and rare classes vanish from short windows. Standard evaluation then confuses a degraded decision boundary with a change in prevalence, and is biased when labels are delayed or selected by the model. We extend an algebraic framework that obtains pooled (micro) and per-class (macro) measures from one confusion matrix to streams, weighting the counts in time by exponential fading or a sliding window; the update costs O(m^2) per step, whatever the stream length, and each pooled measure stays a weighted combination of the per-class ones. Delayed and selective feedback enter as an observation mask: until its label arrives, an instance is counted with the model's calibrated class probabilities, and the bias of this interim estimate is driven by their calibration error. Audited conventions report no value for a class without verified instances. We separate prior shift from concept drift by monitoring prior-free coordinates (recall and specificity) and attribute a change in a measure to the two sources with a first-order Jacobian decomposition. On synthetic streams and four real datasets, a detector on these coordinates with a memory per class raises no excess false alarms under label shift, unlike the Jacobian alarm and error-rate detectors. The correction for delayed labels recovers recall in some real settings and is only partial for precision, specificity and F1. Twenty-five statements are checked in Lean 4, and the code is in the aggmetrics package.
BibTeX
@misc{prati2026temporal,
  author = {Ronaldo C. Prati and Elaine Ribeiro de Faria},
  title = {{A Temporal Algebraic Framework for Data Stream Evaluation Under Delayed Labels and Distribution Shifts}},
  year = {2026},
  eprint = {2611.21914},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21914},
}
Figure