- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies hierarchical Boolean interaction targets under the uniform input distribution using stacked nonlinear state-space models. Under horizon-independent norm bounds and smooth activation assumptions, it proves a constant-depth approximation lower bound that is independent of hidden dimension and nonlinearity width. It also gives a polynomial-sample learner for an unknown balanced interaction tree and compiles the learned predictor into a logarithmic-depth SSM. A separate construction gives exact depth-two tanh representation when the norm budget grows with the input length. The validation consists of theoretical arguments and constructive proofs, including a smooth realization in Appendix A.4. The paper does not report empirical experiments.
Critical strengths
-
Recurrent lower bound. The recurrent sensitivity argument extends the hierarchical Fourier approach to SSMs and gives a lower bound that does not rely on limiting the hidden dimension or nonlinearity width. This is a meaningful theoretical extension beyond the feedforward setting.
-
Constructive learning guarantee. The upper bound includes both recovery of an unknown interaction tree and a constructive SSM realization. Appendix A.4 supplies a smooth activation construction with uniform norm bounds, making the comparison with the lower bound more informative than a representation result alone.
Critical weaknesses
-
Unmatched feedforward comparison. The advertised advantage over comparable-size constant-depth fully connected networks is not established by Theorem 3. Equations (62) and (67) express each parity as shifted tanh functions of a subset sum. Applying these directly to the input vector gives a single-hidden-layer feedforward network of width , the same nonlinear width as Equation (68). Both this construction and Theorem 3 permit growing norms. Theorem 1 is an SSM lower bound under horizon-independent norm and regularity budgets, not a feedforward lower bound. It therefore does not exclude this direct feedforward realization, which also uses a growing norm budget. Additional restrictions on norms, input access, or parameter count must be stated for the architectural comparison to be meaningful.
-
Limited additional learning significance. The paper acknowledges that its target family and layerwise learner build on Ren et al. (2026). In the smooth SSM realization in Appendix A.4, the first layer stores the sequence and all higher recurrent transition matrices are zero, so the hierarchy is evaluated through inter-layer maps at the terminal time. The learner first recovers explicit parity features and then compiles the predictor into an SSM, rather than learning recurrent parameters directly. This is a valid constructive guarantee, and the recurrent lower bound is a meaningful contribution. However, the learning result itself leaves limited evidence for a further benefit from recurrent dynamics beyond input storage, weakening the significance of the additional algorithmic contribution.
-
Depth accounting needs a clearer interpretation. Appendix A.3 explicitly observes that the nonlinear map in the depth-two construction can be moved into the permitted nonlinear readout, yielding a depth-one recurrent realization with growing norms. Thus Theorem 3 establishes a sufficient construction, rather than a need for two recurrent layers, and the parameter L does not by itself count all nonlinear processing. This qualification is important to the paper's interpretation in terms of recurrent memory reducing nonlinear depth. The introduction and discussion should distinguish recurrent-layer depth, inter-layer nonlinear computation, and readout complexity. This is an interpretive limitation, not a contradiction of Theorem 1.
-
The proof presentation does not consistently identify the smooth upper bound. The model class defined in Section 4.1 imposes Assumptions A1–A4, including activation smoothness. Theorem 2 in the main text asserts membership in that class and points to Appendix A.2. However, the purpose paragraph of Appendix A.4 says that the main-text theorem explicitly specifies ReLU, while the actual main-text statement already returns a model in that smooth class and its failure branch uses softplus. Appendix A.4 supplies the required softplus realization with K = 7 and M = 1, so I am not claiming that the smooth upper bound is absent. The inconsistent description and proof pointer nevertheless make it unnecessarily difficult to verify that the upper and lower bounds use the same assumptions. This is a fixable presentation concern, secondary to the comparison and significance issues above.
Questions for authors
-
Matched feedforward constraints. Which precise resource constraints exclude applying the tanh interpolation in Equations (62) and (67) directly to the input vector in a feedforward network of width ? Please state the comparison with matched norm budgets and input access, or revise the advertised feedforward separation. The answer affects the validity of the memory-advantage claim.
-
Additional learning guarantee. Relative to the cited target family and learner of Ren et al. (2026), which additional guarantee in Theorem 2 depends on recurrent computation beyond storing the input and compiling the learned hierarchy? Please distinguish the new recurrent lower-bound analysis from the new content in the learning upper bound. This affects my assessment of significance.
-
Depth convention and readout. How should the depth-reduction claim be interpreted given Appendix A.3's depth-one realization obtained by moving the nonlinear map into the readout? Please clarify what nonlinear operations are counted in each architectural comparison and which resource is being reduced. I am asking about the interpretation of the existing result, not requesting a new minimal-depth theorem.
-
Consistent smooth-theorem statement. Does the stated output of Theorem 2 rely on the softplus construction in Appendix A.4 in addition to Appendix A.2? Please reconcile A.4's claim that the main theorem specifies ReLU with the actual main-text statement and give the explicit proof dependency establishing K = 7 and M = 1 on every sampling outcome. This would resolve the assumption-matching concern.
5 comments
Rebuttal Part 2
Question 6: Additional learning guarantee. Relative to the cited target family and learner of Ren et al. (2026)...
Theorem 2 does not add a learning guarantee that requires recurrence beyond input storage and compilation. The contributions are as follows. Firstly, we build on Ren et al.’s layerwise learner. Our variant passes unweighted parity features between stages, giving one exact update per coordinate and the stated sample bound. This change does not rely on recurrence. The added SSM guarantee is an exact softplus realization of the learned predictor with , , and , satisfying A1–A4 with fixed , independent of . Thus, the learner returns a model under the same norm and smoothness limits as the lower bound. Secondly, the new recurrent analysis lies in Theorem 1. It carries the sensitivity bound through recurrent sums and proves a constant error floor for every fixed-depth SSM under A1–A4, for large enough , regardless of state size or nonlinear width. This covers models that use recurrence in all layers. Thirdly, the significance is a depth separation within this constrained SSM class: fixed depth fails, while a learned logarithmic-depth model succeeds. The lower bound covers the full recurrent class and the upper bound supplies a learned model within that class. This separation does not require a new learning gain from recurrence.
Question 7: Depth convention and readout. How should the depth-reduction claim be interpreted...
Depth in Eq. (1) counts stacked recurrent layers not time steps. The nonlinear stages are the inter-layer maps and the readout . Linear state updates and the final linear sum add no nonlinear stage. The lower-bound proof explicitly includes the readout, whose norms and activation are subject to A3–A4. Theorem 3 has two recurrent layers but only one nonlinear block: uses tanh, while is the identity. Since , moving into gives the same output with one recurrent layer, as stated in A.3. This removes a state layer and it leaves the nonlinear work unchanged.
The resource tradeoff is precise. The logarithmic construction uses inter-layer nonlinear blocks plus one nonlinear readout, for stages. Its smooth form satisfies fixed norm bounds (A.4). The exact shallow construction uses one nonlinear block, state, width and a growing norm budget . Thus, fewer stacked stages are achieved with larger width and norms. Moving the map into the readout does not bypass the fixed-norm lower bound.
For Proposition 4, one layer means one recurrent layer and both the input and output nonlinear blocks must be counted. For the feedforward comparison, A.3’s terminal map is itself a shallow tanh network on a linear encoding of the input. We shall revise the broad depth-reduction wording to state these counts and budgets explicitly.
Question 8: Consistent smooth-theorem statement. Does the stated output of Theorem 2 rely on the softplus construction in Appendix A.4 in addition to Appendix A.2?...
Yes. Theorem 2 relies on both A.2 and A.4. Our main text already states that the output lies in . A.4’s claim that the main theorem specifies ReLU is an editing error and we shall fix in the revised version.
The proof dependency is as follows: A.2 in Steps 1–6 proves the recovery, error and sample bounds, A.2 in Step 8 verifies the output and A.4 in Steps 1–6 gives the exact softplus realization with the stated depth and dimensions. On every outcome that passes the checks, the selected supports form a valid balanced tree. If any check fails, the learner returns the zero softplus SSM with the same dimensions. Hence membership in holds on every sampling outcome and only recovery and the error bound require the event of probability at least .
Thank you for the detailed response. Your clarifications address my questions about proof dependencies, depth accounting, and the scope of Theorem 3. I also appreciate your commitment to removing the unsupported feedforward comparison.
Before finalizing my assessment, I would appreciate clarification of two points concerning novelty and significance.
-
Technical advance over [1]. Beyond the local Taylor estimate inherited from [1], which additional proof step establishes horizon-independent control through the recurrent sums? Why does the existing feedforward result not apply directly after unrolling, and what additional analysis is needed under A1–A4?
-
Insight relative to SSM theory. Accounting for the different settings of [2] and [3], what additional insight does the fixed-budget separation provide about memory versus nonlinear depth? How is that insight limited by time-homogeneous, input-independent transitions?
A concise comparison would help me assess the remaining contribution. No additional experiments are requested.
References
- [1] Yunwei Ren, Zihao Wang, and Jason D. Lee. Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks. arXiv:2607.25200, 2026.
- [2] Shida Wang and Beichen Xue. State-space Models with Layer-wise Nonlinearity are Universal Approximators with Exponential Decaying Memory. NeurIPS, 2023.
- [3] William Merrill, Jackson Petty, and Ashish Sabharwal. The Illusion of State in State-Space Models. ICML, 2024.
Rebuttal Part 1
Question 1: Unmatched feedforward comparison. The advertised advantage over comparable-size constant-depth fully connected networks is not...
Thanks for your comments. We agree that Eqs. (62) and (67) also give a one-hidden-layer tanh network of width nlog2n, matching Eq. (68). Theorem 3 does not prove an advantage over feedforward networks of comparable size. We will remove that claim from the abstract and introduction. Our depth separation holds within the SSM class under the same fixed bounds K=7 and M=1. Theorem 1 gives mean squared error at least 1/8 at any fixed depth for large enough n, regardless of state size or width. Our Theorem 2 using the smooth construction in Appendix A.4 achieves arbitrarily small error at depth log2n under those same bounds. Theorem 3 shows why the fixed norm bound matters: with K=2n, an exact shallow SSM exists. The direct feedforward construction is valid, but it does not affect this fixed-bound SSM depth separation.
Question 2: Limited additional learning significance. The paper acknowledges that its target family and layerwise learner build on Ren et al. (2026)...
We build on Ren et al.’s learning strategy, as stated in §4.3. Our added result is efficient learning under the same norm and smoothness bounds as the recurrent lower bound. Theorem 2 recovers an unknown tree from polynomially many noiseless samples. Appendix A.4 then realizes the learned predictor exactly as a smooth SSM with logarithmic depth, linear state size and width, and fixed bounds K=7,M=1. Under these same bounds, Theorem 1 rules out every fixed-depth SSM for sufficiently long sequences, even with arbitrary state size, width, and admissible recurrent dynamics. Setting higher transitions to zero in our construction does not weaken this separation: the lower bound still covers all allowed recurrent transitions. The learning result thus supplies an efficient learner for targets that every fixed-depth SSM in this class fails to approximate.
Question 3: Depth accounting needs a clearer interpretation. Appendix A.3 explicitly observes that the nonlinear map in the depth-two construction...
The readout is already included in our depth analysis. In Eqs. (1)–(2), L counts recurrent layers, while each inter-layer map and the readout has one hidden layer. A3 bounds the readout norms, and Appendix A.1 explicitly counts L−1 inter-layer maps plus the readout in the proof of Theorem 1. Our Theorem 3 proves that two recurrent layers suffice; it does not claim they are needed. Appendix A.3 states this explicitly. Moving f2 into the readout gives one recurrent layer, but retains the same nonlinear map and its growing norm cost. The result shows that growing norms permit exact shallow representation. We agree that this scope should be clear in the main text. We will revise in the new version.
Question 4: The proof presentation does not consistently identify the smooth upper bound. The model class defined in Section 4.1 imposes Assumptions A1–A4, including activation smoothness. Theorem 2 in the main text asserts membership in that class and points to Appendix A.2...
We agree that the wording and proof pointer need correction. We shall revise in the new version.
Question 5: Matched feedforward constraints. Which precise resource constraints exclude...
No stated constraint excludes this feedforward construction when norm budgets and input access are matched. We will revise the claim. In fact, we could contruct an exact feedforward network with one tanh hidden layer, full access to x and width ∑S∣S∣=nq. Its input matrix W has rows 1S⊤, repeated ∣S∣ times and its output weights are vS,j=aSwj(∣S∣). Using Eq. (66),it could fit the same K=2n, M=1 budget used in Appendix A.3. Both constructions allow unrestricted biases. A norm budget fixed independently of n excludes this particular interpolation in both models.
Theorem 3 establishes exact shallow SSM representation with growing norms. Our depth separation concerns SSMs under the same fixed bounds: Theorem 1 gives the constant-depth lower bound, while Theorem 2, with the smooth construction in Appendix A.4, gives the logarithmic-depth upper bound at K=7, M=1. This correction does not affect that result.