SqLinear: Balanced Square Partitioning Makes Linear Interaction Sufficient for Large-Scale Traffic Forecasting

arXiv:2606.21072v2 Announce Type: replace Abstract: Traffic prediction is a core task in intelligent transportation systems and urban-scale decision making. Despite the effectiveness of mainstream neural network-based methods, their deployment in real-world settings with thousands of traffic sensors is severely jeopardized by their poor computational scalability. To address this, the community has attempted to incorporate spatial database partitioning techniques to improve model scalability. However, these approaches rely on handcrafted geometric heuristics and often produce irregular or imbalanced data partitions, leading to boundary fragmentation, excessive padding overheads, and degraded model accuracy. In this paper, we propose SqLinear, an efficient and effective architecture for large-scale traffic prediction. First, we design Square Partition, a geometry-adaptive algorithm that partitions massive traffic sensors into balanced, non-overlapping, and compact spatial regions. Unlike existing heuristic-based designs, Square Partition is theoretically grounded and provides provable guarantees on partition utilization and split balance, establishing a high-quality foundation for downstream spatio-temporal modeling. Next, we propose a Hierarchical Linear Interaction (HLI) module that abandons the costly attention mechanisms commonly used in Transformer-based spatio-temporal models. HLI efficiently propagates global inter-region dependencies and refines them at the node level through a lightweight linear interaction scheme, enabling effective spatio-temporal modeling with linear computational complexity. Extensive experiments on four large-scale traffic datasets and 11 baselines show that SqLinear reduces MAE by 2.30% on average under the standard setting and by up to 6.78% under extreme scalability settings, while reducing training runtime by 13.27%--30.84% in spatial- and horizon-scaling scenarios.

Abstract:Traffic prediction is a core task in intelligent transportation systems and urban-scale decision making. Despite the effectiveness of mainstream neural network-based methods, their deployment in real-world settings with thousands of traffic sensors is severely jeopardized by their poor computational scalability. To address this, the community has attempted to incorporate spatial database partitioning techniques to improve model scalability. However, these approaches rely on handcrafted geometric heuristics and often produce irregular or imbalanced data partitions, leading to boundary fragmentation, excessive padding overheads, and degraded model accuracy. In this paper, we propose SqLinear, an efficient and effective architecture for large-scale traffic prediction. First, we design Square Partition, a geometry-adaptive algorithm that partitions massive traffic sensors into balanced, non-overlapping, and compact spatial regions. Unlike existing heuristic-based designs, Square Partition is theoretically grounded and provides provable guarantees on partition utilization and split balance, establishing a high-quality foundation for downstream spatio-temporal modeling. Next, we propose a Hierarchical Linear Interaction (HLI) module that abandons the costly attention mechanisms commonly used in Transformer-based spatio-temporal models. HLI efficiently propagates global inter-region dependencies and refines them at the node level through a lightweight linear interaction scheme, enabling effective spatio-temporal modeling with linear computational complexity. Extensive experiments on four large-scale traffic datasets and 11 baselines show that SqLinear reduces MAE by 2.30% on average under the standard setting and by up to 6.78% under extreme scalability settings, while reducing training runtime by 13.27%--30.84% in spatial- and horizon-scaling scenarios.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

arXiv:2606.21072 [cs.LG]

(or arXiv:2606.21072v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2606.21072 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

SqLinear: Balanced Square Partitioning Makes Linear Interaction Sufficient for Large-Scale Traffic Forecasting

Related coverage