{'fraction_non_alphanumeric': 0.05938697318007663, 'fraction_numerical': 0.013601532567049808, 'mean_word_length': 4.123527762198542, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Regularity of Attention

Attention is a powerful component of modern neural networks across a wide variety of domains. In this paper, we seek to quantify the regularity (i.e. the amount of smoothness) of the attention operation. To accomplish this goal, we propose a new mathematical framework that uses measure theory and integral operators to model attention. We show that this framework is consistent with the usual definition, and that it captures the essential properties of attention. Then we use this framework to prove that, on compact domains, the attention operation is Lipschitz continuous and provide an estimate of its Lipschitz constant. Additionally, by focusing on a specific type of attention, we extend these Lipschitz continuity results to non-compact domains. We also discuss the effects regularity can have on NLP models, and applications to invertible and infinitely-deep networks.


Introduction
Attention (Bahdanau et al., 2014;Vaswani et al., 2017) has recently joined the multi-layer perceptron, convolution, and recurrent neural network cell as a fundamental building block of modern neural networks. However, much is still not well understood about the mathematical properties of attention; in this paper, we study the question of regularity. In particular, we seek to understand how "close" the outputs of the attention operation are in terms of the closeness of the inputs and the parameters of the attention block. This problem is important for various reasons. Firstly, regularity is a basic property of a function with important implications for tasks such as feature learning; Lipschitz regularity in particular plays an important role, see e.g. Mallat (2016). Secondly, repeated composition of a function magnifies its regularity (or lack thereof) (Goodfellow et al., 2016, Chapter 10.7); since attention is extensively used in very deep architectures, understanding the regularity of this essential building block can help us better understand the training and stability of these models. Finally, having a precise theory allows us to make testable predictions about experiments (possibly to generate improvements) and also post hoc analysis of experimental results to better understand why a given behaviour was observed.
Because of some special properties of attention -namely self-interaction and the ability to process variable length inputs -special care must be taken to model attention and obtain a robust theory. For example, it is not clear a priori how to measure the closeness of two inputs to attention that have different numbers of vectors. In this paper, we address these issues by formulating attention in terms of measure theory and integral operators, and then use this framework to study its regularity in terms of Lipschtiz continuity.
We also investigate the implications of regularity on a number of concrete scenarios. We study how regularity can help certain applications by providing robustness to the learned representations but hurt others when the regularity of the model does not match the regularity of the task. We also study how regularity impacts the properties of self-attention networks such as their invertibility and the existence of infinite-depth limits.
The paper is organized as follows. We first introduce preliminaries in Section 3. In Section 4, we describe attention using measure theory. We then obtain quantitative Lipschitz continuity estimates for self-attention in Section 5. We apply these results to some concrete problems in Section 6.

Related Work
As noted by Smola and Zhang (2019), the original notion of attention appears in statistics in the form of the Watson-Nadaraya estimator (Watson, 1964;Nadaraya, 1964) which implements a datadependent regression model. The term "attention" and the modern "query-key-value" formulation comes from Bahdanau et al. (2014) who use attention for sequence alignment in a recurrent neural translation model. A similar setup was used in Graves et al. (2014) for differentiable, content-based addressing of a memory array. In Sukhbaatar et al. (2015) and Seo et al. (2016), attention is used for question answering, machine reading comprehension, and language modelling. The extremely successful "Transformer" architecture was introduced in Vaswani et al. (2017) and demonstrated that one could build powerful neural networks using attention as the main component. This led to important developments in language modelling (Devlin et al., 2018;Radford et al., 2018), graph modelling (Veličković et al., 2017), image modelling (Parmar et al., 2018), and set modelling . Recently, Baker et al. (2019) used attention in the policy architecture of a multi-agent reinforcement learning problem.
Concurrent to our work, there has been a recent flurry of activity in the study of the properties of attention-based networks from an empirical and theoretical perspective. As discussed in Section 6, Kim et al. (2020) studies the Lipschitz constant of self-attention as a map from R d×N → R d×N . Other works studying various theoretical aspects of attention (not necessarily regularity) include Katharopoulos et al. (2020); Bhattamishra et al. (2020); Hron et al. (2020); Levine et al. (2020).
We were mathematically inspired by Del Moral (2004) who studied self-interacting "Feynman-Kac models" using semigroup techniques (including contractions for nonlinear operators on measures). An interacting particle interpretation of attention is studied in Lu et al. (2019) using tools from dynamical systems theory.

Attention
The fundamental definition of attention is due to Bahdanau et al. (2014), which we provide below with some additional terminology for the various components that we will study.
Definition 1 (Attention, Bahdanau et al. (2014) a collection of corresponding values, and q ∈ R dq a query. Also, let a : R dq × R d k → R be a measurable similarity function. Then attention is the mapping where softmatch a (q, K) is a probability distribution over the elements of K defined as softmatch a (q, K) i := exp(a(q, k i )) N j=1 exp(a(q, k j )) . (1) While Attention(•, K, V ) is defined point-wise for a given query, it is almost always used to process a set of queries Q = {q 1 , . . . , q M } ⊂ R dq in parallel. Thus, we will usually write Attention(Q, K, V ) := {Attention(q i , K, V )} M i=1 . Also, while |K| = |V | = N , in general M does not have to equal N . When K = V = Q, we call the following mapping self-attention: We are primarily interested in self-attention as it can be composed to arbitrary depth, making it a key building block of many neural network architectures.

Markov Kernels
In the sequel, (E, E) denotes a subset of R d endowed with its Borel σ-algebra, and P(E) the space of probability measures on E. We use the following notation for expectations w.r.t. µ ∈ P(E): for a real-valued measurable function f , we denote µ(f ) :=´f (x)µ(dx) when it exists.
Our framework will heavily rely on linear transformations of measures modelled by Markov kernels; see e.g. Del Moral (2004) for an account that is consistent with our notation.
A Markov kernel M defines a linear operator P(E) → P(E) by µM (dy) :=´µ(dx)M (x, dy). It also defines a linear operator on measurable functions by M (f )(x) :=´f (y)M (x, dy). Markov kernels M, N can be composed by integration, M N (x, dz) :=´M (x, dy)N (y, dz).

Modelling Attention
In this section, we model attention (Bahdanau et al., 2014) andthe Transformer (Vaswani et al., 2017) in measure-theoretic language. Our construction casts the action of attention on collection of vectors as a nonlinear Markov transport on P(E) by reformulating existing linear algebra and point-wise operations in-terms of operators on P(E).

Basic Model of Attention
The fundamental parts of Attention from Definition 1 are: the softmatch a operation, the key-value correspondence, and the value-averaging w.r.t. the softmatch distribution. We will treat each of these in turn.
Softmatch and Botzmann-Gibbs Transformations. At the core of the softmatch function, and indeed attention itself, are the interactions between queries and keys. These interactions are a specific case of a nonlinear measure transformation, the Boltzman-Gibbs transformation.
To implement the softmatch a operation, we will need a function G : E × E → R * + taking the form G(x, y) = exp(a(x, y)), where a is a similarity function as in Definition 1. We call G an interaction potential.
Definition 4 (Softmatch Kernel) For an interaction potential G, we call the softmatch kernel the family of Markov kernels .
In other words, for a given x ∈ E and ν ∈ P(E), the softmatch kernel Ψ G (ν)(x, dy) is the Boltzmann-Gibbs transformation associated to G(x, •). To see how Ψ G can be used to model the softmatch operation, we introduce some simple but useful constructions from measure theory.
Empirical measure mapping. Denote by P δ (E) := {δ x | x ∈ E} the subset of Dirac measures in P(E). There is a natural bijection between E and P δ (E) defined by x ↔ δ x which will be the primary entry point for measure theory in our model of attention. We can associate to any set of vectors X = {x 1 , . . . , x N } ⊆ E ⊆ R d a measure in P(E) via the empirical measure mapping: In what follows, we will often use X and {δ x 1 , . . . , δ x N } interchangeably to represent the individual vectors and m(X) to represent the joint configuration of X. We will see below that m(X) is a very natural object to represent this joint configuration and how it behaves with attention. Now consider a "query" representation δ q , "key" representations K = {δ k 1 , . . . , δ k N }, and the empirical measure m(K). The softmatch kernel models the interaction between q and K using the left-action of the Markov kernels Ψ G (m(K)) on the Dirac measure δ q induced by integration: Furthermore, given a set of queries Q = {δ q 1 , . . . , δ q M }, we can leverage the linearity of integration to model the interaction between the two sets of representations Q and K using the same principle: This new measure represents the joint configuration of the set of queries Q after they have interacted with the keys K through the potential G and the associated Boltzmann-Gibbs transformation. It is a weighted sum of particle measures, and will allow us to model the softmatch operation from Eq. (1).
Key-Value Relationships. To generalize the relationship between keys and values, we now introduce the lookup kernel.
Definition 5 (Lookup Kernel) Assume that the keys and values come from (Borel) measurable subsets of R d k , R dv resp. A lookup kernel is a Markov kernel, L : R d k × B(R dv ) → [0, 1], also denoted L(k, dv), that maps keys to distributions on values. When the mapping from keys to values is a deterministic function ℓ, we have L(k, dv) = δ ℓ(k) (dv).
For self-attention, ℓ(x) = x is the natural choice of the deterministic lookup function, and for the Transformer (see App. A), the natural choice is ℓ(k) = W V k. In general, to study regularity, we assume there exists some well-behaved function ℓ : R d k → R dv that realizes the correspondence k i ↔ v i -this holds for most realistic implementations of attention such as those above.

Remark 6
The most general case of attention, when there is no prescribed correspondence between k i and v i , could be realized by a function such as but this not in general regular without additional assumptions.
Averaging and Measure Projections. In the remainder of this paper, we will make the following technical assumption, which ensures that the operations we describe are well-defined.
The final element of our construction is the averaging w.r.t. the set of values. Denote by Π : P(E) → P δ (E) the measure projection of a probability measure µ ∈ P(E) onto the subset of Dirac measures P δ (E) defined by whenever µ exists (e.g. when µ has finite first moments). We claim (to be justified in a moment) that the averaging w.r.t. values is accomplished by the measure projection Π described in Eq. (2).
The Attention Kernel. Combining these, we obtain a model for attention, the attention kernel.
Definition 7 (Attention Kernel) The attention kernel, denoted A, is the composition of the measure projection Π, the softmatch kernel and the lookup kernel, defined for q ∈ E and µ ∈ P(E) as: where the softmatch and lookup kernels are composed by integration as described after Definition 2 and Π is applied to the resulting measure (which is defined per q). Our first result is that this attention kernel is consistent with attention from Definition 1, for suitable choices of G and L.
Proposition 8 Let G(x, y) = exp(a(x, y)), L(k, dv) = δ ℓ(k) (dv), and Q, K, V be as in the definition of attention. Then, using the left action of kernels on measures, the mapping: implements attention as in Definition 1.
Proof Using the remarks from earlier, for q ∈ R dq , we have: Using the (linear) left-action of this kernel on δ qt , we then obtain: Plugging in the definition of G and using the usual bijection δ x ↔ x concludes the proof.
Attention as a System of Interacting Particles. Let us step back and understand the attention kernel A from a higher level. Consider self-attention: we have effectively factorized the original, linear-algebraic self-attention operation into a series of measure transformations: More importantly, we have a closed-form expression for the evolution of the joint configuration Since interaction with the joint configuration is central to attention, having a framework that describes its evolution will be vital to further analysis. Moreover, as we noted earlier, self-attention can be composed arbitrarily. Indeed, let Q 0 := Q and consider the evolution of a the set of "particles" Our framework shows that self-attention networks are actually simulating deterministic interacting particle systems for a finite number of time steps corresponding to the number of layers H. The representations one obtains are the states of the system after H steps of the dynamics.
Remark 9 Interestingly, the particle interpretation above is studied in Lu et al. (2019) using tools from dynamical systems theory. The authors recognize the Transformer (with the residual connection) as a coupled system of particles evolving under diffusion-convection ODE dynamics, and study this system using the a numerical scheme for the underlying ODE.
Remark 10 (Connection with Expectation) Let us also point out a connection with Bayesian statistics: when G(q, •) = p(q|•) is a likelihood function, ν → Ψ G(q,•) (ν) is the mapping which takes a prior distribution ν(dk) over keys and returns a posterior distribution P (dk|q). Moreover, assuming that q → k → v forms a Markov chain, Ψ G L(q, dv) models the conditional probability of v|q. Finally, the measure projection operator effectively reduces this to a measure concentrated on a single point, E[v|q], which is consistent with the existing interpretation of attention.

Extension to the Transformer
We now sketch how to extend the measure-theoretic model of self-attention described in the previous section to the popular Transformer encoder architecture (Vaswani et al., 2017). It is a straightforward application of the techniques above. We only describe here how our framework can model a single head Transformer 1 , and refer the interested reader to Appendix A for the extension to a full multi-headed Transformer. We seek to model 1. We only consider the encoder part of the transformer, since it uses self-attention. Our framework is fully compatible with the cross-attention from the transformer decoder (Vaswani et al., 2017), see Section 6.1 where X = {x 1 , . . . , x N } ⊂ R d is the input data, SelfAttention(•) is the scaled dot-product attention (Vaswani et al., 2017) and FFN(•) represents a feedforward neural network. We set a(x, y) = x T y/ √ d and let where W Q , W K , W V are matrices in R d×d . These correspond to the various matrix operations performed by the Transformer. We let f : E → E be the FFN in (3) and define the FFN kernel as F(x, dy) = δ f (x) (dy). Using the attention kernel A from Definition 7, we define T := AF, and show in the proposition below that T implements the self-attention transformer (proof in App. A).

Regularity of Attention
In this section, we consider self-attention as a non-linear map from P(E) to P(E) through A : µ → µA µ . To derive a Lipschitz contraction estimate, we must first metrize P(E).
Background. We will work with the Wasserstein metric on P(E). Let P 1 (E) be the set of probability measures with finite 1st moment. The 1-Wasserstein distance between µ, ν ∈ P 1 (E) is W 1 is a metric on P 1 (E) which turns the pair W 1 := (P 1 (E), W 1 ) into a complete, separable metric space (Villani, 2008, Ch 6).

Lipschitz Contractions: Bounded Case
We now derive a Lipschitz contraction estimate for the map µ → µA µ on the metric space (P 1 (E), W 1 ) via an inequality of the form: for some constant τ (A) to be determined. In this Section, we make the additional assumption.
Assumption 2 E ⊂ R d is compact.
We will estimate the Wasserstein contraction coefficient defined below.
Definition 12 (Wasserstein Contraction Coefficient) Let Φ : P 1 (E) → P 1 (E) be a (possibly nonlinear) mapping. We define the Wasserstein contraction coefficient by Remark 13 This definition is a natural extension of two concepts from applied probability: it is the generalization of the total variation contraction coefficient studied in Del Moral (2004) for nonlinear Markov operators to the 1-Wasserstein distance; it is also the extension of the generalized ergodic coefficient from Rudolf et al. (2018) to nonlinear Markov operators.
Also, for f : Theorem 14 Let E ⊂ R d be compact and convex, and let A be the attention kernel from Defini- is Lipschitz continuous as a mapping from R d → R d with the Euclidean distance, and moreover Proof Using elements from the proof of Theorem 14 in Appendix B, we have:

Lipschitz Contractions: Unbounded Case
The results of Section 5.1 depend on the boundedness of the representation space E. While this is sufficient to provide rather general estimates on the Lipschitz coefficient for attention that are verified by reasonable choices for G and L, it is natural to question if it is necessary. As we will discuss below, the answer is affirmative, at least in full generality.
In concurrent work by Kim et al. (2020), the authors investigate Lipschitz constants for selfattention on X = {x 1 , . . . , x N } as a mapping from R d×N → R d×N without assuming E is bounded. They show that, for the case of G(x, y) = exp x, y on the whole of R d , attention is not Lipschitz by proving that the norm of the Jacobian is unbounded (Kim et al. (2020) Theorem 3.1). The authors then show that using instead the interaction potential G(x, y) = exp(− x − y 2 2 / √ d) leads to a Lipschitz bound independent of diam(E) (Kim et al. (2020) Theorem 3.2). They also provide empirical evidence that this potential function does not severely degrade performance.
We provide below an analysis of a similar Gaussian interaction potential G(x, y) = exp(− x − y 2 2 ) as in Kim et al. (2020) 2 for unbounded E = R d . We are able to use a set of tools and approach similar to those from Section 5.1 but exchange the boundedness assumption on E for exponential decay of G(x, y) and ∇G(x, y) as x − y 2 → ∞. The proofs are in Appendix C.
Theorem 16 Let E=R d and suppose 2 ) and Π be the usual projection onto P δ (R d ). Then for µ = m(X) and ν = m(Y ), Theorem 16 provides an alternate path to the Lipschitz constant of self-attention compared to methods based on computing Jacobians (Kim et al., 2020). In particular, Theorem 16 applies to sequences of tokens of various lengths and allows for studying the effect of perturbing a sequence by e.g. removing a given word, or negating a sentence, which is out of immediate reach for Jacobianbased techniques. Finally, we can recover a bound for sequences of equal lengths: Corollary 17 Applying Theorem 16 to the case of N = M gives: Optimality of Lipschitz Estimates. First, let us consider the O(diam(E)/ε(G)) dependence in Theorem 14 in the case of bounded E (recall ε(G) := inf x∈E G(x)). While in practice these values may lead to large bounds, we do not believe they indicate obvious inefficiencies in our technique. Indeed, we cannot simultaneously relax the finiteness of diam(E) and ε(G) in the general case: dotproduct attention is a non-pathological counterexample (Kim et al., 2020). We believe it is likely than one cannot relax diam(E) < ∞ in the general case either, but we will study this in future work. Second, for a trained attention network, diam(E) < ∞ and ε(G) > 0 are automatically satisfied, so these estimates can be used to study the very common use-case of pre-trained models. A potentially useful consequence of these estimates is an easy "knob" to control the regularity of an attention model by controlling diam(E) (e.g. by projecting on a ball of fixed radius).
Finally, the appearance of an additional factor of √ d is the cost we pay for using W 1 , which relies on the ℓ 1 metric in R d , to provide ℓ 2 -Lipschitz bounds. This is likely not optimal; it may be possible to derive a similar result with the 2-Wasserstein which would likely enjoy the good properties of the Wasserstein distance without the penalty of √ d (since x − y 2 = W 2 (δ x , δ y )) but it will not use the Lipschitz duality we have exploited in this paper which is specific to W 1 .

Applications of Regularity
In this section, we will apply the analysis developed above to discuss some consequences of regularity. Firstly, we will show that a common use of attention (called "cross attention") is also (Lipschitz) continuous w.r.t. the input keys. We then highlight cases where regularity either helps or hurts performance on various tasks. Finally, we discuss the implications of regularity on the invertibility of self-attention networks, and the case of infinitely deep, weight-tied self-attention networks.

Cross Attention is Continuous w.r.t. Keys
Although we have been primarily interested in the question of self-attention so far, the tools we have developed also apply to other uses of attention. One common example is cross-attention, i.e. when the keys and values are the same, but the queries can be different q, X → Attention(q, X, X). This is used in practice when one wants to construct a context-specific representation of q in the same "semantic space" as X (hence X provides the values). Most notably, this is used in in the seqence2sequence (or encoder-decoder) architecture (Sutskever et al., 2014), where X represents the encoded sequence and q represents the current element being decoded, see e.g. Bahdanau et al. (2014); Vaswani et al. (2017).
Our framework shows that the resulting representation is Lipschitz continuous w.r.t. the output semantic space X. Note that this result highlights the flexibility of our results: two input spaces X, Y need not even have the same length! Proposition 18 Suppose that q ∈ R dq X := {x 1 , . . . , x N } ⊂ R d k and Y := {y 1 , . . . , y N ′ } ⊂ R d k are sets of vectors for N, N ′ ∈ N, and suppose that the assumptions of Theorem 14 hold. Then Proof We can adapt an argument from the proof of Theorem 14. Firstly, for simplicity write µ := m(X), ν := m(Y ) and note that Then by Proposition 20 In the case that |X| = |Y | = N , we can obtain an explicit formula for W 1 (m(X), m(Y )) (see e.g. Bobkov and Ledoux (2014), Lemma 4.2): where x s ∈ X, y s ∈ Y and Σ(m) is the set of permutations on m elements.

Robustness and Perturbations
Robustness to noisy inputs. One effect of the smoothness of attention is that the representations it produces are "robust to errors" to a certain degree. For instance, in the encoder-decoder setup mentioned above, if the outputs of an encoder are incorrect or noisy, an attention-based decoder still has a chance of performing adequately. This robustness has been used recently in Anderson et al. (2020) to operate self-attention transformer models on reduced-size vocabularies by hashing, where the model must be robust to hash collisions of the larger original vocabulary. The authors of that paper compare this robustness to error correcting output codes (Berger, 1999;Dietterich and Bakiri, 1994). Our framework provides a potential mathematical basis for this phenomenon in transformers.
Negated Sentences. This robustness is not always desirable, however. Indeed, our regularity results may also explain some recent observations on the behavior of deep language models with respect to negation. Table 4 of Kassner and Schütze (2019) shows that negated sentences are often given identical predictions to the original ones: for instance, both "A beagle is a type of [MASK]" and "A beagle is not a type of [MASK]" get a prediction of "dog".
One hypothesis for why this occurs is a "regularity mismatch" between the input space and the output space of the model. On one hand, negation is a type of perturbation in "token space" that drastically changes the semantic content of the sentence, i.e. it is highly irregular. On the other hand, our analysis -specifically, Prop. 18 -suggests that the resulting embeddings will not change "too much" in response to this perturbation. If the embeddings are close with and without negation, i.e. the model is "too smooth" w.r.t. perturbations in token space, the scoring network (often a linear classifier) will not be able to distinguish between the resulting embeddings and the model will fail.
Our modelling could potentially be used to derive predictions of the distance between a selfattention networks' contextual embeddings as a function of the context (e.g. for sentences with and without a "not") to test this hypothesis. Moreover, it could even potentially be used to design better model components (e.g. input embedding spaces) that reduce this "regularity mismatch" for specific perturbations that are highly irregular. We leave that research direction to future work.

Invertible & Infinite Depth Transformers
Finally, let us briefly mention two important consequences of the Lipschitz regularity of attention: invertibility (also studied empirically in Kim et al. (2020)) and infinite-depth attention networks.
Invertibility. Firstly, as noted in Behrmann et al. (2019), a sufficient condition for invertibility of a residual network of the form F (x) = F L • · · · • F 1 (x) where each residual block F ℓ has the form is the Lipschitz condition g ℓ Lip < 1 for ℓ = 1, . . . , L. The self-attention Transformer from Vaswani et al. (2017) uses self-attention exactly this way, where g ℓ (X) = SelfAttention(X) (it also uses a feedforward residual block). Therefore, our results provide sufficient conditions for a deep self-attention transformer to be invertible. Note that this general conclusion was also used in Kim et al. (2020). Moreover, our analysis could be applied to the scaled dot product potential function (Vaswani et al., 2017) by enforcing that the input representations come from a bounded subset of R d . This is in contrast with the work of Kim et al. (2020), whose Lipschitz constants only apply to the Gaussian interaction potential.

Infinitely-Deep Attention Models.
In the opposite direction of invertibility, infinitely-deep models have recently been studied in the context of "deep equilibrium models" (Bai et al., 2019). The authors study representations defined as fixed points where f θ is an input-injected nonlinear function and H * = {h * 1 , . . . , h * N } is a collection of hidden representations for the inputs X = {x 1 , . . . , x N }. Here input-injected means f θ includes a (possibly parameterized) skip connection s θ from the inputs to the hidden representations of the form f θ (H; X) = g θ 1 (H + s θ 2 (X)).
Note that the Banach Fixed Point Theorem provides a sufficient condition for the existence of H * : the mapping H → f θ (H; X) has Lipschitz constant < 1.
In Bai et al. (2019), the authors note that the model in (4) includes the Universal Transformer model (Dehghani et al., 2018), albeit with the minor modification of including an "input injection" connection. In this situation, f θ is self-attention so we can apply our our theory to obtain sufficient conditions on the existence of H * from Theorem 14 or Theorem 16 depending on the type of attention used. We didn't find an existence result such as this in Bai et al. (2019).
In light of our results, we understand why the input injection is important: it produces a datadependent fixed point. If (4) had no the skip-connection (and no way to parameterize f θ in-terms of X), the fixed point H * would not depend on the inputs and therefore be of questionable usefulness.

Conclusion
In this paper, we have studied the regularity of attention. In particular, we have shown that attention is Lipschitz continuous under various assumptions, and provided estimates of the Lipschitz constant. To do so, we have introduced an alternate, but equivalent, modelling paradigm for attention based on measure theory and integral operators. We then assessed the impact of these regularity results on study practical applications of attention, including cross-attention; robustness and token-level perturbations in NLP; and sophisticated extensions to the transformer architecture.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks.
In Advances in neural information processing systems, pages 3104-3112, 2014.

Appendix A. The Transformer
In this section, we show how to extend the measure-theoretic model of self-attention described in the main text to the full Transformer encoder architecture (Vaswani et al., 2017) 3 . This is a straightforward application of the techniques from the main text. For our purpose, we work with the model where X = {x 1 , . . . , x N } ⊂ R d and FFN represents a feedforward neural network. To incorporate this into our formalism above, first set a(x, y) = x T y/ √ d. We can model a single head of the Transformer using the attention kernel from Definition 7 with: where W Q , W K , W V are matrices in R d ′ ×d where d ′ can possibly be a different dimension than d. To model multi-headed attention, we note that multi-headedness amounts to processing independent copies of the data X and combining them with concatenation and matrix multiplication. The "concat-and-matmult" operation can be written as , where we have multiplied by the scalar H, and introducing the mixture kernel where each h parameterizes its own collection of projection matrices and attention head A h , we can define the multi-headed attention attention kernel as Finally, letting f : E → E be the FFN in 5 and defining the FFN kernel as F(x, dy) = δ f (x) (dy), we see that T := MF implements the self-attention transformer as nonlinear measure transport.
Proof Given the discussion about standard attention, the only new element to be checked is the multi-headed attention kernel. Consider a fixed X, then 3. Technically, the Transformer also contains layer normalization and residual connections, which we do not treat here.
Hence considering a single x i , we see that The inner kernel is Finally, applying the mapping Π we get a measure that is concentrated on the point which concludes the proof.
Appendix B. Proofs From Section 5.1 Proposition 20 Suppose µ, ν ∈ P 1 (E) and G : E×E → R, G(x, y) ≥ ǫ(G) > 0 is an interaction potential s.t. G ∞,Lip < ∞ and G Lip,∞ < ∞. Then, ∀x, y ∈ E: Proof For the first inequality, let f be any 1-Lipschitz function, and x, y ∈ E. We have: Let us bound the first term: Let us now bound the second term: Using the fact that Ψ G(x,•) (µ)(f ) = Ψ G(y,•) (µ)(f ) for any constant functionf , we can subtract from f any constant without changing the value of This allows us to assume without loss of generality that f ∞ ≤ diam(E) (picking an arbitrary x ∈ E, we have ∀y ∈ E, |f (y) − f (x)| ≤ |y − x| f Lip ≤ diam(E)). Combining everything, we get: Taking the supremum over 1-Lipschitz functions f concludes the first part of the proof. Let us now prove the second inequality. Similarly, let f be any 1-Lipschitz function, and µ, ν two compactly supported distributions on (E, E). We use the notation G(z) := G(x, z) for this part because x is fixed. We have: Let us bound the first term: Let us now bound the second term: Using the same reasoning as above, we can assume without loss of generality that f ∞ ≤ diam(E), which gives: Taking the supremum over all 1-Lipschitz functions f concludes the proof.
Hence, by our earlier estimation techniques: which concludes the proof.
Theorem 14 Let E ⊂ R d be compact and convex, and let A be the attention kernel from Definition 7 with G an interaction potential s.t. G(x, y) ≥ ǫ(G) > 0, G Lip,∞ < ∞ and G ∞,Lip < ∞. Then the 1-Wasserstein contraction coefficient τ (A) of A considered as a mapping P(E) → P(E) via A : µ → µA µ satisfies . Let µ = ν ∈ P(E), we have: Let us start with the first term: where we used Lemma 23 for the second and third lines, and Propositions 20, 21 and 22 for the third and last. As for the second term, we have: where we also used Lemma 23 for the second and third lines, and Propositions 20, 21 and 22 for the third and last.

Appendix C. Proofs From Section 5.2
Lemma 24 For any f : R d → R, we have Proof Let x = y and L := sup x =y, x−y ≤1 For the reverse inequality, we split the segment [x, y] into the minimum number of chunks of lengths smaller than 1: x = z 1 → z 2 → · · · → z k = y (in particular, if x − y ≤ 1 then z 2 = y). Then which gives f Lip ≤ L so L = f Lip . Now if f Lip = ∞ but L < ∞, by applying the above argument we can obtain a contradiction. Finally, it suffices to note that the case where Lemma 25 For any n and (z 1 , · · · , z n ) ∈ R n + : Proof f is clearly bounded on R n + (z i e −z 2 i → 0 when z i → ∞). Let us now compute the partial derivatives of f . For a given z i : There is only one positive solution of 1 − 2z 2 i + 2z i f * = 0, meaning that f reaches its maximum when all its coordinates are equal. We thus only need to study: The change of variable y = ln n − x 2 gives g(y) = √ ln n−ye y 1+e y ≤ √ ln n−y 1+e −y with y ∈] − ∞, ln n]. On [0, ln n], we clearly have g(y) ≤ √ ln n. Let us consider y ∈] − ∞, 0]. We get g 2 (y) = ln n−y (1+e −y) 2 ≤ ln n−y e −2y ≤ ln n + 1 2e with since (2e) −1 is the maximum of of ze −2z on R + . This concludes the proof.
Proof We use the Kantorovich formulation of W 1 . Let f be a function with f Lip ≤ 1. Using the same kind of technique as in Section B, we can assume without loss of generality that f (y) = 0. For simplicity, we write G(x, •) = G x . We wish to upper-bound the quantity |Ψ Gx (µ)(f ) − Ψ Gy (ν)(f )|.
Because Ψ Gx and Ψ Gy are homonegeous in their measure argument, and for the sake of simplicity, we write µ = i δ x i ν = i δ y i (which is equivalent to simplifying by 1/N in e.g. the numerator and denominator of Ψ Gx ). This guarantees in particular that µ(G x ) ≥ 1 and ν(G y ) ≥ 1 (x and y are in supp (µ) and supp (ν) resp.) and equivalently that 1/µ(G x ) ≤ 1 and 1/ν(G y ) ≤ 1. Then: We start by bounding the second term of (9). We have: Here, δ x ⊗ µ denotes the product of the two measures on E × E. Since f (y) = 0, we see that f (z) ≤ f (y) + f Lip y − z 1 ≤ y − z 1 . This gives: where we applied Cauchy-Schwartz for the last inequality. Since y = y i for a given i, we are interested in the quantity gives an upper-bound of ln N + 1 2e . Let us now consider the first term of (9): To estimate Gf Lip we have Gf Lip = sup (x,w) =(y,z) |G(x, w)f (w) − G(y, z)f (z)| (x, w) − (y, z) 1 where additionally, we can assume that (x, w) − (y, z) ≤ 1 (see Lemma 24). We have: |G(x, w)f (w) − G(y, z)f (z)| = |G(x, w)f (w) − G(x, w)f (z) + G(x, w)f (z) − G(y, z)f (z)| ≤ |G(x, w)||f (w) − f (z)| + |f (z)||G(x, w) − G(y, z)|.
For the first term, we see that y)).
For the second term, we have |f (z)||G(x, w) − G(y, z)| ≤ y − z 1 |G(x, w) − G(y, z)| ≤ y − z 1 ∇G(t 1 , t 2 )) ∞ (x, w) − (y, z) 1 , for t 1 in the segment [x, y] and t 2 in the segment [w, z] (this follows directly from the mean value theorem, note that the gradient is taken with respect to both variables). We used f (y) = 0 and f (z) ≤ f (y) + f Lip y − z 1 = y − z 1 in the first line.
Proof Firstly, using Proposition 8, we know that µA µ is another empirical measure concentrated on {Attention(x i , X, X)}, similarly, νA ν is concentrated on {Attention(y i , Y, Y )}. This fact allows us to use the following result from Santambrogio (2015) Equation 6.2