Limits on what real-valued transformers can learn from sequences
VC Dimension and Expressivity of Real-Valued Transformers
Machine LearningArtificial Intelligence
Summary
This paper looks at how much real-valued transformer neural networks can learn from sequences when using their usual softmax attention mechanism. By using math from real geometry, the authors find upper and lower limits on how complex the patterns these transformers can recognize are, depending on the input length. They also show that transformers can represent all patterns if there’s only one symbol, can almost do so with two symbols, but fail with six. Additionally, they prove transformers can only read a limited number of bits from real numbers.
What this means in practice
- •For machine learning engineers: Know theoretical limits on transformer models’ ability to learn certain sequence functions to better guide model design and expectations.
- •For data compression developers: Understand inherent limits on how precisely transformers can interpret real numbers to inform algorithms involving quantized data.
A theory result. No direct application yet.
Authors
Gavin Dooley, Andy Yang, Yijia Jessica Zhu, David Chiang, Peter Cholak, Anand Pillay
Abstract
Whereas previous results on abilities and limitations of transformers have restricted the definition of transformers in various ways, here we study softmax-attention, multi-layer transformers operating on real values, with very few additional assumptions. Applying results from real geometry, we obtain upper bounds on the VC dimension and split VC dimension of such transformers ($O(n^4)$ and $O(n^6)$, respectively, where $n$ is the input length). Conversely, we also construct specific transformers witnessing lower bounds on these quantities ($Ω(n)$ in each case). These results have some notable consequences. For example, within the class of symmetric (permutation-invariant) functions, we show that transformers can uniformly express all functions over an alphabet of one symbol and non-uniformly express all functions over an alphabet of two symbols, but cannot (even non-uniformly) express some functions over an alphabet of six symbols. We also prove limitations on how many bits of a real number a transformer can access.