Fundamental Limitations on Subquadratic Alternatives to Transformers

## Abstract

Abstract The Transformer architecture is widely deployed in many popular and impactful Large Language Models. At its core is the attention mechanism for calculating correlations between pairs of tokens. Performing an attention computation takes quadratic time in the input size, and had become the time bottleneck for transformer operations. In order to circumvent this, researchers have used a variety of approaches, including designing heuristic algorithms for performing attention computations faster, and proposing alternatives to the attention mechanism which can be computed more quickly. For instance, state space models such as Mamba were designed to replace attention with an almost linear time alternative. In this paper, we prove that any such approach cannot perform important tasks that Transformer is able to perform (assuming a popular conjecture from fine-grained complexity theory). We focus on document similarity tasks, where one is given as input many documents and would like to find a pair which is (approximately) the most similar. We prove that Transformer is able to perform this task, and we prove that this task cannot be performed in truly subquadratic time by any algorithm. Thus, any model which can be evaluated in subquadratic time – whether because of subquadratic-time heuristics for attention, faster attention replacements like Mamba, or any other reason – cannot perform this task. In other words, in order to perform tasks that (implicitly or explicitly) involve document similarity, one may as well use Transformer and cannot avoid its quadratic running time.

## 1 Introduction

The Transformer architecture [] is widely used for natural language processing [, ], computer vision [, ], and many other tasks, and has achieved state-of-the-art performance for numerous applications. At the core of the architecture is the attention mechanism which is designed to calculate the correlation between all pairs of tokens in a given input sequence. Namely, let $Q\in\mathbb{R}^{d_{\textup{in}}\times m}$ be the query matrix, $K\in\mathbb{R}^{d_{\textup{in}}\times m}$ be the key matrix and $V\in\mathbb{R}^{d_{\textup{in}}\times d_{\textup{out}}}$ be the value matrix. Given $X\in\mathbb{R}^{n\times d_{\textup{in}}}$, an attention mechanism computes

$$ $A_{Q,K,V}(X):=\textup{softmax}(XQK^{\top}X^{\top})XV$ $$

where the softmax operator

$$ $\textup{softmax}(v)=\frac{(\exp(v[1]),\ldots,\exp(v[n]))}{\sum_{i=1}^{n}\exp(v [i])}$ $$

for $v\in\mathbb{R}^{n}$ is applied to matrices row-wise. Computing the attention by straightforwardly following the definition above requires quadratic time (in the sequence length $n$), which prohibits efficient model training when the sequence length is too large. As a result, much effort has been devoted to overcoming this obstacle in recent years, and there are two major lines of research to tackle the problem.

The first line of research argues that instead of computing attention exactly in the worst case, it often suffices to use heuristics which work well when the input data has additional structure, or to only return coarse approximations of the attention mechanism which can be computed more quickly. Examples including KDEformer [], Reformer [], Hyperattention [], Linformer [], SMYRF [], and Performer []. In many cases, these heuristics result in algorithms which run in close to linear time. However, these techniques usually have corresponding downsides, such as model accuracy drops, or performance gains which do not appear to scale to large inputs.

The second line of research argues that instead of computing or approximating attention, we can replace the standard attention mechanism with new, different mechanisms which can be computed faster. Models such as Longformer [], Synthesizer [], Routing transformers [], and Mamba [] all aim to circumvent the quadratic barrier by proposing new attention alternatives. A priori, these techniques would result in weaker expressiveness since they replace attention’s calculation of token interactions with simpler alternatives, although most also provide empirical evidence that the loss in accuracy at certain tasks is not large.

In this paper, we prove that any approach that takes subquadratic time, no matter whether it uses heuristic or approximations, or a new architecture, or a completely different approach, is inherently unable to perform important learning tasks that a transformer is able to perform. By using tools and popular hardness conjectures from the area of fine-grained complexity theory, we show that many learning tasks involving document similarity cannot possibly be solved in subquadratic time using *any* algorithmic approach. This implies that subquadratic alternatives to standard transformers are not able to solve these simple and natural tasks in machine learning and NLP. To complement this, we show that standard transformers (even simple transformers with one layer and one attention head) are able to perform these tasks, thereby establishing a separation between standard transformers and these new approaches. In other words, we prove that accuracy loss for any task relating to document similarity is *unavoidable* for any subquadratic approach, even when compared only to the simplest transformers, because of the inherent computational complexity of the task.

### 1.1 Document Similarity

In this work we will be focusing on document similarity tasks. We will show that standard transformers are capable of solving these tasks but subquadratic alternatives to transformers cannot.

Document similarity is a fundamental area in natural language processing with many applications including recommender systems [], search engines [], and plagiarism-detection []. For a given document $D$, we first need to define a document embedding to transform it into a vector $v\in\mathbb{R}^{d}$, and we will then measure how similar two documents are by using a similarity measure on their embedding vectors. There are many ways to embed a document as a vector including Doc2Vec [], TF-IDF [], BERT [], bag-of-words [], and many ways to measure how similar two documents are including cosine similarity, Euclidean distance, and Jaccard Similarity. In this work, we focus on two of the most popular options, bag-of-words embedding and cosine similarity, although our results extend naturally to almost any reasonable alternatives.

##### Bag-of-words Embedding.

Bag-of-words embedding is a well-studied method of embedding [] that is commonly used for text classification [], radiology [] and many other settings, especially in NLP. Given a document $D$ and a list of $\ell$ key words, the bag-of-words embedding of $D$ is a vector $v\in\{0,1\}^{\ell}$ such that the $i$-th entry of $v$ corresponds to whether the $i$-th key word exists in $D$ or not. (^1^11Sometimes the entries are also frequency counts, but that would only make the embedding vectors more complex. Since our main goal is to show hardness, we will focus on the simpler binary case.) For example, if a document only contains one sentence “There are ten apples on the apple tree” and the key words chosen are “apple”, “tree”, “computer” and “ten”, this document will have bag-of-words embedding $(1,1,0,1)$.

##### Cosine Similarity.

Cosine similarity is one of the most commonly used method to measure how similar two documents are. Given two document embeddings $v,w\in\mathbb{R}^{d}$, the cosine similarity is given by

$$ $\frac{\langle v,w\rangle}{\|v\|_{2}\cdot\|w\|_{2}}\in[0,1]$ $$

where $1$ represents complete similarity and 0 0 represents no similarity. It is defined in this way, rather than just taking the inner product $\langle v,w\rangle$, so that two documents (vectors) with large magnitude can still be considered close if they have similar directions. Cosine similarity is one of the most popular and effective measures; for instance, [] found that when used for extractive multi-document text summarization, cosine similarity gives the best results.

##### Problem Statement.

We define our most similar document $(\mathsf{MSD})$ and least similar document $(\mathsf{LSD})$ problems as: given a set of $n$ binary vectors $v_{1},\ldots,v_{n}$ of length $d$ (document embeddings), the goal is to find two documents that are the most/least similar to each other in terms of cosine similarity. There are many natural variants of these two problems, and we prove similar hardness for all of them:

- 1.
(Bichromatic $\mathsf{MSD},\mathsf{LSD}$) Sometimes we have two sets of documents $A,B$ and we want to find one document from each set such that the pair is (un)similar.
- 2.
($\gamma\textup{-}\mathsf{MSD},\gamma\textup{-}\mathsf{LSD}$) Sometimes we might only need to find a pair of documents that is *approximately* the most (un)similar, (up to an approximation factor $\gamma$) and not necessarily the optimal pair.
- 3.
$(\mathsf{MSD}_{n,d,t},\mathsf{LSD}_{n,d,t})$ Sometimes we only want to know if there exists a pair whose cosine similarity is above (or below) a threshold $t\in[0,1]$.

These variants occur in many practical scenarios when using a large language model. They can arise explicitly when the descriptions of $n$ documents of size $\ell$ are given to a language model, and the model is asked to find the most similar pair of documents. However, there are many scenarios where document similarity can arise implicitly as well. For example,

- •
when an animal protection organization has the profiles of $n$ pets and $n$ families and wants to find a best match for adoption;
- •
when a college professor wants to see if there is any academic integrity issues in an important exam;
- •
when one wants to find repetitive or redundant passages in a text, and thus must implicitly determine which pair of passages is most similar.

### 1.2 Main Results

Our hardness results are based on a prevalent conjecture from fine-grained complexity theory called the Strong Exponential Time Hypothesis $(\mathsf{SETH})$:

*for every $\varepsilon>0$, there is an integer $k$ such that $k\mathsf{SAT}$ with $n$ variables requires $\Omega(2^{(1-\varepsilon)n})$ time*.

$\mathsf{SETH}$ was first introduced by [], and is a popular strengthening of the conjecture that $\mathsf{P}\neq\mathsf{NP}$. (In other words, proving that $\mathsf{SETH}$ is true implies $\mathsf{P}\neq\mathsf{NP}$.) Since then, there has been a long line of work studying and making use of $\mathsf{SETH}$. Prior work has given theoretical evidence for $\mathsf{SETH}$, including showing that if $\mathsf{SETH}$ is false, then surprising complexity-theoretic consequences would follow [, , ], and using $\mathsf{SETH}$ to prove hardness of problems in many different areas of algorithm design. See the survey [] for a detailed background.

##### Main Results: Limitations of subquadratic alternatives.

We show that $\mathsf{MSD},\mathsf{LSD}$ and their variants require quadratic time assuming $\mathsf{SETH}$ for some natural choice of parameters, and therefore any subquadratic alternatives to transformers are not able to solve them due to computational constraints. The formal hardness results are as follows, and vary slightly in the dimension parameter $\ell$ depending on the details of the problem:

###### Theorem 1.1 ( Theorem 3.1 and Corollary 3.2 ) .

Assuming $\mathsf{SETH}$, for every $\varepsilon>0$, there exists a constant $c>0$ such that $\mathsf{LSD}_{n,\ell}$ cannot be solved in $O(n^{2-\varepsilon})$ time when $\ell=c\log n$. Moreover, the same lower bound also holds for $\mathsf{LSD}_{n,\ell,t}$ for some $0<t<1$, $\gamma\text{-}\mathsf{LSD}_{n,\ell}$ for any $\gamma\geq 1$, and bichromatic $\mathsf{LSD}_{n,\ell}$.

###### Theorem 1.2 ( Theorem 3.3 and Corollary 3.4 ) .

Assuming $\mathsf{SETH}$, for every $\varepsilon>0$, there exists a constant $c>0$ such that $\mathsf{MSD}_{n,\ell}$ cannot be solved in $O(n^{2-\varepsilon})$ time when $\ell=n^{\frac{c}{\log\log n}}$. Moreover, the same lower bound also holds for $\mathsf{MSD}_{n,\ell,t}$ for some $0<t<1$ and $\gamma\text{-}\mathsf{MSD}_{n,\ell}$ for any $1\leq\gamma\leq\operatorname{polylog}(n)$.

For bichromatic $\mathsf{MSD}$ we can obtain a stronger hardness result.

###### Theorem 1.3 ( Theorem 3.3 and Corollary 3.4 ) .

Assuming $\mathsf{SETH}$, for every $\varepsilon>0$, there exists a constant $c>0$ such that bichromatic $\mathsf{MSD}_{n,\ell}$ cannot be solved in $O(n^{2-\varepsilon})$ time when $\ell=c\log n$.

In all these problems, we prove hardness when $\ell$ is $\Theta(\log n)$ or $n^{o(1)}$. This is a natural choice: for any smaller $\ell<\log n$, there could be at most $2^{\ell}<n$ vectors under a bag-of-words embedding, which means that there would be duplicate vectors in our instance. Making $\ell$ larger can only make the problem harder.

It follows that any language task which, either explicitly or implicitly, involves solving any of these document similarity problems, cannot be solved in subquadratic time, no matter what the parameters or architecture of the language model are.(^2^22We briefly emphasize that the parameter $\ell$ in these similarity problems need not be related to the architecture or parameters (like $d_{\textup{in}},d_{\textup{out}}$, etc) of a language model which solves the problems. For instance, to ask a language model to solve $\mathsf{MSD}_{n,\ell}$, we may ask it “Which of the following paragraphs is most similar?” followed by a list of $n$ different paragraphs of at most $\ell$ words each. Thus, the input to the language model would be a string of length $O(n\ell)$, and since $\ell<n^{o(1)}$ is small compared to $n$, our result shows that a language model would need to take quadratic time in the string length to answer this type of query.)

###### Theorem 1.1 ( Theorem 3.1 and Corollary 3.2 ) .

###### Theorem 1.2 ( Theorem 3.3 and Corollary 3.4 ) .

###### Theorem 1.3 ( Theorem 3.3 and Corollary 3.4 ) .

##### Main Results: Representational strength of standard transformers.

When a problem requires quadratic time to solve, this means that subquadratic-time models cannot solve it, but it does not necessarily mean that a transformer model can solve it. For example, [] defined a problem called “Match3” which can be solved in quadratic time by a textbook algorithm, but which they prove cannot be solved by a one-layer transformer unless it has a lot of attention heads or a very high embedding dimension.

We show that this is not the case for $\mathsf{MSD}$ and $\mathsf{LSD}$ by showing that a single standard attention unit with input and output MLPs can solve $\mathsf{MSD}_{n,d,t},\mathsf{LSD}_{n,d,t}$ and $\mathsf{OV}$. Thus, these problems establish a separation between standard transformers and subquadratic alternatives to transformers.

###### Theorem 1.4 ( Theorems 4.1 and 4.3 ) .

A single unit of standard attention with input and output MLPs, embedding dimension $\ell+1$ can solve $\mathsf{OV}_{n,\ell}$ and $\mathsf{MSD}_{n,\ell,t},\mathsf{LSD}_{n,\ell,t}$ for any $0\leq t\leq 1$.

In principle, there could be concerns with representational results like these that the weights of the model are complicated and hard to find in training. However, our constructions of transformers that solve these problems are very simple: our MLPs are piece-wise linear functions that are easy to approximate/compute, and our key/query/value matrices in the attention unit are also simple, sparse and low-rank matrices with small entries.

###### Theorem 1.4 ( Theorems 4.1 and 4.3 ) .

### 1.3 Related Work

In recent years, several theoretical and algorithmic aspects of transformers have been extensively studied. We discuss next two aspects that are most relevant to our work, and which we build on in the proofs of our results.

##### Representational strengths of Transformers.

Representational strengths of transformers have been widely studied in recent years. It has been shown that transformers have several natural limitations, including not being able to model periodic
finite-state languages or hierarchical structure [], and not being able to recognize some counter languages without large depth []. On the other hand, transformers are able to recognize formal languages such as Dyck languages [], simulate finite-state automata [] with $O(\log n)$ depth, and simulate Turing machines if given enough depth [, ]. There is also a line of work [, ] that understands what transformers can compute through the lens of circuit complexity; see [] for a comprehensive survey.

Another line of work has shown that transformers can compute particular problems of interest, including PARITY (which perceptrons are notably unable to compute) [] and learning problems that attention is particularly suited toward like “sparse averaging” and “$k$-hop induction heads” [, ].

##### Faster attention mechanisms.

As previously discussed, attention computation remains a bottleneck for efficiency, and many different approaches have been proposed to tackle this issue. These approaches typically result in accuracy loss (and a consequence of our main result is theoretical proof that this is necessary), which has mostly been investigated empirically.

The main prior work on theoretical limitations of subquadratic transformers we’re aware of is []. Among other results, they study “kernel-based subquadratic attention” in which one heuristically computes attention faster by approximating intermediate matrices in the attention computation either by sparse matrices [, , ] or low-rank matrices [, ]. [] defined a “$k$-hop induction heads” task and proved that transformers can perform this task but kernel-based subquadratic attention models cannot. Our limitation result is more general than this, applying to any approach that runs in subquadratic time, rather than needing to focus on a particular architecture or heuristic.

##### Fine-Grained Complexity and Machine Learning

Fine-grained complexity theory has been successful at proving conditional lower bounds for problems in diverse areas of algorithm design, such as in graph theory [, , ] and combinatorial optimization [, , , ]. See [] for a detailed survey.

Recently, it has been shown that many problems in machine learning are also inherently hard assuming popular conjectures in fine-grained complexity. For example, [, ] use $\mathsf{SETH}$ to give a lower bound on the time to perform kernel density estimation, [] use $\mathsf{SETH}$ to demonstrate a computational phase transition in Hopfield models, and [, ] use $\mathsf{SETH}$ to give a lower bound on computational complexity of approximating the attention mechanism itself. We remark that our results, together, give a new, alternate proof of the hardness of attention assuming $\mathsf{SETH}$. Indeed, we prove that a single attention unit can solve $\mathsf{MSD}$, and that $\mathsf{MSD}$ requires quadratic time assuming $\mathsf{SETH}$, which together imply that evaluating the attention unit requires quadratic time.

##### Hardness of similarity search.

Similarity search has been a fundamental area in modern machine learning, and the efficiency of similarity search algorithms has been well-studied through the lens of fine-grained complexity. Perhaps the most well-known problem in this area is the nearest neighbor problem.

Nearest Neighbor is a fundamental problem in machine learning which has been the subject of decades of research [, , , , , , , ]. Given a dataset $P\subseteq\mathbb{R}^{d}$ with $n$ points, we want to preprocess it such that given a query point $q\in\mathbb{R}^{d}$, one can find its nearest neighbor in $P$ (in some metric) efficiently. The nearest neighbor problem gives one common way of classifying objects in machine learning: given an object with unknown label, one just find its nearest neighbor in the dataset and use its label as the label for the target object. In addition, it has many applications in classical similarity search over different types of data including text, images, audio (see [] for a complete overview).

There are many natural variants of the nearest neighbor problem, including the closest (furthest) pair problem where one is given a dataset $P$ and wants to find the two points from $P$ that are the closest (furthest). This problem is exactly $\mathsf{Min}\text{-}\mathsf{IP}(\mathsf{Max}\text{-}\mathsf{IP})$ if we let inner product be the measure of closeness. Under standard Euclidean distance, one can also express the distance between two points as $\|p-q\|=\|p\|+\|q\|-2\langle p,q\rangle$ such that when all points have the same $\ell_{2}$ norm, finding the closest pair is equivalent to finding the pair with the largest inner product, i.e. $\mathsf{Max}\text{-}\mathsf{IP}$. In fact, it has been shown that assuming $\mathsf{SETH}$ is true, finding closest pairs in Euclidean or Manhattan distance both require quadratic time [, ]. We will use this in our proofs below.

## 2 Preliminaries

##### Notation.

For a vector $v$, we use $v[i]$ to denote its $i$-th entry for all $i$. For a matrix $A$, we use $A_{i,:}$ to denote the $i$-th row of $A$ and $A_{:,j}$ to denote the $j$-th column of $A$. Given a positive integer $d$, we use $\mathbf{1}_{d}\in\mathbb{R}^{d}$ to denote the vector whose entries are all $1$. Given two vectors $v\in\mathbb{R}^{a},w\in\mathbb{R}^{b}$, we use $v\otimes w\in\mathbb{R}^{ab}$ to denote the Kronecker product of $v$ and $w$ (whose entries are all the products of an entry of $v$ and an entry of $w$) and $v\circ w\in\mathbb{R}^{a+b}$ to denote the concatenation of $v$ and $w$. $\|\cdot\|$ refers to $\ell_{2}$ norm unless otherwise specified. Given a binary vector $v\in\{0,1\}^{d}$, we use $\bar{v}\in\{0,1\}^{d}$ to denote the vector where all entries are flipped. The softmax operator, when given a vector $v\in\mathbb{R}^{n}$, outputs a vector in $\mathbb{R}^{n}$ given by

$$ $\textup{softmax}(v)=\frac{(\exp(v[1]),\ldots,\exp(v[n]))}{\sum_{i=1}^{n}\exp(v [i])}.$ $$

For matrices $A\in\mathbb{R}^{n\times n}$, we apply softmax operator row-wise, so that

$$ $\textup{softmax}(A)_{i,:}=\textup{softmax}(A_{i,:}).$ $$

### 2.1 The Transformer Architecture

Transformer is a machine learning architecture composed mainly of attention layers and multi-layer perceptrons (MLP). We model the input to a attention unit is a $n\times d_{\textup{in}}$ matrix where $d_{\textup{in}}$ is the input dimension and the output of a attention is a $n\times d_{\textup{out}}$ matrix where $d_{\textup{out}}$ is the output dimension.

###### Definition 2.1 (attention) .

For input dimension $d_{\textup{in}}\in\mathbb{N}$, output dimension $d_{\textup{out}}\in\mathbb{N}$, embedding dimension $m\in\mathbb{N}$, matrices $Q,K\in\mathbb{R}^{d_{\textup{in}}\times m}$ and $V\in\mathbb{R}^{d_{\textup{in}}\times d_{\textup{out}}}$, a *attention* is a mapping $A_{Q,K,V}:\mathbb{R}^{n\times d_{\textup{in}}}\rightarrow\mathbb{R}^{n\times d
_{\textup{out}}}$ by

$$ $A_{Q,K,V}(X)=\textup{softmax}(XQK^{\top}X^{\top})XV.$ $$

We use $\mathcal{A}_{d_{\textup{in}},m,d_{\textup{out}}}=\{A_{Q,K,V}:Q\in\mathbb{R}^{d
_{\textup{in}}\times m},K\in\mathbb{R}^{d_{\textup{in}}\times m},V\in\mathbb{R
}^{d_{\textup{in}}\times d_{\textup{out}}}\}$ to denote all such attentions.

An attention layer consists of many attentions in parallel. Upon receiving input $X$, each attention computes an output locally, then the results are all concatenated into a large matrix before being sent to the next layer. Our constructions in this paper will only need transformers with one layer and one single unit of attention to illustrate representational strength (transformers with more layers and heads could only be stronger), so we omit the formal definitions of attention layers.

A *multi-layer perceptron* (MLP) is a type of neural network that is used to learn nonlinear relationships in data. Mathematically, it is usually formulated as a neural network with different types of activation functions [, , ] or sometimes as a more specific threshold circuit []. Since the universal approximation theorem [] states that any continuous function with a finite support can be approximated by a neural network with one hidden layer, [, ] modeled MLP as an arbitrary function $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d^{\prime}}$ defined on fixed-precision vectors, and we will notationally use that definition here.

###### Definition 2.2 (Multi-player perceptron) .

A multi-layer perceptron is represented by some continuous function $\varphi:\mathbb{R}^{a}\rightarrow\mathbb{R}^{b}$ for some positive integers $a,b$. We can apply $\varphi$ to a matrix row-wisely: given any matrix $X\in\mathbb{R}^{n\times a}$, $\varphi(X)=(\varphi(X_{1}),\ldots,\varphi(X_{n}))\in\mathbb{R}^{n\times b}$.

That said, in all our constructions in this paper, it will suffice to use MLPs which are simple, piecewise-linear functions that fit in all the categories discussed above, and can be easily approximated by a small neural network or any other MLP definition.

In this work, our transformer (with a single attention unit) will be defined as a composition of the first MLP, then one attention unit, then the second MLP. This is a natural model for many well-known transformer models including BERT [], GPT-3 [], GPT-4 [] and is typically used in theoretical work on simple transformers [, , ].

Recall in particular that we will be designing such transformers for document similarity problems. In this case, given $n$ documents $D_{1},\ldots,D_{n}$, we will let their bag-of-words embeddings

$$ $(\mathsf{BOW}(D_{1}),\ldots,\mathsf{BOW}(D_{n}))^{\top}\in\mathbb{R}^{n\times d}$ $$

be the input to our transformer, and the output of the transformer will be a real number indicating the answer to our problems.

###### Definition 2.3 .

A *transformer* is a mapping $\mathsf{TF}:\mathbb{R}^{n\times d}\rightarrow\mathbb{R}$ specified by a attention unit $A_{Q,K,V}$ and two MLPs $\varphi_{1}:\mathbb{R}^{n\times d}\rightarrow\mathbb{R}^{n\times d_{\textup{in
}}},\varphi_{2}:\mathbb{R}^{n\times d_{\textup{out}}}\rightarrow\mathbb{R}$. Upon an embedding matrix $E\in\mathbb{R}^{n\times d}$, the transformer outputs $\varphi_{2}(A_{Q,K,V}(\varphi_{1}(E)))$.

To emphasize, this is a very simplified model of a transformer with a single attention unit. We say that a transformer $\mathsf{TF}$ solves a problem whose input is a matrix $E\in\mathbb{R}^{n\times d}$ if $\mathsf{TF}(E)$ is the answer of the problem on instance $E$. For example, for decision problems like $\mathsf{MSD}_{n,d,t}$, we say $\mathsf{TF}$ solves $\mathsf{MSD}_{n,d,t}$ if for all input $v_{1},\ldots,v_{n}$ and $E$ such that $E_{i,:}=v_{i}$ for all $i$, $\mathsf{TF}(E)=1$ if there exists a pair $\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|\cdot\|v_{j}\|}\geq t$ and $\mathsf{TF}(E)=0$ otherwise.

###### Definition 2.1 (attention) .

###### Definition 2.2 (Multi-player perceptron) .

###### Definition 2.3 .

### 2.2 Fine-Grained Complexity

We first introduce some common notions from fine-grained complexity. In fine-grained complexity, one is usually interested in whether we can improve the running time of our algorithms by a polynomial factor. For example, the $\mathsf{OV}$ problem (defined below) has a straightforward quadratic time (ignoring logarithmic factors) algorithm, and it is a major open problem to determine whether there exists a faster, $O(n^{1.99})$ time algorithm. We say that an algorithm is *truly subquadratic* (^3^33Usually in fine-grained complexity, a subquadratic time algorithm means the algorithm runs in time $o(n^{2})$, and a truly subquadratic time algorithm means the algorithm runs in time $O(n^{2-\varepsilon})$ for a fixed constant $\varepsilon>0$. For example, $O(n^{2}/\log n)$ is subquadratic but not truly subquadratic. By contrast, in the context of fast attention, prior machine learning literature often just calls an approach subquadratic to mean that it is truly subquadratic, or often even almost linear time. In this work, we will use the fine-grained complexity definition and refer to such approaches as truly subquadratic.) if it runs in time $O(n^{2-\varepsilon})$ for some constant $\varepsilon>0$. In this work, all our problems have quadratic time solutions, and we are interested in whether truly subquadratic time algorithms exist.

A key technique (that we will use frequently in this work) in fine-grained complexity is the *fine-grained reduction*, which is a way to connect the running times of different problems. If problems $\mathcal{P}$ and $\mathcal{Q}$ both have quadratic time algorithms, we say that $\mathcal{P}$ *reduces to* $\mathcal{Q}$ (sometimes we would also say $\mathcal{P}$ is easier than $\mathcal{Q}$ or $\mathcal{Q}$ is harder than $\mathcal{P}$) if a truly subquadratic time algorithm for $\mathcal{Q}$ implies a truly subquadratic time algorithm for $\mathcal{P}$. We say $\mathcal{P}$ and $\mathcal{Q}$ are *subquadratic equivalent* if they reduce to each other, i.e. there is a truly subquadratic time algorithm for $\mathcal{P}$ if and only if there is a truly subquadratic time algorithm for $\mathcal{Q}$. Such relationships are proved by careful reductions, and we will see many examples soon.

#### 2.2.1 Hardness Conjectures: 𝖲𝖤𝖳𝖧 𝖲𝖤𝖳𝖧 \mathsf{SETH} sansserif_SETH and 𝖮𝖵𝖢 𝖮𝖵𝖢 \mathsf{OVC} sansserif_OVC

We restate our central hardness conjecture here.

###### Definition 2.4 (Strong Exponential Time Hypothesis ( $\mathsf{SETH}$ )) .

For any $\varepsilon>0$, there exists a positive integer $k$ such that $k\mathsf{SAT}$ requires $\Omega(2^{(1-\varepsilon)n})$ time.

$\mathsf{SETH}$ has been one of the biggest open problem in fine-grained complexity, and one of the reasons is that $\mathsf{SETH}$ being true would imply $\mathsf{P}\neq\mathsf{NP}$. See Section 1.2 for a detailed explanation of its significance and why many people believe that it is true.

We also introduce the Orthogonal Vectors problem, which is an important problem in fine-grained complexity and will be a key intermediate problem in some of our proofs.

###### Definition 2.5 (Orthogonal Vectors ( $\mathsf{OV}_{n,\ell}$ )) .

Given binary vectors $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\mathsf{OV}_{n,\ell}$ asks to determine if there exists a pair $i\neq j$ such that $\langle v_{i},v_{j}\rangle=0$.

Usually researchers focus on the regime when $\ell\ll n$, and thus we will assume that $\ell\leq n^{o(1)}$ throughout this paper. The straightforward algorithm for $\mathsf{OV}_{n,\ell}$ runs in time $O(n^{2}\ell)$ by simply computing the inner products between each pair of vectors. In very low dimensions, one can employ a folklore recursive approach to obtain a $O(2^{\ell}+n)$ time algorithm (see []). When $\ell=c\log n$ for a large constant $c$, all algorithms mentioned above require quadratic time with respect to $n$, but [, ] gave a slight improvement, showing that for a fixed constant $c>0$, $\mathsf{OV}_{n,c\log n}$ can be solved in time $n^{2-1/O(\log c)}$. This is a truly subquadratic running time for any fixed constant $c$, but becomes quadratic as $c$ grows. It is still unknown whether there exists a $O(n^{2-\varepsilon})$ time algorithm for all constant $c$, where $\varepsilon$ is an absolute constant that does not depend on $c$, and the popular $\mathsf{OVC}$ Conjecture states that no such algorithm exists.

###### Conjecture 2.6 ( $\mathsf{OVC}$ ) .

For any $\varepsilon>0$, there exists a constant $c>0$ such that $\mathsf{OV}_{n,c\log n}$ cannot be solved in $O(n^{2-\varepsilon})$ time.

[] showed that assuming $\mathsf{SETH}$ is true, then $\mathsf{OVC}$ is true (the other direction is unknown). Our paper will use these two conjectures interchangeably such that our hardness results can be obtained from either conjecture.

There is also a bichromatic version of $\mathsf{OV}_{n,\ell}$ where one is given two sets of vectors $A=\{a_{1},\ldots,a_{n}\},B=\{b_{1},\ldots,b_{n}\}$ such that $a_{i},b_{j}\in\{0,1\}^{\ell}$ and wants to determine if there exists $i,j$ such that $\langle a_{i},b_{j}\rangle=0$. In fact, these two problems are subquadratic equivalent.

###### Lemma 2.7 .

There exists an algorithm for $\mathsf{OV}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$ for some $\varepsilon>0$ if and only if there exists an algorithm for bichromatic $\mathsf{OV}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon^{\prime}}\cdot\operatorname{poly}(\ell))$ for some $\varepsilon^{\prime}>0$.

###### Proof.

First we assume that there exists an algorithm $\mathcal{A}$ for bichromatic $\mathsf{OV}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$ for some $\varepsilon>0$. Given an $\mathsf{OV}_{n,\ell}$ instance $V=\{v_{1},\ldots,v_{n}\}$ with $v_{i}\in\{0,1\}^{\ell}$ for all $i$, we first check if any $v_{i}$ is the all zero vector (if so then it is a yes instance). Otherwise, let $A=B=V$ and run $\mathcal{A}$ on $A,B$. Notice that since there is no all zero vector, $\langle v_{i},v_{i}\rangle\neq 0$ for all $i$, and therefore there exists $i\neq j$ such that $\langle v_{i},v_{j}\rangle=0$ if and only if there exists $v_{i}=a\in A,v_{j}=b\in B$ such that $\langle a,b\rangle=0$. The total running time is $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell)+n\ell)=O(n^{2-\varepsilon}
\cdot\operatorname{poly}(\ell))$.

Now we assume that there exists an algorithm $\mathcal{A}^{\prime}$ for $\mathsf{OV}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$ for some $\varepsilon>0$. Let $A=\{a_{1},\ldots,a_{n}\},B=\{b_{1},\ldots,b_{n}\}$ with vectors $a_{i},b_{j}\in\{0,1\}^{\ell}$ be a bichromatic $\mathsf{OV}_{n,\ell}$ instance. For each $a_{i}$ we construct $a_{i}^{\prime}=(a_{i},1,0)\in\mathbb{R}^{\ell+2}$ and for each $b_{j}$ we construct $b_{j}^{\prime}=(b_{j},0,1)\in\mathbb{R}^{\ell+2}$ and let $A^{\prime}=\{a_{1}^{\prime}\,\ldots,a_{n}^{\prime}\},B^{\prime}=\{b_{1}^{
\prime},\ldots,b_{n}^{\prime}\}$. Notice that now $\langle a_{i}^{\prime},a_{j}^{\prime}\rangle,\langle b_{i}^{\prime},b_{j}^{
\prime}\rangle\geq 1$ for all $i,j$. As a result, if there exists $\langle a_{i},b_{j}\rangle=0$, then $\langle a_{i}^{\prime},b_{j}^{\prime}\rangle=\langle a_{i},b_{j}\rangle+0=0$. Conversely, if $\langle v,w\rangle=0$ for any $v,w\in A^{\prime}\cup B^{\prime}$, then it must be the case that $v=a_{i}^{\prime}$ and $w=b_{j}^{\prime}$ for some $i,j$ or vice versa, which implies that $\langle a_{i},b_{j}\rangle=0$. Therefore, running $\mathcal{A}^{\prime}$ on $A^{\prime}\cup B^{\prime}$ will tell us whether $A,B$ is a yes instance or not. The total running time required is $O((2n)^{2-\varepsilon}\cdot\operatorname{poly}(\ell+2))=O(n^{2-\varepsilon}
\operatorname{poly}(\ell))$.
∎

When $\ell=c\log n$ for some constant $c>0$, an algorithm running in $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$ time for some fixed constant $\varepsilon>0$ is a truly subquadratic algorithm. Therefore, Lemma 2.7 implies that assuming $\mathsf{OVC}$, there is no truly subquadratic algorithm for bichromatic $\mathsf{OV}_{n,\ell}$.

###### Definition 2.4 (Strong Exponential Time Hypothesis ( 𝖲𝖤𝖳𝖧 𝖲𝖤𝖳𝖧 \mathsf{SETH} sansserif_SETH )) .

###### Definition 2.5 (Orthogonal Vectors ( 𝖮𝖵 n , ℓ subscript 𝖮𝖵 𝑛 ℓ \mathsf{OV}_{n,\ell} sansserif_OV start_POSTSUBSCRIPT italic_n , roman_ℓ end_POSTSUBSCRIPT )) .

###### Conjecture 2.6 ( 𝖮𝖵𝖢 𝖮𝖵𝖢 \mathsf{OVC} sansserif_OVC ) .

###### Lemma 2.7 .

###### Proof.

#### 2.2.2 Minimum Inner Product

In this section we introduce the minimum inner product problem, an important problem related to similarity search.

###### Definition 2.8 ( $\mathsf{Min}\text{-}\mathsf{IP}$ ) .

Given a set of binary vectors $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ asks to find one pair of $1\leq i,j\leq n,i\neq j$ such that $\langle v_{i},v_{j}\rangle$ is minimum.

The trivial algorithm for $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ takes $O(n^{2}\ell)$ time by enumerating all possible pairs of inner product. Sometimes we are happy with finding a pair of vectors whose inner product is close enough to optimal, so we also introduce the approximate $\mathsf{Min}\text{-}\mathsf{IP}$ problem as follows.

###### Definition 2.9 ( $\gamma\text{-}\mathsf{Min}\text{-}\mathsf{IP}$ ) .

Given a set of binary vectors $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\gamma\text{-}\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ asks to find one pair of $1\leq i,j\leq n,i\neq j$ such that $\langle v_{i},v_{j}\rangle$ is a $\gamma$-approximation of the minimal inner product.

It is not hard to see that $\mathsf{Min}\text{-}\mathsf{IP}$ and $\gamma\text{-}\mathsf{Min}\text{-}\mathsf{IP}$ are both at least as hard as $\mathsf{OV}$ for any $\gamma\geq 1$ (just find the minimum inner product and see if it is 0 0, and any multiplicative approximation of 0 0 must be 0 0). Therefore, assuming $\mathsf{OVC}$, for any $\varepsilon>0$ there exists $c>0$ such that $\mathsf{Min}\text{-}\mathsf{IP}_{n,c\log n}$ cannot be solved in $O(n^{2-\varepsilon})$ time.

In addition, there is a decision version of $\mathsf{Min}\text{-}\mathsf{IP}$, by which we denote $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell,t}$, where one wants to know whether there exists a pair of vectors whose inner product is at most $t$ for some $0\leq t\leq\ell$.

###### Definition 2.10 ( $\mathsf{Min}\text{-}\mathsf{IP}$ decision version) .

Given a set of binary vectors $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$ and $0\leq t\leq\ell$, $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell,t}$ asks to determine if there exists one pair of $1\leq i,j\leq n,i\neq j$ such that $\langle v_{i},v_{j}\rangle\leq t$.

$\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ is trivially at least as hard as $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell,t}$ for any $t$ because if we can calculate the minimum, then we can decide whether it is at most $t$ or not. In addition, notice that when $t\geq\ell+1$ or $t<0$ the problem is trivial and requires constant time to respond.

The bichromatic versions of these problems can be defined analogously: given two sets $A,B$ with vectors in $\{0,1\}^{\ell}$, one needs to find $i,j$ that achieves (for bichromatic $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$) or approximates (for bichromatic $\gamma\text{-}\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$) the minimal $\langle a_{i},b_{j}\rangle$. One can easily obtain a truly subquadratic algorithm for all three problems above given a truly subquadratic algorithm for their bichromatic versions.

###### Lemma 2.11 .

Suppose there exists an algorithm $\mathcal{A}$ for bichromatic $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$ for any $\varepsilon>0$, then there exists an algorithm for $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon^{\prime}}\cdot\operatorname{poly}(\ell))$ for some $\varepsilon^{\prime}>0$. The same statement is true for $\gamma\text{-}\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ and $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell,t}$.

###### Proof.

Given a $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ instance $V=\{v_{1},\ldots,v_{n}\}$, we first partition $V$ into $V_{1},V_{2}$ of equal size and run $\mathcal{A}$ on $V_{1},V_{2}$. This will allow us to find the minimal pair in $V_{1}\times V_{2}$. Now we further partition $V_{1}$ into two sets of equal size and recurse on $V_{1}$ to eventually find the minimal pair in $V_{1}\times V_{1}$. Similarly we recurse on $V_{2}$ to find the minimal pair in $V_{2}\times V_{2}$. The running time of our algorithm is

$$ $\operatorname{poly}(\ell)\cdot\sum_{i=1}^{\log n}O\Big{(}\Big{(}\frac{n}{2^{i} }\Big{)}^{(2-\varepsilon)}\Big{)}=O(n^{2-\varepsilon}\cdot\operatorname{poly}( \ell)\cdot\log n)\leq O(n^{2-\varepsilon^{\prime}}\cdot\operatorname{poly}( \ell))$ $$

for some $\varepsilon^{\prime}>0$. The exact same argument holds for $\gamma\text{-}\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell}$ as well because the minimal pair must appear in some recursion where we run our algorithm on. The argument also holds for $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell,t}$ because we have gone over all possible pairs of vectors.
∎

###### Definition 2.8 ( 𝖬𝗂𝗇 ⁢ - ⁢ 𝖨𝖯 𝖬𝗂𝗇 - 𝖨𝖯 \mathsf{Min}\text{-}\mathsf{IP} sansserif_Min - sansserif_IP ) .

###### Definition 2.9 ( γ ⁢ - ⁢ 𝖬𝗂𝗇 ⁢ - ⁢ 𝖨𝖯 𝛾 - 𝖬𝗂𝗇 - 𝖨𝖯 \gamma\text{-}\mathsf{Min}\text{-}\mathsf{IP} italic_γ - sansserif_Min - sansserif_IP ) .

###### Definition 2.10 ( 𝖬𝗂𝗇 ⁢ - ⁢ 𝖨𝖯 𝖬𝗂𝗇 - 𝖨𝖯 \mathsf{Min}\text{-}\mathsf{IP} sansserif_Min - sansserif_IP decision version) .

###### Lemma 2.11 .

###### Proof.

#### 2.2.3 Maximum Inner Product

In this section we introduce the maximum inner product problem and its variants. The problems are basically the same as problems in the previous section.

###### Definition 2.12 ( $\mathsf{Max}\text{-}\mathsf{IP}$ ) .

Given a set of binary vectors $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell}$ asks to find one pair of $1\leq i,j\leq n,i\neq j$ such that $\langle v_{i},v_{j}\rangle$ is maximal.

###### Definition 2.13 ( $\gamma\text{-}\mathsf{Max}\text{-}\mathsf{IP}$ ) .

Given a set of binary vectors $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\gamma\text{-}\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell}$ asks to find one pair of $1\leq i,j\leq n,i\neq j$ such that $\langle v_{i},v_{j}\rangle$ is a $\gamma$-approximation of the maximal inner product.

###### Definition 2.14 ( $\mathsf{Max}\text{-}\mathsf{IP}$ decision version) .

Given a set of binary vectors $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell,t}$ asks to determine if there exists one pair of $1\leq i,j\leq n,i\neq j$ such that $\langle v_{i},v_{j}\rangle\geq t$.

The bichromatic versions of these problems can be defined analogously. Similar to $\mathsf{Min}\text{-}\mathsf{IP}$, one can easily obtain a truly subquadratic algorithm for all three problems above given a truly subquadratic algorithm for their bichromatic versions again using the proof of Lemma 2.11.

###### Lemma 2.15 .

Suppose there exists an algorithm $\mathcal{A}$ for bichromatic $(\gamma\text{-})\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$ for any $\varepsilon>0$, then there exists an algorithm for $(\gamma\text{-})\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon^{\prime}}\cdot\operatorname{poly}(\ell))$ for some $\varepsilon^{\prime}>0$.

It is less obvious whether $\mathsf{Max}\text{-}\mathsf{IP}$ is a harder problem than $\mathsf{OV}$ or not. The answer is positive, and for bichromatic $\mathsf{Max}\text{-}\mathsf{IP}$, there exists a simple proof.

###### Lemma 2.16 .

Suppose there exists an algorithm $\mathcal{A}$ for bichromatic $\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$ for any $\varepsilon>0$, then there exists an algorithm for $\mathsf{OV}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$.

###### Proof.

Given an $\mathsf{OV}_{n,\ell}$ instance $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, we partition all $v_{i}$ into subsets $S_{1},\ldots,S_{\ell}$ such that each $S_{j}$ contains all vectors with $j$ ones. Now for each pair of $1\leq i,j\leq\ell$, let $\bar{S}_{j}$ consists of vectors in $S_{j}$ but with all the entries flipped. As a result, for any $v\in S_{i},w\in\bar{S}_{j}$ we have $\langle v,w\rangle=i-\langle v,\bar{w}\rangle$, which implies that $\langle v,\bar{w}\rangle=0$ if and only if $\langle v,w\rangle=i$. Therefore, running $\mathcal{A}$ on $S_{i},\bar{S}_{j}$ will tell us whether there is an orthogonal pair of vectors in $S_{i}$ and $S_{j}$. The total running time is $O(\ell^{2}\cdot n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))=O(n^{2-
\varepsilon})\cdot\operatorname{poly}(\ell)$.
∎

In fact, [] proved a stronger statement which says that even approximate $\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell}$ is stronger than $\mathsf{OV}_{n,\ell}$ for some approximation factor.

###### Definition 2.12 ( 𝖬𝖺𝗑 ⁢ - ⁢ 𝖨𝖯 𝖬𝖺𝗑 - 𝖨𝖯 \mathsf{Max}\text{-}\mathsf{IP} sansserif_Max - sansserif_IP ) .

###### Definition 2.13 ( γ ⁢ - ⁢ 𝖬𝖺𝗑 ⁢ - ⁢ 𝖨𝖯 𝛾 - 𝖬𝖺𝗑 - 𝖨𝖯 \gamma\text{-}\mathsf{Max}\text{-}\mathsf{IP} italic_γ - sansserif_Max - sansserif_IP ) .

###### Definition 2.14 ( 𝖬𝖺𝗑 ⁢ - ⁢ 𝖨𝖯 𝖬𝖺𝗑 - 𝖨𝖯 \mathsf{Max}\text{-}\mathsf{IP} sansserif_Max - sansserif_IP decision version) .

###### Lemma 2.15 .

###### Lemma 2.16 .

###### Proof.

### 2.3 Document Similarity Problems

In this section we formally define the $\mathsf{MSD},\mathsf{LSD}$ problems that we will study. First we define the $\mathsf{MSD}$ variants, which are defined similarly to $\mathsf{Max}\text{-}\mathsf{IP}$ variants.

###### Definition 2.17 ( $\mathsf{MSD}$ ) .

Given $n$ document embeddings $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\mathsf{MSD}_{n,\ell}$ asks to find $1\leq i,j\leq n,i\neq j$ such that $\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|\cdot\|v_{j}\|}$ is the maximum. (^4^44In all versions of $\mathsf{MSD}$ and $\mathsf{LSD}$, we assume that there are no zero vectors.)

Even though $\mathsf{MSD}$ looks similar to $\mathsf{Max}\text{-}\mathsf{IP}$, notice that they are not the same problem because of normalization. For example, $v=(1,1,\ldots,1)\in\mathbb{R}^{\ell}$ and $w=(1,1,\ldots,1,0,\ldots,0)\in\mathbb{R}^{\ell}$ where $w$ has $\ell/2$ ones have a very large inner product but they might not be considered similar. In contrast, $v^{\prime}=(1,1,\ldots,1,0,\ldots,0)\in\mathbb{R}^{\ell}$ where $v^{\prime}$ has $10$ ones and $w^{\prime}=(0,1,\ldots,1,0,\ldots,0)\in\mathbb{R}^{\ell}$ where $w^{\prime}$ has $10$ ones have a inner product of $9$ but they are very similar in terms of cosine similarity.

###### Definition 2.18 ( $\gamma\text{-}\mathsf{MSD}$ ) .

Given $n$ document embeddings $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\gamma\text{-}\mathsf{MSD}_{n,\ell}$ asks to find $1\leq i^{*},j^{*}\leq n,i^{*}\neq j^{*}$ such that

$$ $\frac{1}{\gamma}\cdot\max_{1\leq i,j\leq n}\frac{\langle v_{i},v_{j}\rangle}{ \|v_{i}\|\cdot\|v_{j}\|}\leq\frac{\langle v_{i^{*}},v_{j^{*}}\rangle}{\|v_{i^{ *}}\|\cdot\|v_{j^{*}}\|}\leq\max_{1\leq i,j\leq n}\frac{\langle v_{i},v_{j} \rangle}{\|v_{i}\|\cdot\|v_{j}\|}.$ $$

###### Definition 2.19 ( $\mathsf{MSD}$ decision version) .

Given $n$ document embeddings $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\mathsf{MSD}_{n,\ell,t}$ asks to determine if there exists $1\leq i,j\leq n,i\neq j$ such that $\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|\cdot\|v_{j}\|}\geq t$.

It is not hard to see that $\gamma\text{-}\mathsf{MSD}_{n,\ell}$ and $\mathsf{MSD}_{n,\ell,t}$ are both easier than $\mathsf{MSD}$. In addition, notice that the number of possible $t$ can be considered as discrete because there could only be $O(\ell^{3})$ possible values of $\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|\cdot\|v_{j}\|}$. As a result, the existence of truly subquadratic time algorithm for $\mathsf{MSD}_{n,\ell,t}$ for all $t\in[0,1]$ would imply a truly subquadratic time algorithm for $\mathsf{MSD}_{n,\ell}$ using binary search.

Bichromatic versions of these problems can be defined analogously and the proof of Lemma 2.11 again tells us that bichromatic versions are harder.

We also formally define $\mathsf{LSD}$ variants, which are defined similarly to $\mathsf{Min}\text{-}\mathsf{IP}$ variants.

###### Definition 2.20 ( $\mathsf{LSD}$ ) .

Given $n$ document embeddings $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\mathsf{LSD}_{n,\ell}$ asks to find $1\leq i,j\leq n,i\neq j$ such that $\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|\cdot\|v_{j}\|}$ is the minimum.

###### Definition 2.21 ( $\gamma\text{-}\mathsf{LSD}$ ) .

Given $n$ document embeddings $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\gamma\text{-}\mathsf{MSD}_{n,\ell}$ asks to find $1\leq i^{*},j^{*}\leq n,i^{*}\neq j^{*}$ such that

$$ $\min_{1\leq i,j\leq n}\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|\cdot\|v_{j} \|}\leq\frac{\langle v_{i^{*}},v_{j^{*}}\rangle}{\|v_{i^{*}}\|\cdot\|v_{j^{*}} \|}\leq\gamma\cdot\min_{1\leq i,j\leq n}\frac{\langle v_{i},v_{j}\rangle}{\|v_ {i}\|\cdot\|v_{j}\|}.$ $$

###### Definition 2.22 ( $\mathsf{LSD}$ decision version) .

Given $n$ document embeddings $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$, $\mathsf{LSD}_{n,\ell,t}$ asks to determine if there exists $1\leq i,j\leq n,i\neq j$ such that $\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|\cdot\|v_{j}\|}\leq t$.

$\gamma\text{-}\mathsf{LSD}_{n,\ell}$ and $\mathsf{LSD}_{n,\ell,t}$ are both easier than $\mathsf{LSD}$. In addition, the existence of truly subquadratic time algorithm for $\mathsf{LSD}_{n,\ell,t}$ for all $t$ again implies a truly subquadratic time algorithm for $\mathsf{LSD}_{n,\ell}$ using binary search. Bichromatic versions of these problems can be defined analogously and the proof of Lemma 2.11 again tells us that bichromatic versions are harder.

###### Definition 2.17 ( 𝖬𝖲𝖣 𝖬𝖲𝖣 \mathsf{MSD} sansserif_MSD ) .

###### Definition 2.18 ( γ ⁢ - ⁢ 𝖬𝖲𝖣 𝛾 - 𝖬𝖲𝖣 \gamma\text{-}\mathsf{MSD} italic_γ - sansserif_MSD ) .

###### Definition 2.19 ( 𝖬𝖲𝖣 𝖬𝖲𝖣 \mathsf{MSD} sansserif_MSD decision version) .

###### Definition 2.20 ( 𝖫𝖲𝖣 𝖫𝖲𝖣 \mathsf{LSD} sansserif_LSD ) .

###### Definition 2.21 ( γ ⁢ - ⁢ 𝖫𝖲𝖣 𝛾 - 𝖫𝖲𝖣 \gamma\text{-}\mathsf{LSD} italic_γ - sansserif_LSD ) .

###### Definition 2.22 ( 𝖫𝖲𝖣 𝖫𝖲𝖣 \mathsf{LSD} sansserif_LSD decision version) .

## 3 Hardness of Document Similarity

In this section, we show that assuming $\mathsf{SETH}$ or $\mathsf{OVC}$, for any $\varepsilon>0$, there exists a constant $c>0$ (only depends on $\varepsilon$) such that many variants of $\mathsf{LSD}_{n,c\log n},\mathsf{MSD}_{n,c\log n}$ require $O(n^{2-\varepsilon})$ time.

###### Theorem 3.1 .

Assuming $\mathsf{SETH}$ or $\mathsf{OVC}$, for every $\varepsilon>0$, there exists a constant $c>0$ such that $\gamma\text{-}\mathsf{LSD}_{n,\ell}$ cannot be solved in $O(n^{2-\varepsilon})$ time for any $\gamma\geq 1$ when $\ell=c\log n$.

###### Proof.

Assume by contradiction that there exists an algorithm $\mathcal{A}$ for $\gamma\text{-}\mathsf{LSD}_{n,c\log n}$ that runs in time $O(n^{2-\varepsilon})$ for some $\gamma\geq 1,\varepsilon>0$ and any constant $c>0$. We show that $\mathsf{OV}_{n,c\log n}$ can be solved in time $O(n^{2-\varepsilon})$ for any constant $c>0$, which refutes $\mathsf{OVC}$ and $\mathsf{SETH}$.

Given vectors $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$ where $\ell=c\log n$ for any constant $c$, if any vector is the zero vector (we can check in time $O(n\ell)$), then output yes. Otherwise we run $\mathcal{A}$ on $v_{1},\ldots,v_{n}$ to compute $i^{*},j^{*}$ such that

$$ $\min_{1\leq i,j\leq n}\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|\cdot\|v_{j} \|}\leq\frac{\langle v_{i^{*}},v_{j^{*}}\rangle}{\|v_{i^{*}}\|\cdot\|v_{j^{*}} \|}\leq\gamma\cdot\min_{1\leq i,j\leq n}\frac{\langle v_{i},v_{j}\rangle}{\|v_ {i}\|\cdot\|v_{j}\|}.$ $$

Observe that $\displaystyle\min_{1\leq i,j\leq n}\frac{\langle v_{i},v_{j}\rangle}{\|v_{i}\|
\cdot\|v_{j}\|}=0$ if and only if there exists a pair of orthogonal vectors, which implies that there exists a pair of orthogonal vectors if and only if $\mathcal{A}$ outputs a pair of orthogonal vectors. The total amount of time needed for $\mathsf{OV}_{n,\ell}$ is therefore $O(n\ell+n^{2-\varepsilon})=O(n^{2-\varepsilon})$, which refutes $\mathsf{SETH}$.
∎

Since $\gamma\text{-}\mathsf{LSD}_{n,\ell}$ is easier than $\mathsf{LSD}_{n,\ell}$ and bichromatic $\gamma\text{-}\mathsf{LSD}_{n,\ell}$, the same lower bound applies to these two problems as well. In addition, there must exist $t\in[0,1]$ such that $\mathsf{LSD}_{n,\ell,t}$ cannot be solved in $O(n^{2-\varepsilon})$ time when $\ell=c\log n$ because otherwise that would imply a $O(n^{2-\varepsilon})$ time algorithm for $\mathsf{LSD}_{n,\ell}$ using binary search.

###### Corollary 3.2 .

Assuming $\mathsf{SETH}$ or $\mathsf{OVC}$, for every $\varepsilon>0$, there exists a constant $c>0$ such that $\mathsf{LSD}_{n,d}$ cannot be solved in $O(n^{2-\varepsilon})$ time when $\ell\geq c\log n$. Moreover, the same lower bound holds for bichromatic $\gamma\textup{-}\mathsf{LSD}_{n,\ell}$ for all $\gamma\geq 1$ and $\mathsf{LSD}_{n,\ell,t}$ for some $t\in[0,1]$.

A similar hardness result for $\gamma\textup{-}\mathsf{MSD}_{n,d}$ can be derived with much more complicated techniques. Our proof follows the same idea as Theorem 6.1 of [] which uses graph constructions, and we delay the proof of Theorem 3.3 to Appendix A.

###### Theorem 3.3 .

Assuming $\mathsf{SETH}$, for every $\varepsilon>0$, there exists a constant $c>0$ such that $\gamma\textup{-}\mathsf{MSD}_{n,\ell}$ cannot be solved in $O(n^{2-\varepsilon})$ time when

$$ $\ell\geq(\log n)^{\frac{c\log n}{(\log\log n)^{2}}}\textup{ and }\gamma\leq \Big{(}1+\frac{1}{\log\log n}\Big{)}^{\frac{\log n}{(\log\log n)^{2}}}.$ $$

Similarly, the hardness result also applies to harder problems including $\mathsf{MSD}_{n,\ell}$ and bichromatic $\gamma\textup{-}\mathsf{MSD}_{n,\ell}$.

###### Corollary 3.4 .

Assuming $\mathsf{SETH}$ or $\mathsf{OVC}$, for every $\varepsilon>0$, there exists a constant $c>0$ such that $\mathsf{MSD}_{n,\ell}$ cannot be solved in $O(n^{2-\varepsilon})$ time when $\ell\geq(\log n)^{\frac{c\log n}{(\log\log n)^{2}}}$. Moreover, the same lower bound holds for bichromatic $\gamma\textup{-}\mathsf{MSD}_{n,\ell}$ for all $1\leq\gamma\leq(1+\frac{1}{\log\log n})^{\frac{\log n}{(\log\log n)^{2}}}$ and $\mathsf{MSD}_{n,\ell,t}$ for some $t\in[0,1]$.

###### Theorem 3.1 .

###### Proof.

###### Corollary 3.2 .

###### Theorem 3.3 .

###### Corollary 3.4 .

## 4 Representational Strength of Transformers

So far we have seen multiple problems ($\mathsf{OV},\mathsf{Min}\text{-}\mathsf{IP},\mathsf{Max}\text{-}\mathsf{IP}$ and variants of $\mathsf{MSD},\mathsf{LSD}$) that require quadratic time to solve under certain parameters assuming $\mathsf{SETH}$ or $\mathsf{OVC}$. In this section, we show that $\mathsf{OV}$ and decision versions of $\mathsf{MSD},\mathsf{LSD}$ can be solved by a transformer with one attention unit.

Notice that fine-grained reduction does not trivially apply in representational strength of transformers, i.e. two problems might be subquadratic equivalent, but one problem solvable by transformers might not imply that the other one is also solvable by transformers. This is because many techniques that are simple to do on the word-RAM model (where one can do arithmetic operations, find the maximum/minimum over $n$ numbers in constant time) might not be easy to implement in parallel architectures like transformers.

To start with, we show that transformers are able to solve $\mathsf{OV}$ with appropriate parameters.

###### Theorem 4.1 .

A attention unit with input and output MLPs with parameters $d=\ell,d_{\textup{in}}=\ell,d_{\textup{out}}=1,m\geq\ell+1$ can solve $\mathsf{OV}_{n,\ell}$.

###### Proof.

Let $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$ be an $\mathsf{OV}_{n,\ell}$ instance; define $v_{n+1}:=0^{\ell}$ and $X\in\mathbb{R}^{(n+1)\times\ell}$ such that $X_{i,:}=v_{i}$ for all $i$. Since $m\geq\ell+1$, let $Q,K$ be arbitrary matrices such that $QK^{\top}=-3\log n\cdot I_{\ell}$ and $V\in\mathbb{R}^{\ell\times 1}$ be the all-one matrix. Let $A_{Q,K,V}$ denote this attention head, and $\varphi_{1}$ be the identity function.

Let $X$ be the input to the transformer with $A_{Q,K,V}$ as the only attention head. We claim that if there exists a pair $1\leq i\neq j\leq n$ such that $\langle v_{i},v_{j}\rangle=0$, then $A_{Q,K,V}(X)$ has an entry which is at least $\frac{1}{n+1}$, and otherwise all entries will be at most $\frac{1}{(n+1)^{1.5}}$. As a result, we can use the second MLP $\varphi_{2}$ to map $A_{Q,K,V}(X)$ to $1$ if any of its entry is at least $\frac{1}{n+1}$ and 0 0 otherwise (see Lemma B.1 for a formal proof of existence).

We can calculate that the $i$-th entry of $A_{Q,K,V}(X)$ is

$$ $\sum_{j=1}^{n}\frac{\exp(-3\log n\cdot\langle v_{i},v_{j}\rangle)}{\sum_{k=1}^ {n}\exp(-3\log n\cdot\langle v_{i},v_{k}\rangle)+1}=\frac{\sum_{j=1}^{n}n^{-3 \langle v_{i},v_{j}\rangle}}{\sum_{k=1}^{n}n^{-3\langle v_{i},v_{k}\rangle}+1}.$ $$

As a result, if there exists a pair $\langle v_{i^{*}},v_{j^{*}}\rangle=0$ with $1\leq i^{*},j^{*}\leq n$, then the $i^{*}$-th entry of $A_{Q,K,V}(X)$ can be lower bounded as

$$ $\frac{\sum_{j=1}^{n}n^{-3\langle v_{i},v_{j}\rangle}}{\sum_{k=1}^{n}n^{-3 \langle v_{i},v_{k}\rangle}+1}\geq\frac{n^{-3\langle v_{i^{*}},v_{j^{*}} \rangle}}{n+1}=\frac{1}{n+1}.$ $$

Otherwise, $\langle v_{i},v_{j}\rangle\geq 1$ for all $i,j$ and thus the $i$-th entry of $A_{Q,K,V}(X)$ is

$$ $\frac{\sum_{j=1}^{n}n^{-3\langle v_{i},v_{j}\rangle}}{\sum_{k=1}^{n}n^{-3 \langle v_{i},v_{k}\rangle}+1}\leq\sum_{j=1}^{n}\frac{1}{n^{3\langle v_{i},v_{ j}\rangle}}\leq n\cdot\frac{1}{n^{3}}<\frac{1}{n^{1.5}}.$ $$

∎

Now we show that transformers can solve $\mathsf{Max}\text{-}\mathsf{IP}$ and $\mathsf{Min}\text{-}\mathsf{IP}$.

###### Theorem 4.2 .

A attention unit with input and output MLPs with parameters $d=\ell,d_{\textup{in}}=\ell+1,d_{\textup{out}}=1,m\geq\ell+1$ can solve $\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell,t}$ and $\mathsf{Min}\text{-}\mathsf{IP}_{n,\ell,t}$ for $1\leq t\leq\ell$.

###### Proof.

Given a $\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell}$ instance $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$ and $V\in\mathbb{R}^{n\times\ell}$ such that $V_{i,:}=v_{i}$ for all $i$, let $x_{i}=(v_{i},1)\in\{0,1\}^{\ell+1}$ for all $i$, $x_{n+1}:=(0,\ldots,0,t+1)\in\mathbb{R}^{\ell+1}$ and $X\in\mathbb{R}^{(n+1)\times(\ell+1)}$ be such that $X_{i,:}=x_{i}$ for all $i$. Let $Q,K\in\mathbb{R}^{d_{\textup{in}}\times m}$ be such that $QK^{\top}=3\log n\cdot I_{d_{\textup{in}}}$, $V=(1,1,\ldots,1,0)\in\mathbb{R}^{\ell+1}$ and $A_{Q,K,V}$ denote this attention head.

We want to send $X$ to the attention head, which could be done by many ways given the input $V$. For example, we can add a “end token” (^5^55[] has a similar assumption.) to the $n$ documents that is always embedded into the vector $(0,\ldots,0,t+1)\in\mathbb{R}^{\ell}$. Then we can use a MLP to send $V$ to $X$ (see Lemma B.2 for a formal proof). Now we can check that the $i$-th entry of $A_{Q,K,V}(X)$ is

$$ $\sum_{j=1}^{n}\frac{\exp(3\log n\cdot\langle x_{i},x_{j}\rangle)}{\sum_{k=1}^{ n}\exp(3\log n\cdot\langle x_{i},x_{k}\rangle)+\exp(3(t+1)\log n)}\cdot\|v_{j} \|_{1}=\frac{\sum_{j=1}^{n}n^{3\langle x_{i},x_{j}\rangle}\cdot\|v_{j}\|_{1}}{ \sum_{k=1}^{n}n^{3\langle x_{i},x_{k}\rangle}+n^{3(t+1)}}.$ $$

Let $1\leq i^{*}\neq j^{*}\leq n$ be such that $\langle v_{i^{*}},v_{j^{*}}\rangle$ is the largest. Therefore, if $\langle v_{i^{*}},v_{j^{*}}\rangle\geq t$, then $\langle x_{i^{*}},x_{j^{*}}\rangle\geq t+1$, which means that

$$ $\frac{\sum_{j=1}^{n}n^{3\langle x_{i^{*}},x_{j}\rangle}\cdot\|x_{j}\|_{1}}{ \sum_{k=1}^{n}n^{3\langle x_{i^{*}},x_{k}\rangle}+n^{3(t+1)}}\geq\frac{n^{3 \langle x_{i^{*}},x_{j^{*}}\rangle}\cdot\|v_{j^{*}}\|_{1}}{\sum_{k=1}^{n}n^{3 \langle x_{i^{*}},x_{k}\rangle}+n^{3(t+1)}}\geq\frac{\|v_{j^{*}}\|_{1}}{n+1} \geq\frac{1}{n+1}.$ $$

On the other hand, if $\langle v_{i^{*}},v_{j^{*}}\rangle\leq t-1$, then $\langle x_{i^{*}},x_{j^{*}}\rangle\leq t$, which means

$$ $\frac{\sum_{j=1}^{n}n^{3\langle x_{i^{*}},x_{j}\rangle}\cdot\|v_{j}\|_{1}}{ \sum_{k=1}^{n}n^{3\langle x_{i^{*}},x_{k}\rangle}+n^{3(t+1)}}\leq\ell\cdot \frac{n\cdot n^{3t}}{n^{3(t+1)}}=\frac{\ell}{n^{2}}<\frac{1}{(n+1)^{1.5}}.$ $$

Therefore, we can use the second MLP $\varphi_{2}$ to map $A_{Q,K,V}(X)$ to $1$ if any of its entry is at least $\frac{1}{n+1}$ and 0 0 if all its entries are at most $\frac{1}{(n+1)^{1.5}}$ (see Lemma B.1 for a formal proof of existence).

The proof for $\mathsf{Min}\text{-}\mathsf{IP}$ is almost the same, except that we new let $QK^{\top}=-3\log n\cdot I_{d_{\textup{in}}}$ and $x_{n+1}=[0,\ldots,0,-(t+1)]\in\mathbb{R}^{\ell+1}$ instead. Now the $i$-th entry of $A_{Q,K,V}(X)$ is

$$ $\frac{\sum_{j=1}^{n}n^{-3\langle x_{i},x_{j}\rangle}\cdot\|v_{j}\|_{1}}{\sum_{ k=1}^{n}n^{-3\langle x_{i},x_{k}\rangle}+n^{-3(t+1)}}.$ $$

Let $i^{*},j^{*}$ be such that $\langle x_{i^{*}},x_{j^{*}}\rangle$ is the smallest. Therefore, if $\langle v_{i^{*}},v_{j^{*}}\rangle\leq t$, then $\langle x_{i^{*}},x_{j^{*}}\rangle\leq t+1$, which means that

$$ $\frac{\sum_{j=1}^{n}n^{-3\langle x_{i^{*}},x_{j}\rangle}\cdot\|v_{j}\|_{1}}{ \sum_{k=1}^{n}n^{-3\langle x_{i^{*}},x_{k}\rangle}+n^{-3(t+1)}}\geq\frac{n^{-3 \langle x_{i^{*}},x_{j^{*}}\rangle}}{\sum_{k=1}^{n}n^{-3\langle x_{i^{*}},x_{k }\rangle}+n^{-3(t+1)}}\geq\frac{1}{n+1}.$ $$

On the other hand, if $\langle v_{i^{*}},v_{j^{*}}\rangle\geq t+1$, then $\langle x_{i^{*}},x_{j^{*}}\rangle\geq t+2$, which means

$$ $\frac{\sum_{j=1}^{n}n^{-3\langle x_{i^{*}},x_{j}\rangle}\cdot\|v_{j}\|_{1}}{ \sum_{k=1}^{n}n^{-3\langle x_{i^{*}},x_{k}\rangle}+n^{-3(t+1)}}\leq\ell\cdot \frac{n\cdot n^{-3(t+2)}}{n^{-3(t+1)}}=\frac{\ell}{n^{2}}<\frac{1}{(n+1)^{1.5}}.$ $$

∎

Finally, we show that transformers can solve decision versions of document similarity problems.

###### Theorem 4.3 .

A attention unit with input and output MLPs with parameters $d=\ell,d_{\textup{in}}=\ell+1,d_{\textup{out}}=1,m\geq\ell+1$ can solve $\mathsf{MSD}_{n,\ell,t}$ and $\mathsf{LSD}_{n,\ell,t}$ for any $t\in[0,1]$.

###### Proof.

When $t=0$ the problem is trivial so we simply need to output $1$ using MLPs, so without losing of generality we assume $t\neq 0$. Given a $\mathsf{MSD}_{n,\ell}$ instance $v_{1},\ldots,v_{n}\in\{0,1\}^{\ell}$ and $V\in\mathbb{R}^{n\times\ell}$ such that $V_{i,:}=v_{i}$ for all $i$, let $x_{i}=(\frac{v_{i}}{\|v_{i}\|_{1}},1)\in\mathbb{R}^{\ell+1}$ for all $i$, $x_{n+1}:=(0,\ldots,0,t+1)\in\mathbb{R}^{\ell+1}$ and $X\in\mathbb{R}^{(n+1)\times(\ell+1)}$ be such that $X_{i,:}=x_{i}$ for all $i$. Let $Q,K\in\mathbb{R}^{d_{\textup{in}}\times m}$ be such that $QK^{\top}=3\log n\cdot I_{d_{\textup{in}}},V=(1,1,\ldots,1,0)\in\mathbb{R}^{
\ell+1}$ and $A_{Q,K,V}$ denote this attention head.

Since $\mathsf{MSD}$ is exactly $\mathsf{Max}\text{-}\mathsf{IP}$ after we normalize the document embeddings, the proof of Theorem 4.2 implies that it suffices to send $X$ to the attention head. See Lemma B.3 for a construction.

The proof for $\mathsf{LSD}$ is exactly the same as the proof for $\mathsf{Min}\text{-}\mathsf{IP}$ after applying the $\varphi_{1}$ construced in Lemma B.3.
∎

###### Theorem 4.1 .

###### Proof.

###### Theorem 4.2 .

###### Proof.

###### Theorem 4.3 .

###### Proof.

## 5 Acknowledgements

The authors would like to thank Daniel Hsu, Jingwen Liu and Clayton Sanford for useful discussions.

## Appendix A Proof of Theorem 3.3

In this section we prove Theorem 3.3. Recall the theorem as follows.

###### Theorem A.1 ( Theorem 3.3 ) .

Assuming $\mathsf{SETH}$ or $\mathsf{OVC}$ and $\gamma\leq(1+\frac{1}{\log\log n})^{\frac{\log n}{(\log\log n)^{2}}}=2^{(\log n
)^{1-o(1)}}$, for every $\varepsilon>0$ there exists a constant $c>0$ such that there is no algorithm for $\gamma\text{-}\mathsf{MSD}_{n,\ell}$ that runs in time $O(n^{2-\varepsilon})$ where $\ell=(\log n)^{\frac{c\log n}{(\log\log n)^{2}}}$.

We break down the proof into several lemmas below.

###### Lemma A.2 .

Suppose there exists an algorithm for $\gamma\text{-}\mathsf{MSD}_{n,\ell}$ where $\ell=(\log n)^{\frac{c\log n}{(\log\log n)^{2}}}$ for any constant $c>0$, $\gamma\leq(1+\frac{1}{\log\log n})^{\frac{\log n}{(\log\log n)^{2}}}$ that runs in $O(n^{2-\varepsilon})$ time for any $\varepsilon>0$, then there exists an algorithm for $(1+\frac{1}{\log\log n})\text{-}\mathsf{MSD}_{n,(\log n)^{k}}$ with running time $O(n^{2-\varepsilon})$ for any constant $k>0$.

###### Proof.

Let $v_{1},\ldots,v_{n}\in\{0,1\}^{(\log n)^{k}}$ be an instance of $(1+\frac{1}{\log\log n})\text{-}\mathsf{MSD}_{n,(\log n)^{k}}$ for any constant $k>0$. Construct $V^{\prime}=\{v_{1}^{\otimes q},\ldots,v_{n}^{\otimes q}\}$ for $q=\frac{\log n}{(\log\log n)^{2}}$: all the vectors in $V^{\prime}$ have dimension $(\log n)^{kq}=(\log n)^{\frac{k\log n}{(\log\log n)^{2}}}$, so we can run the algorithm provided to find a $\gamma$-approximation of $\mathsf{MSD}$ on $V^{\prime}$ for some $\gamma\leq(1+\frac{1}{\log\log n})^{q}$. Notice that we have

$$ $\frac{\langle v_{i}^{\otimes q},v_{j}^{\otimes q}\rangle}{\|v_{i}^{\otimes q} \|\cdot\|v_{j}^{\otimes q}\|}=\Big{(}\frac{\langle v_{i},v_{j}\rangle}{\|v_{i} \|\cdot\|v_{j}\|}\Big{)}^{q}$ $$

for any $i,j$, so an $\gamma$-approximation of $\mathsf{MSD}$ on $V^{\prime}$ is a $\gamma^{1/q}=(1+\frac{1}{\log\log n})$ approximation of $\mathsf{MSD}$ on $v_{1},\ldots,v_{n}$.
∎

Now we define the bichromatic $\gamma\text{-Additive-}\mathsf{MSD}$ problem as: given a $A,B\subseteq\{0,1\}^{\ell},\alpha\in[0,1]$ with $|A|=|B|=n$, we want to distinguish between the following two cases:

- 1.
Yes instance: There exists $(a,b)\in A\times B$ such that $\frac{\langle a,b\rangle}{\|a\|\cdot\|b\|}\geq\alpha$.
- 2.
No instance: For every $(a,b)\in A\times B$ we have $\frac{\langle a,b\rangle}{\|a\|\cdot\|b\|}<\alpha-\gamma$.

###### Lemma A.3 .

Suppose there exists an algorithm $\mathcal{A}$ for $(1+\frac{1}{\log\log n})\text{-}\mathsf{MSD}_{n,(\log n)^{k}}$ for any constant $k>0$ with $O(n^{2-\varepsilon})$ running time, then there exists an algorithm for bichromatic $\frac{\log n}{\ell}\textup{-Additive-}\mathsf{MSD}_{n,c\log n}$ for any $c>0$ in time $O(n^{2-\varepsilon^{\prime}})$ for some $\varepsilon^{\prime}>0$.

###### Proof.

The proof follows from Theorem A.4 and Lemma A.5 below, where Theorem A.4 shows that the lemma statement is true if we replace $\frac{\log n}{\ell}\textup{-Additive-}\mathsf{MSD}_{n,c\log n}$ by $(\log n)\textup{-Additive-}\mathsf{Max}\text{-}\mathsf{IP}_{n,c\log n}$ and Lemma A.5 shows that these two problems are subquadratic equivalent.
∎

###### Theorem A.4 ( [ 46 ] Theorem 6.2) .

Suppose there exists an algorithm for $(1+\frac{1}{\log\log n})\textup{-}\mathsf{MSD}_{n,(\log n)^{k}}$ for any constant $k>0$ that runs in $O(n^{2-\varepsilon})$ time for any $\varepsilon>0$, then there exists an algorithm for bichromatic $(\log n)\textup{-Additive-}\mathsf{Max}\text{-}\mathsf{IP}_{n,c\log n}$ for any constant $c>0$ that runs in $O(n^{2-\varepsilon^{\prime}})$ time for some $\varepsilon^{\prime}>0$.

###### Lemma A.5 .

Bichromatic $\frac{\log n}{\ell}\textup{-Additive-}\mathsf{MSD}_{n,\ell}$ with $\ell=O(\log n)$ and bichromatic $(\log n)\textup{-Additive-}\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell^{\prime}}$ with $\ell^{\prime}=O(\log n)$ are subquadratic equivalent.

###### Proof.

Given a bichromatic $(\log n)\textup{-Additive-}\mathsf{Max}\text{-}\mathsf{IP}_{n,\ell}$ instance with sets $A=\{a_{1},\ldots,a_{n}\},B=\{b_{1},\ldots,b_{n}\}$ and integer $\alpha$, we construct $A^{\prime}=\{a_{1}^{\prime},\ldots,a_{n}^{\prime}\},B^{\prime}=\{b_{1}^{\prime
},\ldots,b_{n}^{\prime}\}$ as follows: for each $a_{i}$ we first attach $\ell-\|a_{i}\|_{1}$ many ones at the end and another $\ell+\|a_{i}\|_{1}$ zeros to obtain $a_{i}^{\prime}\in\{0,1\}^{3\ell}$, and for each $b_{j}$ we first attach $\ell+\|b_{j}\|_{1}$ zeros at the end and another $\ell-\|b_{j}\|_{1}$ ones to obtain $b_{j}^{\prime}\in\{0,1\}^{3\ell}$. Now all $a_{i}^{\prime},b_{j}^{\prime}$ have $\ell$ many ones, and $\langle a_{i}^{\prime},b_{j}^{\prime}\rangle=\langle a_{i},b_{j}\rangle$ for all $i,j$ by our construction. Therefore, running our algorithm for $\frac{\log n}{\ell}\textup{-Additive-}\mathsf{MSD}_{n,\ell}$ on $A^{\prime},B^{\prime}$ and $\frac{\alpha}{\ell}$ will tell us whether:

- 1.
there exists $(a^{\prime},b^{\prime})\in A^{\prime}\times B^{\prime}$ such that $\frac{\langle a^{\prime},b^{\prime}\rangle}{\|a^{\prime}\|\cdot\|b^{\prime}\|}
\geq\frac{\alpha}{\ell}$, which is equivalent to $\langle a,b\rangle=\langle a^{\prime},b^{\prime}\rangle\geq\alpha$, or
- 2.
for every $(a^{\prime},b^{\prime})\in A^{\prime}\times B^{\prime}$ we have $\frac{\langle a^{\prime},b^{\prime}\rangle}{\|a^{\prime}\|\cdot\|b^{\prime}\|}
<\frac{\alpha}{\ell}-\frac{\log n}{\ell}$, which is equivalent to $\langle a,b\rangle=\langle a^{\prime},b^{\prime}\rangle<\alpha-\log n$ for all $a\in A,b\in B$.

The running time of our algorithm is $O(n^{2-\varepsilon}\cdot\operatorname{poly}(3\ell))=O(n^{2-\varepsilon}\cdot
\operatorname{poly}(\ell))$.

The reduction for the other direction is similar. Suppose we are given a bichromatic $\frac{\log n}{\ell}\textup{-Additive-}\mathsf{MSD}_{n,\ell}$ instance with sets $A=\{a_{1},\ldots,a_{n}\},B=\{b_{1},\ldots,b_{n}\}$ and $\alpha\in[0,1]$, we construct the exact same $A^{\prime},B^{\prime}$ as before such that $\langle a_{i}^{\prime},b_{j}^{\prime}\rangle=\langle a_{i},b_{j}\rangle$ for all $i,j$. Since $\|a_{i}^{\prime}\|=\|b_{j}^{\prime}\|=\sqrt{\ell}$ for all $i,j$ now, the same argument implies that running the algorithm on $A^{\prime},B^{\prime}$ and $\alpha\cdot\ell$ will solve the problem in time $O(n^{2-\varepsilon}\cdot\operatorname{poly}(\ell))$.
∎

###### Lemma A.6 ( [ 21 ] ) .

Suppose there exists an algorithm for $(\log n)\textup{-Additive-}\mathsf{BMax}\text{-}\mathsf{IP}_{n,c\log n}$ for any constant $c>0$ running in time $O(n^{2-\varepsilon^{\prime}})$ for some $\varepsilon^{\prime}>0$, then there exists an algorithm for $\mathsf{OV}_{n,c^{\prime}\log n}$ for any constant $c^{\prime}>0$ with running time $O(n^{2-\frac{\varepsilon^{\prime}}{2}})$, thus refuting $\mathsf{SETH}$ and $\mathsf{OVC}$.

###### Proof of Theorem 3.3 .

This follows from a combination of Lemma  A.2, Lemma  A.3, Lemma  A.5 and Lemma  A.6.
∎

###### Theorem A.1 ( Theorem 3.3 ) .

###### Lemma A.2 .

###### Proof.

###### Lemma A.3 .

###### Proof.

###### Theorem A.4 ( [ 46 ] Theorem 6.2) .

###### Lemma A.5 .

###### Proof.

###### Lemma A.6 ( [ 21 ] ) .

###### Proof of Theorem 3.3 .

## Appendix B MLP Constructions

###### Lemma B.1 .

For any $a,b\in\mathbb{R}$ such that $b>a$, there exists a continuous function $f:\mathbb{R}^{\ell}\rightarrow\mathbb{R}$ such that

$$ $f(x)=\begin{cases}1&\textup{if }x[i]\geq b\textup{ for any }1\leq i\leq\ell\\ 0&\textup{if }x[i]<a\ \forall 1\leq i\leq\ell.\end{cases}$ $$

###### Proof.

Firstly we define $g:\mathbb{R}$ such that

$$ $g(x)=\begin{cases}1&\textup{if }x\geq b\\ \frac{1}{b-a}(x-a)&\textup{if }a\leq x<b\\ 0&\textup{if }x<a.\end{cases}$ $$

Now we let

$$ $f(x)=1-\prod_{i=1}^{\ell}(1-g(x[i])).$ $$

It is not hard to see that $g$ is a continuous function, and therefore $f$ is a continuous function. When $x[i]\geq b$ for any $1\leq i\leq\ell$, $g(x[i])=1$ and therefore $f(x)=1-0=1$. On the other hand, if $x[i]<a$ for all $i$, then $f(x)=1-1=0$.
∎

###### Lemma B.2 .

There exists a continuous function $f:\mathbb{R}^{\ell}\rightarrow\mathbb{R}^{\ell+1}$ such that

$$ $f(x)=\begin{cases}(x,1)&\textup{if }x[\ell]\leq 1\\ (0,x)&\textup{otherwise}.\end{cases}$ $$

###### Proof.

First we define a function $g:\mathbb{R}\rightarrow\mathbb{R}$ such that

$$ $g(x)=\begin{cases}1&\textup{if }x\leq 1\\ 2-x&\textup{if }1<x\leq 2\\ 0&\textup{if }x>2,\end{cases}$ $$

and we also define $f_{1},f_{2}:\mathbb{R}^{\ell}\rightarrow\mathbb{R}^{\ell+1}$ where

$$ $f_{1}(x)=(x,1),f_{2}(x)=(0,x).$ $$

It is not hard to see that $g,f_{1},f_{2}$ are all continuous functions, so we let

$$ $f(x)=g(x[\ell])\cdot f_{1}(x)+(1-g(x[\ell]))\cdot f_{2}(x)$ $$

such that $f$ is also continuous. We can check that $f$ satisfies the requirement in the lemma statement.
∎

###### Lemma B.3 .

There exists a continuous function $f:\mathbb{R}^{\ell}\rightarrow\mathbb{R}^{\ell+1}$ such that

$$ $f(x)=\begin{cases}(\frac{x}{\|x\|_{1}},1)&\textup{if }x[d]\leq 1\\ (0,\frac{x}{\|x\|_{1}})&\textup{otherwise.}\end{cases}$ $$

###### Proof.

Let $g$ be the same functions as in Lemma B.2 and $f_{1},f_{2}:\mathbb{R}^{\ell}\rightarrow\mathbb{R}^{\ell+1}$ where

$$ $f_{1}(x)=\Big{(}\frac{x}{\|x\|_{1}},1\Big{)},f_{2}(x)=\Big{(}0,\frac{x}{\|x\|_ {1}}\Big{)}.$ $$

$f_{1},f_{2}$ are continuous function over $\mathbb{R}^{\ell}$, and therefore we let

$$ $f(x)=g(x[\ell])\cdot f_{1}(x)+(1-g(x[\ell]))\cdot f_{2}(x)$ $$

such that $f$ is also continuous. We can check that $f$ satisfies the requirement in the lemma statement.
∎

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 .

###### Proof.

###### Lemma B.3 .

###### Proof.

## Peer Reviews

confidence: 1
contribution: 3
initial_rating: 6
presentation: 2
questions: For MSD and LSD, how relevant are your findings in practical applications, such as recommendation systems? Could varying values of sequence length $n$ and model parameters lead to different practical conclusions?
soundness: 2
strengths: Although this is not my area of expertise, I believe the paper's main findings, particularly regarding document similarity tasks, have the potential to impact the literature on architectural development. Additionally, to the best of my knowledge, the paper is well-written, the math is accurate and concise.
summary: This paper introduces a theoretical perspective on the ability of transformers to solve document similarity tasks. Specifically, by relying on the SETH conjecture, the paper connects complexity theory with transformers, and shows that subquadractic models cannot solve a class of problems that are solvable by transformers, which are quadractic.
weaknesses: While the theoretical coverage seems accurate to me, I was disappointed by the lack of empirical evidence supporting the paper's main findings. For instance, experiments demonstrating that subquadratic models cannot solve Max-IP, Min-IP, MSD, and LSD, whereas transformers can, would have been valuable.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. Can the results be enhanced to rank different subquadratic approximations?
2. Similarly, can the results be enhanced to quantify the gap between the quadratic transformers and the subquadratic approximations?
3. Are there approximate algorithms for solving the minimum inner product problem or its variants and how would these relate to the subquadratic approximations?
soundness: 2
strengths: The results are theoretical, demonstrating a fundamental limitation of any subquadratic approximations of the transformers' quadratic attention mechanisms. The involved steps seem sound.
summary: The paper studies a fundamental issue whether any subquadratic approximations to the transformers' quadratic attention mechanisms can solve perfectly the minimum inner product problem (or its variants (such as the maximum inner product one)) among a set of binary vectors. Built on results about the inherent complexity of such problems, the authors show that such problems can not be solved by any subquadratic approximations due to the complexity mismatch. They also show the problems can be solved by a transformer using the quadratic attention mechanisms by constructing such a network.
weaknesses: I believe the results, while rigorous and sound, have almost no connection with the transformers being used in practice. Generally speaking, the transformers are shown to be very capable of solving different kinds of problems empirically. For example, subquadratic approximations try to show that they can perform similarly to the original transformers but more efficiently, which is orthogonal to the results in the paper. Due to the nature of the results, there are no experimental results. But the variants of the transformers being used are mainly justified via results. Furthermore, it is known that at least some of the transformers (such as the decoder-only ones) can not solve counting and copying problems [1] perfectly and the additional impact of the results in the paper to the research on transformers may be very limited. 

[1] Federico Barbero, Andrea Banino, Steven Kapturowski, Dharshan Kumaran, Jo˜ao GM Ara´ujo, Alex Vitvitskyi, Razvan Pascanu, and Petar Veliˇckovi´c. Transformers need glasses! information oversquashing in language tasks. arXiv preprint arXiv:2406.04267, 2024 (also in NeurIPS 2024).

---

confidence: 5
contribution: 4
initial_rating: 8
presentation: 3
questions: - 259: finds
- 310: multi-layer
- 434 write the numbers explicitly, 'very large' is random here
- 534 left side v_i^*  (the star)
- line 529 as mentioned above
soundness: 3
strengths: Finally some more mathematically theoretically founded analysis of the prominent architecture and its limitations.
It analysis seems rigorous and its offering insights that can influence future research on alternative architectures in NLP.
summary: Attention is a computationally bottleneck of the prominent transformer models used for language modelling. The classic variant is in quadratic (on the input-dimension) complexity class, which is why sub-quadratic variants such as state-space models emerged, to enable e.g. longer document processing.
The authors claim that subquadratic alternatives to transformers face inherent limitations in performing specific NLP tasks, namely document similarity. Its contributions are theoretically based on complexity theory; namely, 1) the prominent SETH problam cannot be solved sub-quadratic, and 2) a constructed transformer can solve SETH.
weaknesses: minors/ missing discussions:

1.1) The paper would benefit from discussing the practical impacts of its findings. I.p. the bounds of its proof seem to be quite practically relevant and not 'entirely asymptotic' - in praxis it could be more relevant to have 'bad asymptotic with good bounds'.

1.2) It would be beneficial to explore the performance of alternative architectures i.p. w.r.t. practicability - i am not sure if a state space machine can't handle OVC in a reasonable depth like 10 layers. 

1.3) it would be beneficial to discuss a broader range of tasks

mediocores:

2.1) i find the main paper pretty hard to read and would advice a bit of restructering i.p.
- abstract line 22ff are quite redundant
- intro line 132ff seem pretty random/ not needed/ more distractive
- repetitively bichromatic versions are mentioned but not required in the core eg 2.2.1, 2.2.2, 2.3 -> i would love to see that in a final/following discussion sections once. Similarly Min/Max-IP are pretty confusing as not required for the main result -> discussion afterwards
- you define in 2.3 MSD, but actually require LSD for the core proof. that is one part that actually should be written explicitly twice (or the other version) :)

2.2) the core result is 4. it, and its impact should be discussed further, in particular recall what sub-quadratic methods suffer from.
the proof could use a rewrite. i.p.: 4.1. is a transformer from your definition (not just attention~...). i suffer a bit to understand the step 529: A_{Q,K,V}(X) IS NOT line 528, but it is upperbounded by it which is all you need (?) you miss the factors XV = in this construction #ones in v_i.. or did i miss something?

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 4
questions: > We focus on document similarity tasks, where one is given
as input many documents and would like to find a pair which is (approximately)
the most similar.

Could you please elaborate, why 'approximately' mentioned here? Is it not SETH and derived conjectures about exact results only?

> In other words, in order to perform tasks that (implicitly or explicitly) involve document similarity, one may as well use Transformer and cannot avoid its quadratic running time.

Approximate similarity search involves tradeoff precision and run time. If we talk about the exact solution of the similarity search, it would be nice to make it explicit.

> bag-of-words embeddings
How important is usage of bag of words embedding?  Would it be possible to use embedding / technique which takes into account word ?
soundness: 3
strengths: 1. General results on limitations on sub-quadratic  architecture or heuristic for most similar, least similar and related problems. Proved that accuracy loss for any task relating to document similarity is unavoidable for any sub-quadratic approach.
2. Shown that one head / one layer transformer can solve those tasks.  This includes explicit transformer construction.
3. Bringing complexity results (Strong Exponential Time Hypothesis) to transformer architectures.
summary: Paper is well written and brings interesting results from complexity theory to the deep learning community. It describes theoretical  limitations of sub-quadratic attention architectures for similarity and related problems. Paper shows that MSD, LSD and their variants require quadratic time assuming SETH and therefore any subquadratic alternatives to transformers are not able to solve them due to computational constraints. Also the paper explicitly constructs one head / one layer transformer which is able to solve such a problem, therefore making clear an important difference between standard attention and subquadratic alternatives.
weaknesses: 1. It is not exactly clear when the paper talks about approximate or exact results.
2. It relies on the BOW (bag of words) model, which already introduces approximation in practical settings. This makes results (which are about exact solution) weaker.
3. Considering that finding closest pairs in Euclidean or Manhattan distance both require quadratic time (assuming SETH) is well know, results for MSD, LSD are fairly incremental.

Meta-review: Reviewers agree that the paper considers an important problem of understanding the limitations of subquadratic alternatives to attention. However they disagree on the utility of the complexity theory based separation results shown in this paper. In particular the relation between hardness of solving MSD in subquadratic time and any practical tasks is missing. The recommendation system example given by authors is not convincing, as large scale practical systems do not uses quadratic computation for recommendations. Overall I think the paper is on borderline with interesting research direction, but missing connections to practice. I suggest acceptance in the hope that this encourages future works that builds these connections.

Decision: Accept (Poster)