# Predict, Reuse, and Repair: Accelerating Dynamic Sparse Attention for Long-Context LLM Decoding

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 30 references that are in the map.
- First posted on arXiv 29 Jun 2026.

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

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [∞Bench: Extending Long Context Evaluation Beyond 100K Tokens](https://mlsanity.com/paper/2402.13718/) (2024)
- [WebThinker: Empowering Large Reasoning Models with Deep Research Capability](https://mlsanity.com/paper/2504.21776/) (2025)
- [MathArena: Evaluating LLMs on Uncontaminated Math Competitions](https://mlsanity.com/paper/2505.23281/) (2025)
- [FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving](https://mlsanity.com/paper/2501.01005/) (2025)
- [InfiniGen: Efficient Generative Inference of Large Language Models with Dynamic KV Cache Management](https://mlsanity.com/paper/2406.19707/) (2024)
- [GLM-4-Voice: Towards Intelligent and Human-Like End-to-End Spoken Chatbot](https://mlsanity.com/paper/2412.02612/) (2024)
- [InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memory](https://mlsanity.com/paper/2402.04617/) (2024)
- [Rethinking the Bounds of LLM Reasoning: Are Multi-Agent Discussions the Key?](https://mlsanity.com/paper/2402.18272/) (2024)
- [Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference](https://mlsanity.com/paper/2402.09398/) (2024)
- [FlexiCache: Leveraging Temporal Stability of Attention Heads for Efficient KV Cache Management](https://mlsanity.com/paper/2511.00868/) (2025)
- [LouisKV: Efficient KV Cache Retrieval for Long Input-Output Sequences](https://mlsanity.com/paper/2510.11292/) (2025)
- [AsyncSpade: Efficient Test-Time Scaling with Asynchronous Sparse Decoding](https://mlsanity.com/paper/2510.07486/) (2025)
- [Dynamic Sparse Attention: Access Patterns and Architecture](https://mlsanity.com/paper/2603.13430/) (2026)

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

- [Recall Before You Rank: Similarity-Guided Top-K Reuse for Efficient Long-Context Attention](https://mlsanity.com/paper/2607.27692/) (2026)
- [SPIN: Shadow Predictive Indexer for Sparse Attention](https://mlsanity.com/paper/2610.09025/) (2026)

## Abstract (arXiv)

Dynamic sparse attention (DSA) accelerates long-context LLM decoding by attending to only the top-K KV blocks relevant to each query, but it introduces a serialized selection-to-attention dependency that emerges as a new latency bottleneck. We present PRR, a speculate-reuse-repair runtime that exploits temporal locality in DSA selections to predict likely blocks, speculate the attention over them while selection is in flight, and incrementally repair missed blocks once the true selected set is known. PRR uses a lightweight EMA-based predictor, a profiling-guided speculation budget that keeps speculative work off the critical path, and a FlashAttention-based repair kernel that folds missed blocks into the partial attention state using online-softmax statistics. Across long-context benchmarks and representative DSA methods, PRR reduces per-token decoding latency by up to 40% while preserving downstream task accuracy. Github: https://github.com/Tianyu9748/Incremental_FlashAttention