# NestedKV: Nested Memory Routing for Long-Context KV Cache Compression

> NestedKV reframes training-free KV cache compression as multi-time-scale anomaly detection, outperforming single-anchor methods by up to 19 points under aggressive compression.

- **Source:** [arXiv](https://arxiv.org/abs/2605.26678)
- **Published:** 2026-08-29
- **Permalink:** https://picx.dev/p/czN6It
- **Whiteboard:** https://picx.dev/p/czN6It/image

## Summary

## Summary (Overview)

- **NestedKV** is a training-free KV cache compression method for long-context LLMs that reframes cache eviction as **continuum-memory anomaly detection** over the key stream, inspired by the Continuum Memory System in Nested Learning theory.
- The method maintains **three time-scale key anchors** — stable (global mean), episodic (block mean), and current (sliding-window mean) — and scores each token by its **cosine anomaly** against each scale, retaining tokens anomalous against *any* scale.
- A **training-free outer learner** combines the per-scale rankings via two mechanisms: (1) **head-adaptive softmax blending** that up-weights the most discriminative scale per attention head, and (2) **surprise-gated routing** that switches to the strongest individual memory when the three scales disagree.
- The score is **key-only**, pairs with **adaptive per-head memory allocation**, and requires **no training or LLM modification** — remaining compatible with optimized attention kernels.
- Across RULER (4k–32k), LooGLE, LongBench, LongBench-E, InfiniteBench, and MMLU-Pro on Qwen3 and Llama-3.2 models, NestedKV is **strongest under aggressive compression** (e.g., +19.10 points over KeyDiff on RULER at r=0.75 on Qwen3-4B) while preserving short-prompt capability.

---

## Introduction and Theoretical Foundation

### Background and Motivation

Long-context language models face a fundamental bottleneck: the **key-value (KV) cache** grows linearly with context length and batch size, dominating inference cost even when model weights are fixed. This motivates a growing line of **training-free KV cache compression** research aimed at reducing cache memory without fine-tuning.

### The Single-Anchor Limitation

Most existing methods choose **one importance signal** for token ranking:

| Method | Anchor Signal |
|--------|--------------|
| H2O / attention-based (Liu et al., 2023) | Past attention mass (persistence-of-importance) |
| StreamingLLM (Xiao et al., 2024) | Recency + attention sinks |
| SnapKV (Li et al., 2024b) | Observation window near prompt end |
| PyramidKV (Cai et al., 2024) | Layer-wise cache budgets |
| KeyDiff (Park et al., 2026) | Geometric distinctiveness of keys from mean direction |

The authors argue this is brittle: *"A token may be important because it is globally unusual in the document, because it marks a local topic shift inside one segment, or because it is part of the recent stream that will shape immediate generation."* Under aggressive compression, these notions diverge — a global mean can miss local episodes; a local rule can overfit repetitive blocks; a recent-window rule can discard earlier retrieval evidence.

### Theoretical Basis: Nested Learning and Continuum Memory

The method is grounded in the **Nested Learning** perspective, which posits that models maintain compressed context flows through **nested memory systems** with a self-modifying update rule (Behrouz et al., 2026a). NestedKV instantiates this at test time:

- **Inner learners**: Three time-scale memory anchors (stable, episodic, current) each produce an independent token ranking.
- **Outer learner**: A training-free combination rule that adapts per head and per token, instantiating the "self-modifying compressor motif" with no trainable parameters.

---

## Methodology

### 2.1 KV Compression as Nested Memory Maintenance

For layer $\ell$ and KV head $h$, the full prefill memory is:

$$
M_{\ell,h} = (K_{\ell,h}, V_{\ell,h}) \tag{1}
$$

NestedKV constructs a compressed memory:

$$
M_{\ell,h}^{B_h} = \mathcal{C}_\phi(K_{\ell,h}, V_{\ell,h}; B_h) \tag{2}
$$

where $B_h$ is the head-specific memory budget and $\phi$ is the fixed NestedKV policy (no learned parameters). All scores use **normalized keys** $\hat{k}_i = k_i / \lVert k_i \rVert_2$, focusing on directional structure in key space.

### 2.2 Continuum Memory State

For every cached token $i$, NestedKV maintains three memory anchors:

**Stable memory** (document-level mean):
$$
\mu_s = \frac{1}{N} \sum_{j=1}^{N} \hat{k}_j \tag{5}
$$

**Episodic memory** (block mean, block size $b = \operatorname{clip}(\lfloor N/32 \rfloor, 128, 256)$):
$$
\mu_e(i) = \frac{1}{|B(i)|} \sum_{j \in B(i)} \hat{k}_j \tag{7}
$$

**Current memory** (sliding-window mean, window size $W = 64$):
$$
\mu_c(i) = \frac{1}{i - \ell_i + 1} \sum_{j=\ell_i}^{i} \hat{k}_j, \quad \ell_i = \max(1, i - W + 1) \tag{8}
$$

### 2.3 Per-Scale Anomaly Scores

Each token receives three anomaly scores (negative cosine similarity):

$$
\begin{aligned}
& a_s(i) = -\cos(\hat{k}_i, \mu_s), \\
& a_e(i) = -\cos(\hat{k}_i, \mu_e(i)), \\
& a_c(i) = -\cos(\hat{k}_i, \mu_c(i))
\end{aligned} \tag{9}
$$

**Interpretation**: Low $a_k(i)$ means token $i$ is typical w.r.t. scale $k$ (redundant); high $a_k(i)$ means the token carries information not explained by that scale. Each score is **min-max normalized per head** ($\tilde{a}_s, \tilde{a}_e, \tilde{a}_c$), and the first $n_{\text{sink}} = 4$ positions are pinned (assigned large values) for attention stability.

### 2.4 Outer Learner: Head-Adaptive Blend with Surprise Routing

**Head-adaptive blend weights**: For each head, measure how discriminative each scale is:

$$
\Delta_k = \overline{\mathrm{top}_p(\tilde{a}_k)} - \overline{\mathrm{bot}_p(\tilde{a}_k)}, \quad p = 10\% \tag{10}
$$

Blend weights via softmax over reliability gaps anchored by a fixed log-prior:

$$
w_k = \frac{\exp(\log w_k^0 + \beta \Delta_k)}{\sum_j \exp(\log w_j^0 + \beta \Delta_j)} \tag{11}
$$

with prior $(w_s^0, w_e^0, w_c^0) = (0.4, 0.4, 0.2)$ and fixed temperature $\beta$. The blended score:

$$
a_{\text{blend}}(i) = w_s \tilde{a}_s(i) + w_e \tilde{a}_e(i) + w_c \tilde{a}_c(i) \tag{12}
$$

**Compression-induced surprise** (cross-scale disagreement):

$$
s(i) = \operatorname{std}\left(\tilde{a}_s(i), \tilde{a}_e(i), \tilde{a}_c(i)\right) \tag{13}
$$

**Winner score** (strongest individual memory):

$$
a_{\text{win}}(i) = \max\left(\tilde{a}_s(i), \tilde{a}_e(i), \tilde{a}_c(i)\right) \tag{14}
$$

**Routed score** (sigmoid gate over surprise):

$$
\begin{aligned}
& \alpha(i) = \sigma\left(\kappa (s(i) - \tau)\right), \\
& a^\star(i) = (1 - \alpha(i)) \cdot a_{\text{blend}}(i) + \alpha(i) \cdot a_{\text{win}}(i)
\end{aligned} \tag{15}
$$

with fixed gate threshold $\tau$ and sharpness $\kappa$.

### 2.5 Compression Operator

$$
\mathcal{C}_\phi(K, V; B) = \{(k_i, v_i) : i \in \mathrm{TopB}(a^\star_{1:N})\} \tag{16}
$$

Keeps positions anomalous against **at least one** memory scale.

### 2.6 Head-Wise Memory Competition

Instead of uniform per-head budgets, NestedKV selects the globally highest-residual (head, token) pairs:

$$
\mathcal{P}_\ell = \mathrm{TopB}_{B_\ell}\{(h,i) : a_{h,i}\} \tag{17}
$$

with a small per-head safeguard, inducing head-specific budgets:

$$
B_h = |\{i : (h,i) \in \mathcal{P}_\ell\}|, \quad \sum_h B_h = B_\ell \tag{18}
$$

---

## Empirical Validation / Results

### Experimental Setup

- **Models**: Qwen3-0.6B/4B/8B/32B, Llama-3.2-1B/3B-Instruct
- **Benchmarks**: RULER (13 tasks, 4k–32k contexts), LongBench, LooGLE, LongBench-E, InfiniteBench, MMLU-Pro
- **Compression ratios**: $r \in \{0.25, 0.50, 0.75\}$ (fraction of KV entries evicted)
- **Baselines**: StreamingLLM, SnapKV, Expected Attention, PyramidKV, KeyDiff, Full KV (upper bound)

### RULER Results (Table 1, Qwen3-4B)

| Context | Method | r=0.25 | r=0.50 | r=0.75 |
|---------|--------|--------|--------|--------|
| 4k | KeyDiff | 89.12 | 75.06 | 60.22 |
| 4k | **NestedKV** | **93.60** | **90.40** | **79.32** |
| 8k | KeyDiff | 82.72 | 74.36 | 62.53 |
| 8k | **NestedKV** | **91.11** | **89.35** | **78.52** |
| 16k | KeyDiff | 76.84 | 72.51 | 62.20 |
| 16k | **NestedKV** | **90.44** | **88.36** | **79.89** |
| 32k | KeyDiff | 68.62 | 63.38 | 55.77 |
| 32k | **NestedKV** | **85.25** | **82.61** | **73.11** |

**Key finding**: At r=0.75, NestedKV improves over KeyDiff by **+19.10** (4k), **+15.99** (8k), and **+17.69** (16k) on Qwen3-4B.

### LongBench Results (Figure 5, Qwen3-4B)

- At r=0.75: NestedKV = **50.06** vs. KeyDiff = 30.77
- At r=0.85: NestedKV = **45.38** vs. SnapKV = 40.61
- At r=0.95: NestedKV = **37.32** vs. KeyDiff = 17.55

### Qwen3-32B Scaling (Table 2)

NestedKV is highest-scoring in all six 4k/8k configurations: e.g., **95.10** vs. KeyDiff's 90.23 at 4k/r=0.25, and **76.71** vs. 71.17 at 8k/r=0.75.

### Short-Context Preservation (MMLU-Pro)

- At r=0.25: NestedKV = **36.5** vs. Full KV = 36.3 (essentially lossless)
- At r=0.75: NestedKV = **33.1** vs. SnapKV = 22.0, PyramidKV = 21.4

### Ablation Study (Table 3, Qwen3-4B RULER 4k, r=0.75)

| Variant | Score | Δ |
|---------|-------|---|
| NestedKV (full) | 79.32 | — |
| w/o adaptive (uniform budget) | 70.91 | -8.41 |
| w/o continuum (single anchor) | 71.33 | -7.99 |
| w/o both | 60.22 | **-19.10** |

The combined removal exceeds the sum of individual deltas (16.40), showing the two components are **coupled** by the discrete top-k decision.

### Surprise Gate Ablation (Table 4)

| Variant | Score |
|---------|-------|
| NestedKV (Surprise Gate) | 79.32 |
| Only average (blend only) | 76.25 |
| Only max (winner only) | 75.54 |

### Efficiency (Table 5, Qwen3-4B, 32k context, r=0.75)

| Method | KV | Prefill (s) | Decode (ms/tok) | Peak (GB) |
|--------|-----|-------------|-----------------|-----------|
| Full KV | 100% | 6.28 | 38.90 | 21.48 |
| KeyDiff | 25% | 6.34 | 31.46 | 18.11 |
| SnapKV | 25% | 6.50 | 31.49 | 18.11 |
| **NestedKV** | 25% | **6.36** | **31.47** | **18.11** |

NestedKV's three-time-scale scoring adds only ~0.5% prefill overhead over single-anchor KeyDiff, with identical decode latency and peak memory.

---

## Theoretical and Practical Implications

### Theoretical Implications

1. **Reframing KV compression**: The paper reframes training-free KV cache compression as **continuum-memory anomaly detection** over the key stream, giving token eviction a Nested Learning interpretation as bounded test-time memory maintenance.

2. **Multi-scale vs. single-anchor scoring**: The results demonstrate that **no single importance signal** (attention, recency, distinctiveness) is sufficient under aggressive compression — the three scales capture complementary information, and their combination degrades more gracefully.

3. **Head specialization**: The head-adaptive blending reveals that different attention heads specialize in different temporal roles (stable vs. episodic vs. current), validating the need for per-head adaptation rather than uniform mixing.

4. **Surprise as a routing signal**: Cross-scale disagreement (surprise) is a useful meta-signal for deciding whether to trust the blended average or the strongest individual memory — a novel mechanism not present in prior work.

### Practical Implications

1. **Deployment-ready**: NestedKV is training-free, key-only (compatible with optimized attention kernels like FlashAttention), and requires no LLM modification.

2. **Graceful degradation**: The method's main benefit is **robustness under aggressive compression** (r=0.75–0.95), which is precisely the regime where memory savings matter most for long-context deployment.

3. **Scalability**: Gains hold across model families (Qwen3, Llama-3.2) and scales (0.6B to 32B), suggesting the approach generalizes well.

4. **Minimal overhead**: The additional prefill cost is negligible (~0.5% over KeyDiff), making it practical for real-world serving.

---

## Conclusion

### Main Takeaways

NestedKV treats KV cache compression as **bounded test-time memory maintenance** using a continuum of three time-scale key statistics (stable, episodic, current) as inner learners, combined by a training-free outer learner with head-adaptive blending and surprise-gated routing. The method is:

- **Strongest under aggressive compression**: The multi-time-scale scoring degrades more gracefully when the retained cache must be small.
- **Robust across benchmarks and models**: Consistently best or near-best on RULER, LongBench, LooGLE, and MMLU-Pro across Qwen3 and Llama-3.2 families.
- **Training-free and efficient**: No learned parameters, minimal prefill overhead, compatible with optimized kernels.

### Limitations and Future Directions

1. **Assumption of redundancy**: The method assumes redundancy w.r.t. key statistics is a useful eviction signal — this is weaker for **code-completion tasks** where local repetition is the pattern to preserve. Future variants should adapt continuum weights to input structure.

2. **Prefill-only, query-agnostic**: NestedKV does not recompute scores during decoding or use query information. **Decoding-time recompression** and **query-aware variants** remain open future work.

3. **Frozen models only**: The method does not explore learned or fine-tuned variants that could further improve difficult settings.

4. **Code-like local regularity**: The paper suggests reducing episodic/current redundancy penalties when the prompt exhibits code-like structure, pointing to a need for **input-adaptive continuum weights**.

---

_Markdown view of https://picx.dev/p/czN6It, served by PicX — AI-generated visual whiteboard summaries of research papers._