- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies how parallelizable sequence models with order-symmetric layers (diagonal SSMs, linear attention, and, as the authors argue, transformers) perform on tasks outside their exact expressivity, and how depth changes this. SSMs are modeled as controlled affine ODEs and classified by the Lie algebra their vector fields generate. The main results are:
(1) A single "restricted" layer (abelian linear part with an input-dependent bias) incurs a worst-case error lower-bounded in proportion to the second Magnus term ||Omega_2|| (Thm 3.2).
(2) A Lie algebra extension can be simulated by a two-layer SSM, so k abelian layers simulate any solvable system of derived length k (Thm 3.4, Cor 3.5).
(3) Non-solvable systems can be approximated by k abelian layers with local error O(eps^(2^k)) via free-nilpotent truncation (Cor 3.7).
(4) Word problems of length <= T are solvable with floor(log2 T)+1 abelian layers (Prop 3.8).
Validation consists of length-generalization experiments on word problems over C2, C3, D8, H3, S3, S4, and A5 with GLA, Mamba variants, AUSSM, transformers, and DeltaProduct, plus an A5 rigid-body rotation regression task. That task includes a width control and commutator-probe words that test the ||Omega_2|| scaling of 1-layer models.
Critical strengths
-
A quantitative, width-independent lower bound on order-sensitive error. Thm 3.2's four-input difference-of-differences construction cancels the inhomogeneous terms and shows that any restricted layer, of any width, incurs error tied to ||Omega_2||. This moves beyond binary can/can't expressivity results toward the error-scaling question the paper sets out to answer. It is the most original and most convincing contribution, and it is directly probed by Fig. 3b.
-
A clean structural account of depth via the derived series. Using the derived series as a budget for depth (Prop 3.3 together with Cor 3.5) gives a principled explanation of why depth, rather than width, extends the expressivity of order-symmetric layers. The 8x width control in Fig. 3a supports this qualitatively. Even with the concerns below, the framework is a useful lens that others could build on.
Critical weaknesses
- The experiments are not connected to the theorems they are said to validate. Thm 3.4 and Cor 3.5 concern Lie algebra extensions, while D8, S3, and S4 are finite groups with trivial Lie algebra. The Lie algebra generated by logarithms of a representation's generators depends on the embedding; for example, S3 realized in SO(3) generates so(3), which is not solvable. Moreover, finite subgroups of connected solvable Lie groups are abelian, so a 2-layer abelian solution for S3 must be a nonlinear cascade. That is plausible, and close to what Shakerinava et al. (2026) prove in discrete time, but it is not what Thm 3.4 states.
Separately, Signed Mamba relies on negative real eigenvalues, which cannot arise from discretizing a real diagonal continuous-time generator, and softmax attention does not fit Def. 2.1 at all. Table 2 and Figs. 2-3a are therefore suggestive but do not test the theory. This matters because the paper presents the experiments as validation.
- The headline depth-error claim is not established as stated. First, the local-to-global argument for Cor 3.7 (App. C.6) bounds a product of per-window truncated flows. The constructed model does not compute that product: it accumulates state in the free nilpotent group and applies a non-homomorphic output map once. Realizing the product would require accumulating in the non-solvable group itself. As far as I can tell, the result holds only while the total generator mass stays within the Magnus convergence region.
Second, the lower bound (Thm 3.2) assumes a linear readout, while all the upper bounds allow arbitrary smooth readouts. With smooth readouts and bounded length, even a single sufficiently wide restricted layer can encode the input injectively, and Prop 3.8 is itself a memorization construction. So the claim that depth, rather than width, is the mechanism is not cleanly separated by the results. Together these undercut the abstract's central claim that error "diminishes exponentially as the depth increases." The claimed rate is also doubly exponential in k, not exponential.
Questions for authors
-
How does the per-window telescoping argument in App. C.6 apply to the constructed deep abelian SSM, given that its output map exp o ev o log is not a group homomorphism? If it doesn't, what global statement survives?
-
What result connects the derived length of a finite group to the derived length of the Lie algebra of an SSM that solves its word problem? Is the 2-layer claim for D8 and S3 in Sec. 4.1 meant to follow from Thm 3.4, or from a separate cascade construction?
-
Does Thm 3.2, or the "restricted vs. abelian" distinction, survive if the linear readout P is replaced by a smooth nonlinear readout, as used in the upper bounds?
-
How are Signed Mamba's negative real eigenvalues accommodated in a continuous-time framework where every transition is a matrix exponential?
-
Table 2 uses 8 tokens for H3. If this is the Heisenberg group over F2, it is isomorphic to D8. Are the two columns testing the same group?
-
In the proof of Thm 3.2, can you justify the inequality ||e^X - e^Y|| >= e^(-max(||X||,||Y||)) ||X - Y|| for non-commuting X, Y, and the choice of prefixes that aligns h1 - h2 with the dominant direction of M?
Suggestions that would strengthen the paper:
-
Run 3-layer models on S4 (and include A4). Cor 3.5 predicts these thresholds sharply, so this would be a direct test.
-
Measure error as a function of eps and depth, for example with fractional rotations, and fit a log-log slope in Fig. 3b against the predicted exponent. Note that MSE should scale quadratically if the norm bound is tight.
3 comments
Response to Reviewer QRcZ, part 2/3
[Q4, part of Weakness 1] How are Signed Mamba’s negative real eigenvalues accommodated in a continuous-time framework?
Here we note that being abelian requires commutativity, not real-diagonal structure. We can represent any as an element of . Specifically, any complex-diagonal matrix can be represented as real block-diagonal matrix (e.g. Orvieto 2023):
a & -b \\\\ b & a \end{pmatrix},$$ which keeps commutativity. Therefore, our theory applies to the continuous-time interpretation of the Signed Mamba, and AUSSM further. > [Q5] $H_3(F_2)$ is isomorphic to $D_8$. Are the two columns testing the same group? Yes, they are isomorphic. We included both as a consistency check with different encodings of the same group. We also observed no performance differences in their matrix-based task either. We will state the isomorphism more clearly. > [Q6] Justify matrix exponential inequality in the proof of Thm 3.2. Also justify the choice of prefixes that aligns $h_1 - h_2$ with the dominant direction of $M$. It is important to clarify these points. First, the inequality stems from the matrix operator norm. When $r = \max(\Vert X\Vert_2, \Vert Y\Vert_2) \le 1$, we have Von Neumann’s operator norm inequality: $$\Vert(zI + \exp X)^{-1}\Vert_2 \le (z + e^{-r})^{-1}$$ and similarly for $Y$. With the integral representation of the logarithm, $$X - Y = \int_0^\infty (zI + e^Y)^{-1}(e^X - e^Y) (zI + e^X)^{-1}dz.$$ Therefore, $$\Vert X-Y\Vert_2 \le \Vert e^X-e^Y\Vert_2 \int_0^\infty \frac{dz}{(z+e^{-r})^2} = e^r \Vert e^X-e^Y\Vert_2.$$ Note that this does not require commuting $X,Y$. We can switch operator norm to any submultiplicative norm at a cost of slightly weaker constant. For $r = \max(\Vert X\Vert, \Vert Y\Vert) < \log 2$, $$\Vert e^X - e^Y - (X-Y)\Vert \le \sum_{n=2}^\infty \frac{\Vert X^n-Y^n\Vert}{n!} \le (e^r-1) \Vert X - Y\Vert,$$ via telescoping series. With reverse triangular inequality, we achieve: $$\Vert e^X-e^Y\Vert \ge (2-e^r)\Vert X - Y\Vert = \lambda \Vert X - Y\Vert, \quad \lambda \in (0,1].$$ We will clarify this in the proof and relevant places. Second, the prefix choice leverages the minimality condition, specifically the controllability (Sec 2.1, App B.1). Intuitively, we can lift the prefix assumption by simply choosing two different initial states $(h_1,h_2)$ such that $h_1 - h_2$ does not fall under $\ker M$, and then run the second part of the constructed input. In this view, 4-input subtraction is a trick to reveal differences in initial states carried through affine dynamics. Controllability prescribes prefixes to reach at different “initial” states. > [part of Weakness 1] Softmax attention does not fit Def 2.1. We agree, the transformer was included as a reference model that is similarly parallelizable and order-symmetric with respect to the layer input.Response to Reviewer QRcZ, part 3/3
[Q7] Run 3-layer models on , and include .
Thank you for suggesting the direct test. We trained 2-layer Signed Mamba and AUSSM on , and 3-layer on , but models failed to learn solutions in both tasks. This aligns with the struggle in the task. Shakerinava et al. similarly observed failures in and tasks. These observations clearly show a gap between theory and practice. By manually initializing weights near the analytical solution set, Shakerinava et al. were able to train 2-layer AUSSM on . To probe the learnability issue further, we performed a curriculum task.
We pretrained a 1-layer AUSSM on a quotient of word problem. Specifically, the input tokens are still symbols, but the target tokens are quotient symbols. Next, we warm-started the embedding plus the first residual block of 2-layer AUSSM with the pretrained weights.
We observed the warm-started model successfully learns the word problem with 1.00 sequence accuracy. In contrast, standard 2-layer AUSSM remained at 0 accuracy even after doubling the training epochs. This result suggests the gap between theory and practice partially arises from the optimization process.
[Q8] Measure error as a function of eps and depth.
We fitted a log-log slope in Fig. 3b. As the reviewer predicted, Transformer and GLA scales close to quadratic scale in our probe regime, with mean slope 2.17 and 2.45 respectively. Signed Mamba shows a slightly weaker trend (1.67), potentially from a higher floor error at the smallest probes. We will update Fig. 3b accordingly.
For error against and depth, we are running suggested fractional rotation experiments. Preliminary GLA results below show the benefit of small and depth. Note that the depth effect quickly plateaus:
| Depth / Relative | 1 | 1.67 | 2 |
|---|---|---|---|
| 1 | 0.03 | 0.11 | 0.2 |
| 2 | 3e-3 | 0.013 | 0.03 |
| 4 | 2.9e-3 | 4.5e-3 | 9.9e-3 |
| 6 | 4.2e-3 | 3.8e-3 | 9.2e-3 |
| 8 | 3.8e-3 | 3.7e-3 | 8.6e-3 |
In comparison, length 32 probes on A5 rotation task shows more sustained depth-dependent trend at a cost of shallow model saturation.
| Depth / Relative | 1 | 1.67 | 2 |
|---|---|---|---|
| 1 | 0.35 | 0.33 | 0.33 |
| 2 | 0.3 | 0.33 | 0.33 |
| 4 | 0.013 | 0.026 | 0.046 |
| 6 | 3.0e-3 | 4.4e-3 | 6.9e-3 |
| 8 | 1.4e-3 | 2.2e-3 | 3.5e-3 |
Together, we observe qualitative benefits of depth and smaller , but do not directly confirm the predicted scaling across settings. Gradient-based optimization need not find the solution constructed in Cor 3.7, and finite precision may further obscure trends in a smaller error regime. We will continue remaining experiments and report the results in the appendix.
Thank you again for the clear and constructive feedback. We will soon revise our manuscript and update it. We would deeply appreciate any further comments.
Response to Reviewer QRcZ, part 1/3
We deeply appreciate the thoughtful feedback and careful reading. Addressing these points improves the quality of our work.
This is a keen observation. We agree that our per-window product argument overlooked the group homomorphism issue, and the local-to-global statement in App.C.6 needs to be revised. The global statement can nevertheless be repaired by using the Peano-Baker series (e.g. Baake and Schlägel, 2011), without major revision in the main text.
The class c free nilpotent construction is still the universal construction, which contains all the information needed to evaluate the Peano-Baker term up to c-th order. Rather than logarithmic Magnus evaluation, the Peano-Baker series uses time-ordered products to represent flow:
\quad \mathcal{I}_n(T) := \int_{t_0<t_n<\cdots<t_1<T} A(x(t_1)) \cdots A(x(t_n)) \, dt_n \cdots dt_1.$$ Then the truncated Peano-Baker series readout is simply $\Phi_c(t,t_0) = I + \sum_{n=1}^c \mathcal{I}_n(t)$. Importantly, the Peano-Baker series converges when the generator mass is finite. Therefore, we can evaluate the global error bound at once: $$\Vert\Phi(T,0) - \Phi_c(T,0)\Vert= \Vert\sum_{n=c+1}^\infty \mathcal{I}_n(T)\Vert \le \sum_{n=c+1}^\infty \frac{\epsilon^n}{n!} \le \exp(\epsilon) \frac{\epsilon^{c+1}}{(c+1)!}.$$ Take $c = 2^k - 1$ again, $$\Vert\Phi(T,0) - \Phi_c(T,0)\Vert \le \exp(\epsilon) \frac{\epsilon^{2^k}}{(2^k)!}.$$ When $\epsilon$ is small, we recover $\mathcal{O}(\epsilon^{2^k})$, doubly exponential in $k$. We will revise App.C.6, local-to-global paragraph, accordingly. We will further revise the abstract to describe the doubly exponential rate. > [Q2, part of Weakness 1] What result connects the derived length of a finite group to the derived length of the theory? This is a theoretically very important point. We agree that the word problem is not a direct test of our continuous Lie-algebraic statements but more of a bridge to the existing well-established benchmarks. As reviewer kindly noted, Shakerinava et al., directly worked on finite group regimes. In particular, $D_8$ and $S_3$ have derived length 2, giving a 2-layer discrete realization with 1 abelian layer per factor. Importantly, each abelian factor layer also admits continuous realization. Any finite abelian group faithfully embeds to a torus via roots of unity, so abelian factor symbol action is realized by a flow of commuting rotation generators. Thus, every abelian factor layer in the discrete construction can be seen as an exactly sampled abelian SSM. We see these two as a shared extension-based mechanism applied in two regimes. Our construction begins from the Lie extension and decomposes integrated flow to quotient and kernel components. Shakerinava et al. begins from the finite group extension and applies a similar decomposition. Our attempt was to bridge our result with this key previous work. We will adjust our tone and present word problems as a diagnostic of a discrete analog of our theory, attributing Shakerinava et al.’s contribution. > [Q3, part of Weakness 2] With smooth readouts and bounded length, one restricted layer suffices. Does Thm 3.2, or restricted vs. abelian, survive if $\mathbf{P}$ is replaced by a smooth readout? On a *bounded* horizon, sufficiently wide linear recurrence followed by a nonlinear readout can memorize without loss (e.g. Orvieto et al., 2024). The quantitative bound in Thm 3.2 does not survive with a smooth readout in general. We clarify our notion of simulation below. In Def B.1, simulation fixes initialized SSMs and smooth state map $\varphi$, valid for *every* admissible input and horizon (Krener 1977). Def B.2 quantifies the best simulation error on a given window. For 1-layer SSM, $\varphi$ is restricted to fixed $\mathbf{P}$, preserving the affine SSM class (Toth 2010). Thm 3.2 rules out simulation by showing no fixed $\mathbf{P}$ can match the target state evolution for *all* $T>0$. Similarly, smooth maps in Thm 3.4, Cor 3.5, and Cor 3.7 are horizon-independent. In contrast, the memorizing structure is built per bounded window, which is not necessarily a simulation in our strict sense. As reviewer said, no width-independent bound holds with the arbitrary smooth readout for fixed window, and we did not intend to claim this. The restricted vs. abelian distinction survives with pointwise nonlinearity. Abelian SSM reaches the identical state upon permuted input, which no readout can distinguish. On the other hand, restricted SSM can retain order information. More generally, pointwise nonlinear readout does not add derived length (also Prop 3.3).