Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores

Vivek Chari, Benjamin Van DurmearXiv 2025 · arXiv · OpenReview

TL;DR

Modern LLMs struggle with the massive memory demands of long context windows. This paper introduces Compactor, a novel, training-free method that intelligently compresses the KV cache by identifying and retaining the most important tokens. Compactor achieves significant memory savings (up to 68%) while maintaining full performance, even in challenging query-agnostic scenarios.

What Problem Does This Paper Address?

Large Language Models (LLMs) are increasingly being developed to handle very long context windows, enabling them to process and generate text based on extensive information. However, a major bottleneck in deploying these models efficiently is the KV cache. This cache stores intermediate computations for each token in the context, and its size grows linearly with the context length. For long contexts, this can consume gigabytes of memory per request, significantly increasing serving costs and limiting throughput. Existing compression methods often rely on knowing the specific query being asked (query-aware), which is not always feasible in real-world scenarios and breaks down with techniques like prompt caching. Furthermore, determining how much compression can be applied without degrading performance is a non-trivial challenge.

Methods

Compactor tackles KV cache compression using a two-pronged approach:

  • Approximate Leverage Scores: This is the core of Compactor's novelty. It uses statistical leverage scores to identify "outlier" tokens – those that might not be frequently attended to but hold unique information. To make this computationally feasible, they employ an approximate leverage score computation using sketching techniques.
  • Attention-Based Scoring: In addition to leverage scores, Compactor also considers non-causal attention patterns. This captures the task-specific relevance of tokens, providing a complementary signal to the geometric outlier detection.
  • Score Blending: The leverage and attention scores are combined using a hyperparameter ($\lambda$) to create a final importance score for each token.
  • Context-Calibrated Compression: A key innovation is the ability to infer the optimal compression level for a given context without explicit performance loss. This is achieved by fitting a curve to the relationship between compression ratio and negative log-likelihood (NLL) degradation, allowing the system to dynamically determine how much to compress.
  • compactor-vllm: The authors also release an inference engine and optimized kernels to efficiently handle the sparse, non-contiguous memory access patterns introduced by compressed KV caches.

Datasets

The paper evaluates Compactor on several datasets:

  • RULER: A synthetic benchmark designed to test how well LLMs utilize long contexts. It includes tasks like needle-in-a-haystack retrieval, multi-hop tracing, and aggregation. The authors specifically use the RULER-4k variant.
  • Longbench: A benchmark comprising 21 real-world long-context tasks, including QA, summarization, few-shot learning, and code completion. The evaluation is performed on the English subset.

Key Insights and Ideas

  • Query-Agnostic is Crucial: The paper strongly emphasizes the limitations of query-aware compression for practical LLM serving, highlighting its incompatibility with prompt caching and its performance degradation when queries are unknown. Compactor's query-agnostic nature is a significant advantage.
  • Leverage Scores for Outlier Detection: The insight that statistical leverage scores can identify important but potentially under-attended tokens is key. This moves beyond simply retaining frequently attended tokens.
  • Approximation is Sufficient: The paper demonstrates that approximate leverage scores, computed efficiently via sketching, are sufficient to achieve excellent performance, making the method practical.
  • Context Matters for Compression: The idea of "context-calibrated compression" is a major contribution. It recognizes that different types of text can tolerate vastly different levels of compression, and dynamically adjusting this is crucial for maximizing efficiency without sacrificing quality.
  • Non-Causal Attention Reveals Structure: Using non-causal attention matrices reveals structured patterns that are otherwise hidden, providing valuable signals for token selection.

Key Results

  • Significant Memory Reduction: Compactor achieves substantial KV cache reduction. On Longbench, with context-calibrated compression, it reduces the KV memory burden by 68% on average while maintaining full performance. On synthetic UUID tasks, it achieves full performance with only 50% of the cache.
  • Competitive Performance: Compactor matches or exceeds the performance of full-cache models on Longbench at 50% retention. Even at 25% retention, it recovers ~95% of the full-cache score.
  • Robustness: Compactor demonstrates superior robustness across various tasks and models (Llama 3.1 and Qwen 2.5) compared to existing query-agnostic methods like SnapKV and TOVA, which degrade poorly with compression.
  • Efficiency: The overhead of Compactor's scoring mechanism is minimal, comparable to or faster than other methods like SnapKV for longer contexts, and significantly less than the cost of a single FlashAttention pass.
  • Context-Calibrated Performance: Using context-calibrated compression, Compactor achieves performance within 0.5% of uncompressed cache performance on Longbench, while retaining fewer tokens than competing methods.

Limitations and Future Work

  • Approximation Bounds: While empirically effective, the theoretical bounds for approximate leverage scores (Theorem 2) are noted to be loose in practice. The authors mention that the chosen sketching dimension $k=48$ violates these bounds but still yields good performance.
  • Numerical Stability of Eigendecomposition: The paper notes that the eigendecomposition method for computing leverage scores is less numerically stable than SVD or QR, leading to slightly reduced performance at lower retention rates. However, Compactor remains robust across these variants.
  • Future Work: The paper implicitly suggests that further exploration of different sketching matrices and optimization techniques for the compactor-vllm inference engine could yield even greater efficiency. The context-calibrated compression framework is also applicable to other compression methods, suggesting potential for broader impact.

Summary updated

Abstract

Modern Large Language Models (LLMs) are increasingly trained to support very large context windows. We present Compactor, a training-free, query-agnostic KV compression strategy that uses approximate leverage scores to determine token importance. We show that Compactor can achieve the same performance as competing methods while retaining 20% fewer tokens in both synthetic and real-world context tasks, while being more task-robust. We further introduce a procedure for context-calibrated compression: inferring the maximum compression a given context supports before significant performance loss. Using context-calibrated compression, we show that Compactor achieves full KV performance on Longbench while reducing the KV memory burden by 68%, on average. To demonstrate the efficacy and generalizability of our approach, we apply Compactor to 27 synthetic and real-world tasks from RULER and Longbench, with models from both the Qwen 2.5 and Llama 3.1 families. Finally, we release compactor-vllm, an inference engine and suite of optimized Triton kernels designed to efficiently support the sparse, non-contiguous memory access patterns inherent to compressed KV caches. This work demonstrates that Compactor offers a practical, high-performance solution for alleviating the memory bottleneck in modern LLM deployment.
BibTeX
@misc{chari2025compactor,
  author = {Vivek Chari and Benjamin Van Durme},
  title = {{Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores}},
  year = {2025},
  eprint = {2507.08143},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.08143},
}
Figure