# Vocabulary for Universal Approximation: A Linguistic Perspective of Mapping Compositions

arXiv: https://arxiv.org/abs/2305.12205 · HTML: https://mlsanity.com/paper/2305.12205/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 46 references that are in the map.
- First posted on arXiv 20 May 2023.

## Builds on (most cited first, 21 of 21)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Identity Mappings in Deep Residual Networks](https://mlsanity.com/paper/1603.05027/) (2016)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [Minimum Width for Universal Approximation](https://mlsanity.com/paper/2006.08859/) (2020)
- [Deep Learning via Dynamical Systems: An Approximation Perspective](https://mlsanity.com/paper/1912.10382/) (2019)
- [The paradox of the compositionality of natural language: a neural machine translation case study](https://mlsanity.com/paper/2108.05885/) (2021)
- [Deep, Skinny Neural Networks are not Universal Approximators](https://mlsanity.com/paper/1810.00393/) (2018)
- [Do Residual Neural Networks discretize Neural Ordinary Differential Equations?](https://mlsanity.com/paper/2205.14612/) (2022)
- [Achieve the Minimum Width of Neural Networks for Universal Approximation](https://mlsanity.com/paper/2209.11395/) (2022)
- [Universal Approximation Power of Deep Residual Neural Networks via Nonlinear Control Theory](https://mlsanity.com/paper/2007.06007/) (2020)
- [Benchmarking Compositionality with Formal Languages](https://mlsanity.com/paper/2208.08195/) (2022)
- [CBOW Is Not All You Need: Combining CBOW with the Compositional Matrix Space Model](https://mlsanity.com/paper/1902.06423/) (2019)
- [Vanilla Feedforward Neural Networks as a Discretization of Dynamical Systems](https://mlsanity.com/paper/2209.10909/) (2022)

## Built on by (most cited first, 6 of 6)

- [LLM as GNN: Graph Vocabulary Learning for Text-Attributed Graph Foundation Models](https://mlsanity.com/paper/2503.03313/) (2025)
- [Flipping Against All Odds: Reducing LLM Coin Flip Bias via Verbalized Rejection Sampling](https://mlsanity.com/paper/2506.09998/) (2025)
- [A Minimal Control Family of Dynamical Systems for Universal Approximation](https://mlsanity.com/paper/2312.12903/) (2023)
- [CodeUnlearn: Amortized Zero-Shot Machine Unlearning in Language Models Using Discrete Concept](https://mlsanity.com/paper/2410.10866/) (2024)
- [Vocabulary In-Context Learning in Transformers: Benefits of Positional Encoding](https://mlsanity.com/paper/2511.06376/) (2025)
- [Universal interpolation for deep residual self-attention networks](https://mlsanity.com/paper/2610.01981/) (2026)

## Abstract (arXiv)

In recent years, deep learning-based sequence modelings, such as language models, have received much attention and success, which pushes researchers to explore the possibility of transforming non-sequential problems into a sequential form. Following this thought, deep neural networks can be represented as composite functions of a sequence of mappings, linear or nonlinear, where each composition can be viewed as a word. However, the weights of linear mappings are undetermined and hence require an infinite number of words. In this article, we investigate the finite case and constructively prove the existence of a finite vocabulary V=φi: ℝd → ℝd | i=1,...,n with n=O(d2) for the universal approximation. That is, for any continuous mapping f: ℝd → ℝd, compact domain Omega and varepsilon>0, there is a sequence of mappings φi1, ..., φim ∈ V, m ∈ mathbbZ_+, such that the composition φim circ ... circ φi1  approximates f on Omega with an error less than varepsilon. Our results demonstrate an unusual approximation power of mapping compositions and motivate a novel compositional model for regular languages.