LaplacianFormer:Rethinking Linear Attention with Laplacian Kernel

arXiv:2604.20368v1 Announce Type: cross Abstract: The quadratic complexity of softmax attention presents a major obstacle for scaling Transformers to high-resolution vision tasks. Existing linear attention variants often replace the softmax with Gaussian kernels to reduce complexity, but such approximations lack theoretical grounding and tend to oversuppress mid-range token interactions. We propose LaplacianFormer, a Transformer variant that employs a Laplacian kernel as a principled alternative to softmax, motivated by empirical observations and theoretical analysis. To address expressiveness degradation under low-rank approximations, we introduce a provably injective feature map that retains fine-grained token information. For efficient computation, we adopt a Nystrom approximation of the kernel matrix and solve the resulting system using Newton--Schulz iteration, avoiding costly matrix inversion and SVD. We further develop custom CUDA implementations for both the kernel and solver, enabling high-throughput forward and backward passes suitable for edge deployment. Experiments on ImageNet show that LaplacianFormer achieves strong performance-efficiency trade-offs while improving attention expressiveness.

Related

• VFA: Relieving Vector Operations in Flash Attention with Global Maximum Pre-computation
• MaMe & MaRe: Matrix-Based Token Merging and Restoration for Efficient Visual Perception and Synthesis
• RACE Attention: A Strictly Linear-Time Attention Layer for Training on Outrageously Large Contexts
• AdaSplash-2: Faster Differentiable Sparse Attention

Source: arXiv cs.AI | 2026-04-23