6 ms·
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
by thomasahle 8mo ago
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 https://arxiv.org/pdf/2302.13214
- deleted 8mo ago[deleted]
- cubefox 8mo agoI think DeepSeek V3.2 is sub n^2, but it clearly performs quite well, refuting the alleged lower bounds in the paper.
- deleted 8mo ago[deleted]
- andy12_ 8mo agoIt 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 (<< L) is the number of selected tokens. Although the lightning indexer still has a complexity of O(L^2), it requires much less computation compared with MLA in DeepSeek-V3.1-Terminus [1] https://arxiv.org/pdf/2512.02556 https://arxiv.org/pdf/2512.02556
- cubefox 8mo agoOkay, 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.)
- andy12_ 8mo agoI'm also sure that some kind of linear architecture is possible. After all, humans don't have N^2 perfect recall either.
- fheinsen 8mo agoAs 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 longer, analogous to an RNN: https://www.anthropic.com/engineering/effective-context-engineering-for-ai-agents https://www.anthropic.com/engineering/effective-context-engi...
- cubefox 8mo agoThat website says nothing about numerical error potentially causing context rot.
- fheinsen 8mo agoAs 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.
- cubefox 8mo agoThat 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.
- clarity_hacker 8mo ago[dead]
- cobolexpert 8mo agoDumb question: is the quadratic time complexity for training, inference, or both?
- omneity 8mo agoAttention is calculated during the forward pass of the model, which happens in both inference (forward only) and training (forward & backward).
- SubiculumCode 8mo agoDumb question: Can inference be done in a reverse pass? Outputs predicting inputs?
- root_axis 8mo agoSounds like a great premise for a sci-fi short story.
- anu7df 8mo agoSci-fi ? You mean historical fiction!
- gpm 8mo agoNot as trivially as the forwards direction, unsurprisingly information is lost, but better than you might expect. See for example https://arxiv.org/pdf/2405.15012 https://arxiv.org/pdf/2405.15012
- dave_universetf 8mo agoStrictly speaking: no. The "forward pass" terminology does not imply that there exists a "reverse pass" that does the same kind of computation. Rather, it's describing two different kinds of computation, and the direction they occur in. The forward pass is propagating from inputs to outputs, computing the thing the model was trained for. The reverse/backwards pass is propagating from outputs back to inputs, but it's calculating the gradients of parameters for training (rougly: how much changing each parameter in isolation affects the output, and whether it makes the output closer to the desired training output). The result of the "reverse pass" isn't a set of inputs, but a set of annotations on the model's parameters that guide their adjustment. The computations of the forward pass are not trivially reversible (e.g. they include additions, which destroys information about the operand values). As a sibling thread points out, you can still probabilistically explore what inputs _could_ produce a given output, and get some information back that way, but it's a lossy process. And of course, you could train a "reverse" model, one that predicts the prefix of a sequence given a suffix (trivially: it's the same suffix prediction problem, but you train it on reversed sequences). But that would be a separate model trained from scratch on that task, and in that model the prefix prediction would be its forward pass.
- kristjansson 8mo ago> self-attention is efficiently computable to arbitrary precision with constant cost per token This paper at least aspires to reproduce 'true' attention, which distinguishes it from many of the others. TBD if its successful in that.
- energy123 8mo agoIt's like claims of room temperature superconductors or millenium prize solutions. Earth shattering if true. It'd be such a black swan. Terrible for Nvidia.
- SeanAnderson 8mo agoWell, we solved one of the Millennium Prize problems (honestly kinda quickly) so maybe there's hope :)
- logicchains 8mo agoIt 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.
- hellohello2 8mo agoI'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.
- actionfromafar 8mo agoDoesn't that have to do with how many bits you allow in the actual calculation in physical reality?
- naasking 8mo agoI think any kind of innovation here will have to take advantage of some structure inherent to the problem, like eliminating attention in favour of geometric structures like Grassman flows [1]. [1] Attention Is Not What You Need, https://arxiv.org/abs/2512.19428 https://arxiv.org/abs/2512.19428
- findalex 8mo agoRight - e.g., if you're modeling a physical system it makes sense to bake in some physics - like symmetry.
- naasking 8mo agoIndeed, and I think natural language and reasoning will have some kind of geometric properties as well. Attention is just a sledgehammer that lets us brute force our way around not understanding that structure well. I think the next step change in AI/LLM abilities will be exploiting this geometry somehow [1,2]. [1] GrokAlign: Geometric Characterisation and Acceleration of Grokking, https://arxiv.org/abs/2510.09782 https://arxiv.org/abs/2510.09782 [2] The Geometry of Reasoning: Flowing Logics in Representation Space, https://arxiv.org/abs/2506.12284 https://arxiv.org/abs/2506.12284
- jcarreiro 8mo agoThe paper says that: > In practice, we find that four Taylor terms (P = 4) suffice for recovering conventional attention with elementwise errors of approximately the same magnitude as Float16 resolution, acceptable for many AI applications. ie., the claim is that this method reproduces the results of conventional attention, up to float16 numerical precision.
- fheinsen 8mo agoThe method is more general. The github repository's first example is with eight Taylor terms (P = 8).
- torginus 8mo agoI'm clueless about this whole thing, but from my EE education I remember that in general: Taylor approximations converge slowly in terms of error if the function they're representing is discontinuous (the error disappears quadratically if continuous, linearly if not), and they tend to create highly energetic swings near discontinuties (similarly to Fourier series with Gibbs oscillations). Moreover, Taylor series are inherently nonlinear, and much of the mathematical toolset around AI assumes general linearity (cue linear algebra), with the exception of sigmoids , and going beyond cubic approximations tends to make errors worse (as expressed in SNR).
- energy123 8mo agoIt converges on conventional attention as P goes up
- kristjansson 8mo ago> approximately the same magnitude and they really do mean that, their results show +/- 1 on log10 plots.
- cptroot 8mo agoI 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.
- WhitneyLand 8mo agoThe 2023 paper even if true doesn’t preclude the 2026 paper from being true, it just sets constraints on how a faster attention solution would have to work.
- antirez 8mo agoI 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.
- twotwotwo 8mo agoYeah, 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.
- wetwater 8mo agoI agree. This from the paper mill for the paper mill.
- quotemstr 8mo agoYou 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.
- polynomial 8mo agoRight, 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.
- fheinsen 8mo agoUnlike 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.