Universal Transformers

• The fixed-layer Transformer lacks RNNs’ iterative or recursive inductive bias and does not generalize well to sequence lengths unseen during training.Source: §1 · pp. 1–2
• UTs combine Transformer-like parallelism and global receptive fields with RNN-like iterative bias, and are Turing-complete under certain assumptions.Source: §1 · pp. 1–2
• Dynamic per-position halting lets UTs choose refinement steps per symbol, improving accuracy on several smaller structured tasks but marginally degrading machine translation results.Source: §1 · p. 2
• UTs refine every symbol in parallel at each recurrent step with self-attention, then apply a shared depth-wise separable convolution or position-wise fully connected layer.Source: §1 · p. 2
• UTs outperform Transformers and LSTMs across tasks, improve machine translation and algorithmic/bAbI results, and achieve a new LAMBADA state of the art with dynamic halting.Source: §1 · p. 2

2.1 THE UNIVERSAL TRANSFORMER

• The Universal Transformer (UT) recurs over successive revisions (“depth”) of each position’s representation, not over sequence positions, so computation depends on revisions rather than sequence length.Source: §2.1 · p. 2
• At each step, all positions are updated in parallel by global self-attention followed by a shared position-wise transition, allowing variable depth unlike fixed-stack Transformers and deep RNNs.Source: §2.1 · p. 3
• The encoder iteratively applies multi-head attention and a recurrent transition to input embeddings, with residual connections, dropout, layer normalization, and task-dependent convolutional or feed-forward transitions.Source: §2.1 · p. 3
• The autoregressive decoder attends to final encoder representations, masks future positions, and produces one next-symbol distribution per generation step.During training, its input is the target shifted right by one position; at generation, the encoder runs once while the decoder repeatedly consumes generated symbols.Source: §2.1 · p. 4

2.2 DYNAMIC HALTING

• ACT allocates dynamic processing time using per-step halting probabilities; halted UT positions copy their states forward until all halt or the maximum step count is reached.The motivation is that more ambiguous symbols may warrant more processing.Source: §2.2 · pp. 4–5

3.1 BABI QUESTION-ANSWERING

• Both UT variants—standard and dynamic halting—achieved state-of-the-art results on all tasks for average error and number of failed tasks in both 10K and 1K training regimes.Source: §3.1 · p. 5
• With dynamic halting, average bAbI ponder time rose with the number of supporting facts: 2.3±0.8 for one, 3.1±1.1 for two, and 3.8±2.2 for three.Many positions in three-fact tasks halted after one or two steps, while attention became sharper around the supporting facts over successive steps; the model appeared to ignore irrelevant facts.Source: §3.1 · pp. 5–6, Figure 3 · p. 6

3.2 SUBJECT-VERB AGREEMENT

• UTs significantly outperformed standard Transformers on subject-verb agreement and performed progressively better as agreement attractors increased.UTs achieved an average result comparable to the 99.2% state of the art; the best literature LSTM with attention scored 99.18%.Source: §3.2 · p. 6, Table 2 · p. 7

3.3 LAMBADA LANGUAGE MODELING

• UT achieved state-of-the-art results in both LAMBADA language modeling and reading comprehension, outperforming LSTMs and vanilla Transformers.Fixed UT models with 8 or 9 steps improved over the 6-step model but did not outperform dynamic halting, which averaged 8.2±2.1 steps and may regularize computation by allocating fewer steps to some symbols.Source: Table 3 · p. 7, §3.3 · p. 7

3.4 ALGORITHMIC TASKS

• On Copy, Reverse, and Addition sequences, UT outperformed LSTM and vanilla Transformer by a wide margin when trained on length 40 and evaluated on length 400.The reported Neural GPU perfect result used a special curriculum, unlike the other models.Source: §3.4 · pp. 7–8, Table 4 · p. 8

3.5 LEARNING TO EXECUTE (LTE)

• UT achieved perfect scores on all memorization tasks and outperformed LSTMs and Transformers by a wide margin on all program-evaluation tasks.The models were trained without curriculum learning and used no target sequences at test time.Source: §3.5 · p. 8, Table 5 · p. 8, Table 6 · p. 8

3.6 MACHINE TRANSLATION

• 0.9 BLEU over a Transformer and 0.5 BLEU over a Weighted Transformer were achieved by the UT on WMT14 English-German translation.The UT used a fully connected recurrent transition function and no adaptive computation time (ACT); the comparison used approximately the same number of parameters.Source: §3.6 · p. 8, Table 7 · p. 9

4 DISCUSSION

• With fixed steps, the Universal Transformer is a multi-layer Transformer with tied self-attention and transition weights; it can also be viewed as shared-parameter parallel RNNs with dynamic halting.Each position updates its hidden state by attending to the previous step’s sequence of hidden states.Source: §4 · p. 9
• Unlike time-recurrent RNNs, which have only a fixed-size state vector as recurrent memory, the Universal Transformer can attend to the whole previous layer during recurrence.The passage characterizes time-recurrent models as computationally more similar to automata because they cannot access memory in recurrent steps.Source: §4 · p. 9
• Given sufficient memory, the Universal Transformer is computationally universal, and its added expressivity improves accuracy on several challenging sequence-modeling tasks.The discussion frames this as closing a gap between practical models competitive on machine translation and computationally universal models trainable on algorithmic tasks.Source: §4 · p. 9
• With identity self-attention, convolutional transitions, and T equal to input length, the Universal Transformer reduces to a Neural GPU; its global parallel revisions express Neural Turing Machine read/write steps.The Neural GPU and Neural Turing Machine are cited as (Kaiser & Sutskever, 2016) and (Graves et al., 2014), respectively.Source: §4 · p. 9
• Unlike the Neural GPU and Neural Turing Machine, which the discussion says perform well only on algorithmic tasks, the Universal Transformer achieves competitive results on LAMBADA and machine translation.The passage contrasts performance on algorithmic tasks with competitive performance on realistic natural-language tasks.Source: §4 · p. 9
• Unlike end-to-end Memory Networks, the Universal Transformer uses memory aligned to individual input or output positions and follows an encoder-decoder configuration for large-scale sequence-to-sequence tasks.The passage states that the Universal Transformer achieves competitive performance in these tasks.Source: §4 · p. 9

• The Universal Transformer extends the Transformer’s theoretical capabilities and achieves state-of-the-art results across challenging sequence-modeling tasks.The paper presents it as addressing a key shortcoming of the standard Transformer.Source: §5 · p. 10
• Weight sharing balances inductive bias and model expressivity, with effectiveness shown in small- and large-scale experiments.The approach draws on weight-sharing intuitions from CNNs and RNNs.Source: §5 · p. 10
• Conditional computation lets the Universal Transformer halt or continue computation and performs more strongly than its fixed-depth version.The mechanism supports the goal of building a computationally universal machine.Source: §5 · p. 10
• The authors hope that adding computational capacity and recurrence in processing depth will yield more powerful, data-efficient learning algorithms that generalize beyond the current state of the art.Source: §5 · p. 10

APPENDIX A DETAILED SCHEMA OF THE UNIVERSAL TRANSFORMER

• The Universal Transformer schema includes position and step embeddings, dropout, and layer normalization.Source: Figure 4 · p. 13

APPENDIX B ON THE COMPUTATIONAL POWER OF UT VS TRANSFORMER

• A standard Transformer’s sequential operation count is constant with respect to input size and determined by its number of layers.Source: Appendix B · p. 13
• Under finite precision, the standard Transformer’s constant sequential depth means it cannot be computationally universal.Source: Appendix B · p. 13
• The Universal Transformer avoids this limitation when its number of steps depends non-constantly on input length, whether or not adaptive computation time is used.Source: Appendix B · p. 13
• Because the Universal Transformer shares weights across computation steps, its step count can be varied dynamically after training.Source: Appendix B · p. 13
• For a function requiring sequential processing of every element, a Transformer with depth T cannot correctly process some sequences of length N > T, while an input-length-dependent number of steps lets a Universal Transformer, RNN, or Neural GPU execute it.Source: Appendix B · p. 13

APPENDIX C UT WITH DYNAMIC HALTING

• Each step updates position states and halting probabilities; positions halt after crossing a scalar threshold, and computation ends when all halt or the maximum step count is reached.Halting variables and the previous state are initialized to zero, and the threshold is a hyper-parameter.Source: Appendix C · p. 14
• Halting probabilities accumulate for positions still running; newly halted positions receive a remainder, and update counts increase for running and newly halted positions.The remainder is computed from the probability accumulated before halting.Source: Appendix C · p. 14
• State updates weight the transformed state by the step’s halting probability for running positions, the remainder for newly halted positions, and zero for positions already halted.The transformed state applies self-attention followed by the transition function, then is interpolated with the previous state.Source: Appendix C · p. 14

APPENDIX D DESCRIPTION OF SOME OF THE TASKS/DATASETS

• The appendix covers bAbI, subject-verb agreement, LAMBADA language modeling, and learning to execute (LTE).Source: Appendix D · p. 15

D.1 BABI QUESTION-ANSWERING

• bAbI comprises 20 synthetic tasks testing distinct aspects of language understanding and reasoning, from story-based inference and counting to spatial reasoning and motivations (Weston et al., 2015).The task set also covers true/false questions, negation and indefinite knowledge, coreference, and time reasoning.Source: §D.1 · p. 15
• bAbI offers 1k- and 10k-example training versions; data efficiency matters for the 1k setting, and the intended evaluation trains one model jointly across tasks rather than tuning per task.The joint-train setup is used in Table 1 and the Appendix E tables.Source: §D.1 · p. 15

D.2 SUBJECT-VERB AGREEMENT

• Subject–verb agreement predicts number agreement between subjects and verbs, serving as a proxy for whether models capture hierarchical structure in natural language (Linzen et al., 2016).Success on the task is described as evidence that a model can approximate syntactic structure.Source: §D.2 · p. 15
• Linzen et al. (2016) proposed training for agreement either with next-word language modeling or as binary classification predicting the verb’s number from the sentence.Source: §D.2 · p. 15
• This paper uses the language-modeling objective and evaluates ranking accuracy by comparing the correct verb form with the incorrect form.This provides implicit supervision rather than explicit binary-classification labels.Source: §D.2 · p. 15
• Agreement attractors—intervening nouns with number opposite to the subject—raise difficulty by requiring the model to identify the subject head and ignore those nouns.Examples progress from no attractor (“The boy smiles”) to three (“The ratio of men to women and children is not clear”).Source: §D.2 · p. 15

D.3 LAMBADA LANGUAGE MODELING

• LAMBADA tests whether a model can predict a passage’s final word from its full narrative context, although the preceding target sentence alone is insufficient for human subjects.The passages are selected so humans can guess the final word from the long passage but not from the target sentence alone.Source: §D.3 · p. 15
• A randomly sampled control set of similarly shaped and sized passages checks standard language modeling before LAMBADA, helping distinguish task-specific difficulty from generally poor language modeling.The control passages are not filtered like LAMBADA passages.Source: §D.3 · pp. 15–16
• The LAMBADA control passages are randomly sampled without filtering from passages matching the task data’s shape and size.Source: §D.3 · p. 15
• LAMBADA is evaluated both as standard next-word language modeling and as reading comprehension, and the paper reports Universal Transformer results in both settings.In the more challenging language-modeling setting, models are trained to predict all words and evaluated on target words at test time.Source: §D.3 · p. 16

D.4 LEARNING TO EXECUTE (LTE)

• LTE, proposed by Zaremba & Sutskever (2015), includes program-evaluation tasks for numerical operations, conditionals, assignments, and compositional operations, plus copy, double, and reverse memorization tasks.Source: §D.4 · p. 16
• Program-evaluation difficulty varies with integer length and operation nesting: length bounds the number of digits, while nesting controls how deeply operations combine in parse trees.Integers are chosen uniformly from [1, length].Source: §D.4 · p. 16

APPENDIX E BABI DETAILED RESULTS

• For each task, the appendix reports the best seed run out of 10 runs.Source: Appendix E · p. 17
• The “failed” row lists values 0, 0, 3, and 5 under the displayed train single/joint columns.The supplied text does not make the mapping between individual values and columns clear.Source: Appendix E · p. 17

APPENDIX F BABI ATTENTION VISUALIZATION

• Attention weights are shown across time steps, over story facts and the question, with separate color bars for four heads.The appendix presents these visualizations for a couple of bAbI examples.Source: Appendix F · p. 18
• Figure 5 visualizes attention while encoding “Where is Mary?”, an example from a task requiring one supportive fact.The accompanying story includes Mary journeying to the bathroom.Source: Appendix F · p. 18, Figure 5 · p. 18
• Figure 6 visualizes attention while encoding “Where is the apple?”, an example from a task requiring two supportive facts.The story describes Mary taking and then dropping the apple.Source: Appendix F · p. 19, Figure 6 · p. 19
• Figure 7 visualizes attention while encoding “Where is the milk?”, another example from a task requiring two supportive facts.The story includes John grabbing and dropping the milk.Source: Appendix F · p. 20, Figure 7 · p. 20