  KV-Cache compression methods generally sample a KV-Cache of effectual tokens
or quantize it into lower bits. However, these methods cannot exploit the
redundancy of the hidden dimension of KV tensors. This paper investigates a
unique hidden dimension approach called Palu, a novel KV-Cache compression
framework that utilizes low-rank projection. Palu decomposes the linear layers
into low-rank matrices, caches the smaller intermediate states, and
reconstructs the full keys and values on the fly. To improve accuracy,
compression rate, and efficiency, Palu further encompasses (1) a medium-grained
low-rank decomposition scheme, (2) an efficient rank search algorithm, (3) a
low-rank-aware quantization algorithm, and (4) matrix fusion with optimized GPU
kernels. Our extensive experiments with popular LLMs show that Palu can
compress KV-Cache by more than 91.25% while maintaining a significantly better
accuracy (up to 1.19 lower perplexity) than state-of-the-art KV-Cache
quantization methods at a similar or even higher memory usage. When compressing
KV-Cache for 50%, Palu delivers up to 1.61x end-to-end speedup for the
attention module. Our code is publicly available at
https://github.com/shadowpa0327/Palu.
