# Lexico: Extreme KV Cache Compression via Sparse Coding over Universal Dictionaries

arXiv: https://arxiv.org/abs/2412.08890 · HTML: https://mlsanity.com/paper/2412.08890/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 32 of its 40 references that are in the map.
- First posted on arXiv 12 Dec 2024.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [DeepSeekMoE: Towards Ultimate Expert Specialization in Mixture-of-Experts Language Models](https://mlsanity.com/paper/2401.06066/) (2024)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Fast Transformer Decoding: One Write-Head is All You Need](https://mlsanity.com/paper/1911.02150/) (2019)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [k-Sparse Autoencoders](https://mlsanity.com/paper/1312.5663/) (2013)
- [Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving](https://mlsanity.com/paper/2407.00079/) (2024)
- [GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM](https://mlsanity.com/paper/2403.05527/) (2024)
- [You Only Cache Once: Decoder-Decoder Architectures for Language Models](https://mlsanity.com/paper/2405.05254/) (2024)
- [Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Tasks](https://mlsanity.com/paper/2407.08454/) (2024)
- [ZipCache: Accurate and Efficient KV Cache Quantization with Salient Token Identification](https://mlsanity.com/paper/2405.14256/) (2024)
- [Loki: Low-rank Keys for Efficient Sparse Attention](https://mlsanity.com/paper/2406.02542/) (2024)
- [A Simple and Effective L2 Norm-Based Strategy for KV Cache Compression](https://mlsanity.com/paper/2406.11430/) (2024)
- [ChunkAttention: Efficient Self-Attention with Prefix-Aware KV Cache and Two-Phase Partition](https://mlsanity.com/paper/2402.15220/) (2024)
- [Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference](https://mlsanity.com/paper/2402.09398/) (2024)
- [Infinite-LLM: Efficient LLM Service for Long Context with DistAttention and Distributed KVCache](https://mlsanity.com/paper/2401.02669/) (2024)
- [WKVQuant: Quantizing Weight and Key/Value Cache for Large Language Models Gains More](https://mlsanity.com/paper/2402.12065/) (2024)
- [From Denoising to Compressed Sensing](https://mlsanity.com/paper/1406.4175/) (2014)

## Built on by (most cited first, 17 of 17)

- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [Cartridges: Lightweight and general-purpose long context representations via self-study](https://mlsanity.com/paper/2506.06266/) (2025)
- [Is Random Attention Sufficient for Sequence Modeling? Disentangling Trainable Components in the Transformer](https://mlsanity.com/paper/2506.01115/) (2025)
- [KV Cache Compression for Inference Efficiency in LLMs: A Review](https://mlsanity.com/paper/2508.06297/) (2025)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [ResidualKV: Residual-Based KV Cache Compression for Efficient Long-Context Inference](https://mlsanity.com/paper/2602.08005/) (2026)
- [SQuat: Subspace-orthogonal KV Cache Quantization](https://mlsanity.com/paper/2503.24358/) (2025)
- [Training Transformers for KV Cache Compressibility](https://mlsanity.com/paper/2605.05971/) (2026)
- [CoSpaDi: Compressing LLMs via Calibration-Guided Sparse Dictionary Learning](https://mlsanity.com/paper/2509.22075/) (2025)
- [Compressed Convolutional Attention: Efficient Attention in a Compressed Latent Space](https://mlsanity.com/paper/2510.04476/) (2025)
- [Towards Fast and Effective Long Video Understanding of Multimodal Large Language Models via Adaptive Quasi-Gaussian Sampling](https://mlsanity.com/paper/2606.24187/) (2026)
- [OCTOPUS: Optimized KV Cache for Transformers via Octahedral Parametrization Under optimal Squared error quantization](https://mlsanity.com/paper/2605.21226/) (2026)
- [SWAN: Sparse Winnowed Attention for Reduced Inference Memory via Decompression-Free KV-Cache Compression](https://mlsanity.com/paper/2511.18936/) (2025)
- [Unlocking the Address Book: Dissecting the Sparse Semantic Structure of LLM Key-Value Caches via Sparse Autoencoders](https://mlsanity.com/paper/2512.10547/) (2025)
- [Linear Predictability of Attention Heads in Large Language Models](https://mlsanity.com/paper/2603.13314/) (2026)
- [LLM Inference in a Flash!](https://mlsanity.com/paper/2609.16161/) (2026)
- [OMP-MoE: Efficient Expert Pruning for Mixture-of-Experts LLMs via Orthogonal Matching Pursuit](https://mlsanity.com/paper/2609.31631/) (2026)

## Abstract (arXiv)

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.