Dynamic Sparse Attention: Access Patterns and Architecture

Noam Levy

cs.ARMar 13, 2026

Dynamic Sparse Attention: Access Patterns and Architecture

Authors: Noam Levy

Organizations: Intel Corporation.

Abstract

Dynamic sparse attention (DSA) reduces the per-token attention bandwidth by restricting computation to a top-k subset of cached key-value (KV) entries, but its token-dependent selection pattern introduces a system-level challenge: the KV working set is fragmented, volatile, and difficult to prefetch, which can translate into poor cache locality and stalled decode throughput. We study these effects by implementing a lightweight indexer for DSA-style selection on multiple open-source backbones and logging per-layer KV indices during autoregressive decoding. Our analysis shows a gap in serving DSA backbones - a potential for a high volume of blocking LL (last level) cache miss events, causing inefficiency; we propose a novel LL cache reservation system to save KV tokens in the LL cache between decode steps, combined with a token-granularity LRU eviction policy, and show on the data we collected how this architecture can benefit serving with DSA implemented on different backbones. Finally, we propose directions for future architectural and algorithmic exploration to improve serving of DSA on modern inference platforms.

Figures & tables

Figure 1: Dynamic Sparse Attention overview; an indexer, using a small number of heads and small projection dimensionality, scores each context token; the top-k score are selected, and a the KV values corresponding are gathered from the KV cache, which is typically stored in HBM memory; the scaled dot product attention is applied only to this subset

Figure 2: Blockwise sparse attention vs. DSA sparse attention; each query may select a completely different top- $k$ KV subset to attend to, eliminating the reuse potential of previous approaches and introducing an implementation challenge.

Backbone	N GPUs	HBM BW	Compute
LLama 3.1 70B	7	95%	1.3%
Llama 4 Maverick	26	99%	0.1%
GPT-OSS 120B	8	97%	0.2%
QWEN3-480B	32	99%	0.2%
DeepSeek 3.2	44	93%	67%

Table 1: H100 Rack utilization (per GPU) to decode at 100 tokens per second per user with a 64k context and batch size of 8

Resource	Dense	Sparse
SM Utilization	23.5%	10.9%
HBM BW Utilization	36.0%	7.3%

Table 2: Resource utilization for dense vs. sparse attention as measured using NVidia NCU on H200

Metric	Unit	Mean	P95	$\boldsymbol{\sigma}$
Working Set	top-k	5.15	7.2	1.02
Persistence	steps	1.82	5	2.86
Lookback steps	top-k	3.29	7.77	2.48
New lookups	top-k	0.55	0.9	0.22
Inter-layer	top-k	0.36	0.63	0.16

Table 3: Analysis of access patterns to the KV storage

Figure 3: Distribution of the number of KV entries in a working set of a 50 consecutive tokens, as a fraction of top-k

Figure 4: Distribution of persistence over time steps

Figure 5: Distribution of lookback distance, over fraction of top-k

Figure 6: Distribution of new lookup count, over fraction of top-k

Figure 7: Mean and standard deviation of metrics across the 80 layers of LLama 3.1-70B; (a) - lookback, (b) - new lookups, (c) - working set, (d) - inter-layer overlap

Figure 8: Proposed Architecture of KV-Granular Last Level Cache

LL reserved	0	5MB	10MB	15MB	20MB
Slowdown	1.87	1.67	1.5	1.3	1.15

Table 4: Roofline gain for implementing LRU cache reservation for KV tokens; LLaMa 3.1-70B, 20 layers on each GPU

Figure 9: Distribution of average KV page utilization per decode step

LLM Inference Acceleration

LLM inference acceleration develops algorithms and systems that reduce language-model latency, memory use, and serving cost while preserving output quality.

See all 1,084 papers

Predict, Reuse, and Repair: Accelerating Dynamic Sparse Attention for Long-Context LLM Decoding
Jun 29, 2026Tianyu Wang, Gourav Rattihalli, Aditya Dhakal +4Long-Context Language Model Inference LLM Inference Acceleration
University of Pittsburgh, Pittsburgh, PA, USA · HPE Labs, Milpitas, CA, USA
SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inference
Jun 3, 2026Yaosheng Fu, Guangxuan Xiao, Xin Dong +2KV-Cache Offloading Long-Context Language Model Inference
1NVIDIA · 2Thinking Machines Lab · 3ByteDance Seed +1
Joint Subspace Sparse Attention for Efficient Long-Context Decoding
Oct 13, 2026Jiwon Song, Yoongon Kim, Jae-Joon KimLLM Inference Acceleration Sparse Attention
Seoul National University

Jun 29, 2026J/K move · Enter open · S save

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

Tianyu Wang, Gourav Rattihalli, Aditya Dhakal, Junbo Li+3

University of Pittsburgh, Pittsburgh, PA, USA · HPE Labs, Milpitas, CA, USA

Long-Context Language Model Inference LLM Inference Acceleration Sparse Attention

Open paper AskPDF 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

Abstract

LLM Inference Acceleration

Explore similar work

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

SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inference

Joint Subspace Sparse Attention for Efficient Long-Context Decoding