betaFeedback

WorksComputer Science

Implicit Bias in State Space Models and Linear Autoregressive Training

Abstract

Linear State Space Models (SSMs) and linear autoregressive sequence models reuse the same parameters across a sample-dependent number of steps. As a result, different examples impose constraints through different predictors, even though all predictors share the same weights. We study this phenomenon through a general model of multiple non-homogeneous polynomial predictors with shared parameters, in a classification setting. Under standard interpolation and directional-convergence assumptions, together with a trajectory-dependent effective-degree condition, we show that gradient descent on the exponential loss converges in direction to a KKT point of an effective-degree max-margin problem. In this problem, only examples with minimal effective degree impose hard margin constraints; examples with faster-growing margins are asymptotically inactive except for feasibility. Our result provides a first-order characterization of the implicit bias in linear SSMs and linear autoregressive models. It exposes a mechanism of length bias: a longer input sequence or additional autoregressive steps may increase the example's effective degree, and the examples with the smallest effective degree dominate the limiting classifier. Our result highlights how non-homogeneity and parameter sharing alter classical homogeneous implicit-bias results.

Introduction

Ever since the introduction of Transformers Vaswani et al., [37], they have been widely used for autoregressive sequence generation, and have come to dominate many areas of machine learning [3, 8] (Ji et al. 2025). Recently, State Space Models (SSMs) have emerged as a promising alternative. By offering improved computational efficiency while maintaining competitive performance, SSMs are increasingly being adopted across a range of tasks [27, 6] (Gu et al. 2021; Gu & Dao 2023).

Autoregressive models reuse the same parameters across repeated computation steps. When examples have different sequence lengths or require different numbers of rollout steps, the final prediction for each example may be a different function of the same shared parameters. Even if the per-step computation is linear, the resulting margin is generally a non-homogeneous polynomial in the parameters, with a degree that depends on the number of autoregressive applications.

This creates a setting that is not captured by the existing max-margin implicit-bias theory. Classical results show that gradient descent on separable linear models with an exponential-type loss converges in direction to a hard-margin classifier Soudry et al., [30], and later work extends this picture to homogeneous and some non-homogeneous parameterizations [13, 23, 20, 2] (Ji & Telgarsky 2020b). In those settings, however, the training examples are typically evaluated by a single shared predictor, or by predictors with a common homogeneity structure. In contrast, variable-step autoregressive models lead to multiple polynomial predictors, one per example or per length class, all sharing parameters but potentially growing at different asymptotic rates during training.

We study this phenomenon through the lens of shared-parameter, linear-in-the-input polynomial predictors, in a classification setting. Our main observation is that the relevant degree of a predictor is not necessarily its algebraic degree. Along a gradient-descent trajectory, leading homogeneous components may vanish in the limiting direction, causing a high-degree margin polynomial to grow like a lower-degree polynomial. We call this trajectory-dependent quantity the effective degree. Since exponential-loss gradients weight examples by their current margins, examples with larger effective degree can become asymptotically suppressed, while examples with smaller effective degree can determine the limiting classifier.

Our main result gives a conditional max-margin characterization for this setting. Assuming that the loss converges to zero, the parameter direction converges, and each margin has a well-defined integer effective degree along the trajectory, we prove that the limiting direction of gradient descent satisfies the KKT conditions of an effective-degree max-margin problem. The unit-margin constraints are imposed only by examples with minimum effective degree, and higher-effective-degree examples enter only through feasibility constraints. Thus the limiting classifier can be governed by the slowest-growing margins rather than by all examples equally.

We instantiate the theorem in scalar linear autoregressive models, linear state-space models (SSMs), and linear autoregressive SSMs. These models are not intended to capture all features of modern sequence architectures; rather, they isolate the effect of parameter reuse across variable numbers of steps. Indeed, the implicit bias of linear models and linear neural networks has been extensively studied as a testbed for understanding the implicit bias in more complex architectures [34], and we adopt this approach here by considering linear autoregressive models and linear SSMs. In our simplified settings, when additional recurrent or autoregressive steps increase effective degree, our theorem predicts a form of length-sensitive implicit bias: shorter or lower-effective-degree examples can dominate the asymptotic margin solution.

Our contribution:

  • We introduce a trajectory-dependent effective degree for non-homogeneous polynomial predictors and show that it can differ sharply from the algebraic degree.

  • Under standard asymptotic convergence assumptions and an effective-degree regularity assumption, we prove a max-margin/KKT characterization of the gradient-descent limit for exponential loss. This characterization is significantly different from the standard max-margin characterization of homogeneous models.

  • We show that, in the linear autoregressive and SSM instantiations, this characterization yields a length-sensitive bias whenever additional computation steps increase effective degree.

Related Work

Implicit bias in homogeneous and near-homogeneous models. There is a large body of work studying the implicit bias of gradient-based optimization. Soudry et al. [30] initiated this line of work by showing that gradient descent on separable data with the logistic loss converges in direction to the max-margin classifier. Subsequent works extended this perspective to broader classes of models, including linear convolutional networks and homogeneous polynomials [13 a]. For homogeneous models, Lyu & Li [23] showed that any limit point of the optimization path is in the direction of a KKT point of the corresponding margin-constrained Euclidean-norm minimization problem, and Ji & Telgarsky (2020b) established directional convergence of parameters and gradients under additional structural assumptions. Ji & Telgarsky (2020a) used the induced dynamics on dual variables to characterize convergence rates to the implicit bias in linear models; we use a related observation to prove directional convergence of the gradient along a subsequence.

Several works go beyond standard homogeneity. Nacson et al. [25] studied regularization paths for sums of homogeneous models with different degrees, but their setting uses separate parameters for each homogeneous component and does not analyze gradient descent dynamics. Kunin et al. [20] generalized this framework to quasi-homogeneous models, where different parameters have different homogeneity degrees, and showed that the resulting implicit bias can be asymmetric. Our polynomial models, as well as their multidimensional extensions, do not fall under this quasi-homogeneous framework; see Section A.2. Lippl et al. [22] studied gradient descent on parameter-sharing homogeneous polynomials, allowing the polynomial to vary across examples.

Most closely related to our treatment of non-homogeneous structure is Cai et al. [2], who established implicit bias results for nearly-homogeneous models. Although polynomials satisfy their definition of near-homogeneity, their analysis considers a single predictor shared across all data points, whereas we study a more general setting in which each data point may induce a different predictor. Moreover, their result relies on a strong assumption on the optimization dynamics, which we relax for polynomials; see Section 4.2 for a detailed comparison.

Implicit bias in attention and sequence models. Recent works have begun to study implicit bias in sequence models. For self-attention, Tarzanagh et al. (2023); Ataee Tarzanagh et al. (2023); Vasudeva et al. [36] analyze the implicit bias and convergence behavior of attention-based architectures. These works are complementary to ours: they focus on attention mechanisms, whereas our analysis concerns polynomial and state-space/autoregressive structures.

State-space models and linear autoregressive models. Several recent theoretical works study state-space models and related linear autoregressive models in settings close to ours. Merrill et al. [24] analyze the expressivity of state-space models. Slutzky et al. [28] study the effect of data poisoning on the implicit bias of diagonal SSMs with the square loss for sequences of fixed length. Other works analyze SSMs with structured transition matrices or related architectures (Gu et al. (2021); Dao & Gu [6]), while Smékal et al. [29] study the learning dynamics of SSMs under square loss. For autoregressive models, Joshi et al. [17, 18] establish computational learning results for autoregressive linear threshold models in a setting similar to ours, and Thrampoulidis [32] study implicit optimization bias in linear autoregressive next-token prediction with fixed-length sequences and cross-entropy loss. Finally, Emami et al. [7] analyze linear RNNs at the NTK limit, showing that the effect of input tokens decays geometrically; the model they consider is reminiscent of the SSMs studied in § 3.3.

Preliminaries and Problem Definition

Notations. We denote vectors v∈Rd\mathbf{v} \in\mathbb{R}^{d} by boldface letters i.e. v=(v1,…,vd)\mathbf{v} = (v_{1}, \ldots, v_{d}), and vˉ:=v/∥v∥\bar{\mathbf{v}} := \mathbf{v}/\lVert\mathbf{v}\rVert.

We denote the sign function sgn⁡(x):={1x≥0−1else\operatorname{sgn}(x) := \begin{cases} 1 & x \ge0 \\ -1 & \text{else} \end{cases}. We denote by ∥⋅∥\lVert\cdot\rVert the Euclidean norm, and [n]:={1,…,n}[n] := \{1,\ldots,n\}. For ν∈N\nu\in\mathbb{N}, we denote by Pν\mathcal{P}^{\nu} the sum of (multivariate, vector valued) monomials in P\mathcal{P} of degree ν\nu, this is a ν\nu-homogeneous polynomial, which we call the ν\nu-homogenization of P\mathcal{P}.

Problem Definition

Model and Data. We consider a dataset {Xi,yi}i=1N\{X_i,y_i\}_{i=1}^{N} where Xi∈Rd×ℓiX_i \in\mathbb{R}^{d \times\ell_i} and yi∈{±1}y_i \in\{\pm1\}. We view each input sample XiX_i as ℓi\ell_i tokens, each of dimension dd. Note that we allow for each sample to have a different number of tokens. The difficulty in determining the implicit bias of our models already appears in the case of d=1d=1. Hence, for brevity, in the main part of the paper, we consider the case of d=1d=1, namely, each token is a scalar in R\mathbb{R}, and we denote the input sequence as xi∈Rℓix_i \in\mathbb{R}^{\ell_i}. All our results are readily extended to the case where dd is some constant larger than 11, and we prove these extensions formally in Section B.

Let {xi,yi}i=1N\{x_i,y_i\}_{i=1}^{N} be a dataset where xi∈Rℓix_i \in\mathbb{R}^{\ell_i}, yi∈{±1}y_i \in\{\pm1\}. We define a set of models {Mi:RD→Rℓi}i=1N\{\mathcal{M}_i : \mathbb{R}^{D} \to\mathbb{R}^{\ell_i}\}_{i=1}^{N}, that share the same parameters w∈RD\mathbf{w} \in\mathbb{R}^{D}, but might have different output dimensions. These models act linearly on the data xix_i, namely their output is y^i:=⟨Mi(w),xi⟩\hat{y}_i := \langle\mathcal{M}_i(\mathbf{w}), x_i\rangle where ℓi\ell_i is the dimension of the ii-th sample, i.e. xi∈Rℓix_i \in\mathbb{R}^{\ell_i}, or in other words, the number of one dimensional tokens xix_i has. Note that although {Mi:RD→Rℓi}i=1N\{\mathcal{M}_i : \mathbb{R}^{D} \to\mathbb{R}^{\ell_i}\}_{i=1}^{N} indexes NN models, they may not all be distinct, i.e., we allow Mi=Mj\mathcal{M}_i = \mathcal{M}_j for some i≠ji \ne j. This multi-model setting is a generalization of the standard implicit bias setting where all the samples share the same predictor M\mathcal{M}. This framing aligns with the setting of SSMs and autoregressive models, where each sample may consist of a different number of input tokens or autoregressive steps. In this paper, we focus on two such models: (1) a linear autoregressive model and (2) a linear state-space model (SSM), formally defined in § 3.2 and § 3.3. Although the models acts linearly on the input data, their parameterizations can be highly non-linear, leading to implicit biases that differ substantially from those of standard linear predictors.

Training. In this paper we will consider the exponential loss and denote L(w)=∑i=1nexp⁡(−yiMi(w)Txi)\mathcal{L}(\mathbf{w}) = \sum_{i=1}^{n}\exp(-y_i\mathcal{M}_i(\mathbf{w})^{\mathsf{T}}\mathbf{x}_i). Our results can be readily extended to the logistic loss as well. Throughout the paper, we consider gradient descent w.r.t. vectors or matrices of the parameters. We denote by w(0)\mathbf{w}^{(0)} the parameters at initialization, and

w(t)=w(t−1)−ηt∇L(w(t−1)),(1)\mathbf{w}^{(t)}=\mathbf{w}^{(t-1)}-\eta_t\nabla\mathcal{L}(\mathbf{w}^{(t-1)}), \tag*{(1)}

as the parameter vector after the ttht^{\text{th}} step of gradient descent, where ηt\eta_t denotes the learning rate at time tt. Our results can be applied to general learning rate schedulers, and we only assume the learning rate sequence {ηt}t=1∞\{\eta_t\}_{t=1}^{\infty} does not increase. We denote by wˉ∞=lim⁡t→∞w(t)∥w(t)∥\bar{\mathbf{w}}^{\infty}=\lim_{t\to\infty}\frac{\mathbf{w}^{(t)}}{\lVert\mathbf{w}^{(t)}\rVert} the directional limit of w\mathbf{w} when it exists.

Linear Autoregressive Model

The first model we consider is a linear autoregressive model. This type of models is common in many academic fields for the prediction of time series Gujarati & Porter [11]; Wei [38]; Kirchgässner et al. [19]; Dama & Sinoquet [5]; Chen et al. [4]. Moreover, it is a basic simplification of large language models, where we isolate the autoregressive part of transformers from the non-linear parts which are the self-attention and MLP. The core mechanism is that the model generates new tokens, and then apply itself autoregressively on its own output.

We consider an example x∈Rl\mathbf{x}\in\mathbb{R}^{l} which we interpret as an input prompt, i.e., the initial part of some sequence. Here we will consider parameters w∈RD\mathbf{w}\in\mathbb{R}^{D} and assume for simplicity D=lD=l, thus xT=x1:DT=(x1,…,xD)\mathbf{x}^{\mathsf{T}}=\mathbf{x}_{1:D}^{\mathsf{T}}=(x_1,\ldots,x_D). We compute a sequence of TT autoregressive steps, where the final token’s sign is the label. Formally, the model computes:

xD+1=⟨w,x⟩,xD+2=⟨w,x2:D+1⟩,…,xD+T=⟨w,xT:D+T−1⟩.(2)x_{D+1}=\langle\mathbf{w},\mathbf{x}\rangle,\quad x_{D+2}=\langle\mathbf{w},\mathbf{x}_{2:D+1}\rangle,\quad\ldots,\quad x_{D+T}=\langle\mathbf{w},\mathbf{x}_{T:D+T-1}\rangle. \tag*{(2)}

The label of the sequence is defined as sgn⁡(xD+T)\operatorname{sgn}(x_{D+T}). More generally, we may allow l≠Dl\ne D: in the case l<Dl<D, we pad x=(0,…,x1,…,xl)\mathbf{x}=(0,\ldots,x_1,\ldots,x_l), and in the case l>Dl>D, apply w\mathbf{w} only to the last DD elements of x\mathbf{x}. This can be thought of as the input prompt being longer than the model’s context length.

We denote the vector of coefficients of x1,…,xDx_1,\ldots,x_D in xD+Tx_{D+T} as P\mathcal{P}, a polynomial in w\mathbf{w}. Using this notation, we have that ⟨P(w),x⟩=xD+T\langle\mathcal{P}(\mathbf{w}),\mathbf{x}\rangle=x_{D+T}. See Figure 1 for a demonstration.

Figure 1. Movie-strip view of the autoregressive construction.

We can interpret the setup in the context of language models as having ll initial one-dimensional tokens, x1,…,xlx_1,\ldots,x_l, which serve as the starting sequence. In standard transformers, and autoregressive language models in general, text is generated token by token: the model predicts the next token based on the current sequence, appends this token, and then feeds the entire updated sequence back into the model to produce the next one, TT times. Our framework mirrors this process but uses a linear autoregressive model, which is more tractable to analyze. We note that in our work the polynomials are usually associated with an indexed example xi∈Rli\mathbf{x}_i\in\mathbb{R}^{l_i}, hence we denote them Pi\mathcal{P}_i. Note that crucially for a dataset {xi,yi}i=1N\{x_i,y_i\}_{i=1}^{N}, we have a number of autoregressive steps TiT_i for each example, which together with lil_i changes Pi\mathcal{P}_i. That is, both elements embodied in the polynomial predictor. This also means that we may have Pi=Pj\mathcal{P}_i=\mathcal{P}_j for i≠ji\ne j, if both examples i,ji,j are labeled using the same number TiT_i of autoregressive steps and share the same input length lil_i. We note that in this model our training setup corresponds to training directly on the output after TiT_i steps, rather than training on the next-token-prediction.

Linear State Space Models

The second model we consider, is a Linear State Space Model (SSM). SSMs are used to model natural phenomena and have been lately adopted by the Machine Learning community as a promising candidate for Large Language Models to replace and complement Transformers (Gu et al., 2021; Gu & Dao, 2023; [6]).

References

  1. [2]Cai, Yuhang, Zhou, Kangjie, Wu, Jingfeng, Mei, Song, Lindsey, Michael, & Bartlett, Peter. 2025. Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks. Pages 6426–6504 of: Singh, Aarti, Fazel, Maryam, Hsu, Daniel, Lacoste-Julien, Simon, Berkenkamp, Felix, Maharaj, Tegan, Wagstaff, Kiri, & Zhu, Jerry (eds), Proceedings of the 42nd International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 267. PMLR.arxiv.org/abs/2502.16075
  2. [3]Chandra, Abel, Tünnermann, Laura, Löfstedt, Tommy, & Gratz, Regina. 2023. Transformer-based deep learning for predicting protein properties in the life sciences. eLife, 12(jan), e82819.
  3. [4]Chen, Xinyu, Digalakis, V., Ding, L., Zhuang, Dingyi, & Zhao, Jinhua. 2025. Interpretable Time Series Autoregression for Periodicity Quantification. ArXiv, abs/2506.22895.arxiv.org/abs/2506.22895
  4. [5]Dama, F., & Sinoquet, Christine. 2021. Partially Hidden Markov Chain Linear Autoregressive model: inference and forecasting. ArXiv, abs/2102.12584.arxiv.org/abs/2102.12584
  5. [6]Dao, Tri, & Gu, Albert. 2024. Transformers are ssms: Generalized models and efficient algorithms through structured state space duality. arXiv preprint arXiv:2405.21060.arxiv.org/abs/2405.21060
  6. [7]Emami, Melikasadat, Sahraee-Ardakan, Mojtaba, Pandit, Parthe, Rangan, Sundeep, & Fletcher, Alyson K. 2021. Implicit Bias of Linear RNNs.arxiv.org/abs/2101.07833
  7. [8]Erol, Mehmet Hamza, Senocak, Arda, Feng, Jiu, & Chung, Joon Son. 2024. Audio Mamba: Bidirectional State Space Model for Audio Representation Learning. IEEE Signal Processing Letters, 31, 2975–2979.arxiv.org/abs/2406.03344
  8. [11]Gujarati, Damodar N, & Porter, Dawn C. 2009. Basic econometrics. McGraw-hill.
  9. [13]Gunasekar, Suriya, Lee, Jason D, Soudry, Daniel, & Srebro, Nati. 2018b. Implicit bias of gradient descent on linear convolutional networks. Advances in neural information processing systems, 31.arxiv.org/abs/1806.00468
  10. [17]Joshi, Nirmit, Vardi, Gal, Block, Adam, Goel, Surbhi, Li, Zhiyuan, Misiakiewicz, Theodor, & Srebro, Nathan. 2025. A Theory of Learning with Autoregressive Chain of Thought.arxiv.org/abs/2503.07932
  11. [18]Joshi, Nirmit, Magen, Roey, Srebro, Nathan, Tsilivis, Nikolaos, & Vardi, Gal. 2026. Learning to Think from Multiple Thinkers.arxiv.org/abs/2604.24737
  12. [19]Kirchgässner, Gebhard, Wolters, Jürgen, & Hassler, Uwe. 2012. Introduction to modern time series analysis. Springer Science & Business Media.
  13. [20]Kunin, Daniel, Yamamura, Atsushi, Ma, Chao, & Ganguli, Surya. 2022. The asymmetric maximum margin bias of quasi-homogeneous neural networks. arXiv preprint arXiv:2210.03820.arxiv.org/abs/2210.03820
  14. [21]LeCun, Yann. 1998. The MNIST database of handwritten digits. http://yann. lecun. com/exdb/mnist/.
  15. [22]Lippl, Samuel, Abbott, L. F., & Chung, SueYeon. 2022. The Implicit Bias of Gradient Descent on Generalized Gated Linear Networks.arxiv.org/abs/2202.02649
  16. [23]Lyu, Kaifeng, & Li, Jian. 2019. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv:1906.05890.arxiv.org/abs/1906.05890
  17. [24]Merrill, William, Petty, Jackson, & Sabharwal, Ashish. 2025. The Illusion of State in State-Space Models.arxiv.org/abs/2404.08819
  18. [25]Nacson, Mor Shpigel, Gunasekar, Suriya, Lee, Jason D., Srebro, Nathan, & Soudry, Daniel. 2019. Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models.arxiv.org/abs/1905.07325
  19. [27]Ren, Liliang, Liu, Yang, Lu, Yadong, Shen, Yelong, Liang, Chen, & Chen, Weizhu. 2025. Samba: Simple Hybrid State Space Models for Efficient Unlimited Context Language Modeling.arxiv.org/abs/2406.07522
  20. [28]Slutzky, Yonatan, Alexander, Yotam, Razin, Noam, & Cohen, Nadav. 2025. The Implicit Bias of Structured State Space Models Can Be Poisoned With Clean Labels.arxiv.org/abs/2410.10473
  21. [29]Smékal, Jakub, Smith, Jimmy T. H., Kleinman, Michael, Biderman, Dan, & Linderman, Scott W. 2024. Towards a theory of learning dynamics in deep state space models.arxiv.org/abs/2407.07279
  22. [30]Soudry, Daniel, Hoffer, Elad, Nacson, Mor Shpigel, Gunasekar, Suriya, & Srebro, Nathan. 2018. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70), 1–57.arxiv.org/abs/1710.10345
  23. [32]Thrampoulidis, Christos. 2024. Implicit Optimization Bias of Next-Token Prediction in Linear Models.arxiv.org/abs/2402.18551
  24. [33]Timor, Nadav, Vardi, Gal, & Shamir, Ohad. 2022. Implicit Regularization Towards Rank Minimization in ReLU Networks.arxiv.org/abs/2201.12760
  25. [34]Vardi, Gal. 2023. On the implicit bias in deep-learning algorithms. Communications of the ACM, 66(6), 86–93.arxiv.org/abs/2208.12591
  26. [35]Vardi, Gal, & Shamir, Ohad. 2021. Implicit Regularization in ReLU Networks with the Square Loss.arxiv.org/abs/2012.05156
  27. [36]Vasudeva, Bhavya, Deora, Puneesh, & Thampoulidis, Christos. 2025. Implicit Bias and Fast Convergence Rates for Self-attention.arxiv.org/abs/2402.05738
  28. [37]Vaswani, Ashish, Shazeer, Noam, Parmar, Niki, Uszkoreit, Jakob, Jones, Llion, Gomez, Aidan N, Kaiser, Łukasz, & Polosukhin, Illia. 2017. Attention is all you need. Advances in neural information processing systems, 30.arxiv.org/abs/1706.03762
  29. [38]Wei, William WS. 2013. Time series analysis. Oxford University Press.

Paper details

vlnc:W_su9z97u7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents