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.
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.
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