Fundamental Limitations on Subquadratic Alternatives to Transformers

We thank the reviewer for the thoughtful comments and questions.

Approximation results: In addition to proving the hardness of exact document similarity, we also proved in this paper the hardness of approximate document similarity. We proved that approximation versions of MSD, LSD (which we denoted by $\gamma$-MSD, $\gamma$-LSD) also require quadratic time in our main theorems (Theorem 1.1 and 1.2). Here, approximation means we only need to find one pair of documents whose distance is at most $\gamma$ times the distance of the optimal pair for LSD and at least $1/\gamma$ times the distance of the optimal pair for MSD. As a result, they are also hard for subquadratic models, and this is why we refer to approximation versions throughout the abstract and introduction.

SETH and approximation: Indeed, SETH conjectures the hardness of an exact problem, but it has since been used many times in the literature to prove hardness of approximation problems as well. For example, we cite the papers [1,2,3] which all proved hardness of approximation problems, including closest pair, Max-IP etc, from SETH. We used these results to prove our own hardness of approximate document similarity.

Bag-of-Words embedding: As mentioned above, we also show hardness of approximation, which could mitigate the impact of an embedding like bag-of-words not completely capturing the document. That said, our results hold for many other embeddings. For example, they apply almost directly to TF-IDF without needing to modify the proofs much.

Simple reductions: You’re right that many of our reductions are fairly simple, but we view this as a merit: it means that the practical hardness of problems like SAT, OV, etc translate directly to giving practical hardness here as well. Complicated reductions could otherwise make instances become impractical, but we avoid that here.

[1] C. S. Karthik and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic. Combinatorica, 40(4):539–573, aug 2020. ISSN 0209-9683. doi: 10.1007/ s00493-019-4113-1.

[2] Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. Theory Of Computing, 16(4):1–50, 2020.

[3] Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Proceedings of 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.3188916.

A gentle reminder that the discussion period is going to close soon. Please let us know if there are any questions, thanks!

We thank the reviewer for the thoughtful review.

Empirical evidence: We agree that experiments showing particular models failing to solve document similarity tasks could be interesting in future work. However, we want to emphasize that our results, which mathematically prove that subquadratic models cannot solve document similarity, are more general than any such experiment. For instance, an experiment showing that one particular model cannot solve document similarity may not be very convincing, since one could imagine slightly changing the model to get around the issue. Our results show that it is mathematically impossible to do any such modification without using quadratic time.

Practical applications on recommendation systems: Indeed, our work is directed related to the maximum inner product search (MIPS) problem in recommendation systems. In the MIPS problem we are given a dataset $P$ of $n$ points and a query $q$ such that the goal is to return a data point $p \in P$ such that $\langle p,q\rangle$ is the largest. In recommendation systems, $P$ could be a set of items and $q$ could be a customer, such that each time a customer comes, we want to know which item the customer likes the most. This problem is essentially equivalent to the Max-IP problem we study and prove lower bounds with in this paper. We will add another paragraph on this application in later versions.

Varying sequence length and model parameters: In general, increasing the model parameters in terms of $n$ would make the model more powerful. However, our results show the hardness of these document similarity problems, which are defined independently of what the model parameters are (see our footnote 2 on page 4). So, one would at least need to very substantially increase the parameters, to a regime where the running time becomes quadratic, in order to overcome our lower bound.

A gentle reminder that the discussion period is going to close soon. Please let us know if there are any questions, thanks!

We thank the reviewer for the thoughtful review.

Empirical interpretation: Indeed, as the reviewer explains, the papers introducing subquadratic alternatives typically justify them with experiments showing that they are empirically fast and accurate. The experiments differ in details in different papers, but roughly, they show that their new model runs faster than transformer and achieves nearly the same accuracy, typically slightly worse. (See, for instance, figure 3 in [2], figure 2 of [3]) One may wonder whether it is possible to design a subquadratic model that actually achieves the same accuracy, or whether an accuracy loss is necessary. Our results show that, for document similarity tasks, it is not possible for any subquadratic model to achieve the same accuracy as transformer, and so these accuracy losses observed in all these experimental papers must necessarily appear for document similarity tasks. In other words, our paper is giving a theoretical explanation for exactly the empirical phenomenon that the reviewer is mentioning.

Other limitations on transformers: Indeed, in addition to [1], there has been much work studying problems that transformer is unable to solve. For instance, the papers [4] and [5] which we reference in our paper prove that transformer cannot solve problems based on triple-wise correlations or on tasks that are hard to parallelize. More in the spirit of our paper, one can also take problems which require more than quadratic time (such as problems about finding correlations in tensors that require cubic time), and these also cannot be solved by transformer.

This is why it is important that we also prove transformer can solve the document similarity tasks we discuss in this paper. We are highlighting a class of problems that transformer can solve, but subquadratic models cannot, thus showing subquadratic models must be worse than transformer at these tasks.

Ranking or gaps with subquadratic alternatives: Our results don’t show how to rank subquadratic alternatives, they only show that these alternatives cannot solve document similarity problems. Finding problems that some variants can solve and others cannot would give an interesting way to rank these alternatives, although we note that one would need to focus on problems that can be solved in linear time in order to rank alternatives which run in linear time. Using such problems to quantify the gaps between different models could also be interesting future work.

Approximation algorithms: Unfortunately, approximating the minimum inner product is just as hard as computing it exactly. See Theorem 3.1 in our paper where we prove this. (We prove it for approximate LSD instead of approximate Min-IP, but the essentially identical proof works for approximate Min-IP as well.)

[2] Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. CoRR, abs/2006.04768, 2020.

[3] Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: Fast transformers via sketching polynomial kernels. In Forty-first International Conference on Machine Learn- ing, ICML 2024, Vienna, Austria, July 21-27, 2024.

[4] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic 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–43327. PMLR, 21–27 Jul 2024a.

[5] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA, 2024b. Curran Associates Inc.

Dear Reviewer TK7Z,

to the best of my knowledge the ICLR mission statement is not entirely/ necessarily focused on empirical studies.

Albeit I am pretty interested in the practical implications as well, I also see the merit of theoretical bounds. They definitely should be discussed as good as possible, but they may also be sharpened (or becoming more relevant) in follow up work.

On the other hand you give [1] as a reference, which (to my eyes) is a pretty obvious fact, evaluated on their inhouse models only (that are not primarily trained on the evaluated tasks --- or maybe they are - who knows?), and pretty strange incompletely described toy models (C.4/6) which leaves the reader with just as many questions regarding "what is possible, still"...

Thank you for reflecting on my concern.

A gentle reminder that the discussion period is going to close soon. Please let us know if there are any questions, thanks!

We thank the reviewer for the insightful comments.

Practical impacts: Indeed, most of our hardness results come from simple reductions. For example, if we have an algorithm for LSD that runs in time $T$, then that gives us an algorithm for OV that runs in time at most $2T$. Thus, the practical hardness of problems like SAT and OV carries over to yield practical hardness here as well. We will expand on this in the final version.

Performance of other models solving OV: Indeed, it could be interesting to see how to pick the depth for certain subquadratic models like SSMs to solve document similarity tasks. Since our results show that these tasks need quadratic time, one would need to pick a prohibitively large depth for larger $n$ which scales linearly with $n$ (to get a final quadratic running time).

Broader range of tasks: We aimed to study a wide variety of similarity search and document similarity problems in this paper (exact vs approximate, monochromatic vs bichromatic, closest vs farthest, optimization vs decision, etc), which appear (either explicitly or implicitly) in many different tasks that language models are intended to solve. That said, we fully agree that finding more examples and other types of tasks would be exciting.

Other writing suggestions: Thank you, we agree with all the suggestions and corrections you made and will update them in the final version. In particular, for line 528 in the proof of Theorem 4.1, you’re right that we are missing the $\ell_1$ norm of $v_j$ in the summation, although it does not impact the correctness of the proof since it is upper bounded by $d$, which is much smaller than the multiplicative gap of $\sqrt{n}$.

Thank you for replying, and addressing my concerns.

I still find my rating solid. For increasing it further I would require a thorough discussion on the practicality of your bounds found in the proof (point 1.1) and what i flagged in minors, w.r.t. standard model hyperparameters (sequence lengths). I found your one-liner not sufficient here J (and also not the other review comments). I actually wonder why you do not interpret the bounds further, from first reading the paper, I thought they were quite close to being practically relevant as well.

greets

A gentle reminder that the discussion period is going to close soon. Please let us know if there are any questions, thanks!