Understanding In-Context Learning on Structured Manifolds: Bridging Attention to Kernel Methods
Authors: Zhaiming Shen
Alexander Hsu
Rongjie Lai
Wenjing Liao
Venue: ICLR 2026 Poster (2026)
Keywords: In-Context Learning
Transformer Approximation Theory
Kernel Regression on Manifold
Primary area: learning on graphs and other geometries & topologies

Abstract: While in-context learning (ICL) has achieved remarkable success in natural language and vision domains, its theoretical understanding—particularly in the context of structured geometric data—remains unexplored. This paper initiates a theoretical study of ICL for regression of H\"older functions on manifolds. We establish a novel connection between the attention mechanism and classical kernel methods, demonstrating that transformers effectively perform kernel-based prediction at a new query through its interaction with the prompt. This connection is validated by numerical experiments, revealing that the learned query–prompt scores for H\"older functions are highly correlated with the Gaussian kernel. Building on this insight, we derive generalization error bounds in terms of the prompt length and the number of training tasks. When a sufficient number of training tasks are observed, transformers give rise to the minimax regression rate of H\"older functions on manifolds, which scales exponentially with respect to the prompt length with the exponent depending on the intrinsic dimension of the manifold, rather than the ambient space dimension. Our result also characterizes how the generalization error scales with the number of training tasks, shedding light on the complexity of transformers as in-context kernel algorithm learners. Our findings provide foundational insights into the role of geometry in ICL and novels tools to study ICL of nonlinear models.

Published as a conference paper at ICLR 2026
UNDERSTANDING IN-CONTEXT LEARNING ON STRUCTURED MANIFOLDS: BRIDGING ATTENTION TO KERNEL METHODS
Zhaiming Shen', Alexander Hsu", Rongjic Lai", Wenjing Liao
1 Schooo of Mathematics, Georgia Institute of Technology Department of Mathematics, Purdue University
"2zshen49, 9,, w1iao60]8gatech.. 2 [hsu2997, 1purreepurddue... edu
ABSTRACT
While in-context learning (ICL) has achieved remarkable success in natural lan- guage and vision domains, its theoretical wewrrsttanning-aatiiuuull in the context structured geometric rema-semains unexplored. This paper initiates a theoreti- cal study of ICL for regression of Hölder functions manifolds. We establish novel connection between the attention mechanism and classical kernel methods, demonstrating that transformers effectively perform kernel-based prediction new query through its interaction with the prompt. This connection validated by numerical experiments, revealing that the learned query-prompt scores for Hölder functions are highly correlated with the Gaussian kernel. Building on this insight, we derive generalization error bounds in terms of the prompt length and the number of training tasks. When sufficient number of training tasks are observed, trans- formers give rise the minimax regression rate of Hölder functions on manifolds, which scales exponentially with respect to the prompt length with the exponent depending on the intrinsic dimension of the manifold, rather than the ambient space dimension. Our result also characterizes how the generalization error scales with the number of training tasks, shedding light on the complexity of transformers as in-context kernel algorithm learners. Our findings provide foundational insights into the role geometry in ICL and novels tools to study ICL of nonlinear models.
INTRODUCTION
The Transformer architecture, first introduced by Vaswani et al. 2017), has fundamentally reshaped machine learning, driving significant advancements in natural language processing (NLP), computer vision, and other domains. Unlike traditional feedforward and convolutional neural networks, transformers employ attention mechanism that allows each token interact with others and selectively aggregate information based on learned relevance scores. This mechanism enables more flexible and context-aware representation learning. Transformers now serve as the foundational architecture for large language and video generation models, such as GPT (Achiam et al. 2023). BERT (Devlin 2018), SORA (Brooks al. 2024) and their successors.
These empirical successes have demonstrated the in-context learning (ICL) capability of transformers, which models can perform learning tasks by conditioning on given of examples, known as prompt, provided at inference time, without any additional parameter updates Brown et al. (2020); Radford et al. (2019); Liu al. (2023): y Garg al. (0022). The ICI. phenomenon transformers has also sparked substantial research interest in developing theoretical explanations of its underlying mechanisms. Bai et al. (2023); Zhang et al. (0024); Von Oswald et al. (2023); Akyürek et al. (2022); Cole al. 2024). transformers proved for ICL of linear models, including least squares, ridge regression, Lasso, generalized linear models and linear inverse problems.
Beyond linear models, transformers studied for nonlinear models in Yun al. (0019) Takakura & Suzuki (2023): Gurevych et al. (2022); Havrilla Liao (2024); [Shen et al. (2025). with the goal of learning single function, classifier, or sequence-to-sequene mapping. Specifically, Yun al.

---

Published as a conference paper at ICLR 2026
(2019) proved that transformer models can universally approximate continuous sequence- -eqqeeeeet-seequueee sequence functions with compact support, while the network size grows exponentially with respect to the sequence dimension. Takakura & Suzuki (003) studied the approximation and estimation ability of transformers for -equeence-o-seqqeee
functions with anisotropic smoothness on infiniteddimenionall inputs. Gurevych et al. (2022) studied binary classification with transformers when the posterior probability function exhibits hierarchical composition model with Hölder smoothness, In Havrilla & Liao (022)); Shenn al. (2025), transformers are proved to leverage low-dimensional geometric structures of data (Havrilla & Liao, 2024) or machine learning tasks (Shen et al., (025). While these works focus on a single learning task, ICL involves multiple learning tasks performed within the same model by leveraging prompts to adapt to each task on the fly, highlighting a form of task generalization without explicit retraining. It is worth noting that such task generalization also appear in the operator learning setting such as solving partial differential equations (Yang et al. 2023 Cole
ct al. 2024) and learning on the space of probability measures (Huang & Lai 2025 Cole et al. 2026).
While in-context operator learning has been explored with feedforward neural networks (Chiu et al.) 2025). transformer-basee in-context learning (ICL) has received increasing attention due to its strong empirical performance.
A theoretical understanding of ICL in transformers eunpecalers-eppecilllll in settings involving structured data with geometrie rrior-remains limited and largely unexplored. In this work, we initiate theoretical study of ICL for manifold regression. A manifold hypothesis is incorporated into our regression model to leverage low-dimensional geometric structures of data. Recent works have demonstrated that, under a manifold hypothesis of data, feedforward and convolutional residual networks give rise sample complexity depending on the intrinsic dimension (Shaham al. 2018 Chen et al.) 2022)
2019 Liu et al.) 2021: Nakada & Imaizumi 2020 Semmidt-Hieber 2019). Empirical evidence has shown that the neural scaling laws of transformers depend on the intrinsic dimension of data (Kaplan
al. 2020 Sharma & Kaplan] 2022). while theoretical justifications, especially for ICL, are limited.
central insight of this paper is the interpretation of transformers as learning kernel methods for function regression. Our study establishes novel connection between the attention mechanism and classical kernel methods, showing that token interactions within attention can be interpreted as constructing an interaction kernel used to perform regression. Based on this connection, we construct a transformer neural network to exactly implement kernel regression, which builds an approximation theory of transformers for in-context manifold regression. To be more precise, let 5 = {xi, f(x)). X2. (xx)..... X,, ((x,):xx ( } be a prompt, we explicitly construct a transformer T exactly implement the kernel regression estimator (s) such that
T (6) (s) 1i=1 exp (- |x++1 x2112/1²)
(1)
E exp (- -x111)
where the Gaussian kernel of bandwidth > O is used. Our construction shows that transformer- based ICL can implement kernel regression with zero approximation error. A formal statement can be found in Lemma] I. This perspective not only illuminates the internal workings of transformers in the in-context regression setting, but also motivates a theoretical framework for analyzing their generalization performance. Moreover, this connection is validated by numerical experiments on the regression of Hölder functions, revealing that the learned query-pronge scores in the last transformer layer are highly correlated with the Gaussian kernel.
Based on this key insight, our theoretical contribution for the generalization error of the transformer- based ICL can be summarized as follows: Let M be d-dimensional compact Riemannian manifold in RDD We consider the ICL of a-Hölder (0 < a < 1) functions on M given a prompt of length n. During training, one observes the regression of I' functions/tasks, where each function/task is provided on a prompt of length n. At inference time, a prompt of length n is given for a new a-Hölder function on M, and the goal is to predict the function value new input. Under this setting, prove that the squared generalization error of transformer- basse ICL is upper bounded by
Ci (nD'r-+ <.D'I=+Vlog(nDDT)) C2
žuीa [log n 2+ 3d)
with constants C1, C2. A formal statement of our result can be found in Theorem I Our result sheds light on theoretical understandings of wansformer-baseed ICL in the following aspects:
Scaling Law of Transformers as Algorithm Learners. The first error term in 2 characterizes the scaling law of transformers in-context kemnel algorithm learners. When transformer is trained
2

---

Published as a conference paper at ICLR 2026
on I regression tasks, it can learn kernal regression algorithm and generalize new task, with the generalization error given in the first term in
Minimax Regression Error with Prompt of Length n. The second error term in (2) indicates the scaling law of transformers to make predictions based on a Prompt of Length n. matches Györfi et al., 2006) for the regression of Hölder functions up to log
2a
the lower bound of ni Zal
factor, , and thereby demonstrating that transformers can achieve near-optimal performance if T
large. Specifically, if 1' Z n 20+4 +5 2 D6 log(nD) for some å > O, then the second error term in dominates the first term.
Dependence on the Intrinsic Dimension. By leveraging Now-dimensional geometric structures of data, the error in (2) has an exponential dependence on d rather than the ambient dimension D. This improvement offers foundational insight into the role of geometry in ICL.
Organization. In this paper, we present some preliminaries in Section 2 and the problem setup in Section 3 We bridge attention to kernel methods in Section 4 and present the generalization error bound in Section 5 Related works are discussed in Section Finally, we make conclusion and discuss the limitation of our paper in Section
Notation. Throughout this paper, vectors are denoted by boldface letters, while scalars and matrices are denoted by standard (non-bold) letters. For vector E TR, we use ||x|| to denote its Euclidean norm. For a function f S2 + I, we denote its L norm as Il (L)(() == supxen [x()..
PRELIMINARIES
In this section, introduce preliminary definitions about manifolds, Hölder functions on manifolds, and the transformer neural networks used in this paper.
Manifolds and Hölder Functions Manifolds. In this paper, consider that data are sampled in a compact d-dimensional Riemannian manifold M isometrically embedded in RD. Mathematically d-dimensional manifold M is a topological space where each point has neighborhood that is homeomorphic to an open subset of Rd Furthermore, distinct points in M can be separated by disjoint neighborhoods, and M has countable basis for its topology. A formal definition of manifold and more definitions on geodesic distance and the reach of manifold are provided in Appendix [.I B.I
This work considers in-context regression of Hölder functions on M.
Definition 1 (Hölder function on manifold). A function f f:M + IR is Hölder continuous with Hölder exponent (0, 1] and Hölder constant L 0 if
[f(x) f(x') < (x,x(x for all x,x' EM
Attention and Transformer Blocks. We consider ICL using transformer- networks struc- ture Vaswani et al. (2017) this paper. We briefly review attention and multi-head attention here. Definition 2 (Attention and Multi-head Attention). Attention with the Query, Key, Value matrices Q, K.V E Redeneed x Xdmmeed is defined as
(K) VHo((H)) QQH).
(3)
The multi-heer heati attention (MHA) with heads is given by
MHA(H)= Σド= V,Hoo((,H))TQ.))
(4)
We want to point out that in this paper we apply ReLU the activation function of the attention modules from the first to the penultimate layers in the transformer, and apply Softmax for the last layer. transformer block a residual composition of the form
B0;; H)- FFN(MHA + H) + MHA(H) H.
where FFN is feed-forward neural network operating tokenwise on the input.
3 IN-CONTEXT REGRESSION ON MANIFOLD
Problem Setup. Empirical evidence from image (Roweis & Saul 2000 Tenenbaum et al. 2000; Pope et al. 2021) and language datasets (Sharma & Kaplan 2022 Havrilla & Liao 2024). suggests the
3

---

Published as a conference paper at ICLR 2026
presence of underlying low-dimensional geometric structures in high high-dimensional data. Motivated by this observation, our study adopts a geometric prior by assuming that the data x lies on a Riemannian manifold M of intrinsic dimension d, isometrically embedded in R with d < D.
With this geometric prior, we consider in-context learning for regression of functions defined on M. More precisely, given prompt/task as
5
X1 V/1 X2, 1/: 1/....,, Xn, Uni xx+1) with yr = fxx),
(6)
where x; is are i.i.d. samples from a distribution As supported on M and f is sampled from Pf. a distribution in the function space (ʃ M - RR, the goal to predict f(xx+1) based on the
following in-context learning problem.
Given {f).. i..dd
Pf and the corresponding training set G = { provided by s
[x], v/= 02, X2, vi: x P241 with (x?} i.d. Px and v? = f (x]), we minimize the
empirical risk:
T E argmin (To) where RT,o(To) == Σ (To(tx] ToET
whtt1) (7)
where Tg a transformer neural network parameterized by 0 and T is a transformer network class to be specified. Our goal to study the squared generalization error of T on a random test sample (independent of training data) in (6):
R., ((s)) = (T((x, (((x),)))))) Mi X f(xx+1))
(8)
This generalization error can be characterized by the mean squared generalization error defined as:
R., (T) = EsR. RR. (T()))
where the expectation E, is taken for the test sample a and the expectation Eg taken for the joint distribution of the training samples.
Transformer Network Class. To describe the ICL problem more precisely, let us specify the transformer network class. We define a transformer network To(-) with weights parametrized by 0 as consisting of an embedding layer, a positional encoding module, a sequence transformer blocks, and decoding layer, i.e., for an input defined in (6)
(s(s) DE BL, .... B1 (PF (PF+F((s))
(10)
Here E is a linear embedding and PF is the operation of adding positional encoding (see their definitions in Appendix B.2). PE (s) embeds as a matrix H
X1
Xa
Xa+1
Ø1 Vn
0
= H = PE
0
O
E R
Rembed xt
R (D+5)xE
(11)
I
In matrix H, each column token, and each token has dimension dembed D + 5. The first D + 2 rows are data terms. The (D + 3)-th and (D + 4)-th rows contain the well-known sinusoidal positional encodings Z, (cos( i0 ) sin( 1)T which determines how each token will interact with another through the attention mechanism. The row contains the constant entries all equal to 1. is crucial to note that the data terms are dynamic, whereas the positional encoding and constant terms remain static. Furthermore, B,.... BLY
[Rdembenxt + R dodeme X are the transformer blocks (with ReLU activation from the first the penultimate layers and Softmax activation for the last layer in the attention module) where each block consists of the residual composition of multi-head attention layers and feed-forward layers. DE: ReeebeexXt -> R is the decoding layer which outputs the element in the (D + 1)-th row and (n + 1)-th column as the final output.
Our ICI problem is considered in the following networks class:
4

---

Published as a conference paper at ICLR 2026
Definition 3 (Transformer Network Class), The transformer network class with weights is T(Lr, mer, dembed; e, LEFN, WPEN, R. k)
= {To() (T()) has the form (10) with Le transformer blocks, at most ver attention heads in each block, embedded dimension dembed, number of hidden tokens E, and LEEN layers foed-fowarrd networks with hidden width WFEN, with output ([To())ll=>>30) R
and weight magnitude |001 S k
Throughout the paper, we will shorten the notation T(Lr: mer, dembed: & LEFN. WPEN, R. k) as T long there is ambiguity in the context.
4 BRIDGING ATTENTION TO KERNEL METHODS
One key insight of this paper is to interpret transformers used in ICL as a mechanism for learning kernel methods in function regression. This interpretation not only illuminates the internal workings of transformers in the in-context regression setting, but also motivates a theoretical framework to understand transformers ICL.
Constructing Transformer to Implement Kernel Method. The classical (Nadaraya-Watson) kernel estimator (Nadaraya 1964 Watson 1964) is well-established way for the estimation of
fxx++1) given {(x;, fxx 11=1 It outputs
Kn(x,+1 xx)8i (s) - Kn(x,-1 x,) with y: f(x:).
(12)
|| x= be the unnormalized Gaussian kernel with bandwidth h The transformer's attention mechanism can be interpreted as a form of kernel method, where the attention scores function analogously kernel-based importance weights over input tokens. Our idea is to first use the interaction mechanism in attention to construct several layers of transformer blocks which takes the input H
where we choose KA (u)
(TT)
and outputs the following matrix:
X,,
X
Xx+1
X Xx 1x-1-x0 x.ll
Xn
1x x,ll
H
Y1 0
Un
R"
h
R (245)x(())1)
(13)
y1
Yn
I
I2n++1
We will present the construction details which operates on the in [I] and gives rise the in (13) in Appendix E.I This operation accounts for the first to the penultimate layer in our transformer network.
In the final layer, we apply single-head attention A with a mask from the (n + 2)-th to the (2n + 1)-th token with value matrix V CD+1% and sparse query, key matrices Q, K such that Quaata e R(D+2)x(D+5) and K data E (D++) The exact form of Qdata and data are given the last step of the proof of Lemma
Then, the (n + 1)-th output token is
[A(H))+t
22++1 softmax ((Quatamm n Kdata ()) Vhş
- 1n
E Σy 18.+1 - (yeep+1) (s) ep+1-
Here, we denote e, as the elementary vector with all entries zero except for the j-th entry, which is 1. Therefore, the residual attention gives
X1
Xn
Xa+1
Xn+1 X1 Xx
Xn+1 Xn Xx
(s)
-xx ?|?
x x,,
A(H) + H
y1
O yn
ER (D+5))((2++1)
/1
On
I
Izn+1
1

---

Published as a conference paper at ICLR 2026
Pewrson commitation 6.917 larnel funczin
Pearson corrlation 0.778
Peamson corrlation 5.004
fundiin
520
lannd Fandies
120
440
sorted
Index
sorted
vettroo alieter latrel funczinn
udiraa alamton
--- hame Nundtkn
barnd fundie
30
sorted
index
Figure 1:
Examples of attention scores and Gaussian kernel with in-context length n = (first column), 16 (second column), = 32 (third column) respectively. The top and bottom rows the plots at two different samples. This figure shows a strong correlation between attention scores and Gaussian kernel.
where the kernel estimator K,s (s) is realized in (D + 1)-th row and (n + 1)-th column. Finally, the decoding operation produces this element in the (D + 1)-th row and (n+ 1)-th column as the output.
This connection between the transformer network and the kernel estimator in (22 can be rigorously established, that is, we prove that transformers can exactly implement the kernel estimator (12) without any error. We summarize it as the following lemma, whose proof is in Appendix E.
Lemma 1. Let M C [D. Suppose the prompt 5 in (6) satisfies: the x; 's are i.idd. samples
from distribution Px supported on M and f .M- - R is bounded, i.e. lIfl))))))) $ R. Let
(..-)) be the empirical kernel estimator defined in (2). Then there exists transformer network
Tž E ((Lr, my, (LL,m,, dembed, e, LEEN, WFFN, R, K) with parameters
LT 5, mT nD, dembed D 5, (= 1n2
LFTN = 0(1, WFFN- = + 5, = O (D*n26*
such that for any sample in the form of (6. we have
T (s) = (s).
(14)
The notation O() hides absolute constants.
Remark (Universality). In Lemmaa 7 the network architecture and weight parameters Tú are universal for different functions f and points {x,Y==1 The weight parameters only depend on n,n.b b, R. h. This construction indicates that transformer can universally implement the kernel regression algorithm with zero approximation error.
Validating the Correlation between Attention Scores and Kernel Function. To validate that transformer does indeed perform kernel regression implicitly, we conduct simulated experiment to compare the attention scores in the last layer of the trained transformer and the Gaussian kernel -1xx see if there is strong correlation between the two.
In this simulation, we fix M = S2 (the 2-dimensional sphere), and we consider the target function 52 - IR to be the linear combination of the real part of the first 10 spherical harmonics on the two-dimensional sphere 5². More precisely, let (0, Φ), ... $10 Φ) be the real part of the first 10 spherical harmonics on S For each task, we uniformly random sample the coefficients Wā E [0, 1]. and 87 E [0, x]. o7 E [0, 2T). and generate v = E (07, where (in-context length) and 7 1,..., (number of training tasks). Let of, sin(0?) cos(
1,... nn

---

Published as a conference paper at ICLR 2026
354
64 64
08
14
4
16
Figure Histograms the Pearson correlation for 4, 8, respectively. The ones with negative correlation are not included in this plot, while they only account for small amount. The total counts for positive correlation are 4588, 4598, 4771 out a total 5000 samples in each case respectively.
Table I: Average Pearson correlation coefficients (# standard deviation) and the corresponding
p-values (+: standard deviation)
In In-context length n
Pearson correlation coefficient
p-value
0.86 + 0.21
0.14 + 0.21
0.75 + 0.22
0.09 0.19
16
0.69 + 0.22
0,06 + 0.17
32
0.67 + 0.19
0.03 0.12
x²,, sin sin(o?), x3.; cos ). For each task, the training sample writes as the embedding matrix H shown in (35) in the Appendix F We fix the number of training and testing tasks I' 50000
and vary the in-context length 4, 8, 16,322 32.
Figure D plots the attention scores (after sorting from the highest to the lowest value) in the last layer of the trained transformer and compares it against the Gaus- sian kernel (sorted according the corresponding atten- tion scores), which demonstrates a strong correlation between the quantities. The distribution of the Pear- son correlation values are plotted in Figure 2 we can see that most correlations are concentrated around 0.8, showing that the attention score and Gaussian kernel are highly correlated with each other. More exemplar plots of attention scores and kernel function scores are provided in Figure 5 in Appendix F The average Pear- correlation coefficients between the two scores and the corresponding p-values are also reported in Table The results averaged over 5000 independent ran- dom testing samples. More details of the experimental setup are provided in Appendix F
sentence
sentence
attention score
sentence
sentence
sorted index
Figure 3: Softmax attention scores for real language data.
To further test how the curve of attention scores look like for real language data, we input five user
generated sentences (with length about 20 (3) into the pretrained GPT2 (Radford et al., 2019) and then plot the attention score for one of the heads in the model's 's last layer after sorting the score of each word from highest the lowest value. The curves in Figure shows that the attention scores for the real language data do exhibit some kernel shape.
5 TRANSFORMER SAAFORRMER-BBEEDD ICL GENERALIZATION ERROR BOUND
Based on the connection between transformer and kernel methods, derive generalization error bounds for transformer-bas based ICL involving structured data. By imposing a geometric prior, we assume that is sampled low-dimensional manifold M, and is function on the manifold M.
7

---

Published as a conference paper at ICLR 2026
This assumption leverages low-dimensional geometric structures in data which have been empirically
observed in image [Roweis & Saul 2000; Tenenbaum et al. 2000; Pope et al. (0211) and language
datasets (Sharma & Kaplan 2022; Havrilla & Liao 2024).
Assumption 1. Let M be a compact d d-dimensional Riemannian manifold isometricallyy embedded
in RR,, M C [bbb)j for some b >> O, and M has a positive reach TM >> -0 (reach is defined in
Appendix B. Suppose Px is the uniform distribution on M.
Assumption 2. Let (0, R. >>>00 and Pj be a probability distribution in the function space
F (f: M M a-Hölder with Hölder constant no more than L, and (lfll==(()) & R}.
Our main theorem about the generalization error of transformer-basee ICL is given below.
Theorem 1. Suppose M, Px and f. Py satisfy Assumptions 7 and respectively. If we choose the transformer network class T(L myr, dembed, l, LEEN, WFFN: R. K) with parameters
LT= = MT O(Dn), dembed D 5, l = 2n
LFFN 0(1,, WFEN D O (D
40+2d-8 2ata
R$
where (()) hides the dependency on the absolute constants. Then the minimizer T defined in satisfies the squared generalization error bound:
R. (T) Si ( + C2 (n-
Bo 20+t
log!
(15)
where the constant Ci depends on absolute constants, and the constant C2 depends on d, or L, R, TM-
This paper focuses the scaling between the generalization error and I, n, and the constants C₁ C2 may not be optimal. Note that in the worst case, C2 can depend dd/2, The proof roadmap of Theorem [ is presented in Appendix C and more details of the proof are provided in Appendix B Lemma is utilized
key step prove Theorem [ Theorem also offers insights into several key aspects of transformer-based ICL, which is discussed in the introduction.
Validating the Generalization Error Bound. We conduct simulated experiments to validate generalization error bound 15) in Theorem [ while varying n (prompt length) and T (number of training tasks). The data generating procedure is the same the experiments in Section 4 Figure plots the average Mcan Squared Error (MSE) over 30 repetitions on the testing data against the number of tasks I and the prompt length n. More details of the experiments are given in Appendix F
4
The top row of Figure 3 shows the testing MSE with respect to I' in log-log scale when the prompt length is fixed to be n 16, 64, 256 respectively. In log-log scale, the slope initially coincides with the theoretical slope of -0.5 5 in the first term of (15). and then slightly shifts above it. This is consistent with our error bound in (15). as when I' increases and fixed, the second term starts to dominate the total error. In the bottom row of Figure 4 we plot the logarithm of testing MSE in terms of the prompt length when the number of tasks fixed to be while the first term increases and the second term decreases as n increases. The testing MSE decays as n increases, and the rate of decay depends on the balance of the two terms in (15). The larger I is, the more dominant the second term in (15) is, and therefore the rate of convergence of the testing MSE faster as n increases. By comparing the three plots in the bottom row of Figure 4 with I 400, 1600, 6400 respectively, we observe faster rate of convergence with respect to n when I is larger, which is consistent with our theory.
400, 1600, 6400 respectively.
In our error bound 15 both terms depend
6 ROADMAP FOR THE PROOF OF THEOREM
In this section, we present a roadmap for the proof of our main result in Theorem | detailed discussion of the roadmap to Appendix Clad all the proof details to Appendix
We defer more
Bias- Variance Error Decomposition. We first decompose the squared generalization error at the test sample in 8 as follows:
R., (T()) (T(s)) RR,r(T) Rn) RT,r(T")) RR,r(T") Rr(T" + (T'
8

---

Published as a conference paper at ICLR 2026
-10
-13
vece Hrope 0.5
releran (1024 3.51
seference idope 0.5
-44
-22
-64
3.5
60
75
to
3-5
Heat
Neat
Nean
-4.0
-.30
-1.35
-140
+0.00
100 3/2
300 175 100 1/5 100
Figure 4: Top row: MSE v.s. number of tasks (with fixed prompt length n = 16, 64, 256 respectively). Bottom row: MSE v.s. prompt length (with fixed tasks r 1600,600,6400 6400 respectively). All plots are in log scale.
where T is transformer network which approximates the in-context kernel estimator KG in 12)
One term satisfies RT) ) < 0 since T is the minimizer of R,. given in 7 After taking expectations, we can decompose the mean squared generalization error ( as follows:
R.,
E.
Rr, (T((((s))
(16)
< Es
Rr ((s))) RR, + Fe (T*) R. [R., (T"()) + F. (TT)))
I
In this error decomposition, error IIT denotes the approximation error which we will analyze in Section The errors in I and TT denote the statistical error, which we will analyze in Section C.2
In and we obtain
[log (h )h-1) 1+
and T+Il So (DD' (oggiDDDD 112
I s
+ 2 Plo(( (1=
1)1
nhd
VT
respectively. Putting them together, we get
nD3 Alg(nDD/h
[log (h (1-1))
R.,(T) SI+ III Sa
+ C2
+ 2a
[lo -1)
VT
nhd
Finally, choosing = n no-n gives rise to
15 in Theorem
7 RELATED WORKS
We next discuss some connection and comparison of our result with existing works on transformers. This paper highlights bridging the attention mechanism and classical kernel methods. It provides new interpretation of transformers in ICL, and new tools to address nonlinear models in transformer- based ICL, which allows us move beyond linear models studied in Bai et al. (2023); Zhang et al.) (2024); Von Oswald et al, (003); Akyürek et al.] (2022); Cole et al. (2024). This novel tool also allows address multiple tasks ICI., in contrast to single task learning by transformers studied

---

Published as a conference paper at ICLR 2026
in Yun et al. (2019); Takakura & Suzuki (003): Gurevych et al. (2022): Havrilla & Liao (024);
Shen et al. (2025).
The most closely related work to this paper is Kim et al. (2024), which studied in-context regression of Besov functions in IR." Kim et al. (2024) derived approximation and generalization error bounds for transformer composed of a deep feedforward network and one linear attention layer. There are two main differences between this paper and Kim et al. (2024): 1) Our transformer network has 5 layers of multi-head attention, and each multi-head attention can be wide, i.e. with nD attention heads. The feedforward layers in each attention is of a constant order. Such a wide transformer architecture shares some similarity those used in large language models (LLMs). For example, GPT-2 Small only has 12 layers with 117 million parameters (Radford et al.] 2019). Our approximation theory developed by fully leveraging the attention mechanism. In contrast, Kim al. (2024) utilized one linear attention layer and a deep feedforward network for approximation. 2) By incorporating low-dimensional geometrie structures of data, we prove error bounds which scale exponentially with respect to the prompt length with the exponent depending on the intrinsic dimension d, while the error bound Kim et al. 2024) scales exponentially depending on the ambient dimension D.
Our work is also connected with Li et al. (2023), which derived generalization errors for transformers as in-context algorithm learners. While the framework in Li et al. (2023) is general, it does not address some key components in this paper, such our novel approximation theory bridging the attention mechanism to kernel methods, and our covering number calculation.
The connection between the attention mechanism and kernel methods has been explored in prior work, including Tsai et al. (2019); [Song [0on):[Song et al.] (202T); Yu et al. (2024). Lu & Yu (2025): Cheng et al.) (2024); |Han al. (2025). In particular, the work by Han al. (2025) takes the kernel perspective to understand ICL and empirically demonstrates that the attention and hidden features in LLMs match the behaviors of a kernel regression. While our work and these prior studies all draw on the connection between the attention mechanism and kernel methods, our theoretical justification is novel. In particular, the construction of transformers implement the kernel method in Lemmal [ and the generalization error bound in Theorem [ have not been addressed in literature. Our paper provides a theoretical framework to understand transformer-baat based ICL with geometric structures.
CONCLUSION AND DISCUSSION
Conclusion. This work provides a theoretical foundation for understanding in-context learning (ICL) with transformers in the setting of manifold-structuree regression tasks. By establishing novel connection between the attention mechanism and classical kernel regression, we interpret transformers implicitly learning kernel-based algorithms for function regression. Our findings offer new theoretical insights into the algorithmic nature of transformers in ICL, establish a rigorous approximation and generalization theory for manifold regression, and provide tools for analyzing nonlinear models under geometric structure.
Our analysis derives sharp generalization error bounds for o-Hölder functions compact Riemannian manifolds, revealing how the performance of transformers in ICL depends on the prompt length n, the number of training tasks I, and the intrinsic geometry of the data. Notably, our results show that transformers can achieve the minimax optimal regression rate up to logarithmic factors when I' is sufficiently large. Furthermore, the derived bounds depend exponentially with respect to the prompt length with the exponent depending on the intrinsic dimension d of the manifold, rather than the ambient dimension D, highlighting the critical role of geometric priors in achieving efficient generalization.
Discussion. Our theoretical analysis focuses on o-Hölder regression with fixed-length prompts and large number of training tasks, under idealized assumptions such as exact kernel implementation via attention. Extending the framework to broader function classes, variable prompt lengths, noisy data or limited data remains open challenge. Despite these limitations, our work reveals how geometric structure can enhance generalization in ICL and draws a principled connection between attention mechanisms and kernel methods. These insights may inform the design of more efficient and interpretable models in domains where geometry plays a central role, such as scientific computing robotics, and many others where geometric structure is prevalent.
10

---

Published as a conference paper at ICLR 2026
Reproducibility statement To support reproducibility of work, we provide comprehensive details across the main paper and supplementary material. All theoretical results are accompanied by clear assumptions and complete proofs in the appendix. For experimental results, describe the datasets used, preprocessing steps, and hyperparameter settings both the main text and the appendix. The implementation code used generate the experimental results in this paper is available in the supplementary material.
ACKNOWLEDGMENTS
Zhaiming Shen and Wenjing Liao are partially supported by National Science Foundation under the NSF DMS 2145167 and the U.S. Department Energy under the DOE SC0024348. Alexander Hsu and Rongjie Lai's research are supported in part by NSF DMS-2401297.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303. 08774, 2023.
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algo- rithm in-context learning? investigations with linear models. arXiv preprint arXiv:2211.15661, 2022.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection, 2023.
Tim Brooks, Bill Peebles, Connor Holmes, Will DePue, Yufei Guo, Li Jing, David Schnurr, Joe Taylor, Troy Luhman, Eric Luhman, Clarence Ng, Ricky Wang, and Aditya Ramesh. Video generation models as world simulators. 2024.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1101,2022
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation deep relu networks for functions on low dimensional manifolds. Advances in neural information processing systems, 32, 2019.
Minshuo Chen, Wenjing Liao, Hongyuan Zha, and Tuo Zhao. Distribution approximation and statisti- cal estimation guarantees of generative adversarial networks. arXiv preprint arXiv:2002.03938 2020.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Nonparametric regression on low- dimensional manifolds using deep relu networks: Function approximation and statistical recovery. Information and Inference: Journal of the IMA, 11(4):1003-122 2022.
Xiang Cheng, Yuxin Chen, and Suvrit Sra. Transformers implement functional gradient descent to learn non-linear functions in context. In International Conference on Machine Learning, pp. 8002-8037. PMLR, 2024.
Shao-Ting Chiu, Aditya Nambiar, Ali Syed, Jonathan W Siegel, and Ulisses Braga-Neto In-context multi-operator learning with deeposets. arXiv preprint arXiv:2512. /6074, 2025.
Frank Cole, Yulong Lu, Riley O'Neill, and Tianhao Zhang. Provable in-context learning of linear systems and linear elliptic pdes with transformers. arXiv preprint arXiv:2409. /2293, 2024.
Frank Cole, Dixi Wang, Yineng Chen, Yulong Lu, and Rongjie Lai, In-context operator learning on the space of probability measures. arXiv preprint arXiv:2601.09979 2026.
Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 18/0. 0.000, 2018.
11

---

Published as a conference paper at ICLR 2026
Richard M Dudley. The sizes of compact subsets of hilbert space and continuity of gaussian processes. Journal of Functional Analysis, 1(3):290-330 1967.
Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30598, 2022.
Iryna Gurevych, Michael Kohler, and Gözde Gül Şahin. On the rate of convergence of classifier based on transformer encoder. IEEE Transactions on Information Theory, 68(12):8139-81) 2022.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. distribution-free theory of nonparametric regression. Springer Science & Business Media, 2006.
Chi Han, Ziqi Wang, Han Zhao, and Heng Ji. Understanding emergent in-context learning from a kernel regression perspective. Transactions on Machine Learning Research, 2025.
Alex Havrilla and Wenjing Liao. Predicting scaling laws with statistical and approximation theory for transformer neural networks on intrinsically low-dimensional data. In Advances in Neural Information Processing Systems, 2024.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffdding, pp. 409-426, 1994.
Heinz Hopf and W. Rinow. Über den begriff der vollständigen differentalgecmmttiscennn fläche. Commentarii Mathematici Helvetici, 3:209-225, 1931. Reprinted in Selecta Heinz Hopf, Heraus- gegeben zu seinem 70. Geburtstag von der Eidgenössischen Technischen Hochschule Zürich, 1964, pp. 64
Han Huang and Rongjie Lai. Unsupervised solution operator learning for mean-field games. Journal of Computational Physics, 537:114057, 2025.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001. 008361, 2020.
Juno Kim, Tai Nakamaki, and Taiji Suzuki. Transformers are minimax optimal nonparametric in-context learners. Advances in Neural Information Processing Systems, 37: 37:106667-106713, 2024.
Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and stability in-context learning. In International conference on machine learning, pp. 19565-19594. PMLR, 2023.
Wenjing Liao and Mauro Maggioni. Adaptive geometric multiscale approximations for intrinsically low-dimensional data. Journal of machine learning research, 20(98):1 1-999):::6,,,0 2019.
Hao Liu, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks. In International Conference on Machine Learning, pp. 6770-6780. PMLR, 2021.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM computing surveys, 55(9):1-35, 2023.
Fei Lu and Yue Yu. Transformer learns the cross-task prior and regularization for in-context learning. arXiv preprint 1.XX::2555.1234 2025.
Mauro Maggioni. Stanislav Minsker, and Nate Strawn. Multiscale dictionary learning: non-asymptotic bounds and robustness. The Journal of Machine Learning Research, 17(1):43-33, 2016.
E. A. Nadaraya. On estimating regression. Theory of Probability and Its Applications, 91):141-142, 1964. doi: 10.1137/1 109020.
12

---

Published as a conference paper at ICLR 2026
Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal of Machine Learning Research, 21(174):1-38, 2020.
Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39:419-441, 2008.
Phillip E. Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. ArXiv, abs/2104.0882 2021.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 1(8):9, 2019.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2323 2326, 2000.
Johannes Schmidt-Hieber. Deep relu network approximation of functions on a manifold. arXiv preprint arXiv: 0008,, 2019.
Uri Shaham, Alexander Cloninger, and Ronald R Coifman. Provable approximation properties for deep neural networks. Applied and Computational Harmonic Analysis, 44(3):537-557, 2018.
Shai Shalev-Shwart and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Utkarsh Sharma and Jared Kaplan. Scaling laws from the data manifold dimension. J. Mach. Learn Res., 23(1), jan 2022. ISSN 1532-4435.
Zhaiming Shen, Alex Havrilla, Rongje Lai, Alexander Cloninger, and Wenjing Liao. Transformers for learning on noisy and task-level manifolds: Approximation and generalization insights. arXiv preprint arXiv:2505.0322 00000,, 2025.
Kyungwoo Song, Yohan Jung, Dongjun Kim, and Il-Chul Moon. Implicit kernel attention. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 9713-9721, 2021.
Shokichi Takakura and Taiji Suzuki. Approximation and estimation ability of transformers for sequence-to-sequenne functions with infinite dimensional input. In International Conference on Machine Learning, pp. 33416-33447. PMLR, 2023.
Tao Tang, Nan Wu, Xiuyuan Cheng, and David Dunson. Adaptive bayesian regression on data with low intrinsic dimensionality. arXiv preprint arXiv:2407.092286 2024.
Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 29065500):231922333, 2000.
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhut- dinov. Transformer dissection: unified understanding of transformer's 's attention via the lens of kernel. arXiv preprint arXiv: /908. /775, 2019.
Aad W Van Der Vaart and Jon A Wellner. Weak convergence. In Weak convergence and empirical processes, pp. 16-28. Springer, New York, NY, USA, 1996.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances Neural Information Processing Systems, 2017.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pp. 35151-35174 PMLR, 2023.
G. Watson. Smooth regression analysis. Sankhya: The Indian Journal of Statistics, Series A, 26(4): 359-372, 1964.
13

---

Published as a conference paper at ICLR 2026
Liu Yang, Siting Liu, Tingwei Meng, and Stanley J. Osher. In-context operator learning with data prompts for differential equation problems. Proceedings of the National Academy of Sciences, 120 (39):22300122120, 2023. doi: 10.1073/pnas.23111422)
Yue Yu, Ning Liu, Fei Lu, Tian Gao, Siavash Jafarzadeh, and Stewart A Silling. Nonlocal attention operator: Materializing hidden knowledge towards interpretable physics discovery. Advances in Neural Information Processing Systems, 37:113797-113822 2024.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are trans-
formers universal approximators of sequence-to-sequeeee functions? In International Conference on Learning Representations, 2019.
Ruiqi Zhang, Spencer Frei, and Peter Bartlett. Trained transformers learn linear models in-context. Journal of Machine Learning Research, 15(49):1-555 2024.
14

---

Published as a conference paper at ICLR 2026
A THE USE OF LARGE LANGUAGE MODELS (LLMS)
We used ChatGPT for minor language editing, such as grammar correction and improving sentence flow. The scientific content and all writing were created by the authors.
B MORE DEFINITIONS
B.1 MANIFOLD, GEODESIC DISTANCE, REACH OF THE MANIFOLD AND COVERING NUMBER
Definition 4 (Manifold). An d-dimensional manifold M is a topological space where each point has neighborhood that homeomorphic an open subset of R. Further, distinct points in M can be separated by disjoint neighborhoods, and . has countable basis for its topology.
With the induced metric on M, the geodesic distance on the manifold between x, x' E E is defined
dm(x,x) = inf C [t,t] - M,) xt) =x},
where the length is defined by == (s) The existence of length- minimiziig geodesic
Y t') + M between any two points x(), (t')) is guaranteed by the Hopf Rono-R theorem (Hopf Rinow] 1931).
Definition (Medial Axis). Let M R be connected and compact d-dimensional submanifold. Its medial axis is defined
Med(M) = (x ER 1 qE, x||2 ||q x
inf ||z x112].
which contains all points x E IRD with set-valued orthogonal projection TM(()) = argmin |x z||2-
Definition 6 (Local Reach and Reach of Manifold). The local reach for M is defined as TM((V== == = ||v - 2||2, which describes the minimum distance needed to travel from v to the closure of medial axis. The smallest local reach TM := inlveM (v(() is called reach of M.
Definition (Covering Number). Let (H. p) be a metric space, where is the set of objects and p is a metric. For given >> O, the covering number N(e, H. p) is the smallest number of balls of radius e (with respect to p) needed to cover H. More precisely.
N(c, H) min E N 3(h,,...,hw' hx) C H, vh H. 3hg such that p(h, ha) S c).
B.2 EMBEDDING, POSITIONAL ENCODING, FEED-FORWARD NETWORK CLASS AND TRANSFORMER BLOCK CLASS
Definition (Embedding Layer). Given x, R and ys E R, the embedding layer E takes an input = {x1, 9/, X2, 02 Na, Das Xn+1} 1 and maps it to
Xi
Xn
X
1/1
Yn
D
(s))
E
O
O
E T (D+5)xE
O
Definition 9 (Positional Encoding). The positional encoding takes input s, maps it Ij (cos( (5 sin( it T and put those I, embedding matrix, i.e.,
1, 1.. l, into the third and second last row in the
0
PE (s)
...
O
E ER. (D+5)xE
In
Ie
0
15

---

Published as a conference paper at ICLR 2026
With these definitions, we have
X1
X
X,+1
y1
Yn
0
PE + B (s)
0
E R (D+5)x
I
It
as defined
11).
Definition 10 (Feed-forward Network Class). The feed-forward neural network (FFN) class with weights 0 is
FEN(LEENNEEEN) (FF FFN((:)) is FNN with at most LPEN layers and width wpPN }.
We use ReLU function (xx) = max(x: 0) as the activation function in the feed-forward network. Note that each feed-forward layer is applied tokenwise to embedding matrix H.
Definition 11 (Transformer Block Class). The transformer block class with parameters 0 is
(mm, LEEN. WFEN) = (B(0;-) B(0;-) MHA with m attention heads, and a FFN layer with depth LyFN and width wPPN).
C ROADMAP FOR THE PROOF OF THEOREM
In this section, we present detailed roadmap for the proof of our main result Theorem | We defer all the proof details to Appendix B
Bias- Variance Error Decomposition. We first decompose the squared generalization error the test sample in 8 as follows:
R., (T(s) R., (T()) - (T. RT) RT,r((T)) + (T, R., (s) + R., (T*
where T is transformer network which approximates the in-context kernel estimator K₂ in One term satisfies (T) RT*) I taking expectations, can decompose the mean squared generalization error 9 follows:
since T is the minimizer of RR,, given After
R2 (T) EsL, Rn (T()))
< Es
E,
Rr ((())) - RT),(()) Es (R") E, [R,, (T (s))) E, (T. (s))
In this error decomposition, error III denotes the approximation error which we will analyze in Section C.I. The errors in I and II denote the statistical error, which we will analyze in Section C.2
C.1 APPROXIMATION ERROR: TRANSFORMERS CAN IMPLEMENT KERNEL ESTIMATOR
A key innovation in proof is establishing approximation theory for transformers to implement the classical kernel estimator in (12). Importantly, this implementation is universal for and x, so that the weight matrices in transformer independent of f and the x;'s. 's.
Our approximation error bound is given by Proposition [ below. Since transformers can exactly implement the kernel estimator as shown in Lemma the approximation error in Proposition iis the same as the mean squared error given by the kernel estimator.
Proposition 1. Suppose M, Px and f, Ps satisfy Assumptions | anddd 2 respectively. Let s be prompt in (6. where {x+]+++ 1n+1 are i...d. samples from Px and sampled from py. There exists transformer network T T((L.. mrr, dembed, LFEN, WFFN, ; R, k) with parameters
L 5, O(Dn), dembed D 5, - 2n
LFEN 0()), WFFN D +5, O
/h8)
16

---

Published as a conference paper at ICLR 2026
such that
[log (h (1- 1 2
E [R., (T* S C3
1:20
[log(h (h 1)2
(17)
nhe
The constani C3 hides the constants depending on d, L, R2 TM-
Proposition Tis is proved in Appendix E.4 Here we illustrate our proof idea. The empirical kernel
estimator in is applied to samples in the prompt. When n oc, the empirical kernel estimator in (12) converges to its integral counterpart. Given any f E and Xn+1 ~ Px. we define the integral
form of the kernel estimator
(n xx+1) == Ex [K (Xn+1 -
J -
(18)
Fx [ (Xn+1 - x)]
KKN(X+11 - x)dx
where the integral about x is about the measure error III can be further decomposed into three terms:
dpx. For any test sample s, the approximation
R2 (17 (T7, - (f (xx+11))
(19)
(T) (s)(s) + Kn((s) RR(fix + Rn - (xx+1))
S (T)((()) - KK((s)) (Kn, Rr (f:x+t)) +3 (Rx(fixnt1) - f(xx+1))²
A3
where the error in Al measures the bias of using a transformer network to implement the kernel regression estimator, the error in A2 measures the variance of kernel regression estimator, and the A3 error measures the bias using kernel regression estimator to approximate the target function. The bias and variance of kernel estimators has been studied in the literature of nonparametrie estimation (Tang et al. 2024). In our paper, these three error terms are bounded by Lemma [ Lemma 2 and Lemma respectively. Our Lemma [ shows that the error in Al equals 0. Lemma and Lemma give rise to an upper bound of A2 and A3. We defer their proof in Appendix E.2 and Appendix E.3 respectively.
Lemma 2. Let Rr, be the integral kernel estimator defined as in (8). For any Xa+1 ~ Px and any M and f satisfying Assumptions and respectively,
(fixx))))) - f(x++1)] s O(h log(h-1)).
(20)
The constant hidden in (C)) depend on d, L, R, TM, where the dependency on d can be exponential the worse case.
Lemma 3. Suppose M, Px and f. Pj satisfy Assumptions 7 and respectively. Let s be prompt in
ii are ii.dd samples from Px and f is sampled from Pş. Let Kr,, and Rr, be defined as and 188. Then with probability at least 1-5, 5,
(6) where {x; 11+1
(K)(s Rx(ffxx++1) 50
log3d/11
(+)
(og(4/8) nhd
(21)
The constants hidden in O(-) depend on d, R, TM, where the dependency on d can be dd/2 in the worse case.
C.2
STATISTICAL ERROR
This section focuses on bounding the statistical errors in I and IT in (66). We consider a transformer network class T with the architecture in Proposition [
Bounding Error I in [6). The error in I (16) can be bounded by
Es sup TET
Eg [T(s)( - (T))
since T belongs the network class T. Any function f py bounded, such that ||]|| S R. The transformer network T also yields bounded output such that [ S R. For the sam- ple (6). the transformer neural network takes the input ((x; Wi 1 X,41) and outputs T T((x, y xn+1) E [-R, R, RJ. In this paper, we take squared loss at each sample:
C(T, s, 11+ 1)= (T((x,, (i) bn41)²
17

---

Published as a conference paper at ICLR 2026
which satisfies |C(T, 5, yn+1)l 4R². to the training sample as
We define the Rademacher complexity of L with respect
Rad(L o ToG) = B EE-(+
sup TET
[[(x
11 1==1 ve
(22)
y=1
According to
Ben-Davin (014 Lemma 26.2), we have
Ee sup LEg (T)))))) 2 [Rad(C 6)] TET
To bound the expectation of Rademacher complexity Rad(C T G), we apply the well known
Dudley entropy integral (Dudley 1967). which we state in Lemma 8 By Lemma we have
12
4R2
Es [Rad(L o T o & inf ES0
2E
+
Vlog Co [ d8
(23)
VT
where [88, Lo T. 11 ) is the covering number (defined in Appendix B. of the function class
o T under the _ norm. We follow the proof idea in Havrilla & Liao 2024) to bound its covering number follows.
Lemma 4. For transformer class TLL,, myr, dembed, f, LFPN, WFEN, R. K) with input H U. Let then the covering number of L satisfies
10, S
22 2 LEFX
LVEN B
mpp my glgg R
aomeed
No,, ((0,LoTe LoT 1
6
where Pf dembed (D=rDDDD + 1) + (Td embeeddl + LFENUTEN)
Lemma 4 proved in Appendix E.5
Taking = 1/v[ in 23
obtain bound
nD3s Vlog(DD//H)
Es sup [Eg (T())) - R.. (T)) S 2E [Ra([ o T 6)] so TET where the O(-) hides the dependency some absolute constants.
VT
Bounding Error II in (16). We can directly apply Hoeffding's inequality bound this term, with details in Appendix E.9
Es (T*)(T") - E. (T so log(h-1) (1)
+ x22)
C.3 PUTTING APPROXIMATION ERROR AND STATISTICAL ERROR TOGETHER
Putting all the error terms together in 16 we get
'D' V Mlg(nDD/h)
[log (h []] 14 + 2 [ /h 112
R2 (T) +1+11+11+ S Ci
+ +C2
VT
nhd
Finally, choosing Zorn gives rise to
15) Theorem
D FUNDAMENTAL LEMMAS
In this section, present some fundamental lemmas which are crucial for constructing transformer represent the target function. Note that similar results of Lemma and have appeared in Havrilla general in the sense that they accommodate general dembded and general rows for gating. The detailed proof's of Lemma and are provided in Appendix E.6
& Liao (024)), but results
E.7
and E.8 respectively.
In the lemma and the proof, we use subscript to denote column index and superscript to denote row index. For matrix H. we use the notation || : || s0.0c max,, Hayl to denote the infinity-infinity norm of matrix H. When & denotes the weight parameters of neural network, we ||0| lo to denote the largest magnitude in the weight parameters.
18

---

Published as a conference paper at ICLR 2026
Lemma 5 (Interaction Lemma). Let H Imiisiee E Reembextt be an embedding matrix such that h (ddembed-221 2): = I and hi nomobed 1. Fix 1 S 1,,2 I E, S S dembed: and i E N. Suppose dembed 2 5 and ||H| data kernels Qdata and Kdata IR [R(demeed 3dxombd (the first (dembed 3) rows in the key matrix K) satisfy max max{|]Qu ( lo0,00 [| (o0,00 J S K. Then one can construct an attention head A with ReLU activation RcLU) such that
U for some U 0, and the RR(dembed (axxedd))))eeee 3)xdembed (the first (dembed 3) rows in the query matrix Q)
[A(H)) = o ((Qdataa he, Kd he ift=11
otherwise.
The weight parameters of this attention head satisfies ||0A|l "
2 222).
Lemma 5 is proved in Appendix E.6 Lemma 5 is called an interaction lemma, which allows tokens interact and therefore outputs pair-wise interaction result.
Lemma 6 (Gating Lemma). Let dembed 5 and H [hi]isese Rdeemred be embedding matrix such that h, (dembes 2)-(dembed = (I) ,I,) = I. and h hfummed 1. Then for any T1 and t2 with 1 S rı S 12 I dembed and any k1 12 with 1 s ki, h2 S l, there exist both two-layer feed-forward networks (FFN) such that
he
ift (L.-...,1))
(he)
(he)r
O (he)rat1
FFN, (h+)
(24)
otherwise
(hx (he)demded
It
I
1
and
ift E {12, .., 1..
(he)
(he)--1 0 (he)ret1
FFN2
(25)
otherwise
(Ie (he)dembed 3
I
I
1
Additionally, we have |[ppN]]o & O(E) H (00,00))
Lemma i proved in E.7 Lemma 6 uses the feedforward layers to set certain rows in specified tokens zero.
Lemma 7 (Decrementing Lemma). Let dembed 2 5 and H [holisise Bedembdd be embedding matrix such that h ((dembed-2):(ddem 2):(ddemeed -1) = (I) I2) = I, and h h.fembed 1. Then for any
T1,72 with 1 I T2 I dembed 3 and any ki, 12 with 1 < ki, k2 and any M >> there
19

---

Published as a conference paper at ICLR 2026
exists six-layer residual feed network (FFN) such that
h4
ift E f1. A11 u -.2. .4
(hx)1
(he)rs-1 (he)rr M
:
(h+ h4
(he)rz M (he)ra+1
otherwise
(he (he)demdedd- -3
It
1
Additionally, we have ||0pFN|lo S O(EM).
Lemma] 7 is proved Appendix E.8 Lemma 7 utilizes feedforward layers to substract M from
certain rows in specified tokens.
We next state the Dudley Entropy Integral (Dudley 1967) which is used to derive 23 p. and refer its
proof to Chen et al. (2020) and Van Der Vaar & Wellner (1996).
Lemma (Dudley Entropy Integral). Ler M > 0. Suppose supser = S M for some function class F. Then
12
(M
Ez,g sup SEF n
(x;
< inf e>0
2e +
(log.((FFF.11 1|ا=0 d8
(26)
Vn
i=1
where W,,,T,I, Il I| is the 5-covering number of F with respect to L norm
E DEFERRED PROOFS
E. PROOF OF LEMMA
Proof of Lemma First, we embed the sample s = {(x,, "= into the embedding matrix H such that
X1
X
x
0
On
0
0
PE+ E(s) H1
0
0
E RRdembed
Ii
Izn+
1
We denote the i-th column/token by h; in the following proof. Throughout the proof, we let which is the largest -iie magnitude of the matrix.
U=
|| |
Next, let demonstrate the construction of (s) step-by-step step using fundamental lemma in Appendix(D D
Copying of (xn+1)a 1.. 1 i i D, to the next column (constant multiplication by 1).
Let us define each attention head A, i & D, with V; e;e e dembed? and data kernel in the form
20

---

Published as a conference paper at ICLR 2026
0
0
:
Qdata
0
0
K ddata
0
0
0
0
0 M
where Quatt, Kdaato E IR (RD+2)x(D+5), The Qdata has the i-th position and last position of the last column equal to 1. By the Interaction Lemma
construct A,, I - D, such that h,-2
interacts with h only, i.e.
[A. = a (Q hut2, kdata hn+1) a ((xn+1); + M)e; ((xx+1)s + M)e; and [A:(#)]: O when 1 + 2. Then the residual multi-head attention yields
Xi
Xn
Xn++1
Xn+1
M
0
V1
Un
0
M +
0
I1
I2n+11
1
Similarly, we can copy (xn-1)t, < S D, to the k-th column for l = n + 2, ... 2n + 1. This gives
X1
X
X
Xa+1 M
Xa+1 + M
y1
Yn
0
0
MHA H)) + H =
0
Zi
Izn+1
Then apply Lemma 7
to subtract off the constant M to get
X1
Xn+1
Xn+1
x
V/ Yn
0
0
H1 = (H
0
0
I
12n+1
In total, this process needs B, B(nD,6, D + 5). The upper bound of the weights parameter in B is 10,, - ((D4
Implementation (xx+1): 1): (xx); ) for sis D and S Sn n
Let us define each attention head A with V; e,e dembeed' and data kernel in the form
0 0 0
0
0
:
Qdaat
0
Kduta
where Quata Kddata (P++)) The Quata has the i-th position of last column equals -1
and last position of the last column equals to 1. By the Interaction Lemma 5 we can construct A such that h j interacts with hy only, i.e..
21

---

Published as a conference paper at ICLR 2026
Acs(hn+1+s) = (Q N +++ Kaatah,) Vih; = =x(-(x)); M)e;
(-(x)); + M)e;
and (ha( = 0 for + + 1+ j. where M 2 b |||| Then the residual multi-head attention yields
X1
Xx
Xa+1
Xn+1
X1 M
Xx+1 X, + M
Y1
V/
MHA(H)) 11,
I2n+1
Then apply Lemma
7 to subtract off the constant M to get
X1
Xn
Xn+11
Xn+1
X1
Xn+1 -
Xn
y/
Vn
0
0
H2 = i2
12n+1 In total, this process needs B2 BnDn, 6, D + 5). The upper bound of the weights parameter in B2 |00,11 s O(D*))
I1
Implementation of ||x--1 12 for S.j
Let us define each attention head A, with V,
ep+1 e dambed" and data kernel in the form
0
0
0
0
h
:
Quata
0
0
0
K
0
0
0
0
1
0
M
where Quata Kydaa ((D+)))(D+5) By the Interaction Lemma hatitj interacts with itself only, i.e.,
we can construct Ay such that
Ay(h+t145) a((Qdata Fn- 1 K-daaa bn 1n+11))) ( V3s++)
=o 122 (xn+1= Xj, Xn+1 - X1) +
X
x2
eD+1
+ M
ep+1
h22
and A,(h,) = 0 for + n + 1 1 + where M 2 max
4122D R).
Then the residual multi-head
attention yields
H3 : B3 (2)) MHA(H.) + H2
X1
X Xa+1
Xx+1 X1
Xn Xx
V1
0
x
11
12
+ M
Xx 1 xx,1 +
M
0
I
I2n+1
where Bg E B(n, 1, + 5). The upper bound of the weights parameter B, is 10 loc 5 M(2)
22

---

Published as a conference paper at ICLR 2026
copying "1.... Un from columns 1.... ..... n to columns 2. 2n +
Similar as before, there exists B₃ E B(n, 1, D + 5) such that
Xi
Xn.
Xx+1
Xn+1
Xn+1 Xn
y1
Un
x -x+1=
h2 +
M
|x -x=1lxlll + M
42
(H)(Ha) + H3
0
y1 M
Un M
I1
12
4b
Then apply Lemma
7 to subtract off the constant M 2 max 1a
RR) to get
X1
Xn
Xn+1
Xn-1
X1
Xn+1 Xx
y1
0 yn
0
Xx, 1.1 x1
h2
Xn 12
-xn1-xmll x..l?
H4 (H3
//
Un I2n+1
I1
In total, this process needs B, B(n, D. + 5). The upper bound of the weights parameter in B₃ is M+)
[BB, x s O M²)
Implementation of (s)
In the last layer transformer, we use Softmax instead of ReLU for this part of construction (with mask of size nt). Then, we can construct V eD41e SD410042 and
0
0
0
0
0
Qdata
K K
0
0 0
0
0
0
0
0
where Quaate (DD+2)x(D-G) has (D 1)-th position in the last column equals and all the
other entries are 0, and Ka E (P+2))(D+5) has (D 1, D + 1)-th position equals to 1 and all the other entries are O, such that
[A(H4))+11
Σ
softmax ((Quata hn+1, K data Hai), Vhg
j=n+2
n
yj ||-=] ///
Σ
x/11//12 -D+1 Kr Wi X.+1) eDD1 Kn(s) eD+1-
[x++]
j=1
Therefore, there exists B5 B(1, D + 5) such that
X
Xn
Xn+1
Xn+1 X1
Xn+1 X
1/1
Un
(s)
1xn+1-Xi
X 1-X
1/²
H3 = (H(H,)
0
3/1
yn
I1
Izn+1
The upper bound of the weights parameter in B, is |0, Imo OOD*MM? 1) 1 (D
Finally, we apply decoding layer DE to output the element (s)(s) as desired. The uniform upper bound for the weight parameters in B; o B, o Bg o Bg o B, is k < O (D* M < 0 D ga h
D 28" 2
48
23

---

Published as a conference paper at ICLR 2026
E.2 PROOF OF LEMMA 2
Proof of Lemma 2 Lemma estimates the bias of kernel manifold regression. Our kernel estimator uses the Gaussian kernel, which has infinite support. To deal with the infinite support of the Gaussian kernel, we decompose the integral to nearby regions and far-away regions. For the x close to the center 1, use the Lipchitz property of estimate the bias; For the far from the center Xn+1, we use the Gaussian tail to bound the bias.
We first rewrite the bias in integral form:
I8 (x xx] ((x++1)
xn+11)+ - [(x++1)
IE (x(xxx11111 x)]
J KA (x)+t-x))((e xx)f(x)dx ((xn+1)
S Kn x)dx
J Kn(xn+1 xx) (Xx+ ddx
J KK(xx+1 x)dx
We consider the of points on the manifold M which is h distance to xn+
(x(x++1) == {x E M: xX xa+1 S Ch..
The choice of h will be specified later in the proof.
So we can write
SpH,0... 12) -x(xx41-x))1 xf((xx) f(xx+11)) 1))x
(fixx11) f(xn-11
1 [K((x - x)dx
(x (x -x)(f(x) -(xx+11))dx
I KN(xn++ - x)dx
(B.(Xnn1)) Kn(Xn+1 L2h) dx
2R. (M Kn Kn(x1+1 x)
+
S [a(xxt1- - x)dx
S KK(xxn1 - x)dx
2R SMMBB, 1) Ka(xn+1 - x)dx
s 4 +
S KK(xx441 x)dx
In the calculation above, we used the Lipchistz property of for the integral inside the ball By (x.+1). where the geodesic distance and Euclidean distance are equivalent metrics. By Proposition 11 in (Maggioni et al. 2016), when ||x++ - x|| < TM/2, we have
x) 2||xx+1 x||.
We next bound the integral outside the ball B3 (xx+1). When is small, i.e. TM/ the integral satisfies
Sma h 2-dKKa(xni -x)dx
/ h-de
|x1+1-x|22 62
[10-11 xx| 62
dx
h h-de
dx
M
Br(xatt)
2 f Br(Xes)))
h-de- h -e- -e
=e-1p
with
Cp cos (arcsin) ( cos (arcsin())))
(27)
according to (Niyogi al. 2008 Lemma5.3).
24

---

Published as a conference paper at ICLR 2026
Therefore, when h 7/2, the integral outside the ball (x can be bounded as follows: 2R JM (x6411) Kn (n(xn+1 x)dx
2R JMIBRIX.E1) h "x((x+11 xx)dx
JM [x - x)dx
h (Nn+++11 - x)dx
2eRC
h h- (Xn+1 x)dx
MIBB
S 26 Re (px(M) - (x(BB((xnt))) . 4
la Ch 2eRCB (Dx(M) (x,x(xx++1)) h c c²
S 2eRRC
h he
O(h 10---e--
where O hides constants about R and d.
Hence
Rx(fixn+1) (onett))((xxx-t)) f(xx+11)==++)) O(0"1")))))))))))00000))))))())) +(h -
For (0, by choosing C v (d+g)) have h h = h. Therefore,
(f f(xx+) S0 ha I ( +0(0) : (no1og =0(10100
1
as desired. The notation (() hides the constants depending on d, I,, R, TM-
E.3 PROOF LEMMA
Proof of Lemmna Lemma 3 estimates the variance of kernel manifold regression. We prove it using
a series of concentration inequalities (Hoeftding) 1994] Vershynin 2018).
Let us define some empirical quantities used in kernel estimator and their counterparts in expectation.
(x(x4))) = 1 Σ Kn (Xn+1 xx)
(x(+)) 72
Kn (xx+1 - xx) f(x:),
n2
N(x++1) Ex [Ks - f(x)), D(x,+1) == Ex [Kn (xn+1 - x)]
We first decompose the variance as follows: (K((s) (n(fix++1)l
1
(ID(x)+t)I(N,(xx)) - N(xx+1)l |NNl|+NNN(xaaa (N D(xx+11l)
((xx-1)) [x((x))) [(xn-1)) (1Dn(xn-)) D(xx+1)))
[N(x++1)
[Dx(xn+1)
(28)
We will bound 28 in the following steps.
Estimating (x in the denominator. We consider the following ball
Bj = (x.+1) = e |x x,+1 < h}
(29)
with π = Ch. Let ns be the number of samples in B3, (xx+1). 30), we can estimate n as follows:
). By Liao & Maggioni 2019
Lemma
n P
Px (xx+1)) 2 (B, $ 2e
3n (2 (K, 11)
n
25

---

n Published as a conference paper at ICLR 2026
where Px (Xx+1)))) CBh CBC for some constant Cy which satisfies 27 with probability at least 2
Therefore,
(Rp (1++1
25
it holds
nB 2 (Bx(((())))))
(xx((x(Xx+1))
n
We next re-write D (xn+1) as
Dn(xn+1)= =
RB
-
BB
E
Kx(xn11 Xx))
BBB
BB x.E (Xn++))
where the continuous counterpart 1.
(xIEB(((041) Kn Kn(xn+1 - xx) is
Ki(x xn+1)dx 2 Dx(Bi) / Ki(x - xn+1)
4 =
(Br) Br
Br
Px C4C-d
Px (x
where Cp is constant depending TM-
By the Hoeffding's inequality (Hoeffding 1994), with probability 1 1 5, (xn+1) satisfies
(x(xx+1)2
2
nB
(2/6)
Cac-a-
log(2/8)
n
7B
n
Bounding the first term in
28). The numerator the first term can be decomposed as
Nn N (xxx+1)
(1)) (Xn+1) - (2 (x.+ + N (x.+1) _2 (x.+1))
<
where
( (( (xx+1)
Σ
Kh (xn+1 x:) f(x:)
n
x: XiEB, (Xn+.)
and
N (xn+1) /
Kn(Xn+1 - xxx)xx
JxE (x.111)
and
[2(2 (xn+1)
Σ
Kn (xa+1 xxi) f(x:)
n
(x
and
(222 (x2
JxEM)Br(xxH) -x)xxxx)x)((x()s>
Therefore, just need to bound
( (xn+1) - (1) (xn+)x + Ni ( (N2
Dr (x
(((1) (xn+1)= - ((1) (xx+1))
(22 (xn+1) - (22) (x2)(x++1) (x
(30)
CoC-d log(2/5)
CoC-d
(2g
ng
n
26

---

Published as a conference paper at ICLR 2026
The first term in 30 can be written
1 (x++1) - N (x
CxC-d / log(2/8)
nn
Ex, EB (xx+1) Kn (xn+1 xi) f(xi)
n Sxe B (xn41) Kn(xn+1 - (x)
nn
CxC-d -Vooce /10x(2/00
n2
JZE (Xm+1) Kn(xn+1-29 - -x)(xxxx 1 Ex Bi, (xa+1) Kn (xn+1 xx) f(x:) Px Px(B,)
Bg
CaC-d- 1oR(2/0)
n1
Px(Bp (xEBr(Xx.))) Kn(x++1 xxf(x))xx
JXEBI (x.+1) Kn Kn(Xx+1 xx()xx
ny
C4C-d- - [og(2/5)
RB
By the Hoeffding's inequality, we know that with probability at least 6,
log (2g(2/6)
KA (Xn+1 x:) f(x:) Px(Brr (x
Ka(xn+1 (x)(xx)xx
S RV
n
x;E (x.+))
By Liao & Maggioni (0019 Lemma 30), with probability 1- 6,
Px (B,(2))))) so 50(1 1og(2/8) px (x++1)
n
which gives rise to
Kn(xn+1 xxf(x) n
Kn(xn+1 - xxx
(x(
(x
nB
Kz(xn41 - fx)(x
S (Dx(BR))
n
(x
1l
(xn11)
Px (B,)
11
= R 1
n
Px (B₁))
R
Px (Bp)
50
R
(og(2/5)pp pxx B (x++1))
ng
B
Px (B
log (2/6)
0
[R. nxpx Bíg (xn+1))
Therefore, with probability at least
26, the first term in (30) satisfies
N (xn+1)= ((0((xx+1) -V1 (Xn+1) (Xx+1)
log(2/5)
log(2/8)
00 RC
RCd
(x(xx)1)
+
V
npx (Ba,BBr, B (xx+1))
log(2/5)
|RCd/2 V
(Tog(2/0) nhd
= O RC
mPx (xx+1))
=
VUn
(31)
where the constant Cn satisfies 27
27

---

Published as a conference paper at ICLR 2026
For the second term in (30). it satisfies
( (xn-1) - NT(2) (x
(x(xx+1)
ExEEM Kn (Xn+1 x:) [xx:)
-XEMM Br (x.+1) Ka Kx(xx11 - xxx(x)
C+C-d
/ ne
By the Hoeffding's inequality, we have with probability at least 1 -6 6,
Kh (Xn+1 xx) f(xx)) SEE (x Kx(xx1
log(2/0)
Σ
xxf(x)dx S Re Re-C*
1
(M
where we bound [f(x)] e- for all x E M B₁. Therefore, the second term in 30 can be further bounded as
2 (Xn+1) (xn+1)
Re Re-O2
log(2/6)
0 C e n
log (2/))
Dxn(1+1)
C
log(2/8) BB
BB
C²
(log22/8) nhd
(32)
hd/2
In summary, the first term in
28 can be split into two terms according to (30): one term is inside the
ball B and the other is outside the ball. We have bounded the term inside the ball Bj. in (31) and the term outside the ball in (32). Combining (31 and (32
gives rise to
[N((x+1) N(xn+11) 50
RC
log(2/0) nddd
C2
log(2/6) nhd
+0
(n(xx+1)
VCB
hd/2
=0
[Log (h 1h=
V
(og(2/5)
nh
where the last line results from choosing
C / llg((//))
(33)
that e -C = h < h/22 when h is small.
Bounding the second term in (28). The second term in (88 can be bounded similarly to the first
term, with an additional estimate on N(x441) We define the ball B, (x,-1) and Bj, (xx+1) as in (29 D(x.11)"
with 7 = Ch.
((xx+1)
LM KA Kx(xa+1 x) (xx)
D(x++1)
Sax (n(xn+1 - x) x)dx
S Spp.ten1a) Kr K2 - fx)dx + SM
(x, (1) Kn(xn-1 xx)xxx
[ Kn (xn+1111 x)dx
RE O2 Px(M) {O(RC().
- (xx((xxxx)))
where the last inequality holds with C' chosen according to (33) and when h is sufficiently small.
Applying a similar argument above, the second term in 28 can be bounded by
[N(x+11)l (x(xx)))]-- [D(x++1) (1Dn(xnt1) - D(xn+1)l) 0 3dg (1)
log (2/() nhd
28

---

Published as a conference paper at ICLR 2026
Putting the two terms in
28 together. Putting the two terms in in 28 together, for 5 >
Bm Pxx (B) Usn 11)
2e
We have with probability at least 28,
(100g logiu//4 (
1og(2/0) nhd
(K)(6) - (n(f:x++1) 5o
By abusing the notation, rewrite 26 as 6, we get with at least probability
1
-K)(s) Kn((fix++)) 5 lug (H)
(og(4/0)
ahd
as desired. The notation (-) hides constants depending on d, R, TM-
E.4 PROOF OF PROPOSITION 1
Proof of Proposition
By Lemma and equation I9).
Eg RR, (T (s)) S (1 6)- [log 11- 3d/2 log( (gg(4/)) nha
8- (2R)² +0 [log(h )1
(1 4h12) . O [log (h (1=1))sa)) 3d/2 log(h
let 4=
161 + 0(1 [ogg(1 ))))))
nha
0 loog (h ( 1)/1++3//2
O0h22 ))))).
nhd
The last inequality holds because 0 < h < 1. The notation O(-) hides the constants depending
d, L, R2 TM.
E.5 PROOF OF LEMMA
Proof of Lemmal 4 Through the proof, we the notation | |loo infinity-infinity norm of a matrix H.
|| 100,00 to denote the
Since our transformer has softmax activation function in the last layer and ReLU activation from the first to the penultimate layers, we need to consider those two cases separately.
Set r7 0, choose T with parameters 0, and T' with parameters 0' such that ||0 0 77.
We first bound the Multi-head Attention (MHA) layer in transformer block. For the ReLU activation layer, according to Havrilla & Liao 2024 Lemma 2), for || I U, we have
(MHHA(H) (HHAg(H)II) ReLU < 3x dembea 3 mp mnn
By the similar argument, for the softmax activation layer, since takes normalization, we can bound
softmax < [MHH, - (H)) ReLU < 31.3 dd dembrrd mypen ||HH| MHA2 ||
Therefore, for the MHA layer, we have
|M)AA(H)) MHA,(H))l S 3r. de deebeed S my
Next, we bound the FFN layer. According to Havrilla & Liao 2024 Lemma 2), we have
(F + (H) FF + MH))
< 3rd LEEN 2LyEN
Lembeed 3 merln + LyEN (wFe (2d (2af Umrl) + Lee--1 WEFN
29

---

Published as a conference paper at ICLR 2026
Therefore, putting together the MHA and FFN layer together, get the estimate the difference of the transformer block [[B - (2 cl ( for both ReLU and softmax activation) as
|B (H) (2
-I(H (HA1(H) + +
(H + MHA2(H) FFN2(H 2
|MHA| (H) - (H))(H))
+ ||FFN, (H MHAI(H) FFN2(H MHA2(H))l
3r Sembed mmrln + 3h LoEN 2LEEN Lembed mlt
WFN
+ (PFFN(WFNNL ( eesee UmrT) + (KWFFN) L
<(4R 3+
2LeeN Lembeeu mT& moe LEFN(WFEN (W((WW(FFNNENeeE)) (meem + (KWFFN)) LEEN -1 J)n, WFN
Then, we can chain the multi-block together and have the difference
13 eli [BL ... (H) B',, (HH)l S 2 SiFFNU3h d LeeN x ,6 LEEN mep'
Recall that the decoder layer Rdemdeaxe - R is fixed and it outputs the last element in the first row. For the encoding layer H = PF. + F(s). both PE and E. are fixed and we have [PE + (s) Iloo = ||s|o0 + < U + Thus, together this gives the total error bound between T,7" E T(LT, MT, dembed, L, LFEN, WFEN, R. with 100 0' 0' S 17as
[T((s) (s) = IDo BL, o o...B. B1 o (PE + E(s)) - D' o B',, o...o (
< 2 LFENU 3rr dl LEEN k L.EN 19 r
mip
Notice that the total number of parameters in the transformer class T is
LT
00| = 10
+
Σ
10 + 10 dembed + (3d + LFENWTeN) + dembead D
dembed ( 1)
+ LEFNuFEN).
Since the number of steps for each parameter 2x then the covering number 7.
N(6,T, V1 11x0)
1i gL3, LEEN GL LOWN 2x 24 LFFNU LT LBEN,
(Dmbea mar
(D=1) - LOFN
22 LFFN 3LT d dembedd
Leen LoNN 1. gLz, mip mm
For the covering number L T, we have ||C(T, s, v) - C(T', s, 3l (T(ss) - vn+1)² < 4R|[T((s) (s)) Therefore, the covering number N68, L. llo))
12 gL3 4R 2k 21 LFEN TLT 1813 LEEn LLFN myg
(Dmics(D+1)=11e (3de t Epexw
203+1 LAHALFEUUUL 1887 Leen GL7 LErN+1 17 gbt myp +n
as desired.
30

---

Published as a conference paper at ICLR 2026
E.6
PROOF OF LEMMA
Proof of Lemma
For convenience, we denote the i-th token in the output by
A(h,) == [A(H]], Ejn ((Qh, K
(34)
This formula illustrates that the attention mechanism performs weighted average of token values based on their pairwise interactions.
Let us defined the query, key, and value matrices as
Quata
Kdata
Q na
(Q 1,2
0
(K
(K*
1,2
0
Q
and
0
2,1
(Q 222
0
(K 22,1
(K7
222
0
0
C
and e,e dembed"
Here we call Qdata, Kdata Iddeebedd (eeembea-3)xdemeee the data kernels, Q²
(Q 1.1
(12
(K²) (K²) ),2 1,2
E 222 and KJ =
R2x2 the interaction ker-
(Q 21
(Q²) 2222
(K3)21 (K2)22
nels, and C is large positive number.
Let us choose QT,KT KT such that K Pı., is a projection onto Itz, and Q is dilation and rotation of I, onto I, i.e., I CTa,- Now let compute A(h₂) for t = t and + f1.
For any s S we can write the action A on he as
A(ha) = Σ ((Qh, Khg))hh
((Qdata he, Rddat + (Q=I,, K²Ix) -C),. e,
Case 1: = t1 and k t2. By construction, we have I, = (CIN,I C. Therefore
((Qdutape, K dra) (Q" K -C) ((Qdata Kddata he2) + CC-C)
a ((Q her
Kddata hea))
Case II: t = l1 and h: + lig. We have (Q"I,,, K K²Ix) S I - Itllz C. The last inequality holds since | Ialla when l + t2. Thus, for large C, we have
((Qdata hess Kddta lea) + (Q K KTI,)) C) ((Qdata hes Kdatapa) CIIPI,, Iplla -C).
(Quaet Kducohu) hu) 1 P1 Ixllz
By choosing (Qraato he, Kddata hrdattah))+Ci +C] Is 112 - < 0. or equivalently. C> we get
((Qdata hes data hu) + (Q"I,I, K K"Ia): Combining Case and II, conclude A(ha) a ((Qdata K (edatape))) e, when t t1.
C) s a ((Qratthee hes K ha) + C C) = 0.
Case III: t * t1 and & = t2. We have
Q KITr) I12= cos(O...))
where O,,, is the angle between QJI, and K KII,,- Since & l1, Q # CIn, cos(O <
(Q be Kdaee hez) we have
Then by choosing C >
1000(99,2g)
((Qdata hi kedutapey) +
= -ooodat ((Qdatapu he, Kddatahe) + Cos((Br..)) C) 0
Case IV: # and k * to. In this case, have ((Qdato Kidatahe IQ C 0. so the argument follows the same way as Case 2.
Combining Case III and Case IV, we conclude A(ha) 0 when & l-
31

---

Published as a conference paper at ICLR 2026
To obtain the bound on the constant C, we need C > max (o Redolemnd (Quotu he Krcuttu big) Both numerators can be bounded by
1- [1 Iallz
1 cool 000(01.32)
IQqaato he, Kddata h&)l & l|Q
he 1222l K (odata hallz S [1Q 11,1 112,1 2o Krdata 111ellbolooo
||Qdate| 1o, dembeed | bo, Le Lembedd S dh embeat U
The two denominators can be bounded by
π 221 -21-(1-0(3))-01
1 1 P Ixll2 2 1 cos(
2
and
- cos(00.22) =1 (Ie+ta-12 Ita) 2 cos(
2 1 (1-((1-0(-)==00
2f
The O()) hides the dependency some absolute constant. So we conclude C = ( Odd embeed 2 U2)
E.7 PROOF OF LEMMA 6
Proof of Lemma We denote the i-th column/token by h; and j-th component of h; by (he); in the proof. Recall that I, is the sinusoid positional encoding, it is easy to see there exists some k1 } and == (V1, v2) E 31 such that Iz >> for (1....,k, Then for large C, we can construct (all the blank places are filled with zeros) with CV,, Cur appears in dembedd-2 2-tt and dembed-3-th columns, from row rı to row r2 for S rı S 12 I dembed-3-
< 0 for
-.,,-... ,.).
Cv1 Cv2
:
Cv1 Cv2
W1
Rembed Xdembed
=0= R dembbed
1
-Cvi
-Cv2
-Ov
-Ove
W3
E &Teeembe xdented,
b2 = 0 E Redmmed
32

---

Published as a conference paper at ICLR 2026
so that
(he)1
(he)1
(h a((he)n + CI+.v)
(he)ri-1
21 oW2h + +b,)
a((hi)r + -II.v) (he)rat1
(he)ra+1
(1e) (Ne) I
(he) (he)demeeds I
I
I
and
(he)1
(he)2
(1
(helr (be)rr +CI, '
a((ht) + CI. v)
1 = oW2h, + b,)
a(hh)r + +II+ v) (he)ra+1
(he)es + C (he)rat1
(he (1t))anpodd 3
(ht)dampees 3
I
I
I
I
Then apply the second layer yields
(h+)1
(ht)
(ht)r-
(he)--1
(he)r
(hirrs
22 = W2 + b2 =
and
22 = W221 + ba =
(ht)ret1
(be)ra41
(ht) dambbed
(ht) (he)dembed-3 I
I
I
I
respectively. This shows (44 Similarly, there exists (v,, V2) S' such that I, for = (1. } and Z, v > 0 for L {ki,... l}. Applying the same argument we get (25
To obtain bound on the constant C, need CI, v| > || Hence C'
|||| [.vl
O(e])
33

---

Published as a conference paper at ICLR 2026
E.8
PROOF OF LEMMA 7
Proof of Lemma
Given an H [Mu] we apply the first layer of FFN with
M
Wi
Bdembed Xdembod and b
M
Bembbed
so that the output after the first layer of FFN
is
M
M
H1
M
M
I1
Ie
Then by Lemma there exists two-layer FFN such that the output after applying these layers become
M
M
H3
M
M
0
E R RemmbnaXt
I1
Iuz
T
Ie
1
1
Again by Lemma 6 there exists a two-layer FFN such that the output after applying these two layers become
0
0
M
H₃
0
0
M
M
0
0
IR
dembbaxX
Ij
IkA
I
Ie
1
1
Finally, we apply a FFN with
W6 =
E Redemtd X dembed
and
bg = -0 E TRd Rombbed
34

---

Published as a conference paper at ICLR 2026
where the entries -1 appear in T1 r1-th row to r2-th row and r1-th column r2-th column. Therefore, the output after applying W6 and b& is
0
0
0
0
O
M
M
1000
H6
M
M
E
Reddeed
0
0
0
0
I
Iki
I
Tka+1
1
1
where the entries - .M appear in ri -1tth row to r2-th row and ki column to k2-th column. Therefore, the residual FFN gives the output
h4
if E (1,... A113 U (k2,
(he)
(he)r-1 (herr M
FFN(h:) he
(he)zz M (he)ra+1
otherwise
(he)dembed- 33
I
1
as desired.
E.9 BOUNDING THE ERROR II IN 16
Since 0 - (T*
1 3 w < 4R2, by Hoeffding's inequality, for any / 0, it
satisfies
Pr
P(R,, E, (T" 2 t)
Hence with probability at least satisfies
log (/8)
Rr, - E, (T. (T. < R²
Let 8 = 11?, we get
Eg (R',((T)) - E, (T 50 (V
log(h-1
r + 122 )1))
where 0(-) hides the dependency R.
35

---

Published as a conference paper at ICLR 2026
F ADDITIONAL EXPERIMENTS AND DETAILS
iin+
2nn
22n+1
T
3,m
31,++1
H
Vi
(35)
0
I1
It
1
F.1 ADDITIONAL EXPERIMENTAL DETAILS
For the transformer architecture we used for the experiments in Section we fix dembed = 8, LT = 5.
LeNN 6. The number of attention heads m for n = 4, 8, 16,32. 32. We generate T 50000 for both training and testing. The model is trained with batch size 100, using Adam with learning rate 0.0005 for 100 epochs.
For experiments in Section we fix dembed = 8, LT 5, LFNN = 6, and the number of attention heads m 2, 4, 8 for 16, 64, 256 respectively. generate r 400, 1600, 6400 for both training and testing. The model is trained with batch size 100, using Adam with learning rate 0.0005 for 100 epochs.
To make the experiment setup the close the last layer of our transformer model, and ReLU activation all the layers before the last layer. The activation function for the feed-forward components are ReLU activation.
theory suggests, apply the softmax activation
The following sentences are used to generate the attention score curves in Figure tences cut in the end that all the sentences have the same length.
3
Sen-
"In the quiet town by the river, a curious child spent the afternoon reading stories about distant galaxies and dreaming of becoming an astronaut one day."
Sentence 1:
Sentence 2: "The professor walked slowly across the lecture hall, carefully explaining how black holes bend space and time while students scribbled furiously their notebooks."
"On a rainy evening in Paris, a young artist painted the city's rooftops in dazzling colors, imagining how the world might look if dreams could shape reality."
Sentence 3:
Sentence 4: "The spacecraft drifted silently beyond the orbit of Saturn, transmitting faint signals back Earth as scientists waited anxiously for news its discoveries."
Sentence 5;
"In the heart of the ancient forest, an owl watched quietly from a high branch, while fox padded softly across the moss-covered ground below."
F.2 ADDITIONAL EXPERIMENTAL RESULTS
36

---

Published as a conference paper at ICLR 2026
"earson correstiin 0.912
Pearson corre z6en 0.786 derwi Prscdie
Pearson comeetaion 0/683
alrrnn-lrrinnssn aamel
deddeess larmll Landler
04-
SCtfed
Pearson comrestinn 0.917 deme fandle
Pearson corre z0cn 0.940 oerell fulcdii
Pearson comelasion 0:751 larval Landle
035-
6:3
622
sortect Eook
sorted PYORE
scrbed Index
comrertion ailrur Eanioon almel Fancike
COmTO BOOR
comerszioon
Grmell Procie
4/C
013
soated EoOk
socted Endee
sorfed Inder
Pearson correrticn 0.906
Pearson corre 0.765
Pearson corretstion 0.622
wiliua Bww.iei SURE
3.44
K-2-
645
652
10
Figure 5: More examples of attention scores and Gaussian kernel function with in-context length
4, 8, 16, 32 respectively.
37


Reviews:
[{"review_id": "gXCxEM2fN9", "reviewer": "Reviewer_pVF9", "summary": "The paper analyzes in-context learning (ICL) for regression of Hölder functions on a compact d-dimensional Riemannian manifold. It establishes a connection between the attention mechanism and kernel methods, showcasing that attention interactions can be seen as regression kernels. The authors then construct a transformer for kernel regression. Building on this construction, the authors derive a generalization bound for transformer learnability and statistical difficulty. \n\nI would like to not that I am not an expert on this topic (especially for proof details), and will defer to other reviewers for more in-depth judgement, and put a low confidence on my review as an indication of this.", "questions": "- I understand that this paper differs from Kim et al (2024) in the network size and exponential rate, but why is a comparison to their baseline not provided then, if it is the closest paper in the field for the empirical results?\n- Why do the p-values have very large standard deviations in Table 1?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper is well-written and generally easy to follow with novel contributions.\n- Lemma 1, where the authors explicitly construct a 5-block, multi-head transformer that exactly equals the Gaussian Nadaraya–Watson estimator on the prompt (no approximation error), is easy to follow and clearly makes the connection between the styles of methods and regression. \n-The task-/prompt-level generalization analysis is interesting and very relevant for the field. The decomposition isolates (a) learning the algorithm across tasks and (b) per-prompt nonparametric difficulty on manifolds.", "weaknesses": "- The assumptions for the generalization error bound in Section 5 are quite idealised and strong. For example, the assumption that $p_x$ is uniform is unrealistic, but understandable for the work. A discussion of where this assumption might hold and where this framework may break down due to these assumptions would be helpful to add to the Appendix. \n- Although the paper's main contributions are the theoretical bounds and connection to kernel methods, the empirical experiments are fairly weak to show the practicality of the kernel-attention connection. As such, the paper is mainly a conceptual contribution.\n- The network class of $O(Dn)$ heads and length $2n+1$ is computationally heavy for any realistic $n$ and $D$ with a larger dataset and prompt. No efficiency argument or parameter reduction is provided, and no experiments report compute or runtime scaling. Therefore, the construction serves more as a conceptual bridge than as a scalable algorithm. As such, this makes the connections to typical LLM configurations weaker, and difficult to understand when practically useful. It may be helpful to provide a compute/memory profile for the constructive transformer and show that trained practical architectures (far fewer heads) empirically approach the same behavior. Larger context lengths in Table 1 would also help to clarify this.\n- Additionally, the constructed architecture is a synthetic transformer for kernel simulation, not an explanation of why actual transformers implement kernel regression. Without ablation experiments showing convergence toward this construction under realistic constraints (fewer heads, smaller width, learned parameters), the claim of “bridging attention and kernels” remains largely conceptual.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l7w5IrYTKi", "reviewer": "Reviewer_Sc1b", "summary": "This paper theoretically studies in-context learning on structured data represented as manifolds pertaining to certain assumptions. They start with an explicit construction of a transformer that can perform Gaussian kernel regression without any error. They also give a theoretical framework for generalizing this result by analyzing transformer-based ICL to Reimannian manifolds, and give bounds on the error which are tighter than existing ones. Subsequently, they verify the theoretical claims with experiments that show that the bounds are indeed as one would expect.", "questions": "- Line 790: What is P_f?\n- What are hidden tokens in Def 3? And how are they represented in the input?\n- Will the construction change if softmax was used as an activation in all the layers instead of ReLU? It would be nice to know what went wrong.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- This is an important direction which theoretically studies theoretical representational strengths of transformer-based ICL, and relates it to the role of geometry of the data.\n- The approximation bounds provided are tight.\n- This will have several scopes for future work, where learning techniques can be studies using similar methods to relate to the structure of the data.\n- The proofs are very nicely structured despite being long, which makes them easy to understand.", "weaknesses": "- Since the main purpose of the work is to provide a theoretical analysis, more emphasis should be given to the results and the proof techniques in the main part of the paper. Especially a proof/technique overview along with the first part of Section C would make more sense.\n- Section 3- Please define the input tokens more precisely, for e.g. we are given with (n+1) tokens where the first n tokens contain (x_i, y_i) and the last token contains x_{n+1}, we expect the final output to be present in a certain token etc. Also is \\Gamma the batch size? I thought later it is used as the size of the training data.\n- The constructed transformer has 5 layers, it would be helpful to give an intuitive understanding of what those layers perform.\n- The paper assumes some background on manifolds, but it would be better to explain the concepts more elaborately, especially in Sec B.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ubg7hOXyvb", "reviewer": "Reviewer_WAPE", "summary": "This paper provides a bridge between Transformer attention mechanisms and classical kernel methods in in-context learning (ICL) over manifold-structured data. The authors prove that a Transformer can exactly implement Gaussian kernel regression and establish an approximation error bound for α-Hölder functions on compact Riemannian manifolds, which demonstrates dependence on intrinsic (manifold) rather than ambient dimension. They further validate their claims through simulations, observing high correlations between attention weights and Gaussian kernels.", "questions": "1. On Remark 1 (Universality), the lemma asserts that the same parameterization works for all f and {x_i}. Could the authors clarify how positional encodings and attention masks encode x_i-dependent interactions without weight adaptation? Does this require scaling of input normalization with h or b?\n\n2. The generalization rate depends on the kernel bandwidth h. How is it chosen or adapted across prompts/tasks? Is it optimized implicitly by the Transformer parameters, or assumed known? The statistical rate in Proposition 1 seems sensitive to this.\n\n3. The analysis is limited to α-Hölder smooth functions, but why is it required? Could the framework be extended to broader classes such as Besov or Sobolev spaces, or to non-compact manifolds? Can you discuss how would that alter the covering number and rate derivations?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "+ The paper aims to establish connection between attention scores and kernel estimators (Nadaraya-Watson). This yields a new perspective on Transformers as in-context kernel learners, which conceptually advances and generalizes beyond prior linear-model analyses.\n\n+ The construction of Lemma 1 remarking that a Transformer network that exactly realizes kernel regression with zero approximation error is nontrivial. The explicit architectural specification further concretizes its theoretical claim.\n\n+ Theorem 1’s bound  separates the task-level and prompt-level effects, showing minimax-optimal scaling with intrinsic dimension d.", "weaknesses": "- The theoretical results rely on exact kernel implementation via attention and perfect manifold sampling. These assumptions may obscure how robust the results remain under approximate or noisy conditions typical in practice.\n\n- Some key proof components, particularly how the softmax attention with masking produces the Gaussian weights in Eqs. (12) - (14) are deferred to appendices. The main text should outline at least the constructive steps more transparently for better readability.\n\n- While the simulation results illustrate correlation trends between attention scores and Gaussian kernels, the experiments are synthetic and low-dimensional (S² sphere). There is no ablation on real-world datasets or on deviations when the model is not perfectly aligned with the Gaussian kernel hypothesis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H7c8pE9tAS", "reviewer": "Reviewer_iBpf", "summary": "This paper investigates the theoretical properties of in-context learning when applied to data residing on structured manifolds with a low intrinsic dimension. The authors begin by presenting an expressiveness result, demonstrating that a Transformer can utilize $O(n)$ hidden tokens to approximate a kernel smoothing operation. Building on this constructive proof, the paper derives a generalization bound for a function class of a comparable size to the Transformer construction. This bound is intended to clarify the role of the manifold's intrinsic dimension $d$ in the generalization of ICL. Finally, the paper includes synthetic experiments to validate these theoretical findings.", "questions": "1. Could the authors provide a more explicit characterization of the generalization bound (Eq. 15)? Specifically, how do the constants $C_1$ and $C_2$ depend on the intrinsic dimension $d$, and how should the $D^3$ term be interpreted in the context of a manifold-aware analysis?\n\n2. What are the theoretical implications of the $l = O(n)$ hidden token requirement? Does the analysis hold for a more standard setting, such as $l = 0$? A clearer justification for the role of these hidden tokens and their necessity for the expressiveness result would be valuable.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper frames an interesting and relevant problem: the theoretical analysis of in-context learning on high-dimensional data that possesses a low-dimensional intrinsic manifold structure. This setup is well-motivated and timely given current data regimes.\n\n2. The theoretical claims regarding expressiveness and generalization are supported by corresponding synthetic experiments, which adds to the paper's completeness.\n\n3. The paper is generally clearly written and well-organized.", "weaknesses": "1. The paper's discussion of novelty could be strengthened. The connection between attention mechanisms and kernel smoothing has been explored in prior work (e.g., [1, 2]). It would be beneficial for the authors to more clearly articulate the novelty of their specific formulation in light of these existing results.\n\n2. The central claim regarding the generalization bound's (Eq. 15) dependence on the intrinsic dimension $d$ and ambient dimension $D$ requires further clarification.\n\n   - Firstly, the claim that the bound scales exponentially with $d$ is difficult to verify, as the constants $C_1$ and $C_2$ are also noted to be dependent on $d$. To make this claim more concrete, it would be helpful to explicitly characterize the dependency of $C_1$ and $C_2$ on $d$.\n\n   - Secondly, the bound's polynomial dependence on the ambient dimension ($D^3$) seems to obscure the intended message about the intrinsic dimension $d$. A key motivation for manifold-based analysis is often to obtain bounds that depend primarily on $d$ and are less sensitive to $D$. As written, the significance of the $D^3$ term on the bound's practical implications is unclear.\n\n3. The theoretical setup, which relies on $l = O(n)$ hidden tokens for the expressiveness result, appears to differ from the standard ICL paradigm, where new outputs are typically generated without a set of internal \"hidden tokens\". The authors could provide a clearer justification for this modeling choice and discuss its implications for the relevance of the derived bounds to standard Transformer-based ICL.\n\n[1] Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel. https://arxiv.org/abs/1908.11775.\n\n[2] Implicit Kernel Attention. https://arxiv.org/abs/2006.06147.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)