Deep self-attention networks can map sequences using fixed blocks
Universal interpolation for deep residual self-attention networks
Machine Learning
Summary
Sometimes, neural networks need to be able to transform any set of data sequences into any other set. This paper shows that deep self-attention networks, like those used in transformers, can do this using just a small number of fixed building blocks. These blocks don't need to change for each task—only how they're combined matters. The authors prove this mathematically, including when certain restrictions like causal masking are applied.
What this means in practice
- •For machine learning framework developers: Design self-attention modules that use fixed parameter blocks to simplify training while preserving the ability to transform sequences flexibly.
- •For database query engine builders: Implement new query transformation methods that rely on deep residual attention blocks for flexible sequence data manipulation without retraining parameters.
A theory result. No direct application yet.
Authors
Sibylle Marcotte, Joan Bruna
Abstract
Universal approximation is a necessary qualitative property of learning architectures to benefit from scaling laws. While it is generically verified on a variety of neural architectures and random feature models, it typically involves infinite width limits. In this work, we focus on deep self-attention models and consider instead the `dual' regime, where approximation power is enabled entirely by depth, and featuring strong parameter sharing across layers, motivated by recent models such as the Looped Transformers. More specifically, we ask whether one can find a predefined finite set of parameters, each defining an attention block, such that the resulting finite set of transformations can map any collection of $N$ sequences of $n$ tokens to any other collection of $N$ sequences of $n$ tokens. Crucially, these transformations are \emph{fixed independently of the input and output} collections: only the order in which the blocks are applied, their signs, and their durations depend on the particular interpolation task. Our main result establishes it for residual softmax attention using only two frozen single-head blocks with Gaussian-initialized projection matrices. The result holds at both continuous and finite depth. We also characterize the restrictions imposed by causal masking and establish corresponding universal interpolation guarantees.