Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909554936119296 |
|---|---|
| author | Chen, Yifang Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao Tian, Yu |
| author_facet | Chen, Yifang Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao Tian, Yu |
| contents | The key-value (KV) cache in the tensor version of transformers presents a significant bottleneck during inference. While previous work analyzes the fundamental space complexity barriers in standard attention mechanisms [Haris and Onak, 2025], our work generalizes the space complexity barriers result to tensor attention version. Our theoretical contributions rely on a reduction from communication complexity and deduce the memory lower bound for tensor-structured attention mechanisms when $d = Ω(\log n)$. Furthermore, we introduce two types of tensor attention cache and present a trade-off between time and memory for two scenarios. Overall, our work provides a theoretical foundation for us to understand the time-memory tradeoff of KV-Cache compression in tensor attention decoding and offers more perspectives in developing more memory-efficient tensor attention Transformer architectures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_11108 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding Chen, Yifang Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao Tian, Yu Machine Learning Artificial Intelligence Computational Complexity Computation and Language The key-value (KV) cache in the tensor version of transformers presents a significant bottleneck during inference. While previous work analyzes the fundamental space complexity barriers in standard attention mechanisms [Haris and Onak, 2025], our work generalizes the space complexity barriers result to tensor attention version. Our theoretical contributions rely on a reduction from communication complexity and deduce the memory lower bound for tensor-structured attention mechanisms when $d = Ω(\log n)$. Furthermore, we introduce two types of tensor attention cache and present a trade-off between time and memory for two scenarios. Overall, our work provides a theoretical foundation for us to understand the time-memory tradeoff of KV-Cache compression in tensor attention decoding and offers more perspectives in developing more memory-efficient tensor attention Transformer architectures. |
| title | Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding |
| topic | Machine Learning Artificial Intelligence Computational Complexity Computation and Language |
| url | https://arxiv.org/abs/2503.11108 |