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

• URL: http://arxiv.org/abs/2604.15356v1
• Date: Fri, 10 Apr 2026 22:48:19 GMT
• Title: Sequential KV Cache Compression via Probabilistic Language Tries: Beyond the Per-Vector Shannon Limit
• Abstract summary: Recent work on KV cache quantization, culminating in TurboQuant, has approached the Shannon entropy limit for per-vector compression of transformer key-value caches.<n>We observe that this limit applies to a strictly weaker problem than the one that actually matters: compressing the KV cache as a sequence.<n>The tokens stored in a KV cache are not arbitrary floating-point data -- they are samples from the exact formal language the model was trained on, and the model is by construction a near-optimal predictor of that language.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work on KV cache quantization, culminating in TurboQuant, has approached the Shannon entropy limit for per-vector compression of transformer key-value caches. We observe that this limit applies to a strictly weaker problem than the one that actually matters: compressing the KV cache as a sequence. The tokens stored in a KV cache are not arbitrary floating-point data -- they are samples from the exact formal language the model was trained on, and the model is by construction a near-optimal predictor of that language. We introduce sequential KV compression, a two-layer architecture that exploits this structure. The first layer, probabilistic prefix deduplication, identifies semantically equivalent shared prefixes across sessions using the trie metric d_T(s, s') = -log_2 P_M(s ^ s') from Probabilistic Language Tries (PLTs). The second layer, predictive delta coding, stores only the residual of each new KV vector from the model's own prediction of it, achieving a per-token entropy bound of H(KV_{i+1} | KV_{<=i}) <= H(token_{i+1} | token_{<=i}). We prove that at typical language model perplexity -- approximately 10-20 for fluent English text -- this bound is 3.3-4.3 bits on average per token position, compared to TurboQuant's 3 bits per vector component (with typical attention heads having 64-128 components). The theoretical compression ratio over TurboQuant is approximately 914,000x at the Shannon limit. Even at 1000x above the entropy floor -- a deliberately pessimistic worst-case overhead, two orders of magnitude above the 2-5x typical of practical source coders -- the ratio remains approximately 914x over TurboQuant, with compression improving rather than degrading as context length grows. The two layers are orthogonal and compose with existing per-vector quantization methods including TurboQuant.

Related papers

• VoxZip: Semantic-Anchored Temporal KV Cache Compression for Long-Context Audio Inference [53.883871460875234]
  VoxZip is a semantic-anchored KV cache compression framework.<n>First stage uses automatic speech recognition (ASR) transcriptions as explicit semantic anchors to temporally align, compress, and fuse audio tokens.<n>Second stage employs a dynamic filtering strategy based on temporally decayed accumulated attention to evict non-essential tokens.
  arXiv  Detail & Related papers  (2026-08-09T08:17:18Z)
• A JoLT for the KV Cache: Near-Lossless KV Cache Compression via Joint Tucker and JL-Residual Allocation for LLMs [0.0]
  Key-value (KV) cache has become the dominant memory cost of transformer inference.<n>Low-rank methods factor two-dimensional slices of the cache, or per-head matrices or cross-layer feature blocks, and quantization methods lower the bit-width of every entry.<n>Our method, JoLT, applies a partial Tucker decomposition that compresses only the token and feature axes while leaving the head and layer axes intact.<n>A randomized-SVD variant, FlashJoLT, delivers a 5-13x compression-time speedup at 1024-token context and matched quality.
  arXiv  Detail & Related papers  (2026-07-14T09:23:20Z)
• Fractal KV-Cache Archives: Lossless Symbolic Storage with In-Place Retrieval for Long-Context LLM Inference [0.0]
  Key-value ( KV) cache dominates the memory cost of long-context autoregressive inference.<n>We study how to store the resulting symbol stream once a position's KV state has been quantized to codebook indices.<n>A family of contractive iterated-map codes that serialize a symbol sequence into a sequence of low-dimensional real vectors is revisited.
  arXiv  Detail & Related papers  (2026-07-08T08:37:49Z)
• End-to-End Context Compression at Scale [81.70601323130997]
  Long-context language model inference is bottlenecked by memory, as the KV cache grows with context length.<n>Recent techniques to compress the KV cache fall short: they either degrade model quality substantially or require considerable time and compute to compress a single long prompt.<n>Existing approaches are not competitive with KV cache compression on the accuracy-efficiency frontier.
  arXiv  Detail & Related papers  (2026-06-08T15:43:16Z)
• TPLA: Tensor Parallel Latent Attention for Efficient Disaggregated Prefill and Decode Inference [48.40143137402824]
  Multi-Head Latent Attention (MLA) compresses key-value states into a low-rank latent vector, caching only this vector to reduce memory.<n>In tensor parallelism (TP), however, attention heads are computed across multiple devices, and each device must load the full cache.<n>We propose-Parallel Latent Attention (TPLA), a scheme that partitions both the latent representation and each head's input dimension across devices, performs attention independently per shard, and then combines results with an all-reduce.
  arXiv  Detail & Related papers  (2025-08-21T15:25:40Z)
• CommVQ: Commutative Vector Quantization for KV Cache Compression [50.37946553931796]
  We propose Commutative Vector Quantization (CommVQ) to significantly reduce memory usage for long-context LLM inference.<n>We first introduce additive quantization with a lightweight encoder and codebook to compress the KV cache.<n>Our approach achieves high accuracy with additive quantization and low overhead via the RoPE-commutative codebook.
  arXiv  Detail & Related papers  (2025-06-23T17:50:11Z)
• SQuat: Subspace-orthogonal KV Cache Quantization [19.131705063324883]
  We introduce SQuat (Subspace-orthogonal KV cache quantization), which reduces peak memory by 2.17 to 2.82, improves throughput by 2.45 to 3.60, and achieves more favorable benchmark scores than existing KV cache quantization algorithms.<n>We show that our method reduces peak memory by 2.17 to 2.82, improves throughput by 2.45 to 3.60, and achieves more favorable benchmark scores than existing KV cache quantization algorithms.
  arXiv  Detail & Related papers  (2025-03-31T17:37:32Z)
• Cramming 1568 Tokens into a Single Vector and Back Again: Exploring the Limits of Embedding Space Capacity [5.087492669838185]
  We show that vectors with compression ratios up to x1500 exist, which highlights two orders of magnitude gap between existing and practically attainable solutions.<n>The obtained limits highlight the substantial gap between the theoretical capacity of input embeddings and their practical utilization.
  arXiv  Detail & Related papers  (2025-02-18T17:08:45Z)
• KVSharer: Efficient Inference via Layer-Wise Dissimilar KV Cache Sharing [58.29726147780976]
  We propose a plug-and-play method called textit KVSharer, which shares the KV cache between layers to achieve layer-wise compression. Experiments show that textit KVSharer can reduce KV cache computation by 30%, thereby lowering memory consumption. We verify that textit KVSharer is compatible with existing intra-layer KV cache compression methods, and combining both can further save memory.
  arXiv  Detail & Related papers  (2024-10-24T08:06:41Z)
• GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM [37.87634266742105]
  Key-value (KV) caching has become the de-facto to accelerate generation speed for large language models (LLMs) inference. Existing methods rely on dropping unimportant tokens or quantizing all entries uniformly. We propose GEAR, an efficient KV cache compression framework that achieves near-lossless high-ratio compression.
  arXiv  Detail & Related papers  (2024-03-08T18:48:30Z)
• KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache [67.9776980972508]
  We develop a tuning-free 2bit KV cache quantization algorithm named KIVI. KIVI can enable Llama, Falcon, and Mistral models to maintain almost the same quality while using $mathbf2.6times$ less peak memory.
  arXiv  Detail & Related papers  (2024-02-05T06:06:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.