Nonstationarity is ubiquitous in practical classification settings, leading deployed models to perform poorly even when they generalize well to holdout sets available at training time. We address this by reframing nonstationary classification as time series prediction: rather than predicting from the current input alone, we condition the classifier on a sequence of historical labeled examples that extends beyond the training cutoff. To scale to large sequences, we introduce a learned discrete retrieval mechanism that samples relevant historical examples via input-dependent queries, trained end-to-end with the classifier using a score-based gradient estimator. This enables the full corpus of historical data to remain on an arbitrary filesystem during training and deployment. Experiments on synthetic benchmarks and Amazon Reviews '23 (electronics category) show improved robustness to distribution shift compared to standard classifiers, with VRAM scaling predictably as the length of the historical data sequence increases.
Figures & tables
Figure 1: A diagram illustrating the architecture of our system. We learn input-dependent queries, which are used to sample from a massive corpus of historical data in a manner similar to stochastic hard attention. The input and selected corpus items are then fed to a downstream classifier which predicts the label. Through hard sampling at training time and attention masking, our implementation allows full corpus to stay on an arbitrary filesystem at both training and inference time, facilitating scaling to huge corpora.
Figure 2: Synthetic settings. ( left ) Accuracy vs. time in a nonstationary binary classification setting with rotating decision boundary. Models train on t∈[0,0.5] and test on t∈[0,1]. Our method leverages historical context to mitigate performance degradation beyond the training distribution. ( right ) Training dynamics on a ‘needle in haystack’ task where the label is encoded in one historical item. The system learns to retrieve the correct item after a random exploration phase with duration scaling linearly with the number of items.
Figure 3: Amazon Electronics Reviews. ( left ) Peak VRAM consumption during training vs. hyperparameters. Scaling is consistent with Eqn. 2 . ( right ) Accuracy over time for models trained on pre-2014 data. Our method leverages historical context to mitigate performance degradation on out-of-distribution data beyond 2014.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Additional results in the ‘needle in haystack’ setting. ( left ) Binary cross-entropy classification loss vs. training steps. Loss remains random for some exploration period which scales linearly with the number of historical examples, after which it sharply decreases as the query mechanism learns to retrieve the correct item. ( center ) Cross-entropy loss of the retrieval mechanism over time, when viewing the index of the key-containing historical item as the ‘true label’. This loss decreases at around the same point at which the classification loss decreases. Note that we do not directly train on this objective – the retrieval mechanism learns to select the correct item because this leads to lower classification loss. ( right ) Entropy of the distribution over historical examples from which the retrieval mechanism samples. This sharply increases and then decreases at around the time the classification loss decreases.
Figure 5: Diagram of a Perceiver block ( Jaegle et al., 2021 ) . Rather than attending directly to the full input sequence like a standard transformer, Perceivers use cross-attention to combine the input with a learned data-independent ‘latent’ vector. They then apply a sequence of standard transformer blocks to this sequence. This approach reduces the computational cost from L2 to LM where L is the input sequence length and M is the latent sequence length (a hyperparameter). The Perceiver architecture is appealing for our use case because it was proposed with multimodal feature fusion in mind, and because it is more-scalable to long sequences than standard transformers.
Figure 6: Accuracy over time for models trained on pre-2014 data from the electronics category of Amazon Reviews ’23. ( left ) Our retrieval mechanism returns full historical examples (Xt−m,Yt−m). ( right ) Our retrieval mechanism returns only the labels Yt−m of historical examples. In the former case our system has similar robustness to a standard classifier, while in the latter case it is able to leverage historical context to mitigate performance degradation on the out-of-distribution data beyond 2014.
Retrieval-augmented time-series forecasting typically selects historical examples by similarity between observed pasts, although similar pasts can evolve differently. We propose Predictive Relevance Retrieval (PRR), which uses realized future compatibility as privileged supervision to learn a retrieval function that remains strictly past-only at inference. PRR combines Pearson retrieval with a futuresupervised predictive representation to expand candidate support, then reranks the union using statistical and learned pair relations. Across six datasets and four long horizons, PRR improves Pearson retrieval in 23 of 24 conditions, reducing AnalogFutureMSE by 26.7% on average. A candidate-budget-matched variant, PRR-B100, retains nearly the same retrieval improvement while using at most 100 candidates at inference, showing that the gain is not explained simply by a larger candidate pool. We then connect the retriever to five frozen forecasting backbones using validation-calibrated trust. Downstream effects are heterogeneous, and calibration primarily reduces harmful retrieval use rather than making improved retrieval universally beneficial. These results show that predictive relevance and forecast utility are empirically distinct objectives.
Yong-Hoon Choi, Kwang-Hyun Park, Youngjin Cho
Division of Robotics, Kwangwoon University Seoul 01897, Republic of Korea
Static benchmarks measure a model frozen at training time. Real systems face distribution shift: new categories, paraphrased queries, drift: and must recover online via user corrections. No existing benchmark measures recovery speed under correction streams. We introduce OCRR (Online Correction Recovery Rate): a benchmark that streams a corpus through a classification system, applies oracle or stochastic corrections to wrong predictions, and reports two curves: novel-class accuracy and original-distribution accuracy versus correction count. We evaluate the substrate alongside nine baseline algorithms from five families plus seven bounded-storage variants of the substrate for the Pareto sweep, including standard online-learning baselines (river), continual-learning methods (EWC, A-GEM, LwF), retrieval/parametric hybrids (kNN-LM), parameter-efficient fine-tuning of a 1.5 B-parameter encoder (LoRA on DeBERTa-v3-large), and a hash-chained append-only substrate (Substrate). On Banking77 and CLINC150, under oracle and sparse correction policies, the substrate is the only system that simultaneously recovers novel-class accuracy (88.7 +/- 2.9 %) and retains original-distribution accuracy (95.4 +/- 0.8 %) beating the next-best published continual-learning baseline by 32.6 percentage points at equal memory budget, and beating LoRA-on-DeBERTa-v3-large by 84.6 percentage points on retention. We further find that classification accuracy remains stable at 99 % even as approximate-nearest-neighbour recall@5 degrades from 0.69 to 0.23 across 10 k to 10 M corpus scales, suggesting the substrate's margin-band majority vote is robust to retrieval imperfection in a way that pure top-k recall metrics do not predict. Code and data are available at https://github.com/adriangrassi/ocrr-benchmark.
Time introduces fundamental challenges in model development and deployment: models are usually trained on historical data while deployed on future data where semantic distributions and domain knowledge may evolve. Unfortunately, existing studies either overlook temporal shifts or hardly capture rich shifting patterns of both semantic and knowledge. We develop Knowledge-driven Augmentation and Retrieval for Integrative Temporal Adaptation (KARITA) to capture diverse temporal shifts (e.g., uncertainty and feature shift), construct and integrate rich knowledge sources (e.g., medical ontology like MeSH), and leverage shifting insights for selecting-retrieval augmented learning. We evaluate KARITA on classification tasks across multiple domains, clinical, legal, and scientific corpora, demonstrating consistent improvements across multiple domains with temporal adaptation. Our results show that knowledge integration can be more critical and effective in temporal augmentation and learning.