cs.CVNov 3, 2026

LiSA: Linear Stochastic Attention for Long-Range Visual Modeling

Authors: Sahar Dastani, Fereshteh Shakeri, Samuel Barbeau, Kunal Mahatha, Ismail Ben Ayed, Herve Lombaert, Christian Desrosiers

Organizations: LIVIA, ´ETS Montreal, Canada · Mila – Quebec AI Institute, Canada · Polytechnique Montreal, Canada

Abstract

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

Explore similar work

CardsList
  1. Self-Attention And Beyond the Infinite: Towards Linear Transformers with Infinite Self-Attention

    Feb 26, 2026Giorgio Roffo, Hazem Abdelkawy, Nilli Lavie +1Self-AttentionEfficient ViTs

  2. Switching Linear Attention

    Sep 30, 2026Hyun Dong Lee, Xavier Gonzalez, Nicolas Zucchet +3Efficient AttentionLinear Attention