HieraSparse: Hierarchical Semi-Structured Sparse KV Attention

Abstract

The deployment of long-context Large Language Models (LLMs) poses significant challenges due to the intense computational cost of self-attention and the substantial memory overhead of the Key-Value Cache (KV Cache). In this paper, we introduce \textit{HieraSparse}, a hierarchical KV Cache compression framework with acceleration kernels that leverage GPU sparse tensor cores to speed up semi-structured KV Cache attention for both the prefill and decode phases. With the hierarchical design, our method allows for a flexible quality-sparsity trade-off and successfully converts sparsity into efficiency. Compared to the state-of-the-art decode method that utilizes unstructured sparsity, \textit{HieraSparse} achieves $1.2\times$ KV compression ratio and $4.57\times$ attention speedup at the same sparsity level. Furthermore, we extended the semi-structured KV Cache pruning to the prefill stage, which demonstrated up to $1.85\times$ attention speedup at the highest sparsity. Lastly, we evaluate the generation quality of \textit{HieraSparse} with a simple magnitude-based pruning method, and the results show that $1.34\times$ prefill and $1.71\times$ decode attention speedup can be achieved without significant quality drop. The codebase can be found at https://github.com/psl-ntu/HieraSparse.