Research map / Architectures and efficiency / Quantization
Lexico: Extreme KV Cache Compression via Sparse Coding over Universal Dictionaries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Lexico compresses LLM KV caches by sparse-coding each key/value vector over a small universal dictionary (N=1024–4096 atoms) trained once on WikiText-103, using OMP and 8-bit sparse coefficients.
Problem
KV cache memory grows with context length and limits LLM serving; existing post-training methods (token eviction, 2–4 bit quantization) either fail on long-context tasks or cannot reach very low memory budgets below about 2 bits.
Approach
Approximate each key and value vector as a sparse linear combination of atoms from a small, input-agnostic, per-layer universal dictionary learned by gradient descent with OMP as the encoder; sparsity directly controls the compression ratio, and coefficients are stored in CSR form with FP8 values.
Key results
- On GSM8K, Lexico at s=14 (26.1% KV size) reaches 48.75 on Llama-3-8B vs 40.56 for KIVI-2 at 25.7% size, and 75.06 vs 67.93 on Llama-3.1-8B-Instruct.
- On LongBench at 12.4% KV size, Lexico (s=8) loses 5.6 points on Llama-3.1-8B-Instruct versus the full cache (44.68 vs 50.26 average).
- On GSM8K with Mistral-7B-Instruct-v0.3, Lexico at s=10 (22.0% KV size) scores 44.35 vs 42.91 for KIVI-2 at 25.7%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Lexico instead of KIVI-2 at similar cache size | KV cache compression · GSM8K, Llama-3-8B | Accuracy: +8.2%p | Helped |
| Use Lexico instead of KIVI-2 at similar cache size | KV cache compression · GSM8K, Llama-3.1-8B-Instruct | Accuracy: +7.1%p | Helped |
| Use Lexico instead of KIVI-4 at comparable cache size | KV cache compression · GSM8K, Llama 8B models | Accuracy: less than 3%p | Hurt |
| Use Lexico instead of KIVI at similar cache budgets | KV cache compression · LongBench, Llama-3.1-8B-Instruct | Average: 49.78 -> 49.95 | Helped |
| Early terminate OMP using a higher reconstruction-error threshold (ablation) | Lexico · LongBench average | Average: 50.26 -> 49.63; 50.26 -> 48.90; 50.26 -> 47.73; 50.26 -> 44.33 | Hurt |
| Allocate memory to sparse representation and buffer at task-specific balance (ablation) | Lexico · Qasper, MultiNews, and TREC | Task metric: 6.38 -> 17.84; 17.20 -> 22.81; 58.5 -> 65.0 | Mixed |
| Remove the full-precision recent-token buffer (ablation) | Lexico · GSM8K, Llama-3.1-8B-Instruct and Mistral-7B-Instruct-v0.3 | Accuracy: 79.61 -> 1.97; 48.60 -> 1.29 | Hurt |
| Add input-specific dictionary atoms during generation (ablation) | Lexico · GSM8K, Llama-3.1-8B-Instruct and Mistral-7B-Instruct-v0.3 | Score: +4.5%p; +2.1%p | Helped |
Surprising findings
- Removing the full-precision buffer causes GSM8K accuracy to collapse at around 25% KV size (e.g., 1.97 for Llama-3.1-8B-Instruct at s=16), showing the buffer is essential at low memory budgets.
Limitations
- Higher decoding latency due to OMP computation, which the authors flag as a limitation for latency-critical use.
- Performance drops noticeably at very high sparsity (e.g., s=4 on Llama-3.1-8B-Instruct for GSM8K), and the largest losses appear on harder tasks like Qasper.
- Adaptive dictionary extension increases KV size, limiting low-memory regimes.
Experimental setup
Datasets: WikiText-103
Benchmarks: LongBench GSM8K MMLU-Pro Engineering MMLU-Pro Law
Metrics: accuracy F1 ROUGE-L edit similarity relative reconstruction error KV cache size percentage
Baselines: KIVI-4 KIVI-2 ZipCache SnapKV PyramidKV per-token quantization Sparse Autoencoder
Builds on: KIVI OMP SnapKV PyramidKV
Closest papers by meaning
- CSR:Achieving 1 Bit Key-Value Cache via Sparse Representation (AAAI 2025 · similarity 0.89)
- EchoKV: Efficient KV Cache Compression via Similarity-Based Reconstruction (NeurIPS 2026 · similarity 0.89)
- KV-COBRA: KV Cache Compression via Co-Optimized Bit-Rank Allocation (NeurIPS 2026 · similarity 0.88)
- Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference (ICML 2024 · similarity 0.88)
- SpeCache: Speculative Key-Value Caching for Efficient Generation of LLMs (ICML 2025 · similarity 0.88)
- ZipCache: Accurate and Efficient KV Cache Quantization with Salient Token Identification (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.