Guiding Transformers to Process in Steps
Authors: Simas Sakenis
Stuart Shieber
Venue: ICLR 2022 Submitted (2022)

Abstract: Neural networks have matched or surpassed human abilities in many tasks that humans solve quickly and unconsciously, i.e., via Kahneman's “System 1”, but have not been as successful when applied to “System 2” tasks that involve conscious multi-step reasoning. In this work, we argue that the kind of training that works for System 1 tasks is not sufficient for System 2 tasks, propose an alternative, and empirically demonstrate its effectiveness. Specifically, while learning a direct mapping from inputs to outputs is feasible for System 1 tasks, we argue that algorithmic System 2 tasks can only be solved by learning a mapping from inputs to outputs through a series of intermediate steps. We first show that by using enough intermediate steps a 1-layer 1-head Transformer can in principle compute any finite function, proving the generality of the approach. We then show empirically that a 1-layer 1-head Transformer cannot learn to compute the sum of binary numbers directly from the inputs, but is able to compute the sum when trained to first generate a series of intermediate results. This demonstrates, at a small scale, how a fixed-size neural network can lack the expressivity to encode the direct input-output mapping for an algorithmic task and yet be fully capable of computing the outputs through intermediate steps. Finally, we show that a Frozen Pretrained Transformer is able to learn binary addition when trained to compute the carry bits before the sum, while it fails to learn the task without using intermediates. These results indicate that explicitly guiding the neural networks through the intermediate computations can be an effective approach for tackling algorithmic tasks.

Under review as a conference paper at ICLR 2022
GUIDING TRANSFORMERS TO PROCESS IN STEPS
Anonymous authors
Paper under double-blind review
ABSTRACT
Neural networks have matched surpassed human abilities in many tasks that humans solve quickly and unconsciously, i.e., via Kahneman's "System 1", but have not been successful when applied to "System 2" tasks that involve con- seious multi-step reasoning. In this work, we argue that the kind of training that works for System tasks not sufficient for System 2 tasks, propose an alterna- tive, and empirically demonstrate its effectiveness. Specifically, while learning a direct mapping from inputs to outputs is feasible for System 1 tasks, we argue that algorithmic System 2 tasks can only be solved by learning mapping from in- puts to outputs through series intermediate steps. We first show that by using enough intermediate steps a 1-layer 1-head Transformer can in principle compute any finite function, proving the generality of the approach. We then show em- pirically that 1-layer 1-head Transformer cannot learn to compute the sum of binary numbers directly from the inputs, but able to compute the sum when trained first generate series of intermediate results. This demonstrates, at small scale, how fixed-size neural network can lack the expressivity to encode the direct input-output mapping for an algorithmic task and yet be fully capa- ble of computing the outputs through intermediate steps. Finally, we show that Frozen Pretrained Transformer able to learn binary addition when trained compute the carry bits before the sum, while it fails to learn the task without using intermediates. These results indicate that explicitly guiding the neural networks through the intermediate computations can be an effective approach for tackling algorithmic tasks.
INTRODUCTION
Daniel Kahneman has pointed out that there is a fundamental difference in how humans solve the following two tasks (Kahneman 201I):
(1) complete the phrase "bread and ...." ";
(2) complete the equation "17 x 24 =... ...."
The answer to (1) comes mind instantly, with no mental effort, and is result of computation that one is not consciously aware of and could not explain. The answer to (2) requires time and effort to come up with, and result of sequence computations that one consciously carries out. The former mode of cognition is what Kahneman calls System I, the latter System 2.
We currently have separate tools for solving each of these two kinds of problems on computer, but it is not yet clear how to build single system capable of both modes of cognition simultaneously. Many tasks that exercise System 2 in humans involve executing some fully-specified algorithm and thus are quite straightforward to solve using conventional computer programs. However, classical programming is not applicable to System tasks as these typically correspond to functions that we do not know how to implement. Instead, System I tasks are usually tackled by approximating the target functions from observed input-output pairs. Whether such a learning- based approach could be successfully extended to System 2 tasks is an open question, and one that aim to explore in this paper.
We argue that the classical System 1 paradigm of training neural networks approximate functions from inputs and outputs corresponding to a given task not a scalable approach for tackling tasks from the System domain. We claim that, given only inputs and outputs, neural networks will

---

Under review as a conference paper at ICLR 2022
not receive enough supervision to converge solution when trained to perform algorithmic tasks that humans solve via System 2. To circumvent this, we propose to supplement the training data with intermediate results that would be helpful to compute before arriving at the final output. By modifying the training data in this way, we are effectively changing the training objective - instead of having learn any arbitrary way of mapping inputs outputs, the neural networks are now trained to compute the outputs from the inputs through a particular sequence of intermediate steps. We hypothesize that such additional guidance might be necessary in order for neural networks to learn algorithmic tasks, and we empirically evaluate this hypothesis.
Much of existing work in applying neural networks for System 2 tasks has been focused on making neural architectures more aligned with the execution of algorithms. While fine-tuning the model architectures may ultimately lead to superior System capabilities (after all, the architecture of calculator allows it to perform arithmetic at super-human level), we instead explore the challenge of extending the capabilities of existing state-of-the-art System models namely, the Trans- former towards the System 2 domain. In particular, we take inspiration from the human ability to solve algorithmic tasks by writing down symbols on paper and propose to formulate such tasks sequence- to-sequence problems where the target sequence includes both the outputs and all the intermediate symbols that a human would write (or more). That is, instead of modifying the models, experiment with modifying the data. Our main contributions can be summarized follows:
We show that it is possible hand-code 1-layer 1-head Transformer to compute any finite function if enough intermediate steps are used;
We show that a 1-layer 1-head Transformer can be trained to perform binary addition the target sequences include intermediate results, whereas it fails to learn the task when predicting the outputs directly from the inputs; and
We show that a Frozen Pretrained Transformer can be trained to perform binary addition if the target sequences include intermediate results, whereas it fails to learn the task when predicting the outputs directly from the inputs.
2 RELATED WORK
The need of bridging the gap between System 1 and System 2 capabilities in current deep learning
models has recently been emphasized by Yoshua Bengio (Bengio 2019; Bengio et al.) (021). The
work of Bengio and colleagues addresses the higher-level cognition in its broadest sense, seeking to
model and incorporate into current systems concepts such as consciousness (Bengio) 201 7), causal-
ity (Bengio et al. 2020), agency (Thomas et al.) (2018), and global workspace (Goyal et al. (021) l). In
Goyal & Bengio 2020), they question the paradigm of classical statistical learning and propose to shift from training models on curated datasets towards training agents in complex non-stationary en- vironments. In contrast to that, our approach lies within a conventional learning framework (namely, setuuecce-t-sequeene modeling with Transformers). and addresses System 2 in slightly narrower sense (namely, as algorithmic execution).
A considerable fraction of recent work in applying neural networks for algorithmic tasks has been concerned with modifying or augmenting neural architectures to make them more suitable for algo- rithmic execution. One very common approach involves trying to bring components from classical computer architecture into the neural setting: Neural Turing Machines give neural networks access dynamic external memory (Graves al. 2014, 2016), Stack-augmented RNNs augment the net- works with an infinite pushdown stack (Joulin & Mikolov] 2015), Neural Random Access Machines use registers and introduce the ability to manipulate and dereference pointers (Kurach et al., 2016). while Neural Arithmetic Logic Modules represent neural versions of the ALU (Trask et al. 2018
Madsen & Johansen 2020). parallel but closely related line of research frames these new kinds of augmented architectures neural controllers endowed with access to external interfaces and applies reinforcement learning techniques to train them to solve algorithmic tasks by interacting with the interfaces (Zaremba & Sutskever 2015 Zaremba et al. 2016).
The approach of using variable amount of computation per input, known as Adaptive Computation Time (ACT), has been introduced by (016). Universal Transformers (Dehghani et al. 2019) integrate ACT into the Transformer architecture, allowing each output symbol to be a result of a variable number of applications of single Transformer layer. While these works are, like ours,
2

---

Under review as a conference paper at ICLR 2022
motivated by the apparent necessity of intermediate processing in certain tasks, they use learned ponder time and learned ponder content whereas our work uses given ponder time and given ponder content. The main advantage of learned ponder time and content is that the model is free to discover and learn to perform the intermediate computations that it finds most useful. This also means that the researcher does not need to know the correct intermediate steps train the model and can thus tackle a potentially larger class of problems. The main disadvantage of learned ponder time and content that the amount of supervision per forward pass decreases as the model uses more intermediate steps, and the signal can quickly become too weak for the model to train at all. It is also worth noting that intermediate steps are typically given when humans are taught to perform algorithmic tasks (rather than being asked to infer intermediate computations by just looking at input-output pairs), which might be an important argument for given ponder content.
The idea of providing supervision beyond input-output examples has already appeared in several projects, although, in our view, it still remains largely underexplored, |Reed & de Freitas (2016) train Neural Programmer- Interrrrerrrrrrrrrrrs by providing supervision traces) of the recurrent controller, Mirman et al. (2018) train differential Neural Computational Machines with extra supervision on the movements of the read-write heads, and Mirman et al. (2018) train Neural Execution Engines with extra supervision on the attention masks. While the added training signal does lead to better sample efficiency and improved generalization, a major limitation of all of these approaches, as acknowledged by Mirman et al. (2018), is that the extra supervision needs to be highly specialized as applies to very specific components of each architecture. Our approach of supplementing the target sequences with intermediate results is completely architecture- independent and thus does not share this limitation. Veličković et al. (2020) use extra supervision at the data level as well, though their work is focused specifically on tasks involving graph-stre structured inputs and is thus based on neural network architectures that are tailored for processing graphs. In contrast to that, we adopt general sequence-to-sequeee imitate a human executing an algorithm on a piece of paper. Our main goal is to explore how and whether powerful existing System 1 models could be used in the System 2 domain, rather than to find a neural architecture that would be most suitable for executing algorithms. We therefore use vanilla decoder-only Transformers in our experiments.
the correct action sequences (execution
modeling framework, with an intention to
3 MOTIVATION
The distinguishing characteristic of System tasks is that they can be solved instantly and uncon- sciously, in something akin to a single "forward pass" through human neural network. It thus seems plausible that all input-output mappings corresponding to System tasks are in principle computable via a single forward pass through sufficiently large artificial neural network. Recent success in deep learning shows that training bigger models on more data indeed makes it possible to solve more and more System tasks, and it is not unreasonable to expect this trend to continue.
When it comes to solving System 2 tasks, however, scaling up appears to be dead-end. Consider the problem of completing the sentence "The first digit of the n- Fibonacci number is ... where is replaced by some positive integer. Since single forward pass through neural network (no matter how large) involves a constant amount of computation, there will be some number N E N such that for all n > N the correct output is not computable. follows that the only viable approach for solving these kinds of algorithmic tasks is to arrive at the output through intermediate steps.
The main value of introducing intermediate steps is that it gives control over the level of model expressivity required to implement a solution to a particular task. No matter how many atomic operations separate the outputs from the inputs a given algorithmic problem, performing those exact operations in sequence would make each execution step only as complex as a single atomic operation. This is arguably the main reason why a human brain can "implement" something like integer multiplication even though it does not contain a circuit for multiplying arbitrarily large num- bers directly- - the key is that a complex problem can be decomposed into simpler ones until each sub-problem becomes solvable "atomically" via System 1. By the same token, a neural network that is not expressive enough to compute some output through 0 intermediate steps may be expressive enough to compute the same output through intermediate steps for some I > 0, since each of the I steps would involve computing a simpler function. Since many System? 2 tasks are algorithmic, their outputs can be made arbitrarily distant from the inputs (in terms of the number of atomic operations
3

---

Under review as a conference paper at ICLR 2022
separating the two), which implies that step-by-step processing is the only scalable approach for solving them.
The necessity of intermediate processing does not by itself imply the amount of guidance that the neural networks should receive during training. The exact intermediate computations can either remain unspecified and be inferred by the model, or be fixed and provided part of the training data. Although there are pros and cons to both alternatives (as we have outlined in section 2), see the latter as more promising and choose to include the intermediate results in the target sequences used during training. Our position is based on the following three observations: first, natural provide complete supervision over the intermediate computations when teaching humans to perform algorithmic tasks; second, learned intermediates create the vanishing supervision problem (the longer the ponder time, the less training signal is received per forward pass); and third, for all algorithmic tasks the exact intermediate results are fully known anyway. While manually increasing the amount of supervision goes against the tradition of minimizing the reliance on expert knowledge that arguably lead to most of the recent achievements in the System domain, System 2 tasks represent a structurally different class of problems for which a different set of constraints may apply.
The arguments laid out above have the following important implications:
neural network implementing only some very basic atomic operations should principle be capable of expressing arbitrarily complex functions as long as enough intermediate steps are used;
Expressiveness:
Training: a neural network that fails learn some algorithmic task when trained without intermediate processing may be able to learn the same task if enough intermediate steps are used; and
Composability: neural network that is pretrained some general-purposs task and does not contain a circuit implementing some algorithmic computation directly may nevertheless be able solve the same task by computing the output through simpler operations which it does contain circuits for.
We establish the first of these implications in Section 4 and we empirically validate the latter two in Sections an ( Even though demonstrating a single example where a statement holds does not prove it in general, our empirical results confirm that the hypothesized phenomena do occur in the particular contexts we considered in this work and thus serve as evidence in favor of the latter two implications.
4 EXPRESSIVENESS
Human beings are able to solve algorithmic problems, such as integer multiplication, by writing down sequences of symbols, usually with outputs the end, where each new symbol is result of some basic operation applied to some of the symbols preceding it. Intuitively, it seems that the Transformer architecture should have just the right ingredients for emulating this kind of processing: it is typically used for generating sequences of symbols by iteratively predicting the next one, and its attention mechanism allows each predicted symbol be a function of selected preceding ones. We prove this intuition by demonstrating that it is possible to construct a 1-layer 1-head Transformer to compute any finite function through intermediate steps by emulating NOR circuits. The full details are included in Appendix A but the general argument goes as follows:
Since NOR is a universal gate, for every finite function f {0, 13" 10,1)"' there is Boolean circuit made up of NOR gates that computes f.
(2) By sorting the gates of such a NOR cireuit according their topological order, we can rep- resent the circuit as a sequence of binary symbols (si,..., sn+14m), where (S)..... s,) are the inputs, (8n (8n+141,
8m+/+m) are the outputs, and, for each > n, s; = NOR 88,, sk,)
with jo, kū < i.
(3) Given ($1...., s,), we can correctly complete the sequence with 1-layer 1-head decoder- only Transformer if its attention matrix A satisfies A,, 0.5 if 2 E {1 k2) and A₁, 0 otherwise (the model attends to the correct pair of symbols at each step) and the position- wise feed-forward module computes the NOR of the two symbols attended to.
4

---

Under review as a conference paper at ICLR 2022
(a) representation
(b) representation 2
Figure 1: Attention matrices from the hand-coded Transformer implementing binary addition with = 8.
present a concrete setting of of the weights of 1-layer 1-head decoder-only Transformer that makes (3) possible in Appendix A confirming the first implication from Section
While implementing NOR gates is sufficient for the proof due to the universality of the NOR gate, slight modification to the weights of the feed-forward module allows us to choose between NOR, AND, and XOR operations at each position in the output sequence. As a concrete example, we used this construction to implement addition of fixed-length bit strings (with guaranteed perfect accuracy), proving that addition, with the right number of intermediates, is in the space of programs computable by 1-layer 1-head Transformer. In particular, for each position along the inputs, letting ag and by denote the input bits and 6 denote the carry bit (obtained from the previous position, i.e. from the a:-1 + b,-1 1 Ci-1), compute
dj = (OR(a,, b.)
6, XOR (c,, d4)
ft AND a4 b.)
9: AND Ct d.)
c+1 XOR(ft, (ft.
where e; is the i-th bit of the sum and G+1 the carry bit for the next position (defining c 0)- We can thus represent the addition of, say, 3-bit numbers a a10203 and by b2b (in little-endian order, where on is the least significant bit) as the sequence
(representation 1)
a1 Sigazabbbbba bew.bbbbbbeceeeeeeee htw.://bbbbbddeeeeeeee/eoooeee/e
or, by reordering the symbols to put the sum at the end and intermediates between the inputs and the outputs,
(representation 2)
01a2ugbibzle
E1e233
impuls
intermediates
outputs
which is the representation that we actually use in our training experiments. Figure shows the attention matrices corresponding to both representations (row i of the attention matrix indicates which symbols attended to when predicting the i-th symbol from the output sequence). As be verified from the figure, the hand-coded Transformer does indeed implement the correct attention patterns corresponding to different representations of the Boolean circuit for binary addition.

---

with Under review as a conference paper at ICLR 2022
5 TRAINING
One of our core hypotheses in this work is that in many System 2 tasks the outputs will be too many atomic operations away from the inputs to be computable in single forward pass, regardless of how much the neural networks are scaled up, and that introducing intermediate computation is one way of solving the issue. If true, this phenomenon should manifest at small scale well: a shallow model may lack the expressivity to learn a direct mapping from inputs to outputs for a relatively simple task but be expressive enough to learn the mapping from inputs to outputs through intermediates, as decomposing the problem would reduce the minimum required complexity of single operation to the point where each individual step becomes computable single forward pass. We evaluate this hypothesis empirically by training a 1-layer 1-head decoder-only Transformer on the task of binary addition. (We use the minGPT implementation for our experiments (Karpathy) 2020).)
We chose to investigate binary addition primarily because of its simplicity. Conveniently, there are very clear candidates for what intermediate computations to use - e.g. we can supplement the training data with the carry bits (which are usually explicitly computed when a human is adding numbers on a piece of paper), or the values of all non-output gates in a Boolean circuit implementing binary addition (which is what we did in a previous section and do here as well). This means that, even if the task is decomposed into the most elementary operations (i.c., binary Boolean gates), each output symbol would be associated with at most 4 intermediate computations and so the gap between the inputs and outputs that is left for storing the intermediate results will not be disproportionately large.
We chose to investigate the 1-layer 1-head Transformer for three main reasons. First, we know from Section that this model is sufficient for emulating the Boolean circuit for binary addition and we know what the target attention patterns look like (Figure IT.. Second, using only single layer and a single attention head enhances the interpretability of the model as this makes possible to unambiguously determine its attention patterns (there is only a single attention matrix we need to look at). Finally, recall that the goal of our experiment is to test whether a model that is unable to learn task without the use of intermediate computations could learn the same task if intermediates were used. Thus, even though binary addition may well be a simple enough problem for a large transformer to solve without any intermediate steps at all, our aim here is to artificially restrict the expressivity of the transformer to a point where it is unable to learn the task without using intermediate steps so that could then add intermediate computations and test whether this makes the task learnable. As the results of this section demonstrate, reducing both the number of layers and the number of heads of the Transformer to 1 is sufficient achieve this.
We frame binary addition as a task of sequence completion - that is, the model receives a prefix of 2n symbols representing the two input numbers and has to predict the subsequent / + n symbols, where l is the number of intermediate symbols and the last n symbols represent the sum (ignoring the overflow bit). We train the model in 3 different regimes:
(1) Weak supervision: the model is trained to predict the sum immediately after the inputs, i.e., I= O. A single training example for n = 3 would have the form a1 d1dzagbi b2bse1 with loss computed on the model's predictions of eje2e3
(2) Medium supervision: the model is trained to predict the sum after I = 4n++1 intermediates, with loss computed only on the sum and not the intermediates. A single training example (ezazbbbzyyddeee for n 3 would have the form a1 210203b b2byd d2dd haa.s//ggccaa2ccasseeeeeee loss computed on the model's predictions of 610203-
(3) Strong supervision: the model is trained to predict both the sum and the 1 = 4n + 1 intermediates obtained by decomposing binary addition down to logic gates as ex- plained in section 3. A single training example for n = 3 would have the form a dlagazb b2byd fidd.f..ff.fae waw..//cccgeesssceeeeeeee with loss computed on the model's predictions of di doda fi I'2 (afacigieegppcageee
In all three regimes we use teacher-forcing during training, meaning that when predicting the i-th symbol of the sequence the model sees the correct target symbols at all positions up to i. During testing, the model receives only the two input numbers (e.g., 01 aagazbbbbby and is used to generate the completion (c.g., e e262 for weak supervision and r for medium and strong supervision) autoregressively using greedy sampling.

---

Under review as a conference paper at ICLR 2022
Table
Test set accuracy of a 1-layer 1-head Transformer on binary addition up n-bit numbers.
π 8
16
Tt = 24
12 = 32
40
= 48
weak supervision 1.0000
0.2529
0.1773
0.1961
0.0720
0.0000
medium supervision
0.0473
0.0003
0,0000
0.0000
0.0000
0,0000
strong supervision
1.0000
1.0000
1.0000
1.0000
0.8916
0.9873
We run experiments with E {8, 16, 24, 40, 48). For each n. perform grid search over 5 x 2 x x = 90 hyperparameter settings and run 4 randomly initialized trials for each of those. The hyperparameters
vary are the embedding dimension (chosen from {32, 64, 128, 256, 512)), the number of training examples (chosen from {1000, 10000)), the positional encodings (either fixed and defined via the sine and cosine functions as in the original Transformer (Vaswani et al. 2017), fixed and set to the hand-coded values as Appendix A or learned), and the training regime (weak, medium, or strong supervision). In Table we report the maximum accuracy achieved with weak, medium, and strong supervision over all hyperparameter settings and random trials for each n. We measure the exact-match accuracy against the target output bits representing the sum of the input numbers. The test set consists of 10000 examples not seen by the model during training.
The results in Table I show that, for 2 16, a L-layer 1-head Transformer is not able learn binary addition from weak or medium supervision while it can learn to solve the problem when strong supervision is used, supporting the second implication from Section This experiment thus serves as demonstration of a concrete problem for which the use of intermediate steps is the key factor determining whether neural network will be able to solve a task or not. This supports our main hypothesis that constant-size neural networks incapable of encoding the input-output mappings corresponding to algorithmic tasks may be capable of solving these same tasks by encoding the mappings from inputs to outputs through series of intermediate steps.
We also include a visualization of the attention patterns a Transformer trained with strong su- pervision in Figure 2 (specifically, random inputs), along with the target patterns taken from the hand-coded model. As indicated by the considerable resemblance between most of the corresponding Transformer does indeed learn to compute the intermediate results correctly and make use of them when predicting the outputs. This confirms that guiding Transformers through particular chains of intermediate computations can be instrumental in training them to perform algorithmic tasks.
plot the attention matrix averaged over 100 evaluations
from the two plots, the trained
Finally, for more context on the impact of hyperparameters on performance, Figures 4 the maximum test accuracies achieved with different positional encodings and sizes of the training dataset, respectively. We find that the best performance is achieved by using the sinusoidal positional encodings as used in the original Transformer (Vaswani et al. (017). and that the smaller dataset of 1000 examples sufficient achieve the best performance in most cases (the only exception being the strong supervision case with 40).
6 COMPOSABILITY
2021) have demonstrated that the weights of large pretrained Transformers encode general- purpose computations which can be leveraged to solve tasks from a diverse set of modalities. They show that it is possible to achieve competitive accuracies on a range of tasks by fine-tuning only the input layer, the output layer, and the layer-norm parameters of pretrained GPT-2 model while freezing all of the remaining weights in the "body" of the model (which comprise more than 99.9% of the parameters). This restricted version of the model is called Frozen Pretrained Transformer (FPT). While it is demonstrated that FPT is able to achieve perfect accuracy symbol manipulation tasks like bit memory or bitwise XOR, these tasks only involve elementary single-step computations and thus fall into the domain of System 1. The question are interested in is whether the weights of a pretrained language model contain circuits for solving non-trivial multi-step algorithmic tasks, and if not, whether solutions such tasks can be assembled by composing simpler circuits that
Lu al.
7

---

Under review as a conference paper at ICLR 2022
(a) hand-coded
learned
Figure 2: Attention matrices from the hand-coded vs. trained Transformer implementing binary addition with 8.
(a) weak supervision
(b) medium supervision
(c) strong supervision
Figure 3: Test set accuracy of a 1-layer 1 1-head Transformer on binary addition of up to r-bit numbers with different positional encodings.
1991
1912
02
(a) weak supervision
(b) medium supervision
(c) strong supervision
Figure 4: Test accuracy of a 1-layer 1-head Transformer binary addition of up n-bit numbers with different training set sizes.
8

---

Under review as a conference paper at ICLR 2022
Table 2: Test set accuracy of Frozen Pretrained Transformer on binary addition of up n-bit numbers.
71
8
T
16
=
n = 64
128 N
weak supervision 1.0000
0.0005
0.0000
0.0000
0.0000
medium supervision
0.0357
0.0000
0.0000
0.0000
0.0000
strong supervision 1.0000
1.0000
1.0000
1.0000
1.0000
contained within the weights. If the weights could encode direct input-output mapping, fine-tuning the FPT on example inputs and outputs would be sufficient for priming the model to perform the task. However, if the solution could only be composed out of pieces, we would expect FPT to learn the task only when fine-tuned to produce enough intermediate results before the output such that the individual computations expressible via the pretrained weights.
We investigate this by training a FPT on binary addition in the weak, medium, and strong supervision regimes analogous to those described in Section 5 though, in contrast to the previous experiments, we only use the carry bits as the intermediates (FPT is full-size multi-layer Transformer and thus may require fewer intermediate steps than 1-layer 1-head model). For instance, with 3, FPT would receive 01 (220zb b2b3 as input and have to predict 616263 in the weak supervision regime and C2C3C4e1 C263 in the strong supervision regime (using the same notation before). We train on 10000 examples for up to 100 epochs using teacher forcing and test on 10000 unseen examples without teacher forcing. We report the exact match accuracies (against the sum bits) over the test examples in Table 2 As we can see, FPT fails to learn binary addition in the weak and medium su- pervision regimes while it able solve the task when being trained to compute the carry bits first. This suggests that binary addition may not be directly implemented in the weights of pretrained language model but can nevertheless be expressed as a combination of more granular operations, supporting the third implication from Section 3 This result seems to be an analog of a similar fea- ture of the System learning capabilities of humans while it may not be possible to teach child to compute each digit of the sum in one unconscious step, the same child can easily learn to compute the correct outputs by explicitly calculating and keeping track of the carries. Once again, we see that guidance over intermediate computations is what neural network's 's ability to solve an algorithmic task appears to hinge on.
7 CONCLUSION
In this work, we have argued that the only way for fixed-size neural networks to solve algorithmic System tasks is by computing the outputs through intermediate steps. If neural networks going to be trained to perform such tasks from data, the actual intermediate results will either be given or have be inferred. We here focused on the regime with given intermediates, called strong super- vision. Our experiments demonstrated that 1-layer 1-head Transformer and Frozen Pretrained Transformer can learn to perform binary addition only strong supervision is used, supporting our hypothesis that guidance over intermediate computations can be necessary for solving algorithmic tasks.
We believe that strong supervision will be an integral part of any scalable attempt to use learning- based approach for tackling algorithmic tasks from the domain of System 2. We speculate that the usefulness of strong supervision might even extend beyond the space of algorithmic tasks, since any cognitive task that is characterized by distinct periods of thought leading to concrete intermediate results would become easier to learn if examples of those intermediate results were given during training. This leads us to believe that the idea of providing explicit guidance over intermediate computations might point to fruitful directions for future research.
REFERENCES
Yoshua Bengio. The consciousness prior. ArXiv, abs/1 709.08866..... 2017.

---

Under review as a conference paper at ICLR 2022
Yoshua
Bengio. From system
deep learning to system 2 deep learn- URL bttDs://alideslive com/ ctt.s//2330///22333.33333 38922304/
ing. NeurIPS, 2019.
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Nan Rosemary Ke, Sebastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher Pal. A meta-transfer objective for learning disentan-
gle causal mechanisms. International Conference on Learning Representations, 2020. URL. htttps://ppnrev// 2 F
net/ wwwumooruuiooormmoo
Yoshua Bengio, Yann Lecun, and Geoffrey Hinton. Deep learning for AI. Communications of the ACM, 64(7):58-66 65, June 2021. ISSN 0001-0782.
doi: 10.1145/3448200. URL https:
//oo..org/10.145/388838
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal
transformers. In International Conference on Learning Representations, 2019. URL https:
Anirudh Goyal and Yoshua Bengio. Inductive biases for deep learning of higher-level cognition. ArXiv, abs/2011.1509, 2020.
Anirudh Goyal, Aniket Didolkar, Alex Lamb, Kartikeya Badola, Nan Rosemary Kc, Nasim Ra- haman, Jonathan Binas, Charles Blundell, Michael C. Mozer, and Yoshua Bengio. Coordination among neural modules through shared global workspace. ArXiv, abs/2103.01197, 2021.
Alex Graves, Adaptive computation time for recurrent neural networks. ArXiv, 2016.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural Turing machines. ArXiv, abs/1410.5401, 2014.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gomez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John P. Agapiou, Adrià Puigdomènech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using a neural network with dynamic external memory. Nature, 538:471-476, 2016.
Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Proceedings of the 28th International Conference Neural Information Processing Systems Volume 1, NIPS' 15, pp. 190-198, Cambridge, MA, USA, 2015. MIT Press
Daniel Kahneman. Thinking, Fast and Slow. Farrar, Straus and Giroux, New York, 2011.
Andrej Karpathy, minGPT.
2020.
Karol Kurach, Marcin Andrychowicz, and llya Sutskever. Neural random access machines. ERCIM News, 2016, 2016.
Kevin Lu, Aditya Grover, P. Abbeel, and Igor Mordatch. Pretrained transformers as universal com- putation engines. ArXiv, abs/2 100.00273. 2021.
Andreas Madsen and Alexander Rosenberg Johansen. Neural arithmetic units. In International Conference on Learning Representations, 2020. URJ/itppsrr/ppeneeeeee...tt
id=HIgNOeHHKP
Matthew Mirman, Dimitar Dimitrov, Pavle Djordjevic, Timon Gehr, and Martin Vechev. Train- ing neural machines with trace-based supervision. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pp. -5777 PMLR, 10-15 Jul 2018. URL / d/proceedingg ingieeeddiig......
https:
wwwppess/vllll rman Ba.html
Scott E. Reed and Nando de Freitas. Neural programmeer-nneeppeeers.. CoRR, 0ttps/1511..022770 2016.
10

---

Under review as a conference paper at ICLR 2022
Valentin Thomas, Emmanuel Bengio, William Fedus, Jules Pondard. Philippe Beaudoin, H. Larochelle, Joelle Pineau, Doina Precup, and Yoshua Bengio. Disentangling the indepen- dently controllable factors of variation by interacting with the world. ArXiv, abs/1802.09484, 2018.
Andrew Trask, Felix Hill, Scott E Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arith- metic logic units. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gamnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018. URL /tt.htttsss///rrceeeee http://.......s.ss.././///r////p
newripe woc//paper/2118///5 pdd
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Proceedings of the 31st Inter- national Conference Neural Information Processing Systems, NIPS' 17, pp. 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execu- tion of graph algorithms. International Conference on Learning Representations, 2020. URL
htttss://ppeneet ew ww..tt.///e..ee.....e ftt//oormmpp d=5kkkk0
Wojciech Zaremba and Ilya Sutskever. Reinforcement learning neural Turing machines. ArXiv, abs/1505.00521, 2015.
Wojeiech Zaremba, Tomas Mikolov, Armand Joulin, and Rob Fergus. Learning simple algorithms from examples. In Proceedings of the 33rd International Conference International Conference on Machine Learning Volume 48, ICML' 16, pp. 421-429. JMLR.org, 2016.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A 1-layer 1-head decoder-only Transformer is parameterized function mapping sequences of sym- bols to next symbol probabilities, with parameters given by
( emb; W P
U (Mal, Pmnt, W Wquery. Oquery: Wkep Key Dkey, value: Dvalue U (7i22, P1n2, Wm, bm, Wiz,, Dmz)
U (Mis, Pma. W
Given imput sequence of b symbols (s1, 12, ..,....,8) 8b) from some vocabulary V, the Transformer
outputs b vectors h poob E [0, 1] for E (1,2,...,4 b} interpreted as conditional PMFs for next symbol prediction and computed via the following definitions:
h (1) emb
(Wemb) (ombb)..1.. + (Wpos)is
(1)
Inl LayerNorm, Shal
(A
(8) cmbb
(2)
(i) ( Wguery + -qquery
(3)
k(()) h Wkey bkey
0 (4) A W Wvatue + bvalue
K,, = 1.(1)
gT vd
a (4) Softmax
Maski.;
(3)
(8)
h (6) (i) (1)
rest an
ini
h (1) LayerNorm, na Sae A (8)
1n2
(10)
(4) ReLU (M W
bm
(11)
(4) ReLU (A ( b4zz)
(12)
7 rex2
(6) (8)
1/
(1)
(13)
1 LayerNorm, Saas
ress
(8)
(14)
(1 Woun)
Softmax
(15)
prob
where d is the embedding dimension, and Mask is autoregressive attention mask, i.e., a d x d matrix with all elements above the main diagonal equal to -oo and all of the remaining elements
equal to O. Predictions are made by interpreting the entries of h (i) that is,
prob as next-symbol probabilities,
Polsi+1 1;)= (1110h))
(16)
for each E (1, VJ}. where V, represents the j-th symbol from the vocabulary.
Let n and m be some positive integers and let (81, s2...., .,, Sn+m) a sequence of binary symbols where, for each i > n, setting of the weights of a 1-layer 1-head decoder-only Transformer such that, given (81, $2...., 8n), it autoregressively predicts (sn+1, 1 Sn+2,....
NOR(s), sk,) for some j., k; < i. We are going to show concrete
Sx+m) as the completion of the sequence. Specifically, given any e* > 0. we can hand-code the parameters 0 such that, for each i 2 n, Po(s+t1 NOR( (5 NO 8k; )) -""
12

---

Under review as a conference paper at ICLR 2022
Choose any c² > 0. Let b n + and define constants
be the block size, d = + b be the embedding dimension,
c1 2 In In (
(i - 2) ((i2))1122 1) )
C2 in (1~-²)
) 5 2d2
1
6 1-1-cc 2dd
2
Let the parameters of Transformer be hand-coded according to the following definitions:
if (j. E (2,)),, (1,3).
Wemb E 2xd with (Womb)ja
1
if (j. E (2, otherwise,
(17)
o
W pos E 12xd
with (Wpos)
if =+ otherwise,
(18)
0
Nal Rd with (Mai) =
(19)
Biat E Rd with (Stnt) = O,
(20)
(d/4)-1/2g
if E kj
W query E dxd with (Wquery)iit
(21)
10
otherwise,
Dquery E Rd with (bquerr)) =
(22)
1
if = k 3 otherwise,
Wkey E Rddd with (Wkey)iie
(23)
0
bkey E Rd with (hwey)s =0
(24)
(d/4)-11/2
if (f,)) E (2,
W E Raxd with (Wvalue)i. 10
(25)
otherwise,
bvalue E Rdd
with (bratue) = 0
(26)
Mnz E Rd with (7mn2) = -1,
(27)
Aia IRd with (3mz)) O.
(28)
(d/44)/2
if(i = (4,6) if (j, = (4,7) otherwise,
Wmn E Iadx
with (Wml).. =
(d/4)1/2
(29)
2de if =
E bet
1Rd with (bm)s =
1 - 4e
i =7 otherwise,
(30)
0
kj E {(,,6) (7,7)) (j.k) E (6. 8), (7,9)}
Wm E 1ddx
with (Wmz)j. =
(31)
otherwise,
bm E RRd
with
(bm2), = 0
(32)
Mn3 E Rd
with
(7na); = 1,
(33)
Bin Rd with
(Bma)) O,
(34)
8 (0-1
if otherwise.
(6,2))
out E dx2 with (Wout)j.e
(35)
0
Choose any i 2 n. After the token embedding and positional encoding layers, the hidden represen- tation corresponding to symbol i is given by
(
emb (eem))sst1, + (W i.
(36)
emb
13

---

Under review as a conference paper at ICLR 2022
Since
A
LayerNorm
hh cmb
(37)
Thi Sul
Membb
(4)
1 2==
11 (1)
Nembb)
(Man))
+ (Bmil)
(38)
1
(neal))
1
E
n1
(1)
2
k=
d
emb
lo
= =d/4)
(h
(bamb)
(39)
after layer normalization the hidden representation turned into
Minl (d/4) Pemb
(40)
Then, since the only nonzero elements of (n) are (Al)T the first three rows of Wkey are zero vectors, we get that the key corresponding to symbol j is given by
(n (M
and (1
and
3+
k = ((
(M
T
Whey + bkey) = (2/4)) (Weey)aeeeea (Wkoy)3tLx )3+.h
{ (d/4)3/2 if
(41)
0
otherwise.
kk
and the query corresponding to symbol ji is given by Ux = (1/11) T
c1 if (j++1, k+t1}
query
= =2d/4) query
(Weerry))))) querryaas..t J3+i,
t0 otherwise.
(42)
We thus have that the key matrix K (i.e., a matrix whose j-th row is the j-th key vector k(1) will be a x d matrix whose first b columns are equal to (d/4)1/2 times the identity matrix and all the remaining elements are O. Consequently, the attention weights that will be used for computing the hidden representation corresponding to the i-th symbol are given by
i
Softmax
(a())
Mask)
(43)
where
a00 (g0
fa/2
if kj. otherwise.
k
(44)
Vd
0
Then, since
(i - (1/2 -
(i - 2)(122
C1 2
In
ca12
(45)
2c
2c
(1 - 2(1/2 1/22 > (i-2) (2-2)(112-
(46)
ea12 > (1/2 - c)2c + (i (6-22) 2)(1/2
(47)
e/2
(1/2 c), 2e01/2 + (i - 2)
(48)
we have that, for 11441
e0 (9)
e0//2
0
> 1/2-6. -.
(49)
/2 1 (i - 2) 0
This shows that that the hidden representation corresponding to symbol i after the attention module can be made arbitrarily close to the average of the value vectors corresponding to symbols ji+1 and k
Since the first two elements of hamb sign(s;) and ss)) we get that the value vector corre- sponding to symbol j is given by
(i)
sign( s,) (s,)
if k 4
(1) 0k
(bija Weatue + bvalue)
if k 5 otherwise.
(50)
14

---

Under review as a conference paper at ICLR 2022
The hidden representation corresponding to symbol after the attention module is then given by
Nat
( =
10) jumn
((bi))) + +kkt (14
aktts
(0)
Σ
(51)
j=1
and we have that
8i41 = (Siq11 sk;11) = (0,0)
(52)
det 11 kit1 =
(53)
(hart) 4 E1-1, (1-)(1122)((-))) + (1))
(54)
8441 = 0 = (8) sk.4:) ) * (0,0)
(55)
wdtt E (0,1), 1i E (0,1)
(56)
(h =[(1- 1[11-220 (2) + (2c)
1],
(57)
that is,
( E 11,,-1 if 81+1
(58)
- 1]
if 8141 0,
with (h - (h,t)) 4. and ()) 0 for all j & (4,5}.
The hidden representation corresponding to symbol after the first residual connection is given by rost
(1) (8)
(59)
Since (Man)s - (hau)4 and all other entries of Ian are zero, and It emmh has mean of O, we have that
(6)
mean
| resl
mean
(1att + mean (emb))) = 0 + 0 = 0.
(60)
Also, since and can contain non-zero entries,
std
(h
D std ( (mmb)) = (d/4)
(61)
and since the entries of hest cannot exceed 122
std
(dd/4)1/2-0) -0)2)/20)222 =(4=41/4)212
(62)
rest
Then, since
In2
LayerNorm.
1922
11
(63)
we have that
(d/4) 1/2
rest S (11122 S (d/4)112
(64)
for all j E 21, ... d), which implies that
4e)] if 8
(1 E ((d/4)) (2
(65)
if if 0.
Since (d/4)1/2 > 1, it follows that
[|- (d/4) 4c)] if 8;41
E
1--2de, d]
if s1+1 0.
(66)
Using the definition of Wm and by and the fact that (d/4) > 1, we get that
h 22
Wm + bm
(d/44)//2
h (i)
[n2
2d
(67)
[ [1 4e - 2d e, df
if 8i+1
E
11 1 - 2022
if 8:+1 O.
(68)
15

---

Under review as a conference paper at ICLR 2022
and
(A Wm + =0m), (d/4))/2
(Min2) 1
+1
4E -4e
(69)
[1-dP, 0]
if 8(+1
(70)
[1 - 4E - 2,-t d + 1 - -ee]
if s141 = O.
Since c 542d <
44282 we have that 1 + 2122 > 0,, and thus
[ô, 2d
if 81+1 = 1 if if = 0
(mm)
ReLU (Mi2 Wm + dm
E
(71)
8
[0, 0]
and
( Wm + bms)) ), E (m ReI.U (nmn2
[0,00]
if s 1 if 8f O.
(72)
2d
Then, using the definition of Wmz and byz we get that
(12 6 = ReLU (MR Wnz + buz) = (M
[6, 2d
if s;+1 = if 8it1 = 0,
E
(73)
[0.0]
(1) ) (m
ReLU (hR) Wiz + bree) (
E
[6,
[0.0]
if = 1 if if 0,
(74)
while (1122 - (1122 6. (1102
(1)12 7 and
(112
0 for all j E (10, 11......0 d).
8
Since
1 (6)
res2
1112
(6)
(75)
we have that Also, since the entries of h 2ea2 cannot exceed d?
mean
res2
mean 11 mean
(1) = 0 + 0 = 0.
(76)
1 d
std
S
(d² 0)² = =tt
(77)
d
A=1
Then, since
1 = LayerNorm
(1 (ress))
(78)
ma ,us
we have that
(1) = std (M2002) (1002
(roce)
(8)
2 d
(1
(1)
(79)
j
for all j 2,,,,.... . dJ. It then follows that
8,+1 = -1 =
In2
> dd
and
[1 = 0,
(80)
8141 0 -
1in
0 and
14 dd
(81)
Let
1n3 W
(6)
(82)
Then, using the definition of Wout and the fact that = In 1_e'
2 In
1-c¹
we get that
8141 = 1 = 21 =
h1
(4) (8 (8-12e2)
= 0 and 22 = (1
(5- do)))
2 c2
(83)
In2
2² > E"
(84)
e² 2 + 2 > 1 - E"
(85)
e > 2 22" + 1 1 E²
(86)
2
e²
Po(si41 = 1) = (Softmax(=))
> 1 - E,
(87)
ea1 + e
2 +1
16

---

Under review as a conference paper at ICLR 2022
and
Si+1 =0 = 21 12
(8 dd- 2 C2 and 22 (M122 (f- 0
(88)
1 c
(89)
e E + 1 - E*
(90)
ed > e - +
(91)
e=
PolSi+1 = 1) (Softmax (z))2 e + e
> 1 c.
(92)
ea1 +
We conclude that, for each i2 P8(8:+1 NOR (O )) > - 6
17


Reviews:
[{"review_id": "l_KcOLaaoW", "reviewer": "Reviewer_4ZwD", "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": "I find both the motivating question ('how to get deep learning models to carry out processes associated with system 2?'), and the hypothesis ('by providing intermediate results as supervision') to be generally compelling. Humans are clearly provided with such supervision through the course of formal eduction (e.g. by being a given a demonstration for how to solve a multi-digit arithmetic problem), so this seems like a promising direction to pursue. In its current state however, the paper suffers from two significant limitations:\n\n1. All experiments are performed on the very simple and limited domain of binary addition. This seems like a good testbed for trying out some initial ideas and getting a handle on the problem, but it would be good to show that the method is also useful in richer domains, e.g. more complicated mathematical reasoning problems such as those in the dataset from [1] (notably, problems requiring a number of intermediate steps seemed to be particularly challenging for the models tested in that paper, so it is plausible to think that the presently proposed method might be more useful there). With experiments only performed on such a simple domain, it is very difficult to draw any general conclusions from these results.\n2. The paper's primary comparison is between a 'weak supervision' condition and a 'strong supervision' condition. There are two major differences between these conditions, and thus there is currently a confound concerning which of these differences is responsible for the differences in performance. The first major difference is that, in the 'weak supervision' condition, the model is expected to produce an answer in a single forward pass, whereas in the 'strong supervision' condition, the model produces intermediate results which are then fed back into the model as input. The second major difference is that, in the 'strong supervision' condition, the model is furthermore provided with supervision telling it what the intermediate results should be. An important control model is one that produces a final result via a series of intermediate results (as in the 'strong supervision' condition), but in which there is no supervision for what those intermediate results ought to be (as in the 'weak supervision' condition). The central proposal of the paper is that supervision is necessary to allow the learning of useful intermediate computations, but, without this control condition, it is impossible to know whether the 'strong supervision' model succeeds because of this supervision, or simply because it is allowed to compute intermediate results.\n\nOther issues:\n- Given the simplicity of the task, I wonder to what extent the pre-trained transformer is actually necessary for the results in section 6 ('composability'), as opposed to the fine-tuned input and output layers doing most of the work. A good control would be to test how the same model would perform when the 'body' of the model is just randomly initialized (and frozen), as opposed to being pre-trained.\n- Are all results presented for just a single model instance, or averaged over multiple model instances? Ideally, these results would be averaged over multiple model instances, with the number of model instances, and some measure of variance, reported.\n- The authors might consider citing, and discussing this paper [2], in which recurrent networks are used to generalize from simple to more complex computations via reuse of those simpler computations (notably though, this is *without* supervision on the intermediate results).\n- There is not adequate explanation of the notation used in the argument presented in section 4 (e.g. the indices *n* and *l* are not explained until section 5).\n- In the 'related work' section, 'Mirman et al. (2018)' is mentioned twice in the same sentence, in a manner that makes it sound like these should be referring to two separate papers. Is this a mistake?\n\n[1] Saxton, D., Grefenstette, E., Hill, F., & Kohli, P. (2019). Analysing mathematical reasoning abilities of neural models. arXiv preprint arXiv:1904.01557.\n\n[2] Schwarzschild, A., Borgnia, E., Gupta, A., Huang, F., Vishkin, U., Goldblum, M., & Goldstein, T. (2021). Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks. arXiv preprint arXiv:2106.04537.", "summary_of_the_paper": "This paper proposes that, in order to enable deep learning systems to carry out processes akin to 'system 2' (a term from cognitive psychology, referring to deliberate, step-by-step reasoning processes), these systems should be trained through supervised learning to perform complex computations via a series of simpler, intermediate computations (i.e. by providing the results of those intermediate computations as a source of supervision). Experiments are focused on the domain of binary addition, where it is shown that 1-layer transformers are capable of performing the task for very long bit strings when allowed to do so through a series of intermediate operations, but are limited to very short bit strings when forced to perform the task in a single forward pass. ", "summary_of_the_review": "The proposed approach is promising, but the experiments are only performed on a very simple, limited task domain, and an important control experiment is missing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "i6Or9ZG5zQ", "reviewer": "Reviewer_eRnm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Strengths\n=======\n* I found this work interesting and it is important that researchers explore the limits of what can be learned with current deep learning methods.\n* The text well-written.\n* The authors provide the code in the supplementary material.\n\nWeaknesses\n==========\n\n* In its current state, the work is too shallow for a conference paper. **Here are some additional questions** you could try to answer in your work to increase its depth / insightfulness:\n  1. Intermediate computations seem to help for binary addition, what about other computations? Is there any task where the model would fail even when having access to intermediate steps?\n  2. The study focuses on transformers but it is clearly applicable to other models such as LSTMs or DNCs. Why not trying with more architectures?\n  3. Experiments are done with shallow and pre-trained transformers but it also would be interesting to see what is required to make a transformer learn to perform algorithmic tasks from scratch (how many layers, attention heads, amount of data, amount of supervision) and to compare it with your current models.\n  4. It would be interesting to find an algorithmic task for which you can gradually choose the amount of intermediate guidance that you provide and see how much guidance do different kinds of models require.\n\n* The system 1 / system 2 motivation is interesting but maybe there is too much emphasis on it given that the work is more about transformers than human cognition.", "summary_of_the_paper": "The authors show that shallow and frozen pre-trained transformers can learn to perform algorithmic tasks if properly guided with intermediate computations. They experiment on binary bit addition, showing that including information about carry bits results in models that generalize significantly more than those trained with weaker supervision.", "summary_of_the_review": "The main idea of this submission is interesting but the contributions are not significant enough for ICLR. In \"Weaknesses\" I provide some additional questions that the authors could address to increase the amount of contribution / insights.  For the moment I recommend to reject this work but I strongly encourage the authors to continue working on it!", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Xrwblt-z6Nx", "reviewer": "Reviewer_KKJC", "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": "While I value the high-level goal of the paper and think it is important to explore and establish the necessity of sequential reasoning for system 2 tasks, I feel that in the current form of the paper it doesn’t explore it rigorously or extensively enough to corroborate its claims in a solid manner:\n* **Too narrow task**: The focus on very specific addition problems in a quite particular non-intuitive input-output format doesn’t support the generality of the claims about the necessity  of guiding models through intermediate supervision to make them capable of tackling algorithmic tasks. There could be a much richer variety of algorithmic tasks that fit the domain of the paper and that I would hope to see when I started to read it, that could be explored to make the claims better supported - graph traversal, sorting, reasoning over sequences, summing decimal numbers in different formats (e.g. input x+y+z.. and outputting the result), etc etc. It feels to me that the current focus narrows down the paper preventing it from substantiating such general claims.\n* **Extending experiments**: assuming focusing on the particular addition task in the paper, I think it could still benefit from a larger variety of experiments. Currently there are only a handful of experimental results, basically showing that strong-supervision makes 2 models (pre-trained and from scratch) achieve perfect 1.0 accuracy on the addition task, and fail otherwise. Further exploration into (1) the size of training data, (2) the amount of supervision (interpolation between just weak and strong), (3) the complexity of the addition task in different dimensions, and (4) the transformer configuration (number of parameters, heads, layers) impact performance would be useful to get more intuition on what are the reasons behind models’ failure or success in different settings. \n* **Choice of tested model**: The paper mainly focuses on 1-layer 1-head transformer, but doesn’t justify the choice of the model. It could be that even though theoretically such a model can represent any finite function, it’s too constrained for allowing it to figure out good solution for the task through training without intermediate supervision, but given that the chosen model is very small and limited to begin  that doesn’t necessarily prove that intermediate supervision is necessary for models. Indeed, naturally it is generally true that providing more supervision to tasks would make them simpler, but if a reasonable increase in model’s capacity (more layers, more heads) could allow avoiding that extra supervision, then why is it still necessary? I think it could be really interesting to show the necessity of intermediate supervision but I think that will be better demonstrated by finding a case where even if you add more layers, heads, or parameters to the model, it still fundamentally doesn’t manage to solve an algorithmic task, unless the intermediate supervision is given. I think tasks that have exponential nature in terms of the search space of potential solutions could be good candidates to show that since their space may quickly outgrow the capacity of a model, even if increased in size or complexity.\n* **Exploration of other classes of models**: I think for that paper in particular that focuses on sequential reasoning and the necessity of intermediate steps supervision, it would be very natural to also explore recurrent approaches (RNNs, LSTMs) and their performance and compare it to that of transformers.\n* **Discussion about systems 1 and 2**: The discussion about systems 1 and 2 feels a bit honestly hand-wavy and not precise enough -- given the extent to which these terms are used and discussed here, it would be good to start by some clear definitions in the context of the paper: how to you define system 1 tasks and systems 2 tasks here? Are all math problems considered system 2? Are “easy-enough” to remember math problems should be considered system 1? If a model is pre-trained on a task does it make it system 1 or 2 task (because if the model already is skilled in answering that particular sort of question one might argue it doesn’t require explicit sequential reasoning anymore turning it into system 2).\n* **Motivation section**: I feel that the motivation section in its current form is not compelling and doesn’t answer key questions about the choice of tasks and the design of the experiments discussed above. I think it may be better to work more on the presentation of the paper.\n", "summary_of_the_paper": "The paper’s main claim is that sequential reasoning is necessary for system 2 tasks, and exploring addition as an example for that, showing that a 1-layer 1-head transformer fails to compute the sum of numbers directly (although theoretically shown to be able to compute any finite function)  but does work when being supervised by intermediate results. Then they show that a pretrained transformer likewise fails withouts intermediate supervision on a binary addition task. \n\nUpdate: I do apreaciate the author's revision but since no response has been provided to my comments and/or was addressed by the revision, I unfortunately keep my score.", "summary_of_the_review": "To summarize my review, I think that while the high-level goal of the paper of exploring the necessity of intermediate supervision is interesting and important, the experimental evaluation is not rigorous enough to demonstrate it, missing along multiple key dimensions, which include: \n* Choosing a task that is too narrow\n* Very narrow exploration of models and experimental settings within the chosen task\n* Unjustified/unexplained choice of an unnaturally constrained model (1-layer 1-head transformer)\n* Lack of exploration of other relevant models (e.g. recurrent networks)\n\nFor these reasons I unfortunately recommend rejecting the paper in its current form, but do encourage the authors to extend and explore it further in order to improve it!", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "5oIPmaAKmLH", "reviewer": "Reviewer_urkD", "summary": "", "questions": "", "limitations": "", "rating": 3, "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\nThe paper presents the authors’ hypothesis: intermediate steps are necessary for Transformers to perform well on algorithmic tasks. They analyse Transformers on a simple binary addition task with and without intermediate steps. They show that only the one with immediate steps and supervision over these steps can generalise. In contrast to most of the prior work, the authors argue for supervision in the output domain. This makes the approach architecture-agnostic.\n\n# Strong points\n-   The topic is interesting and relevant\n-   The paper is clear and easy to understand\n-   The supervision is applied as additional outputs, which makes the approach architecture agnostic\n\n# Weaknesses\n-   The 2nd implication (Training) in section 3 is not generally true. There might be many reasons for the NN not learning a task, for which strong supervision cannot help. For example, one can just use a state size of 1 or set initial weights to zero.\n-   The Composability implication of section 3 is not generally true. Having atomic operations is just a necessary but not sufficient condition for building more complicated algorithms from them. Decomposing novel problems to the known atomic operations is a very hard, unsolved problem.\n-   The authors appear to mix two things: the availability of extra computation steps and the strong supervision of the intermediate outputs. Because of this, it is unclear whether their findings show that additional computation steps or additional supervision are needed. \n-   The authors claim in section 5 that their results in table 1 prove 2nd implication from Section 3. However, showing that it works in a particular case does not prove the general statement.\n-   The claim of section 3, that “no matter how many atomic operations separate outputs from inputs…” is true only if we ignore the additional complexity of decomposing the problem and combining the intermediate results, or if this has a fixed complexity, which may or may not be the case.\n-   The authors seem to define the intermediate steps purely in the output space. But in fact, intermediate results can be computed in different layers of the network, and even with extra output steps, this might be enough for solving the problem.\n\n# Questions/suggestions\n-   The weaknesses from above have to be fixed\n-   The experiments either have intermediate steps with supervision, or they don’t have intermediate steps at all. This makes it unclear whether the performance gain comes from the additional computation steps or additional supervision. A more proper way to evaluate this would be to add a third version, which has the same number of output steps as the current strong supervision variant, but with no supervision applied to the intermediate steps.\n-   For adaptive computation, please add citations to [1] and maybe [2]\n-   For Veličković’s work in the references, the authors only mention a work that is concerned about graph-structured problems. However, his recent work is more general focuses on diverse types of data. On the other hand, Transformers can also be understood as graph networks with a fully connected graph (which is also common in the GNN literature)\n-   There is a mistake in eq (7) in the appendix: as defined here, if the logits are negative, the attention score will become nan (inf/inf). The mask should be additive, and the “remaining elements” should be 0 instead of 1. Of course, there are other ways to achieve the same result, but the one described in the paper is incorrect and can result in trainability issues.\n\n# Other\nI have not verified the correctness of the hardcoded weights from the Appendix.\n\n# Citations\n[1] Jürgen Schmidhuber: Self-Delimiting Neural Networks (2012)   \n[2] Banino et al: PonderNet: Learning to Ponder (2021)", "summary_of_the_paper": "The paper presents the authors’ hypothesis: intermediate steps are necessary for Transformers to perform well on algorithmic tasks. They analyse Transformers on a simple binary addition task with and without intermediate steps. They show that only the one with immediate steps and supervision over these steps can generalise. In contrast to most of the prior work, the authors argue for supervision in the output domain. This makes the approach architecture-agnostic.", "summary_of_the_review": "As for the weaknesses, I have to recommend the rejection of the paper. There are flaws in multiple claims, and the authors seem to mix the availability of computation steps and supervision of them.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper offers new ideas about the key question of how to extend modern Transformer architectures to solve problems that require more reasoning steps than the model can implement in a single-step forward pass. Reviewers were unanimous that the problem is important, and that the paper is a step in a promising direction. However, reviewers were also unanimous that the proposed experiments are too narrow to be the basis for any confident new claims in this area and that, in addition, the experimental design has a confound that makes it difficult to interpret, even after the addition of a new condition during discussion.
Decision: Reject