6 ms·
Transformer as a general purpose computer
- Hugsun 3y agoThe title is a little misleading. The post makes an analogy between a turing machine and a transformer and and expands on that analogy a bit. The substance of the article is an explanation of the design of a standard transformer. It does not use transformers as a computer in any novel way. It just makes the analogy.
- typon 3y agoFor those unaware of Alex Graves' work, check out the NTM paper: https://arxiv.org/abs/1410.5401 https://arxiv.org/abs/1410.5401 This actually does what this blog post pretends to
- nyrikki 3y agoExcept it proves nothing about TC, it just refers to a paper that demonstrated RNNs were TC. The authors decision to name their creation a "Neural Turing Machine" doesn't make it computationally equivalent. The fact that it explicitly states: > ...analogous to a Turing Machine or Von Neumann architecture but is differentiable end-to- end, allowing it to be efficiently trained with gradient descent. Actually demonstrates it is not equivalent. Note that I am not saying their approach is wrong, but that their overloading of terms suggests more than they claim. While 'general-purpose computer' is ambiguous, a Turning machine is not as opaque. LLMs can be TC with infinite space for input and infinite width. For finite input, size, and depth, LLMs aren't even equivalent to primitive recursive functions IIRC. With consent depth threshold circuits being a recent claim as the limits of LLMs.
- JohannesVoderho 3y agoOriginal creator of the blog here. Yes, you are right. The title of the blog is a bit misleading. I originally wrote this for a course from my University and thought it was interesting so integrated it into my website. I didn't expect to get that much traffic on the blog and didn't intend to do any clickbaiting. I just wanted to extend on what Andrej karpathy mentioned in one of his tweets: https://twitter.com/karpathy/status/1582807367988654081 https://twitter.com/karpathy/status/1582807367988654081. I think i also linked it in the blogpost. I think this view on transformers is a very powerful one and explains in the best way why the transformer is build that way. This also allows us to reason about certain improvements for the transformer. For example weight tying some layers to make it easier to map to algorithms that have a lot of repeated operation. The Goal of the blog was not to use the transformer as a general purpose differentiable computer but to convince you that the transformer already IS a general purpose differentiable computer. Maybe i will create another blog where i train the transformer on simple algorithmic problems like sorting or copying data, just like in the differentiable turing machine, or even show how you can hard code the transformer weights to solve them. What do you think would be a better title for the blog?
- Hugsun 3y agoThat makes sense. It definitely read like a university project to me. One idea is "Transformers, analogous to general purpose computers" although that doesn't mention the meat of the article. "Transformers from scratch, a turing machine analogy" is another idea. I'm not sure they're good titles but they don't imply that it's about using a transformer as a computer. With the goal you state, I understand better how you came to the title.
- questinthrow 3y agoCould Transformers/LLMs take over custom software implementations given enough training? Why have so many custom ERP software suites or anything else related to the backend if a transformer can do the work?
- janpmz 3y agoI think the problem is that small errors compund, even if each step in a process has a low chance of going wrong.
- typon 3y agoUnless you value correctness and safety, it's probably not a great idea to use a probabilistic algorithm as a backbone for your software
- CamperBob2 3y agoOr unless you have additional feedback mechanisms for correctness and safety. Transformers are components -- subsystems at best, not complete systems. And at some point, "good enough" always wins over "perfect" in real-world systems. Always. No exceptions.
- lolinder 3y ago> Why have so many custom ERP software suites or anything else related to the backend if a transformer can do the work? Because they can't. Transformers are great at probabilistic tasks that traditional computing can't do well, like natural language processing. They're very suboptimal for the tasks that traditional computing is already good at. The first and most obvious reason is that traditional computing is deterministic and predictable in its behavior. This is great for business systems because errors can be tracked down to specific lines of code that can be demonstrably fixed and regression checked. A transformer doesn't have this property—when something fails you can try tweaking parameters like temperature or fine tuning it longer, but it's hard to prove that the specific bug won't show up again. The second reason is cost—even saying you can make a reliable transformer-based ERP system, in the long run it won't cost less than the traditional equivalent. The initial training cost can be enormous and you still need highly paid staff to organize that work. Once you have the working system, your business will still need to make changes to the rules over time, so you'll still need to keep some of those staff on hand to make those changes, but you also have to pay for the GPU time to run the application, which will cost much more than the equivalent traditional ERP. Finally, even if all of that sounds fine, at some point you need to store the data and host a web server of some kind, which means you're going to need to interface with deterministic computation. I guess you could go the tool use route and let the LLM generate its database queries on the fly, but that makes all the reliability problems in the first paragraph much much worse. And if you're going to hire web devs anyway, why not just have them do everything?
- colesantiago 3y agoAs others have said, the title does not match the contents of the article and the way this has been explained looks like a very opaque and highly abstract rube goldberg machine with limited use cases. What does this solve? Even by going with the flawed title, this mostly is a solution in search of a problem.
- typon 3y agoIt solves language understanding in a practical sense - a task heretofore considered impossible
- colesantiago 3y agoThis has been already solved even without LLMs for years: Google Translate, DeepL and Firefox Translate have done this use-case already, much more efficiently than LLMs. So what does this particular use case of a transformer as a general-purpose computer solve that hasn't already been solved before? Why do we need this?
- lolinder 3y ago> Google Translate, DeepL and Firefox Translate have done this use-case already, much more efficiently than LLMs. They may have been more efficient, but the transformer-based Google Translate we have today is way better at its job than its predecessors, and the old Google Translate wasn't capable of other NLU tasks that can now all be done by transformers (and again, all better than the previous specialized tools). I agree that transformer-as-Turing-machine isn't really solving any problems, but transformers have been nothing short of revolutionary for tasks that have usually been hard for plain Turing computation.
- JohannesVoderho 3y agoOriginal creator of the blog here. I originally wrote this for a course from my University and thought it was interesting so integrated it into my website. So i didn't want to "solve" anything. I just wanted to extend on what Andrej karpathy mentioned in one of his tweets: https://twitter.com/karpathy/status/1582807367988654081 https://twitter.com/karpathy/status/1582807367988654081. I think this view on transformers is a very powerful one and explains in the best way why the transformer is build that way. This also allows us to reason about certain improvements for the transformer. This was mostly an educational blog
- f_devd 3y agoInteresting, I thought it was proven Transformers cannot do recursion[0] and aren't actually able to be equivalent to a turing machine due to lack of expandable memory, and are rather finite state automata. [0]: https://youtu.be/rie-9AEhYdY?si=5p0QCxAFovGUHFRb&t=1744 https://youtu.be/rie-9AEhYdY?si=5p0QCxAFovGUHFRb&t=1744
- golol 3y agoPeople always makes these points of things not being technically Turing machines because they are finite, they have finite memory. Well, obviously! Your computer has finite memory too. It doesn't matter in practice, and the conceptual idea that this thing can do arbitrary computations is more important.
- f_devd 3y agoThe argument isn't finite memory but rather the lack of it being expandable memory; as in it cannot learn to read/write to a hypothetical infinite tape. (Although I'm maybe not the right person to word it, I recommend the prior linked video)
- golol 3y agoThe nature of computation is just not about extendability of memory for me. It's just a technicality.
- fl7305 3y ago> it cannot learn to read/write to a hypothetical infinite tape Modern LLMs can perform external function calling. How is that not the same as having access to a potentially infinite memory? Conversely, your brain does not contain infinite storage. So it is clearly not Turing complete in the strictest sense. Does that tell us anything useful about the level of intelligence in a brain?
- f_devd 3y ago> Conversely, your brain does not contain infinite storage. But you can address it and use it, you can think of a system which can make use of infinite memory and then execute that system. LLMs they cannot use something like `set(0x8080, "ABC")` and later retrieve that with `get(0x8080)` without keeping the initial command in it's context therefore it's memory is not expandable. Likewise LLMs can call a external function but the input of the LLM is a fixed context on which it's trained, and it has a fixed amount of time to use that context so it's not expandable. Now this is not necessarily a limitation of the architecture, but rather how we train NNs. It's also not a necessity to do something useful but the efficient/optimal solution for many problems are often turing-complete and are thus not findable or even searchable by NNs. The video goes into more depth everything metioned, and on the distinction between turing machines and NN limitations.
- VHRanger 3y ago1. There's nothing particularly special about Transformers, except that it was the first architecture to scale. Transformers scale well because they leverage a GPU well. The drawback to this is the attention mechanism (RAM hungry and finite autoregressive window) 2. Transformers aren't "computers" in the turing machine sense given their finite state. You could make that argument for models with hidden states, though, like RNNs/LSTM, SSMs/Mamba, RWKV. THe issue with those is that the hidden state makes them harder to train at scale.
- throw10920 3y ago> 2. Transformers aren't "computers" in the turing machine sense given their finite state That's true, but then the things we normally think of today as "computers" also aren't, because of their finite amount of memory. I think that the author is implying that, like linearization, we can approximate transformers as being Turing-complete for a small range of operation (that's much larger for "real" computers).
- logicchains 3y agoTransformers are special because theoretically you can't make something "weaker" than a transformer without it losing some accuracy: https://arxiv.org/abs/2209.04881 https://arxiv.org/abs/2209.04881 .
- VHRanger 3y agoYes, Transformers are probably close to the Pareto frontier in terms of efficiency if you want to train something that has a sequence as an input. But they're not inherently *special*. There's a bunch of other model types around that pareto frontier. Transformers are just good at saturating memory bandwidth, which is the hardware frontier.
- thesz 3y ago> Despite a remarkable amount of algorithmic effort on Boolean satisfiability (SAT) and related problems, to date no one has invented an algorithm with faster-than-exponential (O(2^n)) running time; indeed, there is no polynomial-time algorithm for SAT unless P = NP. [1] https://www.hindawi.com/journals/complexity/2018/7982851/ [2] http://www.cs.cornell.edu/~sabhar/publications/learnIJCAI03.pdf The [1] shows how to replace numerical problem solving process with the SAT (circuit) based one and obtain exponential speed up. Let me quote the [2]: "We also show that without restarts but with a new learning scheme, clause learning can provide exponentially smaller proofs than regular resolution, which itself is known to be much stronger than ordinary DPLL." So, in my opinion, there are algorithms that work in O(2^(n(1-e))) time.
- raidicy 3y agoPlease correct me if I'm wrong, neural Turing machines were a good step but because Transformers do everything in parallel and don't have to read a tape and they more powerful but less efficient?
- cma 3y agoDeepmind found transformers get beat out on learning to reproduce outs towards the general computer end of the Chomsky formal language heirarchy by neural turing machines and even LSTMs: https://arxiv.org/abs/2207.02098 https://arxiv.org/abs/2207.02098
- EGreg 3y agoI think of LLM as a non-von-neumann architecture that basically can compute neural network stuff in parallel. You throw a bunch of training data at it, making it do predictions, and it shifts the gears and finds the model that gets close to modeling the latent space. That’s it. Alan Turing did it with Bombe machin modeling the ENIGMA didn’t he?
- deleted 3y ago[deleted]