Oblivious KV Cache Compaction for Encrypted LLM Decoding

When a language model runs on encrypted input, the server never sees the user's text, but every step costs orders of magnitude more than plaintext. Long private documents make this worse. Examples include a patient record, a contract, or a codebase. During generation the model repeatedly reads its KV cache, the stored keys and values of all earlier tokens that attention looks back over. Under homomorphic encryption (HE), which lets a server compute on ciphertexts without decrypting them, that cache is a growing pile of large ciphertexts. Every new token pays encrypted multiplications, approximations of the softmax, and rotations proportional to its length.

In plaintext, closed-form methods shrink a cache by up to 50× in seconds. They do this by picking representative keys and fitting a small correction so that attention outputs are preserved. Those methods need to see the cache, and an encrypted server cannot. We propose a compaction scheme the server can apply without seeing anything. The cache is merged in fixed-size blocks, so the merge is a fixed, data-independent linear map. Each merged key carries an encrypted "attention mass" factor that restores how much weight the block would have received. The only division involved is delegated to the client in one small blinded round of O(n/b) numbers.

Core Claim

The mass-correction idea from Fast KV Compaction via Attention Matching can be moved into the encrypted domain without its data-dependent parts. That paper does three things per context: it selects keys by orthogonal matching pursuit or importance scores, fits a per-key bias by non-negative least squares so that total attention mass is matched, and fits values by ordinary least squares. It reaches up to 50× compaction, and 200× when combined with text summarization.

Selection and least-squares solves are deep, comparison-heavy circuits under HE. Data-dependent selection would also tell the server which positions matter. We keep only the mass-matching principle and make the rest oblivious. Write attention as a normalized weighted sum $o(q)=\sum_i f(q\cdot k_i)v_i / \sum_i f(q\cdot k_i)$, where $f$ is the model's (polynomial) score function, $q$ the query, and $k_i, v_i$ the cached keys and values. For a block $B$ of $b$ consecutive tokens we store one key, one value and one mass:

$$\bar k_B=\tfrac{1}{b}\sum_{i\in B}k_i,\qquad \bar v_B=\frac{\sum_{i\in B}w_i v_i}{\sum_{i\in B}w_i},\qquad m_B=\frac{\sum_{i\in B}w_i}{\bar w_B},$$

Here $w_i$ is the attention weight token $i$ received from the prompt's own queries. That quantity is already computed during encrypted prefill and only needs to be added up. $\bar w_B$ is the weight the merged key receives from those same reference queries. At decode time the model uses $m_B f(q\cdot\bar k_B)$ in both numerator and denominator.

The block structure is fixed, so the whole merge is additions, plaintext scalings and a logarithmic number of rotate-and-add steps. None of it depends on the data, and the server learns nothing new. The two divisions are delegated to the client, which owns the secret key. The server multiplies each block total by a fresh random blind, the client decrypts and inverts it, then re-encrypts, and the server removes the blind. This is the same multiplicative-blinding pattern Popcorn uses for ReLU. Because the blinds are per block, the client learns nothing about the server's model either.

Per-token decode attention then scales with $n/b+w$ instead of $n$, where $w$ is a small uncompressed recent window. The claim to test is that at 8–16× compaction the mass factor keeps long-context accuracy close to the full encrypted cache, while plain pooling and truncation fall well short.

Why this intersection, and what prior work contributes

The systems literature on computing over compressed data frames the design rule. Compressed Linear Algebra and Tuple-oriented Compression get their speedups because the cost of the operation scales with the number of distinct compressed symbols rather than raw rows. Compression that does not shrink the dominant cost buys little. HEQuant shows the encrypted version of this failure. Quantizing below 4 bits stops saving communication because the ring dimension and modulus are fixed by security, not by data width. That is a negative result that constrains us: shrinking the cache helps only if encrypted attention, rather than the weight-heavy linear layers, is a large share of decode time. Our first experiment checks exactly that.

The encrypted-LLM systems motivate the gap. Sylph, the CKKS implementation of Llama, evaluates a 128-token encrypted prompt at 18 s/token for generation. With a 4096-token context of which only the last 128 tokens are encrypted, it takes 22 s/token. It keeps long contexts affordable by making most of the prompt public, and it does not compact the cache. That workaround is unavailable when the whole document is private. PowerSoftmax supplies HE-friendly polynomial attention at up to 1.4B parameters but did not evaluate autoregressive long-context decoding. Primer and THE-X handle encoders and short inputs.

The closest encrypted work is the dynamic sparse attention approach to HE LLMs. It selects the top-$k$ keys per query, cutting attention cost from $O(n^2)$ to $O(nk)$. That approach needs encrypted comparisons every step, keeps the full cache in memory, and leaves its cryptographic parameters unspecified. We instead shrink the stored cache once, with no encrypted comparisons.

CSSC sparse matrix-vector multiplication and CryptoGCN show how much layout-aware packing pays under HE. Both obtain it by revealing structure in plaintext: column indices in one case, the adjacency matrix in the other. Our fixed blocks are chosen specifically to avoid that kind of leakage.

Research Program

We build three things.

The first is a plaintext emulator of the method. It runs the polynomial score function, applies CKKS-like precision limits, and computes block merges and mass factors. With it we can sweep block size $b$, window $w$, and whether masses are computed from all prompt queries or a subsampled set, at plaintext speed.

The second is an encrypted implementation on a CKKS GPU stack. Merging is fused into the tokens-first packing layout that Primer advocates, so that block sums become short rotate-and-add trees. The client round carries $n/b$ blinded totals per head per layer, densely packed, and adds one round trip per compaction event. Compaction runs once after prefill and again every $b$ generated tokens.

The third is a noise and depth accounting. The mass multiply adds one ciphertext-ciphertext multiplication per block at decode, and client-returned reciprocals are fresh ciphertexts. We will report whether compaction ever forces an extra bootstrapping, the costly noise-reset step, per token. If it does, that erodes the gain.

Baselines

The naive reference point is full-cache encrypted decoding with the same model and packing, doing no compaction. Every speedup and accuracy delta is measured against it. The strongest published system number is Sylph's 18–22 s/token on multi-GPU hardware. That figure is for only 128 encrypted tokens, and there is no reported result found on Lacuna for fully encrypted contexts of thousands of tokens. We will therefore report our own full-cache curve over context length on identical hardware rather than compare across setups.

The strongest compaction method is Attention Matching itself. It reports up to 50× compaction in seconds to minutes. There is no reported result found on Lacuna for its per-task accuracy on QuALITY or LongHealth, so we rerun it in plaintext on the same model and benchmarks. It is best understood as the quality ceiling a client-aided "decrypt and compact exactly" protocol could reach. We also run it inside the encrypted pipeline in that client-aided form and measure the full bandwidth it needs. Beating it means matching its accuracy within a small margin at equal compaction ratio, at a fraction of its communication, and without exposing the cache to the client.

A recency-window baseline keeps only the last $n/b+w$ tokens at matched memory. It is the zero-computation competitor. A dynamic top-$k$ baseline in the style of the sparse-attention HE paper uses the same $k=n/b+w$, so cost is matched.

The key ablation is identical block merging with the mass factor removed ($m_B=1$) and with uniform instead of mass-weighted values. This isolates whether the imported mass-matching ingredient is what carries the quality. All methods share the model, prompts, tuning budget over $b$ and $w$ (chosen on a held-out split), and hardware.

Why not just…?

Why not just compress the document on the client before encrypting it? This is the most serious threat. The client holds the plaintext and could summarize or prune it locally, and Attention Matching's own 200× figure comes from stacking summarization with compaction. The limitations are that this requires a capable local model, which weakens the case for outsourcing, and that summarization is blind to the later question. The approaches are also complementary rather than exclusive. We will compare client-side summarization to our compaction at matched encrypted token counts on LongHealth and QuALITY, and then stack them. If summarization alone matches our accuracy at equal cost, the contribution shrinks to the stacked regime, and we will report that plainly.

Why not just drop old tokens with a sliding window? It costs nothing and leaks nothing. However, benchmarks such as LongHealth (60k-token clinical records) and RULER place evidence far from the query. The recency baseline measures directly how much accuracy is lost when old context is discarded rather than summarized into blocks.

Why not let the client decrypt the cache and run exact Attention Matching? It gives the best quality. The cost is shipping the full cache, all layers, heads and tokens, in both directions each compaction event. It also hands the client activations derived from the server's weights. Our protocol sends $n/b$ blinded scalars per head per layer instead. We measure both bandwidths and quality, so the trade-off is explicit rather than asserted.

Why not just make most of the prompt public, as Sylph does? For documents that are private end to end there is no public part. This option applies to a different threat model.

Proposed Experiments

The first decisive check is a profiling one. For a PowerSoftmax-style polynomial model at 1B scale, and a Llama-family model where feasible, we measure what fraction of encrypted decode time goes to attention as the fully encrypted context grows from 512 to 8k tokens. If attention stays a minor share across that range, cache compaction cannot matter much, and we stop and report the crossover length instead.

Second, in the plaintext emulator we evaluate QuALITY, LongHealth, QASPER and RULER, the long-context suite used by Attention Matching. We compare full cache, window, top-$k$, uniform pooling, mass-corrected blocks, exact Attention Matching and client summarization at 4×, 8×, 16× and 32× compaction. The prediction is that mass correction closes most of the gap between uniform pooling and exact Attention Matching, and that the gain grows with compaction ratio.

Third, encrypted end-to-end runs at the context lengths where profiling showed attention matters report four quantities: seconds per generated token, peak ciphertext memory, client–server bytes per compaction, and bootstrapping count per token, all against the full-cache run.

Success means an 8× or larger compaction with task accuracy within a few points of the full encrypted cache. It also requires a per-token latency reduction that tracks the measured attention share, at a client round measured in megabytes rather than the cache size. Failure on the ablation, meaning mass correction does no better than uniform pooling, would falsify the core claim.