Self-attention has become the standard for modern sequence modeling, enabling Transformers to model long-range dependencies across a wide range of modalities. Despite these advances, its quadratic cost with respect to sequence length remains a significant computational bottleneck. Recent work addresses this limitation by introducing linear variants of self-attention, namely with kernel approximations of the softmax operator. However, their first-order aggregation restricts expressivity and struggles to capture higher-order structure. We propose Linear Stochastic Attention (LiSA), a linear attention plug-in module that enables higher-order token interactions via a stochastic diffusion process based on truncated random walks. LiSA incorporates adaptive locality, favoring semantically similar neighbors to preserve fine-grained structures, while maintaining stable and efficient training. We conduct extensive experiments on classification, semantic segmentation, and object detection tasks and show improved results over state-of-the-art methods.
Figures & tables
Figure 1: Softmax vs. Linear vs. Higher-order attention. Given Q,K,V∈Rn×d : softmax-attention forms QK⊤ then applies to V . Linear-attention computes K⊤V then applies to Q . Higher-order attention (ours) uses a truncation length T , retaining multiple diffusion terms while remaining linear in n and expanding the effective receptive field.
Figure 2: Overview of LiSA . We patchify the input image into tokens and treat them as nodes in a graph G=(V,E) , where edge weights define a row-stochastic transition matrix S . Aggregating the truncated terms on S yields a global attention map that captures transitive (higher-order) dependencies. In parallel, we compute content-based similarity within each token’s local neighborhood to form a local attention map. The layer output is a convex combination of the two, blending sharp local context with long-range structure.
Model
Input
Params (M)
FLOPs (G)
Top1-acc(%)
DeiT Family
DeiT-T [ 33 ]
224
5.72
1.26
72.2
FLatten-DeiT-T [ 14 ]
224
6.19
1.15
74.1
LiSA -DeiT-T
224
6.30
1.29
74.54 +2.34
DeiT-T [ 33 ]
384
5.79
4.70
74.9
FLatten-DeiT-T [ 14 ]
384
7.14
3.37
76.53
Table 1: Results of Classification. Comparison of LiSA across diverse vision backbones. Red indicates gains over the self-attention baseline (in all tables).
Model
Par. (M)
Top1-acc(%)
mIoU
mAcc
BiFormer-T [ 52 ]
13.1
81.4
—
—
LiSA -BiFormer-T
13.2
82.4 +1.0
—
—
BiFormer-S [ 52 ]
25.5
83.8
48.9
—
LiSA -BiFormer-S
25.6
84.1 +0.3
49.5 +0.6
61.5
BiFormer-B [ 52 ]
56.8
84.3
—
—
LiSA -BiFormer-B
56.8
85.0 +0.7
—
—
Table 2: Four-stage pyramid architecture: classification and segmentation results. Segmentation is with S - FPN. Dashes indicate values not reported.
Semantic Segmentation on ADE20K
Backbone
Method
FLOPs (G)
Par. (M)
mIoU
mAcc
PVT - T
S - FPN
158
17
36.57
46.72
FLatten-PVT - T
S - FPN
169
16
37.21
48.95
LiSA - PVT - T
S - FPN
170
16
40.85 +4.28
51.75 +5.03
Swin - T
UperNet
945
60
44.51
55.61
FLatten-Swin - T
UperNet
946
60
44.82
57.01
Table 3: Results of semantic segmentation. FLOPs are computed with an input of 512×2048 . S - FPN denotes SemanticFPN [ 21 ] . Dashes indicate values not reported.
Mask R-CNN Object Detection on COCO
Method
FLOPs
Sch.
AP b
AP 50b
AP 75b
AP m
AP 50m
AP 75m
PVT-T
240G
1x
36.7
59.2
39.3
35.1
56.7
37.3
FLatten-PVT-T
244G
1x
38.2
61.6
41.9
37.0
57.6
39.0
LiSA -PVT-T
245G
1x
40.5 +3.8
62.9 +3.8
44.1 +4.8
37.6 +2.5
59.7 +3.0
40.2 +2.9
Swin-T
267G
1x
43.7
66.6
47.7
39.8
63.3
42.7
FLatten-Swin-T
268G
1x
44.2
67.3
48.5
40.2
63.8
43.0
Table 4: Results of object detection. The FLOPs are computed over backbone, FPN and detection head with input resolution of 1280 × 800.
Linear Attention
Top1-acc(%)
DeiT-S [ 33 ]
79.8
Hydra Attn [ 1 ]
75.38
Vanilla Linear Attn [ 20 ]
76.47
Efficient Attn [ 31 ]
76.81
Linear Angular Attn [ 45 ]
79.21
Enhanced Linear Attn [ 2 ]
77.17
Table 5: Comparison of linear-attention variants on DeiT-S (ImageNet).
Backbone
F+D+G ( α=0 )
F+D+L ( α=1 )
Learned α
DeiT-T
73.7
73.4
76.3 +2.6
DeiT-S
78.3
78.1
80.7 +2.4
Table 6: Component ablation on DeiT-T/DeiT-S classification.
Figure 3: Effect of truncation length T on DeiT-T accuracy, reported as mean ± standard deviation across three runs.
LA
GL
LA+F
GL+F
LA+D
GL+D
FLatten LA+F+D
LiSA GL+F+D
65.7
69.2
65.9
69.3
73.3
75.2
74.4
76.3
Table 7: Component ablation on DeiT-T classification.
Figure 4: Visualization of attention behavior in DeiT-T.
Figure 5: Efficiency comparison across sequence lengths.
Kernel Function
ELU
ReLU
Accuracy (%)
76.0
76.3
Table 8: Impact of different kernel functions (DeiT-T).
Local Window Size
3×3
5×5
7×7
Accuracy (%)
76.3
75.7
76.1
Table 9: Ablation study on local window size using DeiT-T.
Model
Stage
Resolution
LiSA blocks (res, dim, heads, #layers)
#DeiT blocks
LiSA -DeiT-T
Encoder
14×14
(14×14,192,3)×12
0
LiSA -DeiT-S
Encoder
14×14
(14×14,384,6)×12
0
Table 10: Architectures of LiSA -DeiT models. All original DeiT transformer blocks are removed (#DeiT blocks = 0) and replaced with LiSA blocks.
Model
Stage
Output
LiSA blocks (res, dim, heads, #layers)
#PVT blocks
LiSA -PVT-T
res1
56×56
(56×56,64,2)×2
0
res2
28×28
(28×28,128,4)×2
0
res3
14×14
(14×14,320,10)×2
0
res4
7×7
(7×7,512,16)×2
0
LiSA -PVT-S
res1
56×56
(56×56,64,2)×3
0
res2
28×28
(28×28,128,4)×4
0
Table 11: Architectures of LiSA -PVT models. At all stages, the original PVT transformer blocks are removed (#PVT blocks = 0) and replaced with LiSA blocks.
Stage
Output
LiSA -Swin-T
LiSA blocks (win, dim, heads, #layers)
#Swin blocks
res1
56×56
(7×7,96,3)×2
0
res2
28×28
(7×7,192,6)×2
0
res3
14×14
(7×7,384,12)×6
0
res4
7×7
(7×7,768,24)×2
0
Table 12: Architecture of the LiSA -Swin model. At all stages, the original Swin transformer blocks are removed (#Swin blocks = 0) and replaced with LiSA blocks.
Input
DeiT-T
Flatten
LiSA
Res.
Seq.
Latency (ms)
Throughput (img/s)
GPU Memory (MB)
Latency (ms)
Throughput (img/s)
GPU Memory (MB)
Latency (ms)
Throughput (img/s)
GPU Memory (MB)
224
197
3.50
2288.00
74.0
7.15
1118.91
73.2
13.53
591.49
95.4
384
577
4.07
1967.60
152.7
7.34
1090.32
110.2
13.52
591.60
172.1
512
1025
8.06
993.06
312.9
7.40
1080.62
151.1
13.48
593.68
263.4
640
1601
15.56
514.19
627.9
11.11
720.42
206.6
19.47
410.90
382.0
768
2305
27.69
288.93
1178.7
14.74
542.73
275.7
26.15
305.90
529.2
Table 13: Latency, throughput, and peak GPU memory across input resolutions.
The quadratic cost of softmax attention limits Transformer scalability in high-resolution vision. We introduce Infinite Self-Attention (InfSA), a spectral reformulation that treats each attention layer as a diffusion step on a content-adaptive token graph, accumulating multi-hop interactions through a discounted Neumann series over attention matrices. This links self-attention to classical graph centrality (Katz, PageRank, eigenvector centrality) for interpretable token weighting. We also show the Neumann kernel equals the fundamental matrix of an absorbing Markov chain, so a token's centrality is its expected number of random-walk visits before absorption. We then propose Linear-InfSA, a linear-time variant that approximates the principal eigenvector of the implicit attention operator without forming the full attention matrix. It keeps an auxiliary state of fixed size proportional to per-head dimension dh (independent of sequence length N), is drop-in compatible with Vision Transformers, and supports stable training at 4096 by 4096 and inference at 9216 by 9216 (about 332k tokens). In a 4-layer ViT (53.5M parameters, 59 GFLOPs at 224 by 224), Linear-InfSA reaches 84.7% top-1 on ImageNet-1K, a +3.2 point architectural gain over an equal-depth softmax ViT trained with the same recipe. On ImageNet-V2, InfViT variants outperform all compared baselines (up to 79.8% vs 76.8%), indicating robustness under distribution shift. On an A100 40GB GPU, Linear-InfViT runs at 231 images/s and 0.87 J/image (13x better throughput and energy than equal-depth ViT) and is the only tested model to complete 9216 by 9216 inference without out-of-memory. The linear approximation closely matches the dominant eigenvector of the quadratic operator (cosine 0.985).
Giorgio Roffo, Hazem Abdelkawy, Nilli Lavie +1
Equixly API Security, Italy · Toyota Motor Europe, Belgium · MindVisionLabs, UK +2
Designing expressive sequence layers with efficient inference remains a central challenge in modern machine learning. Standard softmax attention achieves excellent sequence modeling performance through rich nonlinear token interactions, but it requires a key-value cache that grows linearly with sequence length, limiting its scalability. Linear attention enables efficient recurrent computation with a constant memory footprint, yet its reduced expressivity often yields inferior modeling performance. We introduce Switching Linear Attention (SwiLA), a novel sequence layer that bridges this gap by enhancing representational capacity while retaining the fixed-size recurrent state of linear attention. We derive the SwiLA recurrence from the test-time regression framework, casting the state update rule as online expectation-maximization in a mixture of linear regressions model. At test time, each output dimension dynamically selects among multiple linear attention components based on the input. Across associative recall, in-context language learning, and language modeling benchmarks, SwiLA shows strong performance and narrows the gap to softmax attention, even surpassing it in several settings.
Hyun Dong Lee, Xavier Gonzalez, Nicolas Zucchet +3
Stanford University · Unconventional AI. Work done at Stanford University.
This paper introduces Exact Linear Attention (ELA), a mechanism that achieves linear computational complexity for Transformer attention by exploiting the exact decomposition property of kernel functions, thereby eliminating approximation error. We identify and address two key limitations of prior linear attention -- gradient explosion and token attention dilution -- by imposing kernel constraints that ensure non-negativity, discriminability, and geometric interpretability. Several kernel functions are proposed, including the Hadamard Exp Kernel, Summation Squared Euclidean Distance Kernel, and Subtraction Squared Euclidean Distance Kernel, each tailored for specific attention behaviors. Beyond the core attention formulation, the paper presents three engineering innovations: (1) a Hyper-Link structure that replaces traditional residual connections to mitigate gradient degradation; (2) a Memory Lobe module based on bidirectional linear attention, which captures "transformation flow" across layers to implement qualitative memory and an implicit reinforcement learning paradigm; and (3) a routing-score-based bias mechanism for Mixture-of-Experts (MoE) to improve interpretability and semantic alignment. Experimental results demonstrate that ELA achieves up to 6x faster decoding speed and 75% reduction in KV cache memory usage compared to full attention, while maintaining comparable or superior training performance. The proposed memory module accelerates convergence and enhances generalization. Furthermore, we extend the linear attention principle to vision models, yielding YOLO-LAT, which attains up to 4.3x GPU inference speedup and 7.9x parameter reduction with competitive detection accuracy. These results underline the broad applicability of exact linear attention for scaling Transformer models to ultra-long sequences and efficient visual tasks.