6 ms·
Attention is Turing complete (2021) [pdf]
- nojvek 3y agoAs others have mentioned, turing machines can be achieved by only one instruction set. See https://en.wikipedia.org/wiki/One-instruction_set_computer https://en.wikipedia.org/wiki/One-instruction_set_computer 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 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.
- api 3y agoOff topic: I’ve been studying all this LLM stuff and feel like I have a solid understanding of everything in these designs except attention layers. 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…”
- petemir 3y agoThere was this comment a couple of weeks ago ( https://news.ycombinator.com/item?id=35980418 https://news.ycombinator.com/item?id=35980418 ). Perhaps also episode 7 of Karpathy’s “Neural Networks: From Zero to Hero” course ( https://www.youtube.com/watch?v=kCc8FmEb1nY https://www.youtube.com/watch?v=kCc8FmEb1nY )
- PartiallyTyped 3y agoAttention is a convex linear combination of values (meaning the coefficients sum to 1) where the coefficients are generated at runtime. 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.
- soVeryTired 3y agoHave you tried asking GPT-4? I got a pretty good explanation of attantion from it. 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.
- metanonsense 3y agoWhat made attention mechanism click to me was the video https://www.youtube.com/watch?v=0PjHri8tc1c https://www.youtube.com/watch?v=0PjHri8tc1c by Sebastian Raschka. Another good video on attention that tries to give a bit more intuition on the query/key/value stuff is https://www.youtube.com/watch?v=OyFJWRnt_AY https://www.youtube.com/watch?v=OyFJWRnt_AY 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 :)
- PartiallyTyped 3y ago> Another think I simply did not get from the original Transformer paper is that the learning of self-attention happens in the linear layers. 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.
- api 3y agoThanks. 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?
- opyate 3y agoI thoroughly recommend Sebastian's newsletter "Ahead Of AI". Link on his website: https://sebastianraschka.com/ https://sebastianraschka.com/
- tomasff 3y agohttps://arxiv.org/abs/2207.09238 https://arxiv.org/abs/2207.09238 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/ http://jalammar.github.io/illustrated-transformer/
- opyate 3y agoI commented yesterday, but came back to say this. Just found it, and it's really good. I like reading descriptions better than watching videos of them, so this is great.
- garganzol 3y agoRelated discussion: https://news.ycombinator.com/item?id=36020520 https://news.ycombinator.com/item?id=36020520
- triska 3y agoQuoting from the article: "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.
- heyitsguay 3y agoIt won't, it just means this is another pointless theoretical study seeking to interpret Transformers in a framework that has no explanatory value for AI.
- triska 3y agoAs I see it, the result is rather establishing a very fundamental property pertaining to the expressive power of a mechanism, and it can be useful also in practice. 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.
- heyitsguay 3y agoI'm not going to engage with this directly, but for any other readers passing through - this is nonsense. One more drop in the flood of uninformed AI noise that's been drowning out the signal. 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.
- meindnoch 3y agoWhat you wrote here is not even wrong.
- 3y ago
- ftxbro 3y agoIsn't there some kind of universality principle where anything that is complicated enough is Turing complete if you let it have infinite memory, and that the surprising thing is when a complicated process isn't Turing complete? I mean, the transformer architecture seems obviously complicated enough to be Turing complete. It's just that it has a finite number of layers and it seems to need a lot of computation to train its weights.
- garganzol 3y agoTuring completeness requires the presence of at least three operations: addition, negation, branching. 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.
- drpixie 3y agoYou might be a little pessimistic about needing 3 operators. 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!)
- garganzol 3y agoI'm neither pessimistic nor optimistic. The formal criteria of Turing completeness are dictated by the math. If a system can implement those or equivalent ops in a disguised form - then it is Turing complete.
- Xen9 3y agoEducative comment!
- jmalicki 3y ago
- robwwilliams 3y agoLovely article by Pèrez and colleagues. Yes, the naive expectation might be that “complex enough” becomes Turing complete, but as discussed in the lucid introduction this is often thought to require a recurrent process. So it is good to see the formal proof. https://scholar.google.com/citations?hl=en&user=a6lUuiwAAAAJ&view_op=list_works&sortby=pubdate https://scholar.google.com/citations?hl=en&user=a6lUuiwAAAAJ...
- gwern 3y ago2019 version which includes the Neural GPU: https://arxiv.org/abs/1901.03429 https://arxiv.org/abs/1901.03429
- adamnemecek 3y agoAttention is just convolution in a Hopf algebra.
- meindnoch 3y agoYou took the words right out of my mouth!
- adamnemecek 3y agoSarcasm?
- meindnoch 3y agoYes.
- adamnemecek 3y agoI wrote a paper on the topic but local heterodoxy police doesn't like it when I link it. So look up my name on arxiv.
- TeMPOraL 3y agoDoes this have explanatory value, or is it the case of "${term} is a ${simple concept} in ${highly specialized framework that's designed specifically so that ${term} is a case of ${simple concept} in it}"?
- frakt0x90 3y agoYeah it's "A monad is just a monoid in the category of endofunctors" rehashed for the millionth time.
- slt2021 3y agoin other words anything can be Turing complete if provided infinite compute/storage
- mr_toad 3y agoYour typical “it’s just curve fitting” algorithm is not Turing complete, no matter how much memory and compute you throw at it.
- sva_ 3y agoI have to say I quite enjoy these incidences where people discover 'accidental' Turing completeness. Seems like gwern wrote an article on it: https://gwern.net/turing-complete https://gwern.net/turing-complete
- tomp 3y agoAttention is linear, so I doubt it can be Turing complete