Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation • Hacker News Board

Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation

#101

Post by cs702 » Fri, Feb 06, 2026, 2:35 PM UTC

yorwba wrote: post #57

amluto wrote: post #38

I skimmed the paper, and I think I completely lost the plot. Sections 2.1 through 2.4 talk about the decomposing the per-token-pair attention (key vector from the ith token with query vector from the jth token, where, in inference, the jth token is the one being sampled) into an approximation that is only mildly outrageously exponential in size compared to the original exponential-of-a-dot product. And they get somet…

> But the reason that attention is quadratic is that each token gets evaluated with respect to each other token. They haven't changed this at all. Section 2.5 seems like it's deferring this to an appendix. They defer it to the appendix because it's a standard construction (Q'K)V = Q'(KV), where Q'K is an n×n matrix and requires O(n²) to compute, but KV has a constant size and can be computed in O(n) time, and the mul…

> if you use enough terms in the Taylor expansion to get the same result as standard attention to within machine precision, the resulting constant state size should give you an upper bound for the amount of data the LLM can effectively retrieve from its context.

I think you've nailed it: Machine precision puts an upper bound (of constant size) on how much information an LLM can retrieve from its context.

Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation

#102

Post by kristjansson » Fri, Feb 06, 2026, 6:01 PM UTC

cptroot wrote: post #88

kristjansson wrote: post #65

Earlier quoted context omitted.

> approximately the same magnitude and they really do mean that, their results show +/- 1 on log10 plots.

I don't think this is an accurate characterization of the error magnitude? Their error plots (from appendix 3) are all showing `log_10(|Y - \dot{Y}|)` as having a median of ~-3 (difference of 0.001) and a max of ~1.5 (difference of 0.035), and this is with only 3 Taylor terms.

Oh you're right that is a misread on my part, the appendix charts don't say that. I think they're just useless then though? Since they're reporting absolute error (on a log10 scale) we can't assess the relative to compare to the 'within an order of magnitude' claim in the text.

Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation

#103

Post by fheinsen » Sat, Feb 07, 2026, 3:07 PM UTC

thomasahle wrote: post #9

There's a graveyard of 100s of papers with "approximate near linear time attention." They always hope the speed increase makes up for the lower quality, but it never does. The quadratic time seems inherent to the problem. Indeed, there are lower bounds showing that sub n^2 algorithms can't work: https://arxiv.org/pdf/2302.13214

Unlike previous efforts, which typically stop at a low-order (e.g., quadratic) term of the Taylor expansion, this work derives a succinct, efficient, parallel general method for approximating attention with any number of Taylor terms, to arbitrary precision.

The github repository's first toy example is with 8 Taylor terms, applied to a context of 1B tokens, with attention computed over 1K heads per token. (Note that applying the quadratic formulation to 1B tokens, each with 1K heads, is not practical with current hardware, because it would require computing 1K attention matrices, each with 1B×1B dot-product scores.

Like every other proposed method, this one must be tested too. If it works, AI service providers who ignore it will find themselves at a disadvantage.

It's worth mentioning also that the mathematical techniques introduced by this work are likely of interest for other applications besides attention.

Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation

#104

Post by fheinsen » Sat, Feb 07, 2026, 3:20 PM UTC

The github repository's first toy example is with 8 Taylor terms, applied to a context with 1B tokens, each token with 1K heads:

https://github.com/glassroom/sata_attention

That toy example is not practical with the quadratic formulation, because it would require computing and storing 1K attention matrices, each with 1B×1B dot-product scores. For example, at Float32 precision, those attention matrices would consume approximately 1K x 1B x 1B x 4 bytes = 3,725,290,298.5 Terabytes of memory, which is not practical.

Like every other proposed method, this one must be tested too. If it performs well in practice, AI service providers who ignore it will find themselves at a disadvantage.

Otherwise, the mathematical techniques introduced by this work are likely useful for other applications besides Transformer attention.