acceptodds
Under review as a conference paper at ICLR 2027

Depth Separation for Learning Hierarchical Interactions with Nonlinear State-Space Models

Abstract

As sequence models emerge as efficient architectures for long-context modeling, it becomes important to understand the role of depth in recurrent architectures which combine recurrent memory with nonlinearity across layers. In this paper, we study the effect of depth through balanced-tree parity targets and show depth seperation phenomenon on Boolean input sequences. First, under norm constraints and bounded activation regularity, we obtain the lower bound of approximation error for deep nonlinear SSMs which means every constant-depth model cannot represent this target regardless of its hidden dimension or nonlinear width. Second, we obtain an upper bound for a logarithmic-depth SSM learned via a normalized layerwise coordinate-descent procedure when fitting this target from polynomially many noiseless samples, under the norm constraints assumptions and with constants independent of the sequence length. Third, we construct a depth-two nonlinear SSM that exactly represents a deep quadratic target, which cannot be represented by any constant-depth fully connected network of comparable size, demonstrating recurrent memory can substantially reduce the nonlinear depth needed for exact representation. These results characterize depth separation through the interplay among memory dimension, nonlinear width and network depth while extending the theoretical understanding of deep nonlinear recurrent architectures.

Primary area:
learning theory
Keywords:
Depth Seperation, Deep Networks, State-Space Models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_z687OpenReview ↗
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
  1. 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 nlog⁡2nn\log_2 n, 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.

  2. 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.

  3. 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.

  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. 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
  1. 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 nlog⁡2nn\log_2 n? 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.

  2. 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.

  3. 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.

  4. 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
AuthorsOpenReview ↗

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 nlog⁡2nn\log_2 n, 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=7K=7 and M=1M=1. Theorem 1 gives mean squared error at least 1/81/8 at any fixed depth for large enough nn, regardless of state size or width. Our Theorem 2 using the smooth construction in Appendix A.4 achieves arbitrarily small error at depth log⁡2n\log_2 n under those same bounds. Theorem 3 shows why the fixed norm bound matters: with K=2nK=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=1K=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), LL 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−1L-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 f2f_2 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 xx and width ∑S∣S∣=nq\sum_S|S|=nq. Its input matrix WW has rows 1S⊤\mathbf1_S^\top, repeated ∣S∣|S| times and its output weights are vS,j=aSwj(∣S∣)v_{S,j}=a_Sw_j^{(|S|)}. Using Eq. (66),it could fit the same K=2nK=2n, M=1M=1 budget used in Appendix A.3. Both constructions allow unrestricted biases. A norm budget fixed independently of nn 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=7K=7, M=1M=1. This correction does not affect that result.

AuthorsOpenReview ↗

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 L=log⁡2nL=\log_2 n, m=2n−1m=2n-1, and d=4n−2d=4n-2, satisfying A1–A4 with fixed K=7,M=1K=7,M=1, independent of nn. 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 nn, 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 LL in Eq. (1) counts stacked recurrent layers not time steps. The nonlinear stages are the inter-layer maps f2,…,fLf_2,\ldots,f_L and the readout gg. 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: f2f_2 uses tanh, while gg is the identity. Since A2=0A_2=0, moving f2f_2 into gg 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 q−1q-1 inter-layer nonlinear blocks plus one nonlinear readout, for q=log⁡2nq=\log_2 n stages. Its smooth form satisfies fixed norm bounds (A.4). The exact shallow construction uses one nonlinear block, O(n)O(n) state, O(nlog⁡n)O(n\log n) width and a growing norm budget K=2nK=2n. 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 Nn(q,7,1)\mathcal N_n(q,7,1). 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 Nn(q,7,1)\mathcal N_n(q,7,1) holds on every sampling outcome and only recovery and the error bound require the event of probability at least 1−δ1-\delta.

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.

  1. 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?

  2. 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.
Reviewer_AyfYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper considers a class of deep SSMs and a class of real-valued functions Fn\mathcal{F}_n defined on sequences of elements {1,−1}\{1,-1\} of length nn. The paper shows that 1) if one considers a class of deep SSMs of any depth and any state-space dimension, but with a certain boundedness condition on its parameters, then no element of Fn\mathcal{F}_n can be realized or approximated with arbitrary accuracy by an SSM of this class, 2) For every function FF from Fn\mathcal{F}_n, we can learn a deep SSM of length log⁡2(n)\log_2(n) from samples of FF which approximates FF with a certain accuracy, 3) every element of Fn\mathcal{F}_n can exactly be realized by a deep SSM of depth 22, 4) every continuous function defined on sequences of length n can be approximated by a deep SSM of depth 11.

Critical strengths

The strength of the paper is that it tries to get an insight to the expressiveness and modeling power of deep SSMs.

Critical weaknesses
  1. The paper is difficult to follow due to large number of undefined notions, which are not defined and for which the reader is not referred to the literature either. The presentation of the learning algorithm is incomplete: the construction of the SSM is not presented, one has to look for it in the appendix of the paper.

A few example:

  • lines 145-146: `signed dyadic version of the hierarchical Fourier targets studied in Ren et al. 2026': in the cited paper the expression ' hierarchical Fourier' does not occur, and at this stage it is not clear what is meant by signed dyadic version. w
  • 150: 'every level contributes the same amount to the squared L2(μn)L^2(\mu_n) norm: for such statements to make sense, you might want to explain that the elements of FnF_n are in L2(μn)L^2(\mu_n), the so called levels are the coordinates of FnF_n with respect to a certain orthogonal basis function in L2(μn)L^2(\mu_n), etc.
  • 227, Theorem 1: what is a 'dyadic horizon'
  • 254-257: you would have to recall what is a 'support at level r above the leaves', what is ' perfectly balanced binary tree'. As it stands, the definition in (9) is not clear. -- Description of the learning algorithm: - what are selected supports BiB_i, numbers br−1b_{r-1}, prp_r, Δi∈HTr,i\Delta_{i \in H} T_{r,i} (line 320). - how do we get the SSM of the final model for (11) ?

-- I am not sure why the results are significant. The minimal error of Theorem 1 stems from the uniform bound on the controllability matrix of Assumption A.1, and the bound on the sum in Assumption A.2. In fact, in terms of control theory, these assumptions ensure that the L2L_2 gain of each subsystem of the deep SSM is bounded by suitable constant CC, and hence so is the L2L_2 gain of the entire SSM and its input-output map. For the various non-linear notions of L2L_2 gain please see for instance the book by Khalil, Nonlinear Control, or the book by Sonta, Mathematical Control Theory. The L2L_2 gain of the input-output maps
from Fn\mathcal{F}_n are bigger than any constant CC for a suitably large nn. All what Theorem 1 seems to say is that one cannot approximate maps whose L2L_2 gain is larger by CC by input-output maps whose L2L_2 gain is smaller than CC. This is hardly surprising. The state-space size of the SSM learned in Theorem 2 is O(n), and the depth is log⁡2(n)\log_2(n). That is the model size is comparable to sequence size and hence it can memorize quite a bit. That is can learn specific, highly regular, functions such as the elements of Fn\mathcal{F}_n, is not surprising. The sample complexity is consistent with the standard PAC rate O(1/N)O(1/\sqrt{N}), which was shown in Racz et al. TML 2025 (in fact, the bound there did not depend on nn), so Theorem 2 is not very surprising either.

-- I think that the claim of the paper that it address the tradeoff between depth of the network and its size is somewhat overstated, as the hidden dimension in Theorem 2 is 2n-1, i.e., the same O(n) as in Theorem 3. Perhaps some of the results could be useful as technical building blocks for some future results, but as they stand, they do not seem to add much to the understanding of the role of depth.

Questions for authors
  • Why are the presented results useful ? In a way, the results do not show much of a tradeoff between depths and number of states (one should not forget the the overall complexity of a model of depth LL with state-space dimension mm is mLmL). In fact, from classical control theory it is known that in general a cascade interconnection of several state-space model is not a minimal realization of its input-output map, i.e., if LL models, each of which with mm states, is interconnected, then the resulting state-space model with mLmL hidden states will not be minimal: one can find a model with smaller than mLmL hidden states but which exactly reproduces the same input-output behavior.
    It is not clear then which complexity metric is used for the overall tradeoff.
3 comments
AuthorsOpenReview ↗

Rebuttal Part 1

Question 1: The paper is difficult to follow due to large number of undefined notions...

We thank the reviewer for identifying unclear terminology and we will revise the definitions in the revised version.

"dyadic horizon": A horizon is the number of input time steps, namely the sequence length nn. We mean n=2q,q∈Nn=2^q, q\in\mathbb N as the dyadic horizon and this restriction allows the target hierarchy to consist of qq levels of equal-sized binary merges. We shall replace the phrase with “sequence length n=2qn=2^q”.

"Support at level r above the leaves": Let TT be the tree in equation (9), whose n=2qn=2^q leaves are labeled bijectively by [n]={1,…,n}[n]=\{1,\ldots,n\}. For a node vv, we define its support by S(v):=i∈[n]:the leaf labeled i belongs to the subtree rooted at vS(v):=\\{i\in[n]: \text{the leaf labeled }i \text{ belongs to the subtree rooted at }v\\}. Thus, a support is a set of input indices. The associated parity feature is χS(v)(x)=∏i∈S(v)x(i)\chi_{S(v)}(x)=\prod_{i\in S(v)}x(i). A node vv is at level rr above the leaves if every leaf in its subtree is exactly rr edges below vv. For the perfect tree of height qq we considered, this is equivalent to $\operatorname{dist}_T(\mathrm{root},v)=q-r. $ We define $\mathcal T_r := \{S(v):v\text{ is at level }r\text{ above the leaves}\}, r=0,\ldots,q. $

"perfectly balanced binary tree”: We mean a rooted perfect binary tree of height qq: every internal node has exactly two children and every leaf has distance exactly qq from the root.

"Selected supports": After stage rr, the learner retains an ordered list $ \mathcal B_r=(B_{r,1},\ldots,B_{r,b_r}), B_{r,j}\subseteq[n]. $ Each support Br,jB_{r,j} indexes the unweighted parity $ \chi_{B_{r,j}}(x)=\prod_{i\in B_{r,j}}x(i). $ Initially, $ \mathcal B_0=(), b_0=0. $

br−1b_{r-1} and prp_r: For r≥2r\ge2, define $ J_{r-1} := \{H\in\mathcal H_{r-1}:w_H^{(r-1)}\ne0\}$, br−1:=∣Jr−1∣=∑H∈Hr−11wH(r−1)≠0b_{r-1}:=|J_{r-1}|=\sum_{H\in\mathcal H_{r-1}}1{\\{w_H^{(r-1)}\ne0\\}} where wH(r−1)w_H^{(r-1)} denotes the coefficient after thresholding at stage r−1r-1. Thus, br−1b_{r-1} counts the entries in the retained list Br−1=(SH(r−1):H∈Jr−1)\mathcal B_{r-1}=\bigl(S_H^{(r-1)}:H\in J_{r-1}\bigr) and $ p_r=n+b_{r-1}. $

The symbol at line 320 is △\triangle, denoting symmetric difference, i.e. A△B=(A∖B)∪(B∖A).A\triangle B=(A\setminus B)\cup(B\setminus A). An index HH selects at most two available features. Its candidate support is SH(r)=△i∈HTr,i=j∈[n]:∑i∈H1j∈Tr,i is odd.S_H^{(r)}=\triangle_{i\in H}T_{r,i}=\\{j\in[n]:\sum_{i\in H} 1{\\{j\in T_{r,i}\\}}\text{ is odd}\\}.

Question 2: The presentation of the learning algorithm is incomplete: the construction of the SSM is not presented, one has to look for it in the appendix of the paper...

We thank the reviewer for pointing out and we shall revise in the new version. For the explicit construction, Write (11) as F^(x)=∑S∈S^a^SχS(x)\widehat F(x)=\sum_{S\in\widehat{\mathcal S}}\widehat a_S\chi_S(x), where S^\widehat{\mathcal S} is the internal-support family of the recovered tree. We choose L=qL=q, m=2n−1m=2n-1, d=2md=2m and index the state coordinates by all tree nodes, with the leaves first. Initialize all states at zero and set A1=∑i=1n−1eiei+1⊤A_1=\sum_{i=1}^{n-1}e_i e_{i+1}^{\top} and B1=enB_1=e_n. This shift register gives h1(n)=(x(1),…,x(n),0,…,0)⊤h_1(n)=(x(1),\ldots,x(n),0,\ldots,0)^\top. Using the exact softplus multiplication and copying gates in Appendix A.4, we let Φr\Phi_r be a one-hidden-layer map of width 2m2m that computes each level-rr node from its two child coordinates and copies all remaining coordinates. The multiplication gate equals the product whenever its two inputs are Boolean. For ℓ=2,…,q\ell=2,\ldots,q, set Aℓ=0A_\ell=0, Bℓ=ImB_\ell=I_m, fℓ=Φℓ−1f_\ell=\Phi_{\ell-1} and g=Φqg=\Phi_q. Finally, choose CS=a^SC_S=\widehat a_S for internal nodes and CS=0C_S=0 for leaves. By induction over the tree levels, the coordinate indexed by SS in g(hq(n))g(h_q(n)) equals χS(x)\chi_S(x). Therefore, Yn(x)=C⊤g(hq(n))=∑S∈S^a^SχS(x)=F^(x),for every x∈{−1,+1}n.Y_n(x)=C^\top g(h_q(n))=\sum_{S\in\widehat{\mathcal S}}\widehat a_S\chi_S(x)=\widehat F(x),\text{for every }x\in\{-1,+1\}^n. Thus, (11) is realized exactly by a time-homogeneous SSM with L=qL=q, m=2n−1m=2n-1 and d=4n−2d=4n-2.

AuthorsOpenReview ↗

Rebuttal Part 2

Question 3: I am not sure why the results are significant....

We thank the reviewer for the comments. Our central contribution is a depth separation under fixed norm and smoothness constraints.

Theorem 1 controls beyond ordinary input--output gain and an ordinary gain bound alone does not imply Theorem 1. First, on the Boolean domain used in our theorem, the targets do not have growing incremental Euclidean gain. In fact, for every F∈FnF\in\mathcal F_n, $ \sup_{x,z\in\{-1,1\}^n, x\ne z} \frac{|F(x)-F(z)|}{|x-z|_2} \le \frac{6}{\sqrt{\log_2 n}}. $.

Thus, the proposed gain mismatch does not hold on our input domain. Appendix A.1 proves $ \sup_x \sum_{i=1}^{n} \bigl(Y_n(x^{(i)})-Y_n(x)\bigr)^2 \le R_0^2, $ where R0R_0 is independent of sequence length, state dimension and nonlinear width. An ordinary Euclidean Lipschitz bound with constant GG gives only 4nG24nG^2 for this quantity. The dimension-independent estimate requires matrix analysis and activation regularity and it bounds the model's high-degree Fourier mass, whereas the target places at least half its squared L2L^2 mass at degrees at least n\sqrt n. Thus, we establish a population approximation lower bound that does not follow from an ordinary gain comparison.

Our Theorem 1 allows arbitrary state dimension and nonlinear width, yet every constant-depth model has mean-squared error at least 1/81/8 for sufficiently large nn, under fixed norm and smoothness bounds. Theorem 2 shows that logarithmic depth succeeds under those same bounds. Thus, more memory alone does not remove the shallow-model limitation. Moreover, Theorem 2 covers the larger class Fntree\mathcal F_n^{\mathrm{tree}}, where both the tree and signs are unknown and our learner recovers the tree from polynomially many noiseless samples and returns an SSM with population L2L^2 error at most ε\varepsilon.

For the comparison with generic PAC rate, Rácz et al. give generalization and empirical risk minimization bounds for stable SSMs. However, their theoretical framework is totallly different from ours and they do not provide the explicit characterization of depth and the tree-recovery algorithm or establish the depth separation. Our contribution is the constructive learning guarantee paired with the lower bound.

In general, our results establish fixed-depth impossibility and logarithmic-depth sufficiency under common norm constraints, together with a shallow construction when those constraints are relaxed.

Question 4: In a way, the results do not show much of a tradeoff between depths and number of states...

Thank you for raising this point.

Theorem 1 allows arbitrary mm and dd. For sufficiently large nn, every constant-depth model in this class has mean squared error at least 1/81/8. This includes shallow models with the same total state count as our deep model, or even more states. Under the same bounds, Theorem 2 achieves any desired accuracy with L=log⁡2nL=\log_2 n, m,d=O(n)m,d=O(n) and polynomially many noiseless samples. Its total allocated state count is O(nlog⁡n)O(n\log n).

State reduction need not reduce nonlinear depth. Indeed, our construction’s higher-layer states can be removed, but their nonlinear composition remains in a deep readout. Thus, the readout falls outside the shallow architecture in equation 2. Our useful conclusion is that more memory alone cannot replace nonlinear depth under the stated bounds. Theorem 3 further shows why the norm condition matters: shallow models succeed when the norm budget grows.

I thank the authors for both responses. It is great that they are willing to add the missing explanation, but in general the paper remains written in a style with unclear (or at least not widely known) terminology. In fact, the response to my question still suffers the same problem, e.g.,n it would have been useful to define what the authors mean by depth separation. I think I now understand better what the authors mean, but I still wonder how useful it is, and how much depth separation it shows: Theorem 1 shows that for long enough sequences a fixed depth and with is insufficient, Theorem 2 shows that for long enough inputs a certain depth is sufficient. In fact, n > 4R_0^4 and R0=O(K3L)R_0=O(K^{3^L}) implies that n>4R04n > 4R_0^4 implies that q=ln⁡(n)>O(3L)>>Lq=\ln(n) > O(3^L)>> L, while in Theorem 2 shows that depth L=q=O(ln n) and with d=O(n)d=O(n) which grow with n are sufficient. However, the amount of memory is determined by the hidden state dimension m and the depth L by construction, and in both theorems the state-dimension is the same. That is, the memory used in Theorem 1 seems to be smaller than the memory used in Theorem 2. The non-linear width d does not play the rule of number of neurons, the size m of the state-space does. The latter is the same in both Theorem 1 and Theorem 2.

In addition, my biggest concern is the presentation which makes the paper very difficult to evaluate. For these reasons I maintain my score.

Reviewer_mqLKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates whether temporal accumulation in linear-recurrent state-space models (SSMs) can compensate for limited nonlinear depth when representing hierarchical interactions. The authors use a balanced-tree parity target, to establish a constant-depth approximation lower bound under a uniform gain budget, independent of state dimension and width. Then they complement this result with a layerwise algorithm that recovers the interaction structure and constructs a logarithmic-depth SSM, and show that shallow models can represent the same target when the norm budget is relaxed. Together, these results characterize an important trade-off between nonlinear depth and gain constraints.

Critical strengths
  1. The authors show that the lower bound is independent of both width and state dimension, which is meaningful for understanding the distinction between memory capacity and nonlinear compositional depth.

  2. The balanced-tree target has a well-motivated structure: interactions at different levels contribute equal squared energy, preventing higher-order interactions from becoming negligible.

Critical weaknesses
  1. The claimed separation from constant-depth feedforward networks is not sufficiently justified. The shallow SSM construction appears to admit an equivalent feedforward realization by absorbing its linear encoding into the first-layer weights, preserving nonlinear depth and hidden width, though not necessarily parameter count or norm bounds. The paper should specify the exact architecture, size measure, and norm constraints supporting this comparison, or weaken the claim accordingly.

  2. The depth separation remains incomplete. The lower bound rules out any fixed depth asymptotically, while the upper bound establishes that logarithmic depth is sufficient, but not necessary. Moreover, the constants in the lower bound lead to extremely large sequence-length thresholds even for shallow models, limiting its quantitative implications. The paper should distinguish more clearly between the established constant-depth separation and the unresolved optimal depth requirement.

Questions for authors
  1. What is the strongest necessary depth scaling as a function of sequence length (n) that can be derived from the current lower-bound recursion? What is the main obstacle to closing the gap between this bound and the logarithmic-depth construction?

  2. Which parts of the learning guarantee would fail if only the root parity, rather than all intermediate interactions, appeared in the label? Can the analysis extend to more general hierarchical targets under suitable minimum-coefficient or noise assumptions?

2 comments
AuthorsOpenReview ↗

Rebuttal Part 1

Question 1: The claimed separation from constant-depth feedforward networks is not sufficiently justified...

We agree that the linear encoding can be absorbed into the first feedforward layer. We could construct a feedforward network with one tanh hidden layer of width d=nlog⁡2nd=n\log_2 n. However, our main depth separation remains unchanged. It concerns the SSM class in Eqs. (1)–(2), with state dimension mm and nonlinear width dd as distinct size measures. Under A1–A4 with the same fixed bounds K=7K=7 and M=1M=1, our Theorem 1 gives mean squared error at least 1/81/8 at any fixed depth for sufficiently large nn, regardless of mm or dd. Our Theorem 2 which uses the smooth construction in Appendix A.4, achieves arbitrary accuracy with L=log⁡2nL=\log_2 n, m=2n−1m=2n-1 and d=4n−2d=4n-2. Our Theorem 3 shows why the fixed norm bounds matter: its exact shallow construction uses K=2nK=2n. We shall revise our paper to state this scope. The depth separation and learning guarantees within the fixed-norm SSM class are unchanged.

Question 2: The depth separation remains incomplete. The lower bound rules out any fixed depth asymptotically...

The claimed depth separation is established. Under fixed norm and smoothness bounds, Theorem 1 gives a mean squared error of at least 1/81/8 for every fixed depth at large enough sequence lengths, even with arbitrary state size and width. Theorem 2 learns the same targets at logarithmic depth under the same bounds. Thus, more memory or width cannot replace depth in this setting. We do not claim that logarithmic depth is necessary. The least depth needed remains open, as Section 5 and Appendix A.4 already state. We agree that the threshold n≥4R04n\geq 4R_0^4 can be very large, which limits the bound’s use at practical sequence lengths. This is a sufficient threshold from the proof, not a sharp estimate of where shallow models first fail. The large constants do not change the proved asymptotic separation.

Question 3: What is the strongest necessary depth scaling as a function of sequence length (n) that can be derived from the current lower-bound recursion? What is the main obstacle to closing the gap between this bound and the logarithmic-depth construction?

For fixed K,MK,M, the strongest necessary depth scaling from our current recursion is L=Ω(log⁡log⁡n)L=\Omega(\log\log n). The main obstacle is the quadratic term in the bound on input-flip sensitivity (Appendix A.1, Eq. (18)). This bound can square at each layer, which causes double-exponential growth with depth. The proof controls total degree-weighted Fourier energy, but does not track how high-degree terms form across layers. Better constants cannot close this gap and a sharper bound on that growth is needed. Our construction builds the tree through pairwise products, but general admissible SSMs need not follow that rule. Thus, logarithmic depth is sufficient, while its necessity remains open.

Question 4: Which parts of the learning guarantee would fail if only the root parity, rather than all intermediate interactions, appeared in the label?...

The intermediate terms are essential to tree recovery. With only root parity in the label and n>2n>2, every first-stage candidate has zero population correlation with the label. Thus, thresholding has no signal and the recovery induction in Appendix A.2 cannot start. The stated learner loses both its tree-recovery and prediction guarantees. More samples cannot restore this missing signal. Moreover, all trees give the same root parity, so the hidden tree cannot be identified from that label. The logarithmic-depth SSM representation still holds (Appendix A.4). Root parity on the known support [n][n] can still be computed directly.

We think the fixed coefficient values can be relaxed. On the same tree class under uniform Boolean inputs, the proof extends to ∣a∣2≤1|a|_2\le1 and ∣aS∣≥κ>0|a_S|\ge\kappa>0 at every internal node. For noisy labels y=F(X)+ξy=F(X)+\xi, a sufficient condition is E[ξ∣X]=0\mathbb E[\xi\mid X]=0 with bounded or conditional sub-Gaussian noise. Polynomial sample size still requires 1/κ1/\kappa and the noise scale to be polynomially bounded. Broader hierarchies also need each required feature to be built from earlier recovered features, a clear gap in residual correlations and gates that meet the SSM norm bounds. A minimum coefficient alone is not enough. These are extensions of the proof and we may leave these extensions as our future work.

Reviewer_mqLKOpenReview ↗

Response to Rebuttal

Thank you for the detailed responses, which have addressed much of my concerns. I still have some reservations regarding the practical significance and generalizability of the findings, so I have decided to maintain my original score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.