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

• URL: http://arxiv.org/abs/2604.23798v1
• Date: Sun, 26 Apr 2026 16:41:30 GMT
• Title: ELSA: Exact Linear-Scan Attention for Fast and Memory-Light Vision Transformers
• Abstract summary: Existing attention accelerators often trade exact softmax semantics, depend on fused Core kernels, or incur sequential depth that limits FP32 throughput on long sequences.<n>We present bfELSA, an algorithmic reformulation of online softmax attention that reserves exact softmax semantics in real arithmetic with a emphprovable $mathcalO(ulog n)$ FP32 relative error bound.<n>Unlike FlashAttention-2/3, which rely on HMMA/GMMA Core instructions and provide no FP32 path, ELSA operates identically on A100s and resource-
• Score: 11.576817774473398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 \textbf{ELSA}, an algorithmic reformulation of online softmax attention that (i)~preserves exact softmax semantics in real arithmetic with a \emph{provable} $\mathcal{O}(u\log 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 \emph{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\times$ speedup over memory-efficient SDPA and $1.97$--$2.27\times$ on BERT; on Jetson TX2, ELSA achieves $1.5$--$1.6\times$ over Math (64--900 tokens), with $17.8$--$20.2\%$ throughput gains under LLaMA-13B offloading at $\ge$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.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• TEMPO: Makespan-Aware Expert-Parallel Load Balancing Across Memory- and Compute-Bound Regimes [6.460910545652521]
  TEMPO is a makespan-aware dispatcher solving per-batch dispatch in milliseconds off the critical path.<n>Its SG integration runs out-of-process and fuses dispatch with count into one in-graph kernel.<n>End-to-end on Testbed B, Qwen3-235B (inside the win region) gains $4$--$6%$ throughput and cuts p99 latency by $sim 15.6%$; DeepSeek-V3 shows only mechanism cost.
  arXiv  Detail & Related papers  (2026-08-13T10:21:11Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• Pruning Deep Neural Networks via the Marchenko--Pastur Distribution [0.0]
  We study a Marchenko--Pastur (MP) random-matrix approach to pruning deep neural networks with very small post-pruning fine-tuning budgets.<n>The main practical contribution is accuracy retention under short calibration and fine-tuning schedules.
  arXiv  Detail & Related papers  (2026-05-23T19:44:02Z)
• Variational Linear Attention: Stable Associative Memory for Long-Context Transformers [0.6117371161379209]
  Linear attention reduces the quadratic cost of softmax attention to $mathcalO(T)$, but its memory state grows as $mathcalO(T)$ in Frobenius norm.<n>We introduce textbfVariational Linear Attention (VLA), which reframes the memory update as an online regularised least-squares problem.
  arXiv  Detail & Related papers  (2026-05-11T20:03:12Z)
• Copy-as-Decode: Grammar-Constrained Parallel Prefill for LLM Editing [2.6382975801439836]
  LLMs edit text and code by autoregressively regenerating the full output, even when most tokens appear verbatim in the input.<n>We study Copy-as-Decode, a decoding-layer mechanism that recasts edit generation as structured decoding over a two-primitive grammar.
  arXiv  Detail & Related papers  (2026-04-20T12:29:53Z)
• Scaling Attention via Feature Sparsity [50.64995497733461]
  Scaling Transformers to ultra-long contexts is bottlenecked by the $O(n2 d)$ cost of self-attention.<n>We propose Sparse Feature Attention, where queries and keys are represented as $k$-sparse codes that preserve high-dimensional expressivity.<n>Across GPT-2 and Qwen3 pretraining, SFA matches dense baselines while improving speed by up to $2.5times$ and reducing FLOPs and KV-cache by nearly 50%.
  arXiv  Detail & Related papers  (2026-03-17T08:41:50Z)
• 98$\times$ Faster LLM Routing Without a Dedicated GPU: Flash Attention, Prompt Compression, and Near-Streaming for the vLLM Semantic Router [9.457255218406333]
  We present three staged optimizations for the vLLM Semantic Router.<n>A custom Flash Attention operator for ONNX on ROCm reduces attention memory from $O(n2)$ to $O(n)$.<n>Near-streaming body processing with adaptive chunking eliminates serialization overhead.
  arXiv  Detail & Related papers  (2026-03-13T04:33:53Z)
• Rank-Aware Spectral Bounds on Attention Logits for Stable Low-Precision Training [0.0]
  Attention scores in transformers are bilinear forms $S_ij = x_itop M x_j / sqrtd_h$ whose maximum magnitude governs overflow risk in low-precision training.<n>We derive a emphrank-aware concentration inequality: when the interaction matrix $M = WQ WKtop$ has rank $r ll d$, tail probabilities for $max_i,j|S_ij|$ decay as $exp(-d22/(
  arXiv  Detail & Related papers  (2026-02-21T14:29:22Z)
• EZ-SP: Fast and Lightweight Superpoint-Based 3D Segmentation [14.136068396056869]
  We propose a learnable, fully GPU partitioning algorithm that generates geometrically and semantically coherent superpoints 13$times$ faster than prior methods.<n>Our module is compact (under 60k parameters), trains in under 20 minutes with a differentiable surrogate loss, and requires no handcrafted features.<n>With 72$times$ faster inference and 120$times$ fewer parameters, EZ-SP matches the accuracy of point-based SOTA models across three domains.
  arXiv  Detail & Related papers  (2025-11-29T08:21:51Z)
• Speeding Up MACE: Low-Precision Tricks for Equivarient Force Fields [51.95157731126864]
  Machine-learning force fields can deliver accurate molecular dynamics (MD) at high computational cost.<n>This thesis aims to make MACE cheaper and faster by identifying computational bottlenecks and evaluating low-precision execution policies.
  arXiv  Detail & Related papers  (2025-10-23T14:02:34Z)
• Numerical Fragility in Transformers: A Layer-wise Theory for Explaining, Forecasting, and Mitigating Instability [0.0]
  We give a first-order, module-wise theory that predicts when and where errors grow.<n>For self-attention we derive a per-layer bound that factorizes into three interpretable diagnostics.<n>We also introduce a precision- and width-aware LayerNorm indicator $rho_rm LN$ with a matching first-order bound.
  arXiv  Detail & Related papers  (2025-10-17T01:03:02Z)
• Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling [50.994194925685434]
  LrcSSM is a $textitnon-linear$ recurrent model that processes long sequences as fast as today's linear state-space layers.<n>By forcing its Jacobian matrix to be diagonal, the full sequence can be solved in parallel.<n>LrcSSM offers a formal gradient-stability guarantee that other input-varying systems such as Liquid-S4 do not provide.
  arXiv  Detail & Related papers  (2025-05-27T20:02:59Z)
• HashAttention: Semantic Sparsity for Faster Inference [95.31739930718116]
  This paper introduces HashAttention, framing pivotal token identification as a recommendation problem.<n>It reduces tokens used by up to $16times$ with minimal quality loss, requiring only 32 bits of auxiliary memory per token.<n>On A100 GPU, at $32times$ sparsity, incorporating HashAttention reduces attention latency by up to $4.3times$ in GPT-FAST and $2.54times$ in FlashDecode, and achieves up to $3.12times$ higher throughput for GPT-FAST.
  arXiv  Detail & Related papers  (2024-12-19T02:34:15Z)
• Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [23.633481089469836]
  Auto-regressive decoding of Large Language Models (LLMs) results in significant overheads in their hardware performance.<n>We propose a novel parallel prompt decoding that requires only $0.0002$% trainable parameters, enabling efficient training on a single A100-40GB GPU in just 16 hours.<n>Our approach demonstrates up to 2.49$times$ speedup and maintains a minimal memory overhead of just $0.0004$%.
  arXiv  Detail & Related papers  (2024-05-28T22:19:30Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.