MAC-Attention: a Match-Amend-Complete Scheme for Fast and Accurate Attention Computation

Jinghan Yao; Sam Adé Jacobs; Walid Krichene; Masahiro Tanaka; Dhabaleswar K Panda

cs.LGMar 31, 2026

MAC-Attention: a Match-Amend-Complete Scheme for Fast and Accurate Attention Computation

Authors: Jinghan Yao, Sam Adé Jacobs, Walid Krichene, Masahiro Tanaka, Dhabaleswar K Panda

Organizations: The Ohio State University · Microsoft, WA, USA · Anyscale, CA, USA

Abstract

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 $\tilde{Q}_{m}$ against a small ring of recent queries; if the nearest match $p$ passes an L2 threshold, fetch its attention summary $\mathrm{AS}_{1:p-r}$ (otherwise run full attention). (b) Complete (critical path): with the post‑RoPE query $q_{m}$ , compute attention only on the band+tail $[\,p{-}r{+}1,\,m\,]$ and log‑domain merge $\mathrm{AS}_{1:p-r}\oplus\mathrm{AS}_{p-r+1:m}$ ; the KV $[1,p{-}r]$ is not accessed. (c) Amend (async): compute a rectification term $\mathrm{AS}_{r+1:m}$ and update the cache via online subtraction to obtain $\mathrm{AS}_{m-r}$ ; insert $\tilde{q}_{m},\mathrm{AS}_{m-r}$ into the rings. Symbols: $p$ —match position, $r$ —band width; $\oplus$ —log‑domain merge, $\ominus$ —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^{\downarrow}_{\%}$	Finish $\%$	Acc.	$KV^{\downarrow}_{\%}$	Acc.	$KV^{\downarrow}_{\%}$
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^{\downarrow}_{\%}

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.

KV %	Full Attn.	Quest	RocketKV	Multipole	MAC-Attn.
1	29.0	27.6	29.4	27.6	30.2
5	29.0	27.8	29.2	27.8	30.4
10	29.0	27.6	29.2	30.2	30.2
20	29.0	28.2	29.4	28.0	29.6

Table 2: Overall accuracy on LongBench v2

KV %	Full Attn.	Quest	RocketKV	Multipole	MAC-Attn.
1	234.2	581.2	822.8	192.4	62.9
5	234.2	594.7	844.7	210.8	64.0
10	234.2	608.5	1042.5	265.4	78.1
20	234.2	640.5	1855.6	324.6	103.8

Table 3: End-to-end Attention Latency (

\mu

s) on 120K context

Model / Setting	$\boldsymbol{\tau}$	$\mathbf{K}$	$\mathbf{r}$	Overall Acc.	Hit (%)	Skip (%)
Full attention	–	–	–	37.0	–	–
MAC-Attention	0.45	512	256	37.0	99.5	98.9
MAC-Attention	0.45	1024	256	36.6	99.6	99.0
MAC-Attention	0.45	2048	256	37.6	99.6	98.8
MAC-Attention	0.45	4096	256	36.6	99.7	98.6

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 ( $\Delta$ ) 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\times

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 (

\mu

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 $\tau$ . Left: LongBench v2. Right: LongGenBench. Solid: quality (relative to baseline). Dashed: KV usage (lower is better).

Figure 10: Normalized KV token efficiency $\big(\text{Acc.}/\text{KV-usage fraction}\big)$ across rectification band and search window . Stars denote accuracy $\geq\theta$ of baseline.

Settings			LongBench v2
Threshold $\tau$	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

\tau

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.

Explore similar work

MKA: Memory-Keyed Attention for Efficient Long-Context Reasoning
Mar 21, 2026Dong Liu, Yanxuan Yu, Ben Lengerich +1Attention Mechanisms Long-Context Language Modeling
University of California, Los Angeles, Los Angeles, California, USA · Columbia University, New York, New York, USA · University of Wisconsin-Madison, Madison, Wisconsin, USA
CSAttention: Centroid-Scoring Attention for Accelerating LLM Inference
Mar 30, 2026Chuxu Song, Zhencan Peng, Jiuqi Wei +1LLM Inference Acceleration Long-Context Language Model Inference
Department of Computer Science, Rutgers University · Oceanbase, Ant Group.
RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inference
Jun 30, 2026Wenhao Li, Jinhao Dong, Hailin Zhang +3KV Caching Long-Context Language Model Inference
School of Information, Renmin University of China, Beijing, China · Peking University, Beijing, China

Mar 21, 2026J/K move · Enter open · S save

MKA: Memory-Keyed Attention for Efficient Long-Context Reasoning

Dong Liu, Yanxuan Yu, Ben Lengerich, Ying Nian Wu

University of California, Los Angeles, Los Angeles, California, USA · Columbia University, New York, New York, USA · University of Wisconsin-Madison, Madison, Wisconsin, USA

Attention Mechanisms Long-Context Language Modeling KV-Cache Management LLM Inference Acceleration Memory-Augmented Language Models

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

MKA: Memory-Keyed Attention for Efficient Long-Context Reasoning

CSAttention: Centroid-Scoring Attention for Accelerating LLM Inference

RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inference