Key-value (KV) caching is a core mechanism in large language models, where intermediate key and value representations are stored to accelerate autoregressive decoding. As generation length increases, KV cache memory and computation grow linearly, making compression critical for efficient long-output reasoning. Dictionary-based sparse KV compression is appealing because it represents each token's KV states as a sparse combination of learned basis elements (atoms) in a dictionary, preserving token-level structure without enforcing a global low-rank constraint. However, existing dictionary-based methods face two practical limitations during decoding: iterative sparse coding methods such as Orthogonal Matching Pursuit add decoding-time overhead, and static dictionaries may mismatch evolving KV distributions under test-time generation. While adaptive dictionary updates can reduce this mismatch, naive append-only strategies lead to dictionary growth during generation. We propose FAD-KV, a Fast Adaptive Dictionary KV caching framework for efficient reasoning decoding. FAD-KV integrates (i) a screening-based sparse coding scheme, where a one-shot Top-n selection identifies a small candidate pool followed by lightweight coefficient refinement, and (ii) a fixed-size dictionary adaptation mechanism that reuses inactive atoms instead of expanding the dictionary. By controlling both sparse coding cost and adaptive dictionary growth, FAD-KV provides a memory-bounded and computation-efficient KV compression framework for long reasoning workloads. Experiments on reasoning and long-context benchmarks show that FAD-KV achieves a strong quality-efficiency trade-off while avoiding unbounded dictionary growth during decoding.
Figures & tables
Figure 1: Motivation for FAD-KV. Diagnostics are computed using Llama-3.2-3B on MATH-500 with 4096 -atom key/value dictionaries and sparsity s=8 . (a)–(b) Decoding-time KV vectors have head-heavy dictionary correlations; we visualize value-vector scores as an example, and show that a small Top- n screened pool recalls most full-OMP atoms. (c)–(d) many atoms remain inactive after prefill, and inactive capacity is common across prompts. These observations motivate screening-based sparse coding and fixed-size dictionary adaptation.
Figure 2: Overview of FAD-KV. Each incoming KV vector is first encoded through screening-based sparse coding. If reconstruction error is high, FAD-KV replaces an inactive atom with a context-relevant atom instead of appending a new one, keeping the dictionary size fixed throughout decoding.
Method
Llama-3.2-3B-Instruct
Llama-3.1-8B-Instruct
Qwen3-4B-Instruct
GSM
MATH
GPQA
LongR.
GSM
MATH
GPQA
LongR.
GSM
MATH
GPQA
LongR.
Adaptive growth
Lexico-ADP
30.0
16.4
15.7
44.0
80.0
41.4
28.3
64.0
65.6
31.0
21.7
26.0
GM (ours)
26.0
17.8
22.2
40.0
76.0
42.8
27.3
66.0
59.2
27.8
22.2
25.0
PL (ours)
32.8
19.4
17.2
38.0
74.4
41.2
27.8
68.0
64.4
33.6
21.7
20.0
Fixed-size adaptation
Table 1: Accuracy (%) on reasoning benchmarks. Best accuracy is bolded within each dictionary group.
Model
Method
8K
16K
S1
MK
MV
MQ
FWE
Avg.
S1
MK
MV
MQ
FWE
Avg.
Llama-3.2 3B
Lexico-ADP
65.6
43.0
19.1
17.5
44.1
37.9
47.6
28.8
13.2
9.4
55.1
30.8
GM (ours)
65.6
42.8
18.3
17.1
44.1
37.6
46.8
29.2
13.5
9.3
55.6
30.9
PL (ours)
65.8
42.8
18.7
17.9
44.1
37.9
47.4
29.4
13.4
9.5
54.3
30.8
Lexico
66.0
44.8
14.5
11.9
35.3
34.5
46.6
28.6
10.9
6.8
40.7
26.7
FAD-KV (GM)
66.2
44.8
14.4
12.8
35.7
34.8
48.0
29.4
11.2
7.8
40.3
27.3
Table 2: RULER results (%) at 8K and 16K context lengths. We report NIAH single-key ( S1 ), multikey ( MK ), multivalue ( MV ), multiquery ( MQ ), and FWE, together with their average.
Model
Method
Single-Doc
Multi-Doc
Summ.
Code
NrtvQA
MF-en
Hotpot
2Wiki
Musique
SAMSum
LCC
RB-P
Llama-3.2 3B
Lexico-ADP
19.50
39.94
46.99
38.52
21.09
5.60
26.64
27.10
GM (ours)
19.97
39.94
47.06
38.63
20.43
5.31
26.62
26.88
PL (ours)
19.20
40.15
46.75
38.52
21.10
5.70
26.60
27.22
Lexico
16.99
38.95
46.66
37.68
20.37
5.70
26.47
26.98
FAD-KV (GM)
18.33
38.40
44.66
35.85
19.97
5.33
26.45
26.75
Table 3: Accuracy (%) on LongBench. Best results are bolded within each dictionary group.
Model
Method
Cost ↓
Latency ↓
Decode ↑
Speedup ↑
Per-seq KV ↓
(ms/tok)
(tok/s)
(compare Lexico)
(GB)
Llama-3.2 3B
Full KV
–
26.41
37.86
–
0.124
Lexico-ADP
1.00
53.63
18.64
–
0.024
GM (ours)
0.19
51.22
19.52
+4.7%
0.025
PL (ours)
0.13
49.95
20.02
+7.4%
0.031
FAD-KV (GM)
0.19
52.00
19.23
+3.1%
0.020
Table 4: Decoding efficiency and KV-cache memory.
Figure 3: Adaptive behavior and sensitivity analysis. (a) Normalized dictionary size during Qwen3-4B-Instruct GSM8K decoding. (b) Reconstruction error on the same setting, averaged over K/V streams, layers, and active examples. (c) Sensitivity of MATH500 accuracy to τc and δ . (d) Sensitivity to dictionary size N and sparsity s .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
Symbol
Value
Dictionary size
N
4096 (3B and 4B models); 8192 (8B model)
Sparsity budget
s
8 (3B and 4B models); 16 (8B model)
Candidate-pool size
n
256 (3B and 4B models); 512 (8B model)
Ridge parameter
λ
10−4+0.20diag(G)
Adaptation threshold
δ
0.50 (key) / 0.70 (value)
Maximum new tokens
1024 (MATH500, GSM8K, LongBench)
Appendix
Table 5: Default hyperparameters used in dictionary-based experiments.
Reasoning language models often generate long chain-of-thought (CoT), which accumulates a massive KV cache during the decoding phase and incurs high decoding latency and limited throughput. To address these issues, KV cache compression has emerged as a promising technique for reducing memory overhead by selectively removing unimportant KV pairs while preserving useful ones for subsequent decoding. Nevertheless, we identify two key limitations in existing KV cache compression methods: 1) their threshold-triggered compression policy may provide limited throughput improvement or even reduce throughput, and may fully eliminate KV pairs from certain blocks of the sequence, potentially worsening information loss. 2) they typically retain either isolated KV pairs or fixed-size chunks with rigid boundaries, failing to preserve important flexible-sized chunks at arbitrary token positions. To overcome these limitations, we propose Kara, a sliding-window KV cache compression method that performs decoding-time compression by operating only on the recently generated context. Kara leverages bidirectional attention to score and select informative KV pairs in the window. To enable flexible preservation of important semantic information, we design a Token2Chunk module to expand a subset of selected KV pairs into chunks. Furthermore, we adapt Kara to PagedAttention and develop KvLLM, an inference framework built upon vLLM, which reduces KV cache memory usage and effectively improves output throughput. Extensive experiments demonstrate consistent performance improvements of proposed Kara and KvLLM.
Key-Value (KV) cache remains a major bottleneck for deploying Large Language Models (LLMs) in long-generation tasks. Prior work often applies uniform compression across both prefill and decoding caches, but compressing the prefill cache degrades performance by corrupting critical context. While preserving the prefill cache is essential, decoding-phase compression remains underexplored, with existing methods relying on rigid recency windows or instantaneous attention. Our analysis of attention dynamics reveals strong temporal patterns: critical tokens receive sustained attention over long horizons, while local reasoning involves short-lived bursts. Static heuristics fail to capture this behavior, leading to premature eviction of important tokens or retention of stale ones. We propose Moment-KV, a decoding-time KV cache compression method based on momentum-driven temporal attention aggregation. Our method models token importance as a continuously evolving state, where attention is aggregated with decay, capturing both long-term influence and recent relevance. Experiments show that Moment-KV significantly improves generation fidelity in long-generation tasks (2.3-3.2 %) while maintaining decoding latency.
Long chain-of-thought reasoning substantially increases KV-cache memory during autoregressive decoding, as every generated token introduces new key and value states and causes the cache to grow linearly with decoding length. Existing KV-cache compression methods typically control this growth through token eviction, but irreversible deletion can remove historical states that later reasoning may need to revisit. SVD-based low-rank compression provides an alternative by retaining all positions with a more compact representation. However, extending it from a fixed prompt cache to online decoding is non-trivial. Through our investigation, we find that if the basis is updated for new tokens while old tokens keep their coordinates in the old basis, the stored history drifts substantially. Based on this observation, we propose iS-KV, an online low-rank KV-cache compression method for long-horizon reasoning. iS-KV keeps a recent window exact while incrementally folding older states into bounded-rank representations. As the low-rank basis evolves, it synchronizes historical coordinates with the updated basis to maintain representation consistency. On DeepSeek-R1-Distill-Llama-8B, iS-KV achieves 82.6% accuracy at 4.06-fold persistent-KV compression, close to the original model's 83.6%. On Qwen3-8B, it achieves 89.2% accuracy at 5.64-fold compression. Under matched memory budgets, iS-KV consistently outperforms token-eviction baselines.
Yiren Zhao, Guanghui Song, Tianrui Qin +3
The Hong Kong University of Science and Technology (Guangzhou) · Guangdong OPPO Mobile Telecommunications Corp., Ltd. · Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences +2