# Transformers are Expressive, But Are They Expressive Enough for Regression?

Swaroop Nath  Harshad Khadilkar  Pushpak Bhattacharyya

###### Abstract

Transformers have become pivotal in Natural Language Processing, demonstrating
remarkable success in applications like Machine Translation and Summarization.
Given their widespread adoption, several works have attempted to analyze the
expressivity of Transformers. Expressivity of a neural network is the class of
functions it can approximate. A neural network is fully expressive if it can
act as a universal function approximator. We attempt to analyze the same for
Transformers. Contrary to existing claims, our findings reveal that
Transformers struggle to reliably approximate continuous functions, relying on
piecewise constant approximations with sizable intervals. The central question
emerges as: “Are Transformers truly Universal Function Approximators?” To
address this, we conduct a thorough investigation, providing theoretical
insights and supporting evidence through experiments. Our contributions
include a theoretical analysis pinpointing the root of Transformers’
limitation in function approximation and extensive experiments to verify the
limitation. By shedding light on these challenges, we advocate a refined
understanding of Transformers’ capabilities.

transformers, universal function approximation, deep learning

##  1 Introduction

Transformers (Vaswani et al., 2017) have become the de-facto backbone models
in several NLP applications: Machine Translation, Summarization, Question
Answering, etc. By modeling recurrence relations through self-attention only,
they have enabled large-scale pre-training (Radford et al., 2019; Brown et
al., 2020; Zhang et al., 2022; Touvron et al., 2023). This has led to drastic
advancements in Language Technologies over competing architectures, such as
LSTM (Hochreiter & Schmidhuber, 1997) and GRU (Cho et al., 2014).

In light of the success of Transformers, several works (Dehghani et al., 2018;
Yun et al., 2020a; Perez et al., 2021; Merrill & Sabharwal, 2023) have studied
the expressivity111Expressivity of a neural network characterizes its
capability in complexity in data. of Transformers. Specifically, two lenses
have been employed to study them: (a) Lens of Universal Function
Approximation, and (b) Lens of Formal Languages and Complexity Classes. In the
latter theme, several works have contributed to prove that expressivity of
Transformers is upper bounded by the TC$0$ complexity class. In the former
theme, Yun et al. (2020a, b); Zaheer et al. (2020) indicated that Transformers
(and their variants) are likely to be Universal Function Approximators.
However, our experimental results (Section 5) contradicted this: they are
unable to reliably approximate continuous functions. We witnessed that
Transformers could approximate the function only after a piecewise constant
approximation, with large sized pieces. Perplexed by such experimental
results, we ask a simple question: Are Transformers truly Universal Function
Approximators? While we acknowledge the theoretical results by Yun et al.
(2020a), we find that there are further implications and analyses that can
provide tighter bounds.

In this work, we conduct both theoretical and experimental analysis on the
approximation capabilities of Transformers. We find that – Transformers are
bad at approximating continuous functions. We provide a relevant theoretical
analysis in Section 4, to see where the difficulty stems from, and the
magnitude of this difficulty. To further verify our claim, we conduct
experiments222We would be releasing our code in the camera-ready paper. to
extensively test the function approximation capabilities of the Transformer.
Specifically, we conduct experiments for two axes: (a) verifying function
approximation capabilities for continuous functions, and (b) verifying
function approximation capabilities for piecewise constant functions. The
results along these two axes provide a boundary of the approximation
capabilities of the Transformers. We provide details on the datasets,
evaluation measures, and report all our results in Section 5.

Our contributions are:

  1. 1.

Theoretical analysis on expressivity of Transformers, which leads to the
finding that Transformers are bad at approximating continuous functions.

  2. 2.

Extensive experimentation evaluating the continuous function approximation
capabilities of Transformers, verifying our claim and supporting our
theoretical analysis.

##  2 Related Works

We categorize the previous works in this line into two categories: Analyzing
the expressivity of Transformers from the lens of (a) Universal Function
Approximation, and (b) Formal Languages and Complexity Classes. We first
summarize the works in these two lines, and finally provide a recap of works
that question the Transformers’ expressivity.

Lens of Universal Function Approximation. Yun et al. (2020a, b) provided some
of the first works in analyzing Transformers as Universal Function
Approximators. Notably, Yun et al. (2020a) contributed a step-by-step strategy
for analyzing Transformers under such a lens, which has been utilized in many
further works. In our work too, we build up on the strategy to show the
limitations in expressivity of Transformers. Zaheer et al. (2020) used the
strategy to deduce the expressivity of their new sparse-attention based
Transformer. More recently, Luo et al. (2022) used the strategy to prove that
Transformers with Relative Positional Embeddings are not Universal Function
Approximators.

Lens of Formal Languages. Perez et al. (2021); Dehghani et al. (2018) provided
two foundational works in this line, with opposing conclusions. Perez et al.
(2021) concluded, under assumptions like arbitrary precision, that
Transformers are Turing Complete. While, Dehghani et al. (2018) provided
intuition-based arguments to claim that Transformers are not Turing Complete.
Bhattamishra et al. (2020) provide a lower limit on the expressivity of
Transformers, concluding that Transformers are at least as powerful as
Simplified Stateless Counter Machines (SSCM). On the other hand, Merrill et
al. (2022); Hao et al. (2022); Merrill & Sabharwal (2023) show that the
expressivity of Transformers is upper-bounded by the TC$0$ complexity class.
More recently, Chiang et al. (2023) provide a tighter bound than TC$0$ for the
expressivity of Transformers.

We see that many works have probed the expressivity of Transformers from the
lens of formal languages and complexity classes. Additionally, Yun et al.
(2020a) have attempted to show that Transformers are Universal Function
Approximators. However, perplexed by our initial experimental results on the
same, we start an investigation on the Universal Function Approximation
capabilities of the Transformer. Like previous works, we provide a theoretical
analysis to examine the capability. And, unlike previous works, we extensively
test our claim through experiments.

##  3 Notations, Definitions and Preliminaries

###  3.1 Transformer Architecture

A Transformer (Vaswani et al., 2017) is a Sequence-to-Sequence mapper,
composed of two main components: Encoder and Decoder. In turn, encoders and
decoders are composed of several stacked blocks. Each block has two key
components: Self-Attention and Token-wise Feed Forward Network, The decoder
has an additional component: Cross-Attention. Using these blocks, Transformers
essentially perform a mapping from $\mathbf{X}$ ($\in\mathbb{R}^{m\times d}$)
to $\mathbf{Y}$ ($\in\mathbb{R}^{n\times d}$), where $m$ and $n$ are sequence
lengths of the input and output, and $d$ is the embedding dimension.

The Self-Attention component operates according to Equation 3.1. Specifically,
it is a dot-product attention (Luong et al., 2015), conducted across several
heads (the equation depicts $h$ heads). Token-wise Feed Forward Network
operates on each token according to Equation 3.0.3. Cross-Attention is a
variant of Self-Attention where a prefix of $\mathbf{Y}$ attends to
$\mathbf{X}$, according to Equation 3.1.

$\displaystyle\text{SA}($ $\displaystyle\mathbf{X})=\mathbf{X}+$
$\displaystyle\mathbf{\mathit{W_{O}}}\bigoplus_{i=1}^{h}\mathbf{\mathit{W_{V}^{i}}\cdot
X}\cdot\sigma\big{[}(\mathbf{\mathit{W_{K}^{i}}\cdot
X})^{T}\mathbf{\mathit{W_{Q}^{i}}\cdot X}\big{]}$ (3.0.1)

C $\displaystyle\text{A}(\mathbf{X},\mathbf{Y})=\mathbf{Y^{:j}}+$
$\displaystyle\mathbf{\mathit{W^{{}^{\prime}}_{O}}}\bigoplus_{i=1}^{h}\mathbf{\mathit{W_{V}^{{}^{\prime}i}}\cdot
X}\cdot\sigma\big{[}(\mathbf{\mathit{W_{K}^{{}^{\prime}i}}\cdot
X})^{T}\mathbf{\mathit{W_{Q}^{{}^{\prime}i}}\cdot Y^{:j}}\big{]}$ (3.0.2)

Where $\bigoplus_{i=1}^{h}$ denotes the concatenation operator along the
embedding dimension axis, $\mathit{W^{{}^{\prime}}_{O}}$,
$\mathit{W_{O}}\>(\in\mathbb{R}^{d\times hd})$,
$\mathit{W^{{}^{\prime}}_{V}}$, $\mathit{W_{V}}\>(\in\mathbb{R}^{d\times d})$,
$\mathit{W^{{}^{\prime}}_{K}}$, $\mathit{W_{K}}\>(\in\mathbb{R}^{d\times d})$,
and $\mathit{W^{{}^{\prime}}_{Q}}$, $\mathit{W_{Q}}\>(\in\mathbb{R}^{d\times
d})$ denote learnable matrices. $\mathbf{Y^{:j}}$ denotes the $j$-length
prefix of the $n$-length sequence $\mathbf{Y}$.

$\displaystyle\text{FFN}(\mathbf{X})=\mathbf{X}+\mathit{W}_{2}\cdot\text{relu}(\mathit{W}_{1}\cdot\mathbf{X}+\mathit{b}_{1})+\mathit{b}_{2}$
(3.0.3)

Where $\mathit{W}_{1}$ ($\in\mathbb{R}^{r\times d}$), $\mathit{W}_{2}$
($\in\mathbb{R}^{d\times r}$), $\mathit{b}_{1}$ ($\in\mathbb{R}^{r}$) and
$\mathit{b}_{2}$ ($\in\mathbb{R}^{d}$) are learnable matrices and vectors,
respectively.

With these notations for the operations in a Transformer, we denote a
Transformer as $\mathcal{T}^{h,d,r}$ in further sections.

(a)

(b)

Figure 1: Effect of changing the size of resolution factor. In (a) we have a
smaller resolution factor, leading to a smaller error in approximation than
(b).

###  3.2 Necessary Definitions

In this section, we provide definitions necessary for the rest of the paper.

######  Definition 3.1 (Resolution Factor).

Let $f$ be a function, and $\overline{f}$ be a piecewise constant
approximation to $f$. Then, Resolution Factor, $\delta$, is the minimum size
of the pieces in $\overline{f}$.

A large $\delta$ indicates that the interval for which $\overline{f}$ is
constant is large, Figure 1. This leads to a bad approximation if $f$ has a
high rate of change (derivative).

######  Definition 3.2 (Adequacy of Approximation).

Let $g$ be an approximation to a function $f$. We say that $g$ adequately
approximates $f$ if the following holds, for some $\epsilon>0$ and $1\leq
p<\infty$.

$d_{p}(f,g)=\bigg{(}\int\big{\|}g(x)-f(x)\big{\|}_{p}^{p}dx\bigg{)}^{\frac{1}{p}}\leq\epsilon$

$d_{p}(f,g)$ defines a distance between $f$ and $g$ for different values of
$x$. It is normalized by the norm ($p$). Prior works (Yun et al., 2020a;
Zaheer et al., 2020) have frequently used this definition for adequacy of
approximation.

######  Definition 3.3 (Function with Compact Support).

A function, $f$, is said to have a compact support iff it is non-zero for an
input from a compact set. A set is compact iff it is closed and bounded.

###  3.3 Transformers as Universal Function Approximators

In this section, we outline the $3$-step process followed by Yun et al.
(2020a). The work attempts to prove that Transformers, $\mathcal{T}^{h,d,r}$,
approximate continuous permutation equivariant functions with compact support.
We denote the set of such functions by $\mathcal{F}_{PE}$.

Step 1. Approximate $\mathcal{F}_{PE}$ with piecewise constant functions. In
this step, Yun et al. (2020a) map the class of functions $\mathcal{F}_{PE}$ to
$\mathcal{\overline{F}}_{PE}$, such that $\overline{f}$
($\in\mathcal{\overline{F}}_{PE}$) is piecewise constant. We have seen in
Definition 3.1 that the goodness of this approximation is governed by
$\delta$.

Step 2. Approximate $\mathcal{\overline{F}}_{PE}$ with modified Transformers.
Yun et al. (2020a) show that $\mathcal{\overline{F}}_{PE}$ can be approximated
by a Transformer with some simplifying modifications, such as replacing the
softmax operator with the hardmax operator.

Step 3. Approximate modified Transformers with (original) Transformers. In
this step, Yun et al. (2020a) show that the original Transformers can
approximate the modified Transformers.

Using this $3$-step process, Yun et al. (2020a, b); Zaheer et al. (2020) have
analyzed the expressivity of Transformers for their respective architectures.
Additionally, Yun et al. (2020a) also note that with a resolution factor
$\delta$, in Step 1, the number of layers in the Transformer, needed to
approximate a piecewise constant function, grows as:
$\mathcal{O}(n(1/\delta)^{dn})$.

##  4 Expressivity of Transformers in the Continuous Space

Yun et al. (2020a) show that Transformers can approximate continuous
functions, with a condition on the number of Transformer layers. We briefly
describe their arguments in Section 3.3, which show that: Transformers
($\mathcal{T}^{h,d,r}$) approximate a piecewise constant function
($\overline{f}$), which is, in turn, an approximation of the target function
($f$). The construction of the piecewise constant approximation is governed by
the resolution factor, $\delta$ (Definition 3.1). Again, we see that this
resolution factor also affects (Section 3.3) the number of layers needed for
an adequate approximation (Definition 3.2) by the Transformer. Thus, we can
deduce that: there is one factor, $\delta$, which governs the adequacy of both
approximations: (a) between $\overline{f}$ and $f$, and (b) between
$\mathcal{T}^{h,d,r}$ and $\overline{f}$. We are interested in finding how
$\delta$ affects these approximations: Does a change in $\delta$ affect both
the approximations similarly333By similar effect we mean that adequacy of both
approximations change in the same direction (worse or better)., or
dissimilarly444By dissimilar effect we mean that adequacy of both
approximations change in the opposite directions.? We answer this in steps, by
answering the following questions:

  1. 1.

What governs the choice of the resolution factor, $\delta$? We provide an
intuition (Section 4.1) and a mathematical expression to answer this question
(Theorem 4.1).

  2. 2.

How does a well-chosen resolution factor affect the conclusion of Yun et al.
(2020a), about the expressivity of Transformers?

######  Theorem 4.1.

Let $\overline{f}$ ($\in\mathcal{\overline{F}}$) be an approximation to f
($\in\mathcal{F}$), with goodness of approximation defined by
$d_{p}$($\overline{f}$, $f$) $\leq$ $\epsilon$ (for some $\epsilon>0$). Then
an upper bound on the resolution factor, $\delta$, can be expressed by the
equation:

$\delta\leq\Bigg{(}\dfrac{2^{p}\cdot(p+1)\cdot\epsilon^{p}}{\sum_{X^{0}\in\mathcal{X}^{0}}\sum_{i=1}^{d}\Big{|}\frac{\partial
f(X)}{\partial
x_{i}}\big{|}_{X^{0}}\Big{|}^{p}}\Bigg{)}^{\frac{{1}}{{(p+d)}}}$ (4.1.1)

where $\mathcal{X}^{0}$ is a covering over the compact support ($\mathcal{S}$)
for the function $f$, $p$ is the norm in $d_{p}$, and $d$ is the embedding
dimension.

From Theorem 4.1, we understand that for a decently changing function, a small
resolution factor is necessary, for an adequate approximation between
$\overline{f}$ and $f$. And, from Section 3.3, we understand that
$\mathcal{T}^{h,d,r}$ needs $\mathcal{O}(n(1/\delta)^{dn})$ layers to
approximate a permutation invariant $\overline{f}$. Thus, for a decently
changing continuous function ($f$), with a small $\delta$, large (exponential
in sequence length) number of layers are required for $\mathcal{T}^{h,d,r}$,
to adequately approximate $f$. We provide a small example quantification
below, to put this requirement into perspective.

Let $\epsilon=0.1$, $p=1$, $d=1$, and $|\mathcal{X}^{0}|=K$; for illustration,
let $K\sim 10$. Assuming $f$ to be a $1$-Lipshitz continuous function in its
compact support, we can have the bound $\frac{df(x)}{dx}\leq 1$. With such a
setup, we have a bound on resolution factor as: $\delta\leq 0.2$. Therefore,
the required number of layers for $\mathcal{T}^{h,d,r}$ grows as
$\mathcal{O}(n\cdot 5^{n})$. We can see how this goes very high for even an
input of sequence length $10$.

From the discussion above, we understand the following:

  1. 1.

The choice of $\delta$ is governed by the derivative of $f$, as highlighted by
Theorem 4.1.

  2. 2.

A well-chosen $\delta$, for even a decently changing function (say, Lipshitz
constant $=1$), leads to a requirement of large number of layers for
$\mathcal{T}^{h,d,r}$.

What if a function is already piecewise constant? In such a case, the
resolution factor is no longer constrained by the derivative (Equation 4.1.1).
Rather it depends on the size of the pieces (step-sizes). As an example, let
us consider the following piecewise constant function, defined over the
interval $[0,1)$:

$f(x)=\begin{cases}0.5&0\leq x<0.75\\\ 1.0&0.75\leq x<1.0\end{cases}$

Here, the step-sizes are $0.75$ and $0.25$. According to Definition 3.1, we
can deduce that the resolution factor, in this case, would be $0.25$. A
piecewise constant function, with small step-sizes, would still pose a
challenge for Transformers.

From the discussion, we can deduce the following things: (a) For a continuous
function, a constraint on $\delta$ is imposed as per Equation 4.1.1, and (b)
For a piecwise constant function, step-sizes constrain $\delta$, specifically
$\delta=\min(step\>sizes)$.

###  4.1 Proof Sketch for Theorem 4.1

In this section, we provide an intuition and a short proof to motivate Theorem
4.1. From Figure 1, we can see how varying the resolution factor can change
the goodness of approximation. We can understand from the figure that having a
smaller step size becomes necessary for functions with a large rate of change,
to have a certain degree of goodness in approximation. With this intuition, we
start deriving a bound on the resolution factor, based on the derivative of
the function. We provide proof for the $1$-dimensional case, using the
$\ell^{1}$ norm. We include a proof for the general case of $d$-dimensional
function, using $\ell^{p}$ norm in Appendix A.

(a)

(b)

Figure 2: (a) Behaviour of $\overline{f}(x)$ in the $\delta/2$ neighborhood of
$x^{0}$. In this neighborhood, we can approximate $f(x)$ by $f(x^{0})$, hence
$\overline{f}(x)=f(x^{0})$. (b) The shaded area in $\delta/2$ neighborhood of
$x^{0}$ for $f(x)$ can be approximated by two triangles.

###### Proof.

We have: $d_{p}$($\overline{f}$, $f$) $\leq\epsilon$; $\epsilon>0$

$\implies\bigg{(}\int_{\mathcal{S}}\big{\|}\overline{f}(x)-f(x)\big{\|}_{p}^{p}dx\bigg{)}^{\frac{1}{p}}\leq\epsilon$

Note that for $x\not\in\mathcal{S}$, $\overline{f}(x)=f(x)=0$. With $p=1$, the
expression becomes:

$\int_{\mathcal{S}}\big{|}\overline{f}(x)-f(x)\big{|}dx\leq\epsilon$

Note that the expression on the left represents the area bounded within the
curves $y=\overline{f}(x)$ and $y=f(x)$. Consider the $\delta/2$ neighborhood
of the point $x^{0}$ in Figure 2(a). A good piecewise constant approximation
of $f(x)$ in this neighborhood is $f(x^{0})$, that is
$\overline{f}(x)=f(x^{0})$ for $\big{(}x^{0}-\delta/2\big{)}\leq
x<\big{(}x^{0}+\delta/2\big{)}$. With this approximation, the expression on
the left represents the area of the shaded region (Figure 2(a)), for
$\big{(}x^{0}-\delta/2\big{)}\leq x<\big{(}x^{0}+\delta/2\big{)}$. The shaded
regions can be approximated by two triangles, as shown in Figure 2(b). Thus,
we have:

$\displaystyle\int_{x^{0}-\frac{\delta}{2}}^{x^{0}+\frac{\delta}{2}}\big{|}\overline{f}(x)-f(x)\big{|}dx$
$\displaystyle=2\cdot\dfrac{1}{2}\cdot\dfrac{\delta}{2}\cdot(\dfrac{\delta}{2}\tan(\theta))$
$\displaystyle=\dfrac{\delta^{2}}{4}\Bigg{|}\dfrac{df(x)}{dx}\bigg{|}_{x^{0}}\Bigg{|}$

Where $\dfrac{df(x)}{dx}\bigg{|}_{x^{0}}$ represents the derivative at
$x^{0}$. Now, if we considering a covering $\mathcal{X}^{0}$ of $\mathcal{S}$,
such that $x^{0}\in\mathcal{X}^{0}$, we have:

$\displaystyle\int_{\mathcal{S}}\big{|}\overline{f}(x)-f(x)\big{|}dx$
$\displaystyle=\sum_{x^{0}\in\mathcal{X}^{0}}\int_{x^{0}-\frac{\delta}{2}}^{x^{0}+\frac{\delta}{2}}\big{|}\overline{f}(x)-f(x)\big{|}dx$
$\displaystyle=\dfrac{\delta^{2}}{4}\sum_{x^{0}\in\mathcal{X}^{0}}\Bigg{|}\dfrac{df(x)}{dx}\bigg{|}_{x^{0}}\Bigg{|}$

Finally,

$\dfrac{\delta^{2}}{4}\sum_{x^{0}\in\mathcal{X}^{0}}\Bigg{|}\dfrac{df(x)}{dx}\bigg{|}_{x^{0}}\Bigg{|}\leq\epsilon$

$\implies\delta\leq\sqrt{\dfrac{4\epsilon}{\sum_{x^{0}\in\mathcal{X}^{0}}\Bigg{|}\dfrac{df(x)}{dx}\bigg{|}_{x^{0}}\Bigg{|}}}$

This matches with our expression in Equation 4.1.1. ∎

As per our intuition, we see that for functions with high rate of change, the
resolution factor has to be small.

##  5 Experiments

We use the Transformer Architecture proposed by Vaswani et al. (2017) for our
experiments. We are aware of several modifications to the vanilla architecture
(Xiong et al., 2020; Zaheer et al., 2020; Child et al., 2019; Kitaev et al.,
2020; Beltagy et al., 2020). Tay et al. (2022) provide a comprehensive survey
of all variants of Transformers. We urge the interested reader to refer to
that for more details. These works attempt to improve stability in training
and reducing computational costs, and do not focus on improving the
expressivity of Transformers. Hence, it suffices to experiment on the vanilla
Transformer architecture.

We perform experiments on sythetic datasets, to ensure that data quality does
not affect our conclusions. Specifically, we perform two experiments:

  * •

Expt-I (Regression): In this experiment, we train the Transformer to generate
vectors to directly approximate a continuous function.

  * •

Expt-II (Quantized Classification): In this experiment, we quantize the
outputs to certain classes, and train the Transformer to predict the class.

Expt-I aims to show how Transformers fare in approximating continuous
functions. In Expt-II, the output space is quantized to piecewise constants,
thereby essentially testing the Transformer’s ability to approximate piecewise
constant functions. From Section 4, we understand that Transformers would
suffer for continuous functions and small step-size piecewise constant
functions. However, for piecewise constant functions with high step-sizes
($\geq 1$), Transformers can perform well. Keeping this in mind, in Expt-II,
we train the Transformer to predict into $k$ classes, where $k$ is reasonably
small. Transformer failing in Expt-I and succeeding in Expt-II would validate
our hypothesis.

Note that, in all of our experiments, we respect the assumption of compact
support (Definition 3.3) for the functions.

(a) Trend of failure-rate vs. token-wise feed-forward network of the
Transformer. We vary the latter from $8$ to $1024$, while keeping the
embedding dimension ($d$) constant to $64$.

(b) Trend of failure-rate vs. embedding dimension of the Transformer. We vary
the latter from $4$ to $512$, while keeping the token-wise feed-forward
network dimension ($r$) equal to the embedding dimension.

Figure 3: Trend of failure-rate with respect to embedding dimension and the
dimension of token-wise feed-forward network. We perform each experiment
(training-validation-testing pipeline) $5$ times. The line in the graph
corresponds to the mean across runs, and the bands around the line indicate
the standard deviation.

###  5.1 Evaluation Measures

Comparing models for Expt-I and Expt-II is non-trivial, as one is a regression
task and the other is a classification task. In order to compare them, we
propose a unified metric: failure-rate. We define this metric as follows:

failure-rate: It is the fraction of times the ground truth output is not the
nearest one to the generated output.

For Expt-II, failure-rate is essentially inaccuracy ($1\>-$ accuracy). For
Expt-I, it is computed as the fraction of times the ground truth vector is not
the nearest-neighbor of the generated vector. We realize that this metric is
very stringent for Expt-I, as there can be a lot of points in a close-by
region, and also additionally propose failure-rate@$\mathbf{k}$. For Expt-II,
failure-rate@$k$ defines the fraction of times the correct class is not in the
top-$k$ probable outputs. For Expt-I, it is computed as the fraction of times
the ground truth vector is not in the $k$-nearest-neighbor set of the
generated vector.

The design of the metric is guided by our initial criteria of judging an
approximation (Definition 3.2). Mathematically, failure-rate is linked to the
Adequacy of Approximation as follows:

$\text{\tt failure-
rate}=\dfrac{\sum_{x\sim\mathcal{D}}\mathcal{F}(\mathcal{T}^{h,d,r},x)}{|\mathcal{D}|}$

where,

$\displaystyle\mathcal{F}(\mathcal{T}^{h,d,r},x)=$
$\displaystyle\mathbbm{1}\big{(}\exists\>y\in\mathcal{D}:d_{1}(\mathcal{T}^{h,d,r}(x),f(y))$
$\displaystyle<d_{1}(\mathcal{T}^{h,d,r}(x),f(x))\big{)}$

where, $\mathbbm{1}(z)$ if $1$ if and only if $z$ evaluates to true, and
$\mathcal{D}$ is the test set.

###  5.2 Synthetic Datasets & Design Considerations

We generate a synthetic dataset using the equations in Table 1. Notice that we
cover various functional forms (logarithmic, exponential, and polynomial),
various forms of interactions (multiplicative, and additive) among variables.
Such coverage adequately checks the expressivity in one go, rather than
designing separate datasets for various functional forms and/or interactions.
We generate $200000$, $10000$ and $20000$ samples for training, validation and
testing, respectively.

Table 1: Equations governing the synthetic data generation. Type: Input signifies that these variables are fed to the Transformer Encoder. Type: Output signifies that the Transformer is trained to generate these variables through the Decoder. By design, we have functions covering the whole spectrum of first-order derivatives ($>1$, $=1$ and $<1$). Type | Generator Function
---|---
Input | $X_{1}\sim Uniform(-1,1)$
$X_{2}=\sqrt[3]{X_{1}}$
$X_{3}$ = $2\cdot\log(2+X_{1})+X_{2}/10$
$X_{4}$ = $e^{X_{2}}+X_{3}$
Output |  $Y_{1}$ = $\dfrac{1}{5}(X_{1}+X_{2}+X_{3}+X_{4})$
$Y_{2}$ = $X_{1}\cdot Y_{1}+e^{X_{2}}+X_{3}+\log(X_{4})$
$Y_{3}$ = $\dfrac{1}{5}(X_{1}+Y_{2}+Y_{1}+\sqrt{X_{2}}+X_{3}\cdot X_{4})$

With this dataset, we ask the following empirical questions:

  * •

How does the failure-rate vary for change in the dimension of the Token-Wise
Feed Forward Network in the Transformer?

  * •

How does the failure-rate vary for change in the embedding dimension of the
Transformer?

  * •

How does the failure-rate vary with the chosen Positional Embedding scheme?

  * •

How does the failure-rate vary with the number of inputs and outputs?555We
include the data generation equations in Appendix C.

(a) Trend of failure-rate with respect to the number of outputs. We run
experiments for $1$, $2$ and $3$ outputs.

(b) Trend of failure-rate with respect to the number of inputs. We run
experiments for $2$, $3$ and $4$ inputs.

Figure 4: Trend of failure-rate with respect to the number of inputs and the
number of outputs. We perform each experiment (training-validation-testing
pipeline) $5$ times. The colored bars correspond to the mean across runs,
while the black lines indicate the standard deviation. For Expt-I, we keep
$r=d=32$, and for Expt-II, we keep $r=d=128$. These configurations were found
to be best performing from Figure 3.

###  5.3 Implementation, Results & Analysis

We use PyTorch (Paszke et al., 2017) to implement Transformers. We perform
hyperparameter tuning on batch size, gradient accumulation, epochs, etc. We
repeat each training-validation-testing pipeline $5$ times, to see the
variation in performance across runs. Refer to Appendix B for training
details.

We use mean squared error loss for Expt-I and cross-entropy loss for Expt-II.
For Expt-II, we use $5$ classes for testing the Transformer across all
settings. Additionally, we also report how the Transformer behaves for higher
number of classes, later on.

We observe that for all of the questions asked in Section 5.2, the Transformer
architecture fails significantly for Expt-I. In Figure 3(a), we analyze the
trend of performance when the token-wise feed-forward network dimension is
varied. We observe that the performance for Expt-II does not have a
discernible trend. However, for Expt-I, the failure-rate oscillates a lot.
Additionally, the standard deviation in performance across runs is
significantly more for Expt-I. In further experiments, we make a simplifying
assumption – we keep the token-wise feed-forward dimension equal to the
embedding dimension. This helps reduce the possible space of experimental
settings, and Figure 3(a) shows that it is a reasonable assumption.

In Figure 3(b), we analyze the trend of performance when the embedding
dimension of the Transformer is varied. We observe that for Expt-II, there is
a downward trend in failure-rate till embedding dimension $=128$. And, for
Expt-I, there is a similar oscillatory trend. Also, as before, the standard
deviation in performance remains high, thus further proving our hypothesis –
the inability of Transformers to reliably generate vectors to directly
approximate a continuous function. From Figure 3(b), we understand that
Transformers perform best in Expt-I for embedding dimension $=32$, and in
Expt-II for embedding dimension $=128$. In our further experiments, we follow
this configuration.

We test the Transformer by varying the number of inputs (Figure 4(b)) and
outputs (Figure 4(a)). We see that there is a significant difference between
performance in Expt-I and Expt-II irrespective of the number of inputs and
outputs. We also examine the performance across two popular positional
embedding schemes: sinusoidal (Vaswani et al., 2017), learned (Devlin et al.,
2019), Figure 6. We observe a similar thing – there is a significant
difference between performance in Expt-I and Expt-II irrespective of the
positional embedding scheme. These experiments answer all the questions we set
in Section 5.2. We test for a few more things too: (a) checking performance in
Expt-II for a higher number of classes, and (b) checking performance as $k$
increases in failure-rate@$k$.

To check the effect of higher number of classes in Expt-II, we repeat the
trend analysis study (similar to Figure 3(b)) with $20$ classes, Figure 7. We
posited earlier that for piecewise constant functions, small-sized pieces
would adversely affect performance. The number of pieces would increase as the
number of classes increases. With the range constant, this implies that a
higher number of classes would lead to smaller pieces. Hence, we expect a
higher failure-rate as the number of classes increases. However, as the
embedding dimension increases, the positioning of the constant pieces becomes
sparse, if the number of classes is kept constant. Hence, we expect failure-
rate to reduce as the number of embedding dimensions is increased. That is
exactly what we observe in the figure.

We had stated earlier, failure-rate can be a stringent metric to judge
performance in Expt-II. To alleviate the situation, we proposed failure-
rate@$k$. We examine how the performance varies across various values of $k$
for Expt-I and Expt-II, Figure 8. We see that even if $k$ is increased, the
Transformer fails significantly for Expt-I.

(a)

(b)

(c)

Figure 5: t-sne plot for the generated and ground truth $Y_{1}$ (a), $Y_{2}$
(b) and $Y_{3}$ (c). Deeper colors indicate higher density.

We also qualitatively analyze the generations in Expt-I to visualize the
failure of the Transformer in generating $Y_{1}$, $Y_{2}$, and $Y_{3}$. We
include t-sne plots of the generated and ground truth values for these three
variables, Figures 5(a), 5(b) and 5(c). For all of the variables, we see that
the Transformer fails to generate representative vectors – the densities of
generated and ground truth points differ significantly.

Figure 6: Trend of failure-rate with respect to two popular Positional
Embedding schemes: sinusoidal (Vaswani et al., 2017) and learned (Devlin et
al., 2019). We see that changing the scheme does not affect the performance
significantly. For Expt-I, we keep $r=d=32$, and for Expt-II, we keep
$r=d=128$. These configurations were found to be best performing from Figure
3. Figure 7: Trend of failure-rate with respect to embedding dimension for
$20$ classes in Expt-II. We keep $r=d=128$ for this experiment, found to be
the best configuration for Expt-II from Figure 3. Figure 8: Trend of
performance of Transformer for Expt-I and Expt-II for various $k$ in failure-
rate@$k$. For Expt-I, we keep $r=d=32$, and for Expt-II, we keep $r=d=128$.
These configurations were found to be best performing from Figure 3.

##  6 Summary, Conclusion and Future Work

In this work, we analyze the function approximation capabilities of the
Transformer. We provide a theoretical treatment, analyzing the capability, in
Section 4. Following that, we provide experimental results on several settings
to experimentally evaluate the capability, in Section 5. We find that
Transformers are bad at approximating continuous functions. However, they are
quite adept at approximating piecewise constant functions with moderately
large-sized pieces. We provide an analysis of how the approximation capability
is affected by piece size in Section 5.3. In future works, we would analyze
the individual components of the Transformer to pinpoint the source of reduced
expressivity and would attempt to expand its expressivity.

## References

  * Beltagy et al. (2020) Beltagy, I., Peters, M. E., and Cohan, A.  Longformer: The long-document transformer.  _CoRR_ , abs/2004.05150, 2020.  URL https://arxiv.org/abs/2004.05150.
  * Bhattamishra et al. (2020) Bhattamishra, S., Ahuja, K., and Goyal, N.  On the Ability and Limitations of Transformers to Recognize Formal Languages.  In Webber, B., Cohn, T., He, Y., and Liu, Y. (eds.), _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 7096–7116, Online, November 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-main.576.  URL https://aclanthology.org/2020.emnlp-main.576.
  * Brown et al. (2020) Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D.  Language models are few-shot learners.  _CoRR_ , abs/2005.14165, 2020.  URL https://arxiv.org/abs/2005.14165.
  * Chiang et al. (2023) Chiang, D., Cholak, P., and Pillay, A.  Tighter bounds on the expressivity of transformer encoders.  In _Proc. ICML_ , pp. 5544–5562, 2023.
  * Child et al. (2019) Child, R., Gray, S., Radford, A., and Sutskever, I.  Generating long sequences with sparse transformers.  _CoRR_ , abs/1904.10509, 2019.  URL http://arxiv.org/abs/1904.10509.
  * Cho et al. (2014) Cho, K., van Merriënboer, B., Bahdanau, D., and Bengio, Y.  On the properties of neural machine translation: Encoder–decoder approaches.  In Wu, D., Carpuat, M., Carreras, X., and Vecchi, E. M. (eds.), _Proceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation_ , pp. 103–111, Doha, Qatar, October 2014. Association for Computational Linguistics.  doi: 10.3115/v1/W14-4012.  URL https://aclanthology.org/W14-4012.
  * Dehghani et al. (2018) Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, L.  Universal transformers.  _ArXiv_ , abs/1807.03819, 2018.  URL https://api.semanticscholar.org/CorpusID:49667762.
  * Devlin et al. (2019) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In Burstein, J., Doran, C., and Solorio, T. (eds.), _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1423.  URL https://aclanthology.org/N19-1423.
  * Hao et al. (2022) Hao, Y., Angluin, D., and Frank, R.  Formal language recognition by hard attention transformers: Perspectives from circuit complexity.  _Transactions of the Association for Computational Linguistics_ , 10:800–810, 2022.  doi: 10.1162/tacl˙a˙00490.  URL https://aclanthology.org/2022.tacl-1.46.
  * Hochreiter & Schmidhuber (1997) Hochreiter, S. and Schmidhuber, J.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Kitaev et al. (2020) Kitaev, N., Kaiser, L., and Levskaya, A.  Reformer: The efficient transformer.  _CoRR_ , abs/2001.04451, 2020.  URL https://arxiv.org/abs/2001.04451.
  * Luo et al. (2022) Luo, S., Li, S., Zheng, S., Liu, T.-Y., Wang, L., and He, D.  Your transformer may not be as powerful as you expect.  In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), _Advances in Neural Information Processing Systems_ , volume 35, pp. 4301–4315. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/1ba5f64159d67775a251cf9ce386a2b9-Paper-Conference.pdf.
  * Luong et al. (2015) Luong, T., Pham, H., and Manning, C. D.  Effective approaches to attention-based neural machine translation.  In Màrquez, L., Callison-Burch, C., and Su, J. (eds.), _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pp. 1412–1421, Lisbon, Portugal, September 2015. Association for Computational Linguistics.  doi: 10.18653/v1/D15-1166.  URL https://aclanthology.org/D15-1166.
  * Merrill & Sabharwal (2023) Merrill, W. and Sabharwal, A.  The parallelism tradeoff: Limitations of log-precision transformers.  _Transactions of the Association for Computational Linguistics_ , 11:531–545, 2023.  doi: 10.1162/tacl˙a˙00562.  URL https://aclanthology.org/2023.tacl-1.31.
  * Merrill et al. (2022) Merrill, W., Sabharwal, A., and Smith, N. A.  Saturated transformers are constant-depth threshold circuits.  _Transactions of the Association for Computational Linguistics_ , 10:843–856, 2022.  doi: 10.1162/tacl˙a˙00493.  URL https://aclanthology.org/2022.tacl-1.49.
  * Paszke et al. (2017) Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A.  Automatic differentiation in pytorch.  In _NIPS-W_ , 2017.
  * Perez et al. (2021) Perez, J., BarcelÃ³, P., and Marinkovic, J.  Attention is turing-complete.  _Journal of Machine Learning Research_ , 22(75):1–35, 2021.  URL http://jmlr.org/papers/v22/20-302.html.
  * Radford et al. (2019) Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I.  Language models are unsupervised multitask learners.  2019\.  URL https://api.semanticscholar.org/CorpusID:160025533.
  * Tay et al. (2022) Tay, Y., Dehghani, M., Bahri, D., and Metzler, D.  Efficient transformers: A survey.  _ACM Comput. Surv._ , 55(6), dec 2022.  ISSN 0360-0300.  doi: 10.1145/3530811.  URL https://doi.org/10.1145/3530811.
  * Touvron et al. (2023) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lample, G.  Llama: Open and efficient foundation language models, 2023.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I.  Attention is all you need.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf.
  * Xiong et al. (2020) Xiong, R., Yang, Y., He, D., Zheng, K., Zheng, S., Xing, C., Zhang, H., Lan, Y., Wang, L., and Liu, T.  On layer normalization in the transformer architecture.  In III, H. D. and Singh, A. (eds.), _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 10524–10533. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/xiong20b.html.
  * Yun et al. (2020a) Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S., and Kumar, S.  Are transformers universal approximators of sequence-to-sequence functions?  In _International Conference on Learning Representations_ , 2020a.
  * Yun et al. (2020b) Yun, C., Chang, Y.-W., Bhojanapalli, S., Rawat, A. S., Reddi, S., and Kumar, S.  O(n) connections are expressive enough: Universal approximability of sparse transformers.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 13783–13794. Curran Associates, Inc., 2020b.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/9ed27554c893b5bad850a422c3538c15-Paper.pdf.
  * Zaheer et al. (2020) Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q., Yang, L., and Ahmed, A.  Big bird: Transformers for longer sequences.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 17283–17297. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/c8512d142a2d849725f31a9a7a361ab9-Paper.pdf.
  * Zhang et al. (2022) Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., Mihaylov, T., Ott, M., Shleifer, S., Shuster, K., Simig, D., Koura, P. S., Sridhar, A., Wang, T., and Zettlemoyer, L.  Opt: Open pre-trained transformer language models, 2022.

##  Appendix A Proof for Theorem 4.1

###### Proof.

We have: $d_{p}(\overline{f},f)\leq\epsilon$

$\implies\bigg{(}\int_{\mathcal{S}}\big{\|}\overline{f}(X)-f(X)\big{\|}_{p}^{p}dx\bigg{)}^{\frac{1}{p}}\leq\epsilon$

Note that for $X\not\in\mathcal{S}$, $\overline{f}(X)=f(X)=0$. Now,

$\displaystyle\big{\|}\overline{f}(X)-f(X)\big{\|}_{p}^{p}$
$\displaystyle=\bigg{\\{}\sum_{i=1}^{d}\big{|}\overline{f}(X)_{i}-f(X)_{i}\big{|}^{p}\bigg{\\}}^{p\times{\frac{1}{p}}}$
$\displaystyle=\sum_{i=1}^{d}\big{|}\overline{f}(X)_{i}-f(X)_{i}\big{|}^{p}$

So, we have,

$\displaystyle\bigg{(}\int_{\mathcal{S}}\big{\|}\overline{f}(X)-f(X)\big{\|}_{p}^{p}dx\bigg{)}^{\frac{1}{p}}$
$\displaystyle\leq\epsilon$
$\displaystyle\implies\bigg{(}\int_{\mathcal{S}}\sum_{i=1}^{d}\big{|}\overline{f}(X)_{i}-f(X)_{i}\big{|}^{p}dX\bigg{)}^{\frac{1}{p}}$
$\displaystyle\leq\epsilon$

Similar to the proof in Section 4.1, we look at the $\delta/2$ neighborhood of
$X^{0}$. Note that the neighborhood is a hypercube. As before, we have
$\overline{f}(X)=f(X^{0})$ in this neighborhood. Again, in this neighborhood,
$f(X)$ can be rewritten as:

$f(X)_{i}=f(X^{0})_{i}+\dfrac{\partial f(X)}{\partial
x_{i}}\bigg{|}_{X^{0}}(x_{i}-x^{0}_{i})\quad\forall i$

where $x_{i}$ denotes the $i$-th component of $X$. With
$\overline{f}(X)=f(X^{0})$, we have,

$\overline{f}(X)_{i}-f(X)_{i}=-\dfrac{\partial f(X)}{\partial
x_{i}}\bigg{|}_{X^{0}}(x_{i}-x^{0}_{i})\quad\forall i$

Thus, in the $\delta/2$ neighborhood of $X^{0}$, we can compute the $\ell^{p}$
error of approximation as ($[\delta/2]_{d}$ denotes a $d$-dimensional vector,
with each element as $\delta/2$):

$\displaystyle\int_{X^{0}-[\delta/2]_{d}}^{X^{0}+[\delta/2]_{d}}\sum_{i=1}^{d}\big{|}\overline{f}(X)_{i}-f(X)_{i}\big{|}^{p}dX$
$\displaystyle=\int_{X^{0}-[\delta/2]_{d}}^{X^{0}+[\delta/2]_{d}}\sum_{i=1}^{d}\Bigg{|}\dfrac{\partial
f(X)}{\partial x_{i}}\bigg{|}_{X^{0}}(x_{i}-x^{0}_{i})\Bigg{|}^{p}dX$
$\displaystyle=\int_{X^{0}-[\delta/2]_{d}}^{X^{0}+[\delta/2]_{d}}\sum_{i=1}^{d}\Bigg{|}\dfrac{\partial
f(X)}{\partial
x_{i}}\bigg{|}_{X^{0}}\Bigg{|}^{p}\big{|}x_{i}-x^{0}_{i}\big{|}^{p}dX$
$\displaystyle=\sum_{i=1}^{d}\Bigg{|}\dfrac{\partial f(X)}{\partial
x_{i}}\bigg{|}_{X^{0}}\Bigg{|}^{p}\int_{X^{0}-[\delta/2]_{d}}^{X^{0}+[\delta/2]_{d}}\big{|}x_{i}-x^{0}_{i}\big{|}^{p}dX$

The integral can be computed as follows:

$\displaystyle\int_{X^{0}-[\delta/2]_{d}}^{X^{0}+[\delta/2]_{d}}\big{|}x_{i}-x^{0}_{i}\big{|}^{p}dX$
$\displaystyle=\int_{x^{0}_{i}-\delta/2}^{x^{0}_{i}+\delta/2}$
$\displaystyle\big{|}x_{i}-x^{0}_{i}\big{|}^{p}dx_{i}\int_{X^{0}_{-i}-[\delta/2]_{d-1}}^{X^{0}_{-i}+[\delta/2]_{d-1}}dX_{-i}$

$X_{-i}$ denotes the components of $X$ other than the $i$-th component. Note
that the integral is truly a multiple integral over all the dimensions. This
lets us compute the integral for the $i$-th and other dimensions separately.
Now, the second integral is essentially the volume of a $d-1$ dimensional
hypercube of side $\delta$. It evaluates to $\delta^{d-1}$. We can compute the
first integral as:

$\displaystyle\quad\quad\quad\int_{x^{0}_{i}-\delta/2}^{x^{0}_{i}+\delta/2}\big{|}x_{i}-x^{0}_{i}\big{|}^{p}dx_{i}$
$\displaystyle=\int_{-\delta/2}^{\delta/2}|u|^{p}dx_{i}\quad\text{[Change of
variable; $u=x_{i}-x^{0}_{i}$]}$
$\displaystyle=2\cdot\int_{0}^{\delta/2}u^{p}dx_{i}\quad\text{[$|u|^{p}$ is
symmetric about $0$]}$
$\displaystyle=2\cdot\dfrac{u^{p+1}}{p+1}\bigg{|}_{0}^{\delta/2}=\dfrac{1}{p+1}\cdot
2^{-p}\cdot\delta^{p+1}$

Thus, we have,

$\displaystyle\int_{X^{0}-[\delta/2]_{d}}^{X^{0}+[\delta/2]_{d}}$
$\displaystyle\sum_{i=1}^{d}\big{|}\overline{f}(X)_{i}-f(X)_{i}\big{|}^{p}dX$
$\displaystyle=\sum_{i=1}^{d}\Bigg{|}\dfrac{\partial f(X)}{\partial
x_{i}}\bigg{|}_{X^{0}}\Bigg{|}^{p}$ $\displaystyle\dfrac{1}{p+1}\cdot
2^{-p}\cdot\delta^{p+1}\cdot\delta^{d-1}$
$\displaystyle=\sum_{i=1}^{d}\Bigg{|}\dfrac{\partial f(X)}{\partial
x_{i}}\bigg{|}_{X^{0}}\Bigg{|}^{p}$ $\displaystyle\dfrac{1}{p+1}\cdot
2^{-p}\cdot\delta^{p+d}$

As in Section 4.1, if we consider a covering $\mathcal{X}^{0}$ of
$\mathcal{S}$, such that $X^{0}\in\mathcal{X}^{0}$, we have:

$\displaystyle\bigg{(}\int_{\mathcal{S}}\sum_{i=1}^{d}\big{|}\overline{f}(X)_{i}-f(X)_{i}\big{|}^{p}dX\bigg{)}^{\frac{1}{p}}\leq\epsilon$
$\displaystyle\Rightarrow\sum_{X^{0}\in\mathcal{X}^{0}}\int_{X^{0}-[\delta/2]_{d}}^{X^{0}+[\delta/2]_{d}}\sum_{i=1}^{d}\big{|}\overline{f}(X)_{i}-f(X)_{i}\big{|}^{p}dX\leq\epsilon^{p}$
$\displaystyle\Rightarrow\sum_{X^{0}\in\mathcal{X}^{0}}\sum_{i=1}^{d}\Bigg{|}\dfrac{\partial
f(X)}{\partial
x_{i}}\bigg{|}_{X^{0}}\Bigg{|}^{p}\dfrac{\delta^{p+d}}{\displaystyle
2^{p}\cdot(p+1)}\leq\epsilon^{p}$
$\displaystyle\Rightarrow\dfrac{\delta^{p+d}}{\displaystyle
2^{p}\cdot(p+1)}\Bigg{(}\sum_{X^{0}\in\mathcal{X}^{0}}\sum_{i=1}^{d}\Bigg{|}\dfrac{\partial
f(X)}{\partial x_{i}}\bigg{|}_{X^{0}}\Bigg{|}^{p}\Bigg{)}\leq\epsilon^{p}$
$\displaystyle\Rightarrow\delta\leq\Bigg{(}\dfrac{2^{p}\cdot(p+1)\cdot\epsilon^{p}}{\sum_{X^{0}\in\mathcal{X}^{0}}\sum_{i=1}^{d}\Big{|}\frac{\partial
f(X)}{\partial x_{i}}\big{|}_{X^{0}}\Big{|}^{p}}\Bigg{)}^{{\frac{1}{(p+d)}}}$

∎

##  Appendix B Training Details

We perform an extensive hyperparameter search for each experimental setting
using wandb.ai. We search for the best combination for the following
hyperparameters: batch size, maximum number of training steps, learning rate,
number of attention heads, number of transformer layers, dropout and warmup
steps for learning rate. We list the range of each in Table 2. We found that
the best combination for each setup is not the same.

We train all our models on a single A$100$ GPU, with each training consuming
$\sim 2.5$ GB GPU memory and $\sim 1-3$ hours of training.

Table 2: Search Space for Hyperparamters. {$\cdot$} denotes a set, $\sim\mathcal{U}(l,h)$ denotes sampling from a Uniform distribution within $l$ and $h$. num-layers corresponds to the number of transformer layers, max-steps corresponds to the maximum training steps, num-attn-heads corresponds to the number of attention heads, warmup-steps corresponds to the fraction of training steps used for learning rate warmup, and emb-dim denotes the embedding dimension of the transformer. Hyperparameter | Values
---|---
batch-size |  {$128$, $256$, $512$}
max-steps |  {$1200$, $1400$, $1600$}
num-layers |  {$2$, $4$, $6$}
num-attn-heads |  {$2$, $4$, $\cdots$, $\min$($16$, emb-dim)}
learning-rate | $\sim\mathcal{U}(10^{-2},5\times 10^{-6})$
warmup-steps | $\sim\mathcal{U}(0.2,0.4)$
dropout | $\sim\mathcal{U}(0.1,0.2)$

##  Appendix C Details on Auxiliary Datasets

We had provided ablation studies on how the performance varies for different
number of inputs and outputs. Here, we provide the equations governing the
generation of those datasets. These generation equations are minor variations
of equations in Table 1, which generates data for $4$ inputs and $3$ outputs.
Tables 3, 4, 5, 6 show the equations for ablations on $2$ inputs, $3$ inputs,
$1$ output and $2$ outputs.

Table 3: Equations governing the synthetic data generation for $2$ inputs and $3$ outputs. Type | Generator Function
---|---
Input | $X_{1}\sim Uniform(-1,1)$
$X_{2}=\sqrt[3]{X_{1}}$
Output |  $Y_{1}$ = $\dfrac{1}{5}(X_{1}+X_{2})$
$Y_{2}$ = $X_{1}\cdot Y_{1}+e^{X_{2}}$
$Y_{3}$ = $\dfrac{1}{5}(X_{1}+Y_{2}+Y_{1}+\sqrt{X_{2}})$
Table 4: Equations governing the synthetic data generation for $3$ inputs and $3$ outputs. Type | Generator Function
---|---
Input | $X_{1}\sim Uniform(-1,1)$
$X_{2}=\sqrt[3]{X_{1}}$
$X_{3}$ = $2\cdot\log(2+X_{1})+X_{2}/10$
Output |  $Y_{1}$ = $\dfrac{1}{5}(X_{1}+X_{2}+X_{3})$
$Y_{2}$ = $X_{1}\cdot Y_{1}+e^{X_{2}}+X_{3}$
$Y_{3}$ = $\dfrac{1}{5}(X_{1}+Y_{2}+Y_{1}+\sqrt{X_{2}})$
Table 5: Equations governing the synthetic data generation for $4$ inputs and $1$ output. Type | Generator Function
---|---
Input | $X_{1}\sim Uniform(-1,1)$
$X_{2}=\sqrt[3]{X_{1}}$
$X_{3}$ = $2\cdot\log(2+X_{1})+X_{2}/10$
$X_{4}$ = $e^{X_{2}}+X_{3}$
Output |  $Y_{1}$ = $\dfrac{1}{5}(X_{1}+X_{2}+X_{3}+X_{4})$
Table 6: Equations governing the synthetic data generation for $4$ inputs and $2$ outputs. Type | Generator Function
---|---
Input | $X_{1}\sim Uniform(-1,1)$
$X_{2}=\sqrt[3]{X_{1}}$
$X_{3}$ = $2\cdot\log(2+X_{1})+X_{2}/10$
$X_{4}$ = $e^{X_{2}}+X_{3}$
Output |  $Y_{1}$ = $\dfrac{1}{5}(X_{1}+X_{2}+X_{3}+X_{4})$
$Y_{2}$ = $X_{1}\cdot Y_{1}+e^{X_{2}}+X_{3}+\log(X_{4})$