Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruning

2025/02/04 by Chaofan Lin, Jiaming Tang, Lin, Chaofan +15 · 1 voice · 14 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Intelligent Tutoring Systems and Adaptive Learning #Online Learning and Analytics #cs.CL #cs.LG

paper · pdf · doi:10.48550/arxiv.2502.02770

arxiv published 2025/02/04 · arxiv updated 2025/11/04

Abstract

Leveraging attention sparsity to accelerate long-context large language models (LLMs) has been a hot research topic. However, current algorithms such as sparse attention or key-value (KV) cache compression tend to use a fixed budget, which presents a significant challenge during deployment because it fails to account for the dynamic nature of real-world scenarios, where the optimal balance between accuracy and efficiency can vary greatly. In this paper, we find that borrowing top-p sampling (nucleus sampling) to sparse attention can surprisingly achieve adaptive budgeting. Based on this, we propose Twilight, a framework to bring adaptive sparsity to any existing sparse attention algorithm without sacrificing their accuracy. Empirical results show that Twilight can adaptively prune at most 98% of redundant tokens, leading to 15.4× acceleration in self-attention operations and 3.9× acceleration in end-to-end per token latency in long context LLM decoding.

Cited by

• Sol-Attn: Accelerating Video Generation Inference via On-the-Fly Attention Sparsification
• LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decoding
• Focus: A Streaming Concentration Architecture for Efficient Vision-Language Models
• A Preliminary Study on the Promises and Challenges of Native Top-k Sparse Attention
• Accelerating Large-Scale Reasoning Model Inference with Sparse Self-Speculative Decoding
• OmniSparse: Training-Aware Fine-Grained Sparse Attention for Long-Video MLLMs
• SpecAttn: Speculating Sparse Attention
• SeerAttention-R: Sparse Attention Adaptation for Long Reasoning
• Kinetics: Rethinking Test-Time Scaling Laws
• Sparse VideoGen2: Accelerate Video Generation with Sparse Attention via Semantic-Aware Permutation
• FreeKV: Boosting KV Cache Retrieval for Efficient LLM Inference
• The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs
• Sparsity Forcing: Reinforcing Token Sparsity of MLLMs
• Evidence-Driven Dynamic Visual Selector for Efficient Long Video Understanding

Discussions

• arxiv.org/abs/2502.02770 [bsky, 0 points, 0 comments]

Related

• Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs
• Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Serving
• SampleAttention: Near-Lossless Acceleration of Long Context LLM Inference with Adaptive Structured Sparse Attention
• Sparser Block-Sparse Attention via Token Permutation
• Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention