Why Depth Matters in Parallelizable Sequence Models: A Lie Algebraic View

Gyuryang Heo, Timothy Ngotiaoco, Kazuki Irie, Samuel J. Gershman, Bernardo L. SabatiniarXiv 2026 · arXiv

TL;DR

This paper uses Lie algebraic control theory to prove that increasing the depth of parallelizable sequence models (like Transformers and SSMs) allows them to overcome structural expressivity limits. The authors show that depth acts as a "tower of Lie algebra extensions," enabling these models to approximate complex, order-sensitive tasks with an error that diminishes exponentially as depth increases.

What Problem Does This Paper Address?

Modern sequence models, such as Transformers and structured state-space models (SSMs), are designed for massive parallelism. To achieve this, they often impose "order symmetry" within their layers—meaning the way a layer processes its input doesn't inherently depend on the sequence order.

However, many real-world tasks (like logic, math, or physical dynamics) are fundamentally order-sensitive. Theoretical work has shown that constant-depth parallel models are provably unable to solve certain state-tracking and reasoning problems. This creates a paradox: if these models are theoretically limited, why do they work so well in practice? The authors set out to quantify the gap between theoretical "unsolvability" and empirical success, specifically looking at how depth bridges this divide.

Methods

The authors leverage Lie theory, a mathematical framework for studying continuous transformation groups and the "order-sensitivity" of operations.

  1. Lie Algebraic Formalization: They treat SSMs as controlled dynamical systems and classify them based on their Lie algebra. For example, a model where operations commute is "Abelian" (order-symmetric), while more complex models are "Nilpotent" or "Solvable."
  2. The Magnus Expansion: To quantify error, they use the Magnus expansion, which decomposes the state evolution of a system into a series of iterated Lie brackets. This provides a direct measure of how much "order-relevant" information a model fails to capture.
  3. Depth as Extension: The core theoretical contribution is showing that stacking layers corresponds to a "tower of Lie algebra extensions." Even if individual layers are simple and Abelian, their composition can represent much more complex, non-commuting flows.
  4. Error Scaling Laws: They analytically derive a bound showing that for tasks a model cannot solve exactly, the approximation error scales as $O(\epsilon^{2^k})$, where $k$ is the number of layers. This means error drops exponentially with depth.
Figure 1: Geometric intuition of Lie the- ory. Initialized at e, consider actions A and B sequentially, and undo actions B−1 then A−1. Composition of actions ABB−1A−1 would return to e. How- ever, switching the order of undoing, by using ABA−1B−1, might not return to e, incurring a discrepancy by landing on point e′. Lie theory provides a measure of the potential offset between e and e′.

Datasets

The researchers validated their theory using two types of diagnostic tasks:

  • Symbolic Word Problems: These involve evaluating sequences of elements from finite groups (e.g., $C_2, D_8, S_4, A_5$). Each group represents a different level of algebraic complexity (Abelian, Nilpotent, Solvable, and Non-solvable).
  • Rigid-body Rotation Problem: A continuous-valued state-tracking task where the model must predict the final orientation of a 3D vector after a sequence of rotations (based on the $A_5$ group).

Key Insights and Ideas

  • Order Symmetry is a Lie Algebraic Constraint: The structural bias that allows for parallelism (like diagonal transitions in SSMs) restricts the model to an Abelian Lie algebra, which is inherently order-insensitive.
  • Depth Mitigates Obstruction: The "aha moment" is that depth isn't just about adding parameters; it's a structural mechanism that allows a model to "glue" simple operations together to simulate complex ones.
  • Exponential Convergence: The most surprising finding is the speed of error reduction. The $O(\epsilon^{2^k})$ scaling explains why relatively shallow models can still achieve high accuracy on tasks they theoretically cannot solve perfectly.
  • The Logarithmic Bound: For finite-length sequences, the authors prove that a depth of $\lfloor \log_2 T \rfloor + 1$ is sufficient for an Abelian model to simulate any word problem of length $T$.

Key Results

  • Layer Thresholds: In symbolic tasks, 1-layer models failed on almost all non-Abelian problems. However, 2-layer models (like Signed Mamba) successfully solved Nilpotent and some Solvable problems, confirming that depth unlocks new algebraic classes.
  • Depth vs. Sequence Length: Experiments on the $A_5$ group (non-solvable) showed that the maximum sequence length a model could handle increased with depth, closely following the predicted logarithmic theoretical bound (see Figure 2).
  • Rotation Accuracy: In the continuous rotation task, MSE decreased significantly as depth increased across all architectures (Transformer, GLA, Signed Mamba), though gains eventually saturated.
Figure 2: Maximum sequence length achieved vs. number of layers. The blue line represents the theoretical upper bound.
Figure 3: Mean squared error on the rotated vector prediction task at various sequence lengths for transformer, GLA, and signed Mamba, with different numbers of layers. Left and right columns illustrate the results on training and test sets, respectively. Standard error is shown using 3 seeds. Performance of DeltaProduct with 4 Householder products is shown as a reference.

Limitations and Future Work

  • Learnability vs. Expressivity: The theory focuses on what a model can represent, but the experiments showed that deeper models are often harder to train due to optimization instabilities. Learnability remains a practical bottleneck.
  • Finite Precision: The proofs assume real arithmetic. In practice, finite numerical precision might blur the "algebraic obstructions" or limit the benefits of the exponentially vanishing error.
  • Scale: While the results are theoretically robust, the experiments were limited to controlled diagnostic tasks. Testing these scaling laws in massive language models is a suggested next step.
  • Positional Encodings: The authors note that the role of advanced positional encodings in unlocking expressivity is an important open question for future Lie-algebraic study.

Summary updated

Abstract

Scalable sequence models, such as Transformer variants and structured state-space models, often trade expressivity power for sequence-level parallelism, which enables efficient training. Here we examine the bounds on error and how error scales when models operate outside of their expressivity regimes using a Lie-algebraic control perspective. Our theory formulates a correspondence between the depth of a sequence model and the tower of Lie algebra extensions. Echoing recent theoretical studies, we characterize the Lie-algebraic class of constant-depth sequence models and their corresponding expressivity bounds. Furthermore, we analytically derive an approximation error bound and show that error diminishes exponentially as the depth increases, consistent with the strong empirical performance of these models. We validate our theoretical predictions using experiments on symbolic word and continuous-valued state-tracking problems.
BibTeX
@misc{heo2026why,
  author = {Gyuryang Heo and Timothy Ngotiaoco and Kazuki Irie and Samuel J. Gershman and Bernardo L. Sabatini},
  title = {{Why Depth Matters in Parallelizable Sequence Models: A Lie Algebraic View}},
  year = {2026},
  eprint = {2603.05573},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.05573},
}
Figure