CompilerKV: Risk-Adaptive KV Compression via Offline Experience Compilation Ning Yang, Chengzhi Wang, Yibo Liu, Baoliang Tian, Haijun Zhang Abstract Large Language Models (LLMs) in long-context scenarios are severely constrained by the linear growth of Key-Value (KV) cache memory. Existing KV compression methods rely either on static thresholds and attention-only heuristics or on coarse memory budget allocation. Under tight memory budgets, these methods overlook two key factors: prompt-dependent variation in compression risk and functional heterogeneity across attention heads, which destabilize token selection and lead to tail failures. To address these challenges, we propose CompilerKV, a risk-adaptive and head-aware compression framework that compiles offline experience into reusable decision tables for prefill-only deployment. CompilerKV integrates two key synergistic components: (i) a Head Heterogeneity Table, learned via offline contextual bandits, which assigns head-specific reliability weights to govern functional differences across attention heads explicitly; and (ii) a Risk-Adaptive Threshold Gating mechanism that jointly models attention entropy and local perplexity, transforming prompt-level risk into deployable retention thresholds. Experiments on LongBench show CompilerKV dominates SOTA methods under a 512-token budget, recovering 97.7% of FullKV performance while achieving up to +5.2 points gain over the strongest competitor. Code and demo are available at https://github.com/luckypiggy-orangejuice/CompilerKV . 1 Introduction The capability of Large Language Models (LLMs) to process extensive contexts has revolutionized applications ranging from document summarization to multi-hop reasoning ( 17 ; 1 ) . To accelerate inference, LLMs maintain a Key-Value (KV) cache that stores intermediate attention states to avoid re-computation. However, this proficiency comes at a prohibitive computational cost: the memory footprint of the KV cache grows linearly with sequence length ( 2 ) . For a 7B model processing a 128k context, the KV cache can consume over 100GB of memory, far exceeding the capacity of standard GPUs and creating a severe bottleneck for deployment ( 21 ; 27 ) . To alleviate this memory pressure, KV cache compression has emerged as a critical research direction. Early approaches adopted static sparsity patterns, such as sliding windows ( 4 ) or fixed attention sinks ( 28 ) , assuming that recent tokens and initial tokens suffice for generation. Recognizing the limitations of static retention, subsequent research evolved towards dynamic importance estimation. Methods like Heavy-Hitter Oracle (H2O) ( 30 ) retain tokens with high accumulated attention scores. More recently, budget-aware strategies such as SnapKV ( 16 ) and PyramidKV ( 3 ) have introduced structural priors to allocate memory budgets across layers, attempting to balance local precision with global context. Despite these advances, current KV compression methods exhibit two fundamental limitations, especially in prefill-only settings under tight memory budgets. First, most approaches employ prompt-agnostic, one-size-fits-all policies that apply a global compression rate regardless of semantic complexity ( 32 ) . Under strict budgets, this leads to tail failures, where high-entropy prompts suffer severe information loss while low-entropy prompts retain redundant tokens. Second, token eviction decisions are often unstable because they rely on weakly conditioned, instantaneous attention statistics. Such signals are inherently noisy and affected by scale bias, where large magnitudes do not necessarily correspond to semantic importance. Without mechanisms to separate reliable signals from noise, small estimation errors can shift selection boundaries and irreversibly remove critical context. Motivated by the instability of prompt-agnostic and weakly conditioned compression strategies, we frame prefill-only KV compression as an irreversible one-shot decision under tight memory budgets. Since decisions are fixed before decoding, unstable token selection can permanently discard critical context and trigger tail failures. This perspective motivates a shift from reactive pruning to a compile-time decision paradigm, embodied by CompilerKV . Our contributions can be summarized as follows: • A novel prefill-only KV cache compression framework, CompilerKV, has been proposed, which compiles offline compression experience into reusable decision tables. By jointly modeling prompt-level risk and head heterogeneity, it transforms noisy importance signals into stable decisions, injecting stabilization priors at prefill to enable robust compression without online adaptation. • We reframe prefill-only KV compression as an irreversible one-shot decision problem under tight memory budgets and substantiate this paradigm by deriving an attention approximation error bound (Theorem 4.1 ), theoretically explaining how our head-aware strategy mitigates tail failures under strict memory constraints. • Experimental results on LongBench across 16 datasets and 4 LLM backbones show that CompilerKV consistently outperforms state-of-the-art baselines under strict budgets. Under a strict 512-token budget, it recovers over 97% of FullKV performance and surpasses the strongest competitor by up to 5.2 on complex summarization. 2 Related Work Token Importance Estimation for Prefill-only Compression. KV compression has evolved from static sparsity patterns ( 4 ; 22 ) to dynamic importance estimation. To retain critical historical states, accumulation-based methods such as H2O ( 30 ) and StreamingLLM ( 28 ) identify heavy-hitter tokens that consistently attract high attention scores. In the specific context of prefill-only compression, SnapKV ( 16 ) adapts this by utilizing an observation window at the end of the prompt to predict future relevance, performing one-shot pruning before generation begins. Recent efforts such as Value-Aware Token Pruning (VATP) ( 12 ) attempt to refine utility estimation by incorporating the absolute L_{2} -norm of value vectors alongside attention probabilities. However, a direct application of these metrics often leads to tail failures, where generation collapses due to the irreversible loss of a few key tokens. This necessitates a more robust utility metric that decouples usage frequency from information density and calibrates signal scales within each sample. Functional Heterogeneity of Attention Heads. Beyond token-level metrics, recent studies highlight functional heterogeneity, showing that a few retrieval heads drive long-context capabilities ( 9 ; 8 ) demonstrating that a small subset of retrieval heads dominates long-context capabilities. While approaches such as ZigZagKV ( 31 ) attempt to exploit this by calculating head-specific importance scores during the prefill phase, they typically overlook the critical reliability gap between heads. This limitation is further supported by prior work ( 26 ) , which shows that attention heads in LLMs exhibit strong functional heterogeneity and that many heads are redundant or noisy. These noisy attention heads can interfere with the recognition of key tokens, especially under high compression ratios ( 6 ) . Furthermore, many existing head-aware strategies ( 30 ; 19 ) rely on online feedback during decoding or necessitate complex alterations to the KV cache layout, rendering them unsuitable for efficient, zero-overhead deployment in strictly prefill-only compression scenarios. Risk-Adaptive Budgeting and Threshold Gating. Complementary to importance scoring and head heterogeneity, effective KV compression also depends on how memory budgets are allocated. Methods such as PyramidKV ( 3 ) assign larger budgets to lower layers and smaller ones to higher layers, while DynamicKV ( 32 ) introduces task-aware budget shaping. Although these strategies improve coarse budget utilization, they largely assume similar compressibility across prompts, which limits robustness under heterogeneous inputs ( 23 ) . Recent work has begun to incorporate statistical signals into caching decisions. Entropy-based approaches ( 24 ) leverage attention distributions to assess structural concentration, but often miss semantically sensitive samples with deceptively concentrated patterns. Conversely, KVPruner ( 20 ) shows that perplexity, as a measure of predictive uncertainty, provides a complementary semantic signal. We propose a Risk-Adaptive Threshold Gating mechanism that jointly models attention entropy and local perplexity, enabling robust threshold calibration for both structurally diffuse and semantically complex prompts. 3 Preliminaries 3.1 KV Caching in LLMs LLMs are typically built upon the Transformer architecture, utilizing the Multi-Head Self-Attention (MHSA) mechanism ( 25 ) . Given an input sequence of length T , for each token at step t , the model projects its embedding into query q_{t}^{(l,h)} , key k_{t}^{(l,h)} , and value v_{t}^{(l,h)} vectors for the l -th layer ( l\in\{1,\dots,L\} ) and h -th head ( h\in\{1,\dots,H\} ). To accelerate autoregressive decoding, modern systems maintain a KV Cache to store historical states. For the l -th layer at step t , this cache is denoted as (K,V) , comprising all preceding keys and values: K^{(l)}=[k_{1}^{(l)},\dots,k_{t}^{(l)}] , V^{(l)}=[v_{1}^{(l)},\dots,v_{t}^{(l)}] . The attention mechanism relies on the attention weight A_{j,t}^{(l,h)} , which represents the relevance of the historical token at position j to the current query at position t : A_{j,t}^{(l,h)}=\frac{\exp\left((q_{t}^{(l,h)})^{\top}k_{j}^{(l,h)}/\sqrt{d_{head}}\right)}{\sum_{i=1}^{t}\exp\left((q_{t}^{(l,h)})^{\top}k_{i}^{(l,h)}/\sqrt{d_{head}}\right)}, (1) where d_{head} is the dimension of each head and \sum_{j=1}^{t}\!\!A_{j,t}^{(l,h)}\!\!=\!\!1 . As the sequence length T increases, the memory footprint of storing (K^{(l)},V^{(l)}) grows linearly with T , posing a challenge for efficient long-context inference. 3.2 Offline Reinforcement Learning We frame the compilation of compression policies as an offline reinforcement learning (RL) problem. Since prefill compression is a one-shot decision without state transitions, we model the problem as a Contextual Bandit, i.e., a single-step Markov Decision Process (MDP). Let s\in\mathcal{S} denote a context observed at prefill time, a\in\mathcal{A} as discrete compression action, and r(s,a)\in\mathbb{R} as scalar reward reflecting the compression quality. Given a fixed offline dataset \mathcal{D}=\{(s_{i},a_{i},r_{i})\}_{i=1}^{N} collected under a behavior policy, the goal is to learn a value function Q_{\phi}(s,a) that estimates the expected reward of each action under a given context. Unified Reward Structure. To govern head reliability and risk thresholds, we define a unified reward function that balances compression fidelity and task-specific constraints: r(s,a)=-(\mathcal{L}_{\text{comp}}(s,a)-\mathcal{L}_{\text{full}}(s))-\lambda\cdot\Psi(s,a), (2) where \Psi(s,a) is the task-specific penalty (e.g., budget violation), \mathcal{L}_{\text{full}}(s) is the baseline loss, and \mathcal{L}_{\text{comp}}(s,a) is the Negative Log-Likelihood (NLL) of the compressed model over a window \Omega : \mathcal{L}_{\text{comp}}(s,a)=-\frac{1}{|\Omega|}\sum_{t\in\Omega}\log P(x_{t}\mid x_{0 ). Let \lambda=\frac{\beta}{T} , where \beta is a hyperparameter. The constraint term is defined as the deviation from the target budget: \Psi(s,a)=\left||\mathcal{I}_{\text{cand}}(a)|-B_{l}\right|, (14) where \mathcal{I}_{\text{cand}}(a) is the set of tokens retained by threshold a . This encourages the policy to find the strictness threshold that maximizes fidelity without violently violating the layer-wise budget B_{l} . Final Selection: Gating with Budget Correction. The final selection set \mathcal{S}^{(l)} is determined by a Threshold Gating and Top- B_{l} Correction strategy. First, we generate a candidate set based on the adaptive threshold: \mathcal{I}_{\text{cand}}^{(l)}=\{t\mid\hat{u}_{t}^{(l)}\geq\tau^{(l)}\}. (15) To strictly enforce the hardware storage budget B_{l} , we apply a correction step: \mathcal{S}^{(l)}=\begin{cases}\mathcal{I}_{\text{cand}}^{(l)},&\text{if }|\mathcal{I}_{\text{cand}}^{(l)}|\leq B_{l},\\ \text{Top-}B_{l}(\mathcal{I}_{cand}^{(l)},\hat{u}_{t}^{(l)}),&\text{if }|\mathcal{I}_{cand}^{(l)}|>B_{l},\end{cases} (16) where \text{Top-}B_{l}(\mathcal{I},u) denotes the subset of B_{l} indices from \mathcal{I} corresponding to the largest values in the score u . The first condition permits elastic retention for low-risk prompts where the adaptive threshold naturally filters out enough redundancy ( |\mathcal{I}_{\text{cand}}^{(l)}|\leq B_{l} ). The second condition acts as a hard clamp, prioritizing the highest-utility tokens to maximize information density when the risk-aware policy admits an excess of candidates. KV Cache Construction. The prefill phase processes an input prompt of length T and generates the complete KV cache (K^{(l)},V^{(l)}) for each layer l . Upon determining the optimal indices \mathcal{S}^{(l)} , the final compressed KV cache (\tilde{K}^{(l)},\tilde{V}^{(l)}) is constructed by gathering the vectors corresponding to the selected indices: \tilde{K}^{(l)}=K^{(l)}[\mathcal{S}^{(l)}],\quad\tilde{V}^{(l)}=V^{(l)}[\mathcal{S}^{(l)}], (17) where K^{(l)}[\mathcal{S}^{(l)}] signifies the projection of the full Key cache onto the selected index set, effectively retaining only the feature vectors required for the compressed representation. This selection and construction process is performed once at the end of the prefill phase (step T ). During the subsequent autoregressive decoding, the retained cache (\tilde{K}^{(l)},\tilde{V}^{(l)}) remains static, prohibiting any further updates or evictions. This “compile-then-execute” paradigm ensures that the overhead of our complex selection logic is amortized to zero during generation. 4.5 Theoretical Analysis To provide insight into the stability of CompilerKV under extreme compression, we derive a stability-oriented bound on the approximation error of the attention output. Theorem 4.1 (Stability-Oriented Attention Approximation Bound) . Consider a transformer layer l with input sequence length T and budget B_{l} . Let A^{(l,h)} and \tilde{A}^{(l,h)} denote the full and compressed attention matrices, respectively. Under CompilerKV’s selection policy determined by the stabilized utility \hat{u}_{t}^{(l)} and the head reliability table W_{\text{head}} , with probability at least 1-\delta , the layer-wise aggregated approximation error satisfies: \displaystyle\frac{1}{H}\sum_{h=1}^{H}\left\|A^{(l,h)}-\tilde{A}^{(l,h)}\right\|_{F} (18) \displaystyle\leq \displaystyle\sqrt{T}\cdot\epsilon_{\text{tail}}^{(l)}+\mathcal{O}\!\left(\sqrt{\frac{(T-B_{l})\log(1/\delta)}{T\cdot(W_{\min}^{(l)})^{2}}}\right), where \epsilon_{\text{tail}}^{(l)} denotes the average attention mass of discarded tokens, and W_{\min}^{(l)} is the minimum reliability weight assigned to any head in layer l . The bound shows that worst-case approximation error is dominated by discarded tail mass and is inversely controlled by head reliability weighting, explaining how stabilized, head-aware selection reduces sensitivity to noisy importance signals under irreversible prefill-only compression. The proof of Theorem 4.1 is shown in Appendix A . Table 1 : Main Results on LongBench (Budget = 512 Tokens). Comparisons with state-of-the-art compression methods across four LLMs. The best result among compression methods is bolded , and the second best is underlined . Single-Doc QA Multi-Doc QA Summarization Few-Shot Learning Synthetic & Code Model Method NarrativeQA Qasper MF-en HotpotQA 2WikiMQA MuSiQue GovReport QMSum MultiNews TREC TriviaQA SAMSum Lcc RB-P Pcount PRe Avg. InternLM-2.5 7B-Chat-1M FullKV 22.47 27.58 39.98 40.96 33.52 26.61 33.01 25.18 26.28 72.5 86.76 39.84 55.86 57.90 2.92 100 43.21 StreamingKV 17.58 15.86 26.55 26.68 16.69 11.01 25.96 21.33 25.57 65.0 67.16 21.71 43.58 42.76 0.95 87.56 32.25 H2O 15.33 19.84 32.67 27.96 19.94 21.18 16.91 23.00 21.46 42.0 84.38 34.76 48.46 50.00 1.23 96.50 34.73 SnapKV 16.86 23.28 36.24 32.14 19.89 23.21 17.81 23.18 22.44 71.0 84.05 34.34 50.32 53.34 1.00 96.50 37.85 PyramidKV 17.62 21.08 37.52 32.21 21.31 22.03 19.37 24.06 22.22 73.0 83.94 34.61 50.45 49.72 1.05 95.50 37.86 ZigZagKV 17.28 22.07 36.94 32.18 20.67 22.56 18.67 23.66 22.32 72.0 83.99 34.49 50.39 51.35 1.03 95.95 37.93 DynamicKV 17.77 23.87 37.74 32.98 21.13 23.21 19.13 23.49 22.48 75.0 84.89 36.70 50.70 51.08 0.91 95.50 38.54 Ours 18.47 24.22 38.37 33.49 21.25 23.05 24.41 24.05 23.68 75.0 84.31 36.11 51.16 52.88 1.00 95.50 39.18 LLaMA-3 8B-Instruct FullKV 25.16 31.81 39.59 43.09 36.15 21.77 28.62 23.34 26.33 75.0 90.50 42.36 59.04 53.93 5.20 69.25 41.95 StreamingKV 19.03 12.78 28.67 37.83 29.97 16.55 20.30 20.94 24.56 61.0 75.43 30.82 51.93 49.98 5.86 69.50 34.70 H2O 22.84 16.80 32.36 41.50 34.07 19.33 22.28 22.88 23.69 41.0 90.46 40.22 57.52 55.43 5.54 69.50 37.21 SnapKV 24.62 22.78 37.88 42.96 34.82 20.25 22.63 22.54 23.93 70.0 90.39 40.30 60.27 55.85 5.74 69.50 40.28 PyramidKV 24.48 23.51 36.24 42.33 31.95 20.73 23.37 23.01 24.37 72.5 90.43 40.54 59.27 54.87 5.88 69.50 40.19 ZigZagKV 24.54 23.18 36.98 42.61 33.24 20.51 23.04 22.80 24.17 71.4 90.41 40.43 59.72 55.31 5.81 69.50 40.66 DynamicKV 24.80 24.62 36.69 44.13 33.25 20.82 23.00 22.54 24.12 72.5 90.39 40.76 61.21 56.91 5.78 69.50 40.69 Ours 24.97 25.11 37.01 43.04 35.69 20.86 23.66 22.93 25.40 72.5 90.21 40.67 61.47 57.00 5.64 69.50 40.98 Qwen2 7B-Instruct FullKV 25.14 42.35 45.04 14.80 14.13 9.23 36.35 23.79 26.51 76.5 89.16 45.23 60.30 60.78 6.50 75.50 40.71 StreamingKV 20.47 26.97 32.64 14.31 14.39 6.82 25.70 19.31 24.88 66.0 76.56 32.11 46.58 44.20 8.00 15.50 29.65 H2O 22.88 34.28 41.50 13.30 14.60 8.31 23.69 22.07 22.72 39.5 88.75 43.91 58.83 57.83 8.00 72.00 35.76 SnapKV 23.86 38.50 44.68 15.60 14.62 9.13 24.56 22.39 23.18 70.0 89.31 43.32 58.68 60.74 5.00 72.00 38.47 PyramidKV 24.47 37.60 43.51 14.48 12.83 8.99 23.59 22.30 22.41 74.0 89.21 43.40 57.67 56.14 6.50 74.00 38.19 ZigZagKV 24.19 38.01 44.04 14.98 13.64 9.05 24.03 22.34 22.76 72.5 89.26 43.36 58.12 58.21 5.80 73.00 38.80 DynamicKV 24.66 40.44 45.30 15.42 13.89 8.46 25.51 22.77 22.92 74.0 89.27 43.18 60.38 59.32 7.00 74.00 39.16 Ours 25.05 41.00 44.99 14.75 14.04 8.50 25.96 22.70 24.16 75.5 89.09 43.38 60.76 60.10 8.00 74.00 39.50 Mistral-7B Instruct-v0.2 FullKV 26.63 32.99 49.34 42.77 27.35 18.77 32.87 24.24 27.10 71.0 86.23 42.96 56.93 54.49 2.75 86.98 42.71 StreamingKV 19.05 17.21 36.82 30.64 21.84 10.56 24.47 19.84 25.48 62.0 72.82 29.49 46.15 42.55 2.71 19.25 30.06 H2O 22.23 25.75 44.09 32.76 22.88 14.96 23.53 22.96 24.53 41.5 85.53 41.54 55.11 50.81 3.39 86.20 37.36 SnapKV 24.96 27.97 49.04 39.93 25.18 17.64 24.14 23.69 24.41 67.5 86.09 41.11 56.73 53.11 2.86 86.98 40.71 PyramidKV 23.55 28.79 48.71 41.00 25.64 16.35 24.79 23.52 24.49 69.5 86.20 42.58 55.45 51.67 3.53 81.81 40.47 ZigZagKV 24.18 28.42 48.86 40.52 25.43 16.93 24.49 23.59 24.45 68.5 86.15 41.91 56.03 52.32 3.22 84.14 40.83 DynamicKV 25.63 29.11 48.41 39.80 26.62 16.72 24.73 23.42 24.83 70.5 86.74 43.01 55.40 52.45 3.20 83.57 40.88 Ours 26.06 29.51 49.29 41.46 27.06 18.15 25.16 24.19 25.13 70.5 86.18 42.91 55.13 51.37 3.29 84.02 41.21 Figure 2 : Performance vs. KV Cache Size. Comparison of average accuracy on LongBench across different budget constraints. Our method (ComplierKV) degrades most gracefully, maintaining usability even at extreme compression ratios where baselines fail. 5 Experiments 5.1 Experimental Setup Datasets and Metrics. We evaluate our method on LongBench ( 1 ) , a comprehensive benchmark for long-context understanding. We cover a diverse set of 16 tasks across categories including Single-Doc QA (e.g., NarrativeQA ( 14 ) , Qasper ( 5 ) ), Multi-Doc QA (e.g., HotpotQA ( 29 ) ), Summarization (e.g., GovReport ( 13 ) , MultiNews ( 7 ) ), Few-shot Learning (e.g., TREC ( 15 ) , SAMSum ( 10 ) ), and Synthetic & Code tasks including Passage Retrieval (PRe), Passage Count (Pcount), LCC ( 11 ) , and RepoBench-P (RB-P) ( 18 ) . Following standard protocols, we report the specific metric for each dataset and the macro-average score. Baselines. We benchmark against FullKV (theoretical upper bound) and six SOTA methods representing diverse paradigms: H2O ( 30 ) and StreamingLLM ( 28 ) as eviction-based baselines; SnapKV ( 16 ) and ZigZagKV ( 31 ) for prefill-optimized selection; and PyramidKV ( 3 ) alongside DynamicKV ( 32 ) for budget allocation strategies. This selection comprehensively covers the spectrum from accumulation-based to head-aware and risk-adaptive compression. Implementation Details. We conduct experiments on four popular LLMs: LLaMA-3-8B-Instruct, Qwen2-7B-Instruct, Mistral-7B-Instruct-v0.2, and InternLM-2.5-7B-Chat. Unless otherwise stated, we set the KV cache budget to 512 tokens per layer for the compressed history. For our method, we compile both the Head Reliability Table and the Risk-Adaptive Threshold Gating on a held-out calibration corpus of approximately 50K long-context prompts, following Appendix B . This calibration corpus is strictly disjoint from all LongBench evaluation instances to avoid leakage. (a) FullKV (Avg. Score: 0.92) (b) StreamingLLM (Avg. Score: 0.26) (c) SnapKV (Avg. Score: 0.42) (d) PyramidKV (Avg. Score: 0.72) (e) DynamicKV (Avg. Score: 0.83) (f) CompilerKV (Avg. Score: 0.86) - Ours Figure 3 : Needle-in-a-Haystack Pressure Test on Mistral-7B. Visual comparison of retrieval accuracy (Green=100%, Red=0%) across varying context lengths (x-axis) and needle depths (y-axis). FullKV (a) sets the upper bound. While baselines like StreamingLLM (b) and SnapKV (c) struggle with long-range dependencies, and DynamicKV (e) shows fragmentation at extreme lengths, our method CompilerKV (f) maintains a robust retrieval pattern comparable to the oracle. 5.2 Main Results: Performance on LongBench Table 1 presents the comparative results across all models. Our method consistently outperforms all baselines and achieves performance closest to the FullKV upper bound. Superiority over State-of-the-Arts. Under the strict 512-token budget, our method achieves the highest average scores across all four models. On LLaMA-3-8B, we achieve an average score of 40.98, surpassing the strongest baseline (DynamicKV: 40.69) and recovering 97.7\% of the FullKV performance (41.95). On Qwen2-7B, while StreamingLLM and H2O suffer significant degradation (collapsing to <36.0 avg), our method maintains a robust score of 39.50, significantly outperforming ZigZagKV (38.33) which suffers from head-selection noise. Comparison with Dynamic Budgeting. Our results show that simply moving budget to lower layers is insufficient for complex reasoning tasks (e.g., Qasper). By contrast, our method, which jointly models entropy and perplexity, successfully identifies and protects high-complexity segments, yielding a +1.17 improvement on Qasper (InternLM-2.5) compared to PyramidKV. 5.3 Analysis of Compression Robustness To understand the behavior of our method under varying constraints, we evaluate the performance retention rate across different KV cache sizes (ranging from 64 to 1024 tokens). Figure 2 illustrates the performance trajectory across varying budget constraints. While eviction-based baselines exhibit precipitous performance drops as the budget decreases below 256 tokens, our approach maintains a significantly flatter degradation curve. Needle-in-a-Haystack Retrieval Heatmaps. To assess the fidelity of our compressed representations, we visualize the “Needle-in-a-Haystack” retrieval heatmaps in Figure 3 . While baselines like StreamingLLM and SnapKV suffer severe information loss (0.26–0.42) and even strong contenders like DynamicKV exhibit fragmentation in deep contexts, CompilerKV achieves a superior score of 0.86. By adaptively preserving high-risk tokens, our method reconstructs a retrieval pattern that closely mirrors the oracle FullKV (0.92), effectively bridging the gap where other compression methods fail. Additional Experiments. Beyond predictive accuracy, we provide the detailed profiling on end-to-end latency and peak memory usage across various context lengths in Table A1 in Appendix B.2 , demonstrating up to a 60% reduction in total latency for long-sequence generation. The effectiveness of these components is further substantiated by the policy visualizations in Figure A2 and A3 in Appendix B.2 , which confirm that the learned tables successfully identify retrieval heads and structurally sensitive layers. 5.4 Ablation Study We conducted ablation experiments on Head Reliability Governance and Risk-Adaptive Gating to verify the contributions of these two core components. As shown in Table 2 , Risk-Adaptive Gating proves most critical; replacing it with static thresholds causes the largest drop ( \sim 3.0 points). Stabilized Utility is also vital, as reverting to raw attention degrades performance by \sim 1.9 points, confirming its role in mitigating scale bias. Finally, Head Reliability contributes a consistent gain ( \sim 1.0 point) by filtering noisy heads to prioritize reliable signals. Table 2 : Component-wise Ablation Study. Impact of removing specific modules under a 512-token budget. Risk-Adaptive Thresholding ( \tau ) is the most critical factor. Ablation Setting Mistral LLaMA-3 Qwen2 InternLM CompilerKV (Full) 41.21 40.98 39.50 39.18 w/o Head Reliability 40.26 40.13 38.60 38.38 w/o Risk-Adaptive \tau 38.16 38.13 36.30 36.23 w/o Stabilized Utility 39.36 39.28 37.55 37.43 6 Conclusion We introduced CompilerKV, a framework that fundamentally rethinks KV cache compression by treating it as a risk-adaptive compilation process rather than a static pruning task. By injecting offline-learned head reliability priors and dynamically calibrating retention thresholds based on prompt complexity, our approach successfully overcomes the inherent instability of the one-size-fits-all compression policy and scale-biased attention statistics. Empirical results across diverse architectures confirm that CompilerKV achieves near-lossless performance even under extreme memory constraints, effectively decoupling inference cost from context length. This paradigm paves the way for deploying robust long-context capabilities on memory-constrained edge devices without the performance trade-offs typical of heuristic approaches. Future work will explore extending this compilation strategy to streaming generation and investigating the transferability of reliability tables across different model families. Appendix A Proof of Theorem 4.1 Proof. Let A^{(l,h)}\in\mathbb{R}^{T\times T} be the full attention matrix for head h in layer l . For a specific query at position t , the attention distribution over keys is given by the row vector A_{t,:}^{(l,h)} . The compressed attention matrix \tilde{A}^{(l,h)} is constructed by retaining only the indices in the set \mathcal{S}^{(l)} , where |\mathcal{S}^{(l)}|=B_{l} . The resulting sparse distribution is re-normalized. A standard result in sparse attention analysis ( 30 ) states that the L_{1} distance between the full and compressed distributions is bounded by twice the probability mass of the discarded tokens: \left\|A_{t,:}^{(l,h)}-\tilde{A}_{t,:}^{(l,h)}\right\|_{1}\leq 2\sum_{j\notin\mathcal{S}^{(l)}}A_{t,j}^{(l,h)}. (A1) This inequality implies that the approximation error is strictly determined by the total attention weight of the evicted tokens. In CompilerKV, the selection set \mathcal{S}^{(l)} is determined by the stabilized utility score \hat{u}_{j}^{(l)} , defined as Eq. ( 10 ). The selection rule \mathcal{S}^{(l)}=\text{Top-}B_{l}(\hat{u}^{(l)}) ensures that we retain tokens with the highest weighted utility. Ideally, maximizing utility \hat{u} minimizes the discarded attention mass. However, the true attention A_{t,j}^{(l,h)} for a specific head h may deviate from the aggregated utility. We bound this deviation using the head reliability weight. The selection rule keeps tokens with high \hat{u}_{t}^{(l)}=\max_{k}(u_{t}^{(l,k)}\cdot W_{\text{head}}[l,k]) . Since , dividing by W_{\min}^{(l)} provides a conservative scaling factor. Specifically, the error contribution of pruned tokens is strictly controlled by their utility. Combining these, we obtain the bound in terms of the utility sum: \sum_{j\notin\mathcal{S}^{(l)}}A_{t,j}^{(l,h)}=\frac{1}{W_{\text{head}}[l,h]}\sum_{j\notin\mathcal{S}^{(l)}}\left(W_{\text{head}}[l,h]\cdot A_{t,j}^{(l,h)}\right)\leq\frac{1}{W_{\min}^{(l)}}\sum_{j\notin\mathcal{S}^{(l)}}u_{j}^{(l,h)}. (A2) Substituting this back into inequality ( A1 ) yields the first result: \left\|A_{t,:}^{(l,h)}-\tilde{A}_{t,:}^{(l,h)}\right\|_{1}\leq\frac{2}{W_{\min}^{(l)}}\sum_{j\notin\mathcal{S}^{(l)}}u_{j}^{(l,h)}. (A3) We now derive the bound for the Frobenius norm over the entire layer. The squared Frobenius norm of the error matrix E^{(h)} for head h is: \|E^{(h)}\|_{F}^{2}=\sum_{t=1}^{T}\|A_{t,:}^{(l,h)}-\tilde{A}_{t,:}^{(l,h)}\|_{2}^{2}. (A4) Using the norm inequality \|x\|_{2}\leq\|x\|_{1} , we have \|A_{t,:}-\tilde{A}_{t,:}\|_{2}^{2}\leq\|A_{t,:}-\tilde{A}_{t,:}\|_{1}^{2} . However, since probabilities sum to 1, a tighter bound for the specific case of probability distributions is \|A_{t,:}-\tilde{A}_{t,:}\|_{2}\leq\sqrt{2\sum_{j\notin\mathcal{S}}A_{t,j}} . Thus, \|E^{(h)}\|_{F}\approx\sqrt{\sum_{t=1}^{T}\left(\sum_{j\notin\mathcal{S}}A_{t,j}^{(l,h)}\right)^{2}} (A5) We define the random variable X_{t}=\sum_{j\notin\mathcal{S}}A_{t,j}^{(l,h)} representing the “lost mass” at step t . The expected value of the total lost mass is \mathbb{E}[\sum X_{t}]=T\cdot\epsilon_{\text{tail}}^{(l)} . By the McDiarmid’s Inequality (or Hoeffding’s bound for bounded variables), the deviation of the sum of independent random variables (assuming approximate independence of attention distributions across diverse prompts) from its expectation is bounded. The range of the sum is constrained by the number of pruned tokens (T-B_{l}) . The sensitivity of the selection function is scaled by the inverse of the head reliability weights (since a low weight increases the variance of the selection decision). Applying the concentration bound with probability 1-\delta : \frac{1}{T}\sum_{t=1}^{T}X_{t}\leq\mathbb{E}[X_{t}]+\mathcal{O}\left(\sqrt{\frac{\log(1/\delta)}{T}}\right) (A6) Scaling to the Frobenius norm (which involves \sqrt{T} ): \|E^{(h)}\|_{F}\leq\sqrt{T}\cdot\epsilon_{\text{tail}}^{(l)}+\mathcal{O}\left(\sqrt{\frac{(T-B_{l})\log(1/\delta)}{T}}\right) (A7) Finally, incorporating the W_{\min}^{(l)} term to account for the worst-case head reliability (since we average over H heads, the bound is dominated by the least reliable head if not weighted), we arrive at the final aggregated bound: \frac{1}{H}\sum_{h=1}^{H}\left\|A^{(l,h)}-\tilde{A}^{(l,h)}\right\|_{F}\leq\sqrt{T}\cdot\epsilon_{\text{tail}}^{(l)}+\mathcal{O}\left(\sqrt{\frac{(T-B_{l})\log(1/\delta)}{T\cdot(W_{\min}^{(l)})^{2}}}\right) (A8) This confirms that the approximation error is bounded by the tail mass \epsilon_{\text{tail}} , and the stability of this bound improves as the context length T increases (law of large numbers), but is penalized by aggressive pruning ( T-B_{l} ) and low head reliability ( W_{\min} ). ∎ Appendix B Additional Experiments B.1 Offline Table Compilation Calibration corpus. We compile both decision tables (the head heterogeneity table W_{\text{head}}[l,h] and the risk-adaptive threshold gating \bf{T}_{\text{gate}} ) on a held-out calibration corpus \mathcal{D}_{\text{cal}} , which is strictly disjoint from the LongBench evaluation set to avoid leakage. \mathcal{D}_{\text{cal}} contains approximately 50 K long-context prompts sampled from diverse public sources, including long-form narratives (PG19), scientific/technical articles (arXiv, PubMed), long-document summarization and meeting transcripts (GovReport, QMSum, BookSum), as well as instruction-style dialogues and code/QA text (ShareGPT/UltraChat and The Pile subsets such as GitHub/StackExchange). All prompts are used in an unlabeled manner: we only require forward statistics from the prefill stage and a short continuation loss for reward computation. Risk signals and stratified coverage. For each prompt x_{1:T} , we compute the observation-window statistics on \mathcal{W}=\{T-w_{\text{obs}}+1,\dots,T\} , including the attention entropy H(A) and local perplexity , and discretize them into bin indices (b_{h},b_{p}) . To ensure sufficient coverage of high-risk prompts (e.g., high-entropy or high-perplexity regimes), we adopt stratified sampling over (b_{h},b_{p}) when constructing \mathcal{D}_{\text{cal}} , avoiding a dominance of medium-risk samples that would otherwise bias the learned tables toward overly aggressive pruning. Why 20\times 4 bins for (H(A),\mathrm{PPL}) . We choose N_{H}{=}20 entropy bins and N_{P}{=}4 perplexity bins, resulting in a 20\times 4 risk grid for each layer. This design is motivated by a practical bias–variance trade-off for discrete table policies: (i) attention entropy is a structural signal with a relatively smooth and wide dynamic range over long-context prompts, hence we allocate finer granularity ( 20 bins) to capture gradual shifts in concentration vs. dispersion; (ii) perplexity acts as a semantic uncertainty signal whose main role is to modulate the overall conservativeness, and empirically exhibits heavier tails and higher estimation noise on short windows, thus we use coarser partitioning ( 4 bins) to maintain stability. With L{=}32 layers, the LUT contains 32\times 20\times 4{=}2560 entries, which is small enough for robust offline estimation and deployment, while still expressive enough to differentiate risk regimes without introducing over-fragmentation. In our calibration, this binning yields adequate per-cell support under stratified sampling and avoids sparse high-risk cells that would cause unstable threshold decisions. Model choice and cross-architecture applicability. We compile tables on a 32-layer backbone to obtain a unified layer index space. For models with different depths, we apply a monotonic depth mapping (e.g., relative-depth interpolation) at inference time. While our main results use per-model compilation, we also explore depth mapping as a heuristic to reuse tables across similar 7B–8B backbones, with preliminary evidence suggesting potential portability. We leave a rigorous same-table transfer evaluation for future work. Hyperparameter ranges and robustness. Both compiled tables operate as bounded multiplicative modulators on top of a normalized utility signal, which allows us to use conservative and architecture-stable ranges. For Stage 3, the LUT outputs a layer threshold \tau^{(l)}\in[0.8,1.0] . This range is chosen for two reasons. First, \hat{u}^{(l)}_{t} is constructed from the stabilized utility u_{t}=\alpha_{t}\cdot\rho_{t} , where \rho_{t} is sample-normalized ; empirically, this makes \hat{u}^{(l)}_{t} concentrate around \mathcal{O}(1) across prompts and layers, so thresholds outside [0.8,1.0] either admit almost all tokens (too conservative) or reject nearly all tokens (degenerate), collapsing the “threshold+Top- B_{l} ” mechanism. Second, under tight budgets the final retention is always enforced by Top- B_{l} ; hence \tau^{(l)} mainly controls the candidate set margin rather than the final budget. Bounding \tau^{(l)} to [0.8,1.0] keeps the candidate size within a stable, budget-aligned regime while still allowing risk-conditioned shifts across (b_{h},b_{p}) . Table A1 : Efficiency comparison between FullKV and our CompilerKV. CompilerKV compiles a fixed compressed KV-cache before decoding, enabling faster token generation with slightly higher prefill cost (TTFT) but significantly improved end-to-end latency and memory usage. Context Setting Efficiency Metrics Input Output Method TTFT TPOT Latency Memory (Tok) (Tok) (s) \downarrow (tok/s) \uparrow (s) \downarrow (MB) \downarrow 8k 2k FullKV 0.66 27.63 74.79 20055 CompilerKV 0.72 36.20 58.90 19050 16k 4k FullKV 1.45 19.55 209.56 23859 CompilerKV 1.52 34.80 118.40 21420 32k 8k FullKV 3.52 11.65 706.56 31213 CompilerKV 3.65 28.50 285.00 26880 Figure A1 : Universality across Model Architectures. The average performance trend of our method on four different LLMs (LLaMA-3, Qwen2, InternLM-2.5, Mistral) under varying KV cache budgets (ranging from 64 to 1024). The consistent degradation patterns across diverse architectures demonstrate the generalization capability of our risk-adaptive mechanism. Figure A2 : Visualization of Learned Head Reliability Table. The color intensity represents the learned scaling factor for each head across layers. The emergence of distinct suppressed zones (blue/cold colors) confirms that our method automatically identifies and suppresses noisy heads that would otherwise disrupt token selection. B.2 Runtime Efficiency and Memory Analysis To evaluate the practical deployment viability of CompilerKV , we conducted a comprehensive efficiency profile comparing it against the lossless FullKV baseline. We measured Time to First Token (TTFT), Time Per Output Token (TPOT), end-to-end Latency, and Peak Memory usage across varying context lengths (Input: 8k-32k, Output: 2k-8k). The results are detailed in Table A1 . Prefill Overhead vs. Decoding Speedup. As shown in the “TTFT” column, CompilerKV introduces a marginal overhead during the prefill phase (e.g., an increase from 0.66s to 0.72s in the 8k setting). This slight delay is the expected “compilation cost” incurred by our Risk-Adaptive Gating and Head-Aware Importance calculation. However, this one-time investment yields significant returns during the decoding phase. By strictly maintaining a compressed budget, CompilerKV dramatically improves the throughput (TPOT). For instance, in the 32k input scenario, the generation speed increases from 11.65 tok/s to 28.50 tok/s. End-to-End Latency. Consequently, the total latency sees a substantial reduction. The slight delay in prefill is negligible compared to the time saved during generation. In the most demanding setting (32k input, 8k output), CompilerKV reduces the total latency by approximately \mathbf{60\%} (from 706.56s to 285.00s), demonstrating that the ”compile-then-execute” paradigm is highly efficient for long-context generation tasks. Memory Efficiency. Furthermore, CompilerKV consistently reduces peak memory consumption. By proactively filtering redundant historical states, it saves approximately 14%–16% of GPU memory compared to FullKV, alleviating hardware bottlenecks and enabling longer context processing on resource-constrained devices. Universality across Model Architectures. Figure A2 demonstrates our method’s consistent performance trajectory across four distinct LLMs (including LLaMA-3, Qwen2, and Mistral) as the budget tightens from 1024 to 64 tokens. This architectural universality confirms that our Risk-Adaptive Gating and Head Reliability mechanisms capture fundamental attention properties rather than overfitting to specific model weights. B.3 Visualization of Learned Policies To understand how CompilerKV adapts to different risk levels, we visualize the learned threshold table \mathbf{T}_{\text{gate}} in Figure A3 . The visualization confirms that the offline RL process converges to an interpretable strategy: As shown in the difference between the “Low Perplexity” and “High Perplexity” subplots, the policy globally lowers the retention threshold (blue zones) for high-perplexity samples, allowing more tokens to be stored when the model is uncertain. Within each plot, as Attention Entropy increases ( x -axis), the threshold decreases. This indicates the model automatically acts conservatively for diffuse attention patterns (e.g., dense retrieval), preventing the pruning of scattered but critical information. We visualize our learned Head Reliability Table in Figure A2 . The heatmap reveals a clear structure: specific heads (e.g., in middle layers L12-L20) are consistently assigned negative or low weights, indicating they act as “noise emitters” for the prefill task. By explicitly down-weighting these heads, our Pass-3 mechanism prevents them from polluting the budget with irrelevant tokens. Figure A3 : Risk-Adaptive Threshold Gating Policy. The plots show the learned retention threshold ( \tau ) across layers for samples with varying risk levels (binned by Perplexity and Attention Entropy). For high-risk samples (High Perplexity, rightmost plots), the policy automatically lowers thresholds to preserve more information, validating our risk-adaptive mechanism. Model Method Single-Document QA Multi-Document QA Summarization Few-shot Learning Synthetic Code Avg. NrtvQA Qasper MF-en HotpotQA 2WikiMQA Musique GovReport QMSum MultiNews TREC TriviaQA SAMSum PCount PRe Lcc RB-P 18409 3619 4559 9151 4887 11214 8734 10614 2113 5177 8209 6258 11141 9289 1235 4206 – LlaMA-3-8B -Instruct FullKV 25.16 31.81 39.59 43.09 36.15 21.77 28.62 23.34 26.33 75.00 90.50 42.36 5.20 69.25 59.04 53.93 41.95 StreamingLLM 17.85 9.50 23.09 37.84 29.02 16.77 17.91 20.42 20.16 44.00 73.00 30.00 5.80 69.50 48.38 49.31 32.03 H2O 21.58 12.54 28.49 37.13 32.36 18.88 20.23 22.16 21.14 39.00 86.62 39.19 5.50 69.50 57.39 54.46 35.39 SnapKV 21.71 12.37 32.38 37.44 30.48 19.50 19.06 21.36 20.07 45.5 87.74 38.15 5.50 68.85 57.42 54.61 35.76 PyramidKV 22.26 16.65 30.73 38.97 29.28 19.19 19.92 22.06 20.87 68.00 88.95 38.23 5.92 69.50 57.20 51.54 37.45 DynamicKV 22.10 14.93 32.94 41.06 27.98 21.18 20.03 22.06 21.28 65.50 89.61 38.70 5.13 69.50 58.01 54.00 37.75 CompilerKV 22.46 15.22 33.34 41.37 28.48 21.25 20.43 22.16 21.35 66 89.68 39.00 5.50 69.25 57.91 53.94 37.97 Mistral-7B -Instruct-v0.2 FullKV 26.63 32.99 49.34 42.77 27.35 18.77 32.87 24.24 27.10 71.00 86.23 42.96 2.75 86.98 56.93 54.49 42.71 StreamingLLM 16.58 14.76 30.36 28.13 21.76 11.98 18.26 19.02 19.16 43.50 74.12 28.50 2.50 31.81 43.65 41.19 27.83 H2O 21.66 21.64 38.60 30.96 20.63 13.02 20.65 22.61 22.08 39.00 82.19 39.75 3.16 79.98 51.25 48.20 34.71 SnapKV 20.11 21.28 42.98 37.51 22.31 14.43 19.19 21.89 21.01 48.00 83.77 40.44 2.51 66.99 51.64 48.57 35.16 PyramidKV 22.11 22.52 43.04 33.57 22.98 15.69 20.56 22.52 21.36 65.50 83.84 40.03 2.89 67.26 51.51 46.42 36.36 DynamicKV 22.05 23.65 43.08 36.03 22.60 15.23 21.35 23.11 22.19 68.00 84.79 41.02 4.20 70.11 52.45 47.41 37.33 CompilerKV 22.31 24.06 43.20 36.42 22.91 16.47 21.55 23.21 22.35 68.20 85.00 41.20 4.25 70.30 52.30 47.60 37.63 Qwen2-7B -Instruct FullKV 25.14 42.35 45.04 14.80 14.13 9.23 36.35 23.79 26.51 76.50 89.16 45.23 6.50 75.50 60.30 60.78 40.71 StreamingLLM 19.25 23.63 26.51 14.00 15.30 7.46 18.07 19.30 18.30 47.00 77.92 31.57 6.50 17.00 42.52 41.94 26.64 H2O 20.33 30.43 34.22 13.61 13.37 7.81 20.72 21.66 18.44 40.00 86.94 42.17 7.00 70.50 53.45 53.76 33.40 SnapKV 22.26 31.62 38.95 16.05 17.71 7.66 18.91 21.41 18.21 46.00 87.61 42.01 6.50 63.50 54.87 53.03 34.14 PyramidKV 20.50 31.70 39.95 18.54 18.54 8.85 19.24 20.47 18.18 60.00 87.98 39.71 7.00 49.00 48.77 47.91 33.52 DynamicKV 22.77 35.57 42.62 14.80 16.35 8.31 21.41 21.97 19.56 58.00 88.18 40.93 6.50 70.00 53.58 52.50 35.82 CompilerKV 23.12 35.93 42.81 14.85 16.45 8.40 21.62 22.47 19.74 60.00 88.38 41.05 6.50 70.50 53.44 52.79 36.13 InternLM-2.5-7B -Chat-1M FullKV 22.42 27.61 39.98 40.92 33.48 26.68 33.01 25.18 26.28 72.50 86.76 39.76 2.91 100.00 55.86 57.95 43.21 StreamingLLM 17.91 13.02 24.31 24.27 16.01 11.29 17.29 20.62 18.06 48.5 67.53 21.93 0.82 87.39 43.45 42.79 29.70 H2O 16.16 17.71 27.94 26.83 17.83 17.81 13.99 22.59 16.9 39.50 81.87 32.15 1.32 96.50 48.30 47.27 32.79 SnapKV 19.65 17.44 35.29 27.36 18.58 19.79 12.76 22.42 16.31 48.00 80.23 31.35 0.95 95.00 49.47 48.22 33.93 PyramidKV 18.80 17.35 33.48 31.16 20.05 19.02 14.65 22.02 17.40 69.50 80.87 32.02 1.23 95.00 47.13 44.73 35.28 DynamicKV 17.93 19.89 34.15 31.50 19.03 20.60 15.14 22.41 18.15 70.00 83.09 32.44 0.86 95.50 49.33 47.16 36.07 CompilerKV 18.36 20.32 34.61 32.17 19.75 20.95 15.5 22.62 18.46 70.50 83.43 32.76 0.92 97.00 49.28 47.42 36.50 Table A2 : Performance comparison on the LongBench dataset for full KV cache, previous methods (StreamingLLM, H2O, SnapKV, PyramidKV, DynamicKV), and our CompilerKV method, with KV cache sizes of 128, using models including LLaMA3-8B-Instruct, Mistral-7B-Instruct-v0.2, QWen2-7B-Instruct, and InternLM-2.5-Chat-1M. Bold indicates the best performance. Appendix C Algorithm Algorithm 1 CompilerKV : Prefill-only KV Compression (operator form) 1: Input: prompt x_{1:T} ; layers l\in[1,L] ; heads h\in[1,H] ; per-layer budgets \{B_{l}\} ; observation window \Omega=\{T-w_{\mathrm{obs}}+1,\dots,T\} ; risk LUT \mathbf{T}_{\mathrm{gate}} ; head table \mathbf{W}_{\mathrm{head}} 2: Output: compressed KV cache \{(\tilde{K}^{(l)},\tilde{V}^{(l)})\}_{l=1}^{L} 3: (A) Prefill-time risk coordinates (streaming reductions) 4: \{A^{(l,h)},\,K^{(l,h)},\,V^{(l,h)}\}\leftarrow\textsc{Prefill}(x_{1:T}) A^{(l,h)}\!\in\!\mathbb{R}^{T\times T},\ K^{(l,h)},V^{(l,h)}\!\in\!\mathbb{R}^{T\times d} 5: \bar{A}\leftarrow\textsc{Mean}_{l,h}\!\left(A^{(l,h)}\right) ( layer/head mean ) 6: \alpha\leftarrow\sum_{j\in\Omega}\bar{A}_{j,:}\in\mathbb{R}^{T} ( window attention mass ) 7: \bar{A}^{\prime}\leftarrow\alpha/\lVert\alpha\rVert_{1} ( normalize to a distribution ) 8: \mathcal{R}_{\mathrm{struct}}\leftarrow\mathsf{H}(\bar{A}^{\prime})\;=\;-\sum_{t=1}^{T}\bar{A}^{\prime}_{t}\log\bar{A}^{\prime}_{t} 9: \mathcal{R}_{\mathrm{sem}}\leftarrow\exp\!\Big(-\frac{1}{|\Omega|}\sum_{j\in\Omega}\log P(x_{j}\mid x_{