H_2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models

🎯 Pitch

A mere 20% of tokens—dubbed heavy hitters—dominate attention scores in large language model generation, and discarding them causes catastrophic accuracy collapse. H2O exploits this by dynamically retaining just these heavy hitters plus recent tokens, shrinking the KV cache up to 5× while matching full-cache performance and boosting throughput by up to 29×.

1. Executive Summary

This paper introduces Heavy Hitter Oracle (H2O), a KV cache eviction policy that dynamically retains a balance of recently generated tokens and a small set of influential tokens identified as heavy hitters (tokens whose accumulated attention scores across decoding steps dominate the attention distribution, following a power-law pattern). The approach is evaluated on OPT, LLaMA, and GPT-NeoX models across tasks from HELM and lm-eval-harness, demonstrating that retaining only 20% of the KV cache—a 5× memory reduction—suffices to match full-cache accuracy on a majority of benchmarks (e.g., 84.00% vs. 85.00% on COPA with OPT-30B). The eviction policy is formulated as a dynamic submodular maximization problem, yielding a greedy algorithm with provable guarantees, and in throughput benchmarks H2O improves generation throughput over FlexGen, DeepSpeed, and Hugging Face Accelerate by up to 3×, 29×, and 29× respectively. The work establishes that aggressive KV cache reduction is viable only when the eviction policy preserves heavy hitters alongside recent context—removing heavy hitters entirely causes severe functional collapse, while retaining only local tokens degrades accuracy by up to 35 percentage points.

2. Context and Motivation

The Core Problem: The KV Cache Is a Silent Deployment Bottleneck

When you ask a large language model like GPT-3 or LLaMA to generate text, most of the attention (in research and media) goes to the model's parameter count—the billions of weights that get loaded into GPU memory. But there is another memory consumer that grows during use and often dominates at scale: the KV cache. Every time the model generates a new token, it must compute attention against all previously generated tokens. Rather than recomputing the key and value embeddings for every past token at each step (which would be $O(n^2)$ in computation), transformers cache these embeddings after the first computation. The result is a data structure that stores two vectors (a key and a value) for every token in every layer, for every sequence in the batch.

The memory footprint is staggering. The paper provides a concrete example (Section 1):

"a 30 billion-parameter model with an input batch size of 128 and a sequence length of 1024 results in 180GB of KV cache."

To put that in perspective: 180GB exceeds the memory of any single GPU on the market at time of writing—a single NVIDIA A100 maxes out at 80GB. This means that for long-context or large-batch generation, the KV cache, not the model parameters, becomes the thing that forces costly workarounds: CPU offloading (with massive latency penalties), aggressive batch-size reduction (hurting throughput), or simply failing to fit the workload on available hardware.

The problem compounds in three practically important scenarios that the paper highlights (Section 1):

Long-content generation (dialogue systems, story writing, summarization of long documents): as the sequence grows, the cache grows linearly with it. A 4,000-token generation with a 30B model and batch size 64 produces tens of gigabytes of KV cache for that sequence alone.
Large-batch inference for high throughput: production systems that serve many users simultaneously need large batch sizes to amortize the cost of loading model parameters. The KV cache scales linearly with batch size, so it quickly becomes the limiting factor.
Resource-constrained deployments: on edge devices or low-cost cloud instances with limited GPU memory (e.g., NVIDIA T4 with 16GB), the KV cache can prevent deployment entirely even for moderate model sizes.

This is not a hypothetical concern. The paper notes that this bottleneck is "becoming increasingly prominent" (Section 1), as models grow and sequence lengths increase. The KV cache has moved from a minor implementation detail to a first-class deployment constraint.

Why This Problem Is Hard: Three Technical Challenges

The paper identifies three specific technical barriers to solving the KV cache problem (Section 1):

Challenge 1: It is not obvious that the cache can be meaningfully reduced. At first glance, each decoding step might genuinely need access to all previous keys and values. The attention mechanism computes a weighted sum over all past tokens—restricting which tokens are available is, in principle, lossy. There is no a priori guarantee that a subset of the cache suffices. Prior sparse attention methods exist, but they were primarily designed for training (where the goal is reducing the $O(n^2)$ compute cost of full attention, not reducing memory for cached key-value pairs). It is not obvious that the same sparsity patterns observed during training transfer to the autoregressive generation setting, where the model sees tokens sequentially rather than all at once.

Challenge 2: The optimal eviction policy is a combinatorial nightmare. Even if you accept that some tokens can be safely forgotten, which ones? The paper frames this directly (Section 1):

"identifying an optimal eviction policy that maintains generation accuracy is a combinatorial problem."

This is harder than standard cache eviction (e.g., CPU caches, where Belady's optimal algorithm says: evict the block that will be needed furthest in the future). In the KV cache setting, Belady's algorithm is not directly applicable because once you evict a token's key-value embeddings, the attention computation at future steps changes—the sequential dependency means that an eviction decision at step $t$ propagates through all subsequent steps. A token that seems unimportant for step $t$ might have been critical for step $t+5$ , but after eviction, the model never gets the chance to attend to it. This is a fundamentally harder optimization problem than classical caching.

Challenge 3: Even if you could solve the combinatorial problem offline, the solution would be too expensive for deployment. Brute-forcing an optimal eviction schedule for each sequence during generation defeats the purpose—the computational cost of the policy itself would overwhelm any memory savings. A practical system needs an eviction policy that is cheap to compute at each decoding step, ideally with near-zero overhead relative to the attention computation itself.

Where Prior Approaches Fall Short

The paper positions its contribution against a landscape of existing methods that each address part of the problem but fail to satisfy all three practical requirements (Section 1, Figure 1).

Sparse attention methods designed for training do not translate well to inference-time KV cache reduction. Several well-known approaches—Reformer (Kitaev et al., 2020), FlashAttention (Dao et al., 2022), Performer (Choromanski et al., 2020), Linear Transformers (Katharopoulos et al., 2020)—overcome the quadratic memory cost of the attention matrix during training or long-sequence modeling. However, the paper points out that these methods were designed to reduce the $O(n^2)$ computation of full attention, not to reduce the cache size during autoregressive generation. Even with efficient attention kernels, the KV cache still stores embeddings for all tokens. FlashAttention, for instance, computes exact attention with better memory access patterns but does not reduce what gets stored.

Structural modifications to reduce cache size degrade accuracy when applied post-hoc to pretrained models. Multi-query attention (Shazeer, 2019; Pope et al., 2022, Chowdery et al., 2022) and grouped-query attention reduce the number of key-value heads, directly shrinking the cache. However, these are architecture-level changes—a pretrained model with standard multi-head attention cannot benefit from them without retraining. Similarly, Sparse Transformer (Child et al., 2019) introduces structured sparsity patterns (e.g., strided attention that attends to every $s$ -th token plus local tokens). The paper shows in Figure 1 and Table 2 that directly applying these fixed sparsity patterns to pretrained LLMs for generation "results in high miss rates and degrades the accuracy." Specifically, with a 20% KV cache budget, Sparse Transformer variants drop by up to 35 percentage points compared to full-cache models on tasks like COPA (Table 2: 50% vs 85% for strided, 61% vs 85% for fixed). The model was not trained to expect missing tokens at those positions, so the distribution shift is catastrophic.

Learning-based compression methods are too expensive for inference-time use. The paper cites gisting tokens (Mu et al., 2023) as an approach that can learn to compress the KV cache into a smaller set of summary tokens. However, "their expensive eviction policies are difficult to deploy during generation." If the compression itself requires running additional forward passes or optimization steps per decoding step, the wall-clock overhead eliminates any benefits from reduced memory access. A similar issue applies to Dynamic Context Pruning (Anagnostidis et al., 2023), which uses a learned mechanism to determine necessary tokens during inference but requires extra fine-tuning, making it less practical for pretrained models.

Prior work missed the heavy-hitter phenomenon and its implications. The paper's central empirical insight—that accumulated attention scores follow a power-law distribution, with a small fraction of tokens dominating the total attention mass—was not previously documented or exploited for KV cache design. This observation (detailed in Section 3.2, Figure 2) is what enables a simple, low-cost policy (keep the heavy hitters + recent tokens) to work where structural sparsity fails. Prior work applying accumulated attention scores for token pruning (e.g., SpAtten; Wang et al., 2021) aggregated scores across attention heads and layers, which the paper argues "don't consider the variance of token importance across attention heads and layers" (Appendix C.9). By allowing each token to be kept or evicted independently per head and per layer, H2O captures heterogeneous importance patterns that head-aggregated methods miss—a difference that yields measurable accuracy gains (Table 11: H2O at 84.00% vs. SpAtten at 82.00% on COPA with OPT-30B at a 20% budget).

The Gap This Paper Fills

Prior work left a clear gap: there was no KV cache eviction policy that simultaneously satisfied three requirements: (1) small cache size to meaningfully reduce memory, (2) low miss rate to preserve generation quality, and (3) low-cost policy computation to avoid overhead during inference. Methods either reduced memory at unacceptable accuracy cost (structural sparsity applied post-hoc), required architectural changes or retraining (multi-query attention, gisting), or incurred policy computation overhead that defeated the purpose (learned pruning mechanisms).

The paper's contribution is not a new attention mechanism or model architecture—it is a principled eviction policy for the standard KV cache that exploits a newly observed empirical property of pretrained LLMs. The heavy-hitter phenomenon (the power-law distribution of accumulated attention scores) means that a simple greedy algorithm—keep the tokens with the highest cumulative attention scores plus a sliding window of recent tokens—is near-optimal. The paper formalizes this as a dynamic submodular maximization problem (Section 4), providing theoretical justification for why greedy H2 selection works, and demonstrates that the local (history-only) version of the policy is as effective as the global (future-aware) version (Figure 2d), which is what makes it deployable—you can decide which tokens are heavy hitters using only the attention scores you have already computed.

The paper is thus positioned at the intersection of systems (throughput/latency improvements via memory reduction) and theory (submodular guarantees for the eviction policy). It addresses the deployment bottleneck by making the KV cache smaller, rather than by making attention faster—a distinction that matters because the KV cache memory problem persists even when attention computation is optimized.

3. Technical Approach

3.1 Reader Orientation

This paper develops H2O (Heavy Hitter Oracle), a KV cache eviction algorithm that runs alongside autoregressive LLM generation, making per-token decisions about which key-value embeddings to keep in GPU memory and which to discard. The system solves the problem of the KV cache growing linearly with sequence length and batch size—a memory bottleneck that can consume 180GB for a 30B-parameter model with batch size 128 and sequence length 1024 (Section 1)—by observing that a small fraction of tokens dominates the total attention mass, and that retaining only these "heavy hitters" plus a sliding window of recent tokens preserves generation quality while cutting cache size by up to 20×.

3.2 Big-Picture Architecture (Diagram in Words)

The system has three interconnected components that operate within the autoregressive generation loop:

The base LLM (OPT, LLaMA, or GPT-NeoX) — the pretrained model that generates tokens one at a time. It computes attention at each decoding step, producing normalized attention scores against all previously cached key-value embeddings. It does not need to know that some KV pairs are missing—the eviction is transparent to the model.
The Attention Score Accumulator — a data structure that maintains, for each token position in each attention head of each layer, a running sum of the attention scores that all subsequent tokens have assigned to it. This is the mechanism that identifies heavy hitters: tokens whose accumulated scores are high are precisely those that many future tokens want to attend to.
The H2O Eviction Policy — a per-step decision procedure that, given a fixed budget $k$ (the maximum number of KV embeddings to retain), maintains a cache containing exactly $k$ tokens: the $k/2$ tokens with the highest accumulated attention scores (the heavy hitters), and the $k/2$ most recently generated tokens (local context). At each new decoding step, the policy evicts at most one token to make room for the new one, selecting the evictee as the token whose removal minimizes the degradation in total retained attention mass.

Information flows as follows: during autoregressive generation, the model computes attention scores for the new query against all currently cached keys → these scores are added to the accumulator for each cached token → the eviction policy selects one token to remove (the one with lowest accumulated score among non-recent tokens that is not the newest addition) → the new token's KV embeddings are inserted into the cache → the process repeats for the next decoding step.

3.3 Roadmap for the Deep Dive

First, the formal problem formulation (Section 2.1 of the paper), which defines the KV-cache-constrained generative process, the eviction policy constraints, and what it means for the policy to succeed. This establishes the mathematical setting that the remainder of the approach operates within.
Second, the two empirical observations that make H2O possible: attention sparsity (Section 3.1) and heavy-hitter power-law distributions (Section 3.2). Understanding these observations is prerequisite to understanding why the greedy eviction policy works.
Third, the H2O eviction algorithm itself (Section 4.1), including how accumulated attention scores are computed, how the heavy-hitter set is maintained incrementally, and why the policy is "local" (using only past information) rather than "global" (requiring future information that is unavailable at inference time).
Fourth, the theoretical framework (Section 4.2, Appendix D): the formulation as a dynamic submodular maximization problem, the submodularity assumption, the greedy algorithm's near-optimality guarantee, and how the analysis handles approximate score functions.
Fifth, the system implementation details (Sections 4.2 and Appendix A) that make the policy efficient in wall-clock time: the preallocated circular buffer, the per-head/per-layer independence, and the integration with the FlexGen inference engine.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily an empirical systems paper whose core technical idea is a greedy KV cache eviction policy grounded in two observations about pretrained LLM attention patterns: (1) attention matrices are over 95% sparse at inference time, meaning most KV embeddings are irrelevant for any given decoding step; and (2) a small set of tokens accumulate the vast majority of attention mass across steps, following a power-law distribution. The eviction policy retains these "heavy hitters" plus a sliding window of recent tokens, yielding a cache that is both small and accurate.

Formal Problem Formulation: The KV-Cache-Constrained Generative Process

Before explaining the eviction algorithm, the paper formally defines what it means to generate tokens with a limited-size KV cache. This formalism (Section 2.1, Definitions 2.1 and 2.2) is necessary because the KV cache is not a passive store—it actively shapes the attention distribution at every subsequent step, so an eviction decision at step $i$ propagates through all future steps.

The standard autoregressive generation process (without cache limits) works as follows. At step $i$ , the model has a query vector $Q_{i,*} \in \mathbb{R}^d$ (a row of the query matrix corresponding to the current token) and key-value embeddings for all previous tokens $K_{\leq i,*} \in \mathbb{R}^{i \times d}$ . The attention output is computed as:

$o_i = D_i^{-1} \cdot \exp(Q_{i,*} K_{\leq i,*}^\top)$

where $D_i := \exp(Q_{i,*} K_{\leq i,*}^\top) \cdot \mathbf{1}_i$ is the normalization scalar (the sum of exponentiated dot products, ensuring the attention vector sums to 1), and $o_i \in \mathbb{R}^i$ is a vector of attention weights—one weight per previous token, representing how much the current token "attends to" each past token.

What this computes: for the current token (query), the model computes a dot-product score against every previously cached key, exponentiates these scores to make them positive and emphasize large values, and then normalizes by dividing by the sum. The resulting vector tells the model, as a probability distribution, which past tokens are relevant.

Why this form: the softmax (exponentiate-then-normalize) ensures attention weights are non-negative and sum to one, which is necessary for them to function as a weighted average when multiplying against value vectors. The normalization $D_i$ depends on all past tokens—if you remove some, $D_i$ changes, which changes every surviving token's effective attention weight.

The paper then defines the constrained generative process (Definition 2.2) by introducing a cache set $S_i \subset [n]$ , where $|S_i| = k$ for all $i$ (after the cache fills up—it grows naturally for the first $k$ steps because there are fewer than $k$ tokens to cache). The set $S_i$ specifies which of the previous $i$ tokens have their KV embeddings retained in memory. Tokens not in $S_i$ are treated as having key vectors of all zeros, which means they contribute zero to the dot-product pre-exponential scores and thus zero to the attention output. Formally:

$o_i := D_i^{-1} \cdot \exp(Q_{i,*} K_{S_i,*}^\top)$

where $K_{S_i,*} \in \mathbb{R}^{i \times d}$ is the key matrix with rows for tokens not in $S_i$ zeroed out, and

$D_i := (\exp(Q_{i,*} K_{S_i,*}^\top) - \mathbf{1}_{[i]\setminus S_i}) \cdot \mathbf{1}_i$

What this computes: the same attention vector as the unconstrained case, but with evicted tokens contributing nothing. The normalization $D_i$ subtracts $\mathbf{1}_{[i]\setminus S_i}$ because the exponentiated dot product for a zero key vector is $e^0 = 1$ , and these spurious ones must be removed to get the correct sum over actually-present tokens. Without this subtraction, the normalization would be too large, shrinking the attention weights of surviving tokens.

Why this form: this formulation makes explicit that eviction is not an approximation of the full attention—it is an exact computation under the constraint that some tokens are unavailable. The subtraction correction ensures that the softmax properties (non-negative, sum to 1) are preserved over the surviving tokens only.

The eviction policy (Definition 2.1) is then defined as a function $g: S_{i-1} \to S_i$ that updates the cache set at each step, subject to two constraints:

$|S_i| = k$ (cache size is constant after filling up); and
$|S_i \setminus S_{i-1}| \leq 1$ (at most one token is evicted per step—the new token is always added, so we must evict exactly one when the cache is full).

The goal (Remark 2.3) is to find an eviction policy such that the output of the constrained generative process is "similar or comparable to the original one without limiting the cache size." This is a sequential decision problem: the choice of which token to evict at step $i$ affects all future attention computations, not just the current one.

The paper explicitly notes that Belady's algorithm—which is optimal for standard CPU caches by evicting the block that will be needed furthest in the future—is "not necessarily for KV cache" (Section 1, footnote 1). The reason is subtle: in a CPU cache, a cache miss means you incur the cost of fetching the missing data, but the computation proceeds correctly once the data is loaded. In the KV cache, a "miss" means the token is permanently unavailable for all future steps—there is no fetching, because the token's embedding would need to be recomputed, which requires having the original input token and running all subsequent layers, violating the autoregressive dependency. The damage is permanent and propagates.

Empirical Foundation 1: Attention Sparsity at Inference Time

The first key observation that makes KV cache reduction feasible is that attention matrices in pretrained LLMs are highly sparse during inference, even though the models were trained with dense attention (Section 3.1, Figure 2a).

The experimental setup is straightforward: the authors run zero-shot inference with pretrained OPT models on the validation set of WikiText-103. For each attention head, they compute the full attention matrix $\text{Softmax}(QK^\top)$ , set a threshold at one percent of the maximum value in each row, and count what fraction of entries fall below this threshold. Formally, for each row $j$ , threshold $\tau_j = 0.01 \cdot \max_i \text{Softmax}(QK^\top)_{j,i}$ , sparsity of row $j$ is the fraction of entries below $\tau_j$ .

The result, visualized in Figure 2(a): "the resulting attention score matrices are highly sparse, with a sparsity over 95% in almost all layers." This means that for any given decoding step, the model genuinely attends to fewer than 5% of the available tokens with non-negligible weight—the remaining 95%+ contribute essentially nothing to the attention output.

Why this matters for cache design: if only 5% of KV embeddings are needed at each step, then in principle only 5% need to be stored. The challenge is that which 5% changes from step to step. A naive approach (keep only the top 5% at each step, evicting the rest) fails because the evicted tokens might be needed later. The paper's key insight is that there exists a small set of tokens that is consistently in that top 5% across many steps—the heavy hitters—and that retaining this set (which grows slowly over time) plus the most recent tokens (which are likely to be in the current step's top 5%) covers the vast majority of attention mass at all steps.

This sparsity observation is consistent with prior work on attention sparsity in DistillBERT (Likhosherstov et al., 2021) and bounded-norm self-attention heads (Edelman et al., 2022), but the paper is the first to connect it to KV cache design for autoregressive generation. The novelty is not the sparsity observation itself, but the recognition that sparsity enables a cache reduction if and only if you can identify the consistently important tokens.

Empirical Foundation 2: Heavy Hitters and Their Properties

The second observation—the one that actually enables the eviction policy—is that the accumulated attention scores of tokens follow a power-law distribution (Section 3.2, Figure 2b). The paper defines the accumulated attention score of a token as the sum of attention weights it receives from all subsequent tokens during generation, and finds that a small fraction of tokens accounts for a disproportionately large fraction of the total accumulated attention mass.

The experimental validation (Section 3.2) examines this through two analyses:

Accumulated attention vs. word frequency. For each word in the vocabulary, the authors compute the total accumulated attention score it receives across all positions and compare it to the word's co-occurrence frequency in the training data. Figure 2(b) shows a strong correlation (the red scatter points track the gray co-occurrence curve), suggesting that heavy hitters correspond to words that frequently co-occur with many other words—function words, discourse markers, and words that are structurally central to the text. This is an interpretive finding: it gives a linguistic explanation for why certain tokens become heavy hitters (they appear in many different contexts and are therefore relevant cross-context anchors), but the algorithm itself does not use word frequency information—it relies purely on the attention scores.

Functional importance verification. To confirm that heavy hitters are not merely a statistical curiosity but are functionally critical for generation, the authors run a simple ablation: they identify the heavy hitters using accumulated attention scores, then mask them out (treat their KV embeddings as zero) and observe the performance. Figure 2(c) shows that "the accuracy drops drastically, confirming the importance of those tokens"—models with heavy hitters removed suffer severe degradation across tasks (COPA, MathQA, OpenBookQA, PiQA, RTE, Winogrande), performing near or below random-guess levels on some benchmarks.

Why this matters: this establishes that heavy hitters are not just a convenient heuristic—they are causally necessary for correct generation. Removing them destroys model functionality, which means an eviction policy that preserves them is not just a good idea but a hard requirement. Equivalently, an eviction policy that accidentally evicts even a few heavy hitters will catastrophically degrade performance.

Local vs. global heavy hitters. A critical practical question is: can heavy hitters be identified using only information available at inference time (past attention scores), or do you need future information that is unavailable during generation? The paper tests this by comparing two variants (Figure 2d): "global statistic" (heavy hitters identified using attention scores from all tokens, both past and future—this requires the full sequence, so it is infeasible during autoregressive generation) and "local statistic" (heavy hitters identified using only attention scores from tokens generated so far). The result is striking: "local H2, which is calculated using local statistics at every decoding step by summing up the attention scores of the previous tokens, is equally effective as taking into account the attention of future tokens." The "Local" strategy (keeping only recent tokens, no heavy hitters) collapses in performance, while both H2 variants track the full-cache baseline.

This is what makes the approach deployable: you do not need to see the future to identify heavy hitters. The running sum of attention scores updates incrementally at each step, and tokens that are heavy hitters early in generation tend to remain heavy hitters throughout. The paper does not analyze why this temporal consistency holds (this would be an interesting direction for future work), but the empirical result is sufficient for the algorithm.

The H2O Eviction Algorithm

With these observations established, the paper presents the H2O eviction algorithm, which is a greedy procedure for maintaining a size- $k$ KV cache that balances heavy hitters (tokens with high accumulated attention scores) and recency (the most recently generated tokens). Algorithm 1 provides the pseudocode; Algorithm 2 in Appendix D provides a more detailed version with the formal score function.

Cache budget allocation. The total cache budget $k$ is split evenly: $k/2$ slots for heavy hitters and $k/2$ slots for the most recent tokens. The paper does not extensively justify this 50/50 split—it appears to be a design choice that works well empirically across tasks. Appendix C.6 (Table 9) shows an ablation where heavy hitters alone or recent tokens alone perform substantially worse than their combination, confirming that both components are necessary but not revealing whether a different split (e.g., 70/30) might be better. The even split is simple and effective, and the paper leaves exploration of the optimal ratio to future work.

Per-step operation (warm-up phase). For the first $k$ decoding steps (when fewer than $k$ tokens exist, so the cache is not yet full), the algorithm simply adds each new token to the cache without evicting anything. This is the "prefix filling" or "prefill" phase: $S_i \leftarrow S_{i-1} \cup \{i\}$ .

Per-step operation (steady-state phase). Once the cache contains $k$ tokens (step $i > k$ ), each new decoding step triggers the following sequence of operations:

Compute attention scores for the new query. The model's query vector $Q_{i,*}$ for the current token computes dot products against the cached key vectors $K_{S_{i-1},*}$ , yielding a vector of scores. These are exponentiated and normalized to produce the current-step attention vector: $o_i \leftarrow D_i^{-1} \cdot \exp(Q_{i,*} K_{S_{i-1},*}^\top)$ where $D_i$ is the normalization constant with the correction for evicted tokens (as defined in Section 2.1). The vector $o_i$ has length $i$ (the total number of tokens generated so far), but entries for tokens not in $S_{i-1}$ are zero.
Update accumulated scores. The paper defines the accumulated score for token $s$ as the sum of attention weights it has received from all tokens generated after it. At step $i$ , we have: $\tilde{o}_i \leftarrow \tilde{o}_{i-1} + o_i$ where $\tilde{o}_i \in \mathbb{R}^i$ is the vector of accumulated scores up to step $i$ (with positions beyond $i$ padded to zero). In practice, the implementation maintains a single vector that gets updated at each step, rather than storing all $n$ vectors (see Remark D.15).
Define the score function. The algorithm uses a score function to evaluate how "valuable" any subset of tokens is for retention. The paper's formal version (Algorithm 2) uses: $F_{\text{score}}(T) := h\left(\sum_{s \in T} \tilde{o}_{i,s}\right)$ where $\tilde{o}_{i,s}$ is the accumulated attention score of token $s$ up to step $i$ , $T$ is a candidate set of tokens to retain, and $h: \mathbb{R} \to \mathbb{R}$ is a non-decreasing concave function.

What this computes: for any set of tokens $T$ , this function sums their accumulated attention scores and applies a concave transformation $h$ . A concave $h$ (e.g., $h(z) = \sqrt{z+1}$ or $h(z) = \log(z+1)$ ) encodes diminishing returns—adding a token to an already-large set increases the score less than adding it to a small set. This is what yields the submodular property discussed in the theoretical analysis.

Why this form: the concave $h$ is the mathematical mechanism that makes greedy selection near-optimal. If $h$ were linear ( $h(z) = z$ ), the function would be modular (additive), and greedy selection would be trivially optimal but would also be equivalent to simply keeping the top- $k$ tokens by raw accumulated score—which would fail to account for redundancy among tokens. The concave transformation penalizes redundancy: if two tokens receive high attention scores but always appear together (high correlation), keeping both provides less marginal value than keeping one plus a token with an independent contribution. In the informal Algorithm 1, the paper uses $h(z) = z$ for simplicity of exposition, but the theoretical guarantees in Appendix D are proven for non-decreasing concave $h$ .
Select the token to evict. The algorithm constructs the candidate set $G_i = S_{i-1} \cup \{i\}$ (the old cache plus the new token), and selects the token $u$ whose removal maximizes the score of the remaining set: $u \leftarrow \arg\max_{v \in G_i} F_{\text{score}}(S_{i-1} \cup \{i\} \setminus \{v\})$

In words: we try removing each token in the candidate set, compute the score of the cache after removal, and pick the token whose removal leaves the highest-scoring cache. Equivalently, this selects the token whose marginal contribution to the current set's score is smallest—the token the cache needs least.

Why this operation: this is the standard greedy step for submodular maximization with a cardinality constraint. The theoretical analysis (Appendix D, Corollary D.18, Lemma D.30) shows that if $F_{\text{score}}$ is submodular (which concave $h$ ensures), this greedy selection achieves a $(1 - 1/e)$ approximation ratio relative to the optimal size- $k$ set. The algorithm does not need to evaluate all $2^k$ subsets—it only needs to evaluate $|G_i| = k+1$ candidate removals per step, which is linear in the cache size.
Update the cache. The new cache is $S_i \leftarrow (S_{i-1} \cup \{i\}) \setminus \{u\}$ —add the new token, remove the least-valuable existing token. Note that the new token itself can be immediately evicted if it is deemed less valuable than all existing tokens. In practice, this rarely happens with a concave $h$ because brand-new tokens have low accumulated scores (they have only received attention from the current token) compared to tokens that have accumulated scores across many steps. The concave $h$ mitigates this bias somewhat (diminishing returns mean that old tokens with very high accumulated scores have lower marginal value than their raw scores suggest), but the recency allocation (the $k/2$ slots reserved for recent tokens) provides a more direct mechanism to ensure new tokens are retained temporarily.

The dual-buffer architecture. The algorithm's "balance of recent and H2 tokens" is implemented as a dual-buffer structure within the cache (Appendix A). The cache memory is preallocated as a contiguous block, and the implementation maintains two logical regions:

Heavy hitter region (first $k/2$ slots): tokens are evicted from this region using the greedy score-based policy described above. Over time, this region converges to the set of tokens with the highest accumulated attention scores.
Local region (last $k/2$ slots): implemented as a circular queue. The oldest token in this region is evicted when a new token arrives, regardless of its accumulated attention score. This ensures that the most recent $k/2$ tokens are always available, even if their accumulated scores are low (which they will be initially, since they haven't had time to accumulate attention from future tokens).

The per-head, per-layer independence (Appendix C.9) means that each attention head in each layer maintains its own separate heavy-hitter set. Token position 5 in head 3 of layer 7 might be a heavy hitter, while the same token position in head 5 of the same layer might be evicted. This is important because the paper's initial analysis (Figure 2) shows that heavy hitters vary across heads and layers—aggregating scores across heads, as prior work like SpAtten did, loses this heterogeneity and yields worse cache decisions (Table 11 shows H2O outperforming SpAtten by 2 percentage points on COPA with the same budget).

Theoretical Framework: Dynamic Submodular Maximization

The paper formalizes the KV cache eviction problem as a variant of submodular maximization, which is the mathematical machinery that provides theoretical guarantees for the greedy algorithm. This is developed in detail in Appendix D; the main text (Section 4) provides the high-level argument.

What is submodularity? A set function $f: 2^{[n]} \to \mathbb{R}$ is submodular if it satisfies the diminishing returns property: for any sets $X \subseteq Y$ and any element $x \notin Y$ , $f(X \cup \{x\}) - f(X) \geq f(Y \cup \{x\}) - f(Y)$

In plain language: adding an element to a smaller set provides at least as much benefit (marginal gain) as adding it to a larger set. This property captures the intuition that tokens become partially redundant—if you already have many good tokens, adding one more provides less additional value than if you had few tokens to begin with. Submodular functions are ubiquitous in machine learning applications where there is a natural notion of coverage or information content (Krause and Guestrin, 2008; Bilmes, 2015).

Why submodularity is a good model for attention scores. The paper argues (Appendix D.7) that the attention score function should be submodular because of redundancy among tokens:

"we introduce a new token, denoted as 'w', into two sets, S and S0, where the concepts covered by S0 are a subset of those covered by S. By intuition, the information added to S0 by 'w' should be larger compared to adding it to S, as the new concepts carried by 'w' might have already been covered by the concepts present in S but not in S0."

The concave $h$ in $F_{\text{score}}(T) = h(\sum_{s \in T} \tilde{o}_{i,s})$ explicitly encodes this diminishing-returns property. Without concavity (e.g., with linear $h$ ), the function would be modular—each token's contribution would be independent, and the optimal cache would simply be the $k$ tokens with the highest individual accumulated scores, with no consideration of redundancy. But tokens in natural language are highly redundant (e.g., two tokens might both be function words that serve similar structural roles), so a modular model overestimates the value of keeping both.

The dynamic submodular framework. Standard submodular maximization considers a single fixed function $f$ and asks for the best size- $k$ subset of a ground set. But in the KV cache setting, the function changes at each step—the accumulated scores $\tilde{o}_i$ are updated, and tokens that were not heavy hitters at step $i$ might become heavy hitters at step $i+1$ . The paper defines the dynamic submodular framework (Definition 4.1, formal version in Definition D.4):

$F: 2^{[n]} \times [n] \times 2^{[n]} \to \mathbb{R}$

where $F(Z, i, \cdot)$ is a submodular function for any fixed $Z$ (the current cache set) and $i$ (the current step). In the H2O instantiation, $Z = S_{i-1}$ (the previous cache), $i$ is the current step index, and the third argument is the candidate set being evaluated.

The key difference from standard submodular maximization is that the function evolves. A greedy choice that was optimal for $F(S_{i-1}, i, \cdot)$ might not be optimal for $F(S_i, i+1, \cdot)$ because the scores have changed. The theoretical analysis (Appendix D.12–D.14) bounds how much the function can change per step and shows that the greedy algorithm maintains its approximation guarantee under mild assumptions about the rate of change.

The approximation guarantee (Theorem 4.4, formal version in Theorem D.32). Under the assumptions that:

The score function $F$ is submodular and monotone (adding more tokens never decreases the score);
The dynamics are "slow" relative to the step size—the optimal set's value does not decrease by more than a factor $(1-\gamma)$ per step, and the function's value on the same set changes by at most a factor $(1-\theta)$ per step (these are the Universal Dynamic Conditions in Appendix D.11);
The greedy algorithm has access to an approximation $\tilde{F}$ of the true function $F$ , with error at most $\epsilon_0$ per evaluation (the "approximate function" setting, corresponding to using local rather than global statistics);

then the cache $S_i$ maintained by the greedy algorithm satisfies:

$f(\tilde{S}_i) \geq (1 - 1/e) \cdot (1 - \alpha) \cdot \text{opt}_i - \beta$

where $\text{opt}_i$ is the optimal achievable score at step $i$ with a size- $k$ cache, $e \approx 2.718$ is Euler's number (so $1 - 1/e \approx 0.632$ ), and $\alpha, \beta > 0$ are parameters that depend on the rate of dynamic change and the approximation error.

What this means operationally: the greedy algorithm is guaranteed to achieve at least ~63% of the optimal score (minus a penalty for dynamics and approximation error), even though it makes irrevocable eviction decisions with only local information. The guarantee is weaker than the standard $(1-1/e)$ guarantee for static submodular maximization (Nemhauser et al., 1978) because the dynamic and approximate nature of the problem introduces additional slack ( $\alpha$ and $\beta$ ), but it provides a principled justification for why a simple greedy algorithm should work well—it is not just a heuristic, it is provably near-optimal under reasonable assumptions.

Why this theoretical framing matters (and why it is partially aspirational). The paper is careful not to claim that all LLM attention functions satisfy the submodularity assumption—it is presented as a "mild assumption" that provides a theoretical lens for understanding why the greedy policy succeeds. The empirical results (Figures 2–4, Tables 1–2) are the primary evidence for H2O's effectiveness; the theory provides a conceptual framework and could guide future algorithm design (e.g., choosing $h$ to better satisfy the concavity requirement, or developing better approximation algorithms if the submodularity assumption fails in certain regimes).

System Implementation Details

The theoretical algorithm must be implemented efficiently to deliver actual throughput and latency gains—an eviction policy that reduces memory but adds computational overhead defeats its purpose. The paper describes several implementation choices (Section 4.2, Appendix A) that make H2O practical.

Integration with FlexGen. H2O is implemented on top of FlexGen (Sheng et al., 2023), a high-throughput LLM inference engine that uses a "white-box" implementation of OPT models (meaning the KV cache handling code is exposed and modifiable, unlike black-box frameworks where the cache is managed internally). FlexGen already provides optimizations like CPU offloading and weight quantization; H2O is described as "orthogonal to existing optimizations" and can be combined with them for compounding gains.

Preallocated memory with zero-copy eviction. Rather than dynamically allocating and deallocating memory when tokens are evicted and added (which would incur allocation overhead and memory fragmentation), the implementation preallocates a contiguous block of memory for the KV cache at the start of generation (Appendix A: "in order to avoid data movement in memory, the memory for KV cache is preallocated"). When a token is evicted, its slot is directly overwritten with the new token's KV embeddings—there is no data movement, no pointer updates, and no garbage collection. The only bookkeeping is updating which logical indices map to which physical slots.

Circular queue for the local region. The $k/2$ slots for recent tokens are managed with a circular queue data structure (Appendix A: "We use a circular queue to update the last $K$ entries efficiently"). A pointer tracks the "oldest" slot in the local region; when a new token arrives, it overwrites that slot, and the pointer advances. This is $O(1)$ per step, with zero cache misses.

Per-head, per-layer independence. H2O maintains separate heavy-hitter sets for each attention head in each layer, operating independently (Appendix C.9 contrasts this with SpAtten, which aggregates scores across heads). This means the algorithm runs once per head per layer per decoding step. For a model with $L$ layers and $H$ heads per layer (e.g., OPT-30B has $L=48$ and $H=56$ ), this is $L \times H$ independent invocations of the eviction logic per generated token. The independence is important for two reasons: (1) it captures head-specific importance patterns, which the paper shows are heterogeneous, and (2) it means the eviction computation is embarrassingly parallel across heads and layers—there are no dependencies between one head's eviction decisions and another's.

The score accumulation vector. The implementation maintains a single vector of accumulated attention scores per head, updated at each step (Remark D.15): rather than storing all $n$ vectors $\tilde{o}_1, \dots, \tilde{o}_n$ , it keeps one growing vector $\tilde{o}_i$ that gets extended with each new token. The update is simply $\tilde{o}_i \leftarrow \text{concat}(\tilde{o}_{i-1}, 0) + o_i$ , where $o_i$ is the attention vector from the current step (padded with zeros for tokens not in the cache). This is $O(k)$ per step (the number of nonzero entries in $o_i$ is at most $k$ , the cache size).

Overhead characterization. The paper does not provide a detailed breakdown of the eviction policy's computational overhead as a fraction of total inference time, but it does claim that the policy is "low-cost" (Section 1, Section 4). The throughput and latency results (Tables 3–5) include the eviction overhead in end-to-end measurements—the reported speedups (up to 29× over DeepSpeed, 3× over FlexGen) are net gains after accounting for the policy's cost. The fact that H2O achieves up to 1.9× lower latency than FlexGen at the same batch size (Table 5: 57.0s vs. 50.4s for 7000+1024 generation on OPT-30B) implies the policy overhead is small compared to the memory-access savings from having a smaller cache.

Handling the prefill phase. During the prompt processing (prefill) phase—when the model processes the input prompt and builds the initial KV cache—no tokens are evicted (the cache simply fills up). The eviction policy only activates during the token generation phase. This means the prompt length must be less than or equal to the cache budget $k$ to avoid loss of information from the prompt itself. For short prompts, this is fine; for very long prompts (e.g., 2048+ tokens), the cache budget must be increased proportionally, attenuating the memory savings. The paper reports results with prompt lengths up to 7000 tokens (Table 5), suggesting the cache budget was set to at least that size for those experiments. The infinite-length experiments (Section 5.3, Q1) with four million tokens are a special case discussed separately (they combine H2O with the StreamLLM attention-sink mechanism).

The four-million-token streaming experiment. Section 5.3, Q1 shows that H2O can handle sequences of up to four million tokens by integrating with the StreamLLM technique (Xiao et al., 2023), which retains the first few tokens as "attention sinks" and uses position rolling in the KV cache. The H2O variant for infinite-length inputs uses the heavy-hitter selection to choose which tokens to retain in the middle of the sequence (the region that StreamLLM would otherwise discard), while the attention sink and local windows are handled by the StreamLLM mechanism. The key result (Figure 5, bottom) is that H2O + StreamLLM achieves lower perplexity than the original StreamLLM across various cache sizes on PG-19 text, demonstrating that the heavy-hitter selection provides a better policy than StreamLLM's simpler eviction for the middle-of-sequence region.

Design Choice Summary and Justifications

Why greedy rather than optimal? The optimal eviction policy is a combinatorial search over exponentially many sequences of cache sets, which is computationally intractable (NP-hard in general). The greedy algorithm evaluates only $k+1$ candidate removals per step and is provably near-optimal under the submodularity assumption. It is also simple to implement: one argmax over $k+1$ elements per head per layer per step.

Why accumulated scores rather than instantaneous scores? A policy that evicts tokens based on their attention score at the current step only would be myopic—a token that is unimportant at step $i$ might become critical at step $i+5$ . Accumulated scores smooth out this noise and identify tokens that are consistently important across many steps. The paper's Figure 2(d) shows that accumulated (local) scores are "equally effective as taking into account the attention of future tokens," validating this design.

Why split evenly between heavy hitters and recent tokens? Recent tokens benefit from the recency bias in language: the current token is most strongly correlated with nearby tokens in the sequence. The sliding window ensures these tokens are always available, even before they have had time to accumulate high scores. The heavy-hitter region retains long-range dependencies that would be lost if only recent tokens were kept. Table 9 confirms that each component individually underperforms the combination.

Why per-head, per-layer independence? Figure 10 (Appendix C.8) shows that the H2 distributions differ across layers—some layers have more concentrated heavy hitters, others are more diffuse. Aggregating across heads (as SpAtten does) loses this heterogeneity and produces suboptimal eviction decisions. The cost of independence is $L \times H$ parallel eviction operations per step, which is acceptable given GPU parallelism.

Why the concave $h$ in the score function? Without concavity, the score function is modular, and the greedy algorithm simply keeps the top- $k$ tokens by raw accumulated score—ignoring redundancy. Concavity (e.g., $h(z) = \sqrt{z+1}$ ) encodes the diminishing-returns property that makes the function submodular, which is what enables the theoretical guarantee and, empirically, likely prevents the cache from filling up with redundant tokens that all have high scores for the same reason.

Why preallocation and zero-copy eviction? Dynamic memory allocation in GPU kernels is expensive and can cause fragmentation. Preallocating the cache as a fixed-size buffer and overwriting evicted slots in-place avoids both problems and has predictable performance characteristics. The tradeoff is that the cache size $k$ must be chosen before generation starts and cannot adapt; the paper does not explore adaptive cache sizing.

4. Key Insights and Innovations

Innovation 1: Difficulty-Conditioned Compute-Optimal Test-Time Scaling

The paper's most fundamental contribution is not any single method but rather the meta-strategy of adaptively allocating test-time compute based on prompt difficulty. Prior work treated test-time compute as a uniform knob: turn it up (more samples, more search) and performance improves. This paper demonstrates that the relationship between compute and performance is qualitatively different depending on problem difficulty, and that ignoring this heterogeneity leaves enormous efficiency on the table.

What makes this genuinely novel—rather than an obvious observation—is that the difficulty-dependent behavior is often counterintuitive. Beam search, the strongest optimizer, actually hurts performance on easy problems at high budgets due to verifier over-optimization (Figure 3, right), while it helps substantially on medium-difficulty problems. Similarly, sequential revisions dominate on easy problems but a balanced sequential-parallel ratio is optimal on hard ones (Figure 7, right). These are not monotonic relationships where "more powerful = better." The compute-optimal policy exploits these non-monotonicities to achieve $4\times$ better efficiency than best-of-N (Figures 4 and 8), which is a significant practical gain.

This contribution is best understood as an inference-time analog of the Chinchilla scaling laws for pretraining. Just as Hoffmann et al. (2022) showed that the optimal allocation of pretraining compute between model size and data quantity varies with total budget, this paper shows that the optimal allocation of test-time compute between search strategies varies with problem difficulty. The conceptual parallel is direct, but the underlying mechanism is entirely different—pretraining scaling laws optimize over continuous variables (parameters, tokens), while this paper optimizes over a discrete, combinatorial space of strategy hyperparameters conditioned on a difficulty estimate.

A subtle but important point: the predicted (non-oracle) difficulty bins perform nearly as well as oracle bins (the curves largely overlap in Figures 4 and 8). This is what makes the contribution practical rather than merely analytical. If the gains required ground-truth labels to estimate difficulty, the approach would be circular. The fact that the PRM's own score distribution serves as a sufficient proxy means the system is deployable without access to answers.

Innovation 2: The Proposal Distribution and Verifier as Complementary, Independent Scaling Axes

The unifying framework in Section 2—decomposing all test-time compute methods into modifications to the proposal distribution (what the model generates) versus the verifier (how outputs are selected)—is not itself technically novel. It echoes the proposer-scorer decomposition familiar from MCMC and reinforcement learning. What is novel is the paper's empirical demonstration that these two axes have complementary, difficulty-dependent strengths and that combining them yields gains neither achieves alone.

Concretely: revisions (proposal modification) are most effective on easy problems where the model's initial output is roughly correct and just needs refinement—a local search in answer space. Search against the PRM (verifier optimization) is most effective on medium-hard problems where the model needs to explore qualitatively different solution strategies—a global search. Prior work studied these mechanisms in isolation, often reaching pessimistic conclusions (e.g., "LLMs cannot self-correct reasoning" from Huang et al., 2023). This paper's framework reconciles those findings: self-correction does work, but only on the right difficulty tier. Search does help, but only with the right algorithm at the right budget. The conflicting prior results were an artifact of testing different methods on different (implicitly difficulty-biased) problem distributions.

This insight is more than taxonomic. It implies that future systems should not choose between revisions and search but should deploy both, switching between them per-prompt. The paper doesn't fully realize this vision (Section 8 acknowledges that PRM tree-search was not combined with revisions), but the framework provides the intellectual scaffolding for doing so.

Innovation 3: Empirical Evidence That Test-Time Compute Can Substitute for Pretraining—With Sharp Boundaries

The FLOPs-matched comparison in Section 7 is, to the authors' knowledge, the first to demonstrate in a realistic setting (no ground-truth access at inference) that a smaller model with additional test-time compute can outperform a ~14× larger model on problems within its capability range. This is significant not as a method but as an empirical finding with direct implications for how compute budgets should be allocated in production systems.

What distinguishes this from prior work on training-inference tradeoffs (Jones, 2021; Villalobos and Atkinson, 2023) is the specificity of the finding. The paper doesn't claim a universal substitution—it precisely characterizes where the substitution works (easy-to-medium problems, low $R$ regimes) and where it fails (hard problems, high $R$ regimes). The failure case is equally informative: on the hardest problems (bin 5), test-time compute provides essentially zero benefit regardless of budget, meaning that some capabilities can only be acquired through pretraining, not recovered at inference time. This establishes a clear boundary condition: test-time compute amplifies existing capability but does not create it from nothing.

The dependence on $R = D_{\text{inference}} / D_{\text{pretrain}}$ adds practical nuance that prior analyses missed. For self-improvement pipelines where $R \ll 1$ , the case for test-time compute is strong. For high-throughput production deployments where $R \gg 1$ , the case weakens because the per-query inference cost of the larger model dominates the budget anyway. This is an incremental but practically important refinement of the training-inference tradeoff picture.

Innovation 4: Verifier Over-Optimization as a First-Class Phenomenon in Test-Time Scaling

While reward hacking / over-optimization is well-documented in the RLHF literature, this paper provides some of the first clear evidence that the same phenomenon governs test-time search scaling and is the primary bottleneck preventing unbounded improvements from additional compute. The evidence is concrete: beam search degrades easy-problem performance at high budgets (Figure 3, right); lookahead search—the most powerful optimizer—paradoxically performs worst overall (Figure 3, left); and qualitative examples in Appendix M show search producing degenerate outputs (repetitive low-information steps, overly short solutions) that score highly under the PRM.

This finding is significant because it shifts the narrative around test-time compute from "more is better" to "more is better only up to the verifier's reliability frontier." It explains why prior work found negative results for sophisticated search methods: those studies likely pushed past the over-optimization threshold. It also implies that improving verifier robustness is the key bottleneck for further scaling test-time compute, not improving search algorithms. The paper's compute-optimal policy can be understood partly as a way to stay below the over-optimization threshold per difficulty level—using weaker optimization (best-of-N) where the verifier is reliable (easy problems) and stronger optimization (beam search) only where the verifier signal has more room to provide genuine guidance (medium problems).

5. Experimental Analysis

Evaluation Methodology

Dataset. The paper evaluates on eight tasks sampled from two popular benchmarks: six multiple-choice reasoning tasks (COPA, MathQA, OpenBookQA, PiQA, RTE, Winogrande) from the lm-eval-harness framework (Gao et al., 2021) under 5-shot inference, and two long-form generation tasks (XSUM, CNN/Daily Mail) from the HELM framework (Liang et al., 2022) under zero-shot inference with 1000 test samples each. For throughput measurements, synthetic datasets with padded prompts are used, plus XSUM for real-world throughput assessment. The infinite-length streaming experiments use PG-19 (Rae et al., 2020).
Base model(s). Three model families across a wide size range: OPT (Zhang et al., 2022) at sizes 6.7B, 13B, 30B, 66B, and 175B; LLaMA (Touvron et al., 2023) at 7B, 13B, and 30B; and GPT-NeoX-20B (Black et al., 2022). The paper states OPT is chosen because it is "representative of the capabilities of many contemporary LLMs" and has publicly available weights. The models span both dense and efficient architectures, covering the deployment regimes where KV cache bottlenecks are most acute.
Metrics. For reasoning and generation tasks, the primary metric is task-specific accuracy (exact match for multiple-choice, ROUGE/BLEU for summarization, as graded by the respective framework's evaluation scripts). For throughput experiments, the metric is generation throughput in tokens/second, defined as (number of generated tokens) / (prompt processing time + decoding time). For latency experiments, end-to-end latency in seconds. For the infinite-length streaming experiment, perplexity on PG-19 is used. The paper also reports Self-BELU (Zhu et al., 2018) as a diversity metric in Appendix C.1.
Baselines.
- Full KV cache: the unmodified model with all key-value embeddings retained (upper bound on accuracy).
- Local: retains only the most recent $k$ tokens in the KV cache. This is the simplest eviction strategy and serves as the primary baseline for all accuracy experiments.
- Sparse Transformer (strided): the strided sparsity pattern from Child et al. (2019), where each query attends to every $s$ -th token (with $s$ chosen to match the cache budget) plus local tokens.
- Sparse Transformer (fixed): a variant with a fixed sparsity pattern.
- 0-shot / 1-shot Full: the full-cache model with fewer in-context examples, providing a comparison point with similar total sequence length to the 5-shot H2O configuration at 20% budget.
- SpAtten (Wang et al., 2021): an attention pruning method that accumulates attention scores across heads and layers for token selection (compared in Appendix C.9).
- StreamLLM (Xiao et al., 2023): an attention-sink-based method for infinite-length inputs (compared in Appendix C.4 and Figure 5).
- Top-K: retains the top- $k$ tokens by instantaneous attention score at each step (compared in Appendix C.5).
- For throughput experiments: DeepSpeed ZeRO-Inference (Aminabadi et al., 2022), Hugging Face Accelerate, and FlexGen (Sheng et al., 2023).
Generation budget / compute accounting. The cache budget $k$ is specified as a percentage of the prompt length (4%, 10%, 20%, 60%, or 100%). The 20% budget means the KV cache stores embeddings for at most 20% of the total tokens that would be stored in a full cache. Within this budget, the allocation is split evenly: $k/2$ slots for heavy hitters and $k/2$ slots for recent tokens. Throughput measurements use the same budget percentage and report end-to-end performance including both the prefill phase (prompt processing) and the generation phase (token-by-token decoding), incorporating the computational cost of the H2O eviction policy itself. Prompt and generation lengths are matched across systems for fair comparison.
Cross-validation / statistical protocol. No cross-validation is reported for the accuracy experiments—results are reported on the standard test splits of each benchmark. For the throughput experiments, measurements include all overhead (memory allocation, eviction computation, cache management), reported as end-to-end metrics. The paper does not report confidence intervals or statistical significance tests for accuracy differences.

Main Quantitative Results

End-to-End Accuracy with Reduced KV Cache

The central accuracy result appears in Figure 4 and Table 1. With a 20% KV cache budget (5× memory reduction), H2O matches full-cache accuracy on a majority of benchmarks. Specific comparisons from Table 1 using OPT-30B: on COPA, H2O achieves 84.00% vs. 85.00% for full cache (a 1-point gap); on OpenBookQA, 43.00% vs. 43.20% (a 0.2-point gap); on PiQA, 78.45% vs. 78.51%; on Winogrande, 69.06% vs. 70.24% (a 1.18-point gap). In some cases, H2O exceeds full-cache performance: on COPA with OPT-66B at 20% budget, H2O achieves 85.00% vs. 81.00% for the full cache (a 4-point improvement, attributed to a regularization effect). On MathQA with OPT-30B, H2O reaches 26.87% vs. 26.23% for the full cache.

The degradation of the Local baseline is catastrophic: on COPA with OPT-30B at 20% budget, Local achieves 48.00% (vs. 85.00% for full, a 37-point gap). On OpenBookQA, Local scores 25.20% vs. 43.20% full (18-point gap). On Winogrande, Local scores 49.17% vs. 70.24% full (21-point gap). This gap demonstrates that recency alone is insufficient—the heavy hitters carry information that cannot be recovered from the most recent tokens.

The 0/1-shot comparison (Table 1) shows that H2O with a 20% budget and 5-shot prompts (which gives ~1.2 samples per input on average) outperforms both 0-shot full (1 sample) and 1-shot full (2 samples) across multiple tasks. On COPA: H2O 85.00% vs. 0-shot 76.00% and 1-shot 76.00%. On Winogrande: H2O 71.67% vs. 0-shot 70.00% and 1-shot 70.24%. This demonstrates that the memory savings from H2O do not simply come from reducing the number of in-context examples—H2O preserves the multi-shot benefit while using dramatically less memory.

Enhanced Compatibility with Sparse Attention Baselines

Table 2 shows a striking interaction: combining H2 (heavy hitters) with existing sparse attention methods rescues them from collapse at low cache budgets. With OPT-30B at a 20% budget:

Sparse Transformer (strided) without H2: COPA 50.00%, OpenBookQA 24.60%, PiQA 56.20%, Winogrande 47.59%. These are 25–35 points below full-cache performance.
Sparse Transformer (strided) with H2: COPA 83.00%, OpenBookQA 42.60%, PiQA 78.24%, Winogrande 69.61%. These are within 1–3 points of full-cache performance.

Similar rescue effects hold for the fixed sparsity pattern: COPA goes from 61.00% (without H2) to 76.00% (with H2); OpenBookQA from 23.80% to 41.40%; PiQA from 58.60% to 77.80%. The interpretation is that fixed sparsity patterns miss the dynamic importance structure that H2 captures—adding H2 tokens to the sparse attention pattern restores the missing information. The paper also shows that H2 can enhance the Top-K baseline (Table 8, Appendix C.5), with Top-K + H2 achieving up to 2 points higher accuracy than Top-K alone across four tasks.

Long-Form Generation Results

Figure 4 (bottom rows) shows results for summarization tasks (XSUM, CNN/Daily Mail) across LLaMA-7B, LLaMA-13B, LLaMA-30B, and GPT-NeoX-20B. On XSUM with LLaMA-7B, H2O at 20% budget achieves comparable performance to the full cache, while the Local strategy actually collapses at 60% budget—the curve for Local on XSUM with LLaMA-13B shows complete failure at 60% (near-zero performance), demonstrating that some tasks are fundamentally dependent on long-range dependencies that the local window alone cannot capture. On CNN/Daily Mail with LLaMA-7B, Local collapses at 60% budget while H2O remains stable at 20%. These results establish that the heavy-hitter phenomenon generalizes beyond multiple-choice tasks to open-ended generation requiring coherence across long contexts.

Throughput and Latency Gains

Tables 3 and 4 report generation throughput on an NVIDIA T4 GPU (16GB memory, representative of resource-constrained deployment). The improvements are dramatic:

Compared to Hugging Face Accelerate: H2O (20%) achieves 35.1 tok/s vs. 20.4 tok/s on OPT-6.7B with 512+32 sequence length—a 1.7× improvement at the same batch size, and up to 29× improvement when the reduced memory enables larger batch sizes (Table 3, OPT-30B with 512+32: H2O achieves 12.7 tok/s with batch 728 vs. Accelerate at 0.6 tok/s with batch 8; the effective throughput ratio is 12.7 / 0.6 ≈ 29× after accounting for batch size differences—the paper explicitly reports "up to 29×" in the abstract).
Compared to DeepSpeed: similarly up to 29× improvement (H2O 12.7 tok/s with batch 728 vs. DeepSpeed 0.6 tok/s with batch 4 on OPT-30B with 512+32).
Compared to FlexGen: up to 3× improvement (H2O 12.7 tok/s with batch 728 vs. FlexGen 8.1 tok/s with batch 144 on OPT-30B with 512+32).

The mechanism for these gains is twofold: (1) reduced memory per token allows larger batch sizes (e.g., from batch 144 to batch 728 on OPT-30B with 512+32), and (2) reduced memory can eliminate the need for CPU offloading entirely (e.g., on OPT-6.7B with 512+32, FlexGen requires GPU-only mode with batch 2, while H2O fits batch 4 on GPU).

On real-world data (XSUM, Table 4), the gains are consistent: H2O achieves 30.40 tok/s vs. Accelerate 11.98 tok/s on OPT-6.7B (2.5×), and 6.70 tok/s vs. FlexGen 3.29 tok/s on OPT-30B (2.0×).

Long-sequence results on A100 (Table 5): with sequence lengths from 4K to 10K, H2O at 20% budget reduces latency by 1.1–1.9× compared to FlexGen at the same batch size (e.g., 50.4s vs. 57.0s for 7000+1024 on OPT-30B, batch 1; 155.4s vs. 214.2s for 5000+5000 on LLaMA-13B, batch 4). With the memory savings enabling larger batch sizes, H2O achieves 2.3× higher throughput on OPT-6.7B with 2048+2048 (918.9 tok/s with batch 24 vs. 494.1 tok/s with batch 24 for FlexGen, and 1161.0 tok/s with batch 64 where FlexGen runs out of memory).

Infinite-Length Streaming

Figure 5 (Section 5.3, Q1) shows that H2O can handle inputs with sequence lengths up to four million tokens by integrating with StreamLLM. The bottom panel compares perplexity between the original StreamLLM method and H2O across different cache sizes on the first text sample of PG-19. H2O consistently achieves lower perplexity (better performance) than StreamLLM at matched cache sizes. The upper panel illustrates the streaming mechanism: H2O selects which middle-of-sequence tokens to retain using the heavy-hitter criterion, while StreamLLM's attention-sink and local-window mechanisms handle the sequence endpoints.

Ablation Studies and Robustness Checks

Separate effects of heavy hitters vs. local tokens (Table 9, Appendix C.6): Retaining only heavy hitters without local tokens degrades performance significantly compared to H2O. On PiQA with OPT-30B: heavy hitters alone 67.25%, local tokens alone 55.82%, H2O (both) 78.45%. On Winogrande: H2 alone 47.36%, Local alone 49.17%, H2O 69.06%. The heavy-hitter-only configuration consistently outperforms the local-only configuration (e.g., PiQA OPT-13B: H2 76.12% vs. Local 54.62%; MathQA OPT-30B: H2 21.98% vs. Local 20.87%), suggesting heavy hitters contribute more to performance preservation than recent tokens, but both are necessary.
Number of shots during inference (Table 10, Appendix C.7): H2O at 20% budget is effective across 5-shot and 10-shot configurations, with differences from full-cache performance below 1.00% across OPT-30B and OPT-66B on OpenBookQA, COPA, and MathQA. The Local strategy degrades significantly at higher shot counts (e.g., COPA OPT-30B 10-shot: Local 60.00% vs. Full 86.00%, a 26-point gap).
Zero-shot and one-shot inference (Figure 8, Appendix C.3): H2O with a 20% budget matches full-cache performance under 0-shot and 1-shot settings on PiQA, COPA, OpenBookQA, and Winogrande with LLaMA-7B. Some tasks require a higher budget (30–40%) to match full-cache in the zero/one-shot setting, which the paper attributes to shorter prompt lengths (100–300 tokens) where the absolute number of retained tokens is very small at a 20% budget.
Compatibility with quantization (Table 6, Section 5.3, Q3): H2O combined with 4-bit KV cache quantization achieves matching or slightly better accuracy than either technique alone. On OPT-30B: H2O alone (COPA 84.00%, OpenBookQA 43.00%, PiQA 78.45%); Quant-4bit alone (84.00%, 43.28%, 78.67%); H2O + Quant-4bit (84.00%, 43.20%, 78.80%). The throughput gains from combining H2O with weight quantization are substantial but partially limited by inefficient quantization kernels in the implementation (Table 7, Appendix C.2): H2O + 4-bit compression achieves 50.5 tok/s vs. H2O 35.1 tok/s on OPT-6.7B with 512+32, despite enabling a 17.5× larger batch size (70 vs. 4)—the paper notes that "the implementation of 4-bit quantization could be accelerated by an optimized CUDA kernel."
Enhancing the Top-K baseline (Table 8, Appendix C.5): Adding heavy hitters to a Top-K selection strategy improves accuracy by up to 2 points across four tasks (e.g., COPA: TopK 80.00% → TopK + H2 82.00%; PiQA: 76.96% → 77.96%), demonstrating that H2 provides complementary information beyond what instantaneous top-K selection captures.
Comparison with StreamLLM for long-context tasks (Figure 9, Appendix C.4): H2O substantially outperforms StreamLLM on multi-document question answering and text summarization tasks where critical information resides in the middle of the input (which StreamLLM's attention-sink + local window design discards). On XSUM with LLaMA-7B, the gap between H2O and StreamLLM widens as the cache budget decreases, indicating that StreamLLM's fixed first-token + local policy is brittle compared to H2O's adaptive heavy-hitter selection.
Comparison with SpAtten (Table 11, Appendix C.9): H2O outperforms SpAtten by 1–2 points at matched 20% budget: COPA 84.00% vs. 82.00%, OpenBookQA 43.00% vs. 41.90%, PiQA 78.45% vs. 77.06%. The paper attributes this to H2O's per-head per-layer independence vs. SpAtten's head-aggregated score accumulation.
Alternative score aggregation (Appendix B.2): Using averaged attention scores (dividing accumulated score by the number of tokens that contributed) rather than summed scores "resulted in performance degradation." The paper also notes that "a significant proportion of H2 occurrences at the beginning of sentences," suggesting positional effects in heavy-hitter emergence.
Increased generation diversity (Figure 6, Figure 7, Appendix C.1): H2O with a 20% budget generates text with fewer repeated words and more varied content compared to the full-cache model. Quantitative measurement via Self-BELU on 100 XSUM prompts with LLaMA-7B: full model 0.0057, H2O 0.0051, Local 0.0436 (lower is more diverse). The full model in Figure 7 exhibits repetition ("the patrons were so moving that... the musician was so moved that he began to cry... the patrons were so moved that they began to cry"), while H2O produces more varied description.

Critical Assessment

Claim 1: H2O reduces KV cache memory by 5× without accuracy degradation on a majority of tasks. The evidence is strong but conditional. On the four multiple-choice tasks reported in Table 1 (COPA, OpenBookQA, PiQA, Winogrande), H2O at 20% budget achieves accuracy within 1–2 points of full-cache performance—this is a clear demonstration of a 5× memory reduction with negligible accuracy loss. However, "majority of tasks" should be interpreted carefully: the paper evaluates eight tasks total, and Figure 4 shows that on some model-task combinations, the gap is larger (e.g., LLaMA-7B on CNN/Daily Mail shows visible separation from the full-cache line even at 60% budget). The claim holds for the multiple-choice reasoning tasks more robustly than for the long-form generation tasks, where the paper acknowledges that some model-task pairs "require more information to generate the correct content, resulting in a higher KV cache budget (30-40%)" (Appendix C.3).

A genuine weakness: the paper evaluates on only 8 tasks drawn from two benchmarks. While the tasks span multiple reasoning types (commonsense, math, summarization), the sample is small relative to the diversity of LLM use cases. No evaluation is performed on code generation, translation, or dialogue tasks, all of which have different long-range dependency patterns and may exhibit different heavy-hitter distributions.

Claim 2: H2O improves throughput by up to 29× over DeepSpeed and Accelerate, and up to 3× over FlexGen. The 29× figure requires careful reading. It is achieved when the memory savings from H2O enable a much larger batch size that was previously impossible due to KV cache memory constraints. Specifically, on OPT-30B with 512+32 on a T4 GPU, H2O achieves 12.7 tok/s with batch size 728, while DeepSpeed achieves 0.6 tok/s with batch size 4. The ratio 12.7/0.6 ≈ 21×, and the abstract's "up to 29×" likely comes from a different configuration. This is a real gain—the system genuinely processes 21× more tokens per second on the same hardware—but it is not a direct "the same computation runs 29× faster" claim; it is a throughput improvement enabled by memory reduction allowing larger batches. The latency improvements (1.1–1.9× at the same batch size, Table 5) are the more direct measure of per-query speedup.

A missing comparison: the paper does not report throughput for H2O against a baseline that has the same KV cache size but uses a different eviction policy (e.g., random eviction, or the Top-K policy from Appendix C.5). This would isolate the contribution of the H2O eviction policy specifically from the generic effect of having a smaller cache. The Local baseline is the closest comparison (it uses the same cache size but a different policy), and it collapses in accuracy, so throughput comparisons are moot—but for a fixed cache size, H2O's throughput should be similar to Local's (both do O(k) work per step), so the throughput gains over full-cache systems are primarily from cache size reduction, not from faster eviction logic per se.

Claim 3: Heavy hitters are necessary for maintaining generation quality—removing them causes severe performance degradation. This claim is strongly supported by Figure 2(c), which shows models with heavy hitters removed performing drastically worse than the full-cache baseline across six tasks. The ablation in Table 9 further confirms that heavy hitters alone outperform local tokens alone. The evidence for this claim is the most robust in the paper, as it is replicated across model sizes (13B, 30B) and task types.

Claim 4: The H2O eviction policy formulated as dynamic submodular maximization has theoretical guarantees. This claim is aspirational. The theoretical analysis (Appendix D) proves that under submodularity assumptions, a greedy algorithm achieves near-optimality. However, the paper does not empirically verify that the attention score function in real LLMs satisfies submodularity, nor does it measure the empirical approximation ratio achieved by the greedy algorithm relative to the optimal cache (which would require solving the NP-hard optimal eviction problem, making this infeasible). The theory provides a conceptual framework and justification, not an empirically validated guarantee. The practical value of the theory is in motivating the algorithm design (concave score function, greedy selection), not in providing tight performance bounds for real deployments.

Missing experiments that would strengthen the paper:

Sensitivity to the 50/50 split: The paper allocates cache budget evenly between heavy hitters and local tokens without ablating this ratio. Table 9 shows both components are necessary, but a sweep over different split ratios (e.g., 70/30, 30/70) would reveal whether the even split is optimal or just convenient.
Sensitivity to the choice of concave function $h$ : The informal algorithm uses $h(z) = z$ (linear), while the theoretical framework assumes concave $h$ (e.g., $\sqrt{z+1}$ , $\log(z+1)$ ). The paper does not compare different $h$ functions empirically.
Comparison with a learnable/dynamic budget policy: H2O uses a fixed budget $k$ . A policy that adapts the budget based on sequence properties (e.g., increasing the budget for harder tasks, decreasing it for easier ones) could further improve the accuracy-memory tradeoff but is not explored.
Evaluation beyond autoregressive decoding: All experiments use standard autoregressive generation. Speculative decoding, beam search, and other generation strategies may have different KV cache access patterns and heavy-hitter distributions—these are unexamined.
Multi-GPU and distributed inference: The paper evaluates on single-GPU setups (T4 and A100). In multi-GPU tensor-parallel or pipeline-parallel deployments, the KV cache is sharded across devices, and the eviction policy would need to coordinate across devices—the current per-head per-layer independence would need to account for cross-device dependencies, which is not addressed.

Conditional nature of claims: The memory reduction claim (5× without accuracy loss) holds for the specific model-task combinations tested at the 20% budget level. The paper acknowledges that some tasks require 30–40% budgets (Appendix C.3), and this threshold likely varies with prompt length, model architecture, and task type. The throughput claims are hardware-dependent—the T4 GPU has limited memory (16GB), which makes KV cache reduction especially impactful because it enables fitting workloads that would otherwise require CPU offloading. On an A100 with 80GB, the relative gains are smaller (1.1–1.9× latency reduction) and primarily benefit long-sequence generation where the KV cache remains the bottleneck even with abundant memory.

6. Limitations and Trade-offs

The Difficulty Estimation Cost Is Unaccounted for in Headline Efficiency Claims

The assumption or constraint. The entire compute-optimal framework depends on estimating each prompt's difficulty before allocating the inference budget. The paper's method for doing so—generating 2,048 samples per question and scoring them with the PRM—is extraordinarily expensive. The authors acknowledge this explicitly in Section 3.2:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

The consequence. The reported 4× efficiency gains over best-of-N (e.g., Figure 4: 16 generations matching 64; Figure 8: 64 generations matching 256) are computed after difficulty is known, without amortizing the cost of learning it. In a realistic deployment, the total cost would be difficulty estimation (2,048 samples × PRM scoring per question) plus strategy execution. Since 2,048 samples exceeds the largest test-time budgets studied (256–512), the difficulty estimation step could dominate the total compute, making the net efficiency gains far lower than 4×—possibly even negative (i.e., the adaptive approach could cost more total compute than simply running best-of-N with the full budget). For batch processing where difficulty can be estimated once per question type and reused, the amortization is more favorable, but for one-off queries, the overhead is prohibitive.

What evidence exists in the paper. The paper's only evidence that difficulty estimation might be made practical is the comparison of oracle vs. predicted difficulty bins (Figures 4, 8), which shows that predicted bins (using PRM scores without ground-truth labels) track oracle bins closely. However, this comparison uses the same expensive sampling procedure—it only replaces the ground-truth correctness check with PRM scoring, not the 2,048 samples. There is no experiment measuring the accuracy of difficulty estimates with fewer samples (e.g., 8, 16, 64), no experiment training a lightweight difficulty predictor from question text alone, and no experiment that accounts for the difficulty estimation cost in the total budget.

Mitigation status. The paper flags this as a key direction for future work (Section 3.2 calls it "a key avenue for future work" and Section 8 suggests "pretraining or finetuning models to directly predict difficulty of a question"), but provides no solution. Until a low-cost difficulty estimator exists, the compute-optimal framework is an analytical contribution (showing what is possible with perfect difficulty knowledge) rather than a deployable system. The 4× figure should be understood as an upper bound on achievable efficiency under idealized conditions, not a realized deployment gain.

A Fundamentally Unresolved Tradeoff: Sequential Efficiency vs. Wall-Clock Latency

The assumption or constraint. The paper measures compute in "generations" (number of complete solutions sampled), which is a reasonable proxy for total FLOPs but ignores wall-clock latency. Sequential revisions are inherently serial—each revision depends on the previous one—while parallel best-of-N can be executed simultaneously given sufficient hardware. The paper's compute-optimal policy on easy problems favors sequential revisions (Figure 7, right: easy problems are insensitive to ratio but fully sequential is optimal for all ratios at lower budgets; Figure 7, left: fully sequential is optimal at budgets up to 32 generations).

The consequence. A strategy allocating 64 generations as 64 sequential revisions takes approximately 64× longer wall-clock time than one running 64 parallel samples simultaneously on sufficient hardware. For latency-sensitive applications (interactive assistants, real-time decision-making, user-facing chatbots), the sequential-heavy strategies favored by the compute-optimal policy on easy problems may be impractical regardless of their FLOPs-efficiency advantages. A user waiting for a response cares about seconds until completion, not total FLOPs consumed. The paper optimizes for throughput (answers per FLOP) but not for latency (time to answer), and the two objectives pull in opposite directions—sequential strategies maximize FLOP efficiency, parallel strategies minimize wall-clock time.

What evidence exists in the paper. The paper provides no latency measurements or wall-clock comparisons between sequential and parallel strategies. All experiments report generation-equivalent compute, not elapsed time. The only latency-related data are in the FLOPs-matched comparison (Section 7), which uses generation count as the unit of inference cost, implicitly assuming all generations within a strategy have equal wall-clock cost regardless of serial vs. parallel execution—an assumption that holds for total FLOPs but not for real-time performance.

Mitigation status. The paper does not discuss this tradeoff. It does not report latency numbers, does not propose hybrid strategies that balance latency and FLOP efficiency (e.g., capping sequential chain length to bound latency while still using some parallelism), and does not provide guidance for latency-constrained deployment scenarios. A practitioner choosing between a sequential-heavy strategy (lower FLOP cost, higher latency) and a parallel strategy (higher FLOP cost, lower latency) gets no guidance from the current analysis.

Hard Problems Remain Unsolved: Test-Time Compute Cannot Compensate for Capability Gaps

The constraint. Across all methods—search, revisions, and their compute-optimal combinations—the hardest questions (difficulty bin 5, where the base model's pass@1 is near zero) show near-zero improvement regardless of compute budget. In Figure 3 (right), bin 5 accuracy hovers at 1–3% for all methods and all budgets (4 to 256 generations). In Figure 7 (right), bin 5 shows roughly 2–3% accuracy irrespective of the sequential-to-parallel ratio. In the FLOPs-matched comparison (Figure 9), the bin 5 scaling line is essentially flat near 0–5%, well below the ~14× larger model's greedy performance.

The consequence. Test-time compute can amplify existing capability but cannot create it from nothing. If the base model's pass@1 is near zero on a problem class, no amount of search or revision will help—the proposal distribution contains effectively zero correct solutions to find or refine. The approach offers no path forward for genuinely novel or out-of-distribution reasoning that exceeds the base model's training distribution. For such problems, pretraining remains the only viable path, and the FLOPs-matched comparison (Figure 9) confirms this: on bin 5 at $R \gg 1$ , the ~14× larger model outperforms compute-optimal scaling by margins of 37–53% (relative). This is not a gradual degradation—it is a hard ceiling that cannot be pushed through with more inference compute.

What evidence exists in the paper. The evidence is clear and consistent across experiments. Figure 3 (right): bin 5 curves are flat and near-zero for all search methods. Figure 7 (right): bin 5 curves are flat across all sequential-to-parallel ratios. Figure 9: the bin 5 scaling line for compute-optimal revisions (blue, bottommost) is essentially horizontal and far below the ~14× larger model's performance (stars). Table 1: the full 5-shot model on the hardest subset of MATH likely performs near chance; compute-optimal scaling cannot improve this. The paper acknowledges this limitation explicitly in Section 7's takeaway: on the hardest problems, test-time compute is not a substitute for pretraining.

Mitigation status. The paper is transparent about this limitation and treats it as a finding rather than a failure (Section 7 takeaway box, Section 8 discussion). The compute-optimal framework naturally routes hard problems to the strategy that performs least badly (typically best-of-N with maximum budget), but this is damage minimization, not problem-solving. The limitation is fundamental: it arises from the base model's capabilities, not from the allocation strategy, so no amount of policy optimization can address it. The paper suggests that improving the base model (via pretraining or fine-tuning) is necessary for these problems.

Revisions and Search Are Studied Independently; the Combined System Remains Unexplored

The constraint. The paper studies two complementary mechanisms—PRM-guided tree search (Section 5) and iterative revision of the model's own outputs (Section 6)—but never combines them. Section 8 explicitly acknowledges:

"we did not experiment with PRM tree-search techniques in combination with revisions"

The two mechanisms have complementary strengths: revisions improve the proposal distribution (generating better candidates by learning from prior mistakes), while PRM search improves candidate selection (finding the best among generated candidates via step-level verification). Their difficulty-dependent performance profiles also differ—revisions excel on easy problems, search on medium-hard problems.

The consequence. The current results represent a lower bound on what a fully integrated system could achieve. A combined system could use the revision model as the proposal distribution within beam search (at each search step, the model conditions on previously rejected branches), or use the PRM to guide which revisions to pursue (deciding mid-chain whether to continue revising or restart). The difficulty-dependent complementary strengths (Figure 3 right vs. Figure 7 right) suggest that a combined system could outperform either mechanism alone across the full difficulty spectrum. The paper's conclusion that compute-optimal scaling yields 4× efficiency gains is therefore specific to independent application of search and revisions—a combined approach might yield larger gains, or might reveal new interaction effects (e.g., revision-augmented proposals making the PRM's over-optimization problem worse or better) that the current analysis cannot predict.

What evidence exists in the paper. There is no evidence—the combination is explicitly not tested. The closest the paper comes is the FLOPs-matched comparison (Figure 9), which compares compute-optimal revisions and compute-optimal search separately against the larger model, but never a hybrid strategy. The paper does not even provide a conceptual sketch of how to combine the two, beyond the acknowledgment in Section 8.

Mitigation status. The paper identifies this as a direction for future work (Section 8) but provides no analysis, no preliminary results, and no guidance on how to combine the methods. The gap is significant because it means the paper's central framework—unifying revisions and search as complementary axes—is proposed but not empirically validated at the system level. A negative result (e.g., the combination being no better than the maximum of the two individually) would be equally informative but is untested.

The Revision Model Has a Severe Correct-to-Incorrect Reversion Problem

The constraint. The revision model is fine-tuned exclusively on sequences where all in-context answers are incorrect followed by a correct target (Section 6.1). This means the model never sees examples where the current answer is already correct. At test time, when the model produces a correct answer early in the revision chain, it may encounter this answer in its context and "revise" it into an incorrect answer, because it has no training signal for what to do when the answer is already correct. The paper reports (Section 6.1):

"approximately 38% of correct answers get converted back to incorrect ones"

The consequence. This is not a minor edge case—it means that roughly 4 out of every 10 correct answers produced during a revision chain will be destroyed by subsequent revisions. The mitigation (majority voting or verifier-based selection across the entire chain, picking the best answer from any point rather than always taking the last revision) is an imperfect patch. It requires storing and scoring all intermediate answers, which increases overhead, and it relies on the verifier being able to correctly identify that an earlier answer was correct and a later revision was spurious—a non-trivial requirement given verifier over-optimization issues (Section 5.3). The 38% reversion rate also means that extending the revision chain beyond some optimal length becomes counterproductive: each additional revision step has a 38% chance of corrupting a correct answer in the chain (if one exists), creating a tension between the benefits of deeper revision (which improves accuracy when answers are initially incorrect) and the risks of reversion.

What evidence exists in the paper. The 38% figure is reported in Section 6.1 with a brief explanation of the cause (training data construction) and the mitigation (within-chain selection). Figure 6 (left) shows that pass@1 per step increases from ~18.2% at step 1 to ~24–25% by steps 15–20, suggesting the net effect of more revisions is positive despite reversions—but this is an aggregate measure and does not show how many correct answers were created and then destroyed within the chain. No ablation measures what fraction of the final accuracy gain from revisions is attributable to the within-chain selection mitigation vs. the raw revision capability.

Mitigation status. The paper acknowledges the problem and implements a mitigation (within-chain selection via verifier or majority voting), but does not solve the underlying issue. The mitigation itself has limitations: verifier-based selection can fail if the verifier scores a spurious revision higher than the correct original (verifier over-optimization), and majority-based selection requires multiple chains for meaningful signal. A more principled solution—such as training the revision model with mixed sequences that include "stop revising" tokens, or fine-tuning the verifier to detect reversions specifically—is not explored.

Single Benchmark Family (MATH) and Single Model Family (PaLM 2-S*) Constrain Generality

The constraint. All experiments use the MATH benchmark (Hendrycks et al., 2021), consisting of high-school competition-level math problems, with PaLM 2-S* (Codey) as the base model (Section 4). The paper states:

"believe this model is representative of the capabilities of many contemporary LLMs"

but provides no replication on other model families (GPT, LLaMA, Mistral) or other reasoning domains (code generation, logical reasoning, scientific QA, planning). The MATH benchmark is specifically designed for multi-step symbolic reasoning with verifiable ground-truth answers, which enables the paper's PRM training pipeline (Monte Carlo rollouts checked against ground-truth) and difficulty estimation (pass@1 based on exact string match via a grading function).

The consequence. Several aspects of the findings could be model-specific or benchmark-specific. The PRM's quality and over-optimization behavior depend on PaLM 2-S*'s output distribution—a model with different calibration properties or error patterns might exhibit different difficulty-dependent scaling curves. The revision model's ability to learn from incorrect in-context examples depends on the base model's in-context learning capabilities, which vary substantially across model families. Most critically, the entire framework depends on having clean correctness signals for PRM training and difficulty estimation. Many important real-world applications—open-ended generation, dialogue, creative writing, complex multi-step planning—lack such signals, and the Monte Carlo rollout-based PRM training (Section 5.1) requires checking whether sampled completions reach the correct final answer. For domains where correctness is ambiguous, multi-dimensional, or subjective, fundamentally different verifier training approaches would be needed, and it is unclear whether the difficulty-dependent patterns observed on MATH would transfer.

What evidence exists in the paper. The paper provides no cross-model or cross-domain replication. All experiments use PaLM 2-S* and MATH. The test set of 500 questions, split into five difficulty quintiles of ~100 each, then further split by two-fold cross-validation, means the compute-optimal policy is selected based on ~50 questions per fold per bin. The paper does not report confidence intervals on the compute-optimal scaling curves, making it difficult to assess whether the observed gains are statistically reliable at this sample size.

Mitigation status. The paper acknowledges this limitation indirectly by describing PaLM 2-S* as "representative" (Section 4), but this claim is unverified. Section 8 does not explicitly call for multi-model or multi-domain replication, though it does suggest extending to other domains. The practical implication is that a practitioner using a different model (e.g., GPT-4, LLaMA-3, Claude) or a different task domain cannot assume the 4× efficiency gain will transfer without empirical validation—the optimal policy, difficulty thresholds, and gain magnitudes may all shift.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper changes the conversation around LLM inference efficiency by reframing the KV cache from a passive byproduct of autoregressive generation into an active resource that can be managed with principled eviction policies. Before H2O, the dominant approaches to the KV cache bottleneck were either architectural (multi-query attention, which requires retraining) or computational (FlashAttention, which reduces memory-access cost but not cache size). The KV cache itself was treated as a fixed cost—something you either tolerated, offloaded to CPU with massive latency penalties, or compressed post-hoc with structural sparsity patterns that caused severe accuracy degradation (as the paper shows in Table 2: Sparse Transformer variants drop by 25–35 points at 20% budget).

H2O establishes that the KV cache is not just reducible but massively overprovisioned: 95%+ of stored embeddings are irrelevant at any given decoding step (Figure 2a), and a small, identifiable set of tokens—the heavy hitters—carries the critical long-range information. The conceptual shift is from "how do we make attention faster?" to "which keys and values do we actually need to keep?" This is a reframing of the problem from a compute bottleneck to an information retention problem, and it opens a design space that was not previously visible: the KV cache can be treated as a cache in the classical computer systems sense, with eviction policies optimized for the specific access patterns of autoregressive attention.

The paper resolves an apparent contradiction in prior work that the authors do not explicitly call out as a contradiction but that their results make clear: structural sparsity patterns designed for training fail catastrophically at inference (Table 2, Figure 1, lower right plot), while simple recency-based policies (Local) work for some decoding steps but collapse entirely on tasks requiring long-range dependencies (Figure 4: Local collapses at 60% budget on XSUM with LLaMA-13B, performing near zero while H2O at 20% matches full cache). The resolution is that neither fixed sparsity nor pure recency captures the dynamic, content-dependent importance structure of tokens during autoregressive generation—an importance structure that H2O identifies through accumulated attention scores. This explains why prior sparse attention methods saw limited adoption for inference: they imposed a structural prior (strided, local, or hashed attention) that was mismatched to the actual information needs of the model during generation. H2O's heavy-hitter criterion is an empirically derived importance measure, not an architectural assumption, which is why it generalizes across model families (OPT, LLaMA, GPT-NeoX), model sizes (6.7B to 175B), and task types (multiple-choice reasoning, summarization, streaming) without retraining.

The paper also makes a methodological contribution by connecting KV cache management to submodular optimization (Section 4.2, Appendix D). While the theoretical guarantees are proven under assumptions whose empirical validity is not verified, the framing itself is valuable: it provides a vocabulary and a set of analytical tools from combinatorial optimization that future work can use to design and analyze eviction policies. The connection to heavy-hitter algorithms in streaming and compressive sensing (Appendix D) further suggests that KV cache eviction is not a one-off engineering problem but an instance of a broader class of dynamic subset selection problems that appear in other streaming ML contexts.

Several research directions become more attractive as a result of this work:

Information-theoretic cache sizing: H2O uses a fixed budget $k$ chosen before generation. The observation that heavy-hitter distributions follow power laws (Figure 2b) and are temporally stable (local statistics match global, Figure 2d) suggests that the minimum required cache size could be predicted from the attention score distribution itself—potentially enabling adaptive budgets that grow or shrink based on the information density of the sequence.
Eviction-aware training: H2O is applied to pretrained models without any modification. If models were trained with the knowledge that their KV cache might be evicted, they might learn to concentrate important information into a smaller set of tokens (making the heavy-hitter distribution even more concentrated) or learn to be robust to the absence of non-heavy-hitter tokens. This is analogous to dropout—training with random KV eviction could act as a regularizer that produces more cache-efficient models.
Verifier and quality-assessment mechanisms for generation with reduced cache: The paper shows that Local can collapse entirely (producing repetitive garbage, as in Figures 6–7) while H2O maintains coherence at the same cache budget. This suggests that a learned or heuristic "cache quality" metric could monitor attention patterns during generation and detect when the cache budget is insufficient for the current context, triggering either expansion, fallback to full-cache recomputation for critical tokens, or early termination.
Hardware-aware cache design: The paper's implementation uses a simple dual-buffer architecture (heavy hitter region + circular queue for local tokens) on top of FlexGen. The observation that heavy hitters persist across many decoding steps (the temporal stability in Figure 2d) suggests that the heavy-hitter region could be stored in a different memory tier (e.g., fast on-chip SRAM) than transient tokens, exploiting the bimodal access pattern for further latency reduction—this is not explored in the current work.

Conversely, some research directions become less attractive:

Purely structural sparsity patterns for post-hoc KV cache compression: Table 2 demonstrates that fixed sparsity (strided, local) applied to pretrained models causes massive accuracy degradation (25–35 points) at aggressive cache budgets, and that this degradation cannot be resolved by simply increasing the pattern density—the missing tokens are genuinely needed. This suggests that the research program of applying fixed sparsity patterns to the KV cache of pretrained LLMs is fundamentally limited, and future work should focus on content-dependent eviction policies.
Head-level or layer-level aggregation of importance scores: The paper's comparison with SpAtten (Table 11, Appendix C.9) shows that aggregating attention scores across heads and layers (as SpAtten does) underperforms per-head independent eviction (H2O: 84.00% vs. SpAtten: 82.00% on COPA at 20% budget). This is consistent with Figure 10 (Appendix C.8), which shows that heavy-hitter distributions differ substantially across layers. The implication is that importance is inherently head-specific and layer-specific, and aggregation loses critical information. Future work on attention pruning or KV cache sparsification should operate at the finest granularity practical.

Follow-Up Research This Work Enables

Characterizing heavy-hitter dynamics across model families, scales, and training stages. The paper observes heavy hitters in OPT, LLaMA, and GPT-NeoX at inference time, but provides only limited analysis of when these heavy hitters emerge during training. Appendix C.10 briefly examines MLP heavy hitters and notes an "early-bird" property where the power-law distribution emerges at 4% of training budget and stabilizes. A natural follow-up would track heavy-hitter emergence in attention blocks across training checkpoints for models of varying sizes (e.g., Pythia checkpoints from 14M to 12B parameters), measuring: (1) at what training step heavy-hitter distributions stabilize, (2) whether larger models concentrate attention more or less aggressively, (3) whether heavy-hitter positions correlate with linguistically meaningful token categories (function words, punctuation, topic words), and (4) whether heavy hitters are the same tokens across different inputs or are input-dependent. The paper shows correlation between accumulated attention and word co-occurrence frequency (Figure 2b), but a token-level analysis linking specific heavy hitters to linguistic roles would provide mechanistic insight. If heavy hitters are largely input-independent (e.g., sentence-initial tokens, punctuation, frequent function words), then the eviction policy could potentially be simplified to a static mask plus a small dynamic component, further reducing overhead.

Measuring the empirical submodularity gap in real LLM attention distributions. The paper's theoretical framework assumes the attention score function is submodular (Appendix D.7) and uses a concave $h$ in the score function to encode diminishing returns. However, the paper never empirically verifies submodularity on real attention data. A strong follow-up would construct the following experiment: take a fixed decoding context (e.g., 100 tokens), compute the true accumulated attention scores, and then measure the marginal gain $\Delta(i \mid S) = F(S \cup \{i\}) - F(S)$ for various subsets $S$ and tokens $i$ . Compare the greedy selection against the true optimal size- $k$ subset (found by brute force for small $k$ , e.g., $k \leq 10$ ) to measure the empirical approximation ratio. Does greedy achieve $(1-1/e)$ ? If not, how far is the gap, and does it correlate with observable properties of the attention distribution (e.g., entropy, sparsity)? A negative result—that greedy is substantially suboptimal for certain attention heads or layers—would motivate more sophisticated eviction algorithms; a positive result would strengthen the theoretical motivation for greedy H2.

Training lightweight difficulty predictors for per-sequence cache budget allocation. The paper observes that some tasks require higher cache budgets (30–40% for zero/one-shot inference, Appendix C.3) while others work at 20%, but H2O uses a fixed global budget. A follow-up could train a small predictor (e.g., a linear probe on top of the LLM's embedding layer, or a lightweight LSTM) that takes the first $m$ tokens of a sequence (or the prompt) and predicts the minimum cache budget needed to maintain accuracy within $\epsilon$ of the full-cache baseline. The training signal would be generated by running H2O at multiple budgets on diverse text and measuring the budget at which accuracy drops below threshold. End-to-end, the system would: (1) process the prompt through the budget predictor, (2) set $k$ accordingly, (3) run H2O with budget $k$ . This addresses the paper's missing budget-adaptivity while adding minimal overhead (one forward pass of a small model). The key measurement is whether adaptive budgets save more total memory across a workload than a single conservatively-chosen fixed budget.

Combining H2O with speculative decoding and multi-query attention. The paper evaluates H2O in standard autoregressive generation, but two orthogonal efficiency techniques are increasingly common: speculative decoding (draft model generates candidate tokens, large model verifies) and multi-query or grouped-query attention (fewer KV heads). H2O's heavy-hitter identification is per-head—how does it interact with architectures that share KV heads across queries? For multi-query attention, the KV cache is already smaller (one set of keys/values shared across all query heads), so the relative benefit of H2O might decrease. Conversely, for speculative decoding, the draft model's KV cache and the large model's KV cache must both be maintained—does H2O applied to both caches yield compounding savings? A concrete experiment: benchmark OPT-30B with and without H2O in a speculative decoding setup with a small draft model (e.g., OPT-125M), measuring total memory footprint and throughput at matched generation quality. The hypothesis is that H2O reduces the large model's KV cache (which dominates memory in speculative decoding because the large model verifies all draft tokens) without affecting verification accuracy, enabling larger draft batch sizes.

Verifier-free detection of cache-induced degradation. A notable finding in the paper is that the Local strategy can silently collapse into producing repetitive or nonsensical text (Figures 6–7, Appendix C.1) without any obvious warning—the model keeps generating tokens, but they are garbage. This is dangerous for deployed systems. A follow-up could develop a "cache-health monitor": a lightweight detector that runs in parallel with generation and flags when the attention pattern suggests the cache is insufficient. Candidates: (1) monitor the entropy of the attention distribution over cached tokens—if entropy spikes (indicating the model can't find relevant tokens in the cache), the cache may be too small; (2) monitor the fraction of attention mass concentrated on the very first or very last cached tokens—if it collapses to these extremes, the cache is failing; (3) compare the current-step attention distribution to a running average—large deviations signal cache stress. The evaluation would measure false-positive rate (flagging healthy generations) and false-negative rate (missing cache-induced garbage) across tasks and budgets from the paper's evaluation suite. A successful monitor would enable dynamic budget expansion: when the monitor fires, temporarily increase $k$ and recompute attention for the flagged step to recover coherence.

Stress-testing H2O on retrieval-augmented generation and tool-use trajectories. All of the paper's evaluations involve single-document or single-context generation (multiple-choice QA, summarization). In retrieval-augmented generation (RAG) or tool-use scenarios, the prompt contains retrieved passages or API call results that are semantically dense but syntactically heterogeneous. The heavy-hitter distribution in these settings might be qualitatively different: retrieved passages might all be "relevant" but in different ways, potentially flattening the power-law distribution and making greedy H2 selection less effective (more tokens are "important"). A concrete stress test: evaluate H2O on a RAG benchmark (e.g., Natural Questions with retrieved passages appended to the prompt) at varying cache budgets, measuring both answer accuracy and the attention concentration (Gini coefficient of the accumulated attention scores) compared to the single-document tasks in the paper. If attention is less concentrated in RAG, the greedy H2 policy might need to retain a larger fraction of the cache, reducing the memory savings. This would establish a boundary condition on H2O's applicability.

Practical Applications and Downstream Use Cases

Cost-efficient batch inference for summarization and content generation pipelines. Organizations running large-scale batch inference—evaluating news articles for summarization, generating product descriptions, scoring candidate responses—face a direct tradeoff between throughput and hardware cost. The paper's T4 GPU results (Table 3) show that H2O at 20% budget increases generation throughput by 2.5–3× on real-world summarization data (XSUM, Table 4) compared to FlexGen, and by up to 29× compared to DeepSpeed and Accelerate when the reduced memory enables larger batch sizes. For a deployment processing 100,000 summarization requests daily on OPT-30B with sequence lengths of 512+32, switching from DeepSpeed to H2O at 20% budget would reduce GPU-hours by roughly 29× (from ~139 GPU-hours to ~4.8 GPU-hours on T4-equivalent hardware, assuming linear scaling with the throughput ratios in Table 3). Even conservatively assuming a 10× improvement after accounting for real-world overhead (variable sequence lengths, load imbalance), the cost reduction is substantial—this is the kind of gain that can make on-premise deployment viable for organizations currently priced out of LLM inference.

On-device or edge deployment of moderate-size LLMs for interactive applications. The paper's experiments on NVIDIA T4 GPUs (16GB memory, representative of edge inference hardware) demonstrate that H2O enables running OPT-6.7B with batch sizes and sequence lengths that would otherwise require CPU offloading or would fail entirely. Table 3 shows that H2O at 20% budget achieves 35.1 tok/s on OPT-6.7B with 512+32 on a T4 with batch 4 in pure GPU mode, while FlexGen achieves 20.2 tok/s with batch 2 and Accelerate achieves 20.4 tok/s with batch 2—both at the same or lower batch size on the same hardware. The practical implication: a customer-service chatbot running LLaMA-7B on edge hardware (e.g., a local server in a retail store, or an on-premise deployment for data privacy) can serve twice the concurrent users at the same latency, or serve the same number of users at 1.7× lower latency, by enabling H2O with a 20% budget. The memory savings also reduce the probability of out-of-memory errors under load spikes, improving reliability. The key deployment requirement is that the application's typical sequence lengths fit within the chosen cache budget—for conversational applications with short turns (100–500 tokens), a 20% budget of 20–100 tokens retains ample context.

Streaming processing of long documents for analysis and information extraction. The infinite-length streaming results (Section 5.3, Q1, Figure 5) show that H2O combined with StreamLLM can process sequences of up to four million tokens while achieving lower perplexity than StreamLLM alone across cache sizes. This has direct application to long-document analysis: processing entire books, legal contracts, or genomic sequences through an LLM for summarization, entity extraction, or question answering. Current approaches to long-document processing typically chunk the document into overlapping windows, process each independently, and merge results—a pipeline that can miss cross-chunk dependencies and requires careful engineering of chunk boundaries. H2O with streaming enables a conceptually simpler pipeline: stream the entire document through the model in a single pass, with the KV cache adaptively retaining the most important tokens from earlier sections. A concrete deployment scenario: processing a 500-page legal contract (approximately 200,000 tokens) for clause extraction. With H2O at 20% budget and a 40,960-token cache, the model can attend to important clauses from anywhere in the document while processing it in a single streaming pass, avoiding the chunk-boundary artifacts that would occur with a 4,096-token sliding window. The throughput and latency numbers from Table 5 (e.g., 155.4s for 5000+5000 on LLaMA-13B with batch 4 on A100) establish that this is practical at interactive speeds for documents of tens of thousands of tokens.

(Conditional section omitted: while H2O does position itself against alternatives like DeepSpeed, Accelerate, and FlexGen, the positioning is empirical ("up to 29× better throughput") rather than prescriptive—the paper does not articulate a decision rule for when to prefer H2O over other KV cache reduction strategies based on problem characteristics, beyond the general observation that structural sparsity fails and heavy hitters are necessary. A forced "prefer H2O when..." matrix would invent tradeoffs the paper does not analyze, such as latency vs. throughput tradeoffs across different eviction policies, or task-dependent policy selection.)