Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

arxiv.org

Post reply on HN
Print view View original

91–100 of 104 posts

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

#91

Post by sifar »

hellohello2 wrote: post #44
logicchains wrote: post #33

Earlier quoted context omitted.

It can't be successful at that any more than 1+1 can equal 3. Fundamentally, if every token wants to be able to look at every previous token without loss of information, it must be O(n^2); N tokens looking at N tokens is quadratic. Any sub-quadratic attention must hence necessarily lose some information and be unable to support perfect recall on longer sequences.

I'm not saying if the paper is correct or not (since I can't tell), but I don't think your argument really holds. Consider applying it to multiplication: Fundamentally, multiplication need to look at every pair of integer from the two input numbers. It must be O(n^2); N digits looking at N other digits is quadratic. Any sub-quadratic multiplication must hence necessarily lose some information.

Multiplication can be sub-quadratic using Karatsuba's algorithm.

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

#92

Post by polynomial »

quotemstr wrote: post #80
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

You can't stuff O(N) bits in O(1) space, so any scheme that purports, in general to do constant-time inference on unbounded context is snake oil, like a perpetual motion machine. Every such scheme must decay somehow. All you can do is choose how it decays.

Right, not to "defend" the paper's claims, but it seems to be more like tuning how the leaky bucket leaks, using lossy compression to try to preserve some measure of coherency? Seems to turn on the fixed size summary.

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

#94

Post by [deleted] »

orlp wrote: post #63
logicchains wrote: post #33

Earlier quoted context omitted.

It can't be successful at that any more than 1+1 can equal 3. Fundamentally, if every token wants to be able to look at every previous token without loss of information, it must be O(n^2); N tokens looking at N tokens is quadratic. Any sub-quadratic attention must hence necessarily lose some information and be unable to support perfect recall on longer sequences.

> N tokens looking at N tokens is quadratic Convolving two arrays can be done perfectly accurately in O(n log n), despite every element being combined with every other element. Or consider the even more basic sum of products a[i] * b[j] for all possible i, j: total = 0 for i in range(len(a)): for j in range(len(b)): total += a[i] * b[j] This can be computed in linear time as sum(a) * sum(b). Your logic that 'the resu…

[deleted]

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

#95

Post by cubefox »

fheinsen wrote: post #18
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

As the error via linear approximation approaches similar magnitude as numerical error via quadratic computation, don’t the two start becoming comparable in practice ? I ask because in practice , for inference, attention is typically computed with low-precision (4-bit, 8-bit, 16-bit) floats. Numerical error, in fact, may be a key factor as to why quadratic attention, in practice , exhibits context rot as context gets…

That website says nothing about numerical error potentially causing context rot.

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

#96

Post by twotwotwo »

antirez wrote: post #71
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

I agree with the fundamental idea that attention must be O(N^2), with the exception of recent DeepSeek sparse attention approach (DSA), that does not escape N^2 but attempts to lower constant times so much that N^2 is more acceptable, by creating a much faster layer that predicts high scoring tokens.

Yeah, this(-ish): there are shipping models that don't eliminate N^2 (if a model can repeat your code back with edits, it needs to reference everything somehow), but still change the picture a lot when you're thinking about, say, how resource-intensive a long-context coding session is.

There are other experiments where model designers mix full-attention layers with limited-memory ones. (Which still doesn't avoid N^2, but if e.g. 3/4 of layers use 'light' attention, it still improves efficiency a lot.) The idea is the model can still pull information from far back in context, just not in every layer. Use so far is limited to smaller models (maybe it costs too much model capability to use at the high end?) but it seems like another interesting angle on this stuff.

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

#97

Post by fheinsen »

cubefox wrote: post #95
fheinsen wrote: post #18

Earlier quoted context omitted.

As the error via linear approximation approaches similar magnitude as numerical error via quadratic computation, don’t the two start becoming comparable in practice ? I ask because in practice , for inference, attention is typically computed with low-precision (4-bit, 8-bit, 16-bit) floats. Numerical error, in fact, may be a key factor as to why quadratic attention, in practice , exhibits context rot as context gets…

That website says nothing about numerical error potentially causing context rot.

As far as I know, there is no widely accepted explanation for context rot.

Numerical error in long sequences of query-key dot-products may be a key factor.

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

#98

Post by cubefox »

korbip wrote: post #93

This was done already here as well: https://arxiv.org/abs/2507.04239

Sounds interesting, but...

> these models dominate both exponential attention and linear attention at long-context training

There is no exponential attention; standard attention is quadratic. Strange mistake.

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

#99

Post by cubefox »

fheinsen wrote: post #97
cubefox wrote: post #95

Earlier quoted context omitted.

That website says nothing about numerical error potentially causing context rot.

As far as I know, there is no widely accepted explanation for context rot. Numerical error in long sequences of query-key dot-products may be a key factor.

That should be easy to test: test a 16 bit model on various benchmarks, once with fresh context and once with the context filled up with irrelevant tokens. Record the relative performance degradation, and then do the same for a quantized model. Compare whether the quantized model has a significant relatively larger performance drop from context rot. If so, numerical error should be the cause.

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

#100

Post by nullc »

sifar wrote: post #91
hellohello2 wrote: post #44

Earlier quoted context omitted.

I'm not saying if the paper is correct or not (since I can't tell), but I don't think your argument really holds. Consider applying it to multiplication: Fundamentally, multiplication need to look at every pair of integer from the two input numbers. It must be O(n^2); N digits looking at N other digits is quadratic. Any sub-quadratic multiplication must hence necessarily lose some information.

Multiplication can be sub-quadratic using Karatsuba's algorithm.

That is the poster's point!
Post reply on HN