StructKV: Preserving the Structural Skeleton for Scalable Long-Context Inference

1. Problem Statement

As Large Language Models (LLMs) scale to support context windows exceeding one million tokens, they face a critical resource bottleneck during long-context inference. This bottleneck manifests in two distinct stages:

• Prefill Stage: The attention mechanism has $O(N^2)$ computational complexity, making the processing of long prompts computationally intensive.
• Decoding Stage: The Key-Value (KV) cache grows linearly with context length, consuming significant GPU memory and saturating memory bandwidth, which limits system throughput.

Limitations of Existing Methods:
Current compression strategies generally fall into two categories, both of which have significant flaws:

1. Decoding-Centric (e.g., StreamingLLM, SnapKV): These prune the KV cache during generation to save memory but do not reduce the quadratic computational cost of the prefill stage.
2. Prefill-Aware (e.g., FastKV, GemFilter): These attempt to accelerate prefill by pruning tokens early. However, they rely on local saliency snapshots (attention scores at a single, specific layer).
   • The Core Issue: A token might appear "dormant" (low attention) at the specific layer chosen for pruning but act as a critical global information hub across the network depth. Relying on a single-layer snapshot risks permanently discarding these structurally vital tokens, degrading performance on complex reasoning and retrieval tasks.

2. Methodology: StructKV

StructKV is a structure-aware KV cache compression framework designed to preserve the "structural skeleton" of the context. It introduces three core innovations:

A. Global In-Degree Centrality ($C_{global}$)

Instead of relying on a single-layer attention map, StructKV aggregates attention patterns across the network depth to identify a token's cumulative contribution to semantic flow.

• Mechanism: It computes a local saliency score ($S^{(l)}_j$) for each token at every layer up to a designated "Pivot Layer."
• Accumulation: It recursively sums these scores with a layer-wise decay factor ($\lambda$) to create a global centrality score:
  $$C_j = \sum_{l=0}^{L^*} \lambda^{(L^*-l)} \cdot S^{(l)}_j$$
• Benefit: Tokens that act as information hubs across multiple early layers accumulate high scores, ensuring they are preserved even if they appear locally dormant at the pruning layer.

B. Dynamic Pivot Detection

Rather than using a fixed hyperparameter (e.g., always pruning at Layer 15), StructKV employs an online mechanism to adaptively locate the optimal layer ($L^*$) for compression.

• Metrics: It monitors three information-theoretic metrics per layer: Attention Entropy (uncertainty), Sparsity (concentration of attention), and Variance (distinguishability).
• Phase Transition: The algorithm detects a "phase transition" point where attention shifts from broad exploration (high entropy) to focused extraction (high sparsity/variance).
• Adaptability: This allows the model to delay pruning for deeper architectures (e.g., moving from Layer 12 in a 7B model to Layer 28 in a 32B model) to ensure the structural skeleton is fully formed before compression.

C. Structural Propagation & Decoupling

StructKV decouples the computational budget (prefill speed) from the memory storage budget (decoding cache).

• Propagation: At the detected Pivot Layer ($L^*$), the model propagates only the top-$K$ tokens with the highest Global In-Degree Centrality to subsequent layers. This accelerates deep-layer computation.
• Decoupling:
  • Computation ($R_{struct}$): Uses a higher retention rate (e.g., 60%) to maintain a rich "structural skeleton" for accurate reasoning.
  • Memory ($R_{KV}$): Uses a lower retention rate (e.g., 10%) for the KV cache stored during decoding to save memory.
• Result: This allows the model to perform high-fidelity prefill computation while maintaining a lightweight memory footprint for generation.

3. Key Contributions

1. Global In-Degree Centrality: A novel metric that aggregates attention across layers to identify tokens with long-term structural importance, solving the "myopic" problem of single-layer pruning.
2. Dynamic Pivot Detection: An adaptive algorithm that automatically identifies the optimal compression layer based on attention entropy and sparsity gradients, eliminating the need for manual, model-specific hyperparameter tuning.
3. Decoupled Budget Strategy: A framework that separates the sequence length used for computation from the sequence length stored in memory, resolving the trade-off between prefill speed and generation quality.
4. Block-Level Aggregation: Implementation support for block-based memory management (e.g., vLLM), preserving contiguous structural anchors (like function definitions) better than fragmented token eviction.

4. Experimental Results

The authors evaluated StructKV on LongBench (comprehensive understanding) and RULER (needle-in-a-haystack retrieval) using models like LLaMA-3.1-8B, Mistral-8B, and Qwen-2.5 (7B/14B/32B).

• Accuracy Retention:
  • On LongBench with a strict 10% KV budget, StructKV achieved an average score of 48.61, outperforming the state-of-the-art FastKV (47.59) and significantly beating GemFilter (40.40).
  • With a relaxed 20% KV budget, StructKV matched full-context performance (48.97 vs. 49.33) while reducing prefill computation by 40%.
• Extreme Context Robustness (RULER):
  • At 128K context length, FastKV's performance dropped sharply (68.2 vs. Full Context 76.3) due to the loss of "dormant" tokens.
  • StructKV maintained a score of 73.6, demonstrating superior resilience by preserving the structural skeleton via global accumulation.
• Efficiency:
  • StructKV achieved a 1.87x speedup in prefill latency compared to full-context processing on a 32K context.
  • The overhead introduced by the dynamic detector and score accumulation was negligible (<2.5% of total latency).
• Adaptability: The Dynamic Pivot Detector successfully adjusted the pruning layer for different model depths (e.g., shifting from Layer 12 to Layer 28 as model size increased), proving its generalizability.

5. Significance

StructKV represents a paradigm shift in long-context inference optimization. By moving from local saliency to global structural importance, it addresses the fundamental fragility of existing pruning methods.

• Solves the Trilemma: It effectively balances the three competing goals of Prefill Speed, Decoding Latency/Memory, and Long-Context Accuracy, which previous methods could not achieve simultaneously.
• Scalability: The dynamic nature of the method makes it suitable for rapidly evolving LLM architectures without requiring costly manual re-tuning.
• Practical Impact: It enables the deployment of LLMs with million-token contexts on limited hardware resources without sacrificing the model's reasoning capabilities or retrieval accuracy.