Abstract
Time series imputation is a fundamental task for understanding time series with missing data. Existing methods either do not directly handle irregularly-sampled data or degrade severely with sparsely observed data. In this work, we reformulate time series as permutation-equivariant sets and propose a novel imputation model NRTSI that does not impose any recurrent structures. Taking advantage of the permutation equivariant formulation, we design a principled and efficient hierarchical imputation procedure. In addition, NRTSI can directly handle irregularly-sampled time series, perform multiple-mode stochastic imputation, and handle data with partially observed dimensions. Empirically, we show that NRTSI achieves state-of-the-art performance across a wide range of time series imputation benchmarks.
The Challenge of Recurrent Imputation
Missing data is a pervasive issue in real-world time series analysis, ranging from sensor failures in industrial settings to missed clinical appointments. Traditionally, researchers have turned to Recurrent Neural Networks (RNNs) to fill these gaps. However, RNNs suffer from two critical limitations:
- Error Compounding: Because RNNs impute data sequentially (e.g., $t=1$, then $t=2$), a small error in an early prediction snowballs as the model uses its own faulty outputs to generate future values.
- Rigidity: Standard RNNs assume fixed time intervals. While specialized variants like Neural ODEs can handle irregular data, they are computationally intensive and still rely on the same sequential processing that leads to error accumulation.
NRTSI (Non-Recurrent Time Series Imputation) challenges this paradigm by asking: Do we really need to process time series in chronological order to fill in the blanks?
NRTSI: A Non-Recurrent Set-Based Approach
NRTSI breaks the mold by reinterpreting a time series not as a sequence, but as a permutation-equivariant set of (timestamp, value) tuples. By treating time as an input feature rather than a structural constraint, the model decouples the temporal order of the data from the computational order of the imputation.
At its core, NRTSI leverages a Transformer-based architecture. Since Transformers use self-attention to relate every point in a set to every other point, they are naturally suited for this non-recurrent approach. This allows the model to use "future" observations to help impute "past" missing values just as easily as the reverse, providing a global context that RNNs lack.
Hierarchical "Coarse-to-Fine" Strategy
Instead of filling in missing values from left to right, NRTSI employs a clever hierarchical imputation procedure. It first identifies the missing points with the largest "gaps"—those farthest from any observed data—and fills them in to act as anchors. It then progressively fills in smaller gaps in a "coarse-to-fine" manner.
This "divide and conquer" strategy significantly reduces the number of steps where errors can accumulate. By establishing a reliable "scaffold" of anchor points early on, the final fine-grained imputations become much more accurate.
Performance and Versatility
NRTSI was evaluated against a wide array of benchmarks, including physics simulations (Billiards, MuJoCo), traffic data (PEMS-SF), and stochastic human movement (NFL trajectories). The results demonstrate a significant leap over previous state-of-the-art models like NAOMI and Latent-ODE:
- Superior Accuracy: On the Billiards trajectory dataset, NRTSI reduced L2 loss by 64% compared to the previous best model.
- Handling Irregularity: On irregularly sampled data, NRTSI achieved an MSE of 0.042, dwarfing the nearest competitor's score of 1.121.
- Efficiency: Despite its architectural depth, NRTSI often runs faster than recurrent models because it can process multiple points in parallel at each level of the hierarchy.
- Robustness: The model remains highly effective even when up to 80% of the data is missing, and it naturally handles partially observed dimensions where only some features are present at a given timestamp.
Conclusion
By moving away from sequential recurrence and embracing a set-based, hierarchical Transformer architecture, NRTSI avoids the pitfalls of error compounding and rigid sampling requirements. While future work may look into scaling the $O(L^2)$ complexity of standard self-attention for extremely long sequences, NRTSI currently represents a major advancement in the accuracy and flexibility of time series imputation.
Summary updated