Earlier quoted context omitted.
Dumb question: Can inference be done in a reverse pass? Outputs predicting inputs?
Sounds like a great premise for a sci-fi short story.
Sci-fi ? You mean historical fiction!
Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
41–50 of 104 posts
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#42Neat result. The symmetry exploitation here reminds me of recent work connecting neural network training dynamics to renormalization group theory.
Charles Martin's SETOL paper https://arxiv.org/abs/2507.17912 shows that well-trained layers converge to something like an RG fixed point—the eigenvalue spectrum of the weight matrix develops power-law tails with exponent α ≈ 2, which is the signature of scale invariance. At this fixed point, the "effective correlation space" is low-dimensional: you can truncate the SVD aggressively and recover nearly identical test accuracy.
I wonder if there's a connection to your Taylor truncation order. In RG terms, higher-order polynomial interactions are "irrelevant operators"—they get suppressed as you flow toward the fixed point. If trained attention heads are sitting near this fixed point, that might explain why modest truncation orders work: the network has already learned to concentrate its computation in the lower-order terms. A testable prediction: layers with α closer to 2 (measurable via weightwatcher https://github.com/CalculatedContent/WeightWatcher) might need fewer Taylor terms for accurate approximation than layers with α far from 2. If true, you could potentially use the spectral statistics to adaptively choose truncation order per-head.
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#43I 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…
[flagged]
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#44Earlier quoted context omitted.
> 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.
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.
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#45I 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…
[flagged]
llm detected
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#46There'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
The 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.
It converges on conventional attention as P goes up
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#47There'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
Dumb question: is the quadratic time complexity for training, inference, or both?
Both, with caveats. The attention computation is fundamentally quadratic: for every token in the sequence, you're doing a computation that has to compute over every other token in the sequence. So it's O(N) per token, O(N^2) for the whole sequence.
The big mitigation for this is that in causal transformers (i.e. all the chatbot type applications, where each token is only allowed to see tokens before it), you're running inference repeatedly on the same prefix in order to grow it by one token at a time. So if you cache the computations for tokens 0..N-1, on each inference pass you only have to compute O(N) for the newly added token at the end of the sequence.
That's why caching (and caching charges) appear so prominently everywhere in the pricing of inference.
In practice, caching is most beneficial at inference time, because you typically have relatively long conversations that start with the same cacheable prefix (the system prompt). At training time the same optimization can apply, but you're typically not pushing the same prefixes through the model repeatedly so you end up paying the quadratic cost more often.
The quadratic cost of attention is the fundamental compute bottleneck for transformer architectures, which is why there's research like this trying to find shortcuts in computing attention, as well as research into completely new primitives to replace attention (e.g. SSM, which is O(N) on a cold cache and O(1) on a warm cache).
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#48Earlier quoted context omitted.
I 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
Right - e.g., if you're modeling a physical system it makes sense to bake in some physics - like symmetry.
Indeed, 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
[2] The Geometry of Reasoning: Flowing Logics in Representation Space, https://arxiv.org/abs/2506.12284
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#49I 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…
This is a form of linear attention (https://arxiv.org/abs/2006.16236) that approximates standard scaled dot-product attention to arbitrary precision, by adding Taylor terms in an efficient manner. Each additional Taylor term improves the approximation. Efficiency is achieved by exploiting certain mathematical symmetries that become evident only after decomposing the standard formulation of attention into an expression over chains of tensor products. The github repository's README walks through examples. The first example is with 8 Taylor terms.
Re: Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
#50Earlier quoted context omitted.
> 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.
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.
That argument could also be used to say that the FFT's time complexity of O(n log n) should be impossible.