A unified framework for establishing the universal approximation of transformer-type architectures
Authors: Jingpu Cheng
Ting Lin
Zuowei Shen
Qianxiao Li
Venue: NeurIPS 2025 poster ()
Keywords: transformers
approximation theory
equivariance
Primary area: theory

Abstract: We investigate the universal approximation property (UAP) of transformer-type architectures, providing a unified theoretical framework that extends prior results on residual networks to models incorporating attention mechanisms. Our work identifies token distinguishability as a fundamental requirement for UAP and introduces a general sufficient condition that applies to a broad class of architectures. Leveraging an analyticity assumption on the attention layer, we can significantly simplify the verification of this condition, providing a non-constructive approach in establishing UAP for such architectures. We demonstrate the applicability of our framework by proving UAP for transformers with various attention mechanisms, including kernel-based and sparse ones. The corollaries of our results either generalize prior works or establish UAP for architectures not previously covered. Furthermore, our framework offers a principled foundation for designing novel transformer architectures with inherent UAP guarantees, including those with specific functional symmetries. We propose examples to illustrate these insights.

A unified framework for establishing the universal approximation of transformer-type architectures
Jingpu Cheng
Ting Lin
Department of Mathematics National University of Singapore chengj ingpudu. mus edu
School of Mathematical Sciences
Peking University lintinnge intingsms@pku edu
Zuowei Shen Department of Mathematics National University of Singapore matzuowsOnus edu. sg
Qianxiao Li
Department Mathematics Institute for Functional Intelligent Materials
National University of Singapore qi qianxiao@nus edu. sg
Abstract
We investigate the universal approximation property (UAP) transformer-type architectures, providing unified theoretical framework that extends prior results on residual networks to models incorporating attention mechanisms. Our work identifies token distinguishability introduces general sufficient condition that applies to a broad class of architectures. Leveraging an analyticity assumption the attention layer, simplify the verification of this condition, providing a non-constructive approach in establishing UAP for such architectures. We demonstrate the applicability of our framework by proving UAP for transformers with various attention mechanisms, including kernel-based and sparse ones. The corollaries of our results either generalize prior works or establish UAP for architectures not previously covered. Furthermore, our framework offers a principled foundation for designing novel transformer architectures with inherent UAP guarantees, including those with specific functional symmetries. We propose examples illustrate these insights.
fundamental requirement for UAP and
significantly
Introduction
Transformers [66]
family of deep learning architectures that have achieved remarkable perfor- mance natural language processing [5] 58), computer vision [6]. and other fields [36]. Given input sequence of tokens, transformer processes through deep composition of alternating attention and token-wise feedforward layers. Besides the original softmax attention [66], a variety
of different attention mechanisms have been proposed enhance performance computational
efficiency, such as kernel-based attention [ 12 38 65
sparse attention
3 40 76], and attention
with low-rank structures [68] 821.
natural theoretical question is: What is the expressive power of these architectures? Previous studies have shown that transformers achieve the universal approximation property (UAP) via architecture- specific constructions, meaning they can approximate any continuous sequence-tor seguencceto-sequenee se-quunece function over compact domains 75 76) in certain measures. However, these results heavily rely explicit, wechteeture-specifie constructions, and a unified theoretical framework of deep transformer-tyn architectures remains elusive. In particular, is highly desirable to derive verifiable condition that guarantees UAP of deep transformer-type architectures, independent specific architectural details
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

such as the choice of the attention mechanism. Such framework would allow greater flexibility in design without sacrificing expressivity.
Similar concerns have been addressed for fully connected deep residual networks (ResNets) using insights from control theory and dynamical systems [10
By interpreting ResNets as control systems, recent studies [10] 44] showed that deep ResNets with Lipschitz nonlinear activation functions possess UAP. However, extending this approach transformers presents a challenge. Unlike ResNets, transformers apply identical feedforward transformations across tokens, without direct inter-token interactions. Hence, the attention mechanism must effectively capture token dependencies and propagate contextual information throughout the network.
44
62
63
To extend the UAP framework from ResNets to transformers, model each transformer block through two sequential operation [
X X2 + Atten(X.), X1+1 x++4=1++ FF)(
where X₂ E Rdxx represents n tokens each of dimension d. The feedforward network (FFN) acts independently on each token, while the attention layer (Atten) explicitly models dependencies across tokens. A transformer model is then defined as the composition of such blocks. In many practical architectures, the attention layer is computed by some interactions between tokens, which has computational complexity up to O(n²d) d)), while the feedforward layer has computation complexity of (ndf). This structure reduces computational complexity from (n? (for using network with dense layers) to (nd((n + d)) (can be even lower in many variants) by decomposing approximation tasks into simpler boken-wise and token-mixing components. Such a decomposition not only enhances computational efficiency but also provides novel perspective in the context of approximation theory. Therefore, it is of theoretical interest to understand how the combination of the token-wise and token-mixing operations contributes to the expressive power of models in handling sequential data.
In this paper, we develop general framework for the UAP analysis of transformers. Specifically, we provide abstract and verifiable conditions ensuring UAP, independent of specific architectural details. Our key contributions include:
We derive a general sufficient condition for transformer models to achieve UAP in the IP sense over compact sets (Theorem D. requiring: (1) feedforward layers satisfying the conditions [10), as stated in Definition 2, and (2) attention mechanisms producing distinct context-aware token representations across different inputs. Notably, our framework incorporates potential symmetry under token permutations in transformers, extending the analysis non-transitive permutation groups beyond (45)
For attention mechanisms that are analytic to their parameters, we reduce UAP verification to a two-sampp wwo-samll condition (Theorem 2. simplifying practical validation compared to con- structive approaches [37 74 76. Moreover, we show conditions under which transformers with a fixed number of attention layers but arbitrarily many feedforward layers achieve UAP, generalizing the results on the memorization capability of transformers (37 (3).
We apply our general framework to various transformer architectures to demonstrate its generality and applicability, including kernel-based [12 65 (6). sparse 3 40 76). and some other attention mechanisms [9] 68). For kernel-based attention (formulated in Section 4.1). our result (Corollary [ provides UAP guarantee for many existing architectures previous works 12
65 66 and also for new architectures. For sparse attention (e.g., architectures
proposed in 3 40 76)). ), our result (Corollary 2 provides a UAP criterion which generalizes beyond the softmax attention and is free from technical assumptions the sparse pattern.
Our theoretical results also enable principled design of MAP-guaranteed architectures. We demonstrate this by proposing new transformer architectures with UAP guarantees, especially for attention mechanisms that preserve specific functional symmetry(Section 4.4).
We discuss in detail after our main results how they relate to the rest of the literature, and collect more detailed review of related work in Section
'erre omit the layer normalization for simplicity of the analysis.

---

2 Problem formulation
In this section, we introduce the transformer-lype architecture, an abstraction of the standard trans- former [66] family of architectures composed of two repeating components: the token-mixing layers and token-wise map layers. Then, we define the universal approximation property (UAP). Notably, introduce the UAP under permutation equivariance for any subgroup G' of the symmetric group S,, over tokens, which a more general framework.
In the following, we use X = [[x],,,... [x],) E R to denote one data sample consisting of n tokens 1X],,... ... [x] of dimension d. We say that X is general position if all of its tokens are distinct. We will also use the notation [n)] = (1.....0) n.
for any positive integer n.
2.1 Transformer architecture
We present general formulation for the two-step architecture of transformers as described in (T. The mapping X, X++1 can be abstracted (Id +h) (g) Here, 9 generalizes the attention map Atten to a general token-mixing map, while h generalizes the token-wise feedforward map FFN, which applies X Ædxn as:
(X)= = (h((x)), M(X])), where h IRd + Rd
We denote by 9 a token-mixing family, consisting of functions mapping Rdxa to Rdxa, to represent all possible choices of in a transformer. Recall that the attention layer in the original transformer [66] is given by
Atten(X, Σ we' X, softmax (wwk X,) T x.).
with trainable parameters Whi W w Raxd for the i-th head in block and the softmax is applied column-wise, In this case, G is precisely the family of functions defined by (3) for all possible choices of W Who Who
Moreover, we consider
H. = (X + (f((X)))...,
h 70,
(4)
where H is family of maps from Rd to Rd, the function family for the token-wiss feedforward map h transformer. We define a transformer block, the generalization of (T). to be a map in
Fg. = ((Td +h) o (Id +g) I g E GG h E HS").
A transformer identified by G and H is then the composition of such blocks, i.e. a map in the set:
To. == {F, o ... o F1 n E, F, Fg.H)
Notably, the feedforward layer can represent only tensor-type functions, i.e. functions of the form ( The token-mixing mechanism extends this capability to general functions by capturing the dependencies between tokens.
2.2 Universal approximation under permutation equivariance
Let S,, denote the symmetric group on n elements and let G S S, be a subgroup. Then, has natural group action over dxn by permuting the d-dimensional tokens. A function f Rddx kdxn is said to G-equivariant if
= ( (X(x)) Vo X ERdd
The original transformer and many of its variants have some degree of permutation equivariance over tokens. For instance, kernel-based token mixers 112 66) typically have G S,, whereas sliding- window attention 3 employs binary group (identity and reflection). and some architectures [68 76) do not enforce any equivariance (i.e. (Td)). If G consists of only G-equivariant functions, then Tg h can approximate only G-equivariant target functions. This motivates the following definition:

---

Definition 1 (G-UAP). The transformer-type model with hypothesis space Tg. is said to have the G-universal approximation property (G-UAP) the L" sense (1 S p oc) if. for every continuous G-equivariant function F Rkdxn - R every compact set K C [Rdx,, and every >> 0, there
exists F E TTH such that
|| - FllE(())) SE
(8)
In applications, the equivariance restriction on the transformer is often addressed by introducing positional encoding [66] on tokens. From theoretical perspective, previous works [34 37 74 75 have shown that if a family T has G-UAP for some G. then for any given compact set K, there exists an absolute positional encoding Enc X X + E, where E is fixed matrix, such that
To.x a Enc == {F a Enc F E
(9)
can approximate any continuous function on K in the L sense without symmetry constraints. Technically, this can done by making the domains of each token position distinet. On the other hand, there are also applications where exact symmetry needs to be enforced, such structure-to- property prediction crystals 8 35, 60 71). Therefore, it is sufficient to consider the G-UAP, which can naturally extend to the general UAP while also covering cases where symmetry is considered. We will hereafter focus on the G-UAP.
In the literature, several works have studied the universal approximation of symmetric functions [3
19 45 73
often focusing on specific architectures and symmetric groups. Notably, 45 provides general sufficient condition for the action of any transitive subgroup of S, on coordinates (1- dimensional tokens). In comparison, this work considers approximation under symmetry in general setting, with group action over d-dimensional tokens instead of coordinates. Additionally, our results apply to non-transitive group cases, which are not covered in [45]. In [i, the authors studied the ensemble controllability of control systems under symmetry, showing that systems that can interpolate arbitrarily many samples under symmetry are generic in a topology sense. However, this result does not tell us whether not given architecture has controllability. In comparison, our target is to provide a verifiable sufficient condition for UAP of specific architectures.
Our analysis focuses on fixed-length sequence to ro-seeue maps compact subsets. This setting directly covers encoder-style tasks and many architectural variants, which underlies many practical applications ranging from automatic speech recognition and visual sequence modeling to struc- ture-property prediction in molecules and crystals 26
35 36 58, g1 In parallel, there are also
reeasue--theoreti formulations in the literature that treat inputs as probability measures, which can handle variable or even infinite context length under continuity/regulaiiy assumptions (2] offering complementary insights to our results.
3
Main results
In this section, we establish general sufficient condition for the UAP of transformer-type architec- tures. Since transformer architectures consist of token-wise feedforward layers and token-mixing attention layers, we first provide conditions for each component required for UAP.
For the feedforward family H we introduce the following definition:
Definition 2 (Nonlinearity and affine-invrrianee for H). We say a fanction family H (consisting of functions from idd to IRd) is nonlinear and affine-invariaa if
For any E and any W, A E Rdxd E Rd, the function Wh(A- also belongs to H;
contains at least one non-affine finncintt.
The nonlinearity and independent of specific choices of activation functions and the width of the network. When 2 2, according to the main result in [10], this condition ensures that the family
condition holds for almost all practical feedforward layers,
he (Id +H)) ((Td + hm)) ... (Id +h1) hi,..., Am E H}
(10)
i Notice that in Definition] | we do not require To.H h to consist of only G-equivariant maps, but only that it approximate Geeqiivariant functions.

---

can approximate any continuous function f: I + R in L" sense over compact set. Therefore, this condition guarantees that only the wisen-wise feedforward layer is able to generate complex features over single token.
However, inherent limitation the expressive power of feedforward layers is that they operate token-wise, meaning that they do not model any interactions between tokens. Considering this, we introduce the following definition for the attention family G:
Definition 3 (Token distinguishability for G). For given group G S. Sn and set of samples D == { C Rdx= that are all in general position, we say a token-mixing family g can distinguish tokens in D using layers under G-action, if there exists
9 E (Td - = {(Td +ym) o ..... (Td +g)) 91,.... Im E [G}
(11)
such that for any distinct j E [N] with X; and x, belonging to different orbits under the G-action (i.e., X, + (Xx)) for all a E G), the tokens of g g(X;) and g(X;) are all distinct.
Moreover, we say 9 satisfies the token distinguishabiliyy condition under G-uction, if for any finite sei D, there exists such that G can distinguish tokens in D using v layers under G-uclion.
The token distinguishability condition ensures that token-mixing layers can model interactions between tokens by generating unique outputs for tokens in finite set (up G-action), enabling distinct context information for each token. This property is crucial for the expressive power of transformers, illustrated below.
Consider a scenario where the token distinguishability condition fails: there exists a set S E RRxx with positive Lebesgue measure and some i E [ra] such that [x()]; is constant over Ω for any g E (Id +g)" Consequently, any F E Ty. also constant over Ω2 leading to the failure of UAP. This example shows that if too many tokens are indistinguishable by the token-mixing mechanism (e.g., from positive measure set), the transformer's expressive power becomes limited.
On the other hand, the token distinguishability condition is relatively mild. as it only demands the composition of loken-mixing layers distinguish tokens, rather than enforcing any precise relation. This condition is generally easy to satisfy, provided G includes sufficiently diverse maps that can effectively mix tokens.
In the following, we assume that 2 2 and the zero map is in g. Based on Definitions 2 and 3 can state our first main result on the UAP of transformers:
we
Theorem 1. Suppose that H is nonlinear and affine-invarian Definition 2 and & satisfies the token distinguishability condition Definition 3 Then, the family of transformers Tg. satisfies the G- G-UAP Definition
Theorem D provides a general condition for the UAP of transformers. However, directly verifying the token distinguishability condition is challenging since we need to check the condition arbitrarily many times. Therefore, we propose the following theorem, which greatly simplifies the procedure.
Theorem 2. We assume that G is parametrized by G (X ((; 0 E e RT),, where θ is connected open subset of R"", and any fixed X, the mapping @ + 9(X; 8) is analytic. Then, if G can distinguish tokens of any dataset D with two elements (Definition 3 using finite many layers, then G satisfies the token distinguishability condition.
Moreover, if there exists uniform m. such that with m layers, G can distinguish tokens of dataset D with D) = 2, then it can also do it for any finite dataset D using m layers. In this case, deep model using only m token-mixing layers and sufficiently many feedforward layers can achieve the UAP.
The key insight in the proof of Theorem is that if token distinguishability fails over finite set, can derive an equation in θ that is Identically zero. By leveraging the property that the zero set of non-trivial analytic function has measure zero, the equation can be reduced to the case of two elements, as detailed in Section B.2 The use of the analytic property is straightforward but significantly simplifies the token distinguishability condition.
Given expressive enough feedforward layers, Theorem Saanreem[hghe Thighlights the role of token-mixing mecha- nisms in transformer architectures for UAP: generating distinct, context-aware token representations. This aligns with prior works 37 75 76), which introduced "contextual mapping" to establish UAP
for transformers. For instance, 37 defines "contextual mapping" as function distinguishing tokens
5

---

in dataset D (similar to in Definition 3) without group actions. However, these works rely on explicit constructions, making verification complex and less generalizable. In contrast, Theorem D the first to our knowledge that formulates token distinguishability and feedforward layer conditions as a general, non-constructive criterion for UAP. There is no need to explicitly construct for UAP once the conditions are verified. Additionally, Theorem 2 significantly simplifies the construction based verification of token distinguishabilit, enabling broader applicability to diverse attention mechanisms, as shown in the examples in Section 4 Furthermore, the uniformity of m in Theorem alss provides a convenient approach on the memorization capacity attention layers studied [37].
Applications practical architectures
We demonstrate the generality and applicability of our UAP results by applying them to practical transformer architectures. We first follow the kernel-based framework from [6]], which provides unified description for series of attention mechanisms. Specifically, many attention variants proposed in prior work can be formulated as
[Atten(X)]: EjENiO &( (. ( (w
Wo. WK. Wy Raddd
(12)
ΣjEN() k(WQ (W xI,
where A Fd x Fd - R+ is positive kernel function, and M(t)) [n]] denotes the set of indices that the i-th token attends to. In the original transformer, the kernel function is defined as k(x, exp(x* y). and (ii [n)]
Under this framework, many transformer variants can be categorized into two types, which we will apply our results::
Kernel modification: Replacing the kernel function & improve efficiency performance. For example, using a kernel of the form k(x, y) = x(x) ((v) with feature map Φ Rd R can significantly reduce computational cost when
n.
Sparse attention: For each i, restricting M(i)) to a subset of [n]. reducing the number of tokens each token attends to. Here, we discuss in a general sense where Mii can be dynamic across different layers, such as the sparse pattern in 40 76)
4.1 Kernel-hased attention
We first consider the kernel modification case, where assume Miii [n] for all The following result follows from Theorem Corollary 1. Suppose the kernel function function k satisfies the following conditions:
k(.--) 12d R2d + IR is an analytic function.
For any x E TRd (0) and distinct points yı, y2 E RRdd (0), for almost all WK Rd the following holds:
lr( (WKy). or 00.
lim 1-00 k( (Wky2)
(13)
That is, for almost all given W WK. the kernel function i can distinguish token representations by scaling the key vectors with a large factor.
Then, a transformer with ternel-based attention famniiy G and feedforward family H. satisfying the D possesses the S,-UAP. Moreover, using only one token aaken-nixing layer and
conditions in Theorem sufficiently many feedforward layers can achieve the UAP.
Corollary D ensures the distinguishability condition in Theorem throuuhh the limiting behavior of the kernel function. This generalizes the idea from 74 75). where softmax was used as an approximation of hardmax in explicit constructions. In comparison, our approach leverages analyticity, allowing the limit behavior directly establish the distinguishability condition without further constructions.
Consequently, this result applies to various existing attention mechanisms. In particular, the following kernels directly satisfy the condition in Corollary
means that the condition holds all the whole space except for measure zero set.

---

k(z, v) exp(x" v). used in the original transformer.
k(x, v) - exp(->lle vlاi) for 7 > O, the RBF kernel, explored in 65
k(x,v) -b(x) (v)), where
o(x)² cxp
[211)))) (exp(w) ....... exp(w,n.) Rm
(14)
with Wi.... Wm R being fixed weights drawn i.i.d from a Gaussian distribution. This kernel is used in Performer [12] where Theorem holds almost surely.
Among these, the UAP for the original transformer and Performer have already been shown 74 Our result recovers these results our framework and relaxes the requirement on the architecture to achieve UAP: for original transformer, we do not need the bias in query vectors as in [74]; for Performer, we do need additional hidden dimensions as in 22. To the best of our knowledge, the UAP for RBF kernel attention is new, demonstrating the generality of our approach. Moreover, we can easily propose other kernels satisfying the condition in Theorem but have not been studied in the literature, such as the following forms of k(æ, y)
k(z, v) exp(w" T c y)) for some E Rd (0);
k(x, y) p(a - y) [ar, y), with p being any positive polynomial function and k being any kernel mentioned above.
Corollary [ also generalizes the results in 37 on the memory capacity of transformers, where they prove that for transformers with dense softmax attention, one layer of attention is sufficient to achieve the UAP. Our result extends this to a broader class of kernel-based attention mechanisms.
4.2 Sparse attention
Prior works proposed sparse attention mechanisms to reduce the computational complexity of attention blocks 3 IT
15 24 40, 76). A common intuition for designing sparse patterns while retaining expressivity is ensuring connectivity, i.e., each token attend to others via multiple "hops." For instance, in sliding window attention (3). where N(i)= = (j E [n] li - il S w) with n, long-range interactions we formalize this intuition and provide a general UAP condition for sparse attention transformers as direct consequence of Theorem I
achieved indirectly via multiple attention layers. In the following,
Denote P([il) as the power set of [m], i.e. the set of subsets of [n]. For given function N : [n] P((n), we define 9N as the family of maps from Rdxn Rdxa defined by (12) associated with the sparsity pattern N. We define the adjacency matrix of N as an n x n matrix Ax with (i, = if j E (i) and ji, otherwise.
We also define
Aut(N) = fo e SN (jE a(j) e N(o(i))
(15)
as the permutations that keep the structure of N invariant.
Let := (N,,2,, .......) be a sequence of sparsity patterns. We define the sparse transformer family associated with + as:
Tot
(od.::.....d/ii//a/eee.. (ld+h))))(d+gg)) n N4, E Hm g. E GN., for i E [n]].
(16)
Such definition formulates transformers with dynamic sparse attention patterns.
Definition 4. We call the sparsity pattern & to be connected within layers, for any i i [n]. there exists a sequence Ti < T2 < Ts S m such that
AN AN.... ... ..., (i. >
(17)
That is, any token can reach any other token through a subsequence of the m sparse attention layers.
Also, let be a family of tosen-wise feedforward layers satisfying the condition in Theorem and A be kemel function satisfying the condition in Corollary I Then, have the following result:
7

---

Corollary 2. Suppose that 4 is connected within m layers. Then. T possesses the G-UAP, where
G = Aut(NG)
(18)
Moreover, transformer with only layers of attention associated with the sparsity patterns Ni, ... .Nm in and sufficient number of token-wise feedsfoowrw layers can achieve the UAP.
Corollary Corollary[proot provides a rigorous justification that the heuristic in keeping connectivity the attention layers is also sufficient for UAP. Results from graph theory indicate that when is large, a random sparse pattern N has trivial automorphism group with probability approaching [7.. This fact indicates that with the guarantee of connectivity, most of the sparse attention patterns allow the UAP without symmetric restriction even in the absence positional encodings.
Corollary can cover many existing sparse attention mechanisms, including the following:
the periodic pattern switching between "fixed attention" and "strided attention" in
the sliding window attention with/without global seeds (tokens connect to all others) in
the star-shape attention in [24] where one token attends to all others and the others connect in a circle;
BigBird, mixture sliding windows, global seeds and random connections in 76
The UAP of transformers with sparse softmax attention have also been studied in 75 76 via constructive approach. Compared to their results, Corollary - has several advantages. First, our results for UAP do not require other technical conditions, such as the periodicity of the sparse patterns and the existence of Hamiltonian path in [7]. or each sparse pattern contains a star sub-structure in [76), other than the connectivity of the graph. For example, if the connection mode & is not periodic (e.g. there are different random patterns across layers), and some of the NG do not contain star graph mode, our result still be applied as long as the connectivity is kept, while the results in [75] (66 may not be applicable.
In addition, results can be applied all kernels that satisfy the condition in Corollary [ which generalizes the results based on explicit construction using softmax attention. Moreover, we identify the number of token-mixing layers required to achieve UAP the minimal number of "hops" for each token to attend to all other tokens. In contrast, the results in 75 76 use unbounded number of layers achieve UAP. In this regard, our result also be viewed generalization of the results on the minimal number of attention layers for UAP in [37 to sparse transformers.
4.3 Other attention mechanisms
Our framework can also be conveniently applied to many other variants of attention mechanisms that cannot be covered by (2). For example, the token distinguishability condition can be verified for the following architectures using similar method as Corollary 1
Linformer
68
where the attention layer is defined
Atten (X) = X (o Wxxx),
(19)
where E, F E Rank with < < n are two trainable projection matrices. This variant of attention reduces the complexity of attention from O(n") to O(nk).
Kernelized attention used in SkyFormer
9 where the attention mechanism given by:
(-11
[Atten(X]) (X)en(X))==
Σ exp
-ooVoXX]-Wxx]]jjap (1xX1111 Wv
(20)
j=1
Corollary 3. We have that: (i) LinFormer satisfies the UAP without symmetric restriction; (ii) SkyFormer satisfies the SAPU
The proofs are provided in Section C.4 using Theorem 2 similar to the proof of Corollary

---

4.4 New attention mechanisms from the approximation analysis
Our results also provide insights into designing new transformer architectures with inherent UAP guarantees. In particular, our framework inspires the design of architectures with UAP under specific symmetries. this section, we present examples of such designs to illustrate these insights.
4.4.1 New attention mechanism with bias term
We propose architecture that naturally satisfies the conditions in Theorem | and Corollary We consider the following attention mechanism with bias term:
2
[Atten(X)) [X]s +
aa(W[X]] b). JEN(()
Σ
(21)
where a E R, W E Ie and b E R are learnable parameters. Assume that a is of polynomial growth, i.c. there exists M and N such that [a(x)] x M [x)*))
for all x R.
Then, the result in Corollary 2 still holds, if we replace attention mechanism See Section C.4.3 for the formal statement and proof.
with
4.4.2 Transformer with UAP under specifie symmetry
In many applications, architectures with specific symmetric restrictions are required. Our framework also offers a new perspective on designing such architectures with UAP guarantees. For given permutation group G S. S., we can design G-equivariant loken-mixing layers that satisfy token distinguishability under G-action. By Theorem [ transformer with such token-mixing layers and feedforward family H. with nonlinearity and athine invariance achieves G-UAP. This simplifies the design process, as only token distinguishability is required for the token-mixing layer.
For some subgroups G of Sn, the design for token-mixing layers can be very simple. Here, we use the example of G D., the dihedral group of order 2n, and the cyclic group C,, of order n to demonstrate. We identify Dn < Sn as the group generated by the cycle == (1,2.--- n) and the (1, n2) 1) ...... C, is the eyclic group generated by p. D,, corresponds the
reflection
symmetry of a regular re-gon, relevant in applications like molecular structure [6] 23 41. Symmetry
under Cn applies modeling periodic data, such as periodic time series 18 27 and classifying
periodic variable stars in cosmology [80].
For D,,, provide the designs of token ooken-mixing layers with token distinguishabilitty.
Architecture with Da-symmetry Choose the token-mixing layers defined 12 or in 21 with the sparsity pattern
N(1 {(t + mod | =- ,,, ,,.,..,,,, .w.
(22)
where < للد in (2I) satisfy the conditions in Corollaries and respectively.
is integer. Here, we assume that the kernel &s in 12 and the function
For Cn, similar designs as above also work. However, we can use simpler one based on convolution:
Architecture with C -a-symmetry: Define the token-mixing layer via column- convolution:
Atten(X] X) = 1b * X, where (W) + X]:
vb (X](et) mod no i= 0, 1,
n 1. (23)
with trainable kernel vb = [vo. ... v5] E IR++1 for some integer 2 1.
This design can be viewed an adaptation of the temporal convolutional network [33 43 treating the input sequence as a circular structure. The following statement holds, with proof in Section C.4.3
Corollary The architecture with D Dn-symmmetry and Cn-symmetry defined above satisfies the token distinguishabilit condition under the action of D,, and Cn, respectively. Moreover, the transformer with such token- leiin mechanisms and a non-linear affine-invarian family H possesses the DU,UAP or C,, UAP, respectively.

---

Architectures incorporating symmetry through convolutional layers have been studied in the literature
70 80]. In particular, [80 also proposed a convolutional structure for representing -n-invariant functions, although it does not inherently guarantee UAP. In contrast, our proposed architecture naturally satisfies the C.PUAP property according to Theorem Moreover, by choosing specific sparse mode N,, we can generalize the architecture for D, symmetry to other permutation subgroups of Sn, that can be identified as the automorphism group of an order-n directed graph. For more general permutation groups, our framework can still be applied if one can find token-mixing layer satisfying the token distinguishability condition under the action the group. The method proposed in [31 61] may be helpful in identifying such layers. We believe our framework provides new perspective on the design of equivariant/nvvaiint architectures with UAP guarantees.
[3
14
46
5
Conclusion
In this paper, we investigate the universal approximation property (UAP) of general transformer architectures within unified framework. Our main results, Theorem [ and Theorem 2 provide general and verifiable conditions for establishing UAP across a range of attention-basee architectures, avoiding complex constructions as in previous works. This generality is demonstrated in Section 4 where we apply our framework to various attention types. Moreover, our results offer guidance for designing new attention mechanisms with UAP guarantees, as illustrated in Section [4.4 We also
acknowledge certain limitations of this work. First, normalization layers commonly used in practice are not considered, and extending our analysis to incorporate them would be valuable. Second, some architectures, such as those in 388. do not satisfy the analyticity assumption in Theorem P Although the condition in Theorem D remains verifiable for such architectures, it remains unclear whether our
our results on the required number of token-mixing layers for UAP still hold. Moreover, results offer con-tonstrecttve yet verifiable criteria for Jbs-absttactinn away the specific forms of eaken-mixing and loken-wise modules- they do not yield quantitative insight into the relative contributions of each architectural component. A systematic, quantitative characterization of how individual mechanisms (e.g., multi-heas head attention, mixture-offexpeer low-rank projections) affect approximation efficiency remains an important direction for future work.
References
[1] Andrei Agrachev and Cyril Letrouit. Generic controllability of equivariant systems and ap- plications to particle systems and neural networks. Annales de I'Institut Henri Poincaré C, 2025.
[2] Silas Alberti, Niclas Dem, Laura Thesing, and Gitta Kutyniok. Sumformer: Universal approxi- mation for efficient transformers. In Topological, Algebraic and Geometric Learning Workshops 2023, pages 72-86. PMLR, 2023.
[3] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-documen transformer. arXiv preprint arXiv:2004.05110, 2020.
[4] Norman Biggs. Algebraic graph theory. Number 67. Cambridge university press, 1993.
[5] 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.
[6] Philip R Bunker and Per Jensen. Molecular symmetry and spectroscopy, volume 46853. NRC research press, 2006.
[7] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European conference on computer vision, pages 213-229. Springer, 2020.
[8] Chi Chen, Weike Ye, Yunxing Zuo, Chen Zheng, and Shyue Ping Ong- Graph networks as a universal machine learning framework for molecules and crystals. Chemistry of Materials, 3 31(9):3564-3777 2019.
10

---

[9] Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian kernel and nystr\" " om method. Advances Neural Information Processing Systems, 34:2122- 2135, 2021.
[10] Jingpu Cheng, Qianxiao Li, Ting Lin, and Zuowei Shen. Interpolation, approximation, and controllability of deep neural networks. SIAM Journal Control and Optimization, 63(1):625- 649, 2025.
[11] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509 2019.
[12] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint 249. 2020.
[13] Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference machine learning, pages 2999.2999. PMLR, 2016.
[14] Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical cnns. arXiv preprint 180i 10130, 2018.
[15] Gonçalo M Correia, Vlad Niculae, and André FT Martins. Adaptively sparse transformers. arXiv preprint arXiv: 19990000155 2019.
[16] Alexey Dosovitskiy. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929 2020.
[17] Paul Erdos and Alfréd Rényi. Asymmetric graphs. Acta Math. Acad. Sci. Hungar, 14(295- 315):3, 1963.
[18] Wei Fan, Shun Zheng, Xiaohan Yi, Wei Cao, Yanjie Fu, Jiang Bian, and Yan Liu. Depts: Deep expansion learning for periodic time series forecasting. arXiv preprint arXiv:2203.0763 2022.
[19] Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convolutional neural networks for equivariance to lie groups arbitrary continuous data. In International Conference on Machine Learning, pages 3165-3176. PMLR, 2020.
[20] Takashi Furuya, Maarten V de Hoop, and Gabriel Peyré. Transformers are universal in-context learners. arXiv preprint arXiv:2408.01 06378 2024.
[21] Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. A mathematical perspective on transformers. Bulletin of the American Mathematical Society, 62(3):427-479, 2025.
[22] Borjan Geshkovski, Philippe Rigollet, and Domènec Ruiz-Balet. Measure-to-meeaurre interpola- tion using transformers. arXiv preprint arXiv:2411.0455// 2024.
[23] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
[24] Qipeng Guo, Xipeng Qiu, Pengfei Liu, Yunfan Shao. Xiangyang Xue, and Zheng Zhang. tta-ttransfommrr. arXiv preprint 1rX:v:1902.09113 2019.
[25] Siddhant Haldar, Zhuoran Peng, and Lerrel Pinto. Baku: An efficient transformer for multi-tasi policy learning. Advances in Neural Information Processing Systems, 1111441208-4122333 2024.
[26] Ali Hatamizadeh, Yucheng Tang, Vishwesh Nath, Dong Yang, Andriy Myronenko, Bennett Landman, Holger R Roth, and Daguang Xu. Unetr: Transformers for 3d medical image segmentation. Proceedings of the IEEF/CVF winter conference on applications of computer vision, pages 574-584, 2022.

---

[27] Zhixiang He, Chi- Yin Chow, and Jia-Dong Zhang. Stenn: A spatio-temporal convolutional neural network for long-term traffic prediction. In 2019 20th IEEE international conference on mobile data management (MDM), pages 226-233. IEEE, 2019.
[28] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. JCLR, 1(2):3, 2022.
[29] Jerry Yao-Chieh Hu, Hude Liu, Hong- Yu Chen, Weimin Wu, and Han Liu. Universal approxi- mation with softmax attention. arXiv preprint arXiv:2504. 159566 2025.
[30] Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, and Han Liu. Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency. In ICLR 2025 Workshop on Deep Generative Model in Machine Learning: Theory, Principle and Efficacy.
[31] Michael J Hutchinson, Charline Le Lan, Sheheryar Zaidi, Emilien Dupont, Yee Whye Teh, and Hyunjik Kim. Lietransformer: Equivariant self-attention for lie groups. In International Conference Machine Learning, pages 4533 4543. PMLR, 2021.
[32] Menglin Jia, Luming Tang, Bor-Chun Chen, Claire Cardie, Serge Belongie, Bharath Hariharan, and Ser-Nam Lim. Visual prompt tuning. In European conference on computer vision, pages 709-727. Springer, 2022.
[33] Haotian Jiang and Qianxiao Li. Forward and inverse approximation theory for linear temporal convolutional networks. In International Conference on Geometric Science of Information, pages 342-350. Springer, 2023.
[34] Haotian Jiang and Qianxiao Li. Approximation rate of the transformer architecture for sequence modeling. Advances in Neural Information Processing Systems, 37:68926-68955, 2024.
[35] Rui Jiao, Wenbing Huang, Peijia Lin, Jiaqi Han, Pin Chen, Yutong Lu, and Yang Liu. Crystal structure prediction by joint equivariant diffusion. Advances in Neural Information Processing Systems, 36: 36:17444-17497 2023.
[36] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. nature, 5967783)))88888-888)) 2021.
[37] Tokio Kajitsuka and Issei Sato. Are transformers with one layer self-attention using low-rank weight matrices universal approximators? In The Twelfth International Conference on Learning Representations.
[38] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns:: Fast autoregressive transformers with linear attention. In International conference on machine learning, pages 5156-518 5165, PMLR, 2020.
[39] Junghwan Kim, Michelle Kim, and Barzan Mozafari. Provable memorization capacity of transformers. In The Eleventh International Conference on Learning Representations, 2022.
[40] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: arXiv preprint 00t-:0000.0441,,
The efficient transformer.
[41] Charles Kittel and Paul McEuen. Introduction to solid state physics. John Wiley & Sons, 2018.
[42] Anastasis Kratsios, Behnoosh Zamanlooy, Tianlin Liu, and Ivan Dokmanić. Universal ap- proximation under constraints is possible with transformers. arXiv preprint arXiv:21 2021.
[43] Colin Lea, Rene Vidal, Austin Reiter, and Gregory D Hager. Temporal convolutional networks: A unified approach to action segmentation. In Computer vision-ECCV 2016 workshops: Amsterdam, the Netherlands, October 8- 10 and 15-16, 2016, proceedings, part III 14, pages 47-54. Springer, 2016.
12

---

[44] Qianxiao Li, Ting Lin, and Zuowei Shen. Deep learning via dynamical systems: An ap- proximation perspective. Journal of the European Mathematical Society, 25()):667-11799 2022.
[45] Qianxiao Li, Ting Lin, and Zuowei Shen. Deep neural network approximation of invariant functions through dynamical systems. Journal of Machine Learning Research, 25(278):1-57, 2024.
[46] Ting Lin, Zuowei Shen, and Qianxiao Li. On the universal approximation property of deep fully convolutional neural networks. arXiv preprint arXiv:221 |4047, 2022.
[47] Hao Liu and Pieter Abbeel. Blockwise parallel transformers for large context models. Advances in neural information processing systems, 36:8828-888 8844, 2023.
[48] Hude Liu, Jerry Yao-Chieh Hu, Zhao Song, and Han Liu. Attention mechanism, max-affine partition, and universal approximation. arXiv preprint arXiv:2504. 19901, 2025.
[49] Shih- Yang Liu, Chien-Yi Yi Wang. Hongxu Yin, Pavlo Molchanov, Yu-Chiang Frank Wang. Kwang- Ting Cheng, and Min-Hung Chen. Dora: Weight-decomposed low-rank adaptation. In Forty-first International Conference on Machine Learning, 2024.
[50] Shengjie Luo, Shanda Li, Shuxin Zheng, Tie- Liu, Liwei Wang, and Di He. Your transformer may not be as powerful you expect. Advances in Neural Information Processing Systems, 35:4301 4311,14355252 2022.
[51] Xuezhe Ma, Chunting Zhou, Xiang Kong, Junxian He, Liangke Gui, Graham Neubig, Jonathan May, and Luke Zettlemoyer. Mega: Moving average equipped gated attention. In The Eleventh International Conference on Learning Representations, 2023.
[52] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference machine learning, pages 4363 4371. PMLR, 2019.
[53] Fanxu Meng, Zhaohui Wang, and Muhan Zhang. Pissa: Principal singular values and singular vectors adaptation of large language models. Advances in Neural Information Processing Systems, 17:120088-121072 2024.
[54] Boris Mityagin. The zero set of a real analytic function. arXiv preprint arXiv:1512.07221 2015.
[55] Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1-35, 2021.
[56] Aleksandar Petrov, Philip HS Torr, and Adel Bibi. Prompting a pretrained transformer can be a universal approximator. arXiv preprint arXiv:2402.1475.. 2024.
[57] Alec Radford. Improving language understanding by generative pre-training. 2018.
[58] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 188)9, 2019.
[59] Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons, In International Conference on Machine Learning, pages 7996-8006. PMLR, 2020.
[60] Zekun Ren, Juhwan Noh, Siyu Tian, Felipe Oviedo, Guangzong Xing, Qiaohao Liang, Armin Aberle, Yi Liu, Qianxiao Li, Senthilnath Jayavelu, et al. Inverse design of crystals using generalized invertible crystallographic representation. arXiv preprint arXiv:2005.07609, 3(6):7 2020.
[61] David Romero and Jean- Cann-Bapistte Cordonnier. Group equivariant stand-alone self-attention for vision. arXiv preprint arXiv:2010.00977, 2020.
[62] Domenec Ruiz-Balet and Enrique Zuazua. Neural ode control for classification, approximation, and transport. SIAM Review, 65(3):735-773, 2023.
13

---

[63] Paulo Tabuada and Bahman Gharesifard. Universal approximation power of deep residual neural networks through the lens of control. IEEE Transactions on Automatic Control, 68(5))27 2728, 2022.
[64] Shokichi Takakura and Taiji Suzuki. Approximation and estimation ability of transformers for aequence-to-sequenee functions with infinite dimensional input. In International Conference on Machine Learning, pages 33416-33447. PMLR, 2023.
[65] Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis- Phiii-Piilippe Morency, and Ruslan Salakhutdinov. Transformer dissection: unified understanding of transformer's attention via the lens kernel. arXiv preprint arXiv:1908. 11775, 2019.
[66] A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
[67] Mingze Wang et al. Understanding the expressive power and mechanisms of transformer for sequence modeling. arXiv preprint arXiv:2402.00522 2024.
[68] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.047668 2020.
[69] Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: a case study on approximating turing machines with transformers. Advances in Neural Information Processing Systems, 35: 15:12071-1208 2022.
[70] Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco S Cohen. 3d steerable cnns: Learning rotationally equivariant features in volumetric data. Advances in Neural information processing systems, 31, 2018.
[71] Tian Xie and Jeffrey C Grossman. Crystal graph convolutional neural networks for an accurate and interpretable prediction of material properties. Physical review letters, 143301,,,,,, 2018.
[72] Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: A nyström-basee algorithm for approximating self-attention. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 14138-14148, 2021.
[73] Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, 55(1):407-474, 2022.
[74] Chulhee Yun, Srinadh Bhojanapalli. Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of souuence-to-sequenee functions? arXiv preprint /0077, 10077, 2019.
1912:
[75] Chulhee Yun, Yin-Wei Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. O (n) connections are expressive enough: Universal approximability of sparse transformers. Advances in Neural Information Processing Systems, 33:13783-13794, 2020.
[76] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslic, Chris Alberti, Santi- ago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33:17283-17297, 2020.
[77] Shuangfei Zhai, Walter Talbott, Nitish Srivastava, Chen Huang, Hanlin Goh, Ruixiang Zhang, and Josh Susskind. An attention free transformer. arXiv preprint 1rXi::2005.14003 2021.
[78] Chi Zhang, Cheng Jingpu, Yanyu Xu, and Qianxiao Li. Parameter-efffcient fine-tuning with controls. In International Conference on Machine Learning, pages 59066-59079. PMLR, 2024.
[79] Chi Zhang, REN Lianhai, Jingpu Cheng, and Qianxiao Li. From weight-based to state-based fine- tuning: Further memory reduction on lora with parallel control. In Forty-second International Conference Machine Learning, 2025.
14

---

[80] Keming Zhang and Joshua S Bloom. Classification of periodic variable stars with novel cyclic- permutation invariant neural networks. Monthly Notices of the Royal Astronomical Society, 505(1):515-522, 2021.
[81] Sixiao Zheng, Jiachen Lu, Hengshuang Zhao, Xiatian Zhu, Zekun Luo, Yabiao Wang, Yanwei Fu, Jianfeng Feng, Tao Xiang, Philip HS Torr, et al. Rethinking semantic segmentation from sequencceto-sequennee perspective with transformers. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 6881-6890, 2021.
[82] Chen Zhu, Wei Ping, Chaowei Xiao, Mohammad Shoeybi, Tom Goldstein, Anima Anandkumar, and Bryan Catanzaro. Long-short transformer: Efficient transformers for language and vision. Advances in neural information processing systems, 34:17723-17736, 2021.
15

---

A Detailed related works
Approximation results for transformers Since the introduction of the transformer architecture in [66], numerous studies have investigated its approximation properties. The universal approximation property (UAP) of the original transformer with softmax attention as fixed length sequence-to- sequence model was established in [74]. This constructive approach was later extended to transformers with certain sparse attention mechanisms [75] 76). In (37], the authors proposed a new construction demonstrating that transformers with a single attention layer and sufficiently deep feedforward networks can achieve UAP. Similarly, 2 showed that with increased hidden dimensions, two variants of transformers, i.e. LinFormer [68] and Performer [12], satisfy the UAP. In contrast to these constructive methods for different architectures, our results offer unified framework for establishing the UAP of various transformer models without relying on explicit constructions. Beyond these works treating transformers as fixed length requence-to-sequent
model, there are also studies handling transformers with variable-length inputs by considering the input sequence as an empirical measure 20 22 The universal interpolation and universal approximation properties under this viewpoint were established with proper assumptions. Compared to these results, we still consider transformers as sequence-to-sequenee models this work offer direct analysis for different transformer architectures. Recently, there are other works studying the UAP of attention-onl -nnly architectures 29] 48), indicating that softmax attention alone can also achive strong approximation power. Other studies have explored the UAP of transformers under alternative settings, such as in-context learning, prompting, and constrained scenarios
30 50, [56]. Another researchline 22
is the Turing completeness of transformers [55 69 Besides these UAP results, there are also
works providing the approximation rates of transformers. For instance, (34 provides explicit rates over dense subset of sequence-to-sequees
functions; [67] derives rates for target functions with structured memory; and (64) characterizes the approximation rate in terms function smoothness for transformers with infinitely long inputs.
Approximation under symmetry The study of approximation under functional symmetries has been explored in various works. In (73), the universal approximation of functions invariant under compact group or translation actions was analyzed using shallow neural networks. In [3
[9].
convolutional structures were proposed to approximate equivariant functions. In 45 52
59], the
universal approximation under symmetry using deep neural networks was investigated. Notably, 45 provides a general sufficient condition for the action of any transitive subgroup of S,, coordinates (I-dimensional tokens). In contrast, our work addresses approximation under symmetry in a broader setting, considering group actions on d-dimensional tokens rather than coordinates, thereby extending the analysis 45 to non-transitive permutation groups. In [. the authors provide a general framework the ensemble controllability of control systems under symmetry. They also show that systems that can interpolate arbitrarily many samples under symmetry are generic in certain topology. Compare their genericity results, our results provide verifiable sufficient condition for UAP of specific architectures, allowing direct applications to various transformer architectures.
Transformer variants
Beyond the original Transformer, numerous architectural variants have been developed to improve efficiency, scalability, or adaptability. These include sparse attention
mechanisms 3 1
24
40
76), low-rank and kernel- bennel-bsed approximations of attention [2 68 72).
as well as other architectural modifications [25] 47 [1 77). Another related line of work explores
parameter-efficient fine-tuning methods for large Transformer models 28
32
49
53
78 79). which
aim to adapt pretrained networks to downstream tasks with minimal additional parameters. In this paper, we establish general sufficient condition for the universal approximation property (UAP) of various Transformer variants. As demonstrated in Section 4 our framework can be readily verified for many existing architectures, and potentially extended to other designs not included as well.
B Proof of Theorem 1 and Theorem 2
B.1 Proof of Theorem 1
In the following, ||
|l2 denotes the normm, for both vectors in Rdxn or Rdd, We begin by proving the following interpolation property of Tg.u:
16

---

Proposition 1 (Interpolation Property). Suppose G and H. satisfy the condition in Theorem 7 for group G. Consider any G-equivariant continuous function F: Rdxn Rdxn Then, for any
and { (X,} Rdxx, there exists F ToH such that:
-F(X))-F(x))) E, if X; is in general position( in Section 2 [I((x)) < n max(]]F(XX
2e, if X; is not in general position.
Proof. Since F and functions in To.N are G-equivariant, we only need to consider the case when X; are from distinct orbits under the G-action. Moreover, we can assume that X; are in general position for = 1, .,, and X; are not in general position for i = M 1,.".,, ,N.
By the token distinguishability condition, there exist m and g (Id (g)+ such that the tokens of g(X;) are all distinct for i 1,... I,...,M. We denote -1,' ,UM as the distinct tokens in g(X)), ... (( For each j S Mn, suppose xj [Xi] for some (L, E [n] [M], we denote yy its corresponding token [F(X)]]k- Moreover, distinct tokens in g( MM1),,... .9(xx) that are different from T1,- " TM For each j > Mn, we denote y, = 0 E IRd. Then, we get set of d-dimensional pairs {(#,, ) j==
M.
denote 3M++1, J.M++J IR as the
MM++J C R Rd
where all 2j are all distinct. Since H satisfies the non-linear affine invariance condition, according to the main result in [10). know that there exists function
fE {(Id + o o...
(Id + fi) | E N+.f1, fs H}
(24)
such that
ll(;,,) Vs 112 I E, j=1,-. .Mn J. Denote f8r as the token-wise extension of f to indxn, For each S M, we have
(25)
(f(m))(X.)) - 2(X.)ll2 = =1((((((xx))) [F(X)))). ... (f(g(X)])) [F(X)))))
(26)
- n n max [I((z) Vsll2 S..
For each i 2 M + we have
| p (x,)) = (f(((x))), ... f(olx.l)))11 (((l)))))))
5 E
|5(((X)))))2+
Σ
[
Eg (ma+.))
< n max (15())
max f>Mn
[1xx2)
5 n (max(]lF(Xi))a)) :) +e= max]mma[[[[(())]] 2s.
(27)
Therefore, F = f g E Tg.N satisfies the interpolation property.
Proposition (Approximation of Tensor-Type Functions). Suppose & and H. satisfy the condition in Theorem Then, there exists F E Tg, such that
f for group G. Consider any continuous, increasing function h E. - IR and any 0.
|| (dxx)) ([o()) Se,
(28)
where ((dxn) is the coordinate-wise extension of h to Rx given by
(ddd))) (X)) h(X,,), 1 1 i i d, 15j5n.
(29)
Proof. Proposition 2 directly follows from the proof of Proposition 4.11 in [T].
and Theorem 2.6
Proposition 3 (Corollary of Main results of [O).. Let d 2 2 and H be a family of maps from Rd dd that satisfies the non-linearity and iffiie-invariance condition Theorem Then, for any {a,,, W C. IRd x R2 with I, + x, for all i # and > 0, there exists
f E {IId + fx) o...0 (Id + fi) k N., f1, fi. .f. H}
(30)
17

---

such that
(lf())) will S, i 1=1,..,,
(31)
Proof. Proposition
is direct corollary of Theorem 2.6 in 10
Proof of Theorem
! The approach of the proof is similar to the main theorem in and
We assume without loss of generality that K = [-8, s]),) is a hypercube Tedxn, Our target is to show that for any > 0, we can find function F E Tg. such that [| Fl) S
Step 1. For each multi-index i == ((R))E(()) E Zdxn and > 0, we define the grid cells:
1,6 == [X E R dmm
Xa E (āud (iu + 1)8]. for all k E [d]. E [n]]]
(32)
We denote Pi,á di comner point of 1, and Xi,8 the characteristic function of U Since is continuous, there exists such that it has a piece-wise constant approximation
F Σ F(Pi)x1.5
(33)
such that
|| FILLP(K)
(34)
Step Apply Proposition 3 to the set grid points
{
PL. iigt E {--s/o]..... [
Then, for any >> 0, there exists function F Ts. such that:
If Pi,á is in general position, then
[[(()))) - F(P1,))l <
Otherwise,
[P(1)))) < max(]1F(p).s)II) + + S n|| 1||Fllo(K)) + 2%.
Step For any a E (0, 1), define
0i == {X ddd X E [ixd iæd + a6), for all k E [d]. E [m]]
(35)
as the shrunk hypercube of 11, with side length aб. We consider the map ha,5 R + R defined as:
i6.
if x E [15, i8 + ad]. i Z,
Nn.
+ I 16 ad
(36)
if [18 + ad, (i 1)8], ie Z.
the interval [15, i8 + ad). function h,,)(z)) remains constant at i5. Then, as x increases from id - ad to (i + 1)8, the function increases linearly from i8 to (i + 1)ō. Notice that ( is continuous and has constant value p: on D% for each i. Since h is continuous and increasing, by Proposition
2 for any p >> 0, there exists function Ha.8 E Tg. such that
Ha.
(dxm)
(lс(K) < <.p. 0,,
(37)
Step 4. Now we can estimate the error of the composition || Ho.8 F(((P(K). We define
ka
(Uris) nk.
and denote K as the union of the grid cells in Ka whose corner point Pt are in general position, and Kÿ as the union of the grid cells in Ka whose Pi not in general position. Then, we have
18

---

1. On KT, we have
(dxm) || o n - Fllee(kp) < <)m{(K)))
(38)
2. For K2. the number of i with Pi,s not in general position is at most m(n 1) we have the measure of K3 = O(*)). Therefore,
(2s/8
1)
| h (dxm)
Fl)) < (n. |[Fllook + 27)
(39)
Therefore, choose 6 and y sufficiently small such that
2 (dxn) FIler(Kc)) E
|I
(40)
On K' K by choosing a sufficiently close 1, we make m(K \ K*) arbitrarily small. Since (dx") and is bounded on K, the following can be guaranteed: F h hag
| (dxm) a.5
-FlLLP(KIK>) < 4
(41)
Since F is uniformly continuous K, there exists > O such that for any X,Y E K with ||X Yll < p. we have (F(X)-F(())) < e/{{(m(K)))) Therefore, after determining a, and 7, we can choose P such that
|| o Ha.s - (() & (((K))
(42)
After determining 8 and by step 3, we can choose sufficiently small such that
|F Ha.5 F hohh
(dxn) [[(P(K) pLip(F))
(43)
Recall also that Thus, by the triangle inequality.
E || F((EP(K) <
|| Ho.s F(l ||F Hn, F (dxx)
[[ FI o Na.
(dxn) FlLL((K))
+ F (dxn)
(l + |1F F (())
(44)
E
+
+ =E,
4
4
4
which completes the proof.
B.2 Proof of Theorem 2
Proof. Assume that Condition 2 in Theorem | fails. Then, there exists N samples [X, from
different orbits under the G-action, but for any and g E (Id +g) there exist indices i, E [N] such that at least one token in 9XX,) is identical to a token in g (X,). This can be written
D = II (X)():)), - Lx(X 11 O. d,
(45)
When G is parametric in 0 E O 11; is also analytic in 0. As the zero set of nonzero real analytic function has measure zero [54], this implies that for some i,j, II is identically zero, meaning that fails to distinguish tokens in X; and X,. This argument reduces Condition 2 in Theorem to the case N = 2.
Moreover, if there exists a uniform such that the token distinguishability condition for any two tokens holds, the above argument essentially shows that this can also be used distinguish any N tokens.
19

---

C Proofs for the applications of main results
C.1 Proof of Corollary D and Corollary 2
We first prove the following lemma.
Lemma 1. Let r be a kernel function satisfying the conditions in Corollary 1
Suppose (a1....,0r) Or) C Rd \ {0) and (b1,...,bb, b,) C IRd \ {0) are sequences of distinct tokens. Suppose that for some indices r' E [r] and s' E [s]. the following equality holds for all choices of Wo, WK, Wv:
k(Woap, Wkaj) Wvas) by Σ
k(Wabs. Wkbj)
0p Σ
Ei k(Wabs, WK Wxbb) Wrbs) (46)
El= k(Woar, Wxaa))
j=1
Then, r = 3, and there exists a permutation o E Sn with o(r') = st such that a, = for all i.
Taking Wy be zero directly gives ar by. In the following, set Wq I, and for notational simplicity define
Proof.
k(x) = k(ar),)), E
The proof utilizes the following lemma:
Lemma 2 (Auxiliary lemma). Let {=1.-.. Apt : (a,,".. (bi...,, ,b,}. Then, there exist WK E Rdxd and permutation Sp such that
lim k(tW ((LW)) = oc, for all i <.j.
(47)
T(IW ((oW))))())
Since {a are distinet tokens, by the auxiliary lemma, we may choose WK (and reindex the sequences accordingly) so that after replacing Wx by tWK the kernel values satisfy, for large > 0.
<(WWka)) < k(tWwaz) .... <...<h(ttWoon
and similarly
k(Wwkb)) < k(tWkb2) < ... < bb))
Moreover, the lemma tells us that for any a, and b,, either aj bi or one of k(tWaa,) and bttWab is dominated by the other in the limit + cc.
After subtracting ar" from both sides in 446). we have
Σ k((WKa;)a
(48)
Ej= k((W
Ej k((W)eb;)
By transformation, it gives
((Wxo;) -b)
bi) = O.
(49)
Let - oc, considering the dominate term k(tWxc xa, (i) b.) gives a, = bs. Then, for all 0. l.... min(r,s), we then prove by induction that: dr-A ba-k-
Suppose we already have ar- = by-ts for 1,... , 1. It then follows that
Σ
Σ
((WWa))((WWxbb)CC b,)
++1
(50)
Σ
Σ
((WWra)E((Wsaall at)= =0 for all IR.
20

---

Combining with (49)
we have
ΣΣ
Σ
(R(WWx))&(WWabbla - -ii) = =0, (51)
== i j
where the leading term is
ba) + k(t (ob----- bg-g).
(52)
Since a, b,, ar-4 * a, and by-q # by. let + oo gives that k(tW kgy-a)) and k(tWKbb.-. are not dominated by each other. By the auxiliary lemma, this indicates that ar-q ba-q. which completes the induction.
Then, we have shown that ar-k = by-k for all l = 0, 1, min s}. The only remaining thing is to show that Suppose 8, then we have
k(W - bt) = 0,
(53)
1=
where the unique leading term is k(tW Nawwa, a, (e(W)e(Wbbbb... xbbr)(aa - ba-r). Since = b, * b that gives contradiction. This completes the proof.
Proof of the auxiliary lemma. For each pair (i,5) with 1 sikj we define
WK lim k(IWRo:s) 0 00 k(tWKzz;)
Ma,j == Rdxdy
(54)
and we define M as the union of all such sets:
M
U Ma.j
(55)
IStCSSP
According to the condition in Corollary each M,, is measure-zero set in Rdxd Therefore, M is also measure-zero. Choose any WK E Rdxd (.M Then, for any i, have
k((Wkw)) or oc,
lim 100 k(tWKI,))
(56)
iee either k(:)) < k(WW)z)) or (tW));;) xz)) for large This indicates that there exists permutation a E Sp such that
i(IWKF = co, for all <j
lim 100 7(tW
(57)
which completes the proof.
Proof of Corollary Lemma shows the token daken-disinnuuishabiltty condition over X with non-zero tokens. This indicates the interpolation property over the region when X has non-zero tokens. Since
the set
{X E ddn [X]; 0 for some E [n]]
(58)
a measure-zero set, the S,,UAAP holds for Tg. by the same argument as Theorem !
C.2 Verification of conditions in Corollary 1 on practical attention mechanisms
We verify the conditions in Corollary for the following kernel functions:
k(x, y) exp(x v), used in the original transformer (66] Verification: For any given x * 0 and distinct y1,82 E Rd {0), the set
p = {WK x WKY1 = x Wx
(59)
21

---

is hyperplane in Raxd, which has zero measure. Notice that for any WK in R P.
lim exp(tx WKY1) lim exp(t(2 Wx(n T
y2))) or 0.
(60)
10000 exp(tx WKy2)
This indicates that the condition in Corollary hholds
kxx y) exp(->ll= vlli), the RBF kernel, explored 65
Verification: Notice that
+W k
exp((>(11t [ ww (222))))1)) + 2tx T Wx(12 -1))).
exp( exp(->ll< EW x3222
(61)
Therefore, any Wx such that [WKy la + [W satisfies the condition Corollary Since for distinct yn and 1/,
[ 12 - 12
(62)
is non-zero quadratic equation on Wx, whose solution set has zero measure. Therefore, the condition in Corollary hoold.
k(z, v) <(x) T ((y), where
o(x) = exp (-2]la112) (exp(wT x).... "xpp...,.p((((TT))) R",
(63)
with wi,..., Wm E Rd drawn i..d. from Gaussian distribution. This kernel is used in Performer [12]. and Corollary [holds almost surely in this case.
Verification: We have
k(x,, (W) s(x) T(x)To(IWX>) ((WWx9))
k(zz, tW23))
o(tWky))
- exp(w] x) exp(tw, Way1) exp(w, x) exp(tw; Wxy/2)
[ [K
|| (1ž)
exp
(64)
We claim that if w, are pair-wise linear independent, i.e. there does not exist i + such that w; awwy for some E IR, the condition in Corollary hholds This almost surely holds when wy are drawn i.i.d. from a Gaussian distribution.
If when + oo, the ratio in 644 do not goes to infinity or zero, it must hold that WK
Wx l2, and max(w; WKm) = max [w. Wxy2]-
(65)
When wy are pair-wise linear independent, we have that y/ " & y for all + [m]. Also, since " y/2 and w; are non-zero(by the pair-wise independent condition), we have 1/1 wo # y2w, for all E [m]. Therefore, have that all the sets
(WK W WxY1 w WKB1} {WK (WK. Vo - y2w, )r = 0), (66)
where (,, FF denotes the Frobenius inner product, hyperplanes in Rxd which has zero measure. That is, equation (65) only holds for a measure-zer zero set of WK, which completes the verification.
k(æ, y) exp(wT T x)) + exp(w" y). where w E Rd.
Verification: We have
(Lx,tWKul exp(w (x + tWK31)) exp(tw" TW y2))
(67)
k(2, x2) exp(w (ar + tW (Wkb2))
When 31 * 12. for almost all WK, we have w WK (V1 - 12) of Therefore, the condition in Corollary holds.
k(z, y) p(x y)ı(E y), with being any positive polynomial function and i being any kernel satisfies the condition in Corollary [
Verification: Just neet to notice that for almost all Wt, it holds that
p( +W w1)
lim
(68)
p(x WdpWWWWW k3)
is constant indicating that the condition in Corollary D still holds.
22

---

C.3 Proof of Corollary 2
Proof. We only need to prove the token distinguishabiliyy condition for two samples:
For any X and that are in general positions and from different orbits of G(defined in (18)
there exists
g E gm = {(Id (mm) .... (Id +91) gi E 9x., for i [m]}
(69)
such that the tokens of g and g(Y are all distinct.
We prove this claim by contradiction. Assume that, there exist X and Y that are in general positions and from different orbits of G. but for any g E g there exist indices i. E [n] such that at least one token in g(X) ) is identical to token in gY)). Then, according to the analyticity, there exist
indices i and i2 such that, [g()],,, = [g(Y))s )], always hold. For a given p1 E [m]. we first consider
g E Id + ON., Then, [9(X)];, = (Y)) gives:
[X]1+ EsEN,, (1) XI, (Wxx)) Ejen,, (1) ((Wo (X)
DM EiEN,, (12) k([W [Wx (w ΣjeN, (2)) (65) k(WoY),, [Wn Y))
(70)
for any Wo, WK, Wv E Bdddd According to Lemma 1 we can deduce that WM,, (1)) (V. (i),.
[X],, = [iigg and
{[1]g q E No, (61) [My 9 E (22)).
(71)
Therefore, choose any Q1 E EN (f1), we can find @2 E Npp (iz) such that [X]e, = [Y
Now, we claim that for any < and E Id + GN (a layer before the -t- layer). [g(X)] =
[g(Y)) 92- Otherwise, suppose there exists 9I E Id + 9pp with [g1 (X))a, * [V)) By scaling
the Wy matrix to be small enough, can assume 91 satisfies that
1
(X) X112 < min [1]xx] - (X],l12)
(72)
Then, we have that (x))) # L0 (Y)) and by equation (2).. for any q A d2 in in.N (12). we have
Illgi (X)),, - 191 (Y [|(]9) (X (X)l [x] + ([X]m1 - -Y1,) ([Y), (Y)
2 |[[x] 9. [112 (1)x [x]q, l2 ||[] [9 (Y (8)lll > 0.
(73)
Therefore, [9 (X)) does not appear in the tokens of 91 (Y),, i.e. the sets
[g j E (ii))) and (l. N(
(74)
must be different. By applying Lemma too (X)), and (Y))), we know that there exists O2 E Id+ such that [92(91 (X)) * [g2(er (Y))) Since 92 E (o C go which can distinguish [X],, and [Y] contradicting to our assumption.
= [g( gg))) Then, we can apply Lemma] I to [X], q. and [Y] la2. and deduce that the set of tokens of X with indices in Np. (g1) are the same as those Y with indices No. (92). That is, the tokens where [X],, can attend to within two hops are the same as those where [Y in can attend to within two hops.
Hence, we have shown that for P2 < P1 I n and any g Id + GNpp [9())
The above process can be repeated. Since we assume that & is connected within m layers, we know that any indices in [n]] can be reached starting from é and i2 within m hops. Finally, the above discussion can cover all indices in [n]. Since X and Y in general positions, the correspondence between their tokens is unique. Finally, this results in permutation a E S,, such that:
[X] [Yoos)-
(75)
On the other hand, apply Lemma agaan to eqch Npp [X]; and [Y]o(i). we can deduce that
j E Ng)) + of) E (N)) for all p E [m]]
(76)
By the definition of Aul) this means that belongs to each Nyp indicating that E G. However, this contradicts to our assumption that and Y are from different orbits of Aut, which completes the proof.
23

---

C.4
Verification of the UAP for other transformer variants
In this section, we verify the condition in Theorem | for the kernelized attention of SkyForner and the attention mechanism of the Linformer [68].
C.4.1
UAP for LinFormer
Linformer 68
where the attention layer is defined
Atten(X] (X) = X + WyXFF softmax((WxxxE)) T W2X)
(77)
where F, F Baxk with 1 I k < n are two trainable projection matrices.
For LinFormer, we have the following lemma:
Lemma 3. Let X,Y E TRdxn be two points that are in general positions. ffr some i1, E [n], the following equality holds for all Wo. WK, Wv E Rdxd and E, F E BRak
[X] +Wy (WyXP X softmax (WxXB) WoX)] = + +WyYF sollmax(W><EB W2Y)
(78)
then have i i2 and X = Y.
Proof. Take Wy = 0 gives [X], = [Y] Then, for any given R (ri," m ,.r,) C [n]. we take
= F = !er Cr.]s
(79)
where Cr, is the r;-th column of the identity matrix. Equation
78
then gives that
x (x(X))))
wx(Y),)
Σ JER
Wv(X(,)
Σ
WyDM),
Ex (Wo[(() Wx(X]))
EiER (W Wx(Yl()
JER
(80)
which reduces to the discussion in Lemma Therefore, we have that the set {[X], i R) is the same {[Y]; R}. Since X and Y are in general positions, and R is arbitrary, this indicates that Y.
According to this lemma and the fact that 19 is analytic all the parameters, conclude by Theorem that the UAP holds for LinFormer without symmetric restrictions. Furthermore, the same result can be generalized to the case where the softmax function in (19) is replaced by kernel-based form with a kernel satisfying the condition in Corollary
C.4.2 UAP for SkyFormer
The kernelized attention used in SkyFormer [9. where the attention mechanism is given by:
[Atten(X) = [X]+ 1++
+
exp
(-1 1 [[
[WxX1,11 Wv
(81)
Ø=1
The proof follows from the verification for the RBF kernel Section prove the ooke--iistinuuishablitty condition.
e4 with the same argument to
C.4.3 UAP for architecture proposed in
More precisely, if we define EN as the family of token-min mixiin maps associated with the sparsity pattern A,, and the transformer family 7 associated with sequence of sparse mode, just T defined in Section 4.2) Then, under the same assumption on as in Corollary 2 we have:
Corollary 5.
The possesses the G-UAP with G defined in (88
Assume the condition in Theorem fails. Then, there exists X and Y that are in general positions, and i,, i2 E [m] such that for all W Idddd a E R and b E Rdd we have
[X] +
ao(W[X], - b) = [1) + Σ
an(W[V], b)-
(82)
JEN(())
JEN(())
24

---

It then follows that [X] = [M Moreover, if the sets
([}) 15 ((()))
(83)
and
{M 1j ((t2)
(84)
are not the same, we can then derive an identity
caa(Wa b) = 0,
(85)
where zι are the unique tokens appears in the two sets, C; equals to 1 if xı appears in the set of X, and -1 otherwise. Notice that the identity holds for all W Raxd and b R, this gives a contradiction according to the proof of Theorem in [T. Specifically, since a is of polynomial growth, taking the Fourier transform(in distributional sense) on both side of (85) with respect b gives:
(Wa) (E)((E) =0, 0, for g TR."
(86)
where is the Fourier transform of a. Since a is not a polynomial, we have supp & contains non-zero value. This will lead to a contradiction. See Section 3.2 in [IO] for more details.
C.4.4 Details for architecture proposed for D,,C,, equivariant map
For architecture with Dn symmetry By choosing + (N,N, as an invariant sequence of sparse mode, by Corollary 2 we have that the transformer with the first design satisfies the Aut(A)-UAP. Therefore, we only need to prove thet (N) Dn,-
First, it is easy to see that for any E Da we have j EN() indicates that g(i) E EN (g(i)) This implies that N, E Au) On the other hand, for any Aut(N), since D, is transitive, there exists h E Dn such that ((g(1)) = 1. Now, we prove that == h o is either the identity or the reflection (I, (2,
Since E (NV) we know that (((()) = (i)) Since 711 = 1. we have (W(()) = ((x(1)) = (11) is invariant. This indicates that for any i E (i1 is also in M(1). Now, consider the value of (2).. We have that
2w (11 (222 = hx((11)
= (()) (W()
(87)
Since 2w + 1 2, we have that in (1),,, there only two indices j n, such that
[W(1) nw()) = 2w.
(88)
Therefore, it follows that 7(2) = n or 2. If (2) = 2, we can then repeat the discussion to deduce that (i) for i 2, 3.3.... sequentially, indicating that y is the identity. If 72) n. Then, can repeat the discussion to deduce that 7(1) = - 1-+22 2 - mod n for = 2,3 3. ... n.. This indicates that 7 is reflection (2, n) (3) 1)... .... which is in D,,-
Therefore, we have shown that Aut(N) = D,, This actually classical result on the automorphism group of the circulant graph (4)
Moreover, we destroy the symmetry to reflection by defining
((1) {i,i i
2. ..... i mod n} for i = 1.2....... ,,
(89)
with w S -للاا proof, we only need check that Aut(N) C., which can be done following the same approach as D,.-
- we get a transformer that is -quequivariant and satisfies the -AP. For the
For architecture with C, symmetry For token-mixing layer defined by the convolution in (23). we first notice that it satisfies the -quivarraae In fact, this follows from the fact that the convolutional operation is equivariant to translation.
Therefore, to prove the -UA, we only need to check the token distinguishability condition under Cn action. Specifically, suppose the condition in Theorem fails. Then, there exists X and Y that
25

---

are in general positions, and i1, i2 E [xx] such that the composition of token mixing layers cannot distinguish the -1 token of X and the i2-th token of Y.
Considering using single layers, we have that for all vp E RR++1, holds
+ [li = 1&b X)221
(90)
i.c.
1
Σ by (((+))) mod = Σ v (Y (>((t)))) mod
(91)
1=0
5=0
which indicates that
Σ by ([X mod (e(()))) mod n) j=0
(92)
Since is arbitrary, this indicates that
(i)+)) mod (1a+s) mod
for j = 0, 1. ,1.
(93)
Then, takethe indicices i + mod and ig + mod of X,Y respectively, and consider using two layers. The process is essentially the same as the proof of Corollary We can finally deduce that
+5) mod
(12+)) mod
for j = 0, 1, ..... n.
(94)
That is, X and Y differs only a eyclic action on tokens, meaning that they from the same C orbit, which is contradiction, and completes the proof.
26

---

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

---

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

---

Answer:
[NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpippi.ccppullc//uuuii wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
29

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://wwwrg..cooooo/oo//ccccaaa
Answer: [Yes]
Justification: Ethics.
The research conducted in this paper conforms with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper and does not discuss societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release any data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
32

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This paper does not involve LLMs any important, original, non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
33


Reviews:
[{"review_id": "Kmnwj4J3Q2", "reviewer": "Reviewer_rM6S", "summary": "This manuscript investigates the expressivity of transformer-like architectures with various attention mechanisms, and establishes their universal approximation property (UAP).  It does so via token-sequence distinguishability under the action of a symmetric subgroup G, followed by sufficiently rich FFNs.  The authors demonstrate the strength of their results via application to various attention mechanisms, and by constructing new architectures equipped with UAP by design.", "questions": "I feel like there should be a more intuitive way to write Eq. (4), which is after all a pretty straightforward parallel application of $\\mathcal{H}$ at each position.  I nudge the authors to consider an alternative, but it’s not crucial.\n\nNitpick:\nBelow Eq. (1) the authors repeatedly use “token” to mean something like “the vector in the residual stream at some layer and token position”.  Typically I think of tokens as elements of a finite set.  The embeddings in the residual stream are then no longer “tokens”.  Alas, my substitution would be unwieldy, but perhaps a brief comment on terminology could be added.  For example, the authors could add a footnote after Eq. (1) saying something like “We will abuse language slightly and call any $d$-dimensional column of $X_t$​ a ‘token’, even though it is the continuous embedding of a discrete input symbol.”\n\nMinor suggestions:\n\nLine 102: \n“can but only can represent only” appears to be a typo.  The authors may want to replace this with something like “can represent only”\n\nLine 102:\nWould “tensor-product functions” be more accurate than “tensor-type functions”?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper appears novel in that it establishes UAP in a relatively architecture-independent fashion for transformer-type models.  \n\nThe paper is very well written.  It builds up the notation and ideas intuitively and precisely, has an elegant aesthetic, and guides the reader easily to and through the results.\n\nUAP has been established for standard transformer architectures.  The surface-level role of this paper is to extend these results to variations of that architecture, which feels somewhat iterative.  However, the techniques developed in this paper seem to provide useful broad insights, and will likely serve more utility beyond the specific results derived here.", "was_revised": true, "final_justification": "I remain satisfied with the strengths of this paper and am happy to maintain my score and recommend it for a poster.", "rebuttal": "We sincerely thank the reviewer for your positive and insightful feedback.\n\n## On notation and minor suggestions\n\n- We acknowledge that the use of the term \"token\" may be potentially ambiguous. Following your suggestion, we will add a footnote after Eq. (1) clarifying that we slightly abuse terminology by referring to any column of $X_t$ as a \"token\", even though it is the continuous embedding of a discrete input symbol.\n\n- We appreciate your careful reading and will correct the typo in line 102. We will also adopt your suggestion to replace \"tensor-type functions\" with \"tensor-product functions\" for better clarity."}, {"review_id": "H5q23qZJ2W", "reviewer": "Reviewer_J3Ee", "summary": "This paper studies the universal approximation/expressivity ability of transformer-type architectures from a theoretical perspective. The results concern the family of architectures that resembles a simplified transformer: attention with residual connection, followed by a MLP with residual connection. Using any such family of transformers, the authors prove a non-constructive expressivity result for the set of functions that satisfy a notion of permutation/symmetric invariance. The sufficient condition is affine invariance, and more importantly, token distinguishability for the attention-type function class.", "questions": "- Are $C_n$ and $D_n$ invariant functions realistic for most practical applications? My impression is that in practice, the order of tokens does matter, and it would be interesting to see if the framework can be extended to function classes that don't satisfy permutation equivariance.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper provides a clean set of sufficient conditions for which UAP is achieved for a given family of transformers, and is overall well written.\n- A sufficient condition for the token distinguishability criterion is given that is feasible to check.\n- Extensions to general transformers via kernels and sparse attention are provided too.\n- Examples of different symmetry groups for the function class to be expressed are given, including the cyclic group and dihedral group.\n\nWeaknesses:\n- The results are not too surprising, since the moment you have token distinguishability, one would intuitively expect expressivity results to go through with enough symmetry.\n- The architecture class does not include other components of the transformers architecture, such as normalization.", "was_revised": true, "final_justification": "As I stated in my response to the authors, I believe this work is worth a poster at the conference. The theory is sound, but I did not give it a higher score due to the slight insignificance of the work (e.g. see discussion by reviewer gCVj), as well as the unsurprising nature of the result.", "rebuttal": "We sincerely thank the reviewer for the positive and insightful feedback.\n\n## On the lack of normalization layers\nWe acknowledge the omission of normalization layers as a limitation. This is a common simplification in theoretical analyses of transformer architectures, intended to isolate core components such as attention and feedforward layers. From a mathematical perspective, normalization introduces a nonlinear projection onto a product of unit spheres, altering the function family $\\mathcal{T}_{\\mathcal{G}, \\mathcal{H}}$. Inspired by recent theoretical studies on dynamics constrained to spheres (e.g., [1]), we believe that extending our framework to include normalization is a promising future direction.\n\n## On $D_n$ and $C_n$ symmetry\nOur intention is not to claim that $D_n$ or $C_n$ symmetries are typical in practical tasks. Rather, these examples serve to illustrate how our framework enables principled design of transformer architectures respecting general symmetry constraints—beyond the full permutation group. Such symmetries do arise in specific scientific domains: $D_n$ symmetry corresponds to the structure of regular molecules, while $C_n$ symmetry is relevant for periodic data, as we have mentioned in line 339-341. Other group symmetries (e.g., alternating groups, space groups) also appear in physics and chemistry, and could be explored\n\n## On functions without symmetry\nOur framework naturally encompasses functions without symmetry as the special case where the symmetry group $G = { \\text{Id} }$. Also, as noted in lines 119–122, prior work shows that for any architecture family satisfying $G$-UAP with nontrivial $G$, adding a suitable positional encoding allows approximation of general, non-equivariant functions. Hence, our focus on $G$-UAP is not restrictive, but rather provides a unified treatment of both symmetric and non-symmetric function classes.\n\nReference:\n[1] Geshkovski, B., Rigollet, P., & Ruiz-Balet, D. (2024). Measure-to-measure interpolation using Transformers. arXiv:2411.04551."}, {"review_id": "3CceJqGFKz", "reviewer": "Reviewer_8Xaz", "summary": "This paper presents a unified theoretical framework for analyzing the universal approximation property (UAP) of transformer-type architectures. Authors leverage token distinguishability as a fundamental condition for UAP to derive a general sufficient condition. Departing from previous work that focuses on architecture-specific constructive proofs, the authors introduce general, verifiable sufficient conditions that guarantee UAP across a broad class of transformer models with an attention-based module.", "questions": "No.", "limitations": "The authors did mention the limitation in the final chapter, and I don't think this work hasa  potential societal impact.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n(1) The paper demonstrates the broad applicability of the framework to various transformer architectures, including: Kernel-based attention, Sparse attention, Linformer, Skyformer, etc. \n(2) The paper is mathematically rigorous and provides extensive appendices with detailed proofs \n(3) The framework recovers and generalizes prior UAP results on softmax-based transformers.\n\nWeakness:\n(1) Limitation for practical usage: Normalization layers, which are practically crucial for stable training, are omitted in the analysis.\n(2) The work is purely theoretical and lacks any empirical experiments or validation. Some numerical results would help demonstrate practical implications.", "was_revised": true, "final_justification": "After reading the authors' and other reviewers' comments, I'll keep the same rating for weak acceptance, due to the broad applicability of the framework to various transformer architectures and mathematical rigor.", "rebuttal": "We sincerely thank the reviewer for taking the time to assess our work and for the constructive comments.\n\n## On normalization layers and empirical validation\n- We acknowledge that normalization layers are crucial for practical transformer architectures. As noted in our response to Reviewer #1, extending the theoretical analysis to include normalization is a promising direction for future work.\n\n- Regarding the absence of empirical experiments, we emphasize that our contribution is theoretical in nature. Nevertheless, we agree that validating the practical implications of the framework through numerical experiments is an interesting future direction."}, {"review_id": "uOooGYJEMM", "reviewer": "Reviewer_gCVj", "summary": "The authors study the universal approximation property of transformer models (a variety of variants, including some not necessarily addressed in previous works), and prove a non-constructive result using the analyticity of the attention kernel (due to the softmax).", "questions": "1. Results that are independent of context length should also be referenced. This connects to the measure-theoretic perspective on transformers; see the works of Furuya, de Hoop and Peyré, as well as Geshkovski, Rigollet and Ruiz-Balet. In my opinion, this is also the more natural point of view. We are at a stage where the actual question in approximation theory is not entirely clear: yes, it is possible to obtain rates and approximate functions, but why is this meaningful? Moreover, the results are not constructive, which in my view misses the point. Indeed, one of the goals of the constructive methods would be to understand the role of different mechanisms (multi head, mixture of experts, etc.) to the inner workings of Transformers. I did not see this being elucidated in the present paper. If the authors comment on how the different mechanisms affect approximation proofs, I believe the quality of the paper would increase significantly.\n\n2. I do not really understand why the authors work with functions on compact sets, as the topic is perhaps fundamentally about probability measures (given the permutation equivariance due to attention and the presence of positional encoding) and maps between spaces of probability measures. This is particularly true due to the fact that the context length $n$ is not necessarily fixed in practical applications.\n\n3. Can the authors comment if there is a way to obtain approximation results with a complexity that is independent of the number of data points?", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The issue I have with this paper is that the formalism is not especially elegant mathematically, and the results are not particularly innovative. The distinguishability aspect has already been addressed in an abstract way by Agrachev and Letrouit in 2024, where they use the notions of strata and orbifolds, which are well known in the context of quotient manifolds. Perhaps I am mistaken, but this should be discussed even if I am.\n\nI would be very open to changing my score, but the presentation of the paper needs to change, to something more fundamental, since this is a very theoretical paper anyway.", "was_revised": true, "final_justification": "After the detailed answers by the authors, and consulting some of the other comments they made to the other referees, I am now convinced that this paper merits acceptance.", "rebuttal": "We sincerely thank the reviewer for the thoughtful critique.  Below we address each concern in turn and will integrate the requested citations and clarifications in the future version.\n\n## Relation to Agrachev and Letrouit (2024)\n\nWe appreciate the reviewer pointing us to this important reference and will include it in the revised version. While both works study expressivity via symmetry-aware controllability, there are substantial differences:\n\n* **Notion of “distinguishability”**: In Agrachev & Letrouit, “distinct samples” refer to a set of distinct points $X_1,\\cdots, X_N$ in the quotient manifold $M = \\mathbb{R}^{d \\times n} / G$. This is part of the problem formulation for the simultaneous controllability. In contrast, our notion of *token distinguishability* (Def. 3) is a condition imposed on the *architecture family* $\\mathcal G$, requiring the existence of $g\\in \\mathcal G$ such that all the $d$-dimensional tokens in $g(X_1),\\cdots, g(X_N)$ are distinct. This requirement arises from the token-wise implementation of the feedforward layers.\n\n* **Genericity vs. sufficient conditions**: Agrachev & Letrouit (2024) proves that the architectures that satisfy controllability is large in a topological sense - roughly that if we were to randomly (assuming that this could be done) pick a architecture, it should satisfy controllability. However, such results cannot tell us whether a specific architecture has controllability or not. This is where our type of results come in, providing explicit and verifiable sufficient conditions on transformer architectures to achieve approximation.\n \n    Both their and our results reveal the power of deep network approximation, but in different ways and complement our understanding.\n\n\n* **Approximation vs. interpolation**: Their notion of ensemble controllability aligns with interpolation property (Prop. 1 in Appendix A). In contrast, our results also incorporates the approximation results. As shown in Cheng, Li, Lin & Shen, 2025, interpolation does not imply UAP in general. \n\n## On the measure-theoretic perspective and variable-length inputs\n\nWe acknowledge the growing interest in framing transformers as maps between probability measures (e.g., Furuya et al., Geshkovski et al.), especially for variable-length inputs. Our work, however, focuses on *fixed-length* sequence-to-sequence transformers, which remain prevalent in practice (e.g., in encoding tasks, classification, and contrastive learning). In such settings, function approximation over compact subsets of $\\mathbb{R}^{d \\times n}$ remains standard.\n\nFurthermore, sparse, low-rank and some other attention mechanisms do not lift transparently to measure-valued inputs as the standard attention layer in Furuya et al; our framework accommodates them directly. By contrast, measure-theoretic perspectives should be important in formulating varying-length autoregressive decoders but may be less suited to these architectural variants.\n\n## On the role of architectural mechanisms\nOur framework abstracts the transformer block into *token-mixing* and *token-wise* components, allowing us to analyze a wide class of architectures without relying on the exact form of architecture components, including multi-head attention, mixture-of-experts, etc. These mechanisms can be viewed as design choices within either component. While quantifying their precise roles in approximation is indeed an important direction, such analysis is orthogonal to our current goal of providing general UAP conditions and is left to future work.\n\n## On approximation complexity\n\nWe are not entirely certain what is meant by “complexity independent of the number of data points.” If the reviewer is referring to the sequence length $n$ (as commonly done in measure-theoretic works), then we believe such independence is unlikely. As the number of tokens increases, the space of functions to approximate becomes essentially more complex. For example, in interpolation-based frameworks like Agrachev & Letrouit (2024), the number of required number of samples $N$ grows exponentially with $n$ to support an approximation result.\n\nOn the other hand, if the question concerns whether the approximation complexity can be independent of the number of interpolation points in the function domain, then Cheng, Li, Lin & Shen (2025) discusses related results in the feedforward case. Combining such insights with structure-specific analysis of token-mixing layers may lead to bounds in certain settings, but this is beyond the scope of our current work.\n\nWe hope these clarifications address the reviewer’s concerns. We will incorporate the suggested references and improve the exposition, particularly with regard to clarity and positioning relative to prior work. Thank you again for your willingness to reconsider your evaluation.\n\nReferences:\n\nGeshkovski, B., Rigollet, P., & Ruiz-Balet, D. (2024). Measure-to-measure interpolation using Transformers. arXiv preprint arXiv:2411.04551.\n\nFuruya, T., de Hoop, M. V., & Peyré, G. Transformers are Universal In-context Learners. In The Thirteenth International Conference on Learning Representations.\n\nCheng, J., Li, Q., Lin, T., & Shen, Z. (2025). Interpolation, approximation, and controllability of deep neural networks. SIAM Journal on Control and Optimization, 63(1), 625-649.\n\nAgrachev, A., & Sarychev, A. (2020). Control in the spaces of ensembles of points. SIAM Journal on Control and Optimization, 58(3), 1579-1596."}]

Author rebuttal:

Meta-review: This is a nice theoretical paper that studies the universal approximation property of Transformers as well as variants of Transformers. Reviewers unanimously voted in favor of accept, and the AC agrees that the paper adds value to understanding and formalizing Transformers.
Decision: Accept (poster)