Sparse-Attention

FlexPrefill A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inference

Extensive Reading Author Info About me - Xunhao Lai Good at writing Triton, here is another repo: XunhaoLai/native-sparse-attention-triton: Efficient triton implementation of Native Sparse Attention. Background As LLM context windows expand (up to 1M+ tokens), the pre-filling phase (processing the input prompt) becomes prohibitively expensive due to the quadratic complexity of full attention($O(n^2)$). Why prior sparse attention is insufficient Many approaches use fixed sparse patterns (e.g., sliding window) or offline-discovered patterns/ratios. These often fail because: ...

XAttention Block Sparse Attention with Antidiagonal Scoring

Extensive Reading Author Info MIT HAN Lab Background Long-Context Transformer Models (LCTMs) are increasingly needed (e.g., long-document QA, long video understanding/generation), but prefill attention is a major bottleneck because standard attention scales quadratically with sequence length. Insights 在一个 Block 中用反对角线可以捕捉到 Vertical-Slash Pattern 的中每个部分，假设整个 Pattern 很稀疏，那么只要包含了 Vertical/Slash 的 BLock 的得分就会很大，因此更容易被选出来为什么反对角线有帮助：信息覆盖：通过提出的跨步反对角线选择，每个标记都至少对一个反对角线和做出贡献（因此不太可能错过重要区域）。模式检测：反对角线与块内常见的垂直和斜线稀疏模式相交，因此它们可以在不明确搜索这些模式的情况下检测到它们。可以认为这篇文章的前提就是每个头都遵循 Vertical-Slash Pattern? Challenges 整体看下来，理念很简单，但是具体的怎么算的 (Algorithm1) 还挺难理解的，必须手动模拟一遍，建议大小为 B=4, S=2 其中最重要的一步是基于步长的降维采样假设：L=16, d=4, B=4, S=2 ...

LServe Efficient Long-sequence LLM Serving with Unified Sparse Attention

Extensive Reading Author Info MIT HAN Lab Background Long-context LLM serving is bottlenecked by attention and KV caches. Prefilling has quadratic attention cost in sequence length, while decoding is memory-bound due to ever-growing KV caches; this makes 128k–512k contexts and long reasoning traces (e.g., 20k-token CoT) slow and expensive in practice. Existing KV cache optimizations are incomplete. Quantization and compression methods (e.g., KV quantization, paged KV cache) reduce memory and bandwidth but do not change the asymptotic attention complexity, so latency still grows linearly (decoding) or quadratically (prefilling) with context length. ...

Quest Query-Aware Sparsity for Efficient Long-Context LLM Inference

Extensive Reading Author Info MIT HAN Lab Background In long-context inference: The KV cache grows linearly with context length ($L$). At each decoding step, the model must read the entire KV cache to compute attention. Existing works recognize there is small part of tokens that can domoinate the accuracy of token generation, and they choose to evict unimportant tokens: StreamingLLM keeps a sliding window plus a few “anchor” tokens. H2O, TOVA, etc., use heuristics or statistics to permanently drop “less important” tokens. Once a token is evicted, it’s gone. BUT, the important tokens are Query-dependent. ...