🤖 machine learning

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

This paper proposes a sequential KV cache compression framework using probabilistic language tries and predictive delta coding to exploit the inherent linguistic structure of token sequences, theoretically achieving compression ratios orders of magnitude higher than current per-vector quantization methods like TurboQuant.

Original authors: Gregory Magarshak

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gregory Magarshak

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a super-intelligent librarian (the AI) who has just finished reading a massive, 100,000-page book. To answer your next question, you need to remember everything you just read.

In the world of AI, this "memory" is called the KV Cache. It's a giant notebook where the AI writes down key details (Key and Value vectors) for every word it processes.

The Current Problem: The "Heavy Backpack"

Right now, every time the AI reads a word, it writes a whole new page in its notebook. Even if the word is just "the" or "and," it writes a full, detailed page.

The Old Way (TurboQuant): Researchers recently figured out how to shrink these pages. Instead of writing in full color (16-bit floating point), they write in black and white (3 bits). It's a great improvement, like switching from a hardcover book to a paperback.
The Limit: But there's a catch. The AI is still writing a new page for every single word, even if the word is predictable. It's like writing a new page for "The" even though you know the next word is almost certainly "cat" or "dog." You are still carrying a heavy backpack full of redundant pages.

The New Idea: "Predictive Memory"

This paper argues that the AI doesn't need to write a new page for every word. It needs to write a note about what changed.

The authors propose a two-step "magic trick" to shrink the memory by a factor of nearly one million compared to current methods.

Layer 1: The "Shared Story" Trick (Probabilistic Prefix Deduplication)

Imagine two people starting a conversation.

Person A: "You are a helpful assistant who loves coding."
Person B: "You are a helpful assistant who loves cooking."

Current AI: Writes down the entire sentence for both people. It sees "You are a helpful assistant who loves..." as different because the last word is different.
New AI: Realizes that for the first 90% of the sentence, the meaning is identical. It writes the shared part once in a master notebook. For Person A and Person B, it only writes a tiny sticky note saying: "Person A: change 'coding' to 'cooking'."

This is called Probabilistic Prefix Deduplication. It groups similar conversations together and only stores the differences.

Layer 2: The "Guess and Check" Trick (Predictive Delta Coding)

Now, imagine the AI is reading a story: "The sky is..."

Current AI: Writes down the full, detailed memory of the word "blue."
New AI: The AI is so good at reading that it already knows the next word is likely "blue." It doesn't write the memory of "blue." Instead, it writes a tiny note: "My guess was 'blue', and the actual word was 'blue'. The difference (residual) is zero."

If the word is something surprising, like "The sky is purple," the note is slightly bigger: "My guess was 'blue', but it was 'purple'. Here is the small difference."

This is Predictive Delta Coding. Instead of storing the whole memory, the AI only stores the error of its own prediction. Since the AI is usually right, the "error" is tiny and takes up almost no space.

Why This Changes Everything

The paper proves a mind-blowing mathematical fact:

Old Limit: The amount of space needed depends on how many "bits" you use to write a single word's memory. It's a fixed cost per word.
New Limit: The amount of space needed depends on how surprising the word is.
- If the story is predictable (like a legal contract or a code tutorial), the AI is almost always right. The memory cost drops to almost zero.
- If the story is chaotic and surprising, the cost goes up, but it's still much lower than before.

The Analogy:
Think of the old method as recording a video of a person walking. You record every single frame, even when they are just standing still.
The new method is like recording a video where you only record the movement. If the person stands still, you record nothing. If they take a step, you record just that step.

The Result

By combining these two tricks:

Sharing the common parts of different conversations.
Only storing the tiny differences between what the AI guessed and what actually happened.

The authors calculate that for long, coherent texts, this method could compress the memory by 900,000 times compared to the best current technology.

Why does this matter?
Currently, if you want an AI to remember a whole book, you need a supercomputer with massive RAM. With this new method, you could potentially run that same AI on a laptop or even a phone, because the "backpack" of memory becomes so light that it barely weighs anything at all.

In short: The paper says, "Stop writing down everything the AI knows. Just write down what the AI didn't guess correctly." And since the AI is a genius guesser, you end up with almost nothing to write down.

1. Problem Statement

The KV (Key-Value) cache is a primary bottleneck in large-scale transformer inference. For a model with $L$ layers, $H_{head}$ attention heads, head dimension $d$ , and context length $n$ , the cache stores $2LH_{head}dn$ floating-point values. For a 70B-parameter model with a 128k context, this requires ~80GB of memory in FP16, often exceeding the model weights themselves.

Current state-of-the-art solutions, such as TurboQuant, focus on per-vector quantization. They treat each KV vector as an isolated sample from a distribution and compress it to ~3 bits per component. While TurboQuant approaches the Shannon limit for independent vectors, the paper argues this is a "strictly weaker problem" than the actual challenge: compressing the KV cache as a sequence.

The Core Insight: KV vectors are not arbitrary floating-point data; they are deterministic functions of the token sequence generated by the model. Since the model is a near-optimal predictor of its training language, the next KV vector is highly predictable given the previous ones. The information content of a KV vector is its conditional entropy given the history, which is significantly lower than its raw entropy.

2. Methodology: Sequential KV Compression

The paper proposes a two-layer architecture that exploits the sequential structure of the KV cache, orthogonal to existing per-vector quantization methods.

Layer 1: Probabilistic Prefix Deduplication

Goal: Eliminate redundancy across different inference sessions (e.g., multiple users sharing similar system prompts or few-shot examples).
Mechanism: Instead of exact string matching (used by vLLM/SGLang), the method uses Probabilistic Language Tries (PLTs).
Metric: It utilizes the trie metric $d_T(s, s') = -\log_2 P_M(s \land s')$ , where $s \land s'$ is the longest common prefix. This measures the "distance" between two token sequences in probability space.
Process:
1. Sessions are clustered based on semantic similarity (small trie distance).
2. A centroid (the most probable prefix in the cluster) is stored in full.
3. Other sessions in the cluster store only the delta (residual) from the centroid starting at the point of divergence.
Result: This eliminates inter-session redundancy even when prefixes are not lexically identical but semantically equivalent.

Layer 2: Predictive Delta Coding

Goal: Eliminate redundancy within a single session by predicting the next KV vector based on the model's own state.
Mechanism:
1. Before writing $KV_i$ to the cache, the model computes the predicted KV vector $\hat{KV}_i$ based on the probability distribution over the next token $P_M(t_i | t_{<i})$ .
2. The system stores the residual $R_i = KV_i - \hat{KV}_i$ instead of the raw vector.
Entropy Bound: The paper proves that the entropy of this residual is bounded by the per-token surprisal (conditional entropy of the next token):
$H(KV_i | KV_{<i}) \leq H(t_i | t_{<i})$
Adaptive Quantization: Since residuals are small at predictable positions (low surprisal) and larger at surprising positions, the system uses surprisal-adaptive quantization, allocating fewer bits to predictable tokens and more to surprising ones.

Composition

These two layers are orthogonal and can be stacked underneath existing per-vector quantizers like TurboQuant. The full stack is:

Prefix Deduplication (Layer 1) $\rightarrow$ stores only the tail delta.
Predictive Delta Coding (Layer 2) $\rightarrow$ stores only the residual of the tail.
Per-Vector Quantization (e.g., TurboQuant) $\rightarrow$ compresses the residuals.

3. Key Contributions & Theoretical Results

A. The Sequential Entropy Bound (Theorem 1)

The paper formally proves that the conditional entropy of the $i$ -th KV vector, given all prior cache entries, is upper-bounded by the model's per-token surprisal:
$H(KV_i | KV_{<i}) \leq H(t_i | t_{<i})$

Implication: For fluent English text with a perplexity of 10–20, the average entropy is 3.3–4.3 bits per token position (covering all layers and heads).
Comparison: TurboQuant stores ~3 bits per component. With 128 components per head, 64 heads, and 80 layers, TurboQuant uses ~3.93 million bits per token position. The sequential bound is ~4.3 bits.
Theoretical Ratio: This yields a theoretical compression ratio of ~914,000× over TurboQuant. Even with a pessimistic 1000× overhead over the entropy floor, the ratio remains ~914×.

B. Asymptotic Behavior (Corollary 5)

Per-vector methods: Memory cost grows linearly with context length ( $O(n)$ ) at a fixed rate.
Sequential compression: As context length $n$ increases, the model's predictive distribution becomes more precise (surprisal $H(t_i|t_{<i})$ decreases). Consequently, the marginal cost per token decreases as context grows. Long-context inference becomes cheaper, not more expensive.

C. Rate-Distortion Analysis

The paper extends the analysis to lossy compression, showing that for low-surprisal tokens, the residual variance is so small that zero bits may be required to achieve a target distortion level, further outperforming uniform quantization.

4. Practical Implementation

The paper addresses engineering challenges to make this feasible:

Efficient Prediction: Computing the expected KV vector over the full vocabulary is too expensive. The authors propose a Top-k approximation (using the top 20 tokens) or a Linear Embedding Approximation to estimate the predicted KV vector with negligible overhead.
Integration: The method integrates into the inference loop by computing the prediction (using the softmax output already available) before caching the residual.
Trie Index: A sparse trie data structure supports efficient insertion, nearest-neighbor lookup (for prefix deduplication), and eviction.

5. Significance and Impact

Redefining the "Memory Wall": The paper argues that the memory wall is not just a hardware limitation but a software opportunity. The sequential redundancy of language is vast and currently untapped by per-vector methods.
Beyond TurboQuant: It demonstrates that TurboQuant's "Shannon limit" applies only to isolated vectors. By treating the cache as a sequence, the true limit is much lower.
Jevons Paradox: By drastically reducing the marginal cost of long contexts, this technology could enable previously impractical applications (e.g., real-time million-token analysis, persistent agent memory), potentially increasing total memory demand while lowering per-token costs.
Synergy with Speculative Decoding: The paper notes a duality between speculative decoding and KV prediction; the same top-k distribution used for drafting tokens can be used to compute the predicted KV mean, allowing both techniques to run with zero additional inference overhead.

Conclusion

"Sequential KV Cache Compression" proposes a paradigm shift from compressing vectors to compressing the sequence of vectors. By leveraging the model's own predictive power and the probabilistic structure of language (via PLTs), it theoretically achieves compression ratios orders of magnitude higher than current state-of-the-art quantization, with performance improving as context length increases.