{"id":"9f6c41de-3dc1-4849-bf25-0efec6f27fdc","arxiv_id":"2412.19350","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"SD-SSM, a single-layer selective SSM with softmax-weighted dense transition matrices, achieves near-perfect length generalization on seven finite-state automaton tasks, while diagonal selective SSMs are shown to be limited to commutative automata under a stated mapping assumption.","lead":"This paper introduces SD-SSM, a selective state-space model that chooses among dense transition matrices at each step and achieves near-perfect accuracy on sequences much longer than trained, across seven automaton tasks. It also proves a limitation: single-layer diagonal selective SSMs, under a stated mapping, can only emulate commutative automata.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1 assumes B=0, but the diagonal models that actually learn D30 use B>0, so the theory does not explain the diagonal length-generalization results it is invoked for.","rationale":"The reader's verdict is CONDITIONAL, and my read agrees with the reader's weakest assumption. The empirical SD-SSM result is supported by Table 1 and the code release, and I do not see a fatal flaw there; the best-of-three reporting is a caveat but not a load-bearing error. The theoretical contribution, however, is explicitly advertised as explaining the diagonal-SSM experiments, and Proposition 1 only covers a mapping that the successful D30 models provably do not implement. The paper is transparent about the assumption, and that transparency is credit-worthy, but transparency does not close the gap: the proposition's antecedent is false for the very configurations in Table 4 that learn D30. A direct numerical probe of the learned b-terms, or an order-sensitivity test on permuted long sequences, would settle whether the B≠0 models are outside the theorem's scope, and would clarify whether the 61.0% length-generalization ceiling has an alternative explanation. The verdict should remain CONDITIONAL: the central empirical claim stands, while the theoretical explanation of the diagonal results is incomplete.","tokens_in":17757,"tokens_out":11839,"duration_ms":118968,"concrete_test":"Take the trained B≠0 nonlinear-readout C-diagonal checkpoint from Table 4 on D30 and measure the contribution of the b(ut) term relative to A(ut)x_{t-1} over a random batch of length-90 sequences, e.g., compute mean ||b(ut)|| / mean ||A(ut)x_{t-1}|| over time and samples. If the b-terms are numerically non-negligible, the model is outside Proposition 1's scope by construction, confirming that the theorem does not explain its length-generalization ceiling. To sharpen the point, also evaluate the same checkpoint on pairs of long length-600 sequences that are permutations of one another and lead to different D30 states: if the model is order-sensitive on these pairs, it cannot be implementing the commutative B=0 solution, so a different mechanism must be responsible for the 61.0% ceiling.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is the mismatch between Proposition 1's assumptions and the experiments it is used to explain. Proposition 1 (Sec. 4) shows that, under the Sec. 2 FSA-to-SSM mapping with x0 = enc(qinit), b(ut) = 0, and simultaneously diagonalizable A(ut), a single-layer diagonal selective SSM is order-invariant and hence can only emulate commutative automata. The theorem is sound, but the diagonal models in Table 4 that actually learn the non-commutative D30 automaton are the B≠0 variants: the B=0 rows never exceed 8.35% maximum accuracy on D30, whereas the B≠0 nonlinear-readout model reaches 61.0% and the B≠0 linear-readout model reaches 11.3%. The paper's own unrolled recurrence (x2 = A2 A1 x0 + A2 b(u1) + b(u2), ...) shows that the b(ut) terms are exactly what break commutativity, so a B≠0 trained model cannot be implementing the Sec. 2 B=0 mapping. Consequently, Proposition 1 does not constrain the models whose behavior it is meant to explain. The conclusion acknowledges this with 'assuming ... they indeed cannot model non-commutative automata,' but this assumption is not satisfied by the only diagonal variants that succeed on D30. The empirical observation that B≠0 diagonal models learn D30 in-domain yet generalize poorly remains without a theoretical account, which weakens the paper's advertised explanation of diagonal-SSM limitations.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies whether selective state-space models can emulate finite-state automata and generalize to longer sequences. It introduces SD-SSM, a single-layer selective SSM whose transition matrix at each step is a softmax-weighted convex combination of a dictionary of dense matrices, followed by operator normalization and a LayerNorm-plus-linear readout. On seven FSA tasks, the best of three seeds reaches at least 99.9% length generalization on all tasks, with lower average accuracy on some tasks such as C2×C4 (93.3%). The paper also studies diagonal selective SSMs and proves Proposition 1: under a specific B=0 mapping with simultaneously diagonalizable transition matrices, a single-layer diagonal selective SSM is order-invariant and can only emulate commutative automata. Experiments on C2×C30 and D30 show that diagonal SSMs learn the commutative automaton in-domain and generalize better than on the non-commutative one, although the B≠0 variants are the ones that learn D30. The paper attributes the diagonal limitations to the proposition.","tokens_in":18049,"tokens_out":7993,"duration_ms":69835,"significance":"The empirical contribution is potentially useful: SD-SSM is a simple architecture with strong length generalization on FSA emulation, and the paper provides code and detailed hyperparameter tables, which supports reproducibility. The comparison against RNN/LSTM on very short training lengths and the parallel-scan timing are informative. Proposition 1 is correct as a linear-algebra statement under its stated assumptions, but its connection to the experiments is incomplete because the diagonal models that learn the non-commutative automaton use B≠0, which is outside the proposition's scope. The paper would be significantly strengthened by either extending the theory to input-dependent bias terms or explicitly limiting the explanatory claim.","major_comments":[{"comment":"Proposition 1 assumes the Sec. 2 FSA-to-SSM mapping with b(u_t)=0 (Eq. 13), but the diagonal variants in Table 4 that actually learn the non-commutative D30 automaton are precisely the B≠0 ones: the B=0 rows never exceed 8.35% accuracy on D30, while the B≠0 nonlinear-readout variant reaches 61.0%. The unrolled equations in Sec. 4 show that the b(u_t) terms are exactly what break commutativity, so a B≠0 trained model cannot be implementing the B=0 mapping. Consequently, Proposition 1 does not constrain the models whose behavior it is invoked to explain, and the paper's stated explanation of the poor length generalization of diagonal SSMs on non-commutative automata is not supported. The Conclusion's caveat 'assuming ... they indeed cannot model non-commutative automata' does not resolve this, because the B≠0 variants already provide a non-commutative update and are outside the assumption.","section":"Section 4, Proposition 1 and Table 4"},{"comment":"The central claim that SD-SSM achieves 'perfect (≥99.9%)' length generalization is presented without qualification, but Table 1 and Table B.8 show this is the maximum over three seeds with per-task hyperparameter search (dictionary size k, lp-normalization exponent p, and learning rate all differ by task). The average C2×C4 accuracy is 93.3%, below the 99.9% threshold. A similar pattern appears in the length-efficiency analysis: Table 2 reports best-seed results, while Table C.14 shows the average SD-SSM accuracy at training length 5 is 41.3%, below the LSTM's 45.7%. The empirical evidence is valuable, but the 'perfect' and 'exhibits better length generalization' claims should be explicitly tied to best-of-three-seed selection; otherwise the abstract overstates robustness.","section":"Abstract, Section 3, Table 1, Appendix B"},{"comment":"The experimental narrative states that diagonal selective SSMs generalize significantly better on the commutative automaton than on the non-commutative one, but Table 4 shows this is not uniform across variants: with B≠0 and a nonlinear readout, C2×C30 reaches 65.8% and D30 reaches 61.0%, a much smaller gap than the B=0 rows. More importantly, the B≠0 nonlinear-readout model learns D30 in-domain, so the Conclusion's sentence that, under the paper's assumption, diagonal SSMs 'indeed cannot model non-commutative automata' is false for the models actually trained. The paper should either analyze the B≠0 case or explicitly limit the theoretical claim to B=0 models and remove the general conclusion.","section":"Section 4, 'Variants of C Diagonal SD-SSM' and Conclusion"}],"minor_comments":[{"comment":"The caption contains the typo 'Leraning rates'; it should read 'Learning rates'.","section":"Table B.10"},{"comment":"The sentence 'it does exhibit higher variability across seeds compared to the the other models' contains a duplicated definite article.","section":"Appendix C, paragraph after Table C.14"},{"comment":"The abstract's phrase 'the first selective SSM' is stronger than the qualified claim in Section 5 ('the first to demonstrate that all ... can be emulated with single layer selective SSM utilizing a linear readout'); please align the wording.","section":"Abstract and Section 5"},{"comment":"The caption refers to 'The complex ( C) diagonal model' but the symbol C is not defined before the table; consider defining it in the caption or in Section 4.","section":"Table 1 caption"},{"comment":"Table 3 reports a single timing run without variance or repetition details; since the parallel-versus-sequential comparison is a secondary claim, please state how many runs were averaged, if any.","section":"Section 3, Table 3"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look if you care about state-tracking in sequence models. The paper's main claim holds up: SD-SSM, a single-layer selective SSM with a softmax-weighted dictionary of dense transition matrices, operator normalization, and a LayerNorm-plus-linear readout, achieves near-perfect length generalization on seven FSA emulation tasks, including the non-solvable group A5. That is a concrete architectural template and, as far as I know, the first time a selective SSM has done this in a single layer. The parallel-scan speedup and the ablation showing that a nonlinear readout hurts are both useful additions.\n\nThe theory is more modest than the prose suggests. Proposition 1 is sound but assumes the FSA-to-SSM mapping with b(u_t)=0. The diagonal models that actually learn the non-commutative D30 automaton use B≠0, and the paper's own unrolled equations show that the b-terms break commutativity. So the proposition does not explain why B≠0 diagonal models fail to generalize; it only covers the B=0 case, which never learns D30 anyway. To the authors' credit, the conclusion is transparent about this assumption, but it means the advertised \"explanation\" of diagonal SSM limitations does not apply to the models that matter empirically. That is a real gap, not a fatal one.\n\nTwo empirical caveats. \"Perfect\" is best-of-three-seeds; average accuracy on C2×C4 is 93.3%. Hyperparameters (dictionary size k, lp-norm exponent p, learning rate) are tuned per task, which is typical in this literature but worth remembering when comparing to baselines. The appendix gives full hyperparameters, and the code is public, so this is reproducible work.\n\nWho is this for? Anyone working on state-tracking, length generalization, or architectural choices in recurrent/SSM models. The main empirical result deserves to be in the literature. I'd send it to peer review, and I'd bring it to the reading group.","headline":"SD-SSM is a genuinely new architecture with strong empirical length-generalization results on FSA tasks; the theory is narrower than it looks, but the main contribution stands.","tokens_in":18605,"tokens_out":2150,"would_cite":true,"duration_ms":20073,"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":"A single-layer selective SSM with dense, input-selected transition matrices reaches at least 99.9% length-generalization accuracy on seven finite-state automata, the first selective SSM to do so.","keywords":["selective state-space models","length generalization","regular languages","finite-state automata emulation","diagonal state-space models","commutativity","state tracking","linear recurrences"],"falsifier":"Run SD-SSM on the seven Table 1 tasks with the reported hyperparameters and fresh random seeds: the headline claim fails if any task's best-seed accuracy stays below 99.9% on lengths up to 500. Separately, train a single-layer diagonal selective SSM with $b(u_t)=0$ on $D_{30}$; any run that reaches perfect length generalization would contradict Proposition 1, while a failure would leave the paper's mapping assumption as the only explanation.","tokens_in":17543,"feed_emoji":"🔁","tokens_out":10778,"duration_ms":91900,"temperature":0.7,"pith_summary":"This paper asks whether selective state-space models can emulate finite-state automata and keep working on sequences far longer than the ones seen in training. It introduces SD-SSM, a single-layer selective SSM that forms each transition matrix as a softmax-weighted convex combination of dense trainable matrices, then reads out the state through layer normalization and a linear map. On the seven automata in Table 1, SD-SSM is the first selective SSM in the paper's comparison to reach at least 99.9% length-generalization accuracy, including on the non-commutative D4 and the 60-state A5. The paper also proves that a single-layer diagonal selective SSM, under its explicit FSA-to-SSM mapping with $b(u_t)=0$, can only emulate commutative automata because simultaneously diagonalizable transitions are order-invariant. This gives a theoretical handle on why diagonal variants generalize on commutative groups but not on non-commutative ones, and it isolates dense input-selected transitions and a simple readout as the design choices that restore state tracking.","feed_headline":"Single-layer selective SSM hits 99.9% on seven automata","feed_subtitle":"Dense transitions and a linear readout let it track order-sensitive automata far past training length.","key_machinery":"The central object is the SD-SSM transition-selection mechanism. For each input $u_t$, a linear map followed by softmax produces weights over $k$ trainable dense matrices $A_1,\\dots,A_k$; the weighted sum is column-normalized, and the recurrence $x_{t+1}=A(u_t)x_t+Bu_t$ propagates the state. Because the selected matrices are dense and unconstrained, successive transition matrices need not commute, so the product $A(u_T)\\cdots A(u_1)$ can implement any permutation of automaton states, including non-commutative ones. On the theory side, the load-bearing identity is simultaneous diagonalizability: if all $A(u_t)$ share one eigenbasis, so $A(u_t)=W\\Lambda(u_t)W^{-1}$, then with $b=0$ the dynamics become $\\tilde{x}_{t+1}=\\Lambda(u_t)\\tilde{x}_t$ in the transformed basis, and products of diagonal matrices commute, making the final state order-invariant.","core_discovery":"On its own terms, the paper establishes an empirical result and a conditional theoretical result. The empirical result is that SD-SSM, with a dictionary of $k$ dense transition matrices combined by softmax and column-wise operator normalization, followed by the recurrence $x_{t+1}=A(u_t)x_t+Bu_t$ and a LayerNorm-plus-linear readout, achieves at least 99.9% best-seed accuracy on all seven FSA tasks after training only on sequences of length up to 40 (or 90 for the larger groups), and its average accuracy stays near-perfect on most of them. The theoretical result is Proposition 1: if a single-layer selective SSM implements the paper's Section 2 mapping with $b(u_t)=0$ and its transition matrices are simultaneously diagonalizable, then the final state is independent of input order, so the model can only emulate commutative automata. The paper uses Table 4's contrast between the commutative $C_2\\times C_{30}$ and the non-commutative $D_{30}$ to show that this restriction matches the empirical difficulty, while acknowledging that the $b(u_t)$ terms in the unrolled recurrence are exactly what can break commutativity when $B\\ne 0$.","pith_inferences":["The commutativity argument suggests a general design rule for sequence models: an input-dependent transition family that is simultaneously diagonalizable cannot implement order-sensitive computation; any architecture that wants state tracking must let successive transitions fail to commute.","A direct test of the paper's theory would be to train a diagonal selective SSM with $b=0$ on a non-commutative solvable group and observe whether it can even reach in-domain accuracy; if it cannot, the mapping assumption is doing the explanatory work.","The softmax-dictionary mechanism could be tried on natural-language state tracking tasks where order matters; if it helps, the benefit would come from the same non-commuting transition structure, not from a larger state size.","Because Proposition 1 only covers $B=0$, the paper leaves open whether a diagonal selective SSM with learned $b(u_t)$ can be regularized to generalize in length; an annealed or sparsified $b$ term might recover non-commutative dynamics without dense matrices."],"forward_implications":["Length generalization on regular languages does not require multi-layer stacks: a single SD-SSM layer emulates commutative and non-commutative automata up to 500 steps after training on 40.","Dense, input-selected transition matrices appear to be the architectural ingredient that diagonal selective SSMs lack for non-commutative state tracking; the paper's theory locates the reason in simultaneous diagonalizability.","The parallel-scan implementation of SD-SSM keeps training parallelizable despite dense matrices, so the expressiveness gain does not force sequential training.","Using a linear readout over LayerNorm instead of a nonlinear MLP is decisive on Arithmetic: replacing it drops accuracy from 99.9% to at most 71.9% in the paper's sweeps.","Diagonal selective SSMs remain effective for commutative or order-insensitive tasks, where the paper reports near-perfect generalization, but their in-domain success on non-commutative automata does not transfer to longer inputs."],"supporting_citations":[{"why":"Provides the experimental protocol, four of the FSA tasks, and the RNN/Transformer baseline results that SD-SSM is compared against.","marker":"Delétang et al. 2023"},{"why":"Introduces the block-diagonal selective SSM (RegularLRNN) and the operator-normalization scheme that SD-SSM adapts.","marker":"Fan, Chi, and Rudnicky 2024"},{"why":"Supplies the group-based automata C2×C4, D4, and A5, plus the transformation-semigroup view of FSA transition matrices.","marker":"Liu et al. 2023"},{"why":"Defines selective SSMs and the Mamba baseline whose poor Arithmetic length generalization motivates the new architecture.","marker":"Gu and Dao 2023"},{"why":"States the TC0 expressiveness bound for diagonal selective SSMs that the paper contrasts with its commutativity finding.","marker":"Merrill, Petty, and Sabharwal 2024"},{"why":"Provides the Transformer length-generalization result used in Table 1 for comparison.","marker":"Ruoss et al. 2023"},{"why":"Motivates complex diagonal transition matrices, the class analyzed in Section 4.","marker":"Orvieto et al. 2023"}],"fun_headline_variants":["Selective dense SSM perfects length generalization on automata","Diagonal selective SSMs exposed: can't emulate non-commutative automata","Single-layer selective SSM matches any test length on seven FSA tasks","New SD-SSM: theoretical limits of diagonal selective state-space models"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theoretical explanation for the diagonal models' failures rests on assuming that trained one-layer models implement the paper's Section 2 FSA-to-SSM mapping with $b(u_t)=0$; the diagonal models that actually learn the non-commutative automaton $D_{30}$ in Table 4 use $b(u_t)\\ne 0$, so the proposition does not directly cover the empirical case it is meant to explain.","fun_headline_variants_meta":{"raw":{"variants":["Selective dense SSM perfects length generalization on automata","Diagonal selective SSMs exposed: can't emulate non-commutative automata","Single-layer selective SSM matches any test length on seven FSA tasks","New SD-SSM: theoretical limits of diagonal selective state-space models"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000332,"raw_usage":{"total_tokens":1883,"prompt_tokens":1017,"completion_tokens":866,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":788}},"tokens_in":633,"tokens_out":866,"duration_ms":8666,"temperature":1.0,"reasoning_tokens":788,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:40:50.778197+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SD-SSM on the seven Table 1 tasks with the reported hyperparameters and fresh random seeds: the headline claim fails if any task's best-seed accuracy stays below 99.9% on lengths up to 500. Separately, train a single-layer diagonal selective SSM with $b(u_t)=0$ on $D_{30}$; any run that reaches perfect length generalization would contradict Proposition 1, while a failure would leave the paper's mapping assumption as the only explanation.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Transformer length-generalization result used in Table 1 for comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the block-diagonal selective SSM (RegularLRNN) and the operator-normalization scheme that SD-SSM adapts."},{"cited_title":"T.; Goel, S.; Krishnamurthy, A.; and Zhang, C","cited_arxiv_id":null,"evidence_quote":"Supplies the group-based automata C2×C4, D4, and A5, plus the transformation-semigroup view of FSA transition matrices."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the TC0 expressiveness bound for diagonal selective SSMs that the paper contrasts with its commutativity finding."},{"cited_title":"L.; Gu, A.; Fernando, A.; Gulcehre, C.; Pascanu, R.; and De, S","cited_arxiv_id":null,"evidence_quote":"Motivates complex diagonal transition matrices, the class analyzed in Section 4."}],"review_version":1}