Technical Summary: NestedKV

Problem Statement

Long-context language models face a critical bottleneck in practical deployment: the Key-Value (KV) cache grows linearly with context length and batch size, dominating inference memory costs even when model weights are fixed. While training-free KV cache compression methods exist, they typically rely on a single "anchor" signal to rank token importance—such as past attention mass, recency, layer-wise allocation, or key distinctiveness.

The paper argues that these single-view approaches become brittle under aggressive compression or long contexts. For instance, attention-based methods often concentrate mass on the prompt tail or "attention sinks," causing them to evict answer-bearing tokens that reside in low-attention regions. Similarly, a global mean may miss local episodic shifts, while a local rule may overfit repetitive blocks. The core problem is that useful context can be globally distinctive, locally episodic, or immediately relevant, requiring a more nuanced, multi-scale approach to memory maintenance.

Methodology: NestedKV

NestedKV is a training-free, key-only KV cache compression method inspired by the Continuum Memory System from Nested Learning. Instead of ranking tokens by a single metric, it treats eviction as bounded test-time memory maintenance using a three-tiered architecture:

1. Continuum Memory State (Inner Learners)

NestedKV maintains three distinct memory anchors over the cached key stream for every token $i$:

• Stable Memory ($\mu_s$): A global mean of all normalized keys, capturing document-level regularities.
• Episodic Memory ($\mu_e(i)$): A local block mean (block size $b \approx N/32$), capturing passage-level or turn-level structure.
• Current Memory ($\mu_c(i)$): A sliding-window mean (window size $W=64$), capturing short-range continuity and immediate redundancy.

For each token, the method computes cosine anomaly scores against these three scales: $a_k(i) = -\cos(\hat{k}_i, \mu_k)$. A high score indicates the token is anomalous (distinctive) relative to that specific memory scale.

2. Outer Learner: Adaptive Blending and Surprise Routing

The method combines these three anomaly rankings through a training-free outer learner that operates on two axes:

• Head-Adaptive Blend: Different attention heads specialize in different temporal roles. NestedKV measures the discriminative power of each scale per head (the gap between top and bottom tokens) and uses a softmax with a fixed log-prior to weight the scales. This creates a blended score $a_{blend}(i)$.
• Surprise-Gated Routing: The method calculates "compression-induced surprise" as the standard deviation of the three anomaly scores.
  • Low Surprise: The three scales agree; the token retains the blended score.
  • High Surprise: The scales disagree (e.g., a token is globally typical but locally anomalous). In this case, the method routes the score to the strongest individual memory ($a_{win}(i) = \max(a_s, a_e, a_c)$) to avoid averaging out critical signals.

3. Head-Wise Memory Allocation

Rather than allocating memory uniformly across heads, NestedKV implements a competitive budgeting mechanism. It selects the globally highest-residual token-head pairs across the layer, subject to a per-head safeguard (ensuring every head retains a minimum state). This distributes the layer budget according to where the continuum memory signals are most surprising.

Key Contributions

1. Reframing Compression: The authors reframe training-free KV compression as continuum-memory anomaly detection over the key stream, providing a Nested Learning interpretation of token eviction as bounded test-time memory maintenance.
2. NestedKV Algorithm: The introduction of a method using three time-scale key statistics (stable, episodic, current) as inner learners, combined via a training-free outer learner that adapts per head and routes based on compression-induced surprise.
3. Empirical Validation: Extensive evaluation across six benchmarks (RULER, LongBench, LooGLE, LongBench-E, InfiniteBench, MMLU-Pro) on Qwen3 and Llama-3.2 models, demonstrating that multi-time-scale scoring is particularly valuable under aggressive compression.

Experimental Results

The evaluation focuses on Qwen3-4B and Llama-3.2-3B-Instruct models across various context lengths (4k–32k) and eviction ratios ($r \in \{0.25, 0.50, 0.75, 0.85, 0.95\}$).

• Aggressive Compression Performance: NestedKV shows its strongest advantage when the retained cache is small. On RULER (4k context, $r=0.75$), NestedKV improves over the strong baseline KeyDiff by 19.10 points on Qwen3-4B.
• LongBench: At $r=0.75$, NestedKV achieves an average score of 50.06 on Qwen3-4B, significantly outperforming KeyDiff (30.77). At extreme compression ($r=0.95$), NestedKV retains 37.32 points, whereas KeyDiff drops to 17.55.
• Robustness: The method maintains near-full-KV performance on short-context knowledge benchmarks (MMLU-Pro) even at high compression ratios, indicating it does not compromise short-prompt capability.
• Ablation Studies: Removing either the continuum memory state or the adaptive head-wise allocation causes significant performance drops (approx. 8 points each). Removing both causes a drop of ~19 points, suggesting the components are synergistic.
• Efficiency: The method adds minimal overhead, with prefill latency within 0.5% of single-anchor baselines like KeyDiff, while decoding latency and peak memory remain nearly identical to other compressed methods.

Significance and Claims

The paper claims that NestedKV addresses the structural insufficiency of single-anchor compression methods. By moving the compression score out of attention space and into the key stream using a continuum-memory view, the method successfully retains tokens that are distinctive at global, local, or immediate scales.

The authors emphasize that the primary benefit of NestedKV is not necessarily peak performance at low compression ratios, but rather graceful degradation as the memory budget shrinks. The multi-time-scale scoring allows the model to preserve diverse supporting tokens that single-signal methods (which rely on attention or global distinctiveness alone) would erroneously evict. The method requires no training, no modification to the underlying LLM, and is compatible with optimized attention kernels.

Limitations noted by the authors:

• The assumption that redundancy with respect to stable/episodic/current statistics is a useful signal may be weaker for code-completion tasks where local repetition is the pattern to be preserved.
• The method is limited to frozen open-weight models and does not learn task-specific parameters or modify decoding kernels.