{"id":"52d9c11a-9e2c-4025-9784-123d18ed3887","arxiv_id":"2506.19296","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Deeper linear state-space models can match the expressive power of shallower wider ones, and under norm constraints they do so with exponentially smaller parameter norms.","lead":"This paper proves that in linear state-space models, depth and width can be swapped freely when parameter norms are unbounded, but depth becomes strictly more valuable when norms are capped. It gives explicit constructions showing deeper models can represent the same functions with much smaller weights, which may explain why stacked state-space models train more stably.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 8's bound, used to prove Theorem 4.2's norm reduction, contains a false inequality; the central proof needs an independent check.","rationale":"The reader's weakest-assumption analysis points to the diagonal-A restriction and the lack of a norm bound on A_i; that is a real scope limitation, especially because Section 4.4 explicitly leaves diagonalizable matrices open and condition numbers could destroy the transfer. My independent read, however, found a more immediate and concrete issue inside the proof of the central claim: Lemma 8's coefficient bound is false as stated, and Theorem 4.2's norm bound is obtained by applying this lemma in Remark 2. This is load-bearing because the exponential norm reduction is exactly the paper's evidence that depth beats width under norm constraints. I checked whether the flaw is fatal to the theorem: with the corrected worst-case bound |H_k| ≤ 2^{n−1}max|Z_i|, the constructed B entries appear bounded by roughly (1/2)max|Z_i|^{1/(l+1)}, which is below Z_0 = 2max|Z_i|^{1/(l+1)}; so the theorem is likely salvageable. For this reason I do not move the verdict: the paper remains conditionally acceptable, but the authors should repair Lemma 8's bound and re-verify the norm estimate in Lemma 9. The diagonalizable gap remains an important scope caveat, so I partially agree with the reader rather than fully agreeing or disagreeing.","tokens_in":20822,"tokens_out":31538,"duration_ms":296430,"concrete_test":"Set n=5, β=(1, e^{i0.01}, e^{-i0.01}, e^{i0.02}, -1), all with |β_p|=1 and distinct, and set Z_j=1. Compute H_5 using the definition in Lemma 8. If |H_5| > 10 = 2n max|Z_i|, the lemma as stated is false. Then, for the 5-layer construction in Lemma 9, evaluate the maximum entry of B_2,...,B_5 and C with these α values; if the max is still ≤ Z_0 = 2(max|Z_i|)^{1/6}, Theorem 4.2's norm bound survives and only the proof of Lemma 8 needs correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the exponential norm reduction in Theorem 4.2, and its proof rests on Lemma 8's bound |H_k| ≤ 2n max|Z_i|. The step from Eq. (58) to Eq. (59) asserts Σ_{j=k}^n |Z_j| 2^{k-1} ≤ 2n max|Z_i|, which is false for large k: for k=n it would require 2^{n-1} max|Z_i| ≤ 2n max|Z_i|, failing for n≥5. Each factor |(β_j−β_p)/β_j| can be arbitrarily close to 2 (take all |β_p| equal and β_1,...,β_{n−1} all close to 1 while β_n=−1), so the product is genuinely exponential in k. Lemma 9 then bounds the constructed B_i entries by H/Z0^l, and Remark 2 invokes this same bound to assert the entries are ≤ Z0. As written, the proof of the norm reduction therefore has a real gap at the load-bearing step. A corrected worst-case bound is |H_k| ≤ (n−k+1)2^{k−1}max|Z_i| ≤ 2^{n−1}max|Z_i|, which still appears small enough to imply the constructed entries are ≤ Z0, so the theorem may be repairable, but the version in the paper does not currently establish it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21091,"tokens_out":20001,"duration_ms":185434,"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":[{"comment":"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.","section":"Appendix A.3, Lemma 8, Eqs. (56)-(59)"},{"comment":"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.","section":"Appendix A.3, Lemma 5"},{"comment":"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.","section":"Appendix A.3, Lemma 7"},{"comment":"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.","section":"Appendix A.3, Lemma A.1"}],"minor_comments":[{"comment":"The proof is introduced as \"A proof of Theorem 3.1\"; the reference should be to Lemma 3.1.","section":"Section A.1, proof of Lemma 3.1"},{"comment":"The result stated as \"Theorem 5.1\" is later called \"Lemma 5.1\"; the numbering and labeling are inconsistent.","section":"Section 5"},{"comment":"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":"Section 4.2, example after Theorem 4.2"},{"comment":"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":"Section 4.3"},{"comment":"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":"Section 5 and Figure 1"},{"comment":"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.","section":"Section 3.2, Eq. (3)"}],"recommendation":"major_revision","confidential_remarks":"This is a theory paper with a clear and plausible main message: depth can exponentially reduce the norm needed to represent a linear SSM kernel. The constructive argument is likely correct and repairable, but the current proof contains a false inequality in Lemma 8, an under-specified perturbation argument in Lemma 5, and incomplete diagonalization arguments in Lemmas 7 and A.1. I recommend major revision rather than rejection; the authors should fix these issues carefully before the paper is accepted. The experiments are illustrative rather than central to the contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is that the paper has a believable and useful result, but one of the load-bearing bounds in the appendix is wrong as stated. The main contributions—Theorem 4.1's complete depth-width inclusions for diagonal linear SSMs, and Theorem 4.2's explicit construction showing that depth reduces the required norm exponentially—are genuinely new and fill a gap left by Smekal et al.'s single conversion example. The constructions are self-contained, and the small worked example for width 7 to two-layer width 4 checks out. If the norm-reduction theorem survives a fix, this is the clearest mechanism I know for why stacking helps in this architecture family.\n\nNow the soft spots, in rough order of seriousness.\n\nFirst, Lemma 8's bound |H_k| ≤ 2n max|Z_i| does not follow. The step from (58) to (59) drops a factor 2^{k−1}. Take β_1 = ... = β_{n−1} = 1, β_n = −1; then |H_n| = 2^{n−1} max|Z_i|, which exceeds 2n for n ≥ 5. The authors need to correct this. My own back-of-envelope says the theorem is probably repairable: replacing the false bound with the true |H_k| ≤ (n−k+1)2^{k−1} max|Z_i| still gives |H|/Z0^l ≤ Z0 in the construction of Lemma 9, because Z0 carries a factor that absorbs the exponential. But as it stands, the proof of Theorem 4.2 has a real gap.\n\nSecond, Lemma 5's proof is under-specified. The \"first-order asymptotic\" step is doing a lot of work, and the argument about degrees of polynomials is too terse. Since Lemma 5 is what gives tightness in Theorem 4.1, a referee should ask for a rigorous write-up.\n\nThird, reproducibility. The checklist says code and multiple seeds are included, but the text has no code link, no hyperparameters, and no error bars; Section B is thin. For a theory paper the experiments are illustrative, so this is a moderate issue, not a fatal one. Also, the prose in Theorem 4.3 about \"constant parameter count\" is loose: the width is set to ⌈K/l⌉+1, which changes with l.\n\nThe diagonal/normal restriction is real, and the authors acknowledge that the diagonalizable case is open (Section 4.4, Remark 3). That is a scope limitation, not a flaw.\n\nBottom line: this is a serious theory paper with a correct-looking main idea and a fixable proof defect. Send it to peer review, but make the authors fix Lemma 8 and tighten Lemma 5 before acceptance. I would cite it once the bound is cleaned up.","headline":"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.","tokens_in":21640,"tokens_out":7376,"would_cite":true,"duration_ms":73543,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["state-space models","deep linear networks","expressivity","depth versus width","norm constraints","convolutional kernels","diagonal state spaces","sequence modeling"],"falsifier":"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.","tokens_in":20633,"feed_emoji":"","tokens_out":10131,"duration_ms":96081,"temperature":0.7,"pith_summary":"The paper proves two complementary statements. Without norm constraints, an $l$-layer linear SSM of width $m$ is equivalent in expressive power to a one-layer model of width between $l(m-1)+1$ and $lm$, so depth and width can be traded under a fixed parameter budget. With norm constraints, the equivalence breaks: any one-layer model of width $l(m-1)+1$ with norm bound $c_1$ is exactly representable by an $l$-layer model of width $m$ whose weights are bounded by $2c_1^{2/(l+1)}$, so depth reduces the required norm exponentially. The paper also gives a logarithmic bound on the depth needed to fit a large-norm shallow model under a prescribed smaller norm, and demonstrates the construction numerically on linear and nonlinear SSMs.","feed_headline":"Depth shrinks required weights exponentially in linear SSMs","feed_subtitle":"A bounded-norm shallow state-space model can be rebuilt exactly at greater depth with far smaller weights.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the simplified S4D diagonal state-space layer that motivates the diagonal $A_i$ hypothesis space.","marker":"Smith et al., 2022"},{"why":"Supplies the HiPPO initialization with well-conditioned state matrices, invoked to justify the normal-matrix extension.","marker":"Gu et al., 2020"},{"why":"Documents the training instability caused by large recurrent norms, motivating the norm-constrained setting.","marker":"Pascanu et al., 2013"},{"why":"Provides a prior four-layer-to-one-layer conversion example that Theorem 4.1 generalizes.","marker":"Smekal et al., 2024"},{"why":"Shows diagonal SSMs are as effective as structured ones, supporting the diagonal assumption and the one-layer S4D baseline.","marker":"Gupta et al., 2022"},{"why":"Defines the linear functional impulse task used in the depth experiments.","marker":"Jordà, 2005"}],"fun_headline_variants":["Deep linear SSMs shrink weight norms exponentially","Bounded weights: depth beats width in linear SSMs","Depth compresses norm exponentially in constrained SSMs","More depth, less weight: linear SSM expressivity","Depth and width equivalent only unbounded in linear SSMs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Deep linear SSMs shrink weight norms exponentially","Bounded weights: depth beats width in linear SSMs","Depth compresses norm exponentially in constrained SSMs","More depth, less weight: linear SSM expressivity","Depth and width equivalent only unbounded in linear SSMs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000488,"raw_usage":{"total_tokens":2427,"prompt_tokens":995,"completion_tokens":1432,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":1356}},"tokens_in":611,"tokens_out":1432,"duration_ms":9946,"temperature":1.0,"reasoning_tokens":1356,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:35:37.722435+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"On the difficulty of training recurrent neural networks","cited_arxiv_id":null,"evidence_quote":"Documents the training instability caused by large recurrent norms, motivating the norm-constrained setting."},{"cited_title":"On the interplay between learning and memory in deep state space models","cited_arxiv_id":null,"evidence_quote":"Provides a prior four-layer-to-one-layer conversion example that Theorem 4.1 generalizes."}],"review_version":2}