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