{"id":"05cead2d-0dea-4ac3-8cdd-a9fcb4a35e04","arxiv_id":"2412.09972","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"PatchSTG uses a leaf KDTree to patch irregular traffic sensor points and a dual depth/breadth attention encoder to forecast traffic at large scale with state-of-the-art accuracy and large efficiency gains.","lead":"A new traffic forecasting model, PatchSTG, groups thousands of irregularly placed road sensors into balanced patches and runs attention only within and across patches, cutting training time and memory versus full pairwise models. It reports the lowest errors on four city-scale traffic datasets while using up to 10x less training time and 4x less memory than prior dynamic spatial models.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Efficiency claim hinges on unaccounted per-batch padding cost and a false M≈N assumption; profile Eq. 5 to settle it.","rationale":"The reader's weakest assumption identifies the same issue I consider most load-bearing: the efficiency claim depends on an incomplete complexity analysis and an omitted padding cost. I verified the arithmetic independently. For CA, the paper sets N=8600, leaf capacity C=3, and R=512 patches; the padded token count is the smallest multiple of C that is a power-of-two multiple of C and at least N, namely 3*4096=12288, so P=24 and M is 43% larger than N. For GBA and SD the inflation is even larger. This falsifies the M≈N statement in Section 4.5, although the method still remains sub-quadratic in N. The more serious gap is Eq. 5: the padding selection uses cosine similarity of the full input matrix X per batch, an O(N^2H) operation. The paper's complexity analysis covers only the leaf KDTree construction and the dual attention; it never mentions the padding selection cost. Since the main contribution is efficiency, this omission could change the magnitude or even the sign of the claimed speedup. I do not think this warrants rejection: the accuracy comparisons are extensive and consistently favorable, and the efficiency issue is addressable by profiling or by clarifying that padding indices are precomputed once. The reader's CONDITIONAL verdict is therefore appropriate, and my independent analysis does not move it. I agree with the reader's identification; my concrete test sharpens it with a specific profiling step and a threshold for deciding whether the concern lands.","tokens_in":18513,"tokens_out":5906,"duration_ms":72320,"concrete_test":"Clone the official PatchSTG repository and instrument the CA training loop with torch.profiler; measure the cumulative wall-clock time and memory of all operations originating from Eq. 5 (CosSim, Query, Pad) over one full epoch. If this fraction is non-trivial (e.g., >10% of the 981s/epoch reported in Table 5) or if Eq. 5 executes per batch rather than once as a precomputation, rerun the efficiency comparison with a complete accounting and report the true M and per-batch padding overhead for every dataset.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central efficiency claim (Section 5.4, up to 10x speed and 4x memory) rests on the complexity analysis of Section 4.5, which asserts M≈N and ignores the cost of Eq. 5. Under the paper's own hyperparameters, M is substantially larger than N: for CA (N=8600, C=3, R=512) the padded size is M=12288 (P=24), for GBA (N=2352, C=2, R=16) M=4096 (P=256), for SD (N=716, C=2, R=16) M=1024, and only GLA is close with M=4096 versus N=3834. Thus the asymptotic comparison in Section 4.5 overstates the benefit of patching. More importantly, Eq. 5 computes CosSim(X, X^T) to choose padding points for every unfull leaf node; if this is executed inside the training loop for each batch, it adds O(N^2H) work per batch (about 888 million multiply-adds for CA with H=12). The paper never states whether this padding is precomputed offline or performed online, and the wall-clock training times in Table 5 cannot be assessed without that information. If Eq. 5 runs per batch, the reported 981s/epoch for CA may include this cost, but then the claimed speedup over baselines still needs a full accounting of all preprocessing and padding operations; if it does not include it, the comparison is incomplete. Given that the efficiency advantage is the paper's primary novelty, this missing cost is the single most load-bearing uncertainty in the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PatchSTG, a Transformer framework for large-scale traffic forecasting that reduces the cost of dynamic spatial attention by partitioning irregularly distributed sensors into balanced, non-overlapping patches using a leaf KDTree. Depth and breadth attention are then applied within and across patches to capture local and global spatial dependencies. On four LargeST datasets (SD, GBA, GLA, CA), PatchSTG consistently outperforms ten baselines on MAE, RMSE, and MAPE, and the paper reports up to 10x training speed and 4x memory reduction over dynamic spatial modeling baselines.","tokens_in":18886,"tokens_out":7129,"duration_ms":76254,"significance":"If the efficiency claims are substantiated, the paper makes a useful contribution: it provides a practical way to apply full dynamic spatial attention at city scale (8,600 sensors) with subquadratic complexity, and the KDTree-based patching offers a spatially interpretable alternative to clustering or low-rank approximations. The empirical evaluation is thorough: four public large-scale datasets, ten baselines, standard metrics, and extensive ablations. The code is publicly available, which is a strength. The paper's primary novelty, however, is the efficiency argument, and that argument currently rests on an incomplete complexity analysis and an unaccounted preprocessing/padding cost.","major_comments":[{"comment":"The expression for the padded size, M = C×2^{⌊log(N)⌋−log(C)} ≥ N, is not valid as written. With the paper's own hyperparameters, for CA (N=8600, C=3, R=512) the required number of points per patch is P=24, giving M=12,288 ≈ 1.43N; for GBA (N=2352, C=2, R=16), P=256, giving M=4096 ≈ 1.74N; for SD (N=716, C=2, R=16), M=1024 ≈ 1.43N. Only GLA is close to the claimed M≈N. Since §4.5 bases its complexity comparison on M≈N, the efficiency analysis overstates the benefit of patching. The authors should correct the formula, report the actual M/N ratios, and revisit the asymptotic and constant-factor claims.","section":"§4.2 and §4.5"},{"comment":"The padding step in Eq. (5) computes CosSim(X, X^T) to select padding points for unfull leaf nodes. If this computation is executed inside the training loop for each batch, it adds O(N^2 H) work per batch; for CA with H=12, this is roughly 8.9×10^8 multiply-adds per batch, which is comparable to the attention cost and would substantially erode the speedups reported in Table 5. The paper does not state whether the padding indices are precomputed once (e.g., on the training set) or recomputed per batch, and §4.5 omits this cost entirely. This is a load-bearing gap: the efficiency advantage is the paper's primary claim, and the authors must specify the placement of Eq. (5) and include its cost in the complexity and runtime analyses.","section":"§4.2, Eq. (5)"},{"comment":"The headline 'up to 10× and 4× improvements in speed and memory' is drawn from total training time on GLA (41h vs 4h) and batch size on CA (32 vs 8), respectively. The per-epoch training time improvements are 5× on GLA (1483s vs 295s) and 3.7× on CA (3641s vs 981s). The paper should state explicitly which quantity is being reported in each claim, and the abstract and conclusions should avoid conflating total training time, per-epoch time, and batch size.","section":"§5.4, Table 5"}],"minor_comments":[{"comment":"There are several typos and infelicitous phrases: 'breath first searching' should be 'breadth first searching'; 'Similarity' should be 'Similarly'; 'intepretable' should be 'interpretable'; 'equaled' should be 'equal'; and 'non-overlap patches' should be 'non-overlapping patches'.","section":"Throughout"},{"comment":"The definition of the number of points per patch uses N_p, but the relationship between P, R, C, and N_p is not written explicitly in the equations; please clarify that P = C × N_p and that N_p must be a power of 2.","section":"§4.2"},{"comment":"The sentence 'which requires less time than quadratic dynamic spatial modeling methods because P≪N, R≪N, and M≈N' is imprecise: even with a correct M, the comparison of asymptotic complexity should be stated as a ratio or with explicit big-O expressions for both depth and breadth attention.","section":"§4.5"},{"comment":"The ablation variant 'w/o FGGC' is listed in the bullet points and in Table 4, but the subsequent discussion does not clearly reference it by name; consider explicitly mapping each variant to its findings.","section":"§5.3"},{"comment":"The 'Improvements' row would be clearer if it indicated the baseline used for the ratios (e.g., STWave, the only dynamic baseline that runs on all datasets) and the direction of each ratio (PatchSTG value divided by baseline value).","section":"§5.4, Table 5"},{"comment":"The paper claims the padded patches are 'non-overlapped' and 'fidelity' (no information loss), but padding duplicates points from other leaf nodes, so the same original point may appear both in its own patch and as padding in another patch. The paper should clarify how this duplication affects the fidelity claim and whether it influences the attention computation.","section":"§4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper's empirical results appear solid and the method is novel, but the efficiency story—which is the paper's main contribution—needs a careful audit. I recommend asking the authors to profile Eq. (5) and to report the actual M/N ratios for each dataset, and to revise the abstract and conclusions to match the measured per-epoch and total-training-time numbers. If the padding cost turns out to be largely amortized in preprocessing, the claims may survive; if not, the speedup figures in Table 5 need to be recomputed. The code availability is a plus and will help verify these points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper has a genuinely new idea: using a leaf KDTree to partition irregularly distributed traffic sensors into balanced patches, then running local (depth) and global (breadth) attention on the patches. Second, the accuracy results look solid: consistent state-of-the-art on four LargeST datasets. But the efficiency story has an unresolved hole.\n\nWhat it does well: the patching algorithm is well-motivated, and the ablations are thorough. The w/o LKDT, w/ METIS, and w/ KMeans comparisons show the KDTree choice matters, and the depth/breadth attention split is simple and effective. The experimental setup is standard, and the code is public.\n\nSoft spots. Section 4.5 claims M≈N, but the hyperparameters in Section 5.1.4 give M=12,288 for CA versus N=8,600 (43% more tokens) and M=4,096 for GBA versus N=2,352 (74% more). That is not fatal—the complexity is still roughly linear in N—but the paper should report actual M values instead of hand-waving. More important is Eq. 5: the padding step computes CosSim(X, X^T) to fill unfull leaf nodes. Since X is the input window, this is a per-batch O(N²H) operation unless it is precomputed offline, and the paper never says which. The theoretical analysis completely omits this cost. If it runs in the training loop, the wall-clock numbers in Table 5 may already include it, in which case the speedup is real but the analysis is still wrong; if it does not, the comparison is incomplete. The authors need to state where and when Eq. 5 is executed, and give a time breakdown.\n\nMinor issues: no error bars in the main tables, and the efficiency comparison only covers dynamic baselines, not the much faster STID. Neither changes the main conclusion.\n\nBottom line: the accuracy contribution is solid, and the patching idea is worth taking seriously. The efficiency claim needs one clear fix—full accounting of padding and actual M values—before I would trust the 10x number. This is a revise-and-resubmit, not a rejection.\n\nMy recommendation: send it to peer review. A referee should ask for the padding cost accounting, actual M values, and a statement about whether Eq. 5 is offline or online. Traffic forecasting and spatio-temporal deep learning researchers will get value from the KDTree patching idea and the thorough ablation study.","headline":"PatchSTG has a genuinely new KDTree-based patching idea and strong accuracy results on LargeST, but its efficiency analysis omits a per-batch padding cost that could eat into the claimed speedup.","tokens_in":19414,"tokens_out":3352,"would_cite":true,"duration_ms":37571,"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":"PatchSTG claims that dynamic spatial attention for traffic forecasting can be made sub-quadratic by partitioning irregularly placed sensors into balanced patches with a leaf KDTree, and reports state-of-the-art accuracy with up to 10x…","keywords":["traffic forecasting","spatio-temporal graph neural networks","Transformer","KDTree","irregular spatial patching","dynamic spatial modeling","large-scale traffic data","spatial data management"],"falsifier":"Profile the CA training run with the leaf-KDTree construction and cosine-similarity padding included in the per-epoch timer and excluded from it; if the padding step accounts for a significant share of wall-clock time, the reported 10x speedup is not the cost of the full method. A simpler check is to compute $M$ from the reported $R=512$, $C=3$, and $N_p$ for CA and compare it with $N=8{,}600$.","tokens_in":18329,"feed_emoji":"🚦","tokens_out":7037,"duration_ms":74565,"temperature":0.7,"pith_summary":"PatchSTG aims to make dynamic spatial modeling in traffic forecasting practical at city scale. The paper argues that the quadratic cost of point-to-point attention is what blocks large-scale use, and that this cost can be cut by first partitioning irregularly placed road sensors into balanced, non-overlapping patches with a leaf KDTree and then running attention only within and across patches. On four large-scale datasets (up to 8,600 sensors), the resulting Transformer is claimed to match or beat existing dynamic and static spatial models in accuracy while training up to 10 times faster and using up to 4 times less GPU memory.","feed_headline":"KDTree sensor patches cut city-scale traffic training 10x","feed_subtitle":"Grouping unevenly spaced road sensors into balanced patches keeps full dynamic attention tractable without losing information","key_machinery":"The machinery is irregular spatial patching driven by a leaf KDTree. A leaf KDTree partitions irregularly distributed sensor points into leaf nodes of capacity at most $C$, using median hyperplanes so all points live in leaves; padding and backtracking then merge these leaves into occupancy-equal, non-overlapped patches of $P$ points each. This reduces the set of points involved in dynamic attention from $N$ to $M$ (with the paper asserting $M\\approx N$), and depth/breadth attention on the patched tensor converts the quadratic point-pair calculation into two smaller attention passes, one local and one global.","core_discovery":"The central claim is that full dynamic spatial dependency modeling does not require every sensor to attend to every other sensor; it can be reorganized through spatial data management. PatchSTG builds a leaf KDTree over sensor coordinates, stores all points in leaves, re-indexes them by breadth-first search, pads unfilled leaves with the most temporally similar points from other leaves, and merges leaves of the same subtree into patches of equal size. The encoder then alternates depth attention (local, within a patch) and breadth attention (global, across same-index positions in different patches), giving $O(\\max(P,R)Md)$ complexity with $M\\approx N$ instead of $O(N^2 d)$. The paper reports state-of-the-art MAE/RMSE/MAPE on SD, GBA, GLA, and CA, with up to $10\\times$ training speed and $4\\times$ memory advantage over dynamic spatial baselines.","pith_inferences":["Editorial inference: The complexity analysis is incomplete because Equation 5 computes a cosine-similarity matrix across all input sensors, an $O(N^2 H)$ operation per batch that is absent from the efficiency comparison; including it could shrink or erase the reported speedup on the largest datasets.","Editorial inference: The same irregular-patching recipe should transfer to other irregularly placed sensor arrays, such as air quality monitors or weather stations; a natural test is whether depth attention's local bias still helps when the spatial correlation length is much longer than typical patch size.","Editorial inference: The hyperparameter search shows the best patch count grows with dataset size (16, 16, 64, 512 for SD, GBA, GLA, CA), suggesting a data-dependent scaling rule could make the method nearly parameter-free in practice.","Editorial inference: A crossover point likely exists: as $N$ grows, the $O(N^2 H)$ padding cost may overtake the savings from patched attention, so the method's advantage may be largest in a mid-scale regime."],"forward_implications":["If PatchSTG's results hold, dynamic point-to-point spatial modeling becomes usable on networks with thousands of sensors, where quadratic baselines either run out of memory or take days to train.","The same patched-attention design can produce interpretable spatial partitions and explicit per-point correlation maps, which linear and low-rank efficient methods cannot provide.","Because breadth attention is applied per index across patches rather than fusing patch representations, global correlations retain per-point heterogeneity, supporting the paper's claim of fidelity.","The efficiency gain is large enough that forecasting on the 8,600-sensor CA dataset completes in about 14 hours of total training time with a batch size of 32 on one 48 GB GPU, compared with baselines that need larger batches or fail to run."],"supporting_citations":[{"why":"Supplies the four large-scale benchmark datasets (SD, GBA, GLA, CA) used in all experiments.","marker":"[43]"},{"why":"Provides the KDTree spatial partition algorithm that the leaf KDTree modifies.","marker":"[52]"},{"why":"Supplies the $O(N \\log N)$ KDTree construction complexity used in the paper's complexity analysis.","marker":"[5]"},{"why":"Establishes the patch-based complexity reduction in vision Transformers that PatchSTG adapts to irregular spatial data.","marker":"[44]"},{"why":"Represents a dot-product attention baseline whose quadratic cost motivates the need for PatchSTG.","marker":"[39]"},{"why":"Represents a linear-complexity baseline that PatchSTG compares against on efficiency and interpretability.","marker":"[20]"},{"why":"Low-rank baseline STWave, the strongest efficient dynamic-spatial competitor in the experiments.","marker":"[11]"},{"why":"STID baseline that demonstrates the power of identity embeddings without spatial modeling, a key comparison point.","marker":"[50]"},{"why":"D2STGNN, a point-to-point dynamic baseline setting the quadratic benchmark that fails to run on the largest datasets.","marker":"[51]"}],"fun_headline_variants":["KDTree patches make traffic transformers 10x faster","Spatial patching trims transformer complexity for city-scale traffic","PatchSTG: balanced spatial patches enable 10x faster traffic forecasting","City traffic forecasting gains 10x speed via KDTree-based attention","10x faster and 4x lighter: KDTree-patched traffic transformers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The near-linear efficiency claim rests on the padded point count staying close to the real sensor count and on the similarity-based padding step costing little; on the CA dataset the reported hyperparameters force $M\\approx 12{,}288$ against $N=8{,}600$, and that padding cost is never measured in the speed comparison.","fun_headline_variants_meta":{"raw":{"variants":["KDTree patches make traffic transformers 10x faster","Spatial patching trims transformer complexity for city-scale traffic","PatchSTG: balanced spatial patches enable 10x faster traffic forecasting","City traffic forecasting gains 10x speed via KDTree-based attention","10x faster and 4x lighter: KDTree-patched traffic transformers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000297,"raw_usage":{"total_tokens":1736,"prompt_tokens":974,"completion_tokens":762,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":590,"completion_tokens_details":{"reasoning_tokens":671}},"tokens_in":590,"tokens_out":762,"duration_ms":7806,"temperature":1.0,"reasoning_tokens":671,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:29:38.213904+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Profile the CA training run with the leaf-KDTree construction and cosine-similarity padding included in the per-epoch timer and excluded from it; if the padding step accounts for a significant share of wall-clock time, the reported 10x speedup is not the cost of the full method. A simpler check is to compute $M$ from the reported $R=512$, $C=3$, and $N_p$ for CA and compare it with $N=8{,}600$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the four large-scale benchmark datasets (SD, GBA, GLA, CA) used in all experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the KDTree spatial partition algorithm that the leaf KDTree modifies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the $O(N \\log N)$ KDTree construction complexity used in the paper's complexity analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the patch-based complexity reduction in vision Transformers that PatchSTG adapts to irregular spatial data."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Represents a dot-product attention baseline whose quadratic cost motivates the need for PatchSTG."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Represents a linear-complexity baseline that PatchSTG compares against on efficiency and interpretability."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Low-rank baseline STWave, the strongest efficient dynamic-spatial competitor in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"STID baseline that demonstrates the power of identity embeddings without spatial modeling, a key comparison point."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"D2STGNN, a point-to-point dynamic baseline setting the quadratic benchmark that fails to run on the largest datasets."}],"review_version":1}