Research map / Architectures and efficiency / Attention and transformers
Fixed Universal Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces universal transformers: fixed-parameter transformers that simulate any transformer in a class via only an input embedding, with explicit sparse constructions, almost-sure universality of random transformers, and an attention-matching lower bound.
Problem
Whether a single fixed-parameter transformer architecture can emulate any transformer of a given class by changing only the input embedding, and how large the embedding dimension must be.
Approach
Define universality analogous to universal Turing machines: the embedding encodes the target's parameters while the attention and value matrices stay fixed. Give sparse 0/1 constructions with embedding dimension scaling as H^L d (or Ld for H=1), show random fixed parameters are universal almost surely, and prove an H^{L/2} lower bound for attention-matching approaches.
Key results
- Sparse universal transformer reaches 100.0% on parenthesis balancing, matching the fully trained transformer; random universal reaches 94.4% (attention-only).
- With residual and layer normalization, the sparse universal transformer reaches 100.0% on all reported k-hop induction-head tasks (1 to 4 hops), while the random universal transformer reaches 85.7% to 96.1%.
- Attention-only universal transformers on 1- to 4-hop induction heads reach only about 29% to 39% accuracy, far below the fully trained model at 3- and 4-hop.
Surprising findings
- Attention-only universal transformers are much weaker on k-hop induction heads than fully trained transformers at depth 3 and 4 (about 39% vs 99.5%), indicating optimization difficulty despite representational capacity.
- Random universal transformers with only embedding and unembedding trained match the fully trained transformer on parenthesis balancing with residual and LN (100% vs 93.0%).
Limitations
- Lower bound applies only to attention-matching (shared-attention) constructions with embedding dimension 1 inputs.
- Universality results do not extend to standard learned LayerNorm; the paper states this as an obstacle.
- Empirical experiments use small toy tasks with embedding dimensions up to 2280 and only train embedding and unembedding.
Experimental setup
Datasets: parenthesis balancing (Dyck-1) k-hop induction head task
Benchmarks: parenthesis balancing (Dyck-1) k-hop induction heads
Metrics: accuracy
Baselines: fully trained transformer random universal transformer
Builds on: random transformers (Zhong and Andreas 2024) model reprogramming universal Turing machines universal circuits
Closest papers by meaning
- Constant Bit-size Transformers Are Turing Complete (NeurIPS 2025 · similarity 0.88)
- A unified framework for establishing the universal approximation of transformer-type architectures (NeurIPS 2025 · similarity 0.88)
- Characterizing the Expressivity of Fixed-Precision Transformer Language Models (NeurIPS 2025 · similarity 0.88)
- Exact Expressive Power of Transformers with Padding (NeurIPS 2025 · similarity 0.87)
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.87)
- Algorithmic Capabilities of Random Transformers (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.