[HN Gopher] Attention is Turing complete (2021) [pdf]
___________________________________________________________________
Attention is Turing complete (2021) [pdf]
Author : Anon84
Score : 66 points
Date : 2023-06-14 20:22 UTC (2 hours ago)
(HTM) web link (www.jmlr.org)
(TXT) w3m dump (www.jmlr.org)
| ftxbro wrote:
| Isn'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 wrote:
| Turing 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.
| Xen9 wrote:
| Educative comment!
| nico wrote:
| Great point
|
| 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
| godelski wrote:
| This is definitely not true. There are context-free grammar
| and finite state machines are not Turing complete (TC).
| Strong functional programming languages (always terminate and
| every action is defined: e.g. x/0=0) are not TC since they
| exclude the ability to not terminate. In fact, most things
| you run on a computer are not TC as they are
| deterministically terminating. Computers themselves are not
| TC! They have finite memory. For practical purposes they are,
| and the languages they use often are, but I'd be a bit
| careful with your "personal theory" as it doesn't capture the
| ideas of TC that well.
| ftxbro wrote:
| OK but I understand that systems like finite state machines
| and parenthesis matchers aren't Turing complete.
| slt2021 wrote:
| in other words anything can be Turing complete if provided
| infinite compute/storage
| robwwilliams wrote:
| Lovely article by Perez 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...
| gwern wrote:
| 2019 version which includes the Neural GPU:
| https://arxiv.org/abs/1901.03429
| adamnemecek wrote:
| Attention is just convolution in a Hopf algebra.
| TeMPOraL wrote:
| Does 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}"?
| meindnoch wrote:
| You took the words right out of my mouth!
| adamnemecek wrote:
| Sarcasm?
| meindnoch wrote:
| Yes.
| triska wrote:
| Quoting 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 wrote:
| It 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 wrote:
| As 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 wrote:
| I'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.
| nyrikki wrote:
| Note that Magic: The Gathering is Turing Complete
|
| 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.
| meindnoch wrote:
| What you wrote here is not even wrong.
| randomNumber7 wrote:
| A computer with limited amount of memory is also theoretically
| not turing complete. So it might still mean that a transformer
| with floats comes close.
| godelski wrote:
| This is a rather mundane and unsurprising line tbh. Finite
| automata are not Turing complete. Computers are not in reality
| since they do not have infinite memory and do not have infinite
| precision. I'm not sure if it'll lead to arbitrary precision
| machines since the lack of real world Turing completeness
| hasn't stopped us so far and likely won't.
| TeMPOraL wrote:
| Is there a formal, mathematical way of saying "real-world
| computers may not have infinite memory, but have more than
| enough, so 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"?
|
| 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"?
| sva_ wrote:
| I 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
| api wrote:
| Off 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..."
| metanonsense wrote:
| What made attention mechanism click to me was the video
| 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
|
| 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 :)
| opyate wrote:
| I thoroughly recommend Sebastian's newsletter "Ahead Of AI".
| Link on his website:
|
| https://sebastianraschka.com/
| PartiallyTyped wrote:
| > 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 wrote:
| Thanks.
|
| 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?
| petemir wrote:
| There was this comment a couple of weeks ago (
| 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 )
| PartiallyTyped wrote:
| Attention 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 wrote:
| Have 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.
| garganzol wrote:
| Related discussion: https://news.ycombinator.com/item?id=36020520
___________________________________________________________________
(page generated 2023-06-14 23:01 UTC)