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

• URL: http://arxiv.org/abs/2603.05573v1
• Date: Thu, 05 Mar 2026 16:16:13 GMT
• Title: Why Depth Matters in Parallelizable Sequence Models: A Lie Algebraic View
• Abstract summary: We examine the bounds on error and how error scales when models operate outside of their expressivity regimes.<n>Our theory formulates a correspondence between the depth of a sequence model and the tower of Lie algebra extensions.<n>We analytically derive an approximation error bound and show that error diminishes exponentially as the depth increases.
• Score: 15.326860959311622
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Invariant Learning Dynamics of Transformers in Inductive Reasoning Tasks [50.79340930913805]
  We study a class of inductive tasks that unifies several synthetic tasks known in the literature, including in-context n-grams and multi-hop reasoning.<n>By casting circuit formation as a low-dimensional dynamical phenomenon, we take a step toward a predictive theory of how Transformers learn.
  arXiv  Detail & Related papers  (2026-07-13T17:56:11Z)
• An Asymptotic Theory of Chain-of-Thought in In-Context Learning [34.69440744042684]
  Chain-of-thought (CoT) reasoning has become a widely used mechanism for eliciting multi-step reasoning in large language models.<n>We study a theoretically solvable model of CoT for in-context weight prediction in linear regression.<n>We derive an exact formula for the generalization error as a function of reasoning depth, pretraining data amount, and context length.
  arXiv  Detail & Related papers  (2026-06-02T06:23:31Z)
• Why Can't Transformers Learn Multiplication? Reverse-Engineering Reveals Long-Range Dependency Pitfalls [54.57326125204404]
  Language models are increasingly capable, yet still fail at a seemingly simple task of multi-digit multiplication.<n>We study why, by reverse-engineering a model that successfully learns multiplication via emphimplicit chain-of-thought'
  arXiv  Detail & Related papers  (2025-09-30T19:03:26Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• A Convergence Theory for Diffusion Language Models: An Information-Theoretic Perspective [8.15094483029656]
  Diffusion models enable parallel token sampling, leading to faster generation and eliminating left-to-right generation constraints.<n>We develop convergence guarantees for diffusion language models from an information-theoretic perspective.<n>These results offer novel theoretical insights into the practical effectiveness of diffusion language models.
  arXiv  Detail & Related papers  (2025-05-27T16:24:20Z)
• Can Diffusion Models Disentangle? A Theoretical Perspective [37.21661224725838]
  This paper presents a novel theoretical framework for understanding how diffusion models can learn disentangled representations.<n>We establish identifiability conditions for general disentangled latent variable models, analyze training dynamics, and derive sample complexity bounds for disentangled latent subspace models.
  arXiv  Detail & Related papers  (2025-03-31T20:46:18Z)
• Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelines [74.42485647685272]
  We focus on Generative Masked Language Models (GMLMs) We train a model to fit conditional probabilities of the data distribution via masking, which are subsequently used as inputs to a Markov Chain to draw samples from the model. We adapt the T5 model for iteratively-refined parallel decoding, achieving 2-3x speedup in machine translation with minimal sacrifice in quality.
  arXiv  Detail & Related papers  (2024-07-22T18:00:00Z)
• Iteratively Refined Image Reconstruction with Learned Attentive Regularizers [14.93489065234423]
  We propose a regularization scheme for image reconstruction that leverages the power of deep learning. Our scheme is interpretable because it corresponds to the minimization of a series of convex problems. We offer a promising balance between interpretability, theoretical guarantees, reliability, and performance.
  arXiv  Detail & Related papers  (2024-07-09T07:22:48Z)
• State-space Models with Layer-wise Nonlinearity are Universal Approximators with Exponential Decaying Memory [0.0]
  We show that stacking state-space models with layer-wise nonlinear activation is sufficient to approximate any continuous sequence-to-sequence relationship. Our findings demonstrate that the addition of layer-wise nonlinear activation enhances the model's capacity to learn complex sequence patterns.
  arXiv  Detail & Related papers  (2023-09-23T15:55:12Z)
• Gradient flow in the gaussian covariate model: exact solution of learning curves and multiple descent structures [14.578025146641806]
  We provide a full and unified analysis of the whole time-evolution of the generalization curve. We show that our theoretical predictions adequately match the learning curves obtained by gradient descent over realistic datasets.
  arXiv  Detail & Related papers  (2022-12-13T17:39:18Z)
• Multi-scale Feature Learning Dynamics: Insights for Double Descent [71.91871020059857]
  We study the phenomenon of "double descent" of the generalization error. We find that double descent can be attributed to distinct features being learned at different scales.
  arXiv  Detail & Related papers  (2021-12-06T18:17:08Z)
• Boundary theories of critical matchgate tensor networks [59.433172590351234]
  Key aspects of the AdS/CFT correspondence can be captured in terms of tensor network models on hyperbolic lattices. For tensors fulfilling the matchgate constraint, these have previously been shown to produce disordered boundary states. We show that these Hamiltonians exhibit multi-scale quasiperiodic symmetries captured by an analytical toy model.
  arXiv  Detail & Related papers  (2021-10-06T18:00:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.