mlsanityData to 14 Oct 2026

Rectified Sparse Attention

arXiv 2506.04108 ↗First posted 4 Jun 2025cs.CLcited by 10

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

Abstract (arXiv)

Efficient long-sequence generation is a critical challenge for Large Language Models. While recent sparse decoding methods improve efficiency, they suffer from KV cache misalignment, where approximation errors accumulate and degrade generation quality. In this work, we propose Rectified Sparse Attention (ReSA), a simple yet effective method that combines block-sparse attention with periodic dense rectification. By refreshing the KV cache at fixed intervals using a dense forward pass, ReSA bounds error accumulation and preserves alignment with the pretraining distribution. Experiments across math reasoning, language modeling, and retrieval tasks demonstrate that ReSA achieves near-lossless generation quality with significantly improved efficiency. Notably, ReSA delivers up to 2.42× end-to-end speedup under decoding at 256K sequence length, making it a practical solution for scalable long-context inference. Code is available at https://aka.ms/ReSA-LM.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 25 of its 28 references that are in the map. First posted on arXiv 4 Jun 2025.

Builds on

25 of 28 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024ClusterKV: Manipulating LLM KV Cache in Semantic Space for Recallable Compression4 Dec
  2. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference16 Jun

Other references · 23

  1. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  2. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  3. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
  4. 2024Qwen2.5 Technical Reportcited by 4,942
  5. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,224
  6. 2022Fast Inference from Transformers via Speculative Decodingcited by 1,653
  7. 2022Solving Quantitative Reasoning Problems with Language Modelscited by 1,392
  8. 2023GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpointscited by 1,346
  9. 2024OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problemscited by 1,136
  10. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Headscited by 843
  11. 2024EAGLE: Speculative Sampling Requires Rethinking Feature Uncertaintycited by 578
  12. 2025Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attentioncited by 407
11 more
  1. 2025MoBA: Mixture of Block Attention for Long-Context LLMscited by 198
  2. 2024InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memorycited by 197
  3. 2023SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefillscited by 193
  4. 2025Qwen2.5-1M Technical Reportcited by 164
  5. 2024SeerAttention: Learning Intrinsic Sparse Attention in Your LLMscited by 124
  6. 2024MagicPIG: LSH Sampling for Efficient LLM Generationcited by 111
  7. 2024DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inferencecited by 106
  8. 2024TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decodingcited by 102
  9. 2024MagicDec: Breaking the Latency-Throughput Tradeoff for Long Context Generation with Speculative Decodingcited by 91
  10. 2024MARIO: MAth Reasoning with code Interpreter Output -- A Reproducible Pipelinecited by 81
  11. 2024MARLIN: Mixed-Precision Auto-Regressive Parallel Inference on Large Language Modelscited by 52

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 5.

10 papers.

  1. 2025SeerAttention-R: Sparse Attention Adaptation for Long Reasoningcited by 30
  2. 2025Efficient Attention Mechanisms for Large Language Models: A Surveycited by 22
  3. 2025BLASST: Dynamic BLocked Attention Sparsity via Softmax Thresholdingcited by 13
  4. 2025Efficient Context Scaling with LongCat ZigZag Attentioncited by 6
  5. 2026A Mechanistic View on Video Generation as World Models: State and Dynamicscited by 6
  6. 2026LycheeDecode: Accelerating Long-Context LLM Inference via Hybrid-Head Sparse Decodingcited by 5
  7. 2025Retrospective Sparse Attention for Efficient Long-Context Generationcited by 4
  8. 2026You Only Index Once: Cross-Layer Sparse Attention with Shared Routingcited by 2
  9. 2026Overlapping Schwarz Attention: Hierarchical Attention via Domain Decompositioncited by 1
  10. 2026BeaconKV: Key-Value Cache Compression Guided by Beacon Queries for Efficient Large Reasoning Model Inferencecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026AB-Sparse: Sparse Attention with Adaptive Block Size for Accurate and Efficient Long-Context Inference
  2. 2025Training-free Context-adaptive Attention for Efficient Long Context Modeling
  3. 2025Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Serving
  4. 2026Simplified Sparse Attention via Gist Tokens
  5. 2026RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inference
  6. 2025Adamas: Hadamard Sparse Attention for Efficient Long-Context Inference
  7. 2026Augmenting Attention with Exponentially Decaying Memory Improves Query-Aware KV Sparsity
  8. 2026Double-P: Hierarchical Top-P Sparse Attention for Long-Context LLMs