Paramixer: Parameterizing Mixing Links in Sparse Factors Works Better than Dot-Product Self-Attention

Tong Yu, Ruslan Khalitov, Lei Cheng, Zhirong YangCVPR 2022 · DOI · arXiv

Abstract

Paramixer is a novel alternative to the standard dot-product self-attention mechanism that reduces computational complexity from $O(N^2)$ to $O(N \log N)$. By factorizing the mixing matrix into sparse, full-rank components parameterized by MLPs, it bypasses the "low-rank bottleneck" common in efficient Transformers. This approach delivers state-of-the-art performance on long sequences, such as genomic data and long-form documents.

Introduction

The scaling of Transformers is hindered by the quadratic $O(N^2)$ cost of standard self-attention. While efficient variants exist, they often suffer from a "low-rank bottleneck" where the attention matrix's expressive power is limited by the embedding dimension. Furthermore, the softmax operation restricts mixing to a convex hull, limiting information synthesis. Paramixer addresses these issues by abandoning dot-products and softmax in favor of learnable, sparse transformations.

Methods

Paramixer treats the mixing process as a learnable transformation through three key components:

1. Sparse Factorization and Parameterization

The mixing matrix $A$ is decomposed into a product of $M$ sparse matrices ($W^{(1)}, \dots, W^{(M)}$). Instead of similarity scores, small MLPs ($f^{(m)}$) generate the non-zero values for these matrices based on the input data.

The Paramixer block architecture, showing the factorization of the mixing matrix into sparse components parameterized by MLPs.

2. Sparsity Protocols

To ensure global connectivity with $O(N \log N)$ complexity, Paramixer employs structured sparsity patterns:

  • CHORD: Inspired by peer-to-peer lookup algorithms, providing logarithmic connectivity.
  • CDIL (Circular Dilated): Inspired by Temporal Convolutional Networks, using dilated connections along a circular graph for symmetric receptive fields.
Sparsity protocols (CHORD and CDIL) and their corresponding matrix parameterization schemes.

3. Full-Rank Guarantee

Unlike dot-product methods, these sparse factors are mathematically guaranteed to be full-rank, allowing the model to capture complex transformations that low-rank approximations cannot.

Evaluation and Results

Paramixer was evaluated on several long-sequence benchmarks:

  • Long Range Arena (LRA): Set new state-of-the-art marks on "Text" (83.32%) and "Pathfinder" (80.49%).
  • Genomic Classification: Achieved 100% ROC AUC on the HFDNA task, outperforming the original Transformer (94.32%).
  • Long Documents: Outperformed competitors by nearly 17 percentage points on 32k-length document classification.
  • Synthetic Tasks: Maintained 100% accuracy on tasks like the "Adding Problem" up to $N = 32,768$, where standard Transformers failed.

Discussion

The success of Paramixer highlights that sparsity, when combined with full-rank guarantees, can be more expressive than dense low-rank approximations. By shifting from similarity-based attention to direct parameterization of links, Paramixer offers a flexible and scalable framework for long-sequence modeling. Future work may explore adaptive sparsity patterns and integration into generative architectures.

Summary updated

BibTeX
@inproceedings{yu2022paramixer,
  author = {Tong Yu and Ruslan Khalitov and Lei Cheng and Zhirong Yang},
  title = {{Paramixer: Parameterizing Mixing Links in Sparse Factors Works Better than Dot-Product Self-Attention}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2022},
  doi = {10.1109/cvpr52688.2022.00077},
}
Figure