Thinking Like Transformers

You do understand that the mechanism through which an auto-regressive transformer works (predicting one token at a time) is completely unrelated to how a model with that architecture behaves or how it's trained, right? You can have both: - An LLM that works through completely different mechanisms, like predicting masked words, predicting the previous word, or predicting several words at a time. - A normal traditional program, like a calculator, encoded as an autoregressive transformer that calculates its output one word at a time (compiled neural networks) [1][2] So saying "it predicts the next word" is a nothing-burger. That a program calculates its output one token at a time tells you nothing about its behavior. [1] https://arxiv.org/pdf/2106.06981 [2] https://wengsyx.github.io/NC/static/paper_iclr.pdf

There's been some work (e.g RASP - https://arxiv.org/abs/2106.06981) on taking logical computations and compiling them into transformer weights.

The difference is there are exponentially more states than an n-gram model. It's really not the same thing at all. An LLM can perform nearly arbitrary computation inside its fixed-size memory. https://arxiv.org/abs/2106.06981 (An LLM with tool use isn't a Markov process at all of course.)

After trying to understand and implement some algorithms in RASP [1, 2], my take-way was that certain functions need a certain amount of transformer layers to operate. Following this logic, it should become apparent that the functions learned by transformers can be spread over multiple heads. Repeating these functions might be very valuable for understanding and solving a problem, but current inference does not allow (a set of subsequent) heads to be repeated. This paper indeed seems a promising direction. [1] https://arxiv.org/pdf/2106.06981.pdf [2] https://www.youtube.com/watch?v=t5LjgczaS80

A related line of work is "Thinking Like Transformers" [1]. They introduce a primitive programming language, RASP, which is composed of operations capable of being modeled with transformer components, and demonstrate how different programs can be written with it, e.g. histograms, sorting. Sasha Rush and Gail Weiss have an excellent blog post on it as well [2]. Follow on work actually demonstrated how RASP-like programs could actually be compiled into model weights without training [3]. [1] https://arxiv.org/abs/2106.06981 [2] https://srush.github.io/raspy/ [3] https://arxiv.org/abs/2301.05062

It is only difficult for a LLM to sort a list of numbers if the list is longer than half of the context window. (Source: I tested this myself[1]). The sorts are not error-free every time, but with sufficient training they become error-free the vast majority of the time, even for long lists. This is not especially surprising because transformers are capable of directly representing sorting programs.[2] [1] https://jbconsulting.substack.com/p/its-not-just-statistics-... [2] https://arxiv.org/abs/2106.06981

https://arxiv.org/abs/2106.06981 - Thinking like Transformes The paper suggests that transformer work on a set of select, aggregate and element-wise operations. Which seems pretty close to the SQL statements i write from day to day.

> it sure has not learned any "algorithm". At best it has learned to approximate a sorting algorithm. That's what statistical machine learning models do, they are function approximators; not program learners. Transformers are RASP programs, which includes sorting programs. See the Weiss paper (https://arxiv.org/pdf/2106.06981.pdf). > Also, Machine Learning 101: you test your models on a test set that is disjoint to the training set. To clarify, we do this not because it's in the book and that's the rules, but because, by testing the model on held-out data, we can predict the error the model will have on unseen data The probability of a tested input list existing in the training set is less than 10^-70.

Author here. Happy to see this discussion. Absolutely, GPT-4 sometimes has trouble reasoning and doesn't reason perfectly. I'm impressed by its successes, but I agree it's not at the human level yet, and I would not make the claim that it is. Counting is a task that transformers can do, per Weiss.[1] But it's not surprising that transformer networks in general have trouble counting characters -- the tokenizer replaces common sub-strings, so the number of characters will not in general be the number of tokens. The network might have little way of even knowing how many characters are in a given token if that information isn't encountered elsewhere in training. [1]: https://arxiv.org/abs/2106.06981