# On the Computational Complexity of Self-Attention

Feyza Duman Keles∗, Pruthuvi Mahesakya Wijewardena†, Chinmay Hegde
∗New York University, †Microsoft
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
FDK and CH are with the Tandon School of Engineering at New York University.
PMW is with Microsoft. This work was supported in part by grants National
Science Foundation (under grants CCF-2005804 and CCF-1801495) and USDA/NIFA
(under grant 2021-67021-35329).

###### Abstract

Transformer architectures have led to remarkable progress in many state-of-art
applications. However, despite their successes, modern transformers rely on
the self-attention mechanism, whose time- and space-complexity is quadratic in
the length of the input. Several approaches have been proposed to speed up
self-attention mechanisms to achieve sub-quadratic running time; however, the
large majority of these works are not accompanied by rigorous error
guarantees. In this work, we establish lower bounds on the computational
complexity of self-attention in a number of scenarios. We prove that the time
complexity of self-attention is necessarily quadratic in the input length,
unless the Strong Exponential Time Hypothesis (SETH) is false. This argument
holds even if the attention computation is performed only approximately, and
for a variety of attention mechanisms. As a complement to our lower bounds, we
show that it is indeed possible to approximate dot-product self-attention
using finite Taylor series in linear-time, at the cost of having an
exponential dependence on the polynomial order.

##  1 Introduction

#### Motivation.

Building upon early successes in natural language processing [1, 2],
transformer models now form the core of virtually every state-of-the-art
approach in numerous applications: computer vision and image understanding [3,
4], proteomics [5], code synthesis [6], and vision-language models [7, 8]. At
the heart of transformer architectures is the _self-attention_ mechanism,
which can be viewed as a trainable “layer” that takes in as input a set of
tokens (vectors), computes pairwise dot-products between (projected forms of)
the tokens, performs a softmax operation to obtain non-negative weights, and
produces output tokens using these weights.

Unfortunately, by virtue of its very definition, the standard form of self-
attention requires pairwise token operations, and therefore incurs quadratic
running time in terms of the number of input tokens. This poses serious
computational challenges not just in terms of the training cost of such
models, but even just for inference (forward passes) through transformer
models. The community has long acknowledged this fact, and numerous
approximate forms of self-attention that break this quadratic bottleneck have
been proposed. Some approaches advocate reducing complexity through windowing,
striding, or some other sparsification of the attention scores [9, 10]. Others
leverage ideas from hashing [9, 11]. Yet others propose kernelizing the
attention operation [12, 13, 14].

Empirically, all these methods certainly seem to lead to reduced running
times: in some cases, they reduce the costs from quadratic to linear. However,
_all_ of these methods incur some form of error in the computation (compared
to vanilla attention). These errors may have the undesirable (but benign)
effect of drop in accuracy, or may have more dramatic effects if fed with an
adversarial input. In any case, it would be useful to clearly establish
rigorous guarantees on time/accuracy tradeoffs for the above methods, but
these are rare. The primary theoretical question that we ask is as follows:

> _What are the fundamental computational tradeoffs involved in self-
> attention?_

#### Our contributions.

In this paper, we pursue a complementary path from most previously published
work in this area. Somewhat surprisingly, we are able to establish
(conditional) _quadratic lower bounds_ on the running time of self-attention
in a large variety of settings. This quadratic barrier holds _even_ if we
relax the self-attention operation and allow for additive, or multiplicative,
errors in the computation. We also prove quadratic — specifically, rectangular
— lower bounds even if we allow for windowing or striding. Finally, this holds
even if we use kernelization (with radial basis function kernels), which to
our current knowledge, achieves the Pareto time/accuracy frontier in terms of
empirical performance among all fast algorithms for self-attention computation
[13]. In Table 1, we summarize hardness results where checkmarks indicate the
proven complexities in this paper for different types of self-attention and
calculation types.

Our results demonstrate that there may be a fundamental “no free lunch”
phenomenon sitting here: it seems unlikely that we can get (provably) sub-
quadratic algorithms for self-attention that are also (provably) near-accurate
for all inputs.

Finally, while our primary contributions in this paper are mainly from the
perspective of lower bounds, we also provide some upper bounds. Specifically,
we show that a finite Taylor series approximation of the softmax function
lends itself to an approximate form of self-attention that can be computed in
linear time. However, a caveat of this result is that the running time now
scales exponentially in the order of the Taylor polynomial.

#### Techniques.

Our proofs are rather intuitive and are based on careful reductions from the
Strong Exponential Time Hypothesis (SETH). SETH-based lower bounds have
attracted recent (but growing) attention from the complexity theory community,
and has been used to prove hardness results for edit distance [15], Frechet
distance [16], dynamic programming [17], among many others [18]. For machine
learning problems, such lower bounds are less common; still, quadratic-time
barriers based on SETH have been proved for kernel PCA and backpropagation
through dense networks [19], as well as nearest neighbors [20]. Our results
can be viewed as an addition to this body of work.

A direct reduction from SETH is cumbersome. So instead, mirroring [15], we
derive reductions from the Orthogonal Vectors Problem (OVP), which is known to
require almost-quadratic time assuming SETH. As intermediate waypoints we
visit two adaptations of OVP: the Thresholded Vectors Product Problem (TVPP),
and the Bichromatic Hamming Close Pair (BHCP) problem. Reductions between
these problems require construction of several “vector gadgets", and form the
bulk of the technical difficulty of our proofs. Another subtlety lies in
identifying the correct temperature scaling in the softmax in order to achieve
the reductions. See Section 4 for details.

Table 1: Summary of our hardness results on self-attention | Calculation Type
---|---
Self-Attention | Exact |  | Element-wise
---
Multiplicative Approx.
Additive Approx.
Exponential Dot-Product | ✓ | ✓ | ✓
Softmax Dot-Product | ✓ | ✓ | ✗
Window Sliding | ✓ | ✓ | ✓
Exponential L2-Norm | ✓ | ✓ | ✗

##  2 Related work

Attention mechanisms and transformers. Ever since the seminal work of [1],
transformer architectures (with self-attention layers as their primary
building blocks) have become the cornerstone of state-of-the-art machine
learning models. Their use cases range from large language models such as BERT
[2] and GPT [21], to computer vision models [3], [22], [4], to multi-modal
vision-language models [7, 8], to even automated code-writing [6], among many,
many other examples. Therefore, a firm theoretical understanding about the
statistical and computational tradeoffs involved in transformer-based models
is of considerable interest. Transformers have already been shown to exhibit
the universal approximation property [23], but lose expressivity unless the
self-attention mechanism is accompanied with skip connections [24]. Self-
attention also exhibits undesirable Lipschitz continuity properties, but this
can be fixed by pursuing kernel-like alternatives [25].

Speeding up self-attention. Our focus in this paper is on the running time of
self-attention computation. It has been well-established that the (standard)
definition of self-attention takes in as input a length-$n$ sequence of tokens
of size $d$, and requires $O(dn^{2})$ time to compute the output. The
quadratic dependence on $n$ poses a challenge for very long input sequences,
both from the training and testing perspectives. Therefore, several sub-
quadratic methods for evaluating attention layers have been proposed.
Approaches (such as the Reformer [9], Big Bird [10], Linformer [26],
Longformer [27], or routing transformers [28]) use some combination of
hashing, sparsification, or low-rank approximation to speed up the computation
of the attention scores. Other approaches involve replacing the softmax-based
attention with kernel approximations; cf. the work of [12], or the
Nyströmformer [29]. More recent works such as the Performer [11], Slim [30],
or RFA [31] approximate the attention computation using random projections.
Methods such as SOFT [13] or the Skyformer [14] propose to replace softmax
operations with Gaussian kernels that can then be quickly evaluated. In an
orthogonal direction, [32] observes that attention patterns often repeat
across heads and layers, and propose reusing score computations during
inference.

We found that despite the large number (and diversity) of interesting
algorithmic ideas involved in the above efforts, the vast majority of these
works only focus on improvement in _running time_ ; but few (if any)
theoretically characterize the _error_ incurred by their proposed methods. Can
there ever be a method that is both fast (i.e., provably with sub-quadratic
running time) as well as near-accurate (i.e., with provably small additive or
multiplicative error)? Our results show that this is unlikely to be the case.

Fine-grained complexity. Classical complexity theory has primarily focused on
distinguishing between problems with efficient (polynomial-time) solutions
versus those who don’t. However, a different (and finer) picture has begun to
emerge over the last decade. In particular, the focus has shifted towards
precisely pinning down the _exponent_ , $c$, of a problem that can be solved
in polynomial time $\tilde{O}(n^{c})$. Many of these results are conditional,
and rely on reductions from popular (but plausible) conjectures such as the
Strong Exponential Time Hypothesis (SETH) [33], [34]. See the relevant surveys
[35], [36], and [18] for a more concrete overview of the field. In particular,
this approach has been shown to provide conditional lower bounds on well-known
problems such as edit distance [15], Frechet distance [16], dynamic time
warping [17], longest common subsequence (LCS) [37], Hausdorff distance [38],
and string matching [39]. In the context of machine learning and massive data
analysis, reductions from SETH have been fruitfully applied to problems such
as clustering [40], kernel PCA [19], and approximate nearest neighbors [20].

##  3 Notations and Preliminaries

An ordered finite set of $n$ vectors in $\mathbb{R}^{d}$ will be denoted as an
$n\times d$ matrix whose rows denote the elements of the set respectively. We
use upper case characters to denote both vector sets and matrices depending on
the context. We use $A_{i}$ to denote the $i^{th}$ row of matrix $A$, or the
$i^{th}$ element of ordered set $A$. We use $A_{ij}$ to denote the element at
the $i^{th}$ row and $j^{th}$ column of matrix $A$. For a positive integer
$n\in\mathbb{Z}^{+}$, $[n]$ denotes the set of all positive integers up to
$n$.

###  3.1 Background on Self-Attention

The well-established Transformer model [1] is based on the multi-head
attention mechanism, comprising several self-attention layers running in
parallel. The canonical choice of self-attention is the _softmax dot-product
self-attention_ , defined as follows. For a given set of inputs written as
$X\in\mathbb{R}^{n\times d}$ and trainable parameter matrices
$W_{q}\in\mathbb{R}^{d\times d_{q}},W_{k}\in\mathbb{R}^{d\times
d_{k}},W_{v}\in\mathbb{R}^{d\times d_{v}}$, this operation first calculates
the _query_ ($Q=XW_{q}$), _key_ ($K=XW_{k}$), and _value_ ($V=XW_{v}$)
matrices respectively. We assume that $d_{q}=d_{k}$. The size of $Q$ and $K$
is then $n\times d_{k}$, while the size of $V$ is $n\times d_{v}$. The softmax
dot-product self-attention operation is defined as:

$\textnormal{Attention}(Q,K,V)=\textnormal{softmax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)V.$
(1)

Let us consider the case where $n$ is very large compared to $d_{k},d_{v}$. By
very virtue of its definition, we might expect to incur $O(n^{2})$ time to
compute this self-attention operation: 1) calculation of
$S=QK^{T}/\sqrt{d_{k}}$ takes $O(n^{2}d_{k})$, 2) exponentiation and
calculation of row sum of $S$ takes $O(n^{2})$ time, 3) division of each
element of $S$ with the corresponding row sum takes $O(n^{2})$, and 4)
multiplication of $\textnormal{softmax}(QK^{T})$ and $V$ takes $O(n^{2}d_{v})$
time. Therefore, the computational complexity of this naive approach to
compute self-attention scales quadratically in $n$.

#### A generalized form of self-attention.

While Eq. 1 is the typical way to define self-attention, we also consider a
more general form. Let
$f:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a function that
takes two vectors in $\mathbb{R}^{d}$ as input. Then, the self-attention score
matrix $S$ is defined as $S_{ij}=f(Q_{i},K_{j})$ for all $i,j\in[n]$. Also,
let $h:\mathbb{R}^{n\times n}\rightarrow\mathbb{R}^{n\times n}$ be some kind
of normalization function. Then a more abstract definition of self-attention
can be expressed as:

$\textnormal{Attention}(Q,K,V)=h(S)\cdot V.$ (2)

In particular, for the softmax dot-product self-attention, the function $f$ is
the dot-product of given vectors with normalization factor $\sqrt{d_{k}}$, and
$h$ is the row-wise softmax function.

In this paper, we show that there is no (provably) better algorithm than the
naive $O(n^{2})$ approach for calculating softmax dot-product self-attention,
given hardness of SETH. We will also give similar lower bounds for various
approximate forms of self-attention. Finally, we will investigate the
computational complexity of generalized self-attention for more general forms
of $f$.

###  3.2 SETH and OVP

Despite a remarkable amount of algorithmic effort on Boolean satisfiability
(SAT) and related problems, to date no one has invented an algorithm with
faster-than-exponential ($O(2^{n})$) running time; indeed, there is no
polynomial-time algorithm for SAT unless $P=NP$. The Strong Exponential Time
Hypothesis (SETH) [33, 34] can be viewed as an strengthening of this
statement: for every $\epsilon$, there is no _sub-exponential_
($O(2^{n(1-\epsilon)})$) time algorithm that solves SAT.

As discussed above in Section 2, over the last decade SETH has been used to
provide fine-grained lower bounds for several polynomial-time problems. Many
of these results use reduction from an intermediate problem, given as follows.

######  Definition 1 (Orthogonal Vectors Problem (OVP)).

Two sets with cardinality $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ are given, where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are
binary vectors for all $i\in[n]$. The problem decides if there exists at least
one pair of vectors $a\in A$ and $b\in B$ such that $a^{T}b=0$.

Previous work has that for all $\epsilon>0$, there is no $O(n^{2-\epsilon})$
algorithm solves OVP for $d=\omega(\log n)$ unless SETH is false [41]. In
other words, for any $\epsilon>0$, problem needs at least $O(n^{2-\epsilon})$
time for $d=\omega(\log n)$. In this work, we will primarily give lower bounds
to the computational complexity of self-attention mechanism by showing
reductions from OVP.

##  4 Hardness of Computing Self-Attention

###  4.1 Adaptations of OVP

Based on the definition of generalized self-attention (Eq. 2), we focus on two
main forms of self-attention: (a) dot-product self-attention with
$f(x,y)=e^{Cx^{T}y}$, (b) $\ell_{2}$ self-attention (or RBF kernel self-
attention) with $f(x,y)=e^{-C.\left\lVert x-y\right\rVert_{2}^{2}}$ for some
temperature/scale parameter $C$ to be specified later, where $x,y$ are row
vectors from matrices $Q,K$ respectively. We provide hardness guarantees for a
variety of self-attention mechanisms built on top of these two types of self-
attention. We achieve this by deriving reductions from two fundamental
problems stated in Definitions 2 and 3.

######  Definition 2 (Threshold Vectors Product Problem (TVPP)).

Two sets with equal cardinality $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ are given, where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are
binary vectors for all $i\in[n]$. The problem decides if there exists at least
one pair $a\in A$ and $b\in B$ such that $a^{T}b\geq t$ for a given $t\in[n]$.

######  Definition 3 (Bichromatic Hamming Close Pair Problem (BHCP)).

Two sets with equal cardinality $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ are given, where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are
binary vectors for all $i\in[n]$. The problem decides if there exists at least
one pair of vectors $a\in A$ and $b\in B$ such that $\left\lVert
a-b\right\rVert_{2}<t$.

Both TVPP and BHCP can be shown to be SETH-hard by showing reductions from OVP
(Definition 1) as shown in Lemmas 1, 2, and 3. The hardness of BHCP is an
established result [19], but we provide an improved reduction from OVP to BHCP
via a new problem: Bichromatic Hamming Far Pair problem (BHFP). In contrast to
established reductions from OVP, we get rid of additional factors of $d$ (the
dimension of binary vectors) that incur during the process.

######  Definition 4 (Bichromatic Hamming Far Pair Problem (BHFP)).

Two sets with equivalent cardinality $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ are given, where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are
binary vectors for all $i\in[n]$. The problem decides if there exists at least
a pair of vectors $a\in A$ and $b\in B$ such that $\left\lVert
a-b\right\rVert_{2}\geq t$.

Before discussing the hardness of computing self-attention, we state the
hardness guarantees of TVPP, BHFP, and BHCP formally, with proofs deferred to
Appendix A.

######  Lemma 1.

Assume SETH. Then for any $\epsilon>0$, the computational complexity of TVPP
is $\Omega(n^{2-\epsilon})$ for $d=\omega(\log n)$.

######  Lemma 2.

Assume SETH. Then for any $\epsilon>0$, the computational complexity of BHFP
is $\Omega(n^{2-\epsilon})$ for $d=\omega(\log n)$.

######  Lemma 3.

Assume SETH. Then for any $\epsilon>0$, the computational complexity of BHCP
is $\Omega(n^{2-\epsilon})$ for $d=\omega(\log n)$.

Below, we show a series of reductions from TVPP and BHCP to several well-
studied self-attention mechanisms. We mainly modify the functions $f(.)$ and
$h(.)$ (see Eq. 2) to reflect each attention mechanism in our arguments. We
ignore the scaling factor $1/\sqrt{d_{k}}$ when computing the function $f(.)$
in dot-product self-attention for easier exposition as we only require to
scale every element of $Q$ or $K$ by $1/\sqrt{d_{k}}$ which takes $O(nd_{k})$
time. Also, we note that several approaches for efficient transformers were
developed with the particular case of $Q=K$ [9], and our hardness results are
valid for this specific instance where $Q=K$ and by direct reduction, and
hardness guarantees hold for any universal $(Q,K)$ as well. Also, all the
process is still valid for multi-head self attention which is proved in
Appendix F.

###  4.2 Vector Gadgets for Reductions

Our arguments follow by showing reductions from TVPP and BHCP instances to
self-attention instances. We define a set of vector gadgets that convert input
to TVPP and BHCP into inputs to self-attention functions in the following
manner.

#### TVPP vector gadgets.

Let $A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$ given in TVPP,
where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are binary vectors for all $i\in[n]$. We
construct our vector gadgets in the following way. First, create the matrix
$Q\in\mathbb{R}^{2n\times d}$ with its rows as $Q_{i}=a_{i}$ for all
$i\in[n]$, and $Q_{n+j}=Cb_{j}$ for all $j\in[n]$, where $C>0$ is a parameter
which we will define in the corresponding reductions. Then we create the
matrix $V\in\mathbb{R}^{2n\times 1}$ by setting first $n$ elements to $0$ and
the second $n$ elements to $1$.

#### BHCP vector gadgets.

Let $A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$ given in BHCP,
where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are binary vectors for all $i\in[n]$. We
construct our vector gadgets in the following way. First, create the matrix
$Q\in\mathbb{R}^{2n\times d}$ with its rows as $Q_{i}=a_{i}$ for all
$i\in[n]$, and $Q_{n+j}=b_{j}$ for all $j\in[n]$. Then we create the matrix
$V\in\mathbb{R}^{2n\times 1}$ by setting first $n$ elements to $0$ and the
second $n$ elements to $1$.

The entire construction process (including multiplying each $a_{i},b_{i}$ by
$C$) of vector gadgets takes $O(nd)$ time. We use the above gadgets in the
following reductions.

###  4.3 Hardness of Dot-Product Self-Attention

We begin with hardness results of dot-product self-attention (without softmax
normalization) as a warm-up. In Theorem 1 we show that exact self-attention,
as well as element-wise multiplicative- and additive-error approximations of
self-attention, all require quadratic time, conditioned on SETH.

######  Theorem 1.

Assume SETH. For any $i,j\in[n]$, let
$S_{ij}=f(Q_{i},Q_{j})=e^{Q_{i}^{T}Q_{j}}$ and for any matrix
$M\in\mathbb{R}^{n\times n}$, let $h(M)=M$. Let $Y=h(S)\cdot
V\in\mathbb{R}^{n\times d_{v}}$ be a self-attention mechanism. Provided
$d_{q}=\omega(\log n)$, for any $\epsilon>0$, computing a matrix
$\hat{Y}\in\mathbb{R}^{n\times d_{v}}$ that satisfies any of the following
conditions requires $\Omega(n^{2-\epsilon})$ time.

  1. 1.

$\hat{Y}=Y$ (exact computation).

  2. 2.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu|Y_{ij}|$ for all $i\in[n]$ and $j\in[d_{v}]$
where $0\leq\mu<1$ (multiplicative approximation).

  3. 3.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu$ for all $i\in[n]$ and $j\in[d_{v}]$ where
$0\leq\mu$ (additive approximation).

###### Proof.

Suppose that the matrices $Q$ and $V$ are constructed as TVPP vector gadgets
described above in Section 4.2. With this, we have $Y=h(S)\cdot
V\in\mathbb{R}^{n\times 1}$. Since $Y$ is a vector, we slightly abuse notation
and define $Y_{i}$ as the $i^{th}$ element of $Y$. Now consider the first $n$
elements of $Y$. Since $Y=SV$, we have that

$Y_{i}=\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}\text{ for any }i\in[n].$

Now we check the magnitude of $Y_{i},i\in[n]$ in order to distinguish between
true and false cases in TVPP. It takes $O(n)$ time to check each
$Y_{i},i\in[n]$. First we focus on the exact computation. Consider the
following two cases.

Case 1. There are no pairs $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is
for all $i,j\in[n]$, we have $a_{i}^{T}b_{j}\leq t-1$, and
$e^{Ca_{i}^{T}b_{j}}\leq e^{C(t-1)}$. Then for all $l\in[n]$, $Y_{l}\leq
ne^{C(t-1)}:=\delta$.

Case 2. There is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is for
some $i,j\in[n]$, we have $a_{i}^{T}b_{j}\geq t$, and $e^{Ca_{i}^{T}b_{j}}\geq
e^{Ct}$. Thus for some $l\in[n]$, we have $Y_{l}\geq e^{Ct}:=\Delta$

To distinguish between the two cases, it is sufficient to have
$\Delta>\delta$. But this holds when $C=2\log n$.

Now let us consider multiplicative approximation error. With a
$\mu$-multiplicative factor, if there are no pairs $a\in A$ and $b\in B$ with
$a^{T}b\geq t$, then we have for all
$l\in[n],\hat{Y}_{l}\leq(1+\mu)Y_{l}\leq(1+\mu)ne^{C(t-1)}:=\hat{\delta}$. On
the other hand, if there is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$,
then for some $l\in[n]$, we have
$\hat{Y}_{l}\geq(1-\mu)Y_{l}\geq(1-\mu)e^{Ct}:=\hat{\Delta}$. In order to
distinguish between two cases, it is sufficient to have
$\hat{\Delta}>\hat{\delta}$ and this inequality holds with
$C=2\log(\frac{1+\mu}{1-\mu}n)$.

Finally we look at additive approximation error. With a $\mu$-additive factor,
if there are no pairs $a\in A$ and $b\in B$ with $a^{T}b\geq t$, then we have
for all $l\in[n],\hat{Y}_{l}\leq Y_{l}+\mu\leq ne^{C(t-1)}+\mu:=\hat{\delta}$.
On the other hand, if there is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq
t$, then for some $l\in[n]$, we have $\hat{Y}_{l}\geq Y_{l}-\mu\geq
e^{Ct}-\mu:=\hat{\Delta}$. In order to distinguish between two cases, it is
sufficient to have $\hat{\Delta}>\hat{\delta}$ and this inequality holds with
$C=2\log(n+2\mu)$.

Thus, if there is an algorithm for computing self-attention up to an element-
wise multiplicative or additive error $\mu$ that runs in $O(n^{2-\epsilon})$
time, this entire process takes at most
$O(n+nd+n^{2-\epsilon})=O(n^{2-\epsilon})$ as long as $d=o(n^{1-\epsilon})$.
Therefore, this algorithm decides if there exists at least a pair of vectors
$a\in A$ and $b\in B$ such that $a^{T}b\geq t$ in $O(n^{2-\epsilon})$ time,
which contradicts the hardness result of TVPP (Lemma 1). This completes the
proof. ∎

The above proof is for computing the output of self-attention. As an easy
consequence, we can also show that computing the self-attention _score matrix_
, $S$, with either exact or element-wise multiplicative/additive error
requires quadratic time, conditioned on SETH. The argument follows a similar
proof as Theorem 1, and is given in Appendix C in detail.

###  4.4 Hardness of Softmax Dot-Product Self-Attention

Now we establish hardness guarantees for computing standard softmax dot-
product self-attention. The difference from vanilla self-attention is that the
function $h(.)$ now normalizes input rows. Discussion of additive
approximation for this part is given in Appendix G.

######  Theorem 2.

Assume SETH. For any $i,j\in[n]$, let
$S_{ij}=f(Q_{i},Q_{j})=e^{Q_{i}^{T}Q_{j}}$ and for any matrix
$M\in\mathbb{R}^{n\times n}$, let $h(M)\in\mathbb{R}^{n\times n}$ be the
matrix where for all $i,j\in[n]$,
$\\{h(M)\\}_{ij}=\frac{M_{ij}}{\sum_{k=1}^{n}M_{ik}}$. Let $Y=h(S)\cdot
V\in\mathbb{R}^{n\times d_{v}}$ be a self-attention. Then provided
$d_{q}=\omega(\log n)$, for any $\epsilon>0$, computing a matrix
$\hat{Y}\in\mathbb{R}^{n\times d_{v}}$ that satisfies any of the following
conditions requires $\Omega(n^{2-\epsilon})$ time.

  1. 1.

$\hat{Y}=Y$(exact).

  2. 2.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu|Y_{ij}|$ for all $i\in[n]$ and $j\in[d_{v}]$
where $0\leq\mu<1$ (multiplicative approximation).

###### Proof.

The proof is technically similar to the one above. Suppose that the matrices
$Q$ and $V$ are constructed according to TVPP vector gadgets described in
Section 4.2. With this we have $Y=h(S)\cdot V\in\mathbb{R}^{n\times 1}$.
Consider the first $n$ elements of $Y$. Since $h(.)$ act as the row-wise
softmax function, we have

$Y_{i}=\sum_{j=n+1}^{2n}S_{ij}=\sum_{j=1}^{n}\frac{e^{Ca_{i}^{T}b_{j}}}{\sum_{k=1}^{n}e^{a_{i}^{T}a_{k}}+\sum_{k=1}^{n}e^{Ca_{i}^{T}b_{k}}}=\frac{\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}}{\sum_{j=1}^{n}e^{a_{i}^{T}a_{j}}+\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}}.$

Again, first we focus on exact computation and consider two cases.

Case 1. There are no pairs $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is
for all $i,j\in[n]$, we have $a_{i}^{T}b_{j}\leq t-1$, and
$e^{Ca_{i}^{T}b_{j}}\leq e^{C(t-1)}$. For a function $\frac{x}{x+y}$, the
maximum value is achieved at maximum $x$ and minimum $y$ values. Thus, for all
$l\in[n]$,
$Y_{l}\leq\frac{ne^{C(t-1)}}{ne^{C(t-1)}+n}=\frac{e^{C(t-1)}}{e^{C(t-1)}+1}:=\delta$.

Case 2. There is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is for
some $i,j\in[n]$, we have $a_{i}^{T}b_{j}\geq t$. Then the row sum
corresponding to that $i,j$ pair is $\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}\geq
e^{Ct}+(n-1)e^{0}=e^{Ct}+(n-1)$. For a function $\frac{x}{x+y}$, the minimum
value is achieved at minimum $x$ and maximum $y$ values. Thus, for some
$l\in[n]$, we have $Y_{l}\geq\frac{e^{Ct}+(n-1)}{e^{Ct}+(n-1)+ne^{d}}:=\Delta$
and $e^{Ca_{i}^{T}b_{j}}\geq e^{Ct}$.

In order to distinguish between two cases, it is sufficient to have
$\Delta>\delta$ which means we require $[e^{Ct}+(n-1)]>ne^{d}[e^{C(t-1)]}$.
This holds with $C=\log n+d$.

Next, consider multiplicative error approximation. Select same TVPP vector
gadgets except this time the matrix $V\in\mathbb{R}^{2n\times 1}$ is set first
$n$ elements to $1$ and the second $n$ elements to $0$. Since
$|\hat{Y}_{l}-Y_{l}|\leq\mu|Y_{l}|$ for all $i\in[2n]$, we have
$(1-\mu)Y_{i}\leq\hat{Y}_{i}\leq(1+\mu)Y_{i}$. Now consider the values of
$\hat{Y}_{i},i\in[n]$ in the following two cases.

Case 1. There are no pairs $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is
for all $i,j\in[n]$, we have $a_{i}^{T}b_{j}\leq t-1$. This means that
$\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}\leq ne^{C(t-1)}$. For a function
$\frac{x}{x+y}$, the minimum value is achieved at the minimum $x$ and maximum
$y$ values. Thus, for all $l\in[n]$,
$Y_{l}\geq\frac{n}{n+ne^{C(t-1)}}=\frac{1}{e^{C(t-1)}+1}$ which means that for
all $l\in[n]$, we have
$\hat{Y_{l}}\geq(1-\mu)Y_{l}\geq(1-\mu)\frac{1}{e^{C(t-1)}+1}:=\Delta$.

Case 2. There is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is for
some $i,j\in[n]$, we have $a_{i}^{T}b_{j}\geq t$. Then the row sum
corresponding to that $i,j$ pair is $\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}\geq
e^{Ct}+(n-1)e^{0}=e^{Ct}+(n-1)$. For a function $\frac{x}{x+y}$, the maximum
is achieved at the maximum $x$ and minimum $y$ values. Thus, for some
$l\in[n]$, we have $Y_{l}\leq\frac{ne^{d}}{e^{Ct}+(n-1)+ne^{d}}$ which means
that for some $l\in[n]$, we have
$\hat{Y_{l}}\leq(1+\mu)Y_{l}\leq(1+\mu)\frac{ne^{d}}{e^{Ct}+(n-1)+ne^{d}}:=\delta.$

In order to distinguish between the two cases, it is sufficient to have
$\Delta>\delta$. This holds with $C=\log(\frac{2(1+\mu)}{1-\mu}n)+d$. Thus, if
there is an algorithm for computing self-attention up to an element-wise
multiplicative error $\mu$ that runs in $O(n^{2-\epsilon})$ time, this entire
process takes at most $O(n+nd+n^{2-\epsilon})=O(n^{2-\epsilon})$ as long as
$d=o(n^{1-\epsilon})$, and this algorithm decides if there exists a pair of
vectors $a\in A,b\in B$ such that $a^{T}b\geq t$ in $O(n^{2-\epsilon})$ time,
contradicting TVPP hardness. ∎

#### Remark.

For the multiplicative error approximations, we can set $\mu$ to a value
arbitrarily close to $1$ with a dependence on $n$, i.e.
$\mu=1-\Theta(1/n^{x})$ for a sufficiently large(constant) order $x$. For
example, with $x=2$, we require
$C>2\log(\frac{2-\Theta(1/n^{2})}{\Theta(1/n^{2})}n)\approx 2[\log
2+3\log(\Theta(n))]$. Therefore, to distinguish between two cases with a $\mu$
multiplicative error approximation with $\mu=1-\Theta(1/n^{2})$, we only
require $C=O(\log(n))$. We discuss this matter in more detail in the Appendix
H.

###  4.5 Hardness of Sliding Window Dot-Product Self-Attention

We now consider well-known less-expensive alternatives to standard self-
attention. A popular example is sliding window self-attention [27]. Here, we
evaluate an element of the score matrix $S_{ij}$ only if the difference
between $i$ and $j$ is within a fixed window size $w$; else we set it to zero.
This reduces the running time to $O(nw)$, which can be small if the window
size is small. However, we show that such a _rectangular_ complexity is
unavoidable.

######  Theorem 3.

Assume SETH. Let
$f:\\{\mathbb{R}^{d},\mathbb{R}^{d}\\}\longrightarrow\mathbb{R}$ as
$f(x,y)=e^{x^{T}y}$. For set $Q$ of vectors $Q_{1},\dots,Q_{n}$, we define the
matrix $S\in\mathbb{R}^{n\times n}$ as

$(S)_{ij}=\begin{cases}f(Q_{i},Q_{j})&|i-j|\leq w/2\\\
0&\text{otherwise}\end{cases}$

Also for any matrix $M\in\mathbb{R}^{n\times n}$, let $h(M)=M$. Let
$Y=h(S)\cdot V\in\mathbb{R}^{n\times d_{v}}$ be a self-attention. Then for any
$\epsilon>0$, computing a matrix $\hat{Y}\in\mathbb{R}^{n\times d_{v}}$ that
satisfies any of the following conditions requires $\Omega(nw^{1-\epsilon})$
time when $d_{q}=\omega(\log w)$ and $w=\omega(d_{q})$.

  1. 1.

$\hat{Y}=Y$(exact).

  2. 2.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu|Y_{ij}|$ for all $i\in[n]$ and $j\in[d_{v}]$
where $0\leq\mu<1$ (multiplicative approximation).

  3. 3.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu$ for all $i\in[n]$ and $j\in[d_{v}]$ where
$0\leq\mu$ (additive approximation).

###### Proof.

See Appendix B for a full proof. First, a TVPP problem with sets size
$k=\sqrt{nw}$ are constructed. Then sliding-window self attention is computed
for all the points in order, so that for each TVPP problem, all the pairs are
in the window. An appropriate value matrix $V$ is constructed for selection of
this pairs. If the overall self attention can be calculated in
$O((nw)^{1-\epsilon})$ time, then TVPP problem can be solved in
$O(k^{2-\epsilon})$ which contradicts Lemma 1. ∎

###  4.6 Hardness of $\ell_{2}\textnormal{-}$ Self-Attention

We now establish hardness guarantees for computing $\ell_{2}$-self-attention,
which replaces a softmax with an RBF kernel and is the core idea underlying
both SOFT [13] and Skyformer [14], the current state-of-the-art in fast self-
attention operations. In our argument, we adopt a similar proof technique
employed in [19], who establish quadratic hardness of kernel PCA assuming
SETH. However, our proof involves a different chain of reductions: OVP
$\rightarrow$ BHFP $\rightarrow$ BHCP $\rightarrow$ kernel computation.
Discussion of additivite approximation for this part is given in Appendix G.

######  Theorem 4.

Assume SETH. For any $i,j\in[n]$, let $S_{ij}=f(Q_{i},Q_{j})=e^{C.\left\lVert
Q_{i}-Q_{j}\right\rVert_{2}^{2}}$ where $C$ is a parameter and for any matrix
$M\in\mathbb{R}^{n\times n}$, let $h(M)=M$. Let
$Y=h(S).V\in\mathbb{R}^{n\times d_{v}}$ be a self-attention. Then for any
$\epsilon>0$, computing a matrix $\hat{Y}\in\mathbb{R}^{n\times d_{v}}$ that
satisfies any of the following conditions requires $\Omega(n^{2-\epsilon})$
time when $d_{q}=\omega(\log n)$.

  1. 1.

$\hat{Y}=Y$(exact).

  2. 2.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu|Y_{ij}|$ for all $i\in[n]$ and $j\in[d_{v}]$
where $0\leq\mu<1$ (multiplicative approximation).

###### Proof.

(Sketch). The $Q$ and $V$ matrices and constructed according to BHCP vector
gadgets described in Section 4.2. With these, we define $Y=h(S)\cdot
V\in\mathbb{R}^{n\times 1}$. Considering the first $n$ elements of $Y$ and a
suitable selection of $C$, our goal is to make the two cases (whether there is
a solution for BHCP or not) distinguishable. Thus, if there is an algorithm
for computing self-attention up to an element-wise multiplicative error $\mu$
that runs in $O(n^{2-\epsilon})$ time, this algorithm decides if there exists
a solution or not for BHCP in $O(n^{2-\epsilon})$ time, which contradicts BHCP
hardness (Lemma 3). ∎

##  5 Polynomial Approximations of Self-Attention

We have shown (conditional) hardness results for a number of well-known self-
attention mechanisms. We conclude with some upper bounds. Given the query $Q$,
key $K$, and value $V$ matrices, we show that when $f(Q_{i},K_{j})$ is a
polynomial of order $p$ ($p$ is an integer $\geq$ 0) of $Q_{i}^{T}K_{j}$ and
$h(.)$ is either the identity function or row-wise normalization, one can
compute self-attention in linear time. However, now the time complexity scales
exponentially with $p$. As a special case of this, we show that one can
approximate dot-product softmax self-attention in linear time in $n$ by using
finite Taylor series approximation:
$e^{x}\approx\sum_{k=0}^{p}\frac{x^{k}}{k!}.$ In what follows we use the fact
that $d_{q}=d_{k}$ and use $d_{q}$ in both places. Recall the dimensions of
matrices $Q\in\mathbb{R}^{n\times d_{q}},K\in\mathbb{R}^{n\times
d_{q}},V\in\mathbb{R}^{n\times d_{v}}$.

Lemma 4 shows that the product $SV$(without the row-wise normalization) can be
computed in linear time $n$. Lemma 5 shows that the denominator for row-wise
normalization can be computed in linear time in $n$. Once we have the
denominator for each row, $h(S)\cdot V$ can be computed by dividing each row
of $SV$ by the corresponding denominator.

######  Lemma 4.

Let $p$ be an integer $\geq 0$ and let $S_{ij}$ be
$C\cdot(Q_{i}^{T}K_{j})^{p}$ where $i,j\in[n]$ and $C$ is a constant. Then
$SV$ can be computed in $O(nd_{q}^{p}d_{v})$ time.

######  Lemma 5.

Let $p$ be an integer $\geq 0$. Then for all $i\in[n]$,
$\sum_{\hat{j}=1}^{n}C\cdot(Q_{i}^{T}K_{\hat{j}})^{p},\hat{j}\in[n]$ where $C$
is a constant can be computed in $O(nd_{q}^{p})$ time.

Proof sketch of Lemma 4 and 5. When $f(Q_{i},V_{j})=Q_{i}^{T}V_{j}$, we
directly multiply matrices $K^{T}$ and $V$ to obtain $K^{T}V$ in
$O(d_{q}nd_{v})$ time, then $Q$ and $K^{T}V$ in $O(nd_{q}d_{v})$ gives the
desired matrix $SV$ in $O(n)$ time. The sum of a row of $S$ can be simply
computed by storing the sum of vectors $K_{j},j\in[n]$ in memory in
$O(nd_{q})$ time and reusing this for each row $i$ to compute
$\sum_{j=1}^{n}Q_{i}^{T}K_{j}=Q_{i}^{T}\sum_{j=1}^{n}K_{j}$ in $O(nd_{q})$
time. This idea can be extended to $(Q_{i}^{T}K_{j})^{p}$. ∎

######  Theorem 5.

Let $p$ be an integer $\geq 0$. If $S_{ij}=f(Q_{i},K_{j})$ is a polynomial
function of order $p$ of $Q_{i}^{T}K_{j}$ and $h(.)$ performs row-wise
normalization, then $h(S)\cdot V$ can be computed in $O(nd_{q}^{p}d_{v})$
time.

###### Proof.

The result is implied by Lemma 4 and Lemma 5. Let
$x_{ij}=Q_{i}^{T}K_{j};i,j\in[n]$. Define the polynomial function of order $p$
as $\sum_{z=0}^{p}c_{z}x_{ij}^{z}$ where $c_{z},z\in\\{0,\dots,p\\}$ are
constants. Let $S^{(1)},\dots,S^{(p)}\in\mathbb{R}^{n\times n}$ where
$S_{ij}^{(z)}=c_{z}x_{ij}^{z}$. Now we can write
$S_{ij}=\sum_{z=0}^{p}S_{ij}^{(z)}$, thus $SV=\sum_{z=0}^{p}S_{ij}^{(z)}V$. By
Lemma 4, each term of this summation can be computed in $O(nd_{q}^{z}d_{v})$
time. Therefore the overall time complexity of computing $SV$ is
$O(nd_{q}^{p}d_{v})$ (considering the largest exponent of $d_{q}$ is when
$z=p$).

Let $s_{i}$ be the sum of the elements of $i^{th}$ row of $S$. What remains is
computing $h(S).V$. This can be computed indirectly by first computing $SV$
and the dividing each row $i$ of $SV$ by $s_{i}$. If we have precomputed each
$s_{i},i\in[n]$, then this process takes $O(nd_{v})$ time, since we are
dividing each element of $SV(\in\mathbb{R}^{n\times d_{v}})$ by a scaler. What
remains to show is that computing $s_{i},\forall i\in[n]$ takes
$O(npd_{q}^{p})$ time. Observe that

$s_{i}=\sum_{\hat{j}=1}^{n}S_{ij}=\sum_{\hat{j}=1}^{n}\sum_{z=0}^{p}S_{i\hat{j}}^{(z)}=\sum_{z=0}^{p}\sum_{\hat{j}=1}^{n}S_{i\hat{j}}^{(z)}=\sum_{z=0}^{p}\sum_{\hat{j}=1}^{n}c_{z}x_{i\hat{j}}^{z}$

From Lemma 5, each term of the outer summation over $z$ can be computed
$O(nd_{q}^{z})$ time for all $i\in[n]$ and overall time complexity is
$O(nd_{q}^{p})$(taking the largest exponent of $d_{q}$ similarly). ∎

######  Corollary 1.

Let $p$ be an non-negative integer. The $p^{th}$ order polynomial
approximation of dot-product softmax self-attention using matrices $Q,K,V$
with finite Taylor series can be computed in $O(nd_{q}^{p}d_{v})$ time.

###### Proof.

The result follows from replacing constants $c_{z}=\frac{1}{z!}$ for
$z=0,\dots,p$ in Theorem 5. ∎

##  6 Conclusions

In this paper we investigate fundamental bounds on the computational
complexity of self-attention. We examine numerous state-of-the-art self-
attention mechanisms, and prove quadratic (or rectangular) lower bounds
assuming the Strong Exponential Time Hypothesis (SETH). Even though a large
number of recent works have proposed fast approximations to self-attention,
our results imply that it may be difficult to both overcome the quadratic
runtime barrier while still retaining high accuracy. On the positive side, we
show that linear-time computation is possible if we choose the score
computation function in the form of a polynomial.

Our work leaves open several directions. At a high level our theorems
establish a result between ‘exponential’ and ‘polynomial’ forms of self-
attention, but having a clearer picture of the landscape may be helpful.
Moreover, our results are for worst-case inputs; similar hardness results on
average-case inputs is an interesting direction. Finally, we leave the door
open for the possibility of randomized algorithms that achieve sub-quadratic
complexity and are correct with high probability.

## References

  * [1] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [2] J. D. M.-W. C. Kenton and L. K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of NAACL-HLT_ , 2019, pp. 4171–4186.
  * [3] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” in _International Conference on Learning Representations_ , 2021\.
  * [4] S. Khan, M. Naseer, M. Hayat, S. W. Zamir, F. S. Khan, and M. Shah, “Transformers in vision: A survey,” _ACM Computing Surveys (CSUR)_ , 2021\.
  * [5] J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Žídek, A. Potapenko _et al._ , “Highly accurate protein structure prediction with alphafold,” _Nature_ , vol. 596, no. 7873, pp. 583–589, 2021.
  * [6] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. de Oliveira Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman _et al._ , “Evaluating large language models trained on code,” _CoRR_ , 2021.
  * [7] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark _et al._ , “Learning transferable visual models from natural language supervision,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 8748–8763.
  * [8] J.-B. Alayrac, J. Donahue, P. Luc, A. Miech, I. Barr, Y. Hasson, K. Lenc, A. Mensch, K. Millican, M. Reynolds _et al._ , “Flamingo: a visual language model for few-shot learning,” _arXiv preprint arXiv:2204.14198_ , 2022.
  * [9] N. Kitaev, L. Kaiser, and A. Levskaya, “Reformer: The efficient transformer,” in _International Conference on Learning Representations_ , 2020.
  * [10] M. Zaheer, G. Guruganesh, K. A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula, Q. Wang, L. Yang _et al._ , “Big bird: Transformers for longer sequences,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 17 283–17 297, 2020.
  * [11] K. M. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Q. Davis, A. Mohiuddin, L. Kaiser _et al._ , “Rethinking attention with performers,” in _International Conference on Learning Representations_ , 2021.
  * [12] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret, “Transformers are rnns: Fast autoregressive transformers with linear attention,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 5156–5165.
  * [13] J. Lu, J. Yao, J. Zhang, X. Zhu, H. Xu, W. Gao, C. XU, T. Xiang, and L. Zhang, “Soft: Softmax-free transformer with linear complexity,” in _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 21 297–21 309.
  * [14] Y. Chen, Q. Zeng, H. Ji, and Y. Yang, “Skyformer: Remodel self-attention with gaussian kernel and nystr$\backslash$" om method,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [15] A. Backurs and P. Indyk, “Edit distance cannot be computed in strongly subquadratic time (unless seth is false),” in _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , 2015, pp. 51–58.
  * [16] K. Bringmann, “Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails,” in _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_. IEEE, 2014, pp. 661–670.
  * [17] K. Bringmann and M. Künnemann, “Quadratic conditional lower bounds for string problems and dynamic time warping,” in _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_. IEEE, 2015, pp. 79–97.
  * [18] K. Bringmann, “Fine-grained complexity theory: Conditional lower bounds for computational geometry,” in _Conference on Computability in Europe_. Springer, 2021, pp. 60–70.
  * [19] A. Backurs, P. Indyk, and L. Schmidt, “On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [20] A. Rubinstein, “Hardness of approximate nearest neighbor search,” in _Proceedings of the 50th annual ACM SIGACT symposium on theory of computing_ , 2018, pp. 1260–1268.
  * [21] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” _Advances in neural information processing systems_ , vol. 33, pp. 1877–1901, 2020.
  * [22] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, “Swin transformer: Hierarchical vision transformer using shifted windows,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 10 012–10 022.
  * [23] C. Yun, S. Bhojanapalli, A. S. Rawat, S. Reddi, and S. Kumar, “Are transformers universal approximators of sequence-to-sequence functions?” in _International Conference on Learning Representations_ , 2019.
  * [24] Y. Dong, J.-B. Cordonnier, and A. Loukas, “Attention is not all you need: Pure attention loses rank doubly exponentially with depth,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 2793–2803.
  * [25] H. Kim, G. Papamakarios, and A. Mnih, “The lipschitz constant of self-attention,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 5562–5571.
  * [26] S. Wang, B. Z. Li, M. Khabsa, H. Fang, and H. Ma, “Linformer: Self-attention with linear complexity,” _arXiv preprint arXiv:2006.04768_ , 2020.
  * [27] I. Beltagy, M. E. Peters, and A. Cohan, “Longformer: The long-document transformer,” _CoRR_ , vol. abs/2004.05150, 2020.
  * [28] A. Roy, M. Saffar, A. Vaswani, and D. Grangier, “Efficient content-based sparse attention with routing transformers,” _Transactions of the Association for Computational Linguistics_ , vol. 9, pp. 53–68, 2021.
  * [29] Y. Xiong, Z. Zeng, R. Chakraborty, M. Tan, G. Fung, Y. Li, and V. Singh, “Nyströmformer: A nyström-based algorithm for approximating self-attention,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 16, 2021, pp. 14 138–14 148.
  * [30] V. Likhosherstov, K. M. Choromanski, J. Q. Davis, X. Song, and A. Weller, “Sub-linear memory: How to make performers slim,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [31] H. Peng, N. Pappas, D. Yogatama, R. Schwartz, N. Smith, and L. Kong, “Random feature attention,” in _International Conference on Learning Representations_ , 2021.
  * [32] S. Bhojanapalli, A. Chakrabarti, A. Veit, M. Lukasik, H. Jain, F. Liu, Y.-W. Chang, and S. Kumar, “Leveraging redundancy in attention with reuse transformers,” _arXiv preprint arXiv:2110.06821_ , 2021.
  * [33] R. Impagliazzo and R. Paturi, “On the complexity of k-sat,” _Journal of Computer and System Sciences_ , vol. 62, no. 2, pp. 367–375, 2001.
  * [34] R. Impagliazzo, R. Paturi, and F. Zane, “Which problems have strongly exponential complexity?” _Journal of Computer and System Sciences_ , vol. 63, no. 4, p. 512–530, 2001.
  * [35] P. Indyk, “Beyond p vs. np: quadratic-time hardness for big data problems,” in _Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures_ , 2017, pp. 1–1.
  * [36] A. Rubinstein and V. V. Williams, “Seth vs approximation,” _ACM SIGACT News_ , vol. 50, no. 4, pp. 57–76, 2019.
  * [37] A. Abboud, A. Backurs, and V. V. Williams, “Tight hardness results for lcs and other sequence similarity measures,” in _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_. IEEE, 2015, pp. 59–78.
  * [38] K. Bringmann and A. Nusser, “Translating hausdorff is hard: Fine-grained lower bounds for hausdorff distance under translation,” in _37th International Symposium on Computational Geometry_ , 2021.
  * [39] A. Abboud, A. Backurs, and V. V. Williams, “If the current clique algorithms are optimal, so is valiant’s parser,” _SIAM Journal on Computing_ , vol. 47, no. 6, pp. 2527–2555, 2018.
  * [40] A. Abboud, V. Cohen-Addad, and H. Houdrougé, “Subquadratic high-dimensional hierarchical clustering,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [41] R. Williams, “A new algorithm for optimal 2-constraint satisfaction and its implications,” _Theoretical Computer Science_ , vol. 348, no. 2, pp. 357–365, 2005.

## Appendix

##  Appendix A Proofs for Hardness of TVPP, BHCP and BHFP

#### Lemma 1.

Assume SETH. Then for any $\epsilon>0$, the computational complexity of TVPP
is $\Omega(n^{2-\epsilon})$ for $d=\omega(\log n)$.

###### Proof.

Consider the two sets $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ given in OVP, where $a_{i},b_{i}\in\\{0,1\\}^{d}$
are binary vectors for all $i\in[n]$. For any vector $a_{i}\in A$, let us
define $\bar{a_{i}}\in\mathbb{R}^{2d}$ as the concatenation of vector $a_{i}$
and vector $(\vec{1}-a_{i})$, where $\vec{1}:=(1,1,\dots,1)\in\mathbb{R}^{d}$.
Then we have $\|\bar{a_{i}}\|_{1}=\|{a_{i}}\|_{1}+\|\vec{1}-{a_{i}}\|_{1}=d$.
Now define $\bar{A}$ as the set of $\bar{a_{i}}$s. For any vector $b_{j}\in
B$, let us define $\bar{b_{j}}\in\mathbb{R}^{2d}$ as the concatenation of
vector $(\vec{1}-b_{j})$ and vector $\vec{1}$. Now define $\bar{B}$ as the set
of $\bar{b_{j}}$. Because the overall dimensions of $A,B$ and
$\bar{A},\bar{B}$ are $nd$ and $2nd$ respectively, this process takes $O(nd)$
time. Now for any $i,j\in[n]$ we have

$\bar{a_{i}}^{T}\bar{b_{j}}={a_{i}}^{T}(\vec{1}-b_{j})+(\vec{1}-{a_{i}})^{T}\vec{1}=\|a_{i}\|_{1}-a_{i}^{T}b_{j}+\|\vec{1}-{a_{i}}\|_{1}=d-a_{i}^{T}b_{j}.$

$\bar{a_{i}}^{T}\bar{b_{j}}=d$ if and only if ${a_{i}}^{T}b_{j}=0$. Now if we
run the algorithm for TVPP with the threshold $t=d$ on the sets $\bar{A}$ and
$\bar{B}$ to find a pair $\bar{a}\in\bar{A}$ and $\bar{b}\in\bar{B}$ that
satisfies $\bar{a}^{T}\bar{b}\geq d$, then we can conclude that there is a
pair $a\in A$ and $b\in B$ that satisfies $a^{T}{b}=0$.

Thus, if there is an algorithm for TVPP that runs in $O(n^{2-\epsilon})$ time,
this entire process takes at most $O(nd+n^{2-\epsilon})=O(n^{2-\epsilon})$ as
long as $d=o(n^{1-\epsilon})$, and this algorithm decides if there exists at
least a pair of vectors $a\in A$ and $b\in B$ such that $a^{T}b=0$ in
$O(n^{2-\epsilon})$ time, which contradicts the hardness result of OVP. As a
result, for at least one $t$, TVPP problem cannot be solved in
$O(n^{2-\epsilon})$ time. (We note that for $t=1$, this problem have a linear
time algorithm. Selecting rows of matrix $Q$ as elements of set $A$, rows of
matrix $K$ as elements of set $B$, and rows of matrix $V$ as 1, then
calculating $Y=QK^{T}V$ takes linear time on $n$, by firstly calculating
$K^{T}V$, then calculating $Q(K^{T}V)$. If there is any positive value of $Y$,
then we can conclude that there is a pair $a\in A$ and $b\in B$ that satisfies
$a^{T}{b}\geq 1$.)

∎

#### Lemma 2.

Assume SETH. Then for any $\epsilon>0$, the computational complexity of BHFP
is $\Omega(n^{2-\epsilon})$ for $d=\omega(\log n)$.

###### Proof.

Consider the two sets $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ given in OVP, where $a_{i},b_{i}\in\\{0,1\\}^{d}$
are binary vectors for all $i\in[n]$.

For any vector $a_{i}\in A$, let us define $\bar{a_{i}}\in\mathbb{R}^{3d}$ as
the concatenation of vector $a_{i}$, vector $(\vec{1}-a_{i})$ and vector
$\vec{0}$ where $\vec{1}:=(1,1,\dots,1)\in\mathbb{R}^{d}$ and
$\vec{0}:=(0,0,\dots,0)\in\mathbb{R}^{d}$. Then we have
$\bar{a_{i}}^{T}\bar{a_{i}}={a_{i}}^{T}a_{i}+(\vec{1}-{a_{i}})^{T}(\vec{1}-{a_{i}})=d$.
Now define $\bar{A}$ as the set of $\bar{a_{i}}$s. For any vector $b_{j}\in
B$, let us define $\bar{b_{j}}\in\mathbb{R}^{3d}$ as the concatenation of
vector $b_{j}$, vector $\vec{0}$, and vector $(\vec{1}-b_{j})$. Then we have
$\bar{b_{j}}^{T}\bar{b_{j}}={b_{j}}^{T}b_{j}+(\vec{1}-{b_{j}})^{T}(\vec{1}-{b_{j}})=d$.
Now define $\bar{B}$ as the set of $\bar{b_{j}}$. Because the overall
dimensions of $A,B$ and $\bar{A},\bar{B}$ are $nd$ and $3nd$ respectively,
this process takes $O(nd)$ time. Now for any $i,j\in[n]$ we have

$\bar{a_{i}}^{T}\bar{b_{j}}={a_{i}}^{T}{b_{j}}+(\vec{1}-{a_{i}})^{T}\vec{0}+\vec{0}^{T}(\vec{1}-b_{j})={a_{i}}^{T}b_{j}.$

The squared $\ell_{2}$ distance between $\bar{a_{i}}$ and $\bar{b_{j}}$ for
any $i,j\in[n]$ is

$\|\bar{a_{i}}-\bar{b_{j}}\|_{2}^{2}=(\bar{a_{i}}-\bar{b_{j}})^{T}(\bar{a_{i}}-\bar{b_{j}})=\bar{a_{i}}^{T}\bar{a_{i}}+\bar{b_{j}}^{T}\bar{b_{j}}-2\bar{a_{i}}^{T}\bar{b_{j}}=d+d-2\bar{a_{i}}^{T}\bar{b_{j}}=2d-2{a_{i}}^{T}b_{j}.$

$\|\bar{a_{i}}-\bar{b_{j}}\|_{2}^{2}=2d$ if and only if ${a_{i}}^{T}b_{j}=0$.
Now if we run the algorithm for BHFP with the threshold $t=\sqrt{2d}$ on the
sets $\bar{A}$ and $\bar{B}$ to find a pair $\bar{a}\in\bar{A}$ and
$\bar{b}\in\bar{B}$ that satisfy $\|\bar{a}-\bar{b}\|_{2}\geq\sqrt{2d}$, then
we can conclude that there is a pair $a\in A$ and $b\in B$ that satisfies
$a^{T}{b}=0$.

Thus, if there is an algorithm for BHFP that runs in $O(n^{2-\epsilon})$ time,
this entire process takes at most $O(nd+n^{2-\epsilon})=O(n^{2-\epsilon})$ as
long as $d=o(n^{1-\epsilon})$, and this algorithm decides if there exists at
least a pair of vectors $a\in A$ and $b\in B$ such that $a^{T}b=0$ in
$O(n^{2-\epsilon})$ time, which contradicts the hardness result of OVP. As a
result, for at least one $t$, BHFP problem cannot be solved in
$O(n^{2-\epsilon})$ time.

∎

#### Lemma 3.

Assume SETH. Then for any $\epsilon>0$, the computational complexity of BHCP
is $\Omega(n^{2-\epsilon})$ for $d=\omega(\log n)$.

###### Proof.

Consider the two sets $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ given in BHFP, where $a_{i},b_{i}\in\\{0,1\\}^{d}$
are binary vectors for all $i\in[n]$. Let $t,t^{\prime}$ be the given
threshold for BHFP and BHCP respectively.

For any vector $b_{j}\in B$, let us define $\bar{b_{j}}\in\mathbb{R}^{d}$ as
$(\vec{1}-b_{j})$, where $\vec{1}:=(1,1,\dots,1)\in\mathbb{R}^{d}$. Now define
$\bar{B}$ as the set of $\bar{b_{j}}$. Because the overall dimension of $B$
and $\bar{B}$ is $nd$, this process takes $O(nd)$ time. The squared $\ell_{2}$
distance between ${a_{i}}$ and $\bar{b_{j}}$ for any $i,j\in[n]$ is

$\|{a_{i}}-\bar{b_{j}}\|_{2}^{2}=\|{a_{i}}-(\vec{1}-b_{j})\|_{2}^{2}=d-\|{a_{i}}-{b_{j}}\|_{2}^{2}.$

$\|a_{i}-\bar{b_{j}}\|_{2}^{2}<d-t^{2}+1$ if and only if
$\|{a_{i}}-{b_{j}}\|_{2}\geq t$. Now if we run the algorithm for BHCP with the
threshold $t^{\prime}=\sqrt{d-t^{2}+1}$ on the sets ${A}$ and $\bar{B}$ to
find a pair ${a}\in\bar{A}$ and $\bar{b}\in\bar{B}$ that satisfy
$\|{a}-\bar{b}\|_{2}<\sqrt{d-t^{2}+1}$, then we can conclude that there is a
pair $a\in A$ and $b\in B$ that satisfies $\left\lVert a-b\right\rVert_{2}\geq
t$.

Thus, if there is an algorithm for BHCP that runs in $O(n^{2-\epsilon})$ time,
this entire process takes at most $O(nd+n^{2-\epsilon})=O(n^{2-\epsilon})$ as
long as $d=o(n^{1-\epsilon})$, and this algorithm decides if there exists at
least a pair of vectors $a\in A$ and $b\in B$ such that $\left\lVert
a-b\right\rVert_{2}\geq t$ in $O(n^{2-\epsilon})$ time, which contradicts the
hardness result of BHFP. As a result, for at least one $t^{\prime}$, BHCP
problem cannot be solved in $O(n^{2-\epsilon})$ time. ∎

##  Appendix B Proof for Hardness of Sliding Window Dot-Product Self-Attention

#### Theorem 3.

Assume SETH. Let
$f:\\{\mathbb{R}^{d},\mathbb{R}^{d}\\}\longrightarrow\mathbb{R}$ as
$f(x,y)=e^{x^{T}y}$. For set $Q$ of vectors $Q_{1},\dots,Q_{n}$, we define the
matrix $S\in\mathbb{R}^{n\times n}$ as

$(S)_{ij}=\begin{cases}f(Q_{i},Q_{j})&|i-j|\leq w/2\\\
0&\text{otherwise}\end{cases}$

Also for any matrix $M\in\mathbb{R}^{n\times n}$, let $h(M)=M$. Let
$Y=h(S)\cdot V\in\mathbb{R}^{n\times d_{v}}$ be a self-attention. Then for any
$\epsilon>0$, computing a matrix $\hat{Y}\in\mathbb{R}^{n\times d_{v}}$ that
satisfies any of the following conditions requires $\Omega((nw)^{1-\epsilon})$
time when $d_{q}=\omega(\log\sqrt{nw})$ and $w=\omega(d_{q})$.

  1. 1.

$\hat{Y}=Y$(exact).

  2. 2.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu|Y_{ij}|$ for all $i\in[n]$ and $j\in[d_{v}]$
where $0\leq\mu<1$(multiplicative approximation).

  3. 3.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu$ for all $i\in[n]$ and $j\in[d_{v}]$ where
$0\leq\mu$(additive approximation).

###### Proof.

Consider the two sets $A=\\{a_{1},\dots,a_{k}\\}$ and
$B=\\{b_{1},\dots,b_{k}\\}$ given in TVPP, where $k=\sqrt{nw}$ and
$a_{i},b_{i}\in\\{0,1\\}^{d}$ are binary vectors for all $i\in[k]$. The
problem is to decide if there exists at least a pair $a\in A$ and $b\in B$
that satisfies $a^{T}b\geq t$ for a given $t\in[d]$.

We construct our matrices $Q$ and $V$ in the following way. Firstly, define
the function $(\alpha\pmod{k}):=m$ if $\alpha\equiv m\pmod{k}$ and $m\in[k]$.
Create the matrix $Q\in\mathbb{R}^{3n\times d}$ with its rows with even
indices as $Q_{2\alpha}=Cb_{(\alpha\pmod{k})}$, and its rows with odd indices
as $Q_{2\alpha-1}=a_{(\alpha\pmod{k})+w\lfloor\frac{2\alpha-1}{2k}\rfloor}$.
Thus, this process takes $O(nd)$ time. By this construction, each
$(a_{i},b_{j})$ pair is found at a distance $w$.

Also, select V as concatenation of vector $(1,0,\dots,1,0)\in\mathbb{R}^{3n}$.

With this we have $Y=h(S)\cdot V\in\mathbb{R}^{3n\times 1}$. Since $Y$ is a
vector, we abuse the notation again and define $Y_{i}$ as the $i^{th}$ element
of $Y$.

Now consider the first $n$ even rows of $Y$. Because odd rows of matrix $Q$ is
from set $A$, and even rows of matrix $Q$ is from set $B$, the even rows of
$Y$ becomes the summation of the exponential of the $C$ times of the dot
products of $w$ different $(a_{i},b_{j})$ pairs by the definition of vector
$V$.

Also, each $(a_{i},b_{j})$ pair is found at a distance $w$, so that the
exponential of the $C$ times dot products of all pairs appear in the sliding
window attention score matrix and contributes $Y_{2l}$ for at least an
$l\in[n]$ value.

Now we check the magnitudes of $Y_{2l}$ for $l\in[n]$ in order to distinguish
between true and false cases in TVPP. It takes $O(n)$ time to check these $n$
values. First, we focus on the exact computation. Consider the following two
cases.

Case 1. There are no pairs $a\in A$ and $b\in B$ with $(a)^{T}b\geq t$, that
is for all $i,j\in[k]$, we have $(a_{i})^{T}b_{j}\leq t-1$, and
$e^{C(a_{i})^{T}b_{j}}\leq e^{C(t-1)}$. Then for all $l\in[n]$, we have
$Y_{2l}\leq we^{C(t-1)}:=\delta$.

Case 2. There is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is for
some $i,j\in[k]$, we have $(a_{i})^{T}b_{j}\geq t$, and
$e^{C(a_{i})^{T}b_{j}}\geq e^{Ct}$. Because any pair appears in some element
of $Y$, we have $Y_{2l}\geq e^{Ct}:=\Delta$ for some odd $l\in[n]$.

In order to distinguish between two cases, it is sufficient to have
$\Delta>\delta$. This holds with $C=2\log w$.

Now let us consider multiplicative approximation error. With a
$\mu$-multiplicative factor, if there are no pairs $a\in A$ and $b\in B$ with
$a^{T}b\geq t$, then we have for all
$l\in[n],\hat{Y}_{2l}\leq(1+\mu)Y_{2l}\leq(1+\mu)we^{C(t-1)}:=\hat{\delta}$.
On the other hand, if there is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq
t$, then for some $l\in[n]$, we have
$\hat{Y}_{2l}\geq(1-\mu)Y_{2l}\geq(1-\mu)e^{Ct}:=\hat{\Delta}$. In order to
distinguish between two cases, it is sufficient to have
$\hat{\Delta}>\hat{\delta}$ and this inequality holds with
$C=2\log(\frac{1+\mu}{1-\mu}w)$.

Finally we look at additive approximation error. With a $\mu$-additive factor,
if there are no pairs $a\in A$ and $b\in B$ with $a^{T}b\geq t$, then we have
for all $l\in[n],\hat{Y}_{2l}\leq Y_{2l}+\mu\leq
we^{C(t-1)}+\mu:=\hat{\delta}$. On the other hand, if there is a pair $a\in A$
and $b\in B$ with $a^{T}b\geq t$, then for some $l\in[n]$, we have
$\hat{Y}_{2l}\geq Y_{2l}-\mu\geq e^{Ct}-\mu:=\hat{\Delta}$. In order to
distinguish between two cases, it is sufficient to have
$\hat{\Delta}>\hat{\delta}$ and this inequality holds with $C=2\log(w+2\mu)$.

Thus, if there is an algorithm for computing self-attention up to an element-
wise multiplicative or additive error $\mu$ that runs in $O(k^{2-\epsilon})$
time, this entire process takes at most
$O(nd+k^{2-\epsilon})=O(\sqrt{nw}^{2-\epsilon})=O({(nw)}^{1-\epsilon})$ as
long as $d=o(w^{1-\epsilon})$. Therefore, this algorithm decides if there
exists at least a pair of vectors $a\in A$ and $b\in B$ such that $a^{T}b\geq
t$ in $O((nw)^{1-\epsilon})$ time, which contradicts the hardness result of
TVPP (Lemma 1). This completes the proof.

∎

A similar proof also applies for dilated sliding window [27], where the self-
attention score is calculated as Theorem 3. Also, when the self-attention
score is the softmax dot product (where softmax is only applied to the window
size in each row), one can prove $O(nw^{1-\epsilon})$ complexity by following
the proof of Theorem 2.

##  Appendix C Proofs for Hardness of Self-Attention Matrix $S$ Approximation

######  Theorem 6.

Assume SETH. For any $i,j\in[n]$, let
$S_{ij}=f(Q_{i},Q_{j})=e^{Q_{i}^{T}Q_{j}}$ and for any matrix
$M\in\mathbb{R}^{n\times n}$, let $h(M)=M$. $\hat{S}\in\mathbb{R}^{n\times n}$
satisfies any of the following conditions:

  1. 1.

$|\hat{S}_{ij}-S_{ij}|\leq\mu|S_{ij}|$ for all $i\in[n]$ and $j\in[d_{v}]$
where $0\leq\mu<1$(multiplicative approximation).

  2. 2.

$|\hat{S}_{ij}-S_{ij}|\leq\mu$ for all $i,j\in[n]$, where $0\leq\mu$(additive
approximation).

Let $Y=h(\hat{S}).V\in\mathbb{R}^{n\times d_{v}}$ be a self-attention. Then
for any $\epsilon>0$, computing self-attention ${Y}\in\mathbb{R}^{n\times
d_{v}}$ requires $\Omega(n^{2-\epsilon})$ time when $d_{q}=\omega(\log n)$.

###### Proof.

Consider two sets $A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$
given in TVPP, where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are binary vectors for all
$i\in[n]$. The problem is to decide if there exists at least a pair $a\in A$
and $b\in B$ that satisfies $a^{T}b\geq t$ for a given $t\in[n]$.

Suppose that the matrices $Q$ and $V$ are constructed according to TVPP vector
gadgets described in the section 4.2. With this we have
$Y=h(\hat{S}).V\in\mathbb{R}^{n\times 1}$. Since $Y$ is a vector, we abuse the
notation again and define $Y_{i}$ as the $i^{th}$ element of $Y$. Now consider
the first $n$ elements of $Y$. Since $Y=SV$, we have that

$Y_{i}=\sum_{j=1}^{n}\hat{S}_{ij}\text{ for any }i\in[n].$

Now we check the magnitude of $Y_{i},i\in[n]$ in order to distinguish between
true and false cases in TVPP. It takes $O(n)$ time to check each
$Y_{i},i\in[n]$. First we focus on the multiplicative error approximation.
Consider the following two cases.

Case 1. There are no pairs $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is
for all $i,j\in[n]$, we have $a_{i}^{T}b_{j}\leq t-1$, and
$S_{ij}=e^{Ca_{i}^{T}b_{j}}\leq e^{C(t-1)}$, so
$\hat{S}_{ij}\leq(1+\mu)S_{ij}=(1+\mu)e^{Ca_{i}^{T}b_{j}}\leq(1+\mu)e^{C(t-1)}$.
Then for all $l\in[n]$, $Y_{l}\leq n(1+\mu)e^{C(t-1)}:=\delta$.

Case 2. There is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is for
some $i,j\in[n]$, we have $a_{i}^{T}b_{j}\geq t$, and
$S_{ij}=e^{Ca_{i}^{T}b_{j}}\geq e^{Ct}$, so
$\hat{S}_{ij}\geq(1-\mu)S_{ij}=(1-\mu)e^{Ca_{i}^{T}b_{j}}\geq(1-\mu)e^{Ct}$.
Then for some $l\in[n]$, we have $Y_{l}\geq(1-\mu)e^{Ct}+n-1:=\Delta$

In order to distinguish between two cases, it is sufficient to have
$\Delta>\delta$. This holds with $C=2\log(\frac{1+\mu}{1-\mu}n)$.

Now let us look at the additive error approximation. With a $\mu$ additive
factor, if there are no pairs $a\in A$ and $b\in B$ with $a^{T}b\geq t$, then
we have for all $l\in[n],{Y}_{l}\leq ne^{C(t-1)}+n\mu:=\hat{\delta}$. On the
other hand, if there is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$, then
for some $l\in[n]$, we have ${Y}_{l}\geq e^{Ct}+n-1-\mu:=\hat{\Delta}$. In
order to distinguish between two cases, it is sufficient to have
$\hat{\Delta}>\hat{\delta}$ and this inequality holds with $C=2\log(n+2\mu)$.

Thus, if there is an algorithm for computing self-attention up to an element-
wise multiplicative or additive error $\mu$ that runs in $O(n^{2-\epsilon})$
time, this entire process takes at most $O(n^{2-\epsilon})$, and this
algorithm decides if there exists at least a pair of vectors $a\in A$ and
$b\in B$ such that $a^{T}b\geq t$ in $O(n^{2-\epsilon})$ time, which
contradicts the hardness result of TVPP (Lemma 1). This completes the proof. ∎

Similar proofs also work to show the quadratic complexity of multiplicative
approximation to the $S$ of softmax dot-product self-attention, and
$\ell_{2}$-self-attention directly from Theorem 2 and Theorem 4. And also by
Theorem 3, one can show the quadratic complexity of additive and
multiplicative approximation to the $S$ of sliding window dot-product self-
attention.

##  Appendix D Proofs of Lemmas for Polynomial Approximations of Self-
Attention

#### Lemma 4.

Let $p$ be an integer $\geq 0$ and let $S_{ij}$ be
$C\cdot(Q_{i}^{T}K_{j})^{p}$ where $i,j\in[n]$ and $C$ is a constant. Then
$SV$ can be computed in $O(nd_{q}^{p}d_{v})$ time.

###### Proof.

We omit the constant $C$ in this proof since we can multiply any of the
matrices $Q,K,V$ by $C$ in $O(nd_{q})$ or $O(nd_{v})$ time before the rest of
the computation.

When $p=1$, $SV=QK^{T}V$ thus $SV$ can be trivially computed by first
computing $K^{T}V$ by multiplying $K^{T}$ and $V$ with $O(d_{q}nd_{v})$ time,
then by multiplying $Q$ and $K^{T}V$ with $O(nd_{q}d_{v})$ time.

For $p\geq 2$, Consider a fixed $(i,j)$ pair. Now

$\begin{split}S_{ij}&=(Q_{i}^{T}K_{j})^{p}=\Big{(}\sum_{r=1}^{d_{q}}x_{r}y_{r}\Big{)}^{p}=\Big{(}x_{1}y_{1}+\dots+x_{d_{q}}y_{d_{q}}\Big{)}^{p}=\sum_{r_{1},\dots,r_{p}=1}^{d_{q}}x_{r_{1}}y_{r_{1}}\dots
x_{r_{p}}y_{r_{p}}\\\ &=\sum_{r_{1},\dots,r_{p}=1}^{d_{q}}(x_{r_{1}}\dots
x_{r_{p}})(y_{r_{1}}\dots y_{r_{p}})\end{split}$ (3)

where $x=Q_{i},y=K_{j}$ and $x_{r},y_{r}$ denote the $r^{th}$ element of the
corresponding vectors. Given a vector $v\in\mathbb{R}^{d_{q}}$, let us define
a function $\alpha:\mathbb{R}^{d_{q}}\rightarrow\mathbb{R}^{d_{q}^{p}}$ where
elements of $\alpha(v)$ are computed by element-wise multiplication
$v_{r_{1}}\dots v_{r_{p}},r_{1},\dots,r_{p}\in[d_{q}]$(ordered
$p$-permutations of $d_{q}$ with replacement). With this, let us define
$\hat{Q}\in\mathbb{R}^{n\times d_{q}^{p}}$(and $\hat{K}$) where each row $i$
is computed with $\alpha(Q_{i})$(respectively $\alpha(K_{j})$ for $\hat{K}$).
$\hat{Q},\hat{K}$ matrices can be computed in $O(nd_{q}^{p})$ time. From Eq.3,
it is evident that $(Q_{i}^{T}K_{j})^{p}=\hat{Q}_{i}^{T}\hat{K}_{j}$. Now,
similar to the case $p=1$ one can compute $SV$ by first computing
$\hat{K}^{T}V$ by multiplying $\hat{K}^{T}$ and $V$ with $O(d_{q}^{p}nd_{v})$
time, then by multiplying $\hat{Q}$ and $\hat{K}^{T}V$ with
$O(nd_{q}^{p}d_{v})$ time. This completes the proof.

∎

#### Lemma 5.

Let $p$ be an integer $\geq 0$. Then for all $i\in[n]$,
$\sum_{\hat{j}=1}^{n}C\cdot(Q_{i}^{T}K_{\hat{j}})^{p},\hat{j}\in[n]$ where $C$
is a constant can be computed in $O(nd_{q}^{p})$ time.

###### Proof.

We omit the constant $C$ in this proof since we can multiply any of the
matrices $Q,K$ by $C$ in $O(nd_{q})$ time before the rest of the computation.

Let $\hat{Q},\hat{K}\in\mathbb{R}^{n\times d_{q}^{p}}$ be the matrices
computed by applying $\alpha(.)$ on rows of $Q,V$ as stated in the proof of
Lemma 4(from Eq. 3). The time complexity of computing $\hat{Q},\hat{K}$ is
$O(nd_{q}^{p})$.

Now we have
$\sum_{\hat{j}=1}^{n}(Q_{i}^{T}K_{\hat{j}})^{p}=\sum_{\hat{j}=1}^{n}\hat{Q_{i}}^{T}\hat{K_{\hat{j}}}=\hat{Q_{i}}^{T}\sum_{\hat{j}=1}^{n}\hat{K_{\hat{j}}}$.
Let $A=\sum_{\hat{j}=1}^{n}\hat{K_{\hat{j}}}$ and $A$ can be computed in
$O(nd_{q}^{p})$ time(taking the summation of $n$ $d_{q}^{p}$ size vectors). We
store the value of $A$ in the memory and reuse it. One can simply compute the
inner product of $\hat{Q_{i}}^{T}$ and $A$ in $O(d_{q}^{p})$ time per $i$. For
all $i\in[n]$, this takes $O(nd_{q}^{p})$ time which gives the desired time
complexity.

∎

##  Appendix E  Proof for Hardness of $\ell_{2}\textnormal{-}$Self-Attention

#### Theorem 4.

Assume SETH. For any $i,j\in[n]$, let $S_{ij}=f(Q_{i},Q_{j})=e^{C.\left\lVert
Q_{i}-Q_{j}\right\rVert_{2}^{2}}$ where $C$ is a parameter and for any matrix
$M\in\mathbb{R}^{n\times n}$, let $h(M)=M$. Let
$Y=h(S).V\in\mathbb{R}^{n\times d_{v}}$ be a self-attention. Then for any
$\epsilon>0$, computing a matrix $\hat{Y}\in\mathbb{R}^{n\times d_{v}}$ that
satisfies any of the following conditions requires $\Omega(n^{2-\epsilon})$
time when $d_{q}=\omega(\log n)$.

  1. 1.

$\hat{Y}=Y$(exact).

  2. 2.

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu|Y_{ij}|$ for all $i\in[n]$ and $j\in[d_{v}]$
where $0\leq\mu<1$(multiplicative approximation).

###### Proof.

Consider two sets $A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$
given in BHCP, where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are binary vectors for all
$i\in[n]$. The problem is to decide if there exists at least a pair $a\in A$
and $b\in B$ that satisfies $\left\lVert a-b\right\rVert_{2}^{2}<t$ for a
given $t\in[n]$.

Suppose that the matrices $Q$ and $V$ are constructed according to BHCP vector
gadgets described in the section 4.2. With this we have
$Y=h(S).V\in\mathbb{R}^{n\times 1}$. Since $Y$ is a vector, we abuse the
notation again and define $Y_{i}$ as the $i^{th}$ element of $Y$. Now consider
the first $n$ elements of $Y$. Since $Y=SV$, we have that

$Y_{i}=\sum_{j=1}^{n}e^{-C\left\lVert a_{i}-b_{j}\right\rVert_{2}^{2}}\text{
for any }i\in[n].$

Now we check the magnitude of $Y_{i},\in[n]$ in order to distinguish between
true and false cases in BHCP. It takes $O(n)$ time to check each
$Y_{i},i\in[n]$. First we focus on the exact computation. Consider the
following two cases.

Case 1. There are no pairs $a\in A$ and $b\in B$ with $\left\lVert
a_{i}-b_{j}\right\rVert_{2}^{2}\leq t$, that is for all $i,j\in[n]$, we have
$\left\lVert a_{i}-b_{j}\right\rVert_{2}^{2}\geq t$, and $e^{-C\left\lVert
a_{i}-b_{j}\right\rVert_{2}^{2}}\leq e^{-Ct}$. Then for all $l\in[n]$,
$Y_{l}\leq ne^{-Ct}:=\delta$.

Case 2. There is a pair $a\in A$ and $b\in B$ with $\left\lVert
a-b\right\rVert_{2}^{2}<t$, that is for some $i,j\in[n]$, we have $\left\lVert
a_{i}-b_{j}\right\rVert_{2}^{2}\leq t-1$, and $e^{-C\left\lVert
a_{i}-b_{j}\right\rVert_{2}^{2}}\geq e^{-C(t-1)}$. Thus for some $l\in[n]$, we
have $Y_{l}\geq e^{-C(t-1)}:=\Delta$

In order to distinguish between two cases, it is sufficient to have
$\Delta>\delta$. This holds with $C=2\log n$.

Now let us look at the multiplicative error approximation. With a $\mu$
multiplicative factor, if there are no pairs $a\in A$ and $b\in B$ with
$a^{T}b\geq t$, then we have for all
$l\in[n],\hat{Y}_{l}\leq(1+\mu)Y_{l}\leq(1+\mu)ne^{-Ct}:=\hat{\delta}$. On the
other hand, if there is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$, then
for some $l\in[n]$, we have
$\hat{Y}_{l}\geq(1-\mu)Y_{l}\geq(1-\mu)e^{-C(t-1)}:=\hat{\Delta}$. In order to
distinguish between two cases, it is sufficient to have
$\hat{\Delta}>\hat{\delta}$ and this inequality holds with
$C=2\log(\frac{1+\mu}{1-\mu}n)$.

Thus, if there is an algorithm for computing self-attention up to an element-
wise multiplicative error $\mu$ that runs in $O(n^{2-\epsilon})$ time, this
entire process takes at most $O(n+nd+n^{2-\epsilon})=O(n^{2-\epsilon})$ as
long as $d=o(n^{1-\epsilon})$, and this algorithm decides if there exists at
least a pair of vectors $a\in A$ and $b\in B$ such that $\left\lVert
a_{i}-b_{j}\right\rVert_{2}^{2}\geq t$ in $O(n^{2-\epsilon})$ time, which
contradicts the hardness result of BHCP (Lemma 3). This completes the proof. ∎

Here in the proof we set $C=2\log(\frac{2(1+\mu)}{1-\mu}n)$ however, the
parameter $C$ in the RBF kernel is predefined, therefore the hardness result
is valid only conditioned on this specific $C$. We can bypass this by simply
defining $C=\log(\frac{2(1+\mu)}{1-\mu}n)=\alpha\beta$, then setting $\alpha$
to the predefined constant of the RBF function and solving this equation for
$\beta$. After this, all that remains is modifying the BHCP vector gadget(see
section 4.2) by multiplying each vector $Q_{i},i\in[2n]$ by the scaler
$\sqrt{\beta}$ in $O(n)$ time, and we obtain the desired hardness result for
general RBF kernel.

##  Appendix F Multi-Head Self-Attention

#### Lemma 6.

$k$ parallel OVP (or TVPP, or BHCP, or BHFP) problems (each has two sets with
n binary vectors) require $O(kn^{2-\epsilon})$ time for any $\epsilon$.

###### Proof.

Suppose there is an algorithm for k parallel OVP (TVPP, BHCP, BHFP) problems
better than $O(kn^{2-\epsilon})$ time.

Say $A_{i}$ and $B_{i}$ are the sets of binary vectors with size $n$ for any
$i\in[k]$.

For each $t\in[k]$, look at these k parallel OVP (TVPP, BHCP, BHFP) problems:

$(A_{1},B_{t}),(A_{2},B_{t+1}),\cdots,(A_{k},B_{t+k-1})\textnormal{, where
}B_{l+k}=B_{l}$

Because of the assumption, there is an algorithm better than
$O(kn^{2-\epsilon})$ time.

So that, there is an $O(k\times kn^{2-\epsilon})$-time algorithm that solves
OVP problem of ($A=A_{1}\cup\cdots A_{k}$, $B=B_{1}\cup\cdots B_{k}$). In
other words for the OVP (TVPP, BHCP, BHFP) problem with sets of size $nk$
binary vectors has an algorithm in $O(kn^{2-\delta})$-time (by selecting
$\delta=\epsilon/2$ and $k<n$). This contradicts SETH. As a result, $k$
parallel OVP (TVPP, BHCP, BHFP) problems require $O(kn^{2-\epsilon})$ time for
any $\epsilon$.

This lemma proves that the “direct sum" of computational complexity for OVP
(TVPP, BHCP, BHFP) problems is valid.

∎

##  Appendix G Discussion of Additive Approximation

This part is depends on for a given $C$ value, and the selected $\delta$ and
$\Delta$ values, the difference $\Delta-\delta$ is positive. So that, this
allows us to select an additive error $\mu$.

The following theorem shows that the we cannot reach better elementwise
additive approximation than $e^{-2d\log(n+2)}$ for the $\ell_{2}$ distance
self-attention.

#### Theorem 5.

Assume SETH. For any $i,j\in[n]$, let
$S_{ij}=f(Q_{i},Q_{j})=e^{-C\|Q_{i}-Q_{j}\|_{2}^{2}}$, where $C$ is a
parameter and for any matrix $M\in R^{n\times n}$. Let $h(M)=M$ and $Y=h(S)$.
$V\in\mathbb{R}^{n\times d_{v}}$ be self-attention. Then for any $\epsilon>0$,
computing a matrix $\hat{Y}\in R^{n\times d_{v}}$ that satisfies the following
condition requires $\Omega(n^{2-\epsilon})$ time when $d_{q}=\omega(\log n)$:
$|\hat{Y}_{ij}-Y_{ij}|\leq\mu$ for all $i\in[n]$ and $j\in[d_{v}]$, where
$0\leq\mu\leq e^{-2d\log(n+2)}=(n+2)^{-2d}$ (additive approximation)

###### Proof.

Consider two sets $A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$
given in BHCP, where $a_{i},b_{i}\in\\{0,1\\}^{d}$ are binary vectors for all
$i\in[n]$. The problem is to decide if there exists at least a pair $a\in A$
and $b\in B$ that satisfies $\|a-b\|_{2}^{2}<t$ for a given $t\in[n]$.

Suppose that the matrices $Q$ and $V$ are constructed according to BHCP vector
gadgets described in the section 4.2. With this we have $Y=h(S)\cdot V\in
R^{n\times 1}$. Since $Y$ is a vector, we abuse the notation again and define
$Y_{i}$ as the $i$th element of $Y$. Now consider the first n elements of $Y$.
Since $Y=SV$, we have that $Y_{i}=\sum_{j=1}^{n}e^{-C\|a_{i}-b_{j}\|_{2}^{2}}$
for any $i,j\in[n]$.

Case 1. There are no pairs $a\in A$ and $b\in B$ that satisfies
$\|a-b\|_{2}^{2}<t$, that is for all $i,j\in[n]$, we have $\|a-b\|_{2}^{2}\geq
t$, and $e^{-C\|a_{i}-b_{j}\|_{2}^{2}}\leq e^{-Ct}$. Then for all $l\in[n]$,
$Y_{l}\leq ne^{-Ct}$. It is given that $|\hat{Y}_{l}-Y_{l}\leq\mu$, so
$\hat{Y}_{l}\leq Y_{l}+\mu\leq ne^{-Ct}+\mu\leq
ne^{-Ct}+e^{-2d\log(n+2)}=:\delta$.

Case 2. There is a pair $a\in A$ and $b\in B$ with $\|a-b\|_{2}^{2}<t$, that
is for some $i,j\in[n]$, we have $\|a-b\|_{2}^{2}\leq t-1$, and
$e^{-C\|a_{i}-b_{j}\|_{2}^{2}}\geq e^{-C(t-1)}$. Thus for some $l\in[n]$,
$Y_{l}\geq ne^{-C(t-1)}$. It is given that $|\hat{Y}_{l}-Y_{l}\leq\mu$ , so
$\hat{Y}_{l}\geq Y_{l}-\mu\leq ne^{-Ct}-\mu\geq
ne^{-Ct}-e^{-2d\log(n+2)}=:\Delta$.

In order to distinguish between two cases, it is sufficient to have
$\Delta>\delta$. This holds with $C=2\log(n+2)$.

Thus, if there is an algorithm for computing self-attention up to an element-
wise additive error $\mu\leq e^{-2d\log(n+2)}$ that runs in
$O(n^{2-\epsilon})$ time, this entire process takes at most
$O(n+nd+n^{2-\epsilon})=O(n^{2-\epsilon})$ as long $d=O(n^{1-\epsilon})$, and
this algorithm decides if there exists at least a pair of vectors $a\in A$ and
$b\in B$ with $\|a-b\|_{2}^{2}<t$ in $O(n^{2-\epsilon})$ time, which
contradicts the hardness result of BHCP (Lemma 3). This completes the proof. ∎

This additive approximation error can be improved slightly, but its order must
be $O(n^{-d})$.

The following theorem shows that the we cannot reach better elementwise
additive approximation than $e^{-3d\log(n)-3d^{2}}=n^{-3d}\cdot e^{-3d^{2}}$
for the softmax dot-product self-attention.

#### Theorem 6.

Assume SETH. For any $i,j\in[n]$, let
$S_{ij}=f(Q_{i},Q_{j})=e^{Q_{i}^{T}Q_{j}}$, and for any matrix
$M\in\mathbb{R}^{n\times n}$ , let $h(M)\in\mathbb{R}^{n\times n}$ be the
matrix where for all $i,j\in[n]$,
$\\{h(M)\\}_{ij}=\frac{M_{ij}}{\sum_{k_{1}}^{n}M_{ik}}$. Let $Y=h(S)\cdot
V\in\mathbb{R}^{n\times d_{v}}$ be self-attention. Then provided
$d_{q}=\omega(\log n)$, for any $\epsilon>0$, computing a matrix
$\hat{Y}=\mathbb{R}^{n\times d_{v}}$ that satisfies the following condition
requires $\Omega(n^{2-\epsilon})$ time:

$|\hat{Y}_{ij}-Y_{ij}|\leq\mu$ for all $i\in[n]$ and $j\in[d_{v}]$, where
$0\leq\mu\leq e^{-3d\log(n)-3d^{2}}$ (additive approximation)

###### Proof.

The proof is technically similar. Suppose that the matrices $Q$ and $V$ are
constructed according to TVPP vector gadgets described in Section 4.2. With
this we have $Y=h(S)\cdot V\in\mathbb{R}^{n\times 1}$. Consider the first $n$
elements of $Y$. Since $h(\cdot)$ act as the row-wise softmax function, we
have

$\displaystyle Y_{i}=\sum_{j=n+1}^{2n}S_{ij}$
$\displaystyle=\sum_{j=1}^{n}\frac{e^{Ca_{i}^{T}b_{j}}}{\sum_{k=1}^{n}e^{Ca_{i}^{T}a_{k}}+\sum_{k=1}^{n}e^{Ca_{i}^{T}b_{k}}}$
$\displaystyle=\frac{\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}}{\sum_{k=1}^{n}e^{Ca_{i}^{T}a_{k}}+\sum_{k=1}^{n}e^{Ca_{i}^{T}b_{k}}}$

Case 1. There are no pairs $a\in A$ and $b\in B$ that satisfies $a^{T}b\geq
t$, that is for all $i,j\in[n]$, we have $a^{T}b\leq t-1$, and
$\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}\leq ne^{C(t-1)}$. For a function
$\frac{x}{x+y}$, the maximum value is achieved at maximum $x$ and minimum $y$
values. Thus, for all $l\in[n]$,
$Y_{l}\leq\frac{ne^{C(t-1)}}{ne^{C(t-1)}+n}=\frac{e^{C(t-1)}}{e^{C(t-1)}+1}$.
It is given that $|\hat{Y}_{l}-Y_{l}|\leq\mu$ , so $\hat{Y}_{l}\leq
Y_{l}+\mu\leq\frac{e^{C(t-1)}}{e^{C(t-1)}+1}+\mu\leq\frac{e^{C(t-1)}}{e^{C(t-1)}+1}+e^{-3d\log(n)-3d^{2}}=:\delta$.

Case 2. There is a pair $a\in A$ and $b\in B$ with $a^{T}b\geq t$, that is for
some $i,j\in[n]$, we have $a^{T}b\geq t$. Then the row sum corresponding to
that $i,j$ pair is $\sum_{j=1}^{n}e^{Ca_{i}^{T}b_{j}}\geq
e^{Ct}+(n-1)e^{0}=e^{Ct}+n-1$. For a function $\frac{x}{x+y}$, the maximum
value is achieved at minimum $x$ and maximum $y$ values. Thus, for some
$l\in[n]$, we have $Y_{l}\geq\frac{e^{Ct}+(n-1)}{e^{Ct}+(n-1)+ne^{d}}$.

∎

##  Appendix H Discussion of Remark in Section 4.4

In our results, we show the quadratic hardness of multiplicative error
approximations self-attention matrix elements for dot-product softmax self-
attention mechanism. One assumption we make on the approximation factor $\mu$
is that $\mu<1$. Consider the value of the parameter
$C=\log(\frac{2(1+\mu)}{1-\mu}n)+d$ in the proof of theorem 2. Notice that
when $\mu=1$, $C$ is not defined. In fact, having $\mu=1$ implies that the
$|\hat{Y}_{l}-Y_{l}|=|Y_{l}|$ for all $l\in[n]$, therefore one can approximate
every entry of $\hat{Y}$ by $0$ in $O(n)$ time while satisfying this
condition. However, as mentioned in the remark, one can set $\mu$ close to $1$
by setting it as $1-\frac{1}{n^{x}}$ for a constant $x$, while maintaining the
condition on $C$ in the same order.