Fundamental Limitations on Subquadratic Alternatives to Transformers
Authors: Josh Alman
Hantao Yu
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Models
Transformers
Fine-grained complexity theory
Document similarity
Hardness of Approximation
Fast attention computation
Primary area: foundation or frontier models, including LLMs

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.

Published as a conference paper at ICLR 2025
FUNDAMENTAL LIMITATIONS ON SUBQUADRATIC AL- TERNATIVES TO TRANSFORMERS
Josh Alman'
Hantao Yu"
Department of Computer Science Columbia University
Department of Computer Science Columbia University
New York, NY 10027, USA joshâcs col umbia edu
New York, NY 10027, USA hantao, yu@.ouuuuuuuub edu
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 tokens. Performing an attention computation takes quadratic time in the input size, and had become the time bottleneck for trans- former operations. 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 perform (assuming popular conjecture from fine-grained complexity theory). We focus on document similarity tasks, where one is given as input many documents and would like find 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 algo- rithm. Thus, any model which can be evaluated in subquadratic time- whether because of subquadratic-tinn 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, may well use Transformer and cannot avoid its quadratic running time.
heuristics for attention, faster attention replacements
INTRODUCTION
The Transformer architecture (Vaswani et al. 2017) is widely used for natural language processing (Devlin et al. 2019b Yang et al. 2019), computer vision (Dosovitskiy et al.) 2021 Carion et al. 2020). and many other tasks, and has achieved state-of-the-an performance for numerous appli- cations. At the core of the architecture is the attention mechanism which is designed to calculate the correlation between all pairs of tokens
given input sequence. Namely, let Q E &d be the query matrix, K Rddax be the key matrix and V E IR Xdu be the value matrix. Given X E Tandaa an attention mechanism computes
AQ.K.v = softmax (ootmax(XQK"") (QQ XX
where the softmax operator
exp(u(n))
softmax(v)
Σ exp(v(i))
for v E TR. 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 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.
denotes equal contribution

---

Published as a conference paper at ICLR 2025
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 (Zandieh et al., (023). Reformer (Kitaev et al. 2020), Hyperattention (Han et al.] 2024), Linformer (Wang al. 2020). SMYRF (Daras et al. 2020), and Performer (Choromanski et al. 2021). 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 (Beltagy et al. 2020), Synthesizer (Tay al.] (021), Routing transformers (Roy et al. (202T) and MAMBA (Gu & Dao 2023) 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 's calculation of token interactions with simpler alterna- tives, 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 new architecture, completely different approach, is inherently unable to perform important learning tasks that 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 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.
these new approaches.
1.1 DOCUMENT SIMILARITY
In this work we will be focusing on document similarity tasks. We will show that standard trans- formers are capable of solving these tasks but subquadratic alternatives to transformers cannot.
Document similarity is a fundamental area in natural language processing with many applica- tions including recommender systems (Ostendorfi) 2020), search engines (Mahdi al. 2018), and plagiarism-detection (Baba et al. 2017). For a given document D, we first need to define a docu- ment embedding to transform it into a vector e Rd 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 vector including Doc2Vec (Le & Mikolov [014), TF-IDF (Sparck Jones) 1988), BERT (Devlin et al. (2016)), bag-of-words (Harris) 1954). 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.
ofg-of-words Embedding. Bag-of-words embedding is a well-studied method of embedding (Blei et al. 2003) that is commonly used for text classification (Jin et al.) 2016). radiology (Ju- luru et al. 2021) and many other settings, especially in NLP. Given a document D and a list of key {0, 1)' such that the i-th entry of e corre- sponds to whether the i-th key word exists in D or not. [ For example, if a document only contains one sentence "There are ten apples on the apple tree" and the key words chosen "apple", "tree". "computer" and "ten", this document will have bag-of-wordd embedding (1, 1, 1).
words, the bag-of oar-offworrdd embedding of D is vector
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 Ed the cosine similarity is
Sometimes the entries are also frequency counts, but that would only make the embedding vectors more complex. Since our main goal is show hardness, we will focus the simpler binary case.
2

---

Published as a conference paper at ICLR 2025
given by
(u w)
[0.
1 1012
where represents complete similarity and 0 represents no similarity. It defined in this way, rather than just taking the inner product w)), 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, Manchez-Gomeet al. (202T) found that when used for extractive multi-document text summarization, cosine similarity gives the best results.
Problem Statement. We define our most similar document (MSD) and least similar document (LSD) problems as: given a set of n binary vectors ......, U/ of length d (document embeddings), the goal is to find two documents that are the most/least similar 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 MSD, LSD) Sometimes we have sets of documents A, B and want to find one document from each set such that the pair is (un)similar.
2. (y-MSD, 7-LSD) Sometimes we might only need to find a pair of documents that is ap- proximately the most (un)similar, (up to approximation factor y) and not necessarily the optimal pair.
3. (MSDn.d.t, LSD,,a.t) Sometimes we only want to know if there exists a pair whose cosine similarity is above (or below) threshold E [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 are given 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, such as in plagiarism detection and team matching.
1.2
MAIN RESULTS
Our hardness results are based on prevalent conjecture from fine-grand tineggraneed complexity theory called the Strong Exponential Time Hypothesis (SETH):
For every e >> 0, there is an integer k such that kSAT with n variables requires ((2(1-e)n) time.
SETH was first introduced by Impagliazzo & Paturi (2001) and is a popular strengthening of the conjecture that P & NP. (In other words, proving that SETH is true implies P * NP.) Since then, there has been a long line of work studying and making use of SETH. Prior work has given theo- retical evidence for SETH (Impagliazzo & Paturi 2001 Abboud al., 2018 Vassilevska Williams, 2015). and has used SETH to prove hardness of problems in many different areas of algorithm design. See the survey Williams (2018) for detailed background.
Main Results: Limitations of subquadratic alternatives. We show that MSD, LSD and their variants require quadratic time assuming SETH for some natural choice of parameters, and there- fore 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 l depending the details of the problem:
Theorem 1.1 (Theorem 3.1 and Corollary 3 Assuming SETH, for every >> O, there exists constant e > such that LSD,,e cannot be solved in O(n2=s) time when f. = clog n. Moreover, the same lower bound also holds for LSD,,,,t for some < t < 7-LSDn,f for any 7 1, and bichromatic LSD,,t-
Theorem 1.2 (Theorem 3.3 and Corollary 3.4.
Assuming SETH, for every > O, there exists constant e >> 0 such that MSD,. cannot be solved in (n²-=) time when n मिरंं Moreover, the same lower bound also holds for MSD,, for some 0 < t < and 7- -MSD,... n... for any 1 S 7 polylog(n).
For bichromatic MSD obtain a stronger hardness result.
3

---

Published as a conference paper at ICLR 2025
Theorem 1.3 (Theorem 3.3 and Corollary 3.4). Assuming SETH, for every > O. there exists constant e > such that bichromatic MSD,,e cannot be solved in O(n² time when f clog n.
In all these problems, we prove hardness when l (log n) or n2(1), This is a natural choice: for any smaller < log there could be at most 2 < vectors under bag-of-words embedding, which means that there would be duplicate vectors in our instance. Making larger can only make the problem harder.
follows that any language task which, either explicitly or implicitly, involves solving any of these document similarity problems, cannot be solved in subquadratic time when the input size is large enough, no matter what the parameters or architecture of the language model are
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 transformer model can solve it. For example, Sanford et al. (2024b) 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 lot of attention heads or very high embedding dimension.
We show that this not the case for MSD and LSD by showing that single standard attention unit with input and output MLPs can solve MSD n.d,t LSD and simpler version of MSD, the Orthogonal Vectors problem (OV), where one is given a set of binary vectors and needs determine if there exists pair of vectors that are orthogonal. Thus, these problems establish separation between standard transformers and subquadratic alternatives to transformers.
Theorem 1.4 (Theorems 4.1 and C.2 A single unit of standard attention with input and output MLPs, embedding dimension + can solve OVn.t and MSDn,,, L,t for any S St
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.
1.3 RELATED WORK
In recent years, several thcoretical and algorithmic aspects of transformers have been extensively studied. We diseuss next two aspects that are most relevant our work, and which we build 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 lim- itations, including not being able to model periodic finite-state languages hierarchical structure (Hahn) (2020), and not being able to recognize some counter languages without large depth (Bhat- tamishra al. 2020 On the other hand, transformers are able to recognize formal languages such as Dyck languages (Yao et al. 2021). simulate finite-state automata (Liu et al., 2023) with O n)
depth, and simulate Turing machines if given enough depth (Wei et al. [2024] Merrill & Sabhar- wal, 2024). There is also a line of work (Hao et al.) 2022] Merrill et al., 2022) that understands
what transformers can compute through the lens of circuit complexity; see Strobl et al. (004)) for comprehensive survey.
Another line of work has shown that transformers can compute particular problems of interest, in- cluding PARITY (which perceptrons are notably unable to compute) (Chiang & Cholak 2022) and learning problems that attention is particularly suited toward like "sparse averaging" and "k-hop induction heads" (Sanford et al. 2024a|b)
We briefly emphasize that the parameter E in these similarity problems need not be related to the architec- ture or parameters (like di., dour, etc) of language model which solves the prohlems. For instance, to ask language model solve MSD..,. we may ask it "Which of the following paragraphs is most similar?" followed by a list of n different paragraphs of at most E words each. Thus, input to the language model would be string of length (nne), and since f. <, (1) is small compared to n, our result shows that language model would need to take quadratic time in the string length answer this type of query.
4

---

Published as a conference paper at ICLR 2025
Faster attention mechanisms. As previously discussed. attention computation remains bottle- neck for efficiency, and many different approaches have been proposed to tackle this issue. These approaches typically result in accuracy loss (and 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 San- ford et al. (2024)). 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 (Kitaev et al. 2020; Roy et al., 2021 Daras et al.) 2020)
or low-rank matrices (Choromanski al.) [222]] Katharopoulos et al., 2020). Sanford al. (2024a) 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 more general than this, applying to any approach that runs in subquadratic time, rather than needing to focus on particular architec- ture or heuristic.
Fine-Grained Complexity and Machine Learning Fine-grained complexity theory has been suc- cessful proving conditional lower bounds for problems in diverse areas of algorithm design, such
as in graph theory (Abboud & Williams 2014:] Abboud et al., [2015a] Williams & Williams 2018)
and combinatorial optimization (Rubinstein) 2018; Alman al.) [2244: Künnemann et al. 2017
Backurs & Indyk] 2015). See (William (2018) for a detailed survey.
Recently, has been shown that many problems in machine learning are also inherently hard as- suming popular conjectures in fine-graines complexity. For example, Baakurrs et al.] (2017); [Alman & Guan (2024) use SETH to give a lower bound on the time to perform kernel density estimation, Hu et al. (2024a) use SETH to demonstrate a computational phase transition in modern Hopfield models, Hu al. 2024c) and Hu et al. (2024b) use SETH to characterize the computational limits of diffusion transformers and Low-Rank Adaptation for transformers respectively, and Duman Keles cct al. (2023); Alman & Song (2024) use SETH to give a lower bound on computational complexity of approximating the attention mechanism itself. We remark that results, together, give a new, alternate proof of the hardness of attention assuming SETH. Indeed, we prove that a single attention unit can solve MSD, and that MSD requires quadratic time assuming SETH, which together imply that evaluating the attention unit requires quadratic time.
Hardness of similarity search. Similarity search has been 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 (Indyk & Motwanil 1998) Andoni & Indyk] 20088] Andoni & Razenshteym
2015 Andoni et al., 2017 Tao et al. 2002]] Engels al. 2024| Uddin al. 2022 Gu al.) (219)]. Given a dataset P C RRd with n points, we want to preprocess it such that given a query point q E Rd. 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 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 [Saahnarovvich et al. (2006) for a complete overview).
There are many natural variants of the nearest neighbor problem, including the closest (furthest) pair problem where one is given dataset P and wants to find the two points from P that are the closest (furthest). This problem is exactly Min-IP(MMax-l)
if we let inner product be the measure of closeness. Under standard Euclidean distance, one can also express the distance between two points as |lp 411 || + || 2(p, 4) such that when all points have the same l norm, finding the closest pair is equivalent to finding the pair with the largest inner product, i.e. Max-IP. In fact, it has been shown that assuming SETH is true, finding closest pairs in Euclidean or Manhattan distance both require quadratic time (Alman & Williams 2015 Rubinstein 2018). We will use this in our
proofs below.
5

---

Published as a conference paper at ICLR 2025
2 PRELIMINARIES
Notation. For vector v, we use v|i] to denote its i-th entry for all For a matrix A, we use A to denote the i-th row of A and A. to denote the j-th column of A. Given a positive integer d, we use 1a E Idd to denote the vector whose entries are all 1. Given two vectors v E R E RR, use v & w E Rab to denote the Kronecker product of u and w (whose entries are all the products of an entry of and an entry of w) and to l2 norm unless otherwise specified. Given a binary vector v E {0,1] we use ö E {0, 1]d to denote the vector where all entries are flipped. The softmax operator, when given vector IR", outputs a vector in IR" given by
E Ro+h to denote the concatenation of and w. ||- refers
softmax(1) (expe(l)),..,exx(((u))))
Ei= exp(vli)
For matrices A E Raxx, we apply softmax operator rowewise, so that noftmax(A);; softmax(A..).
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 attention unit is di matrix where di is the input dimension and the output of a attention is a n. x dom matrix where daut is the output dimension.
Definition 2.1 (attention). For input dimension dm E N. ouput dimension dout N. embedding dimension m E N, matrices Q, K. E R x and V E Rdaxdd xdu,, a attention is a mapping AQ.K.V R I by
(x) soQt XXV..
We use Adg. (AQ.KV Q id K E Rdu xm V E Rddxddar 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 attention to illustrate representational strength (transformers with more layers and heads could only be stronger), so we omit the formal definitions of attention layers.
multi-layer perceptron (MIP) is a type of neural network that is used to learn nonlinear relation- ships in data. Mathematically, it is usually formulated as a neural network with different types of activation functions (Bartlett et al. 2017]] Montúfar et al. 2014] Jacot et al.) 2018) or sometimes as more specific threshold circuit (Maass et al. 1994)). Since the universal approximation theorem (Horiik et al. 1989) states that any continuous function with a finite support can be approximated by neural network with one hidden layer, (anford et al. (2024a b) modeled MLP as arbitrary func- tion Φ : IRd - Rd defined fixed-precision vectors, and we will notationally use that definition here.
Definition 2.2 (Multi-player perceptron). A multi- perceptron is represented by some continu- ous function P : Ra + Ih' for some positive integers a, b. We can apply y to a matrix row-wisely: given any matrix X RRax x(X) ((((X).....,
E 1Raxb.
That said, in our constructions in this paper, will suffice to use MLPs which are simple, piecewise-linear functions that fit in all the categories discussed above, and can be easily approxi- mated by a small neural network or any other MLP definition.
In this work, our transformer (with single attention unit) will be defined as 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 (Devlin et al. 2019a), GPT-3 Brown et al. (2020), GPT- (OpenAll 2023) and is typically used in theoretical work on simple transformers (Phuong & Hutter 2022 Sanford et al. 2024a b).
Recall in particular that we will be designing such transformers for document similarity problems.
In this case, given documents Di,..., Da, we will let their bag-of-words embeddings
(BOW(D)).... ... BOW(D.)) E R

---

Published as a conference paper at ICLR 2025
be the input to transformer, and the output of the transformer will be real number indicating the answer to our problems.
Definition 2.3. A transformer is a mapping TF Ruxd + and two MLPs ip1 : Baxdo 1p2 Raxdon R. Upon an embedding matrix E E Ruudd the transformer outputs 92 (2(Axxv(P)(E)))
R specified by a attention unit AQ...v
To emphasize, this very simplified model of transformer with single attention unit. We say that a transformer TF solves a problem whose input is matrix F E R if TF(E) is the answer of the problem on instance E. For example, for decision problems like MSDn.d,t we say TF solves MSD,, n.d,t if for all input V1, ................................ Cn and E' such that Es: U, for all i, TF(B)= = 1 if there exists pair (ez.0g)
|o:: 15ll 2 t and TF F)) = O otherwise.
2.2 TINE-GRAINED COMPLEXITY
We first introduce some common notions from fine-grained complexity. Many proof' in this sec- tion are deferred to Appendix A and we also refer the reader to Appendix A for a more detailed introduction to fine-grained complexity.
In fine-gratn ree-ggained complexity, one is usually interested in whether we can improve the running time of algorithms by a polynomial factor. For example, the OV problem (defined below) has straight- forward quadratic time (ignoring logarithmic factors) algorithm, and it is a major open problem to determine whether there exists faster, 1n.1.99) time algorithm. We say that algorithm is truly F if it runs in time O(n²-e) for some constant e > O. In this work, all our problems have quadratic time solutions, and we are interested in whether truly subquadratic time algorithms exist.
subquadratic
A key technique (that we will use frequently in this work) in fine fine-grained complexity is the fine- grained reduction, which is a way to connect the rumning times of different problems. If problems P and Q both have quadratic time algorithms. we say that reduces Q (sometimes we would also say PP is easier than Q or Q is harder than PP) if a truly subquadratic time algorithm for Q implies truly subquadratic time algorithm for P. We say P and Q are subquadratic equivalent if they reduce to each other, i.e. there is a truly subquadratic time algorithm for P if and only if there is truly subquadratic time algorithm for @. Such relationships are proved by careful reductions, and we will see many examples soon.
2.2.1 HARDNESS CONJECTURES: SETH AND OVC
We restate our central hardness conjecture here.
Definition 2.4 (Strong Exponential Time Hypothesis (SETH)). For any e > O, there exists a positive integer it such that i:SA requires ((2(1=s)m) time, where n. is the number of variables the CNE
SETH has been one of the biggest open problem in fine-grained complexity, and one of the reasons is that SETH being true would imply P o 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-graine -re-grained complexity and will be key intermediate problem in some of our proofs.
Definition 2.5 (Orthogonal Vectors (OVn,))). Given binary vectors U E (0, OVn. asks to determine if there exists a pair + such that (v,, 01) = O.
Much effort has been made to give a truly subquadratic algorithm for OV D,nlooo n for all but none has succeeded. Therefore, WWilliams (2005) proposed the Orthogonal Vectors Conjecture, which asserts that such algorithm does not exist.
*Usually in fine-grained complexity, a subquadratic time algorithm means the algorithm runs in time o(n") and a truly subquadratic time algorithm means the algorithm runs time O(n²=F) for fixed constant >> 0. For example, On?² 2 logn) 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 suhquadratic, or often even almost linear time. In this work, we will use the fine-grained complexity definition and refer to such approaches truly subquadratic.
7

---

Published as a conference paper at ICLR 2025
Conjecture 2.6 (OVC). For any 0, there exists constant 0 such that OV nVn.clog log cannor be solved in O time.
Williams 2005) showed that assuming SETH is true, then OVC is true (the other direction is un- known). Our paper will use these two conjectures interchangeably such that our hardness results can be obtained from either conjecture.
There is also bichromatic version of OV where one is given two sets of vectors A {a1:..., (n B {bi:..., bn) such that oz, bj E 10, and wants to determine if there exists i such that (a,, by) = In fact, these two problems are subquadratic equivalent (see Theorem A.4 for 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.7 (Min-IP). Given a set of binary vectors Un E (0, Min-IP n,t asks to find one pair of S i,j n, i + such that (vi, minimum.
Sometimes are happy with finding pair of vectors whose inner product is close enough to optimal, so we also introduce the approximate Min-IP problem as follows.
Definition 2.8 (y-Min-IP). Given set of binary vectors u1,-..; Un E (0,1), 7-Min-IP n,e asks to find one pair of S j.j S n, + j such that (Us, 1z) is a n-approximation of the minimal inner product.
It is not hard to see that Min-IP and 7-Min-IP are both at least as hard as OV for any ? 2 1 (just find the minimum inner product and see if it and any multiplicative approximation of 0 must be 0). Therefore, assuming OVC, for any > 0 there exists c > O such that Min-IP innIIPn.clognn n.clog cannot be solved in O(n²-²) time.
In addition, there is decision version of Min-IP, by which denote Min-IP n,t,t, where to know whether there exists a pair of vectors whose inner product is at most for some 0 S t S E. Definition 2.9 (Min-IP decision version). Given a set of binary vectors Ph....,2, Un E {0, and 0 < 1 < &, Min-IPn.tz u.t.t. asks to determine if there exists one pair of 1 S i.j S n, # j such that (w,, M2) t.
The bichromatic versions of these problems can be defined analogously: given two sets A, B with vectors in {0, 133, one needs to find i,j that achieves (for bichromatic Min-IP,x,e) or approximates (for bichromatic 1-Min-IP,.. n,t) the minimal (a,, by). One can obtain truly subquadratic algorithm for all three problems above given a truly subquadratic algorithm for their bichromatic versions (see Theorem A.8 for proof).
2.2.3 MAXIMUM INNER PRODUCT
One can analogously define Max-IP and its variants; see Appendix A.3 for the formal definitions.
is less obvious whether Max-IP a harder problem than OV or not. The answer positive, see Theorem A.13 for simple proof.
In fact, Karthik & Manurangsi (2020) proved stronger statement which says that even approximate Max-IP n. is harder than OV., for some approximation factor.
2.3 DOCUMENT SIMILARITY PROBLEMS
In this section we formally define the MSD, LSD problems that we will study. First we define the MSD variants, which are defined similarly to Max-IP variants.
Definition 2.10 (MSD). Given n document embeddings tn vi...., E {0, 13 MSD asks to find 15 i, n # j such that (e,,y/) is the maximum.
'In all versions of MSD and LSD, assume that there zero vectors.
8

---

Published as a conference paper at ICLR 2025
Even though MSD looks similar to Max-IP, notice that they are not the problem because of normalization. For example, t = (1,1....,,1) E R' and w = (1, 1......... ..0.....0) E R where w has f/2 ones have very large inner product but they might not be considered similar. In contrast, ,
v' = (1, ....., 0,,,,.... .,O,...O) E Ti& where o' has 10 ones and w' = (0, 1,..., O, o...... 0) E R where w/ has 10 ones have inner product of 9 but they very similar in terms of cosine similarity.
Definition 2.11 (7-MSD). Given n document embeddings V1, UI...., {0, [0,1)' y-MSDn, asks to find 1 S 1" 1" S n, + j such that
(1), vz)
(Up- 2/-))
(o 0z)
max 181J5
||e||| ||yll
1 1-11ug-11
max 15:J5n
|e:|| -|15|1
Definition 2.12 (MSD decision version). Given document embeddings v1...., on {0, 13
MSD n.t.t asks to determine if there exists S i. S n, + such that (we.e))
2t.
It is not hard to that n-MSD and MSD,, both casier than MSD. In addition, notice that the number of possible f can be considered as discrete because there could only be O( possible values of (wyee)
|= As result, the existence of truly subquadratic time algorithm for MSDn,f,t for all t E [0, 1] would imply truly subquadratic time algorithm for MSD,, using binary search.
Bichromatic versions of these problems can be defined analogously and the proof Lemma again tells us that bichromatic versions are harder.
A.8
One can analogously define LSD and variants; see Appendix A.4 for the formal definitions.
HARDNESS OF DOCUMENT SIMILARITY
In this section, show that assuming SETH OVC, for any & 0, there exists constant (only depends on E) such that many variants of LSD n,,,,loog MSDn, require O(n2-5) time. Theorem 3.1. Assuming SETH or OVC, for every 0, there exists a constant such that 7-LSDn, cannot be solved in O(n²=F) time for any y 2 when L = c clogn.
Proof. Assume by contradiction that there exists an algorithm A for 7-LSD that runs time Onn2=s) for some 7 2 L,& > 0 and any constant e O. We show that OVn.clog can be solved in time o for any constant
O, which refutes OVC and SETH.
Given vectors Ui...., Un E {0, 13 where & = clog n for any constant c, if any vector is the zero vector (we can check in time O(n))), then output yes. Otherwise run A on 01y-.ry On compute "" such that
Ug))
(1i-, (1g) ||u:-|| [|uz-]]
(vi, Uz))
min LSagsn ||o/|| -11,
<
S7 min isiJsh
||l|||
||ey|l
(us, vi))
if and only if there exists a pair of orthogonal vectors, which implies that there exists pair of orthogonal vectors if and only if A outputs a pair of orthogonal vectors. The total amount of time needed for OV,,t is therefore O(n + n²-=) = O(n which refutes SETH.
Observe that min 15 ||
||ey||
Since y-LSD n. is easier than LSD,. and bichromatic y-LSD,, the same lower bound applies to these two problems as well. In addition, there must exist E [0, 1] such that LSD,,e,t cannot be solved in Onn2=c) time when & clogn n because otherwise that would imply a O(n2-5 time algorithm for LSD,,, using binary search.
Corollary 3.2. Assuming SETH or OVC, every e > O, there exists a constant c 0 such that LSDm,d cannot be solved in 2( time when e 2 clog Moreover, the same lower bound holds for bichromatic nor all y 2 1 and LSD,,..,...ff some t E [0, 1].
A similar hardness result for y- -MMD,,, ,n, Our proof follows the same idea as Theorem 6. Karthik Manurangsi (2020) which uses graph constructions, and delay the proof of Theorem 3.3 Appendix B
be derived with much more complicated techniques.

---

Published as a conference paper at ICLR 2025
Theorem 3.3. Assuming SETH, for every 0, there exists constant 0 such that -yMSS cannot be solved in O(n2==) time when
2 (log (log my? and S log logn
(log log x)
Similarly, the hardness result also applies to harder problems including MSD,, and bichromatic y-MSD
Corollary 3.4. Assuming SETH or OVC, for every E > 0, there exists a constant c 0 such that clog
MSD,,t n,E cannot be solved in ( time when E z (log ni) (log a)a Moreover, the same lower
bound holds for bichromatic n-MSDn.. for all S 7 S (1 log log some E [0, 1].
(log log and MSD n.t.t for
4 REPRESENTATIONAL STRENGTH OF TRANSFORMERS
So far we have seen multiple problems (OV, Min-IP, Max-IP and variants of MSD, LSD) that require quadratic time to solve under certain parameters assuming SETH or OVC. In this section, we show that OV and decision versions of MSD, LSD can solved by a transformer with one attention unit in one layer.
Notice that fine-grained reduction does not trivially apply representational strength of transform- ers, i.c two problems might be subquadratic equivalent, but problem solvable by transformers might not imply that the other one also solvable by transformers. This is because many tech- niques that are simple to do the word-RA. RAM model (where one do arithmetic operations, find the maximun/minimum over n numbers in constant time) might not be easy to implement in parallel architectures like transformers.
We show that transformers are able to solve OV with appropriate parameters. The constructions for Min-IP, Max-IP, MSD, LSD are more complicated but follow similar ideas, so leave them to Appendix C
Theorem 4.1. An attention unit with input and output MLPs with parameters d = E,, din l, dom- 1,m 2 + can solve OV n,t-
Proof. Let UI,...,, Un E {0, 1)2 be an OV instance; define un+1 := 0f and X E [(++1)xe such that X,, = U, for all i. Since m 2 ++ 1, let Q, K be arbitrary matrices such that QK = -3 Ię and V e #x be the all-one matrix. Let Aq.K.v denote this attention head, and ş1 be the identity function.
Let X be the input to the transformer with Aq.k.v as the only attention head. We claim that there C.K.V(( (X) has entry which is least
exists pair < xtI. and otherwise all entries will be at most (n+tyr..- As result, to map Aq.K,v (X) to if any of its entry is at least ntI and 0 otherwise (see Lemma D.1 for formal proof).
such that (us, Uz) = then AQ.
use the second MLP 42
We calculate that the i-th entry of AQ,K.v is
sep(-3logy n- (vi, 0z))
Ej === n 3(v,,ws)) Σ 3(m,,r)) + 1115111.
|10y|11
-= exp exp(-3loge (vr, ux)) +
As a result, there exists pair (ui,, Uzr)) = with S jr S n, then the i* entry of Aq.K.v(X) can be lower bounded
Σ m1
ン== n 3(MLNy))
n 3(p,
k= n 3(
n n+1
n1 n+1 1
Otherwise, (us, vz) 2 1 for all i and thus the i-th entry of AQ, (X) is
Σ 1= 3()
d 333
ン n 3( +1 ||0; <
n 3,
S n
<
n 1.5
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Pairwise
comparison of bit vectors.
Computer
Science
Theory
Stack
Ex-
change, 2017.
URL
https///cstherry.stateeeecciiii com/
quest suestiion/37366
Onn
line:
pai rwise- ootae--coppriin------oiioo
Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 2014 JEEE 55th Annual Symposium on Founda- fions of Computer Science, FOCS 14, pp. 434 443, USA, 2014. IEEE Computer Society. ISBN 97814 9781479965175. doi: 10.1109/FCC.2204555 BRLphtts://do..ooo
23
Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for lcs and other sequence similarity measures. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pp. 59-78, USA, 2015a. IEEE Computer doi: (0009//FOSS220..... htthtt:s: /oii.o.ooooo orc/IC.
Society. ISBN 9781467381918.
I1C9/FOCS. 2015.114
Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, pp. 218 230, USA, 2015b. Society for Industrial and Applied Mathemat- ics.
Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof. More consequences of falsifying seth and the orthogonal vectors conjecture. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 553-266, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978 4783555955 doi: 10.1145//188445331888827
URL httpt::://// //ooi//ooiiio www.oo............. /ttrg//...11...... 145/ /ttp::/::///oooor///...1o1 88745 31 88938
Josh Alman and Yunfeng Guan. Finer-grained hardness of kernel density estimation. In Rahul Santhanam (ed.), 39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, Ann Arbor, MI, USA, volume 300 of LiPlcs, pp. 35:1-35:21. Schloss Dagstuhl Leibnni--iiinnnn für URL http:::///ii...r//11...4.4
Informatik, 2024, doi: WE230LLIPICS.CCCC.0000
LIPIcs CCC 2024 .5
Josh Alman and Zhao Song. Fast attention requires bounded entries. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc.
Josh Alman and Ryan Williams. Probabilistic polynomials and hamming nearest neighbors. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 136-150. IEEE, 2015,
Josh Alman, Ethan Turok, Hantao Yu, and Hengzhi Zhang. Tensor ranks and the fine lnainedi com- plexity of dynamic programming. In Venkatesan Guruswami (ed.), 15th Innovations in Theoret- ical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 of LIPlcs, pp. 4:23. Schloss Dagstuhl Leibniz-ZZnnrrum für Informatik. 2024. doi: 10.4230/LPPCC..ICC 2024.4. URL ITCS 2024.4.
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neigh- bor in high dimensions. Commun. ACM, 51(1):117-12,, Jamuary 2008 ISSN 0001-0782, doi:
141144//3274452.1377999
TRRLhttps: pttctts:://o.... org 10. 1 0tt.//32745222
Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the Forry-Seventh Anmual ACM Symposium on Theory of Comput- ing, STOC 15,, pp. 793-801 801, New York. NY, USA, 2015. Association for Computing Machin- ery. ISBN 4781450335362. doi: 00.1155/244639.2746633 URL htthhtts:.... //doi. orq/10. 1145/2 1145/2746539

---

Published as a conference paper at ICLR 2025
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. Optimal hashing- -ased time-space trade-offs for approximate near neighbors. In Proceedings of the Eventy-Eighht An- mual ACM-SIAM Symposium on Discrete Algorithms, SODA 17, pp. 47-66, USA, 2017. Society for Industrial and Applied Mathematics.
Kensuke Baba, Tetsuya Nakatoh, and Toshiro Minami. Plagiarism detection using document sim- ilarity based on distributed representation. Procedia Computer Science, 11 111:382-387, 2017. ISSN 1877-0509. doi: https///db.orr//1111016////
URL https:/ /www. sciencedirect com/ ooo.i/////rrrccce////////7111110
The 8th In-
ternational Conference on Advances Information Technology.
Arturs Backurs and Piotr 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, STOC '15, pp. 51-58, New York. NY, USA, 2015, Association for Computing Machinery. ISBN 9781450335362.
doi: 00.14452244639.2746622 URL https://doi.
orq/10 005//o..115/2746653 2746612
Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. On the fine- grained complexity of empirical risk minimization: Kernel methods and neural networks. Advances in Neural Information Processing Systems, 30, 2017.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.
margin bounds for neural networks. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL htttpss//pprceeeeddiii www.://ew.....ee..e............o
neurips.c.... wwtpppereppppppppprrpppppppp pdf
Iz. Beltagy, Matthew Peters, and Arman Cohan. Longformer: The long-document transformer. CoRR, abs/2004.05150, 2020. URL
05150
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 7096-71 16. Association for Computational Linguistics, 2020. doi: 10. N0.18653/v1/2000
URL
emn main. 576
David M. Blei, Andrew Y. Ng, and Michael I. Jordan. Latent dirichlet allocation. J. Mach. Learn. Res.,
2003. URL http:///....ppppp/////////////// wttpe//rwww////eeeeaeaaa html
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Vosber Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess. Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL httos: httpps/:/pprcceee.ggg..... neurips wwtpppppp.......c http:/ppprrfffleeee wwt.ffllllpppee//0//// Papp:eaacccccccceooaaaaaepreeee
File
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.), Computer Vision ECCV 2020 16th Eu- ropean Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part 1, volume 12346 of Lec- ture Notes in Computer Science, pp. 213 229. Springer. 2020. doi: 10. 0-30-58452-88 030 --0------00-----------888--
13. WtRLhhtps:///oot httttp::://oo..orrg//.o.o 1007000000000000
Timothy M. Chan and R. Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smi wwmbooooossmolnss....... ACM Trans. Algorithms, 17(1), dec 2021. ISSN 1549-6325. doi: 10. 00.1145/3402926 URL https:ttp/..........m //doi www.ado..orgg//// 1tt.//1001155/44499999
12

---

Published as a conference paper at ICLR 2025
Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. The- ory Of Computing, 16(4):1-50, 2020.
David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. Proceed- ings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 7654-7664, 2022.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with per- formers. In 9th International Conference on Learning Representationss ICLR 1021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021, WRRLhttps://openeeett (W=Ua6ZukOWRH)
net/ forum?
Giannis Daras, Nikita Kitaev, Augustus Odena, and Alexandros G. Dimakis. SMYRF efficient attention using asymmetric clustering. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 12, 2020, virtual, 2020. URL htLps:ts:tt http:ttssp/pccceeee.n. -bstrr/tbbttt.t........ .html
www.rer..c... cc/
Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Compulational Linguisties: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pp. 4171- 4186. Association for Computational Linguistics, 2019a. doi: 10.18653/VI/19-1 1/2331433.. 1423. URL 1423
ht https: wtt.d//.......00.11555////////1.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pp. 4171- 4186. Association for Computational Linguistics, 2019b. doi: 10.18653/VI/N19-11 1423. URL https://doi. 1tt.:/.......0......111//1/1/31 1423
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URU/tttps://ppeneeviees net forum? SeNTccbFNNTTT
Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde. On the computational complexity of self-attention. In Shipra Agrawal and Francesco Orabona (eds.), Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings
of Machine Learning Research, pp. 597-619. PMLR, 20 Feb-23 Feb 2023. URL https:// proceedings.co www. www.m..r.....e..mmmmm v201 duman keles23a....... html
Joshua Engels, Benjamin Coleman, and Anshumali Shrivastava. Practical near neighbor search via group testing. Proceedings of the 35th International Conference on Neural Informa- fion Processing Systems, NIPS '21, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9781713845393.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00753 2023.
Xiaoyi Gu, Leman Akoglu, and Alessandro Rinaldo. Statistical analysis of nearest neighbor meth- ods for anomaly defection. Curran Associates Inc., Red Hook, NY, USA, 2019.
13

---

Published as a conference paper at ICLR 2025
Michael Hahn. Theoretical Limitations of Self-Attention in Neural Sequence Models. Transactions of the Association for Computational Linguistics, 8:156-171, 01 2020. ISSN 2307-387X. doi: 00306
10.1162/tac 00306. URL/ttts:: /oii org. 11..:..11222aaa/
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, and Amir Zandieh. Hyperattention: Long-context attention in near-linear time. In The Twelfth International Con- ference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRe- view.net, 2024. URL /ttps:://ppenreviee net het:/oorrumidd-hoo02....
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics,
2022. doi: 10.
oxg/2022.tacl122
Zellig S. Harris. Distributional structure. WORD, 10020))))1))) 1954, doi: 10.1080/00437956
1954.1 1659520.. (t/.tt/pp////000../////000000000
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks uni-
versal approximators. Neural Nenworks, 2(5):359 -66, 1989. ISSN 0893-6080. doi: https:
htbpl//ww/o....00000099/00000099 sci set.eeee/aarrtillll////////33133
URL https: /wwww scieeeedieeeeerettt... com/
Jerry Yao-Chich Hu, Thomas Lin, Zhao Song, and Han Liu. On computational limits of modern hopfield models: A fine- grained complexity analysis. In Forty-first International Conference on Machine Learning, 2024a.
Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computational limits of low-rank adaptation (lora) transformer-batt based models, 2024b. URL httpps://arxv..
arg/abs/2ne 2406 03136
Jerry Yao-Chich Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, and Han Liu. On statis- tical rates and provably efficient criteria of latent diffusion transformers (dits). In A. Glober- son, L.. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 31562-31628. Curran Associates, Inc., cc paper htsp:/sssseesssepeeeee////0 Conference Panee-eaaeeaaCrreeeeeee-e pd.f
2024c. URL httpsss/pppoceeednss..eeeee.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer
and System Sciences, 62(2):367-375, 2001. ISSN 0022-0000. doi: http://doi.org/10..00
Jess.2000.177 URL htRt:t/ts:///// http::://wwww. www. www.ciinnciiieeeoo comm//scienee//tttccl//..... S0C220000009
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the Thirtieth Anmual ACM Symposium on Theory of Comput- ing, STOC '98, pp. 604-613, New York, NY, USA, 1998. Association for Computing Machin- ery. ISBN 0897919629. doi: 10. 00.114/5776688.27687777 URL pottpps://do. wtt.ddi..og//1.1111 276698 276876
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and gen- eralization neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 8580 8589, Red Hook, NY, USA, 2018. Curran Associates Inc.
Peng Jin Yue Zhang, Xingyuan Chen, and Yunqing Xia. Bag-of-embeddinng for text classifica- tion. In Proceedings of the Twenty-Fifh International Joint Conference on Artificial Intelligence, IJCAI'16, pp. 2824-2830. AAAI Press, 2016. ISBN 9781577357704.
Krishna Juluru, Hao-Hsin Shih, Krishna Nand Keshava Murthy, and Pierre Elnajjar. Bfg-of-words technique in natural language processing: A primer for radiologists. RadioGraphics, 41(5): 1420-1426, 2021. doi: 10. 20.1144/022222200022. URL https: /ow. http://oo..o///1111//1333// 202121000 PMID: 34388050.
14

---

Published as a conference paper at ICLR 2025
C. S. Karthik and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic. Combinatorica, 40(())039- 573: aug 2020. ISSN 0209-9683. doi: 10.1007/ 300493-019-4113-1.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast autoregressive transformers with linear attention. In Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 5156-5165, PMLR, 13-18 Jul 2020. URL mlr press www.v wtt.k//aaaaaooooloo22o2...
https::/proceed//
html
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In
8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL VkgNKkHtvB
net forum?ic
Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the fine-grained complexity of one-dimensional dynamic programming. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (eds.), 44th International Colloquium on Automata, Languages, and Pro- gramming, ICALP 2017, July 10- 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pp. 21:1-21:15. Schloss Dagstuhl -eeinn für Informatik, 2017. doi:
URL
org. 4230 /tt//IIIICcs. ICALP 2017.21
Quoe Le and Tomas Mikolov. Distributed representations of sentences and documents. In Proceed- ings of the 31 International Conference on International Conference on Machine Learning Volume 32, ICML'14, pp. 11-1188-1I-11 199.. JMLR.org, 2014.
Bingbin Liu, Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shortcuts to automata. In The Eleventh International Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL lhttps://openrest
net wwtp/neuntttetteeeeeeee Fow.mm:dddeeePPaaiiua
W. Maass, G. Schnitger, and E. D. Sontag. A Comparison of the Computational Power of Sigmoid and Boolean Threshold Circuits, pp. 127-151. Springer US, Boston, MA, 1994. ISBN 978- 1-4615-2696-4 doi: 10. 00.1007/978-1-4155-5 778-1-4615-266-
URL https: 1tt.ii.org/11..0000000
Mohammed Najah Mahdi, Abdul Rahim Ahmad, and Roslan Ismail. Similarity search techniques in exploratory search: review. In TENCON 2018 2018 IEEE Region 10 Conference, Jeju, South Korea, October 28-31, 2018, pp. 2198-2198. IERE, 2018 8. doi: 10.1 109//ENCON..211... 8.65025777
URL htRl|tttss:// /oii org 100 19/ 201100//TENCCO TENCON. 2018 8650257
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Aus- tria, May 7-11, 2024. OpenReview.net, 2024. URL https:://ppereviiieeeeee/ net forum? 1d=N Ph&Whh
William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers constant-depth threshold circuits.
Transactions of the Association for Computational Linguistics, 10:843-856. 2022. doi: 10.1162/tacl a_00933. URL http:httt/ccccctcat htttes:://elaatttooooooo/////2/2
49
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS' 14, pp. 2932, Cambridge, MA, USA, 2014. MIT Press.
OpenAl GPT-4 technical report. CoRR, abs/2303.08774, 2023. doi: 10.8850/ARXXV.2203008744 URL http::ts:/ooooooo/////oa 085001....558888
Malte Ostendorff. Contextual document similarity for content-based literature recommender sys- tems. CoRR, abs/2008.0022 00202, 2020. htll/htttss//axxvv..om wttpg////////...a/////// 2008 00202
15

---

Published as a conference paper at ICLR 2025
Mary Phuong and Marcus Hutter. Formal algorithms for transformers, 2022. URL https://
arxiv. org/ abs http//aaa///2...//// 220.222272..2
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguis- lics, 9:53-68, 2021.
Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Proceedings the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 1260-1268, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355599, doi: 10. 1145/3188745.3 188916. / /tt../////....//11.....8...
3188916
Jesus M. Sanchez- Gomez, Miguel A. Vega-Rodríguez, and Carlos J. Pérez. The impact of term- weighting schemes and similarity measures on extractive multi-documeet text summarization. Ex- pert Systems with Applications, 169:114510, 2021. ISSN 0957-4174. doi: https://doi.org/10... 1016/ j.eswa. 2020. 1 14510. URL httpt::/t///t. www. sci encedi rect. com/ ccom/cciin www.encceeaatiiiii/cc/c...c 011/50995417420333
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and log- arithmic depth. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 43276 PMLR, 21-27 Jul 2024a. URL htttp:://proceedinngs wtwpiiigss..r...s.e.. V235/ http://afordd...aatett
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. In Proceedings of the 37th International Conference on Neural Information Pro- cessing Systems, NIPS 23, Red Hook, NY, USA, 2024b. Curran Associates Inc
Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing). The MIT Press, 2006. ISBN 026219547X.
Karen Sparck Jones. statistical interpretation of term specificity and its application in retrieval, pp. 132-142. Taylor Graham Publishing, GBR, 1988. ISBN 0947568212.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What Formal Lan- guages Can Transformers Express? Survey. Transactions of the Association for Computa- tional Linguistics, 12:543-561, 05 2024. ISSN 2307-387X. doi: 10.1 10.11//aaaa..00663 URL a_0____0066666
Yufei Tao, Dimitris Papadias, and Qiongmao Shen. Chapter 26 continuous nearest neighbor search. In Philip Bernstein, Yannis E. loannidis, Raghu Ramakrishnan, and Dimitris Papadias (eds.), VLDB '02: Proceedings of the 28th International Conference on Very Large Databases, pp- 287-298. Morgan Kaufmann, San Francisco, 2002. ISBN 978-1-55860-866 869-6. doi: https://doi. URL https: www. scweccedreeccc...et......... com/
org/10. 000.0000066099715555066669999960 Beiiencc/arrtclle////////888BBB
Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. Synthesizer: Rethinking self-attention for transformer models. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pp. 10183-10192. PMLR, 18-24 Jul 2021. URL https://proceee
mmm.mmmrr...m www.mm........... 39/tay21a htt.al1aaa....l.....m.
Shahadat Uddin, Ibtisham Haque, Haohui Lu, Mohammad Ali Moni, and Ergun Gide. Com- parative performance analysis of k-nearest neighbour (knn) algorithm and its different vari- ants for disease prediction. Scientific Reports, 12(1). April 2022. ISSN 2045-2322. doi: 10. 10.1038/s41598-00 10358-x. Publisher Copyright: C 2022. The Author(s).
Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness popular conjectures such as the strong exponential time hypothesis (invited talk). In Thore Husfeldt and Iyad A. Kanj (eds.), 10th International Symposium on Parameterized and Exact Computation, IPEC 2015,
16

---

Published as a conference paper at ICLR 2025
September 16-18. 2015, Patras, Greece, volume 43 of LIPlcs, pp. 17-29. Schloss Dagstuhl Leibniz-Zentrun für Informatik. 2015. doi: 104230LIPPCS.PEC..055.. URL https:// Goi. 10. 0w30//IIIIII. IPEC. 2015.17
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31 Inter- national Conference on Neural Information Processing Systems, NIPS' 17, pp. 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 97819 10066064.
Sinong Wang. Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. CoRR, Abs/2000.04768. 2020. URL htttps://erxiv.org///oo 2006..000 04768]
Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: a case study on approximating turing machines with transformers. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2024.
Curran Associates Inc. ISBN 9781713871088,
Ryan Williams. new algorithm for optimal 2-constraint satisfaction and its implications. Theo- retical Computer Science, 348(2):357-36 2005, ISSN 0304-3975. Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004).
Virginia Vassilevska Williams. On Some Fine-Grained Questions in Algorithms and Complex- ity, pp. 3447-3487. 2018.
doi: 10. 00.11422/988881222288888 0188. URL Intpps:// //wp:: www.
worldscientific. com/ /ts///oi///// /ttp:///......11/99999111110
0188
Virginia Vassilevska Williams and R. Ryan Williams, Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5), August 2018. ISSN 0004-5411. doi: 10. 10.1145/318689,
URL
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoe V. Le. XLNet: generalized autoregressive pretraining for language understanding. Curran Associates Inc., Red Hook, NY, USA, 2019.
Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, and Karthik Narasimhan. Self-attention net- works can process bounded hierarchical languages. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computa- tional Linguistics and the 11th International Joint Conference Natural Language Processing, ACL/JCNLP 2021, (Volume 1: Long Papers). Virtual Event, August 1-6, 2021, pp. 3770-3785, Linguitti Association for Computational Linguistics, 2021. doi: /ttpt/ttt///d..co./0......ao..o.
URL
https::/doi. /oi:: http://6b...222.1...16636/////00 wct-::2...cc1oooo
292
Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. Kdeformer: accelerating transformers via kernel density estimation. In Proceedings of the 40th International Conference on Machine Learning, 1C.L'23. JMLR.org. 2023.
A A DETAILED INTRODUCTION TO FINE-GRAINED COMPLEXITY
A.1 HARDNESS CONJECTURES: SETH AND OVC
We restate our central hardness conjecture here.
Definition A.1 (Strong Exponential Time Hypothesis (SETH)). For any E > 0, there exists a posi- tive integer such that kSAT requires ((((1-e))) time.
SETH has been one of the biggest open problem in fine-grained complexity, and one of the reasons is that SETH being true would imply P o 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- ine-grained complexity and will be key intermediate problem in some of proofs.
17

---

Published as a conference paper at ICLR 2025
Definition A.2 (Orthogonal Vectors nOV,,))) Given binary vectors 01...., Un E {0, OV asks to determine if there exists a pair i + j such that (Us, 0z)) = O.
Usually researchers focus on the regime when & & n, and thus we will assume that I n²((1) throughout this paper. The straightforward algorithm for OV runs in time O( by simply computing the inner products between each pair of vectors. In very low dimensions, one can employ folklore recursive approach to obtain O(2 + n) time algorithm (see CST 2017 ). When é c log nt for a large constant e, all algorithms mentioned above require quadratic time with respect to n, but Abboud et al. (2015b); Chan & Williams (202T) gave slight improvement, showing that for fixed constant > 0, OV OVn,ologn can be solved in time 1)2-1/0(lges, This is truly subquadratic running time for any fixed constant c, but becomes quadratic as e grows. It is still unknown whether there exists (nn²=) time algorithm for all constant c, where is an absolute constant that does not depend on c, and the popular OVC Conjecture states that no such algorithm exists.
Conjecture A.3 (OVC). For any ε > O, there exists a constant > 0 such that OV n.ggon cannor be solved in 0mn2==) time.
Williams 2005) showed that assuming SETH is true, then OVC is true (the other direction is un- known). 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 OV where one is given two sets of vectors = {ai..... Jn B = (bi,.... b such that a, by E {0, 1) and wants to determine if there exists i such that (a,, by) O. In fact, these two problems are subquadratic equivalent.
some Lemma A.4, There exists an algorithm for OV that runs in time O (oly(())))))))))))))))) some & > 0
if and only if there exists an algorithm for bichromatic OV that runs in time O(n²~e' poly(())
for some e' > O.
Proof. First we assume that there exists an algorithm A for bichromatic OV,,e that runs in time O(n poly(e) (l)) for some
O. Given an OV,,, instance V = {eI..... Un with v, E {0, 1) for all i, we first check if any v; is the all zero vector (if so then is a yes instance). Otherwise, let A = B V and run A on A, B. Notice that since there is no all zero vector, (vi, 0;) # 0 for all and therefore there exists i * j such that (v; U2) = 0 if and only if there exists U; = a E A, vj = b E B such that (a, b) = 0. The total running time is O(n²=e poly(E) + nē) = - poly
Now we assume that there exists an algorithm A' for OV that runs in time O(1 poly(!) for some E > 0. Let A = {aI...., an B {bi,..., bn with vectors a, b, E 10, be bichromatic OVn, instance. For each ae we construct df = (a;, 1,0) E R4+2 and for each by we construct By (bj, 1) E R&+2 and let A'= [a] ...,,'). B' (b/,.... b.....,,].. Notice that now (al, az). (b/, b1) 2 1 for all i,j. As result, if there exists (a,, by) = 0, then (a). E A' B', then it must be the case that w a; and w = bú for some j or vice versa, which implies that (a,, = Therefore, running A' on A' B' will tell us whether A, B is a yes instance or not. The total running time required is (((2)) poly + 2)) = O(n poly(e)).
(ar, + = 0. Conversely, if (w, w) = 0 for any
When l = c clog n for some constant e > O, an algorithm running in O(n poly({)) time for some fixed constant E 0 is truly subquadratic algorithm. Therefore, Lemma A.4 implies that assuming OVC, there is no truly subquadratic algorithm for bichromatic OVn.e.
A.2 MINIMUM INNER PRODUCT
In this section we introduce the minimum inner product problem, important problem related to similarity search. Definition A.5 (Min-IP), Given set of binary vectors Un h E {0, 13 Min-IP nft asks to find one pair of 1 < i.j S n, i + j such that (ve, 22)) is minimum.
The trivial algorithm for Min-IP ne takes (n) 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, we also introduce the approximate Min-IP problem as follows.
18

---

Published as a conference paper at ICLR 2025
Definition A.6 (ry-Min-IP). Given set of binary vectors ....... Un 10, y-Min-IP, n.t asks to find one pair of I j,j I n, # j such that (V,, U2)) is a appppooximation of the minimal inner product.
It is not hard find the minimum inner product and see it is 0, and any multiplicative approximation of must be O). Therefore, assuming OVC, for any 0 there exists c 0 such that Min-IP n.e log cannot be solved in O time.
that Min-IP and 7-Min-IP are both least hard OV for any ?
(just
In addition, there is a decision version of Min-IP, by which we denote Min-IPn,e. where one wants to know whether there exists pair of vectors whose inner product is at most for some 0 S <t f. Definition A.7 (Min-IP decision version). Given set of binary vectors 0i.--.. O S S e, Min-IPa,t, n,t. asks to determine if there exists one pair of S i.J S n, F j such that (0%, 02) S t.
, On {0, and
Min-IP is trivially least as hard as Min-IP &,E, for any because if we can calculate the mini- mum, then we can decide whether it is at most or not. In addition, notice that when 2 E + 1 or << the problem 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)3, one needs to find i.j that achieves (for bichromatic Min-IP,,,l ,,,)) or approximates (for bichromatic 7-Min-IP the minimal (0s, by)- One can easily obtain truly subquadratic algorithm for all three problems above given a truly subquadratic algorithm for their bichromatic versions.
Lemma A.8. Suppose there exists algorithm for bichromatic Min-IP n,t that runs in time O(n poly(()) for any O, then there exists an algorithm for Min-IP n.t. that runs in time O(n2-e' poly({)) for some e' O. The same statement true for --iin-IP, n,g and Min-lP n,t.t-
Proof. Given a Min-IP,,, n.e instance = {U1,... }. we first partition V into V1, V/2 of equal size and run A on V1, V/2 This will allow to find the minimal pair in V1 x V2- Now further partition Vi into two sets equal size and recurse on V to eventually find the minimal pair in Vi x Vi. Similarly we recurse V2 find the minimal pair in V/2 V2. The running time of our algorithm is
log n
poly({)
Σ 0 1=1
(
(2-x) = =O poly(!) logn) S 0 poly(())
for some 5' 0. The exact same argument holds for M-n--I n.t as well because the minimal pair must appear in some recursion where we run our algorithm on. The argument also holds for Min-IP n.e,, because we have gone over all possible pairs of vectors.
A.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 A.9 (Max-IP). Given set of binary vectors vi...., .....,,,,, Un E {0. Max-IP,, IP n,e asks find one pair of 1 < i.j S n, # j such that (e,, U;) is maximal.
Definition A.10 (7-M Max-IP). Given set of binary vectors U1,..., Un E 10, --aax-IP asks to find one pair of 1 < i,j < n, i # j such that (vi, 0z) is "/approximation of the maximal inner product.
Definition A.11 (Max-IP decision version). Given a set of binary vectors UI...., Un E {0, 1) Max-IP
neett n.,et asks to determine if there exists one pair of i,j n, + j such that (v,, 0z) 2 t.
The bichromatic versions of these problems be defined analogously. Similar to Min-lP, one easily obtain truly subquadratic algorithm for all three problems above given truly subquadratic algorithm for their bichromatic versions again using the proof of Lemma A.8
19

---

Published as a conference paper at ICLR 2025
Lemma A.12. Suppose there exists algorithu Afrr bichromatic (7- Max-IPPa n,E that runs in time
O(n2 po)y(E)) for any >> O, then there exists an algorithm for (7- Max-IP n. that runs in time O(n²- pool(()) for some e'
It is less obvious whether Max-IP is a harder problem than OV or not. The answer is positive, and for bichromatic Max-IP, there exists a simple proof.
Lemma A.13, Suppose there exists algorithm A for bichromatic Max-IP n.t that runs in time O( poll((pll))))))))))) for any e >> O, then there exists an algorithm a,t that runs in time O poly()).
Proof. Given OV,, instance UI...., Cp E {0,1} 13 we partition all 6 into subsets St...., such that each Sj contains all vectors with j ones. Now for each pair of S i, S f, let S₁ consists of vectors in Sj but with all the entries flipped. As a result, for any E S w E S₁ we have (u, w) = i- (u, w²), which implies that (v, w) = and only if (v, w) Therefore, running A on S;, Sj will tell us whether there is an orthogonal pair of vectors in S; and Sj. The total running time is O n²== poly(f)) = O(n²==) pely(().
In fact, Karthik & Manurangsi (220)) proved stronger statement which says that even approximate Max-IP n,e is stronger than OV,, for some approximation factor.
A.4 LEAST SIMILAR DOCUMENTS
We now formally define LSD variants, which are defined similarly to Min-IP variants. Recall that MSD and variants were defined in Section 2.3 above.
Definition A.14 (LSD). Given document embeddings U1,..., Un E {0, 13 LSD,,t asks to find 1 S n, + j such that (0:.04) is the minimum.
To,]--Iv,
Definition A.15 (n-LSD). Given n document embeddings ,1... Un {0, 13 7-MSD asks to find 1 < j & n i # such that
(Ve, Ug) Uz)
(
(Us, 0y)
min 15t55n
| || S7
min 15tJ5n
||x]|| -1u,
Definition A.16 (LSD decision version). Given document embeddings ,I...., on {0, 13
(1r.25)) LSD asks to determine if there exists S i, < n, i + such that Te: |ley S t.
y-LSD,., and LSD,, t.t both easier than LSD. In addition, the existence of truly subquadratic time algorithm for LSD,,F, for all t again implies a truly subquadratic time algorithm for LSD,,, using binary search. Bichromatic versions of these problems can be defined analogously and the proof of Lemma A.8 A.8 again tells us that bichromatic versions are harder.
B PROOF OF THEOREM 3.3
In this section we prove Theorem 3.3 and our ideas are similar to the ideas in section and 6 of Karthik & Manurangsi (2020). Recall the theorem follows.
log
Theorem B.1 (Theorem 3.3 Assuming SETH OVC and & S log log
(log logg w2)
such that there is no algorithm for 2(log 2(logn)t--dh o(13) for every > there exists a constant C elog
7 MMSD that runs time Onn==e) where (log n) (log 1og
We break down the proof into several lemmas below.
clox e Lemma B.2. Suppose there exists algorithm for -MS. where é (log n)) (log log my for any lox
constant e > 0, 7 S (1 log log
low ve that runs in O(n²=5) time for any & > O, then there exists algorithm for (1 + log Ing n JMMSD MMMSD,,(logann m)o with running time (nn--e) for any constant
k > 0.
20

---

Published as a conference paper at ICLR 2025
{0, 1 (log be an instance of (1+ log log -MSD, nlo n)* for any constant log k >> O. Construct V {vi 0g o for y (log log all the vectors in V have dimension
Proof. Let 01, ......: Un
A
(log n) = (log n) (log w)? so we can run the algorithm provided to find 7-approximation of MSD on V for some 7 - (1 + log n) Notice that we have
(v) 009 " |
(or, Uz) ) ( (1ez1l ||ll|| ||/y]]
=
||
for any i.j. so an y-approximation of MSD on V is a (1+ log log approximation of MSD
on U1,..... :
Now we define the bichromatic 7-Additive-MSD problem as: given a A, B S {0,1], e [0.
with |A| [B] n, we want distinguish between the following two cases:
1. Yes instance: There exists (a, x B such that (a.b)
2
|alllTa||
2. No instance: For every b) A B we have (a.5)
]|त|||[b|| 7.
Lemma B.3. Suppose there exists an algorithm A for (1 + log log ).... n. m,olo nyk for any
constant k > O with O(n²=s) running time, then there exists an algorithm for bichromatic log n MadditveeMSDn.ceeee n for any c. O in time O for some e' 0.
Proof. The proof follows from Theorem B.4 1.4am and Theorem B.5
Theorem B.4 (Karthik & Manurangsi (2020) Theorem 6.2). Suppose there exists an algorithm for (1 log log J-MSD ni* for any constant l > 0 that russ in O(n²=²) time for any >> 0, then there exists an algorithm for bichromatic (log -)dddiiive Mwwdiiie--axx-llll Pn,cloonn for any constant e >> that runs in O(n²-') time for some g! >>
Lemma B.5. Bichromatic Degn-Addiive-MSDD
O(logn) and bichromatic (logn)-Adding Masttivee-ax--In--- n,e' with = O(logn) n) are subquadratic equivalent.
with
Proof. Given bichromatic (log -dditivvei-i---xx-P n.t instance with sets A far..... an).B. B {bi...., ) and integer a, we construct A' {a'...., ( B' = (64.....66 as follows: for each 0; first attach e - ||a,|]a | many ones the end and another + ||a:/|2 zeros to obtain a' E {0, 1) 1 and for each b, we first attach + [byl] zeros at the end and another |bbyl ones to obtain i, E 10.1 Now all a4, by have é many ones, and (at, K8) = (a,, by) for all i.j by our construction. Therefore, running our algorithm for Jogn Additive- on A', B' and will tell us whether:
there exists (a',6') E A' x B' such that (a', 2
fa' a |
2 g. which is equivalent to (a, b)
2. for every (a',b') E A' B' have
(a'.8)
< a
logn which is equivalent to (a,
(a', 1/) < a log n for all a E A,b E B.
The running time of our algorithm O(n2== 2- poly(3()) = O(n2~= - poly(!)).
The reduction for the other direction is similar. Suppose we are given bichromatic log log AdddAAdidivee-SD.. instance with sets A (az,..., J,,, B = Ub,,...,b,) and [0, 1]. we construct the exact same A', B' as before such that (a/, b,}) = (a,,b)) for all i,j. Since ||a|l| ||b /l for all i, now, the same argument implies that running the algorithm A', B' and a f will solve the problem.
21

---

Published as a conference paper at ICLR 2025
Lemma B.6 Chen
(0200). Suppose there exists
algorithm for
(log n)- Bdditiiee-Baxx-I...... nee for any constant 0 running in time O(n²-c') for some
> O, then there exists an algorithm for OV n,e log for any constant c' > 0 with running time
Onn2-E), thus refuting SETH and OVC.
Proof of Theorem 3.3
This follows from combination of Lemma B.2 Lemma
B.3
Lemma
B.5
and Lemma B.6
C
TRANSFORMERS CAN SOLVE Max-IP, Min-IP, MSD n,E, AND LSD
Theorem C.I. attention unit with input and outpul MLPs with parumeters = l, din = +
1, dou 1,m l 1 can solve Max-IPn,te n,e,t and nin-IP 1 S
Proof. Given Max-IP,, n.e instance -1y-.., (0, 13 and V E Ruxxe such that V1, uy for all let 2; (vy, 1) {0, 13 for all In41 = (O..... 0, + 1) E Re+1 and X [x(+1)x(e+1)
6++1
be such that X zi for all i. Let Q, K E Rd be such that QK = 3 log ld. V
1, 1, E Re-1 and AQ.K.v denote this attention head.
We want 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" Uoo to the documents that is always embedded into the vector (0,. ..,..., 0,
0,t+1)
E IR Then we can use MLP to send V to X (see Lemma D.2 for formal proof).
Now we can check that the i-th entry of (X)
exp(3logn n- xz)) 1=1 k= exp(3logu) n. (Ii, vx)) + exp(3(1 + 1) log ||0/|1
Σ n (( || 111
Σ 33 + 3(t-1))
Let < 1" + j & n be such that (us,, Uge) is the largest. Therefore, if (Uss, 11-)) 2 1 then (5ir, Fjr) 2 ++1, which means that
Dn .s) ||o5g|1 E 3a. 3(++1) Eh 1 and + n 3((++)
n ((a || 2 11--- 1l n #+1 1 +
2 1
On the other hand, if (1)),0y)) 1-11, then (1ir, B.-) St, which means
Σラ= n 3 ,3)) |15511
n 3t
E
Els (())) + (((++1) Se.
n 3(++1)
n
(n+ 1)1.5'
Therefore, we can use the second MI.P 922 to map AQ, to any of entry is at least and 0 if all its entries are at most (x+1)Lr (see Lemma D.1 for formal proof of existence).
x+1
The proof for Min-IP almost the same, except that we new let QKT = =3 log n Ia, and øn+t [0, ........ 0, (t + 1)] Rf+1 instead. Now the i-th entry of A is
Ey n 3(mr ||05|11
1m= 3(Z.))) + +n-3(t-)
Let Leti*, j" be such that (I.,, .y.)) the smallest, Therefore, (ve, Uy.) S then (x,,, 1+1. which means that
Ej 3 3(0,
||0y||
n 3(xr at-)
1
Ek=1 30, vx) + 3(++1) >
Σ M + in # 3(+++)
+ 1
On the other hand, if (11-, (.-) 2 ++11 1, then (De, Fz.) 2 2, which means
Eh n 3( mw) + 3(4+1) S L. n.n 3(t+2) E n 3(++1)
Ej n 3/m mn)) ||2
n²
(n + 1)
Sanford al. 2024b) has similar assumption.
22

---

Published as a conference paper at ICLR 2025
Theorem C.2. A attention unit with input and output MLPs with parameters d L, E + 1, dout 1,m 2 + can solve MSDn,c,t and n,, any E [0, 1].
Proof. When 0 the problem is trivial we simply need to output 1 using MLPs, so without
losing of generality we assume t + 0. Given a MSD,., instance .I...., Un E {0, 1 and V E Rnxe
such that Vi,: D2 for all i, let 2; = ( [Tell 1) E R g++1 for all i, 2n+1 == (O. 0, + 1) E Ret1 and E ((++))x(++)) be such that X = 2; for all Let Q, E R be such that QK 3 log n Ld, V = (I, 1,0) E I and Aq,x,v denote this attention head.
1i
Since MSD is exactly Max-IP after normalize the document embeddings, the proof of Theo- rem implies that suffices to send X to the attention head. See Lemma D33 for a construction.
The proof for LSD is exactly the same the proof for Min-IP after applying the (p1 construced in
Lemma D.3
D MLP CONSTRUCTIONS
Lemma D.1. For any a, E R. such that b >> a, there exists continuous function f R. + such
that
((x) - {0
if ar for any sist
if x < <avi < ist.
Proof. Firstly we define g IR such that
if 2
g(x)
h-a a)
if x < if < a
Now we let
f(x) II (1-1g(a g(xli))
It is not hard to see that is continuous function, and therefore f is continuous function. When
b for any < i < l, g(xli))= = and therefore f(x) = 0 1. On the other hand,
for all then f(x) = 1-1 0.
Lemma D.2. There exists a continuous function f RR + R such that
f(x) (x, if x 1 (0, otherwise.
Proof. First we define a function
IR + such that
1
if <
g(x)
2
if < x $2
0
if > 2,
and we also define f1, f2 RR R where
(x) = (x, 1), f2x)) = (0, It is not hard to see that g, f1, f2 are all continuous functions, we let
f(x) g(x(()) f1( (1 g(x((\) f2(
such that is also continuous. We can check that satisfies the requirement in the lemma statement.
Lemma D.3. There exists a continuous function f . Re-1 such that
( | (0,
if if <
f(x) =
) otherwise.
23

---

Published as a conference paper at ICLR 2025
Proof. Let g be the same functions in Lemma D.2 and f1, RR -> R+1 where
(1 | 1) f2(x) (0,
x
||=||
fi, f2 are continuous function over R,, and therefore we let
f(x) g(=(()) fxx)) (1 g(x(e))) f2(2))
such that is also continuous. We can check that f satisfies the requirement in the lemma statement.
24


Reviews:
[{"review_id": "iSFTzk0kdm", "reviewer": "Reviewer_97XG", "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.", "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?", "limitations": "", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 3, "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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "INmLwEx2ND", "reviewer": "Reviewer_TK7Z", "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.", "questions": "1. Can the results be enhanced to rank different subquadratic approximations?\n2. Similarly, can the results be enhanced to quantify the gap between the quadratic transformers and the subquadratic approximations?\n3. Are there approximate algorithms for solving the minimum inner product problem or its variants and how would these relate to the subquadratic approximations?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 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.", "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. \n\n[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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ADKFnW9kN2", "reviewer": "Reviewer_8QVS", "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.\nThe 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.", "questions": "- 259: finds\n- 310: multi-layer\n- 434 write the numbers explicitly, 'very large' is random here\n- 534 left side v_i^*  (the star)\n- line 529 as mentioned above", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Finally some more mathematically theoretically founded analysis of the prominent architecture and its limitations.\nIt analysis seems rigorous and its offering insights that can influence future research on alternative architectures in NLP.", "weaknesses": "minors/ missing discussions:\n\n1.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'.\n\n1.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. \n\n1.3) it would be beneficial to discuss a broader range of tasks\n\nmediocores:\n\n2.1) i find the main paper pretty hard to read and would advice a bit of restructering i.p.\n- abstract line 22ff are quite redundant\n- intro line 132ff seem pretty random/ not needed/ more distractive\n- 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\n- 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) :)\n\n2.2) the core result is 4. it, and its impact should be discussed further, in particular recall what sub-quadratic methods suffer from.\nthe 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KmqJ9Ui8cD", "reviewer": "Reviewer_32nU", "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.", "questions": "> We focus on document similarity tasks, where one is given\nas input many documents and would like to find a pair which is (approximately)\nthe most similar.\n\nCould you please elaborate, why 'approximately' mentioned here? Is it not SETH and derived conjectures about exact results only?\n\n> 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.\n\nApproximate 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.\n\n> bag-of-words embeddings\nHow important is usage of bag of words embedding?  Would it be possible to use embedding / technique which takes into account word ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "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.\n2. Shown that one head / one layer transformer can solve those tasks.  This includes explicit transformer construction.\n3. Bringing complexity results (Strong Exponential Time Hypothesis) to transformer architectures.", "weaknesses": "1. It is not exactly clear when the paper talks about approximate or exact results.\n2. 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.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)