In-context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-separation
Authors: Frank Cole
Yuxuan Zhao
Yulong Lu
Tianhao Zhang
Venue: NeurIPS 2025 poster ()
Keywords: In-context learning
linear dynamical systems
depth-separation
Primary area: theory
TL;DR: We show that shallow linear transformers fail to in-context learn linear dynamical systems, uncovering a distinction between in-context learning over iid and non-iid data; in contrast, transformers with log-depth successfully learn dynamical systems.

Abstract: This paper investigates approximation-theoretic aspects of the in-context learning capability of the transformers in representing a family of noisy linear dynamical systems. Our first theoretical result establishes an upper bound on the approximation error of multi-layer transformers with respect to an $L^2$-testing loss uniformly defined across tasks. This result  demonstrates that transformers with logarithmic depth can achieve error bounds comparable with those of the least-squares estimator. In contrast, our second result establishes a non-diminishing lower bound on the approximation error for a class of single-layer linear transformers, which suggests  a depth-separation phenomenon for transformers in the in-context learning of dynamical systems. Moreover, this second result uncovers a critical distinction in the approximation power of single-layer linear transformers when learning from IID versus non-IID data.

In-Context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-separation
Frank Cole School of Mathematics
Yuxuan Zhao" School of Mathematics University of Minnesota, Twin Cities Minneapolis, MN 55455 zhao 18950umn. edu
University of Minnesota, Twin Cities Minneapolis, MN 55455 cole09320umn. edu
Yulong Lu School of Mathematics University of Minnesota, Twin Cities Minneapolis, MN 55455 yulongludurn, edu
Tianhao Zhang School Mathematics University of Minnesota, Twin Cities Minneapolis, MN 55455 2han7594@umn. edu
Abstract
This paper investigates approximation-theoreeie aspects of the in-context learning capability of the transformers in representing faaiily of noisy linear dynamical systems. Our first theoretical result establishes an upper bound on the approxima- tion error of multi-layer transformers with respect to an L-e-testing loss uniformly defined across tasks. This result demonstrates that transformers with logarithmic depth can achieve error bounds comparable with those of the least-squares esti- mator. In contrast, our second result establishes a non-diminishing lower bound on the approximation етrоr for class of single-layer linear transformers, which suggests a -epaaatttnaatoonn phenomenon for transformers the in-context learning of dynamical systems. Moreover, this second result uncovers a critical distinction in the approximation power of single-layer linear transformers when learning from IID versus non-IID data.
Introduction
Transformers Vaswani 2017 have achieved remarkable success in natural language processing,
driving the success of modern large language models such as ChatGPT Achiam et al. [2023) The
ChatGPT|Achian
impressive capabilities of transformers in NL.P tasks has spurred their adoption across diverse domains beyond NLP, such as computer vision Li et al. 2023 Khan et al. [2022], Chen et al. (2020) Ramesh
al. 2021 computational biology Jumper al. [2021] J. Choi and Lee [0233 physical modeling
Batatia et al. 20233 McCabe et al. [2023] Subramanian et al. [2024]. Ye el al. 20244] among others.
particularly intriguing property transformers their ability perform in-oontex learning: pre-
trained transformers are able to make accurate predictions on unseen sequences, even those beyond the
support of their pre-training distribution, without any parameter updates. One promising explanation for these striking behaviors is the mesa-optis optimizaainnnnn hypothesis Von Oswald et al. [2023a] b), which says that transformers make next-token predictions by implicitly optimizing a context-dependent loss according some optimization algorithm encoded during pre-training.
'Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To elucidate these emergent properties, a lot of recent research has studied in in-context learning
in tractable settings. For instance, several works studied in-context learning of linear models by
simplified transformer architectures Zhang et al. [2023] Mahankali et al. [2023] Ahn et al. [0233]
In this setting, has been shown that the transformer which minimizes a natural population risk
indeed performs in-context learning over the class of linear models, and its prediction error decays at
the parametric rate O (1/T)), where is the number of samples of the downstream task. Moreover, these trained transformers enjoy prediction error bounds that hold uniformly over the set of admissible tasks, despite only being trained on an L loss. The learning algorithm encoded by transformers trained in-context examples of linear regression descent on a context-dependen loss, confirming earlier hypotheses by empirical works Von Oswald al. 2023a Most of the prior theoretical works described in the previous paragraph works assume IID data, where each sequence (Fo, 21,,,,,,,,77 consists of uncorrelated tokens. A more realistic assumption is that the data/tokens are correlated, and linear dynamical systems provide natural and tractable setting to study in-context learning of correlated data. this non-IlI) setting, many theoretical questions the in-context learning capability of transformers have remained elusive:
be expressed as single step of gradient
1. Given a class of dynamical systems, does there exist a transformer which in-context learns the class? If so, can we quantify the prediction error rate achieved by the transformer?
2. How complex must the transformer architecture be in order to perform in-context learning?
3. What algorithm do transformers trained to perform in-context learning over dynamical systems encode?
In this work, we focus on the first two questions above and investigate the approximation power of linear transformers in in-context learning for class of linear dynamical systems which corrupted by noise. Specifically, we are interested in learning from sequences T1, (1....,...., Pr) that generated according to the linear stochastic dynamics
Tt W W + &., 1 st
where W Rddd is matrix whose eigenvalues lie in (0, 1) and is independent Gaussian noise. Our goal is to derive quantitative results that characterize the ability (or inability) of linear transformers to learn the linear map defined by the conditional expectation 2;-1 + [[,1| in-context, from dynamical systems governed by Equation (2) Our main contributions are highlighted as follows.
1. We establish an approximation error bound for a class of deep linear transformers in learning the family of dynamical systems (2) in-context; see Theorem More precisely, we show that linear transformers whose depth scales (log(T)) can achieve error of O (log(T)/ with respect to an t.2-testing loss uniformly defined across tasks. The proof is based on constructing a transformer which approximates the least-squares estimator of the system (2 through iterative methods, while leveraging statistical properties of the least-squares estimator.
2. We further investigate the role of depth of transformers in our first result. We demonstrate that a broad class of single-layer linear transformers fundamentally limited in its ability to perform in-context learning for the system described by Equation (2) Specifically, the test loss satisfies lower bound that remains independent of the transformer's parameterization, even as the length of the trajectory data T approaches infinity; see Theorem 2
To the best our knowledge, our work is the first to quantitatively analyze the in-context population loss for non-IID data, and the techniques required differ substantially from the IID case. In particular, our second result uncovers a distinct feature of single-layer linear transformers: their inability to learn from dependent data. This was observed in different setting in Zheng et al. (2024). In contrast, it has been shown in the IID setting that (see e.g. Zhang et al. (2023) single-layer linear transformers provably learns linear models in-context, in the sense that optimized transformer can achieve zero test loss in the infinite context-length limit. We will expand upon the reasons behind the differing outcomes between these two settings in more detail in Section 3.3
1.1 Related work
ICL in the IID setting: In the setting of IID-data, Garg et al. [002 introduced the concept of in-context learning function class and demonstrated experimentally that trained transformers

---

can indeed learn simple function classes in in-tontext. Several empirical works provided evidence that transformers perform in-context learning by implementing mesa-optimization algorithm to minimize a context-dependent loss Von Oswald et al. 2023a Akyürek et al. [2022] Dai et al. 2022], ,. Müller al. [02TT- Subsequently, several theoretical works proved that single-layer linear transformers indeed implement one step of gradient descent to solve linear regression tasks Zhang ct al. 2023). Mahankali et al. [2023] 3 Ahnn et al. (2023), [u et al. [2023]. Recent works have refined the analysis of single-layer linear transformers, proving additional results expressivity Zhang et al.
2024). adaptivity Vladymyrov et al. [2024), adversarial robustness Anwar et al. [2024]. J. and task diversity Cole et al. [2024]. Lu et al. [2224] For softmax attention, recent works Collins et al. [2024]
Li al. 2024] derived in-context learning guarantees for one-layer transformers and related their inference-time prediction to nearest neighbor algorithms. Concerning deep models, the theoretical
works Giannouu et al. [2024]. Fu et al. [023] proved that multi-layer transformers can implement higher-order optimizations such as Newton's method. Beyond linear functions, several works have proven approximation, statistical, and optimization error guarantees for in-context learning over
larger (possibly nonparametric) classes of nonlinear functions Yang et al. [2024] Guo al. 20223]
Kim and Suzuki 20244. Bai et al. 2022), Kim et al. 20244] Li et al. 2025
ICL in the non-III setting: There are substantially fewer theoretical works on the in-context learning capabilities of transformers for non-IID data. Several works have analyzed transformers in the context of state space modeling and filtering problems Goel and Bartlett [2024). Li et al.
[2023]. AAram and Vikalo 2024), Ziemann et al. 2024]. Closer to our setting, the work Von Oswald et al. 2023b) extended the constructions of Von Oswald et al. [023a] to the autoregressive setting and hypothesized that autoregressively--ran
optimizatinn algorithms to solve downstream tasks. The works Sander et al. [2024], J. Zheng et al. [2024] share a similar setting to our work and they prove that the construction in Von Oswald et al. [2023b] is
transformers learn to implement
optimal for data arising from class of noiseless linear dynamical systems; in particular, Zheng et al.)
(2224] provides a sufficient condition under which the mesa-optimizer is learned during pre-training.
Huang et al. 2024) studied the convergence of trained transformers on a different non-IID next-token prediction task. The work Ziemann et al. (2024) proved a lower bound on the number of parameters
required to represent non-ergodic state space models in a different setting from ours.
Notably, the work Guo et al. [0033] and the concurrent work Wu et al. [2025] study the ability of transformers to approximate least squares algorithms for predicting (possibly more complex) dynamical systems. Our work differs from these two in that, while we study a simpler linear dynamical system, we prove approximation bounds with respect to the next token prediction error on noisy data, whereas the previous works only consider the ability of transformers to implement the least squares algorithm. In partieular, our results requires us synthesize our particular construction with statistical guarantees of the least-squares estimator (LSE) on noisy data, and to control the error incurred on the event where the LSE bounds fail to hold. Additionally, our constructions for the upper bounds are more parameter efficient (by leveraging the Richardson algorithm as opposed to gradient descent) and our lower bounds are novel the best of our knowledge.
ICL of Markov chains: A different line of work analyzes the ability of transformers to perform in-context learning over Markov chains on finite state space. The work Nichani et al. [2024] studied this problem for two-layer softmax transformers trained by gradient descent and found that the model learns to predict the next token by inductively reading all previous instances of the current token. This mechanism was referred to as 'induction heads' by an earlier empirical work Olsson et al. [2022]. Several recent works have provided additional thcoretical and numerical evidence suggest that transformers learn to implement induction heads Edelman et al. [2024), Rajaraman et al. [2024),
Chen et al. [2024]. Our problem setting can be viewed as a Markov chain on an infinite state space and is thus beyond the scope of the aforementioned works.
1.2 Organization
The paper is organized as follows. In Section 2, we discuss the details of our problem setup, including the observation model, the transformer architecture, and the loss functions considered herein. In Sections 3.1 and 3.2 we state our theoretical results on the approximation of deep and single-layer transformers respectively. We also discuss the qualitative difference we uncover between in-context learning with IID and non-lID data in Section 3.3
In Section 5 we sketch the proofs of our main
3

---

theorems, and in Section 6 we describe some directions for future work. All proofs are deferred to the appendix; Appendix A provides the proofs for Section Appendix[Bjrrovides the proofs for Section 3.2 and Appendix provides the proofs for various auxiliary lemmas.
2
Set-up
2.1
The observation model
We consider in-context learning of sequences (zo, 21, .1...., .T) C R defined by the noisy linear dynamical system
zp at = WI--1 Ee, IsTST,
where W E W C Raxd and (f are independent noise terms which follow a Gaussian distribution (O0, Ia) for some } denote a probability measure supported on W. A sequence x is then generated according to the two-stage procedure where we I) sample task W ~ pw. and then conditioned on W, sample according to the observation process (2). Our theoretical results are agnostic to the choice of the task distribution Pw and depend only on its support W. To make the analysis more tractable, place the following assumptions on W.
which deseribes the signal-to-noise ratio of the tasks. We let
Assumption 1. There exist constants < Wmin < Wmax < such that
Umin
Ia < W < Wmax Ias VW E W.
The assumption that the eigenvalues of the matrices in W are strictly less than one ensures that the dynamical system defined in Equation (2) is geometrically ergodic, which guarantees the loss functions to be considered have finite limits as T tends to infinity. In contrast, previous works assume that the underlying dynamical system is noiseless, and therefore require that the task matrices have unit norm (c.g., rotation matrices) in order for the dynamics to be non-degenerate; see e.g. [Sander cet al. 20224, Zheng et al. [2024). Note also that Assumption [ does not impose structural constraints such simultaneuus diagonalizability the task matrices.
2.2 Linear transformer architecture
We first recall the construction of linear transformer block. Let (ei....,ee)) be a sequence of tokens. A linear transformer block with attention weights Wp, Wo, Wv, WK and MLP weights W1, W2 maps the sequence (ei,...,ee et) to the sequence (e)) given by
WMLP & + WpW F. W.WW&o
Pt
where E, = (eI,..., e2). Note that each output token é, is a function of only the first t input tokens. For the purpose of our analysis, we simplify the structure of the attention layer by re-parameterizing some of the weight matrices. The simplified linear transformer block has attention weights Wp, Wo and MLP weights W WMLP& and is given by
é = WMLP Wp 1 LeTTeee))
Pr.
Note that from approximation theory point of view, this re-parameterization of the weights does not lose us any expressiveness. In the case of learning the dynamical system defined by Equation (2). the observations ( .1,..., .T) encoded into sequence of tokens (ei,.... eT). which the user has the freedom to specify. We consider the following positional encoding given by e, (0², 0% x "T=1)" Rdd The first rows of the token e, serve as a placeholder for the transformer's prediction for the next token. That is, é is the tth element of the sequence defined by the transformer block, we write De = (s)) for the prediction of Tt++1 We note that similar prompt embedding for autoregressive transformers, which only the first d rows of e, are held as zero, has been studied in several works Von Oswald et al. [202bb), Sander et al. [024)) Zheng et al. 2024). The reason for choosing this specific embedding structure (with zeros in the first 27 entries) will become clear in the proof of Theorem[] We take the normalization factor to be P: = t.

---

A multi-layer linear transformer is then defined simply by composing linear transformer blocks, More precisely, an L-layer transformer parameterized by weights
{ MLP w w E R4dx4d 13
As in the single-layer case, we use the first d rows of the Transformer output of each token D: (Ct) for prediction. Denote by TF2 the class of L-layer linear transformers.
2.3 Training and inference loss functions
Transformers are typically trained to perform in-context learning by minimizing the following auto-regressive training loss
Leaan (0) = (EI...... &r. W)
1 T
Σ
1e x 11
where the transformer learns to predict the next token xz++1 from the previous / tokens. Here, denotes the transformer parameters. the setting where (Z1.....22) .T) follow dynamical system of the form in Equation (2), we emphasize that the transformer is learning to predict the mean of z
conditioned on xe for each E {l....,T T 1}. This follows from the fact that the loss L(0) averages
over the measurement noise. To analyze the in-context learning ability of a given transformer, we define the 1,2 test loss
(o) = sup BE....... [IOT - W a 12 WEW
The test loss admits three key differences from the train loss. First, it measures the difference between the transformer prediction Y/ and the conditional expectation Wx, B[ WI, rather than the difference between Òt and the noisy label Fc+1 used in the training loss. By simple calculation, this is equivalent to defining the loss using the difference between H. and 1 up to an additive factor which depends only on the distribution of the noise. Thus, this change can viewed as a centering of the loss to ensure that the minimum of the test loss tends to zero as T - co. Second, the test loss only measures the error of the transformer prediction the terminal time T. Since the transformer prediction Yt is only function of the first iterates of the dynamical system (ZI,.... Ie). we cannot expect the transformer to make accurate predictions when is small. Third, and perhaps most importantly, the test loss measures the error uniformly over the task set W. This is quite different from the typical L used to measure the prediction error in supervised learning. However, a small given downstream
-ossoss does not provide guarantees the model's 's peerence-time prediction task W E W. In contrast, the uniform loss captures the worst-case robustness the model, similar to the minimax paradigm in nonparametric statistics Giné and Nickl [2021]. Under the interpretation of transformers as algorithms, we therefore view the uniform-in-Wi W loss as natural metric for in-context learning. We note that while the uniform loss is difficult to for training purposes, several works have proven that transformers trained on an I do in fact exhibit inference-tine time guarantees
which hold uniformly over the task space Zhang al. 2023 Yang
20024] Li 20244.
3
Main results
3.1 Approximation error bound for deep linear transformers
Our first theoretical result is upper bound of the approximation error of deep transformers in learning the dynamical system (2) in-context, measured by the test loss 4
Theorem 1. There exists transformer of depth = O(log(T) with parameters such that
LT x log(T)) T
when T is sufficiently large. The implicit constants depend on Wmaxs and d, and the dependence is at most polynomial in d.
Theorem shows that there is a transformer that can closely track the condition mean T increases to infinity. The key idea underlying the proof of Theorem iis to construct a transformer such that, for any dynamical system (Z1,..., IT) according to (2). the transformer prediction 9r approximates
5

---

the least-squares prediction Wx,, where W argminw ; Ei=D || Wx Il is the least-squares estimator. The proof then proceeds by leveraging the statistical properties of the least-squares estimator to achieve the final bound. Implementing the least squares estimator requires computing the matrix vector product X "x, where X. _ s--1 ,zao is the empirical covariance matrix. An important ingredient of the proof of Theorem is the construction of a transformer which unrolls modified Richardson iteration algorithm for solving the linear system X,b I, for X; tx, The convergent guarantees of the Richardson iteration allow to derive quantitative bounds between the transformer prediction and the least- -uuures estimator. We note that the algorithm unrolling idea has been used to prove the approximation power of deep neural networks Chen et al. [202T]. Marwah ct al. [023] for solutions of PDEs. The recent works adopted the unrolling idea for proving the approximation power of transformers for nonlinear regression tasks Bai et al. (2024). The recent paper Von Oswald et al. 2023bb also utilized unrolling of the Richardson's iteration in their construction of a
I
transformer for learning deterministic linear dynamical systems, but did not provide an approximation guarantee for the constructed transformer.
The error achieved by the deep transformer constructed in Theorem | decays at the parametric rate O (1/T), up to logarithmic factor. This not surprising, as our proof strategy constructs a transformer which (approximately) implements parametric estimator. Theorem aalso shows that the depth of the transformer needed to achieve this rate only logarithmic the sequence length T, owed to the fast convergence of the Richardson iteration. Interestingly, the recent work Yüksel et al. 2024) studies statistical guarantees of the least-squares predictor for long-context problems, and their results could be potentially leveraged to generalize our approximation results to long-context systems. We leave this extension to future work.
3.2 A lower bound for single-layer transformers
While it is beyond the scope of this paper to characterize whether (llo((T) depth is necessary for in-context learning dynamical systems, we provide an analysis for the (limited) approximation power of single-layer transformers. To be concrete, we focus on in-context learning of the one-dimensional dynamical system
Ft w + Ees I. (1....,T).
Eu = 0,
where & N (0, 0²) and [Wminn Wmax To make our analysis tractable, we fix some of the parameters the single-layer transformer: afterwards, we discuss how our results might be extended to the general case. First, we fix the MLP weight matrix W WMLP to be the d d identity matrix. The resulting architecture is often referred to as a linear attention block and has been the study of a lot of recent research Zhang al. [2023). Mahankali et al. [2023). Zheng et al. [2024) ZZhag et al. 2024 In the 1D setting, a linear attention block defines an estimator yr for TT+1 given by
1 Te - 7 (p p2) (
E
(1
912
En
421
(22
FT-
where pr R and 4ú E R are the learnable parameters. Since we know that E[ 1 |ro. T1..... linear function of zt, it is natural to zero out the parameters that lead De being a linear combination of both 2; and xt-1. This motivates us to further set q12 922 0, leading to the simplified parameterization
1 1TT Tr = -
i= o
Σ
TT,
I-Ti-1
where p (Pr P2 and (91 (2) We note that a similar parametrization was also adopted in Zheng al. 2024 and was proven that single layer of aully-paramtterized linear attention trained on gradient flow of the 1,2 loss will converge to a parameterization where only P21 and q are nonzero. In the one-dimensional setting, the test loss introduced in Subsection 2.3 becomes
Lp q) = (ūr 2
Our aim is to understand how the approximation error inf p.q LT(p, q) behaves as function of T. Specifically, we shall show that inf p.q (PT = 2(1) as T + oo, from which we conclude that the single-layer transformer induces an irreducible approximation error, indicating that it is

---

insufficient in learning the linear dynamical system. To this end, we first express the test loss function as (r(p. q) B[e(p, q. w)]. where the individual loss is defined
(p. q. w) = (vr wrr)
The following lemma characterizes the limiting behavior of the individual loss as T - 00. Proposition 1. The individual loss function converges pointwise on IP? x IR? [Wmins Wmax] to a limiting function E(p, q. w) defined by
0²
0² (wa) + a2) - w
P(p.. 1- w²
11
where 01 P192 + P2 and 02 p" q. Moreover, l satisfies the lower bound
inf P.qER*
sup
q(p.9,00 C(o², (Wnin Wmax)
wel Weaann [max]
where C(o², Wmin: Wmaxx) i strictly positive constant depending only on 0², Wmin; and Wmnax-
The proof of the formula for {(p, q, w) follows from a careful computation of the expectations study the behavior of the
defining the test loss. The upshot of Proposition i that it allows minimum value of the test loss LT as the sequence length tends to infinity. In particular, we can translate the lower bound in Proposition D into lower bound on the test loss in the limit T co. This is the content of our main theoretical result in this section, which we state below.
Theorem 2. For any R > 0, the limit limy- inf [plllllll (p q) exists, and
lim T ||plllaalls
inf Lr(p,g) 2 C(o², Wmin Wmax).
where C(o², Wming Wmax) > is the constant from Proposition
7
For technical reasons, must constrain attention parameters p. q lie in a ball of radius R for Theorem 2 It is common in deep learning that model parameters are constrained either by explicit or implicit regularization. Note, however, that the constant in the lower bound of Theorem is independent of R, so R can be arbitrarily large.
Theorem shows that single layer of linear attention is unable to accurately capture the dynamics defined by the system (5). To the best of our knowledge, Theorem 2 provides the first lower bound for in-context learning of dynamical systems, and it suggests that some care is required in choosing an appropriate architecture in this setting. While our results in this section are stated for ID dynamical systems, we expect that the results generalize to arbitrary dimensions. For illustrative purposes, let us consider a d- d-dimensional dynamical system (æ1, PT) according to Equation (2) where the task matrix W E dR diagonal. Then, since the noise is isotropic, this is equivalent to specifying a system of d independent 1D dynamical systems of the form in Equation (5). We therefore expect that in-context learning a muuli-diimensionll dynamical system is at least as difficult as in-context learning system of ID dynamical, for which we have lower bounds. We leave it to future work to rigorously generalize Theorem 2 to higher dimensions.
In addition, we expect that the non-zero lower bound on the limiting loss can be extended to general single layer parameters (i.e., fully parameterized attention with an MLP matrix). At high level, the result in Proposition [ follows from the fact that {(p, w) is polynomial in the parameters, but a non-polynomial function in w (in particular, depends on (1 - - Since this is still the case if we consider a fully-parametent expect an analogous result to hold for general single-layer linear transformers. However, the explicit computation of the limiting loss is more complicated, and we leave it as interesting avenue for future work to justify this rigorously.
single-layer linear transformer with an MLP matrix, we
3.3 Comparing in-context learning over III vs non-IID data:
Our theoretical results hold for non-independent data generated according to a dynamical system. A more common setting for theoretical analysis is the in-context learning IID data, where model, given prompt of independent observations ((11, f(I))..... ..., (IT, f(T))) of some unseen task
7

---

and an unlabeled query point 47+11, is asked to predict the new label f(rr+1). Several recent works Zhang et al. [2023] Ahn al. [023). Mahankali et al. [2023] have analyzed this problem when the task / is given by linear map f() (w', 2). In this case, it has been shown that a single layer of linear attention can achieve test error in the limit 7 - 0o, even when the loss is measured by the uniform norm on the task space. In contrast, we have shown in Theorem 2 for an analogous problem involving non-lID data, that a single layer of linear attention can never achieve zero test loss in the large sample limit. The intuitive explanation for such a discrepancy can be understood as follows. In the IID setting, has been shown that the optimal parameterization Specifically, Zhang et al. 2023] shows that a block of the optimal attention matrix Wa learns to invert the covariance matrix Cov(Px). which independent of the task vector w E IR For dynamical systems given by Equation (2). this construction fails to perform in-context learning because the covariate distribution depends on the task matrix W. This indicates that transformers may have more difficulty performing in-context learning non-IID data compared to IID data.
linear attention
layer depends on the distribution Px of the covariates { {.1, ........ Fr)
2T)
4 Numerical experiments
We train transformers of varying depth in-context learn noisy one-dimensional linear dynamical systems of the form (2), and we plot the test error of the trained transformers (as measured by the L norm over both {2x] and the task u) with T 500 and [mmin Wmax] = [0, 0.8] as a function of the number of epochs. The results are displayed in Figure I Both softmax and linear transformers exhibit clear separation between their optimal test loss depth L and L 2 2, which supports Theorem 2 For softmax transformers, the optimal test loss continues to decrease For linear transformers, the optimal loss is approximately the same at I, 2, 3, 4, 5, and it difficult to say whether this is due to the capacity of deep linear transformers, or simply manifestation of optimization error. Our experiments with linear transformers suggest that our result in Theorem I may be sup-optimal, and that there may exist transformer with constant depth which achieves vanishing test loss. On the other hand, our results on softmax transformers suggest that increasing depth beyond L = 2 improves the test error; this is in contrast to empirical findings for discrete
In this section, we present numerical experiments to validate the claims of Theorems 1 and 2
function of depth up to 7, 5.
Markov chains Olsson et al. 2022], where an induction head emerges at depth
attendior
attention
107
10
10
10:3
10a4
10
Figure 1: Test error as function of training epochs, with 500, [Wmin: Wmax] = [0,0.8) and various values of L
Proof sketches
5.1 Proof sketch for Theorem
As noted in Section 3.1 our proof of Theorem Ieverages algorithm unrolling, powerful technique for proving approximation error bounds whereby a deep model encodes learning algorithm, with each layer of the model corresponding to an iteration the algorithm. Specifically, we use transformer to unroll the least-squares algorithm, which approximates the matrix W defining the

---

dynamical system define in Equation
given the history up to time T by
1 Σ
(+
WT = argminw T
I Woil' 1
Ita
Given the history of the dynamical system (zo..... Zr) up to time T, the goal of the transformer is to predict the conditional expectation E|rr41|0r] = Way pT. In light of the discussion above natural estimator for TT+1 is Wr. Let XT = 2 x denote the sample covariance matrix of the dynamical system, and assume for the moment that Xr invertible. Note that computing Wrxr requires one to find vector 27 such that X7 2T = 2T, or XT = 2T. A classical iterative method for solving linear systems of this form is the modified Richardson iteration. Given linear system Ax b, the modified Richardson iteration with step size a > 0 approximates the solution by the update rule (e) = (Ig - (1) + ab. A key technical lemma in proving Theorem I constructs a transformer which approximates the least-squares prediction WrTT by unrolling the modified Richardson iteration. Let us denote by Zr,L the 1 step of the modified Richardson iteration
2T, (Ia aXT)2T + OTT, 8 0
2r,0 0.
We state the result precisely below. Lemma For any positive integer and a > O, there exists an 1)-laye transformer with parameters 0" {W MT.P: w w Jt=1 such that for any dynamical system (No, ;
defined by ( 0 maps the sequence (e1, .......,c eT) defined by Equation ( to sequence (e1...., ,T)
where, for each 1 TT
T=:= (G)
Σ Bi+12 L.
In other words, there exists a transformer which estimates IT+1 by 1) approximating the matrix- vector product XT TT via the Richardson iteration, and 2) using the approximation to Xxp xT to compute approximation to the least-squares prediction Tr+1 for 2T+11
To translate Lemma 1 into a bound on the test loss (0),,, there are several technical hurdles. First, in order for the least-squares estimator to be well-defined, the sample covariance matrix 2T must be invertible. In this case, if we hope to obtain any quantitative bounds, we need upper bounds on the condition number of the sample covariance (which governs the rate of convergence of the modified Richardson iteration) and estimates on the statistical performance of the least-squares estimator. To this end, we apply results from Foster et al. [2020] and Matni and Tu [2019]. which provide high-prold probabirbay guarantees on the condition number XT and the covariance and the discrepancy
||W,- WI|, respectively. If we let A denote the event on which these hold (see precise definition Appendix A). then, for fixed W W, we can bound the L of the transformer by
E [10. - W 1rll?
<
2E
De W 1A] + 2E
|1K0
Wxr) 1Ae
On the event A, can bound the expectation further by
|10 - Warl 1A] <
2
De
Wrer
A +
2F
[| W
oT A
The first term above can be bounded by leveraging the convergence rate of the modified Richardson iteration, while the second term can be bounded by applying the bound on ||Wr- W||. The two terms can be balanced by choosing the step size as an appropriate function of T. When I. = Ologg()). this
yields a bound of O log(T) To bound the expectation on A, we can apply the Cauchy-Schwartz inequality
E
[
WxT) I1 1 < E | Wo 1(AA)1/2
can There is some care required to handle this term, because, away from the event A the norm of can grow with the step size L, which could potentially offset the decay of P (AA))//² In Lemma 11 in

---

Appendix C we bound the moments of the Richardson iterate LT which allows us to prove that the
above term is O [T)(T))
when L = (llog(T)). This proves that E |l0. - W Wzrl" |
= 0 [og(T)
T
for each W E W, and taking the supremum over W gives the result of Theorem See Appendix for the detailed proof.
A
5.2 Proof sketch for Theorem 2
great deal of the technical work in proving Theorem lies in computing the limit of the individual loss function in Lemma
o²
2
lim é (P(p.q.0) == E(p. q. w) T-000
(wa) + 022) w
-- w²
2
where 01 - P2 + P241 and 02 p²qq. Since these computations are cumbersome, we defer them to the Appendix (see Appendix B and also Appendix [ proofs of auxiliary moment computations). lengthy sum of many different terms,
While the closed form expression for (p q. w) the ergodicity of the dynamical system ensures that only a few terms survive in the limit; this an important theme of our computations. Once this formula established, the lower bound E(P, 9, w) stated in Lemma [ can be argued as follows: for any finite
on inf p.q collection (Wi,..., WK) E [Wmin: Wmax], we have the lower bound
d²
(102
0²
2
inf P.d WE E//mmm Wimax]
sup
((p.q. w) >
inf max 01 Isisk 1 m (1 (w;a) + a2) u0
In other words, we replace the infimum over P.q E R with the infimum over all a 022 R
and we replace the supremum over [Wmin; Wmax] with a finite maximum. The infimum is attained
at pair (aj, .a)) at which the graphs of a subset of the K curves intersects (see Equation (20)
in Appendix [ for details here). For appropriately chosen wi; wk. it can be shown that this infimum is equal to zero if and only if W1..... WK solve certain linear system. The lower bound
then follows from recognizing that the system is inconsistent. Once the lower bound in Lemma | is proven, Theorem 2 can be proven by using the regularity of the family of individual loss functions {pp q, w) + f P. q. w to interchange limits and suprema/infima.
Conclusion and discussion
We studied the approximation power of transformers for performing in-context learning data arising from linear dynamical systems. For multilayer transformers, we showed that logarithmic depth is sufficient achieve fast decay of the test loss as the context length tends to infinity. Conversely, we proved a lower bound for single-layer linear transformers which suggest their incapability of learning such dynamical systems in-context. We also provided numerical results that confirmed the benefits of increasing the depth of the transformer in improving the prediction performance. There are several important directions for future research. First, would like better understand the apparent depth-separation observed in this paper. In particular, it remains to be determined whether there is transformer with O(1) depth whose test loss vanishes the sequence T + oc. If this question can be answered affirmatively, we would also like to describe the opssaioptiiiztiion algorithm that such a transformer encodes. Second, it would be interesting to generalize the analysis of this paper to nonlinear dynamical systems. We anticipate the the unrolling idea may still be effective, but carrying this out is highly non-trivial as the equare estimator does not admit a closed form in the nonlinear setting. Finally, although this paper focused on the approximation only, it remains an open question to investigate whether the transformers trained on in-context examples of the linear dynamical system (2) can in-context learn the dynamical system, in the sense of the uniform loss in Equation 4 We leave these various problems future work.
7
Acknowledgment
YL thanks the support from the NSF CAREER Award DMS-2442463 and the support from the Data Science Initiative University of Minnesota through MnDRIVE DSI Seed Grant. The authors thank Shaurya Sehgal for sharing his codes used to produce preliminary numerical results.
10

---

References
J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt,
S. Altman, S. Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
K. Ahn, X. Cheng, H. Daneshmand, and S. Sra. Transformers learn implement preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36: 45614-45650, 2023.
U. Akram and H. Vikalo. Can transformers in-context learn behavior a linear dynamical system? arXiv preprint arXiv:2410.16544 2024.
E. Akyürek, D. Schuurmans, J. Andreas, Ma, and D. Zhou. What learning algorithm in-context learning? investigations with linear models. arXiv preprint 1rXiv:2211.15661 2022.
U. Anwar, J. Von Oswald, L. Kirsch, D. Krueger, and S. Frei. Adversarial robustness of in-context learning in transformers for linear regression. arXiv preprint arXiv:2411.05/89 2024.
Y. Bai, F. Chen, H. Wang, C. Xiong, and S. Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems, 36, 2024.
I. Batatia, P. Benner, Y. Chiang, A. M. Elena, D. P. Kováes, J. Riebesell, X. R. Advincula, M. Asta, M. Avaylon, W. J. Baldwin, et al. A foundation model for atomistic materials chemistry. arXiv preprint 240002401.00006 2023.
M. Chen, A. Radford, R. Child, J. Wu, H. Jun, D. Luan, and Sutskever. Generative pretraining from pixels. In International conference on machine learning, pages 1691-1703, PMLR, 2020.
S. Chen, H. Sheen, T. Wang, and Yang. Unveiling induction heads: Provable training dynamics and feature learning in transformers. arXiv preprint arXiv:2409. 105599 2024.
Z. Chen, J. Lu, and Y. Lu. On the representation of solutions elliptic pdes in barron spaces. Advances in neural information processing systems, 34:6454-6465, 2021.
S. R. Choi and M. Lee. Transformer architecture and attention mechanisms in genome data analysis: comprehensive review. Biology, 12(7):1033, 2023.
Cole, Y. Lu, R. O'Neill, and T. Zhang. Provable in-context learning of linear systems and linear elliptic pdes with transformers. arXiv preprint arXh::2409.12290 2024.
L. Collins, A. Parulekar, A. Mokhtari, S. Sanghavi, and S. Shakkottai. In-context learning with transformers: Softmax attention adapts to function lipschitzness. arXiv preprint arXiv:2402.11633 2024.
D. Dai, Y. Sun, L. Dong, Y. Hao, S. Ma, Z. Sui, and F. Wei. Why can gpt learn in-context? language models implicitly perform gradient descent as meta-optimizers, arXiv preprint arXiv:2212.1055, 2022.
B. L. Edelman, E. Edelman, S. Goel, E. Malach, and N. Tsilivis. The evolution of statistical induction heads: In-context learning markov chains. arXiv preprint arXiv:2402. 1004, 2024.
G. B. Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
D. Foster, T. Sarkar, and A. Rakhlin. Learning nonlinear dynamical systems from a single trajectory. In Learning for Dynamics and Control, pages 851-8611 PMLR, 2020.
D. Fu, T.-Q. Chen, R. Jia, and V. Sharan. Transformers learn higher-order optimization methods for in-context learning: A study with linear models. arXiv preprint arXiv:2310. /7086, 2023.
S. Garg, D. Tsipras, P. S. Liang, and G. Valiant. What can transformers learn in-context? a case study of simple function classes. Advances Neural Information Processing Systems, 35:30583-30598, 2022.

---

A. Giannou, L. Yang, T. Wang. D. Papailiopoulos, and J. D. Lee. How well can transformers emulate in-context newton's method? arXiv preprint arXiv:2403.03183, 2024.
E. Giné and R. Nickl. fouttmtaaacaluundttiiiii of finfnite-dimensione statistical models. Cambridge university press, 2021.
G. Goel and Bartlett. Can transformer represent a kalman filter? In 6th Annual Learning for Dynamics & Control Conference, pages 1002-112.. PMLR, 2024.
T. Guo, W. Hu, S. Mci, H. Wang, C. Xiong, S. Savarese, and Y. Bai. How do transformers learn in-context beyond simple functions? a case study on learning with representations. arXiv preprint arXiv:2310. 10616, 2023.
R. Huang, Y. Liang, and Yang. Non-asymptotic convergence of training transformers for next-token prediction. Advances in Neural Information Processing Systems, 18886644-06733 2024.
J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool,
R. Bates, A. Zídek, A. Potapenko, et al. Highly accurate protein structure prediction with alphafold. nature, 596(7873):583-58) 2021.
S. Khan, M. Nascer, M. Hayat, S. W. Zamir, F. S. Khan, and M. Shah. Transformers in vision: A survey. ACM computing surveys (CSUR), 54(105): 2022.
Kim and T. Suzuki. Transformers learn nonlinear features in context: Nonconvex mean-field dynamics on the attention landscape. arXiv preprint arXivv2402.01255, 2024.
J. Kim, T. Nakamaki, and T. Suzuki. Transformers are minimax optimal nonparametric in-context learners. arXiv preprint arXiv:2408. 12186, 2024.
G. Li, Y. Jiao, Y. Huang, Y. Wei, and Y. Chen. Transformers meet in-context learning: A universal approximation theory. arXiv preprint 2Xiv:25566.020000 2025.
Y. Li, M. E. Ildiz, D. Papailiopoulos, and S. Oymak. Transformers as algorithms: Generalization and stability in in-context learning. In International Conference on Machine Learning, pages 19565-19594. PMLR, 2023.
Z. Li, Y. Cao, C. Gao, Y. He, H. Liu, J. M. Klusowski, J. Fan, and M. Wang. One-layer transformer provably learns one-nearest neighbor in context. arXiv preprint arXiv:2411.18800, 2024.
Y. M. Lu, M. Letey, J. A. Zavatone- Veth, Maiti, and C. Pehlevan. Asymptotic theory of in-context learning by linear attention. arXiv preprint arXiv:2405. 1755,, 2024.
A. Mahankali, T. B. Hashimoto, and T. Ma. One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. arXiv preprint arXiv:2307.0335 2023.
T. Marwah, Z. C. Lipton, J. Lu, and A. Risteski. Neural network approximations of pdes beyond linearity: A representational perspective. International Conference on Machine Learning, pages 241722 PMLR, 2023.
N. Matni and S. Tu. A tutorial concentration bounds for system identification. In 2019 JEEE 58th conference on decision and control (CDC), pages 3741-3749. IEEE, 2019.
M. McCabe, B. R.-S. Blancard, L. H. Parker, R. Ohana, M. Cranmer, A. Bietti, M. Eickenberg, S. Golkar, G. Krawezik, F. Lanusse, et al. Multiple physics pretraining for physical surrogate models. arXiv preprint arXiv:2310.02994 2023.
S. Müller, N. Hollmann, S. P. Arango, J. Grabocka, and F. Hutter. Transformers can do bayesian inference. arXiv preprint arXiv:2112. 2021.
E. Nichani, A. Damian, and J. D. Lee. How transformers learn causal structure with gradient descent. arXiv preprint 402. 2024.
C. Olsson, N. Elhage, Nanda, Joseph, N. DasSarma, T. Henighan, B. Mann, A. Askell, Bai,
A. Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209, 11895, 2022.
12

---

N. Rajaraman, M. Bondaschi, A. V. Makkuva, K. Ramchandran, and M. Gastpar. Transformers on markov data: Constant depth suffices. Advances in Neural Information Processing Systems, 37: 1375211133556, 2024.
A. Ramesh, M. Pavlov, G. Goh, S. Gray, C. Voss, A. Radford, M. Chen, and I. Sutskever. Zero-shot text-to-image generation. In International conference on machine learning, pages 8821-8831. Pmlr, 2021.
M. E. Sander, R. Giryes, T. Suzuki, M. Blondel, and G. Peyré. How do transformers perform in-context autoregressive learning? arXiv preprint arXiv:2402.05787 2024.
I. R. Shafarevich and A. O. Remizov. Linear algebra and geometry. Springer Science & Business Media, 2012.
Subramanian, P. Harrington, K. Keutzer, W. Bhimji, D. Morozov, M. W. Mahoney, and A. Gholami. Towards foundation models for scientific machine learning: Characterizing scaling and transfer behavior. Advances in Neural Information Processing Systems, 36, 2024.
R. Varga. Iterative matrix analysis. Englewood Cliffs, NJ, 1962.
A. Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
R. Vershynin. High--dimensoonl probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
M. Vladymyrov, J. Von Oswald, M. Sandler, and R. Ge. Linear transformers are versatile in-context learners. arXiv preprint arXiv:2402. 180, 2024.
J. Von Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, and M. Vladymyrov. Transformers learn in-context by gradient descent. International Conference on Machine Learning, pages 35151-35174 PMLR, 2023a.
J. Von Oswald, M. Schlegel, A. Meulemans, S. Kobayashi, E. Niklasson, N. Zucchet, N. Scherrer, N. Miller, M. Sandler, M. Vladymyrov, et al. Uncovering mesa-optimization algorithms in transformers. arXiv preprint
2023b.
M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
D. Wu, Y. He, Cao, J. Fan, and H. Liu, Transformers and their roles as time series foundation models. arXiv preprint arXiv:2502.03388, 2025.
Wu, D. Zou, Z. Chen, V. Braverman, Q Gu, and P. L. Bartlett. How many pretraining tasks needed for in-context learning of linear regression? arXiv preprint arXiv:2310008391, 2023.
T. Yang, Y. Huang, Y. Liang and Y. Chi. In-context learning with representations: Contextual generalization of trained transformers. arXiv preprint arXiv:2408. 10147, 2024.
Z. Ye, Huang, Chen, H. Liu, Wang, and B. Dong. Pdeformer: Towards a foundation model for one-dimensional partial differential equations. arXiv preprint arXiv:2402.12652 2024.
O. K. Yüksel, M. Even, and N. Flammarion. Long-context linear system identification. arXiv preprint arXiv:2410.05690, 2024.
R. Zhang, S. Frei, and P. L. Bartlett. Trained transformers learn linear models in-context. arXiv preprint arXiv:2306.0900 2023.
R. Zhang, J. Wu, and L. Bartlett. In-context learning of linear transformer block: benefits of the mlp component and one-step gd initialization. arXiv preprint arXiv:2402.1495) 2024.
C. Zheng, W. Huang, R. Wang, G. Wa, J. Zhu, and C. Li. On mesa-optimizztion in autoregressively trained transformers: Emergence and capability. arXiv preprint arXivv2405.16845 2024.
I. Ziemann, Matni, and Pappas. State space models, emergence, and ergodicity: How many parameters needed for stable predictions? arXiv preprint 23X11 2024. 2024.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claims are clearly stated in the abstract, explicated greater detail in the introduction, and stated precisely in Theorems 000.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes].
The scope of our paper is limited to in-context learning of linear dynamical systems by linear attention, and our lower bound limited to the set of single layer transformers. These limitations are further discussed in the main paper.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: Our assumptions are clearly stated in the main paper, and the rigorous proofs are fully developed in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: Our paper does not include experiments (since our focus is on learning theory), this item is not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Our paper does not include experiments (since focus is learning theory), so this item is not applicable.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.co
Pooliic/guides/Coeeeuubiiis ott.eeeesuumiisioooooooooooo for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wttpcccpppppppcueeeeeeeeepepeeee
ssissssliccyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper does not include experiments (since our focus is on learning theory), so this item is not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Our paper does not include experiments (since our focus is on learning theory). so this item is not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not include experiments (since focus is learning theory), so this item is not applicable.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't i make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our work indeed conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction)
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our paper helps understand the transformer architecture from foundational point of view and may inspire further research in this area. Beyond that, the societal impacts are insignificant.
Guidelines:
17

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does pose such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our paper doesn't 't use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing experiments research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve study participants; no such risk is posed.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: LLMs were used for any important, original, or non-standard component of the core methods of our research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
20

---

A Proofs for Section 3.1
We recall some notation from Section 5.1 We Xy 7 Er= c.oe denote the sample covariance
matrix of the dynamical system and Wr denote the least-squares estimator of the dynamical system given by
T-1 Σ
W. argmin W
8441 Wx,ll
3 1
77)
T
We let 2T,4 be defined by the modified Richardson iteration
2T,1 2T,1-1 + (xT XTTT,L-1), L>0 0 21,0 = 0.
(8)
We make use of the following classical result on the convergence of the modified Richardson iteration.
Lemma 2. (Richardson iteration, Varga [9622]] Assume that the matrix A Rddd is invertible
let >> O be small enough that that La aAAllop < 1. Let I, E Rd denote the solution to the equation Ax b and let T(k) denote the vector obtained at the tt step of Richardson iteration with initialization Zn = 0. Then Fkk takes the explicit form
(R) = (Ia - (Ls - -aA)*) Ix.
and consequently, the error bound
||=, I(N)ll |1l & [[ aA112/1
holds for all k.
In particular, Lemma 2 shows that the modified Richardson iterates converge to the true solution of the linear system at an exponential rate. For a fixed matrix A, the optimal step size a depends on the smallest and largest eigenvalues of A.
We are interested in constructing transformer which approximately implements the least-squares prediction WTZT to estimate #T+1- In order to approximate the term Xx appearing in the expression for WTZT, to solve a related linear system. Here, depth plays a crucial role, as each layer of the transformer represents step of the modified Richardson iteration. Our result is stated precisely in Lemma in We now present the proof of this result.
design transformer which unrolls the modified Richardson iteration
Section 5.1
Proof of Lemma Step 1: Let dl,...., uT, bi..... br. E Rdd denote fixed vectors. We first show that for any sequence of tokens (ei,... ex) where = (ae, br, vt, 1t-1) there exists single layer transformer which maps the sequence (eI,..., .a.....,e7 (TT to (e,,..., ET), where
a: a(; a.,aa))
b + a(x - X,b,))
E
Ft
Tt-1
In words, there exists a single-layer transformer block which simultancously implements one step of the Richardson iteration for x -;-1 = initialized at a, and b, with step size a. To prove this, let first define the attention weights by
0 I
0
0
0
L
R
4dx4d
Wq
0
R 1d
0
0
0
0
0
ooa
0
21

---

Then we have
ai
0
0
bj
0
0
ae
Wp E,ET Woe=
(0
by
i=1
Ti-1
0
0
0
Ce It-1
Ti-1
Fi-1
o
0
02)
2
03
1
at
03;
0
b;
0
0
Jtc
axia
axb
0
0
It follows that
at aXia
b aXb
e Wp E.E. Woe
It I1-1
Now, let W WLLP Ridxi be any matrix such that
at
aX,a b. aX,b Ft
a + a(x - xxaa)
by alxt X,be)
W MMLP
Ft
Tt-1
x--1
Then the transformer block with weights WMLP, Wp, Wo maps et to
ê WMLP
(e, Wp E,E," WQee)
(tt aXae b aXib Ft
WMLP
It-1
0; + a(x; - X(at)
b, a(T;=
X,b:)
Ht
T1-1
Step 2: By composing the transformer blocks from Step 1, we have shown that there exists L-lerrr
0
0
transformer which maps the token e,
to the token
Ft-1
Zt
(L)
Zt,L
2'
1t-1--/
where 2,, Richardson iterate defined in Equation (
Step 3: We now show that for any sequence of tokens (e1, (ei,...,er) eT) with e; (a,, ai 2;,
there exists single layer transformer block which maps (ci,..., er) to (ei,..., @r), where
t-1
(er) =
Σ 1141
de.
i=0
22

---

To prove this, we use a similar construction to that in Step 1. Let us first define attention weights by
0
0
0
0
0
0
WP
We
0
0
0
0
0
0
0
0
Then we have
1a
a4
0
T
0
Wp- F. Ewe
0
0000
04
0
0
0
de
24
22
0
0
0
1=1
T1-1
24-1
La
0
0
27
100
0
(x
0"
0²)
a1
0
Tt-1
E
1++1
2
a
0
000
It follows that
( x4
at
Et + Wp E,ET Ewe,-
a2
3t xt-1
We then define W WMLP to be any matrix such that It then follows that, for ē = WMLP (et + Wp E.E.. Woe)). we have
1a+t +
(+ EL
Tー- at
WMLP
a2
Σ
ac
Dt xt-1
1:d
1-1
(2)12dd =
Σ Dit1o?
ar.
Step 4: To conclude the proof, we compose the L-layer transformer constructed in step 2 with the single-layer transformer constructed in step to construct an (L + 1)-layer transformer which realizes the mapping
( (+ I++ 12?
L layers from Step
Zt,L
Single layer from Step 3
Z
Z
et
Jt
[I--1
Fr-1
where * denotes entries which are not used in prediction. Since Te = (+ Et- Ei=o0itt mit1 this proves the desired claim.
Before proving Theorem we need to state some technical results about the dynamical system in Equation (2) and the least-squares estimator for its state matrix. First, we need bounds on the smallest and largest eigenvalues of the covariance matrix Xy. Such bounds are necessary for our proof, because the least squares estimator not even well-defined unless the covariance is invertible, and in this case the condition number of X, governs the convergence rate of the associated Richardson
iteration. To this end, we quote the following result from Foster et al. 2020 Note that we have adapted the original result to our setting.
23

---

Lemma 3. Foster et al. [2020], Theorem 1] Let (Z1....,II) be generated according to Equa- 0 such that, for any 0, as long as
tion
Then there a numerical constant c
log 6 T 2 cd max
1) we have
2² I
4
La
4
(1 w max
with probability at least 6. In particular, as long T is sufficiently large, the bound in Equation
( holds with probability 27
The second technical result, due to Matni and Tu 2019], provides high-probability bound for the error of the least-squares estimator. This is crucial bounding the test error achieved by the transformer constructed in Lemma
Lemma (Manni and Tu (019), Theorem 4.2). Let (1......... F4) denote the dynamical system
described by Equation 2 and let W, denote the least-squares estimator 7 for the state matrix W.
Then there exists a universal constant e such that whenever T 2 1-Wmax
calog(d/6) log (1
20²
we
have
~ 0 oddlog(d/5)
E W WT
T(1 - w
with probability at least 1 - 5. In particular, as long as T is sufficiently large, we have
E W
1
o² (log (T) log(Ad))
(10)
T(1 w
with probability at least
274
We now give the proof of Theorem
Proof of Theorem 7
We let fr denote the prediction of the (L + 1)-layer transformer constructed in
Lemma] 1 where the step size a E (0, 1) is independent of T and L and will be specified to satisfy some constraints later in the proof. Let Ar denote the event on which the bounds in Equations (9) and (10) hold, and assume that T is sufficiently large that
P (AA) 2
7
We can now write
E l Wxrll
= (0r Wrr) (1Ar - 11g)11
< 2E (0T - Wxr) LAz - 2E ( Wxr) LA
On the event Ar, the least-squares estimator Wy is well-defined, above by
bound the first expectation
E 1T Wxr) lay $
2E
Ser-Wrar) LAT
2E (wr w) or LAz 1|2
For the first term, recall that the transformer prediction Fr can be written as
T-1
Dr
Σ
2T,L.
1=0
where 2T.1. z. the th iterate of the Richardson method defined in Equation 8 In particular, Lemma implies that
|| Xx. xr IL a 1p 2 xr|]
Now, notice that axXllap = max (l ammax (XT)) Amin (Xr))) Since Amax (Xr) and Amin (Xr) are bounded on Ar according to Equation (9). we can choose a depending only on d, o², and Wmax to ensure that [|L. aXT lop Cn for some constant Co (0, 1) whenever Ar holds. In particular, if we set
8(1 2
a 22 (16d + (1 2
max
max
24

---

then Equation implies that
Ca (1
4(1 w max)
16d + (1 w max
and || aXrll I ca on Ar. In turn, this allows us to bound
E ür WrAT) LAT
=E
(ET.L - 1x-xx 2T) 1AT
T
21
1
1
Σ
||x ||x
1lop
T
16
2L
E
Σ
|
1Ar
T
where we used that || 1lop S ot
on Ar. This gives the final bound
16 M,
[r Wyrr) LAr
21 ca
(11)
where we have defined
M1 M, Wamax
sup E
1++1
T
x 1
T
up
Since the dynamical system is geometrically ergodic, the constant M 1, is finite and depends only on o², Wmax: and (the techniques of Lemma 10 Appendix used to bound M1, wmax by the sixth moment of an appropriate Gaussian). To bound the difference between WT and W, we use Lemma 4 which gives the bound
2E ( Wwr
w) xT LAy
2 x
0² (log(T) log(4d)
B[1
(12)
T(1 w w do (Iog(T) log(4d))
(13)
T(1 w w )
where we used Lemma to bound |[[| We bound the expectation on As. by the Cauchy- Schwarz inequality:
1/2
W xT) Lag
$ E
1r
War
P((AF)
<
[BI
Pr
+ E 1)
1/2 P(ATT)
1/2
T-1
d(d + 2)(r
2
E
2141
21,L
+ (1 w " )2
PPAA9)
T
v d(d 2)
2
M2.0
Ell M 11
P(A79)
w wax
where
1/4
M2. sup E
Σ
Iia
1=0
a constant depending only on o, Wmax. and d. By Lemma 11 as long as a is small enough that
2(1 - w ? we have the following bound for 2T.L
E ElZT,1 11 (1 (1+ 1 + 2(1-1) (16(L-1))1 11)1!/A)
25

---

Note also that P(44) = 0 3) This gives the bound
E [| WxT) LAs 112 M2na (1+ La 7--(((11)) (16(L (1)(4-1))!/0)
do²
+
T
wh
(14)
Combining Equations
and 14 we have the final bound
16 S
co d (log(T)) ) + (og(4d))
E l - War
M1,a,waax
(15)
T(1 w )2 T ++ 2(1-1), (16(L - 1))1
do²
M2 Wmax
T T-
max
(16)
To balance the error between L and T, set
(Tg(T) + log or M1 W.r
2 llg(11/c)
Then it is clear that, when T is sufficiently large, the bound
do2
(1)g(T)
(log(T)
M2.0, Wimee (1+ (16(6 (1)1(11))!(1))
r-2 r===0 =0=00
2
T
max
holds. This proves the final bound
log(T) T
Warll
(17)
for T sufficiently large. The implicit constants depend on σ, Wmax and Moreover, by tracking the implicit constants it can be seen that they depend only polynomially on d. Since the test loss is defined as
La (0) = sup E l
Wz 1
WEW
the bound on Lr as stated in Theorem follows from taking the supremum over W on both sides of Equation 17
B Proofs for Section 3.2
We break up the proof Lemma up into two separate lemmas. The first lemma, stated below, proves formula for the pointwise limit of the individual loss function. The second lemma then proves the lower bound satisfied by the limiting loss. The proof of the first lemma involves several computations involving second, fourth, and sixth moments of the linear dynamical system. The proofs of these technical computations are deferred to Appendix
Lemma 5. Consider the individual loss function
Cr(p.q:)) (ūT WIT)²
where p. q are the parameters of the linear attention block and w E [[mins Wmaxl specifies the dynamical system defined by Equation (5). Then for any p.q IR² and (0, we have
o²
2
lim (p qi w) T-000
(wa) + +22) + ww = = w),
1 - w²
1 1- w
where P102 + p2 and 0:2 P1 + P242.
Proof. We recall the formula for Te:
Σ (p1 P2)
- x 1:34-1
E 23 Σi=1 x2
91
TT
rT.
42
We aim to compute the limit of the expression
E(ÿr wrr) )
E + o E
2w E(prTT
(18)
26

---

Step 1: We first compute B|
By Lemma 8 2T
N
(0,021=²²
We therefore have
x²
lim
(19)
T-000
w²
Step 2: Next, we compute E[yrar]] From the formula 0r, we have
T
T
T
yr = Pi9i
Σ
+
P292
TTT
+ (p192 + p291)
7
T
1=1
By Lemma 9 we have
T
T Σ T
T
lim ØTeT = lim Pidi T-yno
_
1
+ P222
2
12
2
(p102 + p2q1) +
Σ
14
T-000
T
T
im1
1m1
0²
(P191 + P292)
+ (p192 + +p291)
(1
w2)2
(1 w2²2
2 (p)
P2)
1
w)
Q1
w
1
92
Step 3: Next, we compute the limit of
E
1
E
(pi
p2)
T
2:24-1
91
2
T
1i=1 1:31-11
2i=1 #7-1
92)
T
T
T
2
T
1
E
P1
Σ
1 + (p142 + (1p2)
Σ
1 + P202
1-1
i=1
i=1
1=1
T
T
2
T2
pn + (pig2 + (122) Σ
85 + (p19) + +22(2)
F.T
There are six terms to be computed. However, as we are only interested in when - 0C, then only terms with double sum survive. That is, we only need to compute (E 11) (Er= of 22 and (E 24 1 Dz3 By Lemma
10 we have the computations
T
2
lim t0
T
T-34-11
TT
[1
2)
1=1
lim
1
E
Σ
T
2
66
T
7
(1 2
T
Σ
100 7
lim
E
x
TT
(1 - (2-3
Therefore,
1
lim E T-000
lim
E
piqiat + (pi02 + 91P2)
3: + (p19) + P242)
T
T2
1=1
2
2
1
(wi02+ p2
t
lim
72
E
Fiil i-1
+ (pig) + 22
Σ
MiTi-1
1=1
+ 2(p122 + (p1)) + p292)
I1Ti-1 |
Σ 2:3i-1 2
σ6
(pi
p2)
1
w
91
(1 w213
w
1
/2
27

---

Step 4: Combining steps 1-3, we find that
6
lim B[(Ør wor) 7-200
(pl
p2)
91
(1 w2)3
w
1
42
2w
o
(pr
P2)
w
91
σ²
(1
w
1
92
w
o²
0²
(wa) (2)
w
w²
where we have defined 01 = 4142 + P291 and a2 = Piqi + P242- This concludes the proof.
We now present the second lemma required to prove Lemma] 1
Lemma 6. Let ((p, q, w) denote the pointwise limit the individual loss function, defined in Lemma Then
inf
sup
((p. w) 2 Cio?, Wmin; Wmax);
P.q ur [Wimin (Wmmi)
where Cla², Wminn Wmax)
is a strictly positive constant which depends only on o², Wmin; and
Wmaxx.
Proof. We recall that {(p, q. w)
II- (wa) + 02) w wherea and ag related to and q by 01 = P192 + P291 and a2 = P191 + p292. We therefore aim to show that
I-w (
o²
o²
o²
o²
inf P.d
sup
T- 2
(wa) + a2) + wi > C(a², Wmin' Wmax),
w Wiin Wmax
where Ci(o², Wmins W mmax)
> is a strictly positive constant. Clearly, we have
o²
inf P.q
sup (Wmmi Menax)]
1 2
w
(wa) + +a2)
d²
2
inf
sup
(war) + 02) w
01-02 or Miiin::aaa
22
where the infimum the right is taken over all (a1, (2) R²a We abuse notation and denote the above function by f(a1, 02; w). Note that we also have the lower bound
inf 01.02 welWeitn Wimax]
sup ((a1, 022 w)
(20)
2 inf max (((n,, 022; Wmin) ), ((a,, Or;; Wmax), & (01, 02, W + Wmax 01.02
))
(21)
The infimum on the right is attained at point (aj az) on the intersection the curves {(, Winin ) ((.,'s Wmax) and l (.,,, #minttWaax and it is equal to zero if and only if there exist parameters
2
aj, az such that E(a aži w) for all w E [Wmin: Wmaxs Wi Wman
For a fixed w, a point
2
(a1, a2) satisfies {(a1, (2;w) 0 if and only if it lies on the line
o"w
I W
2 w.
Since Wmin # Wmaxx it is easy see, for the system of equations
- Wmin x
+
Wmin
mun
Uumax. T
Wmax
di
W. v 1 (Wmin + Wmnx),
1-102
T-
that the rank of the augmented matrix is strictly greater than the rank of the coefficient matrix. By the Mauche-Capelll Theorem Shafarevich and Remizov (2012), the above system has no solution. This proves that the infimum
Wmin + Wmax )) = C(o2, Wminy Wmax)
inf max [((a), 022 Wmin), ((11, 02! Wmax)), (11,02 01,00
nonzero, and hence the desired claim is proven.
28

---

We now leverage Lemmas 5 and 6 to prove that the limit of the infimum infp (p. q) is lower bounded away from zero. We hist need another lemma. Recall that a family of functions is equicontinuoиs if it has uniform modulus of continuity (see Appendix [ a precise definition). The following lemma establishes some continuity properties of the sequence of individual losses (fr)-
Lemma 7.
1. For any P.q E RR2, the sequence of functions on [Wmin; Wmax) given by {w -> (p, q. w) is equicontinuous.
2. For any R > 0, the family of functions on {llp], I|ll S R} given by
{(p.q) + (r(p.q.w))22 we Wiax
is equicontinuous.
Proof. We first recall that (T [iO -
For 1), the expectations defining Ey are computed Lemmas and 10, and it is easily seen that, for fixed p. q. the derivative in of each term of l (p. q, w) is uniformly bounded for w E [Wmin- Wmax].
For 2), we note that for each 7 and E [Wimn:: Wmax) (p, q. w) is polynomial in the entries of p and q, and the computations of Lemmas and TO show that the coefficients of these polynomials are uniformly bounded in T and w. This proves that the derivatives of the functions {(p. D
TandTOpp
(p,, q, w)}r2 we [Wmmn Wmax] are uniformly bounded with respect to and w on {IIp]), ||||| S R).
We are now ready prove Theorem
Proof of Theurem
By definition, we have
(p =
sup
lr(p. q, w).
w wE(W
The result will be established if we can prove that
lim inf T 70000 Hall SR we [Wiin [mmax]
sup
(T(.q..)
sup
((p, q w),
(22)
pall R E/ Wmmoe]
where l is the pointwise limit of Er, defined in Lemma Once Equation the result follows from Theorem 2
(2) has been established,
which establishes that
inf || (wwin [emwer]
sup
E(p, q, w) > C(o², Wmins Wmax).
To prove Equation ?2 first note that for any p. q E 2R22 the sequence of functions on [Wmin, Wmax
given by (w + (T(P, q. w))T is equicontinuous by Lemma and converges pointwise to the function w ((p q, w) by Lemma 5 Therefore, by Lemma 13 the sequence of functions {w + (r(p, q, Fr converges uniformly on [Wmin Wmax] to the function w + E(p. q, w). In particular, we have
lim
sup
(p(.
sup
(p..q, w), for all P.
(23)
T-000 we [Damm Wianx]
Next, Lemma 7 guarantees that the sequence of functions on fllpll.ql s R) defined by {(p, q)
(T(p, q, IT, is equicontinuous. Since the modulus of continuity of family of functions is
preserved under the supremum, the family of functions {(p, q) + SUpwS[www.. wninn Wmar] (T q, w)] is
also equicontinuous {Ilp]l.q qll < R}. Therefore, Equation 23 and another application Lemma I3
together imply that
sup
Er(p. q,
sup
w), uniformly [IlpI], gll s R).
[Wani [mma]]
we [Wenin M
This proves Equation
22 and concludes the proof.
29

---

C
Auxiliary lemmas
In this section, we state and prove various helpful lemmas used in the proofs Theorems | and 2 To begin, make frequent use of the following characterization of the distribution of the dynamical system iterates defined by Equation (
Lemma 8. Let x = (Ius T1, Tr) be as defined in Equation
1. For any E (1...., T). 21 ~ N (0, w (Ia -22-1)).
2. For any S < - T, the random variable 21 = Ek-i41 Wo-k& satisfies 2i,j 1. Tb E| = 0, and Ij Wa-ix; + Zij- In addition, Zi,j is normal random variable with
covariance 0² Σ Sk=i+1 2
Proof. 1) For any t, 24 = Ei=1 Wi-iss It follows that
It N 0, ( Σ w2(l--) _wett-) -
(0, W2a (Ia- W
2) From the above calculation, it clear that 2- Wi- Z.,j The independence of 21.j and my follows from the independence of cI...., B[gx] for each is E {1....,T):
......,,r Ex, and the fact that IE [2, = follows from the fact that
The following computations, involving fourth and sixth moments of the linear dynamical system, are heavily used in the proof of Lemma
Lemma 9. [Fourth moments along the dynamics] Let (I,...., be the iterates of the ID dynamical system defined by Equation (5) with parameter w E (0, 1). Then
Ix)
1. lim Ei=1 B
at
(I (1-w"y
2. lim;-100 Ei= B[a7xf]
0² (1-w?)²
lime-1o0 1 E B[x
Proof.
For the first equation, we first compute E E[r,;-- [x7] for each / >>> 0 and E (1...., (). For indices i j. we use the decomposition zy w 24 24,j as defined in Lemma 8 We have
B B[r,2, 1 2 = E|
+ 2
EEw 2 2/ I
1E[w2(1- 2(- (WIi-1 + { xi- + I:00
Elw ((--)) (w)) x + 3wx; ?
+? 11,04-12,.1
(i-11
2)
2i--1)
2(t-)) ((---)
2 2(e i)+3
+ 3 2(
4
wm
102
w
w
21- 1)
+ 1(i-1)
2(--1)
=
3w 2(t-))+
3m 2( 2
((t-1)+1
(1 - =2
10
( ((--r + 2)
+ w
(1 w2)2
3r 2(+-))++ 1)3
Gi ( + 3w 2((+1-)
(t-
3w0 2(0-2)+)))))
+
- w2)2
m
- 1)+1 (t) + (1+-)
4
2222
30

---

Notice that we are able to compute the above expectations easily because many of the terms vanish due to independence and the fact that all distinct random variables are centered. Summing over t, we get.
3
1
2
+ w 2(++1) 1 w² 2t
B 1120
0²
w
2tw
2(t-1)+3
(1
w2y2
w²
1 1 w
+ 0 4
3
w
tw
2t=2(11))+1
1 W
1
W2
+ 0²
t
1
22tt
1 - 2
+ tw
w2)2
w
w²
2t
3w
1)+
3w
+ (1 w2)3
w
(1 w
1 w
(1 w2y
(112(11))+
21-2(11))+1
w (1-1)11
+ 00t
w
(1 w2)²
1 - w²
(1 - 22)²
(1 - w2-
1
22t 3w + +w 322(++1)-1 + 3w (1 w²) 2w
u
(1 11 2/
2 (111))+ 3 2 1)+ (1 u + w + w 21+-11++
+ 0 1
(1 - w
1 2 2w= -1 + w
3w0 21 - 1)+3 2w 2(1 ( 1)+1 +
+ 4
(1- w2)2
(1 w2
We then divide by t to get
1
3w 1)+3 (t-14+
(!).
E B 21) 0¹
+
t
- (2=
Since w E (0, 1), all terms of the form wtt vanish when we take the limit. This gives us the final result
o2w
lim Σ E
(24)
(1-w2)
For the second equation, we first prove that
lim 1=
=
1
Σ Bi
04
1
(1-w2y²
1=1
To prove this, we first rewrite the expression at hand as
1
Elz Elzx(wx; (wx; + E+)=+
=
w
E [1 1 x +
E [
To simplify the second sum on the right, we further compute
E E[n
F| Elx,Ci(w0* 24 =1
E Elw 23 + 211122,11
(1 1)+ <3222,]]
-od (3) + - 1) (1-())
2
31

---

This allows us to compute the limit
0 o'w²
lim w 1-000
1
7
Σ
19 M
(1 2
w
(1 w2y
This proves that
limm
E B
1-00
1
desired. To prove that the sum computation that
B|x 1
x7
has the same limit, we observe by similar
E
E [[[ + [1)2
w²
Bia [r]
B xt
w
Bi07-1 1 +
Σ
13 B (w --t + 2x,)9
w²
B +1
+
1
Σ
E 10 2( g) + 22,,
1=1
1=1
2)((e-1))
w
Bia
Σ
3w 2(e + - 22
Rearranging terms and taking limits
oo on both sides, we get that
01
1
lim t1000
E[a
2 =
(1- (1- w2)2
1 1 w
01
(1 w2y²"
This completes the proof.
Lemma 10. [Sixth moments along the dynamics] Let (2.....,2) Iz) be the iterates of the ID dynamical system defined by Equation (5) with parameter w E (0, 1). Then
1. lim LE [(i=n
2,23-1)
x
(1 (1-w233
2
2. lim 1
(Σ 2²²1) )² x =
w1-
3. lime E
[Etn
E
Proof. 1) For the first equation, write
2
1 E
Σ MaTi-1
E
Σ
x
20
1
2
+2 ΣΣ Tza;- 1 j=2
Notice, however, that DE Eiz3a?_a0? = O(t-l), and thus it suffices to only consider the second sum to compute the limit. For each pair (i. j), the expectation of 1 1 decom- poses into sum of many different terms, so computing the precise value of the limit of the sum
32

---

Ej=2 Eisl 12 is ostensibly challenging. However, notice that any term aig such that Σj= Eie Ui = ((2) will vanish when we take the limit. In particular, since Ex w < oc, any term of the form oi c. (((t-))+((--i+aat where es constant, will not contribute the limit. This allows us to ignore most terms arising from the subsequent expectations
To proceed with the proof, compute for i that 16 12 1
23.1) 2, 1221-1
w 2t 5) n uy 1 18 + E 1400))))) 11,
where we used the independence and mean- zero property of 2/.0. For the first term, we get that E [1]0]-12,01-]]
w 20t 2t 2a0t--
20(1)) DE
(wxz-- + -
20-0-
10 10-23 + 33:z 18) 11j-1 11j11123i11
3 33 31- 1 30 m. 11:3;
2 DE
( ( ( 24 + zi.-1) )) 1, + 30 30" (w--i-1x;; + z1)--)) xx;;1=1=11
3 w
101--111 + 6w Gw 2(1 111---11 22
- + 2 I + +30 21(--111) + 2 2
5
21
w 10-1-11 3
w + Ei
5:-1 + 21- - WT;-1 + E3 Fi-1
+ 2/--1
w Er
Fi-1
3
Wi::1 + t (.--1) (())) ]
3w
21t-1B
10 261--1) ww
W + ti Ii-1 + =
2
20 - 1) E R + 10w 22/ x + 5w x
+ 2w
B
E T x1 _; + 35 w
2x x
w
E
+ 30 w 2(t E 2
w
30
B| $ [wał]]) .]
3
2
1 2 1- u
2
1 2
2
15w
30
+ 15w
1 w
- 2s)
20
- 2
+ Gw 21 (1
3u3
+ 3w
- w2
1 - 2
1 - 21
2(1
2i
+ 2(- w
u2
2
+ (t-r)) 2(ا (
3
1
2i
3w2
2
3w 2(t 20--))-
( 1
1- 20
1
u
1
u²
wn
w
As discussed previously, since each of the above terms is o(t²), all of them vanish when we take the limit; that is.
lim
B
2 = 0.
w
F=
33

---

For the second term, we compute
E 11 E[ | BB - 11
B| [ [ - -1. 1x
B[e [ [ 20 20 + w2 1211111
F [B 100 1+1 x 1 w 23 -
w ++1 B[2
2 [1 + 2² B 112
o -it1 -1 (1- -- )
(-=
1- - 2
2
(1 (11 w2
11- --=22 w
1 =
2
+ wm
1 w2
w
w
w
The first term o o Wiiiiti ( (- ) ( ) is o(t2) and hence vanishes in the limit. The second term satisfies
2 20 1-1
r o2 (1 (1-wi) (2((-11) (1-
1 1- w2 ) ("I=
w2(d-1) w2
)
(1
1 w
on (1 - w2)3
lim t000
1 -==
t²
1 w2
1=2 1=2i=1 i=1
This proves that
2
w
lim E 100
x
(1 - w2)3
as we aimed to show.
2) For the second equation, the proof is similar to that of the first equation. The expression whose limit we want to compute is given by
E t2
Σ
2
2
E
Σ
As in the previous case, only the double sum contributes to the limit + co. We compute, for < j.
E|mイスプスウ| =
+ =1,
22 E B
20 B | Ela (w br + zوح) 2
20 ' R p3
2
D 23,0 + Bla
Since w [[ and 26 B to the limit. We conclude that
B[a 23,1 are o(t9) E[n zt, 23.1 is the only term that contributes
t
3
lim 100
Σ
2
lim b
B 2
12
j=2
(1 24 (1 - n 2 21) - (((-))
lim
(1 - 2
j=2 1=1
5
(1
2
3) The proof of the third equation is similar to the proof of the first and second equations. We have
E
x
2
E
z
3
1
+2
2
2 12 1
2
2= t=1
34

---

and only the double sum contributes to the limit. We compute that
B 11 - 11 + -
= [
=00 +
, 11- 23. =
w + E| =3.1 w
Since the first two terms are o(t 2 only the third term contributes to the limit, and we conclude that
2w
lim
--
2i-1
2
lim 100
EE 1 24 11- 131al
100
/=2
2w
(1 w 1) =² - 1)) (((
lim
f2
(1 w2)s
1= 1=1
0 ww
w2)3
The following lemma controls the size 2T,L along the Richardson iteration and is used in the proof of Theorem
Lemma 11. Let (zo...., 21) follow the dynamical system and let ZT be defined by the Richard- son iteration
11, 2T a X1 L>0 2T,0 = 0.
211- 2(1- for a numerical constant e >>> O, we have
Then, long as
Bll O (R: (1 22) + a 2(( (2k(L 1)11)
Proof. By Fubini's theorem, we have
B B| S/² P (ler,ell > r) dr.
Changing variables, we find
E B| 11 11 /
> dr
< k + 1 krk (| > r) dr.
By the recurrence defining ZT, and the triangle inequality, have
( r) IP (l) aXx) I + > r).
Iterating this bound, we have
/ kpk lp
kT k ((1eT, > r) dr S
a Σ ==1
Ia axTlllpl >r dr.
35

---

If & denotes the event on which II - axx)] & 1, then we have
1-1
by
ip
a
[[I, - a. axx))lppl 2r dr
j=l
T-1
KJ
kpp
a
( - ax)]ll > >nn dr
kr
k-pp
[1 - |001==00)66 > dr
a
j=1
For the first term, notice that
oxT)llb >elll>nnn@@_ $ {5 kr PaLllz(L > r) dr
kr 1p
(Ia
S (alb) ( kp ((|TTTl] r) dr
=0 a
where we note that the above integral converges due the exponential concentration of ||rl| proven For the second term, since |[ aXPlloo > on E"; we have
in Lemma 12
L-1
ax.l1 > dr dr S ( kr ' (La aXrllo0'110 '1ær1 > r) dr
kr
k--1
P
a
|| a
j=1
kt (n-IP((L])) - ax 1x116-11171 || > r (1 S vr}) dr
kr 10-1P(al)) [aLlII a xx 11 | FT| (nffllaa) vr3) dr
ky (a ax - vF) dr+ /, kp ( VF) dr.
Notice that by the concentration bound for ||,,|| stated in Lemma 12 the second term above is bounded by
J kr kP (||T|| Vr) dr S Ci l. ky exp (-c,) dr O(k)
where O1 and C2 defined in Lemma 12 For the first term, make the change of variables
11/2 1/(L-1)
r +
ab
to rewrite the integral as
Kr k- 1 P (axilla-axTllr vr) dr
= =a(aa) f
22((1-1)- (I[ aXT)llop r) dr.
(aLjine
We further have
p 2k(1-1)-1P((( aXT)llop dr
, ([[(La aXT) -XX r) dr
+ (2k(6-1)-1p (I[[I aXx))lop > r) dr
< 1+ of (22(1-1)-11 (I axT) r) dr.
36

---

Note that the first integral in the sum above could be negative if aL > 1. This proves that
k (a 2h L Laspine (1((-1)--1p (l axx))llop > r) dr
Sk(aT f ( (II(Ta axxr)llop ((x)llp r) dr.
To control the remaining integral, we note that
a(T-ax))llop max (|1 - admain (XT)), - and (X
S max (1, amxax (XT) - 1).
Therefore, for r 1,
P Amax(XT) > 1 1+1
P (I] (I
- llop
>
This allows to bound the remaining integral by
2k 2k( 11-11-11111 P (I|Ia aXo) r) dr S f 22((1-11--1p (Aaxx(X))
> r 1
dr
a
10 (or (or-1) (0)-1)2R(1--1 1)2 (Amax (XxxxxxXxx) (T) r) dr
22/a
( 22((1-1)-1p (Amax (XT) > r) dr
$ a 22(1-11)
2/2
{ 2h(1-11)-1
cVTr(1 w
cVT) o²
< a 1k)
1)
exp
dr,
0
2/a
where we used the concentration inequality proved in Lemma of variables, we rewrite the above integral as
12 in the last line. After another change
2 cVTr(1 max
cVT
a 2h((-11
222(2-1)-1 1)-1
exp
dr
0²
2/a
2k(1.-1) 1)
a 2k(
Q04
cVT(11
2 maxx
ov/Trll
2(1 then the lower limit of the above integral is non-negative, and hence we have the
a < upper bound
07
24(L-1)
22((-11
11)--- - dr
CVT(1
w2 mmax
2 202
TvTrll whas)
a04
2R(L-1)
2b(--1)
I(2N(L 1))
cVT(1
2
2k(L-1)
2k((111)
(2h( - 1))!
cvT(11
where I'(-) denotes the function. Combining the estimates for each term gives us the bound as stated in the Lemma.
We make use the following elementary concentration inequalities for the dynamical system.
Lemma 12. Let (Zo...., IT) be defined by the dynamical system (2). Then
PP ([ 2 r) S Sexp
(((1- ((l-wmjae? )2)
exp
r(1-w
80
80
37

---

2. IP (Amax (+ mco?)
> >r) S exp
( evTrrl1-mae)
CvT
a²
0²
Proof. To prove 1), note that by Lemma 8 is centered Gaussian random vector with covariance
cov(xT) 0² (Ia W (I, w
max
It follows that | can be written as sum of d independent random variables
d
| 112 = Σ
T
j=1
where æry are normal with E[rr,]] = 0 and E.
E[a
particular, each ær, is sub-
max
exponential with parameters
2,4 I-
x²
2
(see
Wainwright 2019 This implies that ||rl|?
sub-exponential with parameters
22
which yields the concentration inequality
P [||T||| r) IP (1|=) 12
x |2] > r
[[[xT]13))
(r
R rT
[
w )
S exp
80
d(l wmax
)2
r(1 - w max
)2
< exp
.exp
8
8
To prove 2), we proceed in two steps.
Step 1: we first show that the ID dynamical system
Z++1 w2, Ee+1, ε(+1
(0, w [wmin, Wmax], 20
satisfies the concentration inequality
1
d(11 winex)? )²
r(1 whuxx )
P
exp
exp
8 E.. and therefore
8
To prove this, note that 24
T
Σ
2
2i 2i j+h) 2i-j = A
T 1=1
T
1=1
where & (E1,...,,Tr) {T) R and A RTX
is defined by
T
AJk- =
" (++++
T
i=
max (() .... + 2T -(++k)))
w max(j.k)-(G (G++))
T
1- w
It follows that
T
|| <
w
T w2)
j,k=1
(k -)
T2 - =22
k= j=1
w
T 22
1 2
2
T(I w2/2
38

---

Hence
V2
| v
(1- w2 w2-
Then, with { (E1,...-5 Et), noting that each is co--sub-Gausse the Hanson-Wright inequality (Vershynin) 2018) guarantees that
cCTT((1
w maxx)
P (E" Ag EiE" AC) > r) exp
where e > O is a universal constant. Noting that Ei5" [E] the bound above, we find that
I- o² S
by Lemma 8 and rearranging
max
cvT(r E8S" AE))(1
w Wmxx
AE exp
0²
cV Tr maax)
CVT
S exp
Step 2: We show that the bound above implies the desired concentration bound for 7 Ei viet) To begin, note that
Amax
T
T
Xmax
T
Σ
>>
|a 1| >
Next, by expanding each norm |
12 in the basis of eigenvectors of W, we can write
T
T
d
Σ 1
T
where each (zi.j...., 2T.5) is an independent copy of the 1D dynamical system defined in Step 1. By the Bernstein bound for sums of subexponential random variables, this implies that
coVTT(( w +
cVT
IP
| 2
r
exp
T
04
σ²
and therefore that
evTr(1
2 w
CVT
P
Amax
Σ
T Dgal
> >r]
s eexp
+
T
0
O²
1=1
The following lemma is used to extend pointwise convergence of functions to uniform convergence. Recall that sequence of functions {fn} compact metric space X' is equicontinuous at X for every c > 0, there exists 5 > O such that for all x' E X' with [x x'l < 8, we have The sequence (fn} is equicontinuous if it is equicontinuous every
sup,, (f(()) fx()')
x E.
Lemma 13. Let (fa), be functions on compact metric space X such that
1. The sequence (fn is equicontinuous,
2. fn + pointwise.
Then fn + f uniformly.
Proof. Since fn + ff pointwise, the sequence (x)) is bounded for each x X. Therefore the sequence of functions {fn J is pointwise bounded and equicontinuous, so by the Arzela-Ascoli Theorem (see e.g. Folland (1999). has uniformly convergent subsequence. But the limit of any uniformly convergent subsequence of (fn) must equal the pointwise limit of the sequence. This proves that f is the only subsequential limit of (.fr. in the uniform topology, and hence fn + f uniformly.
39


Reviews:
[{"review_id": "zOzsgnLXWT", "reviewer": "Reviewer_dJ25", "summary": "The paper studies the in-context learning capabilities of transformers on non-IID data generated by noisy linear dynamical systems. The authors establish a depth-separation phenomenon. Their primary results show that while deep transformers with logarithmic depth can achieve an error rate of O(log(T)/T), which is comparable to the least-squares estimator, a class of single-layer linear transformers is fundamentally limited, suffering from a non-vanishing approximation error of Ω(1). This highlights that for certain classes of correlated, task-dependent data, network depth is a crucial architectural requirement for effective in-context learning, a finding that contrasts with results from IID settings.", "questions": "- The lower bound is established for a strongly simplified single-layer model. While the authors discuss several possible generalizations (such as to multi-dimensional settings or non-identity MLPs) it remains unclear how they view the role of non-linearity in standard softmax attention. Do they expect the depth separation phenomenon to persist in the presence of such non-linearities?\n- The results identify a task that a one-layer linear transformer cannot learn. Have numerical experiments been conducted (using standard architectures and training) to empirically validate the predicted Ω(1) vs O(log(T)/T) error gap between shallow and deep models, or to explore potential improvements in these bounds?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n- The paper provides a significant depth-separation result for in-context learning in a non-IID setting, which is more realistic than prior work.\n- The analysis is sound and well-written, offering insights into why depth may be crucial for learning from correlated data sequences.\n\n**Weakness:**\n- The key lower bound result, which establishes the failure of shallow models, is proven for a significantly simplified single-layer transformer (one-dimensional system, linear attention, and a fixed identity MLP matrix). While the authors briefly discuss potential extensions, this simplification limits the immediate generality of the claim. It remains an open question how these results would change with more complex components like non-linear MLPs or softmax attention.\n- The work is purely theoretical, and it would be valuable to include numerical experiments to empirically validate the predicted performance gap between shallow and deep models, particularly within a more realistic Transformer architecture. In this context, the phrase “We also provided numerical results that confirmed…” at line 298 is unclear: could the authors clarify which results are being referred to and how they relate to the theoretical findings?", "was_revised": true, "final_justification": "This paper investigates in-context learning under non-IID conditions and presents a meaningful depth-separation result in a setting that more closely reflects realistic data distributions than prior work. The theoretical analysis is rigorous and clearly presented, offering valuable insights into the role of depth in learning from correlated input sequences. However, the model is highly idealized. During the rebuttal, the authors provided numerical experiments which, although limited, offer preliminary evidence that the main claims may extend beyond the simplified setting. For these reasons, I consider this a borderline accept.", "rebuttal": "We thank the reviewer for their kind and helpful feedback. Since several reviewers cited the same weaknesses, we have the following general response:\n\n$\\\\textbf{Experiments:}$ We ran some experiments to validate our theoretical results. Due to the current rebuttal guidelines, we cannot show the plots from our experiments. However, we plan to add our experimental results to the revised version. Our results are as follows. We trained transformers with both linear and softmax attention to learn random linear dynamical systems in-context. For computational reasons, the loss we use is averaged over the task distribution, as opposed to the supremum loss we use for theory. For one-dimensional systems with noise variance $\\sigma^2 = 0.05$ and context length $T = 500$, we present the minimum test loss as as a function of depth in the following tables:\n\n$$\n\\\\begin{bmatrix}\n\\\\textrm{Number of layers (softmax attention)} & \\\\textrm{Minimum loss value:} \\\\\\\\\nL=1 & 0.0011824991088360548 \\\\\\\\\nL=2 & 0.00022110833378974348 \\\\\\\\\nL=5 & 0.00012664416863117367\n\\\\end{bmatrix}\n$$\n\n$$\n\\\\begin{bmatrix}\n\\\\textrm{Number of layers (linear attention)} & \\\\textrm{Minimum loss value:} \\\\\\\\\nL=1 & 0.0007882040226832032 \\\\\\\\\nL=2 & 0.00015281644300557673 \\\\\\\\\nL=5 & 0.00011635164264589548\n\\\\end{bmatrix}\n$$\n\nWe also have numerical experiments for multi-dimensional systems (up to $d=5$), but the results are most illustrative for one-dimensional examples. Additionally, while we are unable to produce results for depth greater than $L=5$ due to the time constraint, we plan to include experimental results for deeper transformers in the revised version. Nonetheless, we hope that our inclusion of these experimental results strengthens the overall contribution of the paper. To summarize, our plots confirm the following points:\n\n1. There is a clear separation in the error achieved by single-layer and multi-layer transformers. This provides evidence for Theorem 2 in our paper.\n2. Increasing the depth beyond two layers  marginally improves the error, but the most significant difference is between one and two-layer transformers.\n3. For each choice of the number of layers $L$, the minimum loss achieved by the softmax attention transformer is comparable to the minimum loss achieved by the linear attention transformer. This suggests that the non-vanishing lower bound persists when using softmax attention. The minimum loss values are shown in the table below.\n\n$\\\\textbf{Choice of architecture for the lower bound:}$ Broadly, the goal of our paper is to provably demonstrate the importance of depth for in-context learning when the data is not iid. We think that the linear transformer is a natural architecture through which to study this phenomenon, since several prior works have studied the in-context learning ability of  this architecture on iid data. In particular, the recent works [1,2,3] which prove upper bounds on the loss for single-layer linear transformers on iid data, provide a direct baseline to compare with our lower bound. Currently, we are investigating  whether our upper bounds can be extended to linear transformers with finite depth, as well as the approximation error of nonlinear transformers, such as those with with softmax attention modules; however, these directions are beyond the scope of the current work.\n\nConcerning your specific questions, we have the following comments:\n\n1. Extending our results to nonlinear transformers is an ongoing direction. Our recent experiments suggest that the depth separation observed in Theorem 2 also holds for transformers with softmax attention. However, it is technically challenging to compute the limiting loss as we did for the linear case, because it involves computing moments softmax vectors of the linear dynamical system. It therefore seems that the softmax case may require a different analytical approach to the problem. \n2. While our experiments do confirm a depth separation, it is difficult to validate these exact rates because they are asymptotic results. In addition, the optimal rate for in-context learning linear dynamical systems is unknown. The $\\frac{\\log(T)}{T}$ rate is optimal (up to the log factor) for estimating the matrix $W$ from the dynamical system trajectory, but it may not be optimal for our in-context learning problem, namely, predicting the next token from the history $x_1, \\dots, x_T$.\n\nReferences:\n[1] Zhang, Ruiqi, Spencer Frei, and Peter L. Bartlett. \"Trained transformers learn linear models in-context.\" Journal of Machine Learning Research 25.49 (2024): 1-55.\n[2] Ahn, Kwangjun, et al. \"Transformers learn to implement preconditioned gradient descent for in-context learning.\" Advances in Neural Information Processing Systems 36 (2023): 45614-45650.\n[3] Mahankali, Arvind, Tatsunori B. Hashimoto, and Tengyu Ma. \"One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention.\" arXiv preprint arXiv:2307.03576 (2023)."}, {"review_id": "39B1y5kaFe", "reviewer": "Reviewer_Q9Jh", "summary": "The paper studies the in-context learning of linear dynamical systems for transformers and presents two main results. The first is the approximation error for multi-layer transformers which implements the Richardson iteration. The second is a lower bound for a single-layer transformer.", "questions": "Q1: My main question is about the significance of Theorem 1. [1] already proved that  transformers can implement ridge regression on nonlinear dynamical systems, then what new message does Theorem 1 bring compared with [1]? \n\nQ2: Theorem 1 used the algorithm unrolling technique, what's the benefit of this approach compared with the conventional gradient descent upadate in [1] [2] [3] [4] etc.?\n\nQ3: While Theorem 2 suggests that a single-layer Transformer is theoretically insufficient for ICL of linear dynamical systems, could this limitation be empirically verified? Additionally, although determining the exact number of layers required remains challenging from a theoretical perspective, an empirical investigation could provide valuable insights.\n\n\n[1] Guo, T., Hu, W., Mei, S., Wang, H., Xiong, C., Savarese, S., & Bai, Y. (2023). How do transformers learn in-context beyond simple functions? a case study on learning with representations. arXiv preprint arXiv:2310.10616.\n\n[2] Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., & Vladymyrov, M. (2023, July). Transformers learn in-context by gradient descent. In International Conference on Machine Learning (pp. 35151-35174). PMLR.\n\n[3] Ahn, K., Cheng, X., Daneshmand, H., & Sra, S. (2023). Transformers learn to implement preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36, 45614-45650.\n\n[4] Bai, Y., Chen, F., Wang, H., Xiong, C., & Mei, S. (2023). Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems, 36, 57125-57211.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n1. The structure of the paper is clear and is generally well-written.\n\n2. The lower bound which showcases the inability of a single-layer transformer to perform ICL on dynamical systems is interesting.\n\n## Weaknesses\n\nPlease see questions.", "was_revised": true, "final_justification": "During the rebuttal period the authors have added experiments to showcase the inability for a one layer attention to learn dynamical systems. Also most of my questions are resolved, and the algorithm unrolling technique is essentially a generalization of the GD but appears beneficial from a theoretical point of view.", "rebuttal": "We thank the reviewer for their kind and helpful feedback. Since several reviewers cited the same weaknesses, we have the following general response:\n\n$\\\\textbf{Experiments:}$ We ran some experiments to validate our theoretical results. Due to the current rebuttal guidelines, we cannot show the plots from our experiments. However, we plan to add our experimental results to the revised version. Our results are as follows. We trained transformers with both linear and softmax attention to learn random linear dynamical systems in-context. For computational reasons, the loss we use is averaged over the task distribution, as opposed to the supremum loss we use for theory. For one-dimensional systems with noise variance $\\sigma^2 = 0.05$ and context length $T = 500$, we present the minimum test loss as as a function of depth in the following tables:\n\n$$\n\\\\begin{bmatrix}\n\\\\textrm{Number of layers (softmax attention)} & \\\\textrm{Minimum loss value:} \\\\\\\\\nL=1 & 0.0011824991088360548 \\\\\\\\\nL=2 & 0.00022110833378974348 \\\\\\\\\nL=5 & 0.00012664416863117367\n\\\\end{bmatrix}\n$$\n\n$$\n\\\\begin{bmatrix}\n\\\\textrm{Number of layers (linear attention)} & \\\\textrm{Minimum loss value:} \\\\\\\\\nL=1 & 0.0007882040226832032 \\\\\\\\\nL=2 & 0.00015281644300557673 \\\\\\\\\nL=5 & 0.00011635164264589548\n\\\\end{bmatrix}\n$$\n\nWe also have numerical experiments for multi-dimensional systems (up to $d=5$), but the results are most illustrative for one-dimensional examples. Additionally, while we are unable to produce results for depth greater than $L=5$ due to the time constraint, we plan to include experimental results for deeper transformers in the revised version. Nonetheless, we hope that our inclusion of these experimental results strengthens the overall contribution of the paper. To summarize, our plots confirm the following points:\n\n1. There is a clear separation in the error achieved by single-layer and multi-layer transformers. This provides evidence for Theorem 2 in our paper.\n2. Increasing the depth beyond two layers  marginally improves the error, but the most significant difference is between one and two-layer transformers.\n3. For each choice of the number of layers $L$, the minimum loss achieved by the softmax attention transformer is comparable to the minimum loss achieved by the linear attention transformer. This suggests that the non-vanishing lower bound persists when using softmax attention. The minimum loss values are shown in the table below.\n\n$\\\\textbf{Choice of architecture for the lower bound:}$ Broadly, the goal of our paper is to provably demonstrate the importance of depth for in-context learning when the data is not iid. We think that the linear transformer is a natural architecture through which to study this phenomenon, since several prior works have studied the in-context learning ability of  this architecture on iid data. In particular, the recent works [1,2,3] which prove upper bounds on the loss for single-layer linear transformers on iid data, provide a direct baseline to compare with our lower bound. Currently, we are investigating  whether our upper bounds can be extended to linear transformers with finite depth, as well as the approximation error of nonlinear transformers, such as those with with softmax attention modules; however, these directions are beyond the scope of the current work.\n\nConcerning your specific questions:\n\nThe main message of Theorem 1 of our paper is not only the construction of a specific transformer, but that our constructed transformer achieves a next-token prediction error bound of $O(\\log(T)/T)$.  This is where much of the work of proving Theorem 1 comes from, as it requires us to synthesize our particular construction with statistical guarantees of the least-squares estimator (LSE) on noisy data, and to control the error incurred on the event where the LSE bounds fail to hold. In contrast, Theorem 1 in [4] only presents the construction of a transformer which approximates the ridge regression algorithm for dynamical systems and does not bound the next-token prediction error of their construction. In addition, the two constructions are not directly comparable because their construction applies to a wider class of nonlinear dynamical systems, but our construction requires a much simpler transformer. In particular, while [4] constructs a transformer with $L + O(\\log(1/\\epsilon))$ layers, 5 heads, and nonlinear MLP layer a hidden dimension of $D_{hid} = 2D + d + 10$ to implement $L$ steps of gradient descent for ridge regression to accuracy $\\epsilon$, our construction requires $L + O(1)$ layers, 1 head, and a linear MLP layer with a hidden dimension of $d$ to implement the least-squares predictor with the inverse covariance approximated by $L$ steps of Richardson's iteration. This demonstrates the benefit of our algorithm unrolling technique compared to the traditional GD approach (which is a different form of algorithm unrolling): it allows us to exploit the structure of the dynamical system considered herein, thus reducing the model capacity.\nReferences: \n\n[1] Zhang, Ruiqi, Spencer Frei, and Peter L. Bartlett. \"Trained transformers learn linear models in-context.\" Journal of Machine Learning Research 25.49 (2024): 1-55. \n\n[2] Ahn, Kwangjun, et al. \"Transformers learn to implement preconditioned gradient descent for in-context learning.\" Advances in Neural Information Processing Systems 36 (2023): 45614-45650. \n\n[3] Mahankali, Arvind, Tatsunori B. Hashimoto, and Tengyu Ma. \"One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention.\" arXiv preprint arXiv:2307.03576 (2023)\n\n[4] Guo, Tianyu, et al. \"How do transformers learn in-context beyond simple functions? a case study on learning with representations.\" arXiv preprint arXiv:2310.10616 (2023)."}, {"review_id": "MFYOMW85Ip", "reviewer": "Reviewer_22f5", "summary": "This paper theoretically studies ICL in the non-IID setting, within the linear dynamica system frameword. A upper bound for error of a multi-layer linear transformer and the error lower bounded for a singla layer linear transformer is provided.", "questions": "See Weakness section. Besides, is it possible to extend the lower bound to a multi-head transformer with linear attention?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1). This work provides a theoretical study of the ICL capabilities of transformers for linear dynamical systems, which is a novel contribution.\n\n2). The lower bound result demonstrating that a single-layer linear transformer lacks sufficient expressive power for in-context learning of linear dynamical systems, to me, it is particularly interesting.\n\nWeakness:\n\n1). Some existing works have already studied ICL for non-IID data theoretically, even if not explicitly framed as such. For example, \"Non-asymptotic Convergence of Training Transformers for Next-Token Prediction\".\n\n2). Theorem 1 focuses on the expressiveness of transformers, showing that they can efficiently optimize training loss for linear dynamical systems by mimicking an iterative algorithm via construction. However, this result does not guarantee that a transformer will actually converge to such a solution during pre-training.\n\n3). Theorems 1 and 2 rely on a linear transformer architecture, which is quite restrictive. While this is not a major criticism, introducing non-linear activations in the attention block would strengthen the theoretical contribution, especially for the lower bound.\n\n4). The lower bound result is based on constrained attention and mlp layers. Although the authors discuss a few sentences about the fully parameterized case, no theoretical results are provided. Could the constraints on the linear attention blocks be relaxed, even if the constraints for mlp layer are kept?\n\n5).  Experimental validation of Theorem 2 would strengthen the paper, since it would show the incapability of a linear transformer structure with one layer.", "was_revised": true, "final_justification": "The rebuttal has resolved most of my initial concerns, and thus I will maintain my score.", "rebuttal": "We thank the reviewer for their kind and helpful feedback. Since several reviewers cited the same weaknesses, we have the following general response:\n\n$\\\\textbf{Experiments:}$ We ran some experiments to validate our theoretical results. Due to the current rebuttal guidelines, we cannot show the plots from our experiments. However, we plan to add our experimental results to the revised version. Our results are as follows. We trained transformers with both linear and softmax attention to learn random linear dynamical systems in-context. For computational reasons, the loss we use is averaged over the task distribution, as opposed to the supremum loss we use for theory. For one-dimensional systems with noise variance $\\sigma^2 = 0.05$ and context length $T = 500$, we present the minimum test loss as as a function of depth in the following tables:\n\n$$\n\\\\begin{bmatrix}\n\\\\textrm{Number of layers (softmax attention)} & \\\\textrm{Minimum loss value:} \\\\\\\\\nL=1 & 0.0011824991088360548 \\\\\\\\\nL=2 & 0.00022110833378974348 \\\\\\\\\nL=5 & 0.00012664416863117367\n\\\\end{bmatrix}\n$$\n\n$$\n\\\\begin{bmatrix}\n\\\\textrm{Number of layers (linear attention)} & \\\\textrm{Minimum loss value:} \\\\\\\\\nL=1 & 0.0007882040226832032 \\\\\\\\\nL=2 & 0.00015281644300557673 \\\\\\\\\nL=5 & 0.00011635164264589548\n\\\\end{bmatrix}\n$$\n\nWe also have numerical experiments for multi-dimensional systems (up to $d=5$), but the results are most illustrative for one-dimensional examples. Additionally, while we are unable to produce results for depth greater than $L=5$ due to the time constraint, we plan to include experimental results for deeper transformers in the revised version. Nonetheless, we hope that our inclusion of these experimental results strengthens the overall contribution of the paper. To summarize, our plots confirm the following points:\n\n1. There is a clear separation in the error achieved by single-layer and multi-layer transformers. This provides evidence for Theorem 2 in our paper.\n2. Increasing the depth beyond two layers  marginally improves the error, but the most significant difference is between one and two-layer transformers.\n3. For each choice of the number of layers $L$, the minimum loss achieved by the softmax attention transformer is comparable to the minimum loss achieved by the linear attention transformer. This suggests that the non-vanishing lower bound persists when using softmax attention. The minimum loss values are shown in the table below.\n\n$\\\\textbf{Choice of architecture for the lower bound:}$ Broadly, the goal of our paper is to provably demonstrate the importance of depth for in-context learning when the data is not iid. We think that the linear transformer is a natural architecture through which to study this phenomenon, since several prior works have studied the in-context learning ability of  this architecture on iid data. In particular, the recent works [1,2,3] which prove upper bounds on the loss for single-layer linear transformers on iid data, provide a direct baseline to compare with our lower bound. Currently, we are investigating  whether our upper bounds can be extended to linear transformers with finite depth, as well as the approximation error of nonlinear transformers, such as those with with softmax attention modules; however, these directions are beyond the scope of the current work.\n\nConcerning your specific questions:\n\n1. (Existing works): We had not encountered the work [4], but we agree that it also studies transformers' ability to learn from non-IID data. Compared to our work, the setting is quite different, since [4] focuses on sentences generated from a discrete vocabulary, whereas we study linear dynamical systems on the continuous state space $\\mathbb{R}^d$. We have updated the literature review of our paper to include a discussion of [4] and other relevant papers  we missed. \n\n2. (Optimization): In general, the optimization dynamics of multi-layer transformers for this learning task is highly nontrivial and beyond the scope of this work. However, recent work [5] has demonstrated that transformers linear transformers can provably learn to perform multi-step gradient descent for in-context linear regression using chain-of-thought (CoT) training. Since the ICL mechanism in [5] is similar to ours (multi-step gradient descent vs multi-step Richardson iteration), a natural extension of our work is to study the dynamics of CoT training to enforce the construction of Theorem 1. We leave the investigation of this direction to future work.\n\n3. (Using full attention parameterization and multi-head attention): We suspect the same proof strategy can be used to prove a lower bound for the full parameterization and for multi-head attention, as it just amounts to more additive terms in the limiting loss function. For the single-head case, we argue that the parameters we chose to zero out are not necessary to predict the dynamical system. Indeed, we know that the next token $x_{t+1}$ takes the form $x_{t+1} = Wx_t + \\textrm{noise}$, and the loss function minimizes the difference between the transformer prediction $y_{\\theta}$ and the conditional mean of $x_{t+1}$ given the history $x_1, \\dots, x_t$. This motivates us to parameterize the transformer to output an estimator of the form $y_{\\theta} =W_{\\theta} x_t,$ where $W_{\\theta}$ is a matrix depending on the transformer parameters $\\theta$ and the history $x_1, \\dots, x_t$. Under the full parameterization, the transformer output is of the form $y_{\\theta} =W_{\\theta}^{(1)} x_t +W_{\\theta}^{(2)} x_{t-1}.$ This motivates us to choose a parameterization of the transformer which corresponds to setting $W_{\\theta}^{(2)} = 0$.\n\nReferences:\n\n[1] Zhang, Ruiqi, Spencer Frei, and Peter L. Bartlett. \"Trained transformers learn linear models in-context.\" Journal of Machine Learning Research 25.49 (2024): 1-55. \n\n[2] Ahn, Kwangjun, et al. \"Transformers learn to implement preconditioned gradient descent for in-context learning.\" Advances in Neural Information Processing Systems 36 (2023): 45614-45650.\n\n[3] Mahankali, Arvind, Tatsunori B. Hashimoto, and Tengyu Ma. \"One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention.\" arXiv preprint arXiv:2307.03576 (2023)\n\n[4] Huang, Ruiquan, Yingbin Liang, and Jing Yang. \"Non-asymptotic convergence of training transformers for next-token prediction.\" Advances in Neural Information Processing Systems 37 (2024): 80634-80673.\n\n[5] Huang, Jianhao, Zixuan Wang, and Jason D. Lee. \"Transformers learn to implement multi-step gradient descent with chain of thought.\" arXiv preprint arXiv:2502.21212 (2025)."}, {"review_id": "rRivYOsLfo", "reviewer": "Reviewer_ETpH", "summary": "This paper studies the in-context learning capabilities of linear transformers. The authors propose the following problem: learning, using a model parametrized by a multi-layer linear transformer, on sequences of next-token prediction trajectory that take the form of noisy linear dynamical systems, with context length equal to one, and design matrices of each LDS being sampled according to some distribution.\nAfter presenting this problem, the results of the paper are two-folds. First, the authors prove that provided the depth is larger than logarithmic in $T$ (the length of each trajectory), there exists a linear transformer that predicts well the last iterate of such LDSs (i.e., performs in context learning of these tasks), with a test error that scales as $\\log(T)/T$. Then, the authors prove that depth 1 is not enough to have a test error that decreases to 0.", "questions": "I have several questions and remark:\nQ1) How about long-context problems such as long-context linear dynamical systems (such as e.g. *Long-Context Linear System Identification, Yuksel et al., ICLR 2025*)?\nQ2) What would be the authors take on the optimization perspectives of the problem?\nQ3) In Eq. (4), I agree that putting a $sup_W$ in the test loss captures a form of worst-case robustness. However, would the depth separation result appear also if it were an average over the sampled matrices ?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**\nS1) In-context learning capacities of transformers is a very timely subject, and the simplified problem studied in this paper is a very nice and elegant proxy to study this problem. It of course does not capture the complexity of real LLMs, but that's completely out of reach for now.\nS2) The depth-separation result is quite strong in my opinion: theory of deep learning and LLMs hardly capture such results, as far as I know. Such a result in the context of next-token prediction and ICL really is a strength.\nS3) The paper is overall very well written: intuitions, assumptions, results are clearly stated, in a way that is reader-friendly. I did not read the proofs fully, but skimming through them and the help of the proof sketch, makes them overall clear.\n\n\n**Weaknesses**\nW1) The proposed results characterize the fact that if a certain depth is satisfied, there exists some linear transformer that satifies desired properties. However, this does not takes into account optimization perspectives of the problem. \n\n\nOverall, I think the contributions and the clarity of this submission are quite strong, and definitely make it above the acceptance threshold.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind and helpful feedback and appreciate the positive assessment of our work. First, since several reviewers cited similar weaknesses, we have a general response:\n\n$\\\\textbf{Experiments:}$ We ran some experiments to validate our theoretical results. Due to the current rebuttal guidelines, we cannot show the plots from our experiments. However, we plan to add our experimental results to the revised version. Our results are as follows. We trained transformers with both linear and softmax attention to learn random linear dynamical systems in-context. For computational reasons, the loss we use is averaged over the task distribution, as opposed to the supremum loss we use for theory. For one-dimensional systems with noise variance $\\sigma^2 = 0.05$ and context length $T = 500$, we present the minimum test loss as as a function of depth in the following tables:\n\n$$\n\\\\begin{bmatrix}\n\\\\textrm{Number of layers (softmax attention)} & \\\\textrm{Minimum loss value:} \\\\\\\\\nL=1 & 0.0011824991088360548 \\\\\\\\\nL=2 & 0.00022110833378974348 \\\\\\\\\nL=5 & 0.00012664416863117367\n\\\\end{bmatrix}\n$$\n\n$$\n\\\\begin{bmatrix}\n\\\\textrm{Number of layers (linear attention)} & \\\\textrm{Minimum loss value:} \\\\\\\\\nL=1 & 0.0007882040226832032 \\\\\\\\\nL=2 & 0.00015281644300557673 \\\\\\\\\nL=5 & 0.00011635164264589548\n\\\\end{bmatrix}\n$$\n\nWe also have numerical experiments for multi-dimensional systems (up to $d=5$), but the results are most illustrative for one-dimensional examples. Additionally, while we are unable to produce results for depth greater than $L=5$ due to the time constraint, we plan to include experimental results for deeper transformers in the revised version. Nonetheless, we hope that our inclusion of these experimental results strengthens the overall contribution of the paper. To summarize, our plots confirm the following points:\n\n1. There is a clear separation in the error achieved by single-layer and multi-layer transformers. This provides evidence for Theorem 2 in our paper.\n2. Increasing the depth beyond two layers  marginally improves the error, but the most significant difference is between one and two-layer transformers.\n3. For each choice of the number of layers $L$, the minimum loss achieved by the softmax attention transformer is comparable to the minimum loss achieved by the linear attention transformer. This suggests that the non-vanishing lower bound persists when using softmax attention. The minimum loss values are shown in the table below.\n\n$\\\\textbf{Choice of architecture for the lower bound:}$ Broadly, the goal of our paper is to provably demonstrate the importance of depth for in-context learning when the data is not iid. We think that the linear transformer is a natural architecture through which to study this phenomenon, since several prior works have studied the in-context learning ability of  this architecture on iid data. In particular, the recent works [1,2,3] which prove upper bounds on the loss for single-layer linear transformers on iid data, provide a direct baseline to compare with our lower bound. Currently, we are investigating  whether our upper bounds can be extended to linear transformers with finite depth, as well as the approximation error of nonlinear transformers, such as those with with softmax attention modules; however, these directions are beyond the scope of the current work.\n\nConcerning your specific questions:\n\n1. (Extension to long-context problems): It would be very interesting to extend the positive results of our paper to linear dynamical systems which depend on a context length $p > 1$. Since our proof for the case $p=1$ constructs a transformer which implements the least-squares estimator, the statistical guarantees derived in [4] of constrained least-squares estimators could potentially be used to adapt the proof of our result to the long-context case (although the transformer construction would have to be modified, since the current proof uses the specific form of the least-squares predictor in the $p=1$ case). We plan to add a discussion of this problem in the conclusion of the paper and cite the reference [4].\n\n2. (Optimization dynamics): In general, the optimization dynamics of multi-layer transformers for this learning task is highly nontrivial and beyond the scope of this work. However, recent work [5] has demonstrated that transformers linear transformers can provably learn to perform multi-step gradient descent for in-context linear regression using chain-of-thought (CoT) training. Since the ICL mechanism in [5] is similar to ours (multi-step gradient descent vs multi-step Richardson iteration), a natural extension of our work is to study the dynamics of CoT training to enforce the construction of Theorem 1. We plan to investigate this direction more carefully in the future.\n\n3. ($\\sup$ loss versus average loss): The reviewer asks an interesting question. Our experiments, which use the average loss instead of sup loss for computational reasons, suggest that a depth-separation is still present in this case. The heuristic behind the lower bound is  that the covariance of a trajectory depends on the task $W$, and thus the expressions in the least-squares predictor which involve the covariance cannot simply be implemented directly by the attention weights. The $\\sup$ loss naturally captures this limitation, but we plan to investigate whether a non-vanishing lower bound also holds under the $W$-averaged loss in the future.\n\nReferences: \n\n[1] Zhang, Ruiqi, Spencer Frei, and Peter L. Bartlett. \"Trained transformers learn linear models in-context.\" Journal of Machine Learning Research 25.49 (2024): 1-55. \n\n[2] Ahn, Kwangjun, et al. \"Transformers learn to implement preconditioned gradient descent for in-context learning.\" Advances in Neural Information Processing Systems 36 (2023): 45614-45650.\n\n[3] Mahankali, Arvind, Tatsunori B. Hashimoto, and Tengyu Ma. \"One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention.\" arXiv preprint arXiv:2307.03576 (2023)\n\n[4] Yüksel, Oğuz Kaan, Mathieu Even, and Nicolas Flammarion. \"Long-Context Linear System Identification.\" arXiv preprint arXiv:2410.05690 (2024).\n\n[5] Huang, Jianhao, Zixuan Wang, and Jason D. Lee. \"Transformers learn to implement multi-step gradient descent with chain of thought.\" arXiv preprint arXiv:2502.21212 (2025)."}]

Author rebuttal:

Meta-review: This paper investigates the in-context learning capabilities of deep linear transformers when data sequences are generated by a stable dynamical system. The authors show that if the transformer depth scales logarithmically with the sequence length T, then the test L2​ loss decreases at the rate of log(T)/T, indicating vanishing approximation error. In contrast, in a simplified setting, they prove that a single-layer transformer cannot perform in-context learning.

The paper received four reviews, all of which recognize its significant contribution in clarifying the fundamental strengths and limitations of linear transformers for in-context learning. The AC concurs with this assessment, noting that the paper introduces several new ideas and results, some with promising potential for extension to more general, nonlinear models.

That said, the reviewers also identified certain drawbacks. A major concern was the limitation of Theorem 2 in constructing a linear transformer that maintains non-vanishing error. They pointed out that the construction in Theorem 2 is considerably more restricted than the one in Theorem 1. In response, the authors provided experiments suggesting that the conclusions of Theorem 2 also hold in the broader setting of Theorem 1 (at least empirically). Another point raised was the lack of analysis on the optimization aspect of transformers. The authors clarified that optimization lies beyond the scope of this work, a position with which I agree.

Overall, this is a solid and meaningful contribution.
Decision: Accept (poster)