KV Cache Compression: Eviction, Quantization & H2O Algorithm

As we explored in the previous chapters on KV cache fundamentals and memory analysis, the cache grows linearly with sequence length and can consume tens of gigabytes for long contexts. A model generating a 32,768-token response might accumulate several gigabytes of cached key and value tensors across all layers and attention heads. Paged attention addresses memory fragmentation and allocation overhead, but the total memory footprint of the cache itself remains substantial. KV cache compression tackles this problem directly by reducing the amount of data stored, either through selective eviction of less important cache entries or by quantizing the cached values to lower numerical precision.

The key insight driving compression research is that not all cached tokens contribute equally to generation quality. Attention patterns in transformers are highly non-uniform: certain tokens receive concentrated attention while others are nearly ignored across hundreds of generation steps. This sparsity creates an opportunity. If we can identify and preserve the high-value cache entries while discarding the rest, we can dramatically reduce memory usage with minimal impact on output quality. The central challenge is doing this identification accurately and efficiently, without expensive per-step computation that would offset the memory savings.

Think of the KV cache as a research library. When a scholar writes a paper, they do not continuously consult every book they have ever read. Instead, they repeatedly return to a small set of highly relevant sources, occasionally glance at recent acquisitions, and largely ignore the large middle ground of books that happened to be present on the shelves. A librarian who understood the scholar's research patterns could remove most of those rarely-consulted books without affecting the quality of the scholar's work. KV cache compression is the process of being that librarian: identifying which cached tokens are the books our model keeps returning to and discarding the rest.

This chapter covers the three main approaches to KV cache compression: eviction-based strategies that remove entire token representations from the cache, attention sink preservation that protects necessary initial tokens from eviction, and cache quantization that reduces the numerical precision of stored values. We examine the H2O (Heavy-Hitter Oracle) algorithm in detail as a representative eviction method, then explore how these techniques combine for maximum compression. We also analyze the quality implications of each approach and discuss the practical trade-offs involved in deploying compressed caches in production.

Understanding these techniques requires familiarity with attention mechanics from Part XIII and the KV cache fundamentals covered earlier in this inference optimization section. We will also build on the attention sink discussion from Part XVIII to explain why naive eviction strategies fail and how the research community solved this problem. By the end of this chapter, you will have a thorough understanding of how to reduce KV cache memory by more than 30x while preserving generation quality for the large majority of practical use cases.

Before diving into specific techniques, we need to understand why compression is feasible in the first place. The basic question is this: can we discard information from the KV cache without significantly harming generation quality? To answer this, consider the attention patterns in a typical language model generating the 500th token. The query for this new token computes attention scores against all 499 previous key vectors. In a perfectly uniform distribution, each previous token would receive $1/499 \approx 0.2\%$ of the attention. In practice, attention is far from uniform, and this non-uniformity is precisely what makes compression possible.

The magnitude of this non-uniformity is striking. Empirical studies of transformer attention patterns consistently find that a small fraction of tokens, often 10-20%, account for 80-90% of the total attention weight. The remaining 80-90% of tokens share only 10-20% of the attention budget. This is reminiscent of the Pareto principle in economics: a small minority of inputs drives the majority of the output. For KV caches, this means that a compressed cache containing only the high-attention minority of tokens can approximate the full attention computation remarkably well, as long as we correctly identify which tokens belong to that necessary minority.

Studies of transformer attention patterns reveal several consistent phenomena that explain why some tokens matter far more than others:

• Local focus: Recent tokens often receive disproportionate attention, especially in lower layers. This makes intuitive sense because language exhibits strong local coherence, with adjacent words being grammatically and semantically related.
• Anchor tokens: Semantically important tokens such as subjects and verbs, along with tokens naming key entities, attract attention regardless of distance. These tokens carry the core meaning of a passage and remain relevant throughout generation.
• Attention sinks: As we covered in Part XVIII, initial tokens accumulate attention even when semantically irrelevant. This curious phenomenon appears to serve a computational purpose rather than a semantic one.
• Sparse activation: Many tokens receive near-zero attention and contribute minimally to the output. These tokens are prime candidates for removal without significant quality degradation.

This non-uniformity means that a cache storing only the high-attention tokens might preserve most of the information needed for accurate generation. The attention distribution is not merely slightly skewed; it is often dramatically concentrated on a small subset of tokens. The challenge lies in identifying these important tokens efficiently, without requiring expensive computation at each generation step. We need methods that can predict which tokens will be important for future generation steps, not just which tokens have been important in the past. As we will see, historical attention patterns turn out to be a surprisingly reliable predictor of future importance, at least for the tokens that truly matter.

The simplest eviction strategy maintains a fixed-size sliding window, keeping only the most recent $k$ tokens in the cache. This approach has clear appeal for several reasons. It is trivial to implement, requires no analysis of attention patterns, and guarantees constant memory usage regardless of sequence length. The underlying assumption is that recent context is the most relevant context, which holds true for many language modeling scenarios. The local attention patterns we observed earlier provide empirical support for this assumption: recent tokens reliably attract a significant portion of the attention budget.

Window-based eviction is analogous to a student who only reads the last paragraph they wrote before continuing. For tasks with strong local dependencies, this works well. For tasks requiring integration of information from across the entire document, it fails catastrophically. Understanding exactly where this boundary lies is important for knowing when to use window-based approaches and when to adopt more sophisticated strategies.

The implementation is straightforward: we simply maintain a buffer of the last $k$ key-value pairs and discard older entries as new tokens are generated. No attention tracking, no score computation, and no complex data structures are required. This simplicity makes it attractive for latency-sensitive deployment scenarios where the overhead of more sophisticated methods would be unacceptable.

Truncating to 32 tokens reduces cache memory by 68% in this example. The implementation is straightforward: we simply slice the tensor to keep only the final positions. However, this simplicity comes with a basic limitation: the approach discards all context beyond the window, including potentially important information from the beginning of the sequence.

Consider the practical implications through a concrete example. Imagine generating a response to a question. The question might appear at token positions 0-50, followed by supporting context at positions 51-400, with generation starting at position 401. A sliding window of 100 tokens would retain only tokens 301-400, losing the original question entirely. The model would have no memory of what it was asked, potentially creating irrelevant or incoherent responses. This illustrates why pure window-based approaches often fail for tasks requiring long-range dependencies. The approach works well for streaming applications or local language modeling, but breaks down when the task requires referencing distant context.

A more sophisticated approach selects tokens based on their historical attention scores rather than their recency. The intuition behind this method is straightforward: tokens that have received high attention in the past are likely to be important for future generation. These tokens have already proven their value, so preserving them makes sense. By tracking cumulative attention and evicting low-attention tokens, we can maintain a compact cache of the most relevant context while adapting to the specific content being processed.

Think of attention-based eviction as a hotel concierge who tracks which guests request the most services. Guests who never ring the service bell can safely be checked out early to free up rooms. Guests who constantly request assistance clearly need to stay. The analogy breaks down slightly because we cannot know in advance which guests will become high-demand, but historical patterns give us a reliable signal.

The key insight here is that attention scores provide a signal of token importance. When the model attends heavily to a particular token, it extracts information from that token to inform its output. Tokens that consistently receive high attention across multiple generation steps are carrying information that the model repeatedly needs. These "frequently consulted" tokens are prime candidates for preservation, while tokens that receive negligible attention can likely be removed without consequence. The cumulative nature of this tracking is important: a token that receives a small amount of attention at each of 100 steps has accumulated substantial importance, even if no single step stands out as particularly high.

This approach adapts dynamically to the content being processed. Important tokens accumulate high attention scores over time and remain in the cache, while less relevant tokens get evicted as their scores remain low. The method naturally identifies semantically meaningful tokens like subjects, key entities, and important verbs that the model needs to reference repeatedly. Unlike the sliding window approach, attention-based eviction can retain a token from position 5 while evicting tokens from positions 50 through 200 if those middle tokens have not been useful.

However, the approach introduces computational overhead for tracking scores and, more critically, has a basic flaw that we must address. The flaw relates to a peculiar attention pattern we covered earlier: attention sinks. We will explore this issue and its solution in the next section.

As we discussed in Part XVIII, Chapter 5 on attention sinks, transformers exhibit a curious behavior that complicates attention-based eviction: initial tokens in a sequence accumulate disproportionate attention even when they carry no semantic importance. These "attention sinks" appear to act as computational anchors. This provides a stable target for attention heads to discharge probability mass when no relevant context exists. The phenomenon emerges from training dynamics: the model learns to use early tokens as a default attention target. This creates a dependency that persists even when those tokens are semantically meaningless.

To understand why this creates a problem for eviction, consider what happens during long generation. Attention-based eviction is supposed to preserve high-attention tokens because they carry important information. But initial tokens receive high attention for a completely different reason: they serve as a computational escape valve. If we sort all tokens by cumulative attention and discard the lowest-scoring ones, we will correctly identify many low-importance middle tokens for eviction. But we might also accidentally evict tokens that had middling cumulative attention scores while the true attention sinks at positions 0-3 consume a large fraction of the attention budget and dominate the preservation list.

When we evict tokens based purely on historical attention scores, we risk removing tokens that should stay while incorrectly preserving tokens that are sinks rather than semantically important. Without attention sinks available, models may produce incoherent outputs, fall into repetition loops, or exhibit generally degraded quality. The attention mechanism loses its computational anchor, disrupting the learned patterns that depend on its presence. This is not a minor quality degradation; for some models and tasks, removing attention sinks completely breaks generation.

This creates a paradox for attention-based eviction strategies. The tokens receiving highest attention (the sinks) may not be semantically important, while truly important content tokens may receive only moderate attention because they share the attention budget with the sinks. Pure attention-score-based eviction conflates two distinct sources of high attention: semantic importance and computational anchoring. These require different treatment in a principled eviction policy.

The solution is to protect initial tokens from eviction regardless of their attention scores. By unconditionally preserving the first few tokens, we ensure the attention sinks remain available while still allowing the eviction policy to remove low-importance tokens from the rest of the sequence. This separation lets the score-based eviction logic focus on semantic importance without interference from the sink phenomenon.

Research has shown that just 4 sink tokens are typically sufficient to maintain generation quality, making this a highly efficient solution. The small sink budget adds minimal memory overhead while giving the computational anchoring the model requires. Combined with a modest window size, the approach achieves substantial compression while maintaining coherent generation for streaming applications. The trade-off is that middle context (between the sinks and the recent window) is entirely lost, which can degrade quality on tasks requiring long-range reasoning.

Heavy-Hitter Oracle (H2O) represents a more sophisticated eviction policy that extends beyond simple recency or sink preservation. The algorithm combines attention-based selection with sink preservation, addressing the limitations of both pure window-based and pure attention-based approaches. The key insight motivating H2O is that tokens exhibit different temporal importance patterns. Some tokens are "heavy hitters," consistently receiving high attention across many generation steps because they carry information the model repeatedly needs. Other tokens are transient, relevant only briefly before becoming obsolete as generation proceeds.

The name "oracle" is somewhat aspirational: a true oracle would know with certainty which future tokens would be needed and preserve exactly those. H2O approximates this oracle by using historical attention patterns as a proxy for future importance. This approximation works well in practice because semantic importance tends to be persistent. A sentence's subject noun remains important throughout the sentences that follow. A key fact mentioned in the introduction remains relevant when the conclusion references it. The oracle approximation is not perfect, but it is far better than ignoring historical patterns entirely.

Consider how these patterns manifest in practice. A subject noun at the beginning of a paragraph might be a heavy hitter, receiving attention throughout the paragraph as the model maintains coherence. A transition word, by contrast, might receive attention only from the immediately following tokens before becoming irrelevant. H2O captures this distinction by tracking cumulative attention over time and using it to identify tokens worthy of long-term preservation. The algorithm maintains two complementary categories of preserved tokens:

1. Recent tokens: A sliding window of the most recent $k_{\text{recent}}$ tokens. These provide immediate local context and ensure the model can maintain coherent generation based on what was just produced.
2. Heavy hitters: Tokens with the highest cumulative attention scores, capped at $k_{\text{heavy}}$ tokens. These represent semantically important content that the model has repeatedly consulted, suggesting continued relevance.

The algorithm dynamically balances these sets throughout generation. This keeps both recency and historical importance are considered when making eviction decisions. Tokens can transition between categories: a recent token that accumulates high attention becomes a heavy hitter candidate, while a former heavy hitter that stops receiving attention may eventually be evicted as new heavy hitters emerge. This fluidity is a key advantage over static approaches that fix which tokens to preserve at the start of generation.

The cumulative attention scores reveal the distinction between heavy hitters and ordinary tokens. Positions 5 and 10 have accumulated substantially higher scores than other retained positions because the simulated attention pattern consistently attended to them. In a real model, these high-attention tokens would typically correspond to semantically important content: the subject of a sentence, a key entity being discussed, or a necessary fact that informs subsequent generation. The visualization makes it clear why H2O outperforms pure sliding windows: important early context is retained automatically, without any manual specification of what to keep.

Let's trace through a concrete numerical example to see exactly how H2O makes eviction decisions. Suppose our cache has recent_size = 2 and heavy_hitter_size = 2, giving a maximum cache size of 4. We have just generated 5 tokens (positions 0-4), so the cache has grown to 5 entries and must evict one.

After 5 generation steps, the cumulative attention scores for the 5 cached tokens are:

• Position 0: cumulative attention = 3.8 (this is an anchor token, repeatedly consulted)
• Position 1: cumulative attention = 0.4 (barely consulted)
• Position 2: cumulative attention = 2.1 (moderately important)
• Position 3: cumulative attention = 0.3 (barely consulted, just added to window)
• Position 4: cumulative attention = 0.0 (brand new, no history yet)

The algorithm proceeds as follows. First, identify the recent_size = 2 most recent tokens by position. Positions 3 and 4 are the two most recent, so they enter the recent set unconditionally. Second, among the remaining tokens (positions 0, 1, 2), identify the heavy_hitter_size = 2 tokens with highest cumulative attention. Position 0 has score 3.8 and position 2 has score 2.1, making them the heavy hitters. Position 1 with score 0.4 is the eviction candidate. Third, the final cache contains positions {0, 2, 3, 4}, preserving the anchor token and the recent window while discarding the low-importance middle token at position 1.

This example illustrates the core logic: recency and importance are evaluated independently, and both contribute tokens to the final cache. A token can survive eviction for either reason: being recent or being an established heavy hitter. Only tokens that are neither recent nor historically important get evicted.

Orthogonal to eviction strategies, cache quantization reduces memory by storing key and value vectors at lower numerical precision. While model weights typically use FP16 or BF16 during inference, the cached activations can often tolerate even lower precision without significant quality loss. This approach complements eviction: rather than removing tokens entirely, we keep all tokens but represent each one using fewer bits.

Think of quantization as converting high-resolution photographs to compressed JPEGs. The compressed versions are smaller and may have barely perceptible artifacts, but they preserve the needed content. For our purposes, the "needed content" of a cached key vector is its direction in high-dimensional space, not its precise magnitude. Attention computation depends on dot products, which are dominated by directional alignment. Modest rounding errors in the vector components rarely change which tokens receive the highest attention.

The mathematical foundation of quantization is straightforward. We need to map continuous floating-point values to a discrete set of integers that can be stored compactly. The simplest form is uniform quantization, which divides the value range into equally-spaced bins and maps each floating-point value to the nearest bin.

To derive the quantization formula, suppose we have a floating-point value $x$ drawn from the range $[x_{\min}, x_{\max}]$. We want to represent it as an integer $q$ in the range $[0, 2^b - 1]$, where $b$ is the bit width. The linear mapping that achieves this is:

where:

• $q$: the resulting quantized integer index, which will be stored in place of the original floating-point value
• $x$: the original floating-point value that we wish to compress
• $x_{\min}$: the minimum value in the group being quantized, establishing the lower bound of the value range
• $x_{\max}$: the maximum value in the group being quantized, establishing the upper bound of the value range
• $b$: the target bit width (e.g., 8 for INT8 or 4 for INT4), determining how many discrete levels are available
• $2^b - 1$: the total number of discrete quantization levels, which equals the maximum integer value representable with $b$ bits

This transformation accomplishes its goal through a sequence of intuitive steps. First, it normalizes the original value $x$ to the range $[0, 1]$ by computing the fraction $\frac{x - x_{\min}}{x_{\max} - x_{\min}}$. This fraction represents where $x$ falls within the overall range of values. Second, it scales this normalized value to the full integer range $[0, 2^b - 1]$ by multiplication. Finally, it rounds to the nearest integer to obtain a discrete representation that can be stored efficiently. This approach preserves the relative ordering and approximate magnitudes of values while dramatically reducing storage requirements.

When we need to use the cached values for computation, we must reverse this process. Dequantization recovers an approximation of the original value:

where:

• $\hat{x}$: the reconstructed floating-point value, which approximates the original $x$
• $q$: the stored quantized integer retrieved from memory
• $b$: the target bit width used during quantization
• $x_{\min}$: the minimum value from the original group, serving as the offset that restores the correct baseline
• $x_{\max} - x_{\min}$: the dynamic range of the original values, used to restore the correct magnitude

The reconstruction process precisely reverses the quantization steps. It first converts the integer $q$ back to a proportion in $[0, 1]$ by dividing by the maximum integer value. It then maps that proportion onto the original dynamic range by multiplying by $(x_{\max} - x_{\min})$. Finally, it adds the offset $x_{\min}$ to restore the correct baseline. The reconstructed value $\hat{x}$ will differ from the original $x$ by at most half a quantization step, introducing a small but bounded error. With 8 bits, this maximum error is approximately $\frac{x_{\max} - x_{\min}}{510}$, which for a typical value range of $[-3, 3]$ is about 0.012, far smaller than the typical variation in key vectors.

Even INT4 quantization, which provides 4x compression, often preserves sufficient similarity for acceptable generation quality. However, quality degradation becomes noticeable for precision-sensitive tasks at this level. The trade-off between compression and accuracy depends heavily on the specific application: chat applications may tolerate INT4 well, while code generation or mathematical reasoning may require the precision of INT8 or higher.

The per-tensor quantization approach we examined computes global statistics across the entire tensor, using a single minimum and scale value for all elements. This approach is simple but can be suboptimal when different attention heads or dimensions have varying value ranges. If one head has values concentrated in a narrow range while another has a wide range, using global statistics forces the narrow-range head to use only a fraction of the available quantization levels, wasting precision.

Think of it this way: if you use a ruler calibrated in meters to measure both the height of a building and the width of a fingernail, you will get very imprecise measurements for the fingernail. Per-channel quantization is like giving each head its own appropriately-scaled ruler.

Per-channel quantization improves accuracy by computing separate scales for each head or channel. Each attention head gets its own minimum and scale values, letting it to use the full range of quantization levels regardless of what other heads are doing. This independence is particularly valuable because different attention heads often specialize in different types of patterns and may exhibit quite different value distributions. A head that specializes in syntactic dependencies may produce keys with very different statistical properties than a head that tracks coreference chains.

The additional overhead of per-channel quantization is modest: instead of storing two scalar parameters (min and scale) per tensor, we store two vectors with one entry per head. For a typical 32-head model, this is 64 additional float values per layer, negligible compared to the tensor itself. The quality improvement, however, can be substantial, particularly at aggressive bit widths where efficient use of the quantization range makes the difference between acceptable and unacceptable quality.

Per-channel quantization significantly reduces error at the same bit width because each attention head can use its full quantization range independently. The improvement is particularly pronounced at lower bit widths where the limited number of quantization levels makes efficient range utilization necessary. This technique allows INT4 per-channel quantization to approach the accuracy of INT8 per-tensor quantization in many cases, effectively doubling the compression while maintaining similar quality.

The most effective KV cache compression strategies combine multiple approaches to achieve multiplicative benefits. Rather than choosing between eviction and quantization, we can apply both: first reduce the number of cached tokens through intelligent eviction, then store the remaining tokens at reduced precision through quantization. This layered approach addresses memory from two complementary angles, and the benefits multiply rather than merely add.

The combination works so well because the two techniques address fundamentally different aspects of the memory problem. Eviction reduces the number of tokens we need to store, which scales with sequence length. Quantization reduces the bytes needed per token, which scales with the vector dimensions and precision. These are orthogonal dimensions of the memory tensor, and reducing both independently provides multiplicative compression. A 16x reduction in token count combined with a 2x reduction in bytes per token gives 32x total compression.

A practical configuration might use the following combination:

1. Attention sink preservation: Keep the first 4 tokens unconditionally to maintain computational stability.
2. H2O-style eviction: Maintain heavy hitters plus recent tokens to preserve both semantic importance and local context.
3. INT8 quantization: Store all cached values at 8-bit precision to halve the per-token memory footprint.

This level of compression enables generation at context lengths that would otherwise exceed available memory. A configuration that might require 16GB of KV cache memory without compression can operate within 500MB using these combined techniques. For deployment scenarios where memory is constrained or costs must be minimized, such aggressive compression makes previously infeasible applications practical. Production systems serving thousands of concurrent users on shared GPU hardware routinely rely on these techniques to make the economics viable.

Compression introduces approximation error that can degrade generation quality, and understanding the nature of this error is needed for making informed trade-offs. Different compression techniques produce qualitatively different error patterns, which affects how they impact the attention mechanism and ultimately the generated text. Characterizing these error profiles helps you choose the right compression strategy for each deployment scenario.

The most important dimension along which the error profiles differ is their locality. Quantization introduces globally distributed errors: every retained token's representation is slightly perturbed, but none are completely lost. Eviction introduces locally catastrophic errors: the evicted tokens are completely gone, but retained tokens are perfectly represented. These different error distributions lead to different failure modes that are worth understanding in depth.

Let's visualize how different compression strategies affect the attention computation:

The visualization reveals the distinct error profiles of each compression technique, illustrating a basic difference in how they affect the attention computation. Quantization introduces small, distributed errors across all positions, preserving the overall attention pattern while adding noise uniformly. The relative importance of tokens remains intact, and the model can still attend to the information it needs, albeit with slight imprecision. This graceful degradation makes quantization a relatively safe compression technique.

Eviction, by contrast, creates complete information loss for removed tokens. The error is not small and distributed but rather binary: retained tokens have zero error while evicted tokens have error equal to their original attention weight. The key to successful eviction is so that evicted tokens would have received near-zero attention anyway. When this condition holds, the total attention error is minimal because we are only losing tokens that contributed negligibly. When eviction removes a token that the model would have attended to significantly, generation quality suffers because that information is permanently lost.

The H2O algorithm's tracking of cumulative attention helps identify which tokens can be safely removed by giving evidence of their historical importance. Tokens that have consistently received minimal attention are unlikely to suddenly become necessary, making them safe eviction candidates. However, this heuristic is not perfect: a token that received little attention during the first 500 generation steps might become important at step 501 if the generated content shifts to reference that earlier context. This is the basic limitation of history-based eviction that no algorithm can fully overcome without knowledge of future generation steps.

KV cache compression involves basic trade-offs that require careful consideration before deployment. Understanding these limitations is not merely academic: getting compression wrong can cause visible quality degradation that harms user experience or produces incorrect outputs in high-stakes applications. The limitations fall into several distinct categories, each requiring different mitigation strategies.

The most significant limitation is task sensitivity. Some tasks are highly sensitive to long-range dependencies that may be evicted or distorted by compression. Summarization requires synthesizing information from across the entire input document, meaning that evicting middle-context tokens can omit important facts from the summary. Question answering over long documents requires retaining the specific passage that answers the question, which may not have received high attention during the reading phase. Multi-hop reasoning requires preserving intermediate conclusions that serve as anchors for later steps. For all of these tasks, aggressive eviction can cause catastrophic failures where the model simply does not have access to the information it needs to produce a correct answer.

Eviction strategies face the challenge of predicting future importance from past attention. A token that received little attention during the first 500 generation steps might become important at step 501, but if it was evicted, that information is permanently lost. This temporal mismatch is particularly problematic for tasks where relevance depends on the specific query or generated content. In conversational settings, a user might refer back to something said many turns earlier, and the model's ability to respond accurately depends on whether that old context survived eviction. Heavy hitter detection helps, but cannot anticipate all future needs, particularly for out-of-distribution or unexpected queries.

Quantization interacts with numerical precision in subtle ways that can be difficult to predict in advance. While INT8 typically works well, INT4 can cause issues for models that rely on precise attention scores. Grouped query attention and multi-query attention, as we covered in Part XXIX, already reduce KV cache memory by sharing key and value heads across multiple query heads. Combining these architectural choices with aggressive quantization requires careful validation because the reduced dimensionality means each cached value carries more semantic load, which makes it more sensitive to quantization error.

Cache compression also complicates batched inference in non-obvious ways. Different sequences in a batch may have different important tokens, requiring either per-sequence eviction decisions (which is complex and adds overhead) or a union of important tokens across sequences (which is less aggressive compression and may exceed memory budgets). When one sequence in a batch has important tokens at positions 50-100 while another has them at positions 200-300, a shared eviction policy cannot serve both optimally. PagedAttention, covered in the previous chapter, handles memory allocation elegantly with non-contiguous blocks, but the combination of dynamic eviction with paged allocation adds implementation complexity that most production systems find challenging.

Finally, the computational overhead of compression must be measured rather than assumed negligible. Tracking cumulative attention scores requires gathering attention weights at each step, averaging across heads, and performing a running update. Identifying heavy hitters requires a partial sort or top-k operation on the score vector. Performing quantization requires computing per-tensor or per-channel statistics plus element-wise arithmetic. For latency-sensitive applications serving interactive users, the overhead from these operations may offset a significant fraction of the memory savings. Simple approaches like StreamingLLM's sink-plus-window strategy often provide the best latency-memory trade-off because they require no attention tracking and no score computation: the eviction policy is purely positional and runs in constant time. When throughput matters more than latency, the additional computation for sophisticated eviction is easier to justify because memory savings translate directly into larger batch sizes and higher tokens per second.

A practical guideline for deploying compression is to start with INT8 quantization alone, since it provides 2x memory reduction with minimal quality impact and nearly zero computational overhead on modern hardware with INT8 tensor core support. Then, if memory remains insufficient, add StreamingLLM-style eviction with a generous window to avoid long-range dependency failures. Only consider more aggressive H2O-style eviction after measuring quality on your specific task and confirming that the quality degradation is acceptable. This incremental approach avoids deploying compression that is more aggressive than necessary, keeping quality impact bounded while still achieving substantial memory reduction.

The key parameters for KV cache compression are:

• sink_size: Number of initial tokens to always preserve in the cache. These attention sinks are necessary for stability and typically only 4 tokens are needed.
• window_size (or recent_size): Number of most recent tokens to keep. Ensures local context is available for coherent generation.
• heavy_hitter_size: Number of high-attention tokens to preserve based on historical importance. Larger values reduce eviction-induced quality loss at the cost of memory.
• bits: Target bit width for quantization (e.g., 4 or 8). Lower bits save more memory but may increase error. INT8 is almost always safe; INT4 requires validation.

The interaction between these parameters determines the memory-quality trade-off. A larger sink plus window budget allows more context but reduces compression. A higher bit width preserves more precision but uses more memory per token. Finding the right balance requires empirical evaluation on representative workloads rather than relying purely on theoretical analysis.

KV cache compression addresses the memory bottleneck of long-sequence generation through two complementary approaches: reducing the number of cached tokens through eviction, and reducing the precision of stored values through quantization.

Window-based eviction provides the simplest implementation but sacrifices all long-range context. Attention sink preservation recognizes that initial tokens serve as computational anchors and must be protected from eviction to maintain generation coherence. The H2O algorithm extends this by tracking cumulative attention to identify and preserve "heavy hitter" tokens that consistently receive high attention, balancing recency with historical importance. The key insight across all eviction strategies is that attention patterns are highly non-uniform and temporally persistent, which makes historical attention a reliable proxy for future importance.

Cache quantization offers orthogonal memory savings without removing any tokens from the cache. INT8 quantization typically achieves 2x compression with negligible quality impact. INT4 provides 4x compression but requires per-channel quantization and careful validation, particularly for precision-sensitive tasks. The basic mechanism is the same as general quantization: represent continuous values with discrete integers, accepting bounded approximation error in exchange for dramatic storage reduction.

Combining eviction with quantization can achieve compression ratios exceeding 30x for long sequences, letting use cases that would otherwise require prohibitive memory. The two techniques combine multiplicatively because they address orthogonal dimensions: eviction reduces token count while quantization reduces bytes per token. The choice of compression strategy depends on the specific use case. Tasks requiring precise long-range reasoning may tolerate only light compression, while streaming applications or tasks with primarily local dependencies can use aggressive compression. Understanding these trade-offs enables you to select appropriate configurations that balance memory efficiency with generation quality.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about KV cache compression techniques.