acceptodds
Under review as a conference paper at ICLR 2027

Approximation Theory for Transformers

Abstract

We establish the first comprehensive approximation theory for positional transformers that parallels classical neural network approximation theory. (i) We prove universal approximation uniformly on compact sets; in \(L_\mu^p\); uniformly on compact sets together with derivatives up to order \(k\); in weighted Sobolev norms. (ii) We establish , Sobolev, , and Barron approximation rates. (iii) The rate is optimal under continuous parameter selection. All these results follow from an exact realization theorem: we show that a positional transformer acting on tokens realizes suitable families of neural networks. This allows us to transfer classical neural network approximation theory, preserving approximation-rate exponents.

Primary area:
learning theory
Keywords:
Approximation theory, transformers

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Nd4vOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper shows the approximation theory for Transformers. This paper list lots of theorem, but it seems many of the theories are much related to the previous work. It is hard to distinguish which of these theories are the contribution of this paper.

Critical strengths

There are lots of mathematical results in this paper.

Critical weaknesses

Presentation. In the paper writing, this paper just put lots of the results together, but do not claim their relationship, how to extend one result to anther, and the differences with the previous work. Therefore, I can hardly find the real contribution of this paper and what is important this paper want to tell us. Although this paper contains lots of mathematical results, I can hardly find some interesting thoughts for human researchers.

Limited discussions. Besides, Transformers have been extended to many variants for several years---like causal attention, linear attention and sparse attention, which may replace the softmax attention. These variants are not discussed, so the title of this paper seems not suitable.

Questions for authors
  1. What is the contribution of this paper?
  2. What is different from the previous work on the approximation theory for Transformers? How important is this paper?
  3. Can the analyses extend to other attentions? such as causal attention, linear attention and sparse attention.
3 comments

We are grateful to the Referee for carefully reading the manuscript and for the comments. These helped us, in particular, to clarify how the exact realization theorem connects the paper's results and prompted us to extend the theory to masked attention. We have addressed these comments in the revised version, with the main changes highlighted in red. As a result, our paper now contains a clearer presentation and stronger results, and we are grateful to the Referee for this.

Below, we address all the points raised and we specify the corresponding changes in the paper.

Critical Weaknesses: Presentation. In the paper writing, this paper just put lots of the results together, but do not claim their relationship, how to extend one result to anther, and the differences with the previous work. Therefore, I can hardly find the real contribution of this paper and what is important this paper want to tell us. Although this paper contains lots of mathematical results, I can hardly find some interesting thoughts for human researchers.

Our main contribution is to show that sequence-to-sequence transformers can inherit classical neural network approximation theory (including universality and rates, i.e., all the results that the Referee noted under Critical Strengths).

To this end, the key new technical tool is the exact realization theorem (Theorem 3.3, i.e., transformers exactly realize suitable neural networks), from which the approximation results can be inherited. In particular, given a target ff, we first adapt classical neural network approximation results (in Appendices B.2, B.3, and B.5) to construct an approximating family in a form compatible with Theorem 3.3. We then realize this family with a transformer via Theorem 3.3.

In our original submission, we had outlined this relationship between exact realization and the approximation results in the introduction, Section 3, and Appendices B.2--B.3. To address the Referee's point, we have made the two steps of the transfer argument more explicit in the revised introduction, Section 3, and Appendices B.2--B.3, B.5.

We have explained these points in detail in our answers to Questions 1 and 2 below, including a comparison with the literature.

Limited discussions. Besides, Transformers have been extended to many variants for several years---like causal attention, linear attention and sparse attention, which may replace the softmax attention. These variants are not discussed, so the title of this paper seems not suitable.

We extended the results to softmax attention with a fixed mask, including causal and fixed sparse attention, as suggested by the Referee. Furthermore, in Remark B.9, we identify linear attention as a possible extension of our framework and leave it for future work.

Our answer to Question~3 explains these points in detail.

Questions For Authors: 1 What is the contribution of this paper?

Our main contribution is to show that sequence-to-sequence transformers can inherit classical neural network approximation theory (including universality and rates).

To this end, the key new technical tool is the exact realization theorem (Theorem 3.3); this shows that sequence-to-sequence transformers exactly realize prescribed families of shallow networks with shared weights and affine positional biases. The main technical idea of the proof is to use attention to gather information and feed it to the feedforward layers (see the explanation at the beginning of the proof of Th. 3.3).

This exact realization lets us transfer classical neural network approximation theory to transformers, using the following very natural strategy: given a target ff, we first adapt (via technical arguments in Appendices B.2, B.3, and B.5) classical network approximation results to construct an approximating family of this form. We then realize this family exactly with a transformer. We show that this procedure preserves universality and rates.

As a consequence, we provide the first comprehensive approximation theory for a general class of transformers, with results that parallel those in classical neural network approximation theory: we prove transformer analogues of Hornik's four universal approximation theorems, derive LpL^p, Sobolev, CkC^k, and Barron rates, and show that the LpL^p rate is optimal under continuous parameter selection. These are among the many material results that the Referee noted under Critical Strengths.

As mentioned in the previous comment, to address the Referee's point, we have made the two steps of the transfer argument more explicit in the revised introduction, Section 3, and Appendices B.2--B.3, B.5.

2 What is different from the previous work on the approximation theory for Transformers? How important is this paper?

Previous approximation theory for transformers was incomplete: previous results typically gave guarantees for particular architectures, target classes, or error criteria, while several basic questions remained open, including (but not only) universality and rates for derivative approximation.

Our exact realization theorem lets us transfer classical neural network approximation theory to positional transformers. In particular, we extend compact-uniform universality to general continuous nonpolynomial activations and LμpL^p_\mu universality to arbitrary finite Borel input measures and bounded Borel measurable activations (Theorems 4.1--4.2). To the best of our knowledge, Theorems 4.3 and 4.4 provide the first universal approximation theorems for transformers that simultaneously approximate functions and their derivatives in the compact-open CkC^k topology and in weighted Sobolev norms.

Our results in Section 5 provide the first Sobolev, CkC^k, and Barron derivative-approximation rates for transformers by transferring classical NN rates. For general smooth nonpolynomial activations, Theorem 5.3 with k=0k=0 gives the LpL^p rate P−s/(dnJ)P^{-s/(d n_{\mathbf J})} for targets whose reduced components have Ws,pW^{s,p} regularity, where nJn_{\mathbf J} is the largest number of active input tokens at any output position. Theorem 6.1 proves optimality of this exponent for continuous parameter selection.

We have clarified these points by providing a revised comparison in the introduction and by adding a comparison with selected literature in Appendix E.

How important is this paper?

Besides the breadth and usefulness of our results, the significance of our paper, in our view, is that it provides a very natural approach for transformer approximation theory. Proving universality and rates (including derivative approximation) for transformers can be technical and difficult. Indeed, many fundamental universality results and rates had remained unproven, as shown in our literature review. Our paper shifts this approach to transferring the corresponding classical neural-network theory as a whole. One can focus on proving exact realization for suitable families of NNs, which our paper identifies. We have clarified this in the introduction.

  1. Can the analyses extend to other attentions? such as causal attention, linear attention and sparse attention?

We have extended our results in the revised manuscript to attention with a mask (see Appendix A.1 for masks and Definition 2.1(ii) for the corresponding transformer architecture). This includes, in particular, causal, sparse (as suggested by the Referee), local, and full attention, illustrating the flexibility of the framework. The approximation results apply to targets compatible with the chosen mask (Definition A.3 and Remark A.4 on mask compatibility). Extending the rates to masked attention required a new transfer argument (Steps 1--4 of Appendix B.3), because the original translation argument uses the full input at every output position. We retain the simpler translation argument in Appendix B.5 for the full-attention rate extensions to deep networks and equivariant targets in Appendices C and D, respectively.

Furthermore, in Remark B.9, we identify linear attention as a possible extension of our framework and leave it for future work.

Reviewer_QBKtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proves an exact realization theorem (Thm. 3.2): a positional transformer with unmasked softmax attention, residual connections and no layer normalization exactly computes shared-weight families of shallow networks Φi(ξ)=Cσ(Aξ+D i+b)+c\Phi_i(\xi) = C\sigma(A\xi + D\,i + b) + c (with A,D,b,C,cA, D, b, C, c shared across positions), applied to the flattened sequence vec(X)\mathrm{vec}(X), for any activation σ\sigma whenever L∗q∗≥mL^* q^* \ge m, where mm is the number of hidden units.

  1. Construction: constant queries and positional keys across heads give a fixed, invertible softmax mixing matrix SS; the output projection contains the factor S−1⊗IdS^{-1}\otimes I_d, which undoes the mixing, so the ordered input is recovered; the feed-forward sublayers then evaluate the hidden units group by group, and their outputs are accumulated through the residual stream. When the working width sw<nds_w < nd, the working block instead stores only the input-dependent terms A(u)vec(X)A^{(u)}\mathrm{vec}(X) of the current group's pre-activations, block by block, and the attention output projections then depend on the target (Remark 3.5).
  2. Universal approximation: Hornik's four theorems transfer, including derivative approximation in the compact-open CkC^k topology, weighted derivative seminorms on classically differentiable functions (App. A), and LμpL^p_\mu for arbitrary finite measures μ\mu.
  3. Rates: LpL^p, Sobolev, CkC^k and Barron rates, plus derivative rates.
  4. Optimality: for smooth nonpolynomial σ\sigma, the LpL^p rate P−s/(nd)P^{-s/(nd)} on the Ws,pW^{s,p} unit ball is optimal under continuous parameter selection (Thm. 6.1).
Critical strengths
  1. Exact realization under softmax attention: there is no error from replacing hard attention with softmax, and derivatives are preserved exactly (Cor. B.5). This is what makes the CkC^k, Sobolev and derivative-rate results possible.
  2. The multi-head invertible-mixing construction recovers the ordered input (when sw≥nds_w \ge nd) using value maps shared across heads and tokens, with positional vectors added in coordinates disjoint from the embedded content, so that tokens carry (xi;ρi;0;0)(x_i;\rho_i;0;0); no position-dependent value map is needed.
  3. Careful resource accounting: dense versus nonzero parameter counts, and explicit head/width/depth trade-offs (Def. 3.1, Remarks 3.3 and 3.7).
  4. Universal approximation in derivative topologies and for arbitrary finite measures, and derivative approximation rates, appear new relative to the compared literature.
  5. The proofs are well organized and readable.
Critical weaknesses
  1. The paper would benefit from a sharper comparison with Yu et al. (ICLR 2026), Alberti et al. (2023, Sumformer) and Siegel et al. (2026), which it cites only in footnotes. In my reading, these works also use attention to collect sequence information and then build on feed-forward approximation, although their architectures and target classes differ. Back de Luca et al. (ICML 2025, "Positional Attention: Expressivity and Learnability of Algorithmic Computation"), which studies attention that depends only on positions, is closely related and not cited. The additional guarantees concerning exact realization, activation assumptions and resource requirements should be isolated more clearly.
  2. The transfer of existing approximation results to this transformer class is useful, particularly for derivative approximation. However, I regard the main conceptual contribution as the realization-and-transfer construction. In my assessment, its incremental significance is not sufficient for acceptance, despite the technically clean construction and the breadth of its consequences.
  3. The rates show no benefit from attention; Remark 3.5 itself notes that gains from input-dependent attention lie beyond the construction. The LpL^p, Sobolev and CkC^k (Hölder-target) rates retain the ambient-dimension dependence ndnd, and their constants depend on nn and dd in ways the paper does not track. The Barron results in Theorems 5.6–5.7 inherit the classical dimension-independent exponent −1/2-1/2 under stronger function-class assumptions, and Theorem 5.8 gives a sharper exponent −12−τ(2+τ)(nd+1)-\tfrac12 - \tfrac{\tau}{(2+\tau)(nd+1)}, a dimension-dependent improvement that requires additional regularity. The ndnd dependence is expected for arbitrary ordered sequence functions and is not a defect in itself. Still, the results neither show an approximation advantage from attention nor exploit sequence structure such as permutation equivariance, locality or sparsity, which limits what they explain about transformers.
Questions for authors
  1. Could you provide a direct comparison of Theorem 3.2 with Yu et al., Back de Luca et al. and the Sumformer-based constructions, specifying the differences in architecture, activation assumptions, exactness and parameter counts?
2 comments

We thank the Referee for the careful reading and the comments provided. These prompted us, in particular, to sharpen the comparison with related work and to strengthen our results by further exploiting sequence structure. We have addressed these comments in the revised version, with the main changes highlighted in red. As a result, our paper now contains both a stronger presentation and stronger results, and we are grateful to the Referee for this.

Below, we address all the points raised and we specify the corresponding changes in the paper.

Critical Weaknesses:

  1. The paper would benefit from a sharper comparison with Yu et al. (ICLR 2026), Alberti et al. (2023, Sumformer) and Siegel et al. (2026), which it cites only in footnotes. In my reading, these works also use attention to collect sequence information and then build on feed-forward approximation, although their architectures and target classes differ. Back de Luca et al. (ICML 2025, "Positional Attention: Expressivity and Learnability of Algorithmic Computation"), which studies attention that depends only on positions, is closely related and not cited. The additional guarantees concerning exact realization, activation assumptions and resource requirements should be isolated more clearly.

As suggested by the Referee, we have provided a comparison against the mentioned references: a detailed one in Appendix E.2 and a short one (for space constraints) in the introduction (moved to the main body). These comparisons further highlight the strength of our approach.

  1. The transfer of existing approximation results to this transformer class is useful, particularly for derivative approximation. However, I regard the main conceptual contribution as the realization-and-transfer construction. In my assessment, its incremental significance is not sufficient for acceptance, despite the technically clean construction and the breadth of its consequences.

Besides the breadth and usefulness of our results (as emphasized by the Referee), the significance of our paper is that it provides a very natural approach for transformer approximation theory: proving universality and rates (including derivative approximation) for transformers can be difficult; and, indeed, many fundamental universality results and rates had remained unproven, as shown in our literature review. Our paper fills this gaps by shifting the approach to transferring the corresponding classical neural-network theory as a whole: one can focus on proving exact realization for suitable families of NNs, which our paper identifies. We have clarified this in the introduction.

  1. The rates show no benefit from attention; Remark 3.5 (Remark B.6 in the revision) itself notes that gains from input-dependent attention lie beyond the construction.

Our construction uses input-independent attention weights. This is a strength in our approach: this construction already attains the optimal LpL^p approximation exponent of Theorem 6.1 among all methods under continuous parameter selection, including transformers with input-dependent attention. We have clarified this point Remark B.6 of the revised manuscript.

Furthermore, we conjecture that the Wk,pW^{k,p} rate for Ws,pW^{s,p} targets (Theorem 5.3) and the CkC^k rate for Cr,αC^{r,\alpha} targets (Theorem 5.4) are also optimal under continuous parameter selection. We have added this conjecture after Theorem 6.1 in the revised manuscript. Proving it requires substantial additional work on continuous parameter selection and matching lower bounds. These are future challenges opened by our paper.

The LpL^p, Sobolev and CkC^k (Hölder-target) rates retain the ambient-dimension dependence ndnd, and their constants depend on nn and dd in ways the paper does not track. The Barron results in Theorems 5.6-5.7 inherit the classical dimension-independent exponent −1/2-1/2 under stronger function-class assumptions, and Theorem 5.8 gives a sharper exponent −12−τ(2+τ)(nd+1)-\frac12-\frac{\tau}{(2+\tau)(nd+1)}, a dimension-dependent improvement that requires additional regularity. The ndnd dependence is expected for arbitrary ordered sequence functions and is not a defect in itself. Still, the results neither show an approximation advantage from attention nor exploit sequence structure such as permutation equivariance, locality or sparsity, which limits what they explain about transformers.

Following the Referee's suggestion, we have revised the paper to cover additional sequence structure:

We have improved our approximation rates by considering targets with prescribed active token dependence. Each output at position ii depends only on a prescribed subset JiJ_i of the tokens visible under an attention mask (Definition A.3 and Remark A.4). This framework covers local, sparse, and causal targets. We have adapted our exact realization and transfer results to cover these structured targets by recovering the tokens in JiJ_i (see Lemma B.5(ii)). This shows that our approach can exploit sequence structure, improving rates: in the LpL^p, L∞L^\infty, Sobolev, and CkC^k rate exponents (Theorems 5.1--5.4), d nJd\,n_{\mathbf J} now replaces ndnd, where nJ=max⁡i∣Ji∣n_{\mathbf J}=\max_i|J_i|. Note that Theorems 5.1--5.3 measure the target's Sobolev regularity using the reduced J\mathbf J-norms (defined in Appendix A.2 for the active token dependence of Definition A.3). These norms measure each output component's regularity on its active inputs. This lets us apply classical approximation estimates in dimensions at most d nJd\,n_{\mathbf J} while still controlling the error in the original ambient space (of dimension dndn). Extending the rates to masked attention and prescribed token dependence required a new transfer argument (Steps 1--4 of Appendix B.3), because the original translation argument uses the full input at every output position. We retain the simpler translation argument in Appendix B.5 for the full-attention rate extensions to deep networks and equivariant targets in Appendices C and D, respectively.

Our main theorems cover permutation-equivariant targets under the stated assumptions. However, the approximants need not themselves be equivariant. We have added Appendix D to show how to construct exactly equivariant approximants by averaging over permutations.

Questions For Authors: Could you provide a direct comparison of Theorem 3.2 (Theorem 3.3 in the revision) with Yu et al., Back de Luca et al. and the Sumformer-based constructions, specifying the differences in architecture, activation assumptions, exactness and parameter counts?

Following the suggestion by the Referee, we have provided a short comparison in the main body of the introduction and a detailed comparison in Appendix E.2.

Reviewer_8s7TOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper develops an approximation theory for positional encoder transformers acting on nn tokens in Rd\mathbb{R}^d. The key tool is an exact realization result (Theorem 3.2): a positional transformer with enough depth, width, and heads can exactly reproduce any family of shallow networks with shared weights and position-dependent biases. Using this transfer mechanism, the paper shows that many classical results for shallow networks carry over to transformers: (i) transformer versions of Hornik's universal approximation theorems in several norms (uniform, LpL^p, CkC^k, and Sobolev); (ii) approximation rates in these norms, as well as a rate for spectral Barron functions, inherited from shallow-network theory; and (iii) a matching lower bound showing the rate is optimal when the parameters must depend continuously on the target function. An appendix extends the realization result to deep feed-forward sublayers.

Critical strengths
  • The results are clearly stated with precise assumptions, and the discussion of related work (Section 1.2) is detailed and honest: the paper carefully explains how each theorem compares to existing transformer results and which gaps it fills.

  • The overall approach is clean and systematic: once the realization result (Theorem 3.2) is established, all the universality and rate results follow in a uniform way, with the same rates as the original shallow-network bounds, and the accounting of the architecture sizes (Definition 3.1, Remark 3.7) is spelled out clearly.

Critical weaknesses
  • As a theory paper, the contribution feels incremental. The main results combine two known ingredients: a transfer principle that converts shallow networks into transformers, and classical approximation theory for shallow networks (e.g., Hornik, 1991). The proofs in Sections 4–6 mostly consist of taking the classical results and passing them through Theorem 3.2. The optimality result (Theorem 6.1) also follows from a classical lower bound that holds for any architecture, so it contains no new transformer-specific insight.

  • It is unclear how new the exact realization theorem itself is. Exact MLP-to-transformer conversions already exist in the literature cited by the paper (e.g., Kratsios et al., 2026, Proposition A.1). The paper says Theorem 3.2 differs by handling ordered multi-token inputs with positional encoder blocks, but the comparison in Section 1.2 is brief, and there is no technical discussion of what is genuinely new in the construction — for example, what difficulties the multi-token, shared-feed-forward setting creates and how the construction in Definition B.1 gets around them. Without this, it is hard to tell whether the main lemma is a new result or an adaptation of known constructions.

Questions for authors
  1. Could the authors clearly explain what is technically new in Theorem 3.2 compared to the existing exact realization results, e.g., Petersen & Voigtlaender (2020) and Kratsios et al. (2026, Prop. A.1)?

  2. In particular, which parts of the construction (the invertible softmax mixing, splitting the heads across blocks, the position-dependent biases) are new, and which are adaptations of existing arguments?

  3. What is the main difficulty that the multi-token setting creates, and how does the construction overcome it?

3 comments

We are grateful to the Referee for the careful reading and for the comments provided. These helped us see that the original manuscript did not clearly explain what was technically new; moreover, they prompted us to strengthen our results by further exploiting sequence structure. We have addressed these comments in the revised version, with the main changes highlighted in red. As a result, our manuscript now contains both a stronger presentation and stronger results, and we are grateful to the Referee for this.

Below, we address all the points raised and we specify the corresponding changes in the paper.

Critical Weaknesses: As a theory paper, the contribution feels incremental. The main results combine two known ingredients: a transfer principle that converts shallow networks into transformers, and classical approximation theory for shallow networks (e.g., Hornik, 1991).

To our knowledge, the exact realization in Theorem 3.3 and its main mechanisms in the proof are new for multi-token transformers under standard softmax attention. We give a detailed explanation and comparison in our answers to your Questions 1--3 below (with references to changes in the paper).

The proofs in Sections 4–6 mostly consist of taking the classical results and passing them through Theorem 3.2 (Th. 3.3 in the revision). The optimality result (Theorem 6.1) also follows from a classical lower bound that holds for any architecture, so it contains no new transformer-specific insight.

To address the Referee's point that our paper offered no new insights specific to transformers, in the revised version, we have generalized the theory to masked attention and to structured sequence-to-sequence targets (Definition 2.1(ii) and Definition A.3). This lets us further exploit, e.g., locality, sparsity, or causality. This framework allows us to improve approximation rates, which in most of our revised theorems depend on dnJdn_{\mathbf J} (in place of ndnd in the original version). In particular, the target is f=(f1,…,fn):Ω⊆Rd×n→Rd×nf=(f_1,\ldots,f_n):\Omega\subseteq\mathbb R^{d\times n}\to\mathbb R^{d\times n}, the sets Ji⊆{1,…,n}J_i\subseteq\{1,\ldots,n\} index the input tokens on which fif_i may depend, and nJ=max⁡i∣Ji∣n_{\mathbf J}=\max_i|J_i| is the largest of these set sizes. Note that, in the revised version, Theorems 5.1--5.3 measure the target's Sobolev regularity using the reduced J\mathbf J-norms (defined in Appendix A.2 for the active token dependence of Definition A.3); these norms measure each output component's regularity on its active inputs. This lets us apply classical approximation estimates in dimensions at most d nJd\,n_{\mathbf J} while controlling the error in the original ambient space (of dimension dndn).

Note also that extending the rates to masked attention and prescribed token dependence required a new transfer argument (Steps 1--4 of Appendix B.3), because the original translation argument uses the full input at every output position. We retain the simpler translation argument in Appendix B.5 for the full-attention rate extensions to deep networks and equivariant targets in Appendices C and D, respectively.

It is unclear how new the exact realization theorem itself is. Exact MLP-to-transformer conversions already exist in the literature cited by the paper (e.g., Kratsios et al., 2026, Proposition A.1). The paper says Theorem 3.2 (Th. 3.3 in the revision) differs by handling ordered multi-token inputs with positional encoder blocks, but the comparison in Section 1.2 is brief, and there is no technical discussion of what is genuinely new in the construction — for example, what difficulties the multi-token, shared-feed-forward setting creates and how the construction in Definition B.1 gets around them. Without this, it is hard to tell whether the main lemma is a new result or an adaptation of known constructions.

To our knowledge, the exact realization in Theorem 3.3 and its main mechanisms in the proof are new for multi-token transformers under standard softmax attention. We give a detailed explanation and comparison in our answers to your Questions 1--3 below.

Questions For Authors:

  1. Could the authors clearly explain what is technically new in Theorem 3.2 compared to the existing exact realization results, e.g., Petersen & Voigtlaender (2020) and Kratsios et al. (2026, Prop. A.1)?

Our exact realization Theorem 3.3/transfer principle is new for standard softmax attention and prescribed network families with arbitrary activation, in the multi-token setting. Its proof is the main new technical contribution of the paper, as it relies on many new techniques with respect to the literature on exact realization theorems/\allowbreak transfer principles. We briefly compare here, while, following the suggestion by the Referee, we have revised the comparison in the introduction and provided a more detailed comparison in the paper in Appendix E.1 (in the appendix, for space constraints).

Petersen--Voigtlaender establish a transfer between fully connected and convolutional networks; their result therefore does not apply to transformers (we cite it as a successful precedent for a transfer principle for another ML architecture; we have clarified this in the introduction).

Kratsios et al. (2026, Proposition A.1) use a single token (n=1n=1), so the unique softmax coefficient is 11, making their proof technically straightforward. This mechanism breaks down in the n>1n>1 multi-token setting. Following the Referee's suggestion we have explained this in the new Appendix E.1.

In Appendix E.1, we have further compared with Kratsios--Furuya (2025, Proposition 11): they propose an exact MLP-to-transformer realization for transformers acting on nn tokens without positional encodings, under a measure-valued formulation of attention (see Section 2.2 there) and activation σ(x)≔α1xp\sigma(x)\coloneqq\alpha_1x^p for x≥0x\geq 0, σ(x)≔α2x\sigma(x)\coloneqq\alpha_2x for x<0x<0. However, their mechanism fails under standard softmax attention for multi-token transformers without positional encodings. We have explained this in Appendix E.1.

In our original submission, we tackle the case of transformers with positional encoding acting on n>1n>1 tokens under standard softmax attention. To circumvent the issues mentioned above, our main new technical contribution is to engineer a new exact recovery and realization mechanism (explained in Appendix B.1). We construct this mechanism by choosing query projections that produce a constant vector at every token, keys that depend only on positional encodings, and value projections that read the original token content. We choose the positional scores so that the resulting ∑jShjxj\sum_j S_{hj}x_j form an invertible system. The attention output projections incorporate S−1⊗IdS^{-1}\otimes I_d, undoing the mixing exactly before the feed-forward layer. They update the working coordinates to contain either the full ordered input vec⁡(X)\operatorname{vec}(X) or, when width is limited, only the input-dependent preactivation terms A(u)vec⁡(X)A_{(u)}\operatorname{vec}(X). The retained positional label supplies position-dependent biases through shared weights, while residual connections accumulate the groups' outputs. If fewer heads are available, we distribute the required terms across consecutive blocks.

Furthermore, as mentioned above, in the revision, we have extended this mechanism under masked attention (covering the unmasked, sparse, and causal cases). See, in particular, Lemma B.5.

  1. In particular, which parts of the construction (the invertible softmax mixing, splitting the heads across blocks, the position-dependent biases) are new, and which are adaptations of existing arguments?

To the best of our knowledge, the main parts of the construction used in the proof of Theorem 3.3, and listed below, are new with respect to other exact realization theorems transfer principles in the literature. In particular, we list them:

Invertible softmax mixing matrix SS for exact recovery under (possibly) masked attention (we show that a shared output projection recovers, at each position ii, an encoding EiMvec⁡(X)E_i^{\mathbf M}\operatorname{vec}(X); see Lemma B.5).

Splitting heads across blocks.

Position-dependent biases (these are natural in approximation theory for transformers, e.g., Yun et al.\ (2020); however, they were not used in the literature developing exact realization theorems).

Recovery with limited working width (when the working coordinates cannot hold the full ndnd-dimensional input, attention recovers only A(u)vec⁡XA_{(u)}\operatorname{vec}X, the input-dependent terms needed by the current group of hidden units. The output projections update these coordinates using A(u)−A(u−1)A_{(u)}-A_{(u-1)}, while preserving the original input and positional information. This extends the exact recovery mechanism to narrow working width).

Our technical Appendices B.2, B.3, and B.5 also need to show that restricting the shallow approximants to the shared family preserves universality and rates.

What is the main difficulty that the multi-token setting creates, and how does the construction overcome it?

In the single-token (n=1n=1) setting of Kratsios, Neuman and Petersen (2026, Proposition A.1) and Hong, Ghoukasian and Kratsios (2026, Proposition C.3), attention has no inter-token information to gather and the proof of exact realization is technically straightforward.

For n>1n>1, their mechanism breaks down as we explain in Appendix E.1. To address this, we had to engineer a new recovery and realization mechanism (Appendix B.1) as described in our answer to Question 1.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.