Lexico: Extreme KV Cache Compression via Sparse Coding over Universal Dictionaries
Authors: Junhyuck Kim
Jongho Park
Jaewoong Cho
Dimitris Papailiopoulos
Venue: ICML 2025 poster (2025)
Keywords: transformer
kv cache
compression
Primary area: deep_learning->large_language_models
TL;DR: We introduce a novel KV cache compression method that leverages sparse coding with a universal dictionary.

Abstract: We introduce Lexico, a novel KV cache compression method that leverages sparse coding with a universal dictionary. Our key finding is that key-value cache in modern LLMs can be accurately approximated using sparse linear combination from a small, input-agnostic dictionary of ~4k atoms, enabling efficient compression across different input prompts, tasks and models. Using orthogonal matching pursuit for sparse approximation, Lexico achieves flexible compression ratios through direct sparsity control. On GSM8K, across multiple model families (Mistral, Llama 3, Qwen2.5), Lexico maintains 90-95% of the original performance while using only 15-25% of the full KV-cache memory, outperforming both quantization and token eviction methods. Notably, Lexico remains effective in low memory regimes where 2-bit quantization fails, achieving up to 1.7x better compression on LongBench and GSM8K while maintaining high accuracy.

Lexico: Extreme KV Cache Compression via Sparse Coding over Universal Dictionaries
Junhyuck Kim
Jongho Park
Jaewoong Cho Dimitris Papailiopoulos
Abstract
requires its own KV cache, limiting opportunities for reuse across different user inputs, with the exception of prompt caching that only works for identical input prefixes. This creates bottleneck in generation speed for GPUs with lim- ited memory (Yu et al., 2022). Thus, it has become crucial to alleviate KV cache memory usage while preserving its original performance across domains.
We introduce Lexico, novel KV cache compres- sion method that leverages sparse coding with universal dictionary. Our key finding that key-value cache in modern LLMs can be accu- rately approximated using sparse linear combi- nation from small, input-agnostic dictionary of ~44 atoms, enabling efficient compression across different input prompts, tasks and models. Us- ing orthogonal matching pursuit for sparse ap- proximation, Lexico achieves flexible compres- sion ratios through direct sparsity control. On GSM8K, across multiple model families (Mis- tral, Llama 3, Qwen2.5), Lexico maintains 90- 95% of the original performance while using only 15-25% of the full KV-cache memory, out- performing both quantization and token eviction methods. Notably, Lexico remains effective in low memory regimes where 2-bit quantization fails, achieving up to 1.7x better compression on LongBench and GSM8K while maintaining high accuracy. Our code is available at https: / //g //github... www////o/////eeeeccoeeeeeeeeeeee kraft on-onn--oo on-oooooaaaaaooooooaeoeooooeeiie lexico.
Extensive post-training KV cache optimization re- search (Kwon et al., 2023; Lin et al., 2024; Ye al., 2024) offers off-the-shelff methods for pretrained LLMs, including selectively retaining tokens (Beltagy et al., 2020; Xiao et al., 2023; Zhang et al., 2024b) and quantizing KV cache to 2 or bits (Liu et al., 2024b; He et al., 2024; Kang et al., 2024). However, eviction strategies have limitations on complex reasoning tasks that require retaining majority of previous tokens, while quantizations to 2 or 4 bits have clear upper bounds compression rates.
In this paper, we focus on utilizing low-dimensional struc- tures for efficient KV cache compression. Prior work reports that each key vector lics in low-rank subspace (Singhania et al., 2024; Wang et al., 2024b; Yu et al., 2024). Yet, is unclear whether all vectors lie in the same subspace; if so, such redundancy remains be taken advantage of. Thus, naturally ask the following questions:
1. Introduction
Do keys and values lie in low-dimensional subspaces across diverse input sequences? If so, can we leverage this for efficient KV cache compression?
Transformers (Vaswani et al., 2017) have become the back- bone of frontier Large Language Models (LLMs), driving progress in domains beyond natural language processing. However, Transformers are typically limited by their sig- nificant memory requirements. This stems not only from the large number model parameters, but also from the having to maintain the key-value (KV) cache that grows proportional to the model size (i.e., the number of layers, heads, and also embedding dimension) and token length of the input. Additionally, serving each model session typically
Towards this end, propose Lexico, universal dictionary that serves overcomplete basis, which sparsely decompose and reconstruct the KV cache with sufficiently small reconstruction eπто that can be directly controlled via the level of sparsity of each reconstruction.
In Section 2.2, we report our observation that a subset of key vectors cluster near each other, even though the keys are from different inputs, while some cluster in different subspaces. To take advantage of such -ow-dinensional structure, we draw inspiration from compressed sensing and dictionary learning, areas of statistical learning and signal processing that developed algorithms for information compression across various domains (Candès et al., 2006; Donoho, 2006; Dong et al., 2014 4; Metzler et al., 2016).
'KRAFTON Uniiversity of Wisconsin-Madison 'Microsoft Research. Correspondence to: Dimitris Papailiopoulos <dim- itris@ papai...o.....
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Key Cache
K
Sparse Key Cache
Uncompressed Buffer
Kcsr
V
k
OMP
D
buffer
Sparse Approximation Algorithm
D
q,D
4;
Sparse
SparseMatMul
MatMul
KV Cache
a
(a) Prefilling Stage
(h) Decoding Stage
Figure (a) Prefilling:
Following attention computation, Lexico uses OMP find sparse representations of the KV vectors (3-8x smaller). (b) Decoding: Key cache consists of the compressed sparse key cache, Ken. and an full full-precision buffer, Kuttter for the most recent tokens. qt, k, represent the query, key vectors
newly generated token. Computation is reduced by computing the query-dictionary product, q: Dr, then multiplying Kar. to get the pre-softmax attention score.
Lexico simple learn, can be applied off-the-sheil for KV cache compression, and only occupies small constant memory regardless of imput or batch size.
than baseline quantization methods on challenging lan- guage tasks, such LongBench (Bai et al., 2023) and GSM8K (Cobbe al., 2021).
Methodologically. Lexico utilizes both sparsity- based com- pression (steps and 2) and quantization (step 3) in three straightforward steps:
Compression rates beyond 2-bits: Lexico's 's sparsity parameter enables both wider and more fine-grained control over desired memory usage. This allows to explore performance when using under 15-20% of the original KV cache size, a low-memory regime previous compression methods could not explore.
Dictionary pretraining: For our experiments, we train dictionary WikiTText-10 103 (Merity, 2016) for each model. This dictionary is only trained once and used universally across all tasks. It only occupies constant memory and does not increase with batch size. We note that this dictionary can be trained from richer sources to improve the overall performance of our sparse ap- proximation algorithms.
Instead of an input-dependent dictionary, we find sufficiently small universal dictionary (per model) that can be used for all tasks and across multiple users. Advantagcously. such dictionary does not scale with batch size and can be used off-the-shelf.
Universality:
2. Sparse decomposition: During prefilling and decod- ing (Figure 1). Lexico decomposes key-value pairs into sparse linear combination, which consists of pairs of reconstruction coefficients and dictionary indices pointing. This step by itself provides high compression rates.
2. KV Cache Compression with Dictionaries
2.1. Background & Notation
During autoregressive decoding in Transformer, the key and value states for preceding tokens independent of subsequent tokens. As a result, these key and value states are cached to avoid recomputation, thereby accelerating the decoding process.
3. Lightweight sparse coefficients: We obtain higher KV cache compression rates by representing the sparse coefficients in 8 bits instead of FP16. Lowering pre- cision to bits yields minimal degradation. Lexico theoretically allows us compress more than 2-bit quantization (1/8 of FP16 6 KV cache size) if 10 when head dimension is 128.
Let the input token embeddings be denoted as E R xd where leey and d are the sequence length and model hidden dimension, respectively. For simplicity, we focus layer and express the computation of query. key, and value states at each attention head during the prefilling stage as:
single
Overall, we make the following contributions:
(W((h)
K XW
(h)) (W
Near-lossless performance: Given similar memory requirements, Lexico performs on par with or better
where W
W!! ddxm are the model weights with m representing the head dimension.
2

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Layer 10 Keys
Layer 10 Keys
1.00
1.00
0.75
6-
0.75
9-
12
12
0.25
18
0.25
21
21
24
0.00
24
0.00
27
27
-0.25
30
-0.25
33
33
36
0.50
36
-0.50
39
0.75
45
-0.75
48
48
11.00
-1.00
24
33
36
Figure Left shows a pairwise cosine similarity matrix between key vectors generated from one input from heads in Layer 10 of Llama-3, I-8B-Instruct. Keys are sorted by similarity to demonstrate the clusters. Right shows the similarity matrix between key vectors from two different input texts. These plots indicate that there may exist mixture low-dimensional subspaces the space all possible keys, hypothesis that naturally leads dictionary learning.
Let represent the current step in the autoregressive decod- ing, and let 2; E RIxd xx denote the embedding of the newly generated token. The KV cache up but not including the
Sparse approximation, which aims to find y with minimum sparsity given and D, while ensuring a small reconstruc- tion error, is NP-hard. This optimization problem is typi- cally formulated as:
current token, are denoted as K and (/hh) respectively.
The typical output computation for each attention head hath) using the KV cache can be expressed as:
min || subject ||k Dyllz 8 ||
for some relative error threshold >> 0.
qi
K
(R) 6-1
(h)
h
(b)
Softmax
(v(h) (
m
In this work, we adopt Orthogonal Matching Pursuit (OMP) the sparse approximation algorithm. Given an input key or value vector k, a dictionary D, and target sparsity OMP iteratively selects dictionary atoms to minimize the fz-reconstruction error, with the process continuing until the specified sparsity s is reached. Our implementation OMP builds on advanced methods that utilize properties of the Cholesky inverse (Zhu et al., 2020) optimize performance. Additionally, incorporate implementation details from (Lubonja et al., 2024) for efficient batched GPU execution and extend it to include an extra batch dimension, allowing for parallel processing across multiple dictionaries. The full algorithm is detailed in Appendix A.
where qi
g0,), kg o represent the query, key, and value
(h) (h)
vectors for the new token embedding vt. Here, denotes concatenation along the sequence length dimension.
2.2. Sparse Approximation
Given a dictionary, our goal is decompose and represent KV cache efficiently, i.e,, approximate vector E m linear combination of few vectors (atoms) from overcomplete dictionary D E m This reconstruction is given by k Dy, where y E IR is the sparse represen- tation vector such that = | lo- For implementation, y only requires space proportional to 8, not N.
2.3. Learning Layer-specific Dictionaries
hypothesize that the KV cache, like other domains where sparse approximation is effective, contains inherent redun- dancy that can be leveraged for efficient compression. For instance, Figure 2 presents pairwise cosine similarity plots for keys generated during inference on a random subset of the WikiText dataset. Here, we observe that key vectors cluster in multiple different subspaces. Dictionary learning can take advantage of such redundancy, enabling KV vec- tors be represented by a compact set of atoms with only few active coefficients.
Layer-specific dictionaries. While the sparse approxima- tion algorithm crucial, achieving a high compression ratio relies heavily on well-constructed dictionaries. In this sec- tion, we describe the process for training the dictionaries used in Lexico. We adopt distinct dictionaries for the key and value vectors in each transformer layer due to their different functionalities. We denote the key and value dic- tionaries at each layer as D2 and D, E " where N is the fixed dictionary size. With N = 1024, the dic- tionaries add an additional 16.8MB to the model's storage requirements for 7B/8B models.
3

---

Table 2. Reconstruction error. Relative reconstruction errors different methods when training dictionary of size 1024 and spar- sity on WikiText- Sparse Autoencoder a two-layer activation (encoder KV Cache Compression via Sparse Coding over Universal Dictionaries
findex, value)
0.4
CSR teneor
02
0.24
perceptron with hard top-k thresholding as a linear layer + activation in Figure 3). Lexico is optimized using OMP encoder. KV cache is generated from Llama-3.1-
1.2
Trainable Dictionary
0.1
0.4
0.08
OMP(A:
1.2
022
0.24
D
8B-Instruct.
0.4
1.2
0.4
Sparse
Random
Test Dataset
Lexico
Autoencoder
Dictionaries
V
Sparse representation
K, V
WikiTex-- 103
0.17 + 0.06
0.20 0.05
0.27 0.02
Approximation
Reconstruction
CNN/DailyMail
0.19 = 0.05
0.22
0.27 0.02
IMDB TweetFvvl
0.18 = 0.05
0.22 +: 0.05
0.27 +: 0.02
0.18 0.06
Figure 3. Dictionary Learning of Lexico. We train linear layer D (our dictionary) that minimizes & fg-reconstruction error of KV cache. The KV cache of layer are used as training data for dictio- nary D Each step, we apply OMP with fixed D to represent KV as vector of sparse coefficients: we then perform step of gradient descent on D and repeat the process. A sparse vector can he efficiently stored as a CSR, using a tuple 16-bit index and 8-bit value.
tion errors, such as 0.19 + 0.05 on out-of-domain dataset CNN/DailyMail,, and this trend is consistent across other datasets.
Despite being trained only on WikiText-103, Lexico dictio- naries demonstrate degree of universality: our dictionaries achieve lower test loss on out-of-domain datasets such as TweetEval than the test loss on WikiText-103 for sparse au- toencoders, offering significant compression with minimal reconstruction error. In the next subsection, we explore how low fg-reconstruction loss translates strong performance preservation in language modeling.
As shown in Figure 3, train layer-specific KV dictio- naries via direct gradient-based optimization. For given key or value vector, denoted as E IR" and a dictionary D mx the OMP algorithm approximates the sparse representation y NRN. This process is parallelized across multiple dictionaries, but for simplicity, we present the nota- tion for single dictionary. The dictionary training objective minimizes the E norm of the reconstruction error, with the loss function L = k Dyll We enforce unit norm con- straints on the dictionary atoms by removing any gradient components parallel to the atoms before applying updates.
2.4. Prefilling and Decoding with Lexico
During the prefilling stage, each layer generates the KV vec- tors for the input tokens, illustrated in Figure la. Lexico uses full preecisinn KV vectors for attention computation, which are then passed subsequent layers. Subsequently, OMP finds the sparse representations of the KV vectors using layer-specific key and value dictionaries, Då and D,-
Training. The dictionaries are trained on KV pairs gener- ated from the WikiText- 103 dataset using Adam (Kingma & Ba, 2014) with a learning rate of 0.0001 and cosine decay schedule over 20 epochs. The dictionaries are initialized with a uniform distribution. Table summarises training time for Llama-3. 3.1-BB- -nstrutt on single NVIDIA A100 different sparsity and dictionary size N.
The compressed key and value caches are denoted as K Ves E R and replace the full-precision KV cache. Their reconstructions become K KesDD and V = V.y
Recall that at the t-th iteration of autoregressive decoding, each layer receives qt. k, and v; the query, key, and value vectors corresponding to the newly generated token. Sim- ilarly to prior work (Liu et al., 2024b; Kang al., 2024). we find that keeping a small number of recent tokens in full precision improves the generative performance of the model. To achieve this, we introduce buffer that temporarily stores recent tokens in uncompressed state. The KV vectors stored in the buffer are denoted as K Vouffer IR Xm. where ni is the number of KV vectors in the buffer. The key cache up to, but not including the token at iteration I is then reconstructed as follows:
We demonstrate our trained dictionaries reconstruct and gen- eralize better than dictionaries trained using sparse autoen- coders (similarly to those from Makhzani & Frey (2013); Bricken et al. (2023)) across several corpora in Table 2. Our method consistently achieves lower relative reconstruc-
Table Dictionary training time (minutes) for Llama-3.1
Instruct on an A100 GPU for different sparsity levels s and dictio- nary sizes N.
K,- K.uD. K
Dictionary size
s-4
s=8
s=16
$=32
1=10
70
119
N 4090
78
100
160
322

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Substituting this reconstruction into the Equation the attention weights for each head at are computed as:
long-context understanding, we conduct experiments on selected tasks from LongBench (Bai et al., 2023), following the setup of Liu et al. (2024b). See Table 7 in Appendix B for task details.
qi (K
(h) (1) D
K
(b) bulfer
k )
(h) Softmax ai
vm
Additionally, we evaluate generative performance on com- plex reasoning tasks, such as GSM8K (Cobbe et al., 2021) with 5-shot prompting and MMLU-Pro Engineer- ing/Law (Wang et al., 2024a) with zero-shot chain-of- thought. We choose these MMLU-Pro subjects since they are deemed the most difficult as they require complex for- mula derivations or deep understanding of legal knowledge intricacies. We compare our method against two kinds of KV cache compression methods: namely, quantization- based compression and eviction-base compression. For quantization- methods, we evaluate KIVI (Liu et al., 2024b), ZipCache (He et al., 2024), and the Hugging Face implementation for per-token quantization. For eviction- based methods, we evaluate PyramidKV (Cai et al., 2024) and SnapKV (Li et al., 2024). We refer to the 4-bit and 2-bit versions of KIVI as KIVI-4 and KIVI-2, respectively, and denote its quantization group size as g-
A key implementation is that attention for the compressed sparse key cache and the uncompressed key cache is com- puted separately. For compressed sparse key cache, we first compute the product qi (h) D2 before multiply Kest directly calculating the pre-softmax attention scores for com- pressed tokens. Attention for the buffer tokens is computed as usual. These scores are then concatenated with softmax to produce the final attention weights (Figure lb). This process is formalized as:
(1) qi
Dr K
(h) (K
As (1))
(1) Softmax
qi
a
Vm
where represents concatenation along columns for attention scores.
When the buffer reaches capacity, OMP compresses the KV vectors for the oldest na tokens in the buffer. This process independent of the attention computation for the newest token and can therefore be performed in parallel.
We report KV size as the average percentage of the com- pressed cache relative to the full cache generation end. Sparsity s is set to match the KV size of the baseline.
Time and space complexity. The sparse representa- tions are stored in CSR format, with values encoded in FP8 (E4M3), and all indices, including offsets, are stored as Ant16. Each row in CSR corresponds to a single key or value vector. For a given sparsity level s, the memory usage includes: nonzero values (s bytes), dictionary indices (2s bytes), and the offset array (2 bytes), resulting in a total size of 38 + 2 bytes. For head dimension of 128, fully uncompressed vector using FP 16 takes 256 bytes, yielding a memory usage of 3s+2 32).
Hyperparameter settings. For both experiments, Lex- ico uses dictionary size of N 4096, a buffer size of n6 = 128, and an approximation window size na 1, compressing the oldest token with each new token gener- ated. For KIVI-4 and KIVI-2, we use quantization group size of = 32 and a buffer size of ni 128, as is tested and recommended in Liu et al. (2024b), for LongBench. For GSMSK and MMLU-Pro, we test for stronger memory savings, so we use g = 64 and n., 64 for KIVI.
256 x 100 x 1.175% (e.g., 37.5% for
3.1. Experimental Results
In terms of time complexity, computing q: T for a sin- gle head requires mlsem)) multiplications. On the other hand, q: K needs (Nm++ multiplications. This means that computation is particularly well-suited for long-context tasks when 4sog N where N is anywhere between 1024 and 4096. For short contexts when loog < N, our method only adds a small overhead to attention compu- tation in actuality.
LongBench results. Table 3 presents the performance of Lexico and KIVI on LongBench tasks. Lexico demonstrates hetter performance than KIVI with similar or even smaller KV sizes. Notably, Lexico enables exploration of extremely low memory regimes that KIVI-2 cannot achieve. At a memory usage of just 12.4% KV size, Lexico maintains reasonable long-context understanding, with only 5.6%p and 4.4%p performance loss on Llama-3. -88t-nsrruutt and respectively, compared the full cache (FP16). The largest performance loss comes from tasks with the lowest full cache accuracy, Qasper, yet there is almost no loss in simpler tasks, such as TriviaQA. This indicates that difficult tasks that require more complex understanding are much more sensitive to performance loss. Hence, it is important to evaluate on GSM8K, one of the harder natural language reasoning tasks, as we do next.
3. Experiments
on
Setup. We evaluate our method various models (Llama-3-8B, -lama-3.1-8B-Instiie Instruct. -lama-3.233B-Instee 1ree2.55-4B-IInttruee
Llama-3.2211 BBB Mistral--B-Inntrruet, using dictionaries trained on WikiText- 103, as done in Section 2.3. To assess the effec- tiveness of Lexico in memory reduction while maintaining
5

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Table Experimental results on LongBench. Lexico, we use 4096 the dictionary size and na, 128 as buffer size. For
KIVI, use 9 32 (group size for quantization) and ny 128 (huffer size). Sparsity level is set match average KV size of KIVI, while = corresponds to eache size unattainable by common 2-bit quantizations. Full cache FP16.
Method
KV Size
Qasper
QMSum
MultiNews TREC
TriviaQA
SAMSum
LCC
RepoBench-P
Average
Llama 3.1-8B-Instrue
Full Cache
100%
22.54
24.57
27.44
72.5
91.65
43.47
63.15
56.76
50.26
KIVI-4
33.2%
22.83
23.72
27.95
71.0
90.39
44.25
62.93
55.48
49.78
Lexico 24
30.6%
21.68
24.25
27.20
72.5
91.58
42.93
62.92
56.51
49.95
KIV1-2
21.1%
13.77
22.72
27.35
71.0
90.85
43.53
62.03
53.00
48.03
Lexico =616
21.4%
15.45
23.13
25.78
72.5
92.25
42.02
63.01
55.58
48.71
Lexico
12.4%
11.66
21.04
22.35
60.0
91.01
40.30
59.60
51.46
44.68
Full Cache
100%
41.58
25.69
27.76
76.0
88.59
47.58
59.37
60.60
53.40
KTVT-4
33.2%
40.37
24.51
27.75
74.0
88.36
47.56
58.49
58.31
52.42
Lexico 24
30.6%
41.01
25.32
27.51
76.0
88.84
46.27
59.98
59.44
53.05
KIV1-2
21.1%
38.24
24.08
26.99
74.5
88.34
47.66
57.51
56.46
51.72
Lexico 16
21.4%
40.34
24.97
26.36
76.0
89.31
45.84
59.31
59.50
52.70
Lexico 12.4%
33.03
22.80
22.85
68.5
87.85
43.10
56.66
56.85
48.96
Table Experimental results on GSM8K. For Lexico, we use = 4096 as the dictionary size and na = 128 as the huffer size. For KIVL, we use g 64 (group size quantization) and nu 64 (buffer size). Sparsity level s set match the average KV size KIVI, while s = 4 corresponds to cache size unattainable by common 2-bit quantizations. Full cache is in FP 1P16 6. We include example
generations of KIVI and Lexico in Appendix C.I.
(a) Llama 3.x 8B Models
(b) Mistral 7B v0.3 Model
Method
KV Size
Llama-3-8B
Method
KV Size
7B-Instruct
Full Cache
100%
49.89
79.61
Full Cache
100%
48.60
KIVI-4
38.2%
49.
78.17
KIVI-4
38 38.2%
48.52
Lexico ==24
36.9%
48,29
76,88
Lexico ==20
32.7%
48 48.60
KIV1-2
25.7%
40.56
67.93
KIVI-2
25.7%
42.91
Lexico 14
26.1%
48.75
75.06
Lexico ==10
22.0%
44.35
Lexico
15.8%
40.03
51.71
Lexico -=4
15.8%
39.20
GSM8K results. The performance of Lexico on GSM8K compared KIVI is shown in Table 4. With KV size of 36.9%, Lexico on Llama 8B models experiences a slight accuracy drop of less than 3%p, underperforming KIVI-4 at a similar KV size. However, in the lower memory regime near 25% KV size, Lexico significantly outperforms KIVI- 2, achieving a higher accuracy by 8.2%p on the Llama-3- 8B model and 7.1%p on the Llama-3. 1-8B-Instruch model. These results highlight the robustness of Lexico in low- memory settings, demonstrating that low reconstruction enror can be achieved using only a few atoms from our universal dictionary. To further test the resilience of Lexico, we set the sparsity to s = 4, observing a noticeable drop in accuracy on the Llama-3.1 --B--..-------ttrcc model. Despite this, both Llama models maintain an accuracy above 40%, which is remarkable given that only 4 atoms from Lexico used for each key-value vector, utilizing just 15.8% of
the full cache, including the buffer.
The performance of Lexico on the Distral-7B-Instruu model is even more impressive. We demonstrate that for Mistral, Lexico not only outperforms KIVI-4 and KIVI-2 but also achieves higher accuracy with even less memory usage. We also evaluate Lexico with
on the Mistral model and observe an accuracy of 39.2%, further demon- strating robustness in low-memory settings.
Results across model sizes and baselines. We illus- trate the trade-off between memory usage and performance across six different KV cache compression methods on Llama models (1B, 3B, and 8B) in Figure 4. For all three model sizes, Lexico consistently lies on the Pareto fron- tier, achieving higher scores than other compression meth- ods at similar KV cache budget sizes. Notably, Lexico demonstrates greater robustness at smaller model scales,
6

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Llama-3 1ooma-3.2-14 1aiaaa...2-B--n--t 1--Instruut
Llama-3.2 3.0--3.-----sruuccc
Llama 3.1 1-88--nnstruct
70
80
70
x1.23
x1.10
60
GSMBK Score
50
x2.27
50
40
10
30-
60
KV Size (%))
KV Size (%)
KV Size (%)
Full Cache
Per-Token Q
ZipCache
PyramicKV
Lexico
KIVI
SnapKV
Figure 4. Memory usage vs. performance of Lexico compared to other KV cache compression methods on GSM8K. The figure illustrates the relationship between KV cache size and the performance of Lexico Llama models GSM8K. For Lexico, N = 4096 as the dictionary size and = 128 as the buffer size. Lexico consistently outperforms both eviction-based methods (SnapK PyramidKY V) and quantization-base methods (per-token quantization, KIVI, ZipCache).
with larger performance gaps observed for the IB and 3B models. In the extremely low-memory regime below 20%, where quantization methods such KIVI and ZipCache cannot achieve feasible cache sizes, Lexico achieves supe- rior performance. Furthermore, while eviction- based meth- ods VS PyramidKV) can operate in these extremely low-memory settings, their performance lags significantly behind due to their incompatibility with Grouped Query Attention (GQA), making Lexico the effective choice for stringent memory constraints. We also evaluate Lexico larger model, @wen2.5-14BB-Instrn quantized to 4 bits, comparing it against quantization meth- ods. The results, illustrated in Figure 5, show that Lexico achieves higher GSM8K score than KIVI under similar KV cache budgets. Additionally, Lexico enables higher com- pression ratios than 2-bit quantization methods, facilitating deployment under extreme memory- memooy-constrained scenarios.
3.2. Ablation Study
Error thresholding in sparse approximation. Lexico also supports quality-controlledd method for memory sav- ing by allowing early termination of the sparse approxi- mation process when predefined error threshold is met. This approach conserves memory that would otherwise be used for marginal improvements in approximation quality, Detailed descriptions and results of this ablation study are provided in the Appendix D.I.
with its weights
Performance without buffer. To evaluate the impact of the buffer, we first conducted experiments with varying sparsity without the buffer, with the results shown by the dashed lines in Figure Appendix D.2. The comparison shows that removing the buffer results in a more pronounced decline in performance, especially at lower KV sizes.
MMLU-Pro results. Figure illustrates the trade-offs between memory usage and performance for Lexico on the MMLU-Pro Engineering and Law subjects using the LJama-3.1-SB-Insttrucc model. Lexico outperforms eviction- based methods like SnapKV and PyramidKV across all memory settings, though its performance comparable quantization-basee methods such as KIVI and ZipCache. However, in a low memory regime below 20% cache, our method still outperforms any other baseline. This highlights that Lexico supports wide range of compression ratios
Table 5. Balancing memory between buffer and sparse repre- sentation. Performance of Lexico with the 1ama--.1-8B-Insttm model on LongBench tasks while varying the memory allocation between the buffer and the sparse representation, with the total KV
cache size fixed at 25% of the original size.
Qasper
MultiNews
TREC
mb
Fl Score
ROUGE-I
Accuracy
862
6.38
1
503
17.20
1232
58.5
724
8.36
4
423
20.21
4
1035
63.5
517
14.58
8
302
21.27
8
739
65.0
quite effectively and that our dictionary is generalizable across input distributions.
12
278
17.84
12
163
22.81
12
398
63.5
16
0
8.27
16
0
10.70
16
0
54.5
7

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
GSMBK [Qwen2.5-1e) Sww.en2.--48--nstrruee Instrrcct)
MMLU Engineering (Liama-32-8BB-nnttue 2.8-innsruct
MMLU Pro
2-8-instrucc))
90
30
25
70
20
20
Accuracy
15
-0
15-
10-
30
10
50
40
30
20
45
40
35
30
25
20
15
196)
KV Size (9)
KV Size (%)
Full Cache
Per-Token O
ZipCache
Full Cache
Per Token
ZipCache
PyramidKV
Lexico
Lexico
KIVI
SnapKV
Figure 5. Memory usage vs. performance of Qwen2.5--14-Instruue with Lexico GSM8K. We compare the performance of Lex- ico against quantization methods on Qwen2.5- 14B-Inst with its weights quantized to 4 bits. For Lexico, we use 4096 as the dictionary size and nı 128 as the buffer size.
Figure Memory usage vs. performance of -llama-3.--8--Immstt with Lexico MMLU-Pro Engineering/Lav. For Lexico. size and r2s = 128 as the buffer size. Lexico often outperforms both eviction- based methods (SnapKV, PyramidKV) and quantization-based methods (per-token quantization, KIVI, ZipCache). For Law, our method slightly underperforms around %, but in lower memory regimes, our method still outperforms any other baseline.
N 4096 the dictionary
Balancing memory between buffer and sparse represen- tation. As shown in Table 5, we examine how balancing memory allocation between the buffer and the sparse repre- sentation affects performance. By fixing the total KV cache size at 25% of the original, we vary the memory distribution between the buffer and the sparse representation across three LongBench tasks: Qasper, MultiNews, and TREC. The re- sults demonstrate that long-context understanding ability while using Lexico is not solely reliant on the buffer or the sparse representation. Rather, there exist optimal balance points where performance is maximized for each task.
but cannot be shared across batches, requiring them to be included in the KV size calculation. While this approach boosts accuracy, it increases memory usage, limiting its ability to achieve low memmomory regimes. Detailed methods and results provided in Appendix D.3.
3.3. Latency Analysis
In this section, we present latency measurements of the forward pass and OMP portion of Lexico during decoding in Table 6. We simple generation tests 1000-token input to the Llama-3.1 1-8-a...-8B-Instruee model and generate up to 250 tokens. We compare dictionary sizes of N = 1024 and 4096, which primarily affects OMP computation time, while setting the sparsity level s = 24 and processing OMP in batches of n. 8.
Adaptive dictionary learning. While our universal dic- tionaries demonstrate strong performance, explore adaptive learning method to better incorporate input-specific context. This adaptive approach improves performance by adding new dictionary atoms during generation when the predefined reconstruction error threshold is not met. These atoms, tailored to the input prompt, improve performance
Although Table 6 separately lists the forward pass and OMP time, these processes can be parallelized: generating one token takes the maximum of the two durations plus some
Table Latency measurements. Time (ms) compute one new token across 32 layers of Llama-3.1 1--.a33.--8---ttrue We report the standard full pellipreiision forward pass and Lexico 's forward pass/ OMP step for dictionary sizes 1020 and N 4096 at various sparsity levels s.
N
1024
N
4096
Computation type
Full
8=4
8=8
8=16
8=24
8=4
8=8
8=16
2424
Standard forward pass (gK*)
48.39
Lexico: forward pass using q (K.,. D.) T and D.
53.90
54.67
55.46
55.56
57.24
56.64
57.13
56.35
Lexico: sparse approximation (OMP)
6.03
10.16
18.31
26.57
9.37
15.55
28.37
40.58
8

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
overhead. However, parallelization introduces time-space tradeoff, as running OMP also increases GPU memory us- age.
ings especially for long-context tasks without discarding any tokens.
Despite these advantages, Lexico has several limitations. Most notably, as shown in Section 3.3, it does not of- fer latency improvements. While well-suited for highly memory-constrained scenarios, it may be less effective in tightthroughut settings, as latency becomes a key per- formance bottleneck. Additionally, the OMP algorithm introduces GPU-side memory overhead, which may limit reductions in peak memory usage. These trade-offs suggest that Lexico is best suited for memory-constrained settings where throughput is not the primary bottleneck.
Higher latency may limit Lexico's suitability for latency- critical use cases. Nonetheless, our primary focus is on memory-constrriiee scenarios where a single GPU can be exceeded with just batch size of one. By prioritizing memory efficiency, Lexico remains feasible where other methods risk out-of-memory errors, making it valuable for deployment in memory-limiter settings.
4. Related Work
Future directions include further optimizing CSR tensors with customized quantizations, improving the OMP-related latency tradeoff's, and exploring "soft-eviction" strategies that dynamically adjust sparsity based on token importance. Additionally, while our current implementation adopts stan- dard greedy OMP for its efficiency in memory-consttrined settings, extending it to a beam search variant-which selects the top- B atoms at each veration-could further improve re- construction accuracy, albeit with increased computational overhead. Investigating such trade-off's between approxima- tion quality and efficiency remains an interesting avenue for future work.
Prior work on KV eache optimization spans training-stage and deployment-fouused methods. On the deployment side, Kwon et al. (2023) introduces Paged Attention mechanism and the vLLM framework. While there is significant and important line of research in this direction (Lin et al., 2024; Qin et al., 2024), this direction is orthogonal to our work and can often be used in tandem with quantization. Post-training techniques focus on three main categories: (1) evicting tokens based on attention scores or heuristics (Ge al., 2023; Li al., 2024; Liu et al., 2024a; Devoto al., 2024; Dong al., 2024), (2) quantizing KV cache with per- channel or -ioddimeniiona schemes (Hooper et al., 2024; Liu et al., 2024b; Yue et al., 2024; Kang et al., 2024), and (3) merging tokens or memory blocks. These approaches can complement one another, as shown by Liu et al. (2024a)
Impact Statement
This paper presents a method to efficiently compress KV cache when employing Transformer-aase models. Al- though there are potential societal consequences of our work, there are none which we feel must be specifically highlighted.
in successfully combining quantization and eviction.
A recent work, QJI,, introduces a promising 1-bit quanti- zation method for KV cache compression (Zandich et al., 2025). However, QJL applies its transformation exclusively to keys (using per-token quantization for values), while Lex- ico compresses both keys and values, enabling a more com- prehensive and memory-efficient solution. Another line of work, PQCache, leverages product quantization by partition- ing vectors into sub-blocks and learning centroids for each subspace (Zhang et al., 2024a). Compression is achieved by replacing each sub-block with its nearest centroid. In contrast, Lexico employs sparse coding, representing each vector as a sparse linear combination of dictionary atoms.
References
Bai, Y., Lv, X., Zhang, J., Lyu, H., Tang, J., Huang, Z., Du, Z., Liu, X., Zeng, A., Hou, L., et al. Longbench: A bilingual, multitask benchmark for long context under- standing, arXiv preprint arXiv:2308.
2023.
Beltagy, L. Peters, M. E., and Cohan, A. Long- former: The long-document transformer. arXiv preprint arXiv:2004.05155 2020.
5. Conclusion and Limitations
Bricken, T., Templeton, A., Batson, J., Chen, B., Jermyn, A., Conerly, T., Turner, N., Anil, C., Denison, C., Askell, A., et al. Towards monosemanticity; Decomposing language models with dictionary learning. Transformer Circuits Thread, 2, 2023.
In conclusion, Lexico offers a novel way to compress KV caches by leveraging low-dimensional structures and sparse dictionary learning, revealing substantial redundancy among key cache vectors across diverse inputs. This enables near- lossless compression that often surpasses traditional quan- tization methods, while offering fine-grained control over memory usage. The universal dictionary remains compact and scalable, making it broadly applicable without increas- ing memory requirements, and yields strong memory sav-
Cai, Z., Zhang, Y., Gao, B., Liu, Y., Liu, T., Lu, K., Xiong, W., Dong, Y., Chang, B., Hu, J., et al. Pyramidkv: Dy- namic kv cache compression based on pyramidal informa- tion funneling. arXiv preprint arXiv:2406.. 02069, 2024.

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Candès, E. J., Romberg, J., and Tao, T. Robust uncertainty principles: Exact signal reconstruction from highly in- complete frequency information. IEEE Transactions information theory, 52(2):489- 509, 2006.
Li, Y., Huang, Y., Yang, B., Venkitesh, B., Locatelli, A., Ye, H., Cai, T., Lewis, P., and Chen, D. Snapkv: Llm knows what you are looking for before generation. arXiv preprint arXiv:2404. 14469, 2024.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L.,, Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 11.22100..44666 2021.
Lin, B., Peng, T., Zhang, C., Sun, M., Li, L., Zhao, H., Xiao, W., Xu, Q. Qiu, X., Li, S., et al. Infinite-llmt Efficient Ilm service for long context with distattention and distributed kvcache. arXiv preprint arXiv:240..0666) 2024.
Devoto, A.,
Zhao, Y., Scardapane, S., and Minervini, A simple and effective 22 norm-based strategy for kv cache compression. arXiv preprint arXiv:2406.1 1430, 2024.
Liu, Z., Desai, A., Liao, F., Wang, W., Xie, V., Xu, Z., Kyril- lidis, A., and Shrivastava, A. Scissorhands: Exploiting the persistence of importance hypothesis for Ilm kv cache compression at test time. Advances in Neural Information Processing Systems, 36, 2024a.
Dong, H., Yang, X., Zhang. Z., Wang, Z., Chi, Y., and Chen, B. Get more with less: Synthesizing recurrence with kv cache compression for efficient I1m inference. In Forty-first International Conference on Machine Learn- ing. 2024.
Liu, Z.. Yuan, J., Jin, H., Zhong, S., Xu, Z., Braverman, V., Chen, B., and Hu, X. Kivi: A tuning-free asym- metric 2bit quantization for kv cache. arXiv preprint arXiv:2402.02750, 2024b.
Dong, W., Shi, G., Li, X., Ma, Y., and Huang, F. Com- pressive sensing via nonlocal low-rank regularization. IEEE transactions image processing, 23(8):3618- 3632, 2014.
Lubonja, A., Præsius, S. K., and Tran, T. D. Efficient batched cpu/gpu implementation of orthogonal matching pursuit for python. arXiv preprint arXiv:2407.06433 444.44444 2024.
Donoho, D. Compressed sensing. IEEE Transactions on information theory, 52(4):1289-1308 2006.
Makhzani, A. and Frey, B. K-sparse autoencoders. arXiv preprint arXiv:
Ge, S., Zhang, Y., Liu, L., Zhang, M., Han, J.. and Gao, Model tells you what to discard: Adaptive kv cache compression for Ilms. In The Twelfth International Con- ference on Learning Representations, 2023.
2013.
Merity, S. The wikitext long term dependency language
modeling dataset. Salesforce Metamind, 9, 2016.
Metzler, C. A., Maleki, A., and Baraniuk, R. G. From denoising compressed sensing. IEEE Transactions on Information Theory, 62(9):5117-5144 2016.
He, Y.. Zhang, L., Wu, W., Liu, J., Zhou, H., and Zhuang, B. Zipcache: Accurate and efficient kv cache quanti- zation with salient token identification. arXiv preprint arXiv:2405.14 14256. 2024.
Qin, R., Li, Z., He, W., Zhang, M., Wu, Y., Zheng, W., and Xu, X. Mooncake: A kveache-centric disaggre- gated architecture for Ilm serving, 2024. arXiv preprint trxiv:2407.00079 2024.
Hooper, C., Kim, S., Mohammadzadeh, H., Mahoney, M. W., Shao, Y. S., Keutzer, K., and Gholami, A. Kvquant: Towards 10 million context length I1m in- ference with kv cache quantization. arXiv preprint 2rXiv:2401.18073 2024.
Singhania, P., Singh, S., He, S., Feizi, S., and Bhatele, A. Loki: Low-rank keys for efficient sparse attention. arXiv preprint arXiv:2406.. 025442 2024.
Kang. H., Zhang, Q. Kundu, S., Jeong, G., Liu, Z., Krishna, T., and Zhao, T. Gear; An efficient kv cache compression recipefor near-lossless generative inference of llm. arXiv preprint arXiv:2403.05527 2024.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Atten- tion is all you need. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp. 5998-6008. 2017.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.603 2014.
Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Sym- posium on Operating Systems Principles, pp. 616622, 2023.
Wang, Y., Ma, X., Zhang, Ni, Y., Chandra, A., Guo, S., Ren, W., Arulraj. A., He, X., Jiang, Z., et al. Mmlu-pro: A more robust and challenging multi-task language under- standing benchmark. arXiv preprint arXiv:2406.01574 2024a.
10

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Wang, Z., Jin, B., Yu, Z., and Zhang, M. Model tells you where to merge: Adaptive kv cache merging for Ilms on long-context tasks. arXiv preprint arXiv:2407.08454, 2024b.
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. Ef- ficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations, 2023.
Ye, L., Tao, Z., Huang, Y., and Li, Y. Chunkattention: Efficient self-attention with prefix-aware kv cache and two-phase partition. arXiv preprint arXiv:2402.15220, 2024.
Yu, G.-I, Jeong, S., Kim, G.-W., Kim. S., and Chun, B.- G. Orca: A distributed serving system for (Transformer- Based] generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI
22), pp. 521 521-538, 2022.
Yu, H., Yang, Z., Li, S., Li, Y., and Wu, J. Effectively com- press kv heads for Ilm. arXiv preprint 2xXtv:2406.07056, 2024.
Yue, Y., Yuan, Z., Duanmu, H., Zhou, S., Wu, J., and Nie, L. Wkvquant: Quantizing weight and key/value cache for large language models gains more. arXiv preprint arXiv:2402. 12065, 2024.
Zandieh, A., Daliri, M., and Han, Qjl: 1-bit quantized jl transform for kv cache quantization with zero overhead. In Proceedings of the AAAI Conference Artificial In- telligence, volume 39, pp. 25805-25811 2025.
Zhang, H., Ji, X., Chen, Y., Fu, F., Miao, X., Nie, X., Chen, W., and Cui, B. Pqcache: Product quantization-basel kvcache for long context IIm inference. arXiv preprint arXiv:2407. 12820, 2024a.
Zhang, Z., Sheng, Y., Zhou, T., Chen, T., Zheng, I.., Cai, R., Song, Z., Tian, Y., Ré, C., Barrett, C., al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024b.
Zhu, H., Chen, W., and Wu, Efficient implementations for orthogonal matching pursuit. Electronics, 959):1507, 2020.

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Appendix
A. Implementation Details
Algorithm illustrates naive implementation OMP for understanding. In Lexico, we adopt the implementation OMP vO proposed by (Zhu al., 2020), which minimizes computational complexity using efficient inverse Cholesky factorization. Additionally, integrate methods from (Lubonja et al., 2024) for batched GPU execution and extend the implementation to handle multiple dictionaries in parallel.
Algorithm OMP
Require: Signal & RT dictionary D RT*X sparsity Ensure: Sparse representation y E R=
I: Initialize (0) k, T(0) 0, (0)
2: for 1 do n <- arg maxisnsN
{1(DD (k
Dyy")))
3:
4: 1 + 1(-1) [n())
5:
(++ arg min NERN {ilK- Dyll2 Supp (w) c I(9)
6: end for
7: return y
Algorithm 2 Prefilling and decoding with Lexico
I: Parameter: sparsity 8, buffer length na. approximation length na
2: procedure PREFILLING
3:
Input: X Rd XWE. t- XW,
5: Kos f- OMP [K]] [: beq Tib) D),
6: Ver +- OMP V Lag nu. Dv,s)
7: Knnter <- K Ulaq
:). Vintter f- V Ukn n2
KV cache f- Ken,, Kiuffe, Vea, Voutier
9:
return K,
10:
end procedure
11:
procedure DECODING
Input: KV cache, se E 1xd 1xd
13:
q: <- v. W,, kü &- w. Wk, v. <- æ; W.
14:
Ken; Kautter, Veu, Viutter + KV cache
15:
Knater +- Concat ( (Kutter kt] dim token)
Vuutter Concat ( (Vunteer, Vz] dim token)
a: < Concat (Iq: De Kar, q: nutter) dim token)
18:
G: < Softmax (az).
19:
V < Concat DD... Vouter] dim token)
20:
a.V
21:
if (Kutte)
Y&s, then
22:
<- OMP (Kinterr [: no] Du,
23:
V < OMP (Vuttee ntl, Dv, 8)
24:
K oz Concat K K' cx) dim token)
25:
Var Concat ( (Ve, V cal dim token)
26:
buller + K [e :]. Vautter +- Veuter [Na
27:
end
28:
KV cache <- Kon, Knitter Ven. Voutier
29:
return
30:
end procedure
12

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
B. LongBench Task Statistics
Table 7. Details of LongBench tasks used in experiments.
Task
Task Type
Evaluation Metric
Average Length
# of Samples
Qasper
Single-doc QA
Fl
3619
200
QMSum
Summarization
ROUGE-L ROUGE-L
10614
200
MultiNews
Summarization
2113
200
TREC
Few-shot information retrieval
Accuracy
5177
200
TriviaQA
Few-shot reading comprehension
FI ROUGE-L
8209
200
SAMSum
Few-shot dialogue summarization
6258
200
LCC
Code completion
Edit Similarity
1235
500
RepoBench-P
Code completion
Edit Similarity
4206
500
C. Qualitative Results
C.1. GSM8K Example Generation
The boxes highlight the correct intermediate answers that must be derived. The highlighted colors in red show incorrect reasoning and answers. We provide the original problem and solution below, along with outputs from Llama-3.1-88 1-8-1-8---snneeee with full KV cache (FP16), KV-Diet (sparsity 14), and KIVI-2.
Original Problem & Solution
Problem:
The Kennel house keeps German Shepherds and Bulldogs. German Shepherd consumes 5 kilograms of dog food and bulldog consumes kilograms of dog food per day, how many kilograms of dog food will they need in week?
Solution: The German Shepherds consume 3 x 5 = 15 kilograms of dog food per day.
The Bulldogs consume 3 kilograms of dog food per day.
The dogs consume total of 15 21 kilograms of dog food per day.
Therefore, they need 21 x 7 147 kilograms of dog food in a week.
Final Answer: 147
3lama-3.1-8B-Insttee with Full Cache
First, find the total amount of food the German Shepherds consume in a day: 3 dogs kg/dog 15 kg.
Then find the total amount of food the Bulldogs consume in day: 2 dogs kg/dog 6 kg.
Add the two amounts together to find the total amount of food the dogs consume in day: 15 kg +6 21 kg. Multiply that number by to find the total amount of food the dogs consume in week: 21 kg/day x7 days 147 kg.
Llama-3.1 1-iima3.1-B---nttruee with KV-Dict (s = 14)
The kennel has German Shepherds and 2 Bulldogs, so they have 3 + 2 = dogs.
The German Shepherds consume 3 = 15 kilograms of dog food per day. The Bulldogs consume 3 6 kilograms of dog food per day.
So, the kennel needs 15 + 21 kilograms of dog food per day.
In week, they will need 21 147 kilograms of dog food. The answer is 147.
Llama-3.1 3.1-8BB-Instrue with KIVI-2
13

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
The Kennel house has German Shepherds and Bulldogs, so they have a total of + 2 5 dogs.
Each German Shepherd consumes kilograms of dog food per day, so the total amount of dog food consumed by the German Shepherds is 5 = 25 kilograms per day.
Each Bulldog consumes 3 kilograms of dog food per day, so the total amount dog food consumed by the Bulldogs 2 x = 6 kilograms per day.
The total amount of dog food consumed per day is 25 +
31 kilograms.
The Kennel house will need 31 x 7 217 kilograms of dog food in week.
D. Ablation Study: Experimental Results
D.1. Error Thresholding in Sparse Approximation
For the error thresholding ablation study, detailed results are provided in Table We set maximum sparsity of 32, corresponding the maximum number of iterations for the OMP algorithm. However, if the reconstruction error at any iteration falls below predefined error threshold, we let the OMP terminate early, saving memory that would otherwise be used for minor approximation improvements. This approach is particularly compatible with OMP, as its greedy nature ensures that early termination yields the same results as using higher sparsity (less non-zero elements). Additionally, OMP inherently computes the residual at each iteration, allowing for continuous evaluation of the relative reconstruction error without requiring any additional computation.
Table Impact of error thresholding on LongBench performance and memory usage. The table presents the performance Lexico on the 1.ama-3.1 1-8B- Instructt model various reconstruction error thresholds (6) for carly termination of the sparse approximation algorithm. A dictionary size of N = 1024 and FP16 precision for the values of the CSR tensors are used.
Threshold (8)
KV Size
Qasper QMSum MultiNews
TREC
TriviaQA
SAMSum
LCC
RepoBench-P
Average
Llama-3. 1-88--BBsnssrn
Full Cache
100%
22.54
24.57
27.44
72.5
91.65
43.47
63.15
56.76
50.26
0.2
50.6%
20.03
23.65
26.44
72.5
91.61
43.47
62.72
56.63
49.63
0.3
41.1%
16.49
23.35
25.34
72.5
91.34
43.02
62.53
56.65
48.90
0.4
30.9%
16.08
22.91
23.77
69.5
90.79
42.70
61.28
54.82
47.73
0.5
22.8%
12.43
21.75
21.29
57.5
88.56
41.04
58.85
53.19
44.33
D.2. Performance without Buffer
In this section, we assess the effect of the buffer by comparing results with and without its use. The results for LongBench and GSM8K are presented in Table and Table 10, respectively.
D.3. Adaptive Lexico
While we observe some degree of universality in our dictionaries, as shown in Table 2, their performance is particularly strong on WikiText-103, the dataset they were trained on. To better incorporate input context information, we propose an extension that adaptively learns the dictionary during generation. In this framework, we begin with a pre-trained universal dictionary as the initial dictionary. If, during the generation process, the sparse approximation fails to meet the predefined relative reconstruction error threshold, the problematic uncompressed key or value vector normalized and added the dictionary. The sparse representation of this vector is then stored with a sparsity of newly added atom and its value is the & norm of the uncompressed vector. The updated dictionary is subsequently used for further sparse approximations during the generation task. In this way, the adaptive learning framework incrementally refines the dictionaries, tailoring them to the specific generative task and enhancing overall performance at the cost of additional memory usage.
where its index corresponds the
In our experiment, we use universal dictionary of size 1024, allowing up to 1024 additional atoms to be added during generation. The maximum sparsity of 16 is used, with a buffer size of n4 128, and FP16 6 precision for the values of the CSR tensors. Results of this experiment are presented in
14

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Memory Usage Performance on LongBench
Memory Usage Performance GSM8K
50
70
Average LongBench Score
60
40
GSMBK Score
50
40
30
20
20
Liama (without buffer)
Llama (without butfer)
10
1024,
Mistral (without butfer]
Mistral (without buffer)
Mistral (N 1024, FP16)
Mistral (N 1024. FP16)
10
80
70
KV Size (%)
KV Size (%)
Figure 7. Memory usage vs. performance of Lexico with and without buffer on LongBench and GSM8K. The figure illustrates the impact removing the buffer on the performance Lexico when evaluated Llama 3.I-8B Instructtt and Mistral BBIInstruct models for LongBench (left) and GSM8K (right) tasks. Solid lines represent configurations with buffer, while dashed lines represent configurations without buffer. We use dictionary size of N and FP1 precision values CSR tensors to vary sparsity and explore wide range of KV sizes.
Table LongBench performance without buffer. This table shows the impact of removing the buffer of Lexico on the performance of the -ama--.1-88--maa and Mistral-7B. IB-Instruc models at varying sparsity levels. A dictionary size of 1024 and FP1 precision for the values of the CSR tensors are used.
Sparsity
KV
Qasper
QMSum
MultiNews
TREC
TriviaQA
SAMSum
LCC
RepoBench-P Average
Llama-3, 1lama-3.1-8--mee Instrrettt
Full Cache
100%
13.10
23.46
26.94
72.5
91.65
43.47
63.15
56.76
48.88
32
50.8%
14.87
26.51
26.57
71.5
92.48
42.88
61.54
54.04
48.80
24
38.2%
13.37
25.02
22.54
65.0
91.75
39.71
52.21
46.48
44.51
16
25.8%
8.27
13.74
10.70
54.5
77.51
20.45
26.53
22.46
29.27
19.5%
6.31
10.15
5.66
39.0
53.70
22.18
19.46
20.41
8
13.3%
2.74
8.05
4.17
36.5
34.45
4.27
18.24
18.32
15.84
Full Cache
100%
41.58
25.69
27.76
76.0
88.59
47.58
59.37
60.60
53.40
32
50.8%
40.27
25.21
27.53
76.5
89.01
45.77
58.64
59.07
52.75
24
38.2%
37.46
24.41
27.34
75.5
88.66
43.87
48.55
49.50
49.41
25.8%
25.57
18.49
15.19
81.91
27.90
19.39
21.45
35.18
19.5%
18.59
13.11
5.95
50.13
2.86
13.38
12.60
21.83
8
13.3%
10.32
6.98
2.67
31.5
20.01
2.27
10.18
8.11
11.51
Table 10. GSMBK performance without buffer. This table shows the impact of removing the buffer Lexico on the performance of the Llama-3.11 1-------Instruu and Mistral- BB-nstruttt models varying sparsity levels. A dictionary size of N 1024 and EP16 precision for the values of the CSR tensors are used.
Sparsity
KV Size
Mistral-7B--nnstuut---ee
Full Cache
100%
79.61
48.60
32
50. 80.8%
69.07
43.97
24
38 2%
32,75
23.20
16
25.8%
1.97
1.29
12
19.6%
1.36
0.76
15

---

KV Cache Compression via Sparse Coding over Universal Dictionaries
Table 11. GSM8K performance adaptive Lexico. The table shows the GSM8K performance and KV cache sizes of adaptive Lexico on the 1lama-3.1 1-8--111--ttttuc and Baataal-B-IIstrutt--ve models varying reconstruction error thresholds (8). A universal dictionary of
size 1024 is used, with up to 1024 additional atoms added during generation. The maximum sparsity of 16, buffer size of na = 128,
and FF 6 precision for CSR tensor values applied.
Threshold (5)
1lama-3.1-8B-Instt
Mistral-7B-Insttuut--...
KV Size
GSM8K Score
KV Size
GSM8K Score
Full Cache
100%
79.61
100%
48.60
0.25
N/A
N/A
42.1%
48.07
0.30
43.5%
77.41
41.3%
48.14
0.35
42.0%
76.80
39.8%
47.76
16


Reviews:
[{"review_id": "qnb90bFs4Z", "reviewer": "Reviewer_Vzmg", "summary": "Lexico compresses the KV cache by finding a sparse representation of each key and value vector using a pre-trained dictionary. Instead of storing the full high-dimensional vectors, Lexico approximates them as a sparse linear combination of a small number of “atoms” (basis vectors) from this dictionary. It uses a technique called Orthogonal Matching Pursuit to efficiently select only a few atoms that best reconstruct the original vector, minimizing the reconstruction error. These sparse representations are much smaller in size and can be stored efficiently using formats like CSR, reducing memory usage.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are pleased that you appreciated the clarity of our experiments, Lexico's effectiveness, and our use of sparse coding. EtKf and EhUD similarly recognized the soundness of our experimental design. We address your concerns below, and would be grateful if you reevaluate our work in light of them.\n\n***LongBench***\n\nWe do not agree that our evaluation is limited. We have covered a comprehensive set of task categories such as document QA, summarization, few-shot tasks, and code completion; this aligns with prior work (e.g., KIVI) that evaluated on the same subset. For completeness, we have Lexico on all LongBench tasks with Llama-3.1-8B-Instruct below.\n\n||Avg.|NarrativeQA|Qasper|MultiFieldQA|HotpotQA|2WikiMultihopQA|MuSiQue|GovReport|QMSum|MultiNews|TREC|TriviaQA|SAMSum|PassageCount|PassageRetrieval|LCC|RepoBench-P|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|Full KV|39.02|23.43|22.54|28.42|16.63|15.3|9.05|35.04|24.57|27.44|72.5|91.65|43.47|1.01|93.33|63.15|56.76|\n|s=16|38.33|23.02|15.45|28.62|16.39|13.8|10.56|31.36|23.13|25.78|72.5|92.25|42.02|1.47|98.33|63.01|55.58|\n|s=8|34.23|14.29|11.66|22.04|13.89|12.45|9.74|23.41|21.04|22.35|60.0|91.01|40.30|0.89|93.62|59.60|51.46|\n\nThe newly added tasks demonstrate a similar trend as the other tasks. The performance remains nearly lossless when $s=16$ (21% of the original KV cache size). Our results remain consistent with our subset of tasks in Table 2. Even at $s=8$ (12% of the original), our approach maintains a strong performance-memory tradeoff; note that 12% is a regime 2-bit quantization cannot achieve. These results show Lexico's strength in handling long contexts.\n\n***Needle In A Haystack (NIAH)***\n\nWe show that Lexico is resilient to such stress-testing. Using Llama-3.1-8B-Instruct with an 8k context size, we followed the settings in PyramidKV. We compared against token eviction methods—which are well-suited for tasks that require only a few tokens from the context—and report ROUGE-1 multiplied by 10. Note that the columns represent the needle depth ratio.\n\nWe find that Lexico outperforms competitors on a 20% KV cache budget, while it delivers similar performance on a 10% budget. Note that the 10% budget is not feasible for 2-bit quantization methods. While we believe that NIAH is a valuable synthetic benchmark, performance on the task does not strongly reflect that of practical performance, as exemplified in the underperformance of eviction-based methods on GSM8K (Figure 4).\n\n|Method|KV Cache|0.0|0.2|0.4|0.6|0.8|1.0|\n|-|-|-|-|-|-|-|-|\n|Full KV|100%|7.06|7.06|9.30|7.06|7.06|7.06|\n|Lexico$_{s=16}$|20%|**7.06**|**7.06**|**9.09**|**7.06**|**7.06**|7.06|\n|PyramidKV|20%|6.06|4.12|4.24|4.78|4.18|**7.41**|\n|SnapKV|20%|6.06|4.12|4.24|5.15|3.94|**7.41**|\n|Lexico$_{s=8}$|10%|3.87|3.61|**5.88**|4.48|**4.26**|4.75|\n|PyramidKV|10%|**6.06**|**4.78**|4.18|4.12|4.18|**7.55**|\n|SnapKV|10%|**6.06**|4.18|4.85|**4.62**|3.94|7.41|\n\n***Dictionary training cost***\n\nTraining dictionaries is cheap because they only need to be trained once and can be provided by a third-party. As we report in L203, sparsity of s=32 and a dictionary size of N=1024 require only 2 hours on an A100 GPU. We provide the training runtime for different sparsities and sizes for Llama-3.1-8B-Instruct.\n\n| |s=4|s=8|s=16|s=32|\n|-|-|-|-|-|\n|N=1024|37m|52m|70m|119m|\n|N=4096|78m|100m|160m|322m|\n\n***Latency***\n\nWe kindly direct the reviewer to the *Hardware measurements* section in our response to reviewer EtKf (R2).\n\n***Dictionary sources and adaptability across domains***\n\nPer your suggestion, we investigated whether training a dictionary on a specific domain enhances the performance. In our ablation below, we trained a dictionary on different sources:\n1) Dictionary trained on WikiText-103.\n2) Dictionary trained on GSM8K training set.\n3) Dictionary trained on WikiText-103 then finetuned on GSM8K.\n\n|Sparsity|KV size|Trained on WikiText|Trained on GSM8K|Finetuned on GSM8K|\n|-|-|-|-|-|\n|s=24|36.9%|76.88|77.63|**79.68**|\n|s=14|26.1%|75.06|70.51|**75.89**|\n|s=10|22.7%|**69.67**|59.59|67.25|\n\nWe observe that training a dictionary from scratch on GSM8K significantly underperforms, especially at low sparsities. Overfitting to GSM8K fails to generalize even to its test set. In contrast, finetuning the universal dictionary on GSM8K provides marginal improvement but adds the additional overhead of custom fine-tuning.\n\n***Missing reference***\n\nWe appreciate the reviewer’s suggestion and will incorporate QJL into our related work. While QJL introduces a 1-bit quantization approach for KV cache compression, its experiments are confined to 3- and 5-bit schemes. In contrast, our work benchmarks Lexico against 2- and 4-bit state-of-the-art methods, and further pushes the efficiency by exploring memory regimes lower than 2 bits. Whereas QJL applies its transformation solely to keys (with per-token quantization for values), our approach compresses both keys and values, offering a more comprehensive and efficient solution.", "claims_and_evidence": "The submission's claims are generally well-supported by clear experimental results across multiple benchmarks and models. The evidence convincingly demonstrates Lexico’s compression effectiveness and performance retention. No major claims appear problematic.", "methods_and_evaluation_criteria": "Yes, the methods and evaluation criteria are appropriate for the problem. The use of sparse coding with universal dictionaries is well-justified, and the evaluation on standard benchmarks like LongBench and GSM8K effectively demonstrates performance and memory trade-offs.", "theoretical_claims": "The paper does not present formal theoretical proofs, but relies on established techniques like Orthogonal Matching Pursuit and sparse coding. The theoretical framing is sound, and no correctness issues were identified in the described methodology.", "experimental_designs_or_analyses": "Yes, the experimental design appears sound. The authors compare Lexico against strong baselines across diverse models and tasks, using consistent settings and fair memory budgets. The analyses of compression vs. performance trade-offs are thorough, and no major issues were found.", "relation_to_broader_scientific_literature": "The paper builds on prior work in KV cache compression, sparse coding, and dictionary learning. It extends ideas from compressed sensing and applies them in a novel way to LLM inference. Compared to quantization and eviction-based methods, Lexico offers finer-grained control and better performance in low-memory regimes, addressing limitations in previous approaches.", "essential_references_not_discussed": "The paper overlooks an essential reference: **QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overhead by Zandieh et al**. This work proposes a highly efficient 1-bit quantization method for KV cache compression, offering strong compression with minimal overhead. Given that Lexico aims to outperform quantization-based baselines, omitting QJL misses an important point of comparison—especially in the context of extreme low-memory regimes, where QJL sets a relevant benchmark. Including this citation would strengthen the discussion of related methods.", "other_strengths_and_weaknesses": "Weaknesses include a limited evaluation on LongBench only a subset of tasks is tested, which may not fully capture long-context challenges. The paper also lacks a \"needle-in-a-haystack\" style experiment, which is important for stress-testing memory compression in precision-critical scenarios. Additionally, while Lexico is positioned as efficient, more detailed analysis of training runtime, dictionary update cost, and latency during decoding (especially under different dictionary sizes and sparsity levels) would strengthen the claims. The absence of ablations on different dictionary sources or adaptability across domains is another gap worth addressing.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "At3hlq56NU", "reviewer": "Reviewer_EtKf", "summary": "This paper proposes a novel KV cache compression method based on sparse coding over a learned “universal” dictionary. The key idea is to represent KV cache vectors with a small number of dictionary “atoms,” reducing memory costs while preserving model performance across different tasks and domains. The paper reports encouraging results on select language tasks (e.g., GSM8K, LongBench), demonstrating near-lossless performance at significant compression ratios.\n\n## update after rebuttal\n\nThe authors have addressed most of my questions. I keep my opinion that this paper leans toward being accepted. The additional results and clarifications should be integrated into the manustript.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and constructive feedback. We are pleased that you appreciated Lexico’s flexible design, near-lossless performance on benchmarks, and the advantage of using a dictionary for KV cache compression. It is also encouraging that reviewers Vzmg and EhUD similarly highlighted our method's strong performance, particularly regarding its improved memory vs. performance trade-offs compared to other compression methods. We address the weaknesses and questions below.\n\n***Hardware measurements***\n\nSection E of the paper already presents a latency analysis and, hence, claiming we \"lack real hardware measurements\" is misleading. In light of the reviewer's emphasis on this point, we will move that section into the main body in the revised manuscript. We have also extended the same setup described in Section E to include varying sparsity levels for a more fine-grained analysis; these results will be incorporated into the revised edition.\n\n|||N=1024||||N=4096||||\n|-|-|-|-|-|-|-|-|-|-|\n||Full KV|s=4|s=8|s=16|s=24|s=4|s=8|s=16|s=24|\n|**Forward pass**|48.39 ms|53.90 ms|54.67 ms|55.46 ms|55.56 ms|57.24 ms|56.64 ms|57.13 ms|56.35 ms|\n|**Sparse approximation via OMP**|-|6.03 ms|10.16 ms|18.31 ms|26.57 ms|9.37 ms|15.55 ms|28.37 ms|40.58 ms|\n\nAlthough Lexico may incur higher latency at larger sparsities, it is designed to address memory-constrained scenarios where a modest latency trade-off is acceptable, and hardware or library optimizations (e.g., support for FP8 multiplications) can further narrow this gap while preserving substantial memory savings.\n\n***Lexico for CoT/reasoning tasks***\n\nWe are glad the reviewer noted the potential for Lexico in long-form reasoning tasks. To investigate this, we tested a reasoning model, DeepSeek-R1-Distill-Llama-8B, on the AIME 2024 exam. We evaluated the performance trade-off when using Lexico to compress the KV cache memory of long reasoning traces:\n\n|Compression method|KV Size|AIME 2024 (pass@1)|\n|-|-|-|\n|Full KV Cache|100%|30.0|\n|KIVI (4 bits)|31.8%|30.0|\n|Lexico ($s=24$)|28.6%|30.0|\n|KIVI (2 bits)|16.3%|23.3|\n|Lexico ($s=14$)|17.0%|26.7|\n\nAt a moderate compression level ($s=24$), Lexico retains full-precision performance (30%). When the compression becomes more aggressive, as with Lexico ($s=14$) and KIVI (2 bits), the model's score declines, though Lexico still scores higher than KIVI at similar compression levels.\n\nOne approach to improve performance is to train task-specific or reasoning-specific dictionaries. Recent reasoning models generate traces that extend well beyond the prompt, so much of the KV cache is used for these model-generated traces. Because these traces may inhabit a different subspace than the prompt KV cache, training the Lexico dictionary specifically on output generations could be a promising direction for improving the performance-memory trade-off in long-form reasoning tasks. We demonstrate this potential for task-specific dictionaries and relevant ablations in the \"Dictionary sources and adaptability across domains\" section in our response to reviewer Vzmg.", "claims_and_evidence": "The author makes the following claims:\n- Near-lossless performance: Supported by performance experiments (but only with the most safe settings)\n- Compression rates beyond 2-bits: Partially supported by theoretical KV cache size analysis (no hardware peak memory report)\n- Universality: Supported by experiment results across different datasets", "methods_and_evaluation_criteria": "Overall, make sense.\n\nComments on evaluation datasets: \n- Use Longbench V2\n- Consider long output tasks such as reasoning", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Experiment design is valid.\n\nNeed to report peak memory and throughput/latency to show efficiency.", "relation_to_broader_scientific_literature": "This work is about KV cache compression. Related to literatures like quantization, token eviction, etc.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I summarize all strengths and weaknesses here.\n\nStrengths\n- This method is intuitive and flexible, allowing fine-grained trade-offs by adjusting sparsity.\n- The performance is good; this method often achieves near-lossless performance on standard benchmarks.\n- The dictionary-based approach is an interesting alternative to quantization or token eviction, and the universality claim is a advantage.\n\nWeaknesses\n- The paper lacks real hardware measurements (latency, throughput) to show efficiency benefits.\n- Each model needs its own dictionary, potentially adding overhead in multi-model or highly specialized scenarios.\n- The authors do not benchmark on more advanced long-form tasks like MATH or AIME, where extended CoT generation can have more burden on memory.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "93JAx5SUyV", "reviewer": "Reviewer_fiw3", "summary": "LLMs that process long contexts need to store token embeddings in a KV-cache: two matrixes K and V. \nThe KV cache can grow arbitrarily large, and thus should be compressed. \nLexico compresses the KV-cache using sparse coding where K is decomposed as D * S where D is a dictionary matrix of fixed size and S a sparse matrix (and similar for V)\nLexico uses a fixed dictionary D trained offline and offers a heuristic algorithm to estimate S (computing the optimal S is NP-hard).\n\n## update after rebuttal\n\nI read the other reviewer comments and the rebuttals. Although the authors did not do some requested experiments, I think the paper has enough merit to be published with the current experimental body.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We are glad that you appreciated the novelty of Lexico, our effort in optimizations, and the overall readability of the paper. We address the remaining weaknesses and questions below.\n\n***W1: Paper organization***\n\nWe greatly appreciate the reviewer’s feedback regarding the organization of our paper. In our revision, we plan to:\n- Reorganize the Layout: We will reposition diagrams and tables so that they enhance readability, moving tables to the top of pages rather than interspersed between paragraphs. This can be done without difficulty in the case of acceptance given the additional ninth page.\n- Move Mistral results for readability: We will move the Mistral 7B results to the supplementary material, addressing concerns of redundancy while still providing experiments sufficient for our message. The original intent was to demonstrate that Lexico is not tailored to any particular model.\n- OMP Algorithm and Latency Measurements: We agree that these are important and will adjust the layout to fit them in the main text.\n\n***W2: Tradeoff between encoding time and accuracy***\n\nWe compared OMP with alternative approaches—Iterative Hard Thresholding (IHT) and Lasso—on the WikiText test set using our universal dictionary (size N=4096). While IHT and Lasso are iterative methods that can achieve better accuracy with additional iterations (trading off computation time for improved performance), OMP’s greedy nature does not allow for such tuning. In our experiments, even after increasing the number of iterations (and thus compute time) for IHT and Lasso, they still produced higher reconstruction errors than OMP across various sparsity levels. Moreover, OMP was the fastest since its complexity scales with the sparsity s, which in our case is much smaller than N.\n\n|Sparsity|OMP|IHT|Lasso|\n|-|-|-|-|\n|s=4|0.28|0.81|0.57|\n|s=8|0.11|0.57|0.43|\n|s=16|0.05|0.35|0.28|\n|s=32|0.01|0.28|0.16|\n\nIf the reviewer is aware of alternative approaches that may offer better tradeoffs, we would be eager to explore them.\n\n***Q1: Estimating the dictionary via least squares***\n\nIndeed a closed-form solution via least squares exists in each update. However, this approach proved prohibitively slow for large training sets. The solution requires forming and inverting an $N \\times N$ matrix, an operation that scales on the order of $\\mathcal{O}\\left ( N^3 \\right )$. With $N = 4096$ in our experiments, such step quickly dominates overall runtime and overshadows any advantage of jumping straight to the global minimizer.\n\n***Related work: Comparing sparse coding to product quantization***\n\nThank you for the suggestion. We will add the reference and comparison to our Related Work. Product quantization and sparse coding both use a form of \"codebook\" for vector compression. Sparse coding represents each vector as a sparse linear combination of learned dictionary atoms, while product quantization partitions vectors (e.g., the first k coordinates) and clusters each sub-vector, concatenating the nearest centroids. PQCache (https://arxiv.org/abs/2407.12820) learns its centroids from input tokens; our method trains the dictionary offline. Despite these differences, both exploit the key vectors’ clustering structure for significant compression.\n\n***L149: overcomplete definition***\n\nIt means that the dictionary has more atoms (number of vectors) than the dimensionality of the vectors. This allows multiple ways to represent the same signal, making it easier to find a good sparse representation.\n\n***Clarification on head-level compression***\n\nThe compression is performed on key vectors of size $m$ (not $d$). The \"one per layer\" phrase in the paper refers to the dictionary rather than the KV cache. For each token, we have $L \\times H$ key vectors of size $m$, while we have $L$ key dictionaries of shape $m \\times N$. Thus, all $H$ heads within a layer share the same dictionary. An analogous setup applies to the value cache and dictionary.\n\n***Figure 2 axes***\n\nIn Figure 2, each axis represents 7 tokens across all 8 heads of layer 10, yielding 7×8=56 elements (with some elements cropped for clarity). The plotted values are from key vectors for each head (with dimensionality m). In the left panel, both axes correspond to the first 7 tokens from the same sentence, whereas in the right panel each axis represents the first 7 tokens from two different sentences. The elements are sorted by similarity to highlight clustering. \n\n***Table 1 error***\n\nWe measure the relative reconstruction error (RRE) for each key or value vector as $\\text{RRE}=\\frac{\\|\\mathbf{k}-\\hat{\\mathbf{k}}\\|_2}{\\|\\mathbf{k}\\|_2}$, where $\\mathbf{k}$ is the original vector and $\\hat{\\mathbf{k}}$ its reconstruction. In Table 1, each reported value is the average RRE across 8k key/value vectors—corresponding to 1k tokens, each producing 8 head vectors—obtained from forward passes on the specified datasets. The standard deviation is computed over those 8k samples.", "claims_and_evidence": "see below", "methods_and_evaluation_criteria": "The evaluation seems fine.", "theoretical_claims": "there are none", "experimental_designs_or_analyses": "Experiments are sufficient. \nThe latency should go into the main paper IMO.", "relation_to_broader_scientific_literature": "The related work section is very short and not properly related to Lexico. \nHow does sparse coding compare to quantization methods like eg. Product Quantization?", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "S1 the first application of sparse coding to KV-cache compression\n\nS2 properly optimized: computation in the compressed domain and very cheap sparse encoder\n\nS3 easy-to-read paper \n\nW1 The paper is sometimes organized in a weird way -- see detailed comments below \n\nW2 judging from algorithm 1 (in the appendix) the OMP sparse encoding is a greedy approximation of sparse coding. Since it is an approximation to a NP-hard problem, there should be a tradeoff between encoding time and accuracy. It would be interesting to see how the same algorithm would perform with eg. a more or less large beam size of encodings", "other_comments_or_suggestions": "There are some paragraphs that have been compressed to fit in 8 pages which looks ugly. \n\nThe results for different LLMs are largely redundant, so others could be moved to appendix\n\nThe OMP algorithm and the latency numbers *are* important so should be in the main text. \n\nDetailed comments: \n\nL149 what does overcomplete mean?\n\nsec 2: There is one KV cache per head, while the exposure mentions one per layer all the time. It is unclear if the compression is performed for all heads of one layer (considering the keys and vals are of size d) or separately for each head (keys and vals of size m)\n\nFig 2: unclear what's on the x and y axis of these plots. IIUC 49 tokens from the same input sequence? Again is this for the whole layer (size d) or for one head of layer 10 (size m)\n\nL198 the expectation maximization algorithm is described in the caption of fig 3 -- move to the main text \n\nTab 1: it is unclear what the error is measured on (and what the standard deviation refers to)\n\nL216 right: the implementation uses a compressed domain multiplication, which is an interesting optimization that the authors could emphasize more \n\nL230 right: AFAICS, n_a has not been introduced (it's described in the supp material)", "questions_for_authors": "The dictionary training algorithm (caption of fig 3) is an EM that alternates between encoding the training set and estimating the dictionary. Estimating the dictionary can be done in closed form (linear least squares to minimize the reconstruction error). Why do the authors perform gradient steps instead ? Does it perform better?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dTUDqFI5MN", "reviewer": "Reviewer_EhUD", "summary": "The paper introduces Lexico, a KV cache compression method using sparse coding over universal dictionaries. By leveraging Orthogonal Matching Pursuit for sparse approximation, Lexico provides flexible compression while maintaining high performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for recognizing the novelty of applying sparse dictionary learning for KV cache compression and our extensive experimental evaluation—a strength also highlighted by reviewers Vzmg and EtKf. We address each concern below.\n\n***Q1: Task-specific dictionaries***\n\nYes, using task-specific dictionaries may improve task accuracies, but would incur the additional training cost of custom fine-tuning. While we find this a promising direction to improve performance, our motivation to employ a universal dictionary was to allow it to be used off-the-shelf for various tasks without the need for additional training. That said, we can see that one may want to explore task-specific dictionaries to further enhance the performance of Lexico in specific domains.\n\nAs MMLU-Pro Law does not have a training split, we tested task-specific dictionaries for GSM8K. Specifically, we present empirical results with the following dictionaries:\n1. **Universal dictionary:** Dictionary trained on WikiText-103.\n2. **Dictionary pre-trained on GSM8K:** Dictionary trained from scratch on the GSM8K training set.\n3. **Universal dictionary fine-tuned on GSM8K:** Dictionary trained on WikiText-103 and then fine-tuned on GSM8K.\n\n| Sparsity | KV size | Universal dictionary | Dictionary pre-trained on GSM8K | Universal dictionary finetuned on GSM8K |\n| -------- | -------- | -------- | -- | -- |\n| $s = 24$     | 36.9%     | 76.88     | 77.63 | **79.68** |\n| $s = 14$     | 26.1%     | 75.06     | 70.51 | **75.89** |\n| $s = 10$     | 22.7%     | **69.67**     | 59.59\t| 67.25 |\n\nFrom the experimental results, we observe that training a dictionary from scratch solely on GSM8K significantly underperforms compared to the universal dictionary, especially at low sparsities. This indicates overfitting to the small GSM8K training set, failing to generalize even to its test set. In contrast, fine-tuning a universal dictionary on GSM8K sometimes provides marginal improvements but adds the additional overhead of task-specific fine-tuning. Therefore, we may expect a slight increase in Lexico's performance on MMLU-Pro given a dataset with similar text distributions.\n\n\n***Q2: Table 10 computation of keys and values***\n\nApologies for the confusion. To clarify, the reported latency for the Lexico forward pass in Table 10 represents the entire process of generating one token. The row stating \"Lexico: forward pass using $q (K_\\text{csr}D_k^\\top ) ^\\top$\" should be corrected to \"Lexico: forward pass using $q (K_\\text{csr}D_k^\\top ) ^\\top$ and $V_\\text{csr}D_v^\\top$\", as the overall latency measurement indeed includes the additional compute for value vector reconstruction. We will revise the manuscript to explicitly note that the Lexico forward pass timing encompasses both the key and value reconstruction computations.\n\n***W1: Do value vectors also lie in low-rank subspaces?***\n\nYes, our findings show that value vectors also lie in a low-rank subspace. We will include an analogous figure as Figure 2 for value vectors. Below we computed the average relative reconstruction errors over 1k tokens from the WikiText test split using a universal dictionary of size $N=4096$.\n\n| sparsity | $s=4$ | $s=8$ | $s=12$ | $s=16$ |\n| -------- | -------- | -------- | -------- | -------- |\n| Keys     | 0.158     | 0.091     |0.058     |0.038     |\n| Values   | 0.410     | 0.264     |0.171     |0.110     |\n\nAlthough the sparse approximation for values is less effective than for keys, we believe that our empirical results on real-world benchmarks (LongBench, GSM8K) clearly demonstrate the effectiveness of our dictionary-based sparse representation.\n\n***W2: Dictionary training time across different sparsity levels***\n\nTraining dictionaries is cheap because they only need to be trained once and can be provided by a third-party. As we report in L203, a sparsity of s=32 and a dictionary size of N=1024 requires only 2 hours on an A100 GPU. We provide the training runtime for different sparsities and dictionary sizes for Llama-3.1-8B-Instruct below and will incorporate these results in a revised edition.\n\n\n| - | $s=4$ | $s=8$ | $s=16$ | $s=32$ |\n| -------- | -------- | -------- | -------- | -------- |\n| $N=1024$     | 37m     | 52m     | 1h 10m | 1h 59m |\n| $N=4096$     | 1h 18m     | 1h 40m     | 2h 40m | 5h 22m |", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "yes", "essential_references_not_discussed": "nothing specific", "other_strengths_and_weaknesses": "Strengths:\n1. The sparse dictionary learning for approximating KV cache compression appears new.\n2. Extensive experiments are conducted. Lexico is tested on various LLMs, including Mistral-7B, Llama-3-8B, Llama-3.1-8B-Instruct, Llama-3.2-1B/3B-Instruct, and Qwen2.5-14B-Instruct. Lexico is benchmarked against prior KV cache compression techniques including Per-Token Q, ZipCache, PyramidKV, KIVI, and SnapKV and performs consistently better \n\nWeakness:\n1. The paper argues that key vectors lie in several low-rank subspaces, as demonstrated in Figure 2. However, it does not explicitly verify whether this property also holds for value vectors. It remains unclear whether the proposed dictionary-based sparse representation is equally effective for both keys and values. \n2. A figure similar to Figure 2 for value vectors would strengthen the hypothesis by showing whether value vectors exhibit the same behavior. \nThe paper does not benchmark dictionary training time across different sparsity levels.", "other_comments_or_suggestions": "nothing in particular", "questions_for_authors": "Questions:\n1. Would task-specific dictionaries improve performance? In Figure 6 for MMLU Pro Law, Lexico does not outperform competing methods. Is this due to the input distribution being significantly different from WikiText-103 where the dictionary was trained?\n2. In Table 10, the computation only considers the key but does not include the value. Why is the computational cost for value vectors omitted in this analysis?\n3. Please see Weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes Lexico, a compression scheme of the KV cache by finding a sparse representation of each key and value vector using a pre-trained dictionary. Most of the reviewers were quite positive about the paper, given the method's significant compression rate while mostly maintaining the accuracy performance. The authors also provided several additional experimental results that corroborates the contribution of the paper. One reviewer (Vzmg) was somewhat critical about a missing reference, but given the overall contribution, the paper seems worth publishing at ICML, as also has been acknowledged by other reviewer (fiw3). So, the recommendation is Accept.
Decision: Accept (poster)