Long-context language models are expensive because attention compares every token with every other token, so cost grows with the square of the sequence length. The cache of past keys and values also grows with every token generated. A common fix is to compress the context: a learned module reads each segment of text and squeezes it into a few "gist tokens," short summary vectors that the model attends to instead of the original text. Current systems give every segment the same number of gist tokens, for example one per four input tokens. Information theory says this uniform split is the wrong allocation whenever segments differ in how much new information they carry. Rate-distortion theory studies the fewest bits needed to describe a source within a given error. Its classical answer for many independent components sharing one bit budget is "reverse water-filling": predictable components get a minimal floor of resources, and the leftover goes to components whose information content rises above a common water level. A second classical result, coding with side information at the decoder, adds that the bits needed depend on what the receiver does not already know, not on how complex the source looks on its own.
This note proposes to treat a frozen language model's own knowledge as decoder side information. The amount of new information in each segment is measured by the decoder's conditional surprisal, which is how unexpected the segment's tokens are to the model given the earlier compressed context. A fixed gist budget is then allocated across segments by reverse water-filling on that quantity, in block-aligned units so the result still runs on standard fused attention kernels. The claim is concrete and falsifiable. At the same total cache size, water-filled allocation should recover most of the gap between uniform gist compression and full attention, with the largest gains at the 8× to 16× ratios where uniform compression is known to collapse and on the rare-fact recall where it fails. The gain should come specifically from using the decoder's conditional surprisal rather than encoder-side entropy or learned importance scores.
Core Claim
The strongest empirical study of gist compression, A Silver Bullet or a Compromise for Full Attention?, compares placements and training schemes for gist tokens. It finds that interleaving gist tokens throughout segments works best, a design it calls fine-grained KV caching (Fine-KV). It also names three failure modes: recall drops right after a segment boundary, low-probability "surprise" facts get smoothed away, and long verbatim strings break mid-generation. All three are what a rate-starved code would produce. A uniform budget over-spends on boilerplate and under-spends on the few segments that carry needles, identifiers, or facts the model cannot guess. The same pattern appears in In-context Autoencoder for Context Compression, which maps 512 tokens to a fixed 128 memory vectors and degrades sharply beyond 4×. It appears again in ComprExIT, which coordinates which compressed slot receives which token's information using optimal transport, but keeps the number of slots fixed. These papers motivate the proposal: they show a rate bottleneck, but none of them chooses the rate.
We supply the missing allocation rule from single-letter theory. Single-letter characterization means reducing a limit over arbitrarily long sequences to an optimization over a few per-symbol random variables, which is what makes rate questions computable at all. Suppose segment $i$ has an effective information scale $\sigma_i^2$, and the downstream error when it receives rate $R_i$ behaves like the Gaussian distortion-rate form $D_i(R_i)=\sigma_i^2 2^{-2R_i}$. Minimizing total error $\sum_i D_i$ subject to a total budget $\sum_i R_i \le R$ then gives reverse water-filling:
$$D_i = \min(\theta, \sigma_i^2), \qquad R_i = \max\left(0, \tfrac{1}{2}\log_2 \frac{\sigma_i^2}{\theta}\right),$$
where the water level $\theta$ is set so the budget is exactly spent. The departure from prior compression work is in how we estimate $\sigma_i^2$. Following the side-information logic of Information Masking and Amplification and the cascade side-information results of Permuter et al., we set $\sigma_i^2$ to a monotone function of the frozen decoder's summed surprisal on segment $i$, conditioned on the compressed representation of everything before it. Those papers supply the method in its abstract form: rate is governed by information conditional on what the receiver already holds.
We use the Gaussian form as a working model, not as an assumption we take for granted. Information Bottleneck on General Alphabets shows that single-letter bottleneck characterizations hold rigorously for continuous variables. That makes it legitimate to reason with continuous gist vectors. It does not guarantee that real segments follow this curve, so the first experiment fits these curves directly.
One prior result has to be confronted directly. Data Distribution Matters reports two findings. Reconstruction quality correlates negatively with entropy as measured by the encoder, but not with the decoder's own entropy estimate. At the same time, the decoder's pretrained prior sets the fidelity ceiling: BLEU falls from 80.02 to 64.61 under an encoder domain swap. On its face, the first finding contradicts our choice of the decoder's measurement. We think the two findings separate two quantities: unconditional, domain-level entropy versus per-segment surprisal conditioned on the compressed past, which is the quantity the side-information theorems actually name. This is an empirical bet, not a settled point. An ablation is designed so that it can lose: we allocate once by encoder entropy and once by decoder-conditional surprisal.
Research Program
The system starts from Fine-KV with the autoencoding and token-importance training of the Silver Bullet study. That model is retrained on 3B SlimPajama tokens on Llama-3.2-3B and Llama-3.1-8B, matching that paper's setup. It is trained so that any segment can be compressed into a variable number of gist tokens, $k \in \{0, 16, 32, \dots\}$. Randomizing $k$ during training costs little and is what makes inference-time allocation possible.
At inference, one cheap pass of the frozen decoder over the segment stream gives per-segment conditional surprisal. Each segment is scored conditioned on the gist tokens of its already-compressed predecessors, so the cost stays linear in length. The water level $\theta$ is found by bisection, and the resulting rates are rounded to multiples of the attention kernel's block size. That rounding matters. Dynamic Sparse Flash Attention shows that irregular sparsity loses to dense kernels in wall-clock time. Bottlenecked Transformers shows that rewriting the cache in place costs roughly 20× training time and 45% inference latency. Our output is simply a shorter, contiguous cache, so standard fused kernels run unchanged.
We add one optional channel. When a segment's water-filled rate exceeds a fixed cap, we keep its few highest-surprisal tokens verbatim as raw cache entries. This is the discrete escape hatch suggested by the Gather-and-Aggregate finding: in Llama-3.1-8B, precise retrieval lives in a tiny number of heads that need sharp, unsmoothed tokens, and ablating one such head drops MMLU from 66% to 25%. That paper constrains the design. It warns that smoothing everything into continuous vectors will break exact retrieval no matter how well the budget is split.
The analysis side has two parts. First, for a sample of segments we sweep $k$ and measure downstream loss on probe questions about that segment. This gives per-segment distortion-rate curves, which we fit to the exponential form to test whether $\sigma_i^2$ is predicted by conditional surprisal. Second, we report where the allocation spends its budget, relative to segment boundaries, needle positions, and identifier strings, to connect the gains to the three named failure modes.
Baselines
The naive reference points are two. The first is full attention with FlashAttention, the ceiling. The second is middle truncation to the same cache size as the compressed models, which LongBench shows costs heavily as length grows (a 17% drop for GPT-3.5-Turbo-16k from 0–4k to 8k+ contexts). The strongest existing method is uniform Fine-KV trained with autoencoding plus token-importance estimation, from A Silver Bullet or a Compromise for Full Attention?. That paper reports 50.1 on HELMET at 4× compression, against 46.2 for plain Fine-KV and 55.6 for full attention. On its PopQA-based synthetic recall test it reports 62.1, against 40.6 for plain Fine-KV. It is the strongest competitor because it is the same architecture family with the best reported numbers on exactly our benchmarks, so any gain we show isolates allocation rather than architecture. We will retrain it ourselves on the identical 3B SlimPajama tokens with the same variable-$k$ training, so the only difference at test time is the allocation rule. Total cache tokens are matched exactly, with the same hyperparameter search budget for both. We count it as beaten if our method gives a HELMET gain of at least two points at 4× and a larger gain at 8× and 16×, holds across three seeds, and shows no loss on any HELMET category beyond seed noise.
ComprExIT serves as a second soft-compression competitor on its six-QA suite, where it reports up to an 18.5% average F1 gain over earlier soft compressors. We run it at matched slot budgets, and we also test it with our allocation laid on top, since the two methods are complementary. QUITO-X is the extractive reference. It reports 86.8% on Quoref at 0.25 compression with Llama-3, against 65.5% for LLMLingua2. We run it at matched retained-token counts on Quoref and LongBench.
Four ablations isolate the key ingredient. The first allocates by encoder-measured entropy instead of decoder-conditional surprisal. The second allocates by the learned token-importance scores aggregated per segment. The third allocates proportionally to surprisal rather than by water-filling. The fourth removes the verbatim escape channel.
Why not just…?
Why not just give every segment more gist tokens? Raising the uniform rate certainly helps, but it changes the budget rather than the policy. The question is what to do at a fixed cache size, which is the regime where quadratic cost and memory bind. All our comparisons hold total cache tokens equal. If uniform allocation matched water-filling at equal budget, our claim would be false. We consider this unlikely mainly at high compression, where the Silver Bullet study shows uniform Fine-KV failing.
Why not just reuse the token-importance scores the strongest baseline already learns? This is the most serious threat. Learned importance and decoder surprisal may largely coincide, and if they do, our contribution shrinks to "reallocate by an existing score." The second ablation settles it directly. If importance-based allocation matches surprisal-based allocation, we will report that the gain comes from variable-rate allocation itself and that the side-information estimate adds nothing. If surprisal-based allocation wins, especially on needles the model cannot guess, that supports the side-information reading.
Why not just keep high-surprisal tokens verbatim and drop the rest, as extractive pruning does? Extractive methods keep tokens rather than allocate summary capacity. QUITO-X's own analysis shows that perplexity-driven selection fragments syntax into what it calls the "noun trap." Our escape channel borrows the useful part of this idea, but only for overflow. The fourth ablation and the QUITO-X comparison at matched token counts show whether the continuous gist component is earning its cost.
Why not just use retrieval-augmented generation over chunks? LongBench reports that retrieval hurts models with strong native long-context ability. HELMET shows large gaps on synthesis tasks such as citation generation and re-ranking. We include a BM25 top-$k$ baseline at matched context length on HELMET's retrieval and summarization categories, and we expect it to win only on single-fact lookup.
Proposed Experiments
The main evaluation is HELMET at 4×, 8×, and 16× compression, plus the PopQA needle recall test from the Silver Bullet study. We add LongBench-E length buckets to measure how degradation scales with length, and ComprExIT's six-QA suite (NewsQA, SQuAD, SearchQA, HotpotQA, TriviaQA, Natural Questions). We also build a synthetic test with UUID strings placed at controlled positions to probe the verbatim failure mode. Metrics are task scores as defined by each benchmark, recall accuracy, peak cache memory, and wall-clock prefill and decode latency against FlashAttention.
Four checks decide the proposal. The first is whether per-segment distortion-rate curves are well fit by the exponential form, with fitted scales correlating with decoder-conditional surprisal. If they are not, the water-filling rule is only a heuristic and we will say so. The second is whether decoder-conditional allocation beats encoder-entropy allocation, which answers the tension with Data Distribution Matters. The third is whether gains over uniform Fine-KV grow with the compression ratio and concentrate on surprise and boundary items, as a rate-starvation account predicts. The fourth is whether total latency, including the surprisal pass, stays below full attention at 32k context. If the method improves accuracy but loses on wall-clock time, it falls into the same hardware gap that Bottlenecked Transformers fell into.
References
- A Silver Bullet or a Compromise for Full Attention? A Comprehensive Study of Gist Token-based Context Compression
- In-context Autoencoder for Context Compression in a Large Language Model
- Context Compression via Explicit Information Transmission
- Information masking and amplification: The source coding setting
- Cascade and Triangular Source Coding With Side Information at the First Two Nodes
- Information Bottleneck on General Alphabets
- Data Distribution Matters: A Data-Centric Perspective on Context Compression for Large Language Model
- Fast Attention Over Long Sequences With Dynamic Sparse Flash Attention
- Bottlenecked Transformers: Periodic KV Cache Consolidation for Generalised Reasoning
- Understanding the Skill Gap in Recurrent Language Models: The Role of the Gather-and-Aggregate Mechanism
- LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding
- QUITO-X: A New Perspective on Context Compression from the Information Bottleneck Theory