{"id":"79cb09a5-2d4c-4018-b9ce-ccd7574a56b8","arxiv_id":"2506.11997","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"pLSTM extends linear recurrent networks to general directed acyclic graphs with a parallelizable scheme and two stabilization modes for long-range propagation.","lead":"This paper introduces pLSTM, a recurrent architecture that processes images, graphs, and other multi-dimensional data in parallel instead of forcing a fixed sequential order. The authors show it handles long-range spatial reasoning, such as an arrow-pointing task, better than Transformers, and performs competitively on ImageNet and molecular graph benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"D-mode multitree reduction is asserted for arbitrary DAGs but fails even on a 4-node diamond if reachability must be preserved; the general-DAG stabilization claim is unsupported.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: D-mode stability for arbitrary DAGs is asserted but not proved. My analysis strengthens this from 'missing proof' to 'false as stated' by exhibiting a 4-node diamond whose line graph admits no reachability-preserving multitree subgraph. This matters because the paper's headline contribution is explicitly about general DAGs, and the abstract and contribution list claim formal stabilization on general DAGs via both P- and D-modes. However, the core architecture is still defensible when the claims are scoped to grids (or to loosely self-similar DAGs where a suitable reduction can be constructed), and the P-mode stabilization is valid for any DAG since it only requires an L1 column normalization without losing reachability. The empirical results, especially the arrow-pointing extrapolation and the released code, provide independent support for the 2D instantiation. The paper can be repaired by either proving a general D-mode construction under explicit assumptions or by revising the claims to the settings actually supported. Since the reader already conditioned acceptance on fixing the general-DAG issue, my concern does not move the verdict; it reinforces the conditionality. I also note the paper's own Limitations section candidly states that the synthetic task tests the long-range claim only in a restricted way, which is consistent with this assessment.","tokens_in":28579,"tokens_out":11227,"duration_ms":122598,"concrete_test":"Run an exhaustive search on the diamond DAG and on random small DAGs: enumerate all ways of setting Transition entries to zero (or restricting to a spanning subgraph of the line graph) such that at most one directed path exists between any two line-graph nodes; check whether every original node can still reach every descendant node. If for the diamond no such subset exists, the general-DAG D-mode claim fails. A second check: in the released graph code, verify whether the D-mode layers actually impose the multitree constraint or merely train unconstrained Transitions; if unconstrained, the graph experiments provide no evidence for D-mode stability.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central contribution (Section 4.2 and the bullet 'formally derive the general stabilization ... on general DAGs') requires that, for every DAG, a subset of Transition edges can be zeroed so the line graph becomes a multitree while the layer still propagates information between every ancestor/descendant pair. Section 4.3.1 only demonstrates this for 2D grids (zeroing one diagonal Transition). For general DAGs the claim is not proven and, as stated, is false. Consider the diamond DAG with nodes a,b,c,d and edges a->b, a->c, b->d, c->d. Its line graph has transitions (a->b)->(b->d) and (a->c)->(c->d). Any multitree subgraph that still lets b reach d and c reach d must keep both transitions; then a reaches d by two paths (via b and via c), violating the unique-path condition. Dropping either transition severs c->d or b->d, losing reachability. Hence no global zeroing of Transitions yields a reachability-preserving multitree on this DAG. The graph experiments (Section 5.4) do not report enforcing a multitree reduction; they use learned Transitions, so D-mode stabilization is not verified there either. The claim that pLSTM 'tackles the vanishing/exploding activation/gradient problem for long distances in DAGs via ... D-mode' therefore overreaches beyond grids, and the paper's own limitation paragraph concedes the synthetic test is 'restricted'.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces pLSTM, a linear recurrent architecture defined on the line graph of a DAG, with Source, Transition, and Mark gates replacing the usual input, forget, and output gates. The authors propose a hierarchical parallelization scheme for regular grids and, more speculatively, for general DAGs, and derive two stabilization mechanisms: a P-mode that bounds column sums of the Transition matrix and a D-mode that reduces the line graph to a multitree so that path-count explosion is avoided. Experiments cover a new synthetic arrow-pointing extrapolation task, ImageNet-1k, and TUDataset graph benchmarks.","tokens_in":28813,"tokens_out":11295,"duration_ms":141010,"significance":"If the claims are scoped correctly, pLSTM is a valuable bridge between linear RNNs and multi-dimensional RNNs. The P-mode column-sum bound in Section 4.2 and the power-law decay calculation in Appendix C.2 are concrete, checkable derivations. The arrow-pointing experiments include multiple seeds with confidence intervals, compare against several strong baselines, and show a clear extrapolation advantage for pLSTM on the tested setting. The release of code and datasets is a further strength. The main weakness is that the D-mode stabilization, which is advertised as a general result for DAGs, is only rigorously demonstrated for 2D grids, and the graph experiments do not verify the D-mode reduction. These are correctable issues, but they are load-bearing because the general-DAG stabilization claim is a headline contribution.","major_comments":[{"comment":"The D-mode stabilization claim for general DAGs is not proven and, under a natural reachability-preservation requirement, is false. Section 4.2 states that D-mode 'reduces T or G′ from a DAG to a multitree' and that this yields long-range propagation, but the only concrete case given is the 2D grid in Section 4.3.1, where zeroing one diagonal Transition produces a multitree while preserving reachability. No preservation condition is stated for arbitrary DAGs. Under the natural requirement that every ancestor-descendant reachability relation of the original DAG be preserved, consider the DAG with edges s→a, a→b, a→c, b→d, c→d, d→t. Its line graph contains two distinct paths from the source edge (s→a) to the sink edge (d→t); retaining both transitions preserves both b→d and c→d but violates the unique-path condition, while zeroing either transition severs one of those relations. Thus the general-DAG claim in the introduction ('formally derive the general stabilization ... on general DAGs') is either trivial if no preservation is required, or unsupported if preservation is required. Please state a precise invariant for D-mode and prove that a reachability-preserving multitree reduction exists for the claimed class; otherwise, restrict the general claim to grids or to DAG families for which the reduction is proven.","section":"4.2, Section 4.3.1, and contribution bullet in Section 1"},{"comment":"The graph experiments do not provide empirical support for the D-mode stabilization claim. Section 5.4 states that pLSTM alternates between P-mode and D-mode on molecular graphs, but no implementation detail is given for the multitree reduction on these DAG covers. The Transitions are computed from learned node and edge features, and no Transition is reported as being zeroed or otherwise forced into a multitree structure. Therefore the results in Table 3 cannot be read as evidence that the D-mode stabilization works on general graph-structured data. Please specify how D-mode is enforced for graph inputs, or remove the implication that the graph experiments exercise the D-mode mechanism.","section":"5.4 (Graph experiments)"},{"comment":"The hierarchical parallelization is claimed for general DAGs, but the recursion in Appendix A.2 is conditional on a decomposition into 'loosely self-similar' subgraphs, and no theorem or complexity analysis states for which DAGs such decompositions exist with bounded boundary size. The appendix itself acknowledges that arbitrary node subsets always produce a decomposition but that the edge balance may be poor. The graph experiments in Appendix D.4 explicitly use the recurrent, non-parallel form. Consequently, the parallelization claim is demonstrated only for regular grids (Appendices A.3 and A.4). Please either prove the parallelization for the stated class of general DAGs or explicitly scope the claim to the cases for which the construction is provided.","section":"4.1.2 and Appendices A.1/A.2"}],"minor_comments":[{"comment":"Table 5 is titled 'Test Results on Arrow Pointing Extrapolation' but reports numbers only for pLSTM variants and ViT, while Figure 5 shows learning curves for EfficientNet, ViL, Mamba2D, and 2DMamba. Numeric results for all baselines should be reported in the table for reproducibility and for a complete comparison.","section":"Table 5 and Figure 5"},{"comment":"The concatenation notation using ⌋i and ⌉i is nonstandard and easy to misread; a small worked example alongside Eq. (21) would make the recursive construction substantially clearer.","section":"Appendix A.3"}],"recommendation":"major_revision","confidential_remarks":"I see this as a major revision rather than a rejection because the core P-mode analysis, the 2D grid construction, and the main empirical demonstration are sound. The required changes are to narrow or repair the general-DAG claims in the D-mode stabilization and in the hierarchical parallelization, and to make the graph-experiment description precise about which stabilization mode is actually used. If the authors can provide a precise preservation condition for D-mode and prove existence for a well-defined class of DAGs, or convincingly weaken the claim to grids and tree-like structures, the paper would be much stronger."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a real contribution to multi-dimensional linear RNNs, but the headline stabilization result for general DAGs is overclaimed. The P-mode analysis is solid; the D-mode as stated doesn't survive a simple diamond DAG.\n\nWhat's genuinely new: the Source-Transition-Mark gating on line graphs, the hierarchical divide-and-conquer parallelization for DAGs, and the P/D mode distinction. The chunkwise-parallel form for grids is a useful extension of the linear-RNN toolbox, and the arrow-pointing extrapolation task is a nice diagnostic. The P-mode column-sum norm bound and the power-law decay calculation in Appendix C.2 are correct, and the synthetic experiments show a clear extrapolation advantage over ViT and the 2D Mamba variants.\n\nThe soft spots: Section 4.2 claims D-mode stabilizes general DAGs by reducing the line graph to a multitree. That reduction is only demonstrated for 2D grids (zero one diagonal transition). For an arbitrary DAG it's not proven, and as stated it's false. Take the diamond a->b, a->c, b->d, c->d. To keep b reachable to d and c reachable to d you must keep both line-graph transitions; then a reaches d by two paths, so the line graph isn't a multitree. Drop either transition and you sever a required connection. So the general-DAG claim in the contributions list and the abstract's \"tackle the vanishing/exploding problem for long distances in DAGs\" need to be scoped down to grids or to whatever graph class the reduction actually works for. The graph experiments don't help: they learn transitions without enforcing any multitree reduction, so D-mode stabilization is not verified there.\n\nAlso, the ImageNet results are below several baselines (e.g., ViL-T 78.3 vs pLSTM-Vis-T 75.2) and the numbers are single runs, so \"strong performance\" in the abstract overstates things. The arrow-pointing task is authored by the same group, so task-architecture co-design is a risk, though the confidence intervals and the failure of the 2D baselines soften that.\n\nBottom line: worth a serious referee. The core idea is novel and mostly well-executed, but the D-mode claim needs either a proof for the stated scope or a narrower scope, and the experimental claims need to be toned down. I'd accept this into the review process and ask for a major revision.","headline":"Real contribution to multi-dimensional linear RNNs, but the general-DAG D-mode stabilization claim is overclaimed and needs scoping down before acceptance.","tokens_in":29432,"tokens_out":3097,"would_cite":true,"duration_ms":74421,"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":"The paper introduces pLSTM, a linear recurrent architecture that moves cell states onto the edges of a directed acyclic graph and processes the whole graph in parallel, with Source, Transition, and Mark gates and two stability modes.","keywords":["pLSTM","linear recurrent networks","directed acyclic graphs","line graphs","parallel associative scan","long-range stability","image extrapolation","graph representation learning"],"falsifier":"Build a diamond DAG whose target receives the sum of the two branch inputs, train D-mode and unrestricted pLSTM on random instances of it, and compare accuracy. If the unrestricted network solves the task while D-mode accuracy is systematically lower, the multitree reduction has removed a route the task needs, refuting the claim that D-mode stabilizes general DAGs without sacrificing expressiveness; if D-mode preserves the contribution in every such DAG, the assumption stands.","tokens_in":28322,"feed_emoji":"🔄","tokens_out":14492,"duration_ms":168551,"temperature":0.7,"pith_summary":"This paper tries to give modern linear recurrent networks what multi-dimensional LSTMs once had: the ability to operate directly on grids, trees, and directed acyclic graphs instead of being forced into a fixed sequential order. The proposal, pLSTM, moves the recurrent cell state from nodes to edges and controls the flow with three learned gates: Source injects input into an edge, Transition moves state between consecutive edges, and Mark reads edge states out to a node. Because every update is linear, the paper shows the computation can be reorganized by divide and conquer into higher-order gates, giving a parallel associative scan over a DAG and logarithmic-time processing on regular grids. The paper also claims two modes that keep long-range activations and gradients bounded, a directed P-mode and a diffusive D-mode, and supports this with an arrow-pointing image task where pLSTM extrapolates to larger resolutions better than Transformer and recurrent baselines. A sympathetic reader would care because the result suggests linear RNNs can escape the sequence-only bottleneck without losing parallel training.","feed_headline":"Parallel linear RNNs now work on graphs and images, not just sequences","feed_subtitle":"Source, Transition, and Mark gates on line graphs keep long-range state flow stable and parallel.","key_machinery":"The load-bearing object is the line graph $G'$ of the DAG: the nodes of $G'$ are the edges of the original DAG, and a line edge connects two original edges that meet at a node. pLSTM places its cell state on these nodes, so the recurrence becomes a power iteration on the adjacency matrix $T$ of $G'$, with Source, Transition, and Mark gates replacing input, forget, and output gates. Associativity of the linear operators is what lets the paper combine them into higher-order Source/Transition/Mark tensors over a recursive decomposition of the graph, turning a node-by-node topological pass into a parallel scan. Stability is a rule on $T$: in P-mode each node's outgoing transitions satisfy the column-sum bound $\\sum_e |T^e_{e'}| \\le 1$, keeping matrix powers bounded and gradients bounded in the dual norm; in D-mode one diagonal transition family is zeroed so $G'$ becomes a multitree with exactly one path between any two states, removing the exponential path sum that otherwise accumulates on grids.","core_discovery":"The central claim is that a linear RNN can be reparametrized as a network on a DAG by placing the cell state $C_e$ on each edge $e$, injecting node input through Source gates, propagating through Transition gates along consecutive edges, and reading node outputs through Mark gates. Writing the recurrence this way keeps every operation linear, so the exact node-to-node transfer is a sum over paths of products of Transitions; instead of enumerating the exponentially many paths, the paper merges Source, Transition, and Mark objects hierarchically over a recursive graph decomposition, yielding a parallel associative scan that reduces to einsum, concatenation, and padding steps for 1D and 2D grids. For long-range stability, the paper identifies two regimes: P-mode keeps the absolute column sums of the Transition matrix per node at most one, which bounds matrix powers and limits a signal to a chosen propagation line with only power-law decay, and D-mode zeroes one family of transitions so the line graph becomes a multitree, removing the exponential path-count blowup at the price of directionality. On the arrow-pointing extrapolation task, the claimed result is that pLSTM generalizes to larger image resolutions where Transformers and scanline recurrent models do not, and on ImageNet and molecular-graph benchmarks the paper reports accuracy competitive with established baselines.","pith_inferences":["The paper does not prove that every DAG admits a D-mode transition subset whose line graph is a multitree and still preserves all source-to-target connections; it demonstrates the reduction on 2D grids. A diamond DAG with two informative routes would be the minimal test of whether the D-mode multitree reduction preserves task-relevant connectivity.","The exponential path-count argument applies to any linear recurrence on a DAG with in-degree greater than one, so the P-mode/D-mode distinction is likely a general design principle for graph state-space models, not a pLSTM-specific trick.","The paper itself notes that the arrow-pointing task tests long-range behavior in a restricted way and that extrapolation is not perfect; a natural next step would be multi-scale medical or remote-sensing benchmarks where input resolution shifts at test time.","With non-diagonal Transition matrices, pLSTM may implement counting and state-tracking on graphs; testing it on graph analogues of regular-language tasks would separate the stabilization claim from the representational claim."],"forward_implications":["Training on images, volumes, or graph-structured data no longer requires flattening them into a scanline order; one pLSTM layer can propagate information along all edges of a DAG in parallel, with a chunkwise-recurrent option that stops hierarchical merging at any chosen level.","With P- and D-modes alternated across layers, a model can both aim a signal along a chosen direction and spread it globally, making the effective receptive field a tunable design choice rather than an accident of the traversal order.","The arrow-pointing experiments imply that recurrence over the true data geometry can beat global-attention or positional-embedding shortcuts when the test resolution changes, because the model is not forced to learn distances in pixels.","On graph data, pLSTM acts as a message-passing network whose receptive field is a whole connected component per layer instead of one hop, reaching accuracy competitive with standard GNNs at matched parameter counts on the tested small-molecule and bioinformatics datasets.","The state-tracking extension with non-diagonal Transition matrices carries the same stability arguments, so a DAG pLSTM can count or track states without losing the P- and D-mode bounds."],"supporting_citations":[{"why":"introduced multi-dimensional RNNs, the framework pLSTM extends from non-linear LSTMs to parallelizable linear recurrences.","marker":"Graves et al. [2007]"},{"why":"established the forget-gate stability problem and the LSTM cell whose input/forget/output gates pLSTM reinterprets as Source/Transition/Mark.","marker":"Hochreiter and Schmidhuber [1997]"},{"why":"provides the modern linear-recurrent xLSTM formulation with state expansion that pLSTM generalizes from sequences to DAGs.","marker":"Beck et al. [2025b]"},{"why":"supplies the chunkwise-parallel associative-scan techniques for linear RNNs that pLSTM lifts to multiple dimensions.","marker":"Yang et al. [2023]"},{"why":"defines the line graph, the central object on which pLSTM cell states and transitions live.","marker":"Whitney [1932]"},{"why":"defines multitrees, the single-path structure used by the D-mode to avoid exponential path sums.","marker":"Jung [1978]"},{"why":"supplies the sub-multiplicative matrix-norm facts used to prove the P-mode stability bound.","marker":"Horn and Johnson [1985]"},{"why":"provides the Transformer baseline and the multi-head/positional-embedding machinery pLSTM adapts for directional heads.","marker":"Vaswani et al. [2017]"},{"why":"Mamba2D is the P-mode-only two-dimensional baseline pLSTM compares against.","marker":"Baty et al. [2024]"},{"why":"2DMamba is the D-mode-only baseline pLSTM compares against.","marker":"Zhang et al. [2024a]"}],"fun_headline_variants":["Linear RNNs go parallel on graphs and images","pLSTM extends linear RNNs to DAGs and grids","Source, Transition, Mark gates enable parallel DAG scans","Long-range stability in linear RNNs for graphs and images"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The D-mode stability argument assumes that for every DAG one can delete enough Transition edges so the line graph becomes a multitree, at most one path between any two state edges, without cutting information the task needs; the paper demonstrates this reduction for 2D grids by dropping one diagonal Transition, but does not prove it for arbitrary DAGs.","fun_headline_variants_meta":{"raw":{"variants":["Linear RNNs go parallel on graphs and images","pLSTM extends linear RNNs to DAGs and grids","Source, Transition, Mark gates enable parallel DAG scans","Long-range stability in linear RNNs for graphs and images"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000679,"raw_usage":{"total_tokens":3182,"prompt_tokens":1138,"completion_tokens":2044,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":754,"completion_tokens_details":{"reasoning_tokens":1983}},"tokens_in":754,"tokens_out":2044,"duration_ms":16419,"temperature":1.0,"reasoning_tokens":1983,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:59:29.751850+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a diamond DAG whose target receives the sum of the two branch inputs, train D-mode and unrestricted pLSTM on random instances of it, and compare accuracy. If the unrestricted network solves the task while D-mode accuracy is systematically lower, the multitree reduction has removed a route the task needs, refuting the claim that D-mode stabilizes general DAGs without sacrificing expressiveness; if D-mode preserves the contribution in every such DAG, the assumption stands.","supporting_citations":[],"review_version":1}