LaplacianFormer:Rethinking Linear Attention with Laplacian Kernel
This addresses scaling limitations in Transformers for vision tasks, offering a more efficient alternative with theoretical grounding, though it is incremental relative to existing linear attention methods.
The paper tackled the quadratic complexity of softmax attention in Transformers for high-resolution vision tasks by proposing LaplacianFormer, which uses a Laplacian kernel and a provably injective feature map to improve expressiveness, achieving strong performance-efficiency trade-offs on ImageNet.
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 Nyström 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.