Long-context decoding in LLMs is IO-bound: each token re-reads an ever-growing KV cache. Prior accelerations cut bytes via compression, which lowers fidelity, or selection/eviction, which restricts what remains accessible, and both can degrade delayed recall and long-form generation. We introduce MAC-Attention, a fidelity- and access-preserving alternative that accelerates decoding by reusing prior attention computations for semantically similar recent queries. It starts with a match stage that performs pre-RoPE L2 matching over a short local window; an amend stage rectifies the reused attention by recomputing a small band near the match boundary; and a complete stage fuses the rectified results with fresh attention computed on the KV tail through a numerically stable merge. On a match hit, the compute and bandwidth complexity is constant regardless of context length. The method is model-agnostic and composes with IO-aware kernels, paged-KV managers, and MQA/GQA. Across LongBench v2 (120K), RULER (120K), and LongGenBench (16K continuous generation), compared to the latest FlashInfer library, MAC-Attention reduces KV accesses by up to 99%, cuts token generation latency by over 60% at 128K, and achieves over 14.3x attention-phase speedups, up to 2.6x end-to-end, while maintaining full-attention quality. By reusing computation, MAC-Attention delivers long-context inference that is both fast and faithful. Code is available here: https://github.com/YJHMITWEB/MAC-Attention.git
Figures & tables
Figure 1: Accuracy vs. KV budget (the fraction of KV cache used in each decoding step) across long‑context benchmarks. Top: LongBench v2 (up to 120K context) Bai et al. (2024) . Bottom left: LongGenBench (up to 16K continuous generation) Wu et al. (2024) . Bottom right: RULER (120K context) Hsieh et al. (2024) . MAC‑Attention is highlighted (dark pink); Full attention shown as a gray dashed line.
Figure 2: MAC‑Attention: Match–Amend–Complete with async cache update. (a) Match: at position m , compare the pre‑RoPE query Q~m against a small ring of recent queries; if the nearest match p passes an L2 threshold, fetch its attention summary AS1:p−r (otherwise run full attention). (b) Complete (critical path): with the post‑RoPE query qm , compute attention only on the band+tail [p−r+1,m] and log‑domain merge AS1:p−r⊕ASp−r+1:m ; the KV [1,p−r] is not accessed. (c) Amend (async): compute a rectification term ASr+1:m and update the cache via online subtraction to obtain ASm−r ; insert q~m,ASm−r into the rings. Symbols: p —match position, r —band width; ⊕ —log‑domain merge, ⊖ —log‑domain removal. Shaded regions denote KV segments not re‑read under reuse.
Figure 3: Decode micro‑pipeline for MAC -Attention . (a): per‑request rings L2 match with SplitQ design; (b): per‑head work spans differ because the reuse point p and band size r vary, the schedule assigns more CTAs to longer band+tail spans as shown in green blocks; many heads do a cheap merge when reuse is strong; (c): Overview of MAC -Attention workflow.
LongBench v2
LongGenBench
RULER
Model
Config.
Overall
Short
Medium
Long
KV%↓
Finish %
Acc.
KV%↓
Acc.
KV%↓
LLaMA-3.1-8B
Full attention
29.0
35.0
26.0
25.0
0
93.1
34.7
0
79.8
0
Grattafiori et al. (2024)
Quest-8K/4K/8K
28.0
33.9
24.2
25.9
85
92.8
32.9
35
77
93
Quest-4K/3K/4K
27.4
33.3
24.7
23.1
92
91.6
34.8
48
75.5
97
Quest-2K
27.8
32.2
26.0
24.1
96
89.9
33.8
63
73.4
98
Quest-1K
26.2
33.3
22.3
22.2
98
83.6
27.2
80
72.4
99
Table 1: Main accuracy results across models and benchmarks. Accuracy (%) on LongBench v2 (up to 120K context), LongGenBench (up to 16K continuous generation), and RULER (120k context). Rows compare Full attention , Quest variants (config / shows the budget settings for each benchmark; Quest only supports LLaMA models.), and our MAC-Attention . The KV%↓ columns report average KV-budget reduction relative to full attention (higher is more savings); - denotes not applicable. LongGenBench is generation-heavy; most models cannot complete the required task; we therefore report Finish% (higher is better), and finish-weighted accuracy.
Table 4: Evaluation on MoE model (Qwen3-30B-A3B-Instruct)
Figure 4: Rectification error vs. reuse gap and band width. Layerwise heatmaps show the normalized output error as a function of reuse gap ( Δ ) and rectification band width ( r ); representative layers are displayed.
Figure 5: Layerwise reuse patterns. Acceptance rate (left) and skipped‑prefix fraction (right) per layer. Top: threshold sweep at fixed window size. Bottom: window‑size sweep at fixed threshold.
Figure 6: Attention speedup vs. batch size and KV skip ratio across context lengths. Speedup is computed as the combined attention‑phase latency of our scheme (512-token matching window, load-balanced planning, rectified‑prefix reuse, and tail attention). The wide shared axes are split into four subgroups for contexts {32K, 64K, 128K, 256K}; within each subgroup, the x‑axis places batch sizes {1,2,4,8,16,32} , the y‑axis (shown once, left) is log‑scale with a 1× reference line. Each line denotes a KV skip ratio. For more thorough latency comparison with existing efficient attention methods, refer to § 5.4 .
Figure 7: End‑to‑end decode latency breakdown and speedup. For a fixed batch size, stacked bars show phase‑level latency (QKV+RoPE, attention, FFN, misc.) under full attention and MAC -Attention across contexts and skip ratios; speedup is computed end‑to‑end.
Figure 8: Kernel‑level costs and load balancing. (a) L2 Match kernel latencies under different GQA settings and window lengths (using standard Attention for reference). (b) Effect of the load‑balancing planner compared with a perfectly balanced oracle and an unbalanced baseline. (c–d) Per‑step composition of MAC -Attention (Match, Plan, Attention) across contexts.
Context
KV %
Full Attn.
MAC-Attention
Attention
Match
Load bal.
Attention
Overall
32K
1
71.6
9.1
28.8
26.0
63.9
32K
5
71.6
9.1
28.9
25.2
63.2
32K
10
71.6
9.1
28.6
25.1
62.8
32K
20
71.6
9.1
29.5
27.3
65.9
60K
1
133.0
9.1
28.6
24.8
62.5
Table 5: Fine-grained attention-path latency profile ( μ s) at fixed match window K=1024 . Full attention reports FlashInfer attention latency. MAC reports the Match kernel, load balancer, attention kernel, and overall attention-path latency.
Layer
Avg.
Std.
Layer
Avg.
Std.
0
-399
0
18
-278
17
6
-369
64
24
-483
121
12
-272
15
31
-346
40
Table 6: MAC Attention matching skew within each KV group at different model layers. Numbers are rounded to integers.
Search window K
Aux. HBM overhead %
256
1.2
512
2.3
1024
4.7
2048
9.4
Table 7: Approximate auxiliary HBM overhead at 128K context.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: Quality–efficiency trade-off vs. matching threshold τ . Left: LongBench v2. Right: LongGenBench. Solid: quality (relative to baseline). Dashed: KV usage (lower is better).
Figure 10: Normalized KV token efficiency (Acc./KV-usage fraction) across rectification band and search window . Stars denote accuracy ≥θ of baseline.
Settings
LongBench v2
Threshold τ
Window
Band r
Overall
Short
Medium
Long
Hit %
Skip %
Baseline (full attention)
29.0
35.0
26.0
25.0
–
–
0.30
inf.
512
26.6
30.6
25.1
23.1
99/99
55/86
0.35
inf.
512
26.8
34.4
22.8
22.2
99/99
55/86
0.45
inf.
128
25.6
29.4
21.4
27.8
96/95
56/85
0.45
inf.
256
27.2
33.3
22.3
26.9
96/95
55/85
Appendix
Table 8: Enabling MAC -Attention for both prefilling and decoding on LongBench v2. We sweep τ and band r ; the window is set to inf. to permit global search across the entire prefix (ablation-only; not production). Hit% and Skip% are reported as prefill/decode . Baseline is full attention.
As long-context language modeling becomes increasingly important, the cost of maintaining and attending to large Key/Value (KV) caches grows rapidly, becoming a major bottleneck in both training and inference. While prior works such as Multi-Query Attention (MQA) and Multi-Latent Attention (MLA) reduce memory by sharing or compressing KV features, they often trade off representation quality or incur runtime overhead. We propose Memory-Keyed Attention (MKA), a hierarchical attention mechanism that integrates multi-level KV caches (local, session, and long-term) and learns to route attention across them dynamically. We further introduce Route-Fused MKA (FastMKA), a broadcast-routed variant that fuses memory sources before attention computation for improved efficiency. Experiments on different sequence lengths show that FastMKA achieves a favorable accuracy-efficiency trade-off: comparable perplexity to MLA while achieving up to 5x faster training throughput and 1.8x lower evaluation latency. These results highlight MKA as a practical and extensible framework for efficient long-context attention.
Dong Liu, Yanxuan Yu, Ben Lengerich +1
University of California, Los Angeles, Los Angeles, California, USA · Columbia University, New York, New York, USA · University of Wisconsin-Madison, Madison, Wisconsin, USA
Long-context LLMs increasingly rely on extended, reusable prefill prompts for agents and domain Q&A, pushing attention and KV-cache to become the dominant decode-time bottlenecks. While sparse attention reduces computation and transfer costs, it often struggles to maintain accuracy at high sparsity levels due to the inherent distribution shift between Queries and Keys. We propose Centroid-Scoring Attention (CSAttention), a training-free sparse attention method optimized for high-throughput serving of reusable contexts. CSAttention adopts a storage-for-computation strategy tailored to the offline-prefill/online-decode setting: it front-loads computation into a one-time offline prefill phase that can be amortized across multiple queries, while aggressively optimizing per-step decoding latency. Specifically, CSAttention constructs query-centric lookup tables during offline prefill, whose size remains fixed during decoding, and enables online decoding to replace full-context scans with efficient table lookups and GPU-friendly score accumulation. Extensive experiments demonstrate that CSAttention achieves near-identical accuracy to full attention. Under high sparsity (95%) and long-context settings (32K-128K), CSAttention consistently outperforms state-of-the-art sparse attention methods in both model accuracy and inference speed, achieving up to 4.6x inference speedup over the most accurate baseline at a context length of 128K.
Chuxu Song, Zhencan Peng, Jiuqi Wei +1
Department of Computer Science, Rutgers University · Oceanbase, Ant Group.
Long-context Large Language Model inference is severely bottlenecked by the massive Key-Value (KV) cache, yet existing sparse attention methods often suffer from static fixed-budget (Top-k) retrieval or rely on proxy scores that are computationally expensive and biased. To address these limitations, we propose RaBitQCache, a novel sparse attention framework that utilizes randomized rotated binary quantization and high-throughput binary-INT4 arithmetic to efficiently estimate attention weights. Our proxy score serves as an unbiased estimator with a proven error bound, enabling adaptive Top-p retrieval that dynamically adjusts the token budget based on actual attention sparsity. We further implement a hardware-aware system with asynchronous pipelining and lazy updates to mask overhead. Evaluations demonstrate that RaBitQCache significantly accelerates inference and reduces memory I/O while preserving generation quality compared to state-of-the-art baselines. Code is available at https://github.com/Sakuraaa0/RaBitQCache.git.
Wenhao Li, Jinhao Dong, Hailin Zhang +3
School of Information, Renmin University of China, Beijing, China · Peking University, Beijing, China