REVIEW 4 major objections 6 minor 25 references
The Effect of Depth on the Expressivity of Deep Linear State-Space Models
T0 review · 4 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read The paper proves that bounded-norm deep linear state-space models represent large-norm shallow ones with exponentially smaller weights, and that without norm constraints depth and width are equivalent.
desk verdict The norm-reduction result is new and likely right, but Lemma 8's bound is false as written, so the paper needs a proof fix before I'd rely on it. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the complete homogeneous symmetric function $F_t(\alpha_1,\dots,\alpha_n)=\sum_{i=1}^n \alpha_i^{t+n-1}/\prod_{j\ne i}(\alpha_i-\alpha_j)$, which equals the sum of all monomials of total degree $t$ in the $\alpha$'s and appears as the coefficient of each diagonal path in the convolutional kernel of Lemma 3.1. Lemma 8 supplies the factorization identity $\sum_{k=1}^n H_k F_t(\beta_1,\dots,\beta_k)=\sum_{k=1}^n Z_k\beta_k^t$ with coefficient bound $|H_k|\le 2n\max_i|Z_i|$ when the $|\beta_i|$ are nondecreasing. This identity lets a single large term $Z_i\sigma_i^t$ in a one-layer kernel be distributed across layers as products of matrices whose entries are of order $Z_0=2(\max_i|B_iC_i|)^{1/(l+1)}$, which is exactly the exponential norm reduction in Theorem 4.2.
What would settle it
For a fixed wide diagonal one-layer model, use the coefficient formula in Lemma 5.1 to write exact matching equations for the smallest-norm equivalent $l$-layer model; a single instance whose minimal feasible norm exceeds $2c_1^{2/(l+1)}$ would disprove Theorem 4.2.
Extended reading notes
Core claim
The central claim is a constructive containment theorem. For diagonal state matrices, $H^{l(m-1)+1}_{c_1,1} \subseteq H^m_{2c_1^{2/(l+1)},l}$; a wide one-layer kernel built from large weights can be factored exactly into $l$ layers of smaller weights, with the norm bound following from splitting each product of input and output weights into $l+1$ equal factors. Theorem 4.3 quantifies the cost of this compression: a shallow kernel with norm $c_1$ can be represented with norm $c_2$ using depth at most $\lceil 2\ln(c_1)/\ln(c_2/2)-1\rceil$ and width $\lceil K/l\rceil+1$, keeping parameter count fixed. Without norm constraints the same construction gives the two-sided bound $H^{l(m-1)+1}_{\infty,1} \subseteq H^m_{\infty,l} \subseteq H^{lm}_{\infty,1}$, with the lower width sharp. The paper takes this contrast as the main message: depth and width are equivalent only when weights are unbounded; once weights are bounded, depth is a separate resource that compresses norm exponentially.
Load-bearing premise
The results assume the state-transition matrices are diagonal (or normal, i.e. unitarily diagonalizable with condition number one) and place the norm constraint only on the input and output weights, so if a practical model requires an ill-conditioned diagonalization, the exponential norm reduction need not survive.
Editorial extensions
If this is right
- For linear SSMs without norm constraints, depth is not intrinsically more expressive than width: every $l$-layer width-$m$ model is equivalent to a one-layer model of width $lm$, and there are one-layer kernels of width $l(m-1)+2$ that no $l$-layer width-$m$ model can represent.
- With norm constraints, deeper models dominate: a width $l(m-1)+1$ kernel requiring norm $c_1$ can be realized by $l$ layers of width $m$ with norm at most $2c_1^{2/(l+1)}$, so the required norm decays exponentially in depth.
- The depth needed to bring a large-norm shallow model down to a prescribed norm $c_2$ grows only logarithmically, roughly $2\ln(c_1)/\ln(c_2/2)$, at constant parameter count.
- The same norm-reduction construction works when the state matrices are normal, with the norm bound gaining a mild width factor $((l(m-1)+1)c_1^2)^{1/(l+1)}$; without norm constraints, diagonalizable and diagonal hypothesis spaces coincide.
- In experiments, replacing a wide one-layer S4 with a deeper, narrower S4 of the same effective expressivity improves MNIST accuracy but increases per-epoch runtime.
Reading between the lines
- The authors do not pursue it, but the norm-reduction bound suggests that any training procedure with weight decay or spectral-norm regularization should systematically prefer deeper factorizations of the same kernel, which is a testable prediction about optimization trajectories.
- The bound in Theorem 4.2 does not constrain the $A_i$ norms; if one instead bounds the full parameter set including $A_i$, the exponential saving could shrink or vanish, especially for non-normal $A_i$ with large condition number.
- Although the theory is linear, the construction factors a large weight into $l+1$ small factors, so a natural extension is to check whether the same factorization persists in the Jacobian of a nonlinear SSM near a stable fixed point, which would transfer the norm-reduction effect to nonlinear training.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the expressive capacity of deep linear state-space models (SSMs) with scalar input/output and diagonal state-transition matrices. It defines norm-constrained hypothesis spaces and proves three types of results. Theorem 4.1 characterizes depth-width equivalence without norm constraints, giving H^{l(m-1)+1}_{∞,1} ⊆ H^m_{∞,l} ⊆ H^{lm}_{∞,1} and showing that width l(m-1)+2 cannot be compressed to l layers of width m. Theorem 4.2, the main contribution, states that under a norm constraint c1, every one-layer SSM of width l(m-1)+1 can be represented exactly by an l-layer SSM of width m whose parameter norm is at most 2 c1^{2/(l+1)}, yielding an exponential norm-reduction effect of depth. Theorem 4.3 converts this into an upper bound on the minimal depth needed to represent a given shallow model under a prescribed norm budget, and Corollary 4.4 extends the norm-reduction result to normal state matrices. Numerical experiments on linear SSMs and on an S4 model for sequential MNIST illustrate the qualitative findings.
Significance. The paper addresses a timely and relevant question: why depth helps in SSMs beyond mere parameter count. If rigorously established, the main claim is a clean constructive result: bounded-norm shallow SSMs can be repacked into deeper SSMs with substantially smaller norms at essentially the same parameter count. This is a genuine expressivity phenomenon, not a parameter-count artifact, and the explicit construction is a useful stepping stone for further theory. The paper is self-contained and does not fit any quantity to data; the constructions are explicit and the appendix provides proof sketches. These are notable strengths. However, the current manuscript contains several proof gaps in load-bearing places, including an incorrect inequality in the key norm bound (Lemma 8) and a non-rigorous perturbation argument (Lemma 5). These appear repairable, but as submitted the central theorems are not fully established.
major comments (4)
- [Appendix A.3, Lemma 8, Eqs. (56)-(59)] The claimed bound |H_k| ≤ 2n max_i |Z_i| is false. The displayed chain contains the step Σ_{j=k}^n |Z_j| 2^{k-1} ≤ 2n max_i |Z_i|, which fails already for k = n and n ≥ 5. Since this bound is invoked in Remark 2 to show that all constructed entries of B_i are bounded by Z0, Theorem 4.2's norm-reduction claim is not proved as written. I note that a correct estimate is |H_k| ≤ (n-k+1)2^{k-1} max_i |Z_i| ≤ 2^{n-1} max_i |Z_i|, and because Z0 = 2 M^{1/(l+1)} this corrected estimate is still strong enough to yield |H_k|/Z0^l ≤ Z0 for the construction in Lemma 9. The theorem therefore appears salvageable, but the current proof has a real gap at this load-bearing step.
- [Appendix A.3, Lemma 5] The proof of Lemma 5 is a sketch rather than a proof. The step "By considering the first-order asymptotic ... we have Σ_{β_ji ∈ B(α_j,ε)} c_ji β_ji^t = B_j(t) α_j^t + o(1)" needs a rigorous justification, and the subsequent case distinction on Σ deg(B_j) does not account for the fact that the coefficients c_ji and the perturbed locations β_ji are free variables of the infimum. Because Lemma 5 underpins Lemma 6, the sharp non-containment H^{l(m-1)+2}_{∞,1} ⊄ H^m_{∞,l} in Theorem 4.1 is currently not established to the standard of a proof.
- [Appendix A.3, Lemma 7] Lemma 7 constructs a one-layer model whose state-transition matrix A0 is a block upper-triangular matrix with non-zero off-diagonal blocks (Eq. (42)). Since the hypothesis space H^{lm}_{∞,1} restricts A to be diagonal, the constructed model is not a member of H^{lm}_{∞,1} as defined. The proof needs an additional step, such as reducing to distinct eigenvalues and diagonalizing A0 while absorbing the similarity transform into B0 and C0. Without that step, the inclusion H^m_{∞,l} ⊆ H^{lm}_{∞,1} in Eq. (4) is not proved.
- [Appendix A.3, Lemma A.1] The proof of Lemma A.1 appears to use the wrong similarity convention. If A_i = P_i^{-1} D_i P_i, then A_i^t = P_i^{-1} D_i^t P_i, so the transformed matrices should be \hat{C} = P_l^{-T} C, \hat{B}_j = P_j B_j P_{j-1}^{-1} (with \hat{B}_1 = P_1 B_1), not the expressions displayed in the proof. As written, substituting the displayed \hat{C}, \hat{B}_j does not reproduce ρ(t). This lemma is used to justify the claim that the diagonalizable case reduces to the diagonal case, so the proof needs correction or a clarified convention for P_i.
minor comments (6)
- [Section A.1, proof of Lemma 3.1] The proof is introduced as "A proof of Theorem 3.1"; the reference should be to Lemma 3.1.
- [Section 5] The result stated as "Theorem 5.1" is later called "Lemma 5.1"; the numbering and labeling are inconsistent.
- [Section 4.2, example after Theorem 4.2] The displayed bound "max{|z_i^2|+|z_{i+4}^2|}/Z0^2 ≤ Z0" omits the prefactor |(α_{i+4}-α_i)/α_{i+4}| ≤ 2 for the first class of B2 entries; the conclusion still holds with a slightly larger constant, but the displayed inequality is not a direct bound for all entries.
- [Section 4.3] The prose says "To maintain a constant parameter count, we set the width..."; with width ⌈K/l⌉+1 the total number of parameters is l⌈K/l⌉ + O(l) ≈ K + O(l), which is not constant as l varies. The abstract's phrase "same order of magnitude" is more accurate.
- [Section 5 and Figure 1] The text alternately says the numerical experiment "applies the construction from Theorem 4.2" and uses a "teacher–student" learning setup; please clarify what is actually computed and how the reported "Max Norm" is obtained.
- [Section 3.2, Eq. (3)] Equation (3) places B2,...,Bl in C^{m×m} but the norm constraint is written only as max_{2≤k≤l} max_{i,j} |(B_k)_{ij}|; the roles of B1 and C are handled by infinity-norm bounds, but the notation should be made consistent for readability.
Circularity Check
No significant circularity: the expressivity and norm-reduction claims are derived by explicit construction from definitions; no fitted quantity is renamed as a prediction and no load-bearing self-citation appears.
full rationale
The paper's load-bearing result (Theorem 4.2, Eq. 5) is not an input to its own proof. It is obtained from Lemma 9's explicit conversion of a one-layer diagonal SSM into an l-layer SSM, with the norm bound following from Lemma 8's expansion identity and the chain of inequalities bounding |H_k|. All ingredients (Lagrange interpolation, the F_t representation, the ansatz for alpha(i,j) and Z(i,j)) are stated and proved inside the paper; none is a fitted parameter, an empirical pattern, or a prior result whose truth is assumed. The depth-width equivalence without norm constraints (Theorem 4.1) is likewise an exact algebraic construction, not a renaming of a known empirical fact. Citations to S4, Mamba, HiPPO, and related work are motivational or contextual and do not carry the load of the proofs; there are no self-citations that supply a uniqueness or existence theorem. The diagonal-A assumption is an explicitly stated modeling choice, not a hidden ansatz imported through citation. The numerical experiments in Section 5 are external checks of the constructive bound, not part of the derivation. The proof-correctness concern about the step from Eq. (58) to Eq. (59) in Lemma 8, if valid, would be a mathematical error or gap in the paper's proof, not circularity: the disputed inequality is a derived estimate that the proof aims to establish, and the theorem is not equivalent to its premise by definition. No self-definitional, fitted-input, or self-citation circularity is present, so the appropriate score is 0.
Assumptions & free parameters
assumptions (4)
- domain assumption State-transition matrices A_i are diagonal in the main hypothesis space H^m_{c,l}.
- domain assumption Spectral radius of each A_i is strictly less than 1.
- domain assumption Target one-layer SSMs are considered with distinct non-zero eigenvalues in the generic case; degenerate cases are handled by limits.
- domain assumption Input and output are scalar-valued.
Cite this review
Pith. "Pith review of The Effect of Depth on the Expressivity of Deep Linear State-Space Models." pith.science (2026). https://pith.science/paper/YAZ27MHI
@misc{pith2026250619296,
author = {Pith},
title = {Pith review of: The Effect of Depth on the Expressivity of Deep Linear State-Space Models},
year = {2026},
howpublished = {\url{https://pith.science/paper/YAZ27MHI}},
note = {Machine review of arXiv:2506.19296}
}
read the original abstract
Deep state-space models (SSMs) have gained increasing popularity in sequence modelling. While there are numerous theoretical investigations of shallow SSMs, how the depth of the SSM affects its expressiveness remains a crucial problem. In this paper, we systematically investigate the role of depth and width in deep linear SSMs, aiming to characterize how they influence the expressive capacity of the architecture. First, we rigorously prove that in the absence of parameter constraints, increasing depth and increasing width are generally equivalent, provided that the parameter count remains within the same order of magnitude. However, under the assumption that the parameter norms are constrained, the effects of depth and width differ significantly. We show that a shallow linear SSM with large parameter norms can be represented by a deep linear SSM with smaller norms using a constructive method. In particular, this demonstrates that deep SSMs are more capable of representing targets with large norms than shallow SSMs under norm constraints. Finally, we derive upper bounds on the minimal depth required for a deep linear SSM to represent a given shallow linear SSM under constrained parameter norms. We also validate our theoretical results with numerical experiments
Figures
Reference graph
Works this paper leans on
-
[1]
A convergence analysis of gradient descent for deep linear neural networks
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. arXiv preprint arXiv:1810.02281, 2018
arXiv 2018
-
[2]
Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers
Bubacarr Bah, Holger Rauhut, Ulrich Terstiege, and Michael Westdickenberg. Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers. Information and Inference: A Journal of the IMA, 11 0 (1): 0 307--353, 2022
2022
-
[3]
The emergence of clusters in self-attention dynamics
Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. The emergence of clusters in self-attention dynamics. Advances in Neural Information Processing Systems, 36: 0 57026--57037, 2023
work page 2023
-
[4]
It’s raw! audio generation with state-space models
Karan Goel, Albert Gu, Chris Donahue, and Christopher R \'e . It’s raw! audio generation with state-space models. In International conference on machine learning, pp.\ 7616--7633. PMLR, 2022
work page 2022
-
[5]
On the Role of Initialization on the Implicit Bias in Deep Linear Networks
Oria Gruber and Haim Avron. On the role of initialization on the implicit bias in deep linear networks. arXiv preprint arXiv:2402.02454, 2024
work page Pith review arXiv 2024
-
[6]
Mamba: Linear-time sequence modeling with selective state spaces
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023
arXiv 2023
-
[7]
Hippo: Recurrent memory with optimal polynomial projections
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher R \'e . Hippo: Recurrent memory with optimal polynomial projections. Advances in neural information processing systems, 33: 0 1474--1487, 2020
2020
-
[8]
Efficiently modeling long sequences with structured state spaces
Albert Gu, Karan Goel, and Christopher R \'e . Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00396, 2021 a
arXiv 2021
Show all 25 references
-
[9]
Combining recurrent, convolutional, and continuous-time models with linear state space layers
Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher R \'e . Combining recurrent, convolutional, and continuous-time models with linear state space layers. Advances in neural information processing systems, 34: 0 572--585, 2021 b
2021
-
[10]
Diagonal state spaces are as effective as structured state spaces
Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces. Advances in Neural Information Processing Systems, 35: 0 22982--22994, 2022
2022
-
[11]
Estimation and inference of impulse responses by local projections
\`O scar Jord \`a . Estimation and inference of impulse responses by local projections. American economic review, 95 0 (1): 0 161--182, 2005
2005
-
[12]
Videomamba: State space model for efficient video understanding
Kunchang Li, Xinhao Li, Yi Wang, Yinan He, Yali Wang, Limin Wang, and Yu Qiao. Videomamba: State space model for efficient video understanding. In European Conference on Computer Vision, pp.\ 237--255. Springer, 2024
2024
-
[13]
The geometry of the deep linear network
Govind Menon. The geometry of the deep linear network. arXiv preprint arXiv:2411.09004, 2024
2024 arXiv
-
[14]
Theoretical foundations of deep selective state-space models
Nicola Muca Cirone, Antonio Orvieto, Benjamin Walker, Cristopher Salvi, and Terry Lyons. Theoretical foundations of deep selective state-space models. Advances in Neural Information Processing Systems, 37: 0 127226--127272, 2024
2024
-
[15]
S4nd: Modeling images and videos as multidimensional signals with state spaces
Eric Nguyen, Karan Goel, Albert Gu, Gordon Downs, Preey Shah, Tri Dao, Stephen Baccus, and Christopher R \'e . S4nd: Modeling images and videos as multidimensional signals with state spaces. Advances in neural information processing systems, 35: 0 2846--2861, 2022
2022
-
[16]
On the difficulty of training recurrent neural networks
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp.\ 1310--1318. Pmlr, 2013
2013
-
[17]
Diagonal state space augmented transformers for speech recognition
George Saon, Ankit Gupta, and Xiaodong Cui. Diagonal state space augmented transformers for speech recognition. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.\ 1--5. IEEE, 2023
2023
-
[18]
On the interplay between learning and memory in deep state space models
Jakub Smekal, Nicolas Zucchet, Dan Biderman, E Kelly Buchanan, Jimmy TH Smith, and Scott Linderman. On the interplay between learning and memory in deep state space models. 2024
2024
-
[19]
Simplified state space layers for sequence modeling
Jimmy TH Smith, Andrew Warrington, and Scott W Linderman. Simplified state space layers for sequence modeling. arXiv preprint arXiv:2208.04933, 2022
2022 arXiv
-
[20]
Long range arena: A benchmark for efficient transformers
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. arXiv preprint arXiv:2011.04006, 2020
2011 arXiv
-
[21]
Attention is all you need
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017
2017
-
[22]
Demystifying the token dynamics of deep selective state space models
Thieu N Vo, Tung D Pham, Xin T Tong, and Tan Minh Nguyen. Demystifying the token dynamics of deep selective state space models. arXiv preprint arXiv:2410.03292, 2024
2024 arXiv
-
[23]
State-space models with layer-wise nonlinearity are universal approximators with exponential decaying memory
Shida Wang and Beichen Xue. State-space models with layer-wise nonlinearity are universal approximators with exponential decaying memory. Advances in Neural Information Processing Systems, 36: 0 74021--74038, 2023
2023
-
[24]
Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017
2017 arXiv
-
[25]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.