Sliced ReLU attention: Quasi-linear contextual expressivity via sorting

2025/12/12 by Boufadène, Siwan, Vialard, François-Xavier
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2512.11411

Abstract

We introduce sliced ReLU attention, a new attention mechanism that departs structurally from both softmax and ReLU-based alternatives. Instead of applying a nonlinearity to pairwise dot products, we operate on one-dimensional projections of key--query differences and leverage sorting to obtain quasi-linear complexity. This construction yields a differentiable, non-symmetric kernel that can be computed in O(n log(n)) through a sorting procedure, making it suitable for very long contexts. Beyond computational benefits, the model retains strong theoretical expressive power: we establish two in-context expressivity results, previously known for softmax attention, showing that sliced ReLU attention preserves the ability to perform nontrivial sequence-to-sequence disentangling tasks and satisfies a contextual universal approximation property. Finally, we illustrate the potential practical interest of this kernel in small-scale experiments.

Citations

• Numerical Methods for Kernel Slicing
• Statistical Advantage of Softmax Attention: Insights from Single-Location Regression
• Fast Large Deformation Matching with the Energy Distance Kernel
• ESPFormer: Doubly-Stochastic Attention with Expected Sliced Transport Plans
• A Comparative Study of Clinical ModernBERT and BioMedical ModernBERT on the DDXPlus Dataset
• Measure-to-measure interpolation using Transformers
• Theory, Analysis, and Best Practices for Sigmoid Self-Attention
• Transformers are Universal In-context Learners
• Scaling Laws for Linear Complexity Language Models
• Simple linear attention language models balance the recall-throughput tradeoff
• How Smooth Is Attention?
• Zoology: Measuring and Improving Recall in Efficient Language Models
• Sliceformer: Make Multi-head Attention as Simple as Sorting in Discriminative Tasks
• FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning
• Generative Sliced MMD Flows with Riesz Kernels
• The emergence of clusters in self-attention dynamics
• BEATs: Audio Pre-Training with Acoustic Tokenizers
• It's Raw! Audio Generation with State-Space Models
• Efficiently Modeling Long Sequences with Structured State Spaces
• Sinkformers: Transformers with Doubly Stochastic Attention
• LoRA: Low-Rank Adaptation of Large Language Models
• RoFormer: Enhanced Transformer with Rotary Position Embedding
• How to Train BERT with an Academic Budget
• Long Range Arena: A Benchmark for Efficient Transformers
• An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
• Efficient Transformers: A Survey
• A Mathematical Theory of Attention
• Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
• wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations
• Language Models are Few-Shot Learners
• Longformer: The Long-Document Transformer
• Sparse Sinkhorn Attention
• Reformer: The Efficient Transformer
• Are Transformers universal approximators of sequence-to-sequence functions?
• Lightweight and Efficient End-to-End Speech Recognition Using Low-Rank\n Transformer
• RoBERTa: A Robustly Optimized BERT Pretraining Approach
• Generalized Sliced Wasserstein Distances
• GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding
• Attention Is All You Need
• Swin Transformer: Hierarchical Vision Transformer using Shifted Windows

Related

• Softmax Attention with Constant Cost per Token
• Support Basis: Fast Attention Beyond Bounded Entries
• Reorganizing attention-space geometry with expressive attention
• Higher-order Linear Attention
• Sparse Attention with Linear Units