KV Cache Compression 900000x Beyond TurboQuant and Per-Vector Shannon Limit

# Sequential KV Cache Compression via Probabilistic Language Tries: Beyond the Per-Vector Shannon Limit
Source: [https://arxiv.org/html/2604.15356](https://arxiv.org/html/2604.15356)
###### Abstract

Recent work on KV cache quantization, culminating in TurboQuant\[[13](https://arxiv.org/html/2604.15356#bib.bib14)\], 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 metricd𝒯​\(s,s′\)=−log2⁡Pℳ​\(s∧s′\)d\_\{\\mathcal\{T\}\}\(s,s^\{\\prime\}\)=\{\-\}\\log\_\{2\}P\_\{\\mathcal\{M\}\}\(s\\wedge s^\{\\prime\}\)from Probabilistic Language Tries \(PLTs\)\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\]\. 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 ofH​\(KVt\+1∣KV≤t\)≤H​\(tokent\+1∣token≤t\)H\(\\mathrm\{KV\}\_\{t\+1\}\\mid\\mathrm\{KV\}\_\{\\leq t\}\)\\leq H\(\\mathrm\{token\}\_\{t\+1\}\\mid\\mathrm\{token\}\_\{\\leq t\}\)\.

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 approximately914,000×914\{,\}000\\timesat the Shannon limit\. Even at1000×1000\\timesabove the entropy floor—a deliberately pessimistic worst\-case overhead, two orders of magnitude above the 2–5×\\timestypical of practical source coders—the ratio remains≈914×\\approx 914\\timesover 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\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2604.15356#S1)
2. [2Background](https://arxiv.org/html/2604.15356#S2)1. [2\.1The KV Cache in Transformer Inference](https://arxiv.org/html/2604.15356#S2.SS1) 2. [2\.2Per\-Vector Quantization: The State of the Art](https://arxiv.org/html/2604.15356#S2.SS2) 3. [2\.3Probabilistic Language Tries](https://arxiv.org/html/2604.15356#S2.SS3)
3. [3The Sequential Entropy Bound](https://arxiv.org/html/2604.15356#S3)1. [3\.1Setup and Notation](https://arxiv.org/html/2604.15356#S3.SS1) 2. [3\.2The Determinism Lemma](https://arxiv.org/html/2604.15356#S3.SS2) 3. [3\.3The Main Bound](https://arxiv.org/html/2604.15356#S3.SS3) 4. [3\.4Tightness of the Bound](https://arxiv.org/html/2604.15356#S3.SS4)
4. [4Layer 1: Probabilistic Prefix Deduplication](https://arxiv.org/html/2604.15356#S4)1. [4\.1The Exact Prefix Sharing Baseline](https://arxiv.org/html/2604.15356#S4.SS1) 2. [4\.2The PLT Trie Metric as a Deduplication Criterion](https://arxiv.org/html/2604.15356#S4.SS2) 3. [4\.3Storage Under Probabilistic Prefix Deduplication](https://arxiv.org/html/2604.15356#S4.SS3)
5. [5Layer 2: Predictive Delta Coding](https://arxiv.org/html/2604.15356#S5)1. [5\.1The Prediction](https://arxiv.org/html/2604.15356#S5.SS1) 2. [5\.2The Residual and Its Entropy](https://arxiv.org/html/2604.15356#S5.SS2) 3. [5\.3Adaptive Quantization of Residuals](https://arxiv.org/html/2604.15356#S5.SS3)
6. [6Composition and the Full Stack](https://arxiv.org/html/2604.15356#S6)1. [6\.1Orthogonality of the Two Layers](https://arxiv.org/html/2604.15356#S6.SS1) 2. [6\.2Composition with Per\-Vector Quantization](https://arxiv.org/html/2604.15356#S6.SS2) 3. [6\.3Asymptotic Behavior with Context Length](https://arxiv.org/html/2604.15356#S6.SS3)
7. [7Practical Implementation](https://arxiv.org/html/2604.15356#S7)1. [7\.1Efficient Prediction Computation](https://arxiv.org/html/2604.15356#S7.SS1) 2. [7\.2Integration with the Inference Loop](https://arxiv.org/html/2604.15356#S7.SS2) 3. [7\.3Trie\-Based Prefix Index](https://arxiv.org/html/2604.15356#S7.SS3)
8. [8Related Work](https://arxiv.org/html/2604.15356#S8)
9. [9Discussion](https://arxiv.org/html/2604.15356#S9)1. [9\.1The Two Shannon Limits](https://arxiv.org/html/2604.15356#S9.SS1) 2. [9\.2Implications for the “Memory Wall”](https://arxiv.org/html/2604.15356#S9.SS2) 3. [9\.3Relation to the Jevons Paradox](https://arxiv.org/html/2604.15356#S9.SS3) 4. [9\.4Rate\-Distortion Analysis of KV Compression](https://arxiv.org/html/2604.15356#S9.SS4) 5. [9\.5Connection to Speculative Decoding](https://arxiv.org/html/2604.15356#S9.SS5) 6. [9\.6Limitations and Open Problems](https://arxiv.org/html/2604.15356#S9.SS6) 7. [9\.7Conjectures and Open Problems](https://arxiv.org/html/2604.15356#S9.SS7) 8. [9\.8Conclusion](https://arxiv.org/html/2604.15356#S9.SS8)
10. [References](https://arxiv.org/html/2604.15356#bib)

## 1Introduction

Every time a transformer language model processes a token, it produces a pair of vectors—a*key*and a*value*—that are stored in the KV cache and reused in all subsequent attention computations\. This cache is the model’s working memory: it contains the compressed representation of everything the model has processed in the current context\. It is also one of the primary bottlenecks in large\-scale inference\.

For a model withLLlayers,HheadH\_\{\\mathrm\{head\}\}attention heads, head dimensiondd, and context lengthnn, the KV cache occupies2​L​Hhead​d​n2LH\_\{\\mathrm\{head\}\}dnfloating\-point values\. At typical scales \(L=80L\{=\}80,Hhead=64H\_\{\\mathrm\{head\}\}\{=\}64,d=128d\{=\}128,n=128,000n\{=\}128\{,\}000\), a single context in a 70B\-parameter model requires approximately 80 GB of cache memory in fp16—more than the model weights themselves\.

A rich literature has developed to compress the KV cache\. Quantization methods represent each cache entry in fewer bits\[[8](https://arxiv.org/html/2604.15356#bib.bib7),[4](https://arxiv.org/html/2604.15356#bib.bib8)\]\. Eviction methods discard entries unlikely to affect future attention scores\[[14](https://arxiv.org/html/2604.15356#bib.bib9),[7](https://arxiv.org/html/2604.15356#bib.bib10)\]\. Prefix sharing methods avoid redundant computation when multiple sessions share a common prefix\[[10](https://arxiv.org/html/2604.15356#bib.bib5),[5](https://arxiv.org/html/2604.15356#bib.bib6)\]\. TurboQuant\[[13](https://arxiv.org/html/2604.15356#bib.bib14)\]recently unified and extended the quantization line of work, achieving near\-optimal per\-vector compression via PolarQuant rotation followed by QJL residual correction, and proved a formal lower bound showing that no per\-vector method can do significantly better\.

#### The gap TurboQuant does not close\.

TurboQuant’s lower bound is tight—for the problem it solves\. That problem is:*given an isolated KV vector drawn from the post\-rotation distribution, what is the minimum number of bits needed to represent it?*The paper’s answer is approximately 3 bits per component, and TurboQuant achieves it\.

But the KV cache is not a collection of isolated vectors\. It is a*sequence*\. Each vector was produced by processing a token from a specific position in a specific context, and both the token and its position are samples from a structured probability distribution—the distribution the model was trained to model\. The information\-theoretic content of thett\-th KV vector, given all prior vectors, is not its raw entropy as an isolated sample\. It is its*conditional entropy*, conditioned on the model’s state after processing tokens11throught−1t\-1\.

This conditional entropy can be far smaller\. For a good language model operating on coherent text, the next token is highly predictable—and therefore the next KV vector is highly predictable\. The residual is small\. Its entropy is bounded by the model’s per\-token surprisal, which at typical perplexities of 10–20 is 3\.3–4\.3 bits*per entire token position*, not per component\.

The gap between TurboQuant’s floor and this sequential floor is not a rounding error\. It is the full redundancy of language—the 10–15 bits per token of predictable structure that Shannon identified in 1951\[[11](https://arxiv.org/html/2604.15356#bib.bib2)\]and that every good language model encodes\.

#### This paper\.

We make this gap precise and propose*sequential KV compression*, a two\-layer architecture that closes it\. Our contributions are:

1. 1\.The sequential entropy bound\(Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)\): a formal proof that the conditional entropy of KV vectors, given all prior cache entries, is bounded above by the model’s per\-token surprisal\.
2. 2\.Probabilistic prefix deduplication\(Section[4](https://arxiv.org/html/2604.15356#S4)\): using the PLT trie metric\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\], we identify semantically equivalent shared prefixes across sessions and store only the delta from the shared centroid, eliminating inter\-session redundancy beyond what exact prefix matching achieves\.
3. 3\.Predictive delta coding\(Section[5](https://arxiv.org/html/2604.15356#S5)\): within a single session, we store only the residual of each KV vector from the model’s own prediction, with the residual entropy bounded by the token\-level surprisal\.
4. 4\.Composability\(Section[6](https://arxiv.org/html/2604.15356#S6)\): both layers are orthogonal to per\-vector quantization methods and can be stacked beneath TurboQuant or any other quantizer\.
5. 5\.Asymptotic behavior\(Corollary[5](https://arxiv.org/html/2604.15356#Thmcorollary5)\): unlike per\-vector methods whose compression ratio is fixed by head dimension, sequential compression*improves with context length*, because a model that has processed more tokens has a more precise predictive distribution for what comes next\.

#### Why this is possible now\.

The sequential structure of the KV cache is not new\. What is new is a formal framework for exploiting it: the PLT trie metric\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\]gives a mathematically precise definition of “distance between token sequences in probability space,” and the prior\-guided caching theorem in that paper provides the theoretical foundation for using a model’s own probability estimates rather than empirical frequencies to identify shared structure\. The present paper applies that framework to the specific problem of KV cache compression\.

#### Organization\.

Section[2](https://arxiv.org/html/2604.15356#S2)reviews the KV cache, per\-vector quantization, and the PLT framework\. Section[3](https://arxiv.org/html/2604.15356#S3)establishes the sequential entropy bound\. Section[4](https://arxiv.org/html/2604.15356#S4)introduces probabilistic prefix deduplication\. Section[5](https://arxiv.org/html/2604.15356#S5)introduces predictive delta coding\. Section[6](https://arxiv.org/html/2604.15356#S6)analyzes how the layers compose\. Section[7](https://arxiv.org/html/2604.15356#S7)discusses practical implementation\. Section[8](https://arxiv.org/html/2604.15356#S8)situates the work relative to the literature\. Section[9](https://arxiv.org/html/2604.15356#S9)discusses implications and open problems\.

## 2Background

### 2\.1The KV Cache in Transformer Inference

A transformer language model withLLlayers processes a token sequence𝐭=\(t1,…,tn\)\\mathbf\{t\}=\(t\_\{1\},\\ldots,t\_\{n\}\)by computing, at each layerℓ\\elland positionii, a key vector𝐤i\(ℓ\)∈ℝd\\mathbf\{k\}^\{\(\\ell\)\}\_\{i\}\\in\\mathbb\{R\}^\{d\}and a value vector𝐯i\(ℓ\)∈ℝd\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}\\in\\mathbb\{R\}^\{d\}\. These are computed from the input embedding and prior layer activations via learned projection matrices:

𝐤i\(ℓ\)=WK\(ℓ\)​𝐱i\(ℓ\),𝐯i\(ℓ\)=WV\(ℓ\)​𝐱i\(ℓ\)\.\\mathbf\{k\}^\{\(\\ell\)\}\_\{i\}=W\_\{K\}^\{\(\\ell\)\}\\mathbf\{x\}^\{\(\\ell\)\}\_\{i\},\\qquad\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}=W\_\{V\}^\{\(\\ell\)\}\\mathbf\{x\}^\{\(\\ell\)\}\_\{i\}\.The*KV cache*𝒦\\mathcal\{K\}stores all\(𝐤i\(ℓ\),𝐯i\(ℓ\)\)\(\\mathbf\{k\}^\{\(\\ell\)\}\_\{i\},\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}\)pairs for every layerℓ∈\{1,…,L\}\\ell\\in\\\{1,\\ldots,L\\\}and every processed positioni∈\{1,…,n\}i\\in\\\{1,\\ldots,n\\\}, so that subsequent tokens can attend to all prior positions without recomputing them\. In autoregressive generation, extending the sequence by one token requires one forward pass plusO​\(n\)O\(n\)attention operations over the cache; without caching it would requireO​\(n2\)O\(n^\{2\}\)operations\.

The total cache size is2​L​Hhead​d​n2LH\_\{\\mathrm\{head\}\}dnvalues, whereHheadH\_\{\\mathrm\{head\}\}is the number of attention heads andddis the per\-head dimension\. In fp16 \(2 bytes per value\), a 128K\-token context on a 70B model requires approximately 80 GB\.

### 2\.2Per\-Vector Quantization: The State of the Art

The dominant approach to KV cache compression is quantization: represent each floating\-point vector component in fewer bits\. The key challenge is that KV vectors have outlier components—individual dimensions with much larger magnitude than the others—that cause severe quantization error if treated uniformly\.

TurboQuant\[[13](https://arxiv.org/html/2604.15356#bib.bib14)\]addresses this via two operations:

PolarQuant\.Apply a learned rotation matrixR∈ℝd×dR\\in\\mathbb\{R\}^\{d\\times d\}to each KV vector so that the rotated components have a more uniform, predictable distribution\. Because the rotation is applied to all vectors uniformly, it can be precomputed once with no per\-vector overhead\. This eliminates the 1–2 bits of overhead per component that prior outlier\-aware methods spent on metadata\.

QJL \(Quantized Johnson\-Lindenstrauss\)\.Quantize the rotated vector tobbbits per component using a precomputed quantizer\. Use a single additional sign bit to correct the expected bias introduced by quantization, ensuring that attention scores computed from compressed vectors are statistically unbiased\.

The combined scheme achieves a compression ratio of16/b16/b\(e\.g\.,≈5\.3×\\approx 5\.3\\timesatb=3b=3\) with negligible accuracy loss\. The paper proves a lower bound showing that, for vectors treated as independent samples from the post\-rotation distribution, no quantization scheme can achieve a higher compression ratio without accuracy loss\. This bound is tight: TurboQuant is near\-optimal for per\-vector quantization\.

### 2\.3Probabilistic Language Tries

We briefly recall the PLT framework\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\], which provides the formal machinery for our sequential approach\.

###### Definition 1\(Probabilistic Language Trie\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\]\)\.

LetVVbe a finite vocabulary andℳ\\mathcal\{M\}a generative model overV∗V^\{\*\}\. The*probabilistic language trie*𝒯​\(ℳ\)\\mathcal\{T\}\(\\mathcal\{M\}\)is the directed rooted tree whose nodes are prefixesx∈V∗x\\in V^\{\*\}and whose outgoing edges from nodexxare labeled by tokenst∈Vt\\in Vwith weightPℳ​\(t∣x\)P\_\{\\mathcal\{M\}\}\(t\\mid x\)\.

###### Definition 2\(Trie Metric\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\]\)\.

For two sequencess,s′∈V∗s,s^\{\\prime\}\\in V^\{\*\}, their*longest common prefix*in the trie iss∧s′s\\wedge s^\{\\prime\}—the maximal prefix shared by both sequences\. The*trie metric*is:

d𝒯​\(s,s′\)=−log2⁡Pℳ​\(s∧s′\)\.d\_\{\\mathcal\{T\}\}\(s,s^\{\\prime\}\)=\-\\log\_\{2\}P\_\{\\mathcal\{M\}\}\(s\\wedge s^\{\\prime\}\)\.Sequences with a long, high\-probability shared prefix are close in this metric; their KV traces share substantial structure\.

The trie metric has a direct compression interpretation:d𝒯​\(s,s′\)d\_\{\\mathcal\{T\}\}\(s,s^\{\\prime\}\)is the number of bits needed to locate the divergence point ofssands′s^\{\\prime\}within the probability distribution\. Sequences with small trie distance are redundant relative to each other: one can be described as a short delta from the other\.

## 3The Sequential Entropy Bound

### 3\.1Setup and Notation

Fix a transformer modelℳ\\mathcal\{M\}withLLlayers,HheadH\_\{\\mathrm\{head\}\}heads, and head dimensiondd\. For a token sequence𝐭=\(t1,…,tn\)\\mathbf\{t\}=\(t\_\{1\},\\ldots,t\_\{n\}\), let𝐤i\(ℓ\)\\mathbf\{k\}^\{\(\\ell\)\}\_\{i\}and𝐯i\(ℓ\)\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}denote the key and value vectors at layerℓ\\elland positionii\. Denote the full KV state at positioniias:

KVi=\(𝐤i\(ℓ\),𝐯i\(ℓ\)\)ℓ=1L∈ℝ2​L​d\.\\mathrm\{KV\}\_\{i\}=\\bigl\(\\mathbf\{k\}^\{\(\\ell\)\}\_\{i\},\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}\\bigr\)\_\{\\ell=1\}^\{L\}\\in\\mathbb\{R\}^\{2Ld\}\.The entire cache afternntokens isKV≤n=\(KV1,…,KVn\)\\mathrm\{KV\}\_\{\\leq n\}=\(\\mathrm\{KV\}\_\{1\},\\ldots,\\mathrm\{KV\}\_\{n\}\)\.

For a random token sequence drawn from the model’s own distribution𝐭∼Pℳ\\mathbf\{t\}\\sim P\_\{\\mathcal\{M\}\}, both the tokens and the KV vectors are random We writeH​\(⋅\)H\(\\cdot\)for Shannon entropy andH\(⋅∣⋅\)H\(\\cdot\\mid\\cdot\)for conditional entropy; since KV vectors are deterministic functions of the discrete token sequence, all entropies here are Shannon entropy\.

### 3\.2The Determinism Lemma

The key structural observation is that KV vectors are*deterministic functions*of the token sequence\. There is no randomness in a transformer’s forward pass given fixed weights and fixed inputs\.

###### Lemma 1\(KV determinism\)\.

For a fixed modelℳ\\mathcal\{M\}with deterministic forward pass,KVi\\mathrm\{KV\}\_\{i\}is a deterministic function of the token prefix\(t1,…,ti\)\(t\_\{1\},\\ldots,t\_\{i\}\):

KVi=Fℳ​\(t1,…,ti\)\\mathrm\{KV\}\_\{i\}=F\_\{\\mathcal\{M\}\}\(t\_\{1\},\\ldots,t\_\{i\}\)for some deterministic functionFℳ:Vi→ℝ2​L​Hhead​dF\_\{\\mathcal\{M\}\}:V^\{i\}\\to\\mathbb\{R\}^\{2LH\_\{\\mathrm\{head\}\}d\}\.

###### Proof\.

By definition of the transformer forward pass\. Given a fixed sequence of input tokens\(t1,…,ti\)\(t\_\{1\},\\ldots,t\_\{i\}\), the embedding layer, all attention computations, and all projection matrices are deterministic \(assuming no dropout or stochastic elements at inference time, which is standard\)\. ThereforeWK\(ℓ\)​𝐱i\(ℓ\)W\_\{K\}^\{\(\\ell\)\}\\mathbf\{x\}^\{\(\\ell\)\}\_\{i\}andWV\(ℓ\)​𝐱i\(ℓ\)W\_\{V\}^\{\(\\ell\)\}\\mathbf\{x\}^\{\(\\ell\)\}\_\{i\}are deterministic functions of\(t1,…,ti\)\(t\_\{1\},\\ldots,t\_\{i\}\)\. ∎

### 3\.3The Main Bound

###### Theorem 1\(Sequential entropy bound\)\.

Let𝐭=\(t1,t2,…\)\\mathbf\{t\}=\(t\_\{1\},t\_\{2\},\\ldots\)be a random token sequence drawn fromPℳP\_\{\\mathcal\{M\}\}\. For any positioni≥2i\\geq 2\(the bound holds trivially ati=1i=1sinceH​\(KV1\)≤H​\(t1\)H\(\\mathrm\{KV\}\_\{1\}\)\\leq H\(t\_\{1\}\)by Lemma[1](https://arxiv.org/html/2604.15356#Thmlemma1)and data processing\):

H​\(KVi∣KV≤i−1\)≤H​\(ti∣t1,…,ti−1\)=H​\(ti∣KV≤i−1\)\.H\\bigl\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{\\leq i\-1\}\\bigr\)\\;\\leq\\;H\\bigl\(t\_\{i\}\\mid t\_\{1\},\\ldots,t\_\{i\-1\}\\bigr\)\\;=\\;H\\bigl\(t\_\{i\}\\mid\\mathrm\{KV\}\_\{\\leq i\-1\}\\bigr\)\.The conditional entropy of theii\-th KV vector, given all prior cache entries, is bounded above by the model’s per\-token surprisal at positionii\.

###### Proof\.

The proof proceeds in two steps: first establishing thatσ​\(KV≤i−1\)=σ​\(t≤i−1\)\\sigma\(\\mathrm\{KV\}\_\{\\leq i\-1\}\)=\\sigma\(t\_\{\\leq i\-1\}\), then deriving the bound\.

Step 1: Injectivity and sigma\-algebra equivalence\.

We establish thattjt\_\{j\}is a measurable function ofKV≤j\\mathrm\{KV\}\_\{\\leq j\}for eachjj, by showing that the maptj↦KVj∣t<jt\_\{j\}\\mapsto\\mathrm\{KV\}\_\{j\}\\mid t\_\{<j\}is injective\.

Fix any contextt<jt\_\{<j\}and supposetj≠tj′t\_\{j\}\\neq t\_\{j\}^\{\\prime\}\. At layerℓ=1\\ell=1, the key vector is𝐤j\(1\)=WK\(1\)​E​\(tj\)\\mathbf\{k\}^\{\(1\)\}\_\{j\}=W\_\{K\}^\{\(1\)\}E\(t\_\{j\}\)\. Since the embedding matrixE:V→ℝdmodelE:V\\to\\mathbb\{R\}^\{d\_\{\\rm model\}\}has full column rank in any trained transformer \(distinct tokens receive distinct embeddings; the set of weight matrices for which any two token embeddings coincide has measure zero in parameter space\), we haveE​\(tj\)≠E​\(tj′\)E\(t\_\{j\}\)\\neq E\(t\_\{j\}^\{\\prime\}\), and sinceWK\(1\)∈ℝdhead×dmodelW\_\{K\}^\{\(1\)\}\\in\\mathbb\{R\}^\{d\_\{\\rm head\}\\times d\_\{\\rm model\}\}satisfies the generic condition that no pairwise embedding differenceE​\(t\)−E​\(t′\)E\(t\)\-E\(t^\{\\prime\}\)lies inker⁡WK\(1\)\\ker W\_\{K\}^\{\(1\)\}\(this holds with probability 1 over random weight matrices since the null space has dimensiondmodel−dheadd\_\{\\rm model\}\-d\_\{\\rm head\}and there are finitely many token pairs\), it follows that𝐤j\(1\)​\(tj\)≠𝐤j\(1\)​\(tj′\)\\mathbf\{k\}^\{\(1\)\}\_\{j\}\(t\_\{j\}\)\\neq\\mathbf\{k\}^\{\(1\)\}\_\{j\}\(t\_\{j\}^\{\\prime\}\)\. In particular,KVj\(1\)​\(tj\)≠KVj\(1\)​\(tj′\)\\mathrm\{KV\}\_\{j\}^\{\(1\)\}\(t\_\{j\}\)\\neq\\mathrm\{KV\}\_\{j\}^\{\(1\)\}\(t\_\{j\}^\{\\prime\}\)\.

SinceKVj\\mathrm\{KV\}\_\{j\}includes the layer\-1 componentKVj\(1\)\\mathrm\{KV\}\_\{j\}^\{\(1\)\}as a subvector, the full vectorKVj\\mathrm\{KV\}\_\{j\}distinguishestjt\_\{j\}fromtj′t\_\{j\}^\{\\prime\}\. Thustj↦KVj∣t<jt\_\{j\}\\mapsto\\mathrm\{KV\}\_\{j\}\\mid t\_\{<j\}is injective for eachjj\. \(No assumption about higher\-layer projections is needed: injectivity is witnessed by the layer\-1 keys alone\.\)

By Lemma[1](https://arxiv.org/html/2604.15356#Thmlemma1),KVj\\mathrm\{KV\}\_\{j\}is measurable w\.r\.t\.σ​\(t≤j\)\\sigma\(t\_\{\\leq j\}\)for eachjj\. By the injectivity just established,tjt\_\{j\}is measurable w\.r\.t\.σ​\(KVj,t<j\)\\sigma\(\\mathrm\{KV\}\_\{j\},t\_\{<j\}\)\. Applying this inductively:t1t\_\{1\}is determined byKV1\(1\)\\mathrm\{KV\}\_\{1\}^\{\(1\)\}\(hence byKV1\\mathrm\{KV\}\_\{1\}\);t2t\_\{2\}is determined by\(KV2,t1\)\(\\mathrm\{KV\}\_\{2\},t\_\{1\}\), hence by\(KV1,KV2\)\(\\mathrm\{KV\}\_\{1\},\\mathrm\{KV\}\_\{2\}\); and so on\. Thereforet<it\_\{<i\}are jointly measurable w\.r\.t\.σ​\(KV1,…,KVi−1\)\\sigma\(\\mathrm\{KV\}\_\{1\},\\ldots,\\mathrm\{KV\}\_\{i\-1\}\), giving:

σ​\(KV≤i−1\)=σ​\(t<i\)\.\\sigma\(\\mathrm\{KV\}\_\{\\leq i\-1\}\)=\\sigma\(t\_\{<i\}\)\.\(1\)
Step 2: The bound\.

SinceKVi=Fℳ​t≤i\\mathrm\{KV\}\_\{i\}=F\_\{\\mathcal\{M\}\}t\_\{\\leq i\}is a deterministic function of\(t≤i−1,ti\)\(t\_\{\\leq i\-1\},t\_\{i\}\), the data\-processing inequality gives:

H​\(KVi∣t≤i−1\)≤H​\(ti∣t≤i−1\)\.H\(\\mathrm\{KV\}\_\{i\}\\mid t\_\{\\leq i\-1\}\)\\leq H\(t\_\{i\}\\mid t\_\{\\leq i\-1\}\)\.Applying \([1](https://arxiv.org/html/2604.15356#S3.E1)\) to both sides \(conditioning onKV≤i−1\\mathrm\{KV\}\_\{\\leq i\-1\}is equivalent to conditioning ont≤i−1t\_\{\\leq i\-1\}\):

H​\(KVi∣KV≤i−1\)=H​\(KVi∣t≤i−1\)≤H​\(ti∣t≤i−1\)=H​\(ti∣KV≤i−1\),H\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{\\leq i\-1\}\)=H\(\\mathrm\{KV\}\_\{i\}\\mid t\_\{\\leq i\-1\}\)\\leq H\(t\_\{i\}\\mid t\_\{\\leq i\-1\}\)=H\(t\_\{i\}\\mid\\mathrm\{KV\}\_\{\\leq i\-1\}\),which is the stated inequality and equality simultaneously\. ∎

###### Corollary 1\(Per\-token surprisal bound\)\.

LetPP​\(ℳ\)\\mathrm\{PP\}\(\\mathcal\{M\}\)denote the perplexity of modelℳ\\mathcal\{M\}on a text distribution𝒟\\mathcal\{D\}\. The average conditional KV entropy satisfies:

1n​∑i=1nH​\(KVi∣KV≤i−1\)≤log2⁡PP​\(ℳ,𝒟\)bits per token position\.\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}H\\bigl\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{\\leq i\-1\}\\bigr\)\\;\\leq\\;\\log\_\{2\}\\mathrm\{PP\}\(\\mathcal\{M\},\\mathcal\{D\}\)\\quad\\text\{bits per token position\.\}At typical perplexities of 10–20 for fluent English:

1n​∑i=1nH​\(KVi∣KV≤i−1\)≤3\.3​to​4\.3​bits per token position\.\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}H\\bigl\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{\\leq i\-1\}\\bigr\)\\;\\leq\\;3\.3\\text\{ to \}4\.3\\text\{ bits per token position\.\}

###### Proof\.

By definition of perplexity,log2⁡PP​\(ℳ,𝒟\)=1n​𝔼​\[−log2⁡Pℳ​\(𝐭\)\]=1n​∑i=1nH​\(ti∣t1,…,ti−1\)\\log\_\{2\}\\mathrm\{PP\}\(\\mathcal\{M\},\\mathcal\{D\}\)=\\frac\{1\}\{n\}\\mathbb\{E\}\\bigl\[\-\\log\_\{2\}P\_\{\\mathcal\{M\}\}\(\\mathbf\{t\}\)\\bigr\]=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}H\(t\_\{i\}\\mid t\_\{1\},\\ldots,t\_\{i\-1\}\)\. Applying Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)position\-wise and averaging yields the result\. ∎

###### Corollary 2\(Compression ratio bounds\)\.

For a 70B\-scale model \(L=80L=80,Hhead=64H\_\{\\mathrm\{head\}\}=64,d=128d=128per head\) at perplexityPP∈\[10,20\]\\mathrm\{PP\}\\in\[10,20\], soh¯≤log2⁡PP∈\[3\.3,4\.3\]\\bar\{h\}\\leq\\log\_\{2\}\\mathrm\{PP\}\\in\[3\.3,4\.3\]bits/token:

1. \(a\)*Theoretical vs\. fp16:*Bfp16=2​L​Hhead​d⋅16≈2\.10×107B\_\{\\rm fp16\}=2LH\_\{\\mathrm\{head\}\}d\\cdot 16\\approx 2\.10\\times 10^\{7\}bits/token; ratio≈4\.9×106×\\approx 4\.9\\times 10^\{6\}\\timesatPP=20\\mathrm\{PP\}=20\.
2. \(b\)*Theoretical vs\. TurboQuant \(b=3b=3\):*BTQ=2​L​Hhead​d⋅3≈3\.93×106B\_\{\\rm TQ\}=2LH\_\{\\mathrm\{head\}\}d\\cdot 3\\approx 3\.93\\times 10^\{6\}bits/token; ratio≈914,000×\\approx 914\{,\}000\\timesatPP=20\\mathrm\{PP\}=20\.
3. \(c\)*Conservative practical vs\. TurboQuant:*At1000×1000\\timesabove the entropy floor:BTQ/4300≈914×B\_\{\\rm TQ\}/4300\\approx 914\\times\.

Items \(a\)–\(b\) are theoretical Shannon limits; item \(c\) uses1000×1000\\timesoverhead—a deliberately pessimistic worst\-case bound, two orders of magnitude above the22–5×5\\timesoverhead typical of practical arithmetic coders\[[12](https://arxiv.org/html/2604.15356#bib.bib3),[2](https://arxiv.org/html/2604.15356#bib.bib15)\]\. The abstract cites item \(c\) as a worst\-case lower bound on the practical ratio\.

###### Proof\.

Items \(a\) and \(b\) follow by substituting the stated model parameters into the formulaB=2​L​Hhead​d⋅bB=2LH\_\{\\mathrm\{head\}\}d\\cdot band dividing byh¯\\bar\{h\}\. Item \(c\) applies a1000×1000\\timesoverhead factor to the entropy floorh¯=4\.3\\bar\{h\}=4\.3bits/token, giving4,3004\{,\}300bits/token, then dividesBTQB\_\{\\rm TQ\}by this value\. ∎

### 3\.4Tightness of the Bound

The bound in Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)is not always tight\. It is tight whenFℳF\_\{\\mathcal\{M\}\}is an injective function oftit\_\{i\}alone given the prior context, and when all entropy inKVi\\mathrm\{KV\}\_\{i\}traces back to the single\-token choice\. In practice, the bound can be loose for two reasons:

1. 1\.Positional and structural information\.KV vectors encode not only the current token’s identity but also its position \(via positional encoding\) and layer\-specific features\. These components may carry additional entropy not captured by the token\-level bound\. However, positional encodings are deterministic functions of positioniiand therefore carry zero entropy conditioned on knowingii\. Layer\-specific features are also deterministic given the full token sequence\.
2. 2\.High\-entropy token positions\.At positions where the model is genuinely uncertain \(low probability assigned to the actual next token\), the KV residual will be larger\. Semantically surprising tokens—a new entity name, an unexpected topic shift, an unusual word choice— produce high\-surprisal positions where the bound is weakest\.

Conversely, the bound is nearly tight for long, coherent, predictable sequences—exactly the regime where long\-context inference is most valuable\. Legal documents, technical manuals, extended narratives, and code all exhibit low perplexity under a well\-matched model, and therefore yield highly compressible KV caches under sequential coding\.

## 4Layer 1: Probabilistic Prefix Deduplication

### 4\.1The Exact Prefix Sharing Baseline

Existing systems such as vLLM\[[5](https://arxiv.org/html/2604.15356#bib.bib6)\]and SGLang implement*exact prefix sharing*: when two sessions begin with the identical token sequence, the KV cache for their shared prefix is computed once and referenced by pointer\. This is valuable for fixed system prompts, few\-shot examples, and common preambles\.

Exact prefix sharing has a fundamental limitation: it operates at the*lexical*level\. Two sessions beginning with “You are a helpful assistant\.” and “You are an AI assistant\.” share no bytes and therefore share no cache under exact prefix sharing\. Yet their KV caches, layer by layer, will be very similar: both prompts steer the model toward a similar distribution over subsequent tokens\. The difference in their KV vectors is small relative to the total vector magnitude\.

### 4\.2The PLT Trie Metric as a Deduplication Criterion

The PLT trie metric \(Definition[2](https://arxiv.org/html/2604.15356#Thmdefinition2)\) provides the right notion of distance for identifying deduplications that exact prefix sharing misses\. Two prefixesssands′s^\{\\prime\}with small trie distanced𝒯​\(s,s′\)d\_\{\\mathcal\{T\}\}\(s,s^\{\\prime\}\)share a long, high\-probability common prefix\. At all positions within that shared prefix, their KV vectors are*identical*by Lemma[1](https://arxiv.org/html/2604.15356#Thmlemma1)\(Proposition[1](https://arxiv.org/html/2604.15356#Thmproposition1)\(a\)\)\. At the divergence point, the KV difference is bounded by the embedding spread \(Proposition[1](https://arxiv.org/html/2604.15356#Thmproposition1)\(b\)\)\. The trie metric thus directly controls KV cache similarity: small trie distance implies small KV delta, making probabilistic prefix deduplication well\-founded\.

We formalize this as follows\.

###### Definition 3\(Semantic prefix cluster\)\.

Letδ\>0\\delta\>0be a distance threshold and𝒮=\{s\(1\),…,s\(m\)\}\\mathcal\{S\}=\\\{s^\{\(1\)\},\\ldots,s^\{\(m\)\}\\\}a set of session prefixes\. A*semantic prefix cluster*at thresholdδ\\deltais a maximal subset𝒞⊆𝒮\\mathcal\{C\}\\subseteq\\mathcal\{S\}such that for alls,s′∈𝒞s,s^\{\\prime\}\\in\\mathcal\{C\}:

d𝒯​\(s,s′\)≤δ\.d\_\{\\mathcal\{T\}\}\(s,s^\{\\prime\}\)\\leq\\delta\.The*centroid*of𝒞\\mathcal\{C\}is the prefixs∗=arg⁡maxs∈𝒞⁡Pℳ​\(s\)s^\{\*\}=\\arg\\max\_\{s\\in\\mathcal\{C\}\}P\_\{\\mathcal\{M\}\}\(s\), i\.e\., the most probable prefix in the cluster\.

###### Proposition 1\(KV similarity within a cluster\)\.

Letssands′s^\{\\prime\}be two session prefixes that first diverge at positiond¯\+1\\bar\{d\}\+1\(i\.e\.,sj=sj′s\_\{j\}=s^\{\\prime\}\_\{j\}forj≤d¯j\\leq\\bar\{d\}andsd¯\+1≠sd¯\+1′s\_\{\\bar\{d\}\+1\}\\neq s^\{\\prime\}\_\{\\bar\{d\}\+1\}\)\. For a transformer withκ=maxℓ⁡κ\(ℓ\)≥1\\kappa=\\max\_\{\\ell\}\\kappa^\{\(\\ell\)\}\\geq 1\(the maximum per\-layer Lipschitz constant; explicit formulas in terms of weight matrix operator norms appear in a companion paper on certified inference caching, forthcoming on arXiv\):

1. \(a\)For all positionsi≤d¯i\\leq\\bar\{d\}and all layersℓ\\ell:KVi\(ℓ\)​\(s\)=KVi\(ℓ\)​\(s′\)\\mathrm\{KV\}^\{\(\\ell\)\}\_\{i\}\(s\)=\\mathrm\{KV\}^\{\(\\ell\)\}\_\{i\}\(s^\{\\prime\}\)\.
2. \(b\)At the divergence positioni=d¯\+1i=\\bar\{d\}\+1, for any layerℓ\\ell: ‖KVd¯\+1\(ℓ\)​\(s\)−KVd¯\+1\(ℓ\)​\(s′\)‖≤κℓ⋅‖E​\(sd¯\+1\)−E​\(sd¯\+1′\)‖,\\bigl\\\|\\mathrm\{KV\}^\{\(\\ell\)\}\_\{\\bar\{d\}\+1\}\(s\)\-\\mathrm\{KV\}^\{\(\\ell\)\}\_\{\\bar\{d\}\+1\}\(s^\{\\prime\}\)\\bigr\\\|\\;\\leq\\;\\kappa^\{\\ell\}\\cdot\\\|E\(s\_\{\\bar\{d\}\+1\}\)\-E\(s^\{\\prime\}\_\{\\bar\{d\}\+1\}\)\\\|,whereE​\(⋅\)E\(\\cdot\)is the token embedding map andκℓ\\kappa^\{\\ell\}denotesκ\\kapparaised to theℓ\\ell\-th power \(not a layer index\)\.

###### Proof\.

Part \(a\)\.For positionsi≤d¯i\\leq\\bar\{d\}, the token inputs are identical \(sj=sj′s\_\{j\}=s^\{\\prime\}\_\{j\}for allj≤d¯j\\leq\\bar\{d\}\), so by Lemma[1](https://arxiv.org/html/2604.15356#Thmlemma1)\(KV determinism\) the KV vectors agree exactly at every layer\.✓\\checkmark

Part \(b\)\.At positiond¯\+1\\bar\{d\}\+1, the embedding layer introduces a difference:‖𝐱d¯\+1\(0\)​\(s\)−𝐱d¯\+1\(0\)​\(s′\)‖=‖E​\(sd¯\+1\)−E​\(sd¯\+1′\)‖\\\|\\mathbf\{x\}^\{\(0\)\}\_\{\\bar\{d\}\+1\}\(s\)\-\\mathbf\{x\}^\{\(0\)\}\_\{\\bar\{d\}\+1\}\(s^\{\\prime\}\)\\\|=\\\|E\(s\_\{\\bar\{d\}\+1\}\)\-E\(s^\{\\prime\}\_\{\\bar\{d\}\+1\}\)\\\|\. Positions1,l​d​o​t​s,b​a​r​d1,\\\\ ldots,\\\\ bar\{d\}were identical, so their KV vectors—which contribute to positiond¯\+1\\bar\{d\}\+1’s attention output—are identical, and introduce no additional error\.

Defineκ\\kappaas the Lipschitz constant of the composed per\-layer map𝐱\(ℓ\)↦𝐱\(ℓ\+1\)\\mathbf\{x\}^\{\(\\ell\)\}\\mapsto\\mathbf\{x\}^\{\(\\ell\+1\)\}at positiond¯\+1\\bar\{d\}\+1, including the attention, MLP, layer\-norm, and key/value projections \(explicit formulas in terms of weight matrix operator norms are given in a companion paper on certified inference caching, forthcoming on arXiv\)\. Applying the Lipschitz bound across layers11throughℓ\\ell:

‖𝐱d¯\+1\(ℓ\)​\(s\)−𝐱d¯\+1\(ℓ\)​\(s′\)‖≤κℓ⋅‖E​\(sd¯\+1\)−E​\(sd¯\+1′\)‖\.\\\|\\mathbf\{x\}^\{\(\\ell\)\}\_\{\\bar\{d\}\+1\}\(s\)\-\\mathbf\{x\}^\{\(\\ell\)\}\_\{\\bar\{d\}\+1\}\(s^\{\\prime\}\)\\\|\\leq\\kappa^\{\\ell\}\\cdot\\\|E\(s\_\{\\bar\{d\}\+1\}\)\-E\(s^\{\\prime\}\_\{\\bar\{d\}\+1\}\)\\\|\.Since the KV projection𝐱\(ℓ\)↦KV\(ℓ\)\\mathbf\{x\}^\{\(\\ell\)\}\\mapsto\\mathrm\{KV\}^\{\(\\ell\)\}is itself part of the per\-layer map with norm absorbed intoκ\\kappa:

∥KVd¯\+1\(ℓ\)\(s\)−KVd¯\+1\(ℓ\)\(s′\)∥≤κℓ⋅∥E\(sd¯\+1\)−E\(sd¯\+1′\)∥\.✓\\\|\\mathrm\{KV\}^\{\(\\ell\)\}\_\{\\bar\{d\}\+1\}\(s\)\-\\mathrm\{KV\}^\{\(\\ell\)\}\_\{\\bar\{d\}\+1\}\(s^\{\\prime\}\)\\\|\\leq\\kappa^\{\\ell\}\\cdot\\\|E\(s\_\{\\bar\{d\}\+1\}\)\-E\(s^\{\\prime\}\_\{\\bar\{d\}\+1\}\)\\\|\.\\qquad\\checkmark∎

### 4\.3Storage Under Probabilistic Prefix Deduplication

###### Definition 4\(Cluster\-relative storage\)\.

Given a semantic prefix cluster𝒞\\mathcal\{C\}with centroids∗s^\{\*\}, store:

1. 1\.The full KV cacheKV≤n​\(s∗\)\\mathrm\{KV\}\_\{\\leq n\}\(s^\{\*\}\)for the centroid\.
2. 2\.For eachs∈𝒞∖\{s∗\}s\\in\\mathcal\{C\}\\setminus\\\{s^\{\*\}\\\}, the*delta cache*Δ​\(s,s∗\)=KV≤n​\(s\)−KV≤n​\(s∗\)\\Delta\(s,s^\{\*\}\)=\\mathrm\{KV\}\_\{\\leq n\}\(s\)\-\\mathrm\{KV\}\_\{\\leq n\}\(s^\{\*\}\)\(zero at all positions before the divergence ofssands∗s^\{\*\}\)\.

The key observation is thatΔ​\(s,s∗\)\\Delta\(s,s^\{\*\}\)is sparse: it is exactly zero at all positions before the divergence ofssands∗s^\{\*\}, and typically small after the divergence \(by Proposition[1](https://arxiv.org/html/2604.15356#Thmproposition1)\)\. The storage cost ofΔ​\(s,s∗\)\\Delta\(s,s^\{\*\}\)therefore scales with the length of the*tail*ofssafter divergence froms∗s^\{\*\}, not the full length ofss\.

###### Corollary 3\(Storage reduction from prefix deduplication\)\.

Suppose sessions are drawn i\.i\.d\. fromPℳP\_\{\\mathcal\{M\}\}and a cluster at thresholdδ\\deltacovers a fractionffof all sessions, with average tail lengthℓ¯\\bar\{\\ell\}after the shared prefix\. The storage cost per session, relative to storing full KV caches independently, is:

relative cost=\(1−f\)⋅1\+f⋅ℓ¯n=1−f​\(1−ℓ¯n\)\.\\text\{relative cost\}=\(1\-f\)\\cdot 1\+f\\cdot\\frac\{\\bar\{\\ell\}\}\{n\}=1\-f\\left\(1\-\\frac\{\\bar\{\\ell\}\}\{n\}\\right\)\.Whenℓ¯≪n\\bar\{\\ell\}\\ll n\(sessions diverge early\), the saving is approximatelyff, i\.e\., the number of full caches stored decreases by a factor offf\.

###### Proof\.

Measure storage in units of one fullnn\-position KV cache\. Of all sessions, fraction\(1−f\)\(1\-f\)lie outside the cluster and each requires 1 full unit\. Fractionfflie inside the cluster: their shared prefix\(n−ℓ¯\(n\-\\bar\{\\ell\}positions\) is stored once in the centroid and amortises across all cluster members, so each member stores only itsℓ¯\\bar\{\\ell\}\-position tail at costℓ¯/n\\bar\{\\ell\}/n\. The average per\-session storage is:

\(1−f\)⋅1\+f⋅ℓ¯n=1−f​\(1−ℓ¯n\),\(1\-f\)\\cdot 1\\;\+\\;f\\cdot\\frac\{\\bar\{\\ell\}\}\{n\}=1\-f\\\!\\left\(1\-\\frac\{\\bar\{\\ell\}\}\{n\}\\right\),which is the stated bound\. Asℓ¯/n→0\\bar\{\\ell\}/n\\to 0\(sessions diverge early from the centroid\) the saving approachesff, i\.e\., a factor\-ffreduction in the number of full caches stored\. ∎

In practice, for chat\-model deployments with a fixed system prompt and few\-shot examples,ffcan be close to 1 \(nearly all sessions share the same prefix\) andℓ¯/n\\bar\{\\ell\}/ncan be small \(the session\-specific content is a small fraction of the context\)\. Even for sessions with different system prompts, probabilistic clustering under the PLT metric groups semantically similar preambles and captures deduplication that exact matching misses entirely\.

## 5Layer 2: Predictive Delta Coding

### 5\.1The Prediction

At each positionii, before writingKVi\\mathrm\{KV\}\_\{i\}to cache, the model has already computed its probability distribution over theii\-th token:

Pℳ​\(ti∣t1,…,ti−1\)=softmax​\(𝐡i−1\(L\)​WLM\)vocabulary,P\_\{\\mathcal\{M\}\}\(t\_\{i\}\\mid t\_\{1\},\\ldots,t\_\{i\-1\}\)=\\text\{softmax\}\(\\mathbf\{h\}^\{\(L\)\}\_\{i\-1\}W\_\{\\rm LM\}\)\_\{\\text\{vocabulary\}\},where𝐡i−1\(L\)∈ℝdmodel\\mathbf\{h\}^\{\(L\)\}\_\{i\-1\}\\in\\mathbb\{R\}^\{d\_\{\\rm model\}\}is the final\-layer hidden state at positioni−1i\-1andWLM∈ℝdmodel×\|V\|W\_\{\\rm LM\}\\in\\mathbb\{R\}^\{d\_\{\\rm model\}\\times\|V\|\}is the language model head \(unembedding matrix\)\. This distribution induces a predicted KV vector for positionii: the expected KV vector under the model’s distribution over possible next tokens\.

###### Definition 5\(Predicted KV vector\)\.

The*predicted KV vector*at positionii, given context\(t1,…,ti−1\)\(t\_\{1\},\\ldots,t\_\{i\-1\}\), is:

KV^i=∑t∈VPℳ​\(t∣t1,…,ti−1\)⋅Fℳ​\(t1,…,ti−1,t\)\.\\widehat\{\\mathrm\{KV\}\}\_\{i\}=\\sum\_\{t\\in V\}P\_\{\\mathcal\{M\}\}\(t\\mid t\_\{1\},\\ldots,t\_\{i\-1\}\)\\cdot F\_\{\\mathcal\{M\}\}\(t\_\{1\},\\ldots,t\_\{i\-1\},t\)\.

In practice, computingKV^i\\widehat\{\\mathrm\{KV\}\}\_\{i\}exactly requires a forward pass for every vocabulary token, which is prohibitively expensive\. Section[7](https://arxiv.org/html/2604.15356#S7)discusses efficient approximations using the top\-kktokens under the model’s distribution\.

### 5\.2The Residual and Its Entropy

###### Definition 6\(KV residual\)\.

The*KV residual*at positioniiis:

Ri=KVi−KV^i\.R\_\{i\}=\\mathrm\{KV\}\_\{i\}\-\\widehat\{\\mathrm\{KV\}\}\_\{i\}\.Predictive delta coding storesRiR\_\{i\}\(compressed\) rather thanKVi\\mathrm\{KV\}\_\{i\}directly\.

###### Theorem 2\(Residual entropy bound\)\.

The conditional entropy of the KV residual satisfies:

H​\(Ri∣t1,…,ti−1\)≤H​\(KVi∣t1,…,ti−1\)≤H​\(ti∣t1,…,ti−1\)\.H\(R\_\{i\}\\mid t\_\{1\},\\ldots,t\_\{i\-1\}\)\\;\\leq\\;H\\bigl\(\\mathrm\{KV\}\_\{i\}\\mid t\_\{1\},\\ldots,t\_\{i\-1\}\\bigr\)\\;\\leq\\;H\\bigl\(t\_\{i\}\\mid t\_\{1\},\\ldots,t\_\{i\-1\}\\bigr\)\.Moreover, at positions where the model assigns high probability to the actual next token, the residual concentrates near zero:

𝔼​\[‖Ri‖22∣t1,…,ti−1\]≤Vart∼Pℳ\(⋅∣t<i\)​\[Fℳ​\(t<i,t\)\],\\mathbb\{E\}\\bigl\[\\\|R\_\{i\}\\\|\_\{2\}^\{2\}\\mid t\_\{1\},\\ldots,t\_\{i\-1\}\\bigr\]\\;\\leq\\;\\mathrm\{Var\}\_\{t\\sim P\_\{\\mathcal\{M\}\}\(\\cdot\\mid t\_\{<i\}\)\}\\bigl\[F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)\\bigr\],which is small whenPℳ\(⋅∣t<i\)P\_\{\\mathcal\{M\}\}\(\\cdot\\mid t\_\{<i\}\)is concentrated\.

###### Proof\.

The first inequality follows from the fact thatRi=KVi−KV^iR\_\{i\}=\\mathrm\{KV\}\_\{i\}\-\\widehat\{\\mathrm\{KV\}\}\_\{i\}andKV^i\\widehat\{\\mathrm\{KV\}\}\_\{i\}is a deterministic function oft<it\_\{<i\}\. ThereforeH​\(Ri∣t<i\)=H​\(KVi−KV^i∣t<i\)=H​\(KVi∣t<i\)H\(R\_\{i\}\\mid t\_\{<i\}\)=H\(\\mathrm\{KV\}\_\{i\}\-\\widehat\{\\mathrm\{KV\}\}\_\{i\}\\mid t\_\{<i\}\)=H\(\\mathrm\{KV\}\_\{i\}\\mid t\_\{<i\}\), since subtracting a constant does not change entropy\. The second inequality is Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)\.

For the variance bound: by Definition[5](https://arxiv.org/html/2604.15356#Thmdefinition5),KV^i=𝔼t∼P​\[F​\(t<i,t\)\]\\widehat\{\\mathrm\{KV\}\}\_\{i\}=\\mathbb\{E\}\_\{t\\sim P\}\[F\(t\_\{<i\},t\)\], soRi=F​\(t<i,ti\)−𝔼​\[F​\(t<i,t\)\]R\_\{i\}=F\(t\_\{<i\},t\_\{i\}\)\-\\mathbb\{E\}\[F\(t\_\{<i\},t\)\]\. Therefore𝔼​\[‖Ri‖2∣t<i\]=Vart∼P​\[F​\(t<i,t\)\]\\mathbb\{E\}\[\\\|R\_\{i\}\\\|^\{2\}\\mid t\_\{<i\}\]=\\mathrm\{Var\}\_\{t\\sim P\}\[F\(t\_\{<i\},t\)\]\. ∎

###### Corollary 4\(Coherent text compression\)\.

LetHi=H​\(ti∣t<i\)H\_\{i\}=H\(t\_\{i\}\\mid t\_\{<i\}\)denote the conditional entropy of the next token given the context \(not the realized surprisalhi=−log2⁡Pℳ​\(ti∣t<i\)h\_\{i\}=\-\\log\_\{2\}P\_\{\\mathcal\{M\}\}\(t\_\{i\}\\mid t\_\{<i\}\)\)\. The expected residual magnitude satisfies:

𝔼​\[‖Ri‖2\|t<i\]≤12​‖Fℳ‖Lip⋅CE⋅min⁡\(1,4​Hi​ln⁡2\),\\mathbb\{E\}\\bigl\[\\\|R\_\{i\}\\\|\_\{2\}\\;\\big\|\\;t\_\{<i\}\\bigr\]\\;\\leq\\;\\tfrac\{1\}\{2\}\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}\\cdot C\_\{E\}\\cdot\\sqrt\{\\min\(1,\\,4\\,H\_\{i\}\\ln 2\)\},where‖Fℳ‖Lip\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}is the Lipschitz constant ofFℳF\_\{\\mathcal\{M\}\}with respect to the input embeddingE​\(t\)E\(t\), andCE=maxt,t′∈V⁡‖E​\(t\)−E​\(t′\)‖C\_\{E\}=\\max\_\{t,t^\{\\prime\}\\in V\}\\\|E\(t\)\-E\(t^\{\\prime\}\)\\\|\. For low\-entropy positions \(Hi≈0H\_\{i\}\\approx 0, i\.e\., the model is near\-certain about the next token\), the expected residual approaches zero; for high\-entropy positions it can be as large as12​‖Fℳ‖Lip⋅CE\\tfrac\{1\}\{2\}\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}\\cdot C\_\{E\}\.

###### Proof\.

By Theorem[2](https://arxiv.org/html/2604.15356#Thmtheorem2),𝔼​\[‖Ri‖22∣t<i\]=Vart∼P​\[Fℳ​\(t<i,t\)\]\\mathbb\{E\}\[\\\|R\_\{i\}\\\|\_\{2\}^\{2\}\\mid t\_\{<i\}\]=\\mathrm\{Var\}\_\{t\\sim P\}\[F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)\]\. By Jensen’s inequality applied to the square root:𝔼​\[‖Ri‖2\]≤Var​\[Fℳ​\(t<i,t\)\]\\mathbb\{E\}\[\\\|R\_\{i\}\\\|\_\{2\}\]\\leq\\sqrt\{\\mathrm\{Var\}\[F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)\]\}\.

The variance ofFℳ​\(t<i,t\)F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)overt∼P\(⋅∣t<i\)t\\sim P\(\\cdot\\mid t\_\{<i\}\)satisfies, by the Lipschitz property ofFℳF\_\{\\mathcal\{M\}\}in the embeddingE​\(t\)E\(t\):

Vart∼P​\[Fℳ​\(t<i,t\)\]≤‖Fℳ‖Lip2⋅Vart∼P​\[E​\(t\)\]\.\\mathrm\{Var\}\_\{t\\sim P\}\[F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)\]\\leq\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}^\{2\}\\cdot\\mathrm\{Var\}\_\{t\\sim P\}\[E\(t\)\]\.For the embedding variance, we derive a bound that decays with conditional entropyHiH\_\{i\}using two standard inequalities\.

Step A \(Popoviciu\)\.For any random variableYYwith‖Y−c‖≤R\\\|Y\-c\\\|\\leq Ralmost surely \(for some centerccand radiusRR\),Var​\[Y\]=𝔼​\[‖Y−𝔼​\[Y\]‖2\]≤𝔼​\[‖Y−c‖2\]≤R2\\mathrm\{Var\}\[Y\]=\\mathbb\{E\}\[\\\|Y\-\\mathbb\{E\}\[Y\]\\\|^\{2\}\]\\leq\\mathbb\{E\}\[\\\|Y\-c\\\|^\{2\}\]\\leq R^\{2\}\. Applied toY=E​\(t\)Y=E\(t\)with centerc=\(E​\(t∗\)\+E​\(t∗∗\)\)/2c=\(E\(t^\{\*\}\)\+E\(t^\{\*\*\}\)\)/2and radiusR=CE/2R=C\_\{E\}/2\(half theℓ2\\ell^\{2\}diameter\):Var​\[E​\(t\)\]≤CE2/4\\mathrm\{Var\}\[E\(t\)\]\\leq C\_\{E\}^\{2\}/4\.

Vart∼P​\[E​\(t\)\]≤CE24\.\\mathrm\{Var\}\_\{t\\sim P\}\[E\(t\)\]\\leq\\frac\{C\_\{E\}^\{2\}\}\{4\}\.
Step B \(variance–entropy coupling\)\.We sharpen Step A to a bound that vanishes asHi→0H\_\{i\}\\to 0\. Sincemaxt⁡P​\(t\)≥2−H​\(P\)\\max\_\{t\}P\(t\)\\geq 2^\{\-H\(P\)\}\(from Jensen applied to concavelog\\log:H​\(P\)≤−log⁡maxt⁡P​\(t\)H\(P\)\\leq\-\\log\\max\_\{t\}P\(t\)\), we have1−maxt⁡P​\(t\)≤1−2−H​\(P\)≤H​\(P\)​ln⁡2=Hi​ln⁡21\-\\max\_\{t\}P\(t\)\\leq 1\-2^\{\-H\(P\)\}\\leq H\(P\)\\ln 2=H\_\{i\}\\ln 2, where the last step uses1−e−x≤x1\-e^\{\-x\}\\leq x\. By the König–Huygens identity,Var​\[E​\(t\)\]=12​𝔼t,t′∼P​\[‖E​\(t\)−E​\(t′\)‖2\]≤CE22​\(1−∑tP​\(t\)2\)\\mathrm\{Var\}\[E\(t\)\]=\\tfrac\{1\}\{2\}\\mathbb\{E\}\_\{t,t^\{\\prime\}\\sim P\}\[\\\|E\(t\)\-E\(t^\{\\prime\}\)\\\|^\{2\}\]\\leq\\tfrac\{C\_\{E\}^\{2\}\}\{2\}\(1\-\\sum\_\{t\}P\(t\)^\{2\}\), where the last step uses‖E​\(t\)−E​\(t′\)‖2≤CE2\\\|E\(t\)\-E\(t^\{\\prime\}\)\\\|^\{2\}\\leq C\_\{E\}^\{2\}for allt,t′t,t^\{\\prime\}\. Since∑tP​\(t\)2≥pmax2\\sum\_\{t\}P\(t\)^\{2\}\\geq p\_\{\\max\}^\{2\}, we have1−∑tP​\(t\)2≤1−pmax2=\(1−pmax\)​\(1\+pmax\)≤2​\(1−pmax\)1\-\\sum\_\{t\}P\(t\)^\{2\}\\leq 1\-p\_\{\\max\}^\{2\}=\(1\-p\_\{\\max\}\)\(1\+p\_\{\\max\}\)\\leq 2\(1\-p\_\{\\max\}\), givingVar​\[E​\(t\)\]≤CE2​\(1−pmax\)≤CE2​Hi​ln⁡2\\mathrm\{Var\}\[E\(t\)\]\\leq C\_\{E\}^\{2\}\(1\-p\_\{\\max\}\)\\leq C\_\{E\}^\{2\}H\_\{i\}\\ln 2\. Combining with the Popoviciu bound from Step A via the minimum:

Vart∼P​\[E​\(t\)\]≤CE24⋅min⁡\(1,4​Hi​ln⁡2\)\.\\mathrm\{Var\}\_\{t\\sim P\}\[E\(t\)\]\\leq\\frac\{C\_\{E\}^\{2\}\}\{4\}\\cdot\\min\\\!\\bigl\(1,\\,4H\_\{i\}\\ln 2\\bigr\)\.
Combining\.Substituting into the Lipschitz bound and taking the square root:

𝔼​\[‖Ri‖2\]≤‖Fℳ‖Lip2⋅CE24⋅min⁡\(1,4​Hi​ln⁡2\)=12​‖Fℳ‖Lip⋅CE⋅min⁡\(1,4​Hi​ln⁡2\)\.\\mathbb\{E\}\[\\\|R\_\{i\}\\\|\_\{2\}\]\\leq\\sqrt\{\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}^\{2\}\\cdot\\frac\{C\_\{E\}^\{2\}\}\{4\}\\cdot\\min\(1,4H\_\{i\}\\ln 2\)\}=\\frac\{1\}\{2\}\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}\\cdot C\_\{E\}\\cdot\\sqrt\{\\min\(1,4H\_\{i\}\\ln 2\)\}\.ForHiH\_\{i\}small \(near\-certain next token\):min⁡\(1,4​Hi​ln⁡2\)≈2​Hi​ln⁡2\\sqrt\{\\min\(1,4H\_\{i\}\\ln 2\)\}\\approx 2\\sqrt\{H\_\{i\}\\ln 2\}, giving𝔼​\[‖Ri‖2\]≲‖Fℳ‖Lip⋅CE⋅Hi​ln⁡2\\mathbb\{E\}\[\\\|R\_\{i\}\\\|\_\{2\}\]\\lesssim\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}\\cdot C\_\{E\}\\cdot\\sqrt\{H\_\{i\}\\ln 2\}, which vanishes asHi→0H\_\{i\}\\to 0and isO​\(Hi\)O\(\\sqrt\{H\_\{i\}\}\)\. ∎

### 5\.3Adaptive Quantization of Residuals

Because residual magnitude varies by position—small at predictable positions, large at surprising ones—a fixed bit\-depth quantizer is suboptimal\. The natural approach is*adaptive*quantization: use fewer bits for small residuals and more bits for large ones, proportional to the per\-token surprisal\.

###### Definition 7\(Surprisal\-adaptive quantizer\)\.

At positioniiwith surprisalhih\_\{i\}, allocatebib\_\{i\}bits per residual component, where:

bi=max⁡\(1,⌊b0⋅hih¯⌋\),b\_\{i\}=\\max\\\!\\left\(1,\\;\\left\\lfloor b\_\{0\}\\cdot\\frac\{h\_\{i\}\}\{\\bar\{h\}\}\\right\\rfloor\\right\),withb0b\_\{0\}a target average bit depth andh¯\\bar\{h\}the average surprisal\.

This adaptive scheme achieves the average entropy bound of Corollary[1](https://arxiv.org/html/2604.15356#Thmcorollary1)while concentrating bits where they are needed, improving the worst\-case accuracy at high\-surprisal positions relative to a uniform low\-bit quantizer\.

## 6Composition and the Full Stack

### 6\.1Orthogonality of the Two Layers

###### Proposition 2\(Layer orthogonality\)\.

Probabilistic prefix deduplication \(Section[4](https://arxiv.org/html/2604.15356#S4)\) and predictive delta coding \(Section[5](https://arxiv.org/html/2604.15356#S5)\) are information\-theoretically orthogonal: they exploit statistically independent sources of redundancy\.

###### Proof\.

We show that the total description length decomposes additively, with no bits counted twice\.

Letssbe a session drawn fromPℳP\_\{\\mathcal\{M\}\}and write its KV cache asKV≤n​\(s\)=\(KV1​\(s\),…,KVn​\(s\)\)\\mathrm\{KV\}\_\{\\leq n\}\(s\)=\(\\mathrm\{KV\}\_\{1\}\(s\),\\ldots,\\mathrm\{KV\}\_\{n\}\(s\)\)\. Lets∗s^\{\*\}be the cluster centroid forss\(Definition[3](https://arxiv.org/html/2604.15356#Thmdefinition3)\), and letd¯\\bar\{d\}be the token position at whichssands∗s^\{\*\}first diverge, so thatsj=sj∗s\_\{j\}=s^\{\*\}\_\{j\}forj≤d¯j\\leq\\bar\{d\}andsd¯\+1≠sd¯\+1∗s\_\{\\bar\{d\}\+1\}\\neq s^\{\*\}\_\{\\bar\{d\}\+1\}\.

Description ofKV≤n​\(s\)\\mathrm\{KV\}\_\{\\leq n\}\(s\)in the full stack\.By Definition[4](https://arxiv.org/html/2604.15356#Thmdefinition4), the encoder writes:

- •*Prefix*\(positions1≤i≤d¯1\\leq i\\leq\\bar\{d\}\): zero bits, sinceKVi​\(s\)=KVi​\(s∗\)\\mathrm\{KV\}\_\{i\}\(s\)=\\mathrm\{KV\}\_\{i\}\(s^\{\*\}\)exactly \(Proposition[1](https://arxiv.org/html/2604.15356#Thmproposition1)\(a\)\) and the centroid is stored separately\.
- •*Tail*\(positionsd¯\+1≤i≤n\\bar\{d\}\+1\\leq i\\leq n\): for each positioniiin the tail, the encoder applies predictive delta coding \(Definition[6](https://arxiv.org/html/2604.15356#Thmdefinition6)\) and storesRi​\(s\)R\_\{i\}\(s\), using a code of length at mostH​\(Ri∣KV<i\)\+O​\(1\)H\(R\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\)\+O\(1\)bits by standard source coding\[[2](https://arxiv.org/html/2604.15356#bib.bib15)\]\.

Rate decomposition\.The total rate for sessionssis:

L​\(s\)\\displaystyle L\(s\)=0⏟prefix, Layer 1\+∑i=d¯\+1n\[H​\(Ri∣KV<i​\(s\)\)\+O​\(1\)\]⏟tail, Layer 2\.\\displaystyle=\\underbrace\{0\}\_\{\\text\{prefix, Layer 1\}\}\+\\underbrace\{\\sum\_\{i=\\bar\{d\}\+1\}^\{n\}\\bigl\[H\(R\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\(s\)\)\+O\(1\)\\bigr\]\}\_\{\\text\{tail, Layer 2\}\}\.These two terms address disjoint index sets \(\{1,…,d¯\}\\\{1,\\ldots,\\bar\{d\}\\\}and\{d¯\+1,…,n\}\\\{\\bar\{d\}\+1,\\ldots,n\\\}respectively\) within the description ofss’s cache\. No positioniiis compressed by both layers simultaneously: Layer 1 eliminates positionsi≤d¯i\\leq\\bar\{d\}entirely by pointer to the centroid; Layer 2 applies only to positionsi\>d¯i\>\\bar\{d\}\. Therefore the bits saved by each layer are*non\-overlapping*, and the total saving is their sum\.

Independence of gain statistics\.The gain of Layer 1 \(the fractionffof full caches replaced by shared\-prefix pointers, Corollary[3](https://arxiv.org/html/2604.15356#Thmcorollary3)\) depends on the overlap structure of sessions underPℳP\_\{\\mathcal\{M\}\}—a property of the*joint*distribution over session pairs\. The gain of Layer 2 at each tail positionii\(the residual entropyH​\(Ri∣KV<i\)H\(R\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\)\) depends on the*per\-token surprisal*hih\_\{i\}within a single session—a marginal property of the language model’s token\-level distribution\. These statistics are functions of different aspects ofPℳP\_\{\\mathcal\{M\}\}and are not constrained to be equal or proportional, so improvements to one layer do not mechanically alter the gain of the other\. This is the sense in which the two layers are “information\-theoretically orthogonal”: each exploits a distinct, non\-overlapping portion of the total redundancy in the KV cache\. ∎

### 6\.2Composition with Per\-Vector Quantization

After applying the two sequential layers, the residualsRiR\_\{i\}are vectors that still need to be stored in finite\-precision format\. This is where per\-vector quantization methods, including TurboQuant, apply\.

###### Proposition 3\(Three\-layer composition\)\.

The full compression stack proceeds as follows:

1. 1\.Prefix deduplication:identify the shared prefix with the cluster centroid; store only the tail KV delta\.
2. 2\.Predictive delta coding:for each token in the tail, store the residualRi=KVi−KV^iR\_\{i\}=\\mathrm\{KV\}\_\{i\}\-\\widehat\{\\mathrm\{KV\}\}\_\{i\}\.
3. 3\.Per\-vector quantization \(e\.g\., TurboQuant\):represent eachRiR\_\{i\}in reduced precision\.

###### Proof\.

Steps 1 and 2 are exactly Definitions[4](https://arxiv.org/html/2604.15356#Thmdefinition4)and[6](https://arxiv.org/html/2604.15356#Thmdefinition6)\. Step 3 applies any per\-vector quantizer toRiR\_\{i\}\.

Correctness:KVi\\mathrm\{KV\}\_\{i\}is recovered asRi\+KV^iR\_\{i\}\+\\widehat\{\\mathrm\{KV\}\}\_\{i\}, whereKV^i\\widehat\{\\mathrm\{KV\}\}\_\{i\}is recomputed deterministically from prior context\. The quantization error on the recoveredKVi\\mathrm\{KV\}\_\{i\}equals the quantization error onRiR\_\{i\}\.

Rate improvement:By Corollary[4](https://arxiv.org/html/2604.15356#Thmcorollary4),𝔼​\[‖Ri‖2\]≤12​‖F‖Lip​CE​min⁡\(1,4​Hi​ln⁡2\)\\mathbb\{E\}\[\\\|R\_\{i\}\\\|\_\{2\}\]\\leq\\tfrac\{1\}\{2\}\\\|F\\\|\_\{\\rm Lip\}C\_\{E\}\\sqrt\{\\min\(1,4H\_\{i\}\\ln 2\)\}\. For low\-surprisal tokens \(HiH\_\{i\}small\),min⁡\(1,4​Hi​ln⁡2\)≈4​hi​ln⁡2\\min\(1,4H\_\{i\}\\ln 2\)\\approx 4h\_\{i\}\\ln 2, so𝔼​\[‖Ri‖2\]≲‖F‖Lip​CE​Hi​ln⁡2→0\\mathbb\{E\}\[\\\|R\_\{i\}\\\|\_\{2\}\]\\lesssim\\\|F\\\|\_\{\\rm Lip\}C\_\{E\}\\sqrt\{H\_\{i\}\\ln 2\}\\to 0\. BecauseRiR\_\{i\}is small in magnitude, the dynamic range needed to represent it is small, and a fixed\-precision quantizer with absolute errorε\\varepsilonuses effectivelylog2⁡\(𝔼​\[‖Ri‖2\]/ε\)\\log\_\{2\}\(\\mathbb\{E\}\[\\\|R\_\{i\}\\\|\_\{2\}\]/\\varepsilon\)bits—which decreases asHi→0H\_\{i\}\\to 0\. Therefore at low\-surprisal positions the residual is small enough that coarse quantization suffices, making the three\-layer stack strictly more bit\-efficient than quantizingKVi\\mathrm\{KV\}\_\{i\}directly \(whose magnitude does not vanish at low surprisal\)\. ∎

### 6\.3Asymptotic Behavior with Context Length

###### Corollary 5\(Compression improves with context length\)\.

LetH¯n=1n​∑i=1nHi\\bar\{H\}\_\{n\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}H\_\{i\}be the average conditional entropy \(whereHi=H​\(ti∣t<i\)H\_\{i\}=H\(t\_\{i\}\\mid t\_\{<i\}\)\) over a context of lengthnn\. By Corollary[1](https://arxiv.org/html/2604.15356#Thmcorollary1):

1n​∑i=1nH​\(KVi∣KV<i\)≤H¯n\.\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}H\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\)\\leq\\bar\{H\}\_\{n\}\.*Monotone entropy condition:*call a context*coherent*if its conditional entropy sequence\(Hi\)\(H\_\{i\}\)is non\-increasing:Hi\+1≤HiH\_\{i\+1\}\\leq H\_\{i\}for allii\(later tokens are more predictable given more context\)\. Under this condition,H¯n\+1=\(n​H¯n\+Hn\+1\)/\(n\+1\)≤H¯n\\bar\{H\}\_\{n\+1\}=\(n\\bar\{H\}\_\{n\}\+H\_\{n\+1\}\)/\(n\+1\)\\leq\\bar\{H\}\_\{n\}sinceHn\+1≤H¯nH\_\{n\+1\}\\leq\\bar\{H\}\_\{n\}\. Thus the sequential compression bound tightens monotonically with context length\.

*Empirical scope\.*Strict pointwise monotonicity does not hold universally: surprisal spikes at topic shifts, new entity names, and dialogue turn boundaries\. The condition holds*in expectation*for long, topically stable documents \(legal text, technical manuals, extended code\), where it is the most practically relevant regime for long\-context inference\. For sessions with high surprisal variance, the asymptotic improvement applies to the running averageh¯n\\bar\{h\}\_\{n\}rather than individual positions \(and using conditional entropyHiH\_\{i\}rather than the realized surprisalhih\_\{i\}, which is equal only in expectation\)\.

By contrast, per\-vector methods \(TurboQuant, KIVI, KVQuant\) apply a fixed bit\-depthbbper component regardless ofnn: their memory cost is2​L​Hhead​d​n⋅b2LH\_\{\\mathrm\{head\}\}dn\\cdot bbits, growing at constant rate2​L​Hhead​d​b2LH\_\{\\mathrm\{head\}\}dbbits per token\. Under the monotone surprisal condition, sequential compression’s marginal rate per token isHn=H​\(tn∣t<n\)H\_\{n\}=H\(t\_\{n\}\\mid t\_\{<n\}\), which is non\-increasing when the coherence condition holds in expectation\. Long\-context inference becomes cheaper per marginal token under sequential compression\.

###### Proof\.

The bound1n​∑H​\(KVi∣KV<i\)≤H¯n\\frac\{1\}\{n\}\\sum H\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\)\\leq\\bar\{H\}\_\{n\}is Corollary[1](https://arxiv.org/html/2604.15356#Thmcorollary1)\. The monotone decrease ofH¯n\\bar\{H\}\_\{n\}under the stated condition follows becauseHn\+1≤Hn≤H¯nH\_\{n\+1\}\\leq H\_\{n\}\\leq\\bar\{H\}\_\{n\}impliesH¯n\+1=n​H¯n\+Hn\+1n\+1≤n​H¯n\+H¯nn\+1=H¯n\\bar\{H\}\_\{n\+1\}=\\frac\{n\\bar\{H\}\_\{n\}\+H\_\{n\+1\}\}\{n\+1\}\\leq\\frac\{n\\bar\{H\}\_\{n\}\+\\bar\{H\}\_\{n\}\}\{n\+1\}=\\bar\{H\}\_\{n\}\. The comparison to per\-vector methods is immediate fromBpv=2​L​Hhead​dhead⋅b⋅nB\_\{\\rm pv\}=2LH\_\{\\mathrm\{head\}\}d\_\{\\mathrm\{head\}\}\\cdot b\\cdot n\(constant rate per token\)\. ∎

This is a qualitative reversal of the current situation\. Under TurboQuant or any per\-vector method, memory grows linearly with context length at a fixed rate\. Under sequential compression, the*marginal cost per token decreases*as context length grows, because the model’s growing context makes subsequent tokens more predictable\. Long\-context inference becomes cheaper, not more expensive, per marginal token\.

## 7Practical Implementation

We now discuss how to implement sequential KV compression efficiently, addressing the main engineering challenges\.

### 7\.1Efficient Prediction Computation

The predicted KV vector \(Definition[5](https://arxiv.org/html/2604.15356#Thmdefinition5)\) requires summing over all\|V\|≈50,000\|V\|\\approx 50\{,\}000vocabulary tokens, each requiring a forward pass\. This is prohibitively expensive\. We propose two approximations:

Top\-kkapproximation\.Use only the top\-kktokens by probability:

KV^i\(k\)=∑t∈topkPℳ​\(t∣t<i\)⋅Fℳ​\(t<i,t\)∑t∈topkPℳ​\(t∣t<i\)\.\\widehat\{\\mathrm\{KV\}\}\_\{i\}^\{\(k\)\}=\\frac\{\\sum\_\{t\\in\\mathrm\{top\}\_\{k\}\}P\_\{\\mathcal\{M\}\}\(t\\mid t\_\{<i\}\)\\cdot F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)\}\{\\sum\_\{t\\in\\mathrm\{top\}\_\{k\}\}P\_\{\\mathcal\{M\}\}\(t\\mid t\_\{<i\}\)\}\.At low perplexity, 95%\+ of the probability mass is concentrated in the top 5–20 tokens, sok=20k=20captures the prediction accurately while requiring only 20 forward pass evaluations instead of 50,000\.

Linear embedding approximation\.For each layerℓ\\ell, approximate the KV function as linear in the input embedding:

Fℳ\(ℓ\)​\(t<i,t\)≈𝐜\(ℓ\)​\(t<i\)\+A\(ℓ\)​\(t<i\)​E​\(t\),F\_\{\\mathcal\{M\}\}^\{\(\\ell\)\}\(t\_\{<i\},t\)\\approx\\mathbf\{c\}^\{\(\\ell\)\}\(t\_\{<i\}\)\+A^\{\(\\ell\)\}\(t\_\{<i\}\)E\(t\),where𝐜\(ℓ\)\\mathbf\{c\}^\{\(\\ell\)\}andA\(ℓ\)A^\{\(\\ell\)\}are computed once per position from the model’s internal state\. Under this approximation,KV^i≈𝐜​\(t<i\)\+A​\(t<i\)​E¯i\\widehat\{\\mathrm\{KV\}\}\_\{i\}\\approx\\mathbf\{c\}\(t\_\{<i\}\)\+A\(t\_\{<i\}\)\\bar\{E\}\_\{i\}, whereE¯i=𝔼t∼P​\[E​\(t\)\]\\bar\{E\}\_\{i\}=\\mathbb\{E\}\_\{t\\sim P\}\[E\(t\)\]is the expected embedding— computable as a single weighted sum over the vocabulary using the softmax output\.

### 7\.2Integration with the Inference Loop

Unlike TurboQuant, which operates as a post\-hoc quantizer with no changes to the model’s forward pass, predictive delta coding requires access to the softmax distribution at each position\. This distribution is already computed during inference \(it is the output of the final language model head before sampling\)\.

The integration points are:

1. 1\.Before writing KVito cache:computeKV^i\\widehat\{\\mathrm\{KV\}\}\_\{i\}using the top\-kkapproximation; subtract to obtainRiR\_\{i\}; quantize and writeRiR\_\{i\}\.
2. 2\.Before reading KVifrom cache:dequantizeRiR\_\{i\}; add backKV^i\\widehat\{\\mathrm\{KV\}\}\_\{i\}\(recomputed identically, since it depends only on prior context which is available\); returnKVi\\mathrm\{KV\}\_\{i\}\.

The additional compute cost per token isO​\(k⋅dmodel\)O\(k\\cdot d\_\{\\mathrm\{model\}\}\)for the top\-kkprediction, wherek≪\|V\|k\\ll\|V\|\. This is negligible relative to theO​\(n⋅dmodel\)O\(n\\cdot d\_\{\\mathrm\{model\}\}\)attention computation\.

### 7\.3Trie\-Based Prefix Index

Probabilistic prefix deduplication requires a data structure that supports:

1. 1\.*Insert*: add a new session prefix and its KV cache\.
2. 2\.*Best\-match lookup*: given a new session prefixss, find the stored prefixs∗s^\{\*\}maximizingd𝒯​\(s,s∗\)d\_\{\\mathcal\{T\}\}\(s,s^\{\*\}\)\(equivalently, maximizing the probability of the longest common prefix\)\.
3. 3\.*Evict*: remove a stored prefix and its KV cache\.

The PLT trie naturally supports all three operations\. The trie is maintained as a sparse structure over the high\-probability prefix tree, pruned at nodes with probability below a thresholdϵ\\epsilon\. Nearest\-neighbor lookup is a trie traversal: follow the path of the query sequence until it diverges from all stored paths, and return the deepest stored ancestor\. Insert adds a new path; evict removes a path and potentially prunes ancestors with no other children\.

All three operations run inO​\(n\)O\(n\)time in the length of the prefix, withO​\(K\)O\(K\)space forKKstored prefixes\.

## 8Related Work

KV cache quantization\.KIVI\[[8](https://arxiv.org/html/2604.15356#bib.bib7)\]introduced 2\-bit quantization with per\-channel scaling\. KVQuant\[[4](https://arxiv.org/html/2604.15356#bib.bib8)\]handled outliers via non\-uniform quantization\. TurboQuant\[[13](https://arxiv.org/html/2604.15356#bib.bib14)\]unified these approaches via PolarQuant rotation and proved a per\-vector Shannon limit, which our work extends to the sequential setting\.

KV cache eviction\.H2O\[[14](https://arxiv.org/html/2604.15356#bib.bib9)\]identified that attention scores concentrate on a small “heavy hitter” subset of tokens and evicts the rest\. SnapKV\[[7](https://arxiv.org/html/2604.15356#bib.bib10)\]uses prefill\-time attention patterns to predict which tokens will be important for generation\. Eviction is orthogonal to compression: it reduces cache*size*by discarding tokens; compression reduces cache*bit depth*while retaining all tokens\. Both approaches compose naturally with sequential compression\.

Prefix sharing\.vLLM\[[5](https://arxiv.org/html/2604.15356#bib.bib6)\]introduced paged attention with exact prefix sharing\. SGLang extended this with a radix tree for multi\-prompt prefix reuse\. Our probabilistic prefix deduplication generalizes these to semantic similarity under the PLT metric\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\]\.

Probabilistic Language Tries\.The PLT framework\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\]introduced the trie metric, proved the prior\-guided caching theorem, and identified prefix KV\-caching as a special case of PLT\-based artifact memoization\. The present paper applies the trie metric specifically to cross\-session KV deduplication and proves the sequential entropy bound connecting token\-level surprisal to KV vector entropy\.

Language modeling and compression\.Delétang et al\.\[[3](https://arxiv.org/html/2604.15356#bib.bib11)\]demonstrated that LLMs implicitly perform arithmetic coding and achieve state\-of\-the\-art compression on text corpora\. Shannon\[[11](https://arxiv.org/html/2604.15356#bib.bib2)\]estimated the true entropy of English at 1\.3 bits per character via human prediction experiments\. Our work draws on both results: the model’s near\-optimal compression of its training distribution implies near\-zero conditional entropy for KV vectors at low\-surprisal positions\.

## 9Discussion

### 9\.1The Two Shannon Limits

It is worth being precise about what we have and have not shown\. TurboQuant proves a lower bound on the per\-vector compression rate and shows it is nearly achieved\. We prove that the*per\-sequence*Shannon limit is lower, bounded by the per\-token surprisal\. These are genuinely different limits, and TurboQuant’s proof does not address ours\.

The per\-sequence limit is lower because it exploits*correlations across token positions*—specifically, the fact that the KV vector at positioniiis largely predictable from the KV vectors at positions11throughi−1i\-1\. Per\-vector methods, by definition, cannot exploit these correlations\.

### 9\.2Implications for the “Memory Wall”

The KV cache memory wall—the observation that cache size grows linearly with context length and at long contexts dominates model weight memory—is often framed as a hardware problem awaiting the next generation of memory technology\. Sequential compression suggests a complementary software path: the wall is lower than it appears, because the marginal cost of each additional token in a coherent context is bounded by that token’s surprisal, which decreases with context length\.

This does not eliminate the need for better hardware\. But it suggests that the software path to longer effective context windows is not exhausted by per\-vector quantization\.

### 9\.3Relation to the Jevons Paradox

Improvements in inference efficiency historically increase total demand rather than decreasing it: cheaper inference enables more users, longer contexts, and more ambitious applications\. Sequential compression, if realized, would continue this pattern\. The reduction in marginal KV cost at long contexts would make currently\-impractical applications—real\-time million\-token document analysis, persistent agent memory, continual learning from interaction— economically viable, driving total memory demand upward even as per\-token cost falls\.

### 9\.4Rate\-Distortion Analysis of KV Compression

The sequential entropy bound \(Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)\) is a lossless result: it characterizes the minimum bits needed for*exact*reconstruction of KV vectors\. Practical systems accept bounded reconstruction error; the relevant quantity is the*rate\-distortion function*Ri​\(D\)R\_\{i\}\(D\)for positioniiat distortion levelDD\.

###### Theorem 3\(KV Rate\-Distortion Bound\)\.

For positioniiwith conditional entropyHi=H​\(ti∣t<i\)H\_\{i\}=H\(t\_\{i\}\\mid t\_\{<i\}\)and residual varianceσi2=Vart∼P​\[Fℳ​\(t<i,t\)\]\\sigma\_\{i\}^\{2\}=\\mathrm\{Var\}\_\{t\\sim P\}\[F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)\], the rate\-distortion function \(minimum rate to reconstructKVi\\mathrm\{KV\}\_\{i\}with mean squared error≤D\\leq Dper component\) satisfies:

Ri\(D\)≤dhead2log2\(σi2D\)\+,R\_\{i\}\(D\)\\;\\leq\\;\\frac\{d\_\{\\mathrm\{head\}\}\}\{2\}\\log\_\{2\}\\\!\\left\(\\frac\{\\sigma\_\{i\}^\{2\}\}\{D\}\\right\)\_\{\+\},where\(x\)\+=max⁡\(0,x\)\(x\)\_\{\+\}=\\max\(0,x\)and the inequality uses the Gaussian upper bound from the KLT \(Karhunen–Loève transform\)\. Sinceσi2≤14​‖Fℳ‖Lip2⋅CE2⋅min⁡\(1,4​Hi​ln⁡2\)\\sigma\_\{i\}^\{2\}\\leq\\frac\{1\}\{4\}\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}^\{2\}\\cdot C\_\{E\}^\{2\}\\cdot\\min\(1,4H\_\{i\}\\ln 2\)\(Corollary[4](https://arxiv.org/html/2604.15356#Thmcorollary4)\):

Ri​\(D\)≤dhead2​\[log2⁡\(‖Fℳ‖Lip2​CE2​Hi​ln⁡2D\)\]\+\.R\_\{i\}\(D\)\\;\\leq\\;\\frac\{d\_\{\\mathrm\{head\}\}\}\{2\}\\left\[\\log\_\{2\}\\\!\\left\(\\frac\{\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}^\{2\}C\_\{E\}^\{2\}H\_\{i\}\\ln 2\}\{D\}\\right\)\\right\]\_\{\+\}\.In particular, for a target distortionDDsatisfyingD≥‖Fℳ‖Lip2​CE2​Hi​ln⁡2D\\geq\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}^\{2\}C\_\{E\}^\{2\}H\_\{i\}\\ln 2\(distortion exceeds the residual variance\), the rate is zero:*no bits are needed at low\-surprisal positions*\.

###### Proof\.

KVi\\mathrm\{KV\}\_\{i\}conditioned ont<it\_\{<i\}is a deterministic function of the discrete random variabletit\_\{i\}\. Sincetit\_\{i\}has\|V\|\|V\|possible values, the distribution ofKVi\\mathrm\{KV\}\_\{i\}has at most\|V\|\|V\|support points—a discrete distribution over a finite set of vectors\. The rate\-distortion function for this source is bounded above by the Gaussian rate\-distortion function with the same second moment \(Shannon’s source coding theorem: Gaussian maximizes R\-D at fixed variance\)\. After a KLT rotation diagonalizingCov​\[KVi\]\\mathrm\{Cov\}\[\\mathrm\{KV\}\_\{i\}\]with eigenvaluesλj\\lambda\_\{j\}:Ri\(D\)≤12∑jlog2\(λj/μ\)\+R\_\{i\}\(D\)\\leq\\frac\{1\}\{2\}\\sum\_\{j\}\\log\_\{2\}\(\\lambda\_\{j\}/\\mu\)\_\{\+\}\(water\-filling, whereμ\\musatisfies∑jmin⁡\(λj,μ\)=D\\sum\_\{j\}\\min\(\\lambda\_\{j\},\\mu\)=D\)\. This is at most the*isotropic*upper bound \(allλj=σi2/dhead\\lambda\_\{j\}=\\sigma\_\{i\}^\{2\}/d\_\{\\mathrm\{head\}\}\), which givesRi\(D\)≤\(dhead/2\)log2\(σi2/D\)\+R\_\{i\}\(D\)\\leq\(d\_\{\\mathrm\{head\}\}/2\)\\log\_\{2\}\(\\sigma\_\{i\}^\{2\}/D\)\_\{\+\}\. \(The actual water\-filling rate can only be smaller when eigenvalues are non\-uniform\.\) Substituting the variance bound from Corollary[4](https://arxiv.org/html/2604.15356#Thmcorollary4)completes the proof\.□\\square∎

###### Corollary 6\(Practical Bit Allocation\)\.

For a target distortionDDper KV component, the optimal bit allocation across positions assignsbi=Ri​\(D\)/dheadb\_\{i\}=R\_\{i\}\(D\)/d\_\{\\mathrm\{head\}\}bits per component at positionii\. The total bits per token is:

Btotal​\(D\)=∑i=1nRi​\(D\)≤dhead2​∑i=1n\[log2⁡\(‖F‖Lip2​CE2​Hi​ln⁡2D\)\]\+\.B\_\{\\mathrm\{total\}\}\(D\)=\\sum\_\{i=1\}^\{n\}R\_\{i\}\(D\)\\;\\leq\\;\\frac\{d\_\{\\mathrm\{head\}\}\}\{2\}\\sum\_\{i=1\}^\{n\}\\left\[\\log\_\{2\}\\\!\\left\(\\frac\{\\\|F\\\|\_\{\\mathrm\{Lip\}\}^\{2\}C\_\{E\}^\{2\}H\_\{i\}\\ln 2\}\{D\}\\right\)\\right\]\_\{\+\}\.At the TurboQuant operating point \(b=3b=3bits per component, uniform quantizer stepΔq=CE/2b\\Delta\_\{q\}=C\_\{E\}/2^\{b\}, giving distortionD≈Δq2/12=CE2/\(12⋅4b\)D\\approx\\Delta\_\{q\}^\{2\}/12=C\_\{E\}^\{2\}/\(12\\cdot 4^\{b\}\)\): positions withHi≤D/\(‖F‖Lip2​CE2​ln⁡2\)=1/\(12⋅4b⋅‖F‖Lip2​ln⁡2\)H\_\{i\}\\leq D/\(\\\|F\\\|\_\{\\mathrm\{Lip\}\}^\{2\}C\_\{E\}^\{2\}\\ln 2\)=1/\(12\\cdot 4^\{b\}\\cdot\\\|F\\\|\_\{\\mathrm\{Lip\}\}^\{2\}\\ln 2\)need*zero bits*\(residual variance is below the quantization noise floor\)\. The waterfilling allocation assigns proportionally more bits to high\-surprisal positions and zero bits to low\-surprisal ones, strictly dominating the uniform\-bb\-bit allocation of per\-vector methods\.

### 9\.5Connection to Speculative Decoding

Speculative decoding\[[6](https://arxiv.org/html/2604.15356#bib.bib23)\]uses a small draft modelℳdraft\\mathcal\{M\}\_\{\\mathrm\{draft\}\}to generateKKcandidate tokens, then verifies them in a single forward pass of the large modelℳ\\mathcal\{M\}\. The acceptance rate of tokenttunder speculative decoding ismin⁡\(1,Pℳ​\(t∣t<i\)/Pdraft​\(t∣t<i\)\)\\min\(1,P\_\{\\mathcal\{M\}\}\(t\\mid t\_\{<i\}\)/P\_\{\\mathrm\{draft\}\}\(t\\mid t\_\{<i\}\)\), averaging to1−TV​\(Pℳ,Pdraft\)1\-\\mathrm\{TV\}\(P\_\{\\mathcal\{M\}\},P\_\{\\mathrm\{draft\}\}\)where TV is the total variation distance\.

###### Theorem 4\(Speculative Decoding–KV Compression Duality\)\.

LetKV^i\(k\)\\widehat\{\\mathrm\{KV\}\}\_\{i\}^\{\(k\)\}be the top\-kkapproximation to the predicted KV vector \(Definition[5](https://arxiv.org/html/2604.15356#Thmdefinition5)\)\. Define the draft modelPdraft=P\_\{\\mathrm\{draft\}\}=the renormalized top\-kkdistribution ofℳ\\mathcal\{M\}\. Then:

1. \(a\)The speculative decoding acceptance rate ofPdraftP\_\{\\mathrm\{draft\}\}equals∑t∈topkPℳ​\(t∣t<i\)\\sum\_\{t\\in\\mathrm\{top\}\_\{k\}\}P\_\{\\mathcal\{M\}\}\(t\\mid t\_\{<i\}\)\.
2. \(b\)The conditional residual variance for tokens in the top\-kkset satisfies: Var​\[Fℳ​\(t<i,t\)∣t∈topk\]≤‖Fℳ‖Lip2⋅Vart∈topk​\[E​\(t\)\]\.\\mathrm\{Var\}\\bigl\[F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)\\mid t\\in\\mathrm\{top\}\_\{k\}\\bigr\]\\;\\leq\\;\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}^\{2\}\\cdot\\mathrm\{Var\}\_\{t\\in\\mathrm\{top\}\_\{k\}\}\[E\(t\)\]\.This equals zero atk=1k=1\(single token, deterministic\)\. Fork\>1k\>1the variance is not monotone inkkin general, but is bounded above by‖Fℳ‖Lip2⋅CE2/4\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}^\{2\}\\cdot C\_\{E\}^\{2\}/4for allkk\.
3. \(c\)Both speculative decoding and KV residual prediction use the same top\-kkdistribution ofℳ\\mathcal\{M\}\. The draft forward pass therefore serves both objectives simultaneously at no extra cost: computingPdraftP\_\{\\mathrm\{draft\}\}yields both the speculative token candidates*and*the predicted KV meanKV^i\(k\)\\widehat\{\\mathrm\{KV\}\}\_\{i\}^\{\(k\)\}\. Askkincreases, acceptance rate increases; the residual variance at covered positions is not guaranteed to be monotone, but is bounded by part \(b\)\.

###### Proof\.

\(a\) WithPdraft​\(t\)=Pℳ​\(t\)/ZkP\_\{\\mathrm\{draft\}\}\(t\)=P\_\{\\mathcal\{M\}\}\(t\)/Z\_\{k\}fort∈topkt\\in\\mathrm\{top\}\_\{k\}andZk=∑t∈topkPℳ​\(t\)≤1Z\_\{k\}=\\sum\_\{t\\in\\mathrm\{top\}\_\{k\}\}P\_\{\\mathcal\{M\}\}\(t\)\\leq 1, eachmin⁡\(1,Pℳ​\(t\)/Pdraft​\(t\)\)=min⁡\(1,Zk\)=Zk\\min\(1,P\_\{\\mathcal\{M\}\}\(t\)/P\_\{\\mathrm\{draft\}\}\(t\)\)=\\min\(1,Z\_\{k\}\)=Z\_\{k\}, so acceptance rate=∑topkZk⋅Pℳ​\(t\)/Zk=Zk=\\sum\_\{\\mathrm\{top\}\_\{k\}\}Z\_\{k\}\\cdot P\_\{\\mathcal\{M\}\}\(t\)/Z\_\{k\}=Z\_\{k\}\.✓\\checkmark

\(b\) Apply Corollary[4](https://arxiv.org/html/2604.15356#Thmcorollary4)to the conditional distributiont∣t∈topkt\\mid t\\in\\mathrm\{top\}\_\{k\}\. Atk=1k=1: point mass, zero variance\. For generalkk: the variance is bounded by‖Fℳ‖Lip2⋅CE2/4\\\|F\_\{\\mathcal\{M\}\}\\\|\_\{\\mathrm\{Lip\}\}^\{2\}\\cdot C\_\{E\}^\{2\}/4\(Popoviciu, since embeddings have diameterCEC\_\{E\}\)\.✓\\checkmark

\(c\) Both applications share the same top\-kkprobability computation from the model’s output distribution\. No additional inference is needed to obtain the KV predictor oncePdraftP\_\{\\mathrm\{draft\}\}is computed\.□\\square∎

### 9\.6Limitations and Open Problems

The main open question is the tightness of the sequential entropy bound in practice\. The theoretical bound \(Corollary[1](https://arxiv.org/html/2604.15356#Thmcorollary1)\) is tight when KV vectors are injective functions of the token sequence, which requires the weight matrices to be non\-degenerate\. Empirical measurement of actual residual magnitudes and their compression ratios under practical quantizers is needed to assess how close to the bound a real implementation can get\.

A second open question is the efficient computation of the top\-kkprediction\. Current transformer inference frameworks do not expose the internal KV computation in a way that easily supports top\-kkpredictive averaging\. Kernel\-level integration \(e\.g\., via Triton or CUDA\) would be needed for production deployment\.

A third open question concerns non\-autoregressive and non\-transformer architectures\. The bound in Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)holds for any model satisfying the determinism condition of Lemma[1](https://arxiv.org/html/2604.15356#Thmlemma1)\. State\-space models \(SSMs, Mamba\) maintain a fixed\-size state rather than a KV cache, but the same principle applies: the state entropy at each step is bounded by the token\-level surprisal\.

Future directions include:

- •Empirical benchmarks:measure actual residual magnitudes on public models \(Llama, Gemma, Mistral\) and text distributions, and compare achieved compression to the theoretical bound\.
- •Kernel implementation:implement predictive delta coding as a Triton kernel, building on the open\-source TurboQuant implementations\.
- •Hierarchical prediction:use not just the model’s next\-token distribution but also its longer\-range predictions \(beam search distributions, speculative decoding candidates\) to improve prediction accuracy and reduce residuals further\.
- •Lossy sequential compression:extend the rate\-distortion analysis of PLTs\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\]to the KV cache setting, allowing bounded distortion in exchange for additional compression beyond the lossless sequential limit\.

### 9\.7Conjectures and Open Problems

###### Conjecture 1\(Tightness of the Sequential Bound for Well\-Trained Models\)\.

For a transformerℳ\\mathcal\{M\}trained to near\-zero cross\-entropy on a corpus with stationary distributionPP, the sequential entropy bound is tight to within a constant factor:

H​\(KVi∣KV<i\)≥c⋅H​\(ti∣t<i\)H\\bigl\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\\bigr\)\\;\\geq\\;c\\cdot H\\bigl\(t\_\{i\}\\mid t\_\{<i\}\\bigr\)for some universal constantc\>0c\>0that does not depend onℳ\\mathcal\{M\}orii\.

*Evidence and partial proof sketch\.*The lower bound direction is the hard part\. An upper bound follows from Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)\. For the lower bound: sinceKVi\\mathrm\{KV\}\_\{i\}is an injective function oftit\_\{i\}givent<it\_\{<i\}\(Lemma[1](https://arxiv.org/html/2604.15356#Thmlemma1)\), the data\-processing inequality givesH​\(KVi∣KV<i\)=H​\(ti∣KV<i\)=H​\(ti∣t<i\)H\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\)=H\(t\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\)=H\(t\_\{i\}\\mid t\_\{<i\}\)\(using sigma\-algebra equivalence from the proof of Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)\)\.*The bound is therefore already tight: equality holds throughout\.*

This is not a conjecture but an observation implicit in the proof, stated here to clarify the theoretical status: the sequential entropy bound is*exact*\(equality, not inequality\)\. The open question is whether practical quantizers can approach the bound, which requires answering: how much entropy do the residualsRiR\_\{i\}carry at low\-surprisal positions under realistic token distributions? Equivalently: isVart∼P​\[Fℳ​\(t<i,t\)\]\\mathrm\{Var\}\_\{t\\sim P\}\[F\_\{\\mathcal\{M\}\}\(t\_\{<i\},t\)\]small whenHiH\_\{i\}is small for actual trained models?

###### Conjecture 2\(Cross\-Session Prefix Entropy Bound\)\.

For sessionss,s′s,s^\{\\prime\}drawn i\.i\.d\. fromPℳP\_\{\\mathcal\{M\}\}, the conditional entropy of sessionss’s KV cache given the cluster centroids∗s^\{\*\}’s full cache satisfies:

H​\(KV≤n​\(s\)∣KV≤n​\(s∗\)\)≤∑i=d¯\+1nH​\(ti\(s\)∣t<i\(s\)\)\+H​\(td¯\+1\(s\)∣td¯\+1\(s∗\),t<d¯\+1\(s\)\),H\\bigl\(\\mathrm\{KV\}\_\{\\leq n\}\(s\)\\mid\\mathrm\{KV\}\_\{\\leq n\}\(s^\{\*\}\)\\bigr\)\\;\\leq\\;\\sum\_\{i=\\bar\{d\}\+1\}^\{n\}H\\bigl\(t\_\{i\}^\{\(s\)\}\\mid t\_\{<i\}^\{\(s\)\}\\bigr\)\\;\+\\;H\\bigl\(t\_\{\\bar\{d\}\+1\}^\{\(s\)\}\\mid t\_\{\\bar\{d\}\+1\}^\{\(s^\{\*\}\)\},t\_\{<\\bar\{d\}\+1\}^\{\(s\)\}\\bigr\),whered¯\\bar\{d\}is the divergence position ofssands∗s^\{\*\}\.

*Partial proof sketch\.*The first term bounds the “tail” entropy of sessionssafter divergence: positionsi\>d¯i\>\\bar\{d\}are bounded by the sequential entropy bound exactly as in Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)\. The second term bounds the “divergence cost”: knowingtd¯\+1\(s∗\)t\_\{\\bar\{d\}\+1\}^\{\(s^\{\*\}\)\}provides partial information about which subtreessis in \(via the cluster structure\), reducing the entropy oftd¯\+1\(s\)t\_\{\\bar\{d\}\+1\}^\{\(s\)\}\. The bound formalizes the Layer 1 gain: prefix deduplication saves bits on the tail \(first term, bounded by per\-token surprisal\) and reduces divergence cost \(second term, bounded by the trie metricd𝒯​\(s,s∗\)d\_\{\\mathcal\{T\}\}\(s,s^\{\*\}\)\)\. A formal proof requires bounding the conditional mutual information between the centroid’s divergence token and the session’s divergence token, which depends on the cluster radiusδ\\delta\.

###### Conjecture 3\(Sequential Bound Strictly Dominates All Per\-Vector Bounds\)\.

For any per\-vector compression scheme𝒞\\mathcal\{C\}\(including TurboQuant, KIVI, KVQuant, and all future schemes bounded by the per\-vector Shannon limit\), there exists a context lengthn∗​\(𝒞\)n^\{\*\}\(\\mathcal\{C\}\)such that for alln\>n∗​\(𝒞\)n\>n^\{\*\}\(\\mathcal\{C\}\):

Rseq​\(n\)<R𝒞​\(n\),R\_\{\\mathrm\{seq\}\}\(n\)\\;<\\;R\_\{\\mathcal\{C\}\}\(n\),whereRseq​\(n\)R\_\{\\mathrm\{seq\}\}\(n\)is the total bits used by sequential compression andR𝒞​\(n\)R\_\{\\mathcal\{C\}\}\(n\)is the total bits used by scheme𝒞\\mathcal\{C\}, both for a context of lengthnn\.

*Partial proof\.*R𝒞​\(n\)≥Bpv⋅nR\_\{\\mathcal\{C\}\}\(n\)\\geq B\_\{\\rm pv\}\\cdot nfor someBpv\>0B\_\{\\rm pv\}\>0\(the per\-vector Shannon limit is a hard floor for any per\-vector scheme\)\.Rseq​\(n\)=∑i=1nH​\(KVi∣KV<i\)≤∑i=1nHiR\_\{\\mathrm\{seq\}\}\(n\)=\\sum\_\{i=1\}^\{n\}H\(\\mathrm\{KV\}\_\{i\}\\mid\\mathrm\{KV\}\_\{<i\}\)\\leq\\sum\_\{i=1\}^\{n\}H\_\{i\}\. Under the monotone entropy condition \(Corollary[5](https://arxiv.org/html/2604.15356#Thmcorollary5)\),1n​∑i=1nHi=H¯n→H∞<Bpv\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}H\_\{i\}=\\bar\{H\}\_\{n\}\\to H\_\{\\infty\}<B\_\{\\rm pv\}asn→∞n\\to\\infty\(sinceH∞H\_\{\\infty\}is the model’s entropy rate, which is strictly less than any fixed per\-vector bit budget for a model with perplexity<2Bpv/dhead<2^\{B\_\{\\rm pv\}/d\_\{\\rm head\}\}\)\. ThusRseq​\(n\)/n→H∞<Bpv≤R𝒞​\(n\)/nR\_\{\\mathrm\{seq\}\}\(n\)/n\\to H\_\{\\infty\}<B\_\{\\rm pv\}\\leq R\_\{\\mathcal\{C\}\}\(n\)/n, giving the stated strict dominance for largenn\. The thresholdn∗​\(𝒞\)=O​\(H∞/\(Bpv−H∞\)\)n^\{\*\}\(\\mathcal\{C\}\)=O\(H\_\{\\infty\}/\(B\_\{\\rm pv\}\-H\_\{\\infty\}\)\)\. The main gap in this argument: the monotone entropy condition holds only for coherent text; for mixed\-topic sessions with high surprisal variance,H¯n\\bar\{H\}\_\{n\}may not converge belowBpvB\_\{\\rm pv\}\. Boundingn∗n^\{\*\}for realistic session distributions is the key open problem\.

### 9\.8Conclusion

We have shown that the Shannon limit proved by TurboQuant applies to a per\-vector problem, and that the Shannon limit for the*sequential*KV cache compression problem is strictly lower\. The gap is the information\-theoretic redundancy of language—the predictable structure that a near\-optimal language model has already learned\.

We formalized this through two results: the sequential entropy bound \(Theorem[1](https://arxiv.org/html/2604.15356#Thmtheorem1)\), which connects KV vector entropy to per\-token surprisal, and the PLT trie metric\[[9](https://arxiv.org/html/2604.15356#bib.bib13)\], which enables cross\-session prefix deduplication in probability space\.

The combined architecture—probabilistic prefix deduplication, predictive delta coding, and per\-vector quantization—is theoretically capable of compression ratios far beyond what per\-vector methods can achieve, with the compression ratio improving rather than degrading as context length grows\.

TurboQuant is not the ceiling\. It is the ceiling of one approach to one subproblem\. The sequential structure of language points toward a different ceiling, considerably lower, and the path to it runs through the formal language the model has already learned\.

## References

- \[1\]T\. Cai, Y\. Li, Z\. Geng, H\. Peng, J\. D\. Lee, D\. Chen, and T\. Dao\(2024\)Medusa: simple LLM inference acceleration framework with multiple decoding heads\.arXiv preprint arXiv:2401\.10774\.Cited by:[Remark 5](https://arxiv.org/html/2604.15356#Thmremark5.p1.3.3)\.
- \[2\]T\. M\. Cover and J\. A\. Thomas\(2006\)Elements of information theory\.2nd edition,Wiley\-Interscience\.Cited by:[2nd item](https://arxiv.org/html/2604.15356#S6.I1.i2.p1.4),[Corollary 2](https://arxiv.org/html/2604.15356#Thmcorollary2.p1.8.3),[Remark 3](https://arxiv.org/html/2604.15356#Thmremark3.p1.15.9)\.
- \[3\]G\. Delétang, A\. Ruoss, P\. Duquenne, E\. Catt, T\. Genewein, C\. Mattern, J\. Grau\-Moya, L\. K\. Li, J\. Veness, A\. Gretton,et al\.\(2023\)Language modeling is compression\.arXiv preprint arXiv:2309\.10668\.Cited by:[§8](https://arxiv.org/html/2604.15356#S8.p5.1)\.
- \[4\]C\. Hooper, S\. Kim, H\. Mohammadzadeh, M\. W\. Mahoney, Y\. S\. Shao, K\. Keutzer, and A\. Gholami\(2024\)KVQuant: towards 10 million context length LLM inference with KV cache quantization\.arXiv preprint arXiv:2401\.18079\.Cited by:[§1](https://arxiv.org/html/2604.15356#S1.p3.1),[§8](https://arxiv.org/html/2604.15356#S8.p1.1)\.
- \[5\]W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. E\. Gonzalez, H\. Zhang, and I\. Stoica\(2023\)Efficient memory management for large language model serving with PagedAttention\.InProceedings of the ACM SIGOPS Symposium on Operating Systems Principles,Cited by:[§1](https://arxiv.org/html/2604.15356#S1.p3.1),[§4\.1](https://arxiv.org/html/2604.15356#S4.SS1.p1.1),[§8](https://arxiv.org/html/2604.15356#S8.p3.1)\.
- \[6\]Y\. Leviathan, M\. Kalman, and Y\. Matias\(2023\)Fast inference from transformers via speculative decoding\.arXiv preprint arXiv:2211\.17192\.Cited by:[§9\.5](https://arxiv.org/html/2604.15356#S9.SS5.p1.6)\.
- \[7\]Y\. Li, Y\. Huang, B\. Yang, B\. Venkitesh, A\. Locatelli, H\. Ye, T\. Cai, P\. Lewis, and D\. Chen\(2024\)SnapKV: LLM knows what you are looking for before generation\.arXiv preprint arXiv:2404\.14469\.Cited by:[§1](https://arxiv.org/html/2604.15356#S1.p3.1),[§8](https://arxiv.org/html/2604.15356#S8.p2.1)\.
- \[8\]Z\. Liu, J\. Yuan, H\. Jin, S\. Zhong, Z\. Xu, V\. Braverman, B\. Chen, and X\. Hu\(2024\)KIVI: a tuning\-free asymmetric 2\-bit quantization for KV cache\.arXiv preprint arXiv:2402\.02750\.Cited by:[§1](https://arxiv.org/html/2604.15356#S1.p3.1),[§8](https://arxiv.org/html/2604.15356#S8.p1.1)\.
- \[9\]G\. Magarshak\(2026\)Probabilistic language tries: a unified framework for compression, decision policies, and execution reuse\.arXiv preprint arXiv:2604\.06228\.Note:arXiv:2604\.06228 \[cs\.LG\]\. Submitted 29 March 2026Cited by:[item 2](https://arxiv.org/html/2604.15356#S1.I1.i2.p1.1),[§1](https://arxiv.org/html/2604.15356#S1.SS0.SSS0.Px3.p1.1),[§2\.3](https://arxiv.org/html/2604.15356#S2.SS3.p1.1),[§8](https://arxiv.org/html/2604.15356#S8.p3.1),[§8](https://arxiv.org/html/2604.15356#S8.p4.1),[4th item](https://arxiv.org/html/2604.15356#S9.I2.i4.p1.1),[§9\.8](https://arxiv.org/html/2604.15356#S9.SS8.p2.1),[Definition 1](https://arxiv.org/html/2604.15356#Thmdefinition1),[Definition 2](https://arxiv.org/html/2604.15356#Thmdefinition2),[Remark 1](https://arxiv.org/html/2604.15356#Thmremark1.p1.6.5)\.
- \[10\]R\. Pope, S\. Douglas, A\. Chowdhery, J\. Devlin, J\. Bradbury, J\. Heek, K\. Xiao, S\. Agrawal, and J\. Dean\(2023\)Efficiently scaling transformer inference\.InProceedings of Machine Learning and Systems,Vol\.5\.Cited by:[§1](https://arxiv.org/html/2604.15356#S1.p3.1)\.
- \[11\]C\. E\. Shannon\(1951\)Prediction and entropy of printed English\.Bell System Technical Journal30\(1\),pp\. 50–64\.Cited by:[§1](https://arxiv.org/html/2604.15356#S1.SS0.SSS0.Px1.p4.1),[§8](https://arxiv.org/html/2604.15356#S8.p5.1)\.
- \[12\]I\. H\. Witten, R\. M\. Neal, and J\. G\. Cleary\(1987\)Arithmetic coding for data compression\.Communications of the ACM30\(6\),pp\. 520–540\.Cited by:[Corollary 2](https://arxiv.org/html/2604.15356#Thmcorollary2.p1.8.3),[Remark 3](https://arxiv.org/html/2604.15356#Thmremark3.p1.15.9)\.
- \[13\]A\. Zandieh, M\. Daliri, M\. Hadian, V\. Mirrokni, P\. Kacham, L\. Gottesburen, and R\. Jayaram\(2026\)TurboQuant: online vector quantization with near\-optimal distortion rate\.InInternational Conference on Learning Representations \(ICLR\),Note:arXiv:2504\.19874\. Google Research, NYU, Google DeepMind, KAISTCited by:[§1](https://arxiv.org/html/2604.15356#S1.p3.1),[§2\.2](https://arxiv.org/html/2604.15356#S2.SS2.p2.1),[§8](https://arxiv.org/html/2604.15356#S8.p1.1)\.
- \[14\]Z\. Zhang, Y\. Sheng, T\. Zhou, T\. Chen, L\. Zheng, R\. Cai, Z\. Song, Y\. Tian, C\. Ré, C\. Barrett, Z\. Wang, and B\. Chen\(2023\)H2O: heavy\-hitter oracle for efficient generative inference of large language models\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§1](https://arxiv.org/html/2604.15356#S1.p3.1),[§8](https://arxiv.org/html/2604.15356#S8.p2.1)\.