Rectified Sparse Attention

2025/06/04 by Yutao Sun, Tianzhu Ye, Sun, Yutao +15 · 4 citations
Computer Science · #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning and Algorithms #Natural Language Processing Techniques #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2506.04108

openalex publication_date 2025/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• MoBA: Mixture of Block Attention for Long-Context LLMs
• Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention
• Qwen2.5-1M Technical Report
• DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning
• Qwen2.5 Technical Report
• ClusterKV: Manipulating LLM KV Cache in Semantic Space for Recallable Compression
• MagicPIG: LSH Sampling for Efficient LLM Generation
• SeerAttention: Learning Intrinsic Sparse Attention in Your LLMs
• MARLIN: Mixed-Precision Auto-Regressive Parallel Inference on Large Language Models
• MagicDec: Breaking the Latency-Throughput Tradeoff for Long Context Generation with Speculative Decoding
• Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference
• TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding
• Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context
• OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problems
• InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memory
• EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty
• Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads
• MARIO: MAth Reasoning with code Interpreter Output -- A Reproducible Pipeline
• DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inference
• SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
• GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints
• Fast Inference from Transformers via Speculative Decoding
• Solving Quantitative Reasoning Problems with Language Models
• Training Verifiers to Solve Math Word Problems
• Measuring Mathematical Problem Solving With the MATH Dataset
• OpenAI o1 System Card

Cited by

• BLASST: Dynamic BLocked Attention Sparsity via Softmax Thresholding
• Retrospective Sparse Attention for Efficient Long-Context Generation
• Efficient Attention Mechanisms for Large Language Models: A Survey
• SeerAttention-R: Sparse Attention Adaptation for Long Reasoning
• Delta Attention: Fast and Accurate Sparse Attention Inference by Delta Correction

Related

• Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention
• Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Serving
• PowerAttention: Exponentially Scaling of Receptive Fields for Effective Sparse Attention
• SSA: Sparse Sparse Attention by Aligning Full and Sparse Attention Outputs in Feature Space
• Sparser Block-Sparse Attention via Token Permutation