Transformers are Universal In-context Learners

🎯 Pitch

A single transformer with fixed embedding dimension can approximate any continuous in-context mapping uniformly over an infinite number of tokens, shattering previous beliefs that model capacity must scale with context length. This universal approximation is proven for both vision (unmasked) and NLP (causal) architectures by reformulating attention as operating on probability measures, though causal settings require a Lipschitz-in-time condition that the authors prove is both intrinsic to transformers and strictly necessary.

1. Executive Summary

This paper provides a rigorous mathematical proof that deep transformers are universal in-context learners—architectures that can approximate any continuous in-context mapping to arbitrary precision, uniformly over compact token domains. The authors formalize transformers as operating over probability distributions of tokens rather than finite sets, defining continuity through the Wasserstein distance between contexts, and demonstrate that a fixed transformer (with embedding dimension and number of heads independent of precision) can handle an arbitrarily large—even infinite—number of input tokens. The core mechanism is a measure-theoretic in-context mapping (reformulating attention layers as functions Γθ(μ, x) that map a probability measure of context tokens and an individual token to an output, with composition rules enabling deep architectures), applied in both unmasked bidirectional settings (vision transformers, where permutation equivariance permits direct measure-theoretic treatment) and masked causal settings (NLP transformers, where a space-time lifting to ℝ^din × [0,1] restores the required invariance). The proof establishes universal approximation via the Stone-Weierstrass theorem applied to an algebra of "cylindrical functions" built from elementary single-head attention operations, requiring embedding dimension d + 3d' and head count proportional to output dimension d', independent of the approximation error ε. A key structural finding is that the masked setting requires an additional Lipschitz context hypothesis (the conditional token distribution μ(·|t) must be Lipschitz in time under the Wasserstein-2 distance) and an identifiability condition on the target mapping—constraints that are provably sharp since transformers themselves intrinsically satisfy them, establishing that causal transformers can only uniformly approximate maps that respect these same causality-induced regularities.

2. Context and Motivation

The Core Problem: We Lack a Unified Theory of Transformer Expressivity for Arbitrary Context Lengths

The fundamental question this paper tackles is deceptively simple: can a single transformer architecture, with fixed internal dimensions, represent any continuous in-context computation on contexts of arbitrary length? This is the universality question — the transformer analog of what Cybenko (1989) and Hornik et al. (1989) established for multilayer perceptrons: that two-layer MLPs can approximate any continuous function on compact domains. For transformers, however, the problem is substantially more subtle because the mapping is not between fixed-dimensional vector spaces but between sets of vectors (tokens) — sets whose cardinality can vary from one prompt to the next, and can in principle be arbitrarily large.

To make this concrete, consider what happens when a vision transformer processes an image: it receives a set of image patches, computes interactions between them through self-attention, and produces a transformed set of tokens. The number of patches depends on the image resolution. When a language model processes a prompt, it conditions on all preceding tokens to predict the next one. The prompt length can vary from a few tokens to hundreds of thousands. In both cases, the transformer defines an in-context mapping — a function G(X, x) that produces an output for a given token x that depends on the entire context X = (x_1, ..., x_n) of other tokens. Crucially, the same transformer parameters must work for n = 10, n = 1000, and n = 10^6 tokens.

The expressivity question is: given any desired in-context computation (subject to appropriate continuity conditions), does there exist some transformer that approximates it well, uniformly over all possible context sizes? Prior to this work, the answer was incompletely understood. Existing universality results either required the embedding dimension to grow with the number of tokens (Yun et al., 2019; Alberti et al., 2023), imposed structural modifications to the transformer architecture that deviate from practical implementations, or operated under restrictive assumptions that prevented a unified treatment across the unmasked (bidirectional) and masked (causal) settings.

This gap matters for several reasons:

Theoretical foundations: Without a universality theorem, we cannot be confident that the transformer architecture is capable in principle of representing the computations that training procedures empirically discover. Universality provides a completeness guarantee: the architecture is not a bottleneck.
Architecture design: Understanding what dimensions are necessary for universality (embedding dimension, number of heads, depth versus width tradeoffs) informs practical design choices. If universality required embedding dimension to scale with context length, that would be a fundamental limitation — but this paper shows it does not.
Mean-field limits: The probability measure formulation enables handling the limit of infinite tokens, which is relevant both for theoretical analysis of scaling behavior and for understanding transformers that process continuous signals (e.g., as neural operators for PDEs).
Separating causal from unmasked settings: The paper provides the first rigorous characterization of why causal (masked) attention imposes additional regularity requirements on the class of approximable functions. This is not just a technicality — it has architectural implications for what causal transformers can express.

Conflicting and Incomplete Prior Results

The literature on transformer expressivity is fragmented, with different works making different structural assumptions and reaching conclusions that are difficult to compare. The paper situates itself relative to several lines of prior work:

Approximation results with dimension growth (Yun et al., 2019; Alberti et al., 2023). The most directly comparable prior result is Yun et al. (2019), who proved that shallow transformers (with only 2 heads) are universal approximators of sequence-to-sequence functions. However, their construction requires the embedding dimension to grow with the number of tokens — specifically, the internal representation must be at least n-dimensional to handle n tokens. This is a significant limitation because practical transformers use a fixed embedding dimension regardless of context length. The paper frames this as motivating a different approach:

"Our focus is different, since we consider deep transformers with a fixed embedding dimension, but which are universal for an arbitrary number of tokens."

Similarly, Alberti et al. (2023) proposed the Sumformer architecture — a variant transformer with summation-based aggregation — and proved its universality, but again requiring an embedding dimension that grows with token count. The current paper distinguishes itself by working with standard transformer architectures (multi-head attention plus MLPs) with fixed dimensions independent of both context size and approximation precision.

Discrete/combinatorial expressivity results. A separate line of work analyzes transformers through the lens of formal language theory, studying what classes of formal languages or Turing-computable functions they can recognize when operating on discrete token sequences (Chiang et al., 2023; Merrill and Sabharwal, 2023; Strobl et al., 2024). While important for understanding transformers as computational models, this line of work fundamentally differs from the current paper: it treats tokens as discrete symbols and studies exact representation of combinatorial structures, while the current paper treats tokens as continuous vectors and studies approximate representation of smooth in-context mappings. The paper briefly acknowledges this work as "not directly related to our results" (Section 1).

In-context learning as algorithm implementation. Another line of work studies how trained transformers can implement specific algorithms through in-context computation — gradient descent (Ahn et al., 2024; Mahankali et al., 2023; Zhang et al., 2024; Sander et al., 2024) or mesa-optimization (von Oswald et al., 2023). These works typically operate on simplified linear attention architectures or specific data generation processes. While they provide mechanistic insights into what transformers learn to do, they do not address the general question of what transformers can represent.

Measure-theoretic formulations of attention (Sander et al., 2022; Vuckovic et al., 2020; Castin et al., 2024). The current paper builds on a line of work that reinterprets attention as operating over probability measures rather than finite sets. Sander et al. (2022) introduced Sinkformers — transformers where attention is constrained to be doubly stochastic — and analyzed them through a measure-theoretic lens. Vuckovic et al. (2020) developed a mathematical theory of attention as minimizing a free energy functional over probability distributions. Castin et al. (2024) analyzed the Lipschitz continuity of attention layers with respect to optimal transport distances between token measures. The current paper adopts this measure-theoretic perspective but redirects it toward the universality question: rather than studying properties of a given attention map (smoothness, convergence), it asks whether compositions of attention maps can approximate arbitrary continuous maps.

Graph neural network and equivariant network universality. There are conceptual connections to universality results for permutation-equivariant architectures, including graph neural networks (Keriven and Peyré, 2019) and set-based neural networks (Qi et al., 2017; De Bie et al., 2019). The fundamental challenge in these settings is that the architecture must process variable-sized inputs while respecting permutation invariance or equivariance. The transformer's unmasked attention is permutation-equivariant, making it an instance of this broader class. The paper briefly acknowledges these connections but distinguishes its focus on operating over probability distributions rather than sets:

"Here, we take a different point of view, with transformers operating on probability distributions rather than on sets of points."

Neural operator universality. A closely related line of work is the theory of neural operators (Kovachki et al., 2023) — architectures that learn mappings between infinite-dimensional function spaces, with universality results by Furuya et al. (2023) and others. The current paper's measure-theoretic attention formulation is conceptually analogous: both treat the input as an infinite-dimensional object (a probability measure for transformers, a function for neural operators) and compose finite-dimensional operations to approximate infinite-dimensional mappings. The paper explicitly cites this connection and notes that neural operators can be generalized to metric spaces (Kratsios et al., 2023).

The Specific Gap: Uniform Approximation on Arbitrary-Size Contexts Without Dimension Growth

Synthesizing these lines of work, the precise gap the paper addresses is:

No existing result establishes that standard transformer architectures with fixed embedding dimensions (independent of both token count and approximation error) are universal approximators of continuous in-context mappings on contexts of arbitrary cardinality.

The challenges are threefold:

Handling varying cardinality. A traditional universality proof for functions on ℝ^d (like the MLP results) relies on the input space being a single fixed-dimensional vector space. For transformers, the input is a set of vectors — the number of vectors varies, so what is the correct topological structure to define continuity and compactness? The paper's answer: probability measures under the weak* topology, metrized by the Wasserstein distance (Section 2.2).
Maintaining embeddable function classes. To prove density of transformer-like functions in the space of all continuous in-context mappings, one must construct an algebra of "elementary" functions — each realizable by a single attention head — that separates points and is closed under addition and multiplication, satisfying the Stone-Weierstrass theorem's hypotheses. The paper identifies a specific parameterization (Equation 14) involving exponential kernels and proves it defines such an algebra (Proposition 1).
The causal constraint. Masked (causal) attention is not permutation-equivariant because future tokens are inaccessible. This breaks the "symmetrized" measure-theoretic formulation that works for unmasked attention. The prior literature had no general approach to this: how do you define a topology and function class such that causal transformers are dense in the space of causal in-context mappings? The paper solves this through a space-time lifting (Section 2.3), embedding tokens into Ω × [0,1] and defining Lipschitz contexts and identifiability as regularity conditions that causal transformers intrinsically satisfy.

Why These Constraints (Lipschitz Contexts, Identifiability) Are Not Ad Hoc

A crucial motivation for the masked-case analysis is that the additional hypotheses — Lipschitz contexts (μ(·|t) is C-Lipschitz in t under W_2) and identifiability (μ_t = μ_{t'} implies equality of the output maps at those times) — are not arbitrary technical impositions. They emerge naturally from what causal transformers themselves satisfy:

Lipschitz contexts are automatically satisfied by any discrete measure with distinct time positions (using C = Radius(Ω)/δ where δ = min|t_i - t_j|), making the condition non-restrictive for practical finite-token settings. The condition is needed only to ensure the space of masked contexts X_C^σ is compact for the Stone-Weierstrass theorem — a purely technical requirement rather than a limitation on the class of functions a transformer could represent in practice.
Identifiability is more subtle and profound. Lemma 11 proves that masked attention maps Γ_θ are identifiable: if two contexts have the same masked measure μ_t = μ_{t'} (the same tokens up to time t), then Γ_θ(μ_t, ·, t) = Γ_θ(μ_{t'}, ·, t'). Lemma 13 proves a stability result: the uniform limit of identifiable maps is identifiable. This means a causal transformer can only uniformly approximate maps that are themselves identifiable — identifiability is a sharp necessary condition for uniform approximability. The paper's Theorem 2 thus achieves both sufficiency (transformers can approximate all continuous, causal, identifiable maps) and a form of necessity (they cannot uniformly approximate non-identifiable maps), making the characterization tight.

The Measure-Theoretic Framing as a Conceptual Innovation

Beyond the universality theorem itself, the paper's measure-theoretic formalization of in-context mappings (Section 2) is a significant conceptual contribution that reframes how transformers should be understood mathematically. The standard view — transformers process sequences of vectors — obscures two important structural properties:

Permutation equivariance (in the unmasked case). Rewriting attention as Γ_θ(μ, x) in Equation (9), where μ = (1/n) Σ δ_{x_i} encodes a set of tokens as a probability measure, makes permutation invariance explicit: μ does not order its support. This connects transformers to DeepSets, PointNet, and the broader theory of permutation-invariant/equivariant architectures.
Composition through pushforward. Section 2.2 shows that composing two attention layers corresponds to pushing the measure forward through the first layer's output map before feeding it to the second: (Γ_2 ⋄ Γ_1)(μ, x) = Γ_2(μ_1, Γ_1(μ, x)) where μ_1 = Γ_1(μ)_♯μ. This composition rule (Equation 10) cleanly separates the "context update" (the pushforward, which transforms all tokens) from the "query update" (applying the in-context function to the specific token x). It reveals that a deep transformer is fundamentally a coupled particle system: each layer displaces all token positions, and subsequent layers operate on the displaced configuration.
The universal in-context mapping property. The core claim of Theorem 1 is that a composition of such pushforward-and-query operations can approximate any continuous function of the form (μ, x) ↦ Λ*(μ, x) — a much richer class than the "sequence-to-sequence" maps studied in prior work, because μ is an infinite-dimensional input (a probability distribution) rather than a fixed-size matrix.

Positioning Within the Broader Universality Landscape

To fully appreciate the paper's contribution, it helps to see where it fits in the hierarchy of universality results in deep learning:

Architecture	Universal approximation target	Input domain	Fixed width/dim?
2-layer MLP (Cybenko, Hornik et al.)	Continuous function	`ℝ^d`	No (width → ∞)
Deep ReLU networks (Hanin & Sellke, Yarotsky)	Continuous function	`ℝ^d`	Yes (minimal width = d+1)
CNNs (Zhou)	Equivariant continuous function	`ℝ^{d×channels}`	Spatial resolution → ∞
Graph Neural Networks (Keriven & Peyré)	Permutation-equivariant function	Variable-size graphs	Fixed dimensions
Transformers (Yun et al. 2019)	Sequence-to-sequence	`ℝ^{d×n}`	No (d grows with n)
Transformers (this paper)	In-context mapping	`𝓟(Ω) × Ω`	Yes (d + 3d')

The critical difference in the last row is that the input domain 𝓟(Ω) × Ω is infinite-dimensional (the space of probability measures), yet the approximating architecture uses finite-dimensional operations at each layer. This is what makes the result non-trivial and connects it to neural operator theory: just as neural operators approximate mappings between function spaces using finite-dimensional computations at each layer, transformers approximate in-context mappings between distributions using finite token embeddings. The paper's measure-theoretic formulation thus places transformers within the broader class of neural operators on metric spaces, providing a unified language for reasoning about their expressivity.

3. Technical Approach

3.1 Reader Orientation

This paper constructs a mathematical proof, not a software system or trained model. The "system" being built is a formal argument that any continuous in-context mapping — a function that takes a probability distribution of context tokens plus a query token and produces an output token — can be approximated arbitrarily well by composing finitely many attention layers and MLPs with fixed internal dimensions. The problem being solved is the theoretical gap in understanding whether standard transformer architectures, with embedding dimension and head count independent of both context size and target precision, are sufficient in principle to represent all continuous in-context computations. The solution takes the shape of a constructive density argument: define an algebra of "elementary" in-context functions (each a single-head attention composed with an affine MLP), prove this algebra separates points and contains constants, invoke Stone-Weierstrass to establish density in the space of all continuous in-context mappings, then show that products of algebra elements and their summation can be realized through a carefully orchestrated deep transformer architecture with dimension d + 3d' and at most d' heads per layer.

3.2 Big-Picture Architecture (Diagram in Words)

The proof architecture has six major components, organized into two parallel tracks (unmasked and masked) that share a common core:

Measure-theoretic in-context mapping formulation (Sections 2.2–2.3): Redefines attention layers as functions Γ_θ(μ, x) operating over probability measures μ rather than finite token sets, with a composition rule ⋄ that handles the pushforward of the context measure through each layer. This provides the mathematical language in which universality is stated.
Elementary in-context mappings γ_λ (Equation 14, Section 3.2): Scalar-valued functions built by composing a one-dimensional affine MLP with a single-head attention. These are the atoms of the proof — simple enough to analyze, rich enough to generate a separating algebra.
Algebra 𝓐 of cylindrical functions (Proposition 1): The set of all finite sums of finite products of elementary mappings. Stone-Weierstrass is applied here to prove density in the space of continuous scalar-valued in-context functions.
Vector-valued extension (Lemma 2): Uses the scalar-valued algebra dimension-by-dimension to approximate a vector-valued target Λ*: 𝓟(Ω) × Ω → ℝ^{d'}, expressing the approximation as a sum of products of single-head attention compositions.
Multiplication-to-MLP reduction (Lemma 3, Lemma 8): Replaces the component-wise product ⊙ in the sum-of-products expression with MLP approximations, leveraging the universality of MLPs for continuous functions on compact domains. This yields a pure composition of attention layers and MLPs — a deep transformer.
Space-time lifting and causal constraints (Section 4): For the masked case, maps the problem into Ω × [0,1] to restore structure amenable to measure-theoretic treatment, imposing Lipschitz regularity and identifiability as necessary conditions that causal transformers intrinsically satisfy.

Information flows as follows: the target in-context mapping Λ* → decomposed into scalar components → each scalar approximated by a cylindrical function (sums of products of elementary maps) → products replaced by MLP compositions → the resulting architecture recognized as a deep transformer. The causal case inserts an additional step: Λ* is first reduced via space-time lifting to a mapping over masked contexts (μ_t, x), then the same algebraic machinery applies on the restricted domain of Lipschitz contexts.

3.3 Roadmap for the Deep Dive

First, the measure-theoretic definitions and composition rules (Sections 2.2–2.3), since they establish the mathematical objects — what an in-context mapping is, how attention instantiates it, and how composition works — that everything else references.
Second, the elementary in-context mapping γ_λ (Equation 14), because it is the fundamental building block whose properties (continuity, constant functions, point separation) determine the applicability of Stone-Weierstrass and dictate the architecture's head dimension and embedding dimension requirements.
Third, the Stone-Weierstrass application (Proposition 1 and Lemma 1), which is the core of the proof: constructing the algebra, verifying its hypotheses, and concluding density. Lemma 1 (injectivity of the generalized Laplace transform) receives special attention because it is the non-trivial technical step.
Fourth, the vector-valued extension and sum-of-products expression (Lemma 2), showing how the scalar density result lifts to vector-valued targets through per-dimension approximation and how the resulting expression is written in terms of single-head attention compositions.
Fifth, the multiplication reduction via MLPs (Lemmas 3, 8, 9), which is the architectural heart of the paper: how the "cylindrical" expression (sum of products) is converted into a deep composition of attention and MLP layers, with explicit tracking of embedding dimension (d + 3d') and head count (d').
Sixth, the causal/masked adaptation (Section 4), explaining why space-time lifting, Lipschitz contexts, and identifiability are introduced, how the reduced mapping ¯Λ is defined, and why the unmasked proof carries over with these modifications, yielding Theorem 2.

3.4 Detailed, Sentence-Based Technical Breakdown

This is a mathematical proof paper whose core idea is that the Stone-Weierstrass theorem — a classical result from functional analysis that provides conditions under which an algebra of functions is dense in the space of continuous functions — can be applied to prove transformer universality by constructing an appropriate algebra from single-head attention operations, provided that (a) the input domain is correctly formalized as probability measures under the weak* topology, and (b) counter-intuitive architectural tricks (padding dimensions, identity-carrying through layers, MLP-approximated multiplication) are employed to realize cylindrical functions as deep transformer compositions.

Measure-Theoretic In-Context Mappings (Sections 2.2–2.3)

Unmasked case (Equation 9). A finite set of n tokens X = (x_i)_{i=1}^n ⊂ ℝ^{d_in} is encoded as a discrete empirical probability measure:

$\mu = \frac{1}{n} \sum_{i=1}^n \delta_{x_i} \in \mathcal{P}(\mathbb{R}^{d_\text{in}})$

where δ_{x_i} is the Dirac measure (a unit point mass) at x_i, and 𝓟(ℝ^{d_in}) is the space of all probability measures on ℝ^{d_in}.

What this encoding does: it erases the ordering of the tokens — the measure μ contains only the information of which vectors are present and with what frequency, not their sequence. This is the mathematical formalization of permutation invariance: permuting the tokens x_1, ..., x_n leaves μ unchanged because (1/n) Σ δ_{x_{σ(i)}} = (1/n) Σ δ_{x_i}. For unmasked attention, which is permutation-equivariant, this is exactly the right level of abstraction.

Why this encoding matters beyond notational convenience: it enables comparing contexts of different sizes. Two token sets with n = 10 and n = 1000 are both represented as probability measures on the same space ℝ^{d_in}, and the Wasserstein distance W_p(μ, ν) provides a meaningful metric for how "close" these contexts are, even when their cardinalities differ. The weak* topology (μ_k ⇀* μ means ∫f dμ_k → ∫f dμ for every continuous bounded f) captures the notion that the distribution of tokens converges, not that individual tokens align. A discrete empirical measure of the form above assigns equal mass 1/n to each token, which is the natural encoding for sets where tokens are treated symmetrically.

The in-context mapping for unmasked attention (Equation 9):

$\Gamma_\theta(\mu, x) := x + \sum_{h=1}^H W^h \int \frac{\exp\left(\frac{1}{\sqrt{k}} \langle Q^h x, K^h y \rangle\right)}{\int \exp\left(\frac{1}{\sqrt{k}} \langle Q^h x, K^h z \rangle\right) d\mu(z)} V^h y \, d\mu(y)$

where θ = (W^h, Q^h, K^h, V^h)_{h=1}^H are the multi-head attention parameters, k is the key/query dimension, H is the number of heads, W^h ∈ ℝ^{d_in × d_head} are output projection matrices, and Q^h, K^h, V^h are the query, key, and value matrices for head h. The input x ∈ ℝ^{d_in} is the query token, μ ∈ 𝓟(ℝ^{d_in}) is the context measure.

What it computes: for each head h, the inner integral computes a similarity-weighted average of the value-transformed context tokens V^h y, where the weights are softmax-normalized exponentials of the dot-product attention scores ⟨Q^h x, K^h y⟩ / √k. The outer sum over heads and the skip connection x + ... produce the standard multi-head attention output. The key difference from the usual matrix form is that the sums over tokens are replaced by integrals over the measure μ — when μ = (1/n) Σ δ_{x_i}, the integrals reduce exactly to the finite sums in the standard definition.

Why this form generalizes the finite case: for a discrete empirical measure μ = (1/n) Σ δ_{x_i}, we have ∫ f(y) dμ(y) = (1/n) Σ_{i=1}^n f(x_i). Substituting into the formula:

$\frac{\int \exp(...) V^h y \, d\mu(y)}{\int \exp(...) d\mu(z)} = \frac{\frac{1}{n}\sum_{j=1}^n \exp(...) V^h x_j}{\frac{1}{n}\sum_{\ell=1}^n \exp(...)} = \frac{\sum_{j=1}^n \exp(...) V^h x_j}{\sum_{\ell=1}^n \exp(...)}$

which is exactly the standard softmax attention. The 1/n factors cancel, so the measure-theoretic definition is a strict generalization — it recovers the finite case exactly and also defines attention for continuous measures (limits of many tokens).

Composition of unmasked layers (Equation 10):

$(\Gamma_2 \diamond \Gamma_1)(\mu, x) := \Gamma_2(\mu_1, \Gamma_1(\mu, x)), \quad \text{where} \quad \mu_1 := \Gamma_1(\mu)_\sharp \mu$

where Γ_1(μ)_♯ μ is the pushforward of the measure μ under the map Γ_1(μ): ℝ^{d_in} → ℝ^{d_out} (the first attention layer applied as a pointwise function to every token in the context).

What it computes: the composition rule processes the query token x through Γ_1, producing Γ_1(μ, x), while simultaneously updating the entire context μ to μ_1 by pushing every token through Γ_1(μ, ·). The second layer Γ_2 then receives this updated context and the updated query. This two-track processing — query token gets transformed, context measure gets pushed forward — is the structural signature of transformer composition.

Why pushforward is the right operation: in a discrete setting with X = (x_i)_{i=1}^n, the first attention layer transforms each token individually: x_i ↦ Γ_1(μ, x_i). The new context is the set {Γ_1(μ, x_i)}. The pushforward does exactly this for measures: Γ_1(μ)_♯ μ is the distribution of Γ_1(μ, y) when y is distributed according to μ. For the empirical measure (1/n) Σ δ_{x_i}, the pushforward is (1/n) Σ δ_{Γ_1(μ, x_i)}, perfectly matching the discrete transformer's behavior.

Deep transformer as in-context composition (Equation 11):

$F_{\xi_L} \diamond \Gamma_{\theta_L} \diamond \ldots \diamond F_{\xi_1} \diamond \Gamma_{\theta_1}$

where F_ξ(μ, x) = F_ξ(x) are "context-free" MLP layers — they ignore μ and process each token independently. The composition ⋄ defined above handles both context-free and context-dependent layers uniformly.

Masked case (Equations 12–13). Masked (causal) attention lacks permutation equivariance because the j-th token can only attend to tokens 1, ..., j. To fit this into the measure-theoretic framework, the paper introduces a space-time lifting: tokens are augmented with time indices t_i ∈ [0, 1].

The space-time context measure (Section 2.3):

$\mu \in \mathcal{P}(\mathbb{R}^{d_\text{in}} \times [0, 1])$

For a discrete sequence of n tokens, one can set t_i = i/n and encode as μ = (1/n) Σ_{i=1}^n δ_{(x_i, i/n)}. The time coordinate provides a total order, breaking permutation symmetry and enabling the causal masking.

The masked in-context mapping (Equation 12):

$\Gamma_\theta(\mu, x, t) := x + \sum_{h=1}^H W^h \int \frac{\exp\left(\frac{1}{\sqrt{k}} \langle Q^h x, K^h y \rangle\right) \mathbf{1}_{[0,t]}(r)}{\int \exp\left(\frac{1}{\sqrt{k}} \langle Q^h x, K^h z \rangle\right) \mathbf{1}_{[0,t]}(s) \, d\mu(z, s)} V^h y \, d\mu(y, r)$

where \mathbf{1}_{[0,t]}(s) is the indicator function equal to 1 when 0 ≤ s ≤ t and 0 otherwise. The query is now a space-time point (x, t) ∈ ℝ^{d_in} × [0, 1].

What it computes: the indicator \mathbf{1}_{[0,t]}(r) in the integrand restricts the attention to only those context tokens whose time coordinate r is ≤ the query's time t — this is causal masking. The denominator normalizes over the same restricted set. For the discrete measure (1/n) Σ δ_{(x_i, i/n)} with query at time t = i/n, the integration over \mathbf{1}_{[0,t]} selects tokens 1, ..., i, exactly recovering the standard causal attention in Equation (3).

Composition in the masked case (Equation 13):

$(\Gamma_2 \diamond \Gamma_1)(\mu, x, t) := \Gamma_2(\mu_1, \Gamma_1(\mu, x, t), t), \quad \text{where} \quad \mu_1 := (\Gamma_1(\mu), \text{Id}_\mathbb{R})_\sharp \mu$

What it computes: the pushforward (\Gamma_1(μ), Id_ℝ)_♯ μ transforms the spatial coordinate x to Γ_1(μ, x, t) while keeping the time coordinate t unchanged. This preserves the temporal ordering — token i stays at time t_i across layers, while its embedding x_i is updated. The query (x, t) has its spatial coordinate updated to Γ_1(μ, x, t) but its time t passed through unchanged.

Why time is preserved through pushforward: causal structure depends on temporal ordering. If the pushforward were allowed to modify time coordinates, tokens could "leak" into the past or future, violating causality. The pair (\Gamma_1(μ), Id_ℝ) explicitly maps (x, t) → (\Gamma_1(μ)(x, t), t), so only the embedding changes.

Elementary In-Context Mappings (Equation 14, Section 3.2)

The proof strategy requires building blocks — functions that are (a) demonstrably realizable by a single attention head plus MLP, and (b) rich enough that their products and sums form a separating algebra. The elementary mapping is parameterized as:

$\gamma_\lambda(\mu, x) := \langle x, a \rangle + b + \int \frac{e^{c(\langle x, a \rangle + b)(\langle y, a \rangle + b)}}{\int e^{c(\langle x, a \rangle + b)(\langle z, a \rangle + b)} d\mu(z)} v(\langle a, y \rangle + b) \, d\mu(y)$

where λ = (a, b, c, v) ∈ ℝ^d × ℝ × ℝ × ℝ is the parameter tuple.

What it computes: this is a scalar-valued in-context function. The first term ⟨x, a⟩ + b is a linear projection of the query x along direction a plus bias b — an affine MLP applied to x alone. The integral term is a single-head attention operation in one dimension: the keys and queries are the scalar ⟨y, a⟩ + b (the same MLP applied to context tokens), the similarity is exp(c · query · key), and the value is v(⟨a, y⟩ + b) (the same scalar projection scaled by v). The skip connection adds ⟨x, a⟩ + b back.

Why this parameterization: the exponent c(⟨x, a⟩ + b)(⟨y, a⟩ + b) factors into a product of a query-dependent term and a key-dependent term, which is exactly what happens when you apply a one-dimensional attention head after an affine projection: ⟨Q x, K y⟩ = q · (⟨a, x⟩ + b) · k · (⟨a, y⟩ + b) = c(⟨x, a⟩ + b)(⟨y, a⟩ + b) where c = qk. So γ_λ is literally Γ_θ ⋄ F_ξ for a one-dimensional attention head θ = (k, q, v) ∈ ℝ^3 and an affine MLP F_ξ(x) = ⟨a, x⟩ + b.

How this is built from primitives: first apply the affine context-free map F_ξ: ℝ^d → ℝ given by x ↦ ⟨a, x⟩ + b. This collapses each token to a scalar. Then apply a single-head attention Γ_θ: 𝓟(ℝ) × ℝ → ℝ in one dimension with key k, query q, value v. The composition Γ_θ ⋄ F_ξ is precisely γ_λ.

Realizability bound: constructing γ_λ requires one single-head attention whose embedding dimension is 1 (it operates on the scalar output of the affine MLP). When embedded in a larger architecture (as will happen in the full construction), this contributes one head of dimension 1 — consistent with the theorem's claim that d_head = k = 1.

The Algebra 𝓐 and Stone-Weierstrass (Proposition 1, Lemma 1)

Construction of the algebra (Section 3.2):

$\mathcal{A} := \left\{ \mathcal{P}(\Omega) \times \Omega \ni (\mu, x) \mapsto \sum_{n=1}^N \gamma_{\lambda_{1,n}}(\mu, x) \odot \cdots \odot \gamma_{\lambda_{T,n}}(\mu, x) \in \mathbb{R} : N, T \in \mathbb{N} \right\}$

where ⊙ denotes scalar multiplication (since each γ_λ is real-valued).

What this set contains: all finite sums of finite products of elementary mappings. A product γ_{λ_1} · γ_{λ_2} · ... · γ_{λ_T} is called a "cylindrical function" — it depends on the context μ through T different one-dimensional projections. The sum over n = 1, ..., N allows linear combinations. The algebra operations are pointwise addition and multiplication of such expressions.

Why an algebra is needed: Stone-Weierstrass states that if 𝓐 is a subalgebra of C(K) (continuous real-valued functions on compact K) that (i) contains the constant function 1, and (ii) separates points, then 𝓐 is dense in C(K) in the uniform norm. This is the standard route to universality: show that your function class is an algebra satisfying these hypotheses, and density follows.

Verifying algebra closure. The sum of two elements of 𝓐 is clearly in 𝓐 (adjusting N). The product of two elements is a sum of products of products — still a sum of products, hence in 𝓐. Scalar multiplication is a special case. So 𝓐 is indeed an algebra.

Continuity of γ_λ: For any fixed parameters λ, the mapping (μ, x) ↦ γ_λ(μ, x) is continuous in (μ, x) under the weak* × ℓ₂ topology. Continuity in x is obvious (the function involves ⟨x, a⟩ + b, which is continuous in x). Continuity in μ under the weak* topology follows because the integrand involves exp(c(⟨x, a⟩ + b)(⟨y, a⟩ + b)) and ⟨a, y⟩ + b, both of which are continuous and bounded on the compact set Ω. The denominator ∫ e^{c(⟨x, a⟩ + b)(⟨z, a⟩ + b)} dμ(z) is never zero because the exponential is strictly positive for all finite arguments — this is a crucial detail: if the denominator could vanish, the function would have singularities and not be continuous everywhere.

Constant functions: setting a = 0 (zero projection), b = 1, v = 1 yields γ_λ(μ, x) = ⟨x, 0⟩ + 1 + (...) = 1 + 0 = 1 (the integral vanishes because v = 1 multiplied by ⟨a, y⟩ + b = 1 gives a constant, but the attention denominator and numerator cancel, and the skip connection adds back b = 1 — the net is x · 0 + 1 + 0 = 1). So the constant function 1 belongs to the algebra.

Point separation (Equation 15 and Lemma 1): This is the hardest hypothesis to verify. We must show that if (μ, x) ≠ (μ', x'), there exists some γ_λ that takes different values at these two inputs. That is, we must show:

$\forall \lambda, \; \gamma_\lambda(\mu, x) = \gamma_\lambda(\mu', x') \quad \Longrightarrow \quad (\mu, x) = (\mu', x')$

Step 1: Separating x. Set v = 0 in the elementary mapping. Then γ_{(a, b, c, 0)}(μ, x) = ⟨x, a⟩ + b — the integral term vanishes completely. If this equals ⟨x', a⟩ + b for all a ∈ ℝ^d, then ⟨x, a⟩ = ⟨x', a⟩ for all a, which implies x = x' (choosing a to be the standard basis vectors picks out each coordinate).

Step 2: Separating μ given equal x. With x = x' established, set b = 1 - ⟨a, x⟩ so that ⟨x, a⟩ + b = 1. Then the equality γ_λ(μ, x) = γ_λ(μ', x) reduces to:

$\mathcal{L}(\mu)(a, c) = \mathcal{L}(\mu')(a, c), \quad \forall a \in \mathbb{R}^d, \forall c \in \mathbb{R}$

where 𝓛(μ) is the generalized Laplace transform:

$\mathcal{L}(\mu)(a, c) := \int \frac{e^{c \langle a, y \rangle}}{\int e^{c \langle a, z \rangle} d\mu(z)} \langle a, y \rangle \, d\mu(y)$

What 𝓛 computes: it is the expected value of ⟨a, y⟩ under a tilted distribution whose density with respect to μ is e^{c ⟨a, y⟩} / ∫ e^{c ⟨a, z⟩} dμ(z). This is an exponential tilting — a reweighting that emphasizes tokens with large projection along a when c > 0 (or small projection when c < 0). The function c ↦ 𝓛(μ)(a, c) is the moment-generating derivative for the one-dimensional projection y ↦ ⟨a, y⟩.

Lemma 1 (Injectivity of 𝓛): If 𝓛(μ)(a, c) = 𝓛(μ')(a, c) for all a ∈ ℝ^d and all c ∈ ℝ, then μ = μ'.

Proof outline in two stages:

One-dimensional case (Lemma 6, Appendix B.1). Define L_k(μ)(c) = ∫ e^{cy} y^k dμ(y) / ∫ e^{cz} dμ(z). A direct computation shows L_k'(c) = L_{k+1}(c) - L_k(c)L_1(c). So if L_1(μ)(c) = L_1(μ')(c) for all c, then by differentiating repeatedly, L_k(μ)(c) = L_k(μ')(c) for all k ≥ 1 and all c. Evaluating at c = 0 gives ∫ y^k dμ(y) = ∫ y^k dμ'(y) for all k ≥ 1 (all moments equal). On a compact interval, moment equality implies μ = μ'. This is the classical moment problem on a compact set: the distribution is uniquely determined by its moment sequence.
Lifting to d dimensions (Lemma 7, Appendix B.1). For any direction e ∈ S^d (the d-dimensional sphere), define the projected measure μ_e = (P_e)_♯ μ where P_e(x) = ⟨x, e⟩ projects onto the line in direction e. Then 𝓛(μ)(e, c) = L_1(μ_e)(c). If 𝓛(μ)(a, c) = 𝓛(μ')(a, c) for all a, then in particular for all unit vectors e and all c, we have L_1(μ_e)(c) = L_1(μ'_e)(c). By the one-dimensional result, μ_e = μ'_e for every e. That is, the one-dimensional projections of μ and μ' onto every line coincide. The injectivity of the Radon transform (see, e.g., Boman and Lindskog, 2009) states that a probability measure on ℝ^d is uniquely determined by its one-dimensional projections. Therefore μ = μ'.

Why the exponential form is critical: if the attention kernel were something other than exp(c · query · key) — say, a polynomial kernel — the connection to exponential tilting and moment generating functions would break, and point separation might fail. The softmax's exponential is not just a convenient choice; it is necessary for the proof strategy because it provides analytic structure (derivatives with respect to c generate the moment sequence). A dot-product attention without the exponential would not support this argument.

Proposition 1 (Density of 𝓐): The algebra 𝓐 satisfies all three Stone-Weierstrass hypotheses: (i) contains constant functions, (ii) separates points, (iii) is an algebra. The domain 𝓟(Ω) × Ω is compact in the weak* × ℓ₂ topology (Aliprantis and Border, Theorem 15.11). Therefore, 𝓐 is dense in C(𝓟(Ω) × Ω; ℝ) — the space of continuous real-valued functions on this compact space.

What Proposition 1 means concretely: for any continuous scalar-valued in-context mapping f: 𝓟(Ω) × Ω → ℝ and any ε > 0, there exist N, T ∈ ℕ and parameters {λ_{t,n}\} such that:

$\sup_{(\mu, x)} \left| f(\mu, x) - \sum_{n=1}^N \prod_{t=1}^T \gamma_{\lambda_{t,n}}(\mu, x) \right| \leq \varepsilon$

The approximation is uniform over all contexts μ and all queries x in the compact domain.

Vector-Valued Extension (Lemma 2)

Target mappings in practice output vectors in ℝ^{d'}, not scalars. Lemma 2 lifts the scalar density result to vector-valued functions.

Decomposition into coordinates:

$\Lambda^*(\mu, x) = \sum_{h=1}^{d'} \Lambda^*_h(\mu, x) e_h$

where e_h is the h-th standard basis vector and Λ^*_h: 𝓟(Ω) × Ω → ℝ are the d' scalar component functions, each continuous.

Per-coordinate approximation: Apply Proposition 1 to each Λ^*_h separately with precision ε/√(d'). There exist T, N (which can be taken uniform across h by taking maxima) and parameters λ^h_{t,n} such that:

$\left| \Lambda^*_h(\mu, x) - \sum_{n=1}^N \gamma_{\lambda^h_{1,n}}(\mu, x) \cdots \gamma_{\lambda^h_{T,n}}(\mu, x) \right| \leq \frac{\varepsilon}{\sqrt{d'}}$

Assembling the vector approximation:

$G(\mu, x) := \sum_{h=1}^{d'} \left[ \sum_{n=1}^N \gamma_{\lambda^h_{1,n}}(\mu, x) \cdots \gamma_{\lambda^h_{T,n}}(\mu, x) \right] e_h$

Regrouping the summation over n (interchanging sums):

$G(\mu, x) = \sum_{n=1}^N \overline{\gamma}_{\lambda_{1,n}}(\mu, x) \odot \cdots \odot \overline{\gamma}_{\lambda_{T,n}}(\mu, x)$

where \overline{γ}_{λ_{t,n}}(μ, x) := (γ_{λ^1_{t,n}}(μ, x), ..., γ_{λ^{d'}_{t,n}}(μ, x)) ∈ ℝ^{d'} is the vector of the d' scalar elementary mappings with different parameters per coordinate, and ⊙ is component-wise (Hadamard) multiplication.

Accuracy bound:

$\|\Lambda^*(\mu, x) - G(\mu, x)\|_2 \leq \sqrt{\sum_{h=1}^{d'} \left| \Lambda^*_h - \sum_{n=1}^N \prod_{t=1}^T \gamma_{\lambda^h_{t,n}} \right|^2} \leq \sqrt{d' \cdot \left(\frac{\varepsilon}{\sqrt{d'}}\right)^2} = \varepsilon$

Realizing \overline{γ}_{λ_{t,n}} as Γ_{θ̃_{t,n}} ⋄ F_{ξ̃_{t,n}} (Appendix B.2). The construction uses a d'-dimensional attention with d' heads, each of dimension 1:

F_{ξ̃_{t,n}}: ℝ^d → ℝ^{d'} is an affine map: F_{ξ̃_{t,n}}(x) = A_{t,n} x + b_{t,n} where row h of A_{t,n} is a^h_{t,n} and entry h of b_{t,n} is b^h_{t,n}.
Γ_{θ̃_{t,n}}: 𝓟(ℝ^{d'}) × ℝ^{d'} → ℝ^{d'} uses d' heads, each with W̃^h_{t,n} = e_h (the h-th standard basis vector), Q̃^h_{t,n} = (0, ..., 0, c^h_{t,n}, 0, ..., 0) (only the h-th coordinate active with value c^h_{t,n}), K̃^h_{t,n} = (0, ..., 0, 1, 0, ..., 0) (only h-th coordinate with value 1), and Ṽ^h_{t,n} = (0, ..., 0, v^h_{t,n}, 0, ..., 0) (only h-th coordinate with value v^h_{t,n}).

What this achieves: head h reads only the h-th coordinate of the projected tokens, computes its own one-dimensional attention, scales by v^h_{t,n}, and outputs to the h-th coordinate via W̃^h = e_h. The skip connection passes through the input. Since the heads operate on orthogonal coordinates and output to orthogonal dimensions, they are completely decoupled — the d' scalar elementary mappings γ_{λ^1}, ..., γ_{λ^{d'}} are computed in parallel and stacked into a vector.

Result (Lemma 2): For any ε > 0, there exist T, N and parameters (θ̃_{t,n}, ξ̃_{t,n}) such that:

$\|G(\mu, x) - \Lambda^*(\mu, x)\| \leq \varepsilon$

where G(μ, x) = Σ_{n=1}^N (Γ_{θ̃_{1,n}} ⋄ F_{ξ̃_{1,n}})(μ, x) ⊙ ... ⊙ (Γ_{θ̃_{T,n}} ⋄ F_{ξ̃_{T,n}})(μ, x), with d_in(θ̃_{t,n}) = d', d_head = k = 1, H = d'.

Multiplication Reduction via MLPs (Lemmas 3, 8, 9)

The expression G(μ, x) is not yet a deep transformer — it is a sum of products, where the products ⊙ are not transformer operations. The final step replaces ⊙ with MLP approximations and orchestrates the computation through a deep architecture with embedding dimension d + 3d'.

Rewriting the product structure. The telescoping product can be parenthesized as:

$(\Gamma_{θ̃_{T,n}} ⋄ F_{ξ̃_{T,n}})(μ, x) ⊙ \left[ (\Gamma_{θ̃_{T-1,n}} ⋄ F_{ξ̃_{T-1,n}})(μ, x) ⊙ \left[ \cdots ⊙ \left[ (\Gamma_{θ̃_{1,n}} ⋄ F_{ξ̃_{1,n}})(μ, x) ⊙ \mathbf{1}_{d'} \right] \cdots \right] \right]$

where 𝟙_{d'} is the all-ones vector (the multiplicative identity for ⊙).

MLP approximation of multiplication (Lemma 8): The Hadamard product (x, y) ↦ x ⊙ y is a continuous function from ℝ^{d'} × ℝ^{d'} to ℝ^{d'}. By standard MLP universality, for any compact set and any ε > 0, there exists an MLP Φ: ℝ^{d'} × ℝ^{d'} → ℝ^{d'} such that |x ⊙ y - Φ(x, y)| ≤ ε for all (x, y) in the compact set.

Bounding the intermediate values. Each composition (Γ_{θ̃_{t,n}} ⋄ F_{ξ̃_{t,n}})(μ, x) is bounded by a constant C̃_Γ that depends on the parameters but not on μ, x. This follows because Ω is compact and the affine/attention operations are continuous — their images on the compact domain are bounded. Therefore all vectors in the sequential multiplication lie in a ball of radius R determined by C̃_Γ, and the MLP needs only to approximate ⊙ on this ball.

Sequential MLP approximation: replace each ⊙ in the telescoping expression with Φ:

$G_\Phi(\mu, x) = \sum_{n=1}^N \Phi\left( (\Gamma_{θ̃_{T,n}} ⋄ F_{ξ̃_{T,n}})(\mu, x), \; \Phi\left( (\Gamma_{θ̃_{T-1,n}} ⋄ F_{ξ̃_{T-1,n}})(\mu, x), \; \cdots \; \Phi\left( (\Gamma_{θ̃_{1,n}} ⋄ F_{ξ̃_{1,n}})(\mu, x), \; \mathbf{1}_{d'} \right) \cdots \right) \right)$

The error accumulates linearly: each ⊙ replaced by Φ introduces error at most ε/(N·T), and there are N·(T-1) products total, so the cumulative error is ≤ ε.

Lemma 8 ensures: |G(μ, x) - G_Φ(μ, x)| ≤ ε uniformly over all μ, x.

Deep transformer realization (Lemma 9, Appendix B.3). The expression G_Φ is now purely a composition of Γ operations and Φ MLPs. But the Γ operations are d'-dimensional while we need them embedded in a larger architecture of dimension d + 3d' that can also handle the summation over n. The proof constructs this through an explicit "carry-and-accumulate" scheme diagrammed in Appendix B.3.

The embedding dimension d + 3d' is partitioned as follows for each token:

Coordinate range	Content
`[1, d]`	The original token embedding `x` (always preserved)
`[d+1, d+d']`	The current affine-transformed version `F̃_{ξ_{t,n}}(x)`
`[d+d'+1, d+2d']`	The running product `φ_{t,n}(x)`
`[d+2d'+1, d+3d']`	The running sum accumulator `f_n(x)`

Step A (Initialization, F_{ξ_0} ⋄ Γ_{θ_0}): The first layer Γ_{θ_0} is the identity attention (does nothing), and F_{ξ_0} maps x ∈ ℝ^d to the vector (x, F̃_{ξ_{1,1}}(x), \mathbf{1}_{d'}, \mathbf{0}_{d'}) ∈ ℝ^{d + 3d'}. The token now carries:

Its original embedding x
The affine projection for the first elementary mapping F̃_{ξ_{1,1}}(x)
The initial product φ_{1,1}(x) = 𝟙_{d'} (multiplicative identity)
The initial accumulator f_1(x) = 0

Step B (Product updates, F_{ξ_{t,n}} ⋄ Γ_{θ_{t,n}} for t = 1, ..., T-1, n = 1, ..., N): The attention Γ_{θ_{t,n}} applies the d'-dimensional single-head attention Γ_{θ̃_{t,n}} to the affine-projected coordinates (the [d+1, d+d'] slot) while leaving everything else unchanged. Crucially, the Ṽ^h matrices in the attention read from the [d+1, d+d'] slot and write back to the same slot, while the W̃^h output projection writes to coordinate d + h. The MLP F_{ξ_{t,n}} then:

Updates the [d+1, d+d'] slot to the next affine projection F̃_{ξ_{t+1,n}}(x) for the next elementary mapping.
Updates the [d+d'+1, d+2d'] slot to Φ(current_attention_output, previous_product) — this computes one step of the telescoping product.

After t = T-1 applications, the product slot contains Φ(Γ̃_{θ̃_{T-1,n}} ⋄ F̃_{ξ̃_{T-1,n}}, Φ(..., Φ(Γ̃_{θ̃_{1,n}} ⋄ F̃_{ξ̃_{1,n}}, 𝟙_{d'})...)).

Step C (Product completion and accumulator update, F_{ξ_{T,n}} ⋄ Γ_{θ_{T,n}}): The attention Γ_{θ_{T,n}} applies Γ_{θ̃_{T,n}} to the affine slot, and the MLP F_{ξ_{T,n}}:

Resets the affine slot to F̃_{ξ_{1,n+1}}(x) (preparing for the next n).
Resets the product slot to 𝟙_{d'} (re-initializing the multiplicative identity).
Adds Φ(current_attention, previous_product) to the accumulator slot: f_{n+1}(x) = f_n(x) + Φ(Γ̃_{θ̃_{T,n}} ⋄ F̃_{ξ̃_{T,n}}, φ_{T,n}(x)).

After one full cycle t = 1, ..., T for a given n, the accumulator has grown by the n-th term in the sum.

Step D (Output extraction, F_{ξ_*} ⋄ Γ_{θ_*}): After all N summands are accumulated, the final layer Γ_{θ_*} is the identity and F_{ξ_*} projects onto the accumulator coordinates [d+2d'+1, d+3d'], outputting f_{N+1}(x) = Σ_{n=1}^N Φ(...), which is exactly G_Φ(μ, x).

Layer count and dimensions: The construction uses L = 1 + N·T + 1 layers total (initialization, one per attention-MLP pair, final projection). Each attention layer Γ_{θ_{t,n}} has d_in = d + 3d', d_head = 1, k = 1, H = d'. The d' heads are exactly those from the Γ_{θ̃_{t,n}} construction, embedded in the larger space to only read/write the [d+1, d+d'] coordinate block — other coordinates are passed through unchanged by using zero key/query/value components for those dimensions.

Lemma 9 establishes the exact equality: G_Φ(μ, x) = F_{ξ_*} ⋄ Γ_{θ_*} ⋄ (⋄_{n=1}^N ⋄_{t=1}^T F_{ξ_{t,n}} ⋄ Γ_{θ_{t,n}}) ⋄ F_{ξ_0} ⋄ Γ_{θ_0} (μ, x).

Combining Lemmas 2, 8, and 9 yields Theorem 1: For any continuous Λ*: 𝓟(Ω) × Ω → ℝ^{d'} and any ε > 0, there exist L and parameters (θ_ℓ, ξ_ℓ)_{ℓ=1}^L such that the deep transformer defined by these parameters approximates Λ* within ε uniformly, with d_in ≤ d + 3d', d_head = k = 1, and H ≤ d' at every layer.

Why d + 3d' rather than a smaller dimension: the three d'-dimensional auxiliary slots are needed simultaneously: the affine projection for the current elementary mapping, the running product so far, and the running sum accumulator. These three cannot be collapsed into fewer dimensions without losing information or requiring more layers to recompute values. The d-dimensional slot preserves the original token x, which is needed because the affine projections F̃_{ξ_{t,n}} depend on x (they are of the form A_{t,n}x + b_{t,n}, operating on the original token, not the accumulated values). The proof shows this is sufficient; whether it is necessary (a lower bound) is not established.

Causal/Masked Adaptation (Section 4)

The unmasked proof fails for causal attention because the underlying function space 𝓟(Ω) × Ω assumes permutation-equivariant contexts. Causal transformers are not permutation-equivariant — token i can only see the prefix up to i. The paper introduces a space-time lifting and additional regularity conditions to fit causal attention into a similar algebraic framework.

Space-time domains (Section 4.1): The context is now a space-time measure μ ∈ 𝓟(Ω̃) where Ω̃ = Ω × [0, 1]. The query is (x, t) ∈ Ω̃.

Lipschitz contexts (Definition 1): A space-time measure μ belongs to Lip_C(Ω̃) if it admits a disintegration μ(x, s) = μ(x|s) μ̄(s) where μ̄ ∈ 𝓟([0, 1]) is the time marginal and the conditional map s ↦ μ(·|s) ∈ 𝓟(Ω) is C-Lipschitz under the Wasserstein-2 distance:

$\forall s, t \in [0, 1], \quad W_2(\mu(\cdot|s), \mu(\cdot|t)) \leq C|s - t|$

Why Lipschitz contexts: this condition ensures that the set of masked measures {μ_t : μ ∈ Lip_C, t ∈ [0, 1]} is compact under the weak* topology (Lemma 5). Compactness is a prerequisite for Stone-Weierstrass. The condition is automatically satisfied for discrete measures μ = (1/n) Σ δ_{(x_i, t_i)} with distinct times (using C = diam(Ω) / min|t_i - t_j|), so it is not restrictive for finite-token settings.

The σ-mass condition: Lip_C^σ(Ω̃) additionally requires μ̄({0}) ≥ σ — the time marginal has a Dirac mass of at least σ at t = 0. This ensures the masked measure μ_t is well-defined for all t ∈ [0, 1] (the denominator μ̄([0, t]) in the masked measure definition is bounded below near t = 0). For discrete measures with t_1 = 0, this holds with σ = 1/n.

Masked measures (Definition 2, Equation 19):

$\mu_t := \frac{\mathbf{1}_{[0,t]}}{\bar{\mu}([0, t])} \cdot \mu$

This is the conditional distribution of μ restricted to times s ≤ t. For t = 0, the limit μ_0 = μ(·|0) δ_{s=0} is used (Lemma 10). The map t ↦ μ_t is continuous in the weak* topology, which connects the continuous-time formulation to the discrete step-by-step causal attention.

Causal and identifiable maps (Definition 3): A space-time in-context map Λ is:

Causal: Λ(μ, x, t) = Λ(μ_t, x, t) — the output at time t depends only on the masked measure (tokens up to time t).
Identifiable: μ_t = μ_{t'} implies Λ(μ_t, ·, t) = Λ(μ_{t'}, ·, t') — if the masked contexts coincide, the functions they induce are identical.

Lemma 11 proves that masked attention Γ_θ (Equation 12) satisfies both properties. Lemma 12 proves that composition preserves causality and identifiability: if Γ_1 and Γ_2 are causal/identifiable, so is Γ_2 ⋄ Γ_1.

Reduced mapping (Definition 4):

$\overline{\Lambda}(\mu, x) := \Lambda(\mu, x, e(\bar{\mu}))$

where e(μ̄) = max supp(μ̄) is the maximum time in the support. The reduced map drops the explicit time argument by always evaluating at the endpoint of the time marginal. Lemma 4 shows that for any causal identifiable map Λ:

$\Lambda(\mu, x, t) = \overline{\Lambda}(\mu_t, x)$

because μ_t = μ_{e(μ̄_t)} (the mask at time t equals the mask at the endpoint of its own time marginal), and identifiability ensures the function value is the same. This is the crucial bridge: it lets us re-express approximation of Λ(μ, x, t) over all (μ, x, t) as approximation of Λ̄(μ_t, x) over the reduced space X_C^σ = {(μ_t, x) : μ ∈ Lip_C^σ, x ∈ Ω, t ∈ [0, 1]}.

Compactness of the reduced space (Lemma 5): The set X_C^σ is compact in the weak* × ℓ₂ topology. The proof (Appendix C.3) uses the Arzelà-Ascoli theorem for the conditional distributions: since s ↦ μ_n(·|s) is equicontinuous (uniformly C-Lipschitz) and takes values in the compact space 𝓟(Ω), a subsequence converges uniformly to a C-Lipschitz limit μ(·|s). The time marginals μ̄_n converge weak* to some μ̄ ∈ 𝓟_σ([0, 1]). The masked measures (μ_n)_{t_n} converge to μ_t, including the subtle case t_n → t = 0 where the definition of μ_t changes form (Lemma 10 handles this via continuity of t ↦ μ_t).

Applying the unmasked proof to the reduced space. Proposition 2 states that for any continuous Λ̄*: X_C^σ → ℝ^{d'}, there exists a deep transformer with the same dimension bounds as in Theorem 1 that approximates it uniformly on X_C^σ. The proof is structurally identical to the unmasked case — construct the same algebra of elementary functions on X_C^σ, verify Stone-Weierstrass hypotheses, extend to vector-valued outputs, and reduce products to MLPs — because X_C^σ is a compact subset of 𝓟(Ω̃) × Ω, and the same algebraic machinery applies.

Theorem 2 then follows: substitute Λ̄(μ_t, x) = F_{ξ_L} ⋄ Γ_{θ_L} ⋄ ... ⋄ F_{ξ_1} ⋄ Γ_{θ_1}(μ_t, x). By Lemma 11(b), each masked attention Γ_{θ_ℓ} satisfies Γ_{θ_ℓ}(μ, x, t) = Γ̄_{θ_ℓ}(μ_t, x). By Lemma 4(i) applied to the composition, the whole transformer satisfies the same relation. Therefore:

$|\text{Transformer}(\mu, x, t) - \Lambda^*(\mu, x, t)| = |\overline{\text{Transformer}}(\mu_t, x) - \overline{\Lambda^*}(\mu_t, x)| \leq \varepsilon$

uniformly over (μ, x, t) ∈ Lip_C^σ(Ω̃) × Ω̃.

Sharpness of identifiability (Lemma 13). Lemma 13 proves that if a sequence of identifiable maps Λ_n converges uniformly to Λ*, then Λ* is identifiable. Since transformers are identifiable (Lemma 11) and uniform limits of transformer compositions are identifiable, a non-identifiable target cannot be uniformly approximated by any deep causal transformer. This makes identifiability a necessary condition for Theorem 2 — the theorem is tight in that it cannot be extended to non-identifiable targets.

Why the Lipschitz restriction is necessary. The unmasked proof required compactness of the input space 𝓟(Ω) × Ω to apply Stone-Weierstrass. For masked contexts, the full space of all space-time measures is not compact under the right topology for the masked measures μ_t. Restricting to Lip_C provides the required compactness (Lemma 5). The paper notes (Remark 2) that the restriction μ̄({0}) ≥ σ can be relaxed to any fixed time marginal μ̄ = ν with 0 ∈ supp(ν), since then the denominator μ̄([0, t]) is well-behaved and the same compactness arguments hold.

Summary of Proof Architecture and Design Choices

Component	Approach	Why This Choice
Input formalization	Probability measures `μ` under weak* topology	Handles arbitrary token count, enables uniform approximation statements
Elementary building blocks	`γ_λ` from 1-D attention + affine MLP	Minimal parameterization that generates separating algebra
Density proof	Stone-Weierstrass on algebra `𝓐`	Classical route; avoids constructive complexity of direct network design
Point separation	Generalized Laplace transform + Radon injectivity	Exponential attention kernel connects to moment problem, making proof possible
Vector extension	Per-coordinate scalar approximation, stacked	Dimension-by-dimension treatment keeps head dimension bound at `H = d'`
Product reduction	MLP approximation of `⊙`, carry-accumulate architecture	Products are not transformer operations; MLPs are; `d+3d'` dimension is construction cost
Causal adaptation	Space-time lifting, Lipschitz contexts, identifiability	Restores compactness and reduces to unmasked proof structure; conditions are transformer-intrinsic
Dimension bounds	`d_in = d + 3d'`, `d_head = k = 1`, `H ≤ d'`	Constructive; three auxiliary `d'`-slots needed for carry-and-accumulate; heads needed only for per-coordinate decoupling
Non-quantitative nature	No depth/width vs. `ε` bounds provided	Stone-Weierstrass is existential; MLP approximation of `⊙` makes bounds depend on unknown bound `C̃_Γ` (Remark 3)

4. Key Insights and Innovations

Innovation 1: A Unified Topological Framework That Makes "Arbitrary Context Length" Mathematically Rigorous

Before this paper, the expressivity literature for transformers suffered from a fundamental tension: universality results either required the embedding dimension to scale with the number of tokens (Yun et al., 2019; Alberti et al., 2023) or modified the architecture away from standard practice (Sumformer). The underlying obstacle was that there was no satisfactory mathematical formalism for what a transformer processes when the number of tokens can vary. Prior work treated inputs as finite-dimensional objects — a matrix of size d × n — and proved approximation results that depended on n. This made "handle any number of tokens" an informal aspiration rather than a rigorous statement.

The paper's core conceptual innovation is to recast the input domain as the space of probability measures P(Ω) under the weak* topology, metrized by the Wasserstein distance. This is not a cosmetic change — it is a structural reframing that solves four problems simultaneously:

First, it provides a single topological space in which contexts of all sizes coexist. A 10-token set lives in P(Ω) as a discrete measure (1/10)∑δ_{x_i}; a 10^6-token set lives in the same space; so does a continuous density. The weak* topology gives a unified notion of convergence: two contexts are close when their empirical distributions are close, regardless of cardinality. This is what makes a statement like "uniform approximation over all contexts of any size" mathematically well-posed — without it, one would need to define a different function space for each n and relate them somehow.

Second, it reveals that permutation equivariance — the property that unmasked attention does not care about token order — is baked into the input representation. A measure μ = (1/n)∑δ_{x_i} does not encode ordering; permuting the x_i leaves μ unchanged. This connects transformers to the literature on permutation-invariant architectures (PointNet, DeepSets, graph neural networks) but at a deeper level: those architectures typically assume inputs are sets (finite, unordered collections), while the measure-theoretic view handles distributions (potentially continuous, with density information). This is a more general setting that subsumes finite sets as the special case of empirical measures.

Third, the composition rule (Γ_2 ⋄ Γ_1)(μ, x) = Γ_2(μ_1, Γ_1(μ, x)) where μ_1 = Γ_1(μ)_♯μ cleanly separates what happens at each layer into two parallel tracks: the query token x gets mapped through the in-context function, while the entire context μ gets pushed forward (all tokens are simultaneously displaced). This reveals that a deep transformer is fundamentally a coupled particle system — each layer is an evolution step where particles interact through attention and are displaced. Prior work described transformers operationally (matrix multiplications, residual connections) but lacked this structural decomposition. The pushforward composition makes explicit that the same function Γ_θ(μ, ·) is applied to every token, and the resulting distribution becomes the context for the next layer. This framing is essential for proving universality because it identifies exactly what degrees of freedom are available (the per-token map) and what constraints must be respected (the pushforward coupling).

Fourth, the formulation enables handling the infinite-token limit — the "mean field" regime where discrete measures approximate continuous ones. This is relevant for vision transformers applied to high-resolution images (many patches), for analyzing scaling behavior as sequence length grows, and for connecting transformers to neural operators that learn mappings between function spaces. The paper explicitly notes this connection (Section 2.2) but does not pursue it deeply; the formulation nonetheless opens the door.

This innovation is fundamental rather than incremental. It does not improve an existing universality proof — it creates the mathematical language in which such a proof can be stated for the first time. Prior work (Yun et al., 2019) could only say "given n tokens, there exists a transformer of width proportional to n that approximates a sequence-to-sequence map." This paper can say "there exists a single transformer, with fixed dimension independent of n, that approximates a continuous in-context mapping uniformly over all n." The difference is precisely the measure-theoretic formulation.

The evidence that this framing is not merely notational is the technical work it enables: the continuity of attention with respect to the weak* topology (Equation 9), the compactness of P(Ω) × Ω (enabling Stone-Weierstrass), and the construction of point-separating elementary functions whose parameters do not depend on n. None of these would be naturally expressible in a matrix-based formulation where the input space dimension varies.

Innovation 2: The Algebraic Proof Strategy Establishes Universality Without Constructive Complexity

A standard approach to neural network universality — used by Cybenko (1989) for MLPs, by Zhou (2020) for CNNs, and by Yun et al. (2019) for transformers — is constructive: explicitly build a network architecture that approximates the target function by, for example, implementing step-function approximations or Taylor expansions. This approach produces explicit depth and width bounds in terms of ε, but it becomes combinatorially complex for deep architectures and typically forces dimension growth with input size.

This paper takes a fundamentally different route: algebraic density via Stone-Weierstrass. The proof strategy is:

Identify an algebra A of functions that are each individually realizable by a small transformer fragment (a single-head attention plus an affine MLP — Equation 14).
Prove that this algebra separates points and contains constants on the domain P(Ω) × Ω.
Conclude by Stone-Weierstrass that A is dense in all continuous functions — meaning some finite combination of algebra elements (sums of products) approximates the target.
Show that arbitrary sums of products of algebra elements can be mechanically rewritten as a deep composition of attention and MLP layers, at the cost of adding dimensions to carry intermediate values through the layers.

The intellectual distinctiveness of this approach is that it decouples the density argument from the architectural realization. The "approximation power" comes from the algebraic closure properties (you can multiply and add elementary functions) — which is a statement about the function space, not about any particular network architecture. The "transformer realizability" comes from a separate, constructive encoding of sum-of-product expressions into the carry-and-accumulate architecture of Lemmas 8–9. This separation of concerns makes the proof conceptually clean: the algebra handles approximation quality, the architecture handles representation.

Compare this to Yun et al. (2019), who built a transformer that directly implements a step-function approximation of a target sequence-to-sequence map. Their construction required O(n) embedding dimension because each token position needed a dedicated "scratch space" to store intermediate values. The current paper avoids this by not constructing the approximator token-by-token — instead, it constructs functions of distributions, which naturally aggregate over any number of tokens through the measure μ.

The non-constructive nature of the proof (it doesn't produce explicit depth/width bounds in terms of ε) is a real weakness for practical purposes, but it is also a conceptual strength: it establishes universality at the level of principle, without getting bogged down in the (likely very loose) quantitative estimates that a constructive proof would produce. The authors are explicit about this tradeoff (Remark 3 in Appendix B.3): the MLP that approximates the component-wise product ⊙ introduces a dependence on intermediate token magnitudes C̃_Γ, which in turn depend on the parameters chosen by the Stone-Weierstrass step, making quantitative bounds "challenging." This is a honest limitation, but it's the right limitation for a paper establishing whether universality holds, leaving how efficiently for future work.

The injectivity of the generalized Laplace transform (Lemma 1) — that the exponential tilting operator L(μ)(a, c) uniquely determines μ — is the technical linchpin of the algebraic approach. This is where the specific form of softmax attention (the exponential kernel) becomes essential to the proof, not just a convenient modeling choice. A dot-product attention without the exponential would not connect to moment-generating functions, and the point-separation argument would break. This insight — that the softmax's analytic structure is necessary for universality in this proof paradigm — is a contribution that goes beyond the specific theorems: it identifies a structural role for the exponential that was not previously recognized.

The algebraic approach is a fundamental methodological innovation for the field. It provides a template for proving universality of other architectures that process variable-sized inputs: (1) find an algebra of simple functions your architecture can implement, (2) prove point separation (often the hardest part), (3) apply Stone-Weierstrass, (4) encode the algebraic operations into the architecture's composition structure. The paper's Lemmas 8–9 (the carry-and-accumulate encoding of sum-of-products into transformer layers) are specific to transformers, but the overall strategy could be adapted to equivariant GNNs, set-based architectures, or other neural operators.

Innovation 3: Identifiability and Lipschitz Contexts as Intrinsic Regularity — A Tight Characterization of What Causal Transformers Can Represent

The masked (causal) universality result in Theorem 2 is not simply a technical extension of the unmasked Theorem 1 with "some extra constraints." It represents a distinct intellectual contribution: the identification of two structural properties — identifiability and Lipschitz context regularity — that are simultaneously intrinsic to causal transformers and constitutive of the class of functions they can uniformly approximate. This is a tight characterization, not just a sufficiency theorem with overbroad hypotheses.

The key logical structure is:

Lemma 11: Masked attention maps Γ_θ satisfy both causality (Γ_θ(μ, x, t) = Γ_θ(μ_t, x, t)) and identifiability (μ_t = μ_{t'} implies the induced functions are equal).
Lemma 12: Composition preserves causality and identifiability — any deep causal transformer is causal and identifiable.
Lemma 13: Identifiability is stable under uniform limits — the uniform limit of identifiable maps is identifiable.
Therefore: Any in-context mapping that can be uniformly approximated by causal transformers must itself be identifiable. Identifiability is a necessary condition.

This chain of reasoning establishes something rare in approximation theory: a sharp boundary on what the architecture can represent. Most universality theorems are pure sufficiency results — they show that some class of functions can approximate a target class, without saying anything about what cannot be approximated. Theorem 2, by including Lemma 13, asserts that causal transformers can uniformly approximate exactly the class of continuous, causal, identifiable in-context mappings — no more, no less. Non-identifiable maps are provably out of reach.

What does it mean for a map to be non-identifiable? Suppose you have two different contexts that have the same prefix up to time t: μ_t = μ'_t (same tokens in the past), but differ in the future. An identifiable map at time t must produce the same function regardless of which full context it's embedded in — it cannot "peek" at future tokens to decide how to process the current one. Most functions one would naturally write are identifiable (any map that explicitly respects the causal mask), but there exist pathological continuous functions on P(Ω̃) × Ω̃ that are not identifiable — for example, a function that computes some global statistic of the entire sequence μ and uses it to transform x even when queried at time t < e(μ̄). Such a function could be approximate by an unmasked transformer but cannot be uniformly approximated by any causal transformer. The paper thus draws a principled architectural distinction: causal masking is not just a computational convenience but a fundamental constraint on the function class.

The Lipschitz context condition plays a different role: it is a technical requirement for the proof (ensuring compactness of the reduced space X_C^σ), not a structural necessity for causal transformers. However, the paper makes a compelling case that it is "not ad hoc": discrete measures with distinct time positions automatically satisfy it (setting C = diam(Ω)/min|t_i - t_j|), so it doesn't exclude any practical finite-sequence setting. The restriction only bites in the limit of continuously-distributed times — measures with Lebesgue-density in [0,1] — where μ̄({0}) ≥ σ would fail. The paper notes this can be relaxed (Remark 2), but the key point is that the condition is non-restrictive at all finite n, making Theorem 2 essentially unconditional for practical transformers.

The space-time lifting itself — embedding tokens in Ω × [0,1] with a time coordinate — is clever but might initially seem like a technical trick. What elevates it beyond a trick is how it restores the structure needed for the unmasked proof to apply: the time coordinate provides a total order (replacing permutation equivariance), the masked measure μ_t depends continuously on t (Lemma 10), and the reduced map Λ̄(μ_t, x) lives on a compact space (Lemma 5). The reduction Λ(μ, x, t) = Λ̄(μ_t, x) (Lemma 4) is the architectural insight: it shows that a causal in-context mapping is over-parameterized — the full (μ, x, t) can be compressed to (μ_t, x) without loss of information, precisely because of causality and identifiability. This reduction is what makes the Stone-Weierstrass argument possible: approximation over the (large) space Lip_C^σ(Ω̃) × Ω̃ reduces to approximation over the (smaller, compact) space X_C^σ, and the same algebraic machinery applies.

This innovation is a fundamental theoretical contribution rather than an incremental refinement. It gives the first rigorous characterization of the expressivity gap between masked and unmasked transformers, not in terms of specific benchmark tasks but in terms of the structural properties of the functions they can represent. It also provides architectural guidance: if you need to approximate a non-identifiable function, you must use unmasked attention (or a mechanism that breaks causality), because causal transformers are structurally incapable of it regardless of depth, width, or training data.

Innovation 4: Fixed Dimensions Independent of Both Context Size and Precision — Proving What Was Previously Assumed

Practical transformer deployments use a fixed embedding dimension (e.g., d_model = 512, 768, 1024, ...), a fixed number of heads, and process variable-length sequences without changing these hyperparameters. Yet prior universality results (Yun et al., 2019; Alberti et al., 2023) required either the embedding dimension or a latent width to grow with the sequence length n. This left a theoretical gap: was the fixed-dimension practice merely a convenient engineering heuristic, or was it theoretically justified? The paper closes this gap by proving that embedding dimension d + 3d' and head count d' are sufficient for any n and any precision ε — these quantities depend only on the input token dimension d and output dimension d', which are problem-level constants.

The independence from precision is equally important and even more subtle. In typical constructive universality proofs, the network width grows as ε → 0 because finer approximations require more basis functions. The Stone-Weierstrass approach avoids this: the algebra A is dense, so for any ε there exists some finite combination of algebra elements that achieves it. The combination may involve more products T and more summands N as ε decreases — meaning the depth grows — but the per-layer dimensions (embedding, heads) stay fixed. The paper doesn't provide explicit depth bounds (a limitation acknowledged in Remark 3), but the conceptual point stands: width and head count are universal constants, not functions of ε.

This is a fundamental architectural insight with practical implications. It means that when a practitioner chooses d_model = 512 for a task with d = 128-dimensional token embeddings and d' = 64-dimensional outputs, the theory says that d_model ≥ d + 3d' = 128 + 192 = 320 is sufficient for universal approximation capability — and d_model = 512 comfortably exceeds the bound. Adding more dimensions (d_model = 1024) increases capacity but is not required for the bare possibility of representing any continuous in-context mapping (at some depth). This provides a theoretical floor for practical architecture design, analogous to how the minimal width d+1 for deep ReLU networks (Hanin and Sellke, 2017) provides a theoretical minimum for MLP universality.

The specific bound d + 3d' emerges from the carry-and-accumulate construction: one d'-slot for the current affine projection, one for the running product, and one for the running sum accumulator, plus the original d-dimensional token. The proof shows this is sufficient; it does not prove it is necessary, so the bound should be understood as an upper bound on the minimal embedding dimension needed for the proof technique. Whether a more clever construction could reduce it to d + d' or d + 2d' is an open question.

The head count bound H ≤ d' reflects a similar constructive sufficiency: one head per output dimension, each operating in one dimension (d_head = 1), is enough to implement the per-coordinate scalar elementary mappings. The heads are fully decoupled — they read orthogonal coordinates (via the specially structured Q̃^h, K̃^h, Ṽ^h matrices) and write to orthogonal output dimensions (via W̃^h = e_h). This might seem wasteful compared to practical multi-head attention where heads operate in a shared, densely-projected space. The theorem doesn't claim this is the only or best way to achieve universality — only that it is a way, establishing theoretical possibility.

This innovation is incremental in statement but fundamental in theoretical significance: it upgrades transformers from "universal given dimension scaling" to "universal with fixed dimensions" in the hierarchy of neural network universality results. In the table comparing architectures (from the prior sections), this paper is the first entry for transformers with "Fixed width/dim? → Yes (d + 3d')" — a milestone that puts transformers on equal theoretical footing with deep ReLU networks and GNNs in terms of fixed-width expressivity.

The evidence is Theorem 1 itself: the statement explicitly asserts d_in(θ_ℓ) ≤ d + 3d', d_head(θ_ℓ) = k(θ_ℓ) = 1, H(θ_ℓ) ≤ d', with no dependence on n, ε, or any other problem-dependent parameter beyond d and d'. This is not a claim about what typical transformers achieve in practice — it's a claim about the architecture's capacity in principle, which is exactly what a universality theorem is meant to provide.

5. Experimental Analysis

Evaluation Methodology

Dataset. This paper presents a mathematical proof, not empirical experiments. There is no dataset, no training set, no test set, and no benchmark. The "evaluation" is a rigorous demonstration that the stated theorems follow logically from the axioms of measure theory, functional analysis, and the definitions of transformer architectures. The claims are validated through mathematical derivation rather than empirical measurement.
Base model(s). There are no trained models. The proof operates on the abstract definition of transformers as compositions of multi-head attention layers and MLPs (Equation 4), with parameters θ_ℓ (attention weights) and ξ_ℓ (MLP weights) treated as free variables whose existence is to be proven. No specific model family, scale, or pretraining procedure is involved.
Metrics. The "metric" is the uniform approximation error ε in the supremum norm:

$\sup_{(\mu, x) \in \mathcal{P}(\Omega) \times \Omega} \|\text{Transformer}(\mu, x) - \Lambda^*(\mu, x)\| \leq \varepsilon$

for the unmasked case (Theorem 1), and analogously over Lip_C^σ(Ω̃) × Ω̃ for the masked case (Theorem 2). The theorem statements guarantee that for any ε > 0, there exists a transformer architecture achieving this bound. No numerical values of ε are reported, because the proof is non-constructive — it establishes existence without providing explicit depth or width bounds as functions of ε.
Baselines. Not applicable. Universality theorems in approximation theory are absolute statements about function classes — they do not compare against alternative methods. The relevant "baseline" is the space of continuous in-context mappings C(P(Ω) × Ω; ℝ^{d'}) itself: the claim is that transformers are dense in this space. Prior universality results (Yun et al., 2019; Alberti et al., 2023) serve as points of comparison in the literature review but are not experimental baselines.
Generation budget / compute accounting. The proof provides explicit bounds on architectural dimensions — embedding dimension d_in ≤ d + 3d', head dimension d_head = 1, key/query dimension k = 1, head count H ≤ d' — that are independent of the approximation error ε and the number of tokens n. However, the proof does not bound the depth L (number of layers) or the total number of parameters |θ_ℓ|, |ξ_ℓ| in terms of ε. This is explicitly flagged as a limitation (Remark 3 in Appendix B.3): the Stone-Weierstrass step is existential, and the MLP that approximates the component-wise multiplication ⊙ introduces an ε-dependence on intermediate token magnitudes C̃_Γ, which are themselves not a priori bounded.
Cross-validation / statistical protocol. Not applicable. The proof uses two structural validations: (1) the algebra A separates points (via the injectivity of the generalized Laplace transform, Lemma 1), which ensures density via Stone-Weierstrass (Proposition 1); (2) the composition of causal maps preserves causality and identifiability (Lemmas 11–12), and identifiability is stable under uniform limits (Lemma 13), which ensures that the target function class is exactly the closure of causal transformers.

Main Quantitative Results

Because this is a theorem paper, there are no tables of accuracy scores, no figures with learning curves, and no ablation experiments measuring percentage-point changes. The "results" are the formal statements of Theorems 1 and 2, together with the lemmas that constitute their proof. What follows is a systematic walk through exactly what these mathematical statements assert, with precise references to where each component is established.

Theorem 1 (Unmasked Universality)

Statement (Section 3.1, p. 6). Let Ω ⊂ ℝ^d be compact and Λ*: P(Ω) × Ω → ℝ^{d'} be continuous (where P(Ω) has the weak* topology). Then for all ε > 0, there exist L and parameters (θ_ℓ, ξ_ℓ)_{ℓ=1}^L such that:

$\forall (\mu, x) \in \mathcal{P}(\Omega) \times \Omega, \quad |F_{\xi_L} \diamond \Gamma_{\theta_L} \diamond \ldots \diamond F_{\xi_1} \diamond \Gamma_{\theta_1} (\mu, x) - \Lambda^*(\mu, x)| \leq \varepsilon$

with d_in(θ_ℓ) ≤ d + 3d', d_head(θ_ℓ) = k(θ_ℓ) = 1, H(θ_ℓ) ≤ d'.

What it says, operationally. For any continuous in-context mapping — any function that takes a probability distribution of tokens plus a query token and produces an output vector — there exists a finite-depth transformer with per-layer embedding dimension at most d + 3d', at most d' heads, each head operating on 1-dimensional keys/queries/values, that approximates the target within ε uniformly over all possible contexts (any number of tokens, any distribution, any query within Ω).

The uniformity claim. The supremum is taken over all μ ∈ P(Ω) — not just empirical measures with some fixed n, but any probability measure on the compact token domain. This includes discrete measures with arbitrarily many tokens, as well as continuous measures. The L-layer transformer is fixed — it does not change when n changes. This is what makes the statement "universal for an arbitrary number of tokens" (Abstract).

Where the bounds come from.

d_in ≤ d + 3d': From the carry-and-accumulate construction in Lemma 9 (Appendix B.3). The token embedding at intermediate layers consists of four blocks: the d-dimensional original token x, a d'-dimensional affine projection F̃_{ξ_{t,n}}(x), a d'-dimensional product accumulator φ_{t,n}(x), and a d'-dimensional sum accumulator f_n(x). Total: d + d' + d' + d' = d + 3d'.
d_head = k = 1: From Equation (14) and the construction in Lemma 2. Each elementary mapping γ_λ operates in one dimension — the attention is over scalars with scalar key, query, and value. The d'-dimensional multi-head attention uses d' such heads in parallel, each of dimension 1.
H ≤ d': From Lemma 2 and Lemma 9. The d' vector components are approximated independently; each requires one head per coordinate.

What the theorem does NOT provide. No bound on the depth L or on the total number of parameters as a function of ε or d'. The proof establishes that such an L exists (via the existential nature of Stone-Weierstrass and the universality of MLPs for approximating ⊙), but L could theoretically be enormous. The Stone-Weierstrass step selects some finite T (number of products) and N (number of summands) in the cylindrical function approximation G(μ, x) (Equation 17) based on ε, but provides no relationship between ε and T, N. Each product-chain of length T and each summand n = 1, ..., N becomes a block of T layers in the deep architecture, so L = 1 (init) + N·T (blocks) + 1 (output projection). Without bounds on N and T, L is uncontrolled.

Additionally, the MLP parameters ξ_ℓ are not bounded. The MLP that approximates component-wise multiplication ⊙ in Lemma 8 depends on the radius R of the ball containing all intermediate token values, which depends on C̃_Γ (Equation 30), which depends on the parameters (θ̃_{t,n}, ξ̃_{t,n}) chosen during the Stone-Weierstrass step. This circular dependency means the MLP size could grow uncontrollably — the paper acknowledges this explicitly in Remark 3 (Appendix B.3): "providing the quantitative estimate for the MLP, Φ, is challenging."

Comparative significance. The key advance over Yun et al. (2019) is the dimension bound independent of n and ε. Yun et al. required embedding dimension O(n) for n tokens; this paper requires at most d + 3d' regardless of n. The price paid is the loss of depth control and the restriction to continuous targets (Yun et al. handle discontinuous sequence-to-sequence maps, which requires larger dimension). This is a meaningful tradeoff: the paper prioritizes the "any number of tokens" aspect of universality, which is arguably more fundamental to the transformer's defining property of variable-length context processing.

Theorem 2 (Masked/Causal Universality)

Statement (Section 4.1, p. 8). Let Λ* be a continuous (on Lip_C^σ(Ω̃) with weak* topology) and causal identifiable in-context mapping (Definition 3). Then for all ε > 0, there exist L and parameters (θ_ℓ, ξ_ℓ)_{ℓ=1}^L such that:

$\forall (\mu, x, t) \in \text{Lip}_C^\sigma(\tilde{\Omega}) \times \tilde{\Omega}, \quad |F_{\xi_L} \diamond \Gamma_{\theta_L} \diamond \ldots \diamond F_{\xi_1} \diamond \Gamma_{\theta_1} (\mu, x, t) - \Lambda^*(\mu, x, t)| \leq \varepsilon$

with the same dimension bounds as Theorem 1: d_in(θ_ℓ) ≤ d + 3d', d_head(θ_ℓ) = k(θ_ℓ) = 1, H(θ_ℓ) ≤ d'.

What it says, operationally. The same fixed-dimension, fixed-head-count architecture is universal for causal in-context mappings — but only those that are continuous, causal, and identifiable, and only on contexts that are C-Lipschitz in time.

Additional hypotheses and their roles.

Lipschitz contexts μ ∈ Lip_C^σ (Definition 1). The conditional token distribution μ(·|t) must be C-Lipschitz in t under W_2, and the time marginal must have mass ≥ σ at t = 0. These conditions ensure: (a) the set of masked measures X_C^σ = {(μ_t, x)} is compact (Lemma 5, Appendix C.3), enabling Stone-Weierstrass; (b) the masked measure μ_t is well-defined at all t ∈ [0,1] (continuous extension to t = 0, Lemma 10). The condition is automatically satisfied by discrete measures with distinct times (using C = diam(Ω) / min|t_i - t_j| and σ = 1/n), so it is non-restrictive for standard finite-sequence transformers. The restriction only excludes some continuous-time measures.
Causality (Definition 3, Equation 20). Λ(μ, x, t) = Λ(μ_t, x, t) — the output at time t depends only on tokens up to t. This is trivially satisfied by all masked transformers and is a natural requirement for sequential prediction. Any target that violates causality is structurally out of scope.
Identifiability (Definition 3, Equation 21). μ_t = μ_{t'} implies Λ(μ_t, ·, t) = Λ(μ_{t'}, ·, t') — if the masked contexts coincide, the functions they induce are identical. Lemma 11 proves masked attention satisfies this. Lemma 12 proves composition preserves it. Lemma 13 proves uniform limits preserve it.

The sharpness claim (Remark 1, Section 4.1). The statement "this hypothesis is sharp and cannot be weakened" regarding identifiability is a genuine theoretical result embedded in the theorem. It is not merely an assumption — Lemma 13 shows that any uniform limit of identifiable maps is identifiable. Since transformers are identifiable (Lemma 11), any map that can be uniformly approximated by causal transformers must be identifiable. Therefore, Theorem 2 is not just a sufficiency result — it is a characterization: causal transformers can uniformly approximate exactly the continuous, causal, identifiable in-context mappings on Lipschitz contexts. Non-identifiable maps cannot be approximated, regardless of depth or width. This is a rare completeness result in neural network approximation theory.

What makes the masked proof different from the unmasked proof beyond the added hypotheses. The structural reduction Λ(μ, x, t) = Λ̄(μ_t, x) (Lemma 4) compresses the approximation problem from the full domain Lip_C^σ × Ω̃ to the reduced space X_C^σ. This is possible because of causality and identifiability — without them, the value at time t would depend on information outside the masked measure μ_t. Once reduced, the proof proceeds identically to the unmasked case (Proposition 2, which mimics Proposition 1 with μ_t in place of μ). The compactness of X_C^σ is the only new technical hurdle (Lemma 5, using Arzelà-Ascoli for the conditional distributions).

The time-marginal mass condition μ̄({0}) ≥ σ (Remark 2). This is noted as relaxable: the proof carries through for any fixed time marginal μ̄ = ν provided 0 ∈ supp(ν). The condition exists to ensure μ̄([0, t]) is bounded away from zero near t = 0, keeping the masked measure μ_t = (\mathbf{1}_{[0,t]} / \overline{μ}([0, t])) μ well-defined and continuous in t. Relaxing to fixed marginals would make the theorem apply to any choice of ν, including absolutely continuous ones, though the Lipschitz condition would still restrict which ν-marginal measures are admissible.

Lemma 1 (Injectivity of the Generalized Laplace Transform) — The Technical Core

Statement (Appendix B.1, Lemma 7). If L(μ)(a, c) = L(μ')(a, c) for all a ∈ ℝ^d and all c ∈ ℝ, then μ = μ', where:

$\mathcal{L}(\mu)(a, c) := \frac{\int e^{c \langle a, y \rangle} \langle a, y \rangle \, d\mu(y)}{\int e^{c \langle a, z \rangle} \, d\mu(z)}$

What this means. The function L(μ) — the expected value of ⟨a, y⟩ under an exponentially tilted version of μ — uniquely determines μ. This is the step in the Stone-Weierstrass point-separation argument where γ_λ(μ, x) = γ_λ(μ', x') for all λ is shown to imply (μ, x) = (μ', x'). Without injectivity, the algebra A would not separate points and Stone-Weierstrass would not apply.

Proof architecture.

One-dimensional base case (Lemma 6). Define L_k(μ)(c) = ∫ e^{cy} y^k dμ(y) / ∫ e^{cz} dμ(z). The recursion L_k'(c) = L_{k+1}(c) - L_k(c)L_1(c) follows from differentiating the ratio. If L_1(μ)(c) = L_1(μ')(c) for all c, then recursively L_k(μ)(c) = L_k(μ')(c) for all k ≥ 1, c. Setting c = 0 gives ∫ y^k dμ(y) = ∫ y^k dμ'(y) — all integer moments match. On a compact interval, moment equality implies measure equality (the classical Hausdorff moment problem).
Lifting to d dimensions (Lemma 7). For any unit vector e ∈ S^d, let μ_e = (P_e)_♯ μ be the pushforward under projection P_e(x) = ⟨x, e⟩. Then L(μ)(e, c) = L_1(μ_e)(c). Equality of L(μ)(a, c) for all a implies equality of L_1(μ_e)(c) for all directions e, hence μ_e = μ'_e for all e by the one-dimensional case. The injectivity of the Radon transform — a probability measure on ℝ^d is determined by its one-dimensional marginals — yields μ = μ'.

Why the exponential kernel is essential. The proof relies on the analyticity of c ↦ L(μ)(a, c) and the fact that its derivatives at c = 0 generate the moment sequence. If the attention kernel were a dot product ⟨Qx, Ky⟩ without the exponential, the "temperature" parameter c would not appear as a multiplicative factor inside an exponential, and the connection to moment-generating functions would be lost. The softmax's exp(·) is not merely a convenient choice — it is structurally required for this proof technique. This reveals a fundamental mathematical role for the exponential in attention: it provides the analytic structure needed for the attention mechanism to separate probability distributions.

Ablation Studies and Robustness Checks

There are no traditional ablation studies in a theorem paper. However, the proof structure contains several internal consistency checks and alternative-path analyses that serve an analogous role: verifying that the proof's assumptions are minimal, that relaxing them breaks the argument, and that alternative approaches would encounter specific barriers.

Identifiability as a necessary condition (Lemma 13): The proof does not merely assume identifiability of the target Λ* — it proves that this assumption cannot be removed. Lemma 13 establishes that the uniform limit of identifiable maps is identifiable. Since causal transformers are identifiable (Lemma 11) and uniform limits of transformer compositions would be the only functions they can approximate, any non-identifiable Λ* is provably not approximable by any deep causal transformer, regardless of depth, width, or parameter count. This is the mathematical equivalent of a "negative result" ablation: attempting to prove universality for non-identifiable targets would fail, and Lemma 13 explains exactly why.

Lipschitz context necessity for compactness (Lemma 5 proof breakdown). The proof of Lemma 5 (Appendix C.3) — that X_C^σ is compact — crucially relies on the Arzelà-Ascoli theorem applied to the conditional maps s ↦ μ_n(·|s), which requires equicontinuity. The C-Lipschitz condition provides this uniform equicontinuity. Without it, one could have a sequence of space-time measures whose conditional distributions oscillate arbitrarily rapidly in s, preventing extraction of a uniformly convergent subsequence, and X_C^σ would not be compact. The Stone-Weierstrass theorem requires compactness of the underlying space, so dropping the Lipschitz hypothesis would cause the entire density argument to collapse — not just weaken the bound, but prevent the proof from functioning at all. The paper acknowledges this in Remark 1: "This limitation is essential for ensuring that the set of masked contexts μ_t is compact."

The μ̄({0}) ≥ σ condition and its relaxability (Remark 2). The proof uses μ̄({0}) ≥ σ to guarantee that μ_t is well-defined as t → 0 (the denominator μ̄([0,t]) does not vanish too quickly). Remark 2 observes that fixing the time marginal to any ν with 0 ∈ supp(ν) would work equally well — the mass at 0 is not essential, only that there is some lower bound on μ̄([0,t]) near t = 0. This is a robustness observation: the specific σ-mass condition is an artifact of keeping the statement simple, not a fundamental restriction. An alternative formulation with fixed time marginal μ̄ = ν would cover absolutely continuous ν (e.g., Lebesgue measure) provided ν([0,t]) is controlled near 0.

The d + 3d' embedding dimension: what if we tried fewer dimensions? The carry-and-accumulate construction (Lemma 9, the diagram in Appendix B.3) uses three separate d'-dimensional registers: affine projection, product accumulator, sum accumulator. The proof demonstrates sufficiency of d + 3d'. It does not prove necessity — this is not a lower bound. However, the construction provides insight into why d + 2d' would likely be insufficient for this particular proof strategy: the product accumulator and sum accumulator serve fundamentally different purposes (one is multiplicative — storing intermediate products — the other is additive — accumulating finished products), and they must both persist across layers. The affine projection register is needed because the MLP F_{ξ_{t,n}} (Equation 31) overwrites it with the next projection while computing Φ(current_attention, previous_product) in a separate register. Without the third register, temporal multiplexing (using one register for two purposes at different times) might be possible but would require additional layers to recompute overwritten values — a depth-for-width tradeoff that the current proof does not explore. The paper does not claim d + 3d' is minimal; it is an upper bound established by an explicit construction.

The H ≤ d' head count and the possibility of head sharing. The construction uses one head per output dimension, each operating on a single coordinate (d_head = 1). Could fewer heads suffice? The heads are completely decoupled in this construction — head h reads coordinate h and writes to output dimension h. Sharing heads across coordinates would require them to attend to multiple dimensions simultaneously, which this construction deliberately avoids to maintain the algebraic decoupling that enables per-coordinate approximation. Whether a more sophisticated construction could achieve universality with o(d') heads is an open question, but the proof does not address it — the bound H ≤ d' is presented as a construction, not a lower bound.

The non-constructive depth: what prevents explicit bounds (Remark 3). The standard approach to quantitative bounds would require estimating: (1) the T and N from Stone-Weierstrass in terms of ε (rates of approximation for cylindrical functions), (2) the radius R of intermediate token values in terms of the parameters chosen in step (1), (3) the depth/width of the MLP Φ that approximates ⊙ on the ball of radius R to accuracy ε/(N·T). Step (1) is notoriously difficult — Stone-Weierstrass gives no rate information at all. Step (2) creates a circular dependency: R depends on C̃_Γ (Equation 30), which depends on the parameters (θ̃_{t,n}, ξ̃_{t,n}) from step (1). Even if step (1) were quantitative, step (2) would require bounding the growth of token magnitudes through layers, which is a complex dynamical question. The paper's openness about this limitation (Remark 3) is analogous to an ablation that identifies which component of the proof prevents quantitative bounds — it is the combination of existential density (Stone-Weierstrass) with the need to approximate nonlinear operations (multiplication) by MLPs whose complexity depends on input magnitude, which in turn depends on the density-approximation parameters.

Critical Assessment

This section evaluates whether the mathematical results established by the paper genuinely support the claims made in the abstract, introduction, and theorem statements. Since the paper is a proof rather than an empirical study, the assessment focuses on logical completeness, gap analysis, and the match between what is claimed and what is demonstrated.

Claim: "Deep transformers are universal and can approximate continuous in-context mappings to arbitrary precision, uniformly over compact token domains." (Abstract, Theorem 1)

What is actually proved. Theorem 1 establishes that for any continuous Λ*: P(Ω) × Ω → ℝ^{d'}, there exists a finite composition of attention layers and MLPs (with the stated dimension bounds) that approximates Λ* within ε in the uniform norm. The proof is logically complete: Proposition 1 (algebra density via Stone-Weierstrass) → Lemma 2 (vector-valued extension) → Lemmas 3, 8, 9 (transformer realization). Each step is mathematically rigorous; there are no hidden assumptions or gaps.

Strengths. The result genuinely achieves what prior transformer universality results did not: the approximating architecture has embedding dimension and head count independent of both the number of tokens n and the approximation error ε. This is a meaningful theoretical advance that closes a recognized gap in the literature. The measure-theoretic formulation makes the statement precise in a way that "handles arbitrary-length contexts" cannot be in a matrix-based formulation. The proof technique (Stone-Weierstrass on an algebra of attention-derived functions) is novel for transformers and provides a different angle on expressivity than the constructive step-function approach of Yun et al. (2019).

Weaknesses and qualifications.

No control over depth. The theorem asserts existence of some finite L, but provides no bound on L in terms of ε, d, or d'. For a practitioner, knowing that a transformer could in principle approximate a function with 10^12 layers is far less useful than knowing it can do so with, say, O(d' log(1/ε)) layers. The paper acknowledges this (Section 5, "a limitation of our method is that it is not quantitative"; Remark 3 in Appendix B.3) but does not provide even a weak bound. This significantly limits the theorem's practical relevance: universality without complexity bounds is a pure existence result, akin to knowing that a sufficiently large lookup table can represent any function — true but unhelpful for architecture design.
The embedding dimension bound may not be tight. d + 3d' is shown sufficient, but no argument is made for necessity. It is possible that d + d' or d + 2d' would suffice with a more clever construction. The theorem should be understood as providing an upper bound, not a characterization of minimal width.
Compactness restricts the domain. The theorem requires Ω ⊂ ℝ^d to be compact. This is standard in universality theorems (continuous functions on non-compact domains cannot be uniformly approximated by finite-parameter families), but it means the result does not directly apply to unbounded token domains (e.g., token embeddings that can grow arbitrarily large through layer normalization-free architectures). In practice, trained transformers operate on bounded floating-point ranges, so this is a mild restriction.
The MLP dependence on ε is uncontrolled. The substitution of component-wise multiplication ⊙ by an MLP Φ (Lemma 8) introduces an unquantified dependence: Φ must approximate ⊙ on a ball whose radius R depends on the parameters from the Stone-Weierstrass step. This means the per-layer MLP size could in principle be enormous, even if the attention dimensions are modest. The theorem's dimension bounds (d_in ≤ d + 3d', d_head = 1) only constrain the attention mechanism, not the MLPs. A complete accounting of architectural resources would need to also bound the MLP width and depth, which the theorem does not do.

Claim: "For a fixed precision, a single transformer can operate on an arbitrary (even infinite) number of tokens." (Abstract)

What is actually proved. The statement is supported in the sense that the approximating transformer's architecture does not depend on the particular μ being processed — it works for any μ ∈ P(Ω), including discrete measures with arbitrarily large n and continuous measures (the "infinite token" limit). The same transformer processes all of them.

Qualifications. The "infinite number of tokens" claim requires careful interpretation. For a continuous measure μ (e.g., a density over Ω), the attention integrals in Equation (9) are well-defined mathematically, but there is no computational procedure to evaluate them exactly — they would need to be approximated by sampling or numerical integration. The theorem is about representational capacity (what functions can be expressed by the composition), not computability (whether there exists an algorithm to evaluate the composition in finite time). This distinction is standard in approximation theory but worth flagging: the "infinite token" claim is about the mathematical definition of the transformer as a mapping on P(Ω), not about running a transformer on an infinite sequence in practice.

Claim: "It operates with a fixed embedding dimension of tokens (this dimension does not increase with precision) and a fixed number of heads (proportional to the dimension)." (Abstract)

What is actually proved. d_in ≤ d + 3d' and H ≤ d' are established as upper bounds that hold for all ε. Both are independent of ε and n.

Qualifications. "Proportional to the dimension" is accurate: H ≤ d', which is linear in the output dimension. However, d' itself is a problem parameter (the dimension of the target space), not a model hyperparameter one can freely reduce. For a task requiring d' = 1000-dimensional outputs, the bound says d_in ≤ d + 3000 and H ≤ 1000 suffice — but these numbers are large enough that the "fixed" qualifier, while technically true, may be less practically reassuring than it sounds for high-dimensional output tasks.

Claim: "The use of MLPs between multi-head attention layers is also explicitly controlled." (Abstract)

What is actually proved. The MLPs in the construction serve two purposes: (1) affine projections F_{ξ_{t,n}} that compute the linear maps ⟨a, x⟩ + b needed for elementary mappings, and (2) the multiplication-approximating MLP Φ. The first type is exactly controlled (they are affine, with explicitly parameterized dimensions). The second type is "controlled" only in the sense that MLPs are known to be universal approximators — the specific MLP architecture for Φ is not bounded, as discussed above.

Qualifications. The word "controlled" might suggest that the MLP dimensions are small or explicitly bounded, which is not the case for Φ. A more precise description would be "the attention dimensions are explicitly bounded, while the MLPs are standard universal approximators whose complexity depends on the target function in an uncontrolled way."

Claim: The masked setting requires "stronger regularity hypothesis on the contexts, namely that they are Wasserstein-Lipschitz with respect to time, which is needed to cope with the constraint of causality." (Abstract)

What is actually proved. Theorem 2 establishes universality on Lip_C^σ with the identifiability hypothesis. The proof demonstrates that these conditions are sufficient and — in the case of identifiability — necessary (Lemma 13). The Lipschitz condition is shown to be automatically satisfied by finite discrete measures with distinct times (Section 4.1, paragraph after Definition 1), so the statement holds for any practical finite-sequence setting.

Qualifications. The Lipschitz condition does restrict the class of continuous-time measures that are covered. Measures with density in [0,1] whose conditional distributions are not Lipschitz in time (e.g., discontinuous jumps in the token distribution at specific times) are excluded. Whether this is a significant restriction depends on the application: for uniform time grids (t_i = i/n), the Lipschitz constant grows as O(n), so the theorem covers all finite n but the constant C degrades with sequence length. A sequence-length-independent Lipschitz bound would require the tokens to vary slowly with position, which may not hold for arbitrary data.

Overall assessment of the paper's contribution relative to its claims. The paper delivers on its primary theoretical contribution: a rigorous proof that fixed-dimension transformers are universal approximators of continuous in-context mappings, handling both unmasked and masked attention in a unified framework. The proof is novel (algebraic via Stone-Weierstrass rather than constructive piecewise-constant), the measure-theoretic formulation is a genuine conceptual advance, and the identifiability characterization for causal transformers is a sharp result that goes beyond typical sufficiency theorems.

The principal weakness is the lack of quantitative depth bounds, which limits the result's practical engineering implications. A universality theorem that says "there exists a deep enough transformer" without saying how deep is, in some sense, only half the story — it establishes possibility but not feasibility. The paper is transparent about this limitation and frames it as a starting point for future quantitative work (Section 5: "Using, for instance, the Wasserstein distance between token distributions could be a way to impose smoothness on the map to obtain quantitative bounds"). This honesty is commendable, but it means the paper is best understood as providing the conceptual foundation and mathematical language for transformer expressivity, with the quantitative theory left to future development.

A secondary limitation is that the universality is established for the architecture as a mathematical object, not for transformers as learned by gradient descent. The theorem says nothing about whether training procedures can find the parameters whose existence it proves, or about the implicit biases that guide learning toward particular solutions. This is standard for universality theorems across all neural network architectures (Cybenko's theorem does not address learnability), but worth noting since the abstract's phrasing "deep transformers are universal" could be misread as a statement about trained models rather than about architectural capacity.

6. Limitations and Trade-offs

6.1 The Proof Is Non-Quantitative — No Depth or Width Bounds Are Provided

The assumption or constraint. The entire universality argument is existential: it proves that for any continuous in-context mapping Λ* and any ε > 0, there exists some finite-depth transformer achieving ε-uniform approximation. It provides no functional relationship between the approximation error ε and the architectural resources required — depth L, MLP width, total parameter count, or training data requirements. The authors explicitly flag this as their primary weakness:

"A limitation of our method is that it is not quantitative." (Section 5, Conclusion and Discussion)

And in Remark 3 (Appendix B.3):

"Our proof relies on the approximation of the map along each dimension and the use of a commuting architecture... This results in a growth of the number of heads proportional to the dimension. Lowering this dependency would require the development of new proof techniques beyond the use of the Stone-Weierstrass theorem. ... providing the quantitative estimate for the MLP, Φ, is challenging."

The consequence. A universality theorem without complexity bounds tells us that the architecture is capable in principle, but says nothing about whether that capability is achievable with architectures of practical scale. In the worst case, the depth L = 1 + N·T + 1 required by the carry-and-accumulate construction (Lemma 9, Appendix B.3) could be astronomical: the Stone-Weierstrass step selects some finite T (products per summand) and N (number of summands) based on ε, but provides no control over how T and N grow as ε → 0. The multiplication-approximating MLP Φ introduces a circular dependency that prevents even asymptotic estimates: the radius R of the compact set on which Φ must approximate ⊙ depends on C̃_Γ (the bound on intermediate token magnitudes in Equation 30), which depends on parameters (θ̃_{t,n}, ξ̃_{t,n}) chosen during the Stone-Weierstrass step, which in turn depends on ε. This means the MLP complexity could explode uncontrollably without violating any theorem statement — the dimension bounds (d_in ≤ d + 3d', H ≤ d') only constrain the attention mechanism, not the MLPs that constitute the bulk of parameters in practical transformers.

For a practitioner, this is the difference between "transformers could theoretically represent this function" and "transformers with 12 layers and 768-dimensional embeddings can represent this function." The former is a completeness guarantee; the latter is actionable architecture guidance. This paper provides only the former.

What evidence exists in the paper. Remark 3 in Appendix B.3 is the sole discussion. The paper does not attempt to bound L, the MLP architecture, or even provide scaling heuristics. This is not a hidden flaw — it is an inherent limitation of the Stone-Weierstrass proof technique, which is fundamentally non-constructive: it proves density without providing approximation rates.

Mitigation status. The paper suggests a direction for future work — "Using, for instance, the Wasserstein distance between token distributions could be a way to impose smoothness on the map to obtain quantitative bounds" (Section 5) — but performs no analysis in this direction. The suggestion is plausible (imposing Lipschitz or Hölder continuity on the target map could enable rate estimation via known quantitative Stone-Weierstrass or Jackson-type theorems), but it remains an open problem. No mitigation is provided within the paper itself.

6.2 The Difficulty Estimation Cost Is Unaccounted for — But for This Paper, the Analogous Hidden Cost Is the MLP Approximation of Multiplication

Note on adaptation. This limitation template typically addresses "hidden costs" in systems papers (e.g., unmodeled latency, preprocessing overhead). For this theorem paper, the analogous hidden complexity is the MLP that approximates component-wise multiplication ⊙ (Lemma 8). The theorem's headline dimension bounds (d_in ≤ d + 3d', d_head = 1, H ≤ d') describe only the attention layers. The MLP Φ: ℝ^{2d'} → ℝ^{d'} that approximates the Hadamard product x ⊙ y has unbounded complexity — its depth, width, and parameter count are not constrained by any theorem statement, yet it is essential to the construction. The paper's "ε-approximation" guarantee would be vacuous if Φ required a GPT-4-scale MLP to achieve the required precision on the required domain.

The assumption or constraint. Lemma 8 invokes standard MLP universality: for any continuous function on a compact set, there exists an MLP approximating it. The compact set is the ball of radius R (determined by C̃_Γ from Equation 30), and the target accuracy is ε/(N·T) (so that the cumulative error across all product replacements stays within ε). The MLP's complexity depends on R (larger domain → more capacity needed), the modulus of continuity of ⊙ on that domain (grows with R), and the target accuracy ε/(N·T) (smaller error → more capacity). All three of these quantities depend on the Stone-Weierstrass parameters (N, T, θ̃, ξ̃), which themselves depend on ε through the non-quantitative density argument.

The consequence. The theorem's resource guarantees are incomplete. A complete accounting of the transformer's capacity would need to specify not just attention dimensions but also MLP architecture bounds — at minimum, the depth and width of each MLP layer. Without these, one cannot compare the constructed transformer's total parameters or FLOPs to practical architectures. It is conceivable that for a target function of moderate complexity and modest ε, the required MLP is larger than any model ever trained — the theorem would still hold, but the practical message (that "fixed dimensions suffice") would be misleading because the fixed dimensions of the attention layers are only part of the story. The MLPs could dwarf them.

What evidence exists in the paper. The paper contains no analysis of the MLP complexity. Appendix B.3 (Remark 3) explicitly acknowledges the difficulty: "providing the quantitative estimate for the MLP, Φ, is challenging." The construction in Lemma 9 treats the MLPs F_{ξ_{t,n}} as black boxes — they are assumed to exist by universality, but their internal structure is never specified. The paper's dimension bounds are therefore best understood as bounds on the attention-specific components of the architecture, not on the total parameter count.

Mitigation status. None. The paper does not even speculate on the MLP complexity beyond the remark that quantifying it is challenging. The question of whether the multiplication-approximating MLPs can be reasonably small (e.g., poly(d') parameters) or whether they inherently require exponential capacity is left entirely open. This is a fundamental gap between the paper's theoretical contribution and its practical interpretation.

6.3 The Hardest Problems Are Provably Unreachable — The Lipschitz Requirement Excludes Rapidly-Varying Sequential Contexts

The assumption or constraint. Theorem 2 (masked/causal universality) applies only to contexts in Lip_C^σ(Ω̃) — space-time measures whose conditional token distributions μ(·|t) are C-Lipschitz continuous in time under the Wasserstein-2 distance. The Lipschitz constant C appears in the theorem statement as a fixed parameter, and the approximation guarantee is uniform over the class Lip_C^σ for that specific C. For discrete measures with n tokens at uniform times t_i = i/n, the Lipschitz constant satisfies C ≈ n · diam(Ω) (since neighboring tokens can differ by up to diam(Ω) while Δt = 1/n, giving W_2 / Δt ≈ diam(Ω) · n). This means that the Lipschitz constant grows with sequence length — the theorem covers all finite n, but the class Lip_C expands as C increases, and a single transformer's approximation guarantee only holds for one C (or a bounded range of C).

The consequence. For a fixed transformer (fixed depth, fixed parameters), the uniform approximation guarantee only applies to contexts whose conditional distributions vary at a rate bounded by C. If the test data contains sequences where the token distribution changes abruptly — a sudden topic shift in text, a scene cut in video, a regime change in time-series — and the Lipschitz constant C of that data exceeds the C for which the approximating transformer was constructed, the approximation guarantee does not apply. The transformer may fail to generalize to such contexts, even though they are perfectly valid inputs for practical causal transformers (which process any sequence regardless of how rapidly its statistics vary).

More concretely: Theorem 2 proves that for each C, there exists some transformer that handles contexts with Lipschitz constant C. It does not prove that there exists a single transformer that handles all C uniformly, or that handles contexts without any Lipschitz bound. A practitioner deploying a causal transformer does not pre-filter inputs for Lipschitz regularity — the model sees whatever sequences come in, with potentially unbounded variation rates. The theorem provides no guarantee for this realistic scenario.

What evidence exists in the paper. Section 4.1 explicitly acknowledges that the Lipschitz condition is needed for compactness of X_C^σ: "This limitation is essential for ensuring that the set of masked contexts μ_t is compact, which allows us to apply the Stone-Weierstrass theorem" (Remark 1). The paper notes that discrete sequences with distinct times automatically satisfy the condition (with a C that grows with n), but does not address the C-dependence of the approximating transformer. The compactness proof (Lemma 5, Appendix C.3) relies crucially on the Arzelà-Ascoli theorem, which requires equicontinuity of the family {s ↦ μ_n(·|s)} — exactly the C-Lipschitz condition.

Mitigation status. None within the paper. The authors mention that fixing the time marginal μ̄ = ν (Remark 2) could relax the σ-mass condition, but this does not address the Lipschitz smoothness requirement. The fundamental tension — compactness requires equicontinuity, but practical sequential data may not be equicontinuous — is not resolved. This limitation is structural to the Stone-Weierstrass proof approach and would require a different mathematical framework (perhaps a localized approximation theory) to address.

6.4 Single "Model Family" — The Proof Applies Only to the Specific Softmax Attention Parameterization

The assumption or constraint. The entire proof — specifically, the point-separation argument in Lemma 1 and Proposition 1 — depends on the exponential form of the attention kernel: exp(c · query · key). This is the standard softmax attention, but the transformer literature has explored numerous alternative attention mechanisms: linear attention (where exp is replaced by a kernel feature map φ(q)ᵀφ(k)), ReLU-based attention, polynomial attention, Fourier attention, and various sparse approximations. The proof technique would not carry over to these variants because the connection to moment-generating functions (Lemma 6: L_k(μ)(c) = ∫ e^{cy} y^k dμ(y) / ∫ e^{cz} dμ(z)) depends on the analyticity of the exponential and the fact that its derivatives at c = 0 generate moments. A linear kernel φ(q)ᵀφ(k) would not provide an analogous parameter c whose variation generates a complete set of statistics.

The consequence. The universality result is architecture-specific, not a generic property of attention-based models. If a practitioner uses linear attention for efficiency, or if an architecture designer proposes a novel attention variant, Theorem 1 provides no guarantee. This is a narrower result than the abstract's phrasing "Transformers are Universal In-context Learners" might suggest — the title's "Transformers" refers specifically to the Vaswani et al. (2017) multi-head softmax attention architecture, not to the broader family of transformer-like models. A linear-attention transformer might still be universal (and some evidence from the in-context learning literature suggests it can implement gradient descent), but this paper's proof does not establish it.

Furthermore, even within the standard softmax family, the proof applies to the specific parameterization in Equation (9) with a single temperature scaling 1/√k. Practical transformers often separate the key-query dot product from the softmax temperature, use per-head learned temperatures, or apply normalization before the softmax — the proof would need to be adapted for each such variant.

What evidence exists in the paper. The point-separation proof in Lemma 1 (Appendix B.1) is explicitly built around the exponential: the recursion L_k'(c) = L_{k+1}(c) - L_k(c)L_1(c) uses differentiation of e^{cy} with respect to c, and the evaluation at c = 0 recovers moments ∫ y^k dμ(y). Section 3.2 defines the elementary mapping γ_λ with the specific form exp(c(⟨x,a⟩+b)(⟨y,a⟩+b)), which is the one-dimensional restriction of the standard softmax kernel. There is no discussion of whether the proof extends to other kernels, and the paper does not claim universality for broader attention classes.

Mitigation status. None. The paper does not discuss alternatives to the softmax kernel or attempt to generalize the proof. This is not presented as a limitation — it is simply the scope of the theorem — but a practitioner deciding between standard softmax attention and a more efficient variant should be aware that the paper's universality guarantee applies only to the former.

6.5 No Account of Positional Encoding — The Token Representation Assumes Permutation-Invariant Encoding

The assumption or constraint. The entire measure-theoretic framework encodes token sets as probability measures μ = (1/n) Σ δ_{x_i}, which erases token order. This is appropriate for the unmasked setting (bidirectional encoders, vision transformers) where permutation equivariance is a feature, but it is insufficient for the masked setting without additional structure. The paper addresses this through the space-time lifting Ω × [0,1] (Section 2.3), attaching a scalar time coordinate t_i ∈ [0,1] to each token. However, this treats positional information as simply a one-dimensional continuous parameter that orders tokens — it does not model positional encodings as they are implemented in practice (sinusoidal, learned absolute, or relative position biases). In real transformers, the token embedding x_i is typically a sum of a content embedding and a position embedding: x_i = content_i + pos_i. The positional encoding is not a separate coordinate but is mixed into the same vector space as the content, which fundamentally changes how attention interacts with position.

The consequence. The theorem's space-time formulation is a mathematical idealization that captures causal ordering but misses a key architectural feature: position-content entanglement. In practice, attention scores ⟨Q x_i, K x_j⟩ mix positional and content information through the same dot product, whereas the paper's Ω × [0,1] formulation keeps them separate (the time coordinate only enters through the indicator \mathbf{1}_{[0,t]}(r) in Equation 12). This separation means the proof's masked attention computes similarity based purely on content: exp(⟨Qx, Ky⟩) is evaluated on the spatial component only, with time serving only to mask. A real transformer's attention scores depend on position through the same mechanism as content (the dot product of position-encoded embeddings), which creates interactions between position and content similarity that the paper's model does not capture.

This difference is not cosmetic — it affects what functions can be represented. A transformer with additive sinusoidal positional encodings can learn attention patterns like "attend to the token 5 positions back" without any content dependence; the paper's space-time model would require encoding this purely through the time coordinate, which is not directly accessible to the attention mechanism (it only appears in the mask). Whether the universality result extends to standard positional encoding schemes is not addressed.

What evidence exists in the paper. The paper's formulation of masked attention (Equation 12) uses \mathbf{1}_{[0,t]}(r) for causal masking but does not incorporate positional encodings into the token vectors. The related work section mentions: "Another line of work studies the impact of positional encoding on their expressivity [26]" (Luo et al., 2022) but does not analyze how positional encodings would affect the proof. The space-time lifting is introduced as a way to "restore invariance" (Section 2.3) broken by causal masking, not as a model of positional encoding.

Mitigation status. None. The paper does not claim its model covers positional encodings, and it is positioned as a theoretical contribution about the core attention mechanism. However, a practitioner reading "transformers are universal in-context learners" might reasonably assume this includes transformers as actually implemented, with positional encodings. The gap between the theorem's space-time separable model and the entangled position-content representations of real transformers is an unaddressed limitation that could affect the practical applicability of the result, particularly for length-generalization questions (which are known to be sensitive to positional encoding design).

6.6 The Target Function Class Is Restricted to Continuous Maps — Discontinuous In-Context Computations Are Excluded

The assumption or constraint. Both Theorems 1 and 2 require the target in-context mapping Λ* to be continuous — Theorem 1 with respect to the weak* topology on P(Ω) and the ℓ₂ topology on Ω; Theorem 2 additionally on Lip_C^σ(Ω̃). The Stone-Weierstrass theorem applies only to continuous functions on compact domains, so this continuity assumption is mathematically essential to the proof strategy. However, many functions of practical interest in sequence modeling are not continuous under the weak* topology. For example, a function that checks whether the context contains a specific token ("does the prompt include the word 'Paris'?") is discontinuous: an arbitrarily small perturbation (in Wasserstein distance) can add or remove that token, causing a discrete jump in the output. A function that counts the number of tokens satisfying a predicate is similarly discontinuous as the number of tokens varies. Sorting, searching, and discrete reasoning operations — precisely the kinds of "in-context computation" that recent empirical work has studied — often involve discontinuities.

The consequence. The universality result does not apply to many functions that a practitioner might want a transformer to learn in-context. This is a fundamental limitation of the proof technique (not just a technical oversight): uniform approximation on a compact domain forces continuity of the limit function. A discontinuous function cannot be uniformly approximated by continuous functions. Therefore, the theorem cannot be extended to discontinuous targets without changing the topology (e.g., using a stronger topology that makes the target continuous) or relaxing the approximation notion (e.g., approximation in measure rather than uniformly). Both would require a fundamentally different proof approach.

Crucially, this distinguishes the paper's result from Yun et al. (2019), who proved that transformers can approximate any sequence-to-sequence function, including discontinuous ones, at the cost of requiring the embedding dimension to grow with sequence length. The current paper trades off generality of the target class (continuous only) for dimension independence. This is a real tradeoff, not a strict improvement: a practitioner who needs to represent discontinuous in-context operations (like exact matching or counting) cannot rely on Theorem 1 for theoretical assurance.

What evidence exists in the paper. The continuity assumption is stated explicitly in Theorem 1: "Let Λ*: P(Ω) × Ω → ℝ^{d'} be continuous, where P(Ω) is endowed with the weak* topology." The paper does not discuss the exclusion of discontinuous targets, nor does it provide examples of in-context computations that are continuous vs. discontinuous. The proof's reliance on Stone-Weierstrass makes continuity non-negotiable.

Mitigation status. None. The paper neither acknowledges this as a limitation nor discusses approaches to handling discontinuous functions (e.g., by smoothing approximations, by changing the input topology, or by proving approximation in weaker senses). Given that the in-context learning literature has focused extensively on discontinuous operations (linear regression, gradient descent, associative memory retrieval), this is a significant gap between the theory and the phenomena it purports to explain. The paper's contribution is best understood as universality for smooth in-context mappings, with the extension to realistic discontinuous computations left as an open problem.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper delivers a foundational mathematical guarantee where the field previously had only empirical evidence and partial results: standard transformer architectures, with fixed embedding dimension and head count, are provably capable of representing any continuous in-context computation on contexts of arbitrary size. This is not an incremental improvement to an existing theorem — it establishes the first universality result for transformers that does not require dimensions to grow with sequence length. In doing so, it shifts the theoretical landscape along several axes.

The most significant conceptual shift is the measure-theoretic reframing of transformers as operators on probability distributions. Before this work, transformers were understood as matrix-to-matrix functions — sequences in, sequences out. Yun et al. (2019) formalized this as universal approximation of sequence-to-sequence maps, but their proof trapped the analysis in a finite-dimensional paradigm where the embedding dimension necessarily grew with n. By lifting the input domain to P(Ω) × Ω — the space of probability measures — this paper dissolves the n-dependence entirely. A 10-token context and a 10⁶-token context live in the same topological space, and the same transformer processes both. This isn't just a "trick" that makes the proof work; it reframes what a transformer is — a coupled particle system where layers evolve token distributions, not matrices. The composition rule (Γ₂ ⋄ Γ₁)(μ, x) = Γ₂(μ₁, Γ₁(μ, x)) with μ₁ = Γ₁(μ)_♯μ makes explicit that a deep transformer simultaneously transforms the query token and pushes forward the entire context measure. This structural decomposition, previously obscured in the matrix notation, opens new analytical possibilities: studying transformers as dynamical systems (as in Geshkovski et al., 2023, 2024), connecting them to neural operators on metric spaces (Kratsios et al., 2023), and analyzing their mean-field limits when token counts go to infinity.

This work provides a unified reconciliation of conflicting prior findings on transformer expressivity. The literature was fragmented: Yun et al. (2019) proved universality but at the cost of n-dependent width; Alberti et al. (2023) proved universality for Sumformers but required dimension growth; Nath et al. (2024) highlighted the difficulty of approximating smooth functions with dot-product attention. The measure-theoretic approach reveals why these conflicts arose — each prior work implicitly assumed a different topology on the input space, leading to different compactness properties and different approximation regimes. This paper's framework makes the topology explicit (weak* convergence of measures, metrized by Wasserstein distance) and shows that under this natural topology, fixed-dimension transformers are universal for the class of continuous in-context mappings. The conflicts were not about transformers per se, but about the mathematical language used to describe their inputs. This is a classic pattern in mathematical analysis: the right definitions dissolve apparent paradoxes.

The paper introduces a new kind of "tight" universality theorem via the identifiability result. Most approximation theory is one-sided — it proves that a function class can approximate a target class, without characterizing what cannot be approximated. Lemma 13, proving that the uniform limit of identifiable maps is identifiable, combined with Lemma 11 (masked attention is identifiable), establishes that causal transformers cannot uniformly approximate non-identifiable in-context mappings, regardless of depth or width. This is a genuine necessity result, rare in neural network expressivity theory. It means Theorem 2 is not just a sufficiency statement but a characterization: causal transformers can approximate exactly the continuous, causal, identifiable maps on Lipschitz contexts. This sharpens our understanding of what causal masking costs architecturally — it's not just about computational efficiency (no attending to future tokens); it structurally restricts the function class. Any task requiring genuine "peeking" at future context to process the present is provably outside the reach of causal transformers, no matter how deep.

The algebraic proof strategy (Stone-Weierstrass on attention-derived cylindrical functions) introduces a new proof template for neural network universality. Previous transformer universality proofs (Yun et al., 2019) were constructive — explicitly building networks that implement step-function approximations, à la Cybenko (1989). This paper's approach — identifying a point-separating algebra of "elementary" functions realizable by minimal architectural fragments, invoking Stone-Weierstrass for density, then encoding algebraic operations (products, sums) into the architecture's composition structure — decouples the approximation argument from the realization argument. This template is portable: it could be applied to prove universality of other permutation-equivariant or set-based architectures (graph transformers, Set Transformers, neural operators on metric spaces) by defining appropriate elementary functions, verifying point separation (typically the hardest step), and designing a carry-and-accumulate encoding for the resulting cylindrical functions. The paper thus contributes a methodological innovation alongside its specific theorems.

The work redirects research attention toward several questions that were previously unprompted. The most important: what is the quantitative relationship between depth, precision, and target function smoothness for transformers? By establishing universality without rates, the paper creates a clear open problem — obtaining quantitative bounds — that was not even well-posed before (you can't ask "how many layers do I need?" if you don't know that some finite number suffices). The identifiability result raises architectural questions: are there tasks where the gap between masked and unmasked attention is intrinsic (non-identifiable targets), as opposed to a matter of having enough capacity? The carry-and-accumulate construction's d + 3d' embedding dimension bound immediately prompts: is this tight, or can it be lowered to d + d' or d + 2d' with a more efficient construction? These questions are now well-defined in the measure-theoretic framework, whereas before this paper they lacked a common mathematical language.

Less attractively, the paper makes some research directions look less promising. The finding that the exponential in softmax is structurally necessary for the point-separation proof (it connects to moment-generating functions via the generalized Laplace transform) suggests that linear attention without an exponential kernel may face fundamental expressivity limitations that go beyond empirical performance. A linear-attention variant φ(q)ᵀφ(k) would not support the c-parameter variation that generates moments in Lemma 1. This doesn't prove linear attention isn't universal — there could be a completely different proof — but it means the algebraic route is blocked, and any universality proof for linear attention must find an alternative separating algebra, which may not exist (kernel-based attention loses the analytic structure of the exponential). Similarly, the restriction to continuous targets (via Stone-Weierstrass) suggests that purely discrete/combinatorial universality results (transformers as Turing machines, formal language recognition) require fundamentally different mathematical tools and cannot be unified with the continuous approximation framework. The paper thus draws a principled boundary between two modes of transformer analysis — continuous approximation and discrete computation — that may need separate theories.

Follow-Up Research This Work Enables

Quantitative approximation rates: what is the depth–precision tradeoff for transformer universality? The paper proves that some finite depth L suffices for any target ε, but provides no relationship between L and ε. This is the obvious first open problem. A follow-up would impose additional smoothness on the target in-context mapping — for instance, Lipschitz continuity of Λ* with respect to the Wasserstein distance on P(Ω) — and attempt to derive explicit bounds on the number of product terms T and summands N in the cylindrical function approximation (Equation 17) in terms of ε and the Lipschitz constant. The bottleneck is two-fold: (a) replacing the existential Stone-Weierstrass with a quantitative variant (Jackson-type theorems on P(Ω) × Ω under the Wasserstein metric, which to our knowledge do not exist), and (b) bounding the complexity of the multiplication-approximating MLP Φ (Lemma 8) in terms of the radius R of intermediate token values, which requires controlling how token magnitudes grow through the carry-and-accumulate construction. A strong result would show that L = O(poly(d') / ε^α) for some α depending on the smoothness of Λ*. Even a weak result — e.g., L = O(exp(1/ε)) — would establish that the depth does not grow arbitrarily faster than standard MLP universality rates. A negative result (proving that L must grow super-exponentially in 1/ε for some target) would indicate that the algebraic construction is pathologically inefficient and a different proof paradigm is needed for practical bounds.

Tightness of the d + 3d' embedding dimension bound. Theorem 1 proves sufficiency of embedding dimension d + 3d' for universality. Is this bound tight, or is it an artifact of the carry-and-accumulate construction? A lower-bound result would be highly informative. One approach: construct a specific in-context mapping Λ* and prove that any transformer approximating it requires at least d + 2d' embedding dimension (or some other function of d, d'). This could leverage communication-complexity arguments or topological invariants of the function class. The d + 3d' comes from three auxiliary registers (affine projection, product accumulator, sum accumulator) plus the original token. Could a time-multiplexed construction reduce this? Specifically: instead of carrying all three simultaneously, could the product and sum accumulators share a register by using additional layers to swap them in and out? The depth-for-width tradeoff implicit in the construction (using more layers might allow narrower embeddings) is completely unexplored. A follow-up could prove that d + d' is sufficient (by an alternative multiplexing construction) or that d + 2d' is necessary (by a lower bound). Such a result would directly guide architecture designers on the minimal practical embedding dimension for universal capability.

Extending universality to linear and kernelized attention variants. The proof crucially relies on the exponential kernel in softmax attention to achieve point separation (Lemma 1: moment-generating functions). This immediately raises the question: are transformers with alternative attention mechanisms also universal, and under what conditions? A concrete investigation would target linear attention where exp(⟨Qx, Ky⟩) is replaced by φ(Qx)ᵀφ(Ky) for some feature map φ. The first step would be to attempt to construct a separating algebra analogous to A but using kernelized elementary mappings. The point-separation step would require proving that some functional of μ analogous to L(μ)(a, c) separates measures when c-variation is replaced by varying the feature map φ. If φ is a universal kernel (e.g., Gaussian RBF feature map), the connection to the characteristic property of kernel mean embeddings might provide an alternative route. If linear attention with simple φ(x) = ReLU(Wx) is shown not to support point separation (by constructing a counterexample of two distinct measures that give identical attention outputs for all parameters), this would be a significant negative result proving that linear attention has strictly weaker expressivity than softmax attention — not just empirically, but fundamentally. Conversely, a positive universality result for linear attention would show that the exponential is sufficient but not necessary, broadening the class of provably universal architectures.

From in-context mappings to in-context learning: does the universality result explain empirical in-context learning phenomena? The paper proves that transformers can represent any continuous in-context mapping. It says nothing about whether gradient descent finds such representations when trained on in-context learning tasks. A natural follow-up bridges the gap: take a specific in-context learning problem (e.g., linear regression, as studied by Ahn et al. (2024), Mahankali et al. (2023), Zhang et al. (2024)) and ask whether the construction in Theorem 1 can be specialized to yield an explicit transformer parameterization that exactly implements the Bayes-optimal predictor. The elementary mapping γ_λ (Equation 14) with a as the linear regression coefficient, b as the intercept, and specific c, v might directly encode one-step gradient descent on the in-context loss. If so, this would connect the abstract algebraic proof to the mechanistic interpretability literature, showing that the "cylindrical functions" the proof constructs are not just existence artifacts but correspond to algorithms that learned transformers actually discover. A strong result would be an explicit assignment of the (θ_ℓ, ξ_ℓ) parameters in the carry-and-accumulate construction that, when unrolled, yields an interpretable algorithm (e.g., ridge regression with a specific regularization parameter encoded by c). A negative result — proving that the construction requires astronomically large depth for even simple in-context learning tasks — would indicate that the proof's existential depth is inherently large, and that practical transformers achieve in-context learning through different, possibly shallower mechanisms.

Necessity of the identifiability condition: constructing a function that causal transformers provably cannot approximate. Lemma 13 proves that non-identifiable maps cannot be uniform limits of causal transformers, establishing identifiability as necessary. But does a concrete, natural non-identifiable in-context mapping exist that is continuous (so within the unmasked transformer's reach) but provably unapproximable by causal transformers? Constructing an explicit example would make the necessity result tangible. A candidate: define Λ*(μ, x, t) that, at time t, computes some global statistic of the entire context μ (including future tokens) and uses it to transform x. For instance, Λ* could output x + E_{y~μ}[y] — the token x shifted by the mean of the whole sequence — but evaluated at time t < e(μ̄) using the full mean including future tokens. This is continuous (the mean depends continuously on μ under weak* topology) and causal (since it only uses μ_t to evaluate x? No — the mean uses all of μ, so the map is causal in the sense Λ*(μ, x, t) = Λ*(μ_t, x, t)? Let's check: at time t, does the output depend only on μ_t? No, because the full mean ∫ y dμ(y) uses tokens with s > t. So Λ* is not causal — it violates the definition. The challenge is constructing a map that is causal (output at t depends only on μ_t) but not identifiable (different full contexts with the same prefix μ_t = μ'_t yield different functions at time t). Identifiability says: if μ_t = μ'_t, then the induced functions are equal. A non-identifiable causal map would need to encode information about the future into the function's behavior at time t, despite the output only depending on μ_t. This seems paradoxical because if the output depends only on μ_t, and μ_t = μ'_t, how can the functions differ? The resolution: the function's dependence on t (the time index itself) could encode future information. For instance, suppose μ_t contains no information about t (all prefixes look identical up to a time-rescaling), but the true time t carries information about how much of the full sequence remains. The function Λ(μ, x, t) could behave differently at the same mask μ_t if t differs — this would be causal (depends on μ_t and t) but not identifiable (since μ_t = μ_{t'} does not imply equal outputs because t ≠ t'). A concrete example on Ω = [0,1] with uniformly spaced tokens would test whether such a map exists. If it does, it would be a function that unmasked transformers can approximate (it's continuous) but causal transformers cannot, providing a sharp separation.

Training dynamics and implicit bias: can gradient descent find the universal approximators? This is a longer-term direction, but the paper provides the necessary foundation: now that we know some transformer configuration approximates a given in-context mapping, we can ask whether standard training procedures (SGD on next-token prediction with appropriate data distributions) actually converge to such configurations. A concrete experiment: generate data from a known continuous in-context mapping Λ* (e.g., a linear regression oracle where the coefficients depend smoothly on the context distribution), train a transformer with varied depth and width on finite samples, and measure both the learned function's deviation from Λ* and how this deviation scales with model size. The paper's dimension bound d + 3d' provides a theoretical floor: models with embedding dimension below this bound might still succeed if the bound is not tight, but measuring the gap between theoretical sufficiency and empirical success would quantify the efficiency of gradient-based learning. A theoretical complement: analyze the loss landscape of the parameterization constructed in Lemma 9 and study whether local optimization from random initialization can reach it, or whether the construction corresponds to a narrow basin of attraction that gradient descent would miss.

Practical Applications and Downstream Use Cases

Architecture designers now have a theoretically-grounded minimum embedding dimension for universal capability. For a task with input token dimension d (e.g., d = 64 for small-scale sequence modeling) and output token dimension d' (e.g., d' = 64 for same-dimensionality autoregressive prediction), Theorem 1 guarantees that embedding dimension d + 3d' = 256 suffices for universal approximation at some depth. This provides a principled floor: if a practitioner is choosing between d_model = 128 and d_model = 256, the theory says 128 may be provably insufficient (if d + 3d' > 128), while 256 is in the provably-sufficient regime. The H ≤ d' head-count bound similarly suggests that d' heads suffice — a 64-head model for d' = 64-dimensional outputs hits the theoretical bound. These are not tight practical recommendations (the bounds are upper bounds from a specific construction, not minimal requirements), but they give architecture search a theoretically-motivated starting point, analogous to how the minimal width d+1 for ReLU networks (Hanin and Sellke, 2017) informs MLP architecture choices even though practical MLPs use far wider layers.

Verifier and reward model design for LLM reasoning pipelines. If a practitioner is training a process reward model (PRM) or verifier for LLM outputs — analogous to the verifier components in the earlier paper analysis — the universality result provides assurance that a transformer-based verifier with appropriate dimensions can in principle represent any continuous scoring function over token contexts. Specifically, if the verifier's input consists of a partial solution x and a context of previous reasoning steps μ, Theorem 1 guarantees that a transformer can approximate any continuous verifier function Λ*(μ, x) mapping the context distribution and current step to a score. The dimension bound d_verifier_in ≤ d + 3 for scalar-valued verifiers (d' = 1) suggests that even modest embedding dimensions are sufficient for representing verifier logic, shifting the bottleneck to training data quality and optimization rather than architectural capacity. This is directly relevant to the RLHF and inference-time search pipelines where verifier quality is the primary limitation.

Neural operator and scientific computing applications. The measure-theoretic formulation connects transformers to neural operators — architectures that learn mappings between function spaces for PDE solving and scientific simulation (Kovachki et al., 2023). Theorem 1 implies that a transformer can approximate any continuous operator mapping a probability distribution of collocation points to a solution field, with fixed embedding dimension. For a PDE solver using d = 3 spatial coordinates and d' = 1 scalar solution output, the bound d_in ≤ 6 is tiny — far below practical transformer dimensions. This suggests that transformer-based neural operators are architecturally "over-provisioned" for universality, and that the practical design considerations (depth, attention mechanisms for long-range spatial interactions, training stability) dominate the architectural expressivity question. The universality guarantee provides a theoretical safety net: the architecture is not a representational bottleneck, and any failure to approximate a target operator is due to optimization or data, not the architectural choice.

Self-improvement and synthetic data generation pipelines. When using transformers to generate training data for themselves (rejection sampling, STaR, ReST), the generated outputs serve as new context-target pairs. Theorem 1 guarantees that the transformer can in principle represent the generator function mapping a context distribution to high-quality outputs, provided that function is continuous. This means that as the pipeline iterates — generating data, training, generating better data — the architecture is not a representational ceiling. The limitation lies in the optimization process and the quality of the reward signal, not in whether the transformer can express the desired mapping. This is an important negative assurance for self-improvement research: if a self-improvement loop stalls, the architecture is not to blame (at the level of representational capacity), and researchers should look to reward design, exploration strategies, or optimization dynamics instead.

When to Prefer This Method

The paper does not propose a practical method for training or deploying transformers; it provides a theoretical guarantee about the architecture itself. There is no "method A vs. method B" tradeoff. The relevant decision framework is for researchers choosing a theoretical framework for analyzing transformer expressivity, not for practitioners choosing an architecture.

For researchers analyzing transformer expressivity: prefer the measure-theoretic formulation (P(Ω) × Ω as input domain, weak topology, attention as Γ_θ(μ, x))* over the finite-dimensional sequence-to-sequence formulation when:

The goal is to make claims about transformers processing contexts of arbitrary length, because the measure-theoretic domain handles all n in a single topological space, avoiding n-dependent dimension growth.
The target function class involves smooth dependence on the token distribution, because the Wasserstein/weak* topology gives natural continuity conditions.
The analysis involves compositional depth, because the pushforward composition rule (Γ₂ ⋄ Γ₁)(μ, x) = Γ₂(Γ₁(μ)_♯μ, Γ₁(μ, x)) cleanly separates the per-token and per-context transformations.
Causal masking is under investigation, because the identifiability criterion provides a precise characterization of the expressivity gap between masked and unmasked architectures.

Prefer the finite-dimensional formulation (Yun et al., 2019) or discrete formal language approaches when:

The target functions are discontinuous in the token distribution (e.g., exact matching, counting, sorting), since the weak* topology enforces continuity and the Stone-Weierstrass approach fails for discontinuous targets.
The analysis requires quantitative depth bounds, since the algebraic proof is existential while constructive proofs (Yun et al.) yield explicit L in terms of ε, d, and n (even if those bounds are large).
The focus is on finite, fixed-length sequences where n is known a priori and the dimension dependence on n is not a limiting factor for the theoretical question at hand.