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

71–80 of 104 posts

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

#71

Post by antirez »

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.

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

#72

Post by logicchains »

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…

That's like saying sorting can be done in O(n) because radix sort exists. If you assume some structure, you lose generality, i.e. there'll be some problems it's no longer able to solve. It can no longer approximate any arbitrary function that needs perfect memory over the sequence.

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

#73

Post by logicchains »

naasking wrote: post #60
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.

Your argument just assumes there is no latent structure that can be exploited. That's a big assumption.

It's a necessary assumption for the universal approximation property; if you assume some structure then your LLM can no longer solve problems that don't fit into that structure as effectively.

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

#74

Post by logicchains »

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 has some properties like being cumulative. If we assume the sequence has any specific properties then we no longer have a general sequence model.

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

#75

Post by [deleted] »

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.

[deleted]

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

#76

Post by andy12_ »

cubefox wrote: post #56
andy12_ wrote: post #25

Earlier quoted context omitted.

It really isn't sub N^2. The main attention is only O(Nk), but only thanks to a lightning indexer that still has complexity O(N^2). So overall it still has the same complexity; just with a smaller constant factor [1] > DSA reduces the core attention complexity of the main model from O(L^2) to O(Lk), where k ( [1] https://arxiv.org/pdf/2512.02556

Okay, then let's see whether we are going to see real linear architectures, like Gated DeltaNet or Mamba-3, in some larger models. I don't believe there is a "lower bound" which states that those can never get to (or exceed) the real-world performance of quadratic attention. (Perfect recall in unrealistic needle-in-haystack tests doesn't count.)

I'm also sure that some kind of linear architecture is possible. After all, humans don't have N^2 perfect recall either.

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

#77

Post by wetwater »

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. This from the paper mill for the paper mill.

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

#78

Post by naasking »

logicchains wrote: post #73
naasking wrote: post #60

Earlier quoted context omitted.

Your argument just assumes there is no latent structure that can be exploited. That's a big assumption.

It's a necessary assumption for the universal approximation property; if you assume some structure then your LLM can no longer solve problems that don't fit into that structure as effectively.

But language does have structure, as does logic and reasoning. Universal approximation is great when you don't know the structure and want to brute force search to find an approximate solution. That's not optimal by any stretch of the imagination though.

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

#79

Post by CrazyStat »

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…

One of my favorite bits of my PhD dissertation was factoring an intractable 3-dimensional integral

\iiint f(x, y, z) dx dy dz = \int [\int g(x, y) dx]*[\int h(y, z) dz] dy

which greatly accelerated numerical integration (O(n^2) rather than O(n^3)).

My advisor was not particularly impressed and objectively I could have skipped it and let the simulations take a bit longer (quite a bit longer--this integration was done millions of times for different function parameters in an inner loop). But it was clever and all mine and I was proud of it.

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

#80

Post by quotemstr »

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.
Post reply on HN