Sparse Universal Transformer
Authors: Shawn Tan
Yikang Shen
Zhenfang Chen
Aaron Courville
Chuang Gan
Venue: EMNLP 2023 Main (2023)
Keywords: efficient UT
transformers
sparse moe
conditional computation
NLP
wmt14
cfq
compositional generalization
natural language processing
sparse
TL;DR: We propose Sparse Universal Transformers, scaling up Universal Transformers with conditional computation, using both Sparse MoEs and dynamic halting to achieve better parameter efficiency, demonstrating better compositional generalisation.

Abstract: The Universal Transformer (UT) is a variant of the Transformer that shares parameters across its layers and is Turing-complete under certain assumptions. 
Empirical evidence also shows that UTs have better compositional generalization than Vanilla Transformers (VTs) in formal language tasks.
The parameter-sharing also affords it better parameter efficiency than  VTs.
Despite its many advantages, most state-of-the-art NLP systems use VTs as their backbone model instead of UTs. 
This is mainly because scaling UT parameters is more compute and memory intensive than scaling up a VT.
This paper proposes the Sparse Universal Transformer (SUT), which leverages Sparse Mixture of Experts (SMoE) to reduce UT's computation complexity while retaining its parameter efficiency and generalization ability. 
Experiments show that SUT combines the best of both worlds, achieving strong generalization results on formal language tasks (Logical inference and CFQ) and impressive parameter and computation efficiency on standard natural language benchmarks like WMT'14.

Sparse Universal Transformer
Shawn Tan'*
Yikang Shen
tanjings@mila.. quueeeeell...ubbee
yikang. shen@ibm. com
Zhenfang Chen zfchen@iben bm. com
Aaron Courville'
Chuang Gan chuangg@ibm. com
courvila@iro. www.:roo..mmtteaaa.c.ommm ca
Mila, University of Montreal
MIT-IBB Watson Al Lab
Abstract
Block
The Universal Transformer (UT) is variant of the Transformer that shares parameters across its layers. Empirical evidence shows that UTs have better compositional generalization than Vanilla Transformers (VTs) in formal language tasks. The parameter-sharing also affords it better parameter efficiency than VTs. Despite many advantages, scaling parameters is much more compute and memory intensive than scaling up a VT. This paper proposes the Sparse Universal Transformer (SUT). which leverages Sparse Mixture of Experts (SMoE) and a new blick-breaking-aase baaed dynamic halt- ing mechanism reduce UT's computation complexity while retaining its parameter effi- ciency and generalization ability. Experiments show that SUT achieves the same performance as strong baseline models while only using half computation and parameters on WMT' 14 and strong generalization results on formal lan- guage tasks (Logical inference and CFQ). The new halting mechanism also enables around 50% reduction in computation during inference with very little performance decrease on formal language tasks.
Block
Block
Block
Block
Transtommer
Universal Transformer
Block
Block
Block
Block
Block
Blook
Block
Block 2
Block
Universal Sparse Transformer
Figure 1: VT has separate Transformer blocks for each layer, with different parameters. For UT with the same number of parameters, the UT block will ~3 times the dimensions of each VT block. Running this block for layers would then incur approximately times the runtime memory. Using SMoEs can recover approximately the same computational cost as the VT.
along with absolute and relative position embed- dings, and showed that UTs with relative positional embeddings performed better on these tasks.
1 Introduction
However, the task of scaling UTs challenging due to its computation complexity (Kaplan et al., 2020; Tay et al., 2022; Takase and Kiyono, 2021). Consider VT with P parameters for each layer and L layers. Evaluating such a VT has compu- tation complexity associated with the model size LP. A sizc-equivalent UT would have UT block with LP parameters and computation complexity of approximately LP run the block once. To run such UT for equivalent I layers would incur a complexity of L This increased computation complexity directly translates to increased train- ing and inference time. According to Takase and Kiyono (2021), 1), UT requires two times the training time and far more GPU memory than VT in WMT Bagglih--Germal translation task.
Recent theoretical work has pointed out that finite- depth Transformers have an issuc of expressibility that will result in failure to generalize (Hahn, 2020; Hao et al., 2022; Merrill et al., 2022; Liu et al., 2022). Delétang al. (2022) ran several neural architectures on suite of different synthetic lan- guages generated from different levels of the Chom- sky hierarchy and empirically confirmed these re- sults, showing that VTs have difficulty generaliz- ing to Regular languages. Universal Transformers (UTs; Dehghani et al. 201 8) are Transformers that share parameters every layer of the architecture. Csordás et al. (2021) performed several composi- tional generalization experiments VTs and UTs
Equal contribution
Sparsely activated neural networks were intro-

---

duced reduce the computation complexity of large models. These networks activate parts of the network conditioned on the input, computing only parts of the model, thereby disentangling the num- ber of parameters from the computation complex- ity. This method allows for drastically increasing the number of parameters without proportionally increasing the computation complexity. Shazeer al. (2017) introduced Sparse Mixture of Ex- perts (SMoE), using the top-k operator allow for sparse computation of experts. This allows for replacing the FeodForword (FFD) layer in the Transformer with an ensemble of Ena FFDs, but only k FFDs (where & < E) would have to be evaluated, conditioned on the input. Zhang et al. (2022) then introduced the Mixture of Attention heads (MoA), which allows Transformers to re- place its Multihead Attention (MHA) layer with an ensemble of Ean attention heads and only activates & heads condition on the input, further sparsifying the model.
Thairing fime
time
Operaiun
Openation
and
nol
Figure Example the compositional generalization splits from (Shen et al., 2019). The combination of not and and are never seen in successive combination during training, and a VT may learn shorteut that prevents generalisation during test.
Background & Related Work
Overcoming VT limitations with UT Dziri al. (2023) and Liu et al. (2022) find that Vanilla Trans- formers learn shortcuts for tasks that require multi- step compositional operations. and fail to general- ize on larger instances of the problem that require more steps. Theoretical results have also shown that Vanilla Transformers have limitations in what they can compute that support these findings (Hahn, 2020; Hao et al.. 2022; Merrill al., 2022). Univer- sal Transformers (Dehghani et al., 2018) are Trans- formers with tied weights across all layers, and an additional halting mechanism to decide when to stop. In an ideal scenario of infinite layers (now that all layers have the same parameters) the UT, like the Neural GPU (Kaiser and Sutskever, 2015), is Turing-complete, which overcomes many of the abovementioned issues.
This paper introduces the Sparse Universal Transformer (SUT), which applies the above sparse computation techniques to UT. Additionally, we re- place the per-position halting mechanism in UT with new stick-breaking formulation that has probabilistic interpretation, allowing us to intro- duce Adaptive Computation Time (ACT; Graves 2016) penalty to minimize layer use. It also pro- vides an easy way to adjust the trade-off between the amount of computation and model performance during inference, further improving the efficiency of the SUT at inference time.
In practice, even with limited depth, UTs have exhibited properties that afford them better perfor- mance in compositional generalization tasks (Csor- dás et al., 2021). UT's allow operations learned in the Transformer during training to be depth-order invariant. If some operations during training are learned be performed in a certain order, during test time, the UT could generalize to an unseen order of operations.
To demonstrate effective scaling, we perform experiments on WMT" 14 English to German trans- lation. showing that an SUT can achieve better performance for the same parameter count, while incurring less computation cost than an equivalent dense UT. Since the UT setting is a specific case SUT, we show on the Compositional Freebase Questions (CFQ; Keysers et al. 2019) tasks that UTs have better compositional generalization prop- erties, improving upon CFQ results from Csordás et al. (2021). Using the Logical Inference task (Bowman et al., 2015), analyse the behaviour of our UT on length and compositional generalization. Finally, we show that the halting mechanism can be used to achieve further efficiency during inference time, and study the trade-off between efficiency and performance.
Challenges with Scaling the UT Despite these compositional abilities, performance tends to de- crease real-world tasks when using UTs. AL- BERT (Lan al., 2019) improved parameter effi- ciency by sharing parameters across layers. This was motivated by an observation that Transform- ers tend to learn to perform similar operations the layers, and that sharing these parameters would

---

reduce this redundancy'. However, the authors observe a dip in performance when sharing param- eters, contrary to Dehghani et al. (2018).
perts, while maintaining that Σe g(e h) 1. The final output of the SMoE is then given by = -e= g(e [e) where g(e h) = 0. (h) will not need to be evaluated, reducing computation cost during training and inference. We replace the Feed-forward layer (FFD) in the Transformer block with a mixture of FFDs. Each Mixture of FFD can be described with a 3-tuple, (E, K. D): E experts, & for the number of experts to be used in the top-k operation, and D for the dimension of the hidden layer for each FFD expert. For the attention layer, we use the Mixture of Multi- head Attention (MoMHA) proposed by Zhang et al. (2022) and Shen et al. (2023). Each MoMHA mod- ule can be described by a 5-tuple, (E, k. H, D. W), with E representing the number of experts, K rep- resenting the parameter k in top-k operation, H representing the number of attention heads per ex- pert, and D for the dimensions per head. Like in MoA, MoMHA maintains only a single set of key-value projections shared among the experts, while there are E query projections of H heads each. W represents the relative position embed- ding window size, parameterizing 2W + 1 embed- dings for W positions before and after the present position. Figure 3 (Left) shows the schematic of SUT block.
Could the issue be one of model capacity? Ex- periments with ALBERT show that scaling up AL- BERT can outperform the BERT baseline, even on real-world tasks (Lan et al., 2019). Kaplan al. Trans-
(2020) also show that former has better scaling properties in terms of parameter-to coaameterto-perfommaneee in terms of performance, but poorer properties since pa- rameter count causes the computation to increase. Tay et al. (2022) scale up different sequence mod- els, and remark on difficulties with scaling up UTs, limiting the experiments they can perform on UT. Takase and Kiyono (2021) outline several strategies of scaling up shared-parameter Transformers to deal with these issues by using different parameter- sharing schemes.
Our experiments show that SMoE techniques can be applied successfully to the UT to scale it up. achieving the UT's parameter efficiency while not incurring the same computation costs. We also per- form experiments that support the compositional generalization claims of prior work, and provide better baselines for those tasks.
3 Method
This technique has been used to reduce compu- tation costs both during training and inference time for large models.
Like UT, we reuse the same SUT block for every layer of the Transformer. Within each SUT block, we use SMoEs to achieve sparsity for the feed- forward network (FFD) and attention heads sepa- rately. We use the Mutual Information Maximiza- tion loss proposed in Chen et al. (2022) and mod- ified for unsupervised tasks in Shen et al. (2023). Finally, we propose a stick-breaking process for- mulation of dynamic halting, which affects how the attention mechanism works in the SUT, and the Adaptive Computation Time (ACT) auxiliary loss we use to minimize the number of layers used.
Mutual Information Maximisation Like other models that rely on conditional activation, auxiliary losses are needed in order to aid learning mod- ule that decides which experts are activated, and to ensure that all experts are used, balancing the load for processing. For this, we use the Mutual Information Maximization introduced in Chen et al. (2022) for the auxiliary loss (to be maximised):
MIM
g(c) log.(c)
3.1 Sparse Mixture of Experts
A Mixture of Experts module consists of E sub- modules Je. There is also a gating network, which we will denote by g(e h) for any input h to the MoE module, the gating network would predict distribution over the E experts. When k < F,, refer to this as Sparse Mixture of Experts (SMoB), and g(e h) > for only k ex-
M(e))
E
Σ
g(e
h) logg(e) h), (1)
X
heX
Hic h)
where,
htttps://at //ai. googleblog. ctt.ll/g.cm//01///121 albert-lite www.l-eeee-----eee bert-for-see soattforr-elf-supaee sewf-supervised. html
g(e) =
Σ g(e(h)
X
he

---

Halting
Y1
22
Y3
Y4
Ys
MLP
MLP
MLP
MLP
Router
Norm
ARt
Att
Alt
All
X
X
Figure 3: Left: Schematic of a SUT block. Right: While the input of each SUT block is the output of the previous layer, the attention mechanism attends the halted state the timestep. When the halting probability exceeds Othresh, the hidden state is simply copied. Finally, the halted state is used as the output of the SUT.
Specifically, we use the unsupervised version pro- posed by Shen et al. (2023) that assumes uniform distribution over all tokens and layers, resulting in the following auxiliary objective. In the SUT setting, the gating network is used | L T times, where L is the number of layers, and T is the number of timesteps.
Algorithm timestep
Halting mechanism given
for
to d. 10
Σ F= ag Othoc then
(t) halt(b(2)
1_1
(0) 42
1=1
Intuitively, the entropy term increases the en- tropy of the marginal probability of the gating net- work predictions, which at its maximum means that the weight for each gating network across the entire minibatch is uniform. The conditional entropy term decreases the conditional entropy. which causes the prediction of the gating network to be sharp, and also penalizes the uniform distribution solution for the gating network.
a
( Attention
S
h
FeodForward(1
8
E
+ E
else
h (0)
h
end 8
end for
3.2 Stick-breaking Dynamic Halting
a function which is implemented by an MLP that takes in the previous layer's embedding. Then, the probability of any layer halting is computed by
There have been several methods for imbuing models with the ability to make a prediction with- out having to use all layers of the model (Graves, 2016; Tan and Sim, 2016; Dehghani et al., 2018; Elbayad et al., 2019; Schuster et al., 2022). Moti- vations for this include: (1) different inputs require different amounts of iteration make prediction, (2) reducing computation cost.
1-1
a
1
II P=1
(2)
similar formulation described in Graves (2016) and Tan and Sim (2016). Algorithm shows how the mechanism is implemented at any given timestep. h, is the output of the previous layer for the current timestep.
UT implements a similar mechanism, but the UT version of halting is difficult to interpret. Here we choose principled version of the dynamic halting mechanism based on the breck-breaking process, viewing it as probability distribution. First, a are the halting probabilities predicted by halt (1)
computing h (f) time-step must not have halted before or at
Conditioned on the fact that
I 1. So we can use h the unhalted state, as

---

input to the computation of the attention query of the block. However, since time-step & can attend to all other timesteps, and it these other steps may have halted, we use the halted states S for the previous layers.
Table 1: BLEU score on WMT14 En-De translation datasets. MACs (Mutiply-Accummulat Operations) measures the computational complexity of each model. VVaswani al. (2017). "Liu al. (2020). Peng al. (2020), ZZhagg al. (2022), *Dehghani al. (2018), 18), Myle et al. (2018), WW et al. (2018)
However, because the halting is a 'soft' decision, we can relax the requirement for evaluating all pos- sible halted states and use the expected halted state substitute. Previous halting mechanisms use "gating' mechanism of convex sums between pre- viously gated outputs and the current step's output by = 0q h + (1 - ax) h (Dehghani et al., 2018). This can lead to vanishingly small gradients going up the layers as (1 ay) multiplies. We can
Model
#Params
BLEU
MACs'
Transformer base
65M
27.3
604M
Admin 6L-6L*
61M
27.7
604M
MAR-7
63M
28.4
MoA base
65M
28.4
628M
UT
65M
28.9
UT base + SB halting
64M
29.3
1998M
SUT base
66M
29.2
787M
Transformer big/
210M
29.3
2090M
instead compute the expected halted embedding at any 1,
LightConv
202M
28.9
1750M
DynamicCony
213M
29.7
1790M²
Admin 181.-181.
151M
29.0
1490M
Admin 601.-121.
256M
30.1
2550M
1
1
(1)
(1) h
MoA big"
200M
29.4
1220M
s
h
(3)
UT + SB halting SUT big
105M
29.6
3707M
110M
29.4
787M
previous layer if not halted
halted
Table 2: Ablation Study. MIM loss" means replacing the MIM loss with the load balancing loss used in (Fedus et al., 2021). "- MoMHA" means replacing MoMHA with the MoA introduced in (Zhang et al., 2022).
If a," - for some I, s/" - h1" recovering the behavior of the discrete halting decision. We use s) as input to the attention key and value transformations.
Model
Valid loss
BLEU
Paramms
This probabilistic interpretation also allows us to impose a loss on the expected number of layers used at each step, biasing the model towards fewer iterations, thereby saving computational cost.
SUT base
2.192
29.2
66M
MIM loss
2.221
28.9
66M
MoMHA
2.232
28.7
66M
ACT loss
2.217
29.0
66M
halting
2.219
29.1
65M
T
(t) ai
LACT
(4)
properties. To further analyze the behaviour of the model under compositional generalization settings, test model the Logical inference task from (Bowman al., 2015). All experiments were implemented within the Fairseq framework (Ott et al., 2019) 2
1=1
We use a threshold Othresh 0.999, such that the cumulative sum of the halting probabilitics has exceeded this, no computation will be performed for that time step, and the previous layer's 's embed- dings will be copied. Due to the routing operation required in the implementation fo SMoEs, we can simply route halted states "No Op" expert, leading to real savings in computation cost when halting hits the threshold early. We find that ad- justing this threshold after training can maintain performance while saving computation steps.
4.1 English to German Translation
We perform experiments on the WMT' 14 English- German translation dataset (Bojar al., 2014). We use the pre-processing from Liu al. (2020). We use joined dictionary and share all word embed- dings of the encoder and decoder. For evaluation, we average the last 5 best models according to their negative log-likelihood scores. We report the BLEU scores (Papineni al., 2002), and also port the MACs (MultipyyAAcummulte Operations) to evaluate the runtime computational costs of the
4 Experiments
First, we show that we can scale the UT with SUT the WMT' 14 English-German (Bojar et al., 2014) translation task. We then ran experiments on Compositional Freebase Questions (CFQ; Keysers et al. 2019) to test for compositional generalization
Fairseq-hasee implementation available on: https:// gi thub. com/ https/sawwnnns/eeeeee sut

---

Table FFD Expert- Word co-occurrences.
modularity can result in more robust generalization.
Exp.
6
17
41
46
a
he
ed
team
4.2
Compositional Freebase Questions
Top 5
their
they
ing children
his
his
ted police
We run experiments on the Compositional Freebase Questions (CFQ; Keysers et al. 2019) dataset to de- termine the compositional generalization abilities of the SUT. This is a translation task from natu- ral language to SPARQL query. As example, the sequence Who wrote M1 and wrote film would be translated the target sequence SELECT DISTINCT ?x0 WHERE { ?x0 a people.person ?x0 film. won.wwiierr.. film ?x1 film. film }. CFQ tests for compositional gener- alization using the notion of compound divergence, which measures how different the training set and test set are in terms of combinations of tokens, which they refer to compounds. To our knowl- edge, the current rest-performing models either finetune pretrained language model or, use knowl- edge about the task to design a suitable prompt for a large language model (Drozdov et al., 2022). While the prompting approach is extremely effective at the CFQ task, we view the task as benchmark for compositional generalization in general and should be viewed in concert with other experiments, es- pecially real-world data (like translation). When using domain knowledge of the task in the prompt. the results may indicate better performance with a specific approach for CFQ (and perhaps other SQL translation tasks) but might be difficult to extrapo- late to other settings.
this
He y deviees
an
you red system
Det. Pronouns
Suffixes
Nouns
different models. MACs of previous models were computed in Zhang et al. (2022).
The results are reported Table 1. We compare against strong baselines while accounting for the number of parameters in these models. In addition, we train two UTs by setting E = k = 1, and parameterizing the FFD and Attention layers with parameters to match our ~6MM, and ~ 10M set- ting for SUT. The SUTs and UTs both demonstrate good parameter efficiency when compared pre- vious models. the 10M parameter class, SUT and UT perform at around 29.4 and 29.6 BLEU re- spectively, while previous models require 2000 parameters. While the SUT does not perform as well as the UT, but the computations required dur- ing runtime could be as low as one-fifth of UT. Also, because MACs stays constant SUT scales up.
?x1 a
keep k constant for SUT, the
We ran experiments removing different aspects of the model and its training process, including: MIM auxiliary loss, Mixture of MHA, the ACT loss, and the halting mechanism. The results in Table 2. The introduction of multiple heads to the MoA was crucial in seeing performance gains on this task, as well as having the MIM loss as a load-balancing auxiliary objective. Interestingly, halting does contribute as much of a performance gain as it does in CFQ.
In our experiments, we use preprocessing scripts from Zheng and Lapata (2021). The scripts per- form preprocessing to the target sequence that simplifies the target sequence the same way per- formed in Furrer et al. (2020). Accordingly, we train baseline Transformer on the transformed target. We performed search on the SUT hyper- parameters, using the MCD1 validation set, and the best perforrerf set of parameters are Attention (E = 1, = = 8, D = 64, = 1) and FFD = 1024). which corresponds
Additionally, we compute the top 5 tokens that occur in conjunction with each expert, regardless of layers, and find that certain associations exist. We pick several experts Table 3 that show a clear sign of co-occurring with tokens that seem to show a pattern. This suggests that while there may be redundancy between the experts, groups of experts specialize certain tasks, resulting in some modularity. Future work can investigate if such
(E = 1, to the UT setting. Refer to Appendix A for fur- ther details. Since CFQ is relatively small task, larger scale is not a factor and might suggest that expert specialization may not be as helpful. The results are shown in Table 4. In cases with and without halting, the model already outperforms pre- vious benchmarks, including the UT baseline from Bergen et al. (2021). For a fairer comparison, we use the same hyperparameters as our UT imple-
'The appnnsooure PTFLOPS petttss///t http//gttthbhccoo com/ covrasov/flops-com pytorch) used calculate the MACs.
"The MACs values of DynamicConv and LightConv are underestimated. Because the PTFLOPS does not support the customized convolution layers.

---

Table 4: CFQ Results. Results on UT are an average runs on diffcrent seeds.
Model
Pretraining
MCD1
MCD2
MCD3
Avg.
MACs
T5-hased UT (Bergen et al., 2021)
X
42.7
9.5
11.6
21.3
1154M
Edge Transformer (Bergen al., 2021)
X
47.7
13.1
13.2
24.7
6504M
Transformer (Keysers et al., 2019)
X
42.5
11.2
10.6
21.4
1154M
TS (Furrer et al., 2020)
61.6
31.3
33.3
42.1
1154M
Roberta (Zheng and Lapata, 2021)
60.6
33.6
36.0
43.4
1660M
Dangle (Zheng and Lapata, 2021)
/
78.3
59.5
60.4
66.1
51033M
TS-based UT (ours)
X
68.3 + 2.9
43.1 4: 1.5
45.7 + 1.8
52.3 1: 1.6
441M
UT w/o halting
X
71.0 + 3.5
48.6 2.3
51.3 0.2
56.9 +
654M
UT with halting
X
72.4 + 3.5
51.1 + 1.8
51.7 51.7
58.4 + 1.2 654M
Table 5: Test accuracy of the models, trained on op- eration lengths of I 6, with their out-of-distribun results shown here (lengths 7-12). LSTM baseline from Bowman et al. (2015), and Transformer baseline from Shen et al. (2019)
then 81 C 82. The crux of the task is in training the model sequences that have 0-6 logical op- erators and evaluating it on sequences that have 7-12 operators. Given our sequence-to-sequeece setting, we convert the task into a translation task. The model takes sentence1 #SEP# sentence2 as its source sentence, with the target sentence being the singlc-token label for that pair.
Model
Number of Operations
Comp, Gen. C
7
8
10
11
12
A
LSTM
88
84
80
78
71
69
80
60
59
Transformer
51
52
51
51
51
48
53
51
51
We train a 12 layer model with Attention (E 12, k: = H = 2, D = 32, W = 1) and FFD (E - 12, K = 4, = 128) and halting. Refer to Appendix A for further details. Training 12- layer Vanilla Transformer achieves approximately the same results in Shen et al. (2019), we report their results. Our results in Table 5 confirm the findings of Tran et al. (2018), showing that with recurrence in SUTs, we are able to generalize to longer sequences of the task. While there are other models that induce a tree structure that performs exceedingly well on the task, we wanted to evaluate our model against other popular architectures. The LSTM is strong baseline, and we find that UT outperforms it in generalization. We also evaluate UTs on the compositional generalization splits proposed (Shen al., 2019), where the splits A, B, and are in increasing difficulty. The results show that UTs are able to generalize better for the A and B splits, outperforming the LSTM and VT. Split C is still presents challenge for the Transformer variants.
SUT
98
97
94
90
88
81
97
94
52
mentation, we modify our UT implementation to be more similar to the T5-based UT in Bergen et al. (2021). These changes include: the bucketed rela- tive position bias used by T5, and going from post layer-norm pre layer-norm. While this results in much improved results compared the original paper, our implementation of UT still outperforms it.
The Dangle (Zheng and Lapata, 2021) model, which beats model, also requires re-running the encoder for every token decoded. This is expensive process, but given that both our method and Dangle perform well at this task, is additional evidence that itcrative processes are beneficial for compositional generalization.
4.3 Logical Inference
We use the logical inference task from (Bowman et al., 2015) as test bench for UT. Despite the apparent simplicity of the language, the task inher- ently requires the model to learn the hicrarchical structure of the problem. Each instance of the task comprises of two logical statements, and the goal is predict if the statements are equivalent, con- tradictory, disjoint, or entail in either direction. For example, given 8 = a and $2 = ( or b )
Additionally, we compute the average halting depth for the test data segmented by operator counts. Because more operators require more nest- ing of expressions in the sequences, more recur- sion is required to properly parse the sequence. As expected, in Figure 4, the average halting depth increases as more operators are used. The operator count for these clauses are correlated with length,

---

Average dynamic halting step
10
6-
8
10
12
Number of operators
Figure 4: The average dynamic halting depth of the UT model as the number of operators increases in the test
set. The model learns to think more when the problem is harder.
or
*#SEP a
( and

>
Logica Inference Accuracy with 12 Ops.
Percentage steps computed
1.0
which suggests that SUTs may be suited to gener- alize for length. We include further experiments length generalization in the Appendix Table 8.
0.8
0.6
0.4
4.4 Post-training Computation Reduction
0.2
Does lowering Orhhreh after training cause the model to halt earlier, saving computation? How much would that cost us in terms of accuracy?
0.0
0.2
0.4
0.3
Ochresh
We estimate the skipped SUT block com- putations given different values Othresh C (0.1,0.2, 0.9) by looking at the halting pat- terns of the decoder given the ground truth source- target pairs. We pass the source-target pair into the model and analyze the halting patterns of the model, giving rough estimate of how much computation would be saved percentage of computing all layers of the SUT.
Figure S: Above: ol ap for an example Logical Inference input r-aiii: timesteps, y-axis: layers. This visualizes the halting pattern of the model: dark blue represents halted, while yellow represents active. Below: Efficiency Performance tradeoff curves when Othresh is adjusted.
is possible since halting earlier will result in dif- Logical Inference We observe the resulting per- formance the hardest split of the test set with 12 operations. Due to the already saturated halting pattern, the halting probability ay spikes rapidly from close to 0 to higher values, resulting a near constant ~ 50% reduction the computation time regardless of the threshold.
ferent embeddings, and result in different halting decisions in other timesteps. Overall, the results suggest that computation steps without any drop in accuracy, and about ~500 for 0.2% decrease.
save about 20% of the SUT
English-German Translation For this larger dataset, we find that these translation models halt much later, suggesting that the translation task re- quires more computational steps than the 6-layer SUT we used. However, further increasing the number of layers to 12 layers does not bring about much benefit, as evidenced by the halting in Figure 4, which is an example of the halting mechanism using nearly all layers. For comparison, Admin 60L-12L model, requires 60-layer encoder achieve its performance. Even when Othresh 1. the skipped computation steps remain at about 33%, compared to 80% in the CFQ task. We find that we can reduce the computation by 9% while still
CFQ Using the MCDI test split of the dataset, and our best-performing model on MCD1, we per- form the Othresh adjustment. The halting patterns reflect the repeated structure of SQL, using fewer steps for and 'WHERE', while the main bulk of the region within {...) requires more SUT steps before halting. Surprisingly, when 0.8 Othresh < 0.999, the accuracy remains fairly constant. An es- timated 33% of the computation steps were skipped at Cthresh = 0.8. At athresh = 0.1, there a slight increase in the number of computed steps, which

---

10
2-
SELECT
vount
WHERE
proppee persoon unteenality
MO
Dlg
During
presentation
the
Welf
seemed
impressed
by the
educational
pilot project
</67
Percentage of SUT steps computed
Percentage SUT steps computed
1.0
1.0
30
Accuracy on CFQ MCD1
1.0
29
0.8
0.8
0.6
0.6
0.6
27
26
0.4
0.2
0.2
0.2
0.0
0.0
23
0.2
0.6
0.2
0.4
0.6
0.8
Ditreshh
Figure 6: Halting plot and trade-off curves for CFQ. (See Figure for description)
Figure Halting plot and trade-off curves for English- German Translation. (See Figure 5 for description)
retaining BLEU score of 2..1.
to ascertain viability in large scale systems. Other issues may also crop up in the further scaling of SUTs, but we believe there is ample literature draw on to finding solutions these problems.
5 Conclusion
We show that it is possible to scale up the UT via SUTs, and SUTs outperforms models of the same capacity in the WMT' 14 English-to-German translation task. The recursive nature of both UTs and SUTs allows for better inductive biases, which we have demonstrated in synthetic tasks like CFQ and logical inference. VTs have been shown to be poor at these compositional generalization tasks without additional domain knowledge. The stick-breaking dynamic halting mechanism also al- lows post-traiming adjustment of computation cost, which is boon for deployment at scale.
References
Leon Bergen, Timothy O' O'Donnell, and Dzmitry Bah- danau. 2021. Systematic generalization with edge transformers. Advances in Neural Information Pro- cessing Systems, 34:1390-1402. 1402.
Ondřej Bojar, Christian Buck, Christian Federmann. Barry Haddow, Philipp Koehn, Johannes Leveling. Christof Monz, Pavel Pecina, Matt Post, Herve Saint- Amand, et al. 2014. Findings of the 2014 workshop statistical machine translation. In Proceedings of the ninth workshop on statistical machine translation, pages 12-58.
Limitations While the experiments in this pa- per show the desirable generalization properties of UTs, there some aspects of compositional generalization that SUTs do not solve. Importantly, while we demonstrate scaling UTs up via SMoEs, further experiments on larger settings are needed
Samuel R Bowman, Christopher D Manning, and Christopher Potts. 2015. Stre-structured composi- tion neural networks without rre-sttrctured archi- tectures. arXiv preprint a5Xiv: 04834.
Zitian Chen, Yikang Shen, Mingyu Ding, Zhenfang

---

Chen, Hengshuang Zhao, Erik Learned-Mllle and Chuang Gan. 2022. Mod-squad: Designing mix- ture of experts modular multi-task learners. arXiv preprint wwXiv:2212.80066
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. 2020. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795.
Kenneth Church and Patrick Hanks. 1990. Word associ- ation norms, mutual information, and lexicography. Computational linguistics, 16(1):22-25
Lukasz Kaiser and llya Sutskever. 2015. Neural gpus Iearn algorithms. arXiv preprint arXiv:1511.0822
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford. Jeffrey Wu, and Dario Amodei. 2020. Scaling laws for neural language models. arXiv preprint arXiv:2011.0836)
Róbert Csordás, Kazuki Irie, and Jürgen Schmidhu- ber. 2021. The devil is in the detail: Simple tricks improve systematic generalization of transformers. arXiv preprint arXiv:2108. 12284.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Fukasz Kaiser, 2018. Universal transfommers, arXiv preprint arXiv: 038999
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov. Lukasz Stafiniak, Tibor Tihon, et al. 2019. Measuring com- positional generalization: A comprehensive method on realistic data. arXiv preprint arXiv:
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Mar- cus Hutter, Shane Legg, and Pedro A Ortega. 2022. Neural networks and the chomsky hierarchy. arXiv preprint arXiv:200700000
Yoon Kim. 2021. Sequence-to--equueeee learning with latent neural grammars. Advances in Neural Infor- mation Processing Systems, 0022262222231111
Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. 2022. Compositional semantic parsing with large language models. arXiv preprint Xrx: 15003.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2019. Albert: lite bert for self-supervised learn- ing of language representations. arXiv preprint 1rXiv:199..11944
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D Hwang, et al. 2023. Faith and fate: Limits of transformers on com- positionality. arXiv preprint ar35v:2305. 18654.
Yuanpeng Li, Liang Zhao, Jianyu Wang, and Joel Hest- ness. 2019, Compositional generalization for primi- tive substitutions. arXiv preprint arXiv: (KKV::/900006122
Bingbin Liu, Jordan Ash, Surbhi Goel, Akshay Kr- ishnamurthy, and Cyril Zhang. 2022. Transform- ers learn shorteuts automata. arXiv preprint 1xXi:2220.110449
Maha Elbayad. Jiatao Gu, Edouard Grave, and Michael Auli. 2019. Depth-adaptive transformer. arXiv preprint arXiv: 10073.
William Fedus, Barret Zoph, and Noam Shazeer. 2021, Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity.
Xiaodong Liu, Kevin Duh, Liyuan Liu, and Jianfeng Gao. 2020. Very deep transformers for neural ma- chine translation. arXiv preprint arXiv:2008.0777
Daniel Furrer, Mare Zee, Nathan Scales, and Nathanael Schärli. 2020. Compositional generaliza- tion in semantic parsing: Pre-training vs. specialized architectures. arXtv preprint arXh::2007.08970.
William Merrill, Ashish Sabharwal, and Noah A Smith. 2022. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843-856
Alex Graves. 2016. For recurrent neural networks. arXiv preprint arXiv:1603.08983.
Adaptive computation time
Out Myle, Edunov Sergey, Grangier David, Auli Michael, al. 2018. Scaling neural machine transla- tion. WMT, pages 1-9.
Michael Hahn. 2020. Theoretical limitations of self- attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 8:156 171.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019. fairseq: A fast, extensible toolkit for quence modeling. arXiv preprint arXiv: 7 1904.01038.
Yiding Hao, Dana Angluin, and Robert Frank. 2022. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Trans- actions of the Association for Computational Linguis- fics, 10:800-810.
Kishore Papineni. Salim Roukos, Todd Ward, and Wei- Jing 7hu. 2002. Bleu: a method for automatic evalu- ation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computa- tional Linguistics, pages 311-33111 111318.

---

Hao Peng, Roy Schwartz, Dianqi Li, and Noah Smith. 2020. A mixture of h-1 heads better than heads. In Proceedings of the 58th Annual Meeting of the As- sociation for Computational Linguistics, pages 6566- 6577.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang. Sebastian Ruder, and Donald Metzler. 2020. Long range arena: benchmark for efficient transformers. arXiv preprinl arXiv:201..04006.
Jake Russin, Jason Jo, Randall C O' O'Reilly, and Yoshua Bengio. 2019. Compositional generalization deep seq2seq model by separating syntax and seman- tics. arXiv preprini arXiv: 1904.09708.
Ke Tran, Arianna Bisazza, and Christof Monz. 2018. The importance of being recurrent for modeling hier- archical structure. arXiv preprint I8X.v 000..0033.03000 03550.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances neural information processing systems, 30.
Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Q Tran, Yi Tay, and Donald Metzler. 2022. Confident adaptive language modeling. arXiv preprint wxx.v:2207.0055 007067.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe Le. Geoffrey Hinton, and Jeff Dean. 2017. Outrageously large neural networks: The sparsely-gated mixture-of-expers layer. arXiv preprint 1ex.v:1701.06550
Felix Wu, Angela Fan, Alexei Baevski, Yann Dauphin, and Michael Auli. 2018. Pay less attention with lightweight and dynamic convolutions. In Interna- tional Conference on Learning Representations.
Xiaofeng Zhang, Yikang Shen, Zeyu Huang, Jie Zhou, Wenge Rong, and Zhang Xiong. 2022. Mixture of attention heads: Selecting attention heads per token. arXiv e-prints, pages arXiv-2210.
Yikang Shen, Shawn Tan, Arian Hosseini, Zhouhan Lin, Alessandro Sordoni, and Aaron Courville. 2019. Ordered memory. Advances in Neural Information Processing Systems, 32.
Hao Zheng and Mirella Lapata. 2021. Disentangled sequence sequence learning for compositional gen- eralization. arXiv preprint arXiv:21
Yikang Shen, Zheyu Zhang, Tianyou Cao, Shawn Tan, Zhenfang Chen, and Chuang Gan. 2023. Moduleformer: Learning modular large language models from uncurated data. arXiv preprint arXiv:2306.04640
Vsevolod Sourkov. 2018.
Igloo: Slicing the fea- tures space to represent sequences. arXiv preprint arXiv:1807.03402.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zhigniew Wojna. 2016. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818-2826.
Sho Takase and Shun Kiyono. 2021. Lessons on pa- rameter sharing across layers transformers. arXiv prepriat (xXv:2104400022.
Shawn Tan, Yikang Shen, Timothy O'Donnell, Alessandro Sordoni, and Aaron Courville. 2020. Re- cursive top-down production sentence generation with latent trees. arXiv preprint arXiv:2010.04704
Shawn Tan and Khe Chai Sim. 2016. Towards implicit complexity control using variable-depth deep neural networks for automatic speech recognition. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5965-5969. IEE..
Yi Tay, Mostafa Dehghani, Samira Abnar, Hyung Won Chung, William Fedus, Jinfeng Rao. Sharan Narang. Vinh Q Tran, Dani Yogatama, and Donald Metzler. 2022. Scaling laws vs model architectures: How does inductive bias influence scaling? arXiv preprint arXiv:2207.105511 10551..


Reviews:
[{"review_id": "BUS8eF5p2F", "reviewer": "Reviewer_T1no", "summary": "", "questions": "A) The paper does not provide standard errors its measurements. It is therefore not clear which of the reported differences are real. This is particularly an issue for the ablation results, where many of the differences are small.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your in-depth review of our paper! \n\n> One of the paper's central claims is that SUT improves compositional generalization. However, the paper does not evaluate on most of the major datasets in this area (COGS, SCAN, PCFG). This would be necessary to make a convincing case for improved generalization.\n\nBy your recommendation, we ran some experiments, and here are some preliminary results for SCAN and PCFG productivity & systematicity splits.\n\n\n|         Task         |      Vanilla Transformer     | Vanilla Transformer (ours) | UT (SUT 1 expert) |\n|----------------------|------------------------------|----------------------------|-------------------|\n| SCAN (add_turn_left) | 99.6% (Furrer et. al., 2020) |                        20% |              100% |\n| SCAN (add_jump)      | 1% (Furrer et. al., 2020)    |                       7.3% |                0% |\n| SCAN (length)        | 0% (Furrer et. al., 2020)    |                         0% |                7% |\n| PCFG (systematicity) | 72% (Hupkes et. al., 2019)   |                        76% |               87% |\n| PCFG (productivity)  | 52% (Hupkes et. al., 2019)   |                        56% |               62% |\n\n\nIn all cases, we ran a baseline Vanilla Transformer (VT) model using the IWSLT Transformer model from fairseq, and compared with a relevant VT baseline from the literature.\nWe were unable to replicate the `add_turn_left` result in Furrer et. al. on SCAN, and found that our VT results on the PCFG splits were slightly higher.\n\n\nThese results show that there are nuances to compositional generalisation. While the SUT can bring consistent benefits in the case of PCFG, the harder generalisation aspects of `add_jump` and `length` in SCAN may require a different kind of generalisation.\nTo our knowledge, there is work that deals explicitly with the `add_jump` ([Russin et. al., 2019](https://aclanthology.org/D19-1438.pdf), [Li et. al., 2019](https://aclanthology.org/D19-1438.pdf)) and others that deal with the `length` split by decoding in a tree structure ([Tan et. al. 2020](https://aclanthology.org/2020.findings-emnlp.208.pdf), [Yoon, 2021](https://arxiv.org/abs/2109.01135)).\nSUT tackles some of these aspects of compositional generalisation, but not all, and this is a good illustration of its strengths and weaknesses, and we will add this to the paper. Thank you for the suggestion.\n\nWe also have Long-range Arena ListOps results in the appendix, where we also achieve good long-range performance.\n\n> The only natural dataset that the paper evaluates on is WMT'14. It is therefore unclear how the architecture would perform on natural data. Language modeling could be interesting, or some reasoning tasks given the paper's emphasis, though those tasks would require pretraining.\n\nWe are currently working towards large language modeling pre-training with the SUT.\n\n>Despite discussing scaling, the paper does not estimate scaling laws for the architecture. There have been many Transformer alternatives proposed in the literature, which have been found to have worse scaling behavior than Transformers (Tay et al., Scaling Laws vs Model Architectures: How does Inductive Bias Influence Scaling?). It seems important to know whether SUT falls into this group. This should be feasible since scaling laws can be accurately estimated from sub-billion parameter models.\n\nWe believe that estimating scaling laws requires a more diverse set of tasks at many different scales.\nHowever, we specifically targeted issues with scaling UTs by introducing sparsity into the UT block. In the appendix of Kaplan et. al., 2020 (Page 24, Figure 17), the authors do note that the universal transformer has better scaling properties in terms of parameter efficiency, but when compared in terms of computation, it performs worse. Scaling Laws vs Model Architectures (Tay et. al., 2022, Appendix 4.1) mentions the same difficulty with scaling UTs, stating: \"we found that even with an increase of FLOPS, this does not lead to improved performance\".\nWe do provide an explanation in our paper for this (Figure 1), namely that attempting to reach parameter equivalence with a VT for a standard UT will incur a quadratic scaling relathionship.\nSparsifying the UT directly tackles the issue.\n\n\n> The model for CFQ uses only a single expert, in which case it reduces to a normal Universal Transformer. This does not provide evidence for SUT.\n\nCFQ is a small task that is not knowledge-intensive, and thus requires a smaller model overall, which requires far fewer experts.\nThe model used in the CFQ task is a special instantiation of the SUT with $E=1$, after performing a hyperparameter search on MCD1 and its validation set.\nUltimately, the issue of overfitting with higher parameters still plays a part in the final result.\n\nWe also wanted to demonstrate that the UT setting (along with the other additions we introduced in this paper) still confers some compositional generalisation properties.\n\n> It is also strange that SUT outperforms Universal Transformer in this setting.\n\nThe \"Universal Transformer\" setting varies slightly from paper to paper. In several cases, as in Bergen et. al. 2021, authors will refer to a model as a Universal Transformer when the weights of a given Transformer architecture are tied across layers. However, we find that certain architecture choices do affect performance on CFQ:\nIn the case of T5,\n1. The choice of pre-LayerNorm over post-LayerNorm, (we believe this affects gradient propagation in a recurrent model),\n2. The type of positional embeddings used (T5 uses binned positional biases instead of an embedding),\n3. The size of the model (the Bergen et. al. 2021 model is much larger),\n\nWe attempt to account for these discrepancies in our T5-based UT baseline and reported those results, which fared much closer to our variant of UT.\nWe have mentioned this in the paper but will elaborate further to clarify the point. \n\n> A) The paper does not provide standard errors its measurements. It is therefore not clear which of the reported differences are real. This is particularly an issue for the ablation results, where many of the differences are small.\n\n\nWe agree and other reviewers have also suggested this. We are presently running these additional runs for WMT'14 En-De to provide these error bars.\nWe provide these standard errors for the CFQ tasks, where we report the average of 5 runs, but follow the Zheng and Lapata, 2021 format by reporting the average only. \n\n| Model              | MCD1            | MCD2           | MCD3           |\n|--------------------|-----------------|----------------|----------------|\n| T5-based UT (ours) | 68.3 $\\pm$ 2.9  | 43.1 $\\pm$ 1.5 | 45.7 $\\pm$ 1.8 |\n| UT w/o halting     | 71.0 $\\pm$ 3.5  | 48.6 $\\pm$ 2.3 | 51.3 $\\pm$ 0.2 |\n| UT with halting    | 72.4 $\\pm$ 3.5  | 51.1 $\\pm$ 1.8 | 51.7 $\\pm$ 2.3 |\n\nWe hope the additional results and explanations have addressed your concerns, and also hope you will reconsider the score for the soundness of our paper. Thank you!", "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": "I am excited about this paper. The architecture is technically sound and well motivated. The paper finds a solution to a real problem for Universal Transformers, which is poor scaling of compute with parameter count. The proposal is the obvious-in-retrospect solution to this problem, which is a strength given the proposal's novelty in the literature.\n\nThe paper is well written, and clearly communicates the details of the architecture, the experiments, and their implications.", "reasons_to_reject": "The experimental evaluation is thin and not fully convincing. Given the \"obviousness\" of the architecture (this is not meant pejoratively, rather it is sufficiently natural that other researchers are likely to think of it), I would support publication of the paper regardless of whether SUT is in fact stronger than Transformers or Universal Transformers in any meaningful way. Even if the result is negative, this will save future researchers a great deal of wasted effort. However, I would not recommend publication in its current state. What I would find sufficient is a convincing demonstration of the model's strengths and weaknesses, whatever they are.\n\n- One of the paper's central claims is that SUT improves compositional generalization. However, the paper does not evaluate on most of the major datasets in this area (COGS, SCAN, PCFG). This would be necessary to make a convincing case for improved generalization.\n\n- The only natural dataset that the paper evaluates on is WMT'14. It is therefore unclear how the architecture would perform on natural data. Language modeling could be interesting, or some reasoning tasks given the paper's emphasis, though those tasks would require pretraining.\n\n- Despite discussing scaling, the paper does not estimate scaling laws for the architecture. There have been many Transformer alternatives proposed in the literature, which have been found to have worse scaling behavior than Transformers (Tay et al., Scaling Laws vs Model Architectures: How does Inductive Bias Influence Scaling?). It seems important to know whether SUT falls into this group. This should be feasible since scaling laws can be accurately estimated from sub-billion parameter models. \n\n- The model for CFQ uses only a single expert, in which case it reduces to a normal Universal Transformer. This does not provide evidence for SUT. It is also strange that SUT outperforms Universal Transformer in this setting.", "questions_to_authors": "A) The paper does not provide standard errors its measurements. It is therefore not clear which of the reported differences are real. This is particularly an issue for the ablation results, where many of the differences are small.", "paper_topic_and_main_contributions": "The paper introduces a new architecture, Sparse Universal Transformer, which is MoE applied to Universal Transformer. The architecture achieves three desirable properties which previously had not been achieved simultaneously: the recurrence of Universal Transformer (using weight tying), high capacity of Transformer, and compute efficiency of Transformer. The architecture is evaluated on three tasks: WMT'14 and two benchmarks for compositional generalization, CFQ and Logical Inference. The paper finds comparable or stronger performance for SUT compared to Transformer and Universal Transformer baselines. The paper also conducts some ablation experiments on specific parts of the architecture.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jQEWsc4nB0", "reviewer": "Reviewer_EnEq", "summary": "", "questions": "A. 288: What is $g(e)$?\n\nB. Do the computational savings for SMoE only apply to inference, not training?\n\nC. Tab 3: This is a cool result. How much cherry-picking did you have to do to get lists like these? Are there lots of obvious groupings like this, or are most of the experts uninterpretable?\n\nD. Tab 4: What is the metric being used here? Is higher or lower better?\n\nE. Tab 4: Are all UT models sparse in this table?\n\nF. Tab 5: What is the metric here?\n\nG. Why is it called \"stick-breaking\"?\n\nH. Tab 4: Is \"UT with halting\" your full SUT model?\n", "limitations": "", "rating": 4, "confidence": 3, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review of our paper. \n\n> In Table 1, the bottom half seems to support the authors' story, whereas the top half does not. For the ~66M tier, SUT has slightly higher BLEU than the baselines, but it also has more params and MACs. I'm not sure what conclusions to draw from this, if any, and I would appreciate more discussion of this by the authors.\n\nMany of the hyperparameters used in our models were derived from the settings used in the Mixture of Attention Heads (Zhang et. al., 2022) paper, with two additions:\n1. Increasing the number of experts since there was only one Transformer block now, and\n2. An MLP router router for both the Attention and the MLP module in the Transformer block.\n\nThese additions lead to one more router computation for every iteration performed by the SUT (higher MACs), and a wider output layer for the router due to the extra experts and additional router (overhead in the number of parameters).\n\nWe now have results on a smaller model: 43M parameters, 28.4 BLEU, and on plotting these three settings (BLEU vs. Parameter count), we find that the SUT models form a Pareto front for the existing methods within the same parameter count.\nWe hope this addresses your biggest concern, we will include this plot in the paper.\n\n\n> In Tab 1 and Tab 2, a lot of the BLEU scores are very close, so it would be helpful to see std devs or significance testing. Otherwise, it's a bit hard to be confident in some of these results.\n\nWe agree and other reviewers have also suggested this.  We are presently running these additional runs to provide these error bars. \nHowever, we would like to point out that our goal is to show that SUT can reach comparable results while using fewer parameters and computation costs.\n\n\n\n> A. 288: What is g(e)?\n\nWe apologise for the confusion. This is the marginal probability of the experts over all the routing probabilities, and we assume a uniform probability over all time-steps:\n$$g(e) = \\frac{1}{|\\mathcal{X}|} \\sum_{\\mathbf{h} \\in \\mathcal{X}} g(e|\\mathbf{h}) $$\nWe will include this definition in the paper. \n\n> B. Do the computational savings for SMoE only apply to inference, not training?\n\nIt is for both training and inference, this is also the case in [Shazeer et. al. 2017](https://arxiv.org/pdf/1701.06538.pdf).\n\n\n> C. Tab 3: This is a cool result. How much cherry-picking did you have to do to get lists like these? Are there lots of obvious groupings like this, or are most of the experts uninterpretable?\n\nWe took the experts that seemed to have an interesting pattern in the top 5 tokens, from among 24 experts. There were others that had an interesting mix of 2 (proper nouns and pronouns) for example. The issue is that it’s hard to evaluate what the experts have specialised in after training because at different levels of the SUT, they may be performing different operations which may not correspond to the word at that particular time-step, whereas in this particular table, we have chosen to analyse the co-occurences of expert usage and words.\n\nWe will include the full list of top words for each expert in the appendix.\n\n> D. Tab 4: What is the metric being used here? Is higher or lower better?\n> F. Tab 5: What is the metric here?\n\nWe apologise, these are Accuracy scores. In Tab. 4 they are results for a full match on the SQL target sequence, so higher is better.  In Tab. 5, the results are how many of the logical expressions were classified correctly, again, higher is better. We will make this clear in the tables. \n\n> E. Tab 4: Are all UT models sparse in this table?\n\nIn this table all UT models are dense.\n\nAs suggested in the WMT’14 En-De experiments, the results show that when we are able to use a dense UT of equivalent parameters to its SUT counterpart, the dense UT performs better, but at great computation cost.\nWe mention performing a hyperparameter search on MCD1 and its validation set, and finding that $E=1$ was the best setting for CFQ.\n\nSince CFQ is a small task and requires only a small model, the benefits of sparsity do not play a role in this experiment. However, we wanted to demonstrate that the UT setting (along with the additional updates we introduced in this paper) still confers some compositional generalisation properties.\n\n\n> G. Why is it called \"stick-breaking\"?\n\nIt is an alternative formulation of the Dirichlet process that formulates it as sampling from a series of Bernoulli random variables till success, \n\n$$\\beta_{k}=\\beta '_{k} \\prod _{i=1}^{k-1} (1 - \\beta'_i)$$\n\nwhere $\\beta'_{k} \\in (0, 1)$\n\nConsider starting with a unit-length stick and breaking off  $\\beta'_k$ portion of the the remaining length of stick. \n\n$\\beta_k$ then gives the length of the $k$-th break in relation to the original length.\nBecause of this formulation, summing up $\\beta_{k}$ approaches 1. \nFurther explanation can be found [here](https://en.wikipedia.org/wiki/Dirichlet_process#The_stick-breaking_process). \n\n> H. Tab 4: Is \"UT with halting\" your full SUT model?\n\nYes. It is a special case of the SUT model with $E=1$ (1 expert), with the halting mechanism.\n\nWe hope this addresses your concerns for the paper, and we would also like to thank you for the detailed list of typos and presentation improvements you suggested. We will make the appropriate modifications to the paper.", "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": "Overall, the paper is very well-written and well-motivated, and I consider the method to be a creative and novel combination of existing ideas. The experimental methodology appears sound throughout. The introduction and background sections are excellent at motivating the method and explaining the main ideas behind it. The breadth of the related work discussed and baselines tested against is comprehensive.\n\nI found Fig 4 to be a particularly cool result. Table 3 is also interesting.\n", "reasons_to_reject": "In Table 1, the bottom half seems to support the authors' story, whereas the top half does not. For the ~66M tier, SUT has slightly higher BLEU than the baselines, but it also has more params and MACs. I'm not sure what conclusions to draw from this, if any, and I would appreciate more discussion of this by the authors.\n\nIn Tab 1 and Tab 2, a lot of the BLEU scores are very close, so it would be helpful to see std devs or significance testing. Otherwise, it's a bit hard to be confident in some of these results.\n", "questions_to_authors": "A. 288: What is $g(e)$?\n\nB. Do the computational savings for SMoE only apply to inference, not training?\n\nC. Tab 3: This is a cool result. How much cherry-picking did you have to do to get lists like these? Are there lots of obvious groupings like this, or are most of the experts uninterpretable?\n\nD. Tab 4: What is the metric being used here? Is higher or lower better?\n\nE. Tab 4: Are all UT models sparse in this table?\n\nF. Tab 5: What is the metric here?\n\nG. Why is it called \"stick-breaking\"?\n\nH. Tab 4: Is \"UT with halting\" your full SUT model?\n", "paper_topic_and_main_contributions": "This paper proposes a more computationally efficient version of the Universal Transformer (i.e. a transformer with a variable number of layers) by applying the method of Sparse Mixture of Experts (SMoE) to the feedforward and multi-head attention mechanisms. SMoE allows the model to evaluate only $k$ of $E$ submodules in a network, where $k < E$, saving computation. The authors also propose a simpler dynamic halting mechanism than the one used in the original Universal Transformer. They call their model Sparse Universal Transformer (SUT).\n\nThe main experimental results are:\n1. MT experiments on WMT 14 English-German. In some cases, SUT has better translation quality, lower computational cost, and fewer parameters than baseline models.\n2. Experiments on the Compositional Freebase Questions task, meant to test compositional generalization. SUT does better than all previous baselines, except one that uses a pretrained LM.\n3. Experiments on the logical inference task of Bowman et al. (2015), where the test set includes out-of-distribution/longer examples. SUT outperforms baseline LSTMs and Transformers, except on a difficult subset of the test set where LSTMs are still best. Fig 4 shows that the number of layers SUT uses increases with the number of operators in the example, as expected.\n4. Analysis of the tradeoff between stopping computation early and performance, for multiple tasks.\n\nIn summary, this paper proposes a new Universal Transformer architecture, SUT, that outperforms a wide range of baselines on multiple tasks, including ones that test compositional generalization, while decreasing computational cost compared to standard UT.\n", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "A. 209: K -> k\n\nB. 266: extra \"it\"\n\nC. 310: Use \\citet\n\nD. 338: extra \"but\"\n\nE. 369: Can you explain what this syntax means?\n\nF. 423: missing subject\n\nG. 464: Extra \"is\"\n\nH. Fig 5: Can you provide a legend for the heatmap colors? Maybe black and white would be simpler and easier to read.\n\nI. Fig 5: The text is too small to read.\n\nJ. Fig 5: Is this figure not referenced in the text?\n\nK. 502: Wrong quotes\n\n"}}, {"review_id": "mR0RKYs0Ta", "reviewer": "Reviewer_PDdV", "summary": "", "questions": "A. Not sure if this was addressed in the original UT paper, but how important is it to have the halting decision made per-position? How different would it be to have one global halting decision?\n\nB. Are the use of sparsity and the new halting mechanism orthogonal improvements to the model, or is there a connection between the two?\n", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your in-depth review.\n\n\n> A. Not sure if this was addressed in the original UT paper, but how important is it to have the halting decision made per-position? How different would it be to have one global halting decision?\n\nIn the cases that we’ve seen where the SUT does halt early, the tokens are usually tokens that are less important: EOS, punctuation, stop-words, etc., and uses more compute where needed.\nConsidering this, we think that if the goal of early halting is to save computation costs, then allowing the model to reduce computations on tokens where it is not necessary would help to achieve this. \n    \n> B. Are the use of sparsity and the new halting mechanism orthogonal improvements to the model, or is there a connection between the two?\n\nEach can be implemented without the other.\n    \nHowever, there is a connection between them that arises out of convenience. In order to perform the sparse expert computation, we have to route each hidden state to the associated expert. Without this, the computational savings from sparse computation cannot be realised. In doing this, we can assign halted states to a “no-op” expert, where they simply pass-through to the output, thereby allowing the computation savings on halted states.\n\nThe alternative without this specific implementation detail would be to evaluate each hidden state through all the available experts, selecting the top-$k$ experts, and then replacing the halted states with the previous output, which creates a lot of redundant computation steps.\n\n\nThank you for pointing out these missing definitions, we will include these definitions in the paper. Here are their definitions to clarify things:\n\n> 229: what is \\mathcal{X}?\n\nIt is the set of all the hidden states for all timesteps at all layers.\n\n\n> 188: what’s the definition of g?\n\nThis is the marginal probability of the experts over all the routing probabilities, and we assume a uniform probability over all time-steps:\n$$g(e) = \\frac{1}{|\\mathcal{X}|} \\sum_{\\mathbf{h} \\in \\mathcal{X}} g(e|\\mathbf{h}) $$\n\n\n\n> 228: what’s the intuition for \\mathcal{L}_{MIM}?\n\nThe entropy term (Line 228) increases the entropy of the marginal probability of the router predictions, which at its maximum means that the weight for each router across the entire minibatch is uniform. \nThe conditional entropy term (Line 229) decreases the conditional entropy, which causes the prediction of the router to be sharp, and also penalises the uniform distribution solution for the router.\n\n\n> 234: what’s the router?\n\nWe apologise for the confusion. We use the term gating network and router interchangeably, and we should make sure the terminology is consistent throughout the paper. We will make sure to keep consistency. \n\n> page 4: what’s \\mathbf{s}?\n\nIt is the weighted halted state as defined by Line 280.\n\n> 275: not very clear. It might be helpful to write out the full distribution over all 2^T possible combinations of halted/not halted, and then write \\mathbf{s} as an expectation under this distribution, pointing out that the expectation can be computed efficiently.\n\nThis is a great suggestion, we will express it this way to make things clearer. \n\nWe hope we've addressed your concerns for this paper.", "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": "Halting seems to be the trickiest part of designing/implementing a Universal Transformer, and this paper presents a nicer mechanism that seems to work better. I consider this the main contribution of the paper and would even suggest changing the title of the paper.\n\nThe adaptation of previous work on SMoE to the Universal Transformer to provide a significant speedup is also a good contribution of the paper.\n", "reasons_to_reject": "Unless I am mistaken, SMoE and the MIM loss are both previous work, and the novelty in this part of the paper lies only in applying them to the Universal Transformer.\n\nThe description of the method is not clear and/or relies too much on formulations in previous papers (see below under \"Presentation Improvements\"). Some more background, at minimum definitions of all the variable names used, is needed.\n", "questions_to_authors": "A. Not sure if this was addressed in the original UT paper, but how important is it to have the halting decision made per-position? How different would it be to have one global halting decision?\n\nB. Are the use of sparsity and the new halting mechanism orthogonal improvements to the model, or is there a connection between the two?\n", "paper_topic_and_main_contributions": "This paper describes a variant of the Universal Transformer that makes a few modifications:\n\n1. Instead of the original halting condition, which halted at a given position if a certain activation exceeded a certain threshold, the paper proposes a new halting mechanism, in which the halting probabilities (\\alpha) are actually probabilities: the forward pass sums (approximately) over all possible outcomes of the halting decisions. This halting mechanism appears to be fairly helpful (+0.4 BLEU).\n\n2. Sparse mixture of experts (Shazeer et al., 2017) for both the attention (Zhang et al, 2022; Shen et al, 2023) and feedforward layers. This hurts accuracy only slightly, but makes the network several times faster.\n\n\n", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "The correct citation for Zhang et al appears to be: https://aclanthology.org/2022.emnlp-main.278/\n"}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "188: what’s the definition of g?\n\n228: what’s the intuition for \\mathcal{L}_{MIM}?\n\n229: what is \\mathcal{X}?\n\n233: following -> preceding?\n\n234: what’s the router?\n\npage 4: what’s \\mathbf{s}?\n\n275: not very clear. It might be helpful to write out the full distribution over all 2^T possible combinations of halted/not halted, and then write \\mathbf{s} as an expectation under this distribution, pointing out that the expectation can be computed efficiently.\n\n295: fo -> of"}}]

Author rebuttal:

Meta-review: The paper introduces the Sparse Universal Transformer (SUT), an innovative variant of the Universal Transformer that integrates the Sparse Mixture of Experts (SMoE) into the feedforward and multi-head attention mechanisms. This alteration offers computational efficiency and the presented dynamic halting mechanism provides a simpler approach than the original Universal Transformer. Through experiments, SUT demonstrates enhanced translation quality, improved compositional generalization, and better computational trade-offs on several benchmarks like WMT 14 English-German. However, concerns have been raised about the thoroughness of the experimental evaluation, the clarity of method descriptions, and the originality of some contributions.

Pros:

Introduction of a well-motivated and technically sound SUT architecture that amalgamates the efficiency of Transformers with the recurrence of Universal Transformers.

A more efficient dynamic halting mechanism, which not only simplifies but also improves performance.

The paper's comprehensive approach, detailing a breadth of related work and providing results against numerous baselines.

Cons:

Parts of the paper's method, especially concerning the SMoE and MIM loss, seem to rely heavily on prior work, questioning the originality of the contribution.

Insufficient evaluation on some datasets (partially addressed in rebuttal).
Decision: Accept-Main