Pith. sign in

REVIEW 3 major objections 5 minor 2 cited by

Subquadratic Algorithms and Hardness for Attention with Any Temperature

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For constant head dimension d, approximate attention can be computed in about n^{2-1/d} polylog(B/eps) time, while SETH-based lower bounds push near-quadratic hardness down to very small d.

desk verdict A genuine algorithmic advance for constant head dimension with a load-bearing flaw in the row-sum reduction that as written invalidates the advertised constant-entry hardness. read the letter →

arxiv 2505.14840 v1 pith:EM76QJS5 submitted 2025-05-20 cs.LG cs.CC

Shreya Gupta , Boyang Huang , Barna Saha , Yinzhan Xu , Christopher Ye This is my paper
classification cs.LGcs.CC
keywords attentionalgorithmtimesubquadraticwhenalgorithmsevenpossible
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Attention is the operation in language models that lets each token look at every other token. The standard way to compute it takes time proportional to the square of the sequence length, so long contexts are expensive. Earlier theory showed that fast, subquadratic computation is possible only when the query and key entries are tiny, which corresponds to running the softmax at high temperature. This paper asks what happens when entries can be large, i.e., when temperature is arbitrary.

The main positive result is an algorithm for small head dimension. The paper approximates the exponential in softmax by a low-degree polynomial, then uses geometric range-searching to sum relevant terms efficiently. For any fixed d, approximate attention can be computed in about n^{2-1/d} polylog(B/eps) time, which is truly subquadratic. The same machinery gives a subquadratic algorithm for the attention gradient, meaning one training step can be accelerated when the head dimension is constant. A low-rank version extends the result to matrices with large head dimension but small rank.

On the hardness side, the paper reduces known hard problems, Maximum Inner Product and Orthogonal Vectors, to attention. Under the Strong Exponential Time Hypothesis, it shows that attention requires nearly quadratic time even when head dimension is only 2^{Theta(log* n)}, a very slow-growing function. For polynomial head dimension, it argues the standard algorithm is optimal under a variant of the Orthogonal Vectors hypothesis. An important caveat: one of the lower-bound reductions claims the attention oracle receives entries bounded by B, but the binary search inside it must write numbers as large as B^2 d plus log n into the query matrix.

Extended reading notes

Core claim

The paper's central positive claim is Theorem 1.3: for d=O(1), Approximate Attention AttC(n,d,B,eps) can be computed in ~O(n^{2-1/d} polylog(B/eps)) time, with a low-rank extension in Theorem 1.4 and a gradient analog in Corollary 4.4. It also claims matching qualitative hardness: under SETH, AttC(n,d,B,eps) requires n^{2-o(1)} time even for d=2^{Theta(log* n)} (Theorem 5.4), and for d=poly(n) the standard O(n^2 d) algorithm is optimal under a generalized high-dimensional OV hypothesis (Theorem 5.5).

Load-bearing premise

The most fragile premise is in Lemma 5.1's row-sum estimation: the reduction assumes that the Attention oracle instance built during binary search still has entries bounded by B, because the first row of Q' contains ln c for the current guesses. But c ranges up to n exp(B^2 d), so ln c can be as large as B^2 d + log n, which for the constant-entry setting of Theorem 5.7 (B=log 2, d=Theta(log n)) is Theta(log n), not constant. This invalidates the claimed input bound and consequently the "B>=log 2" hardness claim for d=Theta(log n); the proof needs the oracle entry bound to be Theta(B^2 d + log n), which weakens or breaks that specific claimed result.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the approximate attention problem AttC(n,d,B,epsilon). Its main positive result is Theorem 1.3: for constant head dimension d, Attention can be computed in ~O(n^{2-1/d} polylog(B/epsilon)) time, with a low-rank generalization (Theorem 1.4) and a gradient-computation reduction leading to a subquadratic backward pass for d=O(1) (Theorem 4.3 and Corollary 4.4). On the hardness side, the paper claims SETH-based n^{2-o(1)} lower bounds for d=2^{Theta(log* n)} with B=poly(n) (Theorem 5.4), a constant-entry lower bound for d=Theta(log n) (Theorem 5.7), and, under a generalized high-dimensional OV hypothesis, optimality of the standard O(n^2 d) algorithm for d=poly(n) (Theorem 5.5). The lower bounds all rely on Lemma 5.1, a row-sum estimation reduction from softmax denominators to AttC oracle calls.

Significance. If the results hold, this is a substantial contribution to the fine-grained complexity of Attention: it replaces the previous exponential dependence on the entry bound B with a polylogarithmic one, gives a genuinely subquadratic algorithm for constant d, extends the result to low-rank matrices and to gradient computation, and provides conditional matching lower bounds across several head-dimension regimes. The positive algorithm is carefully specified, the use of Matousek's range-searching data structure is concrete, and the error analyses are traced with constants. The main caveat is that the lower-bound machinery contains a load-bearing flaw in Lemma 5.1; as a result, the advertised small-entry hardness claims are not currently established, although parts of the program appear repairable.

major comments (3)
  1. [Section 5, Lemma 5.1 and Claim 5.2] The reduction in Lemma 5.1 writes ln c into the first column of Q' and then calls AttC(n+1, d+1, B, epsilon/100). However, during the binary search the thresholds c_i range over [n exp(-d B^2), n exp(d B^2)], so |ln c_i| can be as large as Theta(d B^2 + log n). This exceeds the allowed entry bound B of the AttC instance whenever d B^2 = omega(B) or log n = omega(B), which includes the regimes used later in the paper. For example, in Theorem 5.7 the setting B=log 2 and d=C log n allows ln c_i = Theta(log n). Thus the oracle call is made on matrices outside the input range of AttC, and Lemma 5.1 is false as stated.
  2. [Sections 5.1-5.2, Theorems 5.4, 5.5, and 5.7] Because Lemma 5.1 is the only bridge from AttC oracles to unnormalized row sums, every lower bound built on it inherits the entry-bound violation. In particular, Theorem 5.7's claim that AttC(n, d, log 2, epsilon) is n^{2-o(1)}-hard for d=Theta(log n) is not proven: the reduction requires thresholds with ln c = Theta(log n), which cannot be placed in an AttC instance with B=log 2. The B=O(sqrt(log n)) variant of Theorem 5.5 has the same problem because its row-sum range spans Theta(d log n) in exponent. Enlarging the oracle parameter to Theta(d B^2 + log n) would repair Lemma 5.1's mechanics and would preserve the B=poly(n) claim of Theorem 5.4, but it changes the advertised entry-bound regimes in Theorems 5.5 and 5.7. The paper should either provide an encoding of the thresholds in extra coordinates while keeping the stated B, or explicitly weaken the affected claims.
  3. [Section 4, Definition 4.2 and Theorem 4.3] The gradient problem AAttLGC(n,d,B,epsilon) is defined with inputs A1, A2, A3, E, and Y, but the matrix X at which the gradient is evaluated is not listed as an input and no bound is stated on its entries. The proof of Theorem 4.3 invokes AttC(A1 X, A2, .) with calls such as Attention(A1 X, A2, h(y)), and the AttC guarantee in Definition 1.2 requires all entries of the first argument to lie in [-B,B]. If X is arbitrary, A1 X need not satisfy this bound, so the reduction is not a valid reduction to AttC and the polylog(B/epsilon) running time in Corollary 4.4 is not justified. The definition should include X and either state an entry bound on X or track the resulting bound on A1 X through the reduction.
minor comments (5)
  1. [Section 2, Theorem 2.3] Theorem 2.3 states Max-IP hardness in dimension d=C log* n, while the abstract and Theorem 5.4 use d=2^{Theta(log* n)}; please reconcile the statement with Chen's theorem and with the dimension used in the reduction.
  2. [Section 5.2, Lemma 5.6] The proof of Lemma 5.6 calls k a constant, but the condition k < (1-c)/(n(1+c)) makes k depend on n; rewrite this as k = Theta(1/n) and adjust the surrounding wording.
  3. [Section 4, Definitions 4.1-4.2] The problem is written AAttLGC(n,d,epsilon) in Definition 4.2 but AAttLGC(n,d,B,epsilon) in Theorem 4.3; unify the notation and include X in the input list.
  4. [Section 5.2, opening paragraph] The text says 'computing AAttC(n,d,B,epsilon)' where the problem under discussion is AttC; the extra 'A' appears to be a typo.
  5. [Section 3, Algorithm 2] Algorithm 2 labels its error parameter epsilon but its stated guarantee is ||hat(O)-Attention(Q,K,V)||_infty <= 7 epsilon B; the later rescaling is explained in the text, but the pseudocode would be clearer if the local parameter were named epsilon'.
Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The main algorithm has no fitted parameters and rests on standard tools: range searching, polynomial approximation, and rank factorization. The lower bounds rest on SETH and on a newly introduced Generalized High-D OV Hypothesis. The row-sum estimation flaw in Lemma 5.1 is not an axiom but a derivation error that would need to be fixed.

assumptions (5)
  • domain assumption Strong Exponential Time Hypothesis (SETH), Hypothesis 2.1
    Used to derive all SETH-based lower bounds in Theorems 1.6, 5.4 and 5.7, via the OV and Max-IP hardness of [Wil04] and [Che18].
  • ad hoc to paper Generalized High-Dimensional OV Hypothesis, Section 5.2
    Introduced by the authors to prove Theorem 1.7 that the standard algorithm is optimal for d=poly(n). It is a generalized version of the High-D OV Hypothesis of [DK21] and is not a standard established hypothesis.
  • standard math Matousek simplex range searching data structure, Theorem 3.7
    Underpins the geometric halfspace queries used by the main algorithm; the paper cites [Mat92] rather than proving the data structure.
  • standard math Polynomial approximation of exp with relative error, Lemma 3.3
    Cited from [AA22, AS24a]; provides the low-degree polynomial that makes the attention algorithm polylogarithmic in B and 1/eps.
  • standard math Rank factorization with polynomially bounded factors, Lemma 3.14
    Used in the low-rank attention theorem; cited to Hopcroft-Kannan and Roughgarden-Valiant lecture notes rather than proved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Subquadratic Algorithms and Hardness for Attention with Any Temperature." pith.science (2026). https://pith.science/paper/EM76QJS5

@misc{pith2026250514840,
  author       = {Pith},
  title        = {Pith review of: Subquadratic Algorithms and Hardness for Attention with Any Temperature},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EM76QJS5}},
  note         = {Machine review of arXiv:2505.14840}
}
abstract

Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length $n$. Alman and Song [NeurIPS 2023] showed that when the head dimension $d = \Theta(\log n)$, subquadratic Attention is possible if and only if the inputs have small entries bounded by $B = o(\sqrt{\log n})$ in absolute values, under the Strong Exponential Time Hypothesis ($\mathsf{SETH}$). Equivalently, subquadratic Attention is possible if and only if the softmax is applied with high temperature for $d=\Theta(\log n)$. Running times of these algorithms depend exponentially on $B$ and thus they do not lead to even a polynomial-time algorithm outside the specific range of $B$. This naturally leads to the question: when can Attention be computed efficiently without strong assumptions on temperature? Are there fast attention algorithms that scale polylogarithmically with entry size $B$? In this work, we resolve this question and characterize when fast Attention for arbitrary temperatures is possible. First, for all constant $d = O(1)$, we give the first subquadratic $\tilde{O}(n^{2 - 1/d} \cdot \mathrm{polylog}(B))$ time algorithm for Attention with large $B$. Our result holds even for matrices with large head dimension if they have low rank. In this regime, we also give a similar running time for Attention gradient computation, and therefore for the full LLM training process. Furthermore, we show that any substantial improvement on our algorithm is unlikely. In particular, we show that even when $d = 2^{\Theta(\log^* n)}$, Attention requires $n^{2 - o(1)}$ time under $\mathsf{SETH}$. Finally, in the regime where $d = \mathrm{poly}(n)$, we show that the standard algorithm is optimal under popular fine-grained complexity assumptions.

Figures

Figures reproduced from arXiv: 2505.14840 by the authors.

Figure 1
Figure 1. Rounding based algorithm for 1-dimensional Attention illustrated for qi = 1. Each point is placed at kj and has value vj . Points (e.g. k1) such that qikj < qikmax −log(n/ε) are irrelevant and discarded (in this example qikmax − log(n/ε) = 1). Relevant points with similar kj (e.g. {k2, k3} or {k6, k7, k8}) are grouped together and assigned the same (rounded) key k. The width of each region is log(1 + ε) (in this exa… view at source ↗
Figure 2
Figure 2. Polynomial method algorithm for d-dimensional Attention illustrated for qi = (2, 1). Relevant points are in the shaded blue region. Irrelevant points are in the white region. Weights are omitted for clarity. Generalizing to Low Rank Matrices. To generalize the algorithm for low-rank matrices Q, K with rank r, we may decompose Q = UQV ⊤ Q , K = UKV ⊤ K where UQ, VQ, UK, VK are n × r matrices. Then, we obtain Theorem … view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Minimalist Softmax Attention Provably Learns Constrained Boolean Functions

    cs.LG 2025-05 reject novelty 5.0 of 10

    With teacher forcing that reveals pairwise products of the relevant bits, one gradient step lets a single-head attention recover the support of a k-bit AND/OR; the paper's claimed end-to-end hardness lower bound is in...

  2. Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse

    cs.LG 2025-05 reject novelty 4.0 of 10

    A residual self-attention network with all weight entries bounded by a small η can be approximated by one layer to error O(η)‖X‖∞, so skip connections do not prevent layer collapse.

Reference graph

Works this paper leans on

56 extracted references · 44 canonical work pages · cited by 2 Pith papers

  1. [1]

    Optimal-degree polynomial approximations for exponentials and gaussian kernel density estimation

    Amol Aggarwal and Josh Alman. Optimal-degree polynomial approximations for exponentials and gaussian kernel density estimation. In 37th Computational Complexity Conference (CCC) , 2022

    work page 2022

  2. [2]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams , Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2005--2039. SIAM , 2025

    work page 2025

  3. [3]

    Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl

    Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete and Computational Geometry , 6:407--422, 1991

    work page 1991

  4. [4]

    Finer-grained hardness of kernel density estimation

    Josh Alman and Yunfeng Guan. Finer-grained hardness of kernel density estimation. In Rahul Santhanam, editor, 39th Computational Complexity Conference , 2024

    work page 2024

  5. [5]

    Fast attention requires bounded entries

    Josh Alman and Zhao Song. Fast attention requires bounded entries. In Proceedings of the 37th International Conference on Neural Information Processing Systems . Curran Associates Inc., 2024

    work page 2024

  6. [6]

    The fine-grained complexity of gradient computation for training large language models

    Josh Alman and Zhao Song. The fine-grained complexity of gradient computation for training large language models. arXiv preprint arXiv:2402.04497 , 2024

    arXiv 2024

  7. [7]

    Atish Agarwala, Samuel Stern Schoenholz, Jeffrey Pennington, and Yann N. Dauphin. Temperature check: theory and practice for training models with softmax-cross-entropy losses. Trans. Mach. Learn. Res. , 2023, 2023

    work page 2023

  8. [8]

    More applications of the polynomial method to algorithm design

    Amir Abboud, Richard 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) , pages 218--230. SIAM , 2015

    work page 2015

Show all 56 references
  1. [9]

    More applications of the polynomial method to algorithm design

    Amir Abboud, Richard 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 . SIAM , 2015

    2015

  2. [10]

    Fundamental limitations on subquadratic alternatives to transformers

    Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In The Thirteenth International Conference on Learning Representations , 2025

    2025

  3. [11]

    Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)

    Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput. , 47(3):1087--1097, 2018

    2018

  4. [12]

    Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert - Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jef...

    2020

  5. [13]

    Algorithm and hardness for dynamic attention maintenance in large language models

    Jan van den Brand, Zhao Song, and Tianyi Zhou. Algorithm and hardness for dynamic attention maintenance in large language models. arXiv preprint arXiv:2304.02207 , 2023

    2023 arXiv

  6. [14]

    Scatterbrain: Unifying sparse and low-rank attention

    Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher R \' e . Scatterbrain: Unifying sparse and low-rank attention. In Neural Information Processing Systems, NeurIPS , 2021

    2021

  7. [15]

    On the hardness of approximate and exact (bichromatic) maximum inner product

    Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. In Proceedings of the 33rd Computational Complexity Conference (CCC) , 2018

    2018

  8. [16]

    Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference on Machine Learning, ICML , volume 119 of Proceedings of Machine Learning Research ,...

    2020

  9. [17]

    Colwell, and Adrian Weller

    Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tam \' a s Sarl \' o s, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with perfo...

    2021

  10. [18]

    Chan and Ryan Williams

    Timothy M. Chan and Ryan Williams. Deterministic APSP , orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky . In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1246--1255. SIAM , 2016

    2016

  11. [19]

    Approximation algorithms for min-distance problems in dags

    Mina Dalirrooyfard and Jenny Kaufmann. Approximation algorithms for min-distance problems in dags. In 48th International Colloquium on Automata, Languages, and Programming ICALP , 2021

    2021

  12. [20]

    A fast optimization view: Reformulating single layer attention in llm based on tensor and svm trick, and solving it in matrix multiplication time

    Yeqi Gao, Zhao Song, Weixin Wang, and Junze Yin. A fast optimization view: Reformulating single layer attention in llm based on tensor and svm trick, and solving it in matrix multiplication time. arXiv preprint arXiv:2309.07418 , 2023

    2023 arXiv

  13. [21]

    Fast quantum algorithm for attention computation

    Yeqi Gao, Zhao Song, Xin Yang, and Ruizhe Zhang. Fast quantum algorithm for attention computation. arXiv preprint arXiv:2307.08045 , 2023

    2023

  14. [22]

    Differentially private attention computation

    Yeqi Gao, Zhao Song, Xin Yang, and Yufa Zhou. Differentially private attention computation. arXiv preprint arXiv:2305.04701 , 2023

    2023 arXiv

  15. [23]

    Hyperattention: Long-context attention in near-linear time

    Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David Woodruff, and Amir Zandieh. Hyperattention: Long-context attention in near-linear time. In The Twelfth International Conference on Learning Representations , 2024

    2024

  16. [24]

    Singular value decomposition (svd)

    John Hopcroft and Ravi Kannan. Singular value decomposition (svd). https://www.cs.cmu.edu/ venkatg/teaching/CStheory-infoage/book-chapter-4.pdf. Accessed: 2024-12-21

    2024

  17. [25]

    Adco: Adversarial contrast for efficient learning of unsupervised representations from self-trained negative adversaries

    Qianjiang Hu, Xiao Wang, Wei Hu, and Guo - Jun Qi. Adco: Adversarial contrast for efficient learning of unsupervised representations from self-trained negative adversaries. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR , pages 1074--1083. Computer Vision ...

    2021

  18. [26]

    On the complexity of k-sat

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences , 62(2):367--375, 2001

    2001

  19. [27]

    Dynamic temperature scaling in contrastive self-supervised learning for sensor-based human activity recognition

    Bulat Khaertdinov, Stylianos Asteriadis, and Esam Ghaleb. Dynamic temperature scaling in contrastive self-supervised learning for sensor-based human activity recognition. IEEE Trans. Biom. Behav. Identity Sci. , 4(4):498--507, 2022

    2022

  20. [28]

    Temperature schedules for self-supervised contrastive methods on long-tail data

    Anna Kukleva, Moritz B \" o hle, Bernt Schiele, Hilde Kuehne, and Christian Rupprecht. Temperature schedules for self-supervised contrastive methods on long-tail data. In The Eleventh International Conference on Learning Representations, ICLR , 2023

    2023

  21. [29]

    Reformer: The efficient transformer

    Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, ICLR , 2020

    2020

  22. [30]

    Polysketchformer: Fast transformers via sketching polynomial kernels

    Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: Fast transformers via sketching polynomial kernels. In Forty-first International Conference on Machine Learning , 2024

    2024

  23. [31]

    Transformers are rnns: Fast autoregressive transformers with linear attention

    Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and Fran c ois Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, ICML , 2020

    2020

  24. [32]

    On the computational complexity of self-attention

    Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde. On the computational complexity of self-attention. In International Conference on Algorithmic Learning Theory , pages 597--619. PMLR, 2023

    2023

  25. [33]

    Efficient partition trees

    Ji r \' Matou s ek. Efficient partition trees. Discrete and Computational Geometry , 8(1):315--334, 1992

    1992

  26. [34]

    Dystress: Dynamically scaled temperature in self-supervised contrastive learning

    Siladittya Manna, Soumitri Chattopadhyay, Rakesh Dey, Saumik Bhattacharya, and Umapada Pal. Dystress: Dynamically scaled temperature in self-supervised contrastive learning. CoRR , abs/2308.01140, 2023

    2023 arXiv

  27. [35]

    Fine-tuning language models with just forward passes

    Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems , 36:53038--53075, 2023

    2023

  28. [36]

    Trainable transformer in transformer

    Abhishek Panigrahi, Sadhika Malladi, Mengzhou Xia, and Sanjeev Arora. Trainable transformer in transformer. In Fortieth International Conference on Machine Learning (ICML) , 2023

    2023

  29. [37]

    Can contrastive learning avoid shortcut solutions? In Advances in Neural Information Processing Systems NeurIPS 34 , 2021

    Joshua Robinson, Li Sun, Ke Yu, Kayhan Batmanghelich, Stefanie Jegelka, and Suvrit Sra. Can contrastive learning avoid shortcut solutions? In Advances in Neural Information Processing Systems NeurIPS 34 , 2021

    2021

  30. [38]

    The singular value decomposition (svd) and low-rank matrix approximations

    Tim Roughgarden and Gregory Valiant. The singular value decomposition (svd) and low-rank matrix approximations. https://web.stanford.edu/class/cs168/l/l9.pdf. Accessed: 2024-12-21

    2024

  31. [39]

    Fast approximation algorithms for the diameter and radius of sparse graphs

    Liam Roditty and Virginia Vassilevska Williams . Fast approximation algorithms for the diameter and radius of sparse graphs. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC . ACM , 2013

    2013

  32. [40]

    Understanding transformer reasoning capabilities via graph algorithms

    Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. In Advances in Neural Information Processing Systems , 2024

    2024

  33. [41]

    Hsu, and Matus Telgarsky

    Clayton Sanford, Daniel J. Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. In Advances in Neural Information Processing Systems , 2023

    2023

  34. [42]

    Transformers, parallel computation, and logarithmic depth

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. In Forty-first International Conference on Machine Learning, ICML , 2024

    2024

  35. [43]

    I / O complexity of attention, or how optimal is F lash A ttention? In Proceedings of the 41st International Conference on Machine Learning , 2024

    Barna Saha and Christopher Ye. I / O complexity of attention, or how optimal is F lash A ttention? In Proceedings of the 41st International Conference on Machine Learning , 2024

    2024

  36. [44]

    Solving attention kernel regression problem via pre-conditioner

    Zhao Song, Junze Yin, and Lichen Zhang. Solving attention kernel regression problem via pre-conditioner. In International Conference on Artificial Intelligence and Statistics , pages 208--216. PMLR, 2024

    2024

  37. [45]

    All pairs shortest paths in undirected graphs with integer weights

    Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS) , pages 605--615. IEEE Computer Society, 1999

    1999

  38. [46]

    Gomez, Lukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Neural Information Processing Systems NeurIPS , 2017

    2017

  39. [47]

    Understanding contrastive representation learning through alignment and uniformity on the hypersphere

    Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In Proceedings of the 37th International Conference on Machine Learning, ICML , volume 119 of Proceedings of Machine Learning Research , page...

    2020

  40. [48]

    A new algorithm for optimal constraint satisfaction and its implications

    Ryan Williams. A new algorithm for optimal constraint satisfaction and its implications. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP) , 2004

    2004

  41. [49]

    Ryan Williams

    R. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput. , 47(5), 2018

    2018

  42. [50]

    Understanding the behaviour of contrastive loss

    Feng Wang and Huaping Liu. Understanding the behaviour of contrastive loss. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR , pages 2495--2504. Computer Vision Foundation / IEEE , 2021

    2021

  43. [51]

    Exploring the impact of temperature scaling in softmax for classification and adversarial robustness

    Hao Xuan, Bokai Yang, and Xingyu Li. Exploring the impact of temperature scaling in softmax for classification and adversarial robustness. CoRR , abs/2502.20604, 2025

    2025 arXiv

  44. [52]

    On constructing minimum spanning trees in k-dimensional spaces and related problems

    Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. Siam Journal on Computing , 11(4):721--736, 1982

    1982

  45. [53]

    Depth-width tradeoffs in algorithmic reasoning of graph tasks with transformers

    Gilad Yehudai, Clayton Sanford, Maya Bechler - Speicher, Orr Fischer, Ran Gilad - Bachrach, and Amir Globerson. Depth-width tradeoffs in algorithmic reasoning of graph tasks with transformers. CoRR , abs/2503.01805, 2025

    2025 arXiv

  46. [54]

    Big bird: Transformers for longer sequences

    Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Onta \ n \' o n, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. In Neural Information Processing Systems, NeurIPS , 2020

    2020

  47. [55]

    Kdeformer: Accelerating transformers via kernel density estimation

    Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. Kdeformer: Accelerating transformers via kernel density estimation. In International Conference on Machine Learning , pages 40605--40623. PMLR, 2023

    2023

  48. [56]

    All pairs shortest paths using bridging sets and rectangular matrix multiplication

    Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM , 49(3):289--317, 2002

    2002

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.