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.
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.
Yes, there must be a connection. While adaptive truncation may prove impractical, it should be possible to measure spectral statistics on sample data, and specify a different fixed truncation order per layer, per head, etc. The github repository lists many other possible improvements: https://github.com/glassroom/sata_attention#proof-of-concept
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.
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 longer, analogous to an RNN:
To the best of our knowledge, this is the first time anyone has successfully trained a non-diagonal RNN computed in parallel, via prefix scan, without requiring any form of stabilization. We abstained from claiming as much out of an abundance of caution.
The manuscript formally defines GOOMs as a set of mathematical objects, shows that floating-point formats are a special case of GOOMs, and notes that they extend prior work on logarithmic number systems (LNSs), which go back to at least the early 1970's. That is, LNSs are a special case of GOOMs too. Defining and naming GOOMs enables reasoning about all possible special cases in the abstract. In practice, each implementation makes different trade-offs.
The formal definition stops short of inducing an isomorphism between GOOMs and R, to allow for the possibility of transformations that leverage the structure of the complex plane, e.g., deep learning models that process data in C and apply a final transformation from C to GOOMs, thereby allowing the data to be exponentiated to R. The library in this repository makes implementing such a model trivial, because it ensures that backpropagation works seamlessly over C, over GOOMs, and across mappings between C, GOOMs, and floats.
Take a look at the selective-resetting algorithm in the manuscript too. To the best of our knowledge, it's a new algorithm, but we opted not to claim as much, out of an abundance of caution. You will appreciate reading about it.
> GOOMs generalize the concept of "order of magnitude" to incorporate complex numbers that exponentiate to real ones. As with ordinary orders of magnitude, GOOMs are more stable than the real numbers to which they exponentiate.
> This implementation enables you to operate on real numbers far beyond the limits of conventional floating-point formats, for effortless scaling and parallelization of high-dynamic-range computations. You no longer need to scale, clip, or stabilize values to keep magnitudes within those limits.
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.