Iterative Decoding for Compositional Generalization in Transformers
Authors: Luana Ruiz
Joshua Ainslie
Santiago Ontanon
Venue: ICLR 2022 Submitted (2022)
Keywords: compositional generalization
transformer
compositionality
deep learning
NLP

Abstract: Deep learning models do well at generalizing to in-distribution data but struggle to generalize compositionally, i.e., to combine a set of learned primitives to solve more complex tasks. In particular, in sequence-to-sequence (seq2seq) learning, transformers are often unable to predict even marginally longer examples than those seen during training. This paper introduces iterative decoding, an alternative to seq2seq learning that (i) improves transformer compositional generalization and (ii) evidences that, in general, seq2seq transformers do not learn iterations that are not unrolled. Inspired by the idea of compositionality---that complex tasks can be solved by composing basic primitives---training examples are broken down into a sequence of intermediate steps that the transformer then learns iteratively. At inference time, the intermediate outputs are fed back to the transformer as intermediate inputs until an end-of-iteration token is predicted. Through numerical experiments, we show that transfomers trained via iterative decoding outperform their seq2seq counterparts on the PCFG dataset, and solve the problem of calculating Cartesian products between vectors longer than those seen during training with 100% accuracy, a task at which seq2seq models have been shown to fail. We also illustrate a limitation of iterative decoding, specifically, that it can make sorting harder to learn on the CFQ dataset.

Under review as a conference paper at ICLR 2022
ITERATIVE DECODING FOR COMPOSITIONAL GENER- ALIZATION IN TRANSFORMERS
Anonymous authors Paper under double-blind review
ABSTRACT
Deep learning models do well at generalizing to in-distribution data but struggle to generalize compositionally, i.e., combine set of learned primitives to solve more complex tasks. In particular, in eequence-t--squeeee transformers are often unable predict correct outputs for even marginally longer examples than those seen during training. This paper introduces iterative decod- ing, an alternative to seq2seq learning that (i) improves transformer compositional generalization and (ii) evidences that, in general, seq2seq transformers do not learn iterations that are not unrolled. Inspired by the idea of compositionality that complex tasks can be solved by composing basic primitives training exam- ples are broken down into a sequence of intermediate steps that the transformer then learns iteratively. At inference time, the intermediate outputs are fed back the transformer as intermediate inputs until an end-of oof-iteration token is predicted. Through numerical experiments, we show that transfomers trained via iterative de- coding outperform their seq2seq counterparts on the PCFG dataset, and solve the problem of calculating Cartesian products between vectors longer than those seen during training with 100% accuracy, a task at which seq2seq models have been shown to fail. We also illustrate a limitation of iterative decoding, specifically, that it can make sorting harder to learn on the CFQ dataset.
(seq2seq) learning,
INTRODUCTION
Deep learning architectures achieve saate-of-the-art results in wide array of machine learning prob- lems, where their impressive performance is attributed to their ability to generalize (Goodfellow et al. 2016; LeCun et al., 2015). However, this ability is typically limited to generalization under the statistical learning paradigm, i.c., in-distribution generalization, and does not encompass gen- eralizing compositionally. Compositional generalization is the ability of model to combine a set of learned primitives to execute more complex tasks. For instance, for a ground robot whose mo- tion planner has learned to execute the instructions "walk", "jump". and "jump right", generalizing compositionally would be to be able to execute the instruction "walk right" (Lake & Baroni 2018).
In machine learning models, compositional generalization is desirable for two reasons. First, be- cause it is a crucial aspect of intelligence observed in both humans and classical artificial intelligence techniques. In humans, a prevailing example is the way children can solve complicated mathemati- cal expressions after being taught basic arithmetics. Second, because it can increase a model's data efficiency. By endowing models with the ability extrapolate unseen examples that are more complex, or complex in different ways than seen at training, compositionality acts as an implicit mechanism for data augmentation.
In this paper, our goal is to increase compositional generalization in transformers, with particular focus on natural language-like whhse compositionality key. Understanding that for models to be able to execute composite tasks they need to be taught how to compose, we introduce iterative decoding, an alternative to of mapping the inputs to the outputs of each example into a sequence of intermediate steps which the transformer learns to perform iteratively. During training, each input-output pair is converted into sequence of "intermediate input-intermediate output" pairs, which are task specific. During prediction, the intermediate outputs predicted by the transformer are adapted into the subsequent in- termediate inputs, which are fed back to the transformer until
(seq2seq) learning that decomposes the process
token is produced.

---

Under review as a conference paper at ICLR 2022
Our main contributions are (i) showing that iterative decoding, especially when combined with other architectural modifications such as relative attention (Shaw et al., 2018) and copy decoders (Ontañón al. 202T), largely improves compositional generalization in transformers, and (īi) evidencing that, in general, seq2seq transformers cannot learn iterations unless they are unrolled. We show this through numerical experiments
two compositionally hard splits of PCFG (Hupkes et al.] 2020), string editting dataset; and on a cartesian product dataset, where the goal is to generalize to longer input vectors than those on which the model is trained. We also present numerical results on CFQ (Keysers et al. 2019), semantic parsing dataset consisting of natural language questions paired with SPARQL queries. Importantly, the results obtained in this dataset evidence a limitation of iterative decoding, which is that it can be sensitive to the ordering of the intermediate steps.
The rest of this paper is organized as follows. Section 2 discusses related work on compositional generalization, transformers and on the PCFG, cartesian product, and CFQ datasets. Section introduces iterative decoding. Iterative decoding strategies specific each dataset and numerical results are presented and discussed in Section 4 Section 5 presents future research directions and concluding remarks.
BACKGROUND
In this section, we introduce some background and related work on compositional generalization, transformer architectures and on the PCFG, Cartesian product and CFQ datasets, used in our exper- iments.
2.1 COMPOSITIONAL GENERALIZATION
Compositional generalization (or compositionalitt) refers to the ability of a model that has learned to perform set of basic operations- operations--riimitvverr primitives--t generalize to more complex operations, i.c., operations consisting of compositions of the learned primitives (Lake & Baroni, 2018). Examples shown in Figure for three datasets. For instance, the top-left corner shows an example from the PCFG (Hupkes et al.] 2020) dataset. In some versions of this dataset, the model is trained to solve several atomic string editing operations (such copy and swap_ff wwf.stsslssss. it compose a longer number of operations than seen during training. Hence, the model has to be able to generalize compositionally. This string editing example can be seen an instance of productivity, one of the five types of compositional generalization identified by Hupkes et al. (2020) which involves generalizing to longer examples than those seen during training. Another type of systematicity, the ability to recombine known parts and rules in ways different than those seen during training.
of operations requiring compositionality
and how to compose them. During testing, the model is tested by asking
compositional generalization
Early works on compositionality have explored the limitations of different machine learning models in generalizing compositionally. Liska et al. (2018) showed that, while it is theoretically possible for a recurrent neural network (RNN) to generalize in this way, only a small fraction of the models they trained behaved compositionally. Lake & Baroni (2018) proposed SCAN, a dataset consisting of navigation commands to be mapped to action sequences, and observed that while RNNs trained on it only generalized well when the differences between the training and test sets where small, they failed when more systematic compositional skills were required. Other datasets created with the purpose of measuring compositionality include PCFG (Hupkes et al., 2020) and CFQ (Keysers) et al., 2019), where both soortshort term memory (LSTM) and cersstoomer--bssee architectures have been shown to perform poorly.
More recently, a popular research direction is to try to endow these machine learning models with "compositional generalization bias". Kim et al. (202T) saw benefits in converting CFQ into a classi- fication task and using structural annotations (e.g., entity links) as attention masks in transformers. Ontañón et al. (202I) were able to improve transformer compositional generalization on a variety of compositionally hard datasets by making architectural modifications such as relative attention, copy decoders, and weight sharing. Taking a similar approach, Csordás et al. (2021) observed per- formance improvements from relative position encodings and scaled embeddings. Other strategies to improve compositional generalization include increased pretraining (Furrer et al. 2020), data augmentation (Andreas 2019) and differentiable neurocomputers (Graves al. 2016).
2

---

Under review as a conference paper at ICLR 2022
PCFG
CFQ
IN: cepy first__ last E18 B11 T13 W20
IN: DId person marry a cinenatographer influence M2
oUT: w28 811 T13 E18
inf luence
SELECT count WIERE
?x0 a ns: pesppepppeepee son
Cartesian product
2x8 ns: influence. influence. nuence_nade. inf Iuenced N1 Luence, Luence, _ode luenced PxB ns: as:people. person. son. spouse ?x1
IN: [SE)]
?x1 nn: wrt.lln.cieemttgree. cinemategrapher
?x1
oUT: a aaid4a4da3
Figure 1: Examples of input-output pairs in the PCFG, cartesian product, and CFQ datasets.
Closely related to our work, PonderNet (Banino et al., 2021) trains a model that iterates internally achieve better compromise between training accuracy and generalization. It predicts both an output and a halting probability at each step, operating recurrently. Iterative decoding also operates recurrently, but two important differences are that (i) in iterative decoding the intermediate steps are supervised and interpretable, and (ii) rather than predicting a halting probability at each step, iterative decoding trains the model to produce a special token indicate end of iteration.
2.2 TRANSFORMER MODEL
In this paper focus on transformer models. Despite struggling generalize compositionally. transformer-bet based architectures such as BERT (Devlin et al., (2018) and T5 (Raffel et al. 2019) were
popularized by their remarkable performance machine translation (Zhu al.] [2000] question answering (Ainslie et al., 2020), summarization (Zhang et al. 2019) and other natural language processing (NIP) tasks.
Introduced by Vaswani et al. (007). the basic transformer model is composed of an encoder and decoder. The encoder is made up of layers consisting of a self-attention sublayer and a feedforward sublayer. The decoder has the same structure, but with additional attention sublayer to compute the decoder-to-encoder attention. The input to transformer a sequence of token embeddings. Since these embeddings do not carry information about the position of each token in the sequence, a position encoding is typically added to the input embeddings. These are then fed to the encoder, which encodes all tokens once and forwards the result the decoder. From the encoded input and the decoded output tokens generated so far, the decoder generates the distribution of the next output token, token time.
We experiment with two extensions to the original transformer architecture that were previously shown to improve compositional generalization (Ontañón et al., [021]: relative position encodings and copy decoding. To each pair of tokens in the input, relative position encodings assign a label that equal the minimum between their relative distance and fixed relative attention radius. An im- portant characteristic of relative position encodings is that they are position invariant, which means that two tokens that are positions apart will attend each other the same way regardless their absolute positions in the sequence. Copy decoding involves adding a learnable parameter that allows to switch between the decoder and a copy decoder which produces an independent embedding that can be interpreted "copy" from the input sequence.
2.3 DATASETS
We consider three datasets PCFG, cartesian product, and CFQ are discussed in detail in the following sections.
2.3.1 PCFG
PCFG is an artificial translation dataset proposed by Hupkes et al. (2020) and generated by proba- bilistic context free grammar. The input data consists of string editing instructions with four types of
3

---

Under review as a conference paper at ICLR 2022
seq2seq
iterative decoding
X
0 <is
transformer
transformer
end-af-iteration
n2
x, <<isN
Figure 2: Prediction routines for the seq2seq transformer (left) and iterative decoding transformer (right).
tokens: unary operation tokens (e.g., reverse), binary operation tokens (e.g., append), string separation token ", (to separate arguments of binary operations), and string elements (e.g., B10 D2). The output data consists of the strings resulting from the application the operations; see the top left corner of Tigure[oor example.
There are six training-test splits of the PCFG dataset. The first is a random split which we use as baseline. The other five compositionally hard splits used to measure the five different types compositional generalization. We focus on two them: productivity and systematicity. In the productivity split, the training samples have up to 8 string operations, while the test samples have or more. In the systematicity split, there is no restriction on the number of operations in either set, but the
they are combined in different ways than the training set.
The main challenge of the PCFG dataset is that it requires learning ten string editing operations, some of which are very similar. The unary operation echo, for instance, only differs from copy by repeating the last element of the string. While transformers generally achieve good performance in the random split of the PCFG dataset, the productivity and systematicity splits are harder because transformers tend to learn shortcuts (instead of learning the mechanics of each operation). In partic- ular, a key difficulty of the productivity split is that the model needs to learn to "recursion" and apply an arbitrary number of operations when input examples grow in length. In some cases, the strings to modify can also be very long, which places an additional capacity burden on transformers by requiring them learn how to copy strings.
2.3.2 CARTESIAN PRODUCT
In the cartesian product dataset, the inputs are two vectors and the outputs are their cartesian product. The first input vector is vector of numbers. The second is vector of letters, separated from the numbers by the special token [SEP]. Both numbers and letters are picked at random, without repetition, from the decimal digits and the first letters of the alphabet respectively. possible input-output pair is shown on the bottom left corner of Figure
We consider four splits of the cartesian product dataset. the first split, both the training and test set consists of samples with up to five numbers and letters drawn i.i.d and split at random. This is the "casy split". In the other splits, the training set the same in the first split, but the test set consists of examples with six numbers and five letters for the second split, five numbers and six letters for the third, and six numbers and letters for the fourth respectively. These are "hard splits",, which we use to measure productivity. The productivity splits of the cartesian product dataset are remarkably hard; even transformers with some compositional generalization ability other mathematical datasets have been seen to fail (Ontañón et al.) 2021). This is due to the fact that, in order to solve cartesian products, models need to learn to execute two nested loops. Moreover, the output is quadratic on the size of the inputs. For models that have to learn predict an end-of-sequents token, extrapolating to longer sequences than those seen during training has been shown be difficult (Newman et al. 2020).

---

Under review as a conference paper at ICLR 2022
Cartesian product (row)
PCFG
IN: 7 [SEP]
OUT:
IN: [SEP] a. [SEP2] DU1:
first, last repeat N7
rM: [SEP] [SEP2]
OUT: [END]
somp_first, lastt repest ve
Cartesian product (taken)
swap Marpttistt.mm last 34 AB NZ VS 34 AD N7 VB.
IM: [SEP]
IM: [SEP] [SEP2]
OUT:
V8 AD M7 VR 34 AR N7 34 [[ND]
IM: [SCP] [SCP2] 2
OUT:
IN: [SEP] [SEP2]
OUT:
[CNC]
CFQ
ZN: 01d a person narry a canerstographer
Inf Luence H1 inf Luence H1
OUT: SELECT count(") WHERE OUT: 7x0 ns:people Le. per son
ZM: Did a person narry a caneratographeer
[3EP2] SELECT count(" ()) WHERE
ZM: Oid a person narry a cinerstographer influence M1
OUT: 7x8 Luence Luence inf Luence_node inf luenced Ka
[SEP2] SELECT count(") WHERE Px8 a ns: peop le person
IN: oid a person [SEP2] SELECT caunt(") (*) WHERE 7x8 pooppp.pppp..ae 7x88 ns:influence. lunnel Lnenc node. luenced Ma 7xb ns peope person.spouse. Pxtt ?xt
cinesstographer influence M1
OUT: FILTER ( PxO 1= 7K1 [END]
ns :1:11 in. cinaratagrapher
Figure 3: Examples of intermediate input-output pairs in the PCFG and cartesian product datasets.
2.3.3 CFQ
Introduced by Keysers al. (2019), the CFQ dataset consists of natural language questions and their corresponding SPARQL queries against the Freebase knowledge base. Hence, it can be used to perform semantic parsing by taking the questions the inputs and the queries the outputs. As detailed in (Keysers et al. 2019), compositionally hard splits of the CFQ dataset can be generated by maximizing its compound divergence and minimizing its atom divergence. In this paper, focus on the MCD1 split of the CFQ dataset. An example of question and query from this split are shown on the right hand side of Figure
One of the difficulties of the CFQ dataset is that some of its examples require solving cartesian products. As such, CFQ may face similar challenges to the ones described the previous section. Another difficulty is associated with the ordering of the clauses in the SPARQL query, which are ordered alphabetically by convention. Not only is this ordering different than the one implied by the question, it also requires transformers to learn how to sort.
ITERATIVE DECODING
To improve compositional generalization in transformers, we introduce iterative decoding. As il- lustrated the right hand side of Figure [ iterative decoding consists of predicting series of intermediate outputs y1, ...... from an input x = and then adapting these outputs into in- termediate inputs x; yr. i 0, that are fed back the model until the final output yx = y is predicted. This can be visualized by considering the PCFG example x = "swap_fi fit_fflsstttstt repeat copy
A9 N7 v8" on the left hand side of Figure 3 A seq2seq transformer trained on the PCFG dataset is expected to output y = "V8 A9 N7 V8 J4 A9 N7 J4 [END]" in one forward pass (i.e, to go from top to bottom in the figure). However, iterative decoding, the trans- former's is output to the input Zo = would be v8", which is the first intermediate output of iterative decoding (the second string from the top), and corresponds to just executing one of the operations in the input, copy. Setting 2 y1 and feeding this instruction back to the transformer, we obtain y2= "swap.first. V8 J4 A9 N7 vB" (the third string from the top). The intermediate output y/ then becomes the intermediate input Z2. which the transformer processes to produce the final output y/3 = "78 As N7 v8 J4 A9 N7 J4 [END]".
"swap_f of i irs_lass repeat J4 A9 N7
J4 A9 N7
5

---

Under review as a conference paper at ICLR 2022
The main motivation for iterative decoding comes from the very idea of compositional generalization- by decomposing complex instructions into intermediate steps, iterative decoding essentially teaches models how to compose. Another motivation, related to the first, is that iterative decoding mimics how humans are taught how to perform many compositional tasks. For example, when teaching how solve the arithmetic expression x (1 + 1), first we demonstrate how solve the inner sum, then how to climinate the parentheses, and finally how to compute the product. A third motivation for iterative decoding is that learning step by step can potentially prevent shortcut learning, one of the biggest obstacles to compositional generalization in seq2seq. because it reduces the difficulty of the tasks that the transformer needs to learn to execute in a single forward pass.
To implement iterative decoding, we need to modify both how models are trained and how they pre- dict. The most important change in training that, instead of being trained on the original inputs and outputs, iterative decoding transformers are trained on the "intermediate input-intermddiate output" pairs (x.-1, Vi) for S N. These intermediate inputs and outputs are pre-generated, and their form is specific to each task (see Section 4 for examples for the PCFG, cartesian product and CFQ datasets). Additionally, an end-of-iteration token has to be added to the training outputs so that the model learns when stop. Intuitively, the intermediate outputs correspond providing supervision to the transformers on which are the steps that it should execute to solve the task, similar to how humans taught how perform mathematical operations step by step, rather then learning from input-output mappings of complex expressions.
Depending on the number of intermediate steps necessary iteratively decode given example, the prediction requires multiple forward passes of the transformer. Hence, it is implemented as while loop where the stopping condition is finding the end-of-iteration token. This is illustrated on Figure []] which compares seq2seq (left) with iterative decoding predictions (right). After each intermediate prediction, in this paper we use some data processing step to adapt the intermediate outputs into the following intermediate inputs in some datasets. As we could see from the example above, this not necessary for the PCFG dataset, because it has a built-in recursive structure. But it will be for the cartesian product and CFQ datasets as we detail in Section 4 While, ideally this processing step should be learned, we provide manually in this paper to being to understand the possibilities of iterative decoding.
4 RESULTS AND DISCUSSION
In this section describe the iterative decoding schemes for the PCFG, cartesian product and CFQ datasets, and present and discuss numerical results obtained for seq2seq and iterative decoding transformers. All transformers have é 6 encoder/decoder layers, embedding dimension d = 64, feedforward dimension 256 and h = 4 attention heads. For each dataset, each experiment is repeated 3 times. Additional implementation details can be found in Appendix A.
4.1 PCFG
We apply iterative decoding the PCFG dataset by breaking down each example into number of intermediate steps equal to the number of string editing operations present in the original input. Each intermediate step solves the rightmost instruction in the current intermediate input. Up until the last step, all of the intermediate outputs are themselves string editing instructions. Hence, the intermediate outputs do not need be adapted and serve as the intermediate inputs the next step. Hence, the only additional processing of the dataset needed for iterative decoding is the addition of the
token [END] at the end of the final output. An iterative decoding PCFG example with three intermediate steps is shown on the left hand side of Figure 3
To compare iterative decoding with seq2seq, we start by considering basic transformer model with absolute position encodings as in the original architecture by Vaswani et al. (2017). This is so we can observe the advantages of iterative decoding in the absence of any other compositional generalization biases. The sentence eeve-accuracy achieved by these models on the training and test sets of the random, productivity and systematicity splits of the PCFG dataset is shown in the first two rows of Table I From the first row, see that in the random split of the data the test accuracy of the seq2seq model is close to its training accuracy. This indicates that the model generalizes well to in-distribution samples. In contrast, in the productivity and systematicity splits there is

---

Under review as a conference paper at ICLR 2022
Table 1: Sentence accuracy on the training and test sets for the random, productivity and system- aticity splits of the PCFG dataset.
Random
Productivity
Systematicity
Model
train
test
train
test
train
test
seq2seq-abs
87.2%
85.9%
90.6%
34.2%
89.5%
64.8%
it-dec-abs
96.5%
93.2%
96.6%
45.7%
94.6%
82.9%
seq2seq-rel
98.1%
97.4%
98.8%
65.1%
98.2%
85.7%
it-dec-rel
99.8%
99.2%
100%
91.9%
99.7%
97.0%
seq2seq-rel&copp
97.7%
97.0%
98.3%
63.9%
98.2%
85.1%
it-dec-rel&cooy
99.7%
99.4%
100%
93.3%
99.8%
97.8%
dramatic drop in test aceuracy. This shows that the basic seq2seq transformer struggles to generalize compositionally. In the second row of Table we see that for the iterative decoding transformer the gap between training and test accuracy is much smaller, especially the systematicity split. This indicates that iterative decoding increases the ability of transformers generalize compositionally.
Although iterative decoding helps with compositionality, the test accuracy achieved by the iterative decoding transformers is still low compared to their training accuracy. This implies that composing individual operations into complex instructions is only one facet of compositionality, which makes sense decomposing complex instructions into individual operations only helps if the model can execute each operation correctly (see Appendix B for more details). To verify this claim numeri- cally, we repeat our experiments with transformers including modifications shown increase com- positional generalization in seq2seq learning (Ontañón et al., (02T). These modifications are: (a) replacing absolute attention by relative attention (Shaw et al.j 2018). and (b) adding a learnable parameter that allows to switch between the decoder and a copy decoder (Ontañón et al. (021).
The results for seq2seq and iterative decoding with relative attention are shown in the third and fourth rows of Table [ The relative attention radius is 8. As expected, relative attention helps both models with compositionality, particularly in the productivity split. However, iterative decoding achieves a much better test accuracy, of over 90%, on both the productivity and systematicity splits. Results for transformers with relative attention and copy decoders are shown in the fifth and sixth rows of Table I While adding a copy decoder does not improve compositional generalization in the seq2seq transformer, it helps in iterative decoding, nearly closing the gap between training and test accuracy on the systematicity split, and leading to 2% increase in test accuracy on the productivity split-whiel can be attributed to the ability to copy the longer strings in this split.
4.2 CARTESIAN PRODUCT
To iteratively decode cartesian product, we first need to define what going to be the iterative decoding intermediate steps. There are many possibilities; we could, for instance, define an inter- mediate step as predicting
output token at time, or sequence of tokens with fixed length. In this paper we consider two options. The first is decoding one row at a time. As illustrated on the top right corner of Figure 3 this entails decoding the cartesian product between one element from the first vector and all elements of the second vector at each intermediate step. The second is decoding one token pair at a time. As illustrated on the bottom right corner of Figure this entails decoding only the product between one element of the first vector and one element of the second vector at each intermediate step. If the lengths of the input vectors are l and &g respectively. decoding row by row requires & and token by token & x & intermediate steps.
When decoding one row time, the intermediate output given step is the current row. Sim- ilarly, when decoding one pair of tokens at a time, the intermediate outputs are the current token pairs. Since these intermediate outputs do not carry any information about the next row or pair of tokens to predict, they cannot be used as intermediate inputs. To construct intermediate inputs, thus concatenate a copy of the original input-thhe the two vectors separated by the (SEP) ] token ooken-with with second separation token [SEP2] followed by either (i) the last intermediate output, (ii) all the intermediate outputs so far. Scenario (i), which is illustrated on the right hand side of Figure
3 yields short intermediate imputs where the last intermediate output acts "pointer" to where
7

---

Under review as a conference paper at ICLR 2022
the decoding process stopped in the previous step. Scenario (ii) produces long intermediate inputs. While in both scenarios the intermediate outputs need to be appended to produce the final predic- tion, their prediction routines are slightly different because scenario (i) only needs to concatenate the current intermediate output to the input vectors to produce the next intermediate output, but scenario (ii) needs append the current intermediate output to the last intermediate input to produce the next intermediate input. Note that there are many other possibilities to construct intermediate inputs (c.g., only including the last two, three, four, etc. intermediate outputs). There are also different options for the intermediate outputs. Instead of being only the next row or pair of tokens, for instance, they could be all the rows or all the token pairs so far.
Table 2: Sentence accuracy achieved by the seq2seq and iterative decoding transformers with relative attention (r 8) on the training set and on multiple test sets of the cartesian product dataset.
Iterative
short inputs
long inputs
Split
Seq2seq
row
token
row
token
train (up to numbers/letters)
100%
100%
100%
100%
100%
test (up to 5 numbers/letters)
97.8%
100%
100%
100%
100%
test (6 numbers, 5 letters)
14.3%
89.2%
100%
100% %
100%
test (5 numbers, 6 letters)
12.2%
0%
99.5%
0%
100%
test (6 numbers/letters)
1.1%
0%
98.7%
0%
100%
To analyze the compositional generalization ability of seq2seq and iterative decoding transformers on the cartesian product dataset, we consider the following experimental setup. Both transformers are trained on samples with up to five numbers and letters. Then, they are tested on the four different test sets deseribed in Section 2.3.2] up to five numbers and letters; six numbers and five letters; five numbers and six letters; and six numbers and letters. The second, third and fourth test sets can be seen productivity tests. Additionally, we only report results for transformers with relative attention (relative radius r = 8) as they were the hest performing architecture in our experiments.
The average training and test accuracies achieved by the seq2seq model, as well as by the iterative decoding model in the short/long intermediate input and row/token scenarios, are reported in Table We observe that the seq2seq model (first column) achieves 100% accuracy on the training set and close to that on the "easy" test set with up to five numbers and letters. However, it pretty much fails in all of the "hard" test sets, implying that it cannot generalize compositionally to even one extra token being added to the input. The iterative decoding models that decode one row at time (second and fourth columns) do slightly better as they achieve accuracy closer to the training accuracy in the test set with six numbers and five letters. However, they still fail at the test sets with six letters, which means that the iterative decoding transformer trained to decode one row at a time only generalizes well to calculating cartesian products with larger number of numbers or, equivalently, of rows.
In contrast, the iterative decoding models that decode one pair of tokens at a time (third and fifth columns) achieve close to or exactly 100% accuracy in all of the compositionally hard splits. This means that the iterative decoding transformer can only generalize to longer iterations when these iterations are the ones that were unrolled during training via iterative decoding. If we take trans- former that has been trained to decode rows, and add one more letter to the input-resulting in one more pair of tokens in each row- it will not be able predict this additional token pair because it has learned how to unroll more rows through iterative decoding but not more token pairs within a row. We thus conclude that in the cartesian product dataset transformers struggle to learn iteration by themselves, i.e., without the help of iterative decoding. This is an important result because, de- spite being universal function approximators in theory (Yun et al. 2019), sheds light onto what transformers can actually learn in practice. Finally, the difference between long and short inputs is not substantial, but longer inputs seem to better, probably because they provide the transformer with more memory (i.e., more information about the previous intermediate steps).
4.3 CFQ
Both PCFG and cartesian product were well adapted for iterative decoding because, in PCFG, the recursive structure of the inputs makes it easy define the intermediate steps, and in cartesian prod-
8

---

Under review as a conference paper at ICLR 2022
uet we have the flexibility choose their granularity. On the CFQ dataset, defining the intermediate steps is less obvious. The natural choice is to define each intermediate output as a clause of the query as illustrated on the bottom of Figure However, unlike in -FFG-where the order of the interme- diate steps was defined by the recursion-and in cartesian where the order of the tokens in the input determines the order of the intermediate steps- this ordering of the intermediate steps is not very "natural" because the clauses are sorted alphabetically. Hence, on CFQ transformers also have learn how to sort.
To make learning this ordering easier for the transformer, we define long intermediate inputs for the intermediate steps. These intermediate imputs are constructed by concatenating the question with all of the previous intermediate outputs so far. As such, on CFQ the iterative decoding prediction routine the same as for cartesian product with long inputs: we append the current intermediate output to the previous intermediate input to obtain the next intermediate input, and, once the end-of- -f-ieiitttaaion token predicted, concatenate all of the intermediate outputs to obtain the query prediction.
Table 3: Sentence accuracy achieved by the seq2seq and iterative decoding transformers with relative attention (r 8) the training and test sets of the MCDI split of the CFQ dataset.
Split
Seq2seq
Iterative
train
99.8%
99.7%
test
37.1%
32.5%
Following this iterative decoding scheme, compare the compositional generalization abilities of a seq2seq and an iterative decoding transformer on the MCDI split of the CFQ dataset. The average training and test accuracies are shown in Table 3] where we only report results for the best performing model in our experiments-relatiee attention with relative radius r 8. Both the seq2seq and the iterative decoding transformer exhibit low compositionality, however, iterative decoding performs worse than seq2seq. This reinforces the limitations of iterative decoding that we observed in cartesian product, namely, that iterative decoding performance is largely dependent on how we define the intermediate steps. In the case of CFQ specifically, we also hypothesize that the worse performance of iterative decoding can be tied to the alphabetical ordering of the clauses, as it does not follow naturally from the grammatical structure of the input. Even though sorting these clauses is something that both the seq2seq and the iterative decoding transformer have to learn how to do, in iterative decoding the transformer has to sort at all intermediate steps, so there are more opportunities to make mistakes. In other words, the error probability is larger in iterative decoding, because it compounds with each intermediate step.
5 CONCLUSIONS
This paper introduces iterative decoding, alternative to seq2seq learning that consists of predicting a series of intermediate outputs from an input, and then adapting these outputs into intermediate in- puts that are fed back the model until sequence containing an end-of-iteration token is predicted. Through numerical experiments on the PCFG and cartesian product datasets, we demonstrate that, in general, seq2seq transformers do not learn iterations that are not unrolled. By unrolling them, iterative decoding improves transformer compositional generalization. Additional experiments on the CFQ dataset illustrate a limitation of iterative decoding, which is that it depends on how the intermediate steps are defined. In particular, we hypothesize that their ordering is the reason why the seq2seq transformer outperforms iterative decoding on CFQ, as any ordering that is not inherent to the data requires transformers to learn how to sort and iterative decoding may increase the overall sorting error probability.
As part of our future work, we aim to apply iterative decoding strategies more datasets and under- stand whether some of the iterative steps can be traded for transformer depth. We also intend to use iterative decoding to investigate the aspects of compositional generalization that transformers can and cannot learn. A clear next step is understanding the effect of the order of the intermediate steps in iterative decoding, and what that effect has to say about the transformer's ability to sort.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Joshua Ainslic, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. Ete: Encoding long and structured inputs in transformers. arXiv preprint arXiv:2004.0848 2020.
Jacob Andreas. Good-enough compositional data augmentation. arXiv preprint arXiv:1904.09545, 2019.
Andrea Banino, Jan Balaguer, and Charles Blundell. Pondernet: Learning ponder. arXiv preprint arXiv:2107.05407, 2021.
Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. arXiv preprint arXiv:2108 12284, 2021.
Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800 2018.
Daniel Furrer, Marc van Zee, Nathan Scales, and Nathanael Schärli. Compositional generalization in semantic parsing: Pre-training vs. specialized architectures. arXiv preprint arXiv:2007.08970 2020.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwiñska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using neural network with dynamic external memory. Nature, 538 (7626):471- 476.)6,777766----- 2016.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: how do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020. 2020.
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashu- bin, Nikola Momehev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. Measur- ing compositional generalization: A comprehensive method on realistic data. arXiv preprint arXiv:1912.09773.. 2019.
Juyong Kim, Pradeep Ravikumar, Joshua Ainslie, and Santiago Ontañón. Improving compositional generalization in classification tasks via structure annotations. arXiv preprint arXiv:2106. 10434, 2021.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of soquence-to-sequemee recurrent networks. In International conference on machine learning, pp. 2873-2882 PMLR, 2018.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436-444 2015.
Adam Liška, Germán Kruszewski, and Marco Baroni. Memorize or generalize? searching for compositional rnn in haystack. arXiv preprint arXiv:1802.064400 2018.
Benjamin Newman, John Hewitt, Percy Liang, and Christopher D Manning. The cos decision and length extrapolation. arXiv preprint arXiv:20/0.07//20 2020.
Santiago Ontañón, Joshua Ainslie, Vaclav Cvicek, and Zachary Fisher. Making transformers solve compositional tasks. arXiv preprint 10Xiv:2108.0437,, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yangi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint wxXiv:110.10660 2019.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. arXiv preprint /803./800..22 2018
10

---

Under review as a conference paper at ICLR 2022
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-seqqeecc functions? arXiv preprint arXiv:1912.1007,.20 2019.
Xingxing Zhang, Furu Wei, and Ming Zhou. Hibert: Document level pre-training of hierarchical bidirectional transformers for document summarization. arXiv preprint wrXiv:/905.0666 2019.
Jinhua Zhu, Yingce Xia, Lijun Wu, Di He, Tao Qin, Wengang Zhou, Houqiang Li, and Tie- Liu. Incorporating bert into neural machine translation, arXiv preprint arXiv:2002.06823, 2020.

---

Under review as a conference paper at ICLR 2022
A APPENDIX A: IMPLEMENTATION DETAILS
Across all experiments, the transformer parameters were the same as in the original implementation in (Vaswani al. 2017), including the learning rate schedule. All experiments were run on machines with single CPU and four Tesla V100 GPUs with batch size 64 per device.
Table 4: Vocabulary size, training and test samples, and number of training steps for all seq2seq and iterative decoding datasets.
Seq2seq
Iterative
vocabulary
train
test
vocabulary
train
test
steps
PCFG-i.i.d
534
82662
9721
535
426558
9721
33325
PCFG-prod.
534
81010
11333
535
346222
11333
27049
PCFG-syst.
534
82168
10175
535
403808
10175
31458
Cartesian-row
26
200000
1024
28
600036
1024
4688
Cartesian-token
26
200000
1024
28
1801869
1024
14077
CFQ
181
95743
11968
186
682470
11968
53318
For each dataset, and for both the seq2seq and iterative decoding splits, the vocabulary size, the size of the training and test sets, and the total number of training steps is shown in Table The iterative decoding vocabularies are larger due to the addition of special start, end and separation tokens. The number of training samples is larger for the iterative decoding splits because they include all intermediate steps. make for fair comparison, the number of training steps the same for iterative decoding and seq2seq.
B APPENDIX B: ADDITIONAL ITERATIVE DECODING RESULTS FOR PCFG
To assess the advantages of iterative decoding under no other sources of compositional general- ization, we consider the base transformer (i.e., without relative attention and copy decoder) and analyze its performance on PCFG per number of string editing operations. Namely, Figure we plot the number of correct predictions achieved by seq2seq (orange) and iterative decoding (blue) on the productivity and systematicity splits of PCFG. We observe that, in the productivity split, the performance improvement comes mostly from samples with small number of string editing in- structions. Consistent with Table [ without any other form of compositional generalization bias iterative decoding is more helpful with systematicity.
1600
1000
1400
1200
800
1000
800
400
200
200
10
20
10
15
Number of operations
Number operations
Figure 4: Number of correct predictions versus number of string operations in the input for seq2seq (orange) and iterative decoding (blue), the productivity (left) and systematicity (right) splits of PCFG.
We draw a similar conclusion from Figure which plots the error per intermediate step ((est error) where N the number of operations) versus the number of operations in the input for both splits. The error per intermediate step be the probability of making mistake at any given intermediate step. On the left, this error approaches one for a smaller number of opera- tions than the right, indicating that errors compound faster in the productivity split. Interestingly,
12

---

Under review as a conference paper at ICLR 2022
Entr shop
06-
0.
04
04
02
02
00
0.0
operations
Figure 5: Error per intermediate step versus number of string operations in the input for the iterative decoding transformer the productivity (left) and systematicity (right) splits of PCFG.
this figure also corroborates our claim from Section 4.1
that decomposing complex instructions into
individual operations only helps if the model can execute each operation correctly. In other words, composing individual operations into complex instructions only one facet of compositionality, but one with which iterative decoding helps.
13


Reviews:
[{"review_id": "WCn08KKJayy", "reviewer": "Reviewer_YC1Z", "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": "Strengths:\n- The problem studied in the paper, i.e. addressing the inability of Transformers (and more generally, neural models) to generalize compositionally, is an important one.\n- The paper is written well.\n\nWeaknesses:\n- The biggest weakness of the paper is that it requires the problem to be broken down into iterative subproblems, and it is not at all clear how one might do this with non-synthetic tasks. In fact, sequence-to-sequence is interesting/powerful/general precisely **because** we don't need to manually break down the problem into subproblems.\n- I could see some value in this approach if some heuristically-driven approach to creating intermediate input-output pairs resulted in some gains, but this seems clearly not to be the case as evidenced by the underperformance of the proposed approach compared to a regular seq2seq baseline in the CFQ task.\n\nI apologize for the somewhat harsh review, but I truly do not see how this approach would be at all applicable to general tasks. (In fact, it is not at all clear how how one might adapt this approach for even slightly more complex synthetic tasks such as SCAN/COGS.) I am happy to be convinced otherwise though during the discussion (e.g. if this approach is able to meaningfully improve performance on real world low resource sequence-to-sequence learning tasks, I would revise my score upward significantly). ", "summary_of_the_paper": "This paper studies compositional generalization in the context of Transformer models. Noting that \"one-shot\" sequence-to-sequence learning with Transformer models often results in models that do not generalize compositionally, the authors propose an iterative scheme whereby intermediate input-output pairs are constructed for each task (how this is constructed varies depends on the task), and the decoding proceeds as a series of seq2seq tasks. The approach is found to perform well on synthetic tasks (PCFG, Cartesian product) where there is a \"natural\" way to construct the intermediate input-output pairs, but fails to perform well on more real-world tasks such as CFQ.", "summary_of_the_review": "While the approach does improve compositional generalization in certain synthetic tasks, it is almost completely inapplicable to real, interesting problems such as translation or semantic parsing. ", "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": "OcK10eIlZmV", "reviewer": "Reviewer_BXC7", "summary": "", "questions": "", "limitations": "", "rating": 5, "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- The proposed technique is very simple and requires little or no architecture changes to the transformer. It seems particularly effective on PCFG.\n- Compositional generalization is a very important problem for the ML community, and the paper presents a useful technique to address this.\n\nWeaknesses\n\n- Some of the results are confusing. PCFG seems like an excellent fit for the proposed approach, but the technique applied to Cartesian Product and CFQ is somewhat strange.\n- Given that PCFG was the task that is primarily relevant, the paper would greatly benefit from more detailed error analysis. In other words, the paper is somewhat lacking in content and results as-is.\n- There is clearly a lot of missing related work. Compositionality is not a problem only recently found in the ML community...\n- (medium priority) The writing could be greatly improved in terms of organization, frequent minor errors, and missing details. Although this seems easily addressable in a revision.\n\nComments:\n\na. “By endowing models with the ability to extrapolate to unseen examples that are more complex, or complex in different ways than seen at training, compositionality acts as an implicit mechanism for data augmentation.”\n\nI am not sure it is fair to call “walk right” more complex than “jump right”. Later, complexity is defined: “Compositional generalization (or compositionality) refers to the ability of a model that has learned to perform a set of basic operations—primitives—to generalize to more complex operations, i.e., operations consisting of compositions of the learned primitives”. By this definition, I can see that “walk right” is more complex than “walk” or “right”, and it is only learnable because similarly complex ops (i.e. “jump right”) are seen during training.\n\nI recommend clarifying the quoted statement. Perhaps something like, “unseen examples involving composition not seen during training.”\n\nb. (low priority) “During testing, the model is tested by asking it to compose a longer number of operations than seen during training. Hence, the model has to be able to generalize compositionally.” Very low priority comment… It is not necessary to anthropomorphize the model so much. Possible re-write (take it or leave it): “The test data contains longer sequences with more operations than seen during training. Hence, the model's performance relies on compositional generalization.”\n\nc. You may be interested in another related work/dataset, ListOps (Nangia and Bowman).\n\nd. You may be interested in other works that describe copy mechanism in seq2seq models: Gu et al. 2016 (Incorporating Copying Mechanism in Sequence-to-Sequence Learning) and Gulcehre et al. 2016 (Pointing the Unknown Words). Also, Vinyals et al. 2017 (Pointer Networks), which says plainly in the abstract: “We show that the learnt models generalize beyond the maximum lengths they were trained on.”\n\nIn general, it seems the references used in the paper are mostly from recent work, although many mechanism (halting property as another example) exist in many older work that addressed the same problems.\n\ne. How can one tell if the model is learning “shortcuts”? And how does a shortcut differ from overfitting? For example, is a shortcut simply any behavior different from the desired type of compositionality?\n\nf. It would be helpful to re-arrange the figure so they appear closer to the usage in text. This should be very doable because Figures 1 and 3 contain many subfigures.\n\ng. This description is not particularly informative without reading Keysers et al.: “maximizing its compound divergence and minimizing its atom divergence”. Perhaps remove or explain further?\n\nh. Given that relative attention and copy decoder are critical for good performance, they should really be covered in more detail in the main text.\n\ni. The use of “iterative decoding” in Cartesian Product seems very basic and not really representative of intermediate steps. This is partially addressed in the text, but it still seems strange to group this technique with the one used for PCFG. Also, is it possible this is actually addressing a different problem from compositional generalization? Based on how the seq2seq model is used, the problem with seq2seq might be an inability to incorporate large contexts. Similar comment for CFQ.\n\nj. In general, it would be helpful to have more error analysis. Which types of instances failed to predict correctly? Even for the hard splits, often some of these are predicted correctly.\n\nk. As reviewer YC1Z mentioned, it would be helpful to the reader to provide some ideas of how to apply this technique to other tasks.\n", "summary_of_the_paper": "This paper presents a type of “task re-formulation” that re-arranges the labels in task such that they are easier for transformer-based encoder-decoder models. This technique is specifically meant to address compositional generalization, which roughly means to generalize to instances longer than seen during training, with combinations of tokens not seen during training, and so on (further clarified in the paper). The paper presents interesting results on three tasks (PCFG, Cartesian Product, and CFQ). I find the problem of compositional generalization with transformers to be very important for the ML community, and that the results are mostly useful. Nonetheless, there is a substantial amount of missing related work, and the writing could greatly be improved.", "summary_of_the_review": "I believe this paper is slightly below acceptance threshold because of the listed weaknesses. I may not be convinced in the strength / significance of all the results, but perhaps this would be made more clear after addressing problems in the writing.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EFKYgjWbzfT", "reviewer": "Reviewer_LPPa", "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": "Strengths:\n1. The motivation is clearly presented.\n2. They provide detailed instructions on how to construct \"intermediate input-intermediate output\" pairs.\n3. They achieve strong performance on PCFG and Cartesian product datasets.\n\nWeaknesses and concerns\n1. The construction of \"intermediate input-intermediate output\" can be difficult for practical problems. For example, it is nontrivial to define sequential subtasks for CFQ(discussed in the paper), classification or machine translation. Furthermore, the construction itself can be seen as a compositional generalization problem because it must know how to identify primitives and execute composition first. \n2. missing baselines, A baseline is a seq2seq model trained with the original data as well as the sealed  \"intermediate input-intermediate output\" pairs. Sealed means the intermediate output transformed to the same form of the original data. This is trivial for PCFG and Cartesian product given your current preprocessing.  For example, given \"swap_first_last repeat copy\", you can produce samples with \"swap_first_last\", \"swap_first_last repeat\" and \"repeat copy\".  This is because the construction relies on external knowledge while the current baseline does not see it at all.\n3. Relative attention and copy decoders are not well-discussed on the effect to compositional generalization. The paper makes the conclusion from improved performance, but (I believe) even a larger model with the same structure can produce stronger performance (e.g., bert-tiny and bert-large). There are lots of variants of transformers, then why these two techniques matter?\n4. Experimental results are not compared with other works in this paper. For PCFG(systematicity split), the paper which proposes the dataset report 72 for Transformer while this paper report 64.8. Recent works use T5 without designed components and achieve >50 for CFQ(MCD1 split). However, this paper uses the original transformer(which is not optimized for seq2seq task) and achieves only <40. \n", "summary_of_the_paper": "This paper proposes a decomposed training target for transformers to improve compositional generalization. Specifically, a complex task is decomposed into sequential subtasks by external knowledge to exposure the procedure of composition. Then, they train transformers to reproduce these intermediate steps and perform iterative decoding during prediction. Besides, they adopt relative attention and copy decoders to improve the performance of each step, resulting in overall improvements. They achieve strong performance on PCFG and Cartesian product datasets and report negative results on CFQ dataset.", "summary_of_the_review": "The iterative decoding proposed in this paper has limited to toy datasets. The conclusion about relative attention and copy decoders is not well-supported. ", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "BImZlrLdOIb", "reviewer": "Reviewer_BbzM", "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": "Strengths:\n1. The idea of iterative decoding for compositional generalization is interesting and intuitively makes sense. It encourage the model to learn how the reasoning (generalization) is unfolded.\n2. The experimental results on the PCFG and cartesian product datasets is promising and show clear improvements compared to seq2seq counterparts.\n\nWeaknesses:\n1. The main method (iterative decoding) is described after spending much space on describing datasets, which is somewhat inconvenient for  readers. Maybe consider introducing the datasets in the experiments section will make the paper easier to follow.\n2. According to my understanding, iterative decoding will significantly increases the computational costs (roughly x number of intermediate steps). This could be a significant drawback but is not mentioned in the paper.\n3. Iterative decoding can be seen as autoregressive generation in the level of reasoning steps. Therefore, if the iterative decoding model is trained with MLE and teacher forcing (training of iterative decoding is not described in the paper), it will face the exposure bias problem. How much is that problem affecting the performance is needed to be investigated.\n4. As shown in the CFQ dataset, the proposed only works in cases where intermediate steps can be clearly defined. However, in most cases it is not the case, therefore is unclear whether the proposed method can generalize to many tasks. Therefore the application of the method can be quite limited.", "summary_of_the_paper": "This paper introduces iterative decoding to improve the compositional generalization ability of seq2seq models. Iterative decoding predicts a series of intermediate outputs from an input, and then adapting these outputs into intermediate inputs that are fed back to the model until a sequence containing an end-of-iteration token is predicted. This approach explicitly encourage the model to learn to unfold the compositional generalization procedure. Experiments on the PCFG and cartesian product datasets show that iterative decoding can improve the compositional generalization ability of seq2seq models. However, additional experiments also show that iterative decoding may fail in more general datasets that do not have explicit intermediate steps defined.", "summary_of_the_review": "The proposed method is simple but intuitively make sense. However, the method can be limited and only works in certain scenarios. Also, there are efficiency problems and exposure bias problems that are not mentioned in the paper. Therefore I think the paper is below the bar in its current form. I believe it can be improved by addressing the aforementioned weaknesses.  ", "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": {}}]

Author rebuttal:

Meta-review: All reviewers raise issues with the proposed method and whether it is a) applicable to non-synthetic tasks/datasets; b) how
the input could be broken down into intermediate subproblems in a principled way and whether this would substantially 
make the proposal slower than the vanilla encoder/decoder framework; c) awareness of previous work. It is a same the authors
did not provide a response, however the reviewers have provided useful feedback they could use to improve their submission.
Decision: Reject