Fixed Universal Transformers
Jingwen Liu, Alexandr Andoni, Daniel Hsu · 2026
Read Fixed Universal Transformers by Jingwen Liu, Alexandr Andoni, Daniel Hsu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-31423.txt.
Introduction
Liu, Andoni, and Hsu describe universal transformers. These are fixed models that can mimic any transformer in a given class, once fed a suitable input embedding. Like a universal Turing machine, the embedding carries a sketch of the target model, while all inner weights stay fixed. The authors give sparse builds that work when the embedding is wide enough. They also show that randomly started models are universal almost surely, and they test the idea on bracket balancing and multi-hop reasoning.
Catalog record
| CREATOR | Jingwen Liu, Alexandr Andoni, Daniel Hsu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91952 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.31423
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fixed Universal Transformers Jingwen Liu, Alexandr Andoni, Daniel Hsu Abstract We introduce universal transformers : fixed transformers that can simulate any transformer in a given class via a suitable input embedding. Analogous to a universal Turing machine, the input embedding encodes a description of the target model while all internal parameters remain fixed. We provide explicit sparse constructions achieving universality when the embedding dimension is sufficiently large, and further show that universality is generic: randomly initialized transformers are universal almost surely, which aligns with recent empirical results of Zhong and Andreas (2024). We empirically validate our theory on the algorithmic tasks of parenthesis balancing and multi-hop reasoning. Our results suggest that much of a transformer’s expressive power may reside in its input representation rather than its learned weights. 1 Introduction We introduce the notion of a universal transformer : a fixed transformer that can simulate any transformer in a prescribed class by changing only the input embedding. In a universal transformer, the embedding plays the role of a program: it encodes the parameters of the target transformer, while the attention and value parameters of the universal transformer remain fixed. This notion can be regarded as a deep learning analogue of the concept of universality from the theory of computation, of which universal Turing machines ( Turing 1936 ) and universal circuits ( Valiant 1976 ) are the prime examples. A universal Turing machine is a single Turing machine that is capable of simulating any other Turing machine (provided in a suitable encoding) as input, much like how we regard general purpose computers today ( Turing 1936 ) . A universal circuit is a single circuit that can simulate any target circuit of comparable size by simply fixing additional special “control” inputs to an appropriate values specific to the target circuit ( Valiant 1976 ) . Note that universality here is not the the same as universal approximation, which refers to the ability to choose the model parameters to approximate an arbitrary function. Instead, the architecture and non-embedding parameters are fixed, and the question is, for any target transformer of comparable form, whether there is a suitable representation of the input that makes this fixed computation emulate the target transformer. Our notion of universality is partly motivated by recent experimental findings of ( Zhong and Andreas 2024 ) on random transformers , where they found that many basic capabilities of language models are already present in randomly-initialized transformers, with only trained embedding and unembedding layers. These random transformers turn out to be universal (almost surely). Moreover, randomness is not essential: universal transformers can also be explicitly constructed. Our constructions give more insight into how the emulation can be carried out, and they do not resemble (and are much sparser than) any commonly-used initialization scheme for transformers. Universal transformers are also related to model reprogramming, a transfer-learning paradigm that adapts a pre-trained model to new domains by changing only the embedding layers ( Chen 2024 ) ; the existence of universal transformers vastly expands the potential scope of that approach. (a) (b) (c) Figure 1 : Schematic overview of universal transformers. (a) Each target transformer corresponds to a target-specific embedding (based on the target’s model parameters). (b) The parameters of the universal transformer are fixed, either using the sparse deterministic construction from Theorem 3.1 , or chosen randomly as in Theorem 3.3 . (c) The composition of the universal transformer with the target-specific embedding emulates the target transformer on all inputs. Our contributions. We formalize the notion of a universal transformer, which can simulate any transformer within a given class via a suitable input embedding. We provide explicit constructions of such models and further show that randomly initialized transformers are universal. • Explicit sparse universal transformers. We show that there exists a fixed H -head, L -layer universal transformer with embedding dimension m and \{0,1\} -valued parameters that can simulate any H -head, L -layer transformer with embedding dimension d , provided that m=O(Ld) when H=1 and m=O(H^{L}d) when H\geq 2 . Moreover, this result extends to the looped (weight-tied) setting, where the same parameters are reused across layers in the universal transformer. Theorem 1.1 (Informal version of Theorems 3.1 and 3.2 ) . There exists fixed \{0,1\} -valued parameters defining a H -head L -layer transformer (or looped transformer) \operatorname{UT} with embedding dimension m=O(Ld) when H=1 and m=O(H^{L}d) when H\geq 2 , such that there are at most m nonzero entries in each parameter matrix, and for any H -head L -layer transformer with embedding dimension d , there exists an embedding matrix E\in\mathbb{R}^{d\times m} , we have \operatorname{UT}(XE)=T(X) for any input X. • Random universal transformers. We prove that universality is in abundance: almost surely, a randomly initialized H -head, L -layer transformer can simulate any H -head, L -layer transformer with embedding dimension d , when the embedding dimension satisfies m=O(H^{L}d) . Theorem 1.2 (Informal version of Theorems 3.3 and 3.4 ) . Draw random parameters from an absolutely continuous distribution. With probability 1 , the resulting H -head L -layer transformer (or looped transformer) \operatorname{UT} with embedding dimension m=O(H^{L}d) such that for any H -head L -layer transformer with embedding dimension d , there exists an embedding matrix E\in\mathbb{R}^{d\times m} , we have \operatorname{UT}(XE)=T(X) for any input X . • Lower bounds. We establish that, when the number of heads is H\geq 2 , the exponential dependence on depth L is unavoidable, even when the embedding dimension is 1 , for any approach based on “attention-matching”, where the universal transformer reproduces the attention matrices of the transformer being simulated. Theorem 1.3 (Informal version of Theorem 4.1 ) . If an H -head, L -layer transformer \operatorname{UT} with embedding dimension m can simulate any H -head, L -layer transformer T with embedding dimension 1 via “attention-matching”, then m\geq H^{L/2} . • Empirical evaluation. We evaluate sparse and random universal transformers on parenthesis balancing and k -hop induction head tasks, achieving perfect or near-perfect accuracy. These findings complement our representational results and demonstrate that standard gradient-based optimization can effectively learn the required embeddings. 1.1 Related work Universality in computation. Our notion of a universal transformer takes inspiration from classical notions of universality in the theory of computation ( Turing 1936 ; Valiant 1976 ) , but adapts it to the deep learning context. Specifically, the description of the target transformer is provided as an input embedding layer for the universal transformer. As mentioned in the introduction, universal transformers can also be regarded as a form of model reprogramming ( Chen 2024 ) . Theoretical analyses on model reprogramming rely on distributional assumptions and offer average case error guarantees ( Yang et al. 2021 ) , much like other works on transfer learning. Our results offer a complementary type of theoretical guarantee for model reprogramming when the “pre-trained model” is a universal transformer, and the target tasks are solvable using task-specific transformers. Universal approximation and Turing-completeness. The notion of universality we study in this work is distinct from the universal approximation property of various types of neural networks (including transformers) ( Cybenko 1989 ; Hornik et al. 1989 ; Funahashi 1989 ; Yun et al. 2020 ; Wei et al. 2022