# TreeKV: Smooth Key-Value Cache Compression with Tree Structures

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

## Key facts

- Cited by 3 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 20 of its 22 references that are in the map.
- First posted on arXiv 9 Jan 2025.

## Placed in

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

## Builds on (most cited first, 20 of 20)

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Benchmarking Large Language Models for News Summarization](https://mlsanity.com/paper/2301.13848/) (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)
- [PyramidInfer: Pyramid KV Cache Compression for High-throughput LLM Inference](https://mlsanity.com/paper/2405.12532/) (2024)
- [LM-Infinite: Zero-Shot Extreme Length Generalization for Large Language Models](https://mlsanity.com/paper/2308.16137/) (2023)
- [Transformers are Multi-State RNNs](https://mlsanity.com/paper/2401.06104/) (2024)
- [Fourier Transformer: Fast Long Range Modeling by Removing Sequence Redundancy with FFT Operator](https://mlsanity.com/paper/2305.15099/) (2023)
- [DCT-Former: Efficient Self-Attention with Discrete Cosine Transform](https://mlsanity.com/paper/2203.01178/) (2022)
- [XL3M: A Training-free Framework for LLM Length Extension Based on Segment-wise Inference](https://mlsanity.com/paper/2405.17755/) (2024)
- [Fine- and Coarse-Granularity Hybrid Self-Attention for Efficient BERT](https://mlsanity.com/paper/2203.09055/) (2022)
- [Fovea Transformer: Efficient Long-Context Modeling with Structured Fine-to-Coarse Attention](https://mlsanity.com/paper/2311.07102/) (2023)

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

- [LazyEviction: Lagged KV Eviction with Attention Pattern Observation for Efficient Long Reasoning](https://mlsanity.com/paper/2506.15969/) (2025)
- [Judge Q: Trainable Queries for Optimized Information Retention in KV Cache Eviction](https://mlsanity.com/paper/2509.10798/) (2025)
- [Adaptive Mass-Segmented KV Compression for Long-Context Reasoning](https://mlsanity.com/paper/2605.23200/) (2026)

## Abstract (arXiv)

Efficient key-value (KV) cache compression is critical for scaling transformer-based Large Language Models (LLMs) in long sequences and resource-limited settings. Existing methods evict tokens based on their positions or importance scores, but position-based strategies can miss crucial information outside predefined regions, while those relying on global importance scores resulting in strong regional biases, limiting the KV cache's overall context retention and potentially impairing the performance of LLMs on complex tasks. Our wavelet analysis reveals that as tokens approach the end of sequence, their contributions to generation gradually increase and tends to diverge more from neighboring tokens, indicating a smooth transition with increasing complexity and variability from distant to nearby context. Motivated by this observation, we propose TreeKV, an intuitive, training-free method that employs a tree structure for smooth cache compression. TreeKV maintains a fixed cache size, allowing LLMs to deliver high-quality output even in long text scenarios. Unlike most compression methods, TreeKV is applicable to both the generation and prefilling stages. TreeKV consistently surpasses all baseline models in language modeling tasks on PG19 and OpenWebText2, allowing LLMs trained with short context window to generalize to longer window with a 16x cache reduction. On the Longbench benchmark, TreeKV achieves the best performance with only 6% of the budget at optimal efficiency.