Vocabulary In-Context Learning in Transformers: Benefits of Positional Encoding
Authors: Qian Ma
Ruoxiang Xu
Yongqiang Cai
Venue: NeurIPS 2025 poster ()
Keywords: Transformer
Universal Approximation
In-context Learning
Vocabulary
Primary area: theory
TL;DR: Answer the question: Does the universal approximation property still hold if the context in in-context learning is restricted to a finite set?

Abstract: Numerous studies have demonstrated that the Transformer architecture possesses the capability for in-context learning (ICL). In scenarios involving function approximation, context can serve as a control parameter for the model, endowing it with the universal approximation property (UAP). In practice, context is represented by tokens from a finite set, referred to as a vocabulary, which is the case considered in this paper, i.e., vocabulary in-context learning (VICL). We demonstrate that VICL in single-layer Transformers, without positional encoding, does not possess the UAP; however, it is possible to achieve the UAP when positional encoding is included. Several sufficient conditions for the positional encoding are provided. Our findings reveal the benefits of positional encoding from an approximation theory perspective in the context of in-context learning.

Vocabulary In-Context Learning in Transformers: Benefits of Positional Encoding
Qian Ma Ruoxiang Xu
Yongqiang Cai I+
School of Mathematical Sciences, Beijing Normal University
Abstract
Numerous studies have demonstrated that the Transformer architecture possesses the capability for in-context learning (ICL). In scenarios involving function approx- imation, context can serve as control parameter for the model, endowing it with the universal approximation property (UAP). practice, context represented by tokens from finite set, referred to vocabulary, which is the case considered in this paper, i.e., vocabulary in-context learning (VICL). We demonstrate that VICL in single-layer Transformers, without positional encoding, does not possess the UAP; however, it is possible to achieve the UAP when positional encoding is included. Several sufficient conditions for the positional encoding are provided. Our findings reveal the benefits positional encoding from an approximation theory perspective in the context of ICL.
Intruduction
Transformers have emerged a dominant architecture in deep learning over the past few years. Thanks to their remarkable performance in language tasks, they have become the preferred framework in the natural language processing (NLP) field. major trend in modern NLP is the development and integration of various black-box models, along with the construction of extensive text datasets. In addition, improving model performance specific tasks through techniques such as in-context learning (ICL. 1 2), chain of thought (CoT) 3 4, and retrieval- retrieval-augmented generation (RAG) S has become a significant research focus. While practical success of these models and techniques well-documented, the theoretical understanding of why they perform well remains incomplete.
To explore the capabilities of Transformers in handling ICL tasks, approximation power. The universal approximation property (UAP) 6 has long been a key topic the theoretical study of neural networks (NNs), with much of the focus historically on forward neural networks (FNNs). Yun et al. [10] was the first to investigate the UAP of Transformers, serenceeto-sequene function could be approximated by Transformer
essential to examine their
demonstrating that any network with fixed positional encoding. Luo et al. [11] highlighted that a Transformer with relative positional encoding does not possess the UAP. Meanwhile, Petrov et [12] explored the role of prompting in Transformers, proving that prompting a pre-trained Transformer can act as universal functional approximator.
However, one limitation of these studies is that, in practical scenarios, the inputs to language models derived from a finite set embedded in high-dimensional Euclidean space commonly referred to as vocabulary. Whether examining the work on prompts in [I2] or the research on ICL in [4] these studies assume inputs from the entire Euclidean space, which differs significantly from the discrete nature of vocabularies used in real-world applications.
"Emil:: maiyq.mathe @ bnu.edu.cn. The first two authors made equal contributions to the paper.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.1 Contributions
Starting with the connection between FNNs and Transformers, we turn the finite restriction of vocabularies and study the benefits of positional encoding. Leveraging the UAP of FNNs, we explore the UAP of Transformers for ICL tasks two scenarios: one where positional encoding is used and one where it is not. In both cases, the inputs are from finite vocabulary. More specifically:
1. We first establish connection between FNNs and Transformers in processing ICL tasks (Lemma B). Using this lemma, we show that Transformers can function as universal approximators (Lemma where the context serves control parameters, while the weights and biases of the Transformer remain fixed.
2. When the vocabulary finite and positional encoding not used, we prove that single-layer Transformers cannot achieve the UAP for ICL tasks (Theorem 6
3. However, when positional encoding is used, becomes possible for single-layer Transform- ers to achieve the UAP (Theorem 7 In particular, for Transformers with ReLU or softmax activation functions, the conditions on the positional encoding are relaxed (Theorem 8)
1.2 Related Works
Universal approximation property. NNs, through multi-layer nonlinear transformations and feature extraction, are capable of learning deep feature representations from raw data. As neural networks gain prominence, theoretical iivettiaatiossesseciiae Related studies typically fall into two categories: those allowing arbitrary width with fixed depth [ 21. and those allowing arbitrary depth with bounded width [15] Since our study builds on existing results regarding the approximation capabilities of FNNs, we focus on investigating the approximation abilities of single-layer Transformers in modulating context for ICI. tasks. Consequently, our work relies more on the findings from the first category of research. The realization of the UAP depends on the architecture of the network itself, providing constructive insights for exploring the connection between FNNs and Transformers. Recently, Petrov et al. [12 also explored UAP in the context of ICL, but without considering vocabulary constraints or positional encodings.
into their UAP have intensified.
Transformers. The Transformer is a widely used neural network architecture for modeling se- quences (20)25). This non-recurrent architecture relies entirely on the attention mechanism to capture global dependencies between inputs and outputs [20]. The neural sequence transduction model is typically structured using encoder-decoder framework [26] 27
Without positional encoding, the Transformer be viewed as stack of N blocks, each consisting of a self-attention layer followed by a feed-forward layer with skip connections. In this paper, we focus on the case of single-layer self-attention sequence encoder.
In-context learning. The Transformer has demonstrated remarkable performance in the field of NLP, and large language models (LLMs) are gaining incrcasing popularity. ICL has emerged new paradigm in NLP, enabling LLMs to make better predictions through prompts provided within
the context 2 23 3D ICL delivers high performance with high-quality data at lower cost (32]34]
enhances vetrieval-augment
methods by prepending grounding documents to the input 35 and
effectively update or refine the model's 's knowledge base through well-designed prompts 36
Positional Encoding. The following explanation clarifies the significance of incorporating posi- tional encoding into the Transformer architecture. RNNs capture sequential order by encoding the changes in hidden states over time. In contrast, for Transformers, the self-attention mechanism is permutation equivariant, meaning that for any model f. any permutation matrix and any input the following holds: (x)())) = (f)))).
We aim to explore the impact of positional encoding on the performance of a single- Transformer when performing ICL tasks with a finite vocabulary. Therefore, we focus on analyzing existing positional encoding methods. There are fundamental methods for encoding positional information sequence within the Transformer: absolute positional encodings (APEs), (.PEs),e.. egg. [37 38
relative positional encodings (RPFs), e.g. (40) 39 and rotary positional embedding (RoPE) 42
The commonly used APE is implemented by directly adding the positional encodings to the word embeddings, and we follow this implementation.

---

UAP of ICL. To understand the mechanism of ICL, various explanations have been proposed. including those based on Bayesian theory 45 44
and gradient descent theory 445 Fine-tuning the Transformer through ICI. alters the presentation of the input rather than the model parameters, which driven by successful few-shot and zero-shot learning [46 47 This success raises the question of whether we can achieve the UAP through context adjustment.
Yun al. [[0] demonstrated that Transformers can serve as universal sequence-----sequence approx- imators, while Alberti et al. 48 extended the UAP to architectures with non-standard attention mechanisms. However, their implementations allow the internal parameters of the Transformers to vary, which does not fully capture the nature of ICL. In contrast, Likhosherstov et al. [49] showed that while the parameters of self-attention remain fixed, various sparse matrices can be approximated by altering the inputs. Fixing self-au attention parameters aligns more closely with practical scenarios and provides valuable insights for our work. However, this approach has the limitation of excluding the full Transformer architecture. Furthermore, Deora et al. [50] illustrated the convergence and general- ization of single-layer multi-head self-attention models trained using gradient descent, supporting the feasibility of our research by emphasizing the robust generalization of Transformers. Nevertheless, Petrov et al. [51] indicated that the presence prefix does not alter the attention focus within the context, prompting us to explore variations in input context and introduce flexibility in positional encoding.
1.3 Outline
We will introduce the notations and background results in Section Section 3 addresses the case where the vocabulary finite and positional encoding is not used. Section 4 discusses the benefits of using positional encoding. A summary is provided in Section All proofs of lemmas and theorems are provided in the Appendix.
2 Background Materials
We consider the approximation problem as follows. Given a fixed Transformer network, for any target continuous function f : - R& with a compact domain C. R we aim to adjust the content of the context that the output of the Transformer network approximate First, present the concrete forms and notations for the inputs of ICI. FNNs, and Transformers.
2.1
Notations
Input of in-context learning. In the ICL task, the given n demonstrations are denoted as 2 (x y for = 1, 2.., n. where (((i) E Rd, and y( E Rd. Unlike the setting in 13 14 where
() was related to (+) (for example y(()) = ((x()) for some function Φ), we do not assume any
correspondence between (+) and y()), (i,,, (()) and (()) are chosen freely. To predict the target at
query vector Rdd
(z,0) E Rdy, define the input matrix follows:
(1))) ())
(n) x (n) 0
Z = (2)) (2)
(0) 2)
lR (ddd+t)))((+111
(2))
Furthermore, let P N+ +d, represent positional encoding function, and define p(t)_
P(i). Denote the demonstrations with positional encoding as =! == +pl)) and zp = 2 2+p(+ p(n+1). The context with positional encoding can then be represented as:
(2)
Zp =
(1) 2p
(x) 2p
p
TP
E I (dl (2)
P
2
m)
U
y
y
yp
Additionally, we denote:
X
(1) (2)
[(m] xd
Xp
(1)
(n)
E RRd,.xn
(3)
T
I
Ip
()
2)
y(all
xd
Yp
Vp
yp
(2)
yp
E
R dy
(4)
3

---

Feed-forward neural networks. One-hidden-layer FNNs have sufficient capacity to approximate continuous functions on any compact domain. In this article, all the FNNS we refer and use are one-hidden-layer networks. We denote a one-hidden-layer FNN with activation function N and the of all such networks is denoted as No, L.e.
No {No= Ao + b) A E R xk W E R
R b E KENt}
(5)
N Σ (wr x + b:) (a,, wi, b.) E Rd Rh x X kR
For element- wiine activations, such ReLU, the above notation is well-defined. However, for non- element- -eisent-wiseee activation functions, which are not widely used but considered in this article, especially the softmax activation, need to give more details for the notation:
a
N /softmax
Nsottmax
(as, Wi, bi) E IR
x R x R, KENt
(6)
Transformers.
We define the general attention mechanism following 13 14 as:
xtt == VZMa((QQ)) KZ),
where V, Q, K are the value, query, and key matrices in ((d++d))((4.4d))) respectively. M diag( n. 0) is the mask matrix in R(*+1)x(*+1) and a is the activation function. Note that the context vectors 200) are asymmetric and do not include the query vector itself; therefore, we introduce mask matrix M following the design of 13 14]. Here the softmax activation of a matrix G E RR mxn defined
exp (G..)
(coftmax(G)),
(8)
exp (G1.5)
With this formulation of the general attention mechanism, we can define a single-layer Transformer without positional encoding as:
T T (x; X, Y) = (Z VZMa((QQ))
(Z))))) KZ)) Idd
(9)
where (a b. d) denotes the submatrix from the a-th row to the b-th row and from the e-th column the d-th column. If b (or c = d), the row (or column) index reduced to a single number. Similarly to the notation for FNNs, T denotes the set of all T with different parameters.
Vocabulary. In the above notations, the tokens in context of ICL are general and unrestricted. When we refer to "vocabulary", we mean that the tokens are drawn from a finite set. More specifically, we refer as VICL In this case, we use subscript *, i.e., T7 (2;; X, Y), to represent the Transformer T (z; X, Y) defined in equation
input vectors 2 come from a finite vocabulary
V x Vy C Rdz x Rdy,
p. and denote the set of such Transformers as T."
T = (T) == (2; X,Y) 200) EV, E (1,2, ................................ .n.............................. n E
(10)
To facilitate the simplification of VICL analysis, denote FNN with finite set of weights N and the corresponding set of such networks as No. More specifically, when the activation function is an elementwise activation, we denote:
NI
No
arolwn bi) (ai, wi, b.) E B.AXWxBkEEN
(11)
where AC Rd W C Rds, and B R are finite sets. When the activation function is softmax, denote:
N /sottmax
softmax
B. (12)
where A, W and B are defined as in the previous context.

---

Positional encoding. When positional encoding P is involved, we add the subscript L...
ThP (T; = T (xp; Xp, Yp) 2(4) E ViiE E (1, E N+).
(13)
Note that the context length in T Tę and Tr are unbounded.
We present all our notations in Table I in Appendix for easy reference.
2.2 Universal Approximation Property
The vanilla form of the UAP for FFNs plays crucial role in our study. Before we state this property as formal lemma, we put forward the following assumption first, which is similar the one in [4 and is used to simplify the analysis of Transformers.
Assumption 1. The matrices Q, K, V E R xdz)) have the following sparse partition:
=
B 0
k= 0 -
0
C V
D F
UJ
(14)
where B, C, D E Rdx, E E Rdixdy, E Rddxdd and U E Rdyxdy, Farthermore, the matrices B, C and U non-singular. and the matrix F 0.
In addition, we assume the element- wise activation is non-polynomial, locally bounded, and continuous. It is worth noting that randomly initialized n matrix is non-singular with probability one, so it is acceptable to assume that the matrices B, and are non-singular. Morcover, the assumption F = 0 can be relaxed, which will be discussed in Appendix F. Here, we have slightly strengthened for the sake computational convenience.
Lemma 2 (UAP of FNNs (9). Let R - TR. be non-polynomial, locally bounded, piecewise continuous activation function. For any continuous function f IRd= - IRd defined on compact domain K, and for any there exist N+, A 12d, b RR and W E gexd, such that
|Ao f(x)] < Va
(15)
The theorem presented above is well-known and primarily applies to activation functions operating element-wise. However, can be readily extended the case of the softmax activation function. In fact, this can be achieved using NNs with exponential activation functions. The specific approach for this generalization is detailed in Appendix
2.3 Feed-forward neural networks and Transformers
It is important to emphasize the connection between FNNs and Transformers, which will be repre- sented in the following lemmas and are crucial for establishing our main theory.
Lemma 3. Let lR + R be non-polynomial, locally bounded, piecewise continuous activation function, and T be a single-laye Transformer satisfying Assumption]] I For any one-hidden-layer network No -Rd=-1 Rdd No with n hidden neurons, there exist matrices X Rd and
Y E Bdy xn such that
T (E: (x), VI E 12d-1
(16)
There is difference in the input dimensions of T and No as the latter includes a bias dimension absent in the former. To connect the two inputs, f and we use a tilde, where T is formed by augmenting I with an additional one appended to the end.
By employing the structure of K, Q and V in equation T" ( X, Y) can be simplified as follows:
[4). the output forms of the Transformer
X Y 0
DX + EY FX+UY
B (
0f of [XTBTOX CTC TT ))
T X,,
+
(FX + (X B CJ) BY
(17)
Comparing this with the output form of FNNs, i.e., No Ao(Wa b), becomes evident that setting X (C B)- IW bj] and Y U-1A is sufficient to finish the proof.
5

---

It can be observed that the form in equation (17) exhibits the structure of an FNN. Consequently, Lemmaßiimplies that single-layer Transformers T in the context of ICL and FNNS N are equivalent. However, this equivalence does not hold for the case of softmax activation due to differences in the normalization operations between FNNs and Transformers. Therefore, in the subsequent sections of this article, we employ different analytical methods to address the two types of activation functions.
Moreover, the equivalence in equation (16) suggests that the context Transformers can act as control parameter for the model, thereby endowing it with the UAP.
2.4 Universal Approximation Property of In-context Learning
We now present the UAP of Transformers in the context of ICL.
Lemma 4. Let a R + R be polyoooll,,,al, locally bounded, piecewise continuous activation function or softmax function, and T be a single-layer Transformer satisfying Assumption 7 and K. be compact domain in Rdo-1_ Then for any continuous function f : - TR.d and any >> 0, there exist matrices X E Rddxx and Y E Rdy x' such that
T [T; - f(x)]l <, Ex
(18)
For the case of dlement-wise activation, the result follows directly by combining Lemma 2 and Lemma 3 However, for the softmax activation, the normalization operation requires an additional technique the proof. The core idea is to construct an FNN with exponential activation func- tions, incorporating an additional neuron to handle the normalization effect. Detailed proofs are provided in Appendix B Similar results have been obtained in recent work [1], though via different methodologies.
3 The Non-Universal Approximation Property of N and T.¹
One key aspect of ICL is that the context can act as a control parameter for the model. We now consider the case where the tokens in context are restricted to finite vocabulary. A natural question arises: can single-layer Transformers with a finite vocabulary, i.e., T., still achieve the UAP via ICL? We first analyze Nº" for simplicity, and then use the established connection between FNNs and Transformers to extend the result to T The answer is that No" cannot achieve the UAP because of the restriction of finite parameters.
For element-wise activations, the span of NV span (Na), forms a minee-dimensional function space. According to results from functional analysis. span (NN)) is closed under the function norm (see e.g. Theorem 1.21 of [52] or Corollary C.4 of (53). This implies that the set of functions that can be approximated by span(AV) } is precisely the set of functions within span J. Consequently, any function not span(W?) cannot be arbitrarily approximated, meaning that the UAP cannot be achieved.
For softmax networks, the normalization operation introduces further limitations. Even though Nsoftmax consists of weighted units drawn from a fixed finite collection of basic units, normalization prevents these networks from being simple linear combinations of one another. While the span of A/ (softmax might theoretically have infinite dimensionality. its expressive power remains constrained.
To better understand the functional behavior of /roftmax, we introduce the structural Proposition 12 whose details are provided in Appendix C The proposition characterizes the maximum number of zero points that functions in this class can exhibit, and the result can be established via mathematical induction. This observation motivates the following lemma, which formally states the non-universal approximation property of N
The function class No, with a non non- non-polynomial, locally bounded. piecewise continuous element-wie wise activation function or softmax activation function o, cannot achieve the UAP. Specifi- cally, there exist a compact domain K C R.d., a continuous function f K. -> IR. and Eo > 0 such that
Lemma 5.
max [](()) (o) 2 So: Y NN N zek
(19)
In the proof of Lemma 5
we demonstrated through Proposition 12 that the number of zeros of Nsoftmax depends solely on finite set of parameters and constitutes a bounded quantity. Functions

---

can be explicitly constructed whose number of zeros exceeds this bound, thereby preventing their approximation within N Vsoottmax
By leveraging the connection between FNNs and Transformers, we establish Theorem 6 strate that T cannot achieve the UAP.
to demon-
Theorem 6. The function class T. with a non-polynomial. locally bounded, piecewise continuous element-wise activation function or softmax activation function a and every T E T satisfies
Assumption 1 cannot achieve the UAP. Specifically, there exist compact domain K. C &R= continuous function f KC + R and Eo 0 such that
sEK max [ -
T2 (+)] 80: VT.TT.
(20)
The result for element-wise activations follows directly from the application of Lemma and Lemma [ However, the case of the softmax activation requires additional techniques to account for the normalization effect. The proof, which utilizes Proposition [2) once again, is presented in the Appendix C It worth noting that Theorem hollds even without imposing any constraints on the V. Q and K (e.g., the sparse partition described in equation (14)). Further details can be found in Appendix
The Universal Approximation Property of T.P
After establishing that neither No nor T," can achieve the UAP, we aim to leverage a key feature of Transformers: their ability incorporate APEs during token input. This motivates us investigate whether T.Pp can realize the UAP.
The answer is affirmative. To support our constructive proof, we invoke the Kronecker Approximation Theorem as key auxiliary tool, which will be stated as Lemma [3] This result ensures the density of certain structured sets in I" under mild arithmetic conditions. The formal statement and discussion of this theorem are provided in Appendix
Theorem 7. Let TCp be the class of functions Tú,p satisfying Assumption 7
with non-polynomial, locally bounded, piecewise continuous element-wise activation function a, The subscript refers to the finite vocabulary V Vn Vy, P =P Py represents the positional encoding map, and denote set S as:
S V, + Pa = =f { P(y) I; E E.V i, i,JENT)
(21)
If dense in Rd=, (1, 11 V2, 03 C Vy and Py O, then Túpp can achieve the UAP. More specifically, given a network T2,p, then for any continuous function f: -Rd.- + Rd, defined on compact domain KC and > there always exist X E [Rd2 xn and Y E Rd,xx from the vocabulary V. i.e. (6) E Van ( E Vy, with some length n. E N+ such that
T (i: f(x)]] <E, Vx E.
(22)
We provide a constructive proof in Appendix C and here we only demonstrate the proof idea by considering the specific case of dy and assuming the matrice U in the Transformer To is an identity matrice. In this case, the Transformer can be simplified to an FNN Ng, that is
To (x;(x;; -po (X (X,BB C#) Σ
16 (BD)+PL))BBC..
(23)
which is similar to the calculation equation (17). The UAP of FNNs shown Lemma implies that the target function f can be approximated by an FNN with l hidden neurons, that is
N' (x) = Ao + b) Σ (w, x x
a.o :).
2. i=1
(24)
Since we are considering continuous activation function we can conclude that slightly perturb-
ing the parameters and W will lead new FNN that can still approximate f. This motivates us to construct a proof using the property that each W; dd can be approximated by vectors
7

---

Bp C, BT,'C,, E S V/2 + Pz, and each as E R can be approximated by vv2 = 44 with positive integers 9; and 4,
For ease of exposition, we will first show how to construct X and Y, so as to approximate the first term in the summation in equation (24). namely 01d (0 .i). By Lemma 13 we may choose positive integers q and I such that gv2 = I is sufficiently close to d1. Consider the first token in the context, since the positional encoding is fixed, i.., V2 + p(U) a finite set, then one of two cases must occur:
1. if there exists token z²() E V₂ for which x(1) + p()) is sufficiently close ū1, then declare this position "valid";
2. otherwise, we declare the position "invalid", and choose any x(1) Vz, and set y() 0 so as to nullify its contribution in the sum.
We then proceed inductively: having handled the first token, we construct the second token in exactly the same manner, then the third, and so on, until we have identified q valid positions. Because $ is dense in Rd and q, I are finite, this selection process necessarily terminates after finitely many steps. Finally, assign y 2 for q of the valid positions and y #1 for other / valid positions. Up to now, we have built a partial context that enables the output of T to approximate a1 [ 2)
with arbitrarily small error. Once we have approximated a a c -.), we can then approximate aga (i1g i),.. ag [ix 3) in finitely many steps, therehy completing the construction of the full context X and Y. In the proof idea above, we take the density of the set S in Rd as fundamental assumption. V2 contains only fimitely many elements, rendering it bounded. For S to be dense in the entire space, Pa, must be unbounded. We further extend the above approach to discuss whether other forms of positional encoding can also achieve the UAP in Appendix E.4
Next, we relax this requirement, eliminating the need for Pa to be unbounded, making the conditions more aligned with practical scenarios. Particularly, we consider the specific activation function in the following theorem, where the notations not explicitly mentioned remain consistent with those in Theorem We present an informal version, and the formal version is provided in Appendix E Theorem 8 (Informal Version). the S is dense in [-1, [],, then TReLU is capable of achieving the UAP Additionally, if S is only dense in a neighborhood B(w", 88) of a point w" E R with radius 5 > 0, then the class of transformers with exponential activation, i.e. Typ,, is capable of achieving the UAP.
The density condition S is significantly refined here, which we will discuss in the later remark. This improvement is possible because the proof of Theorem relies directly on the UAP of FNNs, where the weights take values from the entire parameter space. However, for FNNs with specific activations, we can restrict the weights to a small set without losing the UAP.
For ReLU networks, we can use the positive homogeneity property, i.e., AReLU(Wa) X- (RWLU for any X > 0, to restrict the weight matrix W. In fact, the restriction that all elements of W take values in the interval [-1, does not affect the UAP of ReLU FNNs because the scale of W can be recovered by adjusting the scale of A via choosing a proper A.
For exponential networks, the condition on S is much weaker than in the ReLU case. This relaxation is nontrivial, and the proof stems from a property of the derivatives of exponential functions. Consider the exponential function exp(w x) as function of w E B(w", , 5), and denote it as h(w),
E Rd. d = dz. where we and x; E IR are the components of w and x, respectively. Calculating the partial derivatives of h(w), we observe the following relations:
(w) = exp(w r) +
(25)
ghh Owa
glal
h(w),
(26)
Oul
where a (ais..., aa) E No is the index vector representing the order of partial derivatives, and Jal := 0i +... + ou- This relationship allows us to link exponential FNNs to polynomials since any polynomial P(x) can be represented in the following form:
gla
P(x) exp ( (- 1-ww-o xx)
Σ
ae
Owa
(27)
8

---

where are the coefficients of the polynomials, A is a finite set of indices, and the partial derivatives can be approximated by finite differences, which are FNNs. For example, the first-order partial x1h(w") can be approximated by the following difference with small derivative Then w==w
ah
nonzero number E (0,8),
h(w" + Xe1) h(w") = =x exp((w> + xee)) -2)))=2)- x exp("" 2).
(28)
A
This is an exponential FNN with two neurons. Finally, employing the well-known Weieeeeeisssssass Theorem, which states that any continuous function I on compact domains can be approximated by polynomials, and combining the above relations between FNNs and polynomials, we can establish the UAP of exponential FNNs with weight constraints. When y = related), the conclusion still holds in standard ICL, provided that Vy satisfies certain conditions. A brief proof is provided in Theorem [5]
f(x(1) (referred to meaningfully
Remark 9. When discussing density, one of the most immediate examples that comes to mind is the density of rational numbers in RR. How can we effectively enumerate rational numbers? The work by [54] introduces an elegant method for enumerating positive rational numbers, synthesizing ideas from (55) and [56]. It demonstrates the computational feasibility of enumeration through an effective algorithm. Thus, we assume that positional encodings can be implemented using computer algorithms, such as iterative functions. Furthermore, since positional encodings vary across different positions, they encapsulate semantic information concerning both position and order.
5 Conclusion
In this paper, we establish a connection between FNNs and Transformers through ICL. By leveraging the UAP of FNNs, we demonstrate that the UAP of ICL holds when the context is selected from the entire vector space. When the context is drawn from a finite set, we explore the approximation power of VICL, showing that the UAP is achievable only when appropriate positional encodings are incorporated, highlighting their importance.
In our work, we consider Transformers with input sequences of arbitrary length, implying that the positional encoding Pa consists of a countably infinite set elements. In Theorem] we assume a strong density condition, which is later relaxed in Theorem 8 However, in practical applications, input sequences are finite and are typically truncated for computational fcasibility. This shift allows conclusions to be interpreted through an approximation lens, where the objective is to approximate functions within a specified error margin, rather than achieving infinitesimal precision. Additionally, to achieve the UAP, it is insightful to compare the function approximation capabilities of our approach (outlined in Lemma 44) with the direct use of FNNs, particularly when the Transformer parameters trainable.
is important to note that this paper limited to single-layer Transformers with APEs, and the main results (Theorem ( and Theorem 8 focus clement- wise activations. Future research should extend these findings to multi-layer Transformers, general positional encodings (such as RPEs and RoPE), and softmax activations. For softmax Transformers, our analysis in Sections 2 and 3 hiighlighted their connection to Transformers with exponential activations. However, extending this connection to the scenario in Section S proves challenging and requires more sophisticated techniques.
Although this paper primarily addresses theoretical issues, we believe our results provide valuable insights for practitioners. In Remark 9 we observe that algorithms using function composition to enumerate dense numbers in IR could inspire positional encodings via compositions of fixed functions, similar to RNN approaches. RNNs capture the sequential nature of information by integrating word order. However, existing research on RNNs has not explored the denseness of the sets formed by their hidden states, which we hope will inspire future experimental research. Lastly, our construction for Theorem 7 relies on the sparse partition assumption in equation (T4), whose practical validity remains uncertain and requires future exploration.
In fact, Tack al. [57], Hao al. [58] on continuous CoTs and continuous states are closely related to our work specifically, leveraging positional encoding to enable Transformers to achieve the UAP for functions whose domain a finite set while the range covers the entire Euclidean space. Moreover, Xiao et al. [59 propose an approach for automatically adjusting prompts for function fitting, which also related to our theoretical findings. Therefore, with further research, our theory holds practical significance.

---

Acknowledgements
This work was partially supported by the National Key R&D Program of China under grants 2024YFF0505501 and the Fundamental Research Funds for the Central Universities. We thank the anonymous reviewers for their valuable comments and helpful suggestions. We gratefully acknowledge the Scholar Award from the Neural Information Processing Foundation.
References
[1] Q. Dong, L. Li, D. Dai, C. Zheng, J. Ma, R. L.. Xia. J. Xu. Z. Wu, Chang, X. Sun, L. Li, and Z. Sui, "A survey on in-context learning," arXiv preprint arXiv:2301.00234 2024.
[2] T. Brown, B, Mann, N. Ryder, M. Subbiah, D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry,
A. Askell, S. Agarwal, A. Herbert- Voss, G. Krueger, Henighan, R. Child, A. Ramesh, D. Ziegler. J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei, "Language models are few-shot learners," in Advances in Neural Information Processing Systems, 2020.
[3] J. Wei, X. Wang. D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. Chi, Q. V. Le, and D. Zhou, "Chain- of-thought prompting elicits reasoning in large language models," in Advances in Neural Information Processing Systems, 2022.
[4] 7. Chu, J. Chen, Q. Chen, W. Yu, T. He, H. Wang, W. Peng, M. Liu, Qin, and T. Liu, "Navigate through enigmatic lahyrinth survey of chain of thought reasoning: Advances, frontiers and future," " in Annual Meeting of the Association for Computational Linguistics, 2024.
[5] Y. Gao, Y. Xiong, X. Gao, K. Jia, J. Pan, Y. Bi, Y. Dai, J. Sun, M. Wang, and H. Wang. "Retrieval -ugmeette generation for large language models: A survey," arXiv preprint ftf::2312.10999.. 2024.
[6] G. Cybenko. "Approximation by superpositions of sigmoidal function." Mathematics of control, signals and systems, vol. 2. pp. 303-314, 1989.
[7] K. Hormik, M. Stinchcombe, and H. White, "Multilayer feedforward networks are universal approximators." Neural Networks, vol. 2, pp. 359-366, 1989.
[8] K. Hornik, "Approximation capabilities of multilayer feedforward networks," Neural Networks, vol. 4, pp. 251-257, 1991.
[9] M. Leshno, V. Lin, A. Pinkus, and S. Schocken, "Multilayer feedforward networks with a nonpolynomial activation function can approximate any function." " Neural Networks, vol. pp. 861-867, 1993.
[10] C. Yun, S. Bhojanapalli, A. S. Rawat, S. Reddi, and S. Kumar, "Are transformers universal approximators of requence-to-sequemee functions?" International Conference on Learning Representations, 2020.
[11] S. Luo. S. Li, S. Zheng, T.-Y. Liu, L. Wang, and D. He, "Your transformer may not be as powerful as you expect," in Advances in Neural Information Processing Systems, 2022.
[12] A. Petrov, P. Torr, and Bibi, "Prompting pretrained transformer can universal approximator"" in International Conference on Machine Learning, 2024.
[13] K. Ahn, X. Cheng. Daneshmand, and S. Sra, "Transformers learn implement preconditioned gradient descent for in-context lcarning," " in Advances in Neural Information Processing Systems, 2024,
[14] X. Cheng. Y. Chen, and Sra, "Transformers implement functional gradient descent to learn non-linear functions in context," in International Conference on Machine Learning, 2024.
[15] Z. Lu, H. Pu, F. Wang, Z. Hu, and L. Wang. "The expressive power of neural networks: A view from the width," in Advances in Neural Information Processing Systems, 2017.
[16] S. Park, C. Yun, J. Lee, and Shin, "Minimum width for universal approximation." in International Conference on Learning Representations, 2021.
[17] Y. Cai, "Achieve the minimum width of neural networks for universal approximation." in International Conference on Learning Representations, 2023.
[18] L. Li, Y. Duan, G. Ji, and Y. Cai, "Minimum width of leaky-relu neural networks for uniform universal approximation." in X305 2005..0 2024.
10

---

[19] Y. Cai, "Vocabulary for universal approximation: a linguistic perspective of mapping compositions." in International Conference on Machine Learning, 2024.
[20] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, Jones, A. N. Gomez, F.. ukasz Kaiser, and I. Polosukhin, "Attention is all you need," in Advances Neural Information Processing Systems, 2017.
[21] J. Devlin, M.-W. Chang. K. Lee, and K. Toutanova, "Bert: Pre-training of deep bidirectional transformers for language understanding." in Annual Meeting of the Association for Computational Linguistics, 2019.
[22] Z. Yang. Z. Dai, Y. Yang. J. Carbonell, R. R. Salakhutdinov, and Q. V. Le, "XInet: Generalized autore- gressive pretraining for language understanding," in Advances Neural Information Processing Systems. 2019.
[23] C. Raffel, N. Shazeer, A. Roberts, K. Lee, Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu, "Exploring the limits of transfer learning with a unified text-to-texi transformer," Journal of Machine Learning Research, vol. 21, pp. 1-67, 2020.
[24] L. Zhenzhong, C. Mingda, G. Sebastian, G. Kevin, S. Piyush, and S. Radu, "Albert: A lite bert for self- supervised learning of language representations," in International Conference on Learning Representations, 2021.
[25] X. Liu, H.-.. Yu, I. Dhillon, and C.-J. Hsieh, "Learning encode position for transformer with continuous dynamical model," in International Conference on Machine Learning, 2020.
[26] D. Bahdanau, K. Cho, and Y. Bengio, "Neural machine translation by jointly learning to align and translate," arXiv preprint 100.::4409.047: 2014.
[27] 1. Sutskever, O. Vinyals, and Q. L.,. "Sequence to sequence learning with neural networks," " in Advances in Neural Information Processing Systems, 2014.
[28] A. Chowdhery, S. Narang. J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, W. Chung, C. Sutton, S. Gehrmann, P. Schuh, K. Shi, S. Tsvyashchenko, J. Maynez, A. Rao, P. Barnes, Y. Tay, N. Shazeer, V. Prabhakaran, E. Reif, N. Du, B. Hutchinson, R. Pope, J. Bradbury, J. Austin, M. Isard, G. Gur-Ari, P. Yin, T. Duke, A. Levskaya, S. Ghemawat, S. Dev, H. Michalewski, X. Garcia, V. Misra, K. Robinson, I. Fedus, D. Zhou, D. Ippolito. D. Luan, H. Lim, B. Zoph, Spiridonov, R. Sepassi, D. Dohan, Agrawal, Omernick, A. M. Dai, T. S. Pillai, M. Pellat, A. Lewkowycz, E. Moreira, R. Child, Polozov, Lee, Z. Zhou, X. Wang. B. Saeta, M. Diaz, O. Firat, M. Catasta, J. Wei, K. Meier-Hellsterr D. Eck, J. Dean, S. Petrov, and N. Fiedel, "Palm: Scaling language modeling with pathways." Journal of Machine Learning Research, vol. 24, pp. 1-113, 2023.
[29] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, A. Rodriguez, A. Joulin, E. Grave, and G. Lample, "Llama: Open and efficient foundation language models," arXiv preprint arXiv:2302.13977 2023.
[30] OpenAI, J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkuya, F. L. Aleman, D. Almeida, J. Altenschmidt,
S. Altman, Anadkat, R. Avila, I. Babuschkin, S. Balaji. V. Balcom, P. Baltescu, H. Bao, M. Bavarian,
J. Belgum, I. Bello, J. Berdine, G. Bermadett-Shaprro, C. Berner, L. Bogdonoff, O. Boiko, M. Boyd, A.-L. Brakman, G. Brockman, T. Brooks, M. Brundage, K. Button, T. Cai, R. Campbell, A. Cann, B. Carey, C. Carlson, R. Carmichael, B. Chan, C. Chang. F. Chantzis, D. Chen, S. Chen, R. Chen, J. Chen, M. Chen, Currier, Y. Dai, C. Decareaux, N. Deutsch, D. Deville, A. Dhar, D. Dohan, S. Dowling. S. Dunning. A. Ecoffet, A. Eleti, T. Eloundou, D. Farhi, I.. Fedus, N. Felix, S. P. Fishman, J. Forte, I. Fulford, I.. Gao, F. Georges, C. Gibson, V. Goel, T. Goginemi, G. Goh, R. Gontija-Lopes, J. Gordon, M. Grafstein, S. Gray, R. Greene, J. Gross, S. S. Gu, Y. Guo, C. Hallacy, J. Han, J. Harris, Y. Hc, M. Hcaton, Heidecke, C. Hesse, A. Hickey, W. Hickey, P. Hoeschele, B. Houghton, K. Hsu. S. Hu. X. Hu. Huizinga. S. Jain, S. Jain, J. Jang, A. Jiang, R. Jiang. H. Jin, D. Jin, S. Jomoto, B. Jonn, H. Jun, T. Kaftan, Lukasz Kaiser, A. Kamali, I. Kanitscheider, N. S. Keskar, T. Khan, L. Kilpatrick. J. W. Kim, C. Kim, Y. Kim, J. H. Kirchner, J. Kiros, M. Knight, D. Kokotajlo. Lukasz Kondraciuk, A. Kondrich, A. Konstantinidis, K. Kosic, G. Krueger, V. Kuo, M. Lampe, I. Lan, T. Lee, J. Leike, J. Leung, Levy, C. M. Li, R. Lim, M. Lin, S. Lin, M. Litwin, Lopez, R. Lowe, P. Lue, A. Makanju, K. Malfacini, S. Manning, T. Markov, Y. Markovski, B. Martin, K. Mayer, A. Mayne, B. McGrew, S. M. McKinney, C. McLeavey, P. McMillan, J. McNeil, D. Medina, A. Mehta, J. Menick, L. Metz, A. Mishchenko, P. Mishkin, V. Monaco, E. Morikawa, D. Mossing, T. Mu, M. Murati, O. Murk, D. Mély, A. Nair, R. Nakano, R. Nayak, A. Neelakantan, R. Ngo, H. Noh, L. Ouyang. C. O'Keefe, Parascandolo,
B. Chess, C. Cho. C. Chu, H. W. Chung, D. Cummings,
Degry,
Parish, E. Parparita, A. Passos. M. Pavlov, A. Peng. A. Perelman, F. de Avila Belbute Peres, M. Petrov, H. P. de Oliveira Pinto, Michael, Pokorny. M. Pokrass, V. H. Pong. T. Powell, A. Power, B. Power, E. Prochl, R. Puri, A. Radford, J. Rae. A. Ramesh, C. Raymond, F. Real, K. Rimbach, C. Ross, B. Rotsted, H. Roussez, N. Ryder, M. Saltarelli,
Pachocki, A. Paino, Palermo, A. Pantuliano,
11

---

T. Sanders. S. Santurkar, G. Sastry, H. Schmidt, D. Schnurr. J. Schulman, D. Selsam. K. Sheppard, T. Sherbakov. J. Shich, S. Shoker, P. Shyam. S. Sidor, E. Sigler, M. Simens. J. Sitkin, K. Slama, I. Sohl, B. Sokolowsky. Song, N. Staudacher, F. P. Such, N. Summers, Sutskever, J. Tang. N. Tezak, M. Thompson, P. Tillet, A. Tootoonchian, E. Tseng. P. Tuggle, N. Turley, J. Tworek, J. F. C. Uribe, A. Vallone, A. Vijayvergiya, C. Voss, C. Wainwright, J. J. Wang. A. Wang, B. Wang, J. Ward, J. Wei, C. Weinmann, A. Welihinda, P. Welinder, J. Weng. L. Weng. M. Wiethoff, D. Willner, C. Winter, S. Wolrich, H. Wong. L. Workman, S. Wu, J. Wu, M. Wu, K. Xiao, T. Xu, S. Yoo, K. Yu, Q Yuan, W. Zaremba, R. Zellers, C. Zhang, M. Zhang, S. Zhao, T. Zheng, J. Zhuang, W. Zhuk, and B. Zoph, "Gpt-4 technical report," arXiv preprint 303::2333.08774,2000
[31] G. Xun, X. Jia, V. Gopalakrishnan, and Zhang, "A survey on context learning," " IEEE Transactions on Knowledge and Data Engineering, vol. 29, pp. 38-56, 2017.
[32] S. Wang, Y. Liu, Xu, Zhu, and M. Zeng, "Want to reduce labeling cost? gpt-3 can help." in Empirical Methods in Natural Language Processing, 2021.
[33] H. Khorashadizadeh, N. Mitindukulasooriya.. Tiwari, J. Groppe, and S. Groppe, "Exploring in-context learning capabilities of foundation models for generating knowledge graphs from text," arXiv preprint (rXiv:2305.08800 2023.
[34] B. Ding, C. Qin, L. Liu, Y. K. Chia, B. Li, S. Joty, and L. Bing, "Is gpt-3 a good data annotator?" Annual Meeting of the Association for Computational Linguistics, 2023.
[35] O. Ram, Y. Levine, I. Dalmedigos, D. Muhlgay, A. Shashua, K. Leyton- Brown, and Y. Shoham, "In-context correvvalaugmmented language models," in Annual Meeting of the Association for Computational Linguistics, 2023.
[36] N. De Cao, W. Aziz, and I. Titov, "Editing factual knowledge in language models," in Empirical Methods in Natural Language Processing, 2021.
[37] P. He, X. Liu, J. Gao, and W. Chen, "Deberta: Decoding-enhanced International Conference on Learning Representations, 2021.
enhanced bert with disentangled attention," in
[38] B. Wang, L.. Shang, C. Lioma, X. Jiang, H. Yang. Q. Liu, and G. Simonsen, "On position embeddings in bert," in International Conference on Learning Representations, 2021.
[39] G. Ke, D. He, and T.-Y. Liu, "Rethinking positional encoding in language pre-training." in International Conference on Learning Representations, 2021.
[40] P. Shaw, J. Uszkoreit, and A. Vaswani, "Self-attention with relative position representations"" in Annual Meeting of the Association for Computational Linguistics, 2018.
[41] Z. Dai. Z. Yang. Yang, Carbonell, Q. Le, and R. Salakhutdinov, "Transformer-xl: Attentive language models beyond a fixed-length context," in Annual Meeting of the Association for Computational Linguistics, 2019.
[42] J. Su, M. Ahmed, Y. Lu, Pan, W. Bo, and Y. Liu, "Roformer: Enhanced transformer with rotary position embedding." Neurocomputing, vol. 568, p. 127063, 2024.
[43] S. M. Xie, A. Raghunathan, P. Liang, and T. Ma, "An explanation of in-context learning as implicit bayesian inference," in International Conference on Learning Representations, 2022.
[44] X. Wang. W. Zhu, M. Saxon, M. Steyvers, and W. Y. Wang. "Large language models are latent variable models: Explaining and finding good demonstrations for in-context learning," in Advances in Neural Information Processing Systems, 2024.
[45] D. Dai, Y. Sun, L. Dong, Y. Hao, S. Ma, Z. Sui, and F. Wei, "Why can GPT learn in-context? language models secretly perform gradient descent as meta-optimizers," in Annual Meeting of the Association for Computational Linguistics, 2023.
[46] J. Wei, M. Bosma, V. Zhao, K. Guu, A. W. Yu, B. Lester, N. Du, A. M. Dai, and Q. V. Le, "Finetuned language models are zero-shot learners," in International Conference on Learning Representations, 2022.
[47] T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa, "Large language models are zero-shot reasoners." in Advances in Neural Information Processing Systems, 2022.
[48] S. Alberti, N. Dern, L. Thesing, and G. Kutyniok, "Sumformer: Universal approximation for efficient transformers." Annual Workshop on Topology, Algebra, and Geometry in Machine Learning, pp. 72 86, 2023.
12

---

[49] V. Likhosherstov, K. Choromanski, and A. Weller, "On the expressive power of self-attention matrices." arXiv preprint wrXiv:2106.03764, 2021.
[50] P. Deora, R. Ghaderi, H. Taheri, and C. Thrampoulidis, "On the optimization and generalization of multi head attention." Transactions Machine Learning Research, 2024.
[51] A. Petrov, P. Torr, and A. Bibi, "When do prompting and prefix-tuning work? theory of capabilities and limitations," ," in International Conference on Learning Representations, 2024.
[52] W. Rudin, Functional Analysis. McGraw-Hie Hill Science, 1991.
[53] P. Cannarsa and T. D'Aprile, Introduction to Measure Theory and Fanctional Analysis.
Springer Cham,
2015.
[54] N. J. Calkin and H. S. Wilf, "Recounting the rationals," The American Mathematical Monthly, vol. 107, pp- 360-363, 2000.
[55] M. Stern, "Ueber eine zahlentheoretische funktion," Journal für die reine und angewandte Mathematik, vol. 1858, pp. 193-220, 1858.
[56] B. C. Berndt, H. G. Diamond, H. Halberstam, and A. Hildebrand, Analytic Number Theory: Proceedings of Conference in Honor Paul T. Bateman. Birkhäuser, 1990.
[57] J. Tack, Lanchantin, J. Yu, A. Cohen, I. Kulikov, J. Lan, S. Hao, Y. Tian, J. Weston, and X. Li, "I.m pretraining with continuous concepts," arXiv preprint arXiv:2502.08522 2025.
[58] S. Hao, S. Sukhbaatar, D. Su, X. Li, Z. Hu, J. Weston, Tian, and Yuandong. "Training large language models to reason in continuous latent space," arXiv preprint arXiv:2412.06769 2024.
[59] T. Z. Xiao, R. Bamler, B. Schölkopf, and W. Liu, "Verbalized machine learning: Revisiting machine learning with language models," Transactions on Machine Learning Research, 2025.
[60] T. M. Apostol, Modular Functions and Dirichlet Series in Number Theory (Graduate Texts in Mathematics, 41). Springer, 1989.
[61] G. Boole, A Treatise on the Calculus of Finite Differences.
Cambridge University Press, 2009.
13

---

A Table of Notations
We present all notations in Table ffo
for easy reference.
Table I: Table of Notations
Notations
Explanations
dus dy
Dimensions of input and output. Positional encoding. Context without positional encoding. Context with positional encoding P. Input without positional encoding. Input with positional encoding P. Vocabulary.
P
X,Y Y
Xp, Yp
Z
Zp
V
Ve, Vy
Vocabulary of (t) and y
Activation function.
#
Cardinality of a set.
No. No
One-hidden-layer FNN and its collection.
To T
Single-layer Transformer and its collection.
N No
One-hidden-layer FNN with finite set of weights and its collection.
T T
Single-layer Transformer with vocabulary restrictions and its collection. Single-layer Transformer with positional encoding, vocabulary restrictions, and its collection.
T T. T.P
The uniform norm of vectors, i.e., shorthand for || Ilao.
Append one to the end of i.e., .
B Proofs for Section 2
We provide detailed proofs of lemmas Section We will first directly prove Lemma using Lemma 2 Next, by similar method together with additional technical refinement, will establish Lemma Finally, leveraging Lemma we will prove Lemma
B.1 Proof of Lemma
Let : R + R be non-polynomial, locally bounded, piecewise continuous activation function, and T be a single-laye Transformer satisfying Assumption I For any one-hidden-layer network No Rdd-11 + Rdd No with n hidden neurons, there exist matrices X E Rd and
Lemma 3.
Y E Idd,xe xn such that
T (i; -
Vr E 4
(29)
Proof.
The output of T can be computed directly as (T X,Y) = (Z + Auin X, Y)) d,41d,
= =(z + VZMo(Z Q K (Z))), 4dd.
DX + Ey
0) oxXTBTCX) ((
o(X B BTCB) T
UY
a B BTC))
d,+1id, + +dy.
= -YYo(X T CTC)..
(30)
One can easily observe that the output closely resembles that of a single-layer FNN. Suppose Nº (x) AW + b) : gd=-1 + Rdy is an arbitrary single-layer FNN with & hidden neurons, where -1) E xk and b E R² We construct the context by setting its length to i.e., X E Bd Y iRd xk A straightforward calculation shows that choosing
X = (C B) W TT = A.
(31)
14

---

suffices to guarantee T (i; = N for all x E Rd-11
Remark 10. It is worth noting that in the above proof. the matrix F was set in accordance with Assumption | However, we emphasize that this is not a strict requirement. In fact, one can accommodate arbitrary F by choosing Y U- FX). The choice F 0 is made purely for computational convenience under our current assumptions, which is also discussed in Appendix
B.2 Proof of the UAP of Softmax FNNS
Before proving Lemma
demonstrate the UAP of softmax FNNs as supporting lemma.
Lemma 11 (UAP of Softmax FNNs). For any continuous function f 1Rd + 12 defined on compact domain K, and for any & > 0, there exists network Nsoftmax (x) Rd - Rd satisfying
|N (x) s(x)]] <s, ve EK
(32)
Proof. We first build a bridge connecting softmax FNNs and target function f using Lemma 2 can construct a network
We
Nexp Aexp(W +b) Σ are w.tbb
(33)
with & hidden neurons such that
max aEK
N Txp (x) - f(x)] < 2
(34)
where a, E R4, u/ E Rd b, E R. It therefore suffices to construct softmax FNN Nsoftmax (x) that approximates NxxP(x). This task amounts to eliminating the effect of the normalization in the softmax output.
Consider softmax FNN
k+1 a
Nsoftmax (z) softmax (W'r + bD)
1=
(35)
k+1
Σ
with &s + hidden neurons, where What 6/41 = 0, b1 (,(=) is sufficiently small such that
en(aat < 2k(1 max [xx)(
Vr K, i = 1,2, ... K
(36)
and w w; for = 1,2, k. This arrangement ensures that, in the denominators of each term in Equation (35). the first entries are arbitrarily small, while the + 1)-th entry exactly one. We then simply adjust A' so that the numerators coincide with those in Equation 33 and this can be
done by setting af = da
i= 1 k
With the formal construction now complete,
00
present more precise estimate of the approximation error as follows.
15

---

dee
[x)) Nsoftmax
0,6 oe +h
max z
Σ age w.
0,0 4
max
zER
Σ e u x4b, +1
(37)
max
||<*P(x))
max aEk
zE
Σ e
k
max
[x)]]
max
Σ
zER
zER
j=1
This leads to the conclusion that | proof.
(z) f(x)]l < E for all x K, thus completing the
B.3 Proof of Lemma
Lemma 4, Let a IR + R be non-polynomial, locally bounded, piecewise continuous activation function softmax function, and T be a single-layer Transformer satisfying Assumption [ and K. be compact domain in Rd.-1, Then any continuous function f K - IRdy and any > 0, there exist matrices X Rdd,xn and Y E Rdy xn such that
(a; f(x)] e, Vx
(38)
Proof. For clement-wise activation case, with the help of Lemma and Lemma 3 the conclusion follows trivially.
Then we handle the softmax case. Similarly, for any E O, we can construct softmax FNN Nsoftmax (z) with & hidden neurons, using Lemma 11 such that
max |N (x) [(x)) 2
(39)
We need to approximate this softmax FNN with a softmax Transformer. The computation proceeds as follows:
Toofmmux (T, X,Y)
DX + EY
0 0
[ cx X TTBTX ă Ci B ))
softmax
UY
(40)
dat dd.-d
i B Ci CT ))
-UY
softmax
1:m.
By comparing the output with that the exponential FNN, we find that there is an additional bounded positive term t(x) == exp (i B Ci) arising from the normalization process.
Choose the length of the context n k + and matrices X, Y such that
W b+ s1
X BTC
UY = [A 0],
(41)
16

---

k where 1 is all-ones vector and s is big enough, making
e B C2-s
Vo A.
(42)
2(1 + maX [Noftmaxxx)) [x)])
W
b + s1
Wx b s1
Then X BTB
and can compute the explicit form
0
of Teoftmax (#; (x;X, XY,Y
Y) as:
Σ a exp(w; x x bq +
Tsoftmax (2; X)) =
exp(w, by + 8) + exp(s) exp(ii_e B Cā)
(43)
Σ a4 exp(w: xx)
Σ exp(wy bU) - + BTC - 8)
We estimate the upper bound of the distance between Nsoftmax and Teoftmax, that is
max ||Nsoftmax (x) - softmmx (æ; XXT)II
ZER
k
Σ
G3 exp(mi: x + bb)
Σ
G3 exp(1t x +b)
1=1
max #EK
exp(w, + by) +1
> exp(wy I + bU) + 1+ exp((t B Ci -
b Σ j=1
exp(w, x bb) +1
|Nooltmax (x)] max aEK
max
exp(ur: x + bU) + + exp(X T BT Ca s)
(44)
exp(X B Ct - =)
soffmmax (x)]
max m
max aEK
exp( + b;) + 1 exp(x (Tp(TBBBe
B BTC Ca - s)
|N Nsootmmxx (x)]
max #EK [epp(T T B Ca - +)
max
#EK
2"
As consequence, have ||: (i; f[x)]] < for all x E KC, which finishes the proof.
C Proofs for Section
In this appendix, we provide detailed proofs of Proposition 12 Lemma and Theorem 6 presented in Section 3 We will first use induction to prove Proposition 12 and then employ this proposition together with a proof by contradiction to establish Lemma and Theorem 6
Proposition 12. The scalar function hx(x)) Σ are with as, b, E R, where the exponents b;
are pairwise distinct, and at least one a; is nonzero, has at most 1 zero points.
Proof. We prove this statement by induction. When 1 or 2, this can be proven easily. We suppose hx (x) has at most N 1 zero points. Now consider the case A N 1. Let hN+i(z)
17

---

E 0,44 Without loss of generality, assume that aN+1 o O. Thus, we can rewrite (x+1 as
(x) aN+1e xx 12 (1+
04 - elhn-bx+1))) aN-IIe "Ni1" g()).
ON+1
Then we process by contradiction. Suppose 1 (x) has more than N zero points, which implies g(x) has more than N zero points. Then, according to Rolle's Theorem, g (a:) must have more than
N zero points, which contradicts our assumption. Thus, hy+1 have at most N zero points, and the proof is complete.
Lemma 5
The function class No, with non non-pooynoaial. locally bounded, piecewise continuous
element-wee wise activation function or softmax activation function G, cannot achieve the UAP. Specifi- cally, there exist compact domain K C RRd., continuous function :.K. -> IR4,, and Eo >> 0 such that
max zEK
[1 (T) 2 Eo: VN E
(45)
Proof. For any element-wise activation o, span [N forms diiiee-imensional function space. [W is closed under the uniform norm as established by Theorem 2.1 from [52] and Corollary C.4 from [33 This implies that the set of functions approximable by span(N") is precisely the set of functions within span [W*}. Consequently, any function not in span (No) cannot be arbitrarily approximated, meaning that the UAP cannot be achieved.
Then we prove the softmax case. First, we simplify the problem to facilitate the construction of function that cannot be approximated. We observe that it suffices prove the UAP fails when the first input coordinate ranges over [0, 1] and all other coordinates are held fixed. Indeed, we can find the compact set K C Rdd containing
r.]. If we can show that A A does not achieve the UAP on [1] x 11 [4], then, by applying a suitable affine change of variables, it follows that UAP also fails on [0, x 1T)2 Consider continuous target function
d=
f [0. 1
II (4) + R, (21,02, ... ,xd,) ) fi(x1). 2=2
(46)
The reason why we consider such a target function is that every vector-valued function f(x1, Ta.) fa, (41..... , zdz)). If the UAP fails for f. it must fail for at least one of its scalar components. Hence it suffices to consider the one- dimensional (scalar) case. Morcover, since the values Ø2, ... Idd are fixed, the above reduction single-variee variable scalar function justified. We only need to demonstrate that there exists least one such function that cannot be approximated arbitrarily well by any Nsoftmax Asoottaa
can be represented as f(11,... _Id)) (fi(z)..... Id.). )................).. (Td,)
Then we will use Proposition 12 to complete the remainder of this proof. Before that, we need to rewrite the form the output gootmaax which
k
Σ
0ge wy
tbb
Naoftmax
(x)
(47)
Σ eny-
where (a,, Wi, 61) E A W B finite set and is the number of hidden neurons. Consequently, the set W x B is finite, and we denote it as N == #(W x B). By regrouping identical terms in the numerator, we can rewrite the equation as
Σ ā ttb
Nsoftmax (x)
(48)
Σ e.y
important to note that this transformation applies to any Nsoftmax M/soltmxx, ensuring that the number of summation terms in the numerator remains strictly bounded by N.
18

---

Finally, we construct function which cannot be approximated by such softmax networks. Assume continuous target function
9: 9:
[T - IR, (2,, ,Td.) + cos ((N + 1)TTI), 1=2
(49)
which has (N + 1) zero points. If N/uftmaxx achieves the UAP, we assumee that Nautimax E Msoftmax which satisfies [Nsoftmax gll - E 10. We denote if is even, and g(z) - if i is odd, which means Nsoftmax (2) 0.9 for
N+1 for = 0, N + 1. It easy
to verify that ((2))
even i and Nsottmax (2;) < -0 0.9 for odd i. According to the Intermediate Value Theorem, Nsoftmax has at least N + 1 zero points, which contradicts Proposition 12 And we finish our proof.
We will use Figure to provide readers with an intuitive illustration of why class of functions whose number zeros is bounded cannot achieve universal approximation.
N + 2
N+1
Figure 1: An illustration non-approximabiiity. The black curve represents the target function, which has N 1 zero points. The red curve represents sum of exponentials, which has no more than N zero points. If the UAP holds, then the red curve must pass near the N + 2 marked extrema in the figure. By the Intermediate Value Theorem, the function represented by the red curve would then have N zeros, which contradicts its intrinsic properties.
C.1 Proof of Theorem
The function class T with a non-polynomial, locully bounded, piecewise continuous element-wise activation function softmax activation function and every T E T satisfies Assumption ! cannot achieve the UAP. Specifically, there exist compact domain K. C IRd continuous function f K. + Rd,,, and ED > such that
Theorem
max - 2 EO: VT T.
(50)
Proof. For cases of element-wise activation, since T has a similar structure to N find that span [T2} is also finite-dimensional function space. Hence, the same argument from Lemma can be applied here to complete the proof.
Then we prove the softmax case. Recall equation 440. the output of Tsoftmax (z; X,,) Y) can be viewed as
0 0.0 mcmb
moffmmax (5: X.Y)
(51)
euy + T CTC
where n denotes the context length and E A, w; E W. by E B for some finite sets A, W, B. This allows us to apply the same approach as the proof of Lemma which leads to the conclusion that T cannot achieve the UAP.
19

---

D Kronecker Approximation Theorem
To facilitate our constructive proof, we introduce the Kronecker Approximation Theorem as an auxiliary tool to support the main theorem.
Lemma 13 (Kronecker Approximation Theorem 660
Given real n-tuples a
(af" .2 ... On E Rn for = 1,.., m and B -(3,, B2, Pa) E IR", the following condition holds: for any > O, there exist qr l Z such that
Σ
Kiaj + +13
<e j j=
(52)
if and only if for any ri,"
In E Z, i= 1,... with
0 r EZ, -=
(53)
the number Σ Byr is also an integer. In the case of m 1 and n 1, for any a, 3 E R with j=1
irrational and ε > O, there exist integers I and q with q > 0 such that |8 qa + <.
Lemmal 13 indicates that if the condition in equation (33) is satisfied only when all r; are zeros, then the set [M g + 1 q Zm E Z" is dense R", where the matrix M E Rax is assembled with vectors a (6) i.e. M = (a (2)) ( ..... a (m)) In the case of m = and n = 1, let a = v2, then dense in R. We will build upon this
Lemma 13 implies that the set {qv2 / l N E [+} }
result to prove one of the main theorems in this article.
E Proofs for Section
In this appendix, we lay the groundwork for the proof of Theorem by first introducing Lemma [4 We then present Theorem 7 and provide its complete proof, demonstrating that T.,p can realize the UAP. To facilitate understanding of Theorem 7 provide simple illustrative example. While the theorem assumes dense positional encodings, we relax this condition under specific activation functions, as formalized Lemma 16 and Theorem
F. Lemma 14
Lemma 14. For network with fixed width and continuous uctivation function, it is possible to apply slight perturbations within an arbttrarily small error margin. For any network N₃ (a) defined on a compact set K. Rds with parameters A E Bdyxk W -kxxd,
1gx11 there
exists M > 0, Mr > 0 [[|==]| < M and [|aæ]| < M1, = 1, ... ,k), ), and for any > O, there exists 0 << 8 < 2M and a perturbed network (²(x) with parameters E Rdy xk W E BRkxxd= . b Rex1
[ (i x + b.) <
,k), such that if max {Ila: - aارة MIIws w. + Ibb ill
1.... .k} 8, then
| (x) Ng < Vr E,
(54)
where as āg are the i-th column vectors of A, A, respectively, ws, wi are the i-th row vectors of W, W and b,, by are the i-th components of b, b. respectively, for any i = 1,...
Proof. We have NT(x) = Σ 0:0 x bi), where a, E Rdy, wi E Rdd b, R. and Ng(x))
Ca. x + bi), where āj E RRd, w; E IRd, b. E R. For any E IC, |||||| < M. There exists
constant Mj > 0 such that for any = 1,... ,,, the following inequalities hold: ||ae|| < M1 and | x + b.)l Mi.
20

---

Due to the continuity of the activation function, for any > 0, there exists 0 < 8 < 2M such that
I|w; x + b; - (z0; x + b & Iwi, - d; ||| + ||b; - bull < Ml - willl + 166 bll < ö, then (lo x b,) o [i; x + b,)1l 2 and ||a
ās || < 8, for any = 1, k.
Combining all these inequalities, we can further derive:
(x) N2 Σ a (w, x x+
Σ ( x bb))
k
(w; x bi) Σ
(ws x bi)
Σ
a:0 x b.)
Σ
bi)
1m1
im1
im1
< max |
Σ
ow xI x x+bb)) bb)
Σ aw; bi)
+ max | - -I bi]l|
Σa; ai
03
k Σ
k
5 max ||::]
(w: . x + bi) - cwo; x + bi)
+ max | x + bi)
|0: T:ll
i=1
E + Mik
E
Mik 2M,
2M, k
(55)
The proof is complete.
E.2 Proof of Theorem
Theorem 7 Let Túpp be the class of functions Tú.p satisfying Assumption 7 with non-polynomial, locally bounded, piecewise continuous element-wise activation function o, the subscript refers the finite vocabulary V Vn Vg P =P= Py represents the positional encoding map, and denote
set S as:
S V +p, { xx++77 p(5) I I i, JENN-
(56)
If dense in Rds, {1, -1, V2, 03db C Vy and Py = O, then ThPp can achieve the UAP. More specificully, given nelwork T7,p. then for any continuous function f RRd.-1 - Rd defined
compact domain IC and > there always exist X E Idd xu and E x from the vocabulary V. i... (8)) E Va. E Vy, with some length n E N+ such that
T (i; f(x) <E, Vo
(57)
Proof. Our conclusion holds for all element wise continuous activation functions in TrPp. We now assume d, = 1 for simplicity, and the case dy * will be considered later.
We are reformulating the problem. Using Lemma
we have
T X,) = UYp -):
(XX+)) C$ = UYpo (x)B
(58)
Since P,, 0, it follows that Yp Y. For any continuous function f: -R - R.d defined
compact domain I. and for any 5 > 0, we aim to show that there exists T E Tr.p such that:
T
x
X, - Us(x)) < [1Ule, Vo E IC
(59)
+ || (XJ TT)) f(x) <E,
Va K.
In the main text, for illustrative purposes, consider the special case where U is the identity matrix to simplify the exposition. the present analysis, we dispense with this assumption. We already have the Lemma ensuring the existence of one-hidden-layer network N (with activation function
21

---

satisfying the required conditions) that upproximates fx)). Our proof is divided into four steps, serving as a bridge built upon the Lemma
Yo (XPBTCL Ct)
Lemina
(x)
(x)
(2)
(r)
(1)
f(z).
(60)
We present the specific details at each step.
Step (1): Approximating f() Using (z). Supported by Lemma 2 there exists neural network
No (x) Ao(W+++)) Σ a; a (wy x x+bbb b,) No, with parameters N+, Rd, E RR.,
and W E 1x
a + b) - s(x) < 3r Ve E.
(61)
Step (2): Approximating No (I) Using (1)).. Using Lemma 13 and Lemma 14 a neural network
No (x: = Σ (wo x + b.) E Na" can be perturbed into (( = Σ (av2 + 1): x + b.)
==1
(with E N+ and 4 E N+ i 1,..,,k, k), such that for any e > 0, there exists 0 < < 6M,
satisfying:
max{ (qv2 M.. w + 11 bl| li 1..................... ..) <
(62)
ensuring:
k || (x) (N))l
&
a ow +b) > 1) x xbb,) Σ
E
<
Ve E K.
3
(63)
Step (3): Approximating (z)) Using No (z). Next, we show that No (x) = Σ y o R 2) E
No can approximate (²)x) Σ (gv2+l)) o(;; 2). As demonstration, we approximate single
term (nv2 + l) (w -). Since the positional encoding is fixed, i.e., Va + p(1) is finite set, one of two cases must occur:
1. Valid Position: If there exists (1) Va where (x() + C
2. Invalid Position: Set y1) to nullify contribution.
Since S is dense in Rd and T C is non-singular, the set G = R C 2 remains dense. Let K2 denote the set of indices corresponding to all "valid" positions for wr Since (() E (1,-1, 11, v2, 0}, we require + I elements from G that approximate wn, such that
Σ 9 oRR .) (gV2+ 1)1 (w .)) JEKI
1IV2 Σ
oR,y +) Σ o(R, 2) - 2
(),
(64)
jEQi
jET.1
Vx E.K.
3k'
TT, where Q1, Tn are disjoint subsets of positive integer indices satisfying (Q1) = qi and #(L)) = 4. For this construction, we assign yاا) = 2 for j E QI and yاا = +1 for j E L.. For j E (1,2,3, max(i E KiJ) i.e., for the Invalid Position, set (0) 0.
Here, #(K)) = 0 91 1 and K1 = Qi Th,
22

---

The multi-tern term approximation employs parallel construction via disjoint node subsets K; Qi Li.
k
where Qi (q: nodes) and L, (1; nodes) implement v and +1 coefficients respectively. For $ U Kr. we set ( O. Each term achieves:
1=1
Σ
yo o -)) F)
<
E
(65)
3k
JEK,
We then define = max
lie
U
Ki).
The complete network combines these approximations
1=1
through:
[x] NN = Σ y 1 o
(R, 2)
2)
e <
va e K.
(66)
1=1
Step (4): Combining Results.
Combining all results, we have:
| a (X Ct) - f(x)]l = (x] - f(=)]l
[ - (+)) II
f(x)) (67)
< E, Vx E.
The scalar-output results (dy = 1) extend naturally to vector-valued functions via component- wise approximation. For any continuous f TRd,-1 - IRd on a compact domain K., uniform approximation is achieved by independently approximating each coordinate function fz with scalar networks N2,(() satisfying
(x) fz(ر]
&
(68)
Vdy
The full approximator is then obtained by concatenating the component networks.
(xx)
(+) =
[N] - f(x))l < E,
(69)
No,d, (x)
(x) Σ (6) y oRR 2)
(70)
(2) is the j-th row of the (0) We require that the index sets satisfy K(O) n k( 0 for all where Mj
o, u, i, N+, where k(O) denotes the index set constructed for the i-th term approximation in the o-th output dimension. Furthermore, each yاأ must have most one non-zero element across its dimensions. This ensures we achieve uniform approximation by independently handling each output dimension. The proof is complete.
E.3 Example of Theorem
We present a concrete example with 2D input (d,, = 2) and 2D output (d,, = 2) to illustrate the universal approximation capability of our architecture. Consider a continuous function f [0, 1]2 I defined by
(x1, x2) f2 x2))
(71)
Our goal to construct a module T such that
T
I2
X,Y
(211,
<E
(72)
23

---

Step (1): Component-wise Approximation. For each component fú, there exists a single-hiddens layer neural network Nę (a) (W, b,) such that
sup # [u
-
E 6v2
i= 1,
(73)
Step (2): Rational Perturbation.
We approximate each Nę by rational network N
(x) (3v/ - 2) u i), (2 - (2v/ + ()) 8),
(74)
(75)
where I
[2 222
1]', satisfying
sup zE|o.1
(x) - N(((I] < 6v2²
i= 1,2.
(76)
Step (3): Architecture Realization. representation:
We define Transformer-lik module Nọ (z) with shared
W1
W1
01
11
W2
W2
W2
(77)
V2
/2
2
0
Y
(78)
0
0
v2
V2
1
such that
(I(x) =
Σ -1= [ Σ 32
sup =E|0,1I
[N((2)
<
E
(79)
(R.
6/2²
Step (4): Error Analysis. The total approximation error satisfies
- NC
(11/: - - IN; XiI + IN; N2,
(80)
(81)
2 2
We argue that in standard ICL, when (0 (z)( (referred to meaningfully related) and V satisfies certain conditions, the UAP conclusion still holds. This conclusion relies on the density of S. and we provide concise argument based Theorem 7
Theorem 15. Lei Tí be the class of functions T satisfying Assumption with non-polynomial. locally bounded, piecewise continuous element-wise activation function o, the subscript refers the finite vocabulary V = Vo Vy, P Px Py represents the positional encoding map, and denote
set S as:
S r; P(1)
2 E i 1.JENt..
(82)
If S is dense RRd,, and there exists a subset Yo C Vy whose (finite) columnwise additive combina- lions contain the block-diagonal pattern in
V2
1
-1
0
0
0
0 ...
0
/2
1
1
0
0
...
0
0
0
0
2
-1
...
(83)
:
24

---

and Py = 0, then T..p. can achieve the UAP. More specifically, for any network T 1x,p. for any continuous function [gda-1 Rdy defined on a compact domain K. and any O, there exist X E Rd and E IR xn from the vocabulary V, i.e. x86 E Va, y E Vy, with some length N+ such that
T (i; f(x) <E, V
(84)
We reuse Steps (1)-(2) from the proof Theorem 7 focusing on understanding the third step. There exists subset Yo S Vy whose additive combinations of columns contain the pattern in Eq. (83). The role this structure is to enable cumulative approximation through additive combinations.
E.4 Feasibility of UAP under Different Positional Encodings
We also pay attention to more dynamic positional encodings such as RoPE, and are currently exploring appropriate analytical methods for them. Our recent progress on APEs has given us greater confidence in studying RPEs. Our analytical framework mainly relies on achieving density of the set axX B CT), in particular, on the richness of the term X B C. (See Lemma 3 and Theorem for supporting arguments).
For RoPE, whose basic formulation is given by equation (16) in 42
Om kn (Ro.m (mfmm) (R WLTN);
(85)
applying our approach yields
x B (R)
(86)
However, since the rotation operation in RoPE acts distinct two-dimensional subspaces of dz, the induced family {BT ( does not directly apply to RoPE. Consequently, prove that RoPE possesses similar approximation properties.
TC} does not generate a dense subset; hence our density-baxee argument
current method cannot be directly applied to
Likewise, other RPEs, such as the one defined in equation (4) of [40]
x; WQQ
W + +at)
Eiy
Vd=
(87)
cannot be analyzed using this approach either. Nevertheless, the encoding formulation in
41
Fx, + E
Wa,nRi + WK, + Wk.
(88)
(6)
(e)
(d)
can be accommodated within our framework and compatible with the UAP result.
E.5 Proof of Theorem
Before proving Theorem g we need to prove the following lemma with the help of the well-known Stone Weierstrass theorem.
Lemma 16. For any continuous function f 1Rds - Id defined compact domain K,, and for any E O, there exists a network (x)) Rdda + IR satisfying
[[ f(x)) <E,
Vz K.
(89)
where b = and all row vectors of W are restricted in a neighborhood B(w*, with any fixed u² E TR and radius 8 0.
Proof. Assume fxx (z), ... faz (xr).. According to
theorem, for any
8 >> 0, there exist polynomials (z) satisfying
[P((x)) fa(are f((a))e-'' =w'
max TER
2 mmax /0 2I
(90)
* max ( < 2'
i i= 1,2, d
zeR
25

---

Then we construct a single-layer FNN with exponential activation function to approximate P. The multiple derivatives of h(w) = e exp(wi 11 +... Wa, with respect to w1." Wdz are
ala Owa
glai
(91)
Owi
10 ... -.ud
adz
de
where Né, represents the index and aa| a1 + + O'dz Actually, the form of multiple derivative øl is a polynomial of |a| degree with respect to 21, ... ddd times h(w)). Hence, each Ow target term (rr)ee" -2 can be written as linear combination of such multiple derivatives of h(w), which allows us to approximate the required partials and thus complete the proof. Moreover, each mixed derivative can be approximated by finite-difference scheme, which can be implemented using a single hidden layer.
Remark 17. We give two examples of approximating multiple derivatives of h(w) below.
0h
zyh(w)= Owi w==""
h(w" + )e1) - -h(w")
(92)
+ +R1 +RI(A,")) -x-'h(w- + +Xez) ( x~h((w)) + R2(,,
and
82h
x102h(w)) = Ow, Ow2 1ommo
h(w" + M(e + c2)) - h(w" + Aee) - M(w" + Ae2) + ((ww)) + Be w²) (93)
=x-'h((w' + +(e + +2)) x) - ---1>((ww' + ^xE) (ea).00 x)-
A x-'n(("' + Ae2) x) + "(w"" xx) + R2(A, w²);
0), .0) error terms with respect to X and w According to Taylor's theorem, the error terms R3 R2(A, w²)= 8Ph Duy w=g some & between wt and w" + Xey. It is obvious that the partial differential term is uniformly bounded, so the resulting error can be made arbitrarily small by a suitable choice of the parameter X. The argument for R2(2, W*)is yis entirely analogous and is therefore omitted; see 167)
where = (1,0,0, ...
(0,
0) are unit vectors and R1 (),,""); Rg(A, w²) are
for further details.
Since À is very small and the exponential term e"" only involves the parameters w", w + e1 and w" ez, which all lie within a small neighborhood of w", the desired conclusion can be drawn, and this means we can in fact restrict all row vectors of W to lie within B(W,8).
Theorem 8 (Formal Version). Let T., be the class of functions T2,p satisfying Assumption with mon--polynen pommialaal, locally bounded, piecewise continuous element-wise activation function o, the subscript refers to the finite vocabulary V = V2 x Vy, P = Pe x Py represents the positional encoding map, and denote a set S as:
S Va + Pa.
{ D(1)
I, EVV 1,2.,,,1 iENN-
(94)
If the set S is dense in [-1, 1]d,, then T.RLLU is capable of achieving the UAP. Additionally, S is only dense in neighborhood B(w" 8) of a point w" E Rdd, with rudius ō > 0. then the class of transformers with exponential activation, i... T. is capable of achieving the UAP.
Proof. For the proof of the ReLU case, we follow the same reasoning as in the previous one, noting
that Raa) (z) holds for any positive a. In the proof of Theorem 7 we construct
TRELU (z; Y) E T.ReLU to approximate a FNN ReLUU(W x + B). Here we can do a similar
construction to find another TReLL (æ; X) E Tep to approximate XA RcLL (X- + b)) as the Step (2)-(4) in Theorem 7 where À is chosen sufficiently large such that the row vectors of W become small enough to ensure that (x: + P I3 and sufficient for our construction.
E V, i. N+) is dense [-1, 1]d.
26

---

For exponential Transformers, by using Lemma 16 we can do the Step (2) in Theorem aggain
which is similar to ReLU case.
Weakened Assumption and Generalized Conclusions
It is important to note that most of our conclusions remain valid even if Assumption I is weakened. Below we outline the reasoning.
In general, we decompose the matrices as follows:
Q-K On 012
E U V
D = P
(95)
O21 On
where On1, D E Rdx O12; E E Rd,xdd, O21, F Rdyxds and Oz2, U Rd,dd, The attention mechanism can then be computed as:
Attn = VZMo(Z Q KZ)
D
E
X
I
X
Y
On
012
X x.]
Y
0
0
T
0
Oz
Oze
Y
0
(96)
DX + EY
0
O
(XT011 + (TOT2)
FX UUY
0
x
(Onx+00r))
x² Tno
where O represents the matrix X X
+OoZ As result, have:
( (xToI+t 021)
T xxx -FX
(97)
for the of element-wing activations, and:
Tsoftmax ( x) (FX softmax (1xT T Tnn (
021)²
1))
(98)
1:m
for the case softmax activation.
By revisiting the definition of T and T and comparing T presented here with those in the preceding section, is clear that the only distinction lies the specific matrices involved, and matrix O₁ and U are non-singular are the only conditions we need. Notably, the proof process for Theorem does not rely on any assumptions, which means the conclusion stated in Section can be further strengthened.
27

---

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: We outline and discuss the contributions and scope of our work the end of the Abstract and in a dedicated subsection L. the Introduction
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 around line 345 in Section
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].
28

---

Justification:
Our assumptions are clearly stated as Assumption 1 in Section 2 and Ap- pendix F and the proofs are provided Appendix B to Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced 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 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., 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?
29

---

Answer: [NA].
Justification:
This paper does not include experiments requiring code.
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
icy 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
/ ccpppi.ccppulli//uuuii wwwticccguie//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.
30

---

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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror 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 execution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 NeurlPS Code of Ethics https: htt////euripppp httpiips...ppppppeeee ctc//pbbiic/thhiccsiideeee.....d
Answer: [Yes].
Justification: This research is theoretical in nature and does not involve human subjects, per- sonal data, potentially harmful applications. All results derived through mathematical analysis and do not raise ethical concerns as outlined in the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in 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 paper focuses on the theoretical expressivity of Transformers under ICL and provides approximation results from mathematical perspective. We believe that discussing societal impact falls outside the scope of this foundational contribution.
Guidelines:
The answer NA means that there 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.
31

---

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 is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI...
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: This paper does not release any data, models, tools that pose risks of misuse or dual use. The work is purely theoretical and focuses on the UAP VICL with single-layer Transformers.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification: The paper does not use any external assets such as datasets, models, or third- party code. The research is purely theoretical and does not rely on pre-existing software or data resources.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.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 package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
32

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 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: This paper theoretical in nature and does not introduce or release any new datasets, models, software assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the datasct/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsoureing 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)?
Question:
Answer: [NA]
Justification: This paper does not involve any crowdsourcing or experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 to the NeurIPS Code Ethics, workers involved in data collection, curation, 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 involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
33

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA].
Justification:
The core method development in this research does involve LLMs
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non otandtaddrrd components.
Please refer to our LLM policy for what should or should not be described.
34


Reviews:
[{"review_id": "KAPtD2a3Q2", "reviewer": "Reviewer_fhka", "summary": "This theoretical paper investigates the universal approximation property (UAP) of transformers in the specific context of in-context learning (ICL), where the weights of the model are fixed and the input context serves as the parameters. Unlike prior work on the UAP of transformers that assumes continuous, infinite input spaces, this work assumes the input embeddings come from a finite vocabulary of vectors typical in language modeling tasks. By drawing connections to the UAP of single-layer neural networks, the authors show that a single-layer transformer without the input space constraints satisfies UAP, but fails to approximate all functions under the finite-input assumption. However, they prove that adding absolute positional embeddings (PE) restores the UAP, emphasizing the crucial role of PEs in enabling expressivity in this setting.", "questions": "In addition to discussing the issues raised above, could you clarify the role of the mask $M$ in Equation (7)? It seems it only zeroes out the last token in the sequence (i.e., the query). What is the motivation for using this particular masking?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "The paper offers a fresh perspective on the universal approximation property (UAP) of transformers by focusing on a more realistic in-context learning setup, where inputs are drawn from a finite set of embeddings. This contrasts with previous work that assumes continuous input spaces and helps bridge theoretical insights with practical language modeling scenarios. While I did not follow every detail of the proofs, the sketches provided in the main text and a skim of the appendix suggest that the results are built on neat constructions and connections between neural networks and transformers.\n\nAt the same time, some of the assumptions and results appear to be quite strong:\n\nFor example, Lemmas 3 and 4 suggest that for any fixed transformer weights, there exists a prompt/context that enables the model to approximate any function, effectively achieving in-context learning even without training. While interesting, this seems far from what is typically observed in practice.\n\nSimilarly, the results on the role of positional embeddings (PEs) rely on the assumption of the set of input embeddings + position embeddings forming a dense subset of the space (see Eq. 21). Although Theorem 9 attempts to address this partially, both Theorems 8 and 9 seem to require infinite context lengths to satisfy the density condition, which raises questions about their practical relevance. I believe without this assumption, the UAP won't hold with an argument similar to Theorem 7. From my reading, the role of PE in the proof is essentially to break the finite-input limitation by expanding the support to a dense subset of the space, thereby enabling approximation of any target vector in the space—something not possible with a finite vocabulary alone. This is a clever theoretical construction, but this intuition may not be the reason behind why PEs can help generalization in practical transformer models.", "was_revised": true, "final_justification": "The paper presents solid theoretical results. I believe the rebuttal improved it by clarifying the scope and limitations of the findings through additional discussion of the modeling choices and possible extensions of the results. Some idealized assumptions remain, which may limit direct practicality, but with these added discussions, the scope and relevance of the work are much clearer.", "rebuttal": "We sincerely thank you for your positive recognition of our work and your insightful comments. We have carefully reflected on the limitations you pointed out, and would like to offer the following responses:\n\n1. **[About Lemmas 3 and 4]** You noted that *\"this seems far from what is typically observed in practice.\"* We agree that most existing theoretical and empirical studies focus on $\\mathcal{T}^{\\sigma}_{*,\\mathcal{P}}$, and we acknowledge that the constructed Transformers in Lemmas 3 and 4 may deviate from practical architectures. However, our intent is to demonstrate that the expressive power of positional encodings enables Transformers to approximate functions with high accuracy. While the construction may be idealized, we believe these lemmas lay a theoretical foundation for understanding how Transformers can achieve high-precision approximation using finite context in practice, and may inspire future analyses of deeper and more practical architectures.\n2. **[About Positional Encodings]** Your understanding of our density assumption concerning embeddings and positional encodings is entirely correct. Our setting is inspired by the contrast between the finite vocabulary of natural language and the potentially unbounded length of composed sequences, which motivates the need for expressive positional encodings. Although real-world models cannot handle infinitely long inputs, sufficiently long sequences can already allow the model to approximate the desired behavior. While this assumption is admittedly abstract, it serves to highlight the potential role of positional encodings in supporting the generalization capacity of Transformers.\n3. **[About the mask matrix $M$ in Equation (7)]** The design of the mask matrix $M$ follows previous work [1, 2]. As stated by the authors of [1]: *“Note that the prompt is asymmetric since the label for $x^{(n+1)}$ is excluded from the input. To reflect this asymmetric structure, the mask matrix $M$ is included in the attention.”* Our usage of $M$ follows the same motivation.\n\n[1] K. Ahn, X. Cheng, H. Daneshmand, and S. Sra, “Transformers learn to implement preconditioned gradient descent for in-context learning,” in Advances in Neural Information Processing Systems, 2024.\n\n[2] X. Cheng, Y. Chen, and S. Sra, “Transformers implement functional gradient descent to learn non-linear functions in context,” in International Conference on Machine Learning, 2024."}, {"review_id": "3RvGE3DEia", "reviewer": "Reviewer_7CdZ", "summary": "This paper investigated the connection between in-context learning (ICL) in single-layer transformers and universal approximation property (UAP). The main results show that with continuous prompt (e.g., $X$, $Y$), a single-layer attention mechanism can achieve UAP. However, when $X$ and $Y$ are restricted to a discrete set, namely a vocabulary in natural language, the model cannot achieve UAP through ICL alone.  The paper demonstrates that by adding positional encodings, the model can recover the UAP in this discrete setting.", "questions": "1. Does Lemma 4 hold for any choice of the number of demonstrations $n$?\n2. In Theorem 8, what exactly is the choice of the positional encoding $P$? Is $P$ independent of $(X,Y,x)$ or does it depend on them? Could you clarify it?\n  - If $P$ is universal, then $x+P$ lies in a finite set, and by Theorem 7 the model would not achieve UAP. \n  - If $P$ depends on the input, this implies that different inputs require different positional encodings, which is not ideal and seems inconsistent with how positional embeddings are used in practice. \n\n3. Have the authors considered the special case where $x^{(i)}\\equiv0$ in Theorem 8? Can the model still achieve UAP under this condition? If not what are the roles of $X$ and $P$?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The paper addresses the realistic setting where input prompts come from a discrete vocabulary, reflecting how tokenization works in practice.\n\n2. This work takes attention and ICL as function approximation, establishing an equivalence between FFNs and ICL when treating the input data as function parameters. \n\nWeaknesses\n\n1. In standard ICL, the examples $(x^{(i)},y^{(i)})$ are meaningfully related, and the query feature $x$ relies on the relationship captured by the demonstrations to predict its corresponding $y$. In this work, however, $(x^{(i)},y^{(i)})$ are chosen freely, so the entire matrix $Z$ can be seen as arbitrary function parameters. This breaks the connection to real-world ICL, where the sequential structure and feature-label dependencies are important. The paper would benefit from clarifying this point and discussing how this idealized setting related to the practical ICL scenarios.\n2. A key property of ICL is its generalization to new unseen tasks. Discussion on this aspect is missing in the paper.\n3. The paper relies on the choice of hidden dimension $k$ and the number of demonstrations $n$ to ensure the results hold, It would strengthen the contribution to include more detailed discussion about how $k$ and $n$ dcale with other parameters, such as dimensions $d_x,d_y$, vocabulary size, function complexity, et al.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive recognition of our work and your in-depth discussion of the related issues. We have carefully reflected on the shortcomings you pointed out, and would like to offer the following responses:\n1. **[About $x^{(i)}$ and $y^{(i)}$]** We are excited by your question and have thought carefully about it. We believe that in standard ICL, when $y^{(i)} = f( x^{(i)})$ (which we refer to as meaningfully related) and $\\mathcal{V}_ y$ satisfies certain conditions, the conclusion still holds. This relies on the density of the set $S := \\mathcal{V}_ x + \\mathcal{P}_ x$, and we provide a brief justification based on Theorem 8.\n\n    The main idea in the proof of Theorem 8 is to construct $\\mathrm{N}_ * ^\\sigma(x)$ to approximate $\\mathrm{N}^{\\prime}(x)$. Referring to the setup in the sections Implementation Details and Alternative Construction (especially Eq. (82)), we find that the approximation of coefficients such as $(q\\sqrt{2}\\pm l)_ 1\\sigma( \\tilde{w}_ 1\\tilde{x})$ mainly relies on the sum of the elements in the column vectors of $Y$ corresponding to the approximate location $\\tilde{w}_{1}$. Furthermore, we need some of the $y^{(i)}$ vectors to have column sums that are irrational numbers, positive integers, and negative integers, while the unused positions must have column sums equal to zero.\n\n    In short, if $x^{(i)}$ and $y^{(i)}$ are meaningfully related, and there exist some positions where the column sums of $y^{(i)}$ take on irrational, positive, and negative integer values—while the rest are zero—and $S := \\mathcal{V}_ x + \\mathcal{P}_ x$ is dense, then the UAP still holds.\n\n2. **[About generalizing to new unseen tasks]** We would like to clarify the intention of our paper. The main conclusion demonstrates that for models satisfying Assumption 1, arbitrary continuous functions over compact domains can be approximated by adapting the context. We do not assume any form of pretraining for the model, which means that every function is essentially unseen to the model.\n\n3. **[About how $k$ and $n$ scale with other parameters]** We appreciate your suggestion. As you pointed out, the choice of hidden dimension $k$ and the number of demonstrations $n$ indeed plays a crucial role in the validity of our theoretical results. Our current focus is on establishing the feasibility of UAP for a single-layer Transformer under a finite vocabulary and the existence of positional encodings. Therefore, our theoretical framework emphasizes the role and the existence of such positional encodings, rather than providing a full analysis of all parameter interactions.\n    Compared with the feasibility of approximation, analyzing the approximation rate is substantially more difficult. A more precise analysis of approximation rate will be an important direction for future work.\n\n4. **[About Lemma 4]** We would like to further clarify Lemma 4. This lemma guarantees the existence of $n$, and as discussed earlier, the required number of demonstrations $n$ depends on the target function $f$ and the desired approximation precision $\\varepsilon$. Clearly, if $n$ is too small, a good approximation cannot be achieved.\n\n5. **[About the choice of the positional encoding]** We would like to respond to your question as follows:\n        \n    - First, the positional encoding is constructed beforehand. It is universal and independent of any specific context.\n    - Second, Theorem 7 considers whether UAP can be achieved in the absence of positional encoding. Under your proposed setting, if we define $S := \\mathcal{V}_ x + \\mathcal{P}_ x = \\\\{x_ i + \\mathcal{P}_ x^{(j)} \\mid x_ i \\in \\mathcal{V}_ x,\\\\ i,\\\\ j \\in \\mathbb{N}^+\\\\}$, then Theorem 7 naturally extends to Theorem 8, and the conclusion that UAP cannot be achieved still holds.\n    \n    -  Finally, your second conjecture is actually not valid. In fact, this highlights the value of our basic setting—it is both idealized and aligned with practical modeling scenarios. For more details, please refer to the proof in Appendix E.2 and the illustrative example in Appendix E.3.\n\n6. **[About the special case in Theorem 8]** We would like to explain Theorem 8 further. The class $\\mathrm{T}_ {* ,\\mathcal{P}}^\\sigma$ consists of functions satisfying Assumption 1, with specific activation $\\sigma$ and structural conditions on $\\mathcal{V}_ x$, $\\mathcal{V}_ y$, and $\\mathcal{P}_ x$ (see Theorem 8 for details). For any continuous target function $f$, there exists a specific context and structure such that $\\mathrm{T}_ {* ,\\mathcal{P}}^\\sigma(\\tilde{x}; X, Y)$ can approximate $f(x)$. The existence result in the theorem does not exclude the special case where $x^{(i)} \\equiv 0$. UAP can still be achieved, but the approximation depends on its position in the context."}, {"review_id": "fgC2MUFYdG", "reviewer": "Reviewer_ZZKj", "summary": "This paper investigates the role of positional encoding (PE) in the universal approximation property (UAP) of the Transformer architecture. It demonstrates that while a Transformer possesses the UAP under an infinite vocabulary size, there exist functions such as the cosine function that cannot be approximated by any one-layer Transformer without positional encoding. However, once positional encoding is introduced, the one-layer Transformer regains its universal approximation capability.", "questions": "Q1: Could you discuss a bit on the relationship with [1], where they also considered the UAP of transformers with PE? Although you mentioned in sec 1.2 that \"their implementations allow the internal parameters of the Transformers to vary, which does not fully reflect the characteristics of ICL\", I don't fully understand what you mean by \"allow the internal parameters of the Transformers to vary\".\n\nQ2: In line 118 you mentioned \"we do not assume any correspondence between $x^{(i)}$ and $y^{(i)}$, i.e. , $x^{(i)}$ and $y^{(i)}$ are chosen freely\", could you explain why this makes sense, since the essence of ICL is for the transformer model to \"learn\" the relationship of $(x, y)$ pairs from the context information?\n\nQ3: Why is the input to $N^{\\sigma}$, namely $x$ in Lemma 3 of dimension $d_{x}-1$ instead of $d_x$?\n\nQ4: Could you explain what is the role of positional encoding $\\mathcal{P}_x$ in maintaining the UAP of transformers? I took a brief look at the proof of Theorem 8 and couldn't find whether $\\mathcal{P}_x$ is constructed or arbitrarily chosen, so I don't understand how simply adding a $\\mathcal{P}_x$ could miraculously recover the UAP for the finite vocabulary setting.\n\n[1] Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., & Kumar, S. (2019). Are transformers universal approximators of sequence-to-sequence functions?. arXiv preprint arXiv:1912.10077.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n1. The paper studies an important topic of ICL and makes a first step towards understanding the substantial effect of absolute positional encoding on the UAP of transformers.\n\n2. The overall structure of the paper is well-organized and generally easy to follow.\n\n## Weaknesses\n1. The paper includes numerous lemmas, propositions, and theorems, some of which appear unnecessary. For instance, Proposition 5 might be omitted from the main text, as its relevance becomes clear only after reading the proof of Lemma 6, which relies on Rolle's Theorem.\n\n2. The paper only studies one-layer transformer and absolute positional encoding, while in practice more dynamic PE such as RoPE are often employed (Although this is indeed a weakness, given the current theoretical literature on APE and ICL of transformers, I understand the difficulty of extension from a theoretical perspective, so I don't expect the authors to fully address the issue).\n\n3. There are some grammar and typo issues, especially in the appendix, e.g.\n\nline 619: \"cannot arbitrarily approximated\" should be \"cannot be arbitrarily approximated\"\n\nline 646: \"which is contradicts to the Proposition 5\" should be \"which contradicts Proposition 5\"\n\nline 657: \"can be view as\" should be \"can be viewed as\"", "was_revised": true, "final_justification": "The paper studies an important topic of ICL and makes a first step towards understanding the substantial effect of absolute positional encoding on the UAP of transformers. During the discussion period most of my concerns are addressed, and the authors' argument regarding the relation between $(x_i, y_i)$ seems valid to me.", "rebuttal": "We sincerely appreciate your positive recognition of our work and your thoughtful discussion of the related issues. We have carefully considered your suggestions and would like to offer the following responses:\n\n1. **[About omitting Proposition 5]** Yes, we agree with your suggestion, and we believe that the revised manuscript has better focus. The detailed proof is still retained in the appendix.\n\n2. **[About more dynamic positional encodings]** Yes, we are also paying close attention to more dynamic positional encodings such as RoPE and are actively exploring suitable analytical approaches. Our recent progress in studying APEs has given us increased confidence to investigate relative positional encodings as well. \n\n     Our current methodology relies on the density of the matrix $X^\\top B^\\top C$ in the expression $\\sigma(X^\\top B^\\top C \\tilde{x})$ (as shown in the proof of Lemma 3 and Theorem 8 in Appendix B.1). In the case of RoPE, the basic formulation is:\n     $$\n     q_m^\\top k_n = (R_{\\Theta, m}^d W_q x_m)^\\top (R_{\\Theta, n}^d W_k x_n) \\quad \\text{(Eq. 16 in [2])}.\n     $$\n     Applying our method yields: \n     $$\n     \\mathrm{T}^{\\sigma}(\\tilde{x}, X, Y) = UY\\sigma(X^\\top B^\\top (R_{\\Theta, m}^{d})^\\top C\\tilde{x}).\n     $$\n     However, since the RoPE rotation acts independently on different 2D subspaces of the $d_x$-dimensional input, the resulting matrix $B^\\top (R_{\\Theta, m}^{d})^\\top C$ is not dense. Therefore, our current method cannot be directly used to prove that RoPE admits a similar UAP result.\n\n     Similarly, other relative position encodings, such as the one proposed in [3] (Eq. 4):\n     $$\n     e_{ij} = \\frac{x_i W^Q (x_j W^K + a_{ij}^K)^\\top}{\\sqrt{d_z}},\n     $$\n     also cannot be analyzed using our current approach.\n\n     In contrast, the relative positional encoding proposed in [4] is of the following form:\n     $$\n     A_ {i, j}^{\\mathrm{rel}} = \\underbrace{E_ {x_ i}^\\top W_ q^\\top W_ {k, E} E_ {x_ j}}_ {(a)} + \\underbrace {E_ {x_ i}^\\top W_ q^\\top W_ {k, R} R_ {i-j}}_ {(b)} + \\underbrace{u^\\top W_ {k, E} E_ {x_ j}}_ {(c)} + \\underbrace {v^\\top W_ {k, R} R_ {i-j}} _ {(d)}.\n     $$\n     We find that this encoding can indeed be analyzed using our method and can support the realization of the UAP.\n\n3. **[About grammar and typo issues]** Thank you for pointing that out. We have made the necessary corrections.\n\n4. **[About discussion of the relationship with [1]]** We would like to clarify the differences between our work and [1]. We mainly draw from Theorems 2 and 3 of [1] for our understanding:\n\n     - First, the approximation goals differ. [1] focuses on approximating a fixed-length sequence-to-sequence function, $f: \\mathbb{R}^{d_x \\times n} \\to \\mathbb{R}^{d_x \\times n}$, while our goal is to approximate a general continuous function, $g: \\mathcal{K} \\to \\mathbb{R}^{d_y}$.\n     - Second, for the characterization of approximation, [1] uses the $L^P$ norm, whereas we use the infinity norm. This is a key difference between the two works.\n     - Finally, [1] proves that different Transformers can approximate different target functions, while we show that the same Transformer, with different contextual settings, can approximate different targets. [1] focuses on the approximation ability of the Transformer itself, while our work, grounded in VICL, explores how a fixed-parameter Transformer can approximate various target functions by adjusting its context. Therefore, the sentence in our paper reflects that the Transformer parameters are fixed for different approximation targets, while in [1], the Transformer’s parameters vary for different targets.\n\n5. **[About $x^{(i)}$ and $y^{(i)}$]** We are excited by your question and have thought carefully about it. We believe that in standard ICL, when $y^{(i)} =f( x^{(i)})$ (which we refer to as meaningfully related) and $\\mathcal{V}_ y$ satisfies certain conditions, the conclusion still holds. This relies on the density of the set $S := \\mathcal{V}_ x + \\mathcal{P}_ x$, and we provide a brief justification based on Theorem 8.\n\n    The main idea in the proof of Theorem 8 is to construct $\\mathrm{N}_ * ^\\sigma(x)$ to approximate $\\mathrm{N}^{\\prime}(x)$. Referring to the setup in the sections Implementation Details and Alternative Construction (especially Eq. (82)), we find that the approximation of coefficients such as $(q\\sqrt{2}\\pm l)_ 1\\sigma( \\tilde{w}_ 1\\tilde{x})$ mainly relies on the sum of the elements in the column vectors of $Y$ corresponding to the approximate location $\\tilde{w}_ {1}$. Furthermore, we need some of the $y^{(i)}$ vectors to have column sums that are irrational numbers, positive integers, and negative integers, while the unused positions must have column sums equal to zero.\n\n    In short, if $x^{(i)}$ and $y^{(i)}$ are meaningfully related, and there exist some positions where the column sums of $y^{(i)}$ take on irrational, positive, and negative integer values—while the rest are zero—and $S := \\mathcal{V}_ x + \\mathcal{P}_ x$ is dense, then the UAP still holds.\n\n6. **[About dimension $d_x - 1$ in Lemma 3]** The additional dimension is introduced to incorporate the bias term into the model. You can refer to Appendix B, particularly Section B.1, for further details.\n\n7. **[About the role of positional encoding]** Although the vocabulary is finite, the length of the text is adjustable, and the positional encodings at different positions are dense, which introduces diversity. The realization of the UAP takes advantage of the adjustable length of the text, leveraging the diversity of positional encodings to form more varied combinations for function approximation.\n\n     In Theorem 8, the positional encoding is constructed independently of the target function and the vocabulary. We provide a feasible construction method, with detailed steps available in Appendix E.2 and E.3.    \n\n[1] C. Yun, S. Bhojanapalli, A. S. Rawat, S. Reddi, and S. Kumar, “Are transformers universal approximators of sequence-to-sequence functions?” in International Conference on Learning Representations, 2020.\n\n[2] J. Su, M. Ahmed, Y. Lu, S. Pan, W. Bo, and Y. Liu, “Roformer: Enhanced transformer with rotary position embedding,” Neurocomputing, vol. 568, p. 127063, 2024.\n\n[3] P. Shaw, J. Uszkoreit, and A. Vaswani, “Self-attention with relative position representations,” in Annual Meeting of the Association for Computational Linguistics, 2018.\n\n[4] Z. Dai, Z. Yang, Y. Yang, J. Carbonell, Q. Le, and R. Salakhutdinov, “Transformer-xl: Attentive language models beyond a fixed-length context,” in Annual Meeting of the Association for Computational Linguistics, 2019."}, {"review_id": "QlzzqeJBtU", "reviewer": "Reviewer_yZa7", "summary": "This paper studies the expressive power for the prompts of transformers with absolute positional encodings (PE) when the input prompts are restricted to a vocabulary. Under the assumption on sparseness of $Q,K$ and $V$ matrices of the transformer, the authors start with an equivalence between prompting transformers (without PE) and parametrizing FNNs. Then they show there exists some continuous function $f$ that can not be well approximated by FNNs/transformers if restricting the parameters/prompts to a finite set/vocabulary. But with dense PE, the transformers can break this barrier and approximates any continuous function defined on the compact domain using the prompts.", "questions": "Please see weakness.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. The writing is easy to follow and most proof sketches are clear.\n2. I am not a specialist in approximation theory but I feel it is natural to think about the approximation power under the restriction of vocabulary. Hence the motivation is somewhat clear.\n\nWeakness:\n1. One question is on the target $f$. Currently $f$ defined as $\\mathcal{K} \\to \\mathbb{R}^{d_y}.$ As the motivation follows from the fact that all inputs and outputs are from finite vocabularies, I care more about the following target $g: \\mathcal{V}_x\\to\\mathcal{V}_y$ yielded by $f$. (Let's assume $\\mathcal{K}=\\mathcal{V}_x$ and I'm also happy to assume $\\mathcal{V}_x=\\mathcal{V}_y=V$). That is, $g(x) = \\underset{y\\in V}{\\arg\\max} \\ f(x)^\\top y$. This is to resemble the scene of greedy decoding. I wonder if UAP still holds for transformers without PE if targets are these functions like $g$.\n2. Another question is on the assumption 1. This assumption weakens the expressive power. It would be good if there are some discussions on that.", "was_revised": true, "final_justification": "This paper offers a view that real-valued PEs could add much richer information to inputs from a finite vocabulary, so as to achieve UAP of ICL. Though the main assumption is somewhat idealized (infinite context length), the view itself is interesting to the community. It could encourage future theoretical investigations on learned PEs or structural PEs. Thus I raised the score to 4.", "rebuttal": "We sincerely appreciate your positive recognition of our work and your thorough discussion of the related issues. After careful consideration of your questions, we would like to offer the following responses:\n\n1. **[About the target function $f$]** This is a very interesting question, and we are curious about why you considered a function $g(x)$ of this form. After reflecting on this issue, we believe that in most cases, the UAP does not hold in this context. On one hand, the space spanned by all $g(x)$ has a dimension of $|\\mathcal{V}_ x| \\cdot\\dim(\\operatorname{span}(\\mathcal{V}_ y))$, while on the other hand, the span of ${\\sigma(x^{(i)} B^\\top C x)}$ has at most dimension $|\\mathcal{V}_x|$ (refer to Section 3). It is evident that, in most cases, the space spanned by $g(x)$ has a larger dimension, making it impossible for every $g(x)$ to be contained in the span of ${\\sigma(x^{(i)} B^\\top C x)}$, and therefore, it is not feasible for all $g(x)$ to be approximated.\n\n2. **[About the clarification of Assumption 1]** We would like to offer the following explanation for our Assumption 1:\n    - First, the setting where the last row and the last column of the $Q$ and $K$ matrices are all zero is inspired by works [1-3].\n    - Second, our model does not require pretraining, and based on the fact that the probability of a randomly initialized $n$-dimensional matrix being non-singular is $1$, it is acceptable to assume that the matrices $B$, $C$, and $U$ are non-singular.\n    - Furthermore, in Appendix F, we decompose the matrices in the attention mechanism, namely $Q$, $K$, and $V$, and rederive the expression for $\\operatorname{Attn}_ {Q,K,V}^\\sigma(Z)$. We find that it is sufficient for the submatrix $O_ {11} = B^\\top C$ and $U$ to be non-singular. The assumption that $F = 0$ is made for the sake of convenience in proof and computation.\n\n[1] J. Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, and M. Vladymyrov, “Transformers learn in-context by gradient descent,” in International Conference on Machine Learning, pages 35151–35174. PMLR, 2023.\n\n[2] K. Ahn, X. Cheng, H. Daneshmand, and S. Sra, “Transformers learn to implement preconditioned gradient 397 descent for in-context learning,” in Advances in Neural Information Processing Systems, 2024.\n\n[3] X. Cheng, Y. Chen, and S. Sra, “Transformers implement functional gradient descent to learn non-linear functions in context,” in International Conference on Machine Learning, 2024."}]

Author rebuttal:

Meta-review: This work considers the representation capacity of transformers in in-context learning, ie, fix transformer weights while varying the context to represent functions. It considers the setting where the context is represented by tokens from a finite vocabulary. The main result is that single-layer transformers without positional encoding do not have the universal approximation property, while it is possible with positional encoding. 

The work provides an interesting perspective on the capacity of transformers in in-context learning. The analysis and results are solid. In the discussions, the authors have clarified the scope and meaning of the results and some technical details, after which all reviewers leaned towards acceptance. The work is recommended for acceptance, and the authors are suggested to include the revisions in the final version if accepted.
Decision: Accept (poster)