An Efficient and Effective Architecture for Large-Scale Traffic Prediction via Geometry-Adaptive Square Partitioning

Researchers introduce SqLinear, a neural network architecture that improves traffic prediction scalability by replacing attention mechanisms with efficient linear interactions and using a geometry-adaptive partitioning algorithm. The approach achieves 2.3-5.8% accuracy improvements while reducing training time by up to 30.8% on large-scale traffic datasets.

Traffic prediction systems face a fundamental tension between model accuracy and computational feasibility at scale. While Transformer-based approaches with attention mechanisms excel at capturing complex spatiotemporal patterns, their quadratic computational complexity becomes prohibitive when processing thousands of sensors simultaneously. SqLinear addresses this bottleneck through two complementary innovations that challenge prevailing architectural assumptions in the field.

The Square Partition algorithm represents a departure from heuristic-based spatial decomposition methods like Grids and K-D Trees. Rather than relying on handcrafted rules that produce irregular partitions and boundary artifacts, it provides theoretically-grounded guarantees on balance, aspect ratio, and utilization efficiency. This principled approach eliminates the ad-hoc quality variations that plague existing partitioning strategies, creating uniform data structures suitable for scalable processing.

The Hierarchical Linear Interaction module eliminates attention mechanisms entirely, replacing them with lightweight linear operations that maintain both local and global spatial awareness. This architectural shift reduces computational complexity from quadratic to linear while paradoxically improving prediction accuracy, suggesting that attention's costly reweighting operations may be unnecessary for traffic dynamics. The 13-30% runtime reductions across scaling scenarios demonstrate practical benefits beyond incremental optimization.

The implications extend across urban computing infrastructure. Cities managing thousands of traffic sensors benefit from faster, more accurate predictions enabling real-time traffic management and congestion mitigation. The approach establishes a template for rethinking neural architectures where computational efficiency and model performance need not be mutually exclusive, with potential applications in other large-scale spatiotemporal domains.

• →SqLinear achieves 2.3-5.8% MAE improvement while reducing training runtime by 13-30% through linear interaction mechanisms.
• →Geometry-adaptive Square Partition algorithm replaces heuristic partitioning with theoretically-grounded spatial decomposition.
• →Eliminating attention mechanisms maintains or improves accuracy while dramatically reducing computational complexity.
• →Architecture demonstrates practical scalability for real-world traffic sensor networks with thousands of monitoring points.
• →Linear-complexity design enables efficient deployment in resource-constrained urban computing environments.