# ELSA: Exact Linear-Scan Attention for Fast and Memory-Light Vision Transformers

arXiv: https://arxiv.org/abs/2604.23798 · HTML: https://mlsanity.com/paper/2604.23798/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 51 references that are in the map.
- First posted on arXiv 26 Apr 2026.

## Builds on (most cited first, 30 of 35)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Segment Anything](https://mlsanity.com/paper/2304.02643/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [VGGT: Visual Geometry Grounded Transformer](https://mlsanity.com/paper/2503.11651/) (2025)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision](https://mlsanity.com/paper/2407.08608/) (2024)
- [Parallelizing Linear Transformers with the Delta Rule over Sequence Length](https://mlsanity.com/paper/2406.06484/) (2024)
- [Patch n' Pack: NaViT, a Vision Transformer for any Aspect Ratio and Resolution](https://mlsanity.com/paper/2307.06304/) (2023)
- [Multi-Scale Vision Longformer: A New Vision Transformer for High-Resolution Image Encoding](https://mlsanity.com/paper/2103.15358/) (2021)
- [EfficientViT: Memory Efficient Vision Transformer with Cascaded Group Attention](https://mlsanity.com/paper/2305.07027/) (2023)
- [SpectralFormer: Rethinking Hyperspectral Image Classification with Transformers](https://mlsanity.com/paper/2107.02988/) (2021)
- [Online normalizer calculation for softmax](https://mlsanity.com/paper/1805.02867/) (2018)
- [Self-attention Does Not Need O(n2) Memory](https://mlsanity.com/paper/2112.05682/) (2021)
- [FastVGGT: Training-Free Acceleration of Visual Geometry Transformer](https://mlsanity.com/paper/2509.02560/) (2025)
- [SHViT: Single-Head Vision Transformer with Memory Efficient Macro Design](https://mlsanity.com/paper/2401.16456/) (2024)
- [DISTFLASHATTN: Distributed Memory-efficient Attention for Long-context LLMs Training](https://mlsanity.com/paper/2310.03294/) (2023)
- [ViTAR: Vision Transformer with Any Resolution](https://mlsanity.com/paper/2403.18361/) (2024)
- [Lean Attention: Hardware-Aware Scalable Attention Mechanism for the Decode-Phase of Transformers](https://mlsanity.com/paper/2405.10480/) (2024)
- [Win-Win: Training High-Resolution Vision Transformers from Two Windows](https://mlsanity.com/paper/2310.00632/) (2023)
- [HIRI-ViT: Scaling Vision Transformer with High Resolution Inputs](https://mlsanity.com/paper/2403.11999/) (2024)

## Abstract (arXiv)

Existing attention accelerators often trade exact softmax semantics, depend on fused Tensor Core kernels, or incur sequential depth that limits FP32 throughput on long sequences. We present ELSA, an algorithmic reformulation of online softmax attention that (i)~preserves exact softmax semantics in real arithmetic with a provable O(ulog n) FP32 relative error bound; (ii)~casts the online softmax update as a prefix scan over an associative monoid (m,S,W), yielding O(n) extra memory and O(log n) parallel depth; and (iii)~is Tensor-Core independent, implemented in Triton and CUDA C++, and deployable as a drop-in replacement requiring no retraining or weight modification. Unlike FlashAttention-2/3, which rely on HMMA/GMMA Tensor Core instructions and provide no compatible FP32 path, ELSA operates identically on A100s and resource-constrained edge devices such as Jetson TX2 -- making it the only hardware-agnostic exact-attention kernel that reduces parallel depth to O(log n) at full precision. On A100 FP32 benchmarks (1K--16K tokens), ELSA delivers 1.3--3.5× speedup over memory-efficient SDPA and 1.97--2.27× on BERT; on Jetson TX2, ELSA achieves 1.5--1.6× over Math (64--900 tokens), with 17.8--20.2% throughput gains under LLaMA-13B offloading at ≥32K. In FP16, ELSA approaches hardware-fused baselines at long sequences while retaining full FP32 capability, offering a unified kernel for high-precision inference across platforms. Our code and implementation are available at https://github.com/ming053l/ELSA.