Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a computational model for the transformer in the form of a sequence processing programming language named Restricted Access Sequence Processing Language (RASP). The paper shows how RASP can be used to program solutions to tasks that could conceivably be learned by a transformer. The paper argues that considering computational problems and their implementation in the RASP language allows people to "think like a transformer" in the style of symbolic programs. Overall, the paper is well written and easy to follow.

Reasons to accept the paper:
1. The paper provides a novel way of understanding how transformer model works from a programming language perspective.
2. The paper presents solutions in RASP language for simple tasks such as histograms and sorting, and also complicated logic inference task.
3. The paper attempts to build a connection between the operations in RASP language and the computational operations in transformers. This could help analyze the minimally required number of layers and upper-bound number of heads for the transformer to work on a specific task.

Reasons to reject the paper:
1. For general neural network models, which has no explicit attention mechanism but may still be able to learn to reason over various tasks, it is not clear whether the RASP language is still an abstraction. The paper only discusses transformers, but there is no evidence showing that the operations in RASP cannot be completed by a simple multi-layer neural network. In other words, the connection between RASP and transformer may not be unique, and we may use RASP to think like any neural networks.
2. It is not clear whether there exists other forms of programming language that can also "explain" how transformer works, and if so, how the presented one (RASP) is a better abstraction of the transformer model.
3. Although the presented RASP language can help analyze the number of layers and heads required theoretically, there is limited value and insights for improving existing transformers models.
review_title: Official Blind Review #1

final_score: rating: 3: Clear rejection
review_content: This paper proposes a programming language, RASP, as a computational model for transformer encoders, and discusses how analysis in terms of this language could be used to understand the behavior of transformer models.

The idea of finding a computational model for transformers is interesting, and (as discussed in section 4) could lead to insights in terms of how to build better models.

However, this paper lacks any results or experimental analysis, which makes it difficult to judge the validity or value of the claims presented. Section 4 discusses how recently proposed transformer variants could be understood (post-hoc) in terms of the RASP language. However, in order to justify using the RASP language to reason about transformers, I think it is necessary to demonstrate experimentally that insights from RASP can translate to new empirical findings. 

For example, in section 3.1, the paper makes the claim, “For any given RASP program, we can compute the minimal number of layers required to implement it in a transformer, and upper bound the number of heads this implementation requires.” Can this be verified experimentally, by building a synthetic task, and testing performance as the number of heads is varied?

Similarly, section 4.2 provides an analysis of the recently proposed sandwich transformer model. Could similar analysis be used to make claims about novel, untested architecture variants? Could these claims be verified experimentally? Results such as this would be of high value to the ICLR community.

Because of the lack of experiments, I recommend rejection. I think this is an interesting line of work which could prove valuable to the ICLR community if supported by rigorous experimental evidence.

Minor details:
pg 1: “that is requires” -> “that is required”
review_title: Interesting idea without experimental analysis

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a restricted programming language containing rough analogues of operations used in transformers. Using this language, the authors show how some algorithms can be implemented, which gives some insights about the limitations of transformers.

Overall, the paper is badly written, with many typos and many hard-to-understand areas. Since this is a "thought-experiment" paper, this alone is a good reason for rejecting this work at its current form. 

Some things I would have expected an analysis on:
* How well do the individual RASP operations map to the relevant transformer operations?
* Why are the examples in 2.1 important/useful? Where are they needed?
* What are "useful" algorithms that cannot be represented in RASP? How would we need to change a transformer to allow it to represent such algorithms?
*   Sec 2.2 is a textual description of a complicated algorithm, why not build it gradually from primitives by introducing larger functions? Experimental results on RASP/Transformers?
* Can you "compile" RASP into a transformer (=architecture+weights) that performs exactly the task defined in RASP? (If not, why? if yes, some experimental validation would be useful)



##### Typos
* Fig1, Line 8: should the second arg be `vals`?
* Sec2: "the base sequences": unbalanced parenthesis
* In the discussion of `aggregate` a selector `s` is an input, but `s` is never used. Should `s` be `f` instead ?
* In the definition of `select`, `s(i,j)=f(m1[i],...,mk[i], ot1[j], ... otl[j])` What does `m1[i]` mean? `m1` is the first element of `me` but `m1` is also a sequence somehow?
* Footnote 1 says uses variable `n`. What is `n`? Should it be `max(k,l)`?
* Fig3 the semantics of the operation in L2 have not been defined, similarly for Fig2 L7.
review_title: Interesting concept badly presented and evaluated

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors introduce a DSL, the Restricted Access Sequence Processing (RASP) language, that they claim can serve as a computational model for the transformer-encoder.  They develop the reader's intuition for RASP by providing RASP implementations of many basic operations such as computing histograms, sorting, and reversing.  They also show how, for a given RASP program, to determine the minimum number of layers required and to upper-bound the number of heads required to implement it as a transformer.  Lastly, they analyze two transformer variants, restricted-attention transformers and sandwich transformers.  For the former, they use the RASP perspective to claim a theoretical limitation, and for the latter, they comment that a known empirical finding is intuitive in light of the RASP perspective.

I found this paper very interesting, a rare conceptual gem in a mostly empirical field.  The ideas in the paper open up many new questions and directions.  I wish I could champion it but sadly I find it critically underdeveloped in its current state and not yet ready for publication.

The main weakness of the current version is that it only glosses over the connection between RASP and the transformer-encoder.  It does not explain what it means to be a computational model for it, and does not provide general principles for abstracting DSLs from network architectures nor discuss the possible design space.  Section 3 says "While we give a detailed explanation [of the relationship between RASP and transformers] in the appendix..." but the appendix contains no such analysis, only more details of RASP in isolation.  I also find it strange and somewhat of a red-flag that RASP does not seem to be compositional, for example, it does not seem to include a computational model of feed-forward networks within it.  The `zipmap` operation nominally corresponds to the feed-forward stage of the transformer-encoder, but RASP does not seem to include any restrictions on the function being zip-mapped.

I think the paper could be strengthened significantly if it began with a DSL for building computation graphs sufficient to express transformers, and then presented a compositional (if not fully principled) way of abstracting this DSL into a traditional DSL that can serve as a reference computational model for the original version.  Ideally this process generalizes the two prior computational models they refer to, i.e. CNNs as sequences of filters and RNNs as state machines.  I think it is also critical to make explicit what properties are being relaxed and what differences are being abstracted away.  For example, would the authors consider RNNs and LSTMs to have the same reference computational model or would differences be preserved in the abstraction? Are there RASP programs that cannot be realized by transformers, or vice-versa? More generally, what does it mean for one language to be a computational model of another one, and what does the design space look like?

If the main weakness is that the authors do not ground their computational model to transformers theoretically, a related weakness is that they do not ground their computational model to transformers empirically either.  I think the paper could also be strengthened significantly by simple empirical experiments, for example using their RASP implementations of various simple functions to make predictions about the accuracy of transformers trained on those tasks as a function of the number of layers and heads they are provided.  I would be particularly interested to see how sharp these curves are. Is there a phase transition once the minimum required layers/heads are provided, or is it much more gradual?  Is there any evidence that the transformer actually learns these reference programs?

Miscellaneous comments:
- I found the description of RASP unnecessarily difficult to follow. There are conventions for introducing DSLs, e.g. presenting the grammar and then the semantics.  There are also some inconsistencies, with 'aggregate' introduced as taking two arguments but then used in the prose taking a mysterious third lambda argument.
- It is not immediately obvious what it means for one RASP function to call another as a subroutine.  Is it assumed that any such subroutine has one distinguished input that must always have the same size as the distinguished input to the original RASP function (so that `indices` and `length` are the same)?
- I think the inclusion of non-float types merits more discussion. For example, is it important that there is a boolean type?
- The section on logic programming is too informal, with phrases like "We suggest approaching this task in RASP as follows..." and "If a trained transformer ..., this may explain ...".  Does RASP permit one or more decision procedures for horn clauses? If so, what is the code?  Do you hypothesize that the transformers in (Clark et al. 2020) are learning hybrid forwards/backwards reasoning? If so, how might you test this hypothesis?
- The impossibility result for sorting should discuss non-comparison-based sorting algorithms (e.g. radix sort) or else qualify the claim.
- The RASP analysis of the sandwich transformer results (S4.2) does not seem particularly illuminating.
- There is essentially no discussion of related work.

Minor:
- the second sentence of the intro repeats "language"
- in 'The Base Sequences' paragraph, there is a double comma and a dangling close-paren
- the `sort` code uses `seq` instead of `vals` in the last line
- in explanation of `select`, `f` is referred to as a "selection function" even though it has a different type
- top of page 4: attention distribution <MISSING PERIOD> Hence

review_title: Very interesting but underdeveloped

Meta-review: The paper presents a computational model for transformer encoders in the form of a programming language (called RASP), shows how to use this language to "program" tasks solvable by transformers, and describes how to use this model to explain known facts about transformer models.

While the reviewers appreciated the novelty of the main idea, the evaluation and the exposition were found to be below the ICLR bar. As a result, the paper cannot be accepted this time around. I urge the authors to prepare a better new version using the feedback from the reviews and discussion.  In particular, the paper would be much stronger with a discussion of how the ideas here can help with improving the transformer model, and whether these ideas generalize to models other than transformers.
Decision: Reject