Transformers are Universal In-context Learners
Authors: Takashi Furuya
Maarten V. de Hoop
Gabriel Peyré
Venue: ICLR 2025 Poster (2025)
Keywords: Transfomer
In-context learning
Universal approximation
Wasserstein
Optimal transport
Primary area: learning theory

Abstract: Transformers are deep architectures that define ``in-context mappings'' which enable predicting new tokens based on a given set of tokens (such as a prompt in NLP applications or a set of patches for a vision transformer). In this work, we study in particular the ability of these architectures to handle an arbitrarily large number of context tokens. To mathematically, uniformly address their expressivity, we consider the case that the mappings are conditioned on a context represented by a probability distribution of tokens which becomes discrete for a finite number of these. The relevant notion of smoothness then corresponds to continuity in terms of the Wasserstein distance between these contexts. We demonstrate that deep transformers are universal and can approximate continuous in-context mappings to arbitrary precision, uniformly over compact token domains. This result implies, as a special case, that transformers are universal approximators for continuous permutation-invariant mappings over a fixed number of tokens. It also establishes the universal approximation capability of transformers for certain in-context learning tasks, demonstrating in particular their ability to perform regression within context. A key aspect of our results, compared to existing findings, is that for a fixed precision, a single transformer can operate on an arbitrary (even infinite) number of tokens. Additionally, it operates with a fixed embedding dimension of tokens (this dimension does not increase with precision) and a fixed number of heads (proportional to the dimension). The use of MLPs between multi-head attention layers is also explicitly controlled. We consider both unmasked attentions (as used for the vision transformer) and masked causal attentions (as used for NLP and time series applications). We tackle the causal setting leveraging a space-time lifting to analyze causal attention as a mapping over probability distributions of tokens.

Published as a conference paper at ICLR 2025
TRANSFORMERS ARE ANIVERSAL IN-CONTEXT LEARNERS
Takashi Furuya'
Maarten de Hoop" Gabriel Peyré
1 Doshisha Univ. takashi. furuyal101$gmma com
PRie Univ. mvd20rica edu
3 &CNRS, ENS, PSL Univ. gabriel peyreeens. fr
ABSTRACT
Transformers are deep architectures that define "in-context mappings" which en- able predicting new tokens based on a given set of tokens (such as a prompt in NLP applications or a
patches for vision transformer). In this work, we study in particular the ability of these architectures to handle an arbitrarily large number context tokens.
mathematically, uniformly address their expressivity, we consider the case that the mappings are conditioned on context represented by a probability distribution of tokens which becomes discrete for finite number these. The relevant notion of smoothness then corresponds to continuity in terms of the Wasserstein distance between these contexts. We demonstrate that deep transformers universal and can approximate continuous in-context mappings to arbitrary precision, uniformly over compact token domains. This result implies, special case, that transformers are universal approximators for continuous permutation-invarian mappings over a fixed number of tokens. It also establishes the universal approximation capability of transformers for certain in-context learn- ing tasks, demonstrating in particular their ability to perform regression within context. key aspect of our results, compared a fixed precision, a single transformer can operate on an arbitrary (even infinite) number of tokens. Additionally, operates with a fixed embedding dimension of tokens (this dimension does not increase with precision) and a fixed number of heads (proportional to the dimension). The use of MLPs between multi-head at- tention layers is also explicitly controlled. We consider both unmasked attentions (as used for the vision transformer) and masked causal attentions (as used for NLP and time series applications). We tackle the causal setting leveraging space-time lifting to analyze causal attention as a mapping over probability distributions tokens.
existing findings, is that for
INTRODUCTION
Transformers have revolutionized the field of machine learning with their powerful attention mech- anisms introduced by Vaswani al. (2017). The exceptional performance and expressivity of large-scale transformers have been empirically well established for both NLP (Brown et al. 2020)) and vision applications (Dosovitskiy et 2020). One key property of these architectures their ability to leverage contexts of arbitrary length, which enables the parameterization of "in context" mappings with an arbitrarily large complexity. In this paper, we present a rigorous formalism to model inputs and the associated context with an arbitrarily large number of tokens, defining notion of continuity that enables the analysis of their expressivity.
Universality, from neural networks to neural operators. Multilayer Perceptrons (MLP) with two layers are universal approximators, as shown decades ago in Cybenko (198);; Homik et al. 1989), , with a comprehensive review in Pinkus (199)). The significance depth in enhancing ex- pressivity is explored in Hanin & Sellke (2017); Yarotsky (2017). These results have been extended to cover a variety of architectural constraints on the networks, for instance, invoking weight sharing in Convolutional Neural Networks (CNN) (Zhou 2020) and skip connections in ResNets (Cuchiero)

---

Published as a conference paper at ICLR 2025
et al. 2020: Tabuada & Gharesifard 2022) It is also possible to design equivariant architectures,
in particular for graph neural networks (Kratsios & Papon 2022 Keriven & Peyré 2019 Xu et al, 2018) and neural networks operating sets of points (Qi et 2017 De Bie et al. 2019)) The con- nection between transformers and graph neural networks is exposed in Müller et al. (2023) ). Here, take different point of view, with transformers operating on probability distributions rather than on sets of points. Related to this setup are extensions of neural networks acting in finiteddimensional vector spaces
dimeiie-dimeniionalll function spaces resulting in the notion of neural operators (Ko- vachki et al. 2023), the universality of which is studied in Furuya et al. (202). Neural operators can be generalized cope with data in metric spaces, addressing topologiaa obstructions, Kratsios et al. 2023b).
Mathematical modeling of transformers. It is now customary to describe transformers as per- forming "in context" prediction, which means that it maps token token, while this map depends on a set of previously seen tokens. The size of this context might be very long, possibly arbitrarily long, which is the focus of this article. The ability of trained transformers to effectively perform in-context computation has been supported by both empirical studies (von Oswald et al. 2023) and theoretical results (Ahn et al., 20044] Mahankali et al., 2023 Sander et al. Zhang et al.) 2023) on simplified architectures (lypically linear attention) and specific data generation processes.
To make rigorous analysis of arbitrarily long token lengths, and also to describe a "mean field" limit of an infinite number of tokens, it is convenient to view attention as operating over probability distributions of tokens (Vuckovic et al.) 2020) [aander et al. 2022). The smoothness (Lipschitz continuity) of the resulting attention layers analyzed in Castin et al. (2024). Deep transformers
(with the residual connection) can be described by a coupled system of particles evolving across the layers. The analysis of the clustering properties of such evolution is studied in Geshkovski et al. 2023a
Universality transformers. Yun et al. (2019) provides, to the best of our knowledge, the most detailed account of the universality of transformers. The authors rely shallow transformers with only 2 heads but require that the transformers operate over an embedding dimension which grows with the number of tokens. This result is refined in Nath al. (2024) which highlights the difficulty of attention mechanisms to capture smooth functions. Our focus different, since we consider deep transformers with fixed embedding dimension, but which are universal for arbitrary number of tokens.
We note that there exist variations over the original transformer's architecture which enjoys univer- sality results, for instance, the Sumformer (Alberti et al.] (023) and stochastic deep networks (De Bie al. 2019), which also requires an embedding dimension that grows with the number of tokens. We furthermore mention the introduction of probabilistic transformers (Kratsios et al. (003a) which can approximate embeddings of metric spaces. The work of Agrachev Letrouit (2024) provides an abstract universal interpolation result for equivariant architectures under genericity conditions, but it is not known whether there exist generic attention maps.
While this is not directly related to our results, line of works studies the expressivity of transform- ers when operating on a discrete set of tokens as formal systems (Chiang et al., [023 Merrill & Sabharwal 2023 Strobl et al. 2024 Elhage et al.] [021 Another line of work studies the impact of positional encoding on their expressivity (Luo et al. 2022).
1.1 OUR CONTRIBUTIONS
Our work provides a rigorous formalization of transformer expressivity and continuity as operat- ing over the space of probability distributions. The main mathematical results is the universality presented in Theorems and respectively, for the unmasked and the masked settings. Our ap- proach effectively handles an arbitrary number of tokens and leverages deep architectures without requiring arbitrary width. The embedding dimension and the number of heads are proportional to the dimension of the input tokens and are independent of precision. It is interesting to note that the masked setting requires some stronger regularity hypothesis the contexts, namely that they Wasserstein- Hlsserstein-Lipschitz with respect to time, which needed to cope with the constraint of causality in the relevant mappings.
2

---

Published as a conference paper at ICLR 2025
1.2 NOTATION
For natural number N E N. we denote by [M] =- [I....,N), For vector I E IRd, the Euclidean norm of denoted by |ar]. For vectors x; y E Rd the Euclidean inner product of and is denoted by (r, y} and the component multiplication of æ and y is denoted by x Q The vector 1, is the vector of dimension with all coordinates equal to that is, 1. (I..., E R We denote by P(22) the space of probability measures on f2, and denote by ((t) the space of continuous functions from Q to IE, where C Rd a compact domain for tokens' embeddings. In what follows, we frequently utilize notions such as the push-forwar forw-ro operator Tg, weak" topology (denoted by the convergence ~²), and Wasserstein distance Wp for S p < toc. For further details on these notions, we refer to Appendix A
2 MEASURE-THEEORETL IN-CONTEXT MAPPINGS
Transformers are defined by alternating multi-head attention layers (which compute interactions between tokens), MLP and normalization layers (which operate independently over each token). For the sake of simplicity, we omit normalization the following analysis. We first recall their definition and then explain how they can be equivalently re-written using in-context mappings. This definition provides new insights and can also be generalized to an infinite number of tokens encoded probability measure.
2.1 ATTENTION AS IN CONTEXT MAPPINGS TOKEN ENSEMBLES
Classical definition. A set of n tokens, E Rdus, is denoted by X = (z,) E R An attention head maps these n tokens to the same number n of tokens in R.doaad through
VX E K
(X) == VX SoftMax(XT Q KX/VK) E Rhaas
where the parameters are the (Key, Query, Value) matrices 0 = (K, Q V) E Rkxdio x Rxxdi X Ddddod x deok, Here, the (possibly masked) SoftMax function operates row-wise manner:
Ma.jee2. VZ E R SoftMax (Z) = (5 M,,eeZi.e 6,=11
RnXn
where Mr 1 for the unmasked setting (bidirectional encoding transformers) and M.j ردرر in the masked setting (causal decoding transformers). Multiple heads with different parameters 0 (Wh, 8h) ) ) are combined in linear way in multi-head attention
MAtta (X) = X +
Σ wh Att (X), h=1
where Wh E T and 8h = (K*h Q³, Vh). In the following, we denote the various di- mensions of a multi-head attention layer by: (l)) dhead (f) for the token and head dimensions, respectively, and k(0) for the key/query dimensions, and (0) for the number of heads.
In-context mappings form. For the unmasked setting, the mapping X + MAtto(X) can be re-written as the application of an "in context" function Go(X, to each token,
3t + Co(X, i.e. MAtlo(X) = (Go( (G.(X. (r)) where the in-context mapping is, v(X, E Idduxxn Rdua
H
exp vF (Q"x, Kha,))
:
Σ
W
vh Vh
(2)
Et=1 exp ( (Qhh, Khax))
1=1
1=1
In the masked setting, due to the lack of permutation equivariance, it is required to track also the index of the token. The mapping X + MAtl((X) can then be re-written as MAtto(X) (Go (X, v4, i)) where the in-context mapping is,
VK (Qhx, K Khxr))
exp
Go(X.I,1) = x+ Σ Wh
V"Iz.
(3)
1= exp (12 (Qhx, Kharr)

---

Published as a conference paper at ICLR 2025
Here, the terminology "in context" refers to the fact that Gg depends the tokens X them- selves, and can thus be seen as parametric map that modified for each token depending on its interactions with the other tokens. While this we-writing is equivalent to the original one, it highlights the fact that transformers define spatial mappings. This also allows us to clearly state the associated mathematical question at the core of this paper, which is the approximation of arbitrary in-context mappings by (compositions of) such parametric maps. Another interest in this reformulation is that enables the definition of generalized attention operating over possibly infinite number of tokens, as explained in Section 2.2
Composition of in-context mappings. A transformer (ignoring normalization layers this mo- ment) is composition of L attention layers and Multi-Layer Perceptrons (MLP):
MLPg, MAtto, o... MLPs, o MAtte,
(4)
Here, the ML.Pg functions process each token independently from one another:
( = (Fe(a:)))
i.e., they are "context-free" mappings (in the above notation, (x) =Fe(x)), while the attention maps, Ga(X, -) depend on the context X.
On the level of in-context mappings, the composition of layers in 4 induces new "in-context" composition rule, which we denote by o:
(G2 Gi) = (2 G1(,))) where X1 = (X,(X,
(5)
for the unmasked case, and
(G2 Gi),
G2(X1, (x,,,,, where X1 (Gi(X, i))
(6)
for the masked case. This rule can be applied whether C (X,,)) or G2(X, depends on the context X or not (such as for the Fg mappings above). Using this rule, the transformer's definition (4) translates into composition of in-context and context-free maps, i.e.,
Fe, Go, o... F5, Go.
The core question this paper addresses is the uniform approximation of a continuous (in a suitable topology) in-context maps (X, G(X,2)) (X, mappings of the form of 4 with clear control of the dimensions and the number of heads involved in the different layers. The main originality of our approach is that we aim to do for an arbitrary number n of tokens, as we now explain.
x(, i) by transformers' in-context
2.2 MEASURR- IN-CONTEXT MAPPINGS: UNMASKED SETTING
A first key observation is that the definition in 2 makes sense irrespective of the number n of tokens. The second key observation is that, in the un-masked case, M,, = 1, the attention mapping permutation equivariant. To make this more explicit, and also handle the limit an infinite number of tokens, represent set X of tokens using probability distribution μ E (R over |ddook A finite number of tokens is encoded using a discrete empirical measure,
Sz, ((R
n
This encoding is not only for notional convenience, it also allows define clearly correct notion of smoothness for the in-context mappings. This smoothness corresponds to the displacement of the tokens and is quantified through the optimal transport distance as presented in Section [.2] This enables us to compare context with different sizes and, for instance, to compare a set of tokens with a large (but finite) to continuous distribution. The in-context mapping in is now defined as, ((, E (( x Rdoo
I. (Q"x,, K"a)) vI
exp
Te(,,x) = Σ Wh
4 du(y).
I exp
Vh xQ Khz)) dy((2)
4

---

Published as a conference paper at ICLR 2025
The discrete case is contained in this more general definition in the sense that
G)(X,z)= I'o (- Σ S2.12)
XX = (z))
In the following, we will invoke, whenever convenient, the following slight abuse of notation, (e(u,r) ()))))
so that ['a(p) deo + Rdoox defines a map between Euclidean spaces. Using this general defini- tion, the attention map (Att can be rewritten as displacing the tokens' positions, which corresponds to applying a push-forward to the measure as defined in (22
J E (( + ro(u)a P(R
This formulation of transformers in Sander et al. (2022) and also used in Castin et al. (2024) to prove a convergence result of deep transformers. We re-use it here but put emphasis on the in-context mapping itself, which is the object of interest of this paper (rather than on studying the mapping between measures).
mapping between probability measures introduced
Composition of in-context unmasked theseee- mappings. The definition of compo- sition in generalizes to the measure-theorete setting in the unmasked setting as
(T'2 o (1) = (1(,,,,i(,, where Nl = (1))p,
(10)
i... (I's o (4) = (2( ) I'r (4)). Transformers operating over an arbitrary (possibly infinite) number of tokens are then obtained by replacing the original definition of 7 by
FEz o Toz .... Fei TT.
(11)
Here, the Fg are "context-free" MLP mappings, i.e., (u, Fx(x)) independent of μ. is important to keep in mind that when restricted to finite discrete empirical measures of the form of (8), definitions in 7 and in (T] coincide. Our theory encompasses classical transformers as well as their "mean field" limits operating over arbitrary measures.
2.3 MEASURE-THEEORTTE IN-CONTEXT MAPPINGS: MASKED SETTING
In the masked setting (for NLP or time series applications), M,, 1 L the attention mappings are not any more permutation equivariant. To restore this invariance, and be able to write in-context mappings using measures, we introduce space-time lifting so that the input tokens are of the form {2,, h where t2 E [0, 1]. For instance, assuming upper bound, N, on the number of tokens, one can use f4 = i/N, but it is also possible to assume that the t, are positioned arbitrarily in [0, 1], which enables considering an arbitrarily large (and infinite) number of tokens.
We thus let the context be encoded as a space-time measure E P(R x 1]). Similarly to Castin et al. 2024 Definition 2.6), introduced the in-context map, V(z, t) E Rhok x [0.
exp ( (QM,,, kh))) (0,4((r)
H
To(u, x, t)=
hh
Vny du(y.r), (12)
fexp + (Q"x, Kk (s) du(z,s)
#=1
where (s) masking function that is if S s S and otherwise. For a finite number of tokens, using a discrete measure, μ = - ((n))/)) one retrieves the initial definition (3) in the masked case. The space-time lifting can incorporate positional information, however, recent positional encoding methods, such as Rotary Positional Embedding (RoPE) (Kazemnejad et al.)
2024), included in the current formulation. This extension is left for future work.
Composition of in-context masked measure-theoreeic mappings. The composition rule in the masked setting is similar the one in the unmasked setting (cf. (10),, except that the time position of the token is kept unchanged while the push forward acts in space,
(T' o I (u, x,() == [2(,,, I (1,,,,(,,,) x, f), t), where p = (T, (M), IdR).u.
(13)
Here, (Ti (p), Idz) (z, t) E +1 + (T (x, e Bda+t (the time is kept unchanged). Equipped with this definition, one retrieves the composition rule in ( when the measure i is dis- crete.
5

---

Published as a conference paper at ICLR 2025
3 UNIVERSALITY IN THE UNMASKED CASE
3.1 STATEMENT OF THE RESULT AND DISCUSSION
Our first main result is the following universal approximation theorem for unmasked in-context mappings.
Theorem 1. Let Q C E be a compact set and A P((2)) x Ω - Rd be continuous, where P((2)
is endowed with the weak" topology. Then for all 0, there exist and parameters (0e, Ee) such that
V(, E P(L) x S2 [FE. Te. .... o Fe, oTo (,, A (H, S. with diok (0t) S d 3d', (82) = k((e) = 1, ((t)) d
Appendix demonstratee that this result can be applied to two key settings: permutation invarriint mappings over a fixed number of tokens and in-context learning of regression operators.
The two strengths of the result above are (i) the approximating architecture performs the approxi- mation independently of n (it even works for an infinite number of tokens), and (ii) the number of heads and the embedding dimension do not depend on ε. Moreover, its proof technique is notable, particularly because, unlike classical MLPs with cosine activation functions, shallow attention chitectures lack an algebraic structure as these cannot be multiplied. To address this, we rely on depth to accommodate this limitation.
weakness is that the theorem over the dependency of the number of MLP parameters & A limitation of our proof technique that the number of heads grows proportionally to the output dimension while each head only outputs scalar dread (0z)
quantaatanttat""".. meaning that that we have no explicit control
1. Obtaining better balance between these two parameters is an interesting problem. As explained in the proof, these MI.Ps approximate a real-valued squaring operator
+ a², so we expect this dependency however, our construction does not provide any priori bound on how the magnitude of the tokens grows through the layers. The main hypothesis of Theorem T is that the underlying map, A+, is a continuous map for the weak" topology over measures (see Section 1.2 for some background). However, this setting might not be a proper one for conducting further quantitative studies; we leave these for future work.
be well-behaved in common situations;
3.2 PROOF OF THEOREM
We first consider "clementary" in-context mappings, which map (x, (1) to real variable
TA(1,))) = (2r, a) b / eella, a) +b 4)+b) (fa, y) + b) du(y).
(14)
where A == := b, affine scalar-valued MLP with single-head attention (with skip connection) as in (.) operating in 1-D. Indeed, defining (x (a, z) + E R affine MLP, where & = (a, b), we have
ba, c, v) E Rdd x R IR x R. These elementary mappings are built by composing an
2) (To (H,,,,
where # (k,, q, v) 3 (recalling that this attention operates in 1-D), and we let gk.
We now define A, the algebra spanned by these elementary functions:
A= P(0) 0 (1, Σ PAl. (14, 2) O .... TAz, E (R:
The first main ingredient of the proof to show that this algebra is dense. Elements of this algebra are sums of products of elementary functions, which are often referred to as "cylindrical functions". Proposition
dense in the space of (weak" (e)-continuous functions from P(2)) x Ω to TR
Proof. We apply the Stone- Weierstasssss theorem. First, note that P(2) Ω is compact for the (weak* x e) topology (Aliprantis & Border 2006, Theorem 15.11). We then check the three key hypotheses needed to apply the Stone- Weierstrass theorem:

---

Published as a conference paper at ICLR 2025
1. The functions " continuous because the denominator f (c(( a) du((2) in the elementary mapping is not always zero for any μ E P( and x E Ω.
2. When setting a = 0, b
1, one has that (u, x) = 1 is the constant function. 3. We need to show that the set (ry)a separates points, which is more challenging.
For the last one, we need to show that if
YY, 7)( = (2(,'22))
(15)
then (H, = (p',x'). First setting v = 0, this implies that (x, a} (x', a) for all e R and, hence, x'. Then, setting b (a, x). (T3) reads (a, c) ((u')aa, c) where we defined generalized Laplace-like transform
eota. (a, y) dply). ecla, du(2))
[(p)(a,)) =
(16)
We conclude that je' using the following key lemma.
Lemma 1. The map μ + L(u) defined in (66 is injective.
See Appendix B. for detailed proof. To approximate vector-valued in-context mappings, we use the previous algebra of cylindrical functions along each dimension. Since the elementary mapping. 7A. is built by the composing affine MLP and single-head attention, we arrive at the following lemma.
Lemma 2. For any & > 0, there exist T, N E N and (0r,ss (t.n) such that
V(u,z) E P(2) x Ω [G(p, - A (2, Se,
N
where G(u,,)) = Σ
(TT i o FF FFE (1,,)) 3 . (Tōr.. o FF (M,
(17)
with drok (Be.n) = d', dread (Oe,)) = k((r,n) 1, H( d'.
See Appendix B.2 for the details of the proof. We finally need approximate G in 17 by deep transformer of the form of (7). To do that, we furthermore approximate the component-wise
multiplication maps, (x, v) E 2d + x G E Rd in I1 by some MLPs. This way, we obtain the following lemma.
Lemma 3. For any > there exist L and parameters (0e, (0),Ee) such that
V(u E P()) Ω (G(,, Fez o Tog o... Fei To, (u,xx) Se,
with (0t) < d 3d', dhead k((;)) 1, ((a,) s d'.
See Appendix B.3 for a detailed proof.
UNIVERSALITY IN THE MASKED CASE
4.1 CAUSAL MAPS, LIPSCHITZ CONTEXTS, AND MAIN RESULT
As before, Ω C Rd is a compact set, and we define Ω == Ω x [0. as the space-time domain. Throughout this section, f E P(O0, 1)) is the marginal with respect to only the time variable some space-time measure, E P(.)), i.e.,
j Pite where P: (a, (),,))+t te [0.
(18)
Approximation in the masked setting is more subtle than in the unmasked setting because causal attentions are typically less regular due to the masking. To cope with this difficulty, we impose additional smoothness constraints the context, which still allow for arbitrary number of tokens.

---

Published as a conference paper at ICLR 2025
Definition 1 (Lipschitz contexts), A map t [0, ((-lt) P(2)) is C-Lipschitz if V(s,t) E 1]3 (2( S C|s - 1/-
The set of space-time C-Lipschitz measures
Tipe(()) (52) = {u P(O) : 3p(-10) s.I. plx, 8) = p(())s)j((s)) and pu-(t) is C-Lipschitz).
The conditional measure t u(-lt) E P(2) is any valid disintegration of against the marginal D. and must be C-Lipschitz, We also define, Vo E (0, 1),
(ft) = (1 E Lipc p((0)) 2 0).
It is worth noting that these conditions automatically satisfied by discrete measure, μ 1 Ei= (zx, with distinct times == min44s it, t, > 0 (using C = Radius(S))00) More generally, if E [0, (tt) E Ω is C'Lippchitz and E P(O0, 1)), then μ Φyp E Lipc
Masked attention can be conveniently re-expressed as operating over masked contexts which are defined as follows.
Definition 2 (Masked measure). For μ E (ft), the masked probability measure μ E (S2) defined as
100 p ((0, t])
μ.
(19)
Thanks to μ E (St), where the starting point of is fixed as 0 (i.e., 0 E supp(p)), the masked probability measure is well-defined when / E (0, I]. We note that we can define at 1 = 0 as the limit (in the weak* topology), and such limit exists (See Lemma TOp. Thus, the map [0, 1] t + #e (I)) is continuous (for the weak topology).
In the masked setting, the aim is to approximate causal mappings, defined as follows, which are maps where the output of time t only depends on tokens with smaller times.
Definition 3 (Causal identifiable map). A space-time in-context map A is said to be causal if
V(u, x,t) ((1) x Lt Z,, M,,,,
(20)
Such map A is said to be identifiable for any context μ Li)),
1t = P4
M = A
(21)
By the construction, the masked attention map Is, defined in (12). is causal identifiable in-context map (See Lemma I1]. Since the composition of such maps preserves both causality and identifia-
bility (see Lemma 12 a deep transformer, formed by composing of causal identifiable in-context maps, remains these properties.
The following theorem mimies Theorem but is restricted to approximating on Lipschitz contexts to cope with the causality constraint.
Theorem 2. Let A be continuous (where (it) is endowed with the weak" topology) and causal identifiale in-context mapping. Then, for all > 0, there exist L and parameters (0r, / such that
YH, 21 t) E (i)) x Q, [Fe, o To, .... Fs, o To, (H,, x, - A x, t)) SE.
with drote (0&) d 3d', (Os) = k((2) = 1, H(Oe)) I d'. Remark (Sharpness of the identifiability and Lipschitz hypotheses). in Theorem 2 shares the same conclusion as the unmasked Theorem [ but requires stronger assumptions. In particular, the map A is assumed to be identifiable. This hypothesis is sharp and cannot be weakened: transformers define identifiable maps, and as proved in Lemmal 13 identifiable maps can only approximate uniformly identifiable maps. Identifiability is also crucial since our proof technique involves recasting the approximation over (p, x. t) as an approximation over a reduced space ()) Another important assumption is that we restrict contexts. This limitation is essential for ensuring that the set of masked contexts pr is compact, which allows to apply the Stone- Weierstrass theorem.
The masked approximation
approximation to Lipschitz
8

---

Published as a conference paper at ICLR 2025
Remark 2 (Fixing the time marginal). We impose that contexts have Dirac masses at O, namely [({O)) 2 a. While this is not restrictive for discrete measures, this prevents for instance measures with density with respect Lebesgues. It is possible lift this constraint, and instead impose that the time marginal j is fixed, Lee replace the set (St) by {u E Lipc(!)) _ v} for any v E ((0,1 1]) satisfying E supp(v). One can check that the proof of Theorem carries over to this setting with minor modifications.
4.2 PROOF OF THEOREM 2
To translate into the setting that can exploit the Stone- WeieeWeeesss theorem, we first introduce the following operation, which can be defined for any probability measure.
Definition 4 (Reduced mapping). For A P(L2) 52 I2 define the reduced map A. which takes two argument (n, x) as
(1, E P(Ω)) x Ω M(, = a, where e(j) is the end point of supp(p), that e(p) max fr E supp(n)) [0. 1].
We introduce the reduced space on which we consider the approximation.
X2 == {(r, x) (Q),, x E Q E [0, 1]]
Lemma 4. Let ( x + Rdd be causal identifiable in-context mapping defined in Deftmition 3 Then the following holds true.
(i) For any (u, E (itp x Si, M,, 2. Mpr,z).
(ii) If A is continuous, then the reduced map of X6 3 (He,I) + x)) is (weak" x E2)- continuous.
See Appendix C.2 for details of the proof. As the target map A a continuous and causal iden- tifiable in-context mapping. by applying Lemma 4 A has the form (i), and is continuous Xg. Also, the masked attention map I's holds the same properties (See Lemma Thus, suffices to show that the following proposition.
Proposition 2. For all > 0, there exist L and parameters (0e, (0e,Ee)(=1 such that V(ue, x) E XE, |FeL o l' .... F'e, L',, ()), - A (us, x) S with diok (0s) S d + 3d', (Os) k(Oz) = (0e) S d'.
basically the same as the unmasked case, just replacing the argu- ments for μ P(2)) with that for H4 e LipE For the application of the Weie-Weeesssssss theorem, we need to check the compactness of Ng. which is not obvious. Thus, we show that following lemma.
The proof of Proposition
Lemma 5. Xg is compact for the (weak" x (2) topology:
Sketch of proof. Assume that Pn E (9t) and (In, 4n) E ÿ. We denote by Pa 1J) = {v P([O, 1I) v({0)) 2 J.. and In E ((, 1J). As (o, 1]) and á are compact, there exits (10 11) and tx, E Ω such that (if necessary. re-choosing subsequence) a., - and (In, (n) > (xr, l). Since [0. 8 + (.1() )) E P(()) is C-Lipschitz, applying the general Arzela-Asceo theorem (see e.g.. Kelley (2017 Chapter 7, Theorem 17)), there exists p(-(s) P(2) such that (if necessary, re-choosing a subsequence)
sup We(un (-1s), p(-ls)) + 0 as n - oc. sE|o,1]
Thus, we define by := (()ss) which belongs Lipe (.). Using this convergence and the fact that the start points of jin, fa E (0. 1]) are always fixed at / = 0, we can prove the convergence of the masked probability measures, i.e.,
(un),, N4 as The non-obvious situation when t, > and 0 since the masked probability measure μt is differently defined on t 0 or E (0. 1]. However, this can be solved by the continuity of the map [0, 9 14 E Tipg (f2) (see Lemma 10.. See Appendix C.3 for more details of the proof. I1

---

Published as a conference paper at ICLR 2025
CONCLUSION AND DISCUSSION
In this work, we have presented a unified analysis of the expressivity of both unmasked and masked transformers in settings with an arbitrarily large number of tokens. A limitation of our method is that it is not quantitative. Using, for instance, the Wasserstein distance between token distributions could be way impose smoothness on the map obtain quantitative bounds. Our proof relies on the approximation of the map along each dimension and the use of commuting architecture (the trans- former layers multiplied together obtain the output). This results in growth of the number of heads proportional to the dimension. Lowering this dependency would require the development of new proof techniques beyond the use of the Sene-Weiessssrsss theorem. is important to note that universality results like ours do not directly translate into conclusions about the learning capabiliitess of transformers. However, our proof techniques, which leverage ideas from optimal transport, share similarities with those used in the analysis of two-layer MLPs (Chizat & Bach 2018). Thus, believe that future work could build on this approach to investigate both convergence properties of the training of transformers. We also leave extending codings, such as Rotary Positional Embedding (RoPE) (Kazemnejad et al. 2024), for future work. RoPE modifies all attention layers account for relative positional information, which would quire slight adjustments to the proof to accommodate the different formulas.
approach more recent positional en-
ACKNOWLEDGEMENTS
Furuya was supported by JSPS KAKENHI Grant Number JP24K16949, JST CREST JP- MJCR24Q5, and JST ASPIRE JPMJAP2329. M.V. de Hoop carried out the work while he was an invited professor at the Centre Sciences des Données at Ecole Normale Supérieure, Paris. He acknowledges the support of the Department of Energy, BES under grant DE-SC0020345, the Si- mons Foundation under the MATH + X Program, Oxy, and the corporate members the Geo- Mathematical Imaging Group at Rice University. The work of G. Peyré supported by the Euro- pean Research Council (ERC project WOLF) and the French government under the management of Agence Nationale de la Recherche as part of the "France 2030" program, reference ANR-23-IACL- 0008 (PRAIRIE-PSAD),
REFERENCES
Andrei Agrachev and Cyril Letrouit. Generic controllability equivariant systems and applications to particle systems and neural networks. arXiv preprint rIXiv:2404.08289 2024.
Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to imple- ment preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36, 2024.
Silas Alberti. Niclas Dem, Laura Thesing, and Gitta Kutyniok. Sunformer: Universal approxi- mation for efficient transformers. In Topological, Algebraic and Geometric Learning Workshops 2023, pp. 72 86. PMLR, 2023.
Charalambos D. Aliprantis and Kim C Border. Infinite dimensional analysis. Springer, 2006.
Jan Boman and Filip Lindskog. Support theorems for the radon transform and cramér-wold theo- rems. Journal of theoretical probability, 22:683-710, 2009.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Valérie Castin, Pierre Ablin, and Gabriel Peyré. How smooth is attention? In ICML 2024, 2024.
David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, pp. 5544-5562. PMLR, 2023.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in neural information processing sys- fems, 31, 2018
10

---

Published as a conference paper at ICLR 2025
Christa Cuchiero, Martin Larsson, and Josef Teichmann. Deep neural networks, generic universal interpolation, and controlled odes. SIAM Journal on Mathematics of Data Science, 2(3):901- 2020.
George Cybenko. Approximation superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Gwendoline De Bie, Gabriel Peyré, and Marco Cuturi. Stochastic deep networks. In International Conference on Machine Learning, pp. 1556-1565. PMLR, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenbomn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint 1XXiv:0010.11929 2020.
Dennis Elbrächter, Philipp Grohs, Arnulf Jentzen, and Christoph Schwah. Dan expression rate analysis of high-dimensional pdes: Application to option pricing. Constructive Approximation, 55(1):3-71, 2022.
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. A mathematical framework for transformer circuits. Transformer Circuits Thread, 1(1):12, 2021.
Takashi Furuya, Michael Puthawala, Matti Lassas, and Maarten V de Hoop. Globally injective and bijective neural operators. arXiv preprint arXiv:22306.0m 23390982..0 2023.
Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. The emergence of clus- ters in self-attention dynamics. arXiv preprint arXiv:2305.005465. 2023a.
Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. A mathematical per- spective on transformers. arXiv preprint arXiv:2312.10794, 2023b.
Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiv: 2017.
Kurt Horiik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5):359-366 1989.
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 36, 2024.
John Kelley. General topology. Courier Dover Publications, 2017.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Nikola Kovachki, Zongyi Li, Burigede Liu, Kamyar Azizzadenesheli, Kaushik Bhattacharya, An- drew Stuart, and Anima Anandkumar. Neural operator: Learning maps between function spaces with applications to pdes. Journal of Machine Learning Research, 24(89): 99, 2023.
Anastasis Kratsios and Léonie Papon. Universal approximation theorems for differentiable geomet- ric deep learning. Journal of Machine Learning Research, 13 2022.
Anastasis Kratsios, Valentin Debarnot, and Ivan Dokmanié. Small transformers compute universal metric embeddings. Journal of Machine Learning Research, 24(170): 2023a.
Anastasis Kratsios, Chong Liu, Matti Lassas, Maarten V de Hoop, and Ivan Dokmanić. An ap- proximation theory for metric space-valued functions with view towards deep learning. arXiv preprint ar3iv:2304. 12231, 2023b.
Shengjie Luo, Shanda Li, Shuxin Zheng, Tie- Yan Liu, Liwei Wang, and Di He. Your transformer may not be as powerful as you expect. Advances in Neural Information Processing Systems, 35: 4301-4315, 2022.
11

---

Published as a conference paper at ICLR 2025
Arvind Mahankali, Tatsunori B Hashimoto, and Tengyu Ma. One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. arXiv preprint arXiv:2307.03576. 2023.
William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.079223 2023.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending graph transformers. arXiv preprint urXiv:2302.04/35 2023.
Swaroop Nath, Harshad Khadilkar, and Pushpak Bhattacharyya. Transformers expressive, but are they expressive enough for regression? arXiv preprint wrXi:22402.15478, 2024.
Allan Pinkus. Approximation theory of the mlp model in neural networks. Acta numerica, 8:143- 195, 1999.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 652-660, 2017.
Michael E Sander, Pierre Ablin, Mathieu Blondel, and Gabriel Peyré. Sinkformers: Transform- ers with doubly stochastic attention. In International Conference on Artificial Intelligence and Statistics, pp. 3515-3530. PMLR, 2022.
Michael E Sander, Raja Giryes, Taiji Suzuki, Mathieu Blondel, and Gabriel Peyré. How do trans- formers perform in-context autoregressive learning? arXiv preprint arXiv:2402.05787, 2024.
Filippo Santambrogio. Optimal transport for applied mathematicians, Birkäuser, NY, 55(58-63):94, 2015.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal lan- guages can transformers express? a survey, Transactions of the Association for Computational Linguistics, 12:543-561, 2024.
Paulo Tabuada and Bahman Gharesifard. Universal approximation power of deep residual neural networks through the lens of control. IEEE Transactions on Automatic Control, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- fion processing systems, 30, 2017.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordy- intsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pp. 35151-35174, PMLR, 2023.
Johannes von Oswald, Eyvind Niklasson, Maximilian Schlegel, Seijin Kobayashi, Nicolas Zucchet, Nino Scherrer, Nolan Miller, Mark Sandler, Max Vladymyrov, Razvan Pascanu, al. Uncovering messa-ptimizzttonn algorithms in transformers. arXiv preprint arXiv:2309.05858, 2023.
James Vuckovic, Aristide Baratin, and Remi Tachet des Combes. A mathematical theory of atten- tion. arXiv preprint arXiv:2007.02870 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1810.088100006,,, 2018.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint arXiv:1912.10077,.00 2019.
Ruiqi Zhang, Spencer Frei, and Peter L Bartlett. Trained transformers learn linear models in-context. arXiv preprint arXiv:2306.0999 2023.
Ding- Xuan Zhou. Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2):777-79,, 2020.
12

---

Published as a conference paper at ICLR 2025
APPENDIX
A BASIC NOTIONS
In this section, we briefly review basic notations used in the main text.
Let Ω Rd be compact domain. For T Ω Rd 52' IR being measurable map, the push-forward Ti E P(())) of μ E P(22) is given by
AA D Tau(A) = (f (A)).
The push-forward operator, T3. operates on discrete measures by simply displacing their supports,
T.
6z.
8T(a.)
For a general measure, v T;4 defined by change of variables in integration, i.c.
J glv) dv(y) / ((T(z))
Vg E C(S'),
(22)
We employ the weak* topology P()). This induces the following notion of convergence of sequences:
1 + ( / d()))) + / f(x) dp(x))
Intuitively, this corresponds to "soft" notion of convergence where the support of μa approaches that of μ..
In the special case of discrete measures, with a fixed number n of points, this corresponds, up to relabeling the points, to the usual convergence of points finite dimensions:
6
[x (Ii,K)s Rdxa x = (xs); Rdxx)
It is possible to metrize this weak* topology using the Wasserstein Optimal Transport distance, which is defined, for p < + 0o. as
{ || w/1 dx( = μ4, 12 =V) min #EP(O2)
Wp(n, 2)
where m, = ( are the marginals of x with Pi v) = x and Pa(x, y) = y. One has Wy(ms, p)) +
e.g.. Santambrogio 2015 Theorem 5.10). This Wasserstein distance is used in the masked case to impose Lipschitz regularity with respect to the time the contexts.
B PROOFS IN SECTION 3
B. PROOF OF LEMMA I
First, we show the one dimensional of Lemma 1
Lemma 6. Let Ω C R be compact set, and let μ.v P(L). Then,
Li(H)(c) = Li(v)(c), VCE + =
where, for 1e E N,
(x(((c)) = e du(y)
ee du(z)
13

---

Published as a conference paper at ICLR 2025
Proof. One has
(x) - Lx+I(A)(c) -x(W)))))(()()))
Hence, by recursion, have that
(e))(c))= = (c))(o,, Ve E R = [x(u((e) Lo()(()), VC B, Ak 2 1, Evaluating the equation at O, we obtain that
(0) (z)))(0), vk 21 Yhh, ʃ dd(u)=== dudl)).
which is equivalent f v.
Using Lemma we arrive at the following lemma.
Lemma (Lemma)) in the main text). Let Q c R be a compact set, and let p, v E P(Ω). Then.
L(n)(a,)) L(v)(a, c), Va Rd Vc E R, = ==v.
where
c))) [exp(c(a, ()) v) dp(x) Texp(cla, du(z)
Proof. We define
Ve ES, ==:= == (Pc)a/,
where gd is the d-dimensional sphere, and Pa(x) = (r, e) is the projection on e. We see that
L(u)(e, e) [ expp(ce, (e, v) dplu) se
Sexpícle, z)) d]((z)
Je feerdp (r)
By Lemma 6 show that
Ve, (Pe)s/ / = (Pe)au: which implies that, by the injectivity of the Radon transform (see e.g., Boman & Lindskog (2009) Theorem A)),
B.2 PROOF OF LEMMA 2
We write
(u, (Ai(1x)), .. Aa (1,,)),
where Aj : P(2) x Ω + R, so that
d'
(u, x) = Σ AH,,,
h=1
where (en)neja) is the standard basis in IRdd,, For each h I,..., d'. apply Proposition 1 to A and conclude that there exist T, N and (NImeee(T),nEN such that
N
V(u, x) E P(2) x 2 ()
Σ
Vag. (H,2) @ ... 3 ry,, (p,2) S e
v
nml
This implies that
d'
V(, E P()) Ω
A+ (),,,))
Σ
Σ
vx (1,,2) ..... 02g (1, eh
h=1
d'
2
Mgu, x)) -
Σ
Yxh. (u,2x) 3 ... 724 (1,z)
(23)
n=
14

---

Published as a conference paper at ICLR 2025
Here, wrote
X/n = (o b/
ci ( E R
We introduce
N
G(u,
=
Σ
Pa4, (1, x) 3 3 Vag.,. (1, Eh:
h=1 Ln
or
G(u, =
Σ
Da (1, ... ......7.000 FAr,a (11, x),
(24)
n=1
in which
Ya (1, =
MAth (He, xm Saammnee Yatt. (1, E Rdd
We define self-attentions by
exp (lltin K(nn))
T (1,x) = + Σ
V/h Vindd,ly) x ZER", (25)
1,
|exp (Qtime, R/ Rkine) dp(z)
h=1
where
:e, (Whn, r.m Vil 2h, KT, fi,))hl,..... C Rd Bixd' x Rixd' x RRxdd
ie., drox (0r,n) = d', dhead (0.,)) = k(00,,) = and
Wh: = (0,... O,
O, ..., 0) = Ebi
h-th
VAA (0, .... O, unn O..., 0), Qi, (0, .0 Cn O..., 0), K (0, (0,... 0, 1 0..., 0).
h-th
th
h-th
We define affine transforms, F a.. Rdd + Rdd, aacordiig to
Pe... (I) = Ar, + br,as
(26)
where Er,m = (A,nsben) E RRd'xx xd x Rdd in which
A = (a) (nn)) ben = bl.))
Then we have the composition, " o Fe... (1)
-I ((FE..) )ppl Fe (x)) Ae, + ben
(27)
exp (10): ((0t,,(AA,ss (Arai + be,)); Kit (enn(Arn, (Ar. + bea)))
exp
Wrb
ʃ eexp (10t.n + be,n), Rh (e (Ae,z + be,)) dp((2)
Vhh (Ar, +
Σ (olin x) bū..
exp ((latin 2) + Db (aaa y) + b/in))
e Caalaafi 8) + bl.n) dulee) en
+
[ eepp (latin 2²) Dg )el (edtnnn(aa (lat 2) + blim)) du(()
Txg, (w, z)en = Tran (1,
h=1
With 24h. find that
N G(u,z)= E Tr. o Fe... ....0)0))0000 fr... o FFr..) x).
(28)
n=1
Therefore, with the estimate in
23
obtain the statement in Lemma
15

---

Published as a conference paper at ICLR 2025
B.3 PROOF OF LEMMA
We first establish the following lemma.
Lemma 8. For any > 0, there exists MLP Φ RR2d IRe such that
v(,,z) E P(2) x 2 [G(,, - G&,
where Go(H,2) Σ
(Tor, (u, 1 (Tôr-in F (H,,));
@(TTea o F (ean 2 (Tor.. ( x), 1a )))
Proof. We note that
(T (r F Ey.. (u,
....) (Tōr.. o (u..))
(Trrr-n o (H o... (Tārn, o F (4, @
@ (TT o ((,, @ (Tom.. x1)
o
Because the component-wise multiplication map (I, y) R2d x OyO Rd is continuous, by the universality MIPs, for any and R > there exists an MLP Rd2d'
Rdd such that
v(x, v) E Base (0, R), I 1 v) S.
(29)
Since Q IR is compact then s Co == supren ||r|| is finite. Thus, using 27 we obtain the estimate,
(Ta... o oF FF (H, S 11 + 1| +
(1,lelll2C + (12) [ t,n
Vida ll2
h=1
AI (12) +
I Veh Venll2 l1z)
max te [E[]]
hm
=:Cp for all (H,x) E P(2)) Ω (30)
where the constant, Cj. > O. depends on Ωt W Vhh A bt but is independent of t, n, μ and Thus, using the universality in 29), choosing a large radius R > O depending on the constant
OF > 0, we can show that
(Tōr.. P' (H, .... or. o (u,
- * (TTr Frr.. (H, 1 (Tōr-ın o (H,
2 (TT o F Frg. (H,z), 2 (TT... Fan (H, x), 1.
N
Upon summing from n I,..., and using the form 17 we complete the proof of Lemma
Remark 3. (The challenge derive quantitative estimates.) The key is to approximate and cap- ture the mentioned multiplicity by MLPs, for which quantitative estimates have been studied, e.g., Elbrüchter et al. (2022) Lemma 6.2), which is variant of Yarotsky (2017] Proposition 2). However, the depth and width of MLPs depend on the bound of input variables. Specifically, an existential &b in the above depends on the bound CF (see (30)), which in turn depends on parameters I F that are chosen to approximate m within E through the application of the Stone- Weierstrass theorem (see Proposition 7) Thus, providing the quantitative estimate for the MLP, $b is challenging.
16

---

Published as a conference paper at ICLR 2025
Finally in this appendix prove, by construction, the following result.
Lemma Ler R2dd + Idd' be an MLP. There exist Ev. (SLm))e)T,,EE))) &x. and to. (() O, such that
V(u E P(2)) Qi
Golu,x) = Pe. Toe o (o ot Pein o TBum) Feo Too (1,
with following sizes:
drok (00) = d, (head(to) = k(00) ((0)) =1,
drok (Ot.,) = d 3d', dhead (0e,n) k(Or,n) = 1, (1(0.)) = d'
(0o)(0.) = d + 3d', Aread (0.) = k:(O., = H(O+) =1
Proof. The proof is based the following scheme:
F4o 0r [Shep
Fēr. (x) (1.11x)) fi(a)
P (4) (L)))
1.1 111
Ftr, (w)
Fer, a or.1
Ftz (x)
[Step
IStep B)
1Shp
(T.1 fi(m)
BStep Cl
91,a(())
f2(1)
Fci,2 oT01.2
(())
Fez 05022
Fer-1a 1.2 11
Fen (x)) (())(()) fa(e)
a (xx)
(2.2(())
(8tep.
[Step
(13(()))
f2(x))
falx)
N 1 (Sep
(
Feg.N o0
Fey 1.N oFo 1.N
Fēr, (x) PT.N(() (x(
For To [0
Ner (x)
(2.v(())
[8
18tp
$1.N (1
(x(())
(x+1(a)
Fe. oT', D]
fx-1(x) (g.
where Pen : Rdd + RRd is given by
T (To.. (u. @ (T (0
(x)x(x)== ==
$ ((T oz... o
F Féa.. x1, $ ((To,,. Fr (H, La
12 2
lay,
f f=1
and fa Bdd + Rdd by
[n(x) = (
n> 2 n =
where Fe and Fel., Rd Rd the self-attention and affine maps chosen in 25 and 26 respectively. Here, To., Tor.. To., Fe.. Fe... and Fş. will be specified below, the following steps:
[Step A] Let Ioa, (n) Rd + Rdd be
To, (n, x)) = x,
and let Fs. Rdd 3d' be the affine transform defined by
11,1, (c) = (x,, A1 b1,1, 10, 0) (x, Pe., (1.)
Then we see that
Fs. To, (x, (z. (x),
(1,1
and
M1,1 = (Feo o (x)) (Fe. )aH, (P1,,) (fi)au)
We proceed with [Step B] in which handle the when 1
17

---

Published as a conference paper at ICLR 2025
[Step Lett= I.... T and n 1,... N. We already have that
Po o Tagmm (o o'=1 Pe... o To,s)) o Feo (u, = (x. Pe (2)) (enn(()
and
1=,m: == ((oj=/ o oo (0 oa Fe,, o To,.) o Feo o To, (o)(1)))
= (I, )a14, (PLm))sH (fn)alt)
Whenm=: or l = 1, the above reduces to R-1 of Pe.,, o To = la4a0 or oj Eea o To I043d'.
Let To (Mtm) Rd+3d + Rd+3d be given by
To (p (2t u,P, w)) = (x, U,P,
exp (Q ux, ('
Wh
Sexp u, w), (v, (y U,,
Vil o' z u'' exp (10tn" Rinn")
d' x, u
Wh
The Vin dpe ,', w
Sexp (10t u, R k)
h=1
(I, ((F ) u) w)
where 2, U. E RRS u,u, Rd, .Pq.d' E RC, and w, 2, Rdd. Here, orn is given by
On, = (Wh,, vh Oi k C pgd+ddd x1 x gixd+3d glx++3d x glxd+3d
that is,
(1sm) = od+dd. ahoad (0r,n) k((0,n)))) 11 H(O,,) = d'
and
Wh fn
(.,,A, = (0, W/h In:
O), VAA = (0, v/ V. 0,0),
Qi,n (0, 2,, Kt, = (0, -O, 0,0).
Let Fe Rd+td + 3d+ be defined by
Fe., (x, u. U, = (x, A4t1N + b4t1, (u. = (x, Fr Eett.n (I), ((, (31)
Then we have
(o Fe,.. o To (0 of Fe., ooo,)) o Fs, (p,I))
= FFe Te... o (oj oo ( o Fe.. o ooo..) Fso (T)(
= Feam T (Me. (z, Fr.. (1))
Fenm (z, L' (FFe )11,, Pe,.. (x)) (L)))
= -esn (z., (Tr.. o Fz... (H, (z)
(z, Péomo (x), (F41, (2),
and
P0 = (lo) o (Tg..) o (0 of Pe.. o To..) P'oo (T)())))
= (H, (F. (Fimmm)) )ap,, (10441,))114 (fn)st).
18

---

Published as a conference paper at ICLR 2025
We repeat [Step BJ until obtaining pr,.. Once Pr,n is obtained, we proceed with [Step CJ.
[Step CJ Let Teet Bor,, (MT,))
Rdd+ Rd+3d be given by
Tor (Dr,as (I, u, w))
d'
exp (104,n4 R4,n'))
Wh
VAne dur uu, 0' 22),),))
u,u
Tin
Sexp (C0t,n", u, R4, (y,
hml
x, Trr, ((F Er, DEH u), p. w)
Let Fer,. RR4+3 12 be defined by
Fen,, (,) 1 11 Le, w pu, (x, famm (z), fl, (x)))(((),,,))))))) w+ wu, p)).
(32)
When n = N, we define by Fsi (I) = 0 and P1,N+1 = O in the above. We find that
Fe o To (of=m1 o Fe.. To,.) ) Foo To, (1)))) Frr (2, (Tōr,o For..)(e (1,, x), pI, (r, ( fu()))
(n+ (1) = =(I, Fr Pa (Imt))))
and
PT+11 = (10)=1 Feam o oTog.)) (0/=² T Fé... o ooo.)) o Peo o ooo (1)))))
= 14, (F (F Eimmy Dell, (11 (fnt1)uu).
Denoting
M1,+1 1,m1
return to (Step B), and repeat [Step B] and [Step C] until obtaining JT+INN. Once JT41NN is obtained, we proceed with [Step DJ.
[Step DJ Let To, (#T+1,N) Rd+3d + 3d+ 3d' be given by
Te. (PT+L,N (z, u. p. w)) w,w,,
and Fş. Rd+3d' + Rdd be the affine transform defined by
Fg. (x. u. w) w.
Then we conclude that
Fe. To. o (o of Per.. o To.... ( Pso o (1,
= Fs. oTo, (HT+IN, (z, (I, (I), (2 fx+1(=))) = fx)
N
Σ (Tōp. Fir,),, xx), T (T Fér-n. (M,
n=1
... F ((T
Feg. (H, $ (To o (w, 1e ))) Go(ua)).
Remark 4. Note that if the MLPs represent the identity map, such when using ReLU activation functions. then context-free maps Fe... in (3I) and (32) can be represented by MLPs. If this is not the case, is sufficient further approximate Fer... using MI.Ps.
19

---

Published as a conference paper at ICLR 2025
C PROOFS IN SECTION
C.I BASIC PROPERTIES FOR THE MASKED CASE
Lemma 10. The map [0, 14 E (S) is continuous (for the weak" topology).
Proof. Let μ E Lipe (12). We re-define the masked probability measure (including at by
E (0,1)
(33)
11.18)0.-0 -
Thus, the continuity on t E (0, 1] is obvious. We now show that as t + 0
#4 po.
For f E C(L)), we see that
f (x, 8)
duu - (xx
/ [(x 8) du((ols))
(0.1((s) dī(()) / ((x, (((
a((10, f))
/ f(x, (( du(((s)
(0.0)(s)
da(s) / fzx,0) du(z10) du(z)))
(s)
*( t]) dā(s)
(((0, f))
(s)
(((0,)) f) (F(s) F(0)) di(s) s sup
IF(s) F(O)).
sE|o,4]
where
F(s) = / f(x,)) dp(zss))
and + F(s) is continuous as p. E (it). Thus we have, as t + 0,
/ [( [((,,)) du + f f(x,
which implies that
14 No.
Lemma 11. Let To be the masked in-context map defined in (2). Then we have the following:
(a) To is a causal identifiable in-context map in the sense of Definition 3
(b) For any (n, x,,) E ($t) E2
To(u, xr, To(me: x))
(c) The reduced map of Xg e (Hr, + (o x) is (weak" x contiinuuu..
Proof. To show (a), observe that
exp (Qhx, Kh))) 1 11.0(())
To(H, 2,,) x+ /
vhy dp(y,r)
1 [ Tep
(Qher, Khz) 1 (s) d)(2,
VR
exp
Vi 1Q x, Khy)
rhy (ree(r) du(y,r)
x+
dex VR (Qhr, Khe))
Uouuls) dp(2,s)
a((0
exp ( (2"2, km)) (r).
= =x+
vhy durlyr)) To(H,, x,t).
dxxp ( (Q Kh>)) 1 (s) du)(2,s)
(34)
20

---

Published as a conference paper at ICLR 2025
This proves the causality. To show the identifiability, assume that br pe where μ ( and t, E [0, 1]. Without loss of generality, we assume that t < t'. Then we have that ş = on [t, so that
1 VR
(Q" (Q*) (r,
exp
To(m,, x
Vny dp)(v,r)
Sexp
VE
aQ Khz)) 1 (0)
Vt2 (2 K* (1,
exp
x
yhy (y.
Sexp
L
(Q Khz)) (s) (2,(
Vk
1 1Q Kdy) v) 1(00(())
/
exp
x
vhy dpe Tolue, 21,1)
S Sexp
1
(Q"x, kha)) 1 (0) (uu(
VI
Thus we obtain (a).
From Lemma 11 (a), To is causal identifiable in-context map in the sense of Definition 3 By
applying Lemma (i), as Ts we obtain (b).
Using Lemma 11 (b), we find that
I)( = L'e( 2)
cxp J1 1Q",, k²y)) (r))(()) vny dp((y,))
x +
S fexp
Je 1Qhx, kh2)) ((0.)(()) (2)
exp
( (Q"h kmn))
x
Vnu duely,)).
(35)
sexp
1 (Q K)2) (2)( VI
We can show the continuity of the map
1 (Q K Kmy) Vk
/
exp
P(Ω) X (1, + +
Vhy du(y,r) e RR"
exp
Je (Q"ar, Khz))
du((z,)
which, in fact, follows from the continuity of the unmasked self-attention. Thus, with 335 obtain (c).
Lemma 12. Let 11 and D2 be causal identifiable in-context maps in the sense of Definition Then, the composition 122 I1 in the sense of (13) is a causal identifiable in-context map.
Proof. Assume that (,, E (iip((2) x 2. We first show that (IT' IdR).u), = (Mr), IdR)aHt.
(36)
Indeed, we that for all e C(Ô)
[ flz (( IdR)au] (z, / (Ti(H)(E, s), du(
/ (TT(L)) s). du(()ss ds(ss)
/ (c. (a) dā(s),
which obtains that
(Ti(n), Idg (T()(s ())(())))
(37)
21

---

Published as a conference paper at ICLR 2025
This implies that by using the causality of 1
j (()) (I,
/ (x, s) (ax) 1 10.4 (s)
((,t)) ds(ss
= f [Ti((,,, 2),
1o. d))
du(als)
dā(()
[((0, f))
= f [Ti((s.,, I, 8), d)((r(s)
dj((s)
p((0,t))
= f [Ti(H,, I, s), du(x)s)
[0,0
dī(s)
a t])
( [ 8), (x,
/ (2,8) (TT Idm)sul] (2,
where we have used that μe dr when S t. This shows (36)
We see that by using the causality of 1 and 22 and 366
T 2,,, T24,1
I2 ((Tx()) Idp) uM, T 2,,
= It2 (I()) Ida)sal (Hee t),,
.T2 ((T (14,,, Idz), 21,
I2 o Pı 2,,, ().
These discussions apply for E [0,1], and the case when t 0 follows by the same argument. Thus, obtains the causality of [22 T
Assume that 14, pe where μ E (i)) and 1, 1' E j0, 1j. Without loss of generality, assume that t < f'. We have that by the identifiability of I and 22, and (36)
I2 o Ti T2 ((T (m(), Idg) Ti (Me t),
I'2 (He) I' (Mtr xt t'),
I2 [d2))))) T1 (1t
t'),t)
I2 [d)))))) (Mrr, 20, ('),
Ia ((T (dk))) (uw, x,, x,,)),
=[ o F1 (1e,,
where we have used the following fact from 37
[[0.4] ((s)
(TT) Idx):ll, [Ti(#)() ()
[00.99
p0(0, (1) ((s) [(TT(w),
These discussions apply for t E (0, 1]. and the case when t 0 follows by the same argument. Thus, we obtain the identifiability of l TI.
Lemma 13. Identifiability is stable in the following sense: Let Nn be continuous and causal, identi- fiable in-context mappings, and let A be continuous and causal in in-context mappings. Assume that, as n + xC
sup (e.
(p, A A 2, t)] + 0.
(38)
Then, the map NO is identifiable.
22

---

Published as a conference paper at ICLR 2025
Proof. Assume that 14 pe where μ (i) andt,t' E (0, 1]. As An = 22, and Pts Pe TipE (S2),
that
|A (1e, 6) A (uv, t')l
< A (1e, 21 (n 1)] + (Mr, 2. - A (ur, (,,() | (,,,,,,,1) An x, x, 1) (An 2, N (1b,,t)))
sup (L.. xf)
2
sup (p.a,))LLipg (
(u, (1, x, O,
which implies that
A "H,,, = A 2,
C.2 PROOF LEMMA
For the representation (i) we find that, by using 20 21 and μtx Me(ac))
A(J, x, (p,, x. 2I, MHeeaa)) M),,))
where we have used, for the second and fourth equality, pr = He(pe))
The continuity (ii) follows from (20). Indeed, we observe that
A (pr.2 2) A x((,a,, = 2,
(39)
Viewing
Me(a)) (Ha(p))e(a)) (He(a)))1 pe:
(40)
where (el(a)))(aa)) and (He(m))) regarded the masked probability measures of Me((a)) t = e(pe) and t 1, respectively, obtain, using (0 (39 and (40), that
A(u, x) = A((ee()))( e(ā+)) A((Pe(a))) 1) = A(r, 1).
Thus, by the continuity of A, we conclude that the map (#1,2) + M(,, = A 1) is contin- uous.
C.3 PROOF OF LEMMA 5
Assume that Nr, E (it) and (xm, fn) á. We that {s + pm (nIs))eN C C(O0, 1]; P(2)) is equicontinuous, as 8 > pn (11()))) is C-Lipschitz. We also see that
(nn (+)))e)))e C P(22) is compact for each s E [0, 1].
as PQ)) is compact in the W2 topology (see e.g.. Aliprantis & Border (2006 Theorem 15.11)). By the Arzelä-Ae -Ascoii theorem (Kelley) 2017, Chapter 7, Theorem 17), there exists (1-(s) PP()) such that the map s + μ(-ls) is continuous map and (if needed, re-choose subsequence)
sup We W2(Mn p(-Is) ((-ls)) + 0 as oc.
(41)
=E[o,1]
As (Pn)NEN C. Pa ([) Po([O, 1]) such that (if needed, re-choose a subsequence) as n
== {u e P(O0, 1I) v(())) 2 of and Pa ((0, 1]) is compact, there exists
An p.
We set
= (=(((s))[(())
Then we have
1 E LipE
23

---

which is equivalent to Published as a conference paper at ICLR 2025
because
Wa(u((s)) - W2(u(-1s), Cls s'1,
(-16'')) + (2(
2 2 sup xE(0.1]
and taking limit as n 00, see that - u(-1s) E P(2) is C-Lipschitz. Note that form
/ (())) 9(2) du(z)s) 0.
Vg E C(2),
sup sE
(42)
Indeed, since the set Lip( of all Lipschitz functions on is dense in C(22), for any g E C()) and any (0, 1), choose h E Lip(St) such that supzen (g(x) h(x)] I We that as W1 s 22 and the dual formulae
/ g(x) dap((a)s) - f ((x)))(()))
(ʃ
h(x)
dp (2|s) - f
h(x) dp(z)s)
< 2 sup 10(x) - h(x)1 + Lip(h) 2EI2
Lip(h)
Lip(h)
2e + Lip Wi (14 (-1s) ((
- 2e + (ip(h) ((-ss))
Taking sup)e and the limit as co, obtain 42
As (Ins fn) E 52 and 2 is compact, there are (a, t) á (if needed re-choose the subsequence) such that
(In, tn) - (Ir, t) in Ω
We finally need to show that, as n - oo,
(um)e, - pro
f rdduwnn + / sdm-
Af V
(43)
It is enough to check any functions f which separable, i.e. of the form f(x, =( 9(x) because linear combinations of separable functions of the form Σ. (z)),, are dense in C(1)).
To prove
43 we distinguish three cases (appropriately choosing a subsequence again):
ii fy E (0, and e (0, 1], (ii) t. E (0, and o, and (iii) fn
CASE (i): We that + 0o
{ f d(ju)). - / dde
sdde
-fou 1o..1 (n0(0,t)) tnl)
(s)x(1))))((s)))
dun(lss)))))s dpr(s) S.n p( t))
(s)(())
(ʃ g(x) (u(elss dp(s)
+ O,
because n0(0, > 0. equation 42 and using that i., - p.
24

---

Published as a conference paper at ICLR 2025
CASE (ii): We that
f f dd(u))). ( Idpo
-fo _o.11 (m((0,6n)
(x)x0)()))((8))
(L (f slend)n(()s)) dsn(s)) / dplx)))
1o.1 t(), (( din(()) 1mu 110.0.(6))((0))
(s)(c(())l((8))
(fot)aattnl dgn((s)
((0,
h(s)) / ((x))d)(())) h(0) / ( ((x))
1 110,em (6)
dsn(s)
sup sE(0.r..]
10.11 (1, (n]
h(s) / dpn(ss) h(s) / g((x) du(z)ss)
sup sE(0,rm]
h(ss) / g(x) ([(()s))))) h(()) / s( (())))(())))
+ sup sEju,ea]
/ dun (px - ((()))(())))) sE(o.1] sE(0.1)
< sup
[*()] sup
h(s)) / (((()) (((=)d(((())) - -h()))))))()))))))))))))>))))- / g(xx du(z)() +0,
sup .E(o.t..]
where we have used (42 and the continuity of the map + h(s) ( dp(zls).
CASE (iii): We see that, as n - oc.
f [ddpp)en
- Idd = [d(pnno- / Idwo
-1(0) / dpn(())))))) - -(() / du(a(())
|b(0)) / ((x) (pm()))))))))) - ((x))((z()) + 00
by using 42 Therefore, we obtain 443
D EXAMPLES OF OUR THEORY
D. DISCRETE CASE
We consider fixed and an in-context map G(X, 2), with X e Rdaxn, which is continuous on e? and permutation equivariant with respect to the tokens. This defines a map on discrete probability measures
r
Σ de,, = G((x));,)
which is continuous for the weak* topology the set, (A) P(R), of n--piint measures (that is, uniform distributions supported on n points). The map I' is continuous on (2) (because on point sets, the weak" topology coincides with the ettooology up to permutations), and P., (92) compact (because it is closed subset of compact set P()))) Hence, we can use our theorem on P. (S2). and obtain that I' can be approximated by a transformer on this space. This implies the approximation of G by a transformer.
D.2 LINEAR REGRESSION
In the discrete case, tokens are assumed to the form x; = (u, v)) where u, are features and e labels be predicted. Then simplified (linear attention) transformers shown learn
25

---

Published as a conference paper at ICLR 2025
in context linear relation 22 W u4; the in-context (1-C) "prediction" then maps some (u, v) to (u, Wu) (that is, the value is discarded). Adding a ridge penalty, X, to make the problem well-posed, this corresponds to the I-C map
G(X,(u,u)) = (u, u)))u) where ((X) = argminw
Ww: u/l1 A/[WI|/
We note that Von Oswald et al. 2023) consider, in fact, a single attention layer and replace this minimization with single step of gradient descent for simplicity; however, this is just modification of the in-context map.
Thanks framework which operates measures, the above regression be written, for any n. upon considering a data distribution j over the space (u, v) of (feature, label), in terms of the more general in-context map.
/ /IWa w/ du,u, v).
[u, (u, v)) == (u, (p)u) where W(w) == argminw
This map has the closed form,
((x) [f un
du(u, uuduup(u,o) + xla) [ duTTuulu.o))
and is weak" continuous as long as À > 0. Hence, our theorem states that it can be learned in context.
26


Reviews:
[{"review_id": "4C9CTZZqHZ", "reviewer": "Reviewer_5UVs", "summary": "The paper proves that transformers can universally approximate context-dependent mappings, $G(\\mathbf{x}; \\mu)$. They do this by showing that one-dimensional attention functions are dense in the one-dimensional context-dependent mappings. Separate proofs are provided for masked and unmasked attention.", "questions": "Only what I mentioned above.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "*Nice prior-work section, succinctly summarizes a very large literature. \n\n*The \"in-context mapping\" formulation is nice, not sure if it was used in prior theory but seems to apply to many IC learners like RNNs and SSMs and so on. \n\n*Feel like many of the techniques used could become useful theoretical constructions themselves (like the Laplace-like transform of Lemma 1)", "weaknesses": "Hard to think of any beyond those already acknowledged by the authors. If I were to reach for one, I feel like the result itself is maybe less interesting than the methods (which are very interesting), since being able to approximate any function often doesn't translate to being able to learn it (e.g. shallow networks, polynomial regression), and so it might be nice to spend some space in the intro or discussion highlighting what if any bearing this has on learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8t0h6tnxdy", "reviewer": "Reviewer_9RCC", "summary": "This paper examines Transformer's (unmasked and masked) ability to handle an unlimited number of context tokens. Contexts are modeled as probability distributions of tokens, with smoothness defined by continuity in Wasserstein distance. This paper shows that transformers can universally approximate continuous in-context mappings with fixed embedding dimensions and a constant number of heads.", "questions": "I don't have any specific question.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "I believe this paper provides a solid theoretical foundation for how a Transformer can model an infinite number of tokens, which supports the development of long-context language models. I find it especially surprising that a Transformer can handle an infinite number of tokens with a fixed embedding dimension.", "weaknesses": "I'm not sure if people actually use the unmasked variant discussed in this paper. For instance, bidirectional models like BERT and ViT must apply positional embeddings to their input tokens, meaning Eq. (2) isn’t typically used in practice. Therefore, I’d say the main contribution of this paper lies in its analysis of Eq. (3), which introduces additional regularity constraints on the token distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WbiQrn1kBH", "reviewer": "Reviewer_d9aW", "summary": "The paper considers the ability of transformers to approximate arbitrary in-context mappings, namely, their ability to transform an input set of token embeddings into an output set of embeddings arbitrarily close to a given target set, where each input token is transformed based on the context of the other input tokens. The input set is not limited to be a discrete finite set, but can be infinite or even continuous: in general it can be represented by a probability measure over the embedding space. A single transformer is able to obtain a given approximation level (aka precision), independently of the cardinality of the input set, which can even be infinite. The authors consider two settings: unmasked (aka non-causal, often used in vision applications) and masked (aka causal, often used in NLP), the masked setting requiring an extension of the approach used in the unmasked setting.", "questions": "1 (Question). Could you provide one or two concrete examples that would illustrate the potential applicability of the approach? Such examples would improve the accessibility of the paper to a wider audience.\n\n2 (Question). It is not fully clear to me why putting a probability measure over the input tokens is a natural move in the context of transformers. For instance, when considering a standard input of $n$ tokens, the usual representation is in terms of a set of cardinality $n$, and I am not quite sure why putting different weights over these tokens is an appropriate representation for modeling in-context mappings.\n\n3 (Remark). On line 289, you say \"Since our results are not quantitative, this is not a strong restriction.\" I had some difficulty making sense of this statement, starting with the unclarity of the term \"not quantitative\", which I finally understood to mean that you do not state bounds relative to $\\epsilon$, e.g. concerning the number of layers $L$ (which could be mentioned along with the number of MLP parameters).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "The paper explores in depth an interesting theoretical question about the in-context mapping abilities of the transformer architecture, namely its approximation abilities in presence of a context of arbitrary (even continuously infinite) cardinality.\n\nThe depth and rigour of the mathematical derivations appear (from the best judgment of a non-specialist, see also below) to be of very high quality.", "weaknesses": "The paper is extremely technical, and would require a considerable amount of time and effort, even by a mathematically inclined reader, to be fully understood. \n\nThe paper, as it stands, appears to be oriented towards a small number of readers, already familiar with the technical literature relating to measure-theoretic views of the approximation properties of transformers. Its appeal could be made broader by: (1) motivating the approach by potential (even non-immediate) applications and (2) by providing graphical illustrations of some of the underlying mathematical concepts, to help intuition (the current version of the paper does not provide a single illustration).\n\nAs the authors acknowledge, their results \"are not quantitative\", meaning (if I understand correctly), that a number of important parameters of the transformer architecture, such as the number of layers, are not bounded in terms of the approximation precision $\\epsilon$. As they admit, this is a serious obstacle relative to applications. However, on the positive side, their current results provide some welcome clarification of the theoretical landscape. \n\nThe title \"Transformers are Universal In-Context Learners\" could be misleading to many readers, as it may seem to address the well-known question about the \"ICL (In-Context Learning)\" abilities of transformers, for example, the abilities of *fixed* LLMs, when provided with a \"few-shot prompt of examples\", to appear to \"learn\" to reproduce the \"intention\" expressed by the examples. In the current paper, the goal appears to be of a rather different nature, having to do with *finding* a transformer architecture and its parameters to approximate a given target contextual embedding. It would be useful if the authors could clarify whether they see a connection between their work and the usual notion of ICL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)