# Accelerating Prefilling via Decoding-time Contribution Sparsity

arXiv: https://arxiv.org/abs/2507.21526 · HTML: https://mlsanity.com/paper/2507.21526/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 24 references that are in the map.
- First posted on arXiv 29 Jul 2025.

## Builds on (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads](https://mlsanity.com/paper/2410.10819/) (2024)
- [XAttention: Block Sparse Attention with Antidiagonal Scoring](https://mlsanity.com/paper/2503.16428/) (2025)
- [FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inference](https://mlsanity.com/paper/2502.20766/) (2025)
- [Retrieval Augmented Generation (RAG) and Beyond: A Comprehensive Survey on How to Make your LLMs use External Data More Wisely](https://mlsanity.com/paper/2409.14924/) (2024)
- [SCBench: A KV Cache-Centric Analysis of Long-Context Methods](https://mlsanity.com/paper/2412.10319/) (2024)

## Built on by (most cited first, 5 of 5)

- [Attention Sink in Transformers: A Survey on Utilization, Interpretation, and Mitigation](https://mlsanity.com/paper/2604.10098/) (2026)
- [Elastic Attention: Test-time Adaptive Sparsity Ratios for Efficient Transformers](https://mlsanity.com/paper/2601.17367/) (2026)
- [ShadowNPU: System and Algorithm Co-design for NPU-Centric On-Device LLM Inference](https://mlsanity.com/paper/2508.16703/) (2025)
- [S2O: Early Stopping for Sparse Attention via Online Permutation](https://mlsanity.com/paper/2602.22575/) (2026)
- [Flux Attention: Context-Aware Hybrid Attention for Efficient LLMs Inference](https://mlsanity.com/paper/2604.07394/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) incur quadratic attention complexity with input length, creating a major time bottleneck in the prefilling stage. Existing acceleration methods largely exploit attention score sparsity by estimating blocks with high attention scores and applying dynamic sparse attention. In this work, we identify another untapped form of sparsity in the prefilling stage, namely decoding-time contribution sparsity, where many attention blocks exhibit nontrivial attention scores during prefilling yet contribute negligibly to subsequent decoding, as indicated by gradient-based analysis. Building on this observation, we propose TriangleMix, a training-free static attention pattern that uses dense attention in a subset of layers and switches to Triangle attention in the others. Extensive experiments show that TriangleMix preserves nearly lossless performance relative to dense attention while substantially reducing attention overhead in Triangle layers. For 128K inputs, Triangle attention achieves a 15.3x speedup in attention computation, significantly exceeding the acceleration of typical dynamic sparse methods (1.9x to 3.4x). Furthermore, TriangleMix can be seamlessly combined with dynamic sparsity approaches, delivering an additional 6% to 19% reduction in TTFT over using dynamic sparsity alone. Our code is released at https://aka.ms/TriangleMix.