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.