Skip to content

CentralKV: Compressing Long-Context LLMs via Attention-Graph Centrality

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/xxx
Area: Model Compression
Keywords: KV Cache Compression, Dynamic Sparse Graph, Maximum Influence Path, Structural Bridge Tokens, Long-Context Reasoning

TL;DR

CentralKV is a training-free KV cache compression framework that casts attention into a dynamic sparse causal graph and deploys an online Stream-Influence centrality algorithm using a non-linear max operator, accurately retaining low-frequency but structurally pivotal bridge tokens to preserve multi-step reasoning chains under severe memory budgets.

Background & Motivation

As large language models transition toward complex reasoning engines, handling extensive contexts has become a core prerequisite. However, autoregressive decoding incurs a linear explosion in Key-Value (KV) cache memory proportional to sequence length. For example, maintaining KV states for a 128k context on a 7B model consumes more than 100GB of GPU memory, posing an intractable memory wall for deployment on commodity hardware. Existing eviction heuristics primarily rely on first-order frequency statistics: H2O prioritizes accumulated attention mass (Heavy Hitters), while StreamingLLM retains initial attention sinks alongside a sliding local window. While effective for simple single-span retrieval, these frequency-based heuristics break down catastrophically on complex multi-step reasoning tasks.

In extended multi-step logical flows, key connectors (such as conditional variables in programming code or intermediate entities in multi-hop question answering) naturally act as "Structural Bridges". These bridge tokens typically receive low or moderate local attention mass—failing the heavy-hitter threshold—yet they sit at central topological intersections connecting the premise to the ultimate conclusion. Once a greedy frequency-based eviction policy discards these bridge tokens, the underlying chain of thought is severed, causing drastic degradation on tasks characterized by long dependency paths.

While recent graph-based strategies like GraphKV explore topological structures, they compute auxiliary cosine similarities across key vectors and propagate decay signals over static graphs, introducing significant computational overhead and memory access penalties during streaming decoding. Core idea: transform the ephemeral attention matrix directly into a dynamic sparse causal DAG during the forward pass, using a non-linear Stream-Influence centrality algorithm to track the maximum influence path and preserve critical structural bridge tokens with negligible kernel-level overhead.

Method

Overall Architecture

CentralKV is an online, training-free KV cache eviction framework designed for autoregressive decoding. Its execution pipeline comprises four integrated stages: directly extracting a dynamic sparse causal graph from attention weights during the forward pass; performing two-stage kernel-fused Top-\(k\) edge selection to avoid memory materialization; updating token centrality online via the constant-complexity Stream-Influence algorithm; and evicting nodes with the lowest centrality while protecting the initial system prompt and recent sliding window.

The end-to-end processing pipeline is illustrated below:

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Query Token and Active KV Cache"] --> B["Kernel-Fused Dynamic Sparse Graph Construction<br/>Reusing attention weights with two-stage Top-k selection"]
    B --> C["Stream-Influence Maximum Influence Path Centrality Update<br/>Max-recursive propagation and temporal decay"]
    C --> D["Implicit Decay and Periodic Renormalization<br/>Scale-invariant scoring without dense memory writes"]
    D --> E["Centrality-Prioritized Cache Eviction<br/>Protecting system prompts and local sliding window"]
    E --> F["Output Compact KV Cache for Next Decoding Step"]

Key Designs

1. Kernel-Fused Dynamic Sparse Graph Construction: eliminating auxiliary similarity computation overhead

A major bottleneck of prior graph-based compression lies in executing separate cosine similarity calculations across cached key vectors, which severely slows down streaming decoding. CentralKV recognizes that modern Transformer forward attention already transiently generates functional causal dependencies in on-chip SRAM. Thus, CentralKV models token interactions as a dynamic directed acyclic graph (DAG) and retains only the top-\(k\) incoming edges with the highest attention weights for each query token \(x_i\):

\[E_t = \{(i, j) \mid j \in \text{Top-K}_{j' < i}(A_{ij})\}\]

To extract this sparse topology within high-performance attention implementations (such as FlashAttention-2) without materializing full attention matrices into High-Bandwidth Memory (HBM), the method adopts a two-stage fused kernel: Stage 1 maintains a register-array local priority queue of size \(k\) inside each thread block's Softmax loop and performs warp-level reductions via shuffle primitives (__shfl_down_sync), entirely avoiding global atomic contention; Stage 2 launches a tiny standalone reduction kernel immediately afterward to merge block-level candidates into the global top-\(k\) indices. Because autoregressive decoding is strictly memory-bandwidth bound, the added comparison arithmetic is completely hidden behind high-latency HBM memory transactions.

2. Stream-Influence Maximum Influence Path Centrality Update: capturing critical reasoning bridges in causal graphs

Standard spectral graph metrics like PageRank rely on random walks and linear summation, which suffer from a fundamental failure mode in causal attention graphs: summing over numerous weak, irrelevant attention heads dilutes the fragile signal of a single decisive dependency. CentralKV formulates its centrality metric as a Maximum Influence Path (MIP) objective on a time-varying DAG, replacing additive accumulation with a non-linear max operator.

When a new token arrives at time step \(t\), its source potential reflects the continuation of the strongest antecedent reasoning chain:

\[\hat{S}(t) = 1 + \lambda \cdot \max_{v \in \text{Neighbors}(t)} S^{(v)}(t-1)\]

where \(\lambda\) governs the recursive propagation strength. This potential is then injected backward into active predecessor nodes weighted by attention scores, combined with a temporal forgetting factor \(\gamma\):

\[S^{(j)}(t) = \gamma S^{(j)}(t-1) + A_{tj} \hat{S}(t)\]

The non-linear max operator acts as an effective hard filter: it propagates topological importance exclusively along the strongest causal reasoning path. Consequently, even if a structural bridge token accumulates modest overall attention mass, its role in mediating critical reasoning flows to the current token yields high centrality, protecting it from premature eviction.

3. Implicit Decay and Periodic Renormalization: achieving constant-time online maintenance without lock contention

Naively updating the scores of all cached tokens via temporal decay at every decoding step would trigger \(O(B)\) memory writes, crippling generation throughput. CentralKV eliminates this overhead via an implicit decay formulation. By tracking scale-invariant scores \(\tilde{S}[j] = S^{(j)}/\gamma^t\), temporal decay becomes an invariant baseline, requiring additive updates solely for active neighbors identified in the sparse top-\(k\) edge set:

\[\tilde{S}[j] \leftarrow \tilde{S}[j] + \frac{A_{tj} \hat{S}(t)}{\gamma^t}\]

This confines the per-step score update complexity strictly to \(O(k)\). For long sequences (\(L > 4\text{k}\)), the denominator \(\gamma^t\) would otherwise exceed the floating-point dynamic range of BF16. CentralKV incorporates periodic renormalization: every \(N = 1024\) steps, it explicitly multiplies all cached scores by \(\gamma^N\) and resets the time exponent, incurring a negligible amortized cost of \(O(B/N)\). The authors prove recursively that with pinned attention sinks and sliding local windows excluded from eviction, the structural sparsity of middle-context attention guarantees the contraction condition \(\gamma + \alpha \lambda < 1\), ensuring absolute numerical stability.

A Worked Example

Consider a multi-hop scenario from 2WikiMultihopQA: the early context states "[Entity A] (born 1980) directed the film [Movie X]...", followed by extensive background paragraphs, and finally poses the query "Who is the director of [Movie X]?". Under standard heavy-hitter eviction (e.g., H2O), the token representing "[Movie X]" receives moderate local attention but insufficient global accumulation, causing it to be evicted when the cache reaches capacity and severing the link to "[Entity A]". In CentralKV, when the query attends to "[Movie X]", the fused kernel registers it in the top-\(k\) edge set. Stream-Influence's max operator traces the causal dependency connecting the query through "[Movie X]" back to "[Entity A]", sharply elevating the centrality score of the bridge token and securing its presence in the retained cache.

Key Experimental Results

Main Results

On the comprehensive LongBench benchmark across 6 task categories (18 datasets) using Llama-3-8B-Instruct under a 20% logical cache budget, CentralKV significantly outperforms baseline eviction strategies:

Category Metric Full Cache H2O (Heavy Hitter) SnapKV (Chunk) GraphKV (Sim-Graph) CentralKV (Ours)
Single-Doc QA F1 37.9 34.3±0.8 41.2 37.3±0.6 38.3±0.4
Multi-Doc QA F1 39.8 27.5±1.1 34.5 36.7±0.7 38.5±0.5
Summarization Rouge-L 21.5 19.5±0.7 25.2 22.1±0.5 22.4±0.3
Few-Shot Avg. Score 61.0 58.0±0.9 56.8 60.7±0.7 61.7±0.5
Code Edit Sim. 52.5 41.4±1.5 51.5 49.9±0.9 54.5±0.8
Synthetic Accuracy (%) 98.0 83.5±2.1 94.5 94.8±1.2 97.8±0.2
Macro Avg. % 51.8±0.3 44.0±0.9 50.6 50.2±0.7 52.2±0.4

Ablation Study

Ablation experiments on 2WikiMultihopQA demonstrate the necessity of each architectural component:

Config F1 Score \(\Delta\) Note
CentralKV (Full) 34.0 — full model (Max operator and per-head graphs)
w/o Max (use Soft-max) 32.3 -1.7 soft aggregation allows noise from weak neighbors
w/o Max (use Sum) 30.8 -3.2 linear summation dilutes critical path signals
w/o Recursion (\(\lambda = 0\)) 27.9 -6.1 isolates single-step attention, dropping recursive paths
w/o Per-Head (Global Graph) 29.6 -4.4 enforcing a shared graph flattens head-specific topology
w/o Implicit Decay (Explicit) 34.0 +0.0 (Slow) identical accuracy but incurs dense \(O(B)\) memory writes

Key Findings

  • Max aggregation is vital for multi-hop reasoning: Replacing the max operator with summation drops F1 by 3.2 points, showing that reasoning depends on following the strongest causal antecedent rather than averaging diffuse attention mass.
  • Superior long-context needle retrieval: In Needle In A Haystack tests at 128k context, CentralKV maintains 76% accuracy compared to 42% for H2O; at 256k, CentralKV retains 61% accuracy while H2O degrades to 22%.
  • Low latency and high generation throughput: Compared to GraphKV which introduces a 5.95ms similarity computation overhead (reducing throughput to 846 tok/s), CentralKV incurs only 0.95ms overhead with a generation throughput of 972 tok/s, virtually matching H2O's 996 tok/s.

Highlights & Insights

  • Decoupling structural centrality from attention frequency: The paper clearly demonstrates the existence of low-frequency, high-centrality "Structural Bridges" in long-context reasoning, shifting KV cache compression from frequency-based eviction to connectivity-based preservation.
  • Hardware-aware latency hiding: By exploiting the memory-bound nature of autoregressive decoding kernels, CentralKV executes register-level priority queue operations within SRAM during HBM memory wait cycles, achieving topological tracking with near-zero observable overhead.
  • Full orthogonality with budget allocation frameworks: CentralKV serves as an eviction criterion ("what to evict") that seamlessly integrates with layer-wise or head-wise budget allocators ("where to allocate"), elevating AdaKV's performance on 2WikiMultihopQA from 20.1 to 26.0.

Limitations & Future Work

  • Residual gaps on distributed evidence: While closing the reasoning gap, CentralKV remains lossy and can drop performance relative to Full Cache when an answer requires gathering multiple dispersed, weak evidential clues simultaneously.
  • Hardware and kernel specialization: The two-stage fused kernel relies heavily on NVIDIA GPU warp shuffle primitives and SRAM layouts, necessitating tailored reimplementation when porting to other hardware accelerators.
  • Future directions: The authors outline extending streaming attention graph algorithms to parameter-efficient fine-tuning (PEFT), multimodal long-context streaming, and hybrid linear attention architectures.
  • vs H2O / Scissorhands: These methods greedily accumulate attention mass to retain Heavy Hitters, failing on low-frequency bridge tokens that connect distant reasoning steps. CentralKV preserves these multi-step bridges via Maximum Influence Path centrality.
  • vs GraphKV: GraphKV computes expensive cosine similarities across key vectors to enforce semantic diversity, introducing significant latency; CentralKV reuses raw attention logits directly within the attention kernel to construct dynamic causal graphs with negligible overhead.
  • vs SnapKV / ChunkKV: Coarse chunk-level clustering risks discarding isolated critical tokens located within evicted blocks; CentralKV operates at token-level precision to preserve fine-grained structural hubs.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Formulates KV cache compression as streaming centrality on dynamic causal DAGs with seamless kernel fusion.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorously tested on LongBench across 18 datasets, extreme NIAH settings, cross-model transfers, and hardware-level profiling.
  • Writing Quality: ⭐⭐⭐⭐⭐ Excellent motivation, formal mathematical stability proofs, and clear structural case studies.
  • Value: ⭐⭐⭐⭐⭐ Provides an immediately deployable, plug-and-play solution to overcome the memory wall in long-context LLM reasoning.