Sequential KV Cache Compression via Probabilistic Language Tries: Beyond the Per-Vector Shannon Limit

2026-04-20 · Source: cs.AI updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Software Development & Engineering · Depth: Expert, extended

Summary

A new two-layer architecture, "sequential KV compression," is introduced to address the KV cache bottleneck in transformer language models, which can consume up to 80 GB for a 128K-token context in a 70B-parameter model. This method moves beyond per-vector compression techniques like TurboQuant, which approach the Shannon entropy limit for individual KV vectors, by exploiting the sequential nature of KV caches. The first layer, "probabilistic prefix deduplication," uses the trie metric $d_{\mathcal{T}}(s,s^{\prime})={-}\log_{2}P_{\mathcal{M}}(s\wedge s^{\prime})$ from Probabilistic Language Tries (PLTs) to identify and deduplicate semantically equivalent shared prefixes across sessions. The second layer, "predictive delta coding," stores only the residual of each new KV vector from the model's own prediction, achieving a per-token entropy bound of $H(\mathrm{KV}_{t+1}\mid\mathrm{KV}_{\leq t})\leq H(\mathrm{token}_{t+1}\mid\mathrm{token}_{\leq t})$. This approach offers a theoretical compression ratio of approximately $914,000\times$ over TurboQuant at the Shannon limit, improving with context length, and is composable with existing per-vector quantization methods.

Key takeaway

For AI Engineers and Research Scientists optimizing large language model inference, sequential KV compression offers a path to drastically reduce memory bottlenecks. By adopting probabilistic prefix deduplication and predictive delta coding, your systems can achieve orders of magnitude greater compression than current per-vector methods, especially for longer contexts. Consider integrating this two-layer architecture, potentially reusing existing speculative decoding infrastructure, to enhance memory efficiency and scale LLM deployments.

Key insights

Exploiting the sequential, predictable nature of KV caches significantly surpasses per-vector compression limits.

Principles

• KV vectors are deterministic functions of token sequences.
• Conditional entropy of KV vectors is bounded by per-token surprisal.
• Compression improves with context length for sequential methods.

Method

Sequential KV compression uses probabilistic prefix deduplication via PLT trie metrics and predictive delta coding of KV residuals, bounded by token-level surprisal.

In practice

• Reuse speculative decoding draft distributions for KV prediction.
• Integrate with existing per-vector quantizers like TurboQuant.
• Implement as Triton or CUDA kernels for production.

Topics

• Sequential KV Compression
• Probabilistic Language Tries
• Predictive Delta Coding
• KV Cache Optimization
• Transformer Inference

Best for: AI Engineer, NLP Engineer, Research Scientist, AI Scientist, Machine Learning Engineer, AI Architect

Related on AIssential

• PolyKV: Heterogeneous Retention and Allocation for KV Cache Compression — PolyKV optimizes KV cache compression by applying heterogeneous, layer-wise policies and non-uniform budget allocation, significantly improving long-context LLM performance.
• STAR-KV: Low-Rank KV Cache Compression via Soft Thresholding for Adaptive Rank Control — STAR-KV adaptively compresses KV cache using fine-grained rank control, achieving significant memory and speed improvements.
• Still: Amortized KV Cache Compaction in a Single Forward Pass — Still offers an efficient, high-quality KV cache compaction method for long-context language models via a single forward pass Perceiver.
• KVCapsule: Efficient Sequential KV Cache Compression for Vision-Language Models with Asymmetric Redundancy — KVCapsule efficiently compresses VLM KV caches by leveraging asymmetric redundancy and dynamic attention patterns in vision tokens.
• KV Cache Demystified: Speeding Up Large Language Models — KV cache optimizes LLM inference by storing and reusing attention keys and values, preventing redundant computations.
• Compressing Sequences in the Latent Embedding Space: $K$-Token Merging for Large Language Models — K-Token Merging compresses LLM inputs in the latent embedding space for efficiency.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.AI updates on arXiv.org.