A unified framework for establishing the universal approximation of transformer-type architectures

We sincerely thank the reviewer for the thoughtful critique. Below we address each concern in turn and will integrate the requested citations and clarifications in the future version.

Relation to Agrachev and Letrouit (2024)

We appreciate the reviewer pointing us to this important reference and will include it in the revised version. While both works study expressivity via symmetry-aware controllability, there are substantial differences:

• Notion of “distinguishability”: In Agrachev & Letrouit, “distinct samples” refer to a set of distinct points $X_1,\cdots, X_N$ in the quotient manifold $M = \mathbb{R}^{d \times n} / G$. This is part of the problem formulation for the simultaneous controllability. In contrast, our notion of token distinguishability (Def. 3) is a condition imposed on the architecture family $\mathcal G$, requiring the existence of $g\in \mathcal G$ such that all the $d$-dimensional tokens in $g(X_1),\cdots, g(X_N)$ are distinct. This requirement arises from the token-wise implementation of the feedforward layers.

• Genericity vs. sufficient conditions: Agrachev & Letrouit (2024) proves that the architectures that satisfy controllability is large in a topological sense - roughly that if we were to randomly (assuming that this could be done) pick a architecture, it should satisfy controllability. However, such results cannot tell us whether a specific architecture has controllability or not. This is where our type of results come in, providing explicit and verifiable sufficient conditions on transformer architectures to achieve approximation.

  Both their and our results reveal the power of deep network approximation, but in different ways and complement our understanding.

• Approximation vs. interpolation: Their notion of ensemble controllability aligns with interpolation property (Prop. 1 in Appendix A). In contrast, our results also incorporates the approximation results. As shown in Cheng, Li, Lin & Shen, 2025, interpolation does not imply UAP in general.

On the measure-theoretic perspective and variable-length inputs

We acknowledge the growing interest in framing transformers as maps between probability measures (e.g., Furuya et al., Geshkovski et al.), especially for variable-length inputs. Our work, however, focuses on fixed-length sequence-to-sequence transformers, which remain prevalent in practice (e.g., in encoding tasks, classification, and contrastive learning). In such settings, function approximation over compact subsets of $\mathbb{R}^{d \times n}$ remains standard.

Furthermore, sparse, low-rank and some other attention mechanisms do not lift transparently to measure-valued inputs as the standard attention layer in Furuya et al; our framework accommodates them directly. By contrast, measure-theoretic perspectives should be important in formulating varying-length autoregressive decoders but may be less suited to these architectural variants.

On the role of architectural mechanisms

Our framework abstracts the transformer block into token-mixing and token-wise components, allowing us to analyze a wide class of architectures without relying on the exact form of architecture components, including multi-head attention, mixture-of-experts, etc. These mechanisms can be viewed as design choices within either component. While quantifying their precise roles in approximation is indeed an important direction, such analysis is orthogonal to our current goal of providing general UAP conditions and is left to future work.

On approximation complexity

We are not entirely certain what is meant by “complexity independent of the number of data points.” If the reviewer is referring to the sequence length $n$ (as commonly done in measure-theoretic works), then we believe such independence is unlikely. As the number of tokens increases, the space of functions to approximate becomes essentially more complex. For example, in interpolation-based frameworks like Agrachev & Letrouit (2024), the number of required number of samples $N$ grows exponentially with $n$ to support an approximation result.

On the other hand, if the question concerns whether the approximation complexity can be independent of the number of interpolation points in the function domain, then Cheng, Li, Lin & Shen (2025) discusses related results in the feedforward case. Combining such insights with structure-specific analysis of token-mixing layers may lead to bounds in certain settings, but this is beyond the scope of our current work.

We hope these clarifications address the reviewer’s concerns. We will incorporate the suggested references and improve the exposition, particularly with regard to clarity and positioning relative to prior work. Thank you again for your willingness to reconsider your evaluation.

References:

Geshkovski, B., Rigollet, P., & Ruiz-Balet, D. (2024). Measure-to-measure interpolation using Transformers. arXiv preprint arXiv:2411.04551.

Furuya, T., de Hoop, M. V., & Peyré, G. Transformers are Universal In-context Learners. In The Thirteenth International Conference on Learning Representations.

Cheng, J., Li, Q., Lin, T., & Shen, Z. (2025). Interpolation, approximation, and controllability of deep neural networks. SIAM Journal on Control and Optimization, 63(1), 625-649.

Agrachev, A., & Sarychev, A. (2020). Control in the spaces of ensembles of points. SIAM Journal on Control and Optimization, 58(3), 1579-1596.

We sincerely thank the reviewer for taking the time to assess our work and for the constructive comments.

On normalization layers and empirical validation

• We acknowledge that normalization layers are crucial for practical transformer architectures. As noted in our response to Reviewer #1, extending the theoretical analysis to include normalization is a promising direction for future work.

• Regarding the absence of empirical experiments, we emphasize that our contribution is theoretical in nature. Nevertheless, we agree that validating the practical implications of the framework through numerical experiments is an interesting future direction.

We sincerely thank the reviewer for the positive and insightful feedback.

On the lack of normalization layers

We acknowledge the omission of normalization layers as a limitation. This is a common simplification in theoretical analyses of transformer architectures, intended to isolate core components such as attention and feedforward layers. From a mathematical perspective, normalization introduces a nonlinear projection onto a product of unit spheres, altering the function family $\mathcal{T}_{\mathcal{G}, \mathcal{H}}$. Inspired by recent theoretical studies on dynamics constrained to spheres (e.g., [1]), we believe that extending our framework to include normalization is a promising future direction.

On $D_n$ and $C_n$ symmetry

Our intention is not to claim that $D_n$ or $C_n$ symmetries are typical in practical tasks. Rather, these examples serve to illustrate how our framework enables principled design of transformer architectures respecting general symmetry constraints—beyond the full permutation group. Such symmetries do arise in specific scientific domains: $D_n$ symmetry corresponds to the structure of regular molecules, while $C_n$ symmetry is relevant for periodic data, as we have mentioned in line 339-341. Other group symmetries (e.g., alternating groups, space groups) also appear in physics and chemistry, and could be explored

On functions without symmetry

Our framework naturally encompasses functions without symmetry as the special case where the symmetry group $G = { \text{Id} }$. Also, as noted in lines 119–122, prior work shows that for any architecture family satisfying $G$-UAP with nontrivial $G$, adding a suitable positional encoding allows approximation of general, non-equivariant functions. Hence, our focus on $G$-UAP is not restrictive, but rather provides a unified treatment of both symmetric and non-symmetric function classes.

Reference: [1] Geshkovski, B., Rigollet, P., & Ruiz-Balet, D. (2024). Measure-to-measure interpolation using Transformers. arXiv:2411.04551.

I thank the authors for their rebuttal, and I believe this would be worth a poster at the conference. I will keep my original rating.

We sincerely thank the reviewer for your positive and insightful feedback.

On notation and minor suggestions

• We acknowledge that the use of the term "token" may be potentially ambiguous. Following your suggestion, we will add a footnote after Eq. (1) clarifying that we slightly abuse terminology by referring to any column of $X_t$ as a "token", even though it is the continuous embedding of a discrete input symbol.

• We appreciate your careful reading and will correct the typo in line 102. We will also adopt your suggestion to replace "tensor-type functions" with "tensor-product functions" for better clarity.