---
title: "Are Transformers universal — paper by Yun et al. (2019)"
description: "Transformers are widely used for NLP, but it has been unclear which sequence-to-sequence… 29 references, cited by 61 papers here."
authors: ["Chulhee Yun", "Srinadh Bhojanapalli", "Ankit Singh Rawat", "Sashank J. Reddi", "Sanjiv Kumar"]
year: 2019
venue: "arXiv:1912.10077"
source: "https://arxiv.org/abs/1912.10077"
doi: "10.48550/arxiv.1912.10077"
arxiv: "1912.10077"
licence: "arXiv — non-exclusive licence to distribute"
licence_url: "http://arxiv.org/licenses/nonexclusive-distrib/1.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/yun-2019-transformers-universal-approximators-sequence-sequence/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/yun-2019-transformers-universal-approximators-sequence-sequence/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2019](https://md.research.elamur.ai/free/en/papers/2019/page/5/) / Are Transformers universal approximators of sequence-to-sequence functions?

# Are Transformers universal approximators of sequence-to-sequence functions?

**Authors:** Chulhee Yun, Srinadh Bhojanapalli, [Ankit Singh Rawat](https://md.research.elamur.ai/free/en/authors/ankit-singh-rawat/), [Sashank J. Reddi](https://md.research.elamur.ai/free/en/authors/sashank-jakkam-reddi/) and [Sanjiv Kumar](https://md.research.elamur.ai/free/en/authors/sanjiv-kumar/) · **Year:** 2019 · **Venue:** arXiv:1912.10077 · **Licence:** [arXiv — non-exclusive licence to distribute](http://arxiv.org/licenses/nonexclusive-distrib/1.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/1912.10077) · [PDF](https://arxiv.org/pdf/1912.10077) · [DOI 10.48550/arxiv.1912.10077](https://doi.org/10.48550/arxiv.1912.10077) · [arXiv 1912.10077](https://arxiv.org/abs/1912.10077) · [OpenAlex](https://openalex.org/W2995273672)

**Citations:** 36 citations (OpenAlex, 2026-10-14) · [61](https://md.research.elamur.ai/free/en/papers/yun-2019-transformers-universal-approximators-sequence-sequence/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Transformers are widely used for NLP, but it has been unclear which sequence-to-sequence mappings they can actually represent. Every token passes through the same weights, and tokens interact only through pairwise dot products. Yun et al. answer this with a formal expressivity analysis. They first show that stacks of Transformer blocks can approximate, to arbitrary precision, any continuous permutation equivariant function with compact support. They then show that adding trainable positional encodings removes the equivariance limitation, so any continuous sequence-to-sequence function on a compact domain can be approximated. The proofs assign distinct roles to the two layer types. Self-attention computes a "contextual mapping," which assigns each distinct input context its own unique representation. The feed-forward layers then map those representations to the required outputs. Motivated by this split, the authors try cheaper substitutes for attention in BERT-style pre-training: bi-linear projections and separable convolutions. The results matter because they give a theoretical account of why contextual embeddings work. They also suggest that some attention layers could be swapped for more efficient components.

## Key points
- **Theorem 2:** a very narrow class, T^{2,1,4}, can approximate any permutation equivariant target in L_p distance. This class has 2 attention heads of size 1 and a feed-forward hidden width of 4. The analysis leaves out layer normalization.
- **Theorem 3:** with trainable positional encodings, arbitrary continuous functions on a compact domain can be approximated. The construction is very deep, requiring O(n(1/δ)^{dn}) layers.
- **Lemma 6:** this lemma formalizes contextual mappings and proves that self-attention layers can compute them.
- **Experimental setup:** BERT BASE (110M parameters) was pre-trained on English Wikipedia and BooksCorpus, then evaluated on MNLI and SQuAD.
- **Results (Table 1, MLM accuracy / MNLI accuracy):**

| Model | Parameters | MLM accuracy | MNLI accuracy |
|---|---|---|---|
| Transformer | 110M | 63% | 78.2% |
| SepConv | 102.5M | 60% | 73% |
| BProj | 90M | 59% | 72.3% |
| Average Attention | 88.3M | 28% | 66% |

  Used as standalone models, the cheaper layers score below the Transformer. However, replacing only some of the lower self-attention layers with them can improve performance.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Google](https://md.research.elamur.ai/free/en/companies/google/) — Company, Mountain View, United States · 492 works · 440,463 citations
- [Massachusetts Institute of Technology](https://md.research.elamur.ai/free/en/universities/massachusetts-institute-of-technology/) — University, Cambridge, United States · 243 works · 76,506 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works

## Cite

Cite as: Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi and Sanjiv Kumar. 2019. Are Transformers universal approximators of sequence-to-sequence functions?. arXiv:1912.10077.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{yun2019are,
  title = {{Are Transformers universal approximators of sequence-to-sequence functions?}},
  author = {Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi and Sanjiv Kumar},
  year = {2019},
  doi = {10.48550/arxiv.1912.10077},
  eprint = {1912.10077},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1912.10077}
}
```

- [← previous Executing Instructions in Situated Collaborative Interactions](https://md.research.elamur.ai/free/en/papers/suhr-2019-executing-instructions-situated-collaborative-interactions/)
- [next → On Adversarial Removal of Hypothesis-only Bias in Natural Language Inference](https://md.research.elamur.ai/free/en/papers/belinkov-2019-adversarial-removal-hypothesis-only-bias/)
- [↑ back to papers of 2019](https://md.research.elamur.ai/free/en/papers/2019/page/5/)

## References

29 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Nir Ailon and Bernard Chazelle. The fast Johnson–Lindenstrauss transform and approximate nearest neighbors. SIAM Journal on computing, 39(1):302–322, 2009. [find](https://scholar.google.com/scholar?q=Nir+Ailon+and+Bernard+Chazelle%2E+The+fast+Johnson%E2%80%93Lindenstrauss+transform+and+approximate+nearest+neighbors%2E+SIAM+Journal+on+computing%2C+39%281%29%3A302%E2%80%93322%2C+2009%2E)
2. François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1251–1258, 2017. [find](https://scholar.google.com/scholar?q=Franc%CC%A7ois+Chollet%2E+Xception%3A+Deep+learning+with+depthwise+separable+convolutions%2E+In+Proceedings+of+the+IEEE+conference+on+computer+vision+and+pattern+recognition%2C+pp%2E+1251%E2%80%931258%2C+2017%2E)
3. Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning. What does BERT look at? an analysis of BERT’s attention. arXiv preprint arXiv:1906.04341, 2019. [find](https://scholar.google.com/scholar?q=Kevin+Clark%2C+Urvashi+Khandelwal%2C+Omer+Levy%2C+and+Christopher+D+Manning%2E+What+does+BERT+look+at%3F+an+analysis+of+BERT%E2%80%99s+attention%2E+arXiv+preprint+arXiv%3A1906%2E04341%2C+2019%2E)
4. Andy Coenen, Emily Reif, Ann Yuan, Been Kim, Adam Pearce, Fernanda Viégas, and Martin Wattenberg. [Visualizing and measuring the geometry of BERT](https://md.research.elamur.ai/free/en/papers/coenen-2019-visualizing-measuring-geometry-bert/). arXiv preprint arXiv:1906.02715, 2019.
5. George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303–314, 1989. [find](https://scholar.google.com/scholar?q=George+Cybenko%2E+Approximation+by+superpositions+of+a+sigmoidal+function%2E+Mathematics+of+control%2C+signals+and+systems%2C+2%284%29%3A303%E2%80%93314%2C+1989%2E)
6. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Łukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018. [find](https://scholar.google.com/scholar?q=Mostafa+Dehghani%2C+Stephan+Gouws%2C+Oriol+Vinyals%2C+Jakob+Uszkoreit%2C+and+%C5%81ukasz+Kaiser%2E+Universal+transformers%2E+arXiv+preprint+arXiv%3A1807%2E03819%2C+2018%2E)
7. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. [BERT: Pre-training of deep bidirectional transformers for language understanding](https://md.research.elamur.ai/free/en/papers/devlin-2019-bert-pre-training-deep-bidirectional/). arXiv preprint arXiv:1810.04805, 2018.
8. Yunchao Gong, Sanjiv Kumar, Henry A Rowley, and Svetlana Lazebnik. Learning binary codes for high-dimensional data using bilinear projections. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 484–491, 2013. [find](https://scholar.google.com/scholar?q=Yunchao+Gong%2C+Sanjiv+Kumar%2C+Henry+A+Rowley%2C+and+Svetlana+Lazebnik%2E+Learning+binary+codes+for+high%2Ddimensional+data+using+bilinear+projections%2E+In+Proceedings+of+the+IEEE+conference+on+computer+vision+)
9. Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiv:1710.11278, 2017. — [arXiv:1710.11278](https://arxiv.org/abs/1710.11278) [find](https://scholar.google.com/scholar?q=Boris+Hanin+and+Mark+Sellke%2E+Approximating+continuous+functions+by+relu+nets+of+minimal+width%2E+arXiv+preprint+arXiv%3A1710%2E11278%2C+2017%2E+%E2%80%94+%5BarXiv%3A1710%2E11278%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1710%2E11278%29)
10. We refer to Section D for a complete description of the setup. John Hewitt and Christopher D Manning. [A structural probe for finding syntax in word representations](https://md.research.elamur.ai/free/en/papers/hewitt-2019-structural-probe-finding-syntax-word/). In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Te…
11. Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4 (2):251–257, 1991. [find](https://scholar.google.com/scholar?q=Kurt+Hornik%2E+Approximation+capabilities+of+multilayer+feedforward+networks%2E+Neural+networks%2C+4+%282%29%3A251%E2%80%93257%2C+1991%2E)
12. Lukasz Kaiser, Aidan N Gomez, and Francois Chollet. Depthwise separable convolutions for neural machine translation. arXiv preprint arXiv:1706.03059, 2017. [find](https://scholar.google.com/scholar?q=Lukasz+Kaiser%2C+Aidan+N+Gomez%2C+and+Francois+Chollet%2E+Depthwise+separable+convolutions+for+neural+machine+translation%2E+arXiv+preprint+arXiv%3A1706%2E03059%2C+2017%2E)
13. Hongzhou Lin and Stefanie Jegelka. ResNet with one-neuron hidden layers is a universal approximator. In Advances in Neural Information Processing Systems, pp. 6169–6178, 2018. [find](https://scholar.google.com/scholar?q=Hongzhou+Lin+and+Stefanie+Jegelka%2E+ResNet+with+one%2Dneuron+hidden+layers+is+a+universal+approximator%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pp%2E+6169%E2%80%936178%2C+2018%2E)
14. Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pre-training approach. arXiv preprint arXiv:1907.[11692, 2019](https://md.research.elamur.ai/free/en/papers/liu-2019-roberta-robustly-optimized-bert-pretraining/).
15. Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Advances in neural information processing systems, pp. 6231–6239, 2017. [find](https://scholar.google.com/scholar?q=Zhou+Lu%2C+Hongming+Pu%2C+Feicheng+Wang%2C+Zhiqiang+Hu%2C+and+Liwei+Wang%2E+The+expressive+power+of+neural+networks%3A+A+view+from+the+width%2E+In+Advances+in+neural+information+processing+systems%2C+pp%2E+6231%E2%80%936239%2C+2)
16. Minh-Thang Luong, Hieu Pham, and Christopher D. Manning. [Effective approaches to attention-based neural machine translation](https://md.research.elamur.ai/free/en/papers/luong-2015-effective-approaches-attention-based-neural/). In Empirical Methods in Natural Language Processing (EMNLP), pp. 1412–1421, Lisbon, Portugal, September 2015. Association for Computational Linguistics.
17. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. [Distributed representations of words and phrases and their compositionality](https://md.research.elamur.ai/free/en/papers/mikolov-2013-distributed-representations-words-phrases-their/). In Advances in neural information processing systems, pp. 3111–3119, 2013.
18. Jorge Pérez, Javier Marinković, and Pablo Barceló. On the Turing completeness of modern neural network architectures. arXiv preprint arXiv:1901.03429, 2019. [find](https://scholar.google.com/scholar?q=Jorge+Pe%CC%81rez%2C+Javier+Marinkovic%CC%81%2C+and+Pablo+Barcelo%CC%81%2E+On+the+Turing+completeness+of+modern+neural+network+architectures%2E+arXiv+preprint+arXiv%3A1901%2E03429%2C+2019%2E)
19. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. Technical Report, OpenAI, 2018. [find](https://scholar.google.com/scholar?q=Alec+Radford%2C+Karthik+Narasimhan%2C+Tim+Salimans%2C+and+Ilya+Sutskever%2E+Improving+language+understanding+by+generative+pre%2Dtraining%2E+Technical+Report%2C+OpenAI%2C+2018%2E)
20. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. Technical Report, OpenAI, 2019. [find](https://scholar.google.com/scholar?q=Alec+Radford%2C+Jeffrey+Wu%2C+Rewon+Child%2C+David+Luan%2C+Dario+Amodei%2C+and+Ilya+Sutskever%2E+Language+models+are+unsupervised+multitask+learners%2E+Technical+Report%2C+OpenAI%2C+2019%2E)
21. Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. [SQuAD: 100,000+ questions for machine comprehension of text](https://md.research.elamur.ai/free/en/papers/rajpurkar-2016-squad-100-000-questions-machine/). In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383–2392, 2016.
22. Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invariant/equivariant functions by deep neural networks. arXiv preprint arXiv:1903.01939, 2019. — [arXiv:1903.01939](https://arxiv.org/abs/1903.01939) [find](https://scholar.google.com/scholar?q=Akiyoshi+Sannai%2C+Yuuki+Takai%2C+and+Matthieu+Cordonnier%2E+Universal+approximations+of+permutation+invariant%2Fequivariant+functions+by+deep+neural+networks%2E+arXiv+preprint+arXiv%3A1903%2E01939%2C+2019%2E+%E2%80%94+%5BarXiv%3A)
23. Laurent Sifre and Stéphane Mallat. Rigid-motion scattering for image classification. Ph. D. dissertation, 2014. [find](https://scholar.google.com/scholar?q=Laurent+Sifre+and+Ste%CC%81phane+Mallat%2E+Rigid%2Dmotion+scattering+for+image+classification%2E+Ph%2E+D%2E+dissertation%2C+2014%2E)
24. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. [Attention is all you need](https://md.research.elamur.ai/free/en/papers/vaswani-2017-attention-all-need/). In Advances in Neural Information Processing Systems, pp. 5998–6008, 2017.
25. Jesse Vig and Yonatan Belinkov. [Analyzing the structure of attention in a transformer language model](https://md.research.elamur.ai/free/en/papers/vig-2019-analyzing-structure-attention-transformer-language/). arXiv preprint arXiv:1906.04284, 2019.
26. Adina Williams, Nikita Nangia, and Samuel Bowman. [A broad-coverage challenge corpus for sentence understanding through inference](https://md.research.elamur.ai/free/en/papers/williams-2018-broad-coverage-challenge-corpus-sentence/). In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers),…
27. Felix Wu, Angela Fan, Alexei Baevski, Yann N Dauphin, and Michael Auli. [Pay less attention with lightweight and dynamic convolutions](https://md.research.elamur.ai/free/en/papers/wu-2019-pay-less-attention-lightweight-dynamic/). arXiv preprint arXiv:1901.10430, 2019.
28. Zhilin Yang, Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. [XLNet: Generalized autoregressive pretraining for language understanding](https://md.research.elamur.ai/free/en/papers/yang-2019-xlnet-generalized-autoregressive-pretraining-language/). arXiv preprint arXiv:1906.08237, 2019.
29. Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. [Aligning books and movies: Towards story-like visual explanations by watching movies and reading books](https://md.research.elamur.ai/free/en/papers/zhu-2015-aligning-books-movies-towards-story/). In Proceedings of the IEEE international conference on computer vision, pp. 19–27, 2015…

*Updated 2 November 2026*