Approximation Error Upper and Lower Bounds for Hölder Class with Transformers

Xin He, Yuling Jiao, Xiliang Lu, Jerry Zhijian Yang

Introduction

Despite the world-dominating success of Transformers, our theoretical understanding of why they work so well has lagged behind their empirical achievements. Specifically, the field has lacked precise "approximation bounds"—mathematical guarantees dictating how many layers or parameters a Transformer needs to represent a specific type of complex function.

Previous theoretical studies often took shortcuts to make the math tractable, such as replacing the Softmax operator with simpler functions (like Hardmax) or removing residual connections. However, these variants do not reflect the models actually deployed in production. This paper tackles the "standard" Transformer architecture head-on—including Softmax, ReLU activations, and residual connections—to determine its fundamental expressive power and establish a theoretical "speed limit" for the architecture.

Theoretical Framework and Methodology

The authors employ a mix of constructive proofs and statistical learning theory. As a theoretical paper, it does not rely on empirical datasets like ImageNet or GLUE. Instead, it uses the Hölder class of functions as its target benchmark. This is a standard mathematical measure for smoothness, where the complexity of the task is defined by the input dimension ($d_0$) and the smoothness index ($\alpha \in (0,1]$).

To establish the bounds, the researchers utilized two primary approaches:

  1. Upper Bound Construction: To prove that a Transformer can approximate a function, they explicitly design a network composed of three specialized modules:
  2. Quantization Module: Maps continuous inputs onto a discrete grid.
  3. Contextual Mapping: Uses a single Softmax-based attention head to "memorize" and distinguish tokens within a sequence.
  4. Value Mapping: Maps those unique contextual IDs to the final target values.
  5. Lower Bound via VC-Dimension: To prove a Transformer must have a certain size, they utilize Vapnik-Chervonenkis (VC) dimension theory. They derive a new VC-dimension upper bound for Transformers ($\approx D^4$, where $D$ is the number of blocks) to show that if a model is too small, it simply lacks the "shattering" capacity to represent complex Hölder functions.

Key Insights and Results

The paper successfully establishes precise bounds and generalization capabilities for the standard Transformer:

  • The Upper Bound: A standard Transformer with at most $\mathcal{O}(\varepsilon^{-d_0/\alpha})$ blocks can approximate any bounded Hölder function to within an accuracy of $\varepsilon$.
  • The Lower Bound: To achieve that same accuracy $\varepsilon$, a Transformer must have at least $\Omega(\varepsilon^{-d_0/(4\alpha)})$ blocks. This represents the first rigorous lower bound established for the standard Transformer architecture.
  • Generalization in Regression: Extending these bounds to a practical regression setting with $N$ samples, the Transformer achieves an excess risk rate of roughly $N^{-\frac{\alpha}{2d_0+\alpha}}$. This aligns with the minimax optimal rates seen in deep ReLU networks, proving Transformers are theoretically as efficient as the best-known neural architectures.

Beyond the raw bounds, the proofs reveal several architectural insights. The authors demonstrate that a single Softmax head is sufficient to perform contextual mapping, underscoring why attention is the "secret sauce" of the architecture. Furthermore, unlike previous proofs that broke the residual chain to simplify the math, this paper's construction strategy keeps residual connections intact, making the results highly applicable to real-world inductive biases. Finally, the paper proves a flexible depth-width trade-off: approximation accuracy can be maintained by either adding more blocks (depth) or making the internal layers wider, provided the total budget meets the $\mathcal{O}(\varepsilon^{-d_0/\alpha})$ requirement.

Limitations and Future Directions

While this work establishes a rigorous foundation, the authors note several areas for future exploration:

  • The Approximation Gap: There is a notable gap between the upper bound ($1/\alpha$) and the lower bound ($1/4\alpha$). Closing this gap is necessary to find the true theoretical limit of the architecture.
  • Higher Smoothness: The current construction does not fully exploit cases where the target function is extremely smooth ($\alpha > 1$). Future work could investigate "polynomial" approximations within the Transformer blocks.
  • Multi-Layer Attention: This study focuses on the capabilities of a single attention layer within a block. Exploring the composition of multiple attention layers could lead to even tighter bounds.
  • Optimization Error: The paper assumes the ability to find the "best" parameters. In reality, training and optimization are difficult, and analyzing optimization error remains an open challenge for future research.

Summary updated

Abstract

We explore the expressive power of Transformers by establishing precise approximation error upper and lower bounds for Hölder class. Specifically, a new approximation upper bound is derived for the standard Transformer architecture equipped with Softmax operators, ReLU activation functions, and residual connections. We prove that a Transformer network composed of at most $\mathcal{O}(\varepsilon^{-{d_{0}}/{\alpha}})$ blocks can approximate any bounded Hölder function with $d_{0}$-dimensional input and smoothness $\alpha\in(0,1]$ under any accuracy $\varepsilon>0$. In the case of approximation lower bounds, leveraging the VC-dimension upper bound, we are the first to rigorously prove that Transformers demand for at least $\Omega(\varepsilon^{-{d_{0}}/({4\alpha})})$ blocks to achieve the $\varepsilon$ approximation accuracy. As a final step, we extend the derived results for standard Transformers to a general regression task and establish the corresponding excess risk rates demonstrating Transformers' empirical effectiveness in real-world settings.
BibTeX
@inproceedings{he2026approximation,
  author = {Xin He and Yuling Jiao and Xiliang Lu and Jerry Zhijian Yang},
  title = {{Approximation Error Upper and Lower Bounds for Hölder Class with Transformers}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=mWBxEAq9lv},
}
Figure