Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform

Josh Alman; Zhao Song

REVIEW 4 major objections 5 minor 2 cited by

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read The authors give the first provably almost linear-time algorithm for RoPE attention, and show its bounded-entry regime is tight under SETH.

desk verdict A genuinely novel algorithm for RoPE attention whose linear-attention core is correct, but the main theorem is not proved as written because the error analysis is omitted and the normalization is inconsistent. read the letter →

arxiv 2505.11892 v1 pith:ZUVKQJJC submitted 2025-05-17 cs.LG cs.DS

Josh Alman , Zhao Song This is my paper · ORCID

classification cs.LGcs.DS MSC 68Q1768Q2568W4065T50

keywords RoPEattentionrotarypositionembeddingalmostlineartimepolynomialmethodfastFouriertransformToeplitzmatricesfine-grainedcomplexitySETH

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

Rotary position embedding (RoPE) makes attention more expressive by rotating query and key vectors according to token position, but it also breaks the low-rank structure that made previous provably fast attention algorithms work. This paper claims that this obstacle can be overcome: when query, key, and value entries are bounded by $o(\sqrt{\log n})$ and the embedding dimension is $O(\log n)$, RoPE attention can be approximated to $1/\mathrm{poly}(n)$ additive error in $n^{1+o(1)}$ time. The result is not tied to one implementation detail: the proof handles a general class of relative-position attention matrices, and a matching conditional lower bound shows the bounded-entry assumption is necessary. If the paper is right, long-context transformers using RoPE no longer have a computational excuse for quadratic attention.

What carries the argument

A rescaled Toeplitz matrix is a matrix $D_1 C D_2$ with diagonal matrices $D_1, D_2$ and a Toeplitz matrix $C$, meaning $C_{i,j}$ depends only on $j-i$. The load-bearing lemma is that a polynomial $p$ of degree $\tilde d$ applied entry-wise to a sum of $k$ rescaled Toeplitz matrices produces a matrix expressible as $O(\binom{k+\tilde d}{\tilde d})$ rescaled Toeplitz matrices; with $k = O(d) = O(\log n)$ and $\tilde d = o(\log n)$, this is only $n^{o(1)}$ terms. Each term is fast because a Toeplitz matrix embeds into a circulant matrix, and circulant matrices are diagonalized by the discrete Fourier transform, so a matrix-vector product costs $O(n \log n)$. The polynomial used for $\exp$ on $[0,B]$ has degree $\Theta(\max\{\log(1/\epsilon)/\log(\log(1/\epsilon)/B), B\})$, which keeps the total exponent at $1+o(1)$ in the stated regime.

What would settle it

Run the algorithm on a concrete small instance, say $n = 2^{12}$, $d = 1$, with bounded query and key entries and a fixed rotation angle, and compare its output against a brute-force computation of $D^{-1}\exp(\cdot)V$: the claimed $1/\mathrm{poly}(n)$ guarantee fails if the sup-norm error does not shrink to $n^{-c}$ for every fixed $c$ as the polynomial degree grows like $\log n / \log(\log n / B)$ with $B = (\log n)^{0.49}$.

Watch

Extended reading notes

Core claim

The central claim is that the general problem ARAttC—attention with entries $\exp(Q_{i,*} W_{i-j} K_{j,*}^\top / \sqrt{d})$, where each $W_{i-j}$ is supported on an $O(d)$-size coordinate set and standard RoPE is the special case of block-diagonal $2\times 2$ rotations—can be solved in $n^{1+o(1)}$ time whenever $\epsilon = 1/\mathrm{poly}(n)$, $B = o(\sqrt{\log n})$, and $d = O(\log n)$ (Theorem 1.3). It further claims this is tight: for $B = \Theta(\sqrt{\log n})$, the Strong Exponential Time Hypothesis rules out any $O(n^{2-q})$ algorithm (Theorem 1.4). The algorithmic engine is a new variant of the polynomial method: rather than approximating the attention matrix by a low-rank matrix, the paper approximates it by a sum of $n^{o(1)}$ rescaled Toeplitz matrices, each of which can be multiplied by a vector in $O(n \log n)$ time using the fast Fourier transform. The lower bound shows that the regime boundary is forced by the input magnitudes, not by a limitation of the technique.

Load-bearing premise

The whole guarantee rests on an assertion the paper does not prove: that the error analysis for the fast attention algorithm carries over unchanged when the ordinary attention matrix is replaced by a sum of rotated, position-weighted matrices, including the division by the row-sum diagonal matrix that normalizes the attention output.

Editorial extensions

If this is right

RoPE attention can be approximated in $n^{1+o(1)}$ time for $B = o(\sqrt{\log n})$ and $d = O(\log n)$, matching the best known complexity regime for ordinary attention.
When $B = \Theta(\sqrt{\log n})$, no truly subquadratic algorithm exists unless SETH fails, so the bounded-entry condition is exactly what separates fast from slow.
Because the problem formulation ARAttC allows any relative-position weight matrices with $O(d)$ support, the algorithm covers RoPE variants with different angle schedules and rotation patterns, not only the standard one.
Every ingredient is a polynomial approximation followed by FFT-based Toeplitz products, so the algorithm is built from standard numerical primitives, although the paper does not include an empirical implementation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the same decomposition should also apply to any relative-position encoding whose pairwise interaction matrix is a sum of a few Toeplitz-style factors, since only Toeplitz structure and support size enter the runtime analysis.
If the matching lower bound is the whole story, position encoding itself is not the source of attention hardness; the combined theorems suggest entry size alone draws the line between near-linear and quadratic.
A practical offshoot would be an FFT-based approximate RoPE kernel using near-optimal polynomials of modest degree; whether numerical stability permits it is testable, but the paper does not address it.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

You should know two things about this one. First, the central algorithmic idea is real: representing the RoPE attention matrix as a sum of rescaled Toeplitz matrices, approximating exp entrywise with a polynomial, and using FFT for each monomial is a genuinely new combination, and Section 4's linear-attention case is clean and correct. Second, the main theorem for softmax attention is not actually proved in the text. Theorem C.3's proof ends after the runtime calculation with 'the error analysis remains identical to prior attention algorithms using the polynomial method [AS23], thus we omit the details here.' That sentence is load-bearing. The error in A, the error in D=diag(A 1_n), and the amplification when multiplying by D^{-1} all need to be shown for the rescaled-Toeplitz setting, and they aren't. The lower bound is a one-line reduction to AS23 by taking W_i=I, which is fine.

There's also a normalization inconsistency. Definition 1.1 writes the exponent divided by sqrt(d), while Remark 1.2 and the surrounding discussion say the normalization is 1/d. Under the definition as written, with B=o(sqrt(log n)), the exponent range is o((log n)^{3/2}), and the polynomial degree from Lemma 3.1 is not o(log n), so the n^{1+o(1)} runtime doesn't follow. That looks like a typo rather than a deep flaw — the 1/d version gives degree o(log n) and the monomial count n^{o(1)} — but it needs fixing.

What the paper does well: the algebra of rescaled Toeplitz matrices is handled carefully, the decomposition into O(d) one-sparse Toeplitz terms is transparent, and the FFT-based matrix-vector multiplication is correct. The high-level strategy of applying polynomial approximations to structured families other than low-rank matrices is worth taking seriously.

Where the soft spots actually are: the missing error analysis is the big one. I would not be surprised if the argument can be completed with standard exp-approximation and D^{-1} bounds — B=o(sqrt(log n)) gives enough slack — but as written the main theorem is not established. The 'identical to AS23' claim is doing real work and should be verified or replaced with a derivation.

Who this is for: people working on fine-grained complexity of attention and on fast implementations of RoPE. The paper deserves a serious referee, but the referee should ask the authors to supply the omitted error analysis and reconcile the normalization. My recommendation: send to peer review, but expect major revision before it's publishable.

Referee Report

4 major / 5 minor

Summary. The paper claims an almost linear-time algorithm for approximating RoPE attention (ARAttC) in the bounded-entry regime B = o(sqrt(log n)), d = O(log n), with 1/poly(n) additive error, together with a SETH-based lower bound at B = Theta(sqrt(log n)). The approach decomposes the RoPE attention matrix into a sum of rescaled Toeplitz matrices, expands a low-degree polynomial approximation of exp over these components, and uses FFT for fast matrix-vector products. The linear-attention case in Section 4 is analyzed cleanly. The exponential case in Appendix C, however, contains an incomplete proof and a normalization inconsistency, so the main upper-bound theorem is not established as written.

Significance. If the upper-bound claim were established, this would be a significant extension of the Alman-Song bounded-entry attention result to rotary position embeddings, showing the same almost-linear-time / SETH-threshold picture for a more expressive and widely used attention variant. The algebraic observation that entrywise products and polynomials of rescaled Toeplitz matrices remain rescaled Toeplitz matrices, and the combination of the polynomial method with FFT, are novel and likely of independent interest. The linear-attention reduction in Section 4 is correct and clean. However, the exponential-case proof currently omits the error analysis for the additive guarantee, and the normalization mismatch makes the stated runtime unsupported; on the present evidence the main theorem is not established.

major comments (4)

[Definition 1.1 / Remark 1.2 / Theorem C.3] Definition 1.1 defines A_{i,j} with division by sqrt(d), while Remark 1.2 states that the normalization factor is 1/d. Under Definition 1.1 as written, |Q_{i,*} W_{i-j} K_{j,*}^T|/sqrt(d) is at most B^2 sqrt(d) = o((log n)^{3/2}) when d = O(log n) and B = o(sqrt(log n)). The degree g from Lemma 3.1 with range R = B^2 sqrt(d) is then not o(log n); for example, when B = sqrt(log n)/sqrt(log log n) and d = log n, R = log^{3/2} n / log log n and g = Omega(R), which is not o(log n). Consequently the monomial count |M| = binom(k+g,g) with k = O(log n) is not n^{o(1)}, and the claimed n^{1+o(1)} runtime in Theorem C.3 does not follow. If the intended normalization is 1/d, then Definition 1.1, the theorem statements, and the lower-bound reduction must be revised consistently.
[Appendix C.3, Theorem C.3] The proof ends with 'The error analysis remains identical to prior attention algorithms using the polynomial method [AS23], thus we omit the details here.' This is load-bearing: the additive-error guarantee of Theorem 1.3 requires bounding the entrywise approximation error of exp by the polynomial, the error in D = diag(A 1_n), the error in A V, and the amplification when multiplying by D^{-1}. In the RoPE setting the underlying matrix is a sum of rescaled Toeplitz matrices rather than a low-rank matrix, so the AS23 error analysis does not transfer automatically; in particular, one must justify that the diagonal entries of D are not too small or otherwise handle the division by D. As written, the 1/poly(n) additive-error claim is unproved.
[Section 3.2 / Theorem C.3] Lemma 3.1 supplies a polynomial approximation of exp on the interval [0,B], but Definition 1.1 does not restrict Q, K, or W to nonnegative entries, so the RoPE exponents M_{i,j} can be negative. The proof of Theorem C.3 never specifies how the polynomial is applied for negative exponents or provides a symmetric-interval approximation. Until this is addressed, the polynomial step is not justified for valid ARAttC instances.
[Appendix B.2, Theorem B.3] The lower-bound proof says that picking all W_i = I_d makes RoPE attention equal to classical attention. With Definition 1.1 as written, this yields exp(Q_{i,*} K_{j,*}^T / sqrt(d)), not the exp(Q_{i,*} K_{j,*}^T / d) problem treated in [AS23]. Under the 1/d normalization stated in Remark 1.2, the identity choice would work, but then the published definition must be corrected. As written, the reduction in Theorem B.3 is invalid; a scaled choice such as W_i = d^{-1/2} I_d, or an equivalent normalization fix, is needed.

minor comments (5)

[Title] The title contains a spacing typo: 'Fa st Fourier Transform' should read 'Fast Fourier Transform'.
[Section C.1 heading] The heading 'The running time of hamadard product of rescaled Toeplitz matrix multiplying a vector' should read 'Hadamard product'.
[Definition 4.2 / Definition 1.1] Definition 4.2 defines S as the support of the W_i matrices, while Definition 1.1 treats S as a given set with supp(W_i) subset of S; the relationship between these two uses should be stated consistently.
[Section 3.1] The sentence 'We prove folklore fact for explaining the connection between nearly-linear and almost-linear' is awkward; the fact is proved in Appendix A and should be referenced there.
[Theorem B.3] The proof of the lower bound does not spell out how the constants C, Ca, and Cb are obtained from the AS23 reduction; please provide the parameter mapping.

Circularity Check

2 steps flagged · score 4.0 of 10

The rescaled-Toeplitz/FFT algorithm is genuinely new and not fitted, but Theorem C.3's additive-error guarantee is asserted to be identical to the authors' own AS23 error analysis and then omitted, making the central proof load-bearing on a self-citation; a separate sqrt(d)-versus-d normalization gap undercuts the claimed polynomial degree.

self citation load bearing [Appendix C.3, proof of Theorem C.3 (restatement of Theorem 1.3), final sentence]
"The error analysis remains identical to prior attention algorithms using the polynomial method [AS23], thus we omit the details here."

Theorem C.3's entire correctness guarantee is the additive 1/poly(n) error bound for ARAttC = D^{-1}AV. The proof supplies only the rescaled-Toeplitz decomposition and the runtime count; it then closes by asserting, without derivation, that every error-propagation step from AS23 applies unchanged. That assertion is load-bearing: if the polynomial approximation error, the error in D = diag(A1_n), the error in AV, and the D^{-1} amplification are not literally identical for a sum of rescaled Toeplitz matrices, the claimed guarantee does not follow. The paper exhibits no such identity, so the central correctness claim rests on an unverified self-citation rather than on a proof contained in the paper.
other [Definition 1.1 versus Remark 1.2; Theorem C.3 proof, choice of polynomial degree]
"Ai,j := exp(Qi,∗ Wi−j K⊤j,∗ / √ d) ... Remark 1.2: Note that the 1/d factor inside exp in the definition of A is a normalization factor."

The proof fixes the polynomial degree from Lemma 3.1 as ~d = o(log n) and then asserts |M| = n^{o(1)}. Under Definition 1.1 as written, the exponent is divided by sqrt(d), not d, so its magnitude is bounded by B^2 sqrt(d) = o((log n)^{3/2}), not by B. Lemma 3.1's degree must cover that larger range, which need not be o(log n); for example B = (log n)^{1/4} and d = log n give degree Theta(log n), so the claimed n^{1+o(1)} runtime does not follow. This is not a by-construction circularity, but it is a missing-support step in the derivation chain.

full rationale

The core algorithm is not circular: it genuinely decomposes the RoPE attention matrix into a sum of rescaled Toeplitz matrices through a polynomial expansion and then applies FFT-based matrix-vector products, with no parameter fitted to the target output. Lemma 3.1 is imported from the authors' earlier AA22 paper, but it is a stated parameter-free polynomial approximation theorem with assumptions that do not include the target result, so it counts as independent support. The lower bound in Theorem B.3 is a legitimate reduction: setting every W to the identity makes ARAttC coincide with classical attention, so importing the AS23 lower bound is a valid reduction rather than circularity. The circularity-relevant defect is in the proof of Theorem C.3: the additive-error guarantee is not proved but is asserted to be 'identical' to the authors' own prior AS23 analysis and then omitted, and the runtime depends on a polynomial-degree bound that conflicts with the sqrt(d) normalization in Definition 1.1. I weight the self-citation import as load-bearing, giving score 4, while treating the normalization issue as a separate correctness gap rather than as by-construction circularity. As written, Theorem 1.3 would need a full error-propagation proof for the rescaled-Toeplitz setting and a consistent normalization to be established.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

No numeric fitting occurs in this theory paper. The central claim rests on standard FFT facts, the low-degree polynomial approximation lemma from AA22, SETH, and crucially on the paper's unproven assertion that the omitted error analysis is identical to AS23. The only new construct is the rescaled Toeplitz matrix, which is a mathematical definition rather than an empirical entity.

assumptions (6)

domain assumption Strong Exponential Time Hypothesis (SETH)
Used for the lower bound Theorem 1.4, which is a conditional hardness result.
standard math Polynomial approximation of exp on [0,B] with degree g (Lemma 3.1 from AA22)
External result imported to approximate exp by a low-degree polynomial; co-authored by the first author but published separately.
standard math FFT-based multiplication of circulant and Toeplitz matrices in O(n log n) time
Classical Fact 3.3 and Fact 3.5, used as the workhorse for the rescaled Toeplitz multiplications.
ad hoc to paper The omitted error analysis for the approximation of D^{-1}AV is identical to that in AS23
Asserted without proof in Theorem C.3; this is the load-bearing gap that the central guarantee depends on.
domain assumption The bounded-entry regime B = o(sqrt(log n)) is representative of practical attention inputs
Motivates the problem; no empirical validation is provided.
domain assumption The support S of the W matrices has size O(d) and RoPE rotation matrices satisfy this support bound
Needed to keep the number of Toeplitz terms at O(d), which is essential for the n^{o(1)} term count.

invented entities (1)

Rescaled Toeplitz matrix
purpose: A new matrix class M = D1 C D2 with C Toeplitz, used to decompose the RoPE attention matrix into a small sum of FFT-amenable pieces.
Defined in Definition 3.7; it is an internal mathematical tool, not a physical entity, so no external falsifiable handle exists.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform." pith.science (2026). https://pith.science/paper/ZUVKQJJC

@misc{pith2026250511892,
  author       = {Pith},
  title        = {Pith review of: Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZUVKQJJC}},
  note         = {Machine review of arXiv:2505.11892}
}

read the original abstract

The transformer architecture has been widely applied to many machine learning tasks. A main bottleneck in the time to perform transformer computations is a task called attention computation. [Alman and Song, NeurIPS 2023] have shown that in the bounded entry regime, there is an almost linear time algorithm to approximate the attention computation. They also proved that the bounded entry assumption is necessary for a fast algorithm assuming the popular Strong Exponential Time Hypothesis. A new version of transformer which uses position embeddings has recently been very successful. At a high level, position embedding enables the model to capture the correlations between tokens while taking into account their position in the sequence. Perhaps the most popular and effective version is Rotary Position Embedding (RoPE), which was proposed by [Su, Lu, Pan, Murtadha, Wen, and Liu, Neurocomputing 2024]. A main downside of RoPE is that it complicates the attention computation problem, so that previous techniques for designing almost linear time algorithms no longer seem to work. In this paper, we show how to overcome this issue, and give a new algorithm to compute the RoPE attention in almost linear time in the bounded entry regime. (Again, known lower bounds imply that bounded entries are necessary.) Our new algorithm combines two techniques in a novel way: the polynomial method, which was used in prior fast attention algorithms, and the Fast Fourier Transform.

Discussion (0). Continue with ORCID 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

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...
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

214 extracted references · 23 canonical work pages · cited by 2 Pith papers

[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 Proceedings of the 37th Computational Complexity Conference , pages 1--23, 2022

2022
[2]

Gpt-4 technical report

Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 , 2023

arXiv 2023
[3]

Computational complexity: a modern approach

Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009

2009
[4]

A fast algorithm for aperiodic linear stencil computation using fast fourier transforms

Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Yimin Zhu. A fast algorithm for aperiodic linear stencil computation using fast fourier transforms. ACM Transactions on Parallel Computing , 10(4):1--34, 2023

2023
[5]

Linear attention is (maybe) all you need (to understand transformer optimization)

Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. Linear attention is (maybe) all you need (to understand transformer optimization). In The Twelfth International Conference on Learning Representations , 2024

2024
[6]

A few remarks on the operator norm of random toeplitz matrices

Rados aw Adamczak. A few remarks on the operator norm of random toeplitz matrices. Journal of Theoretical Probability , 23:85--108, 2010

2010
[7]

Introducing meta llama 3: The most capable openly available llm to date, 2024

Meta AI. Introducing meta llama 3: The most capable openly available llm to date, 2024. https://ai.meta.com/blog/meta-llama-3/

2024
[8]

Foundation models defining a new era in vision: a survey and outlook

Muhammad Awais, Muzammal Naseer, Salman Khan, Rao Muhammad Anwer, Hisham Cholakkal, Mubarak Shah, Ming-Hsuan Yang, and Fahad Shahbaz Khan. Foundation models defining a new era in vision: a survey and outlook. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2025

2025

Show all 214 references

[9]

The claude 3 model family: Opus, sonnet, haiku, 2024

Anthropic. The claude 3 model family: Opus, sonnet, haiku, 2024. https://www-cdn.anthropic.com/de8ba9b01c9ab7cbabf5c33b80b7bbc618857627/Model_Card_Claude_3.pdf

2024
[10]

Faster walsh-hadamard and discrete fourier transforms from matrix non-rigidity

Josh Alman and Kevin Rao. Faster walsh-hadamard and discrete fourier transforms from matrix non-rigidity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 455--462, 2023

2023
[11]

Fast attention requires bounded entries

Josh Alman and Zhao Song. Fast attention requires bounded entries. In NeurIPS , 2023

2023
[12]

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. In NeurIPS , 2024

2024
[13]

How to capture higher-order correlations? generalizing matrix softmax attention to kronecker computation

Josh Alman and Zhao Song. How to capture higher-order correlations? generalizing matrix softmax attention to kronecker computation. In ICLR , 2024

2024
[14]

Only large weights (and not skip connections) can prevent the perils of rank collapse

Josh Alman and Zhao Song. Only large weights (and not skip connections) can prevent the perils of rank collapse. In arxiv , 2025

2025
[15]

Normalized iterative hard thresholding: Guaranteed stability and performance

Thomas Blumensath and Mike E Davies. Normalized iterative hard thresholding: Guaranteed stability and performance. IEEE Journal of selected topics in signal processing , 4(2):298--309, 2010

2010
[16]

Stable video diffusion: Scaling latent video diffusion models to large datasets

Andreas Blattmann, Tim Dockhorn, Sumith Kulal, Daniel Mendelevitch, Maciej Kilian, Dominik Lorenz, Yam Levi, Zion English, Vikram Voleti, Adam Letts, et al. Stable video diffusion: Scaling latent video diffusion models to large datasets. arXiv preprint arXiv:2311.15127 , 2023

2023 arXiv
[17]

On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency , pages 610--623, 2021

Emily M Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency , pages 610--623, 2021

2021
[18]

Exploring alternatives to softmax function

Kunal Banerjee, Rishi Raj Gupta, Karthik Vyas, and Biswajit Mishra. Exploring alternatives to softmax function. arXiv preprint arXiv:2011.11538 , 2020

2011 arXiv
[19]

Language models are few-shot learners

Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems (NeurIPS) , 33:1877--1901, 2020

1901
[20]

An improved estimate in the restricted isometry problem

Jean Bourgain. An improved estimate in the restricted isometry problem. In Geometric aspects of functional analysis , pages 65--70. Springer, 2014

2014
[21]

Longformer: The long-document transformer

Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150 , 2020

2004 arXiv
[22]

Training (overparametrized) neural networks in near-linear time

Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (overparametrized) neural networks in near-linear time. ITCS , 2021

2021
[23]

Convex optimization: Algorithms and complexity

S \'e bastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8(3-4):231--357, 2015

2015
[24]

Crawling facebook for social network analysis purposes

Salvatore A Catanese, Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, and Alessandro Provetti. Crawling facebook for social network analysis purposes. In Proceedings of the international conference on web intelligence, mining and semantics , pages 1--8, 2011

2011
[25]

High-order matching for one-step shortcut diffusion models

Bo Chen, Chengyue Gong, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, and Mingda Wan. High-order matching for one-step shortcut diffusion models. arXiv preprint arXiv:2502.00688 , 2025

2025 arXiv
[26]

Generating long sequences with sparse transformers

Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509 , 2019

1904 arXiv
[27]

Scaling instruction-finetuned language models

Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. Scaling instruction-finetuned language models. arXiv preprint arXiv:2210.11416 , 2022

arXiv
[28]

Dihan: A novel dynamic hierarchical graph attention network for fake news detection

Ya-Ting Chang, Zhibo Hu, Xiaoyu Li, Shuiqiao Yang, Jiaojiao Jiang, and Nan Sun. Dihan: A novel dynamic hierarchical graph attention network for fake news detection. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management , pages 197--206, 2024

2024
[29]

Fast gradient computation for rope attention in almost linear time

Yifang Chen, Jiayan Huo, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. Fast gradient computation for rope attention in almost linear time. arXiv preprint arXiv:2412.17316 , 2024

2024
[30]

Kernel density estimation through density constrained near neighbor search

Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. Kernel density estimation through density constrained near neighbor search. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 172--183. IEEE, 2020

2020
[31]

Circuit complexity bounds for rope-based transformer architecture

Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, and Zhao Song. Circuit complexity bounds for rope-based transformer architecture. arXiv preprint arXiv:2411.07602 , 2024

2024 arXiv
[32]

Hsr-enhanced sparse attention acceleration

Bo Chen, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. Hsr-enhanced sparse attention acceleration. arXiv preprint arXiv:2410.10165 , 2024

2024 arXiv
[33]

Palm: Scaling language modeling with pathways

Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 , 2022

2022 arXiv
[34]

Active regression via linear-sample sparsification

Xue Chen and Eric Price. Active regression via linear-sample sparsification. In Conference on Learning Theory (COLT) , pages 663--695. PMLR, 2019

2019
[35]

Estimating the frequency of a clustered signal

Xue Chen and Eric Price. Estimating the frequency of a clustered signal. In ICALP , 2019

2019
[36]

Ld-pruner: Efficient pruning of latent diffusion models using task-agnostic insights

Thibault Castells, Hyoung-Kyu Song, Bo-Kyeong Kim, and Shinkook Choi. Ld-pruner: Efficient pruning of latent diffusion models using task-agnostic insights. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , pages 821--830, 2024

2024
[37]

Bronstein, and Max Hansmire

Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M. Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. In The Eleventh International Conference on Learni...

2023
[38]

An algorithm for the machine calculation of complex fourier series

James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation , 19(90):297--301, 1965

1965
[39]

Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE transactions on information theory , 52(12):5406--5425, 2006

Emmanuel J Candes and Terence Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE transactions on information theory , 52(12):5406--5425, 2006

2006
[40]

Flashattention-2: Faster attention with better parallelism and work partitioning

Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691 , 2023

2023 arXiv
[41]

Bert: Pre-training of deep bidirectional transformers for language understanding

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 , 2018

2018 arXiv
[42]

BERT : Pre-training of deep bidirectional transformers for language understanding

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT : Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North A merican Chapter of the Association for Computational Linguistics: Human Lan...

2019
[43]

Flashattention: Fast and memory-efficient exact attention with io-awareness

Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher R \'e . Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems , 35:16344--16359, 2022

2022
[44]

Attentive walk-aggregating graph neural networks

Mehmet F Demirel, Shengchao Liu, Siddhant Garg, Zhenmei Shi, and Yingyu Liang. Attentive walk-aggregating graph neural networks. Transactions on Machine Learning Research , 2022

2022
[45]

Randomized and deterministic attention sparsification algorithms for over-parameterized feature dimension

Yichuan Deng, Sridhar Mahadevan, and Zhao Song. Randomized and deterministic attention sparsification algorithms for over-parameterized feature dimension. arXiv preprint arXiv:2304.04397 , 2023

2023 arXiv
[46]

Swiftbrush v2: Make your one-step diffusion model better than its teacher

Trung Dao, Thuan Hoang Nguyen, Thanh Le, Duc Vu, Khoi Nguyen, Cuong Pham, and Anh Tran. Swiftbrush v2: Make your one-step diffusion model better than its teacher. In European Conference on Computer Vision , pages 176--192. Springer, 2024

2024
[47]

Sketch-gnn: Scalable graph neural networks with sublinear training complexity

Mucong Ding, Tahseen Rabbani, Bang An, Evan Wang, and Furong Huang. Sketch-gnn: Scalable graph neural networks with sublinear training complexity. In Advances in Neural Information Processing Systems , 2022

2022
[48]

Streaming kernel pca algorithm with small space

Yichuan Deng, Zhao Song, Zifan Wang, and Han Zhang. Streaming kernel pca algorithm with small space. arXiv preprint arXiv:2303.04555 , 2023

2023 arXiv
[49]

Superiority of softmax: Unveiling the performance edge over linear attention

Yichuan Deng, Zhao Song, and Tianyi Zhou. Superiority of softmax: Unveiling the performance edge over linear attention. arXiv preprint arXiv:2310.11685 , 2023

2023
[50]

Dynamic spatial-temporal graph convolutional neural networks for traffic forecasting

Zulong Diao, Xin Wang, Dafang Zhang, Yingru Liu, Kun Xie, and Shaoyao He. Dynamic spatial-temporal graph convolutional neural networks for traffic forecasting. In Proceedings of the AAAI conference on artificial intelligence , 2019

2019
[51]

Sparsegpt: Massive language models can be accurately pruned in one-shot

Elias Frantar and Dan Alistarh. Sparsegpt: Massive language models can be accurately pruned in one-shot. In International Conference on Machine Learning , pages 10323--10337. PMLR, 2023

2023
[52]

One step diffusion via shortcut models

Kevin Frans, Danijar Hafner, Sergey Levine, and Pieter Abbeel. One step diffusion via shortcut models. arXiv preprint arXiv:2410.12557 , 2024

2024 arXiv
[53]

Sagn: semantic adaptive graph network for skeleton-based human action recognition

Ziwang Fu, Feng Liu, Jiahao Zhang, Hanyang Wang, Chengyi Yang, Qing Xu, Jiayin Qi, Xiangling Fu, and Aimin Zhou. Sagn: semantic adaptive graph network for skeleton-based human action recognition. In Proceedings of the 2021 International Conference on Multimedia Retrieval , pag...

2021
[54]

Graph neural networks for social recommendation

Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference , pages 417--426, 2019

2019
[55]

Toeplitz and circulant matrices: A review

Robert M Gray et al. Toeplitz and circulant matrices: A review. Foundations and Trends in Communications and Information Theory , 2(3):155--239, 2006

2006
[56]

Making pre-trained language models better few-shot learners

Tianyu Gao, Adam Fisch, and Danqi Chen. Making pre-trained language models better few-shot learners. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing , 2021

2021
[57]

Llama-adapter v2: Parameter-efficient visual instruction model

Peng Gao, Jiaming Han, Renrui Zhang, Ziyi Lin, Shijie Geng, Aojun Zhou, Wei Zhang, Pan Lu, Conghui He, Xiangyu Yue, et al. Llama-adapter v2: Parameter-efficient visual instruction model. arXiv preprint arXiv:2304.15010 , 2023

2023 arXiv
[58]

Garey and David S

Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., USA, 1990

1990
[59]

On computational limits of flowar models: Expressivity and efficiency

Chengyue Gong, Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. On computational limits of flowar models: Expressivity and efficiency. arXiv preprint arXiv:2502.16490 , 2025

2025
[60]

Approximate sparse recovery: optimizing time and measurements

Anna C Gilbert, Yi Li, Ely Porat, and Martin J Strauss. Approximate sparse recovery: optimizing time and measurements. SIAM Journal on Computing , 41(2):436--453, 2012

2012
[61]

An over-parameterized exponential regression

Yeqi Gao, Sridhar Mahadevan, and Zhao Song. An over-parameterized exponential regression. arXiv preprint arXiv:2303.16504 , 2023

2023 arXiv
[62]

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
[63]

Differentially private attention computation

Yeqi Gao, Zhao Song, Xin Yang, and Yufa Zhou. Differentially private attention computation. In Neurips Safe Generative AI Workshop 2024 , 2024

2024
[64]

Image restoration by denoising diffusion models with iteratively preconditioned guidance

Tomer Garber and Tom Tirer. Image restoration by denoising diffusion models with iteratively preconditioned guidance. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , pages 25245--25254, 2024

2024
[65]

Parameter-efficient fine-tuning with discrete fourier transform

Ziqi Gao, Qichao Wang, Aochuan Chen, Zijing Liu, Bingzhe Wu, Liang Chen, and Jia Li. Parameter-efficient fine-tuning with discrete fourier transform. arXiv preprint arXiv:2405.03003 , 2024

2024 arXiv
[66]

Apple intelligence foundation language models

Tom Gunter, Zirui Wang, Chong Wang, Ruoming Pang, Andy Narayanan, Aonan Zhang, Bowen Zhang, Chen Chen, Chung-Cheng Chiu, David Qiu, et al. Apple intelligence foundation language models. arXiv preprint arXiv:2407.21075 , 2024

2024
[67]

Accelerated sparse neural training: A provable and efficient method to find n: m transposable masks

Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Joseph Naor, and Daniel Soudry. Accelerated sparse neural training: A provable and efficient method to find n: m transposable masks. Advances in neural information processing systems , 34:21099--21111, 2021

2021
[68]

Lightgcn: Simplifying and powering graph convolution network for recommendation

Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgcn: Simplifying and powering graph convolution network for recommendation. In SIGIR , 2020

2020
[69]

Nearly optimal sparse fourier transform

Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Nearly optimal sparse fourier transform. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC) , pages 563--578, 2012

2012
[70]

Simple and practical algorithm for sparse fourier transform

Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Simple and practical algorithm for sparse fourier transform. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages 1183--1194. SIAM, 2012

2012
[71]

Denoising diffusion probabilistic models

Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems , 33:6840--6851, 2020

2020
[72]

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
[73]

On computational limits of modern hopfield models: A fine-grained complexity analysis

Jerry Yao-Chieh 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 (ICML) , 2024

2024
[74]

The restricted isometry property of subsampled fourier matrices

Ishay Haviv and Oded Regev. The restricted isometry property of subsampled fourier matrices. In Geometric aspects of functional analysis , pages 163--179. Springer, 2017

2017
[75]

Video diffusion models

Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David J Fleet. Video diffusion models. Advances in Neural Information Processing Systems , 35:8633--8646, 2022

2022
[76]

Computational limits of low-rank adaptation (lora) for transformer-based models

Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computational limits of low-rank adaptation (lora) for transformer-based models. arXiv preprint arXiv:2406.03136 , 2024

2024 arXiv
[77]

Provably optimal memory capacity for modern hopfield models: Tight analysis for transformer-compatible dense associative memories

Jerry Yao-Chieh Hu, Dennis Wu, and Han Liu. Provably optimal memory capacity for modern hopfield models: Tight analysis for transformer-compatible dense associative memories. In Advances in Neural Information Processing Systems (NeurIPS) , volume 37, 2024

2024
[78]

On statistical rates of conditional diffusion transformers: Approximation, estimation and minimax optimality

Jerry Yao-Chieh Hu, Weimin Wu, Yi-Chen Lee, Yu-Chao Huang, Minshuo Chen, and Han Liu. On statistical rates of conditional diffusion transformers: Approximation, estimation and minimax optimality. In The Thirteenth International Conference on Learning Representations , 2025

2025
[79]

On statistical rates and provably efficient criteria of latent diffusion transformers (dits)

Jerry Yao-Chieh Hu, Weimin Wu, Zhao Song, and Han Liu. On statistical rates and provably efficient criteria of latent diffusion transformers (dits). arXiv preprint arXiv:2407.01079 , 2024

2024 arXiv
[80]

Lo RA : Low-rank adaptation of large language models

Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lo RA : Low-rank adaptation of large language models. In International Conference on Learning Representations , 2022

2022
[81]

On sparse modern hopfield model

Jerry Yao-Chieh Hu, Donglin Yang, Dennis Wu, Chenwei Xu, Bo-Yu Chen, and Han Liu. On sparse modern hopfield model. In Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS) , 2023

2023
[82]

Bigst: Linear complexity spatio-temporal graph neural network for traffic forecasting on large-scale road networks

Jindong Han, Weijia Zhang, Hao Liu, Tao Tao, Naiqiang Tan, and Hui Xiong. Bigst: Linear complexity spatio-temporal graph neural network for traffic forecasting on large-scale road networks. Proceedings of the VLDB Endowment , 17(5):1081--1090, 2024

2024
[83]

Sample-optimal fourier sampling in any constant dimension

Piotr Indyk and Michael Kapralov. Sample-optimal fourier sampling in any constant dimension. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages 514--523. IEEE, 2014

2014
[84]

(nearly) sample-optimal sparse fourier transform

Piotr Indyk, Michael Kapralov, and Eric Price. (nearly) sample-optimal sparse fourier transform. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 480--499. SIAM, 2014

2014
[85]

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
[86]

A robust multi-dimensional sparse fourier transform in the continuous setting

Yaonan Jin, Daogao Liu, and Zhao Song. A robust multi-dimensional sparse fourier transform in the continuous setting. In SODA , 2023

2023
[87]

A faster algorithm for solving general lps

Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general lps. In STOC , 2021

2021
[88]

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time

Michael Kapralov. Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 264--277, 2016

2016
[89]

Sample efficient estimation and recovery in sparse FFT via isolation on average

Michael Kapralov. Sample efficient estimation and recovery in sparse FFT via isolation on average. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 651--662. IEEE Computer Society, 2017

2017
[90]

Sparse finetuning for inference acceleration of large language models

Eldar Kurtic, Denis Kuznedelev, Elias Frantar, Michael Goin, and Dan Alistarh. Sparse finetuning for inference acceleration of large language models. arXiv preprint arXiv:2310.06927 , 2023

2023 arXiv
[91]

Reformer: The efficient transformer

Nikita Kitaev, ukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451 , 2020

2001 arXiv
[92]

On the power of preconditioning in sparse linear regression

Jonathan A Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi. On the power of preconditioning in sparse linear regression. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 550--561. IEEE, 2022

2021
[93]

Suprema of chaos processes and the restricted isometry property

Felix Krahmer, Shahar Mendelson, and Holger Rauhut. Suprema of chaos processes and the restricted isometry property. Communications on Pure and Applied Mathematics , 67(11):1877--1904, 2014

1904
[94]

Demonstrate-search-predict: Composing retrieval and language models for knowledge-intensive nlp

Omar Khattab, Keshav Santhanam, Xiang Lisa Li, David Hall, Percy Liang, Christopher Potts, and Matei Zaharia. Demonstrate-search-predict: Composing retrieval and language models for knowledge-intensive nlp. arXiv preprint arXiv:2212.14024 , 2022

2022 arXiv
[95]

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 , pages 5156--5165. PMLR, 2020

2020
[96]

Dimension-independent sparse fourier transform

Michael Kapralov, Ameya Velingker, and Amir Zandieh. Dimension-independent sparse fourier transform. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2709--2728. SIAM, 2019

2019
[97]

Semi-supervised classification with graph convolutional networks

Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR , 2016

2016
[98]

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
[99]

The power of scale for parameter-efficient prompt tuning

Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing . Association for Computational Linguistics, 2021

2021
[100]

Symbiotic graph neural networks for 3d skeleton-based human action recognition and motion prediction

Maosen Li, Siheng Chen, Xu Chen, Ya Zhang, Yanfeng Wang, and Qi Tian. Symbiotic graph neural networks for 3d skeleton-based human action recognition and motion prediction. IEEE transactions on pattern analysis and machine intelligence , 44(6):3316--3333, 2021

2021
[101]

Rsc: Accelerate graph neural networks training via randomized sparse computations

Zirui Liu, Shengyuan Chen, Kaixiong Zhou, Daochen Zha, Xiao Huang, and Xia Hu. Rsc: Accelerate graph neural networks training via randomized sparse computations. ICML , 2023

2023
[102]

Text generation with diffusion language models: A pre-training approach with continuous paragraph denoise

Zhenghao Lin, Yeyun Gong, Yelong Shen, Tong Wu, Zhihao Fan, Chen Lin, Nan Duan, and Weizhu Chen. Text generation with diffusion language models: A pre-training approach with continuous paragraph denoise. In International Conference on Machine Learning , pages 21051--21064. PMLR, 2023

2023
[103]

Prefix-tuning: Optimizing continuous prompts for generation

Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing . Association for C...

2021
[104]

Simulation of hypergraph algorithms with looped transformers

Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, and Zhen Zhuang. Simulation of hypergraph algorithms with looped transformers. arXiv preprint arXiv:2501.10688 , 2025

2025
[105]

Recovery guarantee of weighted low-rank approximation via alternating minimization

Yuanzhi Li, Yingyu Liang, and Andrej Risteski. Recovery guarantee of weighted low-rank approximation via alternating minimization. In International Conference on Machine Learning , pages 2358--2367. PMLR, 2016

2016
[106]

Fourier circuits in neural networks: Unlocking the potential of large language models in mathematical reasoning and modular arithmetic

Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song, and Tianyi Zhou. Fourier circuits in neural networks: Unlocking the potential of large language models in mathematical reasoning and modular arithmetic. arXiv preprint arXiv:2402.09469 , 2024

2024 arXiv
[107]

Fine-grained attention i/o complexity: Comprehensive analysis for backward passes

Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Fine-grained attention i/o complexity: Comprehensive analysis for backward passes. arXiv preprint arXiv:2410.09397 , 2024

2024
[108]

Conv-basis: A new paradigm for efficient attention inference and gradient computation in transformers

Yingyu Liang, Heshan Liu, Zhenmei Shi, Zhao Song, and Junze Yin. Conv-basis: A new paradigm for efficient attention inference and gradient computation in transformers. arXiv preprint arXiv:2405.05219 , 2024

2024 arXiv
[109]

Beyond linear approximations: A novel pruning approach for attention matrix

Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, and Yufa Zhou. Beyond linear approximations: A novel pruning approach for attention matrix. In The Thirteenth International Conference on Learning Representations , 2025

2025
[110]

Exploring the frontiers of softmax: Provable optimization, applications in diffusion model, and beyond

Chenyang Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. Exploring the frontiers of softmax: Provable optimization, applications in diffusion model, and beyond. arXiv preprint arXiv:2405.03251 , 2024

2024
[111]

A tighter complexity analysis of sparsegpt

Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. A tighter complexity analysis of sparsegpt. arXiv preprint arXiv:2408.12151 , 2024

2024 arXiv
[112]

Multi-layer transformers gradient can be approximated in almost linear time

Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, and Yufa Zhou. Multi-layer transformers gradient can be approximated in almost linear time. arXiv preprint arXiv:2408.13233 , 2024

2024 arXiv
[113]

Differential privacy mechanisms in neural tangent kernel regression

Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. Differential privacy mechanisms in neural tangent kernel regression. arXiv preprint arXiv:2407.13621 , 2024

2024 arXiv
[114]

Differential privacy of cross-attention with provable guarantee

Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Differential privacy of cross-attention with provable guarantee. arXiv preprint arXiv:2407.14717 , 2024

2024
[115]

Tensor attention training: Provably efficient learning of higher-order transformers

Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Tensor attention training: Provably efficient learning of higher-order transformers. arXiv preprint arXiv:2405.16411 , 2024

2024
[116]

Deterministic sparse fourier transform for continuous signals with frequency gap

Xiaoyu Li, Zhao Song, and Shenghao Xie. Deterministic sparse fourier transform for continuous signals with frequency gap. In ICML , 2025

2025
[117]

The llama 3 herd of models

AI @ Meta Llama Team. The llama 3 herd of models. arXiv preprint arXiv:2407.21783 , 2024

2024 arXiv
[118]

Finding trainable sparse networks through neural tangent transfer

Tianlin Liu and Friedemann Zenke. Finding trainable sparse networks through neural tangent transfer. In International Conference on Machine Learning , pages 6336--6347. PMLR, 2020

2020
[119]

Score-based generative diffusion models for social recommendations

Chengyi Liu, Jiahao Zhang, Shijie Wang, Wenqi Fan, and Qing Li. Score-based generative diffusion models for social recommendations. arXiv preprint arXiv:2412.15579 , 2024

2024 arXiv
[120]

Some results on random circulant matrices

Mark W Meckes. Some results on random circulant matrices. In High dimensional probability V: the Luminy volume , volume 5, pages 213--224. Institute of Mathematical Statistics, 2009

2009
[121]

Deepcache: Accelerating diffusion models for free

Xinyin Ma, Gongfan Fang, and Xinchao Wang. Deepcache: Accelerating diffusion models for free. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition , pages 15762--15772, 2024

2024
[122]

Mm1: Methods, analysis & insights from multimodal llm pre-training

Brandon McKinzie, Zhe Gan, Jean-Philippe Fauconnier, Sam Dodge, Bowen Zhang, Philipp Dufter, Dhruti Shah, Xianzhi Du, Futang Peng, Floris Weers, et al. Mm1: Methods, analysis & insights from multimodal llm pre-training. arXiv preprint arXiv:2403.09611 , 2024

2024 arXiv
[123]

Cross-task generalization via natural language crowdsourcing instructions

Swaroop Mishra, Daniel Khashabi, Chitta Baral, and Hannaneh Hajishirzi. Cross-task generalization via natural language crowdsourcing instructions. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics , 2022

2022
[124]

Great power, great responsibility: Recommendations for reducing energy for training language models

Joseph McDonald, Baolin Li, Nathan Frey, Devesh Tiwari, Vijay Gadepally, and Siddharth Samsi. Great power, great responsibility: Recommendations for reducing energy for training language models. In Findings of the Association for Computational Linguistics: NAACL 2022 , pages 1...

2022
[125]

The nature of computation

Cristopher Moore and Stephan Mertens. The nature of computation. The Nature of Computation. , 08 2011

2011
[126]

The threshold for super-resolution via extremal functions

Ankur Moitra. The threshold for super-resolution via extremal functions. In STOC . arXiv preprint arXiv:1408.1681, 2015

2015 arXiv
[127]

Preconditioned score-based generative models

Hengyuan Ma, Xiatian Zhu, Jianfeng Feng, and Li Zhang. Preconditioned score-based generative models. International Journal of Computer Vision , pages 1--27, 2025

2025
[128]

Show your work: Scratchpads for intermediate computation with language models

Maxwell Nye, Anders Johan Andreassen, Gur AriGuy, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114 , 2021

2021 arXiv
[129]

New constructions of rip matrices with fast multiplication and fewer rows

Jelani Nelson, Eric Price, and Mary Wootters. New constructions of rip matrices with fast multiplication and fewer rows. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 1515--1528. Society for Industrial and Applied Mathematics, 2014

2014
[130]

IGLU : Efficient GCN training via lazy updates

S Deepak Narayanan, Aditya Sinha, Prateek Jain, Purushottam Kar, and SUNDARARAJAN SELLAMANICKAM. IGLU : Efficient GCN training via lazy updates. In International Conference on Learning Representations , 2022

2022
[131]

(nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless

Vasileios Nakos, Zhao Song, and Zhengyu Wang. (nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1568--1577. IEEE, 2019

2019
[132]

Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit

Deanna Needell and Roman Vershynin. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE Journal of selected topics in signal processing , 4(2):310--316, 2010

2010
[133]

Lazy diffusion transformer for interactive image editing

Yotam Nitzan, Zongze Wu, Richard Zhang, Eli Shechtman, Daniel Cohen-Or, Taesung Park, and Micha \"e l Gharbi. Lazy diffusion transformer for interactive image editing. In European Conference on Computer Vision , pages 55--72. Springer, 2024

2024
[134]

Hello gpt-4o

OpenAI. Hello gpt-4o. https://openai.com/index/hello-gpt-4o/, 2024. Accessed: May 14

2024
[135]

Introducing openai o1-preview

OpenAI. Introducing openai o1-preview. https://openai.com/index/introducing-openai-o1-preview/, 2024. Accessed: September 12

2024
[136]

Training language models to follow instructions with human feedback

Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems , 2022

2022
[137]

Learning graph convolutional network for skeleton-based human action recognition by neural searching

Wei Peng, Xiaopeng Hong, Haoyu Chen, and Guoying Zhao. Learning graph convolutional network for skeleton-based human action recognition by neural searching. In Proceedings of the AAAI conference on artificial intelligence , 2020

2020
[138]

A robust sparse F ourier transform in the continuous setting

Eric Price and Zhao Song. A robust sparse F ourier transform in the continuous setting. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 583--600. IEEE, 2015

2015
[139]

Is solving graph neural tangent kernel equivalent to training graph neural network? arXiv preprint arXiv:2309.07452 , 2023

Lianke Qin, Zhao Song, and Baocheng Sun. Is solving graph neural tangent kernel equivalent to training graph neural network? arXiv preprint arXiv:2309.07452 , 2023

2023 arXiv
[140]

Theory and application of digital signal processing

Lawrence R Rabiner, Bernard Gold, and CK Yuen. Theory and application of digital signal processing. IEEE Transactions on Systems, Man, and Cybernetics , 8(2):146--146, 1978

1978
[141]

Improving language understanding by generative pre-training

Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. Improving language understanding by generative pre-training. OpenAI Research , 2018

2018
[142]

Restricted isometries for partial random circulant matrices

Holger Rauhut, Justin Romberg, and Joel A Tropp. Restricted isometries for partial random circulant matrices. Applied and Computational Harmonic Analysis , 32(2):242--254, 2012

2012
[143]

Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting

Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf. Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting. In International conference on machine learning , pages 8857--8868. PMLR, 2021

2021
[144]

Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context

Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap, Jean-baptiste Alayrac, Radu Soricut, Angeliki Lazaridou, Orhan Firat, Julian Schrittwieser, et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv pre...

2024 arXiv
[145]

Weighted low rank approximations with provable guarantees

Ilya Razenshteyn, Zhao Song, and David P Woodruff. Weighted low rank approximations with provable guarantees. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 250--263, 2016

2016
[146]

Dynamic tensor product regression

Aravind Reddy, Zhao Song, and Lichen Zhang. Dynamic tensor product regression. In Conference on Neural Information Processing Systems (NeurIPS) , pages 4791--4804, 2022

2022
[147]

On sparse reconstruction from fourier and gaussian measurements

Mark Rudelson and Roman Vershynin. On sparse reconstruction from fourier and gaussian measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , 61(8):1025--1045, 2008

2008
[148]

Language models are unsupervised multitask learners

Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog , 1(8):9, 2019

2019
[149]

Roformer: Enhanced transformer with rotary position embedding

Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing , 568:127063, 2024

2024
[150]

Simple and effective masked diffusion language models

Subham Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. Advances in Neural Information Processing Systems , 37:130136--130184, 2024

2024
[151]

wav2vec: Unsupervised pre-training for speech recognition

Steffen Schneider, Alexei Baevski, Ronan Collobert, and Michael Auli. wav2vec: Unsupervised pre-training for speech recognition. In Proc. Interspeech 2019 , pages 3465--3469, 2019

2019
[152]

The trade-off between universality and label efficiency of representations from contrastive learning

Zhenmei Shi, Jiefeng Chen, Kunyang Li, Jayaram Raghuram, Xi Wu, Yingyu Liang, and Somesh Jha. The trade-off between universality and label efficiency of representations from contrastive learning. In The Eleventh International Conference on Learning Representations , 2023

2023
[153]

Retentive network: A successor to transformer for large language models

Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models. arXiv preprint arXiv:2307.08621 , 2023

2023 arXiv
[154]

On the real complexity of a complex dft

Igor Sergeevich Sergeev. On the real complexity of a complex dft. Problems of Information Transmission , 53(3):284--293, 2017

2017
[155]

M. Sipser. Introduction to the Theory of Computation . Thomson Course Technology, 2006

2006
[156]

Linear transformers are secretly fast weight programmers

Imanol Schlag, Kazuki Irie, and J \"u rgen Schmidhuber. Linear transformers are secretly fast weight programmers. In International Conference on Machine Learning . PMLR, 2021

2021
[157]

A simple and effective pruning approach for large language models

Mingjie Sun, Zhuang Liu, Anna Bair, and J Zico Kolter. A simple and effective pruning approach for large language models. In The Twelfth International Conference on Learning Representations , 2024

2024
[158]

Denoising diffusion implicit models

Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations , 2021

2021
[159]

Sparse multiple kernel learning for signal processing applications

Niranjan Subrahmanya and Yung C Shin. Sparse multiple kernel learning for signal processing applications. IEEE Transactions on Pattern Analysis and Machine Intelligence , 32(5):788--798, 2009

2009
[160]

Score-based generative modeling through stochastic differential equations

Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations , 2021

2021
[161]

Black-box tuning for language-model-as-a-service

Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for language-model-as-a-service. In International Conference on Machine Learning . PMLR, 2022

2022
[162]

Quartic samples suffice for fourier interpolation

Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang. Quartic samples suffice for fourier interpolation. In FOCS , pages 1414--1425. IEEE , 2023

2023
[163]

Lazydit: Lazy learning for the acceleration of diffusion transformers

Xuan Shen, Zhao Song, Yufa Zhou, Bo Chen, Yanyu Li, Yifan Gong, Kai Zhang, Hao Tan, Jason Kuen, Henghui Ding, et al. Lazydit: Lazy learning for the acceleration of diffusion transformers. In AAAI , 2025

2025
[164]

Lazydit: Lazy learning for the acceleration of diffusion transformers

Xuan Shen, Zhao Song, Yufa Zhou, Bo Chen, Yanyu Li, Yifan Gong, Kai Zhang, Hao Tan, Jason Kuen, Henghui Ding, et al. Lazydit: Lazy learning for the acceleration of diffusion transformers. In Proceedings of the AAAI Conference on Artificial Intelligence , 2025

2025
[165]

Numerical pruning for efficient autoregressive models

Xuan Shen, Zhao Song, Yufa Zhou, Bo Chen, Jing Liu, Ruiyi Zhang, Ryan A Rossi, Hao Tan, Tong Yu, Xiang Chen, et al. Numerical pruning for efficient autoregressive models. In AAAI , 2025

2025
[166]

Why larger language models do in-context learning differently? In R0-FoMo: Robustness of Few-shot and Zero-shot Learning in Large Foundation Models , 2023

Zhenmei Shi, Junyi Wei, Zhuoyan Xu, and Yingyu Liang. Why larger language models do in-context learning differently? In R0-FoMo: Robustness of Few-shot and Zero-shot Learning in Large Foundation Models , 2023

2023
[167]

Oblivious sketching-based central path method for linear programming

Zhao Song and Zheng Yu. Oblivious sketching-based central path method for linear programming. In International Conference on Machine Learning , pages 9835--9847. PMLR, 2021

2021
[168]

A nearly-optimal bound for fast regression with _ guarantee

Zhao Song, Mingquan Ye, Junze Yin, and Lichen Zhang. A nearly-optimal bound for fast regression with _ guarantee. In ICML . arXiv preprint arXiv:2302.00248, 2023

2023 arXiv
[169]

A nearly-optimal bound for fast regression with _ guarantee

Zhao Song, Mingquan Ye, Junze Yin, and Lichen Zhang. A nearly-optimal bound for fast regression with _ guarantee. In International Conference on Machine Learning (ICML) , pages 32463--32482. PMLR, 2023

2023
[170]

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 (AISTATS) , pages 208--216. PMLR, 2024

2024
[171]

Decoupled dynamic spatial-temporal graph neural network for traffic forecasting

Zezhi Shao, Zhao Zhang, Wei Wei, Fei Wang, Yongjun Xu, Xin Cao, and Christian S Jensen. Decoupled dynamic spatial-temporal graph neural network for traffic forecasting. Proceedings of the VLDB Endowment , 15(11):2733--2746, 2022

2022
[172]

Training multi-layer over-parametrized neural network in subquadratic time

Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training multi-layer over-parametrized neural network in subquadratic time. ITCS , 2024

2024
[173]

Gemini: a family of highly capable multimodal models

Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805 , 2023

2023 arXiv
[174]

Transformer dissection: a unified understanding of transformer's attention via the lens of kernel

Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. Transformer dissection: a unified understanding of transformer's attention via the lens of kernel. arXiv preprint arXiv:1908.11775 , 2019

1908 arXiv
[175]

Degree-quant: Quantization-aware training for graph neural networks

Shyam Anil Tailor, Javier Fernandez-Marques, and Nicholas Donald Lane. Degree-quant: Quantization-aware training for graph neural networks. In International Conference on Learning Representations , 2021

2021
[176]

Llama: Open and efficient foundation language models

Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timoth \'e e Lacroix, Baptiste Rozi \`e re, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971 , 2023

2023 arXiv
[177]

Llama 2: Open foundation and fine-tuned chat models

Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 , 2023

2023 arXiv
[178]

Csdi: Conditional score-based diffusion models for probabilistic time series imputation

Yusuke Tashiro, Jiaming Song, Yang Song, and Stefano Ermon. Csdi: Conditional score-based diffusion models for probabilistic time series imputation. Advances in neural information processing systems , 34:24804--24816, 2021

2021
[179]

Transformers learn in-context by gradient descent

Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, Jo \ a o Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning . PMLR, 2023

2023
[180]

Scalable-effort classifiers for energy-efficient machine learning

Swagath Venkataramani, Anand Raghunathan, Jie Liu, and Mohammed Shoaib. Scalable-effort classifiers for energy-efficient machine learning. In Proceedings of the 52nd annual design automation conference , pages 1--6, 2015

2015
[181]

Attention is all you need

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems , 30, 2017

2017
[182]

Symbol tuning improves in-context learning in language models

Jerry Wei, Le Hou, Andrew Kyle Lampinen, Xiangning Chen, Da Huang, Yi Tay, Xinyun Chen, Yifeng Lu, Denny Zhou, Tengyu Ma, and Quoc V Le. Symbol tuning improves in-context learning in language models. In The 2023 Conference on Empirical Methods in Natural Language Processing , 2023

2023
[183]

ST anhop: Sparse tandem hopfield model for memory-enhanced time series prediction

Dennis Wu, Jerry Yao-Chieh Hu, Weijian Li, Bo-Yu Chen, and Han Liu. ST anhop: Sparse tandem hopfield model for memory-enhanced time series prediction. In The Twelfth International Conference on Learning Representations (ICLR) , 2024

2024
[184]

On some fine-grained questions in algorithms and complexity

Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018 , pages 3447--3487. World Scientific, 2018

2018
[185]

Linformer: Self-attention with linear complexity

Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768 , 2020

2006 arXiv
[186]

Simplifying graph convolutional networks

Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning , pages 6861--6871. Pmlr, 2019

2019
[187]

Chain-of-thought prompting elicits reasoning in large language models

Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems , 35:24824--24837, 2022

2022
[188]

Diffusion recommender model

Wenjie Wang, Yiyan Xu, Fuli Feng, Xinyu Lin, Xiangnan He, and Tat-Seng Chua. Diffusion recommender model. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval , pages 832--841, 2023

2023
[189]

Alignab: Pareto-optimal energy alignment for designing nature-like antibodies

Yibo Wen, Chenwei Xu, Jerry Yao-Chieh Hu, and Han Liu. Alignab: Pareto-optimal energy alignment for designing nature-like antibodies. arXiv preprint arXiv:2412.20984 , 2024

2024
[190]

Bishop: Bi-directional cellular learning for tabular data with generalized sparse modern hopfield model

Chenwei Xu, Yu-Chao Huang, Jerry Yao-Chieh Hu, Weijian Li, Ammar Gilani, Hsi-Sheng Goan, and Han Liu. Bishop: Bi-directional cellular learning for tabular data with generalized sparse modern hopfield model. In Forty-first International Conference on Machine Learning (ICML) , 2024

2024
[191]

Lazygnn: Large-scale graph neural networks via lazy propagation

Rui Xue, Haoyu Han, Mohamadali Torkamani, Jian Pei, and Xiaorui Liu. Lazygnn: Large-scale graph neural networks via lazy propagation. In ICML , 2024

2024
[192]

Geometric latent diffusion models for 3d molecule generation

Minkai Xu, Alexander S Powers, Ron O Dror, Stefano Ermon, and Jure Leskovec. Geometric latent diffusion models for 3d molecule generation. In International Conference on Machine Learning , pages 38592--38610. PMLR, 2023

2023
[193]

Improving foundation models for few-shot learning via multitask finetuning

Zhuoyan Xu, Zhenmei Shi, Junyi Wei, Yin Li, and Yingyu Liang. Improving foundation models for few-shot learning via multitask finetuning. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models , 2023

2023
[194]

Towards few-shot adaptation of foundation models via multitask finetuning

Zhuoyan Xu, Zhenmei Shi, Junyi Wei, Fangzhou Mu, Yin Li, and Yingyu Liang. Towards few-shot adaptation of foundation models via multitask finetuning. In The Twelfth International Conference on Learning Representations , 2024

2024
[195]

Evidence-aware fake news detection with graph neural networks

Weizhi Xu, Junfei Wu, Qiang Liu, Shu Wu, and Liang Wang. Evidence-aware fake news detection with graph neural networks. In Proceedings of the ACM web conference 2022 , pages 2501--2510, 2022

2022
[196]

Weighted sgd for ell\_p regression with randomized preconditioning

Jiyan Yang, Yin-Lam Chow, Christopher R \'e , and Michael W Mahoney. Weighted sgd for ell\_p regression with randomized preconditioning. Journal of Machine Learning Research , 18(211):1--43, 2018

2018
[197]

Graph convolutional neural networks for web-scale recommender systems

Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD , 2018

2018
[198]

Deep fractional fourier transform

Hu Yu, Jie Huang, Lingzhi Li, Feng Zhao, et al. Deep fractional fourier transform. Advances in Neural Information Processing Systems , 36:72761--72773, 2023

2023
[199]

Generate what you prefer: Reshaping sequential recommendation via guided diffusion

Zhengyi Yang, Jiancan Wu, Zhicai Wang, Xiang Wang, Yancheng Yuan, and Xiangnan He. Generate what you prefer: Reshaping sequential recommendation via guided diffusion. Advances in Neural Information Processing Systems , 36:24247--24261, 2023

2023
[200]

Griffiths, Yuan Cao, and Karthik R Narasimhan

Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023

2023
[201]

Q8bert: Quantized 8bit bert

Ofir Zafrir, Guy Boudoukh, Peter Izsak, and Moshe Wasserblat. Q8bert: Quantized 8bit bert. In 2019 Fifth Workshop on Energy Efficient Machine Learning and Cognitive Computing-NeurIPS Edition (EMC2-NIPS) , pages 36--39. IEEE, 2019

2019
[202]

The hedgehog & the porcupine: Expressive linear attentions with softmax mimicry

Michael Zhang, Kush Bhatia, Hermann Kumbong, and Christopher R \'e . The hedgehog & the porcupine: Expressive linear attentions with softmax mimicry. In ICLR , 2024

2024
[203]

Trained transformers learn linear models in-context

Ruiqi Zhang, Spencer Frei, and Peter L Bartlett. Trained transformers learn linear models in-context. arXiv preprint arXiv:2306.09927 , 2023

2023 arXiv
[204]

Big bird: Transformers for longer sequences

Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems , 33:17283--17297, 2020

2020
[205]

Improving social network embedding via new second-order continuous graph neural networks

Yanfu Zhang, Shangqian Gao, Jian Pei, and Heng Huang. Improving social network embedding via new second-order continuous graph neural networks. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining , pages 2515--2523, 2022

2022
[206]

Kdeformer: Accelerating transformers via kernel density estimation

Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. Kdeformer: Accelerating transformers via kernel density estimation. In ICML . arXiv preprint arXiv:2302.02451, 2023

2023 arXiv
[207]

Llama-adapter: Efficient fine-tuning of language models with zero-init attention

Renrui Zhang, Jiaming Han, Aojun Zhou, Xiangfei Hu, Shilin Yan, Pan Lu, Hongsheng Li, Peng Gao, and Yu Qiao. Llama-adapter: Efficient fine-tuning of language models with zero-init attention. arXiv preprint arXiv:2303.16199 , 2023

2023 arXiv
[208]

The expressive power of low-rank adaptation

Yuchen Zeng and Kangwook Lee. The expressive power of low-rank adaptation. In The Twelfth International Conference on Learning Representations , 2024

2024
[209]

LIMA : Less is more for alignment

Chunting Zhou, Pengfei Liu, Puxin Xu, Srini Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, LILI YU, Susan Zhang, Gargi Ghosh, Mike Lewis, Luke Zettlemoyer, and Omer Levy. LIMA : Less is more for alignment. In Thirty-seventh Conference on Neural Information Process...

2023
[210]

Step-back prompting enables reasoning via abstraction in large language models

Huaixiu Steven Zheng, Swaroop Mishra, Xinyun Chen, Heng-Tze Cheng, Ed H Chi, Quoc V Le, and Denny Zhou. Step-back prompting enables reasoning via abstraction in large language models. In The Twelfth International Conference on Learning Representations , 2024

2024
[211]

Opt: Open pre-trained transformer language models

Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068 , 2022

2022 arXiv
[212]

Qksan: A quantum kernel self-attention network

Ren-Xin Zhao, Jinjing Shi, and Xuelong Li. Qksan: A quantum kernel self-attention network. TPAMI , 2024

2024
[213]

Calibrate before use: Improving few-shot performance of language models

Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. In International Conference on Machine Learning . PMLR, 2021

2021
[214]

Linear-time graph neural networks for scalable recommendations

Jiahao Zhang, Rui Xue, Wenqi Fan, Xin Xu, Qing Li, Jian Pei, and Xiaorui Liu. Linear-time graph neural networks for scalable recommendations. In Proceedings of the ACM Web Conference 2024 , pages 3533--3544, 2024

2024

Pith tools

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

[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 Proceedings of the 37th Computational Complexity Conference , pages 1--23, 2022

2022

[2] [2]

Gpt-4 technical report

Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 , 2023

arXiv 2023

[3] [3]

Computational complexity: a modern approach

Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009

2009

[4] [4]

A fast algorithm for aperiodic linear stencil computation using fast fourier transforms

Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Yimin Zhu. A fast algorithm for aperiodic linear stencil computation using fast fourier transforms. ACM Transactions on Parallel Computing , 10(4):1--34, 2023

2023

[5] [5]

Linear attention is (maybe) all you need (to understand transformer optimization)

Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. Linear attention is (maybe) all you need (to understand transformer optimization). In The Twelfth International Conference on Learning Representations , 2024

2024

[6] [6]

A few remarks on the operator norm of random toeplitz matrices

Rados aw Adamczak. A few remarks on the operator norm of random toeplitz matrices. Journal of Theoretical Probability , 23:85--108, 2010

2010

[7] [7]

Introducing meta llama 3: The most capable openly available llm to date, 2024

Meta AI. Introducing meta llama 3: The most capable openly available llm to date, 2024. https://ai.meta.com/blog/meta-llama-3/

2024

[8] [8]

Foundation models defining a new era in vision: a survey and outlook

Muhammad Awais, Muzammal Naseer, Salman Khan, Rao Muhammad Anwer, Hisham Cholakkal, Mubarak Shah, Ming-Hsuan Yang, and Fahad Shahbaz Khan. Foundation models defining a new era in vision: a survey and outlook. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2025

2025