{"id":"70df5678-380e-46ba-9a47-6a67aabb003b","arxiv_id":"2505.11892","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new algorithm computes RoPE attention in n^{1+o(1)} time under bounded entries by decomposing the attention matrix into a small sum of rescaled Toeplitz matrices, then using FFT.","lead":"This theoretical paper gives an almost-linear-time algorithm for computing the attention matrix used by rotary position embedding (RoPE), a core component of models like Llama and Claude. It works when the entries of the query, key, and value matrices are small, the same bounded-entry regime where standard attention already had fast algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 1.1's 1/sqrt(d) normalization makes the exponent range o((log n)^{3/2}), so the claimed o(log n) polynomial degree and n^{1+o(1)} runtime do not follow; the omitted error analysis in Theorem C.3 leaves the additive guarantee unproved.","rationale":"The reader's verdict identifies the same central weakness: Theorem C.3 omits the entire error analysis. I agree that this is load-bearing and that the lower bound is a one-line reduction that receives no independent verification. However, I find an even more decisive issue in the formal problem definition itself: Definition 1.1 uses 1/sqrt(d), while Remark 1.2 claims 1/d. Under the definition's own normalization, the exponent entries can be as large as B^2 sqrt(d) = o((log n)^{3/2}), which is not o(log n) for many choices of B in the stated regime. Consequently, Lemma 3.1's degree bound and the resulting monomial count |M| do not yield n^{o(1)}; the runtime claim collapses. If the authors intended /d instead, the omitted error analysis is still a genuine gap, because the matrix being exponentiated is a sum of rescaled Toeplitz matrices rather than a low-rank matrix, so the AS23 error propagation does not transfer automatically. Both routes leave the central claim unproved as written. I therefore recommend rejecting the preprint in its current form, while noting that the linear-attention decomposition in Section 4 is correct and that the approach may be repairable with a corrected normalization and a full error analysis.","tokens_in":28067,"tokens_out":11238,"duration_ms":112732,"concrete_test":"Take d = log n, B = sqrt(log n)/sqrt(log log n), and choose Q, K, W so that max_{i,j} |Q_i W_{i-j} K_j^T| / sqrt(d) = Theta((log n)^{3/2} / log log n), as allowed by Definition 1.1. Apply Lemma 3.1 with eps = 1/poly(n) to get the polynomial degree deg, then compute log |M| = log O((|S| + deg choose deg)) with |S| = O(log n). If log |M| = Theta(log n log log n), the algorithm's running time is n^{Theta(log log n)} rather than n^{1+o(1)}, so Theorem 1.3 is false as written; if the normalization is instead changed to /d, the missing error analysis for D, AV, and D^{-1} must be supplied to verify the 1/poly(n) additive guarantee.","verdict_should_be":"REJECT","load_bearing_attack":"Definition 1.1 defines A_{i,j} = exp(Q_{i,*} W_{i-j} K_{j,*}^T / sqrt(d)), but Remark 1.2 says the normalization is 1/d. Under the definition as written, |Q_{i,*} W_{i-j} K_{j,*}^T| <= ||Q||_inf ||K||_inf ||W||_inf * d = B^2 d, so the exponent has magnitude up to B^2 sqrt(d) = o((log n)^{3/2}) when B = o(sqrt(log n)) and d = O(log n). Lemma 3.1 then requires polynomial degree Theta(max{log(1/eps)/log(log(1/eps)/R), R}) with R = o((log n)^{3/2}), which is not o(log n); the monomial count |M| = O((k + deg choose deg)) with k = O(log n) is not n^{o(1)} (for example, with B = sqrt(log n)/sqrt(log log n) it is n^{Theta(log log n)}), so the claimed n^{1+o(1)} running time in Theorem C.3 does not follow. If the /d normalization is the intended one, the proof of Theorem C.3 still stops at 'the error analysis remains identical to prior attention algorithms using the polynomial method [AS23]', without deriving the polynomial approximation error over the actual range, the error in D = diag(A 1_n), the error in A V, or the D^{-1} amplification for the rescaled-Toeplitz structure. Either way, Theorem 1.3 is not established as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":28403,"tokens_out":16093,"duration_ms":160717,"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":[{"comment":"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.","section":"Definition 1.1 / Remark 1.2 / Theorem C.3"},{"comment":"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":"Appendix C.3, Theorem C.3"},{"comment":"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.","section":"Section 3.2 / Theorem C.3"},{"comment":"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.","section":"Appendix B.2, Theorem B.3"}],"minor_comments":[{"comment":"The title contains a spacing typo: 'Fa st Fourier Transform' should read 'Fast Fourier Transform'.","section":"Title"},{"comment":"The heading 'The running time of hamadard product of rescaled Toeplitz matrix multiplying a vector' should read 'Hadamard product'.","section":"Section C.1 heading"},{"comment":"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":"Definition 4.2 / Definition 1.1"},{"comment":"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.","section":"Section 3.1"},{"comment":"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.","section":"Theorem B.3"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou 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.\n\nThere'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.\n\nWhat 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.\n\nWhere 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.\n\nWho 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.","headline":"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.","tokens_in":28949,"tokens_out":3832,"would_cite":true,"duration_ms":37333,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","68W40","65T50"],"pacs":[],"model":"deepseek-v4-flash","headline":"The authors give the first provably almost linear-time algorithm for RoPE attention, and show its bounded-entry regime is tight under SETH.","keywords":["RoPE attention","rotary position embedding","almost linear time","polynomial method","fast Fourier transform","Toeplitz matrices","fine-grained complexity","SETH"],"falsifier":"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}$.","tokens_in":27817,"feed_emoji":"⚡","tokens_out":12544,"duration_ms":112018,"temperature":0.7,"pith_summary":"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.","feed_headline":"RoPE attention gets an almost linear-time algorithm","feed_subtitle":"Polynomial approximation plus FFT brings rotary-position attention to near-linear time.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the prior almost linear-time attention algorithm via the polynomial method and its SETH lower bound; the lower bound here reduces to it by setting every RoPE weight matrix to the identity, and the omitted error analysis is asserted to transfer from it.","marker":"[AS23]"},{"why":"Provides the optimal-degree polynomial approximation of the exponential (Lemma 3.1), which determines the polynomial degree and therefore the $n^{o(1)}$ factor in the runtime.","marker":"[AA22]"},{"why":"Introduces the FFT algorithm underlying the $O(n \\log n)$ Toeplitz and circulant matrix-vector products.","marker":"[CT65]"},{"why":"Gives the diagonalization of circulant matrices by the discrete Fourier transform (Fact 3.3), the reason each rescaled Toeplitz factor multiplies quickly.","marker":"[G+06]"},{"why":"Records the Toeplitz-to-circulant embedding (Fact 3.5) used to reduce Toeplitz multiplication to FFT.","marker":"[LLS+24c]"},{"why":"Defines rotary position embedding with block-diagonal $2\\times 2$ rotation matrices and the standard angle schedule that ARAttC generalizes.","marker":"[SAL+24]"},{"why":"Introduces SETH, the conjecture on which the Theorem 1.4 lower bound is conditional.","marker":"[IP01]"}],"fun_headline_variants":["RoPE attention now near-linear via FFT and polynomial method","FFT plus polynomial method speeds up RoPE attention","Near-linear RoPE attention via polynomial and FFT","RoPE attention: polynomial meets FFT for almost linear time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["RoPE attention now near-linear via FFT and polynomial method","FFT plus polynomial method speeds up RoPE attention","Near-linear RoPE attention via polynomial and FFT","RoPE attention: polynomial meets FFT for almost linear time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001132,"raw_usage":{"total_tokens":4760,"prompt_tokens":1059,"completion_tokens":3701,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":3634}},"tokens_in":675,"tokens_out":3701,"duration_ms":26544,"temperature":1.0,"reasoning_tokens":3634,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:47:38.172707+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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}$.","supporting_citations":[],"review_version":1}