LU-KV: KV Cache Optimization Based on Long-term Utility

💡 TL;DR: When large language models process extremely long texts and run out of memory, how do we cope? LU-KV predicts the “future value of each memory fragment” to decide what to keep and what to discard, enabling models to maintain strong comprehension under tighter memory budgets.

📚 Background: What Is KV Cache?

How Do Large Models “Read” Long Documents?

When you ask a large model to analyze a lengthy article, it needs to understand each word while remembering everything it has read before. This “memory” process relies on the attention mechanism:

Current token ←[attends to]→ All previous tokens

To accelerate computation, the model caches the “Keys” and “Values” of previous tokens — this is called the KV Cache.

Why Do We Need Eviction?

When memory runs out, we must discard part of the cache — this is KV Cache Eviction. The central question: What should we discard to minimize performance loss?

📜 A Brief History of KV Cache Eviction

🔹 First Generation: Uniform Compression (2023)

Core Idea: Treat all positions equally and discard at a fixed ratio.

Representative Works: StreamLLM, H2O
Strengths: Simple to implement, low computational overhead
Limitations: Ignores importance differences across positions and attention heads; critical information may be accidentally discarded

🔹 Second Generation: Structure-Prior-Driven (2024)

Core Idea: Use structural patterns of text and models to guide eviction.

Progress: Domain knowledge improves compression efficiency
Limitations: Fixed rules, hard to adapt to new tasks or distributional shifts

🔹 Third Generation: Dynamic Adaptation (2025–2026)

Core Idea: Dynamically adjust based on real-time statistical signals.

where \(b_{\ell,h}\) denotes the retention budget for the \(h\)-th head in layer \(\ell\).

Representative Work: Ada-KV
Strengths: Task-adaptive, online adjustment
Key Limitation: Still assumes “high current attention score = high long-term importance”

🎯 The Core Problem: This assumption does not always hold! High scores in some attention heads may be merely “transient noise,” while low-scoring heads may capture critical long-range dependencies (e.g., discourse topics, causal chains).

🔹 Fourth Generation: LU-KV — Global Optimization via Long-term Marginal Utility (2026)

Core Breakthrough: Elevates eviction decisions from “instantaneous scoring” to “long-term value prediction”.

Intuition:
Instead of asking “How important is this token right now?”, we ask “If we keep it, how much will it help future reasoning?”

🧠 LU-KV: Method Details

Step 1: Formulate KV Cache Eviction as a Global Combinatorial Optimization Problem

Allocate a fixed memory budget \(B_{\text{total}}\) across \(L \times H\) attention heads, where each head retains \(b_{\ell,h}\) tokens:

Key Challenge: This is a high-dimensional discrete combinatorial optimization problem — direct solving is computationally intractable.

Step 2: Efficient Solution via Mathematical Techniques

To solve this non-convex optimization problem, LU-KV employs convex hull relaxation + greedy rounding:

1. Convex Hull Relaxation: Converts the discrete problem into continuous optimization to quickly find a “near-optimal” allocation ratio
2. Greedy Rounding: Sequentially allocates integer budgets in descending order of marginal utility

Result: Dramatically faster solving speed with near-optimal solution quality compared to dynamic programming.

Step 3: Offline Learning + Zero Online Overhead

In practice, future decoding information is unavailable during the current decoding step. Fortunately, the information fidelity of each attention head exhibits a degree of stability across tasks. As shown in the figure below, the locally optimal compression rates are similar across different tasks!

Therefore, LU-KV adopts a “learn once, use many times” strategy:

🔧 Offline Phase (run once before deployment):

• Analyze the “compression rate vs. utility” curve for each attention head on representative data
• Build a lookup table \(\Phi\): given target compression rate \(\sigma\), output the optimal retention ratio \(\{r_{\ell,h}\}\) for each head

⚡ Online Phase (per inference, zero optimization overhead): \(\begin{aligned} 1.\ & \text{Lookup:} \quad \{r_{\ell,h}\} \leftarrow \Phi(\sigma_{\text{target}}) \\ 2.\ & \text{Budgeting:} \quad b_{\ell,h} = \lfloor (1 - r_{\ell,h}) \times T \rfloor \\ 3.\ & \text{Eviction:} \quad \text{Each head independently retains top-}b_{\ell,h}\text{ tokens} \end{aligned}\)

✅ Advantages:

• Metric-agnostic: Compatible with any instantaneous scoring method (SnapKV, H2O, etc.)
• Zero online overhead: Adds only <1ms table lookup time
• Plug-and-play: No modification to model architecture or training pipeline required

🎯 Summary

The core value of LU-KV can be summarized as:

💡 One-line Recap: LU-KV doesn’t “shortsightedly discard low-value cache” — it “retains with greater foresight” — ensuring every byte of a large model’s memory is allocated where it is most likely to generate value.

🔗 Resources

• 📄 Full Paper
• 💻 Code Repository

📄 Citation

If you find this work useful, please cite our paper:

@inproceedings{
    tang2026predicting,
    title     = {Predicting Future Utility: Global Combinatorial Optimization 
                 for Task-Agnostic {KV} Cache Eviction},
    author    = {Ziyao Tang and Pengkun Jiao and Xinhang Chen and 
                 Wei Liu and Shiyong Li and Jingjing Chen},
    booktitle = {Forty-third International Conference on Machine Learning},
    year      = {2026},
    url       = {https://openreview.net/forum?id=FQLxcBsKIb}
}