Key-Value Cache Eviction Strategies Trade Prefill Latency for Long-Context Generation Throughput

A one-million-token prompt consumes approximately two gigabytes of memory per user just to remember the text, a basis that means a single 80-gigabyte server graphics card can support fewer than 40 simultaneous readers. This physical limit dictates the economics of generative artificial intelligence.

The bottleneck restricting long-context models is rarely the raw processing power of the silicon. Instead, the constraint is the Key-Value cache, a temporary memory store that prevents the model from forgetting the beginning of a document by the time it reaches the end.

Every time a language model generates a new word, it must mathematically relate that new word to every previous word in the sequence. Without a cache, the system would have to recalculate the entire document from scratch for every single syllable it produces.

To avoid this redundant calculation, the system stores the intermediate mathematical representations in the graphics card's high-speed memory. As the conversation stretches into hundreds of thousands of words, this scratchpad balloons in size, eventually crowding out the model itself.

When the memory fills up, the server can no longer accept new users, forcing operators to buy more hardware. Solving this memory wall requires algorithms that can selectively forget useless information without degrading the quality of the final output.

The mechanics of the scratchpad

During the generation phase, known as decoding, the graphics card spends the vast majority of its time moving data rather than performing arithmetic. The processor sits idle waiting for the massive Key-Value cache to travel from the memory chips to the compute cores.

This data movement creates a severe bandwidth bottleneck that caps how many words the model can type per second. If the cache size can be reduced, the data travels faster, the compute cores stay busy, and the generation throughput increases dramatically.

Researchers realized that language models do not actually need to remember every single word with equal fidelity. Just as a human reader skims over filler words while focusing on nouns and verbs, an artificial intelligence concentrates its mathematical attention on specific, critical tokens.

If the system can identify which tokens the model ignores, it can evict them from the Key-Value cache entirely. This selective amnesia frees up gigabytes of memory, allowing the server to process larger batches of users simultaneously.

However, predicting exactly which words will be important ten paragraphs later is a complex statistical challenge. Evicting the wrong token can cause the model to hallucinate, lose the thread of the conversation, or fail at basic reasoning tasks.

Heavy hitters and attention sinks

The H2O algorithm, detailed in a 2023 research paper, addresses this by introducing the concept of heavy hitters. By tracking attention scores dynamically, the system retains only the most critical information and discards the rest.[1]

H2O demonstrates that dropping up to 80 percent of the cached tokens results in almost zero degradation in the model's reasoning capabilities. The algorithm simply discards the mathematical representations of filler words, punctuation, and resolved clauses.[1]

The SnapKV framework, introduced in April 2024, takes this eviction strategy further by analyzing the prompt before generation even begins. It recognizes that the language model knows what it is looking for during the initial reading phase.[2]

By clustering attention weights around specific features, SnapKV identifies the exact locations of important facts within massive documents. It then evicts the surrounding noise, shrinking the memory footprint while preserving the model's ability to answer precise questions about the text.[2]

These eviction strategies transform the economics of long-context generation by allowing operators to serve five times as many users on the same hardware. But this massive increase in generation throughput comes with a hidden cost in latency.[1][2]

The prefill penalty

Evicting tokens requires the system to calculate their relative importance, a process that introduces a severe computational tax upfront. To know which words to throw away, the model must first process the entire document at full resolution.

This initial processing phase, known as the prefill, becomes highly compute-bound as the eviction algorithms sort and rank millions of attention scores. The graphics card must perform trillions of extra calculations before it can generate a single word.

Users experience this computational tax as time-to-first-token latency, which is the awkward pause between pressing enter and watching the artificial intelligence start typing. Aggressive eviction strategies deliberately trade a longer initial pause for a much faster typing speed later.

For a 100,000-token document, calculating heavy hitters might add two seconds to the prefill latency, but it doubles the generation throughput from 20 tokens per second to 40. This trade-off is highly favorable for long-form writing, but detrimental for rapid chatbots.

The challenge for infrastructure engineers is that prefill and decode phases compete for the same hardware resources. When a server is busy reading a massive new prompt, it starves the decode process, causing the generation speed for all other users to stutter.

To prevent this interference, operators must isolate the compute-heavy prefill phase from the memory-heavy decode phase. This requires fundamentally redesigning how artificial intelligence clusters are networked together.

Disaggregating the pipeline

Cloud providers are solving this interference by physically separating the two phases into different server pools. Amazon Web Services architectures now disaggregate prefill and decode, routing the workloads to specialized hardware clusters.[3]

In a disaggregated setup, one set of graphics cards handles the heavy lifting of reading the prompt and compressing the cache. The technical documentation provided by Amazon Web Services details this architecture extensively, though it contains no direct quotations from the engineering team regarding the design process.[3]

Once the cache is compressed, it is shipped over the network to a separate pool of decode servers that specialize in rapid generation. These decode machines are optimized for memory bandwidth, allowing them to type out responses at maximum speed.[3]

Frameworks like Sarathi-Serve tame this throughput-latency tradeoff by dynamically scheduling these phases across the cluster. By breaking the prefill phase into smaller chunks, the system ensures that generation never stutters, even when processing massive documents.[5]

Sarathi-Serve uses a technique called chunked prefill to weave the heavy reading tasks into the brief moments when the decode servers are waiting for memory. This maximizes hardware utilization without forcing users to endure long pauses.[5]

Disaggregation allows operators to scale the prefill and decode clusters independently. If users are submitting massive documents but asking for short summaries, the operator can provision more prefill servers without wasting money on idle decode memory.[3][5]

Hardware compression and the future

Software eviction algorithms are now being reinforced by hardware-level compression techniques. Rather than just dropping tokens, engineers are shrinking the mathematical precision of the tokens they choose to keep.

NVIDIA's NVFP4 Key-Value cache formats, detailed in late 2025, reduce the stored numbers down to 4-bit floating-point values. This hardware optimization halves the memory footprint again, allowing for even larger batch sizes without sacrificing accuracy.[4]

By combining 4-bit hardware compression with 80-percent software eviction, operators can reduce the total cache size by a factor of ten. A one-million-token prompt that previously required two gigabytes of memory now fits into just 200 megabytes.[1][4]

This compounded efficiency is what makes features like infinite context windows and autonomous agents economically viable. Without these eviction and compression strategies, the cloud infrastructure would simply run out of memory.

The defining engineering challenge of the next generation of artificial intelligence is no longer just training smarter models. It is managing the brutal physics of memory bandwidth, ensuring the system can remember the past without choking on it.