Transformers as Measure-Theoretic Associative Memory: A Statistical Perspective and Minimax Optimality
Authors: Ryotaro Kawata
Taiji Suzuki
Venue: ICLR 2026 Poster (2026)
Keywords: associative memory
learning theory
Primary area: learning theory

Abstract: Transformers excel through content-addressable retrieval and the ability to exploit contexts of, in principle, unbounded length.
We recast associative memory at the level of probability measures, treating a context as a distribution over tokens and viewing attention as an integral operator on measures. 
Concretely, for mixture contexts $\nu = I^{-1} \sum_{i=1}^I \mu^{(i)}$ and a query $x_{\mathrm{q}}(i^\*)$, the task decomposes into (i) recall of the relevant component $\mu^{(i^\*)}$ and (ii) prediction from $(\mu_{i^\*},x_{\mathrm{q}})$.
We study learned softmax attention (not a frozen kernel) trained by empirical risk minimization and show that a shallow measure-theoretic Transformer composed with an MLP learns the recall-and-predict map under a spectral assumption on the input densities. We further establish a matching minimax lower bound with the same rate exponent (up to multiplicative constants), proving sharpness of the convergence order. The framework offers a principled recipe for designing and analyzing Transformers that recall from arbitrarily long, distributional contexts with provable generalization guarantees.

Published as a conference paper at ICLR 2026
TRANSFORMERS AS - ASSOCIA- TIVE MEMORY: A STATISTICAL PERSPECTIVE AND MINIMAX OPTIMALITY
Ryotaro Kawata Taiji Suzuki-.2.8
'Department of Mathematical Informatics, University of Tokyo, Japan
Center for Advanced Intelligence Project, RIKEN, Japan
kawata ryo.traryot..225ee.eeo wtw.oe.ooo....tcc.....o wtw.iimmmt....utoyo....
ABSTRACT
Transformers excel through content-addreessable retrieval and the ability to ex- ploit contexts of, in principle. unbounded length. We recast associative memory at the level of probability measures, treating a context as a distribution over to- kens and viewing attention an integral operator on measures. Concretely, for mixture contexts / = r-1 E (م(²) and query (i"), the task decomposes into (i) recall the relevant component jult)) and (ii) prediction from (Mi-, #g). We study learned softmax attention (not a frozen kernel) trained by empirical risk minimization and show that a shallow measure-theoretic Transformer composed with an MLP learns the recall-and-pret and-predict map under a spectral assumption on the input densities. We further establish matching minimax lower bound with the same rate exponent (up to multiplicative constants), proving sharpness of the convergence order. The framework offers principled recipe for designing and analyzing Transformers that recall from arbitrarily long, distributional contexts with provable generalization guarantees.
INTRODUCTION
Transformers Vaswani et al. 2017) have achieved strong empirical performance across natural lan- guage [Brown et al. 2020). vision (Dosovitskiy et al.] 2022). and speech/audio (Dong et al.] 2018). Two properties motivate our study: (i) content-aaldresaabe retrieval of associated information
Desociative-memony view attention and (ii) the ability to leverage contexts variable, in prin- ciple unbounded, length.
In this work, we cast associative memory at the level of probability measures, treating context as distribution tokens, and develop rigorous statistical analysis of learned softmax-attention Transformers in this mncaure--therrche setting.
Associative memory provides unifying lens on how neural systems store and retrieve from partial cues: from early self-organizing and correlation memories to Hopfield attractors (Amaril 1972;
Kohonen 1972. Nakano 1972 Hopfield 1982 1984). Transformers recast associative memory or
recall via content-addressee
attention, formally equivalent to Hopfield-style associative updates
(Vaswani et al.) 2017, Ramsauer et al.] 202T). Recent studies quantify memory emergence and
capacity (Bietti et al. 2023] Cabannes et al. 2024 Mahdavi et al. 2024 Kim et al. 2023 Jiang
al. 2024 Nichani al. 2025).
As Transformers are engineered to ingest massive text corpora and long contexts, researchers have formalized this "context" as a probability measure over tokens, yielding measure-theoretic handle on variable-size inputs. Summarizing the text data one measure by the law of large numbers helps them to show results that are independent of the text length. A measure-theow thhooreti view of Trans- formers formalizes attention structure /Vuckovic et al. 2020 Sander et al.] 2022; Geshkovski et al., (2025] Burger et al. 2025). On the expressivity side, Transformers interpolate between input/output measures (Geshkovski
map distributions, enabling analysis of stability and emergent

---

Published as a conference paper at ICLR 2026
(4)
05
15
OF 71- 10
Mixture & Ei=1 Moins
recall
predict
Select index i" 1 1E + P0)
Evaluate (8")
(3')
F (' ;, wqg
Query Fgg (i*)
Figure Associative recall at the level of measures (informal): the query (i") selects the rel-
evant component measure j gfi") from the mixture E Moln followed by prediction from
(f")
(u0")
(6)) m.g) Note that each p ((9) is constructed by (1)) 8d and measure H0
(4)
(9) Rd
ct al. 2024) and even uniformly approximate continuous in-context mappings where the context is itself probability distribution (Furuya al. 2025)
Recent work has developed statistical analyses of Transformers with sefiiite-dimensione inputs. Yet the link to associative memory arguably a defining feature of attention remains under-specified Prior generalization results in distribution regression typically assume frozen (non-learnable) at- tention kernel (Liu & Zhou 2025), leaving unclear how learned attention retrieves the associated measure. Likewise, in a sequence-based in-context setting with dufinitediimesiione inputs (Kim) al. 2024), the analysis was carried out under linear attention, whose limited expressiveness makes it dilficult to realize the sharp, spiky weight distributions achievable by softmax attention (Han et al.,
2024
Fan al. 2025). These considerations motivate the central question:
Q. Can a learned coftmax-attention Transformer recall an refinite-dimensionnn (measure-valued) context and predict from it with provable generalizution guarantees?
"Associative memory" at the level of measures (informal). Consider a text corpus composed of I documents. We model each token as vector x = (v, E Rd4 x Rdd, where u encodes a document-level feature (e.g., topic) and encodes token-level content. For document i, the doeu- ment feature fixed vector ((() gd while the content part 2 is sampled from some distribution empirical token distribution of docu-
Po on Rdd, the limit of an infinitely long document, ment converges to a probability measure (a(0) on dd td2 namely the law x = (v(0) Z) with
(5) Z Po The context seen by the model is then the mixture
( wt POO
wi 2 O, Σ = 1,
representing whole dataset containing many documents. Given such mixture and query iig Rdi+d22 whose first di coordinates align with some document feature vy(*", the desired "associative memory" behavior is:
first, recall the component indexed by it from the mixture v, and
then predict scalar quantity that depends only the associated content distribution 140 possibly on Z.).
(f") (and
We denote by F* (v, + (V, E IR this ground-truth recall-and-prediis map: by con- struction, its output depends on v only through the single component ((") selected by the query (Fig. We study learned ceftmax-attention Transformers (with an integral/empirical measure view of attention) trained by empirical risk minimization (ERM) to implement this recall-and- predictt pipeline. On the statistical side, we work in very smooth regime: we endow the space of con- text measures with a reproducing kernel Hilbert space (RKHS) whose Mercer eigenvalues satisfy (as for Gaussian-type kernels (Schölkopf & Smolal 2002 This spectral decay encodes strong smoothness of the underlying densities and induces an effective dimension that will govern learning rates.
X; exp(-cj") for some
2

---

Published as a conference paper at ICLR 2026
Contributions. We now outline the principal contributions of this work:
Associative memory at the level of measures. We formalize general, mathematically rigorous framework for associative recall over measures: given a measure-valued context and a query, a recall operator selects the associated measure, and a predictor maps the recalled measure together with the query to an output. We formalize query-conditione selection from arbitrarily long contexts: the model recalls the associated probability measure capturing the relevant content and predicts from its statistics.
2. Generalization. We show that a shallow (depth-2) measure- theooreic Transformer composed with an MLP can learn the recall-and-predic mapping at the level of measures (Theorem [T. contrast to linear attentions (Kim al.] (024) or frozen kernels (Zhou al.) 2024), soft- max attention enables sparse and adaptive recall of the relevant measure. For empirical risk minimization over a bounded-paramene
hypothesis class- the number of recall candidates is not excessively large-we establish the sub-polynomial population-risk bound e n) n))a(a+t))), showing that the statistical difficulty is governed by the kemell's Mercer eigen-decay a.
3. Minimax Optimality.
We prove minimax lower bound with the same rate exponent (log n) /))//((+1) establishing the sharpness of the convergence order (Theorem 2). Thus, un- der our spectral and mixture-gron growth assumptions, the proposed measure- measure-theoretic Transformer is minimax-optimal in the order of the exponent, though multiplicative constants may differ.
The remainder of this paper is organized as follows. Section reviews related work. Section introduces the problem setting and the student model. Section presents our main thcoretical results. Section concludes with discussion. Technical details and proofs are deferred to the appendices.
2 RELATED WORK
Associative Memory and Recall.
Associative memory concepts originated in early neuroscience
models (Hopfilld) 1982 Amari 1972, Kohonen 1972 Nakano 1972. Hopfield 1982, 1984). fol-
lowed by Graves et al. [2014) Weston et al. a (2014); Ramsauer al. (2021): Millidge et al. (2022).
The Transformer architecture closely related to associative memory by employing self-attention
as a content-addressablle mechanism (Vaswani et al. 2017). Recent work has increasingly focused on how associative memory emerges and scales within Transformer architectures (Bietti al.
2023
Cabannes et al. 2024 Mahdavi et al., 2024 Kim et al. 2003) Jiang et al. 2024 Nichani et al.
2025
Transformers for sightful analysis of Transformer architectures. Vuckovic et al. (2020); [Sander et al. (2022) formal- ized self-attention as map on probability measures. Its Lipschitzness is explored in Castin et al. (2024). Building on that framework, Geshkovski et al. (2023) 2025); Burger et al. (2025) modeled self-attention
Inputs. A mecsure--heoreee perspective has enabled in-
interacting particle system. Geshkovski al. (2024) proved universality result showing that Transformers can interpolate arbitrary input-output measure pairs, later strengthened by Furuya et al. (2025) uniform approximation of continuous mappings over distributions and queries. On generalization, Liu & Zhou (2025) studied distribution regression, though restricted to frozen attention kernel. In the context sequential, diinite-dimensinaal inputs, Kim et al. (2024) studied in-context learning with linear attention, which essentially reduces to averaging behaviors; hence their analysis assumed relaxed sparsity and orthonormality of the recall candidates, reflecting the difficulty of achieving spiky one-hot recall in contrast to softmax attention (Han et al. 2024 Fan
ct al. 2025).
MLP Approximations of Functional Mappings. In statistical Caamingg,MMaskar Mhaskar & Hahm 1997) laid the groundwork by showing that multi-layer perceptrons (MLPs) can approximate continuous nonlinear functionals over function spaces in a optimal rate that was generalized by (Stinchcombe (199)). Rossi et al. (2005) introduced a novel functional MLPs which is applicable to functional data, followed by variants (aoo et al. 2021 Song et al.) 2023 Zhou et al. 2024). On the opti- mization front, [Suzuki (2020): Nishikawa et al. (2022) established global optimization assurances for two-layer networks operating in infiniteddimensional regime.
3

---

Published as a conference paper at ICLR 2026
3 PROBLEM SETTING
Notations. For integers N1 S N2 and v E IR, we write UN::N, = (UN...... UNa) For a matrix A, ||Allo denotes the number of nonzero entries and ||A|]> maxi, Ai,l- We write À for the Lebesgue measure RV,, and fej for the pushforward of by f. For measurable space X, P(Z') denotes the set of probability measures and (M the set of nonnegative measures. We use (2, IP) for probability space, [| and |/ for the usual TP and essential sup norms, and Px for the law of a random variable X. Expectations are written El.] or Ex [:] with the law of X.
Our Regression Problem. We now formalize the informal recall-and-predice scenario from the introduction.
Definition Let Xo C R be a bounded token-content space and let X Rdd+dd denote the token space with the decomposition æ = (v, 2), where E Rd encodes a document-level feature and = Xo encodes token-level content.
1. Mixture contexts and queries. Each document i [4] is associated with document feature ( E g and content distribution ( E M+ Informally, ( represents the distribu- tion of token contents (e.g.. words embeddings) appearing in document i. The corresponding token distribution on X is the product measure
8gen @ Ho = (Emb,,)))90"
Pol
where Emb (2) (v(9, and fa denotes the pushforward of f by f. so that pg00 is the joint distribution of the document feature w(() and the token content in document i. A context is mixture of these component measures,
1 E P(X),
Σ 00 660
which represents the token distribution of whole dataset containing 7 documents. Concretely, is the law obtained by first sampling document i [T] at random and then token (v((), from that document. Given such mixture, query Pq E X' is constructed so as indicate distinguished index i [4]. For concreteness, we take
T2((")
= Emb,, (0dz) E Rd1+da,
Tq = Od,
that is, the document feature (f") padded with zeros in the last d2 coordinates !
2. Ground-truth recall-and-predite map. The learning task is to predict real- response
y F (v, + E, {~N(00,
from the pair (u, x.)) The key structural assumption is that F* depends on the context v only through the single component associated with the index i* selected by the query. Equivalently, there exists a (hidden) functional F* such that
F*(uzqg) = F (n0 (i*) (aa))
-=
v
so that the regression map (v, + (", 2g)
decomposes into the two conceptual stages
x.)
recall
(it)
prodict
F ("u (it) .rg).
For instance, F* 2rg) could be sentiment score of document i*, or the probability that docu- ment mentions an entity specified by the query.
In particular, F* must first associate the query with the relevant component of the mixture context and then predict scalar from the recalled component (e.g., in-context learning (Brown et al, 2020 This formalizes an "associative memory" task at the level of probability measures.
More general queries, e.g. with nonzero content part, can be treated well; we fix the zero padding here for notational simplicity.
4

---

Published as a conference paper at ICLR 2026
Statistical Estimation Problem. Motivated by the recall-and-prediin regression task described above, We now formulate the associated statistical estimation problem. We observe n i..d. samples
S = (Ve, Zqe x 30)
drawn from the joint distribution of (g v). Let F denote hypothesis class of measurable func- tions F: PXX) Rdi+e IR. Given the training data, we define the empirical risk minimizer
F := arg min En F(,,z)))
where E,, denotes the empirical expectation over the samples. Given a hypothesis (regressor) F, our goal is to learn F* so as to minimize the squared L loss
R(F",
E.s. [Is.[[]F[O [1,
F(u, (l)
RKHS viewpoint on content measures. Before stating the assumptions, we briefly recall how the kernel K induces a function space for modeling token distributions. Given a positive definite kernel K Xy No - R on the bounded token-content domain X, R there exists a unique reproducing kernel Hilbert space (RKHS) (e.g., (Schölkopf & Smola 2002 Ho of functions f No + such that
K(,x)= E Ho and f(z) (f, (f,))) for all x E Xo.
Intuitively, Ho is the class of "smooth" functions compatible with K. In the Mercer basis
K(Ixx') = E5² (T)(()),,
every / E Ho can be written as f(x) = E5214eey6 with finite RKHS norm 11/ Σj² 03/Ag. Large coefficients by in high-frequency directions (small Xÿ) are penalized heavily, so Hy favours functions whose energy is concentrated low-order eigen-components, In our setting we represent each content measure (b by its density P on Ag. and we require these densities to 1u lie in fixed ball of Ho. The rapid eigenvalue decay Aÿ X exp(-cja) corresponds very smooth (Gaussian Kernel-type (Schölkopf Smola 2002)) regime in which the effective dimension of this function class is small; this effective dimension will drive our statistical rates.
3.1 ASSUMPTIONS AND TECHNICAL SETTINGS
We now state the high-level assumptions used in our upper- and lower-bound analyses. Full tech- nical versions are deferred to Appendix [A.]] Throughout this subsection, contexts and queries are generated as described in the beginning of Section
Assumption (Smooth kernel and regular content measures). Let Xo 12da be bounded token- content domain and let K : No x No + I. be a positive definite kernel with Mercer expan- sion (Schölkopf & Smola 2002)
K(I,x') = (xye(())e,((")
We assume (i) The eigenvalues decay exponentially, i.e.Ay x exp(-cj") for some c, a > 0 (a Gaussian-type smoothness regime), (ii) Each content distribution nb is finite measure on X whose density lies in fixed ball of the RKHS Ho induced by K. Informally, the token distributions are very smooth and their effective dimension small, since most of the mass lies low-order cigen-components. We focus this exponentially decaying regime first step, keep the analysis transparent.
Example (Heat-kernel RKHS Grigor yan. 2006)). Consider Xo 00 and the Laplace op- d? with Dirichlet boundary conditions. Its eigenfunctions and eigenvalues are ex(x) sinkkzz) and Č* (kT)} for l 2 1. The heat kernel, the fundamental solution of the heat equation describing how heat placed at y at time 0 spreads x by time
erator A
dzz
K2(x,v) = Ei Sut
S-t (x()))(())= = Eb c 2t (xtee (x()cx())
so the Mercer eigenvalues satisfy D = 22 exp(-ck' and Assumption holds with a = 2. More general constructions compact manifolds are recalled in Appendix A.
5

---

Published as a conference paper at ICLR 2026
Assumption (Separated context vectors). The context vectors v(0) E Shh-1 used to construct the mixture ( are well separated: (v(9, )( 0, for all si< I, and we assume / I d1. This guarantees that different documents are sufficienlly distinguishable for the recall step
Assumption 3 (Lipsehitz ground-truth functional). There exists a metric dprod on the space of pairs (no, 2). induced by the RKHS structure above, such that the hidden functional F (100) x Rdi+d2 R is L-Lipschitz:
F (Ho, F" (16, S I. dppod ((Ho, x²), (16. x'))
for all admissible inputs (No, and (μg. x'). In the proofs, dprod will be the sum of an RKHS- induced distance between densities and the Euclidean distance between queries; see Appendix A.1 for its precise form.
Assumption 4. Each content distribution Po (8)
a probability measure on Xg-
Setting 1 (Probability setting for upper bound (Setting 1)). Contexts and queries are generated as in Section 3] Assumptions 2 and hold. In other words, we consider smooth (Gaussian-
type) content probability distributions in an RKHS ball, well-separated context vectors, and an L- Lipschitz ground-truth functional with respect to RKHS-induced metric.
Structured model for lower bound. For the minimax lower bound, work with simplified random model for the content densities, following Lanthaler (2024): the density of no is generated by random coefficients in the Mercer expansion of K.
Assumption 5 (Informal structural model for densities), Let (Aý, eq) be the spectrum of K in dx (x) = Σ5²1, 20()) (1))(1), where the coefficients Zj are independent, bounded random variables with unit variance. The full set of structural conditions is given Assumption & Appendix A.
Assumption We assume that duo
Setting 2 (Structured setting for lower bound (Setting 2)). Contexts and queries are generated as in Section 3 Assumption [ and 3 hold, and the densities of the content measures follow the structural model in Assumption In this setting we derive minimax lower bounds under random Mercer coefficients.
3.2 STUDENT MODEL: MEASURE- THEORETIC TRANSFORMERS
We define our student model as class of measure-theoretic Transformer architectures following Furuya al. (205)).
Measure-Theoretie Attention. Given a set of tokens X = (xx) RR Xwe and a query x E Edaioo that encodes information about some of the tokens, single unmasked attention head with parameters ((h) (Kh Qh, Vhh in an "in-context" form (Furuya et al. 2025 computes
SAllngos (X,x) x) = E, Softmax ((Qaaaxx('x,,)))) (("*x,"*X)) Vhaj,
where Softmax((21,...... zN)) = (xxp(2)) 2,,, exp(2,)) A standard multi-head attention with H heads is then MSAting (X) Σ W*SAutngoo (X, with W E Rd xdasts In the unmasked case, attention permutation-equivarian in the token indices. This allows us to represent the input set by its empirical measure, in particular, in the form of mixture measure
Vx + Σt. 80000 (,50) P(Ruus) in the limit as + 00.
where v( E Rd (group-shared, possibly indicated by the query), (1) E Id (token- specific) for i E [1 1 [1 wi). E; w; = w and rewrite attention in a measure-theoretic form, where integral replaces the discrete sum in the limit.
A similar separationforthogonalii structure is used in theoretical analyses of factual extraction in trans- formers, e.g., Ghosal al. 2024)

---

Published as a conference paper at ICLR 2026
Definition 2 peeasure-theorete attention layer (Furuya al. 2025 ). Let datta be the embedding dimension for the attention. The weeasure-theoeete attention layer Attng P(Rduus)) x IR dauu Rdas is defined by
Att = Ax +
Σ h=1
wh Softmax((Q* (, K"))) Vhy dr(y),
where Softmax( (Qr, Ky²) == exp ((Qz, K exp ((Qz, K2)) dz(z). Here A E Ra Xdatia applies a learned linear transformation to the skip connection.
When y is empirical mixture measure px, this reduces to the standard discrete attention layer (we do not pursue the discrete case this work). We expect that the query æ indicates tokens the i"-th component in vx based on the group-shared vector u(²*) and the model can recall them. We constrain these layers via the following
hypothesis class.
Definition (Attention hypothesis class), For constants Ba, By Sa, Saa F 0, define the class of H-head seasure-theoretec attention layers
A(dattn H, Ba, By Sa. Sy,) = {Attng max {|| |l, 110" | | 1loc S Bu, max (1IW"l1o. 11o |Ko || |lo) - Sa. || S By ||Alo S S., ||Attnol S F). where || = max,, MMal [| is the number of non-zero entries, for a matrix M. We assume Wh, Q2", K², y are square matrices for simplicity. We write A(datnn H, Bu Sa) when By B, and Sy Sa-
MLP Layer addition to attention, Transformer block also includes feedforward component. Since this part does not depend on the underlying measure μ4, we model it simply as standard multilayer perceptron (MLP), defined below.
Definition 4 (MLP hypothesis class). Let é E N be the depth and p (Po. Pr..... Pp+1) NT+ be the layer widths. A neural network with architecture (f,p) is any function of the form
R R x f(x) Weov, We-10v Wl0v, Wax,
where W; E PP is the weight matrix of layer and v; E IR is shift (bias) vector applied through the activation oy, (z) oz vz) with ReLU activation function R R. The hypothesis class of MLPs with architecture (e, p) is denoted
F(e, (. = {f of the form above max, 1e,, s 1,E, [W + luylo S 8, |1/ S F}.
Transformer Hypothesis Class via Composition. To formally describe a Transformer within our measure- measure-theoretic framework, we introduce the notion of composition for measure-theorede mappings, following Furuya et al. (2025). This will allow us to view a multi-layer Transformer as successive composition of attention and feedforward layers, in exact analogy with the standard architecture.
The key idea is that such mapping I' acts simultancously on token and its generating distribution μ. Given z ~ μ4, applying produces a transformed token I'(,, 2) and induces new distribution on transformed tokens [' 2), namely (I 1)), Thus, composing two mappings means successively applying these joint transformations at both the sample and distribution levels.
Definition 5 (Composition of measure-theoren mappings). Let F1 P(Ref") æ Rd
and l2 ((T.d
+ d with d(2) = dfd Their composition is defined as x a
(T2 T1)(( = -'r(p, (i,,,)) where
#1 == (1, D)x
Remark 1. If we interpret / as a limit of empirical measure vx lim wo composition F2 o [₁ acts by updating both the individual tokens and their empirical distribution. In this case, the construction is consistent with the standard layerwise composition in Transformer: each layer maps the sequence tokens (s),..., F.r) to a new sequence, while the corresponding empirical distribution is updated accordingly.
1 F- 8zy- then the

---

Published as a conference paper at ICLR 2026
Building the notion of measure-theoree composition introduced above, describe a Transformer as the successive composition of attention and feedforward layers. The following definition specifies the corresponding hypothesis class.
formally
Definition
class). For parameters (dy, Hy. Bu,s Bag. Sog. a.j. Pj. 8)) 85)5=11 define TF as the set of mappings of the form
(Transformer
hypothesis
Attua, o MLP o ..... Attng, o MLPS
where Attuo, E A(dj, Hj, Baji B' Ba S.. independent of (i.e. MLPs, (H, = MLP3 (z)), and all intermediate outputs are assumed uniformly bounded.
San) and MLPS E sz. MLP layers are
MAIN RESULTS
4.1 ESTIMATION ERROR OF MEASURE-THEORTE TRANSFORMERS
We begin with the generalization performance of measure-theoretie Transformers in the recall-and- predict task. Throughout this subsection we work under the Probability Setting (Setting D. where each content measure Mo has smooth RKHS density on Ng and the number of mixture components not too large.
Theorem 1 (Sub-pole huub-oolyooiia convergence; informal version of Theorem Let (V, =
Fer (pO) values of the underlying kernel satisfy >; x exp(-ej cj"* [ for some a 0. Suppose that either (i) the number of mixture components satisfies I < d1 S (log (oggn) n)2/(+11), Ta and I di = no(1), Then, for suitable choice of architecture parameters (defining depth-2 teasure-theoretic Transformer class TF n.) any empirical risk minimizer Fr over TF, satisfies
(5*) ,.a) be Lipschitz recall-and-predict map as in Section and assume that the eigen-
(ii) F* does not depend on
R(F Fw) S exp( - ((llon))/latt))
under Setting
Statistically unifying associative recall and infinite-token regimes. Prior work studied (i) asso- ciative recall in Transformers (Ramsauer et al. [021] and (ii) infinite-token infiittedimenssioaal inputs modeled as measures (Vuckovic et al.] 2020). Theorem 1 integrate these threads by giv- ing statistical theory of measure-level associative recall: measure-theoretic Transformer with learned softmax attention can recall-nd-preeice at the level of preassrres-spareel isolating the query-relevant component and basing the prediction on the recalled measure, in contrast the universality or approximation results (Geshkovski et al. 2024 Furuya et al. 2025).
Informal interpretation: effective dimension. The spectral decay X3 x exp( -ci") means that only the first few Mercer modes carry substantial signal. After the recall step, our Transformer Mercer coefficients
effectively aggregates the first
by [eeddp (8")
j j=
so
measure compressed into the D-dimensional vector b (b) (b1,..., bp). Learning a Lipschitz function of b from n samples behaves like a D-dimensional problem (c.f., Schmidt-Hieber (2020)), with estimation error roughly
Error of D-dim. problem ~ n -(1/D) exp( - (((om))()))
while truncating the Mercer expansion after D modes incurs bias of order exp(-cD*)) Balancing these terms yields effective dimension D (m) (log n) 1(a-1) and the sub-polynomial rate
R(F*, exp( @(log ([(lloggg//// n(/(()))))
stated in Theorem I In this sense, the estimator behaves as if it were fitting only (n) degrees of freedom, despite each component being an dimette-dimesiional measure. As a minimal sanity check, Appendix presents synthetic experiment whose convergence rate is consistent.
8

---

Published as a conference paper at ICLR 2026
E A h higue (22)
b (2gg
(1) u(6) = = 00)) 8/4
recalled
hy (v(2))
hizu(0 (1) 2(1)
h (
2
y
hig 14 (3) v(3)
h ()(3)))
(8) Figure 2: A geometric illustration of how query 2ig and components p are mapped by the (sim- plified) first layer hy((v, 2)) = (v, ez()) IR tds, where ej is the jth Mercer eigenfunction. The product of the first d, indices of hy (Ing) and hy(y) higu tells whether y (v, 2) is sampled from 1 066)) or not.
(0)
Mechanism: softmax attention as measure-valued associative memory. Given a mixture con- (3)
text = - M30) and query Iq (o(*), 0), our depth-2 Transformer works follows. initial MI.P embeds each token = (o 2) into a feature vector h(y) that contains the first D Mercer features (ey(=)) Softmax attention then computes scores (Qh(zqq) Kh(y)) and is
parameterized so that these scores are large mainly when the document tag ((()) matches p((") and
small otherwise (Fig. 2)
Softmax attention then computes scores (Qh(rq), Kh(y)) so that, after normalization, the weights concentrate samples from μ (i*) p Writing Wn, (y) for the resulting attention weight token y, the value path computes, for each j.
b,
Wz,
feg(=)duo (z).
j= i= D,
yielding a D-dimensional descriptor (bI...., bp) of the recalled component measure. final .zg). In this way, softmax attention filters the mixture down to the relevant component and integrates its Mercer features, so that predicting from an infinite-dimensionn dimensional measure reduces to learning function of D summary statistics. This one-hot, query-dependent filtering is beyond the limitations of frozen kernels (Zhou et 2004 and linear attentions (Kim al. 2024).
MLP maps (b, ux)) to the scalar prediction ("166 (3")
4.2 MINIMAX OPTIMALITY (THE LOWER BOUND).
Next, we demonstrate the lower bound in Structured Setting (Setting 2}.
We show that the exponent of the obtained upper bound is essentially tight, albeit in Setting whose technical assumptions are different from Setting
Theorem (Minimax Lower Bound). In Setting 2 any T,2
F satisfies
suppter. R(F, exp (-O((ln))+T)
where F* F* (v, FO'
(1((6)) ((a)) is the decay rate of the eigenvalues of the kernel Ho-

---

Published as a conference paper at ICLR 2026
Optimality of Transformers. Taken together with Theorem 1 our information iitommation-thooetiic lower bound Theorem 2 shows that the statistical rate of empirical risk minimization over transformers
achieves the minimax rate (Inn)at up to multiplicative constants in the exponent. Equivalently, no method can improve the n de-eenddence beyond the stated exponent (up to universal constants), so the leamed-softmax Transformer attains the best-possible sample complexity for this problem class. The optimality continues hold for fixed slowly growing number of mixture components I, confirming that the learned softmax attention provides the right inductive bias for measure-level recall. This minimax optimality of softmax Transformers is consistent with statistical results for simple infinie-dimensiona. regression (Takakura & Suzuki] 2023) and with finiteddmmensionll in- context learning scenarios that require retrieval (Nishikawa al. (025).
Technical Citribbution-Minmmal Lower Bound. We first reduce associative recall to infinite- dimensional Lipschitz regression by observing that estimating from the mixed input no eas-
ier than from the pure measure Mo (2") A truncation of Mercer coefficients plus anisotropic rescal- mog-modifying prior rescaling arguments (Lanthaler, 2024) to more general geometry with ex- ponential decay-maker makes the induced geometry essentially isotropic, letting us embed the classical d-dimensional Lipschitz class and import standard packing bounds. Combining these bounds with the classical result (Yang & Barron
1999) yields rate matching our upper bound.
CONCLUSION AND DISCUSSION
We introduced the concept of measure- theoretic associative memory (recall) and established that learned softmax attention can realize sharp recall even in dimnitedimenssonal, measure-valued set- tings someeting beyond the reach of frozen kernels and difficult for linear attention. Our analy- sis further shows that the statistical efficiency of Transformers extends beyond fiite-dimennional contexts, offering principled explanation of their recall ability. While the present results focus exponentially decaying spectra under smooth eigenfunctions, they open the door to broader regimes: extending the rates to polynomial decay and incorporating eigenfunction smoothness into the anal- ysis represent natural next steps toward more complete theory.
LLM USAGE STATEMENT
Large language models are used for two purposes: to proofread and polish English writing, to help us find related works. We did not use any LLM assistant for designing the problem settings and constructing the proofs.
5.0.1 ACKNOWLEDGMENTS
RK and TS were partially supported by JSPS KAKENHI (24K02905) and JST CREST (JP- MJCR2115). This research is supported by the National Research Foundation, Singapore, Info- comm Media Development Authority under its Trust Tech Funding Initiative, and the Ministry of Digital Development and Information under the AI Visiting Professorship Programme (award num- ber AIVP-2024-004). Any opinions, findings and conclusions recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Founda- tion, Singapore, Infocomm Media Development Authority, and the Ministry of Digital Development and Information. RK was supported by the FY 2024 Self-directed Research Activity Grant of the University of Tokyo's International Graduate Program "Innovation for Intelligent World" (IIW).
REFERENCES
Shun-ichi Amari. Learning patterns and pattern sequences by self-organizing nets of threshold elements. IEEE Transactions on Computers, C-21(11)1199--1266 1972.
Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Hervé Jégou, and Léon Bottou. Birth of a transformer: A memory viewpoint. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
10

---

Published as a conference paper at ICLR 2026
Emmanuel Boissard. Simple bounds for the convergence of empirical and occupation measures in I-wasserstein distance. Electronic Journal of Probability, 16:2296-233 2333, 2011.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Martin Burger, Samira Kabri, Yury Korolev, Tim Roith, and Lukas Weigand. Analysis of mean- mean-field models arising from self-attention dynamics in transformer architectures with layer normalization. Philosophical Transactions A, 383(2298):2024223 2025.
Vivien Cabannes, Elvis Dohmatob, and Alberto Bietti. Scaling laws for associative memories. In International Conference on Learning Representations (ICLR), 2024.
Valérie Castin, Pierre Ablin, and Gabriel Peyré. How smooth is attention? International Confer- ence on Machine Learning, pp. 5817-5840. PMLR, 2024.
Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5-30, 2006.
Linhao Dong, Shuang Xu, and Bo Xu. Speech-transformer. a no-recurrence Sguuence-o--equeee model for speech recognition. In 2018 IEEE international conference on acoustics, speech and signal processing (ICASSP), pp. 5884-5888. IEEE, 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x 16 words: Transformers for image recognition at scale. International Conference on Learning Representations, 2021.
Weinan E and Qingcan Wang. Exponential convergence of the deep neural network approximation for analytic functions. Science China Mathematics, 61(10):1333-7444 2018. ISSN 1869-1862,
Qihang Fan, Huaibo Huang, Yuang Ai, and Ran He. Rectifying magnitude neglect in linear attention, 2025.
Takashi Furuya, Maarten V. de Hoop, and Gabriel Peyré. leamnrrs In The Thirteenth International Conference on Learning Representations, 2025.
Transformers are universal in-context
Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. The emergence of clus- ters in self-attention dynamics. Advances in Neural Information Processing Systems, 36:57026- 57037, 2023.
Borjan Geshkovski, Philippe Rigollet, and Domènec Balet.. Mcasure-to-measurre interpolation using transformers. arXiv preprint arXiv:2411.04551 2024.
Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. mathematical per- spective on transformers. Bulletin of the American Mathematical Society, 62(3):427-479, 2025.
Gaurav Ghosal, Tatsunori Hashimoto, and Aditi Raghunathan. Understanding finetuning for factual knowledge extraction, 2024.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv:1410.5401, 2014.
arXiv preprint
Alexander Grigor'yan yan. Heat kernels on weighted manifolds and applications. Cont. Math, 398 (2006))93-191, 2006.
Dongchen Han, Yifan Pu, Zhuofan Xia, Yizeng Han, Xuran Pan, Xiu Li, Jiwen Lu, Shiji Song, and Gao Huang. Bridging the divide: Reconsidering softmax and linear attention. Advances in Neural Information Processing Systems, 37:79221-79245. 2024.
John Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences, 79(8):2554-25 2558, 1982.

---

Published as a conference paper at ICLR 2026
John J. Hopfield. Neurons with graded response have collective computational properties like those of tto-state neurons. Proceedings of the National Academy of Sciences, 81(10):3088-33 -00908888 1984.
Y. Jiang, G. Rajendran, P. Ravikumar, and B. Aragam. Do Ilms dream of elephants (when told not to)? latent concept association and associative memory in transformers. arXiv preprint 24X.0:2406.18400, 2024.
Kim, M. Kim, and B. Mozafari. Provable memorization capacity of transformers. In International Conference on Learning Representations (ICLR), 2023.
Juno Kim, Tai Nakamaki, and Taiji Suzuki. Transformers are minimax optimal nonparametric in- context learners. In A. Globerson, L.. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 106667- 106713. Curran Associates, Inc., 2024.
Teuvo Kohonen. Correlation matrix memories. IEEE Transactions on Computers, C-21(4)3333-66, 1972.
Samuel Lanthaler. Operator learning of lipschitz operators: An information-theoortiee perspective, 2024.
Peilin Liu and Ding Zhou. Generalization analysis of transformers in distribution regression. Neural Computation, 37(2)260-293, 01 2025. ISSN 0899-7667.
S. Mahdavi, R. Liao, and C. Thrampoulidis. Memorization capacity of multihead attention in trans- formers, In International Conference on Learning Representations (ICLR), 2024.
H. N. Mhaskar and Nahmwoo Hahm. Neural networks for functional approximation and system identification. Neural Computation, 91):143-159, 01 1997. ISSN 0899-7667.
Beren Millidge, Tommaso Salvatori, Yuhang Song, Thomas Lukasiewicz, and Rafal Bogacz. Uni- versal hopfield networks: A general framework for single-shot associative memory models. In International Conference on Machine Learning, pp. 15561-15583, PMLR, 2022.
Boaz Nadler, Stephane Lafon, loannis Kevrekidis, and Ronald Coifman. Diffusion maps, spectral clustering and eigenfunctions of ookker-plancke operators. In Y. Weiss, B. Schölkopf, and J. Platt (eds.), Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005.
Kenji Nakano. Associatron model of associative memory. IEEE Transactions on Systems, Man, and Cybermetics, SMCC2(():380-388) 1972.
Eshaan Nichani, Jason D. Lee, and Alberto Bietti. Understanding factual recall in transformers via associative memories. In International Conference on Learning Representations (ICLR), 2025. Spotlight presentation, preprint urXiv:2412.06538.
Naoki Nishikawa, Taiji Suzuki, Atsushi Nitanda, and Denny Wu. Two-layer neural network on infinite dimensional data: global optimization guarantee in the mean-field regime. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 32612-32623, Curran Associates, Inc., 2022.
Naoki Nishikawa, Yujin Song, Kazusato Oko, Denny Wu, and Taiji Suzuki. Nonlinear transform- can perform inference-time feature learning. In Forty-second International Conference Machine Learning, 2025.
Hubert Ramsauer, Bernhard Schäfl, Anna Hopkins, Michael Widrich, Thomas Adler, Lukas Gruber, Markus Holzleitner, Zoltan Pavlović, Geir Kjetil Sandve, Vidar Greiff, Johannes Brandstetter, and Sepp Hochreiter. Hopfield networks is all you need. In International Conference Learning Representations (ICLR), 2021.
Fabrice Rossi, Nicolas Delannay, Brieuc Conan-Gued and Michel Verleysen. Representation of functional data in neural networks. Neurocomputing, 180, 2005. ISSN 0925-2312. Trends in Neurocomputing: 22th European Symposium Artificial Neural Networks 2004.
12

---

Published as a conference paper at ICLR 2026
Michael E. Sander, Pierre Ablin, Mathieu Blondel, and Gabriel Peyré. Sinkformers: Transformers with doubly stochastic attention. In Gustau Camps- Valps-Valss, Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference Artificial Intelligence and Statisties, volume 151 of Proceedings of Machine Learning Research, pp. 3515-3530. PMLR, 28-30 Mar 2022.
Johannes Sehmidt-Hieber. Nonparametric regression using deep neural networks with ReLU acti- vation function. The Annals of Statistics, 48(4):1875-1897 2020.
Bernhard Schölkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Linhao Song, Jun Fan, Di-Rong Chen, and Ding-Xuan Zhou. Correction: Approximation of non- linear functionals using deep relu networks. Journal of Fourier Analysis and Applications, 29(5): 57, 2023. ISSN 1531-5851.
M.B. Stinchcombe. Neural network approximation of continuous functionals and continuous func- tions on compactifications. Neural Networks, 12(3):467-477, 1999. ISSN 0893-6080.
Taiji Suzuki. Generalization bound of globally optimal non-convex neural network training: Trans- portation map estimation by infinite dimensional langevin dynamics. In H. Larochelle, M. Ran- zato, Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 19224-1999 19237. Curran Associates, Inc., 2020.
Shokichi Takakura and Taiji Suzuki. Approximation and estimation ability of transformers for geguence-to-sqquenee functions with infinite dimensional input. In International Conference on Machine Learming, pp.
PMLR, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems (NeurIPS), 2017.
James Vuckovic, Aristide Baratin, and Remi Tachet des Combes. A mathematical theory of atten- tion. arXiv preprint arXiv:2007.02876 2020.
Jason Weston, Sumit Chopra, and Antoine Bordes, Memory networks. In Advances in Neural Information Processing Systems (NeurIPS), 2014.
Weichun Xia and Lei Shi. Spectral algorithms on manifolds through diffusion. arXiv preprint, 2024.
Yuhong Yang and Andrew Barron. Information-theorrticc determination of minimax rates of conver- gence. The Annals of Statistics, 27(5):1564-1599) 1999. ISSN 00905364, 21688966.
Junwen Yao, Jonas Mueller, and Jane-Ling Wang. Deep learning for functional data analysis with adaptive basis layers. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Inter- national Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 11898-11908 PMIR, 18-24 Jul 2021.
Tian-Yi Yi Zhou, Namjoon Suh, Guang Cheng, and Xiaoming Huo. Approximation of rkhs functionals by neural networks. CoRR, abs/2403. 12187, 2024.
A PRELIMINARIES AND NOTATIONAL REMARKS
We begin by fixing notation and conventions used throughout the paper. This includes basic vector and matrix operations, cecasure-theoretic notation, and standard identifications between measures and their densities.
For integers N₁ < N₂ and a vector e E R we define uN :N₂ == (UN,...., UN2) T For a matrix A, we define ||ol|o as the number of nonzero entries and || == maxi, AAyl-- We denote A as the Lebesgue measure on N for integer N. feu(-) (.)= denotes pushfor- ward a measure μ by a mapping f. For a measurable space X, we write P(X) := { y is probability measure X). (+) = {u ja is nonnegative measure on X'
13

---

Published as a conference paper at ICLR 2026
Unless otherwise specified, write (Ω, FPP)) for underlying probability space. For measurable function f .2 + R and S < oc, the (PP))) norm is defined as |f ( = (Jn Ifl dP) 1/P
while the L _ (P) norm given by ( = esssupwed [f()]] When the underlying measure clear from context, we simply write || and |l
For random variable X : - X, denote its distribution (the pushforward of IP under X) by Px(+) = P(X E .). Expectations with respect to IP are denoted by E[. and if is a random variable with law Px, also write Ex [x[](X) for fx) dx)(xx.
fxx
Remark (Identification measures and densities). Let À be a reference measure on X (e.g., the Lebesgue measure). Given f H and constant R, define probability measure by
du Y (x) (x) f(x) c
where e is chosen so that /+C 2 0 A-a.e and μ(X) fx (f(x) + dr 1. In this case, we write E H by identifying with its density f + When sampling E B(Ho, lI |l ) please note that we choose with no randomness and let c 0 for simplicity, throughout this paper. Definition (Mercer expansion). Let Ho be reproducing kernel Hilbert space (RKHS) on do- main X' with reproducing kernel K X x X R. By Mercer's theorem, K admits the decompo- sition
K K(x,x)) = Σ (1))
where (Ay)E21 are the (non-negative, non-increasing) Mercer eigenvalues and (e,)y21 are the cor- responding L2-orthonormal eigenfunctions. For any μ Ho. representation in the eigenbasis is
Pp Σ byeg with coefficients bj = (pps L2)
Definition 8 (Generalized RKHS norm). Let Hu be an RKHS with orthonormal basis {eshi21 in 7,2 and associated eigenvalues (1jb2ı- For a measure f whose associated function Ho admits the expansion
dp (x) = (x()) constant. d
Pμ Σ byes
where
321
we define, for a R, the generalized norm
1 = 1lp ligg = E1
121
Special cases include the case = || 1l coincides with the T norm; a 1: || llag the standard RKHS norm; a = -1: 1: || |lx, is the MMD norm.
Definition 9 (Metric balls). Let (X, d) be a metric space. For a X and > 0, the (closed) metric ball radius e centered at x is
((x, Ey x ( {e).
When = 1, we simply write B(x, d) and refer to it as the unit ball.
Definition 10 (Lipschitz functions). Let (X,d) be a metric space and A X be fixed domain. A function f A + IR is said to be L-Lipschitz on A with respect to d if
(xxx) f(x') < L d(x,x') Ve, a E A. The set of all such functions is denoted by Lip (A, d).
PRELIMINARIES ON METRIC ENTROPY
For the subsequent proofs, we will make repeated use of standard notions from metric entropy. In particular, coverings, packings, and their associated numbers provide convenient way quantify the complexity of hypothesis classes. We therefore collect the relevant definitions and basic lemmas here.
14

---

Published as a conference paper at ICLR 2026
Definition 11 (e-covering). Let (X be metric space, A C X, and 0. A finite set (21....,, ,....,,yyy... C X called an e-covering A (with respect to d)
N
U d(),,
where B(r; d, e) denotes the closed metric ball of radius centered at z;,
Definition 12 (e-packing). Let (X,d) be a metric space, A C X, and > 0. A finite set [f1....,,EN] A is called an e-packing of A (with respect to d) if
d(z;, x3)) > e for all i +
Equivalently, the metric balls B e/e2) are pairwise disjoint. Definition 13 (Covering number). The covering number of A scale with respect d is
(A, e)a == min N Be-covering of A of size N }.
Definition 14 (Packing number). The packing number of A at scale with respect to d is
M(A, t)a == max M Je-packing of A of size M }. Lemma 1 (Covering packing equivalence). For any metric space (X, d), any A X, and 0, one has
M(A,2c)a ((,, S M(A,
In particular, the covering number and the packing number are equivalent to constant factors in the scale parameter.
Lemma 2 (Monotonicity under metric domination). Let d and d' be two metrics on X, and e >> 0 such that d(x, y) S ed' (x, y) for all x. y E X. Then, for any A X and >
c(A,c)a
N((A,)) -NA,c
In words: d is dominated by ed', then e-coverings with respect to od' are also e-coverings with respect to d, hence covering under d is no harder.
A.1 TECHNICAL VERSION OF SECTION
Now we will introduce two technical settings for data generation. We begin with the assump- tions required for establishing the estimation upper bound, and then turn to alternative structural assumptions that are used for deriving the lower bound.
A.1.1 PROBABILITY SETTING FOR UPPER BOUND.
Assumption (Common Assumptions: The RKHS Structure, the Regularity, and the Lipshictzness: Technical Version of Assumption 12. Fix an integer i" E (1,.... /}. A query vector x.. input
measure // = Σ, 8000 @ Ha
(1) and an output = (v, + & are generated as follows:
RKHS setting: We assume the density of Po IP,, is in space Hp ignoring a constant. H4 is an RKHS on a bounded domain Xo C C--M, Mfda with Mercer decomposition (e.g., (Schölkopf & Smola 2002))
K(, = Σ {r),(t)),(1', \ = exp(-cj"),
where c, a > 0 and eigenfunctions (c,)421 are L2-orrhonormal. μ4 is nonnegative and dya d' lies in the metric ball B(H,, (lax3) with 7b O, where À is the Lebesgue measure and d' a global constant without any randomness. Let d' for simplicity, throughout this paper. The density is infiniteddimensional but the informative content is sharply concentrated in low- order components, with figh-freuuency contributions decaying exponentially. For a E R, the Hg-norm on Ho is defined as | = ملي
1 := -, > where dua dx
-E, byeg-
dx
Similar RKHS structures can be found in Suzuki 2020): Nishikawa et al. (2022);
Zhou et al.
(2024):
Liu & Zhou 20255
15

---

Published as a conference paper at ICLR 2026
Smoothness of eigenfinctiins in Ho: (a) (ez)121 are uniformly bounded, and analytic on [-M, (b) No C [-M + 6, M 8]d2 for some i 0; (c) Each ej admits abso- lutely convergent power series ez(x) MENd2 ag* on [-M, M| The three conditions are required to focus on the sample complexity regarding the decay rate a.
Distinguiihabiility of sampled context vectors: The vectors (S4-11)07 (u()) P. satisfy (ul6), )(0) < 15 < i' I. To satisfy this, we also require I d1. This ensures that contexts are sufficiently distinguishable for recall.
Lipschitzness of the target functional: Remember that the output is generated y ("O .a)) +E, & N~ o²). The hidden functional F+ B(Ho, || -11230) x Xg + is
assumed to be Lipschitz: Let the metric on the product set B(Ho- 11 -11200) x Xg be
dprod ((H0 x)) (H6, x')) l1 p6llx0
|| 102-x2122 2212,,
" 0.
where no: 14 E B(Ho, (1x;5) and x' Xq. We write no E Ho by identifying so with its density in Ho up to an additive constant (see Remark We assume F* is in (B || (lgge) x Kg. dproa), a set of L-Lipschitz functionals with respect to dproa-
These assumptions specify the analytic and structural conditions of the RKHS and the distinguisha- bility of contexts, which will be imposed throughout the analysis. We provide an example for our assumptions:
Example (Rapid eigenvalue decay in Assumption 6). It is known (Grigor yan 2006 that on Beltrami operator has a discrete spectrum satisfying Weyl's s law: the heat kernel expansion is pe pe(a,,) v) Ek e e-0(k2/ pxx are eigenfunctions, investigated as data structure (Nadler al. 2005 Coifiman & Lafon 2006 Xia & Shi 2224))
compact Riemannian manifold M the Laplace-Beltrami
_e (a) (y)(y), where {4r)); k dim(M), and t > 0. Settings with rapid eigenvalue decay have been
Gaussian kernels, despite being non-compactly supported, are also widely used in ML tasks (e.g.
Schölkopf & Smola (2002))
Next, we restrict the input measures to be probability measures:
Assumption 7 (Probability assumption for Setting Technical Version of Assumption 4p. Let P(X) denote the set of Borel probability measures on measurable set X. For μo P po Ho E
P(X)) almost surely (with probability 1).
Based on these assumptions, we can summarize the probabilistic setting for upper bound analy- sis:
Setting 3 (Probability Setting for Upper Bound: Technical Version of Setting I. Assumption 6 and Assumption 7 are satisfied. In short: μo IPP is constrained as a probability measure whose density is in RKHS ball.
A.1.2 STRUCTURED SETTING FOR LOWER BOUND.
For the minimax lower bound, relax the probability constraint in Assumption 7 and instead im- pose structural conditions (following Lanthaler (2024) on the coefficients of the Mercer expansion:
Assumption 8 (Structural assumptions for Setting Technical Version of Assumption 5). Let (Ω, IP) be probability space. Instead of constraining Ho P poo to be probability measure, Mo is generated in Definition T as follows:
Random RKHS element: The "density" Puo : Ωt + Ho associated with Ag has the expansion duo
dd (w)() = Pm. (w)( Σ A7 (w)eş()) weΩ,
where (c,)121 an L ortthoooollll basis on Xo. Na > 0, and A > X 2 ... 2 are
summable.
16

---

Published as a conference paper at ICLR 2026
Random coefficients: The variables Z, Ω2 R are jointly independent, satisfy B||Z,1²
1. Zj ~ P5(2) dz, and obey the uniform bounds sup, lllyll> I R. X7a/2 & R for some R 0.
Example 3. Assumption 6 and Assumption are compatible: Take Pj 2-1-11111 and XS S
exp((ce()) Then, ll S ΣS 13 always converges if 7a > no and | 12g
O(A Therefore, there exists some A > such that || a.s.
Finally, we summarize the corresponding setting:
Setting 4 (Structured Setting for Lower Bound: Technical Version of Setting 2). Assumption and Assumption [ are satisfied. short: the density is sampled in the form of Mercer expansion Apo/dd- == E3 3 Zgez where Zz independent r.v.s. and po may not be the probability measure.
B ESTIMATION ERROR ANALYSIS (UPPER BOUND)
The overarching goal of this section is derive a statistical upper bound for transformer-based estimators in Setting 3 Specifically, we establish that the empirical risk minimizer achieves a con- vergence rate of the form
R(F,F) x e m)o/(o+1)))
-
This rate can be regarded the dimentedd analogue of the classical n ((1/d) risk bound for d-dimensional regression, where the effective dimension scales as d ~ (log =/)//(+))), In partic- ular, although the associative recall task requires handling measure-valued components, our analysis demonstrates that its statistical complexity coincides with that of pure definte-ddimnssion sion problem, whose minimax lower bound will be shown in Appendix C The subsequent subsec- tions establish this result step by step, through successive approximation bounds for the individual network layers.
regres-
B. PROOF SKETCH FOR THE ESTIMATION UPPER BOUND
In this part, we will explain how to prove the following theorem:
Theorem 3 (Sub-Polynomial Convergence Corresponding Theorem [ A Simplified Version of
Theorems 5 and 6b. Let F* E Lip, (B((o,)) |l 1lxg3-) Xq. dproa) and assume one of the following cases:
(i) the number of mixture components is bounded as I S di S (Inn)ott;
(ii) the hidden target function i* is independent xq and di (1)))
Let F be the empirical risk minimizer with the transformer class TF(() as the set of mappings Attng, MLPP Attng, o ML.P, such that, H1, Ba,1, l2 (log (1o1)-1)((1) || 82 E exp (O(loge-1))ta 1)). duttuz, Sa,2 H2, B¹, 1, Sa, Ba, 0 in both cases, and
in (i): E,, spolloo, $1, dacani Sa,1 = (loge-1000 in (ii) l k.llpilloo $1, dauai, Sa,1 x
exp (O((oog (((looge>))tat)))) Then in Setting
R(F", FF)
where ar is the decay rate of the eigenvalues of the underlying kernel of Ho-
We will provide a proof sketch for the first case: (i) the number of mixture components is bounded I < di S (In
To derive a statistical rate we must calibrate the size the measure- measure-theoretic transformer hypothesis class. Concretely, choose architecture that grants e-approximation of F* while keeping the covering entropy V()) == log.V(TT (TF 6) minimal; the risk bound then follows by balancing the approximation error with the estimation term governed by V(.). In short, the general theory
17

---

Published as a conference paper at ICLR 2026
in Schmidt-Hieberi (2020) asserts that the excess risk can be bounded by the of approximation terms and a complexity term: for any 5 > O, the L risk is bounded by
R(F F) S inf || F 122 +
V(0)
Here the first term quantifies how well the architecture approximates F*, while the second reflects the statistical price of searching over a class of size ((6). Our proof thus first controls V (-) layer- wise and then selects e realize the optimal trade-off.
Our estimation bound relies on two main ingredients: (i) an approximation strategy for representing .r))
the target functional F [*Vv,, xn) F (mb)) ,xg) via a depth-L 2 transformer, and (ii) covering entropy bounds for each component of the architecture, combined through a composition lemma for measure-theoretie mappings.
Composition lemma (Appendix B.2). We first state a generic result for the covering number of compositions of measure- theoretic measure-theoretic maps.
Step 1:
Lemma 3 (Composition lemma). Lei Gi, i 1,2 be sets of maps r; P(x x x.S)) x:(0
such that x(2) C , (N(())) S N,, and any I22 E 92 is (L2,1, Lipsschitz with respect to the 1 1-Wasserstein and Euclidean metrics. Then,
N([T2 o I1;T, E G [1,1=11,]]eb 1,2];c)x0 S N922 &) N991 2la.it22))
The proof follows the standard finite-dimensional composition argument: approximate each map I' by the nearest covering element, and bound the difference of the composed maps using the Lipschitz constants.
Step 2: Approximation by depth-2 transformer. We approximate F* x) F F* (1b") mrg) using the following architecture, focusing on the first D Z (loge-1)a") Mercer coefficients:
1. First MLP layer (Appendix [.3). Construct MLPe, to augment the input (21 with evaluations (22))))) of an analytic basis {e,} up to O(1)) error. Analyticity implies log (Fi;)))> Z poly log poly D.
2. First attention layer (Appendix B.4 Apply Attne, to MLP& (1) compute empirical means f ej(32) (po(()) up to O 62) error. We approximate a one-hot selection of measures and compute as, informally.
f Softmax (MLP; 10MMML((.))))))
TQT MLP
dv
MMLPPWW) (2) 200 (v).
By the construction of the first layer MLP, and the product decomposition of 1 p the RHS approximates f [e)( dpo(y2). Under sparsity constraints on the attention matrices.
log (dattuu: H, Ba, C2) & poly poly log (T
3. Second MILP layer (Appendix B.5
Approximate Lipschitz map on R DD+d++4 +d2 whose inputs are retained Mercer coefficients () c,(y2) d and query zq. We also show
2 =))a (this is e, not e is sufficient to extract the features. This layer may have
a large Lipschitz constant LMIP. S e ) 2420
for c, S poly log loge which constrains é1 V 6g to be super-polynomially small via the measure-theoretic composition discussed in Lemma
4. Second attention layer (Appendix B.6). Implemented as a -ineedimmssiona)) skip con- nection, with (11) Lipschitz constant, added to fit the formal hypothesis set definition.
Step 3: Bounding the covering entropy (Appendix B.7 Applying the composition lemma re- cursively over the four layers yields
log.N eox & log.N(((d)) 0,1,0,1,0,4 D); cm (o)
82);
18

---

Published as a conference paper at ICLR 2026
+ log (as(daua H, Ba, S.):
+ (F,,, ( ( + 11ka) (c)
This yields (also carefully bounding the term with respect to d1 omitted above):
Lemma 4, The covering entropy of the transformer class satisfies
logN(TT;;) & exp (O(log c - (a, min (a.,0)
where a is the decay rate of RKHS Ho and d1 = (Ine-2)0-1
Step 4:
Applying the regression bound shown in Schmidt-Hiehhe (2020), with V()) log N (TF; dJao and choosing
From covering entropy to risk bound (Appendix B.7).
min (era))
exp (log
mnn [0,0)
where d1 e 1y8 we obtain the sub uub-polynomial convergence rate: Theorem 4 (Sub-polynomial convergence, a generalized version of Theorem I In Probability Setting (Setting
sup R(F, F() S exp (-2((1og 72) F
(ord) (0.P)+T)
where the eigenvalues Xj exp(-cja) and the number of mixture components is T < di 2 (In n) mmin (a.8)/ (min 11)
B.2 STEP 1: COMPOSITION LEMMA.
Lemma 5 (Composition Lemma. Restated). Lef Gb i = 1,2 be sets T, which are maps from P(x(") x(1)) xx2² such that xx(2) C x(1), NNG & Nr. and any I'2 E G2 is (L2,1; L2.2) Lipschitz with respect to 1-Wasserstein distance and Euclidean distance. Then, we have
N(TT2 of |r, G.):) SN(G2: 5)x0 NN 2(L2, + L222
Proof. First, remember that, for standard one-dimensional function classes F, with covering num- bers Nj, Ng.
WHf o f e F.
where Lg is the upperbound of Lipschitz constants of v/f F. For measure-theoretic map- pings T₁ E In and T2 E G2. take Tf and T be the (e1 and eg nearest covering elements (i.e. sup ( (xa,))) [T(,, - (u,,)r) < 6). Then we bound the difference of compositions
(T2 o (i)(,x) oi)
(T of), (TT (T' rf),
(La La2)> - Pi(4, 2)122 + E2
(L2, L22)c1 +
B.3 STEP 2-1: FIRST MLP LAYER
We begin by formalizing the approximation properties of the first MLP layer, which is responsible for embedding both the input tokens and auxiliary analytic features into nigher-dimensional rep- resentation. This layer plays a crucial role in ensuring that subsequent attention and MLP layers can operate sufficiently expressive feature space.
19

---

Published as a conference paper at ICLR 2026
Lemma 6 E & Wang 2018)). Let f be analytic function over | M, M such that Xo C [-M ö, M 0| for some ó O and the power series f(z) = EKEN' agæ" th is absolutely
convergent over [-M, Mf Then, deep ReLU network f with depth O(log ())de)) and width d2 + 4 (independent of e) satisfies
sup 1f(x) ((t)) Se. xe
Here, the notation x* denotes the multivariate monomial II at and the absolute convergence condition ensures that the power series uniformly converges on [-M, M] enabling uniform ap- proximation the interior domain No.
As a corollary of Lemmal 6 we obtain the following result:
Corollary 1. Lei d1 dz. For function such that
21
x2
f: M- Midtda - IRd+D, (()1
el (1(22)
[ep(22)
where ej defined in Assumption 6 That is, f preserves the first d1 + d2 coordinates (æ1, 12) and augments them with analytic feature functions Eg that depend only on Z2. There exists a network F(l1, Pl, $1, 00), where l S (log E y2da PL. S D d, $1 S d + (loge] 1 d2 D, such that
If fllo0 c1
Proof. For the first d1 indices, we simulate 21,; = -ReLU (e, a1) + ReLU(e,e -11. This requires (11) depth, (d1) width, and ((d)) parameters. The + di-th (i 1.... d2) indices require O(1) depth, ((d)) width, and ((22) parameters. We refer to Lemma 6 for the rest of indices.
In other words, each analytic component ej can be uniformly approximated by a ReLU network of logarithmic number of parameters, and the concatenated mapping f can be represented by block- structured network with parameter bounds as stated.
To evaluate the covering number, we use the following lemma:
Lemma Schmidt- Schmedt-Hieber 2020 Ler II + 1). Then,
((F(,,,
I (s+ 1) log(o
The covering number is
P1, S(d + (log 1 D) (log + logloge + (1og6-1)266 log(d + D)))
SCD.e, (d+ elooge addz)
where CD S poly log D + poly log + poly log log G
B.4 STEP 2-2: FIRST ATTENTION LAYER
In the preceding section, we have constructed an MLP layer capable approximating the basis functions ej (Assumption 6) with high accuracy. The role of the first attention layer is now to process an input mixture measure Vy, identify the associated measure corresponding to a given query component yf.i, and then output the concatenation of the raw query coordinates with the integrals of e, against that associated measure. Formally, this operation is realized by the mapping de defined below.
20

---

Published as a conference paper at ICLR 2026
We analyze the approximation properties and complexity of the first attention layer in architecture. Recall that the attention operator Attng has already been defined in the measure- theoretic form
Ating P(TR x Raat
datte
where the first argument is probability measure over token representations and the second argument the query vector. The following lemmas show that, under appropriate structural assumptions on the input measures and functions:
1. the target mapping 22 can be realized to accuracy e2 by a member of the attention class A( A(datt:; H, Ba, Sa) (Lemma 8);
2. such attention mappings are Lipschitz continuous with explicit bound in terms of the model parameters (Lemmag)
3. the eo-covering number of A admits upper bound in the parameter regime above (Lemma TO
We present these results in turn.
Before presenting Lemmaß g we clarify the role of the mapping Φ2 in the composition- of-maps view (ef. Definition 5). In our construction, the first MLP layer Φi approximates the Mercer features:
3
(1(,2) =
Da el (ad)
Lep (ep +1:d)
where {ey}ı21 is the Mereer (RKHS) eigenbasis on No Rd Accordingly, the fush-forward measure after Φ1 is
#1 = (01 )),1 E P(RR+D),
and the composition rule yields
(02 o (1) = (2 Φr (1, x)).
In the present setting, 22 preserves the first d coordinates and replaces the last D coordinates by the (component-wig integrals of the associated measure against the Mercer basis:
F1
:
æd
f
2 (2 (1,x)))
/edppb" dal
/
ep du! (8)
where i* denotes the index of the associated component selected by the query. Moreover, if μb du(i*)
(e*)
admits (Borel) density w.r.t. reference measure X, say dd = fug") with fng E L²(() (cf. Remark 2). then, writing the Mercer expansion f.gg") = Eÿ21 byes, we have, up to the immaterial Ters.
ee / f = (e,, feg.))r))1 = b,.
Hence 62 produces, in its last D coordinates, the (truncated) Mercer coefficients of the associated density.
Lemma shows that, under structural assumptions the input measures and the transformation
f. the target mapping 62 can be uniformly approximated to accuracy 62 by an attention mechanism with bounded parameters.
21

---

Published as a conference paper at ICLR 2026
Intuitions of Lemma 8
The key point is in the structure of the first attention layer: For fixed j, extract the associated Mercer coefficient bj = ff dub"" we construct QK-matrix W W2x such that, with tokens mapped by the (simplified) first MLP layer (21, + Φ (m 22) = (I1, ej (x2)),
1 if i= ii; for y Pola ,01 @ H4 (8)
()y())) Wo
0 if i i
((2)
(1))
recalled
(2)
Psyu (3) 201
(3) Vigu
(1)
Figure 3: Geometric sketch of associative recall. Components pye are separated along feature axis via the first MIP layer fi: the query maps to ())())) and aligns with anchor bh (v(()) = (y((((0)) T ,OT)T), thereby recalling mb (i*) The pushforward Wyg provides features used by F*(u("), ,r.g).
(8)
Then, the softmax value will be
(o))) Wor Dli i*].
The construction is simple: take W QK Ede ejey such that (g(zg) T W W (y
(u(*") v()), and multiply large scalar, where e₁ k-th one-hot vector, since ub preserves the first d coordinates: vb(xrg) (o()t) : (0(1) [u(0) : T and (u(()), are distinguishable (i.e.
( S for + j). as described in Fig. 3 Then, with tokens mapped by the first MLP layer
fi, we have the (d + j)-th output of the jth head is given by
/
e
T
W
Softmax (15 (z) yw QK (b))
(5(())d(()
Eat1eT
estie
1 ""Je;(0a Σ 8,10 & m0) (6)
(z)
= (
where take the parameters as W V e Finally, the second MLP layer maps (ffe ej dub ) ((()) y, and the second attention acts as skip connection.
Lemma 8. Let P, denote the set of probability measures of the form
Vj Σ J.m Sa (
- 14
where the measures μ4 and the mapping f satisfy the following conditions:
22

---

Published as a conference paper at ICLR 2026
M4 is probability measure supported on bounded subset of Rd, where d dj + d2 and admits the product form
H4 == @ Pix
with 02 E 8hi C [- B,) ds satisfying (us, Ui) S for all o d. and where jú probability measure supported on a bounded subset of TR
f: - RR+D given by
21
[(x)
where f Rd - DRP is bounded functiiti
. "IS d1 and supp(fa1s) C [-By, By]++D for all i.
Moreover, for each define vi
[ gdi (0dg} and set ys == f(x.)).
Define the mapping $2 Py Rd+D + Rd+D by
Vfs,1
Ursd s sa(f) fi Pss
02(1),91z) =
where i, denotes the j-th coordinate function of f. Then, there exists an attention operator Aftn A(duuaa H, Bay Sa) such that
[ - Attn(vy, 81.)) S22,
sup WEE
where dattn = D. = B. Vlog(T (I .. and S. d
Fix an arbitrary E {1...., = D). We first specify the attention weight matrices as follows:
Proof.
1h = vb = eathe2th
where d = di + d2 and eath denotes the (d+ -i-tth standard basis vector Rd+D, Similarly, define
La OdstD]
Q³ = k = c
for sufficiently large constant / log (Ta 1 2 /og((T -..))
The corresponding attention weight for query and key f(y) is given by
(ettmax((Q"rr, Kh f(y)))
exp (c (2i.1dd) V1.d,))
exp (2 v1.d,)) duy(y)
exp (c² (I Visdi 1)
J-1 - exp ( Frrd,) d(ōr. & (v)
23

---

Published as a conference paper at ICLR 2026
exp (e (0i, vida))
1-1 Σ exp (ov,, m(a)))
exp(c2)
1 (exp(c²) + (I - 1)) 1 (o =n (2s 1 Ug i * j)
I
= I- (vidd) m. + (2)
where the indicator function 1 [sn.a,=e,) arises because the keys yi.d; take values in the finite (vi,..., 0r with mutually nonpositive inner products. The last equality follows from the choice 2 log(1 e5 which ensures exponential separation of the correct key from the others.
Next, applying the value and output projection matrices, we obtain
wh /
Softmax((Q""
Σ Wh Softmax((Q"'x Khh (())))
(1. (
=m.) +((-1(22) edth (Julus+tia) O(e1)) a(ōr, @ (v)
P=1
(here caunn== = fh)
= - ( + (() dōr, (wnd))) (
In (yid, -1a) div (ud, (Ud.+ +na)) edth
(f In (2a) eath + (c22).
Finally, to incorporate the skip connection over the first coordinates, let
La 0
0
0
Applying to the input vector yys yields
Ayy.a
Uf.id OD
Combining the attention output for each head h with this skip connection reproduces the target mapping 62 up an error of order (Ee)) in the loo norm. This establishes the desired approximation property.
Remark 3 (Why do we need a softmax attention?). We informally demonstrate how linear attentions struggle with one-hot selection of densities without orthogonality. The main problem is that the context vectors (1)))); may have negative correlation. For example, we consider / = 2 and
-
we only have access to a linear attention, with the same QK matrices in the lemma,
if i=
((Q*ttn(Q(((s)))) Khh f()))) (n()) (())))
if i
This implies that is hard for linear attentions to extract only the i--th measure through integra-
tion LinAttn( (Q" x2. K { ydyyyy()) See Han et al. (2024); Fan al. (2025) for empirical discussions; see also Kim et al. (2024), where strong assumptions such as relaxed sparsity and or- thogonality of recall candidates were required bypass this difficulty.
24

---

Published as a conference paper at ICLR 2026
Thus, the first attention layer is expressive enough to implement the "association and extraction" op- eration: given a mixture, it can select the relevant component and compute the eiinneeralss needed for downstream processing. We next turn to the stability of such an operator with respect to pertur- bations in both the measure and the query vector.
The following lemma establishes Lipschitz property of Attng in both arguments. This lemma is inspired by Vuckovic et al. (2020). This quantitative stability will be essential for the subsequent covering number analysis.
The attention operator Atiig computes a weighted average of values using a softmax over inner products xQ*x,, k" To bound its change when (J, varies, split the effect of μu and
For the measure part, Settoovvicc-ubinsteen duality expresses the 1- I-Wasserstein distance W1 (the standard Wasserstein metric) as the supremum of expectation differences over 1-Lipschitz functions, allowing us to control the change via the Lipschitz constant of the softmax kernel.
For the query part, we directly bound the kernel's Lipschitz dependence on and apply sparsity of the output projection. Combining both yields the stated Lipschitz bound.
Lemma 9. Let Attng A(daunn H, Bay S.) be the attention operator as defined in Section 3
Assume that the query inputs satisfy | [0alloor || wl S BB,, and that for each i E {1,2), every y E supp(us) satisfies llylloo I By. Then Attng Lipschitz in the joint variable (Jt, 2) in the sense that
| x1) (12,
S H exp (B (Wi(u1, 12) + || - -x2ll2).
Moreover, if dastn S D. H S D. Ba S (log(((7)) and Sa S d, Br, By S 1, then the Lipschitz (T constant is bounded by D ( log (1r
Proof. Bounding the difference in μ.. We first bound the difference in the y-variable while keep- ing the query fixed. By (P-i) the matrix sparsity bound ||Avilo I sb|lu|loo when A has at most nonzero entries per row and each entry bounded by b, we have
(Attno(u1, x11) Attna(u2, 21)l
y exp (12"z, K"y))
yexp 210"2, K"y}) J exp ((Q Kh ( )du2(=)
B2
J exp (QQxx,, K"z))ddr(()) dpl
due
Next, Inserting intermediate terms align denominators and numerators, we obtain, [11 - Attno (12, m1)
y exxp (1Q"x, 2, kh))) dun / x1, exp 11, Kh Kh2) ddy
yexp (1Q"x x, khy)) J exp ((Qh K Kh x2p(((2
B
dul
yexp (1@"T) v1, K²t v)) exp"( Kh dup
y yexp ((Q" kh) Texp((2 ((Q"s1 Kh (d) due
yexp (Q 21 k4ッ)) J Txp (Q"h Kh dd
yexp (Q x Kh Texp((Q' (("h Kh (2))
$2
dup
yexp ((Q411, K3
yexp (Q"' k2²y)) d12
Σ 2 B²
d/1
Texp exp (1Q"M1, Kh₂) (d
exp ((Q" Kh )d)((((
h
(8)
Bounding the term (i). We have
< Σ S B2 |ʃ yexp ((Q" x1, K²h v) d/11
(i)
h
25

---

Published as a conference paper at ICLR 2026
[ Txp (1Q (dui(z)
Texp (1Q )222(2)
5 Ba / yexp iq, K s))
h
x min { { eex (10" Ka 2) du))))))) / exp (10" k)))) =)) -2
f exp ((""x1, K ))= - / exp (1Q" Ka ddpp(s) (by (P-ii))
exp exp (35 (35 / exp exp (1 K x)) d(ui - 22) 22) (z)
2 Σ B2 h
(by (P-ii),
where we used:
(P-i) the matrix sparsity bound |A ||ul|| S sb|lv||>> when A has at most nonzero entries per row and each entry bounded by b;
(P-ii) [("hx x,, K" b) I S.B. B2 S. B. By. Indeed, since |10 | S S. (total number of
nonzero entries) and 12)x ( I B., while || BN and |l S By we have
1@ x1, kyy
<|1 =1 (Q02zlll 10 |K*v
12jaal [x1x))
Σ 5.k
JK livel
max
k
B.) (S.
Here the bound ||Qa=|/=>> S S. Bg B2 follows because each coordinate of Qh01 a sum of at most S, terms, each of magnitude most B, similarly, | xyll S Σj. |Kl lyul S. B.B.B B, since there most S. nonzero matrix entries in total; (P-iii) the bound
S S ln
azl. A A< min(a1,02).
0n
02
The RHS is bounded
/ exp ((Q"xrn km2)) d(ar u2) (z)
((i) 2
Σ S. exp exp(
SHS exp (,
using the Miniorovvcc-Rubbintii duality
Wi(41, = sup Lip(0)51
Φd(H1 H2).
and the fact that [- By, By] daten because
exp((Q"z), K'y)) is S.B.B, BB. Lipschitz on
lexp (1Q' K ys)) - exp ((Q" m, K² ya))
exp S 3d B, B,) (Q* x1, K" km(ys y4))
< < B² exp S² By llus yall 12l22-
for y3, 94 BB Byydd Jaan.
Bounding the term (ii). We have
/I/ y exx (1Q" or k²h)) v)) d(pz (2)
(i) S Σ B fexp (1Qh2) 21, Kh Kha) (2)
26

---

Published as a conference paper at ICLR 2026
/ [nuexx (1Q" R) d(ui - u2) (v)
- Σ S. exp exp(S
max
dateo
using the 2, (,, H2)
SM S. exp
duality
/ 6d(w1 u2),
Wi(H1, = sup
1ip(0)51
and the fact that + y exp((Q">1 k²) is (1+ B, Bx B.,) on | By. daas..
Finally, we have
|Attno (p1, Attno x1)1 SHS (S. By exp( 4S ( + (1+ S, e x Wi (2),
Bounding the difference x. Next, we bound the difference in the query æ. For fixed μl, using similar interpolation and Lipschitz estimates in x,
Attno x1) - Attmo
/
yexp (1Q K"y))
yexp ((Q" kdy)) fexp (1Qh Kh²) dduz) dpr(v)
52
/exp (
S BaBlaa 11 - x211x
Σ B /
yexp (QQ k'))) dup -
yexp (1Q khy)))
exp ((Qh K 2/2) )dul (z) d1r(1)
J Texp ((Q"I1,
yexp (1Q" K*
dp1 -f
y yexp K*
+ Seep (Qhr2, Khz) (2)
(10 kh ())(()) duz(v)
S, - 22l12
SSS,Ba v
x2112.
By combining approximation and stability, we can control the complexity of the attention class via its covering number, as stated next.
We now bound the cg-covering number of A(datin: H, Ba, Sa) in the parameter regime of interest.
Lemma 10. The c2-covering number of A(dattn, H, Bay Sa) is bounded by
N(A(dattn, H, Ba; 62)
$ (dan exp ())g((()) (Z (E + 1)) O(S.H)
Furthermore, if datn dd D, H = O(D), B. z Vlog(Ie)) [1T S. S d, and B., By 0(1),
then the covering entropy is
(A((aat H, B., Sa), E2) CCD Cp Dd + log 1)3 log 6
where Ca S poly(log + l).
Proof. We define (( set of Al (dattn: H, Sa) set of mappings whose parameters can be constructed as follows:
For each matrix Wht ",, Kh, yh in each h E (I....,II}
1. Choose Sn matrix entries among (d entries.
27

---

Published as a conference paper at ICLR 2026
2. For each matrix entry,
Set its value from {6 1) Ba 1 0,..., 1 where 2
exp(-Ca(log(H1)
BB where C2 sufficiently large constant.
Set the value of chosen Sn entries in A from {(i ( Ba 1 = -......2e"" where E' (S,
Let us prove that the above set of mappings is a (ooeeriv,,n is clear that for W h = 1...., H, there exist matrices W in the E-covering set such that
W W S H exp (-C
I W0 S 25a
where C3 is a sufficiently large constant. Similar inequalities hold true for ,", V4, and A. Let i (Å, (W*, Q", Rrh )x) Then, for all f E PP[-By. Byl Byldau") and x E [- Bus B Jaaue
||Attno (1,, x)) Attug(14
Vny (1Â"x, kK"u)) ʃexp (Qhrr Rh))) du((z) dp
wh /
du W yex (10"x, K*
T exp ((Q^x, Kzz))du(z)
b
+ (I -A)xlloo
Wh /
yxp (1 k"y))
yxp ((Q"rr, kd de exp (1Q"x, Kh ddp(z)
exp (1QAx, x, 2h22) du(() du w
h
(i)
Vhyeep (1¹"z, Khy) exp (1Qhx, Kh kzz))du(() de
Vhy exp (1Q"z, Kny)
+ Σ BaBa h
J exp ((Q"x, K kh²) dd((z) du du-
(8k)
Vhyeep ((²"Z, K* Kny) Sexp (10xz, K*) k)
Vhyjep (10' khy)) exp (10hz, K²²)) K²z))d dp
du /
+ Σ Sa Bu
(dis)
yh yhyeep (Q/^ R
yxy (Q"x k(y)) du exp (Q"x,, Kh²) du((z)
+ Σ S Ba
du
Texp ((Qhx, K h [dm(z)
(1v)
Vhyeep (1Ộ"z, khy))
Vhyexp (1Q' K(h) dp Sexp ((Qt,, 2))) du(())
du I
+ Σ
S Ba
Sexp (Q"h.,, Khz) du((z)
(1)
Vhyexp (1Q" K(li du Vhyy (1Q" k(h))) du / Sexp (("hi,, Khz)) du(())
+ Σ SaBa
Sexp (QQrz, k1) du((z)
(14)
+ (A A)ælloo
(wi))
Each term bounded follows:
28

---

Published as a conference paper at ICLR 2026
(i). Let w == f v" yexp ( (Q""2,
( " kh2s)d du. Then, (i) I I1 W ) x (2Sa)
H 1 exp ( B B,)) e. exp (O & by (P-i.ii);
(ii. The second term is bounded by
Vhy yi /exp (12hz, K ddzz))
(it) S.
sup #ESupp(H)
x( x(exp (1Q kyy)) - exp (12 10 SS, ex,B, (O
10 10"x,K'' 1h v) 1Ô"x,, kay)
sup
yESupp(a)
SS,B, exp (0(5) II(@" xx))=1l0> sup
|||1
yEsupp(a)
(0
H exp
exp
E
SH
Note that the second inequality is derived by (P-ii,P-iv) and the fourth inequality is sup- ported by (P-i).
(iii). The third term can be bounded in the same way (ii).
(iv). The fourth term is bounded by
(iv) SSaBa // v'yyex/ (0"22, k) dul
x ((Q Kh ()))))dd(( Sexp (ihhe, khz) dd((z)
S. / yeyyexp ((²"0, Rーy) dul
x min { exp exp
Krt (K =))d(()=) / exp (K)) (xh=))dp(a Jap(e) }) -2 (by (P-ii))
|exp exp (10"x, exp (Q0' k*)) du(z))
x
exp (O(S)
(Q'x, kh)) - (0"22,K'0
sup =Esupp(a)
SH-E E;
(v). The fifth term is bounded in the similar way as (iv).
(vi). The sixth term is bounded in the same way as (i).
(vii). It is easily bounded by H using (P-i).
Please note that (P-i) ||Ax/|oo boo ||Ar||1 < sb|lz||/oo where the number of non-zero entries in matrix A is bounded by 8, and the absolute value of each entry is bounded by b, (P-ii) (Q^r,, Kdy) s S. B, B. S, B. By because each coordinate of Q²x is sum of most S. terms, each bounded by B.B and similarly each coordinate of K is bounded by S.B.By. (P-ii) 1/a, 1/a2 (a1 a2) ()) A- -agl when A < a1, 02 and (P-iv) y + exp(y) and y y yexp(y) are (xxp(O(B)--ipschit) over B).
By the construction rule of the covering set, the covering number is bounded by
A (A(dattt H, Bay 8)
29

---

Published as a conference paper at ICLR 2026
de
4H-1
?-9a
Sa
(attn
4H+1
eep (O(S, log(H) B,B,B) (E + 1) 1)8.
So
Together, these results give a complete characterization of the first attention layer in the measure- theoretic setting: it can accurately realize Ø2, does so stable manner, and has a covering number that scales favorably with D and 62-
B.5 STEP 2-3: SECOND MLP LAYER
Having established the previous subsections that the first MLP layer can approximate the Mer- basis functions ej and that the attention mechanism extract the corresponding coefficients [e, df(t") associated with the relevant component measure, we now turn the next stage of the architecture.
In this step, the inputs the model are effectively reduced the finite collection of Mercer coef- ficients (bz,... .b)) together with the query vector The statistical problem is thus transformed into the approximation of Lipschitz function defined over a (D ((1))-dimensiona domain.
Our goal in this section is twofold: first, to determine the appropriate truncation dimension D that balances approximation error against complexity, and second, to establish approximation results for Lipschitz functions of D variables using neural networks.
B.5.1 DETERMINING THE DIMENSION D
As discussed above, after the first MLP and attention layers, the effective representation of the input measure Ao reduced to its Mercer coefficients with respect the kernel eigenbasis (erh21- In practice, however, only finite number of coefficients can be retained. Thus, key question is: how many terms should kept in the truncated expansion so that the approximation error remains negligible while the statistical complexity of the model is controlled? The following lemma quanti- fies the truncation error when approximating f4 by projection onto the first D eigenfunctions.
Lemma 11. Let po Ho with Mercer expansion
dpo yx
beli,
where {Ei} are the Mercer eigenfunctions associated with kernel eigenvalues Dii and X is the Lebesgue measure. Define the truncated approximation
D
Σ
bre-
If Y < 0 and "/b > 0, then the truncation error in the nj-morrm bounded as
I|po Pol1 I Apai -
Proof. The LHS is bounded by
1|p0 - Ao Tr
X
76
22
(2D+1
X x T
Σ
02
X +
22+1
D+1
30

---

Published as a conference paper at ICLR 2026
10
Σ 120+1
(by
AD+I 2 X, 12 D+1 and - > 0)
-x- SV ///50i
AD-1
(by Σ
6 1
where we used
S for 2 D in the first inequality, 7, 2 A for i 2 D + 1 and
Ap+1 that po is in the ball in the last inequality.
Having controlled the truncation error of the Mercer expansion, we next turn to the regularity of the target regression function Ft. In particular, F* is assumed to he Lipschitz continuous with respect to the product metric consisting of the -y-weighted RKHS distance on measures and the standard Euclidean distance on the query variable. Formally, there exists L >> 0 such that
(F, -
L (IIu- (1la-vlacc + || vlla): Vu, E B(Ho, || Ilage)) x,y Rd
This Lipschitz property ensures that once the aefinite-dimensiin measure μ is replaced by its trun- cated D-dimensional approximation. the induced error on F can be directly bounded. The follow- ing corollary makes this reduction explicit.
Corollary 2. Define the truncated regression function
FD(Po.v) v) = F+ Ebier x 1)
dpo dx
breis
1=1
If b; f. 2 D + 1, we simply write Fb bD. Then,
FD(HO, v) F" ('HH, w)1 S ADa2
sup PoE B(Ho.ll (ggh))))))
Moreover, FD is Lipschitz with respect to the coefficients (bI,... bib...,,b)))..). and query satisfying
FD(b, v) - FD((s()) s T,
max X₂ " - cll2 + T.llu - v 1|2
v
121
50(1)
where (bI.....b bp) and c (ci...., cp). Note that Y so the multiplicative in front of lb cll2 is @(1).
B.5.2 APPROXIMATING LANIEE-DMMNSIONAL LIPSCHITZ FUNCTIONS
Once the Mercer expansion has been truncated to Odd + D) coefficients, the infiniteddimensional regression problem reduces to approximating a Lipschitz function f [0, 1) + R with Lipschitz constant K. We now recall quantitative results the approximation of such functions by deep ReLU networks.
Lemma 12 (Schmidt-HHeber (2020)) For any function f Lip, 1 P) and any integers m and N 2 exp()(())) There exists network
(D, I).. 6(D +
with depth
t~ + 1)(1 - log (DggDDo) +1)
and number of parameters
8 S 1)3+ N (m +
such that
|1 - 111 $ (I+ 1)(1 + D286DN2~1 LND
31

---

Published as a conference paper at ICLR 2026
This lemma shows that deep ReLU networks approximate any Lipschitz function on [0, 1 with an explicit trade-off between network depth, width, and approximation error. The next remark connects this general result to our Mereer-RKil setting.
Lemma 13 (Schmidt-Hiede 2020 Let = oo + 1). Then,
log ( 8) & (s log log(5
This bound shows that the covering entropy grows at most logarithmically with the resolution 8 once the architecture parameters (L,p, s) are fixed. Applying parameter selection yields the following implication.
Finally, for later use, recall useful estimate the Lipschitz constant of ReLU network in terms of its layer widths.
Lemma 14 (From the proof of lemma 5 in Hhamidt-Hiebee 2020 ) The Lipschitz constant of NN (w.nt. infinity norm) is II
From the above lemmas, we have a specialized approximation results for our Mercer-RKHS setting: Corollary 3 (Specialization to Our Setting). Under Serting and assume d, (In (Inc=1) that
D
( (- 11/a ( di ( -2)2/min(a..))
2c
Letting
m = O(D log Eg ")
N Eg
in Lemma 12
there exists a ReLU network with depth
Eg S (poly log(d + D) (d+ D) logez -1
width
|22ll0 S (d+ D)zs d+D
and the number of parameters
S 0
() (poly log(d D + cJ (3))
that approximates FD, which was defined in Corollary 2 within sup-norm error S
Moreover, the covering entropy of the corresponding hypothesis class satisfies
log.N( &,,, F);ea) S -O((ue (ey0luee)))mmmaeeee)) poly log ((--=
and the Lipschitz constant of the network (with respect to the too norm) is bounded
-O(c,(ne 12 m
II p: 6g
Ce S poly log loge
Instead of assuming di S (loge -1951 if we assume that F* is independent sap then, by adding one layer TR++D x Fd+ld++D -ReL.U(-Ar)) Ar) - ReLU(Ax) E ERD where A = [ODxad D the ReLU network that approximates Fo with sup-error S ea is constructed with depth
8 S (poly log(D) (D) loges
width
P2 = (d (.d+D.00 D,O D.. D)
times
and the number of parameters
S 550 -0 (Ine VV1)))) -((ne) ((0(m))))((( (poly logyllogDD( +D+ + +D)
32

---

Published as a conference paper at ICLR 2026
The covering entropy is bounded as
log (F(C,, F): S -0(( poll log(c (deg))
and the Lipschitz constant is
-0(a((ne))
11 1=0
Pi S di Eg
Ca S poly log loge
where D = (In6-1)a
The original lemma of Schmidt-Hieber (2020) is stated for functions on [0, 1| In our setting, the domain is (-0(1), 0(1)]_ A simple rescaling maps [-0(1), 0(1) to [0, 1]. and this transformation only modifies the Lipschitz constant by a fixed multiplicative factor. Therefore, the approximation and covering results above remain valid to universal constants.
Remark 4.
This corollary consolidates the consequences of parameter selection in our setting: the effective input dimension D grows like (Ine-1)1/a the network size scales sub-exponentially in 1/e, the covering entropy is controlled by c-O(e -1y//)) and the Lipschitz constant grows most quasi- polynomially in E when = poly log e
STEP 2-4: SECOND ATTENTION LAYER B.6
Recall that the attention hypothesis class is parameterized as
A(dattn H, Ba, S,,
where dattn is the embedding dimension, is the number of heads, Ba, By are bounds on the operator norms of the weight matrices, and S., Sy are sparsity constraints.
In the present step, we only implement the skip connection of a scalar. We specialize to the case
dattn 1, 1, B. 0, By =1 S. 0, S. =1
That is, the second attention layer belongs to the class
A(1,1,0,1,0,1
This particular choice corresponds to degenerate attention operator that is independent of the input measure and simply implements a skip connection acting as the identity on vectors, thereby ensuring consistency with the formal definition of the overall transformer class.
Lemma 15. The ca-covering number of A(d + D,1,0,1,0,4 + D) satisfies
log ( (1 = Oppoly loge 7
Proof. omitted.
Lemma 16. Every allention operator Atln 1(1,1,0,1,0,11) O(1)-Lipschitz with respect to the Euclidean norm.
Proof. omitted.
B.7 DERIVING AN ESTIMATION ERROR UPPER BOUND
We now combine the approximation bounds established in the previous subsections to derive an estimation eπror guarantee for transformer-tye architectures. Let TF denote the hypothesis class consisting of transformer models with the architecture and parameter constraints described Sec-
tion 3
33

---

Published as a conference paper at ICLR 2026
Lemma 17 (Approximation by transformers). In Setting 3 for all F Lipz ll (llgg))) (. llg ) there exists F 'TF such that, for any input of the form
(v, (a) where
P ==
Emb (0az)
i=
(1) with p Potn generated according Definition 1
FF (v. - F(v, S.
where the parameters (d Hj, Bag, B' Sa Sa lj Pj, Pj, 8;}3=1 of the hypothesis set TF are de- fined as in Lemma 8 for d1, H1, Ba,1, By Sa,,, S.D, Corollary 7 for &1,1181, Lemma 15 for
d2, H2, Ba.2, B2ag Sa.2 Sh.2. Corollary for E2, P2, 82, respectively. The effective dimension in them determined in Corollary Determination of I...., 4 are deferred to Lemmal 18
The above lemma shows that the transformer hypothesis class is sufficiently rich to approximate any Lipschitz target function F* on the admissible input domain, with uniform accuracy c. Please note that the output of each layer is uniformly bounded (we can add clipping ReLU layer for each layer).
To analyze the statistical performance of ERM (empirical risk minimizer) within this class, next require an upper bound on its covering entropy.
Lemma 18 (Covering entropy of transformers). The covering entropy of the transformer hypothesis class satisfies
log.N (TF;;)) S (0(0ne (()iintt)) =xxp wxxppxxppp -
assuming that I S d1 = (In (Inc-1)0 and d2 1.
Proof.
The claim follows from applying the composition lemma (Lemma 5 for covering numbers. In partieular,
log DogN(TF;;))
< &log.N (AL,,,,,,,,,, + Nog (Fl62,p2. s2):
+ log. (AAttne, J:
Slog
A(1,1,0,1,0010
+ log. F(12,12,82); S((e)
+ log
Aldaatmn H, Bay Ha); 82r (
+ log. (1): ( + LAuaa..1llaa (1))
Slog (A(d -
+ log P(): + log (Alduttm H, Ba. Ha); - Olc
242min(a, min(o,
+ log (F(41, exp(p-(cc Inc
2+2minla, d3
mintor,3)
where e, I poly log log Here used that
(i) Letting é4 the second attention layer is Ó(1)) (Lemma
16
34

---

Published as a conference paper at ICLR 2026
(ii) Letting cs [(c), the Lipschitz constant of the second MLP layer is bounded as
1MLP,2 X exp(-00 (ce ((In c ((n== cZ exp(ce(Ine))
2+ 24iinnfaa)) minte..))
(ce X
poly log l (Corollary B
(iii) Letting 62 2 exp( expp-O(celmg 1)
2minta.. 91 mina,
the Lipschitz constants of the first atten-
tion layer are bounded 1, exp ((cc
L 1,
D exp(O(de log (og(Te)))) To()
2+2mitn(a.2)
min(a..)
(Lemma 9)
(iv) We have 61 2 0(1) exp (Ime))
2+2min a. min(a,
)) for the first MLP layer.
By Lemma and Corollary g
log.N (1,11, S poly loge
By Corollary 3
log (F)2 Se - 1y1/min(a..))
By Lemma 10
logNN (A(dattn: H, B. Ha)ie2) S poly(loge -1 + log 1) d..
By Corollary 1
log.N
S poly log log poly log e lolllol.eeeoo () loge dd (od2.D+d). D+d).
Assuming that I S di (log e)8-* and d2 0(1), have
log.V (A(dattn1, H1, B,,1, (2,1) + log (1): + log.N P2, s2) +
$ O-(nne 1)
With these ingredients, we can invoke general statistical learning bound for ERM.
Lemma 19 Sihhidd-HHibbee (0200). Consider Gaussian regression, and let F be the empirical risk minimizer over hypothesis class F C (T2(Pu...). Suppose [I & A for all E F. Then, for any > (8) denotes the covering entropy of F, it holds that
F*I1ZA(P,...)) + (A²+o2)VV(0 + (A+
R(F*
F) S
1 fEF
inf
We are now ready to state the statistical rate achieved by transformer ERM.
B.7.1 SUB-POLYNOMIAL CONVERGENCE RATE
Theorem 5 (Sub pol-poolyommil convergence). Let F be the empirical risk minimizer whose hypothesis set is constructed in Lemmal 17 Setting we have
R(F F) $ exp( (2(((nn))
min[
mix(o.d)
assuming that the number of mixture components is bounded as I S di S (Inn) 6)+
and
d2 ~ 1.
min(o.
Proof. Let E ~ exp -c' (In
minto.,
for sufficiently small constant d' > 0. Combining Lem-
mas 17 and
with Lemma 19 we obtain
R(F*, S
n
35

---

Published as a conference paper at ICLR 2026
exp (O((lmnn)a (Inn))))
Se +
no"
Se +
for some < d <1,
X exp (2(((n))
minia..)) (mIILO
assuming that the number of mixture components is bounded as / di S (Ine-1ja
Remark (Interpretation of Theorem 5 A common statistical learning bound for nonparametric regression takes the form
R(F, S -114))
where d is the (effective) dimension of the problem. In setting, however, the eigenvalue decay assumption 2y = exp(-cj")) implies that the effective dimension grows only as
d (Inn)/(at))
Consequently, the bound in Theorem can be interpreted direct analogue of the classical -(1//) rate, but with d replaced by (Inn))/aa+1), Importantly, this shows that the estimator by- passes the usual combinatorial difficulty of associative recall tasks. In our framework, each element to be recalled is not finite symbol but rather probability measure, i.c. object. Despite this intrinsic complexity, the analysis reveals that the statistical behavior is gov- erned purely by the eigenvalue decay of the underlying kernel, leading to the rate characteristic of infiniteddimensional regression.
B.7.2 BEYOND LOGARITHMIC CAPACITY
we discussed the case that the number of components (the "capacity" in terms of the associative memory) is bounded as
In Theorem 5
min(o.d) I I d1 - (Inn) mln
which is logarithmic with respect to not only the sample size but also the number of "parameters", which we consider as the covering number, of our Transformer models. This is because the lipschitz functions over $d.-1 not B(Ho, (lxgo)). becomes too complex when d1 is large. On the other hand, in Appendix B.4 observed that the number of the actual parameters attention matrix is linear in d1 (2/1 I).
Here we consider the following additional assumption:
Assumption 9, The target function f (m(b") (i.e. we can write F* (((1()
((') (i*) xq)) is independent of zig and only dependent of po (1*) x.g) F. (mD (**) )))
Then, we have the polynomial "capacity" even in the associative recall task with the infinite- dimensional measure-valued components:
Lemma 20. Assume that
1 exp (op(o de = O(1).
In Setting and under the additional Assumption
log.N (TF; S exp (Onne -1)++a/a)))))))))))
Proof. The main strategy of this lemma follows Lemma 18 We only mention the differences from the preceding lemma.
Let D = d + D ~ di (consider the case & di).
(i) Letting <4 the second attention layer is O(1)-Lipschitz (Lemma 16
36

---

Published as a conference paper at ICLR 2026
(ii) Letting 63 2 [(c), the Lipschitz constant of the second MLP layer is bounded as LMLP, S dj exp(-1 (c.0 (Ine ())), (ce poly log eo (modifying Corollary to ignore the first indices) );
(iii) Letting e2 2 di exp(-0 (Ime-1)3)) the Lipschitz constants of the first at- tention layer are bounded as 1 + L 1. I D (Sp(O(llog(ee) exp (ou
x
(Lemma 9 and I d1):
(iv) We have 61 2 dxp(-0(ca((tmm))))) (o))) (mnt)(/(""))")))""""")"""")""))) for the first MLP layer.
By Lemma
13 and Corollary S
N (,,,,,)) A poly loge
By modifying Corollary 3 to ignore the first indices (corresponding to the query),
log P2, S -((lnet)))e))
By Lemma
10
log N (A(dstta), H1. B Ha,1): o2) z poly(log(c-'dd) d:
By Corollary [
log.N N (F(G,,P,
S poly log log I poly log c- (((log +)+ poly log c1 Ddd).
Assuming that
s di = exp (O((oge)) - and d2 O(1), we have
log (A(dauul, H1, Ba. Ha H),1) (F + log (F(l2, s2) (A 1) 1) 0((mne
In the same vein, obtain the similar result in Theorem 5
Theorem 6. Let F be the empirical risk minimizer whose hypothesis set is constructed in Lemma 17 Assume that
T S di exp(o(log n)) = n o1)
((*) and the target function F* F" (()) x.) is independent of xq (Assumption
In Setting
we have
R(FT F) S exxp(=S((nnn) (I=m)=+t))
Proof. The proof is the same as Theorem
C MINIMAX LOWER BOUND
C. PROOF SKETCH
The goal of this section is to establish an information-theorett minimax lower bound for the asso- ciative recall problem in Setting Our proof strategy consists of two main steps: a reduction to pure cimnite-dimensionall regression task, and the derivation of covering/packing entropy bounds for the corresponding Lipschitz functionals.
Step 1: Reduction from Anfinit--Dimensinn Regression (Appendix regression problem on measures to the associative recall problem. Let
We first reduce
F Lipz,
(Tipp,((HHa (B(Ho, (1x33) Xg dprod),
F Tipr, (B(Ho, ll (1x ). llagg))
where F is the full class of Lipschitz functions depending on both (n, x), and f C F is the subclass depending only on μ..
37

---

Published as a conference paper at ICLR 2026
Here, the key observation is that each can be written average of pushforward measures
(Emb,,o ) (8)
V
I
Therefore, estimating F(Po (8*) 2) with the "noisy" input v is at least as hard as estimating with the "pure" input (6*) Formally, the two observation models differ as follows:
S, = [11, (Iig)s Be) = F ( (xng)))
+ Ec, F*E
U, (1ug ) H)) yr === (1 Ets F"E
That is, under S, we observe outputs of a general Lipschitz function F E E,, whereas under U, the outputs are restricted to the subclass F
Consequently, remembering that F* (v, (16 ,x), the minimax risk satisfies
inf sup Es. (F F P.e..
inf sup (u.lllF(uo)) ('o)))] F F.eF.
In words: the associative recall problem with dataset S, and hypothesis class F is least hard the reduced regression problem with dataset Un and restricted class F This reduction allows us to focus on an infinite-dimensioonal regression setting.
Step 2:
Entropy Bounds for Lipschitz Functionals. The minimax lower bound is based on the [1999; : in short.
general Gaussian regression minimax bound in Yang & Barron
log (E)(TT)) ~ nE² inf R( F) 2 2
where :(F*t)) denotes the e-packing number of the function class with respect to (PP metric. Thus, to obtain a lower bound it suffices to evaluate the packing entropy (i.e., the metric entropy log M (< log the set of Lipschitz functionals G under (P To apply the classical information-theoretiic results, we derive both upper and lower bounds for the covering/packing entropy of the relevant Lipschitz functional class.
STEP 2-1: UPPER BOUND (APPENDIX chitz class,
It known (see Boissard (01TT) that for Lips-
Dog.N(LppA.. d); c) 2 A((A:c)a (poly cogo")) where A is the input set and d is the underlying metrie. Applying this principle, show that
a+1
log C.
|| llage ):c) Mllla* exp (c. log c 1)
Cu < 80.
The proof relies on the following isometric transformation: for Eie bies and parameters a, b, c,
f (a),,c())
bies.
1=1
which is an isometric bijection from (B(Ho: || loeg): ll (1a)) to (B(Ho.) || <llg--+<),, (lagg). We apply this with = 7b. b = ?I, and 0. Then, we employ a standard argument of covering an infiniteddimensionall ellipsoid endowed with e² metric.
The key difficulty is that the Lipschitz constant is anisotropic: differences along low-index directions (small j) are heavily penalized, while directions with larger j effectively much smoother. Formally, for F in our class one has
STEP 2-2: LOWER BOUND (APPENDIX C.4
|F Σ byez) - F F gee) s L R
Σ
x 79 (b, - -3)3
7 < 0,
38

---

Published as a conference paper at ICLR 2026
which clearly shows that directions with larger eigenvalues X, (small j) contribute far more to the Lipschitz bound than those with smaller eigenvalues (large j). In other words, the geometry of the function class is highly distorted across coordinates.
To make this structure explicit, we construct a rescaling map that embeds the standard cube [0, 1]d into measure-inpur space. After rescaling each coordinate according the eigenvalue decay {Ay}. J. a Lipschitz function on [0, 1] becomes a function on B (Ho. Il llxg3)) with Lipschitz constant proportional to
(
This shows that our class contains embedded copy of the d-dimensional Lipschitz ball, up rescaling factor.
Consequently, the packing entropy of our class is least as large as that of Lip; 1] I|e>>) at resolution Re/Aa- (//(t//ta))//2 By combining this rescaling argument with known packing lower bounds for Lipschitz functions on [0, 1] and the Yang-Barron Barron anformation-theorrete inequality, we obtain the desired minimax lower bound for the associative recall problem.
Remark 6. In Setting we assume that the density dyu is nonnegative, which can always be en- sured by adding sufficiently large constant shift. We then relax the additional constraint that μo must be probability measure, and instead only require that dua belongs bounded ball in the ambient function space. This modification does not affect the minimax difficulty the problem, since the essential hardness arises from the diinesioiii of the domain, whereas the nor- malization constraint corresponds merely to a finite-dimmesionnlll restriction.
C.2 STEP 1: REDUCTION FROM
REGRESSION
we will show that the associative recall problem is least as hard as a Gaussian regression problem where the input variables are measures. Remember that standard Gaussian regression problem is defined follows: we observe i.i.d. random variables (X,, Yo)e= such that
By Lemma 21
= (X,) + Ee.
I,..,,,
where are i..d. Gaussian noise, independent of X,. On the other hand, in recall-and -reddicccc problem, the observed input noisy: (4 )igss are mixed v, but they are irrelevant to output y. We will show that we can obtain a better estimator when we "eliminate" the noises in the inputs. Formally, we obtain the following corollary:
Corollary 4. Let
F = LLip, Il 1lx33)) Kgy dproa),
F == Lip Il (lug));l llagz)) )-
Here, F denotes the class of L-Lipschitz functions in both (μ, x), while F denotes the subclass of iutipschiitfuunctions depending only on μ. Note that F. Ft
Consider datasets
Sn = (1r, (Ir))s (c)) W:)
Y: = Fr (6*) (Eg)t)++ + FEF,
U, {116)) Wi 3t F (1())) Exr FFFF
Then, remembering that F (" {^((1( (f)) Izg), we have
sampled as in Setting
inf S,, FETA
sup Es. (v, - (F, x) (1?:))l??((P..)))
F.EF.
inf u. U.-FPEL((P))) F.EF.
sup Eu. (10) F'(N))ll
In words:
the estimation problem with query-depenne dependett target functions at least as hard as the restricted problem where the target depends only on μ. Hence, establishing lower bound for the latter suffices.
To prove Corollary state the following lemma.
39

---

Published as a conference paper at ICLR 2026
Lemma 21, Let Sn {11, Ft; ft, Vi and Sn {116) , It (et,B:))=. be datasets sampled as in
(6")
Definition 1 that
Then, for any estimator F: Sn + F, there exists an estimator F1 : Sn +> F1 such
[s. F" () (V) 2 Rs, (s,
(po, )
Moreover, F independent of the query x, i.e. F (* = F (p), then there exists an estimator F2 depending only on {(1b)) 110) such that
[l. (2o) 2 E (1n5" w.) [1 F7 (xo)
Proof. Remember that
1 7 Σ 1 200
+
Σ (Emb (1)
(2) lid
Pea: (v(0) P..
Mo
We want eliminate the dependency of Ho and ul0 for E [1 M from the original estimator and make a better estimate. We will construct a Bayes-estimated mapping
(6)
x.ag) xxa) + C...T..Fss (v, xa) Po Lgg Sn) = Fi(u)" [xa)] E (.) Sn - 1(40 ((1)),
for Vi (1: 1] {+*} and VI E [1, and Sn This estimator Sn + Fi is well-defined as the mapping from Sn function in I,2 (I because (i) can deterministically construct Sn from Sn and Tn be- cause 1 u 600 (Emb,r,, )=mo and (ii) only has the randomness of the noises (H6 (1) )i given (nD (8") ,,a)). Note that the above estimator does not use the oracle of sam- pling an input/output pair. In short, F1 is not cheating in the context of the standard Gaussian regression: To take the expectation with respect to v/16 (+") and Tn we are additionally observing only the noises of the imput v, which do not exist in the standard Gaussian regression. From now, will explicitly write F Fs.. The loss is lower bounded as
where To = {(00) )e, (o()),
((16") De, (())).11)
(2)
Es. (s, F* (1,xx))(23(B..))
=Es. (F,, (v, Eu,T, [Fs. I ((") ,zg Snl)
+ (Bu,Ta ['ss, (1") [gq Sm1 - ("b (i") a (P
1Il, (V, xia)= Eu,,, [F's 1o
(5*) zq: Sn 3 ...(1)
+ 21,s, | [s,. (V, Ev, T.. [''s
Mu (8)) IIq Sul:
Ev,T, lis. 140 Fgg Sm - f F01(0² (1") , L()))o()))))))
(8")
(ii)
+ Es.. [E, [Fs.. 100) qq 3.1 - F'(((
(8") xxa)) (122)
EEs. Ill (Fi,s, (Mo, xg) F (HO, x.)) (
For the term (i), this is greater than zero. As for (ii), we have
(ii) = Ess, ((ss, xg) Bu.T,[Fs. 110 Zq. Sn),
(1*)
T,, T.. [L'. (3)) 5.q , Sn] - fr ('((bb)
(1) xx xxa) ((
= Es, ET. [ va) -E,TT [Fs. 1o (1") Rq. Snl.
Tu, [s'. (3)) rg. Sn] - p f((16² (1) xxa) (F(enraa) Sn]]
-Es, (BT, PF.. (.) D, 1, S.l Ey, T. IFs.. MD
(1))
zxq S.l.
Tv, T.. [is. 1 (66 xqz Sn] - F'(mb (5) xq)) (F
40

---

Published as a conference paper at ICLR 2026
TT Iss, I MO Fn
) Sn) and Pr (m)()) (8") ,.q) are independent of Tm Sn if S, is given)
-.s.. / {1ʃ
(BT.T (RT,, [És, (u, v. S.l - Bu, [Fs., 1 116 (1") ) Snl)dPP()))
x (Buita ub (t' =.
Sn] ,
F (46 > ,x,)) | (ta))
-Rs.. / 11/ (RT,, [Ps.
(1/(RT..1
(U)(P (v, rng u, uq Snl Bu Fs.. 1ó Bqz S,l ving (w ge) (p) 1)
(f))
no
(Eu, (ss,
Mo (#*) 1 [g. -
xmn)) Fm(("" F
JdlP, (Eg)l
-0.
In the same vein, we can omit the dependence of x. F is independent of zq. We give an estimated mapping as
Hi + Egg (Z [Rs... p ((10 )e. Mt)e
that can be constructed only with the observation ((()')) )e Me).. We omit the details for the second statement.
C.3 STEP 2-1: UPPER-BOUND OF THE ENTROPY
Thanks to Corollary 4 the lower-bound analysis reduces to a Gaussian regression problem in which
the inputs Mo P are generated according to Setting 4 The key step is to control the cov-
ering/packing numbers of the underlying function class so that we can apply the general minimax
bound of Yang & Barron (999)..
Lemma 22 (Yang& & Barron 1199)). Let F = (B(H,, llagg)): ). 1lage) Consider the
dataset Un
{(1b' (T")
)r generated as in Setting 1 Suppose there exist 6, such that
ne? 20
2ne
1ogg logg NFF ;e)= <
log2 M(F*; 80
2 log
x2
Then
inf sup Eu, [ U p.cF-
F 12((2)))
8².
Remark 7. For lower-bound analysis, we adopt the L norm when defining covering and packing numbers.
Goal of this subsection. Lipschitz function class. Specifically, aim to establish upper bound
To apply Lemma 22 we need tight control of the covering entropy of the
log.N [ii,, (
(BoH, ||- (lag)) ). ||x,3
L>((
A lower bound is deferred to Appendix C.4
By proposition B.2 in Boissard (001), the covering entropy of a (1-)Lipschitz class can be con- trolled by the covering entropy of its imput set:
log ())) S N((Ae)) polylog(e=1),
d)
where A the input domain (under some weak assumptions) and d the underlying metrie, Thus, our task reduces to bounding the entropy of the input set A = B(Ho, (lx30) equipped with the metric llage-
To this end, establish an isometric correspondence between balls in weighted Hilbert spaces, which allows us to switch to the standard L metric.
Lemma 23. Let a, b, c R. mapping da.b.oi
f= 1= bes (()+ >,, be:
1=1
is an isometric bijection from (B(Ho, (1llag) Illla)) (B(Ho. Ill -tc), I1lba))
41

---

Published as a conference paper at ICLR 2026
Proof. First, for all f E B(Ho, (1lb))),
())())) Σx Ex b;) b.)² 2 Ex-ett-h Ilffl
This implies that é is isometry and injective. Next, Φ is also a surjection because
bye, E B(Ho: I1lxz)
\ 6
S
3
A -00 (x, bi) 2
e
Σ
X b,e, E B(Ho: Illag vie)
Using the above isometry and eigenvalue decay properties, obtain the following upper bound on the entropy of the input set:
Lemma 24. The covering entropy of B(Ho: Illlag)) endowed with the distance Ill bounded as
upper
log. lBg.N(B(Ho.lll |l 11 )i) $ In(eE))
Proof. By Lemma
letting 7bo b b= Mi 0, it is sufficient to show that
(Ba; S In((e
where Bo = B(H,, |ll (1l We construct a di-dinnnionnal set Ex.
((b1,..,,b,)) b,. bs) E, bie B&} such that, for all E, bies E Bø.
1 L2 4
Σ
6
$2J+11
This can be satisfied if Jc ~ (c (c n)) In - 2/2/aa because Σ5.u.- 5 N3 As. with exponential decay and use X exp(-cja) ). To construct e--oovering on Ej,, we need at most O(1 v (2, (,,-==²²² /c)) patterns for each dimension, so the covering entropy is bounded
log.V()) -
log
J.
7b
ja +
7b - 7f
ja]
7b
7
Jatl
1b
7
(In c -1)0+1//a
c
Finally, results in Boissard (20T and Lemma class.
24
yield the desired entropy bound for the Lipschitz
42

---

Published as a conference paper at ICLR 2026
Lemma 25 (Based on Boissard
2011)). The metric entropy of Lip (B(o, ll 11xx.))) )):ll llxge)
with respect to the Bochner (P no -norm satisfies
(L (la.)) ), (ag O (e E exp
for some Cu O.
o+1 " Proof. By Lemma 24 log log.V(((HHo.) || 11x -1120)): ):0) E In(c=!)"
Then, by Proposition B.2
in Boissard (2011) and e- = exx = o(exp 11) a= for any > 0, we have
log N (Lip, (B(Ho: || |1 ): || ): =ll S exp (cu(Ine a+1
By the inequality / /r (B (1l1,3)) )) Iloo 2 (12(( and /PIs (B(Ho. (B ll (1233)) 1,
we obtain the desired bound.
C.4 STEP 2-2: LOWER BOUND OF THE ENTROPY
To apply the general minimax bound in Lemma 22 We will provide the lower bound the infinite- dimensional lipschitz class.
The main difficulty lies in the anisotropic nature of the Lipschitz constant: for F in our class, one has
F bye, b - F cee,) S L / (b,
0,
which implies that the functional is significantly smoother directions corresponding to high-index coefficients eg. To capture this effect, construct the following embedding:
La ::<((0,1])) L'(HH)),
(Lag)(fa) = =s(0) (1
fu
In.d
Ya/2
where
X70l3 Zalz dy(x) [x(2) (2)dd;; dx,
Sw
j=1
with independent coefficients _ (u)du.
Zj ~ Pj and cumulative distribution functions 2,(x)
We prove that
4 ([, (J)) c Lip 2/1 (B(Ho. 1117Ho-1--1a00 -lago)): Illl (lage) )
and hence obtain packing lower bound
log M(Lip, (B(Ho, (B(Ho, ll (lag))); llag:):)) ):+) 2 log M Lip, (10, 1] I1 [1e==); x Tel Thana
Rr
LP Combining this rescaling argument with standard Lipschitz-packing lower bounds and the information-theoretiic results of Kang-Barron yields the desired minimax lower bound for the as- sociative recall problem.
First, we construct an embedding ld- This construction suggests that, after suitable rescaling of coordinates, functions on [0. 1]d can be embedded isometrically into our measure-input space. The next lemma formalizes this embedding and quantifies how the Lipschitz constant is rescaled.
Lemma 26 (An extension Lanthaler (2024)). Let IP be a probability measure on BHH, I1-I1x;))
in Setting i For any E 20) and d E N, there exists an isometric embedding
La [P( 174) + IP(PP)))
such that ia (Tipp (10, 1]4; IIloo)) C Lippyo/-nctaaa (B(Ho.
(B( || (1 ), ll }), where the Lips-
chitz norm (0, 1]d is defined with respect the co-norm [0, 1]d.
43

---

Published as a conference paper at ICLR 2026
Proof. By Assumption 8 μ Pyo is sampled as
du ax
f = Σ x Zzej.
fp.
where Zj.j 2 are independent and Zj ~ Pj (z) We define the cumulative distribution 2y(2) = S Pjdz. know that F3 Lipschitz, whose Lipschitz constant is bounded by sup, I|oilloo S R. We define fμ.i = (Sar ex). We will show that the mapping
7d )........ )...., D Dalsma/>i))
La (10, 11+)= + mo) (fa
the isometric embedding that we want. For g E ("0 11 the LP(P -norm of tag is equal to
(1,,((4)))())) E5, ,...., Dalfmma )) 1 (2)) Pa (a))
(2,(2,) Unif[o, 1J)
Jo.jaa
| | (0.,.))
which shows that La is isometric embedding. Next, evaluate the image of Ld. A mapping
has (B(Ha, ll (1xa)); II (lxg)) (10, (1lbo)), SN (0:(/1A))))) DalSnd//
lipschitz because
(ha(fpr) ha(fmz)lle
| (fmim /1,²) - -D }
max
Lip(O,), 7 1mms Snaoly
max
Lip(0,) M1 v 21 Ifuni Smarly
max )
max
Lip(#,) ), 11,=²²
2
Σ (Ag 2
Ifris frail)
and thus
Lip(ha) <
-orthna
Therefore, Vg e Lip, ((0, []4, oo), Lipschitz constant of lag is bounded as Lip(eag) Lip(g ha) S Lip(g) Lip(ha)
R
A
Furthermore, we also have ||all C(B(Ho.lll S
Lemma 26 ensures that the Lipschitz class on [0, 1]d can be viewed as subclass of our infinite- dimensional Lipschitz class, up scaling factor depending on Aa- This immediately yields lower bound on the packing numbers of our class in terms of the well-studied packing numbers of Lip,((0 1)
Corollary 5. Under the assumptions of Lemma 26 we have
Rs -x4
log ([Lip (B(Ho, (1:1l ( log M (10, 114, Illloo,
X
LP((0.14))
44

---

Published as a conference paper at ICLR 2026
Proof. By rescaling the function, we have
(B || 11xx0) ), (l (;r)
Re
=M
Lip Lipp/(25 Tel m (B(Ho, II 11 (el.):111lxxt)) (2 (2/ Lo
Re
2M
(10,
(A) (16artaa)/3)
D
Rc
ZM
Lip, (1o);(0))
(2/ (2
L.((0114)
Thus, the problem of estimating the packing entropy of the of estimating the entropy of diiee-dimensionll Lipschitz functions on the cube. Fortunately, sharp lower bounds for the latter available in the literature. Note that packing and covering are almost equivalent when c - O.
class reduces to that
Lemma 27 (Lanthaler 2024)). Forp p E [1, oo) and E N, there exists a constant c > >0 independent of d such that
log M(Lip, (10, 114, (ll I) Z de (2)).
Ve E c0,c/d]
Combining the embedding argument with the finie-ddimensional lower bounds above, we arrive at the following result, which provides the desired exponential lower bound on the entropy growth.
Lemma 28 (Parallel to Lanthaler (2024)). Let Pno be probability measure on B(Ho, || llags)
Setting The packing entropy of Lip, (B(Ho.ll 12 ), (lgge) with respect to the Bochner (P no norrm, satisfies
log (B(H), (lag)))) ).l 11 ), ()3()))) Z exp (c((In
for some constant 0.
Proof. Combining Corollary 5 and Lemma 27
a1 xaaaa d
log M(Li,, (B(Ho: |l 11x3> ), llag ), 2
ad 72tt Then, by da 2 exp(-cdd) cdd the RHS is lower
where 0 >> is constant, provided bounded by
(log M 2) c1 (xpp((ddd))
if expl exp(-ddd)
de
where c' ta) and C2 > 0 is another constant. Assuming that is sufficiently small, let us
take as
1/a
d = log((e CZE d' +1
1)
(= (Ine (1)11))
By rearranging the above inequality, we also obtain
= 02 exp(- 1)d"),
which can satisfy e S exd-lexp(-edddl asymptotically, because exp(-d") dd where d (Ine- 1/1//o - oo as - Then, we have
log M(Lip, (B(Ho, l| 1l ). -1ll1l c)
45

---

Published as a conference paper at ICLR 2026
9 expp(-ddd))
2V
de
(exp (-cd + (c' + 1)dd - Ind 0(1)))
exp (1((ct)))))
2V exp (1(((n)))))*
where we used da = In in the fourth inequality.
C.5 PROOF OF MINIMAX LOWER BOUND
Theorem (Minimax Lower Bound). Under Setting
we have
inf sup Es., [I 125FF111 (1F-FI((2(00))) z exp (xp(((((nnnoot)) S.+ FtEF
Proof. By Lemma 21 it is sufficient to evaluate
inf PE po) FrE
sup (n, F
where Un ((1))) ,)}r sampled as in Setting instead of the original problem. Let
V(Ex) = (B(Ho, || (lagg)) Illag )² and M (6,) = log (BLL,,(((((Ho... llago)) Illaag));
First, let en C1 exp( (cnnn) where cE
Then, by Lemma
2c
V(Gr))
eexp ca (loge ", Til 2cg (In aी
2
exxp
Ca (c((c((nn))tt
)ो)) ديا + 2c
exp
Inn + +((In))att)
2
n
02
Note that
@(1).
Next,
we lower bound the packing entropy.
Taking 6n
Co exp( -a (In (o)nn)))i) ~+)) where G - and C. oz + 2log2 is sufficiently large constant
2
1
only dependent of O(1), using Lemma 28
(ō.) 2 exp (alea "
a+1 mn) + ((Inn)air)
2 02
2log 2
( 2 0²
2 2 2
+
Finally, applying Lemma 22 have
inf sup B B[1Í-- Fl2aa]
2 o8 ž exp (-0(An
S PET
D SYNTHETIC EXPERIMENT ON MEASURE- VALUED ATTENTION
To provide a minimal empirical sanity check of our risk bounds, we design simple synthetic ex- periment where the input is measure-valued context on [0, 1] x {-1, +1, and the model is single MLP- Atteenttnnn MMMiiinnn-MLPP MMP block. The goal is to recover a scalar functional of an underlying "associative" measure from mixture of associative and non-associative components.
46

---

Published as a conference paper at ICLR 2026
Data-generating process. Fix truncation level M 16 I and orthonormal trigonometric basis on [0, 1],
60(x) = 1, ()(z) = 2 sij)
j j I...,,MM -
For smoothness parameter > 0 we define eigenvalues
' = cxp(-j"))
j= .M 1.
For each training example we sample two sets of coefficients 71, Zz N(0, IM1)) independently, Z0 Z2,0 = 0, and form the (unnormalized) densities on [0, 1]
M-1
(x(x) = Σ
N Zr. (z()),
k E (1,2}.
1=0
We discretize [0, 1] on uniform grid { T 32, clamp the density to be nonnegative, and normalize to obtain a probability mass function (px (t))
(t) = (xx)
Faw (2,)
ir (z+),
(x,) = max Faw (x.).E). (x))
Σxm uy (15))
with small cutoff 8
Independently, sample a "query label" y1(1) 1-1,+1 +1} uniformly and set v(2) == -2(1), We
then define a product-measure mixture on [0, 1] x 1 +1 by
( @ 5,0)) + 2 (w2 3 6,
where μr the discrete measure assigning mass pı (4) to Vt. To construct the input token sequence, we draw Ylnkenns 5000 i.i.d. Monte Carlo samples (X, Qi)
(IT, v(!), with prob. 2' Tj P1:
(X, V.)
(IT,, 0 ( with prob. 21 T2 ~ P2:
Ptokens
Finally, we append a single "query token" (0, 2()) at the end of the sequence, that each input example is a sequence
{X,, Vi) V
Rrokems U ((0, (()) E (10, 1] x {-1, Ptokenst1
The target output Y depends only the associative measure l4 (and is independent of #2 and v(2)):
M-1
Y FM Iasoknns +1
(1)).
query
Intuitively, the model must the final query token (0, o(1) to attend to tokens consistent with q and recover information about the hidden coefficients Z1 from Monte Carlo samples of μl. Note that we add small Gaussian noise with std 0.01 in training.
Model and training. operator:
We use a minimal architecture that mirrors the theoretical measure-attention
context/query MLP measure attention MLP HEAD.
For each example we construct a sequence of Taxx context tokens (xz, v&) E R2 together with a final query token (0, Uq J. The context tokens and the query token are embedded by separate two-layer MLPs into Rduoded with dmooeel* 8 and hidden width dhidden 8. The resulting query embedding provides the Q vector, while the context embeddings provide the K and V vectors for a single 4- head softmax attention layer. This imeasure-attentionn layer outputs single -mnod--dimeesional representation, which is fed into a final two-layer MLP head produce the scalar prediction Y. We train with the squared loss ((Y,Y) = (Y Y)² using Adam with an exponentially decaying learning rate for 20 epochs.
For each E {ai...., } we generate independent training sets of sizes E {Maiin ..... Mmnax ( (n 2 for k = 2,...,6) 6) and measure the empirical risk L(n) on held-out validation set (Nval = 2000).
In theory, did explicitly investigated such cutoff the normalization for simplicity.
47

---

Published as a conference paper at ICLR 2026
Empirical Risk for the Synthetic Experiment
alpha-0.75
a-0.75, C-3.36
alpha=1.0
10-1
a=10, C=2.25
MSE (log)
10a
n trarin (log)
Figure 4: Empirical risk L(n) for the synthetic measure-valued experiment, plotted on transformed axis (log m))/(a+1) together with the fitted curves. Each risk was calculated with 2000 unknown samples.
Risk scaling.
Theory predicts that in this setting the minimax risk decays
(n) ~ exp( - (log (logg))//aer) )
up to multiplicative constants. To compare with this prediction, for each a we fit the parametric
form
log L(n) x Aa - Ca (logn) a/(a+1)
(logn)a/(att))
by least squares over (Aa: Ca) using the measured pairs ((log n,, log L(n))), Figure shows
log L(n) against (logn)"//on n))/((++) together with the fitted curves.
As minimal sanity check, this synthetic experiment (Fig. 4 in which varying the spectral decay parameter a systematically affects the convergence speed: heavier-tailed spectra (smaller a) lead to visibly slower decay of the empirical risk. This is qualitatively consistent with the theoretical prediction, although we do not attempt to match the precise asymptotic rate.
Attention-weight analysis. To check whether the attention layer actually uses the query tag, we inspect the softmax attention weights of the trained model on the validation set. For given example, let
((X,, Vi) (10. 1] x (-1,+13)
denote the T context tokens, and let
(X Vo) = (0, (1))
be the query token appended at the end of the sequence. For each attention head h 1,..., H write
(b) E 10
for the softmax attention weights from the query to the 7 context positions, so that
T
We are interested in how the query token redistributes its attention mass over tokens whose tag matches the query versus those with the opposite tag. Accordingly, we define the index sets
Seame (1515T: =V).
Vg).
Sant (1 1 T V VaJ.
48

---

Published as a conference paper at ICLR 2026
that is, we only consider the context tokens and exclude the query token itself from both sets. For each head h we then compute the average per-token attention weight assigned by the query to same- tag and different-tag tokens,
W
samee
(h)
|Saamel
at
at:
W Wdiff
Sann
DE Srame
IESai
as well as the total attention mass
Σ LESexme
(I))
(b) maiif
Σ
(K) at
M same
EE
In practice, we implement this by adding flag the attention module that, when enabled, stores the last softmax attention tensor A E I Bxxxxxx2 on the CPU after a forward pass (where the batch size), and we extract (*) as the length-T vector As, corresponding to the query-to-comee weights for each example b and head h.
(h) We report in Table | the mean and standard deviation of Msamm and mair over 1000 validation exam- ples for each attention head h. On this synthetic task, two of the four heads concentrate essentially all of their attention mass on tokens whose tag matches the query tag, while another head exhibits the opposite preference and one head remains nearly symmetric. Averaged across heads, the query token assigns a larger total mass to tokens with the same tag than to those with the opposite tag, indicating a net bias toward tag-conditioned retrieval.
(h)
The absolute scale of the averaged weights Usame and Waiff is small (on the order of 10-4) simply because the attention distribution is normalized over a long context of Totx ~ Ptokens = 5000 positions. Under an approximately uniform baseline, we would have
~ 2 10
Wunif
Tetx
5000
so the reported values should be interpreted relative to this 1/Toxx scale rather than as absolute probabilities. In our construction, each context token independently comes from fi & or μl @ 6,t: with probability 1/2, so typically |Ssamel = |Sarl ~ Tetx/2. Consequently, values around 2 10 correspond to almost-uniform attention over all context tokens, whereas values around Wsame 2 4 10-1 and Wai R O indicate that head places essentially all of its attention mass on the same-tag subset (and analogously for the opposite tag).
As sanity check that the model genuinely uses the query input, we perform a "query shuffle" exper- iment at evaluation time: within each mini-batch we randomly permute the last (query) token across examples, while keeping the context tokens and targets fixed, and recompute the validation loss (the bottom of Table MT. On this synthetic task, shuffling the query tokens increases the validation MSE, confirming that the model relies nontrivially the query input.
This minimal experiment is not intended as a thorough empirical study, but it provides a sanity check that the qualitative order of the risk predicted by our theory is reproducible in a simple measure- valued attention setting.
49

---

Published as a conference paper at ICLR 2026
Table 1: Average attention weight from the query token to same-tag different-tag context tokens (mean and standard deviation over 1000 validation examples, with 64 training data and a = 1.0). With Tetx 5000 and roughly half of the tokens sharing the query tag. the uniform baseline is T ~ 2 x 10 while head that focuses almost exclusively on same-tag tokens reaches wamee & 10-4 We also report the validation MSE with the original queries and after shuffling queries within 1000 data for validation.
Head
Wsame
Waif
std(Waam
sld(wair)
1.96 10-1
2.04 10-1
2.80
10-4
2.85 10-4 1
1.44 x 10-19
4.00 x 10-1
2.10 x 10-19
4.00 10-1
4.00 10
1.17 x 10 14
4.00 x 10
1.70 x 10-14 14
4.00 10-4
2.86 x 10 27
4.00 10-4
(too small)
mean
2.49 x 10
1.51 x 10-4 2.70 x 10 1.71 x 10
original queries
shuffled queries
val MSE
1.44 10-2
7.75 10-1
50


Reviews:
[{"review_id": "sq2uj3QxSE", "reviewer": "Reviewer_rkiJ", "summary": "The paper attempts to study the associative memory problem theoretically. It formulates the \"context\" to a transformer as a mixture of measures.  The goal of the transformer is, on reading a query corresponding to one of these constituent measures, to identify the associated measure.", "questions": "1. Why this choice of eigenvalue decay (lambda_j = exp(-c j^alpha))?  This seems rather arbitrary and I do not see any justification/explanation for it.  More importantly, this alpha is crucial and shows up in the final results, making them very fragile (not robust to this assumption).\n\n2. Example 1 lists some examples satisfying the assumptions, but it is not clear if these examples satisfy all or some subset of the assumptions, and whether these examples are interesting for the setup being considered (e.g., one could list any arbitrary assumption and say that there are functions satisfying that assumption, but whether it makes sense to consider that example for that setup is important).  Comments?\n\nMinor comments:\n1. Equation at line 211: should be F, not F^\\star\n2.  Section 3.2, one of the expressions for either SAttn or MSAttn must be wrong: both have a V^h x at the end, and MSAttn does not have a W^h  (guessing that SAttn is right and MSAttn has W instead of V)?\n3. Definition 5, the equation: what is nu_1, did you mean mu_1?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "The paper attempts a theoretical analysis of a practically relevant setup in transformers, which is always welcome and appreciated.  It presents matching upper and lower bounds to the risk of a statistical estimation problem that they pose as a proxy to the associative memory problem.", "weaknesses": "The biggest issue of this paper is that the mathematical notation is (a) far too dense for a conference such as ICLR, and (b) just poor, objectively (there are too many to list, but see Questions for a few).  At a high level, the paper reads as follows to me: the paper spend 7 pages (!) setting up notation and making several assumptions (some of which, admittedly, do seem reasonable, but, e.g., the eigenvalue decay rate, just show up out of nowhere) and then obtains some results that likely do not hold if any of the assumptions are violated even slightly (e.g., if the eigenvalue decay rate is different).  \n\nIs there really a need for the entire paper to be measure-theoretic?  What would be different if we just assumed these were just a linear combinations \"discrete distributions\" of some finite set and then went with it?  The insistence on measure theory and functional-analytic analysis makes the paper very specialized, so if it could be simplified at all, it would be greatly appreciated (I understand that often we do actually require this level of sophistication to analyze some setups, but this setup feels like a more interesting analysis could be made with simpler mathematics).\n\nWhat exactly is the statistical estimation problem introduced in Section 3?  As far as I understand, it is an abstraction of the memory recall problem (I might be wrong, but this is what I understood from the paper).  In this case, what exactly is the value of such an abstraction and analysis?  I do not think there is value in knowing at exactly what rate it decays, given that the problem itself is a \"fake\" problem invented only a a proxy.  I think there would be value if the paper were able to provide insights/explain some curious phenomena on the general problem of associate memory and recall, but I do not see any such insights.", "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": "CFUomIZaYr", "reviewer": "Reviewer_wjf3", "summary": "The paper develops a measure-theoretic view of Transformers for \nassociative recall.\nInstead of treating a context as a finite token sequence, the input is a \nmixture of probability measures over tokens; a query identifies the \nrelevant component measure (recall), and the predictor maps that \nrecalled measure (plus the query) to an output (predict).\nTechnically, attention is lifted to an integral operator on measures, so \nsums over tokens become integrals.\nUnder a spectral assumption, i.e. Mercer eigenvalues of the RKHS\nkernel decay exponentially, the authors construct a shallow (depth-2) \nTransformer+MLP and prove a sub-polynomial excess-risk bound of the \nform\n$\\exp\\{-\\Theta((\\log n)^{\\alpha/(\\alpha+1)})\\}$ for ERM, and provide a \nmatching minimax lower bound (same exponent, up to constants).\nThey argue learned softmax attention can implement near one-hot, \nquery-adaptive recall that isolates the correct component measure and \naggregates a small set of its Mercer coefficients for prediction.", "questions": "Polynomial spectra. Can you extend (even heuristically) the analysis to \nkernels with polynomial eigen-decay? Which proof steps break and what \nrates would you expect?\n\nQuery robustness. What happens if $x_q$ does explicitly contain \n$v^{(i^\\*)}$ or if the tags are weakly separated/noisy? Can the softmax \ngate still become sufficiently spiky under ERM?\n\nEmpirics. Could you add synthetic experiments varying $\\alpha$ and \n$I$, and compare learned softmax vs. linear attention / frozen kernels, to \nillustrate the theory?\n\ntypos:\n- line 179 repeats line 176\n- line 180: \\Chi_0 not defined\n- line 211: inside the argmin should be F? Same in line 214", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "To the extent of my understanding, which is limited, the modeling of contexts as probability distributions seems an interesting line of research, with several other recent papers treating it.", "weaknesses": "Clarity:\nI found the paper extremely hard to parse (which may be my fault, and not a weakness, I let the area chair judge). For example:\n- line 73: it is not clear what is meant by \"context\"\n- line 74: it is not clear on which space do the measuere nu, mu^(i) live in\n- line 75: it is not clear which space the query x_q lives in\n- line 76: what is the \"target map\". Is it some sort of ground-truth function? This should be defined clearly\n- etc...\nWhile stated as \"informal\", I find this introductory section quite confusing.\nThe paragraph in line 149-167 is not illuminating either on this, and one needs to reach line 169 to finally know what are the objects we are speaking about.\nWhile the paragraph starting at line 169 provides definition, they are hard to understand: I would suggest providing examples here!\n\nMore generally, important intuitions (effective dimension $(\\log n)^{1/(1+\\alpha)}$, role of the second attention block, sensitivity to query–key geometry) are \nscattered across sections and appendices, hampering readability for a \nbroader audience.\n\nModel:\nThe query explicitly contains the relevant tag $v^{(i^\\*)}$ and the tags \nare well-separated (inner products $\\le 0$), making recall potentially substantially \neasier than in natural setting.\n \nLack of any empirical validation:\nThe work is purely theoretical. Even small \nsynthetic experiments would help test the sharpness/spikiness of learned \nsoftmax and test the assumptions (e.g., performance deterioration \nwhen spectra are polynomial).", "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": "D2Gz1Zm6ZE", "reviewer": "Reviewer_coHc", "summary": "In the paper, the authors cast associative memory in transformers as a problem in retrieving the correct component from a mixture distribution via querying. The authors show that a (measure-theoretic) transformer trained on empirical risk minimization is able to implement via an approximately one-hot softmax the optimal target function with sub-polynomial rate.", "questions": "1.Do you think that this work could be relevant and practically useful for the community in any way? More specifically, why do you think that an infinite-dimensional context in the form of a mixture distribution can be meaningful in practice?\n2. The assumptions are not discussed extensively and they seem quite strict. In the conclusion you mention the possibility to extend your results to broader regimes such as polynomial instead of exponential regimes. What is currently the main difficulty in carrying out such a generalization?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors carry out a sophisticated theoretical analysis of the problem. Particularly nice is the tight characterization of the excess-risk rate. Despite the complex nature of the work, the paper is relatively well written and organized. I especially like that the authors reserved some space to give a quick proof sketch for theorems in the main body. The proofs seem reasonable, even though I could not check the appendix in detail.", "weaknesses": "The limit of the work is obviously the lack of clear practical implications, being a purely theoretical work. The lack of experimental results is also a consequence of the same fact. Nonetheless, the results are interesting and a worthy theoretical contribution.\n\nOn the minor side:\n1. Lines 176-177 are repeated at lines 178-179;\n2. The definition at line 211 is confusing: there is no F in the argument;\n3. I would take a little space to explain what RKHS in Sec. 3.1.1;\n4. There is an extra \"that\" at line 406.", "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)