Attention is Turing complete (2021) [pdf]
jmlr.org
jmlr.org
"To prove this we assume that internal activations are represented as rational numbers with arbitrary precision."
And:
"Transformers with fixed precision are not Turing complete."
It will be interesting to see if this leads to better support for arbitrary precision arithmetic in processor architectures.
And in general, there surely is a way of formally saying "this is theoretically X, but effectively Y, for the [hand-waves] kind of inputs"?
That said, some simple intuition is the following: PSPACE is a subset of EXP is a subset of EXPSPACE
(We think these are all strict separations but technically that’s not fully proven)
If you use the shorthand intuition that we can handle polynomial scaling but can’t handle exponential scaling, this means that we hit a time barrier (EXP-complete problems) before we hit a space barrier (EXPSPACE-complete problems)
Another bit of intuition: you can store a very big number in very few bits in binary because binary holds an exponentially large number in linear bits. But you can’t loop over that number in a humans’ lifespan.
Edit:
> they can be treated as Turing-complete for a subset of programs that are well-behaving - i.e. don't end up hitting the memory limit
Just to be clear, it’s a matter of input size and not the programs themselves. Technically you could say we haven’t “solved” sorting on real hardware because nobody can sort the first 2^1000 digits of pi. But realistically we don’t care to do so.
For the arguably part: I am assuming that the machine can access all of the input at once, so it is reasonable to expect available memory to be a multiple of the input, so you get O(n) memory.
Usually people just let it go unless someone brings up specifically something that implies that there is, or might, not a shared mutual understanding (as done here). Maybe it is shared, maybe not, maybe someone reading it doesn't understand the difference. I mean we're humans. We compress a lot of information into language that is not directly expressed in our words (this is also why it is often hard to talk to people on the internet since there's a wide audience with vastly different priors. Relevant XKCD[1]).
For instance, I have many potential applications of Turing complete formalisms, because I am interested in results of arbitrary computations. The result obtained in the article means that I can use a Neural Network to obtain this, under the conditions outlined in the article, and in the way shown in the article.
This may simplify software architectures, especially in situations where Neural Networks are already applied, and additional mechanisms would otherwise be needed to cover arbitrary computations.
https://arxiv.org/abs/1904.09828
Something being Turing Complete just that means in principle it could be used to solve any computation problem. But this may require infinite memory or infinite time.
printf() is Turing complete as an other example.
https://www.ioccc.org/2020/carlini/index.html
The paper showed that Transformer with positional encodings and rational activation functions is Turing complete.
Rational activation functions with arbitrary precision make sure that you are in the smaller countable infinities, where floats run into that cardinality of the continuum problem.
While all nets that use attention are feed forward and thus effectively DAGs, they add in positional encodings to move it from well-founded to well ordered.
While those constraints allow the authors to make their claims in this paper, they also have serious implications for real world use as rational activation functions are not arbitrarily precise in physically realizable machines in finite time and you will need to find a well-ordering of your data or find a way to force one one it which is not a trivial task.
So while interesting, just as it was interesting when someone demonstrated sendmail configurations were Turing complete, it probably isn't as practical as you seem to think of it.
As attention is really runtime re-weighting and as feed forward networks are similar to DAGs it is not surprising to me that someone found a way to prove this, but just as I am not going to use the C preprocessor as a universal computation tool as it is also TC, I wouldn't hold your breath waiting for attention to be a universal computation tool either.
Choose the sources you trust very carefully, and look to the people actually working on real-world AI systems, not the storytellers and hangers-on.
But if you are talking about arbitrary precision floats, or the computable set of the reals it is equivalent.
The computable reals are just the concatenation of the natural numbers/ints
So it is the countable infinity and thus the cardinality of Aleph-nought.
That adds to the time complexity, while the unbounded memory requirement comes from the definition of a Turing machine which is roughly a finite state machine+ an infinite tape.
As the reals are uncomputable almost everyplace, you would need an activation function that only produced computable reals, as they are equivalent rational activation functions are simpler for the proof.
A usual Neural Network (NN) implements only two operations though: addition and negation. The branching operation can be achieved by:
1) recursion as in Recursive Neural Network (RNN), -or/and-
2) some kind of a conditional intermediary loop that occurs between NN runs.Turing's original machines have only decision making and substitution. With that you can emulate anything you want, and go on to higher levels and more and more complexity.
Apparently even Conway's Game of Life is Turing complete ... it's horribly obtuse but can be used to build something, which is used to build something, and so on, until eventually you have an automata that could compute anything computable (though rather slowly!)
My personal theory is that anything you can run on a computer is Turing complete
Essentially any algorithm needs an interpreter that runs it
So if your algorithm runs on a computer, then in includes the whole computer
Like if you are truly statically linking code, it should include the whole computer with it
And that system is most definitely Turing complete
So probably when a complex enough algorithm runs on a computer, it might be big enough that you need a significant part of the abstractions of the computer system itself to explain the behavior of the algorithm, so the algorithm ends up including the requirements for Turing completeness
Turing completeness is defined on computational models, i.e. sets of instructions that you can use to build algorihms. Not on the algorithms themselves. If you can simulate a Turing machine using only the tools that your model gives you, then it's Turing complete. That doesn't mean that everything else you build using those tools is special in any way.
But you do need an interpreter to interpret/run any algorithm
So you can never really separate the algorithm from the interpreter for any practical application
If your algorithm requires the capabilities that define an interpreter as Turing-complete, then the algorithm will be Turing complete as well
> Understood as such, it's not really such a strange idea, that the things outside of the text itself can and do give meaning to it in an ever-evolving way. In a philosophical context we can understand it to assert the idea that context is always present, and isn't necessarily stable.
I’ve had a tough time finding anything that really just explains the mechanics of how they work without immediately jumping into pytorch abstractions or just describing the reason they are used with some strained metaphor. Like what is the key in the key value lookup and then how is the value used? How are they trained? Etc.
Any good links that skip all the nonsense and just explain how these are constructed for a programmer audience?
Even the LLMs themselves can’t explain it to me very well. ChatGPT and various LLaMa tunings have been able to tell me all about every other aspect of neural nets and LLMs which I love for the spooky factor of having AI tell me how to make more of it.
“I will show you how to bring us into your world…”
In hindsight, what helped me most is understanding the dimensionality at each step of the attention computation (explained well in Raschka's video). Another think I simply did not get from the original Transformer paper is that the learning of self-attention happens in the linear layers. (At least, that's my current understanding. If that's wrong, I appreciate any correction :)
You can replace the KVQ kernels with any parametric computation that allows you to pass gradients through, and you will have learning.
I think some newer language model architectures use residual blocks here, and some vision transformers use FeedForward networks for the kernels.
One thought I’ve had is to wonder if attention isn’t kind of like a way to unroll RNNs to make training more efficient. Any truth in that?
The values are given from the Value kernel; which is often just a linear map.
The strength is given from the dot product of the query and the keys. The queries and keys are given from the Query and Key kernels. Both of which are usually linear maps.
For each token, you have a key value query triplet (D,D,D). You take the query (D,1) and the matrix (N x D) of keys of all tokens, and do a Matrix vector product to get the scaling. You apply softmax to make it convex; and now you have a vector (N, 1). You do another matrix vector product with the Values mapping (N, D), which gives you the value for the current token (1,D).
Repeat N times, and that’s it.
If you would like to change which tokens each token considers, eg a token knows only of preceding tokens, you can do element wise product of the scaling vector with a mask vector which describes what you consider for current token ; and divide by their inner product. This will renormalise the valid coefficients and keep the rest 0; thus they are ignored when you combine all values together.
If you would like to increase the number of attention heads; which can give you finer control of the scaling process, you can split the key query and value vectors into segments, one segment for each head. Eg first 2 indices go to head 1, indices 3,4 go to head 2, etc etc. then you use those to do attention, repeating the process above for each head; and then combine the results to a single vector.
Idk if I confused query with keys, but this is the gist of it.
In practice the operations are much more optimised than what I described.
This is a great transparent and clear description of what is actually going on in attention layers.
Alternatively, this article by Jay Alammar is also very popular http://jalammar.github.io/illustrated-transformer/
The 'key' and 'value' description in the attention mechanism probably doesn't make much sense to you because at best it's a strained metaphor, rather than an actual principle by which attention operates. If you take a look at the maths, you can interchange the role of 'keys' and 'values' and get something mathematically identical.
https://scholar.google.com/citations?hl=en&user=a6lUuiwAAAAJ...
Most popular being subleq (subract if less than or equal to zero).
Subleq can be implemented with a transformer.
See https://arxiv.org/pdf/2301.13196.pdf (Looped Transformers as Programmable Computers).
The important distinction is that transformers need to be looped. Just like ChatGPT calls the model over and over again until stop token or limit is reached.
And we know ChatGPT does better if we let it think step by step and blabber more (chain of thought prompting). In every token it generates, it gets an opportunity to branch.