Summary (Overview)

  • This paper provides the first theoretical analysis of how layer ordering in hybrid architectures (combining Transformer and State-Space Model layers) affects task performance, showing that the optimal hybrid architecture is highly task-specific.
  • The authors prove Theorem 1: for any layer configuration, there exists a task where a model with that configuration provably outperforms any other configuration under fixed resource constraints (state size, precision, window width).
  • They identify natural tasks (Exact Copy, Segmented Retrieval, Tensor Lookup) where specific architectures (TS and TST) are theoretically dominant, and empirically confirm these separations with trained Transformer-Mamba hybrids.
  • Under fixed memory budgets, the theoretically-predicted optimal architecture for Segmented Retrieval achieves perfect accuracy, while the next strongest architecture plateaus below 0.5.
  • For deeper models (4-8 layers), the paper shows that "containing" the dominant sub-architecture (TS or TST) predicts high performance, and provides mechanistic insights via linear probing showing Transformer layers contribute the largest share of associative recall performance.

Introduction and Theoretical Foundation

Background and Motivation

Hybrid architectures—combining full self-attention (Transformer) layers with subquadratic alternatives (SSMs like Mamba, linear attention, Gated DeltaNet)—have become the design of choice for frontier models due to their superior scalability compared to vanilla Transformers on long-context tasks.

However, the expanded design space introduces critical challenges:

  • Layer selection and ordering is combinatorially large
  • Each layer type has different constraints: full-attention is memory-bound by retrieval distance; recurrent alternatives are bound by state size
  • A complete empirical sweep across architectures is intractable due to training costs

Layer Abstractions

The paper abstracts layers into two types:

Transformer Layer (T-layer) with window size WW: A layer FF is a T-layer if there exists a map ff such that for i∈[L]i \in [L]:

F(x⃗)i=f(xi−W+1,…,xi)∈{0,1}PF(\vec{x})_i = f(x_{i-W+1}, \ldots, x_i) \in \{0,1\}^P

State-Space Model Layer (S-layer) with bit complexity BB: A layer FF is an S-layer if there exists a finite state set S\mathcal{S} of size at most 2B2^B, an update rule u:S×{0,1}P→Su: \mathcal{S} \times \{0,1\}^P \to \mathcal{S}, and output function r:S→{0,1}Pr: \mathcal{S} \to \{0,1\}^P such that:

St=u(St−1,x⃗t),F(x⃗)t=r(St)S_t = u(S_{t-1}, \vec{x}_t), \quad F(\vec{x})_t = r(S_t)

Key insight: Transformers perfectly recall their recent context (window), while SSMs store a compressed version of the entire context (state).

Architecture Profiles

An architecture profile A=A1A2⋯AD∈{S,T}∗A = A_1 A_2 \cdots A_D \in \{\mathrm{S}, \mathrm{T}\}^* is a word over the alphabet of layer types. The compression of AA, denoted comp(A)\text{comp}(A), merges consecutive identical layers. For example, comp(TTSSS)=TS\text{comp}(\text{TTSSS}) = \text{TS}.

The model class MA(B,P,W)\mathcal{M}_A(B, P, W) contains all hybrid models with profile AA, where every S-layer has state size at most 2B2^B, every T-layer has window size at most WW, and intermediate tokens have precision at most PP.


Methodology

Main Theoretical Result (Theorem 1)

Theorem 1: Let D∈N+D \in \mathbb{N}_+ and τ=X1r1X2r2⋯Xhrh∈Σ∗\tau = X_1^{r_1} X_2^{r_2} \cdots X_h^{r_h} \in \Sigma^* be an arbitrary architecture profile with depth DD. Let α:=comp(τ)\alpha := \text{comp}(\tau) and ϵ∈(0,1)\epsilon \in (0,1) be an arbitrary fixed constant. There exist constants cτ>0c_\tau > 0, Cτ,ϵ>0C_{\tau,\epsilon} > 0, a family of tasks {Fτ,ϵ,m}m≥1\{F_{\tau,\epsilon,m}\}_{m \geq 1}, and a family of distributions μm\mu_m such that for all mm sufficiently large:

  1. (Completeness): There exists a model Mτ,m∈Mτ(Bτ,m,Pτ,m,Wτ,m)M_{\tau,m} \in \mathcal{M}_\tau(B_{\tau,m}, P_{\tau,m}, W_{\tau,m}) with errμm(Mτ,m,Fτ,ϵ,m)=0\text{err}_{\mu_m}(M_{\tau,m}, F_{\tau,\epsilon,m}) = 0 and Bτ,m≤Cτ,ϵlog⁡mB_{\tau,m} \leq C_{\tau,\epsilon} \log m, Pτ,m≤Cτ,ϵlog⁡mP_{\tau,m} \leq C_{\tau,\epsilon} \log m, Wτ,m≤m+1W_{\tau,m} \leq m+1.

  2. (Soundness for wrong ordering): For any architecture AA with α⪯̸A\alpha \not\preceq A, every model M∈MA(B,P,W)M \in \mathcal{M}_A(B, P, W) achieving error ≤O(1/D)\leq O(1/D) must satisfy W≥cτm1/ϵW \geq c_\tau m^{1/\epsilon} or max⁡{B,P}≥cτm\max\{B, P\} \geq c_\tau m.

  3. (Soundness for insufficient profile): For any architecture AA with α⪯A\alpha \preceq A but τ⪯̸A\tau \not\preceq A, achieving error ≤O(1/D)\leq O(1/D) requires W>λτ(m+1)W > \lambda_\tau(m+1), B>λτBτ,mB > \lambda_\tau B_{\tau,m}, or P>λτPτ,mP > \lambda_\tau P_{\tau,m}, where λτ>1\lambda_\tau > 1 is a constant.

Key Task Construction: Sequential Function Composition

The separating task is defined as:

Definition 1 (Sequential Function Composition): A level-kk recursive chain Fτ,ϵ,mF_{\tau,\epsilon,m} is defined by kk functions {Hi}i=1k\{H_i\}_{i=1}^k where Hi(zi−1,xi):Xkey×Cm→XkeyH_i(z_{i-1}, x_i): \mathcal{X}_{key} \times \mathcal{C}^m \to \mathcal{X}_{key}, with zi:=Hi(zi−1,xi)z_i := H_i(z_{i-1}, x_i). Given input I:=(z0,0⃗0,x1,0⃗1,…,xk,0⃗k)I := (z_0, \vec{0}_0, x_1, \vec{0}_1, \ldots, x_k, \vec{0}_k), the task outputs Fτ,ϵ,m(I):=zkF_{\tau,\epsilon,m}(I) := z_k.

The task is divided into kk stages; each stage takes a previous answer zi−1z_{i-1} and fresh context xix_i to produce the next answer. The zero vectors (0⃗i\vec{0}_i) prevent T-layers from directly accessing information from previous blocks.

Size-2 Cover Method

For analyzing profiles where comp(τ)⪯A\text{comp}(\tau) \preceq A but τ⪯̸A\tau \not\preceq A, the authors introduce the size-2 cover:

C2(τ)={Ss(τ)}∪{Tt(τ)}∪{SiTri(τ)∣i∈[s(τ)]}∪{TiSli(τ)∣i∈[t(τ)]}\mathcal{C}_2(\tau) = \{\mathrm{S}^{s(\tau)}\} \cup \{\mathrm{T}^{t(\tau)}\} \cup \{\mathrm{S}^i \mathrm{T}^{r_i(\tau)} \mid i \in [s(\tau)]\} \cup \{\mathrm{T}^i \mathrm{S}^{l_i(\tau)} \mid i \in [t(\tau)]\}

where s(τ)s(\tau) is the number of S-layers, t(τ)t(\tau) the number of T-layers, ri(τ)r_i(\tau) the number of T-layers after the ii-th S-layer, and li(τ)l_i(\tau) the number of S-layers after the ii-th T-layer. If τ⪯̸A\tau \not\preceq A and A∈Σ≤DA \in \Sigma^{\leq D}, then some profile in C2(τ)\mathcal{C}_2(\tau) is not subsumed by AA.

Natural Task Lower Bound (Theorem 2)

Theorem 2 (SSM → TF Cut): Let FF be a length-LL sequence task with output in Y\mathcal{Y}. Suppose there exist a cut position τ\tau, a nonempty family U\mathcal{U} of length-τ\tau prefixes, and a nonempty family Q\mathcal{Q} of length-(L−τ)(L-\tau) suffixes, such that every concatenation uquq is a legal input and ∀u≠u′∈U\forall u \neq u' \in \mathcal{U}, ∃q∈Q\exists q \in \mathcal{Q} such that F(uq)≠F(u′q)F(uq) \neq F(u'q). Let MM be a deterministic model of architecture ST with recurrent state space SS and attention window WW. If MM computes FF correctly on all legal inputs and τ≤L−W\tau \leq L - W, then ∣S∣≥∣U∣|S| \geq |\mathcal{U}|.

Natural Tasks for TS Dominance

Definition 3 (Exact Copy): Given input x∈VL\mathbf{x} \in \mathcal{V}^L, output yLy_L where yi:=1{x1:i has an exact copy}y_i := \mathbf{1}\{\mathbf{x}_{1:i} \text{ has an exact copy}\}. The sequence contains an exact copy if there exists i∈[L]i \in [L] such that:

xi+j+kl=xi+j+(k+1)l,j∈{0,…,l−1},k∈{0,…,c−2}\mathbf{x}_{i+j+kl} = \mathbf{x}_{i+j+(k+1)l}, \quad j \in \{0, \ldots, l-1\}, k \in \{0, \ldots, c-2\}

Definition 4 (Segmented Retrieval): Given input ((x1,b1),…,(xL,bL))∈(V×{0,1})L((x_1, b_1), \ldots, (x_L, b_L)) \in (\mathcal{V} \times \{0,1\})^L where bib_i indicates segment boundaries, select 1≤λ<l1 \leq \lambda < l (where ll is the minimum segment length), and output the token xtλ⋆−λx_{t_{\lambda^\star} - \lambda} where λ⋆\lambda^\star is the largest index such that xtj−λ∈Nx_{t_j - \lambda} \in \mathcal{N} (a specified subset of the vocabulary).


Empirical Validation / Results

Experimental Setup

  • Tasks: Segmented Retrieval, Exact Copy (2-layer), Tensor Lookup (3-layer, TST-dominant), (2,1)-Associative Recall (8-layer)
  • Models: Transformer layers with RoPE embeddings; Mamba for SSM layers
  • Memory constraint: Fixed proxy of inference memory, creating trade-offs between token embedding dimension, window length, and state size
  • Sequence lengths: ~150 tokens; Vocabulary: ~20 tokens

Two-Layer Results

Results for both tasks are shown in Figure 2. Key findings:

  • Only the TS architecture achieves high accuracy (perfect in one setting)
  • ST architectures never achieve high performance—their ability to capture complex operations early in the sequence is hindered
  • The memory constraint creates a trade-off: larger token dimension reduces window/state size, while smaller token dimension limits expressivity

Four-Layer Results (Segmented Retrieval)

Table 1: Training 4-layer hybrids on segmented retrieval

ModelAccuracyModelAccuracy
TTTT0.871TSSS1.000
STTT0.706STSS1.000
SSTT0.516SSTS1.000
SSST0.345TTSS1.000
SSSS0.125TSTS1.000
TSST1.000
STTS1.000
STST1.000
TSTT1.000
TTST1.000
TTTS1.000

Clear dichotomy: All architectures containing TS as a sub-architecture achieve perfect performance; all architectures without TS fail to achieve perfect performance on any seed.

Five-Layer Results (Tensor Lookup / TST Task)

Models with TST as a sub-architecture perform notably higher than those without (Figure 3), aside from the STSTS architecture.

Eight-Layer Associative Recall Results

  • Hybrid models outperform pure architectures (Figure 4)
  • The T∗S∗\mathrm{T}^*\mathrm{S}^* architecture outperforms the S∗T∗\mathrm{S}^*\mathrm{T}^* architecture
  • Each architecture family peaks at a different TF-to-SSM ratio
  • Models with Transformers in the first few layers benefit most from having very few Transformer layers

Linear Probing Mechanistic Analysis

Linear probe results (Figure 5) show:

  • The first TF layer consistently improves decodability significantly (retrieves key-value pairs within its context window)
  • Models with long strings of SSM layers (e.g., TTSSSSSS) show slow increases in decodability across SSM layers, suggesting these layers bring key-value pairs from outside the context window
  • TTTSSSSS and STSTSTST show little increase at S-layers, supporting the claim that hybrid design is nuanced—slightly different architectures fail to use their SSM layers effectively

Theoretical and Practical Implications

Theoretical Implications

  1. Task-specificity of architecture design: The paper establishes that there is no universally optimal hybrid architecture—the optimal layer ordering depends fundamentally on the task structure. This is formalized through resource-separation results showing that wrong orderings require exponentially larger state spaces/precisions or polynomially larger windows.

  2. Information processing perspective: The results highlight that each layer type serves a distinct computational role: T-layers excel at local computation and information rearrangement, while S-layers efficiently propagate compressed information across long distances. The optimal ordering depends on which operations the task requires and in what sequence.

  3. Characterization of expressivity-efficiency tradeoffs: The size-2 cover method provides a tractable way to analyze the space of possible architectures, showing that only maximal profiles with compressed length at most 2 need to be considered for hardness results.

Practical Implications

  1. Design guidance for frontier models: The finding that containing the dominant sub-architecture (TS or TST) predicts performance in deeper models provides a practical heuristic: identify the critical information-processing motif for your task and ensure it appears as a sub-architecture.

  2. Memory budget allocation: The empirical results demonstrate that under fixed memory constraints, architecture choices (not just total capacity) determine whether tasks can be solved at all—highlighting the importance of architectural design alongside scaling.

  3. Mechanistic understanding: The linear probing results provide insight into how hybrid models actually solve tasks, suggesting that Transformer layers perform the majority of associative recall—consistent with observations in natural language models.

  4. Task-driven architecture search: The theoretical framework offers a path toward predicting effective layer orderings before expensive training, potentially reducing the combinatorial search space for practitioners.


Conclusion

This paper provides the first theoretical analysis of layer ordering effects in hybrid architectures, establishing that:

  1. For every architecture configuration, there exists a task where it provably dominates all alternatives under fixed resource constraints (Theorem 1)
  2. Natural tasks (Exact Copy, Segmented Retrieval) exhibit the predicted TS dominance, confirmed empirically with trained Transformer-Mamba hybrids
  3. Containment of dominant sub-architectures predicts performance in deeper models (4-8 layers)
  4. Mechanistic analysis via linear probing reveals that Transformer layers contribute the largest share of associative recall performance

Limitations and Future Directions

  • The general theory relies on deliberately constructed tasks and expressive abstractions of SSM and attention layers; the corresponding optimal architectures may not always be realizable by standard practical models
  • Future work should extend the theory to:
    • Practical layer classes (actual Mamba, DeltaNet implementations)
    • Richer mixtures of tasks
    • Natural-language settings
    • Identifying task-level properties that predict effective layer orderings before expensive model training

The authors hope this work establishes insights into task-dependent hybrid architecture design relevant to the training and scaling of frontier-scale hybrids.

Related papers