Abstract
Modern Transformer architectures are limited by the $O(n^2)$ computational bottleneck of standard softmax attention. We present Sliced ReLU attention, a mechanism that achieves quasi-linear $O(n \log n)$ complexity by leveraging 1D projections and sorting. Unlike many efficient attention variants, Sliced ReLU attention maintains the theoretical universal approximation power of standard Transformers. Our results across the Long Range Arena (LRA) and computer vision benchmarks demonstrate significant throughput gains and competitive performance, particularly in long-context tasks.
Introduction
The "quadratic bottleneck" of standard attention mechanisms makes processing long sequences—such as high-resolution images or long-form video—prohibitively expensive. While linear attention and State Space Models (SSMs) offer efficiency, they often struggle to capture the complex global interactions that standard Transformers handle with ease. Sliced ReLU attention addresses this by framing attention as a sorting problem, utilizing highly optimized hardware primitives to achieve speed without sacrificing expressivity.
Methodology
Sliced ReLU attention replaces the traditional dot-product similarity with a mechanism based on 1D projections:
- Slicing (Projection): Queries ($Q$) and Keys ($K$) are projected onto a one-dimensional line using learnable linear layers.
- ReLU Interaction: Interactions are computed as $ReLU(\text{proj}(Q_i) - \text{proj}(K_j))$.
- The Sorting Trick: Because the interaction occurs in one dimension, the scores can be sorted. This allows the attention output to be computed using a "scan" (cumulative sum) operation, reducing complexity from $O(n^2)$ to $O(n \log n)$.
- ReLU-Bump Variant: A specialized "hat kernel" combines three ReLU terms to create a localized "bump" of attention, allowing for sharper focus on local context.
- Centered Values: To ensure mathematical stability and align with conditionally positive definite kernels, value vectors are centered by subtracting their mean.
- Scale-Based Normalization: Instead of the probability simplex used in softmax, Sliced ReLU employs a scale-based normalization found to be more stable for this specific kernel.
Experimental Results
Long Range Arena (LRA)
Sliced ReLU attention outperformed the standard softmax baseline on the LRA benchmark, achieving an average score of 62.9 compared to 59.8. The most dramatic improvement was seen in the Pathfinder task, where accuracy rose from 72.2% to 89.9%.
Efficiency and Throughput
On sequences of length 4,000, Sliced ReLU achieved approximately 4x higher inference throughput and 2.5x faster training than the softmax baseline. This efficiency allows for the processing of significantly longer contexts on standard hardware.
Point Cloud and Vision
On the ModelNet40 point cloud dataset, the ReLU-bump variant achieved 85.4% accuracy, nearly matching the 86.3% of standard softmax. While standard attention still generalized better on Tiny ImageNet, Sliced ReLU showed robust performance across diverse modalities.
Geometric Inductive Bias
A significant advantage of the Sliced ReLU mechanism is its strong inductive bias for discovering data structure. The ReLU-bump variant naturally learns structured attention maps—such as banded, block-sparse, or multi-block patterns—without explicit supervision.
These patterns demonstrate the model's ability to adapt its attention mechanism to the inherent syntax and semantics of the input sequence, as seen in the varied structures for different sentence types. The proof that Sliced ReLU is a universal approximator ensures that these learned structures can represent any complex sequence-to-sequence mapping.
Conclusion
By leveraging sorting as a computational primitive, Sliced ReLU attention provides a scalable alternative to standard softmax attention. It maintains theoretical parity with the original Transformer while offering the quasi-linear complexity necessary for next-generation long-context modeling.