Thinking Like Transformers
Authors: Gail Weiss
Yoav Goldberg
Eran Yahav
Venue:  (2021)
Keywords: transformers
interpretability

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 the simple primitives of select, aggregate, and zipmap, around which we form a programming language: the Restricted Access Sequence Process-ing Language (RASP). We show how RASP can be used to program solutions to tasks that could conceivably be learned by a transformer, augmenting it with tools we discover in our work. In particular, we provide RASP programs for histograms, sorting, and even logical inference similar to that of Clark et al. (2020). We further use our model to relate their difficulty in terms of the number of required layers and attention heads. Finally, we see how insights gained from our abstraction might be used to explain phenomena seen in recent works.

Under review as a conference paper at ICLR 2021
THINKING LIKE TRANSFORMERS
Anonymous authors Paper under double-blind review
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 trained models, transformers have such familiar parallel. In this paper we aim to change that, proposing computational model for the transformer-encoder in the form of a programming language. We map the basic components of a transformer-enoode - attention and feed-forward com- putation into the simple primitives of select, aggregate and zipmap, around which we form programming language: the Restricted Access Sequence Process- ing Language (RASP). We show how RASP can be used to program solutions tasks that could conceivably be learned by transformer, augmenting it with tools we discover in our work. In particular, we provide RASP programs for histograms, sorting, and even logical inference similar to that of Clark et al. (2020). We further use our model to relate their difficulty in terms of the number of required layers and attention heads. Finally, we see how insights gained from our abstraction might be used to explain phenomena seen in recent works.
INTRODUCTION
While Yun et al. (019) show that sufficiently large transformers can approximate any constant- length -eeeeneeee-e function, and |ahn (2019) provides theoretical limitations on their ability to compute functions on unbounded input length, neither of these provide insight on how transformer may achieve a specific task. Orthogonally, Bhattamishra et al. (2020) provide transformer constructions for several counting languages, but this also does not direct us towards general model.
This is stark contrast to other neural network architectures, which do have clear computational models. For example, convolution networks are and finite-state automata and their variants have been extensively used both for extraction from and theoretical analysis of recurrent neural networks (RNNs) (Omlin & Giles 1996 Weiss al. 2018 Rabusseau et al.) 2018 Merrill et al., 2020), even inspiring new RNN variants (Joulin & Mikolov 2015).
as sequence of filters (Zhang et al. 201 8),
In this work we propose a computational model for the transformer-encooder in the form of a simple sequence-processing language which dub RASP(Restricted Access Sequence Processing Language). Much like how automata describe the token-by-token processing behavior of an RNN, our language captures the unique information flow constraints under which a transformer (aawwan et al. 2017) operates as it processes input sequences.
Considering computation problems and their implementation in the RASP language allows to "think like a transformer" while abstracting away the technical details of a neural network in favor of symbolic programs. RASP program operates on sequences of values from uniform atomic types, and transforms them by composing a restricted set of sequence processors. One pair of processors used to select inputs for aggregation, and then aggregate the selected items. Another processor performs arbitrary but local computation over its (localized) input. However, access to the complete sequence is available only through aggregate operations that reduce a stream of numbers to a scalar. The key performing complex global computations under this model is to compose the aggregations such that they gather the correct information, that can then be locally processed for a final output.
Given a RASP program, can analyze it to infer the minimal number of layers and maximum number of heads that is required to implement it as a transformer. We show several examples of expressive programs written in the RASP language, showing how complex operations can be

---

Under review as a conference paper at ICLR 2021
def sort count_conditions
num_prevs
(keys, indices), (keys, indices),
lambda key, key' iind';
(key' < key) or
(key' key and ind' ind))
porcc_ssote__diee val select (indices num_prevs, lambda i == np)
return aggregate (select_ssee sorted vals)
Figure RASP program taking two sequences vals, keys and returning sequence y sorting the elements of vals according to keys, e.g.: if vals(z)=(a,b,, and keys(z)=[0,4 2,, then y(æ)=[a,c,bl]
implemented by transformer. Thinking in terms of the RASP model also allows shed light recent empirical observation of transformer variants (Press et al. 2020) and find concrete limitations of "efficient transformers" with restricted-attention (Tay al. 2020).
THE RESTRICTED ACCESS SEQUENCE PROCESSING LANGUAGE
In this section, we present the the Restricted Access Sequence Processing Language (RASP), RASP assumes a machine composed of several functions taking and returning a fixed number of primitive arguments, and simple memory accessor that is controlled by these processors. The select, aggregate, and z zipmap operations which we present will define and constrain how the processors work together to process an input sequence.
processors, each of which can only run
We will focus here only on the language itself, leaving the discussion of its exact relation to trans- formers Section
Overview A RASP program works by manipulating sequences, occasionally with the help of selectors. Sequences contain values of uniform atomic type, such as booleans, integers, floats, or strings. They are functions used for selecting elements from sequences, and are used (together with the appropriate operations) only in the process of creating new sequences, All sequences in RASP are lazily evaluated, meaning that their length and contents are not populated until passed an input.
The Base Sequences Every program in RASP begins from the same of base sequences, and then creates new ones using a small number of core operations. These base sequences are indices, length, and tokens, evaluated on input 22, -.. Fn their names suggest: (0, 1,..,,... 1), (n, n,..., n) (of length ni), and (œ), 22,..., Tn), respectively.
Combining Sequences Sequences can be combined in an 'elementwise' manner, such that the value of the resulting sequence at each position i is function of the values in the combined sequences at position (similar to map operation), or have positions 'mixed' in more complicated ways using selectors, which are functions N N (True, False) whose sole purpose is guide the combination of existing sequences into new ones.
We present the basic ingredients of RASP using an example. Figure shows simple RASP function for sorting sequence of values according to sequence of keys. It accepts an input sequence vals and uses the base sequence indices, that is available any RASP program, compute its output in three operations as follows:
count_conds t tioned Line 2 creates a new sequence that counts for each element of keys the number of "previous items" it has in keys, where the "previous items" are defined to be all items that have a lesser value, or equal value and lower index. Thus, num_prevs creates sequence of numbers, representing the target sorted position of each item.
2. select of line 7 creates position j for which indices[i] is equal to num_prevs[ [j]. Effectively. will direct the elements in each position j towards their target location
selector which will focus each position i the corresponding
2

---

Under review as a conference paper at ICLR 2021
3. Finally, aggregate of line applies select_sorted val to vals, moving each i-th element vals to its calculated sorted position num_prevs(i].
We now describe the base operations of RASP in-depth, occasionally presenting an example on the hypothetical input sequence z of length
zipmap The zipmap operation takes tuple of sequences and element- processing function f, and applies per-index to the values in those sequences to create new sequence. For a simple example, ym= (indices indices), lambda i,j:itj) creates sequence that always evaluates to (0, ..., 2n - 2).
aggregate The aggregate operation takes selector s, a sequence x, and an optional parameter defaul t, and averages subsets of the values of into new sequence y as follows: for every index y[a] is the average of x[jo], x[ji]. ...][] where Jo J1, .... .3
the 0, then y[jo] is assigned the value in faflutt. For example: if s(i, j) returns True iff i is odd and j=0, and the value in default d, then will evaluate to (d, x [O], d, x[o],...,,yl
indices j E [n] for which s (i,j) is True. We say is the focus width of s at i. If
1])
where y[n-1] is either d or x[O] depending the parity of n.
select The select operation takes two sequences-tuples and other=(ot), .ot,,..., and function f expecting k + atomic values and giving boolean output. It composes these create a selector s as fol- lows: for every two indices i. s(i,) is the output of f on the i-th and j-th slice of me and other respectively, i.c. ((i.j)=f (m; [i] [t].oot[[]]...tt(i)]] For a simple ex- ample, in s=select (indices,). (indices,) (indiccs then m; mindices,, ot, =t and the same selector we used for our example in aggregate above.
lengths and I.
me=(m; ................................ m,.)
lambda mi, oti
oi mix2==1 and oti==0),
count_conditionn This operation takes the same parameters me, other and as select, but this time returns sequence y describing the number of selected influencing positions for each output position that s=select (me, other, f) would have created. In other words, for each i, y[i]= & where ji...., jk: is the set of positions for which sii.))=True. For example, h=count__ cercount_condii t ioned (tokens,) ,), (tokens, ,), lambda a, b:b:a==b) returns an in-place histogram for the tokens in the input sequence: h("abaa") =33, 1,3,3).
This concludes the base operations of RASP all other operations shortcuts for combinations of the above 4, occasionally with the base sequences.
Sugar
We implement RASP with variety of syntactic sugar, presented fully in appendix Briefly:
1. When applying zipmap to single sequence, it may be passed directly without using a tuple, e.g.: ripmap(indices (indices, f) is equivalent to zipmap (indices, f))
2. zipmap has sugar for most of the binary operators, e.g.: for two sequences x,y, then x+y is sugar for zipmap ((x,ap((.))) 1ambda a, a.b:)
3. Whenever the focus width aggregate(s, de does not explicitly compute the division. In this case the values of do not have to be numbers.
some index is ("up-to-one selection""),
4. aggregate accepts one additional optional parameter elementwise_function The full order of parameters of elementwise ffefctinnnion is as follows: aggregate f, is equivalent to aggregate (x, deffullltt=)
eeleeeewwiseefunttee defaul and the use
2.1 EXAMPLES
We now present some more example RASP programs, by increasing order of complexity.
Simple Examples The first and simplest example is to compute in-place histogram for some sequence vals. This is achieved with single application count_condi tioned: hi osstorrarrcccmttcooooottooodddld vals, lambda a, b==bb=
3

---

Under review as a conference paper at ICLR 2021
def fy_frrque (vals, (
hist count_condi tioned (vals vals, lambda a, a,b:a==b)
num_earlier count_conditione
(indices, vals), valss,
lambda iq, vq, ik, (v (vq==vk) and (ik<iq))
has_earlier num_earlier
unique_vals zipmap (vals, has_earlier))
lambda h, if not h_e else default)
masked_hist = hist - (length has has_earlier) return sort portquqqqee_ve valls key==masked_hist)
Figure 2: RASP program sorting the unique elements of sequence vals by decreasing frequency. Lines 6 and 7 show syntactic sugar for multiple simple zipmap operations, e.g., line 6 can be written has_earlin
pmap ppmap(num,__m qoum_aarlirr 1ambda n: n;n>0). This program requires a default atom da of the same type vals, to put in place of all otherwise-dupllcated values in its result. For example, by_freuuency (tokens_str, "-") ("abacca") will return "acb--".
From Length to Parity While length is provided as a primitive in the language, it can actually be achieved as composition of the other base operations and sequences. This is done by comput- lambda : :Tue) followed by 1/aggregate(full.
indices, lambda i:int(i==0) (the fraction elements equal to in indices, inverted). From length and that then define count (vals, v), function taking any sequence vals and value
ing Full_s=select(C)
same full_s and returning a new sequence counting the number of appearances of v in vals. The implementation of count is simply Length#aggra angregate (full_s, vals, lambda e:e==v). count in turn enables us to write programs like parity simply as count (tokens, 1, 1)x2==o
Reverse We reverse a sequence seq with the help of up-to-one selector mapping each position to its opposite: flip_s = select (indices, length-1-indices, lambda m, mtthhm===thh) We use flip_s re-order the tokens of seq: reversseaggreeateeeiii...ss
Balanced Parentheses For balanced parentheses we use count_ tioneditieed twice, storing in prev_opens and prev_closes the number previous "(" or ")" (respectively) tokens each posi- tion has, including itself. The sequence is balanced if
prev_closes has no negative values, and is 0 position length-1. These two qualities can be easily computed using two final select- aggregate pairs, and then combined with zipmap.
Most Frequent Tokens In fig. we show how RASP can be used arrange for any input sequence the most frequent tokens in without repetition. The solution has 2 parts: first, we compute the histogram for all the tokens, and mask it such that all but the first of each token given a negative value. Then, we sort the tokens according to the masked histogram. The solution uses the sort function from Figure
def nount_conditioondd (me, other, other otnert(indices. # tuple concatenation, indices end s_with_e select other,lamben <a::(x([[:))))) (a[-1]==0)) s_just_0 select (me (me, other, lambda =x: and (a[-1]==0) frac = aggregate (aggate(s_wvae (s_with_e indicees, lambda i:int (i==0)) 5.
count_outside_@ = (1/frac)-1
count_in_@ aggregatess_withh O) lambda :1, defalult)))) return count_outside_e count_in_@
Figure 3: Implementation of the operation count_conde tioned in terms of indices and the other base operations, assuming that other indeed tuple of sequences (and not single one).
'This does not contradict with the findings of Hahn 2019), who showed that parity is not computable in transformers when each selector restricted to width / ("hard attention").
4

---

Under review as a conference paper at ICLR 2021
Count Conditioned The operation count_ tioned is powerful part of RASP, appearing in many other programs. Surprisingly, it is realisable as a composition of the other operations (and base sequence indices). Understanding its implementation is interesting for learning how to "truly" think like a transformer, and we present the code in Figure 3 The intuition as follows: we compute the select whose width want to calculate twice, once such that it also selects the position 0, and once such that it only selects this position. We then aggregate both these values, broadcasting 1 from position and 0 from everywhere else, and using default value The first aggregate computes for each position the inverse of the number of selected positions (excluding 0) plus one, and the second computes whether that position would also focus on 0. A straightforward zipmaps then gives us the result. To further help the intuition, we present in fig. 4 the computation flow for his histogram calculation, when count_condi tioned is implemented as described here.
layer
bead (Bod conditonn bot only Ot
bead (tod all concitions, and 0.
Iadions
Other bolbens
Other
tolents
Insiicza
defasl:
(XC beg
defuolt:
xaay
0
cluck O, for coediton (as Bost) Loopo//oo/nno.p/p (u))
[u lid oubiide ()) fis condition (.4) (il.5/o.533 0.533 0.583 O
e cerside 01), for condition) 1.0
0.333
31335
0.533
0.5
for
0.0
ocert cenaiee
2.0
from (0)
FR
F
frrm (1)
loketa, Matoggars
Figure The computation flow for the sequence (ertogrramtookssssttt applied to input sequence "hello", when implemented in terms of select, aggregate, and zipmap.
Note Many of the functions provided with RASP can be expressed in terms of count_condie t tioned such as count (which counts how many elements in a sequence are equal to a given value) and contains (which checks if count greater than 0) - but this is not necessarily an optimal implemen- tation with respect to number of heads it uses. The RASPlibrary provides optimal implementations.
2.2 IMPLEMENTING SYMBOLIC REASONING A LA ROVER
How might a transformer implement reasoning, as in Clark et al. (022)) RASP empowers to clearly think about such problems, and we sketch solution direction here. We begin by reformulating the task Clark et al.) to form that focuses on the core problem, moving away from natural language into more "concrete" domain, and by limiting the type of relations we will consider.
In the work of Clark et al., a transformer is presented a sequence of statements and a query Q. and must recognise whether Q is implied by the previous relations or not. For example: al A1, bEA1 = bEA2, EA22 evaluates to True, whereas al şA1, al EA2? evaluates to False. Different inputs for this task can have different depth: the number of 'logical hops' needed to correctly identify whether the query statement true.
Note. The original work accepts this input in natural language, c.g., "Alan is young. [...] If someone is young then..." ", and allows statements with more complicated logical form, such as a1EA1AalEAt = al CB. In this section consider only simplified and symbolic version, in which the statements are limited to the form of the previous paragraph. We assume the statements are separated by special token J.
We sketch this task in RASP as follows: first, mark each statement 'block' in the sequence by its index (as block), by counting for each token the number of separators before it in the input. Set aside the
5

---

Under review as a conference paper at ICLR 2021
final block (the query), it is the set of tokens with separators after them. For each remaining block mark whether it is a relation (E or f) or inference (-+) statement. Then, for each relation block, note at the position of the set token the element and whether it is inside or outside, and similarly over the element token note the set. Next, for as many repetitions as the logical depth that the program should cover: share information between all elements and element information between all sets (including from inference blocks, which initially have none initially empty), and then apply one logical step 'locally" each inference block. Finally, for the query, seek any occurrence of the set token in the sequence, and return whether the element token is listed there in its contents.
Generalisation on Inference Depth A similar solution the one we have proposed would to make all of these logical inferences backwards from the query, i.e. by propagating backwards the requirements that would be sufficient to answer the query. If trained transformer implements both of these solutions in parallel (for instance, to increase its robustness), this may explain the generalisation to greater query depth observed by Clark et al.
RELATION TO TRANSFORMERS, AND ANALYSIS
We discuss how RASP relates to the real transformer architecture, and how it may also be used to compare transformer variants, or analyse the 'difficulty' task for transformers.
Connection of RASP to Transformers The select and aggregate operations of RASP corre- spond to the antention-scoring and then pooling of transformer self-attention heads, the zipmap operations correspond the feed-forward sublayers, and the computed sequences correspond head or feedforward inputs and outputs. indices and tokens represent the initial input, while length and condi tioned_ _oneedinnniinssss are in fact combinations of the other primitives. The persistence of sequences such that they may be accessed multiple times over the course of a RASP program is encouraged by the existence of skip connections in the transformer architecture. appendix [A] we consolidate these connections, giving full description of transformers, and showing how any given transformer can be represented in the RASP language (provided a slight generalization of select?).
3.1 PREDICTING TRANSFORMER COMPLEXITY WITH RASP
The purpose of RASP is to help us reason about the computation process enabled by transformer. We find that RASP programs lend themselves easily to 'width' and 'depth' analysis, enabling to predict the number of heads and layers that transformer will need to implement the same solution. We discuss this analysis now, and evaluate the predictions it provides in Appendix B
For any given RASP program, we can compute the minimal number of layers required to implement it in transformer, and upper bound the number of heads this implementation requires. This is provided its internal dimensions are wide enough to replicate the given processing functions. This analysis can give us intuition regarding the relative difficulty of different tasks for the transformer architecture, where each algorithm we find for a task gives us an upper bound on the number of layers and heads a transformer needs solve it.
We implement such an analysis and provide draw_come Baa___om___aaeeeeeeeeee__e flow function, which automatically positions each attention head using greedy scheduler, and displays the computation flow accordingly (see fig. 4 and others in the supplementary material).
similar analysis can be done for different "primitive" computations in isolation, giving us intuition on the "cost' of various common computations: how many additional heads and layers each compu- tation adds when applied to a previously computed sequence. For example, our implementation of sort takes 2 layers, and so whenever we apply it to a computed sequence we know it will increase our program's 's depth by 2 from that sequence.
"This version is omitted from RASP purely in the interest of clarity for the programmer. 'The reason the number of heads can only be upper bounded is because it is possible that some selects in the program equivalent, can be combined into a single select without interfering with each other, but it is impossible to identify this statically.

---

Under review as a conference paper at ICLR 2021
Algorithm for computing program depth and width As noted, the first 3 base operations of RASP - select, aggregate, and zipmap have direct parallels in the transformer architecture, and so we may easily analyse the result of any RASP program see how many layers and heads it would take to realise in an actual transformer. (For length and count_cond tioned, we analyse them in terms of their deconstruction the other operations and sequences.)
The first part of the analysis is simple: every sequence and selector is initiated with a "minimum depth" d, reflecting the earliest layer at which it can be computed, and so the minimum number of layers needed to create any given sequence is d. d is computed for each new sequence as follows:
1. The base sequences indices and tokens have = 0, as they are input to the transformer rather than part of its computation.
2. Any sequence created from a zipmap is given d equal to the maximum d of the inputs to that zipmap, as it can be created immediately after the last of them in the same feed forward computation that concludes it.
3. Every selector gets d equal to the maximum d of its creating sequences X plus 1, to reflect the fact that all of them must be calculated before it can even begin (as multi-headed attention happens only once, at the beginning of each layer).
4. Any selector created from an aggregate has d equal to at least that of its creating selector, and least one plus those of the input sequences the aggregate operation (as they must be passed through the attention to create the new sequences).
RASP makes it easy to access all sequence and selectors on which an unfinished value is dependent, and allowing us to analyse not only the depth but also the width of a given program. The width of the computation is a reflection of how many (unique) selectors are being used at every layer of the transformer: the number of attention heads needed to mimick that layer in a transformer. We say that a selector is being used at some layer if sequence that is aggregated from s is calculated at I. This is because is possible a selector s may have minimum depth but only or also used at later layers: for instance if the sequences needed for the aggregation operation using 8 are not yet ready.
Similarly, a sequence does not need to be computed at minimum possible depth, as it possible will only be needed much later. Hence there is no one analysis for a given program, and there is room for creating a scheduling algorithm that minimises the maximum width of the transformer, i.e., the maximum of the widths of all layers (useful, as transformers tend to be created with uniform width).
4 IMPLICATIONS FOR TRANSFORMER VARIANTS
4.1 RESTRICTED ATTENTIOON TRANSFORMERS
Multiple works propose restricting the attention mechanism of transformers in order to create more efficient transformers, reducing the time complexity of each layer from 0(n2) to ((noog(n) or even O(n) with respect to the input sequence length n (see Tay et al. (020) for survey of such approaches and their complexity). Several of these do so using sparse attention, which the attention is masked using different patterns to reduce the number of locations that can interact (see for instance (Child al. 2019 Beltagy et al. 2020 Ainslie al., 2020 Zaheer et al., 2020 Roy et al., 2020).
Considering these variants of transformers in terms of the RASP language, allows us to reason about the computations they can and cannot perform. In terms of RASP, these variants of transformers all impose restrictions on the selectors, forcing some of the n² index pairs (i,j) to False.
Figure [ showed how to implement sorting of an input sequence with arbitrary alphabet size, compar- ison function, and length². We now prove that RASP variants where the selector is restricted to O(n) pairs (i.e., transformer variants with sufficiently restricted attention), cannot sort.
'Except in the special case where this maximum d is 0, and the zipmap is not being called from within an aggregate, in which case the sequence is assigned d = 1. This reflects that least one layer must be used reach the first feed-forward computation, but also that attention may do little processing itself before it "aggregates", using the linear translation Providing sufficiently stable word and positional embeddings, a practical limitation that applies to all transformer variants.
7

---

Under review as a conference paper at ICLR 2021
The computation model of RASP and indeed of all transformer variants allows comparison of values between more than one sequence position only during the select operation, i... only while computing the attention distribution Hence, all comparisons necessary for sorting must be applied in select. It follows that whenever select is restricted such that it compares at most O(n) index pairs per head, constant number of heads and layers will be sufficient for the model perform sorting on arbitrary length - as sorting is known to require at least (n)) comparisons.
Thus, variants of transformers in which the attention is masked to impose O(n) complexity require at least (1)) layers to sort. It also follows that they require (I)g layers to implement count_condi tioned, as we see in fig. that count_condi inditioned one can be applied to create sequence (num_prevs) which is sufficient to complete a sorting operation with only O(n) further operations.
4.2 SANDWICH TRANSFORMERS
Recently, Press et al. (020) showed that reordering the attention and ferd-forward sublayers of a transformer affects its ability to train on language modeling tasks. In particular, they showed that 1. pushing feed-forward sublayers towards the bottom of a transformer weakened it, and 2. pushing attention sublayers to the bottom and feed-forward sublayers to the top strengthened it, provided there was still some interleaving in the middle (making a sandwich transformer).
Considering the base operations of RASP helps us understand the observations of Press et al. In RASP, the feed-forward and attention sublayers are the zipmap and aggrettaggeegate (or gather for short) operations. Any arrangement of the sublayers into set architecture, from the 'vanilla' transformer to the variations considered in (Press et al.) 2020). imposes a restriction on the number and order of RASP operations that be chained in RASP program. For example, an architecture in which all feed-forward sublayers appear before the attention sublayers imposes that no z zipmap operation may be applied to the results of any gather operation.
In RASP, there is no value to repeated applications of z zipmap before the first gather, as no further information can be generated beyond that already described by indices and tokens. This imme- diately explains the first observation of Press et al. (2020). Conversely, an architecture beginning with several attention sublayers i.e., multiple gather operations will be able to gather large amount of information into each position early in the computation, if only by simple rules. More complicated gathering rules can be realised by applying zipmaps to the gathered information before generating new selectors', explaining the interleaved feeentioon/eed-forwwae middle section present in the discovered architecture.
EXPERIMENTS
To evaluate the relevance of the RASP language to transformers practice, we train transformers on small set of synthetic tasks and compare their results to the head- and layer- bounds and attention patterns predicted by RASP programs for the same tasks.
While no RASP program promises to he unique solution to the task it solves, several of the trained networks find solutions similar to those predicted by RASP. Among the most striking of these is the transformer trained to compute in in-place histogram, e.g. $abbd-> (1, 1, 2, 1). We considered this (BOS) token S, writing
task when the input sequences are presented with a beginning-of-sequeen single-head RASP program for it and training single-head transformer it. Visualizing the selection/attention patterns of these two heads (one RASP and one transformer) showed an identical pattern- see Figure
We present the single-head RASP program for this task in Figure 6 Its operation is as follows: first, the selector same_and 0 focuses each position i all positions j containing the same token as i, and also on the position 0. Hence the width of this selector at each position i * 0 is exactly one plus the value is that should be output at i. Aggregating the sequence (L, 0, .... 0) with this selector (which at each location i, from which vú can then
always includes focus on 0) gives us the value a; be recovered with a simple zipmap.
"Actually, the unbounded power of the processing functions f that RASP allows passing into select and aggregate technically renders zi zipmap unnecessary.
8

---

Under review as a conference paper at ICLR 2021
1.0
0.4
0.0
0.0
0.8
0.0
b
0.4
0.0
0.0
0.3
0.0
0.0
0.0
0.0
0.6
b
0.4
0.0
0.3
6.0
0.0
0.0
0.0
0.0
0.3
0.0
0.2
0.0
0.0
C
0.6
0.0
0.0
0.0
0.4
0.0
0.0
0.3
0.4
0.
0.0
0.0
0.0
0.
0.0
0.2
0.0
0.3
0.0
0.0
0.3
0.0
0.0
02
0.0
g
0.7
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.3
b
g
Figure 5: The attention (left) and selection (right) patterns of single-head transformer and single- head RASP program both trained/written for the task of in in-place histograms. We visualise both on the input sequence $jibbiejig. On the y axis, the sequence acts as the query, describing the output locations for which new values must be computed, and on the axis it acts as the key, describing input locations being selected to compute these
values. Specifically, each row in the attention pattern describes the self atf-attennton distribution of this head over the sequence Sjibbiejig. The transformer has clearly learned the same pattern that used by the RASP program.
same_and_@ select (tokens (tokens indices), lambda t1 t2, 1: (t1==t2) or (i==0)) inverted_count aggregate (same_and in indices, lambda inint
histogram_given.cn = (1/inverted_count)
that computes an in-place histogram on the input tokens, under the assumption that the first token is always special begimming-of-seqeene character $. The selector same_and, builds on the same intuition as the s_wi th_ selector from implementation of couut_conditioned
Figure 6: Building the RASP sequence his histogram_given
The direct parallel between our program's 's only selector and our trained transformer's 's attention pattern (Figure suggests that this RASP program describes the exact mechanism that our transformer has discovered.
We present further experiments on additional tasks in Appendix B
CONCLUSIONS
We abstract the computation model of the Transformer-encoder into simple sequence processing language that captures the constraints on information flow in a Transformer. Considering computation problems and their implementation in the RASP language allows abstracting away the technical details of neural network in favor of symbolic programs, Moreover, provided it uses reasonable element-prooe processing functions, we can analyze any RASP program to infer the minimum number of layers and maximum number of heads required to implement it in a transformer.
"think like transformer" while
show several examples of expressive programs written in the RASP language, showing how complex operations can be implemented by transformer. We train several transformers on these tasks, and find that RASP helps us predict both the correct number of heads and layers to use for these tasks and also the attention patterns that the transformers realise to solve them. Additionally, we use RASP to shed light on an empirical observation over transformer variants made by Press et al. (2020), and find concrete limitations of some "efficient transformers" architectures.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Joshua Ainslie, Santiago Ontañón, Chris Alberti, Philip Pham, Anirudh Ravula, and Sumit Sanghai. ETC: encoding long and structured data in transformers. CoRR, Abs/2004.08483. 2020. URL
https://arxiv.or http://w.wgg//bb///////o 2004 220./00244..00 08483
Dzmitry Bahdanau. Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
0473
Iz. Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. CoRR, abs/2004.05150, 2020. URL
hwtp://wwwwrrrbbb//...... 05110
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages, 2020.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. CoRR, 1as//904.105500 2019. URL httpp://axxii http://aarrii.oogrbbbb////b///// hwtgg/bbs/19ee 10509
Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers soft reasoners over language, 2020.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. CoRR, abs/1 007.03 2018. URL http:ttp/////iiiorrrr wtt.a/i...r./////////a/o/oo /10b//////..00 10/1/7887.00899
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. CoRR, abs/1906.06675, 2019. URL httt:://aaxxi..rg/bbb/////// 06755
Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366. 1989. doi: 10.1016/0993-6080099 90020-8. URL http:tttt:::ooorrg///// 1011000168993 (000008886660000899990------
Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented re- current nets. In Corinna Cortes, Neil D. Lawrence, Daniel Lee, Masashi Sugiyama, and Roman Garnett (eds.). Advances in Neural Information Processing Systems 28: An- nual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 190-198, 2015. URL http: //papers. nips. cc/paper/ thw.rrrin-ggggrrriiieeeeeeeeeeee
sewiith-stee th- aaaaaaaaaagteetteereerreee-----e
Minh-Thang Luong, Hieu Pham, and Christopher D. Manning. Effective approaches to attention- based neural machine translation. CoRR, 1508. 04025
2015. URL http:/tt://arx/w.orr /
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. A formal hierarchy of RNN architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 443 459, Online, July 2020. Association for Computational Linguistics. doi: 10. (0.18653/v1/2020.0 acc-mmin.3mmam main.43. URL /ttttp::/wwww..rr wwwwwb. wwtp://wwwwwwww..////a.oo.ooo//. 2020. www.aclmmai.4...
Christian W. Omlin and Lee Giles. Extraction of rules from discrete-time recurrent neural networks. Neural Networks, 91):41-52, 1996. doi: 110016608933-08000550000008 URL
https://doi. org/rogg//// 10. 1016/0893- (155:/8899360000555))0
Ofir Press, Noah A. Smith, and Omer Levy. Improving transformer models by reordering their sublayers. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.). Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020. Online, July 5-10, 2020, pp. 290229960000 3005. Association for Computational Linguistics, 2020. URL https 7/www. www.:w.www..b..... org/ att http:////ooolll//222
meee-main... 270/
Guillaume Rabusseau, Tianyu Li, and Doina Precup. Connecting weighted automata and recurrent neural networks through spectral learning. CoRR, abs/1807.01400 2018. URL htLL: //t////rxxvv org/abs/1807 08146
10

---

Under review as a conference paper at ICLR 2021
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers, 2020.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Autention is you need. CoRR, abs/ (bss/1706.037622 2017. URL
http:://arxiv.org/bbbs///
83762
Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention in a transformer language model. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Net- works for NLP. pp. 63-76, Florence, Italy, August 2019. Association for Computational Linguistics. doi: 10.18653/v 1/W 48-8. URL https: //ww:. htttp::/www..a..eeb.orrrr http://wwww.rg/tth.ooooooeoooeee
9-008
Gail Weiss, Yoav Goldberg, and Eran Yahav. Extracting automata from recurrent neural networks using queries and counterexamples. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmssässsan, Stockholm, Sweden, July 10-15, 2018, pp.
2018. URL/http: URL/http://proccediig wtt.s//......eee////eeeisssssss. htt.s//w....//./////ooo/oooonon.
html
Chulhee Yun, Srinadh Bhojanapalli,, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequeee
functions?, 2019.
Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. CoRR, abs/2007.14062 2020. /tthstsss: /arxiv or wrgg/b///////// 14062
Quanshi Zhang, Ying Nian Wu, and Song-Chun 7hu. Interpretable convolutional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
A TRANSFORMERS IN RASP
RASP is almost but quite strict over-approximmaiin of transformerr-ncooders. In this section, we show how the addition of score, generalisation of select that may assign non-boolean values index pairs, makes RASP strict over-approximation. In particular, we give explicit translation from any given transformer-encode to RASP program, provided the augmentation with score. If the reader prefers start there, full description of transformers is given section D (with notations in the preceding section).
We now introduce the score operation, and expand aggregate to receive scorer:
score Similarly to select, the score operation takes two tuples of sequences me=(m1,... ..... ... ,mk and other= ... otl), and function expecting k+1 atomic val- ues. This time however, f may return any non-negative float value. It creates from these scorer similarly to how select creates selector from its inputs.
aggregate The aggregate operation is expanded such that it may receive either scorer or a selector where it previously accepted only a selector. When it receives a scorer, each y[i] is assigned the weighted average of all the values of x, according to the values in the scorer:
ΣiEIN s(i,j)xx[]]
y[i] Eje(n) s(i,j)
Intuitively, the select operation, and the application of aggregate to selector, can seen as the special case of a score-see score-select pair in which the scorer has only given scores of 0 and 1. It does have one difference that it also allows for a default value which may be used when the total score for some index i is 0. However, this can be seen as sugar: it is not difficult to create mechanism similar to that of count_ avoid the direct use of default in aggregate', Moreover, if the data is always given with special beginning-or -owniiinn-o--suuunneeeee (BOS) token, then the default value can simply be loaded from that location whenever other focus is found.
tioned in order to recognize when a selector has width 0, and so
'The head and layer analysis of RASP be trivially updated take this into account.
11

---

Under review as a conference paper at ICLR 2021
def elementwise__artt(x,. (e__f,,s))__
1A, n2, el_funcs
def opply.elemenwwsseeprrtssssww
xy tavec
x, att-y = first_half(xy)
x1 IA(att_y) vector addition
res x1 + fx1))(x1))
return totuple(res)
return zipmap(xtatt.3) apply_appplllaelepela wew.eeeeeeeewwwsseerr......
11
12
def layer (x, head_eaddee_e heagh_eights, nl, el_funcs):
13
multihead_y =O
14
for 1q. lv in head_weights:
score (x, lambda Lambaa xixj:
16
exp(scalarprod(
17
1q(n1 (frrsss 1k (a (xixx)))))
18
head_y aggregate(s.x,1v)
28
multihead_y multihead_y head_y
21
here is concatenating tuples sequences return elementwise_parte mwwtihead_y e el_funcs)
22
23
def T_ (layerr_fuucss.....
25
x zipmap ((indices. tokens), lambda i, t,t)
26
for weidhweights,om ell_funcs in layer_funcs:
27
x = layer (x, head_weights n1 ,l, ml,el_funcs) return x tuple of d float sequences
28
Figure 7: Function r_y0 that takes description of transformer and embedding function and returns d RASP+score sequences mimicking the output values of that transformer exactly (where d is the output dimension of that transformer). Note that the loops in T_y0 and layer are 'meta-loops' with respect the generated RASP program: they generate multiple layers and heads, but the number of these is function of the transformer being mimicked and not of the input it will receive.
(R24* be transformer and yo Σ (Rd))* be an input embedding computed as the sum of token and positional embedding, yo(x); = w(xx) + p(t). Then the computation of T A o T can be mimicked in RASP program that writes the output to d float-sqquences and uses exactly LH score and aggregate calls and (H + 1)L + zipmap calls, where L and H are the number of layers and attention heads in T. respectively.
Theorem A.I. Let T (IR4)- -
Proof Sketch In figure we present code that, given the token and positional embedding w - Rd and p: N Idd and all the weights of transformer, recreates that same transformer in RASP. Our code relies on the helper functions tup2vec, vec2tup. first_half and second_half which help convert between the tuples of values given the processing functions by zipmap and aggregate and the vectors they represent. For simplicity in the presentation, we assume here that the transformer given as collection of linear transformations, layer-norms, and feed-forward functions which can be applied to its internal vectors directly.
The main routine is T_y0, which applies the initial embedding and stores it tuple sequences, and then applies each layer to it in turn. This takes L calls to the layer function, each of which computes score-aggregat (with additional zi zipmap before the aggregate) pair times to mimic each of the heads, and then calls zipmap the concatenation of their result to complete the remaining (elementwise) computations of the layer.
Note. Recall that, noted in E when processing function passed to zipmap returns multiple values, zipmap simply generates that same number of sequences. In particular, at all iterations of the loop in T_y0, x is tuple of d sequences where d is the embedding dimension of the given transformer.
We see that, when augmented with score, the RASP language naturally composes the components of given transformer to reconstruct it exactly.
12

---

Under review as a conference paper at ICLR 2021
Why not have score? The motivation for the omission of score from RASP is cleanliness: is far easier to think in terms of select as opposed to score, and we have not yet encountered a problem where used scorers whose values where outside of 0 and 1. In time, as we use the language more and encounter the limitations this choice poses, we may return to score and see what other kind of special cases of it will benefit from including in RASP.
Power of RASP As seen in this section, RASP can (provided this slight generalization of select) represent any transformer. Additionally, we see that not arbitrarily overpowered. For example, it does not allow iterating over sequence of arbitrary length one-by-one perform some gradual computation (as might be done in RNN or DFA), and in general does not allow arbitrary repetition of operations other languages might allow. This is because the number of operations in RASP program is predetermined: RASP programs do not admit loops. This distinction between transformers and RNNs is known, and there is interest in bridging it. For example, the Universal Transformer attempts to introduce loops into transformers, by allowing them to also have a control mechanism that decides whether to repeat layer during computation (Dehghani al. 2018
B EXPERIMENTS
For RASP to be useful, is important to see that RASP programs relate well actual transformer behavior in practice. In this section, we train transformers on small set of synthetic tasks for which we can write RASP programs, and see how the these programs relate to our empirical results.
We consider the following tasks:
1. Count-a: Return the number of 'a' tokens in sequence, e.g., aba-> 2.
2. Histogram:
For each token, its number repetitions in sequence, presented in-place. For example, aababc-> 2, 1).
3. Reverse:
Reversing sequence, e.g.: abc-+cba.
For Histogram, we also consider a variant with a special beginning-of of-seenence (BOS) token S, appearing exactly once the beginning of each sequence (and nowhere else). For example, $aabo-> 2,,
We train transformers for each of these tasks, and test whether RASP programs accurately predict the minimum number of heads and layers needed to perform them. We also visualise their attention distributions and see if they match the selectors used by our programs.
We find that several of the RASP programs presented in this paper show similar attention (selector) patterns those of the trained transformers in practice, suggesting that programming in RASP helps us provide reasonable predictions of transformer behavior. Moreover, we often find that reducing the number of heads and layers transformer beyond the number needed in our RASP program for the same task significantly degrades its accuracy. This suggests that the specific programs we have presented in for these tasks are also optimal solutions.
the alphabet (a, b, d,,, e} with sequences of sizes through 100. These are generated by first choosing the length uniformly from 100, and then choosing each token uniformly from the alphabet. We use 50, 000 train samples, 1, 000 test samples, and 1, 000 validation samples.
Data and Evaluation Unless stated otherwise: for all of the languages,
For tasks giving 'single' output value such as Count-a (which gives number) as opposed to Reverse which gives a new sequence we train the network to return that value in all positions, e.g., aba-+ 2, 2) for Count-a. This makes the visualisation of the attention distributions clearer (as all locations are trying to do something meaningful, as opposed to one), and is also more clearly aligned with the tasks we have described this work.
We measure the accuracy of transformer on batch of sequences as the fraction of total predictions made for those sequences that were correct, e.g. z for a batch with total sequence length 5. For the train, set, and validation sets, we report accuracy as the average batch accuracy.
ic.. after softmaxing the attention scores.
13

---

Under review as a conference paper at ICLR 2021
Architecture We use the transformer architecture provided with PyTorch 1.7.0, with additional single linear transformation and softmax at the end to convert to the output classes prediction. Unless stated otherwise, small embedding and feed-forward dimensions: 20 and 40, respectively. We vary the number heads and layers per task.
Training Method We train with the ADAM optimizer, sin-cosine positional embedding, and dropout 0.1 in the transformer weights. We use learning rate 0.0003, batch size 50, and PyTorch's s Exponentialle a learning rate scheduler with gamma 0.98 (updated after every epoch). Excluding confirmation of a negative result, we train each network for 20 epochs. If network hits 100% accuracy before then, we stop.
Helpful RASP functions In this section will make frequent use of the full-selector (U) O, 1ambba : :Tre) and the function computes aggregate (full_s sequences, lambda =fnt(f*))))) the fraction of input posi- tions for which the f is satisfied on the values of sequences. Note that frac_condi condition requires only layer (after sequences have been computed) with 1 head, and that that head is full_s. Recall also that length is computed: 1ength=1/frac_com condi tion (onniiicess, 1ambbda i:i==0).
f), which
B.1 COUNT-a
To avoid gradient problems from trying to obtain large numerical values from the transformer (c.g., 8), we encode Count-a a categorical task. In particular, create 21 output tokens {0, 1,2, ..., ,0)), and if there are more than 20 a tokens in the sequence we just report 20.
0/2
0.1
8.1
022
0.2
01
Q1
011
01
0.2
01
Q2
01
81
011
0.1
Q2
02
a1
0.4
P
0.
01
a1
01
d
Q2
3
01
002
8.1
a2
01
a1
0.1
0.0
Figure 8: The attention distribution in the only head of a transformer trained on Count-a. The sequence presented on the y-axis as the queries and on the x-axis as the keys, i.e., each row is distribution over the input positions. As predicted by our RASP program (which solves this task using full_s). this distribution relatively uniform.
RASP permits a 1-layer, 1-head program for this task: count_a lengthfrac_comm condi tion tokens, lambda t: t:t=="a"). (length and frac_condi condition share the selector full_s.) Accord- ingly, training a transformer with layer and head on Count-a succeeded, reaching test accuracy 98.9% on the 20th epoch.
The attention pattern of this transformer on the input sequence abbaabcde is shown Figure g While the distribution is not perfectly uniform, it does seem to focus the entire sequence, the use of full_s in our RASP program suggests (contrast for example with the attention distribution for Reverse, in Figure 12
Thhe exact implementation is slightly different account for the case when there only one sequence, but the idea is the same.
(We leave here cautionary tale: if you do not properly scale the colorbar of your attention figure, it will look like the difference hetween focus on different locations is much greater than it is!)
14

---

Under review as a conference paper at ICLR 2021
We stress that this is different distribution that which might intuitively expect for this task namely, an attention pattern focused solely on instances of the sequence and that RASP has successfully pushed to predict it!
B.2 HISTOGRAM
As with Count-a, we encode histograms as categorical task. This time we limit the maximum count to 10, ie.. only the output tokens 1,2,.... 10. (0 is irrelevant it will not appear in an in-place histogram). Unlike most other tasks, for Histograms we use an alphabet size 10: (a, ,.). For histograms,
input alphabet of size 10: [a,b,.....3
1.0
0.0
0.41
0.0
0.21
0.0
0.39
0.0
0.04
0.42
0.04
0.0
0.04
0.42
0.04
0.0
0.0
0.4
0.01
0.27
0.0
0.33
0.0
0.04
0.46
0.05
0.0
0.04
0.37
0.04
0.0
Figure 9: The attention distribution in the single head transformer trained on Histogram. The input sequence abcdeba is presented on the y-axis the queries and on the x-axis the keys, i.e., each row is distribution over the input positions. This transformer does not have enough heads: despite training for 50 epochs, has only reached test accuracy 55%, and generates the incorrect output (1, 2, 1, 1, 1, 2, 1) for this sequence. Similarly, it does not manage to recreate the selection pattern predicted by our RASP program for this task, which requires heads.
10
0.0
011
0.0
0.8
0.0
0.6
0.4
02 0.2
0.1
01
Q1
01
e1
00
The attention distribution in the 2-head, single-layer transformer trained on Histogram. The input sequence aabbccacde is presented on y-axis as the queries and on the x-axis as keys, i.e., each row is distribution over the input positions. The distribution is similar, but not identical, to our count_conde tone implementation. some extent taking the role of the index 0 in implementation: the first head has most tokens focus on themselves, and e, and the second head has most tokens focus slightly more on and than others. d and themselves seem behave inversely to the other tokens.
Figure 10:
particular, seems that the tokens and
15

---

Under review as a conference paper at ICLR 2021
We trained one transformer with 1 layer and 2 heads, and another with only layer and head. After 20 epochs, the transformer with 2 heads reached test accuracy 89.3%. In contrast, after 50 epochs, the transformer with only 1 head was still at accuracy 55%! Increasing its embedding and feed-forwart dimensions to 50 and 100 respectively also did not work: a I-layer 1-head transformer with these dimensions still only reached 79.3% test accuracy after 50 epochs, and this after being past 77+% validation accuracy since the 27th epoch.
Drawing the attention map for the single-head transformer (Figure 9 did not seem to relate to the selection pattern of count_condi tioned at all, unsurprisingly considering that did not have enough heads. See for example the apparent focus b by several query positions not containing as opposed to our expectations of the count_condit mineitiieed focus pattern as shown in Figure
For the 2-heads transformer, we draw its attention maps in Figure I0 The solution has some clear parallels with our RASP prediction of histogram selection patterns of count_ tioned, such as most tokens focusing on themselves in the one head and sharing distribution patterns the other. But we can also easily find differences: in particular, the d and tokens seem to avoid rather than focus on themselves, and the shared focus most tokens in the similar-attentions head is not on but on d and e. There is a possibility that in this transformer, d and are playing role similar to that which we gave to 0 in our implementation of count_condi tioned. We leave a deeper exploration of this to future work.
B.3 HISTOGRAM WITH BOS
it calculates the "width" (number of selected locations) of a hypothetical selector by simulating it along two actual selectors, s_with, and s_just_@, s_wi th_@ is used to calculate for every index the fraction 1/4++1 where d' is the width of s on everything except index O, and $_juut__ is used to make a final adjustment from of to the actual width, depending the focus on 0.
Recall the implementation of count_condi www.coniiiiooo tioned (Figure 3):
If, then, the contents at position O are constant across all inputs, then the second selector s_just_@ becomes unnecessary: any information it conveys be hard-coded into the RASP program (practically, the transformer). It follows that for setups where all input sequences are prepended with special eoginning-of-sequene
(BOS) token, count_condi t tioned be implemented with only one head, using just the s_with 1 selection pattern.
1.0
0.0
0.0
0.0
03
0.0
0.8
0.3
0.0
0.0
0.0
0.2
0.4
0.0
0.0
0.3
0.3
0.0
0.0
0.0
0.0
0.0
0.6
0.4
0.0
0.
3.3
0.3
0.0
0.0
0.0
0.0
0.2
3.0
0.
0.0
0.0
0.0
0.2
0.6
3.0
3.0
0.0
0.0
0.0
0.4
0.0
0.0
0.0
0.3
0.4
3.0
0.0
0.0
0.0
0.0
0.3
0.0
0.0
02
0.2
8.0
3.3
0.0
0.0
0.3
0.0
0.0
0.2
0.0
0.7
8.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.3
Figure 11: The attention distribution for a 1-head, 1-layer transformer trained on Histogram with BOS tokens. The input sequence jibbiejig is presented on the y-axis as the queries and on x-axis the keys, i.e., each row is distribution over the input positions. This transformer appears to have implemented Histogram (with BOS) using exactly the same s_wi th_0 selection pattern suggested in count_conditin tioned implementation! (The second selection pattern in the count_conds tioned implementation, s_just_e 0, is unnecessary when the value at the index is constant.))
16

---

Under review as a conference paper at ICLR 2021
We prepend all of the original Histogram inputs with special BOS token (and their outputs with 1), and train a new I-layer, 1-head transformer on the resulting data set. For gamma=0.99. the results satisfy predictions perfectly: the transformer reaches 99.7% test accuracy in 20 epochs, and drawing its attention distribution (Figure [T) shows that it follows exactly the pattern of the selector s_wi th (For gamma=0.99 98 the attention distribution was also very similar that of s_with_0, but the model reached only 86.4% test accuracy after 20 epochs.)
Discussion of BOS The significance such 'non-input' tokens in transformers has been previously discussed, with different interpretations. For example, [Vig & Belinkov (2019) refer the attention focused on the initial token of a sequence - Seemingly when there is nothing else to focus on as null attention. They report that the null token gathered as much 97% of the attention of some their heads, and suggest that this is consistent with these heads being unimportant to the transformer's overall performance. Conversely, this new result suggests that the null token the beginning of sequence is playing an important role in the transformer calculations, and in particular is directly assisting counting!
B.4 REVERSE
In RASP, Reverse is implemented using flip_ sindsssseeecttnniics length-1 1-ighhh---ddisess lambda i i,j: i==j) followed by reverse=aggregse pegatefflp.s (flip_s, tokens). This takes two layers of one head each (recall that length itself requires one layer to compute).
10
0.5
06
The attention distributions in the 2-layer, 1-head (per layer) transformer trained on Reverse. The first layer is on the left and the second the right. The input sequence abcdeabcde presented on the y-axis as the queries and on the x-axis as the keys, i.e., each row is a distribution over the input positions. The attention distribution in the second layer is exactly as predicted by our RASP program (i.e., hard, reverse-match attention). In the first layer however, it seems the transformer has learned behavior other than uniform attention compute the length of the sequence (which needs for the second layer).
Figure 12:
We train two transformers on Reverse: one with 2 layers and 1 head, and the other with layer and 2 heads, to verify that the separation into 2 layers is indeed necessary. To give room for the index-based selection pattern (i.e., scoring method that involves comparison of indices and not just tokens), give the transformers per-head width at least as large as our maximum length. particular, we use embedding dimension 100 for the 2-layer transformer and 200 for the 1-layer transformer!! We also give them each feed-forve forward dimension twice their embedding dimension.
The 2-layer transformer reaches test accuracy 99.6% after 20 epochs. In contrast, and expected, the single-layer transformer remains trapped at 39.6% test accuracy even after 50 epochs. Plotting the attention for the 2-layer transformer (Figure 12 matches some of the predictions of our RASP program: the reverse-matching attention is only computed in the 2nd layer, and computed perfectly at that point. We are inclined to believe the length is being computed at the first layer (as we predict).
Intuitively. this allows the query and key vectors to encode their positions/target sources one-hot vectors, matching each other perfectly when computing the attention scores. We leave a full exploration of the relation hetween embedding dimension and selector complexity later work.
17

---

Under review as a conference paper at ICLR 2021
Figure 13: The attention distributions in the I-layer, 1-head transformer trained Reverse with fixed imput length 50, on input sequences of length 45, 50, and 53, in order. The y-axes represent output locations (queries) and the x-axes input locations (keys), i.c., each is distribution over the input positions. As expected, the transformer has learned a constant relation between pairs of input locations, and maintains all of the pairs it find in each input sequence it gets. For missing pairs, such as (0, 49) through (4, 45) in the input of length 45 (left), it struggles to focus its attention.
But there are also devitions from our prediction: the attention pattern suggests that the transformer is computing the length using a different mechanism from the one that have suggested.
We now strengthen the claim that the initial layer of the Reverse transformer is computing the sequence length, by showing that when the sequence length is fixed, then single-layer (and single-head) transformer does succeed on Reverse. We fix the sequence length to 50 and train a 1-layer 1-head transformer on Reverse. This simpler task can be presented one layer and one head in RASP using the single selector flip50 FLip50_s=selese s=select (indices, 19-indices, lambda i,j:i==j), from which the
result computed reverse50-aggregatee (fl (flipse_s_..____ee tokens).
As expected, the transformer succeeds in its task, reaching 100% test accuracy in only 3 epochs. In Figure 13 we illustrate that it has indeed learned a constant (7, 49 i) location pairing, by visualising its attention on sequences slightly longer or shorter than it has been trained on.
For completeness, in Figure 14 we show also the attention patterns of the single-layer transformer trained on variable-length Reverse. In keeping with our predictions, it has not managed to learn the metthign attention pattern at all. This is because needs an additional layer to compute the length before it can create the correct attention pattern.
Figure 14: The attention distributions of the heads the 1-layer transformer trained on Reverse, as applied to the sequence abcdeabcde. As expected from the RASP program, the transformer is unable to learn the reverse-match attention on any head of its first layer.
C
NOTATIONS
Basic Notations For every n E N, denote [n] (1, n.......
18

---

Under review as a conference paper at ICLR 2021
Matrices For matrix X E R' we refer its i-th row X; R and for vector E R we refer to its i-th value as 0/ E R. We additionally refer to n as the length of X and abusively denote [X| n.
For X E Ruxd and b E Rd. we use the shorthand X - to describe the addition of to each of the rows of X, i.e.: (X b); X; + for every i E 'n]. For scalar a R. any operation &oa,0 E (+--, x, } is applied elementwise to all the values of X. Matrix multiplication between two matrices A, B is denoted simply AB, and the transpose of a matrix A is denoted A".
We occasionally treat input or output sequences .1,,... Fn E RR as matrices X E R whose rows the individual input vectors: X; xz. When may be arbitrary, we will say that X E (Rdy'.
Definition C.1. A linear transformation with input dimension d and output dimension is function LA,b (Re)) + (IR"" parameterised by a matrix A E Rædx and vector E Rm as follows: (x) = XA for every X E )" A and b are the weights of the transformation.
Definition C.2. The softmax function s R - R² is defined: for every d E N and a E R., eat s(r) E Id such that s(x); = Ejsige's 6'5 for every i E [d]. We also denote by S the row-wise softmax
function: for every n, d N and X E Raxd, S(X) TRaxd and S(X); =s(x, ((.)) for every E [n].
We denote by R(X) the elementwise application of the ReLU function, r : - max(0, x:), to X.
A function A - B is length preserving it satisfies [f())) = |,z| for any (IR))* (i.e., for any input sequence , Fn E A returns a sequence y . Un B). If there also exists a function A + B such that [(x); = g(x;) for any i S |ar], then f is elementwise, and we say that is an elementvise application of g. Note that linear transformations are elementwise.
Function Qualities
D TRANSFORMER-ENCODER
At the highest level, a transformer-encoder preserving function T: ) - (Ie))" composed of multiple layers of length-preserving functions é (RR4)* - (IR i.e. f = E, o l2... é, which we will describe in this section.
(henceforth, a transformer) is a parameterised length-
Generally speaking, transformer's layers are not elementwise, and indeed the transformer would not be interesting if they were. However, when we come to look their components, we see that this quality rests entirely only their use of attention 12
Attention Attention is a function devised to enable 'recollection' of previously processed data from history of arbitrary length (Bahdanau et al. 2015 Luong et al. 2015). Transformers use a variant called sealed dot dot-product attention to collect data from multiple locations in an input sequence.
Definition D.I. Scaled Dot-Product Attention is function a (IR")= + (IR")" parameterised by 3 linear transformations, lo, lg, ll (Rd4** (R"") y and defined for every X (R4y as follows:
(1 (1e(X)x(XX) )(((X)
a( (X) = S
vm
Note. The original definition of scaled dot-product attention allows lg, and ly to have different output dimensions In this case, the denominator is /mg.
For convenience, from here on we refer to scaled dot- dot-product attention simply as attention.
The attention computation can be broken into 3 stages. First, pairwise score is calculated for each pair of locations, showing how much the input location j should influence the output in location i:
this is the value St in the matrix S (x() Then, each input processed in-place (lv (X)) to create candidate outputs, and finally the candidate outputs are averaged for each output location i, according the softmaxed scores S(S), for that location. In this sense, attention can be seen
vm
request to gather into each output information from various locations, where lo and l work together to select information sources, and lv encodes the transferred information.
12 Unsurprisinggy given the title of the paper.
19

---

Under review as a conference paper at ICLR 2021
Transformer layers often gather information with multiple attention functions, referred to as attention heads, whose results are concatenated back into a single output at the end:
Definition D.2. Let d, H, m E N be such that d = m. A multi-headed attention function with input dimension and H heads is a function A : (Rd)* )* - (IR4)* parameterised by the weights of H scaled dot-pne dot-product attention functions a aи as follows: 13 for every X E (R*)).
A(X) a1
where denotes row-wise concatenation, i.e. for every E [[]]] A(X); is the concatenation of a1 (X); through az (X); The functions a,,..., an are referred to the heads of A.
In addition to attention, transformers use layer-norm and fee- feed-forward components, as follows: Definition D.3. A single-row layer-norm over dimension d is a function IRd - Rd parameterised by vectors a, b E TRd and constant RR and defined for every x E Red and as follows:
az( ②)
g(x); std(x)) +
+ b,
where ā Egcia is the mean of x and std(x)) = V V Ligales 2
8)2 is its standard deviation.
d
A layer-norm over dimension d, ( + ( is an elementwise application of a single-row layer-norm of dimension d.
The layer-norm's 's function is more a reguliser, and indeed, it will not play a part in our abstraction. Definition D.4. A forwar function with input dimension d and internal dimension is an
elementwise function F (R + ( obtained by composing two linear transformations
L1 : (R=) )Rm))" L2 : (Rm > (Rd)" and ReLU, as follows: F(X) & L=(R(L1(X)))
The feed-forward component is elementwise, and the combination of two linear transformations with nonlinear activation provides strong expressive capacity (Hornik et al. 1989).
Layer). A transformer-encoder layer with input dimension d, internal dimension m, and H heads (such that d/H E N), is a mength-preserving function É: (IRd)* (R composed of one multi-heades attention A with input dimension d and H heads, one feed forward function F with input dimension d and internal dimension m, two layer-norm functions n1, n2 over d, and one linear transformation LA (IR))* > (R"),, as follows: for every X E )RR)),
Definition D.5 (Transformer-Fnncee)
X1 X + (X(m ((X) X1 + F(n2(Xi))
(1)
We refer to the additions in both equations as a 'skip connection'. Note that the layernorm, feed- forward, and skip connection components of the layer are elementwise: were it not for the attention, the entire layer would be elementwise.
Finally, we present the full encoder architecture:
Definition D.6 (Tranfformer-nnoou
Vaswani et al. (2017)) ). transformer-encooer with L layers, H heads, and input and internal dimensions d, m is a length-preserving function 'T (IRd)" -> (R parameterised by the weights of L transformeer-ncoder layers f1, LL, each with H heads and impul and internal dimensions d, m, and defined every X E (Rd)* as follows:
T(X) = (x(,,.(((((())
An interesting trait of the transformer architecture is that it has no inherent positional awareness. Specifically: for any transformer T =(Rd)* + (Rd)*, input sequence , F2, ..., In E Rdd and permutation n, have T(=(x)) T (T)()) 15
Permutation Invariance of Transformers
'oSome definitions of multi- headed attention may present it with additional '+X" in the computation (representing a 'skip connection' present the transformer), final linear transformation applied to the result. For reasons that will be clarified later, we prefer to set the boundaries of the definition only to the direct "mixing' operation shown, and instead write the skip connection and further lincar transformation explicitly when presenting the transformer.
Durinn training, a dropout layer also applied after the ReLU operation, hut this not present in inference. As all components of transformers other than attention elementwise, need only consider attention in order be convinced of this. We see quickly that each output location attention function only of
20

---

Under review as a conference paper at ICLR 2021
Discrete Input
Transformers T (R")** + (R*)* are used to process non-empty sequences finite alphabet Σ by composing them with a simple length-preser preserving function, Yo E* + (R Too (x:) _ (vo(()) This yo is in turn composed from a token embedding w E + R2 and position embedding p= N + R", which are normally combined using addition: for every x = 2i...n E Σ", yo(2), F2, .... Fn); wxxx)) + p(i)16.
From here, whenever we refer to a 'transformer over (some finite alphahet) E", we mean a transformer paired with initial emhedding yo described above.
E ADDITIONAL. DETAILS ABOUT RASP
A note about types in RASP Technically, there is no one 'tokens', rather 5 options: tokens_s __tr,, tokens_int, tokens_floo and tokens_book sooolllslllooooo cast the input sequence to the corresponding atomic types, and lokens_asis takes the input sequence as-is. For brevity, we refer to all of these as tokens here.
RASP Sequences RASP operates exclusively on sequence- and selector gereeratiggn functions, which we refer to as sequences and selectors respectively and RASP-function together. All R RASP-function take as input exactly one non-empty sequence, and when describing them and how RASP manipulates them to create and their manipulations generate from each input sequence. When is clear from context, we will simply refer to them sequences and selectors, and describe them directly in terms of their outputs. For example, if we say that a RASP operation applies +1 elementwise to each value a sequence u, we actually mean that it returns new sequence such that for every input and position 0 S | v (v)) [i]++.
-ASP-functions
will do in terms of the sequences and selectors that they
Note In this section we will refer to the i-th value in a sequence s[i], such that s[i] is in of the atomic types. We stress however that this is only for the discussion, and not a part of the language.
Additional operations For brevity in code, the RASP also comes with the following syntactic sugar:
Anywhere that tuple of sequences is passed into operation, single sequence may be passed in as-is as well. For example, y=zipmap ((indicess , (indices, >). lambda a, bbab)) can also be written y=zipmappindices, indices, lambda a,b:a+b).
The zipmap operation is accessible through large range of operators, covering its applica- tion to all of the base binary and unary operations on the atomic types. For example, the above y can equivalently be defined as y=indicest/ cestidices........... These operators can also be mixed with constants from the atomic primitives, such that an equal be obtained using y=2*indices
aggregate may receive a tuple of sequences xx instead of a single sequence x. In this case, it returns new tuple (of the same length) of sequences, the result of applying aggregate to each of the sequences in xx. For example, the line a,b = aggregate(s, (x,,) is (ggregate(s,y))
equivalent a, aggregate(s,x),
The processing function passed to zipmap may return more than one value (provided the number of values it returns is constant). In this case, the operation will arrange the output values into the same number of output sequences. For example, y1, y1,y2zzipmap (x, lambda v:v+1, v+2) is equivalent to writing y y1=++1 and then y2=x+2.
Anywhere that a processing function is expected, if one not provided, the identity function is !?
Ix (X), (X), and (X),, where the order of the rows of (ı (X) and (x) does not matter as long as they remain aligned.
16 Note that without the position emhedding, Yo would be elementwise, and its combination with T would he permutation invariant an undesirable trait for sequence processing.
Thhis is consistent with aggregate allowing you to choose whether to pass single sequence, tuple of sequences and processing function.
21

---

Under review as a conference paper at ICLR 2021
The function select1 which takes only single tuple of sequences and an index- computing function fi. and is syntactic sugar for select (xx, (indices,) ), lambda =aafiia(=-11===aa--D)
select is guaranteed to return true select satisfying the "up-to-one" property, i.e., that can be successfully paired in aggregates with an x that does not contain numbers.
22


Reviews:
[{"review_id": "nun4TbwCQxr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nHowever, 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. \n\nFor 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?\n\nSimilarly, 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.\n\nBecause 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.\n\nMinor details:\npg 1: “that is requires” -> “that is required”", "extra_scores": {}, "extra_text": {}}, {"review_id": "nXDj_IJqITL", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI 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.\n\nThe 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.\n\nI 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?\n\nIf 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?\n\nMiscellaneous comments:\n- 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.\n- 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)?\n- I think the inclusion of non-float types merits more discussion. For example, is it important that there is a boolean type?\n- 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?\n- The impossibility result for sorting should discuss non-comparison-based sorting algorithms (e.g. radix sort) or else qualify the claim.\n- The RASP analysis of the sandwich transformer results (S4.2) does not seem particularly illuminating.\n- There is essentially no discussion of related work.\n\nMinor:\n- the second sentence of the intro repeats \"language\"\n- in 'The Base Sequences' paragraph, there is a double comma and a dangling close-paren\n- the `sort` code uses `seq` instead of `vals` in the last line\n- in explanation of `select`, `f` is referred to as a \"selection function\" even though it has a different type\n- top of page 4: attention distribution <MISSING PERIOD> Hence\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_EEVUfUO4s", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nReasons to accept the paper:\n1. The paper provides a novel way of understanding how transformer model works from a programming language perspective.\n2. The paper presents solutions in RASP language for simple tasks such as histograms and sorting, and also complicated logic inference task.\n3. 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.\n\nReasons to reject the paper:\n1. 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.\n2. 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.\n3. 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CrGxcfjTUWE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, 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. \n\nSome things I would have expected an analysis on:\n* How well do the individual RASP operations map to the relevant transformer operations?\n* Why are the examples in 2.1 important/useful? Where are they needed?\n* 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?\n*   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?\n* 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)\n\n\n\n##### Typos\n* Fig1, Line 8: should the second arg be `vals`?\n* Sec2: \"the base sequences\": unbalanced parenthesis\n* In the discussion of `aggregate` a selector `s` is an input, but `s` is never used. Should `s` be `f` instead ?\n* 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?\n* Footnote 1 says uses variable `n`. What is `n`? Should it be `max(k,l)`?\n* Fig3 the semantics of the operation in L2 have not been defined, similarly for Fig2 L7.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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