Approximation of relation functions and attention mechanisms

Awni Altabaa, John LaffertyarXiv 2024 · DOI · arXiv

Introduction

Modern artificial intelligence relies heavily on the ability to model relationships between data points. Whether it is a Siamese network comparing two images for similarity or a Transformer's attention mechanism determining the relevance of a "key" to a "query," the underlying operation is often the same: an inner product of two neural network feature maps, expressed as $\langle \phi(x), \psi(y) \rangle$.

While the Universal Approximation Theorem has long established that a single neural network can approximate any continuous function $f(x)$, the theoretical limits of these specific relational architectures were not fully characterized. This paper provides a rigorous "seal of approval" for these models, proving that inner product structures are universal approximators for relation functions and establishing a formal link between attention mechanisms and Reproducing Kernel Banach Spaces (RKBS).

The Problem of Relational Representation

In machine learning, we frequently encounter the need to model how two objects relate to one another. The standard approach is to map inputs into a high-dimensional feature space and compute their dot product. However, it was previously unclear if this specific dot-product structure imposed hidden limitations. Could it capture any relationship, or were there certain classes of functions that this architecture simply could not represent? The authors sought to define the "representational power" of these relational neural architectures to answer these fundamental questions.

Theoretical Framework and Methodology

The authors approach the problem by bifurcating relations into two distinct categories based on their mathematical properties:

1. Symmetric Relations

Symmetric relations occur when the relationship between $x$ and $y$ is identical to the relationship between $y$ and $x$ (e.g., similarity or distance). By applying Mercer’s Theorem and the theory of Reproducing Kernel Hilbert Spaces (RKHS), the authors demonstrate that a single multi-layer perceptron (MLP) inner-producted with itself—$\langle \phi(x), \phi(y) \rangle$—can approximate any symmetric positive-definite kernel.

2. Asymmetric Relations

Asymmetric relations are directional, such as when "A is more relevant than B" or in the query-key dynamics of a Transformer. The authors prove that by using two distinct MLPs ($\phi$ and $\psi$), the model can approximate any continuous relation. They link this capability to the more general framework of Reproducing Kernel Banach Spaces (RKBS), providing a more flexible geometric interpretation than standard Hilbert spaces.

To analyze Attention Mechanisms, the authors incorporate the Debreu Representation Theorem from the field of economics. This allows them to treat "relevance" as a preference ordering (a preorder) and represent it as a continuous utility function, which a neural network can then be trained to approximate.

Key Insights

The Banach Space Connection

While symmetric kernels are well-understood through RKHS, the authors argue that the asymmetric nature of modern attention naturally belongs to the world of Banach spaces. This conceptual bridge is significant for researchers attempting to understand the underlying geometry of Transformers and how they process information.

Attention as a Universal Selector

The paper proves that dot-product attention is not merely a "blurry" weighted average. Instead, it is a universal approximator for "selection functions." Specifically, given a set of elements, the mechanism can be tuned to perfectly retrieve the "most relevant" element based on any continuous preference rule.

Overcoming the Curse of Dimensionality

Standard approximation results often suffer from an exponential "curse of dimensionality," where the number of required parameters explodes as the input size increases. However, the authors show that if the relation depends on smooth, low-dimensional features (measured by the Barron norm), the number of neurons needed to achieve high accuracy remains computationally manageable.

Utility Theory in AI

By utilizing the Debreu theorem, the authors provide a rigorous way to interpret "relevance" in Transformers as a form of economic utility. This provides a new, mathematically grounded lens for AI interpretability, viewing attention weights as a manifestation of a model's preference hierarchy.

Summary of Results

  • Universal Approximation (Symmetric): Theorem 2.1 proves that $\langle \phi(x), \phi(y) \rangle$ can approximate any symmetric positive-definite relation function $r(x, y)$ to within $\epsilon$ error.
  • Universal Approximation (Asymmetric): Theorem 3.1 proves that $\langle \phi(x), \psi(y) \rangle$ can approximate any continuous asymmetric relation function.
  • Attention Bounds: Theorem 5.1 demonstrates that for any selection task (picking the best $x_i$ for a query $q$), there exist MLPs and a scaling factor $\beta$ such that the attention mechanism identifies the target with high probability.
  • Complexity Estimates: The paper provides explicit bounds on the number of neurons ($N$) required, showing that $N$ is determined by the "spectral decay" of the relation—essentially how much information is concentrated in its primary components.

Limitations and Future Directions

While this work establishes a strong theoretical foundation, several areas remain for future exploration. The current analysis focuses on the "Select" function (the ability to pick the single most relevant item), but future work is needed to derive bounds for the full distribution of attention weights across the entire softmax output. Additionally, the proofs currently address "flat" relations; extending these results to the hierarchical or recursive relations found in multi-head, multi-layer Transformers is a logical next step. Finally, the results rely on the assumption that the underlying relation is "smooth" (via the Barron norm); if a ground-truth relation is highly discontinuous, these complexity bounds may no longer hold.

Summary updated

Abstract

Inner products of neural network feature maps arise in a wide variety of machine learning frameworks as a method of modeling relations between inputs. This work studies the approximation properties of inner products of neural networks. It is shown that the inner product of a multi-layer perceptron with itself is a universal approximator for symmetric positive-definite relation functions. In the case of asymmetric relation functions, it is shown that the inner product of two different multi-layer perceptrons is a universal approximator. In both cases, a bound is obtained on the number of neurons required to achieve a given accuracy of approximation. In the symmetric case, the function class can be identified with kernels of reproducing kernel Hilbert spaces, whereas in the asymmetric case the function class can be identified with kernels of reproducing kernel Banach spaces. Finally, these approximation results are applied to analyzing the attention mechanism underlying Transformers, showing that any retrieval mechanism defined by an abstract preorder can be approximated by attention through its inner product relations. This result uses the Debreu representation theorem in economics to represent preference relations in terms of utility functions.
BibTeX
@misc{altabaa2024approximation,
  author = {Awni Altabaa and John Lafferty},
  title = {{Approximation of relation functions and attention mechanisms}},
  year = {2024},
  eprint = {2402.08856},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.08856},
}
Figure