HackerPapers

arXiv:2106.06981cs.LG

Thinking Like Transformers

Gail Weiss, Yoav Goldberg, Eran Yahav

Abstract

What is the computational model behind a Transformer? Where recurrent neural networks have direct parallels in finite state machines, allowing clear discussion and thought around architecture variants or trained models, Transformers have no such familiar parallel. In this paper we aim to change that, proposing a computational model for the transformer-encoder in the form of a programming language. We map the basic components of a transformer-encoder -- attention and feed-forward computation -- into simple primitives, around which we form a programming language: the Restricted Access Sequence Processing Language (RASP). We show how RASP can be used to program solutions to tasks that could conceivably be learned by a Transformer, and how a Transformer can be trained to mimic a RASP solution. In particular, we provide RASP programs for histograms, sorting, and Dyck-languages. We further use our model to relate their difficulty in terms of the number of required layers and attention heads: analyzing a RASP program implies a maximum number of heads and layers necessary to encode a task in a transformer. Finally, we see how insights gained from our abstraction might be used to explain phenomena seen in recent works.

arXiv comments
ICML 2021
Journal reference
DOI
Subjects
cs.LGMachine Learning cs.CLComputation and Language

On Hacker News

Linked by 11 identifiable commenters in 13 comments across 11 threads, from Dec 2021 to Nov 2026. Found in 2 HN submissions from Jun 2021 to Jun 2023. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments11 threads

  1. The 'Astra can read and write weights to improve Qwen' post is misleading 1 comment

    • Here's the work that shows how rule-based logic can be compiled into transformer weights: * Thinking Like Transformers” by Weiss, Goldberg & Yahav (ICML 2021).: https://arxiv.org/abs/2106.06981 * Tracr: Compiled Transformers as a Laboratory for Interpretability…

      syllogismView on HNParent context

  2. I want to wash my car. The car wash is 50 meters away. Should I walk or drive? 1 comment

    • 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…

      andy12_View on HNParent context

  3. Weight-sparse transformers have interpretable circuits [pdf] 1 comment

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

      leogaoView on HNParent context

  4. Ask HN: How are Markov chains so different from tiny LLMs? 1 comment

    • 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…

      astrangeView on HNParent context

  5. Mixture-of-Depths: Dynamically allocating compute in transformers 1 comment

    • 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…

      nikvaesView on HNParent context

  6. I made a transformer to predict a simple sequence manually 2 comments

    • 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.…

      teddykokerView on HNParent context

    • Something close exists: RASP https://arxiv.org/abs/2106.06981 python implementation: https://srush.github.io/raspy/

      shawntanView on HNParent context

  7. Graph of Thoughts: Solving Elaborate Problems with Large Language Models 1 comment

    • 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…

      jbay808View on HNParent context

  8. From word models to world models 2 comments

    • > 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…

      jbay808View on HNParent context

    • >> Transformers are RASP programs, which includes sorting programs. See the Weiss paper (https://arxiv.org/pdf/2106.06981.pdf). That's one preprint on arxiv, that makes a wild claim about a new concept that they acronymise as "RASP". It's not any kind of established terminology…

      YeGoblynQueenneView on HNParent context

  9. It's not just statistics: GPT-4 does reason 1 comment

    • 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…

      jbay808View on HNParent context

  10. GitHub Copi­lot inves­ti­ga­tion 1 comment

    • 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.

      attemptoneView on HNParent context

  11. The potential of transformers in reinforcement learning 1 comment

    • Not sure if this is a good introduction, but a good second paper to read is https://arxiv.org/abs/2106.06981 You can think of finite state machines as being two functions: f(input, state) = output, and g(input, state) = next_state. (Traditional FSMs have 3 ‘output’ states…

      lalaithionView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.