mlsanityData to 13 Oct 2026

Stochastic Sparse Attention for Memory-Bound Inference

arXiv 2605.01910 ↗First posted 3 May 2026cs.LG cs.AI cs.DCcited by 1

On the map: Efficient LLM inference and serving → KV cache optimization

Abstract (arXiv)

Autoregressive decoding becomes bandwidth-limited at long contexts, as generating each token requires reading all nk key and value vectors from KV cache. We present Stochastic Additive No-mulT Attention (SANTA), a method that sparsifies value-cache access by sampling S ll nk indices from the post-softmax distribution and aggregates only those value rows. This yields an unbiased estimator of the post-softmax value aggregation while replacing value-stage multiply-accumulates with gather-and-add. We introduce stratified and systematic sampling to design variance-reduced, GPU-friendly variants. Evaluated on Llama-3.1-8B-Instruct at 32k-token contexts, S2ANTA matches baseline accuracy while achieving up to 1.5× decode-step attention-kernel speedup over FlashInfer and FlashDecoding on an NVIDIA RTX 6000 Ada. In batched long-context generation, these kernel gains translate to up to 1.25× end-to-end decode-latency speedup. Finally, we propose Bernoulli qK^mathsfT sampling as a complementary technique to sparsify the score stage, reducing key-feature access through stochastic ternary queries. Both methods are complementary to upstream quantization, low-rank projection, KV-cache compression, and KV-cache selection methods. Together, they point toward sparse, multiplier-free, and energy-efficient inference. We open-source our kernels at: https://github.com/OPUSLab/SANTA.git

Key facts. Cited by 1 paper in the map (data through 13 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 31 of its 52 references that are in the map. First posted on arXiv 3 May 2026.

Builds on

31 of 52 references.

Closest ancestors · 7

Same direction, newest first

  1. 2025FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving2 Jan
  2. 2024ShadowKV: KV Cache in Shadows for High-Throughput Long-Context LLM Inference28 Oct
  3. 2024DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads14 Oct
  4. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference16 Jun
  5. 2024HiRE: High Recall Approximate Top-k Estimation for Efficient LLM Inference14 Feb
  6. 2023SparQ Attention: Bandwidth-Efficient LLM Inference8 Dec
  7. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models24 Jun

Other references · 24

  1. 2017Attention Is All You Needcited by 60,106
  2. 2021Training Verifiers to Solve Math Word Problemscited by 9,916
  3. 2021Evaluating Large Language Models Trained on Codecited by 8,205
  4. 2020Measuring Massive Multitask Language Understandingcited by 7,876
  5. 2018HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answeringcited by 3,716
  6. 2023Let's Verify Step by Stepcited by 3,672
  7. 2020Longformer: The Long-Document Transformercited by 3,393
  8. 2023QLoRA: Efficient Finetuning of Quantized LLMscited by 3,388
  9. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,570
  10. 2020Big Bird: Transformers for Longer Sequencescited by 1,681
  11. 2020Reformer: The Efficient Transformercited by 1,662
  12. 2018Know What You Don't Know: Unanswerable Questions for SQuADcited by 1,546
12 more
  1. 2019Generating Long Sequences with Sparse Transformerscited by 1,538
  2. 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,302
  3. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 999
  4. 2024KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cachecited by 609
  5. 2024KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantizationcited by 572
  6. 2024LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitaskscited by 369
  7. 2024MagicPIG: LSH Sampling for Efficient LLM Generationcited by 111
  8. 2024TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decodingcited by 99
  9. 2021Memory-efficient Transformers via Top-k Attentioncited by 60
  10. 2024RTop-K: Ultra-Fast Row-Wise Top-K Selection for Neural Network Acceleration on GPUscited by 8
  11. 2022Fast Monte-Carlo Approximation of the Attention Mechanismcited by 3
  12. 2024Stochastic Spiking Attention: Accelerating Attention with Stochastic Computing in Spiking Networkscited by 2

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026SANTA++: Sampling Attention through Representative Keyscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025NOSA: Native and Offloadable Sparse Attention
  2. 2026An Efficient Hybrid Sparse Attention with CPU-GPU Parallelism for Long-Context Inference
  3. 2026Learning how to Forget: Fine-tuning for Long-Context Sparse Attention
  4. 2026HiSparse: Scaling Sparse-Attention Decoding with Hierarchical KV Cache Management
  5. 2026Unifying Sparse Attention with Hierarchical Memory for Scalable Long-Context LLM Serving
  6. 2026Elastic Threshold Attention: Learned Contextual Sparsity for Long-Context Decoding
  7. 2025HCAttention: Extreme KV Cache Compression via Heterogeneous Attention Computing for LLMs
  8. 2026SAC: Disaggregated KV Cache System for Sparse Attention LLMs with CXL