Adaptive sparse attention speeds up long-context language models by reading only the parts of the stored context that matter for the current query. Each piece of that context is kept as a "key-value page," a block of cached keys and values, and the method reads only the pages relevant to the query being answered. That is why it is fast: in decoding, latency is set by how many bytes move from memory, not by arithmetic. It is also why it leaks. The list of pages fetched at each layer and step is a function of the prompt's content. Anyone who can watch memory traffic at page granularity can therefore learn things about the prompt, even if the cached values themselves are encrypted. Examples of such an observer include a host watching key-value pages being pulled from CPU memory over the PCIe bus, or a co-located tenant on the same GPU. They might learn where the answer to a question sits in a document, or which of several retrieved documents was relevant.
Image-encryption research on chaotic ciphers has thought hard about a mirror image of this problem. In that work, keys are deliberately derived from the plaintext ("plaintext-dependent key generation") so that the ciphertext reacts strongly to tiny input changes. The same work also shows that deterministic mappings from input to output can be inverted by an attacker who knows some plaintexts. This proposal borrows that toolkit, both its attack methods and its seeding choices, to answer a concrete systems question. How much of the speedup from adaptive sparse attention survives once its memory access pattern is made leakage-bounded? Wall-clock latency, not operation counts, will be the measure of cost throughout.
Core Claim
A content-dependent sparse selection plays the same role as a plaintext-dependent key, except that it is observable. We claim three things. First, current page-selection methods leak recoverable prompt information through their fetch traces. Second, the leakage can be cut to a chosen bound by fetching "decoy" pages. The decoys must be shaped like real selections and must persist across decoding steps the way real selections do. Third, the decoy seed has to be fresh per session. If it is derived from the content, as the chaotic-cipher literature does, it fails under a realistic workload: a shared long context queried repeatedly with different questions. Decoy fetches cost bandwidth rather than arithmetic, so the price of leakage bound $b$ is roughly the extra bytes moved. We will measure that price directly on real sparse kernels and report where it erases the speedup and where it does not.
Prior Work and Its Roles
The methods we attack and defend are the query-aware decoding systems. QUEST keeps per-page minimum and maximum key values, uses them to bound each page's possible attention score, and loads only the top pages. TidalDecode selects tokens at a few layers and reuses that selection in the layers between them, because adjacent layers attend to nearly the same positions. Twilight varies how many tokens it keeps by thresholding cumulative attention mass, so its trace reveals counts as well as positions. For prefill, SeerAttention learns a gate that outputs 64×64 block masks, and MInference 1.0 builds sparse indices online from a sample of queries. None of these papers considers what their access patterns reveal. Our work is a security-and-cost analysis layered on top of them, not a replacement.
Two observations from these papers motivate the threat. TidalDecode's finding that selected positions persist across layers means an observer gets many correlated looks at the same content-revealing set. QUEST shows that a 1% page budget suffices for passkey retrieval, which means the fetched set is small and sharply concentrated around the answer. That is the worst case for leakage.
The chaotic-cryptography line supplies the attack methods and the seeding hypothesis. One study, Breaking a chaotic image encryption algorithm based on perceptron model, shows that a deterministic chaotic-plus-neural pipeline without input-dependent feedback collapses to an XOR stream breakable from one known plaintext. We read this as a warning that any deterministic map from content to observable output invites known-plaintext attacks. Schemes such as A new image encryption scheme based on coupling map lattices with mixed multi-chaos and A Novel Color Image Encryption Scheme Based on Hyperchaos and Hopfield Chaotic Neural Network bind keys to plaintext statistics and evaluate this with differential sensitivity scores. One such score is the number-of-pixels-change rate (NPCR), reported above 99.61% in the coupled-map-lattice scheme. We adapt that differential test into a leakage metric. Hash-based seeding (Image Security Based on Three-Dimensional Chaotic System and Random Dynamic Selection, Double Verifiable Lossless Secret Sharing Based on Hyper-chaos Generated Random Grid) is the design we test as a decoy seed, and we predict it fails.
The latency literature constrains the defense. ShuffleNet V2 and Searching for Fast Model Families on Datacenter Accelerators show that memory traffic and fragmentation, not operation counts, decide speed. Polyline Path Masked Attention shows a linear-complexity attention that runs slower than dense attention when it is not fused into a single GPU kernel. Overcoming the Selection Bottleneck in Sparse Attention argues that selection overhead can cancel sparsity gains. Together these rule out defenses that add irregular gathers or extra kernel launches. Decoys must therefore be whole pages, merged into the same fetch list, and served by the existing kernel.
Research Program
Threat model. The adversary observes, for each request, the sequence of fetched page indices for each layer and decoding step. It does not see the page contents. It knows the model and the selection algorithm and can run chosen prompts offline. This "trace adversary" fits two settings: key-value offload to CPU memory, where page transfers cross an observable bus, and confidential-GPU deployments where the host schedules memory.
Measuring leakage. We use two complementary measures.
The first is attacker accuracy. Probes trained on traces try to recover three targets. The first target is the needle's position, binned into deciles, on needle-in-a-haystack tasks. The second is which document among several is relevant, on LongBench multi-document QA (LongBench). The third is the task family on RULER (RULER). We report attacker advantage over chance, converted to bits.
The second is a differential trace-sensitivity score modeled on NPCR. Edit one token of the prompt and measure the fraction of fetched pages that change:
$$S = \mathbb{E}\left[\frac{|P(x) \,\triangle\, P(x')|}{|P(x)|}\right],$$
Here $P(x)$ is the set of fetched pages for prompt $x$, $x'$ is $x$ with one token edited, and $\triangle$ is the symmetric difference. A high $S$ is desirable for a cipher's output. For a fetch trace it means the trace tracks content finely, so a high $S$ signals leakage.
Defense. We call the defense mimicry decoys. At each selection point, besides the $K$ real pages, the system fetches $c$ fake clusters. Each fake cluster copies the shape of a real selection: the same number of contiguous pages, the same attention-sink and recent-window pages, placed at random offsets. The aim is that an observer sees $c+1$ equally plausible clusters. In the ideal case this caps position leakage at roughly $\log_2(\text{bins}) - \log_2(c+1)$ bits, since the attacker can only guess uniformly among identical-looking clusters.
Real selections persist across steps and layers, as TidalDecode documents. Fake clusters must therefore also persist for the whole session. Otherwise intersecting traces across steps strips them away. Decoy values are fetched but masked out of the attention computation, so model outputs are unchanged by construction. The cost is pure bandwidth, approximately
$$T \approx T_{\text{sel}} + (K + cK)\,\frac{B}{W},$$
where $T_{\text{sel}}$ is selection time, $B$ is bytes per page, and $W$ is achieved memory bandwidth. This form assumes decoding is memory-bound, and we will check that against profiles.
Seeding variants. Fake-cluster positions come from one of two seeds. One is a fresh per-session random seed. The other is a seed hashed from the prompt content, following the chaotic-cipher practice. The prediction is specific. Suppose the same long context is queried with different questions, as in multi-turn chat or retrieval-augmented generation. The content-hashed seed then changes with each question, while the real cluster for shared facts stays put. Intersecting the traces recovers the real cluster. The per-session seed keeps the decoys fixed across turns and resists this attack.
Baselines
Dense attention (the do-nothing reference). We run dense attention with FlashAttention-style kernels on the same model and GPU. Its trace is content-independent, so leakage is zero by construction, and it sets the latency floor every sparse method must beat. A defended sparse method beats it only if its end-to-end decode latency is lower at matched accuracy.
Undefended QUEST. This is the strongest existing method on the speed side. QUEST reports a 7.03× self-attention kernel speedup and a 2.23× end-to-end decoding latency reduction at 32k context on top of 4-bit AWQ quantization, and 100% passkey accuracy at a 1% token budget. TidalDecode reports a further 1.2× over QUEST and 2.1× over FlashInfer, so we include it as a second undefended reference. Both run with their released kernels on Llama-family models at the same contexts (32k and 100k), same quantization, and same token budgets, with no retuning advantage for our variants. Defended QUEST "wins" if it keeps at least half of QUEST's end-to-end speedup over dense while cutting attacker advantage to within a preset margin of chance. We have found no leakage result on Lacuna for access-pattern leakage of QUEST, TidalDecode, SeerAttention, or MInference, so establishing those undefended numbers is itself our first result.
Static sparsity. A sink-plus-sliding-window pattern of matched budget leaks nothing about content, because its pattern does not depend on the prompt. MInference reports that such static patterns (StreamingLLM) fail needle retrieval, so this baseline shows the accuracy price of zero leakage without decoys.
Ablations. Three ablations isolate the key ingredient. The first replaces mimicry decoys with an equal number of uniformly random decoy pages, which tests whether decoy shape matters. The second regenerates decoys every step instead of keeping them for the session, which tests whether persistence matters. The third swaps the fresh seed for the content-hashed seed. All three use identical page budgets, so latency is matched and only leakage differs.
Why not just…?
Why not just encrypt the key-value cache? Encryption hides what is in a page, not which page is read. Every attack here uses only page indices, so encrypted contents leave attacker advantage unchanged. We will confirm this by running the probes on traces from an encrypted-at-rest configuration and showing identical attacker accuracy.
Why not just pad every request to a fixed budget? QUEST already uses a fixed top-K, which hides counts but not positions. Fixed-size padding fixes Twilight-style count leakage only. The position probes will measure what remains, and we expect it to be most of the leakage.
Why not just add uniform random decoys? This is the real threat to the proposal. If uniform decoys turn out nearly as good as mimicry decoys, the design reduces to a trivial trick. We expect them to fail. Real selections are contiguous and persistent, so scattered single pages are easy to filter out. The matched-budget ablation settles the question directly. If uniform decoys come within noise of mimicry decoys, we will report that and recommend the simpler scheme.
Why not just use static sparse patterns or dense attention when privacy matters? These are the two endpoints of the trade-off. The question is whether anything useful lies between them. If the measured decoy cost pushes defended QUEST's latency to within 10% of dense, the honest conclusion is that adaptive sparsity cannot coexist with this threat model. That negative result would still be worth publishing.
Why not seed decoys from the content, as chaotic ciphers do? A content seed gives reproducible traces without storing any per-session state. The multi-question experiment below tests the predicted cross-query intersection failure. If the content seed survives that test, it becomes the preferred design.
Proposed Experiments
The experiments run on Llama-3-8B-class models, matching the cited systems, on RTX 4090 and A100 GPUs, using QUEST's and TidalDecode's decode kernels and SeerAttention's block-sparse prefill kernel.
Undefended leakage. On passkey and needle tasks at 10k, 32k, and 100k context, on LongBench multi-document QA, and on RULER, we train trace probes and compute the sensitivity score $S$ for each undefended method. If needle-position probes reach high accuracy from page traces alone, the side channel is real.
Leakage–latency frontier. We sweep decoy multiplicity $c$ from 0 to 8 and plot attacker advantage against measured end-to-end decode latency, not operation counts. We also profile achieved bandwidth to test whether the linear cost model holds or whether larger fetch lists hit kernel-scheduling effects of the kind the Polyline Path Masked Attention paper documents. Accuracy should match the undefended method exactly, since decoys are masked out. We will verify this on RULER and LongBench as a correctness check on the implementation.
Multi-question seeding test. We use 200 long contexts, each queried with 5 different questions. An intersection attacker is run against fresh-per-session and content-hashed decoys. The prediction is that the content-hashed seed's advantage climbs toward the undefended level as the number of questions grows, while the per-session seed's advantage stays flat.
Prefill. We repeat the frontier for SeerAttention's block masks at 64k and 128k. Here the computation is closer to compute-bound, so decoy blocks cost arithmetic as well as bandwidth, and the frontier should be steeper. This test checks whether the conclusions depend on decoding being memory-bound.
The project's outcome rests on one number: the fraction of the reported 2.23× end-to-end speedup that survives at a leakage bound of one bit on needle position.
References
- QUEST: Query-Aware Sparsity for Efficient Long-Context LLM Inference
- TidalDecode: Fast and Accurate LLM Decoding with Position Persistent Sparse Attention
- Twilight: Adaptive Attention Sparsity with Hierarchical Top-$p$ Pruning
- SeerAttention: Learning Intrinsic Sparse Attention in Your LLMs
- MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention
- Breaking a chaotic image encryption algorithm based on perceptron model
- A new image encryption scheme based on coupling map lattices with mixed multi-chaos
- A Novel Color Image Encryption Scheme Based on Hyperchaos and Hopfield Chaotic Neural Network
- Image Security Based on Three-Dimensional Chaotic System and Random Dynamic Selection
- Double Verifiable Lossless Secret Sharing Based on Hyper-chaos Generated Random Grid
- ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design
- Searching for Fast Model Families on Datacenter Accelerators
- Polyline Path Masked Attention for Vision Transformer
- LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding
- RULER: What’s the Real Context Size of Your Long-Context Language Models?