Technical Summary: Kara - Sliding-Window KV Cache Compression for Efficient Serving of Reasoning LLMs

Problem Statement

Reasoning Large Language Models (LLMs), particularly those utilizing Chain-of-Thought (CoT) generation, produce long token sequences that accumulate massive Key-Value (KV) caches during the decoding phase. This accumulation leads to significant memory overhead, high decoding latency, and limited output throughput, especially in memory-constrained concurrent serving environments.

Existing KV cache compression methods, which aim to reduce memory footprints by selectively removing unimportant KV pairs, suffer from two primary limitations:

1. Threshold-Triggered Compression Policies: Most methods compress the cache only when it reaches a predefined threshold. In concurrent serving, as the number of active sequences approaches the gap between the threshold and the compressed length, compression is triggered frequently. This introduces computational overhead that can outweigh throughput benefits, leading to a "concurrency-throughput inversion" where increasing concurrency actually decreases overall throughput. Furthermore, repeated compression over the entire cache can eliminate all KV pairs from specific sequence blocks, exacerbating information loss.
2. Rigid Retention Granularity: Current methods typically retain either isolated KV pairs or fixed-size chunks with rigid boundaries. This fails to preserve flexible-sized chunks of semantic information located at arbitrary token positions, leading to potential degradation in reasoning performance.

Methodology: Kara

The authors propose Kara, a sliding-window KV cache compression method designed to operate exclusively on recently generated context during decoding. Kara addresses the identified limitations through three core components:

1. Sliding-Window Bidirectional Attention Scoring

Instead of compressing the entire history, Kara maintains a sliding window over the most recently generated tokens.

• Mechanism: Within this window, the method computes bidirectional attention scores. It uses the query states of all tokens in the window to score the key states of tokens in the compressible region (excluding a protected buffer at the end of the window).
• Rationale: Empirical analysis shows that bidirectional attention serves as an effective indicator of importance. Tokens that assign high attention to future tokens (and vice versa) often contain rich contextual information. By accumulating these attention weights, Kara identifies discrete candidate KV pairs that are both important and informative.
• Selection: The Top-K most important discrete KV pairs within the window are selected as retention candidates.

2. Token2Chunk Module

To overcome the rigidity of retaining only isolated pairs or fixed chunks, Kara introduces the Token2Chunk module.

• Function: This module expands the set of selected discrete KV pairs into flexible-sized contiguous chunks.
• Process: It treats every two consecutive candidate KV pairs (sorted by index) as the endpoints of a potential chunk. It then scores these candidate chunks based on their length and the importance scores of their endpoint pairs.
• Outcome: The module filters and selects chunks that maximize information preservation, allowing the retention of contiguous spans of arbitrary size at arbitrary positions, rather than being constrained by fixed boundaries.

3. KvLLM Framework and Periodic Compression

The authors adapt Kara to the PagedAttention mechanism (used in vLLM) to create KvLLM, an inference framework.

• Periodic Compression Policy: To avoid the frequent triggering issues associated with threshold-based policies, KvLLM employs a periodic compression schedule. It compresses the trailing blocks of selected sequences every fixed number of decoding steps.
• Goal: This policy controls when compression occurs, preventing the concurrency-throughput inversion effect and ensuring memory is freed efficiently to support more concurrent sequences.

Key Contributions

1. Kara Algorithm: A novel compression method that utilizes sliding-window bidirectional attention to identify candidate discrete KV pairs and a Token2Chunk module to generate flexible-sized contiguous chunks, preserving semantic information at arbitrary positions.
2. KvLLM Framework: An inference framework built upon vLLM that integrates Kara with PagedAttention and a periodic compression policy, specifically designed to improve throughput and concurrency in memory-constrained environments.
3. Empirical Validation: Comprehensive evaluations demonstrating that Kara maintains near-full-KV accuracy while retaining a small fraction of the cache, and that KvLLM significantly improves output throughput compared to baseline methods.

Experimental Results

The authors evaluated Kara and KvLLM on mathematical reasoning benchmarks (MATH-500, AIME 2024, AMC 2023) and the Needle-in-a-Haystack (NIAH) benchmark using models such as Qwen3-4B, Qwen3-14B, and Distill-Llama-8B.

• Accuracy: Kara preserves nearly 100% of the full-KV accuracy while retaining only 20% of the KV cache. On the MATH-500 dataset with Qwen3-14B, Kara maintained nearly unchanged accuracy at a 30% retention ratio, outperforming other compression methods (including AdaKV, PyramidKV, SnapKV, and ChunkKV) across various retention levels.
• Throughput: Under memory-constrained concurrent serving, KvLLM improved output throughput by an average of 12.75% compared to vanilla vLLM. In contrast, baseline methods like SnapKV showed a throughput drop (e.g., 11.15% at batch size 128) as concurrency increased due to frequent compression triggers.
• Ablation Studies: Experiments confirmed that both the bidirectional attention scoring and the Token2Chunk module are critical; removing either component resulted in measurable accuracy degradation.

Significance

The paper claims that Kara and KvLLM address critical bottlenecks in serving reasoning LLMs. By moving away from rigid, threshold-triggered compression and isolated pair retention, the proposed method effectively balances memory efficiency with reasoning capability. The significance lies in the ability to serve high-concurrency workloads with long-context reasoning requirements without sacrificing accuracy, making it a viable solution for memory-constrained deployment scenarios. The approach is training-free and designed as a plug-in compatible with existing inference frameworks.