SONATA: Synergistic Coreset Informed Adaptive Temporal Tensor Factorization
Authors: Maolin Wang
Zhiqi Li
Binhao Wang
Xuhui Chen
Tianshuo Wei
Wanyu Wang
Shikai Fang
Ruocheng Guo
Zenglin Xu
Xiangyu Zhao
Venue: ICLR 2026 Poster (2026)
Keywords: Dynamic tensor streams
Temporal dynamics
Coreset selection
Linear Dynamical Systems
Adaptive modeling
Primary area: learning on time series and dynamical systems

Abstract: Analyzing dynamic tensor streams is fundamentally challenged by complex, evolving temporal dynamics and the need to identify informative data from high-velocity streams. Existing methods often lack the expressiveness to model multi-scale temporal dependencies, limiting their ability to capture evolving patterns. We propose SONATA, a novel framework that unifies expressive dynamic embedding modeling with adaptive coreset selection. SONATA leverages principled machine learning techniques for efficient evaluation of each observation for uncertainty, novelty, influence, and information gain, and dynamically prioritizes learning from the most valuable data using Bellman-inspired optimization. Entity dynamics are modeled with Linear Dynamical Systems and expressive temporal kernels for fine-grained temporal representation. Experiments on synthetic and real-world datasets show that SONATA consistently outperforms state-of-the-art methods in modeling complex temporal patterns and improving predictive accuracy for dynamic tensor streams.

Published as a conference paper at ICLR 2026
SONATA: SYNERGISTIC CORESET INFORMED ADAP- TIVE TEMPORAL TENSOR FACTORIZATION
Maolin Wang's Zhiqi Li Binhao Wang', Xuhui Chen', Tianshuo Wei', Wanyu Wang', Shikai Fang". Ruocheng Guo Zenglin Xu1.5, Xiangyu Zhao 1.
1 CCity University of Hong Kong, ZZejiang University,
Indeepeneent Researcher, *Fudan University, SShanghai Academy of Al for Science "Corresponding authors
[morin. wangê, Shiglic 6-cêmy., xianzhaol ci cityu. edu. hk xxuanuufagg, rguo. asu, zenglin in @gma il com
ABSTRACT
Analyzing dynamic tensor streams is fundamentally challenged by complex, evolv- ing temporal dynamics and the need identify informative data from high-velocity streams. Existing methods often lack the expressiveness to model multi-scale temporal dependencies, limiting their ability to capture evolving patterns. We propose SONATA, novel framework that unifies expressive dynamic embedding modeling with adaptive coreset selection. SONATA leverages principled machine learning techniques for efficient evaluation of cach observation for uncertainty, novelty, influence, and information gain, and dynamically prioritizes learning from the most valuable data using Bellman-inspire inspired optimization. Entity dynamics are modeled with Linear Dynamical Systems and expressive temporal kernels for fine-grained temporal representation. Experiments on synthetic and real-world datasets show that SONATA consistently outperforms state-of-the-art methods in modeling complex temporal patterns and improving predictive accuracy for dynamic tensor streams. Our code is publicly released at httpp:: //ttps:://ttub coom Mecppllled-aaahhiieeeeea http::/p....oooooooroooeooee/oap
SONATA
INTRODUCTION
Tensors are powerful structures for representing multi-modal data, with applications ranging from recommender systems to neuroscience (Chen et al. 2025: Harshman et al.) 1970: Wang et al.
2024b Sidiropoulos et al. 2017 Wang al.) 20256 a 2023a a b a). In modern scenarios, these
tensors often arrive as velocity continuous streams (Du et al. 2018 Fang et al. 2021a 2023). Learning dynamic embeddings from such streams is critical. Yet,
persistent challenges remain: 1)
Modeling Expressiveness: existing approaches often fail to capture the rich and evolving temporal relationships between entities (Zhang et al., 2027 Li al.) 2022 Wang et al., 2022 Chen al. 2025); and 2) Stream Efficiency: processing all observations is computationally prohibitive, making essential design principled mechanisms for selecting the most informative samples (Wang & Zhe 2020 Broderick et al. (013). Addressing both challenges simultaneously is key for advancing streaming tensor learning.
On the modeling side, static methods (Tucker 1966 Zhe et al. 2016b Rai et al.) 2014 and simple temporal extensions (Xiong al.) 2010 Rogers et al., |213 Zhe al. [016a]]
al. 2018) suffer
from oversimplified temporal representations that cannot capture complex non-stationary dynamics. Even recent dynamic tensor models (Zhang et al.] 202T Fang al,, 2023). though more advanced, still impose restrictive assumptions that limit adaptability to continuously evolving relationships.
On the efficiency side, existing approaches to streaming data typically process everything indiscrim- inately adopt heuristic sampling (Broderick et al. 2013 Fang et al. 202 This overlooks central fact: the informational value of streaming observations is highly uneven. Many samples redundant, while small fraction is disproportionately important for improving representation quality and predictive accuracy. Without explicitly prioritizing such informative data, models waste computation low-value observations and risk missing the few points that matter most. This

---

Published as a conference paper at ICLR 2026
underscores why principled sample selection is not only desirable but also crucial for accurate and effective streaming tensor analysis.
With these motivations, we introduce Synergistic cOreset iNformed Adaptive Temporal Tensor fActorization (SONATA), a framework for precise and efficient learning from dynamic tensor streams (Fang et al. 2023 Chen al. 2025). SONATA is distinguished by two key elements. First, it models fine- tineggrained temporal evolution using Linear Dynamical Systems derived from expressive kernels (e.g., Matérn) (Hartikainen & Särkkä 2010, Särrkä & Svensson 2023), enabling the capture of multi-scale dynamics, Second, and most importantly. it introduces a dynamic coresel strategy that maintains compact yet maximally informative subset of the stream. This coreset is updated adaptively by jointly assessing uncertainty, novelty, influence, and information gain, ensuring that the model focuses its updates on the data that matters most.
By aligning expressive modeling with coreset- based efficiency, SONATA provides both the necessary modeling power and the first principled framework to select informative samples in streaming tensor decomposition. This perspective is at once natural and novel within this field. In contrast, prior work such as (Chhaya et al. (020) remains confined to symmetric tensor settings, producing static coresets that lack adaptivity and generality, and thus cannot address the challenges of general temporally evolving tensor streams. The main contributions of this work are as follows:
We propose SONATA, which combines dynamic embedding modeling with synergistic coreset construction to handle multi-scale temporal dynamics in tensor streams. This integrated approach improves model expressiveness for accurate temporal pattern modeling.
We develop synergistic coreset selection mechanism that evaluates data importance through multiple criteria, i.e., uncertainty, influence, novelty, and information increment, and optimizes coreset composition by principles based on the Bellman equation.
We develop an efficient voreset-guided streaming Bayesian inference algorithm that leverages the concentrated information for adaptive updates without relying on deep neural networks.
2 PROBLEM FORMULATION AND BACKGROUND.
Real-world multiway data can be naturally represented as tensors. Consider a K K-mode tensor with de entities mode k. Each observed entry is indexed by D [(Cn, Un. W where yn is the value at time tn. The aim is to learn dynamic embeddings u (1) : + R that encode evolving entity properties.
.,....,,k), giving dataset
Classical tensor decompositions, such as CP (Harshman et al. 1970) and Tucker (Tucker 1966). estimate static embeddings. In CP.
R
K
V1 ~
Σ1
I
u
(k)
where " is the r-th entry of the embedding for entity 4 in mode k. These approaches ignore temporal evolution. To address nonlinearity, Gaussian processes (GPs) have been used (Xu et al.
2011 Zhe al. 2015 2016a), modeling
(K)) V2- = De=g(uf) ..... Ui
g GP(O, kt)
Yet inference requires an N N kernel matrix, making GPs expensive. With Gaussian noise 6n (,,, o²), the marginal likelihood is p())) N' K of1).
Temporal information is often handled by adding a time mode or discretizing time (Rogers et al. 2013 Xiong et al., 2010). Dependencies can be modeled conditionally, e.g. p(ue, Ue,))
Nuu U
| T II). Continuous-time variants parameterize CP factors with splines (Zhang et al. but struggle with irregular sampling or streaming data.
202
principled alternative is to model embeddings with Linear Dynamical Systems (LDS).. Each entity's
latent state X,. E R evolves as
(k) j.t
Fx
(k) 716--1 At
w
j.t.
(K)
(K) ~N(0 Q),
2

---

Published as a conference paper at ICLR 2026
Time
CoreSet
Latent
Expectation
Propagation
Nan-Coradiet
Mastiercae Time Weighting
Synengatic
Multi-scale Time Weighting Mechanism
Niselyy
thcorieery
Etflanec
2riormation PorPREr
Extraction
SDE
Dynoric Weighring
LDS Lotent States
Bellman Equation
Vp
R2
V(G,, 0.
[R(C, 0x)
7a (CC. :..:)l
smell) dill a.
Trade-sffi Lemmddtte Re Discounted Futuraly))
Overview of SONATA framework: Multi-scale feature extraction combined with SDE, synergistic coreset selection criteria (novelty, influence, uncertainty, information increment), coreset evolution via Bellman equation, and optimization via Expectation Propagation.
Figure 1:
with observed embedding
(b) (t)
H
N(O, R.bs).
j.t
j.t
j.t
Here, F, H, Q Rohs can be linked to continuous-time stochastic differential equations for temporal kernels such Matérn (Hartikainen & Särkkä 2010 Fang al. 2023
SONATA MODELS
As shown in Fig. I the Synergistic cOreset iNformed Adaptive Temporal Tensor fActorization (SONATA) is decomposition model for dynamic tensor streams.
3.1 DYNAMIC LATENT FACTOR MODEL WITH TEMPORAL EVOLUTION
At the heart of SONATA lies model for dynamically evolving latent factors (embeddings) for each entity within the tensor. For K-mode tensor, an entity j in mode k represented by time-varying embedding vector u (k))
(t) E " The evolution of this embedding is governed by Linear Dynamical System (LDS), ensuring smooth and continuous trajectories, An underlying latent state (t) (t) E R
(where R) evolves according to the stochastic differential equation (SDE):
dæ
(k) (t) (M) (t)dtt Ldw((t)
where F is the dynamics matrix, L is a noise matrix, and dw((t is a Wiener process increment with dwo(t) (0, Q.dt). The observed R R-dimensional embedding is linear projection of this state:
Kc
The parameters F, H. and the steady-state covariance Poc (from which L and Q, can be derived) are determined by a chosen temporal kemel, typically from the Matérn family (Matern) 1960) Särkkä
& Svensson 2023). For instance, Matérn-y 3/2 kernel implies 5 = 2R, with 2.

---

Published as a conference paper at ICLR 2026
(2) (I), u [u] translates to the discrete-time LDS:
(10 (L) and specific forms for F and H. For discrete time steps AL, this SDE
(k)
A(AI) a jtt At + jj., j,t
with ji
~ ~NO Q(41)):
(6)
j
u; (t) = Ha
(7)
j
where A(At) cA and Q(at) Px A(At))xA(AT) An observed tensor entry yn at time in involving entities ln = (In.l....,huu is modeled, for a CP decomposition, as:
Un ΣI
(k) Mh (ln) + M(
(k) (La)) Cn.
(8)
where En NO,,T=1) is observation noise, and is its precision.
3.2 SYNERGISTIC CORESET CONSTRUCTION CRITERIA
The computational burden of processing every incoming data point (Ln, fn,t,) in high-velocity streams necessitates a more efficient approach. SONATA addresses this critical challenge by metic- ulously maintaining a temporally dynamic coreset C.. This coreset is not merely a random sample but a compact, dynamically updated subset of data observed up to time 4, specifically engineered to be highly informative. The cornerstone of SONATA's coresct strategy is its synergistic selection criteria. Rather than relying on a single heuristic, the inclusion of data points into C, is guided by comprehensive evaluation of their multifaceted potential to refine the model's 's understanding and enhance its predictive capabilities. This holistic assessment ensures that the coreset captures a rich and diverse representation of the information embedded in the data stream.
This synergy is operationalized through a carefully designed importance score S. for each candidate data point This point n is characterized by observed value yn time and involves set of entities ln = (fn,1, ".....,,,,,,))
(n,r). where f, is the entity index in mode m.. The importance score is:
Sn = Wh. Inne(n) + w. Inn((n) + Wn Iame (n) + Wmn (1)
The non-negative weights Wh, Wi, Wn, Wm balance the contributions of the different components. Uncertainty. Here, Iune (n) quantifies the model's 's uncertainty regarding the entities in ln at time t. Let V V,,a,mm.. be the R predicted covariance matrix of the R- R-dimensional latent embedding (m) u en (tx) for entity fu.m in mode at time (i.e., V Vm.a.mm. m.. Cov(u, (m) (t.))Pt,,,)). D). The score is the average of the mean diagonal elements (variances) of these predicted covariance matrices across the M modes:
Tune (n)
1 M
Σ
1 R
V m. m.laamm Ier
(10)
where [V mm....mtt. the r-th diagonal element of the covariance matrix for the embedding of entity fn.m in mode m. The diagonal elements represent marginal uncertainties of each factor dimension, providing computational efficiency and interpretabilityy while covariance information is implicitly captured through factor interactions in subsequent computations.
Influence. (n)( measures the point's potential influence, typically based on its similarity to (m)
members already in the coreset C, Let p.m... H.n.m.t..lt..- be the R-dimensional predicted mean em- bedding of entity tn,m in mode m for point n. We define an interaction vector for point as (m)
2, O m==1 tt. where ( denotes the element-wise (Hadamard) product if all embed- dings are of the same dimension R. This choice mirrors the CP decomposition strueture where tensor values are computed as sums of element-wiss products of factors, ensuring alignment between influence measurement and the model's prediction mechanism. For coreset point e (involving entities L. =
(k)
M,,M at time lc), let Mic be the posterior mean embedding of entity
The similarity sim(z,, ze) can be, for le,k in mode k. Its interaction vector is z O k=1 m Palttolto"
(k)
example, the cosine similarity: sim 2n, ze) = I 1l
2 Zo
Then, Inr(n) is:
[e Eosc, sim(Zn, 20)
if # 0
[n)
(1))
if C. 0
4

---

Published as a conference paper at ICLR 2026
Novelty. Inov (n) assesses its novelty compared to existing coreset members C. It is weighted sum:
WidxTnovids (1)) + WrimeTnov.time (n:) if C # 0 0
Inwe (n)
(12)
if C+
where Widx and Whime are non-negative weights. Inovide (11) is the proportion of new entity indices in ln. Let Em (C,) be the set of unique entity indices from mode m that are present in the coreset C.
M Σ m==1
Inovids (n)
I(en. & Enn(C()
(13)
M
where II(-) is the indicator function (1 if true, 0 if false). Inuytime depends on the minimum absolute time difference At (n)) = mincee, 1 - tel (if C. = 0, Atmin (n) is treated as oo, making
Inov,time (n) 1). > is decay rate hyperparameter.
noovttime (n) 1 - exp(- (imnAmn
(14)
Information increment. Crucially, (n) represents the Martingale-based information inere- ment, estimating the expected reduction in model error (or increase in information) if point n were included. Let in be the model's prediction for the true value yn. using the predicted mm For a CP model of rank R, this prediction is On =
mean embeddings En JMM
(m)
Σ Im== 14 (nnmmstt Enmmestint (i,,-,,111 Ir. The term AE, quantifies the "surprise" informativeness of point which can be represented by the squared prediction error:
(i7)
A E,, = (Un 02
(15)
The Martingale information increment is then:
Iman (n) = tanh(a max(0, AE,)),
(16)
where > 0 is a scaling hyperparameter, and tanh(-) is the hyperbolic tangent function, which squashes the value, typically into the range [0, 1).
Points with Sn exceeding an adaptive threshold lr. potentially combined with e-greedy exploration strategy, are added to C, If [C,| exceeds a budget Mmax, only top Ma.. will be selected.
3.3 TEMPORAL CORESET EVOLUTION VIA BELLMAN EQUATIONS
The decision of which candidate points include in the coreset each time step can be framed as sequential catisiionmmking problem. SONATA employs principles from optimal stopping and dynamic programming, specifically using a Bellman-like equation, optimize this selection process with respect to long-term model performance.
Let (C,, θ)) be the value function representing the expected future model performance given the current coreset C, and model parameters O, An action S Deamd,t corresponds to selecting subset of new candidate points from the candidate set Deand,t to add to the coreset, resulting in C,+1 (C, U a,) \ Pe, where P. denotes the set of points pruned to maintain the budget constraint M The Bellman equation seeks to maximize the expected cumulative reward:
R[Cr, ar, θ.) + VCC,, = max
0
(17)
a, Deat,
The immediate reward R(C,, de O,) can be defined based on the sum of importance scores S, of points in a,, or the immediate improvement in model fit reduction in uncertainty. 7B E [0, 1] is discount factor for future rewards. Solving this equation (often approximately, e.g., via lookahead or value function approximation) guides the selection of a to maximize long-ten utility, rather than just myopic gain. This allows the model to make strategic choices about data retention, potentially prioritizing points that enable better future learning.
5

---

Published as a conference paper at ICLR 2026
3.4 BAYESIAN INFERENCE AND ONLINE LEARNING OF SONATA
SONATA employs streaming Bayesian approach to learn its parameters, primarily the dynamic latent factors (embeddings) {u. (k) (t)) for each entity in mode k at time t, and the observation
noise precision T. The temporal evolution of an embedding 3 (t) R R is governed by Linear (t)
(Ae)
Dynamical System (LDS) an underlying latent state 2 (t) E R (where S 2 R), described by Eq
At each timestamp i. the Kalman filter's prediction step provides a prior distribution [D<t,) for the latent state of entity j involved in the current data, which in turn yields a prior
Eq.
7
p(a
p (D.)) for its corresponding embedding.
For an observed tensor entry (ens Un. t. where L, = (l kn.K) are the indices of the involved entities, the observed value yr related to their embeddings via a (lypically non-linear) function f()) and Gaussian noise en ~ _N(0,T ) such that yn = f( (k) (=)))=)))) + Ex2 as exemplified by the CP decomposition in Eq. 8 Due the non-linearity of f()), exact posterior inference is intractable.
SONATA thus utilizes Expectation Propagation (EP) to approximate the posterior distributions
( (1) A (tx))==1 Tly,,, ).....
Concurrently, the posterior distribution of the noise precision (typically a Gamma distribution with shape a, and rate b,) is updated via EP. Its parameters are adjusted based on the expected squared prediction error, (un. (f (k) (t,,
((n))==)))) 2, and the variance of f(-). The inclusion of data point in the coreset Ct influences its weight in these message updates, with coreset points typically having full weight and non-coreset points potentially having attenuated weights. This mechanism allows SONATA selectively learn from the most informative data, thereby refining the dynamic
embeddings u (k) (1) and other model parameters. Overall, by focusing on well-established statistical machine learning techniques rather than computationally expensive deep learning methods, SONATA achieves an effective balance between modeling expressiveness and computational efficiency for streaming tensor factorization. Due space constraints, the detailed EP update process can be found in Appendix Sec. A and our code.
4 EXPERIMENTS
In this section, we present experiments for SONATA. Due to space constraints, the implementation details are described in Appendix Sec. B. Evaluation metrics are presented in Appendix Sec. Sec.B.2
4.1 SYNTHETIC DATA ANALYSIS
To validate the effectiveness of our method, we begin with a simulation study on synthetic data. A detailed description is provided in Appendix B.3
We present the estimated factor trajectories from SONATA with a Matérn-3/2 kernel (Fang et al. 2023) and lengthscale 0.3 in Fig. The model successfully recovers the ground-truth trajectories with high accuracy, as shown by the close alignment between estimated and true values. While we lednewledge that tensor decomposition inherently produces non-unique solutions, this non-uniqueness does not diminish the interpretive value of the learned trajectories. Similar to how topic models like LDA provide valuable insights despite non-unique topic assignments, SONATA's trajectories capture meaningful dynamic patterns that serve both interpretive and predictive purposes.
The shaded regions represent the posterior standard deviation, providing quantification of uncertainty for our estimates. Of particular interest is the increased uncertainty at times t ~ 0.5. 1, and 1.5-precisely the points where ground-truth trajectories overlap. This demonstrates that SONATA appropriately expresses higher uncertainty when inherent ambiguities exist in the data, providing reliable confidence measures that reflect the true difficulty in distinguishing trajectory values at these time points. This principled uncertainty quantification, enabled by our Bayesian framework, is key advantage over alternative approaches such as neural networks that may achieve similar predictive performance but lack interpretabilliyy

---

Published as a conference paper at ICLR 2026
1.0
1.0
1.
Grund Cut
ground trub
Grunchup
0.5
0.5
0.0
0.0
-0.5
-05
sene Injetry
-100
Time
10
Time
Time
10-
Time
(a) (f)
(b) (t(()
(c) (t(
(d) u (t(
Figure 2: The learned factor trajectories from the synthetic data. The shaded region indicates the posterior standard deviation.
RACC
FItSI
020
3.25
TH--300
0.35
3.20
8.1055
Error
0.32
LITE
Emor
1265
STT
0.30
1.6
53w/0h X330
Lengthscale
Kemel
Time (seconds)
(a) Effect of Lengthscale on SONATA performance.
(b) Effect of Kernel Selection on SONATA performance.
(c) Per-epoch/iteration running
time comparison.
Figure 3: Performance analysis of the SONATA model on the Server Dataset.
4.2 REAL-WORLD DATA ANALYSIS
Detailed descriptions of the datasets and baseline methods are provided in Appendix B.5 and Sec. B.6 respectively.
Datasets and Baselines:
Our extensive experiments on four real-world datasets demonstrate that SONATA consistently outperforms existing methods. On CA Traffic 30K, SONATA achieved 61.5% RMSE reduction compared to the second-best method SFTL-CP (0.231 - 0.089, < 0.05), showing its strength in capturing complex spatiotemporal patterns such as congestion evolution transportation networks. SONATA also exhibited versatility across diverse domains environmental monitoring (BeijingAir), infrastructure management (ServerRoom), and user behavior analysis (ereccord-validdatiiii our combination of Gaussian processes with state-space priors for streaming factor trajectory learning (detailed in Table [.)
Compared with static methods requiring multiple passes and recent continuous-time decompositions, SONATA achieved superior accuracy while processing the data only once (Table TT.. This advantage arises from: (1) adaptive updating to evolving patterns versus static assumptions; (2) natural emphasis on recent, more predictive observations; (3) avoidance overfitting noise common in non-stationary settings; and (4) coreset mechanism focusing learning the most informative samples. Against streaming baselines such as POST, ADF-CP, and BASS-Tucker, Tucker, SONATA maintained substantial advantages throughout, confirming its ability to incrementally build accurate factor trajectories via state-space priors and conditional expectation propagation.
4.3 PARAMETER ANALYSIS AND COMPUTATIONAL EFFICIENCY
In our analysis of the lengthscale parameter's effect on model accuracy using the Server dataset. (Fig. (a),, found that lengthscale of 0.3 produces the lowest error rates (RMSE 0.1293, MAE 0.0940), indicating this value optimally captures the temporal dynamics the data. Too small (0.1) too large (0.9) lengthscales lead to degraded performance due to either overfitting noise excessive smoothing of important temporal patterns.
The choice of kernel function significantly impacts model performance. Our comparison (Fig. ((b)) shows that the Matérn-3/2 kernel substantially outperforms the Matérn-1// 1/2 kernel, reducing RMSE by 49. 5% and MAE by 47.0%. This confirms that the Matérn-3/2 kernel, with its moderate smoothness
7

---

Published as a conference paper at ICLR 2026
Table Final prediction error with At The results were averaged from ten runs. Bold numbers denote the best performance, underlined numbers represent the second- best results, and indicates statistical significance at p < 0.05 level using paired t-test.
RMSE
CA Traffic 30K
ServerRoom
BeijingAir
FilRecord
PTucker
0.942 + 0.053
0.458 0.039
0.401 + 0.01
0.656 + 0.147
Tucker-ALS
0.043
0.985
0.539 0.021
0.005
CP-ALS
1.093 0.037
0.991 = 0.015
0,801 = 0.082
0.882 1 0.017
Static
CT-CP
0 0.013
0.334 = -0.009
0.640 + 0.007
0.664 + 0.007
CT-GP
0.673 0.019
0.223 0.035
0.759 0.020
0.604 +: 0.004
BCTT
0.685 0.024
0.185 0,013
0.39 0.U22
(15118 + 0.007
NONFAT
0.501 = 0.002
0.117 0.00G
0.395 + 0.007
0.503 + 0.002
THIS ODE
0.632 0.002
0.132 0.003
0.540 + 0.014
0l526 + 0.004
POST
0.032
0.641
U.516
0.696 0.019
ADF-CP
1.089 0.041
0.634 0.008
0.548 + 0.015
0.648 + 0.008
BASS
1,818 0.000
1.000 = 0.016
1.019 + 0.037
0.976 + 0.021
Stream
SFTL-CP
0 0.015
0.161 0.014
0.248 0.012
0.424 + 0.014
SFTL-Tuckkr
0.316 0.029
0.331 0.056
0.303 0.041
0.430 + 0.010
SONATA (Ours)
0.089 + 0.004
0.115 + 0.006"
0.237 0.011
0.414 + 0.016'
MAB
PTucker
0.514 0.006
0,259 0.00S
0.26 0.006
0.369 + 0.009
Tucker-ALS
0.720 0.006
U.739 0.008
0.388 0.008
0.615 + 0.006
CP-ALS
0.712 0.007
0.746 0.000
0.586 + 0.056
0.642 + 0.012
CT-CP
0.461 = 0.003
0,269 0.003
0,489 0.006
0.460 + 0.004
Statie
CT-GP
0,165
0.550
0.414 0.001
BCTT
0.452 0.006
0,141 0.011
0,254 + 0.007
0.355 + 0.005
NONEAT
0.391 0.001
0.091 0,004
U.256 + 0.004
0.341 + 0.001
THIS-ODE
0.005
0.345
0.363 0.004
POST
0.707 0.019
U.476 0.023
0.352 + 0.022
0.478 + 0.014
ADF-CP
0.904 + 0.007
1149% 0.007
0.385 + 0.012
0.449 + 0.006
BASS
1,601 0.041
0.749 + 0.01
0.934 + 0.037
0.772 + 0.031
Streum
SFTL-CP
0.026 0.001
0,108 0.0
0.150 0.003
0,242 0.006
SUTL-Tuckkr
0.17T - 0.005
0.216 0.034
0.185 + 0.029
0,246 + 0.001
SONATA (Ours)
0.015 + 0.001
0.083 + 0.004
0.156 + 0.011
0.240 0.012
CoreSet Factors Trajectories
Non-CoreSet Factors Trajectories
2213
Factor Value
Factor Value
08
32
05
26
3.
Time
Time
(a) Coreset factors
(b) Non-coreset factors
Figure 4: Comparison of temporal patterns between coreset and non-coreset factors. Coreset factors in (a) exhibit more structured and consistent behavior with clearer patterns, while non-coreset factors (b) display more irregular and noisy trajectories.
properties, better captures the underlying patterns in spatiotemporal tensor data. Computational efficiency is crucial for practical applications alongside accuracy.
Our runtime comparison of different methods (Fig. 3]c) demonstrates that SONATA delivers superior performance with reasonable computational cost. While simpler methods like CT-CP execute faster (0.018s per iteration), they deliver significantly lower accuracy evidenced in Table I In contrast, THIS-ODE achieves reasonable accuracy but demands substantially more computation time (7.190s per iteration) due to its deep neural architectures. SONATA, with computation time of 0.338s per iteration, achieves the highest accuracy across all datasets, demonstrating excellent effectiveness without deep neural networks excessive computational burden for streaming tensor tasks.
8

---

Published as a conference paper at ICLR 2026
4.4 COMPARISON OF CORESET AND NON-CORESET FACTOR TRAJECTORIES
As shown in Fig. the temporal patterns of selected coreset and non-coreset factors demonstrate distinct characteristics. The coreset factors exhibit more structured and consistent behavior with clearer patterns, while the non-coreset factors display more irregular and noisy trajectories. It is important to note that these trajectories represent one interpretation of the system dynamics rather than absolute truths-neural network models could provide entirely different yet valid interpretations. However, SONATA's interpretation offers crucial advantages: the clear behavioral patterss in coreset factors (e.g., periodicity suggesting regular events like daily backups) versus the high uncertainty in non-coreset factors provide valuable signal-noise distinction for domain experts. This contrast highlights SONATA's ability to effectively identify and select the most informative and representative factors from the dataset. The temporal priors imposed by our LDS and Matérn kernel further constrain the solution space toward smooth, temporally continuous trajectories, yielding stable and meaningful patterns that directly contribute to our superior predictive performance shown in Table 1. Discussions about the trajectories of all coresets and servers can be found in Appendix Sec.
4.5 CORESET BUDGET AND SIZE ANALYSIS
A key parameter in our proposed procedure is the maximum coreset size, Mmax which serves budget constraint. A legitimate question then seems to be: How can this budget be defined and to what extent does it impact the performance? In order to alleviate this, we conducted a systematic sensitivity analysis on the CA Traffic dataset. The findings, found in Table 2 highlight the core insight of the adaptive approach of our algorithm.
Table 2: Sensitivity analysis of the coreset budget (Mmax) on the CA Traffic dataset. The results demonstrate that the algorithm automatically converges to an effective coreset size without necessarily utilizing the full budget.
Mmx 1000
Final RMSE
Peak Memory (MB)
Avg Update Time (ms)
Final Coreset Size
Coreset Usage (%)
0.1808
7.84
8897.64 64
800 (2.67%)
80.0%
2000
0.0938
8.12
3553.56
1597 (5.32%)
79.9%
3000
0.0891
8.18
3536.70
1654 (5.51%)
55%
Experimental results show that our algorithm does not blindly fill the budget but rather autonomously converges an optimal coreset size. For instance, if increase Maax from 2000 to 3000, we can see the saturation phenomenon. Though the budget grew by 50%, the final coreset size increased only narrowly from 1597 1654, and the utilization rate declined from 79.9% 55.1%. The improvement in RMSE was just 5%. This means those 1600 high-quality samples are adequate to obtain the necessary underlying data stream information. Over the same threshold, the marginal efficiency of adding new ones decreases considerably. This saturation behavior is initiated by the four collaborative selection criteria interacting. The novelty decreases, uncertainty is reduced, and errors converge the coreset grows, since is now representative set of entities and timestamps. This results in an automatic increase the implicit inclusion threshold; that is, only observations with significant informational value are included in the coreset.
4.6 EFFECT OF DISCOUNT FACTOR
The discount factor y the Bellman equation balances immediate vs. future rewards in coreset selection. Ta- shows the RMSE of SONATA on the Server and CA Traffic datasets. For Server, 7 = 0.5 yields the low- est RMSE (0. 115)), indicating immediate rewards dom- inate. For CA Traffic, 7 = 0.9 performs best (0.0893), meaning long-term coreset utility is more useful. This highlights the data-depent dettedeennddnt nature of ry. Due to space limitations, additional analysis about hyperparameter and coreset can be found in Appendix Sec.
Table 3: RMSE performance with different discount factors.
Discount Factor
Server
CA Traffic
0.9
0.1293
0.0893
0.7
0.1181
0.1072
0.5
0.1156
0.1107
0.1409
0.1716

---

Published as a conference paper at ICLR 2026
5 RELATED WORKS
Temporal Tensor Decomposition and Streaming Methods. Traditional tensor decomposition methods Battaglino et al. (2018); Wang et al. [2019] 2020); Bader & Kolda (2008) handle static data but lack temporal dynamics and require multiple passes. Early works treated time as an additional mode Rogers et al. (2013), while recent methods like CT-CP Zhang et al. (2021) CT-GP Chen (et al. (2024), BCTT Fang et al. (2022), and trajectory-based models (e.g., THIS-ODE Li et al. (2022), NONFAT Wang al. (2022)) capture continuous evolution. LDS also models temporal relations Zhen et al. (2023), but these methods require full datasets and multi-epoch training, making them unsuitable for high- streams. Streaming methods such POST Du et al. (2018).
ADF-CP Wang & Zhe (2020). and BASS-Tucker Fang et al. (2021a) update CP/Tucker factors incrementally. OnlineGCPP|Phipps et al. (2023) extends CP to exponential family distributions but does not model dynamics over continuous time. SOFIA Lee & Shin (2021) provides seasonal modeling but requires a pre-set seasonal cycle, while our Matérn kernel learns multi-scale temporal patterns. OR-MSTC Najafi et al. (2019) handles streaming tensors focusing on spatial growth, whereas SONATA captures temporal evolution. SBDT et al. (2021b) uses deep neural networks, but their black-box nature makes temporal patterns harder to interpret compared to SONATA's factor trajectories, which provide intuitive insights.
Coreset Strategies for Tensor Learning. General coreset theory Langberg & Schulman (0010)
has inspired censor-specific sampling, including LineFilter and KerneFiiter for streaming contrac- tions Chhaya et al. (2020), Bayesian regression coresets Huggins et al. (016)), Lewis weights Cohen & (2015), randomized/écooppottion Battaglino et al. (2018), tensor sketching Song et al. (2016); Wang et al. (2015), and RandNLA for matricized tensors Song et al. (2019). However, such methods rely on local criteria, overlooking evolving dynamics and long-term utility. Streaming tensor approaches with GP/LDS or ODEs remain computationally heavy, state complexity grows with data. SONATA advances this by jointly measuring uncertainty, influence, novelty, and information gain, while optimizing long-term benefit via Bellman principles- making it, our knowledge, the first coreset-basse based streaming tensor decomposition that fully integrates temporal considerations.
6 CONCLUSION
We presented SONATA, unified framework for streaming tensor factorization that integrates expressive continuous-time modeling with a synergistic coreset selection strategy. By leveraging linear dynamical systems derived from temporal kernels, SONATA captures complex, multi-scale temporal dynamics of entities. Its coreset mechanism dynamically selects informative data points based on uncertainty, influence, novelty, and information gain, and optimizes long-term utility via Bellman dellman-insppred principles. Our online Bayesian inference algorithm further ensures efficient and adaptive updates. While SONATA demonstrates strong empirical performance, several limitations remain. First, the current implementation assumes Gaussian observation noise and linear dynamical systems derived from Matérn kernels, which may restrict modeling flexibility in certain non-Gaussian or highly nonlinear domains. Second, our method assumes streaming data arrives at consistent temporal intervals; performance under bursty or irregular stream patterns remains to be fully explored. Due to space constraints, LLM usage details are provided in Appendix See D
ACKNOWLEDGMENTS
This research was partially supported by National Natural Science Foundation of China (No.62502404), Hong Kong Research Grants Council (Research Impact Fund No.R1015-23, Collab- orative Research Fund No.C1043-24GF, General Research Fund No. 1218325), Institute of Digital Medicine of City University of Hong Kong (No.9229503) Huawei (Huawei Innovation Research Program), Tencent (Tencent Rhino -iid Focused Research Program, Tencent University Cooperation Project), Alibaba (CCF-Alimane) ars Research Fund), Kuaishou (CCF-Kuaishon Large Model Explorer Fund, Kuaishou University Cooperation Project), and Bytedance.
Tech Kangaroo Fund No. 2024002), Didi (CCF- Didi Gaia Schol-
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Brett W Bader and Tamara G Kolda. Efficient matlab computations with sparse and factored tensors. SIAM Journal on Scientific Computing, 30(1):205-231, 2008.
Casey Battaglino, Grey Ballard, and Tamara G Kolda. A practical randomized ep tensor decomposi- tion. SIAM Journal on Matrix Analysis and Applications, 39(2):876 901, 2018.
Tamara Broderick, Nicholas Boyd, Andre Wibisono, Ashia Wilson, and Michael I Jordan. Stream- ing variational bayes. Advances in neural information processing systems, 26, 2013.
Panqi Chen, Lei Cheng. Jianlong Li, Weichang Li, Weiqing Liu, Jiang Bian, and Shikai Fang. Generalized temporal tensor decomposition with rank-revealing latent-ode. arXiv preprint wrXiv:2502.06/64 2025.
Yuehan Chen, Zhi Liu, Dezhi Han, Qing Yang, Chenhui Li, Xiaolei Shi, Mengchen Zhang, Chunyan Yang. Lijuan Qiu, Hongchang Jia, et al. Cold tolerance snps and candidate gene mining in the soybean germination stage based on genome-wide association analysis. Theoretical and Applied Genetics, 137(8):178, 2024.
Rachit Chhaya, Jayesh Choudhari, Anirban Dasgupta, and Supratim Shit. Streaming coresets for symmetric tensor factorization. International Conference on Machine Learning, pp. 1855-1865. PMLR, 2020.
Michael B Cohen and Richard Peng. Lp row sampling by lewis weights. In Proceedings of the serty-seventh annual ACM symposium on Theory of computing, pp. 183-192, 2015.
Yishuai Du, Yimin Zheng, Kuang-chih Lee, and Shandian Zhe. Probabilistic streaming tensor decomposition. In 2018 IEEE International Conference on Data Mining (ICDM), pp. 99-108. IEEE, 2018.
Shikai Fang, Robert M Kirby, and Shandian Zhe. Bayesian streaming sparse tucker decomposition. In Uncertainty in Artificial Intelligence, pp. 558-567, PMLR, 2021a
Shikai Fang, Zheng Wang, Zhimeng Pan, Ji Liu, and Shandian Zhe. Streaming bayesian deep tensor factorization. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pp. 3116-3126. PMLR, 2021b.
Shikai Fang, Akil Narayan, Robert Kirby, and Shandian Zhe. Bayesian continuous-time tucker decomposition. In International Conference on Machine Learning, pp. 6235-6245. PMLR, 2022.
Shikai Fang, Xin Yu, Shibo Li, Zheng Wang, Mike Kirby, and Shandian Zhe. Streaming factor trajectory learning for temporal tensor decomposition. Advances in Neural Information Processing Systems, 11.56849-568700 2023.
Richard A Harshman et al. Foundations of the parafac procedure: Models and conditions for an "explanatory" multi-modal factor analysis. UCLA working papers in phonetics, 16(1):84, 1970.
Jouni Hartikainen and Simo Särkkä. Kalman filtering and smoothing solutions to temporal gaussian process regression models. In 2010 IEEE international workshop machine learning for signal processing, pp. 379-384. IEEE, 2010.
Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. Advances in neural information processing systems, 29, 2016.
Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, and Maja Pantic. Tensorly: Tensor learning in python. Journal of Machine Learning Research, 20(26):1-6, 2019.
Michael Langberg and Leonard J Schulman. Universal e-approximators for integrals. In Proceedings of the aeent--firs annual ACM-SIAM symposium on Discrete Algorithms, pp. SIAM, 2010.
11

---

Published as a conference paper at ICLR 2026
Dongjin Lee and Kijung Shin. Robust factorization of real-world tensor streams with patterns, missing values, and outliers. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 840-851 IEEE, 2021. doi: 10.100/IDDE5139:221.000777 Also available as arXiv preprint arXiv:2102.0844
Shibo Li, Robert Kirby, and Shandian Zhe. Decomposing temporal high- interactions via latent odes. In International Conference on Machine Learning, pp. 12797-12812. PMLR, 2022.
Bertil Matérn. Spatial variation. stochastic models and their application to some problems in forest surveys and other sampling investigations. 1960.
Sobhan Moosavi, Mohammad Hossein Samavatian, Arnab Nandi, Srinivasan Parthasarathy, and Rajiv Ramnath. Short and long-term pattern discovery over large-scale geo-spatiotemporal data. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2905 2913, 2019.
Mehrnaz Najafi, Lifang He, and Philip S. Yu. Outlier-robust multi-aspect streaming tensor completion and factorization. In Proceedings of the eventy-Eighth International Joint Conference on Artificial Intelligence (ICCAI-19), pp. 3187-3194. International Joint Conferences Artificial Intelligence Organization, 7 2019. doi: 10. 10.24966/iicaii2211/4442
SLAWOMIR Niwiñski. IWONA Pujanek, and MACIEJ Stroiñski. Provision of databases in the poznan supercomputing and networking center. TASK Quarterly. Scientific Bulletin of Academic Computer Centre in Gdansk, 7(2):278-22) 282, 2003.
Sejoon Oh, Namyong Park, Sael Lee, and Uksong Kang. Scalable tucker factorization for sparse tensors- algooriigssss and discoveries. In 2018 IEEE 34th International Conference on Data Engi- neering (ICDE), pp. 1120- 1131. IEEE, 2018.
Yu Pan, Maolin Wang, and Zenglin Xu. Tednet: A pytorch toolkit for tensor decomposition networks Neurocomputing, 469:234 238,,,4-338, 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. 32:8024 8035, 2019.
Eric T. Phipps, Nicholas T. Johnson, and Tamara G. Kolda. Streaming generalized canonical polyadic tensor decompositions. In Proceedings of the Platform for Advanced Scientific Computing Conference (PASC'23), pp. Article 5. ACM, 2023. doi: 10. (00114///5999793559328 Also available
as arXiv preprint 10..5:2100.14514 and SAND2021- 13340 R.
Piyush Rai, Yingjian Wang, Shengbo Guo, Gary Chen, David Dunson, and Lawrence Carin. Scalable bayesian low-rank decomposition incomplete multiway tensors. In International Conference on Machine Learning, pp. 1800-1808. PMLR, 2014.
Mark Rogers, Lei Li, and Stuart J Russell. Multilinear dynamical systems for tensor time series. Advances in Neural Information Processing Systems, 26, 2013.
Simo Särkkä and Lennart Svensson. Bayesian filtering and smoothing, volume 17. Cambridge university press, 2023.
Nicholas D Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang. Evangelos E Papalexakis, and Christos Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on signal processing, 65(13):3551-353 2017.
Qingquan Song, Xiao Huang, Hancheng Ge, James Caverlee, and Xia Hu. Multi-aspect stream- ing tensor completion. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 435-443, 2017.
Zhao Song, David Woodruff, and Huan Zhang. Sublinear time orthogonal tensor decomposition. Advances in Neural Information Processing Systems, 29, 2016.
12

---

Published as a conference paper at ICLR 2026
Zhao Song, David P Woodruff, and Peilin Zhong. Relative enror tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2772- 2789. SIAM, 2019.
Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3): 279-311, 1966.
Maolin Wang, Chenbin Zhang, Yu Pan, Jing Xu, and Zenglin Xu. Tensor ring restricted boltzmann machines. In 2019 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2019.
Maolin Wang, Zeyong Su, Xu Luo, Yu Pan, Shenggen Zheng, and Zenglin Xu. Concatenated tensor networks for deep multi-task learning. In International Conference on Neural Information Processing, pp. 517-525. Springer, 2020.
Maolin Wang, Yu Pan, Zenglin Xu, Guangxi Li, Xiangli Yang, Danilo Mandic, and Andrzej Ci- chocki. Tensor networks meet neural networks: A survey and future perspectives. arXiv preprint arXiv:2302.09019, 2023a.
Maolin Wang. Dun Zeng, Zenglin Xu, Ruocheng Guo, and Xiangyu Zhao. Federated knowledge graph completion via latent embedding sharing and tensor factorization. In 2023 IEEE International Conference on Data Mining (ICDM), pp. 1361-1366. IEEE, 2023b.
Maolin Wang, Yu Pan, Zenglin Xu, Ruocheng Guo, Xiangyu Zhao, Wanyu Wang, Yiqi Wang. Zitao Liu, and Langming Liu. Cumulative distribution function based general temporal point processes. arXiv preprint NXXi::2402.00388 2024a.
Maolin Wang, Yaoming Zhen, Yu Pan, Yao Zhao, Chenyi Zhuang, Zenglin Xu, Ruocheng Guo, and Xiangyu Zhao. Tensorized hypergraph neural networks. In Proceedings of the 2024 SIAM International Conference on Data Mining (SDM), pp. 127-135. SIAM, 2024b.
Maolin Wang, Bowen Yu, Sheng Zhang, Linjie Mi, Wanyu Wang, Yiqi Wang, Pengyue Jía, Xuetao Wei, Zenglin Xu, Ruocheng Guo, et al. Renormalization group guided tensor network structure search. arXiv preprint arXiv:2512.24663 2025a.
Maolin Wang, Xiangyu Zhao, Ruocheng Guo, and Junhui Wang. Metalora: Tensor-enhanced adaptive low-rank fine-tuning, In 2025 IEEE 41st International Conference on Data Engineering (ICDE), pp. 4680-4684. IEEE, 2025b.
Yining Wang, Hsiao-Yo Yu Tung, Alexander J Smola, and Anima Anandkumar. Fast and guaranteed tensor decomposition via sketching. Advances in neural information processing systems, 28, 2015.
Zheng Wang and Shandian Zhe. Conditional expectation propagation. In Uncertainty in Artificial Intelligence, pp. 28-37. PMLR, 2020.
Zheng Wang. Yiming Xu, Conor Tillinghast, Shibo Li, Akil Narayan, and Shandian Zhe. Non- parametric embeddings of sparse high-order interaction events. In International Conference on Machine Learning, pp. 23237-23253. PMLR, 2022.
Liang Xiong, Xi Chen, Tuu-Kuo Huang, Jeff Schneider, and Jaime G Carbonell. Temporal collabora- tive filtering with bayesian probabilistic tensor factorization. In Proceedings of the 2010 SIAM international conference on data mining, pp. 21 SIAM, 2010.
Zenglin Xu, Feng Yan, et al. Infinite tucker decomposition: Nonparametric bayesian models for multiway data analysis. arXiv preprint arXiv: 6296, 2011.
Yanqing Zhang, Xuan Bi, Niansheng Tang, and Annie Qu. Dynamic tensor recommender systems. Journal of machine learning research. 22(65):11355, 2021.
Zijian Zhang, Ze Huang, Zhiwei Hu, Xiangyu Zhao, Wanyu Wang, Zitao Liu, Junbo Zhang, S Joe Qin, and Hongwei Zhao. Mlpst: Mlp is all you need for spatio-temporal prediction. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 3381-3390, 2023a.
13

---

Published as a conference paper at ICLR 2026
Zijian Zhang, Xiangyu Zhao, Qidong Liu, Chunxu Zhang. Qian Ma, Wanyu Wang. Hongwei Zhao, Yiqi Wang, and Zitao Liu. Promptst: Prompt-enhanced spatio-temporal multi-attribute prediction. In Proceedings of the 32nd ACM International Conference Information and Knowledge Management, pp. 3195-3205, 2023b.
Zijian Zhang, Xiangyu Zhao, Hao Miao, Chunxu Zhang, Hongwei Zhao, and Junbo Zhang. Autostl: Automated spatio-tempora multi-task learning. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp. 4902-4910, 2023c.
Xiangyu Zhao and Jiliang Tang. Modeling temporal-spatial correlations for crime prediction. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp- 497-506, 2017.
Xiangyu Zhao, Tong Xu, Yanjie Fu, Enhong Chen, and Hao Guo. Incorporating spatio-temporal smoothness for air quality inference. In 2017 IEEE International Conference on Data Mining (ICDM), pp. 1177-1 182. IEEE, 2017.
Shandian Zhe, Zenglin Xu, Xinqi Chu, Yuan Qi, and Youngja Park. Scalable nonparametric multiway data analysis. In Artificial intelligence and statistics, pp. 1125-1134. PMLR, 2015.
Shandian Zhe Yuan Qi, Youngja Park, Zenglin Xu, Ian Molloy, and Suresh Chari. Dintucker: Scaling up gaussian process models on large multidimensional arrays. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016a.
Shandian Zhe, Kai Zhang, Pengyuan Wang, Kuang-chih Lee, Zenglin Xu, Yuan Qi, and Zoubin Ghahramani, Distributed flexible nonlinear tensor factorization. Advances in neural information processing systems, 29, 2016b.
Zhong Zhen, Kamran Paynahar, and Jianjun Shi. Image-based feedback control using tensor analysis. Technometrics, 65(3):305-314, 2023.
14

---

Published as a conference paper at ICLR 2026
A DETAILS OF EXPECTATION PROPAGATION ALGORITHM IN SONATA
The core challenge in SONATA'S learning process is to infer the posterior distribution of the dynamic (k)
latent embeddings {wi_. (t, given an observation y/ at time in and all previous data Det..
Due to the non-linear relationship = f((u, (k) ((n))==)) + en (as in Eq 8 this posterior is intractable. EP addresses this by iteratively refining an approximation to the true posterior, typically within the exponential family (e.g., Gaussian).
A.1 EP UPDATE FOR DYNAMIC LATENT EMBEDDINGS
The EP algorithm approximates the true likelihood term plynku (k) (tn)) with simpler, tractable site approximations (often called approximate factor messages). When updating the pa- rameters for a specific embedding (kk)
"i, (t,)) of entity 4,, in mode k', we aim to compute the parameters of this site approximation, which will refer the "message" from the likelihood (kk)
factor concerning y/, to the variable Win. (ln). This message encapsulates the information that
the observation yn provides about " (t,). effectively marginalizing out the other embeddings (k) ( and the noise precision T using their current estimates (i.e., their current posterior {
predictive distributions).
This message is chosen to be a Gaussian distribution. For the Canonical Polyadic (CP) decomposition, ())
the observation model is yn (ut (In), mm)kr,)) 6ns where wik Ojzke "... (ln) is the
element wise product of embeddings from modes other than ke' for observation The likelihood (K') factor p(yn | ",,"' (fn),, (u/",, (tn)) r) NN [
(k') (t,)) WWW.r ( The Gaussian mes-
(R") sage approximating this factor with respect to "i (tx) has natural parameters: precision matrix Amsg.e and a mean-precision product (also called information vector) 7msg,kt. These are derived as:
A Amgg.' [E[]] [E[T]-Equ,)) Euu ww u (
(18)
Amsg.k [[[T] yo Buus)a [m
(19)
The expectations ( are taken with respect to the current posterior distributions of the embed- dings {u (tn)) (obtained from their respective Kalman filters at time tn prior to this update iteration), and B[r] is the current expectation of the noise precision (from its Gamma posterior). Damping is often applied when updating these message parameters from one EP iteration to the next to improve convergence stability. If an entity ln,k' participates in multiple observations at the current time fn. the natural parameters (Amsg K and 7msg.k') from each such observation are summed to form an aggregated message for that entity.
This aggregated Gaussian message, now characterized by Augg, and Tags,k', is then converted to moment parameters: mean k and covariance Vpscudo,ks, to serve as a pseudo-observation for the Kalman filter:
V Ypscudo, kt (Aagg. Mpscudo, = Vpscudo, k Tagg.k'
(20)
(21)
(K") The Kalman filter tracks the latent state Ii,, (tn), from which the embedding is derived (8))
via u, u (tn) = He
(k') (tx). The filter's prediction step provides the prior distribution for the state at in based on data up to ln-1 (or the last time this entity was updated, (prew): (ln)) Px.rrir) Specifically, mxxprio Am.. (ppew)) and Pa.prior A.. A.P.poss ((reev) AT Q. where A is the state transition matrix, Q is the process noise covariance, and mx.poal (t (trrew). Px.pos((tpp are the posterior mean and covariance from the previous update of this entity. The Kalman filter incorporates the pssudo-observation (puseudo,,k' V (r
p(()))) (Dn)) =
(K')
-N( (K")
15

---

Published as a conference paper at ICLR 2026
using its standard update equations:
Innovation: Vn P
Hmxxpriore x.prior:
(22)
Innovation Covariance: SKF,2 HPx x.prior
+ Vpseudo,k'
(23)
Kalman Gain: KKF, Ps s.prior H KF,m
(24)
Updated State Mean: Ma.pusi Ma.prior + Rn
(25)
Updated State Covariance: Px Pxpost
(I KkF, P p.pirorr
(26)
This yields the updated posterior for the latent state, p(a) N( (69 mx.)ss Pxppoa). Consequently, the updated posterior for the embedding is (K)) pluin (b,))Ds(,) N(u (tn, (Hm)) H.P xxpp This iterative EP process (cycling
(k)) (t..)
through factors and variables) refines the estimates of all involved embeddings for the current timestamp 4n-
A.2 EP UPDATE NOISE PRECISION
The observation noise precision is also learned via EP. SONATA typically assumes a Gamma prior for r, p(T) Gamma ag. bo), where ag is the shape and by is the rate parameter. The likelihood term p(ym. (u (t,)) r) = -N(,.lf(), also depends on
To update the posterior p(r(Dstt.) ). which remains Gamma distribution Gamma(7lax: bx), HP considers the contribution of each observation Yn- The message from the likelihood factor p(ynl's 7) T effectively updates the parameters of the Gamma posterior. The shape parameter aN typically updated by adding 2 for each observation processed. The rate parameter by is updated by adding { I(v,. - f( (tn)) [)) This expectation is taken with respect to the current posteriors of the embeddings. It can be approximated as 2 ((y, R[S(-)))² + Varlf(-))), where R(S(-)] is the expected prediction and V-r[f(-]] is its variance, both computed using the current embedding posteriors. This process accumulates evidence about the noise level from each data point.
(k)
A.3 INFLUENCE OF THE CORESET
It important to note that the coresct mechanism C., influences these EP updates. Data points selected into the coresct typically contribute with full weight to the message calculations and subsequent posterior updates. Conversely, data points not in the coreset might have their influence attenuated (e.g., their messages are weig-wei This strategy allows SONATA to focus its learning capacity on the most informative observations, thereby efficiently refining the dynamic embeddings u, and other model parameters like a streaming fashion.
(k)
A.4 CORESET SELECTION PROCESS
Not all high-scoring points in batch automatically selected for the coreset. Each point is evaluated independently against the selection criteria. When multiple points exceed the threshold, they compete for the limited coreset budget (Mmax). Only the top-scoring points up the budget limit are retained, ensuring computational efficiency while capturing the most informative samples.
A.5 MULTI-SCALE FEATURE EXTRACTION
Multi-scale feature extraction is fundamental to SONATA and can be realized using both the Matérn kernel and LDS. We build on the Matérn-3/2 kernel, which in our application operates in state space of dimension 2R. This kernel is used in conjunction with the embeddings (u(k), (t)) and their derivatives (ū(k), (4)). This augmented state representation is useful for encoding instantaneous variants as either the derivatives to the embeddings or long-term trends, i.e. embeddings themselves embeddings. With both the embedding values and derivatives together, SONATA chooses between fast and slow overflowing oscillation based on fast versus slow, and in this way, can compute a multi-scale temporal dynamics. Moreover, the time novelty nature of SONATA has exponential
16

---

Published as a conference paper at ICLR 2026
time-decay function. Also the data decay with À parameter has direct effects data temporal quality. Older data points lose their impact and become less important, allowing the model to focus on more recent data, thereby maintaining the temporal aspect, but allows for more overarching structure like a timeline.
B MORE EXPERIMENT SETTINGS
B. IMPLEMENTATION DETAILS
The SONATA model was implemented with PyTorch (Paszke et al. 2019). TensorLy (Kossaifi al. 2019), and TedNet Pann et al. (022), and run on an Intel Core Ultra 7 155H CPU. For all real-world datasets, we used CP decomposition with embedding dimension R 5. Dataset- specific configurations were as follows: for the traffic dataset, we employed Matérn- 1/2 kernel with lengthscale 0.9, discount factor 0.9, evaluation interval 10, and coreset maximum size of 3000; for the Beijing dataset, Matérn-3/2 kernel with lengthscale 0.3, discount factor 0.1, evaluation interval 20, and coreset size of 100; for the Server dataset, Matérn-3/2 kernel with lengthscale 0.3, discount factor 0.5, evaluation interval 60, and coreset size of 400; and for the fitRecord dataset, a Matéén- kernel with lengthscale 0.1, discount factor 0.5, evaluation interval 6, and coreset size of 2000. It is worth noting that the configurations detailed above were selected to achieve the optimal performance reported in the main results (Table 1).
For the ablation studies and parameter sensitivity analyses, we adopted a fixed baseline configuration strictly control variables and isolate the impact of specific factors. In particular, for the Server dataset, these analytical experiments were consistently conducted using discount factor of 0.9 to observe relative trends under a standardized setting, unless otherwise specified.
For the synthetic data experiments, we adopted a Matérn-32 3/2 kernel with lengthscale 0.3 and embed- 2. The model was trained for 100 epochs with dataset-specific evaluation inter- vals, utilizing martingale-basse
ding dimension based dynamic coreset selection with importance weights [0.3, 0.2, 0.2, 0.3].
important to note the fundamental differences between static and streaming methods. Static methods like CP-ALS require multiple passes through the entire dataset and, following their original papers and standard practice, we set fixed iteration counts (e.g., 100 iterations). Their total processing time far exceeds SONATA, they were not designed for streaming scenarios. contrast, streaming methods process data once a single pass, similar to SONATA.
For runtime comparisons,
Fig. presents per-iteration/epcch runtime comparisons for representative methods. While simpler streaming approaches like CT-CP demonstrate faster per-iteration times, their predictive accuracy is substantially lower than SONATA's (as shown in Table 1). Methods pursuing comparable high accuracy levels, such as THIS- ODE, incur much higher computational costs (7.190s per iteration) compared SONATA (0.338s per iteration) while still achieving lower predictive accuracy. This demonstrates that SONATA successfully balances efficiency with superior performance.
B.2 EVALUATION METRICS
To comprehensively evaluate the performance of SONATA and baseline methods dynamic tensor streams, we adopt the following widely used metrics.
Root Mean Square Error (RMSE). RMSE measures the square root of the average squared differences between the predicted and true tensor entry values. It is defined as
N (On
RMSE
Σ 1=1
)2
(27)
where N is the number of evaluated entries, yn is the ground-truth value, and on is the predicted value. Lower RMSE indicates higher predictive accuracy.
Mean Absolute Error (MAE). MAE calculates the average absolute difference between predicted and true values:
N
MAE- =
In ynl
(28)
N
R
17

---

Published as a conference paper at ICLR 2026
MAE is more robust to outliers compared to RMSE and reflects the typical prediction deviation.
These metrics jointly quantify prediction accuracy, robustness, and efficiency, providing a compre- hensive basis for evaluating the effectiveness of SONATA in streaming tensor factorization tasks.
B.3 GENERATED TRAJECTORIES
We generated a two-mode tensor with two nodes per mode, where each node is represented by time- varying factor trajectory. The factor trajectories for the first mode were defined as u (t) = sin 2 and uz(() (t)
(2 sin (4rt), while for the second mode, they were (t) and (t) = sin (2rt) ain(x)). Given these factors, tensor entry values at time were generated via (t) ~ ((u, (t)" unnn (t), 0.0)). We randomly sampled 500 timestamps from the interval [0.5, 1.5] and, for each timestamp. selected two tensor entries with values sampled according to the model above, resulting in 1,000 observed values in total. The near-zero uncertainty before | 0.8 occurs because the trajectories are well well-separated in that region and we have dense observations providing strong evidence. The smooth kernel prior well-suited these underlying trigonometric functions, leading to high confidence. Our experiments focus on the prediction of future observations based on streaming history, demonstrating SONATA's ability to track and predict complex temporal patterns in tensor data.
(int) cos(
B.4 HYPERPARAMETE SELECTION GUIDELINES
There are some key hyperparameters that impact performance in SONATA and the way they are chosen can affect much as an effect on outcome. For coreset budget (Mmax) we recommend that this be 5%-10% of expected data stream size upper bound. This makes the adaptive coreset automatically converge toward the optimal size, making this a budget guideline rather than hard limit. But the coreset size falls outside of this range, performance starts to reduce and computational overhead gradually increases even further for high-throughput coresets.
For the lengthscale of the temporal kernel, experiments show that range between 0.3 and 0.5 leads to stable performance, with RMSE variations staying below 3%. The decision to use values outside of this range can negatively influence model performance either due to overfitting noise given a small lengthscale, or excessively smoothing important temporal features given a large lengthscale.
The kernel selection is also important, where the Matérn-3/2 kernel is the appropriate chosen kernel. This shows that performs relatively better than the Matérn-1/2 1/2 kernel in capturing the multiscale temporal dynamics, therefore making the model much more accurate.
When it comes to the Adiversity parameter, we prefer around 0.1 to 0.3 for most datasets. This bounds a trade-off with diversity and richness in the coreset: for example, allowing the model select appropriate samples from an extensive corpus of data without introducing excess data points that will overwhelm the model with irrelevant samples. Similarly, the Tnoeelty parameter should be adjusted based on the sparsity of data; we would recommend 0.5 for sparse data and 0.9 for dense data, where higher values would favor novel and important data points.
The discount factor (n) of the Bellman equation that considers early or later rewards in coreset selection runs best in a range of 0.5 to 0.9 based on data. For immediate rewards-only datasets y 0.5 most robust, and for long-term urility-oriented sets y 0.9 is more preferable. For example, when comes to the CA Traffic dataset 7 = 0.9 is the right choice, but Server data outperforms with y 0.5.
B.5 DATASETS
We evaluated SONATA four real-world temporal tensor datasets. 1) CA Traffic 30K Mooosvii et al., 2019) contains lane-blocked records in California from January 2018 to December 2020, extracted mode temporal tensor between 5 severity levels, 20 latitudes, and 16 longitudes. Different from many existing papers, we adopted a more complex setup with 30K entry values and their timestamps. [ 2) FitRecord Dataset is collection of outdoor exercise health logs from EndoMondo users' health status, structured as a three-mode tensor encompassing 500 users, 20
hhap:://mmosaai..oydddassssswww
18

---

Published as a conference paper at ICLR 2026
sports types, and 50 altitude levels. The tensor entries represent heart rates, with 50,000 timestamped observations recorded. 3) ServerRoom Dataset contains temperature logs from the Poznan Supercomputing and Networking Center (Niwiñski et al. 2003). organized
three-mode tensor consisting of 3 air conditioning modes, 3 power usage levels (50%. 75%, 100%). and 34 locations. The dataset contains 10,000 timestamped temperature readings. 4) BeijingAir Dataset includes air pollution measurements in Beijing from 2014 to 2017 (Song et al. 2017). structured as a two-mode tensor between monitoring sites and pollutants (12 x 6 dimensions). The dataset includes 20,000 timestamped concentration measurements,
B.6 BASELINES
For evaluation, we compared SONATA against a set of tensor baselines. The static methods require multiple data passes and include: PTucker (Oh et al. 2018). parallel Tucker decomposition using row-wise updates; Tucker-AI.S (Bader & Kolda 20088 and CP-ALS (Battaglino et al.) (018)) utilizing alternating least squares for Tucker and CANDECOMP/PARATER
decomposition respectively; CT- CP (Zhang et al. (001)) a continuous-time CP decomposition with polynomial splines; CT-GP (Chen al. 2024), employing Gaussian processes model tensor entries as functions of latent factors and time; BCTT (Fang et al. 2002), a Bayesian continuous-tins Tucker decomposition that models the tensor-core as a time- varying function; NONFAT (Wang et al. 2022 which employs nonparametric factor trajectory learning in the frequency domain; and THIS- ODE (Li et al. (022). utilizing neural ODEs to model entry values. We also evaluated against streaming methods that process data in single pass: POST (Du et al.) 2018). probabilistic streaming CP decomposition using mean-field variational Bayes; ADF-CP (Wang& & Zhe| 2020), combining assumed density filtering with conditional moment matching: Tucker (Fang et al. 202 which employs online sparse tensor-core estimation via spike-and-slab priors; and
(Fang et al., 2023), representing streaming factor trajectory learning with CP and Tucker formulations. We note that recent work GRET (Chen et al.) 2025) also explores temporal tensor decomposition with neural ODE components; however, we did not include it baseline due to unavailability of open-source implementation.
C ADDITIONAL EXPERIMENTS
C.1 CORESET SELECTION EFFECTIVENESS
The visualization of factor trajectories across different datasets demonstrates SONATA's capability to capture diverse temporal patterns. As shown in Fig. 5 our model effectively learns the temporal evolution of entity embeddings while quantifying uncertainty through confidence bands. This aligns with the framework's 's synergistic coreset strategy that dynamically selects informative data points by assessing their potential for uncertainty reduction and pattern introduction.
As shown in Fig. 6, the temporal patterns of entities selected by SONATA's coreset criteria in the server monitoring dataset reveal the lighent-scoring factor with a score of 0.800 in the top panel, characterized by well-defined, periodic spikes at regular intervals with relatively low uncertainty (narrower confidence bands). This pattern likely corresponds to scheduled server activities or predictable system behaviors that SONATA correctly identifies highly informative.
In contrast, the bottom panel displays the lowest-scoring factor with a score of 0.449, exhibiting significantly higher variability, irregular fluctuations, and wider uncertainty bands. This comparison demonstrates SONATA's ability to effectively distinguish between high-value patterns containing concentrated, reliable information and noisy patterns with less predictive value.
The clear visual difference between these factors validates our synergistic coresct criteria, which prioritizes entities based their latent novelty, influence, and uncertainty characteristics. This selection mechanism ensures that computational resources are allocated to the most informative components of the tensor representation, leading to more efficient and accurate dynamic modeling of server performance data.
"http://sitss.oogll..oom/// http:///.oco/eg.eeddd.//////eeee
19

---

Published as a conference paper at ICLR 2026
CoreSet Factor Fajectories (Traffic)
CoreSet Factor Pajectories (Server)
Festor Sauu
Time
Time
(a) CA Traffic dataset
(b) ServerRoom
dataset
CoreSet Factor Trajectories (ItRecord)
CoreSet Factor Trajectoiee (Bellingtir)
Tine
Time
FitRecord dataset Figure 5: CoreSet Factor Trajectories across different datasets.
(d) BeijingAir dataset
C.2 EMPIRICAL ANALYSIS OF CORESET MECHANISM
To comprehensively evaluate the effectiveness of SONATA's synergistic coreset strategy, we conducted extensive experiments examining three critical aspects: (1) comparison with processing all data points, (2) comparison with simple random sampling, and (3) performance across different coreset budgets.
First, validated the computational efficiency gains of our coreset mechanism by comparing SONATA's performance when processing all available data points versus using our synergistic coreset selection. Experiments Processing all data points increases computational cost by over 25x (from 0.338s to 8.5s per iteration) while providing negligible improvements prediction accuracy (RMSE: 0. 0.1290 vs 0. 1293. MAE: 0.0942 vs 0.0940). This demonstrates that our coreset mechanism successfully identifies and retains the most informative samples while discarding redundant information, achieving substantial compu- tational savings without sacrificing predictive performance. For larger datasets like CA Traffic 30K, processing every data point becomes computationally prohibitive, making efficient strategies like coresets essential.
conducted the ServerRoom dataset with 10,000 total observations.
To isolate the contribution of our synergistic selection strategy, we compared SONATA's multi-criteria coreset selection against simple random sampling using the same coreset budget (400 samples) on the ServerRoom dataset. Our synergistic coreset strategy significantly outperforms random sampling. reducing RMSE by 12.7% (0.1293 0. 0.1481) and MAE by 12.6% (0.0940 vs 0.1075). This substantial improvement validates our core claim that SONATA's performance gains stem not merely from sub-sampling but specifically from its intelligent selection mechanism that evaluates uncertainty, influence, novelty, and information gain to capture critical events (e.g., anomalous temperature patterns preceding system failures) that random sampling might miss.
20

---

Published as a conference paper at ICLR 2026
Top CoreSet Factors by Score (Early Perlod)
Facter Value
2.00
0.2
0.24
2.00
0.08
0.20
212
0.44
Time
Bottom CoreSet Factors Score (Early Period)
VVW
Factor Value
2923 0.449)
0.24
5.65
0.00
Figure 6: Visualization of SONATA's CoreSet selection effectiveness on Server Dataset. The top panel shows the highest-scoring factor (U), Score: 0.800) with well-defined, periodic spikes and low uncertainty bands. The bottom panel displays the lowest-scoring factor (U% Score: 0.449) exhibiting high variability and wider uncertainty bands, demonstrating SONATA's ability effectively identify informative patterns versus noisy ones.
These empirical studies collectively demonstrate that SONATA's synergistic coreset mechanism is both computationally efficient and strategically effective, achieving near-optimal performance with only small fraction of the total data through intelligent, multi-criteria-baseee selection.
C.3 ONLINE PREDICTION ERROR
As shown in Fig. we evaluate the online prediction performance on the CA traffic 30k dataset. The results demonstrate that SONATA consistently achieves lower and more stable RMSE compared to SONATA. especially in the early stages. While both methods show convergence after processing around 20,000 entries, SONATA maintains a slight advantage in prediction accuracy.
C.4 ANALYSIS OF CORESET IMPORTANCE SCORE COMPONENT WEIGHTS
The SONATA framework utilizes synergistic coreset selection strategy where the importance score S, for each data point weighted sum four components: uncertainty reduction (June). influence f) novelty (Tno)), and Martingale-basee information increment (Imart). The respective non-negative weights Wa, Wi, Wny Wmn balance the contributions of these components. As shown in Table conducted experiments model S performance, measured by Root Mean Square Error (RMSE) and Mean Absolute Error (MAE). Additionally, analyzed the effect of different discount factors model performance, as presented in Table 3] and the impact of rank selection shown Table
evaluate the impact of different weighting schemes the
The results presented in Table indiicaee that the choice of weights for the different components of the importance score S, has a discernible impact on SONATA's predictive performance. Among the scenarios where only single component active, prioritizing "Influence" (w; 1) yielded the
21

---

Published as a conference paper at ICLR 2026
Online RMSE on traffic 30k
2.00
SPTL-P, R-5 SONAIA,
1.75
1.50
1.25
RMSE
1.00
0.75
0.25
0.00
0
5000
10000
15000
20000
25000
Number of Processed Entries
Figure 7: Online RMSE comparison between SFTL-CP and SONATA (R=5) on traffic_30k dataset.
Table 4: Effect of Coreset Importance Score Component Weights on SONATA Model Performance
Weights
Performance
Wy (Uncertainty)
wy (Influence)
Wy (Novelty)
Wm. (Martingale)
RMSE
MAE
1.00
0.00
0.00
0.00
0.1207
0.0866
0.00
1.00
0.00
0.00
0.1162
0.0845
0.00
0.00
1.00
0.00
0.1172
0.0842
0.00
0.00
0.00
1.00
0.1214
0.0888
0.00
0.33
0.33
0.34
0,1179
0.0851
0.33
0.00
0.33
0.34
0.1138
0.0820
0.33
0.33
0.00
0.34
0.1169
0.0842
0.34
0.33
0.33
0.00
0.1168
0.0840
lowest RMSE (0.1162) and MAE (0.0845) compared to exclusively using Uncertainty, Novelty, or the Martingale increment.
However, the best overall performance in this experiment was achieved with a combined weighting scheme. Specifically, the combination of weights (w,, 0.33, n. 0.00, w, 0.33, Wm. 0.34 resulted in the lowest RMSE 0. 0.31 and the lowest MAE of 0.0820. This suggests that for the tested dataset and configuration, strategy that balances Uncertainty, Novelty, and the Martingale information increment, while placing minimal or no emphasis on the Influence component, is most effective for constructing an informative coreset and achieving higher predictive accuracy. This demonstrates the synergistic nature of the coreset criteria, where a thoughtful combination of factors can outperform individual heuristics.
C.5 EFFECT OF RANK
The rank R in tensor decomposition determines the number of latent factors used to represent the data. We evaluated the performance SONATA on the Server dataset with different rank values, as shown in T
The results in Table 5 indicate that for the Server dataset, a rank of 3 achieved the lowest RMSE 1233) and MAE (0.0902). Increasing the rank to 5 or 7 did not lead to improved performance; in fact, the RMSE and MAE slightly increased. This suggests that a rank 3 is sufficient to capture the dominant underlying patterns in the Server dataset, and higher ranks might introduce unnecessary
22

---

Published as a conference paper at ICLR 2026
Table 5: Effect of Rank on SONATA Model Performance (Server Dataset)
Rank
RMSE
MAE
0.1233
0.0902
5
0.1293
0.0940
0. 0256
0.0915
complexity or lead to overfitting. The paper mentions that the main experimental results in Table 1 were obtained with R = 5. While R shows better results in this specifie sensitivity analysis for the Server dataset, Rt = 5 might have been chosen as a general setting or based on performance across multiple datasets or other considerations not detailed in this snippet.
C.6 KALMAN FILTER AND EP COMPARED
We compare the Kalman Filter and EP, and present the results and the final performance measurements, RMSE and MAE, with either method the table below:
Table 6: Comparison of Kalman Filter and EP (SONATA) Performance
Method
RMSE
MAE
Kalman Filter
0.2515
0.1876
EP (SONATA)
0.0891
0.0150
Note that a significant RMSE decrease is possible to be made in EP with respect to Kalman filtering. This improvement was primarily due to three key factors. First, Kalman filters struggle with non- linear observations, especially the products of multiple factors in tensor CP decomposition. At this stage it can only linearize the approximation. However, in EP, nonlinear factors are naturally dealt with and thus the conclusion becomes more accurate. Thereafter, EP can share the information with all the relevant entities via message passing and thus integrate the global info. In contrast, Kalman filtering updates locally, which can reduce its performance for more complicated problems. Finally, the pseudo-observation method of EP offers excellent characteristics for tensor structures and is more accurate for such contexts. These benefits illustrate that EP critical for the case of nonlinear tensor flow problems, which Kalman filtering is less suitable to deal with.
C.7 SCALABILITY ANALYSIS
In this subsection, we present scalability analysis of the proposed method on the Traffic dataset for various data sizes. Table summarizes the experimental results.
Table 7: Scalability analysis the Traffic dataset with varying data sizes.
Data Size
Final RMSE
Peak Memory (MB)
Running Time (s)
Final Coreset Size
1, 000
0.5920
4.24
88.49
345
5, 000
0.4236
2.68
315.24
827
10, 000
0.2358
4.12
403.97
1, 153
30, 000
0.0891
8.52
849.83
1, 654
The results show that the proposed approach has good scalability and near-linear time complexity. With the size of the data increased from 1, 000 to 30, 000 points (i.c., 30x time). the running time grows from 88.49 seconds 849.83 seconds (approximately 9.6x increase time). This sublinear scaling is achieved using a simple coreset function: the more data points they process, the more the algorithm keeps those samples which are informative with respect to each other, causing a sub-linear increase in the active coreset size. The method maintains only 1, 654 of core samples, accounting for approximately 5.5% of the total 30, 000 number of sets. In addition, memory usage is maintained throughout the entire process and is largely determined by coreset size rather than the entire dataset size. The results validate our method as an efficient and scalable computation solution to be used for large-scale processing data streams.
23

---

Published as a conference paper at ICLR 2026
C.8 HANDLING IRREGULAR TIME STEPS
Table 8: Performance under different temporal sampling patterns. SONATA demonstrates robustness to irregular time steps.
Sampling Mode
Final RMSE
Time Steps
Interval Mean
Interval Std
Regular Random Dropout
0.0891
217
0.0046
0.0330
0.1262
154
0.0066
0.0420
Bursty Sampling
0.1606
72
0.0137
0.0832
Exponential Gaps
0.1329
56
0.0043
0.0044
A key advantage of SONATA is that it can inherently treat irregular time steps like our continuous-time SDE formulation dz/dt dt = Fx(()= + Lw(t). Discretized, the state transition matrix A( = exp(F. At) naturally accommodates arbitrary time intervals At between observations. To systematically analyze this property, we performed experiments in different irregular sampling conditions and we could find results in Table 8 Our methodology proved be robust confirmed by the results. SONATA performs best (RMSE = 0.0891) under normal sampling. Performance declines gracefully your data has missing observations (Random Dropout) highly irregular patterns (Bursty Sampling and Exponential Gaps). Nevertheless even in the Bursty Sampling hard scenario, with high variance time spans (Std 0.0832), SONATA has good reproducibility (RMSE 0.1606). This illustrates the real-works applicability of our continuous- time method for deployment and actual real-time application situations where data acquisition irregular and sometimes unpredictable.
D LLM USAGE DISCLOSURE.
In accordance with ICLR 2026 policy, we disclose our use of Large Language Models (LLMs) in the preparation of this work. We employed LLM tools, including OpenAl's GPT series, to assist in polishing the writing of this manuscript. Their role was limited to improving clarity, grammar, and readability of certain sections such the Introduction and Related Work, as well as helping rephrase sentences for stylistic consistency. During the research process, we occasionally used LLMs for brainstorming alternative formulations of background text and related work discussions, but all technical content, theoretical analysis, algorithmic design, and empirical experiments were conceived and executed entirely by the authors. We used LLMs for programming support including code formatting, commenting, and implementation assistance, but the core design of the SONATA framework, the coreset mechanism, Bayesian inference pipeline, and all experimental evaluations were independently developed and validated by the research team. All LLM --M--eerrtted suggestions were carefully reviewed and revised by the authors. The core scientific contributions including problem formulation, algorithmic innovations, proofs, and experimental analyses remain completely original and the sole work of the authors.
24


Reviews:
[{"review_id": "ypJUIfzKQJ", "reviewer": "Reviewer_WfpD", "summary": "The paper introduces SONATA, a framework for streaming temporal tensor factorization that integrates: (1) Matérn-kernel-based linear dynamical systems (LDS) for multi-scale temporal modeling, (2) a synergistic coreset selection mechanism combining four criteria (uncertainty, influence, novelty, information gain), (3) Bellman equation inspired long-term value optimization, and (4) expectation propagation (EP) for online Bayesian inference. The approach demonstrates strong empirical performance and computational efficiency compared to existing streaming tensor methods.", "questions": "- Could you please clarify your contribution to non-Gaussian and robust streaming methods?\n- Is there a possibility of lacking ablation studies?\n- Can you explain your procedure for selecting hyperparameters?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Well-Motivated Integration with Clear Value Proposition\n\nThe paper addresses a problem of balancing expressiveness and efficiency in high-velocity tensor streams.\nThe 4-criterion coreset selection is principled and goes beyond simple heuristics.\nEmpirical gains are substantial: 61.5% RMSE reduction vs. SFTL-CP on CA Traffic (Table 1).\n\n2. Strong Empirical Performance Across Multiple Dimensions\n\nThe authors reprorted statistically significant improvements (p<0.05) across 4 diverse datasets.\nThe proposed method is faster than processing all data, ~21× faster than THIS-ODE (Fig. 3c) while maintaining superior accuracy.\nBayesian uncertainty quantification (Fig. 2) and smooth factor trajectories provide domain-interpretable representations unavailable in deep learning alternatives.\n\n3. Solid Technical Execution\n\nThe Bellman-equation-based long-term coreset optimization (Eq. 17) is conceptually novel in streaming tensor factorization.\nDiscount factor analysis (Table 2) shows data-dependent optimal strategies, suggesting principled adaptability.\nCode availability enhances reproducibility.", "weaknesses": "1. Possibliity of Insufficient Related Work and Missing Key Comparisons\nThe paper seems to omit important recent work that directly challenges its novelty claims.\n- OnlineGCP (SIGMOD'23): Generalizes streaming CP to exponential family distributions (Poisson, Bernoulli), directly addressing SONATA's Gaussian limitation. Authors should discuss why Gaussian assumptions are sufficient or provide non-Gaussian extensions\n\n- SOFIA (ICDE'21): Incorporates seasonality + outlier/missing data robustness\n- OR-MSTC (IJCAI'19): Multi-aspect streaming with outlier separation via ADMM\nSONATA's robustness claims are unsupported without comparison to these methods\n\n- SBDT (ICML'21): Streaming Bayesian deep tensor factorization with spike-and-slab priors\nThe \"without deep neural networks\" claim needs explicit comparison to justify EP over deep Bayesian approaches\n\n2. Insufficient Ablation Studies to Support Synergistic\nThe paper does not demonstrate that all components are essential.\nTo support their claims, authors should conduct these experiment:\n-  Individually remove each coreset criterion (uncertainty/influence/novelty/martingale)\n-  Bellman optimization vs. greedy myopic policy (γ=0)\n-  EP vs. simpler online filters \n-  Matérn vs. simpler kernels (RBF, linear)\n\n3. Minor Issues\n- Coreset budget selection: Mmax seems manually tuned per dataset (100-3000 in Appendix B.1). they provide no principled guidance.\n- How does runtime scale with coreset size Mmax?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fycyE7Q0yC", "reviewer": "Reviewer_QPPP", "summary": "The paper presents SONATA, a streaming tensor factorization framework that models each factor trajectory with a linear dynamical system (LDS) and augments learning with a multi-criteria, martingale-guided coreset. The work integrates (i) continuous-time state-space priors for temporal dynamics and (ii) an online coreset selector that combines uncertainty, novelty, influence, and a martingale increment into a Bellman-optimized score under a fixed budget. Empirically, SONATA is evaluated on several real-world and synthetic datasets and generally attains lower RMSE/MAE than static and streaming baselines; the paper also reports per-iteration/epoch runtime, kernel/length-scale sensitivity, and additional experiments.", "questions": "Time-normalized comparisons. Please provide convergence curves for all methods and report each baseline’s accuracy at the same total runtime as SONATA. This would directly address efficiency/accuracy trade-offs. \n\nMemory and budget trade-offs. Please report memory usage and update time as functions of the coreset budget and include accuracy vs. budget curves on multiple datasets. As of now, no budget-sweep experiments are included, which makes it difficult to assess how performance scales with budget.\n\nAblations vs. simple heuristics. The appendix contrasts coreset selection to random sampling on one dataset. Could you add the same comparison across other datasets and summarize whether martingale-guided selection consistently outperforms random sampling at matched budgets? \n\nRobust defaults. The current sensitivity tables are promising but seem dataset-specific. Can the authors propose and validate robust default settings?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Well-motivated architecture. The combination of continuous-time LDS factors with an online coreset mechanism is coherent and addresses a meaningful streaming setting. The design is carefully tied to spatiotemporal structure via Matérn priors and a principled scoring rule. \n\nConsistent accuracy gains. Experiments report SONATA achieving the best or second-best error across multiple datasets compared to strong static and streaming baselines. \n\nUseful diagnostics of the coreset. Visual comparisons of coreset vs. non-coreset factor trajectories help understand what the selector retains.", "weaknesses": "Computational fairness. The paper reports per-iteration/epoch runtime for several methods (e.g., SONATA 0.338s, CT-CP 0.018s, CT-GP 0.105s, THIS-ODE 7.190s), but does not equalize wall-clock time across methods when comparing accuracy; faster methods could take many more iterations within the same time budget. \n\nCompute/memory analysis. The coreset budget directly affects memory footprint and update cost, yet the paper does not provide memory-usage vs. budget or throughput measurements to quantify the trade-off between retained samples and efficiency.\n\nAblations. The coreset analyses (full-data vs. coreset, random sampling) appear focused on a single dataset in the appendix; extending them to more datasets or reporting summary trends would better calibrate the benefits of the martingale-guided selector over simpler heuristics. \n\nHyperparameter. The method exposes several hyperparameters, with dataset-dependent choices. While the paper includes some sensitivity tables, systematic guidance for robust settings in realistic streaming scenarios is limited. \n\nReadability and consistency. The manuscript’s readability suffers in several places due to redundant wording and inconsistent cross-referencing. For example, equation mentions sometimes read like “Eq. equation” and there is mixing of styles (e.g., “Figure” vs. “Fig.”). Please standardize to a single reference style.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KIPiqMQEJn", "reviewer": "Reviewer_KKxL", "summary": "The authors propose SONATA, a novel framework that integrates expressive dynamic embedding modeling with adaptive coreset selection. SONATA employs principled machine learning techniques to efficiently evaluate each observation for uncertainty, novelty, influence, and information gain. It dynamically prioritizes learning from the most valuable data using Bellman-inspired optimization.", "questions": "The representation of SDE in Figure 1 is different from its descriptioin in this paper.\n\nI can not find the details of multi-scale feature extraction in this paper.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper integrates Linear Dynamical Systems (LDS) with temporal kernels to capture fine-grained and hierarchical temporal dependencies, addressing a key limitation of existing methods.\n\nIt enables adaptive representation of evolving patterns across different time scales (short-term vs. long-term dynamics).\n\nBellman-inspired optimization ensures optimal data selection, improving scalability for high-velocity streams.", "weaknesses": "While coreset selection improves efficiency, the evaluation of uncertainty, novelty, and influence for each observation may introduce latency in real-time systems.\n\nThe performance of temporal kernels and LDS models may depend heavily on hyperparameter tuning.\n\nPerformance may degrade with noisy or incomplete streams, as coreset selection relies on accurate uncertainty estimation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zm6X7Evnm4", "reviewer": "Reviewer_iw8e", "summary": "The paper introduces SONATA, a novel framework that integrates LDS-based dynamics, multi-faceted coreset selection, and online Bayesian inference for dynamic tensor stream analysis. It combines expressive temporal modeling with adaptive coreset selection to address two fundamental challenges: capturing complex, multi-scale temporal dependencies and achieving computational efficiency in high-velocity streaming settings. SONATA models entity embeddings using Linear Dynamical Systems with Matérn kernels  to represent multi-scale dynamics. Each entity’s latent state evolves via a stochastic differential equation, with embeddings projected linearly for tensor entry prediction under a CP decomposition structure. The proposed synergistic coreset selection strategy  frames selection as a sequential decision-making problem with four criterions that maintains a compact and informative subset of the stream. For inference, SONATA employs an online Expectation Propagation algorithm, where the coreset guides the update process by emphasizing high-value observations, enabling efficient and adaptive learning.\n\nExtensive experiments on synthetic and real-world datasets  demonstrate that SONATA consistently outperforms many static and streaming baselines in predictive accuracy (RMSE and MAE) while maintaining computational efficiency. Ablation studies further confirm the necessity of each coreset criterion and the framework’s robustness to hyperparameter variations. Overall, the paper offers an interesting solution for temporal tensor decomposition.", "questions": "1. Can this method be directly applied to data with irregularly sampled timesteps? If not, how could it be adapted to handle this more realistic scenario?\n\n2. The authors emphasize the computational efficiency of the proposed method but only report computational time. How does the method scale with respect to the number of data points?\n\n3. Why SONATA is able to capture multi-scale temporal dynamics, is there any special design?\n\n4. I am curious about the motivation for designing the importance score using four criteria: uncertainty, influence, novelty, and information increment. Could the authors provide further explanation? Conducting ablation studies on different combinations of these four criteria may better illustrate the design rationale.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper is well-written, clearly outlining the problem and the limitations of existing methods, proposing a solution, and demonstrating robust performance.\n\n2.The idea of a synergistic coreset selection strategy, specifically designed to capture evolving dynamics and ensure long-term utility, is  novel and well-motivated. It aims to enhance computational efficiency while  improving model performance.\n\n3.Experiments demonstrate strong performance against various baselines and robustness across a variety of datasets.\n\n4.The ablation study of synergistic coreset selection strategy is convincing and reasonable.", "weaknesses": "1. The use of Linear Dynamical Systems: the evolving parameters F,H,L are time-invariant, which limits the model’s expressiveness in capturing complex dynamics.\n\n2. Previous work has already employed SDE-represented Gaussian Processes to model the entities and enable streaming inference (e.g., SFTL; Fang et al., 2023), so the modeling is of fairly limited novelty.\n\n3. The scalibity of the proposed method over data size has not been explored in experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)