Andrii Bidochko

• Updated: July 5, 2026
• 7 min read

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

Direct Answer

The paper introduces SqLinear, a two‑stage architecture that first partitions city‑wide traffic sensors into balanced, near‑square regions and then models spatio‑temporal dynamics with a lightweight Hierarchical Linear Interaction (HLI) module. By replacing costly attention mechanisms with linear operations, SqLinear delivers higher prediction accuracy while cutting training time by up to 30 % on datasets with tens of thousands of sensors.

Background: Why This Problem Is Hard

Urban traffic forecasting sits at the core of intelligent transportation systems, enabling real‑time routing, congestion pricing, and city‑scale planning. The practical challenge stems from three intertwined factors:

• Sensor density: Modern smart‑city deployments can exceed 20,000 loop detectors, Bluetooth beacons, and camera‑derived speed sensors.
• Spatio‑temporal complexity: Traffic flow exhibits strong local interactions (e.g., a bottleneck on a single road) and long‑range dependencies (e.g., upstream demand affecting downstream corridors).
• Computational budget: Real‑time prediction pipelines must ingest fresh data every few minutes, leaving limited time for heavy neural‑network inference.

Existing deep‑learning solutions—graph neural networks, convolutional‑Transformer hybrids, and diffusion models—typically assume a fixed, relatively small graph. To scale, researchers have borrowed spatial database partitioning techniques such as uniform grids, quad‑trees, or K‑D trees. While these heuristics reduce the size of each sub‑graph, they suffer from two critical drawbacks:

1. Irregular partitions: Hand‑crafted splits often generate elongated or highly imbalanced regions, inflating the number of boundary sensors that must be duplicated (padding) across partitions.
2. Fragmented dynamics: When a traffic corridor straddles multiple partitions, the model loses continuity, leading to degraded forecasting accuracy.

Consequently, the industry faces a scalability‑accuracy trade‑off that hampers deployment of AI‑driven traffic management at the city level.

What the Researchers Propose

SqLinear tackles the scalability bottleneck with two complementary ideas:

1. Square Partition – Geometry‑Adaptive Region Splitting

Instead of relying on ad‑hoc heuristics, the authors formulate a provably optimal partitioning problem. The algorithm recursively divides the sensor map into rectangular cells that satisfy three guarantees:

• Aspect‑ratio bound: Each cell’s width‑to‑height ratio stays close to 1, ensuring near‑square shapes.
• Balance constraint: The number of sensors per cell differs by at most a constant factor, preventing overloaded partitions.
• Utilization ceiling: Empty space inside a cell is minimized, which reduces the need for zero‑padding during batch processing.

The result is a set of non‑overlapping, spatially coherent regions that preserve the natural topology of road networks while remaining computationally friendly.

2. Hierarchical Linear Interaction (HLI) – Efficient Spatio‑Temporal Modeling

Traditional Transformer‑based traffic models rely on multi‑head attention to capture global dependencies, incurring O(N²) complexity where N is the number of sensors. HLI replaces attention with a two‑level linear scheme:

1. Intra‑region linear dynamics: Within each square partition, a lightweight linear layer (essentially a matrix multiplication) learns short‑range temporal patterns.
2. Inter‑region aggregation: A second linear transformation aggregates summaries from all regions, allowing the model to reason about city‑wide traffic flow without quadratic cost.

Because linear operations are highly parallelizable on modern GPUs, HLI scales linearly with the number of sensors, delivering comparable expressive power to attention at a fraction of the compute budget.

How It Works in Practice

The end‑to‑end workflow of SqLinear can be broken down into four stages, each of which maps cleanly onto existing data pipelines used by transportation agencies.

Stage 1 – Data Ingestion & Pre‑processing

Raw sensor streams (speed, volume, occupancy) are synchronized to a common timestamp grid (e.g., 5‑minute intervals). Missing values are imputed using simple temporal interpolation, and each sensor is assigned geographic coordinates.

Stage 2 – Square Partition Generation

The geometry‑adaptive algorithm receives the coordinate list and a target cell size (e.g., ~500 sensors per region). It outputs a mapping table:

  sensor_id | region_id
  ----------|---------
  10234     | R07
  10235     | R07
  …         | …
  

This table is stored alongside the time‑series data, enabling downstream models to fetch region‑specific batches without cross‑region joins.

Stage 3 – Hierarchical Linear Interaction Modeling

Training proceeds in two nested loops:

• Local loop: For each region, a linear temporal encoder processes the region’s sensor matrix (time × sensors) and produces a latent representation.
• Global loop: All regional latents are stacked and passed through a second linear layer that learns how regions influence one another (e.g., upstream‑downstream traffic).

The final output is a forecast matrix covering the desired horizon (e.g., next 30 minutes) for every sensor.

Stage 4 – Deployment & Real‑Time Inference

Because both stages consist of matrix multiplications, inference can be executed in a single GPU kernel. The system can therefore ingest fresh sensor readings, map them to regions, and emit city‑wide predictions within seconds—well within the latency budget of most traffic‑control centers.

Evaluation & Results

The authors benchmarked SqLinear on four publicly available, large‑scale traffic datasets covering cities with 5 k–30 k sensors. They compared against ten strong baselines, including Graph WaveNet, ST‑Transformer, and hierarchical GNNs. Evaluation focused on two axes:

Prediction Accuracy

• SqLinear reduced Mean Absolute Error (MAE) by an average of 2.30 % under standard training conditions.
• When the number of sensors was artificially inflated to stress scalability, the MAE improvement grew to 5.81 %, indicating robustness to extreme data volumes.

Computational Efficiency

• Training time per epoch dropped between 13.27 % and 30.84 % compared to the best‑performing Transformer baseline.
• Memory consumption decreased proportionally because the linear interaction eliminates the quadratic attention matrix.

These results demonstrate that SqLinear not only preserves—or even improves—forecast quality but also delivers tangible cost savings, a critical factor for municipal budgets.

Why This Matters for AI Systems and Agents

Scalable traffic prediction is more than a niche academic problem; it underpins a growing ecosystem of AI‑driven agents that manage urban mobility. The implications of SqLinear’s design choices ripple through several practical domains:

• Real‑time routing assistants: Navigation apps can query a city‑wide forecast service every few minutes, allowing agents to reroute drivers before congestion materializes.
• Dynamic pricing engines: Congestion‑charging platforms rely on accurate short‑term demand estimates to adjust tolls on the fly; lower latency models enable finer granularity.
• Autonomous fleet orchestration: Ride‑hailing and delivery bots need to anticipate traffic hotspots to allocate resources efficiently; a linear‑time predictor scales with fleet size.
• Simulation‑in‑the‑loop testing: Urban planners can embed SqLinear into digital twins, running thousands of “what‑if” scenarios without prohibitive compute costs.

From an engineering perspective, the architecture aligns well with modern UBOS platform overview, which emphasizes modular pipelines and GPU‑accelerated linear algebra. Teams can plug the Square Partition step into existing data ingestion workflows, then expose the HLI model as a microservice for downstream agents.

What Comes Next

While SqLinear marks a significant step forward, several avenues remain open for exploration:

Limitations

• Static partitioning: The current algorithm computes regions once offline. Rapid urban development or temporary road closures could invalidate the partition, suggesting a need for adaptive re‑partitioning.
• Linear interaction expressiveness: Although HLI matches attention on benchmark datasets, extreme non‑linear phenomena (e.g., accidents causing sudden shockwaves) may still benefit from hybrid attention‑linear designs.

Future Research Directions

• Integrating Chroma DB integration to store region embeddings for fast retrieval across multiple forecasting horizons.
• Extending the framework to multimodal inputs (e.g., weather, events) by augmenting the intra‑region linear encoder with lightweight feature fusion layers.
• Exploring reinforcement‑learning agents that consume SqLinear forecasts to optimize traffic signal timing in a closed‑loop fashion.

Potential Applications Beyond Traffic

The Square Partition + HLI paradigm is domain‑agnostic. Any large‑scale sensor network—smart grids, environmental monitoring, or retail foot‑traffic analytics—could adopt the same pipeline to achieve linear‑time forecasting.

For organizations looking to prototype such solutions quickly, the Enterprise AI platform by UBOS offers pre‑built connectors for streaming data, GPU orchestration, and model serving, making it straightforward to spin up a SqLinear‑style service.

References

For a complete technical description, see the original arXiv paper.

Andrii Bidochko

CTO UBOS

Andrii Bidochko is an AI entrepreneur and researcher focused on AI agents, reinforcement learning, and autonomous systems. He writes about the technologies shaping the future of machine intelligence, from frontier models and agent architectures to real-world AI applications.