{"id":"3b50ed55-c963-46b1-8d56-0a9e4fe8374b","arxiv_id":"2606.21072","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A linear-complexity architecture with balanced square partitioning and hierarchical low-rank linear interactions outperforms attention/graph baselines on four large-scale traffic forecasting datasets.","lead":"SqLinear splits city-scale traffic sensor networks into balanced, padding-free spatial patches using a geometry-adaptive longest-span partition, then models inter- and intra-patch dependencies with a low-rank linear interaction module instead of attention. On four large traffic datasets it reports lower MAE than ten baselines while scaling linearly in sensor count, offering a practical route to forecasting with tens of thousands of sensors.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Low-rank inter-patch projection is load-bearing, but support is only marginal spectral decay and the paper's own D.6 limitation admits failure on incident-driven dynamics; a rank-ablation test would settle it.","rationale":"The reader's weakest-assumption analysis is correct but understated. The low-rank assumption is not merely 'without a dataset-independent guarantee'; the provided evidence is the wrong kind of evidence. Theorem C.7 restates Eckart-Young and cannot be falsified; Fig. 3's spectral decay of observed patch states mostly measures periodicity and spatial autocorrelation, not the conditional rank of the predictive mapping. The paper's D.6 limitation explicitly concedes that the linear module may fail on abrupt dynamics (accidents), which are exactly the high-rank, non-redundant interactions that attention is designed to model. All four benchmarks are California freeway networks from the LargeST benchmark, so they share a congestion regime; the claim of general 'large-scale traffic forecasting' sufficiency goes beyond the evidence. That said, the paper has independent support: the w/Attn ablation on GBA/CA shows attention does not improve over HLI in those settings, and the complexity analysis is essentially correct (up to a missing C factor in the O(dPr) term, which does not affect the linear-in-N headline). A rank sweep is the cleanest way to decide whether the low-rank truncation is actually the capacity bottleneck. If the sweep shows convergence by the chosen r, the central claim survives on these benchmarks; if not, the accuracy gains are an artifact of the rank choice and the paper should be conditional on reporting r and validating on more diverse networks. Because the reader already marked CONDITIONAL, my read does not change the verdict.","tokens_in":28106,"tokens_out":8714,"duration_ms":103910,"concrete_test":"On CA (or on an unseen urban-arterial dataset), fix C and L at the paper's values and sweep the inter-patch rank r from 1 to C and to P (full rank) while retraining SqLinear; plot test MAE vs r. If MAE still decreases by more than the reported baseline margin (≈0.3 on CA / 2.3% average) as r approaches C/P, the low-rank projection in Eq. (11) is the load-bearing capacity bottleneck. Also record the r used in Table 2, which the paper currently omits.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central accuracy claim — that linear interaction can replace attention — hinges on Eq. (11)'s rank-r inter-patch projection. Theorem C.7 is a correct but tautological Eckart-Young identity: it bounds the approximation error only by the tail singular values of an 'ideal' dependency matrix M, and it says nothing about whether that tail is small for the predictive task. The empirical support (Fig. 3) is spectral decay of patch-wise dependency matrices, but if these are marginal covariance/correlation matrices of observed traffic states, the decay mostly reflects strong daily periodicity and freeway-wide congestion; it does not bound the rank of the conditional dependency needed for forecasting, e.g., the residual dynamics after removing periodic components or the interactions activated by incidents. The paper's own D.6 limitation admits 'limited capacity to model abrupt and highly nonlinear dynamics, such as those caused by traffic accidents.' All four benchmarks are California freeway sensor networks with similar free-flow/congestion regimes, so the low-rank observation may not transfer to dense urban arterials with many weakly coupled independent roads. The rank r used in experiments is not reported, and no error bars are given, so it is impossible to tell whether the reported margins are robust to the rank choice. This is not an internal contradiction of the derivation, but an unproven empirical precondition of the title claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SqLinear, a traffic-forecasting architecture that combines a geometry-adaptive square partitioning algorithm with a hierarchical linear interaction (HLI) module. The partition algorithm recursively splits sensor nodes along their longest spatial span using capacity-aware split points, producing balanced, non-overlapping, near-square patches without padding when the total node count is an exact multiple of the leaf capacity. The HLI module replaces quadratic-complexity attention with a linear inter-patch low-rank projection plus an intra-patch linear refinement, achieving O(N d^2) time and O(N d) memory. The paper reports state-of-the-art accuracy on four LargeST benchmarks, including an average 2.30% MAE reduction over PatchSTG under the standard 12-step setting and an average 5.81% MAE reduction over strong baselines in long-horizon (96=>672) settings, with reduced training runtime. Theoretical results cover partition utilization, split balance, non-amplification of elongation, low-rank approximation capacity, expressiveness relative to linear baselines, and complexity.","tokens_in":28459,"tokens_out":6476,"duration_ms":69304,"significance":"If the empirical results hold, SqLinear is a practically valuable contribution: it demonstrates that, on large freeway sensor networks, a carefully designed linear-complexity model can outperform attention- and graph-based state-of-the-art baselines, addressing a real scalability bottleneck for city-scale traffic forecasting. The paper's strengths include a principled partitioning scheme with explicit theoretical guarantees (Theorems C.2, C.4, C.6), a clear complexity analysis, extensive experiments across four datasets and ten baselines, and a complete long-horizon study covering 16 dataset-horizon combinations. The central empirical claim is well supported by the reported tables. However, the title-level claim that linear interaction is 'sufficient' for large-scale traffic forecasting is broader than what the evidence supports: the low-rank inter-patch assumption is only weakly validated, the padding-free property is conditional on N=PC, and the paper itself acknowledges a limitation on incident-driven dynamics. These issues are fixable within the scope of a revision.","major_comments":[{"comment":"The central accuracy claim depends on the low-rank inter-patch projection. Theorem C.7 is a correct Eckart-Young identity, but it only states that the best rank-r approximation error equals the tail singular-value energy of an 'ideal' dependency matrix M; it does not establish that the tail is small for the forecasting task. Figure 3 shows spectral decay of observed patch-wise dependency matrices, but such decay is dominated by strong daily periodicity and regional congestion and does not bound the rank of the conditional dependencies needed for prediction (e.g., residual dynamics after removing periodic components or incident-activated correlations). Moreover, the rank r is not reported anywhere in the experiments, and no error bars are given. It is therefore impossible to assess whether the reported 2.30% average improvement is robust to the choice of r. Please report the value of r us","section":"§4.3.1, Eq. (11), Theorem C.7, Figure 3"},{"comment":"The padding-free guarantee is explicitly conditional on C being selected such that N=PC. For an arbitrary sensor network, such a C may not exist (e.g., if N is prime, the only exact divisors are C=1 and C=N, neither of which yields a useful partition). The abstract and Section 1 claim that SqLinear works 'without performing padding operations' as a general property, and the efficiency comparison against PatchSTG's 43% padding overhead relies on this. Please either state the N=PC condition prominently in the contribution claims or describe a fallback for non-divisible N (e.g., allowing at most one partially filled patch with bounded overhead). As written, the padding-free contribution is narrower than it appears.","section":"§4.2, Theorem C.2, Abstract"},{"comment":"The paper admits in D.6 that the linear interaction module 'may have limited capacity to model abrupt and highly nonlinear dynamics, such as those caused by traffic accidents.' This directly qualifies the title claim that balanced square partitioning 'makes linear interaction sufficient' for large-scale traffic forecasting. All four benchmarks are California freeway sensor networks with similar free-flow/congestion regimes; the low-rank and linear-sufficiency evidence may not transfer to dense urban arterials with many weakly coupled independent roads or to incident-rich settings. Please scope the central claim to recurrent congestion dynamics on freeway-scale sensor networks, and discuss whether the architecture can be extended to incident scenarios (e.g., a hybrid linear-nonlinear module). Without such qualification, the 'sufficient' wording overstates the demonstrated scope.","section":"Appendix D.6, Title, Abstract"}],"minor_comments":[{"comment":"The abstract is inconsistent: it says '10 baselines' in the full text but '11 baselines' in the header version, and 'reduces MAE by 5.81%' versus 'up to 6.78%' in different places. Please unify these numbers.","section":"Abstract and §5.3"},{"comment":"Typo: 'SqarePartition' should be 'SquarePartition'.","section":"Algorithm 1, line 15"},{"comment":"The spatial embedding uses 'X_P' in the algorithm but Eq. (4) uses X_H. Please align the notation.","section":"Algorithm 2, line 4"},{"comment":"Please specify how the patch-wise dependency matrix is computed (e.g., covariance or correlation of which input features, which layer/aggregation), and define the 'cumulative variance' precisely. This is needed to interpret the low-rank motivation.","section":"Figure 3"},{"comment":"The rank is denoted r in Eq. (11) and Theorem C.7 but k in Figure 8 and Appendix D.3. Unify the notation.","section":"Notation"},{"comment":"The statement that 'the additional intra-patch operator makes HLI strictly more expressive' is not established by the proof sketch, which shows only containment of linear mixing operator classes. Please state the precise sense of expressiveness and prove strictness, or soften the claim.","section":"Theorem C.8"},{"comment":"The Topology-First Road Grouping (TFRG) variant can generate highly imbalanced groups (e.g., a long highway vs. a short ramp), yet no theoretical or empirical analysis of its balance is provided. Please add a discussion of its limitations, especially since the paper's main contribution is balanced partitioning.","section":"§4.5.2 and Figure 9"},{"comment":"Aspect ratios are computed from raw longitude/latitude degrees. Please clarify whether an equal-area projection was used; unprojected degrees can distort aspect ratios, especially at the latitude of California.","section":"Table 7"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid systems-oriented contribution with correct but conditional theoretical claims. The main risk is the unqualified 'sufficient' claim in the title and abstract, which is not fully supported by the empirical evidence (missing rank reporting, no error bars, and the admitted limitation on incident dynamics). The requested additions—a rank ablation, error bars, reporting of r, and a scoped claim—are within the scope of a revision and should make the contribution publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuinely useful architecture paper. The Square Partition is essentially a capacity-aware longest-span k-d tree with a split point chosen to make N=PC exactly, which gives padding-free tensorization. That is a real, simple improvement over PatchSTG's padded K-D tree leaves, and the ablations show it matters. The HLI module is a reasonable linear substitute for attention: rank-r inter-patch projection plus intra-patch MLP, O(N d^2) time, O(N d) memory. The complexity analysis is correct. The empirical work is thorough: four LargeST datasets, standard and long horizons, ablations, runtime/memory, hyperparameter sensitivity. Tables 2 and 6 support the headline numbers. The speedups are modest but real.\n\nThe theory is honest, which I appreciate. Theorem C.2 is conditional on N=PC; C.4 gives split balance below 2C; C.6 says the partition does not amplify elongation, not that it guarantees near-square shapes. The abstract overclaims 'provable guarantees on aspect ratio' when the paper's own definition treats aspect ratio as an empirical diagnostic. That mismatch should be fixed in revision.\n\nThe soft spot is the one the stress-test flags. The load-bearing claim is that the P x P inter-patch dependency matrix is approximately low-rank, and the support is spectral decay of observed covariance plus an Eckart-Young bound that is true but tautological. Figure 3 shows fast decay, which is credible for freeway networks with strong periodicity. But incidents and weakly coupled independent arterials are exactly the kind of high-rank residual that low-rank projection will miss. The paper's own D.6 admits limited capacity for abrupt, nonlinear dynamics. That is not fatal for the paper's scope, but it means 'linear interaction sufficient' is established only for the four benchmark freeway networks, not as a general law. Also missing: the rank r used in experiments is never reported, and there are no error bars or code release. Those are addressable, not fatal.\n\nWho this is for: anyone working on scalable spatio-temporal forecasting will want to read it. It deserves a serious referee—the claims are concrete, the methodology is reproducible in principle, and the comparison to PatchSTG is fair. I would send it to review, with a request to report r, add error bars or at least multiple seeds, and either run one dense urban dataset or soften the generalization claims.","headline":"SqLinear is a solid, well-run empirical architecture paper whose central bet—that inter-patch dependencies are low-rank—holds up on these four freeway benchmarks but is not yet shown to transfer to dense urban networks.","tokens_in":28970,"tokens_out":1372,"would_cite":true,"duration_ms":15873,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"SqLinear shows that a balanced, padding-free square partition of traffic sensors plus a low-rank linear interaction module can replace attention and beat state-of-the-art baselines on large-scale traffic forecasting benchmarks.","keywords":["large-scale traffic forecasting","spatial partitioning","square partition","hierarchical linear interaction","low-rank projection","linear complexity","traffic prediction","spatio-temporal modeling"],"falsifier":"Compute the singular-value spectrum of the empirical patch-wise dependency matrix on a new large-scale traffic dataset with many independent, non-synchronized arterial corridors (rather than the studied metropolitan networks). If the tail energy beyond a practical rank r (say r ≈ 10–50) is large—for instance, if top-r components capture well under 90% of variance—then the low-rank inter-patch operator loses information a full attention matrix would retain, and the accuracy advantage over attention-based models should shrink or invert. Alternatively, run SqLinear with r set to full rank P: if a","tokens_in":27988,"feed_emoji":"🚦","tokens_out":5604,"duration_ms":58370,"temperature":0.7,"pith_summary":"This paper argues that expensive attention mechanisms are unnecessary for large-scale traffic forecasting if the sensor network is first reorganized into compact, balanced, padding-free spatial patches. On top of that partition, a hierarchical linear interaction—low-rank global mixing across patches plus local linear mixing within each patch—captures both long-range and short-range dependencies at linear computational cost. The authors prove the partition yields full utilization, bounded imbalance, and no elongation amplification, and they show the low-rank projection's error reduces to the tail energy of a rapidly decaying spectral distribution. Empirically, the architecture reduces mean absolute error by 2.30% on average under standard 12-step forecasting and by 5.81% under long horizons (up to 672 steps), while cutting training runtime by 13%–31%. A sympathetic reader would care because this makes city-scale traffic prediction practical without sacrificing accuracy.","feed_headline":"Balanced square partitioning makes linear traffic forecasting sufficient","feed_subtitle":"A rank-r linear interaction replaces attention, cutting MAE by 2.3% and training runtime by up to 31%.","key_machinery":"The load-bearing components are (1) Square Partition and (2) the Hierarchical Linear Interaction (HLI) block. Square Partition recursively splits nodes along the axis with the larger geographic span, sorts along that axis, and chooses split points as multiples of a capacity C (Sp = C·ceil(ceil(N/C)/2)). This guarantees padding-free tensorization when N = P·C, split imbalance below 2C, and no amplification of elongation. The resulting patches are non-overlapping, approximately square, and map directly to tensors of shape C×P×d. HLI replaces attention with two linear stages: an inter-patch stage that aligns corresponding nodes across patches, applies a linear MLP, and communicates globally thr","core_discovery":"The central claim is that a well-chosen spatial partition, not a more expressive interaction layer, is what unlocks scalable traffic forecasting. The Square Partition algorithm recursively splits the sensor set along the currently longest geographic span, choosing split positions as multiples of a leaf capacity C, so each resulting patch has exactly C nodes (no padding), the split imbalance stays below 2C, and the effective aspect ratio is not systematically amplified. On this layout, the Hierarchical Linear Interaction block propagates global dependencies through a low-rank projection Θ_r1 Θ_r2 with rank r < C < P, then refines local features with a per-patch linear MLP, achieving O(Nd²) ti","pith_inferences":["I infer the method's effectiveness hinges on the assumption that inter-patch traffic correlations are approximately low-rank; on networks with many spatially interleaved but functionally independent corridors, a full-rank or attention-based interaction would likely retain an accuracy advantage, which is a testable boundary condition.","The Square Partition index depends only on sensor coordinates and capacity, so I would expect it to serve as a drop-in preprocessing step for other spatio-temporal models, improving their scalability without retraining the partitioner.","Because HLI's weights are linear matrices, the learned spatial dependencies are directly interpretable; I infer this opens a route to explainable traffic forecasting and to anomaly detection by monitoring weight drift over time.","The paper's topology-aware extensions suggest that for road networks where geometric proximity is a poor proxy for traffic coupling, the geometry-first or topology-first partitioning variants would be the appropriate fallbacks—though the current experiments show pure geometric partitioning already wins on the tested datasets."],"forward_implications":["City-scale traffic forecasting with thousands of sensors can run at linear complexity without sacrificing accuracy—O(Nd²) time and O(Nd) memory—making deployment on large networks feasible.","Replacing attention with hierarchical linear interaction is safe when the spatial partition is well constructed; the ablation study shows the attention variant does not outperform the linear HLI while consuming more compute.","The rank r of the inter-patch projection serves as an accuracy–efficiency dial: moderate r is sufficient because patch-level dependency spectra decay quickly on the studied datasets.","The partition's guarantees—full utilization, perfect balance, no padding—transfer to any sensor layout approximated by coordinates, suggesting applicability beyond traffic (e.g., environmental or energy monitoring).","The accuracy gain over baselines remains stable as the forecast horizon extends to 672 steps, indicating the learned spatial representation does not degrade with longer prediction ranges."],"fun_headline_variants":["Provable partitioning makes linear traffic forecasting work","Replace attention with linear interaction: 2.3% MAE gain","Balanced square splits boost linear traffic forecast accuracy","SqLinear: Linear complexity traffic forecasting without attention"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The result holds only if the dependency matrix among spatial patches is approximately low-rank—i.e., the top few latent components capture most of the inter-patch correlation variance—so that replacing the full P×P coupling with a rank-r projection loses negligible information.","fun_headline_variants_meta":{"raw":{"variants":["Provable partitioning makes linear traffic forecasting work","Replace attention with linear interaction: 2.3% MAE gain","Balanced square splits boost linear traffic forecast accuracy","SqLinear: Linear complexity traffic forecasting without attention"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00022,"raw_usage":{"total_tokens":1325,"prompt_tokens":829,"completion_tokens":496,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":432}},"tokens_in":573,"tokens_out":496,"duration_ms":5902,"temperature":1.0,"reasoning_tokens":432,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T02:04:33.727858+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the singular-value spectrum of the empirical patch-wise dependency matrix on a new large-scale traffic dataset with many independent, non-synchronized arterial corridors (rather than the studied metropolitan networks). If the tail energy beyond a practical rank r (say r ≈ 10–50) is large—for instance, if top-r components capture well under 90% of variance—then the low-rank inter-patch operator loses information a full attention matrix would retain, and the accuracy advantage over attention-based models should shrink or invert. Alternatively, run SqLinear with r set to full rank P: if a","supporting_citations":[],"review_version":2}