Rank-Preserving KV Cache Compression for Large Vision-Language Models
Abstract
Advancement of Large Vision-Language Models (LVLMs) has enabled comprehension of long and high-resolution multi-modal contexts, but this capability introduces a significant Key-Value (KV) cache memory bottleneck during autoregressive generation. Existing KV cache compression methods typically rely on greedy top-k eviction driven by attention-based importance scores. However, this approach tends to redundantly sample highly similar visual tokens, thereby potentially overlooking the long-tail semantic information. To address this issue, we propose RankKV, an approach that reformulates KV cache compression as a Constrained Column Subset Selection Problem. Rather than heuristically scoring isolated tokens, our approach identifies a compact, mutually complementary subset of original physical tokens that better spans the feature space. RankKV first applies CountSketch-based randomized sketching together with observation-guided attention signals to build a candidate set, and then uses deterministic Pivoted QR factorization to remove redundancy and retain informative tokens. In addition, RankKV dynamically allocates cache budgets across attention heads according to their information capacity. Experiments on six LVLMs across seven benchmarks covering general image understanding, multimodal long-context reasoning, and video understanding show that RankKV achieves competitive performance on long-context tasks and maintains robust multimodal reasoning even under an extreme 1% token retention budget, improving generation quality while maintaining comparable efficiency.