Transformer Vs. MLP-Mixer Exponential Expressive Gap For NLP Problems

Dan Navon, Alex M. BronsteinarXiv 2022 · DOI · arXiv

While MLP-based architectures like MLP-Mixer have shown promise in Computer Vision, they remain notably absent from Natural Language Processing (NLP) leaderboards. This research provides a rigorous mathematical explanation for this disparity, proving an exponential expressive gap between attention-based Transformers and MLP-based models when modeling complex, multi-variable dependencies.

The Architectural Divide: Vision vs. Language

Since the introduction of the Vision Transformer (ViT), researchers have explored whether simpler architectures—specifically those based entirely on Multi-Layer Perceptrons (MLPs)—could achieve parity. Models like MLP-Mixer utilize linear layers and permutations to "mix" information across tokens.

While competitive in vision tasks, MLP-Mixers struggle with NLP. This study investigates whether this is a tuning issue or a fundamental architectural limitation regarding "multi-variable connections"—the complex, simultaneous interactions between multiple parts of an input, such as words in a sentence.

Quantifying Expressivity via Separation-Rank

To measure expressivity, the authors employ a mathematical framework called separation-rank. Originally used in numerical analysis, this metric quantifies how "separable" a function is. A high separation rank indicates a model's ability to represent intricate dependencies between different input partitions.

The researchers established theoretical bounds for both architectures:

  • Transformers: The separation rank grows as $3^p$ (where $p$ is depth).
  • MLP-Mixers: The separation rank grows at a significantly slower rate of $2^p$.

This leads to an exponential divergence in expressive power as models scale. To ensure the proof was robust, the authors analyzed "relaxed" versions of the models (e.g., using $x^2$ activations), which actually favored the MLP-Mixer, making the identified gap even more significant.

The 1.58x Rule and the "Sweet Spot"

A key theoretical insight is the 1.58x Rule: for an MLP-Mixer to match the expressivity of a Transformer within the same parameter budget, it must be at least 1.58 times deeper.

Furthermore, the theory predicts an optimal depth-to-width ratio for MLP-Mixers. The "sweet spot" for performance is expected when the ratio of depth ($p$) to width ($d$) follows the logarithmic relationship: $1 < \frac{p}{\log_2 d} < 2$.

Experimental Validation

The authors validated these predictions using CIFAR10, SVHN (Vision), and MNLI (NLP) datasets.

Experimental validation of the theoretical "sweet spot" for MLP-Mixer depth-to-width ratios across CIFAR10, SVHN, and MNLI.

As shown in the figures above, accuracy across different parameter budgets consistently peaks within the predicted theoretical range ($1 < \frac{p}{\log_2 d} < 2$). Notably, the performance drop-off outside this range is particularly sharp for the MNLI dataset, highlighting why MLPs struggle with the long-range, non-local dependencies inherent in language.

Conclusion

The research confirms that Transformers are fundamentally more efficient at modeling the multi-variable connections required for NLP. While MLP-Mixers can exploit the "local" nature of image data, they lack the expressive machinery to handle the complex dependencies of natural language without becoming prohibitively deep. Future work may explore if the gap is even wider with standard non-linearities like ReLU and Softmax.

Summary updated

BibTeX
@misc{navon2022transformer,
  author = {Dan Navon and Alex M. Bronstein},
  title = {{Transformer Vs. MLP-Mixer Exponential Expressive Gap For NLP Problems}},
  year = {2022},
  eprint = {2208.08191},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.08191},
}
Figure