acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Dynamic sparse attention (DSA) accelerates long-context LLM decoding by attending to only the top- 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.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
efficient LLM, long-context decoding, dynamic sparse attention

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_nA5JOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper targets the serialized selection-to-attention dependency in dynamic sparse attention (DSA) for long-context LLM decoding. Its main idea is to overlap block selection with attention: an EMA-based predictor speculates the next top-K block set, speculative attention runs on the predicted set, and a FlashAttention-based online-softmax repair kernel folds in missed blocks after the true set is known. A profiling-guided speculation budget keeps speculative work off the critical path. Experiments across seven LLMs, three DSA methods (Quest, InfLLM-v2, SeerAttention-R), and five benchmarks report decoding speedups with essentially unchanged downstream accuracy.

Critical strengths

1: The motivation is grounded in measured temporal locality and GPU headroom, and the ablation shows that incremental repair is necessary for the gain. This is consequential because the paper's core claim depends on selection and attention being concurrently schedulable without extending the critical path.

2: The validation is broad: multiple LLMs, both training-free and trainable DSA methods, and several accuracy benchmarks. This matters because it makes the speedups less likely to be a single-configuration artifact and supports the claim that accuracy is preserved.

Critical weaknesses

1: The utilization evidence is too coarse. The paper reports low overall decode-stage SM/L2/DRAM utilization, but does not break this down by selection, attention, and repair. This matters because overlap is only justified if selection leaves specific resources idle that speculative attention can use; aggregate utilization cannot establish that.

2: Peak memory impact is not discussed. PRR adds predictor state, speculative indices, gather/repair workspaces, and extra KV reads, but the paper does not report peak memory or whether KV-cache capacity or maximum batch size changes. This matters for long-context serving, where KV cache capacity often limits batch size and a small memory regression can reduce throughput.

Questions for authors
  1. Can you break down SM, L2, and DRAM utilization separately for selection, speculative attention, and repair? This matters because the overlap argument requires showing that selection leaves the specific resources speculative attention needs, not just low aggregate utilization.
  2. Can you report peak GPU memory breakdown and the maximum batch size for baseline DSA versus PRR under the same context length? This matters because extra predictor state/workspaces or KV reads could reduce KV-cache capacity or serving batch size even if average latency improves.
  3. Beyond mean absolute error, can you provide a tighter error bound or statistics on error accumulation over long decoding steps? This matters because PRR retains over-predicted blocks P/A in the softmax and is not bitwise equivalent, so long-run numerical drift needs stronger evidence.
  4. How robust is PRR at large batch sizes, especially when per-request context length is shorter? This matters because the paper's gains shrink with batch size, and long-context serving may mix batch and length regimes where resource headroom and critical-path assumptions differ.
Reviewer_5f3AOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes PRR, a speculative attention runtime that accelerates long-context LLM decoding by overlapping block selection with attention computation in dynamic sparse attention (DSA). Specifically, the authors first identify the serialized selection-to-attention dependency as a key latency bottleneck and exploit the temporal locality of selected KV blocks across consecutive decoding steps to enable speculative execution. The authors then introduce a lightweight EMA-based predictor that estimates future block importance scores, with its hyperparameters calibrated using importance score trajectories collected during the prefill stage. Based on offline profiling, PRR dynamically determines the speculation budget to maximize the number of predicted KV blocks while keeping speculative attention computation within the selection time window. To handle prediction errors, the authors further develop an incremental attention repair kernel based on online-softmax statistics, which incorporates missed KV blocks into the partially computed attention output without recomputing attention over the entire selected set. Finally, extensive experiments across multiple LLMs, DSA methods, and long-context benchmarks demonstrate the effectiveness of PRR in reducing decoding latency with no observed degradation in downstream task accuracy. However, I have some concerns about this paper. My detailed comments are as follows.

Critical strengths
  1. The authors propose an effective speculative attention runtime that addresses the selection-to-attention dependency in dynamic sparse attention by overlapping block selection with attention computation, providing a promising approach to accelerating long-context LLM decoding.
  2. The proposed method combines a lightweight EMA-based predictor with an incremental attention repair mechanism, enabling the reuse of speculative attention results and avoiding redundant recomputation when the predicted KV blocks differ from the actual selections.
  3. The authors conduct extensive experiments across multiple LLMs, dynamic sparse attention methods, and long-context benchmarks, demonstrating consistent decoding speedups with no observed degradation in downstream task accuracy.
Critical weaknesses
  1. The contribution of the EMA predictor is not sufficiently isolated. Section 5.2 indicates that the improvement in Top-K coverage from 91% to 98% also benefits from a larger speculation budget enabled by the optimized kernel. A comparison with simpler prediction strategies under the same speculation budget would better demonstrate the effectiveness of the EMA predictor.
  2. The overhead and scalability of the prefill calibration are not sufficiently analyzed. Although Appendix A.6 reports low critical-path overhead, the storage and processing costs of importance score trajectories may increase significantly with context length. More details on memory usage, CPU-GPU data transfer, and calibration overhead under longer contexts would help clarify the scalability of the proposed method.
  3. The distinction from related work could be further clarified. Existing approaches such as AsyncSpade [A] and SparDA [B] have explored predictive sparse KV selection and asynchronous execution, while FlashInfer's Recursive/Cascade Attention already supports merging partial attention states. Although PRR combines these ideas in a different runtime design, a more explicit discussion of its unique execution and repair mechanisms, particularly the advantages of its customized repair kernel over existing attention-state merging implementations [C], would help better establish its novelty.

[A] AsyncSpade: Efficient Test-Time Scaling with Asynchronous Sparse Decoding. 2026 ICML. [B] SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inference. 2026 arXiv. [C] Cascade Inference: Memory Bandwidth Efficient Shared Prefix Batch Decoding. FlashInfer blog.

Questions for authors

See Weaknesses.

Reviewer_5yGYOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The KV cache has become a major bottleneck for modern LLMs. Existing sparse attention methods sequentially execute top-k selection and attention, which increases latency. PRR proposes to speculatively execute attention using an EMA-based predictor, allowing it to overlap with top-k selection, and then perform a repair. Evaluation demonstrate comparable accuracy with 1.4x speedup.

Critical strengths
  • The overlapping of selection and attention is promising.
Critical weaknesses
  • The baseline time measurement is very questionable, which is the foundation of this work.
  • The repair is not something new; flashinfer and flashattn already support such an operation.
Questions for authors

Thanks for submitting the paper. I have some concern about the paper.

  1. FlashInfer already exposes attention-state merging primitives (merge_state, merge_states, and merge_state_in_place), while FlashAttention implements partial-attention reduction through its Split-KV combine kernel. The paper’s claim that “However, existing inference engines such as vLLM (Kwon et al., 2023) and SGLang (Zheng et al., 2024), as well as attention kernels such as FlashAttention (Dao, 2024), do not expose an interface for incrementally incorporating missed blocks into a partially computed attention result.” is overstated.
  2. Figure 2’s result is very suspicious; however, this is the core of the paper. With 1024 tokens selected, the memory load on the attention side is very small. The model has 16GB of weights to load, while the selected attention KV cache is only 2 * 8 * 128 * 2 * 36 = 144MB << 16GB. In fact, in my measurements for the Qwen3-8B model using torch 2.14.1+cu130 and FlashInfer 0.7.2, full 16K-token attention takes only 30 μs each. Attention over 1K tokens takes only 9 μs each, or 325 μs in total—an order of magnitude faster than what you report. If the latency of attention over 1K tokens is negligible, the gain from overlapping it with selection is very questionable.
  3. Selection, according to Quest, is also very cheap. I am not sure why that is comparable to the FFN.
  4. Additionally, Qwen3 only has a context length of 32K; even with YaRN, it can be extended to at most 128K. I am not sure why the 512K results are presented.
  5. The BlockSparseAttention optimization is interesting but seems unrelated to your core contributions. Again, this is an implementation-side optimization rather than a system design contribution.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.