{"id":"5b659a08-9926-4176-b6b0-92905295b43b","arxiv_id":"2412.12423","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"GG-SSMs dynamically build a minimum spanning tree over feature embeddings and propagate SSM state along it, claiming state-of-the-art results on vision and time-series benchmarks.","lead":"GG-SSMs replace fixed scanning paths in State Space Models with a minimum spanning tree built on the input features, then run the state propagation along that tree. The paper reports state-of-the-art results on eleven benchmarks, but its own tables and complexity analysis contain inconsistencies that undercut the headline claims.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The described leaf-to-root forward pass (§3.3) does not compute the all-pairs path-product hidden state of Eq. (4); without an explicit derivation or an additional state-propagation pass, the model's definition and implementation diverge.","rationale":"The most load-bearing condition for the central claim is that the model described in Section 3.3 actually computes the hidden states defined in Eq. (4). This is an internal-consistency check, not a disagreement with community consensus. Eq. (4) defines h_i as a sum over all nodes of path products of node-specific matrices, while the leaf-to-root pass as described gives each node only its subtree aggregate. A correct implementation could conceivably use a second downward pass to distribute root-level information, but the paper does not state, derive, or cost such a pass, and no code is available. Because y_i is computed from h_i via Eq. (5), the reported benchmark numbers are not tied to a mathematically specified model. The MST complexity objection (the dense graph has E = O(L^2), so Chazelle's algorithm is O(L^2 alpha), not O(L)) and the Table 4 bolding inconsistencies are real but secondary; even if the complexity were fixed, the Eq. (4)/forward-pass mismatch would remain. The architectural idea is plausible, and a two-pass message-passing variant might compute Eq. (4) in linear time, but that variant is not in the paper. Therefore I agree with the reader's weakest-assumption analysis and leave the verdict unchanged at REJECT.","tokens_in":17840,"tokens_out":10124,"duration_ms":97104,"concrete_test":"On a 4-node path tree (1-2-3-4), assign distinct random transition matrices A_1,...,A_4 and arbitrary inputs x_1,...,x_4. Enumerate h_1 and h_2 directly from Eq. (4) by summing all path products S_ji. Then implement the Section 3.3 traversal exactly as described: initialize states at leaves, aggregate upward to the root, and do not recompute hidden states during the root-to-leaves gradient pass. If the traversal outputs differ from the Eq. (4) values, the forward pass is not the model defined by Eq. (4). If the authors intend a second downward state pass, supply that pseudocode and re-run the comparison, confirming both equality and a total O(L) cost.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2.2 defines the hidden state at node i by Eq. (4): h_i = sum_j S_ji \\bar B_j x_j, where S_ji is the ordered product of node-specific transition matrices along the unique tree path from j to i. Section 3.3 then specifies the forward pass as propagating state information from the leaves to the root, with each node aggregating states from its children. In a rooted tree, such a pass gives node i only the aggregate of its own subtree; contributions from nodes outside that subtree never reach i. The subsequent root-to-leaves pass is described only for gradients, not for recomputing hidden states. Thus the described algorithm does not implement Eq. (4) for non-root nodes unless an additional downward state-propagation pass is included, and that pass is neither derived nor counted in the O(L) complexity budget. No pseudocode or code is provided to resolve this ambiguity, and no experiment compares the leaf-to-root states against the Eq. (4) states. If Eq. (4) is the intended model, the forward pass is wrong; if the leaf-to-root pass is the intended model, Eq. (4) is false. Either way, the reported SOTA numbers are not tied to a well-defined model as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes GG-SSM, a state space model that replaces fixed 1D scanning with a dynamically generated minimum spanning tree (MST) computed over token/pixel feature embeddings. The hidden state at a node is defined via path products of transition matrices over the tree, and the authors claim an O(L) forward/backward pass using Chazelle's MST algorithm. Experiments cover event-based eye tracking, ImageNet classification, optical flow, and six time-series datasets, reporting state-of-the-art numbers (84.9% ImageNet top-1, 2.77% KITTI-15 Fl-all, and superior forecasting results). The paper also includes an ablation of MST construction algorithms.","tokens_in":18093,"tokens_out":7454,"duration_ms":67603,"significance":"If the method and complexity analysis were correct, the work would offer a novel way to inject adaptive, data-dependent scanning into SSMs, backed by a broad benchmark evaluation. The main strengths are the wide experimental coverage and the MST-algorithm ablation. However, the manuscript currently lacks a precise algorithm for the state propagation, contradicts its own complexity model by starting from a fully connected graph, and contains internally inconsistent table formatting that overstates the forecasting results. These issues must be resolved before the SOTA claims can be assessed.","major_comments":[{"comment":"Equation (4) defines h_i as a sum over all nodes v_j of path products S_ji Bbar_j x_j. The forward pass described in Section 3.3 is only a leaf-to-root aggregation, in which each node aggregates states from child nodes and updates its hidden state. In a rooted tree, such a pass provides node i with contributions only from its own subtree; contributions from ancestors and from sibling subtrees are not included unless a subsequent root-to-leaf state pass is performed. The paper mentions a root-to-leaf traversal only for the backward pass ('gradients are propagated from the root back down to the leaves'), not for hidden states. No derivation, pseudocode, or experiment shows that the described leaf-to-root pass computes Eq. (4) for all L nodes in O(L) time. Consequently, the relation between the model definition and the implemented forward pass is unresolved, and the reported SOTA numbers cannot be tied to the stated model.","section":"Sec. 3.2.2 (Eq. (4)) and Sec. 3.3"},{"comment":"The paper defines a fully connected undirected graph G=(V,E) with edge weights computed for every pair (Eq. (2)), so E = O(L^2). It then invokes Chazelle's MST algorithm, whose complexity is O(E alpha(E,V)), to obtain the MST. The claim in Section 3.3 that 'MST construction itself runs in O(L) for sparse graphs where E = O(L)' does not apply to the described construction, because the input graph is dense, not sparse. No approximate-MST or sparsification procedure is described, and no runtime scaling experiment is given to support the overall O(L) claim. Since the advertised efficiency advantage over transformers depends on the O(L) claim, this is a load-bearing inconsistency.","section":"Sec. 3.2.1 and Sec. 3.3"},{"comment":"Several cells are bolded as 'best' even though a competitor has a strictly lower error. For instance, on Exchange horizon 96, GG-SSM's MSE 0.0878 and MAE 0.2073 are bolded while S-Mamba and iTransformer report 0.0860 and 0.2070; on horizon 192, GG-SSM's MSE 0.1813 is bolded while S-Mamba (0.1770) and PatchTST (0.1760) are better. This contradicts the caption and the text's assertion that GG-SSM 'consistently achieves the best accuracy.' The table and any claim based on it must be corrected before the forecasting results can be interpreted.","section":"Table 4"}],"minor_comments":[{"comment":"The row for GG-SSM reads '89.3389.8999.50' without separators; it should read '89.33, 98.89, 99.50.'","section":"Table 1"},{"comment":"Both tables state that the best results are bold and the second-best are underlined, but no underlined entries appear; either add the underlining or revise the captions.","section":"Tables 5 and 7"},{"comment":"The description of Chazelle's algorithm says 'with high probability, only a small fraction of edges require re-checking'; Chazelle's MST algorithm is deterministic, so this probabilistic language should be corrected.","section":"Supplementary Section 8.1"},{"comment":"The optical-flow metrics are written inconsistently as 'Fl-epe' and 'Fl-all'; please standardize the notation (e.g., 'F1-epe' and 'F1-all').","section":"Section 4.4"},{"comment":"The dataset name appears as both 'INI-30' and 'Ini-30' in the text and tables; please use one consistent spelling.","section":"Section 4.1"},{"comment":"Equation (2) defines edge weights as exp(-cosine similarity), which is not 'cosine dissimilarity' in the usual sense; please state the intended dissimilarity measure explicitly.","section":"Section 3.2.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has already been accepted at CVPR, but my assessment is independent of that. The main risk is that the authors cannot supply a correct O(L) derivation or a released implementation for the described algorithm; if so, I would escalate to rejection. The table-formatting issue should be easy to fix, but the state-propagation and complexity gaps are substantive."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, short version: the dynamic MST scan is a genuinely new twist on fixed-path SSMs, and the paper's empirical sweep across eye-tracking, ImageNet, optical flow, and forecasting is broad. The ablation over MST algorithms is a nice touch. But the central claims don't survive close reading.\n\nThe load-bearing problem is Section 3.3. The forward pass is described as propagating state information from leaves to root, with each node aggregating states from its children. Eq. (4), however, defines h_i as a sum over all nodes j of the ordered path product S_ji times \\bar B_j x_j. In a rooted tree, a leaf-to-root pass gives each node only the aggregate of its own subtree; contributions from outside that subtree never reach it. The root-to-leaf pass is described only for gradients, not for recomputing hidden states. So either Eq. (4) is not the model being implemented, or the implementation is wrong. The paper offers no derivation, pseudocode, or code to resolve this. Without a well-defined forward pass, the reported numbers are uninterpretable.\n\nThe O(L) complexity claim is also unsupported. The method starts with a fully connected dense graph on L features; Chazelle's MST on that graph costs O(L^2 α(L)), not O(L). The paper's appeal to sparse graphs conflates the MST output with the construction input. To get near-linear time you'd need a sparse neighbor graph first, and that's neither described nor analyzed.\n\nTable 4 is a separate real problem: several GG-SSM entries are bolded as best where the table shows lower MSE or MAE for S-Mamba or PatchTST (e.g., Exchange at horizons 96 and 192, and ETTm2 MAE at horizon 96). That's not a typo in one cell; it's a pattern that contradicts the text's claim of consistent state-of-the-art results.\n\nWhat the paper does well: the idea of generating the scan graph from feature relationships via MST is worth exploring; the range of tasks is impressive; the MST ablation is informative; and the prose is mostly clear. These strengths are real, but they don't offset flaws in the definition, complexity, and result reporting.\n\nMy take: this needs a major revision with code or a precise algorithm for the all-pairs path-product computation, a corrected complexity analysis, and a corrected table. As written, it is not a reliable citable result. If I were an editor, I would send it to reviewers with a request for major revision, not desk reject — the idea is important enough to demand careful scrutiny. But I would not accept it in its current form.","headline":"A novel MST-based scan idea undermined by a forward pass that doesn't match its own equation, a bogus O(L) claim, and misleading bolded results — needs major revision, not a desk reject.","tokens_in":18590,"tokens_out":2945,"would_cite":false,"duration_ms":28063,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"GG-SSMs replace fixed scanning paths with a dynamically built minimum spanning tree and claim state-of-the-art results across vision and time-series tasks in linear time.","keywords":["state space models","minimum spanning tree","Chazelle's algorithm","dynamic graph construction","visual state space models","time series forecasting","optical flow","event-based eye tracking"],"falsifier":"Take a small tree (for example, $L=4$ nodes) with fixed transition matrices, implement both the explicit sum in Eq. (4) and the described leaf-to-root/root-to-leaf traversal, and compare the hidden states; if they differ at any node, the implementation does not match the definition, and the reported results cannot be attributed to the stated model. A controlled reimplementation of the ImageNet experiment with the same hyperparameters would check whether the 84.9% top-1 accuracy reproduces.","tokens_in":17632,"feed_emoji":"🌳","tokens_out":6071,"duration_ms":47297,"temperature":0.7,"pith_summary":"The paper introduces Graph-Generating State Space Models (GG-SSMs), which replace the fixed one-dimensional scanning paths used by models like Mamba and VMamba with a graph whose edges are chosen dynamically from the input features. For each layer, the model builds a minimum spanning tree over the feature embeddings using Chazelle's near-linear-time MST algorithm, then propagates state updates along the edges of that tree. This lets the model adapt its information flow to the data's intrinsic structure instead of forcing a handcrafted raster order. The authors report state-of-the-art results on all 11 datasets tested: 84.9% top-1 ImageNet accuracy, 2.77% Fl-all error on KITTI-15 optical flow after finetuning, improved pupil-detection rates on event-based eye tracking, and better forecasting error on six time-series benchmarks, all in linear O(L) time.","feed_headline":"SSM builds its own scanning graph, hits 84.9% on ImageNet","feed_subtitle":"Paper claims top vision and time-series results by replacing fixed scan paths with data-driven tree propagation.","key_machinery":"The central object is the minimum spanning tree (MST) built over feature embeddings, with edge weights defined by cosine dissimilarity. Because an MST has exactly one path between any two nodes, it fixes a unique propagation route for each pair; the hidden state at node $i$ is the sum over all $j$ of the ordered product of transition matrices along that path, applied to the projected input. The paper uses Chazelle's MST algorithm to obtain the tree in near-linear time (with an inverse-Ackermann factor), and claims that leaf-to-root forward and root-to-leaf backward traversals implement this aggregation in $O(L)$.","core_discovery":"The central claim is that dynamic, data-dependent graph generation is a better scanning strategy than any fixed path. Given a set of L feature embeddings (pixels, tokens, or variates), GG-SSM treats them as vertices of a complete graph with edge weights given by cosine dissimilarity, computes the minimum spanning tree, and defines the hidden state at each node as a sum over all nodes of the product of state-transition matrices along the unique tree path, times the projected input. The tree's L−1 edges and unique paths make the propagation sparse and, the paper argues, computable in linear time; each layer builds a fresh tree, so the structure adapts per layer and per input. On the strength of this design, the paper reports state-of-the-art numbers across eleven datasets spanning image classification, optical flow, event-based eye tracking, and multivariate time-series forecasting.","pith_inferences":["The tree propagates information along a single path per pair, so the effective receptive field is the tree diameter; one could test whether shallower trees (e.g., low-diameter spanning trees or adding a few short-cut edges) change the accuracy-efficiency trade-off.","If the leaf-to-root/root-to-leaf traversal does not exactly compute Eq. (4), the reported results may reflect a different, weaker aggregation; a direct check would be to compare the forward pass against the explicit all-pairs sum on small L.","The same graph-generation idea could be applied to other architectures that rely on a fixed ordering, such as recurrent networks or linear-attention variants, suggesting the principle is not specific to SSMs."],"forward_implications":["If the reported numbers hold, GG-SSM would be the first single architecture to beat both transformer-based and prior SSM baselines across image classification, optical flow, and time-series forecasting.","The dynamic MST construction means the model's receptive field is decided by feature similarity rather than grid geometry, so it should transfer to irregular data such as event streams without task-specific scanning heuristics.","The claimed O(L) complexity with exactly L−1 edges makes the approach scalable to high-resolution inputs, with the ablation showing Chazelle's MST gives near-identical accuracy to Kruskal's or Prim's but lower runtime.","On optical flow, the reported 2.77% KITTI-15 Fl-all after finetuning would be a substantial improvement over the previous best multi-frame method (3.65%)."],"supporting_citations":[{"why":"Supplies the near-linear-time MST algorithm that the method's efficiency claim rests on.","marker":"[6]"},{"why":"The selective SSM baseline that GG-SSM extends and compares against.","marker":"[19]"},{"why":"The visual SSM baseline whose training protocol is adopted for ImageNet and whose performance is surpassed.","marker":"[30]"},{"why":"The earlier multidimensional SSM that motivates moving beyond 1D scanning.","marker":"[36]"},{"why":"The ImageNet-1K benchmark where the 84.9% top-1 accuracy is reported.","marker":"[10]"},{"why":"The KITTI-15 benchmark where the 2.77% Fl-all optical flow error is reported.","marker":"[18]"},{"why":"The previous best SSM-based time-series model that GG-SSM compares against on forecasting.","marker":"[52]"},{"why":"The previous best multi-frame optical flow method on KITTI-15 whose 3.65 Fl-all GG-SSM claims to beat.","marker":"[42]"}],"fun_headline_variants":["GG-SSMs build a tree per layer, hit 84.9% on ImageNet","Dynamic MST scanning nets SOTA on 11 vision and time-series sets","MST growth makes SSMs adaptive, beating fixed paths by 1% on ImageNet","Graph-generating SSMs outdo Mamba and VMamba, 84.9% top-1","Self-built feature graphs push SSMs to SOTA across 11 datasets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claimed linear-time results depend on the assumption that a single leaf-to-root forward pass and root-to-leaf backward pass computes the all-pairs path-product aggregation defined in Eq. (4); the paper provides no explicit algorithm or experiment showing that these two computations coincide.","fun_headline_variants_meta":{"raw":{"variants":["GG-SSMs build a tree per layer, hit 84.9% on ImageNet","Dynamic MST scanning nets SOTA on 11 vision and time-series sets","MST growth makes SSMs adaptive, beating fixed paths by 1% on ImageNet","Graph-generating SSMs outdo Mamba and VMamba, 84.9% top-1","Self-built feature graphs push SSMs to SOTA across 11 datasets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000161,"raw_usage":{"total_tokens":1260,"prompt_tokens":991,"completion_tokens":269,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":157}},"tokens_in":607,"tokens_out":269,"duration_ms":3323,"temperature":1.0,"reasoning_tokens":157,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:06:14.979069+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small tree (for example, $L=4$ nodes) with fixed transition matrices, implement both the explicit sum in Eq. (4) and the described leaf-to-root/root-to-leaf traversal, and compare the hidden states; if they differ at any node, the implementation does not match the definition, and the reported results cannot be attributed to the stated model. A controlled reimplementation of the ImageNet experiment with the same hyperparameters would check whether the 84.9% top-1 accuracy reproduces.","supporting_citations":[{"cited_title":"A minimum spanning tree algorithm with inverse-ackermann type complexity","cited_arxiv_id":null,"evidence_quote":"Supplies the near-linear-time MST algorithm that the method's efficiency claim rests on."},{"cited_title":"Mamba: Linear-time sequence mod- eling with selective state spaces","cited_arxiv_id":null,"evidence_quote":"The selective SSM baseline that GG-SSM extends and compares against."},{"cited_title":"Vmamba: Visual state space model","cited_arxiv_id":null,"evidence_quote":"The visual SSM baseline whose training protocol is adopted for ImageNet and whose performance is surpassed."},{"cited_title":"Downs, Preey Shah, Tri Dao, Stephen A","cited_arxiv_id":null,"evidence_quote":"The earlier multidimensional SSM that motivates moving beyond 1D scanning."},{"cited_title":"Li, and Li Fei-Fei","cited_arxiv_id":null,"evidence_quote":"The ImageNet-1K benchmark where the 84.9% top-1 accuracy is reported."},{"cited_title":"Are we ready for autonomous driving? the kitti vision benchmark suite","cited_arxiv_id":null,"evidence_quote":"The KITTI-15 benchmark where the 2.77% Fl-all optical flow error is reported."},{"cited_title":"See, Hongwei Qin, Jifeng Dai, and Hongsheng Li","cited_arxiv_id":null,"evidence_quote":"The previous best multi-frame optical flow method on KITTI-15 whose 3.65 Fl-all GG-SSM claims to beat."}],"review_version":1}