Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networks
Authors: Luca Arnaboldi
Bruno Loureiro
Ludovic Stephan
Florent Krzakala
Lenka Zdeborova
Venue: NeurIPS 2025 poster ()
Keywords: single index model
sequential data
attention
SGD
Primary area: theory
TL;DR: theoretical study of the dynamics of attention trained with SGD

Abstract: We study the dynamics of stochastic gradient descent (SGD) for a class of sequence models termed Sequence Single-Index (SSI) models, where the target depends on a single direction in input space applied to a sequence of tokens. This setting generalizes classical single-index models to the sequential domain, encompassing simplified one-layer attention architectures. We derive a closed-form expression for the population loss in terms of a pair of sufficient statistics capturing semantic and positional alignment, and characterize the induced high-dimensional SGD dynamics for these coordinates. Our analysis reveals two distinct training phases: escape from uninformative initialization and alignment with the target subspace, and demonstrates how the sequence length and positional encoding influence convergence speed and learning trajectories. These results provide a rigorous and interpretable foundation for understanding how sequential structure in data can be beneficial for learning with attention-based models.

Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networks
Luca Arnaboldi IdePhics Laboratory
Bruno Loureiro Département d' I'Informatiuue École Normale Supérieure PSL Paris, France
Ludovic Stephan ENS AI University Rennes Rennes, France
EPFL Lausanne, Switzerland
Florent Krzakala
Lenka Zdeborová SPOC Laboratory EPFL Lausanne, Switzerland
IdePhics Laboratory
EPFL
Lausanne, Switzerland
Abstract
We study the dynamics of stochastic gradient descent (SGD) for class of sequence models termed Sequence Single-Index (SSI) models, where the target depends on a single direction in input space applied to a sequence of tokens. This setting generalizes classical single-index models to the sequential domain, encompassing simplified one-layer attention architectures. We derive a closed-form expression for the population loss in terms of pair of sufficient statistics capturing semantic and positional alignment, and characterize the induced high-dimensional SGD dynamics for these coordinates. Our analysis reveals two distinct training phases: escape from uninformative initialization and alignment with the target subspace, and demonstrates how the sequence length and positional encoding influence convergence speed and learning trajectories. These results provide a rigorous and interpretable foundation for understanding how sequential structure in data be beneficial for learning with attention-based models.
Stochastic Gradient Descent (SGD) the core optimization tool driving modern machine learning. Recent years have seen substantial progress in understanding its dynamics, particularly in two-layer networks [Saad and Solla, 1995, Mei et al., 2018, Chizat and Bach, 2018, Rotskoff and Vanden- Eijnden, 2022, Sirignano and Spiliopoulos, 2020, Arnaboldi al., 2023a]. While global convergence qualitatively well-understood when the network is wide enough, quantitative results are scarcer. particularly fruitful body of recent theoretical work addressing this gap has focused on deriving precise convergence rates for particular model classes on synthetic data, such as high-dimensional Gaussian single and multi-index models [Ben Arous al., 2021, Abbe et al., 2022, 2023]. These advances have sparked a wave of follow-up studies [Damian et al., 2022, 2023, Dandi et al., 2024, Bietti et al., 2023, Ba et al., 2023, Moniri al., 2023, Mossavi-Hosseini et al., 2023, Zweig and Bruna, 2024, Berthier et al., 2024, Arnaboldi et al., 2024a,b), deepening our understanding of what problems are hard learn for neural networks trained under SGD.
While multi-index models have served as comnersone in theoretical analyses of learning, they remain far from the architectures driving recent breakthroughs in machine learning. Modern advances in learning from sequential data particularly in natural language processing - are increasingly dominated by inrention-basedd models such the Transformer architecture [Vaswani al., 201 7]. These models introduce a paradigm shift through self-attention mechanisms, which dynamically reweight the influence of each input token based its relevance others. Through successive layers of attention, Transformers capture intricate dependencies across sequences, enabling state-of-the-art
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

performance in tasks ranging from machine translation to large-scale language modeling [Brown et al., 2020, Kenton and Toutanova, 2019].
The main goal of this work is to extend our theoretical understanding of learning with SGD on multi-index models to seeentoonbbsedd architectures and sequential data. Inspired by Cui et al. [2024), Troiani et al. [2025], our focus will be on the following class of single-layer, tied attention model:
f (X) R softmax (x+
P
(x P Va 7)
ww T
(I)
where w E I& are the trainable weights and R is the reduction map, which allows passing from a L x matrix to a k-dimensional vector. As detailed in Appendix A, this model a reduction of the standard attention mechanism, where (i) key and query matrix are tied, and deedd = 1: Q = K X w E R _ ; (ii) since we are considering a single layer attention, and we do not need to Iearn new representation of the sequence, the value matrix is the identity: V Ir. In this work, we will be interested in the optimization properties of the model in eq. (1) when trained under (spherical) one-pass stochastic gradient descent (SGD) from random initial condition w ~ Unif(Sd-1 (Vd)):
-V e(x y"; Sam) 1 vool( , y;; fwm
ur
w
|201
(2)
with the squared loss:
V( =
fu fu)( f
Σ (v (u.))
(3)
Note that for one-pass (a.k.a. online or streaming) SGD each sample is only seen once, meaning that the sample complexity of the algorithm coincides with the convergence rate. The spherical constraint is considered to simplify the mathematical analysis, a common assumption in the analysis of SGD for single-index models [Ben Arous et al., 2021, Damian et al., 2022].
To derive a sharp characterization of the sample complexity and convergence rate of SGD for the single-layer attention mechanism in eq. (1), we assume that the sequence data (X, y) is generated from the following Gaussian sequence single-index (SSI) model:
Assumption 1 (Data distribution). We assume training data (X,y) E BLxdd x RR* is independently drawn from a Gaussian Sequence Single Index (SSI) model:
SSSI (X) g(X ...)
(4)
where X E RRLxd is a Gaussian matrix with entries (0, 1/a), g: IK- + R is vector-valued link function that depends only on the scalar product of the input with a fixed vector w, E (d-1(Vd) and l is a integer that does not depend on d nor L.
Recent work by [Cui et al., 2024, Troiani et al., 2025, Cui, 2025] has shown that the single-layer tied attention model in eq. (1) is particular instance of a class of sequence multi-index (SMI) models, creating bridge between single-index analysis and attention-basee -based learning. This mapping implies that model eq. (1) can learn at best predictor in this class, justifying the choice for training data. The SSI model class was introduced by Cui et al. [2024] in the context of studying phase transitions for the attention mechanism. These results position the SMI model as signature synthetic model to study the interplay between attention mechanisms, data structure, and the dynamics of learning algorithms. Despite this progress, the learning dynamics of SMI models under SGD remain unexplored. Prior studies [Cui, 2025, Cui al., 2024] analyzed the empirical risk minimizer through the heuristic replica method, while [Troiani et al., 2025] rigorously studied the Bayes-optimal estimator for SMI models. However, a thcoretical understanding of the population landscape and SGD dynamics in this model is missing. Our work addresses this gap, providing the first rigorous characterization of SGD dynamics in SMI models by leveraging techniques developed for single and multi-index models.
Main results- Our main methodological contribution is the generalization of analytical tools to study multi-index models to variants that process sequences of tokens rather than simple vector inputs. Our contributions can be summarized as follows:

---

We introduce the notion of sequence information exponent (SIE), as generalization of the informa- tion exponent for single-index models Ben Arous et al. [2021]; the SIE has a direct correspondence with the sample complexity of SGD. We also discuss the implications of the positional encoding on the sample complexity, proving could help SGD to learn faster.
We analyze the speed-up introduced by the attention mechanism when learning sequential data, compared models not adapted to treat sequence structures, e-g. fully connected networks. For many problems, we show that the gain is proportional to the sequence length I. and in some cases even larger.
We investigate the interplay between the positional and semantic structure of the data following the setting from Cui et al. [2024], showing that SGD dynamics is not always able to disentangle the two and that rich phase diagram arises describing the structure of the corresponding population loss and the performance of SGD.
All formal claim are supported by rigorous proofs, as well numerical experiments; the code developed is available at bttps://gitten com/ http///deHIISSSSSeeeee Seaeeeennne-innneeeeeeee Index.
Further Related works- - There have much activity discussing SGD with synthetic data on multi-index models over the last decades or so, see e.g. [Ben Arous et al., 2021, Veiga et al., 2022, Arnaboldi et al., 2023b, Collins- Wioddin et al., 2024, Marion and Berthier, 2023, Montanari and Urbani, 2025] and reference there Information and generative exponent have been the topic of many works over the last few years [Ben Arous et al., 2021, Abbe et al., 2022, Damian et al., 2024, Troiani et al., 2024]. Here we discuss and adapt these notions for sequence models Troiani al. [2025].
On the topic of the Theory of SGD in transformers, Wu al. [2023] convergence guarantees on SGD for the single layer transformer. Song et al. [2024] also study GD convergence in simple architectures and highlight the existence of suboptimal local solutions. Li et al. [2025] point out that rapid convergence does not guarantee meaningful learning. Li et al. [2023] give sample complexity bounds for a shallow vision transformer. Zhang et al. [2025] being overfitting in SGD trained transformer. Yüksel and Flammarion [2025] focus on gradient- based dynamics for next token prediction tasks. Compared to these work we move beyond convergence results to study how the data structure, e.g. sequence structure and positional encodings, affect sample complexity and behaviours of the the population loss and recovery dynamics the high-dimensional limit.
Authors of Marion et al. [2024] introduce a model that can be seen as a sequence two-index model. While we assume the input data be iid Gaussian they assume spiked covariance structure in the data which makes their results not directly comparable to ours. We anticipate that our results can be generalized their setting. Another recent work Mousavi-Hossee complexity separation between attention- networks and more traditional architectures, while their setting different, this question is related to ours.
et al. [2025] looked at sample
1 Setting and definitions
Let (X", .y") E Lxd x R² denote i = 1,..., n samples drawn from the Gaussian sequence single- index model with weights w. E TRd and link function g. defined in eq. (4). As motivated in the introduction, our goal in this work is characterize the sample complexity of learning the sequence task (XT.y" with a tied single-layer attention trained under one-pass (spherical) SGD defined in eq. (2). Note that while the model might appear as too simplified because of the lack of correlation between the tokens, we will show that it is sufficient to capture the main features of sequence models.
As shown in the classical result by Robbins and Monro [1951], one-pass SGD can be understood as noisy discretization of gradient flow on the population risk (often refereed also as population loss):
R(w) Ex~A((014/a)
[(. SS! (X); fw))
Therefore, order to understand the dynamics in eq. (2) it important to understand the landscape of the risk above. The key property of single-index models underlying the convergence rate analysis of Ben Arous et al. [2021] that rotation invariance of the population risk implies that it only depends on single parameter: the correlation between the target weights and the predictor weight, also
3

---

known as an order parameter or sufficient statistic. A similar property holds for the family of SSI models defined by Assumption Indeed, conditionally on the weights, the following projections
P
X w. E R and 2 = x
w WER
vd
define joint Gaussian variables, which can be fully characterized by their means and covariances:
E [.,c] 0, E [ - e;
Cov (20,5) piy, Cov (ze, 24) = beg, Cov (2), 6eym.
where we have introduced the sufficient statistics:
T w w
Pw Vd
and
(8)
d
These play exactly the same role the overlap between target and predictor weights in the standard single-index model. Therefore, the population risk can be written as a function of these statistics:
}]
R(w) = R(e, m) = (=.)))
g(z.) - R softmax
Note that this formulation reduces the problem of understanding the landscape geometry of R in the w E Rd space to understanding in (e,m) m)) E IR a significant simplification when the token size d is large with respect to the sequence length L, the regime we will focus in this work. Note that, given the fixed norm constraint on wn the sufficient statistics are constrained inside the unit ball of R--1, (e,
s 1.
Escaping mediocrity - As previously discussed, studying the convergence rate of one-pass SGD is akin to studying the population risk landscape. In the standard single-index model, the picture arising from [Ben Arous al., 2021, Arnaboldi al., 2023c] is rather simple: the only critical points of the population risk are single global minima at the target weights and (possibly) strict saddle at zero correlation. Therefore, the convergence rate one-pass SGD from random initialization dominated by the time taken to escape this saddle-point, a scenario scenario commonly referred to as escaping mediocrity [Arnaboldi et al., 2023c].
As we shall see, the risk landscape of sequence models is richer, with in particular the presence of local minima. Nevertheless, these models share the common property of mediocrity at initialization, with the convergence rate dominated by the flatness of the initial saddle-point. Therefore, we start our discussion by formalizing this notion in the context of SSI models. In the high-dimensional scenario where d is large. the initial weight w" is approximately orthogonal to the target direction w., as well as the positional embedding P. Quantitatively, the sufficient statisties are distributed as
lim vd(ee, m²) NN(0, IL+1).
(10)
d
Namely, the initial value of the sufficient statistic (e", m²) (0, 0), with fluctuations of order 0(//Z). For the model in eq. (1), m) = (0,0) is saddle-point of risk, and the dynamics is divided in two phases:
The escape from the initial condition, where the model develops a weak correlation with the target direction w, and/or the positional embedding P:
Full recovery where it reaches a complete overlap with either the target direction w, and/or the positional embedding P: (e, 1.
As previously discussed, the first phase is the one that requires the most number of gradient steps Ben Arous et al. [2021], Arnaboldi et al. [2023c]: the sample complexity required for the first phase is always greater or equal to the one required for the second phase; after having reached small correlation with the target, the attention decay exponentially fast a complete overlapped state. Definition 1 (Weak recovery). Let 1 E (0, 1) parameter independent from d. We say that the model has weakly recovered the target when (e, m) 2 n)- The weak recovery time is then
weak ?
min
t 2 0: ||(eT, m )|| 2 n).

---

We use this definition of weak recovery as proxy for identifying the learning has happened, since the subsequent strong recovery will be faster. Figure shows some examples population loss surface: apart from initialization, there are no other critical points where the dynamic can get slowed down.
Finally, for simplicity of the discussion will make the following assumption the spherical one-pass SGD dynamics in eq. (2).
Assumption (Gradient flow approximation). We approximate the training dynamics of eq. via the following ODE, which corresponds to an order-2 Taylor expansion in 7/:
dw
7 2
E
w.
(11)
dt
where V.. ww
V is the spherical gradient. The time scaling corresponds to T/7
As shown in Ben Arous et al. [2021], Arnaboldi et al. [2024c], such an ODE captures both the right weak recovery time for a fixed 7, well the maximal value of y for which the dynamics do not stay trapped in the uninformative region.
The sample complexity of SGD
In this section, we focus on understanding the complexity of the SGD algorithm, i.e., how the number of total gradient steps n scales with the dimension d token embeddings, in the high-dimensional limit d >> I; for simplicity of exposition, we focus on the case k 1, but the same arguments can be repeated for each of the components of the output.
No positional encoding - We first focus on the case without positional encoding: P = 0 implies that the only relevant sufficient statistic is m. analogy with single-index models for networks can be done: For single-inde index models, the information exponent fully characterizes the sample complexity of the SGD algorithm Ben Arous et al. [2021]. The definition can be generalized for sequential data.
Definition (Sequence Information Exponent (SIE)), Given S a sequence single-inde index model, let g be the function that acts on the local field 2., we define the sequence information exponent as
i
[H (2))
SIE SSI == min Σ ky > O & BZ-N(0.22)
g(z)
+
#0
where Heg is the k-th order Hermite polynomial.
In Appendix B we provide more details Hermite polynomials. Let give some examples of SIE for different SSI models:
g ) = 2.,1 + 2. + Z. has SIE = 1;
g(2.) = Z,,1 = Her (z., He (2+.) has SIE = 2;
9(x.) Hey (c.,,))))((2..)))) Hez (2+,3 He2(2,,)) has SIE = 4;
g(x.) = -II Hev, (z..1) has SIE = Σl= kj.
The main feature of the information exponent is that it can be connected to the sample complexity of the SGD algorithm; we prove an equivalent result for the sequence information exponent.
Theorem (Informal). Let f SSS (X) be sequence single-inde index model. and let SIE be its sequence information exponent. If the model fw has a rich enough Hermite expansion, then the sample complexity of the SGD algorithm is
(2(d) Or(dlog" d) O
SIE
+
if SIE 2
if SIE 2
A formal statement of the Theorem and the proof are given in the Appendix C. It relies on the following connection between the flatness the landscape near initialization and the sequence information exponent:
5

---

2.
222 -0.0 7 ua
0.0
000
2.7
000 2.7
Figure I: the landscape of the population risk, together with the hessian at initialization, for different values of the SIE and positional encoding. (left) g(z,) Hes (=y(z..1) + Hez(z..2): SIE=2, no positional encoding: null gradient, but non-null hessian; (center-left) SIE=4, no positional encoding: the first non-null term initialization the 4th order; (center-right) g(x)) = Hea Hz.(z..1) dynamic dominated by the hessian, but we have a positive curvature the direction of e; (right) SIE=4, with positional encoding: hessian is positive semidefinite, and the dynamic is again at 4th order in direction of c. In all the examples L 2, = Ps. R Tr.
Heu(=,,2): SIE=2, with positional encoding: again
Proposition Define the flatness index k([sns SS.) of the model as
k(fw: SSI
min k 0: v R(O, #
where R is the reduced population loss defined in (9). Then, if the model fw has rich enough Hermite expansion, then
(fw S
SIE (fS!!
Intuitively, higher value of ş implies that the landscape R is flatter around initialization point (0, 0), and thus the number of gradient steps needed to build a weak correlation along either the e or m directions higher.
In Figure 1, we show some examples of the population loss landscape for different values of the SIE. Figure focuses on even SIE because the symmetry of Equation restricts the possible targets to even functions; in the Appendix D we discuss how to surpass this limitation, and we present settings with odd SIE.
The effect of positional encoding Despite the fact that positional encoding only acts on the trained model, and not the target function, it changes the population loss, potentially changing the dynamic at initialization. In particular, adding positional encoding increase the expressivity of the model, and can ultimately lead to faster weak-recovery of the SGD.
Lemma 1. Let fwo be a model with P = O that learns a target SSSI (X) with a given SIE. If we add positional encoding P the model, and let fnew be model, then
SST
fuus Ju.
SIE
SSST
In other words, the positional encoding can only decrease the flatness of the loss landscape, thus the sample complexity of the SGD algorithm could be reduced. The proof of this lemma is given in the Appendix C. In the right part of Figure 2, we present an example where adding the positional encoding can improve the sample complexity of the SGD algorithm. The left part of Figure 2 shows that the population loss land- scape at initialization flat, and the hessian is null: the first non-null term in the Taylor expan- sion is at order 4, hence the STE is 4. The right part of Figure 2 shows instead that when we add
N Foo a.l1
t00 -0.0)
N
0.11 -00
-00
-1.3
0
Figure 2: Population loss landscape for P = (left) and P * (right). Example of a case where SIE = 4, while SIE SIEpositional 2. Target: g(x.) 4/3 + Hes(21) + 22,, Pi Pz, Tr.

---

the positional encoding, a non-null term appears at order 2, and SIE posiiinii = 2. Note that while the positions of the global minima are not affected by the positional encoding, SGD can converge to the new local minima instead; more discussion on this point is given in Section 4. In contrast, the right part of Figure shows that the positional encoding is not necessarily beneficial: there are cases for which the loss landscape changes, but not the sample complexity.
3 The role of the sequence length
In this section, we focus first new emerging characteristic of the sequence single-index models over the vanilla single-index models: the sequence length L. Therefore, we neglect the effect of the positional encoding, by setting P O, in order to isolate just the effect of the sequence length. The goal of the section to measure the speed-up that a model like Equation (1) can achieve over the plain single-indes models when processing sequential data with length L.
Linear attention Our first goal is to understand the dependence of the convergence rate of SGD the sequence length. For that, consider the particular case of linear attention, given by the reduction map:
1 VL (1,1,..... 1) RR_.
R[A] ajett Aaright
with dieft
rright
(12)
Rearranging the terms
2
L L
L
= (flatenn(X (X) Wried (13)
fw) = T xz T
2j VL
aright
2
VL
i=1
where Wtied = concat(w,..., w) E RLd is the concatenation of L copies of This model equivalent to a generalized linear model with tied weights, and activation function o(x) x². In terms of performance, taking general activation will at worst be the same of the attention mechanism originally considered, not better. More precisely, we consider:
fw (X) = ( (flateenXX (X) Wiied
(14)
VT.
This is the most generic model we study in this section. Further numerical experiments elucidating the equivalence of the speed-up for this tied network and for the attention models can be found in Appendix E. Note that tied networks are not restricted to learn even function only, differently from the model in Equation (1).
The corresponding untied network- - Given the model in Equation (14), a natural benchmark is the model with untied weights. Let W E LRd be the matrix of weights, whose rows all updated with Equation (2), the untied network is given by
fw (X)= = o (flatten(X) flatten(W)
(15)
VL
Since we have L independent weights (the rows of W ) the sufficient statistic measuring the overlap between the model and the target SSI is not scalar as for the tied network, but vector of length L
W w.
|m VL
m
R
compacted to scalar Muntied
(16)
Measuring the speedup- The learning rate plays an important role in determining the number of gradient steps needed to reach weak recovery: the larger the learning rate (L) is, the faster the model learns. However, if it becomes too large, SGD will fail to converge, never achieving weak recovery. The gradient-flow approximation in Eq. (11) exhibits this effect: when y becomes too large the dynamic of the system is not attracted by w, or P anymore, and there is no learning. In order to have faithful measure of the speed-up, we will assume that the learning rate is taken to be the largest possible that guarantees weak recovery; discuss this upper bound on the learning rate in App. E.
7

---

Gain
quadratic fit
0.5
15-
0.6
10
0.1
0.0
01
2
Stepe
x 1010
L
Figure 3: Left: overlap mn for tied (green) and untied (orange) networks function of the number of gradient steps; different symbols represent different values of L. Right: measured gain function of the sequence length L, with the best fit line showing its scaling as L2 g(2.) Σ Heu(z..), d 1000, o = ReLU.
We measure the speed-up of tied networks with respect to untied networks, as measured in terms of number of gradient steps needed reach weak recovery, by the ratio of the weak recovery times in the two cases
nnuntied
gain L) =
(17)
weak
"
where Tyjuntied is given by Definition 1 where is replaced by muntled: the dependence of gain is subleading, and we will neglect it in the following.
Theorem 2. Let CSIE L be the first non-zero tensor in the Hermite expansion of g (see Appendix B). Then the gain satisfies with high probability
CSIE x (1..... (I.......)) ||CsSE
{1
iSE =1
gain
otherwise
If the tensor CSIE is orthogonally decomposable, in particular in the cases where SIE S 2 or is separable, then
CSSI x (1......1) ||CstEllop
2
{T.
iSSE= otherwise
gain
By definition of the operator norm, we have
CSIE (1.....1) 1) < <|CSseellop 7, /,E/2/2 and hence 0 gain $ 1, SEEv2
Since the untied network has L times the number of parameters compared to the tied one, naive parameter counting argument would yield gain
L (STE- expected gain. Counter-intuitivel the actual gain of using a tied network can either exceed or fall short of this naive value, depending on the function g. In pathological cases (see Appendix E), the tied network can even either fail to learn the target, or so slower than untied counterpart.
Example for SIE case, the SIE is 2 and the tensor C2 is simply the identity matrix Jt. The gain is by
Let's assume to have a target function g(z.) Σt Hez(z..). this
Tr. (" 1T2loop
(1, (1,.....1)) 1 1.
gain
Fig. 3 show numerical experiment, with ReLU activation, confirming the result of Th. 2.
4 Positional encoding and training dynamics
We now turn our attention to the role played by positional encoding the attention layer when trained under SGD. Since the focus is the effect of positional encoding, stick with class of target

---

functions that can exhibit either semantic (label mostly depends on tokens value, but not the order) or a positional (where tokens most important feature is their position in the sequence, rather then their embedding). Consider SSI target function of the form
[(aa= -a²) a² )
I se (X) (1 w) softmax (Xw.w, XT) + softmax
E R2x2
(18)
where he parameter w E [0, 1] allows the target to switch from semantic positional behavior, while the parameter E (0, 1] controls the alignment of the target with its positional part.
We shall train the model in Equation (1) with positional encoding P1 P2 and reduction map R the identity function. We focus on the gradient flow limit where is sufficiently small [Robbins and Monro, 1951]. Our analysis will focus on the population loss given by Equation (9), since it completely characterize the hehavior of SGD in this regime; the sufficient statistics (e, m) are the only free variables of the setting.
The sequential information exponent of this setting is SIE 2 (see Appendix F for the explicit derivation), thus the sample complexity for escaping the initializa- tion is Od log d). After the initial phase, SGD fast con- verges to the minimum of the population loss that is fully aligned with either the semantic the positional sufficient statistic, i.c. [e m)| = 1, but is not guaranteed to be the global minimum. Figure 5 shows example where the population loss has minimums, one semantic with (e, m) (1, 0) and one positional with (c, m) (0, 1), and the steepest direction at initialization, namely the eigenvector associated with the lowest eigenvalue of the Hessian, points towards the local one; in this case, the gradient flow will converge the wrong minima.
80-
0.5-
3 0.7
0.6
Unique
Uniqu Semonts: Minmss Micilgned Dynam::
Unique Postional Kiiin
05-
Clobal Misino
Global Semanti: Minino, Poezional Dynamic
Global Weltionl Mirlins
A770
0.25
0,50
0.65
0.50
0.36
100
Figure 4: Different behaviors of SGD de- Varying the parameters, w and a the high-dimensional pending the parameters and SGD dynamics from random initialization exhibits rich phenomenology. In Figure 4 we show the phase diagram with all the possible behaviors:
the population loss has unique positional minima, and the SGD converges to This is the case for w = and a
Unique Positional Minima:
Global Positional Minima: the population loss has both semantic and positional minimum, and SGD converges the global positional one.
Global Semantic Minima, Positional Dynamic: the population loss has both a semantic and a positional minimum, and SGD converges to the local positional one. This is the case where SGD does not converge to the global minima.
Unique Semantic Minima, Misaligned Dynamics: the population loss has unique semantic minima, and the SGD converges to it, even though the steepest direction at initialization points orthogonal it.
Global Semantic Minima: the population loss has both a semantic and positional minima, and SGD converges to the global semantic one.
Unique Semantic Minima: the population loss has unique semantic minima, and the SGD con- verges to it. This is the case for w = 0 and = 1.
We verify this by simulating many runs of SGD with different initializations and data samples. In Figure 5 we compute the empirical probability of convergence to the semantic minima, for 1 and varying w. The theoretical value of w where we have transition from sematic to positional dynamics is Wtrans 0.64, which is in good agreement with the transition observed in the measured probabilities; the transition becomes sharper as increases: ideally, in the limit -> Do we expect a step function. The simulations in Figure 5 are performed with d = 1000, and some finite size effects are still present. In Appendix we show present a more detailed analysis, including different values of d.

---

1.0
positional uinima probalality
0.6
0.4
SGD transition
0
0.0
0.4
0.6
0.8
1.0
Figure 5: (left) surface of the population loss for w 0.67 and a 1. The steepest direction initialization (green vector) points towards the positional local minimum, while the global minima semantic, Some examples SGD trajectories are shown in yellow: most them fall into the semantic local minimum, while some others manage to fully-recove recover the global minimum due to finite size effects (d 1000). (right) empirical probability of convergence to the semantic minima as a function of w for a = 1. The probability is computed over 64 SGD runs with different initializations and data samples. The theoretical prediction of the transition from semantic to positional minima is at 4trans 0.64.
Conclusion
In this paper, we introduced the Sequence-Singe Index model as a new, nigh-dimenssonal theoretical framework for analyzing single-layer attention architectures. The most significant contribution of this study is the definition the Sequence Information Exponent. This exponent, which serves as rigorous tool to quantify the inherent hardness and predict the sample complexity of Stochastic Gradient Descent, defined direct analogy with classical single-index models. This analysis transcends qualitative understanding, providing precise scaling laws for the required number of gradient steps, denoted by n. relative to the token dimension, denoted by d. We demonstrated that the sequential setting is significantly richer, showing how the sequence length L accelerates convergence and how positional encoding can proactively reduce the SIE, thereby lowering the computational barrier to learning.
This work establishes a foundational line of research essential for a principled understanding of modern sequential data models, particularly those based on the Transformer architecture. The intricate dynamics manifesting in the population loss landscape, exemplified by the identification of phase transitions and the convergence to suboptimal local minima, unveil wealth of avenues for future investigation. Subsequent research should aim to fully map these complex high- nigh-dimensiooal dynamics, develop techniques for robustly breaking inherent symmetries, and extend the SIE framework to more complex multi-index and multi-layer attention systems. We hope that this quantitative framework will stimulate further theoretical explorations, leading to the development of robust, generalizable understanding of learning on structured sequential data.
Limitations The theoretical analysis of SGD in Sequence Single-Index models is subject to several simplifications for tractability. Specifically, the model under scrutiny is a simplified, single- layer attention architecture where the key and query matrices are tied, the attention head dimension one (dhead 1), and the value matrix is the identity (V = Iz). It should be noted that the scope of this architecture is restricted to a specific class of target functions, including even functions, although Appendix D provides extension to this class. Additionally, the analysis operates under the assumption of token independence across the sequence, a crucial simplification that facilitates the execution of numerous sequence modeling tasks. The analysis of SGD dynamics is founded on the approximation of the discrete dynamics via a second- -order ODE (Gradient Flow approximation).
Acknowledgement- We would like to thank Luca Pesce, Luca Biggio, and Yatin Dandi for their insightful discussions. We acknowledge funding from the Swiss National Science Foundation grants SNSF SMArtNet (grant number 21 212049), OperaGOST (grant number 200021 200390), DSGIANGO (grant number 225837) and by the French government, managed by the National Research Agency (ANR), under the France 2030 program with the reference "ANR-23-IACL-00"" and the Choose France CNRS AI Rising Talents program.
10

---

References
David Saad and Sara Solla. On-line learning in soft committee machines. Physical Review E, 52 (4):4225, 1995.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, L1533)),7765--7677 2018.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over wwr-paaameterized models using optimal transport. Advances in neural information processing systems, 31, 2018.
Grant Rotskoff and Eric Vanden Eijnden. Trainability and accuracy of artificial neural networks: An interacting particle system approach. Communications on Pure and Applied Mathematics, 75(9): 1889-1935, 2022. doi: https//dboiorg/11..000/ppppp
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis neural networks: central limit theorem. Stochastic Processes and their Applications, 130(3):1820-183) 2020.
Luca Arnaboldi, Ludovic Stephan, Florent Krzakala, and Bruno Loureiro. From high-dimensional & mean-field dynamics to dimensionless odes: A unifying approach to sgd in two-layers networks. In The Thirty Sixth Annual Conference on Learning Theory, pages (199-1221) PMLR, 2023a.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22 (106):1-51, 2021. URL http: / org/ haaprs/vv2/222 1288. html.
Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pages 4782-4887. PMLR, 2022.
Emmanuel Abbe, Enric Boix Adserå, and Theodor Misiakiewicz. Sgd learning neural networks: leap complexity and saddle-to-saddle dynamics. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2552-2623 PMLR, 12-15 Jul 2023. URL httts:://proceeeeeeee mlr. w.r.ppess//vee wwteess/vvv//ee abbel3a....aa.aeaaabba..aaaaaa html.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 5413-5452. PMLR, 02-05 Jul 2022.
Alex Damian, Eshaan Nichani, Rong Ge, and Jason D. Lee. Smoothing the landscape boosts the signal for SGD: optimal sample complexity for learning single index models. In Alice Oh. Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, ed- itors, Advances in Neural Information Processing Systems 36: Annual Conference on Neu- ral Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, Decem- ber 10 16, 2023, 2023. URL. http: //pptt::::/ppprrssstpt papp/spppeerse/ nips. cc/ wttppprrrccpppppppcpppppmpppp..p 02763667 (1t.:/61111999221118877151bbbbd. - Conf
.ttml.
Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step at time. Journal of Machine Learning Reseurch, 25(349): 1-65, 2024. URL ptstt://jmmrr org/ httppppppe//55/5 2325-2232222 1543. html.
Alberto Bietti, Joan Bruna, and Loucas Pillaud- Vivien. On learning gaussian multi-indes models with gradient flow. arXiv preprint arXiv:2310.1991 197993 2023.
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, and Denny Wu. Learning in the presence of low-dimensional structure: A spiked random matrix perspective. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neurul Information Processing Systems, volume 36, pages 17420-17449, Curran Associates, Inc., 2023. URL https: https::/ wwwpeiinnnn........eee..ee neurips. cctpppppccpppppr.eeepppppppppppe sellee/paper//22/////// 38a167 1t..B6/0.077766ffffe41666661113. copeeaaeeeepppeeereoeeeeeeeeeeee .df.

---

Behrad Moniri, Donghwan Lee, Hamed Hassani, and Edgar Dobriban. A theory of -oneain feature learning with one gradient step in two-layer neural networks. arXiv preprint arXiv:2310.07891, 2023.
Alireza Moussvvi Denny Wu, Taiji Suzuki, and Murat A Erdogdu. Gradient- based feature learning under structured data. In A. Oh, T. Naumann, A. Glober- son, K. Saenko, M. Hardt, and S. Levine, editors. Advances in Neural Informa- tion Processing Systems, volume 36, pages 71449-71485. Curran Associates, Inc., 2023. URL
neweiis cece/pppr__fii_e wll.fflll/pppppl pttlls//ppper/22///11lee e21955c93dedde86Gat ootood/22er66777--aapr----oo-ff
pdf.
Aaron Zweig and Joan Bruna. Symmetric single index learning, In The Twelfth International Conference on Learning Representations, 2024.
Raphaël Berthier, Andrea Montanari, and Kangjie Zhou. Learning time-scales in two-layers neural networks. Foundations of Computational Mathematics, pages 1-84, 2024.
Luca Amaboldi, Florent Krzakala, Bruno Loureiro, and Ludovie Stephan. Escaping mediocrity: how two-layer networks learn hard generalized linear models with sgd. arXiv preprint arXiv:2305.18500 2024a.
Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luea Pesce, and Ludovic Stephan. Online learning and information exponents: The importance of batch size &: Time/Complexity tradeoffs. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 1730- 1762. PMLR, 21-27
27 Jul 2024b.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 31, 2017.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners, 2020.
Jacob Devlin Ming-We Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
Hugo Cui, Freya Behrens, Florent Krzakala, and Lenka Zdeborová. A phase transition between positional and semantic learning in a solvable model of dot-product attention. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 36342-36389, Curran Associates, Inc., 2024. URL nattps://ppet htttps://proceedingss neurips. cc/paper__ae ff fil.f/leaa/ee hea.ee//ppprr//22//55ee2 Stc00044ss1100999992000077. Conferrr pdf.
Emanuele Troiani, Hugo Cui, Yatin Dandi, Florent Krzakala, and Lenka Zdeborová. Fundamental limits of learning in sequence multi-index models and deep attention networks: High-dimensional asymptotics and sharp thresholds, 2025. URL https: / arxiv. org/ abs habb//250000000 00901.
Hugo Cui. High-dimensione learning of narrow neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2025()) 2025.
Rodrigo Veiga, Ludovic Stephan, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase diagram of stochastic gradient descent in high-dimensional two-layer neural networks. Advances in Neural Information Processing Systems, 11-23244-23255 2022.
Luca Arnabold,, Ludovic Stephan, Florent Krzakala, and Bruno Loureiro. From high nigh-dimensional & mean-field dynamics to dimensionless odes: A unifying approach to sgd two-layers networks. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 1199-1227 PMIR, 12-15 Jul 2023b. URL https: / http://///ocece....e/ooe mlr, waa..ppees//ee
html.
12

---

Elizabeth Collins-Wond Woodfin, Courtney Paquette, Elliot Paquette, and Inbar Seroussi. Hitting the high- -igh-simeniin notes: an ode for sgd learning dynamics on glms and multi-index models. Information and Inference: A Journal of the IMA, 2024. htlp:tts:://an semant comanticschoaa:: org/ heg/CorpussDD ID: 27351701..
Pierre Marion and Raphaël Berthier. Leveraging the two-timescale regime to demonstrate convergence of neural networks. Advances in Neural Information Processing Systems, 01944996-650299 2023.
Andrea Montanari and Pierfrancesco Urbani. Dynamical decoupling of generalization and overfitting in large two-layer networks. arXiv preprint 2.0Xivv:.50222/22666 2025.
Alex Damian, Loucas Pillaud- Vivien, Jason D Lee, and Joan Bruna. Computational computational-statitticaal gaps in gaussian single-inde index models. arXiv preprint arXiv:2403.05522, 2024.
Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, and Florent Krzakala. Fundamental limits of weak learnability in high-dimensional multi-index models. arXiv preprint arX.vv2205..555 15480, 2024.
Yongtao Wu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher. On the convergence of encoder- only shallow transformers. Advances in Neural Information Processing Systems, 36:52197-52237, 2023.
Bingqing Song, Boran Han, Shuai Zhang, Jie Ding, and Mingyi Hong. Unraveling the gradient descent dynamics of transformers. Advances in Neural Information Processing Systems, 37: 92317-922 18311-93351, 2024.
Bingrui Li, Wei Huang, Andi Han. Zhampeng Zhou, Taiji Suzuki, Jun Zhu, and Jianfei Chen. On the optimization and generalization of two-layer transformers with sign gradient descent. In The Thirteenth International Conference Learning Representations, 2025.
Hongkang Li, Meng Wang, Sijia Liu, and Pin-Yu Chen. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity. arXiv preprint a5X1v:2302.06015 2023.
Yingying Zhang, Zhenyu Wu, Jian Li, and Yong Liu. Understanding generalization in transform- ers: Error bounds and training dynamics under benign and harmful overlitting. arXiv preprint 22050 2025.
Oguz Kaan Yüksel and Nicolas Flammarion. On the sample complexity next-token prediction. In The 28th International Conference on Artificial Intelligence and Staristics, 2025.
Pierre Marion, Raphaël Berthier, Gérard Biau, and Claire Boyer. Attention layers provably solve single-location regression. arXiv preprint Xiiv22410.00537 2024.
Alireza Mousavi-Hosseini, Clayton Sanford, Denny Wu, and Murat A Erdogdu. When do trans- formers outperform feedforward and recurrent networks? a statistical perspective. arXiv preprint
arXiv:2503.11272. 2025.
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Math- ematical Statistics, 22(3):400 407, 1951. doi: //doi. otbo:.oorg/..... 1214/ aoms/ wttom//11700 1177729586.
11777995877777 URL https:
Luca Arnaboldi, Florent Kızakala, Bruno Loureiro, and Ludovic Stephan. Escaping mediocrity: how two-layer networks learn hard generalized linear models. In OPT 2023: Optimization for Machine Learning, 2023c.
Luca Araaooddi Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iu- vant: Data repetition allows sgd to learn high-dimensional multi-index functions. arXiv preprint arXiv:2405.1545, 2024c.
Elina Robeva. Orthogonal decomposition of symmetric tensors. SIAM Journal on Matrix Analysis and Applications, 370)):86-102, 2016. doi: 10.1137//409893440 URL https://doi. org/ 10.
1137/140989344
Harold Grad. Note on N-dimensional hermite polynomials. Communications on Pure and Applied Mathematics, ((4):325-330, 1949. ISSN 1097-0312. 12. doi: 10.10022/qa.31102224222
13

---

A Reduction from attention to sequence single-index
Let X E Rxxd denote sequence of length L of d-dimensional tokens, and consider the standard dot-product attention:
QK
Attention (X) softmax
(19)
Vihead
where Q + P) K k) V = (X + P)Wv E BLxxdoa are trainable weights known as the query, key and value matrices, respectively. The matrix P E RL is the positional encoding. fixed matrix needed inject representation of the position of the tokens in the sequence. To make the analysis tractable, [Troiani et al., 2025] considered the following simplifying assumptions:
Key and query matrix are tied, and dhead 1: Q K X w R
Identity value matrix V= == IL.
Note the second assumption is mild for single-layer attention, since we do not need to learn new representation of the sequence. Under these assumptions, eq. (19) reduces to:
TiedAttention(() softmax (Xww") xT)
(20)
This is a map from sequences X E RLxd to L x L matrices. Further adding the reduction map R: gLxL + R* we get the model in eq. (1). Finally, get the reduction sequence single-index model, it suffices to consider P = 0 and the map real-valued sequences s E IR:
g R softmax (ss)
(21)
B Mathematical preliminaries and notations
B.1
Tensors
We consider tensors as multidimensional arrays: tensor T order i and dimensions (di,..., de) simply an element of IR x,,,,,,, Its elements denoted by T.,.. where [de]. The scalar product between two tensors with same dimensions is defined as
(T,T)
Σ Te T T.....
61....8k
We say that a tensor is symmetric if all its dimensions are equal and for any index (f1,.... .4)) and permutation a E S+:
Te Tott
We shall need two operations on tensors: the first is the tensor product, that turns two tensors of order k, into tensor of order defined as
(T & T") "i = Tr. Ti.-
The second is the tensor-matrix contraction: given tensor T of order k, an index & and matrix M of size de x d'e, the tensor T X M is defined as
(T X2 M)....... i.........
Σ Sn Mari
Given & matrices (1)) ..... (A), we will use the shorthand
T x (1)) T x (1).... M
Immediate properties of those operations are gathered in the following lemma:
Lemma 2. The operation x is associative: if is tensor and (L) ,,, M())), (N.)),..., N(0) are matrices with compatible dimensions,
(T x (a((),,.,,(R))) M(K) x (N(), (N())...,NNO N(() = T (M)) M()
Let E BR xu and (II...., T3) E Rd x ... x Rd Then (T, 2 X xbk) T x xxxxxx11 (I), (21....,3)) 3kk
14

---

Odeco tensors Since tensors of order k 2 3 are sometimes hard to handle, we work with restricted class. We say that symmetric tensor T odeco (short for orthogonally decomposable, see Robeva (2016]) if there exist real numbers \1 Xy and orthogonal vectors vi,...; : such that
T
X
2m
In partieular, all tensors of order (with 1) and (with equal to the rank of T) are odeco.
B.2 Hermite Polynomials
In this section we provide our definition of Hermite polynomials. which are used in the construction of the Hermite basis, both for the one-dimensional and the multidimensional case.
Gaussian measure and Gaussian e² space
We define the Gaussian density in p dimensions
wp(x)) (2x)
exp
and dwp((x) wp(x))d.. This measure defines space e (wpp of functions f satisfying
If Ilfl : : ((x))( < oo;
it is Hilbert space w.r.t the scalar product
(f. (f.9) -
f(xr)(())du
Hermite polynomials and tensors Hermite tensor Hy as
We follow the conventions of Grad [1949]. Define the k-th
H4 (-1)4 V V'up:
Wp
where & is the k-th order derivative. This results in k--th order symmetric tensor of size p X p. The Hermite tensors are orthogonal, in the sense that
((H4))....e) (Hee),...
if and only if k == l and (f..... i is permutation of ,J..... -e).
When 1, all Hermite tensors are scalars, and we get the usual Hermite polynomials:
Heo(a) = 1,
(22)
He (z) = E,
(23)
Hez(x) = x² -1 -1,
(24)
Hey(r) = x² - 3I,,
(25)
Her(s) = x² 6x + 3.
(26)
Hermite expansion The orthogonality properties of the Hermite tensors imply the following theorem:
Theorem 3. Let f E ((up)) There exist a unique sequence of coefficients (C&(J)) kzo such that
(f) a tensor of order k and
f= (CE())
(27)
120
Those coefficients are given by the following formula:
1 Ca(f) ke
f ( ((x)))((
Further, the scalar product (c, /w be written
(f.g) Σ (C.(f)
K20
15

---

The proof of this theorem can be found in Grad [1949]. The identity (27) is called the Hermite
expansion of f. and the (f) are its Hermite coefficients
Finally, by invariance of the Gaussian distribution through orthogonal transformation, the following holds:
Lemma 3. Let g RP - R,, and W E IRpx4 be a matrix satisfying WW = 1p. Let s(x) = >(Wx.) Then
Cx(f) = Cx(g) x (W....,W) W.
When and w is a single vector, we get
CR(J) C2: (g)
This gives rise to link between odeco tensors and separable functions: Lemma 4. Let IR + R be separable function, such that
g(z) Σ g((z),
W E Rex orthogonal matrix, and let f(x)) g(Wx). Then wx).
8 Ca(f) = Σ (g
and in particular every Hermite coefficient of f is odeco.
C Formalization and proofs
C.1 Preliminaries
We consider the following approximation of the SGD dynamics:
dw -E V C(X, y, fw)) E V y, fa)) 11
w
(28)
dt
The results of Ben Arous et al. [2021] (when m is scalar) and Arnaboldi et al. [2024c] (when m is a vector) imply the following:
Theorem 4. Let Ty be the weak recovery time of the ODE (28), with the same initial conditions as the process (2). Then for small enough and any ō > 0, there exist constants c(8), C(8) such that if
cd))(
(29)
then with probubility at least 1 - 8
1 S C(6)dT?
On the other hand, for any t S C(5)dr2 if S c(f) 11/2, then with probability
* 2 c(6)
When y does not satisfy the bound (29), cannot show strong enough concentration around the deterministic ODE dynamics, and hence directly showing non-convergence of (2) is difficult. However, as we shall see in the proof, above this value of 7 the inhibitive term in (28) dominates initialization, and hence the ODE dynamics stay trapped around zero overlap with the target subspace. For this reason, we shall consider (in line with Ben Arous et al. [2021]) that the sample complexity cannot be improved by increasing above the bound (29).
Remark. When 7 is instead fixed below the value (29), the hitting time of the dynamics is instead given by
(7) Tq.
We shall also assume that mg O, and that the coefficients appearing in the gain expression in Theorem 2 are all non-negative. As mentioned in Ben Arous et al. [2021], Amnboldi et al. [2024b,c], this condition can be ensured with probability 1/2 by randomly setting the learning rate +- with equal probability.
16

---

C.2 An ODE for overlap evolution
We begin by computing the expectation of the gradient term:
Lemma 5. In the tied case, have when | =
E[((X, y, Sheed) = Ely²] - Σ
cx(o)Ca(g) x (Iz...., 11)m² +|lo]lw-
k20
In the untied case, we have instead
[[ 1/ Sunsied)]
Ely²)] - Σ
cx(o))((g)) (m,...,m,) m)) + || k20
Proof.
Recall that L(X, U, f) = (y -y- ((X)) 1³² ( For simplicity, define
w
0
0
w
Wtied = (w w w... w) E RdL
Wnniidd = (ul...W1 1R and W
IR
LxdL
0
un
Then, for D e {tied, untied), have
fo(X) (w flatten(X))
and v(X) g(W" -laaten(()))
VL
Since [latten(X), is a standard normal vector, and both VL use the Hermite expansion properties to find
wh and vL VL
are orthogonal matrices, we can
{[fn(X)u(X)]
Σ [(C((1)).
k20
Σ (ox(o) 2k ( x (W (W....,,"")
k20
ca(o)C((g)) x (W*wn. wn.... (wwm)
420
In the tied case, we have W Wnidd m1, t. while in the untied case W Wnnied m. For the last term, we have in both cases (w0 flatten (X) ~ No 1) whenever || = L, and hence
VL
[[fo(X) ||
This ends the proof.
When || w|| (resp. ||w:|| is different from one, the expressions of Lemma 5 depend on g = =||z0|] (resp.
= =||ws ()) However, we can write
Ew y, fuea)] = 3m
E[[(X, y, fwe))] + Og
E[[(X, y, (w.
As result, have
V EIXX, frica]] = ( θ E(C((X y, Snoaa)] (wo (oo--ma))
pm
The same holds for the untied case:
0 ELC(X, y, Sicaal] (w0- m,
L[,,, v. frcal =
0m,
We arrive at the following result:
17

---

Proposition 2. Define the drift functions
(m)) 2(1 m)²)
kcp (o)(())a)))) (I 1t)m
k20
Qumtied m)) = 2(1 m o m)
cx(o)C((g) x (Lz, m.... m...,,
#20
Then the tied and untied overlaps satisfy the the following ODEs:
dm
2
dt (nea(m)) -
V L(x y; fw]
m
(30)
dm Oomnied m - B Vin y, fw]
m
(31)
dt
C.3 Controlling the gradient norm
We turn our attention to the inhibitive terms in Proposition 2. We show the following: Lemma 6. There exist an and two constants c, C such that if m < n (resp. ||m|]| S m))
ed = 1 V
v.
sCd
Proof. We only treat the tied case; the untied one is done similarly. Differentiating the loss w.r.t w. we find
((X,8.f) 20' ( (ar (futris S flatten())))
(a(((t
v(x))
E, x;
VL
VL
VL
We write æ, x. + xx, where a!! is the projection on æ; on the subspace spanned by w and wt.
Then
V C 20' (wWaec ( flatten (X)) ( VI
(
(2W flatten (X)) (X))
E.(I ww )x! + +, x.
v(x)
VL
VI
Importantly, the vector x.!- is independent from any of the prefactors, and has norm dl - while the first vector is fixed-dimensional Gaussian. As a result, we have
E V
(x))
0(1)
remains to show that the expectation above is bounded away from zero. Assuming that the labels centered for simplicity, when m the expectation simplifies to
Lo E fw (x)
[(x))] + EE
[ fw (X)*
> 0.
By continuity, we can choose 17 > 0 such that if |vr| S
Lo E (X) 2
2Lo.
which ends the proof.
C.4 Hitting time for the tied dynamics
We are now ready to prove Theorem 1 (as well as part Theorem 2). In light of Theorem it suffices to compute the hitting time Tn of the tied dynamics (30). Since (ria(()) 20sTE X (1....., 11)mStE- OmB))) there exists an Thied > 0 such that if m Thied
eSIE (O) (1,,.. 1 1 SIE-1 < (m) < 3CsIE(o CsSE (I....., 1, 1 SIE
18

---

Combining this with the bound of Lemma 6, we find that whenever m(() I 17 for some constant
0,
dm
dt 2 c. CSIB x (IL...., 1s Jm SIE-1
Cyydm
For any 8 > 0, there exists a constant k(6) such that with probability at least 6,
x(0)
m(0) Z
vd
As result, when S ((6)SIE-1C-11 SIr
then for 0 S S
dm
d CSIE x (Ins..., STE-1
di
This implies:
when SIE
m(t) 2 mo + CSIE x (I 1t)
C'n
hence Ta s CSIE x (In,..., 11)
2
when SIE = 2.
CSIE (I .111 /2)))) hence
C' C'In(d)
m(t) 2 mg exp
Ty Csie (Iz...., 11)
2
when SIE 2 2.
m(t)= 2 (m CSIE x (1...... 1x) SIE-2
B1B
hence
Tn S CSIE (I....., 11)
2
The bound on 7 above is always weaker (up to constant factors) than the bound S C((dT) of Theorem 4, and hence always have
1 CdT
which corresponds the statement of Theorem 1. On the other hand, for any 2 we have
dm
3CSIE X (1L,..., 1 1m)m
dt
which by the same reasoning implies that the bounds on Tú that we obtained are sharp up to constants.
C,5 Hitting time for untied dynamics
We are now ready to finish the proof of Theorem 2. Since
@untied (m) 2csiE(a)CsıE (Jz, m...., m) + 00 m |SIE)
for small enough 17 > O we have for t S Ty
d||m| dt
CC CSIE (m...., m) +|[Cseellll [m| SIE-1 (C + 1)l[CsIel| -||m|| SIE-1
Recall that the hitting time untintied corresponds to mal hitting the threshold nVLL L. As result, since the dependency r7 is of leading order only for SIE 1, we find
nVL log(d) d SuE
SIE if SIE
Ty untiedd
>
if SIE
Since the gain satisfies
2
Tyjuntied
gain x
Tn
19

---

this proves the first part of Theorem 2.
For the second part, assume that Csue is odeco, hence there exists A1,- - dr. and orthogonal vectors V1.... 1r. such that
OSIE
Σ M
We assume that the A, are ordered by absolute value, so that [CSIEll = |A1l Letting m (m, U1). we have
11 CSIE x (Jz, m.,..,,, m)) = CSIE x (V1, m, m) = (m
For small enough 7, this implies that
dm (1)
2 csull (m (m))--
dt
Since |||]] 2 m1) by the Gauchy-Schwaadd inequality, the hitting time Tnmmmiedd is at most that of ml)).
and hence
TvT log(d) 8IR d
if STF
C
Tyjuntied S
SIE
||CSIE|
if SIE 2
This closes the upper bound of Theorem 2.
C.6
Proof of 1
Let Reew (e, m). R(m) be the reduced population losses for the model with and without positional encoding, respectively, so that R(m)= = Rmne (0,m). m.) Then
I Roow
d R
(0,0)
dm (0),
dm
and hence V R(0) * 0 implies that V Rnow + 0.
D Sequence Information Exponent Beyond attention
In the main paper, we discussed the learning of generic Sequence Single Index model with parametrized model like Fquation (1), with the goal of modelling the attention mechanism learning. The theory of Sequence Information Exponent goes beyond this, and can be used understand the sample complexity of the learning of generic sequence single-index model both as target and as trained model. this Appendix, we focus on particular choice of positional encoding that breaks the even symmetry of the model, allowing attention weakly recover odd SIE targets. In particular, we consider dynamical positional encoding the form:
P.
un + P v
with P: 4xd fixed vector.
(32)
CE LRL is a fixed vector of coefficients. We call this special version of positional encoding injected positional encoding. The trained model becomes:
]
P vd
P Va
fn [w) = R softmax
x
ww
x
+ cc.
(33)
and it has now non-zero odd Hermite expansion. In Figure 6 we show examples of population losses with odd targets, learned with the model in Equation (33). The injected positional encoding breaks the symmetry, as the population risk plots show.
20

---

Figure Population of model Equation (33) with targets. (left) g(z.) Hei (2.,1) Hei (z.,)).
no positional encoding: (center-left) g(z.) = (z..1) + Hei (z1,2). injected positional encoding: (center-
right) s(z.) Hea(z..1 - Hea 2x. (2..). positional encoding; (right) 9(z.) = Hea(z + Hea(z,.2).
injected positional encoding. 2, P = order to isolate the effect of the injection.
E Further analysis on the effect of sequence length
The aim of this Appendix is to clarify and give further examples on Theorem 2. Here we provide an intuitive explanation of the result, while the mathematical details can be found in Appendix C.
Let's start from the main result the gain, that be broken down in three parts:
gain (gain at costant 7)
(
Ttied
(special factor for SIE = 1)
(34)
Yuntied
The gain constant ? This speedup comes from the different structure of the two networks, the tied one can built up correlation faster than the tied one because it compose L different signals. The strength of this effect strongly dependent on the target function, the overall result
gain constant 7 CSIE X (1.....1)
(35)
||Csıellop
The ratio of the learning rates In Appendix C, we showed that the the learning rate grow with the sequence length L at most as
for the tied network
Vtied E CSIE x (1,...,)) 1),
for the untied network
Yuntied S 1|Csuellop
clear that saturating the bounds above leads to a factor
Teled
max Yeled
CSIE x (1.....)
(36)
Vuntied
max Yuntied
|Csiellp
that exactly the same as the gain at constant y, Obviously the gain measure is fair only the learning rates bounds are saturated, but our result predict the speed-up factor even in the case where the optimal learning rates are not used.
The special factor for SIE = 1 The case SIE = 1 is special because the dependence of the weak recovery time on the constant r is not negligible, differently from the cases SIE > 2. This slows down further the learning of the untied network, by a factor VI., leading factor
SIE > 2 SIE
special factor for SIE
(37)
VL
E.1 Example at not optimal learning rate
In Figure we presented the speed up in the case of a target function with STE: = 2, and optimal learning rate for both the tied and untied network. Here want to show that result predicts the
21

---

x10#
1.0
United Ene
Goin
Untted w.r. time
Line fit
0.8
Tedd fit line
Tidd time.
10.0
0.6
Coosing
7.5
2.5
0.0
0.5
1.0
1.5 1100
10
15
20
5
10
Stepe
Figure 7: The gain in the case of a target function with STE 2, where both cases use the same learning rate Yo 0.005. (left) The evolution of the overlap, (middle) the weak recovery time and (right) the gain. The gain proportional as predicted.
gain well even when the learning rate are not scaled up optimally. particular, consider the same setting as in Figure 3, but with the learning rates
Viied Tuntied costant with L 7oo
(38)
Using Equation (34) we can predict the gain as
gain ~ L. L.
(39)
In Figure 7 we show the result of the simulation, where we can see that the gain is indeed proportional L, as predicted.
E.2 The upper bound of learning rate scaling
In this subsection we want to show an example proving that not all scalings of the learning rate are allowed: if it grows too fast with the sequence length, the network will not be able to learn.
Let's take as example the SIE 1 target function
g(z.)
(40)
VT.
with the corresponding leading Hermite tensor
C1 (1/VE
I/DD E ERL.
(41)
We know that the maximum scaling for the learning rate of the untied network is
Tuntied SIICillop 1,
thus stick with constant learning rate "/o for both networks
Vied Yuntied Yo 1.
(42)
We can use Equation (34) to have the theoretical prediction of the gain in this case:
C1 x (1,....
VL
gain vL VL
(43)
Figure 8 we show the result of the simulation, where we can see that the gain is indeed proportional to L. as predicted. We can now ask what happens if we push the learning rate scaling of the untied network beyond the limit of Theorem 2. If we set
Vuntied = "iied = 700 L,,
(44)
the ratio between the learning rates becomes now "riie /rautiied = 1/r, and the gain
gain VL 1 -I=1.
(45)
Apparently, the untied network performance matching the one the tied network. Figure 9 shows the result of the simulation of such case: the learning rate of the untied network is too high, and the network not able for large L., and thus the gain diverges with a maximum value of This plot proves our bounds the learning rate scaling indeed correct.
22

---

Untied
0.8
8000
Untied
30
Line
Tind Eit line
Tioi w.r. time.
6000
20-
Crossing
0.4
0.0
25000
50000
7G000
100000
10
20
30
10
30
Figure 8: The gain in the case of a target function with SIE = 1, where both cases use the same learning rate " 0.005. (left) The evolution of the overlap, (middle) the weak recovery time. The gain proportional to L, as predicted. d 1000, ReLU
Plain
Plam Tied
Fitted
0.15
Croseing dine
6000
4000
0.05
150
Stops
Figure 9: The gain in the case of target function with STE 1, where both cases the same learning 7/o 0.005. (left) The evolution of the overlap, (middle) weak recovery time (right) the gain. The gain diverges, as predicted. d = 1000, a = ReLU
1.0
Crowing lime
0.6
0.4
Tial Notwock Et
0.2
0.0-
Salmas Alsatiio fit
polats
Soctmax Atteution pelnts
0.0
-0.5
0.0
0.5
1.0
1.5
2.0
Steps
X200
Figure 10: comparison between the learning of the tied network with squared activation (orange), namely linear attention, and the single-layer softmax atlention (green) (left) The evolution of the overlap: each symbol is different value of L. (right) the weak recovery time. The networks learn at the rate, but with different costants, g(*.) = Etn ())(z..), d = 1000, ReLU
23

---

E.3 Equivalence between Single-Layer attention and Tied network
In the main paper we proved that the tied network model generalization of the single-layer attention model. In particular, if the activation function is o (z) = x², the tied network is equivalent to the single-layer linear attention. We also claimed that adding non-linearity to the attention can only improve the performance of the network, although not affecting the scaling with the sequence length. In Figure 10 we show the comparison between the learning of the tied network with squared activation (orange), namely linear attention, and the single-layer softmax attention(green The two networks learn at the same linear rate, but with different growth constants. Softmax attention performs better than the tied network with squared activation for sufficiently large sequence lengths.
E.4 Pathological cases
Theorem 2 shows that there could be cases where the gain from learning is O, meaning that the tied network cannot learn anything, while the untied one possibly can. In particular the degenerate condition happens when
OSIE x (1.... 1) = 0,
(46)
where Theorem 2 guarantees that the gain is O. Examples of such pathological cases are:
STE
1: possible pathological target could be g(z.) 2,,1 2,,2.
In this case the leading term in Hermite expansion is
C = ( and consequently C1 0.
STE = 2: anlogously, a possible pathological target could be g(2.) = 24,2
In this case the leading term in Hermite expansion is
1 0 -1
and consequently C2 (1 1) - 0.
C2 =
In Figure 11 show the pathological case for STE 1 and STE 2. The untied network is not able to learn the target function because of the symmetry: the tied network is by design symmetric, while the target is constructed to be as antisymmetric as possible in the sequence length. The untied network instead is able to learn the target function, because the weights are not constrained to be equal, thus the symmetry broken by the initialization.
0.35
0:35
Tied Let
N.twork,1-22
0.30
Tixl Notwork, 1-
0.30
Plain L=t
Tiel Network,L=10
0.25
Plain
0.25
0.20
Plain Network L
Plain Netwock L-
0.35
0.10
0.30
0.05
20000
00000
00000
80000
100000
0.0
0.2
0.4
0.6
0.8
1.0
Stepe
Stege
x10"
Figure 11: Pathological cases for SIE = 1 (left) and SIE = 2 (right). The untied network is able to learn the target function, while the tied one cannot.
The degeneracy of the tied network could be solved by weighting randomly the neurons, In that case, almost surely we have
CSIE (1, 1) + 0.
(47)
Although this a possible solution, we leave the study of the effect of random weights fro symmetry breaking for future work.
24

---

Further discussion on the positional-semantic transition
F.1
SIE of model (18)
Definition 2 of the sequence information expoment does not apply directly to the model (18) because the model has non-scalar output. However, can still extend the concept of SIE to this case by looking at the update rule of sufficient statistics around initialization.
The population loss function is given by
(1 - w) softmax (z.2.) + w softmax
(-ao
a²
-a²)
softmax (2z1)
R(e, m) =Ez,z.~(een P(e.))
a²
Ez,z. [2(2,
(48)
with
0
m
0
0
P(e, N
0
1
0
m
(49)
m
0
1
0
0
m
0
1
easily show that the gradient of the population loss is 0 at the initialization point (e, m) = (0, 0). Let p(z., e, m) be the probability density function associated with the distribution P(e, m). Then the gradient initialization is
Using parity arguments,
(e..))(Z., ((z,2.)
V (e.m) R(e, m)
= P(e.x.
(50)
c=m=0
2;0,,
C(z., 2) is an even function of 2z., while the gradient of the probability density function is an odd function of (z.,2) Therefore, the product is an odd function of (z., z) and the expectation is 0.
(e,m) R(e, m)
(0,
(51)
e=
We can use the same computation technique to compute the Hessian of the population loss at initialization. This time the parity arguments does not apply, and we can show numerically that the Hessian is non-null
0²R R
0²R dm
O²R
+ 0.
(52)
dea
dedm
e=m==0
emmm=00
The information exponent We can also compute the information exponent by looking at what rate grows around initialization. We use spherical gradient descent beacuse assumed the norm of the vector w to be costant (as Ben Arous also does in his paper on Information Exponent):
The update rule of wr is
2D 7 V
Vd, I 7 V vw
multiplying both sides by w./a we get
m 7 W.
Vd.
m
| - 7 N.
We can assume to be in the gradient flow regime, where the learning rate <1
R vdy 1 27 w V VnL
ww Vw = v|lwl|2 2yw
that finally lead us to
m - w. vwL
(1 (1+7 w VnL
W. Voll
w V
m 7+1
2 m -
d +
(53)
d
25

---

1.0
positional trinimao probabiity
0.4
0.2
SGD transition
0.4
0.6
0.8
1.0
Figure 12: reproduction of Figure 5 for d = 100. The transition is smoother than in the d 1000. Averaged over runs.
where in the last step we used again the small learning rate limit.
Now we can use the chain rule for getting the gradient in terms of the derivatives we already have
UL
V + Oc
de Vwe Oc w dm d de
ac p
v.L=
+
3m
vd
can rearrange equation above as
m -.. m m
Dc P Vd
+w- OC w. Oc p
OC
OL Ōm
OC de
+ +e
7/a
3m d
de
3m
d
de Vd.
dm
where we used the fact w. x 0 in high dimension (as already assumed above), and Iw = d.
We are interested in what happening at initialization, therefore all the derivatives should be evaluated around (e, m. O. We already know that V Ve,mCl.
0, so we expand the at the next order in
m
m
OLC
8LL
2me
7/a
dm2
dnde
m..e00
1m.e=0
We can repeat the same derivation for finding the analogous equation for e:
e ++1 e²
02L
O2C
3/a -
DE
+ 2me
Omde
m.e=0
m,,==
Since the hessian of he loss has always a negative eigenvalue, both these equations need (d d) to escape neighborhood of initialization, leading to IE
F22 Numerical experiments on the transition
In this Appendix we would like to provide more details on the phase diagram of Figure 4.
In Figure 12 reproduce Figure 5 for d 100, clarifying the finite size effects claimed in the main text. Smaller values of lead a more smooth transition, since the grndient flow assumption is less valid. In the limit d'
we expect to see step function.
The yellow region in the phase diagram of Figure is predicted have unique global semantic minima, while SGD is aligned with the positional direction at initialization. The resulting trajectories are shown Figure 13: the dynamics moves towards the minima direction, get stuck the local flat (but not critical) region around (e, m) (1,0), and then it moves towards the global minima. In this region the convergence very slow. The turning point of the dynamics is bit misplaced because of the numerical errors given by the loss integration; details on this in Appendix G.
26

---

0
0
m
Figure 13: The loss surface in the yellow region of the phase diagram. The SGD trajectory shown in yellow. The training moves towards the direction orthogonal to the one of global minima, ultimatcly slowing down the convergence.
F.3
An alternative model without phase transition
In order to highlight the peculiarity the model (18), we present an example a model that does not exhibit phase transition between the positional and semantic regimes. Let's assume that target a softmax attention matrix with positional encoding
v(X) = softmax
[x P.IVajw., P.//va)]
where
P. =
+p. PP
w. = VI- wpp.V. Vd
with w..P..
plays the same role in the model (18), and to get the positional model. The difference is that this case the positional encoding is added to the input of the softmax function, while in the previous model it added the output. This change has a significant impact on the behavior of the model.
set 0 get the semantic model, 1
The gloabl minima of the population loss function does not transition from positional to semantic regime, but rather smoothly move from the semantic to the positional regime as w increases. We leave the details and numerical experiments for future work.
G Numerical experiments details
All the codes used run the experiments are available at https://github com/ IdePPICP/ Sequence- Sequence-Single Index; where details for reproducing figures are not available in the paper, we provide the code reproduce them the repository.
The experiments run on a Mac Studio M2 Ultra, within at most few hours for the largest ones. The code is written in Python, using the libraries numpy, scipy, torch and matplotlib. hydra is used to manage the configuration files.
G.1 Details the integration method of squared loss
All the plot of population loss we showed are a numerical integration of the loss function. As showed in Section 1, the population loss is given by multivariate Gaussian integral of 2L dimensions, where the mean and the covariance are determined by the sufficient statistics. The integral can't 't be computed analytically,
custom numerical procedure based the Gauss-Hermite quadrature.
Let f: 222L be function of 2/. variables be integrated, let la E 2R and 5 E T22x2L be the mean and covariance of the multivariate Gaussian distribution. The integral want compute
27

---

is
1=
22 (2 exp
f(x)
1
(-1 (x (-2(2
pi) E
(x 10)
dx
(54)
The numerical procedure as follows:
(i) Compute the 1D Gauss
Gauss- Hermite nodes and weights for Nint points
(
Nur and {we)t
Min
where z; are the nodes given by the roots of the Hermite polynomial H (x) and wy are the corresponding weights, computed as
N Wi Nint!
1
Hi (x:)²
(ii) Compute the 2L dimensional nodes and weights by taking the Kronecker product of the 1D nodes and weights
2L
2L
N22
Mus and {W
N
(wihen
Naa ==
i=1
(iii) Let 7 be the Cholesky decomposition of Σ, i.e. E = T T.
We can then change the variable
to y T-1 (x p.) and compute the integral as
f(z) (2T)
exp
- --)
1 (-2(0=
1 - p1) do f(a. f(Ty+R) (2x) exp
(-2" 8) dy
RaL
(iv) The integral can then be approximated, as
NaL
2L
1
II Wil f(TX, +
The precision of the integral is obviously regulated by the number of points Ni we use. our experiments, we used Nine 17, while for the phase diagram in Figure 4 we used Nitt = 19. Some effects of this integration error visible in Figure 13.
28

---

NeurIPS Paper Checklist
(i) Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We state all the result clearly in the Main Result section.
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 in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
(ii) Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We state all the assumptions made in the paper and discuss their limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on 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 images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
(iii) Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
All hypothesis and proof of the theoretical results are reported either in the main paper in the appendix.
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 if they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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.
(iv) Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
We release the code used for the experiments, as well as an appendix with details on numerical simulations.
Justification:
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 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 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 can also be provided via detailed 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, or other means that appropriate to the research performed.
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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
30

---

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?
Question:
Answer: [Yes]
Justification:
See answer above.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/ public/guides/ http://odeeuummiiiiiooooaaeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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: httppscccppbbpcccc/peecepppccccc /Codeeubeeeeeeeeeeeeeee /tti:///gggiieeeeeeeettttiiiii
onnolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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 to the paper) recommended, but including URLs to data and code permitted.
(vi)
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: [Yes]
The released code contains all the details needed to reproduce the experiments, including the hyperparameters. Sometimes the hyperparameters are also specified in the text.
Justification:
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, appendix, as supplemental material.
(vii)
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: When applicable, we report the standard deviation of the results as symmetric error bars.
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.
31

---

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 or the standard error of the mean.
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 not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
(viii)
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: [Yes]
Justification: In the Appendix G, we briefly describe our hardware and give upper bounds on running times.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 make into the paper).
(ix) Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: / htt./neurr.ppeeee//eee/ee cc cccppulic/.cchccssuueeeeeeee
Answer: [Yes]
Justification: We verified our Reserach Process is in accordance with the NeurIPS Code of Ethics. Concering Societal Impact, result do not work with any real dataset,
release any trained model that could be used for malicious purposes.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
(x) Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines: Our result do not work with any real dataset, nor we release any trained model that could be used for malicious purposes.
32

---

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 negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.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 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as 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 or 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
(xi) Safeguards
Question: 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)?
Answer: [NA]
Justification: our result do not work with any real dataset, nor we release any trained model that could be used for malicious purposes.
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 to 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.
(xii) 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: [Yes]
Justification: Authors developed all the code and data used in the paper, based on open source library like PyTorch, NumPy, and SciPy.
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 dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
33

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
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 not available online, the authors encouraged to reach out to the asset's 's creators.
(xiti) New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The code released is not meant to be used outside this paper. The code should be simple enough to be understood without any documentation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model 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 is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
(xiv)
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 details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor 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 as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
(xv)
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:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
34

---

Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.
(xvi)
Declaration of LLM usage
Does the paper describe the usage of LLMs if 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, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
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 policy (https: / //neruurpp.... wcc//onfeeencce/222//11111 for what should or should not be described.
35


Reviews:
[{"review_id": "0p4REeCQv9", "reviewer": "Reviewer_3AjM", "summary": "The paper investigates the training dynamics of SGD for a class of sequence single-index (SSI) models, which generalizes the classical single-index model to encompass a simplified one-layer attention model. The authors introduce a metric called the Sequence Information Exponent (SIE) to characterize the sample complexity of SGD and show that positional encoding can help SGD learn faster for certain problems. Then the authors show that a tied-weight model,  representing the attention mechanism, can learn faster than its untied counterpart with a gain proportional to $L$. Finally, the paper explores the interplay between learning semantic versus positional information, revealing a rich phase diagram that describes the different convergence behaviors of SGD.", "questions": "- The proof of Lemma 1 appears to be missing in Appendix C.\n- Lemma 1 indicates that positional encoding does not worsen the sample complexity of SGD. Could the authors provide a more general characterization of the conditions under which positional encoding strictly improves sample complexity?", "limitations": "While the paper discusses the limitations of the assumptions made for its theoretical analysis, it would benefit from a more explicit discussion of the limitations of the architecture being studied.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper is well-written and clear\n- The paper provides a strong theoretical analysis complemented by numerical experiments.\n\nWeaknesses\n- The paper considers a tied-weight and rank-$1$ attention model, limiting its applicability to real-world transformers.", "was_revised": true, "final_justification": "I'll keep my current positive score.", "rebuttal": "### Weaknesses\n> The paper considers a tied-weight and rank- attention model, limiting its applicability to real-world transformers.\n\nWe agree. This is analogous to the classical single-index model, which also does not capture the full complexity of multi-layer perceptrons  but has nonetheless proven foundational in understanding separations between lazy and feature learning regimes for fully-connected neural networks. Similarly, our model enables rigorous analysis while retaining key mechanisms—such as token interactions and positional encoding—and we hope it will serve as a first step towards theoretically understanding more complex attention architectures.\n\n### Questions\n> The proof of Lemma 1 appears to be missing in Appendix C.\n\nThank you for pointing this inattention out. The informal idea behind this Lemma is that adding the positional encoding can only increase the number of non-zero terms in the Hermite expansion, giving the chance to a lower term to correlate with the target. Thus, lowering the effective information exponent. The formal statement and proof will be added in the Appendix C of final version.\n\n> Lemma 1 indicates that positional encoding does not worsen the sample complexity of SGD. Could the authors provide a more general characterization of the conditions under which positional encoding strictly improves sample complexity?\n\nWe thank the reviewer for the insightful question. A characterization of $\\text{SIE}_\\text{positional}$ would indeed be a natural direction for future exploration. Roughly speaking, a model having $\\text{SIE} \\geq k$ implies that the derivatives up to order $k$ of the loss (as a function of the overlaps) are zero _in the direction of $m$_. If any of the derivatives below order $k$ in the direction of the positional overlap $e$ are nonzero, it would imply that adding a trainable positional encoding improves the required sample complexity.\n\n### Limitations\n> While the paper discusses the limitations of the assumptions made for its theoretical analysis, it would benefit from a more explicit discussion of the limitations of the architecture being studied.\n\nThanks for the precious comment. While we have described all the assumptions made for leading to our result through the text, we will make sure to add a paragraph explicitly recapping them."}, {"review_id": "gp0fp4hCs9", "reviewer": "Reviewer_YJDv", "summary": "This paper analyzes the behavior of (spherical) SGD for a class of sequence models where the transformation of the input data is determined by a single vector and a link function. The trainable model is represented as a simplified attention mechanism, where the key and query matrices are tied, the attention head dimension is 1, and with an identity value matrix. The paper introduces two *sufficient statistics* (**e**, m) from which the population risk can be determined. It also generalizes the \"information exponent\" to sequential data, helping establish the sample complexity of SGD for the studied models. The paper further analyzes the impact of positional encodings, which can only reduce (or keep constant) the sequence information exponent, as well as the impact of the sequence length.", "questions": "1. You mention that \"the single-layer tied attention model in eq. (1) is a particular instance of a class of sequence multi-index (SMI) models\", which justifies the choice of training data (drawn from a sequence single-index model (SSI)). Could the data also be generated from a multi-index model? If so, what would that imply?\n\n2. Can you provide an intuitive interpretation about the definition of the Sequence Information Exponent?\n\n3. Can you clarify the statement \"while the model might appear as too simplified because of the lack of correlation between the tokens, we will show that it is sufficient to capture the main features of sequence models.\"?\n\n*Minor comments*\n\nL45: Missing closing parenthesis\n\nThe paper mostly uses \"sequence single-index model\", but the hyphen is placed differently in the title (\"sequence-single index model\").", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- The paper presents a detailed analysis of the behavior of (spherical) SGD for a class of sequence models related to self-attention, evaluating the SGD sample complexity and the impact of positional encodings and sequence length.\n\n- The paper is rigorous, clearly presenting the hypotheses under which the results hold, proving key claims (although I didn't examine the proofs in the appendix in detail), presenting numerical simulations and sharing code for easily reproducible results.\n\n**Weaknesses**\n\n- The paper assumes independence of the inputs (and outputs) across a sequence, which is not realistic for many sequence modeling tasks. The authors mention that \"while the model might appear as too simplified because of the lack of correlation between the tokens, we will show that it is sufficient to capture the main features of sequence models\", but it is not clear to me how having correlated inputs/outputs would impact the claims and results.\n\n- The paper ends abruptly, with no clear conclusion. I would like the authors to discuss the potential impact of their findings on future research directions.", "was_revised": true, "final_justification": "This submission provides a rigorous analysis of SGD on a simplified class of sequence models. While these models don't capture all the intricacies of practical Transformers, there is still non-trivial and interesting behavior to inspect. The authors addressed my limited concerns, in particular by adding nuance to their claim regarding the impact of independent inputs (or outputs).", "rebuttal": "### Weaknesses\n> The paper assumes independence of the inputs (and outputs) across a sequence, which is not realistic for many sequence modeling tasks. The authors mention that \"while the model might appear as too simplified because of the lack of correlation between the tokens, we will show that it is sufficient to capture the main features of sequence models\", but it is not clear to me how having correlated inputs/outputs would impact the claims and results.\n\nWe agree that the assumption of independent inputs and outputs is a simplification, and we will clarify this more explicitly as a limitation in the revision. However, we would like to stress that the SSI model still captures length-wise correlations through the link function $g$, i.e. the dependence of the task outputs in the sequence inputs. Even in this simplified setting, we observe rich and nontrivial behaviors—such as alignment phase transitions, positional vs. semantic learning dynamics, and SIE-dependent sample complexity—that highlight core challenges in sequence learning. Studying correlated inputs is an important next step, and we believe our framework provides a solid foundation for doing so (see as example Cui et al. _A phase transition between positional and semantic learning in a solvable model of dot-product attention_). \n\n> The paper ends abruptly, with no clear conclusion. I would like the authors to discuss the potential impact of their findings on future research directions.\n\nThank you for the comment. We will write a proper conclusion for the final version of the paper. \n\n### Questions\n> You mention that \"the single-layer tied attention model in eq. (1) is a particular instance of a class of sequence multi-index (SMI) models\", which justifies the choice of training data (drawn from a sequence single-index model (SSI)). Could the data also be generated from a multi-index model? If so, what would that imply?\n\nYes, in principle samples can be generated by a SMI, but as long as the attention model is rank 1, only a single direction can be recovered by the model. Our model would learn the most relevant direction (in term of lowest Hermite order), and a similar result to Theorem 1 would apply to this special direction.\nAllowing the the rank of $Q, K$ to be $>1$, all the complex effects characteristic of multi-index model would emerge. In particular, we expect to observe hierarchical learning phenomena such as _staircases_, and it might be possible to extend _leap exponents_ (Abbe et al. _SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics_) to sequence model; this would be a natural future direction after this work; we will discuss this in a Future Direction section in the final revision of our paper.\n\n> Can you provide an intuitive interpretation about the definition of the Sequence Information Exponent?\n\nEvery token is a gaussian vector of dimension $d$. When we project a token along a fixed direction, the resulting coefficient $z_\\star$ is also gaussian variable. When $d\\to+\\infty$, close to initialization, all the $L$ _projected tokens_ are independent and distributed as $L$ multivariate gaussian. At this point, it is natural to decompose the target function $f^\\text{SSI}$ over an orthonormal base with respect to the Gaussian distribution: that's how the Hermite polynomials appear in our derivation. Given that the target takes as inputs the $L$ projections of the tokens, the orthonormal basis elements are the product of $L$ scalar Hermite polynomials. The information exponent is nothing more than the lowest degree of the multivariate polynomials of this expansion. You can find more details in Appendix B.\n\n> Can you clarify the statement \"while the model might appear as too simplified because of the lack of correlation between the tokens, we will show that it is sufficient to capture the main features of sequence models.\"?\n\nAnswered in \"Weaknesses\"."}, {"review_id": "OgzBi3neuP", "reviewer": "Reviewer_iycP", "summary": "This paper investigates the dynamics of Stochastic Gradient Descent (SGD) in sequence models referred to as Sequence Single-Index (SSI) models. The authors introduce the Sequence Information Exponent (SIE) as a generalization of the information exponent from single-index models, and demonstrate its close relationship with the sample complexity of SGD. The paper also explores the theoretical impact of positional encoding on the speed of SGD training. It analyzes how models equipped with attention mechanisms significantly outperform fully connected networks, which are not designed to handle sequential data, in terms of learning efficiency for sequential inputs. Furthermore, the authors show that when data contains positional and semantic information, the dynamics of SGD may not always disentangle these components, leading to a rich phase diagram that characterizes the structure of the population loss and the performance of SGD.", "questions": "Equation 1: Readers unfamiliar with Transformers may not understand what the variables $X$ and $P$ represent. In particular, the introduction of $P$ feels abrupt.\n\nLine 202: What form of positional encoding is assumed here? While it is clear that it should be non-zero, it is unclear whether the authors are assuming the $\\sin$ and $\\cos$ form used in the original Transformer, or if any arbitrary form is acceptable.\n\nSection 4: Is the discussion limited to the case where only $P_1$ and $P_2$ exist, that is, the case of $L=2$?", "limitations": "There is some explanation about how this formulation is far from the practical use of Transformer. However, there is no dedicated section or paragraph explaining the limitations.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strength\n\n+ The paper elucidates the dynamics of SGD in SMI models.\n+ It clarifies how the sequence length and positional encoding affect the convergence speed and trajectory of SGD.\n\nWeakness\n\n+ As a theoretical study, the approach inevitably diverges from the practical Transformer architecture. It remains unclear how applicable the insights gained in this paper are to real-world Transformer-based research.", "was_revised": true, "final_justification": "I see the value of the theoretical work even if it is deviated from the practical use of Transformers. The author response answers questions raised in the initial review.", "rebuttal": "We thank the reviewer for the insightful comments. Below, we address the primary concerns that have been raised.\n\n### Weakness\n> As a theoretical study, the approach inevitably diverges from the practical Transformer architecture. It remains unclear how applicable the insights gained in this paper are to real-world Transformer-based research.\n\nOur theoretical model is not the full transformer architecture, but a simplification of the attention architecture. This is almost always the case in theoretical works, where the goal is not to replicate a real setting (which is often mathematically not tractable) but rather to identify and isolate the core mechanisms —such as token interactions, positional encoding, and sequence -induced learning dynamics — in a mathematically tractable setting. Despite the simplifications, our analysis reveals rich behaviors that are qualitatively aligned with challenges observed in real-world sequence learning. We hope these insights will serve as a foundation for future theoretical work that bridges further toward practical architectures.\n\n\n\n### Questions\n> Equation 1: Readers unfamiliar with Transformers may not understand what the variables and represent. In particular, the introduction of feels abrupt.\n\nThank you for the feedback. We will use part of the extra space of the final version for making this step clearer; we also have Appendix A for a detailed explanation of the attention mechanism.\n\n> What form of positional encoding is assumed here? While it is clear that it should be non-zero, it is unclear whether the authors are assuming the $\\sin$ and $\\cos$ form used in the original Transformer, or if any arbitrary form is acceptable.\n\nFrom a theoretical point of view, any set of linearly independent vector could be used as positional encoding. \nWhen simulating or running it practically, farther apart are the positional embedding vectors, easier for the model distinguishing the positions, thus more effective it is. For most of our simulations, we use $P_1=-P_2$, in order to have the bigger separation as possible.\nIn practice, any usual strategy to have a well separated positional encoding (as the one you suggest), would work.\n\n> Section 4: Is the discussion limited to the case where only $P_1$ and $P_2$ exist, that is, the case of $L=2$?\n\nNo, the phase transition could be certainly observed for settings $L>2$. We stick with $L=2$ just for having a nicer visualization of what is happening, since only in this case we could reduce the problem to just 2 sufficient statistics and consequently have nice plots like Figure 7. Nevertheless the assumption $L=2$, we are able to make our point: SGD is not always converging to global minima for Sequence Single Index models.\n\n### Limitation\n> There is some explanation about how this formulation is far from the practical use of Transformer. However, there is no dedicated section or paragraph explaining the limitations.\n\nThanks for the precious comment. While we have described all the assumptions made for leading to our result through the text, we will make sure to add a recap Paragraph explicitly recapping them."}, {"review_id": "Et7dII77De", "reviewer": "Reviewer_GTHc", "summary": "The authors study the ability of a one-layer attention mechanism to learn a sequence-single index (SSI) model, which generalizes the classic single-index model to sequence inputs. Specifically, they approximate one-pass SGD by gradient flow and analyze the sample complexity required for weak recovery. They also investigate how positional encoding and sequence length affect sample complexity.", "questions": "(Q1) In line 116, you state: “Note that while the model might appear as too simplified because of the lack of correlation between the tokens, we will show that it is sufficient to capture the main features of sequence models.” Which specific results in the paper demonstrate this claim?\n\n(Q2) How exactly does the gradient flow defined in Equation (11) relate to the sample complexity?\n\n(Q3) In Lemma 2, it is claimed that adding positional encoding lowers the information exponent. Is this a formal statement? Since the information exponent is a property of the test function $g$, I would expect it not to change even if the model is modified. (If I am misunderstanding this, please clarify.)\n\n(Q4) In line 237, you state: “In terms of performance, taking a general activation $\\sigma$ will at worst be the same of the attention mechanism originally considered, if not better.” What is the justification for this claim?\n\n(Q5) In Section 3, why did you consider the linear attention model instead of eq.(1)?", "limitations": "No, the authors do not discuss limitations of their study within the paper. At the very least, I believe the issues I raised in (W3) and (W4) should be explicitly discussed.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n(S1) Extending the single-index model to sequence inputs is a unique contribution.\n\n(S2) The paper does not merely analyze sample complexity, but also provides both theoretical and empirical discussions on how sequence length and positional encoding affect learning. The use of concrete examples to supplement the explanations is commendable.\n\n**Weaknesses:**\n\n(W1) Although the paper frames this work as an extension of the single-index model to sequences, the technical differences in the proofs and analysis seem relatively minor compared to standard single-index models.\n\n(W2) It is unclear what fundamental insights the authors aim to uncover through the SSI setting. For example, when analyzing two-layer neural networks for learning single-index models, the goal is to study the feature learning capability of neural networks. In contrast, the SSI model is simply a generalization of the single-index model by introducing functions along the sequence dimension, and the motivation for studying such a model is not clearly articulated.\n\n(W3) The model defined in Equation (1) is an even function, so if the true target function is not even, then even after achieving weak recovery, it is not guaranteed that the model can fit the true function. To achieve this, one would typically need to add a feed-forward layer after the attention layer, but doing so would change the gradients flowing through the attention layer. Thus, the model studied in this work is subject to strong simplifications for tractability.\n\n(W4) The Sequence Information Exponent is defined via products of Hermite polynomials, but the necessity of this choice is not sufficiently explained. In standard single-index models, the Hermite polynomials serve as an orthogonal basis for Gaussian inputs, which justifies their use. However, it is not discussed whether similar justification holds in the SSI setting. Additionally, in classic single-index models, the (C)SQ lower bound characterizes learning limits in terms of the Information Exponent, but it remains unclear whether a similar limit applies to the SSI setting. Therefore, the practical significance of the upper bounds derived in this paper is not clear.", "was_revised": true, "final_justification": "This paper investigates the SGD dynamics of Transformers in the setting where the true function is given by the sequence single-index (SSI) model. The SSI model extends the single-index model to sequence inputs and includes cases where the teacher model employs a rank-one tied-weight single-layer attention matrix.\n\nThe authors are to be commended for building a rigorous theory of SGD dynamics on top of prior theoretical work on the SSI model. However, I assign a rating leaning toward rejection due to (1) limited insight into practical applicability, and (2) the reliance of the positional-encoding theory on comparisons with models of restricted expressive capacity. My initial rating was “Reject,” but after the authors clarified the connection to previous work and addressed theoretical ambiguities during the discussion period, I raised it to “Borderline Reject.”", "rebuttal": "We thank the reviewer for the detailed review.\n\n### Weaknesses\n> Although the paper frames this work as an extension of the single-index model to sequences, the technical differences in the proofs and analysis seem relatively minor compared to standard single-index models.\n\nThe primary contribution of our work is indeed conceptual: it lies in formulating and analyzing a sequence-structured analogue of the classical single-index model that bridges the gap between established theoretical frameworks and attention-based architectures used in practice.\n\nWhile our mathematical results build on those developed for standard single-index models, the geometry of the population loss becomes significantly more intricate, requiring new sufficient statistics that jointly capture semantic and positional alignment. This richer structure underpins phenomena such as alignment failure, sample complexity phase transitions, and the impact of positional encoding --- none of which arise in the classical setting.\n\nWe view this conceptual reframing as important precisely because it enables technically grounded insights into the learning dynamics of simplified attention models, while staying mathematically tractable. Even if the technical machinery appears familiar, its application yields qualitatively new behaviors specific to sequence models.\n\nMoreover, we believe it is a particularly exciting aspect of this work that the tools developed for studying single-index models can be adapted and extended to provide rigorous insight into the training dynamics of attention-based architectures. It is a first step towards a mathematical understanding of the role of sequential structure in learning.\n\n> It is unclear what fundamental insights the authors aim to uncover through the SSI setting. .... the SSI model is simply a generalization of the single-index model by introducing functions along the sequence dimension, and the motivation for studying such a model is not clearly articulated.\n\nWe respectfully disagree with this comment. While the motivation may not have been sufficiently emphasized in the manuscript—a point we will address in the revision—it is scientifically strong: the SSI model provides a minimal yet expressive framework to rigorously analyze how sequence structure and attention mechanisms affect learning under SGD. \n\nJust as classical single-index models isolate the core of feature learning in two-layer networks, the SSI model isolates key aspects of attention-based models—such as positional encoding—in a tractable setting. It enables rigorous analysis of phenomena like sample complexity scaling with sequence length, the effect of positional encoding, and alignment phase transitions, none of which are accessible in classical single-index models. A very concrete and direct consequence of our results is to provide a class of tasks for which one can rigorously establish the *computational* benefits of sequence length for attention-based architectures over their fully connected counterpart. This is among the first results in this direction in the existing literature. \n\nFar from being an arbitrary generalization, the SSI model is a deliberate abstraction aimed at uncovering what makes learning from sequences distinct. It opens a path toward a theoretical understanding of attention-based learning grounded in established tools.\n\n> The model defined in Equation (1) is an even function, so if the true target function is not even [...] the model studied in this work is subject to strong simplifications for tractability.\n\nWe have dedicated appendix D to non-even targets, that can fully recover a larger set of functions. \n    \nMoreover, in the single-index literature it is frequent to consider  the weak recovery phase of the learning, since is the one dominating the sample complexity; as the reviewer mentioned, surpassing the low expressivity of our model is not hard in practice, yet makes the theoretical analysis more complex.\n\nWe will emphasize this aspect more and state our focus on even functions as a limitation of our work and the full treatments of generic functions as a direction of future work. \n\n> The Sequence Information Exponent is defined via products of Hermite polynomials, but the necessity of this choice is not sufficiently explained. In standard single-index models, the Hermite polynomials serve as an orthogonal basis for Gaussian inputs, which justifies their use.\n\nAn equivalent justification is provided in Appendix B, and will be further clarified in the main text. As the Hermite polynomials are an orthogonal basis under the one dimensional standard Gaussian measure, all possible products of Hermite polynomials $\\mathrm{He}_ {k_1}(x_1)\\dots\\mathrm{He}_{k_L}(x_L)$ are an orthogonal basis under the $L$-dimensional measure.\n\n> In classic single-index models, the (C)SQ lower bound characterizes learning limits in terms of the Information Exponent, but it remains unclear whether a similar limit applies to the SSI setting. Therefore, the practical significance of the upper bounds derived in this paper is not clear.\n\nWe appreciate the reviewer’s point and agree that establishing (C)SQ lower bounds for the SSI setting is an important open direction. Our goal in this paper is to lay the groundwork for such results by introducing the SSI framework and deriving sharp upper bounds based on the Sequence Information Exponent (SIE), in close analogy to what was done for classical single-index models. While we do not yet provide a corresponding lower bound, we believe our analysis highlights the structural features—such as the role of the Hermite expansion and the geometry of sufficient statistics—that are likely to be relevant for future hardness results. In this sense, our contribution is a necessary step toward a complete information-theoretic understanding of learning in sequence-structured problems.\nWe will dicuss this in limitations and future directions. \n\n### Questions\n> “Note that while the model might appear as too simplified because of the lack of correlation between the tokens, we will show that it is sufficient to capture the main features of sequence models.” Which specific results in the paper demonstrate this claim?\n\n We will reword to: \"we will show that it is sufficient to capture some of the key properties of sequence models.\"\n\nIn particular, we were able to demonstrate a transition between the positional and semantic regimes, modeling both of these properties that distinguish sequential models from unstructured ones.\nThe model also allowed us to study the sequence length dependence of the sample complexity.\n\n> How exactly does the gradient flow defined in Equation (11) relate to the sample complexity?\n\nThe precise relationship between the gradient flow of (11) and the sample complexity is stated in Theorem 4 (Appendix C). In short, the dynamics of $m^{\\tau}$ closely follow those of $m(\\gamma \\tau)$, where $m(t)$ is the overlap of the solution $w(t)$ to (11), as long as $\\gamma$ is small enough. Choosing the largest possible $\\gamma$ such that the ODE approximation stays valid allows us to relate the hitting time of the ODE (11) to the one of the process (2). We will add a reference to Theorem 4 in the main text.\n\n> In Lemma 2, it is claimed that adding positional encoding lowers the information exponent. Is this a formal statement? Since the information exponent is a property of the test function , I would expect it not to change even if the model is modified.\n\nThank you for pointing this out: the information exponent is indeed a property of the target function. The intention of the lemma was to express that the sample complexity of a model with positional encoding is asymptotically less than or equal to that of the same model learning the same target function without positional encoding. The model with positional encoding effectively behaves as if the target has a $\\text{SIE}_\\text{positional} \\le \\text{SIE}$, in the sense of Theorem 1. We agree that this section needs to be reformulated for clarity: we will change Lemma 1 accordingly and include the formal statement in Appendix C.\n\n> “In terms of performance, taking a general activation $\\sigma$ will at worst be the same of the attention mechanism originally considered, if not better.” What is the justification for this claim?\n\nWe showed that our model with linear attention is equivalent to the one in Equation (14) with $\\sigma = x^2$. By allowing a generic activation function $\\sigma$, our analysis encompasses a broad class of models, including the specific case $\\sigma = x^2$. This generalization makes it possible to explore whether other activation functions may outperform $\\sigma = x^2$ in terms of weak recovery speed, which is the metric we use to evaluate performance.\n\n> In Section 3, why did you consider the linear attention model instead of eq.(1)?\n\nLinear attention is primarily a way to draw a connection between attention mechanisms and tied/untied neural networks. Building on the previous point, the model considered in Section 3 is significantly more general than linear attention: by allowing any activation function $\\sigma$, we can emulate sequential models that go beyond the standard $\\mathrm{softmax}$ aggregation strategy. We will clarify this point in the final version."}]

Author rebuttal:

Meta-review: The reviewers agreed that this paper addresses an important topic, is clearly written, and has strong results. Some reviewers had concerns about the technical assumptions made in the paper, and how it may affect the proposed model's applicability. I believe that the authors were able to provide detailed answers to almost all of the concerns. After going through the paper, I felt that I will have to agree with the majority of the reviews as the positives (such as originality, clarity) clearly outweigh the perceived negatives in the submission. Hence, I recommend accepting this paper.
Decision: Accept (poster)