When a language-model serving system gets a request whose opening tokens were seen before, it reuses the stored intermediate states (the "KV cache") and skips the expensive prefill computation. The time to first token therefore announces whether the request hit or missed the cache — and that announcement is readable by anyone with a stopwatch and a network connection. Attackers have used exactly this signal to reconstruct proprietary system prompts (89% of tokens recovered on average in The Early Bird Catches the Leak), to steal medical queries from real patient conversations in 62% of attempts on the Chatdoctor corpus (InputSnatch: Stealing Input in LLM Services via Timing Side-Channel Attacks), and to fingerprint which providers share caches globally (Auditing Prompt Caching in Language Model APIs). The proposed defenses — disabling cache sharing, padding all responses to worst-case latency — destroy the very throughput gains the cache exists to provide.
This proposal asks whether an algebraic tool from a completely different literature can break this bind: the structured random rotation. A rotation here is a fast, structured orthogonal transform (a randomized Walsh–Hadamard transform, computable in $O(d\log d)$) that mixes all coordinates of a vector so that each output coordinate becomes a roughly identically distributed linear combination of the whole input — erasing coordinate-wise outliers. Applied before quantization, it is what lets QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs quantize a model end-to-end at 4 bits with a negligible perplexity increase of 0.47 on WikiText-2, and what lets TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate quantize vectors with codebooks computed analytically offline, with no calibration data at all. Our claim is that the same transform, used to build the cache lookup key rather than merely the cache storage format, converts the cache's exact-equality oracle into a coarse geometric-neighborhood oracle — collapsing the token-level information that timing attackers depend on — while the dense, fixed-shape arithmetic it enables has input-independent execution time, removing a second, subtler leak at the hardware level.
Core Claim
Today's prefix caches answer a binary question with a noisy channel: "is this exact token string cached?" Each probe leaks one bit about one exact token, which is why token-by-token search recovers entire system prompts. We propose replacing the exact-match key with a rotation-quantized sketch: each KV block is passed through a randomized Hadamard rotation, and the rotated vector is quantized with a fixed, analytically derived scalar codebook (the Lloyd–Max codebook for the Beta-distributed rotated coordinates established by TurboQuant). Two prompts then collide in the cache not when their tokens are identical but when their KV states fall within a quantization radius $\varepsilon$ of each other in rotated space. The timing signal still exists, but it now answers "does some cached block lie near my probe's internal representation?" — a fuzzy, low-information bit per query that does not compose into token-level reconstruction, because near-misses at the token level become genuine cache hits at the sketch level and receive the same fast path.
The second claim is about hardware. Sparse and data-dependent paths in quantization pipelines — the sparse outlier lookups of SqueezeLLM: Dense-and-Sparse Quantization, the layer-sequential predictors of Cache Me If You Must: Adaptive Key-Value Quantization for Large Language Models — execute memory accesses whose addresses depend on the data, and data-dependent memory access is the canonical source of GPU timing channels, sufficient for full AES-128 key recovery in roughly 30 minutes (A Survey of Techniques for Improving Security of GPUs). The rotated pipeline is, by construction, a dense, fixed-operation-count computation on uniformly distributed coordinates. Whether that statistical homogenization translates into physical timing invariance on real GPUs has never been measured; we will measure it.
We must be honest about one limit up front: no representation change removes the compute asymmetry between "reuse cached work" and "run full prefill." A bimodal time-to-first-token distribution will survive. The defense succeeds if it removes the attacker's ability to aim probes, which we measure directly as a drop in prompt-recovery success rates under the strongest published attacks — not merely as a smaller hit/miss timing gap.
Relation to the Closest Existing Work
Two lines border this proposal and must be distinguished from it. Joint Encoding of KV-Cache Blocks for Scalable LLM Serving is the closest: it fuses similar KV blocks via data-dependent cosine-similarity thresholds and explicitly notes that this blurs the prompt-to-cache correspondence, mitigating exact-match timing attacks. But its fusion is itself data-dependent — the comparison depth and fusion pattern vary with the prompt text, plausibly opening a secondary timing channel the authors never audit — and its similarity search requires per-workload evaluation. Our sketch is data-oblivious: the rotation is drawn once, the codebook is fixed offline, and every block takes the same constant-shape arithmetic path regardless of content. QuaRot and TurboQuant supply our machinery but evaluate only perplexity, accuracy, and throughput; neither contains a single timing measurement. Practical Timing Side-Channel Attacks on Memory Compression motivates the hardware question — its Comprezzor fuzzer amplifies residual timing deltas by three orders of magnitude — but studies lossless dictionary compression, not lossy vector quantization.
Research Program
The first workstream builds the sketch cache. Concretely, we modify a vLLM-style serving engine so that the prefix-cache index maps from the current block-hash of token prefixes to a rotation-quantized sketch: apply a randomized Hadamard transform to each key-state block, quantize the rotated coordinates with the analytic Beta-matched Lloyd–Max codebook, and index blocks by their quantized codeword with a radius search for retrieval. The quantization radius $\varepsilon$ is the single security–fidelity knob: larger radii merge more distinct prompts into shared fast paths (less timing distinguishability, more attention error). Because the rotation is orthogonal, attention scores computed on dequantized rotated states are approximations of the exact scores with isotropic, bounded error — the rate–distortion guarantee of TurboQuant (distortion within a factor of roughly 2.7 of the Shannon lower bound) tells us how much accuracy we must spend per bit of collision radius. We will derive the relationship between $\varepsilon$, the number of bits per coordinate, and the per-probe information an attacker obtains, treating the attacker's query as a noisy-ORACLE problem and bounding reconstruction accuracy as a function of query budget.
The second workstream is a microarchitectural timing audit. We instrument three quantization pipelines on identical GPUs (A100 and RTX 3090, matching QuaRot's testbed): a rotated dense 4-bit pipeline (fused Hadamard plus integer GEMM), a sparse-outlier pipeline in the style of SqueezeLLM, and a lookup-table dequantization path. For each, we feed input batches drawn from adversarially different distributions (heavy-tailed activations versus equalized ones, outlier-rich versus outlier-free) and measure per-batch kernel latency distributions. The hypothesis, grounded in the coalescing analysis of A Survey of Techniques for Improving Security of GPUs, is that the rotated dense path shows statistically indistinguishable timing across input distributions while the sparse path does not.
Proposed Experiments
The security evaluation replays the strongest published attacks against the sketch cache on the exact benchmarks they used. On zero_scrolls, The Early Bird Catches the Leak reports a 99% accuracy rate in distinguishing KV-cache hits from misses with a false positive rate of only 0.003; that is the number our defense must attack. We expect the raw hit/miss timing gap to persist but the content recovery to collapse: their Prompt Stealing Attack recovered an average of 89% of targeted system prompts on gabrielchua/system-prompt-leakage, and their Peeping Neighbor Attack reached 95.4% recovery accuracy after just five trials on MedQuAD. Success means driving prompt recovery toward the floor set by blind guessing, at each radius $\varepsilon$ — and we will run the attack with full knowledge of our mechanism (rotation structure, bit-width, radius), including an adaptive attacker who optimizes probes to sit near quantization cell boundaries, since Decomp+Time shows that residual timing deltas of even three orders of magnitude smaller than the original can be amplified by evolutionary search. The InputSnatch Time Analyzer, which achieved 87.13% accuracy in identifying cached prefixes, and its Chatdoctor exfiltration task (62% disease-name theft) provide a second, independently implemented attack pipeline to replicate.
The fidelity evaluation runs on WikiText-2 perplexity and LongBench, with QuaRot (perplexity increase of 0.47 at 4 bits on Llama-2-70B) and TurboQuant (absolute quality neutrality at 3.5 bits per channel, over 4.5x KV-cache compression on Needle-In-A-Haystack and LongBench) as the quality anchors the sketch cache must not degrade beyond. Throughput is measured against an unmodified vLLM baseline, with Joint Encoding's reported ~40% token-throughput gain and 4.38x compression on Qwen2.5-72B as the reference for what cache sharing is worth and therefore what a defense is allowed to cost.
Baselines
The naive reference point is the deployed system doing nothing: an exact-match prefix cache with global sharing, the configuration under which the attacks above achieve their published numbers — 99% hit/miss discrimination on zero_scrolls with a 0.003 false positive rate (The Early Bird Catches the Leak) and 87.13% cached-prefix identification (InputSnatch). This baseline is essential because it quantifies the leakage the field currently accepts; beating it means cutting content-recovery rates, not merely shrinking a timing gap. The strongest existing competitor is the data-dependent fusion cache of Joint Encoding of KV-Cache Blocks for Scalable LLM Serving), which is the only published system that both shares KV state across tenants and claims a timing-mitigation benefit. We will run it on the same models (Llama-3.1 8B and Qwen2.5-72B, as it reports), the same attack scripts, the same GPU allocation, and the same tuning budget of radius/threshold sweeps, and we will additionally audit its fusion-depth timing channel, which its authors never measured. Beating it requires matching its throughput within a small margin while achieving strictly lower prompt-recovery rates under both non-adaptive and adaptive attacks. The key ablation isolates the rotation itself: an unrotated cache sketch that quantizes raw KV coordinates to the same bit-width with a data-fitted codebook, at matched compression and matched compute. If the unrotated sketch defends as well, the rotation is not the active ingredient and the proposal's core claim fails; if the unrotated sketch either leaks (because raw coordinates retain outliers whose quantization is input-dependent) or degrades quality faster as bits shrink, the rotation is doing the work.
Why not just…?
Why not just pad all responses to a fixed rate? The constant-output-rate defense was evaluated directly by Remote Timing Attacks on Efficient Language Model Inference, which found that sending tokens at fixed intervals either inflates user-visible latency or wastes bandwidth on empty padding packets; InputSnatch concurs that timing homogenization negates the performance advantages that motivated caching. Padding also defends the wrong thing in our threat model: it hides when work was skipped but cannot stop the attacker from learning which content is cached, which is what the Prompt Stealing Attack needs. Our experiments will measure both defenses under the identical attack pipeline so the latency-quality-security trade-off is directly comparable, and if padding wins on that trade-off at acceptable latency cost, we will report that honestly.
Why not just disable cross-tenant cache sharing? This is what several providers actually did after responsible disclosure, per Auditing Prompt Caching in Language Model APIs. It works, but it forfeits the entire point: Joint Encoding shows sharing/fusion yields up to 4.38x KV compression and ~40% throughput gains, and The Confinement Problem: 40 Years Later argues that any multiplexed shared system leaks something, so "isolate everything" is a roadmap to no cloud at all. We will include sharing-disabled isolation as a security upper bound and throughput lower bound in every experiment, so the proposal is judged on how much of the gap between the two extremes it captures.
Why not just add random delays or noise? The Early Bird Catches the Leak evaluates noise-injection and batching-threshold strategies and concludes they do not eliminate the side channel and often cost system performance; more decisively, Decomp+Time demonstrates that an evolutionary attacker amplifies residual timing deltas by three orders of magnitude, so any defense that merely shrinks the gap without changing the information content of the oracle is vulnerable to exactly the adaptive attacks we will run. This is a real threat to any fuzzy-match defense too, which is why our headline metric is adaptive-attack recovery rate rather than timing-gap magnitude.
Why not just handle outliers sparsely instead of rotating? SqueezeLLM shows sparse outlier isolation matches accuracy, but it is weight-only quantization, its Fisher-information and k-means calibration scales with model size, and its own authors note sparse kernels are notoriously hard to optimize across architectures. From the security side, irregular sparse memory access is precisely the pattern that induces data-dependent coalescing timing channels per A Survey of Techniques for Improving Security of GPUs; our hardware audit will quantify this contrast directly by timing both pipelines on identical inputs.
Decisive Checks
The proposal stands or falls on three numbers. First, adaptive prompt-recovery rate: from 89% (Early Bird) and 62% disease-name theft (InputSnatch) on the exact-match baseline down toward the guessing floor at each radius, with the attack given full knowledge of the sketch construction. Second, fidelity cost: LongBench and WikiText-2 degradation versus the TurboQuant anchor of neutrality at 3.5 bits per channel — if achieving meaningful protection costs more than roughly a point of LongBench score, the radius knob has too little room and the idea should be abandoned. Third, microarchitectural invariance: kernel timing distributions of the rotated dense path that are statistically indistinguishable across adversarially chosen input distributions, while the sparse path separates — the first direct evidence, on either side, of whether mathematical equalization becomes physical timing uniformity on commodity GPUs.
References
- The Early Bird Catches the Leak: Unveiling Timing Side Channels in LLM Serving Systems
- InputSnatch: Stealing Input in LLM Services via Timing Side-Channel Attacks
- Auditing Prompt Caching in Language Model APIs
- QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs
- TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
- SqueezeLLM: Dense-and-Sparse Quantization
- Cache Me If You Must: Adaptive Key-Value Quantization for Large Language Models
- A Survey of Techniques for Improving Security of GPUs
- Joint Encoding of KV-Cache Blocks for Scalable LLM Serving
- Practical Timing Side-Channel Attacks on Memory Compression
- Remote Timing Attacks on Efficient Language Model Inference
- The Confinement Problem: 40 Years Later