domain: info math

text:
Borjan Geshkovski

Cyril Letrouit

Yury Polyanskiy

Philippe Rigollet
email: rigollet@mit.edu

THE EMERGENCE OF CLUSTERS IN SELF-ATTENTION DYNAMICS

Viewing Transformers as interacting particle systems, we describe the geometry of learned representations when the weights are not time dependent. We show that particles, representing tokens, tend to cluster toward particular limiting objects as time tends to infinity. Cluster locations are determined by the initial tokens, confirming context-awareness of representations learned by Transformers. Using techniques from dynamical systems and partial differential equations, we show that the type of limiting object that emerges depends on the spectrum of the value matrix. Additionally, in the one-dimensional case we prove that the self-attention matrix converges to a low-rank Boolean matrix. The combination of these results mathematically confirms the empirical observation made by Vaswani et al. [VSP `17] that leaders appear in a sequence of tokens when processed by Transformers.

).

Part 1. Introduction and main results

Introduction

The introduction of Transformers in 2017 [VSP `17] marked a turning point in the AI revolution, powering breakthroughs in natural language modeling and computer vision. With remarkable empirical success, Transformers enable large language models to compute very powerful representations using the self-attention arXiv:2305.05465v6 [cs.LG] 12 Feb 2024 mechanism. Yet, little is known about the geometric structure of these representations. As the size of these models grows at an astonishing rate, the need to understand their inner workings is becoming a pressing scientific challenge. In this work, we make a first step in this direction by describing the geometry of learned representations.

To provide a transparent presentation of our findings, we take a leaf out of the literature on continuous-time dynamics such as neural ordinary differential equations (ODEs) [START_REF] Ricky Tq Chen | Neural ordinary differential equations[END_REF][START_REF] Weinan | A proposal on machine learning via dynamical systems[END_REF][START_REF] Haber | Stable architectures for deep neural networks[END_REF]. By viewing layers as a time variable, this formalism has emerged as a flexible mathematical framework to implement and study ResNets [START_REF] He | Deep residual learning for image recognition[END_REF] as particular discrete-time versions of a parametrized dynamics of the form 9 xptq " f θ pxptqq, t P r0, T s.

Here θ is the trained parameter of a neural network and f θ is characterized by the precise architecture of the ResNet 1 . In turn, an input (e.g., an image) xp0q P R d is mapped to its representation xpT q.

Unlike neural ODEs and ResNets, the representation map of Transformers is not solely a function of an individual input xp0q P R d but rather of a set/sequence px 1 p0q, . . . , x n p0qq of n ě 1 d-dimensional tokens. These tokens then evolve in time by interacting with each other per the self-attention mechanism. Namely, following [START_REF] Michael E Sander | Sinkformers: Transformers with doubly stochastic attention[END_REF], we view tokens as particles, and the transformer dynamics as an interacting particle system of the form 9 x i ptq " n ÿ j"1 P ij ptqV x j ptq, t P r0, `8q, (

for any i P rns, where P ij ptq are the entries of a n ˆn stochastic matrix P ptq, given by P ij ptq :" e xQxiptq,Kxj ptqy ř n ℓ"1 e xQxiptq,Kx ℓ ptqy , pi, jq P rns 2 .

(1.2)

Here the matrices Q (Query), K (Key), and V (Value) are learned from data. Note that Q, K need not be square. The n ˆn matrix P ptq is called self-attention matrix. The wording attention stems precisely from the fact that P ij ptq captures the attention given by token i to token j relatively to all tokens ℓ P rns. The matrices Q and K in (1.2) warp the geometry of the input tokens, so that a trained attention matrix contains weights which indicate semantic relations between words. Such conclusions have been drawn in the context of language processing tasks in [VSP `17, Figures 345].

Our goal is to showcase the fact that self-attention, which itself is the core novelty of Transformers, entails a clustering effect. To that end, we focus on the pure self-attention dynamics described in (1.1). In particular, we do not model variations such as multiple heads, feed-forward layers, and layer normalization that are typically adjoined to self-attention dynamics of (1.1). However, on this last point, we note that our theoretical findings indicate that without any normalization, the dynamics (1.1) can diverge in some (or even all) directions over time. We leave these additional questions for future research; see Section 12. 1.1. Organization of the paper and summary of contributions. The goal of this paper is to characterize clustered representations of a trained Transformer by studying the asymptotic behavior of a sequence of tokens px 1 ptq, . . . , x n ptqq as they evolve through the layers of a transformer architecture using the dynamics (1.1). In this setup, a Transformer is completely described by the weight matrices pQ, K, V q obtained during training. Note that we assume that these three matrices are timeindependent. While this assumption is motivated by mathematical convenience, it is worth noting that such weight-sharing scenarios are in fact used in practice-see, e.g., ALBERT [LCG `20]-as they drastically reduce the number of parameters of a network.

With parameters pQ, K, V q fixed, tokens are subject to collective dynamics that we call transformer dynamics. While these dynamics are reminiscent of existing models for opinion dynamics and flocking, they present they own mathematical challenges requiring ad-hoc tools to study their asymptotic behavior.

The main conclusion of our analysis is that the set of tokens tx 1 ptq, . . . , x n ptqu, appropriately rescaled, tends to a clustered configuration as t Ñ 8. Our theoretical findings justify the empirical observation made in [VSP `17] that leaders appear in a sequence of tokens when processed by Transformers. We now list our main contributions.

(i) As a warm-up to the geometric characterization of the limits of sequences of tokens, we show in Section 2 that when d " 1 and V ą 0, the self-attention matrix P ptq converges to a low-rank matrix with entries 0 and 1 as t Ñ `8 thus revealing the emergence of a small number of leaders that drive the transformer dynamics. The restriction d " 1 follows from technical considerations, and some pathological phenomena may occur in higher dimensions (see Remark 7.9). The proof may be found in Section 7. But numerical experiments (as well as past empirical work) indicate that the result may extend to higher dimensions for almost all initial sequences of tokens.

(ii) In Section 3 we first focus on the case V " I d as a natural canonical choice that enables us to establish some of the main tools of the paper. We introduce a time re-scaling reminiscent of the layer normalization heuristics to alleviate the possible divergence of tokens. We show that along this scale the tokens converge to the boundary of a convex polytope. For almost all initial sequences they even converge to the vertices of the polytope, the number of which is significantly smaller than n. This elucidates the clustering phenomenon. (See Fig. 1.) When V " ´Id , all tokens following the dynamics (1.1) collapse to 0. The proofs are given in Section 8.

(iii) We build on these results and in Section 4 consider the case wherein V is only assumed to have a simple and positive leading eigenvalue. This setting is much closer to reality and corresponds to actual learned matrices V (see Figure 10). We show that along the particular timescale, tokens cluster toward one of at most three hyperplanes which are determined by the corresponding eigenvector. The proof is given in Section 9.

(iv) In Section 5 we complete the results of Sections 3 and 4 by addressing the case where the leading eigenvalue has multiplicity. This results in clustering toward the vertices of a convex polytope in some directions, and a linear subspace in the others. The proof is provided in Section 10.

(v) We also prove the global existence and uniqueness of solutions of all dynamics considered in this work (including the mean field limit). We refer the reader to Section 6 for more details.

We also observed numerically that our conclusions extend to more compound architectures (see Conjecture 4.3, Section 12 and Section 11).

Value

Key and Query Limit geometry Reference

V " I d Q J K ą 0 vertices of convex polytope Theorem 3.1 λ1pV q ą 0, simple xQφ1, Kφ1y ą 0 union of 3 parallel hyperplanes Theorem 4.2 V paranormal Q J K ą 0 polytope ˆsubspaces Theorem 5.2

V " ´Id Q J K " I d single cluster at origin ˚Theorem 8.5

Table 1. Summary of the clustering results of this work. ˚All results except for the case V " ´Id hold for the time-scaled dynamics (3.1).

Remark 1.1 (Discrete time). While we focus on the idealized setting of selfattention dynamics in continuous-time, this is solely done for convenience and all of our methods are straightforwardly applicable to the discrete-time setting. (See also Remark 3.4.) The discrete-time analog of (1.1) with time-step ∆t ą 0 (equal to 1 in practice) is simply the forward Euler iteration

x i ppk `1q∆tq " x i pk∆tq `∆t n ÿ j"1 ˆexQxipk∆tq,Kxjpk∆tqy ř n ℓ"1 e xQxipk∆tq,Kx ℓ pk∆tqy ˙V x j pk∆tq, (1.3) for k P N.

1.2. Notation. We denote by x¨, ¨y and } ¨} the Euclidean dot product and norm respectively, and we use the shorthand rns :" t1, . . . , nu. For any matrix M P R dˆd , we order its eigenvalues (repeated according to multiplicity) by decreasing order of modulus: |λ 1 pM q| ě . . . ě |λ d pM q|. We denote by }M } op the ℓ 2 -operator norm of the matrix M , equal to the largest singular value of M . Given a set S Ă R d , we define the distance of a point x P R d to S as distpx, Sq :" inf sPS }x ´s}, and by convpSq the convex hull of S.

1.3. Related work. Our study and results build on several different lines of work, and we draw some parallels in what follows.

1.3.1. Analysis of attention-based models. Given the widespread use of Transformers in natural language processing, there has been a surge of interest in understanding the function and significance of attention layers within these models. In [YBR `20], the authors show that when treated as discrete-time systems with additional dense layers and multiple heads appended to the core attention mechanism, Transformers exhibit the universal approximation property. In [LLH `20], the authors present, to the best of our knowledge, the first interacting particle systems perspective on Transformers. They then leverage the similarities between Transformers (with an additional feed-forward layer compared to (1.1)) and convectiondiffusion equations to slightly improve the performance of Transformers by employing a Strang-Marchuk splitting scheme for time discretization. In [START_REF] Michael E Sander | Sinkformers: Transformers with doubly stochastic attention[END_REF], the authors interpret system (1.1) as the characteristics of a continuity equation. Drawing on the similarities between (1.1) and Sinkhorn iterations, they propose a novel architecture dubbed Sinkformer, which possesses the desirable property of being a Wasserstein gradient flow. 1.3.2. Quadratic complexity of Transformers. The major computational challenge of Transformers is their high computational complexity, particularly when processing long sequences. Transformers require quadratic time and space complexity to process sequences, because each self-attention layer contains n 2 products of the form xQx i , Kx j y (for i, j P rns). The empirical observation that the self-attention matrix P is close to a low rank matrix-see [LWLQ22, Section 4.4] for references-is cited as the inspiration behind Linformers [WLK `20] and the fine-tuning algorithm LoRA [HysW `22]. For both approaches, the low-rank structure is imposed rather than extracted from P itself. Other methods called sparse attention and block attention have been proposed to reduce the quadratic complexity-see [WLK `20, Section 2.2] for references. In the spirit of these works, a foreshadowing of the clustering mechanism was invoked in [START_REF] Vyas | Fast transformers with clustered attention[END_REF], where queries are clustered into groups, again in view of reducing the quadratic complexity of self-attention. We point out that [START_REF] Dong | Attention is not all you need: Pure attention loses rank doubly exponentially with depth[END_REF] previously demonstrated that without skip connections, the dynamics trivializes and all tokens quickly lump together into a single tight cluster. Our work, in contrast, shows that in the presence of skip connections a rich cluster structure emerges.

Compared to the usual BERT, ALBERT [LCG `20] uses parameter-sharing across layers, meaning that the weight matrices Q, K, V in (1.1)-(1.2) do not depend on time, as in the present paper. This does not reduce the theoretical Opn 2 q complexity of the original Transformer, but, quoting [LCG `20], it "significantly reduce[s] the number of parameters for BERT without seriously hurting performance, thus improving parameter-efficiency. An ALBERT configuration similar to BERT-large has 18x fewer parameters and can be trained about 1.7x faster. The parameter reduction techniques also act as a form of regularization that stabilizes the training and helps with generalization". 1.3.3. Neural collapse. Our results and conclusions bear a resemblance to some geometric aspects of neural collapse for classification tasks [START_REF] Vardan Papyan | Prevalence of neural collapse during the terminal phase of deep learning training[END_REF]. A key geometric aspect of neural collapse is the observation that, during the training of deep neural networks, the representation of different classes in the later layers of the network tends to form a tight cluster around the vertices of a simplex. The emergence of a simplex structure in the representation space provides insights into how the neural network organizes and separates the different classes.

9 x i ptq " n ÿ j"1 a ij px j ptq ´xi ptqq, a ij " ϕp}x i ´xj } 2 q ř n k"1 ϕp}x i ´xk } 2 q .
which is non-symmetric in general (a ij ‰ a ji ), much like (1.1). When ϕ is compactly supported, it has been shown in [START_REF] Jabin | Clustering and asymptotic behavior in opinion formation[END_REF] that the particles x i ptq assemble in several clusters as t Ñ `8. Other models of opinion dynamics and flocking have been proposed and studied, among which the Vicsek model [VCBJ `95], the Hegselmann-Krause model [START_REF] Hegselmann | Opinion dynamics and bounded confidence: models, analysis and simulation[END_REF] and the Cucker-Smale model [START_REF] Cucker | Emergent behavior in flocks[END_REF]. These models may also exhibit a clustering behavior under various assumptions (see [MT14, CHH `16, HKPZ19] and the references therein). The transformer dynamics are also closely related to the dynamics employed in mean-shift clustering [START_REF] Cheng | Mean shift, mode seeking, and clustering[END_REF], and this work indirectly sheds some light on its theoretical properties. The analysis of transformer dynamics presents unique mathematical challenges that cannot be addressed using the tools developed for these more primitive models. In particular, our work demonstrates how different choices for the parameters lead to remarkably diverse clustering patterns. Much more remains to be discovered and this work is a first attempt a rigorous mathematical analysis of these synthetic dynamics.

Asymptotic low-rankness of the self-attention matrix

As mentioned in Section 1.3, numerical experiments in [WLK `20] show that the self-attention matrix P , defined in (1.2), has an almost low-rank structure. This observation has then been leveraged to reduce the quadratic complexity in the sequence length n which is inherent to Transformers, resulting in a non-negligible decrease in the cost of training.

As a warm-up to deriving complete geometric representations of the dynamics, our first result shows, in the simple 1d case that P ptq indeed converges exponentially fast toward a matrix which is typically both Boolean and low-rank (see Fig. 3). Although there are clear obstructions to a rigorous extension of this result to higher dimensions (Remark 7.9), numerical experiments appear to show that this result holds in greater generality, for almost all initial sequences (Section 11).

To set this up, we introduce the set P of nˆn matrices having the form illustrated in Fig. 2, where the asterisks denote arbitrary non-negative real numbers which add up to 1. The row of asterisks may actually be any row between the first and the last one.

Theorem 2.1 (Self-attention matrix converges to a low-rank Boolean matrix). Let d " 1. Suppose that the scalars pQ, K, V q satisfy V ą 0 and QK ą 0. For any initial sequence of pairwise distinct tokens px 1 p0q, . . . , x n p0qq P R n , there exists some P ˚P P such that the self-attention matrix P ptq defined in (1.2) converges to P ˚as t Ñ `8.

P σ             1 0 . . . 0 . . . . . . . . . . . . 1 0 . . . 0 * * . . . * 0 . . . 0 1 . . . . . . . . . . . . 0 . . . 0 1             1 Figure 2. Elements in P,
where Pσ i P R nˆn are some permutation matrices, and asterisks denote arbitrary nonnegative reals which add to 1.

The proof may be found in Section 7. The rate of convergence toward P ˚is in fact doubly exponential in t for coefficients outside the row of asterisks in Fig. 2. The proof the theorem also reveals that for almost all initial sequences of pairwise distinct tokens, P ˚is actually of rank 1 or 2, i.e., the row of asterisks is equal to either e 1 " p1, 0, . . . , 0q or e n " p0, . . . , 0, 1q.

The interpretation of Theorem 2.1 is that in the 1d case, at most three tokens capture the attention of all tokens except at most one. Typically, these leading tokens are those carrying the largest amount of information. This is also illustrated in Fig. 4. Since the tokens x i here evolve on R, the right-most and left-most ones (which typically tend toward ˘8) capture the attention of all the others.

Clustering toward vertices of convex polytopes

In the rest of the paper, we seek to taxonomize various clustering results for the solutions to (3.1) when t Ñ `8, depending the sign and the multiplicity of the eigenvalues of V . We begin by focusing on what may appear to be the most natural2 case V " I d , as is also done in [START_REF] Michael E Sander | Sinkformers: Transformers with doubly stochastic attention[END_REF]. In fact, we demonstrate (theoretically and numerically) later on, clustering is a generic phenomenon which holds under much less restrictive assumptions.

The transformer dynamics considered in (1.1) does not contain a layer normalization mechanism typically encountered in practice [VSP `17]. In absence of such a device, tokens may diverge to infinity as in Theorem 2.1. In fact, the norm of the tokens x i ptq typically diverges exponentially toward `8 for any d: this is expected, by analogy with the non-trivial solutions to 9 yptq " yptq. To remedy this situation, we take inspiration from the solution yptq " e tV yp0q to 9

yptq " V yptq. Namely, for any i P rns we consider the rescaled tokens z i ptq :" e ´tV x i ptq, which solve

9 z i ptq " n ÿ j"1
˜exQe tV ziptq,Ke tV zj ptqy ř n k"1 e xQe tV ziptq,Ke tV z k ptqy ¸V pz j ptq ´zi ptqq,

t P r0, `8q. (3.1)
The initial condition remains the same: x i p0q " z i p0q for any i P rns. More importantly, the coefficients of the self-attention matrix for the rescaled tokens z i ptq are the same as those for the original tokens x i ptq. Whence, the conclusion of Theorem 2.1 also applies to the dynamics (3.1). We see this rescaling of tokens as a mathematically justified surrogate for the layer normalization. The appearance of the exponential factor within the self-attention kernel facilitates the analysis of (3.1) compared to (1.1), and it is in fact instrumental in the proofs of all results that follow. Each result on the rescaled tokens z i ptq then gives information on the dynamics of the original tokens x i ptq by virtue of the relation x i ptq " e tV z i ptq.

We are now able to state the main result of this section on the case V " I d . The following theorem shows that the tokens z i ptq evolving per dynamics (3.1) converge to the boundary of a convex polytope as t Ñ `8. We present here a simplified but weaker version of our result for convenience, and refer the reader to Theorem 8.1 for a complete statement.

Theorem 3.1 (Convergence to points on the boundary of a convex polytope). Suppose V " I d and Q J K ą 0. Then, for any initial sequence of tokens tz i p0qu iPrns Ă R d , there exists a convex polytope K Ă R d such that for any i P rns, z i ptq converges either to 0 or to some point on BK as t Ñ `8.

The convex polytope K is completely determined by the initial sequence of tokens, and Q J K (refer to Claim 1). Numerical experiments (e.g. Fig. 5) also lead us to claim that for almost all initial sequences of tokens, one should expect convergence of z i ptq (i P rns) toward some vertex of K. (Furthermore, the number of vertices of K is often found to be significantly smaller than n.) It may however in Section 8.2 that the dynamics converge to a single cluster located at the origin. Multiplicative constants preserving the sign, i.e., V " ˘cI d , c ą 0 trivially yield the same conclusions.

happen that for initial sequences taken in some null set (not seen when tokens are drawn at random) some tokens converge to other points of the boundary BK, namely in the interior of facets. On the other hand, for generic choices of initial sequences, we do not see a way to predict K explicitly besides running the full dynamics. Recall that the points x i ptq " e t z i ptq when V " I d follow the original dynamics (1.1). Akin to Theorem 2.1, this result also shows the emergence of a set of leaders (given by the vertices of K) attracting all tokens as t grows. It has been experimentally observed (first in [VSP `17]) that in trained Transformers, tokens focus their attention on local leaders in a way that seems to reproduce the syntactic and semantic structure of sentences.

The proof of Theorem 3.1 is postponed to Section 8, and amounts to a couple of effects entailed by the dynamics. First of all, the convex hull of the particles is shrinking over time (Proposition 8.2). This is due to the fact that the distance of the particle nearest to any half-space (not containing the particles) increases with time. On the other hand, the convex hull ought not collapse since particles which have not concentrated near the boundary of the limiting polytope will continue to increase in magnitude until they themselves reach this boundary (Step 2 in the proof). This occurs due to the time-rescaling.

Remark 3.2. Assuming Q J K ą 0 does not seem to be essential for our conclusions; instead, it guides the direction of the proof. To emphasize the broader validity of our conclusion beyond this specific assumption, we conducted additional experiments (refer to Section 12.1) which suggest that Theorem 3.1 (as well as Theorems 4.2 and 5.2 stated below) holds in more generality.

Remark 3.3 (Rate of convergence). Although Theorem 3.1 (as well as Theorems 4.2 and 5.2 stated below) does not specify a rate of convergence toward BK, we expect (and observe through numerics) that convergence happens very quickly-after few layers, most tokens are already clustered. What "few layers" means here necessarily depends on the typical modulus of the initial tokens, since the dynamics (1.1) is not invariant under multiplication of all initial conditions by a fixed real number.

Remark 3.4 (Discrete time). As alluded to in Remark 1.1, all our results extend to the discrete-time Transformers (1.3). Indeed, just as in the continuous-time case, there is a natural rescaled dynamics, which is the discrete analogue of (3.1): if we set R " I d `V ∆t, and assume that R is invertible (which is the case for sufficiently small ∆t), then z i pk∆tq " R ´kx i pk∆tq :"

z rks i satisfies z rk`1s i " z rks i `∆t n ÿ j"1 ˜exQR k z rks i ,KR k z rks j y ř n ℓ"1 e xQR k z rks i ,KR k z rks ℓ y ¸R´1 V ´zrks j ´zrks i ¯, k P N.
The proofs of Theorems 2.1, 8.5, 3.1, 4.2, and 5.2 carry through with straightforward modifications.

Let us provide some comments on the proof of Theorem 3.1 in the discrete-time setting, for the sake of completeness. First of all, Proposition 8.2 holds intuitively because for all integers i P rns and k ě 1,

z rk`1s i " 1 1 `∆t ˜zrks i `∆t n ÿ j"1 P rks ij z rks j ¸P conv ˆ!z rks j ) jPrns ˙.
We then define the candidate set of limit points as in (8.6), and Claim 1 holds without any change in the statement or in the proof. Then, just as in Steps 2 and 3 in the proof of 8.1, we can first show that if z rks i is not already near some point in the candidate limit set, it will keep moving toward the boundary of the convex polytope. Finally, we can prove that tokens cannot circulate indefinitely between different points on the boundary. The combination of these arguments would establish the convergence of each token toward some point in the set given by (8.6).

Clustering toward hyperplanes

While being a natural example to consider, value matrices found empirically are much more general than V " I d , which we considered in the previous section. We now turn our attention to a significantly more general setting of value matrices, which we formalize as follows.

Definition 4.1. We call pQ, K, V q a good triple if the two following conditions are satisfied:

' the eigenvalue of V with largest modulus is real, positive, and simple; namely, λ 1 pV q ą |λ 2 pV q| ě . . . ě |λ d pV q|.

' xQφ 1 , Kφ 1 y ą 0 for any φ 1 P R d lying on the line kerpV ´λ1 pV qIdq.

The second condition simply states that the quadratic form xQ¨, K¨y is positive definite along the eigenspace associated to the leading eigenvalue of V . Note also that if all entries of V are positive, the first condition is automatically satisfied by virtue of the Perron-Frobenius theorem. In fact, this assumption is generic. On the one hand, it is satisfied by some pre-trained value matrices for ALBERT (Figure 10). On the other hand, numerical experiments indicate that a constant fraction (about 14%) of matrices from the real Ginibre ensemble in dimension d " 128-this proportion is known to vanish as d Ñ 8, albeit very slowly [START_REF] Rider | Extremal laws for the real Ginibre ensemble[END_REF].

Our clustering result in the setting of good triples can be summarized as follows: the coordinate xz i ptq, φ1 }φ1} y of any token z i ptq along the eigenspace spanned by φ 1 converges, as t Ñ `8, toward one among possibly 3 real scalars. Consequently, all the tokens z i ptq converge toward one among at most three parallel hyperplanes; see Fig. 6 for an illustration.

Theorem 4.2 (Convergence toward ď 3 hyperplanes). Assume that pQ, K, V q is a good triple in the sense of Definition 4.1. Then, for any initial sequence of tokens tz i p0qu iPrns Ă R d , there exist at most three parallel hyperplanes in R d such that for any i P rns, the distance of the solution z i ptq to (3.1) to one of these hyperplanes converges to 0 as t Ñ `8. ) We also observe that tokens typically cluster toward only two hyperplanes-a third one (passing through the origin) may appear for non-generic initial sequences. The hyperplanes are perpendicular to φ1 since V is diagonalizable.

The proof may be found in Section 9. The important role played by λ 1 pV q in the dynamics may be seen in (3.1): the component of z i ptq along φ 1 determines the size of e tV z i ptq in the exponent appearing in (3.1). The tokens z j ptq attracting other tokens z i ptq are those for which this component along φ 1 is largest in modulus. This attraction process forms the clusters. These leaders, as in all our results, have been empirically observed to be the ones carrying the largest amount of information in the sentence (see Supplementary material in [VSP `17]).

Furthermore, Theorem 4.2 can also be interpreted in more classical machine learning terms. On the one hand, it can be seen as an instance of K-flats clustering [BM00, Vid11]-points in the input sequence are clustered, based on their intrinsic similarity, to at most 3 "flats" of dimension d ´1. On the other hand, it ensures that for a good triple pQ, K, V q, (3.1) generates a linearly separable representation of tokens.

Beyond a single direction? Numerical experiments (e.g., Fig. 7) indicate that a similar phenomenon emerges for more complex V . We formulate following conjecture which is a natural generalization of Theorem 4.2.

Conjecture 4.3 (Codimension conjecture). Let k ě 1 be the number of eigenvalues of V with positive real part. Then there exist at most three parallel Euclidean subspaces of R d of codimension k such that for any i P rns, the distance of z i ptq to one of these subspaces converges to 0 as t Ñ `8. The negative eigenvalue generates a repulsive effect between the tokens, and we see a divergence along two lines (note the different scales between the four figures). (b) n " 256, d " 128, with pQ, K, V q fixed random matrices and V symmetric. For each coordinate j corresponding to a positive eigenvalue, the variance of the set tφ j pziptqq : i P rnsu (shaded area) tends to 0 with t, while the mean (solid lines) converges to one among two real scalars: one positive (top figure), one negative (bottom) figure. Coordinates corresponding to negative eigenvalues diverge (Fig. 15).

A mix of hyperplanes and polytopes

We now turn our attention to an even more general version of Theorem 4.2, which does not require the leading eigenvalue of V to be simple. The resulting theorem can be viewed as a combination of Theorem 4.2 and Theorem 3.1. Specifically, we assume that V behaves as the identity when acting on the eigenspace of the leading eigenvalue. This property is automatically satisfied if V is normal-so that its eigenvectors form an orthonormal basis-so we call such a V paranormal.

Definition 5.1. We call pQ, K, V q a good triple with multiplicity if the following conditions hold:

(i) Q J K is positive definite: Q J K ą 0;
(ii) V is paranormal: there exist two linear subspaces F, G Ă R d which are invariant under V , and such that F' G " R d , V |F " λId for λ ą 0, and ρpV | G q ă λ, where ρp¨q denotes the spectral radius (the maximal modulus of eigenvalues).

An example of such a V is used for Fig. 8. We may now state our main result in the setting of good triples with multiplicity. The proof may be found in Section 10.

Theorem 5.2 (Clustering for λ 1 with multiplicity). Suppose that pQ, K, V q is a good triple with multiplicity in the sense of Definition 5.1. Then, for any initial sequence tz i p0qu iPrns Ă R d , there exists a bounded convex polytope K Ă F such that setting H :" pBK Yt0uqˆG, for any i P rns, we have distpz i ptq, Hq Ñ 0 as t Ñ `8.

Part 2. Proofs

Well-posedness

We collect several facts regarding the global-in-time existence and uniqueness of solutions to all systems under consideration. Throughout the remainder of the paper, we use the terminology "tokens" and "particles" interchangeably.

To prove these results, we leverage the underlying continuity equation (see (6.1)). For the sake of future use, we prove a more general well-posedness result for the continuity equation than what is needed in this paper. 6.1. Notation. We denote by P c pR d q the set of compactly supported probability measures on R d , and by P 2 pR d q the set of probability measures µ on R d having finite second moment:

ş R d }x} 2 dµpxq ă `8. Let C 0 pR; P c pR d qq denote the Banach space of continuous curves R Q t Þ Ñ µptq P P c pR d q.
Here P c pR d q is endowed with the weak topology, which coincides with the topology induced by the Wasserstein distance W p for any p P r1, `8q.

As seen below, for compactness purposes regarding solutions to the continuity equation, we consider an additional property on the support of such curves, summarized by the following definition. Definition 6.1 (Equi-compactly supported curves). The set C 0 co pR; P c pR d qq consists of all elements µ P C 0 pR; P c pR d qq such that for any t 0 , t 1 P R, there exists a compact subset K Ă R d such that supppµptqq Ă K for any t P rt 0 , t 1 s.

We emphasise that there exist elements in C 0 pR; P c pR d qq which do not satisfy this property with regard to their support-e.g., µptq " p1 ´e´1 t 2 qδ 0 `e´1 t 2 δ 1 t .

-5 0 5 -5 0 5

-5 . As before, Q " K " I d , and we take V " diagp1, 1, ´1 2 q. A convex polytope K emerges before time 5, toward which two coordinates of the tokens cluster, and persists throughout the evolution, while the tokens diverge along the coordinate corresponding to the eigenvalue ´1 2 (note the different scales between the four figures).

0 5 t = 0.0 -5 0 5 -5 0

6.2.

Well-posedness of the ODEs. For any initial datum, i.e. a sequence of n points in R d , the dynamics (1.1) is well-posed, in the sense that it admits a unique solution defined for all times. Proposition 6.2. For any initial datum X 0 " px 0 1 , . . . , x 0 n q P pR d q n , there exists a unique Lipschitz continuous function R Q t Þ Ñ Xptq " px 1 ptq, . . . , x n ptqq such that x i p¨q solves (1.1) and satisfies x i p0q " x 0 i for any i P rns. We postpone the proof which is seen as a corollary of the well-posedness for the corresponding continuity equation. It follows that the equation (3.1) is also well-posed: Proposition 6.3. For any initial datum Z 0 " pz 0 1 , . . . , z 0 n q P pR d q n , there exists a unique Lipschitz continuous function R Q t Þ Ñ Zptq " pz 1 ptq, . . . , z n ptqq such that z i p¨q solves (3.1) and satisfies z i p0q " z 0 i for any i P rns.

Proof of Proposition 6.3. Since the equations (1.1) and (3.1) are related by the change of variables x i ptq " e tV z i ptq, Proposition 6.3 is an immediate consequence of Proposition 6.2. □ 6.3. The continuity equation. To prove Proposition 6.2, we show a more general result concerning global existence and uniqueness of solutions to the corresponding continuity equation3

# B t µ `divpX rµsµq " 0 in p0, `8q ˆRd µ |t"0 " µ 0 in R d , (6.1)
when X rµs is the attention kernel

X rµspxq :" ż R d e xQx,Kyy V y dµpyq ż R d e xQx,Kyy dµpyq . (6.2)
We will make use of the following notion of solution.

Definition 6.4. Fix µ 0 P P c pR d q. We say that t Þ Ñ µptq ": µ t is a solution to the Cauchy problem (6.1) if µ P C 0 co pR, P c pR d qq, the function

R Q t Þ Ñ ż R d
gpxq dµ t pxq is absolutely continuous for every g P C 8 c pR d q, and ż

R d gpxq dµ t pxq " ż R d gpxq dµ 0 pxq `ż t 0 ż R d
x∇gpxq, X rµ t spxqy dµ s pxq ds holds for almost every t P R.

We will make use of the following lemma regarding (6.2).

Lemma 6.5. For any R ą 0 there exists a constant C 1 pRq ą 0 such that for any µ, ν P P c pR d q with support in Bp0, Rq,

}X rµs} L 8 pR d ;R d q ď }V } op R, (6.3) }∇ x X rµs} L 8 pR d ;R dˆd q ď 2}Q J K} op }V } op R 2 (6.4) }X rµsp¨q ´X rνsp¨q} L 8 pBp0,Rq;R d q ď C 1 pRqW 2 pµ, νq. (6.5)
Proof. We henceforth set Gpx, yq :" e xQx,Kyy . To show (6.3), since G ą 0 we see that for any

x P R d , }X rµspxq} ⩽ }V } op ż Bp0,Rq Gpx, yq}y} dµpyq ż Bp0,Rq
Gpx, yq dµpyq

⩽ }V } op R.
We now show (6.4). Note that ∇ x Gpx, yq " Q J KyGpx, yq, thus, arguing as above, we find Using (6.8) and the fact that the Lipschitz constant }Gpx, ¨q} C 0,1 pBp0,Rqq is uniformly bounded for }x} ď R by some C R ą 0 in (6.7), we end up with ˇˇˇż

}∇ x X rµspxq} ⩽ ż Bp0,
R d Gpx, yqp dν ´dµqpyq ˇˇˇď C R W 2 pµ, νq.
The same chain of inequalities applies to the second integral in (6.6) (with the additional multiplier }V } op R), which finally leads us to (6.5). □

The following existence and uniqueness result is adapted from [PRT15, Theorem 2.3]. In fact, the result holds true for any vector field X rµs on R d satisfying conditions analog to those entailed by Lemma 6.5. Proposition 6.6. For any initial condition µ 0 P P c pR d q, the Cauchy problem (6.1) admits a unique solution µ P C 0 co pR; P c pR d qq in the sense of Definition 6.4. Furthermore, we have the following stability estimate for solutions: for any R ą 0 and T ą 0, there exists a constant CpT, Rq ą 0 such that for any µ 0 , ν 0 P P c pR d q with support in Bp0, Rq, W 2 pµptq, νptqq ď e CpT,Rqt W 2 pµ 0 , ν 0 q (6.9)

for any t P r0, T s, where µptq and νptq solve (6.1) with initial conditions µ 0 and ν 0 respectively.

Results of this nature can be found in the literature-see for instance [START_REF] Piccoli | Control to flocking of the kinetic Cucker-Smale model[END_REF]. They are however not sufficient for our purposes. We wrote Proposition 6.6 in the W 2 setting instead of the usual W 1 setting (used for instance for the classical Dobrushin estimate [START_REF] Roland | Vlasov equations[END_REF][START_REF] Golse | Mean field kinetic equations[END_REF]) because it allows to extend the results of [START_REF] Weinan | A mean-field optimal control formulation of deep learning[END_REF] without difficulty from classical ResNets to self-attention dynamics. We recall that the goal of [START_REF] Weinan | A mean-field optimal control formulation of deep learning[END_REF] is to import classical (mean-field) optimal control tools such as the Pontryagin maximum principle and the analysis of Hamilton-Jacobi-Bellman equations to deep learning, and relies heavily on W 2 estimates (e.g., in [WHL19, Section 4]).

Proof of Proposition 6.6. To ease reading, we split the proof in three parts.

Part 1: Existence. Fix an arbitrary T ą 0. For k ě 1, set

τ k :" T 2 k .
We define a sequence of curves µ k : r0, T s Ñ P c pR d q by the following scheme4 : (i) µ k p0q :" µ 0 ;

(ii) µ k pℓτ k `tq :" ´Φt X rµ k pℓτ k qs ¯# µ k pℓτ k q for ℓ P t0, . . . , 2 k ´1u and t P p0, τ k s, where for any x P R d , Φ t X rµ k pℓτ k qs pxq is the unique solution to the Cauchy problem # 9 yptq " X rµ k pℓτ k qspyptqq on r0, τ k s yp0q " x.

(The above problem indeed has a unique solution for any x P R d by virtue of the Cauchy-Lipschitz theorem, using (6.4).) By construction, µ k P C 0 pr0, T s; P c pR d qq for any k ⩾ 1.

We begin by showing that there exists a radius R " RpT q ą 0 independent of k such that supppµ k ptqq Ă Bp0, Rq for any k ⩾ 1 and t P r0, T s. To this end, for any t P r0, T s and k ⩾ 1, let R k ptq ą 0 denote the smallest positive radius5 such that supppµ k ptqq Ă Bp0, R k ptqq. We will first look to show that

supppµ k pℓτ k `tqq Ă Bp0, R k pℓτ k q `t}V } op R k pℓτ k qq.
(6.10) Let x P supppµ k pℓτ k `tqq, thus µ k pℓτ k `tqpBpx, εqq ą 0 for any ε ą 0. By the change of variables formula, we find that ż

pΦ t X rµ k pℓτ k qs q ´1 pBpx,εqq dµ k pℓτ k qpzq ą 0.
Consequently pΦ t X rµ k pℓτ k qs q ´1pBpx, εqqXsupppµ k pℓτ k qq ‰ H, and let z be an element lying in this set. From the Duhamel formula, we gather that

Φ t X rµ k pℓτ k qs pzq ": yptq " z `ż t 0 X rµ k pℓτ k qspypsqq ds.
Since z P pΦ t X rµ k pℓτ k qs q ´1pBpx, εqq, we find that

› › › › z `ż t 0 X rµ k pℓτ k qspypsqq ds ´x› › › › ď ε.
Using the triangle inequality, (6.3), and since z P supppµ k pℓτ k qq implies z P Bp0, R k pℓτ k qq, we deduce that }x} ⩽ ε `t}V } op R k pℓτ k q `Rk pℓτ k q. Since ε ą 0 is arbitrary, this inequality yields (6.10). We now use (6.10) to prove the original claim. Using the definition of the radius R k ptq, we evaluate (6.10) at t " τ k and find R k ppℓ `1qτ k q ⩽ p1 `}V } op τ k qR k pℓτ k q. By induction, we deduce that

R k pℓτ k q ⩽ p1 `}V } op τ k q ℓ R k p0q, whence R k pℓτ k q ⩽ ˆ1 `}V } op T 2 k ˙2k R k p0q ă e }V }opT R 0 ,
where R 0 ą 0 denotes the smallest positive radius such that supppµ 0 q Ă Bp0, R 0 q. Since the above bound is independent of k, the claim follows, yielding the desired radius R " RpT q ą 0 bounding the support of every element in the sequence. In turn, we also deduce that µ k P C 0 co pR; P c pR d qq for any k ⩾ 1. Using the above fact, along with (6.3) and the definition of µ k pℓτ k `tq, we find that W 2 `µk pℓτ k `tq, µ k pℓτ k q ˘ď }V } op Rt for any ℓ P t0, . . . , 2 k ´1u, t P p0, τ k s and k ⩾ 1. Gluing these inequalities (for different ℓ and t) with the triangle inequality yields W 2 `µk ptq, µ k psq ˘ď }V } op R|t ´s| for any t P r0, T s. Since µ k p0q " µ 0 for any k ě 1, and since P 2 pR d q is the completion of P c for the Wasserstein distance W 2 , the Arzelà-Ascoli theorem implies the existence of a subsequence uniformly converging to some µ ˚P C 0 pr0, T s; P 2 pR d qq.

Since for any t P r0, T s the curves µ k ptq have their support enclosed in Bp0, Rq for any k ⩾ 1, we even deduce that µ ˚P C 0 co pR, P c pR d qq. Note moreover that µ ˚p0q " µ 0 and that W 2 pµ ˚ptq, µ ˚psqq ď }V } op R|t ´s| for any t, s P r0, T s.

The fact that µ ˚is a solution of (6.1) follows exactly from the same computations as in [PRT15, p. 4711-4712], starting from (A.2) therein. We do not reproduce here this argument since the computations are the same word for word. The fact that for any T ą 0 we have sup tPr0,T s W 1 pµ ˚ptq, µ k ptqq Ñ 0 as k Ñ `8, which is instrumental in [PRT15, p. 4711-4712], follows in our case from the left-hand-side of (6.8).

Part 2: Uniqueness. Regarding uniqueness, we proceed as follows. We first recall the following estimate from [PR16, Proposition 4]. Let p ě 1, let t ě 0, let v, w P C 0,1 X L 8 pr0, ts ˆRd ; R d q (both with Lipschitz constant L ą 0, say), and let µ, ν P P c pR d q. Then W p `pΦ t v q # µ, pΦ t w q # ν ˘ď e p`1 p Lt W p pµ, νq `e Lt p pe Lt ´1q L }v ´w} L 8 pr0,tsˆR d ;R d q .

(6.11) Now assume that there are two solutions µ and ν of (6.1), with a spatial support that is locally bounded in time, and having the same initial condition. Define vpt, xq :" X rµptqspxq and wpt, xq :" X rνptqspxq. Also set t 0 :" inftt ě 0 : W 2 pµptq, νptqq ‰ 0u, and assume that t 0 ‰ `8. Fix T ą t 0 and take R ą 0 such that µ t and ν t are supported in Bp0, Rq for any t P r0, T s. Using (6.11) with p " 2, and setting C 2 pRq :" 2}Q J K} op }V } op R 2 in (6.4), we find W 2 pµpt 0 `sq, νpt 0 `sqq ď e 2C2pRqs W 2 pµpt 0 q, νpt 0 qq `eC2pRqs e C2pRqs ´1 C 2 pRq sup τ Prt0,t0`ss }vpτ, ¨q ´wpτ, ¨q} L 8 pR d q .

Choose s ą 0 sufficiently small so that e C2pRqs ´1 ď 2C 2 pRqs. Then, by virtue of (6.5) and the fact that W 2 pµpt 0 q, νpt 0 qq " 0, we deduce W 2 pµpt 0 `sq, νpt 0 `sqq ď 2se C2pRqs sup τ Prt0,t0`ss W 2 pµpτ q, νpτ qq. (6.12)

We choose s 1 ą 0 satisfying both e C2pRqs 1 ´1 ď 2C 2 pRqs 1 and 2s 1 e C2pRqs 1 ă 1. Applying (6.12) to every s P r0, s 1 s we obtain sup sPr0,s 1 s W 2 pµpt 0 `sq, νpt 0 `sqq ď 2s 1 e C2pRqs 1 sup τ Prt0,t0`s 1 s W 2 pµpτ q, νpτ qq ă sup sPr0,s 1 s W 2 pµpt 0 `sq, νpt 0 `sqq, which is a contradiction. Therefore µptq " νptq for any t ě 0, which proves uniqueness, as desired.

Part 3: Stability. We do not detail the proof of estimate (6.9), which is very similar to the proof of (2.3) in Theorem 2.3 of [START_REF] Piccoli | Control to flocking of the kinetic Cucker-Smale model[END_REF]: it follows from (6.11) with p " 2, and the argument after (A.7) in [START_REF] Piccoli | Control to flocking of the kinetic Cucker-Smale model[END_REF], with W 2 instead of W 1 . See also [START_REF] Piccoli | Transport equation with nonlocal velocity in Wasserstein spaces: convergence of numerical schemes[END_REF]Theorem 3]. □

We conclude this section with the proof of Proposition 6.2, which follows as a corollary of the above derivations.

Proof of Proposition 6.2. We first show existence. We apply Proposition 6.6 with µ 0 :" 1 n ř n j"1 δ x 0 i , which in turn yields a solution µptq to (6.1). Following the proof of Proposition 6.6, we also know that this solution satisfies µptq " pΦ t X rµptqs q # µ 0 for any t P R, and the vector field X rµptqs satisfies the assumptions of the Cauchy-Lipschitz theorem. In particular, µptq is of the form µptq " 1 n ř n j"1 δ xiptq for some Lipschitz curves R Q t Þ Ñ x i ptq, for i P rns. Then t Þ Ñ µptq " 1 n ř n j"1 δ xiptq is a solution to the Cauchy problem (6.1)-(6.2) in the sense of Definition 6.4. Secondly, we show uniqueness. Suppose that Xptq " px 1 ptq, . . . , x n ptqq and X ˚ptq are two Lipschitz solutions to (1.1), with the same initial conditions. Then for a.e. t ě 0, using the equation (1.1) and the fact that the attention matrix coefficients P ij ptq defined in (1.2) belong to r0, 1s, we obtain

1 2 d dt max iPrns }x i ptq} 2 ď }V } op max iPrns }x i ptq} 2
(and analogously for x i ptq). Using Grönwall's inequality, we deduce the existence of two constants c 1 , c 2 ą 0 such that for any t ą 0 and for any i P rns, }x i ptq} and }x i ptq} are bounded from above by c 1 e c2t . It then follows that the empirical measures µp¨q " 1 n ř n j"1 δ xip¨q and µ ˚p¨q " 1 n ř n j"1 δ x i p¨q belong to C 0 co pR, P c pR d qq. Moreover, they satisfy µptq " pΦ t X rµptqs q # µ 0 and µ ˚ptq " pΦ t X rµ ˚ptqs q # µ 0 and are thus solutions to (6.1). Using the uniqueness result of Proposition 6.6, we obtain that µ " µ ˚which concludes the proof. □

Proof of Theorem 2.1

Throughout this section we focus on the following dynamics:

9 x i ptq " n ÿ j"1
ˆexxiptq,xjptqy ř n k"1 e xxiptq,x k ptqy ˙xj ptq.

(7.1)

Note that for d " 1, the dot products in (7.1) are just multiplications of scalars. We begin with the following observation, which holds for any d ě 1.

Lemma 7.1. For any x 1 , . . . , x n P R d , the function f : R d Ñ R defined by

f : x Þ Ñ log ˜n ÿ j"1 e xx,xj y ¸(7.2) is convex.
Proof. Using the elementary inequality pa `bq ě 2pabq 1 2 for any a, b ě 0, we have

exppf pxq `f pyqq " ˜n ÿ j"1 exppxx, x j yq ¸˜n ÿ j"1 exppxy, x j yq " 1 2 n ÿ j"1 n ÿ k"1 " exp pxx, x j y `xy, x k yq `exppxx, x k y `xy, x j yq ı (7.3) ě n ÿ j"1 n ÿ k"1 exp ˆB x `y 2 , x j `xk F˙( 7.4) " exp ˆ2f ˆx `y 2 ˙˙.
Taking the log on both sides yields the statement. □

The following lemma also holds for any d ě 1.

Lemma 7.2. Let R Q t Þ Ñ tx i ptqu iPrns be a solution to (7.1). Then for any i, j P rns, the map R Q t Þ Ñ }x i ptq ´xj ptq} is non-decreasing.

Proof. The dynamics (7.1) can be equivalently written as

9 x i ptq " ∇f px i ptqq
where f is as in (7.2). By convexity of f (Lemma 7.1), 1 2 d dt }x i ptq ´xj ptq} 2 " x 9 x i ptq ´9 x j ptq, x i ptq ´xj ptqy " x∇f px i ptqq ´∇f px j ptqq, x i ptq ´xj ptqy ě 0, as desired. □

We now present the proof of Theorem 2.1, which assumes d " 1. We recall that in the statement, V is a positive scalar, but by reparametrizing time we may assume that V " 1, so the 1d dynamics under consideration is really given by (7.1). Also, to ease notations we focus on QK " 1, but the proof adapts straightforwardly to the setting QK ą 0 assumed in the statement of Theorem 2.1.

As seen in Section 7.1, it is not difficult to prove the convergence of the coefficients P ij ptq of the attention matrix for indices i P rns for which x i ptq becomes unbounded as t Ñ `8. This is the case for at least n ´1 of the particles x i ptq (Lemma 7.6). But should one particle x i ptq remain bounded, proving the convergence of P ij ptq for j P rns is slightly tedious (Section 7.2). Since d " 1, up to relabeling, we can order the initial collection of particles (which, we recall, are assumed distinct):

x 1 p0q ă . . . ă x n p0q.

We set c :" min iPrn´1s |x i`1 p0q ´xi p0q|.

(7.5)

According to Lemma 7.2, we have |x i ptq ´xj ptq| ě c for any i ‰ j and any t ě 0.

In particular, particles never "collide".

7.1. Results about unbounded particles. In this section we gather several results concerning the indices i corresponding to particles x i ptq which are not uniformly bounded in time. In particular, in Lemma 7.4 we show that for such indices i, P ij ptq converges toward 0 or 1 for any j P rns.

Lemma 7.3. Let A ą 0 denote the unique positive real number satisfying A 2 " n 2 expp´A 2 q. If x n pt 0 q ą A for some time t 0 ě 0, then there exists c 1 ą 0 such that x n ptq ě c 1 e t for any sufficiently large t ą 0. Similarly, if x 1 pt 0 q ă ´A for some t 0 ě 0, then x 1 ptq ď ´c1 e t for any sufficiently large t ą 0.

Proof. The two cases are symmetric since the evolution (7.1) commutes with the involution of pR d q n given by px 1 , . . . , x n q Þ Ñ p´x 1 , . . . , ´xn q. We thus focus on the case x n pt 0 q ą A. We provide some detail on the above sequence of inequalities. First of all, to pass from (7.6) to (7.7), we use e xnptqpx k ptq´xnptqq ď e ´cxnptq for j " n and for any k P rns (which holds by virtue of (7.5)), combined with the fact that

n ÿ k"1 e xnptqpx k ptq´xnptqq ě 1
for all indices j such that x j ptq ă 0. To pass from (7.7) to (7.8), we use e xnptqz z ě ´1 xnptq , which holds for any z ď 0.

For any B ą A, we clearly have

B n ´n e ´B2 B ą 0.
We then deduce from (7.8) and the fact that x n pt 0 q ą A that x n ptq Ñ `8 as t Ñ `8. Moreover due to the fact that the expression in (7.9) is bounded from below by xnptq 2n whenever x n ptq is sufficiently large, we deduce that

x n ptq ě c 0 e t 2n
for any sufficiently large t ą 0.

Coming back to (7.8), we find that for sufficiently large t ą 0,

9 x n ptq ě x n ptq ˜1 1 `pn ´1qe ´cc0e t 2n ´e´c 2 0 e t n

¸.

This implies that d dt logpx n ptqq ě 1 ´O ´e´t 3n ¯, whence logpx n ptqq ě t `Op1q for sufficiently large t ą 0, as desired. □

Here and in what follows, δ jk denotes the Kronecker symbol.

Lemma 7.4. If i P rns is such that x i ptq is not uniformly bounded with respect to t ą 0, then x i ptq converges to either ´8 or `8 as t Ñ `8. Moreover, (1) if x i ptq Ñ `8, then for any j P rns, P ij ptq converges to δ nj as t Ñ `8, with doubly exponential rate.

(2) if x i ptq Ñ ´8, then for any j P rns, P ij ptq converges to δ 1j as t Ñ `8, with doubly exponential rate.

Proof. We assume that x i ptq is not uniformly bounded with respect to t ą 0. Without loss of generality, we assume that there exists a sequence of positive times tt k u `8 k"1 with t k Ñ `8 such that x i pt k q Ñ `8. Necessarily, x n pt k q Ñ `8. We notice that if x i ptq ą 0 for some t ě 0, then, arguing as in (7.6)-(7.7)-(7.8), we have

9 x i ptq " n ÿ j"1 ˆexiptqpxjptq´xnptqq ř n k"1 e xiptqpx k ptq´xnptqq ˙xj ptq ě
x n ptq n ´n x i ptq e ´xiptqxnptq . (7.10)

For sufficiently large integers k ě 1, from (7.10) we get 9

x i pt k q ą 0 and 9

x n pt k q ą 0. But as x i and x n increase, the lower bound in (7.10) becomes larger. It follows that 9 x i ptq ě

x n ptq 2n ě x i ptq 2n for sufficiently large t, implying that x i ptq Ñ `8 with exponential rate as t Ñ `8.

We now prove point 1. regarding P ptq. We assume that x i ptq Ñ `8 as t Ñ `8. In this case, for j ‰ n (namely j P rn ´1s),

P ij ptq " e xiptqxj ptq n ÿ k"1 e xiptqx k ptq
ď e xiptqpxj ptq´xnptqq ď e ´cxiptq , thus P ij ptq converges to 0 as t Ñ `8 (with doubly exponential rate). Consequently, we also deduce that

P in ptq " 1 ´n´1 ÿ j"1 P ij ptq
converges to 1, also with doubly exponential rate, as t Ñ `8.

The case where x i ptq Ñ ´8 is symmetric. This concludes the proof. □

Our last result is useful in the next section.

Lemma 7.5. For any i P rns such that x i ptq is not uniformly bounded with respect to t ą 0, there exists some γ i P R, γ i ‰ 0 such that x i ptq " γ i e t `ope t q as t Ñ `8.

Proof. Without loss of generality we assume that x i ptq Ñ `8 as t Ñ `8. For j ‰ n, we find

P ij ptq " e xiptqxj ptq n ÿ k"1 e xiptqx k ptq " e xiptqpxj ptq´xnptqq n ÿ k"1 e xiptqpx k ptq´xnptqq ď e ´cxiptq .
Consequently, P in ptq ě 1 ´ne ´cxiptq .

Therefore, using Lemma 7.3 and the fact that x i ptq ě b i e t 2n for some b i ą 0 (thanks to (7.10)), we gather that 9 x i ptq ě ´1 ´ne ´cxiptq ¯xn ptq ´ne ´cxiptq c 1 e t ě ˆ1 ´ne ´cbie t 2n

˙xn ptq ´ne ´cbie for some c 1 ą 0 independent of t. We also notice that due to (7.1), 9

x i ptq ď x n ptq. Using (7.11), firstly for i " n, together with the trivial upper bound x n ptq ď Ce t for some C ą 0 independent of t (immediately seen from (7.1)), we obtain 9 x n ptq " x n ptq ˆ1

`o ˆe´cbie t 3n ˙ȧs t Ñ `8, which yields x n ptq " γ n e t `ope t q for some γ n ą 0. Now using (7.11) for the index i, we gather that

9 x i ptq " x n ptq `o ˆe´cbie t 3n ˙,
and so we deduce that x i ptq " γ n e t `ope t q.

Similarly, if x i ptq Ñ ´8, then x i ptq " γ 1 e t `ope t q. This proves Lemma 7.5 (and shows that γ i P tγ 1 , γ n u). □ 7.2. Results about bounded particles. In this section we collect results concerning particles which remain uniformly bounded in time. The following lemma entails that there can be at most one particle with this property.

Lemma 7.6. Consider B :"

! i P rns : x i p¨q P L 8 pr0, ` 8qq
) .

Then #B P t0, 1u.

Proof. We first prove that either x 1 ptq Ñ ´8 or x n ptq Ñ `8 as t Ñ `8. By contradiction, if this is not the case, then by Lemma 7.3, px 1 ptq, . . . , x n ptqq P r´A, As n for any t ě 0. We denote by I the set of configurations px 1 , . . . , x nq P r´A, As n such that |x i ´xj | ě |x i p0q ´xj p0q| ą 0 for any distinct i, j P rns. For any X ˚" px 1 , . . . , x nq P I, the function f defined in (7.2) (with anchor points given by X ˚) is strictly convex-the equality in the inequality between (7.3) and (7.4) is never achieved. Therefore, the proof of Lemma 7.2 shows that if X ˚is seen as an initial datum for the dynamics (7.1), then

vpX ˚q :" d dt |t"0 |x 1 ptq ´xn ptq| ą 0.
Since I is compact, v 0 :" inf X ˚PI vpX ˚q ą 0. Hence, t Þ Ñ |x 1 ptq ´xn ptq| grows at least linearly, which is a contradiction. We may therefore assume without loss of generality that x 1 ptq Ñ ´8 as t Ñ `8. We prove that x n ptq converges to either ´8, or 0, or `8, as t Ñ `8. We assume in the sequel that x n ptq does not converge to ´8 or 0. For any i P rns, if there exists ε ą 0 and a sequence of positive times ts k u `8 k"1 tending to `8 such that x i ps k q ď ´ε, then it follows from (7.10) that x i ptq Ñ ´8. Therefore, by our assumptions, we have lim inf tÑ`8 x n ptq ě 0. Also, since x n ptq ↛ 0, there exists ε ą 0 and a sequence of positive times tt k u `8 k"1 tending to `8 such that x n pt k q ě ε for any integer k ⩾ 1. For any t ě 0 such that x n ptq ě ε, we introduce the set of indices N ptq " ti P rns : x i ptq ă 0u, According to Lemma 7.4, any point x i ptq which takes negative values for arbitrarily large times and does not converge to ´8 has to converge to 0. Therefore, the second term in the lowermost bound in (7.12) is lower bounded by ´ε 2n for sufficiently large t. All in all, we gather that 9

x n ptq ě ε 2n and x n ptq converges to `8 as t Ñ `8. If it converges to 0, then necessarily x n´1 ptq Ñ ´8 by combining Lemma 7.2 with Lemma 7.4. This proves Lemma 7.6 in this case.

From now on we assume that x n ptq Ñ `8. Using (7.10) we see that if there exists ε ą 0 such that x i ptq ą ε for an unbounded sequence of times t, then x i ptq Ñ `8. The same is true symmetrically when x i ptq ă ´ε for an unbounded sequence of times t. Thus if i P B, necessarily x i ptq Ñ 0. By Lemma 7.2 this can be true for at most one index i, which concludes the proof of Lemma 7.6. □

If B " H, Theorem 2.1 follows from Lemma 7.4. From now on, we assume that #B " 1, and we denote by i 0 P rns its unique element. We distinguish two cases: either i 0 P t1, nu (Lemma 7.7), or i 0 R t1, nu (Lemma 7.8).

Lemma 7.7. If x n ptq is bounded as t Ñ `8, then P nn ptq Ñ 1, and P nj ptq Ñ 0 for any j P rn ´1s, as t Ñ `8. Similarly, if x 1 ptq is bounded as t Ñ `8, then P 11 ptq Ñ 1, and P 1j ptq Ñ 0 for any j P rn ´1s, as t Ñ `8.

Proof. The two cases (x n p¨q bounded or x 1 p¨q bounded) are symmetric since the evolution (7.1) commutes with the involution of pR d q n given by px 1 , . . . , x n q Þ Ñ p´x 1 , . . . , ´xn q. Whence, we only address the first one: we assume that x n ptq is bounded as t Ñ `8. We first notice that all particles x j ptq for j P rn ´1s tend to ´8 as t Ñ `8 due to Lemma 7.6. We now prove the following properties:

(1) x n ptq ą 0 for any sufficiently large t;

(2) x n ptq Ñ 0 as t Ñ `8;

(3) for any j P rn ´1s, P nj ptq Ñ 0 as t Ñ `8.

To prove point (1), we notice that for sufficiently large t, x i ptq ď 0 for any i P rn´1s. If in addition x n ptq ď 0, then due to (7.1), all x i ptq (i P rns) remain negative and due to (7.1), x n ptq Ñ ´8 as t Ñ `8, which is a contradiction.

For point (2), we fix ε ą 0, and set T ὲ :" tt ě 0 : x n ptq ě εu.

We prove that if T ὲ is unbounded, then x n ptq Ñ `8 as t Ñ `8, which is a contradiction. As a consequence, T ὲ is bounded for any ε ą 0, which implies (in conjunction with point 1.) that x n ptq Ñ 0 as t Ñ `8. So let us assume that T ὲ is unbounded. We notice that for any δ ą 0, if t P T ὲ is sufficiently large then ˇˇe xnptqxj ptq x j ptq ˇˇď δ for any j P rn ´1s since x j ptq Ñ `8 as t Ñ `8. Therefore, n ÿ j"1 e xnptqxj ptq x j ptq ě e ε 2 ε ´pn ´1qδ ě 0, where we took δ ą 0 sufficiently small for the last inequality to hold. Consequently,

9
x n ptq " It is not difficult to see that this implies that x n ptq Ñ `8 as t Ñ `8, which is a contradiction.

For point (3), we first notice that for any j ‰ n, since x j ptq Ñ ´8,

9 x j ptq " n ÿ k"1 ˆexjptqpx k ptq´xnptqq ř n ℓ"1 e xj ptqpx ℓ ptq´xnptqq ˙xk ptq ď x 1 ptq n `n ε e ´xj ptqxnptq .
Using Lemma 7.3, we deduce the existence of some c 2 ą 0 such that x j ptq ď ´c2 e t for any sufficiently large t ą 0. We now prove that for any j ‰ n,

x j ptqx n ptq ´xn ptq 2 ÝÑ tÑ`8

´8.

(7.13)

Due to the ordering of the particles, it is enough to prove (7.13) for j " n ´1. Fix j " n ´1 and κ ą 0, and assume that

x n ptqx j ptq ě x n ptq 2 ´κ for some t ě 0. Then, using the fact that

x n ptqx j ptq ě x n ptqx k ptq for any k P rn ´2s, we get P nj ptq ě e xj ptqxnptq e xnptq 2 `pn ´1qe xnptqxj ptq ě ε, where ε " 1 n`e κ . We obtain 9

x n ptq ď P nn ptqx n ptq `Pnj ptqx j ptq ď x n ptq `εx j ptq, hence d dt `xn ptqpx n ptq ´xj ptqq ˘" 9

x n ptqp2x n ptq ´xj ptqq ´xn ptq 9 x j ptq ď px n ptq `εx j ptqqp2x n ptq ´xj ptqq ´xn ptq 9 x j ptq " ´εx j ptq 2 `xn ptqp2εx j ptq `2x n ptq ´xj ptq ´9 x j ptqq ď ´εx j ptq 2 `xn ptqp2x n ptq ´2x 1 ptqq, (7.14)

where in the last line we used the fact that 9 x j ptq ě x 1 ptq, which is due to (7.1), and that x 1 ptq ă x j ptq, which is due to the ordering of the particles. Since x j ptq ď ´c2 e t and x 1 ptq ě ´c1 e t , the upper bound in (7.14) is negative if t is large enough. We therefore conclude that for any fixed κ, if there exist unbounded times t such that x n ptqx j ptq ě x n ptq 2 ´κ, then x n ptqx j ptq ě x n ptq 2 ´κ for any t large enough. But this is excluded since x n ptq ą 0 and x j ptq Ñ ´8 as t Ñ `8. This concludes the proof of (7.13), and the lemma follows by plugging this information into the definition of P nj ptq. □ Lemma 7.8. If i 0 R t1, nu and x i0 ptq remains uniformly bounded in t, then for any j P rn ´1s, there exists some α j P r0, 1s such that P i0j ptq Ñ α j as t Ñ `8.

Proof. Assume that i 0 R t1, nu. Then x 1 ptq Ñ ´8 and x n ptq Ñ `8 as t Ñ `8. Also, x i0 ptq Ñ 0 due to (7.10). We write x i0 ptq " y i0 ptqe ´t. Since γ n ą 0 and γ 1 ă 0, we notice that the function

g : θ Þ Ñ ÿ iPrnszti0u e γiθ γ i 1 `ÿ iPrnszti0u e γiθ
takes value ´8 at ´8, and `8 at `8, and has a positive derivative. Thus, it takes the value 0 exactly once, and we denote this point by θ 0 . We prove that y i0 ptq Ñ θ 0 as t Ñ `8. We observe that e xi 0 ptq 2 " 1 `op1q.

Using Lemma 7.5 we have 9 y i0 ptq " e t 9 x i0 ptq ´yi0 ptq " pP i0i0 ptq ´1qy i0 ptq `e2t

ÿ jPrnszti0u ¨eyi 0 ptqpγj `op1qq
1 `op1q `ÿ kPrnszti0u e yi 0 ptqpγ k `op1qq ‹ ‹ ' pγ j `op1qq.

We recognize that the sum in the above expression is roughly equal to gpy i0 q. If the latter is not close to 0 for large times, then 9 y i0 ptq necessarily have a huge magnitude due to the e 2t factor, leading to a contradiction. Fix ε ą 0. If y i0 ptq ą θ 0 `ε for some large time t ą 0, then, noticing that |y i0 ptq| " e t |x i0 ptq| " ope t q, (7.15) we get 9 y i0 ptq " ope t q `e2t ´g`y i0 ptq `opy i0 ptqq ˘¯.

But gpy i0 ptqq ě δ " δpεq, and hence

9 y i0 psq ě δ 2 e 2s
for any larger time s ě t, which contradicts (7.15). We get a similar contradiction if y i0 ptq ă θ 0 ´ε for large enough t. This concludes the proof that y i0 ptq Ñ θ 0 . As a consequence, x i0 ptqx i ptq Ñ θ 0 γ i for any i ‰ i 0 , and we deduce Lemma 7.8. □ 7.3. Concluding the proof of Theorem 2.1.

Proof of Theorem 2.1. By Lemma 7.6, there is at most one index i 0 P rns for which the particle x i0 ptq remains bounded for any t ą 0. In turn, for any i P rnszti 0 u, we may invoke Lemma 7.4 which entails that P ij ptq converges to either δ 1j or δ nj as t Ñ `8 (with doubly exponential rate). And by ordering of the particles, for indices i 1 ď i 2 different from i 0 , and P i1j ptq Ñ δ nj then necessarily P i2j ptq Ñ δ nj as well. Consequently, all but at most one row of P ptq converge to either e 1 " p1, 0, . . . , 0q or e n " p0, . . . , 0, 1q as t Ñ `8. For the i 0 -th row, we may invoke either Lemma 7.7 or Lemma 7.8. The former applies if i 0 P t1, nu, and entails that the i 0 -th row of P ptq converges either to e 1 or e n , while the latter applies if i 0 R t1, nu, and entails that the i 0 -th row of P ptq converges to some vector α P R d with non-negative entries.

Finally, since the i 0 -th row of P ptq has entries which sum up to 1, then so does α. These conclusions lead us to a final limit matrix P ˚which has precisely the form indicated in Fig. 2 (namely, P ˚P Pq, as desired. □ Remark 7.9 (Higher dimensions). The extension of Theorem 2.1 to d ě 2 is not straightforward due to rare pathological situations. For example, suppose d " 2, n " 2, and the initial configuration x 1 p0q " p1, εq and x 2 p0q " p1, ´εq. One can check that x i ptq Ñ p1, 0q as t Ñ `8, for i " 1, 2, which means that a single cluster appears. However, the self-attention matrix converges toward the identity (which has rank 2). Therefore, it is not true in full generality that the rank of the limiting self-attention matrix is equal to the number of clusters as t Ñ `8, although we believe that the result is true for almost all initial conditions.

8. Proofs of Theorems 3.1 and 8.5

In this section, we focus on proving the result in the case

V " I d .
We also provide a full picture of the behavior of the dynamics in the case V " ´Id in Section 8.2.

8.1. Clustering towards vertices of convex polytopes: Theorem 3.1. In this section, we prove Theorem 8.1-namely, we show that particles tz i ptqu iPrns following the rescaled dynamics

9 z i ptq " n ÿ j"1
˜ee 2t xAziptq,Azj ptqy ř n k"1 e e 2t xAziptq,Az k ptqy ¸pz j ptq ´zi ptqq (8.1) converge, as t Ñ 8, toward points lying on the boundary of a particular convex polytope. In (8.1) we made use of the shorthand notation

A :" `QJ K ˘1 2 . (8.2)
The precise statement is the following:

Theorem 8.1. Suppose V " I d and Q J K ą 0. Then, for any initial datum tz i p0qu iPrns Ă R d , the solution to (8.1) is such that its convex hull conv `tz i ptqu iPrns converges to some convex polytope K Ă R d as t Ñ `8. Furthermore, let V " tv 1 , . . . , v m u (m ď n) denote the set of vertices of K, and consider S :"

" x P K : }Ax} 2 " max jPrms xAx, Av j y * ,
with A defined in (8.2). Then S has finite cardinality, and V Ă S Ă BK Y t0u. Finally, for any i P rns there exists a point z P S such that z i ptq Ñ z as t Ñ `8.

In particular, z i ptq converges either to some point on the boundary of K, or to 0.

8.1.1. The convex hull is shrinking. To prove Theorem 8.1, we begin with the following illustrative result.

Proposition 8.2. Suppose V " I d and Q J K ą 0. Then the solution tz i p¨qu iPrns to (8.1) is such that t Þ Ñ convptz i ptqu iPrns q is non-increasing in the sense of setinclusion.

Proof of Proposition 8.2. Fix t ą 0 and let H Ă R d be a closed half-space which does not contain any of the points z i ptq. We define the map

α : s Þ Ñ min iPrns distpz i psq, Hq
for s ⩾ 0. We claim that α is non-decreasing on rt, `8q. (8.3)

Before proving (8.3), let us show how to conclude the proof of Proposition 8.2 using this claim. It follows from (8.3) that if convptz i ptqu iPrns q X H " H, then convptz i pt 1 qu iPrns q X H " H for any t 1 ě t. Writing the convex set convptz i ptqu iPrns q as

convptz i ptqu iPrns q " č H 1 open half-space convptziptqu iPrns qĂH 1 H 1 " č H closed half-space convptziptqu iPrns qXH"H R d zH,
we get that convptz i pt 1 qu iPrns q Ă convptz i ptqu iPrns q for any t 1 ě t.

We now turn to the proof of the claim (8.3). Denoting by n the unit outer normal to H and by proj H the orthogonal projection onto the closed set H, we have distpx, Hq " xx ´proj H pxq, ny. P ij psqxz j psq ´zi psq, ny ě 0, where the last inequality comes from the fact that each term in the sum is nonnegative, since i P M psq. This proves (8.3) (and, as a byproduct, that T " `8). □

If t Þ Ñ xptq is a differentiable curve,
The following fact immediately ensues.

Corollary 8.3. For any i P rns and t ě 0, z i ptq P convptz i p0qu iPrns q. In particular, z i p¨q is uniformly bounded in time.

8.1.2. Proof of Theorem 8.1.

Proof of Theorem 8.1. As a consequence of Proposition 8.2, the set convptz i ptqu iPrns q converges as t Ñ `8 toward some convex polytope K. In the remainder of the proof, we look to show that the particles z i ptq can in fact converge only to some well-distinguished points lying on the boundary of this polytope.

Step 1. The candidate set of limit points. We denote by V " tv 1 , . . . , v m u the set of vertices of K. Writing any x P K as a convex combination of these vertices:

x " ř m j"1 α j v j for some weights α j ě 0 with ř m j"1 α j " 1, we gather that The following holds-we postpone the proof to after that of the theorem.

}Ax} 2 " C Ax, m ÿ j"1 α j Av j G " m ÿ j"1 α j xAx,
Claim 1. V Ă S. Moreover, if 0 P K, then 0 P S. Finally, S Ă BK Y t0u, and S has finite cardinality. Now, for δ ą 0, we define the set S δ of points in K at distance at most δ from S: S δ :" tx P K : distpx, Sq ď δu.

Since S is finite, there exists a sufficiently small δ 0 ą 0 such that for any δ ď δ 0 , the set S δ has M :" #S connected components, with any two of these connected components being separated by a distance of at least δ 0 . Our goal is to prove that for any i P rns, and for sufficiently large t, the particle z i ptq remains in one of these connected components. In the sequel, we fix i P rns.

Step 2. z i ptq must grow if it is not already in S δ . We now prove that there exists some γ " γpKq ą 0 (depending only on the geometry of K) such that for any δ P p0, δ 0 s, there exists T pδq ą 0 such that if t ě T pδq and z i ptq R S δ , then

d dt }Az i ptq} 2 ě γδ. (8.7) K S S δ Figure 9
. An example configuration of the sets S and S δ in R 2 . The set S consists of all green nodes along the boundary of BK, while S δ is the union of all yellow "hemispheres". The latter are pairwise disjoint and are the connected components of S δ , which we denote by C k , for k P rM s.

To this end, we observe that

1 2 d dt }Az i ptq} 2 " xA 9 z i ptq, Az i ptqy " n ÿ j"1 ˜exAziptq,Azjptqye 2t
ř n k"1 e xAziptq,Az k ptqye 2t ¸xApz j ptq ´zi ptqq, Az i ptqy

" n ÿ j"1 ˜eajptqe 2t
ř n k"1 e a k ptqe 2t ¸aj ptq loooooooooooooomoooooooooooooon :"bj ptq (8.8)

where we have set a j ptq :" xApz j ptq ´zi ptqq, Az i ptqy.

(To obtain the last equality in (8.8), divide both the numerator and the denominator by e }Aziptq} 2 e 2t .) The following holds.

Claim 2. There exists some constant γ 1 " γ 1 pKq ą 0 depending only on the geometry of K such that the following holds. Fix δ P p0, δ 0 s. There exists T 1 pδq ą 0 such that if t ě T 1 pδq and z i ptq R S δ , then there exists j P rns such that a j ptq ě γ 1 δ.

We postpone the proof of this claim to after that of the theorem. We seek to use this claim in obtaining a lower bound of b j ptq for any j, whenever δ is small enough and t is large enough. Since by Corollary 8.3, for any j P rns, t Þ Ñ z j ptq is uniformly bounded on r0, `8q, we gather that a j p¨q P L 8 p0, `8q. So, we may set κ :" max jPrns sup tě0 |a j ptq|.

Let t ě 0 be fixed. We define Bptq :" tj P rns : a j ptq ě 0u.

We pick an index j 0 ptq maximizing a j ptq, namely j 0 ptq P argmax jPrns a j ptq.

Observe that j 0 ptq P Bptq since a j0ptq ptq ě a i ptq " 0. Clearly b j ptq ě 0 for all j P Bptq. (8.9)

In fact, we also have b j0ptq ptq ě a j0ptq ptq n .

(8.10)

Now suppose that j R Bptq; since a j ptq ě ´κ, and

e aj ptqe 2t n ÿ k"1 e a k ptqe 2t ď 1 n ÿ k"1 e a k ptqe 2t ď e ´aj 0 ptq e 2t ,
we gather that b j ptq ě ´κe ´aj 0 ptq ptqe 2t for all j P rnszBptq.

(8.11)

Using (8.9), (8.10) and (8.11) in (8.8), we find

1 2 d dt }Az i ptq} 2 ⩾ a j0ptq ptq n ´κne ´aj 0 ptq ptqe 2t .
The above inequality along with Claim 2 lead us to deduce that there exists T pδq ą 0 (possibly larger than T 1 pδq) such that (8.7) holds whenever t ⩾ T pδq, with γ " γ 1 2n , as desired.

Step 3. z i ptq cannot circulate indefinitely between the connected components of S δ . Since z i P L 8 pr0, `8qq by Corollary 8.3, from (8.1) we gather that 9 z i P L 8 pr0, `8qq as well. And since any two connected components of S δ0 are separated by a distance at least δ 0 , we deduce that it takes a time at least

T 0 :" δ 0 } 9 z i } L 8 pr0,`8qq
for z i to go from one connected component of S δ0 to another one. Fix δ P p0, δ 0 q such that δ ă

T 0 γδ 0 8R}A} op , (8.12)
where R :" max jPrns }z j } L 8 pr0,`8qq . Denote by

C 1 , . . . , C M
the connected components of S δ , each of which being the intersection of K with a Euclidean ball of radius δ centered at some point of S (see Fig. 9). For any k P rM s,

sup xP C k }Ax} 2 ´inf xP C k }Ax} 2 ď 4R}A} op δ. (8.13)
We introduce the following binary relation on rM s:

k ą ℓ ðñ inf xP C k }Ax} 2 ą sup xP C ℓ }Ax} 2 ,
which is transitive. The underlying idea is the following: if t is sufficiently large, and if z i starts from some connected component C ℓ , then the only connected components C k which z i is able to visit later on are those for which k ą ℓ. This travel of z i has to stop after some time since rM s is finite, ą is transitive, and for any ℓ, the relation ℓ ą ℓ does not hold. Let T " T pδq be as in Step 2. Suppose that t 2 ą t 1 ě T and k 1 , k 2 P rM s are distinct and such that z i pt 1 q P C k1 , z i pt 2 q P C k2 and z i ptq R S δ for any t P pt 1 , t 2 q. Per Step 2 (more specifically, (8.7)), }Az i pt 2 q} 2 ě }Az i pt 1 q} 2 `T0 γδ 0 .

Therefore using (8.13) twice and since δ is chosen as in (8.12), we gather that

inf xP C k 2 }Ax} 2 ě }Az i pt 2 q} 2 ´4R}A} op δ ě }Az i pt 1 q} 2 `T0 γδ 0 ´4R}A} op δ ě inf xP C k 1 }Ax} 2 `T0 γδ 0 ´4R}A} op δ ě sup xP C k 1 }Ax} 2 `T0 γδ 0 ´8R}A} op δ ą sup xP C k 1 }Ax} 2 . (8.14)
Whence k 2 ą k 1 . We therefore deduce that there exist some T 1 ě T and k P rM s such that z i ptq R S δ z C k for any t ě T 1 .

Step 4. Conclusion. To conclude, it remains to be shown that z i ptq stays in C k for t large enough. For this, in addition to (8.12), we impose

δ 1 4 ă γT 0 8R}A} op δ 0 . (8.15)
For r ą 0, we denote by C r k the intersection of K with the closed Euclidean ball of radius δ r having the same center as C k . In particular, C 1 k " C k . If, after time T 1 , z i travels from C k to the complement of C 1 4 k , it spends a time at least pδ

1 4 ´δ 1 2 q } 9 z i } L 8 pr0,`8qq in C 1 4 k z C 1 2 k . Per Step 2 (used with δ 1 2 ), }Az i } 2 has to increase by at least γδ 1 2 ´δ 1 4 ´δ} 9 z i } L 8 pr0,`8qq ě γδ 3 4 2} 9 z i } L 8 pr0,`8qq ą 4R}A} op δ (8.16)
during this travel (the last inequality in (8.16) stems from (8.15)). This implies that z i cannot reenter C k after having reached the boundary of C k , due to (8.13). Thus z i ptq R S δ for any sufficiently large t, which is impossible due to Step 2 and the uniform boundedness of t Þ Ñ }Az i ptq}. Hence, for sufficiently large t, z i ptq P C 1 4 k . Since δ may be chosen arbitrarily small, this concludes the proof of Theorem 8.1. □ 8.1.3. Proving Claims 1 and 2. We now address the proofs of the two claims which were instrumental in what precedes (along with a sketch of the proof of V Ă S, as implied).

Proof of Claim 1. The fact that 0 P S if 0 P K is immediate. We now show that S is finite and S Ă BK Y t0u. Let w P Szt0u. As w " m ÿ j"1 α j v j for some α j ⩾ 0 with ř m j"1 α j " 1, and since (8.6) holds by definition, it follows that α j " 0 for any j not attaining the maximum in (8.6). Let I Ă rms denote the set of all such indices. We have w " ÿ jPI α j v j with }Aw} 2 " xAw, Av j y for any j P I. Whence w is the orthogonal projection onto spantv j u jPI with respect to xA¨, A¨y. This yields S Ă BK. Moreover, since for each subset I Ă rms there exists a unique such projection w, S is finite. □ Sketch of proof of V Ă S. We notice that for any i P rns and for t large enough, we have

9 z i ptq " n ÿ j"1 ˜ee 2t xAziptq,Azj ptqy ř n k"1 e e 2t
where M i ptq is the subset of rns containing all indices j such that max kPrns xAz i ptq, Az k ptqy ´xAz i ptq, Az j ptqy ď e ´t (all other terms in the sum (8.17) are negligible). Due to the convergence of convptz i ptqu iPrns q toward K, we also know that for t large enough, ' all the points z i ptq are contained in a small neighborhood of K, ' near any element of V, there exists some particle z i ptq. Assume, for the sake of contradiction, that there exists a vertex v j P V such that v j R S. Set C :" convptv i u iPrmsztju q. In particular, distpv j , Cq ą 0 since v j is a vertex of K. If I Ă rns denotes the set of indices i such that z i ptq lies near v j , then M i ptq X I " H for any i P I, since v j R S. For i P I, using (8.18), we find that distpz i ptq, Cq decays as t Ñ `8 as long as i R M i ptq-indeed, (8.18) implies that z i ptq is attracted by C. This implies that v j R convptz k pt 1 qu kPrns q for t 1 large enough. This is a contradiction since K Ă convptz k ptqu kPrns q for any t ě 0 according to Proposition 8.2. □ Proof of Claim 2. To simplify the notation, we only prove Claim 2 when A " I d . Assume that t ě 0 and that z i ptq R S δ .

First case. Firstly, we prove the claim in the case where z i ptq R S δ0 . For this, we notice that the function

f : x Þ Ñ max jPrns xv j , xy ´}x} 2
is continuous, and by definition of S, f is strictly positive on the compact set KzIntpS δ0 q (the complement in K of the interior of S δ0 ). Hence f pxq ě c 1 in this set for some constant c 1 ą 0. Setting

K ε :" tx P R d : distpx, Kq ď εu,
by continuity we find that f pxq ě c 1 {2 for x P K ε zIntpS δ0 q and for sufficiently small ε ą 0 (fixed in the sequel). For sufficiently large t, we have z i ptq P K ε for any i P rns, thus max jPrns xz i ptq, z j ptq ´zi ptqy ě max jPrms xz i ptq, v j ´zi ptqy ě c 1 2 .

Since c 1 is independent of δ, we deduce the claim in this case (notice that it suffices to prove the claim for sufficiently small δ).

Second case. Secondly, we prove the claim when z i ptq P S δ0 zS δ . The proof mainly relies on the following result:

Lemma 8.4. For any w P S, there exists β ą 0 such that if6 x P K X Bpw, δ 0 q, then max jPrms xx, v j ´xy ě β}x ´w}.

(8.19)

We postpone the proof of Lemma 8.4 and show how to conclude the proof of Claim 2. Fix δ ą 0. We set η :" βδ 6R where R :" max jPrns }z j } L 8 pRq .

Since convptz j ptqu jPrns q converges to K as t Ñ `8, there exists T pδq ą 0 such that for any t ě T pδq, if z i ptq P Bpw, δ 0 qzBpw, δq for some w P S, then }z i ptq ´x} ď η for some x P K X pBpw, δ 0 qzBpw, δqq. Therefore, using Lemma 8.4, To summarize, we have found that for any δ ą 0 there exists T pδq ą 0 such that if t ě T pδq and z i ptq P S δ0 zS δ , then We can exclude having xx, v j ´xy " 0 for all j P rms, as this would necessarily imply that }x} 2 " 2 ř m j"1 α j xx, v j ´xy " 0. We deduce from (8.21) that max jPrms xx, v j ´xy ą 0 for any x P Kzt0u. Hence, it is sufficient to prove (8.19) for }x} small enough. We notice that for any x P Kzt0u written as above,

}x} 2 " m ÿ j"1 α j xv j , xy.
Hence x Þ Ñ max jPrms xv j , xy is positive for x P Kzt0u. Since this function is continuous and homogeneous in x, we deduce the existence of β ą 0 such that max jPrms xv j , xy ě 2β}x} for any x P K. For x P K with }x} sufficiently small, we obtain (8.19). We now assume that w P Szt0u. We set I w :" ␣ j P rns : }w} 2 " xw, v j y ( and A :" span `␣v j ´w : j P I w (˘, which is orthogonal to w. We also introduce R :" `Rw ' A ˘K, and we denote by π R the orthogonal projection on R. We claim that there exists some ρ ą 0 such that for any j P rms, we have xw ´vj , wy ě ρ}π R v j }.

This follows from the observation that rms is finite, and that }π R v j } ą 0 implies xw ´vj , wy ą 0. Therefore, for any x P K, writing x as a convex combination of the vertices, namely x " ř m j"1 α j v j , we find that

ρ}π R x} ď m ÿ j"1 α j }π R v j } ď m ÿ j"1
α j xw ´vj , wy " xw ´x, wy. (8.22)

Fix x P K X Bpw, δ 0 q. We write x " w `δ1 u with 0 ď δ 1 ď δ 0 and }u} " 1. Notice that b ď 0 by combining (8. 22) and (8.23). Since }u} " 1 and using (8. 22) we have 1 " b 2 `}a} 2 `}r} 2 ď }a} 2 `κb 2 ď κp}a} 2 `b2 q where κ :" 1`ρ ´2}w} 4 . We deduce that either }a} 2 ě p2κq ´1 or ´b " |b| ě p2κq ´1 2 . Plugging this knowledge in (8.24) and using the fact that }w} ą 0, we finally deduce the existence of an α ą 0 (independent of δ ą 0 and x P K X Bpw, δ 0 q) such that max jPrms xx, v j ´xy ě αδ 1 ´δ12 " α}x ´w} ´}x ´w} 2 .

This proves (8.19) when }x ´w} ď α{2.

It thus remains to show that (8.19) holds for all x P K X pBpw, δ 0 qzBpw, α 2 qq. To this end, we notice that x Þ Ñ max jPrms xx, v j ´xy is continuous in the connected set K X pBpw, δ 0 qzBpw, α 2 qq, non-negative according to (8.5), and it is nowhere 0 (by definition of S). Therefore, it is strictly positive, and denote by α 1 ą 0 some lower bound. Then for x P K X pBpw, δ 0 qzBpw, α 2 qq, we have

max jPrms xx, v j ´xy ě α 1 ě α 1 δ 0 }x ´w}.
This concludes the proof of Lemma 8.4. □ 8.2. A cluster at the origin. We complete this section by addressing the case V " ´Id , for which the convergence of the solutions of (1.1) is the simplest, since a unique cluster forms at the origin. We also suppose that Q J K " I d : in other words, we consider the dynamics 9

x i ptq " ´n ÿ j"1 ˆexxiptq,xjptqy ř n k"1 e xxiptq,x k ptqy ˙xj ptq, t P r0, `8q, (8.25) with a prescribed initial condition tx i p0qu iPrns Ă R d .

Theorem 8.5 (Convergence toward the origin). Suppose V " ´Id and Q J K " I d . Then, for any initial sequence of tokens tx i p0qu iPrns Ă R d , and for any i P rns, we have }x i ptq} Ñ 0 as t Ñ `8.

Remark 8.6. In the setting of Theorem 8.5, the self-attention matrix P ptq defined in (1.2) converges, as t Ñ `8, to the n ˆn matrix with all entries equal to 1{n.

8.2.1. Proof of Theorem 8.5. We begin by showing that for any i P rns, the solution to (8.25) is uniformly bounded for all t ą 0. In the sequel, we fix an initial configuration tx i p0qu iPrns Ă R d .

Lemma 8.7. The trajectories of (8.25) are uniformly bounded in time-namely, there exists R ą 0 (depending solely on n and the initial configuration) such that the solution x i p¨q to (8.25) satisfies }x i ptq} ⩽ R for any i P rns and t ⩾ 0.

Proof of Lemma 8.7. We fix i P rns. For t ě 0, we denote by D i ptq the set of points x k ptq such that xx i ptq, x k ptqy ě 0. We also set This shows that }x i ptq} ď maxt}x i p0q}, ? 2nu for any t ě 0, which concludes the proof.

S
□ By virtue of Lemma 7.1, we are able to characterize the stationary configurations for the dynamics (8.25)-namely, the set of points px 1 , . . . , xn q P pR d q n satisfying n ÿ j"1 ˆexxi,xjy ř n k"1 e xxi,x k y ˙x j " 0 for all i P rns.

Lemma 8.8. The only stationary configuration for the dynamics (8.25) is x1 " . . . " xn " 0.

Proof. Assume that px 1 , . . . , xn q P pR d q n is a stationary configuration for the dynamics (8.25). We consider f : R d Ñ R defined as

f : x Þ Ñ log ˜n ÿ j"1 e xx,xj y ¸.
Per Lemma 7.1, f is convex, whence f pxq ě f px i q `x∇f px i q, x ´x i y for x P R d and i P rns. Since ∇f px i q " 0 for any i P rns, we gather that f pxq ě f px i q, whence xi is a global minimizer of f for any i P rns. By convexity, f is constant on convptx i u iPrns q. Since f is analytic on the affine space E spanned by the points xi , i P rns, it is then constant on E as well. Now assume that not all of the points xi are equal, and pick an index i 0 P rns such that xi0 is not equal to the projection of the origin onto E. Then there exists some j 0 P rns such that xx i0 ´x j0 , xi0 y ‰ 0. For any s P R, we set P s :" xj0 `spx i0 ´x j0 q P E, and we notice that f pP s q ě xP s , xi0 y, where the lower bound tends to `8 either when s Ñ `8 or when s Ñ ´8. This contradicts the fact that f is constant on E. We conclude that the xi are all equal for i P rns. The only value they can then take is necessarily 0. □ 9.1. Some monotonicity properties and bounds. To start, we present some general facts that are prove useful in all subsequent sub-cases.

Lemma 9.1. Suppose k P rds is such that λ k ě 0. Then t Þ Ñ max jPrns φ k pz j ptqq is a non-increasing and bounded function, and t Þ Ñ min jPrns φ k pz j ptqq is a nondecreasing and bounded function. In particular, t Þ Ñ φ k pz i ptqq is uniformly bounded as a function on r0, `8q for any i P rns.

Proof. For any k P rds and any t ě 0, set α k ptq " min jPrns φ k pz j ptqq, β k ptq " max jPrns φ k pz j ptqq.

Let i P rns be an index such that α k ptq " φ k pz i ptqq. Then we have

d dt φ k pz i ptqq " n ÿ j"1 P ij ptqφ k pV pz j ptq ´zi ptqqq " λ k n ÿ j"1
P ij ptqpφ k pz j ptqq ´φk pz i ptqqq ě 0

where the last inequality stems from the fact that λ k ě 0 and the choice of index i. This proves that α k p¨q is non-decreasing, as desired. Arguing similarly, one finds that β k p¨q is non-increasing. As a consequence, α k p0q ď α k ptq ď β k ptq ď β k p0q for any t ě 0, which shows that α k p¨q and β k p¨q are bounded. □ Corollary 9.2. If V only has real non-negative eigenvalues, then z i p¨q P L 8 pr0, `8qq.

Lemma 9.3. Fix k P rds and i P rns. Then there exists a constant C ą 0 such that ˇˇφ k `etV z i ptq ˘ˇď Ce |λ k |t holds for all t ⩾ 0.

Proof. We naturally make use of the equation for x i ptq :" e tV z i ptq. Fix t ⩾ 0. We have

d dt |φ k px i ptqq| 2 " 2 ¨Re ˆφk px i ptqq d dt φ k px i ptqq " 2 ¨Re ˜n ÿ j"1 P ij ptqφ k pV x j ptqqφ k px i ptqq " 2 ¨Re ˜n ÿ j"1 P ij ptqλ k φ k px j ptqqφ k px i ptqq ḑ 2|λ k | max jPrns |φ k px j ptqq| 2 .
Choosing i P rns running over the set of indices such that |φ k px i ptqq| is maximal, we obtain d dt max

jPrns |φ k px j ptqq| 2 ď 2|λ k | max jPrns |φ k px j ptqq| 2 .
We conclude the proof by applying Grönwall's lemma. □ 9.2. Proof of Theorem 4.2. We now prove Theorem 4.2. We again recall that λ 1 is simple and positive, and the eigenvalues of V are ordered in decreasing order of modulus:

λ 1 ą |λ 2 | ě . . . ě |λ d |.
Proof of Theorem 4.2. We look to prove that for any i P rns, the component of z i ptq along the principal eigenvector φ 1 , i.e. φ 1 pz i ptqq, converges as t Ñ `8. We also show that there exists a set of at most 3 real numbers (depending on the initial datum pz 1 p0q, . . . , z n p0qq) such that for any i P rns the limit of φ 1 pz i ptqq belongs to this set. Theorem 4.2 directly follows from these facts. Let i P rns be fixed. Recall from Lemma 9.1 that φ 1 pz i ptqq is uniformly bounded for any t P r0, `8q. We set a :" lim (Note that by Lemma 9.1, a ě min jPrns φ 1 pz j p0qq and b ď max jPrns φ 1 pz j p0qq.) For c P t0, a, bu, we define the candidate limiting hyperplanes for z i ptq:

H c :" tx P R d : φ 1 pxq " cu.
We show that z i ptq converges either to H 0 , to H a or to H b . If a " b " 0, then according to (9.1) all particles converge to H 0 and there is nothing left to prove. We now distinguish two scenarios:

(i) either for any ε ą 0, |φ 1 pz i ptqq| ď ε for t large enough-in which case, we deduce that z i ptq converges toward H 0 as t Ñ `8-, (ii) or |φ 1 pz i pt k qq| ą ε 0 for some ε 0 ą 0 and for some sequence of positive times tt k u `8 k"1 with t k Ñ `8.

Since case (i) is straightforward, let us handle case (ii). Without loss of generality, we can extract a subsequence of times (which we do not relabel, for simplicity of notation) along which

φ 1 pz i pt k qq ą ε 0 . (9.2)
Let ε P p0, ε 0 s be fixed and to be chosen later. We set w j ptq :" @ Qe tV z i ptq, Ke tV z j ptq D ,

so that 1 λ 1 d dt φ 1 pz i ptqq " n ÿ j"1
e wj ptq ř n k"1 e w k ptq pφ 1 pz j ptqq ´φ1 pz i ptqqq .

(9.3)

We look to obtain a lower bound for the right-hand side in the above identity. Let us use the shorthand c kℓ :" xQφ k , Kφ ℓ y for k, ℓ P rds. By assumption, c 11 ą 0. We have φ k pe tV z i ptqq " e tλ k φ k pz i ptqq and the following spectral expansion holds:

e tV z i ptq " d ÿ k"1 e tλ k φ k pz i ptqqφ k .
Using this fact, as well as Lemma 9.3, we gather that ˇˇwjptq ´c11 e 2λ1t φ 1 pz i ptqqφ 1 pz j ptqq ˇˇ" ˇˇˇˇˇÿ pk,ℓq‰p1,1q c kℓ φ k pe tV z i ptqqφ l `etV z j ptq ˘ˇˇˇˇď ÿ pk,ℓq‰p1,1q

|c kℓ | ˇˇφ k `etV z i ptq ˘ˇˇφ l `etV z j ptq ˘ď C 2 }Q J K} op ÿ pk,ℓq‰p1,1q e p|λ k |`|λ ℓ |qt ď C 2 }Q J K} op pd ´1q 2 loooooooooooomoooooooooooon ":C 1 e pλ1`|λ2|qt (9.4)
holds for all t ě 0 and j P rns. Now since λ 1 ą 0, Lemma 9.1 implies that for any t ě 0 there exists an index i 0 ptq P rns such that φ 1 pz i0ptq ptqq ě b. (9.5)

With j 0 ptq P argmax jPrns w j ptq, using (9.4) and (9.5) we see that w j0ptq ptq ě w i0ptq ptq ě c 11 φ 1 pz i ptqqbe 2λ1t ´C1 e pλ1`|λ2|qt . (9.6)

Now for any t within the sequence tt k u `8 k"1 , combining the first inequality in (9.6) with the fact that c 11 ą 0, (9.2) and (9.4), we deduce that φ 1 pz j0ptq ptqq ´φ1 pz i0ptq ptqq ě ´2C 1 c 11 ε e ´pλ1´|λ2|qt . (9.7)

As λ 1 ą |λ 2 |, for t large enough, we find that we can lower bound the above expression by ´ε 4 . We now define the set of indices N ptq :" tj P rns : φ 1 pz i ptqq ´φ1 pz j ptqq ě 0u.

Take t within the sequence tt k u `8 k"1 such that φ 1 pz i ptqq ď b ´ε and large enough so that (9.7) is lower bounded by ´ε 4 (if such a t does not exist, we immediately conclude that φ 1 pz i ptqq Ñ b as t Ñ `8). Using (9.5) and the subsequent derivations, we deduce that φ 1 pz j0ptq ptqq ´φ1 pz i ptqq ě 3ε 4 , and since φ 1 pz j ptqq ´φ1 pz i ptqq ě 0 for j R N ptq, we expand in (9.3) to get This shows the existence of a larger time horizon T 1 ą T such that φ 1 pz i ptqq ě b ´ε whenever t ě T 1 . And since ε can be taken arbitrarily small, we deduce that φ 1 pz i ptqq converges toward b, namely that z i ptq converges toward H b , as t Ñ `8.

1 λ 1 d dt φ 1 pz i ptqq ě e w j 0
Arguing in the same way as above, and assuming without loss of generality that a ă 0, we may find that all indices i P rns for which φ 1 pz i pt k qq ď ´ε0 for some ε 0 ą 0 and some sequence t k Ñ `8, the particle z i ptq converges toward H a as t Ñ `8. This concludes the proof. □ 9.3. Remarks.

Remark 9.4. Theorem 4.2 establishes the convergence of φ 1 pz i ptqq for any i P rns as t Ñ `8, but does not preclude the fact that }z i ptq} may diverge toward `8 (along the hyperplane) as t Ñ `8. This is indeed expected (and observed numericallysee Fig. 6) when V has some negative eigenvalues. We also note that when all the eigenvalues of V are non-negative, Corollary 9.2 shows that all the z i ptq remain bounded.

Remark 9.5 (The case where V is not diagonalizable). If V is not assumed to be diagonalizable, Lemma 9.3 (or, at least the proof thereof ) requires some modifications. Let δ :" λ 1 ´|λ 2 | ą 0. Let ε ą 0 be fixed and to be chosen later. We decompose V in Jordan blocks, and we consider

C d " m à k"1 F k , (9.11)
where F k is the span of the Jordan chain corresponding to the k-th Jordan block. By a slight abuse of notation (solely for the purpose of this remark), we denote by λ k the eigenvalue associated to the k-th Jordan block. We recall that we can choose a basis pφ k,1 , . . . , φ k,j k q of each F k in a way that V |F k reads in this basis as ř n k"1 e a k ptqe 2λ 1 t `rk ptq ¸aj ptq looooooooooooooooooomooooooooooooooooooon ":bj ptq .

(10.1)

We now make use of the following adaptation of Claim 2.

Claim 3. There exists some constant γ 1 " γ 1 pKq ą 0 depending only on the geometry of K such that the following holds. Fix δ P p0, δ 0 s. There exists T " T pδq ą 0 such that if t ě T and z i ptq R S δ ˆG, then there exists j P rns such that a j ptq ě γ 1 δ.

Compared to

Step 2 in the proof of Theorem 8.1, we now have to estimate the coefficients r j ptq. To this end, setting y j ptq :" Ae tV z j ptq for j P rns, we notice that r j ptq " P 1 ptq `P2 ptq `P3 ptq where P 1 ptq " xπ F py i ptqq, π G py j ptq ´yi ptqqy, P 2 ptq " xπ G py i ptqq, π F py j ptq ´yi ptqqy, P 3 ptq " xπ G py i ptqq, π G py j ptq ´yi ptqqy.

By virtue of Lemma 9.3 we have |π F py j ptqq| ď Ce λ1t and |π G py j ptqq| ď Ce t|λ2| for any t ě 0 (or Ce t|λ2|`ε if V | G is not diagonalizable-see Remark 9.5), hence |r j ptq| ď Ce tpλ1`|λ2|q .

(10.2) Since π F pz j ptqq is uniformly bounded in t P r0, `8q for any j P rns due to Corollary 8.3, we get a j p¨q P L 8 p0, `8q. So, we may set κ :" max jPrns sup tě0 |a j ptq|.

Let t ě 0. We define Bptq :" ␣ j P rns : a j ptqe 2λ1t `rj ptq ě 0 ( .

Let j 0 ptq P argmax jPrns pa j ptqe 2λ1t `rj ptqq. Note that j 0 ptq P Bptq since a j0 ptqe 2λ1t `rj0 ptq ě a i ptqe 2λ1t `ri ptq " 0.

https://github.com/borjanG/2023-transformers. We now present some experiments which motivate some conjectures and claims made in what precedes. 11.2. Eigenvalues of ALBERT's value matrices. In Figure 10 we illustrate the eigenvalues of the value matrices V h for a couple of heads h in a pre-trained ALBERT model. We focus on ALBERT-xlarge-v2 available online at https://huggingface.co/albert-xlarge-v2. This version uses 16 heads, with sequences of length n " 256 and tokens of dimension d " 128. While not all value matrices V h per head h P r16s satisfy the assumptions made in Section 4, we illustrate the eigenvalues of a couple of them which do. and pQ14, K14q (the inner products evaluated along the eigenvector of norm 1 equal 1.3060 and 0.6719 respectively). In other words, the triples pQ h , K h , V h q corresponding to heads h " 5 and h " 14 in ALBERT satisfy all the assumptions made in the statement of Theorem 4.2. 11.3. Experiments related to Theorem 2.1. We begin with the setup of Theorem 2.1, which we recall was proven to hold in the case d " 1. Herein we present a couple of examples (Figures 11 and12) which elucidate the role that d and n appear to play in this fact.

Notably, as seen in Fig. 4, we believe that the conclusion of Theorem 2.1 could plausibly be extended to any d ą 1, assuming V ą 0. 11.4. Illustrating Theorem 4.2 in R 3 . To precisely illustrate the appearance of at most three hyperplanes in the setting of Theorem 4.2, we gave an example in R 2 . We expand on this and provide a couple of toy examples in R 3 for the purpose of visualization (we recall that these are toy models, as Transformers in practice are high-dimensional), and namely focus in both examples on the case where the two latter eigenvalues are complex. In Fig. 14, we see the effect of having eigenvalues with a negative real part, and the complementary case is illustrated in Fig. 13. . We consider n " 25, Q " K " I d , and V a random matrix with positive entries and eigenvalues t1, 0.1 `0.08i, 1 ´0.08iu. The pair of complex eigenvalues have a positive real part. We not only see convergence to one of two hyperplanes determined by the direction φ1 " p0.38, 0.8, 0.47q, but in fact, the particles appear to collapse to two points. In other words, the "hyperplanes" are of codimension 3, which is in line with Conjecture 4.3. The pair of complex eigenvalues have a negative real part, which entails the rotation of the particles. We see that the particles rotate within a couple of 2-dimensional hyperplanes determined by φ1 " p´0.3, ´0.8, ´0.45q, as implied by Theorem 4.2. For each h P rHs (corresponding to a different head ), the weight matrices Q h , K h , V h are constant. Proofs regarding clustering or convergence of the self-attention matrix for such dynamics is an open problem. Preliminary numerical investigations seem to indicate that interesting clustering phenomena also occur in this context. A characterization or properties of optimal weights by invoking the optimal control correspondence in the spirit of [START_REF] Weinan | A proposal on machine learning via dynamical systems[END_REF] is also an interesting avenue for future research.

We hereby list a couple of additional numerical experiments suggesting generalizations of our results, which we leave as open problems.

12.1. Beyond Q J K ą 0 in Theorems 3.1 and 5.2. As seen throughout all the presented proofs, assumptions on the value matrix V are significantly more rigid than assumptions on the matrices Q and K. For instance, should the eigenvalue λ with the largest real part of V be negative, all rescaled tokens will diverge to infinity. Should λ be complex, we do not expect any clustering to occur (for the

Figure 1 .

 1 Figure 1. For V " I3 tokens cluster toward the vertices of a convex polytope (Theorem 3.1).

  1.3.4. Clustering in interacting particle systems. The transformer dynamics (1.1) have a strong connection to the vast literature on nonlinear systems arising in the modeling of opinion dynamics and flocking phenomena. In addition to the classical Kuramoto model describing synchronization/clustering of oscillators [Kur75, ABV `05], the model which is most similar to (1.1) is the Krause model[START_REF] Krause | A discrete nonlinear and non-autonomous model of consensus[END_REF]

Figure 3 .Figure 4 .

 34 Figure 3. An illustration of the asymptotics of P ptq entailed by Theorem 2.1 for n " 40 tokens, with Q " K " 1 and V " 1. (See Section 11 for details on computing.) Increasing n has no effect on this behavior of P ptq-see Fig. 11.

Figure 5 .

 5 Figure 5. A toy example illustrating Theorem 3.1 with n " 40 tokens in R 3 . Here Q " K " I3. The tokens converge to one of the vertices (leaders) of the limiting convex polytope.

Figure 6 .

 6 Figure6. Illustrating Theorem 4.2 with n " 40 tokens in R 2 . Here Q " K " I2, V is a random symmetric matrix with eigenvalues t1.35, ´0.07u, and φ1 " p0.76, 0.65q. The components of the tokens in the direction of φ1 (orange arrow) cluster over time. (See Figures13-14for examples in R 3 .) We also observe that tokens typically cluster toward only two hyperplanes-a third one (passing through the origin) may appear for non-generic initial sequences. The hyperplanes are perpendicular to φ1 since V is diagonalizable.

  Conjecture 4.3: low-dimensional case. Negative limits for clustered coordinates (b) Conjecture 4.3: high-dimensional case.

Figure 7 .

 7 Figure7. (a) n " 40, d " 3 and Q " K " I3 with V a random matrix with eigenvalues t1.96, ´0.22, 0.25u. The k " 2 positive eigenvalues of V generate attraction between the tokens and even convergence in the corresponding eigenspaces-this explains the codimension k statement. The negative eigenvalue generates a repulsive effect between the tokens, and we see a divergence along two lines (note the different scales between the four figures). (b) n " 256, d " 128, with pQ, K, V q fixed random matrices and V symmetric. For each coordinate j corresponding to a positive eigenvalue, the variance of the set tφ j pziptqq : i P rnsu (shaded area) tends to 0 with t, while the mean (solid lines) converges to one among two real scalars: one positive (top figure), one negative (bottom) figure. Coordinates corresponding to negative eigenvalues diverge (Fig.15).

Figure 8 .

 8 Figure8. Illustrating Theorem 5.2 with n " 40 tokens in R 3 . As before, Q " K " I d , and we take V " diagp1, 1, ´1 2 q. A convex polytope K emerges before time 5, toward which two coordinates of the tokens cluster, and persists throughout the evolution, while the tokens diverge along the coordinate corresponding to the eigenvalue ´1 2 (note the different scales between the four figures).

t

  2n c 1 e t (7.11)

and we write 9 x n ptq ě e xnptq 2 x n ptq n ÿ k" 1 e xnptqx k ptq `ÿ jPN ptq e xj ptqxnptq x j ptq n ÿ k" 1 e xnptqx k ptq ě ε n `1 e ε 2 ÿ jPN ptqe

 11 εxj ptq x j ptq. (7.12)

e xnptqxj ptq x j ptq n ÿ j"1 e xnptqxj ptq ě e xnptq 2 x n ptq ´pn ´1qδ e xnptq 2

 2 `n ´1.

  Av j y ď max jPrms xAx, Av j y. (8.5) Let S Ă K denote the set of points w P K such that }Aw} 2 " max jPrms xAw, Av j y. (8.6)

max jPrms xz i ptq, v j ´zi ptqy ě max jPrms xx, v j ´xy

max jPrms xz i ptq, v j ´zi ptqy ě βα

  ptq, z j ptq ´zi ptqy ě max jPrms xz i ptq, v j ´zi ptqy concludes the proof of Claim 2 in this second case. □ Proof of Lemma 8.4. Let us first address the case where w " 0. Writing any x P Kzt0u as a convex combination of the vertices: x " ř m j"1 α j v j , we find 0 " j xx, v j ´xy. (8.21)

Figure 10 .

 10 Figure10. The eigenvalues of V5 and V14 in the pre-trained ALBERT satisfy the eigenvalue assumption made in Definition 4.1. Furthermore, the second assumption made in Definition 4.1 is satisfied by pQ5, K5q and pQ14, K14q (the inner products evaluated along the eigenvector of norm 1 equal 1.3060 and 0.6719 respectively). In other words, the triples pQ h , K h , V h q corresponding to heads h " 5 and h " 14 in ALBERT satisfy all the assumptions made in the statement of Theorem 4.2.

Figure 11 .Figure 12 .

 1112 Figure11. We expand on Fig.3-for the same setup, consider n " 100. The sequence length n does not appear to influence the rank of P ptq, which is expected since the rank of P corresponds to the number of leaders.

11. 5 .

 5 Complementing Figure 7. In Figure 7, we illustrate the appearance of clustering in high-dimension (the ALBERT setup: n " 256 and d " 128) for generic random matrices pQ, K, V q. The value matrix V in question has 65 positive eigenvalues, and we show the conjectured convergence of the 65 coordinates along the corresponding eigenvectors to one of possibly 3 (generically 2) real scalars. In Figure 15, we complement this illustration by showing the possible oscillatory and divergent behavior of the remaining coordinates.

  Figure13. We consider n " 25, Q " K " I d , and V a random matrix with positive entries and eigenvalues t1, 0.1 `0.08i, 1 ´0.08iu. The pair of complex eigenvalues have a positive real part. We not only see convergence to one of two hyperplanes determined by the direction φ1 " p0.38, 0.8, 0.47q, but in fact, the particles appear to collapse to two points. In other words, the "hyperplanes" are of codimension 3, which is in line with Conjecture 4.3.

Figure 14 .

 14 Figure14. We consider n " Q K " d , and V a random matrix with positive entries and eigenvalues t1, ´0.05 `0.25i, ´0.05 ´0.25iu. The pair of complex eigenvalues have a negative real part, which entails the rotation of the particles. We see that the particles rotate within a couple of 2-dimensional hyperplanes determined by φ1 " p´0.3, ´0.8, ´0.45q, as implied by Theorem 4.2.

Figure 15 .

 15 Figure15. We complement Figure7and plot the variance of the set tφ j pziptqq : i P rnsu of all coordinates j corresponding to negative eigenvalues of V . We also show the mean along tokens of a couple of coordinates (white lines). Coordinates diverge rapidly to ˘8 over time t; y-axis is in log scale.

  Rq}∇ x Gpx, yq}}V y} dµpyq K} op }V } op R 2 . We thus end up with the task of bounding from above the absolute values of

	ż
		Gpx, yq dµpyq
	Bp0,Rq
		ż	ż
		Gpx, yq}y} dµpyq	}∇ x Gpx, yq} dµpyq
	`}V } op	Bp0,Rq ż	Bp0,Rq ż
		Gpx, yq dµpyq	Gpx, yq dµpyq
		Bp0,Rq	Bp0,Rq
	ď 2}Q J We finally prove (6.5). Using the fact that
	ż
	R ż	ż
	Gpx, yqp dν ´dµqpyq	and
	R d	R

d Gpx, yq dµpyq ⩾ ˆinf px,yqPBp0,Rq 2 Gpx, yq ˙µpBp0, Rqq, -with an analogous bound for ν-, we see that it suffices to bound ˇˇˇż R d Gpx, yqV y dµpyq ż R d Gpx, yq dνpyq ´żR d Gpx, yqV y dνpyq ż R d Gpx, yq dµpyq ˇˇf rom above. We rewrite this difference by making µ ´ν appear artificially, and we then use the triangle inequality along with the fact that both ş R d Gpx, yqV y dµpyq and ş R d Gpx, yq dµpyq are bounded from above (by e }Q J K}opR 2 maxp1, }V } op Rq). d Gpx, yqV yp dν ´dµqpyq. (6.6) For the first integral, from the Kantorovich-Rubinstein duality we deduce ˇˇˇż R d Gpx, yqp dν ´dµqpyq ˇˇˇď }Gpx, ¨q} C 0,1 pBp0,Rqq W 1 pµ, νq. (6.7) We now recall the following inequality relating Wasserstein distances of different orders: for any p ě 1 and any bounded set B, for all Radon measures µ, ν supported in B, W 1 pµ, νq ď W p pµ, νq ď diampBq 1´1 p W 1 pµ, νq 1{p . (6.8)

  If x n ptq ě 0 for some t ě 0, then

	9 x n ptq "	n ÿ j"1	ˆexnptqpxjptq´xnptqq ř n k"1 e xnptqpx k ptq´xnptqq ˙xj ptq	(7.6)
	ě	x n ptq 1 `pn ´1qe ´cxnptq	`ÿ tjPrns : xj ptqă0u	e xnptqpxj ptq´xnptqq x j ptq	(7.7)
	ě	x n ptq 1 `pn ´1qe ´cxnptq	´n e ´xnptq 2 x n ptq	(7.8)
	ě	x n ptq n	´n e ´xnptq 2 x n ptq	.	(7.9)

  Let T ą t denote the infimum of the times for which one of the points z i ptq lies in H. Now fix s P rt, T q, and denote by M psq the set of indices i P rns such that distpz i psq, Hq is minimal. For h Ñ 0, we have

	Moreover, for any i P M psq, one has
	d dt	distpz i psq, Hq	(8.4) " x 9 z i psq, ny "
						writing 9 xptq " x 9 xptq, nyn `vptq where vptq P H
	we have d dt pproj H pxptqqq " vptq, whence
					d dt	distpxptq, Hq " x 9 xptq, ny.	(8.4)
	αps `hq " min iPM psq	distpz i ps `hq, Hq
		" min iPM psq	ˆdistpz i psq, Hq	dt `h d	distpz i psq, Hq `ophq	"
		αpsq	`h ˆmin iPM psq	d dt	distpz i psq, Hq ˙`ophq.
	Consequently,
			dα dt	psq " min iPM psq	d dt	distpz i psq, Hq.

n ÿ j"1

  xAziptq,Az k ptqy ¸pz j ptq ´zi ptqq e e 2t xAziptq,Az k ptqy ¸pz j ptq ´zi ptqq,

		(8.17)
	ÿ	˜ee 2t xAziptq,Azj ptqy
	«	ř n
	jPMiptq	k"1

  i ptq :" ÿ kPDiptq e xxiptq,x k ptqy xx i ptq, x k ptqy, Now since 1 ´x ď e ´x whence e x ď 1 `ex x, we find that R i ptq ď n `Si ptq. Consequently, if we assume that }x i ptq} 2 ě 2n then S i ptq ě 2n, and therefore

	and						n
				R i ptq :"	ÿ	e xxiptq,x k ptqy .
							k"1
	Since 1 `x ď e x whence e ´xx ď 1, we deduce that
	1 2	d dt	}x i ptq} 2 "	´n ÿ k"1	e xxiptq,x k ptqy xx i ptq, x k ptqy R i ptq	ď	´Si ptq R i ptq `n	.
			1 2	d dt	}x i ptq} 2 ď	´Si ptq n `Si ptq `n	ď ´1.

  Given our choice of t, we have φ 1 pz i ptqq 2 ´bφ 1 pz i ptqq ď ´εpb ´εq, so, we conclude from the inequality just above that exp ´´c 11 εpb ´εqe 2λ1t `2C 1 e pλ1`|λ2|qt ¯. (9.10) Since λ 1 ą |λ 2 |, it follows from (9.10) that there exists T ą 0 such that for any t within the sequence tt k u `8 k"1 for which t ě T and φ 1 pz i ptqq P rε, b ´εs, there holds

	Using the monotonicity properties from Lemma 9.1, as well as (9.9) in (9.8), we
	obtain
		1 λ 1	d dt	φ 1 pz i ptqq ě	3ε 4n	´C0 n	exp ´c11 φ 1 pz i ptqq 2 e 2λ1t `C1 e pλ1`|λ2|qt ´c11 φ 1 pz i ptqqbe 2λ1t ´C1 e pλ1`|λ2|qt	ēxp ¯.
	1 λ 1	d dt	φ 1 pz i ptqq ě	3ε 4n	´C0 n d dt	φ 1 pz i ptqq ě	λ 1 ε 2n	.
					ptq ptq k"1 e w k ptq ř n	3ε 4	`ÿ jPN ptq	e wj ptq ř n k"1 e w k ptq pφ 1 pz j ptqq ´φ1 pz i ptqqq .
									(9.8)
	On another hand, for j P N ptq, we may use (9.4) to find
					w (9.9)
	We set
						C 0 :" max

j ptq ď c 11 φ 1 pz i ptqq 2 e 2λ1t `C1 e pλ1`|λ2|qt . jPrns φ 1 pz j p0qq ´min jPrns φ 1 pz j p0qq.

  F pz i ptqq R S δ , then d dt }π F pAz i ptqq} 2 ě γδ.Proof ofStep 2'. We set a j ptq :" xπ F pAz i ptqq, π F pApz j ptq ´zi ptqqy and r j ptq :" @ Ae tV z i ptq, Ae tV pz j ptq ´zi ptqq D ´aj ptqe 2λ1t .˜exAe tV ziptq,Ae tV zj ptqy ř n k"1 e xAe tV ziptq,Ae tV z k ptqy ¸xπ F pApz j ptq ´zi ptqqq, π F pAz i ptqqy " ˜exAe tV ziptq,Ae tV pzj ptq´ziptqqy ř n k"1 e xAe tV ziptq,Ae tV pz k ptq´ziptqqy ¸xπ F pApz j ptq ´zi ptqqq, π F pAz i ptqqy "

	We now proceed in proving this statement.
		We find
	1 2	d dt	}π F pAz i ptqq} 2 " xπ F pA 9 z i ptqq, π F pAz i ptqqy
			n
			ÿ
			"
			j"1
			n
			ÿ
			j"1
							7
			» λ k ε		fi
			-----	. . .	. . . . . . ε	ffi ffi fl ffi ffi	.	(9.12)
					λ k

7

Recall that Jordan blocks are commonly written with a `1 in the superdiagonal. This can be replaced by any non-zero complex scalar as done here-see [HJ12, Chapter 3, Corollary 3.1.21]. π n ÿ j"1 ˜eajptqe 2λ 1 t `rj ptq

Note that the case V " ´Id may appear equally natural. For such a choice of V , we show

which can be seen as a mean-field limit, and is sometimes also referred to as a Vlasov equation.

In other words we "freeze" the vector field X on each interval of the form rℓτ k , pℓ `1qτ k q, and during this time interval, we follow the flow generated by this vector field starting from µ k pℓτ k q.

This radius always exists, since µ k ptq is compactly supported.

Here, Bpy, rq denotes the closed ball with center y P R d and radius r ą 0.

Acknowledgments. We thank Pierre Ablin, Léonard Boussioux, Enric Boix Adsera, Gabriel Peyré, Yair Shenfeld and Emmanuel Trélat for helpful discussions. C.L. was supported by the Simons Foundation Grant 601948, DJ. P.R. is supported by NSF grants IIS-1838071, DMS-2022448, and CCF-2106377. Y.P. is supported in part by the MIT-IBM Watson AI Lab.

Lemma 8.9. The trajectories of (8.25) satisfy ż `8 0 } 9 x i ptq} 2 dt ă `8 for any i P rns.

Proof. The function Lptqq, which concludes the proof. □

We are now able to conclude the proof of Theorem 8.5.

Proof of Theorem 8.5. We set Xptq :" px 1 ptq, . . . , x n ptqq P pR d q n . If Xptq does not converge to 0, the compactness provided by Lemma 8.7 implies that there is a sequence tt k u `8 k"1 with t k Ñ `8, and X ˚" px 1 , . . . , x nq P pR d q n zt0u, such that Xpt k q Ñ X ˚as k Ñ `8. To conclude the proof, it suffices to show that X ˚is a stationary configuration of the dynamics: this directly leads to a contradiction per Lemma 8.8. Therefore, assume that X ˚is not a stationary configuration of the dynamics. We denote by X ˚ptq " px 1 ptq, . . . , x nptqq the solution of (8.25) with initial condition X ˚. Then, there exists i P rns such that 9 x i p0q ‰ 0. We set ε " } 9

x i p0q}. We select T 0 ą 0 (possibly small) such that } 9 x i ptq} ě ε{2 for t P r0, T 0 s. It follows from (6.9) (which is verified according to Corollary 6.6) that for any δ ą 0 there exists k 0 P N such that }Xpt k `tq´X ˚ptq} ď δ for any t P r0, T 0 s and any k ě k 0 . By (6.5) (which is verified according to Corollary 6.6), we obtain that } 9

x i pt k `tq ´9 x 0 i ptq} ď Cδ for t P r0, T 0 s and any k ě k 0 . Choosing δ ą 0 sufficiently small, we obtain that } 9

x i pt k `tq} ě ε{4 for t P r0, T 0 s and any k ě k 0 . This contradicts Lemma 8.9. □

Proof of Theorem 4.2

To ensure clarity, we present the proof of Theorem 4.2 under the assumption that V is diagonalizable. However, this assumption is not necessary. In Remark 9.5, we explain how the proof can be modified to accommodate for non-diagonalizable V .

Let us therefore assume that V is diagonalizable. Let pφ 1 , . . . , φ d q be an orthonormal basis of eigenvectors associated to eigenvalues pλ 1 , . . . , λ d q, ordered in a decreasing manner with respect to their modulus: |λ 1 | ě . . . ě |λ d |. (Starting from this point and throughout, we use the symbol λ exclusively to denote the eigenvalues of V .) Except for λ 1 P R, all the other eigenvalues (and eigenvectors) may be complex. We denote by pφ 1 , . . . , φ d q the dual basis of pφ 1 , . . . , φ d q.

We observe that if ε is chosen sufficiently small (depending only on δ), Lemma 9.3 may be replaced by the following estimate in each F k : DC ą 0, @t ě 0, @i P rns,

Here, π F k denotes the orthogonal projection onto F k . To prove estimate (9.13), we follow the proof of Lemma 9.3, with d dt }π

The key observation is that combining (9.11) and (9.12) we obtain

provided ε is chosen sufficiently small. Then (9.13) follows as in Lemma 9.3. With (9.11) at hand, the proof of Theorem 4.2 carries through, under the impactless modification that Ce pλ1`|λ2|`δqt replaces (9.4) (and subsequent estimates are modified in the same way).

Proof of Theorem 5.2

In this section, we establish the proof for Theorem 5.2. Since the proof is essentially a combination of the proofs of Theorems 4.2 and 8.1, we may occasionally skip certain details and refer to the proofs of these two results. As done throughout this work, we set A :" pQ J Kq 1 2 . We denote by π F : R d Ñ F the projection onto F parallel to G, and by π G : R d Ñ G the projection onto Gparallel to F. The set π F pconvptz i ptqu iPrns qq is a convex subset of F which is non-increasing with respect to t (the proof of this fact is identical to that of Proposition 8.2). It therefore converges toward some convex polytope K as t Ñ `8.

Fix i P rns. We have

˜exAe tV ziptq,Ae tV zj ptqy ř n k"1 e xAe tV ziptq,Ae tV z k ptqy ¸πF pV pz j ptq ´zi ptqqq " n ÿ j"1 ˜exAe tV ziptq,Ae tV pzj ptq´ziptqqy ř n k"1 e xAe tV ziptq,Ae tV pz k ptq´ziptqqy ¸πF pV pz j ptq ´zi ptqqq.

From this point on, we follow the proof of Theorem 8.1, and we solely highlight the changes compared to the original proof. Roughly speaking, this new proof amounts to adding projections π F at several places. We denote by S Ă F the set of points w P K such that

The fact that S Ă BK and that S has finite cardinality is proved precisely as Claim 1 (in the proof of Theorem 8.1), simply by replacing all occurrences of A¨by π F pA¨q.

Once again, S δ denotes the set of all points in K at distance ď δ to some point of S.

Step 2 in the proof of Theorem 8.1 (i.e., (8.7)) is replaced by the following statement:

Step 2': There exists a constant γ " γpKq ą 0 (depending only on the geometry of K) such that for any δ P p0, δ 0 s, there exists T " T pδq ą 0 such that if t ě T and We notice the following three properties: ' For j " j 0 ptq, we have b j0ptq ptq ě a j 0 ptq ptq n (recall the definition of b j in (10.1));

' for any j P Bptqztj 0 u, we have b j ptq ě 0; ' for any j R Bptq, we have b j ptq ě ´κ exp ´´a j0 ptqe 2λ1t `Ce pλ1`|λ2|qt ¯.

Indeed, using the fact that j P Bptq and (10.2), we find exp `aj ptqe 2λ1t `rj ptq n ÿ k"1 exp `ak ptqe 2λ1t `rk ptq ˘ď

Making use of these properties in (10.1) yields the desired lower bound-indeed, if t is sufficiently large and z i ptq R S δ ˆG, we have tj P rns : a j ptq ě γ 1 δu ‰ H according to Claim 3, and so we deduce that 1 2

Taking t possibly larger (and depending on δ), we obtain the result of Step 2'. □

Steps 3 and 4 in the proof of Theorem 8.1 are essentially unchanged-we replace all the occurrences of }A ¨} by }π F pA¨q} (for instance in (8.13) and (8.14)). Although }Az i ptq} may not be uniformly bounded in t, it is important to note that }π F pAz i ptqq} is uniformly bounded. Similarly, while 9 z i ptq R L 8 pr0, `8qq, we do have } d dt π F pz i p¨qq} L 8 pr0,`8qq ă `8. The sets S δ , C k and C r k are replaced by S δ ˆG, C k ˆG and C r k ˆG respectively. The conclusion is that }π F pAz i ptqq} 2 has to increase by at least

As in the proof of Theorem 8.1 this implies that for any i P rns there exists s P S such that z i ptq remains at distance at most δ away from tsu ˆG. This being true for any δ ą 0, we obtain the desired result.

Numerical experiments

11.1. Setup. Unless indicated otherwise, all figures presented in this paper were generated by discretizing the underlying dynamics (either (1.1) or (3.1)) using a fourth order Runge-Kutta scheme with a step size of 0.1. All points in the initial sequence were drawn independently from the uniform distribution over the hypercube r´5, 5s d . Random matrices (e.g., Q, K, V ) have entries drawn independently from the uniform distribution on r´1, 1s. Codes and animated plots of all examples may be found online at rescaled tokens). Yet, none of the conclusions of Theorems 3.1 or 5.2 seem to change for generic choices of Q J K. This is illustrated in Figures 16 and17 respectively. 12.2. Beyond pure self-attention: adding a feed-forward layer. Practical implementations of the Transformer architecture combine the self-attention mechanism with a feed-forward neural network. While extending the mathematical analysis from this paper to such a broader setting would be challenging, we can offer some numerical insights into the expected outcomes. The feed-forward neural network which can be adjoined to the Transformer dynamics in one of two ways. The first way consists in running the pure self-attention dynamics up to time t ď T (or equivalently, for OpT q layers), and then applying a pure feed-forward neural network to the concatenated vector of clustered features at time T . This amounts to seeing the feed-forward network as a map from R nd to R m (for some m ⩾ 1), which can be studied independently with existing theory. Here, V is paranormal, while Q J K violates the PSD assumption-it is a random matrix (with entries drawn from the uniform distribution on r´1, 1s). Nonetheless, the clustering pattern entailed by Theorem 5.2 persists.

The second way consists in using both the self-attention and feed-forward mechanisms in parallel at every layer t. In this case, clustering in the exact sense of Theorems 3.1 and Theorems 5.2 would be difficult to anticipate since the weights of the feed-forward network play the role of a value matrix V (as they can be absorbed within V ), and the conclusions of these theorems strongly depend on the identity-like structure.

In Figure 18, we focus on the second of the above-discussed examples, and illustrate a possible generalization of Theorem 4.2 to this setup. For simplicity, we focus on a 2-layer neural network: we apply a component-wise nonlinear activation function σ (either the ReLU or tanh) to the self-attention dynamics, and then multiply by a weight matrix W P R dˆd . Namely, we consider

˜exQe tV ziptq,Ke tV zj ptqy ř n k"1 e xQe tV ziptq,Ke tV z k ptqy ¸pz j ptq ´zi ptqq ¸(12.1) for i P rns and t ě 0. A bias vector b P R d (whether inside or outside the activation function) can also be included to allow for translations. The clustering property appears to persist, the pattern depending on the weight matrix W and on the activation function σ. We leave this problem open to further investigation. Middle: σ " tanh with W " I d . Bottom: σ " ReLU with W being a random matrix. In the first row, we see that the particles first evolve as to reach the upper right quadrant pRą0q d (due to the ReLU). Once they reach it, every particle eventually follows one of three hyperplanes determined by the spectrum of V and the projection onto pRą0q d . In the other two cases, all particles appear to collapse to 0.