SemantiCache: Efficient KV Cache Compression via Semantic Chunking and Clustered Merging

1. Problem Statement

Large Language Models (LLMs) face significant bottlenecks during long-context autoregressive inference due to the Key-Value (KV) cache. As the input sequence grows, the KV cache expands linearly, leading to:

• Prohibitive Memory Footprint: Exhausting GPU VRAM resources.
• High Inference Latency: Slowing down the decoding stage.

Existing compression methods generally fall into two categories:

1. Eviction-based: Discard tokens deemed "less critical" (e.g., based on attention scores). This causes irreversible information loss.
2. Merging-based: Combine tokens to reduce size.

The Core Flaw: Both existing approaches typically operate on discrete tokens or arbitrary, non-semantic chunks. This ignores the natural hierarchical structure of language, leading to semantic fragmentation. Breaking apart coherent linguistic units (phrases, clauses, sentences) disrupts semantic integrity, causing irreversible information loss and degraded model performance.

2. Methodology: SemantiCache

The authors propose SemantiCache, a novel compression framework that aligns the compression process with the semantic hierarchy of human language. The framework mimics the cognitive strategy of reading: segmenting text into semantic units, distilling core meanings, and consolidating them.

The pipeline consists of three stages:

A. Semantic Chunking

Instead of fixed-size windows, the KV cache is partitioned using natural language delimiters (e.g., ., ,, ?, !, \n, \t).

• Mechanism: The sequence is split into alternating non-delimiter chunks and delimiter tokens.
• Preservation: Delimiter tokens (which often carry high attention scores) are preserved as structural anchors without modification.
• Goal: Ensure that compression happens within coherent semantic units (e.g., a sentence) rather than cutting across them.

B. Similarity Clustering (GSC Algorithm)

Within each semantic chunk, tokens are grouped based on semantic similarity to identify redundancy.

• Metric: Semantic affinity is measured using the Key vectors ($k_i$) via cosine similarity:
  $$\text{Sim}((k_i, v_i), (k_j, v_j)) = \frac{k_i \cdot k_j}{\|k_i\|_2 \|k_j\|_2}$$
• Algorithm: A Greedy Seed-Based Clustering (GSC) algorithm is used.
  • It performs a single, sequential pass through the chunk.
  • An unassigned token becomes a "seed."
  • The seed greedily absorbs all subsequent unassigned tokens whose similarity exceeds a threshold $\tau$.
  • This creates disjoint clusters of semantically related tokens.

C. Clustered Merging & Proportional Attention

The tokens within each cluster are merged into a single Semantic Core.

• Mean-Pooling: The Key and Value vectors of the cluster are averaged to create a representative core $(\hat{k}_t, \hat{v}_t)$.
• Proportional Attention Mechanism: Merging tokens dilutes their attention contribution. To counteract this, the method applies a reweighting mechanism during the attention calculation:
  $$\text{Attention}(Q, K_c, V_c) = \text{softmax}\left(\frac{QK_c^T}{\sqrt{d}} + \log s\right)V_c$$
  • Here, $s$ is a vector containing the size of each cluster ($|S_t|$).
  • Adding $\log s$ to the logits is mathematically equivalent to multiplying the attention scores by the cluster size after the softmax, ensuring the merged token's influence is proportional to the number of original tokens it represents.

3. Key Contributions

1. Identification of Semantic Fragmentation: The paper highlights that breaking linguistic coherence is the primary cause of performance degradation in existing KV cache compression methods.
2. Semantic-Aligned Framework: Introduces a three-stage pipeline (Chunking $\to$ Clustering $\to$ Merging) that respects the hierarchical nature of language, emulating human memory strategies.
3. Efficient GSC Algorithm: Proposes a lightweight, single-pass greedy clustering algorithm that efficiently groups semantically similar tokens without heavy computational overhead.
4. Proportional Attention: Solves the information dilution problem common in merging techniques by dynamically reweighting attention based on cluster size.

4. Experimental Results

The method was evaluated on Llama-3-8B and Mistral-7B across diverse benchmarks.

• Accuracy (LongBench): SemantiCache consistently outperformed state-of-the-art baselines (StreamingLLM, H2O, SnapKV, CaM, D2O) across various cache budgets (20%, 35%, 50%). It achieved the highest average scores, demonstrating that preserving semantic integrity mitigates performance decline even at high compression ratios.
• Retrieval (Needle-in-a-Haystack): On 8k and 32k context lengths, SemantiCache achieved superior retrieval accuracy compared to all baselines, proving robustness in long-context scenarios.
• Efficiency:
  • Speed: Achieved up to 2.61× speedup in Time Per Output Token (TPOT) compared to the full model.
  • Memory: Significantly reduced memory footprint (e.g., 15.94 GB vs. 24.27 GB for the full model in specific tests).
• Ablation Studies:
  • Chunking Strategy: Semantic chunking significantly outperformed fixed-size chunking (64 tokens) and global clustering (no chunking), confirming the necessity of linguistic boundaries.
  • Threshold ($\tau$): A trade-off exists between compression ratio and accuracy; higher $\tau$ values preserve more accuracy but reduce the compression ratio.

5. Significance

SemantiCache represents a paradigm shift in KV cache compression by moving from token-level or arbitrary-block operations to semantic-level operations. By acknowledging that language is a hierarchy of meaning rather than a flat stream of words, the method successfully resolves the trade-off between memory efficiency and model performance. It enables LLMs to handle long contexts with significantly lower memory costs and faster inference speeds without sacrificing the coherence required for high-quality generation.