LaplacianFormer:Rethinking Linear Attention with Laplacian Kernel
Authors: Zhe Feng
Sen Lian
Changwei Wang
Muyang Zhang
Tianlong Tan
Rongtao Xu
Weiliang Meng
Xiaopeng Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: Linear Attention
Transformer
Kernel learning
Primary area: foundation or frontier models, including LLMs

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 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. Code is available at the following site: \href{https://mike7472727.github.io/laplacianformer.github.io/}{\textcolor{black}{LaplacianFormer }}.

Published as a conference paper at ICLR 2026
LAPLACIANFORMME:RRTHINNE TION WITH LAPLACIAN KERNEL
LINEAR ATTEN-
Zhe Feng*! Sen Lian Changwei Wang Muyang Zhang?! Tianlong Tan' Rongtao Xu? Weiliang Mengl.2i Xiaopeng Zhangl2
Institute of Automation, Chinese Academy of Sciences
School of Artificial Intelligence, University of Chinese Academy Sciences
China Electronics Data Corporation
'Institute of Computing Technology, Chinese Academy of Sciences
'The Key Laboratory of Computing Power Network and Information Security,
Ministry of Education, Shandong Computer Science Center, Qilu University of Technology "Shandong Provincial Key Laboratory of Computing Power Internet and Service Computing, Shandong Fundamental Research Center for Computer Science
Spatialtemporal AI
org, www.ann..enn@a.e....
ABSTRACT
The quadratic complexity of softmax attention presents a major obstacle for scal- ing Transformers to high-resolution vision tasks. Existing linear attention variants often replace the softmax with Gaussian kernels to reduce complexity, but such ap- proximations lack theoretical grounding and tend oversuppress mid-range token interactions. We propose LaplacianFormer a Transformer variant that employs Laplacian kernel as principled alternative softmax, motivated by empiri- cal observations and theoretical analysis. To address expressiveness degradation introduce provably injective feature map
under low-rank approximations, that retains ine-grrieed token information. For efficient computation, we adopt a Nyström approximation of the kernel matrix and solve the resulting system using Sowton-Schull 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. Ex- periments on ImageNet show that LaplacianForme achieves strong performance- efficiency trade-off's while improving attention expressiveness. Code is available at the following site: LaplacianFormer
INTRODUCTION
The Transformer architecture Vaswani et al. (017) has become fundamental framework for sequence modeling, demonstrating strong performance across wide range of computer vision tasks Diang Jians et al. (2024); Zhu al. (202T): Yu al. (2025); Hou al.) (2024); : [Su al.] (2024).
While its self-attention mechanism effectively captures rich contextual dependencies, its quadratic time and space complexity with respect to sequence length significantly limits scalability to long
input sequences Keles et al. (2022 Hassani et al. (2044).
To address this, a number of linear attention variants have been proposed to approximate softmax at- tention using kemee-bbased formulations, thereby reducing complexity to linear Katharopoulos et al. 2020 Lu et al. 2021): Chen et al. (202T) Bui et al. (2025): Kashiwagi et al. (022)) Notably, de- similar design choice: they rely on Gaussian-like kernels to define attention similarity. This widespread adoption appears be more default convention than a theoretically grounded decision. Indeed, there is a lack of empirical or analytical justification for why the Gaussian kernel is inherently suitable for modeling query-key interactions in attention mechanisms.
spite differences implementation. the vast majority of these methods converge
"Equal contribution.
Corresponding author.

---

Published as a conference paper at ICLR 2026
beft ittendion Q-K Vettor destance ettbution
Actertini Q Wettor diitance atribttion
Swth Attartion di Vidtee Diitance Citerbuttoon
Utrans
Linance
(a) DeiT
(b) PVT
(c) Swin
Figure Distributions & and & Q-K distances DeiT, PVT, and Swin Transformers.
Theoretically, the Gaussian kernel presumes that query-key similarity should decay rapidly with increasing eg distance. However, this assumption may not reflect the actual distribution query-key interactions in vision Transformers. To investigate this issue, we analyze the empirical distribution of query-key distances DeiT Touvron et al. (2020), PVT Wang et al. (2021b), and Swin Liu et al.) (2021b), using official checkpoints on the ImageNet Net Deng et al. (2009) validation set. As shown in Figure 1 the lg distances exhibit heavy-tailed distribution with high variance and frequent outliers. When passed through the exponential function in the Gaussian kernel, these long-tailed distances will lead to an amplification of the tail effect: outliers dominate the attention map, while moderately relevant keys overly suppressed. This behavior not only reduces the expressiveness of attention weights but also causes vanishing gradients and unstable optimization, especially during the early stages of training Zhang al. (2021). In contrast, & distances tend be more concentrated and less sensitive to outliers, providing a more faithful measure of token relevance. This observation
motivates the use of the Laplacian kernel, defined as k(x, = exp - where x, v E R& input feature vectors and À is decay parameter. Compared to the Gaussian kernel, which is based on squared &g distances, the Laplacian kernel exhibits a slower decay rate.
Aesumoo
(pp1 A
Epoch
Epoch
200
300
J0C
30C
206
Wm
06
09 205 201 R0
28 256 200 1M 20
SOFT-+ (Gaussian)
SOFT+ (Laplacion)
Skyfomeer (Gaussian)
Sky Skyformer (Laplacian)
Figure 2: (a) Top-1 accuracy (%) over training epochs on ImageNet. The left plot shows results for SOFT++, and the right plot for Skyformer, each using either Gaussian or Laplacian kernel for attention computation. Models with Laplacian kernels (blue) converge faster and achieve slightly higher final accuracy compared to their Gaussian counterparts (red). (b) Visual comparison of atten- tion maps with different kernel choices. Each pair shows attention maps from the first Transformer block of SOFT++ and Skyformer, where only replace the Gaussian kernel with Laplacian ker- nel, keeping all other components unchanged. Attention matrices computed with Laplacian kernels exhibit more structured patterns and centir-conditioned rank profiles.
Beyond empirical distributions, we further analyze the gradient behavior of these kernels, which plays critical role in optimization stability. For the Laplacian kernel, the partial derivative with
2

---

Published as a conference paper at ICLR 2026
respect to coordinate 2; Szz
0k (2: - ys) exp
|| -|ا-ج|1 while for the Gaussian kernel,
Sw; it is ak d (z: y:) exp 2
[-=vl= where a denotes the kernel bandwidth. Notably, the
Laplacian kernel maintains non-vanishing gradients even when I and y are nearly identical, owing to the piecewise linear nature of the & norm. In contrast, the Gaussian kernel's gradients diminish linearly ||æ- 7/l2 + resulting in vanishing updates that may hinder convergence. To empiri- cally validate this theoretical claim, we perform a simple ablation by replacing the Gaussian kernel two representative models-SOFT++ Lu al. (2024) and Skyformer (Cen al.] (2021)- wwith a Laplacian kernel, keeping all other architectural components unchanged. As shown in Figure 2 this modification alone leads to significantly faster convergence in both models, supporting the hy- pothesis that the Laplacian kernel facilitates more stable and efficient learning dynamics. Beyond training behavior, we also compare attention maps produced by the two kernels. The same figure also visualizes attention from the first Transformer block of both models. In SOFT++, the Gaussian kernel yields overly sparse attention, while the Laplacian variant produces more expressive and co- herent patterns. A similar trend is also observed in Skyformer. These results suggest that, beyond its theoretically favorable decay profile, the Laplacian kernel also improves the practical expressiveness of attention maps, particularly in early to mid-stage layers.
Motivated by these findings, we introduce Laplacian Former, scalable linear attention framework that replaces the -aassian-based attention mapping with a Laplacian formulation. To support prac- tical deployment, we develop CUDA-accelerated implementation that features efficient Laplacian similarity computation and a Newton-Schulz SchuSc-hasssssss inverse solver for fast inference. As shown in
ImageNet Top-1 Accuracy (%)
Themafor aborrer
x
Unfamrrr
Memory (MB)
Appethommr
SOFT
ketverer
Suih
Mymrorfforvve
CMT
Token sequence length
Mest
(a)
Figure 3: Accuracy and Memory Comparison.(a) Top-1 accuracy vs. FLOPs on ImageNet- Ik Deng jet al.) (2009). LaplacianForrmer offers a strong accuracy-efficiency trade-off, outperforming prior models across all FLOPss ranges. (b) GPU memory usage across input lengths. LaplacianFormer shows linear scaling, matches efficient Transformers like Performer and SOFT, and far better than the vanilla Transformer.
Figure LaplacianFormer achieves strong performance across accuracy, memory efficiency, and scalability metrics standard vision benchmarks.
Our main contributions are summarized as follows:
We propose LaplacianFormen linear attention model grounded in the Laplacian ker- nel, which enhances long-range dependency modeling while maintaining scalability and efficiency.
We develop a CUDA-optimized implementation that integrates Laplacian attention with Newton-Schul) inverse module, significantly improving runtime and memory efficiency.
We validate LaplacianFormer on ImageNet- 1k Deng et al. (2009) and downstream vision tasks such as object detection and instance segmentation, demonstrating competitive per- formance across multiple benchmarks.
2
RELATED WORK
Vision Transformer with Softmax Attention. The Vision Transformer (ViT) Dosovitskiy et al. 2021 has demonstrated exceptional performance and has been widely adopted for range of
3

---

Published as a conference paper at ICLR 2026
computer vision tasks, including image classification Touvron al. (2021): D:: Liu et al. 2222
Touvron et al. (2022), object detection Zhu et al. (2021): Zhang et al. (2023a), , and semantic seg- mentation Zheng et al. (2020); Xie et al. (2021); Cheng al. (2021). By substituting traditional convolutional operations with self-attention mechanisms, ViT enables the modeling of global de- pendencies within images, offering a powerful alternative to convolutional neural networks (CNNs). However, a major bottleneck lies in the quadratic time and memory complexity. O(n²), of stan- dard softmax attention, which significantly restricts its scalability for high-resolution inputs- and limits its deployment on resource-constraine edge devices.
Linear Attention: A Scalable Alternative. To mitigate the computational overhead of softmax attention, linear attention has emerged as an efficient alternative. While softmax attention requires (( operations to compute pairwise similarities, linear attention reduces this ((Nd²) by replacing the softmax with kernel-based approximations and reordering computations. Specifically, computing '" first decouples the attention process and enables linear scalability. This efficiency gain becomes particularly significant in modern Transformers, where the token count N typically exceeds the channel dimension d. Linear attention thus maintains the ability to model long-range dependencies while substantially improving computational efficiency.
Building on this foundation, a number of linear attention variants have been developed to reduce computational cost while enhancing model capacity. Nyströmformer Xiong al. (202I) approxi- mates softmax attention via Nyström matrix decomposition. SOFT Lu et al. (2021) replaces soft- max with learnable kernel based on low-rank approximations. Skyformer Chen et al. (202T) in- corporates Gaussian kernels and Nyström sampling to improve scalability in vision tasks, while Gaussian Kernelized Attention Kashiwagi al. (202I) applies similar design to speech decoding. Performer Choromanski el al. (2021) employs orthogonal random features (FAVOR+) to achieve linear-time softmax approximation. Cosformer Qin al. (2022) replaces softmax with a cosine- based reweighting scheme to achieve linear complexity. Hedgehog Zhang et al. (2024) introduces structured linear transformations alternative. HiViT /Zhang et al. (2023b) streamlines hierarchical Transformers by reducing token mixing and applying uniform downsampling.
approximate softmax behavior, providing unified and scalable
While differing in architecture, many of these methods share common reliance Gaussian kernels to approximate attention weights. this work, we replace the Gaussian kernel with a Laplace kernel that ensures injectivity and enhances expressiveness, grounded in rigorous theoretical analysis.
PRELIMINARIES
3.1 SOFTMAX SETENTITEN
Softmax self-attention is core operation in transformer models. Given input sequence X N xd, of N tokens embedded in a de-dimensional space, we compute queries, keys, and values via XW V XWr, where Wq, Wx, Wy Rd. xd are learnable parameters and Q K. V Nxd. The standard scaled dot dot-product attention for token is:
linear projections:Q X XWq q: K
Σn exp
k vi V
(artoonQQQ. Attention Q Q)
(1)
Σn exp
9. kj vdd
and in matrix form:
QKT Vd
Attention K,
K. V) = Softmax
V
(2)
This formulation computes similarity matrix QK E RNN resulting in O(N d) complexity due to all pairwise interactions. To reduce cost, consider removing the softmax. Without it, attention simplifies QK"
V, which can be reordered Q(K V) using associativity. This avoids Va
forming the large N N matrix and reduces complexity to ((Nd²), linear in N if d is small. This insight underlies linear attention, which replaces softmax with associative operations for improved efficiency. Figure F compares softmax and linear self-attention.
4

---

Published as a conference paper at ICLR 2026
K
QK
K
K'
XV
X N
x
N.X
dxN
x
Softmax Self-A ttention
L inear Self-Atiention
Figure 4: Comparison between Softmax Self-Attention (left) and Linear Self-Attention (right). The former computes full N x N similarity matrix, while the latter enables associativity through kernel decomposition, reducing the complexity from O(N2) to O(N).
3.2 LINEAR SELF-ATTENTION
Linear self-attention reformulates the attention mechanism by approximating the similarity compu- tation through semel-based feature mappings. Specifically, let o(.) denote a kernel function, and define the similarity between query q: and key ky Sim ky) ((q:) p(k,)
The kernel-based formulation replaces the exponential dot product with a more general similarity function, enabling efficient reordering of computations and eliminating the softmax operation. The attention output for the i-th query can be written as:
Attention( Q, V), ((q:) EE (kk) Tv;))
o(q:) E o(₁,) )
Since the key-value summaries Σj=1 (k2, Tv, V, and Σ (ky) independent of the query, they can be precomputed, allowing each attention output be computed in linear time.
4 METHOD
4.1 LAPLACIANFORMER
Our LaplacianFormer instantiates the general kernel attention framework described Section 3.2 using novel Laplace-based transformation inspired by recent work on attention injectivity Han ctt al. (2024a). Instead of directly using the Laplacian kernel as similarity score, we construct normalized kernel representation for each query to enhance feature discrimination:
2, Fー (1) ((,))...,,,,,kx)
Σ k(q, kj)
+ N
denotes the Laplacian kernel. The whitening matrix Σ 1-1/2 NNN is ideally computed from the covariance of query-key similarity vectors gi R where each g: = [k(q;, .,) k(q; T.
where loq,, k)
exp
(- | kl11
1/2
In practice computing the full inverse square root Σ- 1/2 computationally prohibitive for long sequences, requiring cigendecomposition with ( time and O(N2) memory. To mitigate this, we approximate the whitening operation with a diagonal estimator that normalizes each feature dimension independently across batch of query-key vectors {g:), where B is the batch size.
For each dimension j E {1,.... B.....NY, N). we compute the empirical mean and variance:
B
1 B
P9
Σ
Búj.
gu
m1y)²
(5)
B
i=1
We then normalize each element the similarity vector:
gij
R: Vot+s
where e is small constant
added for numerical stability. This corresponds to a diagonal whitening matrix:
1
D 1/2 diag
(6)
Vo
VoN
+
5

---

Published as a conference paper at ICLR 2026
This approximation preserves the centering and scaling effects of full whitening, improves stability, and reduces both time and memory complexity from quadratic to linear in N, making it compatible with efficient kernelized attention. For completeness, we define the kernel similarity matrix among keys as G2 = kk,,, kj), Σhey = PGPT, with P I $11_ Although not directly used in normalization, the key-key covariance Eayy provides useful interpretation of the kernel structure.
We prove in the appendix that the transformation in Eq. equation + is injective under mild assump- tions, ensuring that distinct queries yield distinct outputs. This injectivity property aligns with the behavior of softmax attention, which is inherently injective and yields full-rank attention maps that preserve fine-grained token distinctions Han et al. (2024a). The final attention output incorporates both global interactions via kernliized similarity and local context modeling through depth-wist wise convolution. Specifically, we compute
Attention( Q K. V) ZV DWC(V),
where Z RNNN stacks each z as row, and DWC(-) denotes depth-wise convolution applied over the value sequence V.
4.2 NYSTRÖM APPROXIMATION FOR LAPLACTAN KERNEL.
To efficiently compute Laplacian kernel-based attention, we adopt a Nyström approxima- tion Williams Seeger (2000); Xiong al. (2021). The Nyström method approximates the ker- nel matrix G by selecting a small set of landmark keys and computing a rank-reduced estimate G E RNNNN, defined as G = CWICT, where C E IRN xm is the matrix of Laplacian kernel simi- larities between all queries and a selected subset of m < N landmark keys, W m contains pairwise Laplacian kernel similarities among the m selected landmark keys, and Wt denotes the Penro-e pseudoinverse of W. More specifically, the (i, f)-th entry of defined as:
Ci = k(q ke) exp (- |1 -
(1ll))
8
the f-th landmark key, while where qi is the query vector of the i-th token and ke E {ki,..., .......,, ... } the (e, l') )')-th entry of W is computed as:
likee qe) = exp (- q lll.)
e
where ke and qe are the landmark key and query vectors selected by Nyström sampling, respec- tively.
The process for computing the low-rank Laplacian kernel via Nyström approximation outlined in Algorithm [ In Line 2, the sampling function fs selects m < N landmark tokens from the full set of queries and keys, forming the landmark matrices Q K Roxd Lines 3-5 perform the
kernel operations: Line 3 computes the landmark kernel matrix W (Eq, D). Line 4 computes the query-to-landmark kernel matrix C (Eq. 8 and Line 5 applies the Nyström approximation using
wi to obtain the final attention matrix S.
Algorithm 1 Laplacian Kernel with Nyström Approximation
1: Input: Queries Q E Nxd Keys e R.xx Nyström sampling function fs
2: Sampling: Q, K < [(())
Selecct m < n landmark points
3: W + exp
1 K|11)
Kernel matrix on sampled points
4: - exp
e K||I)
D Cross-kernel between all queries and landmarks
5: & CWiCT
> Low-rank approximation of full kernel matrix
6: Output: &
Laplacian Kernel Inversion via Newton-Schulz Iteration. To efficiently and stably approximate the inverse of the landmark kernel matrix W E mm which is symmetric and positive semi- definite, we the Newton-Schula iteration. Since convergence requires W be strictly positive

---

Published as a conference paper at ICLR 2026
Algorithm Newton-Schulz Iteration for Approximating W
1: Input: Landmark kemel matrix W E R number of iterations T E Z
2: Add small perturbation: W < W el, where e
3: Initialize scaling factor: a + I
4: Initialize: X & aW
5: for to T do
6: X₁ + x -
7: end for
8: Output: Approximate pseudoinverse X R W
NewTon-Schulz Kernel Execution Time
Laplace Kernel Execution Time
1.70
1.70
PyTorch Forward
Time (milliscconds)
PyTorch Backward
1.50
10008
CUDA Backward
1.50
0.4
0.41
0.6
0.5
2.2
0.0
0.0
0.0
Matrix Size (N)
Matrix Size (N)
Figure 5: Execution time breakdown of custom CUDA kernels. Comparison of forward and backward execution time for Newton-Schulz iteration (left) and Laplacian kernel (right) across dif- ferent matrix sizes (batch 1, 2 heads, 32 channels). CUDA execution times (<c 0.05ms) are shown as 0.0 due to timing resolution limits.
definite, apply small diagonal perturbation W W+ with > O, preserving the structure while ensuring stability. Unlike inversion or SVD-based methods, Newton-Schulz relies only on matrix multiplications and additions. making it GPU-friendly. The iteration starts with X.- = a W where a TW ensures ||I ||I- aWW || 1. The update rule is: X = Xx - WX.). The
full algorithm is detailed in Algorithm 2
Sampling Strategies for Landmark Selection. To efficiently approximate attention, we adopt posling-based landmark selection strategy inspired by PVTv2 Wang al. (2021a). The query tensor Q I Bx H x Xxxd; is reshaped into spatial map R x where N H' x W'. We apply average pooling with kernel size and stride r to aggregate each r x region into a landmark token, yielding
tokens per head.
We also explored depthwise convolution- bbssed selection strategy, in which each region is processed by lightweight filter to extract local structure. While this approach offers greater expres- siveness, yielded no significant improvement over average pooling our experiments. Given its higher computational cost and additional parameters, we adopt average pooling by default.
Convergence Guarantee and Complexity Analysis. The Newton-Schulz iteration is guaranteed to converge for strictly positive definite matrices; this condition is satisfied by applying small diagonal perturbation to W. Our method achieves linear time and space complexity O(n) with respect to the input length n. A complete complexity analysis and proof of convergence are provided in the appendix.
4.3 CUDA ACCELERATION
The Laplacian kernel fuses distance computation and exponential transformation into single oper- ation, reducing global memory access. For Nowton-Schull iteration, we optimize matrix multipli- cations via tiling and register reuse.
7

---

Published as a conference paper at ICLR 2026
Table Performance comparison with state-of-the-ar models on ImageNet.
FLOPs range
Model
Params
FLOPs
Top-1 %+
Image Size
Agent-Deit-l Hon et (20246
6.0M
1.2G
74.9
224
VRWKV-T Duan
2025
6.2M
1.2G
75.1
256
< 3G
PVT viree Meng eial.
2025
12M
2.0G
78.8
224
FL-PVTV2-BI Han
13M
2.2G
79.5
224
BiFormer-T Zhh al 2025
13.1M
2.2G
81.4
224
Laplacian
InLine CSwin S Iaan
2024g)
33M
6.8G
83.8
224
SVTT Huang et 2004
25M
4.4G
83.6
224
BiFormer
A172
25.5M
4.5G
83.8
224
3~-8
HiVIT-I Zhang cl 01250
19M
4.60
82.1
224
Agent PVT
SiplacianFormer SSmall
25.7M
4,80
83.8
224
SVT-BB Huang ot all 22033
52M
9.9G
84,8
224
8w100G
SOFT+ Circt (2024
45M
83.7
BiFormer- Zhu el (2223
56,8M
9.80
84.3
224
Polaivomerr
SB-SSSwi Guo (
8.7G
81.8
224
FaplacinnFormtrMMSSi
7,43G
85.3
StructViT-B----
(2024
Lorge+ La 2224
64M
11G
84.1
224
MogaNer-L oF al (TT4
82.5M
15.9G
84.7
224
FLattca-CSWi1-- Hal
2023
35M
6.9G
83.6
224
Laplacian Former
63.1M
11.2G
85.6
224
VRWKY-B Duan et all K2025
93.7M
18.20
82.0
224
Huung
>> 14G
MLLA- A.LA-B]Ee Hai at
96M
16.2G
85.3
224
HiVIT-B Zlanng ar
20256
66M
15.9G
83.8
224
Luplaciana
78.5M
15.5G
85.8
224
To assess the effectiveness of our CUDA acceleration, we compare the execution time of both Lapla- cian kernel evaluation and Newton-Schulz iteration against their PyTorch counterparts Paszke et al. (2017), with and without custom CUDA kernels. As shown in Figure our implementation consis- tently outperforms the baseline across various matrix sizes. The speedup is particularly prominent in backward passes, which benefit from precomputed gradients and in-place memory reuse. Numerical accuracy comparisons provided in the appendix.
EXPERIMENTS
5.1 IMAGE CLASSIFICATION
Datasets and model architectures. We evaluate our model on the ImageNet-1K 1K dataset Deng et al. (2009), which contains 1.28M training and 50K validation images across 1000 classes. Built on the PVT architecture WWan et al. (2021b). our LaplacianFormer re-designs the self-attention mechanism by constructing injective attention function based the Laplacian kernel. To sure training efficiency, we implement two custom CUDA kernels: one for computing the Laplacian kernel matrix and another for performing Newton-Schulz iteration approximate the inverse. Addi- tionally, SoPE[SU2 (2024) is adopted for positional encoding. All other settings follow the original PVT configuration. Training is performed with a batch size of 1024 on multiple NVIDIA H800 GPUs.
Comparison. We compare the Top-1 accuracy and computational cost of our LaplacianFormer against state-of-the-an Vision Transformers. As shown in Table [ models are grouped by FLOPs:<IG, 1-3G, 3-5G, 5-10G, and > 10G. LaplacianFormer consistently achieves the highest Top-1 1 accuracy across all FLOP ranges. This result demonstrates the superiority of LaplacianFormer over existing methods.
5.2 OBJECT DETECTION AND INSTANCE SEGMENTATION
Results. Table 2 summarizes the comparison results under the 1x schedule for both Mask R- CNN He et al. (2017) and RetinaNet Lin et al. (2017). Across all scales, LaplacianFormer consis- tently surpasses previous backbone designs. For instance, LapllciinnFormer-Ting achieves 43.2 A
8

---

Published as a conference paper at ICLR 2026
and 40.3 AP" under Mask R-CNN, outperforming SOFT++ Tiny and FL-PVT-T. Under RetinaNet, it further achieves 42.5 AP,, ranking first among all tiny-scale counterparts. As the model size in- creases, LaplacianFoormeet SappaaciiaFoomeeMMddiu yields 48.0 AP" and 43.5 AP", establishing new state-of-the- art within the medium-size category. These results highlight the strong generalization and detection capabilities enabled by our Laplacian kernel attention mechanism.
Table 2: Comparison to other backbones using RetinaNet and Mask R-CNN with "Ix" schedule.
Mask R-CNN Ix AP
RetinaNet
Backbone
Ap
Ap
Apm
A
AP75
Apb
AP
AP
AP
AP
APP.
Swin T PRenBN Gup el al. 2024
42.9
65.8
46.8
39.3
62.6
41.9
PV. Han et SOFT++ my Lurer 2024
38.2
61.6
41.9
37.0
57.6
39.0
41.2
63.7
44.7
38.2
61.0
41.0
41.9
62.7
44.7
27.8
45.4
55.6
Taplacian Tiny
42.5
64.1
46.9
57.8
SV PolalFomer Meng el al.
2025
43.9
66.1
47.9
40.2
63.1
43.0
43.2
64.1
46.4
Tnl int----VV Han
43.4
66.4
47.1
40.1
63.1
43.3
SOFT++-Smal al 2024
43.8
66.0
47.5
40. 1
63.0
43.0
43.7
64.9
46.8
28.7
47.4
57.6
LaplacianFormiss
49.8
65.1
45.5
66.8
30.7
51.8
59.5
Agent-PVT-M
(2024c
45.9
67.8
50.4
42.0
65.0
45.4
FL-Swin-M Han al 2025)
44.0
66.4
48.0
40.3
63.4
43.5
SOFT++-Maahmjj
SOFT++ Medium eu el
2024
46.6
67.8
51.2
42.0
64.8
45.2
44.3
64.7
47.4
29.0
48.2
59.9
CuplacianFormee Mechum
48.0
70.3
52.5
43.5
65.8
46.5
47.2
68.5
51.5
31.8
53.0
61.4
Poroaalerel Meny
2025
44.8
49.1
Ageat-PVT-L Han of all 20240
46.9
69.2
51.4
42.8
66.2
46.2
3OFT++-Lang at at
2024
47.0
68.3
51.7
42.2
65.2
45.4
47.0
67.8
50.4
30.2
50.9
62.0
Aaplacianl-orne Large
48.2
70.5
53.0
43.8
67.1
47.4
48.5
69.3
52.4
32.6
52.3
63.8
5.3 ABLATION STUDIES
Convergence Under Varying Condition Numbers. We evaluate solver convergence across vary- ing condition numbers. We measure the relative error for Newton-Schulz using the Frobenius norm and for CG using the Euclidean norm || x= ||||/ / ||x" Al2.As shown in Figure CG converges more rapidly under well-conditioned settings (e.g., K = 2) but degrades sig- nificantly as the condition number increases. In contrast, Newton-Schulz exhibits an initial warm-up phase followed by stable convergence even under ill-conditioned regimes (e.g.. K 50), indicating greater robustness in practice.
||X
Wt |///r//[WtTl
6
Condition Number =
Condition Number = 10
Condition Number = 50
Mevton-Sohuu c Conlugena
10a
Mewitn-ddhill Corjugate Cradirt
10"
Mantor- Sowttr-Sddus
Conbugate Gradeet
Relaive Eror (lg Scalet
10
Wlg scale
10:1
10
101
30
20
30%
Ratetive
30%
10
30'4
30'4
10
10
20"14
2.5
Iteranton
Iteration
Figure 6: Convergence behavior of Newton-Schulz and conjugate gradient methods under varying condition numbers. Each plot shows relative enror (log scale) vs. iteration.
Inverse Solver Effect. We compare two iterative solvers-Newton-SShhee (used in our model) and conjugate gradient (CG) for computing the kernel inverse in linear attention, both implemented with custom CUDA kernels. As shown in Table 33, Newton -choulz achieves higher Top-1 accuracy than CG for both LaplacianFormer-TT Tinny (81.4% vs. 79.2%) and LaplacianForrer-SSme (83.8% vs. 81.4%), likely due to better GPU convergence and numerical stability.
Effeet of Laplacian Kernel Scale. We study the impact of the Laplacian kemel scale À in the similarity function sim k) exp
As shown in Table 3 the model achieves the

---

Figure 7: Visualization of attention maps under different Laplacian kernel scales A. From left to right: À = 0.5, 1, 8. Published as a conference paper at ICLR 2026
best Top-1 accuracy (81.4%) when 4. Small À values (e.g.. 0.5, 1) overly suppress long-range interactions, while large values (e.g., 8) yield overly smooth attention, diluting local detail. An intermediate scale (A 4) balances local sensitivity and global context, and is thus fixed in all experiments. Attention map visualizations (Figure 7 further validate this choice.
Table 3: Ablation studies on Laplacian architecture. (left) Top-1 accuracy (%) of LaplacianFormer variants using different inverse solvers: conjugate gradient (CG) vs. Newton-Schulz (right) Effects of the Laplacian kernel scale À on Faplacian
Model
CG (%)
NS (%)
0.5
2
4
8
LaplacianFormec Tiny
79.2
81.4
Top-1 Acc (%) 79.4
79.6
80.1
81.4
78.5
LaplacianFormer-S5 Former-Small
81.4
83.8
CONCLUSIONS AND FUTURE WORK
We propose LaplacianFormer, a Transformer variant that employs Laplacian kernel construct injective and normalized attention, enabling fine-grained token discrimination with linear com- plexity. To ensure scalability, we adopt the Nyström approximation and accelerate computation via Sowtton-cchlzz iteration, with efficient CUDA support for both forward and backward passes. LaplacianFormer strikes balance between expressiveness and efficiency, performing well on both vision and long-sequence tasks. Moreover, it achieves strong results on downstream applications such as object detection and segmentation, further demonstrating generalization capability.
This work specifically focuses comparing Laplacian and Gaussian kernels the latter being the dominant choice in prior linear attention models Katharopoulos et al. (2020); Lu al. (2021): Chen [Chen et al. 202T). Our goal is challenge this convention through both theoretical analysis and empirical validation. Broader comparisons with other kernel families (e.g., cosine, polynomial) are left as future work.
ACKNOWLEDGMENTS
This work was supported by Beijing Natural Science Foundation (L2310013, L241056, JQ23014),
National Natural Science Foundation of China (Nos. 62376271. U22B2034, 62572059, and 62365014), Jiangxi Provincial Natural Science Foundation (No. 20253BAC280104) Shenzhen S&T Programme (No. CIGIZA22224022
Taishan Scholars Program No.1$Q0N02507241,, Key R&D Program of Shandong Province, China No.2025KJH2013, Shan- dong Provincial University Youth Innovation and Technology Support Program No. No.2022KJ291, Shandong Provincial Natural Science Foundation for Young Scholars Program No. No.2R2225QC1627.
Qilu University of Technology (Shandong Academy of Sciences) Youth Outstanding Talent Program No. 2024QZJHO2. Open Project of Key Laboratory of Computing Power Network and Information Security (No. 2024PY021). and the Open Project Program of State Key Laboratory Virtual Real- ity Technology and Systems, Beihang University (No. VRLAB20251003)
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 127063, 2024. ISSN 0925-2312. doi: https://doi.orge ortp//00...r//....
Long Minh Bui, Tho Tran Huu, Duy Dinh, Tan Minh Nguyen, and Trong Nghia Hoang. Revisiting kernel attention with correlated gaussian process representation. ArXiv, abs/2502.20525, 2025.
Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian kernel and nyström method. In Neural Information Processing Systems, 2021.
Bowen Cheng, Alexander G. Schwing, and Alexander Kirillov. Per-pixel classification is not all you need for semantic segmentation. In Neural Information Processing Systems, 2021.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller. Rethinking attention with per- formers. In International Conference on Learning Representations, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, K. Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenbor, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Yuchen Duan, Weiyun Wang, Zhe Chen, Xizhou Zhu, Lewei Lu, Tong Lu, Yu Qiao, Hongsheng Li, Jifeng Dai, and Wenhai Wang. Vision-rwkv: Efficient and scalable visual perception with rwky-like architectures. 2025.
Jialong Guo, Xinghao Chen, Yehui Tang, and Yunhe Wang. Slab: Efficient transformers with sim- plified linear attention and progressive re-parameterized batch normalization. In International Conference Machine Learning, 2024.
Dongchen Han, Xuran Pan, Yizeng Han, Shiji Song. and Gao Huang. Flatten transformer: Vision transformer using focused linear attention. 2023 IEEE/CVF International Conference Com- puter Vision (ICCV), pp.
2023.
Dongchen Han, Yifan Pu, Zhuofan Xia, Yizeng Han, Xuran Pan, Xiu Li, Jiwen Lu, Shiji Song, and Gao Huang. Bridging the divide: Reconsidering softmax and linear attention. In NeurlPS, 2024a.
Dongchen Han, Ziyi Wang, Zhuofan Xia, Yizeng Han, Yifan Pu, Chunjiang Ge, Jun Song, Shiji Song, Bo Zheng, and Gao Huang. Demystify mamba in vision: A linear attention perspective. In NeurlPS, 2024b.
Dongchen Han, Tianzhu Ye, Yizeng Han, Zhuofan Xia, Siyuan Pan, Pengfei Wan, Shiji Song, and Gao Huang. Agent attention: On the integration of softmax and linear attention. European Conference Computer Vision, pp. 124-140. Springer, 2024c.
Ali Hassani, Steven Walton, Jiachen Li. Shen Li, and Humphrey Shi. Neighborhood attention trans- former. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 6185-6194, June 2023.
Ali Hassani, Wen-mei Hwu, and Humphrey Shi. Faster neighborhood attention: Reducing the o(n2) cost of self attention at the threadblock level. In Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak. and C. Zhang (eds.). Advances in Neural Information Processing Systems, volume 37, pp. 64717-64734, 2024.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross B. Girshick. Mask r-cnn. 2017 IEEE Inter- national Conference Computer Vision (ICCV), pp. 2980-2988, 2017.
11

---

Published as a conference paper at ICLR 2026
Zhichao Hou, Weizhi Gao, Yuchen Shen, and Xiaorui Liu. Protransformer: Robustify transformers via plug-and-play paradigm. In ICLR 2024 Workshop on Reliable and Responsible Foundation Models, 2024.
Huaïbo Huang, Xiaoqiang Zhou, Jie Cao, Ran He, and Tieniu Tan. Vision transformer with super token sampling. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 12703-12712, 2023.
Siyuan Jiang, Senyan Xu, and Xingfu Wang. Rbsformer: Enhanced transformer network for raw image super-resolution. 2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 6479-6488, 2024.
Yosuke Kashiwagi, Emiru Tsunoo, and Shinji Watanabe. Gaussian kernelized self-attention for long sequence data and its application to cte-based speech recognition. ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6214-6218, 2021.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and Franccois Fleuret. Transformers are mnss: Fast autoregressive transformers with linear attention. In International Conference Ma- chine Learning, 2020.
Feyza Duman Keles, Pruthuvi Maheshakya Wijewardena, and Chinmay Hegde. On the computa- tional complexity of self-attention. In International Conference on Algorithmic Learning Theory, 2022.
Manjin Kim, Paul Hongsuck Seo, Cordelia Schmid, and Minsu Cho. Learning correlation structures for vision transformers. 2024 IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 18941-18951, 2024.
Siyuan Li, Zedong Wang. Zicheng Liu, Cheng Tan, Haitao Lin, Di Wu, Zhiyuan Chen, Jiangbin Zheng, and Stan Z. Li. Moganet: Multi-order gated aggregation network. In International Con- ference on Learning Representations, 2024.
Tsung-Y Yi Lin, Priya Goyal, Ross B. Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. 2017 IEEE International Conference on Computer Vision (ICCV), pp. 2999 3007, 2017.
Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie, Yixuan Wei, Jia Ning, Yue Cao. Zheng Zhang, Li Dong, Furu Wei, and Baining Guo. Swin transformer v2: Scaling up capacity and resolution. 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11999-12009, 2021a.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. 2021 IEEE/CVF In- ternational Conference on Computer Vision (ICCV), pp. 9992-10002, 2021b.
Jiachen Lu, Jinghan Yao, Junge Zhang, Xiatian Zhu, Hang Xu, Weiguo Gao, Chunjing Xu, Tao Xiang, and Li Zhang. Soft: Softmax free transformer with linear complexity, Advances in Neural Information Processing Systems, 34:21297-213099 2021.
Jiachen Lu, Junge Zhang, Xiatian Zhu, Jianfeng Feng, Tao Xiang, and Li Zhang. Softmax-free linear transformers. International Journal of Computer Vision, 133(6):3355-3374 August 2024. doi: 10. 10.10077/112233-24-00200
Weikang Meng, Yadan Luo, Xin Li, Dongmei Jiang, and Zheng Zhang. Polaformer: Polarity- aware linear attention for vision transformers. In The Thirleenth International Conference on Learning Representations, 2025.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
12

---

Published as a conference paper at ICLR 2026
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. The Tenth International Conference Learning Representations, 2022.
Wei Su, Peihan Miao, Huanzhang Dou, and Li. Scanformer: Referring expression comprehension by iteratively scanning. 2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 13449- 13458, 2024.
Hugo Touvron, Matthicu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herv'e J'egou. Training data-efficient image transformers & distillation through attention. In International Conference Machine Learning, 2020.
Hugo Touvron, Matthieu Cord, Alexandre Sablayrolles, Gabriel Synnaeve, and Herv'e e J' e'ggo.. Go- ing deeper with image transformers. 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 32 42, 2021.
Hugo Touvron, Matthieu Cord, and Herv'e J'egou. Deit ii:: Revenge of the vit. In European Conference on Computer Vision, 2022.
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Neural Information Processing Systems, 2017.
Wenhai Wang, Enze Xie, Xiang Li, Deng- Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pvt v2: Improved baselines with pyramid vision transformer. Computational Visual Media, 8:415
424, 2021a.
Wenhai Wang. Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pyramid vision transformer: A versatile backbone for dense prediction without convolutions. 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 548- 558, 2021b.
Christopher K. I. Williams and Matthias W. Seeger. Using the nyström method to speed up kernel machines. In Neural Information Processing Systems, 2000.
Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, José Manuel Álvarez, and Ping Luo. Segformer: Simple and efficient design for semantic segmentation with transformers. In Neural Information Processing Systems, 2021.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Moo Fung, Yin Li, and Vikas Singh. Nyströmformer: A nyström-based algorithm for approximating self-attention. Proceedings of the ... AAAI Conference Artificial Intelligence. AAAI Conference Artificial Intelligence, 35 14138-111441 2021.
Hyunwoo Yu, Yubin Cho, Beoungwoo Kang, Seunghun Moon, Kyeongbo Kong, and Suk-Ju Kang- Embedding- freee transformer with inference spatial reduction for efficient semantic segmentation. In Aleš Leonardis, Elisa Ricci, Stefan Roth, Olga Russakovsky, Torsten Sattler, and Gül Varol (eds.), Computer Vision ECCV 2024, pp. 110. 2025.
Hao Zhang, Feng Li. Shilong Liu, Lei Zhang, Hang Su, Jun Zhu, Lionel Ni, and Hleng-YYung Shum. DINO: DETR with improved denoising anchor boxes for end-to-end object detection. In The Eleventh International Conference Learning Representations, 2023a.
Michael Zhang, Kush S. Bhatia, Hermann Kumbong, and Christopher R'c. The hedgehog & the porcupine: Expressive linear attentions with softmax mimicry. In The Twelfth International Con- ference Learning Representations, 2024.
Xiaosong Zhang, Yunjie Tian, Lingxi Xie, Wei Huang, Qi Dai, Qixiang Ye, and Qi Tian. Hivit: A simpler and more efficient design of hierarchical vision transformer. In The Eleventh International Conference Learning Representations, 2023b.
Yifan Zhang, Bingyi Kang, Bryan Hooi, Shuicheng Yan, and Jiashi Feng. Deep long-tailed learning: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45:10795- 2021.
13

---

Published as a conference paper at ICLR 2026
Sixiao Zheng, Jiachen Lu, Hengshuang Zhao, Xiatian Zhu, Zekun Luo, Yabiao Wang, Yanwei Fu, Jianfeng Feng, Tao Xiang, Philip H. S. Torr, and Li Zhang. Rethinking semantic segmenta- tion from sequencceto-sequeeee Computer Vision and Pattern Recognition (CVPR), pp. 6877-6886, 2020.
perspective with transformers. 2021 IEEE/CVF Conference on
Lei Zhu, Xinjiang Wang, Zhanghan Ke, Wayne Zhang, and Rynson Lau. Biformer: Vision trans- former with bi-level routing attention. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023.
Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai. Deformable DETR: deformable transformers for end-to-end object detection. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
14

---

Published as a conference paper at ICLR 2026
A GRADIENT BEHAVIOR OF GAUSSIAN VS. LAPLACIAN KERNELS
Proposition 1 (Gradient Magnitude Decay in High Dimensions). Let x, E R4. As the distance |xx yll + O, the gradient magnitude of the Gaussian kernel decays linearly to zero. In contrast, the gradient magnitude of the Laplacian kernel remains at constant non-zero order proportional to vd.
Proof. Let y Rd. We analyze the & norm of the gradient with respect to denoted as | xx)x(x)))22
1. Gaussian kernel
The multi-dimensional Gaussian kernel is defined as:
|
Krauss (x. y) exp
2
The gradient vector with respect to x is:
l|t112
Gauss
02 exp
2o²
Taking the l norm the gradient yields:
|t|l2 o²
|| 2x
l|
exp
As ||tl| - 0, the exponential term approaches 1, resulting in:
||t||a o²
kGaus
This confirms that the gradient magnitude of the Gaussian kernel diminishes linearly zero as
x + y.
2.
Laplacian kernel
The dilli-ddimensoonll Laplacian kernel is defined as:
||t//2 A
Laplace (x, = exp
For 4 (vi E {l,..., df), the gradient vector is: +
Vxhitaplace - exp
|ttll1
where sign(t) E {-1, is applied element-wise The la norm this sign vector is ||sign(t)]la Vd. Taking the l norm the gradient yields:
vd exp
||t||1
V aapaae ||2
As the exponential term approaches resulting in: Vd X
V
Thus, in a d-dimensional space, the gradient magnitude of the Laplacian kernel is bounded away from zero and remains constant order vd/A.
B MATHEMATICAL PROOF
This section offers mathematical proofs for the propositions outlined in the main paper.
15

---

Published as a conference paper at ICLR 2026
Proposition 2 (Injectivity of Laplacian-based Kernel Embedding). Let qs Oj E R and define their kernel similarity vectors as
[k(q;, k.)...., k(qi, kN)]",
is the Laplaciann kernel, and (ki...., kN) C Rd is a fixed set of anchor points. Define the normalized feature mapping
where k(q, k) = exp (- ||
2; = --=--1/ g:
Σ 9
+ N
+
where Σ is the empirical covariance matrix over {gi), Suppose the key set is sufficiently rich such that qi + qj = gi * 8j. Assume further that for any qi + qj and E R, gi gj # cl (no constant-vector degeneracy). Then the mapping qi + 2, E IR is injective.
Proof. We proceed by contradiction. Assume that qi + qj but z; = Zzj
For notational convenience, let 14 = N/4 Σx= of denote the mean of the components of g: We can then rewrite the normalized feature mapping as:
1
2, = 1/21 gi p:1) +
1. N
Expanding the assumed equality z, Zj. obtain:
1 1/2 g: - ,, + N 1 -1= - 1111 + =
Subtracting the constant vector マ from both sides yields:
Σ //1/2 (11 = 1/2 1,)1)
Assuming non-degenerate cases where the covariance matrix E is strictly positive definite, 1/1 invertible. Left-multiplying both sides by 11/2 gives:
gi - 111 gi - 11
Rearranging the terms gives:
g gj = (#: - μ4 11
Let μ4 HJj where E IR is scalar. Then the equation becomes:
cl.
(10)
We now consider two mutually exclusive cases for the value of
Case 1: c 0.
Equation (T) implies g; gy- However, since assumed q, qj, this directly contradicts the proposition assumption that q; + qj = gi
gj.
Case 2: * O.
Equation (10) implies g, g, = cl for some scalar c. Since qi * qj. this directly contradicts the assumption of no constant-vector degeneracy.
In both cases, we arrive at a contradiction. Therefore, our initial assumption must be false. The only possibility is that z, 2j qi qi Thus, the mapping injective.
Proposition 3 (Linear-Timee Time Computation of Laplacian Feature Map via Nyström Approximation).
Let qi E Idd be query and (ki...,, km)
C IR be set of m landmark keys sampled via the
Nyström method, where m & N. Define the Laplacian kernel k:qq, k) cxp (- [|q-k]], and let
g: = =[K(q,,ki)) ki),,i),..... b.l....,,,(((..... kmm)
E R
16

---

Published as a conference paper at ICLR 2026
be the landmark kernel similarity vector for the i-th query. Assuming input dimension d and the number of landmarks m are constants with respect to the sequence length N, the normalized em- bedding
1 +
2, = 1-12
8:
(1I)
can be computed in ((m) time and space. Consequently, computing the feature maps for all N queries achieves an overall ((N) time and space complexity at inference time, provided that 1-1/2 approximated by an m m diagonal whitening matrix estimated offline.
Proof. The proof proceeds by analyzing the time and space complexity of computing the sequence of embeddings ....... n at inference time, based on the m sampled landmarks.
Step 1: Computation of the landmark similarity vector g: For each landmark key kj G 1,..., m,) computing the Laplacian kernel element / exp
|q k
requires:
1. Vector subtraction qi ky in IRd, which takes ((d) time.
2. Computing the L, norm of the resulting difference vector, taking (dd) time.
3. Scalar division by À and exponentiation, taking (11) time.
Since the input dimension assumed to be constant, computing one element g is bounded by O(d) (1). Computing all m elements for the vector therefore takes ((m) time. Storing the resulting vector g, requires (m) space.
Step 2: Centering the feature vector.
m Σド= K. Summing the elements of g; and dividing by takes ((m) time. Sub- tracting this scalar mean from each component of to compute the centered vector p4 takes an additional (m) time. The space required for the centered vector O(m).
Let μ4; 1
Step 3: Applying the whitening transformation.
By assumption, the m X m matrix 1/2 is approximated by a diagonal matrix computed offline. Let D diag(d1,-.. .......... d..)) be this diagonal approximation. The matrix-vector multiplication D(g: 1;1) reduces to an element-wise multiplication (Hadamard product) between the diagonal entries of D and the centered vector. This corment-wise operation takes ((m) time. Storing the diagonal of D requires (m)) space, and the resulting transformed vector also takes O(m) space. (Note: Without the diagonal assumption, a full matrix-vector multiplication would require O(m²) time).
Step 4: Adding the final bias term.
Adding the scalar constant m to each element of the resulting vector obtain the final normalized embedding z; E 1 requires (m)) time.
Conclusion:
For single query q: summing the time complexities yields ((m) + ((m) + O(m) + O(m) (m) inference time. Extending this operation the entire sequence of N queries results in a total inference time of N x O(m) O(N m.) Because the number of Nyström landmarks m is predefined parameter such that m & N, m acts constant with respect to the sequence length. Thus, the overall computation of the feature maps scales linearly, achieving O(N) time and space complexity.
17


Reviews:
[{"review_id": "audhpINeG5", "reviewer": "Reviewer_crNf", "summary": "This paper revisits linear attention and argues that the usual Gaussian kernel is not the best match for how query–key distances actually behave in vision Transformers. The authors show that distance distributions from real models (DeiT, PVT, Swin) are heavier-tailed, so a slower-decaying kernel is more appropriate. They therefore use a Laplacian kernel based on L1 distance, and make it practical with a Nyström-style approximation, a Newton–Schulz solver for the small kernel inverse, and a lightweight whitening step to keep the representation from collapsing. The method is evaluated on ImageNet-1K and COCO? (I guess..) (detection/segmentation) across several model sizes and generally matches or improves over existing efficient/linear-attention backbones. The paper is readable and implementation-minded.", "questions": "1. Can you include at least one non-Gaussian baseline to show that the improvement is tied to the Laplacian choice?\n2. Can you move a short version of the injectivity result into the main paper and state whether the Nyström step affects it?\n3. Do you use the same kernel scale for all stages/resolutions, or do you tune it per stage?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Motivation is concrete. The paper does not just say “we use another kernel,” but first measures Q–K distances from trained vision models and shows they are heavy-tailed. That gives a reasonable justification for trying a Laplacian kernel rather than the default Gaussian.\n2. The method goes beyond a trivial kernel swap. The injective feature mapping and diagonal whitening are intended to address the expressivity loss that often comes with low-rank/Nyström variants. Even if the theoretical part is short, the design is more careful than many incremental kernel papers.\n3. The implementation path is clear. Using Nyström plus Newton–Schulz and providing a CUDA-friendly formulation makes it more likely that people can actually run it.\n4. Experiments are not limited to a single classification model. The authors test on classification and dense prediction, and across multiple scales, which helps show the effect is not a one-off.", "weaknesses": "1. The comparison space is narrow. The central claim is that Gaussian is not ideal and Laplacian fits the data better, but the experiments mostly compare against Gaussian-style baselines. Including at least one other simple non-Gaussian/linearizable kernel (e.g. cosine-type) would make the claim more specific to Laplacian rather than “any slower decay works.”\n2. The injectivity argument is under-documented in the main text. It is mentioned and deferred to the appendix, but the reader cannot see clearly under what assumptions it holds or how much of it remains after the Nyström approximation. Since this is one of the few parts that differentiates the method conceptually, it should be stated more explicitly.\n3. The relation to recent Nyström/efficient ViT work could be clearer. Many recent papers also do landmark selection, low-rank approximation, and stabilization of the inverse. Here the novelty is framed as “Laplacian + Newton–Schulz + whitening,” but it would help to say more precisely what is new compared to those works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eEy6QtOKLs", "reviewer": "Reviewer_qL3Q", "summary": "This paper introduces LaplacianFormer, a Transformer variant that replaces the commonly used Gaussian kernel in linear attention with a Laplacian kernel to better capture heavy-tailed token distance distributions and enhance training stability.\n\n### Key Motivations:  \nEmpirical analysis of query–key distance distributions in DeiT, PVT, and Swin Transformers reveals a heavy-tailed pattern, inconsistent with the rapid decay assumed by Gaussian kernels.  \nThe proposed Laplacian kernel more accurately models this behavior and preserves non-vanishing gradients, leading to more stable and efficient optimization.\n\n### Methods:  \nThe authors design a provably injective attention mapping, ensuring that distinct queries produce distinct outputs and preserving fine-grained token relationships.  \nThey further employ a Nyström approximation combined with Newton–Schulz iteration to efficiently compute the kernel inverse, avoiding expensive matrix decompositions.  \nOptimized CUDA implementations are provided for both the Laplacian kernel and the solver, enabling scalable training and inference.\n\n### Experiments:  \nLaplacianFormer achieves faster and more stable convergence than Gaussian-based baselines (e.g., SOFT++, Skyformer).  \nIt delivers strong performance–efficiency trade-offs on ImageNet and COCO benchmarks and demonstrates linear memory scaling and robustness under high condition numbers, validating both the stability and scalability of the proposed approach.", "questions": "1. Equation (4) appears without derivation or explanation. Could the authors clarify how Equation (4) is obtained from the preceding formulation, and what assumptions or approximations lead to this step?  \n\n2. Why is the whitening matrix defined as $\\Sigma^{-1/2}A$ instead of $\\Sigma^{-1}A$?  \n   Typically, symmetric whitening uses $\\Sigma^{-1/2} A \\Sigma^{-1/2}$.  \n   Please explain the rationale behind this choice and how it affects the theoretical properties of the transformation.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### 1. Convincing analysis of Laplacian vs. Gaussian kernels\nThe paper provides a clear and well-supported theoretical and empirical comparison between Laplacian and Gaussian kernels.\nThe analysis of query–key distance distributions in vision Transformers (e.g., DeiT, PVT, Swin) convincingly shows that these distances follow a heavy-tailed pattern, making the Gaussian assumption unrealistic.\n\n### 2. Theoretical soundness and novel properties\nThe authors derive a provably injective attention mapping, ensuring that distinct queries produce distinct outputs.\nThis injectivity and the non-vanishing gradient property are both novel and important contributions that improve expressivity and optimization stability, addressing common issues like representation collapse in previous linear attention models.\n\n### 3. Methodological clarity and efficiency\nThe use of Nyström approximation and Newton–Schulz iteration for efficient kernel inversion is elegant and well-motivated.\nThe method maintains linear complexity while improving numerical stability.\nThe paper provides implementation details and custom CUDA optimization, supporting reproducibility and practical relevance.", "weaknesses": "### 1. Section 4.1 lacks coherence and clarity\nThe description of LaplacianFormer in Section 4.1 feels disconnected from the rest of the paper.\nIn earlier sections, the authors introduce linear self-attention and its approximation, but Equation (4) appears abruptly without derivation from Equation (3).\nSimilarly, Equations (8) and (9) in the approximation section are difficult to relate back to Equation (4), making the mathematical flow hard to follow.\n\n### 2. Limited experimental coverage\nOnly image classification and object detection are evaluated, which is insufficient to justify general claims about linear self-attention.\nThe paper should include more diverse and representative benchmarks such as:\n- Vision generation: DiT (Diffusion Transformers)\n- Vision–language: CLIP, BLIP, or Flamingo\n- Language modeling: The Pile\n- NLP understanding and reasoning: GLUE and ARC\n\nThese are widely used in prior efficient-attention works like Longformer, Performer, and FlashAttention.\n\n### 3. Limited novelty and missing discussion of limitations\nWhile the comparison between Laplacian and Gaussian kernels is well-analyzed, simply changing the kernel may not constitute a sufficiently strong contribution for a top-tier venue like ICLR.\nThe paper should also discuss the limitations of the Laplacian kernel, such as potential issues in scaling, expressivity trade-offs, or behavior in non-vision tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "klZDGzmy2D", "reviewer": "Reviewer_KiuY", "summary": "This paper proposes LaplacianFormer, a new Transformer variant that addresses the quadratic complexity of softmax attention by replacing the commonly used Gaussian kernel with a Laplacian kernel. The authors argue that the Laplacian kernel, based on $l_1$ distance, is better suited for the heavy-tailed distribution of query-key interactions in vision models, preventing the over-suppression of mid-range tokens. To ensure efficiency, the model uses a Nyström approximation solved via a CUDA-accelerated Newton-Schulz iteration, achieving good accuracy on ImageNet.", "questions": "1.  How does the diagonal whitening approximation (Eq. 6) preserve the claimed injectivity when Appendix A requires full-rank $\\Sigma^{-1/2}$? Can you provide a proof for the diagonal case?\n2. How does the query-dependent mean subtraction in Eq. 4 maintain $O(Nm)$ complexity when it couples all queries to all keys?\n3. Please fix the inconsistency for Table 3.\n4. The Gaussian gradient is linear in $(x_i - y_i)$ near zero, not quadratic as claimed - can you correct this analysis?\n5. The abstract mentions \"long input sequences\" but experiments are on 224×224 images - do you have results on actual long sequences?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Shows with real data that current Gaussian kernels oversuppress mid-range token interactions, making the Laplacian kernel a justified alternative.\n- Achieves best accuracy across all model sizes on ImageNet, showing the efficacy of the proposed method.\n• Uses GPU-friendly Newton-Schulz iteration that converges better than CG under poor conditioning.", "weaknesses": "- The \"provably injective\" claim relies on circular reasoning (Appendix A assumes $\\phi$ is already injective) and contains a mathematical error (Step 2 incorrectly claims centering preserves distinctness). The practical implementation uses diagonal whitening, further departing from the theoretical setup.\n- Claims that Gaussian kernel gradients \"diminish quadratically\" near zero are incorrect (they're linear in $x_i - y_i$).\n- The normalization (Eq. 4) includes query-dependent mean subtraction over all keys, which appears to break the precomputation trick. The paper doesn't show how Nyström factorization maintains $O(Nm)$ complexity with this coupling.\n- Table 3 reports different accuracy values (81.4% vs 79.2%) than the text claims (81.1% vs 77.8%) for the same comparison, and so is the other comparison.\n- Only compares against Gaussian kernels, not other alternatives (polynomial, cosine). No evaluation on truly long sequences despite abstract claims about scalability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WH7OXEB5oU", "reviewer": "Reviewer_sjHj", "summary": "This paper presents a Laplacian-kernel-based linear attention matrix approximation. The query-key distribution of a vision transformer is heavy-tailed, whereas a Gaussian kernel assumes fast-decaying tails. This motivates the use of a Laplacian kernel, which additionally improves gradient stability and attention map representation. To achieve linear computational complexity, the Laplacian kernel matrix is approximated via the Nyström method, where the time-consuming matrix inversion is replaced with GPU-friendly Newton–Schulz iterations. The Laplacian kernel was tested on ImageNet classification, object detection, and instance segmentation, achieving higher accuracy while using fewer FLOPs than other models.", "questions": "1. Why is the injectivity of Eq. 4 important? Is Softmax attention also injective?\n2. In addition to Weakness1, what is the latency of the forward and backward paths when using the basic PyTorch or CUDA matrix inversion functions (e.g., `torch.linalg.solve` or `torch.linalg.lstsq`)?\n\nMinor comments\n\n- The font sizes in the figures are too small.\n- Eq. equation 4 → Eq. 4 or equation 4 in Line 264.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "I am inclined to recommend acceptance of this paper because the proposed method makes a meaningful contribution to linear attention research, with sufficient empirical motivation and supporting experimental results. Additionally, the paper addresses several practical challenges related to matrix inversion, which may promote the adoption of this work in future research. There are some caveats, which are discussed in Weaknesses, but I don’t think they outweigh the strengths. Please refer to the following items and Weaknesses for additional reasons behind this recommendation.\n\n- Although the Laplacian kernel is not driven by theoretical connections from the Softmax attention as many prior works were, the it is motivated clearly by the empirical observation. Also, the algorithm is implemented with the consideration of practicality and efficiency.\n- The paper is well written and easy to follow. The proposed method is well positioned in the literature, and the Laplacian linear attention algorithm is explained clearly and thoroughly.\n- The expressiveness of the Laplacian kernel is supported by experimental results. The Laplacian models achieve superior accuracy compared to other methods, and the memory savings remain within a similar range to other linear attention methods.", "weaknesses": "Although the paper is well presented, a few points could make it stronger:\n\n1. Although the linear attention is implemented via a custom GPU kernel, the GPU latency of the Laplacian kernel is only self-compared and not compared with other methods. Although the pseudoinverse of W is implemented via a custom GPU kernel using Newton–Schulz iterations, it is unclear whether the end-to-end latency of a Laplacian-kernel transformer is within a practical range. Comparing the end-to-end latency of the proposed method with other linear attention methods—especially those without matrix inversion—could help clarify its practicality.\n2. The gradient behavior of the Laplacian kernel regarding non-vanishing gradients is discussed only in the context of full attention. It is unclear whether the same behavior holds when the kernel matrix is approximated by the Nyström method.\n3. It is unclear whether the diagonal matrix approximates the whitening matrix effectively.\n4. Some prior works mentioned in the experimental results are not sufficiently explained in the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)